First, make the crash boring

Every browser build had to face the same small test. Load the same page in a fresh profile, press the same key once, and record whether the renderer lived. That repeatable yes-or-no test is what an algorithm calls an oracle:

Fresh profiles removed extensions and accumulated browser state. Turning off GPU acceleration did not help. Neither did disabling field trials, variation-seed fetching, or component updates. I reproduced the crash three times; every dump showed the same renderer thread, fault address, and 36-frame unnamed stack.

None of this named the bug. It did something more modest and more useful: it made the competing explanations pay rent. The GPU and ordinary variation state no longer explained what I was seeing.

Ask the build in the middle

The known-good Beta build came from Chromium main-line position 1669021. The bad Canary came from 1671751. Between them sat 2,736 changes and one change, not yet identified, that turned good into bad. Reading every patch would turn a one-key crash into a cataloging project.

Binary search asks a cheaper question: what does the build in the middle do?

If the midpoint works, every older candidate can go. If it crashes, every newer candidate can go. One honest answer dismisses half the suspects. Starting with $n$ candidates, the list shrinks like this:

If that sounds unlike the binary search from a data-structures class, look past the nouns. There is no visible array and no number to look up, but the shape of the reasoning is the same:

You have probably used binary search without calling it binary search. Any time you ask “when did this start?” and jump halfway through an ordered history, you are doing the important part. The array is merely one place the pattern fits.

The essential promise is that the answers change direction only once. Read from oldest to newest, they must look like this:

good, good, good, ..., bad, bad, bad

The algorithm is not searching for “bad” in general. It is searching for the boundary between the last good candidate and the first bad one. If the same bug disappears and returns across the interval, or if the test changes its mind, a single boundary no longer describes the evidence.

FIRST-BAD-BUILD(B, ORACLE)
Input:  ordered builds B[1:n], reliable ORACLE
Output: least i with ORACLE(B[i]) = BAD, or NIL

low ← 1
high ← n
answer ← NIL
while low ≤ high
    mid ← low + ⌊(high - low) / 2⌋
    if ORACLE(B[mid]) = BAD
        answer ← mid
        high ← mid - 1
    else
        low ← mid + 1
return answer

The procedure records a bad midpoint before searching the older half because that midpoint may be the boundary. Its contract also exposes the assumption the investigation is about to violate: ORACLE must give reliable answers whose GOOD results all precede its BAD results.

The worst case is the base-two logarithm of $n$, rounded up. Before compressing that sentence into symbols, here is the whole refresher it needs:

The sentence now has a compact mathematical expression:

$$\lceil \log_2 n \rceil$$

For this interval, substitute the number of candidates:

$$\lceil \log_2 2736 \rceil = \lceil 11.42\ldots \rceil = 12$$

In plain terms, count how many times the remaining list can be halved before one candidate remains. Eleven halvings cover only 2,048 candidates; twelve cover up to 4,096. So twelve reliable answers are enough to reduce 2,736 changes to one.

Twelve is not just a clever upper bound. It is the best possible worst case for a reliable yes-or-no test. After one answer there are at most two distinguishable outcomes; after two, four; after $k$, at most $2^k$. To distinguish among $n$ possible boundaries, any method therefore needs enough answers that $2^k \ge n$. In other words, $k$ must be at least the base-two logarithm of $n$, rounded up. Binary search meets that lower bound by keeping the two remaining halves as even as possible.

That analysis counts decisions, not minutes. Downloading a browser, compiling a commit, or repeating a flaky test can dominate the clock. The algorithm spends the expensive resource carefully; it cannot make each experiment cheap.

python3 tools/bisect-builds.py -cft -a mac-arm \
  -g 1669021 -b 1671751 --verify-range

Then the bad build worked

Before choosing a midpoint, the tool opened the Chrome for Testing build at the supposedly bad position, 1671751. I loaded the page and pressed /.

The command window opened.

I tried a standalone Chrome for Testing build with the exact same 153.0.7983.3 version string as the crashing Canary. That worked too. The tool stopped before the first midpoint because there was nothing honest to bisect yet.

It was tempting to call the endpoint bad anyway and keep going. That would have made the script look busy while stripping the reasoning out of binary search. If “bad” passes, the next midpoint tells you nothing about which half to discard.

The contradiction exposed a hidden assumption: a version number is not the whole browser. Behavior also depends on the exact artifact, runtime state, and machine:

$$\text{behavior} = f(\text{source revision},\; \text{build artifact},\; \text{runtime state},\; \text{machine}) .$$

This is the browser-build form of the same lossiness described in You Don't Want Separate Repos: SemVer is a lossy hash of a diff the VCS already had. A browser version string compresses even more—the source, toolchain, build flags, packaging, and experiments. A commit hash identifies the source more precisely, but it still names only one input to the function above. A content hash can identify the exact artifact; reproducing that artifact requires the complete set of build inputs.

