Team for Research in
Ubiquitous Secure Technology

Citation
Domagoj Babic, Lorenzo Martignoni, Stephen McCamant, Dawn Song. "Statically-Directed Dynamic Automated Test Generation". Proceedings of the 2011 International Symposium on Software Testing and Analysis (ISSTA11), 2011.

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.

Electronic downloads

• http://dl.acm.org/citation.cfm?doid=2001420.2001423

• HTML

  Domagoj Babic, Lorenzo Martignoni, Stephen McCamant, Dawn
  Song. <a
  href="http://www.truststc.org/pubs/857.html"
  >Statically-Directed Dynamic Automated Test
  Generation</a>, Proceedings of the 2011 International
  Symposium on Software Testing and Analysis  (ISSTA11), 2011.

• Plain text

  Domagoj Babic, Lorenzo Martignoni, Stephen McCamant, Dawn
  Song. "Statically-Directed Dynamic Automated Test
  Generation". Proceedings of the 2011 International
  Symposium on Software Testing and Analysis  (ISSTA11), 2011.

• BibTeX

  @inproceedings{BabicMartignoniMcCamantSong11_StaticallyDirectedDynamicAutomatedTestGeneration,
      author = {Domagoj Babic and Lorenzo Martignoni and Stephen
                McCamant and Dawn Song},
      title = {Statically-Directed Dynamic Automated Test
                Generation},
      booktitle = {Proceedings of the 2011 International Symposium on
                Software Testing and Analysis  (ISSTA11)},
      year = {2011},
      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.},
      URL = {http://www.truststc.org/pubs/857.html}
  }
  

Posted by Mary Stewart on 4 Apr 2012.
For additional information, see the Publications FAQ or contact webmaster at www truststc org.