💻 computer science

Graph-Aware Fuzzing for Graph Database Management Systems

GRAF is a black-box fuzzing framework for Graph Database Management Systems that leverages LLM-driven, graph-context-aware query generation and execution-state-guided mutation to overcome the limitations of existing testing methods, ultimately achieving significantly higher code coverage and discovering dozens of previously unknown bugs across multiple systems.

Original authors: Yu Li, Qiang Hu, Yao Zhang, Junjie Wang, Hao Liu, Rui Wang, Yongqiang Lyu

Published 2026-07-07

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Yu Li, Qiang Hu, Yao Zhang, Junjie Wang, Hao Liu, Rui Wang, Yongqiang Lyu

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 a Graph Database as a massive, living city map. Unlike a standard spreadsheet (which is like a rigid grid of rows and columns), this city is made of nodes (people, places, things) connected by roads (relationships). In this city, you can ask questions like, "Find all the friends of friends of Bob who live in Paris and work at a bakery."

To test if this city's navigation system (the database engine) is safe and reliable, you need to send it thousands of tricky questions. If the system crashes or gets stuck in a loop, that's a bug.

The paper introduces GRAF, a new "robot tester" designed specifically to break these graph databases. Here is how it works, explained simply:

The Problem: Why Old Testers Failed

Previous testers were like two different types of clumsy tourists:

The "Copycat" Tourist: They asked the same question to five different cities to see if the answers matched. If they didn't match, they found a bug. But this only worked if the question was simple enough to be asked in all five cities. It missed the deep, weird crashes that happen when you ask a single city a very complex question.
The "Random Typist": They just mashed keys to create random sentences. But graph databases are picky. If you say "Bob knows Alice" but Bob and Alice don't actually exist in the city, the system rejects the question immediately. The random typist wasted 99% of their time asking questions the system wouldn't even read.

The Solution: GRAF (The Smart Tourist)

GRAF is a "black box" tester, meaning it doesn't need to see the internal code of the database. It just sends questions and watches what happens. It solves the two main problems using two clever tricks:

1. The "Skeleton and Flesh" Trick (Generating Valid Questions)

Imagine you want to build a house.

Old way: You try to build a house by randomly throwing bricks at a wall. Most of the time, the wall collapses because the bricks don't fit.
GRAF's way:
- Step A (The Skeleton): GRAF uses a super-smart AI (a Large Language Model) to draw up a blueprint. This blueprint has empty spaces where the specific details go, like "Insert [Name] here" or "Connect to [Street] here."
- Step B (The Flesh): Before sending the blueprint to the city, GRAF looks at the actual city map. It sees that "Bob" exists and "Paris" exists. It fills in the blanks with real, valid data that fits the city's rules.
- The Result: Every question GRAF sends is guaranteed to be grammatically correct and logically possible within that specific city. It never wastes time on questions the system will reject.

2. The "Traffic Cop" Trick (Guiding the Exploration)

Once GRAF starts sending questions, it watches how the city reacts. It uses three signals to decide what to do next:

Time: How long did the question take?
Size: How big was the answer?
Status: Did the system crash, freeze, or finish normally?

How it uses this info:

If the answer is empty: GRAF thinks, "This question was too strict." It loosens the rules (e.g., "Maybe Bob doesn't have to live in Paris") and tries again.
If the answer takes forever (Time out): GRAF thinks, "This is too heavy." It stops making the question deeper and tries a different angle to avoid getting stuck.
If the system crashes: GRAF celebrates! It saves that specific question, tweaks it slightly, and tries to make the crash happen again to prove it's a real bug.

The Results: Breaking the System

The researchers tested GRAF on six popular graph databases (like Neo4j and Memgraph) and compared it to the best existing testers.

Coverage: GRAF explored 31% to 41% more of the database's internal logic than the next best tester. It found deep, hidden corners that others missed.
Bugs Found: In just 12 hours, GRAF found 25 unique bugs on its own. The other three testers combined only found 6.
Real-World Impact: GRAF discovered 34 previously unknown bugs. Developers confirmed 32 of them, and 23 were given official "CVE" numbers (security alerts), meaning they were serious enough to be patched immediately.

The Big Takeaway

GRAF is like a master detective who knows exactly how to ask a city's navigation system the most confusing, complex questions possible without ever getting rejected. By separating the structure of the question from the data inside it, and by listening to how the system reacts, it finds crashes and errors that other tools simply cannot see.

Technical Summary: GRAF - Graph-Aware Fuzzing for Graph Database Management Systems

1. Problem Statement

Graph Database Management Systems (GDBMSs) are critical infrastructure for managing interconnected data, yet their testing remains underexplored compared to relational databases. Existing testing methods primarily rely on differential and metamorphic testing, which depend on result consistency oracles. These approaches constrain inputs to queries that are comparable across engines or semantically transformable, thereby narrowing the input space to well-defined, result-producing queries. Consequently, engine-specific runtime failures—such as crashes, memory corruption, and resource exhaustion—remain insufficiently explored.

Developing dedicated fuzzers for GDBMSs faces two specific challenges:

