shell-ipv4-fragment-overlap-reassembly-rfc5722-exactness
Done. The verified solution is written to ~/SOLUTION.md (self-contained: root-cause analysis, full working module, test harness, and verification transcripts). Companion files: ~/ipv4_reasm.sh and ~/test_reasm.sh.
Root cause (failure modes of a naive reassembler):
1. Offset-write reassembly accepts overlaps (last-writer-wins). RFC 5722 requires discarding the entire datagram on any overlap, including byte-identical duplicates.
2. Demux key omits src, conflating interleaved datagrams that share (dst,id,proto).
3. Blind trust in the MF=0 fragment — multiple conflicting last fragments and non-final fragments past the declared end are accepted.
4. Unbounded, non-expiring reassembly queue → memory exhaustion / tiny-fragment amplification.
5. No RFC 791 structural validation (8-byte alignment, non-final length multiple of 8, 65535 cap).
Fix: a strict, keyed, interval-based reassembler. Every datagram keeps disjoint half-open [start,end) intervals; a new fragment is tested for intersection, and the whole datagram is dropped with the exact intersecting range reported. Completion requires the intervals to tile [0, declared_end) exactly. Key = full (src,dst,id,proto) tuple. Tunables FRAG_TTL, MAX_DATAGRAMS, MAX_FRAGS, MAX_BYTES cover expiry/eviction/amplification.
Rules emitted: rfc5722-overlap, conflicting-last, exceeds-declared-length, invalid-fragment, lifetime-expired, queue-eviction, fragment-limit, plus INCOMPLETE at EOF.
Verification: 14/14 tests pass, and the code embedded in SOLUTION.md is byte-identical to the tested files and passes when extracted and re-run:
PASS out-of-order reassembly PASS fragment limit
PASS identical duplicate PASS queue eviction
PASS partial overlap -> range PASS lifetime expiry
PASS conflicting last fragment PASS interleaved distinct sources
PASS MF=1 past declared end PASS unfragmented datagram
PASS MF=0 below buffered data PASS non-final not multiple of 8
PASS offset not multiple of 8 PASS missing payload field rejected
14 passed, 0 failed
shellcheck -S warning is clean. Note: two datagrams genuinely in flight with an identical 4-tuple are indistinguishable by definition; the full-tuple key plus FRAG_TTL enforces RFC 791's uniqueness assumption, so the "different sources" case demultiplexes correctly.
# Evidence - Problem class: shell-ipv4-fragment-overlap-reassembly-rfc5722-exactness - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-30T10:09:27.969Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement an IPv4 reassembly module that follows RFC 791 as amended by RFC 5722: any overlapping fragment, including a byte-identical duplicate, silently discards the entire datagram. Feed it a captured fragment stream, reassemble the well-formed datagrams exactly, and for every malformed datagram emit the RFC-mandated decision, the rule that fired and the byte ranges that overlapped; cover last-fragment FL=0 abuse, tiny-fragment amplification, out-of-order and duplicate arrival, fragment lifetime expiry and reassembly-queue eviction pressure. Include two datagrams from different sources sharing one (src, dst, id, protocol) tuple that interleave and must never be conflated.", "environment": "bash", "language": "shell", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "shell-ipv4-fragment-overlap-reassembly-rfc5722-exactness", "provider": "openrouter", "solved_at": "2026-09-30T10:09:27.969Z", "version": "5.2"}Done. The verified solution is written to ~/SOLUTION.md (self-contained: root-cause analysis, full working module, test harness, and verification transcripts). Companion files: ~/ipv4_reasm.sh and ~/test_reasm.sh.
Root cause (failure modes of a naive reassembler):
1. Offset-write reassembly accepts overlaps (last-writer-wins). RFC 5722 requires discarding the entire datagram on any overlap, including byte-identical duplicates.
2. Demux key omits src, conflating interleaved datagrams that share (dst,id,proto).
3. Blind trust in the MF=0 fragment — multiple conflicting last fragments and non-final fragments past the declared end are accepted.
4. Unbounded, non-expiring reassembly queue → memory exhaustion / tiny-fragment amplification.
5. No RFC 791 structural validation (8-byte alignment, non-final length multiple of 8, 65535 cap).
Fix: a strict, keyed, interval-based reassembler. Every datagram keeps disjoint half-open [start,end) intervals; a new fragment is tested for intersection, and the whole datagram is dropped with the exact intersecting range reported. Completion requires the intervals to tile [0, declared_end) exactly. Key = full (src,dst,id,proto) tuple. Tunables FRAG_TTL, MAX_DATAGRAMS, MAX_FRAGS, MAX_BYTES cover expiry/eviction/amplification.
Rules emitted: rfc5722-overlap, conflicting-last, exceeds-declared-length, invalid-fragment, lifetime-expired, queue-eviction, fragment-limit, plus INCOMPLETE at EOF.
Verification: 14/14 tests pass, and the code embedded in SOLUTION.md is byte-identical to the tested files and passes when extracted and re-run:
PASS out-of-order reassembly PASS fragment limit
PASS identical duplicate PASS queue eviction
PASS partial overlap -> range PASS lifetime expiry
PASS conflicting last fragment PASS interleaved distinct sources
PASS MF=1 past declared end PASS unfragmented datagram
PASS MF=0 below buffered data PASS non-final not multiple of 8
PASS offset not multiple of 8 PASS missing payload field rejected
14 passed, 0 failed
shellcheck -S warning is clean. Note: two datagrams genuinely in flight with an identical 4-tuple are indistinguishable by definition; the full-tuple key plus FRAG_TTL enforces RFC 791's uniqueness assumption, so the "different sources" case demultiplexes correctly.
# Evidence - Problem class: shell-ipv4-fragment-overlap-reassembly-rfc5722-exactness - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-30T10:09:27.969Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement an IPv4 reassembly module that follows RFC 791 as amended by RFC 5722: any overlapping fragment, including a byte-identical duplicate, silently discards the entire datagram. Feed it a captured fragment stream, reassemble the well-formed datagrams exactly, and for every malformed datagram emit the RFC-mandated decision, the rule that fired and the byte ranges that overlapped; cover last-fragment FL=0 abuse, tiny-fragment amplification, out-of-order and duplicate arrival, fragment lifetime expiry and reassembly-queue eviction pressure. Include two datagrams from different sources sharing one (src, dst, id, protocol) tuple that interleave and must never be conflated.", "environment": "bash", "language": "shell", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "shell-ipv4-fragment-overlap-reassembly-rfc5722-exactness", "provider": "openrouter", "solved_at": "2026-09-30T10:09:27.969Z", "version": "5.2"}