26#include "llvm/Support/FormatVariadic.h"
36using BugReportPtr = std::unique_ptr<PathSensitiveBugReport>;
38struct NoteTagTemplate {
39 llvm::StringLiteral SignInfo;
40 llvm::StringLiteral UpperBoundIntro;
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 "}
53class BitwiseShiftValidator {
58 const bool PedanticFlag;
61 enum { NonNegLeft = 1, NonNegRight = 2 };
62 unsigned NonNegOperands = 0;
64 std::optional<unsigned> UpperBoundBitCount = std::nullopt;
69 : Ctx(
C), FoldedState(
C.getState()), Op(O), BT(B), PedanticFlag(
P) {}
73 const Expr *operandExpr(OperandSide Side)
const {
74 return Side == OperandSide::Left ? Op->
getLHS() : Op->
getRHS();
77 bool shouldPerformPedanticChecks()
const {
86 const NoteTag *createNoteTag()
const;
88 BugReportPtr createBugReport(StringRef ShortMsg, StringRef Msg)
const;
90 BugReportPtr checkOvershift();
91 BugReportPtr checkOperandNegative(OperandSide Side);
92 BugReportPtr checkLeftShiftOverflow();
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" :
""; }
100void BitwiseShiftValidator::run() {
103 if (BugReportPtr BR = checkOvershift()) {
109 if (BugReportPtr BR = checkOperandNegative(OperandSide::Right)) {
114 if (shouldPerformPedanticChecks()) {
116 if (BugReportPtr BR = checkOperandNegative(OperandSide::Left)) {
122 if (BugReportPtr BR = checkLeftShiftOverflow()) {
137bool BitwiseShiftValidator::assumeRequirement(OperandSide Side,
142 const SVal OperandVal = Ctx.
getSVal(operandExpr(Side));
147 auto ResultVal = SVB.
evalBinOp(FoldedState, Comparison, OperandVal, LimitVal,
150 auto [StTrue, StFalse] = FoldedState->assume(DURes.value());
153 FoldedState = StFalse;
157 FoldedState = StTrue;
160 recordAssumption(Side, Comparison, Limit);
166BugReportPtr BitwiseShiftValidator::checkOvershift() {
170 if (assumeRequirement(OperandSide::Right, BO_LT, LHSBitWidth))
175 std::string RightOpStr =
"", LowerBoundStr =
"";
177 RightOpStr = formatv(
" '{0}'", ConcreteRight->getValue());
180 if (
const llvm::APSInt *MinRight = SVB.
getMinValue(FoldedState, Right)) {
181 LowerBoundStr = formatv(
" >= {0},", MinRight->getExtValue());
185 std::string ShortMsg = formatv(
186 "{0} shift{1}{2} overflows the capacity of '{3}'",
187 isLeftShift() ?
"Left" :
"Right", RightOpStr.empty() ?
"" :
" by",
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);
206BugReportPtr BitwiseShiftValidator::checkOperandNegative(OperandSide Side) {
208 if (!operandExpr(Side)->getType()->isSignedIntegerType())
212 if (assumeRequirement(Side, BO_GE, 0))
215 std::string ShortMsg = formatv(
"{0} operand is negative in {1} shift",
216 Side == OperandSide::Left ?
"Left" :
"Right",
219 std::string Msg = formatv(
"The result of {0} shift is undefined "
220 "because the {1} operand is negative",
222 Side == OperandSide::Left ?
"left" :
"right")
225 return createBugReport(ShortMsg, Msg);
228BugReportPtr BitwiseShiftValidator::checkLeftShiftOverflow() {
235 const bool ShouldPreserveSignBit = !Ctx.
getLangOpts().CPlusPlus;
237 const Expr *LHS = operandExpr(OperandSide::Left);
240 assert(LeftBitWidth > 0);
249 if (!
Left.has_value())
254 assert(
Left->getValue().isNonNegative());
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;
263 if (assumeRequirement(OperandSide::Right, BO_LT, MaximalAllowedShift + 1))
266 const std::string CapacityMsg =
267 formatv(
"because '{0}' can hold only {1} bits ({2} the sign bit)",
269 ShouldPreserveSignBit ?
"excluding" :
"including");
273 std::string ShortMsg, Msg;
277 const unsigned RHS = ConcreteRight->getValue().getExtValue();
278 assert(RHS > MaximalAllowedShift);
279 const unsigned OverflownBits = RHS - MaximalAllowedShift;
281 "The shift '{0} << {1}' overflows the capacity of '{2}'",
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));
288 ShortMsg = formatv(
"Left shift of '{0}' overflows the capacity of '{1}'",
291 "Left shift of '{0}' is undefined {1}, so some bits overflow",
292 Left->getValue(), CapacityMsg);
295 return createBugReport(ShortMsg, Msg);
298void BitwiseShiftValidator::recordAssumption(OperandSide Side,
301 switch (Comparison) {
304 NonNegOperands |= (Side == OperandSide::Left ? NonNegLeft : NonNegRight);
307 assert(Side == OperandSide::Right);
308 if (!UpperBoundBitCount || Limit < UpperBoundBitCount.value())
309 UpperBoundBitCount = Limit;
312 llvm_unreachable(
"this checker does not use other comparison operators");
316const NoteTag *BitwiseShiftValidator::createNoteTag()
const {
317 if (!NonNegOperands && !UpperBoundBitCount)
321 llvm::raw_svector_ostream Out(Buf);
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());
332std::unique_ptr<PathSensitiveBugReport>
333BitwiseShiftValidator::createBugReport(StringRef ShortMsg, StringRef Msg)
const {
337 std::make_unique<PathSensitiveBugReport>(BT, ShortMsg, Msg, ErrNode);
347 BugType BT{
this,
"Bitwise shift",
"Suspicious operation"};
353 if (Op != BO_Shl && Op != BO_Shr)
356 BitwiseShiftValidator(B, Ctx, BT,
Pedantic).run();
368bool ento::shouldRegisterBitwiseShiftChecker(
const CheckerManager &mgr) {
Defines the clang::ASTContext interface.
void checkPreStmt(const BinaryOperator *B, CheckerContext &Ctx) const
unsigned getIntWidth(QualType T) const
const LangOptions & getLangOpts() const
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".
This represents one expression.
A (possibly-)qualified type.
static std::string getAsString(SplitQualType split, const PrintingPolicy &Policy)
bool isUnsignedIntegerType() const
Return true if this is an integer type that is unsigned, according to C99 6.2.5p6 [which returns true...
SValBuilder & getSValBuilder()
ASTContext & getASTContext()
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.
nonloc::ConcreteInt makeIntVal(const IntegerLiteral *integer)
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
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.
std::optional< T > getAs() const
Convert to the specified SVal type, returning std::nullopt if this SVal is not of the desired type.
Value representing integer constant.
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.
The JSON file list parser is used to communicate input to InstallAPI.