REVIEW 5 major objections 5 minor 43 references
Extremal Testing for Network Software using LLMs
T0 review · 5 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read A two-prompt LLM recipe—elicit validity constraints, then generate inputs that violate them—found new bugs in widely used DNS, HTTP, and BGP implementations.
desk verdict A cheap, promising two-stage LLM prompting trick that found a few real bugs, but the evidence for the headline claim is a handful of reports and no artifact. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing mechanism is a two-stage prompting protocol the paper calls chain-of-thought prompting: first the LLM lists validity constraints for a protocol feature, then a second prompt asks for test cases violating one or more of those constraints. A third, optional stage asks the LLM to produce either the test harness code or, in a variant, filtering code that rejects invalid input before it reaches the implementation. The invalid-input-only design finesses the oracle problem: the expected answer is always rejection, so any implementation behavior other than rejection on a truly invalid input is a discrepancy. Differential testing across multiple independent implementations then converts spec-interpretation disagreements into candidate bugs. The method is deliberately contrasted with boundary value analysis, which also probes edges of ranges but restricts itself to simple range constraints and does not use an LLM to elicit a richer constraint set.
What would settle it
Rerun the two-step method on a protocol with a fully formal grammar, such as DNS under RFC 1035, and independently check every generated 'invalid' input against the specification. The authors' own Test 3, 'exam!ple.com', is a live case: RFC 1035's grammar does not explicitly enumerate '!' as forbidden, so if the reported BIND/NSD divergence rests on a constraint the RFC does not actually state, the assumption that LLM-elicited constraints proxy the specification is falsified for one of the paper's own headline bugs.
Extended reading notes
Core claim
The paper's central claim is that LLM-driven extremal testing works: in two stages, an LLM can enumerate the validity conditions that an input to a well-known protocol must satisfy, and then translate violations of those conditions into concrete tests, producing a stream of subtle invalid inputs that existing fuzzing and symbolic-execution tools are unlikely to generate. The authors show this by finding previously unreported behavioral divergences across five HTTP servers, four DNS authoritative servers, three BGP implementations, and two graph libraries. Examples include BIND and NSD accepting a DNS label containing '!' despite the RFC grammar, Caddy responding 500 to a %00-encoded URI where peers return 400, GoBGP accepting an invalid AS-path regex, Batfish accepting negative local-preference, and Boost returning the maximum double value instead of the correct shortest-path length. The claim is that these are new bugs, found with minimal networking expertise, and that focusing on invalid inputs finesses the oracle problem because every test's expected outcome is rejection.
Load-bearing premise
The method assumes the LLM's stated validity constraints match the protocol's real specification, so an input the LLM calls invalid truly is invalid and rejection is the only correct outcome; if a constraint is hallucinated or misread, the test can be misclassified and a divergence misreported as a bug.
Editorial extensions
If this is right
- The prompts are nearly templatized, so even testers without protocol expertise can generate extremal suites quickly.
- For any truly invalid input, the correct behavior is rejection, so generated tests double as oracle-free checks: any implementation that accepts the input is a candidate bug.
- LLM-generated preprocessing code that rejects invalid input can align divergent implementations, pointing toward generated validators as well as generated tests.
- An agentic pipeline with Researcher, Senior Researcher, and Intern agents is proposed to automate iteration over protocol RFCs without manual prompting.
- Extremal testing complements fuzzing and symbolic execution, which are unlikely to hit cases like a 253-character DNS name with two consecutive dots or a shortest path whose length overflows a double.
Reading between the lines
- If the constraint-elicitation step is unreliable, then a single implementation's acceptance of a supposedly invalid input is not by itself a bug report; the authors' use of differential testing is what converts hallucinated constraints into checkable hypotheses, and future users should verify each divergence against the RFC before reporting.
- The invalid-input focus inherently cannot reach internal-state extrema such as a divide-by-zero when two inputs become equal, as the authors concede; combining LLM-generated constraints with static or symbolic analysis of state variables would be a natural extension.
- The same two-stage scheme should transfer to any well-specified input domain where 'invalid' is decidable, so the protocol examples here are likely a subset of a broader testing recipe.
- The success with '!' in DNS and %00 in URIs suggests LLMs may be reasoning from adversarial knowledge rather than just enumerating syntax rules, which would make the method relevant to vulnerability discovery.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes a two-step methodology for extremal testing of network software using large language models: first prompt the LLM for validity constraints on an input domain (e.g., DNS name length limits, URI component rules, BGP route-map constraints), then prompt it to generate inputs that violate those constraints. The authors report case studies on DNS, HTTP, BGP, and shortest-path libraries, claiming that each domain 'uncovered new bugs': BIND/NSD accepting '!' in a DNS label (pending vendor response), two acknowledged Caddy bugs (null-byte URIs and long URI paths), an acknowledged GoBGP AS-path regex bug, a pending Batfish negative-local-preference discrepancy, and a pending Boost double-overflow issue. They also compare two-stage prompting with one-stage prompting, describe a preliminary agentic-AI pipeline, and argue that extremal testing extends boundary value analysis by using LLM-generated, non-range constraints.
Significance. If the empirical claims hold up, the paper offers a low-effort, low-expertise testing recipe that is genuinely complementary to fuzzing, symbolic execution, and model-based testing, and it contributes several concrete findings, including two developer-acknowledged bugs in Caddy and one in GoBGP. The differential-testing methodology is clearly described, and the two-step prompting comparison in Table 1 is a useful practical data point. However, the evidence per protocol is thin (one or two events per domain), at least one 'bug' (DNS '!' acceptance) is currently an unconfirmed apparent violation that may be spec-compliant, and no artifacts or raw logs are provided. The significance is therefore moderate: the methodology is promising, but the strongest claim in the abstract is not yet supported at the level the paper states.
major comments (5)
- [§2 (Prompt 1, Prompt 2, Test 3)] The central claim that DNS extremal tests 'uncovered new bugs' rests on Test 3 (exam!ple.com), but the oracle that this input must be rejected is not established. RFC 1035's preferred host-name grammar excludes '!', yet the paper itself calls the BIND/NSD behavior an 'apparent violation' and is 'awaiting their responses.' Moreover, DNS zone names used for A records are not necessarily restricted to host-name grammar, and RFC 2181 permits arbitrary octets in labels. If BIND and NSD respond that accepting '!' is spec-compliant for non-host domain names, the DNS contribution reduces from 'new bug' to a benign divergence. The paper needs a vendor/RFC confirmation that this is a violation, or the DNS claim in the abstract and §6 must be weakened to 'reported divergence'.
- [§3 (HTTP) and Table 1] The reported test counts are internally inconsistent: §3 states that the methodology generated 'around 400 subtle test cases across five servers,' but Table 1 reports only 20 total HTTP tests for the two-stage strategy and 14 and 10 for the one-stage variants. If the 400 cases include all strategies or additional generated tests, the text should say so and Table 1 should report the full counts; otherwise the bug-finding rates in §6 cannot be reproduced from the data given.
- [§2–§5, Table 1] The 'Buggy' column in Table 1 and the abstract's 'each of which uncovered new bugs' conflate three evidential categories: developer-acknowledged bugs (Caddy×2, GoBGP), pending reports that may be spec-compliant behavior (BIND/NSD '!', Batfish negative local-pref, Boost overflow), and an explicitly acknowledged non-bug behavioral difference (FRR vs GoBGP conjunctive match logic). Because the central claim depends on these counts, the paper must separate confirmed, pending, and benign divergence per test and temper the abstract and conclusion claims accordingly.
- [§6, Table 1] The comparative claim that two-stage prompting 'consistently yields higher-quality test cases' is based on four protocols and per-cell bug counts of 0–2, with no replication and no statistical analysis. The observed pattern is suggestive but not established. The paper should either frame this as anecdotal evidence from an early exploration or gather enough repeated trials per strategy to support the comparative claim.
- [§2–§5 (overall evaluation)] No reproducible artifacts are provided: exact software versions, zone/configuration files, raw differential-testing outputs, full prompt transcripts, and issue-tracker links are all absent. Given that each protocol's bug count is one or two events, and at least one claim (DNS) may not survive vendor review, the evidence base is too thin for the strength of the title and abstract. A released test harness and logs, plus explicit per-bug status, are needed before the claimed 'uncovered new bugs' can be independently verified.
minor comments (5)
- [§2 (Prompt 1 and Prompt 2)] The numbered list in Prompt 1 skips item 4, and Tests 6 and 11 in Prompt 2 are the same input (example..com); renumbering would avoid confusion.
- [§2 (Prompt 1, item 2)] The statement that DNS labels 'must not contain any other characters' states a host-name rule, not a general DNS-label rule; distinguishing <host> from <domain> early would prevent the ambiguity that later affects Test 3.
- [§3 (HTTP null-byte test)] The sentence 'the redirect path is precisely the original request URI and causes a redirect loop' asserts a loop that was not demonstrated in the text; clarify whether the loop was observed with a client or inferred from the 301 response.
- [§5 (Boost shortest path)] The text says the correct shortest-path sum is '2.0e138,' but 1e308 + 1e308 = 2e308; this appears to be a typo and should be corrected.
- [§1 (related work on BVA)] The assertion that 'most work in BVA focuses on simple range constraints' is made without citation; citing the boundary-value-analysis literature surveyed in [17] would strengthen the contrast.
Circularity Check
No significant circularity: LLM outputs supply only the test inputs, while the bug findings are anchored by independent RFC citations, differential testing across implementations, and developer acknowledgments; the SCALE/MESSI/Eywa self-citations are descriptive contrasts, not load-bearing premises.
full rationale
The claimed derivation chain is: an LLM elicits protocol validity constraints; the same LLM generates inputs that violate them; the oracle is that invalid inputs should be rejected; implementations that accept them are reported as bugs. This would be circular only if the LLM's constraint were the sole standard of invalidity, but every bug claim in the paper is anchored to an external standard. The Caddy null-byte and long-URI findings are checked against RFC 3986 Section 7.3 and RFC 7230 Section 3.1 and are confirmed by Caddy developers; the GoBGP AS-path regex bug was acknowledged by GoBGP developers; the Batfish negative-local-preference claim rests on agreement between FRR and GoBGP plus the IETF YANG model; and the DNS '!' divergence is backed by an independent quotation of RFC 1035's grammar, hedged as an 'apparent violation,' with BIND/NSD responses explicitly awaited. The self-citations (SCALE [29], MESSI [38], Eywa [28]) only establish that DNS/BGP implementations were previously tested and contrast model-based testing with invalid-input extremal testing, and that claim is jointly supported by external fuzzing references [20,22,23,32], so they are not load-bearing. The closest thing to a self-referential risk is DNS Test 3 ('exam!ple.com'): its invalidity premise is LLM-generated, and RFC 1035's <domain> grammar is broader than its <host> grammar, so BIND/NSD acceptance could prove spec-compliant; however, the paper consults the RFC independently, discloses that responses are still pending, and therefore does not force the result by construction. That residual concern is an oracle-validity risk (a possible false positive), not a demonstrated reduction of the finding to the method's own inputs; per the analysis rules, it belongs in correctness risk rather than in the circularity score. The central claim is self-contained against external benchmarks, so the score of 1 reflects only the presence of minor, non-load-bearing self-citations.
Assumptions & free parameters
assumptions (3)
- domain assumption LLM-generated validity constraints accurately reflect the protocol specification (RFC 1035, RFC 3986, RFC 4271) for the tested implementations.
- domain assumption Differential testing disagreements among a small set of implementations indicate a bug or spec violation.
- domain assumption The LLM-generated test set is representative of the space of extremal inputs that matter for these protocols.
Cite this review
Pith. "Pith review of Extremal Testing for Network Software using LLMs." pith.science (2026). https://pith.science/paper/OFR6QJXA
@misc{pith2026250711898,
author = {Pith},
title = {Pith review of: Extremal Testing for Network Software using LLMs},
year = {2026},
howpublished = {\url{https://pith.science/paper/OFR6QJXA}},
note = {Machine review of arXiv:2507.11898}
}
read the original abstract
Physicists often manually consider extreme cases when testing a theory. In this paper, we show how to automate extremal testing of network software using LLMs in two steps: first, ask the LLM to generate input constraints (e.g., DNS name length limits); then ask the LLM to generate tests that violate the constraints. We demonstrate how easy this process is by generating extremal tests for HTTP, BGP and DNS implementations, each of which uncovered new bugs. We show how this methodology extends to centralized network software such as shortest path algorithms, and how LLMs can generate filtering code to reject extremal input. We propose using agentic AI to further automate extremal testing. LLM-generated extremal testing goes beyond an old technique in software testing called Boundary Value Analysis.
Figures
Reference graph
Works this paper leans on
-
[26]
X. Guo, C. Li, and T. Tsuchiya. Boundary Value Test Input Generation using Prompt Engineering with LLMs: Fault Detection and Coverage analysis, 2025
work page 2025
-
[1]
uk/resources/the-limiting-case-sublime-or-ridiculous.pdf
The Limiting Case: Sublime or Ridiculous? https://www.polydron.co. uk/resources/the-limiting-case-sublime-or-ridiculous.pdf
-
[2]
https://en.wikipedia.org/wiki/Simplex_ algorithm
The Simplex Method. https://en.wikipedia.org/wiki/Simplex_ algorithm
- [3]
-
[4]
https://leda.uni- trier.de/leda/guide/graph_algorithms/check_sp.html
LEDA: Checking the results of an SSSP Algorithm. https://leda.uni- trier.de/leda/guide/graph_algorithms/check_sp.html
-
[5]
https://leda.uni-trier.de/leda/guide/ NumberTypes.html
LEDA: Number Types. https://leda.uni-trier.de/leda/guide/ NumberTypes.html
-
[6]
https://leda.uni-trier.de/leda/guide/ graph_algorithms/shortest_path_algorithm.html
LEDA Shortest Path Algorithms. https://leda.uni-trier.de/leda/guide/ graph_algorithms/shortest_path_algorithm.html
-
[7]
https: //datatracker.ietf.org/doc/html/rfc3986
RFC 3986: Uniform Resource Identifier (URI): Generic Syntax. https: //datatracker.ietf.org/doc/html/rfc3986
Show all 43 references
-
[8]
https://datatracker
RFC 4271 - a Border Gateway Protocol 4 (BGP-4). https://datatracker. ietf.org/doc/html/rfc4271
-
[9]
https://datatracker.ietf.org/doc/html/rfc7230
RFC 7230: Hypertext Transfer Protocol (HTTP/1.1): Message Syntax and Routing. https://datatracker.ietf.org/doc/html/rfc7230
-
[10]
https://arxiv.org/abs/2405.06682
Self-Reflection in LLM agents: Effects on Problem-Solving Performance. https://arxiv.org/abs/2405.06682
-
[11]
https://tetrahedral
Truly Pathological: the Alexander Horned Sphere. https://tetrahedral. blogspot.com/2011/02/truly-pathological-alexanders-horned.html
2011
-
[12]
Aldoseri and D
A. Aldoseri and D. Oswald. insecure://: Vulnerability analysis of URI scheme handling in Android mobile browsers. In Proceedings of MAD- Web 2022: Workshop on Measurements, Attacks, and Defenses for the Web, Apr 2022
2022
-
[13]
Alshahwan, J
N. Alshahwan, J. Chheda, A. Finegenova, B. Gokkaya, M. Harman, I. Harper, A. Marginean, S. Sengupta, and E. Wang. Automated Unit Test Improvement using Large Language Models at Meta, 2024
2024
-
[14]
Afl 2018
American Fuzzing Lop (AFL). Afl 2018. https://lcamtuf.coredump.cx/ afl/
2018
-
[15]
D. A. S. Aric A. Hagberg and P. J. Swart. Exploring network structure, dynamics, and function using NetworkX. Proceedings of the 7th Python in Science Conference (SciPy2008) , 2008
2008
-
[16]
E. T. Barr, M. Harman, P. McMinn, M. Shahbaz, and S. Yoo. The Oracle Problem in Software Testing: A Survey. IEEE Trans. Softw. Eng., 41(5):507–525, May 2015
2015
-
[17]
Bhat and S
A. Bhat and S. M. K. Quadri. Equivalence class partitioning and bound- ary value analysis - a review. In 2015 2nd International Conference on Computing for Sustainable Global Development (INDIACom) , pages 1557–1562, 2015
2015
-
[18]
Böhme, V.-T
M. Böhme, V.-T. Pham, and A. Roychoudhury. Coverage-based greybox fuzzing as Markov chain. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security , pages 1032– 1043, 2016
2016
-
[19]
Bozic, L
J. Bozic, L. Marsso, R. Mateescu, and F. Wotawa. A formal TLS hand- shake model in LNT. arXiv preprint arXiv:1803.10319, 2018
2018 arXiv
-
[20]
Cadar, D
C. Cadar, D. Dunbar, D. R. Engler, et al. KLEE: Unassisted and automatic generation of high-coverage tests for complex systems programs. In OSDI, volume 8, pages 209–224, 2008
2008
-
[21]
Dashevskyi
S. Dashevskyi. A simple BGP fuzzer based on boofuzz. Github, 2023. https://github.com/Forescout/bgp_boofuzzer
2023
-
[22]
D. A. Donald Sharp and et al. Fuzzing targets and supported fuzzers available in FRR. Github, 2023. https://docs.frrouting.org/projects/dev- guide/en/latest/fuzzing.html
2023
-
[23]
Fuzzing DNS zone parsers
Frederic Cambus. Fuzzing DNS zone parsers. https://www.cambus. net/fuzzing-dns-zone-parsers/
-
[24]
Ganesh and D
V. Ganesh and D. L. Dill. A decision procedure for bit-vectors and arrays. In W. Damm and H. Hermanns, editors, Computer Aided Verifi- cation, 19th International Conference, CA V 2007, Berlin, Germany, July 3-7, 2007, Proceedings, volume 4590 ofLecture Notes in Computer Scienc...
2007
-
[25]
Godefroid, N
P. Godefroid, N. Klarlund, and K. Sen. DART: Directed automated random testing. In Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation , pages 213–223, 2005
2005
-
[27]
V. Hamon. Malicious URI resolving in PDF documents. J. Comput. Virol., 9(2):65–76, 2013
2013
-
[28]
S. K. Kakarla and R. Beckett. Oracle-based protocol testing with Eywa. arXiv preprint arXiv:2312.06875, 2023
2023 arXiv
-
[29]
S. K. Kakarla, R. Beckett, T. Millstein, and G. Varghese. SCALE: Auto- matically finding RFC compliance bugs in DNS nameservers. In 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI 22), pages 307–323, 2022
2022
-
[30]
H. Lee, J. Seibert, D. Fistrovic, C. Killian, and C. Nita-Rotaru. Gatling: Automatic performance attack discovery in Large-scale Distributed systems. ACM Trans. Inf. Syst. Secur., 17(4), apr 2015
2015
-
[31]
Dns-fuzz
NMAP Organization. Dns-fuzz. https://nmap.org/nsedoc/scripts/dns- fuzz.html
-
[32]
https://peachtech.gitlab.io/peach-fuzzer-community/
Peach Fuzzer. https://peachtech.gitlab.io/peach-fuzzer-community/
-
[33]
C. Qian, W. Liu, H. Liu, N. Chen, Y. Dang, J. Li, C. Yang, W. Chen, Y. Su, X. Cong, J. Xu, D. Li, Z. Liu, and M. Sun. ChatDev: Communicative Agents for Software Development, 2024
2024
-
[34]
Ramachandran
M. Ramachandran. Testing software components using boundary value analysis. In 2003 Proceedings 29th Euromicro Conference , pages 94–98. IEEE, 2003
2003
-
[35]
Reynolds, A
J. Reynolds, A. Bates, and M. Bailey. Equivocal URLs: Understanding the Fragmented Space of URL Parser Implementations. In Computer Security – ESORICS 2022: 27th European Symposium on Research in Computer Security, Copenhagen, Denmark, September 26–30, 2022, Pro- ceedings, Par...
2022
-
[36]
C. Roos, T. Terlaky, and J.-P. Vial. Interior Point Methods for Linear Optimization. Springer, New York, 2005
2005
-
[37]
Sholeh, I
M. Sholeh, I. Gisfas, M. A. Fauzi, et al. Black Box testing with Boundary Value Analysis and Equivalence Partitioning Methods. In Journal of Physics: Conference Series, volume 1823, page 012029. IOP Publishing, 2021. 7 Conference’17, July 2017, Washington, DC, USA Singha et al
2021
-
[38]
Singha, R
R. Singha, R. Mondal, R. Beckett, S. K. Kakarla, T. Millstein, and G. Varghese. MESSI: Behavioral testing of BGP implementations. In 21st USENIX Symposium on Networked Systems Design and Imple- mentation (NSDI 24), pages 1009–1023, 2024
2024
-
[39]
R. Swiecki. Honggfuzz - Security oriented software fuzzer. https: //github.com/google/honggfuzz/tree/master/examples/bind
-
[40]
J. Wang, Y. Huang, C. Chen, Z. Liu, S. Wang, and Q. Wang. Software Testing with Large Language Models: Survey, Landscape, and Vision, 2024
2024
-
[41]
White, T.-R
G. White, T.-R. Sikorski, J. Landay, and M. Ahmed. Limiting case analysis in an electricity and magnetism course. Phys. Rev. Phys. Educ. Res., 19:010125, Apr 2023
2023
-
[42]
Zhang, T
Z. Zhang, T. Wu, and J. Zhang. Boundary value analysis in automatic white-box test generation. In 2015 IEEE 26th International Symposium on Software Reliability Engineering (ISSRE) , pages 239–249. IEEE, 2015
2015
-
[43]
zzuf: multi-purpose fuzzer
Sam Hocevar. zzuf: multi-purpose fuzzer. https://caca.zoy.org/wiki/ zzuf. 8
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.