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.
What command did you use to run afl-fuzz properly?
ReplyDelete./afl-fuzz -i dir_with_sql_testcases -x testcases/_extras/sql.dict -o out_dir ./sqlite3_shell -bail
DeleteHave I understood it right that you grepped SQL test cases from here https://www.sqlite.org/src/dir?ci=9b8e5823bccf69f5&name=test and used them instead of the initial naive query "create table t1(one smallint); insert into t1 values(1); select * from t1;"?
ReplyDeleteYup, except for an extra afl-cmin step in the middle on the grepped-out testcases to reduce their number.
DeleteCan you share the SQL files that you got from the test cases? Or can you share a bash script that does it?
ReplyDeleteI don't have the script anymore, but they come from the files mentioned in your previous comment.
Delete