ROSE  0.11.51.0
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 
8 class SgAsmFunction;
9 
10 namespace Rose {
11 namespace BinaryAnalysis {
12 
21 class FunctionCall {
22 public:
23 
24  FunctionCall()
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*>
56  > Graph;
57 
58 
59  /**********************************************************************************************************************
60  * Filters
61  **********************************************************************************************************************/
62 public:
63 
68  class VertexFilter {
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  }
131 protected:
132  VertexFilter *vertex_filter;
133  EdgeFilter *edge_filter;
134 
135  /**********************************************************************************************************************
136  * Methods that modify the AST
137  **********************************************************************************************************************/
138 public:
139 
154  template<class FunctionCallGraph>
155  void cache_vertex_descriptors(const FunctionCallGraph&);
156 
157  /**********************************************************************************************************************
158  * Graph construction methods
159  **********************************************************************************************************************/
160 public:
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 
236 template<class FunctionCallGraph>
237 void
238 FunctionCall::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_cached_vertex(*vi);
245  }
246 }
247 
248 template<class ControlFlowGraph, class FunctionCallGraph>
249 void
250 FunctionCall::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_enclosing_function();
283  SgAsmFunction *func_b = block_b->get_enclosing_function();
284  if (func_a && func_b && block_b==func_b->get_entry_block() && !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 
295 template<class FunctionCallGraph, class ControlFlowGraph>
296 FunctionCallGraph
297 FunctionCall::build_cg_from_cfg(const ControlFlowGraph &cfg)
298 {
299  FunctionCallGraph cg;
300  build_cg_from_cfg(cfg, cg);
301  return cg;
302 }
303 
304 template<class FunctionCallGraph>
305 void
306 FunctionCall::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_enclosing_function() : 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_entry_va() != 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 
375 template<class FunctionCallGraph>
376 FunctionCallGraph
378 {
379  FunctionCallGraph cg;
380  build_cg_from_ast(root, cg);
381  return cg;
382 }
383 
384 template<class FunctionCallGraph>
385 void
386 FunctionCall::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 
414 template<class FunctionCallGraph>
415 FunctionCallGraph
416 FunctionCall::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
void put_ast_node(Sawyer::Container::Graph< V, E > &cfg, size_t vertexId, AstNode *astNode)
Set the AST node associated with a vertex.
Definition: ControlFlow.h:571
bool is_vertex_filtered(SgAsmFunction *func)
Determines if a vertex is filtered out.
Definition: FunctionCall.h:113
bool is_edge_filtered(SgAsmFunction *src, SgAsmFunction *dst, EdgeFilter *filter)
Determines if an edge is filtered out.
Definition: FunctionCall.h:123
Instruction basic block.
Class for traversing the AST.
bool is_vertex_filtered(SgAsmFunction *func, VertexFilter *filter)
Determines if a vertex is filtered out.
Definition: FunctionCall.h:110
SgAsmBlock * get_entry_block() const
Function entry basic block.
void set_vertex_filter(VertexFilter *filter)
Manipulate the vertex filter.
Definition: FunctionCall.h:91
Represents a synthesized function.
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.
Definition: ControlFlow.h:560
Main namespace for the ROSE library.
Binary function call analysis.
Definition: FunctionCall.h:21
boost::adjacency_list< boost::setS, boost::vecS, boost::bidirectionalS, boost::property< boost::vertex_name_t, SgAsmFunction * > > Graph
The default function call graph type.
Definition: FunctionCall.h:56
This class represents the base class for all IR nodes within Sage III.
Definition: Cxx_Grammar.h:9555
FunctionCallGraph copy(const FunctionCallGraph &src)
Copies a graph while filtering.
Definition: FunctionCall.h:416
const SgAsmIntegerValuePtrList & get_successors() const
Property: Control flow successors.
VertexFilter * get_vertex_filter() const
Manipulate the vertex filter.
Definition: FunctionCall.h:92
SgAsmFunction * get_enclosing_function() const
Returns the function that owns this block.
FunctionCallGraph build_cg_from_cfg(const ControlFlowGraph &)
Build a function call graph from a control flow graph.
Definition: FunctionCall.h:297
FunctionCallGraph build_cg_from_ast(SgNode *root)
Build a function call graph from an AST.
Definition: FunctionCall.h:377
EdgeFilter * get_edge_filter() const
Manipulate the edge filter.
Definition: FunctionCall.h:102
bool is_edge_filtered(SgAsmFunction *src, SgAsmFunction *dst)
Determines if an edge is filtered out.
Definition: FunctionCall.h:126
rose_addr_t get_address() const
Property: Starting virtual address.
void cache_vertex_descriptors(const FunctionCallGraph &)
Cache vertex descriptors in AST.
Definition: FunctionCall.h:238
void set_edge_filter(EdgeFilter *filter)
Manipulate the edge filter.
Definition: FunctionCall.h:101