[analyzer] alpha.different.MissingBreak checker

[e.pavlov]

Summary

Please review new checker for Clang static analyzer, which checks for missing 'break' statement in 'switch' statement

[jordan_rose]

We already have this as a warning in Clang: -Wimplicit-fallthrough. The problem is that we have no way to silence it in any mode except C++11 (where we have a [[clang::fallthrough]] attribute), so it currently doesn't do anything in other language modes. There have been some past discussions on cfe-dev about turning it on anyway, possibly with idioms to silence the warning (like a comment containing the word "fallthrough").

[e.pavlov]

Hello Jordan, thanks for reply. I read the discussion on cfe-dev and I agree that this checker could be as special case for DeadStores checker.
My checker also checks dead stores, but this is just one condition to suppress false positives. My checker can find missing break when dead store didn't exist,
we just need to comment out lines 188-189 in the code of the checker. Of course, without dead store checking it produces a little bit more false positives, but it is not too noisy and can find more true positives.
Please note, that this checker can processing 'fallthrough' comments (it might be improved, but it works) and works with another versions of C/C++.

Anyway, I hope that this checker can be useful for further work on implicit-fallthrough warning.

lib/StaticAnalyzer/Checkers/CMakeLists.txt

   MallocChecker.cpp
   MallocOverflowSecurityChecker.cpp
   MallocSizeofChecker.cpp
+  MissingBreakChecker.cpp
   NSAutoreleasePoolChecker.cpp
   NSErrorChecker.cpp
   NoReturnFunctionChecker.cpp

lib/StaticAnalyzer/Checkers/Checkers.td

 def DeadCode : Package<"deadcode">;
 def DeadCodeAlpha : Package<"deadcode">, InPackage<Alpha>, Hidden;
 
+def Different : Package<"different">;
+def DifferentAlpha : Package<"different">, InPackage<Alpha>, Hidden;
+
 def Security : Package <"security">;
 def InsecureAPI : Package<"insecureAPI">, InPackage<Security>;
 def SecurityAlpha : Package<"security">, InPackage<Alpha>, Hidden;

 } // end "alpha.deadcode"
 
 //===----------------------------------------------------------------------===//
+// Different checkers.
+//===----------------------------------------------------------------------===//
+
+let ParentPackage = DifferentAlpha in {
+
+def MissingBreakChecker : Checker<"MissingBreak">,
+  HelpText<"Check for missing break in switch statement">,
+  DescFile<"MissingBreakChecker.cpp">;
+
+} // end "alpha.different"
+
+//===----------------------------------------------------------------------===//
 // Security checkers.
 //===----------------------------------------------------------------------===//
 

lib/StaticAnalyzer/Checkers/MissingBreakChecker.cpp

