Systematically Cover SQL Syntactic Structures via 𝑘-Sequence

Abstract

Testing Relational Database Management Systems (RDBMSs) is inherently challenging because SQL, the primary language for interacting with RDBMSs, exhibits a vast and highly complex grammar with hundreds of interdependent production rules in the Extended Backus--Naur Form. While existing grammar-based testing techniques have made progress in covering SQL syntactic structures, they predominantly focus on parent-child relationships in derivation paths, which capture vertical expansions from a non-terminal to its alternatives. However, they overlook an equally critical dimension, sibling-like relationships, which capture co-occurring alternatives across derivation paths. This oversight results in insufficient coverage of intricate syntactic interactions that may trigger unique behaviors or latent bugs in RDBMSs. In this work, we propose k-sequence, a novel coverage criterion that characterizes syntactic structures as ordered sequences of k alternatives encountered during derivation. By simultaneously capturing both vertical parent-child and horizontal sibling-like relationships in the SQL syntactic structures, k-sequence provides a unified framework for comprehensive SQL syntactic coverage. Based on this criterion, we develop KSeqFuzz, a directed fuzzing approach that systematically generates SQL statements to explore previously unseen k-sequences, achieving deeper and broader testing coverage. We implement and evaluate KSeqFuzz on four widely-deployed RDBMSs, i.e., MySQL, MariaDB, TiDB, and OceanBase. In total, KSeqFuzz detects 58 new unique bugs, including 6 critical crashes. Evaluation results demonstrate that KSeqFuzz outperforms state-of-the-art baselines, detecting 26% more unique bugs during 24-hour testing campaigns.