Predicting Concurrency Errors at Runtime using Sliced Causality

Chen, Feng; Rosu, Grigore

Permalink

https://hdl.handle.net/2142/11142 Copy

Description

Title

Predicting Concurrency Errors at Runtime using Sliced Causality

Author(s)

• Chen, Feng
• Rosu, Grigore

Issue Date

2005-11

Keyword(s)

• runtime analysis
• computer science

Abstract

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.

Type of Resource

text

Permalink

http://hdl.handle.net/2142/11142

Copyright and License Information

You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections