University of Illinois Urbana-Champaign

SpanCoverage: Architectural Support for Increasing the Path Coverage of Dynamic Bug Detection

Lu, Shan; Zhou, Pin; Liu, Wei; Zhou, YuanYuan; Torrellas, Josep

Content Files
SpanCoverage Architectural Support for Increasing the Path Coverage of Dynamic Bug Detection.pdf

Permalink

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

Description

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
Issue Date
2005-07
Keyword(s)
  • dynamic bug detection
  • computer science
Date of Ingest
2009-04-20T15:42:32Z
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.
Type of Resource
text
Genre of Resource
Technical Report
Permalink
http://hdl.handle.net/2142/11083
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