Predictive Testing: Amplifying the Effectiveness of Software Testing

Pallavi Joshi, Koushik Sen and Mark Shlimovich

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2007-35
March 20, 2007

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

Testing with manually generated test cases often results in poor coverage and fails to discover many corner case bugs and security vulnerabilities. Automated test generation techniques based on static or symbolic analysis usually do not scale beyond small program units. We propose predictive testing, a new method for amplifying the effectiveness of existing test cases using symbolic analysis. We assume that a software system has an associated test suite consisting of a set of test inputs and a set of program invariants, in the form of a set of assert statements that the software must satisfy when executed on those inputs. Predictive testing uses a combination of concrete and symbolic execution, similar to concolic execution, on the provided test inputs to discover if any of the assertions encountered along a test execution path could be violated for some closely related inputs. We extend predictive testing to catch bugs related to memory-safety violations, integer overflows, and string-related vulnerabilities.

Furthermore, we propose a novel technique that leverages the results of unit testing to hoist assertions located deep inside the body of a unit function to the beginning of the unit function. This enables predictive testing to encounter assertions more often in test executions and thereby significantly amplifies the effectiveness of testing. We have implemented predictive testing in a tool called PRETEX and our initial experiments on some open-source programs show that predictive testing can effectively discover bugs that are missed by normal testing. PRETEX uses symbolic analysis and automated theorem proving techniques internally, but all of this complexity remains hidden from the user behind a testing usage model. For this reason, we expect that PRETEX will be easy to integrate into existing software engineering processes and will be usable even by unsophisticated developers.


BibTeX citation:

@techreport{Joshi:EECS-2007-35,
    Author = {Joshi, Pallavi and Sen, Koushik and Shlimovich, Mark},
    Title = {Predictive Testing: Amplifying the Effectiveness of  Software Testing},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2007},
    Month = {Mar},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-35.html},
    Number = {UCB/EECS-2007-35},
    Abstract = {  Testing with manually generated test cases often results in poor
  coverage and fails to discover many corner case bugs and security
  vulnerabilities.  Automated test generation techniques based on
  static or symbolic analysis usually do not scale beyond small
  program units.  We propose predictive testing, a new method for
  amplifying the effectiveness of existing test cases using symbolic
  analysis.  We assume that a software system has an associated test
  suite consisting of a set of test inputs and a set of program
  invariants, in the form of a set of assert statements that the
  software must satisfy when executed on those inputs.  Predictive
  testing uses a combination of concrete and symbolic execution,
  similar to concolic execution, on the provided test inputs to
  discover if any of the assertions encountered along a test execution
  path could be violated for some closely related inputs.  We extend
  predictive testing to catch bugs related to memory-safety
  violations, integer overflows, and string-related vulnerabilities.

  Furthermore, we propose a novel technique that leverages the results
  of unit testing to hoist assertions located deep inside the body of
  a unit function to the beginning of the unit function.  This enables
  predictive testing to encounter assertions more often in test
  executions and thereby significantly amplifies the effectiveness of
  testing.  We have implemented predictive testing in a tool called
  PRETEX and our initial experiments on some open-source programs show
  that predictive testing can effectively discover bugs that are
  missed by normal testing.  PRETEX uses symbolic analysis and
  automated theorem proving techniques internally, but all of this
  complexity remains hidden from the user behind a testing usage
  model.  For this reason, we expect that PRETEX will be easy to
  integrate into existing software engineering processes and will be
  usable even by unsophisticated developers.}
}

EndNote citation:

%0 Report
%A Joshi, Pallavi
%A Sen, Koushik
%A Shlimovich, Mark
%T Predictive Testing: Amplifying the Effectiveness of  Software Testing
%I EECS Department, University of California, Berkeley
%D 2007
%8 March 20
%@ UCB/EECS-2007-35
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-35.html
%F Joshi:EECS-2007-35