PaperlayerView exact revision on arXiv

Source-linked AI summary

SQUIRREL: Testing Database Management Systems with Language Validity and Coverage Feedback

Rui Zhong, Yongheng Chen, Hong Hu, Hangfan Zhang, Wenke Lee, Dinghao Wu

arXiv:2006.02398v1cs.CR

TL;DR

DBMS fuzzing struggles because mutation-based inputs often fail syntax or semantic checks, while generation-based testing lacks feedback-guided exploration. Sqirrel combines syntax-preserving IR mutation with dependency-aware instantiation, and it found memory-error bugs while improving semantic correctness and coverage over existing tools. Its effectiveness varies with DBMS-specific SQL dialects and feedback behavior.

  • Problem

    Mutation-based fuzzers struggle with DBMS syntax and semantic checks, while generation-based testing lacks feedback to guide exploration.

  • Method

    Sqirrel uses a structural SQL IR for syntax-preserving type-based mutation and analyzes data dependencies to instantiate semantically valid queries.

  • Results

    Sqirrel found 63 memory-error issues across four DBMSs, achieved 2.4×-243.9× higher semantic correctness, and discovered 2.0×-10.9× more new edges than mutation-based tools.

  • Takeaways & Limitations

    The evaluation shows that combining language validity with coverage feedback is effective for finding memory-related DBMS bugs.

  • Takeaways & Limitations

    Sqirrel’s effectiveness is limited by DBMS-specific SQL dialects and by coverage feedback that can favor grammar-incorrect queries.

Abstract

from arXiv · show

Fuzzing is an increasingly popular technique for verifying software functionalities and finding security vulnerabilities. However, current mutation-based fuzzers cannot effectively test database management systems (DBMSs), which strictly check inputs for valid syntax and semantics. Generation-based testing can guarantee the syntax correctness of the inputs, but it does not utilize any feedback, like code coverage, to guide the path exploration. In this paper, we develop Squirrel, a novel fuzzing framework that considers both language validity and coverage feedback to test DBMSs. We design an intermediate representation (IR) to maintain SQL queries in a structural and informative manner. To generate syntactically correct queries, we perform type-based mutations on IR, including statement insertion, deletion and replacement. To mitigate semantic errors, we analyze each IR to identify the logical dependencies between arguments, and generate queries that satisfy these dependencies. We evaluated Squirrel on four popular DBMSs: SQLite, MySQL, PostgreSQL and MariaDB. Squirrel found 51 bugs in SQLite, 7 in MySQL and 5 in MariaDB. 52 of the bugs are fixed with 12 CVEs assigned. In our experiment, Squirrel achieves 2.4x-243.9x higher semantic correctness than state-of-the-art fuzzers, and explores 2.0x-10.9x more new edges than mutation-based tools. These results show that Squirrel is effective in finding memory errors of database management systems.

1 Introduction

DBMS fuzzing must satisfy both syntax and semantics before reaching deep execution logic, yet mutation and generation approaches each leave a gap. Sqirrel combines syntax-preserving mutation with semantics-guided instantiation and finds substantially more DBMS bugs and coverage than prior tools.

  • Motivation: Generation-based testing distributes effort across the SQL input space without feedback, making rare bug-triggering queries difficult to find.The input space is effectively infinite, and brute-force-like enumeration is ineffective for memory-error discovery.
  • Motivation: DBMSs reject queries with syntax or semantic errors before optimization and execution, limiting fuzzers that produce invalid inputs.Random mutation rarely guarantees syntax correctness, while grammar-based generation may fail semantic validation.
  • Approach: Sqirrel combines syntax-preserving IR mutation with semantics-guided instantiation to generate valid SQL while retaining feedback-guided fuzzing.Its IR supports type-based statement insertion, deletion, and replacement after stripping concrete data into skeletons.
  • Results: Sqirrel found nine unique bugs in 24 hours, discovered 2.0×-10.9× more new edges than mutation-based tools, and achieved 2.4×-243.9× higher semantic correctness.Its edge coverage was comparable to SQLsmith, a generation-based tester.

2 Problem Definition

