[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

213–217

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

47–60

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

47–60

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

47–60

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

47–60

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/ExprEngine.h

protected:
   /// \param[in] ITraits Specifies invalidation traits for regions/symbols.
   ProgramStateRef notifyCheckersOfPointerEscape(
                            ProgramStateRef State,
                            const InvalidatedSymbols *Invalidated,
                            ArrayRef<const MemRegion *> ExplicitRegions,
                            const CallEvent *Call,
                            RegionAndSymbolInvalidationTraits &ITraits) override;
 
+  ProgramStateRef processLocalRegionEscape(ProgramStateRef State,
+                                           const MemRegion *R) const override;
+
   /// A simple wrapper when you only need to notify checkers of pointer-escape
   /// of a single value.
   ProgramStateRef escapeValue(ProgramStateRef State, SVal V,
                               PointerEscapeKind K) const;
 
 public:
   // FIXME: 'tag' should be removed, and a LocationContext should be used
   // instead.

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

 #include "clang/StaticAnalyzer/Core/PathSensitive/Store.h"
 #include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/ImmutableMap.h"
 #include "llvm/Support/Allocator.h"
 #include <utility>
 
 namespace llvm {
 class APSInt;
-}
+} // namespace llvm
 
 namespace clang {
 class ASTContext;
 
 namespace ento {
 
 class AnalysisManager;
 class CallEvent;
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/include/clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h

public:
   inline ProgramStateRef
   processRegionChange(ProgramStateRef state,
                       const MemRegion* MR,
                       const LocationContext *LCtx) {
     return processRegionChanges(state, nullptr, MR, MR, LCtx, nullptr);
   }
 
   virtual ProgramStateRef
-  processPointerEscapedOnBind(ProgramStateRef State, SVal Loc, SVal Val, const LocationContext *LCtx) = 0;
+  processPointerEscapedOnBind(ProgramStateRef State, SVal Loc, SVal Val,
+                              const LocationContext *LCtx) = 0;
 
-  virtual ProgramStateRef
-  notifyCheckersOfPointerEscape(ProgramStateRef State,
-                           const InvalidatedSymbols *Invalidated,
-                           ArrayRef<const MemRegion *> ExplicitRegions,
-                           const CallEvent *Call,
-                           RegionAndSymbolInvalidationTraits &HTraits) = 0;
+  virtual ProgramStateRef notifyCheckersOfPointerEscape(
+      ProgramStateRef State, const InvalidatedSymbols *Invalidated,
+      ArrayRef<const MemRegion *> ExplicitRegions, const CallEvent *Call,
 
+  virtual ProgramStateRef
+  processLocalRegionEscape(ProgramStateRef State, const MemRegion *R) const = 0;
+
   /// printJson - Called by ProgramStateManager to print checker-specific data.
   virtual void printJson(raw_ostream &Out, ProgramStateRef State,
                          const LocationContext *LCtx, const char *NL,
                          unsigned int Space, bool IsDot) const = 0;
 
   /// Called by CoreEngine when the analysis worklist is either empty or the
   //  maximum number of analysis steps have been reached.
   virtual void processEndWorklist() = 0;
 };
 
 } // end GR namespace
 
 } // end clang namespace
 
 #endif

clang/lib/StaticAnalyzer/Core/ExprEngine.cpp

 };
 } // namespace
 
 typedef llvm::ImmutableMap<ConstructedObjectKey, SVal>
     ObjectsUnderConstructionMap;
 REGISTER_TRAIT_WITH_PROGRAMSTATE(ObjectsUnderConstruction,
                                  ObjectsUnderConstructionMap)
 
+REGISTER_SET_WITH_PROGRAMSTATE(EscapedLocals, const MemRegion *)
+
 //===----------------------------------------------------------------------===//
 // Engine construction and deletion.
 //===----------------------------------------------------------------------===//
 
 static const char* TagProviderName = "ExprEngine";
 
 ExprEngine::ExprEngine(cross_tu::CrossTranslationUnitContext &CTU,
                        AnalysisManager &mgr,
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);
   }
 
+  EscapedLocalsTy 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);
 
ProgramStateRef ExprEngine::escapeValue(ProgramStateRef State, SVal V,
   };
 
   const CollectReachableSymbolsCallback &Scanner =
       State->scanReachableSymbols<CollectReachableSymbolsCallback>(V);
   return getCheckerManager().runCheckersForPointerEscape(
       State, Scanner.getSymbols(), /*CallEvent*/ nullptr, K, nullptr);
 }
 
+ProgramStateRef ExprEngine::processLocalRegionEscape(ProgramStateRef State,
+                                                     const MemRegion *R) const {
+  return State->add<EscapedLocals>(R);
+}
+
 void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred,
                        ExplodedNodeSet &DstTop) {
   PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
                                 S->getBeginLoc(), "Error evaluating statement");
   ExplodedNodeSet Dst;
   StmtNodeBuilder Bldr(Pred, DstTop, *currBldrCtx);
 
   assert(!isa<Expr>(S) || S == cast<Expr>(S)->IgnoreParens());
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->contains<EscapedLocals>(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

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
 
 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) {
   stateMgr->getStoreManager().incrementReferenceCount(store);
 }
 
 ProgramState::~ProgramState() {
   if (store)
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 = Eng.processLocalRegionEscape(newState, R->getBaseRegion());
+    }
+
     newState = Eng.notifyCheckersOfPointerEscape(newState, IS,
                                                  TopLevelInvalidated,
                                                  Call,
                                                  *ITraits);
   }
 
   return Eng.processRegionChanges(newState, IS, TopLevelInvalidated,
                                   Invalidated, LCtx, Call);

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