Add static analyzer checker for finding infinite recursion

[NoQ]

Summary

This is the very first version of a checker that aims to find cases of infinite recursion. It relies on Add LocationContext to members of check::RegionChanges.

What it does:

• it registers on check::PreCall and check::RegionChanges events
• in checkPreCall digs through the call stack searching for invocation of currently encountered function/method with exactly the same arguments (meaning same SVals of them)
• in checkRegionChanges makes all the frames on the call stack invalid by adding them to the set of dirty frames
• if the frame encountered by the search in checkPreCall is in the set of dirty frames the search stops

Obviously this has lots of both false negatives and false positives, but I plan to improve it by decreasing the number of frame invalidations and only taking into account changes that affect whether the recursive call happens or not. The support for Obj-C method calls is also on the way.

I welcome any ideas on how to make it better!

PS. This is one of my first patches submitted here - sorry if it doesn't comply with some conventions you might have here!

[a.sidorin]

Wow, thank you for such a contribution! Did you evaluate this checker on some real code?

I have some minor inline comments below.

lib/StaticAnalyzer/Checkers/CMakeLists.txt

41

Please fix indentation here

lib/StaticAnalyzer/Checkers/RecursionChecker.cpp

12

This description is for other checker, could you update it?

21

The idea of "dirty stack frames" deserves some explanation. As I understand, it describes function calls where some values may change unexpectedly and we cannot consider this calls later. Am I understanding correctly?

49

Incorrect indentation.

68

We may just use getParent()->getCurrentStackFrame() in the loop increment to make the code cleaner. What do you think?

79

We usually prefer LLVM [dyn_]cast<> where possible.

89

Maybe we can use early return here?

test/Analysis/recursion.cpp

27

I'd like to see some more informative function names: for me, it is hard to distinguish between f1-7 here :) It is also hard to determine the function where test starts.

[k-wisniewski]

@a.sidorin
Thank you for your review! I'll upload the new patch this evening that will include fixes for the things you pointed out. Can I also add you as a reviewer? Also: Can you have a look at my other patch that I have linked in the description? Thanks in advance!

lib/StaticAnalyzer/Checkers/RecursionChecker.cpp

12

Sure, it was easier for me to use some other checker as a template and I forgot about it. Should I add you as a reviewer once I upload the updated patch?

21

Yes! Right now it considers frame as "dirty" when there was any kind of region change in this frame or in any function that was called from it. As you see below, it then stops the search down the stack once it encounter such a "dirty" frame, because it can no longer be sure that conditions upon which the recursive call depends on did not change in an unpredictable way. It's obviously too broad a definition and in the next iterations I'll try to narrow it down to variables that affect whether the recursive call happens or not. I also consider looking at the way it changes to determine if it's meaningful or not.

test/Analysis/recursion.cpp

27

The convention I know is that the bottom-most one gets considered first, but I may add some explicitly marked entry points for the sake of consistency and to make it easier to reason about.

[NoQ]

Thank you for working on this! The overall approach is good. Because alpha checkers are disabled by default, false positives can be addressed later in subsequent commits.

lib/StaticAnalyzer/Checkers/RecursionChecker.cpp

2

Accidental line break :o

21

I think this deserves commenting, at least the very mechanism of how a stack frame is considered dirty (if it is present in the set, or if a parent is present in the set, or something else, and why is the chosen method somehow correct).

145

I think one of the builtin bugtypes should be used, such as LogicError. In any case, both of these should be human-friendly (they appear eg. in scan-view).

test/Analysis/recursion.cpp

27

There's a way to hard-check this through FileCheck + -analyzer-display-progress (see inlining/analysis-order.c). Might be an overkill, but on the other hand may actually improve readability of the test quite a bit.

37

This should eventually warn. Even though the variable is accessed, it's not really changed :)

I'd suggest something like:

++SampleGlobalVariable;
if (SampleGlobalVariable < 100)
  f3();

It'd make sure that the test is "correct" (it's obvious to the reader that this is a false positive we'd never want to warn about). But you could also keep the original test with a FIXME remark ("we should eventually warn about this").

I also think that this group of tests deserves to have the following test:

bool bar(); // no definition!
void foo() {
  if (bar()) { // may change the global state
    foo(); // no-warning
  }
}

