1 //=== PointerSubChecker.cpp - Pointer subtraction checker ------*- 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 files defines PointerSubChecker, a builtin checker that checks for
10 // pointer subtractions on two pointers pointing to different memory chunks.
11 // This check corresponds to CWE-469.
12 //
13 //===----------------------------------------------------------------------===//
14
15 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
16 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
17 #include "clang/StaticAnalyzer/Core/Checker.h"
18 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
19 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
20 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h"
21 #include "llvm/ADT/StringRef.h"
22
23 using namespace clang;
24 using namespace ento;
25
26 namespace {
27 class PointerSubChecker
28 : public Checker< check::PreStmt<BinaryOperator> > {
29 const BugType BT{this, "Pointer subtraction"};
30 const llvm::StringLiteral Msg_MemRegionDifferent =
31 "Subtraction of two pointers that do not point into the same array "
32 "is undefined behavior.";
33 const llvm::StringLiteral Msg_LargeArrayIndex =
34 "Using an array index greater than the array size at pointer subtraction "
35 "is undefined behavior.";
36 const llvm::StringLiteral Msg_NegativeArrayIndex =
37 "Using a negative array index at pointer subtraction "
38 "is undefined behavior.";
39 const llvm::StringLiteral Msg_BadVarIndex =
40 "Indexing the address of a variable with other than 1 at this place "
41 "is undefined behavior.";
42
43 bool checkArrayBounds(CheckerContext &C, const Expr *E,
44 const ElementRegion *ElemReg,
45 const MemRegion *Reg) const;
46
47 public:
48 void checkPreStmt(const BinaryOperator *B, CheckerContext &C) const;
49 };
50 }
51
checkArrayBounds(CheckerContext & C,const Expr * E,const ElementRegion * ElemReg,const MemRegion * Reg) const52 bool PointerSubChecker::checkArrayBounds(CheckerContext &C, const Expr *E,
53 const ElementRegion *ElemReg,
54 const MemRegion *Reg) const {
55 if (!ElemReg)
56 return true;
57
58 auto ReportBug = [&](const llvm::StringLiteral &Msg) {
59 if (ExplodedNode *N = C.generateNonFatalErrorNode()) {
60 auto R = std::make_unique<PathSensitiveBugReport>(BT, Msg, N);
61 R->addRange(E->getSourceRange());
62 C.emitReport(std::move(R));
63 }
64 };
65
66 ProgramStateRef State = C.getState();
67 const MemRegion *SuperReg = ElemReg->getSuperRegion();
68 SValBuilder &SVB = C.getSValBuilder();
69
70 if (SuperReg == Reg) {
71 if (const llvm::APSInt *I = SVB.getKnownValue(State, ElemReg->getIndex());
72 I && (!I->isOne() && !I->isZero()))
73 ReportBug(Msg_BadVarIndex);
74 return false;
75 }
76
77 DefinedOrUnknownSVal ElemCount =
78 getDynamicElementCount(State, SuperReg, SVB, ElemReg->getElementType());
79 auto IndexTooLarge = SVB.evalBinOp(C.getState(), BO_GT, ElemReg->getIndex(),
80 ElemCount, SVB.getConditionType())
81 .getAs<DefinedOrUnknownSVal>();
82 if (IndexTooLarge) {
83 ProgramStateRef S1, S2;
84 std::tie(S1, S2) = C.getState()->assume(*IndexTooLarge);
85 if (S1 && !S2) {
86 ReportBug(Msg_LargeArrayIndex);
87 return false;
88 }
89 }
90 auto IndexTooSmall = SVB.evalBinOp(State, BO_LT, ElemReg->getIndex(),
91 SVB.makeZeroVal(SVB.getArrayIndexType()),
92 SVB.getConditionType())
93 .getAs<DefinedOrUnknownSVal>();
94 if (IndexTooSmall) {
95 ProgramStateRef S1, S2;
96 std::tie(S1, S2) = State->assume(*IndexTooSmall);
97 if (S1 && !S2) {
98 ReportBug(Msg_NegativeArrayIndex);
99 return false;
100 }
101 }
102 return true;
103 }
104
checkPreStmt(const BinaryOperator * B,CheckerContext & C) const105 void PointerSubChecker::checkPreStmt(const BinaryOperator *B,
106 CheckerContext &C) const {
107 // When doing pointer subtraction, if the two pointers do not point to the
108 // same array, emit a warning.
109 if (B->getOpcode() != BO_Sub)
110 return;
111
112 SVal LV = C.getSVal(B->getLHS());
113 SVal RV = C.getSVal(B->getRHS());
114
115 const MemRegion *LR = LV.getAsRegion();
116 const MemRegion *RR = RV.getAsRegion();
117 if (!LR || !RR)
118 return;
119
120 // Allow subtraction of identical pointers.
121 if (LR == RR)
122 return;
123
124 // No warning if one operand is unknown.
125 if (isa<SymbolicRegion>(LR) || isa<SymbolicRegion>(RR))
126 return;
127
128 const auto *ElemLR = dyn_cast<ElementRegion>(LR);
129 const auto *ElemRR = dyn_cast<ElementRegion>(RR);
130
131 if (!checkArrayBounds(C, B->getLHS(), ElemLR, RR))
132 return;
133 if (!checkArrayBounds(C, B->getRHS(), ElemRR, LR))
134 return;
135
136 const ValueDecl *DiffDeclL = nullptr;
137 const ValueDecl *DiffDeclR = nullptr;
138
139 if (ElemLR && ElemRR) {
140 const MemRegion *SuperLR = ElemLR->getSuperRegion();
141 const MemRegion *SuperRR = ElemRR->getSuperRegion();
142 if (SuperLR == SuperRR)
143 return;
144 // Allow arithmetic on different symbolic regions.
145 if (isa<SymbolicRegion>(SuperLR) || isa<SymbolicRegion>(SuperRR))
146 return;
147 if (const auto *SuperDLR = dyn_cast<DeclRegion>(SuperLR))
148 DiffDeclL = SuperDLR->getDecl();
149 if (const auto *SuperDRR = dyn_cast<DeclRegion>(SuperRR))
150 DiffDeclR = SuperDRR->getDecl();
151 }
152
153 if (ExplodedNode *N = C.generateNonFatalErrorNode()) {
154 auto R =
155 std::make_unique<PathSensitiveBugReport>(BT, Msg_MemRegionDifferent, N);
156 R->addRange(B->getSourceRange());
157 // The declarations may be identical even if the regions are different:
158 // struct { int array[10]; } a, b;
159 // do_something(&a.array[5] - &b.array[5]);
160 // In this case don't emit notes.
161 if (DiffDeclL != DiffDeclR) {
162 if (DiffDeclL)
163 R->addNote("Array at the left-hand side of subtraction",
164 {DiffDeclL, C.getSourceManager()});
165 if (DiffDeclR)
166 R->addNote("Array at the right-hand side of subtraction",
167 {DiffDeclR, C.getSourceManager()});
168 }
169 C.emitReport(std::move(R));
170 }
171 }
172
registerPointerSubChecker(CheckerManager & mgr)173 void ento::registerPointerSubChecker(CheckerManager &mgr) {
174 mgr.registerChecker<PointerSubChecker>();
175 }
176
shouldRegisterPointerSubChecker(const CheckerManager & mgr)177 bool ento::shouldRegisterPointerSubChecker(const CheckerManager &mgr) {
178 return true;
179 }
180