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