The Midpoint That Overflowed

Medium

· Backend

Incident

SEV-3

Time to fix: 20 min

Failing checks on the shipped build

  • huge endpoints do not overflow

    expected 2050000000 but got -97483648

How to work this incident

  1. Read the report: write down the expected behaviour and the actual one in a sentence each.
  2. Reproduce it: run the visible tests and find the failing check that matches the report.
  3. Read the logs and the failing checks for the first value that is wrong — the earliest wrong value is nearer the cause than the loudest error.
  4. Follow the request through the handler, the validation and the service it calls; find the first step whose output disagrees with the report.
  5. Fix the cause rather than the symptom, run the visible tests again, and submit against the hidden ones — then write the root cause down.

Inspired by

The JDK itself

Inspired by the bug that lived in the JDK's own Arrays.binarySearch for nine years: (low + high) / 2 overflows when the endpoints are large, producing a negative midpoint. Joshua Bloch called it "nearly impossible to test for" — unless you test the midpoint itself.

Search.java exposes its midpoint helper. Make it overflow-proof.

Code map

class Search {
    static int midpoint(int low, int high) {
        return (low + high) / 2;
    }

    static int indexOf(int[] sorted, int target) {
        int lo = 0, hi = sorted.length - 1;
        while (lo <= hi) {
            int mid = midpoint(lo, hi);
            if (sorted[mid] == target) return mid;
            if (sorted[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return -1;
    }
}

Sign in to edit the file, run the tests and submit a fix

A free account — no card, no trial clock. You come straight back here.

The Midpoint That Overflowed — Java Bug Hunt

Inspired by the bug that lived in the JDK's own Arrays.binarySearch for nine years: (low + high) / 2 overflows when the endpoints are large, producing a…

  • Language: Java
  • Layer: Backend
  • Difficulty: Medium
  • Concepts: Overflow, Algorithms
  • Modelled on: The JDK itself
  • Visible tests: huge endpoints do not overflow; small midpoints floor correctly; binary search still finds its targets
  • Reward: 50 XP for a complete fix

Incident

  • Severity: SEV-3
  • Time to fix: 20 minutes, the target for a medium incident

Failing checks on the shipped build

  • huge endpoints do not overflow — expected 2050000000 but got -97483648

How to work this incident

  1. Read the report: write down the expected behaviour and the actual one in a sentence each.
  2. Reproduce it: run the visible tests and find the failing check that matches the report.
  3. Read the logs and the failing checks for the first value that is wrong — the earliest wrong value is nearer the cause than the loudest error.
  4. Follow the request through the handler, the validation and the service it calls; find the first step whose output disagrees with the report.
  5. Fix the cause rather than the symptom, run the visible tests again, and submit against the hidden ones — then write the root cause down.

Briefing

Inspired by the bug that lived in the JDK's own Arrays.binarySearch for nine years: (low + high) / 2 overflows when the endpoints are large, producing a negative midpoint. Joshua Bloch called it "nearly impossible to test for" — unless you test the midpoint itself.

Search.java exposes its midpoint helper. Make it overflow-proof.

Bug report

BUG-JDK5045582 · Reported by: platform (with a famous blog post attached)

midpoint(low, high), both non-negative, low <= high:

  • must equal the true mathematical midpoint, floored
  • for low=2_000_000_000, high=2_100_000_000 the answer is 2_050_000_000

Observed: that call returns a negative number, and binary search dies with ArrayIndexOutOfBoundsException on gigantic collections.

Logs

[search] midpoint(2000000000, 2100000000) = -97483648

The code as shipped

Search.java (editable)

class Search {
    static int midpoint(int low, int high) {
        return (low + high) / 2;
    }

    static int indexOf(int[] sorted, int target) {
        int lo = 0, hi = sorted.length - 1;
        while (lo <= hi) {
            int mid = midpoint(lo, hi);
            if (sorted[mid] == target) return mid;
            if (sorted[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return -1;
    }
}

Open the hunt to start the incident clock, edit the files, run the visible tests and submit against the hidden ones, then write the root cause down. More Java bug hunts.