Live Mutants: A Driver, an Observer, a Correlation Id and a Checker
Check the instrument: plant one wrong decision in running code, and see which oracle notices
Table of Contents
- Checking the instrument
- The model and its oracles
- The four parts
- Rung 2: a defect-free baseline under test.check
- Rung 4: the same probe under a running explorer
- The same mutants, through time
- Changes on a bus
- Code, not state
- The contract
- The changes, as a choreography
- The same rung in other stacks
- Related work
- Next
Checking the instrument
A scale is trusted because a known weight was put on it, not because it has never shown a wrong number. The weight's value is fixed first. The check runs on the scale in service, under load.
Testing has the same order. A model says what the program should do: a merge sort agrees with
sort, a run-length encoding has maximal runs, a shopper is charged the price they were
quoted. Oracles are written from the model. Specs, tests and the implementation come after. An
oracle that has never met a fault has only ever passed, and passing says nothing about whether
it can fail.
A live mutant is the reference weight. One function in the running program is redefined to make one wrong decision, at a recorded time. The name is used here in the sense of live code: the change goes into a process that is already running. It is not the standard mutation-testing sense, where a live mutant is one that survived, which every row below would call killed or one of the four ways of missing. If the oracles hold the model, a check fails. If none does, there are four cases. The changed code never ran. It ran and returned the same answer. Its answer changed but never reached the program's output. Or the output changed and no oracle could see the difference. Only the last is a finding, and it is a finding about the oracle.
The program has to be running. A fault behind a switch read at start-up is mutant schemata (Untch, Offutt and Harrold, ISSTA 1993), and it tests the oracle against one state. A fault set mid-run tests it while the data moves under it, which is the condition the oracle has to work in.
The calibration carries further than the opening. A scale too coarse to resolve a difference is the observer bug below. A weight lighter than the scale's resolution is an equivalent mutant. A scale that reads only totals is a round trip: right sum, wrong composition.
The model and its oracles
Each run here starts from laws written before its mutants were chosen. For the baseline they are
the classic property shapes: an implementation agrees with a simpler one (merge sort with
sort, binary search with a scan), an encoding round-trips and has the shape its definition
requires (maximal runs), a structure matches a model and keeps its invariant (a sorted-vector
set, a two-list queue). For the shop they are statements about money and time: charged as
quoted, stock conserved, the page's catalogue version faithful to the server's within 2,000 ms,
a backorder shown with its date.
Those laws are the spec. A test is one way to run a law; a server invariant, a Bombadil law and a counter on a dashboard are three more, and all four should cite the same name. The mutants below are chosen against the laws, one wrong decision per law, so the question each run answers is which law noticed, and how long it took.
The order matters most when the model is large. The next shop, a bookstore whose catalogue, search index and taxonomy all change while a customer searches, has its model written in TLA+ and checked by TLC before the first handler exists; its invariants are the ones its mutants are built to break (see Next).
The four parts
RIPR is Ammann and Offutt, Introduction to Software Testing 2nd ed. 2016 (doi 10.1017/9781316771273); Li and Offutt TSE 2017 kept for the oracle-strategy argument. Table was four rows against RIPR's four stages with propagation and revealability bundled in one cell; split into five, since a return that never reaches output is not an oracle finding. Observer measures at the function boundary, not program state, and is Voas's PIE estimator (TSE 1992).
A live mutant is a function redefined in a running process. To learn anything from one, four parts have to be named:
| part | job |
|---|---|
| driver | puts the change in, at a chosen moment, and records when |
| observer | at the redefined call site, runs the original and the mutant on the same arguments; counts calls, and calls where they differed; returns the mutant's value. This is Voas's PIE infection estimate (IEEE TSE 18(8), 1992) taken at the function boundary |
| correlation id | a key carried by the driver's record, every observer entry and every verdict, so they can be joined afterwards |
| checker | decides pass or fail, and never reads the observer |
Joined, they give each mutant one outcome per stage of the RIPR model (reach, infection, propagation, revealability; the model is Ammann and Offutt, Introduction to Software Testing, 2nd ed., 2016, and the oracle-strategy argument for the fourth stage is Li and Offutt, IEEE TSE 2017). The observer reads the redefined function's return, so what it counts as an infection is measured at that boundary and not at the program state. A game harness that patches a C++ roguelike has a real case for each:
| outcome | in the runs below | in the roguelike |
|---|---|---|
| never reached | none in these runs | a change to code that runs only when one rare dragon dies deep in the dungeon; a coverage build shows most play never executes it |
| reached, never changed its return | insert-le |
a change to the shop's stock picker on a level where that shop refuses to open |
| changed its return, never reached the program's output | none in these runs | a stock total recomputed from stored quantities before the screen draws, so the picker's answer never shows |
| reached the output, no check noticed | rle-runs-of-two, if the round trip were its only property |
a save round trip that compares only what the game displays, so a field that never displays can change |
| killed | the other mutants | not mutants but real upstream bugs: selling a worn item duplicated it, which fails "an item leaves exactly one place"; a spell healed a monster past its hit dice, which fails "hp at most the maximum of its dice" |
Only the fourth row is a finding about the oracle. The third is a propagation failure and says nothing about the checker, which is why the two are worth separating: bundled, a weak law and an unobservable change look the same. A property-based tester on its own reports only the last row.
Rung 2: a defect-free baseline under test.check
The baseline is about a hundred lines of plain Clojure with the classic property shapes:
run-length encoding (round trip, maximal runs), merge sort (against sort, idempotent,
stable), binary search (against a linear scan), a sorted-vector set and a two-list queue (each
against a model, with its invariant). All eight properties hold.
The observer is a probe that replaces one var:
(defn probe [original mutant log]
(fn [& args]
(if *shadow*
(apply original args) ; the original's own recursive calls skip the probe
(let [expected (binding [*shadow* true] (apply original args))
actual (apply mutant args)]
(swap! log #(-> % (update :calls inc)
(update :infected + (if (same? expected actual) 0 1))))
actual))))
Each mutant is swapped in with with-redefs-fn (what alter-var-root does from a REPL), and
every property runs at a fixed seed. Six mutants, seeds 42, 1 and 7, the same result at each:
| mutant | change | calls | infected | outcome | killed by |
|---|---|---|---|---|---|
| merge-ties-right | <= to < on ties |
36,154 | 4 | killed | merge-sort-stable |
| merge-sort-pairs-unsorted | base case < 2 to < 3 |
533 | 108 | killed | matches sort, idempotent, stable |
| bsearch-skips-last | upper bound starts one short | 113 | 13 | killed | bsearch agrees with scan, set model |
| rle-runs-of-two | runs stop growing at 2 | 266 | 62 | killed | runs are maximal (not the round trip) |
| insert-le | neg? to < 0= in the split |
3,005 | 0 | reached, never infected | none: equivalent here |
| queue-pop-no-rebalance | pop forgets to rebalance | 22 | 6 | killed | queue matches vector model |
Counts are from seed 42. Two rows say more than "killed". rle-runs-of-two still decodes
correctly, so the round trip, the property everyone writes first, cannot see it; only the
invariant on the encoding can. And insert-le was reached three thousand times without once
changing an output: no property should kill it, and a mutation score that counts it as a
survivor is wrong about the tests.
The probe was wrong first
On the first run, merge-ties-right came back "reached, never infected" while
merge-sort-stable killed it. Both cannot be true. The probe compared outputs with
Clojure's =, which ignores metadata, and the stability property tagged each element's
original position in metadata. The checker could see a difference the observer could not.
The fix is one function; the rule is the finding:
The observer's equality must be no coarser than the checker's.
The roguelike's save check has the same weakness from the other side: it compares what the game displays, which is coarser than the item record.
Rung 4: the same probe under a running explorer
The page is a small shop whose catalogue changes underneath it: a data driver reprices pets, sells them out and puts them on backorder on a schedule, and the page has to keep up within 2,000 ms (Bombadil for SPAs covers the explorer). Bombadil explores it for 75 s with 18 temporal laws. Thirty seconds in, one store function in the running server is redefined through a loopback-only route, and the moment it went in is recorded. A reset route undoes it, on every exit path.
| mutant | first changed output | first violation | detection | killed by |
|---|---|---|---|---|
| none | none | |||
| silent-reprice | +348 ms | +368 ms | 20 ms | charged as quoted; server invariants |
| stale-version | +1,469 ms | +1,662 ms | 193 ms | version faithful; server invariants |
| backorder-as-201 | +10,280 ms | +10,502 ms | 222 ms | server invariants |
No violation came before a mutant went in, and the clean run had none. The killers match those
of the same faults set by a switch at start. The new column is the first one: because the
probe records when the mutated call first made a difference, time-to-kill splits into reach
(waiting for the program to exercise the change) and detection (the laws noticing). Detection
was 20 to 222 ms. backorder-as-201 took ten seconds because an order has to land on a
backordered pet before the mutant does anything, the same ten seconds it took as a switch.
silent-reprice, frame by frame. Before the mutant, the catalogue is at v49:
368 ms after it, the first violation: the cart still quotes Waffles at $29.99 while the catalogue says $30.99, totals $290.85, and checkout is in flight. A correct store answers 409, stale price:
The next state: "Order #33 placed: $294.85". Four dollars more than the quote, four Waffles at a dollar each, reported to the shopper as success:
A mutant that did too much
The first silent-reprice returned "no objection" for a stale price. That also skipped the
stock check that came after it, so the unit test showed it killing the oversell invariants as
well. A live mutant changes one decision and lets the rest of the function run; this one now
re-checks the line at the current price.
From a cart to an owned set
b3 fits 1 and 4, b6 fits none, fits-any returns 3 of 4; store tests pass
The cart is a collection the customer builds for one order. The bookstore in the next section adds a collection the customer keeps: things they own, each with attributes, that every product is checked against. The car-parts trade calls the set a garage and the check fitment. In the bookstore it is the Menagerie of saved creatures. A category page returns the whole category, not the results of a search, so the set decides each product's badges and, with the filter on, which products come back:
That is the bookstore's own category page, served by the lab. Each book carries one badge per saved creature, in Menagerie order. Waterproof Bedtime Stories fits two creatures, the fireproof hydra (1) and the wet gremlin (4). Do Not Read After Midnight fits none, so turning on "fits someone in my Menagerie" returns three books of four. Like the search list, the page reads the index; a catalogue change reaches it only through a reindex. A creature the taxonomy no longer has is badged unknown, never fits. Three parties can change a badge: the catalogue changes a book's rules, the taxonomy changes what a creature can be, and the customer changes the set.
The same mutants, through time
lag max 1.006 s, now about 1 s; RIPR cited (Li and Offutt, TSE 2017); Jepsen shading attributed, not fetched
The lab's experiment 018 repeats rung 4 on a bookstore with four parties (Harness first has the setup): a catalogue, a taxonomy and an indexer change on their own schedules while Bombadil plays the customer. Seven mutants, two page faults and a clean control ran three times each for 60 s, with each mutant applied at about 19 s.
Mutation tools report the outcome as a table of killed and survived. To see the waits, the same runs go on a clock, using conventions from three places: Jepsen's plots shade the window where its nemesis is active, a Lamport space-time diagram gives each process its own lane, and RIPR names the stages. The band is the time the mutant is live. ▼ marks the moment it went in, ● the observer's first changed output, ◆ the first server invariant to fail and ■ the first Bombadil property to fail.
In that run of pdp-reads-catalog-head, the detail panel read the catalogue head instead of
the index. Its output changed 0.06 s after the mutant went in, and 55 of 145 calls changed in
all. No invariant failed for another 27 s. A changed snapshot breaks something only when a
detail page is open while the catalogue is ahead of the index, and it took the customer that
long to open one at such a moment.
Three things the clock shows that the table does not:
- The waits come before detection. In all 18 caught runs, the page reported a violation at
about 1 s after the server's invariant failed (0.01 to 1.01 s). Every long wait came earlier: 29 s before
badge-ignores-yearsfirst changed an output in r2, and 27 s between the first changed output and the first broken invariant forpdp-reads-catalog-headin r2. - Reached is not infected.
taxo-change-drops-savedwas called seven times in each run. Its output changed once across all three runs, 33 ms before the end of r2. The table says "survived"; on the clock the problem is reach, which belongs to the driver: a taxonomy change has to touch a saved creature. A stronger oracle would not help. - The server notices first. In all 18 runs, a server invariant failed before or instead of
any page property of its own. Page properties caught 7 runs directly. The other 11 came
through
serverInvariantsHold, a page property that reads the server's verdict, and a kill table would count those as page kills.
Changes on a bus
ledger output and the 48.39 -> 53.23 redelivery mutant reproduced by the lab's tests
The drivers so far play a list of single-product changes at set times. The lab's experiment 019 puts a message bus in front of the shop, so a change can be a rule over the whole catalogue, and every effect of that rule can be read back, replayed and traced to its cause. Four commands over 40 products, ten seconds apart:
{:seed 19
:catalog {:n 40}
:commands [{:at 5000 :op :base-pct :where {:mod 10} :pct 10} ; pid % 10 = 0: base +10%
{:at 15000 :op :sale :where {:mod 5} :pct -20} ; pid % 5 = 0: sale -20%
{:at 25000 :op :end-sales :where :all} ; every sale ends
{:at 35000 :op :base-delta :where {:mod 20} :cents -100}]} ; pid % 20 = 0: base -1.00
The bus is an append-only log of messages with offsets. A pricing consumer turns each command into one change message per product it moved: base, sale and price, before and after, with the command's offset as its cause. Product 20 is one of the two products every command reaches:
#0 5.0 s base-pct pid % 10 = 0 +10% (4 changed) #2 PET-0020 base 21.99 -> 24.19 sale - -> - price 21.99 -> 24.19 #5 15.0 s sale pid % 5 = 0 -20% (8 changed) #9 PET-0020 base 24.19 -> 24.19 sale - -> -20% price 24.19 -> 19.35 #14 25.0 s end-sales all (8 changed) #18 PET-0020 base 24.19 -> 24.19 sale -20% -> - price 19.35 -> 24.19 #23 35.0 s base-delta pid % 20 = 0 -1.00 (2 changed) #24 PET-0020 base 24.19 -> 23.19 sale - -> - price 24.19 -> 23.19 26 messages, 22 set-price steps for the shop, 40 products
The shop doesn't know the bus exists. Each change whose price moved becomes one of the shop's
own set-price steps, carrying :bus-offset, and the shop's change log keeps its arguments. So
every effect in the shop names the message that caused it. That is the data-side version of
the binding check in the three surfaces: an effect with no cause is
a clause that names no spec.
Delivery is at least once, and a consumer skips offsets it has seen. The test for that is calibrated the way this note asks. With the check in place, a redelivered command changes nothing. With it redefined to always answer "not seen", product 10's base rises 10% twice, from 48.39 to 53.23, and the test fails. Four properties hold over random catalogues and commands:
- replaying the change messages rebuilds the final products;
- each product's changes chain, every one starting where the last ended;
- every price is derived from its base and sale;
- the shop driven by the bus ends at the bus's prices.
One bug came out of writing the route. When every command was published before any of its effects, offsets no longer followed time, and a reader resuming from offset N skipped messages. Each command is now handled before the next is published.
Code, not state
A live change goes in at one of two places. Redefining code keeps every state the run reaches
one the program built itself; only a transition is wrong, so a counterexample is a finding.
Writing state (memory through a debugger, a database row, the DOM) can start the run from a
state the program could never reach, and a counterexample from there is a bug in the harness.
The umoria harness's crashes were mostly of that kind: a player outside his own screen panel,
an over-full pack, an uninitialised item. Its fix is the one the shop's data driver already
follows: change the world only through the program's own transitions.
The contract
- C1. The observer's equality is no coarser than the checker's.
- C2. Redefine code; don't write state, or check the program's invariants on any state you write.
- C3. Restore on every exit path, and have the reset path undo every redefinition.
- C4. One mutant at a time.
- C5. A mutant changes one decision and lets the rest run.
- C6. The checker never reads the observer.
- C7. Never change a file a running process was started from; move it aside first. The roguelike's launcher runs its binary through a symlink, and relinking in place would change the file under the live game.
- C8. The observer identifies the program by its process id. Watchers keyed on a tmux session's name ran on into the next session with the same name, and the pane's own process is the shell the game runs under; they now record the game's process id at start.
The changes, as a choreography
The shop run has more parties than the program under test: a catalogue driver, the mutation driver, the server, the page, the explorer, the probe and the checker. Each one changes or reads the system at its own times. Drawn as one protocol, with each arrow a message or a change:
There is no arrow from the probe to the checker. That is C6, drawn. Every reliability finding
in this note sits on one arrow. The silent reprice is on page → store, where the store took
an order at a quote it should have refused. backorder-as-201 is on store → page, where the
status code was wrong. The ten-second reach is the time until the catalogue driver's arrow
and the explorer's arrow both landed on the same pet. The dashed part is the next driver: a customer
whose queries come from what they already own. A list page is then the product of a query and
an index, and the two are moved by different parties.
It is the model the next experiment's drivers were written against. Not projected from: this is a global view of who touches what, and it carries no ordering, no choice and no recursion, so no endpoint behaviour follows from it mechanically. The languages in Related work do projection for real, from a protocol written as a term; the ordered figure in through time is the one here that comes close.
The same rung in other stacks
Library versions (fast-check 4.10, Hypothesis 6.170, prop_check 1.0.2) are as recorded at the time of the runs and are not re-checked here; they are the fastest-decaying claims in the note. Cross-language PBT mutation replication separating generator-dependent from test-dependent outcomes: no prior art found. MuCheck (Le et al., ISSTA 2014) is the single-language precedent for mutating to calibrate properties.
The contract is language-neutral; what changes is how a call site is redefined while the process runs.
| stack | PBT runner | live redefinition | status |
|---|---|---|---|
| Clojure | test.check | with-redefs / alter-var-root over nREPL |
rungs 2 and 4 run |
| TypeScript | fast-check 4.10 | a property swapped on the module object, restored in finally |
rung 2 run: same outcomes and killers at all three seeds |
| Python | Hypothesis 6.170 | unittest.mock.patch on module attributes, restored in finally |
rung 2 run: same outcomes and killers at all three seeds |
| Ruby | prop_check 1.0.2 | define_singleton_method, removed in ensure so lookup falls back to the original |
rung 2 run: same outcomes and killers at all three seeds |
The TypeScript port made a calls count about ten times lower (fast-check's default arrays stop
at ten elements; test.check's grow) and the same outcome in every cell. The Ruby port's shrinker
barely shortens arrays, so its witnesses are longer (eleven zeros for rle-runs-of-two, not
three fours), and the verdicts are the same. Counts are a property
of the generator; the cells and the killers are a property of the tests.
C++ has no live redefinition, and the roguelike harness used two weaker forms. Each mutant was a
patch built into its own binary, and every arm loaded the same immutable save at the same seed:
a mutant per build rather than per call site, still keeping every state one the program built,
at the cost of a rebuild and no swap mid-run. And one call site was replaced by an injected
library at process start (DYLD_INSERT_LIBRARIES on an ad-hoc-signed copy, on macOS): the C
form of redefining a function, but only before the run begins.
Next
- Apply times of 10 s and 50 s, twice each, before the detection lags are more than one sample.
- The browser-side version: a page function patched over the DevTools protocol while Bombadil drives the same Chrome.
- Rung 4 in the other stacks, behind Express, Django and Rails versions of the shop.
- A taxonomy driver aimed at saved creatures, so
taxo-change-drops-savedgets inputs it can damage (through time). - The same clock drawn live from an event stream while a run is going, not afterwards from its files.
- Checking the observer before blaming the property. In a registered-prediction run in the
roguelike, every failure the agents reported was the observer's: a
-more-prompt hid the status line, and they read a stale armour class. - When to harden as work moves between agent contexts is in When hardening comes due.