🤖 AI

SPARC: Scenario Planning and Reasoning for Automated C Unit Test Generation

SPARC is a neuro-symbolic framework that bridges the gap between high-level intent and C's rigid constraints by combining Control Flow Graph analysis, validated operation maps, and iterative compiler feedback to generate significantly more effective and maintainable automated unit tests than existing LLM-based or symbolic execution approaches.

Original authors: Jaid Monwar Chowdhury, Chi-An Fu, Reyhaneh Jabbarvand

Published 2026-02-19

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Jaid Monwar Chowdhury, Chi-An Fu, Reyhaneh Jabbarvand

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a very talented but slightly scattered robot how to write a manual for a complex, old-fashioned machine (written in the C programming language). This machine is tricky: it has moving parts that can break if you pull the wrong lever (pointers), and you have to manually carry heavy crates of tools (memory management) without dropping them.

The paper introduces a new method called SPARC to help this robot write a perfect "user manual" (unit tests) for the machine.

Here is how SPARC works, broken down into simple analogies:

The Problem: The "Leap-to-Code" Trap

If you just ask a standard AI (like a "Vanilla Prompt") to "Write a test for this machine," it often panics. It tries to guess the whole manual at once.

The Result: It makes up tools that don't exist (hallucinations), forgets to check for broken levers (missing edge cases), or writes instructions that make the machine explode (code that won't compile). It's like a student who memorized the definition of "driving" but has never actually held a steering wheel.

The Solution: SPARC (The Architect Approach)

SPARC changes the game. Instead of asking the AI to write the whole manual in one go, it acts like a construction architect who breaks the job down into four distinct, manageable steps.

1. The Blueprint (Control Flow Graph)

First, SPARC doesn't just look at the code; it draws a map of every possible path the machine can take.

Analogy: Imagine a maze. Instead of guessing where the exit is, SPARC draws every single corridor, dead end, and shortcut on a piece of paper. It knows exactly how many ways you can walk through the machine.

2. The Toolbox (Operation Map)

Before the AI writes a single line of code, SPARC gives it a strict list of allowed tools.

Analogy: If you are building a house, you don't let the builder guess what a hammer looks like. You hand them a specific box containing only the hammers, nails, and saws that actually exist in your garage. This stops the AI from inventing fake tools that don't work.

3. The Scenario Planner (Path-Targeted Synthesis)

Now, SPARC tells the AI: "Okay, let's test Path A." The AI writes a test specifically for that one path. Then, "Now let's test Path B."

Analogy: Instead of trying to drive the whole maze in one go, the robot practices driving just the left turn, then just the right turn, then just the dead end. It ensures every single corner of the maze gets visited.

4. The Safety Inspector (Iterative Validation)

After the AI writes a test, SPARC runs it. If the test crashes or fails, it doesn't just throw it away. It shows the error to the AI and says, "Fix this specific mistake," and tries again.

Analogy: It's like a teacher grading a homework assignment. If you get a math problem wrong, the teacher circles the error and says, "Try again," rather than giving you a zero and moving on. SPARC does this up to three times to fix the test.

Why is this better? (The Results)

The researchers tested SPARC on 59 real-world C projects (like complex algorithms for sorting data or handling images).

Better Coverage: While the "Vanilla" AI missed about 30% of the tricky paths, SPARC found almost all of them. It's like finding every hidden trap in a video game level.
Fewer Hallucinations: Because SPARC gave the AI a strict "Toolbox" (Operation Map), the AI stopped making up fake functions.
Human Approval: When real human developers looked at the tests, they said SPARC's tests were much easier to read, more logical, and easier to maintain than the AI's first attempts.
Cost-Effective: Surprisingly, SPARC worked just as well with cheaper, smaller AI models as it did with the most expensive, powerful ones. The process (the blueprint and the toolbox) mattered more than the brainpower of the AI.

The Bottom Line

SPARC is like giving a robot a checklist, a map, and a strict toolbox before letting it loose on a complex job. By breaking the problem down into small, logical steps and checking the work at every stage, it turns a chaotic, error-prone process into a reliable, industrial-grade system for testing old, difficult software.

1. Problem Statement

Automated unit test generation for C programming language remains a significant challenge due to the "semantic gap" between high-level program intent and the rigid syntactic constraints of C (e.g., pointer arithmetic, manual memory management).

While Large Language Models (LLMs) have shown promise in code generation, direct "intent-to-code" synthesis (vanilla prompting) suffers from a "leap-to-code" failure mode. In this mode, LLMs prematurely emit code without grounding in the program's structure, leading to:

Non-compilable tests: Due to hallucinated function signatures or missing dependencies.
Low coverage: Tests often plateau at "happy-path" scenarios, missing edge cases, boundary values, and error-handling branches.
Lack of traceability: Generated tests act as black boxes with generic names and weak assertions that do not explain the logic path taken.
Poor fault detection: Tests fail to capture bugs effectively, resulting in low mutation scores.

