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