[Coding Guideline]: Subset Guideline for CERT C, INT34-C: Do not shift an expression by a negative number of bits or by greater than or equal to the number of bits that exist in the operand

[felix91gr]

Chapter

Expressions

Guideline Title

Integer shift shall only be performed through checked_ APIs

Category

Required

Status

Draft

Release Begin

1.7.0

Release End

latest

FLS Paragraph ID

fls_sru4wi5jomoe

Decidability

Decidable

Scope

Module

Tags

numerics, reduce-human-error, maintainability, portability, surprising-behavior, subset

Amplification

In particular, the user should only perform left shifts via the checked_shl function and right shifts via the checked_shr function. Both of these functions exist in core.

This rule applies to the following primitive types:

• i8
• i16
• i32
• i64
• i128
• u8
• u16
• u32
• u64
• u128
• usize
• isize

Exception(s)

If, for a specific instance of a shifting operation, the user can prove that the RHS operand will always be inside the range 0..=N-1, where N is the number of bits of the LHS operand, then this Guideline does not apply to that instance.

Rationale

This is a Subset rule, directly inspired by INT34-C. Do not shift an expression by a negative number of bits or by greater than or equal to the number of bits that exist in the operand.

In Rust these out-of-range shifts don't give rise to Undefined Behavior; however, they are still problematic in Safety Critical contexts for two reasons.

Reason 1: inconsistent behavior

The behavior of shift operations depends on the compilation mode. Say for example, that we have a number x of type uN, and we perform the operation

x << M

Then, it will behave like this:

Compilation Mode	0 <= M < N	M < 0	N <= M
Debug	Shifts normally	Panics	Panics
Release	Shifts normally	Shifts by M mod N	Shifts by M mod N

Note: the behavior is exactly the same for the >> operator.

Panicking in Debug is an issue by itself, however, a perhaps larger issue there is that its behavior is different from that of Release. Such inconsistencies aren't acceptable in Safety Critical scenarios.

Therefore, a consistently-behaved operation should be required for performing shifts.

Reason 2: programmer intent

There is no scenario in which it makes sense to perform a shift of negative length, or of more than N - 1 bits. The operation itself becomes meaningless.

Therefore, an API that restricts the length of the shift to the range [0, N - 1] should be used instead of the << and >> operators.

The Solution

The ideal solution for this exists in core: checked_shl and checked_shr.

<T>::checked_shl(M) returns a value of type Option<T>, in the following way:

• If M < 0, the output is None
• If 0 <= M < N for T of N bits, then the output is Some(T)
• If N <= M, the output is None

This API has consistent behavior across Debug and Release, and makes the programmer intent explicit, which effectively solves this issue.

Non-Compliant Example - Prose

As seen in the example below:

• A Debug build panics,

• Whereas a Release build prints the values:

  61 << -1 = 2147483648
  61 << 4 = 976
  61 << 40 = 15616
  

This shows Reason 1 prominently.

Reason 2 is not seen in the code, because it is a reason of programmer intent: shifts by less than 0 or by more than N - 1 (N being the bit-length of the value being shifted) are both meaningless.

Non-Compliant Example - Code

fn bad_shl(bits: u32, shift: i32) -> u32 {
    bits << shift
}
    
let bits : u32 = 61;
let shifts = vec![-1, 4, 40];
    
for sh in shifts {
    println!("{bits} << {sh} = {}", bad_shl(bits, sh));
}

Compliant Example - Prose

As seen in the example below:

• Both Debug and Release give the same exact output, which addresses Reason 1.
• Shifting by negative values is impossible due to the fact that checked_shl only accepts unsigned integers as shift lengths.
• Shifting by more than N - 1 (N being the bit-length of the value being shifted) returns a None value:

  61 << 4 = Some(976)
  61 << 40 = None
  

The last 2 observations show how this addresses Reason 2.

Compliant Example - Code

fn good_shl(bits: u32, shift: u32) -> Option<u32> {
    bits.checked_shl(shift)
}
    
let bits : u32 = 61;
// let shifts = vec![-1, 4, 40];
//                    ^--- Would not typecheck, as checked_shl
//                         only accepts positive shift amounts
let shifts = vec![4, 40];
    
for sh in shifts {
    println!("{bits} << {sh} = {:?}", good_shl(bits, sh));
}

[felix91gr]

I assumed this text would be directly passed into Sphinx, hence why I didn't write the code blocks with the usual ```rust and ``` delimiters. @PLeVasseur lemme know if I should add them :)

[felix91gr]

This is how they used to look:

fn bad_shl(bits: u32, shift: i32) -> u32 {
    bits << shift
}

let bits : u32 = 61;
let shifts = vec![-1, 4, 40];

for sh in shifts {
    println!("{bits} << {sh} = {}", bad_shl(bits, sh));
}

fn good_shl(bits: u32, shift: u32) -> Option<u32> {
    bits.checked_shl(shift)
}

let bits : u32 = 61;
let shifts = vec![4, 40];

for sh in shifts {
    println!("{bits} << {sh} = {:?}", good_shl(bits, sh));
}

[x0rw]

Hey @felix91gr .
You can use ```rust ``` in you code section, because before it is passed into sphinx, these backticks will be stripped.

The indentation will be taken into account too, to keep the code more organized.

[felix91gr]

@x0rw thank you! Noted, and updated.

[felix91gr]

For book-keeping: this work was started in #6

And, no lint currently exists to enforce this guideline, but as I said at some point:

It should (haha famous last words) be reasonably straight-forward to implement a lint for this; something that's analogous to the existing integer arithmetic lint.

[PLeVasseur]

This looks high quality @felix91gr!

The only feedback I have is more on formatting: for the compliant and non-compliant code examples, I'd suggest removing the outer:

fn non_compliant_example() {
}

fn compliant_example() {
}

If the examples require functions we can have them be named something like that, but in this case the guideline is based on expressions, so I don't think we need the outer functions.

What do you think?

[felix91gr]

This looks high quality @felix91gr!

Yay 🥰

The only feedback I have is more on formatting: for the compliant and non-compliant code examples, I'd suggest removing the outer:

fn non_compliant_example() {
}
fn compliant_example() {
}
If the examples require functions we can have them be named something like that, but in this case the guideline is based on expressions, so I don't think we need the outer functions.

What do you think?

I think that makes a lot of sense. I was copying the form's suggested text: "As seen below in the non_compliant_example() function, (...)", because I worried that perhaps it was an expected (maybe even necessary) part of the answer. Do we have examples of how the form's answers get rendered? :3