This test case should magically work because calling bar() will change the "global memory space" region (invalidate all globals).

[NoQ]

lib/StaticAnalyzer/Checkers/RecursionChecker.cpp

65

Off-by-1: C.getStackFrame() is already the caller context, which we should check.

[NoQ]

Seems to become outdated with D27092.

include/clang/StaticAnalyzer/Checkers/Checkers.td

 def TestAfterDivZeroChecker : Checker<"TestAfterDivZero">,
   HelpText<"Check for division by variable that is later compared against 0. Either the comparison is useless or there is division by zero.">,
   DescFile<"TestAfterDivZeroChecker.cpp">;
 
 def DynamicTypeChecker : Checker<"DynamicTypeChecker">,
   HelpText<"Check for cases where the dynamic and the static type of an object are unrelated.">,
   DescFile<"DynamicTypeChecker.cpp">;
 
+def RecursionChecker : Checker<"RecursionChecker">,
+  HelpText<"Check for cases of infinite recursion.">,
+  DescFile<"RecursionChecker.cpp">;
+
 } // end "alpha.core"
 
 let ParentPackage = Nullability in {
 
 def NullPassedToNonnullChecker : Checker<"NullPassedToNonnull">,
   HelpText<"Warns when a null pointer is passed to a pointer which has a _Nonnull type.">,
   DescFile<"NullabilityChecker.cpp">;
 

lib/StaticAnalyzer/Checkers/CMakeLists.txt

add_clang_library(clangStaticAnalyzerCheckers
   DirectIvarAssignment.cpp
   DivZeroChecker.cpp
   DynamicTypePropagation.cpp
   DynamicTypeChecker.cpp
   ExprInspectionChecker.cpp
   FixedAddressChecker.cpp
   GenericTaintChecker.cpp
   IdenticalExprChecker.cpp
+        RecursionChecker.cpp
   IvarInvalidationChecker.cpp
   LLVMConventionsChecker.cpp
   LocalizationChecker.cpp
   MacOSKeychainAPIChecker.cpp
   MacOSXAPIChecker.cpp
   MallocChecker.cpp
   MallocOverflowSecurityChecker.cpp
   MallocSizeofChecker.cpp

lib/StaticAnalyzer/Checkers/RecursionChecker.cpp

+// InfiniteRecursionChecker.cpp - Test if function is infinitely
+// recursive--*--//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This defines TestAfterDivZeroChecker, a builtin check that performs checks
+//  for division by zero where the division occurs before comparison with zero.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ClangSACheckers.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+
+REGISTER_SET_WITH_PROGRAMSTATE(DirtyStackFrames, const clang::StackFrameContext *)
+
+namespace {
+using namespace clang;
+using namespace ento;
+
+class RecursionChecker
+    : public Checker<check::PreCall, check::RegionChanges, check::PostCall> {
+  mutable std::unique_ptr<BugType> BT;
+
+  void emitReport(CheckerContext &C) const;
+
+  bool compareArgs(CheckerContext &C, const ProgramStateRef &State,
+                   const SVal &CurArg, const SVal &PrevArg) const;
+
+public:
+  void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
+
+  bool wantsRegionChangeUpdate(ProgramStateRef State,
+                               const LocationContext *LCtx) const;
+
+  ProgramStateRef
+  checkRegionChanges(ProgramStateRef State,
+                     const InvalidatedSymbols *Invalidated,
+                     ArrayRef<const MemRegion *> ExplicitRegions,
+                     ArrayRef<const MemRegion *> Regions, const CallEvent *Call,
+                     const LocationContext *LCtx) const;
+  void checkPostCall(const CallEvent &Call,
+                                       CheckerContext &C) const;
+};
+}
+
+
+void RecursionChecker::checkPreCall(const CallEvent &Call,
+                                    CheckerContext &C) const {
+
+  const FunctionDecl *CurFuncDecl =
+      dyn_cast_or_null<FunctionDecl>(Call.getDecl());
+  if (!CurFuncDecl)
+    return;
+  CurFuncDecl = CurFuncDecl->getCanonicalDecl();
+
+  const ProgramStateRef State = C.getState();
+
+  for (const auto *ParentLC = C.getStackFrame()->getParent();
+       ParentLC != nullptr; ParentLC = ParentLC->getParent()) {
+
+    if (ParentLC->getKind() != LocationContext::StackFrame)
+      continue;
+
+
+    const StackFrameContext *PrevStackFrameCtx =
+        ParentLC->getCurrentStackFrame();
+
+    if (State->contains<DirtyStackFrames>(PrevStackFrameCtx))
+      return;
+
+    const FunctionDecl *PrevFuncDecl =
+        (const FunctionDecl *)PrevStackFrameCtx->getDecl();
+    PrevFuncDecl = PrevFuncDecl->getCanonicalDecl();
+
+    if (PrevFuncDecl != CurFuncDecl)
+      continue;
+
+    bool SameArgs = true;
+    for (unsigned i = 0; SameArgs && i < CurFuncDecl->getNumParams(); ++i) {
+      SVal CurArg = Call.getArgSVal(i);
+      SVal PrevArg = State->getArgSVal(PrevStackFrameCtx, i);
+      SameArgs = SameArgs && compareArgs(C, State, CurArg, PrevArg);
+    }
+
+    if (SameArgs)
+      emitReport(C);
+  }
+}
+void RecursionChecker::checkPostCall(const CallEvent &Call,
+                                     CheckerContext &C) const {
+  ProgramStateRef State = C.getState();
+  State->remove<DirtyStackFrames>(C.getStackFrame());
+}
+bool RecursionChecker::compareArgs(CheckerContext &C,
+                                   const ProgramStateRef &state,
+                                   const SVal &curArg,
+                                   const SVal &prevArg) const {
+  SValBuilder &sValBuilder = C.getSValBuilder();
+  ConstraintManager &constraintManager = C.getConstraintManager();
+
+  SVal argsEqualSVal = sValBuilder.evalBinOp(state, BO_EQ, curArg, prevArg,
+                                             sValBuilder.getConditionType());
+  Optional<DefinedSVal> argsEqual = argsEqualSVal.getAs<DefinedSVal>();
+
+  if (!argsEqual)
+    return false;
+
+  ProgramStateRef stateEQ, stateNEQ;
+  std::tie(stateEQ, stateNEQ) = constraintManager.assumeDual(state, *argsEqual);
+
+  if (stateNEQ)
+    return false;
+
+  return true;
+}
+
+bool RecursionChecker::wantsRegionChangeUpdate(
+    ProgramStateRef State, const LocationContext *LCtx) const {
+  return true;
+}
+
+ProgramStateRef RecursionChecker::checkRegionChanges(
+    ProgramStateRef State, const InvalidatedSymbols *Invalidated,
+    ArrayRef<const MemRegion *> ExplicitRegions,
+    ArrayRef<const MemRegion *> Regions, const CallEvent *Call,
+    const LocationContext *LCtx) const {
+  State = State->add<DirtyStackFrames>(LCtx->getCurrentStackFrame());
+  for (const auto *ParentLC = LCtx->getCurrentStackFrame()->getParent();
+       ParentLC != nullptr; ParentLC = ParentLC->getParent()) {
+    State = State->add<DirtyStackFrames>(ParentLC->getCurrentStackFrame());
+  }
+  return State;
+}
+
+void RecursionChecker::emitReport(CheckerContext &C) const {
+  if (!BT)
+    BT.reset(
+        new BugType(this, "Infinite recursion detected", "RecursionChecker"));
+
+  ExplodedNode *node = C.generateErrorNode();
+  if (!node)
+    return;
+
+  auto report = llvm::make_unique<BugReport>(*BT, BT->getName(), node);
+  C.emitReport(std::move(report));
+}
+
+void ento::registerRecursionChecker(CheckerManager &mgr) {
+  mgr.registerChecker<RecursionChecker>();
+}

test/Analysis/misc-ps-region-store.cpp

 void test_inline() {
   A a;
   a.foo(0);
   a.bar();
 }
 
 void test_alloca_in_a_recursive_function(int p1) {
     __builtin_alloca (p1);
-    test_alloca_in_a_recursive_function(1);
+    test_alloca_in_a_recursive_function(1); // expected-warning {{Infinite recursion detected}}
     test_alloca_in_a_recursive_function(2);
 }
 
 //===---------------------------------------------------------------------===//
 // Random tests.
 //===---------------------------------------------------------------------===//
 
 // Tests assigning using a C-style initializer to a struct

test/Analysis/recursion.cpp

+// RUN: %clang_cc1 -analyze -analyzer-checker=alpha.core.RecursionChecker -verify %s
+
+namespace obvious {
+
+void f() {
+    f(); // expected-warning {{Infinite recursion detected}}
+}
+
+void h();
+
+// Mutual recursion - simplest case
+void g() {
+    h(); // expected-warning {{Infinite recursion detected}}
+}
+
+void h() {
+    g();
+}
+
+}
+
+namespace region_changes {
+
+// some global variable
+int SampleGlobalVariable = 0;
+
+void f2();
+void f3();
+void f1();
+
+void f1() {
+    f2();
+}
+
+// we spoil the frame here by touching global variable - no warnings
+void f2() {
+    SampleGlobalVariable = 1;
+    f3();
+}
+
+// no warning because frame of f1 has been spoiled in f2!
+void f3() {
+    f1();
+}
+
+void f() {
+    f1();
+}
+
+void f5();
+void f6();
+void f7();
+void f4();
+
+void f5() {
+    f6();
+}
+
+void f6() {
+    f7();
+}
+
+void f7() {
+   f5(); // expected-warning {{Infinite recursion detected}}
+}
+
+// only the first frame is spoiled, the two over it are fine
+void f4() {
+    SampleGlobalVariable = 1;
+    f5();
+}
+
+}
+
+namespace obvious_with_arguments {
+
+void f(int a) {
+  f(a); // expected-warning {{Infinite recursion detected}}
+}
+
+void h(int a, int b);
+
+void g(int a, int b) {
+  h(b, a); // expected-warning {{Infinite recursion detected}}
+}
+
+void h(int a, int b) {
+  g(b, a);
+}
+
+void f2(int a);
+
+void f1(int a, int b) {
+  f2(a); // expected-warning {{Infinite recursion detected}}
+}
+
+void f2(int a) {
+  f1(a, 3);
+}
+
+}
+
+namespace object_oriented {
+
+struct A {
+  void f() {
+    f(); // expected-warning {{Infinite recursion detected}}
+  }
+
+  // Mutual recursion - simplest case
+  void g() {
+      h();
+  }
+
+  void h() {
+      g(); // expected-warning {{Infinite recursion detected}}
+  }
+  void f(int a) {
+    f(a); // expected-warning {{Infinite recursion detected}}
+  }
+
+  void g1(int a, int b) {
+    h1(b, a);
+  }
+
+  void h1(int a, int b) {
+    g1(b, a); // expected-warning {{Infinite recursion detected}}
+  }
+
+  void f1(int a, int b) {
+    f2(a);
+  }
+
+  void f2(int a) {
+    f1(a, 3); // expected-warning {{Infinite recursion detected}}
+  }
+
+};
+
+void start1() {
+  A a;
+  a.f();
+}
+
+void start2() {
+  A a;
+  a.g();
+}
+
+void start3() {
+  A a;
+  a.g1(1, 2);
+}
+
+void start4() {
+  A a;
+  a.f1(1, 3);
+}
+
+class B {
+public:
+
+  int f(A& a) {
+    return f(a); // expected-warning {{Infinite recursion detected}}
+  }
+
+  A g(A& a, int b) {
+    return h(b, a);
+  }
+
+  A h(int a, A& b) {
+    return g(b, a); // expected-warning {{Infinite recursion detected}}
+  }
+
+  int f1(const B& b) const {
+    return b.f1(*this); // expected-warning {{Infinite recursion detected}}
+  }
+
+  void g1(const B& b) const {
+    b.h1(*this);
+  }
+
+  void h1(const B& b) const {
+    b.g1(*this); // expected-warning {{Infinite recursion detected}}
+  }
+
+};
+
+void start5() {
+  B b;
+  A a;
+  b.f(a);
+}
+
+void start6() {
+  B b;
+  A a;
+  b.g(a, 3);
+}
+
+void start7() {
+  B b1, b2;
+  b1.f1(b2);
+}
+
+void start8() {
+  B b1, b2;
+  b1.g1(b2);
+}
+}