Alan Myrvold's Favorite Bug

I get excited about bugs, especially ones that I learn from.
 
Years ago, I was testing some data mining software at a commercial software company. This was cool, since I majored in statistics at university, not computer science, so at last a chance to use my schooling. The software read data from a number of sources, including .CSV files. I noticed that for some medium-size files, it took a bit longer than I expected to read in the file. I logged a bug and moved on to more testing.
 
Stephan, the lead developer, was amazing to work with. He was a great software architect, careful coder, took feedback with grace, and was respected by testers. He looked at my bug, looked at the code, and insisted that the code, which was written by a 3rd party, looked right. When reading data in, the program placed data in a red-black tree, which I learned from Stephan is a data structure that keeps a binary tree roughly balanced for efficiency. I kept asking questions about how it worked, and Stephan loaned me his copy of Introduction to Algorithms, by Cormen et al.
 
The program still didn't seem right. I did performance tests with files that were in sorted, random, and reverse order, and found that the time for the same file could differ by 1000x. I debugged the code as data was read in. I didn't have access to source code, so I was looking at the disassembly and tracing the data through. On a sheet of paper I carefully drew the tree that was built as data was read in, and noticed that it violated the requirements of a red-black tree. I asked for source code access, and was able to confirm the problem, even though the source code did look right. I wrote an implementation of the algorithm that was correct, and, after careful code review by Stephan, was allowed to check my changes in.
 
I ended up learning that:

• Peripheral vision during manual testing can find bugs that would otherwise be missed.
• It is possible to debug without source code, although a bit harder.
• Even code that looks right can be wrong.
• Knowledge of computer science can help testers.

-- Alan Myrvold, Microsoft

 

Do you have a bug whose story you love to tell? Let me know!