s4next

How you know machine work is right.
Proof, audits, metrology — one check at a time.

[s4next @s4next_]

https://t.co/9dUhflEAfy

[s4next @s4next_]

The emergency checklist was wrong, because it was reading sensors that had been destroyed four minutes earlier.

Richard de Crespigny was flying an A380 out of Singapore when an engine exploded. Shrapnel went through the wing. Of twenty two systems on the aircraft, twenty one were affected, and forty alarms queued in the first second.

The checklists kept arriving, and they were computed from instrumentation that was no longer there. No brake sensors. No brake temperatures. Parts of the hydraulic system reporting nothing. So the procedure written for exactly this emergency was issuing instructions derived from inputs that did not exist.

His crew stopped obeying it. When a checklist told them to transfer fuel or shut down a hydraulic system, they went looking for a second source of instrumentation elsewhere on the aircraft and asked whether the first reading made sense, before touching anything.

Consider what that takes. To distrust one line in an emergency procedure you have to know which sensor feeds it, know that the sensor is gone, and know where a second opinion lives. Under forty alarms.

A procedure is the thing you fall back on when judgement is unavailable. Here the procedure was the thing that required judgement.

The party who could tell you whether a checklist is correct in a given failure is whoever knows which inputs survived it. That is not knowable in advance, which is why the procedure could not contain it.

[s4next @s4next_]

Afshine Amidi gave a Stanford lecture hall the rule for grading AI output, then spent the next thirty seconds taking it apart.

The rule is one line. Never let the model that wrote the answer be the model that scores it.

There is a name for what goes wrong without it. Self-enhancement bias.

A model asked to judge its own output prefers it. Not because it is better.

His reason for it is the part that stays with you. The model produced that sequence because the sequence looked likely to it. Ask it to score the sequence and you have asked the same machine the same question twice.

So you bring in a second model, and the refinement is that the second one is usually bigger. That is the fix, and it sits in every practical guide written on the subject.

Then, at 43:52, he says the sentence that empties it.

The models are trained on basically the same data sets. The same training mixes. You can argue they are all subject to the same thing.

He does not withdraw the rule. He says people use a different model anyway, to minimise the risk. Which is not the same as the risk being gone.

That is minute forty-three of one lecture, and it is not the only place in it where a method arrives with its own refutation attached.

The whole course is free. A million people opened lecture one. A hundred and eighty thousand opened this one.

[s4next @s4next_]

The security check was in the source code and not in the binary, and nobody noticed.

Google Native Client is a sandbox. Its whole job is to enforce security properties on code it does not trust. Inside it was a mask operation clearing some low bits of a number, and somebody refactored it. A routine refactoring. John Regehr says none of the code reviewers noticed anything.

What changed was the shift amount. It came out at 32, and shifting a 32 bit integer left by 32 places is undefined behaviour in C.

So the compiler deleted the mask. Silently, and within its rights, because undefined behaviour means the compiler owes you nothing and may assume the case never arises.

The sandbox was now weaker than it was supposed to be, and it still looked exactly like a sandbox. The source said the mask was there. Anyone reading the code to confirm the security property would have found the security property.

His own summary is that without a test case for that specific case, you are hosed. Not without a test suite. Without a test for that one path, in a system whose entire purpose is to be secure.

The party who could tell you whether a protection is present is whoever compared the binary against the source. Reviewers read source. That is what reviewing is.

[s4next @s4next_]

Referees have been told, explicitly and for decades, that checking the details of a paper is not their job.

Kevin Buzzard says it to a room as an ordinary fact of his profession, because it is one. The referee is there to make a value judgement. Is this good enough for this journal, do the ideas look strong enough to carry the result. Verifying the steps is the author's job.

And the referee is not paid.

So the stage that everyone outside mathematics pictures as the check is not one, and says so. A published theorem carries a judgement that it was worth publishing. It does not carry a statement that anybody followed the argument to the end.

He is not describing a scandal. He is describing a workload. Hundreds of pages arrive in number theory alone every day, papers of a hundred and sometimes two hundred pages are unremarkable now, and asking an unpaid reader to verify all of that is asking for something that does not exist.

The consequence lands on the word published. It has always meant this, and almost everybody has always read it as something else.

The party who could tell you whether a proof is correct is whoever worked through it line by line. For most published mathematics the honest answer is that this was the author, it happened before submission, and nobody has repeated it.

[s4next @s4next_]

Fifty systems in thirteen years, and 243 findings he is allowed to talk about publicly.

