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

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