The main-line position orders only the source revision. It does not hold branded packaging, generated configuration, field trials, branch cherry-picks, or the machine constant. Two browsers can print 153.0.7983.3 and still contain meaningfully different experiments.

Binary search did not fail. It caught us asking it a question whose premises were false.

The crash left another clue

Bisection had reached a dead end, but each crash had left a note behind. Chrome's Crashpad directory contained three minidumps: compact snapshots of the renderer at the moment it died. Mozilla's Rust minidump tools found the same signature in all three—an EXC_BAD_ACCESS at address 0x2b on the renderer's main thread, with the same unnamed Chrome Framework stack.

A dSYM is a source map for native code. The crash dump gives you machine addresses; the dSYM translates them back into functions, files, and lines. Official macOS Chrome builds keep that debug information outside the shipped binary. Chromium's macOS debugging guide explains the arrangement, and its public tools/mac/download_symbols.py script fetches the symbols.

python3 tools/mac/download_symbols.py \
  --version 153.0.7983.3 --channel canary --arch arm64 \
  --out /path/to/symbols

dwarfdump --uuid "/path/to/Google Chrome Framework"
dwarfdump --uuid "/path/to/Google Chrome Framework.dSYM"
minidump-stackwalk crash.dmp > raw-stack.txt

There is one catch: the source map must belong to the exact binary that crashed. The binary and dSYM carry matching UUIDs. If those values differ, addresses may still turn into convincing function names—just not the right ones.

The downloaded dSYM and the installed Canary framework both carried UUID 4C4C4440-5555-3144-A11B-2D13053E4AC4. With that identity check satisfied, the anonymous addresses became this stack:

blink::AXObject::AncestorMenuList()
blink::AXObjectCacheImpl::GetActiveAriaModalDialog()
blink::AXObject::IsBlockedByAriaModalDialog()
blink::AXObject::ComputeIsInertViaStyle()
blink::AXObject::UpdateCachedAttributeValuesIfNeeded()
blink::AXNodeObject::InsertChild()

The stack overturned the visual hypothesis. The renderer was not dying in CSS animation or GPU composition. It was inside Blink's accessibility-tree code, inserting children beneath a modal dialog.

Public Chromium history supplied the next clue. Change 018ca90a, at position 1671058, had added checks to AXObjectCacheImpl::GetActiveAriaModalDialog(). The method looked like a simple question—“which modal dialog is active?”—but answering it called IsVisible(). That call tried to walk the accessibility tree while the first walk was still building it.

The next day, change ce2a6293, at position 1671982, fixed the problem in third_party/blink/renderer/modules/accessibility/ax_object_cache_impl.cc:

Element* AXObjectCacheImpl::GetActiveAriaModalDialog() const {
  return active_aria_modal_dialog_;
}

The fix made the getter a getter again. Validity maintenance moved into the document lifecycle, where tree changes belong, instead of letting a question start another walk through a half-built tree. The first tagged branch containing the fix was 153.0.7984.0.

Why we changed nothing

The website could have dodged the crash by removing its modal-dialog semantics. That would also have made the page less accurate to assistive technology. A temporary Canary bug would have left a permanent scar on the website.

We changed nothing.

The page was using a valid platform contract. The crash belonged to Blink's accessibility cache. Chromium had already merged the repair, and the next Canary branch contained it. The smallest correct fix was the one upstream had already made.

That is not a rule to wait blindly. A production crash affecting stable users, no deployable browser fix, or invalid application markup would change the decision. A narrow, removable compatibility shim can be responsible. The useful questions are who is affected, what correctness the workaround costs, and how soon the real fix arrives—not how quickly the workaround can be typed.

The same trick works elsewhere

The useful abstraction is not “look something up in an array.” It is “find the place where an ordered yes-or-no answer changes.” That includes the first release that supports an API, the first commit that fails a test, the smallest buffer that avoids a failure, the largest batch size that stays below a latency budget, or the earliest date on which a report changes. The question must remain stable and change only once across the chosen interval. If larger batches sometimes recover after failing, for example, there is no single threshold to bisect.

This was not my first browser bisection. I had used the same method to find the versions of Safari and Firefox where a Content Security Policy behavior changed. The symptom was different; the search was the same.

Under a CSP Level 3 'strict-dynamic' policy, WebKit blocked an external script even though the script's hash matched. The one-bit test became: does this fixed policy execute this integrity-matched script?

The public record includes WebKit bug 270784, the reproduction added to Web Platform Tests, the standards discussion in issue 653, and the live cross-browser results. Bisection located the compatibility boundaries: Firefox before 119 and Safari before 18.2 needed a nonce fallback instead of a hash-rooted policy.

The recipe was unchanged:

