University of Illinois Urbana-Champaign

Predictive Runtime Analysis of Multithreaded Programs

Chen, Feng; Rosu, Grigore

Content Files
Predictive Runtime Analysis of Multithreaded Programs.pdf

Permalink

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

Description

Title
Predictive Runtime Analysis of Multithreaded Programs
Author(s)
  • Chen, Feng
  • Rosu, Grigore
Issue Date
2005-07
Keyword(s)
computer science
Date of Ingest
2009-04-20T18:27:24Z
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
Genre of Resource
Technical Report
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

Research and Tech Reports - Computer Science PRIMARY