article

Free access

Efficient detection of all pointer and array access errors

Authors:

Todd M. Austin,

Scott E. Breach,

Gurindar S. SohiAuthors Info & Claims

ACM SIGPLAN Notices, Volume 29, Issue 6

Pages 290 - 301

https://doi.org/10.1145/773473.178446

Published: 01 June 1994 Publication History

Abstract

We present a pointer and array access checking technique that provides complete error coverage through a simple set of program transformations. Our technique, based on an extended safe pointer representation, has a number of novel aspects. Foremost, it is the first technique that detects all spatial and temporal access errors. Its use is not limited by the expressiveness of the language; that is, it can be applied successfully to compiled or interpreted languages with subscripted and mutable pointers, local references, and explicit and typeless dynamic storage management, e.g., C. Because it is a source level transformation, it is amenable to both compile- and run-time optimization. Finally, its performance, even without compile-time optimization, is quite good. We implemented a prototype translator for the C language and analyzed the checking overheads of six non-trivial, pointer intensive programs. Execution overheads range from 130% to 540%; with text and data size overheads typically below 100%.

References

[1]

A.V. Aho, R. Sethi, and J.D. Ullman. Compilers: Principles, Techntques, and Tools. Addison-Wesley, Reading, MA, 1986.

Digital Library

[2]

Hans-Juergen Boehm. Space efficieht conservative garbage collection. Proceedings of the A CM SIGPLAN '93 Conference on Programming Language Design and Implementation, 28(6):197-204, June 1993.

Digital Library

[3]

Hans-Juergen Boehm and Mark Weiser. Garbage collection in an uncooperative environment. Software -Practtce and Experience, 18(9):807-820, September 1988.

Digital Library

[4]

John R. Ellis and David L. Detlefs. Safe, efficient garbage collection for C++. Technical Report 102, DEC Systems Research Center, June 1993.

[5]

D.R. Edelson and I. Pohl. Smart pointers: They're smart but they're not pointers. Proceedings of the i991 Usen~x C-k+ Conference, April 1991.

[6]

Anthony J. Field and Peter G. Harrison. Functional Programming. Addison-Wesley Publishing Company, 1988.

[7]

Charles N. Fischer and Richard J. LeBlanc. The implementation of run-time diagnostics in Pascal. IEEE Transactions on Software Engineering, SE-6(4):313-319, 1980.

Digital Library

[8]

Andrew Ginter. Design alternatives for a cooperative garbage collector for the C++ programming language. Technical Report 91/417/01, Department of Computer Science, University of Calgary, 1992.

[9]

Rajiv Gupta. A fresh look at optimizing array bound checking. Proceedings of the ACM SIGPLAN '90 Conference on Programming Language Design and Implementation, pages 272-282, June 1990.

Digital Library

[10]

Reed Hastings and Bob Joyce. Purify: fast detection of memory leaks and access errors. Proceedings of the Winter Usen~x Conference, 1992.

[11]

Samuel C. Kendall. Bcc: Runtime checking for C programs. Proceedings of the Summer Usenzx Conference, 1983.

[12]

Stephen Kaufer, Russel Lopez, and Sesha Pratap. Saber- C: an interpreter-based programming environment for the C language. Proceedings of the Summer Usenix Conference, pages 161-171, 1988.

[13]

James R. Larus. Efficient program tracing. IEEE Computer, 26(5):52-61, May 1993.

Digital Library

[14]

Peter Lee, editor. Topics in Advanced Language Implementation. The MIT Press, Cambridge, MA, 1991.

Digital Library

[15]

Barton P. Miller, Lars Fredriksen, and Bryan So. An empirical study of the reliability of Unix utilities. Communications of the ACM, 33(12):32-44, December 1990.

Digital Library

[16]

Graham Ross. Integral C - a practical environment for C programming. In Proceedings of the A CM SIG- SOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Enwronments (SIGPLAN Notices), pages 42-48. Association for Computing Machinery, January 1987.

Digital Library

[17]

Mark Sullivan and Ram Chillarege. Software defects and their impact on system availability - a study of field failures in operating systems. Digest of the ~1st International Symposium on Fault Tolerant Computing, pages 2-9, June 1991.

[18]

Joseph L. Steffen. Adding run-time checking to the Portable C Compiler. Software - Practice and Experience, 22(4):305-316, 1992.

Digital Library

[19]

Benjamin Zorn and Paul Hilfinger. A memory allocation profiler for C and Lisp programs. Proceedings of the Summer Usen~x Conference, pages 223-237, 1988.

Cited By

Seo JBang ICho YShin JHwang DKwon DCho YPaek Y(2022)Exploring effective uses of the tagged memory for reducing bounds checking overheadsThe Journal of Supercomputing10.1007/s11227-022-04694-y79:1(1032-1064)Online publication date: 20-Jul-2022
https://doi.org/10.1007/s11227-022-04694-y
Ziad MArroyo MManzhosov EPiersma RSethumadhavan SMartínez JDuato JJohn L(2021)No-FATProceedings of the 48th Annual International Symposium on Computer Architecture10.1109/ISCA52012.2021.00076(916-929)Online publication date: 14-Jun-2021
https://dl.acm.org/doi/10.1109/ISCA52012.2021.00076
Vasiladiotis CLozano RCole MFranke BLee J(2021)Loop parallelization using dynamic commutativity analysisProceedings of the 2021 IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO51591.2021.9370319(150-161)Online publication date: 27-Feb-2021
https://dl.acm.org/doi/10.1109/CGO51591.2021.9370319
Show More Cited By

