ROSE 0.11.145.189
FunctionCall.h
1#ifndef ROSE_BinaryAnalysis_FunctionCall_H
2#define ROSE_BinaryAnalysis_FunctionCall_H
3#include <featureTests.h>
4#ifdef ROSE_ENABLE_BINARY_ANALYSIS
5
6#include <Rose/BinaryAnalysis/ControlFlow.h>
7
8class SgAsmFunction;
9
10namespace Rose {
11namespace BinaryAnalysis {
12
22public:
23
25 : vertex_filter(NULL), edge_filter(NULL)
26 {}
27
52 typedef boost::adjacency_list<boost::setS, /* out-edges of each vertex in std::list */
53 boost::vecS, /* store vertices in std::vector */
54 boost::bidirectionalS, /* call graph is directed */
55 boost::property<boost::vertex_name_t, SgAsmFunction*>
57
58
59 /**********************************************************************************************************************
60 * Filters
61 **********************************************************************************************************************/
62public:
63
69 public:
70 virtual ~VertexFilter() {}
71 virtual bool operator()(FunctionCall*, SgAsmFunction*) = 0;
72 };
73
78 class EdgeFilter {
79 public:
80 virtual ~EdgeFilter() {}
81 virtual bool operator()(FunctionCall*, SgAsmFunction *source, SgAsmFunction *target) = 0;
82 };
83
91 void set_vertex_filter(VertexFilter *filter) { vertex_filter = filter; }
92 VertexFilter *get_vertex_filter() const { return vertex_filter; }
101 void set_edge_filter(EdgeFilter *filter) { edge_filter = filter; }
102 EdgeFilter *get_edge_filter() const { return edge_filter; }
111 return filter && !(*filter)(this, func);
112 }
114 return is_vertex_filtered(func, vertex_filter);
115 }
124 return filter && !(*filter)(this, src, dst);
125 }
127 return is_edge_filtered(src, dst, edge_filter);
128 }
131protected:
132 VertexFilter *vertex_filter;
133 EdgeFilter *edge_filter;
134
135 /**********************************************************************************************************************
136 * Methods that modify the AST
137 **********************************************************************************************************************/
138public:
139
154 template<class FunctionCallGraph>
155 void cache_vertex_descriptors(const FunctionCallGraph&);
156
157 /**********************************************************************************************************************
158 * Graph construction methods
159 **********************************************************************************************************************/
160public:
161
173 template<class FunctionCallGraph, class ControlFlowGraph>
174 FunctionCallGraph build_cg_from_cfg(const ControlFlowGraph&);
175
176 template<class ControlFlowGraph, class FunctionCallGraph>
177 void build_cg_from_cfg(const ControlFlowGraph &cfg, FunctionCallGraph &cg/*out*/);
207 template<class FunctionCallGraph>
208 FunctionCallGraph build_cg_from_ast(SgNode *root);
209
210 template<class FunctionCallGraph>
211 void build_cg_from_ast(SgNode *root, FunctionCallGraph &cg/*out*/);
224 template<class FunctionCallGraph>
225 FunctionCallGraph copy(const FunctionCallGraph &src);
226 template<class FunctionCallGraph>
227 void copy(const FunctionCallGraph &src, FunctionCallGraph &dst/*out*/);
230};
231
232/******************************************************************************************************************************
233 * Function template definitions
234 ******************************************************************************************************************************/
235
236template<class FunctionCallGraph>
237void
238FunctionCall::cache_vertex_descriptors(const FunctionCallGraph &cg)
239{
240 typename boost::graph_traits<FunctionCallGraph>::vertex_iterator vi, vi_end;
241 for (boost::tie(vi, vi_end)=boost::vertices(cg); vi!=vi_end; ++vi) {
242 SgAsmFunction *func = get_ast_node(cg, *vi);
243 if (func && !is_vertex_filtered(func))
244 func->set_cachedVertex(*vi);
245 }
246}
247
248template<class ControlFlowGraph, class FunctionCallGraph>
249void
250FunctionCall::build_cg_from_cfg(const ControlFlowGraph &cfg, FunctionCallGraph &cg/*out*/)
251{
252 typedef typename boost::graph_traits<FunctionCallGraph>::vertex_descriptor CG_Vertex;
253 typedef typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor CFG_Vertex;
254 typedef std::map<SgAsmFunction*, CG_Vertex> FunctionVertexMap;
255
256 cg.clear();
257
258 /* Add CG vertices by collapsing CFG nodes that belong to a common function. */
259 FunctionVertexMap fv_map;
260 typename boost::graph_traits<const ControlFlowGraph>::vertex_iterator vi, vi_end;
261 for (boost::tie(vi, vi_end)=boost::vertices(cfg); vi!=vi_end; ++vi) {
262 SgAsmFunction *func = SageInterface::getEnclosingNode<SgAsmFunction>(get_ast_node(cfg, *vi));
263 if (!is_vertex_filtered(func)) {
264 typename FunctionVertexMap::iterator fi=fv_map.find(func);
265 if (func && fi==fv_map.end()) {
266 CG_Vertex v = boost::add_vertex(cg);
267 put_ast_node(cg, v, func);
268 fv_map[func] = v;
269 }
270 }
271 }
272
273 /* Add edges whose target is a function entry block. */
274 typename boost::graph_traits<const ControlFlowGraph>::edge_iterator ei, ei_end;
275 for (boost::tie(ei, ei_end)=boost::edges(cfg); ei!=ei_end; ++ei) {
276 CFG_Vertex cfg_a = boost::source(*ei, cfg);
277 CFG_Vertex cfg_b = boost::target(*ei, cfg);
278 SgAsmBlock *block_a = SageInterface::getEnclosingNode<SgAsmBlock>(get_ast_node(cfg, cfg_a), true/* inc. self */);
279 ASSERT_not_null(block_a);
280 SgAsmBlock *block_b = SageInterface::getEnclosingNode<SgAsmBlock>(get_ast_node(cfg, cfg_b), true/* inc. self */);
281 ASSERT_not_null(block_b);
282 SgAsmFunction *func_a = block_a->get_enclosingFunction();
283 SgAsmFunction *func_b = block_b->get_enclosingFunction();
284 if (func_a && func_b && block_b==func_b->get_entryBlock() && !is_edge_filtered(func_a, func_b)) {
285 typename FunctionVertexMap::iterator fi_a = fv_map.find(func_a);
286 if (fi_a!=fv_map.end()) {
287 typename FunctionVertexMap::iterator fi_b = fv_map.find(func_b);
288 if (fi_b!=fv_map.end())
289 boost::add_edge(fi_a->second, fi_b->second, cg);
290 }
291 }
292 }
293}
294
295template<class FunctionCallGraph, class ControlFlowGraph>
296FunctionCallGraph
297FunctionCall::build_cg_from_cfg(const ControlFlowGraph &cfg)
298{
299 FunctionCallGraph cg;
300 build_cg_from_cfg(cfg, cg);
301 return cg;
302}
303
304template<class FunctionCallGraph>
305void
306FunctionCall::build_cg_from_ast(SgNode *root, FunctionCallGraph &cg/*out*/)
307{
308 typedef typename boost::graph_traits<FunctionCallGraph>::vertex_descriptor Vertex;
309 typedef std::map<SgAsmFunction*, Vertex> FunctionVertexMap;
310 FunctionVertexMap fv_map;
311
312 cg.clear();
313
314 /* Visiter that adds a vertex for each unique function. */
315 struct VertexAdder: public AstSimpleProcessing {
316 FunctionCall *analyzer;
317 FunctionCallGraph &cg;
318 FunctionVertexMap &fv_map;
319 VertexAdder(FunctionCall *analyzer, FunctionCallGraph &cg, FunctionVertexMap &fv_map)
320 : analyzer(analyzer), cg(cg), fv_map(fv_map)
321 {}
322 void visit(SgNode *node) {
323 SgAsmFunction *func = isSgAsmFunction(node);
324 if (func && !analyzer->is_vertex_filtered(func)) {
325 Vertex vertex = boost::add_vertex(cg);
326 fv_map[func] = vertex;
327 put_ast_node(cg, vertex, func);
328 }
329 }
330 };
331
332 /* Visitor that adds edges for each vertex. Traversal should be over one function at a time. */
333 struct EdgeAdder: public AstSimpleProcessing {
334 FunctionCall *analyzer;
335 FunctionCallGraph &cg;
336 FunctionVertexMap &fv_map;
337 Vertex source_vertex;
338 EdgeAdder(FunctionCall *analyzer, FunctionCallGraph &cg, FunctionVertexMap &fv_map, Vertex source_vertex)
339 : analyzer(analyzer), cg(cg), fv_map(fv_map), source_vertex(source_vertex)
340 {}
341 SgAsmFunction *function_of(SgAsmBlock *block) {
342 return block ? block->get_enclosingFunction() : NULL;
343 }
344 void visit(SgNode *node) {
345 SgAsmBlock *block_a = isSgAsmBlock(node); /* the calling block */
346 SgAsmFunction *func_a = function_of(block_a); /* the calling function */
347 if (!func_a)
348 return;
349 const SgAsmIntegerValuePtrList &succs = block_a->get_successors();
350 for (SgAsmIntegerValuePtrList::const_iterator si=succs.begin(); si!=succs.end(); ++si) {
351 SgAsmFunction *func_b = isSgAsmFunction((*si)->get_baseNode()); // the called function
352 if (func_b == NULL) {
353 SgAsmBlock *block_b = isSgAsmBlock((*si)->get_baseNode()); /* the called block */
354 func_b = function_of(block_b); /* the called function */
355 if (func_b && func_b->get_entryVa() != block_b->get_address())
356 continue;
357 }
358 if (func_b && !analyzer->is_edge_filtered(func_a, func_b)) {
359 typename FunctionVertexMap::iterator fi_b = fv_map.find(func_b); /* find vertex for called function */
360 if (fi_b!=fv_map.end())
361 boost::add_edge(source_vertex, fi_b->second, cg);
362 }
363 }
364 }
365 };
366
367 VertexAdder(this, cg, fv_map).traverse(root, preorder);
368 typename boost::graph_traits<FunctionCallGraph>::vertex_iterator vi, vi_end;
369 for (boost::tie(vi, vi_end)=boost::vertices(cg); vi!=vi_end; ++vi) {
370 SgAsmFunction *source_func = get_ast_node(cg, *vi);
371 EdgeAdder(this, cg, fv_map, *vi).traverse(source_func, preorder);
372 }
373}
374
375template<class FunctionCallGraph>
376FunctionCallGraph
378{
379 FunctionCallGraph cg;
380 build_cg_from_ast(root, cg);
381 return cg;
382}
383
384template<class FunctionCallGraph>
385void
386FunctionCall::copy(const FunctionCallGraph &src, FunctionCallGraph &dst)
387{
388 typedef typename boost::graph_traits<FunctionCallGraph>::vertex_descriptor Vertex;
389 Vertex NO_VERTEX = boost::graph_traits<FunctionCallGraph>::null_vertex();
390
391 dst.clear();
392 std::vector<Vertex> src_to_dst(boost::num_vertices(src), NO_VERTEX);
393
394 typename boost::graph_traits<const FunctionCallGraph>::vertex_iterator vi, vi_end;
395 for (boost::tie(vi, vi_end)=boost::vertices(src); vi!=vi_end; ++vi) {
396 SgAsmFunction *func = get_ast_node(src, *vi);
397 if (!is_vertex_filtered(func)) {
398 src_to_dst[*vi] = boost::add_vertex(dst);
399 put_ast_node(dst, src_to_dst[*vi], func);
400 }
401 }
402
403 typename boost::graph_traits<const FunctionCallGraph>::edge_iterator ei, ei_end;
404 for (boost::tie(ei, ei_end)=boost::edges(src); ei!=ei_end; ++ei) {
405 if (NO_VERTEX!=src_to_dst[boost::source(*ei, src)] && NO_VERTEX!=src_to_dst[boost::target(*ei, src)]) {
406 SgAsmFunction *func1 = get_ast_node(src, boost::source(*ei, src));
407 SgAsmFunction *func2 = get_ast_node(src, boost::target(*ei, src));
408 if (!is_edge_filtered(func1, func2))
409 boost::add_edge(src_to_dst[boost::source(*ei, src)], src_to_dst[boost::target(*ei, src)], dst);
410 }
411 }
412}
413
414template<class FunctionCallGraph>
415FunctionCallGraph
416FunctionCall::copy(const FunctionCallGraph &src)
417{
418 FunctionCallGraph dst;
419 copy(src, dst);
420 return dst;
421}
422
423} // namespace
424} // namespace
425
426#endif
427#endif
Class for traversing the AST.
Binary function call analysis.
FunctionCallGraph copy(const FunctionCallGraph &src)
Copies a graph while filtering.
bool is_edge_filtered(SgAsmFunction *src, SgAsmFunction *dst, EdgeFilter *filter)
Determines if an edge is filtered out.
void set_vertex_filter(VertexFilter *filter)
Manipulate the vertex filter.
void cache_vertex_descriptors(const FunctionCallGraph &)
Cache vertex descriptors in AST.
void set_edge_filter(EdgeFilter *filter)
Manipulate the edge filter.
FunctionCallGraph build_cg_from_cfg(const ControlFlowGraph &)
Build a function call graph from a control flow graph.
bool is_vertex_filtered(SgAsmFunction *func, VertexFilter *filter)
Determines if a vertex is filtered out.
EdgeFilter * get_edge_filter() const
Manipulate the edge filter.
FunctionCallGraph build_cg_from_ast(SgNode *root)
Build a function call graph from an AST.
boost::adjacency_list< boost::setS, boost::vecS, boost::bidirectionalS, boost::property< boost::vertex_name_t, SgAsmFunction * > > Graph
The default function call graph type.
VertexFilter * get_vertex_filter() const
Manipulate the vertex filter.
bool is_edge_filtered(SgAsmFunction *src, SgAsmFunction *dst)
Determines if an edge is filtered out.
bool is_vertex_filtered(SgAsmFunction *func)
Determines if a vertex is filtered out.
Instruction basic block.
SgAsmIntegerValuePtrList const & get_successors() const
Property: Control flow successors.
SgAsmFunction * get_enclosingFunction() const
Returns the function that owns this block.
Represents a synthesized function.
rose_addr_t const & get_entryVa() const
Property: Primary entry address.
SgAsmBlock * get_entryBlock() const
Function entry basic block.
rose_addr_t const & get_address() const
Property: Starting virtual address.
This class represents the base class for all IR nodes within Sage III.
Sawyer::Container::Graph< V, E >::VertexValue get_ast_node(const Sawyer::Container::Graph< V, E > &cfg, size_t vertexId)
Return the AST node associated with a vertex.
void put_ast_node(Sawyer::Container::Graph< V, E > &cfg, size_t vertexId, AstNode *astNode)
Set the AST node associated with a vertex.
The ROSE library.