ArrayBoundCheckerV2.cpp | Explore in Territory

//== ArrayBoundCheckerV2.cpp ------------------------------------*- C++ -*--==//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file defines ArrayBoundCheckerV2, which is a path-sensitive check
// which looks for an out-of-bound array element access.
//
//===----------------------------------------------------------------------===//

#include "clang/AST/CharUnits.h"
#include "clang/AST/ParentMapContext.h"
#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
#include "clang/StaticAnalyzer/Checkers/Taint.h"
#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
#include "clang/StaticAnalyzer/Core/Checker.h"
#include "clang/StaticAnalyzer/Core/CheckerManager.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
#include "llvm/ADT/SmallString.h"
#include "llvm/Support/FormatVariadic.h"
#include "llvm/Support/raw_ostream.h"
#include <optional>

usingnamespaceclang;
usingnamespaceento;
usingnamespacetaint;
formatv;

namespace {
/// If `E` is a "clean" array subscript expression, return the type of the
/// accessed element. If the base of the subscript expression is modified by
/// pointer arithmetic (and not the beginning of a "full" memory region), this
/// always returns nullopt because that's the right (or the least bad) thing to
/// do for the diagnostic output that's relying on this.
static std::optional<QualType> determineElementType(const Expr *E,
                                                    const CheckerContext &C) { … }

static std::optional<int64_t>
determineElementSize(const std::optional<QualType> T, const CheckerContext &C) { … }

class StateUpdateReporter { … };

struct Messages { … };

// NOTE: The `ArraySubscriptExpr` and `UnaryOperator` callbacks are `PostStmt`
// instead of `PreStmt` because the current implementation passes the whole
// expression to `CheckerContext::getSVal()` which only works after the
// symbolic evaluation of the expression. (To turn them into `PreStmt`
// callbacks, we'd need to duplicate the logic that evaluates these
// expressions.) The `MemberExpr` callback would work as `PreStmt` but it's
// defined as `PostStmt` for the sake of consistency with the other callbacks.
class ArrayBoundCheckerV2 : public Checker<check::PostStmt<ArraySubscriptExpr>,
                                           check::PostStmt<UnaryOperator>,
                                           check::PostStmt<MemberExpr>> { … };

} // anonymous namespace

/// For a given Location that can be represented as a symbolic expression
/// Arr[Idx] (or perhaps Arr[Idx1][Idx2] etc.), return the parent memory block
/// Arr and the distance of Location from the beginning of Arr (expressed in a
/// NonLoc that specifies the number of CharUnits). Returns nullopt when these
/// cannot be determined.
static std::optional<std::pair<const SubRegion *, NonLoc>>
computeOffset(ProgramStateRef State, SValBuilder &SVB, SVal Location) { … }

// NOTE: This function is the "heart" of this checker. It simplifies
// inequalities with transformations that are valid (and very elementary) in
// pure mathematics, but become invalid if we use them in C++ number model
// where the calculations may overflow.
// Due to the overflow issues I think it's impossible (or at least not
// practical) to integrate this kind of simplification into the resolution of
// arbitrary inequalities (i.e. the code of `evalBinOp`); but this function
// produces valid results when the calculations are handling memory offsets
// and every value is well below SIZE_MAX.
// TODO: This algorithm should be moved to a central location where it's
// available for other checkers that need to compare memory offsets.
// NOTE: the simplification preserves the order of the two operands in a
// mathematical sense, but it may change the result produced by a C++
// comparison operator (and the automatic type conversions).
// For example, consider a comparison "X+1 < 0", where the LHS is stored as a
// size_t and the RHS is stored in an int. (As size_t is unsigned, this
// comparison is false for all values of "X".) However, the simplification may
// turn it into "X < -1", which is still always false in a mathematical sense,
// but can produce a true result when evaluated by `evalBinOp` (which follows
// the rules of C++ and casts -1 to SIZE_MAX).
static std::pair<NonLoc, nonloc::ConcreteInt>
getSimplifiedOffsets(NonLoc offset, nonloc::ConcreteInt extent,
                     SValBuilder &svalBuilder) { … }

static bool isNegative(SValBuilder &SVB, ProgramStateRef State, NonLoc Value) { … }

static bool isUnsigned(SValBuilder &SVB, NonLoc Value) { … }

// Evaluate the comparison Value < Threshold with the help of the custom
// simplification algorithm defined for this checker. Return a pair of states,
// where the first one corresponds to "value below threshold" and the second
// corresponds to "value at or above threshold". Returns {nullptr, nullptr} in
// the case when the evaluation fails.
// If the optional argument CheckEquality is true, then use BO_EQ instead of
// the default BO_LT after consistently applying the same simplification steps.
static std::pair<ProgramStateRef, ProgramStateRef>
compareValueToThreshold(ProgramStateRef State, NonLoc Value, NonLoc Threshold,
                        SValBuilder &SVB, bool CheckEquality = false) { … }

static std::string getRegionName(const SubRegion *Region) { … }

static std::optional<int64_t> getConcreteValue(NonLoc SV) { … }

static std::optional<int64_t> getConcreteValue(std::optional<NonLoc> SV) { … }

static Messages getPrecedesMsgs(const SubRegion *Region, NonLoc Offset) { … }

/// Try to divide `Val1` and `Val2` (in place) by `Divisor` and return true if
/// it can be performed (`Divisor` is nonzero and there is no remainder). The
/// values `Val1` and `Val2` may be nullopt and in that case the corresponding
/// division is considered to be successful.
static bool tryDividePair(std::optional<int64_t> &Val1,
                          std::optional<int64_t> &Val2, int64_t Divisor) { … }

static Messages getExceedsMsgs(ASTContext &ACtx, const SubRegion *Region,
                               NonLoc Offset, NonLoc Extent, SVal Location,
                               bool AlsoMentionUnderflow) { … }

static Messages getTaintMsgs(const SubRegion *Region, const char *OffsetName,
                             bool AlsoMentionUnderflow) { … }

const NoteTag *StateUpdateReporter::createNoteTag(CheckerContext &C) const { … }

std::string StateUpdateReporter::getMessage(PathSensitiveBugReport &BR) const { … }

bool StateUpdateReporter::providesInformationAboutInteresting(
    SymbolRef Sym, PathSensitiveBugReport &BR) { … }

void ArrayBoundCheckerV2::performCheck(const Expr *E, CheckerContext &C) const { … }

void ArrayBoundCheckerV2::markPartsInteresting(PathSensitiveBugReport &BR,
                                               ProgramStateRef ErrorState,
                                               NonLoc Val, bool MarkTaint) { … }

void ArrayBoundCheckerV2::reportOOB(CheckerContext &C,
                                    ProgramStateRef ErrorState, Messages Msgs,
                                    NonLoc Offset, std::optional<NonLoc> Extent,
                                    bool IsTaintBug /*=false*/) const { … }

bool ArrayBoundCheckerV2::isFromCtypeMacro(const Stmt *S, ASTContext &ACtx) { … }

bool ArrayBoundCheckerV2::isInAddressOf(const Stmt *S, ASTContext &ACtx) { … }

bool ArrayBoundCheckerV2::isIdiomaticPastTheEndPtr(const Expr *E,
                                                   ProgramStateRef State,
                                                   NonLoc Offset, NonLoc Limit,
                                                   CheckerContext &C) { … }

void ento::registerArrayBoundCheckerV2(CheckerManager &mgr) { … }

bool ento::shouldRegisterArrayBoundCheckerV2(const CheckerManager &mgr) { … }
llvm/clang/lib/StaticAnalyzer/Checkers/ArrayBoundCheckerV2.cpp