Index Terms

Efficient detection of all pointer and array access errors
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
    2. General programming languages
      1. Language features
      2. Language types
2. Theory of computation
  1. Semantics and reasoning
    1. Program constructs

Recommendations

Efficient detection of all pointer and array access errors
PLDI '94: Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation

We present a pointer and array access checking technique that provides complete error coverage through a simple set of program transformations. Our technique, based on an extended safe pointer representation, has a number of novel aspects. Foremost, it ...
Interprocedural pointer alias analysis

We present practical approximation methods for computing and representing interprocedural aliases for a program written in a language that includes pointers, reference parameters, and recursion. We present the following contributions: (1) a framework ...
Detecting memory errors via static pointer analysis (preliminary experience)
PASTE '98: Proceedings of the 1998 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering

Programs which manipulate pointers are hard to debug. Pointer analysis algorithms (originally aimed at optimizing compilers) may provide some remedy by identifying potential errors such as dereferencing NULL pointers by statically analyzing the behavior ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 29, Issue 6

June 1994

360 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/773473

Guest Editor:
Brent T. Hailpern

Issue’s Table of Contents

PLDI '94: Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation
August 1994
360 pages
ISBN:089791662X
DOI:10.1145/178243
Chairmen:
Vivek Sarkar
IBM Santa Teresa Lab.
,
Barbara Ryder
Rutgers Univ., New Brunswick, NJ
,
Mary Lou Soffa
Univ. of Pittsburgh, Pittsburgh, PA

Copyright © 1994 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1994

Published in SIGPLAN Volume 29, Issue 6

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

338
Total Citations
View Citations
1,803
Total Downloads

Downloads (Last 12 months)279
Downloads (Last 6 weeks)28

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Seo JBang ICho YShin JHwang DKwon DCho YPaek Y(2022)Exploring effective uses of the tagged memory for reducing bounds checking overheadsThe Journal of Supercomputing10.1007/s11227-022-04694-y79:1(1032-1064)Online publication date: 20-Jul-2022
https://doi.org/10.1007/s11227-022-04694-y
Ziad MArroyo MManzhosov EPiersma RSethumadhavan SMartínez JDuato JJohn L(2021)No-FATProceedings of the 48th Annual International Symposium on Computer Architecture10.1109/ISCA52012.2021.00076(916-929)Online publication date: 14-Jun-2021
https://dl.acm.org/doi/10.1109/ISCA52012.2021.00076
Vasiladiotis CLozano RCole MFranke BLee J(2021)Loop parallelization using dynamic commutativity analysisProceedings of the 2021 IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO51591.2021.9370319(150-161)Online publication date: 27-Feb-2021
https://dl.acm.org/doi/10.1109/CGO51591.2021.9370319
Banerjee SDevecsery DChen PNarayanasamy S(2020)Sound garbage collection for C using pointer provenanceProceedings of the ACM on Programming Languages10.1145/34282444:OOPSLA(1-28)Online publication date: 13-Nov-2020
https://doi.org/10.1145/3428244
Li WXu DWu WGong XXiang XWang Ygu FZeng Q(2019)Memory access integrity: detecting fine-grained memory access errors in binary codeCybersecurity10.1186/s42400-019-0035-x2:1Online publication date: 7-Jun-2019
https://doi.org/10.1186/s42400-019-0035-x
Zhang TLee DJung CBahar IHerlihy MWitchel ELebeck A(2019)BOGOProceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3297858.3304017(631-644)Online publication date: 4-Apr-2019
https://dl.acm.org/doi/10.1145/3297858.3304017
Ruef ALampropoulos LSweet ITarditi DHicks M(2019)Achieving Safety Incrementally with Checked CPrinciples of Security and Trust10.1007/978-3-030-17138-4_4(76-98)Online publication date: 3-Apr-2019
https://doi.org/10.1007/978-3-030-17138-4_4
van der Kouwe EKroes TOuwehand CBos HGiuffrida C(2018)Type-After-TypeProceedings of the 34th Annual Computer Security Applications Conference10.1145/3274694.3274705(17-27)Online publication date: 3-Dec-2018
https://dl.acm.org/doi/10.1145/3274694.3274705
Elliott ARuef AHicks MTarditi D(2018)Checked C: Making C Safe by Extension2018 IEEE Cybersecurity Development (SecDev)10.1109/SecDev.2018.00015(53-60)Online publication date: Sep-2018
https://doi.org/10.1109/SecDev.2018.00015
Menon AMurugan SRebeiro CGala NVeezhinathan K(2017)Shakti-TProceedings of the Hardware and Architectural Support for Security and Privacy10.1145/3092627.3092629(1-8)Online publication date: 25-Jun-2017
https://dl.acm.org/doi/10.1145/3092627.3092629
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Issue’s Table of Contents