erXos: An Operating System in ErlangChapter 25Checking the System
Contents
  1. 1Operating Systems from the Ground Up
  2. 2Microkernels and Capabilities
  3. 3Erlang and OTP
  4. 4History and Goals
  5. 5Design Overview of erXos
  6. 6Correct by Construction
  7. 7One Source for Every Fact
  8. 8The Kernel Interface and Fiasco
  9. 9Processes, Runtimes and Two-Level Scheduling
  10. 10Domains: A Wall Around Some Processes
  11. 11Authority and Security
  12. 12Memory and Budgets
  13. 13Native Programs, Pipes and POSIX-lite
  14. 14Files, Namespaces and Service Trees
  15. 15Devices and Drivers
  16. 16Storage and Updates
  17. 17The Network Stack
  18. 18WiFi
  19. 19Bluetooth
  20. 20The Command Shell and the UNIX Surface
  21. 21The Live Machine
  22. 22Displays, Windows and the Web
  23. 23Apps and Packages
  24. 24Startup, Configuration and Shutdown
  25. 25Checking the System
    1. 25.1Answers from outside the code
    2. 25.2Seeded faults
    3. 25.3Fuzzing every parser of untrusted input
    4. 25.4Models and bounded proofs
    5. 25.5Exhaustive tests of protocol state machines
    6. 25.6Determinism and reproducibility
    7. 25.7The running system under QEMU
    8. 25.8Fast checks and slow checks
    9. 25.9What the checks cannot say
    10. 25.10Design choices
    11. Summary
    12. Where to read next
  26. AGlossary
  27. BReading the Design Documents
  28. CBuilding and Booting erXos
  29. DDependencies and Licenses
  30. ELineage

Chapter 25Checking the System

Background needed. The whole book, chapters 6 and 7 most: the functional core, chokepoint checks, seeded violations and the stack proof are defined there.

A test written by the person who wrote the code shares that person’s picture of what the code should do. If the picture is wrong, the code and the test are wrong together, and the test passes. Think of a runtime that prints a pid differently, a C library whose pthread_cancel cannot wake a blocked thread, or a decoder that accepts one malformed term. Each is invisible to a test that asks only what its author expected.

Most tests anywhere state their expected answers by hand. erXos asks for answers that do not come from its own code. Where an independent implementation of the same contract exists, such as stock OTP or musl’s own tests, the two run side by side and every difference must be explained. Where none exists, a model checker or a bounded proof supplies the answer from a separate description. And every check must first be seen to fail on a fault planted for it.

Section 25.1 covers the oracles and 25.2 the seeded faults. Sections 25.3 to 25.5 cover fuzzing and sanitizers, models and bounded proofs, and exhaustive tests of state machines. Section 25.6 covers determinism, 25.7 the QEMU suites, and 25.8 how the checks are split between every commit and the slower runs.

25.1Answers from outside the code

How does erXos know that lists:sort/1 behaves as it should, in a runtime it has taken apart and rebuilt? It runs OTP’s own tests of lists:sort/1 on erXos and on stock OTP, and compares the results case by case (design.md, Testing and the oracle). The rule behind every check in this section is the project’s: behavior that disagrees with an independent oracle is a bug until it is explained and pinned by a test.

Figure 25.1 shows the oracles erXos uses and what each judges.

stock OTPOTP's suites, case by casemusl's libc-testerXos's C librarybinary_to_term/1the funnelplan9port rcthe command shelllibvtermthe terminal emulator
Figure 25.1.The oracles and what each judges. Each oracle on the left is an implementation erXos did not write. A difference from it fails the check unless a checked-in row explains it.

25.1.1Stock OTP

The same .beam files run on both sides. OTP’s suites for the emulator, kernel, stdlib and compiler groups are compiled once, by stock OTP’s compiler, and run under Common Test, OTP’s test framework. On one side they run in erXos’s system domain, booted under QEMU on one CPU with HVF, Apple’s hypervisor framework. On the other they run on stock OTP of the same release, built on the development host (README.md, Guest and stock oracle). A Ruby tool compares the two case by case (tools/lib/erx/oracle_suites.rb). The README estimates the full run at six to seven hours.

