Predictive Runtime Analysis of Multithreaded Programs

Chen, Feng; Rosu, Grigore

Permalink

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

Description

Title

Predictive Runtime Analysis of Multithreaded Programs

Author(s)

• Chen, Feng
• Rosu, Grigore

Issue Date

2005-07

Keyword(s)

computer science

Abstract

We present a technique to predict property violations in multi-threaded programs from successful executions. An appealing aspect of our technique is that it is entirely automatic; another is that no special simulation or modeling infrastructure is needed. All the user needs to do is to provide the multi-threaded system and the property to check. An observer is automatically generated from the property and an instrumentation procedure based on vector clocks automatically modifies the program to emit relevant events to the observer. By making intensive use of a dynamically computed generalized ``happens-before'' causal partial order that is refined with control-flow and data-flow dependency information obtained apriory via static analysis of the program, the observer is able to build from one concrete execution trace a set of abstract execution traces. Those abstract execution traces correspond to concrete executions that have not necessarily happened but ``were close to happen'' and could indeed happen in another execution of the system under a different thread scheduling. The predictive aspect of our technique comes from the fact that some of those executions may violate the property. If that is the case, a counter-example is provided. The technique has been implemented in the context of Java and has been shown to be useful via a series of experiments.

Type of Resource

text

Permalink

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

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