The Cross-Entropy based Testing

Large concurrent programs present a challenge for all testing approaches due to the sheer number of possible executions and difficulty to direct the scheduler to interesting (potentially buggy) executions. Exhaustive testing is clearly infeasible for even medium-size programs, since the number of possible threads-interleaving makes the state space of the program prohibitively large. Other testing techniques, which combine systematic exploration, program analysis techniques and/or heuristics for guiding a dynamic exploration, can fail to find rare faults in the code due to lack of space or time. 
 
In this talk, I will review the cross-entropy based testing approach of concurrent programs. The cross-entropy (CE) method is a widely used approach to estimating probabilities of rare events (Rubinstein); the CE-based testing approach uses the cross-entropy method for graph optimization problems to direct a dynamic search throw interesting and potentially buggy parts of the code via a goal function.

I will present implementations of the approach, including: performance (goal/heuristic) functions for finding rare faults of different classes of bugs, and experimental results of Java code with several up to hundreds of threads, in which the tools were able to find rare bugs successfully.

Karine Even Mendoza: currently a PhD student at King's College London, in the Software Modelling and Applied Logic group under the supervision of Dr Hana Chockler, worked in research at eBay, Netanya, Israel and at IBM Research Labs, Haifa, Israel for several years and obtained her M.Sc. in Computer Science from the Technion(2013) in the field of software verification and testing, software engineering and learning; the results of the M.Sc. thesis were presented at ISSTA 2013.