[analyzer] Add checker for underflowing unsigned integers

[pfultz2]

Summary

This will check for when assigning a negative value to an unsigned integer, when it happens implicitly.

[xazax.hun]

Isn't this case already covered by conversion checker? https://github.com/llvm-mirror/clang/blob/master/lib/StaticAnalyzer/Checkers/ConversionChecker.cpp

[pfultz2]

Isn't this case already covered by conversion checker?

I was unaware of this. This looks like it only works for binary operators. So f(-1) won't get caught.

[pfultz2]

So I submitted my change to the ConversionChecker, instead.

include/clang/StaticAnalyzer/Checkers/Checkers.td

 def DynamicTypeChecker : Checker<"DynamicTypeChecker">,
   HelpText<"Check for cases where the dynamic and the static type of an object are unrelated.">,
   DescFile<"DynamicTypeChecker.cpp">;
 
 def StackAddrAsyncEscapeChecker : Checker<"StackAddressAsyncEscape">,
   HelpText<"Check that addresses to stack memory do not escape the function">,
   DescFile<"StackAddrEscapeChecker.cpp">;
 
+def UnderflowChecker : Checker<"Underflow">,
+  HelpText<"Check for assigning negative values to unsigned integers">,
+  DescFile<"UnderflowChecker.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
   TestAfterDivZeroChecker.cpp
   TraversalChecker.cpp
   TrustNonnullChecker.cpp
   UndefBranchChecker.cpp
   UndefCapturedBlockVarChecker.cpp
   UndefResultChecker.cpp
   UndefinedArraySubscriptChecker.cpp
   UndefinedAssignmentChecker.cpp
+  UnderflowChecker.cpp
   UnixAPIChecker.cpp
   UnreachableCodeChecker.cpp
   VforkChecker.cpp
   VLASizeChecker.cpp
   ValistChecker.cpp
   VirtualCallChecker.cpp
 
   DEPENDS

lib/StaticAnalyzer/Checkers/UnderflowChecker.cpp

+//== UnderflowCheck.cpp - Division by zero checker --------------*- C++ -*--==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This defines UnderflowCheck, a builtin check in ExprEngine that performs
+// checks for assigning negative values to unsigned integers
+//
+//===----------------------------------------------------------------------===//
+
+#include "ClangSACheckers.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/CheckerContext.h"
+
+using namespace clang;
+using namespace ento;
+
+namespace {
+class UnderflowCheck : public Checker<check::PreStmt<ImplicitCastExpr>> {
+  mutable std::unique_ptr<BuiltinBug> BT;
+  void reportBug(const char *Msg, ProgramStateRef StateZero,
+                 CheckerContext &C) const;
+
+public:
+  void checkPreStmt(const ImplicitCastExpr *CE, CheckerContext &C) const;
+};
+} // end anonymous namespace
+
+void UnderflowCheck::reportBug(const char *Msg, ProgramStateRef StateZero,
+                               CheckerContext &C) const {
+  if (ExplodedNode *N = C.generateErrorNode(StateZero)) {
+    if (!BT)
+      BT.reset(new BuiltinBug(this, "Underflow unsigned integer"));
+    C.emitReport(llvm::make_unique<BugReport>(*BT, BT->getDescription(), N));
+  }
+}
+
+void UnderflowCheck::checkPreStmt(const ImplicitCastExpr *CE,
+                                  CheckerContext &C) const {
+
+  if (!CE->getType()->isUnsignedIntegerType() || CE->getType()->isBooleanType())
+    return;
+
+  const Expr *E = CE->getSubExpr();
+  if (!E)
+    return;
+  QualType valTy = E->getType();
+  if (valTy->isUnsignedIntegerType())
+    return;
+  Optional<DefinedSVal> DV = C.getSVal(E).getAs<DefinedSVal>();
+
+  if (!DV)
+    return;
+
+  // Check for negative
+  ProgramStateRef state = C.getState();
+  SValBuilder &svalBuilder = C.getSValBuilder();
+  ConstraintManager &CM = C.getConstraintManager();
+
+  // First, ensure that the value is >= 0.
+  DefinedSVal zeroVal = svalBuilder.makeIntVal(0, valTy);
+  SVal greaterThanOrEqualToZeroVal = svalBuilder.evalBinOp(
+      state, BO_GE, *DV, zeroVal, svalBuilder.getConditionType());
+
+  Optional<DefinedSVal> greaterThanEqualToZero =
+      greaterThanOrEqualToZeroVal.getAs<DefinedSVal>();
+
+  if (!greaterThanEqualToZero) {
+    // The SValBuilder cannot construct a valid SVal for this condition.
+    // This means we cannot properly reason about it.
+    return;
+  }
+
+  ProgramStateRef stateLT, stateGE;
+  std::tie(stateGE, stateLT) = CM.assumeDual(state, *greaterThanEqualToZero);
+
+  // Is it possible for the value to be less than zero?
+  if (stateLT && !stateGE) {
+    reportBug("Underflow unsigned integer", stateLT, C);
+    // In either case, we are done.
+    return;
+  }
+}
+
+void ento::registerUnderflowChecker(CheckerManager &mgr) {
+  mgr.registerChecker<UnderflowCheck>();
+}

test/Analysis/underflow.cpp

+// RUN: %clang_analyze_cc1 -analyzer-checker=alpha.core.Underflow -verify %s
+
+void foo(unsigned int i);
+
+void f1() {
+  unsigned int i = -1; // expected-warning {{Underflow unsigned integer}}
+  unsigned int j = 0;
+}
+
+void f2() {
+  foo(-1); // expected-warning {{Underflow unsigned integer}}
+  foo(0);
+}
+
+void f3() {
+  long x = -1;
+  int y = 0;
+  foo(x); // expected-warning {{Underflow unsigned integer}}
+  foo(y);
+}