Miasm2
 All Classes Namespaces Files Functions Variables Typedefs Properties Macros
Public Member Functions | Static Public Member Functions | Private Member Functions | Static Private Member Functions | Private Attributes | List of all members
miasm2.analysis.depgraph.DependencyGraph Class Reference
+ Inheritance diagram for miasm2.analysis.depgraph.DependencyGraph:
+ Collaboration diagram for miasm2.analysis.depgraph.DependencyGraph:

Public Member Functions

def __init__
 
def step_counter
 
def current_step
 
def inc_step
 
def get
 
def get_from_depnodes
 
def get_from_end
 

Static Public Member Functions

def get_expr
 
def follow_expr
 

Private Member Functions

def _follow_exprs
 
def _follow_apply_cb
 
def _get_irs
 
def _get_affblock
 
def _direct_depnode_dependencies
 
def _resolve_intrablock_dep
 
def _get_previousblocks
 
def _compute_interblock_dep
 

Static Private Member Functions

def _follow_simp_expr
 
def _follow_nolabel
 

Private Attributes

 _ira
 
 _implicit
 
 _step_counter
 
 _current_step
 
 _cb_follow
 

Detailed Description

Implementation of a dependency graph

A dependency graph contains DependencyNode as nodes. The oriented edges
stand for a dependency.
The dependency graph is made of the lines of a group of IRblock
*explicitely* or *implicitely* involved in the equation of given element.

Definition at line 676 of file depgraph.py.

Constructor & Destructor Documentation

def miasm2.analysis.depgraph.DependencyGraph.__init__ (   self,
  ira,
  implicit = False,
  apply_simp = True,
  follow_mem = True,
  follow_call = True 
)
Create a DependencyGraph linked to @ira
The IRA graph must have been computed

@ira: IRAnalysis instance
@implicit: (optional) Imply implicit dependencies

Following arguments define filters used to generate dependencies
@apply_simp: (optional) Apply expr_simp
@follow_mem: (optional) Track memory syntactically
@follow_call: (optional) Track through "call"

Definition at line 687 of file depgraph.py.

688  follow_call=True):
689  """Create a DependencyGraph linked to @ira
690  The IRA graph must have been computed
691 
692  @ira: IRAnalysis instance
693  @implicit: (optional) Imply implicit dependencies
694 
695  Following arguments define filters used to generate dependencies
696  @apply_simp: (optional) Apply expr_simp
697  @follow_mem: (optional) Track memory syntactically
698  @follow_call: (optional) Track through "call"
699  """
700  # Init
701  self._ira = ira
702  self._implicit = implicit
703  self._step_counter = itertools.count()
704  self._current_step = next(self._step_counter)
705 
706  # The IRA graph must be computed
707  assert hasattr(self._ira, 'g')
708 
709  # Create callback filters. The order is relevant.
710  self._cb_follow = []
711  if apply_simp:
712  self._cb_follow.append(self._follow_simp_expr)
713  self._cb_follow.append(lambda exprs: self._follow_exprs(exprs,
714  follow_mem,
715  follow_call))
716  self._cb_follow.append(self._follow_nolabel)

Member Function Documentation

def miasm2.analysis.depgraph.DependencyGraph._compute_interblock_dep (   self,
  depnodes,
  heads 
)
private
Create a DependencyDict from @depnodes, and propagate
DependencyDicts through all blocs

Definition at line 900 of file depgraph.py.

901  def _compute_interblock_dep(self, depnodes, heads):
902  """Create a DependencyDict from @depnodes, and propagate
903  DependencyDicts through all blocs
904  """
905  # Create a DependencyDict which will only contain our depnodes
906  current_depdict = DependencyDict(list(depnodes)[0].label, [])
907  current_depdict.pending.update(depnodes)
908 
909  # Init the work list
910  done = {}
911  todo = deque([current_depdict])
912 
913  while todo:
914  depdict = todo.popleft()
915 
916  # Update the dependencydict until fixed point is reached
917  self._resolve_intrablock_dep(depdict)
918  self.inc_step()
919 
920  # Clean irrelevant path
921  depdict.filter_unmodifier_loops(self._implicit, self._ira.IRDst)
922 
923  # Avoid infinite loops
924  label = depdict.label
925  if depdict in done.get(label, []):
926  continue
927  done.setdefault(label, []).append(depdict)
928 
929  # No more dependencies
930  if len(depdict.pending) == 0:
931  yield depdict.copy()
932  continue
933 
934  # Has a predecessor ?
935  is_final = True
936 
937  # Propagate the DependencyDict to all parents
938  for label, irb_len in self._get_previousblocks(depdict.label):
939  is_final = False
940 
941  # Duplicate the DependencyDict
942  new_depdict = depdict.extend(label)
943 
944  if self._implicit:
945  # Implicit dependencies: IRDst will be link with heads
946  implicit_depnode = DependencyNode(label, self._ira.IRDst,
947  irb_len,
948  self.current_step,
949  modifier=False)
950 
951  # Create links between DependencyDict
952  for depnode_head in depdict.pending:
953  # Follow the head element in the parent
954  new_depnode = DependencyNode(label, depnode_head.element,
955  irb_len,
956  self.current_step)
957  # The new node has to be analysed
958  new_depdict.cache[depnode_head] = set([new_depnode])
959  new_depdict.pending.add(new_depnode)
960 
961  # Handle implicit dependencies
962  if self._implicit:
963  new_depdict.cache[depnode_head].add(implicit_depnode)
964  new_depdict.pending.add(implicit_depnode)
965 
966  # Manage the new element
967  todo.append(new_depdict)
968 
969  # Return the node if it's a final one, ie. it's a head (in graph
970  # or defined by caller)
971  if is_final or depdict.label in heads:
972  yield depdict.copy()

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

