GRAF, a black box fuzzing framework for GDBMS query engines, introduces graph context aware query generation based on cascading dependency resolution and applies five graph specific mutation operators guided by execution state feedback.
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.
Relational Database Management Systems (RDBMSs) are the backbone of modern data-intensive applications, making reliability and robustness critical. However, achieving high coverage in RDBMS testing remains challenging because of large codebases and complex execution logic. Traditional fuzzing relies on random SQL generation and cannot capture the correspondence between SQL inputs and internal execution paths, while symbolic execution suffers from prohibitive cost and scalability limitations. We propose DBcover, an LLM-driven white-box SQL test generation framework based on contextual reasoning. DBcover uses lightweight dynamic analysis to extract SQL-to-path correspondence and call graphs as global context, and collects source-level information around target functions as local context. These contexts are organized in a unified knowledge graph for efficient retrieval and reuse. DBcover then performs two-phase test generation: it first selects a semantically relevant seed whose execution path is close to the uncovered target, and then guides the LLM with global and local context to generate SQL test cases that trigger previously uncovered code regions. Experiments show that DBcover achieves 80.1% and 82.3% coverage on PostgreSQL and MySQL, and is also effective on the enterprise RDBMS KingbaseES, demonstrating its practical applicability to closed-source systems.
Yan-Kai Rong, Shuang Liu, Jinhao Dong et al.· 0 citations
We investigate the data management of temporal property graphs on atemporal Labeled Property Graph (LPG) engines. While existing frameworks define temporal semantics, practitioners lack systematic empirical guidance on mapping these models to concrete representations in the absence of native engine support. We formalize two fundamental representation strategies implemented on top of standard LPG systems: a Versioning strategy that materializes temporal states via topological expansion, and a Property Lists strategy that encapsulates evolution through property-level compression. For each strategy, we define query translations for temporal evolution operators and analytical aggregations, and evaluate them across two heterogeneous real-world datasets. Our evaluation reveals a fundamental trade-off between topological selectivity and historical compactness: Versioning excels at high-throughput ingestion and short-window workloads but suffers from traversal amplification in dense graphs over long horizons, while Property Lists amortizes scan costs for read-heavy, multi-window analytics but incurs higher ingestion overhead and cannot support time-varying labels. We identify workload-dependent crossover points, showing how dataset density and structural volatility determine the superior strategy.
Fotios Kamanis, Georgia Koloniari, E. Pitoura· International Conference on...· 0 citations
Modern analytics is increasingly organized as recurring SQL pipelines rather than isolated SQL statements. Tools such as dbt, which have gained extreme popularity in recent years, allow teams to write each transformation as SQL and make dependencies between transformations explicit, producing directed acyclic graphs (DAGs) with hundreds or thousands of interdependent SQL models. Traditional query optimizers and source-to-source query rewriters operate on one query at a time, while materialized-view selection and multi-query optimization address narrower forms of reuse. They do not exploit the pipeline-level information exposed by explicit dependencies: how intermediate results are consumed, which downstream outputs depend on each computation, where expensive work sits relative to data reduction, which results are worth persisting, and how refresh schedules relate to input change and output demand. We introduce DAGSmith, to the best of our knowledge the first holistic dependency-aware source-to-source rewriting system for SQL pipeline DAGs. DAGSmith treats explicit dependencies as optimization signals. It analyzes each transformation with its upstream inputs, downstream consumers, and position in the pipeline DAG, uses an LLM to propose pipeline-level refactorings, separates SQL generation and equivalence checking to reject unsafe rewrites, retunes persistence choices with a learned cost model, and selects a globally compatible, conflict-free set of rewrites. This enables dependency-edge simplification, non-local semantic reuse, downstream-aware pruning, pipeline-aware work placement, rewrite-materialization co-optimization, and frequency-aware optimization. On the open-source Tuva dbt project, DAGSmith reduces elapsed time by 42.6% and warehouse compute cost by 67.7%, 98.1%/348.3% larger than state-of-the-art single-query rewriting.
ClosureBench is introduced, a constructive benchmark for compositional graph-relational reasoning with programmatically verified ground truth with programmatically verified ground truth: each task's reference answer is computed by executing a program in the Ein tensor-logic language, ensuring machine-verified correctness.
ARBIGRAPH is introduced, a benchmark generator for evaluating whether tool-assisted language agents can retain, update, compose, and discard task-relevant context across extended reasoning workflows, and shows that ARBIGRAPH exposes failures that are not visible from single-task evaluation alone.
Pavel Golikov, E. Opryshko, Gennady Pekhimenko et al.· 0 citations
This work proposes Explore-Construct-Verify (ECV), a three-stage framework for API KG construction using large language models (LLMs), which preserves LLMs’ ability to discover domain-specific knowledge while enabling efficient post-hoc validation.
Yanbang Sun, Qing Huang, Zhenchang Xing et al.· ACM Transactions on Software...· 0 citations