Monthly Archives: January 2022

Rust: signed vs unsigned arithmetic

A comment here https://stackoverflow.com/questions/12335784/c-integer-overflow postulated, the C-compiler would be able to optimize arithmetic expressions with undefined behavior (such as if (a -10 < 20) ) much better if the variable a being a signed integer (converting internally to an expression similar to a < 30). This is in contrast to the case variable a being an unsigned integer.

And indeed, there is a difference in the output of the C compiler (x86-64 clang 13.0.0), generating less instructions when declaring the variable a as signed integer int

Compared to the output of the C-compiler when declaring as unsigned integer unsigned int

Explaining the code generation of the C compiler

As for the programming language C, the behavior of overflow/underflow is undefined: Garbage In, Garbage Out!

This means the compiler is not constrained by having to worry about what happens when there is overflow/underflow. It only has to emit an executable that exemplifies the behavior for the cases which are defined. For example in case of an overflow of a single signed integer variable, then the behavior of the complete application is said to be undefined!

Analyzing code generation of the Rust compiler

I wondered if there might be any difference in the output of the rust compiler (using -C opt-level=3) either declaring variable a as type i32 or type u32.

Using the Compiler Explorer https://rust.godbolt.org, the conclusion is:
There is no difference! The Rust-Compiler does not transform the expression to something like a < 30 for the case using signed integers !

See the function using Signed Integer i32

See the function using Unsigned Integer u32

As it seems, this is not a lost opportunity for optimization of the signed case, but it is intended behavior, as these two statements are not equal in terms of integer underflow a - 10 < 20 and a < 30, where variable a being a signed integer. And for that reason Rust does not perform any optimization potentially changing the semantics of the expression.

For example, just assume a: i8 = -120 in this case the expression a - 10 would cause an underflow (wrapping) evaluating to value 126. In this case
a - 10 < 20 would yield false, but
a < 30 would yield true!!
So, whereas C is acting on the maxim “I think I know what you mean” and performing ruthless optimization, in contrast Rust is not changing the semantics when generating the binary code.

Now, to find these arithmetic expression with undefined behavior in your code, Rust clippy could be used. After installation of clippy, the following compiler attribute can be added to your lib or application

now calling cargo clippy the faulty location in question will be highlighted and could be corrected.

Conclusion

So, regarding arithmetic expression with undefined behavior, unlike C/C++ the Rust compiler is treating signed operations and unsigned operations the same. Those expressions with undefined behavior are not optimized by the compiler as this optimization might change the semantics of the code! Now, to find these spots in your Rust code, the compiler tool clippy can be used; either refactoring the code to get rid of the undefined behavior (see below), or handling these cases gracefully as shown in my previous post!

For example, using clippy the faulty expression a - 10 < 20 would be detected and could be changed to

PS: As dealing with acceptable and unacceptable input values, if you want to annotate functions and methods with “contracts”, using invariants, pre-conditions and post-conditions, check out the crate contractsDesign By Contract for Rust.

For example, using the crate contracts to define a pre-condition of the form “a >= 10“. Just, these constraints are not evaluated at compile time, but at runtime.

Rust: detect unsigned integer underflow

Recently a critical bug has been discovered in Linux Kernel https://seclists.org/oss-sec/2022/q1/55 , being caused by an unsigned integer underflow. I was wondering how the code in question would have been done safely in Rust, preventing such underflow.

At first, please read about the issue (citing the original post):

On 18 Jan 2022, at 18:21, Will <willsroot () protonmail com> wrote:

There is a heap overflow bug in legacy_parse_param in which the length of data copied can be incremented beyond the 
width of the 1-page slab allocated for it. We currently have created functional LPE exploits against Ubuntu 20.04 and 
container escape exploits against Google's hardened COS. The bug was introduced in 5.1-rc1 
(https://github.com/torvalds/linux/commit/3e1aeb00e6d132efc151dacc062b38269bc9eccc#diff-c4a9ea83de4a42a0d1bcbaf1f03ce35188f38da4987e0e7a52aae7f04de14a05)
 and is present in all Linux releases since. As of January 18th, this patch 
(https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=722d94847de29310e8aa03fcbdb41fc92c521756)
 fixes this issue.

The bug is caused by an integer underflow present in fs/fs_context.c:legacy_parse_param, which results in 
miscalculation of a valid max length. A bounds check is present at fs_context.c:551, returning an error if (len > 
PAGE_SIZE - 2 - size); however, if the value of size is greater than or equal to 4095, the unsigned subtraction will 
underflow to a massive value greater than len, so the check will not trigger. After this, the attacker may freely 
write data out-of-bounds. Changing the check to size + len + 2 > PAGE_SIZE (which the patch did) would fix this.

Exploitation relies on the CAP_SYS_ADMIN capability; however, the permission only needs to be granted in the current 
namespace. An unprivileged user can use unshare(CLONE_NEWNS|CLONE_NEWUSER) to enter a namespace with the 
CAP_SYS_ADMIN permission, and then proceed with exploitation to root the system.

As the Linux kernel has been implemented using the programming language C, these kind of integer underflows may happen undiscovered in the expression (PAGE_SIZE - 2 - size), using unsigned variables with PAGE_SIZE=4096 and if size>=4095.

Now, using the programming language Rust instead, we have got to distinguish different cases.

Behavior in Release Mode

If the application has been compiled with the flag –-release the underflow in the expression (PAGE_SIZE - 2 - size) might have occurred undiscovered as well. This flag causes the compiler to build artifacts in release mode, with optimization and without any checks for overflows or underflows.

For example, having this small Rust code snippet

use std::env;
const PAGE_SIZE: u64 = 4096;
fn main() {
    let args: Vec<String> = env::args().skip(1).collect();
    let size: u64 = args[0].parse().unwrap();
    println!("({} - 2 - {}) => {}", PAGE_SIZE, size, PAGE_SIZE - 2 - size);
}

Here, the underflow of the unsigned 64-bit integer expression (PAGE_SIZE - 2 - size) would not be discovered in release mode, and producing the following output:

$ cargo run --release 4095
Compiling underflow v0.1.0 (test/underflow)
Finished release [optimized] target(s) in 0.28s
Running target/release/underflow 4095
(4096 - 2 - 4095) => 18446744073709551615

Behavior in Debug Mode

Otherwise, if the compiler flag --release is absent, the Rust compiler will produce artifacts in debug mode, including checks for arithmetic underflows and overflows. Now, using unit tests during development, such edge cases would have been discovered, hopefully.

For example, In debug mode an underflow in the expression (PAGE_SIZE - 2 - size) would trigger a panic and the application/test would abort with an error message similar to

thread 'main' panicked at 'attempt to subtract with overflow', src/xxx.rs:9:20

One can detect such arithmetic overflows/underflows in code automatically using rust-chippy! After installation of rust-clippy, just decorate your code as shown below

And now the following call cargo clippy will detect the arithmetic operation with undefined behavior, and clippy yielding the following error

Checked Operations coming to our Rescue

To fix such issues, Rust provides a family of checked operations such as checked_sub() and checked_add() etc. to handle such integer underflows and overflows in a programmatically safe way, for example see the operation checked_sub for the primitive type u64 https://doc.rust-lang.org/std/primitive.u64.html#method.checked_sub

Comment: I expect the feature checked_sub to make use of a carry-flag (or similar flag) of the CPU, being set for each arithmetic operation anyway, so all-in-all checked_sub causing very little overhead per arithmetic operation.

Now, let’s use this operation to see how a safe implementation might look like, handling variable input and potential underflows. Here the variables len and size shall be user defined and PAGE_SIZE shall be equal to 4096 .

For example, getting back to the kernel bug. Let’s port the following bad C code snippet (possibly undefined behavior)

#define PAGE_SIZE 4096u
void foo(unsigned int len, unsigned int size) {
  if (len > PAGE_SIZE - 2 - size) { 
    printf("no capacity left\n") 
  } else {
     printf("sufficient capacity %ul\n", PAGE_SIZE - 2 - size); 
  }
}

the corresponding safe Rust code would look like this, using the operation checked_sub and catching the underflow in the None case branch. Also, please note in the first Some case the additional condition "len > capacity".

const PAGE_SIZE : u64 = 4096;
fn foo(len: u64, size: u64) {
  match (PAGE_SIZE - 2).checked_sub(size) {
      Some(capacity) if len > capacity => {
          println!("no capacity left");
      }
      Some(capacity) => {
          println!("sufficient capacity {}", capacity);
      }
      None => {
          println!("underflow! bad user input!");
      }
  }
}

To be able to estimate the costs for the checked variant, the Rust function has been modified slightly in the code below, getting rid of the print-statements. The screenshot of the Compiler Explorer windows shows the corresponding instructions on the right side (please note the instruction setb checking for the carry-flag CF)

We are able to compare this to the unchecked variant, which may perform arithmetic operations with undefined behavior. The corresponding instructions are shown on the right side of the Compiler Explorer UI. Comparing both, the proportion can be interpreted (naively) as 6 to 9 instructions.

My conclusion is: Arithmetic underflow may occur undiscovered even with Rust (release mode), but rust-clippy provides a mechanism to detect such code segements and Rust provides a standardized API of checked operations to handle these situations with acceptable overhead! So, in any case when dealing with input data, the arithmetic expressions in question should check for underflows or overflows, as demonstrated in the code snipped above using the feature checked_sub() !

PS: for performance reasons, I don’t propose to use checked operations in all expressions, just where affected by inbound data via user input or IO.

Gluon Lang Show

Gluon is a small, statically-typed, functional programming language designed for application embedding into Rust code.

Gluon lang is a native Rust implementation and does not require any FFI interfacing to foreign C libraries, such as for guile.

Gluon lang provides a feature called “implicit arguments” that can be used to realize parametric polymorphism.

Just Gluon lang is a a bit picky regarding recursion and implicit arguments, for example using the Functor Show from module std.show.
The following document is helpful to understand the feature http://marwes.github.io/2018/06/19/gluon-0.8.html

The following is a short example demonstrating its usage.

Let’s have two file,

  • the module maybe.glu exporting both symbols Maybe and show
  • and the application app.glu
// file: maybe.glu

let show @ { ? } = import! std.show
let { (<>) } = import! std.semigroup

// A `Maybe` represents a parameterized type for an optional value
type Maybe a =
  | Just a
  | Nothing

// Stringifying the `Maybe` value
let show ?d : [Show a] -> Show (Maybe a) =
    let show o =
        match o with
        | Just x -> "Just (" <> d.show x <> ")"
        | Nothing -> "Nothing"
    { show }

in
{  Maybe, show }

Now, the application app.glu imports both symbols, using the following expression

let maybe @ { Maybe , ? } = import! maybe

Here, the placeholder ? is important to import in the function shows as scoped symbol maybe.show to avoid ambiguity with symbol show.show.

// file: app.glu
let prelude = import! std.prelude
let  { Show, show } = import! std.show
let io @ { ? } = import! std.io
let string @ { ? } = import! std.string

let maybe @ { Maybe , ? } = import! maybe

let val : maybe.Maybe String = Just "foo"
in
io.println (show val)

Execution in console will be as follows

$ gluon app.glu 
Just ("foo")

Rust Memory Layout Optimization (Enum)

Usage of enum-types is inherent in Rust, usually causing additional overhead due to the enum-discriminator. But, there are a number of optimizations that may eliminate this memory overhead. The following is just a cheatsheet. For further reading see https://rust-lang.github.io/unsafe-code-guidelines/layout/enums.html

Data-Less and Uninhabited fields

Data containers without data payload or containers over types of “zero byte size” the following optimizations exist.

Introduced by MR https://github.com/rust-lang/rust/pull/45225

Size optimizations implemented so far:

  • ignoring uninhabited variants (i.e. containing uninhabited fields), e.g.:
    • Option<!> is 0 bytes
    • Result<T, !> has the same size as T
  • using arbitrary niches, not just 0, to represent a data-less variant, e.g.:
    • Option<bool>, Option<Option<bool>>, Option<Ordering> are all 1 byte
    • Option<char> is 4 bytes
  • using a range of niches to represent multiple data-less variants, e.g.:
    • enum E { A(bool), B, C, D } is 1 byte

An integer that is known not to equal zero.

Wrappers as Option<T> or Result<T> over “NonZero” data types may be optimized by the compiler.

For example Option<usize> may occupy up to 16 bytes, using 8 additional bytes for the discriminator to represent a flag such as 0x00 and 0x01. In contrast using the NonZeroUsize as in Option<NonZeroUsize> the memory consumption may shrink to 8 bytes in total. using the unused bit of NonZeroUsize to represent the discriminator of the generic data type Option<T>

See https://doc.rust-lang.org/std/num/struct.NonZeroUsize.html

This enables some memory layout optimization. For example, Option<NonZeroUsize> is the same size as usize:

use std::mem::size_of;
assert_eq!(size_of::<Option<core::num::NonZeroUsize>>(), size_of::<usize>());

And analogous to it all other NonZero types https://doc.rust-lang.org/std/num/index.html

Please note, using an optimized Option<NonZeroX>, its enum-discriminator will be one of the ‘unused’ bit-combinations in the underlying integer representation, for example the bit combination all zero representing state Option::None.