def miasm2.analysis.depgraph.DependencyGraph._direct_depnode_dependencies (   self,
  depnode 
)
private
Compute and return the dependencies involved by @depnode,
over the instruction @depnode.line_,.
Return a set of FollowExpr

Definition at line 820 of file depgraph.py.

821  def _direct_depnode_dependencies(self, depnode):
822  """Compute and return the dependencies involved by @depnode,
823  over the instruction @depnode.line_,.
824  Return a set of FollowExpr"""
825 
826  if isinstance(depnode.element, m2_expr.ExprInt):
827  # A constant does not have any dependency
828  output = set()
829 
830  elif depnode.line_nb == 0:
831  # Beginning of a block, inter-block resolving is not done here
832  output = set()
833 
834  else:
835  # Intra-block resolving
836  # Get dependencies
837  read = set()
838  modifier = False
839 
840  for affect in self._get_affblock(depnode):
841  if affect.dst == depnode.element:
842  elements = self._follow_apply_cb(affect.src)
843  read.update(elements)
844  modifier = True
845 
846  # If it's not a modifier affblock, reinject current element
847  if not modifier:
848  read = set([FollowExpr(True, depnode.element)])
849 
850  # Build output
851  output = FollowExpr.to_depnodes(read, depnode.label,
852  depnode.line_nb - 1, modifier,
853  self.current_step)
854  return output

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

def miasm2.analysis.depgraph.DependencyGraph._follow_apply_cb (   self,
  expr 
)
private
Apply callback functions to @expr
@expr : FollowExpr instance

Definition at line 797 of file depgraph.py.

798  def _follow_apply_cb(self, expr):
799  """Apply callback functions to @expr
800  @expr : FollowExpr instance"""
801  follow = set([expr])
802  nofollow = set()
803 
804  for callback in self._cb_follow:
805  follow, nofollow_tmp = callback(follow)
806  nofollow.update(nofollow_tmp)
807 
808  out = set(FollowExpr(True, expr) for expr in follow)
809  out.update(set(FollowExpr(False, expr) for expr in nofollow))
810  return out

+ Here is the caller graph for this function:

def miasm2.analysis.depgraph.DependencyGraph._follow_exprs (   cls,
  exprs,
  follow_mem = False,
  follow_call = False 
)
private
Extracts subnodes from exprs and returns followed/non followed
expressions according to @follow_mem/@follow_call

Definition at line 775 of file depgraph.py.

776  def _follow_exprs(cls, exprs, follow_mem=False, follow_call=False):
777  """Extracts subnodes from exprs and returns followed/non followed
778  expressions according to @follow_mem/@follow_call
779 
780  """
781  follow, nofollow = set(), set()
782  for expr in exprs:
783  expr.visit(lambda x: cls.get_expr(x, follow, nofollow),
784  lambda x: cls.follow_expr(x, follow, nofollow,
785  follow_mem, follow_call))
786  return follow, nofollow
def miasm2.analysis.depgraph.DependencyGraph._follow_nolabel (   exprs)
staticprivate
Do not follow labels

Definition at line 788 of file depgraph.py.

789  def _follow_nolabel(exprs):
790  """Do not follow labels"""
791  follow = set()
792  for expr in exprs:
793  if not expr_is_label(expr):
794  follow.add(expr)
795 
796  return follow, set()

+ Here is the call graph for this function:

def miasm2.analysis.depgraph.DependencyGraph._follow_simp_expr (   exprs)
staticprivate
Simplify expression so avoid tracking useless elements,
as: XOR EAX, EAX

Definition at line 733 of file depgraph.py.

