[docs]classCDG(Analysis):""" Implements a control dependence graph. """
[docs]def__init__(self,cfg,start=None,no_construct=False):""" Constructor. :param cfg: The control flow graph upon which this control dependence graph will build :param start: The starting point to begin constructing the control dependence graph :param no_construct: Skip the construction step. Only used in unit-testing. """self._start=startifstartisnotNoneelseself.project.entryself._cfg=cfgself._ancestor=Noneself._semi=Noneself._post_dom:Optional[networkx.DiGraph]=Noneself._graph:Optional[networkx.DiGraph]=Noneself._normalized_cfg=Noneifnotno_construct:ifself._cfgisNone:# This leads to import cycles otherwise# pylint: disable=import-outside-toplevelfromangr.analyses.cfg.cfg_emulatedimportCFGEmulatedself._cfg=self.project.analyses[CFGEmulated].prep()()# FIXME: We should not use get_any_irsb in such a real setting...self._entry=self._cfg.model.get_any_node(self._start)self._construct()
## Properties#@propertydefgraph(self):returnself._graph## Public methods#
[docs]defget_post_dominators(self):""" Return the post-dom tree """returnself._post_dom
[docs]defget_dependants(self,run):""" Return a list of nodes that are control dependent on the given node in the control dependence graph """ifruninself._graph.nodes():returnlist(self._graph.successors(run))else:return[]
[docs]defget_guardians(self,run):""" Return a list of nodes on whom the specific node is control dependent in the control dependence graph """ifruninself._graph.nodes():returnlist(self._graph.predecessors(run))else:return[]
## Private methods#def_construct(self):""" Construct a control dependence graph. This implementation is based on figure 6 of paper An Efficient Method of Computing Static Single Assignment Form by Ron Cytron, etc. """ifnotself._cfg._model.ident.startswith("CFGEmulated"):raiseValueError("CDG is only supported by CFGEmulated.")self._acyclic_cfg=self._cfg.copy()# TODO: Cycle-removing is not needed - confirm it later# The CFG we use should be acyclic!# self._acyclic_cfg.remove_cycles()# Pre-process the acyclic CFGself._pre_process_cfg()# Construct post-dominator treeself._pd_construct()self._graph:networkx.DiGraph=networkx.DiGraph()# Construct the reversed dominance frontier mappingrdf=compute_dominance_frontier(self._normalized_cfg,self._post_dom)foryinself._cfg.graph.nodes():ifynotinrdf:continueforxinrdf[y]:self._graph.add_edge(x,y)# self._post_process()def_pre_process_cfg(self):""" Pre-process the acyclic CFG. - Change all FakeRet edges to normal edges when necessary (e.g. the normal/expected return edge does not exist) """for_,dst,datainself._acyclic_cfg.graph.edges(data=True):if"jumpkind"indataanddata["jumpkind"]=="Ijk_FakeRet":all_edges_to_dst=self._acyclic_cfg.graph.in_edges([dst],data=True)ifnotany((s,d)fors,d,dainall_edges_to_dstifda["jumpkind"]!="Ijk_FakeRet"):# All in edges are FakeRets# Change them to a normal edgefor_,_,data_inall_edges_to_dst:data_["jumpkind"]="Ijk_Boring"def_post_process(self):""" There are cases where a loop has two overlapping loop headers thanks to the way VEX is dealing with continuous instructions. As we were breaking the connection between the second loop header and its successor, we shall restore them in our CDG. """# TODO: Verify its correctnessloop_back_edges=self._cfg.get_loop_back_edges()forb1,b2inloop_back_edges:self._graph.add_edge(b1,b2)## Post-dominator tree related#def_pd_construct(self):pdoms=PostDominators(self._acyclic_cfg,self._entry,successors_func=self._pd_graph_successors)self._post_dom=pdoms.post_domself._pd_post_process(self._acyclic_cfg)# Create the normalized_cfg without the annoying ContainerNodesself._normalized_cfg=networkx.DiGraph()forsrc,dstinpdoms.prepared_graph.edges():self._normalized_cfg.add_edge(src.obj,dst.obj)@staticmethoddef_pd_graph_successors(graph,node):iftype(node)isTemporaryNode:# This is for testingsuccessors=graph.graph.successors(node)else:# Real CFGNode!successors=graph.model.get_successors(node)returnsuccessorsdef_pd_post_process(self,cfg):""" Take care of those loop headers/tails where we manually broke their connection to the next BBL """loop_back_edges=self._cfg.get_loop_back_edges()forb1,b2inloop_back_edges:# The edge between b1 and b2 is manually broken# The post dominator of b1 should be b2 (or not?)successors=list(self._pd_graph_successors(cfg,b1))iflen(successors)==0:ifb2inself._post_dom:self._post_dom.add_edge(b1,b2)else:_l.debug("%s is not in post dominator dict.",b2)