IteratorModeling.cpp | Explore in Territory

//===-- IteratorModeling.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
//
//===----------------------------------------------------------------------===//
//
// Defines a modeling-checker for modeling STL iterator-like iterators.
//
//===----------------------------------------------------------------------===//
//
// In the code, iterator can be represented as a:
// * type-I: typedef-ed pointer. Operations over such iterator, such as
//           comparisons or increments, are modeled straightforwardly by the
//           analyzer.
// * type-II: structure with its method bodies available.  Operations over such
//            iterator are inlined by the analyzer, and results of modeling
//            these operations are exposing implementation details of the
//            iterators, which is not necessarily helping.
// * type-III: completely opaque structure. Operations over such iterator are
//             modeled conservatively, producing conjured symbols everywhere.
//
// To handle all these types in a common way we introduce a structure called
// IteratorPosition which is an abstraction of the position the iterator
// represents using symbolic expressions. The checker handles all the
// operations on this structure.
//
// Additionally, depending on the circumstances, operators of types II and III
// can be represented as:
// * type-IIa, type-IIIa: conjured structure symbols - when returned by value
//                        from conservatively evaluated methods such as
//                        `.begin()`.
// * type-IIb, type-IIIb: memory regions of iterator-typed objects, such as
//                        variables or temporaries, when the iterator object is
//                        currently treated as an lvalue.
// * type-IIc, type-IIIc: compound values of iterator-typed objects, when the
//                        iterator object is treated as an rvalue taken of a
//                        particular lvalue, eg. a copy of "type-a" iterator
//                        object, or an iterator that existed before the
//                        analysis has started.
//
// To handle any of these three different representations stored in an SVal we
// use setter and getters functions which separate the three cases. To store
// them we use a pointer union of symbol and memory region.
//
// The checker works the following way: We record the begin and the
// past-end iterator for all containers whenever their `.begin()` and `.end()`
// are called. Since the Constraint Manager cannot handle such SVals we need
// to take over its role. We post-check equality and non-equality comparisons
// and record that the two sides are equal if we are in the 'equal' branch
// (true-branch for `==` and false-branch for `!=`).
//
// In case of type-I or type-II iterators we get a concrete integer as a result
// of the comparison (1 or 0) but in case of type-III we only get a Symbol. In
// this latter case we record the symbol and reload it in evalAssume() and do
// the propagation there. We also handle (maybe double) negated comparisons
// which are represented in the form of (x == 0 or x != 0) where x is the
// comparison itself.
//
// Since `SimpleConstraintManager` cannot handle complex symbolic expressions
// we only use expressions of the format S, S+n or S-n for iterator positions
// where S is a conjured symbol and n is an unsigned concrete integer. When
// making an assumption e.g. `S1 + n == S2 + m` we store `S1 - S2 == m - n` as
// a constraint which we later retrieve when doing an actual comparison.

#include "clang/AST/DeclTemplate.h"
#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
#include "clang/StaticAnalyzer/Core/Checker.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h"
#include "llvm/ADT/STLExtras.h"

#include "Iterator.h"

#include <utility>

usingnamespaceclang;
usingnamespaceento;
usingnamespaceiterator;

namespace {

class IteratorModeling
    : public Checker<check::PostCall, check::PostStmt<UnaryOperator>,
                     check::PostStmt<BinaryOperator>,
                     check::PostStmt<MaterializeTemporaryExpr>,
                     check::Bind, check::LiveSymbols, check::DeadSymbols> { … };

bool isSimpleComparisonOperator(OverloadedOperatorKind OK);
bool isSimpleComparisonOperator(BinaryOperatorKind OK);
ProgramStateRef removeIteratorPosition(ProgramStateRef State, SVal Val);
ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1,
                              SymbolRef Sym2, bool Equal);
bool isBoundThroughLazyCompoundVal(const Environment &Env,
                                   const MemRegion *Reg);
const ExplodedNode *findCallEnter(const ExplodedNode *Node, const Expr *Call);

} // namespace