Existing symbolic execution tools (like KLEE) struggle with path explosion and require manual driver code, while standard LLM approaches lack the structural grounding necessary for complex C codebases.

2. Methodology: The SPARC Framework

SPARC (Scenario Planning And Reasoning for Automated C Unit Test Generation) is a neuro-symbolic, scenario-based framework that bridges the gap between program structure and test synthesis. It decomposes test generation into four distinct stages:

A. Pre-processing & Structured Metadata

Input: Raw C source code.
Process:
- Extracts functions and their dependencies.
- Constructs a Control Flow Graph (CFG) using the ATLAS tool to enumerate all feasible execution paths ( $\pi$ ).
- Linearizes paths into JSON format (e.g., START → (root==NULL) → RETURN) to make control-flow intent explicit for the LLM.
- Generates a semantic description of the function.

B. Operation Map Construction (RAG-based)

Goal: Ground LLM reasoning in validated utility helpers to prevent hallucination.
Process:
- Uses Retrieval-Augmented Generation (RAG) to match the target function against a curated pool of validated helper functions (e.g., memory cleanup, data structure initialization, Unity assertions).
- A single LLM call generates an Operation Map ( $\Omega$ ) which defines:
  - Which existing helpers to reuse.
  - Which new helpers to create (with full implementations).
  - Dependency analysis.
- This map acts as a strict constraint, ensuring the LLM only invokes functions that exist or are explicitly generated.

C. Path-Targeted Test Synthesis

Process: Instead of generating a monolithic test suite, SPARC generates a dedicated test case for each execution path ( $\pi$ ).
Input to LLM: The function body, the specific linearized path, and the path-specific slice of the Operation Map.
Output: A self-contained Unity test file that constructs inputs to trigger that specific path and asserts expected outcomes.

D. Iterative Validation & Repair Loop

Process: Each generated atomic unit (test + helpers) undergoes a validation loop:
1. Compile & Run: Checks for static errors (undefined references) and dynamic errors (memory leaks, segmentation faults via AddressSanitizer).
2. Repair: If errors occur, the LLM is prompted to fix the specific errors. The temperature is slightly raised (0.1) to allow variation.
3. Merge: Validated tests are merged into a unified suite, deduplicating headers and helpers.
4. Discard: Tests failing to stabilize after 3 iterations are discarded.

3. Key Contributions

Novel Framework: SPARC is the first technique to propose scenario-based decomposition (per-path scenarios) for automated C test generation, effectively bridging the semantic gap between the function under test and the test code.
Neuro-Symbolic Integration: It combines static analysis (CFG, path enumeration) with LLM synthesis, constrained by a RAG-based Operation Map to eliminate dependency hallucinations.
Iterative Self-Correction: Introduces a robust validation loop that repairs tests based on compiler and runtime feedback, achieving high retention rates.
Scalability & Portability: Demonstrates that the pipeline architecture drives quality, allowing cost-efficient models to match frontier model performance.

4. Experimental Results

The framework was evaluated on 59 real-world and algorithmic C projects (including Rustine and TheAlgorithms C).

Coverage Effectiveness:
- Line Coverage: SPARC outperforms vanilla LLM prompting (DeepSeek V3.2) by 31.36%.
- Branch Coverage: SPARC outperforms the baseline by 26.01%.
- Comparison with KLEE: SPARC matches or exceeds the symbolic execution tool KLEE on complex subjects (e.g., heman, red_black_tree), where KLEE often struggles with path explosion.
- Complexity Resilience: Unlike vanilla prompting, whose coverage drops significantly as path count increases, SPARC maintains high coverage even in high-complexity subjects (>30 paths).
Test Validity & Fault Detection:
- Retention: 94.3% of generated tests are retained after iterative repair.
- Mutation Score: SPARC achieves a 20.78% higher mutation score than the baseline, indicating superior fault detection capabilities.
- Root Cause Analysis: The primary failure mode was "helper API hallucination" (66% of dropped tests), which the Operation Map and repair loop successfully mitigated.
Developer Perception (User Study):
- A blind A/B study with 10 developers showed SPARC tests were rated significantly higher in Readability, Correctness, Completeness, and Maintainability compared to vanilla LLM outputs.
Cost & Model Agnosticism:
- Cost Scaling: Token cost scales roughly quadratically with path count, but structural complexity per path is a major driver.
- Model Choice: The pipeline works effectively with cost-efficient models (e.g., Gemini 3 Flash, GPT-5-Mini), proving that the structured pipeline is the dominant factor in quality, not the underlying LLM.

5. Significance

SPARC represents a paradigm shift in automated testing for legacy and complex C codebases. By decoupling structural analysis (path enumeration) from code synthesis (LLM generation) and enforcing semantic constraints (Operation Maps), it solves the "leap-to-code" failure mode inherent in current LLM approaches.

Its ability to generate industrial-grade, maintainable, and highly effective unit tests without relying on expensive frontier models makes it a scalable solution for software maintenance, refactoring, and safety-critical verification in the C ecosystem.