Statically-directed dynamic automated test generation
Authors:
Open Access
- 17 July 2011
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 12-22
Abstract
We present a new technique for exploiting static analysis to guide dynamic automated test generation for binary programs, prioritizing the paths to be explored. Our technique is a three-stage process, which alternates dynamic and static analysis. In the first stage, we run dynamic analysis with a small number of seed tests to resolve indirect jumps in the binary code and build a visibly pushdown automaton (VPA) reflecting the global control-flow of the program. Further, we augment the computed VPA with statically computable jumps not executed by the seed tests. In the second stage, we apply static analysis to the inferred automaton to find potential vulnerabilities, i.e., targets for the dynamic analysis. In the third stage, we use the results of the prior phases to assign weights to VPA edges. Our symbolic-execution based automated test generation tool then uses the weighted shortest-path lengths in the VPA to direct its exploration to the target potential vulnerabilities. Preliminary experiments on a suite of benchmarks extracted from real applications show that static analysis allows exploration to reach vulnerabilities it otherwise would not, and the generated test inputs prove that the static warnings indicate true positives.Keywords
Funding Information
- Office of Naval Research (N000140911081)
- National Science Foundation (8.33E+33)
- Air Force Research Laboratory (P010071555)
- Air Force Office of Scientific Research (FA9550-08-1-0352FA9550-09-1-0539)
This publication has 35 references indexed in Scilit:
- WYSINWYXACM Transactions on Programming Languages and Systems, 2010
- Adding nesting structure to wordsJournal of the ACM, 2009
- Analysis of modular arithmeticACM Transactions on Programming Languages and Systems, 2007
- Weighted pushdown systems and their application to interprocedural dataflow analysisScience of Computer Programming, 2005
- Exploring very large state spaces using genetic algorithmsInternational Journal on Software Tools for Technology Transfer, 2004
- Directed explicit-state model checking in the validation of communication protocolsInternational Journal on Software Tools for Technology Transfer, 2004
- GRASP: a search algorithm for propositional satisfiabilityIEEE Transactions on Computers, 1999
- Red-black trees in a functional settingJournal of Functional Programming, 1999
- Symbolic execution and program testingCommunications of the ACM, 1976
- A note on two problems in connexion with graphsNumerische Mathematik, 1959