More Web Proxy on the site http://driver.im/

Article

AccMon: Automatically Detecting Memory-Related Bugs via Program Counter-Based Invariants

Authors:

Samuel Midkiff,

Josep TorrellasAuthors Info & Claims

MICRO 37: Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture

Pages 269 - 280

https://doi.org/10.1109/MICRO.2004.3

Published: 04 December 2004 Publication History

Abstract

This paper makes two contributions to architectural support for software debugging. First, it proposes a novel statistics-based, on-the-fly bug detectionmethod called PC-based invariant detection. The idea is based on the observation that, in most programs, a given memory location is typically accessed by only a few instructions. Therefore, by capturing the invariant of the set of PCs that normally access a given variable, we can detect accesses by outlier instructions, which are often caused by memory corruption, buffer overflow, stack smashing or other memory-related bugs. Since this method is statistics-based, it can detect bugs that do not violate any programming rules and that, therefore, are likely to be missed by many existing tools. The second contribution is a novel architectural extension called the Check Look-aside Buffer (CLB). The CLB uses 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 invariant debugging. We demonstrate a PC-based invariant detection tool called AccMon that leverages architectural, run-time system and compiler support. Our experimental results with seven buggy applications and a total of ten bugs, show that AccMon can detect all ten bugs with few false alarms (0 for five applications and 2-8 for two applications) and with low overhead (0.24-2.88 times). Several existing tools evaluated, including Purify, CCured and value-based invariant detection tools, fail to detect some of the bugs. In addition, Purify's overhead is one order of magnitude higher than AccMon's. Finally, we show that the CLB is very effective at reducing overhead.

References

[1]

{1} T. M. Austin, S. E. Breach, and G. S. Sohi. Efficient detection of all pointer and array access errors. In Proceedings of the ACM SIGPLAN 1994 Conference on Programming Language Design and Implementation, pages 290-301, 1994.

Digital Library

[2]

{2} D. A. Barrett and B. G. Zorn. Using lifetime predictors to improve memory allocation performance. In SIGPLAN Conference on Programming Language Design and Implementation, pages 187-196, 1993.

Digital Library

[3]

{3} B. H. Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7):422-426, 1970.

Digital Library

[4]

{4} B. Calder, K. Chandra, S. John, and T. Austin. Cache-conscious data placement. In Proceedings of the Eighth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-VIII), 1998.

Digital Library

[5]

{5} A. Chou, J. Yang, B. Chelf, S. Hallem, and D. R. Engler. An empirical study of operating system errors. In Symposium on Operating Systems Principles, pages 73-88, 2001.

Digital Library

[6]

{6} J. Condit, M. Harren, S. McPeak, G. C. Necula, and W. Weimer. CCured in the real world. In Proceedings of the ACM SIGPLAN 2003 Conference on Programming Language Design and Implementation, pages 232-244, 2003.

Digital Library

[7]

{7} C. Cowan, C. Pu, D. Maier, J. Walpole, P. Bakke, S. Beattie, A. Grier, P. Wagle, Q. Zhang, and H. Hinton. StackGuard: Automatic adaptive detection and prevention of buffer-overflow attacks. In Proceedings of the 7th USENIX Security Conference, pages 63-78, San Antonio, Texas, Jan 1998.

Digital Library

[8]

{8} J. Dean, J. E. Hicks, C. A. Waldspurger, W. E. Weihl, and G. Z. Chrysos. Profileme: Hardware support for instruction-level profiling on out-of-order processors. In International Symposium on Microarchitecture, pages 292-302, 1997.

Digital Library

[9]

{9} D. Engler, B. Chelf, A. Chou, and S. Hallem. Checking system rules using system-specific, programmer-written compiler extensions. In the Fourth Symposium on Operating Systems Design and Implementation (OSDI), Oct 2000.

Digital Library

[10]

