Cottontail: Large Language Model-Driven Concolic Execution for Highly Structured Test Input Generation

Introduction

• Highly structured inputs matter because they pass parser checks and allow deeper application logic to be examined, but parsing libraries can retain vulnerabilities despite intensive testing.Existing concolic engines are hindered by structure-agnostic path selection, solutions that may be syntactically invalid, and difficulty acquiring new structured seeds.Source: §1 · pp. 1–2
• Cottontail’s structure-aware selector uses expressive branch information in an Expressive Coverage Tree (ECT) to guide path-constraint selection.Its structural program paths represent meaningful, complete paths while reducing redundant constraints.Source: §1 · p. 2
• Its Solve-Complete solver first satisfies path constraints, then uses an LLM to complete solutions for syntactic validity and flexible input sizes.A test-case validator refines unsound LLM results.Source: §1 · pp. 1–2
• History-guided seed acquisition prompts an LLM for structured initial seeds and, after coverage saturates, uses recorded input-to-coverage mappings to generate fresh seeds.The later prompts use Chain-of-Thought to target unexplored features.Source: §1 · p. 2
• Cottontail covered 30.73% more lines and 41.32% more branches on average than SYMCC, MARCO, and their variants.It also improved parser-checking pass rates by more than 100x and found six previously unknown memory-related vulnerabilities; four of the six have been fixed.Source: §1 · p. 2
• Cottontail is presented as the first LLM-driven concolic execution engine to automatically generate highly structured inputs in a white-box manner.The prototype was built on SYMCC and tested on eight libraries across XML, SQL, JavaScript, and JSON formats.Source: §1 · pp. 2–3

Concolic Execution

• Concolic execution combines concrete execution with symbolic exploration, but fixed-size inputs and harness limits can lead testing to saturate.Engines negate selected path constraints and solve them to generate inputs for unexplored branches; fresh seeds can restart exploration after saturation.Source: §2 · p. 3

LLMs for Test Input Generation

• Prior work applied LLMs to black-box and grey-box fuzzing, but the authors report no earlier integration with concolic execution.They cite advanced program analysis and logical Chain-of-Thought prompts as promising ways to improve LLM reliability and robustness.Source: §2 · p. 3

Motivation: Investigative Study

• The authors identify structure-aware path selection and new-seed acquisition as needs for improving concolic testing effectiveness and continuity.They also investigate whether an LLM-driven solver can produce inputs that satisfy constraints while remaining syntactically valid and allowing flexible sizes.Source: §2 · pp. 3–4
• 100x more parser-checking pass rate was achieved by the LLM-driven solver than Z3 across the tested formats.The comparison used the same path constraints. Traditional solvers produced 85.3% to 99.9% syntactically invalid test cases and kept solution size fixed.Source: §2 · p. 4

3.1.1. Why Structure-aware Selection.

• Parsing-program constraint selection should represent paths meaningfully and completely, expose human-readable coverage, remove redundant constraints, and avoid missing promising coverage.The paper argues that exhaustive, bitmap-based, and CSTG-based strategies do not meet all these requirements for parsing programs.Source: §3.1.1 · pp. 4–5

3.1.2. Structural

• COTTONTAIL instruments IR code to record branch names and case values, then saves this structural metadata in JSON for runtime analysis.The instrumentation walks function instructions and records branch information, including switch cases, to preserve structural information that compilation can lose.Source: §3.1.2 · p. 5

3.1.3. Expressive Coverage Tree Maintainer.

• The source-based ECT records branch and call-context paths, including visit status, count, branch type, stack size, and branch identifier, distinguishing contexts for the same branch.Unlike binary-code coverage maps, ECT is partially context- and path-sensitive, avoiding loss of path or semantic information from compilation or hash collisions.Source: §3.1.3 · pp. 5–6

3.1.4. ECT-guided Constraint Selector.

• ECT-guided selection removes duplicate constraints within a run and prioritizes constraints across runs using node weight based on untaken status, visit count, and depth.Within a run, constraints differing only by symbolic input index at the same branch are deduplicated; the three node-weight factors balance exploration and redundancy.Source: §3.1.4 · p. 6

3.2.1. LLM-driven Constraint Solver.

• The Solve-Complete paradigm prompts an LLM to satisfy path constraints first, then complete the surrounding input to preserve syntax.It resolves a constraint mask with syntax-aware character synthesis under ASCII semantics, then fills the flexible mask with code that remains valid JavaScript.Source: §3.2.1 · pp. 6–7

3.2.2. Test Case Validator.

