That’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.
I 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?
A 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.
You 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.
I've seen a few programs that misbehave due to a comparison function that doesn't have all of the necessary properties.
Maybe what's notable from a security perspective is that here's a contract about the behavior of an algorithm (comparison function) as opposed to the value of an argument (null pointer, negative, bigger than N, etc.).
It'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:
Rust 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.
Code 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.
But: they are holding it wrong and it got fixed regardless because if you can fix such stuff you should. For Rust such a CVE is nearly free given the installed base of Rust and the fact that most of that code is fresh and in maintenance. But that definitely isn't true for all of the instances of glibc that are currently deployed.
Dynamic linking is something that I would personally like to see in Rustland too.
But parent's point is that some issues that count as a CVE for Rust do not count as such for C/C++ because the boundaries of undefined behavior are drawn elsewhere. This means that there are many fixes that are simply never made for C/C++, even though dynamic linking would make such a counterfactual fix easier to deploy.
Parent point was that such CVE could be fixed in Rust super cheaply (free) because code is maintained.
If I have to reinstall the whole system to fix CVE in Rust stdlib in a brave new world where everything is written in Rust, then it's certainly not free fix.
"Memory safe" means that if the user is "holding it wrong", it won't cause a memory error.
In safe Rust, it is impossible to call free with the wrong address (simply by virtue of the `free` equivalent being unsafe, and with the pervasive use of smart pointers to make it practical to stay in safe land).
Similarly even if you "hold it wrong" and use a wrong comparison function in Rust's sort, you might get nonsensical results, but no memory errors.
That's precisely what safety means in this context
In particular, most traits you've seen for Rust, such as PartialEq, or here Ord (a claim that our type is totally ordered) are safe traits, this means you don't need to utter the unsafe keyword to implement these traits, and so even though Rust clearly documents the traits as having specific requirements in fact it promises it won't actually cause UB if you ignore them, and the users of that trait must behave accordingly.
My misfortunate crate https://crates.io/crates/misfortunate is a library of types that just deliberately implement various traits "wrongly" in order that you can play with the consequences.
For example Clone promises to uh, clone things, but Rust can't know if this Doodad is really a "clone" of that Doodad, only that the result was really the correct type, so if your type only implements Default my Multiplicity type wrapper will cheerfully claim it can be cloned anyway, cloning the wrapper doesn't get you a "real" clone but only your Default - the types look correct but what's inside is not a "clone" in any reasonable sense.
Rust does have what it calls unsafe traits, traits which you cannot implement without writing the "unsafe" keyword. They are solemn promises that you did what the documentation told you to, if you messed up in writing the unsafe trait then the resulting software may have Undefined Behaviour.
For example, my type wrapper Comte (named after the guy who invented the trick with a hat you've seen magicians do) claims to be an ExactSizeIterator. If it has one rabbit inside it, duh, exact size. Nope, it's a trick, we can just tap the Comte with our wand and produce an unlimited number of rabbits despite claiming to be an ExactSizeIterator, that's a bad idea but it's not Undefined Behaviour.
On the other hand Rust has the unsafe TrustedLen, which also says we can trust this iterator knows exactly how big it is, but because it's unsafe that's a solemn promise, if we took the Comte code but claimed to implement TrustedLen we're just despicable liars.
I'm surprised that random comparison functions were not mentioned in the article. An awful idea, sure, but oh so tempting. Maybe everyone who tried it quickly saw the crashes...
Mh, my main concern is: Both the weirdest absurd and non-exploitable things as well as the most trivially exploitable thing are just being run through all kinds of news channels as security vulnerabilities and out-of-bound writes and such. Like, "complete bypass of redirect URI validation in keycloak OIDC" vs "memory corruption for qsort in glibc (if the application passes a bad comparision function (and you can trigger it))".
I'm finding myself very fatigued by this about vulnerabilities and find myself just giving up about trying to keep track. Also because there is no good curated source it feels. I can run after 3 nonsense ones a week and the one that can rip my systems apart drops on Christmas eve anyway.
In theory this is what CVSS scores were supposed to fix, but a lot of the "does this vulnerability really matter" evaluation ultimately depends on the details of your environment and application :(
I have also found CVSS scores to over- or underestimate the impact of vulnerabilities so much.. I might as well flip a coin. And while I probably should be informed more, I really consider that a problem in the output of the security community.
For example, the keycloak OIDC vulnerability would've allowed me to compromise any account of our internal authentication with ~1 bad click from a user, possibly fewer. Working that out to a point it was terrifying to all internal users took like 30 minutes at most and most time was wasted on realizing their version constraints for the exploit are wrong. That's a 7.8.
But then you have "Oh curl with high parameters can hang" and "Oh if you reload postgres many times a second it stops working" coming in at 9+. Like sure, a user with elevated privileges on a critical server sending signals to postgres causing a postgres DoS is my biggest issue at that point.
So I either have to evaluate everything for myself, or .. no idea.
What I'd like to see is a different scoring system that measures how much attention I have to pay to something.
Score 1: This is an implementation bug in the library. Update the library and you're done. It doesn't matter that this gives remote root on a machine with no services running, all you have to worry about is to install the patch and it's 100% fixed.
Score 2: This is a vulnerability discovered in multiple implementations. Some of them have fixed it and some of them haven't. Here is the list of known-good implementations, you need to check that the one you're using is on the list and if it isn't then switch to one of the ones that is.
Score 3: This is a flaw which some platforms don't currently provide a means to implement securely for any implementation. You need to pay attention to this if you use those platforms and possibly redesign your applications to do something else there.
Score 4: This is a design flaw in the API. We can't fix it without breaking compatibility so here's a new API and now you definitely have to update your applications to use it and the existing ones will continue to be vulnerable. Compilers should emit a deprecation warning for anything still using the old API.
Score 5: Spectre. We kind of mitigated it some and you need some patches but now you have to review all existing code, probably won't catch it all anyway, people will continue finding new variants for years and we're all totally screwed.
Intresting 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.
They 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.
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.
By 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.
> 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.
For those interested, I found a blog post that covers an iMessage-based zero-click exploit, which was caused by unchecked integer overflow, and a lack of bounds checking done on allocated buffers:
If you wrote this code as Rust, the resulting bounds miss traps and the exploit doesn't work (but the messaging application fails which is pretty annoying)
For this specific case, saturating_sub would work fine. The checked_sub way would need an additional `.unwrap_or(-1)`
Though of course you wouldn't need to do either because the usual way to write a Rust API that takes comparators is for that comparator to return std::cmp::Ordering, not a signed integer.
And if you do make a PartialOrd / Ord impl that isn't transitive, it is guaranteed by the sorting fns in libstd that sorting may be incorrect, but it won't be undefined behavior.
It amazes me that with all the focus on memory safety, most PLs still don't handle integer overflow sensibly by default: you either get guaranteed wraparound (which silently gives wrong values), or straight up undefined behavior as in C and C++. The latter won't change at this point, of course, but why do new designs insist on following their lead? Safety should always be opt-out, not opt-in.
And sure, overflow checks aren't free - but this is something that has been optimized in CPUs for decades.
That highly depends on the execution environment. In Erlang for instance that would be an acceptable solution. But most other environments don't deal nearly as gracefully with runtime errors.
It takes two lines in your Cargo.toml to turn overflows into panics in release mode in rust, if you don't mind the performance hit.
Or more sensibly you can set clippy lints to disallow any operation that may overflow, forcing you to specify the desired behavior (either with the .{wrapping,checking,saturating}_{sub,add,mul,div} functions or the Saturating<Type> etc wrappers)
Similarly, with C#, you can compile with exception-on-overflow for integers. This is all great, but this should really be the default behavior for basic arithmetic operators, even in release builds. For cases where you want overflow (or saturation, or UB) there should really be distinct operators. Maybe something like <+> for wraparound, [+] for saturation etc.
The guaranteed wraparound of "unsigned" types in C and derivatives is not very helpful.
While the "signed" types in C are well defined kinds of integers, which nonetheless have unpredictable behavior on overflow, the "unsigned" types are ambiguous, because they correspond to 4 different primitive types (each of these 4 being available in various sizes, i.e. 1-bit, 8-bit, 16-bit, 32-bit, 64-bit or 128-bit).
By primitive types I mean types for which the modern CPUs implement distinct dedicated hardware instructions. The 4 types are non-negative integers, integer residues (a.k.a. modular numbers), binary polynomials and Galois-field binary polynomials.
The same operation, e.g. multiplication, is implemented with different algorithms for each of these 4 types.
Moreover, while a 64-bit "unsigned" may be interpreted as a 64-bit non-negative integer or a residue modulo 2^64 or a 64-bit binary polynomial or a value in GF(2^64), there are 2 additional interpretations between which there are subtle differences, as a 64-element array of 1-bit non-negative integers or as a 64-element array of residues modulo-2. The failure to be aware of the differences between the operations that can be performed with these 6 types and using a single name for all can easily lead to bugs.
The wraparound is correct for integer residues modulo 2^N, but it is wrong for non-negative integers, which are more frequent in most applications.
Also the implicit conversions of unsigned types are very bad in C and derivatives. They are some times correct for non-negative integers, but they are always wrong for integer residues. While a small-size non-negative integer may be converted without losses to a bigger size, for integer residues the reverse is true, they can be converted correctly only towards smaller sizes.
Therefore, the unsigned types of C are defined wrongly both when interpreted as non-negative integers and when interpreted as integer residues. Most other languages are not better.
While there are many applications where either non-negative integers, integer residues, binary polynomials or Galois-field binary polynomials are needed, so unsigned C types must be used for lack of a better alternative, the use of "unsigned" types requires extra care in comparison with using the signed types (e.g. all implicit conversions must be avoided) and it must be clearly documented what kind of "unsigned" is really meant (preferably by defining dedicated types for the various possible interpretations; in C++ it is possible to also define correct operations with them, replacing the built-in operators with undesirable behavior).
Very interesting thoughts. I have also seen one programming languages, ehich I cannot find anymore, which doesn't differentiate between signed and unsigned integers as types. Instead, there are just various sized integers, and for each operation you must choose between signed and unsigned semantics. Kind of like Javas >>> and unsignedToString.
I am not sure I follow. unsigned types in C are residues and not binary polynoms or Galois fields (also you can of course store them in unsigned integers).
The conversions work, e.g. conversion to a smaller unsigned type are reduced. That some other conversion work does seem convenient to me and not a problem.
One can, of course, define types in C for Galois fields and access them using functions that do the correct operations (and by wrapping it in a struct one can also prevent regular operations to be used on such type). In C++ one can overload the builtin operators, but I am not terrible sure this is even a good idea.
That's correct, Rust does not have this, in principle Pattern Types (a possible future Rust feature) could do this, but you probably wouldn't use them for this purpose.
WUFFS can do this, it calls such types "refined" types - and indeed WUFFS can also do:
assert n_bits < 12 via "a < b: a < c; c <= b"(c: width)
What that's saying is "As the programmer I say on this line n_bits is strictly less than 12, and I claim you can prove that based on knowing the value of width, and here's why"
WUFFS doesn't know how to create such a proof, it's in quotes because WUFFS has a list of proofs a human gave it, baked in, and just accepts any of those proofs, after all a human mathematician assured it these are true. But it can check the rest of your assertion given this proof, and if that fails your software doesn't compile.
WUFFS requires that it can see why everything you're doing is OK, whether that's indexing into an array (if you write dogs[k] where dogs is an array of 16 dogs, WUFFS needs to be certain that k is strictly in the range from zero to fifteen inclusive, or the program won't compile) or arithmetic (if bits is supposed to be an integer between one and thirty two inclusive then we can't very well do bits = k * 2 can we, because k might be zero)
As a result WUFFS gets to be entirely safe. As a side effect (and also with the help of some clever SIMD friendly language design choices) WUFFS gets to go very, very fast. And all for the very affordable price of abandoning generality. The next Doom, Excel, Apache and Linux cannot be written in WUFFS. But the question is why your thumbnail making code, or your file compressor is written in anything else.
I highly doubt there is a single CL compiler out there that'd be able to e.g. optimize (logand 1 (the even-element x)) into the constant 0. Thus declaring types like this -- in Common Lisp at least -- is only really useful for documenting code and run-time validation.
Extant cl compilers are quite primitive. Well known and uncomplicated analyses exist that can cope with this; e.g. in llvm https://godbolt.org/z/nadbG5zGs
I 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.
Their 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.
The 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.
I don't think it's undefined behavior though. Looking at (the working draft of) the C ISO standard, I don't see a requirement that the comparison function must be transitive.
The closes thing there is 7.22.5.2 §4: "If two elements compare as equal, their order in the resulting sorted array is unspecified"
So I'd say blaming users for a bug in glibc isn't fair.
"When the same objects (consisting of size bytes, irrespective of their current positions in the array) are passed more than once to the comparison function, the results shall be consistent with one another. That is, for qsort they shall define a total ordering on the array, and for bsearch the same object shall always compare the same way with the key."
But being footguns is a feature of C/C++, not a defect: they trade safety for performance by design. (Edit: Wrong trade-off in my opinion, just to make it clear.)
If you shop specifically for an unsafe tool, surprise, you get one. Should have picked better.
1) The performance saved is negligible in many cases, for most footguns. Sometimes it's of no benefit, or slower than safe solutions to the same problem.
2) There's no reason to not just have the footgun be opt-in rather than it being the default approach, if performance does matter so much
3) Why is trading safety for performance the right decision in the first place? It's funny to compare the way software engineers talk about software with the way any other kind of engineer talks about their domain, or even how software engineers talk about other domains.
How many threads have been had here over the past month about how unacceptable Boeing's "just turn off the de-icer" is to a hardware problem that could damage the engine, and other dodgy engineering decisions?
You may have misread my comment, I'm on safe languages team.
I'm complaining about the people that start projects in unsafe languages in exchange of a thin performance boost, and then blame the compiler/runtime maintainers for their own code being unsafe in exactly the ways the spec says it can be unsafe to give them such an extra boost.
Personally, I think all remaining C and C++ projects should consider either rewriting in a safer language or adopting additional tools to prove (not just test) the lack of undefined behaviour. Trying to compromise is just giving us memory safety CVEs one after another.
The glibc team could certainly have been a little less guarded, but I'm not sure they were wrong. If CVEs are to be something other than a stamp collection, then they need to facilitate remediation. To do that, CVEs need to identify vulnerabilities specifically and not just in general.
For example, it wouldn't be useful to assign a CVE to the concept of SQLi, but it can be useful to assign CVEs to particular products exhibiting SQLi vulnerabilities. This fault isn't quite as general as that, but the argument for non-CVE-assignment goes along the same lines.
Gcc'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.
The aftermath of issuing a CVE for this bug would have massive consequences all over the industry, fixing the bug and leaving the past - where you probably would have become aware of this by now if it affected you and you probably should have a look at your code regardless to see if the situation can occur - means that on the next scheduled update of glibc everybody will have the fix. If you have a way of getting this to escalate to RCE or some other nastiness, especially if it can be done remotely in some application that is networked and that uses qsort (which should be most of them so if it is that easy then it should be quick to prove).
Note that even something as mundane as the UTF-8 encoding scheme led to an exploit so it may well be possible. But I think classifying this as a security bug rather than just as a bug at this point is premature.
Consider being on the receiving side of a mandatory (for instance: regulated industry) upgrade requirement of all of your systems because a CVE was issued would carry substantial costs even if the risk of those systems being exploited was very small. So the glibc team likely took such costs into account and absent an easy or obvious way to exploit this that seems for the moment to be the right call. But it could change.
Requiring no CVE is obviously a proxy for no vulnerabilities, and it's as close as you can get. I think if you are in an industry that values this, the correct thing to do is check if you use qsort and check your comparision functions. Now. To encourage this, it would be good thing for glibc to issue a CVE.
Another 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.
That'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.
I 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.
A 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.
Note 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.
> 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.
The 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.
Never 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.
In 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.
Does that mean all programs which use qsort have "Undefined Behavior"™?
Just those which use nontransitive comparison functions?
Only those which encounter non-transitivity?
Programs 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.
That'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.
Hrm—that's another case of missing isel from gcc/clang (c.f. <https://pp.ipd.kit.edu/firm/selgen>)—my implementation (<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.)
So 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.
Indeed 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.
I 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.
IMO 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.
128 comments
[ 2.8 ms ] story [ 187 ms ] threadC APIs were not all designed to be safe to call and can commonly crash or introduce a vulnerability.
So what I mean is: how much performance are we giving up with this "fix" for qsort?
Unfortunately, qsort is really slow and sometimes barely usable.
Maybe what's notable from a security perspective is that here's a contract about the behavior of an algorithm (comparison function) as opposed to the value of an argument (null pointer, negative, bigger than N, etc.).
Still qualifies as passing an invalid parameter.
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-browse...
[0] https://www.reddit.com/r/cpp/comments/151cnlc/a_safety_cultu...
Not sure about the Microsoft C++ standard library since the Microsoft Windows system API does not provide the same softlink functionalty.
Can you say the same for Rust?
But parent's point is that some issues that count as a CVE for Rust do not count as such for C/C++ because the boundaries of undefined behavior are drawn elsewhere. This means that there are many fixes that are simply never made for C/C++, even though dynamic linking would make such a counterfactual fix easier to deploy.
If I have to reinstall the whole system to fix CVE in Rust stdlib in a brave new world where everything is written in Rust, then it's certainly not free fix.
"Memory safe" means that if the user is "holding it wrong", it won't cause a memory error.
In safe Rust, it is impossible to call free with the wrong address (simply by virtue of the `free` equivalent being unsafe, and with the pervasive use of smart pointers to make it practical to stay in safe land).
Similarly even if you "hold it wrong" and use a wrong comparison function in Rust's sort, you might get nonsensical results, but no memory errors.
That's precisely what safety means in this context
My misfortunate crate https://crates.io/crates/misfortunate is a library of types that just deliberately implement various traits "wrongly" in order that you can play with the consequences.
For example Clone promises to uh, clone things, but Rust can't know if this Doodad is really a "clone" of that Doodad, only that the result was really the correct type, so if your type only implements Default my Multiplicity type wrapper will cheerfully claim it can be cloned anyway, cloning the wrapper doesn't get you a "real" clone but only your Default - the types look correct but what's inside is not a "clone" in any reasonable sense.
Rust does have what it calls unsafe traits, traits which you cannot implement without writing the "unsafe" keyword. They are solemn promises that you did what the documentation told you to, if you messed up in writing the unsafe trait then the resulting software may have Undefined Behaviour.
For example, my type wrapper Comte (named after the guy who invented the trick with a hat you've seen magicians do) claims to be an ExactSizeIterator. If it has one rabbit inside it, duh, exact size. Nope, it's a trick, we can just tap the Comte with our wand and produce an unlimited number of rabbits despite claiming to be an ExactSizeIterator, that's a bad idea but it's not Undefined Behaviour.
On the other hand Rust has the unsafe TrustedLen, which also says we can trust this iterator knows exactly how big it is, but because it's unsafe that's a solemn promise, if we took the Comte code but claimed to implement TrustedLen we're just despicable liars.
I'm finding myself very fatigued by this about vulnerabilities and find myself just giving up about trying to keep track. Also because there is no good curated source it feels. I can run after 3 nonsense ones a week and the one that can rip my systems apart drops on Christmas eve anyway.
For example, the keycloak OIDC vulnerability would've allowed me to compromise any account of our internal authentication with ~1 bad click from a user, possibly fewer. Working that out to a point it was terrifying to all internal users took like 30 minutes at most and most time was wasted on realizing their version constraints for the exploit are wrong. That's a 7.8.
But then you have "Oh curl with high parameters can hang" and "Oh if you reload postgres many times a second it stops working" coming in at 9+. Like sure, a user with elevated privileges on a critical server sending signals to postgres causing a postgres DoS is my biggest issue at that point.
So I either have to evaluate everything for myself, or .. no idea.
Score 1: This is an implementation bug in the library. Update the library and you're done. It doesn't matter that this gives remote root on a machine with no services running, all you have to worry about is to install the patch and it's 100% fixed.
Score 2: This is a vulnerability discovered in multiple implementations. Some of them have fixed it and some of them haven't. Here is the list of known-good implementations, you need to check that the one you're using is on the list and if it isn't then switch to one of the ones that is.
Score 3: This is a flaw which some platforms don't currently provide a means to implement securely for any implementation. You need to pay attention to this if you use those platforms and possibly redesign your applications to do something else there.
Score 4: This is a design flaw in the API. We can't fix it without breaking compatibility so here's a new API and now you definitely have to update your applications to use it and the existing ones will continue to be vulnerable. Compilers should emit a deprecation warning for anything still using the old API.
Score 5: Spectre. We kind of mitigated it some and you need some patches but now you have to review all existing code, probably won't catch it all anyway, people will continue finding new variants for years and we're all totally screwed.
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.
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.
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.
For those interested, I found a blog post that covers an iMessage-based zero-click exploit, which was caused by unchecked integer overflow, and a lack of bounds checking done on allocated buffers:
https://googleprojectzero.blogspot.com/2021/12/a-deep-dive-i...
If you wrote this code in WUFFS it won't compile.
Though of course you wouldn't need to do either because the usual way to write a Rust API that takes comparators is for that comparator to return std::cmp::Ordering, not a signed integer.
And if you do make a PartialOrd / Ord impl that isn't transitive, it is guaranteed by the sorting fns in libstd that sorting may be incorrect, but it won't be undefined behavior.
And sure, overflow checks aren't free - but this is something that has been optimized in CPUs for decades.
https://graydon2.dreamwidth.org/307291.html
Or more sensibly you can set clippy lints to disallow any operation that may overflow, forcing you to specify the desired behavior (either with the .{wrapping,checking,saturating}_{sub,add,mul,div} functions or the Saturating<Type> etc wrappers)
While the "signed" types in C are well defined kinds of integers, which nonetheless have unpredictable behavior on overflow, the "unsigned" types are ambiguous, because they correspond to 4 different primitive types (each of these 4 being available in various sizes, i.e. 1-bit, 8-bit, 16-bit, 32-bit, 64-bit or 128-bit).
By primitive types I mean types for which the modern CPUs implement distinct dedicated hardware instructions. The 4 types are non-negative integers, integer residues (a.k.a. modular numbers), binary polynomials and Galois-field binary polynomials.
The same operation, e.g. multiplication, is implemented with different algorithms for each of these 4 types.
Moreover, while a 64-bit "unsigned" may be interpreted as a 64-bit non-negative integer or a residue modulo 2^64 or a 64-bit binary polynomial or a value in GF(2^64), there are 2 additional interpretations between which there are subtle differences, as a 64-element array of 1-bit non-negative integers or as a 64-element array of residues modulo-2. The failure to be aware of the differences between the operations that can be performed with these 6 types and using a single name for all can easily lead to bugs.
The wraparound is correct for integer residues modulo 2^N, but it is wrong for non-negative integers, which are more frequent in most applications.
Also the implicit conversions of unsigned types are very bad in C and derivatives. They are some times correct for non-negative integers, but they are always wrong for integer residues. While a small-size non-negative integer may be converted without losses to a bigger size, for integer residues the reverse is true, they can be converted correctly only towards smaller sizes.
Therefore, the unsigned types of C are defined wrongly both when interpreted as non-negative integers and when interpreted as integer residues. Most other languages are not better.
While there are many applications where either non-negative integers, integer residues, binary polynomials or Galois-field binary polynomials are needed, so unsigned C types must be used for lack of a better alternative, the use of "unsigned" types requires extra care in comparison with using the signed types (e.g. all implicit conversions must be avoided) and it must be clearly documented what kind of "unsigned" is really meant (preferably by defining dedicated types for the various possible interpretations; in C++ it is possible to also define correct operations with them, replacing the built-in operators with undesirable behavior).
The conversions work, e.g. conversion to a smaller unsigned type are reduced. That some other conversion work does seem convenient to me and not a problem.
One can, of course, define types in C for Galois fields and access them using functions that do the correct operations (and by wrapping it in a struct one can also prevent regular operations to be used on such type). In C++ one can overload the builtin operators, but I am not terrible sure this is even a good idea.
I don't even think Rust can do something like
WUFFS can do this, it calls such types "refined" types - and indeed WUFFS can also do:
What that's saying is "As the programmer I say on this line n_bits is strictly less than 12, and I claim you can prove that based on knowing the value of width, and here's why"WUFFS doesn't know how to create such a proof, it's in quotes because WUFFS has a list of proofs a human gave it, baked in, and just accepts any of those proofs, after all a human mathematician assured it these are true. But it can check the rest of your assertion given this proof, and if that fails your software doesn't compile.
WUFFS requires that it can see why everything you're doing is OK, whether that's indexing into an array (if you write dogs[k] where dogs is an array of 16 dogs, WUFFS needs to be certain that k is strictly in the range from zero to fifteen inclusive, or the program won't compile) or arithmetic (if bits is supposed to be an integer between one and thirty two inclusive then we can't very well do bits = k * 2 can we, because k might be zero)
As a result WUFFS gets to be entirely safe. As a side effect (and also with the help of some clever SIMD friendly language design choices) WUFFS gets to go very, very fast. And all for the very affordable price of abandoning generality. The next Doom, Excel, Apache and Linux cannot be written in WUFFS. But the question is why your thumbnail making code, or your file compressor is written in anything else.
In Common Lisp, you can write
and in this case, a "smart" compiler like SBCL will be able to infer the bounds of (the element x), but for more complex predicates, like I highly doubt there is a single CL compiler out there that'd be able to e.g. optimize (logand 1 (the even-element x)) into the constant 0. Thus declaring types like this -- in Common Lisp at least -- is only really useful for documenting code and run-time validation.> 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.
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.
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.
For instance, the bad comparator could be used in nested authentication checks:
if check_A { drop privilege to FOO } else if check_B { drop privilege to BAR } else { /* leave root bit set, because "not (A or B)" means root */ }
and it could lead to a privilege escalation in the face of malformed inputs.
I've seen this sort of thing happen in the wild with Java.
The closes thing there is 7.22.5.2 §4: "If two elements compare as equal, their order in the resulting sorted array is unspecified"
So I'd say blaming users for a bug in glibc isn't fair.
"When the same objects (consisting of size bytes, irrespective of their current positions in the array) are passed more than once to the comparison function, the results shall be consistent with one another. That is, for qsort they shall define a total ordering on the array, and for bsearch the same object shall always compare the same way with the key."
No, we blame the person that did not take proper training or exercise sufficient caution when using their tool.
If you shop specifically for an unsafe tool, surprise, you get one. Should have picked better.
2) There's no reason to not just have the footgun be opt-in rather than it being the default approach, if performance does matter so much
3) Why is trading safety for performance the right decision in the first place? It's funny to compare the way software engineers talk about software with the way any other kind of engineer talks about their domain, or even how software engineers talk about other domains.
How many threads have been had here over the past month about how unacceptable Boeing's "just turn off the de-icer" is to a hardware problem that could damage the engine, and other dodgy engineering decisions?
I'm complaining about the people that start projects in unsafe languages in exchange of a thin performance boost, and then blame the compiler/runtime maintainers for their own code being unsafe in exactly the ways the spec says it can be unsafe to give them such an extra boost.
Personally, I think all remaining C and C++ projects should consider either rewriting in a safer language or adopting additional tools to prove (not just test) the lack of undefined behaviour. Trying to compromise is just giving us memory safety CVEs one after another.
For example, it wouldn't be useful to assign a CVE to the concept of SQLi, but it can be useful to assign CVEs to particular products exhibiting SQLi vulnerabilities. This fault isn't quite as general as that, but the argument for non-CVE-assignment goes along the same lines.
The aftermath of issuing a CVE for this bug would have massive consequences all over the industry, fixing the bug and leaving the past - where you probably would have become aware of this by now if it affected you and you probably should have a look at your code regardless to see if the situation can occur - means that on the next scheduled update of glibc everybody will have the fix. If you have a way of getting this to escalate to RCE or some other nastiness, especially if it can be done remotely in some application that is networked and that uses qsort (which should be most of them so if it is that easy then it should be quick to prove).
Note that even something as mundane as the UTF-8 encoding scheme led to an exploit so it may well be possible. But I think classifying this as a security bug rather than just as a bug at this point is premature.
Consider being on the receiving side of a mandatory (for instance: regulated industry) upgrade requirement of all of your systems because a CVE was issued would carry substantial costs even if the risk of those systems being exploited was very small. So the glibc team likely took such costs into account and absent an easy or obvious way to exploit this that seems for the moment to be the right call. But it could change.
https://www.youtube.com/watch?v=cMRyQkrjEeI
And i had always thought networked services avoid using plain qsort due to risk of dos
New Linux glibc flaw lets attackers get root on major distros - 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 - Jan 2024 (1 comment)
CVE-2023-6246: Heap-based buffer overflow in the glibc's syslog() - 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 - Oct 2023 (130 comments)
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.
https://stackoverflow.com/a/42723797/2077386
To make a point, here is a sorting function I'm using.
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.
The odds of a setuid root program having this particular, exotic flaw are miniscule. None have been found in the wild.
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.
In which setuid-root program?
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=41448
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.
Now, if you're exploiting that quirk for performance purposes, that's another story. But then the code should be labeled as such.
Also 7.18 makes the bool macros explicitly 1 and 0.
At a higher level, who's misusing qsort in this way? I'd say PBCAK.
Not only will it not sort them... it will lead to OOB memory accesses by qsort itself
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.
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.