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 interpretation 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 and GrammaTech, Inc.