13 ms·

Its yet another int overflow bug too. Something like a kernel should probably be built with saturating arithmetic rather than the stupid C overflow behavior.

saagarjha 5y ago
Saturating arithmetic is not free from problems, although typically better than two’s complement that some languages have settled on. I’d rather it just panicked, to be honest.
- StillBored 5y ago
  Which on x86, one could trap on overflow. That is one of those legacy options people complain about because they aren't used by C. I'm not sure that is as easy on Arm/etc because IIRC there isn't an integer overflow exception. For whatever reason most newer languages (say rust) don't actually solve this problem either. They could diverge from the normal and do saturating (which arm does have) ints, or throw exceptions on overflow/underflow, but they don't because that would be to hard when they have to manually check overflow on each operation because its not a common feature of many processor arches. edit: although LEA is one of the instructions which avoids flags updates, so even if you wanted to trap it probably wouldn't.
  - Munksgaard 5y ago
    Rust does in fact have a story around overflows: https://doc.rust-lang.org/book/ch03-02-data-types.html#integer-overflow https://doc.rust-lang.org/book/ch03-02-data-types.html#integ...
    - StillBored 5y ago
      But the rust story is basically the same as the C story, which is use something other than the normal operators to do your arithmetic. There are tons of checked_add()_sub/_mul macros or functions floating around. At least in C++ one could override the global operators if needed.
      - fbkr 5y ago
        You cannot overload operators of integral types in C++, if you mean you can overload `int operator+(int, int)` to be saturating. You can create `saturating_int` kind of types easily though.
        pjmlp 5y ago
        Despite its C underpinnings, C++ does provide the tooling for Type Driven Development like ML languages, I think it is a hard sell on the performance driven culture to have little types for those purposes, which is why it isn't used as much as it should.
      - steveklabnik 5y ago
        You can also pass a flag to have all overflows checked, if desired. We do, even on embedded where space is a premium. We’ll take the performance hit.
  - beagle3 5y ago
    Don’t you have to add an INTO (interrupt on overflow) to trigger that? I don’t remember there’s a mode where arithmetic overflows trap automatically. (And if that’s the case, by now INTO will be a slow microcode implementation, with JO _trigger_into probably being much faster)
    - adrian_b 5y ago
      Unfortunately INTO has been deprecated by AMD 20 years ago, with the passing to 64-bit. No Intel/AMD CPU supports INTO in 64-bit mode. It is wise to compile any C/C++ program with options like: "-fsanitize=undefined -fsanitize-undefined-trap-on-error" (as for gcc) or whatever they are called by the used compiler. In that case, the compiler will add instructions with the same effect as INTO, but with more overhead than it was needed in 32-bit Intel/AMD CPUs.
      - gpderetta 5y ago
        are you sure it is more overhead? Sanitize overflow adds a single jo in the critical path. INTO has been microcoded for decades in 32 bits.
        adrian_b 5y ago
        The guaranteed overhead is in size, because JO has either 1 or 5 extra bytes per overflow check, compared to INTO. If you want the exception place to be known precisely, the program counter must be saved separately for each check, which adds a few extra bytes per check (e.g. 5 extra bytes for a CALL instruction, which allows the use of a short JO, so there are 6 extra bytes per check in total). Because there are many checks in a program, the extra program size is non-negligible. The execution time should be about the same for INTO and JO, both for the normal case, when both INTO and JO are ignored and for the error case, when JO is guaranteed to be mispredicted, so its long execution time added to the time needed to fetch and execute the following instructions required to match the effect of an INTO (e.g. saving state and a second not-predicted jump or call that might be needed to reach the actual exception handler) will also be about the same as what would have been needed by an INTO exception, if not longer.
  - throwaway81523 5y ago
    x86 can trap on int overflow? I hadn't heard that before, I should look into it, but is there some special little-known trick? I'm not an x86 wiz obviously, but I thought I had basic familiarity with it.
    - josefx 5y ago
      As far as I can find an integer overflow just sets the overflow flag and you need an explicit INTO instruction to check for the flag and run the trap handler.
    - ncmncm 5y ago
      It was removed from amd64 because it was not actually useful in practice. I.e., sometimes you might want the check, but other times you certainly don't, and turning it off and on at the right times is too hard to get right. And, the ability to turn it on, even when it was never used, slowed everything down. You would anyway need to be able express the choice in the languages used. If you had such a way, a compiler could insert extra instructions to check or to suppress checking where it is not wanted, but making such a choice wherever arithmetic happens would be a big burden to programmers already just barely hanging on.
      - adrian_b 5y ago
        It was not removed because it was not useful. Generating exceptions on overflows is extremely useful. It was removed because it was seldom used by Microsoft and by the other large companies which mattered, so the AMD and Intel designers took advantage of this bad habit of many programmers, in order to simplify their CPU design work. It was seldom used because the programmers have always preferred to obtain the highest speed even with the risk of erroneous computations in seldom cases. The reason is that a lower speed is noticed immediately, possibly leading to a lost sale, while occasional errors may be discovered after a long time and even when they are discovered, the programmers who have made this choice are not punished proportionally with the losses that might have been caused to the users, which in most cases are difficult to quantify anyway. A normal policy is to always check for integer overflow, out-of-bounds accesses and so on. Such checks are provided by all decent compilers. Only when performance problems are identified and if it is certain that there is no danger in omitting the checks, the checks should be omitted in the functions where this matters. Selecting whether run-time checks must be done or not is very easy. You just need to use the appropriate sets of compiler flags for the 2 kinds of functions, those with enabled checks and those with disabled checks. It is sad that the C tradition has imposed that the default compiler flags are with disabled checks, but that is not an acceptable excuse. Any C/C++ programmer should always enable the checks, unless there are good reasons to disable them. If they do not do this, it is completely their fault and not the fault of the programming languages. However the C/C++ standard libraries have the problem that they lack a good standard way of handling such exceptions (i.e. a better way than the UNIX signals). That means that if you do not want to abort the program in case of overflows or out-of-bounds accesses, it can be difficult to ensure a recovery after errors.
  - kevin_thibedeau 5y ago
    This was solved by Ada 40 years ago, with modular types added later to satisfy use cases where silent overflow is wanted.
    - pjmlp 5y ago
      That is the biggest issue with C derived languages, the unsafe parts would be perfectly alright if they weren't the default way of doing things. Of course using straighjacket systems programming languages (as they put it) doesn't match hacker culture, so here we are.
    - ncmncm 5y ago
      And, Ada's solution is the proximate cause of the first Ariane 5 exploding, destroying (IIRC) $1/2 billion in payload, unnecessarily. In the Ariane 5 case, an ill-tuned and anyway unnecessary out-of-bounds check was compiled into the inertial platform firmware, causing a debug traceback to be dumped to the rocket gimbal controls, which interpreted the traceback as instructions to steer sideways. To be clear: without the trap, the payload would have been delivered unharmed. There was nothing useful that could be done about the out-of-bounds value during the actual launch, and they knew that when they built the system. Extra points for dumping debug details down a channel where it corrupted correct data. Europeans I have mentioned this to considered what did happen a sensible outcome.
      - pyjarrett 5y ago
        This was the first attempted flight of Ariane 5, which has ended up becoming one of the most reliable launch vehicles of all time. Also, according to NASA, because of its reliability, the Ariane 5 was used to launch the James Webb Space Telescope. The code reuse in the project was pretty poor engineering, they reused code from a different project which had different flight paths and characteristics, and didn't test it. The modern equivalent would be copying and pasting code from a completely different project, and then just shipping to production without testing it at all, even locally. Note that Ada is being used for the Ariane 6.
        5y ago
  - josefx 5y ago
    > That is one of those legacy options people complain about because they aren't used by C. Have you seen how the C math library does error handling? It silently writes to errno. I can just imagine the runtime using the trap to do just that and continue as if nothing happened.
    - adrian_b 5y ago
      Unfortunately the default is like you say. However all C/C++ compilers have options to detect and report or trap on all common errors, but few people use these compiling options, because of a usually baseless fear that they might reduce the performance more than acceptable. In the cases when the performance is indeed too low for correct execution, the complaints should be directed to the CPU manufacturers who are guilty of this (by neglecting the architectural features needed for handling many kinds of exceptions, which were considered mandatory in older CPUs), instead of improving the performance of the programs by cheating, i.e. by omitting the error checks and by accepting that the programs may have horribly wrong behaviors in seldom cases.
      - ncmncm 5y ago
        There is a long-standing principle in system design: do not check for an error condition that you cannot do anything about. It is the responsibility of whoever is so equipped either to ensure that you cannot encounter such an error, or to have provided a path to deal with the error. In C++ you can throw an exception, and count on anybody who cares to act on it, resolving the conflict.
  - pjmlp 5y ago
    > That is one of those legacy options people complain about because they aren't used by C Another one would be bound, which eventually got dropped. https://www.felixcloutier.com/x86/bound https://www.felixcloutier.com/x86/bound
