Rupak Majumdar and Koushik Sen

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2007-36

March 20, 2007

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-36.pdf

We present lazy expansion, a new algorithm for scalable test input generation using directed concolic execution. Lazy expansion is an instantiation of the counterexample-guided refinement paradigm from static software verification in the context of testing. Our algorithm works in two phases. It first explores, using concolic execution, an abstraction of the function under test by replacing each called function with an unconstrained input. Second, for each (possibly spurious) trace generated by this abstraction, it attempts to expand the trace to a concretely realizable execution by recursively expanding the called functions and finding concrete executions in the called functions that can be stitched together with the original trace to form a complete program execution. Thus, it reduces the burden of symbolic reasoning about interprocedural paths to reasoning about intraprocedural paths (in the exploration phase), together with a localized and constrained search through functions (in the concretization phase).

Lazy expansion is particularly effective in testing functions that make more-or-less independent calls to lower level library functions (that have already been unit tested), by only exploring relevant paths in the function under test. We have implemented our algorithm on top of the CUTE concolic execution tool for C and applied it to testing parser code in small compilers. In preliminary experiments, our tool, called LATEST, outperformed CUTE by an order of magnitude in terms of the time taken to generate inputs, and in contrast to CUTE, produced many syntactically valid input strings which exercised interesting paths through the compiler (rather than only the parser error handling code).

---

BibTeX citation:

@techreport{Majumdar:EECS-2007-36,
    Author= {Majumdar, Rupak and Sen, Koushik},
    Title= {LATEST : Lazy Dynamic Test Input Generation},
    Year= {2007},
    Month= {Mar},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-36.html},
    Number= {UCB/EECS-2007-36},
    Abstract= {  We present lazy expansion, a new algorithm for scalable test
  input generation using directed concolic execution.  Lazy expansion
  is an instantiation of the counterexample-guided refinement paradigm
  from static software verification in the context of testing.  Our
  algorithm works in two phases.  It first explores, using concolic
  execution, an abstraction of the function under test by replacing
  each called function with an unconstrained input.  Second, for each
  (possibly spurious) trace generated by this abstraction, it attempts
  to expand the trace to a concretely realizable execution by
  recursively expanding the called functions and finding concrete
  executions in the called functions that can be stitched together
  with the original trace to form a complete program execution.  Thus,
  it reduces the burden of symbolic reasoning about interprocedural
  paths to reasoning about intraprocedural paths (in the exploration
  phase), together with a localized and constrained search through
  functions (in the concretization phase).

  Lazy expansion is particularly effective in testing functions that
  make more-or-less independent calls to lower level library functions
  (that have already been unit tested), by only exploring relevant
  paths in the function under test.  We have implemented our algorithm
  on top of the CUTE concolic execution tool for C and applied it to
  testing parser code in small compilers.  In preliminary experiments,
  our tool, called LATEST, outperformed CUTE by an order of
  magnitude in terms of the time taken to generate inputs, and in
  contrast to CUTE, produced many syntactically valid input strings
  which exercised interesting paths through the compiler (rather than
  only the parser error handling code).},
}

EndNote citation:

%0 Report
%A Majumdar, Rupak 
%A Sen, Koushik 
%T LATEST : Lazy Dynamic Test Input Generation
%I EECS Department, University of California, Berkeley
%D 2007
%8 March 20
%@ UCB/EECS-2007-36
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-36.html
%F Majumdar:EECS-2007-36