Add RecursionChecker for finding infinite recursion

[k-wisniewski]

Summary

This patch adds RecursionChecker for finding infinite recursion. I have refactored the checker quite thoroughly since the last time I posted it - it should now support ObjC methods as well. I have fixed several issues pointed out in the previous version too. My plan for now is to have it tested on some real code bases to check how useful it is in practice and evaluate its performance. I will also implement some heurestics to eliminate excesive false positives/negatives and evaluate them.

BTW. as I'm a complete newbie in Objective-C - could you please help me with some interesting unit test cases for this checker?
Thanks in advance!

[zaks.anna]

This is waiting for a resolution on a CallEvent API patch as described in https://reviews.llvm.org/D27091.

This is blocked on https://reviews.llvm.org/D27091.

lib/StaticAnalyzer/Checkers/RecursionChecker.cpp

29

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

+// RecursionChecker.cpp - Tests for infinitely recursive functions -*- C++ -*-//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This defines a checker that aims to find cases of infinite recursion
+// by searching up the call stack. It is in alpha.core but will hopefully
+// eventually move to core package.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ClangSACheckers.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+
+// Stackframe is considered "dirty", when there was any kind of region change
+// in it or in any function that was called from it.
+// As you see below, the checker then stops the search down the stack once
+// it encounters such a "dirty" frame. The reason for such behavior is that
+// we can no longer be sure that conditions upon which the recursive call
+// depends on did not change in an unpredictable way. The class of region changes
+// that trigger this behavior will be more fine-grained in subsequent versions of
+// this patch.
+REGISTER_SET_WITH_PROGRAMSTATE(DirtyStackFrames,
+                               const clang::StackFrameContext *)
+
+namespace {
+using namespace clang;
+using namespace ento;
+
+class RecursionChecker : public Checker<check::PreCall,
+                                        check::PreObjCMessage,
+                                        check::RegionChanges,
+                                        check::PostCall> {
+  mutable std::unique_ptr<BugType> BT;
+
+  void emitReport(CheckerContext &C) const;
+
+  Optional<SVal> getThisArgument(const CallEvent &Call) const;
+
+  bool compareArgs(const SVal &curArg,
+                   const SVal &prevArg,
+                   CheckerContext &C) const;
+
+  bool checkReceiversSame(const CallEvent &Call,
+                          const StackFrameContext *SFC,
+                          CheckerContext &C) const;
+
+  bool checkThisPointersSame(const CallEvent &Call,
+                             const StackFrameContext *SFC,
+                             CheckerContext &C) const;
+
+  bool checkAllArgumentsSame(const CallEvent &Call,
+                             const StackFrameContext *SFC,
+                             CheckerContext &C) const;
+
+  void checkPreCallImpl(const CallEvent &Call, CheckerContext &C) const;
+
+public:
+  void checkPreCall(const CallEvent &Call, CheckerContext &C) const {
+    checkPreCallImpl(Call, C);
+  }
+
+  void checkPreObjCMessage(const ObjCMethodCall &Msg, CheckerContext &C) const {
+    checkPreCallImpl(Msg, C);
+  }
+
+  ProgramStateRef checkRegionChanges(ProgramStateRef State,
+                                     const InvalidatedSymbols *Invalidated,
+                                     ArrayRef<const MemRegion *> ExplicitRegions,
+                                     ArrayRef<const MemRegion *> Regions,
+                                     const LocationContext *LCtx,
+                                     const CallEvent *Call) const;
+
+  void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
+};
+}
+
+ProgramStateRef RecursionChecker::checkRegionChanges(
+    ProgramStateRef State, const InvalidatedSymbols *Invalidated,
+    ArrayRef<const MemRegion *> ExplicitRegions,
+    ArrayRef<const MemRegion *> Regions,
+    const LocationContext *LCtx,
+    const CallEvent *Call) const {
+
+  for (const auto *SFC = LCtx->getCurrentStackFrame();
+       SFC != nullptr;
+       SFC = SFC->getParent()->getCurrentStackFrame())
+    State = State->add<DirtyStackFrames>(SFC);
+
+  return State;
+}
+
+void RecursionChecker::checkPostCall(const CallEvent &Call,
+                                     CheckerContext &C) const {
+  ProgramStateRef State = C.getState();
+  State->remove<DirtyStackFrames>(C.getStackFrame());
+}
+
+void RecursionChecker::checkPreCallImpl(const CallEvent &Call,
+                                        CheckerContext &C) const {
+
+  for (const auto *SFC = C.getStackFrame();
+       SFC != nullptr;
+       SFC = SFC->getParent()->getCurrentStackFrame()) {
+    if (C.getState()->contains<DirtyStackFrames>(SFC))
+      return;
+
+    if (Call.getDecl() != SFC->getDecl())
+      continue;
+
+    if (isa<ObjCMethodCall>(Call) && !checkReceiversSame(Call, SFC, C))
+      continue;
+    else if (!checkThisPointersSame(Call, SFC, C))
+      continue;
+
+    if (checkAllArgumentsSame(Call, SFC, C))
+      emitReport(C);
+  }
+}
+
+inline bool
+RecursionChecker::checkAllArgumentsSame(const CallEvent &Call,
+                                        const StackFrameContext *SFC,
+                                        CheckerContext &C) const {
+  bool SameArgs = true;
+  for (unsigned i = 0; SameArgs && i < Call.getNumArgs(); ++i) {
+    SVal CurArg = Call.getArgSVal(i);
+    SVal PrevArg = C.getState()->getArgSVal(SFC, i);
+    SameArgs = SameArgs && compareArgs(CurArg, PrevArg, C);
+  }
+  return SameArgs;
+}
+
+inline bool
+RecursionChecker::checkThisPointersSame(const CallEvent &Call,
+                                        const StackFrameContext *SFC,
+                                        CheckerContext &C) const {
+  const Optional<SVal> CurThis = getThisArgument(Call);
+  const Optional<SVal> PrevThis = C.getState()->getThisSVal(SFC);
+
+  return !CurThis || compareArgs(*CurThis, *PrevThis, C);
+}
+
+inline bool
+RecursionChecker::checkReceiversSame(const CallEvent &Call,
+                                     const StackFrameContext *SFC,
+                                     CheckerContext &C) const {
+  const ObjCMethodCall *Msg_ = dyn_cast<const ObjCMethodCall>(&Call);
+
+  const SVal CurReceiver = Msg_->getReceiverSVal();
+  const Optional<SVal> PrevReceiver =
+      C.getState()->getObjCMessageReceiverSVal(SFC);
+
+  return PrevReceiver && *PrevReceiver == CurReceiver;
+}
+
+inline void
+RecursionChecker::emitReport(CheckerContext &C) const {
+  if (!BT)
+    BT.reset(new BugType(this,
+                         "Infinite recursion detected",
+                         categories::LogicError));
+
+  ExplodedNode *node = C.generateErrorNode();
+  if (!node)
+    return;
+
+  auto report = llvm::make_unique<BugReport>(*BT, BT->getName(), node);
+  C.emitReport(std::move(report));
+}
+
+inline Optional<SVal>
+RecursionChecker::getThisArgument(const CallEvent &Call) const {
+  const FunctionDecl *F = dyn_cast<FunctionDecl>(Call.getDecl());
+  if (!F)
+    return None;
+  F = F->getCanonicalDecl();
+
+  Optional<SVal> CurThis;
+  if (isa<CXXMethodDecl>(F))
+    CurThis = cast<CXXInstanceCall>(&Call)->getCXXThisVal();
+  else if (isa<CXXConstructorDecl>(F))
+    CurThis = cast<CXXConstructorCall>(&Call)->getCXXThisVal();
+  else if (isa<CXXDestructorDecl>(F))
+    CurThis = cast<CXXDestructorCall>(&Call)->getCXXThisVal();
+
+  return CurThis;
+}
+
+inline bool
+RecursionChecker::compareArgs(const SVal &curArg,
+                              const SVal &prevArg,
+                              CheckerContext &C) const {
+  const ProgramStateRef state = C.getState();
+  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);
+
+  return !stateNEQ;
+}
+
+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 simplestRecursiveFunction() {
+    simplestRecursiveFunction(); // expected-warning {{Infinite recursion detected}}
+}
+
+
+void simplestMutuallyRecursiveFunction2();
+
+void simplestMutuallyRecursiveFunction1() {
+    simplestMutuallyRecursiveFunction2();
+}
+
+void simplestMutuallyRecursiveFunction2() {
+    simplestMutuallyRecursiveFunction1(); // expected-warning {{Infinite recursion detected}}
+}
+
+void startMutualRecursionTest() {
+    simplestMutuallyRecursiveFunction1();
+}
+
+}
+
+namespace region_changes {
+
+// some global variable
+int SampleGlobalVariable = 0;
+
+void firstInNoWarnCycle();
+void secondInNoWarnCycle();
+void thirdInNoWarnCycle();
+
+void firstInNoWarnCycle() {
+    secondInNoWarnCycle();
+}
+
+// we spoil the frame here by touching global variable - no warnings
+void secondInNoWarnCycle() {
+    if (++SampleGlobalVariable)
+        thirdInNoWarnCycle();
+}
+
+// no warning because frame of f1 has been spoiled in f2!
+void thirdInNoWarnCycle() {
+    firstInNoWarnCycle();
+}
+
+void startNoWarnCycle() {
+    firstInNoWarnCycle();
+}
+
+
+void firstInWarnCycle();
+void secondInWarnCycle();
+void thirdInWarnCycle();
+void fourthInWarnCycle();
+
+void secondInWarnCycle() {
+    thirdInWarnCycle();
+}
+
+void thirdInWarnCycle() {
+    fourthInWarnCycle();
+}
+
+void fourthInWarnCycle() {
+   secondInWarnCycle(); // expected-warning {{Infinite recursion detected}}
+}
+
+// only the first frame is spoiled, the two over it are fine
+void firstInWarnCycle() {
+    SampleGlobalVariable = 1;
+    if (SampleGlobalVariable++ < 5)
+        secondInWarnCycle();
+}
+
+}
+
+namespace obvious_with_arguments {
+
+void oneClassArgFunction(int a) {
+  oneClassArgFunction(a); // expected-warning {{Infinite recursion detected}}
+}
+
+void twoArgsSecondMutuallyRecursiveFunction(int a, int b);
+
+void twoArgsMutuallyRecursiveFunction(int a, int b) {
+  twoArgsSecondMutuallyRecursiveFunction(b, a);
+}
+
+void twoArgsSecondMutuallyRecursiveFunction(int a, int b) {
+  twoArgsMutuallyRecursiveFunction(b, a); // expected-warning {{Infinite recursion detected}}
+}
+
+void startMutuallyRecursiveCycle() {
+    twoArgsMutuallyRecursiveFunction(1, 2);
+}
+
+
+// Making sure the number of parameters doesn't cause problems for the checker
+void oneArgFunction(int a);
+
+void twoArgsFunction(int a, int b) {
+  oneArgFunction(a);
+}
+
+void oneArgFunction(int a) {
+  twoArgsFunction(a, 3); // expected-warning {{Infinite recursion detected}}
+}
+
+void startVariableClassArgNumberCycle() {
+    oneArgFunction(1);
+}
+
+
+bool onlyForwardDecl();
+
+// we don't know anything about onlyForwardDecl so the RegionChanges callbacks
+// ensure we don't rely on it to decide if the recursive call will happen
+void recursiveFunctionUsingForwardDecl() {
+  if (!onlyForwardDecl())
+    recursiveFunctionUsingForwardDecl();
+}
+
+}
+
+namespace object_oriented {
+
+struct ClassA {
+  void selfRecursiveMethod() {
+    selfRecursiveMethod(); // expected-warning {{Infinite recursion detected}}
+  }
+
+  // Mutual recursion - simplest case
+  void mutuallyRecursiveMethod() {
+      anotherMutuallyRecursiveMethod();
+  }
+
+  void anotherMutuallyRecursiveMethod() {
+      mutuallyRecursiveMethod(); // expected-warning {{Infinite recursion detected}}
+  }
+  void methodWithArg(int a) {
+    methodWithArg(a); // expected-warning {{Infinite recursion detected}}
+  }
+
+  void twoArgsMutuallyRecursive(int a, int b) {
+    anotherTwoArgsMutuallyRecursive(b, a);
+  }
+
+  void anotherTwoArgsMutuallyRecursive(int a, int b) {
+    twoArgsMutuallyRecursive(b, a); // expected-warning {{Infinite recursion detected}}
+  }
+
+  // different number arguments in mutually recursive methods
+  void twoArgsCallingOneArgsMethod(int a, int b) {
+    oneArgMethodCallingTwoArgsMethod(a);
+  }
+
+  void oneArgMethodCallingTwoArgsMethod(int a) {
+    twoArgsCallingOneArgsMethod(a, 3); // expected-warning {{Infinite recursion detected}}
+  }
+
+};
+
+void startSelfRecursiveMethod() {
+  ClassA a;
+  a.selfRecursiveMethod();
+}
+
+void startMutuallyRecursiveMethodCycle() {
+  ClassA a;
+  a.mutuallyRecursiveMethod();
+}
+
+void startMethodWithArg() {
+  ClassA a;
+  a.methodWithArg(1);
+}
+
+void startTwoArgsMutuallyRecursiveCycle() {
+  ClassA a;
+  a.twoArgsMutuallyRecursive(1, 2);
+}
+
+void start() {
+  ClassA a;
+  a.twoArgsCallingOneArgsMethod(1, 3);
+}
+
+class ClassB {
+public:
+
+  int methodTakingObjectParam(ClassA& a) {
+    return methodTakingObjectParam(a); // expected-warning {{Infinite recursion detected}}
+  }
+
+
+  ClassA multiArgObjectTakingMutuallyRecursive(ClassA& a, int b) {
+    return anotherMultiArgObjectTakingMutuallyRecursive(b, a);
+  }
+
+  ClassA anotherMultiArgObjectTakingMutuallyRecursive(int a, ClassA& b) {
+    return multiArgObjectTakingMutuallyRecursive(b, a); // expected-warning {{Infinite recursion detected}}
+  }
+
+
+  int recursiveWithDifferentThisPointer(const ClassB& b) const {
+    return b.recursiveWithDifferentThisPointer(*this); // expected-warning {{Infinite recursion detected}}
+  }
+
+
+  void mutuallyRecursiveWithDifferentThisPointer(const ClassB& b) const {
+    b.anotherMutuallyRecursiveWithDifferentThisPointer(*this);
+  }
+
+  void anotherMutuallyRecursiveWithDifferentThisPointer(const ClassB& b) const {
+    b.mutuallyRecursiveWithDifferentThisPointer(*this); // expected-warning {{Infinite recursion detected}}
+  }
+
+};
+
+void startMethodTakingObjectParam() {
+  ClassB b;
+  ClassA a;
+  b.methodTakingObjectParam(a);
+}
+
+void startMultiArgObjectTakingMutuallyRecursive() {
+  ClassB b;
+  ClassA a;
+  b.multiArgObjectTakingMutuallyRecursive(a, 3);
+}
+
+void startRecursiveWithDifferentThisPointer() {
+  ClassB b1, b2;
+  b1.recursiveWithDifferentThisPointer(b2);
+}
+
+void startMutuallyRecursiveWithDifferentThisPointer() {
+  ClassB b1, b2;
+  b1.mutuallyRecursiveWithDifferentThisPointer(b2);
+}
+
+}