Merge pull request #496 from commial/feature/expr_range

Feature/expr range

1 files changed, 65 insertions, 0 deletions

diff --git a/miasm2/analysis/expression_range.py b/miasm2/analysis/expression_range.py
new file mode 100644
index 00000000..ca63588c
--- /dev/null
+++ b/miasm2/analysis/expression_range.py
@@ -0,0 +1,65 @@
+"""Naive range analysis for expression"""
+
+from miasm2.analysis.modularintervals import ModularIntervals
+
+_op_range_handler = {
+    "+": lambda x, y: x + y,
+    "&": lambda x, y: x & y,
+    "|": lambda x, y: x | y,
+    "^": lambda x, y: x ^ y,
+    ">>": lambda x, y: x >> y,
+    "a>>": lambda x, y: x.arithmetic_shift_right(y),
+    "<<": lambda x, y: x << y,
+    ">>": lambda x, y: x >> y,
+    ">>>": lambda x, y: x.rotation_right(y),
+    "<<<": lambda x, y: x.rotation_left(y),
+}
+
+def expr_range(expr):
+    """Return a ModularIntervals containing the range of possible values of
+    @expr"""
+    max_bound = (1 << expr.size) - 1
+    if expr.is_int():
+        return ModularIntervals(expr.size, [(int(expr), int(expr))])
+    elif expr.is_id() or expr.is_mem():
+        return ModularIntervals(expr.size, [(0, max_bound)])
+    elif expr.is_slice():
+        interval_mask = ((1 << expr.start) - 1) ^ ((1 << expr.stop) - 1)
+        arg = expr_range(expr.arg)
+        # Mask for possible range, and shift range
+        return ((arg & interval_mask) >> expr.start).size_update(expr.size)
+    elif expr.is_compose():
+        sub_ranges = [expr_range(arg) for arg in expr.args]
+        args_idx = [info[0] for info in expr.iter_args()]
+
+        # No shift for the first one
+        ret = sub_ranges[0].size_update(expr.size)
+
+        # Doing it progressively (2 by 2)
+        for shift, sub_range in zip(args_idx[1:], sub_ranges[1:]):
+            ret |= sub_range.size_update(expr.size) << shift
+        return ret
+    elif expr.is_op():
+        # A few operation are handled with care
+        # Otherwise, overapproximate (ie. full range interval)
+        if expr.op in _op_range_handler:
+            sub_ranges = [expr_range(arg) for arg in expr.args]
+            return reduce(_op_range_handler[expr.op],
+                          (sub_range for sub_range in sub_ranges[1:]),
+                          sub_ranges[0])
+        elif expr.op == "-":
+            assert len(expr.args) == 1
+            return - expr_range(expr.args[0])
+        elif expr.op == "%":
+            assert len(expr.args) == 2
+            op, mod = [expr_range(arg) for arg in expr.args]
+            if mod.intervals.length == 1:
+                # Modulo intervals is not supported
+                return op % mod.intervals.hull()[0]
+
+        # Operand not handled, return the full domain
+        return ModularIntervals(expr.size, [(0, max_bound)])
+    elif expr.is_cond():
+        return expr_range(expr.src1).union(expr_range(expr.src2))
+    else:
+        raise TypeError("Unsupported type: %s" % expr.__class__)