Skip to content

C++: Recognize any non-overflowing arithmetic expression as a barrier for cpp/uncontrolled-arithmetic #6120

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 3 commits into from
Jun 23, 2021
Merged

C++: Recognize any non-overflowing arithmetic expression as a barrier for cpp/uncontrolled-arithmetic #6120

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
3 commits
Select commit Hold shift + click to select a range
18e5d3c
C++: Add false positive with multiplication.
MathiasVP Jun 21, 2021
238c483
C++: Make any non-overflowing arithmetic operation a barrier.
MathiasVP Jun 21, 2021
a611e76
C++: Respond to review comments.
MathiasVP Jun 23, 2021
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
15 changes: 11 additions & 4 deletions cpp/ql/src/Security/CWE/CWE-190/ArithmeticUncontrolled.ql
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -36,7 +36,7 @@ predicate boundedDiv(Expr e, Expr left) { e = left }

/**
* An operand `e` of a remainder expression `rem` (i.e., `rem` is either a `RemExpr` or
* an `AssignRemExpr`) with left-hand side `left` and right-ahnd side `right` is bounded
* an `AssignRemExpr`) with left-hand side `left` and right-hand side `right` is bounded
* when `e` is `left` and `right` is upper bounded by some number that is less than the maximum integer
* allowed by the result type of `rem`.
*/
Expand All @@ -59,10 +59,17 @@ predicate boundedBitwiseAnd(Expr e, Expr andExpr, Expr operand1, Expr operand2)
}

/**
* Holds if `fc` is a part of the left operand of a binary operation that greatly reduces the range
* of possible values.
* Holds if `e` is an arithmetic expression that cannot overflow, or if `e` is an operand of an
* operation that may greatly reduces the range of possible values.
*/
predicate bounded(Expr e) {
(
e instanceof UnaryArithmeticOperation or
e instanceof BinaryArithmeticOperation or
e instanceof AssignArithmeticOperation
) and
not convertedExprMightOverflow(e)
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

If I'm understanding correctly, this can in certain cases fall short of the specification "greatly reduces the range of possible values" - to give an extreme example the following is now a barrier:

x = x + 0; // this can't overflow

However this is pretty silly, in practice we expect the overwhelming majority of arithmetic either can cause an overflow (x = x + 1), or greatly narrows the range of values (x = x / RAND_MAX) ... or is working on an already constrained value (hopefully safely).

If my above understanding is accurate, this is a somewhat heuristic approach, but I think I'm happy with it.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Indeed. This whole predicate uses a bunch of heuristics.

or
// For `%` and `&` we require that `e` is bounded by a value that is strictly smaller than the
// maximum possible value of the result type of the operation.
// For example, the function call `rand()` is considered bounded in the following program:
Expand All @@ -85,7 +92,7 @@ predicate bounded(Expr e) {
boundedBitwiseAnd(e, andExpr, andExpr.getAnOperand(), andExpr.getAnOperand())
)
or
// Optimitically assume that a division always yields a much smaller value.
// Optimitically assume that a division or right shift always yields a much smaller value.
boundedDiv(e, any(DivExpr div).getLeftOperand())
or
boundedDiv(e, any(AssignDivExpr div).getLValue())
Expand Down
14 changes: 12 additions & 2 deletions cpp/ql/test/query-tests/Security/CWE/CWE-190/semmle/uncontrolled/test.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -3,12 +3,12 @@

int rand(void);
void trySlice(int start, int end);
void add_100(int);

#define RAND() rand()
#define RANDN(n) (rand() % n)
#define RAND2() (rand() ^ rand())


#define RAND_MAX 32767



Expand Down Expand Up @@ -99,4 +99,14 @@ void randomTester() {
*ptr_r = RAND();
r -= 100; // BAD
}

{
int r = rand();
r = ((2.0 / (RAND_MAX + 1)) * r - 1.0);
add_100(r);
}
}

void add_100(int r) {
r += 100; // GOOD
}