article

Open access

Implicit array bounds checking on 64-bit architectures

Authors:

Chris Bentley,

Scott A. Watterson,

David K. Lowenthal,

Barry RountreeAuthors Info & Claims

ACM Transactions on Architecture and Code Optimization (TACO), Volume 3, Issue 4

Pages 502 - 527

https://doi.org/10.1145/1187976.1187982

Published: 01 December 2006 Publication History

PDF eReader

Abstract

Several programming languages guarantee that array subscripts are checked to ensure they are within the bounds of the array. While this guarantee improves the correctness and security of array-based code, it adds overhead to array references. This has been an obstacle to using higher-level languages, such as Java, for high-performance parallel computing, where the language specification requires that all array accesses must be checked to ensure they are within bounds. This is because, in practice, array-bounds checking in scientific applications may increase execution time by more than a factor of 2. Previous research has explored optimizations to statically eliminate bounds checks, but the dynamic nature of many scientific codes makes this difficult or impossible. Our approach is, instead, to create a compiler and operating system infrastructure that does not generate explicit bounds checks. It instead places arrays inside of Index Confinement Regions (ICRs), which are large, isolated, mostly unmapped virtual memory regions. Any array reference outside of its bounds will cause a protection violation; this provides implicit bounds checking. Our results show that when applying this infrastructure to high-performance computing programs written in Java, the overhead of bounds checking relative to a program with no bounds checks is reduced from an average of 63% to an average of 9%.

References

[1]

Artigas, P., Gupta, M., Midkiff, S., and Moreira, J. 2000. Automatic loop transformations and parallelization for Java. In Proc. ACM International Conference on Supercomputing. 1--10.

Digital Library

Google Scholar

[2]

Bailey, D., Barton, J., Lasinski, T., and Simon, H. 1991. The NAS parallel benchmarks. RNR-91-002, NASA Ames Research Center.

Google Scholar

[3]

