clang 19.0.0git
BitwiseShiftChecker.cpp
Go to the documentation of this file.
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
16#include "clang/AST/CharUnits.h"
26#include "llvm/Support/FormatVariadic.h"
27#include <memory>
28
29using namespace clang;
30using namespace ento;
31using llvm::formatv;
32
33namespace {
34enum class OperandSide { Left, Right };
35
36using BugReportPtr = std::unique_ptr<PathSensitiveBugReport>;
37
38struct NoteTagTemplate {
39 llvm::StringLiteral SignInfo;
40 llvm::StringLiteral UpperBoundIntro;
41};
42
43constexpr 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.
53class 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
66public:
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
72private:
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
100void 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.
137bool 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
166BugReportPtr 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 LowerBoundStr = formatv(" >= {0},", MinRight->getExtValue());
182 }
183 }
184
185 std::string ShortMsg = formatv(
186 "{0} shift{1}{2} overflows the capacity of '{3}'",
187 isLeftShift() ? "Left" : "Right", RightOpStr.empty() ? "" : " by",
188 RightOpStr, LHSTy.getAsString());
189 std::string Msg = formatv(
190 "The result of {0} shift is undefined because the right "
191 "operand{1} is{2} not smaller than {3}, the capacity of '{4}'",
192 shiftDir(), RightOpStr, LowerBoundStr, LHSBitWidth, LHSTy.getAsString());
193 return createBugReport(ShortMsg, Msg);
194}
195
196// Before C++20, at 5.8 [expr.shift] (N4296, 2014-11-19) the standard says
197// 1. "... The behaviour is undefined if the right operand is negative..."
198// 2. "The value of E1 << E2 ...
199// if E1 has a signed type and non-negative value ...
200// otherwise, the behavior is undefined."
201// 3. "The value of E1 >> E2 ...
202// If E1 has a signed type and a negative value,
203// the resulting value is implementation-defined."
204// However, negative left arguments work in practice and the C++20 standard
205// eliminates conditions 2 and 3.
206BugReportPtr BitwiseShiftValidator::checkOperandNegative(OperandSide Side) {
207 // If the type is unsigned, it cannot be negative
208 if (!operandExpr(Side)->getType()->isSignedIntegerType())
209 return nullptr;
210
211 // Main check: determine whether the operand is constrained to be negative
212 if (assumeRequirement(Side, BO_GE, 0))
213 return nullptr;
214
215 std::string ShortMsg = formatv("{0} operand is negative in {1} shift",
216 Side == OperandSide::Left ? "Left" : "Right",
217 shiftDir())
218 .str();
219 std::string Msg = formatv("The result of {0} shift is undefined "
220 "because the {1} operand is negative",
221 shiftDir(),
222 Side == OperandSide::Left ? "left" : "right")
223 .str();
224
225 return createBugReport(ShortMsg, Msg);
226}
227
228BugReportPtr BitwiseShiftValidator::checkLeftShiftOverflow() {
229 // A right shift cannot be an overflowing left shift...
230 if (!isLeftShift())
231 return nullptr;
232
233 // In C++ it's well-defined to shift to the sign bit. In C however, it's UB.
234 // 5.8.2 [expr.shift] (N4296, 2014-11-19)
235 const bool ShouldPreserveSignBit = !Ctx.getLangOpts().CPlusPlus;
236
237 const Expr *LHS = operandExpr(OperandSide::Left);
238 const QualType LHSTy = LHS->getType();
239 const unsigned LeftBitWidth = Ctx.getASTContext().getIntWidth(LHSTy);
240 assert(LeftBitWidth > 0);
241
242 // Quote "For unsigned lhs, the value of LHS << RHS is the value of LHS *
243 // 2^RHS, reduced modulo maximum value of the return type plus 1."
244 if (LHSTy->isUnsignedIntegerType())
245 return nullptr;
246
247 // We only support concrete integers as left operand.
248 const auto Left = Ctx.getSVal(LHS).getAs<nonloc::ConcreteInt>();
249 if (!Left.has_value())
250 return nullptr;
251
252 // We should have already reported a bug if the left operand of the shift was
253 // negative, so it cannot be negative here.
254 assert(Left->getValue().isNonNegative());
255
256 const unsigned LeftAvailableBitWidth =
257 LeftBitWidth - static_cast<unsigned>(ShouldPreserveSignBit);
258 const unsigned UsedBitsInLeftOperand = Left->getValue().getActiveBits();
259 assert(LeftBitWidth >= UsedBitsInLeftOperand);
260 const unsigned MaximalAllowedShift =
261 LeftAvailableBitWidth - UsedBitsInLeftOperand;
262
263 if (assumeRequirement(OperandSide::Right, BO_LT, MaximalAllowedShift + 1))
264 return nullptr;
265
266 const std::string CapacityMsg =
267 formatv("because '{0}' can hold only {1} bits ({2} the sign bit)",
268 LHSTy.getAsString(), LeftAvailableBitWidth,
269 ShouldPreserveSignBit ? "excluding" : "including");
270
271 const SVal Right = Ctx.getSVal(Op->getRHS());
272
273 std::string ShortMsg, Msg;
274 if (const auto ConcreteRight = Right.getAs<nonloc::ConcreteInt>()) {
275 // Here ConcreteRight must contain a small non-negative integer, because
276 // otherwise one of the earlier checks should've reported a bug.
277 const unsigned RHS = ConcreteRight->getValue().getExtValue();
278 assert(RHS > MaximalAllowedShift);
279 const unsigned OverflownBits = RHS - MaximalAllowedShift;
280 ShortMsg = formatv(
281 "The shift '{0} << {1}' overflows the capacity of '{2}'",
282 Left->getValue(), ConcreteRight->getValue(), LHSTy.getAsString());
283 Msg = formatv(
284 "The shift '{0} << {1}' is undefined {2}, so {3} bit{4} overflow{5}",
285 Left->getValue(), ConcreteRight->getValue(), CapacityMsg, OverflownBits,
286 pluralSuffix(OverflownBits), verbSuffix(OverflownBits));
287 } else {
288 ShortMsg = formatv("Left shift of '{0}' overflows the capacity of '{1}'",
289 Left->getValue(), LHSTy.getAsString());
290 Msg = formatv(
291 "Left shift of '{0}' is undefined {1}, so some bits overflow",
292 Left->getValue(), CapacityMsg);
293 }
294
295 return createBugReport(ShortMsg, Msg);
296}
297
298void BitwiseShiftValidator::recordAssumption(OperandSide Side,
299 BinaryOperator::Opcode Comparison,
300 unsigned Limit) {
301 switch (Comparison) {
302 case BO_GE:
303 assert(Limit == 0);
304 NonNegOperands |= (Side == OperandSide::Left ? NonNegLeft : NonNegRight);
305 break;
306 case BO_LT:
307 assert(Side == OperandSide::Right);
308 if (!UpperBoundBitCount || Limit < UpperBoundBitCount.value())
309 UpperBoundBitCount = Limit;
310 break;
311 default:
312 llvm_unreachable("this checker does not use other comparison operators");
313 }
314}
315
316const NoteTag *BitwiseShiftValidator::createNoteTag() const {
317 if (!NonNegOperands && !UpperBoundBitCount)
318 return nullptr;
319
321 llvm::raw_svector_ostream Out(Buf);
322 Out << "Assuming ";
323 NoteTagTemplate Templ = NoteTagTemplates[NonNegOperands];
324 Out << Templ.SignInfo;
325 if (UpperBoundBitCount)
326 Out << Templ.UpperBoundIntro << UpperBoundBitCount.value();
327 const std::string Msg(Out.str());
328
329 return Ctx.getNoteTag(Msg, /*isPrunable=*/true);
330}
331
332std::unique_ptr<PathSensitiveBugReport>
333BitwiseShiftValidator::createBugReport(StringRef ShortMsg, StringRef Msg) const {
334 ProgramStateRef State = Ctx.getState();
335 if (ExplodedNode *ErrNode = Ctx.generateErrorNode(State)) {
336 auto BR =
337 std::make_unique<PathSensitiveBugReport>(BT, ShortMsg, Msg, ErrNode);
338 bugreporter::trackExpressionValue(ErrNode, Op->getLHS(), *BR);
339 bugreporter::trackExpressionValue(ErrNode, Op->getRHS(), *BR);
340 return BR;
341 }
342 return nullptr;
343}
344} // anonymous namespace
345
346class BitwiseShiftChecker : public Checker<check::PreStmt<BinaryOperator>> {
347 BugType BT{this, "Bitwise shift", "Suspicious operation"};
348
349public:
350 void checkPreStmt(const BinaryOperator *B, CheckerContext &Ctx) const {
352
353 if (Op != BO_Shl && Op != BO_Shr)
354 return;
355
356 BitwiseShiftValidator(B, Ctx, BT, Pedantic).run();
357 }
358
359 bool Pedantic = false;
360};
361
362void ento::registerBitwiseShiftChecker(CheckerManager &Mgr) {
363 auto *Chk = Mgr.registerChecker<BitwiseShiftChecker>();
364 const AnalyzerOptions &Opts = Mgr.getAnalyzerOptions();
365 Chk->Pedantic = Opts.getCheckerBooleanOption(Chk, "Pedantic");
366}
367
368bool ento::shouldRegisterBitwiseShiftChecker(const CheckerManager &mgr) {
369 return true;
370}
Defines the clang::ASTContext interface.
StringRef P
void checkPreStmt(const BinaryOperator *B, CheckerContext &Ctx) const
unsigned getIntWidth(QualType T) const
const LangOptions & getLangOpts() const
Definition: ASTContext.h:778
CanQualType IntTy
Definition: ASTContext.h:1103
Stores options for the analyzer from the command line.
bool getCheckerBooleanOption(StringRef CheckerName, StringRef OptionName, bool SearchInParents=false) const
Interprets an option's string value as a boolean.
A builtin binary operation expression such as "x + y" or "x <= y".
Definition: Expr.h:3840
Expr * getLHS() const
Definition: Expr.h:3889
Expr * getRHS() const
Definition: Expr.h:3891
Opcode getOpcode() const
Definition: Expr.h:3884
This represents one expression.
Definition: Expr.h:110
QualType getType() const
Definition: Expr.h:142
A (possibly-)qualified type.
Definition: Type.h:940
static std::string getAsString(SplitQualType split, const PrintingPolicy &Policy)
Definition: Type.h:1341
bool isUnsignedIntegerType() const
Return true if this is an integer type that is unsigned, according to C99 6.2.5p6 [which returns true...
Definition: Type.cpp:2195
SValBuilder & getSValBuilder()
const ProgramStateRef & getState() const
ExplodedNode * addTransition(ProgramStateRef State=nullptr, const ProgramPointTag *Tag=nullptr)
Generates a new transition in the program state graph (ExplodedGraph).
SVal getSVal(const Stmt *S) const
Get the value of arbitrary expressions at this point in the path.
LLVM_ATTRIBUTE_RETURNS_NONNULL const NoteTag * getNoteTag(NoteTag::Callback &&Cb, bool IsPrunable=false)
Produce a program point tag that displays an additional path note to the user.
ExplodedNode * generateErrorNode(ProgramStateRef State=nullptr, const ProgramPointTag *Tag=nullptr)
Generate a transition to a node that will be used to report an error.
const LangOptions & getLangOpts() const
void emitReport(std::unique_ptr< BugReport > R)
Emit the diagnostics report.
const AnalyzerOptions & getAnalyzerOptions() const
CHECKER * registerChecker(AT &&... Args)
Used to register checkers.
The tag upon which the TagVisitor reacts.
Definition: BugReporter.h:779
nonloc::ConcreteInt makeIntVal(const IntegerLiteral *integer)
Definition: SValBuilder.h:290
virtual const llvm::APSInt * getMinValue(ProgramStateRef state, SVal val)=0
Tries to get the minimal possible (integer) value of a given SVal.
QualType getConditionType() const
Definition: SValBuilder.h:153
SVal evalBinOp(ProgramStateRef state, BinaryOperator::Opcode op, SVal lhs, SVal rhs, QualType type)
SVal - This represents a symbolic expression, which can be either an L-value or an R-value.
Definition: SVals.h:55
std::optional< T > getAs() const
Convert to the specified SVal type, returning std::nullopt if this SVal is not of the desired type.
Definition: SVals.h:86
Value representing integer constant.
Definition: SVals.h:297
bool trackExpressionValue(const ExplodedNode *N, const Expr *E, PathSensitiveBugReport &R, TrackingOptions Opts={})
Attempts to add visitors to track expression value back to its point of origin.
Stencil run(MatchConsumer< std::string > C)
Wraps a MatchConsumer in a Stencil, so that it can be used in a Stencil.
Definition: Stencil.cpp:485
The JSON file list parser is used to communicate input to InstallAPI.
BinaryOperatorKind