Jacob Burnim and Koushik Sen

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2008-123

September 19, 2008

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-123.pdf

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 \tname{}, 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.

---

BibTeX citation:

@techreport{Burnim:EECS-2008-123,
    Author= {Burnim, Jacob and Sen, Koushik},
    Title= {Heuristics for Scalable Dynamic Test Generation},
    Year= {2008},
    Month= {Sep},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-123.html},
    Number= {UCB/EECS-2008-123},
    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 \tname{}, 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.},
}

EndNote citation:

%0 Report
%A Burnim, Jacob 
%A Sen, Koushik 
%T Heuristics for Scalable Dynamic Test Generation
%I EECS Department, University of California, Berkeley
%D 2008
%8 September 19
%@ UCB/EECS-2008-123
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-123.html
%F Burnim:EECS-2008-123