Predicting Concurrency Errors at Runtime using Sliced Causality

A runtime analysis technique is presented, which can predict errors in multi-threaded systems by examining event traces generated by executions of these systems even when they are successful. The technique is based on a novel partial order relation on relevant events, called sliced causality, which loosens the obvious but strict ``happens-before'' relation by considering static structural information about the multi-threaded program, such as control-flow and data-flow dependence, and dynamic synchronization information, such as lock-sets. A vector clock based algorithm to encode the sliced causality is given, together with a procedure for generating all potential runs that are consistent with this partial order in a memory effective way. Then violations of properties can be ``predicted'' by running the corresponding monitor against potential runs that are consistent with the observed execution, i.e., permutations of (abstract) events that do not violate the sliced causal partial order. The monitors can be manually implemented or automatically synthesized from the desired properties, which can be given in any formalism that allows monitor synthesis algorithms. Our runtime analysis technique is sound, in the sense that it reports no false alarms. As expected, it is not complete; indeed, it cannot say anything about code that was not reached during the observed execution. A prototype system, called jPredictor, has been implemented and evaluated on several Java applications with promising results