Proceedings of ISP RAS


A Static Analysis Tool Svace as a Collection of Analyzers with Various Complexity Levels

A. Borodin (ISP RAS, Moscow), A. Belevancev (ISP RAS, Moscow; MSU, Moscow)

Abstract

The paper describes a practical approach for finding bugs in the source code of
programs using static analysis.  The approach is implemented in the Svace tool that is developed by ISP RAS. Svace performs defect detection for different error types including null pointer dereferences, buffer overruns and underruns, uninitialized variables usages, memory leaks, double locks and missing locks, unreachable code, division by zero, use after free and others.
The analysis goal is to find as many defects as possible while minimizing false positives with acceptable analysis time.  As a result, on large programs the approach inevitably results in missing some defects.
Even critical program defects exist because of various reasons, and the right analysis approach should be detected based on a defect type. A good analyzer will include both simple detectors using only semantic analysis on an abstract syntax tree (AST) and complex detectors using interprocedural context and path sensitive analyzers. The Svace analyzer is designed for that purpose as a collection of analyzers having various levels: an AST analyzer, a conservative data flow analyzer, flow, context and path sensitive interprocedural analysis that makes a few assumptions losing conservativeness. The interprocedural analysis is annotation based: each function is analyzed only once, and its annotation created to summarize the analysis results is used when simulating this function’s call. All described algorithms are presented and illustrated using examples of various detectors and their real warnings found on a number of open source projects.

Keywords

static analysis; C language; defects in source code; abstract syntax tree; flow-sensitivity; path-sensitivity; interprocedural analysis; unsound analysis; null pointer dereference

Edition

Proceedings of the Institute for System Programming, vol. 27, issue 6, 2015, pp. 111-134.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2015-27(6)-8

Full text of the paper in pdf (in Russian) Back to the contents of the volume