Finding Rare Numerical Stability Errors in Concurrent Computations

Stability of a numerical algorithm is an important factor in its analysis, since an error exceeding the bound can lead to disastrous results: for example, the Patriot missile failure in 1991 occurred due to rounding errors and explosion of the Ariane 5 rocket in 1996 was a result of an overflow error. Introduction of concurrency to numerical algorithms results in a significant increase in the number of possible computations of the same result and can lead to instability of previously stable algorithms, since rounding combined with the possibility of different interleaving of threads can result in a larger error than expected for some interleaving. Such errors can be very rare, since the particular combination of rounding can occur in only a very small percentage of interleaving, making the detection of such errors an especially challenging task.

In this talk, I will present a framework for cross-entropy based testing of concurrent numerical programs. The framework combines ideas from cross-entropy based testing, together with abstractions that make these techniques effective for programs with large number of threads. We developed a new tool ACE that implemented our approach.

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.