Files in this item



application/pdfSpanCoverage Ar ... Dynamic Bug Detection.pdf (452kB)
(no description provided)PDF


Title:SpanCoverage: Architectural Support for Increasing the Path Coverage of Dynamic Bug Detection
Author(s):Lu, Shan; Zhou, Pin; Liu, Wei; Zhou, YuanYuan; Torrellas, Josep
Subject(s):dynamic bug detection
computer science
Abstract:Dynamic tools for software bug detection such as Purify are commonly used because they leverage run-time information. However, they suffer from a fundamental limitation, namely the Path Coverage Problem: they detect bugs only in taken paths but not in non-taken paths. In other words, they require bugs to be exposed in the monitored execution. This paper makes one of the first attempts to address this fundamental problem with a simple architecture extension. We propose SpanCoverage, a novel design that dynamically increases the path coverage of dynamic bug detection tools with no involvement from programmers. As a program executes, SpanCoverage also selectively executes non-taken paths in a hardware sandbox without side effects. This enables dynamic bug detection tools to find bugs in these paths that would otherwise not be detected. To minimize overhead, SpanCoverage provides an optimization option to leverage thread level speculation (TLS) with small modifications to execute selected non-taken paths on idle processors in a chip multi-processor (CMP) architecture. We evaluate SpanCoverage using three dynamic bug detection methods: assertions, software-only checkers (CCured), and hardware-assisted checkers (iWatcher). Our experiments with nine buggy programs using inputs that do not expose the tested bugs show that SpanCoverage is able to help these tools find bugs in seven out of the nine tested bugs that are otherwise not detected. This is because SpanCoverage increases the branch coverage from 36% to 60% on average. The cumulative coverage also improves significantly by 11--58%, even when applications are tested with multiple input sets. We also show that SpanCoverage has a modest overhead (less than 9.9% for three open source applications, and three bug-free SPEC2000 benchmarks with the CMP optimization) and introduces only a few (3 on average) false positives.
Issue Date:2005-07
Genre:Technical Report
Other Identifier(s):UIUCDCS-R-2005-2618
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