Page History

Bitwise shifts include left-shift operations of the form shift-expression << additive-expression and right-shift operations of the form shift-expression >> additive-expression. The standard integer promotions are first performed on the operands, each of which has an integer type. The type of the result is that of the promoted left operand. If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined.

...

(See undefined behavior 51.)

Do not shift an expression by a negative number of bits or by a number greater than or equal to the precision of the promoted left operand. The precision of an integer type is the number of bits it uses to represent values, excluding any sign and padding bits. For unsigned integer types, the width and the precision are the same; whereas for signed integer types, the width is one greater than the precision. This rule uses precision instead of width because, in almost every case, an attempt to shift by a number of bits greater than or equal to the precision of the operand indicates a bug (logic error). A logic error is different from overflow, in which there is simply a representational deficiency.  In general, shifts should be performed only on unsigned operands. (See INT13-C. Use bitwise operators only on unsigned operands.)

Noncompliant Code Example (Left Shift, Unsigned Type)

The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are filled with zeros. If E1 has a signed type and nonnegative value and . The following diagram illustrates the left-shift operation.

Image Added

According to the C Standard, if E1 has an unsigned type, the value of the result is E1 * 2E2 is , reduced modulo 1 more than the maximum value representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.

Image Removed

. 

This noncompliant code example fails to ensure The following code can result in undefined behavior because there is no check to ensure that left and right operands have nonnegative values and that the right operand is greater less than or equal to the width precision of the promoted left operand.:

int si1, si2, sresult;

sresult = si1 << si2;

Compliant Solution (left shift, signed type)

void func(unsigned int ui_a, unsigned int ui_b) {
  unsigned int uresult = ui_a << ui_b;
  /* ... */
}

Compliant Solution (Left Shift, Unsigned Type)

This compliant solution eliminates the possibility of shifting by greater than or equal to the number of bits that exist in the precision of the left operand: Wiki MarkupThis compliant solution eliminates the possibility of undefined behavior resulting from a left shift operation on signed and unsigned integers. Smaller sized integers are promoted according to the integer promotion rules \[[INT02-A. Understand integer conversion rules]\].

int si1, si2, sresult;

if ( (si1 < 0) || (si2 < 0) || (si2 >= sizeof(int)*CHAR_BIT) || si1 > (INT_MAX >> si2) ) {
  /* handle error condition */
}
else {
  sresult = si1 << si2;
}

In C99, the CHAR_BIT macro defines the number of bits for the smallest object that is not a bit-field (byte). A byte, therefore, contains CHAR_BIT bits.

Non-Compliant Code Example (left shift, unsigned type)

The result of {{E1 << E2}} is {{E1}} left-shifted {{E2}} bit positions; vacated bits are filled with zeros. According to C99, if {{E1}} has an unsigned type, the value of the result is {{E1 * 2 ^E2{^}}}, reduced modulo one more than the maximum value representable in the result type.  Although C99 specifies modulo behavior for unsigned integers, unsigned integer overflow frequently results in unexpected values and resultant security vulnerabilities (see \[[INT32-C. Ensure that integer operations do not result in an overflow]\]). Consequently, unsigned overflow is generally non-compliant and {{E1 * 2 ^E2{^}}} must be representable in the result type.  Modulo behavior is allowed if the conditions in the exception section are met.

The following code can result in undefined behavior because there is no check to ensure that the right operand is greater than or equal to the width of the promoted left operand.

unsigned int ui1, ui2, uresult;

uresult = ui1 << ui2;

Compliant Solution (left shift, unsigned type)

This compliant solution eliminates the possibility of undefined behavior resulting from a left shift operation on unsigned integers. Example solutions are provided for the fully compliant case (unsigned overflow is prohibited) and the exceptional case (modulo behavior is allowed).

unsigned int ui1, ui2, uresult;
unsigned int mod1, mod2;  /* modulo behavior is allowed on mod1 and mod2 by exception */

if ( (ui2 >= sizeof(unsigned int)*CHAR_BIT) || (ui1 > (UINT_MAX  >> ui2))) ) {
  /* handle error condition */
}
else {
  uresult = ui1 << ui2;
}

if (mod2 >= sizeof(unsigned int)*CHAR_BIT) {
  /* handle error condition */
}
else {
  uresult = mod1 << mod2; /* modulo behavior is allowed by exception */
}

#include <limits.h>
#include <stddef.h>
#include <inttypes.h>

extern size_t popcount(uintmax_t);
#define PRECISION(x) popcount(x)
 
void func(unsigned int ui_a, unsigned int ui_b) {
  unsigned int uresult = 0;
  if (ui_b >= PRECISION(UINT_MAX)) {
    /* Handle error */
  } else {
    uresult = ui_a << ui_b;
  }
  /* ... */
}

The PRECISION() macro and popcount() function provide the correct precision for any integer type. (See INT35-C. Use correct integer precisions.)

Modulo behavior resulting from left-shifting an unsigned integer type is permitted by exception INT30-EX3 to INT30-C. Ensure that unsigned integer operations do not wrap.

Noncompliant Code Example (Left Shift, Signed Type)

The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are filled with zeros. If E1 has a signed type and nonnegative value, and E1 * 2E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.

This noncompliant code example fails to ensure that left and right operands have nonnegative values and that the right operand is less than the precision of the promoted left operand. This example does check for signed integer overflow in compliance with INT32-C. Ensure that operations on signed integers do not result in overflow.

#include <limits.h>
#include <stddef.h>
#include <inttypes.h>

void func(signed long si_a, signed long si_b) {
  signed long result;
  if (si_a > (LONG_MAX >> si_b)) {
    /* Handle error */
  } else {
    result = si_a << si_b;
  }
  /* ... */
}

Shift operators and other bitwise operators should be used only with unsigned integer operands in accordance with INT13-C. Use bitwise operators only on unsigned operands.

Compliant Solution (Left Shift, Signed Type)

In addition to the check for overflow, this compliant solution ensures that both the left and right operands have nonnegative values and that the right operand is less than the precision of the promoted left operand:

#include <limits.h>
#include <stddef.h>
#include <inttypes.h>
 
extern size_t popcount(uintmax_t);
#define PRECISION(x) popcount(x)
 
void func(signed long si_a, signed long si_b) {
  signed long result;
  if ((si_a < 0) || (si_b < 0) ||
      (si_b >= PRECISION(ULONG_MAX)) ||
      (si_a > (LONG_MAX >> si_b))) {
    /* Handle error */
  } else {
    result = si_a << si_b;
  }
  /* ... */
}

Noncompliant Code Example (Right Shift

...

)

The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1 / 2E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined and may can be either an arithmetic (signed) shift:

or a logical (unsigned) shift:

This non-compliant noncompliant code example fails to test whether the right operand is negative or is greater than or equal to the width precision of the promoted left operand, allowing undefined behavior.:

int si1, si2, sresult;
unsigned int ui1, ui2, uresult;

sresult = si1 >> si2;
uresult = ui1 >> ui2;

Making assumptions about whether a right shift is implemented as an arithmetic (signed) shift or a logical (unsigned) shift can also lead to vulnerabilities (see \[[INT13-A. Do not assume that a right shift operation is implemented as a logical or an arithmetic shift]\]).

Compliant Solution (right shift)

This compliant solution tests the suspect shift operation to guarantee there is no possibility of unsigned overflow.

int si1, si2, sresult;
unsigned int ui1, ui2, result;

if ( (si2 < 0) || (si2 >= sizeof(int)*CHAR_BIT) ) {
  /* handle error condition */
}
else {
  sresult = si1 >> si2;
}

if (ui2 >= sizeof(unsigned int)*CHAR_BIT) {
  /* handle error condition */
}
else {
  uresult = ui1 >> ui2;
}

Exceptions

Unsigned integers can be allowed to exhibit modulo behavior if and only if

1. the variable declaration is clearly commented as supporting modulo behavior
2. each operation on that integer is also clearly commented as supporting modulo behavior

If the integer exhibiting modulo behavior contributes to the value of an integer not marked as exhibiting modulo behavior, the resulting integer must obey this rule.

Risk Assessment

void func(unsigned int ui_a, unsigned int ui_b) {
  unsigned int uresult = ui_a >> ui_b;
  /* ... */
}

When working with signed operands, making assumptions about whether a right shift is implemented as an arithmetic (signed) shift or a logical (unsigned) shift can also lead to vulnerabilities. (See INT13-C. Use bitwise operators only on unsigned operands.)

Compliant Solution (Right Shift)

This compliant solution eliminates the possibility of shifting by greater than or equal to the number of bits that exist in the precision of the left operand:

#include <limits.h>
#include <stddef.h>
#include <inttypes.h>

extern size_t popcount(uintmax_t);
#define PRECISION(x) popcount(x)
 
void func(unsigned int ui_a, unsigned int ui_b) {
  unsigned int uresult = 0;
  if (ui_b >= PRECISION(UINT_MAX)) {
    /* Handle error */
  } else {
    uresult = ui_a >> ui_b;
  }
  /* ... */
}

Implementation Details

GCC has no options to handle shifts by negative amounts or by amounts outside the width of the type predictably or to trap on them; they are always treated as undefined. Processors may reduce the shift amount modulo the width of the type. For example, 32-bit right shifts are implemented using the following instruction on x86-32:

sarl   %cl, %eax

The sarl instruction takes a bit mask of the least significant 5 bits from %cl to produce a value in the range [0, 31] and then shift %eax that many bits:

// 64-bit right shifts on IA-32 platforms become
shrdl  %edx, %eax
sarl   %cl, %edx

where %eax stores the least significant bits in the doubleword to be shifted, and %edx stores the most significant bits.

Risk Assessment

Although shifting a negative number of bits or shifting a number of bits greater than or equal to the width of the promoted left operand is undefined behavior in C, the risk is generally low because processors frequently reduce the shift amount modulo the width of the typeImproper range checking can lead to buffer overflows and the execution of arbitary code by an attacker.

Automated Detection

Related Vulnerabilities

Search for vulnerabilities resulting from the violation of this rule on the CERT website.

References

A test program for this rule is available.

...

Related Guidelines

Key here (explains table format and definitions)

CERT-CWE Mapping Notes

Key here for mapping notes

CWE-758 and INT34-C

Independent( INT34-C, INT36-C, MEM30-C, MSC37-C, FLP32-C, EXP33-C, EXP30-C, ERR34-C, ARR32-C)

CWE-758 = Union( INT34-C, list) where list =

• Undefined behavior that results from anything other than incorrect bit shifting

CWE-682 and INT34-C

Independent( INT34-C, FLP32-C, INT33-C) CWE-682 = Union( INT34-C, list) where list =

• Incorrect calculations that do not involve out-of-range bit shifts

Bibliography

...

...

...

...

Image Added Image Added Image Added overflow" \[[ISO/IEC 03|AA. C References#ISO/IEC 03]\] Section 6.5.7, "Bitwise shift operators"