Finding bugs in SQLite, the easy way

SQLite is probably the most popular embedded database in use today; it is also known for being exceptionally well-tested and robust. In contrast to traditional SQL solutions, it does not rely on the usual network-based client-server architecture and does not employ a complex ACL model; this simplicity makes it comparatively safe.

At the same time, because of its versatility, SQLite sometimes finds use as the mechanism behind SQL-style query APIs that are exposed between privileged execution contexts and less-trusted code. For an example, look no further than the WebDB / WebSQL mechanism available in some browsers; in this setting, any vulnerabilities in the SQLite parser can open up the platform to attacks.

With this in mind, I decided to take SQLite for a spin with - you guessed it - afl-fuzz. As discussed some time ago, languages such as SQL tend to be difficult to stress-test in a fully automated manner: without an intricate model of the underlying grammar, random mutations are unlikely to generate anything but trivially broken statements. That said, afl-fuzz can usually leverage the injected instrumentation to sort out the grammar on its own. All I needed to get it started is a basic dictionary; for that, I took about 5 minutes to extract a list of reserved keywords from the SQLite docs (now included with the fuzzer as testcases/_extras/sql/). Next, I seeded the fuzzer with a single test case:

create table t1(one smallint);
insert into t1 values(1);
select * from t1;

This approach netted a decent number of interesting finds, some of which were mentioned in an earlier blog post that first introduced the dictionary feature. But when looking at the upstream fixes for the initial batch, I had a sudden moment of clarity and recalled that the developers of SQLite maintained a remarkably well-structured and comprehensive suite of hand-written test cases in their repository.

I figured that this body of working SQL statements may be a much better foundation for the fuzzer to build on, compared to my naive query - so I grepped the test cases out, split them into files, culled the resulting corpus with afl-cmin, and trimmed the inputs with afl-tmin. After a short while, I had around 550 files, averaging around 220 bytes each. I used them as a starting point for another run of afl-fuzz.

This configuration very quickly yielded a fair number of additional, unique fault conditions, ranging from NULL pointer dereferences, to memory fenceposts visible only under ASAN or Valgrind, to pretty straightforward uses of uninitialized pointers (link), bogus calls to free() (link), heap buffer overflows (link), and even stack-based ones (link). The resulting collection of 22 crashing test cases is included with the fuzzer in docs/vuln_samples/sqlite_*. They include some fairly ornate minimized inputs, say:

CREATE VIRTUAL TABLE t0 USING fts4(x,order=DESC);
INSERT INTO t0(docid,x)VALUES(-1E0,'0(o');
INSERT INTO t0 VALUES('');
INSERT INTO t0 VALUES('');
INSeRT INTO t0 VALUES('o');
SELECT docid FROM t0 WHERE t0 MATCH'"0*o"';

All in all, it's a pretty good return on investment for about 30 minutes of actual work - especially for a piece of software functionally tested and previously fuzzed to such a significant extent.

PS. I was truly impressed with Richard Hipp fixing each and every of these cases within a couple of hours of sending in a report. The fixes have been incorporated in version 3.8.9 of SQLite and have been public for a while, but there was no upstream advisory; depending on your use case, you may want to update soon.