Dynamic program analysis for error detection using goal-seeking input data generation
https://doi.org/10.15514/ISPRAS-2014-26(1)-15
Abstract
This paper describes the principles of program dynamic analysis for defect detection using input data generation. Techniques of program transformation allowing execution trace extraction, data flow tracing and input data generation for execution path coverage approaches are considered. We clarify in what way such an approach allows us to perform fully automatic analysis using executable or interpretable code. This paper also presents dynamic analysis tools developed at Institute for System Programming RAS---Avalanche (Valgrind-based tool) and a prototype tool for Java applications. The paper concludes with an evaluation of practical results of applying Avalanche tool to a set of open source projects as well as results of applying Java analysis tool to detect concurrency defects.
About the Authors
S. P. Vartanov
Institute for System Programming of RAS
Russian Federation
Russian Federation
A. Y. Gerasimov
Institute for System Programming of RAS
Russian Federation
Russian Federation
References
1. [1]. V. O. Savitsky, D. V. Sidorov. «Lenivyj» analiz iskhodnogo koda na yazykakh C i C++ [Lazy source code analysis for C/C++ languages] Trudy ISP RAN [The Proceedings of ISP RAS], 2012, vol 23, pp. 133-141. DOI: 10.15514/ISPRAS-2012-23-8. (in Russian)
2. [2]. V. O. Savitsky, D. V. Sidorov, Inkremental'nyj analiz iskhodnogo koda na yazykakh C/C++[Incremental source code analysis for C/C++ languages] Trudy ISP RAN [The Proceedings of ISP RAS], 2012, vol 22, pp. 119-129. DOI: 10.15514/ISPRAS-2012-22-8. (in Russian)
3. [3]. Novikova N. M. Osnovy optimizatsii [The Basics of Optimization]. M.: MGU [MSU], 1998. 17–22 p. (in Russian)
4. [4]. Eén N., Sörensson N. An Extensible SAT-solver. SAT 2003. P. 502-518.
5. [5]. Ganesh V., Dill D. L. A Decision Procedure for Bit-Vectors and Arrays // In Proceedings of Computer Aided Verification. 2007. P. 524–536.
6. [6]. Isaev I. K., Sidorov D. V. Primenenie dinamicheskogo analiza dlya generatsii vkhodnykh dannykh, demonstriruyushhikh kriticheskie oshibki i uyazvimosti v programmakh [The Use of Dynamic Analysis for Generation of Input Data that Demonstrates Critical Bugs and Vulnerabilities in Programs]. Programmirovanie [Programming and Computer Software]. 2010. # 4. P. 1-16. (in Russian)
7. [7]. Cadar C., Ganesh V., Pawlowski P., Dill D., Engler D. EXE: Automatically Generating Inputs of Death // Computer System Laboratory Stanford University. P. 14.
8. [8]. Dunbar D., Cadar C., Engler D. KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs // Stanford University. 2008.
9. [9]. Lattner C. The LLVM Compiler Infrastructure [HTML] (http://llvm.org/)
10. [10]. Goldefroid P., Levin. M. Y, Molnar D. SAGE: Whitebox Fuzzing for Security Testing // Communications of the ACM. 2012. 55. P. 40–44.
11. [11]. Valgrind. Instrumentation Framework for Building Dynamic Analysis Tools [HTML] (http://valgrind.org/)
12. [12]. Drewry W., Ormandy T. Flayer: Taint analysis and flow alteration tool [HTML] (http://code.google.com/p/flayer/)
13. [13]. Molnar D., Wagner D. Catchconv: Symbolic execution and run-time type inference for integer conversion errors // UC Berkeley, 2007.
14. [14]. Apache Commons Byte Code Engineering Library [HTML] (http://commons.apache.org/bcel)
15. [15]. Visser W., Păsăreanu C. S., Khurshid S. Test Input Generation with Java PathFinder // Proceeding ISSTA '04 Proceedings of the 2004 ACM SIGSOFT international symposium on Software testing and analysis. P. 97–107.
16. [16]. Serebryany K., Iskhodzhanov T. ThreadSanitizer—data race detection in practice. WBIA '09, New York City, NY, USA, 2009
17. [17]. Ermakov M. K., Gerasimov A. Y. Avalanche: adaptation of parallel and distributed computing for dynamic analysis to improve performance of defect detection [Avalanche: primenenie parallel'nogo i raspredelennogo dinamicheskogo analiza programm dlya uskoreniya poiska defektov i uyazvimostej] Trudy ISP RAN [The Proceedings of ISP RAS], 2013, vol 25, pp. 29-38. DOI: 10.15514/ISPRAS-2013-25-2. (in Russian)
18. [18]. Vartanov S. P., Gerasimov A. Y. Applying dynamic analysis for defect detection in Java-applications [Primenenie dinamicheskogo analiza dlya poiska defektov v programmakh na yazyke Java] Trudy ISP RAN [The Proceedings of ISP RAS], 2013, vol 25, pp. 9-28. DOI: 10.15514/ISPRAS-2013-25-1. (in Russian)
Review
For citations:
Vartanov S.P., Gerasimov A.Y. Dynamic program analysis for error detection using goal-seeking input data generation. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2014;26(1):375-394. (In Russ.) https://doi.org/10.15514/ISPRAS-2014-26(1)-15
Email this article 