Buffer Overflow

What the four classes so far have in common is that a value was handed to an interpreter. The fifth has no interpreter. A value is written into the neighboring space because it is longer than the space allocated for it, and the item in that neighboring space becomes something else.

This lesson handles the class at the logic level. What is measured is not how to produce an overflow, but what result follows from fields sitting adjacent in a region, and which check cuts which step. The region, the field layout, and the copy are a data-structure model written for this lesson; no real memory layout, no real address, and no machine code appears at all.

The Result of Adjacency

The fields inside a region sit adjacent to one another: each field’s start is the previous one’s end. If a value longer than its size is written into a field, the extra bytes are the next field’s bytes. The copy operation does not know this; all it is given is a start and a length. A bounds check is the step that looks at whether the copy exceeds the target field’s size, and if so, does not perform the operation at all.

The region below has seven fields, and their order matters: the counter reading, the tariff code, and the auth flag are data fields; the guard value is a known, fixed item; the return label names which continuation point the function will return to. This is a model: not the layout of a real call record, but an array written to measure the result of adjacency.

TA22: the region has a fixed size, and its fields are adjacent. TA23: a copy with no bounds check writes the requested length, not the target field’s length; bytes that overflow past the end of the region are counted separately. TA24: the step sequence is five steps, and each check breaks a single step. TA25: the copied value is a single byte value; its content is not chosen.

// bo/region.mjs — bounded-array model: a fixed-size region and its named fields inside it.
// No real memory layout, no real address, and no machine code at all; this is a
// data-structure model.
export const FIELD = [
  ["name", 0, 12], ["counter", 12, 4], ["tariff", 16, 4], ["auth-flag", 20, 1],
  ["padding", 21, 3], ["guard-value", 24, 4], ["return-label", 28, 4],
];
export const SIZE = 32;
export const VALID_LABEL = [7, 9, 11];   // fictional: only these three labels are callable
export const FILL_BYTE = 65;             // the single byte value of the copied value

export function freshRegion() {
  const b = new Uint8Array(SIZE);
  b.set([79, 76, 67, 85, 77, 45, 48, 49], 0);   // name field: fictional counter id
  b.set([0, 0, 4, 210], 12);                     // counter reading
  b.set([0, 0, 0, 3], 16);                       // tariff code
  b[20] = 0;                                     // auth flag off
  b.set([222, 173, 190, 239], 24);               // guard value: fixed and known
  b.set([0, 0, 0, 7], 28);                       // return label: valid
  return b;
}

export function copyInto(b, fieldName, length, boundsCheck) {
  const [, start, size] = FIELD.find((a) => a[0] === fieldName);
  if (boundsCheck && length > size) return { written: 0, overflow: 0, rejected: true };
  const toWrite = Math.min(length, SIZE - start);
  for (let i = 0; i < toWrite; i++) b[start + i] = FILL_BYTE;
  return { written: toWrite, overflow: Math.max(0, length - (SIZE - start)), rejected: false };
}

export const corrupted = (b) => {
  const t = freshRegion();
  return FIELD.filter(([, start, size]) => {
    for (let i = start; i < start + size; i++) if (b[i] !== t[i]) return true;
    return false;
  }).map(([name]) => name);
};

export const label = (b) => b[28] * 16777216 + b[29] * 65536 + b[30] * 256 + b[31];
export const guardCorrupted = (b) => corrupted(b).includes("guard-value");

export const write = (g, ...s) => console.log(s.map((v, i) =>
  (g[i] < 0 ? String(v).padEnd(-g[i]) : String(v).padStart(g[i]))).join(""));

// bo/measure.mjs — the same set of lengths is run in two setups: without a bounds check and
// with one. Corrupted neighboring fields are counted. No randomness.
import { FIELD, SIZE, VALID_LABEL, freshRegion, copyInto, corrupted, label,
  guardCorrupted, write } from "./region.mjs";

const LENGTH = [8, 12, 13, 16, 20, 21, 24, 25, 28, 32, 36];
const nameSize = FIELD.find((a) => a[0] === "name")[2];

