Static Value-Flow Analysis
Loading...
Searching...
No Matches
SparseAbstractInterpretation.cpp
Go to the documentation of this file.
1//===- SparseAbstractInterpretation.cpp -- Sparse Abstract Execution----//
2//
3// SVF: Static Value-Flow Analysis
4//
5// Copyright (C) <2013-> <Yulei Sui>
6//
7
8// This program is free software: you can redistribute it and/or modify
9// it under the terms of the GNU Affero General Public License as published by
10// the Free Software Foundation, either version 3 of the License, or
11// (at your option) any later version.
12
13// This program is distributed in the hope that it will be useful,
14// but WITHOUT ANY WARRANTY; without even the implied warranty of
15// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16// GNU Affero General Public License for more details.
17
18// You should have received a copy of the GNU Affero General Public License
19// along with this program. If not, see <http://www.gnu.org/licenses/>.
20//
21//===---------------------------------------------------------------------===//
22
24#include "AE/Svfexe/AEWTO.h"
26#include "SVFIR/SVFIR.h"
27#include "Graphs/SVFG.h"
28#include "MSSA/SVFGBuilder.h"
29#include "WPA/Andersen.h"
30
31using namespace SVF;
32
33// FullSparse Obj inputs follow prebuilt routes. Shared SSA def-site access
34// and WTO gather/scatter retain their existing implementations.
35
36// =====================================================================
37// Full-sparse — class lifecycle + SVFG construction.
38// =====================================================================
39
41
43{
44 svfgBuilder = std::make_unique<SVFGBuilder>(true);
45 svfgBuilder->buildFullSVFG(preAnalysis->getPointerAnalysis());
46 objRoutes = std::make_unique<SparseObjGraph>(
47 *svfgBuilder->getSVFG(), *svfir->getICFG(),
48 *preAnalysis->getPointerAnalysis(), *svfir);
49}
50
52 const AbstractState& src)
53{
54 for (NodeID addr : src.getFreedAddrs())
55 dst.addToFreedAddrs(addr);
56}
57
59 const AbstractState& src, const NodeBS& objs)
60{
61 for (NodeID obj : objs)
62 {
64 const auto value = src.getLocToVal().find(src.getIDFromAddr(addr));
65 if (value != src.getLocToVal().end())
66 {
67 if (dst.getLocToVal().count(dst.getIDFromAddr(addr)))
68 dst.load(addr).join_with(value->second);
69 else
70 dst.store(addr, value->second);
71 }
72 }
73}
74
76 const ICFGNode* node)
77{
78 const auto& graphEdges = objRoutes->getInputs(node);
79 AbstractState previous;
80 bool hasPrevious = false;
81 for (const SparseObjGraph::Edge* edge : graphEdges)
82 {
83 if (edge->getSrcNode()->getICFGNode() == node && hasAbsState(node))
84 {
85 previous = getAbsState(node);
86 hasPrevious = true;
87 break;
88 }
89 }
90
91 // The ICFG merge determines reachability and propagates freed addresses.
92 const bool reachable = AbstractInterpretation::mergeStatesFromPredecessors(node);
93 if (reachable)
94 {
95 AbstractState merged = getAbsState(node);
96 for (const SparseObjGraph::Edge* edge : graphEdges)
97 {
98 const SparseObjGraph::Node* sourceNode = edge->getSrcNode();
99 const ICFGNode* source = sourceNode->getICFGNode();
100 const AbstractState* sourceState = source == node
101 ? (hasPrevious ? &previous : nullptr)
102 : (hasAbsState(source)
103 ? &getAbsState(source) : nullptr);
104 if (!sourceState)
105 continue;
106
107 const AbstractState* input = sourceState;
108 AbstractState refined;
109 if (sourceNode->branch)
110 {
111 refined = *sourceState;
112 if (!isBranchEdgeFeasible(sourceNode->branch, refined) ||
113 !applyBranchRefinement(sourceNode->branch, refined))
114 continue;
115 input = &refined;
116 }
117 joinStates(merged, *input, svfir->getAllFieldsObjVars(
118 svfir->getBaseObject(sourceNode->base)));
119 }
120 updateAbsState(node, merged);
121 }
122 return reachable;
123}
124
126 const ICFGCycleWTO* cycle)
127{
128 // Start from the dense snapshot (ObjVars + any ValVars that happen to
129 // be cached at cycle_head's trace entry).
131
132 const Set<const ValVar*>& valVars = preAnalysis->getCycleValVars(cycle);
133 if (valVars.empty())
134 return snap; // no cycle ValVars known: nothing to pull
135
136 // Drop stale ValVar entries and pull each cycle ValVar from its
137 // def-site. ValVars without a genuine stored value are skipped to
138 // avoid getAbsValue's top-fallback contaminating body def-sites on
139 // the subsequent widen/narrow scatter.
140 snap.clearValVars();
141 for (const ValVar* v : valVars)
142 {
143 const ICFGNode* defSite = v->getICFGNode();
144 if (!defSite || !hasAbsValue(v, defSite))
145 continue;
146 snap[v->getId()] = getAbsValue(v, defSite);
147 }
148 return snap;
149}
150
152 const AbstractState& prev, const AbstractState& cur, const ICFGCycleWTO* cycle)
153{
154 // Base widens, writes trace[cycle_head], and returns fixpoint bool.
155 bool fixpoint = AbstractInterpretation::widenCycleState(prev, cur, cycle);
156
157 // Scatter the widened ValVars back to their def-sites so body nodes
158 // observe the widened values on the next iteration. Matches the
159 // pre-refactor semantics: scatter unconditionally, including at
160 // widening fixpoint (see the narrowing-starts-with-stale-body issue
161 // fixed by always writing widened state back).
162 const ICFGNode* cycle_head = cycle->head()->getICFGNode();
163 const AbstractState& next = abstractTrace[cycle_head];
164 for (const auto& [id, val] : next.getVarToVal())
165 updateAbsValue(svfir->getSVFVar(id), val, cycle_head);
166 return fixpoint;
167}
168
170 const AbstractState& prev, const AbstractState& cur, const ICFGCycleWTO* cycle)
171{
172 // Delegate to base. It returns true on the two non-scatter cases
173 // (narrowing disabled, or narrow fixpoint); we preserve the original
174 // "skip scatter at fixpoint" semantics by bailing early here.
175 bool fixpoint = AbstractInterpretation::narrowCycleState(prev, cur, cycle);
176 if (fixpoint)
177 return true;
178
179 // Non-fixpoint: base wrote the narrowed state to trace. Scatter the
180 // narrowed ValVars back to def-sites.
181 const ICFGNode* cycle_head = cycle->head()->getICFGNode();
182 const AbstractState& next = abstractTrace[cycle_head];
183 for (const auto& [id, val] : next.getVarToVal())
184 updateAbsValue(svfir->getSVFVar(id), val, cycle_head);
185 return false;
186}
187
188// =====================================================================
189// Shared SemiSparse/FullSparse state-access overrides. Both use the
190// established ValVar def-site reads and writes below.
191// =====================================================================
192
194 const ICFGNode* node, const AbstractState& state)
195{
196 // Only replace ObjVar state. ValVars live at their def-sites and
197 // must not be overwritten when the predecessor's state is merged in.
198 abstractTrace[node].updateAddrStateOnly(state);
199}
200
202 const AbstractState& src)
203{
204 // ValVars live at def-sites in semi-sparse mode; they don't flow
205 // through state merges. Iterate src's ObjVar (_addrToAbsVal) entries
206 // directly and join into dst, leaving dst's ValVar map untouched.
207 // _freedAddrs (used by the null-deref detector) also rides along
208 // ICFG edges — there is no SVFG-level encoding of free events.
209 for (const auto& [id, val] : src.getLocToVal())
210 {
212 if (dst.getLocToVal().count(id))
213 dst.load(addr).join_with(val);
214 else
215 dst.store(addr, val);
216 }
217 for (NodeID a : src.getFreedAddrs())
218 dst.addToFreedAddrs(a);
219}
220
222 const ValVar* var) const
223{
224 // const ValVars are all defined in global node
225 if (!var->getICFGNode())
226 {
227 return svfir->getICFG()->getGlobalICFGNode();
228 }
229 // for return value of callsite, use the ret-site as def-site
230 else if (SVFUtil::isa<CallICFGNode>(var->getICFGNode()) &&
232 {
234 ->getRetICFGNode();
235 }
236 // for other ValVars, use their def-site as the node to query abstract
237 // value.
238 else
239 {
240 return var->getICFGNode();
241 }
242}
243
245 const AbstractValue& val,
246 const ICFGNode* node)
247{
248 // Write to the var's def-site so getAbsValue stays consistent.
249 const ICFGNode* defNode = var->getICFGNode();
250 abstractTrace[defNode ? defNode : node][var->getId()] = val;
251}
252
254 const ValVar* var, const ICFGNode* node)
255{
256 // Read from the var's def-site (where updateAbsValue wrote it).
258}
259
261 const ICFGNode* node) const
262{
264}
item next
Definition cJSON.cpp:2224
cJSON * a
Definition cJSON.cpp:2560
newitem prev
Definition cJSON.cpp:2285
AbstractState & getAbsState(const ICFGNode *node)
virtual bool narrowCycleState(const AbstractState &prev, const AbstractState &cur, const ICFGCycleWTO *cycle)
virtual bool hasAbsValue(const ValVar *var, const ICFGNode *node) const
Side-effect-free existence check.
virtual AbstractState getFullCycleHeadState(const ICFGCycleWTO *cycle)
bool isBranchEdgeFeasible(const IntraCFGEdge *edge, AbstractState &as)
virtual bool widenCycleState(const AbstractState &prev, const AbstractState &cur, const ICFGCycleWTO *cycle)
bool applyBranchRefinement(const IntraCFGEdge *edge, AbstractState &as)
virtual bool mergeStatesFromPredecessors(const ICFGNode *node)
SVFIR * svfir
Data and helpers reachable from SparseAbstractInterpretation.
virtual const AbstractValue & getAbsValue(const ValVar *var, const ICFGNode *node)
bool hasAbsState(const ICFGNode *node)
Map< const ICFGNode *, AbstractState > abstractTrace
per-node trace; owned here
const AddrToAbsValMap & getLocToVal() const
get loc2val map
u32_t getIDFromAddr(u32_t addr) const
Return the internal index if addr is an address otherwise return the value of idx.
void store(u32_t addr, const AbstractValue &val)
const Set< NodeID > & getFreedAddrs() const
virtual AbstractValue & load(u32_t addr)
static u32_t getVirtualMemAddress(u32_t idx)
The physical address starts with 0x7f...... + idx.
void addToFreedAddrs(NodeID addr)
void join_with(const AbstractValue &other)
void joinStates(AbstractState &dst, const AbstractState &src, const NodeBS &objs)
bool mergeStatesFromPredecessors(const ICFGNode *node) override
void mergeFreedAddrs(AbstractState &dst, const AbstractState &src)
NodeID getId() const
Get ID.
Definition SVFValue.h:158
bool narrowCycleState(const AbstractState &prev, const AbstractState &cur, const ICFGCycleWTO *cycle) override
const AbstractValue & getAbsValue(const ValVar *var, const ICFGNode *node) override
AbstractState getFullCycleHeadState(const ICFGCycleWTO *cycle) override
void joinStates(AbstractState &dst, const AbstractState &src) override
bool widenCycleState(const AbstractState &prev, const AbstractState &cur, const ICFGCycleWTO *cycle) override
void updateAbsValue(const ValVar *var, const AbstractValue &val, const ICFGNode *node) override
bool hasAbsValue(const ValVar *var, const ICFGNode *node) const override
Side-effect-free existence check.
void updateAbsState(const ICFGNode *node, const AbstractState &state) override
const ICFGNode * getICFGNode(const ValVar *var) const
const IntraCFGEdge * branch
const ICFGNode * getICFGNode() const
const ICFGNode * getICFGNode() const
const WTONode< GraphT > * head() const
Return the head of the cycle.
Definition WTO.h:411
const NodeT * getICFGNode() const
Return the graph node.
Definition WTO.h:343
LLVM_NODISCARD bool isa(const Y &Val)
Definition Casting.h:241
LLVM_NODISCARD std::enable_if_t<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type > dyn_cast(const Y &Val)
Definition Casting.h:405
for isBitcode
Definition BasicTypes.h:70
WTOCycle< ICFG > ICFGCycleWTO
Definition ICFGWTO.h:49
u32_t NodeID
Definition GeneralType.h:76
std::unordered_set< Key, Hash, KeyEqual, Allocator > Set
Definition GeneralType.h:51
SparseBitVector NodeBS
Definition GeneralType.h:82
unsigned u32_t
Definition GeneralType.h:67