Reads-From Fuzzing — coverage-guided concurrency exploration.
Adaptation of Meng et al., "Greybox Fuzzing for Concurrency Testing" (ASPLOS 2024) to the BEAM. Treats reads-from edges between concurrent operations as the coverage domain (the same role branches play in AFL), tracks which edges have been observed across iterations, and biases iteration scheduling toward seeds that produce new edges.
Pairs with Lockstep.Strategy.PCT (or any other strategy): RFF
drives which iterations to run, the strategy drives which
schedule each iteration explores.
What is a reads-from edge?
In a controlled-concurrency execution, every operation on shared
state is a write or a read. A reads-from edge is the pair
(write_event, read_event) where the read returned the value the
write set. For Lockstep, the shared state is:
- ETS tables —
:ets.insert/:ets.lookupand friends - Atomics —
:atomics.put/add/exchange/compare_exchange/:atomics.get - persistent_term —
:persistent_term.put/:get
Two iterations that exercise different reads-from edges have meaningfully different concurrent behavior, even if their schedules look superficially similar. Two iterations that hit the same edges are redundant from a bug-finding perspective.
Why this is competitive
The technique has a paper (Meng et al., ASPLOS'24) but no production tool in any concurrency-testing ecosystem. Coyote ships PCT and QL; Fray ships PCT and POS and SURW; Concuerror ships DPOR. None ship RFF. Lockstep + RFF is the first.
v1 limitations (planned for v2)
This v1 ships the coverage extraction + seed-biased
exploration pieces. The full ASPLOS'24 design also includes
schedule-prefix mutation — taking a productive prefix and
diverging from a chosen point with a different scheduling
decision. That requires deeper controller surgery (record the
full sequence of pick/2 decisions, replay a prefix of them
via the Replay strategy, then mutate the next decision). v2 will
add it; v1 demonstrates the technique on smaller search spaces.
Coverage signature in v1 is
{resource_class, resource, writer_actor_position, reader_actor_position}.
Actor positions come from the trace's spawn order so the
signature is stable across iterations even though raw pids vary.
Usage
result =
Lockstep.RFF.run(
fn -> Demo.race_body() end,
iterations: 5_000,
seed: 1,
strategy: :pct,
max_steps: 3_000,
iter_timeout: 30_000,
suite: "rff_demo"
)
IO.puts("\n iterations: #{result.total_iterations}")
IO.puts(" unique edges: #{MapSet.size(result.seen_edges)}")
IO.puts(" iters w/ new cov: #{result.iterations_with_new_coverage}")
IO.puts(" first bug at iter: #{inspect(result.first_bug_at_iter)}")Returns :ok if no bug found; raises Lockstep.BugFound (with
full schedule) on first bug, just like Lockstep.Runner.run/2.
Summary
Functions
Extract reads-from edges from a trace. Each edge is a tuple of
{resource_class, resource_id, writer_actor, reader_actor}.
Used internally by run/2; exposed for testing and for users
who want to compute coverage from a saved trace.
Run a coverage-guided fuzzing campaign. Same shape as
Lockstep.Runner.run/2, but iteration scheduling is biased toward
seeds that produce new reads-from coverage.
Types
@type t() :: %Lockstep.RFF{ edges_per_iter: [non_neg_integer()], first_bug_at_iter: non_neg_integer() | nil, first_bug_seed: integer() | nil, iterations_with_new_coverage: non_neg_integer(), productive_seeds: [{seed :: integer(), edges_added :: pos_integer()}], seen_edges: MapSet.t(), total_iterations: non_neg_integer() }
Functions
@spec coverage_edges(Lockstep.Trace.t()) :: MapSet.t()
Extract reads-from edges from a trace. Each edge is a tuple of
{resource_class, resource_id, writer_actor, reader_actor}.
Used internally by run/2; exposed for testing and for users
who want to compute coverage from a saved trace.
Conservative: any (writer, reader) pair on the same resource
with writer_step < reader_step produces an edge, regardless of
intervening writes. False positives (extra edges) inflate the
coverage map but don't bias toward worse exploration.
Run a coverage-guided fuzzing campaign. Same shape as
Lockstep.Runner.run/2, but iteration scheduling is biased toward
seeds that produce new reads-from coverage.
Raises Lockstep.BugFound on the first bug, with full schedule
attached (same exception shape as Runner.run/2).