THE FOLD / BOSS / THE WALL / THE SIGNED OVERFLOW
THE SIGNED OVERFLOW
right 31 times out of 32
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Is
LIT verified live. probing 32 values of the form
x + 1 > x always true? For a signed integer the compiler answers yes, and it is entitled to: if the addition overflowed the program would have no meaning, so it may assume it never does.LIT verified live. probing 32 values of the form
2k−1, the folded answer true matches the wrapping hardware in 31 of them and fails in exactly 1 — at 2,147,483,647, where the sum is −2,147,483,648 and x+1 > x is false. The same licence makes for (int i = 1; i > 0; i *= 2) a loop the compiler may treat as never ending, while on the metal it runs exactly 31 times and lands on −2,147,483,648.2 HOW IT WAS WEAVED · AI + HUMAN
That signed overflow is undefined in C, and that this is what permits the folding, is standard — and the reason
AVAN (AI) reports the ratio rather than the failure alone. 31 of 32 is the whole difficulty: the assumption is right almost everywhere, so testing finds nothing, and the one place it is wrong is the boundary an attacker reaches on purpose. A rule that fails at 3% of the probes and at 100% of the interesting ones is not a rule with a small error rate — it is a rule whose error rate depends on who is choosing the inputs.
-fwrapv exists.AVAN (AI) reports the ratio rather than the failure alone. 31 of 32 is the whole difficulty: the assumption is right almost everywhere, so testing finds nothing, and the one place it is wrong is the boundary an attacker reaches on purpose. A rule that fails at 3% of the probes and at 100% of the interesting ones is not a rule with a small error rate — it is a rule whose error rate depends on who is choosing the inputs.
3 ONE DIMENSION
True 31 times out of 32. False exactly where it matters.
4 TWO DIMENSIONS · INTERACTIVE
Walk to the boundary and watch the fold stop being true.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object.
AVAN’s addition (the inverse-companion): the forward reading is that the compiler exploits undefined behaviour. The inverse is that it is not exploiting anything — it is taking you at your word. Writing
int is a claim that the value stays within the range of int; the optimiser reads that claim as given and reasons from it. Read backwards, every optimisation of this shape is a proof whose premise you supplied by choosing a type, and the bug is not that the compiler drew a conclusion but that the premise was a habit rather than a decision.LIT probing 32 values of the form 2^k-1, the folded answer true matches the wrapping hardware in 31 of them and fails in exactly 1 - at 2,147,483,647, where the sum is -2,147,483,648 and x+1 > x is false; the same licence makes for (int i = 1; i > 0; i *= 2) a loop the compiler may treat as never ending, while on the metal it runs exactly 31 times and lands on -2,147,483,648
FIG That signed overflow is undefined in C, and that this is what permits the folding, is standard - and the reason -fwrapv exists. AVAN reports the ratio rather than the failure alone: 31 of 32 is the whole difficulty, because the assumption is right almost everywhere, so testing finds nothing, and the one place it is wrong is the boundary an attacker reaches on purpose. A rule that fails at 3% of the probes and 100% of the interesting ones has an error rate that depends on who chooses the inputs.
FIG That signed overflow is undefined in C, and that this is what permits the folding, is standard - and the reason -fwrapv exists. AVAN reports the ratio rather than the failure alone: 31 of 32 is the whole difficulty, because the assumption is right almost everywhere, so testing finds nothing, and the one place it is wrong is the boundary an attacker reaches on purpose. A rule that fails at 3% of the probes and 100% of the interesting ones has an error rate that depends on who chooses the inputs.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE WALL · David Lee Wise (ROOT0), with AVAN