Skip to content

Commit

Permalink
Fix issue 9979: false positive: containerOutOfBounds with conditional…
Browse files Browse the repository at this point in the history 
… resize
  • Loading branch information
@pfultz2
pfultz2 committed Feb 18, 2021
1 parent 7ab84be commit 82810ed
Show file tree
Hide file tree
Showing 5 changed files with 188 additions and 61 deletions.
42 changes: 28 additions & 14 deletions lib/programmemory.cpp
View file
Original file line number Diff line number Diff line change
Expand Up @@ -4,6 +4,7 @@
#include "mathlib.h"
#include "symboldatabase.h"
#include "token.h"
#include "valueflow.h"
#include <algorithm>
#include <cassert>
#include <cstdio>
Expand Down Expand Up @@ -424,20 +425,33 @@ void execute(const Token *expr,

else if (expr->isComparisonOp()) {
MathLib::bigint result1(0), result2(0);
execute(expr->astOperand1(), programMemory, &result1, error);
execute(expr->astOperand2(), programMemory, &result2, error);
if (expr->str() == "<")
*result = result1 < result2;
else if (expr->str() == "<=")
*result = result1 <= result2;
else if (expr->str() == ">")
*result = result1 > result2;
else if (expr->str() == ">=")
*result = result1 >= result2;
else if (expr->str() == "==")
*result = result1 == result2;
else if (expr->str() == "!=")
*result = result1 != result2;
bool error1, error2;
execute(expr->astOperand1(), programMemory, &result1, &error1);
execute(expr->astOperand2(), programMemory, &result2, &error2);
if (error1 && error2) {
*error = true;
} else if (error1 && !error2) {
ValueFlow::Value v = inferCondition(expr->str(), expr->astOperand1(), result2);
*error = !v.isKnown();
*result = v.intvalue;
} else if (!error1 && error2) {
ValueFlow::Value v = inferCondition(expr->str(), result1, expr->astOperand2());
*error = !v.isKnown();
*result = v.intvalue;
} else {
if (expr->str() == "<")
*result = result1 < result2;
else if (expr->str() == "<=")
*result = result1 <= result2;
else if (expr->str() == ">")
*result = result1 > result2;
else if (expr->str() == ">=")
*result = result1 >= result2;
else if (expr->str() == "==")
*result = result1 == result2;
else if (expr->str() == "!=")
*result = result1 != result2;
}
}

else if (expr->isAssignmentOp()) {
Expand Down
194 changes: 148 additions & 46 deletions lib/valueflow.cpp
View file
Original file line number Diff line number Diff line change
Expand Up @@ -4692,6 +4692,93 @@ static const ValueFlow::Value* proveNotEqual(const std::list<ValueFlow::Value>&
return result;
}

static std::vector<MathLib::bigint> minUnsignedValue(const Token* tok, int depth = 8)
{
std::vector<MathLib::bigint> result = {};
if (!tok)
return result;
if (depth < 0)
return result;
if (tok->hasKnownIntValue()) {
result = {tok->values().front().intvalue};
} else if (tok->isConstOp() && tok->astOperand1() && tok->astOperand2()) {
std::vector<MathLib::bigint> op1 = minUnsignedValue(tok->astOperand1(), depth - 1);
std::vector<MathLib::bigint> op2 = minUnsignedValue(tok->astOperand2(), depth - 1);
if (!op1.empty() && !op1.empty())
result = {calculate(tok->str(), op1.front(), op2.front())};
}
if (result.empty() && tok->valueType() && tok->valueType()->sign == ValueType::UNSIGNED)
result = {0};
return result;
}

ValueFlow::Value inferCondition(const std::string& op, const Token* varTok, MathLib::bigint val)
{
if (!varTok)
return ValueFlow::Value{};
if (varTok->hasKnownIntValue())
return ValueFlow::Value{};
if (std::none_of(varTok->values().begin(), varTok->values().end(), [](const ValueFlow::Value& v) {
return v.isImpossible() && v.valueType == ValueFlow::Value::ValueType::INT;
})) {
if (varTok->valueType() && varTok->valueType()->sign == ValueType::UNSIGNED && (op == ">" || op == ">=")) {
std::vector<MathLib::bigint> minvalue = minUnsignedValue(varTok);
if (minvalue.empty())
return ValueFlow::Value{};
bool isTrue = calculate(op, std::max<MathLib::bigint>(0, minvalue.front()), val);
if (!isTrue)
return ValueFlow::Value{};
ValueFlow::Value value;
value.intvalue = 1;
value.bound = ValueFlow::Value::Bound::Point;
value.setKnown();
return value;
}
return ValueFlow::Value{};
}
const ValueFlow::Value* result = nullptr;
bool known = false;
if (op == "==" || op == "!=") {
result = proveNotEqual(varTok->values(), val);
known = op == "!=";
} else if (op == "<" || op == ">=") {
result = proveLessThan(varTok->values(), val);
known = op == "<";
if (!result && !isSaturated(val)) {
result = proveGreaterThan(varTok->values(), val - 1);
known = op == ">=";
}
} else if (op == ">" || op == "<=") {
result = proveGreaterThan(varTok->values(), val);
known = op == ">";
if (!result && !isSaturated(val)) {
result = proveLessThan(varTok->values(), val + 1);
known = op == "<=";
}
}
if (!result)
return ValueFlow::Value{};
ValueFlow::Value value = *result;
value.intvalue = known;
value.bound = ValueFlow::Value::Bound::Point;
value.setKnown();
return value;
}

ValueFlow::Value inferCondition(std::string op, MathLib::bigint val, const Token* varTok)
{
// Flip the operator
if (op == ">")
op = "<";
else if (op == "<")
op = ">";
else if (op == ">=")
op = "<=";
else if (op == "<=")
op = ">=";
return inferCondition(op, varTok, val);
}

static void valueFlowInferCondition(TokenList* tokenlist,
const Settings* settings)
{
Expand All @@ -4711,57 +4798,72 @@ static void valueFlowInferCondition(TokenList* tokenlist,
value.setKnown();
setTokenValue(tok, value, settings);
} else if (tok->isComparisonOp()) {
MathLib::bigint val = 0;
const Token* varTok = nullptr;
ValueFlow::Value value{};
std::string op = tok->str();
if (tok->astOperand1()->hasKnownIntValue()) {
val = tok->astOperand1()->values().front().intvalue;
varTok = tok->astOperand2();
// Flip the operator
if (op == ">")
op = "<";
else if (op == "<")
op = ">";
else if (op == ">=")
op = "<=";
else if (op == "<=")
op = ">=";
MathLib::bigint val = tok->astOperand1()->values().front().intvalue;
const Token* varTok = tok->astOperand2();
value = inferCondition(tok->str(), val, varTok);
} else if (tok->astOperand2()->hasKnownIntValue()) {
val = tok->astOperand2()->values().front().intvalue;
varTok = tok->astOperand1();
MathLib::bigint val = tok->astOperand2()->values().front().intvalue;
const Token* varTok = tok->astOperand1();
value = inferCondition(tok->str(), varTok, val);
}
if (!varTok)
continue;
if (varTok->hasKnownIntValue())
continue;
if (varTok->values().empty())
continue;
const ValueFlow::Value* result = nullptr;
bool known = false;
if (op == "==" || op == "!=") {
result = proveNotEqual(varTok->values(), val);
known = op == "!=";
} else if (op == "<" || op == ">=") {
result = proveLessThan(varTok->values(), val);
known = op == "<";
if (!result && !isSaturated(val)) {
result = proveGreaterThan(varTok->values(), val - 1);
known = op == ">=";
}
} else if (op == ">" || op == "<=") {
result = proveGreaterThan(varTok->values(), val);
known = op == ">";
if (!result && !isSaturated(val)) {
result = proveLessThan(varTok->values(), val + 1);
known = op == "<=";
}
}
if (!result)

if (!value.isKnown())
continue;
ValueFlow::Value value = *result;
value.intvalue = known;
value.bound = ValueFlow::Value::Bound::Point;
value.setKnown();

// MathLib::bigint val = 0;
// const Token* varTok = nullptr;
// std::string op = tok->str();
// if (tok->astOperand1()->hasKnownIntValue()) {
// val = tok->astOperand1()->values().front().intvalue;
// varTok = tok->astOperand2();
// // Flip the operator
// if (op == ">")
// op = "<";
// else if (op == "<")
// op = ">";
// else if (op == ">=")
// op = "<=";
// else if (op == "<=")
// op = ">=";
// } else if (tok->astOperand2()->hasKnownIntValue()) {
// val = tok->astOperand2()->values().front().intvalue;
// varTok = tok->astOperand1();
// }
// if (!varTok)
// continue;
// if (varTok->hasKnownIntValue())
// continue;
// if (varTok->values().empty())
// continue;
// const ValueFlow::Value* result = nullptr;
// bool known = false;
// if (op == "==" || op == "!=") {
// result = proveNotEqual(varTok->values(), val);
// known = op == "!=";
// } else if (op == "<" || op == ">=") {
// result = proveLessThan(varTok->values(), val);
// known = op == "<";
// if (!result && !isSaturated(val)) {
// result = proveGreaterThan(varTok->values(), val - 1);
// known = op == ">=";
// }
// } else if (op == ">" || op == "<=") {
// result = proveGreaterThan(varTok->values(), val);
// known = op == ">";
// if (!result && !isSaturated(val)) {
// result = proveLessThan(varTok->values(), val + 1);
// known = op == "<=";
// }
// }
// if (!result)
// continue;
// ValueFlow::Value value = *result;
// value.intvalue = known;
// value.bound = ValueFlow::Value::Bound::Point;
// value.setKnown();
setTokenValue(tok, value, settings);
}
}
Expand Down
3 changes: 3 additions & 0 deletions lib/valueflow.h
View file
Original file line number Diff line number Diff line change
Expand Up @@ -385,6 +385,9 @@ struct LifetimeToken {
const Token *parseCompareInt(const Token *tok, ValueFlow::Value &true_value, ValueFlow::Value &false_value, const std::function<std::vector<MathLib::bigint>(const Token*)>& evaluate);
const Token *parseCompareInt(const Token *tok, ValueFlow::Value &true_value, ValueFlow::Value &false_value);

ValueFlow::Value inferCondition(std::string op, MathLib::bigint val, const Token* varTok);
ValueFlow::Value inferCondition(const std::string& op, const Token* varTok, MathLib::bigint val);

std::vector<LifetimeToken> getLifetimeTokens(const Token* tok,
bool escape = false,
ValueFlow::Value::ErrorPath errorPath = ValueFlow::Value::ErrorPath{},
Expand Down
2 changes: 1 addition & 1 deletion test/testcondition.cpp
View file
Original file line number Diff line number Diff line change
Expand Up @@ -2411,7 +2411,7 @@ class TestCondition : public TestFixture {
ASSERT_EQUALS("", errout.str());

check("void f1(const std::string &s) { if(s.size() >= 0) if(s.empty()) {}} ");
ASSERT_EQUALS("", errout.str());
ASSERT_EQUALS("[test.cpp:1]: (style) Condition 's.size()>=0' is always true\n", errout.str());

// TODO: These are identical condition since size cannot be negative
check("void f1(const std::string &s) { if(s.size() <= 0) if(s.empty()) {}} ");
Expand Down
8 changes: 8 additions & 0 deletions test/teststl.cpp
View file
Original file line number Diff line number Diff line change
Expand Up @@ -396,6 +396,14 @@ class TestStl : public TestFixture {
" Bar(0.34, result[1]);\n"
"}\n");
ASSERT_EQUALS("", errout.str());

checkNormal("void f(size_t entries) {\n"
" std::vector<uint8_t> v;\n"
" if (v.size() < entries + 2)\n"
" v.resize(entries + 2);\n"
" v[0] = 1;\n"
"}\n");
ASSERT_EQUALS("", errout.str());
}

void outOfBoundsIndexExpression() {
Expand Down

0 comments on commit 82810ed

Please sign in to comment.