Heap-buffer overflow in nodeAcquire

[Even Rouault]

A heap-buffer overflow (sometimes a crash) can arise when running a SQL request on malformed sqlite3 databases such as the one attached to this ticket

{{{
$ valgrind sqlite3 clusterfuzz-testcase-minimized-4960347410661376 "SELECT pkid FROM 'idx_byte_metadata_geometry' WHERE xmax > 0 AND xmin < 0 AND ymax > 0 AND ymin < 0"
==21234== Memcheck, a memory error detector
==21234== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==21234== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info
==21234== Command: sqlite3 clusterfuzz-testcase-minimized-4960347410661376 SELECT\ pkid\ FROM\ 'idx_byte_metadata_geometry'\ WHERE\ xmax\ \>\ 0\ AND\ xmin\ \<\ 0\ AND\ ymax\ \>\ 0\ AND\ ymin\ \<\ 0
==21234== Invalid read of size 1
==21234== at 0x1B3945: nodeAcquire (in /usr/bin/sqlite3)
==21234== by 0x1B5056: rtreeFilter (in /usr/bin/sqlite3)
==21234== by 0x186EAA: sqlite3VdbeExec (in /usr/bin/sqlite3)
==21234== by 0x190316: sqlite3_step (in /usr/bin/sqlite3)
==21234== by 0x11886F: shell_exec.constprop.12 (in /usr/bin/sqlite3)
==21234== by 0x114693: main (in /usr/bin/sqlite3)
==21234== Address 0x5ae5b00 is 0 bytes after a block of size 48 alloc'd
==21234== at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==21234== by 0x14C176: sqlite3MemMalloc (in /usr/bin/sqlite3)
==21234== by 0x128380: sqlite3Malloc (in /usr/bin/sqlite3)
==21234== by 0x1B38DF: nodeAcquire (in /usr/bin/sqlite3)
==21234== by 0x1B5056: rtreeFilter (in /usr/bin/sqlite3)
==21234== by 0x186EAA: sqlite3VdbeExec (in /usr/bin/sqlite3)
==21234== by 0x190316: sqlite3_step (in /usr/bin/sqlite3)
==21234== by 0x11886F: shell_exec.constprop.12 (in /usr/bin/sqlite3)
==21234== by 0x114693: main (in /usr/bin/sqlite3)
}}}

This bug is no longer reproducible with at least sqlite3 3.17

{{{
$ valgrind ~/install-sqlite-3.17.0/bin/sqlite3 clusterfuzz-testcase-minimized-4960347410661376 "SELECT pkid FROM 'idx_byte_metadata_geometry' WHERE xmax > 0 AND xmin < 0 AND ymax > 0 AND ymin < 0"
==21265== Memcheck, a memory error detector
==21265== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==21265== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info
==21265== Command: /home/even/install-sqlite-3.17.0/bin/sqlite3 clusterfuzz-testcase-minimized-4960347410661376 SELECT\ pkid\ FROM\ 'idx_byte_metadata_geometry'\ WHERE\ xmax\ \>\ 0\ AND\ xmin\ \<\ 0\ AND\ ymax\ \>\ 0\ AND\ ymin\ \<\ 0
==21265==
Error: database disk image is malformed
}}}

This bug has been originally uncovered by OSS-Fuzz when running on the GDAL library that uses libsqlite3: https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=2405 (content not viewable during the grace period)

ProblemType: Bug
DistroRelease: Ubuntu 16.04
Package: sqlite3 3.11.0-1ubuntu1
ProcVersionSignature: Ubuntu 4.4.0-79.100-generic 4.4.67
Uname: Linux 4.4.0-79-generic x86_64
NonfreeKernelModules: nvidia_uvm nvidia_drm nvidia_modeset nvidia
ApportVersion: 2.20.1-0ubuntu2.6
Architecture: amd64
CurrentDesktop: GNOME-Flashback:Unity
Date: Wed Jun 28 11:18:29 2017
InstallationDate: Installed on 2016-11-04 (235 days ago)
InstallationMedia: Ubuntu 16.04.1 LTS "Xenial Xerus" - Release amd64 (20160719)
SourcePackage: sqlite3
UpgradeStatus: No upgrade log present (probably fresh install)

[Even Rouault (even-rouault)]

I've run git bisect on the https://github.com/mackyle/sqlite mirror of sqlite3 source code repository and spotted that the following commit fixes the issue :
https://github.com/mackyle/sqlite/commit/ce015fb42bbb6cafdbfc9b028c2ec0626a8f3217

This applies almost on top of sqlite 3.11.0 sources:

$ patch -p1 < /tmp/tmp.patch
patching file ext/rtree/rtree.c
Hunk #1 succeeded at 132 (offset -1 lines).
Hunk #2 succeeded at 506 (offset -113 lines).
Hunk #3 succeeded at 524 (offset -113 lines).
Hunk #4 succeeded at 541 (offset -113 lines).
Hunk #5 succeeded at 819 (offset -116 lines).
Hunk #6 succeeded at 858 (offset -116 lines).
Hunk #7 succeeded at 2961 (offset -220 lines).
Hunk #8 succeeded at 3002 (offset -220 lines).
Hunk #9 succeeded at 3055 (offset -227 lines).
Hunk #10 FAILED at 3490.
1 out of 10 hunks FAILED -- saving rejects to file ext/rtree/rtree.c.rej

