Testing Database Engines via Pivoted Query Synthesis.pdf

上善若水

205

17页

5次

2022-05-30

免费下载

This paper is included in the Proceedings of the

14th USENIX Symposium on Operating Systems

Design and Implementation

November 4–6, 2020

978-1-939133-19-9

Open access to the Proceedings of the

14th USENIX Symposium on Operating

Systems Design and Implementation

is sponsored by USENIX

Testing Database Engines via

Pivoted Query Synthesis

Manuel Rigger and Zhendong Su, ETH Zurich

https://www.usenix.org/conference/osdi20/present ation/rigger

Testing Database Engines via Pivoted Query Synthesis

Manuel Rigger Zhendong Su

Department of Computer Science, ETH Zurich

Abstract

Database Management Systems (DBMSs) are used widely,

and have been extensively tested by fuzzers, which are suc-

cessful in ﬁnding crash bugs. However, approaches to ﬁnding

logic bugs, such as when a DBMS computes an incorrect

result set, have remained mostly untackled. 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 speciﬁc, 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 DBMSs, namely SQLite, MySQL, and Post-

greSQL. In total, we found 121 unique bugs in these DBMSs,

96 of which have been ﬁxed or veriﬁed, demonstrating that

the approach is highly effective and general. We expect that

the wide applicability and simplicity of our approach will

enable improving the robustness of many DBMSs.

1 Introduction

Database management systems (DBMSs) based on the rela-

tional model [10] are a central component in many applica-

tions, since they allow efﬁciently storing and retrieving data.

They have been extensively tested by random query gener-

ators such as SQLsmith [45], which have been effective in

ﬁnding queries that cause the DBMS process to crash (e.g.,

by causing a buffer overﬂow). Also fuzzers such as AFL [2]

are routinely applied to DBMSs. However, these approaches

cannot detect logic bugs, which we deﬁne as bugs that cause a

query to return an incorrect result, for example, by erroneously

omitting a row, without crashing the DBMS.

Logic bugs in DBMSs are difﬁcult to detect automatically.

A key challenge for automatic testing is to come up with an

effective test oracle, that can detect whether a system behaves

correctly for a given input [21]. In 1998, Slutz proposed to

use differential testing [33] to detect logic bugs in DBMSs,

by constructing a test oracle that compares the results of a

query on multiple DBMSs, which the author implemented

in a tool RAGS [46]. While RAGS detected many bugs, dif-

ferential testing comes with the signiﬁcant limitation that

the systems under test need to implement the same seman-

tics for a given input. All DBMSs support a common and

standardized language Structured Query Language (SQL) to

create, access, and modify data [8]. In practice, however, each

DBMS provides a plethora of extensions to this standard and

deviates from it in other parts (e.g., in how

NULL

values are

handled [46]). This vastly limits differential testing, and also

the author stated that the small common core and the dif-

ferences between different DBMSs were a challenge [46].

Furthermore, even when all DBMSs fetch the same rows,

it cannot be ensured that they work correctly, because they

might be affected by the same underlying bug.

To efﬁciently detect logic bugs in DBMSs, we propose

a general and principled approach that we termed Pivoted

Query Synthesis (PQS), which we implemented in a tool

called SQLancer. The core idea is to solve the oracle problem

for a single, randomly-selected row, called the pivot row, by

synthesizing a query whose result set must contain the pivot

row. We synthesize the query by randomly generating expres-

sions for

WHERE

and

JOIN

clauses, evaluating the expressions

based on the pivot row, and modifying each expression to

yield

TRUE

. If the query, when processed by the DBMS, fails

to fetch the pivot row, a bug in the DBMS has been detected.

We refer to this oracle as the containment oracle.

Listing 1 illustrates our approach on a test case that trig-

gered a bug that we found using the containment oracle in

the widely-used DBMS SQLite. The

CREATE TABLE

statement

creates a new table

with a column

. Subsequently, an in-

dex is created and three rows with the values

, and

NULL

are inserted. We select the pivot row

c0=NULL

and construct

the random

WHERE

clause

c0 IS NOT 1

. Since

NULL IS NOT

evaluates to

TRUE

, we can directly pass the query to the

DBMS, expecting the row with value

NULL

to be contained

in the result. However, due to a logic bug in the DBMS, the

partial index was used based on the incorrect assumption that

c0 IS NOT 1

implied

c0 NOT NULL

, resulting in the pivot row

USENIX Association 14th USENIX Symposium on Operating Systems Design and Implementation 667

of 17

免费下载

tidb

关注

评论