• The validator checks each LLM-generated input against its path constraint and, when needed, replaces the unreliable solution with a traditional solver’s solution before updating ECT.If the input satisfies the constraint, it is retained; otherwise, the validator refines it and returns the updated global coverage tree.Source: §3.2.2 · p. 7

3.3.1. History Coverage Recorder.

• The history coverage recorder uses ECT to track which test inputs cover which branches and identify branches that remain uncovered, providing information for seed-generation prompts.The history links between inputs and branches help reveal processing logic and missing input features.Source: §3.3.1 · p. 7, §3.3 · p. 7

3.3.2. LLM-driven Seed Generator.

• The seed generator supplies initial seeds when none are available and, after three minutes without coverage gains, uses coverage-guided CoT prompts to mutate prior inputs or create new ones.It compares covered and uncovered branches, groups them by source location, and infers relevant input bytes; generated seeds may miss target branches and are quickly discarded if they do.Source: §3.3.2 · pp. 7–8

4. Implementation

• Cottontail extends SymCC with C++ structural instrumentation and coverage-guided path-constraint selection, while Python implements LLM-driven constraint solving and history-guided seed acquisition.The running script uses Python 3.9.Source: §4 · p. 8
• The selected Equation 1 parameters were α = 1.0, β = 3.0, and γ = 0.8, chosen for a better efficiency-effectiveness trade-off.The authors used gpt-4o only in RQ1 Setting 1 and gpt-4o-mini as base LLMs, accessed through Python APIs with temperature 0; they report that deepseek-v3 and gpt-4.1-nano also worked very well compared with higher-cost gpt-4o.Source: §4 · p. 8

5.1. RQ1: Comparison with Baseline Approaches

• Cottontail improved average line coverage by 30.73% and branch coverage by 41.32% over comparative approaches, outperforming them on average in all three running settings.The reported improvements reached up to 99.65% over QuickJS for line coverage and 175.88% over Libexpat for branch coverage.Source: §5.1 · pp. 9–10, Table 2 · p. 10

5.2. RQ2: Ablation Studies

• CoT prompts achieved higher line coverage than normal prompts across all tested libraries, while the validator configuration matched or outperformed the version without validation.SQLite coverage increased from approximately 13,000 to over 15,000 lines with CoT prompts; the solver directly solved 70.08% of cases on average, and the validator refined unreliable results. Validator gains were notable in SQLite, QuickJS, and Libxml2.Source: §5.2 · pp. 10–11, Figure 10 · p. 11, Figure 11 · p. 11
• History-guided seed acquisition outperformed random seed generation in all selected benchmarks, and enabling seed generation with initial seeds added coverage during the latter 10 hours.In SQLite, Cottontail covered over 23,000 lines versus under 19,000 for the random-seed variant; enabling generation added 101, 376, 806, and 21 lines over Libexpat, SQLite, QuickJS, and JSON-C, respectively.Source: §5.2 · pp. 11–12

5.3. RQ3: Vulnerability Detection Capability

• Cottontail found six previously unknown vulnerabilities across three testing subjects, and four had been fixed when the paper was submitted.MARCO detected only vulnerability #5, while SYMCC detected four of the six; the reported issues included heap memory leaks, buffer overflows, and stack overflows.Source: §5.3 · p. 12, Table 4 · p. 12

Potential in Detecting Other Types of Bugs

• COTTONTAIL-generated inputs helped uncover a confirmed JSON-C parsing bug involving incomplete handling of control characters.Differential testing flagged potential issues when parsers disagreed, but differing standards can cause false positives; developers confirmed and fixed the reported bug.Source: §6 · p. 13

Potential in Practical Adoption

• 200%+ reduction in redundant path constraints could save testing time, and COTTONTAIL may support practical white-box testing such as SAGE.The authors also report that its low-cost API invocation supports integration with closed- and open-source LLMs, and that adding expert knowledge to the Solve-Complete completion phase could improve structure-aware generation.Source: §6 · p. 13

API Costs for Running Experiments

• GPT API use averaged 816 calls per subject and $0.78 per hour with gpt-4o-mini; traditional solvers are faster but produce many invalid test cases.The authors suggest that better LLM response time and robustness could further improve test generation.Source: §7 · p. 14

Threats to Validity

• The evaluation covers eight open-source libraries and five repetitions, but its conclusions may not generalize to all programs or large systems such as V8 and GCC.The authors consider LLM memorization unlikely because Cottontail's constraint-solving process is unconventional; a validator checks and refines generated cases to address hallucinations.Source: §7 · p. 14

