Statically-Directed Dynamic Automated Test Generation
[PDF] [PS] [PS.BZ2] [VIEW] Note: This version has a slightly extended related work section (a few extra references).
Bibtex:
@inproceedings{babic11sandwich,
author = {Domagoj Babi\'c and Lorenzo Martignoni and
Stephen McCamant and Dawn Song},
title = {{Statically-Directed Dynamic Automated Test Generation}},
booktitle = {ISSTA'11: Proceedings of the International Symposium
on Software Testing and Analysis},
year = {2011},
location = {Toronto, ON, Canada},
publisher = {ACM Press},
pages = {12--22},
address = {New York, NY, USA},
}
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.