TSL: A System for Generating Abstract Interpreters
and its Application to Machine-Code Analysis
Junghee Lim and Thomas Reps
This paper describes the design and implementation of a system, called
TSL (for ``Transformer Specification Language''), that provides a
systematic solution to the problem of creating retargetable tools
for analyzing machine code. TSL is a tool generator -- i.e., a
meta-tool -- that automatically creates different abstract interpreters
for machine-code instruction sets.
The most challenging technical issue that we faced in designing
TSL was how to automate the generation of the set of
abstract transformers for a given abstract
interpretaton of a given instruction set. From a description of the
concrete operational semantics of an instruction set, together with
the datatypes and operations that define an abstract domain, TSL
automatically creates the set of abstract transformers for the
instructions of the instruction set. TSL advances the state of the art
in program analysis because it provides two dimensions of
parameterizability: (i) a given analysis component can be retargeted
to different instruction sets; (ii) multiple analysis components can
be created automatically from a single specification of the concrete
operational semantics of the language to be analyzed.
TSL is an abstract-transformer-generator generator.
The paper describes the principles behind TSL, and discusses how one
uses TSL to develop different abstract interpreters.
(Click here to access the paper:
PDF.)
University of Wisconsin