Re: [PATCH] D12726: [analyzer] A fix for symbolic element region index lifetime.
This revision was automatically updated to reflect the committed changes.
Closed by commit rL255236: [analyzer] Fix symbolic element index lifetime.
(authored by dergachev).
Changed prior to commit:
http://reviews.llvm.org/D12726?vs=37267=42400#toc
Repository:
rL LLVM
http://reviews.llvm.org/D12726
Files:
cfe/trunk/docs/analyzer/DebugChecks.rst
cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h
cfe/trunk/lib/StaticAnalyzer/Checkers/ExprInspectionChecker.cpp
cfe/trunk/lib/StaticAnalyzer/Core/Environment.cpp
cfe/trunk/lib/StaticAnalyzer/Core/RegionStore.cpp
cfe/trunk/lib/StaticAnalyzer/Core/SymbolManager.cpp
cfe/trunk/test/Analysis/return-ptr-range.cpp
cfe/trunk/test/Analysis/symbol-reaper.c
Index: cfe/trunk/lib/StaticAnalyzer/Core/Environment.cpp
===
--- cfe/trunk/lib/StaticAnalyzer/Core/Environment.cpp
+++ cfe/trunk/lib/StaticAnalyzer/Core/Environment.cpp
@@ -171,10 +171,6 @@
// Copy the binding to the new map.
EBMapRef = EBMapRef.add(BlkExpr, X);
- // If the block expr's value is a memory region, then mark that region.
- if (Optional R = X.getAs())
-SymReaper.markLive(R->getRegion());
-
// Mark all symbols in the block expr's value live.
RSScaner.scan(X);
continue;
Index: cfe/trunk/lib/StaticAnalyzer/Core/RegionStore.cpp
===
--- cfe/trunk/lib/StaticAnalyzer/Core/RegionStore.cpp
+++ cfe/trunk/lib/StaticAnalyzer/Core/RegionStore.cpp
@@ -2348,8 +2348,12 @@
if (const SymbolicRegion *SymR = dyn_cast(baseR))
SymReaper.markLive(SymR->getSymbol());
- for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I)
+ for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I) {
+// Element index of a binding key is live.
+SymReaper.markElementIndicesLive(I.getKey().getRegion());
+
VisitBinding(I.getData());
+ }
}
void removeDeadBindingsWorker::VisitBinding(SVal V) {
@@ -2370,6 +2374,7 @@
// If V is a region, then add it to the worklist.
if (const MemRegion *R = V.getAsRegion()) {
AddToWorkList(R);
+SymReaper.markLive(R);
// All regions captured by a block are also live.
if (const BlockDataRegion *BR = dyn_cast(R)) {
Index: cfe/trunk/lib/StaticAnalyzer/Core/SymbolManager.cpp
===
--- cfe/trunk/lib/StaticAnalyzer/Core/SymbolManager.cpp
+++ cfe/trunk/lib/StaticAnalyzer/Core/SymbolManager.cpp
@@ -391,6 +391,18 @@
void SymbolReaper::markLive(const MemRegion *region) {
RegionRoots.insert(region);
+ markElementIndicesLive(region);
+}
+
+void SymbolReaper::markElementIndicesLive(const MemRegion *region) {
+ for (auto SR = dyn_cast(region); SR;
+ SR = dyn_cast(SR->getSuperRegion())) {
+if (auto ER = dyn_cast(SR)) {
+ SVal Idx = ER->getIndex();
+ for (auto SI = Idx.symbol_begin(), SE = Idx.symbol_end(); SI != SE; ++SI)
+markLive(*SI);
+}
+ }
}
void SymbolReaper::markInUse(SymbolRef sym) {
Index: cfe/trunk/lib/StaticAnalyzer/Checkers/ExprInspectionChecker.cpp
===
--- cfe/trunk/lib/StaticAnalyzer/Checkers/ExprInspectionChecker.cpp
+++ cfe/trunk/lib/StaticAnalyzer/Checkers/ExprInspectionChecker.cpp
@@ -17,22 +17,26 @@
using namespace ento;
namespace {
-class ExprInspectionChecker : public Checker< eval::Call > {
+class ExprInspectionChecker : public Checker {
mutable std::unique_ptr BT;
void analyzerEval(const CallExpr *CE, CheckerContext ) const;
void analyzerCheckInlined(const CallExpr *CE, CheckerContext ) const;
void analyzerWarnIfReached(const CallExpr *CE, CheckerContext ) const;
void analyzerCrash(const CallExpr *CE, CheckerContext ) const;
+ void analyzerWarnOnDeadSymbol(const CallExpr *CE, CheckerContext ) const;
typedef void (ExprInspectionChecker::*FnCheck)(const CallExpr *,
CheckerContext ) const;
public:
bool evalCall(const CallExpr *CE, CheckerContext ) const;
+ void checkDeadSymbols(SymbolReaper , CheckerContext ) const;
};
}
+REGISTER_SET_WITH_PROGRAMSTATE(MarkedSymbols, const void *)
+
bool ExprInspectionChecker::evalCall(const CallExpr *CE,
CheckerContext ) const {
// These checks should have no effect on the surrounding environment
@@ -42,7 +46,10 @@
.Case("clang_analyzer_checkInlined",
::analyzerCheckInlined)
.Case("clang_analyzer_crash", ::analyzerCrash)
-.Case("clang_analyzer_warnIfReached", ::analyzerWarnIfReached)
+.Case("clang_analyzer_warnIfReached",
+ ::analyzerWarnIfReached)
+.Case("clang_analyzer_warnOnDeadSymbol",
+ ::analyzerWarnOnDeadSymbol)
.Default(nullptr);
if (!Handler)
@@ -137,6 +144,41 @@
Re: [PATCH] D12726: [analyzer] A fix for symbolic element region index lifetime.
NoQ added a comment. In http://reviews.llvm.org/D12726#303122, @zaks.anna wrote: > > So the real question is whether (or rather how) the Store should maintain > > correct region liveness information > > > after completing its internal garbage collection pass, because there are, > > in fact, other users of > > > this information later in the chain, but this seems to be a larger problem > > without instantly noticeable effects. > > > Could you give specific (possibly potential) examples of this problem? > > We assume that the symbols that are collected do not need to stick around, so > no-one "later in the chain" should need them. Except for the cases where we > artificially extend liveness by calling addSymbolDependency(). What I was trying to say is that after `StoreManager` iterates over the `Store`, there are also checkers that may want to make decisions on liveness of their symbols based on liveness of certain regions, by checking `SymbolReaper::isLiveRegion()`, but currently such behavior is very rare, and thus barely tested. But eventually, with more checkers and further development, we'd need to figure out how this should work (eg. http://reviews.llvm.org/D14277 is a step in this direction - this patch can only work as long as `isLiveRegion()` is reliable after GC'ing the `Store`). Theoretically, it still makes sense to me to say that, for example, the `Store` shouldn't hold its keys as live - for the reasons stated above. So this is mostly a hand-waving thing, and i think the patch is not immediately affected by this potential debate, and it should be OK to commit it. http://reviews.llvm.org/D12726 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
Re: [PATCH] D12726: [analyzer] A fix for symbolic element region index lifetime.
zaks.anna accepted this revision. zaks.anna added a comment. This revision is now accepted and ready to land. LGTM. (Feel free to add comments to the existing code!) > So the real question is whether (or rather how) the Store should maintain > correct region liveness information > after completing its internal garbage collection pass, because there are, in > fact, other users of > this information later in the chain, but this seems to be a larger problem > without instantly noticeable effects. Could you give specific (possibly potential) examples of this problem? We assume that the symbols that are collected do not need to stick around, so no-one "later in the chain" should need them. Except for the cases where we artificially extend liveness by calling addSymbolDependency(). http://reviews.llvm.org/D12726 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
Re: [PATCH] D12726: [analyzer] A fix for symbolic element region index lifetime.
NoQ updated this revision to Diff 37267.
NoQ added a comment.
A, another mis-submit. Sorry for the noise.
http://reviews.llvm.org/D12726
Files:
docs/analyzer/DebugChecks.rst
include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h
lib/StaticAnalyzer/Checkers/ExprInspectionChecker.cpp
lib/StaticAnalyzer/Core/Environment.cpp
lib/StaticAnalyzer/Core/RegionStore.cpp
lib/StaticAnalyzer/Core/SymbolManager.cpp
test/Analysis/return-ptr-range.cpp
test/Analysis/symbol-reaper.c
Index: test/Analysis/symbol-reaper.c
===
--- test/Analysis/symbol-reaper.c
+++ test/Analysis/symbol-reaper.c
@@ -0,0 +1,76 @@
+// RUN: %clang_cc1 -analyze -analyzer-checker=debug.ExprInspection -verify %s
+
+void clang_analyzer_eval(int);
+void clang_analyzer_warnOnDeadSymbol(int);
+
+int conjure_index();
+
+void test_that_expr_inspection_works() {
+ do {
+int x = conjure_index();
+clang_analyzer_warnOnDeadSymbol(x);
+ } while(0); // expected-warning{{SYMBOL DEAD}}
+}
+
+// These tests verify the reaping of symbols that are only referenced as
+// index values in element regions. Most of the time, depending on where
+// the element region, as Loc value, is stored, it is possible to
+// recover the index symbol in checker code, which is also demonstrated
+// in the return_ptr_range.c test file.
+
+int arr[3];
+
+int *test_element_index_lifetime_in_environment_values() {
+ int *ptr;
+ do {
+int x = conjure_index();
+clang_analyzer_warnOnDeadSymbol(x);
+ptr = arr + x;
+ } while (0);
+ return ptr;
+}
+
+void test_element_index_lifetime_in_store_keys() {
+ do {
+int x = conjure_index();
+clang_analyzer_warnOnDeadSymbol(x);
+arr[x] = 1;
+if (x) {}
+ } while (0); // no-warning
+}
+
+int *ptr;
+void test_element_index_lifetime_in_store_values() {
+ do {
+int x = conjure_index();
+clang_analyzer_warnOnDeadSymbol(x);
+ptr = arr + x;
+ } while (0); // no-warning
+}
+
+struct S1 {
+ int field;
+};
+struct S2 {
+ struct S1 array[5];
+} s2;
+
+void test_element_index_lifetime_with_complicated_hierarchy_of_regions() {
+ do {
+int x = conjure_index();
+clang_analyzer_warnOnDeadSymbol(x);
+s2.array[x].field = 1;
+if (x) {}
+ } while (0); // no-warning
+}
+
+// Test below checks lifetime of SymbolRegionValue in certain conditions.
+
+int **ptrptr;
+void test_region_lifetime_as_store_value(int *x) {
+ clang_analyzer_warnOnDeadSymbol((int) x);
+ *x = 1;
+ ptrptr =
+ (void)0; // No-op; make sure the environment forgets things and the GC runs.
+ clang_analyzer_eval(**ptrptr); // expected-warning{{TRUE}}
+} // no-warning
Index: test/Analysis/return-ptr-range.cpp
===
--- test/Analysis/return-ptr-range.cpp
+++ test/Analysis/return-ptr-range.cpp
@@ -0,0 +1,27 @@
+// RUN: %clang_cc1 -analyze -analyzer-checker=alpha.security.ReturnPtrRange -verify %s
+
+int arr[10];
+int *ptr;
+
+int conjure_index();
+
+int *test_element_index_lifetime() {
+ do {
+int x = conjure_index();
+ptr = arr + x;
+if (x != 20)
+ return arr; // no-warning
+ } while (0);
+ return ptr; // expected-warning{{Returned pointer value points outside the original object (potential buffer overflow)}}
+}
+
+int *test_element_index_lifetime_with_local_ptr() {
+ int *local_ptr;
+ do {
+int x = conjure_index();
+local_ptr = arr + x;
+if (x != 20)
+ return arr; // no-warning
+ } while (0);
+ return local_ptr; // expected-warning{{Returned pointer value points outside the original object (potential buffer overflow)}}
+}
Index: lib/StaticAnalyzer/Core/SymbolManager.cpp
===
--- lib/StaticAnalyzer/Core/SymbolManager.cpp
+++ lib/StaticAnalyzer/Core/SymbolManager.cpp
@@ -391,6 +391,18 @@
void SymbolReaper::markLive(const MemRegion *region) {
RegionRoots.insert(region);
+ markElementIndicesLive(region);
+}
+
+void SymbolReaper::markElementIndicesLive(const MemRegion *region) {
+ for (auto SR = dyn_cast(region); SR;
+ SR = dyn_cast(SR->getSuperRegion())) {
+if (auto ER = dyn_cast(SR)) {
+ SVal Idx = ER->getIndex();
+ for (auto SI = Idx.symbol_begin(), SE = Idx.symbol_end(); SI != SE; ++SI)
+markLive(*SI);
+}
+ }
}
void SymbolReaper::markInUse(SymbolRef sym) {
Index: lib/StaticAnalyzer/Core/RegionStore.cpp
===
--- lib/StaticAnalyzer/Core/RegionStore.cpp
+++ lib/StaticAnalyzer/Core/RegionStore.cpp
@@ -2344,8 +2344,12 @@
if (const SymbolicRegion *SymR = dyn_cast(baseR))
SymReaper.markLive(SymR->getSymbol());
- for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I)
+ for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I) {
+// Element index of a binding key is live.
+
Re: [PATCH] D12726: [analyzer] A fix for symbolic element region index lifetime.
NoQ updated this revision to Diff 37263.
NoQ added a comment.
Hmm, i think i'm ready to explain most of the stuff.
- First of all, the piece of code in `EnvironmentManager::removeDeadBindings()`
i mentioned above is truly useless; everything would be marked as live anyway
on the next line.
- Then, in `RegionStore`, in `VisitBinding()`, `markLive()` of the whole region
value inside the binding is indeed correct, and i provide a pretty
straightforward test;
- Finally, in `VisitCluster()`, it's a bit more complicated, and i suggest that
`markLive()` is unnecessary here, and in fact does very little if anything, so
it's hard to test even with stuff we have now:
- i guess we shouldn't think of a region as live, simply because it has
bindings, in a procedure designed for removing bindings;
- however, marking the region as live here wouldn't save the bindings; they
would later be removed simply because they weren't visited;
- liveness of the region would also extend lifetime of a few symbols that
depend on it, such as its `SymbolRegionValue`, `SymbolExtent`, and
`SymbolMetadata`, however because the binding would be dead anyway, these
symbols would die on the next pass;
- note that `SymbolRegionValue` should explicitly be dead when the region
has other bindings, so we certainly shouldn't try to preserve the region only
to save `SymbolRegionValue`;
- see also http://reviews.llvm.org/D5104 ; i also think i accidentally
wrote the missing test for this ticket, will put it there;
- another place that relies on region liveness information collected on these
passes is Dynamic Type Propagation, however the same arguments apply; it would
only delay the inevitable.
So the real question is whether (or rather how) the `Store` should maintain
correct region liveness information after completing its internal garbage
collection pass, because there are, in fact, other users of this information
later in the chain, but this seems to be a larger problem without instantly
noticeable effects.
The new diff removes dead code in `Environment` and tests and fixes the
separate bug in the `Store` that caused reaping of constraints on
`SymbolRegionValue` (and a few other kinds of `SymbolData`) too early when the
only place where the related region is stored is a store value.
http://reviews.llvm.org/D12726
Files:
docs/analyzer/DebugChecks.rst
include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h
lib/StaticAnalyzer/Checkers/ExprInspectionChecker.cpp
lib/StaticAnalyzer/Core/Environment.cpp
lib/StaticAnalyzer/Core/RegionStore.cpp
lib/StaticAnalyzer/Core/SymbolManager.cpp
test/Analysis/return-ptr-range.cpp
test/Analysis/symbol-reaper.c
Index: test/Analysis/symbol-reaper.c
===
--- test/Analysis/symbol-reaper.c
+++ test/Analysis/symbol-reaper.c
@@ -0,0 +1,77 @@
+// RUN: %clang_cc1 -analyze -analyzer-checker=debug.ExprInspection -verify %s
+
+void clang_analyzer_eval(int);
+void clang_analyzer_warnOnDeadSymbol(int);
+void clang_analyzer_warnIfReached();
+
+int conjure_index();
+
+void test_that_expr_inspection_works() {
+ do {
+int x = conjure_index();
+clang_analyzer_warnOnDeadSymbol(x);
+ } while(0); // expected-warning{{SYMBOL DEAD}}
+}
+
+// These tests verify the reaping of symbols that are only referenced as
+// index values in element regions. Most of the time, depending on where
+// the element region, as Loc value, is stored, it is possible to
+// recover the index symbol in checker code, which is also demonstrated
+// in the return_ptr_range.c test file.
+
+int arr[3];
+
+int *test_element_index_lifetime_in_environment_values() {
+ int *ptr;
+ do {
+int x = conjure_index();
+clang_analyzer_warnOnDeadSymbol(x);
+ptr = arr + x;
+ } while (0);
+ return ptr;
+}
+
+void test_element_index_lifetime_in_store_keys() {
+ do {
+int x = conjure_index();
+clang_analyzer_warnOnDeadSymbol(x);
+arr[x] = 1;
+if (x) {}
+ } while (0); // no-warning
+}
+
+int *ptr;
+void test_element_index_lifetime_in_store_values() {
+ do {
+int x = conjure_index();
+clang_analyzer_warnOnDeadSymbol(x);
+ptr = arr + x;
+ } while (0); // no-warning
+}
+
+struct S1 {
+ int field;
+};
+struct S2 {
+ struct S1 array[5];
+} s2;
+
+void test_element_index_lifetime_with_complicated_hierarchy_of_regions() {
+ do {
+int x = conjure_index();
+clang_analyzer_warnOnDeadSymbol(x);
+s2.array[x].field = 1;
+if (x) {}
+ } while (0); // no-warning
+}
+
+// Test below checks lifetime of SymbolRegionValue in certain conditions.
+
+int **ptrptr;
+void test_region_lifetime_as_store_value(int *x) {
+ clang_analyzer_warnOnDeadSymbol((int) x);
+ *x = 1;
+ ptrptr =
+ (void)0; // No-op; make sure the environment forgets things and the GC runs.
+ clang_analyzer_eval(**ptrptr); // expected-warning{{TRUE}}
+} // no-warning
Index: test/Analysis/return-ptr-range.cpp
Re: [PATCH] D12726: [analyzer] A fix for symbolic element region index lifetime.
NoQ updated this revision to Diff 37266.
NoQ added a comment.
Whoops accidentally left out a dead code line in tests.
http://reviews.llvm.org/D12726
Files:
docs/analyzer/DebugChecks.rst
include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h
lib/StaticAnalyzer/Checkers/ExprInspectionChecker.cpp
lib/StaticAnalyzer/Core/Environment.cpp
lib/StaticAnalyzer/Core/RegionStore.cpp
lib/StaticAnalyzer/Core/SymbolManager.cpp
test/Analysis/return-ptr-range.cpp
test/Analysis/symbol-reaper.c
Index: test/Analysis/symbol-reaper.c
===
--- test/Analysis/symbol-reaper.c
+++ test/Analysis/symbol-reaper.c
@@ -0,0 +1,78 @@
+// RUN: %clang_cc1 -analyze -analyzer-checker=debug.ExprInspection -verify %s
+
+void clang_analyzer_eval(int);
+void clang_analyzer_warnOnDeadSymbol(int);
+
+int conjure_index();
+
+void test_that_expr_inspection_works() {
+ do {
+int x = conjure_index();
+clang_analyzer_warnOnDeadSymbol(x);
+ } while(0); // expected-warning{{SYMBOL DEAD}}
+}
+
+// These tests verify the reaping of symbols that are only referenced as
+// index values in element regions. Most of the time, depending on where
+// the element region, as Loc value, is stored, it is possible to
+// recover the index symbol in checker code, which is also demonstrated
+// in the return_ptr_range.c test file.
+
+int arr[3];
+
+int *test_element_index_lifetime_in_environment_values() {
+ int *ptr;
+ do {
+int x = conjure_index();
+clang_analyzer_warnOnDeadSymbol(x);
+ptr = arr + x;
+ } while (0);
+ return ptr;
+}
+
+void test_element_index_lifetime_in_store_keys() {
+ do {
+int x = conjure_index();
+clang_analyzer_warnOnDeadSymbol(x);
+arr[x] = 1;
+if (x) {}
+ } while (0); // no-warning
+}
+
+int *ptr;
+void test_element_index_lifetime_in_store_values() {
+ do {
+int x = conjure_index();
+clang_analyzer_warnOnDeadSymbol(x);
+ptr = arr + x;
+ } while (0); // no-warning
+}
+
+struct S1 {
+ int field, other_field;
+};
+struct S2 {
+ struct S1 array[5];
+} s2;
+
+void test_element_index_lifetime_with_complicated_hierarchy_of_regions() {
+ do {
+int x = conjure_index();
+clang_analyzer_warnOnDeadSymbol(x);
+s2.array[x].field = 1;
+if (x) {}
+ } while (0); // no-warning
+}
+
+// Test below checks lifetime of SymbolRegionValue in certain conditions.
+// SymbolRegionValue should live as long as its region is live but has no
+// direct bindings that override its value.
+
+int **ptrptr;
+void test_region_lifetime_as_store_value(int *x) {
+ clang_analyzer_warnOnDeadSymbol((int) x);
+ *x = 1;
+ ptrptr =
+ (void)0; // No-op; make sure the environment forgets things and the GC runs.
+ clang_analyzer_eval(**ptrptr); // expected-warning{{TRUE}}
+} // no-warning
Index: test/Analysis/return-ptr-range.cpp
===
--- test/Analysis/return-ptr-range.cpp
+++ test/Analysis/return-ptr-range.cpp
@@ -0,0 +1,27 @@
+// RUN: %clang_cc1 -analyze -analyzer-checker=alpha.security.ReturnPtrRange -verify %s
+
+int arr[10];
+int *ptr;
+
+int conjure_index();
+
+int *test_element_index_lifetime() {
+ do {
+int x = conjure_index();
+ptr = arr + x;
+if (x != 20)
+ return arr; // no-warning
+ } while (0);
+ return ptr; // expected-warning{{Returned pointer value points outside the original object (potential buffer overflow)}}
+}
+
+int *test_element_index_lifetime_with_local_ptr() {
+ int *local_ptr;
+ do {
+int x = conjure_index();
+local_ptr = arr + x;
+if (x != 20)
+ return arr; // no-warning
+ } while (0);
+ return local_ptr; // expected-warning{{Returned pointer value points outside the original object (potential buffer overflow)}}
+}
Index: lib/StaticAnalyzer/Core/SymbolManager.cpp
===
--- lib/StaticAnalyzer/Core/SymbolManager.cpp
+++ lib/StaticAnalyzer/Core/SymbolManager.cpp
@@ -391,6 +391,18 @@
void SymbolReaper::markLive(const MemRegion *region) {
RegionRoots.insert(region);
+ markElementIndicesLive(region);
+}
+
+void SymbolReaper::markElementIndicesLive(const MemRegion *region) {
+ for (auto SR = dyn_cast(region); SR;
+ SR = dyn_cast(SR->getSuperRegion())) {
+if (auto ER = dyn_cast(SR)) {
+ SVal Idx = ER->getIndex();
+ for (auto SI = Idx.symbol_begin(), SE = Idx.symbol_end(); SI != SE; ++SI)
+markLive(*SI);
+}
+ }
}
void SymbolReaper::markInUse(SymbolRef sym) {
Index: lib/StaticAnalyzer/Core/RegionStore.cpp
===
--- lib/StaticAnalyzer/Core/RegionStore.cpp
+++ lib/StaticAnalyzer/Core/RegionStore.cpp
@@ -2344,8 +2344,12 @@
if (const SymbolicRegion *SymR = dyn_cast(baseR))
SymReaper.markLive(SymR->getSymbol());
- for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I)
+ for (ClusterBindings::iterator I =
Re: [PATCH] D12726: [analyzer] A fix for symbolic element region index lifetime.
NoQ updated this revision to Diff 36946.
NoQ marked 4 inline comments as done.
NoQ added a comment.
Thanks for the review! Fixed all comments. I don't notice any significant
performance hit with this patch (+/- 2% on the whole Android codebase runs).
I guess i won't break this into separate reviews, because less work =)
The loop through super-regions is necessary for supporting the test proposed by
Jordan Rose, which is now added. Not sure what other tests are worth adding;
together with specific tests on ReturnPtrRange, we're covering all three places
that were patched; maybe i could move these tests to symbol-reaper.c as well,
but i guess it's more worth it to test the actual analyzer output than
artificially dumped internals(?) Not sure.
The change in Environment.cpp was removed because it's now handled
automatically by markLive().
http://reviews.llvm.org/D12726
Files:
docs/analyzer/DebugChecks.rst
include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h
lib/StaticAnalyzer/Checkers/ExprInspectionChecker.cpp
lib/StaticAnalyzer/Core/RegionStore.cpp
lib/StaticAnalyzer/Core/SymbolManager.cpp
test/Analysis/return-ptr-range.cpp
test/Analysis/symbol-reaper.c
Index: test/Analysis/symbol-reaper.c
===
--- test/Analysis/symbol-reaper.c
+++ test/Analysis/symbol-reaper.c
@@ -0,0 +1,37 @@
+// RUN: %clang_cc1 -analyze -analyzer-checker=debug.ExprInspection -verify %s
+
+void clang_analyzer_warnOnDeadSymbol(int);
+
+int conjure_index();
+
+void test_that_expr_inspection_works() {
+ do {
+int x = conjure_index();
+clang_analyzer_warnOnDeadSymbol(x);
+ } while(0); // expected-warning{{SYMBOL DEAD}}
+}
+
+int arr[3];
+void test_element_index_lifetime() {
+ do {
+int x = conjure_index();
+clang_analyzer_warnOnDeadSymbol(x);
+arr[x] = 1;
+if (x) {}
+ } while (0); // no-warning
+}
+
+struct S1 {
+ int field;
+};
+struct S2 {
+ struct S1 array[5];
+} s2;
+void test_element_index_lifetime_with_complicated_hierarchy_of_regions() {
+ do {
+int x = conjure_index();
+clang_analyzer_warnOnDeadSymbol(x);
+s2.array[x].field = 1;
+if (x) {}
+ } while (0); // no-warning
+}
Index: test/Analysis/return-ptr-range.cpp
===
--- test/Analysis/return-ptr-range.cpp
+++ test/Analysis/return-ptr-range.cpp
@@ -0,0 +1,27 @@
+// RUN: %clang_cc1 -analyze -analyzer-checker=alpha.security.ReturnPtrRange -verify %s
+
+int arr[10];
+int *ptr;
+
+int conjure_index();
+
+int *test_element_index_lifetime() {
+ do {
+int x = conjure_index();
+ptr = arr + x;
+if (x != 20)
+ return arr; // no-warning
+ } while (0);
+ return ptr; // expected-warning{{Returned pointer value points outside the original object (potential buffer overflow)}}
+}
+
+int *test_element_index_lifetime_with_local_ptr() {
+ int *local_ptr;
+ do {
+int x = conjure_index();
+local_ptr = arr + x;
+if (x != 20)
+ return arr; // no-warning
+ } while (0);
+ return local_ptr; // expected-warning{{Returned pointer value points outside the original object (potential buffer overflow)}}
+}
Index: lib/StaticAnalyzer/Core/SymbolManager.cpp
===
--- lib/StaticAnalyzer/Core/SymbolManager.cpp
+++ lib/StaticAnalyzer/Core/SymbolManager.cpp
@@ -391,6 +391,18 @@
void SymbolReaper::markLive(const MemRegion *region) {
RegionRoots.insert(region);
+ // Mark the element index in all superregions as live.
+ markElementIndicesLive(region);
+}
+
+void SymbolReaper::markElementIndicesLive(const MemRegion *region) {
+ for (auto SR = dyn_cast(region); SR;
+ SR = dyn_cast(SR->getSuperRegion()))
+if (auto ER = dyn_cast(SR)) {
+ SVal Idx = ER->getIndex();
+ for (auto SI = Idx.symbol_begin(), SE = Idx.symbol_end(); SI != SE; ++SI)
+markLive(*SI);
+}
}
void SymbolReaper::markInUse(SymbolRef sym) {
Index: lib/StaticAnalyzer/Core/RegionStore.cpp
===
--- lib/StaticAnalyzer/Core/RegionStore.cpp
+++ lib/StaticAnalyzer/Core/RegionStore.cpp
@@ -2344,8 +2344,12 @@
if (const SymbolicRegion *SymR = dyn_cast(baseR))
SymReaper.markLive(SymR->getSymbol());
- for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I)
+ for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I) {
+// Element index of a binding key is live.
+SymReaper.markElementIndicesLive(I.getKey().getRegion());
+
VisitBinding(I.getData());
+ }
}
void removeDeadBindingsWorker::VisitBinding(SVal V) {
@@ -2366,6 +2370,8 @@
// If V is a region, then add it to the worklist.
if (const MemRegion *R = V.getAsRegion()) {
AddToWorkList(R);
+// Element index of a binding value is live.
+SymReaper.markElementIndicesLive(R);
// All regions captured by a block are also live.
Re: [PATCH] D12726: [analyzer] A fix for symbolic element region index lifetime.
zaks.anna added a comment.
Now that we have a way to test symbol reaper, please, add more coverage to the
symbol-reaper.c test, including the test that Jordan mentioned. Even if it is
not fixed, it's good to include it with a FIXME note.
What is the performance impact of this change?
The changes to the RegionStore and Environment seem inconsistent and
repetitive.. For example, we can remove a lot of this just by changing
SymbolReaper::markLive(const MemRegion *region), see below. How is this patch
different from your solution? Can it be generalized to handle more cases?
diff --git a/lib/StaticAnalyzer/Core/RegionStore.cpp
b/lib/StaticAnalyzer/Core/RegionStore.cpp
index 49b5ac3..55db545 100644
--- a/lib/StaticAnalyzer/Core/RegionStore.cpp
+++ b/lib/StaticAnalyzer/Core/RegionStore.cpp
@@ -2320,8 +2320,14 @@ void removeDeadBindingsWorker::VisitCluster(const
MemRegion *baseR,
if (const SymbolicRegion *SymR = dyn_cast(baseR))
SymReaper.markLive(SymR->getSymbol());
- for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I)
+ for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I) {
+// Mark the key of each binding as live.
+const BindingKey = I.getKey();
+if (auto subR = dyn_cast(K.getRegion()))
+ SymReaper.markLive(subR);
+
VisitBinding(I.getData());
+ }
}
void removeDeadBindingsWorker::VisitBinding(SVal V) {
@@ -2342,6 +2348,7 @@ void removeDeadBindingsWorker::VisitBinding(SVal V) {
// If V is a region, then add it to the worklist.
if (const MemRegion *R = V.getAsRegion()) {
AddToWorkList(R);
+SymReaper.markLive(R);
// All regions captured by a block are also live.
if (const BlockDataRegion *BR = dyn_cast(R)) {
diff --git a/lib/StaticAnalyzer/Core/SymbolManager.cpp
b/lib/StaticAnalyzer/Core/SymbolManager.cpp
index df4d22a..793f53e 100644
--- a/lib/StaticAnalyzer/Core/SymbolManager.cpp
+++ b/lib/StaticAnalyzer/Core/SymbolManager.cpp
@@ -391,6 +391,16 @@ void SymbolReaper::markLive(SymbolRef sym) {
void SymbolReaper::markLive(const MemRegion *region) {
RegionRoots.insert(region);
+
+ // Mark the element index as live.
+ if (const ElementRegion *ER = dyn_cast(region)) {
+SVal Idx = ER->getIndex();
+for (SymExpr::symbol_iterator SI = Idx.symbol_begin(),
+ SE = Idx.symbol_end();
+ SI != SE; ++SI) {
+ markLive(*SI);
+}
+ }
}
Comment at: lib/StaticAnalyzer/Checkers/ExprInspectionChecker.cpp:177
@@ +176,3 @@
+
+C.emitReport(llvm::make_unique(*BT, "SYMBOL DEAD", N));
+ }
Thank you for adding this!!! This can be part of this commit or separate; up to
you.
Please, update the debugger checkers document in the docs folder with
information on how this should be used.
Comment at: lib/StaticAnalyzer/Core/RegionStore.cpp:2241
@@ +2240,3 @@
+ for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I) {
+
+// Mark the index symbol of any ElementRegion key as live.
Please, remove unnecessary spacing here and in a couple of other places.
Comment at: lib/StaticAnalyzer/Core/RegionStore.cpp:2247
@@ +2246,3 @@
+ if (auto elemR = dyn_cast(subR))
+if (SymbolRef Sym = elemR->getIndex().getAsSymbol())
+ SymReaper.markLive(Sym);
Why symbol_iterator is not used here?
Comment at: lib/StaticAnalyzer/Core/RegionStore.cpp:2249
@@ +2248,3 @@
+ SymReaper.markLive(Sym);
+ subR = dyn_cast(subR->getSuperRegion());
+}
Could you add test cases that explain why we need the while loop here?
http://reviews.llvm.org/D12726
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
Re: [PATCH] D12726: [analyzer] A fix for symbolic element region index lifetime.
NoQ updated this revision to Diff 35067.
NoQ added a comment.
Thanks for the quick reply, sorry for the delay! Was afk for a couple of days.
Yeah, right, in fact i didn't even fix the issue for store keys at all; only
for store values and environment values.
It also seems much harder to test store keys, because it's quite a problem to
guess the symbolic key once the symbol is not present anywhere else, though i
can imagine an artificial checker that would rely on that. A test like...
int a[1];
{
int x = conjure_index();
a[x] = 0;
if (x != 0)
return;
clang_analyzer_eval(a[0] == 0); // expected-warning{{TRUE}}
}
clang_analyzer_eval(a[0] == 0); // expected-warning{{TRUE}}
...should have exposed such problem, but this kind of lookup doesn't seem to be
supported by the store yet (that is, the first `expected-warning{{TRUE}}` fails
as well).
Hmm, what if i expand the `debug.ExprInspection` checker to allow testing
`SymbolReaper` directly? Updated the diff with a proof of concept, which fixes
the issue for the store keys and adds a test. I can split the `ExprInspection`
change into a separate commit/review if necessary. It might be useful for
testing other `SymbolReaper`-related patches as well.
http://reviews.llvm.org/D12726
Files:
lib/StaticAnalyzer/Checkers/ExprInspectionChecker.cpp
lib/StaticAnalyzer/Core/Environment.cpp
lib/StaticAnalyzer/Core/RegionStore.cpp
test/Analysis/return-ptr-range.cpp
test/Analysis/symbol-reaper.c
Index: test/Analysis/symbol-reaper.c
===
--- test/Analysis/symbol-reaper.c
+++ test/Analysis/symbol-reaper.c
@@ -0,0 +1,23 @@
+// RUN: %clang_cc1 -analyze -analyzer-checker=debug.ExprInspection -verify %s
+
+void clang_analyzer_warnOnDeadSymbol(int);
+
+int arr[3];
+
+int conjure_index();
+
+void test_that_expr_inspection_works() {
+ do {
+int x = conjure_index();
+clang_analyzer_warnOnDeadSymbol(x);
+ } while(0); // expected-warning{{SYMBOL DEAD}}
+}
+
+void test_element_index_lifetime() {
+ do {
+int x = conjure_index();
+clang_analyzer_warnOnDeadSymbol(x);
+arr[x] = 1;
+if (x) {}
+ } while(0); // no-warning
+}
Index: test/Analysis/return-ptr-range.cpp
===
--- test/Analysis/return-ptr-range.cpp
+++ test/Analysis/return-ptr-range.cpp
@@ -0,0 +1,27 @@
+// RUN: %clang_cc1 -analyze -analyzer-checker=alpha.security.ReturnPtrRange -verify %s
+
+int arr[10];
+int *ptr;
+
+int conjure_index();
+
+int *test_element_index_lifetime() {
+ do {
+int x = conjure_index();
+ptr = arr + x;
+if (x != 20)
+ return arr; // no-warning
+ } while (0);
+ return ptr; // expected-warning{{Returned pointer value points outside the original object (potential buffer overflow)}}
+}
+
+int *test_element_index_lifetime_with_local_ptr() {
+ int *local_ptr;
+ do {
+int x = conjure_index();
+local_ptr = arr + x;
+if (x != 20)
+ return arr; // no-warning
+ } while (0);
+ return local_ptr; // expected-warning{{Returned pointer value points outside the original object (potential buffer overflow)}}
+}
Index: lib/StaticAnalyzer/Core/RegionStore.cpp
===
--- lib/StaticAnalyzer/Core/RegionStore.cpp
+++ lib/StaticAnalyzer/Core/RegionStore.cpp
@@ -2237,8 +2237,20 @@
if (const SymbolicRegion *SymR = dyn_cast(baseR))
SymReaper.markLive(SymR->getSymbol());
- for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I)
+ for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I) {
+
+// Mark the index symbol of any ElementRegion key as live.
+const BindingKey = I.getKey();
+auto subR = dyn_cast(K.getRegion());
+while (subR) {
+ if (auto elemR = dyn_cast(subR))
+if (SymbolRef Sym = elemR->getIndex().getAsSymbol())
+ SymReaper.markLive(Sym);
+ subR = dyn_cast(subR->getSuperRegion());
+}
+
VisitBinding(I.getData());
+ }
}
void removeDeadBindingsWorker::VisitBinding(SVal V) {
@@ -2260,6 +2272,16 @@
if (const MemRegion *R = V.getAsRegion()) {
AddToWorkList(R);
+// Element index of an element region is live.
+if (const ElementRegion *ER = dyn_cast(R)) {
+ SVal Idx = ER->getIndex();
+ for (SymExpr::symbol_iterator SI = Idx.symbol_begin(),
+SE = Idx.symbol_end();
+ SI != SE; ++SI) {
+SymReaper.markLive(*SI);
+ }
+}
+
// All regions captured by a block are also live.
if (const BlockDataRegion *BR = dyn_cast(R)) {
BlockDataRegion::referenced_vars_iterator I = BR->referenced_vars_begin(),
Index: lib/StaticAnalyzer/Core/Environment.cpp
===
--- lib/StaticAnalyzer/Core/Environment.cpp
+++ lib/StaticAnalyzer/Core/Environment.cpp
@@ -171,8 +171,15 @@
EBMapRef =
Re: [PATCH] D12726: [analyzer] A fix for symbolic element region index lifetime.
jordan_rose added a comment. Hm, interesting. I'm not sure this is even sufficient, though: what if I have a FieldRegion that's a sub-region of an ElementRegion with a symbolic index? RegionStore does everything by base regions, so we won't ever see that intermediate region with the symbolic index. http://reviews.llvm.org/D12726 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D12726: [analyzer] A fix for symbolic element region index lifetime.
NoQ created this revision.
NoQ added reviewers: zaks.anna, krememek.
NoQ added subscribers: cfe-commits, dergachev.a.
In Clang Static Analyzer, when the symbol is referenced by an index value of an
element region, it does not prevent garbage collection (reaping) of that
symbol. Hence, if the element index value is the only place where the symbol is
stored, the symbol gets reaped, and range information is removed from the
constraint manager.
It seems that both the store and the environment need to mark the element
indices of their regions as live.
http://reviews.llvm.org/D12726
Files:
lib/StaticAnalyzer/Core/Environment.cpp
lib/StaticAnalyzer/Core/RegionStore.cpp
test/Analysis/return-ptr-range.cpp
Index: test/Analysis/return-ptr-range.cpp
===
--- test/Analysis/return-ptr-range.cpp
+++ test/Analysis/return-ptr-range.cpp
@@ -0,0 +1,27 @@
+// RUN: %clang_cc1 -analyze -analyzer-checker=alpha.security.ReturnPtrRange
-verify %s
+
+int arr[10];
+int *ptr;
+
+int conjure_index();
+
+int *test_element_index_lifetime() {
+ do {
+int x = conjure_index();
+ptr = arr + x;
+if (x != 20)
+ return arr; // no-warning
+ } while (0);
+ return ptr; // expected-warning{{Returned pointer value points outside the
original object (potential buffer overflow)}}
+}
+
+int *test_element_index_lifetime_with_local_ptr() {
+ int *local_ptr;
+ do {
+int x = conjure_index();
+local_ptr = arr + x;
+if (x != 20)
+ return arr; // no-warning
+ } while (0);
+ return local_ptr; // expected-warning{{Returned pointer value points outside
the original object (potential buffer overflow)}}
+}
Index: lib/StaticAnalyzer/Core/RegionStore.cpp
===
--- lib/StaticAnalyzer/Core/RegionStore.cpp
+++ lib/StaticAnalyzer/Core/RegionStore.cpp
@@ -2260,6 +2260,16 @@
if (const MemRegion *R = V.getAsRegion()) {
AddToWorkList(R);
+// Element index of an element region is live.
+if (const ElementRegion *ER = dyn_cast(R)) {
+ SVal Idx = ER->getIndex();
+ for (SymExpr::symbol_iterator SI = Idx.symbol_begin(),
+SE = Idx.symbol_end();
+ SI != SE; ++SI) {
+SymReaper.markLive(*SI);
+ }
+}
+
// All regions captured by a block are also live.
if (const BlockDataRegion *BR = dyn_cast(R)) {
BlockDataRegion::referenced_vars_iterator I =
BR->referenced_vars_begin(),
Index: lib/StaticAnalyzer/Core/Environment.cpp
===
--- lib/StaticAnalyzer/Core/Environment.cpp
+++ lib/StaticAnalyzer/Core/Environment.cpp
@@ -171,8 +171,15 @@
EBMapRef = EBMapRef.add(BlkExpr, X);
// If the block expr's value is a memory region, then mark that region.
- if (Optional R = X.getAs())
-SymReaper.markLive(R->getRegion());
+ if (Optional R = X.getAs()) {
+const MemRegion *MR = R->getRegion();
+SymReaper.markLive(MR);
+
+// Mark the element index as live.
+if (const ElementRegion *ER = dyn_cast(MR))
+ if (SymbolRef Sym = ER->getIndex().getAsSymbol())
+SymReaper.markLive(Sym);
+ }
// Mark all symbols in the block expr's value live.
RSScaner.scan(X);
Index: test/Analysis/return-ptr-range.cpp
===
--- test/Analysis/return-ptr-range.cpp
+++ test/Analysis/return-ptr-range.cpp
@@ -0,0 +1,27 @@
+// RUN: %clang_cc1 -analyze -analyzer-checker=alpha.security.ReturnPtrRange -verify %s
+
+int arr[10];
+int *ptr;
+
+int conjure_index();
+
+int *test_element_index_lifetime() {
+ do {
+int x = conjure_index();
+ptr = arr + x;
+if (x != 20)
+ return arr; // no-warning
+ } while (0);
+ return ptr; // expected-warning{{Returned pointer value points outside the original object (potential buffer overflow)}}
+}
+
+int *test_element_index_lifetime_with_local_ptr() {
+ int *local_ptr;
+ do {
+int x = conjure_index();
+local_ptr = arr + x;
+if (x != 20)
+ return arr; // no-warning
+ } while (0);
+ return local_ptr; // expected-warning{{Returned pointer value points outside the original object (potential buffer overflow)}}
+}
Index: lib/StaticAnalyzer/Core/RegionStore.cpp
===
--- lib/StaticAnalyzer/Core/RegionStore.cpp
+++ lib/StaticAnalyzer/Core/RegionStore.cpp
@@ -2260,6 +2260,16 @@
if (const MemRegion *R = V.getAsRegion()) {
AddToWorkList(R);
+// Element index of an element region is live.
+if (const ElementRegion *ER = dyn_cast(R)) {
+ SVal Idx = ER->getIndex();
+ for (SymExpr::symbol_iterator SI = Idx.symbol_begin(),
+SE = Idx.symbol_end();
+ SI != SE; ++SI) {
+SymReaper.markLive(*SI);
+ }
+}
+
// All
