1//===- UnsafeBufferUsageAnalysis.cpp - WPA for UnsafeBufferUsage ----------===//
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// UnsafeBufferUsageAnalysis is a noop analysis.
9//
10// UnsafeBufferUsageAnalysisResult is a map from EntityIds to
11// EntityPointerLevelSets.
12//
13// UnsafeBufferReachableAnalysisResult is a flat set of EntityPointerLevels
14// reachable from unsafe buffer usage.
15//===----------------------------------------------------------------------===//
16
17#include "clang/ScalableStaticAnalysis/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.h"
18#include "SSAFAnalysesCommon.h"
19#include "clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h"
20#include "clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevelFormat.h"
21#include "clang/ScalableStaticAnalysis/Analyses/PointerFlow/PointerFlow.h"
22#include "clang/ScalableStaticAnalysis/Analyses/PointerFlow/PointerFlowAnalysis.h"
23#include "clang/ScalableStaticAnalysis/Analyses/TypeConstrainedPointers/TypeConstrainedPointers.h"
24#include "clang/ScalableStaticAnalysis/Analyses/UnsafeBufferUsage/UnsafeBufferUsage.h"
25#include "clang/ScalableStaticAnalysis/Core/Model/EntityId.h"
26#include "clang/ScalableStaticAnalysis/Core/Serialization/JSONFormat.h"
27#include "clang/ScalableStaticAnalysis/Core/WholeProgramAnalysis/AnalysisRegistry.h"
28#include "clang/ScalableStaticAnalysis/Core/WholeProgramAnalysis/SummaryAnalysis.h"
29#include "llvm/ADT/STLExtras.h"
30#include "llvm/ADT/iterator_range.h"
31#include "llvm/Support/Error.h"
32#include "llvm/Support/JSON.h"
33#include <memory>
34
35using namespace clang::ssaf;
36using namespace llvm;
37
38namespace {
39
40json::Object serializeUnsafeBufferUsageAnalysisResult(
41 const UnsafeBufferUsageAnalysisResult &R,
42 JSONFormat::EntityIdToJSONFn IdToJSON) {
43 json::Object Result;
44
45 Result[UnsafeBufferUsageAnalysisResultName] =
46 entityPointerLevelMapToJSON(Map: R.UnsafeBuffers, IdToJSON);
47 return Result;
48}
49
50Expected<std::unique_ptr<AnalysisResult>>
51deserializeUnsafeBufferUsageAnalysisResult(
52 const json::Object &Obj, JSONFormat::EntityIdFromJSONFn IdFromJSON) {
53 const json::Array *Content =
54 Obj.getArray(K: UnsafeBufferUsageAnalysisResultName);
55
56 if (!Content)
57 return makeSawButExpectedError(Saw: Obj, Expected: "an object with a key %s",
58 ExpectedArgs: UnsafeBufferUsageAnalysisResultName.data());
59
60 auto UnsafeBuffers = entityPointerLevelMapFromJSON(Content: *Content, IdFromJSON);
61
62 if (!UnsafeBuffers)
63 return UnsafeBuffers.takeError();
64
65 auto Ret = std::make_unique<UnsafeBufferUsageAnalysisResult>();
66
67 Ret->UnsafeBuffers = std::move(*UnsafeBuffers);
68 return std::move(Ret);
69}
70
71JSONFormat::AnalysisResultRegistry::Add<UnsafeBufferUsageAnalysisResult>
72 RegisterUnsafeBufferUsageResultForJSON(
73 serializeUnsafeBufferUsageAnalysisResult,
74 deserializeUnsafeBufferUsageAnalysisResult);
75
76class UnsafeBufferUsageAnalysis final
77 : public SummaryAnalysis<UnsafeBufferUsageAnalysisResult,
78 UnsafeBufferUsageEntitySummary> {
79public:
80 llvm::Error add(EntityId Id,
81 const UnsafeBufferUsageEntitySummary &Summary) override {
82 auto UnsafeBuffersOfEntity = getUnsafeBuffers(Summary);
83
84 getResult().UnsafeBuffers[Id] = EntityPointerLevelSet(
85 UnsafeBuffersOfEntity.begin(), UnsafeBuffersOfEntity.end());
86 return llvm::Error::success();
87 }
88};
89
90AnalysisRegistry::Add<UnsafeBufferUsageAnalysis>
91 RegisterUnsafeBufferUsageAnalysis(
92 "Whole-program unsafe buffer usage analysis");
93
94//===----------------------------------------------------------------------===//
95// UnsafeBufferReachableAnalysis---computes reachable unsafe buffer nodes
96//===----------------------------------------------------------------------===//
97
98json::Object serializeUnsafeBufferReachableAnalysisResult(
99 const UnsafeBufferReachableAnalysisResult &R,
100 JSONFormat::EntityIdToJSONFn IdToJSON) {
101 json::Object Result;
102
103 Result[UnsafeBufferReachableAnalysisResultName] =
104 entityPointerLevelSetToJSON(EPLs: R.Reachables, EntityId2JSON: IdToJSON);
105 return Result;
106}
107
108Expected<std::unique_ptr<AnalysisResult>>
109deserializeUnsafeBufferReachableAnalysisResult(
110 const json::Object &Obj, JSONFormat::EntityIdFromJSONFn IdFromJSON) {
111 const json::Array *Content =
112 Obj.getArray(K: UnsafeBufferReachableAnalysisResultName);
113
114 if (!Content)
115 return makeSawButExpectedError(
116 Saw: Obj, Expected: "an object with a key %s",
117 ExpectedArgs: UnsafeBufferReachableAnalysisResultName.data());
118
119 auto Reachables = entityPointerLevelSetFromJSON(EPLsData: *Content, EntityIdFromJSON: IdFromJSON);
120
121 if (!Reachables)
122 return Reachables.takeError();
123
124 auto Ret = std::make_unique<UnsafeBufferReachableAnalysisResult>();
125
126 Ret->Reachables = std::move(*Reachables);
127 return std::move(Ret);
128}
129
130JSONFormat::AnalysisResultRegistry::Add<UnsafeBufferReachableAnalysisResult>
131 RegisterUnsafeBufferReachableResultForJSON(
132 serializeUnsafeBufferReachableAnalysisResult,
133 deserializeUnsafeBufferReachableAnalysisResult);
134
135/// \brief Computes pointers (EPLs) that satisfy a specific set of constraints.
136///
137/// The pointers must satisfy all of the following constraints:
138///
139/// 1. **C1 (Unsafe):** Any pointer in `UnsafeBufferUsageAnalysisResult`
140/// is considered unsafe.
141/// 2. **C2 (Reachable):** If a pointer is reachable from an unsafe pointer in
142/// the pointer flow graph (provided by `PointerFlowAnalysisResult`), it is
143/// also unsafe.
144/// 3. **C3 (Constrained):** Type-constrained entities are NOT unsafe.
145class UnsafeBufferReachableAnalysis
146 : public DerivedAnalysis<UnsafeBufferReachableAnalysisResult,
147 PointerFlowAnalysisResult,
148 TypeConstrainedPointersAnalysisResult,
149 UnsafeBufferUsageAnalysisResult> {
150
151 struct BoundsPropagationGraph {
152 EdgeSet PointerFlows;
153
154 /// Returns the EntityPointerLevelSet that are reachable from \p Src by
155 /// one edge in the BoundsPropagationGraph.
156 EntityPointerLevelSet getDestNodes(const EntityPointerLevel &Src) const {
157 auto I = PointerFlows.find(x: Src);
158 if (I == PointerFlows.end())
159 return {};
160 return I->second;
161 }
162 };
163
164 std::map<EntityId, BoundsPropagationGraph> BPG;
165
166 // Use pointers for efficiency. EPLs are in tree-based containers that only
167 // grow. So pointers to them are stable.
168 using EPLPtr = const EntityPointerLevel *;
169
170 // Find all outgoing edges from `EPL` in the `Graph`, insert their
171 // destination nodes into `Reachables`, and add newly discovered nodes to
172 // `Worklist`:
173 void updateReachablesWithOutgoings(EPLPtr EPL,
174 std::vector<EPLPtr> &WorkList) {
175 for (auto &[Id, SubGraph] : BPG) {
176 auto R = SubGraph.getDestNodes(Src: *EPL);
177
178 for (const auto &Dst : R) {
179 auto [It, Inserted] = getResult().Reachables.insert(x: Dst);
180 if (Inserted)
181 WorkList.push_back(x: &*It);
182 }
183 }
184 }
185
186 // Expand the initial set of C1 pointers in `getResult().Reachables` by
187 // computing and appending all reachable pointers, satisfying both C1 and C2.
188 void computeReachableUnsafePointers() {
189 auto &Reachables = getResult().Reachables;
190 // Simple DFS:
191 std::vector<EPLPtr> Worklist;
192
193 for (auto &EPL : Reachables)
194 Worklist.push_back(x: &EPL);
195
196 while (!Worklist.empty()) {
197 EPLPtr Node = Worklist.back();
198 Worklist.pop_back();
199
200 updateReachablesWithOutgoings(EPL: Node, WorkList&: Worklist);
201 }
202 }
203
204public:
205 llvm::Error
206 initialize(const PointerFlowAnalysisResult &PtrFlowGraph,
207 const TypeConstrainedPointersAnalysisResult &TypeConstraints,
208 const UnsafeBufferUsageAnalysisResult &UnsafePtrs) override {
209 auto HasNoTypeConstraint =
210 [&TypeConstraints](const EntityPointerLevel &EPL) {
211 return !TypeConstraints.contains(Id: EPL.getEntity());
212 };
213
214 // Filter out edges involving type-constrained pointers from `PtrFlowGraph`:
215 for (auto &[Id, SubGraph] : PtrFlowGraph.Edges) {
216 EdgeSet FilteredSubGraph;
217
218 for (const auto &[Src, Dsts] : SubGraph) {
219 if (TypeConstraints.contains(Id: Src.getEntity()))
220 continue;
221
222 auto FilteredDstRange =
223 llvm::make_filter_range(Range: Dsts, Pred: HasNoTypeConstraint);
224
225 if (!FilteredDstRange.empty())
226 FilteredSubGraph[Src].insert(first: FilteredDstRange.begin(),
227 last: FilteredDstRange.end());
228 }
229 if (!FilteredSubGraph.empty())
230 BPG.try_emplace(k: Id,
231 args: BoundsPropagationGraph{.PointerFlows: std::move(FilteredSubGraph)});
232 }
233
234 // Filter out type-constrained pointers from `UnsafePtrs`:
235 for (auto &[Contributor, EPLs] : UnsafePtrs) {
236 auto FilteredRange = llvm::make_filter_range(Range: EPLs, Pred: HasNoTypeConstraint);
237
238 getResult().Reachables.insert(first: FilteredRange.begin(), last: FilteredRange.end());
239 }
240 return llvm::Error::success();
241 }
242
243 llvm::Expected<bool> step() override {
244 // Compute the reachable EPLs from the C1 unsafe pointers over the
245 // pointer-flow graph; both are already C3-filtered, so the result
246 // satisfies C1, C2, and C3.
247 computeReachableUnsafePointers();
248 // This is not an iterative algorithm so stop iteration by retruning false:
249 return false;
250 }
251};
252
253AnalysisRegistry::Add<UnsafeBufferReachableAnalysis>
254 RegisterUnsafeBufferReachableAnalysis(
255 "Reachable pointers from unsafe buffer usage in pointer flow graph");
256
257} // namespace
258
259namespace clang::ssaf {
260// NOLINTNEXTLINE(misc-use-internal-linkage)
261volatile int UnsafeBufferUsageAnalysisAnchorSource = 0;
262} // namespace clang::ssaf
263