Proceedings of ISP RAS


An approach of reachability determination for static analysis defects with help of dynamic symbolic execution

Gerasimov A.Y. (ISP RAS, Moscow, Russia)
Kruglov L.V. (ISP RAS, Moscow, Russia)
Ermakov M.K. (ISP RAS, Moscow, Russia)
Vartanov S.P. (ISP RAS, Moscow, Russia)

Abstract

Historically program analysis methods are divided into two groups – static program analysis methods and dynamic program analysis methods. In this paper, we present a combined approach which allows to determine reachability for defects found by static program analysis techniques through applying dynamic symbolic execution for a program. This approach is an extension of our previously proposed approach for determining the reachability of specific program instructions using dynamic symbolic execution. We focus on several points in the program which include a defect initialisation point, a defect realisation point, and additional intermediate conditional jumps related to the defect in question. Our approach can be described as follows. First of all, we perform static analysis of program executable code to gather information on execution paths which guide dynamic symbolic execution to the point of defect initialisation. Next, we perform concolic execution in order to obtain an input data set to reach the defect initialisation point as well as the defect realisation point through intermediate conditional jumps. Concolic execution is guided by minimizing the distance from a previous path to the next defect trace point when selecting execution paths. The distance metric is calculated using an extended graph of the program combining its call graph and portions of its control flow graph that include all the paths through which the defect realisation point can be reached. We have evaluated our approach using several open source command line programs from Linux Debian. The evaluation confirms that the proposed approach can be used for classification of defects found by static program analysis. However, we have found some limitations, which prevent deploying this approach to industrial program analysis tools.  Mitigation of these limitations serves as one of the possible directions for future research.

Keywords

static program analysis; dynamic program analysis

Edition

Proceedings of the Institute for System Programming, vol. 29, issue 5, 2017, pp. 111-134.

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

DOI: 10.15514/ISPRAS-2017-29(5)-7

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