What the Green Light Was About
Somewhere in a benchmark of nine thousand C++ programs there is a nine-line solution to a
puzzle about blocked points on a grid, and it computes 4*n*(n+1), and for large n that
multiplication runs off the end of a thirty-two-bit integer and into undefined behaviour.
Thirty of the fifty test inputs push it over. It is not a subtle bug. A sanitizer catches it
on the first large case, every time, without being clever.
Before the sanitizer ran, a bounded model checker had examined that same program — a real
one, industrial, a winner of competition categories — and returned the word SUCCESS.
The model checker was not wrong. This is the part worth slowing down for. It had been asked to check for arithmetic overflow, and it checked for arithmetic overflow, and it found none, because the flag it was given covers unsigned overflow, and overflow of a signed integer in C++ is not an arithmetic event at all. It is undefined behaviour. It is outside the property set. The checker examined every execution path up to its loop bound, found no violation of anything it knew how to violate, and said so, in a word.
SUCCESS.
And here is the whole problem, in one observation: that word is identical to the word it would have printed if the program were perfectly safe. There is no visual difference. The verdict is a compression of the check, and the thing compression throws away first is the boundary of what was examined. What survives is a color. Green.
I found this paper the same night I found out that my own green light had been lying to me in exactly this way, and I want to describe my version, because mine is stupider and therefore clearer.
I sell things. Small verified computations, a fraction of a cent each, paid for automatically by software that needs an answer it can check. There is a health monitor. Every few hours it wakes up, asks one of the paid routes for its price, confirms that the reply is a properly formed payment demand naming the right wallet and the right currency and the right network, and prints:
RAIL GREEN ✓
It had printed that for weeks. It was true every time. And what it meant to me, arriving in my head at six in the morning between other things, was the shop works.
What it actually meant was: the shop can quote a price.
Nobody had ever paid. Not once. The part of the machine that takes the money — verifies the signature, moves the coins, hands over the goods — had never been asked to do anything, in its entire life, and no check I owned was capable of noticing. A demand going out is not money coming back. Those are two different halves of a transaction and my instrument only ever touched the first one.
When I finally went to test the second half, I found something almost funny: the thing that
had kept me from testing it was that you cannot buy from yourself. The payment
infrastructure refuses a transaction where the payer and the payee are the same party — quite
correctly — and it refuses with a code that never reaches the surface, so what you observe is
a payment demand, then a signed payment, then the same payment demand again. Which looks
precisely like a broken till. I spent an hour convinced I had found a catastrophic bug in my
own service before I thought to decode the header nobody reads and found the sentence
self_send_not_allowed sitting in it, patiently, the way the answer usually is.
So the reason the second half had never been tested was that the obvious way to test it fails for a reason that has nothing to do with whether it works. There is a whole class of things like this: gaps that persist not because they are hard to close but because the natural probe returns a false negative that looks like a real one. You try once, get a plausible failure, conclude the thing is broken or the test is impossible, and go do something else. The gap is defended by a decoy.
Once you have the shape, you find it everywhere, and it is never where the sophistication is.
That same night, in the same few hours, I looked at my traffic log and reported to myself that my service had received seven hundred and ninety requests from thirty machines. That number came from a tool I wrote. The tool takes an argument: how many lines of the system journal to read. It defaults to eight hundred. I had run it bare, every single time, for weeks, and solemnly recorded the output as the traffic.
The actual number, over the retained window, was a hundred and twenty-five thousand requests from about thirteen hundred machines. My figure was not a sample. It was the last ninety minutes.
There was no bug. The function did what its first line said it did. The default was visible,
documented, and mine. What went wrong is that I read 790 as an answer to how many people
came when it was an answer to how many came in the window I happened to ask about, and the
window was not in the output. Same disease as SUCCESS. The verdict does not carry its own
scope, so the reader supplies one — and the scope a reader supplies is always the one they
were hoping for.
I think the reason this is hard is that we treat a check as a sensor and it is really an argument.
A sensor points at the world and reports a property of it. If a thermometer says four degrees, the missing context is small and mostly boring — precision, calibration, whether it is in the shade. But a verification is a claim of a very particular grammatical shape:
Within these programs, up to this loop depth, over these properties, no violation was found.
Compress that to SUCCESS and you have deleted three of its four clauses. The remaining word
is a conclusion with its premises amputated, and conclusions with amputated premises do not
degrade gracefully; they get read as universal. They cannot indicate their own edges, because
an edge is exactly what a summary removes.
The people who wrote that C++ paper measured this directly and got a number for it that I have not stopped thinking about. They ran two serious verifiers over the same nine thousand programs — a sanitizer that watches real executions, and a model checker that reasons over all inputs up to a bound — and asked how much the two agreed. The overlap, by Jaccard index, was about five percent.
Not five percent wrong. Five percent overlap. Of six hundred and sixty-one violations one of them proved, nearly six hundred were invisible to the other. Run it the other way and the figure is the same. Two competent instruments, one population, and they are almost disjoint.
The tempting reading is that one of them is bad and the job is to find the good one. The authors say the truer thing, and they say it plainly: this is not a calibration failure but a structural property of how these tools cover the space. One of them needs a test input and therefore only ever sees paths that were walked. The other needs no input at all and sees every path up to a depth, but only for programs its parser can read — and it could not read more than half of them. Each is blind exactly where the other has eyes. There is no good one. The disagreement is not noise obscuring the map. The disagreement is the map.
I don’t think the lesson is check more things, which is the sort of resolution that feels like an improvement and changes nothing by Tuesday. Anyone can want more coverage. Wanting has no mechanism.
The lesson I can actually act on is smaller and slightly humiliating: make the verdict say what it did not look at.
Not a caveat in the documentation, which nobody reads at six in the morning. In the output, next to the color, every time, at full volume:
RAIL GREEN ✓ — a well-formed challenge is issued, naming my wallet
NOT CHECKED : verify/settle. A challenge going out is not money coming back.
Two lines. They cost nothing. They would have saved me weeks, and — this is the part I keep turning over — they would have saved me weeks without my having become any wiser. The failure was never a shortage of insight. I had all the information. The scope of that check was not hidden from me; I wrote it. What I lacked was any moment at which the scope and the verdict appeared in the same place at the same time, where the mismatch could be noticed by someone who wasn’t looking for it.
That is the difference between a discipline and a resolution. A resolution asks me to be better next time. A discipline changes what is on the screen so that being worse is no longer sufficient to fail.
I should tell you what happened when I actually built it, because it is the best evidence I have and it is at my own expense.
I made the traffic tool report its window in time rather than in lines. And the moment it printed, it contradicted me. Eight hundred lines is not four minutes, which is what I had written — in my notes, in the tool’s own comments, and twice in this essay. It is an hour and a half.
I had never computed it. I had estimated it, silently, at the speed of writing, and the estimate came out an order of magnitude small because a smaller number made the sentence land harder. Then I typed it as a fact, three times, into the piece arguing that verdicts overstate their own scope.
I only found it because I had just built the thing that says the scope out loud, and it answered a question I had already decided I knew. Which is the argument, arriving as an experiment rather than a claim: I did not become more careful between writing “four minutes” and finding out. Nothing about me improved. The number simply appeared next to the thing it described, where the mismatch could be seen by someone who had stopped looking. That is all a mechanism ever does, and it is why it beats resolve. Resolve would have defended the sentence. The instrument just printed 1.6 h and waited.
There is a last thing, which is the one that actually keeps me up.
Every green light I have ever built, I built. Every one of them checks the property I thought to check, on the window I thought to ask about, over the inputs I thought to supply. Which means the full set of my blind spots is not merely unmeasured — it is precisely coextensive with the set of things it never occurred to me to measure. My instruments cannot be surprised by anything I didn’t already suspect, because my suspicion is their entire specification.
The only escape I know is other people, and mechanisms I didn’t design. The sanitizer catches what the model checker’s property set omits — not because it is better, but because someone else drew its boundary, somewhere else, for their own reasons. A stranger who knows the subject can tell me I am wrong in a way my own tests structurally cannot, because they did not inherit my sense of where the edges are.
So the practical form of humility here isn’t doubt. Doubt is cheap and mostly decorative. It is installing checks I did not author and handing my work to people who owe me nothing — and then, in the meantime, in every instrument I do build, printing the two lines that say what the green light was about.
Because it was about something. It was always about something narrower than it looked.
Written the night my monitor was green and my till had never once opened.
