Citation
Jacob Burnim, Koushik Sen. "Heuristics for Scalable Dynamic Test Generation". Automated Software Engineering, 2008. ASE 2008. 23rd IEEE/ACM International Conference on, 443-446, 15, September, 2008.

Abstract
Recently there has been great success in using symbolic execution to automatically generate test inputs for small software systems. A primary challenge in scaling such approaches to larger programs is the combinatorial explosion of the path space. It is likely that sophisticated strategies for searching this path space are needed to generate inputs that effectively test large programs (by, e.g., achieving significant branch coverage). We present several such heuristic search strategies, including a novel strategy guided by the control flow graph of the program under test. We have implemented these strategies in CREST, our open source concolic testing tool for C, and evaluated them on two widely-used software tools, grep 2.2 (15K lines of code) and Vim 5.7 (150K lines). On these benchmarks, the presented heuristics achieve significantly greater branch coverage on the same testing budget than concolic testing with a traditional depth-first search strategy.

Electronic downloads

• http://dx.doi.org/10.1109/ASE.2008.69
• http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-123.html. (EECS Technical Report Version)

• HTML

  Jacob Burnim, Koushik Sen. <a
  href="http://chess.eecs.berkeley.edu/pubs/507.html"
  >Heuristics for Scalable Dynamic Test
  Generation</a>, Automated Software Engineering, 2008.
  ASE 2008. 23rd IEEE/ACM International Conference on,
  443-446, 15, September, 2008.

• Plain text

  Jacob Burnim, Koushik Sen. "Heuristics for Scalable
  Dynamic Test Generation". Automated Software
  Engineering, 2008. ASE 2008. 23rd IEEE/ACM International
  Conference on, 443-446, 15, September, 2008.

• BibTeX

  @inproceedings{BurnimSen08_HeuristicsForScalableDynamicTestGeneration,
      author = {Jacob Burnim and Koushik Sen},
      title = {Heuristics for Scalable Dynamic Test Generation},
      booktitle = {Automated Software Engineering, 2008. ASE 2008.
                23rd IEEE/ACM International Conference on},
      pages = {443-446},
      day = {15},
      month = {September},
      year = {2008},
      abstract = {Recently there has been great success in using
                symbolic execution to automatically generate test
                inputs for small software systems. A primary
                challenge in scaling such approaches to larger
                programs is the combinatorial explosion of the
                path space. It is likely that sophisticated
                strategies for searching this path space are
                needed to generate inputs that effectively test
                large programs (by, e.g., achieving significant
                branch coverage). We present several such
                heuristic search strategies, including a novel
                strategy guided by the control flow graph of the
                program under test. We have implemented these
                strategies in CREST, our open source concolic
                testing tool for C, and evaluated them on two
                widely-used software tools, grep 2.2 (15K lines of
                code) and Vim 5.7 (150K lines). On these
                benchmarks, the presented heuristics achieve
                significantly greater branch coverage on the same
                testing budget than concolic testing with a
                traditional depth-first search strategy. },
      URL = {http://chess.eecs.berkeley.edu/pubs/507.html}
  }
  

Posted by Christopher Brooks on 18 Nov 2008.
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.