PathExpander: architectural support for increasing the path coverage of dynamic bug detection

Shan Lu, Pin Zhou, Wei Liu, Yuanyuan Zhou, Josep Torrellas

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Dynamic software bug detection tools are commonly used because they leverage run-time information. However, they suffer from a fundamental limitation, 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 hardware extension. First, we propose PathExpander, a novel design that dynamically increases the code path coverage of dynamic bug detection tools with no programmer involvement. As a program executes, PathExpander selectively executes non-taken paths in a sandbox without side effects. This enables dynamic bug detection tools to find bugs that are present in these non-taken paths and would otherwise not be detected. Second, we propose a simple hardware extension to control the huge overhead in its pure software implementation to a moderate level. To further minimize overhead, PathExpander provides an optimization option to execute non-taken paths on idle cores in chip multi-processor architectures that support speculative execution. To evaluate PathExpander, we use three dynamic bug detection methods: dynamic software-only checker (CCured), dynamic hardware-assisted checker (iWatcher) and assertions; and conduct side-by-side comparison with PathExpander's counterpart software implementation. Our experiments with seven buggy programs using general inputs that do not expose the tested bugs show that PathExpander is able to help these tools detect 21 (out of 38) tested bugs that are otherwise missed. This is because PathExpander increases the code coverage of each test case from 40% to 65% on average, based on the branch coverage metric. When applications are tested with multiple inputs, the cumulative coverage also significantly improves by 19%. We also show that PathExpander introduces modest false positives (4 on average) and overhead (less than 9.9%). The 3-4 orders of magnitude lower overhead compared with pure-software implementation further justifies the hardware design in PathExpander.

Original languageEnglish (US)
Title of host publicationProceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, MICRO-39
Number of pages12
StatePublished - 2006
Event39th Annual IEEE/ACM International Symposium on Microarchitecture, MICRO-39 - Orlando, FL, United States
Duration: Dec 9 2006Dec 13 2006

Publication series

NameProceedings of the Annual International Symposium on Microarchitecture, MICRO
ISSN (Print)1072-4451


Other39th Annual IEEE/ACM International Symposium on Microarchitecture, MICRO-39
Country/TerritoryUnited States
CityOrlando, FL

ASJC Scopus subject areas

  • General Engineering


Dive into the research topics of 'PathExpander: architectural support for increasing the path coverage of dynamic bug detection'. Together they form a unique fingerprint.

Cite this