Off-by-one error
An off-by-one error (OBOE) 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. Usually this problem arises when a programmer fails to take into account that a sequence starts at zero rather than one (as with array indices in many languages), or makes mistakes such as using "is less than or equal to" where "is less than" should have been used in a comparison. This can also occur in a mathematical context.
Looping over arrays
Consider an array of items, and items m through n are to be processed. How many items are there? An intuitive answer may be n−m, but that is off by one, exhibiting a fencepost error; the correct answer is n−m+1.
For this reason, ranges in computing are often represented by half-open intervals; the range from m to n (inclusive) is represented by the range from m (inclusive) to n+1 (exclusive) to avoid fencepost errors. For example, a loop that iterates five times can be written as a half-open interval from 0 to 5:
for (i = 0; i < 5; i++) {
/* Body of the loop */
}
The loop body is executed first of all with i equal to 0; i then becomes 1, 2, 3, and finally 4 on successive iterations. At that point, i becomes 5, so i < 5 is false and the loop ends. However, if the comparison used were <= (less than or equal to), the loop would be repeated six times: i takes the values 0, 1, 2, 3, 4, and 5. Likewise, if i were initialized to 1 rather than 0, there would only be four iterations: i takes the values 1, 2, 3, and 4. Both of these alternatives can cause off-by-one errors.
Another such error can occur if a do-while loop is used in place of a while loop (or vice versa.) A do-while loop is guaranteed to run at least once.
Array-related confusion may also result from differences in programming languages. Numbering from 0 is most common, but some languages start array numbering with 1. Pascal has arrays with user-defined indices. This makes it possible to model the array indices after the problem domain.
Fencepost error
A fencepost error (occasionally called a "telegraph pole" or "lamp-post" error) is a specific type of off-by-one error. The following problem illustrates the error:
- If you build a fence 100 feet (30 m) long with posts 10 feet (3.0 m) apart, how many posts do you need?
A common intuition is to divide 100 by 10 and thus answer 10. This is incorrect; the fence has 10 sections, but it has 11 posts.
"Fencepost error" can also, rarely, refer to an error induced by unexpected regularities in input values, which can (for instance) completely thwart a theoretically efficient binary tree or hash function implementation. The error here involves the difference between expected and worst case behaviours of an algorithm.
Security implications
A common off-by-one error which results in a security related bug is caused by misuse of the libc strncat routine. A common misconception with strncat is that the guaranteed null termination will not write beyond the maximum length. In reality it will write a terminating null character one byte beyond the maximum length specified. The following code contains such a bug:
void foo (char *s) {
char buf[15];
memset(buf, 0, sizeof(buf));
strncat(buf, s, sizeof(buf)); // Final parameter should be: sizeof(buf)-1
return;
}
On some systems (little endian architectures in particular) this can result in the overwriting of the least significant byte of the frame pointer. This can cause an exploitable condition where an attacker can hijack the local variables for the calling routine.
Well-Known Cases
A well-publicized problem with the Internet's DNS, based on a program called bind, was found to be caused by an off-by-one error.
Quoting from Slashdot:
"As it turns out, it appears to be a simple off-by-one error in BIND, which favors new NS records over cached ones (even if the cached TTL is not yet expired)." http://it.slashdot.org/article.pl?sid=08/08/29/127210
See also
References
- An earlier version of this article was based on fencepost error at FOLDOC, used with permission.