[StaticAnalyzer] Fix ProgramState for static variables that are not written

[danielmarjamaki]

Summary

I saw a false positive where the analyzer made wrong conclusions about a static variable.

Static variables that are not written have known values (initialized values).

This is the (simplified) code that motivated me to create this patch:

static char *allv[] = {
	"rpcgen", "-s", "udp", "-s", "tcp",

};
static int allc = sizeof(allv) / sizeof(allv[0]);

static void f(void) {
	int i;

	for (i = 1; i < allc; i++) {
		const char *p = allv[i];  // <- line 28
		i++;
	}
}

Clang output:

array-fp3.c:28:19: warning: Access out-of-bound array element (buffer overflow)
                const char *p = allv[i];
                                ^~~~~~~

I added testcases that shows this patch solves both false positives and false negatives

[danielmarjamaki]

Minor cleanups. Changed names. Updated comments.

[xazax.hun]

Out of curiosity, does the false positive disappear after making the static variables const?

[danielmarjamaki]

In D37897#871858, @xazax.hun wrote:

Out of curiosity, does the false positive disappear after making the static variables const?

Yes that fixes the false positive

[xazax.hun]

I have some comments and questions but maybe you do not want to address those until Devin, NoQ, or Anna approved the general directions.

lib/StaticAnalyzer/Core/ExprEngine.cpp

107

Usually, we do not like bug recursions since it might eat up the stack.
Also, do you consider the case when the variable is passed by reference to a function in another translation unit?

169

Does this work for non-integer typed e.g. structs?

[NoQ]

The overall idea makes sense to me. I'd like you to join the effort with Peter who during his work on loop widening came up with a matcher-based procedure for finding out if a variable is changed anywhere; it currently lives in LoopUnrolling.cpp and we need only once implementation of that.

[danielmarjamaki]

Fixes according to review comments. Reuse ast matchers in LoopUnrolling.cpp. Avoid some recursion (however the isChanged() is still recursive but it is very small and simple).

[danielmarjamaki]

lib/StaticAnalyzer/Core/ExprEngine.cpp

107

I rewrote the code to reuse the ast matchers in LoopUnroll.. and that is not recursive. I rewrote the getGlobalStaticVars (this code is longer and in my opinion less readable but it's not recursive).

169

Currently static struct objects are unaffected by these changes. There is no regression.

Reviews are taking too long time. I am not against getting reviews but I am against waiting for reviews for months, ideally people would only need to wait for at most a week to get a review. This is why I don't want to handle structs now -- I am not eager to prolong the review process for this patch.

[szepet]

Hello Daniel!

It is a great feature to add, thanks for working on this!
I have just small comments (rather questions) on the code.

lib/StaticAnalyzer/Core/ExprEngine.cpp

155

I think instead of this logic it would be better to use ConstStmtVisitor. In this case it does quite the same thing in a (maybe?) more structured manner. What do you think?

168

Is it possible that a type is an IntegerType and a PointerType at the same time? If these are excluding cases then the check for !isPointer could be removed.

[dcoughlin]

Apologies for the delay reviewing! As I noted inline, I'm pretty worried about the performance impact of this. Is it possible to do the analysis in a single traversal of the translation unit?

lib/StaticAnalyzer/Core/ExprEngine.cpp

123

Since you are calling getInitialStateForGlobalStaticVar() in getInitialState() for each static variable declaration and getInitialState() is called for each top-level function, you are doing an n^3 operation in the size of the translation unit, which is going to be very, very expensive for large translation units.

Have you considered doing the analysis for static variables that are never changed during call-graph construction? This should be a linear operation and doing it during call-graph construction would avoid an extra walk of the entire translation unit.

[danielmarjamaki]

In D37897#892667, @dcoughlin wrote:

Apologies for the delay reviewing! As I noted inline, I'm pretty worried about the performance impact of this. Is it possible to do the analysis in a single traversal of the translation unit?

I agree. I first tried more like that but ran into problems. Don't remember the details. I will try again.. however as far as I see this will mean the LoopUnroller AST matchers can't be reused unless I change them.

[danielmarjamaki]

lib/StaticAnalyzer/Core/ExprEngine.cpp

123

hmm... could you tell me where the call-graph construction is that I can tweak?

[danielmarjamaki]

lib/StaticAnalyzer/Core/ExprEngine.cpp

123

I think I found it: clang/lib/Analysis/CallGraph.cpp

[danielmarjamaki]

Track modification of global static variables in CallGraph construction

[danielmarjamaki]

lib/StaticAnalyzer/Core/ExprEngine.cpp

123

I now track variable modifications in call-graph construction instead.

155

As far as I see ConstStmtVisitor is also recursive. Imho let's have readable code instead..

[NoQ]

however as far as I see this will mean the LoopUnroller AST matchers can't be reused unless I change them.

Hmm. What is the problem here? I'm expecting library linkage issues (i.e. libAnalysis is not linked to libASTMatchers directly), but i guess it'd better to have the whole thing in libAnalysis then (Peter, WDYT?). Or maybe we could move the code around a bit, so that we're still in libStaticAnalyzerCore but at roughly the same moment of time.

Because you're duplicating the solution for exact same problem, using different technology, and this problem is not trivial (eg. you still need to consider reference-type declstmts and initializer lists which are not taken into account in your solution yet) so i'd dislike the idea of duplicating it.

lib/Analysis/CallGraph.cpp

104

A hint, even if we don't use visitors: the whole point of having a visitor is about not needing to make a pattern-matching (switch or sequence of dyn_casts) by statement kind yourself, like you do in this function. You already have VisitUnaryOperator, VisitBinaryOperator, VisitCallExpr, etc., so you can add the code there.

[danielmarjamaki]

I will not continue working on this. Feel free to take over the patch or write a new patch.

include/clang/AST/Decl.h

public:
 
   /// \brief Kinds of thread-local storage.
   enum TLSKind {
     TLS_None,   ///< Not a TLS variable.
     TLS_Static, ///< TLS with a known-constant initializer.
     TLS_Dynamic ///< TLS with a dynamic initializer.
   };
 
+  void setModified();
+  bool isModified() const;
+
 protected:
   // A pointer union of Stmt * and EvaluatedStmt *. When an EvaluatedStmt, we
   // have allocated the auxiliary struct of information there.
   //
   // TODO: It is a bit unfortunate to use a PointerUnion inside the VarDecl for
   // this as *many* VarDecls are ParmVarDecls that don't have default
   // arguments. We could save some space by moving this pointer union to be
   // allocated in trailing space when necessary.
   typedef llvm::PointerUnion<Stmt *, EvaluatedStmt *> InitType;
 
   /// \brief The initializer for this variable or, for a ParmVarDecl, the
   /// C++ default argument.
   mutable InitType Init;
 
 private:
   class VarDeclBitfields {
     friend class VarDecl;
     friend class ASTDeclReader;
 
     unsigned SClass : 3;
     unsigned TSCSpec : 2;
     unsigned InitStyle : 2;
+    unsigned Modified : 1;
   };
-  enum { NumVarDeclBits = 7 };
+  enum { NumVarDeclBits = 8 };
 
   friend class ASTDeclReader;
   friend class StmtIteratorBase;
   friend class ASTNodeImporter;
 
 protected:
   enum { NumParameterIndexBits = 8 };
 

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

public:
   /// Evaluate a call, running pre- and post-call checks and allowing checkers
   /// to be responsible for handling the evaluation of the call itself.
   void evalCall(ExplodedNodeSet &Dst, ExplodedNode *Pred,
                 const CallEvent &Call);
 
   /// \brief Default implementation of call evaluation.
   void defaultEvalCall(NodeBuilder &B, ExplodedNode *Pred,
                        const CallEvent &Call);
+
 private:
+  ProgramStateRef getInitialStateForGlobalStaticVar(const LocationContext *LCtx,
+                                                    const ProgramStateRef State,
+                                                    const VarDecl *VD);
+
   void evalLoadCommon(ExplodedNodeSet &Dst,
-                      const Expr *NodeEx,  /* Eventually will be a CFGStmt */
-                      const Expr *BoundEx,
-                      ExplodedNode *Pred,
-                      ProgramStateRef St,
-                      SVal location,
-                      const ProgramPointTag *tag,
-                      QualType LoadTy);
+                      const Expr *NodeEx, /* Eventually will be a CFGStmt */
+                      const Expr *BoundEx, ExplodedNode *Pred,
+                      ProgramStateRef St, SVal location,
+                      const ProgramPointTag *tag, QualType LoadTy);
 
   // FIXME: 'tag' should be removed, and a LocationContext should be used
   // instead.
   void evalLocation(ExplodedNodeSet &Dst,
                     const Stmt *NodeEx, /* This will eventually be a CFGStmt */
                     const Stmt *BoundEx,
                     ExplodedNode *Pred,
                     ProgramStateRef St, SVal location,

lib/AST/Decl.cpp

static_assert(sizeof(ParmVarDeclBitfields) <= sizeof(unsigned),
                 "ParmVarDeclBitfields too large!");
   static_assert(sizeof(NonParmVarDeclBitfields) <= sizeof(unsigned),
                 "NonParmVarDeclBitfields too large!");
   AllBits = 0;
   VarDeclBits.SClass = SC;
   // Everything else is implicitly initialized to false.
 }
 
-VarDecl *VarDecl::Create(ASTContext &C, DeclContext *DC,
-                         SourceLocation StartL, SourceLocation IdL,
-                         IdentifierInfo *Id, QualType T, TypeSourceInfo *TInfo,
-                         StorageClass S) {
+void VarDecl::setModified() { VarDeclBits.Modified = true; }
+bool VarDecl::isModified() const { return VarDeclBits.Modified; }
+
+VarDecl *VarDecl::Create(ASTContext &C, DeclContext *DC, SourceLocation StartL,
+                         SourceLocation IdL, IdentifierInfo *Id, QualType T,
+                         TypeSourceInfo *TInfo, StorageClass S) {
   return new (C, DC) VarDecl(Var, C, DC, StartL, IdL, Id, T, TInfo, S);
 }
 
 VarDecl *VarDecl::CreateDeserialized(ASTContext &C, unsigned ID) {
   return new (C, ID)
       VarDecl(Var, C, nullptr, SourceLocation(), SourceLocation(), nullptr,
               QualType(), nullptr, SC_None);
 }

lib/Analysis/CallGraph.cpp

 namespace {
 /// A helper class, which walks the AST and locates all the call sites in the
 /// given function body.
 class CGBuilder : public StmtVisitor<CGBuilder> {
   CallGraph *G;
   CallGraphNode *CallerNode;
 
 public:
-  CGBuilder(CallGraph *g, CallGraphNode *N)
-    : G(g), CallerNode(N) {}
+  CGBuilder(CallGraph *g, CallGraphNode *N) : G(g), CallerNode(N) {}
 
-  void VisitStmt(Stmt *S) { VisitChildren(S); }
+  void VisitStmt(Stmt *S) {
+    markModifiedVars(S);
+    VisitChildren(S);
+  }
 
   Decl *getDeclFromCall(CallExpr *CE) {
     if (FunctionDecl *CalleeDecl = CE->getDirectCallee())
       return CalleeDecl;
 
     // Simple detection of a call through a block.
     Expr *CEE = CE->getCallee()->IgnoreParenImpCasts();
     if (BlockExpr *Block = dyn_cast<BlockExpr>(CEE)) {
if (G->includeInGraph(D)) {
       CallerNode->addCallee(CalleeNode);
     }
   }
 
   void VisitCallExpr(CallExpr *CE) {
     if (Decl *D = getDeclFromCall(CE))
       addCalledDecl(D);
     VisitChildren(CE);
+    markModifiedVars(CE);
   }
 
   // Adds may-call edges for the ObjC message sends.
   void VisitObjCMessageExpr(ObjCMessageExpr *ME) {
     if (ObjCInterfaceDecl *IDecl = ME->getReceiverInterface()) {
       Selector Sel = ME->getSelector();
-      
       // Find the callee definition within the same translation unit.
       Decl *D = nullptr;
       if (ME->isInstanceMessage())
         D = IDecl->lookupPrivateMethod(Sel);
       else
         D = IDecl->lookupPrivateClassMethod(Sel);
       if (D) {
         addCalledDecl(D);
         NumObjCCallEdges++;
       }
     }
   }
 
   void VisitChildren(Stmt *S) {
     for (Stmt *SubStmt : S->children())
       if (SubStmt)
         this->Visit(SubStmt);
   }
+
+  void modifyVar(Expr *E) {
+    auto *D = dyn_cast<DeclRefExpr>(E->IgnoreParenCasts());
+    if (!D)
+      return;
+    VarDecl *VD = dyn_cast<VarDecl>(D->getDecl());
+    if (VD)
+      VD->setModified();
+  }
+
+  void markModifiedVars(Stmt *S) {
+    // Increment/Decrement, taking address of variable
+    if (UnaryOperator *U = dyn_cast<UnaryOperator>(S)) {
+      const UnaryOperatorKind K = U->getOpcode();
+      if (K == UO_AddrOf || K == UO_PostDec || K == UO_PostInc ||
+          K == UO_PreDec || K == UO_PreInc)
+        modifyVar(U->getSubExpr());
+      return;
+    }
+
+    // Assignments
+    if (BinaryOperator *B = dyn_cast<BinaryOperator>(S)) {
+      if (!B->isAssignmentOp())
+        return;
+      modifyVar(B->getLHS());
+      if (B->getLHS()->getType()->isReferenceType())
+        modifyVar(B->getRHS());
+      return;
+    }
+
+    // Handle reference arguments
+    if (auto *CE = dyn_cast<CallExpr>(S)) {
+      const Decl *D = CE->getCalleeDecl();
+      if (!D)
+        return;
+      const FunctionDecl *FD = dyn_cast<FunctionDecl>(D);
+      if (!FD)
+        return;
+      unsigned N = 0;
+      for (const auto Arg : FD->parameters()) {
+        if (Arg->getType()->isReferenceType() &&
+            !Arg->getType().isConstQualified() && N < CE->getNumArgs())
+          modifyVar(CE->getArg(N));
+        N++;
+      }
+    }
+  }
 };
 
 } // end anonymous namespace
 
 void CallGraph::addNodesForBlocks(DeclContext *D) {
   if (BlockDecl *BD = dyn_cast<BlockDecl>(D))
     addNodeForDecl(BD, true);
 

lib/StaticAnalyzer/Core/ExprEngine.cpp

 ExprEngine::~ExprEngine() {
   BR.FlushReports();
 }
 
 //===----------------------------------------------------------------------===//
 // Utility methods.
 //===----------------------------------------------------------------------===//
 
+/** Get initial state for global static variable */
+ProgramStateRef ExprEngine::getInitialStateForGlobalStaticVar(
+    const LocationContext *LCtx, ProgramStateRef State, const VarDecl *VD) {
+  // Is variable changed anywhere in TU?
+  if (VD->isModified())
+    return State;
+
+  // What is the initialized value?
+  llvm::APSInt InitVal;
+  if (const Expr *I = VD->getInit()) {
+    if (!I->EvaluateAsInt(InitVal, getContext()))
+      return State;
+  } else {
+    InitVal = 0;
+  }
+
+  const MemRegion *R = State->getRegion(VD, LCtx);
+  if (!R)
+    return State;
+  SVal V = State->getSVal(loc::MemRegionVal(R));
+  SVal Constraint_untested =
+      evalBinOp(State, BO_EQ, V, svalBuilder.makeIntVal(InitVal),
+                svalBuilder.getConditionType());
+  Optional<DefinedOrUnknownSVal> Constraint =
+      Constraint_untested.getAs<DefinedOrUnknownSVal>();
+  if (!Constraint)
+    return State;
+  return State->assume(*Constraint, true);
+}
+
+static void getGlobalStaticVars(const Stmt *FuncBody,
+                                llvm::SmallSet<const VarDecl *, 4> *Vars) {
+  std::stack<const Stmt *> Children;
+  Children.push(FuncBody);
+  while (!Children.empty()) {
+    const Stmt *Child = Children.top();
+    Children.pop();
+    if (!Child)
+      continue;
+    for (const Stmt *C : Child->children()) {
+      Children.push(C);
+    }
+    if (const DeclRefExpr *D = dyn_cast<DeclRefExpr>(Child)) {
+      const VarDecl *VD = dyn_cast<VarDecl>(D->getDecl());
+      if (VD && VD->isDefinedOutsideFunctionOrMethod() &&
+          VD->getType()->isIntegerType() &&
+          VD->getStorageClass() == SC_Static &&
+          !VD->getType()->isPointerType()) {
+        Vars->insert(VD);
+      }
+    }
+  }
+}
+
 ProgramStateRef ExprEngine::getInitialState(const LocationContext *InitLoc) {
   ProgramStateRef state = StateMgr.getInitialState(InitLoc);
+  // Get initial states for static global variables.
+  if (const auto *FD = dyn_cast<FunctionDecl>(InitLoc->getDecl())) {
+    llvm::SmallSet<const VarDecl *, 4> Vars;
+    getGlobalStaticVars(FD->getBody(), &Vars);
+    for (const VarDecl *VD : Vars) {
+      state = getInitialStateForGlobalStaticVar(InitLoc, state, VD);
+    }
+  }
+
   const Decl *D = InitLoc->getDecl();
 
   // Preconditions.
   // FIXME: It would be nice if we had a more general mechanism to add
   // such preconditions.  Some day.
   do {
 
     if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {

test/Analysis/global-vars.c

+// RUN: %clang_analyze_cc1 -analyzer-checker=alpha,core -verify %s
+
+// Avoid false positive.
+static char *allv[] = {"rpcgen", "-s", "udp", "-s", "tcp"};
+static int allc = sizeof(allv) / sizeof(allv[0]);
+static void falsePositive1(void) {
+  int i;
+  for (i = 1; i < allc; i++) {
+    const char *p = allv[i]; // no-warning
+    i++;
+  }
+}
+
+// Detect division by zero.
+static int zero = 0;
+void truePositive1() {
+  int x = 1000 / zero; // expected-warning{{Division by zero}}
+}