The reject is
$ cat ext/rtree/rtree.c.rej
--- ext/rtree/rtree.c
+++ ext/rtree/rtree.c
@@ -3490,7 +3540,7 @@ static int rtreeInit(
   pRtree->zDb = (char *)&pRtree[1];
   pRtree->zName = &pRtree->zDb[nDb+1];
   pRtree->nDim = (u8)((argc-4)/2);
- pRtree->nDim2 = argc - 4;
+ pRtree->nDim2 = pRtree->nDim*2;
   pRtree->nBytesPerCell = 8 + pRtree->nDim2*4;
   pRtree->eCoordType = (u8)eCoordType;
   memcpy(pRtree->zDb, argv[1], nDb);

The nDim2 member doesn't exist in sqlite 3.11.0

I've attached the "clean" patch derived from this.

[Seth Arnold (seth-arnold)]

Hello Even, thanks for this. There's a lot of complexity in that patch, and the commit message includes "This is a work in progress". I'm not sure we should just apply this patch ourselves without further interaction with SQLite3 developers.

What constraints are we under via the oss-fuzz or GDAL projects?

Thanks

[Even Rouault (even-rouault)]

I agree the patch is complex (I don't understand it, just blindly git bisected and applied it), the commit message doesn't specifically mention addressing database corruption (the fact it fixes the bug seems to be a side-effect) and should be vetted by SQLite3 developers. OSS-Fuzz has a 90 day deadline period (https://github.com/google/oss-fuzz/), starting yesterday.

[Even Rouault (even-rouault)]

@seth-arnold Who does engage with SQLite3 developers: you/your team ?

[Seth Arnold (seth-arnold)]

Even, I just mailed some questions to http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users -- hopefully they'll have some advice.

Thank

[Even Rouault (even-rouault)]

Update from our exchanges with Richard Hipp, SQLite3 developper

The issue is hidden in SQLite 3.17.0 or later due to a refactoring in the RTree area. That said, he committed https://sqlite.org/src/vpatch?from=0db20efe201736b3&to=66de6f4a9504ec26 in SQLite3 master to detect the corruption earlier.

Last message from Richard Hipp:

"""
A proper fix for the problem can be seen at https://sqlite.org/src/info/66de6f4a

The change on trunk appears to be defensive code only. I have been
unable to generate any problems after the 3.11.0 optimizations. But
the defensive code has value in that it provides a better error
message, and it should help prevent any future problems.

You only need the patch to rtree.c, of course, not the new test case
in rtreeA.test.

This patch merges cleanly with SQLite version 3.10.2, and probably
most other prior versions. What version of SQLite did you say you are
using? The plain ASCII patch can be seen at
https://sqlite.org/src/vpatch?from=0db20efe201736b3&to=66de6f4a9504ec26
"""

This patch is small and I found it applies cleanly on top of 3.11.0 sources

patching file ext/rtree/rtree.c
Hunk #1 succeeded at 3153 (offset -282 lines).
patching file ext/rtree/rtreeA.test

and no Valgrind warning is emitted anymore

Attaching here the clean patch for 3.11.0 : rtree_commit_0db20efe201736b3&to=66de6f4a9504ec26.patch

[Ubuntu Foundations Team Bug Bot (crichton)]

The attachment "Proposed patch to apply on top of sqlite 3.11.0" seems to be a patch. If it isn't, please remove the "patch" flag from the attachment, remove the "patch" tag, and if you are a member of the ~ubuntu-reviewers, unsubscribe the team.

[This is an automated message performed by a Launchpad user owned by ~brian-murray, for any issues please contact him.]

[Seth Arnold (seth-arnold)]

Use CVE-2017-10989.

Thanks

[Even Rouault (even-rouault)]

@seth There's an error regarding the SQLite version number in the CVE text. It should read "in SQLite before 3.17.0" (and not 3.11.0)

[Seth Arnold (seth-arnold)]

On Fri, Jul 07, 2017 at 07:01:41PM -0000, Even Rouault wrote:
> @seth There's an error regarding the SQLite version number in the CVE
> text. It should read "in SQLite before 3.17.0" (and not 3.11.0)

Oh that's unfortuate. I didn't say it was fixed in -any- version in
my submission, because it felt to me the 3.17.0 was an accidental
no-longer-triggered case not actually fixed-case. After all, the fix
was checked into a master branch and no new releases appear to have been
tagged afterwards.

Thanks for the sharp eyes. I've submitted a change request.

[Even Rouault (even-rouault)]

Will there be a security package with the patch ?

[Seth Arnold (seth-arnold)]

Even, we've triaged this as a 'low' priority for our team: https://people.canonical.com/~ubuntu-security/cve/2017/CVE-2017-10989.html -- it might be a while before fixes are released.

Thanks