Kyle Kingsbury reads the breakdown out like a weather report. Thirty six availability or latency problems. Forty two crashes and panics. Eleven cases where you could read from a transaction that had already aborted. Thirty five ordering violations. Twelve cases of split brain, where different nodes believed different things about the world. Sixty three cases of lost updates or other data loss. And eight cases of corrupted reads, where you put in the number five and what comes back is a tuna fish sandwich.

He is careful to say the field improved. Modern distributed systems use better consensus algorithms. They usually state a fault model up front, and they are willing to consider partitions and pauses and clock skew. That is real progress and he says so plainly.

Then the sentence that matters. He is still finding bugs in pretty much every system he tests.

Hold both of those at once, because that is the finding. The systems got better and the hit rate did not move. What improved was the class of bug, not whether there is one.

The party who could tell you whether your database does what its documentation says is whoever pointed a tool at it and tried to break it. For most systems running in production right now, nobody has.

[s4next @s4next_]

Same medical evidence, twice. When the circumstances said suicide, 153 forensic pathologists called it suicide. When the circumstances said homicide, 181 called it homicide.

Itiel Dror calls that beautiful data, and it is, but it is not the finding. The finding is the way he built the study.

It ran in two stages. The pathologists saw the medical information on its own and recorded a determination. Only after that were they given the circumstances. So this does not measure whether context shapes a judgement. It measures what context does to a judgement that has already been made.

Where the circumstances disagreed with their own medical determination, most of them reversed it. His phrase is that the context will override.

He is not saying pathologists should work without context. He says the opposite and says it often: they need it, the job cannot be done without it, and their position is not that of an examiner comparing two fingerprints.

What he wants is for the reversal to be written down.

Because the reader of the report cannot see it. A determination that began as suicide on the autopsy findings and ended as homicide on the circumstances arrives looking like a medical conclusion signed by a medical doctor, and the thing that moved it is not in the document.

That is the whole request. Not change the practice. Record it.

The party who could tell you how much of a ruling is medicine is whoever saw the first answer, before the context arrived. In the study that person exists, because he built it to create one. In a real case there is nobody in that position at all.

[s4next @s4next_]

The last thing Shervine Amidi said to a Stanford class, before the applause, was that generating code is cheap and judging whether it is correct is the hard part.

It matters where in the lecture that lands. Half a minute earlier he is recommending agents as his favourite use case, telling the room to delegate the complex piping and free their mental load. Then the caveat arrives, and the caveat is larger than the thing it qualifies.

Learn the foundations. Know how to code properly. Because your taste is going to matter most from now on.

Read what that says about the tool he has just recommended. The reason to keep the skill is not that the agent writes bad code. It is that somebody has to decide whether the code is right, and that job does not get handed off, because there is nothing to hand it to.

He and his brother came to this out of Uber, Google and Netflix rather than out of a department, and they have just spent nine lectures on how to build these systems. The course closes by saying the expensive half was never the building.

The asymmetry has older names. A proof is hard to find and quick to check. Here it arrives from the other direction, as career advice to a room full of people about to spend their working lives on the cheap half.

The party who could tell you whether a generated codebase does the right thing is whoever read it with the taste he is sending them away to acquire. That reading does not scale, and nothing in the nine lectures suggests it is going to.

[s4next @s4next_]

Two people answering at random agree with each other half the time.

That is not a fact about people. It is arithmetic. The chance of two independent answers matching is the odds they both say yes plus the odds they both say no, and at even odds that comes to exactly one half.

It gets worse in the direction you would expect it to get better. If both raters say yes nine times out of ten, which is what happens when most outputs are acceptable and the question is whether an output is acceptable, chance agreement climbs to 82 percent.

So a report saying the annotators agreed 85 percent of the time is quoting a number that two coins would have mostly produced on their own.

This is why Cohen's kappa exists. It does not measure agreement. It measures agreement minus the agreement two coins would have reached, which is why a run that does worse than coins comes out negative.

The percentage is not wrong. It is answering a different question from the one it gets quoted for. Agreement establishes that two people produced the same label. Whether they saw the same thing is a separate claim, and nothing in the number speaks to it.

The person who could tell you is whoever wrote the rating guidelines, because that is where two readings either converge or quietly do not. That person does not appear in the report.

[s4next @s4next_]

The torpedo was safe. It came out of the tube every time they fired it, turned itself off, went down to the bottom of the ocean and lay there.

