Merge pull request #339 from serpilliere/new_depgraph_mod_fix01

New DependencyGraph algorithm

4 files changed, 85 insertions, 39 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)