- Jenz 5y ago
  > not free from problems is a massive understatement…
grnmamba 5y ago
C# has a compiler flag for checked arithmetic, i.e. overflow will throw an exception. You can't use c# for kernel development of course, but the idea has existed for decades (for much longer than c# existed). That flag is not set by default in the new project templates for whatever reason. There's also an escape hatch, the unchecked keyword, for the rare cases where you need to overflow, e.g. when implementing hash tables.
- gpderetta 5y ago
  -fsanitize=signed-integer-overflow produces rather decent code with GCC.
- pjmlp 5y ago
  > You can't use c# for kernel development of course Midori team kind of disagreed with that, and most of System C# features keep landing on regular C# a bit per version, but I digress.
  - viraptor 5y ago
    > Midori team kind of disagreed with that Also Singularity https://en.wikipedia.org/wiki/Singularity_(operating_system) https://en.wikipedia.org/wiki/Singularity_(operating_system) and a few random attempts like SharpOs https://sourceforge.net/projects/sharpos/ https://sourceforge.net/projects/sharpos/ and Cosmos.
    - pjmlp 5y ago
      Singularity actually uses a micro-kernel in C++, with everything else in Sing#. An approach similar to what Meadows has taken with NuttX. I haven't mentioned, because I expected it as a possible reply that Singularity wasn't 100% pure Sing#.
