diff options
| -rw-r--r-- | example/ida/depgraph.py | 201 | ||||
| -rw-r--r-- | miasm2/analysis/depgraph.py | 608 | ||||
| -rw-r--r-- | miasm2/arch/x86/arch.py | 4 | ||||
| -rw-r--r-- | miasm2/arch/x86/sem.py | 55 | ||||
| -rw-r--r-- | miasm2/core/graph.py | 2 | ||||
| -rw-r--r-- | miasm2/ir/translators/C.py | 8 | ||||
| -rw-r--r-- | miasm2/jitter/vm_mngr.c | 19 | ||||
| -rw-r--r-- | miasm2/os_dep/win_api_x86_32.py | 4 | ||||
| -rw-r--r-- | test/analysis/depgraph.py | 602 | ||||
| -rw-r--r-- | test/arch/x86/arch.py | 4 | ||||
| -rw-r--r-- | test/ir/ir2C.py | 2 | ||||
| -rw-r--r-- | test/samples/x86_32/bsr_bsf.S | 42 | ||||
| -rw-r--r-- | test/test_all.py | 27 |
13 files changed, 1534 insertions, 44 deletions
diff --git a/example/ida/depgraph.py b/example/ida/depgraph.py new file mode 100644 index 00000000..65a3c88f --- /dev/null +++ b/example/ida/depgraph.py @@ -0,0 +1,201 @@ +import sys + +from idaapi import GraphViewer +from miasm2.core.bin_stream_ida import bin_stream_ida +from miasm2.core.asmbloc import * +from miasm2.expression.simplifications import expr_simp +from miasm2.analysis.machine import Machine +from miasm2.analysis.depgraph import DependencyGraph, DependencyGraph_NoMemory + +from utils import guess_machine + + +class depGraphSettingsForm(Form): + + def __init__(self, ira): + + self.ira = ira + self.address = ScreenEA() + cur_bloc = list(ira.getby_offset(self.address))[0] + for line_nb, l in enumerate(cur_bloc.lines): + if l.offset == self.address: + break + cur_label = str(cur_bloc.label) + labels = sorted(map(str, ira.blocs.keys())) + regs = sorted(ir_arch.arch.regs.all_regs_ids_byname.keys()) + reg_default = regs[0] + for i in xrange(10): + opnd = GetOpnd(self.address, i).upper() + if opnd in regs: + reg_default = opnd + break + + Form.__init__(self, +r"""BUTTON YES* Launch +BUTTON CANCEL NONE +Dependency Graph Settings + +Track the element: +<Before the line:{rBeforeLine}> +<After the line:{rAfterLine}> +<At the end of the basic block:{rEndBlock}>{cMode}> + +<Target basic block:{cbBBL}> +<Register to track:{cbReg}> +<Line number:{iLineNb}> + +Method to use: +<Best effort:{rBest}> +<No memory (sound & complete):{rNoMem}>{cMethod}> + +<Highlight color:{cColor}> +""", { + 'cbReg': Form.DropdownListControl( + items=regs, + readonly=False, + selval=reg_default), + 'cMode': Form.RadGroupControl(("rBeforeLine", "rAfterLine", + "rEndBlock")), + 'cMethod': Form.RadGroupControl(("rBest", "rNoMem")), + 'iLineNb': Form.NumericInput(tp=Form.FT_RAWHEX, + value=line_nb), + 'cbBBL': Form.DropdownListControl( + items=labels, + readonly=False, + selval=cur_label), + 'cColor': Form.ColorInput(value=0xc0c020), + }) + + self.Compile() + + @property + def label(self): + value = self.cbBBL.value + for real_label in self.ira.blocs: + if str(real_label) == value: + return real_label + raise ValueError("Bad label") + + @property + def line_nb(self): + value = self.iLineNb.value + mode = self.cMode.value + if mode == 0: + return value + elif mode == 1: + return value + 1 + else: + return len(self.ira.blocs[self.label].irs) + + @property + def elements(self): + value = self.cbReg.value + return set([ir_arch.arch.regs.all_regs_ids_byname[value]]) + + @property + def method(self): + value = self.cMethod.value + if value == 0: + return DependencyGraph + elif value == 1: + return DependencyGraph_NoMemory + else: + raise ValueError("Unknown method") + + @property + def color(self): + return self.cColor.value + + +# Init +machine = guess_machine() +mn, dis_engine, ira = machine.mn, machine.dis_engine, machine.ira + +bs = bin_stream_ida() +mdis = dis_engine(bs, dont_dis_nulstart_bloc=True) +ir_arch = ira(mdis.symbol_pool) + +# Populate symbols with ida names +for ad, name in Names(): + if name is None: + continue + mdis.symbol_pool.add_label(name, ad) + +# Get the current function +addr = ScreenEA() +func = idaapi.get_func(addr) +blocs = mdis.dis_multibloc(func.startEA) + +# Generate IR +for bloc in blocs: + ir_arch.add_bloc(bloc) + +# Simplify affectations +for irb in ir_arch.blocs.values(): + for irs in irb.irs: + for i, e in enumerate(irs): + e.dst, e.src = expr_simp(e.dst), expr_simp(e.src) + +# Build the IRA Graph +ir_arch.gen_graph() + +# Get settings +settings = depGraphSettingsForm(ir_arch) +settings.Execute() + +# Get dependency graphs +dg = (settings.method)(ir_arch) +graphs = dg.get(settings.label, settings.elements, settings.line_nb, + set([ir_arch.symbol_pool.getby_offset(func.startEA)])) + +# Display the result +comments = {} +sol_nb = 0 + +def clean_lines(): + "Remove previous comments" + global comments + for offset in comments: + SetColor(offset, CIC_ITEM, 0xffffff) + MakeComm(offset, "") + comments = {} + +def treat_element(): + "Display an element" + global graphs, comments, sol_nb, settings + + try: + graph = graphs.next() + except StopIteration: + comments = {} + print "Done: %d solutions" % (sol_nb) + return + + sol_nb += 1 + print "Get graph number %02d" % sol_nb + filename = "/tmp/solution_0x%08x_%02d.dot" % (addr, sol_nb) + print "Dump the graph to %s" % filename + open(filename, "w").write(graph.graph.dot()) + + for node in graph.relevant_nodes: + try: + offset = ir_arch.blocs[node.label].lines[node.line_nb].offset + except IndexError: + print "Unable to highlight %s" % node + continue + comments[offset] = comments.get(offset, []) + [node.element] + SetColor(offset, CIC_ITEM, settings.color) + + print "Possible value: %s" % graph.emul().values()[0] + + for offset, elements in comments.iteritems(): + MakeComm(offset, ", ".join(map(str, elements))) + +def next_element(): + "Display the next element" + clean_lines() + treat_element() + +# Register and launch +idaapi.add_hotkey("Shift-N", next_element) +treat_element() diff --git a/miasm2/analysis/depgraph.py b/miasm2/analysis/depgraph.py new file mode 100644 index 00000000..06b5b8b6 --- /dev/null +++ b/miasm2/analysis/depgraph.py @@ -0,0 +1,608 @@ +"""Provide dependency graph""" +import itertools +import miasm2.expression.expression as m2_expr +from miasm2.core.graph import DiGraph +from miasm2.core.asmbloc import asm_label +from miasm2.expression.simplifications import expr_simp +from miasm2.ir.symbexec import symbexec +from miasm2.ir.ir import irbloc + + +class DependencyNode(object): + """Node elements of a DependencyGraph + + A dependency node stands for the dependency on the @element at line number + @line_nb in the IRblock named @label, *before* the evaluation of this + line. + """ + + def __init__(self, label, element, line_nb, modifier=False): + """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._hash = hash((self._label, self._element, self._line_nb)) + + def __hash__(self): + return self._hash + + def __eq__(self, depnode): + if not isinstance(depnode, self.__class__): + return False + return (self.label == depnode.label and + self.element == depnode.element and + self.line_nb == depnode.line_nb) + + def __cmp__(self, node): + if not isinstance(node, self.__class__): + raise ValueError("Compare error between %s, %s" % (self.__class__, + node.__class__)) + return cmp((self.label, self.element, self.line_nb), + (node.label, node.element, node.line_nb)) + + def __str__(self): + return "<%s %s %s %s M:%s>"%(self.__class__.__name__, + self.label.name, self.element, + self.line_nb, self.modifier) + + def __repr__(self): + return self.__str__() + + @property + def label(self): + "Name of the current IRBlock" + return self._label + + @property + def element(self): + "Current tracked Expr" + return self._element + + @property + def line_nb(self): + "Line in the current IRBlock" + return self._line_nb + + @property + def modifier(self): + """Evaluating the current line involves a modification of tracked + dependencies""" + return self._modifier + + @modifier.setter + def modifier(self, value): + if not isinstance(value, bool): + raise ValueError("Modifier must be a boolean") + self._modifier = value + + +class DependencyDict(object): + """Internal structure for the DependencyGraph algorithm""" + + 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 = {} + + def __eq__(self, depdict): + if not isinstance(depdict, self.__class__): + return False + return (self._label == depdict.label and + self._cache == depdict.cache and + self._pending == depdict.pending) + + 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" + + # Initialize + new_history = list(self.history) + depdict = DependencyDict(self.label, new_history) + + # Copy values + for key, values in self.cache.iteritems(): + depdict.cache[key] = set(values) + depdict.pending.update(self.pending) + + return depdict + + 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 + """ + depdict = DependencyDict(label, list(self.history) + [self]) + for key, values in self.cache.iteritems(): + depdict.cache[key] = set(values) + return depdict + + 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 + + @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): + "Dictionnary of DependencyNode and their dependencies" + return self._cache + + @property + def pending(self): + """Dictionnary of DependencyNode and their dependencies, waiting for + resolution""" + return self._pending + + def _get_modifiers_in_cache(self, depnode, force=False): + """Recursively find nodes in the path of @depnode which are modifiers. + Update the internal cache + If @depnode is already managed (ie. in @depnode_queued), abort""" + + # Base case + if depnode not in self._cache: + # Constant does not have any dependencies + return [depnode] if depnode.modifier else [] + + if depnode.modifier and not force: + return [depnode] + + # Recursion + dependencies = self._cache[depnode] + + out = set() + ## Launch on each depnodes + parallels = [] + for depnode in dependencies: + parallels.append(self._get_modifiers_in_cache(depnode)) + + if parallels: + for parallel in itertools.product(*parallels): + out.update(parallel) + + return out + + def clean_modifiers_in_cache(self): + """Remove intermediary states (non modifier depnodes) in the internal + cache values""" + + cache_out = {} + for depnode in self._cache.keys(): + cache_out[depnode] = self._get_modifiers_in_cache(depnode, + force=True) + self._cache = cache_out + + 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] + 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 + 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 + + 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 + """ + # Init + todo = set(node_heads) + used_nodes = set() + + # Map + while todo: + node = todo.pop() + 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] + + +class DependencyResult(object): + """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 + 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): + "Lazy" + if self._graph is None: + self._graph = self._depdict.as_graph(self._input_depnodes) + return self._graph + + @property + def history(self): + return list(self._depdict.history) + [self._depdict] + + @property + def unresolved(self): + return set(self._depdict.pending) + + @property + def relevant_nodes(self): + output = set() + for depnodes in self._depdict.cache.values(): + output.update(depnodes) + return output + + @property + def relevant_labels(self): + # 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]: + if label not in output and label in used_labels: + output.append(label) + + return output + + @property + def input(self): + return self._input_depnodes + + def emul(self): + """Symbolic execution of relevant nodes according to the history + Return the values of input nodes' elements + + /!\ The emulation is not safe if there is a loop in the relevant labels + """ + # Init + new_ira = (self._ira.__class__)() + lines = self.relevant_nodes + affects = [] + + # Build a single affectation block according to history + for label in self.relevant_labels[::-1]: + affected_lines = [line.line_nb for line in lines + if line.label == label] + irs = self._ira.blocs[label].irs + for line_nb in sorted(affected_lines): + affects.append(irs[line_nb]) + + # Eval the block + temp_label = asm_label("Temp") + sb = symbexec(new_ira, new_ira.arch.regs.regs_init) + sb.emulbloc(irbloc(temp_label, affects)) + + # Return only inputs values (others could be wrongs) + return {depnode.element: sb.symbols[depnode.element] + for depnode in self.input} + + +class DependencyGraph(object): + """Implementation of a dependency graph + + A dependency graph contains DependencyNode as nodes. The oriented edges + stand for a dependency. + The dependency graph is made of the lines of a group of IRblock + *explicitely* involved in the equation of given element. + """ + + def __init__(self, ira): + """Create a DependencyGraph linked to @ira + @ira: IRAnalysis instance + """ + # Init + self._ira = ira + + # The IRA graph must be computed + self._ira.gen_graph() + + 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 _resolve_depNode(self, depnode): + """Compute and return the dependencies involved by @depnode""" + + 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 + + for affect in self._get_affblock(depnode): + if affect.dst == depnode.element: + ### Avoid tracking useless elements, as XOR EAX, EAX + src = expr_simp(affect.src) + + read.update(src.get_r(mem_read=True, cst_read=True)) + modifier = True + + ## If it's not a modifier affblock, reinject current element + if not modifier: + read = set([depnode.element]) + + ## Build output + dependencies = set() + for element in read: + dependencies.add(DependencyNode(depnode.label, + element, + depnode.line_nb - 1, + modifier=modifier)) + output = dependencies + + return output + + def _updateDependencyDict(self, depdict): + """Update DependencyDict 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 + continue + + if depdict.is_head(depnode): + depdict.pending.add(depnode) + # A head cannot have dependencies inside the current IRblock + continue + + # Find dependency of the current depnode + sub_depnodes = self._resolve_depNode(depnode) + depdict.cache[depnode] = sub_depnodes + + # Add to the worklist its dependencies + todo.update(sub_depnodes) + + # Pending states will be override in cache + for depnode in depdict.pending: + try: + del depdict.cache[depnode] + except KeyError: + continue + + def _get_previousblocks(self, label): + """Return an iterator on predecessors blocks of @label, with their + lengths""" + preds = self._ira.g.predecessors_iter(label) + for pred_label in preds: + length = len(self._get_irs(pred_label)) + yield (pred_label, length) + + def _processInterBloc(self, depnodes, heads): + """Create a DependencyDict from @depnodes, and propagate DependencyDicts + through all blocs + """ + # Create an DependencyDict which will only contain our depnodes + current_depdict = DependencyDict(list(depnodes)[0].label, []) + current_depdict.pending.update(depnodes) + + # Init the work list + done = [] + todo = [current_depdict] + + while todo: + depdict = todo.pop() + + # Update the dependencydict until fixed point is reached + self._updateDependencyDict(depdict) + + # Avoid infinite loops + if depdict in done: + continue + done.append(depdict) + + # No more dependencies + if len(depdict.pending) == 0: + yield depdict + continue + + # Propagate the DependencyDict to all parents + for label, irb_len in self._get_previousblocks(depdict.label): + + ## Duplicate the DependencyDict + new_depdict = depdict.extend(label) + + ## 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) + ### The new node has to be computed in _updateDependencyDict + new_depdict.cache[depnode_head] = set([new_depnode]) + new_depdict.pending.add(new_depnode) + + ## Manage the new element + todo.append(new_depdict) + + # Return the node if it's a final one, ie. it's a head + if depdict.label in heads: + yield depdict.copy() + + def get(self, label, elements, line_nb, heads): + """Compute the dependencies of @elements at line number @line_nb in + the block named @label in the current IRA, before the execution of + this line. Dependency check stop if one of @heads is reached + @label: asm_label instance + @element: set of Expr instances + @line_nb: int + @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)) + + # Compute final depdicts + depdicts = self._processInterBloc(input_depnodes, heads) + + # Unify solutions + unified = [] + for final_depdict in depdicts: + ## Keep only relevant nodes + final_depdict.clean_modifiers_in_cache() + 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 DependencyResult(self._ira, final_depdict, input_depnodes) + + def get_fromDepNodes(self, depnodes, heads): + """Alias for the get() method. Use the attributes of @depnodes as + argument. + PRE: Labels and lines of depnodes have to be equals + @depnodes: set of DependencyNode instances + @heads: set of asm_label instances + """ + lead = list(depnodes)[0] + elements = set([depnode.element for depnode in depnodes]) + return self.get(lead.label, elements, lead.line_nb, heads) + + def get_fromEnd(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) + + +class DependencyGraph_NoMemory(DependencyGraph): + """Dependency graph without memory tracking. + + That way, the output has following properties: + - Only explicit dependencies are followed + - Soundness: all results are corrects + - Completeness: all possible solutions are founds + """ + + def _resolve_depNode(self, depnode): + """Compute and return the dependencies involved by @depnode""" + # Get inital elements + result = super(DependencyGraph_NoMemory, self)._resolve_depNode(depnode) + + # If @depnode depends on a memory element, give up + for node in result: + if isinstance(node.element, m2_expr.ExprMem): + return set() + + return result diff --git a/miasm2/arch/x86/arch.py b/miasm2/arch/x86/arch.py index c5535153..c059e1be 100644 --- a/miasm2/arch/x86/arch.py +++ b/miasm2/arch/x86/arch.py @@ -3745,7 +3745,7 @@ addop("popad", [bs8(0x61), bs_opmode32]) # popf_name = {16:'POPF', 32:'POPFD', 64:'POPFQ'} # bs_popf_name = bs_modname_size(l=0, name=popf_name) # addop("popf", [bs8(0x9d), bs_popf_name]) -addop("popf", [bs8(0x9d), bs_opmode16]) +addop("popfw", [bs8(0x9d), bs_opmode16]) addop("popfd", [bs8(0x9d), bs_opmode32]) addop("popfq", [bs8(0x9d), bs_opmode64]) @@ -3775,7 +3775,7 @@ addop("pushad", [bs8(0x60), bs_opmode32_no64]) # pushf_name = {16:'PUSHF', 32:'PUSHFD', 64:'PUSHFQ'} # bs_pushf_name = bs_modname_size(l=0, name=pushf_name) # addop("pushf", [bs8(0x9c), bs_pushf_name]) -addop("pushf", [bs8(0x9c), bs_opmode16]) +addop("pushfw", [bs8(0x9c), bs_opmode16]) addop("pushfd", [bs8(0x9c), bs_opmode32]) addop("pushfq", [bs8(0x9c), bs_opmode64]) diff --git a/miasm2/arch/x86/sem.py b/miasm2/arch/x86/sem.py index bc98baf3..52cec344 100644 --- a/miasm2/arch/x86/sem.py +++ b/miasm2/arch/x86/sem.py @@ -970,7 +970,7 @@ def popfd(ir, instr): def popfw(ir, instr): - tmp = m2_expr.ExprMem(esp) + tmp = m2_expr.ExprMem(mRSP[instr.mode]) e = [] e.append(m2_expr.ExprAff(cf, m2_expr.ExprSlice(tmp, 0, 1))) e.append(m2_expr.ExprAff(pf, m2_expr.ExprSlice(tmp, 2, 3))) @@ -983,7 +983,7 @@ def popfw(ir, instr): e.append(m2_expr.ExprAff(of, m2_expr.ExprSlice(tmp, 11, 12))) e.append(m2_expr.ExprAff(iopl, m2_expr.ExprSlice(tmp, 12, 14))) e.append(m2_expr.ExprAff(nt, m2_expr.ExprSlice(tmp, 14, 15))) - e.append(m2_expr.ExprAff(esp, esp + m2_expr.ExprInt32(2))) + e.append(m2_expr.ExprAff(mRSP[instr.mode], mRSP[instr.mode] + m2_expr.ExprInt_fromsize(mRSP[instr.mode].size, 2))) return e, [] @@ -2496,32 +2496,41 @@ def aas(ir, instr, ): return e, [] -def bsf(ir, instr, a, b): - lbl_do = m2_expr.ExprId(ir.gen_label(), instr.mode) - lbl_skip = m2_expr.ExprId(ir.get_next_label(instr), instr.mode) +def bsr_bsf(ir, instr, a, b, op_name): + """ + IF SRC == 0 + ZF = 1 + DEST is left unchanged + ELSE + ZF = 0 + DEST = @op_name(SRC) + """ + lbl_src_null = m2_expr.ExprId(ir.gen_label(), instr.mode) + lbl_src_not_null = m2_expr.ExprId(ir.gen_label(), instr.mode) + lbl_next = m2_expr.ExprId(ir.get_next_label(instr), instr.mode) - e = [m2_expr.ExprAff(zf, m2_expr.ExprCond(b, m2_expr.ExprInt_from(zf, 0), - m2_expr.ExprInt_from(zf, 1)))] + aff_dst = m2_expr.ExprAff(ir.IRDst, lbl_next) + e = [m2_expr.ExprAff(ir.IRDst, m2_expr.ExprCond(b, + lbl_src_not_null, + lbl_src_null))] + e_src_null = [] + e_src_null.append(m2_expr.ExprAff(zf, m2_expr.ExprInt_from(zf, 1))) + # XXX destination is undefined + e_src_null.append(aff_dst) - e_do = [] - e_do.append(m2_expr.ExprAff(a, m2_expr.ExprOp('bsf', b))) - e_do.append(m2_expr.ExprAff(ir.IRDst, lbl_skip)) - e.append(m2_expr.ExprAff(ir.IRDst, m2_expr.ExprCond(b, lbl_do, lbl_skip))) - return e, [irbloc(lbl_do.name, [e_do])] + e_src_not_null = [] + e_src_not_null.append(m2_expr.ExprAff(zf, m2_expr.ExprInt_from(zf, 0))) + e_src_not_null.append(m2_expr.ExprAff(a, m2_expr.ExprOp(op_name, b))) + e_src_not_null.append(aff_dst) + return e, [irbloc(lbl_src_null.name, [e_src_null]), + irbloc(lbl_src_not_null.name, [e_src_not_null])] -def bsr(ir, instr, a, b): - lbl_do = m2_expr.ExprId(ir.gen_label(), instr.mode) - lbl_skip = m2_expr.ExprId(ir.get_next_label(instr), instr.mode) - - e = [m2_expr.ExprAff(zf, m2_expr.ExprCond(b, m2_expr.ExprInt_from(zf, 0), - m2_expr.ExprInt_from(zf, 1)))] +def bsf(ir, instr, a, b): + return bsr_bsf(ir, instr, a, b, "bsf") - e_do = [] - e_do.append(m2_expr.ExprAff(a, m2_expr.ExprOp('bsr', b))) - e_do.append(m2_expr.ExprAff(ir.IRDst, lbl_skip)) - e.append(m2_expr.ExprAff(ir.IRDst, m2_expr.ExprCond(b, lbl_do, lbl_skip))) - return e, [irbloc(lbl_do.name, [e_do])] +def bsr(ir, instr, a, b): + return bsr_bsf(ir, instr, a, b, "bsr") def arpl(ir, instr, a, b): diff --git a/miasm2/core/graph.py b/miasm2/core/graph.py index 2b873ad9..b25907e5 100644 --- a/miasm2/core/graph.py +++ b/miasm2/core/graph.py @@ -1,6 +1,6 @@ from collections import defaultdict -class DiGraph: +class DiGraph(object): """Implementation of directed graph""" def __init__(self): diff --git a/miasm2/ir/translators/C.py b/miasm2/ir/translators/C.py index a730b1d8..007f8378 100644 --- a/miasm2/ir/translators/C.py +++ b/miasm2/ir/translators/C.py @@ -59,6 +59,10 @@ class TranslatorC(Translator): if expr.op == 'parity': return "parity(%s&0x%x)" % (cls.from_expr(expr.args[0]), size2mask(expr.args[0].size)) + elif expr.op in ['bsr', 'bsf']: + return "x86_%s(%s, 0x%x)" % (expr.op, + cls.from_expr(expr.args[0]), + expr.args[0].size) elif expr.op == '!': return "(~ %s)&0x%x" % (cls.from_expr(expr.args[0]), size2mask(expr.args[0].size)) @@ -102,10 +106,6 @@ class TranslatorC(Translator): cls.from_expr(expr.args[0]), cls.from_expr(expr.args[1]), size2mask(expr.args[0].size)) - elif expr.op in ['bsr', 'bsf']: - return 'my_%s(%s, %s)' % (expr.op, - cls.from_expr(expr.args[0]), - cls.from_expr(expr.args[1])) elif (expr.op.startswith('cpuid') or expr.op.startswith("fcom") or expr.op in ["fadd", "fsub", "fdiv", 'fmul', "fscale"]): diff --git a/miasm2/jitter/vm_mngr.c b/miasm2/jitter/vm_mngr.c index 188f0372..057c10be 100644 --- a/miasm2/jitter/vm_mngr.c +++ b/miasm2/jitter/vm_mngr.c @@ -915,26 +915,29 @@ int rcr_cf_op(unsigned int size, unsigned int a, unsigned int b, unsigned int cf { return rcl_cf_op(size, a, size+1-b, cf); } -unsigned int my_bsr(unsigned int a, unsigned int b) + +unsigned int x86_bsr(uint64_t src, unsigned int size) { int i; - for (i=31; i>=0; i--){ - if (b & (1<<i)) + for (i=size-1; i>=0; i--){ + if (src & (1<<i)) return i; } - return a; + fprintf(stderr, "sanity check error bsr\n"); + exit(0); } -unsigned int my_bsf(unsigned int a, unsigned int b) +unsigned int x86_bsf(uint64_t src, unsigned int size) { int i; - for (i=0; i<32; i++){ - if (b & (1<<i)) + for (i=0; i<size; i++){ + if (src & (1<<i)) return i; } - return a; + fprintf(stderr, "sanity check error bsf\n"); + exit(0); } diff --git a/miasm2/os_dep/win_api_x86_32.py b/miasm2/os_dep/win_api_x86_32.py index cac03905..cb107419 100644 --- a/miasm2/os_dep/win_api_x86_32.py +++ b/miasm2/os_dep/win_api_x86_32.py @@ -782,8 +782,8 @@ def kernel32_GetModuleFileName(jitter, funcname, set_str): for x in winobjs.runtime_dll.name2off.items()]) p = name_inv[args.hmodule] else: - log.warning('Unknown module 0x%x.' + \ - 'Set winobjs.hcurmodule and retry' % args.hmodule) + log.warning(('Unknown module 0x%x.' + \ + 'Set winobjs.hcurmodule and retry') % args.hmodule) p = None if p is None: diff --git a/test/analysis/depgraph.py b/test/analysis/depgraph.py new file mode 100644 index 00000000..9237d785 --- /dev/null +++ b/test/analysis/depgraph.py @@ -0,0 +1,602 @@ +from miasm2.expression.expression import ExprId, ExprInt32, ExprAff +from miasm2.core.asmbloc import asm_label +from miasm2.ir.analysis import ira +from miasm2.ir.ir import ir, irbloc +from miasm2.core.graph import DiGraph +from miasm2.analysis.depgraph import DependencyNode, DependencyGraph, DependencyDict, DependencyGraph_NoMemory +from pdb import pm + +a = ExprId("a") +b = ExprId("b") +c = ExprId("c") +d = ExprId("d") + +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") + +cst1 = ExprInt32(0x11) +cst2 = ExprInt32(0x12) +cst3 = ExprInt32(0x13) + +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(lbl, exprs): + lines = [None for i in xrange(len(exprs))] + irb = irbloc(lbl, exprs, lines) + return irb + + +class Regs(object): + regs_init = {a: a_init, b: b_init, c: c_init, d: d_init} + +class Arch(object): + regs = Regs() + + def getpc(self, attrib): + return pc + + def getsp(self, attrib): + return sp + +class IRATest(ir, ira): + + def __init__(self, symbol_pool=None): + arch = Arch() + ir.__init__(self, arch, 32, symbol_pool) + self.IRDst = pc + + def gen_graph(self): + return + +class GraphTest(DiGraph): + def __init__(self, ira): + self.ira = ira + super(GraphTest, self).__init__() + + def __eq__(self, graph): + if self._nodes != graph._nodes: + return False + if sorted(self._edges) != sorted(graph._edges): + return False + return True + + def gen_graph(self): + return + + def node2str(self, node): + if not node in self.ira.blocs: + return str(node) + else: + return str(self.ira.blocs[node]) + +class DepNodeTest(DiGraph): + def __init__(self, ira): + self.ira = ira + super(DepNodeTest, self).__init__() + + def __eq__(self, graph): + if self._nodes != graph._nodes: + return False + if sorted(self._edges) != sorted(graph._edges): + return False + return True + + def node2str(self, 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, i) for i 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 "[+] DependencyDict OK !" +print "[+] Structures OK !" + +# 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)] ]) +g1_irb2 = gen_irbloc(lbl2, [ [ExprAff(a, b)] ]) + +g1_ira.g.add_uniq_edge(g1_irb0.label, g1_irb1.label) +g1_ira.g.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_ira.g = GraphTest(g2_ira) + +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.g.add_uniq_edge(g2_irb0.label, g2_irb1.label) +g2_ira.g.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_ira.g = GraphTest(g3_ira) + +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.g.add_uniq_edge(g3_irb0.label, g3_irb1.label) +g3_ira.g.add_uniq_edge(g3_irb0.label, g3_irb2.label) +g3_ira.g.add_uniq_edge(g3_irb1.label, g3_irb3.label) +g3_ira.g.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_ira.g = GraphTest(g4_ira) + +g4_irb0 = gen_irbloc(lbl0, [ [ExprAff(c, cst1)] ]) +g4_irb1 = gen_irbloc(lbl1, [ [ExprAff(c, c+cst2)] ]) +g4_irb2 = gen_irbloc(lbl2, [ [ExprAff(a, b)] ]) + +g4_ira.g.add_uniq_edge(g4_irb0.label, g4_irb1.label) +g4_ira.g.add_uniq_edge(g4_irb1.label, g4_irb2.label) +g4_ira.g.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_ira.g = GraphTest(g5_ira) + +g5_irb0 = gen_irbloc(lbl0, [ [ExprAff(b, cst1)] ]) +g5_irb1 = gen_irbloc(lbl1, [ [ExprAff(b, b+cst2)] ]) +g5_irb2 = gen_irbloc(lbl2, [ [ExprAff(a, b)] ]) + +g5_ira.g.add_uniq_edge(g5_irb0.label, g5_irb1.label) +g5_ira.g.add_uniq_edge(g5_irb1.label, g5_irb2.label) +g5_ira.g.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_ira.g = GraphTest(g6_ira) + +g6_irb0 = gen_irbloc(lbl0, [ [ExprAff(b, cst1)] ]) +g6_irb1 = gen_irbloc(lbl1, [ [ExprAff(a, b)] ]) + +g6_ira.g.add_uniq_edge(g6_irb0.label, g6_irb1.label) +g6_ira.g.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_ira.g = GraphTest(g7_ira) + +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.g.add_uniq_edge(g7_irb0.label, g7_irb1.label) +g7_ira.g.add_uniq_edge(g7_irb1.label, g7_irb1.label) +g7_ira.g.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_ira.g = GraphTest(g8_ira) + +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.g.add_uniq_edge(g8_irb0.label, g8_irb1.label) +g8_ira.g.add_uniq_edge(g8_irb1.label, g8_irb1.label) +g8_ira.g.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_ira.g = GraphTest(g10_ira) + +g10_irb1 = gen_irbloc(lbl1, [ [ExprAff(b, b+cst2)] ]) +g10_irb2 = gen_irbloc(lbl2, [ [ExprAff(a, b)] ]) + +g10_ira.g.add_uniq_edge(g10_irb1.label, g10_irb2.label) +g10_ira.g.add_uniq_edge(g10_irb1.label, g10_irb1.label) + +g10_ira.blocs = dict([(irb.label, irb) for irb in [g10_irb1, g10_irb2]]) + + +# Test graph 1 + +g1_test1 = DepNodeTest(g1_ira) + +g1_test1_dn1 = DependencyNode(g1_irb2.label, a, len(g1_irb2.irs)) +g1_test1_dn2 = DependencyNode(g1_irb2.label, b, 0) +g1_test1_dn3 = DependencyNode(g1_irb1.label, c, 0) +g1_test1_dn4 = DependencyNode(g1_irb0.label, cst1, 0) + +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_input = (set([g1_test1_dn1]), set([g1_irb0.label])) +g1_output1 = {"graph": g1_test1, + "emul": {a: cst1}, + "unresolved": set(), + "has_loop": False} + +# Test graph 2 + +g2_test1 = DepNodeTest(g2_ira) + +g2_test1_dn1 = DependencyNode(g2_irb2.label, a, len(g2_irb2.irs)) +g2_test1_dn2 = DependencyNode(g2_irb2.label, b, 0) +g2_test1_dn3 = DependencyNode(g2_irb2.label, c, 0) +g2_test1_dn4 = DependencyNode(g2_irb1.label, cst2, 0) +g2_test1_dn5 = DependencyNode(g2_irb0.label, cst1, 0) + +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_input = (set([g2_test1_dn1]), set([g2_irb0.label])) +g2_output1 = {"graph": g2_test1, + "emul": {a: ExprInt32(int(cst1.arg) + int(cst2.arg))}, + "unresolved": set(), + "has_loop": False} + +# Test graph 3 + +g3_test1_0 = DepNodeTest(g3_ira) +g3_test1_1 = DepNodeTest(g3_ira) + +g3_test1_0_dn1 = DependencyNode(g3_irb3.label, a, len(g3_irb3.irs)) +g3_test1_0_dn2 = DependencyNode(g3_irb3.label, b, 0) +g3_test1_0_dn3 = DependencyNode(g3_irb3.label, c, 0) +g3_test1_0_dn4 = DependencyNode(g3_irb2.label, cst3, 0) +g3_test1_0_dn5 = DependencyNode(g3_irb0.label, cst1, 0) + +g3_test1_1_dn1 = DependencyNode(g3_irb3.label, a, len(g3_irb3.irs)) +g3_test1_1_dn2 = DependencyNode(g3_irb3.label, b, 0) +g3_test1_1_dn3 = DependencyNode(g3_irb3.label, c, 0) +g3_test1_1_dn4 = DependencyNode(g3_irb1.label, cst2, 0) +g3_test1_1_dn5 = DependencyNode(g3_irb0.label, cst1, 0) + +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_1_dn1) +g3_test1_1.add_uniq_edge(g3_test1_1_dn3, g3_test1_0_dn1) + +g3_input = (set([g3_test1_0_dn1]), set([g3_irb0.label])) + +g3_output1 = {"graph": g3_test1_0, + "emul": {a: ExprInt32(int(cst1.arg) + int(cst3.arg))}, + "unresolved": set(), + "has_loop": False} + +g3_output2 = {"graph": g3_test1_1, + "emul": {a: ExprInt32(int(cst1.arg) + int(cst2.arg))}, + "unresolved": set(), + "has_loop": False} + +# Test graph 4 + +g4_test1 = DepNodeTest(g4_ira) + +g4_test1_dn1 = DependencyNode(g4_irb2.label, a, len(g2_irb0.irs)) +g4_test1_dn2 = DependencyNode(g4_irb2.label, b, 0) +g4_test1_dn3 = DependencyNode(g4_irb0.label, b, 0) + +g4_test1.add_uniq_edge(g4_test1_dn2, g4_test1_dn1) + +g4_input = (set([g4_test1_dn1]), set([g4_irb0.label])) + +g4_output1 = {"graph": g4_test1, + "emul": {a: b_init}, + "unresolved": set([g4_test1_dn3]), + "has_loop": False} + +# Test graph 5 + +g5_test1 = DepNodeTest(g5_ira) + +g5_test1_dn1 = DependencyNode(g5_irb2.label, a, len(g5_irb2.irs)) +g5_test1_dn2 = DependencyNode(g5_irb2.label, b, 0) +g5_test1_dn3 = DependencyNode(g5_irb1.label, b, 0) +g5_test1_dn4 = DependencyNode(g5_irb0.label, cst1, 0) +g5_test1_dn5 = DependencyNode(g5_irb1.label, cst2, 0) + +g5_test1.add_uniq_edge(g5_test1_dn4, g5_test1_dn3) +g5_test1.add_uniq_edge(g5_test1_dn3, g5_test1_dn2) +g5_test1.add_uniq_edge(g5_test1_dn5, g5_test1_dn2) +g5_test1.add_uniq_edge(g5_test1_dn2, g5_test1_dn1) + +g5_input = (set([g5_test1_dn1]), set([g5_irb0.label])) + +g5_output1 = {"graph": g5_test1, + "emul": {}, + "unresolved": set(), + "has_loop": True} + +# Test graph 6 + +g6_test1_0 = DepNodeTest(g6_ira) + +g6_test1_0_dn1 = DependencyNode(g6_irb1.label, a, len(g6_irb1.irs)) +g6_test1_0_dn2 = DependencyNode(g6_irb1.label, b, 0) +g6_test1_0_dn3 = DependencyNode(g6_irb0.label, cst1, 0) + + +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_input = (set([g6_test1_0_dn1]), set([g6_irb0.label])) + +g6_output1 = {"graph": g6_test1_0, + "emul": {a: cst1}, + "unresolved": set(), + "has_loop": True} + +# Test graph 7 + +g7_test1_0 = DepNodeTest(g7_ira) + +g7_test1_0_dn1 = DependencyNode(g7_irb2.label, a, len(g7_irb2.irs)) +g7_test1_0_dn2 = DependencyNode(g7_irb1.label, b, 1) +g7_test1_0_dn3 = DependencyNode(g7_irb1.label, c, 0) +g7_test1_0_dn4 = DependencyNode(g7_irb0.label, cst1, 0) + + +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_input = (set([g7_test1_0_dn1]), set([g7_irb0.label])) + +g7_output1 = {"graph": g7_test1_0, + "emul": {a: cst1}, + "unresolved": set(), + "has_loop": True} + +# Test graph 8 + +g8_test1_0 = DepNodeTest(g8_ira) +g8_test1_1 = DepNodeTest(g8_ira) + +g8_test1_0_dn1 = DependencyNode(g8_irb2.label, a, len(g8_irb2.irs)) +g8_test1_0_dn2 = DependencyNode(g8_irb2.label, b, 0) +g8_test1_0_dn3 = DependencyNode(g8_irb1.label, c, 0) +g8_test1_0_dn4 = DependencyNode(g8_irb0.label, cst1, 0) + +g8_test1_1_dn1 = DependencyNode(g8_irb2.label, a, len(g8_irb2.irs)) +g8_test1_1_dn2 = DependencyNode(g8_irb2.label, b, 0) +g8_test1_1_dn3 = DependencyNode(g8_irb1.label, c, 0) +g8_test1_1_dn4 = DependencyNode(g8_irb1.label, d, 1) + +g8_test1_1_dn5 = DependencyNode(g8_irb0.label, d, 0) + + +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_input = (set([g8_test1_0_dn1]), set([g3_irb0.label])) + +g8_output1 = {"graph": g8_test1_0, + "emul": {a: cst1}, + "unresolved": set(), + "has_loop": False} + +g8_output2 = {"graph": g8_test1_1, + "emul": {a: d_init}, + "unresolved": set([g8_test1_1_dn5]), + "has_loop": True} + + +# Test 9: Multi elements + +g9_test1_0 = DepNodeTest(g8_ira) +g9_test1_1 = DepNodeTest(g8_ira) + +g9_test1_0_dn1 = DependencyNode(g8_irb2.label, a, len(g8_irb2.irs)) +g9_test1_0_dn2 = DependencyNode(g8_irb2.label, b, 0) +g9_test1_0_dn3 = DependencyNode(g8_irb1.label, c, 0) +g9_test1_0_dn4 = DependencyNode(g8_irb0.label, cst1, 0) +g9_test1_0_dn5 = DependencyNode(g8_irb2.label, c, len(g8_irb2.irs)) +g9_test1_0_dn6 = DependencyNode(g8_irb1.label, d, 1) + +g9_test1_1_dn1 = DependencyNode(g8_irb2.label, a, len(g8_irb2.irs)) +g9_test1_1_dn2 = DependencyNode(g8_irb2.label, b, 0) +g9_test1_1_dn3 = DependencyNode(g8_irb1.label, c, 0) +g9_test1_1_dn4 = DependencyNode(g8_irb1.label, d, 1) +g9_test1_1_dn5 = DependencyNode(g8_irb2.label, c, len(g8_irb2.irs)) + + +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_dn4, 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) + +g9_input = (set([g9_test1_0_dn1, g9_test1_0_dn5]), set([g8_irb0.label])) + +g9_output1 = {"graph": g9_test1_0, + "emul": {a: cst1, + c: d_init}, + "unresolved": set([g8_test1_1_dn5]), + "has_loop": False} + +g9_output2 = {"graph": g9_test1_1, + "emul": {a: d_init, + c: d_init}, + "unresolved": set([g8_test1_1_dn5]), + "has_loop": True} + + +# Test 10: loop at beginning + +g10_test1 = DepNodeTest(g10_ira) + +g10_test1_dn1 = DependencyNode(g10_irb2.label, a, len(g10_irb2.irs)) +g10_test1_dn2 = DependencyNode(g10_irb2.label, b, 0) +g10_test1_dn3 = DependencyNode(g10_irb1.label, b, 0) +g10_test1_dn4 = DependencyNode(g10_irb1.label, cst2, 0) + +g10_test1.add_uniq_edge(g10_test1_dn3, g10_test1_dn2) +g10_test1.add_uniq_edge(g10_test1_dn4, g10_test1_dn2) +g10_test1.add_uniq_edge(g10_test1_dn2, g10_test1_dn1) + +g10_input = (set([g10_test1_dn1]), set([g10_irb1.label])) + +g10_output1 = {"graph": g10_test1, + "emul": {}, + "unresolved": set([g10_test1_dn3]), + "has_loop": True} + + +# Launch tests +for i, test in enumerate([(g1_ira, g1_input, [g1_output1]), + (g2_ira, g2_input, [g2_output1]), + (g3_ira, g3_input, [g3_output1, g3_output2]), + (g4_ira, g4_input, [g4_output1]), + (g5_ira, g5_input, [g5_output1]), + (g6_ira, g6_input, [g6_output1]), + (g7_ira, g7_input, [g7_output1]), + (g8_ira, g8_input, [g8_output1, g8_output2]), + (g8_ira, g9_input, [g9_output1, g9_output2]), + (g10_ira, g10_input, [g10_output1]), + ]): + # Extract test elements + print "[+] Test", i+1 + g_ira, (depnodes, heads), g_test_list = test + open("graph_%02d.dot" % (i+1), "w").write(g_ira.g.dot()) + # Test classes + for g_dep in [DependencyGraph(g_ira), + DependencyGraph_NoMemory(g_ira)]: + print " - Class %s" % g_dep.__class__.__name__ + + ## Test public APIs + for api_i, g_list in enumerate([g_dep.get_fromDepNodes(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_fromDepNodes" if api_i == 0 else "get") + + ### Expand result iterator + g_list = list(g_list) + ### Dump outputs graphs for debug means + for j, result in enumerate(g_list): + open("graph_test_%02d_%02d.dot" % (i+1, j), "w").write(result.graph.dot()) + + ### The number of results should be the same + print " - - - number of results" + assert(len(g_list) == len(g_test_list)) + + ### Match the right result (unordered) + for i, result in enumerate(g_list): + print " - - - result %d" % i + found = False + for expected in g_test_list: + if expected["graph"].__eq__(result.graph): + found = True + break + assert(found) + + #### @expected is the corresponding result, test for properties + print " - - - - emul" + if not expected["has_loop"]: + assert(expected["emul"] == result.emul()) + for element in ["unresolved"]: # TODO: has_loop + print " - - - - %s" % element + assert(expected[element] == getattr(result, element)) diff --git a/test/arch/x86/arch.py b/test/arch/x86/arch.py index 5a87012f..16a0794a 100644 --- a/test/arch/x86/arch.py +++ b/test/arch/x86/arch.py @@ -1111,7 +1111,7 @@ reg_tests = [ (m32, "00000000 POPAD", "61"), - (m16, "00000000 POPF", + (m16, "00000000 POPFW", "9d"), (m32, "00000000 POPFD", "9d"), @@ -1179,7 +1179,7 @@ reg_tests = [ (m32, "00000000 PUSHAD", "60"), - (m16, "00000000 PUSHF", + (m16, "00000000 PUSHFW", "9c"), (m32, "00000000 PUSHFD", "9c"), diff --git a/test/ir/ir2C.py b/test/ir/ir2C.py index 1089bba4..11b9b10e 100644 --- a/test/ir/ir2C.py +++ b/test/ir/ir2C.py @@ -37,7 +37,7 @@ class TestIrIr2C(unittest.TestCase): self.translationTest( ExprOp('-', *args[:2]), r'(((0x0&0xffffffff) - (0x1&0xffffffff))&0xffffffff)') self.translationTest( - ExprOp('bsr', *args[:2]), r'my_bsr(0x0, 0x1)') + ExprOp('bsr', *args[:1]), r'x86_bsr(0x0, 0x20)') self.translationTest( ExprOp('cpuid0', *args[:2]), r'cpuid0(0x0, 0x1)') self.translationTest( diff --git a/test/samples/x86_32/bsr_bsf.S b/test/samples/x86_32/bsr_bsf.S new file mode 100644 index 00000000..0f915ed1 --- /dev/null +++ b/test/samples/x86_32/bsr_bsf.S @@ -0,0 +1,42 @@ +main: + ;; BSF + ;; standard case + MOV ECX, 0xF0000004 + MOV EAX, 0x0 + BSF EAX, ECX + JZ bad + CMP EAX, 2 + JNZ bad + + + ;; case undef + MOV ECX, 0x0 + MOV EAX, 0x1337beef + BSF EAX, ECX + JNZ bad + CMP EAX, 0x1337beef + JNZ bad + + ;; BSR + ;; standard case + MOV ECX, 0x4000000F + MOV EAX, 0x0 + BSR EAX, ECX + JZ bad + CMP EAX, 30 + JNZ bad + + + ;; case undef + MOV ECX, 0x0 + MOV EAX, 0x1337beef + BSR EAX, ECX + JNZ bad + CMP EAX, 0x1337beef + JNZ bad + + RET + +bad: + INT 0x3 + RET diff --git a/test/test_all.py b/test/test_all.py index a2fd6df3..0ecc677f 100644 --- a/test/test_all.py +++ b/test/test_all.py @@ -68,7 +68,9 @@ class SemanticTestAsm(RegressionTest): class SemanticTestExec(RegressionTest): """Execute a binary file""" - launcher_dct = {("PE", "x86_64"): "sandbox_pe_x86_64.py"} + launcher_dct = {("PE", "x86_64"): "sandbox_pe_x86_64.py", + ("PE", "x86_32"): "sandbox_pe_x86_32.py", + } launcher_base = os.path.join("..", "example", "jitter") def __init__(self, arch, container, address, *args, **kwargs): @@ -86,9 +88,13 @@ class SemanticTestExec(RegressionTest): test_x86_64_mul_div = SemanticTestAsm("x86_64", "PE", ["mul_div"]) +test_x86_32_bsr_bsf = SemanticTestAsm("x86_32", "PE", ["bsr_bsf"]) testset += test_x86_64_mul_div +testset += test_x86_32_bsr_bsf testset += SemanticTestExec("x86_64", "PE", 0x401000, ["mul_div"], depends=[test_x86_64_mul_div]) +testset += SemanticTestExec("x86_32", "PE", 0x401000, ["bsr_bsf"], + depends=[test_x86_32_bsr_bsf]) ## Core for script in ["interval.py", @@ -115,6 +121,25 @@ for script in ["win_api_x86_32.py", ]: testset += RegressionTest([script], base_dir="os_dep") +## Analysis +testset += RegressionTest(["depgraph.py"], base_dir="analysis", + products=["graph_test_01_00.dot", + "graph_test_02_00.dot", + "graph_test_02_01.dot", + "graph_test_03_00.dot", + "graph_test_03_01.dot", + "graph_test_04_00.dot", + "graph_test_05_00.dot", + "graph_test_06_00.dot", + "graph_test_07_00.dot", + "graph_test_08_00.dot", + "graph_test_08_01.dot", + "graph_test_09_00.dot", + "graph_test_09_01.dot", + "graph_test_10_00.dot", + ] + ["graph_%02d.dot" % test_nb + for test_nb in xrange(1, 11)]) + # Examples class Example(Test): """Examples specificities: |