Graph-Aware Fuzzing for Graph Database Management Systems

• URL: http://arxiv.org/abs/2607.03741v1
• Date: Sat, 04 Jul 2026 07:08:14 GMT
• Title: Graph-Aware Fuzzing for Graph Database Management Systems
• Abstract summary: We propose GRAF, a black box fuzzing framework for GDBMS query engines.<n>It generates valid and structurally diverse queries under complex graph constraints.<n>It applies five graph specific mutation operators guided by execution state feedback, including execution time, result size, and system status.<n> GRAF consistently improves line coverage by 31.6% to 41.1% over the strongest baseline on each target.
• Score: 22.261896283072137
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph Database Management Systems (GDBMSs) are essential infrastructure for managing interconnected data. Existing GDBMS testing methods primarily rely on differential and metamorphic testing. The result consistency oracles of these methods constrain inputs to queries that are comparable across engines or transformations, leaving single engine runtime failures, such as crashes and memory errors, insufficiently explored. Developing dedicated fuzzers for GDBMSs faces two key challenges: (1) generating valid and structurally diverse queries under complex graph constraints, and (2) guiding exploration to capture topology dependent execution behavior. To address these challenges, we propose GRAF, a black box fuzzing framework for GDBMS query engines. First, GRAF introduces graph context aware query generation based on cascading dependency resolution. It instantiates parameterized Cypher skeletons generated by a Large Language Model (LLM) by jointly resolving labels, relationship types, properties, values, and variable scopes against the active graph state. This process produces structurally diverse queries while eliminating syntactic and semantic violations. Second, GRAF applies five graph specific mutation operators guided by execution state feedback, including execution time, result size, and system status. This feedback steers exploration away from unproductive queries and expensive traversals, while prioritizing local mutations around abnormal executions. We evaluated GRAF against three existing approaches on six widely used GDBMSs. GRAF consistently improves line coverage by 31.6% to 41.1% over the strongest baseline on each target. In 12 hour fuzzing, it triggered 25 unique bugs, compared to six from all baselines combined. Overall, GRAF discovered 34 previously unknown bugs, with 32 confirmed by developers and 23 assigned CVEs.

Related papers

• Degraded but Not Entirely Ineffective: PE-Based Deformable Graph Neural Networks [7.304609897426712]
  We propose a Position.<n>Based Deformable Spatial Aggregation Module (PEBDSAM)<n>We utilize a deformable mechanism in the position space to identify relevant first-order neighbor information of GNNs, allowing traditional GNNs to adapt to heterophilous scenarios.<n>The module is plug-and-play and applied it to GCN, GAT, GIN, and GraphSAGE, achieving desirable results on three homophilous datasets and six heterophilous graph datasets.
  arXiv  Detail & Related papers  (2026-09-12T04:56:02Z)
• Atomic Task Graph: A Unified Framework for Agentic Planning and Execution [13.978062792065215]
  Atomic Task Graph (ATG) is a unified control framework for planning and execution.<n>ATG maintains an explicit graph to expose dependencies and support reuse.<n>ATG consistently outperforms strong baselines in success rate and execution efficiency.
  arXiv  Detail & Related papers  (2026-07-02T09:34:20Z)
• GREPO: A Benchmark for Graph Neural Networks on Repository-Level Bug Localization [50.009407518866965]
  Repository-level bug localization is a critical software engineering challenge.<n>GNNs offer a promising alternative due to their ability to model complex, repository-wide dependencies.<n>We introduce GREPO, the first GNN benchmark for repository-scale bug localization tasks.
  arXiv  Detail & Related papers  (2026-02-14T23:22:15Z)
• Align-GRAG: Reasoning-Guided Dual Alignment for Graph Retrieval-Augmented Generation [79.75818239774952]
  Large language models (LLMs) have demonstrated remarkable capabilities, but still struggle with issues like hallucinations and outdated information.<n>Retrieval-augmented generation (RAG) addresses these issues by grounding LLM outputs in external knowledge with an Information Retrieval (IR) system.<n>We propose Align-GRAG, a novel reasoning-guided dual alignment framework in post-retrieval phrase.
  arXiv  Detail & Related papers  (2025-05-22T05:15:27Z)