GoblinSlayer 5y ago
It's buffer overflow. Integer overflow doesn't cause anything by itself there.
- StillBored 5y ago
  Read the report closer, its a buffer overflow because the buffer overflow check failed due to: " Effectively this implies that the compiler is free to emit code that operates on `reg` as if it were a 32-bit value. If this is the case (and it is on the kernel I tested), a user can forge an expression register value that will overflow upon multiplication with `NFT_REG32_SIZE` (4) and upon addition with `len`, will be a value smaller than `sizeof_field(struct nft_regs, data)` (0x50). Once this check passes, the least significant byte of `reg` can still contain a value that will index outside of the bounds of the `struct nft_regs regs` that it will later be used with. " Which is the classic way to exploit integer overflow to bypass buffer checks (i've personally written code like this, which thankfully was caught before it got this far).
  - GoblinSlayer 5y ago
    Did you try to contradict? You only confirm that the bug is buffer overflow. Take any language with bound checking, you won't be able to reproduce this bug there by merely overflowing integers.

saagarjha 5y ago

Saturating arithmetic is not free from problems, although typically better than two’s complement that some languages have settled on. I’d rather it just panicked, to be honest.

StillBored 5y ago
Which on x86, one could trap on overflow. That is one of those legacy options people complain about because they aren't used by C. I'm not sure that is as easy on Arm/etc because IIRC there isn't an integer overflow exception. For whatever reason most newer languages (say rust) don't actually solve this problem either. They could diverge from the normal and do saturating (which arm does have) ints, or throw exceptions on overflow/underflow, but they don't because that would be to hard when they have to manually check overflow on each operation because its not a common feature of many processor arches. edit: although LEA is one of the instructions which avoids flags updates, so even if you wanted to trap it probably wouldn't.
- Munksgaard 5y ago
  Rust does in fact have a story around overflows: https://doc.rust-lang.org/book/ch03-02-data-types.html#integer-overflow https://doc.rust-lang.org/book/ch03-02-data-types.html#integ...
  - StillBored 5y ago
    But the rust story is basically the same as the C story, which is use something other than the normal operators to do your arithmetic. There are tons of checked_add()_sub/_mul macros or functions floating around. At least in C++ one could override the global operators if needed.
    - fbkr 5y ago
      You cannot overload operators of integral types in C++, if you mean you can overload `int operator+(int, int)` to be saturating. You can create `saturating_int` kind of types easily though.
      - pjmlp 5y ago
        Despite its C underpinnings, C++ does provide the tooling for Type Driven Development like ML languages, I think it is a hard sell on the performance driven culture to have little types for those purposes, which is why it isn't used as much as it should.
    - steveklabnik 5y ago
      You can also pass a flag to have all overflows checked, if desired. We do, even on embedded where space is a premium. We’ll take the performance hit.
- beagle3 5y ago
  Don’t you have to add an INTO (interrupt on overflow) to trigger that? I don’t remember there’s a mode where arithmetic overflows trap automatically. (And if that’s the case, by now INTO will be a slow microcode implementation, with JO _trigger_into probably being much faster)
  - adrian_b 5y ago
    Unfortunately INTO has been deprecated by AMD 20 years ago, with the passing to 64-bit. No Intel/AMD CPU supports INTO in 64-bit mode. It is wise to compile any C/C++ program with options like: "-fsanitize=undefined -fsanitize-undefined-trap-on-error" (as for gcc) or whatever they are called by the used compiler. In that case, the compiler will add instructions with the same effect as INTO, but with more overhead than it was needed in 32-bit Intel/AMD CPUs.
    - gpderetta 5y ago
      are you sure it is more overhead? Sanitize overflow adds a single jo in the critical path. INTO has been microcoded for decades in 32 bits.
      - adrian_b 5y ago
        The guaranteed overhead is in size, because JO has either 1 or 5 extra bytes per overflow check, compared to INTO. If you want the exception place to be known precisely, the program counter must be saved separately for each check, which adds a few extra bytes per check (e.g. 5 extra bytes for a CALL instruction, which allows the use of a short JO, so there are 6 extra bytes per check in total). Because there are many checks in a program, the extra program size is non-negligible. The execution time should be about the same for INTO and JO, both for the normal case, when both INTO and JO are ignored and for the error case, when JO is guaranteed to be mispredicted, so its long execution time added to the time needed to fetch and execute the following instructions required to match the effect of an INTO (e.g. saving state and a second not-predicted jump or call that might be needed to reach the actual exception handler) will also be about the same as what would have been needed by an INTO exception, if not longer.
- throwaway81523 5y ago
  x86 can trap on int overflow? I hadn't heard that before, I should look into it, but is there some special little-known trick? I'm not an x86 wiz obviously, but I thought I had basic familiarity with it.
  - josefx 5y ago
    As far as I can find an integer overflow just sets the overflow flag and you need an explicit INTO instruction to check for the flag and run the trap handler.
  - ncmncm 5y ago
    It was removed from amd64 because it was not actually useful in practice. I.e., sometimes you might want the check, but other times you certainly don't, and turning it off and on at the right times is too hard to get right. And, the ability to turn it on, even when it was never used, slowed everything down. You would anyway need to be able express the choice in the languages used. If you had such a way, a compiler could insert extra instructions to check or to suppress checking where it is not wanted, but making such a choice wherever arithmetic happens would be a big burden to programmers already just barely hanging on.
    - adrian_b 5y ago
      It was not removed because it was not useful. Generating exceptions on overflows is extremely useful. It was removed because it was seldom used by Microsoft and by the other large companies which mattered, so the AMD and Intel designers took advantage of this bad habit of many programmers, in order to simplify their CPU design work. It was seldom used because the programmers have always preferred to obtain the highest speed even with the risk of erroneous computations in seldom cases. The reason is that a lower speed is noticed immediately, possibly leading to a lost sale, while occasional errors may be discovered after a long time and even when they are discovered, the programmers who have made this choice are not punished proportionally with the losses that might have been caused to the users, which in most cases are difficult to quantify anyway. A normal policy is to always check for integer overflow, out-of-bounds accesses and so on. Such checks are provided by all decent compilers. Only when performance problems are identified and if it is certain that there is no danger in omitting the checks, the checks should be omitted in the functions where this matters. Selecting whether run-time checks must be done or not is very easy. You just need to use the appropriate sets of compiler flags for the 2 kinds of functions, those with enabled checks and those with disabled checks. It is sad that the C tradition has imposed that the default compiler flags are with disabled checks, but that is not an acceptable excuse. Any C/C++ programmer should always enable the checks, unless there are good reasons to disable them. If they do not do this, it is completely their fault and not the fault of the programming languages. However the C/C++ standard libraries have the problem that they lack a good standard way of handling such exceptions (i.e. a better way than the UNIX signals). That means that if you do not want to abort the program in case of overflows or out-of-bounds accesses, it can be difficult to ensure a recovery after errors.
- kevin_thibedeau 5y ago
  This was solved by Ada 40 years ago, with modular types added later to satisfy use cases where silent overflow is wanted.
  - pjmlp 5y ago
    That is the biggest issue with C derived languages, the unsafe parts would be perfectly alright if they weren't the default way of doing things. Of course using straighjacket systems programming languages (as they put it) doesn't match hacker culture, so here we are.
  - ncmncm 5y ago
    And, Ada's solution is the proximate cause of the first Ariane 5 exploding, destroying (IIRC) $1/2 billion in payload, unnecessarily. In the Ariane 5 case, an ill-tuned and anyway unnecessary out-of-bounds check was compiled into the inertial platform firmware, causing a debug traceback to be dumped to the rocket gimbal controls, which interpreted the traceback as instructions to steer sideways. To be clear: without the trap, the payload would have been delivered unharmed. There was nothing useful that could be done about the out-of-bounds value during the actual launch, and they knew that when they built the system. Extra points for dumping debug details down a channel where it corrupted correct data. Europeans I have mentioned this to considered what did happen a sensible outcome.
    - pyjarrett 5y ago
      This was the first attempted flight of Ariane 5, which has ended up becoming one of the most reliable launch vehicles of all time. Also, according to NASA, because of its reliability, the Ariane 5 was used to launch the James Webb Space Telescope. The code reuse in the project was pretty poor engineering, they reused code from a different project which had different flight paths and characteristics, and didn't test it. The modern equivalent would be copying and pasting code from a completely different project, and then just shipping to production without testing it at all, even locally. Note that Ada is being used for the Ariane 6.
      - 5y ago
- josefx 5y ago
  > That is one of those legacy options people complain about because they aren't used by C. Have you seen how the C math library does error handling? It silently writes to errno. I can just imagine the runtime using the trap to do just that and continue as if nothing happened.
  - adrian_b 5y ago
    Unfortunately the default is like you say. However all C/C++ compilers have options to detect and report or trap on all common errors, but few people use these compiling options, because of a usually baseless fear that they might reduce the performance more than acceptable. In the cases when the performance is indeed too low for correct execution, the complaints should be directed to the CPU manufacturers who are guilty of this (by neglecting the architectural features needed for handling many kinds of exceptions, which were considered mandatory in older CPUs), instead of improving the performance of the programs by cheating, i.e. by omitting the error checks and by accepting that the programs may have horribly wrong behaviors in seldom cases.
    - ncmncm 5y ago
      There is a long-standing principle in system design: do not check for an error condition that you cannot do anything about. It is the responsibility of whoever is so equipped either to ensure that you cannot encounter such an error, or to have provided a path to deal with the error. In C++ you can throw an exception, and count on anybody who cares to act on it, resolving the conflict.
- pjmlp 5y ago
  > That is one of those legacy options people complain about because they aren't used by C Another one would be bound, which eventually got dropped. https://www.felixcloutier.com/x86/bound https://www.felixcloutier.com/x86/bound
Jenz 5y ago
> not free from problems is a massive understatement…

grnmamba 5y ago

C# has a compiler flag for checked arithmetic, i.e. overflow will throw an exception. You can't use c# for kernel development of course, but the idea has existed for decades (for much longer than c# existed). That flag is not set by default in the new project templates for whatever reason. There's also an escape hatch, the unchecked keyword, for the rare cases where you need to overflow, e.g. when implementing hash tables.

gpderetta 5y ago
-fsanitize=signed-integer-overflow produces rather decent code with GCC.
pjmlp 5y ago
> You can't use c# for kernel development of course Midori team kind of disagreed with that, and most of System C# features keep landing on regular C# a bit per version, but I digress.
- viraptor 5y ago
  > Midori team kind of disagreed with that Also Singularity https://en.wikipedia.org/wiki/Singularity_(operating_system) https://en.wikipedia.org/wiki/Singularity_(operating_system) and a few random attempts like SharpOs https://sourceforge.net/projects/sharpos/ https://sourceforge.net/projects/sharpos/ and Cosmos.
  - pjmlp 5y ago
    Singularity actually uses a micro-kernel in C++, with everything else in Sing#. An approach similar to what Meadows has taken with NuttX. I haven't mentioned, because I expected it as a possible reply that Singularity wasn't 100% pure Sing#.

GoblinSlayer 5y ago

It's buffer overflow. Integer overflow doesn't cause anything by itself there.

StillBored 5y ago
Read the report closer, its a buffer overflow because the buffer overflow check failed due to: " Effectively this implies that the compiler is free to emit code that operates on `reg` as if it were a 32-bit value. If this is the case (and it is on the kernel I tested), a user can forge an expression register value that will overflow upon multiplication with `NFT_REG32_SIZE` (4) and upon addition with `len`, will be a value smaller than `sizeof_field(struct nft_regs, data)` (0x50). Once this check passes, the least significant byte of `reg` can still contain a value that will index outside of the bounds of the `struct nft_regs regs` that it will later be used with. " Which is the classic way to exploit integer overflow to bypass buffer checks (i've personally written code like this, which thankfully was caught before it got this far).
- GoblinSlayer 5y ago
  Did you try to contradict? You only confirm that the bug is buffer overflow. Take any language with bound checking, you won't be able to reproduce this bug there by merely overflowing integers.