Bounds checking
Encyclopedia
In computer programming
, bounds checking is any method of detecting whether a variable
is within some bounds before its use. It is particularly relevant to a variable used as an index
into an array to ensure its value lies within the bounds of the array. For example: a value of 32768 about to be assigned to a sixteen-bit signed integer variable (whose bounds are −32768 to +32767), or accessing element 25 on an array with index range 0 through 9 only. The first is also known as range checking, the second as index checking.
A failed bounds check usually results in the generation of some sort of exception
signal.
Because performing bounds checking during every usage is time-consuming it is not always done. Bounds-checking elimination
are compiler technologies that eliminate unneeded bounds checking in many common cases.
Many programming language
s, such as C
, never perform automatic bounds checking, to raise speed. However, this leaves uncaught many off-by-one error
s and buffer overflow
s. Many programmers believe these languages sacrifice too much for rapid execution. In his 1980 Turing Award
lecture, C. A. R. Hoare
described his experience in the design of ALGOL 60
, a language that included bounds checking, saying:
Mainstream languages that enforce run time checking include Ada
, C#, Haskell
, Java
, JavaScript
, Lisp, PHP
, Python
, Ruby
, and Visual Basic
. The D
and Objective Caml
languages have run time bounds checking that is enabled or disabled with a compiler switch. C# also supports unsafe regions: sections of code that (among other things) temporarily suspend bounds checking to raise efficiency. These are useful for speeding up small time-critical bottlenecks without sacrificing the safety of a whole program.
, as using a number outside of the upper range in an array may cause the program to crash, or may introduce security vulnerabilities (see buffer overflow
). In Java
, the interpreter automatically does a range-check when items in an array are accessed, and throws an exception
if the item is out of range.
indexing an array, first check the index value against the bounds of the array which were established when the array was defined, and should an index be out of bounds, further execution is suspended via some sort of error
.
Pascal, Fortran, Java have index checking ability. The VAX
computer has an INDEX assembly instruction for array index checking which takes six operands, all of which can use any VAX addressing mode. The B6500 and similar Burroughs computers performed bound checking via hardware, irrespective of which computer language had been compiled to produce the machine code.
Computer programming
Computer programming is the process of designing, writing, testing, debugging, and maintaining the source code of computer programs. This source code is written in one or more programming languages. The purpose of programming is to create a program that performs specific operations or exhibits a...
, bounds checking is any method of detecting whether a variable
Variable (programming)
In computer programming, a variable is a symbolic name given to some known or unknown quantity or information, for the purpose of allowing the name to be used independently of the information it represents...
is within some bounds before its use. It is particularly relevant to a variable used as an index
Index (information technology)
In computer science, an index can be:# an integer that identifies an array element# a data structure that enables sublinear-time lookup -Array element identifier:...
into an array to ensure its value lies within the bounds of the array. For example: a value of 32768 about to be assigned to a sixteen-bit signed integer variable (whose bounds are −32768 to +32767), or accessing element 25 on an array with index range 0 through 9 only. The first is also known as range checking, the second as index checking.
A failed bounds check usually results in the generation of some sort of exception
Exception handling
Exception handling is a programming language construct or computer hardware mechanism designed to handle the occurrence of exceptions, special conditions that change the normal flow of program execution....
signal.
Because performing bounds checking during every usage is time-consuming it is not always done. Bounds-checking elimination
Bounds-checking elimination
In computer science, bounds-checking elimination is a compiler optimization useful in programming languages or runtimes that enforce bounds checking, the practice of consistently checking every index into an array to verify that the index is within the defined valid range of indexes...
are compiler technologies that eliminate unneeded bounds checking in many common cases.
Many programming language
Programming language
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....
s, such as C
C (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
, never perform automatic bounds checking, to raise speed. However, this leaves uncaught many off-by-one error
Off-by-one error
An off-by-one error is a logical error involving the discrete equivalent of a boundary condition. It often occurs in computer programming when an iterative loop iterates one time too many or too few...
s and buffer overflow
Buffer overflow
In computer security and programming, a buffer overflow, or buffer overrun, is an anomaly where a program, while writing data to a buffer, overruns the buffer's boundary and overwrites adjacent memory. This is a special case of violation of memory safety....
s. Many programmers believe these languages sacrifice too much for rapid execution. In his 1980 Turing Award
Turing Award
The Turing Award, in full The ACM A.M. Turing Award, is an annual award given by the Association for Computing Machinery to "an individual selected for contributions of a technical nature made to the computing community. The contributions should be of lasting and major technical importance to the...
lecture, C. A. R. Hoare
C. A. R. Hoare
Sir Charles Antony Richard Hoare , commonly known as Tony Hoare or C. A. R. Hoare, is a British computer scientist best known for the development of Quicksort, one of the world's most widely used sorting algorithms...
described his experience in the design of ALGOL 60
ALGOL 60
ALGOL 60 is a member of the ALGOL family of computer programming languages. It gave rise to many other programming languages, including BCPL, B, Pascal, Simula, C, and many others. ALGOL 58 introduced code blocks and the begin and end pairs for delimiting them...
, a language that included bounds checking, saying:
A consequence of this principle is that every occurrence of every subscript of every subscripted variable was on every occasion checked at run time against both the upper and the lower declared bounds of the array. Many years later we asked our customers whether they wished us to provide an option to switch off these checks in the interest of efficiency on production runs. Unanimously, they urged us not to—they already knew how frequently subscript errors occur on production runs where failure to detect them could be disastrous. I note with fear and horror that even in 1980, language designers and users have not learned this lesson. In any respectable branch of engineering, failure to observe such elementary precautions would have long been against the law.
Mainstream languages that enforce run time checking include Ada
Ada (programming language)
Ada is a structured, statically typed, imperative, wide-spectrum, and object-oriented high-level computer programming language, extended from Pascal and other languages...
, C#, Haskell
Haskell (programming language)
Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
, Java
Java (programming language)
Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
, JavaScript
JavaScript
JavaScript is a prototype-based scripting language that is dynamic, weakly typed and has first-class functions. It is a multi-paradigm language, supporting object-oriented, imperative, and functional programming styles....
, Lisp, PHP
PHP
PHP is a general-purpose server-side scripting language originally designed for web development to produce dynamic web pages. For this purpose, PHP code is embedded into the HTML source document and interpreted by a web server with a PHP processor module, which generates the web page document...
, Python
Python (programming language)
Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
, Ruby
Ruby (programming language)
Ruby is a dynamic, reflective, general-purpose object-oriented programming language that combines syntax inspired by Perl with Smalltalk-like features. Ruby originated in Japan during the mid-1990s and was first developed and designed by Yukihiro "Matz" Matsumoto...
, and Visual Basic
Visual Basic
Visual Basic is the third-generation event-driven programming language and integrated development environment from Microsoft for its COM programming model...
. The D
D (programming language)
The D programming language is an object-oriented, imperative, multi-paradigm, system programming language created by Walter Bright of Digital Mars. It originated as a re-engineering of C++, but even though it is mainly influenced by that language, it is not a variant of C++...
and Objective Caml
Objective Caml
OCaml , originally known as Objective Caml, is the main implementation of the Caml programming language, created by Xavier Leroy, Jérôme Vouillon, Damien Doligez, Didier Rémy and others in 1996...
languages have run time bounds checking that is enabled or disabled with a compiler switch. C# also supports unsafe regions: sections of code that (among other things) temporarily suspend bounds checking to raise efficiency. These are useful for speeding up small time-critical bottlenecks without sacrificing the safety of a whole program.
Range checking
A range check is a check to make sure a number is within a certain range. This is often used with arraysArray data type
In computer science, an array type is a data type that is meant to describe a collection of elements , each selected by one or more indices that can be computed at run time by the program. Such a collection is usually called an array variable, array value, or simply array...
, as using a number outside of the upper range in an array may cause the program to crash, or may introduce security vulnerabilities (see buffer overflow
Buffer overflow
In computer security and programming, a buffer overflow, or buffer overrun, is an anomaly where a program, while writing data to a buffer, overruns the buffer's boundary and overwrites adjacent memory. This is a special case of violation of memory safety....
). In Java
Java (programming language)
Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
, the interpreter automatically does a range-check when items in an array are accessed, and throws an exception
Exception handling
Exception handling is a programming language construct or computer hardware mechanism designed to handle the occurrence of exceptions, special conditions that change the normal flow of program execution....
if the item is out of range.
Index checking
Index checking means that, in all expressionsExpression (programming)
An expression in a programming language is a combination of explicit values, constants, variables, operators, and functions that are interpreted according to the particular rules of precedence and of association for a particular programming language, which computes and then produces another value...
indexing an array, first check the index value against the bounds of the array which were established when the array was defined, and should an index be out of bounds, further execution is suspended via some sort of error
Error
The word error entails different meanings and usages relative to how it is conceptually applied. The concrete meaning of the Latin word "error" is "wandering" or "straying". Unlike an illusion, an error or a mistake can sometimes be dispelled through knowledge...
.
Pascal, Fortran, Java have index checking ability. The VAX
VAX
VAX was an instruction set architecture developed by Digital Equipment Corporation in the mid-1970s. A 32-bit complex instruction set computer ISA, it was designed to extend or replace DEC's various Programmed Data Processor ISAs...
computer has an INDEX assembly instruction for array index checking which takes six operands, all of which can use any VAX addressing mode. The B6500 and similar Burroughs computers performed bound checking via hardware, irrespective of which computer language had been compiled to produce the machine code.