Files in this item



application/pdfPredicting Conc ... using Sliced Causality.pdf (268kB)
(no description provided)PDF


Title:Predicting Concurrency Errors at Runtime using Sliced Causality
Author(s):Chen, Feng; Rosu, Grigore
Subject(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.
Issue Date:2005-11
Genre:Technical Report
Other Identifier(s):UIUCDCS-R-2005-2660
Rights 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).
Date Available in IDEALS:2009-04-20

This item appears in the following Collection(s)

Item Statistics