Index: include/clang/StaticAnalyzer/Checkers/Checkers.td =================================================================== --- include/clang/StaticAnalyzer/Checkers/Checkers.td +++ include/clang/StaticAnalyzer/Checkers/Checkers.td @@ -301,6 +301,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 + 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); } }; @@ -187,9 +199,11 @@ 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 +218,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 }; @@ -248,7 +266,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 +307,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, @@ -299,16 +321,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)) { @@ -346,7 +381,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); @@ -615,6 +653,21 @@ } } +void IteratorChecker::verifyAccess(CheckerContext &C, const SVal &Val) const { + auto State = C.getState(); + const auto *Pos = getIteratorPosition(State, Val); + if (Pos && !Pos->isValid()) { + // If I do not put a tag here, some invalidation tests will fail + static CheckerProgramPointTag Tag("InvalidatedIteratorChecker", + "InvalidatedIterator"); + auto *N = C.generateNonFatalErrorNode(State, &Tag); + 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 @@ -854,6 +907,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 { @@ -862,6 +935,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); @@ -937,10 +1018,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; @@ -1159,6 +1247,37 @@ return State; } +template +ProgramStateRef processIteratorPositions(ProgramStateRef State, Condition Cond, + Process Proc) { + auto RegionMap = State->get(); + for (const auto Reg : RegionMap) { + if (Cond(Reg.second)) { + State = setIteratorPosition(State, Reg.first, Proc(Reg.second)); + } + } + + auto SymbolMap = State->get(); + for (const auto Sym : SymbolMap) { + if (Cond(Sym.second)) { + State = setIteratorPosition(State, Sym.first, Proc(Sym.second)); + } + } + + 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, @@ -1231,3 +1350,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 =================================================================== --- /dev/null +++ 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}} +}