4 ms·
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
by adrian_b 3y ago
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.
- 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.
- trealira 3y ago> 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-into-nso-zero-click.html https://googleprojectzero.blogspot.com/2021/12/a-deep-dive-i...
- tialaramex 3y agoIf 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) If you wrote this code in WUFFS it won't compile.
- trealira 3y agoInteresting, I hadn't heard of WUFFS before now. Thanks for telling me about it.
- Arnavion 3y agoFor 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.
- deleted 3y ago[deleted]