1. Write one small standards-level test.
2. Pin browser builds instead of trusting auto-update.
3. Find one version that passes and one that fails.
4. Test the middle until the two versions are adjacent.
5. Read the landing change and issue discussion before choosing a fallback.

Chrome for Testing exists because auto-update is good for users and awkward for reproducible experiments. Firefox and Safari use different archives, but binary search does not care. Give it comparable builds in order and one reliable question.

A crash regression and a support boundary can demand different product choices. One may justify a browser revert; the other may require a standards-compatible fallback. Bisection finds the boundary. It does not make that policy decision for you.

When the recipe gets stuck

Most failed bisections are failed experiments, not failed binary searches. These are the questions I would check first:

• I do not have a Chromium checkout. You do not need the whole source tree to begin. Chromium's bisection guide shows how to download the standalone script on macOS, Linux, or Windows and explains the supported platform names.
• The tool cannot find enough builds. Check chrome://version and make sure the endpoints are versions or main-line commit positions—not branch numbers. The same range guide explains the accepted forms and an important limit: trunk bisection cannot discover a change merged only into a release branch.
• The same build sometimes passes and sometimes fails. Do not force a flaky result into good or bad. The current script source documents -t / --times for repeating each build. If repetition does not produce a stable answer, narrow the test or treat the result as unknown before resuming the search.
• Installed Chrome and the downloaded build disagree. First compare the same artifact family. Chromium's guide notes that non-branded builds use a field- trial testing configuration. When that difference matters, pass the browser switch --disable-field-trial-config after the script's -- separator. This is exactly the class of mismatch --verify-range is meant to reveal.
• Browser automation cannot find a compatible driver. Use --chromedriver and the %d placeholder when the bisection tool can supply it. For manual selection, Chrome's version-selection guide explains how Chrome and ChromeDriver releases match, including the Chrome for Testing JSON endpoints.
• There is no dump, or the dump has only addresses. Start with Chromium's crash-report guide for the local Crashpad layout. Then follow Apple's symbolication guide: compare the binary, crash report, and dSYM UUIDs with dwarfdump before trusting any resolved frame.
• LLDB refuses to attach to official Chrome. That can be expected: official builds are code-signed to restrict debuggers. Read Chromium's macOS debugging guide before changing code signing or System Integrity Protection. Symbolicating an existing dump does not itself require weakening those protections.

Addendum: writing the search you just proved correct

Bisecting by hand needs no code. You read a revision range, pick a middle, and press a key. The reasoning is the whole method, and it cannot overflow.

Writing the same reasoning down is a different act. The proof used mathematical integers, an array that is merely long, and a comparison that always answers. The program gets fixed-width machine integers, a real allocator, and a comparator someone else wrote. Four cracks open between the two. Bloch's is the famous one; the other three are quieter and, in a corpus that keeps growing, more likely.

int mid_unsafe(int low, int high) { return (low + high) / 2; }
int mid_safe(int low, int high)   { return low + (high - low) / 2; }

func midUnsafe(low, high int32) int32 { return (low + high) / 2 }
func midSafe(low, high int32) int32   { return low + (high-low)/2 }

fn mid_unsafe(low: i32, high: i32) -> i32 { (low + high) / 2 }
fn mid_safe(low: i32, high: i32) -> i32 { low + (high - low) / 2 }

def mid_unsafe(low, high): return (low + high) // 2
def mid_safe(low, high):   return low + (high - low) // 2

const midFloat = (low: number, high: number): number =>
  Math.floor((low + high) / 2); // safe: never coerces
const midShift = (low: number, high: number): number =>
  (low + high) >>> 1; // unsafe: coerces the SUM through ToUint32
const midSafe = (low: number, high: number): number =>
  low + ((high - low) >>> 1);

while (low < high) {
  const mid = low + ((high - low) >>> 1);
  if (predicate(mid)) high = mid;
  else low = mid; // never terminates: with high - low === 1, mid === low
}

// Returns the FIRST index where the predicate holds, or `high` if none does.
// The invariant is that everything below `low` fails and everything at or
// above `high` is unknown — so the answer is `low` when they meet.
function firstWhere(
  low: number,
  high: number,
  predicate: (at: number) => boolean
): number {
  while (low < high) {
    const mid = low + ((high - low) >>> 1);
    if (predicate(mid)) high = mid; // mid may itself be the boundary: keep it
    else low = mid + 1; // mid fails, so the boundary is strictly above it
  }
  return low;
}

Lessons

• First make the failure repeatable enough to call each build good, bad, or unknown.
• Binary search finds one change among $n$ ordered candidates by repeatedly halving the remaining interval. It is a reusable shape of reasoning, not a trick that belongs only to arrays.
• A reliable yes-or-no answer carries at most one bit. That makes the base-two logarithm of $n$, rounded up, both sufficient and necessary in the worst case; for 2,736 candidates, the bound is twelve decisions.
• The clean mathematics still depends on machine and experimental premises: safe midpoint arithmetic, comparable candidates, a stable oracle, and one ordered transition.
• Test both ends before the middle. If the bad build passes, stop and find out what differs between the artifacts or environments.
• Treat a version string as a label, not a complete identity.
• Match a dSYM's UUID to the crashing binary before trusting the names in a stack.
• Let the evidence overturn the first theory. This visual crash came from the accessibility tree, not graphics.
• Debugging ends with an ownership decision. An upstream fix can make “change nothing downstream” the safest result.
• The same bisection method finds crashes, slowdowns, rendering changes, and browser support boundaries.
• Writing the search down adds cracks the reasoning does not have: a midpoint that wraps, a loop that never shrinks, a match that is not the boundary, and an ordering the array does not share. Three of the four fail silently.

Practice

References

1. Edsger W. Dijkstra. “Structured Programming (EWD 268).” 1969. — the epigraph's primary source and the larger argument about what tests can establish
2. Joshua Bloch. “Nearly All Binary Searches and Mergesorts are Broken.” Google Research, 2006. — the midpoint-overflow bug and the gap between mathematical integers and machine arithmetic
3. “git-bisect documentation.” Git. — manual classification, automated test commands, custom terms, skipped commits, and finding the first change in a commit graph
4. “Chrome for Testing: per-commit builds.” Chromium, 2025. — the announcement of per-commit Chrome for Testing builds
5. “Bisecting Chromium builds.” Chromium. — the public regression-bisection guide
6. “bisect-builds.py.” Chromium. — the public regression-bisection implementation
7. “Chrome for Testing: reliable downloads for browser automation.” Chrome Developers. — why pinned, non-auto-updating browser artifacts exist
8. “ChromeDriver version selection.” Chrome Developers. — matching an automated test driver to an exact Chrome or Chrome for Testing build
9. “Debugging Chromium on macOS.” Chromium. — LLDB, multiprocess debugging, official dSYMs, and symbolized traces
10. Apple. “Adding identifiable symbol names to a crash report.” — checking binary and dSYM UUIDs before resolving addresses
11. “Chromium change 018ca90a.” Chromium, 2026. — the change that introduced the accessibility-tree regression
12. “Chromium change ce2a6293.” Chromium, 2026. — the source-level repair
13. Mozilla. “Rust Minidump.” — Mozilla's cross-platform parser, processor, and stack walker
14. W3C. “Content Security Policy Level 3: strict-dynamic.” — the standard's trust-propagation model
15. “WebKit bug 270784.” WebKit. — the external-hash and strict-dynamic interoperability defect
16. “WPT pull request 44769.” Web Platform Tests. — the cross-browser regression test
17. “strict-dynamic hash-source results.” WPT. — live cross-browser results for the compatibility boundary
18. “Mozilla bug 1409200.” Mozilla. — a related historical boundary between strict-dynamic and external-script hashes
19. “ECMAScript: ToUint32 and ToInt32.” Ecma International. — why a JavaScript bitwise operator truncates its operand even though the arithmetic itself is exact
20. “Arithmetic operators: overflow.” cppreference. — signed integer overflow as undefined behavior in C
21. “The Go Programming Language Specification: integer overflow.” Go. — Go's defined wrapping behavior for signed integers
22. “The Rust Reference: overflow.” Rust. — panic on overflow in debug builds and two's complement wrapping in release
23. “Numeric types.” Python. — arbitrary-precision integers, which close the overflow crack entirely
24. Jay Abramson. “Logarithmic Functions.” OpenStax Precalculus 2e, 2021. — logarithms as the inverses of exponential functions
25. Eric W. Weisstein. “Ceiling Function.” MathWorld. — the least integer greater than or equal to a real number

Mangalapilly, Y. J. (2026, July). The Good, the Bad, and the Bugly. Saṃhitā Notes. https://yesudeep.com/blog/the-good-the-bad-and-the-bugly/

@online{mangalapilly2026the,
  author  = {Yesudeep Jose Mangalapilly},
  title   = {The Good, the Bad, and the Bugly},
  journal = {Sa\d{m}hit\=a Notes},
  year    = {2026},
  month   = {July},
  url     = {https://yesudeep.com/blog/the-good-the-bad-and-the-bugly/},
  urldate = {2026-08-01},
}

Yesudeep Jose Mangalapilly. “The Good, the Bad, and the Bugly.” Saṃhitā Notes, 2026. https://yesudeep.com/blog/the-good-the-bad-and-the-bugly/.

TY  - ELEC
AU  - Mangalapilly, Yesudeep Jose
TI  - The Good, the Bad, and the Bugly
T2  - Saṃhitā Notes
PY  - 2026
UR  - https://yesudeep.com/blog/the-good-the-bad-and-the-bugly/
Y2  - 2026-08-01
ER  -