baloghadamsoftware created this revision.
baloghadamsoftware added reviewers: NoQ, Szelethus.
baloghadamsoftware added a project: clang.
Herald added subscribers: ASDenysPetrov, martong, steakhal, Charusso,
gamesh411, dkrupp, donat.nagy, mikhail.ramalho, a.sidorin, rnkovacs, szepet,
xazax.hun, whisperity.
baloghadamsoftware added a comment.
This patch replaces the verification part of D62895
<https://reviews.llvm.org/D62895>.
Upon calling one of the functions `std::advance()`, `std::prev()` and
`std::next()` iterators could get out of their valid range which leads to
undefined behavior. If all these funcions are inlined together with the
functions they call internally (e.g. `__advance()` called by `std::advance()`
in some implementations) the error is detected by `IteratorRangeChecker` but
the bug location is inside the STL implementation. Even worse, if the budget
runs out and one of the calls is not inlined the bug remains undetected. This
patch fixes this behavior: all the bugs are detected at the point of the STL
function invocation.
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D76379
Files:
clang/lib/StaticAnalyzer/Checkers/IteratorRangeChecker.cpp
clang/test/Analysis/Inputs/system-header-simulator-cxx.h
clang/test/Analysis/iterator-range.cpp
Index: clang/test/Analysis/iterator-range.cpp
===================================================================
--- clang/test/Analysis/iterator-range.cpp
+++ clang/test/Analysis/iterator-range.cpp
@@ -359,6 +359,423 @@
auto j = i[1]; // expected-warning{{Past-the-end iterator dereferenced}} FIXME: expect warning Iterator incremented behind the past-the-end iterator
}
+//
+// std::advance()
+//
+
+// std::advance() by +1
+
+void advance_plus_1_begin(const std::vector<int> &V) {
+ auto i = V.begin();
+ std::advance(i, 1); // no-warning
+}
+
+void advance_plus_1_behind_begin(const std::vector<int> &V) {
+ auto i = ++V.begin();
+ std::advance(i, 1); // no-warning
+}
+
+void advance_plus_1_unknown(const std::vector<int> &V) {
+ auto i = return_any_iterator(V.begin());
+ std::advance(i, 1); // no-warning
+}
+
+void advance_plus_1_ahead_of_end(const std::vector<int> &V) {
+ auto i = --V.end();
+ std::advance(i, 1); // no-warning
+}
+
+void advance_plus_1_end(const std::vector<int> &V) {
+ auto i = V.end();
+ std::advance(i, 1); // expected-warning{{Iterator incremented behind the past-the-end iterator}}
+}
+
+// std::advance() by -1
+
+void advance_minus_1_begin(const std::vector<int> &V) {
+ auto i = V.begin();
+ std::advance(i, -1); // expected-warning{{Iterator decremented ahead of its valid range}}
+}
+
+void advance_minus_1_behind_begin(const std::vector<int> &V) {
+ auto i = ++V.begin();
+ std::advance(i, -1); // no-warning
+}
+
+void advance_minus_1_unknown(const std::vector<int> &V) {
+ auto i = return_any_iterator(V.begin());
+ std::advance(i, -1); // no-warning
+}
+
+void advance_minus_1_ahead_of_end(const std::vector<int> &V) {
+ auto i = --V.end();
+ std::advance(i, -1); // no-warning
+}
+
+void advance_minus_1_end(const std::vector<int> &V) {
+ auto i = V.end();
+ std::advance(i, -1); // no-warning
+}
+
+// std::advance() by +2
+
+void advance_plus_2_begin(const std::vector<int> &V) {
+ auto i = V.begin();
+ std::advance(i, 2); // no-warning
+}
+
+void advance_plus_2_behind_begin(const std::vector<int> &V) {
+ auto i = ++V.begin();
+ std::advance(i, 2); // no-warning
+}
+
+void advance_plus_2_unknown(const std::vector<int> &V) {
+ auto i = return_any_iterator(V.begin());
+ std::advance(i, 2); // no-warning
+}
+
+void advance_plus_2_ahead_of_end(const std::vector<int> &V) {
+ auto i = --V.end();
+ std::advance(i, 2); // expected-warning{{Iterator incremented behind the past-the-end iterator}}
+}
+
+void advance_plus_2_end(const std::vector<int> &V) {
+ auto i = V.end();
+ std::advance(i, 2); // expected-warning{{Iterator incremented behind the past-the-end iterator}}
+}
+
+// std::advance() by -2
+
+void advance_minus_2_begin(const std::vector<int> &V) {
+ auto i = V.begin();
+ std::advance(i, -2); // expected-warning{{Iterator decremented ahead of its valid range}}
+}
+
+void advance_minus_2_behind_begin(const std::vector<int> &V) {
+ auto i = ++V.begin();
+ std::advance(i, -2); // expected-warning{{Iterator decremented ahead of its valid range}}
+}
+
+void advance_minus_2_unknown(const std::vector<int> &V) {
+ auto i = return_any_iterator(V.begin());
+ std::advance(i, -2); // no-warning
+}
+
+void advance_minus_2_ahead_of_end(const std::vector<int> &V) {
+ auto i = --V.end();
+ std::advance(i, -2); // no-warning
+}
+
+void advance_minus_2_end(const std::vector<int> &V) {
+ auto i = V.end();
+ std::advance(i, -2); // no-warning
+}
+
+// std::advance() by 0
+
+void advance_0_begin(const std::vector<int> &V) {
+ auto i = V.begin();
+ std::advance(i, 0); // no-warning
+}
+
+void advance_0_behind_begin(const std::vector<int> &V) {
+ auto i = ++V.begin();
+ std::advance(i, 0); // no-warning
+}
+
+void advance_0_unknown(const std::vector<int> &V) {
+ auto i = return_any_iterator(V.begin());
+ std::advance(i, 0); // no-warning
+}
+
+void advance_0_ahead_of_end(const std::vector<int> &V) {
+ auto i = --V.end();
+ std::advance(i, 0); // no-warning
+}
+
+void advance_0_end(const std::vector<int> &V) {
+ auto i = V.end();
+ std::advance(i, 0); // no-warning
+}
+
+//
+// std::next()
+//
+
+// std::next() by +1 (default)
+
+void next_plus_1_begin(const std::vector<int> &V) {
+ auto i = V.begin();
+ auto j = std::next(i); // no-warning
+}
+
+void next_plus_1_behind_begin(const std::vector<int> &V) {
+ auto i = ++V.begin();
+ auto j = std::next(i); // no-warning
+}
+
+void next_plus_1_unknown(const std::vector<int> &V) {
+ auto i = return_any_iterator(V.begin());
+ auto j = std::next(i); // no-warning
+}
+
+void next_plus_1_ahead_of_end(const std::vector<int> &V) {
+ auto i = --V.end();
+ auto j = std::next(i); // no-warning
+}
+
+void next_plus_1_end(const std::vector<int> &V) {
+ auto i = V.end();
+ auto j = std::next(i); // expected-warning{{Iterator incremented behind the past-the-end iterator}}
+}
+
+// std::next() by -1
+
+void next_minus_1_begin(const std::vector<int> &V) {
+ auto i = V.begin();
+ auto j = std::next(i, -1); // expected-warning{{Iterator decremented ahead of its valid range}}
+}
+
+void next_minus_1_behind_begin(const std::vector<int> &V) {
+ auto i = ++V.begin();
+ auto j = std::next(i, -1); // no-warning
+}
+
+void next_minus_1_unknown(const std::vector<int> &V) {
+ auto i = return_any_iterator(V.begin());
+ auto j = std::next(i, -1); // no-warning
+}
+
+void next_minus_1_ahead_of_end(const std::vector<int> &V) {
+ auto i = --V.end();
+ auto j = std::next(i, -1); // no-warning
+}
+
+void next_minus_1_end(const std::vector<int> &V) {
+ auto i = V.end();
+ auto j = std::next(i, -1); // no-warning
+}
+
+// std::next() by +2
+
+void next_plus_2_begin(const std::vector<int> &V) {
+ auto i = V.begin();
+ auto j = std::next(i, 2); // no-warning
+}
+
+void next_plus_2_behind_begin(const std::vector<int> &V) {
+ auto i = ++V.begin();
+ auto j = std::next(i, 2); // no-warning
+}
+
+void next_plus_2_unknown(const std::vector<int> &V) {
+ auto i = return_any_iterator(V.begin());
+ auto j = std::next(i, 2); // no-warning
+}
+
+void next_plus_2_ahead_of_end(const std::vector<int> &V) {
+ auto i = --V.end();
+ auto j = std::next(i, 2); // expected-warning{{Iterator incremented behind the past-the-end iterator}}
+}
+
+void next_plus_2_end(const std::vector<int> &V) {
+ auto i = V.end();
+ auto j = std::next(i, 2); // expected-warning{{Iterator incremented behind the past-the-end iterator}}
+}
+
+// std::next() by -2
+
+void next_minus_2_begin(const std::vector<int> &V) {
+ auto i = V.begin();
+ auto j = std::next(i, -2); // expected-warning{{Iterator decremented ahead of its valid range}}
+}
+
+void next_minus_2_behind_begin(const std::vector<int> &V) {
+ auto i = ++V.begin();
+ auto j = std::next(i, -2); // expected-warning{{Iterator decremented ahead of its valid range}}
+}
+
+void next_minus_2_unknown(const std::vector<int> &V) {
+ auto i = return_any_iterator(V.begin());
+ auto j = std::next(i, -2); // no-warning
+}
+
+void next_minus_2_ahead_of_end(const std::vector<int> &V) {
+ auto i = --V.end();
+ auto j = std::next(i, -2); // no-warning
+}
+
+void next_minus_2_end(const std::vector<int> &V) {
+ auto i = V.end();
+ auto j = std::next(i, -2); // no-warning
+}
+
+// std::next() by 0
+
+void next_0_begin(const std::vector<int> &V) {
+ auto i = V.begin();
+ auto j = std::next(i, 0); // no-warning
+}
+
+void next_0_behind_begin(const std::vector<int> &V) {
+ auto i = ++V.begin();
+ auto j = std::next(i, 0); // no-warning
+}
+
+void next_0_unknown(const std::vector<int> &V) {
+ auto i = return_any_iterator(V.begin());
+ auto j = std::next(i, 0); // no-warning
+}
+
+void next_0_ahead_of_end(const std::vector<int> &V) {
+ auto i = --V.end();
+ auto j = std::next(i, 0); // no-warning
+}
+
+void next_0_end(const std::vector<int> &V) {
+ auto i = V.end();
+ auto j = std::next(i, 0); // no-warning
+}
+
+//
+// std::prev()
+//
+
+// std::prev() by +1 (default)
+
+void prev_plus_1_begin(const std::vector<int> &V) {
+ auto i = V.begin();
+ auto j = std::prev(i); // expected-warning{{Iterator decremented ahead of its valid range}}
+}
+
+void prev_plus_1_behind_begin(const std::vector<int> &V) {
+ auto i = ++V.begin();
+ auto j = std::prev(i); // no-warning
+}
+
+void prev_plus_1_unknown(const std::vector<int> &V) {
+ auto i = return_any_iterator(V.begin());
+ auto j = std::prev(i); // no-warning
+}
+
+void prev_plus_1_ahead_of_end(const std::vector<int> &V) {
+ auto i = --V.end();
+ auto j = std::prev(i); // no-warning
+}
+
+void prev_plus_1_end(const std::vector<int> &V) {
+ auto i = V.end();
+ auto j = std::prev(i); // no-warning
+}
+
+// std::prev() by -1
+
+void prev_minus_1_begin(const std::vector<int> &V) {
+ auto i = V.begin();
+ auto j = std::prev(i, -1); // no-warning
+}
+
+void prev_minus_1_behind_begin(const std::vector<int> &V) {
+ auto i = ++V.begin();
+ auto j = std::prev(i, -1); // no-warning
+}
+
+void prev_minus_1_unknown(const std::vector<int> &V) {
+ auto i = return_any_iterator(V.begin());
+ auto j = std::prev(i, -1); // no-warning
+}
+
+void prev_minus_1_ahead_of_end(const std::vector<int> &V) {
+ auto i = --V.end();
+ auto j = std::prev(i, -1); // no-warning
+}
+
+void prev_minus_1_end(const std::vector<int> &V) {
+ auto i = V.end();
+ auto j = std::prev(i, -1); // expected-warning{{Iterator incremented behind the past-the-end iterator}}
+}
+
+// std::prev() by +2
+
+void prev_plus_2_begin(const std::vector<int> &V) {
+ auto i = V.begin();
+ auto j = std::prev(i, 2); // expected-warning{{Iterator decremented ahead of its valid range}}
+}
+
+void prev_plus_2_behind_begin(const std::vector<int> &V) {
+ auto i = ++V.begin();
+ auto j = std::prev(i, 2); // expected-warning{{Iterator decremented ahead of its valid range}}
+}
+
+void prev_plus_2_unknown(const std::vector<int> &V) {
+ auto i = return_any_iterator(V.begin());
+ auto j = std::prev(i, 2); // no-warning
+}
+
+void prev_plus_2_ahead_of_end(const std::vector<int> &V) {
+ auto i = --V.end();
+ auto j = std::prev(i, 2); // no-warning
+}
+
+void prev_plus_2_end(const std::vector<int> &V) {
+ auto i = V.end();
+ auto j = std::prev(i, 2); // no-warning
+}
+
+// std::prev() by -2
+
+void prev_minus_2_begin(const std::vector<int> &V) {
+ auto i = V.begin();
+ auto j = std::prev(i, -2); // no-warning
+}
+
+void prev_minus_2_behind_begin(const std::vector<int> &V) {
+ auto i = ++V.begin();
+ auto j = std::prev(i, -2); // no-warning
+}
+
+void prev_minus_2_unknown(const std::vector<int> &V) {
+ auto i = return_any_iterator(V.begin());
+ auto j = std::prev(i, -2); // no-warning
+}
+
+void prev_minus_2_ahead_of_end(const std::vector<int> &V) {
+ auto i = --V.end();
+ auto j = std::prev(i, -2); // expected-warning{{Iterator incremented behind the past-the-end iterator}}
+}
+
+void prev_minus_2_end(const std::vector<int> &V) {
+ auto i = V.end();
+ auto j = std::prev(i, -2); // expected-warning{{Iterator incremented behind the past-the-end iterator}}
+}
+
+// std::prev() by 0
+
+void prev_0_begin(const std::vector<int> &V) {
+ auto i = V.begin();
+ auto j = std::prev(i, 0); // no-warning
+}
+
+void prev_0_behind_begin(const std::vector<int> &V) {
+ auto i = ++V.begin();
+ auto j = std::prev(i, 0); // no-warning
+}
+
+void prev_0_unknown(const std::vector<int> &V) {
+ auto i = return_any_iterator(V.begin());
+ auto j = std::prev(i, 0); // no-warning
+}
+
+void prev_0_ahead_of_end(const std::vector<int> &V) {
+ auto i = --V.end();
+ auto j = std::prev(i, 0); // no-warning
+}
+
+void prev_0_end(const std::vector<int> &V) {
+ auto i = V.end();
+ auto j = std::prev(i, 0); // no-warning
+}
+
//
// Structure member dereference operators
//
Index: clang/test/Analysis/Inputs/system-header-simulator-cxx.h
===================================================================
--- clang/test/Analysis/Inputs/system-header-simulator-cxx.h
+++ clang/test/Analysis/Inputs/system-header-simulator-cxx.h
@@ -783,6 +783,14 @@
return it;
}
+ template <class ForwardIterator>
+ ForwardIterator
+ next (ForwardIterator it,
+ typename iterator_traits<ForwardIterator>::difference_type n = 1) {
+ advance(it, n);
+ return it;
+ }
+
template <class InputIt, class T>
InputIt find(InputIt first, InputIt last, const T& value);
Index: clang/lib/StaticAnalyzer/Checkers/IteratorRangeChecker.cpp
===================================================================
--- clang/lib/StaticAnalyzer/Checkers/IteratorRangeChecker.cpp
+++ clang/lib/StaticAnalyzer/Checkers/IteratorRangeChecker.cpp
@@ -31,18 +31,32 @@
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 verifyDereference(CheckerContext &C, SVal Val) const;
+ void verifyIncrement(CheckerContext &C, SVal Iter) const;
+ void verifyDecrement(CheckerContext &C, 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;
+ SVal LHS, SVal RHS) const;
+ void verifyAdvance(CheckerContext &C, SVal LHS, SVal RHS) const;
+ void verifyPrev(CheckerContext &C, SVal LHS, SVal RHS) const;
+ void verifyNext(CheckerContext &C, SVal LHS, SVal RHS) const;
+ void reportBug(const StringRef &Message, SVal Val, CheckerContext &C,
+ ExplodedNode *ErrNode) const;
public:
IteratorRangeChecker();
void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
+ typedef void (IteratorRangeChecker::*AdvanceFn)(CheckerContext &, SVal,
+ SVal) const;
+
+ CallDescriptionMap<AdvanceFn> AdvanceFunctions = {
+ {{{"std", "advance"}, 2},
+ &IteratorRangeChecker::verifyAdvance},
+ {{{"std", "prev"}, 2},
+ &IteratorRangeChecker::verifyPrev},
+ {{{"std", "next"}, 2},
+ &IteratorRangeChecker::verifyNext},
+ };
};
bool isPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos);
@@ -107,11 +121,22 @@
verifyDereference(C, Call.getArgSVal(0));
}
}
+ } else {
+ const AdvanceFn *Verifier = AdvanceFunctions.lookup(Call);
+ if (Verifier) {
+ if (Call.getNumArgs() > 1) {
+ (this->**Verifier)(C, Call.getArgSVal(0), Call.getArgSVal(1));
+ } else {
+ auto &BVF = C.getSValBuilder().getBasicValueFactory();
+ (this->**Verifier)(C, Call.getArgSVal(0),
+ nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
+ }
+ }
}
}
void IteratorRangeChecker::verifyDereference(CheckerContext &C,
- const SVal &Val) const {
+ SVal Val) const {
auto State = C.getState();
const auto *Pos = getIteratorPosition(State, Val);
if (Pos && isPastTheEnd(State, *Pos)) {
@@ -123,15 +148,13 @@
}
}
-void IteratorRangeChecker::verifyIncrement(CheckerContext &C,
- const SVal &Iter) const {
+void IteratorRangeChecker::verifyIncrement(CheckerContext &C, 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 {
+void IteratorRangeChecker::verifyDecrement(CheckerContext &C, SVal Iter) const {
auto &BVF = C.getSValBuilder().getBasicValueFactory();
verifyRandomIncrOrDecr(C, OO_Minus, Iter,
nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
@@ -139,8 +162,7 @@
void IteratorRangeChecker::verifyRandomIncrOrDecr(CheckerContext &C,
OverloadedOperatorKind Op,
- const SVal &LHS,
- const SVal &RHS) const {
+ SVal LHS, SVal RHS) const {
auto State = C.getState();
auto Value = RHS;
@@ -180,9 +202,24 @@
}
}
-void IteratorRangeChecker::reportBug(const StringRef &Message,
- const SVal &Val, CheckerContext &C,
- ExplodedNode *ErrNode) const {
+void IteratorRangeChecker::verifyAdvance(CheckerContext &C, SVal LHS,
+ SVal RHS) const {
+ verifyRandomIncrOrDecr(C, OO_PlusEqual, LHS, RHS);
+}
+
+void IteratorRangeChecker::verifyPrev(CheckerContext &C, SVal LHS,
+ SVal RHS) const {
+ verifyRandomIncrOrDecr(C, OO_Minus, LHS, RHS);
+}
+
+void IteratorRangeChecker::verifyNext(CheckerContext &C, SVal LHS,
+ SVal RHS) const {
+ verifyRandomIncrOrDecr(C, OO_Plus, LHS, RHS);
+}
+
+void IteratorRangeChecker::reportBug(const StringRef &Message, SVal Val,
+ CheckerContext &C,
+ ExplodedNode *ErrNode) const {
auto R = std::make_unique<PathSensitiveBugReport>(*OutOfRangeBugType, Message,
ErrNode);
R->markInteresting(Val);
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