A difference is allowed only when a row of test/oracle/hosted_known_differences/ explains it. Two rows of the emulator group’s table, abridged (the spacing is narrowed and the second reason cut short):

a_SUITE  -  long_timers    failed  cannot run: no distribution; the case starts a peer node
a_SUITE  -  pollset_size   failed  ERTS has no poll set: liberx event sources replace erts_check_io, ...

The first case cannot run in a test domain, because it starts a second Erlang node. The second is a difference the design states: erXos’s ERTS has no poll set. Every row names one of four causes: a difference a design document states, a case that cannot run, a bug that TODO.md names, or a bug in stock OTP.

The comparison fails on any difference no row explains. It also fails on a row that explains nothing, because its case agrees with stock. Without that second rule a table of excuses could only grow: a fixed bug would leave its row behind, to hide the next bug in that case. The hosted runtime, a macOS process, reads the same tables (make check-oracle-hosted runs a fast subset on it), so a case that differs there and not under QEMU is a bug in one of the two.

Stock OTP’s emulator, kernel and stdlib suites, in full, also run alone in an offline Linux container with no route out (make check-oracle-host, design-host-oracle.md). Both runs are Built.

25.1.2musl’s own tests

erXos’s C library is musl, modified to call liberx instead of a UNIX kernel (chapter 13). musl’s maintainers publish libc-test, small C programs that each print an error line for every contract they find broken. make check-oracle runs them under QEMU, each test as a small program of its own, on four CPUs, after OTP’s suites.

The verdicts live in test/conformance/libc-test-verdicts.txt. A test not listed there must pass. Each listed test names the result it must have, the kind of cause and the reason, and a failure also names the source lines of libc-test that its error lines cite. One line, its spacing narrowed:

functional/pthread_cancel  timed_out  fiasco  a thread blocked in a call is not interrupted by pthread_cancel: design-fiasco.md

The kind fiasco marks a difference that follows from running on Fiasco, documented in design-fiasco.md; the other kinds are bug, upstream and cannot-run. The check holds each of the file’s 55 lines exactly. A listed test that starts to pass fails the run. So does one that fails at a source line its row does not list, since that is a new failure hiding behind an old excuse. The run is Built.

25.1.3The funnel against binary_to_term/1

The funnel, the one C function that decodes and judges every frame from another domain (chapter 10, section 10.3), is erXos’s own code facing a hostile writer. Section 10.3.4 introduced its differential test, test/integration/erx_funnel_oracle_test.rb. The test generates random control terms, the same terms mutated, and random payloads. For every control term the funnel accepts, stock ERTS’s binary_to_term/1 must decode the same tuple, element by element. For every payload it accepts, the funnel must charge exactly the heap words that ERTS’s own size pass charges. That matters because the funnel reserves heap before decoding, so an undercount would let a frame overrun its reservation. The test is Built and runs in make check.

25.1.4Further oracles

Two more oracles are Built:

  • plan9port’s rc for the command shell (chapter 20): make check-rc-oracle builds rc from a pinned source and runs the shell’s corpus of scripts under both.
  • libvterm for the terminal emulator (chapter 22): tools/lib/erx/vt_oracle.rb builds libvterm with a small harness, and the emulator’s screens are compared with its, against the differences listed in test/vt/differences.txt.

The network stack’s model, FreeBSD’s TCP/IP stack (chapter 17), supplies the rules that the TCP core’s exploration of section 25.5 checks.

The design names more oracles, each designed and not built: the Open POSIX Test Suite for the POSIX-lite personality, toybox’s own tests, FreeBSD’s utilities for the commands that share their names, FreeBSD’s TCP test scripts for erx_net, and Linux’s F2FS for erXos’s (design.md, Testing and the oracle).

