sqlancer: Detecting Logic Bugs in DBMS
SQLancer
SQLancer (Synthesized Query Lancer) is a tool to automatically test Database Management Systems (DBMS) in order to find logic bugs in their implementation. We refer to logic bugs as those bugs that cause the DBMS to fetch an incorrect result set (e.g., by omitting a record).
SQLancer operates in the following two phases:
- Database generation: The goal of this phase is to create a populated database, and stress the DBMS to increase the probability of causing an inconsistent database state that could be detected subsequently. First, random tables are created. Then, randomly SQL statements are chosen to generate, modify, and delete data. Also, other statements, such as those to create indexes as well as views and to set DBMS-specific options are sent to the DBMS.
- Testing: The goal of this phase is to detect the logic bugs based on the generated database. See Testing Approaches below.
Testing Approaches
| Approach | Description |
|---|---|
| Pivoted Query Synthesis (PQS) | PQS is the first technique that we designed and implemented. It randomly selects a row, called a pivot row, for which a query is generated that is guaranteed to fetch the row. If the row is not contained in the result set, a bug has been detected. It is fully described here. PQS is the most powerful technique, but also requires more implementation effort than the other two techniques. It is currently unmaintained. |
| Non-optimizing Reference Engine Construction (NoREC) | NoREC aims to find optimization bugs. It is described here. It translates a query that is potentially optimized by the DBMS to one for which hardly any optimizations are applicable and compares the two result sets. A mismatch between the result sets indicates a bug in the DBMS. |
| Ternary Logic Partitioning (TLP) | TLP partitions a query into three partitioning queries, whose results are composed and compare to the original query’s result set. A mismatch in the result sets indicates a bug in the DBMS. In contrast to NoREC and PQS, it can detect bugs in advanced features such as aggregate functions. |
Supported DBMS
Since SQL dialects differ widely, each DBMS to be tested requires a separate implementation.
| DBMS | Status | Expression Generation | Description |
|---|---|---|---|
| SQLite | Working | Untyped | This implementation is currently affected by a significant performance regression that still needs to be investigated |
| MySQL | Working | Untyped | Running this implementation likely uncovers additional, unreported bugs. |
| PostgreSQL | Working | Typed | |
| MariaDB | Preliminary | Untyped | The implementation of this DBMS is very preliminary since we stopped extending it after all but one of our bug reports were addressed. Running it likely uncovers additional, unreported bugs. |
| CockroachDB | Working | Typed | |
| TiDB | Working | Untyped | |
| DuckDB | Working | Untyped, Generic | |
| ClickHouse | Preliminary | Untyped, Generic | Implementing the different table engines was not convenient, which is why only a very preliminary implementation exists. |
| TDEngine | Removed | Untyped | We removed the TDEngine implementation since all but one of our bug reports were still unaddressed five months after we reported them. |
Install & Use
Copyright 2020 SQLancer Contributors
