Proceedings of ISP RAS


Formalization of Error Criteria for static symbolic execution

V.K. Koshelev (ISP RAS, Moscow, Russia)

Abstract

This paper is devoted to the formalization of the error criteria for program static analysis, based on symbolic execution. Using the original error criteria of symbolic execution approach in program static analysis leads to an excessive number of false positives. To solve this problem, we propose an alternative definition of the error criteria.  Proposed definition reports errors only if they occur on a certain set of input variables. Examples of such sets are the set of values ​​of input variables in which control will pass through a given point of the program, or set of values ​​in which the controls take place along a given path in the control flow graph. This paper discusses the various ways to specify such sets of initial values, including analysis of the final error criteria. We overview algorithms corresponding to the error criteria and prove their correctness. Finally, we consider the practical applications of the given error criteria, which include classification of the warnings generated by static analysis tools; taking into account unknown function contracting, especially preconditions; using the proposed error criteria as formulas for a SMT-solver. The latest application allows to get the precise solution of the particular error criteria, including the error trace.

Keywords

static analysis, error criteria, symbolic execution

Edition

Proceedings of the Institute for System Programming, vol. 28, issue 5, 2016, pp. 105-118.

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

DOI: 10.15514/ISPRAS-2016-28(5)-6

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