9 ms·
Out-of-bounds read and write in the glibc's qsort()
- goalieca 3y agoThat’s a pretty cool find. It just goes to show even some of the oldest and most widely used open source libraries still have security issues. This is a rare corner case but it’s still a fantastic find. I suppose no static analysis tools found it over all those years.
- ericdfoley 3y agoThis has always been an issue with sorting float arrays that contain NaN in C or C++ (e.g. with std::sort() with the default "<" comparator.)
- vitiral 3y agowhat has been? OOB errors?
- ericdfoley 3y agoSeg faults
- vitiral 3y agoso... you're saying you've hit this exact bug before? I bet that was a fun debug session!
- charcircuit 3y agoIt's not new. They are just passing in an invalid parameter. If you pass random parameters into a function like memcpy it will do bad stuff too. C APIs were not all designed to be safe to call and can commonly crash or introduce a vulnerability.
- jhallenworld 3y agoI can imagine the future memcpy CVE: "arguments to memcpy to regions not previously allocated or after having been freed can potentially cause security issues. Therefore we propose that memcpy check its arguments against this new list of valid memory addresses that we are now going to keep around..." So what I mean is: how much performance are we giving up with this "fix" for qsort?
- anonymoushn 3y agothe glibc qsort function is already something you only use if you don't care about performance.
- sureglymop 3y agoThen what is a better alternative? I was always told that I shouldn't implement something as trivial as sorting algorithms by myself...
- tokedo 3y agoA simple solution is to create a C++ file and exposing sorting functions to C. E.g. "void sort_int(int *data, size_t n)". The implementation uses then std::sort. Unfortunately, qsort is really slow and sometimes barely usable.
- CyberDildonics 3y agoYou were told correctly, but there is a lot of room between using the C standard library and making your own sort. C++ STL std::sort is one, but the internet is filled with libraries you can download, of course you can find a better alternative with a search.
- SAI_Peregrinus 3y agoARM Morello does that check in hardware.
- MathMonkeyMan 3y ago
- deleted 3y ago[deleted]
- moyix 3y agoIt's a bit debatable whether this is a security bug vs a "you're holding it wrong" kind of bug, but fixing the bounds check is a good defensive practice and I'm glad they implemented it. Somewhat tangentially, Microsoft at one point got in a bit of trouble for trying to use a randomized comparison function to implement shuffling on their "Browser choice" page: https://www.robweir.com/blog/2010/02/microsoft-random-browser-ballot.html https://www.robweir.com/blog/2010/02/microsoft-random-browse...
- dralley 3y agoRust generally does consider "you're holding it wrong" type bugs to be safety issues. See for example [0], where the Rust developers filed a CVE for (and fixed) an issue in the standard library which the C / C++ communities mostly considered a holding-it-wrong issue. [0] https://www.reddit.com/r/cpp/comments/151cnlc/a_safety_culture_and_c_we_need_to_talk_about/ https://www.reddit.com/r/cpp/comments/151cnlc/a_safety_cultu...
- bregma 3y agoA you're-holding-it-wrong that still got fixed in all the major C++ standard library implementations.
- pests 3y agoFixed?
- bregma 3y agoCode was added to libc++ and libstdc++ to avoid the TOCTOU exploit documented in the CVE. "Fixed" in this case means the source code for the library was modified to prevent the documented exploit, and test cases were added to their test suites to exercise the code. Not sure about the Microsoft C++ standard library since the Microsoft Windows system API does not provide the same softlink functionalty.
- jacquesm 3y ago
- up2isomorphism 3y agoFunction pointer essentially is how functions gets passed how is a bug in the function a security issue? It is within the same security boundary.
- jandrese 3y agoIntresting that the problem only occurs when using a buggy comparison function, but one of the most obvious comparison functions is buggy (a - b can suffer from integer overflow) so this vulnerability may very well exist in the wild.
- deleted 3y ago[deleted]
- adrian_b 3y agoThey link there a posting that does not explain properly why such comparison functions are buggy: "subtraction is not comparison". In fact comparison is really just subtraction where the result is ignored, only the condition flags are updated in the same way as by any other subtraction. The difference is elsewhere. In machine language, after either an integer subtraction or an integer comparison, the relationship between the operands is not tested by using the sign of the result. It is tested instead by using the true sign of the result, which is computed by the addition modulo 2 (a.k.a. XOR) between the sign of the result and the overflow flag. In the currently popular high-level programming languages it is no longer possible to access the overflow flag. (In many early programming languages there were available facilities like "on overflow do ...".) Had this been possible, the qsort comparison function could have been implemented as a subtraction, with the result conditionally corrected in case of overflow. Therefore in languages like C and derivatives one must always use the relational operators ">", "<", ">=" and "<=", because these are implemented by the compiler using conditional instructions that test the true sign computed with the overflow flag, after the subtraction of the operands.
- hedora 3y agoRust has a checked_add function for this purpose. Also, by default, Rust's integer operations trap on overflow, so if you wrote the obvious comparator (x-y) the program would panic instead of exhibiting undefined behavior.
- adrian_b 3y agoBy default, i.e. in release builds, Rust's integer operations do not trap on overflow. I do not consider that the behavior of a debug build can be considered as "default". I consider the disabling of the overflow traps a very bad practice, which is justified only for specific functions or code sequences that have been analyzed carefully to prove that overflows are impossible. For example, the chain of exploits that have been used to gain complete remote control of any iPhone without detection during many years has included some that were based on integer overflows in the Apple system software.
- sgift 3y agoI see the glibc security team fell back to a variant of the age old "oh, but it's undefined behavior, so if we burn down your computer that's okay too!" justification why they shouldn't be assigned an CVE for this. > 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. Disappointing. Not unexpected, but still disappointing. Oh well, at least they fixed it.
- CJefferson 3y agoGcc's std::sort has always had this "bug" for bad comparators, doing "x <= y" instead of "x < y" is enough to cause out of bounds read and writes. This isn't fixed because it's undefined behaviour.
- alphazard 3y agoTheir assessment seems fair to me. There are lots of reasons that software can be bad. "Easy to misuse" is one of them. Not the same thing as a vulnerability. I'm sure there are some Rust devs who would say the same thing about C. It's possible to write secure code in C, just as it's possible to write a sort with defined behavior using glibc.
- sgift 3y agoThe reason I'd say assigning a CVE is the right call is that the "easy to misuse" leads to a potential security problem here because of the way glibc handles the function that you give it. Case in point: You can make the same error in Java (I think it's even included in the docs for Comparators that you shouldn't do a-b, because of integer overflow/underflow), but it cannot lead to an out-of-bounds read/write. And that's because Java (~glibc) handles the comparison function that you give it differently.
- hedora 3y ago
- madars 3y agoAnother place where non-transitive comparison frequently results in correctness errors/crashes is balanced tree-based STL containers like std::set or std::map. It's interesting to know whether those are similarly exploitable.
- CJefferson 3y agoThey definitely are, similarly bad comparators in std::sort.
- deleted 3y ago[deleted]
- kevincox 3y agoThere was a recent CppCon talk about changing the sort implementation in LLVM's libc++. They talked about this is as one of the issues as well. https://www.youtube.com/watch?v=cMRyQkrjEeI https://www.youtube.com/watch?v=cMRyQkrjEeI
- orlp 3y agoI also mentioned it explicitly as a source of CVE's two years ago in a talk I gave on pdqsort: https://youtu.be/jz-PBiWwNjc?t=856 https://youtu.be/jz-PBiWwNjc?t=856
- kramerger 3y agoBut is this really exploitable? And i had always thought networked services avoid using plain qsort due to risk of dos
- jacquesm 3y agoThat's the big question, it may well be. But I don't immediately see how though there are probably enough applications out there using quicksort that some of them may end up being exploitable. But it would take an interesting set of circumstances to bring that about.
- dang 3y agoRecent and related: New Linux glibc flaw lets attackers get root on major distros - https://news.ycombinator.com/item?id=39250076 https://news.ycombinator.com/item?id=39250076 - Feb 2024 (93 comments) Out-of-bounds read and write in glibc's qsort() - https://news.ycombinator.com/item?id=39206029 https://news.ycombinator.com/item?id=39206029 - Jan 2024 (1 comment) CVE-2023-6246: Heap-based buffer overflow in the glibc's syslog() - https://news.ycombinator.com/item?id=39194093 https://news.ycombinator.com/item?id=39194093 - Jan 2024 (18 comments) Safety vs. Performance. A case study of C, C++ and Rust sort implementations - https://news.ycombinator.com/item?id=37781612 https://news.ycombinator.com/item?id=37781612 - Oct 2023 (130 comments)
- LukeShu 3y agoThis is unrelated to CVE-2023-6246 (which 2 of your links are about), other than that it piggy-backed on the embargo date.
- dang 3y agoThanks! I guess they're related at the glibc level and not at the CVE level.
- nuc1e0n 3y agoNot entirely. It appears glibc as a whole is being security audited at present and these CVEs are visible symptoms of the process. Have the auditors tried looking at musl libc? It seems a lot less convoluted from what I've seen so may be an easier thing to validate.
- Voultapher 3y agoI would argue, https://news.ycombinator.com/item?id=37781612 https://news.ycombinator.com/item?id=37781612 is also related. It explains that issue in detail and measures it in C++ standard library implementations.
- dang 3y agoOk, thanks! Added above.
- skitter 3y agoThey already mention the issue of using substraction for comparison; here's another different accidentally intransitive comparison function: int cmp(const float *a, const float *b) { if (*a < *b) { return 1; } else if (*a == *b) { return 0; } else { return -1; } }
- jstimpfle 3y agoIs it intransitive? Can you give a, b, c s.t. a < b and b < c, but not a < c?
- rrauenza 3y agoMaybe inf or nan? https://stackoverflow.com/a/42723797/2077386 https://stackoverflow.com/a/42723797/2077386
- scythe 3y agoTrivially, NaN != NaN, so this function is not even properly reflexive (i.e. for a = b = NaN we find cmp(&a,&b) = cmp(&b,&a) = 1).
- jstimpfle 3y agoI mean, yeah. It's not like there is a lot of meaning to NaN. For most applications, trying to sort NaNs is probably a bug in itself. So I think this is likely a perfectly valid comparison function. To make a point, here is a sorting function I'm using. static int cmp_seqnos(const void *a, const void *b) { uint64_t x = (const uint64_t *) a; uint64_t y = (const uint64_t *) b; if (y - x < ((uint64_t) 1 << 63)) return -1; return x != y; } I think this should work if there are uint64_t a, b: b - a < ((uint64_t) 1 << 63) and all values x from the set to be sorted are in the range a..b. Note that a < b isn't a requirement here. Sorting such numbers can be useful when dealing with sliding windows.
- ufo 3y agoMaybe theyre talking about NaN?Comparing against NaN return false. That doesn't violate transitivity, but it can confuse many sorting algorithms.
- Scubabear68 3y agoA bit of a non-event to me, this is a bug in user code. I don’t see it much differently then freeing a block twice or using an uninitialized pointer. It’s the price of using C.
- NotYourLawyer 3y agoIt’s a footgun for sure though, since the “obvious” comparison function of subtracting arguments is intransitive with integer overflow.
- superjan 3y agoBear in mind that comparing floating point NaNs is not transitive. IIRC, Rust considers floating point unsortable for that reason.
- crotchfire 3y agoNote that this can only be exploited if the program is already using a nontransitive comparision function, which is an egregious bug, and the program is setuid root. The odds of a setuid root program having this particular, exotic flaw are miniscule. None have been found in the wild.
- PoignardAzur 3y ago> Note that this can only be exploited if the program is already using a nontransitive comparision function, which is an egregious bug The example they give is "a function cmp(int a, int b) that returns (a - b)", which is definitely a comparison function I've seen before. It's wrong because of overflow, but it's not egregiously wrong. I think it's more significant than you're implying. I wouldn't be surprised if it were used as a step in an exploit chain somewhere in the wild.
- crotchfire 3y agowhich is definitely a comparison function I've seen before. In which setuid-root program?
- ComputerGuru 3y ago<removed incorrect comparison with std::sort()>
- ack_complete 3y agoThe situation is not any different for std::sort, which also requires that the supplied comparison operator be well-behaved and can also fail in the same way otherwise. https://gcc.gnu.org/bugzilla/show_bug.cgi?id=41448 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=41448
- ComputerGuru 3y agoNever mind, you're right of course. I blanked for a moment there and completely forgot that you just need to use `std::stable_sort()` for non-deterministic comparison routines.
- microtherion 3y agoIn fact if an implementation of std::sort has this bug, it's worse, because a fix in a template function requires recompiling all clients to go into effect, while qsort can be fixed in one shared library.
- mac3n 3y agoDoes that mean all programs which use qsort have "Undefined Behavior"™? Just those which use nontransitive comparison functions? Only those which encounter non-transitivity?
- o11c 3y agoPrograms that use subtraction to implement comparisons have two different kinds of UB - the integer overflow, and the invalid argument (nontransitive function) to qsort. It's possible to implement a nontransitive function without the first UB though. Note however that the UB only actually happens if the dynamically-passed values are more than INT_MAX apart. So e.g. if the values are never negative in practice, or limited to a small maximum, there is no UB.
- cmovq 3y agoI recently fixed some code that was doing the incorrect comparison with this alternative which avoids the overflow and is also branchless [1]: return (a > b) - (a < b); [1]: https://godbolt.org/z/EnqsTr1jo https://godbolt.org/z/EnqsTr1jo
- kmoser 3y agoThat's clever, but I am not a fan: Booleans are implementation dependent; making the assumption that Boolean 'true' evaluates to 1, or even a number greater than what Boolean 'false' evaluates to, is not a good idea, even if it happens to be correct most of the time. Even if it is defined that way in the language specs, it might not be defined that way in a future version of that language or certainly not necessarily in other, simlar languages. Now, if you're exploiting that quirk for performance purposes, that's another story. But then the code should be labeled as such.
- deleted 3y ago[deleted]
- AgentME 3y agoThe comparison operators are specifically defined in the C standard to output 1 if true and 0 if false.
- viraptor 3y agoI was curious about the details. 6.5.8 in https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1548.pdf https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1548.pdf Also 7.18 makes the bool macros explicitly 1 and 0.
- moonchild 3y agoHrm—that's another case of missing isel from gcc/clang (c.f. <https://pp.ipd.kit.edu/firm/selgen https://pp.ipd.kit.edu/firm/selgen>)—my implementation (<https://github.com/moon-chilled/fancy-memcmp/blob/master/memcmp-sse2.S#L82-L86 https://github.com/moon-chilled/fancy-memcmp/blob/master/mem...>) does it in one less instruction. (An alternative is to skip the xors and do cmp/setcc/setcc/sub/movsx, which matches my approach on instruction count, but relies on good handling of partial renames, which is uarch-dependent. And I can never remember if anybody can eliminate movsx. Otoh it is non-destructive.)
- nuc1e0n 3y agoSo glibc's qsort doesn't sort arrays of items when fed nonsense input? No kidding. Of course it won't. But reading off the end of the array is concerning. At a higher level, who's misusing qsort in this way? I'd say PBCAK.
- foota 3y agoThis class of vulnerability was analysed in detail here: https://github.com/Voultapher/sort-research-rs/blob/main/writeup/sort_safety/text.md https://github.com/Voultapher/sort-research-rs/blob/main/wri.... Discussion from the time at https://news.ycombinator.com/item?id=37781612 https://news.ycombinator.com/item?id=37781612
- Voultapher 3y agoIndeed I think there is a valid discussion to be had, in terms of how far can we go with reasonable sacrifices. Also the analysis finds only a correlation between memory safety and expected user base. It doesn't find any correlation between safety and performance, nor does it find one between safe or unsafe internal abstractions and memory safety for users. Personally I believe, that blaming users for "holding it wrong" is not an effective way forwards. As a programming community we've tried that many times, and I've yet to see it succeed at scale.
- nuancebydefault 3y agoI'm confused. You hand over an ill formed comparison function to qsort and it does not behave as expected. What did you expect?
- n_plus_1_acc 3y agoI consider the use of undefined behaviour in trivially detectible cases like this a great mistake. Sure, undefined behaviour is useful for many Compiler optimizations, but requiring qsort implementations to not do out-of-bounds reads does not hurt.
- mjevans 3y agoIMO Optimizations like that should be at least a __warning__ and ideally lead to refactored and more correct code as a result. Also IMO, the default should always be unsigned (modulus) integers, not signed. That would promote more correct consideration of integer types and operations. Yes, the ship has sailed on that, but it would also be nice if code linters added 'signed ' where not specified to remind everyone of the present default.
- jonathrg 3y agoI'm surprised that qsort can malloc.