  Relational databases are used ubiquitously. They are managed by database
management systems (DBMS), which allow inserting, modifying, and querying data
using a domain-specific language called Structured Query Language (SQL).
Popular DBMS have been extensively tested by fuzzers, which have been
successful in finding crash bugs. However, approaches to finding logic bugs,
such as when a DBMS computes an incorrect result set, have remained mostly
untackled. Differential testing is an effective technique to test systems that
support a common language by comparing the outputs of these systems. However,
this technique is ineffective for DBMS, because each DBMS typically supports
its own SQL dialect. To this end, we devised a novel and general approach that
we have termed Pivoted Query Synthesis. The core idea of this approach is to
automatically generate queries for which we ensure that they fetch a specific,
randomly selected row, called the pivot row. If the DBMS fails to fetch the
pivot row, the likely cause is a bug in the DBMS. We tested our approach on
three widely-used and mature DBMS, namely SQLite, MySQL, and PostgreSQL. In
total, we reported 123 bugs in these DBMS, 99 of which have been fixed or
verified, demonstrating that the approach is highly effective and general. We
expect that the wide applicability and simplicity of our approach will enable
the improvement of robustness of many DBMS.
