Multilevel static analysis for improving program quality

Abstract

In this paper, we discuss some program analysis methods for finding defects in source code that are combined to form a multilevel analysis system. The first level consists of the checks using abstract syntax tree (AST) walks and intraprocedural dataflow; this level also builds a memory model for the subsequent levels. The memory model requires evaluating integer expressions and points-to sets. The second level is an interprocedural summary-based approach whereby the program features of interest are calculated as attributes of value classes that are formed in the program. Finally, the third level is a path-sensitive analysis that builds reachability formulas for program points and tracks the predicates that should hold for the desired features to be observable. The errors are found by testing the formulas for satisfiability with an SMT solver. All these levels of analysis are implemented in the Svace analyzer toolset, which demonstrates scalability up to millions of lines of code and precision of 60–90% true positives.