Added remove taint support to ProgramState.

[franchiotta]

Summary

Currently there is support for just adding taint on ProgramState, this would allow to mark symbols as non-tainted.

[krememek]

I don't remember why the 'tainted' methods were added to ProgramState in the first place, but it doesn't seem quite right. Taint can easily be modeled as a set of APIs that modify and produce new ProgramStates, but I don't see why it should be part of ProgramState itself.

[krememek]

In general I'm not a fan of the taint methods being directly on ProgramState, but this extends the current pattern. We could move the APIs elsewhere later.

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

371–372

The parameters from the two lines should line up.

lib/StaticAnalyzer/Core/ProgramState.cpp

679–713

This seems reasonable enough. It mostly mirrors the other taint operations we have, and there is noticeably a fair amount of copy-paste here that I wonder could be better factored. removeTaint looks pretty much identical to addTaint except that it uses the remove function on the TaintMap. I'm particularly concerned about the copy-paste for the first removeTaint, as that is a non-trivial amount of logic. Could this case possibly be refactored a bit with addTaint?

[franchiotta]

In D11700#216472, @krememek wrote:

I don't remember why the 'tainted' methods were added to ProgramState in the first place, but it doesn't seem quite right. Taint can easily be modeled as a set of APIs that modify and produce new ProgramStates, but I don't see why it should be part of ProgramState itself.

Yes, I agree with you Ted. We can leave as it is just for now, and then I can work on that patch. May I assign you as subscriber when submitting it?

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

371–372

Alright

lib/StaticAnalyzer/Core/ProgramState.cpp

679–713

Yes, sure! Let me upload a new patch for this.

[franchiotta]

Basically, I moved the logic of AddTaint out of the method, and placed it on a generic method which allows to add or remove over the map based on a parameter value. All this taint logic will be placed on a external API in a future.

[franchiotta]

Updated refactoring.

[krememek]

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

451–455

Can we add documentation comments for these? Seems like generally useful utility methods. We could also probably just make these public.

lib/StaticAnalyzer/Core/ProgramState.cpp

650–651

Is this even needed? I think Environment::getSVal() already handles parenthesis and other ignored expressions. This looks like dead code.

This can probably just be an inline method in ProgramState.h, that just forwards to getSVal(S, LCtx).getAsSymbol().

Alternatively, if this is only called once, we don't need to add a method at all, since it is just a one liner.

657–658

This looks fishy. 'addTaint' returns a new state, but then the return value is ignored, and 'this' is returned.

657–660

This is just a one-liner. Do we really need this method at all? It is only called once.

685–689

This looks fishy. 'removeTaint' returns a new state, but then the return value is ignored. 'ProgramState' values are immutable, so this method appears to do nothing.

[krememek]

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

451–455

Actually, I'm wondering if we really need to add these at all. They are just one liners that easily could be written where they are used.

[franchiotta]

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

451–455

Right. Removing these methods, and adding the one-liners directly where they are used.

lib/StaticAnalyzer/Core/ProgramState.cpp

650–651

Yes, you are right. It is not needed since it is handle by ignoreTransparentExprs method in Environment module. I will not add this method at all.

657–658

Yes, it does.. I will return at the time the last addTaint is invoked.

657–660

We don't. I will add the one-liner directly where it is used.

685–689

Yes, you are right. I will return at the time the last addTaint is invoked.

[franchiotta]

Some changes made based on the received suggestions.

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

template <typename CB> CB scanReachableSymbols(const SVal *beg,
                                                  const SVal *end) const;
   
   template <typename CB> CB
   scanReachableSymbols(const MemRegion * const *beg,
                        const MemRegion * const *end) const;
 
   /// Create a new state in which the statement is marked as tainted.
   ProgramStateRef addTaint(const Stmt *S, const LocationContext *LCtx,
-                               TaintTagType Kind = TaintTagGeneric) const;
 
   /// Create a new state in which the symbol is marked as tainted.
   ProgramStateRef addTaint(SymbolRef S,
-                               TaintTagType Kind = TaintTagGeneric) const;
 
   /// Create a new state in which the region symbol is marked as tainted.
   ProgramStateRef addTaint(const MemRegion *R,
-                               TaintTagType Kind = TaintTagGeneric) const;
 
+  /// Create a new state in which the statement is marked as non-tainted.
+  ProgramStateRef removeTaint(const Stmt *S, const LocationContext *LCtx,
+                              TaintTagType Kind = TaintTagGeneric) const;
+
+  /// Create a new state in which the symbol is marked as non-tainted.
+  ProgramStateRef removeTaint(SymbolRef S,
+                              TaintTagType Kind = TaintTagGeneric) const;
+
+  /// Create a new state in which the region symbol is marked as non-tainted.
+  ProgramStateRef removeTaint(const MemRegion *R,
+                              TaintTagType Kind = TaintTagGeneric) const;
+
   /// Check if the statement is tainted in the current state.
   bool isTainted(const Stmt *S, const LocationContext *LCtx,
                  TaintTagType Kind = TaintTagGeneric) const;
   bool isTainted(SVal V, TaintTagType Kind = TaintTagGeneric) const;
   bool isTainted(SymbolRef Sym, TaintTagType Kind = TaintTagGeneric) const;
   bool isTainted(const MemRegion *Reg, TaintTagType Kind=TaintTagGeneric) const;
 
   //==---------------------------------------------------------------------==//
   // Accessing the Generic Data Map (GDM).
   //==---------------------------------------------------------------------==//
 
   void *const* FindGDM(void *K) const;
 
   template<typename T>
   ProgramStateRef add(typename ProgramStateTrait<T>::key_type K) const;
private:
   invalidateRegionsImpl(ArrayRef<SVal> Values,
                         const Expr *E, unsigned BlockCount,
                         const LocationContext *LCtx,
                         bool ResultsInSymbolEscape,
                         InvalidatedSymbols *IS,
                         RegionAndSymbolInvalidationTraits *HTraits,
                         const CallEvent *Call) const;
 };
 
 //===----------------------------------------------------------------------===//
 // ProgramStateManager - Factory object for ProgramStates.
 //===----------------------------------------------------------------------===//
 
 class ProgramStateManager {
   friend class ProgramState;
   friend void ProgramStateRelease(const ProgramState *state);
 private:
   /// Eng - The SubEngine that owns this state manager.
   SubEngine *Eng; /* Can be null. */
 
   EnvironmentManager                   EnvMgr;

lib/StaticAnalyzer/Core/ProgramState.cpp

bool ProgramState::scanReachableSymbols(const MemRegion * const *I,
                                    SymbolVisitor &visitor) const {
   ScanReachableSymbols S(this, visitor);
   for ( ; I != E; ++I) {
     if (!S.scan(*I))
       return false;
   }
   return true;
 }
 
-ProgramStateRef ProgramState::addTaint(const Stmt *S,
-                                           const LocationContext *LCtx,
-                                           TaintTagType Kind) const {
-  if (const Expr *E = dyn_cast_or_null<Expr>(S))
-    S = E->IgnoreParens();
-
+ProgramStateRef ProgramState::addTaint(const Stmt *S, const LocationContext
+                                       *LCtx, TaintTagType Kind) const {
   SymbolRef Sym = getSVal(S, LCtx).getAsSymbol();
   if (Sym)
     return addTaint(Sym, Kind);
 
   const MemRegion *R = getSVal(S, LCtx).getAsRegion();
-  addTaint(R, Kind);
-
-  // Cannot add taint, so just return the state.
-  return this;
+  return addTaint(R, Kind);
 }
 
 ProgramStateRef ProgramState::addTaint(const MemRegion *R,
-                                           TaintTagType Kind) const {
   if (const SymbolicRegion *SR = dyn_cast_or_null<SymbolicRegion>(R))
     return addTaint(SR->getSymbol(), Kind);
   return this;
 }
 
-ProgramStateRef ProgramState::addTaint(SymbolRef Sym,
-                                           TaintTagType Kind) const {
+ProgramStateRef ProgramState::addTaint(SymbolRef Sym, TaintTagType Kind) const {
   // If this is a symbol cast, remove the cast before adding the taint. Taint
   // is cast agnostic.
   while (const SymbolCast *SC = dyn_cast<SymbolCast>(Sym))
     Sym = SC->getOperand();
 
   ProgramStateRef NewState = set<TaintMap>(Sym, Kind);
   assert(NewState);
   return NewState;
 }
 
+ProgramStateRef ProgramState::removeTaint(const Stmt *S, const LocationContext
+                                          *LCtx, TaintTagType Kind) const {
+  SymbolRef Sym = getSVal(S, LCtx).getAsSymbol();
+  if (Sym)
+    return removeTaint(Sym, Kind);
+
+  const MemRegion *R = getSVal(S, LCtx).getAsRegion();
+  return removeTaint(R, Kind);
+}
+
+ProgramStateRef ProgramState::removeTaint(const MemRegion *R,
+                                          TaintTagType Kind) const {
+  if (const SymbolicRegion *SR = dyn_cast_or_null<SymbolicRegion>(R))
+    return removeTaint(SR->getSymbol(), Kind);
+  return this;
+}
+
+ProgramStateRef ProgramState::removeTaint(SymbolRef Sym,
+                                          TaintTagType Kind) const {
+  // If this is a symbol cast, remove the cast before removing the taint. Taint
+  // is cast agnostic.
+  while (const SymbolCast *SC = dyn_cast<SymbolCast>(Sym))
+    Sym = SC->getOperand();
+
+  ProgramStateRef NewState = remove<TaintMap>(Sym);
+  assert(NewState);
+  return NewState;
+}
+
 bool ProgramState::isTainted(const Stmt *S, const LocationContext *LCtx,
                              TaintTagType Kind) const {
   if (const Expr *E = dyn_cast_or_null<Expr>(S))
     S = E->IgnoreParens();
 
   SVal val = getSVal(S, LCtx);
   return isTainted(val, Kind);
 }
 
 bool ProgramState::isTainted(SVal V, TaintTagType Kind) const {
   if (const SymExpr *Sym = V.getAsSymExpr())
     return isTainted(Sym, Kind);
   if (const MemRegion *Reg = V.getAsRegion())
     return isTainted(Reg, Kind);