734  def _follow_simp_expr(exprs):
735  """Simplify expression so avoid tracking useless elements,
736  as: XOR EAX, EAX
737  """
738  follow = set()
739  for expr in exprs:
740  follow.add(expr_simp(expr))
741  return follow, set()
def miasm2.analysis.depgraph.DependencyGraph._get_affblock (   self,
  depnode 
)
private
Return the list of ExprAff associtiated to @depnode.
LINE_NB must be > 0

Definition at line 815 of file depgraph.py.

816  def _get_affblock(self, depnode):
817  """Return the list of ExprAff associtiated to @depnode.
818  LINE_NB must be > 0"""
819  return self._get_irs(depnode.label)[depnode.line_nb - 1]

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

def miasm2.analysis.depgraph.DependencyGraph._get_irs (   self,
  label 
)
private

Definition at line 811 of file depgraph.py.

812  def _get_irs(self, label):
813  "Return the irs associated to @label"
814  return self._ira.blocs[label].irs

+ Here is the caller graph for this function:

def miasm2.analysis.depgraph.DependencyGraph._get_previousblocks (   self,
  label 
)
private
Return an iterator on predecessors blocks of @label, with their
lengths

Definition at line 892 of file depgraph.py.

893  def _get_previousblocks(self, label):
894  """Return an iterator on predecessors blocks of @label, with their
895  lengths"""
896  preds = self._ira.g.predecessors_iter(label)
897  for pred_label in preds:
898  length = len(self._get_irs(pred_label))
899  yield (pred_label, length)

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

def miasm2.analysis.depgraph.DependencyGraph._resolve_intrablock_dep (   self,
  depdict 
)
private
Resolve the dependencies of nodes in @depdict.pending inside
@depdict.label until a fixed point is reached.
@depdict: DependencyDict to update

Definition at line 855 of file depgraph.py.

856  def _resolve_intrablock_dep(self, depdict):
857  """Resolve the dependencies of nodes in @depdict.pending inside
858  @depdict.label until a fixed point is reached.
859  @depdict: DependencyDict to update"""
860 
861  # Prepare the work list
862  todo = set(depdict.pending)
863 
864  # Pending states will be handled
865  depdict.pending.clear()
866 
867  while todo:
868  depnode = todo.pop()
869  if isinstance(depnode.element, m2_expr.ExprInt):
870  # A constant does not have any dependency
871  continue
872 
873  if depdict.is_head(depnode):
874  depdict.pending.add(depnode)
875  # A head cannot have dependencies inside the current IRblock
876  continue
877 
878  # Find dependency of the current depnode
879  sub_depnodes = self._direct_depnode_dependencies(depnode)
880  depdict.cache[depnode] = FollowExpr.extract_depnodes(sub_depnodes)
881 
882  # Add to the worklist its dependencies
883  todo.update(FollowExpr.extract_depnodes(sub_depnodes,
884  only_follow=True))
885 
886  # Pending states will be overriden in cache
887  for depnode in depdict.pending:
888  try:
889  del depdict.cache[depnode]
890  except KeyError:
891  continue

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

def miasm2.analysis.depgraph.DependencyGraph.current_step (   self)

Definition at line 723 of file depgraph.py.

724  def current_step(self):
725  "Current value of iteration counter"
726  return self._current_step

+ Here is the caller graph for this function:

def miasm2.analysis.depgraph.DependencyGraph.follow_expr (   expr,
  follow,
  nofollow,
  follow_mem = False,
  follow_call = False 
)
static
Returns True if we must visit sub expressions.
@expr: expression to browse
@follow: set of nodes to follow
@nofollow: set of nodes not to follow
@follow_mem: force the visit of memory sub expressions
@follow_call: force the visit of call sub expressions

Definition at line 758 of file depgraph.py.

759  def follow_expr(expr, follow, nofollow, follow_mem=False, follow_call=False):
760  """Returns True if we must visit sub expressions.
761  @expr: expression to browse
762  @follow: set of nodes to follow
763  @nofollow: set of nodes not to follow
764  @follow_mem: force the visit of memory sub expressions
765  @follow_call: force the visit of call sub expressions
766  """
767  if not follow_mem and isinstance(expr, m2_expr.ExprMem):
768  nofollow.add(expr)
769  return False
770  if not follow_call and expr.is_function_call():
771  nofollow.add(expr)
772  return False
773  return True
def miasm2.analysis.depgraph.DependencyGraph.get (   self,
  label,
  elements,
  line_nb,
  heads 
)
Compute the dependencies of @elements at line number @line_nb in
the block named @label in the current IRA, before the execution of
this line. Dependency check stop if one of @heads is reached
@label: asm_label instance
@element: set of Expr instances
@line_nb: int
@heads: set of asm_label instances
Return an iterator on DiGraph(DependencyNode)

Definition at line 973 of file depgraph.py.

