Bug: Heap Buffer Overflow
(1) By Yu Liang (LY1598773890) on 2021-07-03 01:58:07 [source]
Query
CREATE TABLE v0 ( v1, v2, v3, FOREIGN KEY ( v1, v1, v1, v1, v1, v1, v1, v1, v1, v1, v1, v1, v1 ) REFERENCES t0 );
INSERT INTO v0 VALUES ( 18446744073709551615, 'x', 'four' );
PRAGMA foreign_key_check;
Bug
The query above triggers a heap based buffer overflow when testing with the latest commit of sqlite (55e2fbebb0a2c999). The ASAN output is as follows:
=================================================================
==26238==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x61d0000013c8 at pc 0x00000064ee66 bp 0x7ffc6245fd70 sp 0x7ffc6245fd68
READ of size 2 at 0x61d0000013c8 thread T0
#0 0x64ee65 in sqlite3VdbeExec /home/sqlite/sqlite-asan-build/sqlite3.c:89413:7
#1 0x5712c9 in sqlite3Step /home/sqlite/sqlite-asan-build/sqlite3.c:84974:10
#2 0x5712c9 in sqlite3_step /home/sqlite/sqlite-asan-build/sqlite3.c:85031
#3 0x557643 in exec_prepared_stmt /home/sqlite/sqlite-asan-build/shell.c:14164:8
#4 0x51e40e in shell_exec /home/sqlite/sqlite-asan-build/shell.c:14473:7
#5 0x55c009 in runOneSqlLine /home/sqlite/sqlite-asan-build/shell.c:21449:8
#6 0x52235a in process_input /home/sqlite/sqlite-asan-build/shell.c:21549:17
#7 0x4feee5 in main /home/sqlite/sqlite-asan-build/shell.c
#8 0x7f1e6bcb083f in __libc_start_main /build/glibc-S7Ft5T/glibc-2.23/csu/../csu/libc-start.c:291
#9 0x41b278 in _start (/home/sqlite/sqlite-asan-build/sqlite3+0x41b278)
0x61d0000013c8 is located 8 bytes to the right of 2368-byte region [0x61d000000a80,0x61d0000013c0)
allocated by thread T0 here:
#0 0x4bb9a3 in malloc /home/sqlite/llvm_source/llvm/projects/compiler-rt/lib/asan/asan_malloc_linux.cc:88:3
#1 0x8e429c in sqlite3MemMalloc /home/sqlite/sqlite-asan-build/sqlite3.c:24178:7
SUMMARY: AddressSanitizer: heap-buffer-overflow /home/sqlite/sqlite-asan-build/sqlite3.c:89413:7 in sqlite3VdbeExec
Shadow bytes around the buggy address:
0x0c3a7fff8220: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c3a7fff8230: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c3a7fff8240: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c3a7fff8250: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c3a7fff8260: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x0c3a7fff8270: 00 00 00 00 00 00 00 00 fa[fa]fa fa fa fa fa fa
0x0c3a7fff8280: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c3a7fff8290: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c3a7fff82a0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c3a7fff82b0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c3a7fff82c0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Freed heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
Container overflow: fc
Array cookie: ac
Intra object redzone: bb
ASan internal: fe
Left alloca redzone: ca
Right alloca redzone: cb
==26238==ABORTING
Running the debug version
leads to the following assertion failure:
sqlite3: sqlite3.c:89245: sqlite3VdbeExec: Assertion `pOp->p3>0 && pOp->p3<=(p->nMem+1 - p->nCursor)' failed.
Bisecting
It seems this bug has been in the source code for a while. Here is an incomplete bisect result:
6 BAD 2021-07-02 12:25:30 55e2fbebb0a2c999 CURRENT
2 BAD 2020-11-25 20:29:45 f4b7c10057a50c5b
3 BAD 2020-02-04 20:22:32 76668b55894a9c75
1 BAD 2018-07-27 20:01:00 865249de683e6971
5 BAD 2016-02-05 21:09:26 22589018ac3321f7
(2.1) By Richard Hipp (drh) on 2021-07-03 10:41:23 edited from 2.0 in reply to 1 [link] [source]
When there is a foreign key with more columns than the underlying table, the code generator fails to allocate enough registers in the virtual machine to handle all the columns in the foreign key. This came about because when we were writing the code for "PRAGMA foreign_key_check", it never occurred to us that anybody would construct a foreign key with more columns than the underlying table. The problem goes back to SQLite 3.8.1, 2013-10-17.
Now fixed on trunk.
(3.1) By Richard Hipp (drh) on 2021-07-03 16:03:59 edited from 3.0 in reply to 1 [link] [source]
Are you not compiling with -DSQLITE_DEBUG? Adding that #define to your fuzzer will enable assert() statements in the code, which will often find these kinds of problems much faster. In particular, this problem assert()s before ASAN finds any problems.
When Michał Zalewski first invented AFL, it used it to finds some bugs in SQLite. When I suggested he add the -DSQLITE_DEBUG option, his find rate went way up. There are over 6000 assert() statements in SQLite. Enabling them will often find problems that ASAN, MSAN, and UBSAN miss.
(4) By Yu Liang (LY1598773890) on 2021-07-03 15:30:35 in reply to 3.0 [link] [source]
Thank you for the very good advice. :-)
We do use the -DSQLITE_DEBUG version for fuzzing. Actually, we observe the assertion failure first in our fuzzing tool, and then use ASAN to generate the heap buffer report.
We are very happy to provide more information if needed, and produce more reports in the future to make the software better!