Proceedings of ISP RAS


Path-Sensitive Bug Detection Analysis of C# Program Illustrated by Null Pointer Dereference

V. Koshelev (ISP RAS, Moscow), I. Dudina (ISP RAS, Moscow), V. Ignatyev (ISP RAS, Moscow), A. Borzilov (ISP RAS, Moscow)

Abstract

This paper proposes an approach for detecting bugs in C# programs and uses null pointer deference as the main example. The approach employs a scalable path-sensitive analysis, which involves symbolic execution with state merging and function summary methods. C/C++ program analyzers like Saturn Software Analysis Project, Calysto or Svace use similar approaches. We analyze functions in backward topological order with account for previously calculated summaries. For summary construction, we use the same analysis engine as for bug detection. The paper contains a formal description of the proposed approach applied to reduced “sugar-free” subset of C# language. For each instruction of the considered language, we define a formal semantics and transfer function according to the symbolic state. During the path-sensitive analysis, we store additional information related to possible bugs in the symbolic state, and the decision whether the warning should be reported is made upon the satisfiability of the corresponding formula. Therefore, we reduce the problem of bug detection to satisfiability of a first-order logical formula defined on atoms, which are arithmetic expressions on function input values. It can be efficiently solved with modern SMT solvers. We have implemented the approach in our Roslyn-based analyzer, called SharpChecker. Evaluation of SharpChecker on open-source commodity applications has shown acceptable scalability and reasonable amount of warnings.

Keywords

static analysis; null pointer dereference; path-sensitive analysis; function summary; bug detection

Edition

Proceedings of the Institute for System Programming, vol. 27, issue 5, 2015, pp. 59-86.

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

DOI: 10.15514/ISPRAS-2015-27(5)-5

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