Effective Predictive Runtime Analysis Using Sliced Causality and Atomicity

From FSL
Jump to: navigation, search

Technical Report

Effective Predictive Runtime Analysis Using Sliced Causality and Atomicity
Feng Chen, Traian Florin Serbanuta and Grigore Rosu
Technical report UIUCDCS-R-2007-2905, October 2007
Abstract. Predictive runtime analysis has been proposed to improve the effectiveness of concurrent program analysis and testing. By observing one execution trace of the running system, predictive runtime analysis extracts a causality relation among runtime events, which is then used as an abstract model of the program and checked against desired properties. This way, one can predict concurrency errors without actually hitting them and without re-executing the program. The quality of the extracted causality relation directly determines the effectiveness of predictive runtime analysis. This paper presents an efficient and sound approach to compute sliced causality and sliced atomicity. These significantly improve upon existing causalities: irrelevant causal relationships are removed using an apriori static analysis process based on control and data dependence, and on property relevance and atomicity analysis. The algorithms presented in this paper have been implemented and extensively evaluated. The results show that the proposed technique is effective and sound: we found the previously known concurrency bugs as well as some unknown errors in popular systems, like the Tomcat webserver and the Apache FTP server, without any false alarms.

Personal tools