• Scalable Graph Generative Modeling via Substructure Sequences [50.32639806800683]
  We introduce Generative Graph Pattern Machine (G$2$PM), a generative Transformer pre-training framework for graphs.<n>G$2$PM represents graph instances (nodes, edges, or entire graphs) as sequences of substructures.<n>It employs generative pre-training over the sequences to learn generalizable and transferable representations.
  arXiv  Detail & Related papers  (2025-05-22T02:16:34Z)
• Divide by Question, Conquer by Agent: SPLIT-RAG with Question-Driven Graph Partitioning [62.640169289390535]
  SPLIT-RAG is a multi-agent RAG framework that addresses the limitations with question-driven semantic graph partitioning and collaborative subgraph retrieval.<n>The innovative framework first create Semantic Partitioning of Linked Information, then use the Type-Specialized knowledge base to achieve Multi-Agent RAG.<n>The attribute-aware graph segmentation manages to divide knowledge graphs into semantically coherent subgraphs, ensuring subgraphs align with different query types.<n>A hierarchical merging module resolves inconsistencies across subgraph-derived answers through logical verifications.
  arXiv  Detail & Related papers  (2025-05-20T06:44:34Z)
• Identifying Root Cause of bugs by Capturing Changed Code Lines with Relational Graph Neural Networks [7.676213873923721]
  We propose a method called RC-Detection to detect root-cause deletion lines in changed code lines.<n>RC-Detection is used to detect root-cause deletion lines in changed code lines, thereby identifying the root cause of introduced bugs in bug-fixing commits.<n>Our experiments show that, compared to the most advanced root cause detection methods, RC-Detection improved Recall@1, Recall@2, Recall@3, and MFR by at 4.107%, 5.113%, 4.289%, and 24.536%, respectively.
  arXiv  Detail & Related papers  (2025-05-02T04:29:09Z)
• MA-GTS: A Multi-Agent Framework for Solving Complex Graph Problems in Real-World Applications [22.705728671135834]
  Graph-theoretic problems arise in real-world applications like logistics, communication networks, and traffic optimization.<n>Large language models (LLMs) offer potential solutions but face challenges, including limited accuracy and input length constraints.<n>We propose MA-GTS, a multi-agent framework that decomposes these complex problems through agent collaboration.
  arXiv  Detail & Related papers  (2025-02-25T08:34:00Z)
• Beyond Message Passing: Neural Graph Pattern Machine [50.78679002846741]
  We introduce the Neural Graph Pattern Machine (GPM), a novel framework that bypasses message passing by learning directly from graph substructures.<n>GPM efficiently extracts, encodes, and prioritizes task-relevant graph patterns, offering greater expressivity and improved ability to capture long-range dependencies.
  arXiv  Detail & Related papers  (2025-01-30T20:37:47Z)
• Dinkel: State-Aware and Granular Framework for Validating Graph Databases [6.966247442329522]
  Graph database management systems (GDBMSs) have been powering many data-driven applications.<n>We propose a novel and practical approach Dinkel, to thoroughly test GDBMSs.
  arXiv  Detail & Related papers  (2024-08-14T13:00:24Z)
• GADBench: Revisiting and Benchmarking Supervised Graph Anomaly Detection [44.501646702560635]
  GADBench is a benchmark tool dedicated to supervised anomalous node detection in static graphs. Our main finding is that tree ensembles with simple neighborhood aggregation can outperform the latest GNNs tailored for the GAD task.
  arXiv  Detail & Related papers  (2023-06-21T13:16:10Z)
• RU-Net: Regularized Unrolling Network for Scene Graph Generation [92.95032610978511]
  Scene graph generation (SGG) aims to detect objects and predict the relationships between each pair of objects. Existing SGG methods usually suffer from several issues, including 1) ambiguous object representations, and 2) low diversity in relationship predictions. We propose a regularized unrolling network (RU-Net) to address both problems.
  arXiv  Detail & Related papers  (2022-05-03T04:21:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.