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.
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.
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.
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.
And sure, overflow checks aren't free - but this is something that has been optimized in CPUs for decades.
I don't even think Rust can do something like
type Element is Integer range 100 .. 1000;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)
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
(deftype element () `(integer 100 1000))
(deftype even-element ()
`(and (integer 100 1000)
(satisfies evenp)))
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.
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)