Predicting Concurrency Errors at Runtime using Sliced Causality

From FSL
Jump to: navigation, search

The interested reader can find our latest news and more details about this work in the webpages of Predictive Runtime Analysis and jPredictor.

Technical report

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.

Personal tools