"""Regression test module for DependencyGraph""" 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 from itertools import count from pdb import pm import re EMULATION = True try: import z3 except ImportError: EMULATION = False STEP_COUNTER = count() A = ExprId("a") B = ExprId("b") C = ExprId("c") D = ExprId("d") R = ExprId("r") A_INIT = ExprId("a_init") B_INIT = ExprId("b_init") C_INIT = ExprId("c_init") D_INIT = ExprId("d_init") PC = ExprId("pc") SP = ExprId("sp") CST0 = ExprInt32(0x0) CST1 = ExprInt32(0x1) CST2 = ExprInt32(0x2) CST3 = ExprInt32(0x3) CST22 = ExprInt32(0x22) CST23 = ExprInt32(0x23) CST24 = ExprInt32(0x24) CST33 = ExprInt32(0x33) CST35 = ExprInt32(0x35) CST37 = ExprInt32(0x37) LBL0 = asm_label("lbl0") LBL1 = asm_label("lbl1") LBL2 = asm_label("lbl2") LBL3 = asm_label("lbl3") LBL4 = asm_label("lbl4") LBL5 = asm_label("lbl5") LBL6 = asm_label("lbl6") def gen_irbloc(label, exprs_list): """ Returns an IRBlock with empty lines. Used only for tests purpose """ lines = [None for _ in xrange(len(exprs_list))] irs = [] for exprs in exprs_list: if isinstance(exprs, AssignBlock): irs.append(exprs) else: irs.append(AssignBlock(exprs)) irbl = irbloc(label, irs, lines) return irbl class Regs(object): """Fake registers for tests """ regs_init = {A: A_INIT, B: B_INIT, C: C_INIT, D: D_INIT} all_regs_ids = [A, B, C, D, SP, PC, R] class Arch(object): """Fake architecture for tests """ regs = Regs() def getpc(self, attrib): return PC def getsp(self, attrib): return SP class IRATest(ira): """Fake IRA class for tests""" def __init__(self, symbol_pool=None): arch = Arch() super(IRATest, self).__init__(arch, 32, symbol_pool) self.IRDst = PC self.ret_reg = R def get_out_regs(self, _): return set([self.ret_reg, self.sp]) def bloc2graph(irgraph, 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 irgraph.graph.nodes(): if isinstance(label, asm_label): label_name = label.name else: label_name = str(label) 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 =<' block_label = '' % ( 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') out_block += "%s " % block_label out_block += block_html_lines + "
%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 = ('
' % td_attr + ('
' % td_attr).join(block_html_lines) + '
> ];" 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: 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 =<' block_label = '' % ( label_attr, label_name) block_html_lines = [] block_html_lines = ('') out_block += "%s " % block_label out_block += block_html_lines + "
%s
' % td_attr + ('
' % td_attr).join(block_html_lines) + '
> ];" 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_IRB0 = gen_irbloc(LBL0, [[ExprAff(C, CST1)]]) G1_IRB1 = gen_irbloc(LBL1, [[ExprAff(B, C)]]) G1_IRB2 = gen_irbloc(LBL2, [[ExprAff(A, B)]]) G1_IRA.graph.add_uniq_edge(G1_IRB0.label, G1_IRB1.label) G1_IRA.graph.add_uniq_edge(G1_IRB1.label, G1_IRB2.label) G1_IRA.blocs = dict([(irb.label, irb) for irb in [G1_IRB0, G1_IRB1, G1_IRB2]]) # graph 2 G2_IRA = IRATest() G2_IRB0 = gen_irbloc(LBL0, [[ExprAff(C, CST1)]]) G2_IRB1 = gen_irbloc(LBL1, [[ExprAff(B, CST2)]]) G2_IRB2 = gen_irbloc(LBL2, [[ExprAff(A, B + C)]]) G2_IRA.graph.add_uniq_edge(G2_IRB0.label, G2_IRB1.label) G2_IRA.graph.add_uniq_edge(G2_IRB1.label, G2_IRB2.label) G2_IRA.blocs = dict([(irb.label, irb) for irb in [G2_IRB0, G2_IRB1, G2_IRB2]]) # graph 3 G3_IRA = IRATest() G3_IRB0 = gen_irbloc(LBL0, [[ExprAff(C, CST1)]]) G3_IRB1 = gen_irbloc(LBL1, [[ExprAff(B, CST2)]]) G3_IRB2 = gen_irbloc(LBL2, [[ExprAff(B, CST3)]]) G3_IRB3 = gen_irbloc(LBL3, [[ExprAff(A, B + C)]]) G3_IRA.graph.add_uniq_edge(G3_IRB0.label, G3_IRB1.label) G3_IRA.graph.add_uniq_edge(G3_IRB0.label, G3_IRB2.label) G3_IRA.graph.add_uniq_edge(G3_IRB1.label, G3_IRB3.label) G3_IRA.graph.add_uniq_edge(G3_IRB2.label, G3_IRB3.label) G3_IRA.blocs = dict([(irb.label, irb) for irb in [G3_IRB0, G3_IRB1, G3_IRB2, G3_IRB3]]) # graph 4 G4_IRA = IRATest() G4_IRB0 = gen_irbloc(LBL0, [[ExprAff(C, CST1)]]) G4_IRB1 = gen_irbloc(LBL1, [[ExprAff(C, C + CST2)], [ExprAff(G4_IRA.IRDst, ExprCond(C, ExprId(LBL2), ExprId(LBL1)))]]) G4_IRB2 = gen_irbloc(LBL2, [[ExprAff(A, B)]]) G4_IRA.graph.add_uniq_edge(G4_IRB0.label, G4_IRB1.label) G4_IRA.graph.add_uniq_edge(G4_IRB1.label, G4_IRB2.label) G4_IRA.graph.add_uniq_edge(G4_IRB1.label, G4_IRB1.label) G4_IRA.blocs = dict([(irb.label, irb) for irb in [G4_IRB0, G4_IRB1, G4_IRB2]]) # graph 5 G5_IRA = IRATest() G5_IRB0 = gen_irbloc(LBL0, [[ExprAff(B, CST1)]]) G5_IRB1 = gen_irbloc(LBL1, [[ExprAff(B, B + CST2)], [ExprAff(G5_IRA.IRDst, ExprCond(B, ExprId(LBL2), ExprId(LBL1)))]]) G5_IRB2 = gen_irbloc(LBL2, [[ExprAff(A, B)]]) G5_IRA.graph.add_uniq_edge(G5_IRB0.label, G5_IRB1.label) G5_IRA.graph.add_uniq_edge(G5_IRB1.label, G5_IRB2.label) G5_IRA.graph.add_uniq_edge(G5_IRB1.label, G5_IRB1.label) G5_IRA.blocs = dict([(irb.label, irb) for irb in [G5_IRB0, G5_IRB1, G5_IRB2]]) # graph 6 G6_IRA = IRATest() G6_IRB0 = gen_irbloc(LBL0, [[ExprAff(B, CST1)]]) G6_IRB1 = gen_irbloc(LBL1, [[ExprAff(A, B)]]) G6_IRA.graph.add_uniq_edge(G6_IRB0.label, G6_IRB1.label) G6_IRA.graph.add_uniq_edge(G6_IRB1.label, G6_IRB1.label) G6_IRA.blocs = dict([(irb.label, irb) for irb in [G6_IRB0, G6_IRB1]]) # graph 7 G7_IRA = IRATest() G7_IRB0 = gen_irbloc(LBL0, [[ExprAff(C, CST1)]]) G7_IRB1 = gen_irbloc(LBL1, [[ExprAff(B, C)], [ExprAff(A, B)]]) G7_IRB2 = gen_irbloc(LBL2, [[ExprAff(D, A)]]) G7_IRA.graph.add_uniq_edge(G7_IRB0.label, G7_IRB1.label) G7_IRA.graph.add_uniq_edge(G7_IRB1.label, G7_IRB1.label) G7_IRA.graph.add_uniq_edge(G7_IRB1.label, G7_IRB2.label) G7_IRA.blocs = dict([(irb.label, irb) for irb in [G7_IRB0, G7_IRB1, G7_IRB2]]) # graph 8 G8_IRA = IRATest() G8_IRB0 = gen_irbloc(LBL0, [[ExprAff(C, CST1)]]) G8_IRB1 = gen_irbloc(LBL1, [[ExprAff(B, C)], [ExprAff(C, D)]]) G8_IRB2 = gen_irbloc(LBL2, [[ExprAff(A, B)]]) G8_IRA.graph.add_uniq_edge(G8_IRB0.label, G8_IRB1.label) G8_IRA.graph.add_uniq_edge(G8_IRB1.label, G8_IRB1.label) G8_IRA.graph.add_uniq_edge(G8_IRB1.label, G8_IRB2.label) G8_IRA.blocs = dict([(irb.label, irb) for irb in [G8_IRB0, G8_IRB1, G8_IRB2]]) # graph 9 is graph 8 # graph 10 G10_IRA = IRATest() G10_IRB1 = gen_irbloc(LBL1, [[ExprAff(B, B + CST2)]]) G10_IRB2 = gen_irbloc(LBL2, [[ExprAff(A, B)]]) G10_IRA.graph.add_uniq_edge(G10_IRB1.label, G10_IRB2.label) G10_IRA.graph.add_uniq_edge(G10_IRB1.label, G10_IRB1.label) G10_IRA.blocs = dict([(irb.label, irb) for irb in [G10_IRB1, G10_IRB2]]) # graph 11 G11_IRA = IRATest() G11_IRB0 = gen_irbloc(LBL0, [[ExprAff(A, CST1), ExprAff(B, CST2)]]) G11_IRB1 = gen_irbloc(LBL1, [[ExprAff(A, B), ExprAff(B, A)]]) G11_IRB2 = gen_irbloc(LBL2, [[ExprAff(A, A - B)]]) G11_IRA.graph.add_uniq_edge(G11_IRB0.label, G11_IRB1.label) G11_IRA.graph.add_uniq_edge(G11_IRB1.label, G11_IRB2.label) G11_IRA.blocs = dict([(irb.label, irb) for irb in [G11_IRB0, G11_IRB1, G11_IRB2]]) # graph 12 G12_IRA = IRATest() G12_IRB0 = gen_irbloc(LBL0, [[ExprAff(B, CST1)]]) G12_IRB1 = gen_irbloc(LBL1, [[ExprAff(A, B)], [ExprAff(B, B + CST2)]]) G12_IRB2 = gen_irbloc(LBL2, [[ExprAff(B, A)]]) G12_IRA.graph.add_uniq_edge(G12_IRB0.label, G12_IRB1.label) G12_IRA.graph.add_uniq_edge(G12_IRB1.label, G12_IRB2.label) G12_IRA.graph.add_uniq_edge(G12_IRB1.label, G12_IRB1.label) G12_IRA.blocs = dict([(irb.label, irb) for irb in [G12_IRB0, G12_IRB1, G12_IRB2]]) # graph 13 G13_IRA = IRATest() G13_IRB0 = gen_irbloc(LBL0, [[ExprAff(A, CST1)], #[ExprAff(B, A)], [ExprAff(G13_IRA.IRDst, ExprId(LBL1))]]) G13_IRB1 = gen_irbloc(LBL1, [[ExprAff(C, A)], #[ExprAff(A, A + CST1)], [ExprAff(G13_IRA.IRDst, ExprCond(R, ExprId(LBL2), ExprId(LBL1)))]]) G13_IRB2 = gen_irbloc(LBL2, [[ExprAff(B, A + CST3)], [ExprAff(A, B + CST3)], [ExprAff(G13_IRA.IRDst, ExprId(LBL1))]]) G13_IRB3 = gen_irbloc(LBL3, [[ExprAff(R, C)]]) G13_IRA.graph.add_uniq_edge(G13_IRB0.label, G13_IRB1.label) G13_IRA.graph.add_uniq_edge(G13_IRB1.label, G13_IRB2.label) G13_IRA.graph.add_uniq_edge(G13_IRB2.label, G13_IRB1.label) G13_IRA.graph.add_uniq_edge(G13_IRB1.label, G13_IRB3.label) G13_IRA.blocs = dict([(irb.label, irb) for irb in [G13_IRB0, G13_IRB1, G13_IRB2, G13_IRB3]]) # graph 14 G14_IRA = IRATest() G14_IRB0 = gen_irbloc(LBL0, [[ExprAff(A, CST1)], [ExprAff(G14_IRA.IRDst, ExprId(LBL1))] ]) G14_IRB1 = gen_irbloc(LBL1, [[ExprAff(B, A)], [ExprAff(G14_IRA.IRDst, ExprCond(C, ExprId(LBL2), ExprId(LBL3)))] ]) G14_IRB2 = gen_irbloc(LBL2, [[ExprAff(D, A)], [ExprAff(A, D + CST1)], [ExprAff(G14_IRA.IRDst, ExprId(LBL1))] ]) G14_IRB3 = gen_irbloc(LBL3, [[ExprAff(R, D + B)]]) G14_IRA.graph.add_uniq_edge(G14_IRB0.label, G14_IRB1.label) G14_IRA.graph.add_uniq_edge(G14_IRB1.label, G14_IRB2.label) G14_IRA.graph.add_uniq_edge(G14_IRB2.label, G14_IRB1.label) G14_IRA.graph.add_uniq_edge(G14_IRB1.label, G14_IRB3.label) G14_IRA.blocs = dict([(irb.label, irb) for irb in [G14_IRB0, G14_IRB1, G14_IRB2, G14_IRB3]]) # graph 16 G15_IRA = IRATest() G15_IRB0 = gen_irbloc(LBL0, [[ExprAff(A, CST1)]]) G15_IRB1 = gen_irbloc(LBL1, [[ExprAff(D, A + B)], [ExprAff(C, D)], [ExprAff(B, C)]]) G15_IRB2 = gen_irbloc(LBL2, [[ExprAff(R, B)]]) G15_IRA.graph.add_uniq_edge(G15_IRB0.label, G15_IRB1.label) G15_IRA.graph.add_uniq_edge(G15_IRB1.label, G15_IRB2.label) G15_IRA.graph.add_uniq_edge(G15_IRB1.label, G15_IRB1.label) G15_IRA.blocs = dict([(irb.label, irb) for irb in [G15_IRB0, G15_IRB1, G15_IRB2]]) # graph 16 G16_IRA = IRATest() G16_IRB0 = gen_irbloc(LBL0, [[ExprAff(A, CST1)]]) G16_IRB1 = gen_irbloc(LBL1, [[ExprAff(R, D)]]) G16_IRB2 = gen_irbloc(LBL2, [[ExprAff(D, A)]]) G16_IRB3 = gen_irbloc(LBL3, [[ExprAff(R, D)]]) G16_IRB4 = gen_irbloc(LBL4, [[ExprAff(R, A)]]) G16_IRB5 = gen_irbloc(LBL5, [[ExprAff(R, A)]]) G16_IRA.graph.add_uniq_edge(G16_IRB0.label, G16_IRB1.label) G16_IRA.graph.add_uniq_edge(G16_IRB1.label, G16_IRB2.label) G16_IRA.graph.add_uniq_edge(G16_IRB2.label, G16_IRB1.label) G16_IRA.graph.add_uniq_edge(G16_IRB1.label, G16_IRB3.label) G16_IRA.graph.add_uniq_edge(G16_IRB3.label, G16_IRB1.label) G16_IRA.graph.add_uniq_edge(G16_IRB1.label, G16_IRB4.label) G16_IRA.graph.add_uniq_edge(G16_IRB4.label, G16_IRB1.label) G16_IRA.graph.add_uniq_edge(G16_IRB1.label, G16_IRB5.label) G16_IRA.blocs = dict([(irb.label, irb) for irb in [G16_IRB0, G16_IRB1, G16_IRB2, G16_IRB3, G16_IRB4, G16_IRB5]]) # graph 17 G17_IRA = IRATest() G17_IRB0 = gen_irbloc(LBL0, [[ExprAff(A, CST1), ExprAff(D, CST2)]]) G17_IRB1 = gen_irbloc(LBL1, [[ExprAff(A, D), ExprAff(B, D)]]) G17_IRB2 = gen_irbloc(LBL2, [[ExprAff(A, A - B)]]) G17_IRA.graph.add_uniq_edge(G17_IRB0.label, G17_IRB1.label) G17_IRA.graph.add_uniq_edge(G17_IRB1.label, G17_IRB2.label) G17_IRA.blocs = dict([(irb.label, irb) for irb in [G17_IRB0, G17_IRB1, G17_IRB2]]) # Test graph 1 G1_TEST1_DN1 = DependencyNode( G1_IRB2.label, A, len(G1_IRB2.irs)) G1_INPUT = (set([G1_TEST1_DN1]), set([G1_IRB0.label])) # Test graph 2 G2_TEST1_DN1 = DependencyNode( G2_IRB2.label, A, len(G2_IRB2.irs)) G2_INPUT = (set([G2_TEST1_DN1]), set([G2_IRB0.label])) # Test graph 3 G3_TEST1_0_DN1 = DependencyNode( G3_IRB3.label, A, len(G3_IRB3.irs)) G3_INPUT = (set([G3_TEST1_0_DN1]), set([G3_IRB0.label])) # Test graph 4 G4_TEST1_DN1 = DependencyNode( G4_IRB2.label, A, len(G2_IRB0.irs)) G4_INPUT = (set([G4_TEST1_DN1]), set([G4_IRB0.label])) # Test graph 5 G5_TEST1_0_DN1 = DependencyNode( G5_IRB2.label, A, len(G5_IRB2.irs)) G5_INPUT = (set([G5_TEST1_0_DN1]), set([G5_IRB0.label])) # Test graph 6 G6_TEST1_0_DN1 = DependencyNode( G6_IRB1.label, A, len(G6_IRB1.irs)) G6_INPUT = (set([G6_TEST1_0_DN1]), set([G6_IRB0.label])) # Test graph 7 G7_TEST1_0_DN1 = DependencyNode( G7_IRB2.label, D, len(G7_IRB2.irs)) G7_INPUT = (set([G7_TEST1_0_DN1]), set([G7_IRB0.label])) # Test graph 8 G8_TEST1_0_DN1 = DependencyNode( G8_IRB2.label, A, len(G8_IRB2.irs)) G8_INPUT = (set([G8_TEST1_0_DN1]), set([G3_IRB0.label])) # Test 9: Multi elements G9_TEST1_0_DN1 = DependencyNode( G8_IRB2.label, A, len(G8_IRB2.irs)) G9_TEST1_0_DN5 = DependencyNode( G8_IRB2.label, C, len(G8_IRB2.irs)) G9_INPUT = (set([G9_TEST1_0_DN1, G9_TEST1_0_DN5]), set([G8_IRB0.label])) # Test 10: loop at beginning G10_TEST1_0_DN1 = DependencyNode( G10_IRB2.label, A, len(G10_IRB2.irs)) G10_INPUT = (set([G10_TEST1_0_DN1]), set([G10_IRB1.label])) # Test 11: no dual bloc emulation G11_TEST1_DN1 = DependencyNode( G11_IRB2.label, A, len(G11_IRB2.irs)) G11_INPUT = (set([G11_TEST1_DN1]), set([G11_IRB0.label])) # Test graph 12 G12_TEST1_0_DN1 = DependencyNode(G12_IRB2.label, B, 1) G12_INPUT = (set([G12_TEST1_0_DN1]), set([])) # Test graph 13: # All filters G13_TEST1_0_DN4 = DependencyNode(G13_IRB3.label, R, 1) G13_INPUT = (set([G13_TEST1_0_DN4]), set([])) # Test graph 14 # All filters G14_TEST1_0_DN1 = DependencyNode(G14_IRB3.label, R, 1) G14_INPUT = (set([G14_TEST1_0_DN1]), set([])) # Test graph 15 G15_TEST1_0_DN1 = DependencyNode(G15_IRB2.label, R, 1) G15_INPUT = (set([G15_TEST1_0_DN1]), set([])) # Test graph 16 G16_TEST1_0_DN1 = DependencyNode(G16_IRB5.label, R, 1) G16_INPUT = (set([G16_TEST1_0_DN1]), set([])) # Test graph 17 G17_TEST1_DN1 = DependencyNode(G17_IRB2.label, A, 1) G17_INPUT = (set([G17_TEST1_DN1]), set([])) FAILED = set() 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 """ 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)) 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 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), (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) = 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", "_implicit"] # Test classes for g_ind, g_dep in enumerate([DependencyGraph(g_ira), DependencyGraph(g_ira, apply_simp=False), DependencyGraph(g_ira, follow_mem=False), DependencyGraph(g_ira, follow_mem=False, follow_call=False), # DependencyGraph(g_ira, implicit=True), ]): # 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 # Test public APIs 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 test_num in sorted(FAILED): print test_num, else: print "SUCCESS" # Return an error status on error assert not FAILED