Hi Jordan,
I have changed the patch to store $foo instead of the variable. I also make
sure that the divison and check is in the same block by comparing the blockid.
This handles your second example.
//Anders
________________________________________
Från: Jordan Rose [[email protected]]
Skickat: den 5 april 2014 04:03
Till: Anders Rönnholm
Cc: [email protected]; Daniel Marjamäki
Ämne: Re: [PATCH] Division by zero
On Apr 3, 2014, at 7:18 , Anders Rönnholm
<[email protected]<mailto:[email protected]>> wrote:
Hi Jordan, see below for comments and questions.
< Hi, Anders. I have some high-level concerns about this checker as it's
structured now. First (and most mundanely), the checker is conflating values
and locations. A particular symbol in the analyzer can <never change, so
there's no reason to ever have to remove something from the DivZeroMap because
of invalidation.
<
< int x = foo(); // The value stored in 'x' is some symbol '$foo'
< int y = 5 / x; // use $foo
< x = bar(); // The value stored in 'x' is now some symbol '$bar', but '$foo'
hasn't changed.
< On the flip side, I'm concerned that values never leave the map. You could
clean up some of them with a checkDeadSymbols callback, but that's still a
large amount of state for values that may have been < checked quite a while
ago. In particular, this will result in false positives if a value is used in
one function and then checked in another.
Why don't we have to remove it? When x changes as you say we need to remove it
or flag it so we don't check x against zero anymore since x has changed after
the division.
I guess we could remove all items in DivZeroMap when we leave the function, do
you think that would work?
"When 'x' changes" is the interesting part. '$foo' can't change, and that's
what you're inserting into the map. The value stored in 'x' can change, and
that's why 'x' is being removed from the map. But 'x' should never be in the
map in the first place; it's '$foo', the value, that's important.
Here's another example:
int x = foo();
int y = x;
use(5 / x);
if (y == 0) // warn!
If we track the variable 'x', then we won't catch this case, even though it's
pretty much equivalent to what you had before.
Here's another problem with doing things this way: doing this as a
path-sensitive check says that there's a spurious comparison along one path,
but you really need to know if it happens along all paths:
void foo() {
bool isPositive;
int x = getValue(&isPositive);
if (isPositive) {
use(5 / x);
}
if (x == 0) {
log("x is zero");
}
}
In this case, there exists a path where 'x' checked against 0 after being used
as a denominator, but it's not actually a problem. You can argue that the test
should be moved up before the use, or that an assertion should be added, but I
don't know if we want to tackle that. OTOH, you would have to add an assertion
if you did move the test before the use.
I like the idea of clearing the map/set on function exit, because it's somewhat
reasonable to add asserts within a function...but you'd basically also have to
clear it on function entrance too. Which means you have one set per
LocationContext. I haven't fully thought that through yet.
<
< (The opposite order hit us so much when dealing with C++ support that we
coined a term for it: "inlined defensive checks". This occurs when one function
accepts null pointers and so does a check, the <caller knows the value is
never null but doesn't actually assert it, and then the value is used. We ended
up having to silence all bugs where the first null check came from an inlined
function, which <definitely through out some true positives with the false
ones.)
<
< What do you think?
< Jordan
<
< P.S. If your map entries always map to "true", you might as well use a set.
;-)
Is it possible to get a specific entry using set or do you have to iterate
through all items to find the one your looking for?
With map you can do this,:
const bool D = State->get<DivZeroMap>(MR);
but with set i'm only able to get them all.
DivZeroMapTy DivZeroes = State->get<DivZeroMap>();
For future reference, set traits get a State->contains<DivZeroMap>().
Jordan
Index: lib/StaticAnalyzer/Checkers/CMakeLists.txt
===================================================================
--- lib/StaticAnalyzer/Checkers/CMakeLists.txt (revision 204458)
+++ lib/StaticAnalyzer/Checkers/CMakeLists.txt (working copy)
@@ -32,6 +32,7 @@
DereferenceChecker.cpp
DirectIvarAssignment.cpp
DivZeroChecker.cpp
+ DivZeroChecker2.cpp
DynamicTypePropagation.cpp
ExprInspectionChecker.cpp
FixedAddressChecker.cpp
Index: lib/StaticAnalyzer/Checkers/DivZeroChecker2.cpp
===================================================================
--- lib/StaticAnalyzer/Checkers/DivZeroChecker2.cpp (revision 0)
+++ lib/StaticAnalyzer/Checkers/DivZeroChecker2.cpp (revision 0)
@@ -0,0 +1,188 @@
+//== DivZeroChecker2.cpp - Division by zero checker -------------*- C++ -*--==//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This defines DivZeroChecker2, a builtin check that performs checks for
+// division by zero where the division occurs before comparison with zero.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ClangSACheckers.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"
+
+using namespace clang;
+using namespace ento;
+
+struct DivZeroState {
+private:
+ SVal S;
+ unsigned B;
+
+public:
+ DivZeroState(SVal S, unsigned B) : S(S), B(B) {}
+ unsigned getBlockId() const { return B; }
+ SVal getSval() const { return S; }
+
+ bool operator==(const DivZeroState &X) const { return S == X.S && B == X.B; }
+
+ void Profile(llvm::FoldingSetNodeID &ID) const {
+ ID.AddInteger(B);
+ ID.AddPointer(&S);
+ }
+};
+
+namespace {
+class DivZeroChecker2
+ : public Checker<check::PreStmt<BinaryOperator>,
+ check::BranchCondition,
+ check::EndFunction> {
+ mutable std::unique_ptr<BuiltinBug> BB;
+ void reportBug(const char *Msg, CheckerContext &C) const;
+
+public:
+ void checkPreStmt(const BinaryOperator *B, CheckerContext &C) const;
+ void checkBranchCondition(const Stmt *Condition, CheckerContext &C) const;
+ void checkEndFunction(CheckerContext &C) const;
+ void setDivZeroMap(SVal Var, const DivZeroState &DS, CheckerContext &C) const;
+ bool hasDivZeroMapSval(const DivZeroState &DS, const CheckerContext &C) const;
+ unsigned getBlockID(const Expr *B, CheckerContext &C) const;
+};
+} // end anonymous namespace
+
+REGISTER_MAP_WITH_PROGRAMSTATE(DivZeroMap, const MemRegion *, DivZeroState)
+
+void DivZeroChecker2::setDivZeroMap(SVal Var, const DivZeroState &DS,
+ CheckerContext &C) const {
+ const MemRegion *MR = Var.getAsRegion();
+ if (!MR)
+ return;
+
+ ProgramStateRef State = C.getState();
+ if (!State->get<DivZeroMap>(MR)) {
+ State = State->set<DivZeroMap>(MR, DS);
+ C.addTransition(State);
+ }
+}
+
+bool DivZeroChecker2::hasDivZeroMapSval(const DivZeroState &DS,
+ const CheckerContext &C) const {
+ ProgramStateRef State = C.getState();
+ DivZeroMapTy Tracked = State->get<DivZeroMap>();
+ for (DivZeroMapTy::iterator I = Tracked.begin(), E = Tracked.end(); I != E;
+ ++I) {
+ const DivZeroState Divided = I->second;
+ if (Divided == DS) {
+ return true;
+ }
+ }
+ return false;
+}
+
+unsigned DivZeroChecker2::getBlockID(const Expr *B, CheckerContext &C) const {
+ const CFG &cfg = C.getPredecessor()->getCFG();
+ for (CFG::const_iterator I = cfg.begin(); I != cfg.end(); ++I) {
+ for (CFGBlock::const_iterator BI = (*I)->begin(), BE = (*I)->end();
+ BI != BE; ++BI) {
+ Optional<CFGStmt> stmt = BI->getAs<CFGStmt>();
+ if (stmt && stmt->getStmt() == B)
+ return (*I)->getBlockID();
+ }
+ }
+ return 0;
+}
+
+void DivZeroChecker2::reportBug(const char *Msg, CheckerContext &C) const {
+ if (ExplodedNode *N = C.generateSink(C.getState())) {
+ if (!BB)
+ BB.reset(new BuiltinBug(this, "Division by zero"));
+
+ BugReport *R = new BugReport(*BB, Msg, N);
+ C.emitReport(R);
+ }
+}
+
+void DivZeroChecker2::checkEndFunction(CheckerContext &C) const {
+ ProgramStateRef State = C.getState();
+ State = State->remove<DivZeroMap>();
+ C.addTransition(State);
+}
+
+void DivZeroChecker2::checkPreStmt(const BinaryOperator *B,
+ CheckerContext &C) const {
+ BinaryOperator::Opcode Op = B->getOpcode();
+ if (Op == BO_Div || Op == BO_Rem || Op == BO_DivAssign ||
+ Op == BO_RemAssign) {
+ if (!B->getRHS()->getType()->isScalarType())
+ return;
+ ProgramStateRef State = C.getState();
+ SVal Val = C.getSVal(B->getRHS());
+ Optional<DefinedSVal> DSV = Val.getAs<DefinedSVal>();
+
+ if (!DSV)
+ return;
+
+ // Make sure SVal can be zero.
+ if (!C.getConstraintManager().assume(State, *DSV, false))
+ return;
+
+ SVal Var = C.getSVal(B->getRHS()->IgnoreParenImpCasts());
+ setDivZeroMap(Var, DivZeroState(Val, getBlockID(B, C)), C);
+ }
+}
+
+void DivZeroChecker2::checkBranchCondition(const Stmt *Condition,
+ CheckerContext &C) const {
+ if (const BinaryOperator *B = dyn_cast<BinaryOperator>(Condition)) {
+ if (B->isComparisonOp()) {
+ const IntegerLiteral *IntLiteral = dyn_cast<IntegerLiteral>(B->getRHS());
+ bool LRHS = true;
+ if (!IntLiteral) {
+ IntLiteral = dyn_cast<IntegerLiteral>(B->getLHS());
+ LRHS = false;
+ }
+
+ if (IntLiteral && IntLiteral->getValue() != 0)
+ return;
+
+ if (hasDivZeroMapSval(
+ DivZeroState(C.getSVal(LRHS ? B->getLHS() : B->getRHS()),
+ getBlockID(B, C)), C))
+ reportBug("Comparison is useless, "
+ "or there is division by zero previously",
+ C);
+ }
+ } else if (const UnaryOperator *U = dyn_cast<UnaryOperator>(Condition)) {
+ if (U->getOpcode() == UO_LNot) {
+ SVal Val;
+ if (const ImplicitCastExpr *I =
+ dyn_cast<ImplicitCastExpr>(U->getSubExpr()))
+ Val = C.getSVal(I->getSubExpr());
+ else
+ Val = C.getSVal(U->getSubExpr());
+
+ if (hasDivZeroMapSval(DivZeroState(Val, getBlockID(U, C)), C))
+ reportBug("Comparison is useless, "
+ "or there is division by zero previously",
+ C);
+ }
+ } else if (const ImplicitCastExpr *IE =
+ dyn_cast<ImplicitCastExpr>(Condition)) {
+ if (hasDivZeroMapSval(
+ DivZeroState(C.getSVal(IE->getSubExpr()), getBlockID(IE, C)), C))
+ reportBug("Comparison is useless, "
+ "or there is division by zero previously",
+ C);
+ }
+}
+
+void ento::registerDivZeroChecker2(CheckerManager &mgr) {
+ mgr.registerChecker<DivZeroChecker2>();
+}
Index: lib/StaticAnalyzer/Checkers/Checkers.td
===================================================================
--- lib/StaticAnalyzer/Checkers/Checkers.td (revision 204458)
+++ lib/StaticAnalyzer/Checkers/Checkers.td (working copy)
@@ -72,6 +72,10 @@
HelpText<"Check for division by zero">,
DescFile<"DivZeroChecker.cpp">;
+def DivZeroChecker2 : Checker<"DivideZero2">,
+ HelpText<"Check for division by variable that is later compared against 0. Either the comparison is useless or there is division by zero.">,
+ DescFile<"DivZeroChecker2.cpp">;
+
def UndefResultChecker : Checker<"UndefinedBinaryOperatorResult">,
HelpText<"Check for undefined results of binary operators">,
DescFile<"UndefResultChecker.cpp">;
Index: test/Analysis/div-zero2.cpp
===================================================================
--- test/Analysis/div-zero2.cpp (revision 0)
+++ test/Analysis/div-zero2.cpp (revision 0)
@@ -0,0 +1,155 @@
+// RUN: %clang_cc1 -analyze -analyzer-checker=core.DivideZero2 -verify %s
+
+int var;
+
+void err_eq(int x) {
+ var = 77 / x;
+ if (x==0){} // expected-warning {{Comparison is useless, or there is division by zero previously}}
+}
+
+void err_eq2(int x) {
+ var = 77 / x;
+ if (0==x){} // expected-warning {{Comparison is useless, or there is division by zero previously}}
+}
+
+void err_ne(int x) {
+ var = 77 / x;
+ if (x!=0){} // expected-warning {{Comparison is useless, or there is division by zero previously}}
+}
+
+void err_ge(int x) {
+ var = 77 / x;
+ if (x>=0){} // expected-warning {{Comparison is useless, or there is division by zero previously}}
+}
+
+void err_le(int x) {
+ var = 77 / x;
+ if (x<=0){} // expected-warning {{Comparison is useless, or there is division by zero previously}}
+}
+
+void err_yes(int x) {
+ var = 77 / x;
+ if (x){} // expected-warning {{Comparison is useless, or there is division by zero previously}}
+}
+void err_not(int x) {
+ var = 77 / x;
+ if (!x){} // expected-warning {{Comparison is useless, or there is division by zero previously}}
+}
+
+
+
+void err_pnot(int x) {
+ int *y = &x;
+ var = 77 / *y;
+ if (!x){} // expected-warning {{Comparison is useless, or there is division by zero previously}}
+}
+
+void err_pnot2(int x) {
+ int *y = &x;
+ var = 77 / x;
+ if (!*y){} // expected-warning {{Comparison is useless, or there is division by zero previously}}
+}
+
+void err_ppnot(int x) {
+ int *y = &x;
+ int **z = &y;
+ var = 77 / **z;
+ if (!x){} // expected-warning {{Comparison is useless, or there is division by zero previously}}
+}
+
+void ok_other(int x, int y) {
+ var = 77 / y;
+ if (x == 0){}
+}
+
+void ok_assign(int x) {
+ var = 77 / x;
+ x = var / 77; // <- assignment => don't warn
+ if (x == 0){}
+}
+
+void ok_assign2(int x) {
+ var = 77 / x;
+ x = var / 77; // <- assignment => don't warn
+ if (0 == x){}
+}
+
+void ok_dec(int x) {
+ var = 77 / x;
+ x--; // <- assignment => don't warn
+ if (x == 0){}
+}
+
+void ok_inc(int x) {
+ var = 77 / x;
+ x++; // <- assignment => don't warn
+ if (x == 0){}
+}
+
+void do_something_ptr(int*x);
+void ok_callfunc_ptr(int x) {
+ var = 77 / x;
+ do_something_ptr(&x); // <- pass address of x to function => don't warn
+ if (x == 0){}
+}
+
+void do_something_ref(int&x);
+void ok_callfunc_ref(int x) {
+ var = 77 / x;
+ do_something_ref(x); // <- pass reference of x to function => don't warn
+ if (x == 0){}
+}
+
+void do_something(int x);
+void nok_callfunc(int x) {
+ var = 77 / x;
+ do_something(x);
+ if (x == 0){} // expected-warning {{Comparison is useless, or there is division by zero previously}}
+}
+void ok_if(int x) {
+ if (x > 3)
+ var = 77 / x;
+ if (x == 0){}
+}
+
+void ok_if2(int x) {
+ if (x < 3)
+ var = 77 / x;
+ if (x == 0){} // TODO warn here
+}
+
+void ok_pif(int x) {
+ int *y = &x;
+ if (x < 3)
+ var = 77 / *y;
+ if (x == 0){} // TODO warn here
+}
+
+int getValue(bool *isPositive);
+void use(int a);
+void log(char* a);
+void foo() {
+ bool isPositive;
+ int x = getValue(&isPositive);
+ if (isPositive) {
+ use(5 / x);
+ }
+
+ if (x == 0) {}
+}
+
+int getValue2();
+void foo2() {
+ int x = getValue2();
+ int y = x;
+
+ use(5 / x);
+ if (y == 0){} // expected-warning {{Comparison is useless, or there is division by zero previously}}
+}
+
+void ok_while(int x) {
+ int n = 100 / x;
+ while (x != 0) { // <- do not warn
+ x--;
+ }
+}
_______________________________________________
cfe-commits mailing list
[email protected]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
