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. The following diagram illustrates the left-shift operation.
According to the C Standard, if E1
has an unsigned type, the value of the result is E1
* 2
^{E2}
, reduced modulo 1 more than the maximum value representable in the result type.
This noncompliant code example fails to ensure that the right operand is less than the precision of the promoted left operand:
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:
#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
macro and PRECISION()
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
* 2
^{E2}
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
/ 2
^{E2}
. If E1
has a signed type and a negative value, the resulting value is implementation-defined and can be either an arithmetic (signed) shift
or a logical (unsigned) shift
This noncompliant code example fails to test whether the right operand is greater than or equal to the precision of the promoted left operand, allowing undefined behavior:
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 type.
Rule | Severity | Likelihood | Remediation Cost | Priority | Level |
---|---|---|---|---|---|
INT34-C | Low | Unlikely | Medium | P2 | L3 |
Automated Detection
Tool | Version | Checker | Description |
---|---|---|---|
Astrée | 19.04 | precision-shift-width | Fully checked |
Axivion Bauhaus Suite | 6.9.0 | CertC-INT34 | Can detect shifts by a negative or an excessive number of bits and right shifts on negative values. |
CodeSonar | 5.1p0 | LANG.ARITH.BIGSHIFT | Shift amount exceeds bit width |
Compass/ROSE | Can detect violations of this rule. Unsigned operands are detected when checking for INT13-C. Use bitwise operators only on unsigned operands | ||
Coverity | 2017.07 | BAD_SHIFT | Implemented |
Cppcheck | 1.66 | shiftNegative, shiftTooManyBits | Context sensitive analysis |
ECLAIR | 1.2 | CC2.INT34 | Partially implemented |
LDRA tool suite | 9.7.1 | 51 S, 403 S, 479 S | Partially implemented |
Parasoft C/C++test | 10.4.2 | CERT_C-INT34-a | Invalid range of the right hand operand of a shift operator |
Polyspace Bug Finder | R2018a | Shift operator on negative value Overflow from shifting operation | |
PRQA QA-C | 9.5 | 0499, 2790 [C], 2791 [D], | Partially implemented |
PRQA QA-C++ | 4.3 | 2791, 2792, 2793, 3003, 3321, 3322 | |
PVS-Studio | 6.23 | V610 | |
RuleChecker | 19.04 | precision-shift-width-constant | Partially checked |
TrustInSoft Analyzer | 1.38 | shift | Exhaustively verified (see one compliant and one non-compliant example). |
Related Vulnerabilities
Search for vulnerabilities resulting from the violation of this rule on the CERT website.
Related Guidelines
Key here (explains table format and definitions)
Taxonomy | Taxonomy item | Relationship |
---|---|---|
CERT C | INT13-C. Use bitwise operators only on unsigned operands | Prior to 2018-01-12: CERT: Unspecified Relationship |
CERT C | INT35-C. Use correct integer precisions | Prior to 2018-01-12: CERT: Unspecified Relationship |
CERT C | INT32-C. Ensure that operations on signed integers do not result in overflow | Prior to 2018-01-12: CERT: Unspecified Relationship |
ISO/IEC TR 24772:2013 | Arithmetic Wrap-Around Error [FIF] | Prior to 2018-01-12: CERT: Unspecified Relationship |
CWE 2.11 | CWE-682 | 2017-07-07: CERT: Rule subset of CWE |
CWE 2.11 | CWE-758 | 2017-07-07: CERT: Rule subset of CWE |
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
[C99 Rationale 2003] | 6.5.7, "Bitwise Shift Operators" |
[Dowd 2006] | Chapter 6, "C Language Issues" |
[Seacord 2013b] | Chapter 5, "Integer Security" |
[Viega 2005] | Section 5.2.7, "Integer Overflow" |
21 Comments
Alex Volkovitsky
What's up with the test program in the references?
Kirk Sayre
In the code for the compliant solution (left shift, unsigned type) it appears that mod2 and mod1 are never assigned a value. Is there something in the solution that sets mod1 and mod2 that I am missing?
Robert Seacord
Yeah, that's true. Also, this code snippets are non-compliant with DCL04-C. Do not declare more than one variable per declaration
Also, the last compliant solution didn't even compile because the variables had different names (
result
vsuresult
.I've fixed up some of these examples. I'll finish the rest later, unless someone beats me to it.
Robert Seacord
I'm also confused as to why the Non-Compliant Code Example (Right Shift) has signed and unsigned examples, but the compliant solution only uses unsigned.
I think we have a recommendation somewhere that INT13-C. Use bitwise operators only on unsigned operands. This should probably be referenced above.
It may still be OK to show compliant solutions for signed types, so that if someone tries to do this we have an example of how to do it. However, they should reference INT13-C. Use bitwise operators only on unsigned operands to indicate that this practice is not recommended.
Robert Seacord
This problem still (urgently) needs to be addressed.
Alex Volkovitsky
I think I addressed this problem by removing the signed types from the non-compliant solution. I also think we should not introduce a compliant solution that would violate one of our own recommendations.
David Svoboda
In the first NCCE, the diagram shows a '1' in the leftmost box, which disappears when the byte is shifted. Doesn't this represent an int that is 'too large' to be shifted properly? (either it's unsigned and > UINT_MAX/2 or it's signed & <0.
Robert Seacord
Yes that is true, but perhaps OK in this context. The example is only meant to show how this works, and it is in the NCE section so is actually an example of the problem.
Alex Volkovitsky
uhhh... doesn't this line in the first CCE violate the rule?
Note how UINT_MAX is being shifted by more bits than exist in the operand...
Alex Volkovitsky
robert sez:
Alex Volkovitsky
In that case I guess this is a false positive that we can't really avoid without dynamic analysis
David Svoboda
Why? By the logic of his if statement, if the 2nd part of the if expression executes then {{ui2} < sizeof(CHAR_BIT). And since we know it is unsigned, we can therefore validate the shift operation at compile time (or with ROSE).
Alex Volkovitsky
And how do you propose we match the condition
ui2 < sizeof(CHAR_BIT)
using ROSE? Especially knowing that there are at least 100 different ways to structure that conditional statement?David Svoboda
Right, there are 100 different ways to structure the cond. For now just worry about the two that are demonstrated by the code examples here.
Laurent Alebarde
Sorry to come on such an old article.
First of all : thank you very much because I was becoming creasy.
Secondly : using a negative parameter should not be a bug. In terms of algorithmic, it is usefull. At least for me and my algorithm. To escape from undefined, I have to write two lines instead of one with an if.
I understand that in assembly language, the result is undefined. But in my opinion, C++ standard should accept it and manage it because writting code with a parameter that can be negative is natural, while shaking one's mind to anticipate what the processor will do is not. Or suppress simply every languages except assembly ! natural here means that I do expect it to work and I don't ask myself the question.
Moreover, the compiler does not issue any warning, even with all the warnings enabled. That's another argument to make it work.
One may argue against me that if the compiler adds a test in the assembly translation of << or >>, it will be less efficient. My answer is C and C++ are (also) high level languages and the first priority is robustness. And one can include assembly code easily. Or we may have variants : >>> and <<<.
David Svoboda
Shifting by a negative number is explicitly mentioned as undefined behavior by the C and C++ standards. This gives different platform vendors the latitude to have the system do whatever they want (usually whatever is fastest) when they encounter it. I believe i86 ignores all but the least significant 5 bits of the right operand to a shift operation, so if you know your code only runs on those platforms you could rely on that behavior. But we don't recommend it, as your code is inherently non-portable.
Given that other vendors most likely do something different when the right operand is negative, I doubt the standards committees are inclined to change this behavior.
The compiler is not officiially required to issue a warning, although some try to. Perhaps your compiler simply cannot determine that shifting by a negative number is occurring. Alas, that means it is your responsibility to make sure your right operand is positive (and not more than the number of bits in your left operand.)
Laurent Alebarde
So the C and C++ standards are bad ! Just my opinion.
David Svoboda
Only if you think that this feature (shifting a negative number of bits) outweighs the portability and speed that platforms gain by leaving this behavior undefined. Clearly the C committee believed otherwise (and still does).
Yozo TODA
about implementation details.
Aaron Ballman
GCC 4.9.0 produces (using AT&T syntax):
So you are correct, two different patterns are needed. I have rectified this now, thank you for pointing it out!
You can play with this yourself using http://gcc.godbolt.org if you don't have a GCC implementation handy.
Yozo TODA
thanks, Aaron.
I fixed the register operands for correct right shifting (-:
and thanks too for the information on gcc.godbolt.org!