Contents
Introduction
In order to produce high-quality code, compilers have to rely on
the results of static program analyses. To date, implementing these analyses has
been difficult, expensive and error-prone. The PAG
Program Analyzer Generator provides automatic tool support for generation of
efficient analyzers from concise specifications. However, while PAG makes it easy
to create an analyzer and to integrate the analyzer into a compiler, it is not
appropriate for program analysis novices, because it requires deep understanding
of the PAG internals to get started.
This is where PAG/WWW steps in. PAG/WWW is a simplified version
of PAG which tries to close the gap between theory and practice by implementing
an easy-to-use system for experimenting with program analysis that is easily
accessible to everyone through the World Wide Web.
The PAG/WWW system implements the
WHILE language and classical data flow
analysis introduced in Principles
of Program Analysis (Nielson, Nielson, Hankin, 1999) so that users can
experiment with program analysis without having to care too much about the theoretical
background. All classical analyses are already predefined and there are even
example programs (which makes PAG/WWW an ideal addition to the book) —
but PAG/WWW also allows the users to easily specify their own programs and analyses.
The structure of PAG/WWW
PAG/WWW consists of two parts: The WWW user interface and the
PAG/WWW backend. The purpose of this construction is to keep the users of PAG/WWW
away from the PAG internals.
The user interface guides the user through the setup for running
program analyses, namely choosing a standard analysis or writing a custom analysis
specification and choosing an example program or writing a new program to be analyzed.
The analysis specification and the program are then passed to the backend. The backend
takes the user input and builds an analyzer from the specification which is then run
on the given WHILE program. The analysis results are summarized and
passed back to the user interface (cf. Figure 1).
Figure 1: The structure of PAG/WWW
PAG/WWW and PAG
The PAG/WWW backend relies on the functionality of PAG to build and run the
analyzer. It automatically performs the following steps:
- Check the analysis specification for errors and translate it into PAG input.
- Run PAG. This produces a set of C files that make up the analyzer.
- Compile these files to build the analyzer.
- Check the
WHILE program for errors and build a control flow graph,
which can be processed by the analyzer.
- Run the analyzer on the WHILE program.
- Extract analysis results and pass them back to the user interface.
The analysis results are summarized in a table by routines of the
backend. In addition, images of the control flow graph for each analysis step are
generated using a freely available graph
visualization tool. An illustrative example of the
analysis steps is available as well as detailed information on how to
interpret analysis results.
Figure 2 shows the analyzer generation process inside PAG.
The PAG/WWW user needs to care only about the input that is marked red.
Figure 2: The automated execution steps of PAG/WWW.
PAG features left out in PAG/WWW
In order to make PAG/WWW usable for non-experts, there are
restrictions to the program specification and to the analysis specification.
The WHILE language is a very simple imperative language similar
to Pascal. The original PAG is designed to handle any programming language,
even assembler.
PAG/WWW features a functional language called FULA to specify
an analysis, i.e. the transfer functions, the definitions of custom data types
and the analysis parameters. This language is a modified version of the one used
in PAG, specialized for the use with the WHILE language and optimized
for the interactive generation of analyzers. The syntax of the analysis specification
language is simplified and the following features are left out:
- Syntactical lists, patterns and constructors
- Bit operators
- Sets/Domains differentiation
Due to the simplifications listed above, a speed optimization was possible,
leading to little waiting time for analysis results.
Search
| 