Principles and Practice of Program Analysis
Semester II, 2024/2025
Program Analysis
A process of automatically analyzing the runtime behavior. of a computer program.
• TRADITIONAL USES: Program optimization (compilers)
To improve the program’s performance while reducing the resource usage
• MODERN USES: Verification, Testing, Debugging, Synthesis, Vulnerabilities, Performance estimation, …
To ensure “correctness”: that the program will do what it is supposed to
Program analysis can be performed without executing the program (static program analysis), during runtime (dynamic program analysis), or in a combination of both.
Static and Dynamic Program Analysis
• STATIC
SPA is performed without actually executing programs, usually on some representation of the source code or low-level code. The most common representation is the Control Flow Graph.
• DYNAMIC
DPA is the analysis of computer software that is performed by executing programs on a real or virtual processor. For DPA to be effective, the target program must be executed with sufficient test inputs to produce interesting behavior. Use of software testing measures such as code coverage helps ensure that an adequate slice of the program’s set of possible behaviors has been observed.
Static Analysis
Some Traditional Analyses
• PEEPHOLE OPTIMIZATION (LOW LEVEL)
Examine a few adjacent instructions (like “looking through a peephole” at the code) to see whether they can be replaced by a single instruction or a shorter sequence of instructions. Eg. For multiplication by 2 is more efficiently executed by left-shifting or by adding.
• LOOP OPTIMIZATION
The idea is to move loop-invariant code within a loop body to outside the loop. Eg. the assignment to x is loop invariant in the loop below and thus can be moved before the loop.
for (i=0; i
Note that it is generally very difficult to discover loop invariants.
• REGISTER ALLOCATION
To assign a large number of target program variables onto a small number of CPU registers. Not all variables are in use (or “live”) at the same time, so some registers may be assigned to more than one variable. Liveness analysis can construct a graph of variables, with edges indication pairwise simultaneous liveness. To determine the minimum number K of registers then is reduced to K-Coloring Problem (NP-complete).
Some Modern Analyses
• Are arrays always accessed within their bounds? (Common error)
• Can a secret value flow into an observable variable? (Information leakage)
• At which program points could x be assigned its current value? (common for program understanding)
• How large can the heap become during execution? (Important for emdedded systems, IoT)
• Does the program contain dead code? (Can make program smaller)
• Does there exist an input that leads to a null pointer dereference, division by zero, or arithmetic overflow? (Runtime error)
• Are all variables initialized before they are read? (If not, the program may be vulnerable to attacks by malicious users.)
• Can the value of certain “secret” variables be learnt from running the program?
(Information leakage via Side-Channel attack)
• Can there be dangling references, e.g. pointers to memory that has been freed? (Cause for security)
Related Areas
• PROGRAM VERIFICATION
To ensure that a given property is never violated in any execution of the program. Often it is impossible to build a complete program verifier.
• RUNTIME VERIFICATION
Runtime verification is a computing system analysis and execution approach based on extracting information from a running system and using it to detect and possibly react to observed behaviors satisfying or violating certain properties.
• TESTING
A set of tests can be obtained by random or systematic methods. Blackbox testing considers the program as a “black box” and does not scrutinize the source code. Whitebox testing on other hand considers the program structure in considering the test cases.
• QUANTITATIVE ANALYSIS
There is a class of analyses which serves to determine the resource usage of a program. Typically for embedded systems, resources of interest involve time, size of (dynamic) memory (maximum size or high-water-mark), or energy.
Challenges to Program Analysis
• DECIDABILITY
All interesting questions about program properties are undecidable.
(Rice 1953)
• COMPLEXITY
Most interesting questions about programs are intractable (NP-hard or worse)
• SCALABILITY
In order to analyze large programs, program analyzers need to have near linear complexity
The General Approach
Program analysis is usually an approximate process.
• OVER-APPROXIMATE
To compute more properties than is true.
(Eg. to say a variable x is less than 10, when in fact it is binary.)
Analysis is sound if it never returns a wrong answer.
• UNDER-APPROXIMATE
To compute less properties than is true.
The process of verification is no longer possible.
We can however do program testing.
to show the existence of an execution with some property.
BUT: Program testing can be used to show the presence of bugs, but never to show their absence. (Dijkstra 1970)