DBMS testing must reach optimization and execution through queries that pass syntax and semantic checks. Existing generation and mutation methods each provide only part of the needed validity or exploration guidance, motivating a hybrid design.

  • Query Processing: DBMS query processing proceeds through parsing, validation, optimization, and execution, with later phases reachable only after earlier correctness checks pass.Parsing checks grammar, while validation checks properties such as table existence and column ambiguity.
  • Existing Techniques: Model-based generation constructs syntactically correct SQL but explores the input space without sufficient guidance and can still produce semantically invalid queries.Such queries may be rejected during validation, as when a WHERE clause references a nonexistent table.
  • Existing Techniques: Feedback-guided random mutation explores program state efficiently, but byte-level mutations struggle to preserve SQL syntax and semantics.AFL generated 20 million SQLite queries in 24 hours, yet only about 30% passed syntax checks and 4% passed semantic checks.
  • Our Insight: Sqirrel introduces syntax-correct and semantics-aware mutation to combine mutation-based feedback with generation-based validity.Its IR and type-based mutations target syntax correctness, while dependency-aware instantiation targets semantic correctness.

3 Overview of Sqirrel

Sqirrel transforms existing SQL queries into mutable IR, generates syntax-correct skeletons, instantiates values satisfying inferred dependencies, and executes the resulting SQL to detect crashes.

  • Overview: Sqirrel selects an initial or previously interesting query, translates it into a vector of IR statements, and mutates the IR to produce a new candidate.The framework uses Translator, Mutator, Instantiator, and SQL Fuzzer components.
  • Overview: The mutated IR is syntactically correct, after which the Instantiator builds a dependency graph and fills it with concrete values satisfying those dependencies.The resulting query is therefore likely to be semantically correct.
  • Overview: Sqirrel converts the instantiated IR back to SQL and executes it against the DBMS, treating a crash as a bug and otherwise using execution feedback for continued fuzzing.The overview targets queries that crash the DBMS.

4 Intermediate Representation

Sqirrel represents SQL as a linear, SSA-form IR that preserves structural information while enabling uniform mutations and translation back to SQL. This representation supports type-aware statements and simple insertion, deletion, and replacement operations.

  • IR Design: Sqirrel translates SQL into an IR and back again, using the representation to support syntax-correct query mutation.The IR is designed to be expressive for SQL statements, general in format and operations, and efficient to translate.
  • IR Design: The IR uses static single assignment form, where each statement assigns a destination variable from a literal or an operator with operands.IR fields include statement types and operators corresponding to SQL or mathematical operations.
  • Example: The running example shows AST nodes translated into IR statements representing names, references, expressions, parameter lists, and clauses.Figure 3 presents the IR and Figure 4 presents the corresponding AST.
  • Mutation: Unlike tree or graph representations such as ASTs, the IR is a linear sequence of assignments that enables unified mutation strategies.Sqirrel can insert, delete, or replace statements while maintaining syntactic correctness.

5 Syntax-Preserving Mutation

Squirrel separates SQL structure from data and mutates an intermediate representation using type-compatible operations, preserving syntax while exploring new query structures.

  • 5 Syntax-Preserving Mutation: Squirrel strips concrete data before mutation because changing query structure affects DBMS execution paths more than changing literal values.Data modification is deferred to the semantics-guided instantiation stage.
  • 5 Syntax-Preserving Mutation: IR programs store structural variants by type in a library, allowing mutations to reuse distinct same-type IRs and add newly discovered structures.The library is initialized from seed queries and updated when generated IRs introduce new structures.
  • 5 Syntax-Preserving Mutation: Type-based insertion, replacement, and deletion mutate IR statements or operands while respecting structural types.Insertion adds compatible IRs, replacement substitutes same-type IRs or operands, and deletion removes optional operands.
  • 5 Syntax-Preserving Mutation: Syntax validation parses each mutated IR after conversion to SQL and discards queries that fail parsing.Type-based manipulation preserves syntactic correctness with high probability but does not guarantee it.
  • 5 Syntax-Preserving Mutation: Figure 5 illustrates insertion of ORDERBY, replacement with CountClause, and deletion of a WHERE clause, producing three syntactically correct IRs.The figure summarizes the supported mutation strategies on IR programs.

6 Semantics-Guided Instantiation

