[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20240204163520.GA20987@openwall.com>
Date: Sun, 4 Feb 2024 17:35:20 +0100
From: Solar Designer <solar@...nwall.com>
To: oss-security@...ts.openwall.com
Cc: Qualys Security Advisory <qsa@...lys.com>,
Adhemerval Zanella <adhemerval.zanella@...aro.org>
Subject: Re: Out-of-bounds read & write in the glibc's qsort()
Hi,
Great findings and excellent quality write-up from Qualys, as usual.
On Tue, Jan 30, 2024 at 06:39:37PM +0000, Qualys Security Advisory wrote:
> We therefore decided to assess the robustness of the glibc's qsort()
> implementation, by calling it with a nontransitive comparison function:
>
> ------------------------------------------------------------------------
> 1 #include <limits.h>
> 2 #include <stdlib.h>
> 3 #include <sys/time.h>
> 4
> 5 static int
> 6 cmp(const void * const pa, const void * const pb)
> 7 {
> 8 const int a = *(const int *)pa;
> 9 const int b = *(const int *)pb;
> 10 return (a - b);
> 11 }
> 12
> 13 int
> 14 main(const int argc, const char * const argv[])
> 15 {
> 16 if (argc != 2) return __LINE__;
> 17 const size_t nmemb = strtoul(argv[1], NULL, 0);
> 18 if (nmemb <= 0 || nmemb >= (1<<28)) return __LINE__;
> 19
> 20 int * const pcanary1 = calloc(1 + nmemb + 1, sizeof(int));
> 21 if (!pcanary1) return __LINE__;
> 22 int * const array = pcanary1 + 1;
> 23 int * const pcanary2 = array + nmemb;
> 24
> 25 struct timeval tv;
> 26 if (gettimeofday(&tv, NULL)) return __LINE__;
> 27 srandom((tv.tv_sec << 16) ^ tv.tv_usec);
> 28
> 29 const int canary1 = *pcanary1 = (random() << 16) ^ random();
> 30 const int canary2 = *pcanary2 = (random() << 16) ^ random();
> 31 array[random() % nmemb] = INT_MIN;
> 32
> 33 qsort(array, nmemb, sizeof(int), cmp);
> 34 if (*pcanary1 != canary1) abort();
> 35 if (*pcanary2 != canary2) abort();
> 36 return 0;
> 37 }
I've attached an enhanced version of the above program to this message.
> We therefore decided to assess the robustness of the glibc's quick sort
> (instead of its merge sort, which was clearly not crashing), by forcing
> qsort() to call _quicksort(). Locally, forcing the malloc() at line 221
> to fail is very easy: we simply execute our program with a low RLIMIT_AS
> ("The maximum size of the process's virtual memory", man setrlimit); and
> this works even when executing a SUID-root program. So we executed our
> program in the following loop instead:
>
>
> ------------------------------------------------------------------------
> $ while true; do n=$((RANDOM*64+RANDOM+1)); prlimit --as=$((n*4/2*3)) ./qsort $n; done
> Aborted (core dumped)
While we have to do it externally with "prlimit" or such when attacking
an existing program, for our own testing we can instead set RLIMIT_AS
right from the test program. This eliminates the need for choosing a
value for RLIMIT_AS that's barely sufficient for the program to work,
but not sufficient for glibc to choose merge sort. In the attached
program, I simply set RLIMIT_AS to 0 right before the call to qsort(),
which lets the program continue running (even though it's already beyond
limit) but makes any further memory allocations from the kernel fail.
I also added a test that the sort order is correct when qsort() is
called with a proper, transitive comparison function.
This makes me wonder whether/how glibc upstream tests quick sort, given
that without the RLIMIT_AS trick or such that code is not reached. If
glibc tests do not include this yet (I didn't see it), then maybe they
should make use of the "set RLIMIT_AS to 0" trick in a bundled test?
Searching the glibc tree for RLIMIT_AS now, I see some tests do set it
for similar reasons, but none of them are for qsort() and they use
various non-zero values.
> To patch these out-of-bounds memory accesses in _quicksort(), a simple
> check "tmp_ptr > base_ptr &&" can be added in front of the cmp() call at
> line 227 (of course this does not magically result in a correctly sorted
> array if cmp() is nontransitive, but at least it does not result in a
> memory corruption anymore).
I confirmed (with the attached test program) that this one-line change
indeed makes qsort() robust also when applied on top of RHEL9's patched
glibc 2.34, as found in Rocky Linux 9 (patch attached). We now use this
in Rocky Linux SIG/Security package of glibc for EL9:
https://sig-security.rocky.page/packages/glibc/
> In fact, while drafting this advisory, we discovered that such a check
> ("tmp_ptr != base_ptr &&") has already been added to the glibc's master
> branch (which will become glibc 2.39 in February 2024), by the following
> commit ("stdlib: Fix array bounds protection in insertion sort phase of
> qsort"):
>
> https://sourceware.org/git?p=glibc.git;a=commit;h=b9390ba93676c4b1e87e218af5e7e4bb596312ac
This commit also adds a test, but I don't see how that test would
possibly detect the issue. It sorts a tiny array and does not set
RLIMIT_AS, so it probably does not reach quick sort, does it? Well,
maybe it did briefly while glibc experimented with introsort, but
perhaps currently it does not:
As you've identified in the "last-minute note", a later commit ("stdlib:
Reinstate stable mergesort implementation on qsort") made/reverted lots
of other changes:
https://sourceware.org/git/?p=glibc.git;a=commit;h=709fbd3ec3595f2d1076b4fec09a739327459288
It's so invasive I cannot easily tell whether qsort() remained robust
after it or not. There's no longer a "tmp_ptr != base_ptr &&" check.
So, lacking known-working tests in glibc tree, we don't know about glibc
2.39's status with respect to this issue.
I don't have a glibc 2.39 build handy. Perhaps someone on a distro that
has already updated can run the attached test program and let us know?
Alexander
View attachment "glibc-qualys-rocky-qsort-test.c" of type "text/x-c" (1566 bytes)
View attachment "glibc-2.34-qualys-rocky-qsort.patch" of type "text/plain" (564 bytes)
Powered by blists - more mailing lists
Please check out the
Open Source Software Security Wiki, which is counterpart to this
mailing list.
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
