SQLancer

This post is based on work done with SQLancer.

SQLancer is a tool to automatically test Database Management Systems (DBMSs) in order to find bugs in their implementation. That is, it finds bugs in the code of the DBMS implementation, rather than in queries written by the user. SQLancer has found hundreds of bugs in mature and widely-known DBMSs.

Testing DBMSs

In automatic testing of DBMSs, there are two concerns:

• generation of test input (database schema, data, query)
• validation of test output (to detect bugs)

Common types of bugs in DBMSs

• Logical Bugs (incorrect query results)
• Data Integrity Bugs (corrupted data)
• Performance Bugs (slow queries)
• Access Control Bugs (unauthoized data access)
• Schema Design Bugs (poor database structure)
• Concurrency Control Bugs (inconsistencies during concurrent access)
• Data Type mismatch bugs (incorrect data type)

Here, we focus on logical bugs, where query is designed with incorrect logic, leading to inaccurate data retrieval or manipulation. These bugs are often hard to identify due to complexity of the query.

SQLancer can find logic bugs.

Here, we look at multiple complementary test oracles such as TLP, NoREC, PQS,DQP, CODDTest, CERT.

Naive Differential Testing DBMSs (naive / not comprehensive)

In a naive test case generation, we generate some random schema, generate a random query, and use a test oracle to verify the result to test the presence of any bug.

In order to verify the result, one way is to use differential testing, which is to make use of different DBMSs and test the same query. This way, if there is a difference in results, it is an indication that at least one is wrong.

However, there are some obvious limitations to this, including DBMS-specific SQL, and the potential of a wrong result (thus presence of bug) even if all DBMSs return the same result. Also, we wouldn’t be able to test DBMS-specific features.

Testing approaches (adopted by SQLancer)

TLP, PQS, NoREC, DQP (Tackling Test Oracle Problem)

Here, we tackling Test Oracle Problem to find logic Bugs.

Ternary Logic Partitioning (TLP)

TLP is based on Query Partitioning. Taking an original query, we equate the query into three partitions. It aims to find a valid partitioning strategy that stresses the DBMS.

For example, given a predicate X and a given row r, exactly one of the following must hold, which we call the ternary predicate variants:

* X
* not X
* X IS NULL

Then, if we find that e.g.

SELECT * from TABLE != SELECT * from TABLE WHERE X
                        UNION ALL from TABLE WHERE not X
                        UNION ALL from TABLE WHERE X is NULL

This inequality will show a bug.

Using this idea, we may apply TLP on queries with WHERE, GROUP BY, HAVING, DISTINCT queries, as well as aggregate functions, such asMAX, MIN, COUNT and so on.

CERT (Finding Potential Performance Issues)

Tackling test oracle problem to find potential performance issues. A DBMS, when doing query optimizing, has to balance between optimization time and execution time. It makes various tradeoffs to balance it.

Naive Testing of performance

• Measuring execution time is prone to performance fluctuations
• Is time consuming
• Potential False Alarms: generating equivalent queries and comparing them could result in many false alarms because of tradeoff between optimization and execution time (depending on the checks done to optimize a query and how it is implemented)

CERT: Cardinality Estimator Restriction Testing

Since DBMS translate a SQL query into a logical and then physical execution plan that is executed, which is readily made available (exposed) through the EXPLAIN statement, we can make use of the cardinality estimate (i.e. number of estimated rows returned) (e.g. for INDEX SCAN or FULL SCAN etc.)

Since the cardinality estimate is a key determinant in which physical execution plan is executed and hence resultant optimality of the query plan, we can look at the relative accuracy of the CE.

CERT: The cardinality estimator should be consistent (triangle inequality), and estimate fewer rows for a more restrictive query to be returned. Since we can determine the exact cardinalities by executing parts of the queries, but cardinality estimators cannot be expected to be close in all cases

• Key Insight is that a more restrictive query should be expected to fetch fewer or equal rows. (Cardinality Restriction Monotonicity Property)

SQLancer proposes 12 simple rules covering the common clauses of a query

• [ALL | DISTINCT]
• [ALL | WHERE]
• [LIMIT, HAVING, GROUP by]

By generating these types of queries and checking if the cardinality estimate violates these intuitive rules, we can look at how to optimize query plan generation.

(For example, it may detect bugs in reduction / selectivity factor with simple uniformity assumption / inclusion assumption)

QPG (Focusing on ‘interesting / comprehensive’ test inputs)

QPG: Query Plan Guidance

Another issue of naive test case generation is that the generators have no bias towards generating interesting test cases.

• E.g. test seq scan vs test indexed scan

Hence, in testing, we collect the query plan covered in a pool.

• If we do not observe a certain type of query plan
• Mutate the database state such that it promotes the use of different query plans.

Overall

SQLancer provides a systematic and innovative approach to uncovering bugs and performance issues in DBMSs through intelligent testing methodologies. By addressing common challenges such as the Test Oracle Problem and naive test case generation, SQLancer goes beyond basic testing to identify logical inconsistencies, optimize query execution, and ensure robust cardinality estimation.

Techniques like Ternary Logic Partitioning (TLP), Cardinality Estimator Restriction Testing (CERT), and Query Plan Guidance (QPG) enable SQLancer to test a wide range of DBMS features while minimizing false alarms and performance bottlenecks. By leveraging these methods, SQLancer has (already) successfully identified hundreds of bugs in mature DBMSs, proving its effectiveness in advancing the reliability and performance of database systems.