[analyzer] Revise GenericTaintChecker's internal representation

[boga95]

Summary

Use a more optimal data structure to represent taint propagation rules. There is no change in the checker's behavior.
Clean up the code.

[kristina]

If you don't mind, please submit diffs with full context (diff -U99999 or something alike depending on what you use). It makes it much easier to review patches. Also the formatting looks really off in some places where 4 spaces are used. Also another nitpick, nested statement ifs should have the statements within them aligned without adding another indentation level for every line break within the statement, also in case below dyn_cast_or_null may eliminate a need for an additional check in which case you can just use && instead.

if ((D->getName().find("stdin") != StringRef::npos) && D->isExternC())
  if (const PointerType *PtrTy =
          dyn_cast<PointerType>(D->getType().getTypePtr()))
    if (PtrTy->getPointeeType().getCanonicalType() ==
        C.getASTContext().getFILEType().getCanonicalType())
      return true;

Also, is there a reason for pulling in <utility> here?

[Szelethus]

Could you please reupload with full context? :)
https://llvm.org/docs/Phabricator.html#requesting-a-review-via-the-web-interface

[boga95]

Upload diff with full context.

[Szelethus]

lib/StaticAnalyzer/Checkers/GenericTaintChecker.cpp

207–229

Hmmm, the formatting part change already is in your other revision, D54918. Can you please rebase this patch on top of it, and add it as a dependency (that can be done on the right side, "Edit related revisions...").

[boga95]

I use std::move which is in the <utility>.

[Szelethus]

Hmm, I find the revision title and summary a little vague -- I'd expect a revision called "Refactoring" not to feature any funcitonal change, yet you changed how variadic functions are handled. Please

• Keep purely formatting changes to your earlier revision, and rebase this patch on that
• Edit the revision title and/or summary about what your patch does,
• If it features any change in the checker's behavior, include tests.

lib/StaticAnalyzer/Checkers/GenericTaintChecker.cpp

127

typo: marks

134–139

I like this a lot! Call sites look very nice.

145–158

In-class method definitions are implicitly inline -- could you please remove them while we're cleaning up anyways? :)

[boga95]

Rebase patch on the earlier version. Remove unnecessary inline specifiers. Fix typo.

[NoQ]

Hi, thanks again for looking into this! I have a single piece of doubt that this doesn't change the behavior (the comment about pread), but other than that, this diff is good to go, in my opinion.

lib/StaticAnalyzer/Checkers/GenericTaintChecker.cpp

209

llvm::ArrayRef has a fancy feature: it can be constructed not only from an initializer list, but also from a single element. This could have allowed skipping {} in these constructors when there is just one value in the list. That's what i would have done, but i guess it's up to you to decide which approach is prettier.

221

Now pread doesn't produce a tainted result when only the buffer is tainted but other arguments are not. Is it a functional change? I guess we should be able to add tests for it. You can also commit this patch with {0, 1, 2, 3} and remove 1 in the next patch that also adds a test.

461–462

auto here as well?

462–463

The more natural way to write this is ArgNum >= CE->getNumArgs(), as opposed to ArgNum < CE->getNumArgs() which is the usual boundary when dealing with arrays that start at 0.

481–482

auto here as well?

[a_sidorin]

lib/StaticAnalyzer/Checkers/GenericTaintChecker.cpp

154

llvm::find?

190

This string formatting change looks a bit broken.

342–343

for (unsigned ArgNum : TaintArgs)?

481–482

for (unsigned ArgNum : DstArgs)?

[boga95]

Is it ready to land?

lib/StaticAnalyzer/Checkers/GenericTaintChecker.cpp

209

Those who don't know that feature will be confused. I should make changes in the constructor to support it. I'm going to leave it.

221

I changed it to {0, 1, 2, 3}. I don't want to make any change in the behavior in this patch. I think who made it use InvalidArgIndex because the previous implementation wasn't expressive enough.

[NoQ]

In D55734#1372972, @boga95 wrote:

Is it ready to land?

Whooooops. Yes, right, it's totally ready to land! Sorry. Should i commit?

[boga95]

Yes, thank you.

[NoQ]

Hmm, the diff is a mixture of D54918 and this patch. I'll apply it by reverting D54918 locally and then applying this diff, but please let us know if you accidentally uploaded a wrong diff!

lib/StaticAnalyzer/Checkers/GenericTaintChecker.cpp

 #include "clang/AST/Attr.h"
 #include "clang/Basic/Builtins.h"
 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
 #include "clang/StaticAnalyzer/Core/Checker.h"
 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
 #include <climits>
+#include <initializer_list>
+#include <utility>
 
 using namespace clang;
 using namespace ento;
 
 namespace {
 class GenericTaintChecker
     : public Checker<check::PostStmt<CallExpr>, check::PreStmt<CallExpr>> {
 public:
   static void *getTag() {
     static int Tag;
     return &Tag;
   }
 
   void checkPostStmt(const CallExpr *CE, CheckerContext &C) const;
 
   void checkPreStmt(const CallExpr *CE, CheckerContext &C) const;
 
 private:
   static const unsigned InvalidArgIndex = UINT_MAX;
   /// Denotes the return vale.
   static const unsigned ReturnValueIndex = UINT_MAX - 1;
 
   mutable std::unique_ptr<BugType> BT;
-  inline void initBugType() const {
+  void initBugType() const {
     if (!BT)
       BT.reset(new BugType(this, "Use of Untrusted Data", "Untrusted Data"));
   }
 
   /// Catch taint related bugs. Check if tainted data is passed to a
   /// system call etc.
   bool checkPre(const CallExpr *CE, CheckerContext &C) const;
 
private:
   /// Check if the region the expression evaluates to is the standard input,
   /// and thus, is tainted.
   static bool isStdin(const Expr *E, CheckerContext &C);
 
   /// Given a pointer argument, return the value it points to.
   static Optional<SVal> getPointedToSVal(CheckerContext &C, const Expr *Arg);
 
   /// Functions defining the attack surface.
-  typedef ProgramStateRef (GenericTaintChecker::*FnCheck)(
+  using FnCheck = ProgramStateRef (GenericTaintChecker::*)(
       const CallExpr *, CheckerContext &C) const;
   ProgramStateRef postScanf(const CallExpr *CE, CheckerContext &C) const;
   ProgramStateRef postSocket(const CallExpr *CE, CheckerContext &C) const;
   ProgramStateRef postRetTaint(const CallExpr *CE, CheckerContext &C) const;
 
   /// Taint the scanned input if the file is tainted.
   ProgramStateRef preFscanf(const CallExpr *CE, CheckerContext &C) const;
 
private:
   static const char MsgTaintedBufferSize[];
   bool checkTaintedBufferSize(const CallExpr *CE, const FunctionDecl *FDecl,
                               CheckerContext &C) const;
 
   /// Generate a report if the expression is tainted or points to tainted data.
   bool generateReportIfTainted(const Expr *E, const char Msg[],
                                CheckerContext &C) const;
 
-  typedef SmallVector<unsigned, 2> ArgVector;
+  using ArgVector = SmallVector<unsigned, 2>;
 
   /// A struct used to specify taint propagation rules for a function.
   ///
   /// If any of the possible taint source arguments is tainted, all of the
   /// destination arguments should also be tainted. Use InvalidArgIndex in the
   /// src list to specify that all of the arguments can introduce taint. Use
   /// InvalidArgIndex in the dst arguments to signify that all the non-const
   /// pointer and reference arguments might be tainted on return. If
   /// ReturnValueIndex is added to the dst list, the return value will be
   /// tainted.
   struct TaintPropagationRule {
+    enum class VariadicType { None, Src, Dst };
+
     /// List of arguments which can be taint sources and should be checked.
     ArgVector SrcArgs;
     /// List of arguments which should be tainted on function return.
     ArgVector DstArgs;
-    // TODO: Check if using other data structures would be more optimal.
-
-    TaintPropagationRule() {}
-
-    TaintPropagationRule(unsigned SArg, unsigned DArg, bool TaintRet = false) {
-      SrcArgs.push_back(SArg);
-      DstArgs.push_back(DArg);
-      if (TaintRet)
-        DstArgs.push_back(ReturnValueIndex);
-    }
-
-    TaintPropagationRule(unsigned SArg1, unsigned SArg2, unsigned DArg,
-                         bool TaintRet = false) {
-      SrcArgs.push_back(SArg1);
-      SrcArgs.push_back(SArg2);
-      DstArgs.push_back(DArg);
-      if (TaintRet)
-        DstArgs.push_back(ReturnValueIndex);
-    }
+    /// Index for the first variadic parameter if exist.
+    unsigned VariadicIndex;
+    /// Show when a function has variadic parameters. If it has, it marks all
+    /// of them as source or destination.
+    VariadicType VarType;
+
+    TaintPropagationRule()
+        : VariadicIndex(InvalidArgIndex), VarType(VariadicType::None) {}
+
+    TaintPropagationRule(std::initializer_list<unsigned> &&Src,
+                         std::initializer_list<unsigned> &&Dst,
+                         VariadicType Var = VariadicType::None,
+                         unsigned VarIndex = InvalidArgIndex)
+        : SrcArgs(std::move(Src)), DstArgs(std::move(Dst)),
+          VariadicIndex(VarIndex), VarType(Var) {}
 
     /// Get the propagation rule for a given function.
     static TaintPropagationRule
     getTaintPropagationRule(const FunctionDecl *FDecl, StringRef Name,
                             CheckerContext &C);
 
-    inline void addSrcArg(unsigned A) { SrcArgs.push_back(A); }
-    inline void addDstArg(unsigned A) { DstArgs.push_back(A); }
+    void addSrcArg(unsigned A) { SrcArgs.push_back(A); }
+    void addDstArg(unsigned A) { DstArgs.push_back(A); }
 
-    inline bool isNull() const { return SrcArgs.empty(); }
+    bool isNull() const {
+      return SrcArgs.empty() && DstArgs.empty() &&
+             VariadicType::None == VarType;
+    }
 
-    inline bool isDestinationArgument(unsigned ArgNum) const {
-      return (std::find(DstArgs.begin(), DstArgs.end(), ArgNum) !=
-              DstArgs.end());
+    bool isDestinationArgument(unsigned ArgNum) const {
+      return (llvm::find(DstArgs, ArgNum) != DstArgs.end());
     }
 
-    static inline bool isTaintedOrPointsToTainted(const Expr *E,
-                                                  ProgramStateRef State,
-                                                  CheckerContext &C) {
+    static bool isTaintedOrPointsToTainted(const Expr *E, ProgramStateRef State,
       if (State->isTainted(E, C.getLocationContext()) || isStdin(E, C))
         return true;
 
       if (!E->getType().getTypePtr()->isPointerType())
         return false;
 
       Optional<SVal> V = getPointedToSVal(C, E);
       return (V && State->isTainted(*V));

 
 const char GenericTaintChecker::MsgSanitizeSystemArgs[] =
     "Untrusted data is passed to a system call "
     "(CERT/STR02-C. Sanitize data passed to complex subsystems)";
 
 const char GenericTaintChecker::MsgTaintedBufferSize[] =
     "Untrusted data is used to specify the buffer size "
     "(CERT/STR31-C. Guarantee that storage for strings has sufficient space "
-    "for "
-    "character data and the null terminator)";
+    "for character data and the null terminator)";
 
 } // end of anonymous namespace
 
 /// A set which is used to pass information from call pre-visit instruction
 /// to the call post-visit. The values are unsigned integers, which are either
 /// ReturnValueIndex, or indexes of the pointer/reference argument, which
 /// points to data, which should be tainted on return.
 REGISTER_SET_WITH_PROGRAMSTATE(TaintArgsOnPostVisit, unsigned)
 
 GenericTaintChecker::TaintPropagationRule
 GenericTaintChecker::TaintPropagationRule::getTaintPropagationRule(
     const FunctionDecl *FDecl, StringRef Name, CheckerContext &C) {
   // TODO: Currently, we might lose precision here: we always mark a return
   // value as tainted even if it's just a pointer, pointing to tainted data.
 
   // Check for exact name match for functions without builtin substitutes.
   TaintPropagationRule Rule =
       llvm::StringSwitch<TaintPropagationRule>(Name)
-          .Case("atoi", TaintPropagationRule(0, ReturnValueIndex))
-          .Case("atol", TaintPropagationRule(0, ReturnValueIndex))
-          .Case("atoll", TaintPropagationRule(0, ReturnValueIndex))
-          .Case("getc", TaintPropagationRule(0, ReturnValueIndex))
-          .Case("fgetc", TaintPropagationRule(0, ReturnValueIndex))
-          .Case("getc_unlocked", TaintPropagationRule(0, ReturnValueIndex))
-          .Case("getw", TaintPropagationRule(0, ReturnValueIndex))
-          .Case("toupper", TaintPropagationRule(0, ReturnValueIndex))
-          .Case("tolower", TaintPropagationRule(0, ReturnValueIndex))
-          .Case("strchr", TaintPropagationRule(0, ReturnValueIndex))
-          .Case("strrchr", TaintPropagationRule(0, ReturnValueIndex))
-          .Case("read", TaintPropagationRule(0, 2, 1, true))
-          .Case("pread", TaintPropagationRule(InvalidArgIndex, 1, true))
-          .Case("gets", TaintPropagationRule(InvalidArgIndex, 0, true))
-          .Case("fgets", TaintPropagationRule(2, 0, true))
-          .Case("getline", TaintPropagationRule(2, 0))
-          .Case("getdelim", TaintPropagationRule(3, 0))
-          .Case("fgetln", TaintPropagationRule(0, ReturnValueIndex))
+          .Case("atoi", TaintPropagationRule({0}, {ReturnValueIndex}))
+          .Case("atol", TaintPropagationRule({0}, {ReturnValueIndex}))
+          .Case("atoll", TaintPropagationRule({0}, {ReturnValueIndex}))
+          .Case("getc", TaintPropagationRule({0}, {ReturnValueIndex}))
+          .Case("fgetc", TaintPropagationRule({0}, {ReturnValueIndex}))
+          .Case("getc_unlocked", TaintPropagationRule({0}, {ReturnValueIndex}))
+          .Case("getw", TaintPropagationRule({0}, {ReturnValueIndex}))
+          .Case("toupper", TaintPropagationRule({0}, {ReturnValueIndex}))
+          .Case("tolower", TaintPropagationRule({0}, {ReturnValueIndex}))
+          .Case("strchr", TaintPropagationRule({0}, {ReturnValueIndex}))
+          .Case("strrchr", TaintPropagationRule({0}, {ReturnValueIndex}))
+          .Case("read", TaintPropagationRule({0, 2}, {1, ReturnValueIndex}))
+          .Case("pread",
+                TaintPropagationRule({0, 1, 2, 3}, {1, ReturnValueIndex}))
+          .Case("gets", TaintPropagationRule({}, {0, ReturnValueIndex}))
+          .Case("fgets", TaintPropagationRule({2}, {0, ReturnValueIndex}))
+          .Case("getline", TaintPropagationRule({2}, {0}))
+          .Case("getdelim", TaintPropagationRule({3}, {0}))
+          .Case("fgetln", TaintPropagationRule({0}, {ReturnValueIndex}))
           .Default(TaintPropagationRule());
 
   if (!Rule.isNull())
     return Rule;
 
   // Check if it's one of the memory setting/copying functions.
   // This check is specialized but faster then calling isCLibraryFunction.
   unsigned BId = 0;
   if ((BId = FDecl->getMemoryFunctionKind()))
     switch (BId) {
     case Builtin::BImemcpy:
     case Builtin::BImemmove:
     case Builtin::BIstrncpy:
     case Builtin::BIstrncat:
-      return TaintPropagationRule(1, 2, 0, true);
+      return TaintPropagationRule({1, 2}, {0, ReturnValueIndex});
     case Builtin::BIstrlcpy:
     case Builtin::BIstrlcat:
-      return TaintPropagationRule(1, 2, 0, false);
+      return TaintPropagationRule({1, 2}, {0});
     case Builtin::BIstrndup:
-      return TaintPropagationRule(0, 1, ReturnValueIndex);
+      return TaintPropagationRule({0, 1}, {ReturnValueIndex});
 
     default:
       break;
     };
 
   // Process all other functions which could be defined as builtins.
   if (Rule.isNull()) {
-    if (C.isCLibraryFunction(FDecl, "snprintf") ||
-        C.isCLibraryFunction(FDecl, "sprintf"))
-      return TaintPropagationRule(InvalidArgIndex, 0, true);
+    if (C.isCLibraryFunction(FDecl, "snprintf"))
+      return TaintPropagationRule({1}, {0, ReturnValueIndex}, VariadicType::Src,
+                                  3);
+    else if (C.isCLibraryFunction(FDecl, "sprintf"))
+      return TaintPropagationRule({}, {0, ReturnValueIndex}, VariadicType::Src,
+                                  2);
     else if (C.isCLibraryFunction(FDecl, "strcpy") ||
              C.isCLibraryFunction(FDecl, "stpcpy") ||
              C.isCLibraryFunction(FDecl, "strcat"))
-      return TaintPropagationRule(1, 0, true);
+      return TaintPropagationRule({1}, {0, ReturnValueIndex});
     else if (C.isCLibraryFunction(FDecl, "bcopy"))
-      return TaintPropagationRule(0, 2, 1, false);
+      return TaintPropagationRule({0, 2}, {1});
     else if (C.isCLibraryFunction(FDecl, "strdup") ||
              C.isCLibraryFunction(FDecl, "strdupa"))
-      return TaintPropagationRule(0, ReturnValueIndex);
+      return TaintPropagationRule({0}, {ReturnValueIndex});
     else if (C.isCLibraryFunction(FDecl, "wcsdup"))
-      return TaintPropagationRule(0, ReturnValueIndex);
+      return TaintPropagationRule({0}, {ReturnValueIndex});
   }
 
   // Skipping the following functions, since they might be used for cleansing
   // or smart memory copy:
   // - memccpy - copying until hitting a special character.
 
   return TaintPropagationRule();
 }
bool GenericTaintChecker::propagateFromPre(const CallExpr *CE,
   ProgramStateRef State = C.getState();
 
   // Depending on what was tainted at pre-visit, we determined a set of
   // arguments which should be tainted after the function returns. These are
   // stored in the state as TaintArgsOnPostVisit set.
   TaintArgsOnPostVisitTy TaintArgs = State->get<TaintArgsOnPostVisit>();
   if (TaintArgs.isEmpty())
     return false;
 
-  for (llvm::ImmutableSet<unsigned>::iterator I = TaintArgs.begin(),
-                                              E = TaintArgs.end();
-       I != E; ++I) {
-    unsigned ArgNum = *I;
-
+  for (unsigned ArgNum : TaintArgs) {
     // Special handling for the tainted return value.
     if (ArgNum == ReturnValueIndex) {
       State = State->addTaint(CE, C.getLocationContext());
       continue;
     }
 
     // The arguments are pointer arguments. The data they are pointing at is
     // tainted after the call.

 }
 
 ProgramStateRef
 GenericTaintChecker::TaintPropagationRule::process(const CallExpr *CE,
                                                    CheckerContext &C) const {
   ProgramStateRef State = C.getState();
 
   // Check for taint in arguments.
   bool IsTainted = false;
-  for (ArgVector::const_iterator I = SrcArgs.begin(), E = SrcArgs.end(); I != E;
-       ++I) {
-    unsigned ArgNum = *I;
+  for (unsigned ArgNum : SrcArgs) {
+    if (ArgNum >= CE->getNumArgs())
+      return State;
+    if ((IsTainted = isTaintedOrPointsToTainted(CE->getArg(ArgNum), State, C)))
+      break;
+  }
 
-    if (ArgNum == InvalidArgIndex) {
-      // Check if any of the arguments is tainted, but skip the
-      // destination arguments.
-      for (unsigned int i = 0; i < CE->getNumArgs(); ++i) {
-        if (isDestinationArgument(i))
-          continue;
-        if ((IsTainted = isTaintedOrPointsToTainted(CE->getArg(i), State, C)))
-          break;
-      }
-      break;
-    }
+  // Check for taint in variadic arguments.
+  if (!IsTainted && VariadicType::Src == VarType) {
+    // Check if any of the arguments is tainted
+    for (unsigned int i = VariadicIndex; i < CE->getNumArgs(); ++i) {
 
-    if (CE->getNumArgs() < (ArgNum + 1))
-      return State;
-    if ((IsTainted = isTaintedOrPointsToTainted(CE->getArg(ArgNum), State, C)))
-      break;
-  }
   if (!IsTainted)
     return State;
 
   // Mark the arguments which should be tainted after the function returns.
-  for (ArgVector::const_iterator I = DstArgs.begin(), E = DstArgs.end(); I != E;
-       ++I) {
-    unsigned ArgNum = *I;
+  for (unsigned ArgNum : DstArgs) {
+    // Should mark the return value?
+    if (ArgNum == ReturnValueIndex) {
+      State = State->add<TaintArgsOnPostVisit>(ReturnValueIndex);
+      continue;
+    }
 
-    // Should we mark all arguments as tainted?
-    if (ArgNum == InvalidArgIndex) {
-      // For all pointer and references that were passed in:
-      //   If they are not pointing to const data, mark data as tainted.
-      //   TODO: So far we are just going one level down; ideally we'd need to
-      //         recurse here.
-      for (unsigned int i = 0; i < CE->getNumArgs(); ++i) {
-        const Expr *Arg = CE->getArg(i);
-        // Process pointer argument.
-        const Type *ArgTy = Arg->getType().getTypePtr();
-        QualType PType = ArgTy->getPointeeType();
-        if ((!PType.isNull() && !PType.isConstQualified()) ||
-            (ArgTy->isReferenceType() && !Arg->getType().isConstQualified()))
-          State = State->add<TaintArgsOnPostVisit>(i);
-      }
-      continue;
-    }
-
-    // Should mark the return value?
-    if (ArgNum == ReturnValueIndex) {
-      State = State->add<TaintArgsOnPostVisit>(ReturnValueIndex);
-      continue;
-    }
-
-    // Mark the given argument.
-    assert(ArgNum < CE->getNumArgs());
-    State = State->add<TaintArgsOnPostVisit>(ArgNum);
+    // Mark the given argument.
+    assert(ArgNum < CE->getNumArgs());
+    State = State->add<TaintArgsOnPostVisit>(ArgNum);
+  }
+
+  // Mark all variadic arguments tainted if present.
+  if (VariadicType::Dst == VarType) {
+    for (unsigned int i = VariadicIndex; i < CE->getNumArgs(); ++i) {
   }
 
   return State;
 }
 
 // If argument 0 (file descriptor) is tainted, all arguments except for arg 0
 // and arg 1 should get taint.
 ProgramStateRef GenericTaintChecker::preFscanf(const CallExpr *CE,
bool GenericTaintChecker::isStdin(const Expr *E, CheckerContext &C) {
   if (!Sm)
     return false;
   const DeclRegion *DeclReg = dyn_cast_or_null<DeclRegion>(Sm->getRegion());
   if (!DeclReg)
     return false;
 
   // This region corresponds to a declaration, find out if it's a global/extern
   // variable named stdin with the proper type.
-  if (const VarDecl *D = dyn_cast_or_null<VarDecl>(DeclReg->getDecl())) {
+  if (const auto *D = dyn_cast_or_null<VarDecl>(DeclReg->getDecl())) {
     D = D->getCanonicalDecl();
-    if ((D->getName().find("stdin") != StringRef::npos) && D->isExternC())
-      if (const PointerType *PtrTy =
-              dyn_cast<PointerType>(D->getType().getTypePtr()))
-        if (PtrTy->getPointeeType().getCanonicalType() ==
+    if ((D->getName().find("stdin") != StringRef::npos) && D->isExternC()) {
+      const auto *PtrTy = dyn_cast<PointerType>(D->getType().getTypePtr());
+      if (PtrTy && PtrTy->getPointeeType().getCanonicalType() ==
                        C.getASTContext().getFILEType().getCanonicalType())
-          return true;
     }
+  }
   return false;
 }
 
 static bool getPrintfFormatArgumentNum(const CallExpr *CE,
                                        const CheckerContext &C,
                                        unsigned int &ArgNum) {
   // Find if the function contains a format string argument.
   // Handles: fprintf, printf, sprintf, snprintf, vfprintf, vprintf, vsprintf,