Ivannikov Institute for System Programming of the RAS


Avalanche: dynamic program analysis tool

Avalanche is a defect detection tool based on Valgrind dynamic instrumentation framework. It performs an extensive analysis of a target program by tracing tainted data flow (all external input data received through input streams, file system, network sockets, environment variables and command line arguments, and internal program data derived from external input data) through executed code branching points. Collected data is used to generate special queries which are subsequently processed by an SMT solver to produce modified input data sets; these data sets provide different execution paths when processed by the target program. Thus, through an iterative process every possible execution path in the target program is traversed and checked for critical runtime defects.

Avalanche analysis results include a full a report on detected defects as well as input data sets to be used to reproduce the corresponding defects.

Tainted data flow analysis and iterative execution path traversal feature the following advantages over similar methods:

  • no dependence on target program source code;
  • zero false positive rate for determinate programs;
  • potentially high coverage rate;
  • no additional costs to reproduce defects.

Avalanche tool was successfully applied to an extensive set of open-source projects resulting in a number of critical defects being detected. These defects include null pointer dereference situations, mathematical errors (division by zero) and other situations causing critical program failure.

Current work on the project focuses on the following three major research directions:

    the use of parallel and distributed computing models; targeted dynamic analysis – traversing execution paths through specific program modules; hybrid static and dynamic analysis approach – using Avalanche to automatically reproduce and verify defects detected through a static analysis tool.

Publications

  1. Ildar Isaev, Denis Sidorov, Alexander Gerasimov, Mikhail Ermakov. Avalanche: Using dynamic analysis for automatic defect detection in programs based on network sockets. Proceedings of the Institute for System Programming Volume 21. 2011 . pp. 55-70.
  2. Sergey Vartanov, Denis Sidorov. Optimization of Boolean satisfiability solver by caching intermediate results. Proceedings of the Institute for System Programming Volume 22. 2012 . pp. 281-292.
  3. M.K. Ermakov, A.Y. Gerasimov. Avalanche: adaptation of parallel and distributed computing for dynamic analysis to improve performance of defect detection. Proceedings of the Institute for System Programming Volume 25. 2013 . pp. 29-38.

Projects

Avalanche: dynamic program analysis tool

Developer/Participant

System Programming

Back to the list of technologies of ISP RAS