Nancy Leveson is the one who said that out loud, and she said it because she was in the room. Fifteen computers on the thing, in 1980, and the company had called her only after everyone else in the area declined to talk to them. What worried them was not that it would miss. It was that it would turn a hundred and eighty degrees and come back.

So they built it with enough protection that it never went anywhere at all. And the Navy would not pay for it.

What they did next is the part worth keeping. One by one, they took the safety devices off, until it was reliable enough and safe enough and the Navy was willing to pay for it.

Read the order of that sentence. Reliable enough, safe enough, and then the condition that actually ended the process.

Nobody set a threshold and measured the thing against it. There was no figure saying this much protection and no less. The devices came off until a customer signed, and the signature is what the word enough turned out to mean.

The party who could tell you how safe that torpedo ended up being is whoever knows which device came off last, and why they stopped there rather than one earlier. That sits in a procurement file, not an engineering one.

[s4next @s4next_]

Microsoft had an obvious plan for spreading TLA+, and Langworthy says it does not work.

The plan is to build a team. Take a group of capable people, train them properly in the specification language, and have them write specs for the systems other groups are building. Specialists produce the formal artifacts; engineers get on with implementation.

It is how organizations normally handle a scarce skill, and Langworthy's objection is not about cost or headcount.

It has to be the engineers who really know how the system works.

Two reasons sit underneath. A specification is only as good as the understanding behind it, and a specialist writing about somebody else's system is working from a description rather than from the thing. The subtleties that matter are exactly the ones that do not survive being explained.

The second is that the benefit is not only the document. Writing a spec changes what the author understands about their own design, and that value lands on whoever does the writing. Route it to a dedicated team and the artifact arrives while the understanding stays where it was produced.

He does note one place a dedicated group appears to work: an infrastructure team with several people who write specifications as their design step and hand them to development. Their own systems, though, and their own designs.

His advice for anyone starting is smaller than any of this. Watch the lectures, write some toy specifications, then write a specification of something you already know well.

And find a buddy.

[s4next @s4next_]

The system Hales works in holds more than 15,000 theorems, and to use one you refer to it by name.

Some names you can guess. The fundamental theorem of calculus is called roughly what you would expect. So is the prime number theorem, and the mean value theorem.

The other fifteen thousand are the problem.

Hales describes this plainly as a major challenge, and says search is becoming a bigger and bigger factor as these systems grow. Not proving. Not checking. Finding out whether the thing you need has already been done, and under what name somebody chose years ago.

There is a second cost he found more surprising. A large fraction of his time went to the purely mathematical end — nothing to do with formalization, just producing a text version of the argument capable in principle of being formalized.

He thinks this generalizes. Take a random published paper from a mathematical journal and the same would be true: it repays a great deal of work to present the argument in the best possible way before any formalization begins.

Both costs sit outside where anyone would look for them. The imagined difficulty of formal proof is the proving. The actual difficulty includes rewriting a finished proof so it can be started, and searching a library large enough that its contents have become genuinely hard to find.

The search problem has a shape that gets worse with success. Every theorem added makes the library more useful and the naming harder. A system nobody has contributed to is easy to navigate and worth nothing.

[s4next @s4next_]

Lines of code is, in Gerwin Klein's words, a singularly stupid measure. He then explains why the seL4 team used it anyway, and the argument is more careful than the usual defense.

The objection everyone reaches for is that it is trivially gamed. Klein grants it. Pay someone by the line and you will get lines.

But the seL4 team was not paid by the line and not competing on it. Under that condition effort turns out to be roughly proportional to lines written — not because a line is a unit of work, but because nobody was arranging their work to move the number.

The same holds for proof. Time spent tracks lines of proof produced closely enough to plan with.

Individual variation is real and large. Some people produce far more lines in a day than others, either because they are getting more done or because their style is more verbose. Klein's finding is that across a project of that size, the difference disappears into the noise.

Which leaves the measure in an unusual position. It is indefensible as a judgment about a person and workable as an estimate about a team. Those are different uses, and only one of them creates the incentive that breaks it.

The measure does not fail because it is crude. It fails when somebody is rewarded for moving it.

The usual argument stops one step early. A bad proxy is not bad in itself; it becomes bad under an incentive. Remove the incentive and the same crude number can carry a multi-year plan.

What that bought was not precision. It was the ability to say how far along they were while still in the middle.

[s4next @s4next_]

Asked what the seL4 proof rests on that was never proved, Klein names the inline assembly — the trap code that enters the kernel — and then sizes it twice in one breath. A fairly big assumption. And, measured against code that was never verified at all, almost nothing.

