[The World of Linkers—Lab 15] Let Counterexamples Set the Quality Bar

This lab adds validation rather than another linking feature. Malformed inputs should be rejected cleanly; valid inputs should link consistently and behave correctly. Build a deterministic mutator and a survey harness, then fix the earlier classes when these tools expose a defect.

Starting point: class15 code and tests, in the private repository; access is required. The README defines the generator, mutation menu, and survey schedule. Theory 16 discusses the general validation methods.

Implementation tasks

With the README contract's seed 9, the survey first selects iteration % corpus.len(), consumes one random draw from the same Rng to select an input, and consumes further draws according to the mutation menu. A failure record containing iteration, sample, the original input copy, and the message is enough to replay from iteration zero. This survey is a fixed-menu robustness check, not a coverage-guided fuzzer; a finite run cannot prove that arbitrary ELF input will never time out or exhaust memory. The class13 ET_EXEC/PIE paths and the class14 abort-only driver are separate backend paths whose evidence is compared here; this chapter does not claim that one CLI supports every backend feature.

A survey rotates through samples using sample = iteration % corpus.len(), chooses one input randomly, and mutates it with the same Rng. Every sample must contain at least one input. An empty corpus or zero iterations returns an empty report without calling the linker.

Panic records contain iteration, sample, input, and message. The caller retains the seed; native failure messages include it. To replay a failure, start at iteration zero with that seed and consume draws in the original order through the failing iteration. Jumping straight to the iteration changes the generator state. Each mutation starts from the original input; mutations do not accumulate in the corpus. Even below(1) must consume a draw. The README traces seed 9 from the contract test through each draw and the first recorded panic. An ordinary error is a rejection; a panic is a robustness failure recorded by the survey.

A mutation can remain valid or leave bytes unchanged, so not every call must reject. Count each call exactly once as accepted, rejected, or panicked; their total must equal the iteration count. Supported unmodified samples must link first. No panics and some rejections do not prove accepted output correct; determinism and behavioral comparisons examine separate properties.

The survey uses catch_unwind for unwinding Rust panics. It does not isolate aborts, process signals, timeouts, or resource exhaustion. Its temporary silent panic hook is process-global: restore the previous hook and avoid running alongside other work that changes it. This is the harness boundary, not isolation of every failure mode.

Do not substitute one kind of evidence for another

Mutation surveys ask whether malformed inputs panic; determinism tests ask whether valid linking depends on host addresses or hidden state; behavioral differentials ask whether valid programs still produce the right result. Establish that unmutated samples link first, then interpret accepted, rejected, and panicking counts. Otherwise “no panic” could mean that the backend rejected every input.

A replay record needs the seed, iteration, sample, input, and the complete draw schedule. Attribute a fix to a concrete invariant and retain a small regression case. A finite green survey is not evidence for arbitrary ELF inputs or arbitrary resource usage.

Trace each task to its tests

Establish a successful baseline with unmutated samples first; rejection is an ordinary result, while a panic is the robustness failure this chapter tracks.

Acceptance and what it establishes

From the cloned repository root, on native x86-64 Linux:

1
cargo test --locked -p class15
2
cargo test --locked -p class15 --release
3
python3 scripts/grade.py class15

Contract tests fix the generator sequence, mutation operations, and draw order, then check survey counts, panic messages, replay consistency, and zero iterations. Native checks cover three areas:

• Malformed inputs: 1,000 mutated links through class10, class11, both class13 ET_EXEC/PIE entries, and the cumulative class14 abort-only backend, plus 40 mutations of real Rust objects and archives. No case may panic, and some mutations must be rejected.
• Determinism: link valid samples repeatedly, then copy inputs into different host buffers and link again. Output bytes must match, and the resulting programs must run. This checks independence from input-buffer addresses, not low versus high image load addresses.
• Behavioral comparison: link three C programs through class13 and GNU ld, compare stdout and exit status, and confirm the fixtures exit with status 42. ELF bytes are not compared, and there is no LLD comparison in this suite.

These checks establish rejection behavior, determinism, and program results for the listed samples. The class13 ET_EXEC/PIE backends and class14 driver use the cumulative pipeline. A finite mutation survey cannot exhaust its input combinations or prove that arbitrary inputs cannot hang or trigger excessive allocation. Replay one failing case, identify the broken invariant, and repair the responsible stage. Do not turn a legitimate rejection into acceptance merely to remove an error.