Abstract
The ability to check memory references against their associated array/buffer bounds helps programmers to detect programming errors involving address overruns early on and thus avoid many difficult bugs down the line. This paper proposes a novel approach called Boud to the array bounds checking problem that exploits the debug register hardware in modern CPUs. Boud allocates a debug register to monitor accesses to an array or buffer within a loop so that accesses stepping outside the array’s or buffer’s bound will trigger a breakpoint exeption. Because the number of debug registers is typically small, in cases when hardware bounds checking is not possible, Boud falls back to software bounds checking. Although Boud can effectively eliminate per-array-reference software checking overhead in most cases, it still incurs a fixed set-up overhead for each use of an array within a loop. This paper presents the detailed design and implementation of the Boud compiler, and a comprehensive evaluation of various performance tradeoffs associated with the proposed array bounds checking technique. For the set of real-world network applications we tested, including Apache, Sendmail, Bind, etc., the latency penalty of Boud’s bounds checking mechanism is between 2.2% to 8.8%, respectively, when compared with the vanilla GCC compiler, which does not perform any bounds checking.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Perens, B.: Electric fence: a malloc() debugger for linux and unix. http://perens.com/FreeSoftware/
Bentley, C., Watterson, S.A., Lowenthal, D.K.: A comparison of array bounds checking on superscalar and vliw architectures. In: The annual IEEE Workshop on Workload Characterization (submitted)
Lam, L.-C., Chiueh, T.-C.: Checking array bound violation using segmentation hardware. In: DSN 2005. Proceedings of 2005 International Conference on Dependable Systems and Networks (June 2005)
Cowan, C., et al.: Stackguard: Automatic adaptive detection and prevention of buffer-overflow attacks. In: Proc. 7th USENIX Security Conference, San Antonio, Texas, pp. 63–78 (January 1998)
GCC. Bounds-checking gcc, http://www.gnu.org/software/gcc/projects/bp/main.html
Pearson, G.: Array bounds checking with turbo c. Dr. Dobb’s Journal of Software Tools 16(5) 72, 74, 78–79, 81–82, 104–107 (1991)
Patil, H., Fischer, C.N.: Efficient run-time monitoring using shadow processing. In: Proceedings of Automated and Algorithmic Debugging Workshop, pp. 119–132 (1995)
Xi, H., Pfenning, F.: Eliminating array bound checking through dependent types. In: SIGPLAN Conference on Programming Language Design and Implementation, pp. 249–257 (1998)
Xi, H., Xia, S.: Towards array bound check elimination in java virtual machine language. In: Proceedings of CASCON 1999, Mississauga, Ontario, pp. 110–125 (November 1999)
Intel. IA-32 Intel Architecture Software Developer’s Manual vol. 2 Instruction Set Reference, http://www.intel.com/design/Pentium4/manuals/
Intel. Ia-32 intel architecture software developer’s manual. volume 3: System programming guide, http://developer.intel.com/design/pentium4/manuals/245472.htm
Asuru, J.M.: Optimization of array subscript range checks. ACM letters on Programming Languages and Systems 1(2), 109–118 (1992)
Jones, R.W.M., Kelly, P.H.J.: Backwards-compatible bounds checking for arrays and pointers in c programs. In: Proceedings of Automated and Algorithmic Debugging Workshop, pp. 13–26 (1997)
Kolte, P., Wolfe, M.: Elimination of redundant array subscript range checks. In: SIGPLAN Conference on Programming Language Design and Implementation, pp. 270–278 (1995)
Prasad, M., Chiueh, T.-C.: A binary rewriting approach to stack-based buffer overflow attacks. In: Proceedings of 2003 USENIX Conference (June 2003)
Qin, F., Lu, S., Zhou, Y.: Safemem: Exploiting ecc-memory for detecting memory leaks and memory corruption during production runs. In: HPCA 2005. Proceedings of the 11th International Symposium on High-Performance Computer Architecture (February 2005)
Gupta, R.: A fresh look at optimizing array bound checking. In: SIGPLAN Conference on Programming Language Design and Implementation, pp. 272–282 (1990)
Gupta, R.: Optimizing array bound checks using flow analysis. ACM Letters on Programming Languages and Systems 2(1-4), 135–150 (1993)
Bodik, R., Gupta, R., Sarkar, V.: Abcd: eliminating array bounds checks on demand. In: SIGPLAN Conference on Programming Language Design and Implementation, pp. 321–333 (2000)
Chiueh, T.-C., Hsu, F.-H.: Rad: A compiler time solution to buffer overflow attacks. In: ICDCS. Proceedings of International Conference on Distributed Computing Systems, Phoenix, Arizona (April 2001)
Chiueh, T.-C., Venkitachalam, G., Pradhan, P.: Integrating segmentation and paging protection for safe, efficient and transparent software extensions. In: Proceedings of 17th ACM Symposium on Operating Systems Principles, Charleston, SC (December 1999)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chiueh, Tc. (2008). Fast Bounds Checking Using Debug Register. In: Stenström, P., Dubois, M., Katevenis, M., Gupta, R., Ungerer, T. (eds) High Performance Embedded Architectures and Compilers. HiPEAC 2008. Lecture Notes in Computer Science, vol 4917. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-77560-7_8
Download citation
DOI: https://doi.org/10.1007/978-3-540-77560-7_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-77559-1
Online ISBN: 978-3-540-77560-7
eBook Packages: Computer ScienceComputer Science (R0)