Static Value-Flow Analysis
Loading...
Searching...
No Matches
PAGBase.h
Go to the documentation of this file.
1//===- PAG.h -- PAG (Program Assignment Graph) -------------------------------//
2//
3// SVF: Static Value-Flow Analysis
4//
5// Copyright (C) <2013-2017> <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
23/*
24 * PAGBase.h
25 *
26 * Created on: Nov 1, 2013
27 * Author: Yulei Sui
28 */
29
30
31#ifndef PAGBASE_H_
32#define PAGBASE_H_
33
34#include "Graphs/GenericGraph.h"
37
38namespace SVF
39{
42
43class ICFGNode;
44class ObjTypeInfo;
45
46/*
47 * To be extended by PAG. Perhaps we should fold this into PAG in the future.
48 */
49class PAGBase : public GenericGraph<SVFVar, SVFStmt>
50{
51 friend class PAGBuilder;
52 friend class SymbolTableBuilder;
53 friend class GraphDBClient;
54
55public:
56
69
71 //{@
74
77
81
82private:
86
93
96
99
100 void destorySymTable();
101
102public:
104
105protected:
108 bool fromFile;
113
115 inline NodeID addNode(SVFVar* node)
116 {
117 assert(node && "cannot add a null node");
118 addGNode(node->getId(),node);
119 return node->getId();
120 }
121
122 bool addEdge(SVFVar* src, SVFVar* dst, SVFStmt* edge);
123
130 const ICFGNode* cs);
135 const SVFVar* op2);
136
137public:
138 PAGBase(bool buildFromFile)
139 : totalSymNum(0), fromFile(buildFromFile), nodeNumAfterPAGBuild(0), totalPTAPAGEdge(0), valVarNum(0), objVarNum(0),
140 maxStruct(nullptr), maxStSize(0)
141 {
142 }
143
144 virtual ~PAGBase();
145
146
148 inline bool isBuiltFromFile()
149 {
150 return fromFile;
151 }
152
154 // @{
155 static inline bool isBlkPtr(NodeID id)
156 {
157 return (id == BlkPtr);
158 }
159 static inline bool isNullPtr(NodeID id)
160 {
161 return (id == NullPtr);
162 }
163 static inline bool isBlkObj(NodeID id)
164 {
165 return (id == BlackHole);
166 }
167
168 static inline bool isNullOrBlkObj(NodeID id)
169 {
170 return isNullPtr(id) || isBlkObj(id);
171 }
172 static inline bool isConstantSym(NodeID id)
173 {
174 return (id == ConstantObj);
175 }
176 static inline bool isBlkObjOrConstantObj(NodeID id)
177 {
178 return (isBlkObj(id) || isConstantSym(id));
179 }
180
181 inline NodeID blkPtrSymID() const
182 {
183 return BlkPtr;
184 }
185
186 inline NodeID nullPtrSymID() const
187 {
188 return NullPtr;
189 }
190
191 inline NodeID constantSymID() const
192 {
193 return ConstantObj;
194 }
195
196 inline NodeID blackholeSymID() const
197 {
198 return BlackHole;
199 }
200
202
203 inline u32_t getTotalSymNum() const
204 {
205 return totalSymNum;
206 }
207 inline u32_t getMaxStructSize() const
208 {
209 return maxStSize;
210 }
211
212
214
216 {
217 return objTypeInfoMap;
218 }
219
221 {
222 return objTypeInfoMap;
223 }
224
226 {
227 return returnFunObjSymMap;
228 }
229
231 {
232 return varargFunObjSymMap;
233 }
234
236
238 {
239 IDToTypeInfoMapTy::const_iterator iter = objTypeInfoMap.find(id);
240 assert(iter!=objTypeInfoMap.end() && "obj type info not found");
241 return iter->second;
242 }
243
245 NodeID getReturnNode(const FunObjVar*func) const;
246
248 NodeID getVarargNode(const FunObjVar*func) const;
249
251 {
252 return blackholeSymID();
253 }
254 inline NodeID getConstantNode() const
255 {
256 return constantSymID();
257 }
258 inline NodeID getBlkPtr() const
259 {
260 return blkPtrSymID();
261 }
262 inline NodeID getNullPtr() const
263 {
264 return nullPtrSymID();
265 }
267
269
271
272 inline const SVFTypeSet& getSVFTypes() const
273 {
274 return svfTypes;
275 }
276
277 inline const SVFType* getSVFType(u32_t id) const
278 {
279 for(const SVFType* type : svfTypes)
280 {
281 if(type->getId() == id)
282 return type;
283 }
284 return nullptr;
285 }
286 inline const Set<const StInfo*>& getStInfos() const
287 {
288 return stInfos;
289 }
290
291
292 virtual APOffset getModulusOffset(const BaseObjVar* baseObj, const APOffset& apOffset);
294
295
296 const StInfo* getTypeInfo(const SVFType* T) const;
297 inline bool hasSVFTypeInfo(const SVFType* T)
298 {
299 return svfTypes.find(T) != svfTypes.end();
300 }
301
304
306
311 u32_t getFlattenedElemIdx(const SVFType* T, u32_t origId);
313 const SVFType* getFlatternedElemType(const SVFType* baseType, u32_t flatten_idx);
317 const SVFType* getOriginalElemType(const SVFType* baseType, u32_t origId) const;
319
321 void printFlattenFields(const SVFType* type);
322
323
325 {
327 }
329 {
331 }
332
333 inline u32_t getSVFVarNum() const
334 {
335 return nodeNum;
336 }
337 inline u32_t getSVFStmtNum() const
338 {
339 return edgeNum;
340 }
341 inline u32_t getPTAPAGEdgeNum() const
342 {
343 return totalPTAPAGEdge;
344 }
345
346 inline std::string getGraphName() const
347 {
348 return "PAG";
349 }
350
352
354 void dump(std::string name);
355
357 void view();
358
359
360
363
366
367 inline void addTypeInfo(const SVFType* ty)
368 {
369 bool inserted = svfTypes.insert(ty).second;
370 if(!inserted)
371 assert(false && "this type info has been added before");
372 }
373
374 inline void addStInfo(StInfo* stInfo)
375 {
376 stInfo->setStinfoId(stInfos.size());
377 stInfos.insert(stInfo);
378 }
379
380protected:
381
383 const std::vector<const SVFType*>& getFlattenFieldTypes(const SVFStructType *T);
384};
385
386}
387
388namespace SVF
389{
390
391/* !
392 * GenericGraphTraits specializations of PAG to be used for the generic graph algorithms.
393 * Provide graph traits for traversing from a PAG node using standard graph traversals.
394 */
395template<> struct GenericGraphTraits<SVF::SVFVar*> : public GenericGraphTraits<SVF::GenericNode<SVF::SVFVar,SVF::SVFStmt>* >
396{
397};
398
400template<> struct GenericGraphTraits<Inverse<SVF::SVFVar *> > : public GenericGraphTraits<Inverse<SVF::GenericNode<SVF::SVFVar,SVF::SVFStmt>* > >
401{
402};
403
404template<> struct GenericGraphTraits<SVF::PAGBase*> : public GenericGraphTraits<SVF::GenericGraph<SVF::SVFVar,SVF::SVFStmt>* >
405{
407};
408
409} // End namespace llvm
410#endif /* PAGBASE_H_ */
newitem type
Definition cJSON.cpp:2739
const char *const name
Definition cJSON.h:264
void addGNode(NodeID id, NodeType *node)
virtual ~PAGBase()
Definition IRGraph.cpp:58
friend class PAGBuilder
Definition PAGBase.h:51
const SVFType * getOriginalElemType(const SVFType *baseType, u32_t origId) const
Definition IRGraph.cpp:143
static bool isBlkObjOrConstantObj(NodeID id)
Definition PAGBase.h:176
SVFStmt * hasLabeledEdge(SVFVar *src, SVFVar *dst, SVFStmt::PEDGEK kind, const ICFGNode *cs)
Definition IRGraph.cpp:308
u32_t objVarNum
Definition PAGBase.h:112
const SVFTypeSet & getSVFTypes() const
Constant reader that won't change the state of the symbol table.
Definition PAGBase.h:272
void setNodeNumAfterPAGBuild(u32_t num)
Definition PAGBase.h:328
const SVFType * maxStruct
The struct type with the most fields.
Definition PAGBase.h:362
static bool isConstantSym(NodeID id)
Definition PAGBase.h:172
NodeID nullPtrSymID() const
Definition PAGBase.h:186
NodeID getVarargNode(const FunObjVar *func) const
getVarargNode - Return the unique node representing the variadic argument of a variadic function.
Definition IRGraph.cpp:71
IDToTypeInfoMapTy objTypeInfoMap
map a memory sym id to its obj
Definition PAGBase.h:85
static bool isBlkPtr(NodeID id)
special value
Definition PAGBase.h:155
NodeID getConstantNode() const
Definition PAGBase.h:254
NodeID getNullPtr() const
Definition PAGBase.h:262
SVFStmt::KindToSVFStmtMapTy KindToSVFStmtSetMap
PAG edge map containing all PAGEdges.
Definition PAGBase.h:106
u32_t getSVFVarNum() const
Definition PAGBase.h:333
void printFlattenFields(const SVFType *type)
Debug method.
Definition IRGraph.cpp:77
void addTypeInfo(const SVFType *ty)
Definition PAGBase.h:367
u32_t maxStSize
The number of fields in max_struct.
Definition PAGBase.h:365
u32_t getMaxStructSize() const
Definition PAGBase.h:207
FunObjVarToIDMapTy returnFunObjSymMap
return map
Definition PAGBase.h:83
void destorySymTable()
Definition IRGraph.cpp:40
NodeID getBlackHoleNode() const
Definition PAGBase.h:250
NodeID addNode(SVFVar *node)
Add a node into the graph.
Definition PAGBase.h:115
const ObjTypeInfo * createDummyObjTypeInfo(NodeID symId, const SVFType *type)
Definition IRGraph.cpp:194
void dump(std::string name)
Dump PAG.
Definition IRGraph.cpp:333
ObjTypeInfo * createObjTypeInfo(const SVFType *type)
Create an objectInfo based on LLVM type (value is null, and type could be null, representing a dummy ...
Definition IRGraph.cpp:248
bool fromFile
Whether the PAG is built according to user specified data from a txt file.
Definition PAGBase.h:108
u32_t valVarNum
Definition PAGBase.h:111
NodeID getBlkPtr() const
Definition PAGBase.h:258
u32_t getObjectNodeNum()
Definition IRGraph.cpp:360
SVFTypeSet svfTypes
Definition PAGBase.h:92
void dumpSymTable()
NodeID nodeNumAfterPAGBuild
initial node number after building PAG, excluding later added nodes, e.g., gepobj nodes
Definition PAGBase.h:109
NodeID getReturnNode(const FunObjVar *func) const
GetReturnNode - Return the unique node representing the return value of a function.
Definition IRGraph.cpp:64
NodeID blackholeSymID() const
Definition PAGBase.h:196
FunObjVarToIDMapTy & varargFunObjSyms()
Definition PAGBase.h:230
PAGBase(bool buildFromFile)
Definition PAGBase.h:138
OrderedMap< NodeID, ObjTypeInfo * > IDToTypeInfoMapTy
various maps defined
Definition PAGBase.h:73
ObjTypeInfo * getObjTypeInfo(NodeID id) const
Definition PAGBase.h:237
u32_t getFlattenedElemIdx(const SVFType *T, u32_t origId)
Flattened element idx of an array or struct by considering stride.
Definition IRGraph.cpp:148
const std::vector< const SVFType * > & getFlattenFieldTypes(const SVFStructType *T)
Return the flattened field type for struct type only.
Definition IRGraph.cpp:122
Set< const SVFStmt * > SVFStmtSet
Definition PAGBase.h:103
SVFStmt * hasEdge(SVFStmt *edge, SVFStmt::PEDGEK kind)
Definition IRGraph.cpp:319
friend class SymbolTableBuilder
Definition PAGBase.h:52
const Set< const StInfo * > & getStInfos() const
Definition PAGBase.h:286
OrderedMap< const FunObjVar *, NodeID > FunObjVarToIDMapTy
function to sym id map
Definition PAGBase.h:76
friend class GraphDBClient
Definition PAGBase.h:53
const SVFType * getFlatternedElemType(const SVFType *baseType, u32_t flatten_idx)
Return the type of a flattened element given a flattened index.
Definition IRGraph.cpp:127
u32_t totalPTAPAGEdge
Definition PAGBase.h:110
static bool isBlkObj(NodeID id)
Definition PAGBase.h:163
u32_t getPTAPAGEdgeNum() const
Definition PAGBase.h:341
const StInfo * getTypeInfo(const SVFType *T) const
Get struct info.
Definition IRGraph.cpp:259
std::string getGraphName() const
Return graph name.
Definition PAGBase.h:346
NodeID totalSymNum
total number of symbols
Definition PAGBase.h:98
SVFStmt::KindToSVFStmtMapTy KindToPTASVFStmtSetMap
PAG edge map containing only pointer-related edges, i.e., both LHS and RHS are of pointer type.
Definition PAGBase.h:107
SYMTYPE
Symbol types.
Definition PAGBase.h:59
IDToTypeInfoMapTy & idToObjTypeInfoMap()
Get different kinds of syms maps.
Definition PAGBase.h:215
NodeID constantSymID() const
Definition PAGBase.h:191
static bool isNullPtr(NodeID id)
Definition PAGBase.h:159
u32_t getNodeNumAfterPAGBuild() const
Definition PAGBase.h:324
virtual APOffset getModulusOffset(const BaseObjVar *baseObj, const APOffset &apOffset)
Given an offset from a Gep Instruction, return it modulus offset by considering memory layout.
Definition IRGraph.cpp:205
u32_t getSVFStmtNum() const
Definition PAGBase.h:337
Set< const SVFType * > SVFTypeSet
struct type to struct info map
Definition PAGBase.h:79
u32_t getNumOfFlattenElements(const SVFType *T)
Definition IRGraph.cpp:186
void addStInfo(StInfo *stInfo)
Definition PAGBase.h:374
bool addEdge(SVFVar *src, SVFVar *dst, SVFStmt *edge)
Add an edge into the graph.
Definition IRGraph.cpp:270
u32_t getValueNodeNum()
Definition IRGraph.cpp:347
u32_t getTotalSymNum() const
Statistics.
Definition PAGBase.h:203
FunObjVarToIDMapTy & retFunObjSyms()
Definition PAGBase.h:225
FunObjVarToIDMapTy varargFunObjSymMap
vararg map
Definition PAGBase.h:84
Set< const StInfo * > stInfos
(owned) All StInfo
Definition PAGBase.h:95
bool hasSVFTypeInfo(const SVFType *T)
Definition PAGBase.h:297
bool isBuiltFromFile()
Whether this PAG built from a txt file.
Definition PAGBase.h:148
const IDToTypeInfoMapTy & idToObjTypeInfoMap() const
Definition PAGBase.h:220
const SVFType * getSVFType(u32_t id) const
Definition PAGBase.h:277
static bool isNullOrBlkObj(NodeID id)
Check a decoded NodeID, not an AE virtual memory address.
Definition PAGBase.h:168
void view()
View graph from the debugger.
Definition IRGraph.cpp:341
NodeID blkPtrSymID() const
Definition PAGBase.h:181
SVFStmt * hasNonlabeledEdge(SVFVar *src, SVFVar *dst, SVFStmt::PEDGEK kind)
Definition IRGraph.cpp:285
PAGEdgeToSetMapTy KindToSVFStmtMapTy
NodeID getId() const
Get ID.
Definition SVFValue.h:158
void setStinfoId(u32_t id)
Definition SVFType.h:69
for isBitcode
Definition BasicTypes.h:70
std::map< Key, Value, Compare, Allocator > OrderedMap
Definition GeneralType.h:64
u32_t NodeID
Definition GeneralType.h:76
std::unordered_set< Key, Hash, KeyEqual, Allocator > Set
Definition GeneralType.h:51
s64_t APOffset
Definition GeneralType.h:80
SVFVar PAGNode
Definition PAGBase.h:40
unsigned u32_t
Definition GeneralType.h:67
SVFStmt PAGEdge
Definition PAGBase.h:41