Method for optimizing array bounds checks in programs

Details Method for optimizing array bounds checks in programs Method for optimizing array bounds checks in programs

1998-04-24

2002-01-29

Powell, Mark R. (Department: 2122)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

Reexamination Certificate

active

06343375

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to computer programming and, more particularly, to a method for a compiler, programmer or run-time system to transform a program so as to reduce the overhead of determining if an invalid reference to an array element is attempted, while strictly preserving the original semantics of the program.
2. Background Description
The present invention is a method for a compiler, program translation system, run-time system or a programmer to transform a program or stream of instructions in some machine language so as to minimize the number of array reference tests that must be performed while maintaining the exact semantics of the program that existed before the transformation.
A single-dimensional array A is defined by a lower bound lo(A) and an upper bound up(A). A[lo(A):up(A)] represents an array with (up(A)−lo(A)+1) elements. An array element reference is denoted by A[&sgr;], where &sgr; is an index into the array, also called a subscript expression. This subscript expression may be a constant value at run-time, or it may be computed by evaluating an expression which has both constant and variable terms. For the reference A[&sgr;] to be valid, A must represent an existing array, and a must be within the valid range of indices for A: lo(A), lo(A)+1, . . . , up(A). If A does not represent an existing array, we say that A is null. If &sgr; is not within the valid range of indices for A, we say that &sgr; is out of bounds. The purpose of array reference tests is to guarantee that all array references are valid. If an array reference is not valid we say that it produces an array reference violation. We can define lo(A)=0 and up(A)=−1 for null arrays. In this case, out of bounds tests cover all violations. Array references typically (but not exclusively) occur in the body of loops. The loop index variable is often used in subscript expressions within the body of the loop.
The goal of our method and its variants is to produce a program, or segment of one, in which all array reference violations are detected by explicit array reference tests. This is achieved in an efficient manner, performing a reduced number of tests. The ability to perform array reference tests in a program is important for at least three reasons:
1. Accesses to array elements outside the range of valid indices for the array have been used in numerous attacks on computer systems. See S. Garfinkel and G. Spafford,
Practical Unix and Internet Security
, O'Reilly and Associates (1996), and D. Dean, E. Felton and D. Wallach, “Java security: From HotJava to Netscape and beyond”,
Proceedings of the
1996
IEEE Symposium on Security and Privacy
, May 1996.
2. Accesses to array elements outside the range of valid indices for the array are a rich source of programming errors. Often the error does not exhibit itself until long after the invalid reference, making correction of the error a time-consuming and expensive process. The error may never flagrantly exhibit itself, leading to subtle and dangerous errors in computed results.
3. Detection of array reference violations are mandated by the semantics of some programming languages, such as Java™. (Java is a trademark of Sun Microsystems, Inc.).
Naively checking every array reference that occurs has an adverse effect on the execution time of the program. Thus, programs are often run with tests disabled. Therefore, to fully realize the benefits of array reference tests it is necessary that they be done efficiently.
Prior art for detecting an out of bounds array reference or a memory reference through an invalid memory address can be found in U.S. Pat. No. 5,535,329, U.S. Pat. No. 5,335,344, U.S. Pat. No. 5,613,063, and U.S. Pat. No. 5,644,709. These patents give methods for performing bounds tests in programs, but do not give methods for a programmer, a compiler or translation system for a programming language, or a run-time system to reduce the number of tests.
Prior art exists for the narrow goal of simply reducing the run-time overhead of array bounds testing, while changing the semantics of the program in the case where an error occurs. See P. Cousot and R. Cousot, “Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints”,
Conference Record of the
4
th
ACM Symposium on Principles of Programming Languages
, pp. 238-252, January 1977; W. H. Harrison, “Compiler analysis for the value ranges for variables”,
IEEE Transactions on Software Engineering
, SE3(3):243-250, May 1997; P. Cousot and N. Halbwachs, “Automatic discovery of linear restraints among variables in a program”,
conference Record of the
5
th
ACM Symposium on Principles of Programming Languages
”, pp. 84-96, January 1978; P. Cousot and N. Halbwachs, “Automatic proofs of the absence of common runtime errors”,
Conference Record of the
5
th
ACM Symposium on Principles of Programming Languages
, pp. 105-118, January 1978; B. Schwarz, W. Kirchgassner and R. Landwehr, “An optimizer for Ada—design, experience and results”,
Proceedings of the ACM SIGPLAN '
88
Conference on Programming Language Design and Implementation
, pp. 175-185, June 1988; V. Markstein, J. Cocke and P. Markstein, “Elimination of redundant array subscript range checks”,
Proceedings of the ACM SIGPLAN '
82
Conference on Programming Language Design and Implementation
, pp. 114-119, June 1982; R. Gupta, “A fresh look at optimizing array bounds checking”,
Proceedings of the ACM SIGPLAN '
90
Conference on Programming Language Design and Implementation
, pp. 272-282, June 1990; P. Kolte and M. Wolfe, “Elimination of redundant array subscript range checks”,
Proceedings of the ACM SIGPLAN '
95
Conference on Programming Language Design and Implementation
, pp. 270-278, June 1995; J. M. Asuru, “Optimization of array subscript range checks”,
ACM Letters on Programming Languages and Systems
, 1(2):109-118, June 1992; R. Gupta, “Optimizing array bounds checks using flow analysis”,
ACM Letters on Programming Languages and Systems
, 1-4(2):135-150, March-December 1993; and U.S. Pat. No. 4,642,765. These approaches fall into two major groups. In the first group, P. Cousot and R. Cousot, W. H. Harrison, P. Cousot and N. Halbwachs (both citations), and B. Schwarz et al., analysis is performed on the program to determine that an reference A
2
[&sgr;
2
] in a program will lead to an out of bounds array reference only if a previous reference A
1
[&sgr;
1
] also leads to an out of bounds array reference. Thus, if the program is assumed to terminate at the first out of bounds array reference, only reference A
1
[&sgr;
1
] needs to be checked, since reference A
2
[&sgr;
2
] will never actually perform an out of bounds array reference. These techniques are complementary to our method. That is, they can be used in conjunction with our method to provide some benefit, but are not necessary for our method to work, or for our method to provide its benefit.
In the second group, V. Markstein et al., R. Gupta (both citations), P. Kolte et al., J. M. Asuru, and U.S. Pat. No. 4,642,765, bounds tests for array references within loops of a program are optimized. Consider an array reference of the form A[&sgr;] where the subscript expression &sgr; is a linear function in a loop induction variable. Furthermore, the value of &sgr; can be computed prior to the execution of each iteration. A statement is inserted to test this value against the bounds of the array prior to the execution of each iteration. The statement raises an exception if the value of &sgr; in a reference A[&sgr;] is less than lo(A), or is greater than up(A). The transformations in this group can also use techniques from the first group to reduce the complexity of the resulting tests.
The weakness of the first group is that at least one test must remain in the body of any loop whose index variable i

Affiliated with

Also associated with

Rating

Method for optimizing array bounds checks in programs does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method for optimizing array bounds checks in programs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for optimizing array bounds checks in programs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2838468