Re: [PATCH] Division by zero
On Sep 15, 2014, at 1:59 AM, Anders Rönnholm anders.ronnh...@evidente.se wrote: Hi, I feel that to change this checker and the null dereference check would take a large amount of time compared to what is gained, time which could be used more efficiently on other checkers. The null dereference check is already completed as path sensitive and works well. We are talking about converting only the check after division/dereference (not regular div by zero or dereference checks) because these checks require all paths reasoning (See the [cfe-dev] [RFC] Creating base class for 'Test after X' checkers thread). The main win is speed (flow sensitive analyzes are algorithmically much simpler than the path sensitive ones), which also opens a possibility of converting this into a compiler warning. I agree that it would not be a very easy task, but this is the right way to approach the problem. I agree with Anna. Doing this because it's convenient is really just technical debt and isn't something we'd necessarily be comfortable moving out of the alpha package, meaning that plenty of users won't even know it exists. I can see us very easily never coming back to do the right thing here. Jordan We still need to know more of how to do the right thing. Can you help us more on how to do it cfg-based? Do we need to create our own LiveVariables class for our checkers and then observe it like DeadStoresChecker observes LiveVariables? Consuming the result of data flow analysis in a checker is a good approach for producing static analyzer warnings. I can think of one reason that might need to change; specifically, if the analysis is cheap enough to turn it into a warning. It is hard to say if that will be the case ahead of time. Anna. //Anders ___ cfe-commits mailing list cfe-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
Re: [PATCH] Division by zero
Hi, I feel that to change this checker and the null dereference check would take a large amount of time compared to what is gained, time which could be used more efficiently on other checkers. The null dereference check is already completed as path sensitive and works well. We are talking about converting only the check after division/dereference (not regular div by zero or dereference checks) because these checks require all paths reasoning (See the [cfe-dev] [RFC] Creating base class for 'Test after X' checkers thread). The main win is speed (flow sensitive analyzes are algorithmically much simpler than the path sensitive ones), which also opens a possibility of converting this into a compiler warning. I agree that it would not be a very easy task, but this is the right way to approach the problem. I agree with Anna. Doing this because it's convenient is really just technical debt and isn't something we'd necessarily be comfortable moving out of the alpha package, meaning that plenty of users won't even know it exists. I can see us very easily never coming back to do the right thing here. Jordan We still need to know more of how to do the right thing. Can you help us more on how to do it cfg-based? Do we need to create our own LiveVariables class for our checkers and then observe it like DeadStoresChecker observes LiveVariables? //Anders ___ cfe-commits mailing list cfe-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
Re: [PATCH] Division by zero
I feel that to change this checker and the null dereference check would take a large amount of time compared to what is gained, time which could be used more efficiently on other checkers. The null dereference check is already completed as path sensitive and works well. We are talking about converting only the check after division/dereference (not regular div by zero or dereference checks) because these checks require all paths reasoning (See the [cfe-dev] [RFC] Creating base class for 'Test after X' checkers thread). The main win is speed (flow sensitive analyzes are algorithmically much simpler than the path sensitive ones), which also opens a possibility of converting this into a compiler warning. I don't mean the regular dereference but the new dereference then check checker. We have it completed but haven't sent the patch due to this change that you propose. We simply suggest that we submit this check now as it's completed and working rather well and we currently don't have time to redo it. I agree that it would not be a very easy task, but this is the right way to approach the problem. I don't know when we can deliver this as CFG-based (definitely not this year), wouldn't it be better to have it like this now? For a possible remake of this checker to a CFG-based one in the future, we would need more help from you on how to make them CFG-based. What parts of LiveVariables and DeadStoresChecker are related to our check? I guess just parts of the LiveVariables framework is needed. DeadStoresChecker is an example of other flow sensitive checks. You would need to create a similar one for div by zero / dereference. Yes i know that DeadStoresChecker is an example of a flow sensitive check. It seems like it uses LiveVariables and only reacts to what happens there. Do we need to create our own LiveVariables framework for our checkers and then observe it like DeadStoresChecker observes LiveVariables? Thanks, Anders ___ cfe-commits mailing list cfe-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
Re: [PATCH] Division by zero
On Sep 5, 2014, at 10:03 , Anna Zaks ga...@apple.com wrote: On Sep 5, 2014, at 5:24 AM, Anders Rönnholm anders.ronnh...@evidente.se wrote: Hi, I feel that to change this checker and the null dereference check would take a large amount of time compared to what is gained, time which could be used more efficiently on other checkers. The null dereference check is already completed as path sensitive and works well. We are talking about converting only the check after division/dereference (not regular div by zero or dereference checks) because these checks require all paths reasoning (See the [cfe-dev] [RFC] Creating base class for 'Test after X' checkers thread). The main win is speed (flow sensitive analyzes are algorithmically much simpler than the path sensitive ones), which also opens a possibility of converting this into a compiler warning. I agree that it would not be a very easy task, but this is the right way to approach the problem. I agree with Anna. Doing this because it's convenient is really just technical debt and isn't something we'd necessarily be comfortable moving out of the alpha package, meaning that plenty of users won't even know it exists. I can see us very easily never coming back to do the right thing here. Jordan___ cfe-commits mailing list cfe-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
RE: [PATCH] Division by zero
Hi,
I feel that to change this checker and the null dereference check would take a
large amount of time compared to what is gained, time which could be used more
efficiently on other checkers.
The null dereference check is already completed as path sensitive and works
well. I don't know when we can deliver this as CFG-based (definitely not this
year), wouldn't it be better to have it like this now?
For a possible remake of this checker to a CFG-based one in the future, we
would need more help from you on how to make them CFG-based. What parts of
LiveVariables and DeadStoresChecker are related to our check? I guess just
parts of the LiveVariables framework is needed.
So, Anna brought up that the check as implemented is very nearly
path-independent, i.e. it only depends on flow-sensitive properties of the
CFG. The path-sensitivity is buying us very little; it catches this case:
int y = x;
int div = z / y;
if (x) { ...}
But also warns here, which doesn't necessarily make sense:
int foo(int x, int y, int z) {
int div = z / y;
if (x) return div;
return 0;
}
foo(a, a, b); // only coincidentally the same symbol
What would you think about turning this (and/or the null dereference check)
into a CFG-based check instead? We lose the first example (and cases where
inlining would help), but fix the second, and very possibly speed up analysis.
CFG analysis is also more capable of proving that something happens on all
paths rather than just some, since that's just propagating information along
the graph.
I agree, this can in theory be a false positive but we believe it is an
unlikely one. Other existing checkers in the Clang static analyser have the
same problem. I don't have any proposal, but maybe a generic solution for such
FP would be good. In the long run I think it would be nice to have full flow
analysis in this checker so we can find deeper bugs that are not limited to a
single basic block.
//Anders
___
cfe-commits mailing list
cfe-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
Re: [PATCH] Division by zero
On Sep 5, 2014, at 5:24 AM, Anders Rönnholm anders.ronnh...@evidente.se
wrote:
Hi,
I feel that to change this checker and the null dereference check would take
a large amount of time compared to what is gained, time which could be used
more efficiently on other checkers.
The null dereference check is already completed as path sensitive and works
well.
We are talking about converting only the check after division/dereference
(not regular div by zero or dereference checks) because these checks require
all paths reasoning (See the [cfe-dev] [RFC] Creating base class for 'Test
after X' checkers thread). The main win is speed (flow sensitive analyzes are
algorithmically much simpler than the path sensitive ones), which also opens a
possibility of converting this into a compiler warning.
I agree that it would not be a very easy task, but this is the right way to
approach the problem.
I don't know when we can deliver this as CFG-based (definitely not this
year), wouldn't it be better to have it like this now?
For a possible remake of this checker to a CFG-based one in the future, we
would need more help from you on how to make them CFG-based. What parts of
LiveVariables and DeadStoresChecker are related to our check? I guess just
parts of the LiveVariables framework is needed.
DeadStoresChecker is an example of other flow sensitive checks. You would need
to create a similar one for div by zero / dereference.
So, Anna brought up that the check as implemented is very nearly
path-independent, i.e. it only depends on flow-sensitive properties of the
CFG. The path-sensitivity is buying us very little; it catches this case:
int y = x;
int div = z / y;
if (x) { ...}
But also warns here, which doesn't necessarily make sense:
int foo(int x, int y, int z) {
int div = z / y;
if (x) return div;
return 0;
}
foo(a, a, b); // only coincidentally the same symbol
What would you think about turning this (and/or the null dereference check)
into a CFG-based check instead? We lose the first example (and cases where
inlining would help), but fix the second, and very possibly speed up
analysis. CFG analysis is also more capable of proving that something
happens on all paths rather than just some, since that's just propagating
information along the graph.
I agree, this can in theory be a false positive but we believe it is an
unlikely one. Other existing checkers in the Clang static analyser have the
same problem. I don't have any proposal, but maybe a generic solution for
such FP would be good. In the long run I think it would be nice to have full
flow analysis in this checker so we can find deeper bugs that are not limited
to a single basic block.
Again, the main issue is the algorithmic performance win, not false positives.
//Anders
___
cfe-commits mailing list
cfe-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
RE: [PATCH] Division by zero
Hi Jordan,
I don't know if I have the time to change division by zero right away but I can
make the dereference check CFG-based. Do you have an example of a CFG-based
checker? I don't know how to make those.
//Anders
From: Jordan Rose [mailto:jordan_r...@apple.com]
Sent: den 21 juli 2014 19:40
To: Anders Rönnholm
Cc: cfe-commits@cs.uiuc.edu; Daniel Marjamäki; Anna Zaks
Subject: Re: [PATCH] Division by zero
So, Anna brought up that the check as implemented is very nearly
path-independent, i.e. it only depends on flow-sensitive properties of the CFG.
The path-sensitivity is buying us very little; it catches this case:
int y = x;
int div = z / y;
if (x) { ...}
But also warns here, which doesn't necessarily make sense:
int foo(int x, int y, int z) {
int div = z / y;
if (x) return div;
return 0;
}
foo(a, a, b); // only coincidentally the same symbol
What would you think about turning this (and/or the null dereference check)
into a CFG-based check instead? We lose the first example (and cases where
inlining would help), but fix the second, and very possibly speed up analysis.
CFG analysis is also more capable of proving that something happens on all
paths rather than just some, since that's just propagating information along
the graph.
Jordan
On Jul 10, 2014, at 9:55 , Anders Rönnholm
anders.ronnh...@evidente.semailto:anders.ronnh...@evidente.se wrote:
Great, no problem. I'll move forward with my dereference then check patch now
that this one is commited, which will be pretty similar.
//Anders
...
Anders Rönnholm Senior Engineer
Evidente ES East AB Warfvinges väg 34 SE-112 51 Stockholm Sweden
Mobile:+46 (0)70 912 42 54
E-mail:
anders.ronnh...@evidente.semailto:anders.ronnh...@evidente.se
www.evidente.sehttp://www.evidente.se
Från: Jordan Rose [jordan_r...@apple.com]
Skickat: den 10 juli 2014 18:20
Till: Anders Rönnholm
Cc: cfe-commits@cs.uiuc.edumailto:cfe-commits@cs.uiuc.edu; Daniel Marjamäki
Ämne: Re: [PATCH] Division by zero
Thank you for going through so many rounds of review on this. Committed in
r212731! (The one change I made was to reset the test in isZero to use assume
instead of assumeDual, now that my confusion has been fixed.)
Jordan
___
cfe-commits mailing list
cfe-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
Re: [PATCH] Division by zero
The dead stores checker is an example of a CFG-based check. That checker rides
on top of the live variables analysis (which is CFG-based), so really the guts
of the analysis of the checker are there. The analysis for -Wuninitialized is
also dataflow-based, although that is a compiler warning instead of a checker,
but it works exactly the same way.
Essentially you do a dataflow analysis to collect possible facts at each basic
block, propagating facts forward as you analyze the statements of a basic
block. You then merge values at confluence points, which are the basic
blocks with multiple predecessors. That merging is what makes the analysis
path-insensitive, but flow-sensitive. Path-insensitive analyses are
dramatically faster, but for many of the properties the static analyzer looks
for they are too imprecise. For this checker it may be the case you don't need
path-sensitivity, which is why Jordan suggested it. If it can be implemented
as path-insensitive, it then has the possible chance of becoming a compiler
warning one day.
On Aug 11, 2014, at 11:58 PM, Anders Rönnholm anders.ronnh...@evidente.se
wrote:
Hi Jordan,
I don’t know if I have the time to change division by zero right away but I
can make the dereference check CFG-based. Do you have an example of a
CFG-based checker? I don’t know how to make those.
//Anders
From: Jordan Rose [mailto:jordan_r...@apple.com]
Sent: den 21 juli 2014 19:40
To: Anders Rönnholm
Cc: cfe-commits@cs.uiuc.edu; Daniel Marjamäki; Anna Zaks
Subject: Re: [PATCH] Division by zero
So, Anna brought up that the check as implemented is very nearly
path-independent, i.e. it only depends on flow-sensitive properties of the
CFG. The path-sensitivity is buying us very little; it catches this case:
int y = x;
int div = z / y;
if (x) { ...}
But also warns here, which doesn't necessarily make sense:
int foo(int x, int y, int z) {
int div = z / y;
if (x) return div;
return 0;
}
foo(a, a, b); // only coincidentally the same symbol
What would you think about turning this (and/or the null dereference check)
into a CFG-based check instead? We lose the first example (and cases where
inlining would help), but fix the second, and very possibly speed up
analysis. CFG analysis is also more capable of proving that something happens
on all paths rather than just some, since that's just propagating information
along the graph.
Jordan
On Jul 10, 2014, at 9:55 , Anders Rönnholm anders.ronnh...@evidente.se
mailto:anders.ronnh...@evidente.se wrote:
Great, no problem. I'll move forward with my dereference then check patch now
that this one is commited, which will be pretty similar.
//Anders
...
Anders Rönnholm Senior Engineer
Evidente ES East AB Warfvinges väg 34 SE-112 51 Stockholm Sweden
Mobile:+46 (0)70 912 42 54
E-mail:anders.ronnh...@evidente.se
mailto:anders.ronnh...@evidente.se
www.evidente.se http://www.evidente.se/
Från: Jordan Rose [jordan_r...@apple.com]
Skickat: den 10 juli 2014 18:20
Till: Anders Rönnholm
Cc: cfe-commits@cs.uiuc.edu mailto:cfe-commits@cs.uiuc.edu; Daniel Marjamäki
Ämne: Re: [PATCH] Division by zero
Thank you for going through so many rounds of review on this. Committed in
r212731! (The one change I made was to reset the test in isZero to use assume
instead of assumeDual, now that my confusion has been fixed.)
Jordan
___
cfe-commits mailing list
cfe-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
___
cfe-commits mailing list
cfe-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
Re: [PATCH] Division by zero
So, Anna brought up that the check as implemented is very nearly
path-independent, i.e. it only depends on flow-sensitive properties of the CFG.
The path-sensitivity is buying us very little; it catches this case:
int y = x;
int div = z / y;
if (x) { ...}
But also warns here, which doesn't necessarily make sense:
int foo(int x, int y, int z) {
int div = z / y;
if (x) return div;
return 0;
}
foo(a, a, b); // only coincidentally the same symbol
What would you think about turning this (and/or the null dereference check)
into a CFG-based check instead? We lose the first example (and cases where
inlining would help), but fix the second, and very possibly speed up analysis.
CFG analysis is also more capable of proving that something happens on all
paths rather than just some, since that's just propagating information along
the graph.
Jordan
On Jul 10, 2014, at 9:55 , Anders Rönnholm anders.ronnh...@evidente.se wrote:
Great, no problem. I'll move forward with my dereference then check patch now
that this one is commited, which will be pretty similar.
//Anders
...
Anders Rönnholm Senior Engineer
Evidente ES East AB Warfvinges väg 34 SE-112 51 Stockholm Sweden
Mobile:+46 (0)70 912 42 54
E-mail:anders.ronnh...@evidente.se
www.evidente.se
Från: Jordan Rose [jordan_r...@apple.com]
Skickat: den 10 juli 2014 18:20
Till: Anders Rönnholm
Cc: cfe-commits@cs.uiuc.edu; Daniel Marjamäki
Ämne: Re: [PATCH] Division by zero
Thank you for going through so many rounds of review on this. Committed in
r212731! (The one change I made was to reset the test in isZero to use assume
instead of assumeDual, now that my confusion has been fixed.)
Jordan
___
cfe-commits mailing list
cfe-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
Re: [PATCH] Division by zero
Thank you for going through so many rounds of review on this. Committed in r212731! (The one change I made was to reset the test in isZero to use assume instead of assumeDual, now that my confusion has been fixed.) Jordan ___ cfe-commits mailing list cfe-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
Re: [PATCH] Division by zero
Great, no problem. I'll move forward with my dereference then check patch now that this one is commited, which will be pretty similar. //Anders ... Anders Rönnholm Senior Engineer Evidente ES East AB Warfvinges väg 34 SE-112 51 Stockholm Sweden Mobile:+46 (0)70 912 42 54 E-mail:anders.ronnh...@evidente.se www.evidente.se Från: Jordan Rose [jordan_r...@apple.com] Skickat: den 10 juli 2014 18:20 Till: Anders Rönnholm Cc: cfe-commits@cs.uiuc.edu; Daniel Marjamäki Ämne: Re: [PATCH] Division by zero Thank you for going through so many rounds of review on this. Committed in r212731! (The one change I made was to reset the test in isZero to use assume instead of assumeDual, now that my confusion has been fixed.) Jordan ___ cfe-commits mailing list cfe-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
Re: [PATCH] Division by zero
We don't get into the if-case because we never get a Loc from Sval therefore it
always returns false and our tests are passed.
OptionalLoc L = S.getAsLoc();
if (!L)
return false;
Um. Right, we shouldn't get a Loc at that point. But we don't need a Loc. We
just need whatever NonLoc symbol is there, and we can check to see if that is
0. Why did we need a Loc again?
Anyway, we shouldn't have features that don't show up in the tests. I think
this code was either trying to avoid emitting duplicate messages if the
denominator is known to be 0 already (which won't happen because that's a fatal
error), or trying to avoid adding the symbol to the map if it's known not to be
0 (which is not what it's doing now, or at least not what it says it's doing).
The latter is kind of useful but it's just optimization.
Jordan
Are you suggesting that we use NonLoc instead of Loc? Can we get an Sval from
NonLoc? We needed Loc to get sval from state instead of looping the exploded
node to find the range before the division.
Let's stop for a second. We want to check if the denominator's value is equal
to 0. At this point in execution, the denominator expression is an rvalue, i.e.
the integer value has already been loaded from the variable. That means the
value of the denominator expression is going to be a NonLoc (because it
represents an integer value rather than a location). Additionally, we don't
need to load anything, because we're already past the point in analysis where
the variable is loaded.
So if I'm right, you should be able to just take the denominator SVal as is,
and feed it into the constraint manager if it's defined.
Jordan
Yes it seems like we can do that, don't know why it was a problem previously
(before we began looping the exploded node) because this was what we did.
I have made a new patch now.
//Anders
Index: lib/StaticAnalyzer/Checkers/TestAfterDivZeroChecker.cpp
===
--- lib/StaticAnalyzer/Checkers/TestAfterDivZeroChecker.cpp (revision 0)
+++ lib/StaticAnalyzer/Checkers/TestAfterDivZeroChecker.cpp (revision 0)
@@ -0,0 +1,271 @@
+//== TestAfterDivZeroChecker.cpp - Test after division by zero checker --*--==//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===--===//
+//
+// This defines TestAfterDivZeroChecker, 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
+#include llvm/ADT/FoldingSet.h
+
+using namespace clang;
+using namespace ento;
+
+namespace {
+
+class ZeroState {
+private:
+ SymbolRef ZeroSymbol;
+ unsigned BlockID;
+ const StackFrameContext *SFC;
+
+public:
+ ZeroState(SymbolRef S, unsigned B, const StackFrameContext *SFC)
+ : ZeroSymbol(S), BlockID(B), SFC(SFC) {}
+
+ const StackFrameContext *getStackFrameContext() const { return SFC; }
+
+ bool operator==(const ZeroState X) const {
+return BlockID == X.BlockID SFC == X.SFC ZeroSymbol == X.ZeroSymbol;
+ }
+
+ bool operator(const ZeroState X) const {
+if (BlockID != X.BlockID)
+ return BlockID X.BlockID;
+if (SFC != X.SFC)
+ return SFC X.SFC;
+return ZeroSymbol X.ZeroSymbol;
+ }
+
+ void Profile(llvm::FoldingSetNodeID ID) const {
+ID.AddInteger(BlockID);
+ID.AddPointer(SFC);
+ID.AddPointer(ZeroSymbol);
+ }
+};
+
+class DivisionBRVisitor : public BugReporterVisitorImplDivisionBRVisitor {
+private:
+ SymbolRef ZeroSymbol;
+ const StackFrameContext *SFC;
+ bool Satisfied = false;
+
+public:
+ DivisionBRVisitor(SymbolRef ZeroSymbol, const StackFrameContext *SFC)
+ : ZeroSymbol(ZeroSymbol), SFC(SFC) {}
+
+ void Profile(llvm::FoldingSetNodeID ID) const override {
+ID.Add(ZeroSymbol);
+ID.Add(SFC);
+ }
+
+ PathDiagnosticPiece *VisitNode(const ExplodedNode *Succ,
+ const ExplodedNode *Pred,
+ BugReporterContext BRC,
+ BugReport BR) override;
+};
+
+class TestAfterDivZeroChecker
+: public Checkercheck::PreStmtBinaryOperator, check::BranchCondition,
+ check::EndFunction {
+ mutable std::unique_ptrBuiltinBug DivZeroBug;
+ void reportBug(SVal Val, CheckerContext C) const;
+
+public:
+ void checkPreStmt(const BinaryOperator *B, CheckerContext C) const;
+ void checkBranchCondition(const Stmt *Condition, CheckerContext C) const;
+ void
Re: [PATCH] Division by zero
On Jul 7, 2014, at 2:28 , Anders Rönnholm anders.ronnh...@evidente.se wrote: We don't get into the if-case because we never get a Loc from Sval therefore it always returns false and our tests are passed. OptionalLoc L = S.getAsLoc(); if (!L) return false; Um. Right, we shouldn't get a Loc at that point. But we don't need a Loc. We just need whatever NonLoc symbol is there, and we can check to see if that is 0. Why did we need a Loc again? Anyway, we shouldn't have features that don't show up in the tests. I think this code was either trying to avoid emitting duplicate messages if the denominator is known to be 0 already (which won't happen because that's a fatal error), or trying to avoid adding the symbol to the map if it's known not to be 0 (which is not what it's doing now, or at least not what it says it's doing). The latter is kind of useful but it's just optimization. Jordan Are you suggesting that we use NonLoc instead of Loc? Can we get an Sval from NonLoc? We needed Loc to get sval from state instead of looping the exploded node to find the range before the division. Let's stop for a second. We want to check if the denominator's value is equal to 0. At this point in execution, the denominator expression is an rvalue, i.e. the integer value has already been loaded from the variable. That means the value of the denominator expression is going to be a NonLoc (because it represents an integer value rather than a location). Additionally, we don't need to load anything, because we're already past the point in analysis where the variable is loaded. So if I'm right, you should be able to just take the denominator SVal as is, and feed it into the constraint manager if it's defined. Jordan___ cfe-commits mailing list cfe-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
Re: [PATCH] Division by zero
Huh. So, I changed it back to the way it was:
SVal Val = State-getRawSVal(*L);
if (Val == S) {
OptionalDefinedSVal DSV = Val.getAsDefinedSVal();
ConstraintManager CM = C.getConstraintManager();
if (!CM.assume(State, *DSV, false))
return true;
}
and tried running the tests. No failures. Then I flipped the false to true
in the assume...and still no failures. So we must never be getting into that
if-case!
What would that affect?
Jordan
We don't get into the if-case because we never get a Loc from Sval therefore it
always returns false and our tests are passed.
OptionalLoc L = S.getAsLoc();
if (!L)
return false;
Um. Right, we shouldn't get a Loc at that point. But we don't need a Loc. We
just need whatever NonLoc symbol is there, and we can check to see if that is
0. Why did we need a Loc again?
Anyway, we shouldn't have features that don't show up in the tests. I think
this code was either trying to avoid emitting duplicate messages if the
denominator is known to be 0 already (which won't happen because that's a fatal
error), or trying to avoid adding the symbol to the map if it's known not to be
0 (which is not what it's doing now, or at least not what it says it's doing).
The latter is kind of useful but it's just optimization.
Jordan
Are you suggesting that we use NonLoc instead of Loc? Can we get an Sval from
NonLoc? We needed Loc to get sval from state instead of looping the exploded
node to find the range before the division.
Or should we remove the isZero check? We reason we have this is the latter,
avoid adding the symbol to the map if it's known not to be 0.
//Anders
___
cfe-commits mailing list
cfe-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
Re: [PATCH] Division by zero
On Jul 4, 2014, at 1:15 , Anders Rönnholm anders.ronnh...@evidente.se wrote:
Huh. So, I changed it back to the way it was:
SVal Val = State-getRawSVal(*L);
if (Val == S) {
OptionalDefinedSVal DSV = Val.getAsDefinedSVal();
ConstraintManager CM = C.getConstraintManager();
if (!CM.assume(State, *DSV, false))
return true;
}
and tried running the tests. No failures. Then I flipped the false to
true in the assume...and still no failures. So we must never be getting
into that if-case!
What would that affect?
Jordan
We don't get into the if-case because we never get a Loc from Sval therefore
it always returns false and our tests are passed.
OptionalLoc L = S.getAsLoc();
if (!L)
return false;
Um. Right, we shouldn't get a Loc at that point. But we don't need a Loc. We
just need whatever NonLoc symbol is there, and we can check to see if that is
0. Why did we need a Loc again?
Anyway, we shouldn't have features that don't show up in the tests. I think
this code was either trying to avoid emitting duplicate messages if the
denominator is known to be 0 already (which won't happen because that's a fatal
error), or trying to avoid adding the symbol to the map if it's known not to be
0 (which is not what it's doing now, or at least not what it says it's doing).
The latter is kind of useful but it's just optimization.
Jordan
___
cfe-commits mailing list
cfe-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
Re: [PATCH] Division by zero
Huh. So, I changed it back to the way it was:
SVal Val = State-getRawSVal(*L);
if (Val == S) {
OptionalDefinedSVal DSV = Val.getAsDefinedSVal();
ConstraintManager CM = C.getConstraintManager();
if (!CM.assume(State, *DSV, false))
return true;
}
and tried running the tests. No failures. Then I flipped the false to true
in the assume...and still no failures. So we must never be getting into that
if-case!
What would that affect?
Jordan
We don't get into the if-case because we never get a Loc from Sval therefore it
always returns false and our tests are passed.
OptionalLoc L = S.getAsLoc();
if (!L)
return false;
Should we go back to how it was previously and walk backwards on the exploded
node or do you have a better idea? Or leave it as it is? How can i write a test
were we actually get a Loc?
bool TestAfterDivZeroChecker::isZero(SVal S, CheckerContext C) const {
const ExplodedNode *N = C.getPredecessor();
while (N) {
ProgramStateRef State = N-getState();
if (const MemRegion *MR = C.getLocationRegionIfPostStore(N)) {
SVal Val = State-getSVal(MR);
if (Val == S) {
OptionalDefinedSVal DSV = Val.getAsDefinedSVal();
ConstraintManager CM = C.getConstraintManager();
ProgramStateRef stateNotZero, stateZero;
std::tie(stateNotZero, stateZero) = CM.assumeDual(State, *DSV);
if (!stateNotZero) {
assert(stateZero);
return true;
}
}
}
N = N-pred_empty() ? nullptr : *(N-pred_begin());
}
return false;
}
//Anders
___
cfe-commits mailing list
cfe-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
Re: [PATCH] Division by zero
On Jul 2, 2014, at 5:27 , Anders Rönnholm anders.ronnh...@evidente.se wrote:
Hi,
New iteration with comments addressed.
I still don't understand why this is a loop at all:
+bool TestAfterDivZeroChecker::isZero(SVal S, CheckerContext C) const {
+ OptionalLoc L;
+ if (!(L = S.getAsLoc())) return false;
+
+ const ExplodedNode *N = C.getPredecessor();
+ while (N) {
+ProgramStateRef State = N-getState();
+
+// Find the most recent expression bound to the symbol in the current
+// context.
+SVal Val = State-getRawSVal(L.getValue());
+if (Val == S) {
+ OptionalDefinedSVal DSV = Val.getAsDefinedSVal();
+ return !C.getConstraintManager().assume(State, *DSV, false);
+}
+N = N-pred_empty() ? nullptr : *(N-pred_begin());
+ }
+ return false;
+}
What's wrong with Val = C.getState()-getRawSVal(*L)?
Sorry, thought I still had to loop, I have removed it now.
Also, I'm reading your check as saying that the value is zero if there does
not exist a state where DSV is not non-zero. I must be reading something
wrong (since you have test cases), but what? Can you explain it to me?
Yes it looks kinda strange. I have changed it slightly to more resemble how
DivZeroChecker does it.
Huh. So, I changed it back to the way it was:
SVal Val = State-getRawSVal(*L);
if (Val == S) {
OptionalDefinedSVal DSV = Val.getAsDefinedSVal();
ConstraintManager CM = C.getConstraintManager();
if (!CM.assume(State, *DSV, false))
return true;
}
and tried running the tests. No failures. Then I flipped the false to true
in the assume...and still no failures. So we must never be getting into that
if-case!
What would that affect?
Jordan___
cfe-commits mailing list
cfe-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
Re: [PATCH] Division by zero
I still don't understand why this is a loop at all:
+bool TestAfterDivZeroChecker::isZero(SVal S, CheckerContext C) const {
+ OptionalLoc L;
+ if (!(L = S.getAsLoc())) return false;
+
+ const ExplodedNode *N = C.getPredecessor();
+ while (N) {
+ProgramStateRef State = N-getState();
+
+// Find the most recent expression bound to the symbol in the current
+// context.
+SVal Val = State-getRawSVal(L.getValue());
+if (Val == S) {
+ OptionalDefinedSVal DSV = Val.getAsDefinedSVal();
+ return !C.getConstraintManager().assume(State, *DSV, false);
+}
+N = N-pred_empty() ? nullptr : *(N-pred_begin());
+ }
+ return false;
+}
What's wrong with Val = C.getState()-getRawSVal(*L)?
Also, I'm reading your check as saying that the value is zero if there does not
exist a state where DSV is not non-zero. I must be reading something wrong
(since you have test cases), but what? Can you explain it to me?
Smaller comments:
+ OptionalLoc L;
+ if (!(L = S.getAsLoc())) return false;
I personally think this is clearer if you put the assignment in with the
declaration.
+ DivZeroMapTy DivZeroes = State-getDivZeroMap();
+ if (DivZeroes.isEmpty())
+return;
+
+ for (llvm::ImmutableSetZeroState::iterator I = DivZeroes.begin(),
+ E = DivZeroes.end();
+ I != E; ++I) {
+ZeroState ZS = *I;
+if (ZS.getStackFrameContext() == C.getStackFrame())
+ State = State-removeDivZeroMap(ZS);
+ }
+ C.addTransition(State);
I should have mentioned this sooner, but it's more efficient if you use the map
factory to remove everything first and then generate one new state with the
final map. See MallocChecker::checkDeadSymbols for an example of how to do this
(they're using it for RegionState).
Jordan
On Jun 24, 2014, at 6:29 , Anders Rönnholm anders.ronnh...@evidente.se wrote:
Thanks for your comments. Here's a new patch.
//Anders
Från: Jordan Rose [jordan_r...@apple.com]
Skickat: den 19 juni 2014 18:17
Till: Anders Rönnholm
Cc: cfe-commits@cs.uiuc.edu; Daniel Marjamäki
Ämne: Re: [PATCH] Division by zero
On Jun 18, 2014, at 7:30 , Anders Rönnholm anders.ronnh...@evidente.se
wrote:
Changes according to comments.
I'm pretty sure PVS-Studio does not have this checker, this bug has been
seen in production code.
Oops, noticing more things:
+ const ExplodedNode *N = C.getPredecessor();
+ while (N) {
+ProgramStateRef State = N-getState();
+
+// Find the most recent expression bound to the symbol in the current
+// context.
+if (const MemRegion *MR = C.getLocationRegionIfPostStore(N)) {
+ SVal Val = State-getSVal(MR);
+ if (Val == S) {
+OptionalDefinedSVal DSV = Val.getAsDefinedSVal();
+if (!C.getConstraintManager().assume(State, *DSV, false))
+ return true;
+ }
+}
+N = N-pred_empty() ? nullptr : *(N-pred_begin());
+ }
Why are you looking for the last time a value was stored rather than just
asking for the value in the current state?
if (OptionalLoc L = S.getAsLoc()) {
SVal V = State-getSVal(L) // or getRawSVal if you don't want a symbol
constrained to 0 to be simplified to 0.
// ...
+if (OptionalKnownSVal V = Val.getAsKnownSVal()) {
Because you needed a symbol already to get this far, you can skip this step.
Or assert it.
+void TestAfterDivZeroChecker::checkPreStmt(const BinaryOperator *B,
+ CheckerContext C) const {
Strange alignment here. If the second line doesn't fit, just indent it twice
from the start of the function...don't try to right-align it.
+if (!B-getRHS()-getType()-isScalarType())
+ return;
Dividing by a floating-point 0 is well-defined, so this should be a more
specific check.
Jordan
divzero2.diff
___
cfe-commits mailing list
cfe-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
Re: [PATCH] Division by zero
Thanks for your comments. Here's a new patch.
//Anders
Från: Jordan Rose [jordan_r...@apple.com]
Skickat: den 19 juni 2014 18:17
Till: Anders Rönnholm
Cc: cfe-commits@cs.uiuc.edu; Daniel Marjamäki
Ämne: Re: [PATCH] Division by zero
On Jun 18, 2014, at 7:30 , Anders Rönnholm anders.ronnh...@evidente.se wrote:
Changes according to comments.
I'm pretty sure PVS-Studio does not have this checker, this bug has been seen
in production code.
Oops, noticing more things:
+ const ExplodedNode *N = C.getPredecessor();
+ while (N) {
+ProgramStateRef State = N-getState();
+
+// Find the most recent expression bound to the symbol in the current
+// context.
+if (const MemRegion *MR = C.getLocationRegionIfPostStore(N)) {
+ SVal Val = State-getSVal(MR);
+ if (Val == S) {
+OptionalDefinedSVal DSV = Val.getAsDefinedSVal();
+if (!C.getConstraintManager().assume(State, *DSV, false))
+ return true;
+ }
+}
+N = N-pred_empty() ? nullptr : *(N-pred_begin());
+ }
Why are you looking for the last time a value was stored rather than just
asking for the value in the current state?
if (OptionalLoc L = S.getAsLoc()) {
SVal V = State-getSVal(L) // or getRawSVal if you don't want a symbol
constrained to 0 to be simplified to 0.
// ...
+if (OptionalKnownSVal V = Val.getAsKnownSVal()) {
Because you needed a symbol already to get this far, you can skip this step. Or
assert it.
+void TestAfterDivZeroChecker::checkPreStmt(const BinaryOperator *B,
+ CheckerContext C) const {
Strange alignment here. If the second line doesn't fit, just indent it twice
from the start of the function...don't try to right-align it.
+if (!B-getRHS()-getType()-isScalarType())
+ return;
Dividing by a floating-point 0 is well-defined, so this should be a more
specific check.
Jordan
Index: lib/StaticAnalyzer/Checkers/TestAfterDivZeroChecker.cpp
===
--- lib/StaticAnalyzer/Checkers/TestAfterDivZeroChecker.cpp (revision 0)
+++ lib/StaticAnalyzer/Checkers/TestAfterDivZeroChecker.cpp (revision 0)
@@ -0,0 +1,276 @@
+//== TestAfterDivZeroChecker.cpp - Test after division by zero checker --*--==//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===--===//
+//
+// This defines TestAfterDivZeroChecker, 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
+#include llvm/ADT/FoldingSet.h
+
+using namespace clang;
+using namespace ento;
+
+namespace {
+
+class ZeroState {
+private:
+ SymbolRef ZeroSymbol;
+ unsigned BlockID;
+ const StackFrameContext *SFC;
+
+public:
+ ZeroState(SymbolRef S, unsigned B, const StackFrameContext *SFC)
+ : ZeroSymbol(S), BlockID(B), SFC(SFC) {}
+
+ const StackFrameContext *getStackFrameContext() const { return SFC; }
+
+ bool operator==(const ZeroState X) const {
+return BlockID == X.BlockID SFC == X.SFC ZeroSymbol == X.ZeroSymbol;
+ }
+
+ bool operator(const ZeroState X) const {
+if (BlockID != X.BlockID)
+ return BlockID X.BlockID;
+if (SFC != X.SFC)
+ return SFC X.SFC;
+return ZeroSymbol X.ZeroSymbol;
+ }
+
+ void Profile(llvm::FoldingSetNodeID ID) const {
+ID.AddInteger(BlockID);
+ID.AddPointer(SFC);
+ID.AddPointer(ZeroSymbol);
+ }
+};
+
+class DivisionBRVisitor : public BugReporterVisitorImplDivisionBRVisitor {
+private:
+ SymbolRef ZeroSymbol;
+ const StackFrameContext *SFC;
+ bool Satisfied = false;
+
+public:
+ DivisionBRVisitor(SymbolRef ZeroSymbol, const StackFrameContext *SFC)
+ : ZeroSymbol(ZeroSymbol), SFC(SFC) {}
+
+ void Profile(llvm::FoldingSetNodeID ID) const override {
+ID.Add(ZeroSymbol);
+ID.Add(SFC);
+ }
+
+ PathDiagnosticPiece *VisitNode(const ExplodedNode *Succ,
+ const ExplodedNode *Pred,
+ BugReporterContext BRC,
+ BugReport BR) override;
+};
+
+class TestAfterDivZeroChecker
+: public Checkercheck::PreStmtBinaryOperator, check::BranchCondition,
+ check::EndFunction {
+ mutable std::unique_ptrBuiltinBug DivZeroBug;
+ void reportBug(SVal Val, CheckerContext C) const;
+
+public:
+ void checkPreStmt(const BinaryOperator *B, CheckerContext C) const;
+ void
Re: [PATCH] Division by zero
On Jun 18, 2014, at 7:30 , Anders Rönnholm anders.ronnh...@evidente.se wrote:
Changes according to comments.
I'm pretty sure PVS-Studio does not have this checker, this bug has been seen
in production code.
Oops, noticing more things:
+ const ExplodedNode *N = C.getPredecessor();
+ while (N) {
+ProgramStateRef State = N-getState();
+
+// Find the most recent expression bound to the symbol in the current
+// context.
+if (const MemRegion *MR = C.getLocationRegionIfPostStore(N)) {
+ SVal Val = State-getSVal(MR);
+ if (Val == S) {
+OptionalDefinedSVal DSV = Val.getAsDefinedSVal();
+if (!C.getConstraintManager().assume(State, *DSV, false))
+ return true;
+ }
+}
+N = N-pred_empty() ? nullptr : *(N-pred_begin());
+ }
Why are you looking for the last time a value was stored rather than just
asking for the value in the current state?
if (OptionalLoc L = S.getAsLoc()) {
SVal V = State-getSVal(L) // or getRawSVal if you don't want a symbol
constrained to 0 to be simplified to 0.
// ...
+if (OptionalKnownSVal V = Val.getAsKnownSVal()) {
Because you needed a symbol already to get this far, you can skip this step. Or
assert it.
+void TestAfterDivZeroChecker::checkPreStmt(const BinaryOperator *B,
+ CheckerContext C) const {
Strange alignment here. If the second line doesn't fit, just indent it twice
from the start of the function...don't try to right-align it.
+if (!B-getRHS()-getType()-isScalarType())
+ return;
Dividing by a floating-point 0 is well-defined, so this should be a more
specific check.
Jordan
___
cfe-commits mailing list
cfe-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
Re: [PATCH] Division by zero
Changes according to comments.
I'm pretty sure PVS-Studio does not have this checker, this bug has been seen
in production code.
//Anders
Från: Jordan Rose [jordan_r...@apple.com]
Skickat: den 16 juni 2014 18:39
Till: Anders Rönnholm
Cc: cfe-commits@cs.uiuc.edu; Daniel Marjamäki
Ämne: Re: [PATCH] Division by zero
On Jun 5, 2014, at 5:16 , Anders Rönnholm
anders.ronnh...@evidente.semailto:anders.ronnh...@evidente.se wrote:
Hi Jordan,
New patch and some comments.
+inline void inline_func3(int x) {
+ var = 77 / x;
+}
+void ok_inline(int x) {
+ var = 77 / x;
+ inline_func3(x);
+ if (x==0){}
+}
This is an example where we should still be warning. Why aren't we?
It doesn't warn here because blockid is in the value and not the key as it
should. I have made a set of symbol-block-frame as you suggested and that fixes
this problem.
+// RUN: %clang_cc1 -analyze -analyzer-checker=core.DivideZero2
-analyzer-output=text -verify %s
We should never be running path-sensitive checks without the rest of the core
checkers.
There is a small problem here. It looks like the DivideZero checker makes the
assumtion that because it can't see that a variable is zero then it's not zero
so all variables in our tests have the range reg_$0x : { [-2147483648, -1],
[1, 2147483647] }. I have removed the range check in my checker to make it work
otherwise i would have to change the DivideZero checker.
Hm. The important thing is that a variable is zero before the division; in the
absence of this checker, it's a reasonable assumption that it's zero if we made
it past the division. Would it make sense to step back through ExplodedNodes
instead until we found a ProgramPoint before the division statement itself, and
then look at the value of the variable in that state?
+ const ZeroState *ZS = C.getState()-getDivZeroMap(SR);
+ return (ZS *ZS == ZeroState(C.getBlockID(), C.getStackFrame()));
...now I'm wondering about the wisdom of using a map for this. What if the same
symbol is constrained in two stack frames? Would it make more sense to keep
around a set of symbol-block-frame triples, rather than a map from symbols to
block/frame pairs?
Or can this not happen because a value can only be used once along a certain
path before it is constrained to be non-zero?
Changed to a set of symbol-block-frame triples to make the above example work.
+def DivZeroChecker2 : CheckerDivideZero2,
+ HelpTextCheck for division by variable that is later compared against 0.
Either the comparison is useless or there is division by zero.,
+ DescFileDivZeroChecker2.cpp;
+
I'm not sure this is really a core checker, since it's safe to run the analyzer
without it. But we don't have a category for useful C checks that should be on
by default yet. Anton was looking at reorganizing the categories, but the
problem is that everything outside of alpha is something people expect to be
able to rely on when using scan-build.
Any ideas for this particular checker, or for the general issue?
I ok with having it as an alpha, or something else. I just put it in core since
the other DivideZero checker is there.
Let's put it in alpha for now.
Code comments:
+class DivZeroChecker2
+: public Checkercheck::PreStmtBinaryOperator, check::BranchCondition,
+ check::EndFunction {
Since we're not doing the normal divide-by-zero check in this checker, let's
name it something else. TestAfterDivideChecker, maybe?
+ DivZeroMapTy DivZeroes = C.getState()-getDivZeroMap();
+ if (DivZeroes.isEmpty())
+return false;
+
+ for (llvm::ImmutableSetZeroState::iterator I = DivZeroes.begin(),
+ E = DivZeroes.end();
+ I != E; ++I) {
+if (*I == ZeroState(SR, C.getBlockID(), C.getStackFrame()))
+ return true;
+ }
+ return false;
This whole thing can be simplified quite a bit:
ZeroState ZS(SR, C.getBlockID(), C.getStackFrame());
return C.getState()-containsDivZeroMap(ZS);
...and other than that it's looking pretty good! Has this checker found any
real bugs that you know of? (Does PVS-Studio have a similar checker?)
JordanIndex: include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h
===
--- include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h (revision 210244)
+++ include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h (working copy)
@@ -174,8 +172,13 @@
return Pred-getLocationContext()-getAnalysisDeclContext();
}
- /// \brief If the given node corresponds to a PostStore program point, retrieve
- /// the location region as it was uttered in the code.
+ /// \brief Get the blockID.
+ unsigned getBlockID() const {
+return NB.getContext().getBlock()-getBlockID();
+ }
+
+ /// \brief If the given node corresponds to a PostStore program point,
+ /// retrieve the location region as it was uttered in the code
Re: [PATCH] Division by zero
Ping.
-Original Message-
From: Anders Rönnholm
Sent: den 5 juni 2014 14:17
To: Jordan Rose
Cc: cfe-commits@cs.uiuc.edu; Daniel Marjamäki
Subject: Re: [PATCH] Division by zero
Hi Jordan,
New patch and some comments.
+inline void inline_func3(int x) {
+ var = 77 / x;
+}
+void ok_inline(int x) {
+ var = 77 / x;
+ inline_func3(x);
+ if (x==0){}
+}
This is an example where we should still be warning. Why aren't we?
It doesn't warn here because blockid is in the value and not the key as it
should. I have made a set of symbol-block-frame as you suggested and that
fixes this problem.
+// RUN: %clang_cc1 -analyze -analyzer-checker=core.DivideZero2 -analyzer-
output=text -verify %s
We should never be running path-sensitive checks without the rest of the
core checkers.
There is a small problem here. It looks like the DivideZero checker makes the
assumtion that because it can't see that a variable is zero then it's not
zero so
all variables in our tests have the range reg_$0x : { [-2147483648, -1], [1,
2147483647] }. I have removed the range check in my checker to make it
work otherwise i would have to change the DivideZero checker.
+ const ZeroState *ZS = C.getState()-getDivZeroMap(SR);
+ return (ZS *ZS == ZeroState(C.getBlockID(), C.getStackFrame()));
...now I'm wondering about the wisdom of using a map for this. What if the
same symbol is constrained in two stack frames? Would it make more sense
to keep around a set of symbol-block-frame triples, rather than a map from
symbols to block/frame pairs?
Or can this not happen because a value can only be used once along a certain
path before it is constrained to be non-zero?
Changed to a set of symbol-block-frame triples to make the above example
work.
+def DivZeroChecker2 : CheckerDivideZero2,
+ HelpTextCheck for division by variable that is later compared against 0.
Either the comparison is useless or there is division by zero.,
+ DescFileDivZeroChecker2.cpp;
+
I'm not sure this is really a core checker, since it's safe to run the
analyzer
without it. But we don't have a category for useful C checks that should be
on by default yet. Anton was looking at reorganizing the categories, but the
problem is that everything outside of alpha is something people expect to
be able to rely on when using scan-build.
Any ideas for this particular checker, or for the general issue?
I ok with having it as an alpha, or something else. I just put it in core
since the
other DivideZero checker is there.
//Anders
divzero2.diff
Description: divzero2.diff
___
cfe-commits mailing list
cfe-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
Re: [PATCH] Division by zero
On Jun 5, 2014, at 5:16 , Anders Rönnholm anders.ronnh...@evidente.se wrote:
Hi Jordan,
New patch and some comments.
+inline void inline_func3(int x) {
+ var = 77 / x;
+}
+void ok_inline(int x) {
+ var = 77 / x;
+ inline_func3(x);
+ if (x==0){}
+}
This is an example where we should still be warning. Why aren't we?
It doesn't warn here because blockid is in the value and not the key as it
should. I have made a set of symbol-block-frame as you suggested and that
fixes this problem.
+// RUN: %clang_cc1 -analyze -analyzer-checker=core.DivideZero2
-analyzer-output=text -verify %s
We should never be running path-sensitive checks without the rest of the
core checkers.
There is a small problem here. It looks like the DivideZero checker makes the
assumtion that because it can't see that a variable is zero then it's not
zero so all variables in our tests have the range reg_$0x : { [-2147483648,
-1], [1, 2147483647] }. I have removed the range check in my checker to make
it work otherwise i would have to change the DivideZero checker.
Hm. The important thing is that a variable is zero before the division; in the
absence of this checker, it's a reasonable assumption that it's zero if we made
it past the division. Would it make sense to step back through ExplodedNodes
instead until we found a ProgramPoint before the division statement itself, and
then look at the value of the variable in that state?
+ const ZeroState *ZS = C.getState()-getDivZeroMap(SR);
+ return (ZS *ZS == ZeroState(C.getBlockID(), C.getStackFrame()));
...now I'm wondering about the wisdom of using a map for this. What if the
same symbol is constrained in two stack frames? Would it make more sense to
keep around a set of symbol-block-frame triples, rather than a map from
symbols to block/frame pairs?
Or can this not happen because a value can only be used once along a certain
path before it is constrained to be non-zero?
Changed to a set of symbol-block-frame triples to make the above example work.
+def DivZeroChecker2 : CheckerDivideZero2,
+ HelpTextCheck for division by variable that is later compared against
0. Either the comparison is useless or there is division by zero.,
+ DescFileDivZeroChecker2.cpp;
+
I'm not sure this is really a core checker, since it's safe to run the
analyzer without it. But we don't have a category for useful C checks that
should be on by default yet. Anton was looking at reorganizing the
categories, but the problem is that everything outside of alpha is
something people expect to be able to rely on when using scan-build.
Any ideas for this particular checker, or for the general issue?
I ok with having it as an alpha, or something else. I just put it in core
since the other DivideZero checker is there.
Let's put it in alpha for now.
Code comments:
+class DivZeroChecker2
+: public Checkercheck::PreStmtBinaryOperator, check::BranchCondition,
+ check::EndFunction {
Since we're not doing the normal divide-by-zero check in this checker, let's
name it something else. TestAfterDivideChecker, maybe?
+ DivZeroMapTy DivZeroes = C.getState()-getDivZeroMap();
+ if (DivZeroes.isEmpty())
+return false;
+
+ for (llvm::ImmutableSetZeroState::iterator I = DivZeroes.begin(),
+ E = DivZeroes.end();
+ I != E; ++I) {
+if (*I == ZeroState(SR, C.getBlockID(), C.getStackFrame()))
+ return true;
+ }
+ return false;
This whole thing can be simplified quite a bit:
ZeroState ZS(SR, C.getBlockID(), C.getStackFrame());
return C.getState()-containsDivZeroMap(ZS);
...and other than that it's looking pretty good! Has this checker found any
real bugs that you know of? (Does PVS-Studio have a similar checker?)
Jordan___
cfe-commits mailing list
cfe-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
Re: [PATCH] Division by zero
Hi Jordan,
New patch and some comments.
+inline void inline_func3(int x) {
+ var = 77 / x;
+}
+void ok_inline(int x) {
+ var = 77 / x;
+ inline_func3(x);
+ if (x==0){}
+}
This is an example where we should still be warning. Why aren't we?
It doesn't warn here because blockid is in the value and not the key as it
should. I have made a set of symbol-block-frame as you suggested and that fixes
this problem.
+// RUN: %clang_cc1 -analyze -analyzer-checker=core.DivideZero2
-analyzer-output=text -verify %s
We should never be running path-sensitive checks without the rest of the core
checkers.
There is a small problem here. It looks like the DivideZero checker makes the
assumtion that because it can't see that a variable is zero then it's not zero
so all variables in our tests have the range reg_$0x : { [-2147483648, -1],
[1, 2147483647] }. I have removed the range check in my checker to make it work
otherwise i would have to change the DivideZero checker.
+ const ZeroState *ZS = C.getState()-getDivZeroMap(SR);
+ return (ZS *ZS == ZeroState(C.getBlockID(), C.getStackFrame()));
...now I'm wondering about the wisdom of using a map for this. What if the same
symbol is constrained in two stack frames? Would it make more sense to keep
around a set of symbol-block-frame triples, rather than a map from symbols to
block/frame pairs?
Or can this not happen because a value can only be used once along a certain
path before it is constrained to be non-zero?
Changed to a set of symbol-block-frame triples to make the above example work.
+def DivZeroChecker2 : CheckerDivideZero2,
+ HelpTextCheck for division by variable that is later compared against 0.
Either the comparison is useless or there is division by zero.,
+ DescFileDivZeroChecker2.cpp;
+
I'm not sure this is really a core checker, since it's safe to run the analyzer
without it. But we don't have a category for useful C checks that should be on
by default yet. Anton was looking at reorganizing the categories, but the
problem is that everything outside of alpha is something people expect to be
able to rely on when using scan-build.
Any ideas for this particular checker, or for the general issue?
I ok with having it as an alpha, or something else. I just put it in core since
the other DivideZero checker is there.
//AndersIndex: lib/StaticAnalyzer/Checkers/DivZeroChecker2.cpp
===
--- lib/StaticAnalyzer/Checkers/DivZeroChecker2.cpp (revision 0)
+++ lib/StaticAnalyzer/Checkers/DivZeroChecker2.cpp (revision 0)
@@ -0,0 +1,266 @@
+//== 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
+#include llvm/ADT/FoldingSet.h
+
+using namespace clang;
+using namespace ento;
+
+namespace {
+
+class ZeroState {
+private:
+ SymbolRef ZeroSymbol;
+ unsigned BlockID;
+ const StackFrameContext *SFC;
+
+public:
+ ZeroState(SymbolRef S, unsigned B, const StackFrameContext *SFC)
+ : ZeroSymbol(S), BlockID(B), SFC(SFC) {}
+
+ const StackFrameContext *getStackFrameContext() const { return SFC; }
+
+ bool operator==(const ZeroState X) const {
+return BlockID == X.BlockID SFC == X.SFC ZeroSymbol == X.ZeroSymbol;
+ }
+
+ bool operator(const ZeroState X) const {
+if (BlockID != X.BlockID)
+ return BlockID X.BlockID;
+if (SFC != X.SFC)
+ return SFC X.SFC;
+return ZeroSymbol X.ZeroSymbol;
+ }
+
+ void Profile(llvm::FoldingSetNodeID ID) const {
+ID.AddInteger(BlockID);
+ID.AddPointer(SFC);
+ID.AddPointer(ZeroSymbol);
+ }
+};
+
+class DivisionBRVisitor : public BugReporterVisitorImplDivisionBRVisitor {
+private:
+ SymbolRef ZeroSymbol;
+ const StackFrameContext *SFC;
+ bool Satisfied = false;
+
+public:
+ DivisionBRVisitor(SymbolRef ZeroSymbol, const StackFrameContext *SFC)
+ : ZeroSymbol(ZeroSymbol), SFC(SFC) {}
+
+ void Profile(llvm::FoldingSetNodeID ID) const override {
+ID.Add(ZeroSymbol);
+ID.Add(SFC);
+ }
+
+ PathDiagnosticPiece *VisitNode(const ExplodedNode *Succ,
+ const ExplodedNode *Pred,
+ BugReporterContext BRC,
+ BugReport BR)
Re: [PATCH] Division by zero
Okay, this definitely looks promising! I still see some issues, though.
+inline void inline_func3(int x) {
+ var = 77 / x;
+}
+void ok_inline(int x) {
+ var = 77 / x;
+ inline_func3(x);
+ if (x==0){}
+}
This is an example where we should still be warning. Why aren't we?
+// RUN: %clang_cc1 -analyze -analyzer-checker=core.DivideZero2
-analyzer-output=text -verify %s
We should never be running path-sensitive checks without the rest of the core
checkers.
On the code itself (mostly small things):
+struct ZeroState {
+private:
Small style note: this should probably be a class. The LLVM coding standards
prefer to use 'struct' only when all members are public.
http://llvm.org/docs/CodingStandards.html#use-of-class-and-struct-keywords
+ unsigned B;
I'd appreciate this having a more descriptive name, like a full BlockID.
+class DivisionBRVisitor : public BugReporterVisitorImplDivisionBRVisitor {
+protected:
Why protected?
+ DivisionBRVisitor(KnownSVal V) : V(V), Satisfied(false) {}
Now that we're using C++11, it probably makes more sense to move the
initialization of Satisfied into the member declaration itself. The
constructor should also be marked explicit.
(But good job making the visitor at all. This makes the error report much more
helpful!)
+ mutable std::unique_ptrBuiltinBug BB;
The name of this variable should describe the bug, not just be the type.
+bool DivZeroChecker2::hasDivZeroMapSval(SVal Var,
+const CheckerContext C) const {
The SVal part of this really isn't important, so I would drop it from the
name. But...
+ const ZeroState *ZS = C.getState()-getDivZeroMap(SR);
+ return (ZS *ZS == ZeroState(C.getBlockID(), C.getStackFrame()));
...now I'm wondering about the wisdom of using a map for this. What if the same
symbol is constrained in two stack frames? Would it make more sense to keep
around a set of symbol-block-frame triples, rather than a map from symbols to
block/frame pairs?
Or can this not happen because a value can only be used once along a certain
path before it is constrained to be non-zero?
+ } else if (const ImplicitCastExpr *IE =
+ dyn_castImplicitCastExpr(Condition)) {
+SVal Val = C.getSVal(IE-getSubExpr());
+
+if (hasDivZeroMapSval(Val, C))
+ reportBug(Value being compared against zero has already been used for
+division,
+Val, C);
+ }
I'm not sure there's always an ImplicitCastExpr. There is in C++, of course,
but I don't think C uses an integer-to-boolean conversion for if-statements. I
suggest renaming the test to div-zero2.c, and then having two RUN lines, with
the second including -x c++.
+def DivZeroChecker2 : CheckerDivideZero2,
+ HelpTextCheck for division by variable that is later compared against 0.
Either the comparison is useless or there is division by zero.,
+ DescFileDivZeroChecker2.cpp;
+
I'm not sure this is really a core checker, since it's safe to run the analyzer
without it. But we don't have a category for useful C checks that should be on
by default yet. Anton was looking at reorganizing the categories, but the
problem is that everything outside of alpha is something people expect to be
able to rely on when using scan-build.
Any ideas for this particular checker, or for the general issue?
Jordan
___
cfe-commits mailing list
cfe-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
Re: [PATCH] Division by zero
Ping
Från: Anders Rönnholm
Skickat: den 16 maj 2014 13:15
Till: Jordan Rose
Cc: cfe-commits@cs.uiuc.edu; Daniel Marjamäki
Ämne: Re: [PATCH] Division by zero
Clearing the map at the end of a function is a start, but you ought to make
sure you don't clear it for the function that called this one. I suppose that's
a refinement that can be made later, since it only produces false negatives.
(I'm not super happy about not being able to merge branches within the
function, though.)
No I don't like it either and would like to fix it but I haven't figured out
how. Can I find out the current function somehow when the division occurs?
I would just put the current StackFrameContext in as part of the key for the
map, or make a two-tiered map. Then when you hit the end of the function, you
can just drop things that match the current StackFrameContext.
Added as value, couldn't get it to work as key.
+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) {
+ OptionalCFGStmt stmt = BI-getAsCFGStmt();
+ if (stmt stmt-getStmt() == B)
+return (*I)-getBlockID();
+}
+ }
+ return 0;
+}
This is much too expensive. The CheckerContext has a NodeBuilder, which has a
NodeBuilderContext, which has a CFGBlock. We should just expose that somewhere
(probably on CheckerContext).
have made a get function in CheckerContext to retrieve the NodeBuilder. Is
there something better than blockid? Scope id would have been nice. Blockid
creates false negatives like below when an if-statement that has nothing to do
with the division comes in between.
Ok, only blockid exposed now
void err_not(int x, int y) {
var = 77 / x;
if (y)
int v = 0;
if (!x){}// should warn here but don't since this is a new blockid.
}
We don't currently track scopes, but that still wouldn't eliminate all the
false positives. I guess it would be closer, though—some day if we start
tracking scopes again, we can switch to that.
I don't think it makes sense to expose the whole NodeBuilder through the
CheckerContext, just the block ID.
Finally, please include some test cases with inlining so that the
clear-at-end-of-function logic is exercised.
What's the difference with inline and normal functions in this case? As I have
understood it inline functions are still treated like normal functions when
walking the ast.
When doing path-sensitive checks, the analyzer can choose to inline any
function call that it can see the definition for. I want to make sure that we
still detect test-after-uses when the test and use are both within the inlined
function and when there is an inlined function call between the test and use in
the top-most function. (The latter would hit the first issue I noted, that
clearing the entire state at the end of a function is a bit too destructive.)
I have added a couple of inline functions.
Index: test/Analysis/div-zero2.cpp
===
--- test/Analysis/div-zero2.cpp (revision 0)
+++ test/Analysis/div-zero2.cpp (revision 0)
@@ -0,0 +1,190 @@
+// RUN: %clang_cc1 -analyze -analyzer-checker=core.DivideZero2 -analyzer-output=text -verify %s
+
+int var;
+
+void err_eq(int x) {
+ var = 77 / x; // expected-note {{Division with compared value made here}}
+ if (x==0){} // expected-warning {{Value being compared against zero has already been used for division}}
+} // expected-note@-1 {{Value being compared against zero has already been used for division}}
+
+void err_eq2(int x) {
+ var = 77 / x; // expected-note {{Division with compared value made here}}
+ if (0==x){} // expected-warning {{Value being compared against zero has already been used for division}}
+} // expected-note@-1 {{Value being compared against zero has already been used for division}}
+
+void err_ne(int x) {
+ var = 77 / x; // expected-note {{Division with compared value made here}}
+ if (x!=0){} // expected-warning {{Value being compared against zero has already been used for division}}
+} // expected-note@-1 {{Value being compared against zero has already been used for division}}
+
+void err_ge(int x) {
+ var = 77 / x; // expected-note {{Division with compared value made here}}
+ if (x=0){} // expected-warning {{Value being compared against zero has already been used for division}}
+} // expected-note@-1 {{Value being compared against zero has already been used for division}}
+
+void err_le(int x) {
+ var = 77 / x; // expected-note {{Division with compared value made here}}
+ if (x=0){} // expected-warning {{Value being compared against zero has already been used for division}}
+} // expected-note@-1 {{Value being
Re: [PATCH] Division by zero
Clearing the map at the end of a function is a start, but you ought to make
sure you don't clear it for the function that called this one. I suppose that's
a refinement that can be made later, since it only produces false negatives.
(I'm not super happy about not being able to merge branches within the
function, though.)
No I don't like it either and would like to fix it but I haven't figured out
how. Can I find out the current function somehow when the division occurs?
I would just put the current StackFrameContext in as part of the key for the
map, or make a two-tiered map. Then when you hit the end of the function, you
can just drop things that match the current StackFrameContext.
Added as value, couldn't get it to work as key.
+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) {
+ OptionalCFGStmt stmt = BI-getAsCFGStmt();
+ if (stmt stmt-getStmt() == B)
+return (*I)-getBlockID();
+}
+ }
+ return 0;
+}
This is much too expensive. The CheckerContext has a NodeBuilder, which has a
NodeBuilderContext, which has a CFGBlock. We should just expose that somewhere
(probably on CheckerContext).
have made a get function in CheckerContext to retrieve the NodeBuilder. Is
there something better than blockid? Scope id would have been nice. Blockid
creates false negatives like below when an if-statement that has nothing to do
with the division comes in between.
Ok, only blockid exposed now
void err_not(int x, int y) {
var = 77 / x;
if (y)
int v = 0;
if (!x){}// should warn here but don't since this is a new blockid.
}
We don't currently track scopes, but that still wouldn't eliminate all the
false positives. I guess it would be closer, though—some day if we start
tracking scopes again, we can switch to that.
I don't think it makes sense to expose the whole NodeBuilder through the
CheckerContext, just the block ID.
Finally, please include some test cases with inlining so that the
clear-at-end-of-function logic is exercised.
What's the difference with inline and normal functions in this case? As I have
understood it inline functions are still treated like normal functions when
walking the ast.
When doing path-sensitive checks, the analyzer can choose to inline any
function call that it can see the definition for. I want to make sure that we
still detect test-after-uses when the test and use are both within the inlined
function and when there is an inlined function call between the test and use in
the top-most function. (The latter would hit the first issue I noted, that
clearing the entire state at the end of a function is a bit too destructive.)
I have added a couple of inline functions.
Index: test/Analysis/div-zero2.cpp
===
--- test/Analysis/div-zero2.cpp (revision 0)
+++ test/Analysis/div-zero2.cpp (revision 0)
@@ -0,0 +1,190 @@
+// RUN: %clang_cc1 -analyze -analyzer-checker=core.DivideZero2 -analyzer-output=text -verify %s
+
+int var;
+
+void err_eq(int x) {
+ var = 77 / x; // expected-note {{Division with compared value made here}}
+ if (x==0){} // expected-warning {{Value being compared against zero has already been used for division}}
+} // expected-note@-1 {{Value being compared against zero has already been used for division}}
+
+void err_eq2(int x) {
+ var = 77 / x; // expected-note {{Division with compared value made here}}
+ if (0==x){} // expected-warning {{Value being compared against zero has already been used for division}}
+} // expected-note@-1 {{Value being compared against zero has already been used for division}}
+
+void err_ne(int x) {
+ var = 77 / x; // expected-note {{Division with compared value made here}}
+ if (x!=0){} // expected-warning {{Value being compared against zero has already been used for division}}
+} // expected-note@-1 {{Value being compared against zero has already been used for division}}
+
+void err_ge(int x) {
+ var = 77 / x; // expected-note {{Division with compared value made here}}
+ if (x=0){} // expected-warning {{Value being compared against zero has already been used for division}}
+} // expected-note@-1 {{Value being compared against zero has already been used for division}}
+
+void err_le(int x) {
+ var = 77 / x; // expected-note {{Division with compared value made here}}
+ if (x=0){} // expected-warning {{Value being compared against zero has already been used for division}}
+} // expected-note@-1 {{Value being compared against zero has already been used for division}}
+
+void err_yes(int x) {
+ var = 77 / x; // expected-note {{Division with compared value made here}}
+ if (x){} // expected-warning {{Value
Re: [PATCH] Division by zero
On Apr 30, 2014, at 3:54 , Anders Rönnholm anders.ronnh...@evidente.se wrote:
Clearing the map at the end of a function is a start, but you ought to make
sure you don't clear it for the function that called this one. I suppose
that's a refinement that can be made later, since it only produces false
negatives. (I'm not super happy about not being able to merge branches within
the function, though.)
No I don't like it either and would like to fix it but I haven't figured out
how. Can I find out the current function somehow when the division occurs?
I would just put the current StackFrameContext in as part of the key for the
map, or make a two-tiered map. Then when you hit the end of the function, you
can just drop things that match the current StackFrameContext.
+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) {
+ OptionalCFGStmt stmt = BI-getAsCFGStmt();
+ if (stmt stmt-getStmt() == B)
+return (*I)-getBlockID();
+}
+ }
+ return 0;
+}
This is much too expensive. The CheckerContext has a NodeBuilder, which has
a NodeBuilderContext, which has a CFGBlock. We should just expose that
somewhere (probably on CheckerContext).
I have made a get function in CheckerContext to retrieve the NodeBuilder. Is
there something better than blockid? Scope id would have been nice. Blockid
creates false negatives like below when an if-statement that has nothing to
do with the division comes in between.
void err_not(int x, int y) {
var = 77 / x;
if (y)
int v = 0;
if (!x){}// should warn here but don't since this is a new blockid.
}
We don't currently track scopes, but that still wouldn't eliminate all the
false positives. I guess it would be closer, though—some day if we start
tracking scopes again, we can switch to that.
I don't think it makes sense to expose the whole NodeBuilder through the
CheckerContext, just the block ID.
Finally, please include some test cases with inlining so that the
clear-at-end-of-function logic is exercised.
What's the difference with inline and normal functions in this case? As I
have understood it inline functions are still treated like normal functions
when walking the ast.
When doing path-sensitive checks, the analyzer can choose to inline any
function call that it can see the definition for. I want to make sure that we
still detect test-after-uses when the test and use are both within the inlined
function and when there is an inlined function call between the test and use in
the top-most function. (The latter would hit the first issue I noted, that
clearing the entire state at the end of a function is a bit too destructive.)
Jordan___
cfe-commits mailing list
cfe-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
RE: [PATCH] Division by zero
Clearing the map at the end of a function is a start, but you ought to make
sure you don't clear it for the function that called this one. I suppose that's
a refinement that can be made later, since it only produces false negatives.
(I'm not super happy about not being able to merge branches within the
function, though.)
No I don't like it either and would like to fix it but I haven't figured out
how. Can I find out the current function somehow when the division occurs?
+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) {
+ OptionalCFGStmt stmt = BI-getAsCFGStmt();
+ if (stmt stmt-getStmt() == B)
+return (*I)-getBlockID();
+}
+ }
+ return 0;
+}
This is much too expensive. The CheckerContext has a NodeBuilder, which has a
NodeBuilderContext, which has a CFGBlock. We should just expose that somewhere
(probably on CheckerContext).
I have made a get function in CheckerContext to retrieve the NodeBuilder. Is
there something better than blockid? Scope id would have been nice. Blockid
creates false negatives like below when an if-statement that has nothing to do
with the division comes in between.
void err_not(int x, int y) {
var = 77 / x;
if (y)
int v = 0;
if (!x){}// should warn here but don't since this is a new blockid.
}
Finally, please include some test cases with inlining so that the
clear-at-end-of-function logic is exercised.
What's the difference with inline and normal functions in this case? As I have
understood it inline functions are still treated like normal functions when
walking the ast.
Thanks for working on this, and sorry for the slow responses.
Jordan
It's ok I'm not that fast either.
On Apr 24, 2014, at 7:50 , Anders Rönnholm
anders.ronnh...@evidente.semailto:anders.ronnh...@evidente.se wrote:
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 [jordan_r...@apple.commailto:jordan_r...@apple.com]
Skickat: den 5 april 2014 04:03
Till: Anders Rönnholm
Cc: cfe-commits@cs.uiuc.edumailto:cfe-commits@cs.uiuc.edu; Daniel Marjamäki
Ämne: Re: [PATCH] Division by zero
On Apr 3, 2014, at 7:18 , Anders Rönnholm
anders.ronnh...@evidente.semailto:anders.ronnh...@evidente.semailto:anders.ronnh...@evidente.se
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
Re: [PATCH] Division by zero
I don't understand why the DivZeroMap uses a MemRegion as a key at all. In this
patch you never look things up by MemRegion. I would expect it to be a map from
SymbolRef to block ID.
Clearing the map at the end of a function is a start, but you ought to make
sure you don't clear it for the function that called this one. I suppose that's
a refinement that can be made later, since it only produces false negatives.
(I'm not super happy about not being able to merge branches within the
function, though.)
I'm not sure why you only update the DivZeroMap with the first BlockID that
gets used. If I do a division operation, and then I do another one in another
block, and then I do a check of the variable, shouldn't that still count as a
reversed check?
Smaller comments:
+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) {
+ OptionalCFGStmt stmt = BI-getAsCFGStmt();
+ if (stmt stmt-getStmt() == B)
+return (*I)-getBlockID();
+}
+ }
+ return 0;
+}
This is much too expensive. The CheckerContext has a NodeBuilder, which has a
NodeBuilderContext, which has a CFGBlock. We should just expose that somewhere
(probably on CheckerContext).
+ if (ExplodedNode *N = C.generateSink(C.getState())) {
+if (!BB)
+ BB.reset(new BuiltinBug(this, Division by zero));
Before this checker goes non-alpha, we definitely need a visitor that says
where the most recent division or remainder operation happened.
+ if (IntLiteral IntLiteral-getValue() != 0)
+return;
This check should be if (!IntLiteral || IntLiteral-getValue() != 0).
+reportBug(Comparison is useless,
+ or there is division by zero previously,
Now that the checker is restricted to a guaranteed check-after-division, we can
probably improve the error message to be more precise. Value being compared
against zero has already been used for division or something.
Finally, please include some test cases with inlining so that the
clear-at-end-of-function logic is exercised.
Thanks for working on this, and sorry for the slow responses.
Jordan
On Apr 24, 2014, at 7:50 , Anders Rönnholm anders.ronnh...@evidente.se wrote:
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 [jordan_r...@apple.com]
Skickat: den 5 april 2014 04:03
Till: Anders Rönnholm
Cc: cfe-commits@cs.uiuc.edu; Daniel Marjamäki
Ämne: Re: [PATCH] Division by zero
On Apr 3, 2014, at 7:18 , Anders Rönnholm
anders.ronnh...@evidente.semailto:anders.ronnh...@evidente.se 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
Re: [PATCH] Division by zero
On Apr 3, 2014, at 7:18 , Anders Rönnholm anders.ronnh...@evidente.se 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-getDivZeroMap(MR);
but with set i'm only able to get them all.
DivZeroMapTy DivZeroes = State-getDivZeroMap();
For future reference, set traits get a State-containsDivZeroMap().
Jordan___
cfe-commits mailing list
cfe-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
Re: [PATCH] Division by zero
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?
(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-getDivZeroMap(MR);
but with set i'm only able to get them all.
DivZeroMapTy DivZeroes = State-getDivZeroMap();
/Anders
On Apr 1, 2014, at 7:45 , Anders Rönnholm
anders.ronnh...@evidente.semailto:anders.ronnh...@evidente.se wrote:
Hi,
I have a new patch i'd like to get reviewed for a different kind of division by
zero than the already existing one.
This patch check for division by variable that is later compared against 0.
Either the comparison is useless or there is division by zero.
It catches scenarios like these:
void f(int y) {
x = 100 / y;
if (y == 0) {}
}
//Andersdivzero2.diff___
cfe-commits mailing list
cfe-commits@cs.uiuc.edumailto:cfe-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
___
cfe-commits mailing list
cfe-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
Re: [PATCH] Division by zero
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.
(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. ;-)
On Apr 1, 2014, at 7:45 , Anders Rönnholm anders.ronnh...@evidente.se wrote:
Hi,
I have a new patch i'd like to get reviewed for a different kind of division
by zero than the already existing one.
This patch check for division by variable that is later compared against 0.
Either the comparison is useless or there is division by zero.
It catches scenarios like these:
void f(int y) {
x = 100 / y;
if (y == 0) {}
}
//Andersdivzero2.diff___
cfe-commits mailing list
cfe-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
___
cfe-commits mailing list
cfe-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