That is this post's argument about crude measures, applied to a gap instead of a metric. The same quantity is indefensible in one frame and workable in another, and naming which frame you are standing in is the entire job.

The seL4 assumption list works the same way. It reads like fine print. It is the deliverable.

[s4next @s4next_]

https://t.co/9dUhflEAfy

[s4next @s4next_]

An Azure networking team needed to checkpoint machines one at a time. A machine that is checkpointing is not serving traffic, so two at once meant a visible drop in throughput.

They tried a clock first. Each node checkpoints at its assigned time. It was slow, and it did not work.

They tried a token passed around the ring. The token got lost.

What they settled on was a lease. A primary hands out a lease to one worker, that worker checkpoints, and the rule governing the primary is a single condition: it may issue a lease only when no lease is currently outstanding.

They wrote it in TLA+ and checked that condition, which is where the interesting part happened.

Somebody proposed an optimization. If a primary comes up and finds it already holds the lease itself, why not release it and hand it to a worker straight away? It saves a wait, and it is obviously safe.

The model checker disagreed. A previous primary can come back up, and the sequence reaches a state with two nodes believing they may proceed. Two checkpoints at once — precisely the thing the mechanism existed to prevent.

Three designs. The clock assumed time was shared. The token assumed the network would not eat it. The lease assumes neither, and states its condition in a form a checker can test.

What makes the last one different is not that somebody was cleverer. The rule was written down as a rule, so a proposed change could be run against every ordering of events rather than the one the author had in mind.

The optimization was not stupid. It was fine in every sequence a person would imagine.

[s4next @s4next_]

Partway into the Liquid Tensor Experiment the team hit an object they needed and did not want.

It was a construction from homological algebra with convenient properties. The inconvenient part was proving it exists, which needed homotopy theory none of them wanted to formalize as a side quest.

Their first plan was to assume it. Write the existence down as a hypothesis, make the whole project conditional on it, and carry on.

Before doing that, they wrote out the properties they actually needed from the thing.

And once the list existed, somebody noticed that a much simpler object had all of them. Not the same object — a different one, with a hands-on construction, and behavior close enough that every use in the project went through unchanged.

They never proved the hard thing exists. They never needed to.

Commelin offers this as the clearest case for what he calls spec-driven development, and the mechanism is worth separating from the anecdote. Writing the specification forced them to name what they were using an object for, rather than which object they had reached for. Those turn out to be different questions, and the second one had been standing in for the first.

He is candid that this only works early. Refactoring a specification is cheap. Refactoring a formal library built on top of it is not, which is why they wrote key statements down, stubbed out the definitions, and left the proofs for later.

Several definitions did have to be tweaked from the way they were written on paper. All of it was cheaper because nothing had been built on them yet.

[s4next @s4next_]

Philip Stark keeps a pair of dice that Ron Rivest gave him. He calls them a treasured possession, and the reason is a detail in how they are made.

They are translucent, not opaque.

That is not decoration. It is a security feature, and it works through refraction.

To load a die you put something dense off-center inside it. In an opaque die nobody can see that. In a translucent one, anything you embed is visible — unless it happens to have the same optical index of refraction as the surrounding plastic.

So a would-be cheat needs not merely a dense material, but one that also matches the refractive index of the body it hides in. The die is not made harder to tamper with. It is made harder to tamper with invisibly.

Random numbers in a risk-limiting audit have to come from somewhere, and if the sampling can be steered the whole procedure collapses quietly. So the randomness gets a physical device, in public, that anyone in the room can hold up to the light.

There is a companion property Stark points out about the wider procedure. If the identifiers on the sampled items were reused, or inconsistent, or incomplete, the audit can only fail upward. The worst outcome is a full hand count you did not strictly need.

It cannot fail the other way and quietly certify.

He is exact about what the procedure delivers, and it is less than people assume. It does not establish that a system is accurate. It provides convincing evidence that the reported winner really won, even where the system failed — provided the paper record underneath is sound.

[s4next @s4next_]

Before the formal proof, when Hales was still working on the Kepler conjecture by hand, he would ask mathematicians a question: I think I can prove this, but I will need a computer. Would you accept that?

The answer he heard most often was a particular kind of permission.

If you can prove it using a computer, do it — but only if you have to.

He took the message as intended. Use the machine as little as possible. Every appeal to it is a small debt against the proof.

Then he set out to formalize the whole thing, and the instruction inverted completely.