console.log(`region ${SIZE} bytes, ${FIELD.length} fields; target field "name" ${nameSize} bytes`);
console.log(`field layout: ${FIELD.map(([a, b, u]) => `${a}[${b}..${b + u - 1}]`).join(" ")}\n`);

const A = [-9, 9, 10, 11, 20, 12, 10];
console.log("1. without a bounds check");
write(A, "length", "written", "overflow", "corrupted", "farthest corrupted", "guard", "label");
let totalNeighbor = 0, guardHit = 0, labelCorrupted = 0, validCount = 0;
for (const u of LENGTH) {
  const b = freshRegion();
  const r = copyInto(b, "name", u, false);
  const neighbor = corrupted(b).filter((a) => a !== "name");
  totalNeighbor += neighbor.length;
  if (guardCorrupted(b)) guardHit++;
  const e = label(b);
  if (neighbor.includes("return-label")) {
    labelCorrupted++;
    if (VALID_LABEL.includes(e)) validCount++;
  }
  write(A, u, r.written, r.overflow, neighbor.length, neighbor.at(-1) ?? "-",
    guardCorrupted(b) ? "corrupted" : "intact",
    neighbor.includes("return-label") ? (VALID_LABEL.includes(e) ? "valid" : "invalid") : "intact");
}
console.log(`\nacross ${LENGTH.length} lengths, ${totalNeighbor} neighboring fields were corrupted ` +
  `in total; ${LENGTH.filter((u) => u > nameSize).length} lengths exceed the field's size`);
console.log(`cases where the guard value was corrupted: ${guardHit}/${LENGTH.length}; cases where ` +
  `the return label was corrupted: ${labelCorrupted}, and in ${validCount} of those the label ` +
  `stayed valid`);

const B = [-9, 12, 12, 16];
console.log("\n2. same set, with a bounds check");
write(B, "length", "result", "corrupted", "caught");
let caught = 0, passed = 0;
for (const u of LENGTH) {
  const b = freshRegion();
  const r = copyInto(b, "name", u, true);
  if (r.rejected) caught++; else passed++;
  write(B, u, r.rejected ? "rejected" : "written",
    corrupted(b).filter((a) => a !== "name").length, r.rejected ? "yes" : "no");
}
console.log(`the bounds check caught ${caught} of ${LENGTH.length} cases, ${passed} passed because ` +
  `they stayed inside the field; corrupted neighboring fields: 0`);

const STEP = [
  ["bounds-unchecked-copy", "the language or call does not check the length"],
  ["length-from-outside", "the length to copy comes from an input field"],
  ["neighbor-field-corruption", "there is a meaningful item next to the target"],
  ["decision-determining-field", "the corrupted field is a flag, a counter, or a continuation record"],
  ["jump-to-requested-branch", "the corrupted value is accepted as a valid branch name"],
];
const CONTROL = [
  ["bounds-checked-language", 1, "language class", 0],
  ["input-length-contract", 2, "app", 2],
  ["compiler-bounds-check", 3, "compiler", 5],
  ["guard-value-check", 4, "compiler", 3],
  ["non-executable-data-region", 5, "operating system", 1],
  ["layout-randomization", 5, "operating system", 1],
];
const C = [-29, 9, 20, 8];
console.log("\n3. step sequence and step-to-control mapping");
STEP.forEach(([a, o], i) => console.log(`  ${i + 1}. ${a.padEnd(29)}precondition: ${o}`));
write(C, "control", "breaks", "layer", "legit");
for (const [name, n, layer, m] of CONTROL) write(C, name, `step ${n}`, layer, m);

