[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Date: Tue, 30 Jan 2024 18:39:37 +0000
From: Qualys Security Advisory <qsa@...lys.com>
To: "oss-security@...ts.openwall.com" <oss-security@...ts.openwall.com>
Subject: Out-of-bounds read & write in the glibc's qsort()
Qualys Security Advisory
For the algorithm lovers: Nontransitive comparison functions lead to
out-of-bounds read & write in glibc's qsort()
========================================================================
Contents
========================================================================
Summary
Background
Experiments
Analysis
Patch
Discussion
Acknowledgments
Timeline
CUT MY LIST IN TWO PIECES
THAT'S HOW YOU START QUICK SORT
-- https://twitter.com/QuinnyPig/status/1710447650112438710
========================================================================
Summary
========================================================================
We discovered a memory corruption in the glibc's qsort() function, due
to a missing bounds check. To be vulnerable, a program must call qsort()
with a nontransitive comparison function (a function cmp(int a, int b)
that returns (a - b), for example) and with a large number of attacker-
controlled elements (to cause a malloc() failure inside qsort()). We
have not tried to find such a vulnerable program in the real world.
All glibc versions from at least September 1992 (glibc 1.04) to the
current release (glibc 2.38) are affected, but the glibc's developers
have independently discovered and patched this memory corruption in the
master branch (commit b9390ba, "stdlib: Fix array bounds protection in
insertion sort phase of qsort") during a recent refactoring of qsort().
About our advisory, the glibc security team issues the following
statement:
------------------------------------------------------------------------
This memory corruption in the GNU C Library through the qsort function is
invoked by an application passing a non-transitive comparison function, which
is undefined according to POSIX and ISO C standards. As a result, we are of
the opinion that the resulting CVE, if any, should be assigned to any such
calling applications and subsequently fixed by passing a valid comparison
function to qsort and not to glibc. We however acknowledge that this is a
quality of implementation issue and we fixed this in a recent refactor of
qsort. We would like to thank Qualys for sharing their findings and helping
us validate our recent changes to qsort.
------------------------------------------------------------------------
========================================================================
Background
========================================================================
While browsing through Postfix's HISTORY file, we stumbled across a
puzzling entry from February 2002:
------------------------------------------------------------------------
Bugfix: make all recipient comparisons transitive, because
Solaris qsort() causes SIGSEGV errors otherwise. Victor
Duchovni, Morgan Stanley. File: *qmgr/qmgr_message.c.
------------------------------------------------------------------------
Segmentation faults in qsort()? Transitive comparison functions?
As explained in the manual page for qsort(), "The comparison function
must return an integer less than, equal to, or greater than zero if the
first argument is considered to be respectively less than, equal to, or
greater than the second." Of course, such a comparison function cmp()
must be transitive:
- if a < b (i.e., if cmp(pointer_to(a), pointer_to(b)) < 0);
- and if b < c (i.e., if cmp(pointer_to(b), pointer_to(c)) < 0);
- then necessarily a < c (i.e., cmp(pointer_to(a), pointer_to(c)) < 0).
For example, the following comparison function (which compares integers)
is transitive (and perfectly correct):
------------------------------------------------------------------------
int
cmp(const void * const pa, const void * const pb)
{
const int a = *(const int *)pa;
const int b = *(const int *)pb;
if (a > b) return +1;
if (a < b) return -1;
return 0;
}
------------------------------------------------------------------------
A shorter and more efficient version of this comparison function could
simply "return (a > b) - (a < b);" and still be transitive and perfectly
correct:
- if a > b, it returns 1 - 0 = +1;
- if a < b, it returns 0 - 1 = -1;
- if a = b, it returns 0 - 0 = 0.
The question, then, is: how can a comparison function be nontransitive?
A comparison function cmp() is nontransitive if there exist a, b, and c
such that:
- a < b (because cmp(pointer_to(a), pointer_to(b)) < 0);
- b < c (because cmp(pointer_to(b), pointer_to(c)) < 0);
- but a >= c (because cmp(pointer_to(a), pointer_to(c)) >= 0 by
mistake).
Although the following comparison function seems correct at first, it is
in fact nontransitive, because the subtraction in "return (a - b);" is
prone to integer overflows:
------------------------------------------------------------------------
int
cmp(const void * const pa, const void * const pb)
{
const int a = *(const int *)pa;
const int b = *(const int *)pb;
return (a - b);
}
------------------------------------------------------------------------
For example, if a = INT_MIN, b = 0, and c = INT_MAX, then:
- a < b (because cmp(pointer_to(a), pointer_to(b)) returns INT_MIN - 0,
which is correctly negative);
- b < c (because cmp(pointer_to(b), pointer_to(c)) returns 0 - INT_MAX,
which is also correctly negative);
- but a > c by mistake (because cmp(pointer_to(a), pointer_to(c))
returns INT_MIN - INT_MAX = +1, which is incorrectly positive because
this subtraction overflows).
Unfortunately, such nontransitive comparison functions are extremely
common, as discussed in this excellent blog post from Ted Unangst:
https://flak.tedunangst.com/post/subtraction-is-not-comparison
and as hinted at in OpenBSD's manual page for qsort(): "It is almost
always an error to use subtraction to compute the return value of the
comparison function."
Fortunately, when passed to a robust qsort() implementation, these
nontransitive comparison functions should (at the worst) result in an
incorrectly sorted array; certainly not in a memory corruption. However,
the aforementioned entry from Postfix's HISTORY file suggests that not
all qsort() implementations are robust.
========================================================================
Experiments
========================================================================
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 }
------------------------------------------------------------------------
- at lines 5-11, cmp() is the nontransitive comparison function
introduced in the previous "Background" section;
- at lines 16-18, the number of elements to be sorted (simple integers)
is read from the command line;
- at lines 20-23, the array of elements to be sorted is calloc()ated,
along with a canary element below this array, and a canary element
above this array;
- at lines 29-30, these two canary elements are randomized, and copied
to the stack for later comparison;
- at line 31, one random element of the array is initialized to INT_MIN
(all other elements are initialized to 0 by calloc());
- at line 33, the elements of this array are sorted by qsort();
- at lines 34-35, the two canary elements (below and above the sorted
array) are checked against their stack copies, and if they differ (an
out-of-bounds write in qsort()), abort() is called.
We chose the array elements a = INT_MIN and b = 0 because they directly
exhibit the problematic behavior of this cmp() function:
- a < b, because cmp(pointer_to(a), pointer_to(b)) returns INT_MIN - 0,
which is correctly negative;
- but b < a by mistake, because cmp(pointer_to(b), pointer_to(a))
returns 0 - INT_MIN = INT_MIN (the "Leblancian Paradox"), which is
incorrectly negative (because this subtraction overflows).
We then executed our test program in a loop, on Fedora 39 (which uses
the latest glibc version, 2.38):
------------------------------------------------------------------------
$ while true; do n=$((RANDOM*64+RANDOM+1)); ./qsort $n; done
------------------------------------------------------------------------
Unsurprisingly, nothing happened: our program did not crash or abort().
While this loop was still running (and not crashing), we started to read
the glibc's qsort() implementation; to our great surprise, we discovered
that the glibc's qsort() is not, in fact, a quick sort by default, but a
merge sort (in stdlib/msort.c).
Most likely, merge sort was chosen over quick sort to avoid quick sort's
worst-case performance, which is O(n^2); on the other hand, merge sort's
worst-case performance is O(n*log(n)). But merge sort suffers from one
major drawback: it does not sort in-place -- it malloc()ates a copy of
the array of elements to be sorted. As a result, if this array is very
large (lines 212-217), or if this malloc() fails (lines 219-229), then
the glibc's qsort() falls back to a quick sort (in stdlib/qsort.c),
because quick sort does sort in-place:
------------------------------------------------------------------------
163 void
164 __qsort_r (void *b, size_t n, size_t s, __compar_d_fn_t cmp, void *arg)
165 {
166 size_t size = n * s;
...
170 /* For large object sizes use indirect sorting. */
171 if (s > 32)
172 size = 2 * n * sizeof (void *) + s;
173
174 if (size < 1024)
175 /* The temporary array is small, so put it on the stack. */
176 p.t = __alloca (size);
177 else
178 {
...
212 /* If the memory requirements are too high don't allocate memory. */
213 if (size / pagesize > (size_t) phys_pages)
214 {
215 _quicksort (b, n, s, cmp, arg);
216 return;
217 }
218
219 /* It's somewhat large, so malloc it. */
220 int save = errno;
221 tmp = malloc (size);
222 __set_errno (save);
223 if (tmp == NULL)
224 {
225 /* Couldn't get space, so use the slower algorithm
226 that doesn't need a temporary array. */
227 _quicksort (b, n, s, cmp, arg);
228 return;
229 }
230 p.t = tmp;
231 }
...
299 }
------------------------------------------------------------------------
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)
Aborted (core dumped)
Aborted (core dumped)
...
------------------------------------------------------------------------
Incredibly, we almost immediately observed crashes of our test program:
calls to abort(), because one of our canary elements (below or above the
sorted array) was overwritten (i.e., an out-of-bounds write in qsort()).
To understand these crashes, we examined one of them in gdb:
------------------------------------------------------------------------
$ gdb prlimit
(gdb) run --as=8104854 ./qsort 1350809
Starting program: /usr/bin/prlimit --as=8104854 ./qsort 1350809
...
Program received signal SIGABRT, Aborted.
__pthread_kill_implementation (threadid=<optimized out>, signo=signo@...ry=6, no_tid=no_tid@...ry=0) at pthread_kill.c:44
44 return INTERNAL_SYSCALL_ERROR_P (ret) ? INTERNAL_SYSCALL_ERRNO (ret) : 0;
(gdb) backtrace
#0 __pthread_kill_implementation (threadid=<optimized out>, signo=signo@...ry=6, no_tid=no_tid@...ry=0) at pthread_kill.c:44
#1 0x00007ffff7e698a3 in __pthread_kill_internal (signo=6, threadid=<optimized out>) at pthread_kill.c:78
#2 0x00007ffff7e178ee in __GI_raise (sig=sig@...ry=6) at ../sysdeps/posix/raise.c:26
#3 0x00007ffff7dff8ff in __GI_abort () at abort.c:79
#4 0x0000555555555334 in main (argc=2, argv=0x7fffffffe338) at qsort.c:34
(gdb) select-frame 4
(gdb) p/x canary1
$1 = 0xc6109e4c
(gdb) p/x *pcanary1
$2 = 0x0
(gdb) x/xw pcanary1 - 2
0x7ffff78af008: 0x00528002
0x7ffff78af00c: 0x80000000
0x7ffff78af010: 0x00000000
0x7ffff78af014: 0xc6109e4c
0x7ffff78af018: 0x00000000
------------------------------------------------------------------------
- at address 0x7ffff78af010 (pcanary1), the original value of the canary
(0xc6109e4c) was overwritten with 0x0 -- an out-of-bounds write;
- at address 0x7ffff78af00c (below pcanary1), the most significant word
of an mchunk_size (heap metadata) was overwritten with 0x80000000
(INT_MIN) -- another out-of-bounds write;
- at address 0x7ffff78af014 (above pcanary1), the first element of the
array was overwritten with 0xc6109e4c (the original value of the
canary), which was therefore read out-of-bounds beforehand (from
pcanary1).
========================================================================
Analysis
========================================================================
To identify the root cause of these out-of-bounds memory accesses, we
must analyze the implementation of the glibc's quick sort:
------------------------------------------------------------------------
87 void
88 _quicksort (void *const pbase, size_t total_elems, size_t size,
89 __compar_d_fn_t cmp, void *arg)
90 {
91 char *base_ptr = (char *) pbase;
...
108 while (STACK_NOT_EMPTY)
109 {
...
193 }
...
206 char *tmp_ptr = base_ptr;
...
214 for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size)
215 if ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0)
216 tmp_ptr = run_ptr;
217
218 if (tmp_ptr != base_ptr)
219 SWAP (tmp_ptr, base_ptr, size);
...
223 run_ptr = base_ptr + size;
224 while ((run_ptr += size) <= end_ptr)
225 {
226 tmp_ptr = run_ptr - size;
227 while ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0)
228 tmp_ptr -= size;
...
246 }
...
248 }
------------------------------------------------------------------------
- at lines 108-193, when quick sort's partitions become smaller than
MAX_THRESH (4 elements), _quicksort() switches to a final insertion
sort (at lines 206-246), which is faster than quick sort for small or
mostly sorted arrays;
- at lines 206-219, this insertion sort makes sure that the very first
element of the array (base_ptr) is the smallest element of the array;
- at lines 226-228, this first element acts as a natural barrier that
prevents tmp_ptr from being decremented below the array (because if
tmp_ptr reaches base_ptr, then necessarily cmp(run_ptr, tmp_ptr) >= 0
because tmp_ptr is base_ptr, the smallest element of the array);
- unfortunately this does not hold true if cmp() is nontransitive, in
which case cmp(run_ptr, tmp_ptr) can be < 0 even if tmp_ptr is
base_ptr, so tmp_ptr can be decremented below the array, where
out-of-bounds elements are read and overwritten.
========================================================================
Patch
========================================================================
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).
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
Indeed, the glibc developers have recently refactored qsort() and
replaced the merge sort (and its fallback to quick sort) with an
introspective sort (a combination of quick sort, heap sort, and
insertion sort):
https://en.wikipedia.org/wiki/Introsort
https://sourceware.org/pipermail/libc-alpha/2023-October/151907.html
During this refactoring, the glibc developers have proactively
discovered (and patched) the out-of-bounds memory accesses in the
insertion sort (probably because these out-of-bounds memory accesses
became directly exposed to the misbehavior of nontransitive comparison
functions, instead of being safely hidden behind a malloc() failure in
the merge sort).
Last-minute note: in January 2024, the glibc developers have reverted
this refactoring of qsort(), back to the original merge sort, plus a
fallback to heap sort instead of quick sort; for more information:
https://sourceware.org/pipermail/libc-alpha/2024-January/154051.html
========================================================================
Discussion
========================================================================
We have not tried to find a vulnerable program (i.e., a program that
uses a nontransitive comparison function to qsort() attacker-controlled
elements); however, vulnerable programs are certain to exist in the real
world:
- calls to qsort() are extremely common;
- nontransitive comparison functions are also common;
- all glibc versions from at least September 1992 (glibc 1.04, the first
version that we could find online) to the current release (glibc 2.38)
are affected by this memory corruption.
Locally, forcing a malloc() failure in qsort() (which is necessary to
reach the memory corruption) is easy: either execute the target program
(e.g., a SUID-root program) with a low RLIMIT_AS, or allocate a large
amount of memory with another program on the same machine.
Remotely, forcing this malloc() failure is harder: either allocate a
large amount of memory (e.g., a memory leak) in the network service that
is being targeted, or in another network service on the same machine.
========================================================================
Acknowledgments
========================================================================
We thank the glibc security team and the linux-distros@...nwall.
========================================================================
Timeline
========================================================================
2023-12-12: We sent a draft of our advisory to the glibc security team.
They immediately acknowledged receipt of our email.
2023-12-19: The glibc security team decided to not treat this memory
corruption in qsort() as a vulnerability in the glibc itself, as
explained in the "Summary" of our advisory.
2024-01-16: We backported commit b9390ba to all current and past stable
versions of the glibc, and sent this patch and a draft of our advisory
to the linux-distros@...nwall (to piggyback on the glibc embargo for
CVE-2023-6246). They immediately acknowledged receipt of our email.
2024-01-30: Coordinated Release Date (18:00 UTC).
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.
