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