+/// MissingBreakChecker.cpp - Check break in switch statements ----s*- C++ -*-=//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// This file defines MissingBreakChecker, a checker which finds cases
+// with missing break in switch statement. This check corresponds to CWE-484
+//===----------------------------------------------------------------------===//
+
+#include "ClangSACheckers.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
+#include "clang/StaticAnalyzer/Core/Checker.h"
+#include "clang/AST/StmtVisitor.h"
+#include "clang/AST/Attr.h"
+#include "clang/Analysis/CFGStmtMap.h"
+#include "clang/Analysis/Analyses/CFGReachabilityAnalysis.h"
+#include "clang/Lex/Lexer.h"
+#include "llvm/Support/Regex.h"
+#include "clang/Analysis/Analyses/LiveVariables.h"
+
+using namespace clang;
+using namespace ento;
+using namespace llvm;
+namespace {
+
+class WalkAST : public ConstStmtVisitor<WalkAST> {
+  BugReporter &BR;
+  const CheckerBase *Checker;
+  AnalysisDeclContext* AC;
+  AnalysisManager& MGR;
+  const CFGStmtMap *Map;
+  CFGReverseBlockReachabilityAnalysis *RA;
+  LiveVariables *LV;
+public:
+  WalkAST(BugReporter &br, const CheckerBase *checker,
+        AnalysisDeclContext* ac, AnalysisManager& mgr,
+        const CFGStmtMap *map, CFGReverseBlockReachabilityAnalysis *ra,
+        LiveVariables *lv) :
+        BR(br), Checker(checker), AC(ac), MGR(mgr), Map(map), RA(ra), LV(lv) {}
+  void VisitStmt(const Stmt *S);
+  void VisitChildren(const Stmt *S);
+  void checkSwitchStmt(const SwitchStmt *S);
+  bool isEndPathStmt(const Stmt *S) const;
+  const Stmt * isFallThroughStmt(const Stmt *Body);
+  bool hasFallThroughComment(const Stmt *BeginStmt, const Stmt *EndStmt);
+  bool isNextBeginWithJumpStatement(const Stmt *S) const;
+  bool isReachable(const Stmt *CurrCase, const Stmt *NextCase) const;
+  bool isExistDeadStoreStmt(const Stmt *S, const Stmt *N) const;
+  bool isExistAssignmentInStmt(const Stmt *S, const VarDecl *VD) const;
+  void reportBug(const Stmt *LastStmt) const;
+};
+}
+
+void WalkAST::VisitChildren(const Stmt *S) {
+  const Stmt *PrevStmt = 0;
+  for (Stmt::const_child_iterator I = S->child_begin(), E = S->child_end();
+      I != E; PrevStmt = *I, ++I) {
+    // Don't emit warning if 'fall through' comment was found before switch
+    if (PrevStmt && *I && dyn_cast<SwitchStmt>(*I) &&
+        hasFallThroughComment(PrevStmt, *I))
+      continue;
+    if (const Stmt *child = *I)
+      Visit(child);
+  }
+}
+
+void WalkAST::reportBug(const Stmt *LastStmt) const {
+  PathDiagnosticLocation ELoc =
+      PathDiagnosticLocation::createEnd(LastStmt, BR.getSourceManager(), AC);
+  BR.EmitBasicReport(AC->getDecl(), Checker,
+      "Missing break in switch statement",
+      "Logic error",
+      "Missing break at the end of case",
+      ELoc, LastStmt->getSourceRange());
+}
+
+bool WalkAST::isReachable(const Stmt *CurrCase,
+                             const Stmt *NextCase) const {
+  return RA->isReachable(Map->getBlock(CurrCase), Map->getBlock(NextCase));
+}
+
+bool WalkAST::hasFallThroughComment(const Stmt *BeginStmt,
+                                        const Stmt *EndStmt) {
+  SourceRange Range(BeginStmt->getLocStart(), EndStmt->getLocStart());
+  CharSourceRange CharRange = CharSourceRange::getCharRange(Range);
+  bool IsValid = false;
+  // FIXME: Actually, we need to process only comments
+  StringRef Text = Lexer::getSourceText(CharRange, MGR.getSourceManager(),
+                                        MGR.getLangOpts(), &IsValid);
+  Regex FallThroughRegex("(fall.?|pass).?thr.?u", Regex::IgnoreCase);
+  Regex NoBreakRegex("no.?break", Regex::IgnoreCase);
+  return (FallThroughRegex.match(Text) || NoBreakRegex.match(Text));
+}
+
+inline bool WalkAST::isEndPathStmt(const Stmt *S) const {
+  return (isa<BreakStmt>(S) || isa<ReturnStmt>(S) ||
+      isa<ContinueStmt>(S) || isa<GotoStmt>(S));
+}
+
+bool WalkAST::isNextBeginWithJumpStatement(const Stmt *S) const {
+  if (const SwitchCase *SC = dyn_cast<SwitchCase>(S)) {
+    const Stmt *SubStmt = SC->getSubStmt();
+    if (isa<SwitchCase>(SubStmt))
+      return isNextBeginWithJumpStatement(SubStmt);
+    return (isa<BreakStmt>(SubStmt) || isa<ContinueStmt>(SubStmt) ||
+             isa<NullStmt>(SubStmt) || isa<ReturnStmt>(SubStmt) ||
+             isa<GotoStmt>(SubStmt));
+  }
+  return false;
+}
+
+// Method checks that body of case falls through to the next case.
+const Stmt * WalkAST::isFallThroughStmt(const Stmt *Body) {
+  if (Body == NULL)
+    return Body;
+  if (const CompoundStmt *Compound = dyn_cast<CompoundStmt>(Body)) {
+    const Stmt *Last = Compound->body_back();
+    if (Last != NULL)
+      return isFallThroughStmt(Last);
+    return Body;
+  } else if (const SwitchCase *SC = dyn_cast<SwitchCase>(Body)) {
+    return isFallThroughStmt(SC->getSubStmt());
+  } else if (isEndPathStmt(Body)) {
+    return NULL;
+  } else if (isa<Expr>(Body)) {
+    return Body;
+  } else if (const IfStmt *IS = dyn_cast<IfStmt>(Body)) {
+    const Stmt *Last = isFallThroughStmt(IS->getThen());
+    if (Last)
+      return Last;
+    return isFallThroughStmt(IS->getElse());
+  }
+  return Body;
+}
+
+void WalkAST::checkSwitchStmt(const SwitchStmt *SS) {
+  if (SS->getLocStart().isMacroID())
+    return;
+  const CompoundStmt *SwitchBody = dyn_cast<CompoundStmt>(SS->getBody());
+  if (!SwitchBody)
+    return;
+  const Stmt *PrevStmt = 0;
+  for (CompoundStmt::const_body_iterator I = SwitchBody->body_begin(),
+      E = SwitchBody->body_end(); I != E; PrevStmt = *I, I++) {
+    Stmt *CurrStmt = *I;
+    if (isa<SwitchStmt>(CurrStmt)) {
+      VisitStmt(CurrStmt);
+    }
+    if (!isa<SwitchCase>(CurrStmt))
+      continue;
+
+    const Stmt *NextStmt = NULL;
+    CompoundStmt::const_body_iterator N = I;
+    ++N;
+    if (N != E) {
+      NextStmt = *N;
+    }
+
+    if (NextStmt == NULL || !isa<SwitchCase>(NextStmt))
+      continue;
+
+    // Ignore case which doesn't fall through to the next case
+
+    const Stmt *LastStmt = isFallThroughStmt(CurrStmt);
+    if (!LastStmt)
+      continue;
+
+    // Additional check that current case reachable to the next one
+    if (!isReachable(CurrStmt, NextStmt))
+      continue;
+
+    // Don't emit warning if next case begin with 'break', 'continue', 'return'
+    // or 'goto' statement
+    if (isNextBeginWithJumpStatement(NextStmt))
+      continue;
+
+    // Don't emit warning if exist comment like 'fall through' or 'no break'
+    if (hasFallThroughComment(CurrStmt, NextStmt) ||
+        (PrevStmt && hasFallThroughComment(PrevStmt, CurrStmt)))
+      continue;
+
+    // Don't emit warning if dead store doesn't exist
+    // This additional check suppresses a lot of false positives
+    if (!isExistDeadStoreStmt(CurrStmt, NextStmt))
+      continue;
+
+    reportBug(LastStmt);
+  }
+}
+
+bool WalkAST::isExistDeadStoreStmt(const Stmt *S, const Stmt *N) const {
+  if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {
+    if (!B->isAssignmentOp())
+      return false;
+    if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(B->getLHS())) {
+      if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
+        if (!VD->hasLocalStorage())
+          return false;
+
+        if (VD->getType()->getAs<ReferenceType>())
+          return false;
+        if (!LV->isLive(Map->getBlock(S), VD) &&
+            !(VD->getAttr<UnusedAttr>() || VD->getAttr<BlocksAttr>()) &&
+            isExistAssignmentInStmt(N, VD)) {
+          return true;
+        }
+      }
+    }
+  }
+  for (Stmt::const_child_iterator I = S->child_begin(),
+      E = S->child_end(); I!=E; ++I)
+    if (const Stmt *child = *I)
+      if (isExistDeadStoreStmt(child, N))
+        return true;
+  return false;
+}
+
+bool WalkAST::isExistAssignmentInStmt(const Stmt *S,
+                                           const VarDecl *VD) const {
+  if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {
+    if (!B->isAssignmentOp())
+      return false;
+    if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(B->getLHS())) {
+      if (const VarDecl *vd = dyn_cast<VarDecl>(DR->getDecl())) {
+        if (VD->getFirstDecl() == vd->getFirstDecl())
+          return true;
+      }
+    }
+  }
+  for (Stmt::const_child_iterator I = S->child_begin(),
+      E = S->child_end(); I!=E; ++I)
+    if (const Stmt *child = *I)
+      if (isExistAssignmentInStmt(child, VD))
+        return true;
+  return false;
+}
+
+void WalkAST::VisitStmt(const Stmt *S) {
+  if (const SwitchStmt *SS = dyn_cast<SwitchStmt>(S)) {
+    checkSwitchStmt(SS);
+  }
+  VisitChildren(S);
+}
+
+namespace {
+class MissingBreakChecker : public Checker < check::ASTCodeBody > {
+public:
+  void checkASTCodeBody(const Decl *VD, AnalysisManager& mgr,
+                           BugReporter &BR) const;
+};
+}
+
+void MissingBreakChecker::checkASTCodeBody(const Decl *D,
+                                AnalysisManager& mgr, BugReporter &BR) const {
+  AnalysisDeclContext *AC = mgr.getAnalysisDeclContext(D);
+  CFGStmtMap *Map = AC->getCFGStmtMap();
+  CFGReverseBlockReachabilityAnalysis *RA = AC->getCFGReachablityAnalysis();
+  LiveVariables *LV = LiveVariables::computeLiveness(*AC, true);
+
+  WalkAST walker(BR, this, AC, mgr, Map, RA, LV);
+  walker.Visit(D->getBody());
+
+}
+
+void ento::registerMissingBreakChecker(CheckerManager &mgr) {
+  mgr.registerChecker<MissingBreakChecker>();
+}

