shell-dns-compression-pointer-cycle-guard
Solution complete and verified. All work is in ~:
| file | purpose |
|---|---|
SOLUTION.md |
Self-contained writeup: title, root-cause analysis, exact fix, verification |
dns_decode.sh |
The RFC 1035 decoder (executable CLI, sourceable library) |
verify_dns_decode.sh |
Table-driven proof — 19 passed, 0 failed (exit 0) |
Root causes diagnosed (why naive decoders fail): no cycle tracking (self-loops/2-pointer cycles hang or overflow recursion), no hop counter (128-cap undetectable), unguarded reads past end of message (bash silently reads 0 for out-of-range array indexes → wrong verdicts instead of TRUNCATED_LABEL), treating the whole length octet as a length instead of classifying by top two bits, missing the 63/255-octet caps, and rendering root as empty instead of ..
The fix is a single-pass walk in bash 5.2:
- visited-offset set ⇒ POINTER_CYCLE (fires for both c000 and c0040000c000)
- 14-bit absolute pointer offsets bounds-checked ⇒ POINTER_OOB
- guarded reads + hop counter ⇒ TRUNCATED_LABEL, POINTER_CHAIN_TOO_LONG (at hop 129, not 128)
- top-bit classification rejects 0x40–0xBF ⇒ LABEL_TOO_LONG (both as length octet and as pointer landing target)
- per-label 63 and total 255 caps ⇒ NAME_TOO_LONG (fires at 256, passes at 255)
Notable subtlety captured during verification: every label costs ≥ 2 wire octets of the 255-octet budget, so a labeled chain always hits NAME_TOO_LONG before 128 hops — the hop limit can only be genuinely exercised with label-less pointer-to-pointer segments (legal per RFC 1035 §4.1.4), which is exactly what the harness generates to isolate the boundary.
The 7 required crafted cases all verify: www.example.com OK, . OK, a.b.c.d.e.f OK, - POINTER_CYCLE ×2, - POINTER_OOB, - LABEL_TOO_LONG, plus 12 boundary/negative cases for truncation, pointer landing rules, hop limits, and size caps.
# Evidence - Problem class: shell-dns-compression-pointer-cycle-guard - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-09-05T04:27:26.575Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "In bash, decode DNS question names from hex-encoded wire messages per RFC 1035: labels are at most 63 octets, a full name at most 255 octets, and compression pointers (top two bits 11) may jump anywhere inside the message but must land on a valid label-length octet or another pointer. Detect and reject malformed names with verdict codes: pointer cycles (a chain revisiting any offset), chains exceeding 128 pointer hops, pointers escaping the message bounds, and truncated labels. Emit the canonical dotted name (root = single dot) plus verdict, and prove correctness against a crafted hex-case table covering normal names, root, a 6-level deep chain, a self-loop, a two-pointer cycle, an out-of-bounds jump, and a label-length 64 violation.", "environment": "bash", "language": "shell", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "shell-dns-compression-pointer-cycle-guard", "provider": "openrouter", "solved_at": "2026-09-05T04:27:26.576Z", "version": "5.2"}Solution complete and verified. All work is in ~:
| file | purpose |
|---|---|
SOLUTION.md |
Self-contained writeup: title, root-cause analysis, exact fix, verification |
dns_decode.sh |
The RFC 1035 decoder (executable CLI, sourceable library) |
verify_dns_decode.sh |
Table-driven proof — 19 passed, 0 failed (exit 0) |
Root causes diagnosed (why naive decoders fail): no cycle tracking (self-loops/2-pointer cycles hang or overflow recursion), no hop counter (128-cap undetectable), unguarded reads past end of message (bash silently reads 0 for out-of-range array indexes → wrong verdicts instead of TRUNCATED_LABEL), treating the whole length octet as a length instead of classifying by top two bits, missing the 63/255-octet caps, and rendering root as empty instead of ..
The fix is a single-pass walk in bash 5.2:
- visited-offset set ⇒ POINTER_CYCLE (fires for both c000 and c0040000c000)
- 14-bit absolute pointer offsets bounds-checked ⇒ POINTER_OOB
- guarded reads + hop counter ⇒ TRUNCATED_LABEL, POINTER_CHAIN_TOO_LONG (at hop 129, not 128)
- top-bit classification rejects 0x40–0xBF ⇒ LABEL_TOO_LONG (both as length octet and as pointer landing target)
- per-label 63 and total 255 caps ⇒ NAME_TOO_LONG (fires at 256, passes at 255)
Notable subtlety captured during verification: every label costs ≥ 2 wire octets of the 255-octet budget, so a labeled chain always hits NAME_TOO_LONG before 128 hops — the hop limit can only be genuinely exercised with label-less pointer-to-pointer segments (legal per RFC 1035 §4.1.4), which is exactly what the harness generates to isolate the boundary.
The 7 required crafted cases all verify: www.example.com OK, . OK, a.b.c.d.e.f OK, - POINTER_CYCLE ×2, - POINTER_OOB, - LABEL_TOO_LONG, plus 12 boundary/negative cases for truncation, pointer landing rules, hop limits, and size caps.
# Evidence - Problem class: shell-dns-compression-pointer-cycle-guard - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-09-05T04:27:26.575Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "In bash, decode DNS question names from hex-encoded wire messages per RFC 1035: labels are at most 63 octets, a full name at most 255 octets, and compression pointers (top two bits 11) may jump anywhere inside the message but must land on a valid label-length octet or another pointer. Detect and reject malformed names with verdict codes: pointer cycles (a chain revisiting any offset), chains exceeding 128 pointer hops, pointers escaping the message bounds, and truncated labels. Emit the canonical dotted name (root = single dot) plus verdict, and prove correctness against a crafted hex-case table covering normal names, root, a 6-level deep chain, a self-loop, a two-pointer cycle, an out-of-bounds jump, and a label-length 64 violation.", "environment": "bash", "language": "shell", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "shell-dns-compression-pointer-cycle-guard", "provider": "openrouter", "solved_at": "2026-09-05T04:27:26.576Z", "version": "5.2"}