{10} D. Engler, D. Y. Chen, and A. Chou. Bugs as inconsistent behavior: A general approach to inferring errors in systems code. In Proceedings of the 18th ACM Symposium on Operating Systems Principles, pages 57-72. ACM Press, 2001.

Digital Library

[11]

{11} M. D. Ernst, J. Cockrell, W. G. Griswold, and D. Notkin. Dynamically discovering likely program invariants to support program evolution. In International Conference on Software Engineering, 1999.

Digital Library

[12]

{12} M. D. Ernst, A. Czeisler, W. G. Griswold, and D. Notkin. Quickly detecting relevant program invariants. In International Conference on Software Engineering, 2000.

Digital Library

[13]

{13} C. Flanagan, K. Leino, M. Lillibridge, C. Nelson, J. Saxe, and R. Stata. Extended static checking for java. In Proceedings of SIGPLAN 2002 Conference on Programming Language Design and Implementation (PLDI), 2002.

Digital Library

[14]

{14} S. Hangal and M. S. Lam. Tracking down software bugs using automatic anomaly detection. In Proceedings of the International Conference on Software Engineering, May 2002.

Digital Library

[15]

{15} R. Hastings and B. Joyce. Purify: Fast detection of memory leaks and access errors. In Proceedings of the USENIX Winter Technical Conference, 1992.

[16]

{16} J. K. Hollingsworth, B. P. Miller, and J. Cargille. Dynamic program instrumentation for scalable performance tools. In Scalable High Performance Computing Conference, 1994.

[17]

{17} Intel Co. The IA-32 intel architecture software developer's manual, volume 2: Instruction set reference. Intel.

[18]

{18} M. S. Johnson. Some requirements for architectural support of software debugging. In Proceedings of the first International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-I), 1982.

Digital Library

[19]

{19} R. W. M. Jones and P. H. J. Kelly. Backwards-compatible bounds checking for arrays and pointers in c programs. In Automated and Algorithmic Debugging, 1997.

[20]

{20} A. R. Lebeck and D. A. Wood. Cache profiling and the SPEC benchmarks: A case study. IEEE Computer, 27(10):15-26, 1994.

Digital Library

[21]

{21} S.-I. Lee, T. A. Johnson, and R. Eigenmann. Cetus - an extensible compiler infrastructure for source-to-source transformation. In Proceedings of the 16th Annual Workshop on Languages and Compilers for Parallel Computing (LCPC '2003), 2003.

[22]

{22} Z. Li, S. Lu, S. Myagmar, and Y. Zhou. CP-Miner: A Tool for Finding Copy-paste and Related Bugs in Operating System Code. In Proceedings of the Sixth Symposium on Operating System Design and Implementation, 2004.

Digital Library

[23]

{23} B. Liblit, A. Aiken, A. X. Zheng, and M. I. Jordan. Bug isolation via remote program sampling. In Proceedings of SIGPLAN 2003 Conference on Programming Language Design and Implementation (PLDI), 2003.

Digital Library

[24]

{24} E. Marcus and H. Stern. Blueprints for high availablity. John Willey and Sons, 2000.

Digital Library

[25]

{25} A. Moshovos, G. Memik, B. Falsafi, and A. Choudhary. Jetty: Filtering snoops for reduced energy consumption in SMP servers. In Proceedings of the Seventh International Symposium on High Performance Computer Architecture (HPCA- 7), 2001.

Digital Library

[26]

{26} M. Musuvathi, D. Park, A. Chou, D. R. Engler, and D. L. Dill. CMC: A pragmatic approach to model checking real code. In Proceedings of the Fifth Symposium on Operating Systems Design and Implementation, Dec. 2002.

Digital Library

[27]

{27} National Institute of Standards and Technlogy (NIST), Department of Commerce. Software errors cost U.S. economy $59.5 billion annually. NIST News Release 2002-10, 2002.

[28]

{28} G. C. Necula, S. McPeak, and W. Weimer. CCured: type-safe retrofitting of legacy code. In Proceedings of the 29th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), 2002.

