diff options
Diffstat (limited to 'src/miasm/analysis/simplifier.py')
| -rw-r--r-- | src/miasm/analysis/simplifier.py | 325 |
1 files changed, 325 insertions, 0 deletions
diff --git a/src/miasm/analysis/simplifier.py b/src/miasm/analysis/simplifier.py new file mode 100644 index 00000000..a7c29b06 --- /dev/null +++ b/src/miasm/analysis/simplifier.py @@ -0,0 +1,325 @@ +""" +Apply simplification passes to an IR cfg +""" + +import logging +import warnings +from functools import wraps +from miasm.analysis.ssa import SSADiGraph +from miasm.analysis.outofssa import UnSSADiGraph +from miasm.analysis.data_flow import DiGraphLivenessSSA +from miasm.expression.simplifications import expr_simp +from miasm.ir.ir import AssignBlock, IRBlock +from miasm.analysis.data_flow import DeadRemoval, \ + merge_blocks, remove_empty_assignblks, \ + del_unused_edges, \ + PropagateExpressions, DelDummyPhi + + +log = logging.getLogger("simplifier") +console_handler = logging.StreamHandler() +console_handler.setFormatter(logging.Formatter("[%(levelname)-8s]: %(message)s")) +log.addHandler(console_handler) +log.setLevel(logging.WARNING) + + +def fix_point(func): + @wraps(func) + def ret_func(self, ircfg, head): + log.debug('[%s]: start', func.__name__) + has_been_modified = False + modified = True + while modified: + modified = func(self, ircfg, head) + has_been_modified |= modified + log.debug( + '[%s]: stop %r', + func.__name__, + has_been_modified + ) + return has_been_modified + return ret_func + + +class IRCFGSimplifier(object): + """ + Simplify an IRCFG + This class applies passes until reaching a fix point + """ + + def __init__(self, lifter): + self.lifter = lifter + self.init_passes() + + @property + def ir_arch(self): + warnings.warn('DEPRECATION WARNING: use ".lifter" instead of ".ir_arch"') + return self.lifter + + def init_passes(self): + """ + Init the array of simplification passes + """ + self.passes = [] + + @fix_point + def simplify(self, ircfg, head): + """ + Apply passes until reaching a fix point + Return True if the graph has been modified + + @ircfg: IRCFG instance to simplify + @head: Location instance of the ircfg head + """ + modified = False + for simplify_pass in self.passes: + modified |= simplify_pass(ircfg, head) + return modified + + def __call__(self, ircfg, head): + return self.simplify(ircfg, head) + + +class IRCFGSimplifierCommon(IRCFGSimplifier): + """ + Simplify an IRCFG + This class applies following passes until reaching a fix point: + - simplify_ircfg + - do_dead_simp_ircfg + """ + def __init__(self, lifter, expr_simp=expr_simp): + self.expr_simp = expr_simp + super(IRCFGSimplifierCommon, self).__init__(lifter) + self.deadremoval = DeadRemoval(self.lifter) + + def init_passes(self): + self.passes = [ + self.simplify_ircfg, + self.do_dead_simp_ircfg, + ] + + @fix_point + def simplify_ircfg(self, ircfg, _head): + """ + Apply self.expr_simp on the @ircfg until reaching fix point + Return True if the graph has been modified + + @ircfg: IRCFG instance to simplify + """ + modified = ircfg.simplify(self.expr_simp) + return modified + + @fix_point + def do_dead_simp_ircfg(self, ircfg, head): + """ + Apply: + - dead_simp + - remove_empty_assignblks + - merge_blocks + on the @ircfg until reaching fix point + Return True if the graph has been modified + + @ircfg: IRCFG instance to simplify + @head: Location instance of the ircfg head + """ + modified = self.deadremoval(ircfg) + modified |= remove_empty_assignblks(ircfg) + modified |= merge_blocks(ircfg, set([head])) + return modified + + +class IRCFGSimplifierSSA(IRCFGSimplifierCommon): + """ + Simplify an IRCFG. + The IRCF is first transformed in SSA, then apply transformations passes + and apply out-of-ssa. Final passes of IRcfgSimplifier are applied + + This class apply following pass until reaching a fix point: + - do_propagate_expressions + - do_dead_simp_ssa + """ + + def __init__(self, lifter, expr_simp=expr_simp): + super(IRCFGSimplifierSSA, self).__init__(lifter, expr_simp) + + self.lifter.ssa_var = {} + self.all_ssa_vars = {} + + self.ssa_forbidden_regs = self.get_forbidden_regs() + + self.propag_expressions = PropagateExpressions() + self.del_dummy_phi = DelDummyPhi() + + self.deadremoval = DeadRemoval(self.lifter, self.all_ssa_vars) + + def get_forbidden_regs(self): + """ + Return a set of immutable register during SSA transformation + """ + regs = set( + [ + self.lifter.pc, + self.lifter.IRDst, + self.lifter.arch.regs.exception_flags + ] + ) + return regs + + def init_passes(self): + """ + Init the array of simplification passes + """ + self.passes = [ + self.simplify_ssa, + self.do_propagate_expressions, + self.do_del_dummy_phi, + self.do_dead_simp_ssa, + self.do_remove_empty_assignblks, + self.do_del_unused_edges, + self.do_merge_blocks, + ] + + + + def ircfg_to_ssa(self, ircfg, head): + """ + Apply the SSA transformation to @ircfg using it's @head + + @ircfg: IRCFG instance to simplify + @head: Location instance of the ircfg head + """ + ssa = SSADiGraph(ircfg) + ssa.immutable_ids.update(self.ssa_forbidden_regs) + ssa.ssa_variable_to_expr.update(self.all_ssa_vars) + ssa.transform(head) + self.all_ssa_vars.update(ssa.ssa_variable_to_expr) + self.lifter.ssa_var.update(ssa.ssa_variable_to_expr) + return ssa + + def ssa_to_unssa(self, ssa, head): + """ + Apply the out-of-ssa transformation to @ssa using it's @head + + @ssa: SSADiGraph instance + @head: Location instance of the graph head + """ + cfg_liveness = DiGraphLivenessSSA(ssa.graph) + cfg_liveness.init_var_info(self.lifter) + cfg_liveness.compute_liveness() + + UnSSADiGraph(ssa, head, cfg_liveness) + return ssa.graph + + @fix_point + def simplify_ssa(self, ssa, _head): + """ + Apply self.expr_simp on the @ssa.graph until reaching fix point + Return True if the graph has been modified + + @ssa: SSADiGraph instance + """ + modified = ssa.graph.simplify(self.expr_simp) + return modified + + @fix_point + def do_del_unused_edges(self, ssa, head): + """ + Del unused edges of the ssa graph + @head: Location instance of the graph head + """ + modified = del_unused_edges(ssa.graph, set([head])) + return modified + + def do_propagate_expressions(self, ssa, head): + """ + Expressions propagation through ExprId in the @ssa graph + @head: Location instance of the graph head + """ + modified = self.propag_expressions.propagate(ssa, head) + return modified + + @fix_point + def do_del_dummy_phi(self, ssa, head): + """ + Del dummy phi + @head: Location instance of the graph head + """ + modified = self.del_dummy_phi.del_dummy_phi(ssa, head) + return modified + + @fix_point + def do_remove_empty_assignblks(self, ssa, head): + """ + Remove empty assignblks + @head: Location instance of the graph head + """ + modified = remove_empty_assignblks(ssa.graph) + return modified + + @fix_point + def do_merge_blocks(self, ssa, head): + """ + Merge blocks with one parent/son + @head: Location instance of the graph head + """ + modified = merge_blocks(ssa.graph, set([head])) + return modified + + @fix_point + def do_dead_simp_ssa(self, ssa, head): + """ + Apply: + - deadrm + - remove_empty_assignblks + - del_unused_edges + - merge_blocks + on the @ircfg until reaching fix point + Return True if the graph has been modified + + @ircfg: IRCFG instance to simplify + @head: Location instance of the ircfg head + """ + modified = self.deadremoval(ssa.graph) + return modified + + def do_simplify(self, ssa, head): + """ + Apply passes until reaching a fix point + Return True if the graph has been modified + """ + return super(IRCFGSimplifierSSA, self).simplify(ssa, head) + + def do_simplify_loop(self, ssa, head): + """ + Apply do_simplify until reaching a fix point + SSA is updated between each do_simplify + Return True if the graph has been modified + """ + modified = True + while modified: + modified = self.do_simplify(ssa, head) + # Update ssa structs + ssa = self.ircfg_to_ssa(ssa.graph, head) + return ssa + + def simplify(self, ircfg, head): + """ + Add access to "abi out regs" in each leaf block + Apply SSA transformation to @ircfg + Apply passes until reaching a fix point + Apply out-of-ssa transformation + Apply post simplification passes + + Updated simplified IRCFG instance and return it + + @ircfg: IRCFG instance to simplify + @head: Location instance of the ircfg head + """ + + ssa = self.ircfg_to_ssa(ircfg, head) + ssa = self.do_simplify_loop(ssa, head) + ircfg = self.ssa_to_unssa(ssa, head) + ircfg_simplifier = IRCFGSimplifierCommon(self.lifter) + ircfg_simplifier.deadremoval.add_expr_to_original_expr(self.all_ssa_vars) + ircfg_simplifier.simplify(ircfg, head) + return ircfg |