Generating Valid and Structurally Diverse Queries: Valid Cypher queries must satisfy complex, interdependent syntactic and semantic constraints (e.g., variable scoping, type compatibility, and graph schema adherence). Generic byte-level fuzzers corrupt syntax, while grammar-based generators often produce structurally simple queries that fail to exercise deep engine logic.
Guiding Exploration under Topology-Dependent Execution: Traditional coverage feedback captures control flow but fails to capture topology-dependent data flow behaviors. Graph query execution is highly sensitive to hubs, cycles, and traversal depth; small parameter changes can cause exponential resource spikes (e.g., execution time increasing 320x) without altering control flow paths. Existing methods lack feedback mechanisms to distinguish between unproductive empty results, expensive traversals, and abnormal failures.

2. Methodology: The GRAF Framework

The authors propose GRAF, a black-box, feedback-driven fuzzing framework designed to address these challenges. GRAF operates entirely as a black box, relying on externally visible outcomes rather than traditional code coverage for guidance.

A. Graph Context-Aware Query Generation

GRAF decouples abstract query structure from concrete graph data to ensure validity while maintaining diversity.

Skeleton Generation: A Large Language Model (LLM) synthesizes a pool of parameterized Cypher skeletons with diverse clause combinations and traversal patterns. These skeletons use standardized identifiers and placeholders but contain no concrete values.
Cascading Dependency Resolution: Instead of random instantiation, GRAF resolves placeholders against the active graph state in three cascading phases:
1. Topology Resolution: It samples node labels and relationship types based on schema metadata (e.g., if a source label is Customer, only valid outgoing relationships like Order are selected).
2. Property and Value Resolution: It binds property keys and generates concrete values (observed, boundary, or anomalous) compatible with the entity types.
3. Global Parameter Alignment: It adjusts global parameters (e.g., LIMIT or traversal bounds) proportionally to the graph's scale to prevent immediate timeouts.
  This process eliminates syntactic and semantic violations before execution, ensuring queries reach the optimization and execution logic.

B. Execution State Guided Query Mutation

GRAF employs a dynamic feedback vector $F = \langle t, |R|, s \rangle$ , where $t$ is execution time, $|R|$ is result size, and $s$ is system status. This feedback guides five graph-specific mutation operators:

Topology Mutation: Inserts, removes, or reconnects patterns.
Depth and Volume Mutation: Modulates path bounds and LIMIT configurations.
Predicate Mutation: Manipulates WHERE expressions to alter selectivity.
Clause Insertion: Injects pipeline components (e.g., WITH, aggregations).
Value Mutation: Substitutes literals with boundary or anomalous values.

Feedback Strategies:

Empty Results: If a query returns quickly with no results, GRAF relaxes predicates or adjusts topology to ensure data materialization.
High Cost/Timeouts: For queries nearing timeout, GRAF penalizes depth expansion and favors bounded reductions to avoid unproductive exploration.
Abnormal Terminations: Crashes or OOMs trigger priority analysis and localized mutations to isolate the failure cause.

3. Key Contributions

The paper claims the following contributions:

GRAF Framework: A black-box fuzzer that uses execution feedback rather than code coverage to test diverse GDBMS engines.
Decoupled Generation Strategy: A novel approach separating abstract structure (generated via LLM) from concrete data (resolved via cascading dependency), enabling the generation of complex, valid queries.
State-Guided Mutation: A mutation strategy that adapts operators based on execution time, result size, and system status to steer exploration toward deep engine logic.
Empirical Validation: Extensive evaluation on six popular GDBMSs demonstrating significant improvements in coverage and bug discovery.

4. Experimental Results

The authors evaluated GRAF against three baselines (Dinkel, BUZZBEE, and AFL++) on six GDBMSs: Memgraph, FalkorDB, Neo4j, KuzuDB, NebulaGraph, and RedisGraph.

Code Coverage: GRAF consistently improved line coverage by 31.6% to 41.1% over the strongest baseline on each target. It covered significantly more unique lines, particularly in deep implementation regions, compared to the baselines which largely overlapped on frontend parser logic.
Query Validity: GRAF maintained a valid query rate of 61.8% to 76.7%, significantly higher than AFL++ (~~2%) and BUZZBEE (~~50-60%), though slightly lower than the conservative Dinkel.
Bug Discovery:
- GRAF discovered 34 previously unknown bugs across the six systems.
- 32 bugs were confirmed by developers, and 23 were assigned CVE identifiers.
- In a controlled 12-hour evaluation, GRAF triggered 25 unique bugs, whereas the three baselines combined triggered only 6.
- The bugs spanned critical components including pattern matching, path expansion, aggregation, and transaction management, with types including segmentation faults, use-after-free, stack overflows, and out-of-memory errors.

5. Significance and Claims

The paper asserts that GRAF demonstrates the effectiveness of decoupling query structure from runtime context and utilizing external execution feedback to test complex database engines. By addressing the specific challenges of graph topology and semantic constraints, GRAF successfully bypasses frontend validation to stress-test backend execution logic. The results suggest that traditional coverage metrics are insufficient for graph databases and that execution state signals (time, size, status) are critical for guiding fuzzing toward deep, latent defects. The authors conclude that their approach provides a robust method for uncovering runtime failures in GDBMSs that differential and metamorphic testing miss.