[analyzer] SValHasDescendant: Determine whether the SVal has an SVal descendant

[Charusso]

Summary

This relies on the SValVisitor and behaves something similar to the
Clang Tidy's hasDescendant(). The difference is it allows equality.

[Charusso]

It suppresses stuff in curl like:

char buf[4096];
size_t linelen = strlen(line);
char *ptr = realloc(line, linelen + strlen(buf) + 1);
strcpy(&line[linelen], buf);

char buffer[256];
char *string = NULL;
size_t buflen = strlen(buffer);
char *ptr = realloc(string, stringlen + buflen + 1);
string = ptr;
strcpy(string + stringlen, buffer);

char *enc = curl_easy_escape(NULL, postdata, (int)size);
size_t outlen = nlen + strlen(enc) + 2;
char *n = malloc(outlen);
strcpy(n, enc);

[Charusso]

• Add more tests.
• Let us specify the descendant as allowing equality of symbols.

[Charusso]

• Add back a comment.

[Charusso]

Here is a possible piece of code from the Tidy world: anyOf(declRefExpr(), hasDescendant(declRefExpr()), integerLiteral(), hasDescendant(integerLiteral())), that is why I recommend to allow equality of symbols to prevent boilerplate.

[NoQ]

Usually this kind of code is hard to re-use because all use cases require different definitions of "has descendant". We already have at least 3 such definitions floating around and we can't re-use them.

Even in the world of ASTMatchers the actual hasDescendant matcher is basically an anti-pattern as you always want to use a matcher for a specific parent-child relation instead (cf. http://lists.llvm.org/pipermail/cfe-dev/2019-September/063260.html).

[Charusso]

In D70805#1776527, @NoQ wrote:

Usually this kind of code is hard to re-use because all use cases require different definitions of "has descendant". We already have at least 3 such definitions floating around and we can't re-use them.

Even in the world of ASTMatchers the actual hasDescendant matcher is basically an anti-pattern as you always want to use a matcher for a specific parent-child relation instead (cf. http://lists.llvm.org/pipermail/cfe-dev/2019-September/063260.html).

When I encounter the following:

unsigned Foo = Foo.Bar[Baz]->Qux;
malloc(strlen(src) + Foo + 1);

At the moment I cannot lookup the strlen(src) and nor the + 1. There is no way to say the strlen(src) which parent is a malloc(). I do not think we could make the full support of pattern-matching on symbolic level, so at least I wanted to see if it is possible. I am even thinking of using the ASTImporter to normalize the expression so that in a flatten/serialized form the AST-matcher could look for such constructs without any wonky DeclRefExpr or ReturnStmt matching. I believe the latter is the way we could benefit a lot, and the former, the current patch needs to be eliminated. For now I cannot relax the AST or invent a symbolic-matcher language so I would prefer this simple workaround and may we will have better ideas later.

[NoQ]

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

55

Arithmetic is indeed easy, but for example this part requires a much deeper justification.

[Charusso]

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

55

Well, this is an experiment. I have checked out the Clang Tidy's matcher-writing language's framework so I believe their own language is way more better, than implementing hasDescendant() only. Some kind of framework would be neat, but this is what I came up with as the hasDescendant() is the most powerful matcher in their world.

[Charusso]

• Rebase.

[Charusso]

Way more sophisticated matching: https://reviews.llvm.org/D77745

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

+//===- SValHasDescendant.h - Symbolic value traversing ----------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file defines SValHasDescendant which returns whether the given
+//  symbol or region has a descendant symbol.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALHASDESCENDANT_H
+#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALHASDESCENDANT_H
+
+#include "clang/AST/DeclCXX.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/SValVisitor.h"
+
+namespace clang {
+namespace ento {
+
+class SValHasDescendant : public FullSValVisitor<SValHasDescendant, bool> {
+  Optional<SVal> StoredV;
+  const MemRegion *StoredMR;
+
+public:
+  SValHasDescendant(SVal V) : StoredV(V) {}
+  SValHasDescendant(const MemRegion *MR) : StoredMR(MR) { assert(MR); }
+
+  bool VisitLocMemRegionVal(loc::MemRegionVal V) {
+    if (StoredV)
+      if (const auto MRV = StoredV->getAs<loc::MemRegionVal>())
+        if (V == MRV)
+          return true;
+
+    return Visit(V.getRegion());
+  }
+
+  bool VisitNonLocSymbolVal(nonloc::SymbolVal V) {
+    if (StoredV && *StoredV == V)
+      return true;
+
+    return Visit(V.getSymbol());
+  }
+
+  bool VisitNonLocLazyCompoundVal(nonloc::LazyCompoundVal V) {
+    if (StoredV && *StoredV == V)
+      return true;
+
+    return Visit(V.getRegion());
+  }
+
+  bool VisitSymbolRegionValue(const SymbolRegionValue *S) {
+    return Visit(S->getRegion());
+  }
+
+  bool VisitSymbolExtent(const SymbolExtent *S) {
+    return Visit(S->getRegion());
+  }
+
+  bool VisitSymbolMetadata(const SymbolMetadata *S) {
+    return Visit(S->getRegion());
+  }
+
+  bool VisitSymIntExpr(const SymIntExpr *S) { return Visit(S->getLHS()); }
+
+  // TODO: IntSymExpr doesn't appear in practice.
+  // Add the relevant code once it does.
+
+  bool VisitSymSymExpr(const SymSymExpr *S) {
+    if (Visit(S->getLHS()))
+      return true;
+
+    return Visit(S->getRHS());
+  }
+
+  // TODO: SymbolCast doesn't appear in practice.
+  // Add the relevant code once it does.
+
+  bool VisitSymbolicRegion(const SymbolicRegion *SR) {
+    if (SR == StoredMR)
+      return true;
+
+    if (StoredV)
+      if (auto MRV = StoredV->getAs<loc::MemRegionVal>())
+        if (MRV->getRegion() == SR)
+          return true;
+
+    return Visit(SR->getSymbol());
+  }
+
+  bool VisitMemRegion(const MemRegion *MR) {
+    if (StoredV)
+      if (auto MRV = StoredV->getAs<loc::MemRegionVal>())
+        if (MRV->getRegion() == MR)
+          return true;
+
+    return StoredMR && StoredMR == MR;
+  }
+
+  bool VisitSVal(SVal V) { return StoredV && *StoredV == V; }
+};
+
+} // end namespace ento
+} // end namespace clang
+
+#endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALHASDESCENDANT_H

clang/lib/StaticAnalyzer/Checkers/ExprInspectionChecker.cpp

 //==- ExprInspectionChecker.cpp - Used for regression tests ------*- C++ -*-==//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
 #include "clang/StaticAnalyzer/Checkers/SValExplainer.h"
 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
 #include "clang/StaticAnalyzer/Core/Checker.h"
 #include "clang/StaticAnalyzer/Core/IssueHash.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicSize.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/SValHasDescendant.h"
 #include "llvm/ADT/StringSwitch.h"
 #include "llvm/Support/ScopedPrinter.h"
 
 using namespace clang;
 using namespace ento;
 
 namespace {
 class ExprInspectionChecker : public Checker<eval::Call, check::DeadSymbols,
class ExprInspectionChecker : public Checker<eval::Call, check::DeadSymbols,
   void analyzerEval(const CallExpr *CE, CheckerContext &C) const;
   void analyzerCheckInlined(const CallExpr *CE, CheckerContext &C) const;
   void analyzerWarnIfReached(const CallExpr *CE, CheckerContext &C) const;
   void analyzerNumTimesReached(const CallExpr *CE, CheckerContext &C) const;
   void analyzerCrash(const CallExpr *CE, CheckerContext &C) const;
   void analyzerWarnOnDeadSymbol(const CallExpr *CE, CheckerContext &C) const;
   void analyzerDump(const CallExpr *CE, CheckerContext &C) const;
   void analyzerExplain(const CallExpr *CE, CheckerContext &C) const;
+  void analyzerHasDescendant(const CallExpr *CE, CheckerContext &C) const;
   void analyzerPrintState(const CallExpr *CE, CheckerContext &C) const;
   void analyzerGetExtent(const CallExpr *CE, CheckerContext &C) const;
   void analyzerHashDump(const CallExpr *CE, CheckerContext &C) const;
   void analyzerDenote(const CallExpr *CE, CheckerContext &C) const;
   void analyzerExpress(const CallExpr *CE, CheckerContext &C) const;
 
   typedef void (ExprInspectionChecker::*FnCheck)(const CallExpr *,
                                                  CheckerContext &C) const;
FnCheck Handler = llvm::StringSwitch<FnCheck>(C.getCalleeName(CE))
     .Case("clang_analyzer_checkInlined",
           &ExprInspectionChecker::analyzerCheckInlined)
     .Case("clang_analyzer_crash", &ExprInspectionChecker::analyzerCrash)
     .Case("clang_analyzer_warnIfReached",
           &ExprInspectionChecker::analyzerWarnIfReached)
     .Case("clang_analyzer_warnOnDeadSymbol",
           &ExprInspectionChecker::analyzerWarnOnDeadSymbol)
     .StartsWith("clang_analyzer_explain", &ExprInspectionChecker::analyzerExplain)
+    .StartsWith("clang_analyzer_hasDescendant", &ExprInspectionChecker::analyzerHasDescendant)
     .StartsWith("clang_analyzer_dump", &ExprInspectionChecker::analyzerDump)
     .Case("clang_analyzer_getExtent", &ExprInspectionChecker::analyzerGetExtent)
     .Case("clang_analyzer_printState",
           &ExprInspectionChecker::analyzerPrintState)
     .Case("clang_analyzer_numTimesReached",
           &ExprInspectionChecker::analyzerNumTimesReached)
     .Case("clang_analyzer_hashDump", &ExprInspectionChecker::analyzerHashDump)
     .Case("clang_analyzer_denote", &ExprInspectionChecker::analyzerDenote)
if (CE->getNumArgs() == 0) {
     return;
   }
 
   SVal V = C.getSVal(CE->getArg(0));
   SValExplainer Ex(C.getASTContext());
   reportBug(Ex.Visit(V), C);
 }
 
+void ExprInspectionChecker::analyzerHasDescendant(const CallExpr *CE,
+                                                  CheckerContext &C) const {
+
+  if (CE->getNumArgs() < 2) {
+    reportBug("Missing argument for descending", C);
+    return;
+  }
+
+  SVal LhsV = C.getSVal(CE->getArg(0));
+  SVal RhsV = C.getSVal(CE->getArg(1));
+  SValHasDescendant Desc(RhsV);
+
+  reportBug(Desc.Visit(LhsV) ? "TRUE" : "FALSE", C);
+}
+
 void ExprInspectionChecker::analyzerDump(const CallExpr *CE,
                                          CheckerContext &C) const {
   if (CE->getNumArgs() == 0) {
     reportBug("Missing argument for dumping", C);
     return;
   }
 
   SVal V = C.getSVal(CE->getArg(0));

clang/lib/StaticAnalyzer/Checkers/cert/StrChecker.cpp

 #include "clang/Lex/Lexer.h"
 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.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/CallEvent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicSize.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/SValHasDescendant.h"
 #include "llvm/ADT/Optional.h"
 #include <utility>
 
 using namespace clang;
 using namespace ento;
 using namespace ast_matchers;
 
 namespace {
void StrCheckerBase::checkStrcpy(const CallEvent &Call,
   const MemRegion *DestMR = getRegion(DestV);
   if (!SrcMR || !DestMR)
     return;
 
   DefinedOrUnknownSVal SrcSize = getDynamicSize(State, SrcMR, SVB);
   DefinedOrUnknownSVal DestSize = getDynamicSize(State, DestMR, SVB);
 
   // 'strlen(src) + integer' is most likely fine.
-  // FIXME: Use the 'SValVisitor' to catch every such constructs of the symbol.
   // FIXME: We cannot catch every '+ integer' part at the moment so we do not
   // check that property for now.
-  if (const SymExpr *SE = DestSize.getAsSymExpr())
-    for (const auto &Sym : SE->symbols())
-      if (const auto *SIE = dyn_cast<SymIntExpr>(Sym))
-        if (SIE->getOpcode() == BO_Add)
-          if (const auto *SM = dyn_cast<SymbolMetadata>(SIE->getLHS()))
-            if (SM->getRegion() == SrcMR)
-              return;
+  SValHasDescendant HasDescendantSrc(SrcMR);
+  if (HasDescendantSrc.Visit(DestSize))
 
   // 'StringRegion' returns the size with the null-terminator.
   if (const llvm::APSInt *SrcSizeInt = SVB.getKnownValue(State, SrcSize))
     if (const llvm::APSInt *DestSizeInt = SVB.getKnownValue(State, DestSize))
       if (SrcSizeInt->getZExtValue() <= DestSizeInt->getZExtValue())
         return;
 
   createOverflowNote(Call, CallC, C);

clang/test/Analysis/cert/str31-c-fp-suppression.cpp

 void test_everything_known() {
   char *dest = (char *)malloc(strlen("Foo") + 1);
   if (dest)
     strcpy(dest, "Foo");
 
   free(dest); // no-warning
 }
 
-// FIXME: Suppress that with 'SValVisitor' or something similar.
 void test_complex_size_false_positive(const char *src) {
   char *dest;
   size_t size;
   size = strlen(src);
 
   dest = (char *)malloc(size * 2 + 2);
 
   strcpy(dest, &src[13]);
-  free(dest);
-  // expected-warning@-1 {{'dest' is not null-terminated}}
+  free(dest); // no-warning
 }
 
 void test_complex_size_wrong_size(const char *src) {
   char *dest;
   size_t size;
   size = strlen(src);
 
 // FIXME: '+ 2' is missing so there is not enough space for the null terminator.
   dest = (char *)malloc(size * 2);
 
   strcpy(dest, &src[13]);
-  free(dest);
-  // expected-warning@-1 {{'dest' is not null-terminated}}
+  free(dest); // no-warning
 }
 
 void test_char_by_char(const char *src, size_t size) {
   const char *s;
   unsigned char c;
   char *escape = (char *)malloc(size);
   char *e = escape;
   for (s = src; (c = *s) != '\0'; ++s) {

clang/test/Analysis/sval-has-desc.c

+// RUN: %clang_analyze_cc1 \
+// RUN:  -analyzer-checker=core,unix,debug.ExprInspection \
+// RUN:  -verify %s
+
+#include "Inputs/system-header-simulator.h"
+
+void clang_analyzer_hasDescendantTrue(size_t, const char *);
+void clang_analyzer_hasDescendantFalse(const char *, size_t);
+void clang_analyzer_hasDescendantEquals(const char *, const char *);
+
+void test_desc(const char *src) {
+  size_t size = strlen(src);
+  clang_analyzer_hasDescendantTrue(size, src); // expected-warning {{TRUE}}
+}
+
+void test_non_desc(const char *src) {
+  size_t size = strlen(src);
+  clang_analyzer_hasDescendantFalse(src, size); // expected-warning {{FALSE}}
+}
+
+void test_equality_is_desc(const char *src) {
+  clang_analyzer_hasDescendantEquals(src, src); // expected-warning {{TRUE}}
+}