dhcp: concurrency and progress fuzzers for the DORA client and lease DB
The existing fuzzers cover codec crash-safety; these cover the pure state machines' behaviour under adversarial interleaving -- the axis a deterministic, I/O-free machine is actually exposed to. All three thread immutable state and feed time explicitly.
fuzz_client drives fuzzed drop/duplicate/reorder/forge streams of DHCPOFFER/ACK/NAK plus timer ticks through the DORA machine against an exact model: totality and exact transitions, transaction-id correlation (a foreign-xid or wrong-phase reply is ignored, never advances), bounded retransmit with no livelock (at most attempts-1 resends per phase before Failed; a junk flood neither consumes the budget nor keeps the client alive past its ticks), and the capped 4->64s backoff.
fuzz_server drives fuzzed interleavings of many clients' DISCOVER/REQUEST/RELEASE/DECLINE against one lease database and checks, after every step: no double allocation (leases have pairwise-distinct addresses), database consistency (holder/for_client/addr_allocated agree with entries), model agreement (the committed leases match the database), offer-commits-nothing, and release/decline frees for reuse. A Claim op forces several clients onto a few hot addresses so the interleaving reliably exercises the already-allocated guard.
fuzz_lease pins reuse/renewal (extend keeps the address and client while restarting the window; an expired lease is cleanly reassigned) and drives the database to N leases (default 100k, overridable with DHCP_SCALE_N), asserting O(log n) allocate (alloc/op doubling ratio under 3) and lookup (worst-case comparisons under the log bound), O(n) memory at a small per-entry cost, and a leak-free return to baseline once every lease is removed or GC'd. At a true 1,000,000 leases: alloc ratio 1.21, 21 comparisons/lookup (log bound 68), 28 words/entry, 3 words residual after removal, 0 after GC.
Each fuzzer was verified to fail against a broken core: uncapped retransmit and a dropped xid check (client); a disabled already-allocated guard (server, caught as '2 leases but 1 distinct address'); a leaking remove (1.4M words residual) and an O(n) insert (alloc ratio 5.5) (lease).
dhcp: a client that has asked enough reverts to INIT
A spent retransmission budget ended the exchange: timer answered Failed
and left the client in SELECTING or REQUESTING, holding a half-finished
exchange nothing could take further. RFC 2131 s.3.1 step 5 is explicit
about the DHCPREQUEST -- "If the client receives neither a DHCPACK or a
DHCPNAK message after employing the retransmission algorithm, the client
reverts to INIT state and restarts the initialization process" -- and
s.3.2 step 3 says the same of a client verifying a remembered address.
For the DHCPDISCOVER the specification gives no bound at all: s.4.1
bounds the delay between retransmissions and not their number, and s.3.1
step 3 says only that the client times out and retransmits. Either way
a client that stops asking has recorded nothing, which is INIT.
So the pure machine no longer stops: it goes back to the start, drops
what it was holding, and hands the driver Restart, which already meant
begin again with a fresh transaction id. Figure 5 has no arrow that
ends a client's life, and now neither has this reducer, bar the two
lease-holding phases the next commit is about.
When to stop asking is a policy, and it moves to the driver that has a
clock and a user to answer to. Dhcp_eio.drive, lease and renew take a
~sends budget, eight by default -- a DORA's two phases at the four
attempts s.3.1 step 5 gives as its example -- and lease shares one
budget across every restart, so a client nobody answers stops rather
than beginning again for ever. A caller that wants the old timing
passes ~sends:4.
Two pins retired, two left.
dhcp: concurrency and progress fuzzers for the DORA client and lease DB
The existing fuzzers cover codec crash-safety; these cover the pure state machines' behaviour under adversarial interleaving -- the axis a deterministic, I/O-free machine is actually exposed to. All three thread immutable state and feed time explicitly.
fuzz_client drives fuzzed drop/duplicate/reorder/forge streams of DHCPOFFER/ACK/NAK plus timer ticks through the DORA machine against an exact model: totality and exact transitions, transaction-id correlation (a foreign-xid or wrong-phase reply is ignored, never advances), bounded retransmit with no livelock (at most attempts-1 resends per phase before Failed; a junk flood neither consumes the budget nor keeps the client alive past its ticks), and the capped 4->64s backoff.
fuzz_server drives fuzzed interleavings of many clients' DISCOVER/REQUEST/RELEASE/DECLINE against one lease database and checks, after every step: no double allocation (leases have pairwise-distinct addresses), database consistency (holder/for_client/addr_allocated agree with entries), model agreement (the committed leases match the database), offer-commits-nothing, and release/decline frees for reuse. A Claim op forces several clients onto a few hot addresses so the interleaving reliably exercises the already-allocated guard.
fuzz_lease pins reuse/renewal (extend keeps the address and client while restarting the window; an expired lease is cleanly reassigned) and drives the database to N leases (default 100k, overridable with DHCP_SCALE_N), asserting O(log n) allocate (alloc/op doubling ratio under 3) and lookup (worst-case comparisons under the log bound), O(n) memory at a small per-entry cost, and a leak-free return to baseline once every lease is removed or GC'd. At a true 1,000,000 leases: alloc ratio 1.21, 21 comparisons/lookup (log bound 68), 28 words/entry, 3 words residual after removal, 0 after GC.
Each fuzzer was verified to fail against a broken core: uncapped retransmit and a dropped xid check (client); a disabled already-allocated guard (server, caught as '2 leases but 1 distinct address'); a leaking remove (1.4M words residual) and an O(n) insert (alloc ratio 5.5) (lease).
dhcp: fuzz the transaction id and the answers, not just the absence of a crash
The two state-machine properties hardwired one transaction id and
matched every outcome, so they proved only that neither machine raises:
an xid mismatch was never generated, and a client that took the wrong
arrow -- or a server that offered an address it does not own -- passed.
The id is now generated, and four properties say what the answer must
be with the fuzzed option list still in the message. A reply for a
foreign xid is Wait whatever it carries (RFC 2131 s.4.4.1, and
Client.incoming): the correlation is made before an option is read, so
an off-path forger who cannot guess the id moves nothing. Figure 5's
three arrows -- OFFER to Send, ACK to Obtained, NAK to Restart -- hold
with arbitrary options riding along, so an unknown option cannot cost a
transition. On the server side, an OFFER's yiaddr is inside the
configured range whatever the DISCOVER asks for, and repeating a
DISCOVER leaves both the lease count and the pool's free count alone
(s.4.3.1: an offer reserves nothing), so no client drains the pool by
asking.
Each property was checked against a deliberate mutation: accepting any
xid, rejecting the client's own, offering the server's own address, and
committing a lease on the offer.
dhcp: fix O(n^2) pool fill and constant client-id hint in usable_addr
The lease-DB scale fuzzer found free-IP selection dies at scale. Two defects in Lease.usable_addr, neither fork-specific: (1) the client-identifier hint was the constant 1805, so every client that sends an RFC 2132 option-61 identifier -- most modern clients -- hashed to one address, collided, and fell to the linear scan; (2) that fallback rescanned the range from low on every call, so filling the pool was O(size^2), each of size allocations rewalking the dense allocated-from-low prefix.
Hash the identifier so distinct client-id clients spread across the range, as the hardware-address hint already does, and make the fallback probe forward from the per-client hint, wrapping across the range (open addressing). A partially-loaded pool is then served in a bounded number of probes per client. The address a client is offered when its hint is free is unchanged, so per-client affinity is preserved and the existing tests still pass.
fuzz_lease gains a regression test that fills a range to 80% load through usable_addr with distinct client identifiers and asserts the fill cost is sub-quadratic (doubling the range at most triples the cost). Verified to fail against the constant hint: ratio 3.98, ~104M words at size 8000, versus ratio 2.15 and ~1.4M words after the fix. Complete exhaustion of any probe-based allocator is inherently super-linear, so the load stops short of full.
dhcp: fix O(n^2) pool fill and constant client-id hint in usable_addr
The lease-DB scale fuzzer found free-IP selection dies at scale. Two defects in Lease.usable_addr, neither fork-specific: (1) the client-identifier hint was the constant 1805, so every client that sends an RFC 2132 option-61 identifier -- most modern clients -- hashed to one address, collided, and fell to the linear scan; (2) that fallback rescanned the range from low on every call, so filling the pool was O(size^2), each of size allocations rewalking the dense allocated-from-low prefix.
Hash the identifier so distinct client-id clients spread across the range, as the hardware-address hint already does, and make the fallback probe forward from the per-client hint, wrapping across the range (open addressing). A partially-loaded pool is then served in a bounded number of probes per client. The address a client is offered when its hint is free is unchanged, so per-client affinity is preserved and the existing tests still pass.
fuzz_lease gains a regression test that fills a range to 80% load through usable_addr with distinct client identifiers and asserts the fill cost is sub-quadratic (doubling the range at most triples the cost). Verified to fail against the constant hint: ratio 3.98, ~104M words at size 8000, versus ratio 2.15 and ~1.4M words after the fix. Complete exhaustion of any probe-based allocator is inherently super-linear, so the load stops short of full.
dhcp: concurrency and progress fuzzers for the DORA client and lease DB
The existing fuzzers cover codec crash-safety; these cover the pure state machines' behaviour under adversarial interleaving -- the axis a deterministic, I/O-free machine is actually exposed to. All three thread immutable state and feed time explicitly.
fuzz_client drives fuzzed drop/duplicate/reorder/forge streams of DHCPOFFER/ACK/NAK plus timer ticks through the DORA machine against an exact model: totality and exact transitions, transaction-id correlation (a foreign-xid or wrong-phase reply is ignored, never advances), bounded retransmit with no livelock (at most attempts-1 resends per phase before Failed; a junk flood neither consumes the budget nor keeps the client alive past its ticks), and the capped 4->64s backoff.
fuzz_server drives fuzzed interleavings of many clients' DISCOVER/REQUEST/RELEASE/DECLINE against one lease database and checks, after every step: no double allocation (leases have pairwise-distinct addresses), database consistency (holder/for_client/addr_allocated agree with entries), model agreement (the committed leases match the database), offer-commits-nothing, and release/decline frees for reuse. A Claim op forces several clients onto a few hot addresses so the interleaving reliably exercises the already-allocated guard.
fuzz_lease pins reuse/renewal (extend keeps the address and client while restarting the window; an expired lease is cleanly reassigned) and drives the database to N leases (default 100k, overridable with DHCP_SCALE_N), asserting O(log n) allocate (alloc/op doubling ratio under 3) and lookup (worst-case comparisons under the log bound), O(n) memory at a small per-entry cost, and a leak-free return to baseline once every lease is removed or GC'd. At a true 1,000,000 leases: alloc ratio 1.21, 21 comparisons/lookup (log bound 68), 28 words/entry, 3 words residual after removal, 0 after GC.
Each fuzzer was verified to fail against a broken core: uncapped retransmit and a dropped xid check (client); a disabled already-allocated guard (server, caught as '2 leases but 1 distinct address'); a leaking remove (1.4M words residual) and an O(n) insert (alloc ratio 5.5) (lease).