5 ms·

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

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.

deleted 3y ago
[deleted]
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 ago
  Rust 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 ago
    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.
    - 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 ago
        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) If you wrote this code in WUFFS it won't compile.
        trealira 3y ago
        Interesting, I hadn't heard of WUFFS before now. Thanks for telling me about it.
  - Arnavion 3y ago
    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.
- deleted 3y ago
  [deleted]
int_19h 3y ago
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.
- trealira 3y ago
  Graydon Hoare originally wanted integers to be promoted to bignums on overflow, but that didn't happen. https://graydon2.dreamwidth.org/307291.html https://graydon2.dreamwidth.org/307291.html
  - jacquesm 3y ago
    That's really the only proper solution for this problem.
    - jcranmer 3y ago
      Not necessarily the only proper solution--hard failure, like array out-of-bounds errors, is also often an acceptable solution.
      - jacquesm 3y ago
        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.
      - rsaxvc 3y ago
        MIPS on GCC defaulted to trapping integer overflows, but they had non trapping instructions too.
- avgcorrection 3y ago

deleted 3y ago

[deleted]

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 ago
Rust 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 ago
  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.
  - 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 ago
      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) If you wrote this code in WUFFS it won't compile.
      - trealira 3y ago
        Interesting, I hadn't heard of WUFFS before now. Thanks for telling me about it.
- Arnavion 3y ago
  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.
deleted 3y ago
[deleted]

int_19h 3y ago

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.

trealira 3y ago
Graydon Hoare originally wanted integers to be promoted to bignums on overflow, but that didn't happen. https://graydon2.dreamwidth.org/307291.html https://graydon2.dreamwidth.org/307291.html
- jacquesm 3y ago
  That's really the only proper solution for this problem.
  - jcranmer 3y ago
    Not necessarily the only proper solution--hard failure, like array out-of-bounds errors, is also often an acceptable solution.
    - jacquesm 3y ago
      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.
    - rsaxvc 3y ago
      MIPS on GCC defaulted to trapping integer overflows, but they had non trapping instructions too.
avgcorrection 3y ago