Predicting Concurrency Errors at Runtime using Sliced Causality
- Predicting Concurrency Errors at Runtime using Sliced Causality
- Feng Chen and Grigore Rosu
- Technical report UIUCDCS-R-2006-2965, 2006.
- Abstract. A runtime analysis technique is presented, which can predict concurrency errors in multithreaded systems by observing potentially non-erroneous executions. It builds upon a novel causal partial order, sliced causality, that weakens the classic but strict ``happens-before by using both static information about the program, such as control- and data-flow dependence, and dynamic synchronization information, such as lock-sets. A vector clock algorithm is introduced to automatically extract a sliced causality from any execution. A memory-efficient procedure then checks all causally consistent potential runs against properties given as monitors. If any of these runs violates a property, it is returned as a ``predicted counter-example. This runtime analysis technique is sound (no false alarms) but not complete (says nothing about code that was not covered). A prototype called jPredictor has been implemented and evaluated on several Java applications with promising results.