Proceedings of ISP RAS


Avalanche: adaptation of parallel and distributed computing for dynamic analysis to improve performance of defect detection.

M.K. Ermakov, A.Y. Gerasimov.

Abstract

This paper focuses on dynamic program analysis optimization through the use of distributed computing scheme and parallel computing for checking satisfiability of Boolean constraint sets. The paper is organised as follows: section 1 contains an overview of the Avalanche tool and identifies the key points of its work flow and module structure applicable to distributed and parallel optimizations. Sections 2 and 3 provide general schemes of parallel and distributed program analysis respectively: parallel approach is based on the relative independence of several execution constraint sets; distributed approach is based on a protocol for communication between a number of computing units targeted at sharing sub-trees of execution paths in the analysed program. An overview of results obtained from applying the practical implementation of parallel and distributed schemes of dynamic analysis to a number of open-source applications is given. The paper presents a detailed evaluation of the increased efficiency (in terms of the number of defects detected, as well as relative detection time) of dynamic analysis achieved while applying developed techniques. Section 4 concludes the paper with an overview of possible issues related to nondeterministic nature of parallel and distributed approaches and discusses future directions for research on the Avalanche tool.

Keywords

dynamic analysis, defect detection, parallel computing, distributed computing

Edition

Proceedings of the Institute for System Programming, vol. 25, 2013, pp. 29-38.

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

DOI: 10.15514/ISPRAS-2013-25-2

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