Non-race concurrency bug detection through order-sensitive critical sections
Abstract
This paper introduces a new heuristic condition for non-race concurrency bugs, named order-sensitive critical sections, and proposes a run-time bug detection scheme based on the condition. The order-sensitive critical sections are defined as a pair of critical sections that can lead to non-deterministic shared memory state depending on the order in which they execute. In a sense, the order-sensitive critical sections can be seen as extending the intuition in using data races as a potential bug condition to capture non-race bugs. Experiments show that the proposed scheme provides a good coverage for multiple types of non-race bugs, with a small number of false positives. For example, the scheme detected all 9 real-world non-race bugs that were tested as well as over 90% of injected non-race bugs. Additionally, this paper presents an efficient hardware architecture that supports the proposed scheme with minor hardware changes and a small amount of additional state - a 9-KB buffer per core and a 1-bit tag per data cache block. The hardware-based scheme could still detect all 9 real-world bugs that were tested and more than 84% of the injected non-race bugs. Moreover, the hardware supported scheme has a negligible impact on performance, with a 0.23% slowdown on average.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jun 23, 2013
- Source ID
- 10.1145/2508148.2485978
Entities
People
- Erik Halberg
- G. Edward Suh
- Ruirui Huang
Organizations
- Air Force Office of Scientific Research
- Cornell University
- Division of Computer and Network Systems
- Division of Computing and Communication Foundations