diff options
41 files changed, 1141 insertions, 1426 deletions
diff --git a/example/ida/depgraph.py b/example/ida/depgraph.py index 406f7200..1784b4e4 100644 --- a/example/ida/depgraph.py +++ b/example/ida/depgraph.py @@ -132,9 +132,11 @@ for bloc in blocs: # Simplify affectations for irb in ir_arch.blocs.values(): - for irs in irb.irs: - for i, expr in enumerate(irs): - irs[i] = m2_expr.ExprAff(expr_simp(expr.dst), expr_simp(expr.src)) + for assignblk in irb.irs: + for dst, src in assignblk.items(): + del(assignblk[dst]) + dst, src = expr_simp(dst), expr_simp(src) + assignblk[dst] = src # Get settings settings = depGraphSettingsForm(ir_arch) @@ -183,7 +185,10 @@ def treat_element(): comments[offset] = comments.get(offset, []) + [node.element] SetColor(offset, CIC_ITEM, settings.color) - print "Possible value: %s" % graph.emul().values()[0] + if graph.has_loop: + print 'Graph has dependency loop: symbolic execution is inexact' + else: + print "Possible value: %s" % graph.emul().values()[0] for offset, elements in comments.iteritems(): MakeComm(offset, ", ".join(map(str, elements))) diff --git a/example/ida/graph_ir.py b/example/ida/graph_ir.py index 4447cadd..188c8fa6 100644 --- a/example/ida/graph_ir.py +++ b/example/ida/graph_ir.py @@ -19,10 +19,11 @@ def color_irbloc(irbloc): lbl = '%s' % irbloc.label lbl = idaapi.COLSTR(lbl, idaapi.SCOLOR_INSN) o.append(lbl) - for i, expr in enumerate(irbloc.irs): - for e in expr: - s = expr2colorstr(ir_arch.arch.regs.all_regs_ids, e) - s = idaapi.COLSTR(s, idaapi.SCOLOR_INSN) + for assignblk in irbloc.irs: + for dst, src in sorted(assignblk.iteritems()): + dst_f = expr2colorstr(ir_arch.arch.regs.all_regs_ids, dst) + src_f = expr2colorstr(ir_arch.arch.regs.all_regs_ids, src) + s = idaapi.COLSTR("%s = %s" % (dst_f, src_f), idaapi.SCOLOR_INSN) o.append(' %s' % s) o.append("") o.pop() @@ -119,7 +120,7 @@ print hex(ad) ab = mdis.dis_multibloc(ad) print "generating graph" -open('asm_flow.dot', 'w').write(ab.graph.dot(label=True)) +open('asm_flow.dot', 'w').write(ab.dot()) print "generating IR... %x" % ad @@ -133,9 +134,11 @@ for b in ab: print "IR ok... %x" % ad for irb in ir_arch.blocs.values(): - for irs in irb.irs: - for i, expr in enumerate(irs): - irs[i] = ExprAff(expr_simp(expr.dst), expr_simp(expr.src)) + for assignblk in irb.irs: + for dst, src in assignblk.items(): + del(assignblk[dst]) + dst, src = expr_simp(dst), expr_simp(src) + assignblk[dst] = src out = ir_arch.graph.dot() open(os.path.join(tempfile.gettempdir(), 'graph.dot'), 'wb').write(out) diff --git a/example/samples/x86_32_if_reg.S b/example/samples/x86_32_if_reg.S new file mode 100644 index 00000000..f519f8f7 --- /dev/null +++ b/example/samples/x86_32_if_reg.S @@ -0,0 +1,11 @@ +main: + MOV EAX, 0x0 + CMP EBX, 0 + JZ skip1 + OR EAX, 0x11220000 +skip1: + CMP EBX, 0 + JZ skip2 + OR EAX, 0x3344 +skip2: + RET diff --git a/example/symbol_exec/depgraph.py b/example/symbol_exec/depgraph.py index a870b275..48758ad0 100644 --- a/example/symbol_exec/depgraph.py +++ b/example/symbol_exec/depgraph.py @@ -1,5 +1,6 @@ from argparse import ArgumentParser from pdb import pm +import json from miasm2.analysis.machine import Machine from miasm2.analysis.binary import Container @@ -12,18 +13,21 @@ parser.add_argument("func_addr", help="Function address") parser.add_argument("target_addr", help="Address to start") parser.add_argument("element", nargs="+", help="Elements to track") parser.add_argument("-m", "--architecture", - help="Architecture (%s)" % Machine.available_machine()) + help="Architecture (%s)" % Machine.available_machine()) parser.add_argument("-i", "--implicit", help="Use implicit tracking", - action="store_true") + action="store_true") parser.add_argument("--unfollow-mem", help="Stop on memory statements", - action="store_true") + action="store_true") parser.add_argument("--unfollow-call", help="Stop on call statements", - action="store_true") + action="store_true") parser.add_argument("--do-not-simplify", help="Do not simplify expressions", - action="store_true") + action="store_true") parser.add_argument("--rename-args", help="Rename common arguments (@32[ESP_init] -> Arg1)", - action="store_true") + action="store_true") +parser.add_argument("--json", + help="Output solution in JSON", + action="store_true") args = parser.parse_args() # Get architecture @@ -38,9 +42,9 @@ elements = set() regs = machine.mn.regs.all_regs_ids_byname for element in args.element: try: - elements.add(regs[element.upper()]) + elements.add(regs[element.upper()]) except KeyError: - raise ValueError("Unknown element '%s'" % element) + raise ValueError("Unknown element '%s'" % element) mdis = machine.dis_engine(cont.bin_stream, dont_dis_nulstart_bloc=True) ir_arch = machine.ira(mdis.symbol_pool) @@ -63,9 +67,9 @@ for block in blocks: # Get the instance dg = DependencyGraph(ir_arch, implicit=args.implicit, - apply_simp=not(args.do_not_simplify), - follow_mem=not(args.unfollow_mem), - follow_call=not(args.unfollow_call)) + apply_simp=not args.do_not_simplify, + follow_mem=not args.unfollow_mem, + follow_call=not args.unfollow_call) # Build information target_addr = int(args.target_addr, 0) @@ -73,23 +77,46 @@ current_block = list(ir_arch.getby_offset(target_addr))[0] line_nb = 0 for line_nb, line in enumerate(current_block.lines): if line.offset == target_addr: - break + break # Enumerate solutions +json_solutions = [] for sol_nb, sol in enumerate(dg.get(current_block.label, elements, line_nb, set())): - fname = "sol_%d.dot" % sol_nb - with open(fname, "w") as fdesc: - fdesc.write(sol.graph.dot()) - result = ", ".join("%s: %s" % (k, v) - for k, v in sol.emul(ctx=init_ctx).iteritems()) - print "Solution %d: %s -> %s" % (sol_nb, - result, - fname) - if args.implicit: - sat = sol.is_satisfiable - constraints = "" - if sat: - constraints = {} - for element in sol.constraints: - constraints[element] = hex(sol.constraints[element].as_long()) + fname = "sol_%d.dot" % sol_nb + with open(fname, "w") as fdesc: + fdesc.write(sol.graph.dot()) + + results = sol.emul(ctx=init_ctx) + tokens = {str(k): str(v) for k, v in results.iteritems()} + if not args.json: + result = ", ".join("=".join(x) for x in tokens.iteritems()) + print "Solution %d: %s -> %s" % (sol_nb, + result, + fname) + if sol.has_loop: + print '\tLoop involved' + + if args.implicit: + sat = sol.is_satisfiable + constraints = {} + if sat: + for element in sol.constraints: + try: + result = hex(sol.constraints[element].as_long()) + except AttributeError: + result = str(sol.constraints[element]) + constraints[element] = result + if args.json: + tokens["satisfiability"] = sat + tokens["constraints"] = {str(k): str(v) + for k, v in constraints.iteritems()} + else: print "\tSatisfiability: %s %s" % (sat, constraints) + + if args.json: + tokens["has_loop"] = sol.has_loop + json_solutions.append(tokens) + + +if args.json: + print json.dumps(json_solutions) diff --git a/miasm2/analysis/depgraph.py b/miasm2/analysis/depgraph.py index 897de77b..aec159aa 100644 --- a/miasm2/analysis/depgraph.py +++ b/miasm2/analysis/depgraph.py @@ -1,20 +1,18 @@ """Provide dependency graph""" -import itertools -from collections import deque -from UserDict import IterableUserDict - -try: - import z3 -except ImportError: - pass import miasm2.expression.expression as m2_expr from miasm2.core.graph import DiGraph -from miasm2.core.asmbloc import asm_label, expr_is_label +from miasm2.core.asmbloc import asm_label, expr_is_int_or_label, expr_is_label from miasm2.expression.simplifications import expr_simp from miasm2.ir.symbexec import symbexec -from miasm2.ir.ir import irbloc +from miasm2.ir.ir import irbloc, AssignBlock from miasm2.ir.translators import Translator +from miasm2.expression.expression_helper import possible_values + +try: + import z3 +except ImportError: + pass class DependencyNode(object): @@ -26,24 +24,21 @@ class DependencyNode(object): line. """ - __slots__ = ["_label", "_element", "_line_nb", "_modifier", + __slots__ = ["_label", "_element", "_line_nb", "_step", "_nostep_repr", "_hash"] - def __init__(self, label, element, line_nb, step, modifier=False): + def __init__(self, label, element, line_nb): """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._step = step self._nostep_repr = (self._label, self._line_nb, self._element) self._hash = hash( - (self._label, self._element, self._line_nb, self._step)) + (self._label, self._element, self._line_nb)) def __hash__(self): """Returns a hash of @self to uniquely identify @self""" @@ -57,8 +52,7 @@ class DependencyNode(object): return False return (self.label == depnode.label and self.element == depnode.element and - self.line_nb == depnode.line_nb and - self.step == depnode.step) + self.line_nb == depnode.line_nb) def __cmp__(self, node): """Compares @self with @node. The step attribute is not taken into @@ -72,10 +66,9 @@ class DependencyNode(object): def __str__(self): """Returns a string representation of DependencyNode""" - return "<%s %s %s %s M:%s S:%s>" % (self.__class__.__name__, - self.label.name, self.element, - self.line_nb, self.modifier, - self.step) + return "<%s %s %s %s>" % (self.__class__.__name__, + self.label.name, self.element, + self.line_nb) def __repr__(self): """Returns a string representation of DependencyNode""" @@ -101,434 +94,163 @@ class DependencyNode(object): "Line in the current IRBlock" return self._line_nb - @property - def step(self): - "Step of the current node" - return self._step - - @property - def modifier(self): - """Evaluating the current line involves a modification of tracked - dependencies""" - return self._modifier - - @modifier.setter - def modifier(self, value): - """Evaluating the current line involves a modification of tracked - dependencies if @value. - @value: boolean""" - self._modifier = value - - -class CacheWrapper(IterableUserDict): - - """Wrapper class for cache dictionary""" - - def __init__(self, dct=None): - """Create a CacheWrapper with value @dct.""" - IterableUserDict.__init__(self, dct) - self._nostep_cache = None - self._nostep_keys = None - - def __eq__(self, cache): - """Returns True if the nostep caches are equals""" - if self.nostep_keys != cache.nostep_keys: - return False - return self.nostep_cache == cache.nostep_cache - - @property - def nostep_keys(self): - """List of dictonnary keys without the step attribute. - The list is generated once when the method is called and not updated - afterward. - """ - if self._nostep_keys is None: - self._nostep_keys = set(key.nostep_repr for key in self.data) - return self._nostep_keys - - @property - def nostep_cache(self): - """Dictionary of DependencyNode and their dependencies, - without the step attribute. - The dictionary is generated once when the method is called for the - first time and not updated afterward. - """ - if self._nostep_cache is None: - self._nostep_cache = {} - for (node, values) in self.data.iteritems(): - self._nostep_cache.setdefault(node.nostep_repr, set()).update( - set(val.nostep_repr for val in values)) - return self._nostep_cache - - -class DependencyDict(object): - - """Internal structure for the DependencyGraph algorithm""" - __slots__ = ["_label", "_history", "_pending", "_cache"] - - 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 = CacheWrapper() +class DependencyState(object): - def __eq__(self, depdict): - if not isinstance(depdict, self.__class__): - return False - return (self._label == depdict.label and - self.cache == depdict.cache) - - 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" + """ + Store intermediate depnodes states during dependencygraph analysis + """ - # Initialize - new_history = list(self.history) - depdict = DependencyDict(self.label, new_history) + def __init__(self, label, inputs, pending, line_nb=None): + self.label = label + self.inputs = inputs + self.history = [label] + self.pending = {k: set(v) for k, v in pending.iteritems()} + self.line_nb = line_nb + self.links = set() - # Copy values - for key, values in self.cache.iteritems(): - depdict.cache[key] = set(values) - depdict.pending.update(self.pending) + # Init lazy elements + self._graph = None - return depdict + def __repr__(self): + return "<State: %r (%r) (%r)>" % (self.label, + self.pending, + self.links) 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 + """Return a copy of itself, with itself in history + @label: asm_label instance for the new DependencyState's label """ - depdict = DependencyDict(label, list(self.history) + [self]) - for key, values in self.cache.iteritems(): - depdict.cache[key] = set(values) - return depdict + new_state = self.__class__(label, self.inputs, self.pending) + new_state.links = set(self.links) + new_state.history = self.history + [label] + return new_state - 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 + def get_done_state(self): + """Returns immutable object representing current state""" + return (self.label, frozenset(self.links)) - @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): - "Dictionary of DependencyNode and their dependencies" - return self._cache - - @property - def pending(self): - """Dictionary of DependencyNode and their dependencies, waiting for - resolution""" - return self._pending - - def _get_modifiers_in_cache(self, nodes_heads): - """Find modifier nodes in cache starting from @nodes_heads. - Returns new cache""" - # 'worklist_depnode' order is needed (depth first) - worklist_depnodes = list(nodes_heads) - # Temporary cache - cache = {} - # Partially resolved 'cache' elements - worklist = [] - - # Build worklist and cache for non modifiers - while worklist_depnodes: - depnode = worklist_depnodes.pop() - # Resolve node dependencies - if depnode in cache: - # Depnode previously resolved - continue - - if depnode not in self._cache: - # Final node - if not depnode.modifier: - cache[depnode] = [] - continue - - # Propagate to son - dependencies = self._cache[depnode] - for son in dependencies: - worklist_depnodes.append(son) - # Save partially resolved dependency - worklist.append((depnode, dependencies)) - - # Convert worklist to cache - while worklist: - depnode, dependencies = worklist.pop() - parallels = [] - for node in dependencies: - if node.modifier: - parallels.append([node]) - else: - parallels.append(cache[node]) - out = set() - for parallel in itertools.product(*[p for p in parallels if p]): - out.update(parallel) - cache[depnode] = out - - return cache - - def clean_modifiers_in_cache(self, node_heads): - """Remove intermediary states (non modifier depnodes) in the internal - cache values""" - - self._cache = CacheWrapper(self._get_modifiers_in_cache(node_heads)) - - 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] + def as_graph(self): + """Generates a Digraph of dependencies""" 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 + for node_a, node_b in self.links: + if not node_b: + graph.add_node(node_a) + else: + graph.add_edge(node_a, node_b) + for parent, sons in self.pending.iteritems(): + for son in sons: + graph.add_edge(parent, son) 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 + @property + def graph(self): + """Returns a DiGraph instance representing the DependencyGraph""" + if self._graph is None: + self._graph = self.as_graph() + return self._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 + def remove_pendings(self, nodes): + """Remove resolved @nodes""" + for node in nodes: + del self.pending[node] + + def add_pendings(self, future_pending): + """Add @future_pending to the state""" + for node, depnodes in future_pending.iteritems(): + if node not in self.pending: + self.pending[node] = depnodes + else: + self.pending[node].update(depnodes) + + def link_element(self, element, line_nb): + """Link element to its dependencies + @element: the element to link + @line_nb: the element's line """ - # Init - todo = set(node_heads) - used_nodes = set() - - # Map - while todo: - node = todo.pop() - if node in used_nodes: - continue - 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] - - def filter_unmodifier_loops(self, implicit, irdst): - """ - Remove unmodifier node creating dependency loops over - pending elements in cache. - @implicit: boolean - @irdst: ExprId instance of IRDst register + depnode = DependencyNode(self.label, element, line_nb) + if not self.pending[element]: + # Create start node + self.links.add((depnode, None)) + else: + # Link element to its known dependencies + for node_son in self.pending[element]: + self.links.add((depnode, node_son)) + + def link_dependencies(self, element, line_nb, dependencies, + future_pending): + """Link unfollowed dependencies and create remaining pending elements. + @element: the element to link + @line_nb: the element's line + @dependencies: the element's dependencies + @future_pending: the future dependencies """ - previous_dict = None - # Get pending nodes of last time the label was handled - for hist_dict in reversed(self.history): - if hist_dict.label == self.label: - previous_dict = hist_dict - break - - if not previous_dict: - return - - nostep_pending = [node.nostep_repr for node in self.pending] - - to_remove = set() - for depnode in previous_dict.pending: - if (depnode.nostep_repr not in nostep_pending or - implicit and depnode.element == irdst): - continue - - to_remove.update(self._non_modifier_in_loop(depnode)) - - # Replace unused keys by previous ones - for key in to_remove: - if depnode.nostep_repr == key.nostep_repr: - self._cache[depnode] = self._cache.get(key, set()).copy() - self.pending.discard(key) - self.pending.add(depnode) - - # Replace occurences of key to remove - for dependencies in self._cache.itervalues(): - if key in dependencies: - dependencies.remove(key) - dependencies.add(depnode) + depnode = DependencyNode(self.label, element, line_nb) - if self._cache.has_key(key): - del self._cache[key] - - def _non_modifier_in_loop(self, depnode): - """ - Walk from @depnode until a node with the same nostep_repr is - encountered. - Returns a set of unmodifier nodes met in the path if no modifier was - found. - Returns set() if there exist a modifier node on the path. - """ - if not self.cache.has_key(depnode): - return set() - # Init - todo = set(self.cache[depnode]) - unmodifier_nodes = [] - - # Map - while todo: - node = todo.pop() - if node in unmodifier_nodes: + # Update pending, add link to unfollowed nodes + for dependency in dependencies: + if not dependency.follow: + # Add non followed dependencies to the dependency graph + parent = DependencyNode( + self.label, dependency.element, line_nb) + self.links.add((parent, depnode)) continue - if node.modifier: - return set() - unmodifier_nodes.append(node) - if not node in self._cache: - continue - if node.nostep_repr == depnode.nostep_repr: - unmodifier_nodes.append(node) - break - - for sub_node in self._cache[node]: - todo.add(sub_node) - - return unmodifier_nodes + # Create future pending between new dependency and the current + # element + future_pending.setdefault(dependency.element, set()).add(depnode) -class DependencyResult(object): +class DependencyResult(DependencyState): """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 + def __init__(self, state, ira): + self.label = state.label + self.inputs = state.inputs + self.history = state.history + self.pending = state.pending + self.line_nb = state.line_nb + self.links = state.links 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): - """Returns a DiGraph instance representing the DependencyGraph""" - if self._graph is None: - self._graph = self._depdict.as_graph(self._input_depnodes) - return self._graph - - @property - def history(self): - """List of depdict corresponding to the blocks encountered in the - analysis""" - return list(self._depdict.history) + [self._depdict] - - @property def unresolved(self): """Set of nodes whose dependencies weren't found""" - return set(node.nostep_repr for node in self._depdict.pending - if node.element != self._ira.IRDst) + return set(element for element in self.pending + if element != self._ira.IRDst) @property def relevant_nodes(self): - """Set of nodes directly and indirectly influencing - @self.input_depnodes""" + """Set of nodes directly and indirectly influencing inputs""" output = set() - for depnodes in self._depdict.cache.values(): - output.update(depnodes) + for node_a, node_b in self.links: + output.add(node_a) + if node_b is not None: + output.add(node_b) return output @property def relevant_labels(self): - """List of labels containing nodes influencing @self.input_depnodes. - The history order is preserved. - """ + """List of labels containing nodes influencing inputs. + The history order is preserved.""" # 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]: + for label in self.history: if label in used_labels: output.append(label) return output @property - def input(self): - """Set of DependencyGraph start nodes""" - return self._input_depnodes - - @property def has_loop(self): """True if current dictionary has a loop""" if self._has_loop is None: @@ -536,38 +258,55 @@ class DependencyResult(object): len(set(self.relevant_labels))) return self._has_loop + def irblock_slice(self, irb): + """Slice of the dependency nodes on the irblock @irb + @irb: irbloc instance + """ + + assignblks = [] + line2elements = {} + for depnode in self.relevant_nodes: + if depnode.label != irb.label: + continue + line2elements.setdefault(depnode.line_nb, + set()).add(depnode.element) + + for line_nb, elements in sorted(line2elements.iteritems()): + assignblk = AssignBlock() + for element in elements: + if element in irb.irs[line_nb]: + # constants, label, ... are not in destination + assignblk[element] = irb.irs[line_nb][element] + assignblks.append(assignblk) + + return irbloc(irb.label, assignblks) + def emul(self, ctx=None, step=False): """Symbolic execution of relevant nodes according to the history - Return the values of input nodes' elements - @ctx: (optional) Initial context as dictionary + Return the values of inputs nodes' elements + @ctx: (optional) Initial context as dictionnary @step: (optional) Verbose execution - - Warning: The emulation is not sound if the input nodes depend on loop + Warning: The emulation is not sound if the inputs nodes depend on loop variant. """ # Init ctx_init = self._ira.arch.regs.regs_init if ctx is not None: ctx_init.update(ctx) - depnodes = self.relevant_nodes - affects = [] + assignblks = [] # Build a single affectation block according to history for label in self.relevant_labels[::-1]: - affected_lines = set(depnode.line_nb for depnode in depnodes - if depnode.label == label) - irs = self._ira.blocs[label].irs - for line_nb in sorted(affected_lines): - affects.append(irs[line_nb]) + assignblks += self.irblock_slice(self._ira.blocs[label]).irs # Eval the block temp_label = asm_label("Temp") symb_exec = symbexec(self._ira, ctx_init) - symb_exec.emulbloc(irbloc(temp_label, affects), step=step) + symb_exec.emulbloc(irbloc(temp_label, assignblks), step=step) # Return only inputs values (others could be wrongs) - return {depnode.element: symb_exec.symbols[depnode.element] - for depnode in self.input} + return {element: symb_exec.symbols[element] + for element in self.inputs} class DependencyResultImplicit(DependencyResult): @@ -575,57 +314,81 @@ class DependencyResultImplicit(DependencyResult): """Stand for a result of a DependencyGraph with implicit option Provide path constraints using the z3 solver""" - __slots__ = ["_ira", "_depdict", "_input_depnodes", "_graph", - "_has_loop", "_solver"] - # Z3 Solver instance _solver = None + unsat_expr = m2_expr.ExprAff(m2_expr.ExprInt(0, 1), + m2_expr.ExprInt(1, 1)) + + def _gen_path_constraints(self, translator, expr, expected): + """Generate path constraint from @expr. Handle special case with + generated labels + """ + out = [] + expected_is_label = expr_is_label(expected) + for consval in possible_values(expr): + if (expected_is_label and + consval.value != expected): + continue + if (not expected_is_label and + expr_is_label(consval.value)): + continue + + conds = z3.And(*[translator.from_expr(cond.to_constraint()) + for cond in consval.constraints]) + if expected != consval.value: + conds = z3.And(conds, + translator.from_expr( + m2_expr.ExprAff(consval.value, + expected))) + out.append(conds) + + if out: + conds = z3.Or(*out) + else: + # Ex: expr: lblgen1, expected: 0x1234 + # -> Avoid unconsistent solution lblgen1 = 0x1234 + conds = translator.from_expr(self.unsat_expr) + return conds + def emul(self, ctx=None, step=False): # Init ctx_init = self._ira.arch.regs.regs_init if ctx is not None: ctx_init.update(ctx) - depnodes = self.relevant_nodes solver = z3.Solver() symb_exec = symbexec(self._ira, ctx_init) - temp_label = asm_label("Temp") - history = self.relevant_labels[::-1] + history = self.history[::-1] history_size = len(history) + translator = Translator.to_language("z3") + size = self._ira.IRDst.size for hist_nb, label in enumerate(history): - # Build block with relevant lines only - affected_lines = set(depnode.line_nb for depnode in depnodes - if depnode.label == label) - irs = self._ira.blocs[label].irs - affects = [] - - for line_nb in sorted(affected_lines): - affects.append(irs[line_nb]) + irb = self.irblock_slice(self._ira.blocs[label]) # Emul the block and get back destination - dst = symb_exec.emulbloc(irbloc(temp_label, affects), step=step) + dst = symb_exec.emulbloc(irb, step=step) # Add constraint if hist_nb + 1 < history_size: next_label = history[hist_nb + 1] - expected = symb_exec.eval_expr(m2_expr.ExprId(next_label, 32)) - constraint = m2_expr.ExprAff(dst, expected) - solver.add(Translator.to_language("z3").from_expr(constraint)) - + expected = symb_exec.eval_expr(m2_expr.ExprId(next_label, + size)) + solver.add( + self._gen_path_constraints(translator, dst, expected)) # Save the solver self._solver = solver # Return only inputs values (others could be wrongs) - return {depnode.element: symb_exec.symbols[depnode.element] - for depnode in self.input} + return {element: symb_exec.eval_expr(element) + for element in self.inputs} @property def is_satisfiable(self): """Return True iff the solution path admits at least one solution PRE: 'emul' """ - return self._solver.check().r > 0 + return self._solver.check() == z3.sat @property def constraints(self): @@ -644,24 +407,23 @@ class FollowExpr(object): self.follow = follow self.element = element + def __repr__(self): + return '%s(%r, %r)' % (self.__class__.__name__, self.follow, self.element) + @staticmethod - def to_depnodes(follow_exprs, label, line, modifier, step): + def to_depnodes(follow_exprs, label, line): """Build a set of FollowExpr(DependencyNode) from the @follow_exprs set of FollowExpr @follow_exprs: set of FollowExpr @label: asm_label instance @line: integer - @modifier: boolean - @step: integer """ dependencies = set() for follow_expr in follow_exprs: dependencies.add(FollowExpr(follow_expr.follow, DependencyNode(label, follow_expr.element, - line, - step, - modifier=modifier))) + line))) return dependencies @staticmethod @@ -686,9 +448,10 @@ class DependencyGraph(object): def __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 + @implicit: (optional) Track IRDst for each block in the resulting path Following arguments define filters used to generate dependencies @apply_simp: (optional) Apply expr_simp @@ -698,8 +461,6 @@ class DependencyGraph(object): # Init self._ira = ira self._implicit = implicit - self._step_counter = itertools.count() - self._current_step = next(self._step_counter) # Create callback filters. The order is relevant. self._cb_follow = [] @@ -710,21 +471,6 @@ class DependencyGraph(object): follow_call)) self._cb_follow.append(self._follow_nolabel) - @property - def step_counter(self): - "Iteration counter" - return self._step_counter - - @property - def current_step(self): - "Current value of iteration counter" - return self._current_step - - def inc_step(self): - "Increment and return the current step" - self._current_step = next(self._step_counter) - return self._current_step - @staticmethod def _follow_simp_expr(exprs): """Simplify expression so avoid tracking useless elements, @@ -748,10 +494,12 @@ class DependencyGraph(object): follow.add(expr) elif isinstance(expr, m2_expr.ExprInt): nofollow.add(expr) + elif isinstance(expr, m2_expr.ExprMem): + follow.add(expr) return expr @staticmethod - def follow_expr(expr, follow, nofollow, follow_mem=False, follow_call=False): + def follow_expr(expr, _, nofollow, follow_mem=False, follow_call=False): """Returns True if we must visit sub expressions. @expr: expression to browse @follow: set of nodes to follow @@ -785,7 +533,7 @@ class DependencyGraph(object): """Do not follow labels""" follow = set() for expr in exprs: - if not expr_is_label(expr): + if not expr_is_int_or_label(expr): follow.add(expr) return follow, set() @@ -804,167 +552,38 @@ class DependencyGraph(object): out.update(set(FollowExpr(False, expr) for expr in nofollow)) return out - 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 _direct_depnode_dependencies(self, depnode): - """Compute and return the dependencies involved by @depnode, - over the instruction @depnode.line_,. - Return a set of FollowExpr""" - - 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 - - assignblk = self._get_affblock(depnode) - if depnode.element in assignblk: - elements = self._follow_apply_cb(assignblk[depnode.element]) - read.update(elements) - modifier = True - - # If it's not a modifier affblock, reinject current element - if not modifier: - read = set([FollowExpr(True, depnode.element)]) - - # Build output - output = FollowExpr.to_depnodes(read, depnode.label, - depnode.line_nb - 1, modifier, - self.current_step) - return output - - def _resolve_intrablock_dep(self, depdict): - """Resolve the dependencies of nodes in @depdict.pending inside - @depdict.label 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 + def _track_exprs(self, state, assignblk, line_nb): + """Track pending expression in an assignblock""" + future_pending = {} + node_resolved = set() + for dst, src in assignblk.iteritems(): + # Only track pending + if dst not in state.pending: continue - - if depdict.is_head(depnode): - depdict.pending.add(depnode) - # A head cannot have dependencies inside the current IRblock + # Track IRDst in implicit mode only + if dst == self._ira.IRDst and not self._implicit: continue + assert dst not in node_resolved + node_resolved.add(dst) + dependencies = self._follow_apply_cb(src) - # Find dependency of the current depnode - sub_depnodes = self._direct_depnode_dependencies(depnode) - depdict.cache[depnode] = FollowExpr.extract_depnodes(sub_depnodes) + state.link_element(dst, line_nb) + state.link_dependencies(dst, line_nb, + dependencies, future_pending) - # Add to the worklist its dependencies - todo.update(FollowExpr.extract_depnodes(sub_depnodes, - only_follow=True)) + # Update pending nodes + state.remove_pendings(node_resolved) + state.add_pendings(future_pending) - # Pending states will be overriden in cache - for depnode in depdict.pending: - try: - del depdict.cache[depnode] - except KeyError: - continue + def _compute_intrablock(self, state): + """Follow dependencies tracked in @state in the current irbloc + @state: instance of DependencyState""" - def _get_previousblocks(self, label): - """Return an iterator on predecessors blocks of @label, with their - lengths""" - preds = self._ira.graph.predecessors_iter(label) - for pred_label in preds: - length = len(self._get_irs(pred_label)) - yield (pred_label, length) - - def _compute_interblock_dep(self, depnodes, heads): - """Create a DependencyDict from @depnodes, and propagate - DependencyDicts through all blocs - """ - # Create a DependencyDict which will only contain our depnodes - current_depdict = DependencyDict(list(depnodes)[0].label, []) - current_depdict.pending.update(depnodes) + irb = self._ira.blocs[state.label] + line_nb = len(irb.irs) if state.line_nb is None else state.line_nb - # Init the work list - done = {} - todo = deque([current_depdict]) - - while todo: - depdict = todo.popleft() - - # Update the dependencydict until fixed point is reached - self._resolve_intrablock_dep(depdict) - self.inc_step() - - # Clean irrelevant path - depdict.filter_unmodifier_loops(self._implicit, self._ira.IRDst) - - # Avoid infinite loops - label = depdict.label - if depdict in done.get(label, []): - continue - done.setdefault(label, []).append(depdict) - - # No more dependencies - if len(depdict.pending) == 0: - yield depdict.copy() - continue - - # Has a predecessor ? - is_final = True - - # Propagate the DependencyDict to all parents - for label, irb_len in self._get_previousblocks(depdict.label): - is_final = False - - # Duplicate the DependencyDict - new_depdict = depdict.extend(label) - - if self._implicit: - # Implicit dependencies: IRDst will be link with heads - implicit_depnode = DependencyNode(label, self._ira.IRDst, - irb_len, - self.current_step, - modifier=False) - - # 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, - self.current_step) - # The new node has to be analysed - new_depdict.cache[depnode_head] = set([new_depnode]) - new_depdict.pending.add(new_depnode) - - # Handle implicit dependencies - if self._implicit: - new_depdict.cache[depnode_head].add(implicit_depnode) - new_depdict.pending.add(implicit_depnode) - - # Manage the new element - todo.append(new_depdict) - - # Return the node if it's a final one, ie. it's a head (in graph - # or defined by caller) - if is_final or depdict.label in heads: - yield depdict.copy() + for cur_line_nb, assignblk in reversed(list(enumerate(irb.irs[:line_nb]))): + self._track_exprs(state, assignblk, cur_line_nb) def get(self, label, elements, line_nb, heads): """Compute the dependencies of @elements at line number @line_nb in @@ -976,32 +595,34 @@ class DependencyGraph(object): @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, - self.current_step)) + pending = {element: set() for element in elements} + state = DependencyState(label, elements, pending, line_nb) + todo = set([state]) + done = set() + dpResultcls = DependencyResultImplicit if self._implicit else DependencyResult - # Compute final depdicts - depdicts = self._compute_interblock_dep(input_depnodes, heads) - - # Unify solutions - unified = [] - cls_res = DependencyResultImplicit if self._implicit else \ - DependencyResult - - for final_depdict in depdicts: - # Keep only relevant nodes - final_depdict.clean_modifiers_in_cache(input_depnodes) - 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 cls_res(self._ira, final_depdict, input_depnodes) + while todo: + state = todo.pop() + self._compute_intrablock(state) + done_state = state.get_done_state() + if done_state in done: + continue + done.add(done_state) + if (not state.pending or + state.label in heads or + not self._ira.graph.predecessors(state.label)): + yield dpResultcls(state, self._ira) + if not state.pending: + continue + + if self._implicit: + # Force IRDst to be tracked, except in the input block + state.pending[self._ira.IRDst] = set() + + # Propagate state to parents + for pred in self._ira.graph.predecessors_iter(state.label): + todo.add(state.extend(pred)) def get_from_depnodes(self, depnodes, heads): """Alias for the get() method. Use the attributes of @depnodes as @@ -1013,12 +634,3 @@ class DependencyGraph(object): lead = list(depnodes)[0] elements = set(depnode.element for depnode in depnodes) return self.get(lead.label, elements, lead.line_nb, heads) - - def 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 - """ - return self.get(label, elements, len(self._get_irs(label)), heads) diff --git a/test/analysis/depgraph.py b/test/analysis/depgraph.py index fafae1fb..f1d9151c 100644 --- a/test/analysis/depgraph.py +++ b/test/analysis/depgraph.py @@ -1,18 +1,20 @@ """Regression test module for DependencyGraph""" -from miasm2.expression.expression import ExprId, ExprInt32, ExprAff, ExprCond +from miasm2.expression.expression import ExprId, ExprInt32, ExprAff, ExprCond, \ + ExprInt from miasm2.core.asmbloc import asm_label from miasm2.ir.analysis import ira from miasm2.ir.ir import ir, irbloc, AssignBlock from miasm2.core.graph import DiGraph -from miasm2.analysis.depgraph import DependencyNode, DependencyGraph,\ - DependencyDict +from miasm2.analysis.depgraph import DependencyNode, DependencyGraph from itertools import count +from pdb import pm +import re -EMULATION=True +EMULATION = True try: import z3 except ImportError: - EMULATION=False + EMULATION = False STEP_COUNTER = count() A = ExprId("a") @@ -30,9 +32,9 @@ PC = ExprId("pc") SP = ExprId("sp") CST0 = ExprInt32(0x0) -CST1 = ExprInt32(0x11) -CST2 = ExprInt32(0x12) -CST3 = ExprInt32(0x13) +CST1 = ExprInt32(0x1) +CST2 = ExprInt32(0x2) +CST3 = ExprInt32(0x3) CST22 = ExprInt32(0x22) CST23 = ExprInt32(0x23) CST24 = ExprInt32(0x24) @@ -97,117 +99,138 @@ class IRATest(ira): return set([self.ret_reg, self.sp]) -class GraphTest(DiGraph): +def bloc2graph(irgraph, label=False, lines=True): + """Render dot graph of @blocks""" - """Fake graph representation class for test cases""" + escape_chars = re.compile('[' + re.escape('{}') + ']') + label_attr = 'colspan="2" align="center" bgcolor="grey"' + edge_attr = 'label = "%s" color="%s" style="bold"' + td_attr = 'align="left"' + block_attr = 'shape="Mrecord" fontname="Courier New"' - def __init__(self, pira): - self.ira = pira - super(GraphTest, self).__init__() + out = ["digraph asm_graph {"] + fix_chars = lambda x: '\\' + x.group() - def __eq__(self, graph): - if (len(self._nodes) != len(graph.nodes()) or - len(self._edges) != len(graph.edges())): - return False - - if (set([n.nostep_repr for n in self._nodes]) != - set([n.nostep_repr for n in graph.nodes()])): - return False - if (sorted([(src.nostep_repr, dst.nostep_repr) - for (src, dst) in self._edges]) - != sorted([(src.nostep_repr, dst.nostep_repr) - for (src, dst) in graph.edges()])): - return False - return True + # Generate basic blocks + out_blocks = [] + for label in irgraph.graph.nodes(): + if isinstance(label, asm_label): + label_name = label.name + else: + label_name = str(label) - def node2str(self, node): - if isinstance(node, asm_label): - if node not in self.ira.blocs: - return str(node) + if hasattr(irgraph, 'blocs'): + irblock = irgraph.blocs[label] + else: + irblock = None + if isinstance(label, asm_label): + out_block = '%s [\n' % label.name + else: + out_block = '%s [\n' % label + out_block += "%s " % block_attr + out_block += 'label =<<table border="0" cellborder="0" cellpadding="3">' + + block_label = '<tr><td %s>%s</td></tr>' % ( + label_attr, label_name) + block_html_lines = [] + if lines and irblock is not None: + for assignblk in irblock.irs: + for dst, src in assignblk.iteritems(): + if False: + out_render = "%.8X</td><td %s> " % (0, td_attr) + else: + out_render = "" + out_render += escape_chars.sub(fix_chars, "%s = %s" % (dst, src)) + block_html_lines.append(out_render) + block_html_lines.append(" ") + block_html_lines.pop() + block_html_lines = ('<tr><td %s>' % td_attr + + ('</td></tr><tr><td %s>' % td_attr).join(block_html_lines) + + '</td></tr>') + out_block += "%s " % block_label + out_block += block_html_lines + "</table>> ];" + out_blocks.append(out_block) + + out += out_blocks + # Generate links + for src, dst in irgraph.graph.edges(): + if isinstance(src, asm_label): + src_name = src.name + else: + src_name = str(src) + if isinstance(dst, asm_label): + dst_name = dst.name else: - return str(self.ira.blocs[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, linenb, next(STEP_COUNTER)) - for linenb 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 " [+] Test dictionary equality" -DNA = DependencyNode(LBL2, A, 0, next(STEP_COUNTER)) -DNB = DependencyNode(LBL1, B, 1, next(STEP_COUNTER)) -DNC = DependencyNode(LBL1, C, 0, next(STEP_COUNTER), True) -DNB2 = DependencyNode(LBL1, B, 1, next(STEP_COUNTER)) -DNC2 = DependencyNode(LBL1, C, 0, next(STEP_COUNTER), True) -DNB3 = DependencyNode(LBL1, B, 1, next(STEP_COUNTER)) -DNC3 = DependencyNode(LBL1, C, 0, next(STEP_COUNTER), True) - -DDCT1 = DependencyDict(LBL1, []) -DDCT1.cache.update({DNA: set([DNB]), DNB: set([DNC])}) - -DDCT2 = DDCT1.extend(LBL1) -DDCT2.cache.update({DNA: set([DNB]), DNB: set([DNC]), - DNC: set([DNB2]), DNB2: set([DNC2]) - }) - -DDCT3 = DDCT2.extend(LBL1) -DDCT3.cache.update( - {DNA: set([DNB]), DNB: set([DNC]), - DNC: set([DNB2]), DNB2: set([DNC2]), - DNC2: set([DNB3]), DNB3: set([DNC3])}) - -assert not DDCT1.__eq__(DDCT2) -assert DDCT2.__eq__(DDCT3) - -print "[+] DependencyDict OK !" -print "[+] Structures OK !" + dst_name = str(dst) + + edge_color = "black" + out.append('%s -> %s' % (src_name, + dst_name) + + '[' + edge_attr % ("", edge_color) + '];') + + out.append("}") + return '\n'.join(out) + + +def dg2graph(graph, label=False, lines=True): + """Render dot graph of @blocks""" + + escape_chars = re.compile('[' + re.escape('{}') + ']') + label_attr = 'colspan="2" align="center" bgcolor="grey"' + edge_attr = 'label = "%s" color="%s" style="bold"' + td_attr = 'align="left"' + block_attr = 'shape="Mrecord" fontname="Courier New"' + + out = ["digraph asm_graph {"] + fix_chars = lambda x: '\\' + x.group() + + # Generate basic blocks + out_blocks = [] + for label in graph.nodes(): + if isinstance(label, DependencyNode): + label_name = "%s %s %s" % (label.label.name, + label.element, + label.line_nb) + else: + label_name = str(label) + out_block = '%s [\n' % hash(label) + out_block += "%s " % block_attr + out_block += 'label =<<table border="0" cellborder="0" cellpadding="3">' + + block_label = '<tr><td %s>%s</td></tr>' % ( + label_attr, label_name) + block_html_lines = [] + block_html_lines = ('<tr><td %s>' % td_attr + + ('</td></tr><tr><td %s>' % td_attr).join(block_html_lines) + + '</td></tr>') + out_block += "%s " % block_label + out_block += block_html_lines + "</table>> ];" + out_blocks.append(out_block) + + out += out_blocks + # Generate links + for src, dst in graph.edges(): + edge_color = "black" + out.append('%s -> %s ' % (hash(src), + hash(dst)) + + '[' + edge_attr % ("", edge_color) + '];') + + out.append("}") + return '\n'.join(out) + + +print " [+] Test dictionnary equality" +DNA = DependencyNode(LBL2, A, 0) +DNB = DependencyNode(LBL1, B, 1) +DNC = DependencyNode(LBL1, C, 0) +DNB2 = DependencyNode(LBL1, B, 1) +DNC2 = DependencyNode(LBL1, C, 0) +DNB3 = DependencyNode(LBL1, B, 1) +DNC3 = DependencyNode(LBL1, C, 0) # 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)]]) @@ -221,7 +244,6 @@ 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)]]) @@ -236,7 +258,6 @@ 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)]]) @@ -254,7 +275,6 @@ G3_IRA.blocs = dict([(irb.label, irb) for irb in [G3_IRB0, G3_IRB1, # 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)], @@ -274,7 +294,6 @@ 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)], @@ -293,7 +312,6 @@ 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)]]) @@ -306,7 +324,6 @@ 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)]]) @@ -321,7 +338,6 @@ 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)]]) @@ -338,7 +354,6 @@ G8_IRA.blocs = dict([(irb.label, irb) for irb in [G8_IRB0, G8_IRB1, G8_IRB2]]) # 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)]]) @@ -351,7 +366,6 @@ G10_IRA.blocs = dict([(irb.label, irb) for irb in [G10_IRB1, G10_IRB2]]) # graph 11 G11_IRA = IRATest() -G11_IRA.g = GraphTest(G11_IRA) G11_IRB0 = gen_irbloc(LBL0, [[ExprAff(A, CST1), ExprAff(B, CST2)]]) @@ -368,7 +382,6 @@ G11_IRA.blocs = dict([(irb.label, irb) # graph 12 G12_IRA = IRATest() -G12_IRA.g = GraphTest(G12_IRA) G12_IRB0 = gen_irbloc(LBL0, [[ExprAff(B, CST1)]]) G12_IRB1 = gen_irbloc(LBL1, [[ExprAff(A, B)], [ExprAff(B, B + CST2)]]) @@ -385,7 +398,6 @@ G12_IRA.blocs = dict([(irb.label, irb) for irb in [G12_IRB0, G12_IRB1, # graph 13 G13_IRA = IRATest() -G13_IRA.g = GraphTest(G13_IRA) G13_IRB0 = gen_irbloc(LBL0, [[ExprAff(A, CST1)], #[ExprAff(B, A)], @@ -414,7 +426,6 @@ G13_IRA.blocs = dict([(irb.label, irb) for irb in [G13_IRB0, G13_IRB1, # graph 14 G14_IRA = IRATest() -G14_IRA.g = GraphTest(G14_IRA) G14_IRB0 = gen_irbloc(LBL0, [[ExprAff(A, CST1)], [ExprAff(G14_IRA.IRDst, @@ -445,7 +456,6 @@ G14_IRA.blocs = dict([(irb.label, irb) for irb in [G14_IRB0, G14_IRB1, # graph 16 G15_IRA = IRATest() -G15_IRA.g = GraphTest(G15_IRA) G15_IRB0 = gen_irbloc(LBL0, [[ExprAff(A, CST1)]]) G15_IRB1 = gen_irbloc(LBL1, [[ExprAff(D, A + B)], @@ -463,7 +473,6 @@ G15_IRA.blocs = dict([(irb.label, irb) for irb in [G15_IRB0, G15_IRB1, # graph 16 G16_IRA = IRATest() -G16_IRA.g = GraphTest(G16_IRA) G16_IRB0 = gen_irbloc(LBL0, [[ExprAff(A, CST1)]]) G16_IRB1 = gen_irbloc(LBL1, [[ExprAff(R, D)]]) @@ -488,7 +497,6 @@ G16_IRA.blocs = dict([(irb.label, irb) for irb in [G16_IRB0, G16_IRB1, # graph 17 G17_IRA = IRATest() -G17_IRA.g = GraphTest(G17_IRA) G17_IRB0 = gen_irbloc(LBL0, [[ExprAff(A, CST1), ExprAff(D, CST2)]]) @@ -503,627 +511,518 @@ G17_IRA.blocs = dict([(irb.label, irb) for irb in [G17_IRB0, G17_IRB1, G17_IRB2]]) # Test graph 1 - -G1_TEST1 = GraphTest(G1_IRA) - G1_TEST1_DN1 = DependencyNode( - G1_IRB2.label, A, len(G1_IRB2.irs), next(STEP_COUNTER)) -G1_TEST1_DN2 = DependencyNode(G1_IRB2.label, B, 0, next(STEP_COUNTER)) -G1_TEST1_DN3 = DependencyNode(G1_IRB1.label, C, 0, next(STEP_COUNTER)) -G1_TEST1_DN4 = DependencyNode(G1_IRB0.label, CST1, 0, next(STEP_COUNTER)) - -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_IRB2.label, A, len(G1_IRB2.irs)) G1_INPUT = (set([G1_TEST1_DN1]), set([G1_IRB0.label])) -G1_OUTPUT = {"graph": [G1_TEST1], - "emul": [{A: CST1}], - "unresolved": [set()], - "has_loop": [False]} - # Test graph 2 -G2_TEST1 = GraphTest(G2_IRA) - G2_TEST1_DN1 = DependencyNode( - G2_IRB2.label, A, len(G2_IRB2.irs), next(STEP_COUNTER)) -G2_TEST1_DN2 = DependencyNode(G2_IRB2.label, B, 0, next(STEP_COUNTER)) -G2_TEST1_DN3 = DependencyNode(G2_IRB2.label, C, 0, next(STEP_COUNTER)) -G2_TEST1_DN4 = DependencyNode(G2_IRB1.label, CST2, 0, next(STEP_COUNTER)) -G2_TEST1_DN5 = DependencyNode(G2_IRB0.label, CST1, 0, next(STEP_COUNTER)) - -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_IRB2.label, A, len(G2_IRB2.irs)) G2_INPUT = (set([G2_TEST1_DN1]), set([G2_IRB0.label])) -G2_OUTPUT = {"graph": [G2_TEST1], - "emul": [{A: ExprInt32(int(CST1.arg) + int(CST2.arg))}], - "unresolved": [set()], - "has_loop": [False]} # Test graph 3 -G3_TEST1_0 = GraphTest(G3_IRA) -G3_TEST1_1 = GraphTest(G3_IRA) - G3_TEST1_0_DN1 = DependencyNode( - G3_IRB3.label, A, len(G3_IRB3.irs), next(STEP_COUNTER)) -G3_TEST1_0_DN2 = DependencyNode(G3_IRB3.label, B, 0, next(STEP_COUNTER)) -G3_TEST1_0_DN3 = DependencyNode(G3_IRB3.label, C, 0, next(STEP_COUNTER)) -G3_TEST1_0_DN4 = DependencyNode(G3_IRB2.label, CST3, 0, next(STEP_COUNTER)) -G3_TEST1_0_DN5 = DependencyNode(G3_IRB0.label, CST1, 0, next(STEP_COUNTER)) - -G3_TEST1_1_DN2 = DependencyNode(G3_IRB3.label, B, 0, next(STEP_COUNTER)) -G3_TEST1_1_DN3 = DependencyNode(G3_IRB3.label, C, 0, next(STEP_COUNTER)) -G3_TEST1_1_DN4 = DependencyNode(G3_IRB1.label, CST2, 0, next(STEP_COUNTER)) -G3_TEST1_1_DN5 = DependencyNode(G3_IRB0.label, CST1, 0, next(STEP_COUNTER)) - -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_0_DN1) -G3_TEST1_1.add_uniq_edge(G3_TEST1_1_DN3, G3_TEST1_0_DN1) + G3_IRB3.label, A, len(G3_IRB3.irs)) G3_INPUT = (set([G3_TEST1_0_DN1]), set([G3_IRB0.label])) -G3_OUTPUT = {"graph": [G3_TEST1_0, G3_TEST1_1], - "emul": [{A: ExprInt32(int(CST1.arg) + int(CST3.arg))}, - {A: ExprInt32(int(CST1.arg) + int(CST2.arg))}], - "unresolved": [set(), - set()], - "has_loop": [False, False]} - # Test graph 4 -G4_TEST1 = GraphTest(G4_IRA) - G4_TEST1_DN1 = DependencyNode( - G4_IRB2.label, A, len(G2_IRB0.irs), next(STEP_COUNTER)) -G4_TEST1_DN2 = DependencyNode(G4_IRB2.label, B, 0, next(STEP_COUNTER)) -G4_TEST1_DN3 = DependencyNode(G4_IRB0.label, B, 0, 10) -G4_TEST1_DN4 = DependencyNode(G4_IRB0.label, G4_IRA.IRDst, 0, 0) - -G4_TEST1.add_uniq_edge(G4_TEST1_DN2, G4_TEST1_DN1) + G4_IRB2.label, A, len(G2_IRB0.irs)) G4_INPUT = (set([G4_TEST1_DN1]), set([G4_IRB0.label])) -G4_OUTPUT = {"graph": [G4_TEST1], - "emul": [{A: B_INIT}], - "unresolved": [set([G4_TEST1_DN3.nostep_repr])], - "has_loop": [False]} - # Test graph 5 -G5_TEST1_0 = GraphTest(G5_IRA) -G5_TEST1_1 = GraphTest(G5_IRA) - G5_TEST1_0_DN1 = DependencyNode( - G5_IRB2.label, A, len(G5_IRB2.irs), next(STEP_COUNTER)) -G5_TEST1_0_DN2 = DependencyNode(G5_IRB2.label, B, 0, next(STEP_COUNTER)) -G5_TEST1_0_DN3 = DependencyNode(G5_IRB1.label, B, 0, next(STEP_COUNTER)) -G5_TEST1_0_DN4 = DependencyNode(G5_IRB0.label, CST1, 0, next(STEP_COUNTER)) -G5_TEST1_0_DN5 = DependencyNode(G5_IRB1.label, CST2, 0, next(STEP_COUNTER)) - -G5_TEST1_0.add_uniq_edge(G5_TEST1_0_DN4, G5_TEST1_0_DN3) -G5_TEST1_0.add_uniq_edge(G5_TEST1_0_DN3, G5_TEST1_0_DN2) -G5_TEST1_0.add_uniq_edge(G5_TEST1_0_DN5, G5_TEST1_0_DN2) -G5_TEST1_0.add_uniq_edge(G5_TEST1_0_DN2, G5_TEST1_0_DN1) - -G5_TEST1_1_DN3 = DependencyNode(G5_IRB1.label, B, 0, next(STEP_COUNTER)) -G5_TEST1_1_DN5 = DependencyNode(G5_IRB1.label, CST2, 0, next(STEP_COUNTER)) - -G5_TEST1_1.add_uniq_edge(G5_TEST1_0_DN4, G5_TEST1_1_DN3) -G5_TEST1_1.add_uniq_edge(G5_TEST1_1_DN3, G5_TEST1_0_DN3) -G5_TEST1_1.add_uniq_edge(G5_TEST1_1_DN5, G5_TEST1_0_DN3) -G5_TEST1_1.add_uniq_edge(G5_TEST1_0_DN3, G5_TEST1_0_DN2) -G5_TEST1_1.add_uniq_edge(G5_TEST1_0_DN5, G5_TEST1_0_DN2) -G5_TEST1_1.add_uniq_edge(G5_TEST1_0_DN2, G5_TEST1_0_DN1) + G5_IRB2.label, A, len(G5_IRB2.irs)) G5_INPUT = (set([G5_TEST1_0_DN1]), set([G5_IRB0.label])) -G5_OUTPUT = {"graph": [G5_TEST1_0, G5_TEST1_1], - "emul": [{A: CST35}, {A: CST23}], - "unresolved": [set(), set()], - "has_loop": [True, False]} - # Test graph 6 -G6_TEST1_0 = GraphTest(G6_IRA) - G6_TEST1_0_DN1 = DependencyNode( - G6_IRB1.label, A, len(G6_IRB1.irs), next(STEP_COUNTER)) -G6_TEST1_0_DN2 = DependencyNode(G6_IRB1.label, B, 0, next(STEP_COUNTER)) -G6_TEST1_0_DN3 = DependencyNode(G6_IRB0.label, CST1, 0, next(STEP_COUNTER)) - - -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_IRB1.label, A, len(G6_IRB1.irs)) G6_INPUT = (set([G6_TEST1_0_DN1]), set([G6_IRB0.label])) -G6_OUTPUT = {"graph": [G6_TEST1_0], - "emul": [{A: CST1}], - "unresolved": [set()], - "has_loop": [False]} - # Test graph 7 -G7_TEST1_0 = GraphTest(G7_IRA) - G7_TEST1_0_DN1 = DependencyNode( - G7_IRB2.label, A, len(G7_IRB2.irs), next(STEP_COUNTER)) -G7_TEST1_0_DN2 = DependencyNode(G7_IRB1.label, B, 1, next(STEP_COUNTER)) -G7_TEST1_0_DN3 = DependencyNode(G7_IRB1.label, C, 0, next(STEP_COUNTER)) -G7_TEST1_0_DN4 = DependencyNode(G7_IRB0.label, CST1, 0, next(STEP_COUNTER)) - - -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_IRB2.label, D, len(G7_IRB2.irs)) G7_INPUT = (set([G7_TEST1_0_DN1]), set([G7_IRB0.label])) -G7_OUTPUT = {"graph": [G7_TEST1_0], - "emul": [{A: CST1}], - "unresolved": [set()], - "has_loop": [False]} - # Test graph 8 -G8_TEST1_0 = GraphTest(G8_IRA) -G8_TEST1_1 = GraphTest(G8_IRA) - G8_TEST1_0_DN1 = DependencyNode( - G8_IRB2.label, A, len(G8_IRB2.irs), next(STEP_COUNTER)) -G8_TEST1_0_DN2 = DependencyNode(G8_IRB2.label, B, 0, next(STEP_COUNTER)) -G8_TEST1_0_DN3 = DependencyNode(G8_IRB1.label, C, 0, next(STEP_COUNTER)) -G8_TEST1_0_DN4 = DependencyNode(G8_IRB0.label, CST1, 0, next(STEP_COUNTER)) - -G8_TEST1_1_DN1 = DependencyNode( - G8_IRB2.label, A, len(G8_IRB2.irs), next(STEP_COUNTER)) -G8_TEST1_1_DN2 = DependencyNode(G8_IRB2.label, B, 0, next(STEP_COUNTER)) -G8_TEST1_1_DN3 = DependencyNode(G8_IRB1.label, C, 0, next(STEP_COUNTER)) -G8_TEST1_1_DN4 = DependencyNode(G8_IRB1.label, D, 1, next(STEP_COUNTER)) - -G8_TEST1_1_DN5 = DependencyNode(G8_IRB0.label, D, 0, next(STEP_COUNTER)) - - -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_IRB2.label, A, len(G8_IRB2.irs)) G8_INPUT = (set([G8_TEST1_0_DN1]), set([G3_IRB0.label])) -G8_OUTPUT = {"graph": [G8_TEST1_0, G8_TEST1_1], - "emul": [{A: D_INIT}, {A: CST1}], - "unresolved": [set([G8_TEST1_1_DN5.nostep_repr]), set()], - "has_loop": [True, False]} - # Test 9: Multi elements -G9_TEST1_0 = GraphTest(G8_IRA) -G9_TEST1_1 = GraphTest(G8_IRA) - G9_TEST1_0_DN1 = DependencyNode( - G8_IRB2.label, A, len(G8_IRB2.irs), next(STEP_COUNTER)) -G9_TEST1_0_DN2 = DependencyNode(G8_IRB2.label, B, 0, next(STEP_COUNTER)) -G9_TEST1_0_DN3 = DependencyNode(G8_IRB1.label, C, 0, next(STEP_COUNTER)) -G9_TEST1_0_DN4 = DependencyNode(G8_IRB0.label, CST1, 0, next(STEP_COUNTER)) + G8_IRB2.label, A, len(G8_IRB2.irs)) G9_TEST1_0_DN5 = DependencyNode( - G8_IRB2.label, C, len(G8_IRB2.irs), next(STEP_COUNTER)) -G9_TEST1_0_DN6 = DependencyNode(G8_IRB1.label, D, 1, next(STEP_COUNTER)) - -G9_TEST1_1_DN1 = DependencyNode( - G8_IRB2.label, A, len(G8_IRB2.irs), next(STEP_COUNTER)) -G9_TEST1_1_DN2 = DependencyNode(G8_IRB2.label, B, 0, next(STEP_COUNTER)) -G9_TEST1_1_DN3 = DependencyNode(G8_IRB1.label, C, 0, next(STEP_COUNTER)) -G9_TEST1_1_DN4 = DependencyNode(G8_IRB1.label, D, 1, next(STEP_COUNTER)) -G9_TEST1_1_DN5 = DependencyNode( - G8_IRB2.label, C, len(G8_IRB2.irs), next(STEP_COUNTER)) -G9_TEST1_1_DN6 = DependencyNode(G8_IRB1.label, D, 1, next(STEP_COUNTER)) - - -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_DN6, 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) + G8_IRB2.label, C, len(G8_IRB2.irs)) G9_INPUT = (set([G9_TEST1_0_DN1, G9_TEST1_0_DN5]), set([G8_IRB0.label])) -G9_OUTPUT = {"graph": [G9_TEST1_1, G9_TEST1_0], - "emul": [{A: D_INIT, C: D_INIT}, - {A: CST1, C: D_INIT}], - "unresolved": [set([G8_TEST1_1_DN5.nostep_repr]), - set([G8_TEST1_1_DN5.nostep_repr])], - "has_loop": [True, False]} - # Test 10: loop at beginning -G10_TEST1_0 = GraphTest(G10_IRA) -G10_TEST1_1 = GraphTest(G10_IRA) - G10_TEST1_0_DN1 = DependencyNode( - G10_IRB2.label, A, len(G10_IRB2.irs), next(STEP_COUNTER)) -G10_TEST1_0_DN2 = DependencyNode(G10_IRB2.label, B, 0, next(STEP_COUNTER)) -G10_TEST1_0_DN3 = DependencyNode(G10_IRB1.label, B, 0, next(STEP_COUNTER)) -G10_TEST1_0_DN4 = DependencyNode(G10_IRB1.label, CST2, 0, next(STEP_COUNTER)) - -G10_TEST1_0.add_uniq_edge(G10_TEST1_0_DN3, G10_TEST1_0_DN2) -G10_TEST1_0.add_uniq_edge(G10_TEST1_0_DN4, G10_TEST1_0_DN2) -G10_TEST1_0.add_uniq_edge(G10_TEST1_0_DN2, G10_TEST1_0_DN1) - -G10_TEST1_1_DN3 = DependencyNode(G10_IRB1.label, B, 0, next(STEP_COUNTER)) -G10_TEST1_1_DN4 = DependencyNode(G10_IRB1.label, CST2, 0, next(STEP_COUNTER)) - -G10_TEST1_1.add_uniq_edge(G10_TEST1_1_DN3, G10_TEST1_0_DN3) -G10_TEST1_1.add_uniq_edge(G10_TEST1_1_DN4, G10_TEST1_0_DN3) -G10_TEST1_1.add_uniq_edge(G10_TEST1_0_DN3, G10_TEST1_0_DN2) -G10_TEST1_1.add_uniq_edge(G10_TEST1_0_DN4, G10_TEST1_0_DN2) -G10_TEST1_1.add_uniq_edge(G10_TEST1_0_DN2, G10_TEST1_0_DN1) + G10_IRB2.label, A, len(G10_IRB2.irs)) G10_INPUT = (set([G10_TEST1_0_DN1]), set([G10_IRB1.label])) -G10_OUTPUT = {"graph": [G10_TEST1_0, G10_TEST1_1], - "emul": [{A: B_INIT + CST24}, {A: B_INIT + CST2}], - "unresolved": [set([G10_TEST1_0_DN3.nostep_repr]), - set([G10_TEST1_0_DN3.nostep_repr])], - "has_loop": [True, False]} - # Test 11: no dual bloc emulation -G11_TEST1 = GraphTest(G11_IRA) G11_TEST1_DN1 = DependencyNode( - G11_IRB2.label, A, len(G11_IRB2.irs), next(STEP_COUNTER)) -G11_TEST1_DN2 = DependencyNode(G11_IRB2.label, A, 0, next(STEP_COUNTER)) -G11_TEST1_DN3 = DependencyNode(G11_IRB2.label, B, 0, next(STEP_COUNTER)) -G11_TEST1_DN4 = DependencyNode(G11_IRB1.label, A, 0, next(STEP_COUNTER)) -G11_TEST1_DN5 = DependencyNode(G11_IRB1.label, B, 0, next(STEP_COUNTER)) -G11_TEST1_DN6 = DependencyNode(G11_IRB0.label, CST1, 0, next(STEP_COUNTER)) -G11_TEST1_DN7 = DependencyNode(G11_IRB0.label, CST2, 0, next(STEP_COUNTER)) - -G11_TEST1.add_uniq_edge(G11_TEST1_DN7, G11_TEST1_DN5) -G11_TEST1.add_uniq_edge(G11_TEST1_DN6, G11_TEST1_DN4) -G11_TEST1.add_uniq_edge(G11_TEST1_DN5, G11_TEST1_DN2) -G11_TEST1.add_uniq_edge(G11_TEST1_DN4, G11_TEST1_DN3) -G11_TEST1.add_uniq_edge(G11_TEST1_DN3, G11_TEST1_DN1) -G11_TEST1.add_uniq_edge(G11_TEST1_DN2, G11_TEST1_DN1) + G11_IRB2.label, A, len(G11_IRB2.irs)) G11_INPUT = (set([G11_TEST1_DN1]), set([G11_IRB0.label])) -G11_OUTPUT = {"graph": [G11_TEST1], - "emul": [{A: ExprInt32(0x1)}], - "unresolved": [set()], - "has_loop": [False]} # Test graph 12 -G12_TEST1_0 = GraphTest(G12_IRA) -G12_TEST1_1 = GraphTest(G12_IRA) - -G12_TEST1_0_DN1 = DependencyNode(G12_IRB2.label, B, 1, next(STEP_COUNTER)) -G12_TEST1_0_DN2 = DependencyNode(G12_IRB2.label, A, 0, next(STEP_COUNTER)) -G12_TEST1_0_DN3 = DependencyNode(G12_IRB1.label, B, 0, next(STEP_COUNTER)) -G12_TEST1_0_DN4 = DependencyNode(G12_IRB0.label, CST1, 0, next(STEP_COUNTER)) - - -G12_TEST1_0.add_uniq_edge(G12_TEST1_0_DN2, G12_TEST1_0_DN1) -G12_TEST1_0.add_uniq_edge(G12_TEST1_0_DN3, G12_TEST1_0_DN2) -G12_TEST1_0.add_uniq_edge(G12_TEST1_0_DN4, G12_TEST1_0_DN3) - -G12_TEST1_1_DN3 = DependencyNode(G12_IRB1.label, B, 1, next(STEP_COUNTER)) -G12_TEST1_1_DN5 = DependencyNode(G12_IRB1.label, CST2, 1, next(STEP_COUNTER)) - -G12_TEST1_1.add_uniq_edge(G12_TEST1_0_DN4, G12_TEST1_1_DN3) -G12_TEST1_1.add_uniq_edge(G12_TEST1_1_DN5, G12_TEST1_0_DN3) -G12_TEST1_1.add_uniq_edge(G12_TEST1_1_DN3, G12_TEST1_0_DN3) -G12_TEST1_1.add_uniq_edge(G12_TEST1_0_DN3, G12_TEST1_0_DN2) -G12_TEST1_1.add_uniq_edge(G12_TEST1_0_DN2, G12_TEST1_0_DN1) - +G12_TEST1_0_DN1 = DependencyNode(G12_IRB2.label, B, 1) G12_INPUT = (set([G12_TEST1_0_DN1]), set([])) -G12_OUTPUT = {"graph": [G12_TEST1_0, G12_TEST1_1], - "emul": [{B: CST23}, {B: CST1}], - "unresolved": [set(), set()], - "has_loop": [True, False]} - # Test graph 13: # All filters -G13_TEST1_0 = GraphTest(G13_IRA) -G13_TEST1_1 = GraphTest(G13_IRA) - -G13_TEST1_0_DN1 = DependencyNode(G13_IRB0.label, CST1, 0, next(STEP_COUNTER)) -G13_TEST1_0_DN2 = DependencyNode(G13_IRB1.label, A, 0, next(STEP_COUNTER)) -G13_TEST1_0_DN3 = DependencyNode(G13_IRB3.label, C, 0, next(STEP_COUNTER)) -G13_TEST1_0_DN4 = DependencyNode(G13_IRB3.label, R, 1, next(STEP_COUNTER)) -G13_TEST1_0.add_uniq_edge(G13_TEST1_0_DN3, G13_TEST1_0_DN4) -G13_TEST1_0.add_uniq_edge(G13_TEST1_0_DN2, G13_TEST1_0_DN3) -G13_TEST1_0.add_uniq_edge(G13_TEST1_0_DN1, G13_TEST1_0_DN2) - -G13_TEST1_1_DN5 = DependencyNode(G13_IRB2.label, A, 0, next(STEP_COUNTER)) -G13_TEST1_1_DN6 = DependencyNode(G13_IRB2.label, CST3, 0, next(STEP_COUNTER)) -G13_TEST1_1_DN7 = DependencyNode(G13_IRB2.label, B, 1, next(STEP_COUNTER)) -G13_TEST1_1_DN8 = DependencyNode(G13_IRB2.label, CST3, 1, next(STEP_COUNTER)) - -G13_TEST1_1.add_uniq_edge(G13_TEST1_0_DN3, G13_TEST1_0_DN4) -G13_TEST1_1.add_uniq_edge(G13_TEST1_0_DN2, G13_TEST1_0_DN3) - -G13_TEST1_1.add_uniq_edge(G13_TEST1_1_DN7, G13_TEST1_0_DN2) -G13_TEST1_1.add_uniq_edge(G13_TEST1_1_DN8, G13_TEST1_0_DN2) -G13_TEST1_1.add_uniq_edge(G13_TEST1_1_DN5, G13_TEST1_1_DN7) -G13_TEST1_1.add_uniq_edge(G13_TEST1_1_DN6, G13_TEST1_1_DN7) - -G13_TEST1_1.add_uniq_edge(G13_TEST1_0_DN1, G13_TEST1_1_DN5) - -# Implicit dependencies - -G13_TEST2_0 = GraphTest(G13_IRA) -G13_TEST2_1 = GraphTest(G13_IRA) - -G13_TEST2_0_DN1 = DependencyNode(G13_IRB0.label, CST1, 0, next(STEP_COUNTER)) -G13_TEST2_0_DN2 = DependencyNode(G13_IRB1.label, A, 0, next(STEP_COUNTER)) -G13_TEST2_0_DN3 = DependencyNode(G13_IRB3.label, C, 0, next(STEP_COUNTER)) -G13_TEST2_0_DN4 = DependencyNode(G13_IRB3.label, R, 1, next(STEP_COUNTER)) -G13_TEST2_0_DN5 = DependencyNode(G13_IRB1.label, R, 1, next(STEP_COUNTER)) - -G13_TEST2_0.add_uniq_edge(G13_TEST2_0_DN3, G13_TEST2_0_DN4) -G13_TEST2_0.add_uniq_edge(G13_TEST2_0_DN2, G13_TEST2_0_DN3) -G13_TEST2_0.add_uniq_edge(G13_TEST2_0_DN1, G13_TEST2_0_DN2) -G13_TEST2_0.add_uniq_edge(G13_TEST2_0_DN5, G13_TEST2_0_DN3) - -G13_TEST2_1_DN5 = DependencyNode(G13_IRB2.label, A, 0, next(STEP_COUNTER)) -G13_TEST2_1_DN6 = DependencyNode(G13_IRB2.label, CST3, 0, next(STEP_COUNTER)) -G13_TEST2_1_DN7 = DependencyNode(G13_IRB2.label, B, 1, next(STEP_COUNTER)) -G13_TEST2_1_DN8 = DependencyNode(G13_IRB2.label, CST3, 1, next(STEP_COUNTER)) -G13_TEST2_1_DN9 = DependencyNode(G13_IRB1.label, R, 1, next(STEP_COUNTER)) - -G13_TEST2_1.add_uniq_edge(G13_TEST2_0_DN3, G13_TEST2_0_DN4) -G13_TEST2_1.add_uniq_edge(G13_TEST2_0_DN2, G13_TEST2_0_DN3) -G13_TEST2_1.add_uniq_edge(G13_TEST2_0_DN5, G13_TEST2_0_DN3) - -G13_TEST2_1.add_uniq_edge(G13_TEST2_1_DN7, G13_TEST2_0_DN2) -G13_TEST2_1.add_uniq_edge(G13_TEST2_1_DN8, G13_TEST2_0_DN2) -G13_TEST2_1.add_uniq_edge(G13_TEST2_1_DN5, G13_TEST2_1_DN7) -G13_TEST2_1.add_uniq_edge(G13_TEST2_1_DN6, G13_TEST2_1_DN7) - -G13_TEST2_1.add_uniq_edge(G13_TEST2_0_DN1, G13_TEST2_1_DN5) -G13_TEST2_1.add_uniq_edge(G13_TEST2_1_DN9, G13_TEST2_0_DN5) -G13_TEST2_1.add_uniq_edge(G13_TEST2_1_DN9, G13_TEST2_1_DN5) - - -DN13_UR_R = DependencyNode(G13_IRB0.label, R, 0, 0).nostep_repr +G13_TEST1_0_DN4 = DependencyNode(G13_IRB3.label, R, 1) G13_INPUT = (set([G13_TEST1_0_DN4]), set([])) -G13_OUTPUT = {"graph": [G13_TEST1_0, G13_TEST1_1], - "graph_implicit": [G13_TEST2_0, G13_TEST2_1], - "emul": [{R: CST37}, {R: CST1}], - "unresolved": [set(), set()], - "unresolved_implicit": [set([DN13_UR_R]), set([DN13_UR_R])], - "has_loop": [True, False]} - # Test graph 14 # All filters -G14_TEST1_0 = GraphTest(G14_IRA) -G14_TEST1_1 = GraphTest(G14_IRA) - -G14_TEST1_0_DN1 = DependencyNode(G14_IRB3.label, R, 1, next(STEP_COUNTER)) -G14_TEST1_0_DN2 = DependencyNode(G14_IRB3.label, D, 0, next(STEP_COUNTER)) -G14_TEST1_0_DN3 = DependencyNode(G14_IRB3.label, B, 0, next(STEP_COUNTER)) -G14_TEST1_0_DN4 = DependencyNode(G14_IRB1.label, A, 0, next(STEP_COUNTER)) -G14_TEST1_0_DN5 = DependencyNode(G14_IRB0.label, CST1, 0, next(STEP_COUNTER)) - -G14_TEST1_0.add_uniq_edge(G14_TEST1_0_DN2, G14_TEST1_0_DN1) -G14_TEST1_0.add_uniq_edge(G14_TEST1_0_DN3, G14_TEST1_0_DN1) - -G14_TEST1_0.add_uniq_edge(G14_TEST1_0_DN4, G14_TEST1_0_DN3) -G14_TEST1_0.add_uniq_edge(G14_TEST1_0_DN5, G14_TEST1_0_DN4) - -G14_TEST1_1_DN5 = DependencyNode(G14_IRB2.label, D, 1, next(STEP_COUNTER)) -G14_TEST1_1_DN6 = DependencyNode(G14_IRB2.label, CST1, 1, next(STEP_COUNTER)) -G14_TEST1_1_DN7 = DependencyNode(G14_IRB2.label, A, 0, next(STEP_COUNTER)) -#G14_TEST1_1_DN8 = DependencyNode( -# G14_IRB2.label, A, 0, next(STEP_COUNTER) + 1) -#G14_TEST1_1_DN9 = DependencyNode( -# G14_IRB0.label, CST1, 0, next(STEP_COUNTER) + 1) - -# 1 loop -G14_TEST1_1.add_uniq_edge(G14_TEST1_0_DN2, G14_TEST1_0_DN1) -G14_TEST1_1.add_uniq_edge(G14_TEST1_0_DN3, G14_TEST1_0_DN1) - -G14_TEST1_1.add_uniq_edge(G14_TEST1_0_DN4, G14_TEST1_0_DN3) -G14_TEST1_1.add_uniq_edge(G14_TEST1_1_DN5, G14_TEST1_0_DN4) -G14_TEST1_1.add_uniq_edge(G14_TEST1_1_DN6, G14_TEST1_0_DN4) -G14_TEST1_1.add_uniq_edge(G14_TEST1_1_DN7, G14_TEST1_1_DN5) -G14_TEST1_1.add_uniq_edge(G14_TEST1_0_DN5, G14_TEST1_1_DN7) - -G14_TEST1_1.add_uniq_edge(G14_TEST1_1_DN7, G14_TEST1_0_DN2) -# G14_TEST1_1.add_uniq_edge(G14_TEST1_1_DN5, G14_TEST1_1_DN8) - -# Implicit dependencies -G14_TEST2_0 = GraphTest(G14_IRA) -G14_TEST2_1 = GraphTest(G14_IRA) - -G14_TEST2_0_DN6 = DependencyNode(G14_IRB1.label, C, 1, next(STEP_COUNTER)) - -G14_TEST2_0.add_uniq_edge(G14_TEST1_0_DN2, G14_TEST1_0_DN1) -G14_TEST2_0.add_uniq_edge(G14_TEST1_0_DN3, G14_TEST1_0_DN1) - -G14_TEST2_0.add_uniq_edge(G14_TEST1_0_DN4, G14_TEST1_0_DN3) -G14_TEST2_0.add_uniq_edge(G14_TEST1_0_DN5, G14_TEST1_0_DN4) - -G14_TEST2_0.add_uniq_edge(G14_TEST2_0_DN6, G14_TEST1_0_DN3) -G14_TEST2_0.add_uniq_edge(G14_TEST2_0_DN6, G14_TEST1_0_DN2) - -# 1 loop -G14_TEST2_0_DN7 = DependencyNode(G14_IRB1.label, C, 1, next(STEP_COUNTER)) - -G14_TEST2_1.add_uniq_edge(G14_TEST1_0_DN2, G14_TEST1_0_DN1) -G14_TEST2_1.add_uniq_edge(G14_TEST1_0_DN3, G14_TEST1_0_DN1) - -G14_TEST2_1.add_uniq_edge(G14_TEST1_0_DN4, G14_TEST1_0_DN3) -G14_TEST2_1.add_uniq_edge(G14_TEST1_1_DN5, G14_TEST1_0_DN4) -G14_TEST2_1.add_uniq_edge(G14_TEST1_1_DN6, G14_TEST1_0_DN4) -G14_TEST2_1.add_uniq_edge(G14_TEST1_1_DN7, G14_TEST1_1_DN5) -G14_TEST2_1.add_uniq_edge(G14_TEST1_0_DN5, G14_TEST1_1_DN7) - -G14_TEST2_1.add_uniq_edge(G14_TEST1_1_DN7, G14_TEST1_0_DN2) - -G14_TEST2_1.add_uniq_edge(G14_TEST2_0_DN6, G14_TEST1_0_DN3) -G14_TEST2_1.add_uniq_edge(G14_TEST2_0_DN6, G14_TEST1_0_DN2) -DN14_UR_D = DependencyNode(G14_IRB0.label, D, 0, 0).nostep_repr -DN14_UR_C = DependencyNode(G14_IRB0.label, C, 0, 0).nostep_repr +G14_TEST1_0_DN1 = DependencyNode(G14_IRB3.label, R, 1) G14_INPUT = (set([G14_TEST1_0_DN1]), set([])) -G14_OUTPUT = {"graph": [G14_TEST1_0, G14_TEST1_1], - "graph_implicit": [G14_TEST2_0, G14_TEST2_1], - "emul": [{R: CST33}, {R: D_INIT + CST1}], - "unresolved": [set(), set([DN14_UR_D])], - "unresolved_implicit": [set([DN14_UR_C]), - set([DN14_UR_D, DN14_UR_C])], - "has_loop": [True, False]} - # Test graph 15 -G15_TEST1_0 = GraphTest(G15_IRA) -G15_TEST1_1 = GraphTest(G15_IRA) - -G15_TEST1_0_DN1 = DependencyNode(G15_IRB2.label, R, 1, next(STEP_COUNTER)) -G15_TEST1_0_DN2 = DependencyNode(G15_IRB2.label, B, 0, next(STEP_COUNTER)) -G15_TEST1_0_DN3 = DependencyNode(G15_IRB1.label, C, 2, next(STEP_COUNTER)) -G15_TEST1_0_DN4 = DependencyNode(G15_IRB1.label, D, 1, next(STEP_COUNTER)) -G15_TEST1_0_DN5 = DependencyNode(G15_IRB1.label, B, 0, next(STEP_COUNTER)) -G15_TEST1_0_DN6 = DependencyNode(G15_IRB1.label, A, 0, next(STEP_COUNTER)) -G15_TEST1_0_DN7 = DependencyNode(G15_IRB0.label, CST1, 0, next(STEP_COUNTER)) -G15_TEST1_0_DN8 = DependencyNode(G15_IRB1.label, C, 2, next(STEP_COUNTER)) -G15_TEST1_0_DN9 = DependencyNode(G15_IRB1.label, D, 1, next(STEP_COUNTER)) -G15_TEST1_0_DN10 = DependencyNode(G15_IRB1.label, B, 0, next(STEP_COUNTER)) - - -# 1 loop -G15_TEST1_0.add_uniq_edge(G15_TEST1_0_DN2, G15_TEST1_0_DN1) -G15_TEST1_0.add_uniq_edge(G15_TEST1_0_DN3, G15_TEST1_0_DN2) -G15_TEST1_0.add_uniq_edge(G15_TEST1_0_DN4, G15_TEST1_0_DN3) -G15_TEST1_0.add_uniq_edge(G15_TEST1_0_DN5, G15_TEST1_0_DN4) -G15_TEST1_0.add_uniq_edge(G15_TEST1_0_DN6, G15_TEST1_0_DN4) - -G15_TEST1_0.add_uniq_edge(G15_TEST1_0_DN7, G15_TEST1_0_DN6) - -G15_TEST1_0.add_uniq_edge(G15_TEST1_0_DN8, G15_TEST1_0_DN5) -G15_TEST1_0.add_uniq_edge(G15_TEST1_0_DN9, G15_TEST1_0_DN8) -G15_TEST1_0.add_uniq_edge(G15_TEST1_0_DN6, G15_TEST1_0_DN9) -G15_TEST1_0.add_uniq_edge(G15_TEST1_0_DN10, G15_TEST1_0_DN9) - -# 0 loop - -G15_TEST1_1.add_uniq_edge(G15_TEST1_0_DN2, G15_TEST1_0_DN1) -G15_TEST1_1.add_uniq_edge(G15_TEST1_0_DN3, G15_TEST1_0_DN2) -G15_TEST1_1.add_uniq_edge(G15_TEST1_0_DN4, G15_TEST1_0_DN3) -G15_TEST1_1.add_uniq_edge(G15_TEST1_0_DN5, G15_TEST1_0_DN4) -G15_TEST1_1.add_uniq_edge(G15_TEST1_0_DN6, G15_TEST1_0_DN4) -G15_TEST1_1.add_uniq_edge(G15_TEST1_0_DN7, G15_TEST1_0_DN6) +G15_TEST1_0_DN1 = DependencyNode(G15_IRB2.label, R, 1) G15_INPUT = (set([G15_TEST1_0_DN1]), set([])) -DN15_UNRESOLVED = DependencyNode(G15_IRB0.label, B, 0, 0).nostep_repr -G15_OUTPUT = {"graph": [G15_TEST1_0, G15_TEST1_1], - "emul": [{R: B_INIT + CST22}, {R: B_INIT + CST1}], - "unresolved": [set([DN15_UNRESOLVED]), set([DN15_UNRESOLVED])], - "has_loop": [True, False]} - # Test graph 16 -G16_TEST1_0_DN1 = DependencyNode(G16_IRB5.label, R, 1, next(STEP_COUNTER)) -G16_TEST1_0_DN2 = DependencyNode(G16_IRB5.label, A, 0, next(STEP_COUNTER)) -G16_TEST1_0_DN3 = DependencyNode(G16_IRB0.label, CST1, 0, next(STEP_COUNTER)) +G16_TEST1_0_DN1 = DependencyNode(G16_IRB5.label, R, 1) -G16_TEST1_0 = GraphTest(G16_IRA) +G16_INPUT = (set([G16_TEST1_0_DN1]), set([])) -G16_TEST1_0.add_uniq_edge(G16_TEST1_0_DN3, G16_TEST1_0_DN2) -G16_TEST1_0.add_uniq_edge(G16_TEST1_0_DN2, G16_TEST1_0_DN1) +# Test graph 17 -G16_INPUT = (set([G16_TEST1_0_DN1]), set([])) +G17_TEST1_DN1 = DependencyNode(G17_IRB2.label, A, 1) -G16_OUTPUT = {"graph": [G16_TEST1_0], - "emul": [{R: CST1}], - "unresolved": [set()], - "has_loop": [False]} +G17_INPUT = (set([G17_TEST1_DN1]), set([])) -# Test graph 17 -G17_TEST1 = GraphTest(G17_IRA) +FAILED = set() -G17_TEST1_DN1 = DependencyNode(G17_IRB2.label, A, 1, next(STEP_COUNTER)) -G17_TEST1_DN2 = DependencyNode(G17_IRB2.label, B, 0, next(STEP_COUNTER)) -G17_TEST1_DN3 = DependencyNode(G17_IRB2.label, A, 0, next(STEP_COUNTER)) -G17_TEST1_DN4 = DependencyNode(G17_IRB1.label, D, 0, next(STEP_COUNTER)) -G17_TEST1_DN5 = DependencyNode(G17_IRB0.label, CST2, 0, next(STEP_COUNTER)) -G17_TEST1.add_uniq_edge(G17_TEST1_DN2, G17_TEST1_DN1) -G17_TEST1.add_uniq_edge(G17_TEST1_DN3, G17_TEST1_DN1) -G17_TEST1.add_uniq_edge(G17_TEST1_DN4, G17_TEST1_DN2) -G17_TEST1.add_uniq_edge(G17_TEST1_DN4, G17_TEST1_DN3) -G17_TEST1.add_uniq_edge(G17_TEST1_DN5, G17_TEST1_DN4) +def flatNode(node): + if isinstance(node, DependencyNode): + if isinstance(node.element, ExprId): + element = node.element.name + elif isinstance(node.element, ExprInt): + element = int(node.element.arg.arg) + else: + RuntimeError("Unsupported type '%s'" % type(enode.element)) + return (node.label.name, + element, + node.line_nb) + else: + return str(node) + + +def flatGraph(graph): + out_nodes, out_edges = set(), set() + for node in graph.nodes(): + out_nodes.add(flatNode(node)) + for nodeA, nodeB in graph.edges(): + out_edges.add((flatNode(nodeA), flatNode(nodeB))) + out = (tuple(sorted(list(out_nodes))), + tuple(sorted(list(out_edges)))) + return out + + +def unflatGraph(flat_graph): + graph = DiGraph() + nodes, edges = flat_graph + for node in nodes: + graph.add_node(node) + for nodeA, nodeB in edges: + graph.add_edge(nodeA, nodeB) + return graph + + +def get_node_noidx(node): + if isinstance(node, tuple): + return (node[0], node[1], node[2]) + else: + return node + + +def test_result(graphA, graphB, leaves): + """ + Test graph equality without using node index + """ -G17_INPUT = (set([G17_TEST1_DN1]), set([])) + todo = set((leaf, leaf) for leaf in leaves) + done = set() + while todo: + nodeA, nodeB = todo.pop() + if (nodeA, nodeB) in done: + continue + done.add((nodeA, nodeB)) -G17_OUTPUT = {"graph": [G17_TEST1], - "emul": [{A: CST0}], - "unresolved": [set()], - "has_loop": [False]} + if get_node_noidx(nodeA) != get_node_noidx(nodeB): + return False + if nodeA not in graphA.nodes(): + return False + if nodeB not in graphB.nodes(): + return False + parentsA = graphA.predecessors(nodeA) + parentsB = graphB.predecessors(nodeB) + if len(parentsA) != len(parentsB): + return False + parentsA_noidx, parentsB_noidx = {}, {} + for parents, parents_noidx in ((parentsA, parentsA_noidx), + (parentsB, parentsB_noidx)): + for node in parents: + node_noidx = get_node_noidx(node) + assert(node_noidx not in parents_noidx) + parents_noidx[node_noidx] = node -FAILED = set() + if set(parentsA_noidx.keys()) != set(parentsB_noidx.keys()): + return False + for node_noidx, nodeA in parentsA_noidx.iteritems(): + nodeB = parentsB_noidx[node_noidx] + todo.add((nodeA, nodeB)) + return True + +def match_results(resultsA, resultsB, nodes): + """ + Match computed list of graph against test cases + """ + out = [] + + if len(resultsA) != len(resultsB): + return False + + for resultA in resultsA: + nodes = resultA.leaves() + for resultB in resultsB: + if test_result(resultA, resultB, nodes): + out.append((resultA, resultB)) + return len(out) == len(resultsB) + + +def get_flat_init_depnodes(depnodes): + out = [] + for node in depnodes: + out.append((node.label.name, + node.element.name, + node.line_nb, + 0)) + return out + +# TESTS +flat_test_results = [[((('lbl0', 1, 0), ('lbl0', 'c', 0), ('lbl1', 'b', 0), ('lbl2', 'a', 0)), + ((('lbl0', 1, 0), ('lbl0', 'c', 0)), + (('lbl0', 'c', 0), ('lbl1', 'b', 0)), + (('lbl1', 'b', 0), ('lbl2', 'a', 0))))], + [((('lbl0', 1, 0), + ('lbl0', 'c', 0), + ('lbl1', 2, 0), + ('lbl1', 'b', 0), + ('lbl2', 'a', 0)), + ((('lbl0', 1, 0), ('lbl0', 'c', 0)), + (('lbl0', 'c', 0), ('lbl2', 'a', 0)), + (('lbl1', 2, 0), ('lbl1', 'b', 0)), + (('lbl1', 'b', 0), ('lbl2', 'a', 0))))], + [((('lbl0', 1, 0), + ('lbl0', 'c', 0), + ('lbl1', 2, 0), + ('lbl1', 'b', 0), + ('lbl3', 'a', 0)), + ((('lbl0', 1, 0), ('lbl0', 'c', 0)), + (('lbl0', 'c', 0), ('lbl3', 'a', 0)), + (('lbl1', 2, 0), ('lbl1', 'b', 0)), + (('lbl1', 'b', 0), ('lbl3', 'a', 0)))), + ((('lbl0', 1, 0), + ('lbl0', 'c', 0), + ('lbl2', 3, 0), + ('lbl2', 'b', 0), + ('lbl3', 'a', 0)), + ((('lbl0', 1, 0), ('lbl0', 'c', 0)), + (('lbl0', 'c', 0), ('lbl3', 'a', 0)), + (('lbl2', 3, 0), ('lbl2', 'b', 0)), + (('lbl2', 'b', 0), ('lbl3', 'a', 0))))], + [(('b', ('lbl2', 'a', 0)), (('b', ('lbl2', 'a', 0)),))], + [((('lbl0', 1, 0), + ('lbl0', 'b', 0), + ('lbl1', 2, 0), + ('lbl1', 'b', 0), + ('lbl2', 'a', 0)), + ((('lbl0', 1, 0), ('lbl0', 'b', 0)), + (('lbl0', 'b', 0), ('lbl1', 'b', 0)), + (('lbl1', 2, 0), ('lbl1', 'b', 0)), + (('lbl1', 'b', 0), ('lbl1', 'b', 0)), + (('lbl1', 'b', 0), ('lbl2', 'a', 0)))), + ((('lbl0', 1, 0), + ('lbl0', 'b', 0), + ('lbl1', 2, 0), + ('lbl1', 'b', 0), + ('lbl2', 'a', 0)), + ((('lbl0', 1, 0), ('lbl0', 'b', 0)), + (('lbl0', 'b', 0), ('lbl1', 'b', 0)), + (('lbl1', 2, 0), ('lbl1', 'b', 0)), + (('lbl1', 'b', 0), ('lbl2', 'a', 0))))], + [((('lbl0', 1, 0), ('lbl0', 'b', 0), ('lbl1', 'a', 0)), + ((('lbl0', 1, 0), ('lbl0', 'b', 0)), + (('lbl0', 'b', 0), ('lbl1', 'a', 0))))], + [((('lbl0', 1, 0), + ('lbl0', 'c', 0), + ('lbl1', 'a', 1), + ('lbl1', 'b', 0), + ('lbl2', 'd', 0)), + ((('lbl0', 1, 0), ('lbl0', 'c', 0)), + (('lbl0', 'c', 0), ('lbl1', 'b', 0)), + (('lbl1', 'a', 1), ('lbl2', 'd', 0)), + (('lbl1', 'b', 0), ('lbl1', 'a', 1))))], + [(('d', ('lbl1', 'b', 0), ('lbl1', 'c', 1), ('lbl2', 'a', 0)), + (('d', ('lbl1', 'c', 1)), + (('lbl1', 'b', 0), ('lbl2', 'a', 0)), + (('lbl1', 'c', 1), ('lbl1', 'b', 0)))), + ((('lbl0', 1, 0), ('lbl0', 'c', 0), ('lbl1', 'b', 0), ('lbl2', 'a', 0)), + ((('lbl0', 1, 0), ('lbl0', 'c', 0)), + (('lbl0', 'c', 0), ('lbl1', 'b', 0)), + (('lbl1', 'b', 0), ('lbl2', 'a', 0))))], + [(('d', + ('lbl0', 1, 0), + ('lbl0', 'c', 0), + ('lbl1', 'b', 0), + ('lbl1', 'c', 1), + ('lbl2', 'a', 0)), + (('d', ('lbl1', 'c', 1)), + (('lbl0', 1, 0), ('lbl0', 'c', 0)), + (('lbl0', 'c', 0), ('lbl1', 'b', 0)), + (('lbl1', 'b', 0), ('lbl2', 'a', 0)))), + (('d', ('lbl1', 'b', 0), ('lbl1', 'c', 1), ('lbl2', 'a', 0)), + (('d', ('lbl1', 'c', 1)), + (('lbl1', 'b', 0), ('lbl2', 'a', 0)), + (('lbl1', 'c', 1), ('lbl1', 'b', 0))))], + [(('b', ('lbl1', 2, 0), ('lbl1', 'b', 0), ('lbl2', 'a', 0)), + (('b', ('lbl1', 'b', 0)), + (('lbl1', 2, 0), ('lbl1', 'b', 0)), + (('lbl1', 'b', 0), ('lbl1', 'b', 0)), + (('lbl1', 'b', 0), ('lbl2', 'a', 0)))), + (('b', ('lbl1', 2, 0), ('lbl1', 'b', 0), ('lbl2', 'a', 0)), + (('b', ('lbl1', 'b', 0)), + (('lbl1', 2, 0), ('lbl1', 'b', 0)), + (('lbl1', 'b', 0), ('lbl2', 'a', 0))))], + [((('lbl0', 1, 0), + ('lbl0', 2, 0), + ('lbl0', 'a', 0), + ('lbl0', 'b', 0), + ('lbl1', 'a', 0), + ('lbl1', 'b', 0), + ('lbl2', 'a', 0)), + ((('lbl0', 1, 0), ('lbl0', 'a', 0)), + (('lbl0', 2, 0), ('lbl0', 'b', 0)), + (('lbl0', 'a', 0), ('lbl1', 'b', 0)), + (('lbl0', 'b', 0), ('lbl1', 'a', 0)), + (('lbl1', 'a', 0), ('lbl2', 'a', 0)), + (('lbl1', 'b', 0), ('lbl2', 'a', 0))))], + [((('lbl0', 1, 0), + ('lbl0', 'b', 0), + ('lbl1', 2, 1), + ('lbl1', 'a', 0), + ('lbl1', 'b', 1), + ('lbl2', 'b', 0)), + ((('lbl0', 1, 0), ('lbl0', 'b', 0)), + (('lbl0', 'b', 0), ('lbl1', 'b', 1)), + (('lbl1', 2, 1), ('lbl1', 'b', 1)), + (('lbl1', 'a', 0), ('lbl2', 'b', 0)), + (('lbl1', 'b', 1), ('lbl1', 'a', 0)))), + ((('lbl0', 1, 0), + ('lbl0', 'b', 0), + ('lbl1', 2, 1), + ('lbl1', 'a', 0), + ('lbl1', 'b', 1), + ('lbl2', 'b', 0)), + ((('lbl0', 1, 0), ('lbl0', 'b', 0)), + (('lbl0', 'b', 0), ('lbl1', 'b', 1)), + (('lbl1', 2, 1), ('lbl1', 'b', 1)), + (('lbl1', 'a', 0), ('lbl2', 'b', 0)), + (('lbl1', 'b', 1), ('lbl1', 'a', 0)), + (('lbl1', 'b', 1), ('lbl1', 'b', 1)))), + ((('lbl0', 1, 0), ('lbl0', 'b', 0), ('lbl1', 'a', 0), ('lbl2', 'b', 0)), + ((('lbl0', 1, 0), ('lbl0', 'b', 0)), + (('lbl0', 'b', 0), ('lbl1', 'a', 0)), + (('lbl1', 'a', 0), ('lbl2', 'b', 0))))], + [((('lbl0', 1, 0), + ('lbl0', 'a', 0), + ('lbl1', 'c', 0), + ('lbl2', 3, 0), + ('lbl2', 3, 1), + ('lbl2', 'a', 1), + ('lbl2', 'b', 0), + ('lbl3', 'r', 0)), + ((('lbl0', 1, 0), ('lbl0', 'a', 0)), + (('lbl0', 'a', 0), ('lbl2', 'b', 0)), + (('lbl1', 'c', 0), ('lbl3', 'r', 0)), + (('lbl2', 3, 0), ('lbl2', 'b', 0)), + (('lbl2', 3, 1), ('lbl2', 'a', 1)), + (('lbl2', 'a', 1), ('lbl1', 'c', 0)), + (('lbl2', 'a', 1), ('lbl2', 'b', 0)), + (('lbl2', 'b', 0), ('lbl2', 'a', 1)))), + ((('lbl0', 1, 0), + ('lbl0', 'a', 0), + ('lbl1', 'c', 0), + ('lbl2', 3, 0), + ('lbl2', 3, 1), + ('lbl2', 'a', 1), + ('lbl2', 'b', 0), + ('lbl3', 'r', 0)), + ((('lbl0', 1, 0), ('lbl0', 'a', 0)), + (('lbl0', 'a', 0), ('lbl2', 'b', 0)), + (('lbl1', 'c', 0), ('lbl3', 'r', 0)), + (('lbl2', 3, 0), ('lbl2', 'b', 0)), + (('lbl2', 3, 1), ('lbl2', 'a', 1)), + (('lbl2', 'a', 1), ('lbl1', 'c', 0)), + (('lbl2', 'b', 0), ('lbl2', 'a', 1)))), + ((('lbl0', 1, 0), ('lbl0', 'a', 0), ('lbl1', 'c', 0), ('lbl3', 'r', 0)), + ((('lbl0', 1, 0), ('lbl0', 'a', 0)), + (('lbl0', 'a', 0), ('lbl1', 'c', 0)), + (('lbl1', 'c', 0), ('lbl3', 'r', 0))))], + [(('d', + ('lbl0', 1, 0), + ('lbl0', 'a', 0), + ('lbl1', 'b', 0), + ('lbl3', 'r', 0)), + (('d', ('lbl3', 'r', 0)), + (('lbl0', 1, 0), ('lbl0', 'a', 0)), + (('lbl0', 'a', 0), ('lbl1', 'b', 0)), + (('lbl1', 'b', 0), ('lbl3', 'r', 0)))), + ((('lbl0', 1, 0), + ('lbl0', 'a', 0), + ('lbl1', 'b', 0), + ('lbl2', 1, 1), + ('lbl2', 'a', 1), + ('lbl2', 'd', 0), + ('lbl3', 'r', 0)), + ((('lbl0', 1, 0), ('lbl0', 'a', 0)), + (('lbl0', 'a', 0), ('lbl2', 'd', 0)), + (('lbl1', 'b', 0), ('lbl3', 'r', 0)), + (('lbl2', 1, 1), ('lbl2', 'a', 1)), + (('lbl2', 'a', 1), ('lbl1', 'b', 0)), + (('lbl2', 'a', 1), ('lbl2', 'd', 0)), + (('lbl2', 'd', 0), ('lbl2', 'a', 1)), + (('lbl2', 'd', 0), ('lbl3', 'r', 0)))), + ((('lbl0', 1, 0), + ('lbl0', 'a', 0), + ('lbl1', 'b', 0), + ('lbl2', 1, 1), + ('lbl2', 'a', 1), + ('lbl2', 'd', 0), + ('lbl3', 'r', 0)), + ((('lbl0', 1, 0), ('lbl0', 'a', 0)), + (('lbl0', 'a', 0), ('lbl2', 'd', 0)), + (('lbl1', 'b', 0), ('lbl3', 'r', 0)), + (('lbl2', 1, 1), ('lbl2', 'a', 1)), + (('lbl2', 'a', 1), ('lbl1', 'b', 0)), + (('lbl2', 'd', 0), ('lbl2', 'a', 1)), + (('lbl2', 'd', 0), ('lbl3', 'r', 0))))], + [(('b', + ('lbl0', 1, 0), + ('lbl0', 'a', 0), + ('lbl1', 'b', 2), + ('lbl1', 'c', 1), + ('lbl1', 'd', 0), + ('lbl2', 'r', 0)), + (('b', ('lbl1', 'd', 0)), + (('lbl0', 1, 0), ('lbl0', 'a', 0)), + (('lbl0', 'a', 0), ('lbl1', 'd', 0)), + (('lbl1', 'b', 2), ('lbl1', 'd', 0)), + (('lbl1', 'b', 2), ('lbl2', 'r', 0)), + (('lbl1', 'c', 1), ('lbl1', 'b', 2)), + (('lbl1', 'd', 0), ('lbl1', 'c', 1)))), + (('b', + ('lbl0', 1, 0), + ('lbl0', 'a', 0), + ('lbl1', 'b', 2), + ('lbl1', 'c', 1), + ('lbl1', 'd', 0), + ('lbl2', 'r', 0)), + (('b', ('lbl1', 'd', 0)), + (('lbl0', 1, 0), ('lbl0', 'a', 0)), + (('lbl0', 'a', 0), ('lbl1', 'd', 0)), + (('lbl1', 'b', 2), ('lbl2', 'r', 0)), + (('lbl1', 'c', 1), ('lbl1', 'b', 2)), + (('lbl1', 'd', 0), ('lbl1', 'c', 1))))], + [((('lbl0', 1, 0), ('lbl0', 'a', 0), ('lbl5', 'r', 0)), + ((('lbl0', 1, 0), ('lbl0', 'a', 0)), + (('lbl0', 'a', 0), ('lbl5', 'r', 0))))], + [((('lbl0', 2, 0), + ('lbl0', 'd', 0), + ('lbl1', 'a', 0), + ('lbl1', 'b', 0), + ('lbl2', 'a', 0)), + ((('lbl0', 2, 0), ('lbl0', 'd', 0)), + (('lbl0', 'd', 0), ('lbl1', 'a', 0)), + (('lbl0', 'd', 0), ('lbl1', 'b', 0)), + (('lbl1', 'a', 0), ('lbl2', 'a', 0)), + (('lbl1', 'b', 0), ('lbl2', 'a', 0))))]] + +test_results = [[unflatGraph(flat_result) for flat_result in flat_results] + for flat_results in flat_test_results] + +all_flats = [] # Launch tests -for test_nb, test in enumerate([(G1_IRA, G1_INPUT, G1_OUTPUT), - (G2_IRA, G2_INPUT, G2_OUTPUT), - (G3_IRA, G3_INPUT, G3_OUTPUT), - (G4_IRA, G4_INPUT, G4_OUTPUT), - (G5_IRA, G5_INPUT, G5_OUTPUT), - (G6_IRA, G6_INPUT, G6_OUTPUT), - (G7_IRA, G7_INPUT, G7_OUTPUT), - (G8_IRA, G8_INPUT, G8_OUTPUT), - (G8_IRA, G9_INPUT, G9_OUTPUT), - (G10_IRA, G10_INPUT, G10_OUTPUT), - (G11_IRA, G11_INPUT, G11_OUTPUT), - (G12_IRA, G12_INPUT, G12_OUTPUT), - (G13_IRA, G13_INPUT, G13_OUTPUT), - (G14_IRA, G14_INPUT, G14_OUTPUT), - (G15_IRA, G15_INPUT, G15_OUTPUT), - (G16_IRA, G16_INPUT, G16_OUTPUT), - (G17_IRA, G17_INPUT, G17_OUTPUT), +for test_nb, test in enumerate([(G1_IRA, G1_INPUT), + (G2_IRA, G2_INPUT), + (G3_IRA, G3_INPUT), + (G4_IRA, G4_INPUT), + (G5_IRA, G5_INPUT), + (G6_IRA, G6_INPUT), + (G7_IRA, G7_INPUT), + (G8_IRA, G8_INPUT), + (G8_IRA, G9_INPUT), + (G10_IRA, G10_INPUT), + (G11_IRA, G11_INPUT), + (G12_IRA, G12_INPUT), + (G13_IRA, G13_INPUT), + (G14_IRA, G14_INPUT), + (G15_IRA, G15_INPUT), + (G16_IRA, G16_INPUT), + (G17_IRA, G17_INPUT), ]): # Extract test elements print "[+] Test", test_nb + 1 - g_ira, (depnodes, heads), g_test_output = test + g_ira, (depnodes, heads) = test open("graph_%02d.dot" % (test_nb + 1), "w").write(g_ira.graph.dot()) + open("graph_%02d.dot" % (test_nb + 1), "w").write(bloc2graph(g_ira)) # Different options suffix_key_list = ["", "_nosimp", "_nomem", "_nocall", @@ -1134,125 +1033,41 @@ for test_nb, test in enumerate([(G1_IRA, G1_INPUT, G1_OUTPUT), DependencyGraph(g_ira, follow_mem=False), DependencyGraph(g_ira, follow_mem=False, follow_call=False), - DependencyGraph(g_ira, implicit=True), + # DependencyGraph(g_ira, implicit=True), ]): - if g_ind == 4: - # TODO: Implicit specifications - continue + # if g_ind == 4: + # TODO: Implicit specifications + # continue print " - Class %s - %s" % (g_dep.__class__.__name__, suffix_key_list[g_ind]) # Select the correct result key mode_suffix = suffix_key_list[g_ind] graph_test_key = "graph" + mode_suffix - if not g_test_output.has_key(graph_test_key): - graph_test_key = "graph" - - expected_results = g_test_output[graph_test_key] # Test public APIs - for api_i, g_list in enumerate( - [g_dep.get_from_depnodes(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_from_depnodes" - if api_i == 0 else "get") - - # Expand result iterator - g_list = list(g_list) - - # Dump outputs graphs for debug means - for result_nb, result_graph in enumerate(g_list): - open("graph_test_%02d_%02d.dot" % (test_nb + 1, result_nb), - "w").write(result_graph.graph.dot()) - - for result_nb, result_graph in enumerate(expected_results): - open("exp_graph_test_%02d_%02d.dot" % (test_nb + 1, result_nb), - "w").write(result_graph.dot()) - - try: - # The number of results should be the same - print " - - - number of results %d/%d" % (len(g_list), - len(expected_results)) - - error = 'len:' + \ - str(len(g_list)) + '/' + str(len(expected_results)) - assert len(g_list) == len(expected_results) - - # Check that every result appears in expected_results - for j, result in enumerate(g_list): - print " - - - result %d" % j - found = False - for expected in expected_results: - if expected.__eq__(result.graph): - found = True - error = "found1" - assert found - - # Check that every expected result appears in real results - for j, expected in enumerate(expected_results): - print " - - - expected %d" % j - found = False - for result in g_list: - if expected.__eq__(result.graph): - found = True - error = "found2" - assert found - - if not EMULATION: - continue - # Test emulation results and other properties - unresolved_test_key = "unresolved" + mode_suffix - if not g_test_output.has_key(unresolved_test_key): - unresolved_test_key = "unresolved" - - # Check that every computed result was expected - for emul_nb, result in enumerate(g_list): - print " - - - - emul %d" % emul_nb - emul_result = result.emul() - - error = "emul" - found = False - for exp_nb in xrange(len(g_list)): - if (emul_result == g_test_output["emul"][exp_nb] and - getattr(result, "unresolved") == - g_test_output[unresolved_test_key][exp_nb] and - g_test_output["has_loop"][exp_nb] == - getattr(result, "has_loop") - ): - found = True - break - assert found - - # Check that every expected result has been computed - for exp_nb in xrange(len(g_list)): - print " - - - - emul %d" % exp_nb - - error = "emul2" - found = False - for emul_nb, result in enumerate(g_list): - emul_result = result.emul() - if (emul_result == g_test_output["emul"][exp_nb] and - getattr(result, "unresolved") == - g_test_output[unresolved_test_key][exp_nb] and - g_test_output["has_loop"][exp_nb] == - getattr(result, "has_loop") - ): - found = True - break - assert found - - except AssertionError: - FAILED.add((test_nb + 1, error)) - continue + results = g_dep.get_from_depnodes(depnodes, heads) + print "RESULTS" + all_results = set() + all_flat = set() + for i, result in enumerate(results): + all_flat.add(flatGraph(result.graph)) + all_results.add(unflatGraph(flatGraph(result.graph))) + open("graph_test_%02d_%02d.dot" % (test_nb + 1, i), + "w").write(dg2graph(result.graph)) + # print all_flat + if g_ind == 0: + all_flat = sorted(all_flat) + all_flats.append(all_flat) + flat_depnodes = get_flat_init_depnodes(depnodes) + if not match_results(all_results, test_results[test_nb], flat_depnodes): + FAILED.add(test_nb) + # fds + continue if FAILED: print "FAILED :", len(FAILED) - for i in sorted(FAILED, key=lambda (u, _): u): - print i, + for test_num in sorted(FAILED): + print test_num, else: print "SUCCESS" diff --git a/test/analysis/dg_check.py b/test/analysis/dg_check.py new file mode 100644 index 00000000..0d680b6f --- /dev/null +++ b/test/analysis/dg_check.py @@ -0,0 +1,20 @@ +from pdb import pm +import sys +import subprocess +import json + + +expected_file = sys.argv[1] +dg = subprocess.Popen(["python"] + sys.argv[2:], stdout=subprocess.PIPE) + +stdout, _ = dg.communicate() +expected = json.load(open(expected_file)) +result = json.loads(stdout) + + +expected.sort() +result.sort() + +print expected +print result +assert expected == result diff --git a/test/analysis/dg_test_00_expected.json b/test/analysis/dg_test_00_expected.json new file mode 100644 index 00000000..cae8b582 --- /dev/null +++ b/test/analysis/dg_test_00_expected.json @@ -0,0 +1 @@ +[{"EAX": "0x1", "has_loop": false}] diff --git a/test/analysis/dg_test_00_implicit_expected.json b/test/analysis/dg_test_00_implicit_expected.json new file mode 100644 index 00000000..186704d0 --- /dev/null +++ b/test/analysis/dg_test_00_implicit_expected.json @@ -0,0 +1 @@ +[{"has_loop": false, "EAX": "0x1", "satisfiability": true, "constraints": {}}] diff --git a/test/analysis/dg_test_01_expected.json b/test/analysis/dg_test_01_expected.json new file mode 100644 index 00000000..724d74a3 --- /dev/null +++ b/test/analysis/dg_test_01_expected.json @@ -0,0 +1 @@ +[{"EAX": "0x3", "has_loop": false}] diff --git a/test/analysis/dg_test_01_implicit_expected.json b/test/analysis/dg_test_01_implicit_expected.json new file mode 100644 index 00000000..2edb5ede --- /dev/null +++ b/test/analysis/dg_test_01_implicit_expected.json @@ -0,0 +1 @@ +[{"has_loop": false, "EAX": "0x3", "satisfiability": true, "constraints": {}}] diff --git a/test/analysis/dg_test_02_expected.json b/test/analysis/dg_test_02_expected.json new file mode 100644 index 00000000..16d409fb --- /dev/null +++ b/test/analysis/dg_test_02_expected.json @@ -0,0 +1 @@ +[{"EAX": "0x3", "has_loop": false}, {"EAX": "0x4", "has_loop": false}] diff --git a/test/analysis/dg_test_02_implicit_expected.json b/test/analysis/dg_test_02_implicit_expected.json new file mode 100644 index 00000000..9394f01d --- /dev/null +++ b/test/analysis/dg_test_02_implicit_expected.json @@ -0,0 +1 @@ +[{"has_loop": false, "EAX": "0x4", "satisfiability": true, "constraints": {"zf_init": "0x1"}}, {"has_loop": false, "EAX": "0x3", "satisfiability": true, "constraints": {"zf_init": "0x0"}}] diff --git a/test/analysis/dg_test_03_expected.json b/test/analysis/dg_test_03_expected.json new file mode 100644 index 00000000..9d0dfdbd --- /dev/null +++ b/test/analysis/dg_test_03_expected.json @@ -0,0 +1 @@ +[{"EAX": "0x3", "has_loop": false}, {"EAX": "0x5", "has_loop": true}] diff --git a/test/analysis/dg_test_03_implicit_expected.json b/test/analysis/dg_test_03_implicit_expected.json new file mode 100644 index 00000000..9f7ddea0 --- /dev/null +++ b/test/analysis/dg_test_03_implicit_expected.json @@ -0,0 +1 @@ +[{"has_loop": false, "EAX": "0x3", "satisfiability": false, "constraints": {}}, {"has_loop": true, "EAX": "0x5", "satisfiability": false, "constraints": {}}] diff --git a/test/analysis/dg_test_04_expected.json b/test/analysis/dg_test_04_expected.json new file mode 100644 index 00000000..fb115835 --- /dev/null +++ b/test/analysis/dg_test_04_expected.json @@ -0,0 +1 @@ +[{"EAX": "EBX_init", "has_loop": false}] diff --git a/test/analysis/dg_test_04_implicit_expected.json b/test/analysis/dg_test_04_implicit_expected.json new file mode 100644 index 00000000..73e7209e --- /dev/null +++ b/test/analysis/dg_test_04_implicit_expected.json @@ -0,0 +1 @@ +[{"has_loop": false, "EAX": "EBX_init", "satisfiability": true, "constraints": {}}, {"has_loop": true, "EAX": "EBX_init", "satisfiability": false, "constraints": {}}] diff --git a/test/analysis/dg_test_05_expected.json b/test/analysis/dg_test_05_expected.json new file mode 100644 index 00000000..724d74a3 --- /dev/null +++ b/test/analysis/dg_test_05_expected.json @@ -0,0 +1 @@ +[{"EAX": "0x3", "has_loop": false}] diff --git a/test/analysis/dg_test_05_implicit_expected.json b/test/analysis/dg_test_05_implicit_expected.json new file mode 100644 index 00000000..ef39008f --- /dev/null +++ b/test/analysis/dg_test_05_implicit_expected.json @@ -0,0 +1 @@ +[{"has_loop": false, "EAX": "0x3", "satisfiability": true, "constraints": {}}, {"has_loop": true, "EAX": "0x3", "satisfiability": false, "constraints": {}}] diff --git a/test/analysis/dg_test_06_expected.json b/test/analysis/dg_test_06_expected.json new file mode 100644 index 00000000..7d823131 --- /dev/null +++ b/test/analysis/dg_test_06_expected.json @@ -0,0 +1 @@ +[{"EAX": "0x1", "has_loop": false}, {"EAX": "0x2", "has_loop": true}] diff --git a/test/analysis/dg_test_06_implicit_expected.json b/test/analysis/dg_test_06_implicit_expected.json new file mode 100644 index 00000000..050915c1 --- /dev/null +++ b/test/analysis/dg_test_06_implicit_expected.json @@ -0,0 +1 @@ +[{"has_loop": false, "EAX": "0x1", "satisfiability": true, "constraints": {"EAX_init": "0xffffffff"}}, {"has_loop": true, "EAX": "0x2", "satisfiability": false, "constraints": {}}] diff --git a/test/analysis/dg_test_07_expected.json b/test/analysis/dg_test_07_expected.json new file mode 100644 index 00000000..0ed0be95 --- /dev/null +++ b/test/analysis/dg_test_07_expected.json @@ -0,0 +1 @@ +[{"EAX": "0x1", "ECX": "0x2", "has_loop": false}] diff --git a/test/analysis/dg_test_07_implicit_expected.json b/test/analysis/dg_test_07_implicit_expected.json new file mode 100644 index 00000000..4f8c782a --- /dev/null +++ b/test/analysis/dg_test_07_implicit_expected.json @@ -0,0 +1 @@ +[{"has_loop": false, "EAX": "0x1", "constraints": {}, "satisfiability": true, "ECX": "0x2"}] diff --git a/test/analysis/dg_test_08_expected.json b/test/analysis/dg_test_08_expected.json new file mode 100644 index 00000000..b4c379d1 --- /dev/null +++ b/test/analysis/dg_test_08_expected.json @@ -0,0 +1 @@ +[{"ECX": "0x2", "has_loop": false}] diff --git a/test/analysis/dg_test_08_implicit_expected.json b/test/analysis/dg_test_08_implicit_expected.json new file mode 100644 index 00000000..a0416a4e --- /dev/null +++ b/test/analysis/dg_test_08_implicit_expected.json @@ -0,0 +1 @@ +[{"has_loop": false, "constraints": {}, "satisfiability": true, "ECX": "0x2"}] diff --git a/test/analysis/dg_test_09_expected.json b/test/analysis/dg_test_09_expected.json new file mode 100644 index 00000000..ba0e4673 --- /dev/null +++ b/test/analysis/dg_test_09_expected.json @@ -0,0 +1,2 @@ +[{"EAX": "0x1", "EBX": "0x2", "has_loop": false}, + {"EAX": "0x3", "EBX": "0x4", "has_loop": false}] diff --git a/test/analysis/dg_test_09_implicit_expected.json b/test/analysis/dg_test_09_implicit_expected.json new file mode 100644 index 00000000..1ea2976f --- /dev/null +++ b/test/analysis/dg_test_09_implicit_expected.json @@ -0,0 +1 @@ +[{"has_loop": false, "EAX": "0x1", "EBX": "0x2", "satisfiability": true, "constraints": {}}, {"has_loop": false, "EAX": "0x3", "EBX": "0x4", "satisfiability": true, "constraints": {}}] diff --git a/test/analysis/dg_test_10_expected.json b/test/analysis/dg_test_10_expected.json new file mode 100644 index 00000000..720b85e2 --- /dev/null +++ b/test/analysis/dg_test_10_expected.json @@ -0,0 +1 @@ +[{"EAX": "0x1", "EBX": "0x3", "has_loop": false}, {"EAX": "0x1", "EBX": "0x4", "has_loop": false}, {"EAX": "0x2", "EBX": "0x4", "has_loop": false}, {"EAX": "0x2", "EBX": "0x3", "has_loop": false}] diff --git a/test/analysis/dg_test_10_implicit_expected.json b/test/analysis/dg_test_10_implicit_expected.json new file mode 100644 index 00000000..05b34918 --- /dev/null +++ b/test/analysis/dg_test_10_implicit_expected.json @@ -0,0 +1 @@ +[{"has_loop": false, "EAX": "0x1", "EBX": "0x3", "satisfiability": true, "constraints": {"zf_init": "0x0"}}, {"has_loop": false, "EAX": "0x2", "EBX": "0x3", "satisfiability": false, "constraints": {}}, {"has_loop": false, "EAX": "0x1", "EBX": "0x4", "satisfiability": false, "constraints": {}}, {"has_loop": false, "EAX": "0x2", "EBX": "0x4", "satisfiability": true, "constraints": {"zf_init": "0x1"}}] diff --git a/test/samples/x86_32/dg_test_00.S b/test/samples/x86_32/dg_test_00.S new file mode 100644 index 00000000..dc9ef665 --- /dev/null +++ b/test/samples/x86_32/dg_test_00.S @@ -0,0 +1,9 @@ +main: + MOV ECX, 0x1 + JMP lbl1 +lbl1: + MOV EBX, ECX + JMP lbl2 +lbl2: + MOV EAX, EBX + RET diff --git a/test/samples/x86_32/dg_test_01.S b/test/samples/x86_32/dg_test_01.S new file mode 100644 index 00000000..4f4ff80d --- /dev/null +++ b/test/samples/x86_32/dg_test_01.S @@ -0,0 +1,9 @@ +main: + MOV ECX, 0x1 + JMP lbl1 +lbl1: + MOV EBX, 0x2 + JMP lbl2 +lbl2: + LEA EAX, DWORD PTR [EBX + ECX] + RET diff --git a/test/samples/x86_32/dg_test_02.S b/test/samples/x86_32/dg_test_02.S new file mode 100644 index 00000000..164dd90a --- /dev/null +++ b/test/samples/x86_32/dg_test_02.S @@ -0,0 +1,12 @@ +main: + MOV ECX, 0x1 + JZ lbl2 +lbl1: + MOV EBX, 0x2 + JMP end +lbl2: + MOV EBX, 0x3 + JMP end +end: + LEA EAX, DWORD PTR [EBX + ECX] + RET diff --git a/test/samples/x86_32/dg_test_03.S b/test/samples/x86_32/dg_test_03.S new file mode 100644 index 00000000..ac0edc56 --- /dev/null +++ b/test/samples/x86_32/dg_test_03.S @@ -0,0 +1,10 @@ +main: + MOV EBX, 0x1 + JMP lbl1 +lbl1: + ADD EBX, 0x2 + CMP EBX, 0x0 + JNZ lbl1 +end: + MOV EAX, EBX + RET diff --git a/test/samples/x86_32/dg_test_04.S b/test/samples/x86_32/dg_test_04.S new file mode 100644 index 00000000..393430ed --- /dev/null +++ b/test/samples/x86_32/dg_test_04.S @@ -0,0 +1,10 @@ +main: + MOV ECX, 0x1 + JMP lbl1 +lbl1: + ADD ECX, 0x2 + CMP ECX, 0x0 + JZ lbl1 +end: + MOV EAX, EBX + RET diff --git a/test/samples/x86_32/dg_test_05.S b/test/samples/x86_32/dg_test_05.S new file mode 100644 index 00000000..336ee3f5 --- /dev/null +++ b/test/samples/x86_32/dg_test_05.S @@ -0,0 +1,11 @@ +main: + MOV ECX, 0x1 + MOV EBX, 0x3 + JMP lbl1 +lbl1: + ADD ECX, 0x2 + CMP ECX, 0x0 + JZ lbl1 +end: + MOV EAX, EBX + RET diff --git a/test/samples/x86_32/dg_test_06.S b/test/samples/x86_32/dg_test_06.S new file mode 100644 index 00000000..e12766f2 --- /dev/null +++ b/test/samples/x86_32/dg_test_06.S @@ -0,0 +1,12 @@ +main: + MOV ECX, 0x1 + MOV EDX, 0x2 + JMP lbl1 +lbl1: + MOV EBX, ECX + MOV ECX, EDX + CMP EAX, 0x0 + JZ lbl1 +end: + MOV EAX, EBX + RET diff --git a/test/samples/x86_32/dg_test_07.S b/test/samples/x86_32/dg_test_07.S new file mode 100644 index 00000000..a23d5b66 --- /dev/null +++ b/test/samples/x86_32/dg_test_07.S @@ -0,0 +1,10 @@ +main: + MOV ECX, 0x1 + MOV EBX, 0x2 + JMP lbl1 +lbl1: + XCHG EBX, ECX + JMP end +end: + MOV EAX, EBX + RET diff --git a/test/samples/x86_32/dg_test_08.S b/test/samples/x86_32/dg_test_08.S new file mode 100644 index 00000000..a23d5b66 --- /dev/null +++ b/test/samples/x86_32/dg_test_08.S @@ -0,0 +1,10 @@ +main: + MOV ECX, 0x1 + MOV EBX, 0x2 + JMP lbl1 +lbl1: + XCHG EBX, ECX + JMP end +end: + MOV EAX, EBX + RET diff --git a/test/samples/x86_32/dg_test_09.S b/test/samples/x86_32/dg_test_09.S new file mode 100644 index 00000000..d4d053f5 --- /dev/null +++ b/test/samples/x86_32/dg_test_09.S @@ -0,0 +1,13 @@ +main: + MOV ECX, 0x8 + JZ lbl2 +lbl1: + MOV EAX, 0x1 + MOV EBX, 0x2 + JMP end +lbl2: + MOV EAX, 0x3 + MOV EBX, 0x4 + JMP end +end: + RET diff --git a/test/samples/x86_32/dg_test_10.S b/test/samples/x86_32/dg_test_10.S new file mode 100644 index 00000000..5825da67 --- /dev/null +++ b/test/samples/x86_32/dg_test_10.S @@ -0,0 +1,20 @@ +main: + MOV ECX, 0x8 + JZ lbl2 +lbl1: + MOV EAX, 0x1 + JMP end1 +lbl2: + MOV EAX, 0x2 + JMP end1 +end1: + JZ lbl4 +lbl3: + MOV EBX, 0x3 + JMP end +lbl4: + MOV EBX, 0x4 + JMP end + +end: + RET diff --git a/test/test_all.py b/test/test_all.py index adee5f2d..d633d85c 100644 --- a/test/test_all.py +++ b/test/test_all.py @@ -22,11 +22,19 @@ class RegressionTest(Test): - @base_dir: test/@base_dir - @tags: TAGS["regression"]""" + sample_dir = os.path.join("..", "samples") + def __init__(self, *args, **kwargs): super(RegressionTest, self).__init__(*args, **kwargs) self.base_dir = os.path.join("test", self.base_dir) self.tags.append(TAGS["regression"]) + @classmethod + def get_sample(cls, sample_name): + "Return the relative path of @sample_name" + return os.path.join(cls.sample_dir, sample_name) + + ## Architecture testset += RegressionTest(["x86/arch.py"], base_dir="arch", products=["x86_speed_reg_test.bin", @@ -242,6 +250,56 @@ testset += RegressionTest(["depgraph.py"], base_dir="analysis", (14, 1), (15, 1))) for fname in fnames]) +## Degraph +class TestDepgraph(RegressionTest): + """Dependency graph test""" + example_depgraph = os.path.join("..", "..", "example", "symbol_exec", + "depgraph.py") + launcher = "dg_check.py" + + + def __init__(self, test_nb, implicit, base_addr, target_addr, elements, + *args, **kwargs): + super(TestDepgraph, self).__init__([self.launcher], + *args, **kwargs) + self.base_dir = os.path.join(self.base_dir, "analysis") + if implicit: + expected_fname = "dg_test_%.2d_implicit_expected.json" + self.tags.append(TAGS["z3"]) + else: + expected_fname = "dg_test_%.2d_expected.json" + + self.command_line += [ + expected_fname % test_nb, + self.example_depgraph, + "-m", "x86_32", + "--json", + self.get_sample(os.path.join("x86_32", + "dg_test_%.2d.bin" % test_nb)), + hex(base_addr), + hex(target_addr)] + elements + if implicit: + self.command_line.append("-i") + +# Depgraph emulation regression test +test_args = [(0x401000, 0x40100d, ["EAX"]), + (0x401000, 0x401011, ["EAX"]), + (0x401000, 0x401018, ["EAX"]), + (0x401000, 0x401011, ["EAX"]), + (0x401000, 0x401011, ["EAX"]), + (0x401000, 0x401016, ["EAX"]), + (0x401000, 0x401017, ["EAX"]), + (0x401000, 0x401012, ["EAX", "ECX"]), + (0x401000, 0x401012, ["ECX"]), + (0x401000, 0x40101f, ["EAX", "EBX"]), + (0x401000, 0x401025, ["EAX", "EBX"]), +] +for i, test_args in enumerate(test_args): + test_dg = SemanticTestAsm("x86_32", "PE", ["dg_test_%.2d" % i]) + testset += test_dg + testset += TestDepgraph(i, False, *test_args, depends=[test_dg]) + testset += TestDepgraph(i, True, *test_args, depends=[test_dg]) + ## Jitter for script in ["jitload.py", ]: @@ -322,6 +380,7 @@ test_mips32b = ExampleShellcode(["mips32b", "mips32.S", "mips32_sc_b.bin"]) test_mips32l = ExampleShellcode(["mips32l", "mips32.S", "mips32_sc_l.bin"]) test_x86_64 = ExampleShellcode(["x86_64", "x86_64.S", "demo_x86_64.bin", "--PE"]) +test_x86_32_if_reg = ExampleShellcode(['x86_32', 'x86_32_if_reg.S', "x86_32_if_reg.bin"]) testset += test_armb testset += test_arml @@ -335,6 +394,7 @@ testset += test_msp430 testset += test_mips32b testset += test_mips32l testset += test_x86_64 +testset += test_x86_32_if_reg class ExampleDisassembler(Example): """Disassembler examples specificities: @@ -387,6 +447,8 @@ testset += ExampleDisasmFull(["aarch64b", Example.get_sample("demo_aarch64_b.bin "0"], depends=[test_aarch64b]) testset += ExampleDisasmFull(["x86_32", Example.get_sample("x86_32_simple.bin"), "0x401000"], depends=[test_box["simple"]]) +testset += ExampleDisasmFull(["x86_32", Example.get_sample("x86_32_if_reg.bin"), + "0x0"], depends=[test_x86_32_if_reg]) testset += ExampleDisasmFull(["msp430", Example.get_sample("msp430_sc.bin"), "0"], depends=[test_msp430]) testset += ExampleDisasmFull(["mips32l", Example.get_sample("mips32_sc_l.bin"), @@ -441,7 +503,7 @@ class ExampleSymbolExec(Example): testset += ExampleSymbolExec(["single_instr.py"]) for options, nb_sol, tag in [([], 8, []), - (["-i", "--rename-args"], 10, [TAGS["z3"]])]: + (["-i", "--rename-args"], 12, [TAGS["z3"]])]: testset += ExampleSymbolExec(["depgraph.py", Example.get_sample("simple_test.bin"), "-m", "x86_32", "0x0", "0x8b", @@ -450,6 +512,17 @@ for options, nb_sol, tag in [([], 8, []), for nb in xrange(nb_sol)], tags=tag) +for options, nb_sol, tag in [([], 4, []), + (["-i", "--rename-args"], 4, [TAGS["z3"]])]: + testset += ExampleSymbolExec(["depgraph.py", + Example.get_sample("x86_32_if_reg.bin"), + "-m", "x86_32", "0x0", "0x19", + "eax"] + options, + products=["sol_%d.dot" % nb + for nb in xrange(nb_sol)], + depends=[test_x86_32_if_reg], + tags=tag) + ## Jitter class ExampleJitter(Example): """Jitter examples specificities: |