diff options
author | Dimitry Andric <dim@FreeBSD.org> | 2020-01-17 20:45:01 +0000 |
---|---|---|
committer | Dimitry Andric <dim@FreeBSD.org> | 2020-01-17 20:45:01 +0000 |
commit | 706b4fc47bbc608932d3b491ae19a3b9cde9497b (patch) | |
tree | 4adf86a776049cbf7f69a1929c4babcbbef925eb /clang/lib/StaticAnalyzer/Checkers/IteratorRangeChecker.cpp | |
parent | 7cc9cf2bf09f069cb2dd947ead05d0b54301fb71 (diff) | |
download | src-706b4fc47bbc608932d3b491ae19a3b9cde9497b.tar.gz src-706b4fc47bbc608932d3b491ae19a3b9cde9497b.zip |
Vendor import of llvm-project master e26a78e70, the last commit beforevendor/llvm-project/llvmorg-10-init-17466-ge26a78e7085
the llvmorg-11-init tag, from which release/10.x was branched.
Notes
Notes:
svn path=/vendor/llvm-project/master/; revision=356843
svn path=/vendor/llvm-project/llvmorg-10-init-17466-ge26a78e7085/; revision=356844; tag=vendor/llvm-project/llvmorg-10-init-17466-ge26a78e7085
Diffstat (limited to 'clang/lib/StaticAnalyzer/Checkers/IteratorRangeChecker.cpp')
-rw-r--r-- | clang/lib/StaticAnalyzer/Checkers/IteratorRangeChecker.cpp | 273 |
1 files changed, 273 insertions, 0 deletions
diff --git a/clang/lib/StaticAnalyzer/Checkers/IteratorRangeChecker.cpp b/clang/lib/StaticAnalyzer/Checkers/IteratorRangeChecker.cpp new file mode 100644 index 000000000000..bd8b84d464b6 --- /dev/null +++ b/clang/lib/StaticAnalyzer/Checkers/IteratorRangeChecker.cpp @@ -0,0 +1,273 @@ +//===-- IteratorRangeChecker.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 checker for dereference of the past-the-end iterator and +// out-of-range increments and decrements. +// +//===----------------------------------------------------------------------===// + +#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h" +#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" +#include "clang/StaticAnalyzer/Core/Checker.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" + + +#include "Iterator.h" + +using namespace clang; +using namespace ento; +using namespace iterator; + +namespace { + +class IteratorRangeChecker + : public Checker<check::PreCall> { + + std::unique_ptr<BugType> OutOfRangeBugType; + + void verifyDereference(CheckerContext &C, const SVal &Val) const; + void verifyIncrement(CheckerContext &C, const SVal &Iter) const; + void verifyDecrement(CheckerContext &C, const SVal &Iter) const; + void verifyRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op, + const SVal &LHS, const SVal &RHS) const; + void reportBug(const StringRef &Message, const SVal &Val, + CheckerContext &C, ExplodedNode *ErrNode) const; +public: + IteratorRangeChecker(); + + void checkPreCall(const CallEvent &Call, CheckerContext &C) const; + +}; + +bool isPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos); +bool isAheadOfRange(ProgramStateRef State, const IteratorPosition &Pos); +bool isBehindPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos); +bool isZero(ProgramStateRef State, const NonLoc &Val); + +} //namespace + +IteratorRangeChecker::IteratorRangeChecker() { + OutOfRangeBugType.reset( + new BugType(this, "Iterator out of range", "Misuse of STL APIs")); +} + +void IteratorRangeChecker::checkPreCall(const CallEvent &Call, + CheckerContext &C) const { + // Check for out of range access + const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl()); + if (!Func) + return; + + if (Func->isOverloadedOperator()) { + if (isIncrementOperator(Func->getOverloadedOperator())) { + // Check for out-of-range incrementions + if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) { + verifyIncrement(C, InstCall->getCXXThisVal()); + } else { + if (Call.getNumArgs() >= 1) { + verifyIncrement(C, Call.getArgSVal(0)); + } + } + } else if (isDecrementOperator(Func->getOverloadedOperator())) { + // Check for out-of-range decrementions + if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) { + verifyDecrement(C, InstCall->getCXXThisVal()); + } else { + if (Call.getNumArgs() >= 1) { + verifyDecrement(C, Call.getArgSVal(0)); + } + } + } else if (isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) { + if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) { + // Check for out-of-range incrementions and decrementions + if (Call.getNumArgs() >= 1 && + Call.getArgExpr(0)->getType()->isIntegralOrEnumerationType()) { + verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(), + InstCall->getCXXThisVal(), + Call.getArgSVal(0)); + } + } else { + if (Call.getNumArgs() >= 2 && + Call.getArgExpr(1)->getType()->isIntegralOrEnumerationType()) { + verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(), + Call.getArgSVal(0), Call.getArgSVal(1)); + } + } + } else if (isDereferenceOperator(Func->getOverloadedOperator())) { + // Check for dereference of out-of-range iterators + if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) { + verifyDereference(C, InstCall->getCXXThisVal()); + } else { + verifyDereference(C, Call.getArgSVal(0)); + } + } + } +} + +void IteratorRangeChecker::verifyDereference(CheckerContext &C, + const SVal &Val) const { + auto State = C.getState(); + const auto *Pos = getIteratorPosition(State, Val); + if (Pos && isPastTheEnd(State, *Pos)) { + auto *N = C.generateErrorNode(State); + if (!N) + return; + reportBug("Past-the-end iterator dereferenced.", Val, C, N); + return; + } +} + +void IteratorRangeChecker::verifyIncrement(CheckerContext &C, + const SVal &Iter) const { + auto &BVF = C.getSValBuilder().getBasicValueFactory(); + verifyRandomIncrOrDecr(C, OO_Plus, Iter, + nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1)))); +} + +void IteratorRangeChecker::verifyDecrement(CheckerContext &C, + const SVal &Iter) const { + auto &BVF = C.getSValBuilder().getBasicValueFactory(); + verifyRandomIncrOrDecr(C, OO_Minus, Iter, + nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1)))); +} + +void IteratorRangeChecker::verifyRandomIncrOrDecr(CheckerContext &C, + OverloadedOperatorKind Op, + const SVal &LHS, + const SVal &RHS) const { + auto State = C.getState(); + + auto Value = RHS; + if (auto ValAsLoc = RHS.getAs<Loc>()) { + Value = State->getRawSVal(*ValAsLoc); + } + + if (Value.isUnknown()) + return; + + // Incremention or decremention by 0 is never a bug. + if (isZero(State, Value.castAs<NonLoc>())) + return; + + // The result may be the past-end iterator of the container, but any other + // out of range position is undefined behaviour + auto StateAfter = advancePosition(State, LHS, Op, Value); + if (!StateAfter) + return; + + const auto *PosAfter = getIteratorPosition(StateAfter, LHS); + assert(PosAfter && + "Iterator should have position after successful advancement"); + if (isAheadOfRange(State, *PosAfter)) { + auto *N = C.generateErrorNode(State); + if (!N) + return; + reportBug("Iterator decremented ahead of its valid range.", LHS, + C, N); + } + if (isBehindPastTheEnd(State, *PosAfter)) { + auto *N = C.generateErrorNode(State); + if (!N) + return; + reportBug("Iterator incremented behind the past-the-end " + "iterator.", LHS, C, N); + } +} + +void IteratorRangeChecker::reportBug(const StringRef &Message, + const SVal &Val, CheckerContext &C, + ExplodedNode *ErrNode) const { + auto R = std::make_unique<PathSensitiveBugReport>(*OutOfRangeBugType, Message, + ErrNode); + R->markInteresting(Val); + C.emitReport(std::move(R)); +} + +namespace { + +bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2); +bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2); +bool isEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2); + +bool isZero(ProgramStateRef State, const NonLoc &Val) { + auto &BVF = State->getBasicVals(); + return compare(State, Val, + nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0))), + BO_EQ); +} + +bool isPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos) { + const auto *Cont = Pos.getContainer(); + const auto *CData = getContainerData(State, Cont); + if (!CData) + return false; + + const auto End = CData->getEnd(); + if (End) { + if (isEqual(State, Pos.getOffset(), End)) { + return true; + } + } + + return false; +} + +bool isAheadOfRange(ProgramStateRef State, const IteratorPosition &Pos) { + const auto *Cont = Pos.getContainer(); + const auto *CData = getContainerData(State, Cont); + if (!CData) + return false; + + const auto Beg = CData->getBegin(); + if (Beg) { + if (isLess(State, Pos.getOffset(), Beg)) { + return true; + } + } + + return false; +} + +bool isBehindPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos) { + const auto *Cont = Pos.getContainer(); + const auto *CData = getContainerData(State, Cont); + if (!CData) + return false; + + const auto End = CData->getEnd(); + if (End) { + if (isGreater(State, Pos.getOffset(), End)) { + return true; + } + } + + return false; +} + +bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) { + return compare(State, Sym1, Sym2, BO_LT); +} + +bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) { + return compare(State, Sym1, Sym2, BO_GT); +} + +bool isEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) { + return compare(State, Sym1, Sym2, BO_EQ); +} + +} // namespace + +void ento::registerIteratorRangeChecker(CheckerManager &mgr) { + mgr.registerChecker<IteratorRangeChecker>(); +} + +bool ento::shouldRegisterIteratorRangeChecker(const LangOptions &LO) { + return true; +} |