void IteratorModeling::checkPostCall(const CallEvent &Call,
                                     CheckerContext &C) const { … }

void IteratorModeling::checkBind(SVal Loc, SVal Val, const Stmt *S,
                                 CheckerContext &C) const { … }

void IteratorModeling::checkPostStmt(const UnaryOperator *UO,
                                     CheckerContext &C) const { … }

void IteratorModeling::checkPostStmt(const BinaryOperator *BO,
                                     CheckerContext &C) const { … }

void IteratorModeling::checkPostStmt(const MaterializeTemporaryExpr *MTE,
                                     CheckerContext &C) const { … }

void IteratorModeling::checkLiveSymbols(ProgramStateRef State,
                                        SymbolReaper &SR) const { … }

void IteratorModeling::checkDeadSymbols(SymbolReaper &SR,
                                        CheckerContext &C) const { … }

void
IteratorModeling::handleOverloadedOperator(CheckerContext &C,
                                           const CallEvent &Call,
                                           OverloadedOperatorKind Op) const { … }

void
IteratorModeling::handleAdvanceLikeFunction(CheckerContext &C,
                                            const CallEvent &Call,
                                            const Expr *OrigExpr,
                                            const AdvanceFn *Handler) const { … }

void IteratorModeling::handleComparison(CheckerContext &C, const Expr *CE,
                                        SVal RetVal, SVal LVal, SVal RVal,
                                        OverloadedOperatorKind Op) const { … }

void IteratorModeling::processComparison(CheckerContext &C,
                                         ProgramStateRef State, SymbolRef Sym1,
                                         SymbolRef Sym2, SVal RetVal,
                                         OverloadedOperatorKind Op) const { … }

void IteratorModeling::handleIncrement(CheckerContext &C, SVal RetVal,
                                       SVal Iter, bool Postfix) const { … }

void IteratorModeling::handleDecrement(CheckerContext &C, SVal RetVal,
                                       SVal Iter, bool Postfix) const { … }

void IteratorModeling::handleRandomIncrOrDecr(CheckerContext &C, const Expr *CE,
                                              OverloadedOperatorKind Op,
                                              SVal RetVal, SVal Iterator,
                                              SVal Amount) const { … }

void IteratorModeling::handlePtrIncrOrDecr(CheckerContext &C,
                                           const Expr *Iterator,
                                           OverloadedOperatorKind OK,
                                           SVal Offset) const { … }

void IteratorModeling::handleAdvance(CheckerContext &C, const Expr *CE,
                                     SVal RetVal, SVal Iter,
                                     SVal Amount) const { … }

void IteratorModeling::handlePrev(CheckerContext &C, const Expr *CE,
                                  SVal RetVal, SVal Iter, SVal Amount) const { … }

void IteratorModeling::handleNext(CheckerContext &C, const Expr *CE,
                                  SVal RetVal, SVal Iter, SVal Amount) const { … }

void IteratorModeling::assignToContainer(CheckerContext &C, const Expr *CE,
                                         SVal RetVal,
                                         const MemRegion *Cont) const { … }

bool IteratorModeling::noChangeInAdvance(CheckerContext &C, SVal Iter,
                                         const Expr *CE) const { … }

void IteratorModeling::printState(raw_ostream &Out, ProgramStateRef State,
                                  const char *NL, const char *Sep) const { … }

namespace {

bool isSimpleComparisonOperator(OverloadedOperatorKind OK) { … }

bool isSimpleComparisonOperator(BinaryOperatorKind OK) { … }

ProgramStateRef removeIteratorPosition(ProgramStateRef State, SVal Val) { … }

ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1,
                              SymbolRef Sym2, bool Equal) { … }

bool isBoundThroughLazyCompoundVal(const Environment &Env,
                                   const MemRegion *Reg) { … }

const ExplodedNode *findCallEnter(const ExplodedNode *Node, const Expr *Call) { … }

} // namespace

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

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