Skip to main content

Transfer Function Synthesis without Quantifier Elimination (long version)

Brauer, Jorg, King, Andy (2012) Transfer Function Synthesis without Quantifier Elimination (long version). Logical Methods in Computer Science, 8 (2012). (KAR id:30800)

PDF (Logical Methods in Computer Science) Author's Accepted Manuscript
Language: English
Download this file
(PDF/840kB)
[thumbnail of Logical Methods in Computer Science]
Preview
Request a format suitable for use with assistive technology e.g. a screenreader
Official URL:
http://www.cs.kent.ac.uk/pubs/2012/3238

Abstract

Traditionally, transfer functions have been designed manually for each operation in a program, instruction by instruction. In such a setting, a transfer function describes the semantics of a single instruction, detailing how a given abstract input state is mapped to an abstract output state. The net effect of a sequence of instructions, a basic block, can then be calculated by composing the transfer functions of the constituent instructions. However, precision can be improved by applying a single transfer function that captures the semantics of the block as a whole. Since blocks are program-dependent, this approach necessitates automation. There has thus been growing interest in computing transfer functions automatically, most notably using techniques based on quantifier elimination. Although conceptually elegant, quantifier elimination inevitably induces a computational bottleneck, which limits the applicability of these methods to small blocks. This paper contributes a method for calculating transfer functions that finesses quantifier elimination altogether, and can thus be seen as a response to this problem. The practicality of the method is demonstrated by generating transfer functions for input and output states that are described by linear template constraints, which include intervals and octagons.

Item Type: Article
Additional information: Available as http://arxiv.org/abs/1207.4286
Uncontrolled keywords: abstract interpretation, best transform, transfer functions, binary analysis
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Andy King
Date Deposited: 21 Sep 2012 09:49 UTC
Last Modified: 16 Nov 2021 10:08 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/30800 (The current URI for this page, for reference purposes)

University of Kent Author Information

  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.