Digital Library

[29]

{29} H. Patil and C. Fischer. Low-cost, concurrent checking of pointer and array accesses in C programs. Software-Practice & Experience, 27(1), 1997.

Digital Library

[30]

{30} J.-K. Peir, S.-C. Lai, and S.-L. Lu. Bloom filtering cache misses for accurate data speculation and prefetching. In Proceedings of the 16th Annual ACM International Conference on Supercomputing (ICS), 2002.

Digital Library

[31]

{31} M. Prvulovic and J. Torrellas. ReEnact: Using Thread-Level Speculation Mechanisms to Debug Data Races in Multithreaded Codes. In Proceedings of the 30th Annual International Symposium on Computer Architecture (ISCA), June 2003.

Digital Library

[32]

{32} S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. Eraser: A dynamic data race detector for multithreaded programs. ACM Transactions on Computer Systems, 15(4):391-411, 1997.

Digital Library

[33]

{33} S. Sethumadhavan, R. Desikan, D. Burger, C. R. Moore, and S.W. Keckler. Scalabel hardware memory disambiguation for high ILP processors. In Proceedings of the 36th Annual International Symposium on Microarchitecture (MICRO-36), Dec 2003.

Digital Library

[34]

{34} J. Seward. Valgrind, an open-source memory debugger for x86-GNU/Linux. available at URL http://developer.kde.org/ sewardj/.

[35]

{35} SPARC International. The SPARC architecture manual: Version 8. Prentice-Hall, 1992.

Digital Library

[36]

{36} A. Srivastava and A. Eustace. ATOM: A System for Building Customized Program Analysis Tools. In Proceedings of SIGPLAN 1994 Conference on Programming Language Design and Implementation (PLDI), June 1994.

Digital Library

[37]

{37} R. Wahbe. Efficient data breakpoints. In Proceedings of the fifth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-V), 1992.

Digital Library

[38]

{38} E. Witchel, J. Cates, and K. Asanovic. Mondrian memory protection. In Proceedings of the Tenth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-X), Oct 2002.

Digital Library

[39]

{39} M. Xu, R. Bodik, and M. D. Hill. A "flight data recorder" for enabling full-system multiprocessor deterministic replay. In Proceedings of the 30th Annual International Symposium on Computer Architecture (ISCA), 2003.

Digital Library

[40]

{40} P. Zhou, F. Qin, W. Liu, Y. Zhou, and J. Torrellas. iWatcher: Efficient Architectural Support for Software Debugging. In Proceedings of the 31st International Symposium on Computer Architecture (ISCA), 2004.

Digital Library

Cited By

Dinh MJin CAbramson DJeffery C(2016)Runtime verification of scientific computingProceedings of the 5th Workshop on Extreme-Scale Programming Tools10.5555/3018823.3018827(26-33)Online publication date: 13-Nov-2016
https://dl.acm.org/doi/10.5555/3018823.3018827
Zhang MWu YLu SQi SRen JZheng W(2016)A Lightweight System for Detecting and Tolerating Concurrency BugsIEEE Transactions on Software Engineering10.1109/TSE.2016.253166642:10(899-917)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1109/TSE.2016.2531666
Park JDiniz P(2015)Program-Invariant Checking for Soft-Error Detection using Reconfigurable HardwareACM Transactions on Reconfigurable Technology and Systems10.1145/27515639:1(1-13)Online publication date: 5-Nov-2015
https://dl.acm.org/doi/10.1145/2751563
Show More Cited By

AccMon: Automatically Detecting Memory-Related Bugs via Program Counter-Based Invariants
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis

Recommendations

Efficient Java exception handling in just-in-time compilation
Research Articles

Java uses exceptions to provide elegant error handling capabilities during program execution. However, the presence of exception handlers complicates the job of the just-in-time (JIT) compiler, while exceptions are rarely used in most programs. This ...
Using evolution patterns to find duplicated bugs
An exploratory study on exception handling bugs in Java programs