974  def get(self, label, elements, line_nb, heads):
975  """Compute the dependencies of @elements at line number @line_nb in
976  the block named @label in the current IRA, before the execution of
977  this line. Dependency check stop if one of @heads is reached
978  @label: asm_label instance
979  @element: set of Expr instances
980  @line_nb: int
981  @heads: set of asm_label instances
982  Return an iterator on DiGraph(DependencyNode)
983  """
984 
985  # Init the algorithm
986  input_depnodes = set()
987  for element in elements:
988  input_depnodes.add(DependencyNode(label, element, line_nb,
989  self.current_step))
990 
991  # Compute final depdicts
992  depdicts = self._compute_interblock_dep(input_depnodes, heads)
993 
994  # Unify solutions
995  unified = []
996  cls_res = DependencyResultImplicit if self._implicit else \
997  DependencyResult
998 
999  for final_depdict in depdicts:
1000  # Keep only relevant nodes
1001  final_depdict.clean_modifiers_in_cache(input_depnodes)
1002  final_depdict.filter_used_nodes(input_depnodes)
1003 
1004  # Remove duplicate solutions
1005  if final_depdict not in unified:
1006  unified.append(final_depdict)
1007 
1008  # Return solutions as DiGraph
1009  yield cls_res(self._ira, final_depdict, input_depnodes)

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

def miasm2.analysis.depgraph.DependencyGraph.get_expr (   expr,
  follow,
  nofollow 
)
static
Update @follow/@nofollow according to insteresting nodes
Returns same expression (non modifier visitor).

@expr: expression to handle
@follow: set of nodes to follow
@nofollow: set of nodes not to follow

Definition at line 743 of file depgraph.py.

744  def get_expr(expr, follow, nofollow):
745  """Update @follow/@nofollow according to insteresting nodes
746  Returns same expression (non modifier visitor).
747 
748  @expr: expression to handle
749  @follow: set of nodes to follow
750  @nofollow: set of nodes not to follow
751  """
752  if isinstance(expr, m2_expr.ExprId):
753  follow.add(expr)
754  elif isinstance(expr, m2_expr.ExprInt):
755  nofollow.add(expr)
756  return expr
def miasm2.analysis.depgraph.DependencyGraph.get_from_depnodes (   self,
  depnodes,
  heads 
)
Alias for the get() method. Use the attributes of @depnodes as
argument.
PRE: Labels and lines of depnodes have to be equals
@depnodes: set of DependencyNode instances
@heads: set of asm_label instances

Definition at line 1010 of file depgraph.py.

1011  def get_from_depnodes(self, depnodes, heads):
1012  """Alias for the get() method. Use the attributes of @depnodes as
1013  argument.
1014  PRE: Labels and lines of depnodes have to be equals
1015  @depnodes: set of DependencyNode instances
1016  @heads: set of asm_label instances
1017  """
1018  lead = list(depnodes)[0]
1019  elements = set(depnode.element for depnode in depnodes)
1020  return self.get(lead.label, elements, lead.line_nb, heads)

+ Here is the call graph for this function:

def miasm2.analysis.depgraph.DependencyGraph.get_from_end (   self,
  label,
  elements,
  heads 
)
Alias for the get() method. Consider that the dependency is asked at
the end of the block named @label.
@label: asm_label instance
@elements: set of Expr instances
@heads: set of asm_label instances

Definition at line 1021 of file depgraph.py.

1022  def get_from_end(self, label, elements, heads):
1023  """Alias for the get() method. Consider that the dependency is asked at
1024  the end of the block named @label.
1025  @label: asm_label instance
1026  @elements: set of Expr instances
1027  @heads: set of asm_label instances
1028  """
1029  return self.get(label, elements, len(self._get_irs(label)), heads)

+ Here is the call graph for this function:

def miasm2.analysis.depgraph.DependencyGraph.inc_step (   self)

Definition at line 727 of file depgraph.py.

728  def inc_step(self):
729  "Increment and return the current step"
730  self._current_step = next(self._step_counter)
731  return self._current_step

+ Here is the caller graph for this function:

def miasm2.analysis.depgraph.DependencyGraph.step_counter (   self)

Definition at line 718 of file depgraph.py.

719  def step_counter(self):
720  "Iteration counter"
721  return self._step_counter

Member Data Documentation

miasm2.analysis.depgraph.DependencyGraph._cb_follow
private

Definition at line 709 of file depgraph.py.

miasm2.analysis.depgraph.DependencyGraph._current_step
private

Definition at line 703 of file depgraph.py.

miasm2.analysis.depgraph.DependencyGraph._implicit
private

Definition at line 701 of file depgraph.py.

miasm2.analysis.depgraph.DependencyGraph._ira
private

Definition at line 700 of file depgraph.py.

miasm2.analysis.depgraph.DependencyGraph._step_counter
private

Definition at line 702 of file depgraph.py.


The documentation for this class was generated from the following file: