clang/lib/StaticAnalyzer/Checkers/BitwiseShiftChecker.cpp

   1 //== BitwiseShiftChecker.cpp ------------------------------------*- C++ -*--==//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file defines BitwiseShiftChecker, which is a path-sensitive checker
  10 // that looks for undefined behavior when the operands of the bitwise shift
  11 // operators '<<' and '>>' are invalid (negative or too large).
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "clang/AST/ASTContext.h"
  16 #include "clang/AST/CharUnits.h"
  17 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
  18 #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
  19 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
  20 #include "clang/StaticAnalyzer/Core/Checker.h"
  21 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
  22 #include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h"
  23 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
  24 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
  25 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
  26 #include "llvm/Support/FormatVariadic.h"
  27 #include <memory>
  28
  29 using namespace clang;
  30 using namespace ento;
  31 using llvm::formatv;
  32
  33 namespace {
  34 enum class OperandSide { Left, Right };
  35
  36 using BugReportPtr = std::unique_ptr<PathSensitiveBugReport>;
  37
  38 struct NoteTagTemplate {
  39   llvm::StringLiteral SignInfo;
  40   llvm::StringLiteral UpperBoundIntro;
  41 };
  42
  43 constexpr NoteTagTemplate NoteTagTemplates[] = {
  44   {"", "right operand of bit shift is less than "},
  45   {"left operand of bit shift is non-negative", " and right operand is less than "},
  46   {"right operand of bit shift is non-negative", " but less than "},
  47   {"both operands of bit shift are non-negative", " and right operand is less than "}
  48 };
  49
  50 /// An implementation detail class which is introduced to split the checker
  51 /// logic into several methods while maintaining a consistently updated state
  52 /// and access to other contextual data.
  53 class BitwiseShiftValidator {
  54   CheckerContext &Ctx;
  55   ProgramStateRef FoldedState;
  56   const BinaryOperator *const Op;
  57   const BugType &BT;
  58   const bool PedanticFlag;
  59
  60   // The following data members are only used for note tag creation:
  61   enum { NonNegLeft = 1, NonNegRight = 2 };
  62   unsigned NonNegOperands = 0;
  63
  64   std::optional<unsigned> UpperBoundBitCount = std::nullopt;
  65
  66 public:
  67   BitwiseShiftValidator(const BinaryOperator *O, CheckerContext &C,
  68                         const BugType &B, bool P)
  69       : Ctx(C), FoldedState(C.getState()), Op(O), BT(B), PedanticFlag(P) {}
  70   void run();
  71
  72 private:
  73   const Expr *operandExpr(OperandSide Side) const {
  74     return Side == OperandSide::Left ? Op->getLHS() : Op->getRHS();
  75   }
  76
  77   bool shouldPerformPedanticChecks() const {
  78     // The pedantic flag has no effect under C++20 because the affected issues
  79     // are no longer undefined under that version of the standard.
  80     return PedanticFlag && !Ctx.getASTContext().getLangOpts().CPlusPlus20;
  81   }
  82
  83   bool assumeRequirement(OperandSide Side, BinaryOperator::Opcode Cmp, unsigned Limit);
  84
  85   void recordAssumption(OperandSide Side, BinaryOperator::Opcode Cmp, unsigned Limit);
  86   const NoteTag *createNoteTag() const;
  87
  88   BugReportPtr createBugReport(StringRef ShortMsg, StringRef Msg) const;
  89
  90   BugReportPtr checkOvershift();
  91   BugReportPtr checkOperandNegative(OperandSide Side);
  92   BugReportPtr checkLeftShiftOverflow();
  93
  94   bool isLeftShift() const { return Op->getOpcode() == BO_Shl; }
  95   StringRef shiftDir() const { return isLeftShift() ? "left" : "right"; }
  96   static StringRef pluralSuffix(unsigned n) { return n <= 1 ? "" : "s"; }
  97   static StringRef verbSuffix(unsigned n) { return n <= 1 ? "s" : ""; }
  98 };
  99
 100 void BitwiseShiftValidator::run() {
 101   // Report a bug if the right operand is >= the bit width of the type of the
 102   // left operand:
 103   if (BugReportPtr BR = checkOvershift()) {
 104     Ctx.emitReport(std::move(BR));
 105     return;
 106   }
 107
 108   // Report a bug if the right operand is negative:
 109   if (BugReportPtr BR = checkOperandNegative(OperandSide::Right)) {
 110     Ctx.emitReport(std::move(BR));
 111     return;
 112   }
 113
 114   if (shouldPerformPedanticChecks()) {
 115     // Report a bug if the left operand is negative:
 116     if (BugReportPtr BR = checkOperandNegative(OperandSide::Left)) {
 117       Ctx.emitReport(std::move(BR));
 118       return;
 119     }
 120
 121     // Report a bug when left shift of a concrete signed value overflows:
 122     if (BugReportPtr BR = checkLeftShiftOverflow()) {
 123       Ctx.emitReport(std::move(BR));
 124       return;
 125     }
 126   }
 127
 128   // No bugs detected, update the state and add a single note tag which
 129   // summarizes the new assumptions.
 130   Ctx.addTransition(FoldedState, createNoteTag());
 131 }
 132
 133 /// This method checks a requirement that must be satisfied by the value on the
 134 /// given Side of a bitwise shift operator in well-defined code. If the
 135 /// requirement is incompatible with prior knowledge, this method reports
 136 /// failure by returning false.
 137 bool BitwiseShiftValidator::assumeRequirement(OperandSide Side,
 138                                               BinaryOperator::Opcode Comparison,
 139                                               unsigned Limit) {
 140   SValBuilder &SVB = Ctx.getSValBuilder();
 141
 142   const SVal OperandVal = Ctx.getSVal(operandExpr(Side));
 143   const auto LimitVal = SVB.makeIntVal(Limit, Ctx.getASTContext().IntTy);
 144   // Note that the type of `LimitVal` must be a signed, because otherwise a
 145   // negative `Val` could be converted to a large positive value.
 146
 147   auto ResultVal = SVB.evalBinOp(FoldedState, Comparison, OperandVal, LimitVal,
 148                                  SVB.getConditionType());
 149   if (auto DURes = ResultVal.getAs<DefinedOrUnknownSVal>()) {
 150     auto [StTrue, StFalse] = FoldedState->assume(DURes.value());
 151     if (!StTrue) {
 152       // We detected undefined behavior (the caller will report it).
 153       FoldedState = StFalse;
 154       return false;
 155     }
 156     // The code may be valid, so let's assume that it's valid:
 157     FoldedState = StTrue;
 158     if (StFalse) {
 159       // Record note tag data for the assumption that we made
 160       recordAssumption(Side, Comparison, Limit);
 161     }
 162   }
 163   return true;
 164 }
 165
 166 BugReportPtr BitwiseShiftValidator::checkOvershift() {
 167   const QualType LHSTy = Op->getLHS()->getType();
 168   const unsigned LHSBitWidth = Ctx.getASTContext().getIntWidth(LHSTy);
 169
 170   if (assumeRequirement(OperandSide::Right, BO_LT, LHSBitWidth))
 171     return nullptr;
 172
 173   const SVal Right = Ctx.getSVal(operandExpr(OperandSide::Right));
 174
 175   std::string RightOpStr = "";
 176   if (auto ConcreteRight = Right.getAs<nonloc::ConcreteInt>())
 177     RightOpStr = formatv(" '{0}'", ConcreteRight->getValue());
 178
 179   std::string ShortMsg = formatv(
 180       "{0} shift{1}{2} overflows the capacity of '{3}'",
 181       isLeftShift() ? "Left" : "Right", RightOpStr.empty() ? "" : " by",
 182       RightOpStr, LHSTy.getAsString());
 183   std::string Msg =
 184       formatv("The result of {0} shift is undefined because the right "
 185               "operand{1} is not smaller than {2}, the capacity of '{3}'",
 186               shiftDir(), RightOpStr, LHSBitWidth, LHSTy.getAsString());
 187   return createBugReport(ShortMsg, Msg);
 188 }
 189
 190 // Before C++20, at 5.8 [expr.shift] (N4296, 2014-11-19) the standard says
 191 // 1. "... The behaviour is undefined if the right operand is negative..."
 192 // 2. "The value of E1 << E2 ...
 193 //     if E1 has a signed type and non-negative value ...
 194 //     otherwise, the behavior is undefined."
 195 // 3. "The value of E1 >> E2 ...
 196 //     If E1 has a signed type and a negative value,
 197 //     the resulting value is implementation-defined."
 198 // However, negative left arguments work in practice and the C++20 standard
 199 // eliminates conditions 2 and 3.
 200 BugReportPtr BitwiseShiftValidator::checkOperandNegative(OperandSide Side) {
 201   // If the type is unsigned, it cannot be negative
 202   if (!operandExpr(Side)->getType()->isSignedIntegerType())
 203     return nullptr;
 204
 205   // Main check: determine whether the operand is constrained to be negative
 206   if (assumeRequirement(Side, BO_GE, 0))
 207     return nullptr;
 208
 209   std::string ShortMsg = formatv("{0} operand is negative in {1} shift",
 210                                  Side == OperandSide::Left ? "Left" : "Right",
 211                                  shiftDir())
 212                              .str();
 213   std::string Msg = formatv("The result of {0} shift is undefined "
 214                             "because the {1} operand is negative",
 215                             shiftDir(),
 216                             Side == OperandSide::Left ? "left" : "right")
 217                         .str();
 218
 219   return createBugReport(ShortMsg, Msg);
 220 }
 221
 222 BugReportPtr BitwiseShiftValidator::checkLeftShiftOverflow() {
 223   // A right shift cannot be an overflowing left shift...
 224   if (!isLeftShift())
 225     return nullptr;
 226
 227   // In C++ it's well-defined to shift to the sign bit. In C however, it's UB.
 228   // 5.8.2 [expr.shift] (N4296, 2014-11-19)
 229   const bool ShouldPreserveSignBit = !Ctx.getLangOpts().CPlusPlus;
 230
 231   const Expr *LHS = operandExpr(OperandSide::Left);
 232   const QualType LHSTy = LHS->getType();
 233   const unsigned LeftBitWidth = Ctx.getASTContext().getIntWidth(LHSTy);
 234   assert(LeftBitWidth > 0);
 235
 236   // Quote "For unsigned lhs, the value of LHS << RHS is the value of LHS *
 237   // 2^RHS, reduced modulo maximum value of the return type plus 1."
 238   if (LHSTy->isUnsignedIntegerType())
 239     return nullptr;
 240
 241   // We only support concrete integers as left operand.
 242   const auto Left = Ctx.getSVal(LHS).getAs<nonloc::ConcreteInt>();
 243   if (!Left.has_value())
 244     return nullptr;
 245
 246   // We should have already reported a bug if the left operand of the shift was
 247   // negative, so it cannot be negative here.
 248   assert(Left->getValue().isNonNegative());
 249
 250   const unsigned LeftAvailableBitWidth =
 251       LeftBitWidth - static_cast<unsigned>(ShouldPreserveSignBit);
 252   const unsigned UsedBitsInLeftOperand = Left->getValue().getActiveBits();
 253   assert(LeftBitWidth >= UsedBitsInLeftOperand);
 254   const unsigned MaximalAllowedShift =
 255       LeftAvailableBitWidth - UsedBitsInLeftOperand;
 256
 257   if (assumeRequirement(OperandSide::Right, BO_LT, MaximalAllowedShift + 1))
 258     return nullptr;
 259
 260   const std::string CapacityMsg =
 261       formatv("because '{0}' can hold only {1} bits ({2} the sign bit)",
 262                     LHSTy.getAsString(), LeftAvailableBitWidth,
 263                     ShouldPreserveSignBit ? "excluding" : "including");
 264
 265   const SVal Right = Ctx.getSVal(Op->getRHS());
 266
 267   std::string ShortMsg, Msg;
 268   if (const auto ConcreteRight = Right.getAs<nonloc::ConcreteInt>()) {
 269     // Here ConcreteRight must contain a small non-negative integer, because
 270     // otherwise one of the earlier checks should've reported a bug.
 271     const unsigned RHS = ConcreteRight->getValue().getExtValue();
 272     assert(RHS > MaximalAllowedShift);
 273     const unsigned OverflownBits = RHS - MaximalAllowedShift;
 274     ShortMsg = formatv(
 275         "The shift '{0} << {1}' overflows the capacity of '{2}'",
 276         Left->getValue(), ConcreteRight->getValue(), LHSTy.getAsString());
 277     Msg = formatv(
 278         "The shift '{0} << {1}' is undefined {2}, so {3} bit{4} overflow{5}",
 279         Left->getValue(), ConcreteRight->getValue(), CapacityMsg, OverflownBits,
 280         pluralSuffix(OverflownBits), verbSuffix(OverflownBits));
 281   } else {
 282     ShortMsg = formatv("Left shift of '{0}' overflows the capacity of '{1}'",
 283                        Left->getValue(), LHSTy.getAsString());
 284     Msg = formatv(
 285         "Left shift of '{0}' is undefined {1}, so some bits overflow",
 286         Left->getValue(), CapacityMsg);
 287   }
 288
 289   return createBugReport(ShortMsg, Msg);
 290 }
 291
 292 void BitwiseShiftValidator::recordAssumption(OperandSide Side,
 293                                              BinaryOperator::Opcode Comparison,
 294                                              unsigned Limit) {
 295   switch (Comparison)  {
 296     case BO_GE:
 297       assert(Limit == 0);
 298       NonNegOperands |= (Side == OperandSide::Left ? NonNegLeft : NonNegRight);
 299       break;
 300     case BO_LT:
 301       assert(Side == OperandSide::Right);
 302       if (!UpperBoundBitCount || Limit < UpperBoundBitCount.value())
 303         UpperBoundBitCount = Limit;
 304       break;
 305     default:
 306       llvm_unreachable("this checker does not use other comparison operators");
 307   }
 308 }
 309
 310 const NoteTag *BitwiseShiftValidator::createNoteTag() const {
 311   if (!NonNegOperands && !UpperBoundBitCount)
 312     return nullptr;
 313
 314   SmallString<128> Buf;
 315   llvm::raw_svector_ostream Out(Buf);
 316   Out << "Assuming ";
 317   NoteTagTemplate Templ = NoteTagTemplates[NonNegOperands];
 318   Out << Templ.SignInfo;
 319   if (UpperBoundBitCount)
 320     Out << Templ.UpperBoundIntro << UpperBoundBitCount.value();
 321   const std::string Msg(Out.str());
 322
 323   return Ctx.getNoteTag(Msg, /*isPrunable=*/true);
 324 }
 325
 326 std::unique_ptr<PathSensitiveBugReport>
 327 BitwiseShiftValidator::createBugReport(StringRef ShortMsg, StringRef Msg) const {
 328   ProgramStateRef State = Ctx.getState();
 329   if (ExplodedNode *ErrNode = Ctx.generateErrorNode(State)) {
 330     auto BR =
 331         std::make_unique<PathSensitiveBugReport>(BT, ShortMsg, Msg, ErrNode);
 332     bugreporter::trackExpressionValue(ErrNode, Op->getLHS(), *BR);
 333     bugreporter::trackExpressionValue(ErrNode, Op->getRHS(), *BR);
 334     return BR;
 335   }
 336   return nullptr;
 337 }
 338 } // anonymous namespace
 339
 340 class BitwiseShiftChecker : public Checker<check::PreStmt<BinaryOperator>> {
 341   mutable std::unique_ptr<BugType> BTPtr;
 342
 343 public:
 344   void checkPreStmt(const BinaryOperator *B, CheckerContext &Ctx) const {
 345     BinaryOperator::Opcode Op = B->getOpcode();
 346
 347     if (Op != BO_Shl && Op != BO_Shr)
 348       return;
 349
 350     if (!BTPtr)
 351       BTPtr = std::make_unique<BugType>(this, "Bitwise shift",
 352                                         "Suspicious operation");
 353
 354     BitwiseShiftValidator(B, Ctx, *BTPtr, Pedantic).run();
 355   }
 356
 357   bool Pedantic = false;
 358 };
 359
 360 void ento::registerBitwiseShiftChecker(CheckerManager &Mgr) {
 361   auto *Chk = Mgr.registerChecker<BitwiseShiftChecker>();
 362   const AnalyzerOptions &Opts = Mgr.getAnalyzerOptions();
 363   Chk->Pedantic = Opts.getCheckerBooleanOption(Chk, "Pedantic");
 364 }
 365
 366 bool ento::shouldRegisterBitwiseShiftChecker(const CheckerManager &mgr) {
 367   return true;
 368 }