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 = "", LowerBoundStr = ""; 176 if (auto ConcreteRight = Right.getAs<nonloc::ConcreteInt>()) 177 RightOpStr = formatv(" '{0}'", ConcreteRight->getValue()); 178 else { 179 SValBuilder &SVB = Ctx.getSValBuilder(); 180 if (const llvm::APSInt *MinRight = SVB.getMinValue(FoldedState, Right); 181 MinRight && *MinRight >= LHSBitWidth) { 182 LowerBoundStr = formatv(" >= {0},", MinRight->getExtValue()); 183 } 184 } 185 186 std::string ShortMsg = formatv( 187 "{0} shift{1}{2} overflows the capacity of '{3}'", 188 isLeftShift() ? "Left" : "Right", RightOpStr.empty() ? "" : " by", 189 RightOpStr, LHSTy.getAsString()); 190 std::string Msg = formatv( 191 "The result of {0} shift is undefined because the right " 192 "operand{1} is{2} not smaller than {3}, the capacity of '{4}'", 193 shiftDir(), RightOpStr, LowerBoundStr, LHSBitWidth, LHSTy.getAsString()); 194 return createBugReport(ShortMsg, Msg); 195 } 196 197 // Before C++20, at 5.8 [expr.shift] (N4296, 2014-11-19) the standard says 198 // 1. "... The behaviour is undefined if the right operand is negative..." 199 // 2. "The value of E1 << E2 ... 200 // if E1 has a signed type and non-negative value ... 201 // otherwise, the behavior is undefined." 202 // 3. "The value of E1 >> E2 ... 203 // If E1 has a signed type and a negative value, 204 // the resulting value is implementation-defined." 205 // However, negative left arguments work in practice and the C++20 standard 206 // eliminates conditions 2 and 3. 207 BugReportPtr BitwiseShiftValidator::checkOperandNegative(OperandSide Side) { 208 // If the type is unsigned, it cannot be negative 209 if (!operandExpr(Side)->getType()->isSignedIntegerType()) 210 return nullptr; 211 212 // Main check: determine whether the operand is constrained to be negative 213 if (assumeRequirement(Side, BO_GE, 0)) 214 return nullptr; 215 216 std::string ShortMsg = formatv("{0} operand is negative in {1} shift", 217 Side == OperandSide::Left ? "Left" : "Right", 218 shiftDir()) 219 .str(); 220 std::string Msg = formatv("The result of {0} shift is undefined " 221 "because the {1} operand is negative", 222 shiftDir(), 223 Side == OperandSide::Left ? "left" : "right") 224 .str(); 225 226 return createBugReport(ShortMsg, Msg); 227 } 228 229 BugReportPtr BitwiseShiftValidator::checkLeftShiftOverflow() { 230 // A right shift cannot be an overflowing left shift... 231 if (!isLeftShift()) 232 return nullptr; 233 234 // In C++ it's well-defined to shift to the sign bit. In C however, it's UB. 235 // 5.8.2 [expr.shift] (N4296, 2014-11-19) 236 const bool ShouldPreserveSignBit = !Ctx.getLangOpts().CPlusPlus; 237 238 const Expr *LHS = operandExpr(OperandSide::Left); 239 const QualType LHSTy = LHS->getType(); 240 const unsigned LeftBitWidth = Ctx.getASTContext().getIntWidth(LHSTy); 241 assert(LeftBitWidth > 0); 242 243 // Quote "For unsigned lhs, the value of LHS << RHS is the value of LHS * 244 // 2^RHS, reduced modulo maximum value of the return type plus 1." 245 if (LHSTy->isUnsignedIntegerType()) 246 return nullptr; 247 248 // We only support concrete integers as left operand. 249 const auto Left = Ctx.getSVal(LHS).getAs<nonloc::ConcreteInt>(); 250 if (!Left.has_value()) 251 return nullptr; 252 253 // We should have already reported a bug if the left operand of the shift was 254 // negative, so it cannot be negative here. 255 assert(Left->getValue()->isNonNegative()); 256 257 const unsigned LeftAvailableBitWidth = 258 LeftBitWidth - static_cast<unsigned>(ShouldPreserveSignBit); 259 const unsigned UsedBitsInLeftOperand = Left->getValue()->getActiveBits(); 260 assert(LeftBitWidth >= UsedBitsInLeftOperand); 261 const unsigned MaximalAllowedShift = 262 LeftAvailableBitWidth - UsedBitsInLeftOperand; 263 264 if (assumeRequirement(OperandSide::Right, BO_LT, MaximalAllowedShift + 1)) 265 return nullptr; 266 267 const std::string CapacityMsg = 268 formatv("because '{0}' can hold only {1} bits ({2} the sign bit)", 269 LHSTy.getAsString(), LeftAvailableBitWidth, 270 ShouldPreserveSignBit ? "excluding" : "including"); 271 272 const SVal Right = Ctx.getSVal(Op->getRHS()); 273 274 std::string ShortMsg, Msg; 275 if (const auto ConcreteRight = Right.getAs<nonloc::ConcreteInt>()) { 276 // Here ConcreteRight must contain a small non-negative integer, because 277 // otherwise one of the earlier checks should've reported a bug. 278 const int64_t RHS = ConcreteRight->getValue()->getExtValue(); 279 assert(RHS > MaximalAllowedShift); 280 const int64_t OverflownBits = RHS - MaximalAllowedShift; 281 ShortMsg = formatv( 282 "The shift '{0} << {1}' overflows the capacity of '{2}'", 283 Left->getValue(), ConcreteRight->getValue(), LHSTy.getAsString()); 284 Msg = formatv( 285 "The shift '{0} << {1}' is undefined {2}, so {3} bit{4} overflow{5}", 286 Left->getValue(), ConcreteRight->getValue(), CapacityMsg, OverflownBits, 287 pluralSuffix(OverflownBits), verbSuffix(OverflownBits)); 288 } else { 289 ShortMsg = formatv("Left shift of '{0}' overflows the capacity of '{1}'", 290 Left->getValue(), LHSTy.getAsString()); 291 Msg = formatv( 292 "Left shift of '{0}' is undefined {1}, so some bits overflow", 293 Left->getValue(), CapacityMsg); 294 } 295 296 return createBugReport(ShortMsg, Msg); 297 } 298 299 void BitwiseShiftValidator::recordAssumption(OperandSide Side, 300 BinaryOperator::Opcode Comparison, 301 unsigned Limit) { 302 switch (Comparison) { 303 case BO_GE: 304 assert(Limit == 0); 305 NonNegOperands |= (Side == OperandSide::Left ? NonNegLeft : NonNegRight); 306 break; 307 case BO_LT: 308 assert(Side == OperandSide::Right); 309 if (!UpperBoundBitCount || Limit < UpperBoundBitCount.value()) 310 UpperBoundBitCount = Limit; 311 break; 312 default: 313 llvm_unreachable("this checker does not use other comparison operators"); 314 } 315 } 316 317 const NoteTag *BitwiseShiftValidator::createNoteTag() const { 318 if (!NonNegOperands && !UpperBoundBitCount) 319 return nullptr; 320 321 SmallString<128> Buf; 322 llvm::raw_svector_ostream Out(Buf); 323 Out << "Assuming "; 324 NoteTagTemplate Templ = NoteTagTemplates[NonNegOperands]; 325 Out << Templ.SignInfo; 326 if (UpperBoundBitCount) 327 Out << Templ.UpperBoundIntro << UpperBoundBitCount.value(); 328 const std::string Msg(Out.str()); 329 330 return Ctx.getNoteTag(Msg, /*isPrunable=*/true); 331 } 332 333 std::unique_ptr<PathSensitiveBugReport> 334 BitwiseShiftValidator::createBugReport(StringRef ShortMsg, StringRef Msg) const { 335 ProgramStateRef State = Ctx.getState(); 336 if (ExplodedNode *ErrNode = Ctx.generateErrorNode(State)) { 337 auto BR = 338 std::make_unique<PathSensitiveBugReport>(BT, ShortMsg, Msg, ErrNode); 339 bugreporter::trackExpressionValue(ErrNode, Op->getLHS(), *BR); 340 bugreporter::trackExpressionValue(ErrNode, Op->getRHS(), *BR); 341 return BR; 342 } 343 return nullptr; 344 } 345 } // anonymous namespace 346 347 class BitwiseShiftChecker : public Checker<check::PreStmt<BinaryOperator>> { 348 BugType BT{this, "Bitwise shift", "Suspicious operation"}; 349 350 public: 351 void checkPreStmt(const BinaryOperator *B, CheckerContext &Ctx) const { 352 BinaryOperator::Opcode Op = B->getOpcode(); 353 354 if (Op != BO_Shl && Op != BO_Shr) 355 return; 356 357 BitwiseShiftValidator(B, Ctx, BT, Pedantic).run(); 358 } 359 360 bool Pedantic = false; 361 }; 362 363 void ento::registerBitwiseShiftChecker(CheckerManager &Mgr) { 364 auto *Chk = Mgr.registerChecker<BitwiseShiftChecker>(); 365 const AnalyzerOptions &Opts = Mgr.getAnalyzerOptions(); 366 Chk->Pedantic = Opts.getCheckerBooleanOption(Chk, "Pedantic"); 367 } 368 369 bool ento::shouldRegisterBitwiseShiftChecker(const CheckerManager &mgr) { 370 return true; 371 } 372