Merge pull request #82 from commial/feature-depgraph

Feature: dependency graphs

5 files changed, 1431 insertions, 1 deletions

diff --git a/example/ida/depgraph.py b/example/ida/depgraph.py
new file mode 100644
index 00000000..65a3c88f
--- /dev/null
+++ b/example/ida/depgraph.py
@@ -0,0 +1,201 @@
+import sys
+
+from idaapi import GraphViewer
+from miasm2.core.bin_stream_ida import bin_stream_ida
+from miasm2.core.asmbloc import *
+from miasm2.expression.simplifications import expr_simp
+from miasm2.analysis.machine import Machine
+from miasm2.analysis.depgraph import DependencyGraph, DependencyGraph_NoMemory
+
+from utils import guess_machine
+
+
+class depGraphSettingsForm(Form):
+
+    def __init__(self, ira):
+
+        self.ira = ira
+        self.address = ScreenEA()
+        cur_bloc = list(ira.getby_offset(self.address))[0]
+        for line_nb, l in enumerate(cur_bloc.lines):
+            if l.offset == self.address:
+                break
+        cur_label = str(cur_bloc.label)
+        labels = sorted(map(str, ira.blocs.keys()))
+        regs = sorted(ir_arch.arch.regs.all_regs_ids_byname.keys())
+        reg_default = regs[0]
+        for i in xrange(10):
+            opnd = GetOpnd(self.address, i).upper()
+            if opnd in regs:
+                reg_default = opnd
+                break
+
+        Form.__init__(self,
+r"""BUTTON YES* Launch
+BUTTON CANCEL NONE
+Dependency Graph Settings
+
+Track the element:
+<Before the line:{rBeforeLine}>
+<After the line:{rAfterLine}>
+<At the end of the basic block:{rEndBlock}>{cMode}>
+
+<Target basic block:{cbBBL}>
+<Register to track:{cbReg}>
+<Line number:{iLineNb}>
+
+Method to use:
+<Best effort:{rBest}>
+<No memory (sound & complete):{rNoMem}>{cMethod}>
+
+<Highlight color:{cColor}>
+""", {
+            'cbReg': Form.DropdownListControl(
+                    items=regs,
+                    readonly=False,
+                    selval=reg_default),
+            'cMode': Form.RadGroupControl(("rBeforeLine", "rAfterLine",
+                                           "rEndBlock")),
+            'cMethod': Form.RadGroupControl(("rBest", "rNoMem")),
+            'iLineNb': Form.NumericInput(tp=Form.FT_RAWHEX,
+                                         value=line_nb),
+            'cbBBL': Form.DropdownListControl(
+                    items=labels,
+                    readonly=False,
+                    selval=cur_label),
+            'cColor': Form.ColorInput(value=0xc0c020),
+        })
+
+        self.Compile()
+
+    @property
+    def label(self):
+        value = self.cbBBL.value
+        for real_label in self.ira.blocs:
+            if str(real_label) == value:
+                return real_label
+        raise ValueError("Bad label")
+
+    @property
+    def line_nb(self):
+        value = self.iLineNb.value
+        mode = self.cMode.value
+        if mode == 0:
+            return value
+        elif mode == 1:
+            return value + 1
+        else:
+            return len(self.ira.blocs[self.label].irs)
+
+    @property
+    def elements(self):
+        value = self.cbReg.value
+        return set([ir_arch.arch.regs.all_regs_ids_byname[value]])
+
+    @property
+    def method(self):
+        value = self.cMethod.value
+        if value == 0:
+            return DependencyGraph
+        elif value == 1:
+            return DependencyGraph_NoMemory
+        else:
+            raise ValueError("Unknown method")
+
+    @property
+    def color(self):
+        return self.cColor.value
+
+
+# Init
+machine = guess_machine()
+mn, dis_engine, ira = machine.mn, machine.dis_engine, machine.ira
+
+bs = bin_stream_ida()
+mdis = dis_engine(bs, dont_dis_nulstart_bloc=True)
+ir_arch = ira(mdis.symbol_pool)
+
+# Populate symbols with ida names
+for ad, name in Names():
+    if name is None:
+        continue
+    mdis.symbol_pool.add_label(name, ad)
+
+# Get the current function
+addr = ScreenEA()
+func = idaapi.get_func(addr)
+blocs = mdis.dis_multibloc(func.startEA)
+
+# Generate IR
+for bloc in blocs:
+    ir_arch.add_bloc(bloc)
+
+# Simplify affectations
+for irb in ir_arch.blocs.values():
+    for irs in irb.irs:
+        for i, e in enumerate(irs):
+            e.dst, e.src = expr_simp(e.dst), expr_simp(e.src)
+
+# Build the IRA Graph
+ir_arch.gen_graph()
+
+# Get settings
+settings = depGraphSettingsForm(ir_arch)
+settings.Execute()
+
+# Get dependency graphs
+dg = (settings.method)(ir_arch)
+graphs = dg.get(settings.label, settings.elements, settings.line_nb,
+                set([ir_arch.symbol_pool.getby_offset(func.startEA)]))
+
+# Display the result
+comments = {}
+sol_nb = 0
+
+def clean_lines():
+    "Remove previous comments"
+    global comments
+    for offset in comments:
+        SetColor(offset, CIC_ITEM, 0xffffff)
+        MakeComm(offset, "")
+    comments = {}
+
+def treat_element():
+    "Display an element"
+    global graphs, comments, sol_nb, settings
+
+    try:
+        graph = graphs.next()
+    except StopIteration:
+        comments = {}
+        print "Done: %d solutions" % (sol_nb)
+        return
+
+    sol_nb += 1
+    print "Get graph number %02d" % sol_nb
+    filename = "/tmp/solution_0x%08x_%02d.dot" % (addr, sol_nb)
+    print "Dump the graph to %s" % filename
+    open(filename, "w").write(graph.graph.dot())
+
+    for node in graph.relevant_nodes:
+        try:
+            offset = ir_arch.blocs[node.label].lines[node.line_nb].offset
+        except IndexError:
+            print "Unable to highlight %s" % node
+            continue
+        comments[offset] = comments.get(offset, []) + [node.element]
+        SetColor(offset, CIC_ITEM, settings.color)
+
+    print "Possible value: %s" % graph.emul().values()[0]
+
+    for offset, elements in comments.iteritems():
+        MakeComm(offset, ", ".join(map(str, elements)))
+
+def next_element():
+    "Display the next element"
+    clean_lines()
+    treat_element()
+
+# Register and launch
+idaapi.add_hotkey("Shift-N", next_element)
+treat_element()
diff --git a/miasm2/analysis/depgraph.py b/miasm2/analysis/depgraph.py
new file mode 100644
index 00000000..06b5b8b6
--- /dev/null
+++ b/miasm2/analysis/depgraph.py
@@ -0,0 +1,608 @@
+"""Provide dependency graph"""
+import itertools
+import miasm2.expression.expression as m2_expr
+from miasm2.core.graph import DiGraph
+from miasm2.core.asmbloc import asm_label
+from miasm2.expression.simplifications import expr_simp
+from miasm2.ir.symbexec import symbexec
+from miasm2.ir.ir import irbloc
+
+
+class DependencyNode(object):
+    """Node elements of a DependencyGraph
+
+    A dependency node stands for the dependency on the @element at line number
+    @line_nb in the IRblock named @label, *before* the evaluation of this
+    line.
+    """
+
+    def __init__(self, label, element, line_nb, modifier=False):
+        """Create a dependency node with:
+        @label: asm_label instance
+        @element: Expr instance
+        @line_nb: int
+        @modifier: bool
+        """
+        self._label = label
+        self._element = element
+        self._line_nb = line_nb
+        self._modifier = modifier
+        self._hash = hash((self._label, self._element, self._line_nb))
+
+    def __hash__(self):
+        return self._hash
+
+    def __eq__(self, depnode):
+        if not isinstance(depnode, self.__class__):
+            return False
+        return (self.label == depnode.label and
+                self.element == depnode.element and
+                self.line_nb == depnode.line_nb)
+
+    def __cmp__(self, node):
+        if not isinstance(node, self.__class__):
+            raise ValueError("Compare error between %s, %s" % (self.__class__,
+                                                               node.__class__))
+        return cmp((self.label, self.element, self.line_nb),
+                   (node.label, node.element, node.line_nb))
+
+    def __str__(self):
+        return "<%s %s %s %s M:%s>"%(self.__class__.__name__,
+                                     self.label.name, self.element,
+                                     self.line_nb, self.modifier)
+
+    def __repr__(self):
+        return self.__str__()
+
+    @property
+    def label(self):
+        "Name of the current IRBlock"
+        return self._label
+
+    @property
+    def element(self):
+        "Current tracked Expr"
+        return self._element
+
+    @property
+    def line_nb(self):
+        "Line in the current IRBlock"
+        return self._line_nb
+
+    @property
+    def modifier(self):
+        """Evaluating the current line involves a modification of tracked
+        dependencies"""
+        return self._modifier
+
+    @modifier.setter
+    def modifier(self, value):
+        if not isinstance(value, bool):
+            raise ValueError("Modifier must be a boolean")
+        self._modifier = value
+
+
+class DependencyDict(object):
+    """Internal structure for the DependencyGraph algorithm"""
+
+    def __init__(self, label, history):
+        """Create a DependencyDict
+        @label: asm_label, current IRblock label
+        @history: list of DependencyDict
+        """
+        self._label = label
+        self._history = history
+        self._pending = set()
+
+        # DepNode -> set(DepNode)
+        self._cache = {}
+
+    def __eq__(self, depdict):
+        if not isinstance(depdict, self.__class__):
+            return False
+        return (self._label == depdict.label and
+                self._cache == depdict.cache and
+                self._pending == depdict.pending)
+
+    def __cmp__(self, depdict):
+        if not isinstance(depdict, self.__class__):
+            raise ValueError("Compare error %s != %s" % (self.__class__,
+                                                         depdict.__class__))
+        return cmp((self._label, self._cache, self._pending),
+                   (depdict.label, depdict.cache, depdict.pending))
+
+    def is_head(self, depnode):
+        """Return True iff @depnode is at the head of the current block
+        @depnode: DependencyNode instance"""
+        return (self.label == depnode.label and
+                depnode.line_nb == 0)
+
+    def copy(self):
+        "Return a copy of itself"
+
+        # Initialize
+        new_history = list(self.history)
+        depdict = DependencyDict(self.label, new_history)
+
+        # Copy values
+        for key, values in self.cache.iteritems():
+            depdict.cache[key] = set(values)
+        depdict.pending.update(self.pending)
+
+        return depdict
+
+    def extend(self, label):
+        """Return a copy of itself, with itself in history and pending clean
+        @label: asm_label instance for the new DependencyDict's label
+        """
+        depdict = DependencyDict(label, list(self.history) + [self])
+        for key, values in self.cache.iteritems():
+            depdict.cache[key] = set(values)
+        return depdict
+
+    def heads(self):
+        """Return an iterator on the list of heads as defined in 'is_head'"""
+        for key in self.cache:
+            if self.is_head(key):
+                yield key
+
+    @property
+    def label(self):
+        "Label of the current block"
+        return self._label
+
+    @property
+    def history(self):
+        """List of DependencyDict needed to reach the current DependencyDict
+        The first is the oldest"""
+        return self._history
+
+    @property
+    def cache(self):
+        "Dictionnary of DependencyNode and their dependencies"
+        return self._cache
+
+    @property
+    def pending(self):
+        """Dictionnary of DependencyNode and their dependencies, waiting for
+        resolution"""
+        return self._pending
+
+    def _get_modifiers_in_cache(self, depnode, force=False):
+        """Recursively find nodes in the path of @depnode which are modifiers.
+        Update the internal cache
+        If @depnode is already managed (ie. in @depnode_queued), abort"""
+
+        # Base case
+        if depnode not in self._cache:
+            # Constant does not have any dependencies
+            return [depnode] if depnode.modifier else []
+
+        if depnode.modifier and not force:
+            return [depnode]
+
+        # Recursion
+        dependencies = self._cache[depnode]
+
+        out = set()
+        ## Launch on each depnodes
+        parallels = []
+        for depnode in dependencies:
+            parallels.append(self._get_modifiers_in_cache(depnode))
+
+        if parallels:
+            for parallel in itertools.product(*parallels):
+                out.update(parallel)
+
+        return out
+
+    def clean_modifiers_in_cache(self):
+        """Remove intermediary states (non modifier depnodes) in the internal
+        cache values"""
+
+        cache_out = {}
+        for depnode in self._cache.keys():
+            cache_out[depnode] = self._get_modifiers_in_cache(depnode,
+                                                              force=True)
+        self._cache = cache_out
+
+    def _build_depGraph(self, depnode):
+        """Recursively build the final list of DiGraph, and clean up unmodifier
+        nodes
+        @depnode: starting node
+        """
+
+        if depnode not in self._cache or \
+                not self._cache[depnode]:
+            ## There is no dependency
+            graph = DiGraph()
+            graph.add_node(depnode)
+            return graph
+
+        # Recursion
+        dependencies = list(self._cache[depnode])
+
+        graphs = []
+        for sub_depnode in dependencies:
+            graphs.append(self._build_depGraph(sub_depnode))
+
+        # head(graphs[i]) == dependencies[i]
+        graph = DiGraph()
+        graph.add_node(depnode)
+        for head in dependencies:
+            graph.add_uniq_edge(head, depnode)
+
+        for subgraphs in itertools.product(graphs):
+            for sourcegraph in subgraphs:
+                for node in sourcegraph.nodes():
+                    graph.add_node(node)
+                for edge in sourcegraph.edges():
+                    graph.add_uniq_edge(*edge)
+
+        # Update the running queue
+        return graph
+
+    def as_graph(self, starting_nodes):
+        """Return a DiGraph corresponding to computed dependencies, with
+        @starting_nodes as leafs
+        @starting_nodes: set of DependencyNode instance
+        """
+
+        # Build subgraph for each starting_node
+        subgraphs = []
+        for starting_node in starting_nodes:
+            subgraphs.append(self._build_depGraph(starting_node))
+
+        # Merge subgraphs into a final DiGraph
+        graph = DiGraph()
+        for sourcegraph in subgraphs:
+            for node in sourcegraph.nodes():
+                graph.add_node(node)
+            for edge in sourcegraph.edges():
+                graph.add_uniq_edge(*edge)
+        return graph
+
+    def filter_used_nodes(self, node_heads):
+        """Keep only depnodes which are in the path of @node_heads in the
+        internal cache
+        @node_heads: set of DependencyNode instance
+        """
+        # Init
+        todo = set(node_heads)
+        used_nodes = set()
+
+        # Map
+        while todo:
+            node = todo.pop()
+            used_nodes.add(node)
+            if not node in self._cache:
+                continue
+            for sub_node in self._cache[node]:
+                todo.add(sub_node)
+
+        # Remove unused elements
+        for key in list(self._cache.keys()):
+            if key not in used_nodes:
+                del self._cache[key]
+
+
+class DependencyResult(object):
+    """Container and methods for DependencyGraph results"""
+
+    def __init__(self, ira, final_depdict, input_depnodes):
+        """Instance a DependencyResult
+        @ira: IRAnalysis instance
+        @final_depdict: DependencyDict instance
+        @input_depnodes: set of DependencyNode instance
+        """
+        # Store arguments
+        self._ira = ira
+        self._depdict = final_depdict
+        self._input_depnodes = input_depnodes
+
+        # Init lazy elements
+        self._graph = None
+        self._has_loop = None
+
+    @property
+    def graph(self):
+        "Lazy"
+        if self._graph is None:
+            self._graph = self._depdict.as_graph(self._input_depnodes)
+        return self._graph
+
+    @property
+    def history(self):
+        return list(self._depdict.history) + [self._depdict]
+
+    @property
+    def unresolved(self):
+        return set(self._depdict.pending)
+
+    @property
+    def relevant_nodes(self):
+        output = set()
+        for depnodes in self._depdict.cache.values():
+            output.update(depnodes)
+        return output
+
+    @property
+    def relevant_labels(self):
+        # Get used labels
+        used_labels = set([depnode.label for depnode in self.relevant_nodes])
+
+        # Keep history order
+        output = []
+        for label in [depdict.label for depdict in self.history]:
+            if label not in output and label in used_labels:
+                output.append(label)
+
+        return output
+
+    @property
+    def input(self):
+        return self._input_depnodes
+
+    def emul(self):
+        """Symbolic execution of relevant nodes according to the history
+        Return the values of input nodes' elements
+
+        /!\ The emulation is not safe if there is a loop in the relevant labels
+        """
+        # Init
+        new_ira = (self._ira.__class__)()
+        lines = self.relevant_nodes
+        affects = []
+
+        # Build a single affectation block according to history
+        for label in self.relevant_labels[::-1]:
+            affected_lines = [line.line_nb for line in lines
+                              if line.label == label]
+            irs = self._ira.blocs[label].irs
+            for line_nb in sorted(affected_lines):
+                affects.append(irs[line_nb])
+
+        # Eval the block
+        temp_label = asm_label("Temp")
+        sb = symbexec(new_ira, new_ira.arch.regs.regs_init)
+        sb.emulbloc(irbloc(temp_label, affects))
+
+        # Return only inputs values (others could be wrongs)
+        return {depnode.element: sb.symbols[depnode.element]
+                for depnode in self.input}
+
+
+class DependencyGraph(object):
+    """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* involved in the equation of given element.
+    """
+
+    def __init__(self, ira):
+        """Create a DependencyGraph linked to @ira
+        @ira: IRAnalysis instance
+        """
+        # Init
+        self._ira = ira
+
+        # The IRA graph must be computed
+        self._ira.gen_graph()
+
+    def _get_irs(self, label):
+        "Return the irs associated to @label"
+        return self._ira.blocs[label].irs
+
+    def _get_affblock(self, depnode):
+        """Return the list of ExprAff associtiated to @depnode.
+        LINE_NB must be > 0"""
+        return self._get_irs(depnode.label)[depnode.line_nb - 1]
+
+    def _resolve_depNode(self, depnode):
+        """Compute and return the dependencies involved by @depnode"""
+
+        if isinstance(depnode.element, m2_expr.ExprInt):
+            # A constant does not have any dependency
+            output = set()
+
+        elif depnode.line_nb == 0:
+            # Beginning of a block, inter-block resolving is not done here
+            output = set()
+
+        else:
+            # Intra-block resolving
+            ## Get dependencies
+            read = set()
+            modifier = False
+
+            for affect in self._get_affblock(depnode):
+                if affect.dst == depnode.element:
+                    ### Avoid tracking useless elements, as XOR EAX, EAX
+                    src = expr_simp(affect.src)
+
+                    read.update(src.get_r(mem_read=True, cst_read=True))
+                    modifier = True
+
+            ## If it's not a modifier affblock, reinject current element
+            if not modifier:
+                read = set([depnode.element])
+
+            ## Build output
+            dependencies = set()
+            for element in read:
+                dependencies.add(DependencyNode(depnode.label,
+                                                element,
+                                                depnode.line_nb - 1,
+                                                modifier=modifier))
+            output = dependencies
+
+        return output
+
+    def _updateDependencyDict(self, depdict):
+        """Update DependencyDict until a fixed point is reached
+        @depdict: DependencyDict to update"""
+
+        # Prepare the work list
+        todo = set(depdict.pending)
+
+        # Pending states will be handled
+        depdict.pending.clear()
+
+        while todo:
+            depnode = todo.pop()
+            if isinstance(depnode.element, m2_expr.ExprInt):
+                # A constant does not have any dependency
+                continue
+
+            if depdict.is_head(depnode):
+                depdict.pending.add(depnode)
+                # A head cannot have dependencies inside the current IRblock
+                continue
+
+            # Find dependency of the current depnode
+            sub_depnodes = self._resolve_depNode(depnode)
+            depdict.cache[depnode] = sub_depnodes
+
+            # Add to the worklist its dependencies
+            todo.update(sub_depnodes)
+
+        # Pending states will be override in cache
+        for depnode in depdict.pending:
+            try:
+                del depdict.cache[depnode]
+            except KeyError:
+                continue
+
+    def _get_previousblocks(self, label):
+        """Return an iterator on predecessors blocks of @label, with their
+        lengths"""
+        preds = self._ira.g.predecessors_iter(label)
+        for pred_label in preds:
+            length = len(self._get_irs(pred_label))
+            yield (pred_label, length)
+
+    def _processInterBloc(self, depnodes, heads):
+        """Create a DependencyDict from @depnodes, and propagate DependencyDicts
+        through all blocs
+        """
+        # Create an DependencyDict which will only contain our depnodes
+        current_depdict = DependencyDict(list(depnodes)[0].label, [])
+        current_depdict.pending.update(depnodes)
+
+        # Init the work list
+        done = []
+        todo = [current_depdict]
+
+        while todo:
+            depdict = todo.pop()
+
+            # Update the dependencydict until fixed point is reached
+            self._updateDependencyDict(depdict)
+
+            # Avoid infinite loops
+            if depdict in done:
+                continue
+            done.append(depdict)
+
+            # No more dependencies
+            if len(depdict.pending) == 0:
+                yield depdict
+                continue
+
+            # Propagate the DependencyDict to all parents
+            for label, irb_len in self._get_previousblocks(depdict.label):
+
+                ## Duplicate the DependencyDict
+                new_depdict = depdict.extend(label)
+
+                ## Create links between DependencyDict
+                for depnode_head in depdict.pending:
+                    ### Follow the head element in the parent
+                    new_depnode = DependencyNode(label, depnode_head.element,
+                                                 irb_len)
+                    ### The new node has to be computed in _updateDependencyDict
+                    new_depdict.cache[depnode_head] = set([new_depnode])
+                    new_depdict.pending.add(new_depnode)
+
+                ## Manage the new element
+                todo.append(new_depdict)
+
+            # Return the node if it's a final one, ie. it's a head
+            if depdict.label in heads:
+                yield depdict.copy()
+
+    def 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)
+        """
+
+        # Init the algorithm
+        input_depnodes = set()
+        for element in elements:
+            input_depnodes.add(DependencyNode(label, element, line_nb))
+
+        # Compute final depdicts
+        depdicts = self._processInterBloc(input_depnodes, heads)
+
+        # Unify solutions
+        unified = []
+        for final_depdict in depdicts:
+            ## Keep only relevant nodes
+            final_depdict.clean_modifiers_in_cache()
+            final_depdict.filter_used_nodes(input_depnodes)
+
+            ## Remove duplicate solutions
+            if final_depdict not in unified:
+                unified.append(final_depdict)
+                ### Return solutions as DiGraph
+                yield DependencyResult(self._ira, final_depdict, input_depnodes)
+
+    def get_fromDepNodes(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
+        """
+        lead = list(depnodes)[0]
+        elements = set([depnode.element for depnode in depnodes])
+        return self.get(lead.label, elements, lead.line_nb, heads)
+
+    def get_fromEnd(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
+        """
+        return self.get(label, elements, len(self._get_irs(label)), heads)
+
+
+class DependencyGraph_NoMemory(DependencyGraph):
+    """Dependency graph without memory tracking.
+
+    That way, the output has following properties:
+    - Only explicit dependencies are followed
+    - Soundness: all results are corrects
+    - Completeness: all possible solutions are founds
+    """
+
+    def _resolve_depNode(self, depnode):
+        """Compute and return the dependencies involved by @depnode"""
+        # Get inital elements
+        result = super(DependencyGraph_NoMemory, self)._resolve_depNode(depnode)
+
+        # If @depnode depends on a memory element, give up
+        for node in result:
+            if isinstance(node.element, m2_expr.ExprMem):
+                return set()
+
+        return result
diff --git a/miasm2/core/graph.py b/miasm2/core/graph.py
index 2b873ad9..b25907e5 100644
--- a/miasm2/core/graph.py
+++ b/miasm2/core/graph.py
@@ -1,6 +1,6 @@
 from collections import defaultdict
 
-class DiGraph:
+class DiGraph(object):
     """Implementation of directed graph"""
 
     def __init__(self):
diff --git a/test/analysis/depgraph.py b/test/analysis/depgraph.py
new file mode 100644
index 00000000..9237d785
--- /dev/null
+++ b/test/analysis/depgraph.py
@@ -0,0 +1,602 @@
+from miasm2.expression.expression import ExprId, ExprInt32, ExprAff
+from miasm2.core.asmbloc import asm_label
+from miasm2.ir.analysis import ira
+from miasm2.ir.ir import ir, irbloc
+from miasm2.core.graph import DiGraph
+from miasm2.analysis.depgraph import DependencyNode, DependencyGraph, DependencyDict, DependencyGraph_NoMemory
+from pdb import pm
+
+a = ExprId("a")
+b = ExprId("b")
+c = ExprId("c")
+d = ExprId("d")
+
+a_init = ExprId("a_init")
+b_init = ExprId("b_init")
+c_init = ExprId("c_init")
+d_init = ExprId("d_init")
+
+pc = ExprId("pc")
+sp = ExprId("sp")
+
+cst1 = ExprInt32(0x11)
+cst2 = ExprInt32(0x12)
+cst3 = ExprInt32(0x13)
+
+lbl0 = asm_label("lbl0")
+lbl1 = asm_label("lbl1")
+lbl2 = asm_label("lbl2")
+lbl3 = asm_label("lbl3")
+lbl4 = asm_label("lbl4")
+lbl5 = asm_label("lbl5")
+lbl6 = asm_label("lbl6")
+
+
+
+def gen_irbloc(lbl, exprs):
+    lines = [None for i in xrange(len(exprs))]
+    irb = irbloc(lbl, exprs, lines)
+    return irb
+
+
+class Regs(object):
+    regs_init = {a: a_init, b: b_init, c: c_init, d: d_init}
+
+class Arch(object):
+    regs = Regs()
+
+    def getpc(self, attrib):
+        return pc
+
+    def getsp(self, attrib):
+        return sp
+
+class IRATest(ir, ira):
+
+    def __init__(self, symbol_pool=None):
+        arch = Arch()
+        ir.__init__(self, arch, 32, symbol_pool)
+        self.IRDst = pc
+
+    def gen_graph(self):
+        return
+
+class GraphTest(DiGraph):
+    def __init__(self, ira):
+        self.ira = ira
+        super(GraphTest, self).__init__()
+
+    def __eq__(self, graph):
+        if self._nodes != graph._nodes:
+            return False
+        if sorted(self._edges) != sorted(graph._edges):
+            return False
+        return True
+
+    def gen_graph(self):
+        return
+
+    def node2str(self, node):
+        if not node in self.ira.blocs:
+            return str(node)
+        else:
+            return str(self.ira.blocs[node])
+
+class DepNodeTest(DiGraph):
+    def __init__(self, ira):
+        self.ira = ira
+        super(DepNodeTest, self).__init__()
+
+    def __eq__(self, graph):
+        if self._nodes != graph._nodes:
+            return False
+        if sorted(self._edges) != sorted(graph._edges):
+            return False
+        return True
+
+    def node2str(self, node):
+        assert(node.label in self.ira.blocs)
+        out = "(%s, %s, %s)\\l"%(node.label.name,
+                                 node.element,
+                                 node.line_nb)
+        if not (0 <= node.line_nb < len(self.ira.blocs[node.label].irs)):
+            return out
+        exprs = self.ira.blocs[node.label].irs[node.line_nb]
+        exprs_str = '\\l'.join([str(x) for x in exprs])
+        return "%s %s"%(out, exprs_str)
+
+# Test structures
+print "[+] Test structures"
+
+print "[+] Test DependencyDict"
+dd0 = DependencyDict(lbl0, [])
+depnodes_0 = [DependencyNode(lbl0, a, i) for i in xrange(10)][::-1]
+
+## Heads
+assert(list(dd0.heads()) == [])
+assert(dd0.is_head(depnodes_0[-1]) == True)
+assert(dd0.is_head(depnodes_0[0]) == False)
+dd0.cache[depnodes_0[-1]] = set(depnodes_0[-1:])
+assert(list(dd0.heads()) == [depnodes_0[-1]])
+
+## Extend
+dd1 = dd0.extend(lbl1)
+
+assert(dd1.label == lbl1)
+assert(dd1.history == [dd0])
+assert(dd1.cache == dd0.cache)
+assert(dd1.pending == set())
+assert(dd1 != dd0)
+
+dd1.cache[depnodes_0[4]] = set(depnodes_0[5:9])
+assert(dd1.cache != dd0.cache)
+
+dd2 = dd0.copy()
+assert(dd2.label == lbl0)
+assert(dd2.history == [])
+assert(dd2.cache == dd0.cache)
+assert(dd2.pending == dd0.pending)
+assert(dd2 == dd0)
+
+dd2.cache[depnodes_0[4]] = set(depnodes_0[5:9])
+assert(dd2.cache != dd0.cache)
+
+print "[+] DependencyDict OK !"
+print "[+] Structures OK !"
+
+# graph 1
+
+g1_ira = IRATest()
+g1_ira.g = GraphTest(g1_ira)
+
+g1_irb0 = gen_irbloc(lbl0, [ [ExprAff(c, cst1)] ])
+g1_irb1 = gen_irbloc(lbl1, [ [ExprAff(b, c)] ])
+g1_irb2 = gen_irbloc(lbl2, [ [ExprAff(a, b)] ])
+
+g1_ira.g.add_uniq_edge(g1_irb0.label, g1_irb1.label)
+g1_ira.g.add_uniq_edge(g1_irb1.label, g1_irb2.label)
+
+g1_ira.blocs = dict([(irb.label, irb) for irb in [g1_irb0, g1_irb1, g1_irb2]])
+
+# graph 2
+
+g2_ira = IRATest()
+g2_ira.g = GraphTest(g2_ira)
+
+g2_irb0 = gen_irbloc(lbl0, [ [ExprAff(c, cst1)] ])
+g2_irb1 = gen_irbloc(lbl1, [ [ExprAff(b, cst2)] ])
+g2_irb2 = gen_irbloc(lbl2, [ [ExprAff(a, b+c)] ])
+
+g2_ira.g.add_uniq_edge(g2_irb0.label, g2_irb1.label)
+g2_ira.g.add_uniq_edge(g2_irb1.label, g2_irb2.label)
+
+g2_ira.blocs = dict([(irb.label, irb) for irb in [g2_irb0, g2_irb1, g2_irb2]])
+
+
+# graph 3
+
+g3_ira = IRATest()
+g3_ira.g = GraphTest(g3_ira)
+
+g3_irb0 = gen_irbloc(lbl0, [ [ExprAff(c, cst1)] ])
+g3_irb1 = gen_irbloc(lbl1, [ [ExprAff(b, cst2)] ])
+g3_irb2 = gen_irbloc(lbl2, [ [ExprAff(b, cst3)] ])
+g3_irb3 = gen_irbloc(lbl3, [ [ExprAff(a, b+c)] ])
+
+g3_ira.g.add_uniq_edge(g3_irb0.label, g3_irb1.label)
+g3_ira.g.add_uniq_edge(g3_irb0.label, g3_irb2.label)
+g3_ira.g.add_uniq_edge(g3_irb1.label, g3_irb3.label)
+g3_ira.g.add_uniq_edge(g3_irb2.label, g3_irb3.label)
+
+g3_ira.blocs = dict([(irb.label, irb) for irb in [g3_irb0, g3_irb1,
+                                                  g3_irb2, g3_irb3]])
+
+# graph 4
+
+g4_ira = IRATest()
+g4_ira.g = GraphTest(g4_ira)
+
+g4_irb0 = gen_irbloc(lbl0, [ [ExprAff(c, cst1)] ])
+g4_irb1 = gen_irbloc(lbl1, [ [ExprAff(c, c+cst2)] ])
+g4_irb2 = gen_irbloc(lbl2, [ [ExprAff(a, b)] ])
+
+g4_ira.g.add_uniq_edge(g4_irb0.label, g4_irb1.label)
+g4_ira.g.add_uniq_edge(g4_irb1.label, g4_irb2.label)
+g4_ira.g.add_uniq_edge(g4_irb1.label, g4_irb1.label)
+
+g4_ira.blocs = dict([(irb.label, irb) for irb in [g4_irb0, g4_irb1, g4_irb2]])
+
+
+# graph 5
+
+g5_ira = IRATest()
+g5_ira.g = GraphTest(g5_ira)
+
+g5_irb0 = gen_irbloc(lbl0, [ [ExprAff(b, cst1)] ])
+g5_irb1 = gen_irbloc(lbl1, [ [ExprAff(b, b+cst2)] ])
+g5_irb2 = gen_irbloc(lbl2, [ [ExprAff(a, b)] ])
+
+g5_ira.g.add_uniq_edge(g5_irb0.label, g5_irb1.label)
+g5_ira.g.add_uniq_edge(g5_irb1.label, g5_irb2.label)
+g5_ira.g.add_uniq_edge(g5_irb1.label, g5_irb1.label)
+
+g5_ira.blocs = dict([(irb.label, irb) for irb in [g5_irb0, g5_irb1, g5_irb2]])
+
+# graph 6
+
+g6_ira = IRATest()
+g6_ira.g = GraphTest(g6_ira)
+
+g6_irb0 = gen_irbloc(lbl0, [ [ExprAff(b, cst1)] ])
+g6_irb1 = gen_irbloc(lbl1, [ [ExprAff(a, b)] ])
+
+g6_ira.g.add_uniq_edge(g6_irb0.label, g6_irb1.label)
+g6_ira.g.add_uniq_edge(g6_irb1.label, g6_irb1.label)
+
+g6_ira.blocs = dict([(irb.label, irb) for irb in [g6_irb0, g6_irb1]])
+
+# graph 7
+
+g7_ira = IRATest()
+g7_ira.g = GraphTest(g7_ira)
+
+g7_irb0 = gen_irbloc(lbl0, [ [ExprAff(c, cst1)] ])
+g7_irb1 = gen_irbloc(lbl1, [ [ExprAff(b, c)], [ExprAff(a, b)]  ])
+g7_irb2 = gen_irbloc(lbl2, [ [ExprAff(d, a)]  ])
+
+g7_ira.g.add_uniq_edge(g7_irb0.label, g7_irb1.label)
+g7_ira.g.add_uniq_edge(g7_irb1.label, g7_irb1.label)
+g7_ira.g.add_uniq_edge(g7_irb1.label, g7_irb2.label)
+
+g7_ira.blocs = dict([(irb.label, irb) for irb in [g7_irb0, g7_irb1, g7_irb2]])
+
+# graph 8
+
+g8_ira = IRATest()
+g8_ira.g = GraphTest(g8_ira)
+
+g8_irb0 = gen_irbloc(lbl0, [ [ExprAff(c, cst1)] ])
+g8_irb1 = gen_irbloc(lbl1, [ [ExprAff(b, c)], [ExprAff(c, d)]  ])
+g8_irb2 = gen_irbloc(lbl2, [ [ExprAff(a, b)]  ])
+
+g8_ira.g.add_uniq_edge(g8_irb0.label, g8_irb1.label)
+g8_ira.g.add_uniq_edge(g8_irb1.label, g8_irb1.label)
+g8_ira.g.add_uniq_edge(g8_irb1.label, g8_irb2.label)
+
+g8_ira.blocs = dict([(irb.label, irb) for irb in [g8_irb0, g8_irb1, g8_irb2]])
+
+# graph 9 is graph 8
+
+# graph 10
+
+g10_ira = IRATest()
+g10_ira.g = GraphTest(g10_ira)
+
+g10_irb1 = gen_irbloc(lbl1, [ [ExprAff(b, b+cst2)] ])
+g10_irb2 = gen_irbloc(lbl2, [ [ExprAff(a, b)] ])
+
+g10_ira.g.add_uniq_edge(g10_irb1.label, g10_irb2.label)
+g10_ira.g.add_uniq_edge(g10_irb1.label, g10_irb1.label)
+
+g10_ira.blocs = dict([(irb.label, irb) for irb in [g10_irb1, g10_irb2]])
+
+
+# Test graph 1
+
+g1_test1 = DepNodeTest(g1_ira)
+
+g1_test1_dn1 = DependencyNode(g1_irb2.label, a, len(g1_irb2.irs))
+g1_test1_dn2 = DependencyNode(g1_irb2.label, b, 0)
+g1_test1_dn3 = DependencyNode(g1_irb1.label, c, 0)
+g1_test1_dn4 = DependencyNode(g1_irb0.label, cst1, 0)
+
+g1_test1.add_uniq_edge(g1_test1_dn4, g1_test1_dn3)
+g1_test1.add_uniq_edge(g1_test1_dn3, g1_test1_dn2)
+g1_test1.add_uniq_edge(g1_test1_dn2, g1_test1_dn1)
+
+g1_input = (set([g1_test1_dn1]), set([g1_irb0.label]))
+g1_output1 = {"graph": g1_test1,
+              "emul": {a: cst1},
+              "unresolved": set(),
+              "has_loop": False}
+
+# Test graph 2
+
+g2_test1 = DepNodeTest(g2_ira)
+
+g2_test1_dn1 = DependencyNode(g2_irb2.label, a, len(g2_irb2.irs))
+g2_test1_dn2 = DependencyNode(g2_irb2.label, b, 0)
+g2_test1_dn3 = DependencyNode(g2_irb2.label, c, 0)
+g2_test1_dn4 = DependencyNode(g2_irb1.label, cst2, 0)
+g2_test1_dn5 = DependencyNode(g2_irb0.label, cst1, 0)
+
+g2_test1.add_uniq_edge(g2_test1_dn5, g2_test1_dn3)
+g2_test1.add_uniq_edge(g2_test1_dn4, g2_test1_dn2)
+g2_test1.add_uniq_edge(g2_test1_dn2, g2_test1_dn1)
+g2_test1.add_uniq_edge(g2_test1_dn3, g2_test1_dn1)
+
+g2_input = (set([g2_test1_dn1]), set([g2_irb0.label]))
+g2_output1 = {"graph": g2_test1,
+              "emul": {a: ExprInt32(int(cst1.arg) + int(cst2.arg))},
+              "unresolved": set(),
+              "has_loop": False}
+
+# Test graph 3
+
+g3_test1_0 = DepNodeTest(g3_ira)
+g3_test1_1 = DepNodeTest(g3_ira)
+
+g3_test1_0_dn1 = DependencyNode(g3_irb3.label, a, len(g3_irb3.irs))
+g3_test1_0_dn2 = DependencyNode(g3_irb3.label, b, 0)
+g3_test1_0_dn3 = DependencyNode(g3_irb3.label, c, 0)
+g3_test1_0_dn4 = DependencyNode(g3_irb2.label, cst3, 0)
+g3_test1_0_dn5 = DependencyNode(g3_irb0.label, cst1, 0)
+
+g3_test1_1_dn1 = DependencyNode(g3_irb3.label, a, len(g3_irb3.irs))
+g3_test1_1_dn2 = DependencyNode(g3_irb3.label, b, 0)
+g3_test1_1_dn3 = DependencyNode(g3_irb3.label, c, 0)
+g3_test1_1_dn4 = DependencyNode(g3_irb1.label, cst2, 0)
+g3_test1_1_dn5 = DependencyNode(g3_irb0.label, cst1, 0)
+
+g3_test1_0.add_uniq_edge(g3_test1_0_dn5, g3_test1_0_dn3)
+g3_test1_0.add_uniq_edge(g3_test1_0_dn4, g3_test1_0_dn2)
+g3_test1_0.add_uniq_edge(g3_test1_0_dn2, g3_test1_0_dn1)
+g3_test1_0.add_uniq_edge(g3_test1_0_dn3, g3_test1_0_dn1)
+
+g3_test1_1.add_uniq_edge(g3_test1_1_dn5, g3_test1_1_dn3)
+g3_test1_1.add_uniq_edge(g3_test1_1_dn4, g3_test1_1_dn2)
+g3_test1_1.add_uniq_edge(g3_test1_1_dn2, g3_test1_1_dn1)
+g3_test1_1.add_uniq_edge(g3_test1_1_dn3, g3_test1_0_dn1)
+
+g3_input = (set([g3_test1_0_dn1]), set([g3_irb0.label]))
+
+g3_output1 = {"graph": g3_test1_0,
+              "emul": {a: ExprInt32(int(cst1.arg) + int(cst3.arg))},
+              "unresolved": set(),
+              "has_loop": False}
+
+g3_output2 = {"graph": g3_test1_1,
+              "emul": {a: ExprInt32(int(cst1.arg) + int(cst2.arg))},
+              "unresolved": set(),
+              "has_loop": False}
+
+# Test graph 4
+
+g4_test1 = DepNodeTest(g4_ira)
+
+g4_test1_dn1 = DependencyNode(g4_irb2.label, a, len(g2_irb0.irs))
+g4_test1_dn2 = DependencyNode(g4_irb2.label, b, 0)
+g4_test1_dn3 = DependencyNode(g4_irb0.label, b, 0)
+
+g4_test1.add_uniq_edge(g4_test1_dn2, g4_test1_dn1)
+
+g4_input = (set([g4_test1_dn1]), set([g4_irb0.label]))
+
+g4_output1 = {"graph": g4_test1,
+              "emul": {a: b_init},
+              "unresolved": set([g4_test1_dn3]),
+              "has_loop": False}
+
+# Test graph 5
+
+g5_test1 = DepNodeTest(g5_ira)
+
+g5_test1_dn1 = DependencyNode(g5_irb2.label, a, len(g5_irb2.irs))
+g5_test1_dn2 = DependencyNode(g5_irb2.label, b, 0)
+g5_test1_dn3 = DependencyNode(g5_irb1.label, b, 0)
+g5_test1_dn4 = DependencyNode(g5_irb0.label, cst1, 0)
+g5_test1_dn5 = DependencyNode(g5_irb1.label, cst2, 0)
+
+g5_test1.add_uniq_edge(g5_test1_dn4, g5_test1_dn3)
+g5_test1.add_uniq_edge(g5_test1_dn3, g5_test1_dn2)
+g5_test1.add_uniq_edge(g5_test1_dn5, g5_test1_dn2)
+g5_test1.add_uniq_edge(g5_test1_dn2, g5_test1_dn1)
+
+g5_input = (set([g5_test1_dn1]), set([g5_irb0.label]))
+
+g5_output1 = {"graph": g5_test1,
+              "emul": {},
+              "unresolved": set(),
+              "has_loop": True}
+
+# Test graph 6
+
+g6_test1_0 = DepNodeTest(g6_ira)
+
+g6_test1_0_dn1 = DependencyNode(g6_irb1.label, a, len(g6_irb1.irs))
+g6_test1_0_dn2 = DependencyNode(g6_irb1.label, b, 0)
+g6_test1_0_dn3 = DependencyNode(g6_irb0.label, cst1, 0)
+
+
+g6_test1_0.add_uniq_edge(g6_test1_0_dn3, g6_test1_0_dn2)
+g6_test1_0.add_uniq_edge(g6_test1_0_dn2, g6_test1_0_dn1)
+
+g6_input = (set([g6_test1_0_dn1]), set([g6_irb0.label]))
+
+g6_output1 = {"graph": g6_test1_0,
+              "emul": {a: cst1},
+              "unresolved": set(),
+              "has_loop": True}
+
+# Test graph 7
+
+g7_test1_0 = DepNodeTest(g7_ira)
+
+g7_test1_0_dn1 = DependencyNode(g7_irb2.label, a, len(g7_irb2.irs))
+g7_test1_0_dn2 = DependencyNode(g7_irb1.label, b, 1)
+g7_test1_0_dn3 = DependencyNode(g7_irb1.label, c, 0)
+g7_test1_0_dn4 = DependencyNode(g7_irb0.label, cst1, 0)
+
+
+g7_test1_0.add_uniq_edge(g7_test1_0_dn4, g7_test1_0_dn3)
+g7_test1_0.add_uniq_edge(g7_test1_0_dn3, g7_test1_0_dn2)
+g7_test1_0.add_uniq_edge(g7_test1_0_dn2, g7_test1_0_dn1)
+
+g7_input = (set([g7_test1_0_dn1]), set([g7_irb0.label]))
+
+g7_output1 = {"graph": g7_test1_0,
+              "emul": {a: cst1},
+              "unresolved": set(),
+              "has_loop": True}
+
+# Test graph 8
+
+g8_test1_0 = DepNodeTest(g8_ira)
+g8_test1_1 = DepNodeTest(g8_ira)
+
+g8_test1_0_dn1 = DependencyNode(g8_irb2.label, a, len(g8_irb2.irs))
+g8_test1_0_dn2 = DependencyNode(g8_irb2.label, b, 0)
+g8_test1_0_dn3 = DependencyNode(g8_irb1.label, c, 0)
+g8_test1_0_dn4 = DependencyNode(g8_irb0.label, cst1, 0)
+
+g8_test1_1_dn1 = DependencyNode(g8_irb2.label, a, len(g8_irb2.irs))
+g8_test1_1_dn2 = DependencyNode(g8_irb2.label, b, 0)
+g8_test1_1_dn3 = DependencyNode(g8_irb1.label, c, 0)
+g8_test1_1_dn4 = DependencyNode(g8_irb1.label, d, 1)
+
+g8_test1_1_dn5 = DependencyNode(g8_irb0.label, d, 0)
+
+
+g8_test1_0.add_uniq_edge(g8_test1_0_dn4, g8_test1_0_dn3)
+g8_test1_0.add_uniq_edge(g8_test1_0_dn3, g8_test1_0_dn2)
+g8_test1_0.add_uniq_edge(g8_test1_0_dn2, g8_test1_0_dn1)
+
+g8_test1_1.add_uniq_edge(g8_test1_1_dn4, g8_test1_1_dn3)
+g8_test1_1.add_uniq_edge(g8_test1_1_dn3, g8_test1_1_dn2)
+g8_test1_1.add_uniq_edge(g8_test1_1_dn2, g8_test1_1_dn1)
+
+g8_input = (set([g8_test1_0_dn1]), set([g3_irb0.label]))
+
+g8_output1 = {"graph": g8_test1_0,
+              "emul": {a: cst1},
+              "unresolved": set(),
+              "has_loop": False}
+
+g8_output2 = {"graph": g8_test1_1,
+              "emul": {a: d_init},
+              "unresolved": set([g8_test1_1_dn5]),
+              "has_loop": True}
+
+
+# Test 9: Multi elements
+
+g9_test1_0 = DepNodeTest(g8_ira)
+g9_test1_1 = DepNodeTest(g8_ira)
+
+g9_test1_0_dn1 = DependencyNode(g8_irb2.label, a, len(g8_irb2.irs))
+g9_test1_0_dn2 = DependencyNode(g8_irb2.label, b, 0)
+g9_test1_0_dn3 = DependencyNode(g8_irb1.label, c, 0)
+g9_test1_0_dn4 = DependencyNode(g8_irb0.label, cst1, 0)
+g9_test1_0_dn5 = DependencyNode(g8_irb2.label, c, len(g8_irb2.irs))
+g9_test1_0_dn6 = DependencyNode(g8_irb1.label, d, 1)
+
+g9_test1_1_dn1 = DependencyNode(g8_irb2.label, a, len(g8_irb2.irs))
+g9_test1_1_dn2 = DependencyNode(g8_irb2.label, b, 0)
+g9_test1_1_dn3 = DependencyNode(g8_irb1.label, c, 0)
+g9_test1_1_dn4 = DependencyNode(g8_irb1.label, d, 1)
+g9_test1_1_dn5 = DependencyNode(g8_irb2.label, c, len(g8_irb2.irs))
+
+
+g9_test1_0.add_uniq_edge(g9_test1_0_dn4, g9_test1_0_dn3)
+g9_test1_0.add_uniq_edge(g9_test1_0_dn3, g9_test1_0_dn2)
+g9_test1_0.add_uniq_edge(g9_test1_0_dn2, g9_test1_0_dn1)
+g9_test1_0.add_uniq_edge(g9_test1_0_dn6, g9_test1_0_dn5)
+
+g9_test1_1.add_uniq_edge(g9_test1_1_dn4, g9_test1_1_dn5)
+g9_test1_1.add_uniq_edge(g9_test1_1_dn4, g9_test1_1_dn3)
+g9_test1_1.add_uniq_edge(g9_test1_1_dn3, g9_test1_1_dn2)
+g9_test1_1.add_uniq_edge(g9_test1_1_dn2, g9_test1_1_dn1)
+
+g9_input = (set([g9_test1_0_dn1, g9_test1_0_dn5]), set([g8_irb0.label]))
+
+g9_output1 = {"graph": g9_test1_0,
+              "emul": {a: cst1,
+                       c: d_init},
+              "unresolved": set([g8_test1_1_dn5]),
+              "has_loop": False}
+
+g9_output2 = {"graph": g9_test1_1,
+              "emul": {a: d_init,
+                       c: d_init},
+              "unresolved": set([g8_test1_1_dn5]),
+              "has_loop": True}
+
+
+# Test 10: loop at beginning
+
+g10_test1 = DepNodeTest(g10_ira)
+
+g10_test1_dn1 = DependencyNode(g10_irb2.label, a, len(g10_irb2.irs))
+g10_test1_dn2 = DependencyNode(g10_irb2.label, b, 0)
+g10_test1_dn3 = DependencyNode(g10_irb1.label, b, 0)
+g10_test1_dn4 = DependencyNode(g10_irb1.label, cst2, 0)
+
+g10_test1.add_uniq_edge(g10_test1_dn3, g10_test1_dn2)
+g10_test1.add_uniq_edge(g10_test1_dn4, g10_test1_dn2)
+g10_test1.add_uniq_edge(g10_test1_dn2, g10_test1_dn1)
+
+g10_input = (set([g10_test1_dn1]), set([g10_irb1.label]))
+
+g10_output1 = {"graph": g10_test1,
+               "emul": {},
+               "unresolved": set([g10_test1_dn3]),
+               "has_loop": True}
+
+
+# Launch tests
+for i, test in enumerate([(g1_ira, g1_input, [g1_output1]),
+                          (g2_ira, g2_input, [g2_output1]),
+                          (g3_ira, g3_input, [g3_output1, g3_output2]),
+                          (g4_ira, g4_input, [g4_output1]),
+                          (g5_ira, g5_input, [g5_output1]),
+                          (g6_ira, g6_input, [g6_output1]),
+                          (g7_ira, g7_input, [g7_output1]),
+                          (g8_ira, g8_input, [g8_output1, g8_output2]),
+                          (g8_ira, g9_input, [g9_output1, g9_output2]),
+                          (g10_ira, g10_input, [g10_output1]),
+                      ]):
+    # Extract test elements
+    print "[+] Test", i+1
+    g_ira, (depnodes, heads), g_test_list = test
+    open("graph_%02d.dot" % (i+1), "w").write(g_ira.g.dot())
+    # Test classes
+    for g_dep in [DependencyGraph(g_ira),
+                  DependencyGraph_NoMemory(g_ira)]:
+        print " - Class %s" % g_dep.__class__.__name__
+
+        ## Test public APIs
+        for api_i, g_list in enumerate([g_dep.get_fromDepNodes(depnodes, heads),
+                                        g_dep.get(list(depnodes)[0].label,
+                                                  [depnode.element for
+                                                   depnode in depnodes],
+                                                  list(depnodes)[0].line_nb,
+                                                  heads)]):
+            print " - - API %s" % ("get_fromDepNodes" if api_i == 0 else "get")
+
+            ### Expand result iterator
+            g_list = list(g_list)
+            ### Dump outputs graphs for debug means
+            for j, result in enumerate(g_list):
+                open("graph_test_%02d_%02d.dot" % (i+1, j), "w").write(result.graph.dot())
+
+            ### The number of results should be the same
+            print " - - - number of results"
+            assert(len(g_list) == len(g_test_list))
+
+            ### Match the right result (unordered)
+            for i, result in enumerate(g_list):
+                print " - - - result %d" % i
+                found = False
+                for expected in g_test_list:
+                    if expected["graph"].__eq__(result.graph):
+                        found = True
+                        break
+                assert(found)
+
+                #### @expected is the corresponding result, test for properties
+                print " - - - - emul"
+                if not expected["has_loop"]:
+                    assert(expected["emul"] == result.emul())
+                for element in ["unresolved"]: # TODO: has_loop
+                    print " - - - - %s" % element
+                    assert(expected[element] == getattr(result, element))
diff --git a/test/test_all.py b/test/test_all.py
index 1e5de442..0ecc677f 100644
--- a/test/test_all.py
+++ b/test/test_all.py
@@ -121,6 +121,25 @@ for script in ["win_api_x86_32.py",
                ]:
     testset += RegressionTest([script], base_dir="os_dep")
 
+## Analysis
+testset += RegressionTest(["depgraph.py"], base_dir="analysis",
+                          products=["graph_test_01_00.dot",
+                                    "graph_test_02_00.dot",
+                                    "graph_test_02_01.dot",
+                                    "graph_test_03_00.dot",
+                                    "graph_test_03_01.dot",
+                                    "graph_test_04_00.dot",
+                                    "graph_test_05_00.dot",
+                                    "graph_test_06_00.dot",
+                                    "graph_test_07_00.dot",
+                                    "graph_test_08_00.dot",
+                                    "graph_test_08_01.dot",
+                                    "graph_test_09_00.dot",
+                                    "graph_test_09_01.dot",
+                                    "graph_test_10_00.dot",
+                                    ] + ["graph_%02d.dot" % test_nb
+                                         for test_nb in xrange(1, 11)])
+
 # Examples
 class Example(Test):
     """Examples specificities: