[analyzer] Keep track of escaped locals.

[xazax.hun]

Summary

We want to escape all symbols that are stored into escaped regions. The problem is, we did not know which local regions were escaped. Until now.

[xazax.hun]

So some of the questions that came to my mind:

1. Should this be exposed to the checkers?
2. Where should we actually have this trait registered? ProgramState? ExprEngine? Both of them need access, and due to layering I feel like it cannot be in ExprEngine but I might be wrong.

[NoQ]

I've been hiding these internal traits in ExprEngine lately but i don't have a strong preference. I don't see any immediate need to expose this info to the checkers, nor do i see a need to actively hide it.

And, yeah, needs dead region cleanup :)

clang/lib/StaticAnalyzer/Core/ProgramState.cpp

219–223

Ok, so how do we want to deal with non-base regions? I think for the purposes of escaping we try to stick to per-base-region granularity (cf. the C-style linked list example). This is also going to be nice because the amount of regions we'll have to track is going to be more limited and there's going to be no problem of representing the same region in multiple different ways.

[NoQ]

Hiding the trait in ExprEngine has the additional benefit of disallowing *direct* access to the trait - it can only be accessed through getters. It also doesn't prevent us from exposing the trait to checkers as a method on ProgramState in the future, because ProgramStateManager has access to SubEngine.

[NoQ]

clang/lib/StaticAnalyzer/Core/ProgramState.cpp

48–61

Wait, you are preventing direct access anyway by putting this stuff into the .cpp file.

In this case i think you can safely use the REGISTER_... macros.

[xazax.hun]

• Add cleanup.

[xazax.hun]

clang/lib/StaticAnalyzer/Core/ProgramState.cpp

48–61

Yeah, initially I wanted to hide this trait but at this point I have no idea how to do that. If I get the layering right, ExprEngine is using ProgramState, and ProgramState should not reference ExprEngine. So if I want to use a trait in both it should be in ProgramState. The reason why I also need to touch ProgramState, because the list of invalidated regions are readily available there. Probably it is possible to somehow get that list in ExprEngine, but I think that would be way more complicated than the current solution.

[xazax.hun]

clang/lib/StaticAnalyzer/Core/ProgramState.cpp

48–61

Well, I realized that ProgramState can access SubEngine, so as long as we extend the abstract interface there we could move the trait to ExprEngine. What do you prefer?

[NoQ]

Looks great, thanks! I'd love to see what effect it immediately causes and whether there will be any true or false negatives because of this change.

Also i-i-it's not that i insist or something, but somebody will have to add it to the exploded graph dumps :)

clang/lib/StaticAnalyzer/Core/ProgramState.cpp

48–61

I very slightly prefer to have it in ExprEngine because it's consistent with other existing traits: defined in the place in which they're maintained, don't show up in the overall definition of the ProgramState.

[xazax.hun]

• A first take on trying to reuse processPointerEscapedOnBind.

[xazax.hun]

Whoops, this one was updated accidentally. Wrong tab :(

clang/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h

 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_PROGRAMSTATE_H
 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_PROGRAMSTATE_H
 
 #include "clang/Basic/LLVM.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeInfo.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/Environment.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/Store.h"
 #include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/ImmutableMap.h"
+#include "llvm/ADT/ImmutableSet.h"
 #include "llvm/Support/Allocator.h"
 #include <utility>
 
 namespace llvm {
 class APSInt;
-}
+} // namespace llvm
 
 namespace clang {
 class ASTContext;
 
 namespace ento {
 
 class AnalysisManager;
 class CallEvent;

 template <typename T> struct ProgramStateTrait {
   typedef typename T::data_type data_type;
   static inline void *MakeVoidPtr(data_type D) { return (void*) D; }
   static inline data_type MakeData(void *const* P) {
     return P ? (data_type) *P : (data_type) 0;
   }
 };
 
+/// Tag for GDM.
+struct EscapedLocals{
+  using data_type = llvm::ImmutableSet<const MemRegion *>;
+};
+template <>
+struct ProgramStateTrait<EscapedLocals> :
+  public ProgramStatePartialTrait<llvm::ImmutableSet<const MemRegion *>> {
+  static void *GDMIndex();
+};
+
 /// \class ProgramState
 /// ProgramState - This class encapsulates:
 ///
 ///    1. A mapping from expressions to values (Environment)
 ///    2. A mapping from locations to values (Store)
 ///    3. Constraints on symbolic values (GenericDataMap)
 ///
 ///  Together these represent the "abstract state" of a program.
public:
   SVal getSVal(const MemRegion* R, QualType T = QualType()) const;
 
   /// Return the value bound to the specified location, assuming
   /// that the value is a scalar integer or an enumeration or a pointer.
   /// Returns UnknownVal() if none found or the region is not known to hold
   /// a value of such type.
   SVal getSValAsScalarOrLoc(const MemRegion *R) const;
 
+  /// TODO
+  bool isEscapedLocal(const MemRegion *R) const;
+
   using region_iterator = const MemRegion **;
 
   /// Visits the symbols reachable from the given SVal using the provided
   /// SymbolVisitor.
   ///
   /// This is a convenience API. Consider using ScanReachableSymbols class
   /// directly when making multiple scans on the same state with the same
   /// visitor to avoid repeated initialization cost.
public:
 
   bool scan(nonloc::LazyCompoundVal val);
   bool scan(nonloc::CompoundVal val);
   bool scan(SVal val);
   bool scan(const MemRegion *R);
   bool scan(const SymExpr *sym);
 };
 
-} // end ento namespace
+} // namespace ento
 
-} // end clang namespace
+} // namespace clang
 
 #endif

clang/lib/StaticAnalyzer/Core/ExprEngine.cpp

void ExprEngine::removeDead(ExplodedNode *Pred, ExplodedNodeSet &Out,
 
   for (auto I : CleanedState->get<ObjectsUnderConstruction>()) {
     if (SymbolRef Sym = I.second.getAsSymbol())
       SymReaper.markLive(Sym);
     if (const MemRegion *MR = I.second.getAsRegion())
       SymReaper.markLive(MR);
   }
 
+  EscapedLocals::data_type EscapedRegions = CleanedState->get<EscapedLocals>();
+  for (const MemRegion *MR : EscapedRegions) {
+    if (!SymReaper.isLiveRegion(MR))
+      CleanedState = CleanedState->remove<EscapedLocals>(MR);
+  }
+
   getCheckerManager().runCheckersForLiveSymbols(CleanedState, SymReaper);
 
   // Create a state in which dead bindings are removed from the environment
   // and the store. TODO: The function should just return new env and store,
   // not a new state.
   CleanedState = StateMgr.removeDeadBindingsFromEnvironmentAndStore(
       CleanedState, SFC, SymReaper);
 
Bldr.generateNode(AE, I, State, nullptr,
                       ProgramPoint::PostStmtKind);
   }
 
   getCheckerManager().runCheckersForPostStmt(Dst, AfterInvalidateSet, AE, *this);
 }
 
 // A value escapes in four possible cases:
 // (1) We are binding to something that is not a memory region.
-// (2) We are binding to a MemRegion that does not have stack storage.
+// (2) We are binding to a MemRegion that does not have stack storage
+//     or the stack storage is escaped.
 // (3) We are binding to a top-level parameter region with a non-trivial
 //     destructor. We won't see the destructor during analysis, but it's there.
 // (4) We are binding to a MemRegion with stack storage that the store
 //     does not understand.
 ProgramStateRef
 ExprEngine::processPointerEscapedOnBind(ProgramStateRef State, SVal Loc,
                                         SVal Val, const LocationContext *LCtx) {
 
   // Cases (1) and (2).
   const MemRegion *MR = Loc.getAsRegion();
-  if (!MR || !MR->hasStackStorage())
+  if (!MR || !MR->hasStackStorage() || State->isEscapedLocal(MR))
     return escapeValue(State, Val, PSK_EscapeOnBind);
 
   // Case (3).
   if (const auto *VR = dyn_cast<VarRegion>(MR->getBaseRegion()))
     if (VR->hasStackParametersStorage() && VR->getStackFrame()->inTopFrame())
       if (const auto *RD = VR->getValueType()->getAsCXXRecordDecl())
         if (!RD->hasTrivialDestructor())
           return escapeValue(State, Val, PSK_EscapeOnBind);

clang/lib/StaticAnalyzer/Core/ProgramState.cpp

 //===----------------------------------------------------------------------===//
 
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
 #include "clang/Analysis/CFG.h"
 #include "clang/Basic/JsonSupport.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace clang;
 using namespace ento;
 
 namespace clang { namespace  ento {
void ProgramStateRelease(const ProgramState *state) {
   ProgramState *s = const_cast<ProgramState*>(state);
   if (--s->refCount == 0) {
     ProgramStateManager &Mgr = s->getStateManager();
     Mgr.StateSet.RemoveNode(s);
     s->~ProgramState();
     Mgr.freeStates.push_back(s);
   }
 }
-}}
+} // namespace ento
+} // namespace clang
+
+void *ProgramStateTrait<EscapedLocals>::GDMIndex() {
+  static int index = 0;
+  return &index;
+}
 
 ProgramState::ProgramState(ProgramStateManager *mgr, const Environment& env,
                  StoreRef st, GenericDataMap gdm)
   : stateMgr(mgr),
     Env(env),
     store(st.getStore()),
     GDM(gdm),
     refCount(0) {
   stateMgr->getStoreManager().incrementReferenceCount(store);
 }
 
 ProgramState::ProgramState(const ProgramState &RHS)
     : llvm::FoldingSetNode(),
       stateMgr(RHS.stateMgr),
       Env(RHS.Env),
       store(RHS.store),
       GDM(RHS.GDM),
       refCount(0) {
ProgramState::invalidateRegionsImpl(ValueList Values,
   const StoreRef &newStore
   = Mgr.StoreMgr->invalidateRegions(getStore(), Values, E, Count, LCtx, Call,
                                     *IS, *ITraits, &TopLevelInvalidated,
                                     &Invalidated);
 
   ProgramStateRef newState = makeWithStore(newStore);
 
   if (CausedByPointerEscape) {
+    for (const MemRegion *R : Invalidated) {
+      if (!R->hasStackStorage())
+        continue;
+      newState = newState->add<EscapedLocals>(R->getBaseRegion());
+    }
+
     newState = Eng.notifyCheckersOfPointerEscape(newState, IS,
                                                  TopLevelInvalidated,
                                                  Call,
                                                  *ITraits);
   }
 
   return Eng.processRegionChanges(newState, IS, TopLevelInvalidated,
                                   Invalidated, LCtx, Call);
bool ProgramState::scanReachableSymbols(
     SymbolVisitor &visitor) const {
   ScanReachableSymbols S(this, visitor);
   for (const MemRegion *R : Reachable) {
     if (!S.scan(R))
       return false;
   }
   return true;
 }
+
+bool ProgramState::isEscapedLocal(const MemRegion *R) const {
+  return this->contains<EscapedLocals>(R->getBaseRegion());
+}

clang/test/Analysis/symbol-escape.cpp

C **indirect_escape_in_bitwise_op() {
   Baz = reinterpret_cast<C **>(reinterpret_cast<uintptr_t>(Baz) &
                    ~static_cast<uintptr_t>(0x1));
   // no-warning: "Potential leak of memory pointed to by 'Qux'" was here.
 
   delete *Baz;
   return Baz;
 }
 
+void save_ptr(int **);
+void delete_saved();
+
+void store_to_escaped_region() {
+  int *p;
+  save_ptr(&p);
+  p = new int;
+  delete_saved();
+} // no-warning:
+