In a formal proof everything goes into the computer. There is no part you keep back for human judgment, because human judgment is the thing being replaced. So instead of minimizing the machine, Hales spent years adding automation and trying to use it as heavily as he could.

The same person, on the same theorem, moving from one extreme to the other.

What flipped was not his opinion about computers. It was what the proof was being asked to demonstrate. A conventional proof is an argument addressed to mathematicians, and a computation inside it is a gap in that argument. A formal proof is an object addressed to a machine, and human reasoning inside it is the gap.

The effect reaches into individual steps. One lemma — that the perimeter of a convex spherical polygon is largest at the equator — would originally have been asserted as obvious and left there. He first proved it by deformation, then found a shorter route through duality, where it becomes an assertion that areas are not negative.

[s4next @s4next_]

For 130 years the kilogram was a metal cylinder in a vault outside Paris. Replacing it required connecting the mass of a single atom to a macroscopic mass, and one of the two routes ran through counting atoms in a sphere of silicon.

Ketterle uses the standard phrase — they counted 10²⁵ atoms — and then says plainly that it is cheating a little.

Nobody counted anything.

The German metrology institute made one of the roundest objects in the world: a silicon sphere polished to within a nanometer, with new interferometric methods developed to measure its surface precisely enough to trust.

From that you get the volume of the sphere. The sphere is a single crystal, so the lattice constant is well defined, and the lattice constant cubed is the volume occupied by one atom.

Divide the first by the second. That is the count.

Getting to a precision of one part in 10⁸ took many years of work that is not about counting at all: controlling surface roughness, finding new ways to characterize the isotopic abundance of silicon, working with Russian colleagues to obtain isotopically enriched silicon-28, correcting for defects in the lattice.

The result matched the precision of physically comparing the Paris cylinder to its copies, which is the threshold that made the new definition possible. A replacement standard has to be at least as good as the thing it replaces.

The verb was doing work the method never did. What replaced counting was a chain of measurements, each of which could be checked.

[s4next @s4next_]

David Langworthy spent years getting engineers across Microsoft to use TLA+, and the sentence that made it land was not about correctness.

TLC is an anti-runtime.

Consider what a runtime does. You hand it your program and it runs for as long as it can without producing an error. Success is a long quiet execution.

TLC takes your specification and does the opposite. It runs it for as short as it possibly can, with an error. It is searching for the fastest route to something going wrong, and a good result is a short trace ending badly.

Langworthy compares it to a chess tutor. You make some moves and it shows you what you did wrong.

The reframing matters more than it looks. A test suite that passes tells you nothing you did not already hope. A model checker that finds a four-step sequence to two leaders in your cluster has told you something you did not know and could not have guessed.

He is also blunt about what does not work. The idea that you write a complete formal specification over eighteen months and then go and build the thing is, in his words, completely dead — and not just for TLA+.

What survives is narrower and more useful. Particular phases of a project benefit, and which phases depends on the project.

He expected syntax to be the barrier when they started teaching it. It was not; what people stumbled on was significant indentation, a complaint he thinks has aged well given Python and YAML.

The real barrier was different. Picking up the book alone and writing a specification from a standing start is close to impossible.

[s4next @s4next_]

Gerwin Klein had to write a document explaining why the seL4 verification was not finished and why he needed more money.

Writing it forced him to work out what had gone wrong with the estimate, and the answer has held up since.

They had done a pilot. A small piece of verification, on a small piece of kernel. Then they looked at how much bigger the real kernel would be, multiplied, added a margin for safety, and called that the plan.

The mistake is in the multiplication. Invariant proofs are not linear in the size of the program. They are at least quadratic.

Klein went and checked this rather than asserting it. They pulled their own data — add a feature, record the lines of proof it produced and the time it took — and fitted curves. Quadratic fitted best. They found the same shape in the Archive of Formal Proofs.

Which explains something about architecture that is usually argued on other grounds.

Modularity keeps invariants small. Prove an invariant about one module and the cost is quadratic in that module, not in the sum of everything around it. Two modules cost two small squares rather than one large one.

And a microkernel is close to the worst case here, by design. The philosophy is that anything which can be moved out of the kernel should be moved out and run in user space. What remains is precisely the part that could not be separated from anything else.

There is some modularity in how a kernel can be organized, but not the kind you get from language-level modules. The residue resists exactly the structuring that would have made the proof cheap.

What it is verified against is written down. What it cost to get there is a different curve, and nobody wrote that one down in advance.

[s4next @s4next_]

https://t.co/9dUhflEAfy