Joy of Programming: The Technology Behind Static Analysis Tools

To answer these questions, we need to understand the technology behind static analysers. In this column, I will first provide a detailed overview of static analysers and then delve into the different analysis techniques, many of which are formal, i.e., applied mathematics for modelling and analysing computer systems (hardware or software). For each technique, I will also mention widely adopted (open source or commercial) tools that use the specific technology; and highlight the possibilities of implementing your own static analysers (i.e., ideas for your six-month academic project).

Analysing programs to gather facts on them is known as program analysis. This can be performed dynamically, i.e., by actually executing the program and gathering facts. For example, when you test a program, you are performing dynamic program analysis, where you check if the program leaks memory, or fails with a null-pointer access exception. Program analysis can also be performed statically, i.e., without actually executing the program, and gathering facts. For example, when you review code, you don’t actually execute the program — you just analyse the program in your mind, and find bugs in the program, such as null-pointer access.

So what are static analysers? They are tools that analyse the program without actually executing it. Static program analysis can be performed for a wide variety of reasons. However, two main applications of program analysis are to optimise code, and to find bugs. A compiler optimiser analyses programs to understand how it can generate more efficient code. Bug-detection tools analyse programs to see if there are any mistakes in the program, such as buffer overflows, that can lead to runtime errors. Our focus is on static analysis to find bugs.