Squirrel improves semantic validity by inferring dependencies among data in syntax-correct IR skeletons and instantiating values that satisfy those dependencies.

  • 6 Semantics-Guided Instantiation: Dependency-guided instantiation fills mutated, data-stripped IR skeletons with concrete values that satisfy inferred relationships between semantic-binding data.The resulting queries have a high chance of being semantically correct.
  • 6.1 Data Dependency Inference: Squirrel infers dependencies using lifetime and customization principles: variables must be defined before use, while types, scopes, and operations constrain relationships.These rules identify relationships such as isAnElement and isA among SQL data.
  • 6.2 IR Instantiation: Figure 7 shows one concrete dependency graph replacing placeholders with values and producing a final SQL query.The example assigns a newly created table name to a later UseAnyTable value through the dependency relation.
  • 6.1 Data Dependency Inference: Refined data types encode definition or use status, scope, and context-specific database roles to identify valid candidate dependencies.For example, CreateTable, UseAnyTable, and UseFromTable distinguish where and how table values may be used.
  • 6.1 Data Dependency Inference: The system constructs a dependency graph whose nodes are typed IR data and whose edges connect dependent values, randomly selecting among multiple valid candidates.Random selection avoids circular dependencies and supports multiple concrete graphs for one mutated IR.
  • 6.2 IR Instantiation: Instantiation processes dependency-graph nodes in breadth-first and statement order, generating unique names for definitions and reusing mapped values for dependent uses.Literal values are randomized or drawn from predefined sets; unsatisfiable dependencies leave semantic errors.

7 Implementation

Squirrel is implemented as a 43,783-line C++ system with a general, DBMS-customizable AST parser supporting most documented grammar features.

  • 7 Implementation: Squirrel contains 43,783 lines of code and uses a general AST parser customized for DBMS-specific features.The parser is based on Bison 3.3.2 and Flex 2.6.4 and supports most documented grammar features while excluding some administrative functionality.

8 Evaluation

SQUIRREL finds memory-error bugs across production DBMSs and outperforms tested mutation-based fuzzers in validity, coverage, and bug discovery. Its evaluation shows that syntax-preserving mutation, semantics-guided instantiation, and coverage feedback jointly improve exploration, while feedback has the strongest contribution.

  • 8.1 DBMS Bugs: 63 bugs were found across SQLite, MySQL, and MariaDB, with 52 fixed and 12 assigned CVE numbers.The findings include 51 SQLite bugs, 7 MySQL bugs, and 5 MariaDB bugs.
  • 8.1 DBMS Bugs: SQUIRREL uncovered diverse memory errors, including 12 buffer overflows, 2 use-after-free bugs, and 33 SQLite assertion failures.One assertion failure led to a high-severity use-after-free vulnerability in SQLite’s released binary.
  • 8.2 Comparison with Existing Tools: SQUIRREL found the first SQLite crash in four minutes and about 600 unique crashes, compared with AFL’s first crash in 32 minutes and 30 total crashes.QSYM found its first crash in 14 minutes and 13 crashes overall, while Angora, GRIMOIRE, and SQLsmith found none during the 24-hour test.
  • 8.2 Comparison with Existing Tools: SQUIRREL achieved 1.8×-20.9× higher syntax correctness and 2.4×-243.9× higher semantic correctness than comparison tools.It was comparable to SQLsmith for syntax correctness overall, except where SQLsmith was highly customized for PostgreSQL grammar.
  • 8.3 Contributions of Validity and Feedback: Ablation results show that syntax, semantics, and feedback all contribute to memory-error discovery, with coverage feedback having the greatest impact.The full system found 600 unique crashes, versus 30 without semantic guidance, 10 without syntax preservation and semantic guidance, and 3 without feedback.

9 Discussion

The discussion identifies DBMS-specific logic, incomplete dependency rules, coverage collisions, and harmful feedback as limitations of Sqirrel’s current implementation.

  • DBMS-Specific Logic: DBMS-specific SQL dialects and operand checks limit Sqirrel’s effectiveness, producing many more bugs on SQLite than on PostgreSQL, MySQL, and MariaDB.The authors plan more accurate dialect grammars and PostgreSQL type-consistency relations.
  • Relation-Rule Construction: Sqirrel’s dependency rules are manually written from domain knowledge and cover only 133 clauses after two authors spent two hours constructing them.Future work considers data-flow analysis or machine learning to infer relations automatically.
  • Collisions in Code-Coverage: 14% of SQLite’s approximately 20,000 branches share AFL bitmap entries, creating coverage collisions that the evaluation mitigates by enlarging the bitmap to 256K.The authors plan to adopt CollAFL to eliminate the collision problem.
  • Alternative Feedback Mechanisms: Coverage feedback can favor grammar-incorrect queries because their fault-handling branches appear novel, diverting testing from semantics-correct queries.The authors propose dropping inputs that trigger new branches during short executions.

10 Related Work