BEA. 2005. BEA JRockit whitepaper (http://www.bea.com/content/news_events/white_papers/bea_jrockit_wp.pdf).

Google Scholar

[4]

Bodik, R., Gupta, R., and Sarkar, V. 2000. ABCD: eliminating array-bounds checks on demand. In Proc. ACM Conference on Programming Language Design and Implementation. 321--333.

Crossref

Google Scholar

[5]

Boisvert, R. F., Dongarra, J. J., Pozo, R., Remington, K. A., and Stewart, G. W. 1998. Optimizing array reference checking in Java programs. Concurrency: Practice and Experience 10, 11-13, 1117--1129.

Google Scholar

[6]

Chase, J. S., Levy, H. M., Feeley, M. J., and Lazowska, E. D. 1994. Sharing and protection in a single address space operating system. ACM Transactions on Computer Systems 12, 4 (May), 271--307.

Digital Library

Google Scholar

[7]

Chiueh, T. and Hsu, F. 2001. RAD: A compile-time solution to buffer overflow attacks. In Proc. IEEE International Conference on Distributed Computing Systems. 409--420.

Crossref

Google Scholar

[8]

Cowan, C., Pu, C., Maier, D., Walpole, J., Bakke, P., Beattie, S., Grier, A., Wagle, P., Zhang, Q., and Hinton, H. 1998. StackGuard: Automatic adaptive detection and prevention of buffer-overflow attacks. In Proc. USENIX Security Conference. 63--78.

Crossref

Google Scholar

[9]

Dahn, C. and Mancoridis, S. 2003. Using program transformation to secure c programs against buffer overflows. In Working Conference on Reverse Engineering. 323--333.

Crossref

Google Scholar

[10]

Frumkin, M., Schultz, M., Jin, H., and Yan, J. 2002. Implementation of the NAS parallel benchmarks in Java. NAS-02-009, NASA Ames Research Center.

Google Scholar

[11]

Gupta, R. 1993. Optimizing array-bound checks using flow analysis. ACM Letters on Programming Languages and Systems 2, 1--4 (Mar.--Dec.), 135--150.

Digital Library

Google Scholar

[12]

Intel. 2006. Intel Itanium Architecture Software Developer's Manual (http://download.intel.com/design/itanium/manuals/24531705.pdf).

Google Scholar

[13]

Itzkovitz, A. and Schuster, A. 1999. Multiview and Millipage---fine-grain sharing in page-based DSMs. In Proc. USENIX Operating Systems Design and Implementation. 215--228.

Crossref

Google Scholar

[14]

Java hotspot vm options (http://java.sun.com/docs/hotspot/vmoptions.html).

Google Scholar

[15]

Kolte, P. and Wolfe, M. 1995. Elimination of redundant array subscript range checks. In Proc. ACM Conference on Programming Language Design and Implementation. 270--278.

Crossref

Google Scholar

[16]

Lam, L. and Chiueh, T. 2005. Checking array-bound violation using segmentation hardware. In Proc. IEEE International Conference on Dependable Systems and Networks. 388--397.

Crossref

Google Scholar

[17]

Markstein, V., Cocke, J., and Markstein, P. 1982. Optimization of range checking. In Proc. ACM Conference on Programming Language Design and Implementation. 114--119.

Crossref

Google Scholar

[18]

McGary, G. Bounds-checking C compiler (http://www.gnu.org/software/gcc/projects/bp/main.html).

Google Scholar

[19]

Midkiff, S. P., Moreira, J. E., and Snir, M. 1998. Optimizing array reference checking in Java programs. IBM Systems Journal 37, 3, 409--453.

Digital Library

Google Scholar

[20]

Moreira, J., Midkiff, S. P., Gupta, M., Artigas, P., and Snir, M. 2000. Java programming for high performance numerical computing. IBM Systems Journal 39, 1, 21--56.

Digital Library

Google Scholar

[21]

Mosberger, D. and Eranian, S. 2002. IA-64 Linux Kernel: Design and Implementation. Prentice-Hall, Eaglewood Cliffs, NJ.

Crossref

Google Scholar

[22]

Perens, B. Electric Fence (http://sunsite.unc.edu/pub/linux/devel/lang/c/electricfence-2.0.5.tar.gz).

Google Scholar

[23]

Rugina, R. and Rinard, M. C. 2000. Symbolic bounds analysis of pointers, array indices, and accessed memory regions. In Proc. ACM Conference on Programming Language Design and Implementation. 182--195.

Crossref

Google Scholar

[24]

SUN. 2002. The Java HotSpot virtual machine (http://java.sun.com/products/hotspot/docs/whitepaper/java_hotspot_v1.4.1/jhs_141_wp_d2a.pdf).

Google Scholar

[25]

Talluri, M., Hill, M. D., and Khalidi., Y. A. 1995. A new page table for 64-bit address spaces. In Proc. ACM Symposium on Operating Systems Principles. 184--200.

Crossref

Google Scholar

[26]

Winwood, S., Shuf, Y., and Franke, H. 2002. Multiple page size support in the linux kernel.

Google Scholar

[27]

Xi, H. and Pfenning, F. 1998. Eliminating array-bound checking through dependent types. In Proc. ACM Conference on Programming Language Design and Implementation. 249--257.

Crossref

Google Scholar

[28]

Xi, H. and Xia, S. 1999. Towards array-bound check elimination in Java virtual machine langauge. In Proc. Centre for Advanced Studies Conference. 110--125.

Crossref

Google Scholar

[29]

Young, M., Avadis Tevanian, J., Rashid, R., Eppinger, D. G. J., Chew, J., Bolosky, W., Black, D., and Baron, R. 1987. The duality of memory and communication in the implementation of a multiprocessor operating system. In Proc. ACM Symposium on Operating Systems Principles. 63--76.

Crossref

Google Scholar

Index Terms

Implicit array bounds checking on 64-bit architectures
1. Information systems
  1. Information storage systems
    1. Record storage systems
      1. Record storage alternatives
    2. Storage management
2. Software and its engineering
  1. Software notations and tools
    1. Compilers
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        File systems management
        Memory management

Recommendations

Implicit java array bounds checking on 64-bit architecture
ICS '04: Proceedings of the 18th annual international conference on Supercomputing

Interest in using Java for high-performance parallel computing has increased in recent years. One obstacle that has inhibited Java from widespread acceptance in the scientific community is the language requirement that all array accesses must be checked ...
Performant Bounds Checking for 64-Bit WebAssembly
VMIL '24: Proceedings of the 16th ACM SIGPLAN International Workshop on Virtual Machines and Intermediate Languages

WebAssembly is becoming increasingly popular for various use cases due to its high portability, strict and easily enforceable isolation, and its comparably low run-time overhead. For determinism and security, WebAssembly guarantees that accesses to ...
Array Bounds Model Checking in C Code Based on Predicate Abstraction
CCATS '15: Proceedings of the 2015 International Conference on Computer Application Technologies

As C program compilers do not check the array bounds during compiling, array index out of bounds attacks cause serious security problems. Array bound checking is becoming more and more important, however, original array bound checking, which needs ...

Reviews

Reviewer: R. Clayton

Manipulating virtual memory implementations to provide improved primary storage access protection has a long and fruitful history. Changes in technologies and applications make possible new manipulations providing better protection. This paper describes how Java and 64-bit architectures can be exploited to provide time-efficient array bounds checking. Java requires that out-of-bound array accesses be detected and flagged; the cost of doing so can be expensive for array-intensive applications. However, artfully mapping each array dimension into a contiguous virtual memory segment can reduce array bounds checking to unmapped page access, moving the problem from an expensive language to a relatively cheaper operating system. Because practical programs can have many large segments, a 64-bit address space is essential. However, even with a 64-bit address space, the segment population can stress the operating system, a problem ameliorated by modifying the virtual memory subsystem. Balancing these factors as described in this paper results in code with no explicit checks but full array bounds checking at a cost within 10 percent of not doing any checks at all. This paper is excellent, well written, and clear. Java knowledge is not required; basic memory management knowledge is helpful but not required. In addition to being a model solution for the problem at hand, this paper can also serve as a good example of the engineering influences and tradeoffs found when working at the intersection of user applications, system software, and operating systems. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Architecture and Code Optimization

ACM Transactions on Architecture and Code Optimization Volume 3, Issue 4

December 2006

169 pages

ISSN:1544-3566

EISSN:1544-3973

DOI:10.1145/1187976

Issue’s Table of Contents

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 December 2006

Published in TACO Volume 3, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
715
Total Downloads

Downloads (Last 12 months)47
Downloads (Last 6 weeks)14

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Abstract

References

Index Terms

Recommendations

Implicit java array bounds checking on 64-bit architecture

Performant Bounds Checking for 64-Bit WebAssembly

Array Bounds Model Checking in C Code Based on Predicate Abstraction

Reviews

Access critical reviews of Computing literature here

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations