Statically-directed dynamic automated test generation

Domagoj Babić, Lorenzo Martignoni, Stephen McCamant, Dawn Song

Research output: Chapter in Book/Report/Conference proceedingConference contribution

67 Scopus citations

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.

Original languageEnglish (US)
Title of host publication2011 International Symposium on Software Testing and Analysis, ISSTA 2011 - Proceedings
Pages12-22
Number of pages11
DOIs
StatePublished - Aug 26 2011
Event20th International Symposium on Software Testing and Analysis, ISSTA 2011 - Toronto, ON, Canada
Duration: Jul 17 2011Jul 21 2011

Publication series

Name2011 International Symposium on Software Testing and Analysis, ISSTA 2011 - Proceedings

Other

Other20th International Symposium on Software Testing and Analysis, ISSTA 2011
CountryCanada
CityToronto, ON
Period7/17/117/21/11

Keywords

  • automated testing
  • dynamic analysis
  • prioritization
  • static analysis

Fingerprint Dive into the research topics of 'Statically-directed dynamic automated test generation'. Together they form a unique fingerprint.

  • Cite this

    Babić, D., Martignoni, L., McCamant, S., & Song, D. (2011). Statically-directed dynamic automated test generation. In 2011 International Symposium on Software Testing and Analysis, ISSTA 2011 - Proceedings (pp. 12-22). (2011 International Symposium on Software Testing and Analysis, ISSTA 2011 - Proceedings). https://doi.org/10.1145/2001420.2001423