Quick sort is recursive. It divides the sort data into two sections, moves some elements around, then recurses to sort each section. The BSD implementation, largely taken from Bentley & McIlroy's "Engineering a Sort Function", omits the tail recursion in order to save stack space. However, it always sorts the "left" section by recursion, even when it is large relative to the "right" section. Imagine crafted data such that each time the routine must recurse the "right" section is extremely small. Maybe only a few elements wide. This would necessitate a maximum stack depth on the order of N, where N is the number of elements being sorted. If, however, the routine always chose to sort the *smaller* of the two sub-sections via recursion, then the maximum stack depth would be at worst log2(N). Qsort should test the "width" of each section before recursing, and always choose to sort the smaller one via recursion. This results in an optimally low worst-case in terms of required stack space.
Please see: https://github.com/freebsd/freebsd/pull/94
(In reply to jhoward from comment #1) Hi; I am CC'ing Andrey Chernov as he has done changes in qsort(3). The change is interesting, but it has to be benchmarked first. Perhaps you can try the tests in lib/libc/tests/stdlib/ and see how the compare to the existing code? FWIW, ministat(1) is welcome too ;). Also, we generally don't touch the stuff in contrib until the changes are reviewed by upstream maintainers.
Unfortunately I don't have a working FreeBSD environment to use. This patch came about because I pulled down the qsort code for a separate project (just needed a good implementation to tinker with) and noticed the potential for the recursion to be exploited using crafted sort data. Can you point me to a reference on how to run the tests you mentioned? I'll work on finding a FreeBSD VM I can use, and/or code to generate sort data that breaks the existing qsort implementation. That at least proves there's an issue. Since the kernel also uses the same implementation, if someone could find a way to pass crafted sort data to the kernel version, I'd imagine there could be security implications.
(In reply to jhoward from comment #3) Thanks for looking into it. I have just been too busy. BTW, if you could upload a diff to bugzilla it would be much better. You can check the standalone tests here: https://svnweb.freebsd.org/base/stable/9/tools/regression/lib/libc/stdlib/ (Newer FreeBSD versions have integrated the regression tool into the testsuite.) I think I had a random testcase with more datapoints somewhere to verify the last commit. and you can get VM images from ftp, for example here: ftp://ftp.freebsd.org/pub/FreeBSD/releases/VM-IMAGES/11.0-RELEASE/ About exploitability, it very much depends on where qsort() is used, opengrok is your friend, and if you are able to realistically generate such sequence. I am aware there are cases where the algorithm can be suboptimal; it may be the case that the algorithm needs revision (I just haven't seen a case in real life).
Created attachment 180381 [details] Diff from pull request Uploading patch form https://github.com/freebsd/freebsd/pull/94
Closing https://github.com/freebsd/freebsd/pull/94
Seems related to r318515, which was applied to libc only while the atachement also applies to libkern (and heimdal).
A commit references this bug: Author: delphij Date: Fri May 19 06:37:16 UTC 2017 New revision: 318517 URL: https://svnweb.freebsd.org/changeset/base/318517 Log: Sync qsort.c with userland r318515. (Note that MIN macro is removed in favor of sys/param.h's version). PR: 213922 Changes: head/sys/libkern/qsort.c
A commit references this bug: Author: delphij Date: Fri May 26 06:09:11 UTC 2017 New revision: 318917 URL: https://svnweb.freebsd.org/changeset/base/318917 Log: Disconnect heimdal version of qsort.c from build because we are already using libc's version of qsort. PR: bin/213922 MFC after: 2 weeks Differential Revision: https://reviews.freebsd.org/D10814 Changes: head/kerberos5/lib/libroken/Makefile
A commit references this bug: Author: delphij Date: Wed May 31 05:52:33 UTC 2017 New revision: 319285 URL: https://svnweb.freebsd.org/changeset/base/319285 Log: MFC r318514-r318515, r318517, r318917 r318514: Use size_t. Inspired by: OpenBSD src/lib/libc/stdlib/qsort.c,v 1.11 r318515: The current qsort(3) implementation ignores the sizes of partitions, and always perform recursion on the left partition, then use a tail call to handle the right partition. In the worst case this could require O(N) levels of recursions. Reduce the possible recursion level to log2(N) by always recursing on the smaller partition instead. Obtained from: PostgreSQL 9d6077abf9d6efd992a59f05ef5aba981ea32096 r318517: Sync qsort.c with userland r318515. (Note that MIN macro is removed in favor of sys/param.h's version). PR: 213922 r318917: Disconnect heimdal version of qsort.c from build because we are already using libc's version of qsort. PR: bin/213922 Changes: _U stable/11/ stable/11/kerberos5/lib/libroken/Makefile stable/11/lib/libc/stdlib/qsort.c stable/11/sys/libkern/qsort.c
A commit references this bug: Author: delphij Date: Wed May 31 06:26:38 UTC 2017 New revision: 319291 URL: https://svnweb.freebsd.org/changeset/base/319291 Log: MFC r318514-r318515, r318517, r318917 r318514: Use size_t. Inspired by: OpenBSD src/lib/libc/stdlib/qsort.c,v 1.11 r318515: The current qsort(3) implementation ignores the sizes of partitions, and always perform recursion on the left partition, then use a tail call to handle the right partition. In the worst case this could require O(N) levels of recursions. Reduce the possible recursion level to log2(N) by always recursing on the smaller partition instead. Obtained from: PostgreSQL 9d6077abf9d6efd992a59f05ef5aba981ea32096 r318517: Sync qsort.c with userland r318515. (Note that MIN macro is removed in favor of sys/param.h's version). PR: 213922 r318917: Disconnect heimdal version of qsort.c from build because we are already using libc's version of qsort. PR: bin/213922 Changes: _U stable/10/ stable/10/kerberos5/lib/libroken/Makefile stable/10/lib/libc/stdlib/qsort.c stable/10/sys/libkern/qsort.c