test/Analysis/missing-break.c

+// RUN: %clang_cc1 -analyze -analyzer-checker=core,alpha.different.MissingBreak -analyzer-store=region -verify %s
+void foo();
+extern void exit (int status);
+extern void __assert_fail (__const char *__assertion, __const char *__file,
+                           unsigned int __line, __const char *__function)
+__attribute__ ((__noreturn__));
+#define assert(expr) \
+((expr)  ? (void)(0)  : __assert_fail (#expr, __FILE__, __LINE__, __func__))
+
+int f1(int val, int b) {
+  int i = 0;
+  switch(val) {
+  case 0:
+    i = 1;    // expected-warning {{Missing break at the end of case}}
+  case 1:
+    i = 2;
+    break;    // no-warning
+  case 2: case 3:
+    i = 3;    // expected-warning {{Missing break at the end of case}}
+  case 4: case 5:
+    i = 5;
+    break;    // no-warning
+  case 6: case 7:
+    i = 7;
+    return i;   // no-warning
+  case 8:
+    if (b)
+      i = 9;    // expected-warning {{Missing break at the end of case}}
+    else
+      break;    // no-warning
+  case 9: {
+      i = 9;
+  } break;      // no-warning
+  case 10:
+    if (b)
+      break;    // no-warning
+    else
+      i = 10;   // expected-warning {{Missing break at the end of case}}
+  case 11: {
+    i = 11;
+  } break;      // no-warning
+  case 12:
+    if (b == 0)
+      i = 5;    // expected-warning {{Missing break at the end of case}}
+    else if (b == 1)
+      i = 6;
+    else if (b < 0)
+      i = 0;
+    else
+      break;    // no-warning
+  case 13: {
+    i = 5;
+    b++;
+  } break;      // no-warning
+  default:
+    i = -1;     // no-warning
+    break;
+  }
+  return i;
+}
+
+void f2(int v, int b) {
+  switch (v) {
+  case 1:
+    foo();
+    break;
+  case 3:
+    exit(0);    // no-warning
+  case 4:
+    exit(0);    // no-warning
+    break;
+  case 7:
+    assert(b > 7);  // no-warning
+  case 8:
+    v++;
+    assert(b > 8);  // no-warning
+  case 9:
+    assert(b > 9);  // no-warning
+    break;
+  case 10:
+    return;        // no-warning
+  default:
+    return;
+  }
+}
+
+int f3(int v, int cond) {
+  int i = 0;
+  switch(v) {
+  case 2:
+    if (cond)
+      return 2;  // no-warning
+    else
+      i = 10;  // expected-warning {{Missing break at the end of case}}
+  case 3:
+    if (cond)
+      return 3;  // no-warning
+    else {
+      i = 10;
+      return i;  // no-warning
+    }
+  case 4:
+    if (cond > 1)
+      return 4;  // no-warning
+    else if (cond > 2) {
+      i = 4;
+      break;  // no-warning
+    } else
+      break;  // no-warning
+  case 5:
+    if (cond > 1)
+      return 4;
+    else if (cond > 2) {
+      i = 4;
+      break;
+    }  // no-warning
+  case 6:
+    if (cond)
+      i = 20;
+    goto out;  // no-warning
+  case 7:
+    if (cond)
+      return cond;  // no-warning
+    else
+      goto out;  // no-warning
+  case 8:
+    switch (cond) {
+    case 0:
+      i = 10;   // expected-warning {{Missing break at the end of case}}
+    case 1:
+      i = 11;
+      break;
+    } // expected-warning {{Missing break at the end of case}}
+  default:
+    i = 10;
+    return i;  // no-warning
+  }
+out:
+  return i;
+}
+
+int f4(int v, int flag) {
+  int i = 0;
+  switch(v) {
+  case 0:
+    i = 1;     // fall through
+  case 1:
+    i = v;    // FALL THROUGH
+  case 3:
+    i = 3;    // fall thru
+  case 4:
+    i = 4;
+    // FALLTHROUGH
+  case 5:
+    i = 5;
+    /* FALLTHROUGH */
+  case 6:
+    i = 6;
+    /* Falls Through */
+  case 7:
+    i = 7;
+    // no break
+  case 8:
+    i = 8; // no-break
+  case 9:
+    i = 9; // no break
+  case 10: {
+    // fall through
+    i = 10;
+  }
+  case 11:
+    i = 11;
+    break;
+    // fall through
+  case 12:
+    i = 12;
+  default:
+    return i;
+  }
+  // falls through
+  switch(flag) {
+  case 0:
+    i = 1;
+  case 1:
+    i = 2;
+  case 3:
+    i = -1;
+  default:
+    i = 0;
+  }
+
+  return i;
+}
+
+int f5(int v) {
+  int i = 0;
+  int j = 0;
+  switch(v) {
+  default: break;
+  case 0: i = 1; break;
+  case 1: i = 4;    // no-warning
+  case 2: break;
+  case 3: i = 4;    // no-warning
+  case 4: return i;
+  }
+
+  return i;
+}
+
+int f6(int v) {
+  int i = 0;
+  int j = 0;
+  for (j = 0; j < v; j++) {
+    switch(v) {
+      default: break;
+      case 0: i = 1; break;
+      case 1: i += 4;    // no-warning
+      case 2: break;
+      case 3: i += 4;    // no-warning
+      case 4: return i;
+    }
+  }
+  return i;
+}
+
+int f7(int v) {
+  int i = 0;
+  switch(v) {
+    case 0: i = 1; return i;  // no-warning
+  }
+  switch(v) {
+    case 0: i = 1;  // no-warning
+  }
+  switch(v) {
+    case 0: i = 2; break;  // no-warning
+  }
+  return i;
+}
+
+int f8(int v) {
+  int i = 0;
+  switch(v) {
+  default:
+    i = 3;
+  break;
+  case 2:
+    i = 2;  // no-warning
+  case 1:
+    ;  // no-warning
+  }
+  return i;
+}
+
+int f9(int v) {
+  int i;
+  for (i = 0; i < 10; i++) {
+    switch(v) {
+    case 1:
+      i = 1;
+      break;
+    case 2:
+    case 3:
+    case 4:
+    case 10 ... 15:
+    case 16 ... 20:
+      i = 10;  // no-warning
+    case 21:
+    case 30 ... 39:
+      break;
+    case 40:
+    case 41 ... 80:
+    default:
+      i = 100;
+      break;
+    }
+  }
+  return i;
+}
+
+
+int f10(int v) {
+  unsigned nsym = 10;
+  unsigned i = 0;
+
+  while (1) {
+    if (i == 5)
+      continue;
+    switch(v) {
+    case 1:
+    case 2:
+    case 3:
+    case 4:
+      i = 5;    // no-warning
+    }
+  }
+  return i;
+}
+
+int f11(int val,int b) {
+  int i = 0;
+  int j = 1;
+  switch(val) {
+  case 0:
+    i = 2;        // expected-warning {{Missing break at the end of case}}
+  case 1:
+    i = 2;  // no-warning
+    break;
+  case 2:
+    i = 2;  // no-warning
+  case 3:
+    j = 3;  // no-warning
+    break;
+  default:
+    i = -1;
+    break;
+  }
+  return i;
+}
+
+struct str {
+  char *val;
+  int size;
+};
+
+int f12(int val,int b, struct str *v) {
+  int i = 0, j = 1;
+  int f1 = 0, f2 = 0;
+  switch(val) {
+  case 0:
+    i = 2;        // expected-warning {{Missing break at the end of case}}
+  case 1:
+    i = 3;
+    break;
+  case 2: {
+    i = 4;
+    int j = 2;
+    i++;
+    break;
+  }
+  case 3:
+    v->val = "3";   // no-warning
+  case 4:
+    v->val = "4";   // no-warning
+  case 5:
+    v->size = 5;
+    break;
+  case 6:
+    i++;    // no-warning
+  case 7:
+    i++;
+    break;
+  case 8:
+    f1 = 1;     // no-warning
+  case 9:
+    f2 = 1;
+    break;
+  case 10:
+    j = i;      // no-warning
+  case 11:
+    i = 2;
+    break;
+  default:
+    i++;
+    break;
+  }
+  j += b;
+  if (f1)
+    return i;
+  return j;
+}
+
+void f13(int v) {
+   int flags;
+   switch (v) {
+   case 1:
+     flags = 2;   // no-warning
+   default:
+     return;
+   }
+}
+
+void f14(int v) {
+   int flags;
+   switch (v) {
+   case 1:
+     flags = 2;   // no-warning
+   case 2:
+     v++;   // no-warning
+     break;
+   default:
+     return;
+   }
+   flags = 1;
+}
+
+int f15(int a) {
+  switch(a) {
+    case 1:
+      a = 2;
+      if (a)
+        break;  // no-warning
+      else
+        break; // no-warning
+    case 2:
+      a = 1;
+      break;
+    case 3: case 4:
+      a = 3;
+      if (a)
+        break;  // no-warning
+      else
+        break;  // no-warning
+    case 5:
+      a = 2;
+      break;
+    default:
+      a = 0;
+  }
+  return a;
+}