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
23using namespace clang;
24using namespace ento;
25
26namespace {
27class 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
47public:
48 void checkPreStmt(const BinaryOperator *B, CheckerContext &C) const;
49};
50}
51
52bool 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>(args: BT, args: Msg, args&: N);
61 R->addRange(R: E->getSourceRange());
62 C.emitReport(R: 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: State, val: ElemReg->getIndex());
72 I && (!I->isOne() && !I->isZero()))
73 ReportBug(Msg_BadVarIndex);
74 return false;
75 }
76
77 DefinedOrUnknownSVal ElemCount =
78 getDynamicElementCount(State, MR: SuperReg, SVB, Ty: ElemReg->getElementType());
79 auto IndexTooLarge = SVB.evalBinOp(state: C.getState(), op: BO_GT, lhs: ElemReg->getIndex(),
80 rhs: ElemCount, type: SVB.getConditionType())
81 .getAs<DefinedOrUnknownSVal>();
82 if (IndexTooLarge) {
83 ProgramStateRef S1, S2;
84 std::tie(args&: S1, args&: S2) = C.getState()->assume(Cond: *IndexTooLarge);
85 if (S1 && !S2) {
86 ReportBug(Msg_LargeArrayIndex);
87 return false;
88 }
89 }
90 auto IndexTooSmall = SVB.evalBinOp(state: State, op: BO_LT, lhs: ElemReg->getIndex(),
91 rhs: SVB.makeZeroVal(type: SVB.getArrayIndexType()),
92 type: SVB.getConditionType())
93 .getAs<DefinedOrUnknownSVal>();
94 if (IndexTooSmall) {
95 ProgramStateRef S1, S2;
96 std::tie(args&: S1, args&: S2) = State->assume(Cond: *IndexTooSmall);
97 if (S1 && !S2) {
98 ReportBug(Msg_NegativeArrayIndex);
99 return false;
100 }
101 }
102 return true;
103}
104
105void 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(S: B->getLHS());
113 SVal RV = C.getSVal(S: 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>(Val: LR) || isa<SymbolicRegion>(Val: RR))
126 return;
127
128 const auto *ElemLR = dyn_cast<ElementRegion>(Val: LR);
129 const auto *ElemRR = dyn_cast<ElementRegion>(Val: RR);
130
131 if (!checkArrayBounds(C, E: B->getLHS(), ElemReg: ElemLR, Reg: RR))
132 return;
133 if (!checkArrayBounds(C, E: B->getRHS(), ElemReg: ElemRR, Reg: 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>(Val: SuperLR) || isa<SymbolicRegion>(Val: SuperRR))
146 return;
147 if (const auto *SuperDLR = dyn_cast<DeclRegion>(Val: SuperLR))
148 DiffDeclL = SuperDLR->getDecl();
149 if (const auto *SuperDRR = dyn_cast<DeclRegion>(Val: SuperRR))
150 DiffDeclR = SuperDRR->getDecl();
151 }
152
153 if (ExplodedNode *N = C.generateNonFatalErrorNode()) {
154 auto R =
155 std::make_unique<PathSensitiveBugReport>(args: BT, args: Msg_MemRegionDifferent, args&: N);
156 R->addRange(R: 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(Msg: "Array at the left-hand side of subtraction",
164 Pos: {DiffDeclL, C.getSourceManager()});
165 if (DiffDeclR)
166 R->addNote(Msg: "Array at the right-hand side of subtraction",
167 Pos: {DiffDeclR, C.getSourceManager()});
168 }
169 C.emitReport(R: std::move(R));
170 }
171}
172
173void ento::registerPointerSubChecker(CheckerManager &mgr) {
174 mgr.registerChecker<PointerSubChecker>();
175}
176
177bool ento::shouldRegisterPointerSubChecker(const CheckerManager &mgr) {
178 return true;
179}
180