Griffin: Grammar-Free DBMS Fuzzing

Fuzzing is a promising approach to DBMS testing. One crucial component in DBMS fuzzing is grammar: since DBMSs enforce strict validation on inputs, a grammar improves fuzzing efficiency by generating syntactically- and semantically-correct SQL statements. However, due to the vast differences in the complex grammar of various DBMSs, it is painstaking to adapt these fuzzers to them. Considering that lots of DBMSs are not yet well tested, there is an urgent need for an effective DBMS fuzzing approach that is free from grammar dependencies. In this paper, we propose Griffin, a grammar-free mutation based DBMS fuzzer. Rather than relying on grammar, Griffin summarizes the DBMS's state into metadata graph, a lightweight data structure which improves mutation correctness in fuzzing. Specifically, it first tracks the metadata of the statements in built-in SQL test cases as they are executed, and constructs the metadata graph to describe the dependencies between metadata and statements iteratively. Based on the graphs, it reshuffles statements and employs metadata-guided substitution to correct semantic errors. We evaluate Griffin on MariaDB, SQLite, PostgreSQL, and DuckDB. Griffin covers 73.43%-274.70%, 80.47%-312.89%, 43.80%-199.11% more branches, and finds 27, 27, and 22 more bugs in 12 hours than SQLancer, SQLsmith, and Squirrel, respectively. In total, Griffin finds 55 previously unknown bugs with 13 CVEs assigned.