An off-by-one error or off-by-one bug is a logic 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. This problem could arise when a programmer makes mistakes such as using "is less than or equal to" where "is less than" should have been used in a comparison, or fails to take into account that a sequence starts at zero rather than one. 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 + 1. For this reason, ranges in computing are often represented by half-open intervals; the range from m to n is represented by the range from m to n + 1 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
The loop body is executed first of all with indexequal to 0; i then becomes 1, 2, 3, and finally 4 on successive iterations. At that point, index becomes 5, so index < 5 is false and the loop ends. However, if the comparison used were <=, the loop would be carried out six times: index takes the values 0, 1, 2, 3, 4, and 5. Likewise, if index were initialized to 1 rather than 0, there would only be four iterations: index 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 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 is a specific type of off-by-one error. An early description of this error appears in the works of Vitruvius. The following problem illustrates the error: The naive answer 10 is wrong. The fence has 10 sections, but 11 posts. The reverse error occurs when the number of posts is known and the number of sections is assumed to be the same. The actual number of sections is one fewer than the number of posts. More generally, the problem can be stated as follows: The correct answer may be if the line of posts is open-ended, n if they form a loop, or if the posts do not occur at the end of the fence. The precise problem definition must be carefully considered, as the setup for one situation may give the wrong answer for other situations. Fencepost errors come from counting things rather than the spaces between them, or vice versa, or by neglecting to consider whether one should count one or both ends of a row. Fencepost errors can also occur in units other than length. For example, the Time Pyramid, consisting of 120 blocks placed at 10-year intervals between blocks, is scheduled to take 1,190 years to build, from the installation of the first block to the last block. One of the earliest fencepost errors involved time, where the Julian calendar originally calculated leap years incorrectly, due to counting inclusively rather than exclusively, yielding a leap year every three years rather than every four. "Fencepost error" can, in rare occasions, refer to an error induced by unexpected regularities in input values, which can completely thwart a theoretically efficient binary tree or hash function implementation. This error involves the difference between expected and worst case behaviours of an algorithm. In larger numbers, being off by one is often not a major issue. In smaller numbers, however, and specific cases where accuracy is paramount committing an off-by-one error can be disastrous. Sometimes such an issue will also be repeated and, therefore, worsened, by someone passing on an incorrect calculation if the following person makes the same kind of mistake again. An example of this error can occur in the computational language MATLAB with the linspacelinear interpolation function, whose parameters are and not . A programmer who misunderstands the third parameter to be the number of increments might hope that linspace would achieve a sequence but instead would get.
Security implications
A common off-by-one error which results in a security-related bug is caused by misuse of the C standard librarystrncat 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
Off-by-one errors are common in using the C library because it is not consistent with respect to whether one needs to subtract 1 byte – functions like fgets and strncpy will never write past the length given them subtracts 1 itself, and only retrieves, whereas others, like strncat will write past the length given them. So the programmer has to remember for which functions they need to subtract 1. On some systems 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. One approach that often helps avoid such problems is to use variants of these functions that calculate how much to write based on the total length of the buffer, rather than the maximum number of characters to write. Such functions include strlcat and strlcpy, and are often considered "safer" because they make it easier to avoid accidentally writing past the end of a buffer.
