Index: include/clang/StaticAnalyzer/Checkers/Checkers.td =================================================================== --- include/clang/StaticAnalyzer/Checkers/Checkers.td +++ include/clang/StaticAnalyzer/Checkers/Checkers.td @@ -313,6 +313,10 @@ HelpText<"Check for iterators used outside their valid ranges">, DescFile<"IteratorChecker.cpp">; +def InvalidatedIteratorChecker : Checker<"InvalidatedIterator">, + HelpText<"Check for use of invalidated iterators">, + DescFile<"IteratorChecker.cpp">; + def MisusedMovedObjectChecker: Checker<"MisusedMovedObject">, HelpText<"Method calls on a moved-from object and copying a moved-from " "object will be reported">, Index: lib/StaticAnalyzer/Checkers/IteratorChecker.cpp =================================================================== --- lib/StaticAnalyzer/Checkers/IteratorChecker.cpp +++ lib/StaticAnalyzer/Checkers/IteratorChecker.cpp @@ -67,11 +67,14 @@ // a constraint which we later retrieve when doing an actual comparison. #include "ClangSACheckers.h" +#include "clang/AST/DeclTemplate.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 + using namespace clang; using namespace ento; @@ -85,34 +88,43 @@ // Container the iterator belongs to const MemRegion *Cont; + // Whether iterator is valid + const bool Valid; + // Abstract offset const SymbolRef Offset; - IteratorPosition(const MemRegion *C, SymbolRef Of) - : Cont(C), Offset(Of) {} + IteratorPosition(const MemRegion *C, bool V, SymbolRef Of) + : Cont(C), Valid(V), Offset(Of) {} public: const MemRegion *getContainer() const { return Cont; } + bool isValid() const { return Valid; } SymbolRef getOffset() const { return Offset; } + IteratorPosition invalidate() const { + return IteratorPosition(Cont, false, Offset); + } + static IteratorPosition getPosition(const MemRegion *C, SymbolRef Of) { - return IteratorPosition(C, Of); + return IteratorPosition(C, true, Of); } IteratorPosition setTo(SymbolRef NewOf) const { - return IteratorPosition(Cont, NewOf); + return IteratorPosition(Cont, Valid, NewOf); } bool operator==(const IteratorPosition &X) const { - return Cont == X.Cont && Offset == X.Offset; + return Cont == X.Cont && Valid == X.Valid && Offset == X.Offset; } bool operator!=(const IteratorPosition &X) const { - return Cont != X.Cont || Offset != X.Offset; + return Cont != X.Cont || Valid != X.Valid || Offset != X.Offset; } void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddPointer(Cont); + ID.AddInteger(Valid); ID.Add(Offset); } }; @@ -181,15 +193,16 @@ class IteratorChecker : public Checker, check::PostStmt, check::LiveSymbols, check::DeadSymbols, eval::Assume> { std::unique_ptr OutOfRangeBugType; + std::unique_ptr InvalidatedBugType; void handleComparison(CheckerContext &C, const SVal &RetVal, const SVal &LVal, const SVal &RVal, OverloadedOperatorKind Op) const; + void verifyAccess(CheckerContext &C, const SVal &Val) const; void verifyDereference(CheckerContext &C, const SVal &Val) const; void handleIncrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter, bool Postfix) const; @@ -204,17 +217,21 @@ const SVal &Cont) const; void assignToContainer(CheckerContext &C, const Expr *CE, const SVal &RetVal, const MemRegion *Cont) const; + void handleAssign(CheckerContext &C, const SVal &Cont) const; void verifyRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op, const SVal &RetVal, const SVal &LHS, const SVal &RHS) const; void reportOutOfRangeBug(const StringRef &Message, const SVal &Val, CheckerContext &C, ExplodedNode *ErrNode) const; + void reportInvalidatedBug(const StringRef &Message, const SVal &Val, + CheckerContext &C, ExplodedNode *ErrNode) const; public: IteratorChecker(); enum CheckKind { CK_IteratorRangeChecker, + CK_InvalidatedIteratorChecker, CK_NumCheckKinds }; @@ -223,7 +240,6 @@ void checkPreCall(const CallEvent &Call, CheckerContext &C) const; void checkPostCall(const CallEvent &Call, CheckerContext &C) const; - void checkPreStmt(const CXXOperatorCallExpr *COCE, CheckerContext &C) const; void checkPostStmt(const MaterializeTemporaryExpr *MTE, CheckerContext &C) const; void checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const; @@ -248,7 +264,9 @@ bool isIterator(const CXXRecordDecl *CRD); bool isBeginCall(const FunctionDecl *Func); bool isEndCall(const FunctionDecl *Func); +bool isAssignmentOperator(OverloadedOperatorKind OK); bool isSimpleComparisonOperator(OverloadedOperatorKind OK); +bool isAccessOperator(OverloadedOperatorKind OK); bool isDereferenceOperator(OverloadedOperatorKind OK); bool isIncrementOperator(OverloadedOperatorKind OK); bool isDecrementOperator(OverloadedOperatorKind OK); @@ -287,6 +305,8 @@ const IteratorPosition &Pos1, const IteratorPosition &Pos2, bool Equal); +ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State, + const MemRegion *Cont); const ContainerData *getContainerData(ProgramStateRef State, const MemRegion *Cont); ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont, @@ -300,16 +320,29 @@ OutOfRangeBugType.reset( new BugType(this, "Iterator out of range", "Misuse of STL APIs")); OutOfRangeBugType->setSuppressOnSink(true); + InvalidatedBugType.reset( + new BugType(this, "Iterator invalidated", "Misuse of STL APIs")); + InvalidatedBugType->setSuppressOnSink(true); } void IteratorChecker::checkPreCall(const CallEvent &Call, CheckerContext &C) const { - // Check for out of range access + // Check for out of range access or access of invalidated position and + // iterator mismatches const auto *Func = dyn_cast_or_null(Call.getDecl()); if (!Func) return; if (Func->isOverloadedOperator()) { + if (ChecksEnabled[CK_InvalidatedIteratorChecker] && + isAccessOperator(Func->getOverloadedOperator())) { + // Check for any kind of access of invalidated iterator positions + if (const auto *InstCall = dyn_cast(&Call)) { + verifyAccess(C, InstCall->getCXXThisVal()); + } else { + verifyAccess(C, Call.getArgSVal(0)); + } + } if (ChecksEnabled[CK_IteratorRangeChecker] && isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) { if (const auto *InstCall = dyn_cast(&Call)) { @@ -347,7 +380,10 @@ if (Func->isOverloadedOperator()) { const auto Op = Func->getOverloadedOperator(); - if (isSimpleComparisonOperator(Op)) { + if (isAssignmentOperator(Op)) { + const auto *InstCall = dyn_cast(&Call); + handleAssign(C, InstCall->getCXXThisVal()); + } else if (isSimpleComparisonOperator(Op)) { if (const auto *InstCall = dyn_cast(&Call)) { handleComparison(C, Call.getReturnValue(), InstCall->getCXXThisVal(), Call.getArgSVal(0), Op); @@ -441,36 +477,6 @@ } } -void IteratorChecker::checkPreStmt(const CXXOperatorCallExpr *COCE, - CheckerContext &C) const { - const auto *ThisExpr = COCE->getArg(0); - - auto State = C.getState(); - const auto *LCtx = C.getLocationContext(); - - const auto CurrentThis = State->getSVal(ThisExpr, LCtx); - if (const auto *Reg = CurrentThis.getAsRegion()) { - if (!Reg->getAs()) - return; - const auto OldState = C.getPredecessor()->getFirstPred()->getState(); - const auto OldThis = OldState->getSVal(ThisExpr, LCtx); - // FIXME: This solution is unreliable. It may happen that another checker - // subscribes to the pre-statement check of `CXXOperatorCallExpr` - // and adds a transition before us. The proper fix is to make the - // CFG provide a `ConstructionContext` for the `CXXOperatorCallExpr`, - // which would turn the corresponding `CFGStmt` element into a - // `CFGCXXRecordTypedCall` element, which will allow `ExprEngine` to - // foresee that the `begin()`/`end()` call constructs the object - // directly in the temporary region that `CXXOperatorCallExpr` takes - // as its implicit object argument. - const auto *Pos = getIteratorPosition(OldState, OldThis); - if (!Pos) - return; - State = setIteratorPosition(State, CurrentThis, *Pos); - C.addTransition(State); - } -} - void IteratorChecker::checkPostStmt(const MaterializeTemporaryExpr *MTE, CheckerContext &C) const { /* Transfer iterator state to temporary objects */ @@ -624,16 +630,25 @@ auto State = C.getState(); const auto *Pos = getIteratorPosition(State, Val); if (Pos && isOutOfRange(State, *Pos)) { - // If I do not put a tag here, some range tests will fail - static CheckerProgramPointTag Tag("IteratorRangeChecker", - "IteratorOutOfRange"); - auto *N = C.generateNonFatalErrorNode(State, &Tag); + auto *N = C.generateNonFatalErrorNode(State); if (!N) return; reportOutOfRangeBug("Iterator accessed outside of its range.", Val, C, N); } } +void IteratorChecker::verifyAccess(CheckerContext &C, const SVal &Val) const { + auto State = C.getState(); + const auto *Pos = getIteratorPosition(State, Val); + if (Pos && !Pos->isValid()) { + auto *N = C.generateNonFatalErrorNode(State); + if (!N) { + return; + } + reportInvalidatedBug("Invalidated iterator accessed.", Val, C, N); + } +} + void IteratorChecker::handleIncrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter, bool Postfix) const { // Increment the symbolic expressions which represents the position of the @@ -874,6 +889,26 @@ C.addTransition(State); } +void IteratorChecker::handleAssign(CheckerContext &C, const SVal &Cont) const { + const auto *ContReg = Cont.getAsRegion(); + if (!ContReg) + return; + + while (const auto *CBOR = ContReg->getAs()) { + ContReg = CBOR->getSuperRegion(); + } + + // Assignment of a new value to a container always invalidates all its + // iterators + auto State = C.getState(); + const auto CData = getContainerData(State, ContReg); + if (CData) { + State = invalidateAllIteratorPositions(State, ContReg); + } + + C.addTransition(State); +} + void IteratorChecker::reportOutOfRangeBug(const StringRef &Message, const SVal &Val, CheckerContext &C, ExplodedNode *ErrNode) const { @@ -882,6 +917,14 @@ C.emitReport(std::move(R)); } +void IteratorChecker::reportInvalidatedBug(const StringRef &Message, + const SVal &Val, CheckerContext &C, + ExplodedNode *ErrNode) const { + auto R = llvm::make_unique(*InvalidatedBugType, Message, ErrNode); + R->markInteresting(Val); + C.emitReport(std::move(R)); +} + namespace { bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2); @@ -957,10 +1000,17 @@ return IdInfo->getName().endswith_lower("end"); } +bool isAssignmentOperator(OverloadedOperatorKind OK) { return OK == OO_Equal; } + bool isSimpleComparisonOperator(OverloadedOperatorKind OK) { return OK == OO_EqualEqual || OK == OO_ExclaimEqual; } +bool isAccessOperator(OverloadedOperatorKind OK) { + return isDereferenceOperator(OK) || isIncrementOperator(OK) || + isDecrementOperator(OK) || isRandomIncrOrDecrOperator(OK); +} + bool isDereferenceOperator(OverloadedOperatorKind OK) { return OK == OO_Star || OK == OO_Arrow || OK == OO_ArrowStar || OK == OO_Subscript; @@ -1211,6 +1261,49 @@ return false; } +template +ProgramStateRef processIteratorPositions(ProgramStateRef State, Condition Cond, + Process Proc) { + auto &RegionMapFactory = State->get_context(); + auto RegionMap = State->get(); + bool Changed = false; + for (const auto Reg : RegionMap) { + if (Cond(Reg.second)) { + RegionMap = RegionMapFactory.add(RegionMap, Reg.first, Proc(Reg.second)); + Changed = true; + } + } + + if (Changed) + State = State->set(RegionMap); + + auto &SymbolMapFactory = State->get_context(); + auto SymbolMap = State->get(); + Changed = false; + for (const auto Sym : SymbolMap) { + if (Cond(Sym.second)) { + SymbolMap = SymbolMapFactory.add(SymbolMap, Sym.first, Proc(Sym.second)); + Changed = true; + } + } + + if (Changed) + State = State->set(SymbolMap); + + return State; +} + +ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State, + const MemRegion *Cont) { + auto MatchCont = [&](const IteratorPosition &Pos) { + return Pos.getContainer() == Cont; + }; + auto Invalidate = [&](const IteratorPosition &Pos) { + return Pos.invalidate(); + }; + return processIteratorPositions(State, MatchCont, Invalidate); +} + bool isZero(ProgramStateRef State, const NonLoc &Val) { auto &BVF = State->getBasicVals(); return compare(State, Val, @@ -1281,4 +1374,4 @@ } REGISTER_CHECKER(IteratorRangeChecker) - +REGISTER_CHECKER(InvalidatedIteratorChecker) Index: test/Analysis/Inputs/system-header-simulator-cxx.h =================================================================== --- test/Analysis/Inputs/system-header-simulator-cxx.h +++ test/Analysis/Inputs/system-header-simulator-cxx.h @@ -252,6 +252,15 @@ return size_t(_finish - _start); } + vector& operator=(const vector &other); + vector& operator=(vector &&other); + vector& operator=(std::initializer_list ilist); + + void assign(size_type count, const T &value); + template + void assign(InputIterator first, InputIterator last); + void assign(std::initializer_list ilist); + void clear(); void push_back(const T &value); @@ -301,8 +310,21 @@ list& operator=(list &&other); list& operator=(std::initializer_list ilist); + void assign(size_type count, const T &value); + template + void assign(InputIterator first, InputIterator last); + void assign(std::initializer_list ilist); + void clear(); + void push_back(const T &value); + void push_back(T &&value); + void pop_back(); + + void push_front(const T &value); + void push_front(T &&value); + void pop_front(); + iterator begin() { return iterator(_start); } const_iterator begin() const { return const_iterator(_start); } const_iterator cbegin() const { return const_iterator(_start); } @@ -338,6 +360,15 @@ return size_t(_finish - _start); } + deque& operator=(const deque &other); + deque& operator=(deque &&other); + deque& operator=(std::initializer_list ilist); + + void assign(size_type count, const T &value); + template + void assign(InputIterator first, InputIterator last); + void assign(std::initializer_list ilist); + void clear(); void push_back(const T &value); @@ -351,11 +382,11 @@ T &operator[](size_t n) { return _start[n]; } - + const T &operator[](size_t n) const { return _start[n]; } - + iterator begin() { return iterator(_start); } const_iterator begin() const { return const_iterator(_start); } const_iterator cbegin() const { return const_iterator(_start); } @@ -367,7 +398,7 @@ T& back() { return *(end() - 1); } const T& back() const { return *(end() - 1); } }; - + template class forward_list { struct __item { @@ -387,6 +418,15 @@ forward_list(forward_list &&other); ~forward_list(); + forward_list& operator=(const forward_list &other); + forward_list& operator=(forward_list &&other); + forward_list& operator=(std::initializer_list ilist); + + void assign(size_type count, const T &value); + template + void assign(InputIterator first, InputIterator last); + void assign(std::initializer_list ilist); + void clear(); void push_front(const T &value); Index: test/Analysis/diagnostics/explicit-suppression.cpp =================================================================== --- test/Analysis/diagnostics/explicit-suppression.cpp +++ test/Analysis/diagnostics/explicit-suppression.cpp @@ -19,6 +19,6 @@ void testCopyNull(C *I, C *E) { std::copy(I, E, (C *)0); #ifndef SUPPRESSED - // expected-warning@../Inputs/system-header-simulator-cxx.h:514 {{Called C++ object pointer is null}} + // expected-warning@../Inputs/system-header-simulator-cxx.h:554 {{Called C++ object pointer is null}} #endif } Index: test/Analysis/invalidated-iterator.cpp =================================================================== --- test/Analysis/invalidated-iterator.cpp +++ test/Analysis/invalidated-iterator.cpp @@ -0,0 +1,32 @@ +// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.InvalidatedIterator -analyzer-eagerly-assume -analyzer-config aggressive-relational-comparison-simplification=true -analyzer-config c++-container-inlining=false %s -verify +// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.InvalidatedIterator -analyzer-eagerly-assume -analyzer-config aggressive-relational-comparison-simplification=true -analyzer-config c++-container-inlining=true -DINLINE=1 %s -verify + +#include "Inputs/system-header-simulator-cxx.h" + +void bad_copy_assign_operator_list1(std::list &L1, + const std::list &L2) { + auto i0 = L1.cbegin(); + L1 = L2; + *i0; // expected-warning{{Invalidated iterator accessed}} +} + +void bad_copy_assign_operator_vector1(std::vector &V1, + const std::vector &V2) { + auto i0 = V1.cbegin(); + V1 = V2; + *i0; // expected-warning{{Invalidated iterator accessed}} +} + +void bad_copy_assign_operator_deque1(std::deque &D1, + const std::deque &D2) { + auto i0 = D1.cbegin(); + D1 = D2; + *i0; // expected-warning{{Invalidated iterator accessed}} +} + +void bad_copy_assign_operator_forward_list1(std::forward_list &FL1, + const std::forward_list &FL2) { + auto i0 = FL1.cbegin(); + FL1 = FL2; + *i0; // expected-warning{{Invalidated iterator accessed}} +}