[analyzer] Adding basic building blocks for taint propagation.

TaintTag.h will contain definitions of different taint kinds and their properties.
TaintManager will be responsible for implementing taint specific operations, storing taint.
ProgramState will provide API to add/remove taint.

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@144824 91177308-0d34-0410-b5e6-96231b3b80d8

4 files changed, 131 insertions, 0 deletions

diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h
index edae06e68c..d70600f299 100644
--- a/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h
+++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h
@@ -19,6 +19,7 @@
 #include "clang/StaticAnalyzer/Core/PathSensitive/Environment.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/Store.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/TaintTag.h"
 #include "llvm/ADT/PointerIntPair.h"
 #include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/ImmutableMap.h"
@@ -288,6 +289,19 @@ public:
   scanReachableSymbols(const MemRegion * const *beg,
                        const MemRegion * const *end) const;
 
+  /// Create a new state in which the statement is marked as tainted.
+  const ProgramState* addTaint(const Stmt *S,
+                               TaintTagType Kind = TaintTagGeneric) const;
+
+  /// Create a new state in which the symbol is marked as tainted.
+  const ProgramState* addTaint(SymbolRef S,
+                               TaintTagType Kind = TaintTagGeneric) const;
+
+  /// Check if the statement is tainted in the current state.
+  bool isTainted(const Stmt *S, TaintTagType Kind = TaintTagGeneric) const;
+  bool isTainted(SVal V, TaintTagType Kind = TaintTagGeneric) const;
+  bool isTainted(const SymExpr* Sym, TaintTagType Kind = TaintTagGeneric) const;
+
   //==---------------------------------------------------------------------==//
   // Accessing the Generic Data Map (GDM).
   //==---------------------------------------------------------------------==//
diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/TaintManager.h b/include/clang/StaticAnalyzer/Core/PathSensitive/TaintManager.h
new file mode 100644
index 0000000000..4a5b31cb9b
--- /dev/null
+++ b/include/clang/StaticAnalyzer/Core/PathSensitive/TaintManager.h
@@ -0,0 +1,40 @@
+//== TaintManager.h - Managing taint --------------------------- -*- C++ -*--=//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file provides APIs for adding, removing, querying symbol taint.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TAINTMANAGER_H
+#define LLVM_CLANG_TAINTMANAGER_H
+
+#include "clang/StaticAnalyzer/Core/PathSensitive/TaintTag.h"
+
+namespace clang {
+namespace ento {
+
+/// The GDM component containing the tainted root symbols. We lazily infer the
+/// taint of the dependednt symbols. Currently, this is a map from a symbol to
+/// tag kind. TODO: Should support multiple tag kinds.
+struct TaintMap {};
+typedef llvm::ImmutableMap<SymbolRef, TaintTagType> TaintMapImpl;
+template<> struct ProgramStateTrait<TaintMap>
+    :  public ProgramStatePartialTrait<TaintMapImpl> {
+  static void *GDMIndex() { static int index = 0; return &index; }
+};
+
+class TaintManager {
+
+  TaintManager() {}
+};
+
+}
+}
+
+#endif
diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/TaintTag.h b/include/clang/StaticAnalyzer/Core/PathSensitive/TaintTag.h
new file mode 100644
index 0000000000..8ddc8b9d6f
--- /dev/null
+++ b/include/clang/StaticAnalyzer/Core/PathSensitive/TaintTag.h
@@ -0,0 +1,27 @@
+//== TaintTag.h - Path-sensitive "State" for tracking values -*- C++ -*--=//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines a set of taint tags. Several tags are used to differentiate kinds
+// of taint.
+//
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_CLANG_TAINTTAG_H
+#define LLVM_CLANG_TAINTTAG_H
+
+namespace clang {
+namespace ento {
+
+/// The type of taint, which helps to differentiate between different types of
+/// taint.
+typedef unsigned TaintTagType;
+static const TaintTagType TaintTagGeneric = 0;
+
+}}
+
+#endif
diff --git a/lib/StaticAnalyzer/Core/ProgramState.cpp b/lib/StaticAnalyzer/Core/ProgramState.cpp
index 73788cc42e..3ce3db7313 100644
--- a/lib/StaticAnalyzer/Core/ProgramState.cpp
+++ b/lib/StaticAnalyzer/Core/ProgramState.cpp
@@ -15,6 +15,7 @@
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/TaintManager.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace clang;
@@ -623,3 +624,52 @@ bool ProgramState::scanReachableSymbols(const MemRegion * const *I,
   }
   return true;
 }
+
+const ProgramState* ProgramState::addTaint(const Stmt *S,
+                                           TaintTagType Kind) const {
+  SymbolRef Sym = getSVal(S).getAsSymbol();
+  assert(Sym && "Cannot add taint to statements whose value is not a symbol");
+  return addTaint(Sym, Kind);
+}
+
+const ProgramState* ProgramState::addTaint(SymbolRef Sym,
+                                           TaintTagType Kind) const {
+  const ProgramState *NewState = set<TaintMap>(Sym, Kind);
+  assert(NewState);
+  return NewState;
+}
+
+bool ProgramState::isTainted(const Stmt *S, TaintTagType Kind) const {
+  return isTainted(getSVal(S), Kind);
+}
+
+bool ProgramState::isTainted(SVal V, TaintTagType Kind) const {
+  const SymExpr* Sym = V.getAsSymbol();
+  if (!Sym)
+    Sym = V.getAsSymbolicExpression();
+  if (!Sym)
+    return false;
+  return isTainted(Sym, Kind);
+}
+
+bool ProgramState::isTainted(const SymExpr* Sym, TaintTagType Kind) const {
+  // Check taint on derived symbols.
+  if (const SymbolDerived *SD = dyn_cast<SymbolDerived>(Sym))
+    return isTainted(SD->getParentSymbol(), Kind);
+
+  if (const SymIntExpr *SIE = dyn_cast<SymIntExpr>(Sym))
+    return isTainted(SIE->getLHS(), Kind);
+
+  if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(Sym))
+    return (isTainted(SSE->getLHS(), Kind) || isTainted(SSE->getRHS(), Kind));
+
+  // Check taint on the current symbol.
+  if (const SymbolData *SymR = dyn_cast<SymbolData>(Sym)) {
+    const TaintTagType *Tag = get<TaintMap>(SymR);
+    return (Tag && *Tag == Kind);
+  }
+
+  // TODO: Remove llvm unreachable.
+  llvm_unreachable("We do not know show to check taint on this symbol.");
+  return false;
+}