Bounds checking | EPFL Graph Search

Are you an EPFL student looking for a semester project?

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

In computer programming, bounds checking is any method of detecting whether a variable is within some bounds before it is used. It is usually used to ensure that a number fits into a given type (range checking), or that a variable being used as an array index is within the bounds of the array (index checking). A failed bounds check usually results in the generation of some sort of exception signal. As performing bounds checking during each use can be time-consuming, it is not always done. Bounds-checking elimination is a compiler optimization technique that eliminates unneeded bounds checking. A range check is a check to make sure a number is within a certain range; for example, to ensure that a value about to be assigned to a 16-bit integer is within the capacity of a 16-bit integer (i.e. checking against wrap-around). This is not quite the same as type checking. Other range checks may be more restrictive; for example, a variable to hold the number of a calendar month may be declared to accept only the range 1 to 12. Index checking means that, in all expressions indexing an array, the index value is checked against the bounds of the array (which were established when the array was defined), and if the index is out-of-bounds, further execution is suspended via some sort of error. Because reading or especially writing a value outside the bounds of an array may cause the program to malfunction or crash or enable security vulnerabilities (see buffer overflow), index checking is a part of many high-level languages. Early compiled programming languages with index checking ability included ALGOL 60, ALGOL 68 and Pascal, as well as interpreted programming languages such as BASIC. Many programming languages, such as C, never perform automatic bounds checking to raise speed. However, this leaves many off-by-one errors and buffer overflows uncaught. Many programmers believe these languages sacrifice too much for rapid execution. In his 1980 Turing Award lecture, C. A. R.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (4)

Related people (2)

Related units (1)

Related concepts (35)

Related courses (7)

Related lectures (88)

Related MOOCs (15)

A Type-and-Effect System for Object Initialization

Martin Odersky, Fengyun Liu, Paolo Giosuè Giarrusso, Ondrej Lhoták

Every newly created object goes through several initialization states: starting from a state where all fields are uninitialized until all of them are assigned. Any operation on the object during its initialization process, which usually happens in the constructor via \emph{this}, has to observe the initialization states of the object for correctness, i.e.~only initialized fields may be used. Checking safe usage of \emph{this} statically, without manual annotation of initialization states in source code, is a challenge, due to aliasing and virtual method calls on \emph{this}. Mainstream languages either do not check initialization errors, like Java, C++, Scala, or they defend against them by not supporting useful initialization patterns, such as Swift. In parallel, past research has shown that safe initialization can be achieved for varying degrees of expressiveness but by sacrificing syntactic simplicity. We approach the problem by upholding \emph{local reasoning} of initialization which avoids whole-program analysis, and we achieve \emph{typestate polymorphism} via subtyping. On this basis, we put forward a novel type-and-effect system that can effectively ensure initialization safety while allowing flexible initialization patterns with almost zero annotation burden.

2020

Safe Initialization of Objects

Martin Odersky, Fengyun Liu, Paolo Giosuè Giarrusso, Ondrej Lhoták

Every newly created object goes through several initialization states: starting from a state where all fields are uninitialized until all of them are assigned. Any operation on the object during its initialization process, which usually happens in the constructor via \emph{this}, has to observe the initialization states of the object for correctness, i.e.~only initialized fields may be used. Checking safe usage of \emph{this} statically, without manual annotation of initialization states in the source code, is a challenge, due to aliasing and virtual method calls on \emph{this}. Mainstream languages either do not check initialization errors, like Java, C++, Scala, or they defend against them by not supporting useful initialization patterns, such as Swift. In parallel, past research has shown that safe initialization can be achieved for varying degrees of expressiveness but by sacrificing syntactic simplicity. We approach the problem by upholding \emph{local reasoning} about initialization which avoids whole-program analysis, and we achieve \emph{typestate polymorphism} via subtyping. On this basis, we put forward a novel type-and-effect system that can effectively ensure initialization safety while allowing flexible initialization patterns. We implement an initialization checker in the Scala 3 compiler and evaluate on several real-world projects.

2020

A Type-and-Effect System for Object Initialization

Martin Odersky, Fengyun Liu, Paolo Giosuè Giarrusso, Ondrej Lhoták

Every newly created object goes through several initialization states: starting from a state where all fields are uninitialized until all of them are assigned. Any operation on the object during its initialization process, which usually happens in the constructor via this, has to observe the initialization states of the object for correctness, i.e. only initialized fields may be used. Checking safe usage of this statically, without manual annotation of initialization states in the source code, is a challenge, due to abasing and virtual method calls on this. Mainstream languages either do not check initialization errors, such as Java, C++, Scala, or they defend against them by not supporting useful initialization patterns, such as Swift. In parallel, past research has shown that safe initialization can be achieved for varying degrees of expressiveness but by sacrificing syntactic simplicity. We approach the problem by upholding local reasoning about initialization which avoids whole-program analysis, and we achieve typestate polymorphism via subtyping. On this basis, we put forward a novel type-and-effect system that can effectively ensure initialization safety while allowing flexible initialization patterns. We implement an initialization checker in the Scala 3 compiler and evaluate on several real-world projects.

ASSOC COMPUTING MACHINERY2020

Bounds checking

Rust (programming language)

Rust is a multi-paradigm, general-purpose programming language that emphasizes performance, type safety, and concurrency. It enforces memory safety—ensuring that all references point to valid memory—without requiring the use of a garbage collector or reference counting present in other memory-safe languages. To simultaneously enforce memory safety and prevent data races, its "borrow checker" tracks the object lifetime of all references in a program during compilation.

Cyclone (programming language)

The Cyclone programming language is intended to be a safe dialect of the C language. Cyclone is designed to avoid buffer overflows and other vulnerabilities that are possible in C programs, without losing the power and convenience of C as a tool for system programming. Cyclone development was started as a joint project of AT&T Labs Research and Greg Morrisett's group at Cornell University in 2001. Version 1.0 was released on May 8, 2006. Cyclone attempts to avoid some of the common pitfalls of C, while still maintaining its look and performance.

Parallelism and Concurrency

(merge of parprog1, scala-reactive, scala-spark-big-data)

Functional Programming

In this course you will discover the elements of the functional programming style and learn how to apply them usefully in your daily programming tasks. You will also develop a solid foundation for rea

Functional Programming Principles in Scala [retired]

This advanced undergraduate programming course covers the principles of functional programming using Scala, including the use of functions as values, recursion, immutability, pattern matching, higher-

CS-320: Computer language processing

We teach the fundamental aspects of analyzing and interpreting computer languages, including the techniques to build compilers. You will build a working compiler from an elegant functional language in

ME-437: Advanced solid mechanics

MATH-106(f): Analysis II

Étudier les concepts fondamentaux d'analyse et le calcul différentiel et intégral des fonctions réelles de plusieurs variables.

Software Security: Security Testing - Sanitizers COM-301: Computer security and privacy

Explores the use of sanitizers in software security testing to detect bugs early and improve testing effectiveness.

Structures: Examination of Supporting Structure

Covers the examination and reinforcement of supporting structures in buildings.

Type Checking in Compiler Frontend CS-320: Computer language processing

Covers the implementation of a type checker in the compiler frontend.