25.2Seeded faults

A check that has never failed may not be running at all. It may read the wrong file, match nothing, or report success on a timeout. So erXos requires each subtle check to be seen failing on the fault it exists for: a removed bound, an off-by-one comparison, a dropped fence. Chapter 6 followed a chokepoint rule’s seed from end to end (section 6.6.3); the other checks follow the same discipline.

A TLA+ model carries its seeds as configurations. The links model, specs/tla/Links.tla, has a constant Fault, and each value changes one rule of the protocol. LinksAnswerFirst.cfg sets one:

\* The target's runtime puts noproc ahead of what is queued on the lane.
\* An answer overtakes a message sent before it.
CONSTANTS
    Budget = 3
    Exported <- Exports
    Fault = "answer_first"
SPECIFICATION Spec
INVARIANTS AnswersAfterSends

With this fault, a runtime answers “no such process” before it delivers the messages that process sent first. The property AnswersAfterSends says every answer about a process arrives after everything the process sent. The roster expects this configuration to fail on exactly that property. The runner matches the property’s name and TLC’s exit status, not a substring of its output, so a parser error, a timeout or another property fails the run.

A litmus test has a twin with its fences, or its acquire and release orderings, removed; the twin must reach the bad outcome the original never reaches (section 25.4.2).

A CBMC harness has seeded defects in test/cbmc/roster.json. Each is one edit of the C core the harness checks, applied to a copy of the core in a scratch directory, and the harness must fail on a property matching a stated pattern. make check confirms that each edit still applies to the tree’s code, so a seed cannot silently stop matching.

A fuzz target can carry seeds too. The shell parser’s target, tools/fuzz/erx_shell_parse.rb, runs the parser as it is and then seven broken copies of it. One allows 257 levels of nesting instead of 256, one does not count $ as a level, and five get the bound on a command’s length wrong. Each copy must be caught by the property aimed at it.

The QEMU gate, which boots the system and judges its console (section 25.7), is seeded by mutating liberx itself. test/integration/qemu_gate_mutant_test.rb builds a probe guest from a copy of the sources in which the Fiasco backend’s message call asks for one byte more than a full message holds. The guest must fail its transcript under QEMU. A control run of an unmutated copy must pass, so the failure is the mutation’s and not the harness’s. Figure 25.2 shows that run, which make check-qemu-mutant starts.

plant one-byte overrun in the backendboot probe built from Mtranscript differs: failed (required)boot probe built from Ctranscript matches: passed (required)mutant testmutated copyclean copyQEMU gate
Figure 25.2.A seeded fault and the check that catches it. The control run matters as much as the mutant: without it, a gate that always failed would pass the test.

make check-native-seeds does the same for the native threads, watchdog, task and interrupt suites. All of these seeds are Built.

One more seed guards the gates themselves. Gates find what they run from files in the tree (section 25.8), so deleting a fuzz target or a rule would make a gate quietly run less. test/host/gate_baseline_test.rb holds a floor under what each gate runs: the sanitizer tests, the QEMU suites, and each chokepoint rule’s and C fuzz target’s least number of seeds. Adding to a gate never touches that file; taking something away must, so every removal is a visible edit.

25.3Fuzzing every parser of untrusted input

