Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

   

2008 Research Summary

Predictive Testing for Sequential and Multithreaded Programs

View Current Project Information

Koushik Sen and Pallavi Joshi

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 employ predictive testing to catch bugs related to memory-safety violations, integer overflows, and string-related vulnerabilities.

We also extend the idea of predictive testing to test multithreaded programs. As in the case for sequential programs, we execute the multithreaded program once for each existing test case. We use locksets, happens-before relation and dataflow analysis to predict if any of the assertions encountered along a test execution path could be violated for some closely related thread interleaving. The dataflow analysis that we perform is specific to the kind of assertions that we want to verify. But this specific analysis can be very easily instantiated from a generic algorithm that we have developed by plugging in only a few parameters.

[1]
"Predictive Testing: Amplifying the Effectiveness of Software Testing," ESEC/FSE, poster paper, 2007.