AccMon: Automatically Detecting Memory-related Bugsvia Program Counter-based Invariants∗Pin Zhou, Wei Liu, Long Fei†, Shan Lu, Feng Qin, Yuanyuan Zhou, Samuel Midkiff†and Josep TorrellasDepartment of Computer Science,University of Illinois at Urbana-Champaign{pinzhou,liuwei,shanlu,fengqin,yyzhou,torrellas}@cs.uiuc.edu†School of Electrical and Computer Engineering,Purdue University{lfei,smidkiff}@purdue.eduAbstractThis paper makes two contributions to architectural support forsoftware debugging. First, it proposes a novel statistics-based, on-the-fly bug detection method called PC-based invariant detection.The idea is based on the observation that, in most programs, a givenmemory location is typically accessed by only a few instructions.Therefore, by capturing the invariant of the set of PCs that nor-mally access a given variable, we can detect accesses by outlierinstructions, which are often caused by memory corruption, bufferoverflow, stack smashing or other memory-related bugs. Since thismethod is statistics-based, it can detect bugs that do not violate anyprogramming rules and that, therefore, are likely to be missed bymany existing tools. The second contribution is a novel architec-tural extension called the Check Look-aside Buffer (CLB). The CLBuses a Bloom filter to reduce monitoring overheads in the recently-proposed iWatcher architectural framework for software debugging.The CLB significantly reduces the overhead of PC-based invariantdebugging.We demonstrate a PC-based invariant detection tool called Ac-cMon that leverages architectural, run-time system and compilersupport. Our experimental results with seven buggy applicationsand a total of ten bugs, show that AccMon can detect all ten bugswith few false alarms (0 for five applications and 2-8 for two appli-cations) and with low overhead (0.24-2.88 times). Several existingtools evaluated, including Purify, CCured and value-based invariantdetection tools, fail to detect some of the bugs. In addition, Purify’soverhead is one order of magnitude higher than AccMon’s. Finally,we show that the CLB is very effective at reducing overhead.1. IntroductionSoftware bugs significantly affect system reliability and avail-ability, accounting for as many as 40% of computer system fail-ures [24]. According to NIST, software bugs cost the U.S. econ-omy an estimated $59.5 billion annually, or 0.6% of the GDP [27].Memory-related bugs are among the most prevalent and difficult tocatch of all software bugs, particularly in programs written in an un-safe language such as C/C++. In addition, they are often exploitedto launch security attacks [7].As micro-architectural innovations have significantly improvedperformance, interest has recently risen in the architecture commu-∗This work was supported in part by NSF under grants CCR-0325603,EIA-0072102, CHE-0121357, and EIA-0081307; by DARPA under grantF30602-01-C-0078; by an IBM SUR grant; and by additional gifts fromIBM and Intel.nity to use transistors to improve software robustness. For exam-ple, Prvulovic and Torrellas proposed ReEnact [31], which uses thestate buffering, rollback and re-execution features of Thread-LevelSpeculation (TLS) to detect data races on the fly. Xu et al designedthe “flight data recorder” [39], which enables off-line deterministicreplay and can be used for postmortem analysis of a bug. Our pre-vious work on iWatcher [40] provides a convenient and efficient ar-chitectural framework for dynamic monitoring. While recent workprovides a good foundation, architectural support for software de-bugging is still far from providing a complete solution. This papertakes another step toward the goal of improving software robust-ness.Many methods have been proposed to detect bugs dynamicallyduring execution. These methods can be classified into two cat-egories: the programming-rule-based approach and the statistics-rule-based approach. Methods in both categories check for viola-tions of certain rules at run time, but they focus on different typesof rules. The programming-rule-based approach focuses on rulesthat should be followed when programming in a specific languagesuch as C/C++. “An array pointer cannot move out-of-bounds” is anexample of these rules. Much work has been conducted on this ap-proach, including Purify [15], CCured [6, 28], SafeC [1] and Jonesand Kelly’s tool [19].The statistics-rule-based approach is a newly explored directionthat extracts rules (e.g., invariants) statistically from multiple suc-cessful executions (e.g., in-house regression tests) or multiple peri-ods of a single long-running execution, and then uses these rules tocheck for violations in a later execution (or later in the same long-running execution). This approach is promising because it can catchbugs that may not violate any programming rules. Many statistics-based rules such as value-based invariants (i.e., a variable’s valuealways falls in a certain range during normal runs) are related toapplications semantics. Such information is difficult to infer fromthe code, and is too tedious to be documented or annotated by pro-grammers.Only a few studies have been conducted on the statistics-rule-based approach, and almost all are software-only solutions. Liblit etal [23] uses statistical analysis to find the difference between abnor-mal and normal runs for the purpose of providing more informationfor postmortem bug analysis. DAIKON [11, 12] and DIDUCE [14]focus on detecting bugs on the fly by automatically extracting in-variants and detecting violations during execution. Both DAIKONand DIDUCE consider only value-based invariants, and thereforecan miss bugs that do not violate these invariants.Novel architectural support would provide several benefits forstatistics-rule-based bug detection over software-only solutions: (1)Efficiency: Architectural support can significantly lower the over-head of dynamic monitoring because it does not need extensivecode instrumentation. Note also that such instrumentation can in-terfere with compiler optimizations. Moreover, it is possible to useextra hardware to speed up certain operations. Both iWatcher andAccMon are examples that demonstrate this benefit. (2) Accuracy:Architectural support can avoid pointer aliasing problems and ac-curately capture all desired accesses to monitored memory objects.(3) Portability: Architectural support can be language-independent,cross-module and easy to use with low-level system code such asthe operating