What does a parser do with input no test author imagined? In erXos every parser of untrusted input lands with a fuzz target that tries to find out. The boot image and its manifests, executable headers, the funnel, the 9P codec, the shell’s parser, device rings, packets and file system images all have one (design.md, Testing and the oracle). The tree holds over a hundred targets, in tools/fuzz/ and as test/erlang/*_fuzz.erl, and TODO.md lists the parsers still without one.

25.3.1C targets

A C target is two files. tools/fuzz/KIND_fuzz.c is the entry point libFuzzer calls with each input, and tools/fuzz/KIND_target.rb declares the sources it compiles and the seeds that start it. The target for executable headers, elf_target.rb, compiles liberx/elf_plan.c and liberx/exec/load_plan.c, the files the system links. Its seeds, built in Ruby, include valid executables, every prefix of each, and one with an unlisted dynamic tag. It checks more than the absence of a crash. Every position-independent plan the parser accepts is laid out as the loader lays it out, and each step must stay inside its span and never write code.

make check-fuzz compiles each target with -fsanitize=fuzzer,address,undefined and runs it for a fixed number of executions with a recorded random seed, so a failure can be reproduced. The gate refuses a _fuzz.c without its _target.rb, and the reverse.

25.3.2Erlang targets

Most of erXos’s parsers are Erlang. Their targets are Erlang modules, run on stock OTP’s emulator, that generate inputs and check properties. They do not measure coverage; they make up for it with generators that know the format. The shell parser’s target, test/erlang/erx_shell_parse_fuzz.erl, draws from soups of rc’s token fragments and random bytes, mutations of valid scripts, nestings near the 256-level limit, and commands at and over the 4,096-byte bound. Its properties include these:

  • every input parses or fails with a diagnostic, and never raises;
  • a diagnostic names a line and column inside the source, in printable ASCII;
  • a tree has at most 256 levels, counted by a walker of the target’s own;
  • a tree printed back to rc‘s syntax, by a printer of the target’s own, parses to itself.

The last two show the method: a property computed with the parser’s own helpers would share its bugs. Host tools that read untrusted bytes, such as the host link’s frame reader and the QEMU harness’s screenshot decoder, have Ruby targets run the same way. All three kinds are Built.

25.3.3Sanitizers

A buffer overrun by one byte rarely crashes a program, so a fuzzer alone would pass it by; a sanitizer makes the damage visible. erXos’s host tests of C code declare themselves with a comment, # erx-gate: sanitizers, and make check-sanitizers runs every declaring test with AddressSanitizer and UndefinedBehaviorSanitizer. 88 test files carry the line. The gate fails when a C core or a liberx source is named by no declaring test, so new C code cannot escape it. The concurrency tests of the budget, capability, lane and log cores also build under ThreadSanitizer, which reports data races (README.md, Correctness and testing).

macOS has no LeakSanitizer, and the gate says so rather than report leaks as checked. All of this is Built.

25.4Models and bounded proofs

Some bugs need a rare order of events, such as a wake lost because two CPUs each read before the other wrote. Tests seldom hit such an order. For these, erXos checks a description of the protocol against every order of events, within stated bounds.

25.4.1TLA+ models

Three protocol models are Built, in specs/tla/ (design-verification.md, Model suite and runner):

  • Lane.tla, the shared ring between two domains (chapter 10): no record is overwritten before it is read, records are read whole, and no wake is lost.
  • Connection.tla, connections between domains: a connection’s end is handled after every frame it published, and a name is reused only after the earlier connection went down.
  • Links.tla, links, monitors and exits across domains (chapter 10): an answer about a process arrives after everything it sent, and a link two processes make towards each other is never left half made.

Each configuration has one expectation in a roster: pass, a counterexample of one named property, or a deadlock. Besides the seeded faults, reachability configurations claim that some important state is never reached, and expect TLC to refute the claim. They prove the model reaches the paths that matter; a model too constrained to reach them would pass every property vacuously. specs/tla/MAPPING.md maps each property to the design section that owns it and the functions that implement it.

make check-tla runs the suite, and a timeout or tool error fails it. TLC checks the model and nothing more. The mapping is reviewed and tested, not proved: the model says the protocol is right, and the host tests and QEMU suites say the code follows it.

Two further models are designed and not built: the update protocol of chapter 16, with its slots, trials, torn records and resets, and the host link’s sessions (chapter 21).

25.4.2Litmus tests under herd7

TLC treats memory as one store every CPU sees at once. Real CPUs do not: an Arm core may let a later load overtake an earlier store. Whether the lane’s fences are enough is a question about the processor’s memory model. erXos asks it with herd7, a simulator that enumerates every outcome a memory model allows for a small program. Here is the lane’s wake handshake, from test/litmus/lane-wake-fenced.litmus:

AArch64 lane-wake-fenced
"the producer stores wpos (a), fences, loads wake (b); the consumer stores wake, fences, loads wpos: one load sees the other store"
{
0:X1=a; 0:X3=b;
1:X1=a; 1:X3=b;
}
 P0           | P1 ;
 MOV W0,#16   | MOV W0,#17 ;
 STLR W0,[X1] | STLR W0,[X3] ;
 DMB ISH      | DMB ISH ;
 LDR W2,[X3]  | LDAR W2,[X1] ;
exists (0:X2=0 /\ 1:X2=0)

P0, the producer, stores its write position (a), fences, and loads the consumer’s wake flag (b). P1, the consumer, does the mirror image: it sets the wake flag to ask to be woken, fences, and loads the write position. The exists line is the lost wake. Both loads read 0: the producer sees no request to wake anyone, the consumer thinks nothing was written, and both wait. herd7 must report that the outcome never happens under Arm’s model. The twin, lane-wake-unfenced.litmus, is the same program without the two DMB ISH lines, and must reach it. The twin proves that the fences, not the shape of the test, prevent the bad outcome.

test/litmus/ holds sixteen such files, for the lane’s wake and ring positions and the pipe’s lock (chapter 13). Five of the eight pairs test acquire and release orderings rather than fences: a release store keeps every earlier access before it, and an acquire load keeps every later access after it (section 1.7.3), and the twin uses relaxed accesses, which order nothing. One pair is written in C11’s atomics rather than Arm instructions; herd7 runs it under RC11, a repaired model of C11’s atomics. make check-litmus is Built. It checks the litmus programs, not the compiled lane, so a compiler that dropped a fence would go unseen.

25.4.3CBMC harnesses

CBMC checks C code itself. Each harness, one file in test/cbmc/, includes the core’s .c file whole, so it reaches the core’s static helpers. It takes its inputs from functions it declares and never defines, which CBMC treats as “any value” (design-verification.md, CBMC harnesses and runner). The harnesses cover four C17 cores that Fiasco links (chapter 6, section 6.7.1): the budget arithmetic; the capability table’s lookup, rights and slot-closing; the grace tracker; and the page funnel. The grace tracker decides when memory that another CPU might still be reading may be reused. A retired item is stamped with a period. The period completes once every CPU has reported passing a point where it holds no such reference. The page funnel moves pages between a budget’s reserve and the lists of free and released pages, keeping each reserve’s count equal to the pages it holds. A released page goes on its list, stamped by the grace tracker, before the budget it was charged to is refunded, and it is reused only once its period has completed.

A harness computes its expected answer from the contract in the design and the core’s header, never from the core’s own helpers. test/cbmc/roster.json pins CBMC’s version and states each harness’s loop bounds, assumptions and the constructs it cannot check. Every harness runs with unwinding assertions, so a loop that could run past its bound fails the check instead of being cut short in silence. A core’s __builtin_trap, its response to an impossible state, counts as a failed property.

CBMC models one thread, with every memory access indivisible and in program order. A harness over atomic fields therefore lists their ordering as unchecked; litmus tests and ThreadSanitizer cover that ground. make check-cbmc is Built.

25.4.4What each covers

CheckCoversDoes not cover
TLCevery order of a protocol’s steps, within boundsthe code, memory order
herd7every outcome Arm’s model allows for a litmus programthe compiled code
CBMCevery input to a C core, within boundsconcurrency, memory order
ThreadSanitizerdata races in runs that happenwhether a protocol is right
chokepoint checkswhere an operation may appearwhether it is used rightly
stack proofworst-case stack of the C17 coresFiasco’s own C++

The last two rows are the static checks of chapter 6 (section 6.6 and section 6.7), which run in every make check. No row replaces another, and each report states its bounds and assumptions with its result.

25.5Exhaustive tests of protocol state machines

A model checker checks a model; erXos can also explore the real code. Chapter 6’s functional core makes this possible (section 6.3). A protocol’s decisions are a pure function from a state and an event to the next state and a list of actions. A pure function can be called on every event in every state, on the host, with no machine to boot. The project’s rule is that every protocol state machine is tested this way. Four explorations are Built:

  • The TCP core. test/erlang/erx_tcp_explore.erl applies every kind of segment, at every class of sequence and acknowledgement number, and every user request, in every state, breadth first. On every step it checks, among other properties, that no byte is delivered twice or out of order and that every state change is one RFC 9293 allows (chapter 17, section 17.4.5). It runs again with sequence numbers near 2^32, to cross the wrap.
  • The USB hub machine. test/erlang/erx_usb_hub_core_tests.erl explores the hub’s port machine to a fixed point, where no new state appears, for hubs of 1, 2, 7, 8 and 15 ports.
  • The pipe server. test/erlang/erx_pipe_explore.erl drives the pipe server’s decisions with three holders through every order of their events, including notices forged by the wrong holder and repeated after an end is gone (chapter 13, section 13.4).
  • The host link’s 9P bridge. test/erlang/erx_hostlink_9p_exhaustive.erl enumerates every interleaving of a host and one file grant within a small bound: reads, flushes of requests in flight, and replies in any order, well formed or not.

The TCP exploration carries seeds too. Its host test, test/host/erx_tcp_explore_test.rb, replaces one line of the core at a time, such as a reset accepted at rcv_nxt instead of at last_ack_sent. The property named for that fault must catch it, and because the search is breadth first, the trace it reports is a shortest one.

25.6Determinism and reproducibility

Can someone else check that an erXos image was built from the source it names? Only if building the same source twice gives the same bytes. erXos holds itself to that, and to a second property: a boot in a special mode writes the same console transcript every time.

Reproducible images. make check-reproducible builds the production boot image and its medium twice from clean, for QEMU’s disk image and for the Raspberry Pi 4’s SD card image, and requires the results to be identical byte for byte. Both builds pack one build of the kernel, so the check covers erXos’s own code and packing, not a second build of Fiasco (README.md, Correctness and testing). It is Built.

Deterministic mode. A multi-CPU boot is never the same twice: timer interrupts land at different instructions, and threads race. The kernel command-line word erx.det=1 removes those sources (design-fiasco.md, Deterministic mode). The harness runs QEMU on one CPU under TCG, QEMU’s instruction translator, with instruction counting, so the virtual clock advances with instructions executed rather than with real time. The real-time clock starts at a fixed date, and the device tree carries no random seeds. Every domain runs ERTS’s interpreter on one scheduler, so no code depends on where BeamAsm placed it, and the watchdog is off.

tools/lib/erx/deterministic_transcript.rb compares two such boots from erXos’s banner to the command shell’s banner. The span must include the kernel’s report of its timer; without it, two boots would compare equal whether or not the clock counted instructions. The check runs in the QEMU gate and is Built.

25.7The running system under QEMU

Host tests check pieces; only a boot checks the system. A QEMU suite builds an image, boots it in QEMU and judges what the guest writes on its serial console. Each suite is one file in tools/lib/erx/qemu_suites/, 29 in all, from native threads and the watchdog to the system domain, block devices, the display, the kiosk and the Raspberry Pi 4’s board model.

A suite declares the cells it expects, each a configuration such as one CPU or four, or a declared case. It reports every cell as passed, failed, timed_out, partial, not_run or pending (design-build.md, What the gates run). An expected cell the suite did not report becomes not_run, never passed: the inspector’s never-fabricate rule (chapter 21, section 21.2), applied to tests.

Suites run under HVF, except that the landing gate of section 25.8 may move a suite’s multi-CPU cells to a second host, which runs them under TCG. TCG also runs the deterministic transcript, one boot to the shell on one CPU, and the Raspberry Pi 4 suite, whose board model starts its CPUs at a privilege level HVF cannot host. A host whose QEMU lacks either accelerator fails the gate before anything is built, and the gate never falls back from one to the other. A test that passes under one accelerator and fails under the other is a bug until explained.

The gate does not boot a guest again when it already passed on the same inputs (design-build.md, Reusing passing boots). The key is the SHA-256 of everything the guest’s output depends on, from the image and QEMU’s arguments to QEMU itself and the build tools’ code. On a hit, the stored serial log is judged again by the suite’s current checks. A boot with a disk, a network device or a host link talks to the host, so it always runs fresh.

The kernel interface has a conformance harness, tools/erx conformance, which boots one guest per configuration, TCG and HVF at one CPU and four, and reads each case’s verdict from the serial line. The harness is Built. Its roster, test/conformance/roster.txt, holds one pending case, since each case lands with the kernel call whose contract it tests. The conformance suite is designed and not built.

Some hostile cases run in the system domain’s suite: a configured domain asks for services it was not given, and sends atoms the system domain lacks. The full suites of hostile programs, which fill lanes, forge pids and ignore kills, are designed and not built. So is a fuzz campaign against Fiasco’s system calls (design-fiasco.md). Without it, that nothing a domain does can panic Fiasco rests on Fiasco’s own code.

25.8Fast checks and slow checks

The checks in this chapter take from seconds to hours. Running them all on every commit would make each change wait most of a day, and developers who wait that long batch their changes, which makes failures harder to trace. So erXos splits the checks into two tiers.

The landing gate, for every commit, is make check and the QEMU suites the change touches. make check runs offline. It runs each host test file as its own process, with its own log and deadline, including the funnel’s differential test and the explorations of section 25.5. It also runs the chokepoint checks, the stack proof, the generated tree’s tests, and the TLA+ and CBMC runners’ own tests with stand-in tools. A touched suite runs through tools/erx check-qemu --suite NAME, which reuses passing boots.

The full gate runs before a large body of work merges, and in the background on a spare machine; design-build.md and tools/erx call this tier the milestone gate. It is make check-oracle, the sanitizer runs, the fuzz budgets of make check-fuzz, make check-reproducible, make check-cbmc, make check-tla, make check-litmus, and make check-qemu, which boots every suite fresh, one after another. A failure there is fixed forward with a regression test. It does not undo work that passed the landing gate, unless it breaks that gate too. Figure 25.3 shows the two tiers.

a commitmake checktouched QEMU suites, reused bootslandsfull gate, in the backgroundoracle, sanitizers, fuzz budgetsTLA+, CBMC, litmusevery QEMU suite fresh, reproducibilityfailure: fix forward with a test
Figure 25.3.The fast and the slow checks. Every commit waits only for the landing gate; the slow checks run on what has landed, and a failure they find gets a regression test rather than a revert.

The gates run what the tree declares. A chokepoint rule is a file in tools/lib/erx/chokepoint_rules/, a sanitizer test carries its comment line, a QEMU suite is a file in tools/lib/erx/qemu_suites/, and a fuzz target is its pair of files. Adding a chokepoint rule, a sanitizer test, a suite or a fuzz target means adding a file, so parallel work never edits a shared list for them. The litmus tests, the TLA+ configurations and the CBMC harnesses are the exception: each kind is listed in one central file. The baseline of section 25.2 makes removal visible. Every command runs under one runner with a log and a hard deadline, and a check that cannot run, for a missing tool or a timeout, fails; none is reported as skipped and green (design-build.md, Processes and evidence).

25.9What the checks cannot say

Every check here answers a narrower question than its name suggests. TLC checks a model, not the machine code. herd7 checks litmus programs, not the compiled lane. CBMC’s answer holds only within its bounds, for one thread. ThreadSanitizer finds data races but does not show that a protocol’s memory ordering is right. An oracle cannot see a bug it shares with erXos.

Some parts of the system are checked less than the rest. Fiasco’s C++ is outside the stack proof and the chokepoint checks; its thread stacks are measured, not proven (chapter 6, section 6.7.1). What a device does to Fiasco, such as an asynchronous error or a storm of interrupts, is driven by no erXos test. These are limits of the system.

25.10Design choices

Oracles over hand-written expectations. Writing expected answers by hand for OTP’s thousands of cases would restate OTP’s behavior with every misreading built in. Running the suites OTP’s developers wrote, against the runtime they built, borrows decades of their judgment. The price is the known-differences tables, which must stay exact; the stale-row rule keeps them from becoming a place to hide bugs.

Bounded tools over a full proof. A microkernel’s C code can be proved correct against its specification, at a cost seL4’s authors put at about 20 person-years in all, of which about 11 went into the kernel-specific proof (Klein et al., 2009). erXos runs on Fiasco and checks its own code with tools whose cost grows with what they check. They are models of the protocols that are hard to get right, bounded proofs of small C cores, and exhaustive exploration of pure cores. Each says exactly what it covers.

Discovery from files over a central list. A central list of tests is an enumeration every change must remember to update (chapter 6, section 6.1). Files remove that duty. The price is that a deleted file goes unnoticed unless something counts it, which is the baseline’s job (section 25.2), and that removal edits that baseline.

Slow checks off the commit path. erXos accepts that a slow check may find a fault a few commits late, and fixes it forward with a test, rather than make every commit wait six hours for the oracle.

Summary

erXos judges its code against answers it did not write: stock OTP’s suites, musl’s libc-test, ERTS’s own term decoder, plan9port’s rc and libvterm. Every allowed difference is a checked-in row with a cause, and a row that no longer explains a difference fails the run. Every subtle check is first seen to fail on a planted fault. Every parser of untrusted input has a fuzz target built from the sources the system links. TLA+ models, herd7 and CBMC answer for every case within stated bounds, and pure protocol cores are explored state by state on the host. Boot images build byte for byte the same, and a deterministic boot writes the same transcript twice. QEMU suites report every cell’s status and never invent a pass. Fast checks guard every commit; slow ones run on what has landed.

  • design.md, Testing and the oracle: the layers of testing and every oracle, built and designed.
  • design-verification.md: how models are built, mapped to code and run, and the CBMC harness rules.
  • design-host-oracle.md: the offline Linux container that runs stock OTP’s suites.
  • design-build.md, What the gates run and Reusing passing boots: gate discovery, cell statuses and boot reuse.
  • design-fiasco.md, Deterministic mode: the settings behind a byte-identical transcript.
  • design-network-stack.md, The TCP core: exhaustive exploration: the alphabet, abstraction and properties of the TCP exploration.
  • README.md, Correctness and testing: each check’s command, in one list.
  • Leslie Lamport, Specifying Systems: The TLA+ Language and Tools for Hardware and Software Engineers, Addison-Wesley, 2002: TLA+ and TLC, from the language’s author.
  • Jade Alglave, Luc Maranget and Michael Tautschnig, “Herding Cats: Modelling, Simulation, Testing, and Data Mining for Weak Memory”, ACM Transactions on Programming Languages and Systems 36(2), article 7, 2014: the method behind herd7 and its litmus tests.
  • Daniel Kroening and Michael Tautschnig, “CBMC: C Bounded Model Checker”, TACAS 2014, LNCS 8413, pp. 389-391: the tool behind the C harnesses.
  • Gerwin Klein et al., “seL4: Formal Verification of an OS Kernel”, 22nd ACM Symposium on Operating Systems Principles (SOSP), 2009: what a full proof of a microkernel costs and gives.
  • William M. McKeeman, “Differential Testing for Software”, Digital Technical Journal 10(1), 1998: the method of section 25.1.