Array boounds checking Bibliography

Overview

A list of papers dealing with the implementation of array bounds checking in languages of interest to the ISO Language Vulnerabilities Working Group. The algorithms and results described in many older papers have been improved on and these older papers are not listed here. Only papers detailing, with experimental results, an actual implementation of any algorithms they contain are listed. If you think a paper should be included please email details to the maintainer.

The following paper provides empirical evidence that accessing objects outside their allocated bounds need not render an application unusable and argues that there are advantages to not performing memory bounds access checks in a non-testing non-development environment.

Martin Rinard, Cristian Cadar, and Huu Hai Nguyen. Exploring the acceptability envelope. In Conference on Object Oriented Programming Systems Languages and Applications, pages 21–30, October 2005.

Maintained by Derek Jones. Send suggested additions to derek (at) knosof.co dot uk.

Changelog

8 Feb 08 Initial release

Todd M. Austin, Scott E. Breach, and Gurindar S. Sohi. Efficient detection of all pointer and array access errors. In Proceedings of the SIGPLAN'94 Conference on Programming Language Design and Implementation, 1994.
Chris Bentley, Scott A. Watterson, and David K. Lowenthal. A comparison of array bounds checking on superscalar and VLIW architectures. Submitted to the IEEE Workshop on Workload Characterization, September 2002.
Rastislav Bodik, Rajiv Gupta, and Vivek Sarkar. ABCD: Eliminating array bounds checks on demand. In Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation, pages 321–333, June 2000.
Wei-Ngan Chin, Siau-Cheng Khoo, and Dana N. Xu. Deriving pre-conditions for array bound check elimination. In Proceedings of the Second Symposium on Programs as Data Objects, pages 2–24, May 2001.
Lap chung Larn and Tzi cker Chiueh. Checking array bound violation using segmentation hardware. Technical Report TR 181, Stony Brook University, April 2005.
Dinakar Dhurjati and Vikram Adve. Backwards-compatible array bounds checking for C with very low overhead. In Proceeding of the 28th International Conference on Software Engineering, pages 162–171, 2006.
Björn Franke and Michael O'Boyle. Compiler transformation of pointers to explicit array accesses in DSP applications. In Reinhard Wilhelm, editor, Compiler Construction, 10^th International Conference, pages 69–85. Springer-Verlag, April 2001.
Michael Hind and Anthony Pioli. Which pointer analysis should I use? International Symposium on Software Testing and Analysis (ISSTA 2000), Aug 2000, 2000.
Michael Hind. Pointer analysis: Haven't we solved this problem yet? In ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE'01), pages 54–61. ACM, June 2001.
Richard W. M. Jones and Paul H. J. Kelly. Backwards-compatible bounds checking for arrays and pointers in C programs. In M. Kamkar and D. Byers, editors, Third International Workshop on Automated Debugging. Linkoping University Electronic Press, 1997.
Priyadarshan Kolte and Michael Wolfe. Elimination of redundant array subscript range checks. SIGPLAN Notices, 30(6):270–278, June 1995. Fortran.
John Lu. Interprocedural Pointer Analysis for C. PhD thesis, Rice University, April 1998.
Mikel Luján, John R. Gurd, T. L. Freeman, and José Miguel. Elimination of Java array bounds checks in the presence of indirection. Concurrency abd Computation: Practice and Experience, 17(5-6):489–514, 2005.
Thi Viet Nga Nguyen, François Irigoin, Corinne Ancourt, and Ronan Keryell. Efficient intraprocedural array bound checking. In Second International Workshop on Automated Program Analysis, Testing and Verification (WAPATV01), May 2001. Fortran.
Feng Qian, Laurie Hendren, and Clark Verbrugge. A comprehensive approach to array bounds check elimination for Java. Technical Report Sable Technical Report No. 2000-4, McGill University, November 2000.
Radu Rugina and Martin C. Rinard. Symbolic bounds analysis of pointers, array indices, and accessed memory regions. ACM Transactions on Programming Languages and Systems, 27(2):185–235, March 2005.
Arnaud Venet. A scalable nonuniform pointer analysis for embedded programs. In Proceedings of the International Static Analysis Symposium, SAS 04, pages 149–164, August 2004.