4 ms·

There was a rare race condition [1] bug in the linux kernel, and they didn't know precisely where it was introduced (which made it difficult to know what to cha

There was a rare race condition [1] bug in the linux kernel, and they didn't know precisely where it was introduced (which made it difficult to know what to change to fix it). They knew it was introduced at some point between two versions, but there were 52,363 code changes between those two versions. Because the bug was rare, you would have to test any given code change multiple times (thousands of times, in their case) to be confident that the bug was still present (if working backwards), or still absent (if working forwards). A way to do that faster is a binary search [2], or commit bisection. Basically, you know commit 0 is fine, and change 52,363 is bad, so you run 1000 tests on change 26,180 to cut in half the number of commits that could have introduced the problem. If the bug is still there, then you run 1000 tests on change 13,090; if the bug is not in change 26,180, then you run 1000 tests on change 39,270. Eventually (after 15 or 16 iterations) you'll narrow down the problem to a single change which introduced the problem. Unfortunately code is complicated, so the first time they ran that procedure, their tests didn't find the right bug, so they did it again but slightly differently. (many details omitted for simplicity) [1] https://en.wikipedia.org/wiki/Race_condition https://en.wikipedia.org/wiki/Race_condition [2] https://en.wikipedia.org/wiki/Binary_search_algorithm https://en.wikipedia.org/wiki/Binary_search_algorithm?

sh34r 3y ago
It's worth mentioning that this generalized problem in user space can often be solved much more easily using concurrent fuzz testing (ex: https://www.microsoft.com/en-us/research/project/cuzz-concurrency-fuzzing/ https://www.microsoft.com/en-us/research/project/cuzz-concur...). Unfortunately, when the problem is in kernel boot software, that is not a practical solution for obvious reasons, and you're left using more basic techniques like running a binary search on the commit history.
ufo 3y ago
Furthermore, in this case there were actually two commits related to the bug. An older commit that introduced the race condition, and a second commit that triggered it (by subtly changing how long a certain function took to run). The long bisection process identified the second commit but it took further work to identify the true cause of the bug.

sh34r 3y ago

It's worth mentioning that this generalized problem in user space can often be solved much more easily using concurrent fuzz testing (ex: https://www.microsoft.com/en-us/research/project/cuzz-concurrency-fuzzing/ https://www.microsoft.com/en-us/research/project/cuzz-concur...). Unfortunately, when the problem is in kernel boot software, that is not a practical solution for obvious reasons, and you're left using more basic techniques like running a binary search on the commit history.

ufo 3y ago

Furthermore, in this case there were actually two commits related to the bug. An older commit that introduced the race condition, and a second commit that triggered it (by subtly changing how long a certain function took to run). The long bisection process identified the second commit but it took further work to identify the true cause of the bug.