Humble Pi: A Comedy of Maths Errors
by
Matt Parker
Published 7 Mar 2019
Counting from zero breaks the link between what you’ve counted to and what the total is. Counting from zero to fourteen is a total of fifteen. This type of mistake is so common that the programming community has a name for it: OBOE, or off-by-one errors. Named after the symptom and not the cause, most off-by-one errors come from the complications of convincing code to run for a set number of times or count a certain number of things. I’m obsessed with one specific species of off-by-one error: the fence-post problem. Which is the second weapon in Josh’s arsenal. This mistake is called the fence-post problem because it is quintessentially described using the metaphor of a fence: if a 50-metre stretch of fence has a post every 10 metres, how many fence posts are there?
…
So we cannot rule out the possibility that he was genuine. I’d like to believe he was. Troll or genuine: either way, TheJosh has taken a perfect stance, which is wrong yet supported by enough plausible misconceptions that it is possible to argue about it at length. Which he does, utilizing two classic maths mistakes: counting from zero and off-by-one errors. Counting from zero is a classic behaviour of programmers. Computer systems are often being used to their absolute limit, so programmers are sure not to waste a single bit. This means counting from zero instead of one. Zero is, after all, a perfectly good number. It’s like counting on your fingers, which is indeed the mascot of the easiest maths possible.
…
This is perfect fence-post-problem territory: something is alternating (escalator is used, escalator is refurbished, repeat) and it must begin and end with the same thing (escalator being used). If an escalator is refurbished twice, then it will be in use for three times as long compared to if it was never refurbished at all. The people who run the Tube forgot to mind the gap. Two refurbishments allow for three sections of use. Off-by-one errors also explain a struggle I always had with music theory. Moving along piano keys is measured in terms of the number of notes encompassed: hitting C on a piano, skipping D and then hitting E is an interval called a third, because E is the third note on the scale. But what really matters is not how many notes are used but the difference between them.
Code Complete (Developer Best Practices)
by
Steve McConnell
Published 8 Jun 2004
In the next example, the meaning of 0x1B isn't clear. The use of the ESCAPE constant makes the meaning more obvious. Example 12-4. C++ Examples of Comparisons Using Strings if ( input_char == 0x1B ) ... <-- 1 if ( input_char == ESCAPE ) ... <-- 2 (1)Bad! (2)Better! Watch for off-by-one errors. Because substrings can be indexed much as arrays are, watch for off-by-one errors that read or write past the end of a string. cc2e.com/1285 Know how your language and environment support Unicode. In some languages such as Java, all strings are Unicode. In others such as C and C++, handling Unicode strings requires its own set of functions.
…
Make sure that the rare cases don't obscure the normal path of execution. This is important for both readability and performance. Make sure that you branch correctly on equality. Using > instead of >= or < instead of <= is analogous to making an off-by-one error in accessing an array or computing a loop index. In a loop, think through the endpoints to avoid an off-by-one error. In a conditional statement, think through the equals case to avoid one. Put the normal case after the if rather than after the else. Put the case you normally expect to process first. This is in line with the general principle of putting code that results from a decision as close as possible to the decision.
…
For details, see Chapter 7. Check the routine's variables. Check for inaccurate variable names, unused objects, undeclared variables, improperly initialized objects, and so on. For details, see the chapters on using variables, Chapter 10 through Chapter 13. Check the routine's statements and logic. Check for off-by-one errors, infinite loops, improper nesting, and resource leaks. For details, see the chapters on statements, Chapter 14 through Chapter 19. Check the routine's layout. Make sure you've used white space to clarify the logical structure of the routine, expressions, and parameter lists. For details, see Chapter 31.
The Art of Software Security Assessment: Identifying and Preventing Software Vulnerabilities
by
Justin Schuh
Published 20 Nov 2006
When it’s possible to overflow a buffer by a fairly large amount, the attacker can copy over the entire stack, resulting in an exception when the stack base is overwritten. The application then uses the corrupted SEH information on the stack and jumps to an arbitrary address. This process is depicted in Figure 5-8. Figure 5-8. SEH exploit Off-by-One Errors Memory corruption is often caused by calculating the length of an array incorrectly. Among the most common mistakes are off-by-one errors, in which a length calculation is incorrect by one array element. This error is typically caused by failing to account for a terminator element or misunderstanding the way array indexing works. Consider the following example: ...
…
Off-by-one stack frame If the new base pointer points to some user-controllable data (such as a character buffer), users can then specify local variable values from the previous stack frame as well as the saved base pointer and return address. Therefore, when the calling function returns, an arbitrary return address might be specified, and total control over the program can be seized. Off-by-one errors can also be exploitable when the element is written out of bounds into another variable used by that function. The security implications of the off-by-one error in this situation depend on how the adjacent variable is used subsequent to the overflow. If the variable is an integer indicating size, it’s truncated, and the program could make incorrect calculations based on its value.
…
APPLICATION REVIEW PROCESS Introduction Overview of the Application Review Process Rationale Process Outline Preassessment Scoping Application Access Information Collection Application Review Avoid Drowning Iterative Process Initial Preparation Plan Work Reflect Documentation and Analysis Reporting and Remediation Support Code Navigation External Flow Sensitivity Tracing Direction Code-Auditing Strategies Code Comprehension Strategies Candidate Point Strategies Design Generalization Strategies Code-Auditing Tachniques Internal Flow Analysis Subsystem and Dependency Analysis Rereading Code Desk-Checking Test Cases Code Auditor’s Toolbox Source Code Navigators Debuggers Binary Navigation Tools Fuzz-Testing Tools Case Study: OpenSSH Preassessment Implementation Analysis High-Level Attack Vectors Documentation of Findings Summary II. Software Vulnerabilities 5. MEMORY CORRUPTION Introduction Buffer Overflows Process Memory Layout Stack Overflows Off-by-One Errors Heap Overflows Global and Static Data Overflows Shellcode Writing the Code Finding Your Code in Memory Protection Mechanisms Stack Cookies Heap Implementation Hardening Nonexecutable Stack and Heap Protection Address Space Layout Randomization SafeSEH Function Pointer Obfuscation Assessing Memory Corruption Impact Where Is the Buffer Located in Memory?
Practical Vim: Edit Text at the Speed of Thought
by
Drew Neil
Published 6 Oct 2012
As we’ll see throughout the rest of this chapter, Vim provides much quicker ways of moving around. You’re wasting keystrokes if you press the h key more than two times in a row. When it comes to moving horizontally, you can get around quicker using word-wise or character search motions (see Tip 48, and Tip 49). I use the h and l keys for off-by-one errors, when I narrowly miss my target. Apart from that, I hardly touch them. Given how little I use the h key, I’m happy to have to stretch for it on a Qwerty keyboard. On the flip side, I use the character search commands often (see Tip 49), so I’m pleased that the ; key rests comfortably beneath my little finger.
…
h This phrase takes time but eventually gets to the point. d This phrase gets to the point. To begin with, we press v to switch to Visual mode. Then we can extend the selection by searching for the short “ge” string, which puts the cursor where we want it in a single bound. Well, almost—we have an off-by-one error. The selection includes the “g” at the start of the word, but we don’t want to delete that. We’ll use h to back up one character. Then, having defined our selection, we’ll delete it with the d command. Here’s an even quicker way of doing the same thing: Keystrokes Buffer Contents {start} This phrase takes time but eventually gets to the point.
Practical Vim, Second Edition (for Stefano Alcazi)
by
Drew Neil
As we’ll see throughout the rest of this chapter, Vim provides much quicker ways of moving around. You’re wasting keystrokes if you press the h key more than two times in a row. When it comes to moving horizontally, you can get around quicker using word-wise or character search motions (see Tip 49, and Tip 50). I use the h and l keys for off-by-one errors, when I narrowly miss my target. Apart from that, I hardly touch them. Given how little I use the h key, I’m happy to have to stretch for it on a Qwerty keyboard. On the flip side, I use the character search commands often (see Tip 50), so I’m pleased that the ; key rests comfortably beneath my little finger.
…
h This phrase takes time but eventually gets to the point. d This phrase gets to the point. To begin with, we press v to switch to Visual mode. Then we can extend the selection by searching for the short “ge” string, which puts the cursor where we want it in a single bound. Well, almost—we have an off-by-one error. The selection includes the “g” at the start of the word, but we don’t want to delete that. We’ll use h to back up one character. Then, having defined our selection, we’ll delete it with the d command. Here’s an even quicker way of doing the same thing: KeystrokesBuffer Contents {start} This phrase takes time but eventually gets to the point.
Practical Vim
by
Drew Neil
As we’ll see throughout the rest of this chapter, Vim provides much quicker ways of moving around. You’re wasting keystrokes if you press the h key more than two times in a row. When it comes to moving horizontally, you can get around quicker using word-wise or character search motions (see Tip 49, and Tip 50). I use the h and l keys for off-by-one errors, when I narrowly miss my target. Apart from that, I hardly touch them. Given how little I use the h key, I’m happy to have to stretch for it on a Qwerty keyboard. On the flip side, I use the character search commands often (see Tip 50), so I’m pleased that the ; key rests comfortably beneath my little finger.
…
h This phrase takes time but eventually gets to the point. d This phrase gets to the point. To begin with, we press v to switch to Visual mode. Then we can extend the selection by searching for the short “ge” string, which puts the cursor where we want it in a single bound. Well, almost—we have an off-by-one error. The selection includes the “g” at the start of the word, but we don’t want to delete that. We’ll use h to back up one character. Then, having defined our selection, we’ll delete it with the d command. Here’s an even quicker way of doing the same thing: KeystrokesBuffer Contents {start} This phrase takes time but eventually gets to the point.
Smart and Gets Things Done: Joel Spolsky's Concise Guide to Finding the Best Technical Talent
by
Joel Spolsky
Published 1 Jun 2007
You may want to ask, “OK, so where’s the bug?” The quintessential Open-Ended Question From Hell. All programmers make mistakes, there’s nothing wrong with that, they just have to be able to find them. With string functions in C, most college kids forget to nullterminate the new string. With almost any function, they are likely to have off-by-one errors. They will forget semicolons sometimes. Their function won’t work correctly on 0 length strings, or it will GPF if malloc fails ... Very, very rarely, you will have a candidate write code that doesn’t have any bugs the first time. In this case, this question is even more fun. When you say, “There’s a bug in that code,” they will review their code carefully, and then you get a chance The Guerrilla Guide to Interviewing 113 to see if they’re rigorous in reasoning about their code, and if they’re diplomatic yet firm in asserting that the code is perfect.
Test-Driven Development With Python
by
Harry J. W. Percival
Published 10 Jun 2014
But, as we saw, those mitigations involve a fair bit of hard work on the part of the programmer—you need to remember to keep track of the interfaces between your units, to identify the implicit contract that each component needs to honour, and you need to write tests for those contracts as well as for the internal functionality of your unit. Unit Tests Seldom Catch Unexpected Bugs Unit tests will help you catch off-by-one errors and logic snafus, which are the kinds of bugs we know we introduce all the time, so in a way we are expecting them. But they don’t warn you about some of the more unexpected bugs. They won’t remind you when you forgot to create a database migration. They won’t tell you when the middleware layer is doing some clever HTML-entity escaping that’s interfering with the way your data is rendered … something like Donald Rumsfeld’s unknown unknowns?
…
The holy flow state! So where are we? Synthesis: What Do We Want from Our Tests, Anyway? Let’s step back and have a think about what benefits we want our tests to deliver. Why are we writing them in the first place? Correctness We want our application to be free of bugs—both low-level logic errors, like off-by-one errors, and high-level bugs like the software ultimately should deliver what our users want. We want to find out if we ever introduce regressions which break something that used to work, and we want to find that out before our users see something broken. We expect our tests to tell us our application is correct.
The Art of Readable Code
by
Dustin Boswell
and
Trevor Foucher
Published 14 Sep 2010
2 : 1); } else if (new_vote === 'Down') { score -= (old_vote === 'Up' ? 2 : 1); } else if (new_vote === '') { score += (old_vote === 'Up' ? -1 : 1); } } set_score(score); }; Even though the code is pretty short, it’s doing a lot. There are lots of intricate details, and it’s hard to tell at a glance whether there are any off-by-one errors, typos, or other bugs. The code may seem to be doing only one thing (updating the score), but there are actually two tasks being performed at once: old_vote and new_vote are being “parsed” into numerical values. score is being updated. We can make the code easier to read by solving each task separately.
Python Tricks: The Book
by
Dan Bader
Published 14 Oct 2017
Slicing uses the familiar “[]” indexing syntax with the following “[start:stop:step]” pattern: >>> lst = [1, 2, 3, 4, 5] >>> lst [1, 2, 3, 4, 5] # lst[start:end:step] >>> lst[1:3:1] [2, 3] Adding the [1:3:1] index returned a slice of the original list ranging from index 1 to index 2, with a step size of one element. To avoid off-by-one errors, it’s important to remember that the upper bound is always exclusive. This is why we got [2, 3] as the sublist from the [1:3:1] slice. If you leave out the step size, it defaults to one: >>> lst[1:3] [2, 3] You can do other interesting things with the step parameter, also called the stride.
Kill It With Fire: Manage Aging Computer Systems
by
Marianne Bellotti
Published 17 Mar 2021
Consider different ways of talking about the same project for different audiences. Some audiences will appreciate detailed planning, and other audiences will appreciate a high-level approach. Look for the following when you need to prune the number of big decisions that have to be made to move forward: Existing programs, projects, or technology These are the best off-by-one errors. Riding the coattails of an already approved solution removes the need to seek out those approvals yourself. Advantageous regulation You can eliminate a big decision by making it seem like it was already made, but you can also eliminate a big decision by making it seem like the organization doesn’t have a choice.
Functional Programming in Scala
by
Paul Chiusano
and
Rúnar Bjarnason
Published 13 Sep 2014
For one, it would be a shame to have to exhaustively generate all these values if we end up having to resort to random test case generation (and the full set of values may be huge or even infinite!). So let's use a Stream in place of List. We are going to use the Stream type we developed last chapter and also promote our type alias to a data type.5 Footnote 5mWe aren't using Scala's standard library streams here. They have an unfortunate "off-by-one" error—they strictly evaluate their first element. Generic code like what we are writing in this chapter can't assume it is desireable to evaluate any part of the stream until it is explicitly requested. case class Gen[+A](sample: State[RNG,A], exhaustive: Stream[A]) EXERCISE 5: Let's see what we can implement using this representation of Gen.
The Pragmatic Programmer
by
Andrew Hunt
and
Dave Thomas
Published 19 Oct 1999
Loop Invariants Getting the boundary conditions right on a nontrivial loop can be problematic. Loops are subject to the banana problem (I know how to spell "banana," but I don't know when to stop), fencepost errors (not knowing whether to count the fenceposts or the spaces between them), and the ubiquitous "off by one" error [URL 52]. Invariants can help in these situations: a loop invariant is a statement of the eventual goal of a loop, but is generalized so that it is also valid before the loop executes and on each iteration through the loop. You can think of it as a kind of miniature contract. The classic example is a routine that finds the maximum value in an array.
Practical C Programming, 3rd Edition
by
Steve Oualline
Published 15 Nov 2011
Read 80 symbols (dbx) run Running: search Enter number to search for or -1 to quit:5 ^C interrupt in main at line 70 in file "search.c" 70 low = middle; Now we can use the single-step command to step through our infinite loop, looking at key values along the way: 70 low = middle; (dbx)step stopped in main at line 57 in file "search.c" 57 middle = (low + high) / 2; (dbx) step stopped in main at line 59 in file "search.c" 59 if (data[middle] == search) { (dbx) print middle middle = 0 (dbx) print data[middle] data[middle] = 4 (dbx) print search search = 5 (dbx) step stopped in main at line 64 in file "search.c" 64 if (low == high) { (dbx) step stopped in main at line 69 in file "search.c" 69 if (data[middle] < search) (dbx) step stopped in main at line 70 in file "search.c" 70 low = middle; (dbx) step stopped in main at line 57 in file "search.c" 57 middle = (low + high) / 2; (dbx) step stopped in main at line 59 in file "search.c" 59 if (data[middle] == search) { (dbx) step stopped in main at line 64 in file "search.c" 64 if (low == high) { (dbx) step stopped in main at line 69 in file "search.c" 69 if (data[middle] < search) (dbx) step stopped in main at line 70 in file "search.c" 70 low = middle; (dbx) step stopped in main at line 57 in file "search.c" 57 middle = (low + high) / 2; (dbx) step stopped in main at line 59 in file "search.c" 59 if (data[middle] == search) { (dbx) step stopped in main at line 64 in file "search.c" 64 if (low == high) { (dbx) step stopped in main at line 69 in file "search.c" 69 if (data[middle] < search) (dbx) print low,middle,high low = 0 middle = 0 high = 1 (dbx) print search search = 5 (dbx) print data[0], data[1] data[0] = 4 data[1] = 6 (dbx)quit The problem is that we have reached a point where: low= 0 middle= 0 high= 1 The item we are seeking (value 5) falls between element (value 4) and element 1 (value 6). Our algorithm has an off-by-one error. This type of error occurs when one variable in a program is just one off the value it should have. In this case, the variable is our index middle. We have narrowed our search to the interval to 1. We then take the middle of this interval. But our algorithm is flawed. Because the interval is so small, the “middle” works out to be element 1.
Machine Learning for Hackers
by
Drew Conway
and
John Myles White
Published 10 Feb 2012
user.ego <- subgraph(user.net, c(0, neighbors(user.net, user, mode = "out"))) Warning One of the most frustrating “gotchas” of working with igraph is that igraph uses zero-indexing for nodes, whereas R begins indexing at one. In the 2-core example you’ll notice that we subtract one from the vector returned by the which function, lest we run into the dreaded “off by one” error. The second key subgraph we will extract is the seed’s ego-network. Recall that this is the subgraph induced by the seed’s neighbors. Thankfully, igraph has a useful neighbors convenience function for identifying these nodes. Again, however, we must be cognizant of Twitter’s directed graph structure.
Joel on Software
by
Joel Spolsky
Published 1 Aug 2004
The quintessential Open-Ended Question From Hell. All programmers make mistakes, and there's nothing wrong with that; they just have to be able to find them. With the string functions, most college kids forget to null-terminate the new string. With almost any function, they are likely to have off-by-one errors. They will forget semicolons sometimes. Their function won't work correctly on 0 length strings, or it will GPF if malloc fails, and so on. Very, very rarely, you will find a candidate who doesn't have any bugs the first time. In this case, this question is even more fun. When you say, "There's a bug in that code," they will review their code carefully, and then you get to see if they can be diplomatic yet firm in asserting that the code is perfect. 6.
Empire of the Sum: The Rise and Reign of the Pocket Calculator
by
Keith Houston
Published 22 Aug 2023
Frankston would write code all night, when the mainframe’s time was cheap, and Bricklin would pick up after class, where Frankston had left off.25 As frankston and bricklin perfected their program, Dan Fylstra set about selling it. There is an old joke that there are only two hard problems in software engineering: cache invalidation, naming things, and off-by-one errors. At some point along the way, in the early hours at a diner in Cambridge, Massachusetts, Frankston and Fylstra solved the second problem.26 That was when they settled on the name “VisiCalc” as a contraction of “visible calculator.” Which one of them came up with the name is still a matter of dispute, but putting a name to their unfinished program allowed Fylstra to start promoting it in earnest.27 Fylstra kicked off the VisiCalc marketing campaign with a cryptic advertisement in the May 1979 issue of Byte magazine.
Beautiful Testing: Leading Professionals Reveal How They Improve Software (Theory in Practice)
by
Adam Goucher
and
Tim Riley
Published 13 Oct 2009
One of the greatest advantages of Mudflap is the ability to detect out-of-object accesses, which can be perfectly legal from the memory point of view. Such a situation may occur when a program reads or writes to some object out of boundary without violating the memory itself but breaking the internal structure of another object. This kind of problem, often caused by off-by-one errors, can be very nasty and hard to debug, and the tools described earlier won’t detect them. Mudflap has already saved us a lot of time debugging these errors. 274 CHAPTER TWENTY Limitations Although there are very good memory debuggers, the common problem is that memory leaks may occur at very rare execution paths, which highly complicates their detection.
Producing Open Source Software: How to Run a Successful Free Software Project
by
Karl Fogel
Published 13 Oct 2005
But by then, the habit was so ingrained for the rest of us as to seem that it had been going on since time immemorial. Start doing reviews from very first commit. The sorts of problems that are easiest to catch by reviewing diffs are security vulnerabilities, memory leaks, insufficient comments or API documentation, off-by-one errors, caller/callee discipline mismatches, and other problems that require a minimum of surrounding context to spot. However, even larger-scale issues such as failure to abstract repeated patterns to a single location become spottable after one has been doing reviews regularly, because the memory of past diffs informs the review of present diffs.
Programming in Scala
by
Martin Odersky
,
Lex Spoon
and
Bill Venners
Published 15 Jan 2008
In other languages, you might use this facility to iterate through an array, like this: // Not common in Scala... for (i <- 0 to filesHere.length - 1) println(filesHere(i)) This for expression introduces a variable i, sets it in turn to each integer between 0 and filesHere.length - 1, and executes the body of the for expression for each setting of i. For each setting of i, the i’th element of filesHere is extracted and processed. The reason this kind of iteration is less common in Scala is that you can just as well iterate over the collection directly. If you do, your code becomes shorter and you sidestep many of the off-by-one errors that can arise when iterating through arrays. Should you start at 0 or 1? Should you add -1, +1, or nothing to the final index? Such questions are easily answered, but easily answered wrongly. It is safer to avoid such questions entirely. any type that has certain methods, in this case foreach, with appropriate signatures.
Programming Ruby 1.9: The Pragmatic Programmer's Guide
by
Dave Thomas
,
Chad Fowler
and
Andy Hunt
Published 15 Dec 2000
For example, Ruby doesn’t have a for loop—at least not the kind you’d find in C, C++, and Java. Instead, Ruby uses methods defined in various built-in classes to provide equivalent, but less error-prone, functionality. Let’s look at some examples: 3.times do print "Ho! " end produces: Ho! Ho! Ho! Report erratum L OOPS 162 It’s easy to avoid fence-post and off-by-one errors; this loop will execute three times, period. In addition to times, integers can loop over specific ranges by calling downto and upto, and all numbers can loop using step. For instance, a traditional “for” loop that runs from 0 to 9 (something like i=0; i < 10; i++) is written as follows: 0.upto(9) do |x| print x, " " end produces: 0 1 2 3 4 5 6 7 8 9 A loop from 0 to 12 by 3 can be written as follows: 0.step(12, 3) {|x| print x, " " } produces: 0 3 6 9 12 Similarly, iterating over arrays and other containers is easy if you use their each method: [ 1, 1, 2, 3, 5 ].each {|val| print val, " " } produces: 1 1 2 3 5 And once a class supports each, the additional methods in the Enumerable module (documented beginning on page 487 and summarized on page 100) become available.