[analyzer] Track multiple raw pointer symbols in DanglingInternalBufferChecker

[rnkovacs]

Summary

Previously, the checker only tracked one raw pointer symbol for each container object.
But member functions returning a pointer to the object's inner buffer may be called on the object several times.
These pointer symbols are now collected in a set inside the program state map and thus all of them is checked for use-after-free problems.

[xazax.hun]

Overall looks good, some nits inline. Let's run it on some projects to exercise this change.

lib/StaticAnalyzer/Checkers/DanglingInternalBufferChecker.cpp

27–42

I think we should use using now instead of typedef.

137–139

Using both contains and get will result in two lookups. Maybe it would be better to just use get and check if the result is nullptr?

138

Is it possible here the set to be empty? We just added a new element to it above. Maybe turn this into an assert or just omit this if it is impossible?

157

Same comment as above.

test/Analysis/dangling-internal-buffer.cpp

111

We started to use lowercase letters for variable names. Maybe this is not the best, since it is not following the LLVM coding guidelines. So I think it would be better to rename this Cond to start with a lowercase letter in this patch for consistency, and update the tests to follow the LLVM coding styleguide in a separate patch later.

[rnkovacs]

Addressed comments.

lib/StaticAnalyzer/Checkers/DanglingInternalBufferChecker.cpp

138

I'm not sure whether add() can fail. I turned it into an assert now and will see if it ever fails.

[xazax.hun]

Thanks! The changes look good, I forgot to mark one double lookup though in my previous review.

lib/StaticAnalyzer/Checkers/DanglingInternalBufferChecker.cpp

121

Oh, there is also a double lookup here, sorry I did not spot it in the initial review.

[rnkovacs]

lib/StaticAnalyzer/Checkers/DanglingInternalBufferChecker.cpp

121

Thanks for noticing. I should have seen it in the first place :)

[NoQ]

Much symbols!

lib/StaticAnalyzer/Checkers/DanglingInternalBufferChecker.cpp

32–40

Please add a comment on how this template is useful. This trick is used by some checkers, but it's a veeeery unobvious trick. We should probably add a macro for that, i.e. REGISTER_FACTORY_WITH_PROGRAMSTATE or something like that.

113

Maybe turn the FIXME into a NOTE or something like that. It indeed seems fine, but let's still make sure the reader realizes that there's a subtle potential problem here.

115

I'd much rather unwrap the symbol here, i.e. if (SymbolRef Sym = RawPtr.getAsSymbol()). A lot of other cornercases may occur if the implementation is accidentally inlined (Undefined, concrete regions). Also, speculatively, .getAsSymbol(/* search for symbolic base = */ true) for the same reason*.

If we didn't care about inlined implementations, the Unknown check would have been redundant. So it should also be safe to straightforwardly ignore inlined implementations by consulting C.wasInlined, then the presence of the symbol can be asserted. But i'd rather speculatively care about inlined implementations as long as it seems easy.

__
* In fact your code relies on a very wonky implementation detail of our SVal hierarchy: namely, pointer-type return values of conservatively evaluated functions are always expressed as &SymRegion{conj_$N<pointer type>} and never as &element{SymRegion{conj_$N<pointer type>}, 0 S32b, pointee type}. Currently nobody knows the rules under which zero element regions are added in different parts of the analyzer, i.e. what is the "canonical" representation of the symbolic pointer, though i made a few attempts to speculate.

119

My favorite idiom for such cases, looks a bit cleaner:

const PtrSet *SetPtr = State->get<RawPtrMap>(ObjRegion)
PtrSet Set = SetPtr ? *SetPtr : F.getEmptySet()

122

This contains check is very unlikely to yield true because if the implementation is not inlined, the symbol is newly born. I'd much rather skip the check; it doesn't sound like it'd make things any faster.

Even better, let's assert that: assert(C.wasInlined || !Set.contains(Sym)). It'll probably help us catch some "reincarnated symbol" bugs in the core.

138

It totally can't. We're just adding an object to a set. What could possibly go wrong?

[rnkovacs]

Thanks very much for your review!

lib/StaticAnalyzer/Checkers/DanglingInternalBufferChecker.cpp

32–40

Should I do that then? Maybe in CheckerContext.h?

115

I wasn't aware of much of this. Thanks for the detailed explanation :)

[NoQ]

Looks great, thanks!

lib/StaticAnalyzer/Checkers/DanglingInternalBufferChecker.cpp

 #include "clang/StaticAnalyzer/Core/BugReporter/CommonBugCategories.h"
 #include "clang/StaticAnalyzer/Core/Checker.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
 
 using namespace clang;
 using namespace ento;
 
-// FIXME: member functions that return a pointer to the container's internal
-// buffer may be called on the object many times, so the object's memory
-// region should have a list of pointer symbols associated with it.
-REGISTER_MAP_WITH_PROGRAMSTATE(RawPtrMap, const MemRegion *, SymbolRef)
+using PtrSet = llvm::ImmutableSet<SymbolRef>;
+
+// Associate container objects with a set of raw pointer symbols.
+REGISTER_MAP_WITH_PROGRAMSTATE(RawPtrMap, const MemRegion *, PtrSet)
+
+namespace clang {
+namespace ento {
+template<> struct ProgramStateTrait<PtrSet>
+  : public ProgramStatePartialTrait<PtrSet> {
+  static void *GDMIndex() {
+    static int Index = 0;
+    return &Index;
+  }
+};
+} // end namespace ento
+} // end namespace clang
 
 namespace {
 
 class DanglingInternalBufferChecker
     : public Checker<check::DeadSymbols, check::PostCall> {
   CallDescription CStrFn, DataFn;
 
 public:
std::shared_ptr<PathDiagnosticPiece> VisitNode(const ExplodedNode *N,
                                                    BugReporterContext &BRC,
                                                    BugReport &BR) override;
 
     // FIXME: Scan the map once in the visitor's constructor and do a direct
     // lookup by region.
     bool isSymbolTracked(ProgramStateRef State, SymbolRef Sym) {
       RawPtrMapTy Map = State->get<RawPtrMap>();
       for (const auto Entry : Map) {
-        if (Entry.second == Sym)
+        if (Entry.second.contains(Sym))
           return true;
       }
       return false;
     }
   };
 
   DanglingInternalBufferChecker() : CStrFn("c_str"), DataFn("data") {}
 

 
 void DanglingInternalBufferChecker::checkPostCall(const CallEvent &Call,
                                                   CheckerContext &C) const {
   const auto *ICall = dyn_cast<CXXInstanceCall>(&Call);
   if (!ICall)
     return;
 
   SVal Obj = ICall->getCXXThisVal();
-  const auto *TypedR = dyn_cast_or_null<TypedValueRegion>(Obj.getAsRegion());
-  if (!TypedR)
+  const auto *ObjRegion = dyn_cast_or_null<TypedValueRegion>(Obj.getAsRegion());
+  if (!ObjRegion)
     return;
 
-  auto *TypeDecl = TypedR->getValueType()->getAsCXXRecordDecl();
+  auto *TypeDecl = ObjRegion->getValueType()->getAsCXXRecordDecl();
   if (TypeDecl->getName() != "basic_string")
     return;
 
   ProgramStateRef State = C.getState();
 
   if (Call.isCalled(CStrFn) || Call.isCalled(DataFn)) {
     SVal RawPtr = Call.getReturnValue();
     if (!RawPtr.isUnknown()) {
-      State = State->set<RawPtrMap>(TypedR, RawPtr.getAsSymbol());
+      // Start tracking this raw pointer by adding it to the set of symbols
+      // associated with this container object in the program state map.
+      PtrSet::Factory &F = State->getStateManager().get_context<PtrSet>();
+      PtrSet NewSet = F.getEmptySet();
+      if (const PtrSet *OldSet = State->get<RawPtrMap>(ObjRegion)) {
+        NewSet = *OldSet;
+        if (NewSet.contains(RawPtr.getAsSymbol()))
+          return;
+      }
+      NewSet = F.add(NewSet, RawPtr.getAsSymbol());
+      assert(!NewSet.isEmpty());
+      State = State->set<RawPtrMap>(ObjRegion, NewSet);
       C.addTransition(State);
     }
     return;
   }
 
   if (isa<CXXDestructorCall>(ICall)) {
-    if (State->contains<RawPtrMap>(TypedR)) {
-      const SymbolRef *StrBufferPtr = State->get<RawPtrMap>(TypedR);
-      // FIXME: What if Origin is null?
+    if (const PtrSet *PS = State->get<RawPtrMap>(ObjRegion)) {
+      // Mark all pointer symbols associated with the deleted object released.
       const Expr *Origin = Call.getOriginExpr();
-      State = allocation_state::markReleased(State, *StrBufferPtr, Origin);
-      State = State->remove<RawPtrMap>(TypedR);
+      for (const auto Symbol : *PS)
+        State = allocation_state::markReleased(State, Symbol, Origin);
+      State = State->remove<RawPtrMap>(ObjRegion);
       C.addTransition(State);
       return;
     }
   }
 }
 
 void DanglingInternalBufferChecker::checkDeadSymbols(SymbolReaper &SymReaper,
                                                      CheckerContext &C) const {
   ProgramStateRef State = C.getState();
+  PtrSet::Factory &F = State->getStateManager().get_context<PtrSet>();
   RawPtrMapTy RPM = State->get<RawPtrMap>();
   for (const auto Entry : RPM) {
-    if (!SymReaper.isLive(Entry.second))
-      State = State->remove<RawPtrMap>(Entry.first);
     if (!SymReaper.isLiveRegion(Entry.first)) {
-      // Due to incomplete destructor support, some dead regions might still
+      // Due to incomplete destructor support, some dead regions might
       // remain in the program state map. Clean them up.
       State = State->remove<RawPtrMap>(Entry.first);
     }
+    if (const PtrSet *OldSet = State->get<RawPtrMap>(Entry.first)) {
+      PtrSet CleanedUpSet = *OldSet;
+      for (const auto Symbol : Entry.second) {
+        if (!SymReaper.isLive(Symbol))
+          CleanedUpSet = F.remove(CleanedUpSet, Symbol);
+      }
+      State = CleanedUpSet.isEmpty()
+              ? State->remove<RawPtrMap>(Entry.first)
+              : State->set<RawPtrMap>(Entry.first, CleanedUpSet);
+    }
   }
   C.addTransition(State);
 }
 
 std::shared_ptr<PathDiagnosticPiece>
 DanglingInternalBufferChecker::DanglingBufferBRVisitor::VisitNode(
     const ExplodedNode *N, const ExplodedNode *PrevN, BugReporterContext &BRC,
     BugReport &BR) {

test/Analysis/dangling-internal-buffer.cpp

const char32_t *c32;
     c32 = s32.data(); // expected-note {{Pointer to dangling buffer was obtained here}}
   } // expected-note {{Internal buffer is released because the object was destroyed}}
   std::u32string s32;
   const char32_t *c32_2 = s32.data();
   consume(c32); // expected-warning {{Use of memory after it is freed}}
   // expected-note@-1 {{Use of memory after it is freed}}
 }
 
+void multiple_symbols(bool cond) {
+  const char *c1, *d1;
+  {
+    std::string s1;
+    c1 = s1.c_str(); // expected-note {{Pointer to dangling buffer was obtained here}}
+    d1 = s1.data(); // expected-note {{Pointer to dangling buffer was obtained here}}
+    const char *local = s1.c_str();
+    consume(local); // no-warning
+  } // expected-note {{Internal buffer is released because the object was destroyed}}
+  // expected-note@-1 {{Internal buffer is released because the object was destroyed}}
+  std::string s2;
+  const char *c2 = s2.c_str();
+  if (cond) {
+    // expected-note@-1 {{Assuming 'cond' is not equal to 0}}
+    // expected-note@-2 {{Taking true branch}}
+    // expected-note@-3 {{Assuming 'cond' is 0}}
+    // expected-note@-4 {{Taking false branch}}
+    consume(c1); // expected-warning {{Use of memory after it is freed}}
+    // expected-note@-1 {{Use of memory after it is freed}}
+  } else {
+    consume(d1); // expected-warning {{Use of memory after it is freed}}
+  } // expected-note@-1 {{Use of memory after it is freed}}
+}
+
 void deref_after_scope_cstr_ok() {
   const char *c;
   std::string s;
   {
     c = s.c_str();
   }
   consume(c); // no-warning
 }