Before we go ahead, note that static analysers can be used for purposes other than finding bugs: to find instances of the use of design patterns, to find duplicate code segments (code clones), to report metrics (measurement results such as Depth of Inheritance Tree) results, for code comprehension and reverse engineering (generate documentation or higher-level design diagrams to aid understanding the program), etc. Also note that static analysis can be performed on different software artefacts, such as design diagrams (e.g., UML diagrams), structured contents (e.g., XML files), grammars (e.g., yacc programs), etc. Further, the input to static analysers need not be just source code; it can also be byte code (as in Java/C#) or executable code (e.g., native code generated from C/C++ programs). Here, we mainly focus on techniques to find bugs, i.e., code or design problems, from code.

An overview of technologies

Static analysers are implemented using a wide range of technologies. I’ll describe them starting from the simple ones to the more complex. A warning before we proceed: topics such as theorem proving and abstract interpretation are quite technically complex, so I will present the overall idea behind the technique and leave it to you to explore the concepts further and figure them out.

Bug pattern matching

Some bugs are easy to find, even without the use of sophisticated technologies. For example, it is a common mistake in C/C++ to type = instead of == in condition checks. We can easily detect this ‘bug pattern’ by checking if the = operator is used for condition checks. This is typically performed by matching the coding pattern in the program with the expected bug pattern at the AST (Abstract Syntax Tree) level, as in the case of the classic, free “lint” program in UNIX (today, Gimpel sells better lints under the name PC-Lint for Windows and Flexlint for UNIX flavours; see gimpel.com). FxCop is a free C# tool from Microsoft that matches bug patterns at byte code level.

One main advantage with bug pattern-matching is that the tool can execute quite fast even on a large code base, and even on partially written programs (i.e., work-in-progress code with syntax or semantic errors that won’t compile successfully). The main disadvantage of bug pattern-matchers is that they are not effective in finding useful runtime errors such as null-reference or divide-by-zero errors. Since their analysis is shallow, they report wrong or false errors, technically referred to as ‘false positives’.

Most bug pattern matching tools provide support for extending the tool. For example, FxCop has a documented API, and you can write your own (i.e., custom) rules using the API. The Eclipse IDE supports JDT and CDT for Java and C/C++, respectively. JDT/CDT’s ASTs are exposed as APIs. If you learn the AST and the API, you can write a bug detector as a summer project.

Since lint is perhaps the earliest of static analysers, even today, when people refer to static analysis tools, they have a lint-like tool in mind. However, today there are sophisticated and different technologies used to find bugs, as we’ll see later in this article.

Data-flow analysis

In data flow analysis (DFA), the runtime information about the data in programs is collected. This analysis is typically performed by traversing over the control-flow graph (CFG) of the program. Now, what is a CFG? It can be thought of as an abstract representation of functions in a program, in a graph. Each node in the graph represents a basic block, and directed edges are used to represent jumps in the control flow. Now what is a basic block? It is a sequence of statements where the control enters at the beginning, leaves only at the end, and the control cannot halt or branch out of the block (except, of course, at the end).

Now, DFA can be performed to find bugs such as null-pointer access. From the point where the pointer variable is initialised, and where it is de-referenced, we can find out the path(s) in which the value of the pointer variable is still null when it is de-referenced. DFA can be intra-procedural or inter-procedural, i.e., the analysis can be limited only to within a function or to the whole program. The analysis is typically performed by using standard algorithms, and they are not computationally intensive. However, analysing the whole program is costly in terms of processing time and/or the memory space required. Hence, many static analysers limit themselves to intra-procedural analysis. For example, FindBugs is an open source tool that performs bug pattern matching for simple problems, and performs DFA to detect problems such as null-pointer access at the intra-procedural level.

DFA is mainly used by compiler optimisers to generate efficient code. DFA does not gather much useful information based on the semantics of the programming languages and their operators. Hence, it is useful for finding bugs, but is still not very effective.

Abstract interpretation

Abstract interpretation is approximating the program semantics by replacing the concrete domain of computation and their operations to an abstract domain of computing and their operations. I know this description is confusing; so, let me explain abstract interpretation with a standard introductory example about rules-of-sign that we learnt in school.

Consider the expression (-123*456). What is the sign of this expression? Without actually calculating the resulting value, we can say that the expression results in a negative value. How? We know the rules-of-sign: multiplying a negative value with a positive value results in a negative value. In other words, the expression can be abstractly interpreted as (negative-value * positive-value) => negative-value. If we actually perform the arithmetic to find the sign, we will be performing concrete interpretation; if we abstract them and perform arithmetic to find the sign, we are performing abstract interpretation. Now, how is it useful for finding bugs? Consider a simple C example:

float f1 = -4;
float f2 = 4;
printf("%lf", sqrt(f1 * f2));

We need not have to actually evaluate (concretely interpret) the expression f1 * f2 to find that it results in a negative value—and it is an invalid arithmetic operation to try to get the square root of a negative number; we can reach the same conclusion if we abstractly interpret the expression.

There are many commercial tools that use abstract interpretation to find bugs — for example, Polyspace from Mathworks. Abstract interpretation is computationally very expensive, and choosing an appropriate abstract value domain and heuristics for determining termination are important to make it practically usable on large code-bases. Most commercial tools that use this technology are also costly.

Symbolic execution is analysing the program by tracking the symbolic values instead of actual values. In a way, symbolic execution (or analysis, or evaluation) is abstract interpretation; in fact, every kind of deeper analysis without executing the program can be seen as abstract interpretation!

Model checking

Program execution can be viewed as the transition of the program from one state to another state. Most states are valid, and some are error states. Examples of error states are the program states when divide-by-zero, deadlock or buffer-overflow happens. Model checking is an automated verification technique, where the possible system behaviour (i.e., implementation behaviour) is matched with the desired behaviour (specified properties). In other words, a model checker ideally checks all possible system states and verifies if the given properties hold. If the property does not hold for a certain reachable state, then the property is violated, and a counter example is thrown to the user about the violation. Java PathFinder (JPF) is an open source tool that explicitly constructs state models to check the software.

In practice, exhaustive checking of all system states is not feasible for commercial software, which often consists of millions of lines of code. In other words, if the transition system representing the program has too many states, then it becomes very difficult to check the system against the properties; this is known as a state-explosion problem. Many techniques are being developed to address this problem, and already some solutions are being widely used. One is to construct only part of the state space of the program, and as state transitions are explored, more states are built, as the need arises. Another approach is to use ‘symbolic checking’. In this approach, the states and transitions are implicitly represented using Boolean formulas, known as Binary Decision Diagrams (BDDs). Now the solvers that work on BDDs can be used, and this simplification considerably pushes the limits on the size of the programs that can be checked. For example, the SLAM/SDV tool from Microsoft automatically creates Boolean program abstraction from a C program, and model checking is applied on the resulting Boolean program. The SDV tool is shipped with the Windows Driver Development Kit (WDK).

Model checking can find defects that are generally hard-to-detect using conventional techniques like testing. Also, model checking can be used for sequential as well as concurrent programs (as we know, concurrent programs can have bugs that are non-deterministic, and hence model checking is very useful).

Program querying

The fundamental idea behind program querying is that a program can be viewed as structured data (in other words, a database), and we can perform queries on it to get the necessary information. In implementing this idea, the program can be implicitly treated as a database or it can explicitly use a database such as MySQL. Similarly, for querying the data, one can use an SQL-like language, or SQL itself. For example, NDepend is a tool that generates code and design metrics. With its Code Query Language (CQL), we can write SQL-like queries to obtain data on the program. A list of query languages is provided at cs.nyu.edu.

Logic programming languages such as Prolog use a database of facts, and queries in these languages allow for inferring relationships from the given set of facts. For this reason, Prolog and its variants, such as Datalog, are widely used for static analysis, particularly for inferring design patterns or anti-patterns. For example, the JTransformer tool translates a Java program to Prolog facts. Now, it’s possible to implement tools such as Cultivate, which use the Prolog facts generated by JTransformer, and infer design metrics as well as violations.

Static analysis is a useful and cost-effective way to find bugs early in the software development life-cycle, and complements other approaches such as testing. In this article, I have outlined different technologies for static analysis, and hope you’ll appreciate the fact that the technologies applied for static analysis are advanced. If you’re a student, you’ll find the writing tools to automatically find bugs interesting and challenging; you can start learning about the technology that interests you, and implement your own detector. Many of the widely used and free tools, such as PMD, FindBugs, CheckStyle, FxCop and StyleCop, provide extensibility facilities to write your own rules; so you can also learn by implementing new rules and testing them, before starting to write a full-fledged bug detector.