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