[analyzer] Restrict CallDescription fuzzy builtin matching

[steakhal]

Summary

CallDescriptions for builtin functions relaxes the match rules
somewhat, so that the CallDescription will match for calls that have
some prefix or suffix. This was achieved by doing a StringRef::contains().
However, this is somewhat problematic for builtins that are substrings
of each other.

Consider the following:

CallDescription{ builtin, "memcpy"} will match for
__builtin_wmemcpy() calls, which is unfortunate.

This patch addresses/works around the issue by checking if the
characters around the function's name are not part of the 'name'
semantically. In other words, to accept a match for "memcpy" the call
should not have alphanumeric ([a-zA-Z]) characters around the 'match'.

So, CallDescription{ builtin, "memcpy"} will not match on:

• __builtin_wmemcpy: there is a w alphanumeric character before the match.
• __builtin_memcpyFOoBar_inline: there is a F character after the match.
• __builtin_memcpyX_inline: there is an X character after the match.

But it will still match for:

• memcpy: exact match
• __builtin_memcpy: there is an _ before the match
• __builtin_memcpy_inline: there is an _ after the match
• memcpy_inline_builtinFooBar: there is an _ after the match

[steakhal]

clang/lib/StaticAnalyzer/Core/CheckerContext.cpp

58–80

std::size_t

[NoQ]

clang/lib/StaticAnalyzer/Core/CheckerContext.cpp

107–111

Do these need fixing as well?

Though honestly I'd remove isCLibraryFunction() as an API entirely, people should just use CallDescription for everything.

[NoQ]

Looks great overall!

[steakhal]

In D118388#3280439, @NoQ wrote:

Looks great overall!

Thanks!

clang/lib/StaticAnalyzer/Core/CheckerContext.cpp

107–111

Probably yes. I dont know how i missed this. I probably tunnel visioned too much.

Btw CDs are calling back to this API. So unless we settle on the exact semantics for builtins we should keep it. Do you have anything specific in mind?

[martong]

clang/lib/StaticAnalyzer/Core/CheckerContext.cpp

107–111

Good catch! I am suggesting to move your new logic that replaces contains into a member function (or lambda?) and then use that in the remaining two cases.

[steakhal]

I decided to land it as-is.
I tried to refactor the rest of the isCLibraryFunction() to reuse the new detection logic, but I run into issues by doing that.
BTW I'm not sure if we should support anything besides the builtins defined in clang/include/clang/Basic/Builtins*.def files.
Given that the parser should recognize these and use the appropriate Builtin for the FunctionDecl, getBuiltinID() should return the given ID.
Anyway. I decided to take it slowly and fix only the issue causing the crashes.

clang/lib/StaticAnalyzer/Core/CheckerContext.cpp

bool CheckerContext::isCLibraryFunction(const FunctionDecl *FD,
   // To avoid false positives (Ex: finding user defined functions with
   // similar names), only perform fuzzy name matching when it's a builtin.
   // Using a string compare is slow, we might want to switch on BuiltinID here.
   unsigned BId = FD->getBuiltinID();
   if (BId != 0) {
     if (Name.empty())
       return true;
     StringRef BName = FD->getASTContext().BuiltinInfo.getName(BId);
-    if (BName.contains(Name))
+    size_t start = BName.find(Name);
+    if (start != StringRef::npos) {
+      // Accept exact match.
+      if (BName.size() == Name.size())
+        return true;
+
+      //    v-- match starts here
+      // ...xxxxx...
+      //   _xxxxx_
+      //   ^     ^ lookbehind and lookahead characters
+
+      const auto MatchPredecessor = [=]() -> bool {
+        return start <= 0 || !llvm::isAlpha(BName[start - 1]);
+      };
+      const auto MatchSuccessor = [=]() -> bool {
+        std::size_t LookbehindPlace = start + Name.size();
+        return LookbehindPlace >= BName.size() ||
+               !llvm::isAlpha(BName[LookbehindPlace]);
+      };
+
+      if (MatchPredecessor() && MatchSuccessor())
         return true;
     }
+  }
 
   const IdentifierInfo *II = FD->getIdentifier();
   // If this is a special C++ name without IdentifierInfo, it can't be a
   // C library function.
   if (!II)
     return false;
 
   // Look through 'extern "C"' and anything similar invented in the future.
bool CheckerContext::isCLibraryFunction(const FunctionDecl *FD,
 
   if (Name.empty())
     return true;
 
   StringRef FName = II->getName();
   if (FName.equals(Name))
     return true;
 
   if (FName.startswith("__inline") && FName.contains(Name))
     return true;
 
   if (FName.startswith("__") && FName.endswith("_chk") && FName.contains(Name))
     return true;
 
   return false;
 }
 
 StringRef CheckerContext::getMacroNameOrSpelling(SourceLocation &Loc) {
   if (Loc.isMacroID())
     return Lexer::getImmediateMacroName(Loc, getSourceManager(),
                                              getLangOpts());

clang/unittests/StaticAnalyzer/CallDescriptionTest.cpp

TEST(CallDescription, MatchBuiltins) {
   EXPECT_TRUE(tooling::runToolOnCode(
       std::unique_ptr<FrontendAction>(new CallDescriptionAction<>(
           {{{"memset", 3}, false}, {{CDF_MaybeBuiltin, "memset", 3}, true}})),
       "void foo() {"
       "  int x;"
       "  __builtin___memset_chk(&x, 0, sizeof(x),"
       "                         __builtin_object_size(&x, 0));"
       "}"));
+
+  {
+    SCOPED_TRACE("multiple similar builtins");
+    EXPECT_TRUE(tooling::runToolOnCode(
+        std::unique_ptr<FrontendAction>(new CallDescriptionAction<>(
+            {{{CDF_MaybeBuiltin, "memcpy", 3}, false},
+             {{CDF_MaybeBuiltin, "wmemcpy", 3}, true}})),
+        R"(void foo(wchar_t *x, wchar_t *y) {
+            __builtin_wmemcpy(x, y, sizeof(wchar_t));
+          })"));
+  }
+  {
+    SCOPED_TRACE("multiple similar builtins reversed order");
+    EXPECT_TRUE(tooling::runToolOnCode(
+        std::unique_ptr<FrontendAction>(new CallDescriptionAction<>(
+            {{{CDF_MaybeBuiltin, "wmemcpy", 3}, true},
+             {{CDF_MaybeBuiltin, "memcpy", 3}, false}})),
+        R"(void foo(wchar_t *x, wchar_t *y) {
+            __builtin_wmemcpy(x, y, sizeof(wchar_t));
+          })"));
+  }
+  {
+    SCOPED_TRACE("lookbehind and lookahead mismatches");
+    EXPECT_TRUE(tooling::runToolOnCode(
+        std::unique_ptr<FrontendAction>(
+            new CallDescriptionAction<>({{{CDF_MaybeBuiltin, "func"}, false}})),
+        R"(
+          void funcXXX();
+          void XXXfunc();
+          void XXXfuncXXX();
+          void test() {
+            funcXXX();
+            XXXfunc();
+            XXXfuncXXX();
+          })"));
+  }
+  {
+    SCOPED_TRACE("lookbehind and lookahead matches");
+    EXPECT_TRUE(tooling::runToolOnCode(
+        std::unique_ptr<FrontendAction>(
+            new CallDescriptionAction<>({{{CDF_MaybeBuiltin, "func"}, true}})),
+        R"(
+          void func();
+          void func_XXX();
+          void XXX_func();
+          void XXX_func_XXX();
+
+          void test() {
+            func(); // exact match
+            func_XXX();
+            XXX_func();
+            XXX_func_XXX();
+          })"));
+  }
 }
 
 } // namespace
 } // namespace ento
 } // namespace clang