const COMPONENT = [
  ["collector.driver", "bounds-unchecked", ["compiler-bounds-check", "guard-value-check",
    "non-executable-data-region", "layout-randomization"]],
  ["collector.parser", "bounds-unchecked", ["guard-value-check", "layout-randomization"]],
  ["branch-endpoint.protocol-layer", "bounds-unchecked", ["input-length-contract",
    "non-executable-data-region"]],
  ["field-device.firmware", "bounds-unchecked", []],
  ["validator.service", "bounds-checked", []],
  ["billing-generation.service", "bounds-checked", []],
];
const D = [-33, -18, 11, 14, 14];
console.log("\n4. chain per component");
write(D, "component", "language class", "controls", "first break", "uncontrolled");
for (const [name, lang, d] of COMPONENT) {
  const set = lang === "bounds-checked" ? ["bounds-checked-language", ...d] : d;
  const breaks = CONTROL.filter(([a]) => set.includes(a)).map(([, n]) => n);
  const h = breaks.length ? Math.min(...breaks) : 0;
  write(D, name, lang, set.length, h ? `step ${h}` : "not broken",
    STEP.length - new Set(breaks).size);
}
const open = COMPONENT.filter(([, lang, d]) =>
  lang !== "bounds-checked" && d.length === 0).length;
console.log(`components with no link broken at all: ${open}; in the bounds-checked language ` +
  `class, the chain breaks at the first step, so the remaining four steps never even arise`);

region 32 bytes, 7 fields; target field "name" 12 bytes
field layout: name[0..11] counter[12..15] tariff[16..19] auth-flag[20..20] padding[21..23] guard-value[24..27] return-label[28..31]

1. without a bounds check
length     written  overflow  corrupted  farthest corrupted       guard     label
8                8         0          0                   -      intact    intact
12              12         0          0                   -      intact    intact
13              13         0          1             counter      intact    intact
16              16         0          1             counter      intact    intact
20              20         0          2              tariff      intact    intact
21              21         0          3           auth-flag      intact    intact
24              24         0          4             padding      intact    intact
25              25         0          5         guard-value   corrupted    intact
28              28         0          5         guard-value   corrupted    intact
32              32         0          6        return-label   corrupted   invalid
36              32         4          6        return-label   corrupted   invalid

across 11 lengths, 33 neighboring fields were corrupted in total; 9 lengths exceed the field's size
cases where the guard value was corrupted: 4/11; cases where the return label was corrupted: 2, and in 0 of those the label stayed valid

2. same set, with a bounds check
length         result   corrupted          caught
8             written           0              no
12            written           0              no
13           rejected           0             yes
16           rejected           0             yes
20           rejected           0             yes
21           rejected           0             yes
24           rejected           0             yes
25           rejected           0             yes
28           rejected           0             yes
32           rejected           0             yes
36           rejected           0             yes
the bounds check caught 9 of 11 cases, 2 passed because they stayed inside the field; corrupted neighboring fields: 0

3. step sequence and step-to-control mapping
  1. bounds-unchecked-copy        precondition: the language or call does not check the length
  2. length-from-outside          precondition: the length to copy comes from an input field
  3. neighbor-field-corruption    precondition: there is a meaningful item next to the target
  4. decision-determining-field   precondition: the corrupted field is a flag, a counter, or a continuation record
  5. jump-to-requested-branch     precondition: the corrupted value is accepted as a valid branch name
control                         breaks               layer   legit
bounds-checked-language         step 1      language class       0
input-length-contract           step 2                 app       2
compiler-bounds-check           step 3            compiler       5
guard-value-check               step 4            compiler       3
non-executable-data-region      step 5    operating system       1
layout-randomization            step 5    operating system       1

4. chain per component
component                        language class       controls   first break  uncontrolled
collector.driver                 bounds-unchecked            4        step 3             2
collector.parser                 bounds-unchecked            2        step 4             3
branch-endpoint.protocol-layer   bounds-unchecked            2        step 2             3
field-device.firmware            bounds-unchecked            0    not broken             5
validator.service                bounds-checked              1        step 1             4
billing-generation.service       bounds-checked              1        step 1             4
components with no link broken at all: 1; in the bounds-checked language class, the chain breaks at the first step, so the remaining four steps never even arise

The Order of Corruption

The first output runs through eleven lengths one by one and counts the corrupted neighboring fields. The result is graduated: 13 bytes corrupts one field, 20 bytes two, 21 bytes three, 25 bytes five, 32 bytes six. There are 33 neighboring-field corruptions in total, and nine of the eleven lengths exceed the target field’s size.

The order is not random; it is exactly the same as the fields’ layout in the region. A one-byte overflow touches the nearest neighbor, a twelve-byte overflow touches four neighbors. The only thing that determines which item an overflow corrupts is that item’s distance from the target. This explains why the defense has to look at the field layout: the same overflow corrupts a different item in a different layout.

Three fields produce a separate result. auth-flag is a decision field: when it is corrupted, a branch goes a different way. guard-value is a known, fixed item; the moment it is corrupted, the process can see this before returning — it was corrupted in 4 of eleven cases. return-label names where the function will return to, and it was corrupted in two cases.

The last line is this lesson’s most important number: in neither of the two cases where the return label was corrupted did the label stay valid. The copied value was a single byte value and it was not chosen; the corruption happened, but the result did not produce a valid branch name. Corruption and steering control flow are not the same thing; the step required for the second is not covered by this lesson and will not be. That is why the chain’s fifth step is written as a separate step.

What the Bounds Check Catches

The second output runs the same eleven lengths with a bounds check. Nine cases are rejected, two pass — and the two that pass are the lengths that do not exceed the target field’s size. The count of corrupted neighboring fields is zero.

What this table says is that the bounds check does not make a complicated inference. It makes a single comparison: is the requested length greater than the target field’s size. The cost of this comparison is immeasurably small next to the checks needed to break the rest of the chain.

The result that follows from this is the third output’s first row. If the bounds check is done by the language itself, the chain breaks at the first step: there is no such thing as a copy with no bounds check, the precondition for the next four steps never even arises, and its legitimate-work cost is 0. The language class removing this class is not adding a check — it is removing the first step’s precondition from the definition.

Which Step Each Check Breaks

The third output maps five steps to six checks. The checks come from three separate layers, and each lands on a different step.

The length contract at the app layer breaks the second step: the length to copy no longer comes from outside. The bounds check the compiler adds breaks the third step: the copy can no longer write outside the region. The guard-value check the compiler adds breaks the fourth step: the corruption happens, but it is seen before the return, and the process halts. The operating-system checks land on the fifth step.

Their legitimate-work costs differ: the language class is 0, the length contract 2, the guard value 3, the operating-system checks 1 each, the compiler’s bounds check 5. The most expensive check is not one of the earliest-breaking ones — earliness and cheapness do not go together in this class.

The fourth output measures six components. Two components are in the bounds-checked language class, and the chain breaks at the first step. Of the four bounds-unchecked components, one breaks at the third step, one at the fourth, one at the second. One — the firmware — breaks at no step at all: all five of the five steps are uncontrolled. In a runtime environment with no compiler or operating-system checks, this class’s only defense is the app’s own length contract, and it is absent there too.

Summary

• Fields inside a region sit adjacent to one another; a copy that exceeds the target field’s size writes the extra bytes into the neighboring fields’ bytes. The order of corrupted fields is exactly the same as the fields’ layout.
• In the 32-byte region, 11 lengths corrupted 33 neighboring fields in total; 9 lengths exceeded the target field’s size. The guard value was corrupted in 4 cases, the return label in 2.
• In neither of the 2 cases where the return label was corrupted did the label stay valid. Corruption and steering control flow are not the same thing, and that is why the chain’s fifth step is kept separate.
• Over the same 11 lengths, the bounds check rejected 9 cases, 2 passed because they stayed inside the field, and the count of corrupted neighboring fields came out to 0. The check consists of a single comparison.
• The bounds-checked language class breaks the chain at the first step, at a legitimate-work cost of 0: the precondition for the remaining four steps never even arises. The length contract breaks the 2nd step, the compiler’s bounds check the 3rd, the guard value the 4th, the operating-system checks the 5th.
• Of six components, the chain breaks at step 1 in 2, at step 2, 3, or 4 in 3; in 1, all five of the five steps are uncontrolled.

Next Step

In this lesson’s chain, a field had no boundary, and the defense was about putting that boundary in place. In the next class, the boundary already exists, and the attacker tries not to cross it, but to stay under it: a few attempts per account, each attempt a valid request. The next lesson separates three password-attack forms along cost and threshold: how many forms a lockout stops, why a form that makes only a few attempts per account never triggers lockout at all, at which attempt a rate limit kicks in, and how many legitimate users each threshold locks out.