We study exception handling bugs from two real systems.We survey developers to understand their thoughts about exception handling bugs.Analysis of bug repositories shows small percentages of exception handling bugs.Exception handling bugs seems to be as ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MICRO 37: Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture

December 2004

345 pages

ISBN:0769521266

Sponsors

SIGMICRO: ACM Special Interest Group on Microarchitectural Research and Processing

Publisher

IEEE Computer Society

United States

Publication History

Published: 04 December 2004

Check for updates

Qualifiers

Article

Conference

MICRO37

Sponsor:

SIGMICRO

MICRO37: The 37th Annual International Symposium on Microarchitecture

December 4 - 8, 2004

Oregon, Portland

Acceptance Rates

MICRO 37 Paper Acceptance Rate 29 of 158 submissions, 18%;

Overall Acceptance Rate 484 of 2,242 submissions, 22%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

68
Total Citations
View Citations
521
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dinh MJin CAbramson DJeffery C(2016)Runtime verification of scientific computingProceedings of the 5th Workshop on Extreme-Scale Programming Tools10.5555/3018823.3018827(26-33)Online publication date: 13-Nov-2016
https://dl.acm.org/doi/10.5555/3018823.3018827
Zhang MWu YLu SQi SRen JZheng W(2016)A Lightweight System for Detecting and Tolerating Concurrency BugsIEEE Transactions on Software Engineering10.1109/TSE.2016.253166642:10(899-917)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1109/TSE.2016.2531666
Park JDiniz P(2015)Program-Invariant Checking for Soft-Error Detection using Reconfigurable HardwareACM Transactions on Reconfigurable Technology and Systems10.1145/27515639:1(1-13)Online publication date: 5-Nov-2015
https://dl.acm.org/doi/10.1145/2751563
Chaudhary SFischmeister STan L(2014)em-SPADEACM SIGPLAN Notices10.1145/2666357.259782349:5(105-114)Online publication date: 12-Jun-2014
https://dl.acm.org/doi/10.1145/2666357.2597823
Chaudhary SFischmeister STan LZhang YKulkarni P(2014)em-SPADEProceedings of the 2014 SIGPLAN/SIGBED conference on Languages, compilers and tools for embedded systems10.1145/2597809.2597823(105-114)Online publication date: 12-Jun-2014
https://dl.acm.org/doi/10.1145/2597809.2597823
Lee STuck J(2013)Automatic parallelization of fine-grained metafunctions on a chip multiprocessorACM Transactions on Architecture and Code Optimization10.1145/2541228.254123710:4(1-26)Online publication date: 1-Dec-2013
https://dl.acm.org/doi/10.1145/2541228.2541237
Giuffrida CKuijsten ATanenbaum A(2013)Safe and automatic live update for operating systemsACM SIGPLAN Notices10.1145/2499368.245114748:4(279-292)Online publication date: 16-Mar-2013
https://dl.acm.org/doi/10.1145/2499368.2451147
Giuffrida CKuijsten ATanenbaum A(2013)Safe and automatic live update for operating systemsACM SIGARCH Computer Architecture News10.1145/2490301.245114741:1(279-292)Online publication date: 16-Mar-2013
https://dl.acm.org/doi/10.1145/2490301.2451147
Giuffrida CKuijsten ATanenbaum ASarkar VBodik R(2013)Safe and automatic live update for operating systemsProceedings of the eighteenth international conference on Architectural support for programming languages and operating systems10.1145/2451116.2451147(279-292)Online publication date: 16-Mar-2013
https://dl.acm.org/doi/10.1145/2451116.2451147
Lee STuck J(2011)Automatic parallelization of fine-grained meta-functions on a chip multiprocessorProceedings of the 9th Annual IEEE/ACM International Symposium on Code Generation and Optimization10.5555/2190025.2190060(130-140)Online publication date: 2-Apr-2011
https://dl.acm.org/doi/10.5555/2190025.2190060
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents