/*

* Cppcheck - A tool for static C/C++ code analysis

* Copyright (C) 2007-2012 Daniel Marjamäki and Cppcheck team.

*

* This program is free software: you can redistribute it and/or modify

* it under the terms of the GNU General Public License as published by

* the Free Software Foundation, either version 3 of the License, or

* (at your option) any later version.

*

* This program is distributed in the hope that it will be useful,

* but WITHOUT ANY WARRANTY; without even the implied warranty of

* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the

* GNU General Public License for more details.

*

* You should have received a copy of the GNU General Public License

* along with this program. If not, see <http://www.gnu.org/licenses/>.

*/

//---------------------------------------------------------------------------

// Buffer overrun..

//---------------------------------------------------------------------------

#include "checkbufferoverrun.h"

#include "tokenize.h"

#include "errorlogger.h"

#include "mathlib.h"

#include "symboldatabase.h"

#include <algorithm>

#include <sstream>

#include <list>

#include <cassert> // <- assert

#include <cstdlib>

//---------------------------------------------------------------------------

// Register this check class (by creating a static instance of it)

namespace {

CheckBufferOverrun instance;

}

//---------------------------------------------------------------------------

static void makeArrayIndexOutOfBoundsError(std::ostream& oss, const CheckBufferOverrun::ArrayInfo &arrayInfo, const std::vector<MathLib::bigint> &index)

{

oss << "Array '" << arrayInfo.varname();

for (unsigned int i = 0; i < arrayInfo.num().size(); ++i)

oss << "[" << arrayInfo.num(i) << "]";

if (index.size() == 1)

oss << "' accessed at index " << index[0] << ", which is";

else {

oss << "' index " << arrayInfo.varname();

for (unsigned int i = 0; i < index.size(); ++i)

oss << "[" << index[i] << "]";

}

oss << " out of bounds.";

}

void CheckBufferOverrun::arrayIndexOutOfBoundsError(const Token *tok, const ArrayInfo &arrayInfo, const std::vector<MathLib::bigint> &index)

{

std::ostringstream oss;

makeArrayIndexOutOfBoundsError(oss, arrayInfo, index);

reportError(tok, Severity::error, "arrayIndexOutOfBounds", oss.str());

}

void CheckBufferOverrun::arrayIndexOutOfBoundsError(const std::list<const Token *> &callstack, const ArrayInfo &arrayInfo, const std::vector<MathLib::bigint> &index)

{

std::ostringstream oss;

makeArrayIndexOutOfBoundsError(oss, arrayInfo, index);

reportError(callstack, Severity::error, "arrayIndexOutOfBounds", oss.str());

}

static std::string bufferOverrunMessage(std::string varnames)

{

varnames.erase(std::remove(varnames.begin(), varnames.end(), ' '), varnames.end());

std::string errmsg("Buffer is accessed out of bounds");

if (!varnames.empty())

errmsg += ": " + varnames;

else

errmsg += ".";

return errmsg;

}

void CheckBufferOverrun::bufferOverrunError(const Token *tok, const std::string &varnames)

{

reportError(tok, Severity::error, "bufferAccessOutOfBounds", bufferOverrunMessage(varnames));

}

void CheckBufferOverrun::bufferOverrunError(const std::list<const Token *> &callstack, const std::string &varnames)

{

reportError(callstack, Severity::error, "bufferAccessOutOfBounds", bufferOverrunMessage(varnames));

}

void CheckBufferOverrun::possibleBufferOverrunError(const Token *tok, const std::string &src, const std::string &dst, bool cat)

{

if (cat)

reportError(tok, Severity::warning, "possibleBufferAccessOutOfBounds",

"Possible buffer overflow if strlen(" + src + ") is larger than sizeof(" + dst + ")-strlen(" + dst +").\n"

"Possible buffer overflow if strlen(" + src + ") is larger than sizeof(" + dst + ")-strlen(" + dst +"). "

"The source buffer is larger than the destination buffer so there is the potential for overflowing the destination buffer.");

else

reportError(tok, Severity::warning, "possibleBufferAccessOutOfBounds",

"Possible buffer overflow if strlen(" + src + ") is larger than or equal to sizeof(" + dst + ").\n"

"Possible buffer overflow if strlen(" + src + ") is larger than or equal to sizeof(" + dst + "). "

"The source buffer is larger than the destination buffer so there is the potential for overflowing the destination buffer.");

}

void CheckBufferOverrun::possibleReadlinkBufferOverrunError(const Token* tok, const std::string &funcname, const std::string &varname)

{

const std::string errmsg = funcname + "() might return the full size of '" + varname + "'. Lower the supplied size by one.\n" +

funcname + "() might return the full size of '" + varname + "'. "

"If a " + varname + "[len] = '\\0'; statement follows, it will overrun the buffer. Lower the supplied size by one.";

reportError(tok, Severity::warning, "possibleReadlinkBufferOverrun", errmsg, true);

}

void CheckBufferOverrun::strncatUsageError(const Token *tok)

{

if (_settings && !_settings->isEnabled("style"))

return;

reportError(tok, Severity::warning, "strncatUsage",

"Dangerous usage of strncat - 3rd parameter is the maximum number of characters to append.\n"

"strncat appends at max its 3rd parameter's amount of characters. The safe way to use "

"strncat is to calculate remaining space in the buffer and use it as 3rd parameter.");

}

void CheckBufferOverrun::outOfBoundsError(const Token *tok, const std::string &what, const bool show_size_info, const MathLib::bigint &supplied_size, const MathLib::bigint &actual_size)

{

std::ostringstream oss;

oss << what << " is out of bounds";

if (show_size_info)

oss << ": Supplied size " << supplied_size << " is larger than actual size " << actual_size;

oss << '.';

reportError(tok, Severity::error, "outOfBounds", oss.str());

}

void CheckBufferOverrun::pointerOutOfBoundsError(const Token *tok, const std::string &object)

{

reportError(tok, Severity::portability, "pointerOutOfBounds", "Undefined behaviour: Pointer arithmetic result does not point into or just past the end of the " + object + ".\n"

"Undefined behaviour: The result of this pointer arithmetic does not point into or just one element past the end of the " + object + ". Further information: https://www.securecoding.cert.org/confluence/display/seccode/ARR30-C.+Do+not+form+or+use+out+of+bounds+pointers+or+array+subscripts");

}

void CheckBufferOverrun::sizeArgumentAsCharError(const Token *tok)

{

if (_settings && !_settings->isEnabled("style"))

return;

reportError(tok, Severity::warning, "sizeArgumentAsChar", "The size argument is given as a char constant.");

}

void CheckBufferOverrun::terminateStrncpyError(const Token *tok, const std::string &varname)

{

reportError(tok, Severity::warning, "terminateStrncpy",

"The buffer '" + varname + "' may not be null-terminated after the call to strncpy().\n"

"If the source string's size fits or exceeds the given size, strncpy() does not add a "

"zero at the end of the buffer. This causes bugs later in the code if the code "

"assumes buffer is null-terminated.");

}

void CheckBufferOverrun::cmdLineArgsError(const Token *tok)

{

reportError(tok, Severity::error, "insecureCmdLineArgs", "Buffer overrun possible for long command line arguments.");

}

void CheckBufferOverrun::bufferNotZeroTerminatedError(const Token *tok, const std::string &varname, const std::string &function)

{

const std::string errmsg = "The buffer '" + varname + "' is not null-terminated after the call to " + function + "().\n"

"The buffer '" + varname + "' is not null-terminated after the call to " + function + "(). "

"This will cause bugs later in the code if the code assumes the buffer is null-terminated.";

reportError(tok, Severity::warning, "bufferNotZeroTerminated", errmsg, true);

}

//---------------------------------------------------------------------------

//---------------------------------------------------------------------------

// Check array usage..

//---------------------------------------------------------------------------

/**

* @brief This is a helper class to be used with std::find_if

*/

class TokenStrEquals {

public:

/**

* @param str Token::str() is compared against this.

*/

explicit TokenStrEquals(const std::string &str)

: value(str) {

}

/**

* Called automatically by std::find_if

* @param tok Token inside the list

*/

bool operator()(const Token *tok) const {

return value == tok->str();

}

private:

TokenStrEquals& operator=(const TokenStrEquals&); // disallow assignments

const std::string value;

};

/**

* bailout if variable is used inside if/else/switch block or if there is "break"

* @param tok token for "if" or "switch"

* @param varid variable id

* @return is bailout recommended?

*/

static bool bailoutIfSwitch(const Token *tok, const unsigned int varid)

{

// Used later to check if the body belongs to a "if"

bool is_if = tok->str() == "if";

const Token* end = tok->linkAt(1)->linkAt(1);

if (Token::simpleMatch(end, "} else {")) // scan the else-block

end = end->linkAt(2);

for (; tok != end; tok = tok->next()) {

// If scanning a "if" block then bailout for "break"

if (is_if && (tok->str() == "break" || tok->str() == "continue"))

return true;

// bailout for "return"

else if (tok->str() == "return")

return true;

// bailout if varid is found

else if (tok->varId() == varid)

return true;

}

// No bailout stuff found => return false

return false;

}

/**

* Parse for loop initialization statement. Look for a counter variable

* \param tok [in] first token inside the parentheses

* \param varid [out] varid of counter variable

* \param varname [out] name of counter variable

* \param init_value [out] init value of counter variable

* \return success => pointer to the for loop condition. fail => 0

*/

static const Token *for_init(const Token *tok, unsigned int &varid, std::string &varname, std::string &init_value)

{

if (Token::Match(tok, "%var% = %any% ;")) {

if (tok->tokAt(2)->isNumber()) {

init_value = tok->strAt(2);

}

varid = tok->varId();

varname = tok->str();

tok = tok->tokAt(4);

} else if (Token::Match(tok, "%type% %var% = %any% ;")) {

if (tok->tokAt(3)->isNumber()) {

init_value = tok->strAt(3);

}

varid = tok->next()->varId();

varname = tok->next()->str();

tok = tok->tokAt(5);

} else if (Token::Match(tok, "%type% %type% %var% = %any% ;")) {

if (tok->tokAt(4)->isNumber()) {

init_value = tok->strAt(4);

}

varid = tok->tokAt(2)->varId();

varname = tok->tokAt(2)->str();

tok = tok->tokAt(6);

} else

return 0;

if (!init_value.empty() && (Token::Match(tok, "-- %varid%", varid) || Token::Match(tok, "%varid% --", varid))) {

init_value = MathLib::subtract(init_value, "1");

}

return tok;

}

/** Parse for condition */

static bool for_condition(const Token *tok2, unsigned int varid, std::string &min_value, std::string &max_value, bool &maxMinFlipped)

{

if (Token::Match(tok2, "%varid% < %num% ;|&&|%oror%", varid) ||

Token::Match(tok2, "%varid% != %num% ; ++ %varid%", varid) ||

Token::Match(tok2, "%varid% != %num% ; %varid% ++", varid)) {

maxMinFlipped = false;

const MathLib::bigint value = MathLib::toLongNumber(tok2->strAt(2));

max_value = MathLib::toString<MathLib::bigint>(value - 1);

} else if (Token::Match(tok2, "%varid% <= %num% ;|&&|%oror%", varid)) {

maxMinFlipped = false;

max_value = tok2->strAt(2);

} else if (Token::Match(tok2, "%num% < %varid% ;|&&|%oror%", varid) ||

Token::Match(tok2, "%num% != %varid% ; ++ %varid%", varid) ||

Token::Match(tok2, "%num% != %varid% ; %varid% ++", varid)) {

maxMinFlipped = true;

const MathLib::bigint value = MathLib::toLongNumber(tok2->str());

max_value = min_value;

min_value = MathLib::toString<MathLib::bigint>(value + 1);

} else if (Token::Match(tok2, "%num% <= %varid% ;|&&|%oror%", varid)) {

maxMinFlipped = true;

max_value = min_value;

min_value = tok2->str();

} else {

// parse condition

while (tok2 && tok2->str() != ";") {

if (tok2->str() == "(")

tok2 = tok2->link();

else if (tok2->str() == ")") // unexpected ")" => break

break;

if (tok2->str() == "&&" || tok2->str() == "||") {

if (for_condition(tok2->next(), varid, min_value, max_value, maxMinFlipped))

return true;

}

tok2 = tok2->next();

}

return false;

}

return true;

}

/**

* calculate maximum value of loop variable

* @param stepvalue token that contains the step value

* @param min_value the minimum value of loop variable

* @param max_value maximum value of the loop variable

*/

static bool for_maxvalue(const Token * const stepvalue, const std::string &min_value, std::string &max_value)

{

if (!MathLib::isInt(stepvalue->str()))

return false;

// We have for example code: "for(i=2;i<22;i+=6)

// We can calculate that max value for i is 20, not 21

// 21-2 = 19

// 19/6 = 3

// 6*3+2 = 20

const MathLib::bigint num = MathLib::toLongNumber(stepvalue->str());

MathLib::bigint max = MathLib::toLongNumber(max_value);

const MathLib::bigint min = MathLib::toLongNumber(min_value);

max = ((max - min) / num) * num + min;

max_value = MathLib::toString<MathLib::bigint>(max);

return true;

}

/**

* Parse the third sub-statement in for head

* \param tok first token

* \param varid variable id of counter

* \param min_value min value of counter

* \param max_value max value of counter

* \param maxMinFlipped counting from max to min

*/

static bool for3(const Token * const tok,

unsigned int varid,

std::string &min_value,

std::string &max_value,

const bool maxMinFlipped)

{

assert(tok != 0);

if (Token::Match(tok, "%varid% += %num% )", varid) ||

Token::Match(tok, "%varid% = %num% + %varid% )", varid)) {

if (!for_maxvalue(tok->tokAt(2), min_value, max_value))

return false;

} else if (Token::Match(tok, "%varid% = %varid% + %num% )", varid)) {

if (!for_maxvalue(tok->tokAt(4), min_value, max_value))

return false;

} else if (Token::Match(tok, "%varid% -= %num% )", varid) ||

Token::Match(tok, "%varid% = %num% - %varid% )", varid)) {

if (!for_maxvalue(tok->tokAt(2), min_value, max_value))

return false;

} else if (Token::Match(tok, "%varid% = %varid% - %num% )", varid)) {

if (!for_maxvalue(tok->tokAt(4), min_value, max_value))

return false;

} else if (Token::Match(tok, "--| %varid% --| )", varid)) {

if (!maxMinFlipped && MathLib::toLongNumber(min_value) < MathLib::toLongNumber(max_value)) {

// Code relies on the fact that integer will overflow:

// for (unsigned int i = 3; i < 5; --i)

// Set min value in this case to zero.

max_value = min_value;

min_value = "0";

}

} else if (! Token::Match(tok, "++| %varid% ++| )", varid)) {

return false;

}

return true;

}

/**

* Check is the counter variable increased elsewhere inside the loop or used

* for anything else except reading

* \param tok1 first token of for-body

* \param varid counter variable id

* \return bailout needed => true

*/

static bool for_bailout(const Token * const tok1, unsigned int varid)

{

for (const Token *loopTok = tok1; loopTok && loopTok != tok1->link(); loopTok = loopTok->next()) {

if (loopTok->varId() == varid) {

// Counter variable used inside loop

if (Token::Match(loopTok->next(), "+=|-=|++|--|=") ||

(loopTok->previous()->type() == Token::eIncDecOp)) {

return true;

}

}

}

return false;

}

void CheckBufferOverrun::parse_for_body(const Token *tok, const ArrayInfo &arrayInfo, const std::string &strindex, bool condition_out_of_bounds, unsigned int counter_varid, const std::string &min_counter_value, const std::string &max_counter_value)

{

const std::string pattern = (arrayInfo.varid() ? std::string("%varid%") : arrayInfo.varname()) + " [ " + strindex + " ]";

for (const Token* tok2 = tok; tok2 && tok2 != tok->link(); tok2 = tok2->next()) {

// TODO: try to reduce false negatives. This is just a quick fix

// for TestBufferOverrun::array_index_for_question

if (tok2->str() == "?")

break;

if (Token::simpleMatch(tok2, "for (") && Token::simpleMatch(tok2->next()->link(), ") {")) {

const Token *endpar = tok2->next()->link();

const Token *startbody = endpar->next();

const Token *endbody = startbody->link();

tok2 = endbody;

continue;

}

if (Token::Match(tok2, "if|switch")) {

if (bailoutIfSwitch(tok2, arrayInfo.varid()))

break;

}

if (condition_out_of_bounds && Token::Match(tok2, pattern.c_str(), arrayInfo.varid())) {

bufferOverrunError(tok2, arrayInfo.varname());

break;

}

else if (arrayInfo.varid() && tok2->varId() && counter_varid > 0 && !min_counter_value.empty() && !max_counter_value.empty()) {

// Is the loop variable used to calculate the array index?

// In this scope it is determined if such calculated

// array indexes are out of bounds.

// Only the minimum and maximum results of the calculation is

// determined

// Minimum calculated array index

int min_index = 0;

// Maximum calculated array index

int max_index = 0;

if (Token::Match(tok2, "%varid% [ %var% +|-|*|/ %num% ]", arrayInfo.varid()) &&

tok2->tokAt(2)->varId() == counter_varid) {

// operator: +-*/

const char action = tok2->strAt(3)[0];

// second operator

const std::string &second(tok2->strAt(4));

//printf("min_index: %s %c %s\n", min_counter_value.c_str(), action, second.c_str());

//printf("max_index: %s %c %s\n", max_counter_value.c_str(), action, second.c_str());

min_index = std::atoi(MathLib::calculate(min_counter_value, second, action).c_str());

max_index = std::atoi(MathLib::calculate(max_counter_value, second, action).c_str());

} else if (Token::Match(tok2, "%varid% [ %num% +|-|*|/ %var% ]", arrayInfo.varid()) &&

tok2->tokAt(4)->varId() == counter_varid) {

// operator: +-*/

const char action = tok2->strAt(3)[0];

// first operand

const std::string &first(tok2->strAt(2));

//printf("min_index: %s %c %s\n", first.c_str(), action, min_counter_value.c_str());

//printf("max_index: %s %c %s\n", first.c_str(), action, max_counter_value.c_str());

min_index = std::atoi(MathLib::calculate(first, min_counter_value, action).c_str());

max_index = std::atoi(MathLib::calculate(first, max_counter_value, action).c_str());

}

else {

continue;

}

//printf("min_index = %d, max_index = %d, size = %d\n", min_index, max_index, size);

if (min_index < 0 || max_index < 0) {

std::vector<MathLib::bigint> indexes;

indexes.push_back(std::min(min_index, max_index));

arrayIndexOutOfBoundsError(tok2, arrayInfo, indexes);

}

// skip 0 length arrays

if (arrayInfo.num(0) == 0)

;

// taking address.

else if (tok2->previous()->str() == "&" && max_index == arrayInfo.num(0))

;

else if (arrayInfo.num(0) && (min_index >= arrayInfo.num(0) || max_index >= arrayInfo.num(0))) {

std::vector<MathLib::bigint> indexes;

indexes.push_back(std::max(min_index, max_index));

arrayIndexOutOfBoundsError(tok2, arrayInfo, indexes);

}

}

}

}

void CheckBufferOverrun::checkFunctionParameter(const Token &tok, unsigned int par, const ArrayInfo &arrayInfo, std::list<const Token *> callstack)

{

// total_size : which parameter in function call takes the total size?

std::map<std::string, unsigned int> total_size;

total_size["fgets"] = 2; // The second argument for fgets can't exceed the total size of the array

total_size["memcmp"] = 3;

total_size["memcpy"] = 3;

total_size["memmove"] = 3;

total_size["memchr"] = 3;

if (par == 1) {

// reading from array

// if it is zero terminated properly there won't be buffer overruns

total_size["strncat"] = 3;

total_size["strncpy"] = 3;

total_size["memset"] = 3;

total_size["fread"] = 1001; // parameter 2 * parameter 3

total_size["fwrite"] = 1001; // parameter 2 * parameter 3

}

else if (par == 2) {

total_size["read"] = 3;

total_size["pread"] = 3;

total_size["write"] = 3;

total_size["recv"] = 3;

total_size["recvfrom"] = 3;

total_size["send"] = 3;

total_size["sendto"] = 3;

}

std::map<std::string, unsigned int>::const_iterator it = total_size.find(tok.str());

if (it != total_size.end()) {

if (arrayInfo.element_size() == 0)

return;

// arg : the index of the "wanted" argument in the function call.

unsigned int arg = it->second;

// Parse function call. When a ',' is seen, arg is decremented.

// if arg becomes 1 then the current function parameter is the wanted parameter.

// if arg becomes 1000 then multiply current and next argument.

const Token *tok2 = tok.tokAt(2)->nextArgument();

if (arg == 3)

tok2 = tok2->nextArgument();

if ((arg == 2 || arg == 3) && tok2) {

if (Token::Match(tok2, "%num% ,|)")) {

const MathLib::bigint sz = MathLib::toLongNumber(tok2->str());

MathLib::bigint elements = 1;

for (unsigned int i = 0; i < arrayInfo.num().size(); ++i)

elements *= arrayInfo.num(i);

if (sz < 0 || sz > int(elements * arrayInfo.element_size())) {

bufferOverrunError(callstack, arrayInfo.varname());

}

}

else if (Token::Match(tok2->next(), ",|)") && tok2->type() == Token::eChar) {

sizeArgumentAsCharError(tok2);

}

} else if (arg == 1001) { // special code. This parameter multiplied with the next must not exceed total_size

if (Token::Match(tok2, "%num% , %num% ,|)")) {

const MathLib::bigint sz = MathLib::toLongNumber(MathLib::multiply(tok2->str(), tok2->strAt(2)));

MathLib::bigint elements = 1;

for (unsigned int i = 0; i < arrayInfo.num().size(); ++i)

elements *= arrayInfo.num(i);

if (sz < 0 || sz > int(elements * arrayInfo.element_size())) {

bufferOverrunError(&tok, arrayInfo.varname());

}

}

}

}

// Calling a user function?

// only 1-dimensional arrays can be checked currently

else if (arrayInfo.num().size() == 1) {

const Token *ftok = _tokenizer->getFunctionTokenByName(tok.str().c_str());

if (Token::Match(ftok, "%var% (") && Token::Match(ftok->next()->link(), ") const| {")) {

// Get varid for the corresponding parameter..

const Token *ftok2 = ftok->tokAt(2);

for (unsigned int i = 1; i < par; i++)

ftok2 = ftok2->nextArgument();

unsigned int parameterVarId = 0;

for (; ftok2; ftok2 = ftok2->next()) {

if (ftok2->str() == "(")

ftok2 = ftok2->link();

else if (ftok2->str() == "," || ftok2->str() == ")")

break;

else if (Token::Match(ftok2, "%var% ,|)|[")) {

// check type..

const Token *type = ftok2->previous();

while (Token::Match(type, "*|const"))

type = type->previous();

if (type && _tokenizer->sizeOfType(type) == arrayInfo.element_size())

parameterVarId = ftok2->varId();

}

}

// No parameterVarId => bail out

if (parameterVarId == 0)

return;

// Step into the function scope..

ftok = ftok->next()->link();

if (!Token::Match(ftok, ") const| {"))

return;

ftok = Token::findsimplematch(ftok, "{");

ftok = ftok->next();

// Check the parameter usage in the function scope..

for (; ftok; ftok = ftok->next()) {

if (Token::Match(ftok, "if|for|while (")) {

// bailout if there is buffer usage..

if (bailoutIfSwitch(ftok, parameterVarId)) {

break;

}

// no bailout is needed. skip the if-block

else {

// goto end of if block..

ftok = ftok->next()->link()->next()->link();

if (Token::simpleMatch(ftok, "} else {"))

ftok = ftok->linkAt(2);

if (!ftok)

break;

continue;

}

}

if (ftok->str() == "}")

break;

if (ftok->varId() == parameterVarId) {

if (Token::Match(ftok->previous(), "-- %var%") ||

Token::Match(ftok, "%var% --"))

break;

if (Token::Match(ftok->previous(), "=|;|{|}|%op% %var% [ %num% ]")) {

const MathLib::bigint index = MathLib::toLongNumber(ftok->strAt(2));

if (index >= 0 && arrayInfo.num(0) > 0 && index >= arrayInfo.num(0)) {

std::list<const Token *> callstack2(callstack);

callstack2.push_back(ftok);

std::vector<MathLib::bigint> indexes;

indexes.push_back(index);

arrayIndexOutOfBoundsError(callstack2, arrayInfo, indexes);

}

}

}

// Calling function..

if (Token::Match(ftok, "%var% (")) {

ArrayInfo ai(arrayInfo);

ai.varid(parameterVarId);

checkFunctionCall(ftok, ai, callstack);

}

}

}

}

}

void CheckBufferOverrun::checkFunctionCall(const Token *tok, const ArrayInfo &arrayInfo, std::list<const Token *> callstack)

{

// Don't go deeper than 2 levels, the checking can get very slow

// when there is no limit

if (callstack.size() >= 2)

return;

// Prevent recursion

for (std::list<const Token*>::const_iterator it = callstack.begin(); it != callstack.end(); ++it) {

// Same function name => bail out

if (tok->str() == (*it)->str())

return;

}

callstack.push_back(tok);

const Token *tok2 = tok->tokAt(2);

// 1st parameter..

if (Token::Match(tok2, "%varid% ,|)", arrayInfo.varid()))

checkFunctionParameter(*tok, 1, arrayInfo, callstack);

else if (Token::Match(tok2, "%varid% + %num% ,|)", arrayInfo.varid())) {

const ArrayInfo ai(arrayInfo.limit(MathLib::toLongNumber(tok2->strAt(2))));

checkFunctionParameter(*tok, 1, ai, callstack);

}

// goto 2nd parameter and check it..

tok2 = tok2->nextArgument();

if (Token::Match(tok2, "%varid% ,|)", arrayInfo.varid()))

checkFunctionParameter(*tok, 2, arrayInfo, callstack);

else if (Token::Match(tok2, "%varid% + %num% ,|)", arrayInfo.varid())) {

const ArrayInfo ai(arrayInfo.limit(MathLib::toLongNumber(tok2->strAt(2))));

checkFunctionParameter(*tok, 2, ai, callstack);

}

}

void CheckBufferOverrun::checkScopeForBody(const Token *tok, const ArrayInfo &arrayInfo, bool &bailout)

{

bailout = false;

const Token *tok2 = tok->tokAt(2);

const MathLib::bigint size = arrayInfo.num(0);

// Check if there is a break in the body..

{

const Token *bodyStart = tok->next()->link()->next();

const Token *bodyEnd = bodyStart->link();

if (Token::findsimplematch(bodyStart, "break ;", bodyEnd))

return;

}

std::string counter_name;

unsigned int counter_varid = 0;

std::string counter_init_value;

tok2 = for_init(tok2, counter_varid, counter_name, counter_init_value);

if (tok2 == 0 || counter_varid == 0)

return;

bool maxMinFlipped = false;

std::string min_counter_value = counter_init_value;

std::string max_counter_value;

if (!for_condition(tok2, counter_varid, min_counter_value, max_counter_value, maxMinFlipped)) {

// Can't understand the condition. Check that the start value

// is used correctly

const Token *startForScope = tok->next()->link()->next();

if (!for_bailout(startForScope, counter_varid)) {

// Get index variable and stopsize.

bool condition_out_of_bounds = bool(size > 0);

if (MathLib::toLongNumber(counter_init_value) < size)

condition_out_of_bounds = false;

parse_for_body(startForScope, arrayInfo, counter_name, condition_out_of_bounds, counter_varid, counter_init_value, counter_init_value);

}

return;

}

// Get index variable and stopsize.

bool condition_out_of_bounds = bool(size > 0);

if (MathLib::toLongNumber(max_counter_value) < size)

condition_out_of_bounds = false;

// Goto the end of the condition

while (tok2 && tok2->str() != ";") {

if (tok2->str() == "(")

tok2 = tok2->link();

else if (tok2->str() == ")") // unexpected ")" => break

break;

tok2 = tok2->next();

}

if (!tok2 || tok2->str() != ";")

return;

if (!for3(tok2->next(), counter_varid, min_counter_value, max_counter_value, maxMinFlipped))

return;

if (Token::Match(tok2->next(), "%var% =|+=|-=") && MathLib::toLongNumber(max_counter_value) <= size)

condition_out_of_bounds = false;

// Goto the end parenthesis of the for-statement: "for (x; y; z)" ..

tok2 = tok->next()->link();

if (!tok2 || !tok2->tokAt(5)) {

bailout = true;

return;

}

// Check is the counter variable increased elsewhere inside the loop or used

// for anything else except reading

if (for_bailout(tok2->next(), counter_varid)) {

bailout = true;

return;

}

parse_for_body(tok2->next(), arrayInfo, counter_name, condition_out_of_bounds, counter_varid, min_counter_value, max_counter_value);

}

void CheckBufferOverrun::checkScope(const Token *tok, const std::vector<std::string> &varname, const ArrayInfo &arrayInfo)

{

const MathLib::bigint size = arrayInfo.num(0);

if (size == 0) // unknown size

return;

const MathLib::bigint total_size = arrayInfo.element_size() * arrayInfo.num(0);

unsigned int varid = arrayInfo.varid();

std::string varnames;

for (unsigned int i = 0; i < varname.size(); ++i)

varnames += (i == 0 ? "" : " . ") + varname[i];

const unsigned char varc = static_cast<unsigned char>(varname.empty() ? 0U : (varname.size() - 1) * 2U);

if (tok && tok->str() == "return") {

tok = tok->next();

if (!tok)

return;

}

// Array index..

if ((varid > 0 && Token::Match(tok, "%varid% [ %num% ]", varid)) ||

(varid == 0 && Token::Match(tok, (varnames + " [ %num% ]").c_str()))) {

const MathLib::bigint index = MathLib::toLongNumber(tok->strAt(2 + varc));

if (index >= size) {

std::vector<MathLib::bigint> indexes;

indexes.push_back(index);

arrayIndexOutOfBoundsError(tok->tokAt(varc), arrayInfo, indexes);

}

}

// If the result of pointer arithmetic means that the pointer is

// out of bounds then this flag will be set.

bool pointerIsOutOfBounds = false;

for (const Token* const end = tok->scope()->classEnd; tok != end; tok = tok->next()) {

if (varid != 0 && Token::Match(tok, "%varid% = new|malloc|realloc", varid)) {

// Abort

break;

}

// reassign buffer

if (varid > 0 && Token::Match(tok, "[;{}] %varid% = %any%", varid)) {

// using varid .. bailout

if (tok->tokAt(3)->varId() != varid)

break;

pointerIsOutOfBounds = false;

}

// Array index..

if ((varid > 0 && ((tok->str() == "return" || (!tok->isName() && !Token::Match(tok, "[.&]"))) && Token::Match(tok->next(), "%varid% [ %num% ]", varid))) ||

(varid == 0 && ((tok->str() == "return" || (!tok->isName() && !Token::Match(tok, "[.&]"))) && Token::Match(tok->next(), (varnames + " [ %num% ]").c_str())))) {

std::vector<MathLib::bigint> indexes;

const Token *tok2 = tok->tokAt(2 + varc);

for (; Token::Match(tok2, "[ %num% ]"); tok2 = tok2->tokAt(3)) {

const MathLib::bigint index = MathLib::toLongNumber(tok2->strAt(1));

indexes.push_back(index);

}

if (indexes.size() == arrayInfo.num().size()) {

// Check if the indexes point outside the whole array..

// char a[10][10];

// a[0][20] <-- ok.

// a[9][20] <-- error.

// total number of elements of array..

MathLib::bigint totalElements = 1;

// total index..

MathLib::bigint totalIndex = 0;

// calculate the totalElements and totalIndex..

for (unsigned int i = 0; i < indexes.size(); ++i) {

std::size_t ri = indexes.size() - 1 - i;

totalIndex += indexes[ri] * totalElements;

totalElements *= arrayInfo.num(ri);

}

// totalElements == 0 => Unknown size

if (totalElements == 0)

continue;

const Token *tok3 = tok->previous();

while (tok3 && Token::Match(tok3->previous(), "%var% ."))

tok3 = tok3->tokAt(-2);

// just taking the address?

const bool addr(tok3 && (tok3->str() == "&" ||

Token::simpleMatch(tok3->previous(), "& (")));

// taking address of 1 past end?

if (addr && totalIndex == totalElements)

continue;

// Is totalIndex in bounds?

if (totalIndex > totalElements || totalIndex < 0) {

arrayIndexOutOfBoundsError(tok->tokAt(1 + varc), arrayInfo, indexes);

}

// Is any array index out of bounds?

else {

// check each index for overflow

for (unsigned int i = 0; i < indexes.size(); ++i) {

if (indexes[i] >= arrayInfo.num(i)) {

if (indexes.size() == 1U) {

arrayIndexOutOfBoundsError(tok->tokAt(1 + varc), arrayInfo, indexes);

break; // only warn about the first one

}

// The access is still within the memory range for the array

// so it may be intentional.

else if (_settings->inconclusive) {

arrayIndexOutOfBoundsError(tok->tokAt(1 + varc), arrayInfo, indexes);

break; // only warn about the first one

}

}

}

}

}

tok = tok2;

continue;

}

// memset, memcmp, memcpy, strncpy, fgets..

if (varid == 0 && size > 0) {

std::list<const Token *> callstack;

callstack.push_back(tok);

if (Token::Match(tok, ("%var% ( " + varnames + " ,").c_str()))

checkFunctionParameter(*tok, 1, arrayInfo, callstack);

if (Token::Match(tok, ("%var% ( %var% , " + varnames + " ,").c_str()))

checkFunctionParameter(*tok, 2, arrayInfo, callstack);

}

// Loop..

if (Token::simpleMatch(tok, "for (")) {

const ArrayInfo arrayInfo1(varid, varnames, (unsigned int)size, (unsigned int)total_size);

bool bailout = false;

checkScopeForBody(tok, arrayInfo1, bailout);

if (bailout)

break;

continue;

}

// Writing data into array..

if ((varid > 0 && Token::Match(tok, "strcpy|strcat ( %varid% , %str% )", varid)) ||

(varid == 0 && Token::Match(tok, ("strcpy|strcat ( " + varnames + " , %str% )").c_str()))) {

const std::size_t len = Token::getStrLength(tok->tokAt(varc + 4));

if (total_size > 0 && len >= (unsigned int)total_size) {

bufferOverrunError(tok, varid > 0 ? std::string("") : varnames);

continue;

}

} else if ((varid > 0 && Token::Match(tok, "strcpy|strcat ( %varid% , %var% )", varid)) ||

(varid == 0 && Token::Match(tok, ("strcpy|strcat ( " + varnames + " , %var% )").c_str()))) {

const Variable *var = _tokenizer->getSymbolDatabase()->getVariableFromVarId(tok->tokAt(4)->varId());

if (var && var->isArray() && var->dimensions().size() == 1) {

const std::size_t len = (std::size_t)var->dimension(0);

if (total_size > 0 && len > (unsigned int)total_size) {

if (_settings->inconclusive)

possibleBufferOverrunError(tok, tok->strAt(4), tok->strAt(2), tok->str() == "strcat");

continue;

}

}

}

// Detect few strcat() calls

const std::string strcatPattern = varid > 0 ? std::string("strcat ( %varid% , %str% ) ;") : ("strcat ( " + varnames + " , %str% ) ;");

if (Token::Match(tok, strcatPattern.c_str(), varid)) {

std::size_t charactersAppend = 0;

const Token *tok2 = tok;

while (tok2 && Token::Match(tok2, strcatPattern.c_str(), varid)) {

charactersAppend += Token::getStrLength(tok2->tokAt(4 + varc));

if (charactersAppend >= static_cast<std::size_t>(total_size)) {

bufferOverrunError(tok2);

break;

}

tok2 = tok2->tokAt(7 + varc);

}

}

// sprintf..

// TODO: change total_size to an unsigned value and remove the "&& total_size > 0" check.

const std::string sprintfPattern = varid > 0 ? std::string("sprintf ( %varid% , %str% [,)]") : ("sprintf ( " + varnames + " , %str% [,)]");

if (Token::Match(tok, sprintfPattern.c_str(), varid) && total_size > 0) {

checkSprintfCall(tok, static_cast<unsigned int>(total_size));

}

// snprintf..

const std::string snprintfPattern = varid > 0 ? std::string("snprintf ( %varid% , %num% ,") : ("snprintf ( " + varnames + " , %num% ,");

if (Token::Match(tok, snprintfPattern.c_str(), varid)) {

const MathLib::bigint n = MathLib::toLongNumber(tok->strAt(4 + varc));

if (n > total_size)

outOfBoundsError(tok->tokAt(4 + varc), "snprintf size", true, n, total_size);

}

// Check function call..

if (Token::Match(tok, "%var% (") && total_size > 0) {

// No varid => function calls are not handled

if (varid == 0)

continue;