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/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 {.SignInfo: "", .UpperBoundIntro: "right operand of bit shift is less than "},
43 {.SignInfo: "left operand of bit shift is non-negative", .UpperBoundIntro: " and right operand is less than "},
44 {.SignInfo: "right operand of bit shift is non-negative", .UpperBoundIntro: " but less than "},
45 {.SignInfo: "both operands of bit shift are non-negative", .UpperBoundIntro: " and right operand is less than "}
46};
47
48/// An implementation detail class which is introduced to split the checker
49/// logic into several methods while maintaining a consistently updated state
50/// 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 issues
77 // 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 the
100 // left operand:
101 if (BugReportPtr BR = checkOvershift()) {
102 Ctx.emitReport(R: std::move(BR));
103 return;
104 }
105
106 // Report a bug if the right operand is negative:
107 if (BugReportPtr BR = checkOperandNegative(Side: OperandSide::Right)) {
108 Ctx.emitReport(R: 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(Side: OperandSide::Left)) {
115 Ctx.emitReport(R: 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(R: std::move(BR));
122 return;
123 }
124 }
125
126 // No bugs detected, update the state and add a single note tag which
127 // summarizes the new assumptions.
128 Ctx.addTransition(State: FoldedState, Tag: createNoteTag());
129}
130
131/// This method checks a requirement that must be satisfied by the value on the
132/// given Side of a bitwise shift operator in well-defined code. If the
133/// requirement is incompatible with prior knowledge, this method reports
134/// 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 a
143 // negative `Val` could be converted to a large positive value.
144
145 auto ResultVal = SVB.evalBinOp(state: FoldedState, op: Comparison, lhs: OperandVal, rhs: LimitVal,
146 type: 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 made
158 recordAssumption(Side, Cmp: 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(T: LHSTy);
167
168 if (assumeRequirement(Side: OperandSide::Right, Comparison: BO_LT, Limit: LHSBitWidth))
169 return nullptr;
170
171 const SVal Right = Ctx.getSVal(operandExpr(Side: 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(state: FoldedState, val: Right);
179 MinRight && *MinRight >= LHSBitWidth) {
180 LowerBoundStr = formatv(Fmt: " >= {0},", Vals: MinRight->getExtValue());
181 }
182 }
183
184 std::string ShortMsg = formatv(
185 Fmt: "{0} shift{1}{2} overflows the capacity of '{3}'",
186 Vals: isLeftShift() ? "Left" : "Right", Vals: RightOpStr.empty() ? "" : " by",
187 Vals&: RightOpStr, Vals: LHSTy.getAsString());
188 std::string Msg = formatv(
189 Fmt: "The result of {0} shift is undefined because the right "
190 "operand{1} is{2} not smaller than {3}, the capacity of '{4}'",
191 Vals: shiftDir(), Vals&: RightOpStr, Vals&: LowerBoundStr, Vals: LHSBitWidth, Vals: LHSTy.getAsString());
192 return createBugReport(ShortMsg, Msg);
193}
194
195// Before C++20, at 5.8 [expr.shift] (N4296, 2014-11-19) the standard says
196// 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 standard
204// eliminates conditions 2 and 3.
205BugReportPtr BitwiseShiftValidator::checkOperandNegative(OperandSide Side) {
206 // If the type is unsigned, it cannot be negative
207 if (!operandExpr(Side)->getType()->isSignedIntegerType())
208 return nullptr;
209
210 // Main check: determine whether the operand is constrained to be negative
211 if (assumeRequirement(Side, Comparison: BO_GE, Limit: 0))
212 return nullptr;
213
214 std::string ShortMsg = formatv(Fmt: "{0} operand is negative in {1} shift",
215 Vals: Side == OperandSide::Left ? "Left" : "Right",
216 Vals: shiftDir())
217 .str();
218 std::string Msg = formatv(Fmt: "The result of {0} shift is undefined "
219 "because the {1} operand is negative",
220 Vals: shiftDir(),
221 Vals: 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(Side: OperandSide::Left);
237 const QualType LHSTy = LHS->getType();
238 const unsigned LeftBitWidth = Ctx.getASTContext().getIntWidth(T: 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 was
252 // 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(Side: OperandSide::Right, Comparison: BO_LT, Limit: MaximalAllowedShift + 1))
263 return nullptr;
264
265 const std::string CapacityMsg =
266 formatv(Fmt: "because '{0}' can hold only {1} bits ({2} the sign bit)",
267 Vals: LHSTy.getAsString(), Vals: LeftAvailableBitWidth,
268 Vals: 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, because
275 // 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(n: OverflownBits), verbSuffix(n: 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(Note: Msg, /*isPrunable=*/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>(args: BT, args&: ShortMsg, args&: Msg, args&: ErrNode);
337 bugreporter::trackExpressionValue(N: ErrNode, E: Op->getLHS(), R&: *BR);
338 bugreporter::trackExpressionValue(N: ErrNode, E: Op->getRHS(), R&: *BR);
339 return BR;
340 }
341 return nullptr;
342}
343} // anonymous namespace
344
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(C: Chk, OptionName: "Pedantic");
365}
366
367bool ento::shouldRegisterBitwiseShiftChecker(const CheckerManager &mgr) {
368 return true;
369}
370

source code of clang/lib/StaticAnalyzer/Checkers/BitwiseShiftChecker.cpp