Limitations

• Cottontail depends on a complete fuzzing driver and available source code, and its performance on unstructured inputs or formats unfamiliar to the LLM remains unclear.The authors identify large-system scalability as a limitation and plan to explore selective path exploration; they also propose transferring the approach to SYMQEMU for binary-only targets.Source: §7 · pp. 14–15

Traditional Fuzzing for Software Security

• Black-box fuzzers such as Peach, LangFuzz, and Grammarinator generate or mutate structured inputs but lack internal program feedback.Grey-box approaches add coverage feedback and structure-aware techniques, but still face challenges comprehensively exploring execution space.Source: §8 · p. 15
• Concolic engines systematically explore paths, but often fail to generate valid highly structured inputs; grammar-based white-box methods remain limited on complex formats and deep paths.Prior work includes grammar-based white-box fuzzing, CESE, and grammar-agnostic Grdse.Source: §8 · p. 15

LLM-assisted Fuzzing for Software Security

• COTTONTAIL combines systematic path exploration with structure-aware selection, smart constraint solving, and seed acquisition, unlike random-input LLM fuzzers such as Fuzz4All.Its Solve-Complete approach uses path constraints with an LLM to improve test-case generation and code coverage and vulnerability detection.Source: §8 · pp. 15–16

• COTTONTAIL uses structure-aware constraint selection to prioritize path constraints worth exploring.Source: §9 · p. 16
• Its LLM-driven solver produces test cases that satisfy path constraints and align with syntax rules.Source: §9 · p. 16
• History-guided seed acquisition generates new seeds when testing starts or when the process saturates.Source: §9 · p. 16
• Compared with state-of-the-art concolic engines, COTTONTAIL shows superior code coverage and vulnerability detection capability.Source: §9 · p. 16

3. Running Real-world Applications / 3.1. Prepare the subject. / 3.2. Set Up the Environment Variables and Paths. / 3.3. Launch the concolic testing.

• COTTONTAIL testing uses a customized concolic compiler, configurable model, targets, and settings, and launches with `python ./run-cottontail.py`.The configuration includes API-key and path settings, plus a 43,200-second run timeout and a 60-second coverage-collection interval.Source: §3 · p. 19, §3.1 · p. 19, §3.2 · p. 19

1. Comparison of Existing Coverage Maps

• For parsing programs, exhaustive search wastes effort on redundant byte-level constraints, while Bitmap and CSTG can miss coverage and lack meaningful, human-readable path representations.The paper argues that effective selection should represent program paths meaningfully and completely, record human-readable coverage, exclude redundant structure-agnostic constraints, and reduce missed interesting coverage.Source: §1 · p. 20

2. Extra Experimental Results against State-of-the-art Approaches

• SYMCC and MARCO often saturate early on benchmarks such as Libexpat and SQLite, motivating COTTONTAIL’s fresh-seed acquisition strategy to explore more program paths.The paper reports that SYMCC quickly plateaus within an hour with minimal later improvement; MARCO’s final coverage also remains substantially below other approaches in many cases.Source: §2 · pp. 20–21

3. Overhead of Structural Instrumentation

• Structural instrumentation overhead ranges from 9.78% for JSON-C and 23.96% for Jansson to 31.49% for Libexpat and 26.26% for QuickJS.The paper characterizes the overhead as negotiable relative to the longer duration of comprehensive testing, given the instrumentation’s contribution to execution insights and code coverage.Source: §3 · p. 21

4. Performances of Integration with Other LLMs

• Across tested LLM integrations, COTTONTAIL performs competitively or better, with the DeepSeek-V3 version achieving the best line coverage in most cases.The 12-hour comparison included DeepSeek-V3, GPT-4.1-nano, and GPT-4o-mini; the paper describes integration cost as minimal.Source: §4 · p. 21, Figure 17 · p. 22

Section C: Meta-Review / Scientific Contributions / Reasons for Acceptance

• The review identifies LLMs as integral to concolic execution as an innovation, says experiments address longstanding issues, and notes that the open-source prototype can support future security research.The meta-review was prepared by the program committee for the 2026 IEEE Symposium on Security and Privacy.Source: Section C: Meta-Review · p. 22, Reasons for Acceptance · p. 22

Noteworthy Concerns

• The evaluation covers small programs with structured formats familiar to LLMs, not large or unstructured-input programs or formats unknown to LLMs; the review also says broader context comes late.The review warns that readers limited to the introduction and evaluation may not appreciate the technique’s limitations.Source: Noteworthy Concerns · p. 22