TY - GEN
T1 - Statically-directed dynamic automated test generation
AU - Babić, Domagoj
AU - Martignoni, Lorenzo
AU - McCamant, Stephen
AU - Song, Dawn
PY - 2011
Y1 - 2011
N2 - 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.
AB - 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.
KW - automated testing
KW - dynamic analysis
KW - prioritization
KW - static analysis
UR - http://www.scopus.com/inward/record.url?scp=80051934403&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=80051934403&partnerID=8YFLogxK
U2 - 10.1145/2001420.2001423
DO - 10.1145/2001420.2001423
M3 - Conference contribution
AN - SCOPUS:80051934403
SN - 9781450305624
T3 - 2011 International Symposium on Software Testing and Analysis, ISSTA 2011 - Proceedings
SP - 12
EP - 22
BT - 2011 International Symposium on Software Testing and Analysis, ISSTA 2011 - Proceedings
T2 - 20th International Symposium on Software Testing and Analysis, ISSTA 2011
Y2 - 17 July 2011 through 21 July 2011
ER -