Paper Info
Title
Statically-directed dynamic automated test generation
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.
Year
DOI
Venue
2011
10.1145/2001420.2001423
ISSTA
Keywords
Field
DocType
binary code,test input,dynamic analysis,static warning,automated test generation tool,computed vpa,statically-directed dynamic automated test,dynamic automated test generation,seed test,vpa edge,static analysis,shortest path,control flow
Small number,Suite,Computer science,Static analysis,Automaton,Binary code,Algorithm,Real-time computing,Pushdown automaton,True positive rate,Binary number
Conference
Citations 
PageRank 
References 
51
1.90
38
Authors
4
Name
Order
Citations
PageRank
Domagoj Babić11457.11
Lorenzo Martignoni257629.92
Stephen McCamant3163874.34
Dawn Song47084442.36