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.
A typical (bad) algorithm for erasing elements of a list is the following:
for(auto i = L.begin(); i != L.end(); ++i) {
if (condition(*i))
i = L.erase(i);
}
If `condition()` returns true for the last element, then `erase()` returns the
past-the-end iterator which the loop tries to increment which leads to
undefined behavior. However, the iterator range checker does not find this bug
because the "loop iteration before that last iteration" cannot be recognized by
the analyzer. Instead we added an option in this patch to `ContainerModeling`
which enables the modeling checker to assume after every erase that the result
is the past-the-end iterator (if this case is possible).
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D77150
Files:
clang/include/clang/StaticAnalyzer/Checkers/Checkers.td
clang/lib/StaticAnalyzer/Checkers/ContainerModeling.cpp
clang/test/Analysis/analyzer-config.c
Index: clang/test/Analysis/analyzer-config.c
===================================================================
--- clang/test/Analysis/analyzer-config.c
+++ clang/test/Analysis/analyzer-config.c
@@ -7,6 +7,7 @@
// CHECK-NEXT: alpha.clone.CloneChecker:IgnoredFilesPattern = ""
// CHECK-NEXT: alpha.clone.CloneChecker:MinimumCloneComplexity = 50
// CHECK-NEXT: alpha.clone.CloneChecker:ReportNormalClones = true
+// CHECK-NEXT: alpha.cplusplus.ContainerModeling:AggressiveEraseModeling = false
// CHECK-NEXT: alpha.cplusplus.STLAlgorithmModeling:AggressiveStdFindModeling = false
// CHECK-NEXT: alpha.security.MmapWriteExec:MmapProtExec = 0x04
// CHECK-NEXT: alpha.security.MmapWriteExec:MmapProtRead = 0x01
@@ -100,4 +101,4 @@
// CHECK-NEXT: unroll-loops = false
// CHECK-NEXT: widen-loops = false
// CHECK-NEXT: [stats]
-// CHECK-NEXT: num-entries = 97
+// CHECK-NEXT: num-entries = 98
Index: clang/lib/StaticAnalyzer/Checkers/ContainerModeling.cpp
===================================================================
--- clang/lib/StaticAnalyzer/Checkers/ContainerModeling.cpp
+++ clang/lib/StaticAnalyzer/Checkers/ContainerModeling.cpp
@@ -65,6 +65,8 @@
public:
ContainerModeling() = default;
+ DefaultBool AggressiveEraseModeling;
+
void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
void checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const;
void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
@@ -606,7 +608,7 @@
auto RetPos =
IteratorPosition::getPosition(Pos->getContainer(), Pos->getOffset());
State = setIteratorPosition(State, RetVal, RetPos);
-
+
C.addTransition(State);
}
@@ -632,7 +634,7 @@
SymMgr.getType(Pos->getOffset())).getAsSymbol();
auto RetPos = IteratorPosition::getPosition(Pos->getContainer(), RetOffset);
State = setIteratorPosition(State, RetVal, RetPos);
-
+
C.addTransition(State);
}
@@ -677,7 +679,29 @@
SymMgr.getType(Pos->getOffset())).getAsSymbol();
auto RetPos = IteratorPosition::getPosition(Pos->getContainer(), RetOffset);
State = setIteratorPosition(State, RetVal, RetPos);
-
+
+ if (AggressiveEraseModeling) {
+ if (const auto *CData = getContainerData(State, ContReg)) {
+ if (const SymbolRef EndSym = CData->getEnd()) {
+ const auto RetEnd =
+ SVB.evalBinOp(State, BO_EQ, nonloc::SymbolVal(RetOffset),
+ nonloc::SymbolVal(EndSym), SVB.getConditionType())
+ .getAs<DefinedOrUnknownSVal>();
+ if (RetEnd) {
+ ProgramStateRef StateEnd, StateNotEnd;
+ std::tie(StateEnd, StateNotEnd) = State->assume(*RetEnd);
+ if (StateEnd) {
+ C.addTransition(StateEnd);
+ }
+ if (StateNotEnd) {
+ C.addTransition(StateNotEnd);
+ }
+ return;
+ }
+ }
+ }
+ }
+
C.addTransition(State);
}
@@ -725,6 +749,11 @@
void ContainerModeling::handleEraseAfter(CheckerContext &C, SVal Cont,
SVal Iter, SVal RetVal) const {
+ const auto *ContReg = Cont.getAsRegion();
+ if (!ContReg)
+ return;
+
+ ContReg = ContReg->getMostDerivedObjectRegion();
auto State = C.getState();
const auto *Pos = getIteratorPosition(State, Iter);
if (!Pos)
@@ -748,6 +777,28 @@
auto RetPos = IteratorPosition::getPosition(Pos->getContainer(), RetOffset);
State = setIteratorPosition(State, RetVal, RetPos);
+ if (AggressiveEraseModeling) {
+ if (const auto *CData = getContainerData(State, ContReg)) {
+ if (const SymbolRef EndSym = CData->getEnd()) {
+ const auto RetEnd =
+ SVB.evalBinOp(State, BO_EQ, nonloc::SymbolVal(RetOffset),
+ nonloc::SymbolVal(EndSym), SVB.getConditionType())
+ .getAs<DefinedOrUnknownSVal>();
+ if (RetEnd) {
+ ProgramStateRef StateEnd, StateNotEnd;
+ std::tie(StateEnd, StateNotEnd) = State->assume(*RetEnd);
+ if (StateEnd) {
+ C.addTransition(StateEnd);
+ }
+ if (StateNotEnd) {
+ C.addTransition(StateNotEnd);
+ }
+ return;
+ }
+ }
+ }
+ }
+
C.addTransition(State);
}
@@ -1131,7 +1182,11 @@
} // namespace
void ento::registerContainerModeling(CheckerManager &mgr) {
- mgr.registerChecker<ContainerModeling>();
+ auto *Checker = mgr.registerChecker<ContainerModeling>();
+ Checker->AggressiveEraseModeling =
+ mgr.getAnalyzerOptions().getCheckerBooleanOption(
+ "alpha.cplusplus.ContainerModeling", "AggressiveEraseModeling");
+
}
bool ento::shouldRegisterContainerModeling(const CheckerManager &mgr) {
Index: clang/include/clang/StaticAnalyzer/Checkers/Checkers.td
===================================================================
--- clang/include/clang/StaticAnalyzer/Checkers/Checkers.td
+++ clang/include/clang/StaticAnalyzer/Checkers/Checkers.td
@@ -615,6 +615,14 @@
def ContainerModeling : Checker<"ContainerModeling">,
HelpText<"Models C++ containers">,
+ CheckerOptions<[
+ CmdLineOption<Boolean,
+ "AggressiveEraseModeling",
+ "Enables exploration of the past-the-end branch for the "
+ "return value of the erase() method of containers.",
+ "false",
+ Released>
+ ]>,
Documentation<NotDocumented>,
Hidden;
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