Related work includes differential, generation-based, and mutation-based DBMS testing, while Sqirrel targets memory corruption with structurally valid and semantically guided SQL.

  • Detecting Logic and Performance Bugs in DBMSs: Sqirrel differs from logic- and performance-bug testers by focusing on memory corruption bugs, which can cause severe security consequences.Related systems use differential testing, row-fetch checks, tuning, execution-time comparisons, or predefined performance thresholds.
  • Generation-based DBMS Testing: Generation-based testers can efficiently produce syntax-correct cases but seldom guarantee semantic correctness, while SQLsmith restricts query types and relies on initial schemas.Sqirrel instead generates context-free cases from an empty database and creates required content before testing.
  • Mutation-based DBMS Testing: General mutation-based fuzzers lack awareness of highly structured DBMS inputs and therefore struggle to generate SQL with correct semantics.Grammar-like synthesis remains syntactically incorrect, while grammar-component mutation may preserve syntax without guaranteeing semantic correctness.

11 Conclusion

Sqirrel combines syntax-preserving mutation with semantics-guided instantiation to fuzz DBMSs and identify memory-related bugs across four systems.

  • 11 Conclusion: Sqirrel found 51 bugs in SQLite, 7 in MySQL, and 5 in MariaDB, achieving at least 3.4x higher semantic correctness and up to 12x higher code coverage than existing fuzzers.The evaluation also included PostgreSQL, and the authors conclude that Sqirrel is effective and efficient for DBMS testing.

Algorithm 3: Dependency Graph Construction.

Algorithm 3 constructs a dependency DAG for stripped data-carrying IRs by matching relation-defined types to earlier candidate IRs and selecting dependency edges.

  • Algorithm 3: Dependency Graph Construction: The algorithm takes an IR set and predefined relation set as input and produces a dependency DAG.It initializes a graph map and result vectors for the IRs before processing relations.
  • Algorithm 3: Dependency Graph Construction: For each relation, the algorithm matches an IR whose data type is the relation’s dependent type with an earlier IR of the required matching type.Candidate IRs are restricted to those positioned before the dependent IR in the query.
  • Algorithm 3: Dependency Graph Construction: The algorithm chooses one candidate according to the relation’s properties and records the resulting mapping as a dependency edge.Choosing one candidate avoids circular dependencies and ensures each graph node has at most one parent.
  • Algorithm 3: Dependency Graph Construction: The IR represents SSA-form assignment statements whose expressions use literals or two-operand operations, enabling uniform mutation and later conversion back to SQL strings.AST queries are translated into IRs using depth-first traversal, with multi-child nodes combined in grammar order and intermediate nodes marked Unknown.
  • Algorithm 3: Dependency Graph Construction: After dependency construction, IR roots are converted to SQL query strings by recursively returning stored data or combining operator components.The conversion algorithm’s stated output is the SQL query string.
  • Algorithm 3: Dependency Graph Construction: Sqirrel creates graph nodes for data-carrying IRs after stripping concrete data, then searches for nodes matching each relation’s required type.The graph construction procedure applies relation pairs of the form “N depends on M” to connect corresponding typed nodes.

D PoCs for Case Study

The case studies present proof-of-concept SQL programs for several discovered bugs, including database leakage, use-after-free, and bugs with short lifetimes. Additional tables report statistical significance and the numbers of generated test cases by validity category.

  • Case studies: Squirrel produced PoCs for an 11-year-old bug, database leakage, a use-after-free triggered by an assertion, and bugs lasting one day or one hour.The examples include SQL programs demonstrating each case-study bug.
  • Case studies: A database-leakage PoC creates a view recursively referencing itself and then selects duplicated view columns.
  • Case studies: The use-after-free PoC combines an indexed table, a virtual R-tree table, joins, and self-joins with predicates involving repeated column names.
  • Case studies: The one-day bug PoC uses CHECK and UNIQUE generated-column constraints before an INSERT and a CROSS JOIN with a USING clause.
  • Case studies: The one-hour bug PoC repeatedly applies ZIPFILE to inserted values after dropping a table, then selects the resulting value in hexadecimal.
  • Evaluation summaries: Table 6 reports p-values comparing Squirrel with other fuzzers, while Table 7 counts generated test cases across syntax-error, semantic-error, and semantic-correctness categories.Table 6 marks p-values below 0.05 as statistically significant; Table 7 covers a 24-hour evaluation.
Loading 2006.02398v1…