diff options
Diffstat (limited to 'miasm2/core')
| -rw-r--r-- | miasm2/core/asmbloc.py | 109 | ||||
| -rw-r--r-- | miasm2/core/graph.py | 149 | ||||
| -rw-r--r-- | miasm2/core/sembuilder.py | 4 | ||||
| -rw-r--r-- | miasm2/core/utils.py | 6 |
4 files changed, 159 insertions, 109 deletions
diff --git a/miasm2/core/asmbloc.py b/miasm2/core/asmbloc.py index a4427206..38d3d17a 100644 --- a/miasm2/core/asmbloc.py +++ b/miasm2/core/asmbloc.py @@ -3,7 +3,6 @@ import logging import inspect -import re from collections import namedtuple import miasm2.expression.expression as m2_expr @@ -254,6 +253,7 @@ class asm_bloc(object): class asm_block_bad(asm_bloc): + """Stand for a *bad* ASM block (malformed, unreachable, not disassembled, ...)""" @@ -261,7 +261,7 @@ class asm_block_bad(asm_bloc): 0: "Unable to disassemble", 1: "Null starting block", 2: "Address forbidden by dont_dis", - } + } def __init__(self, label=None, alignment=1, errno=-1, *args, **kwargs): """Instanciate an asm_block_bad. @@ -577,6 +577,7 @@ def dis_bloc_all(mnemo, pool_bin, offset, job_done, symbol_pool, dont_dis=[], class AsmCFG(DiGraph): + """Directed graph standing for a ASM Control Flow Graph with: - nodes: asm_bloc - edges: constraints between blocks, synchronized with asm_bloc's "bto" @@ -640,7 +641,7 @@ class AsmCFG(DiGraph): def add_uniq_edge(self, src, dst, constraint): """Add an edge from @src to @dst if it doesn't already exist""" if (src not in self._nodes_succ or - dst not in self._nodes_succ[src]): + dst not in self._nodes_succ[src]): self.add_edge(src, dst, constraint) def del_edge(self, src, dst): @@ -704,81 +705,54 @@ class AsmCFG(DiGraph): # Use "_uniq_" beacause the edge can already exist due to add_node self.add_uniq_edge(*edge, constraint=graph.edges2constraint[edge]) - def dot(self, label=False, lines=True): - """Render dot graph with HTML - @label: (optional) if set, add the corresponding label in each block - @lines: (optional) if set, includes assembly lines in the output - """ - - 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 block in self.nodes(): - out_block = '%s [\n' % block.label.name - out_block += "%s " % block_attr - if isinstance(block, asm_block_bad): - out_block += 'style=filled fillcolor="red" ' - out_block += 'label =<<table border="0" cellborder="0" cellpadding="3">' - - block_label = '<tr><td %s>%s</td></tr>' % ( - label_attr, block.label.name) - block_html_lines = [] - - if lines: - if isinstance(block, asm_block_bad): - block_html_lines.append(block.ERROR_TYPES.get(block._errno, - block._errno)) - - for line in block.lines: - if label: - out_render = "%.8X</td><td %s> " % (line.offset, - td_attr) - else: - out_render = "" - out_render += escape_chars.sub(fix_chars, str(line)) - block_html_lines.append(out_render) - - block_html_lines = ('<tr><td %s>' % td_attr + - ('</td></tr><tr><td %s>' % td_attr).join(block_html_lines) + - '</td></tr>') - out_block += "%s " % block_label - out_block += block_html_lines + "</table>> ];" - out_blocks.append(out_block) + def node2lines(self, node): + yield self.DotCellDescription(text=str(node.label.name), + attr={'align': 'center', + 'colspan': 2, + 'bgcolor': 'grey'}) + + if isinstance(node, asm_block_bad): + yield [self.DotCellDescription( + text=node.ERROR_TYPES.get(node._errno, + node._errno), + attr={})] + raise StopIteration + for line in node.lines: + if self._dot_offset: + yield [self.DotCellDescription(text="%.8X" % line.offset, + attr={}), + self.DotCellDescription(text=str(line), attr={})] + else: + yield self.DotCellDescription(text=str(line), attr={}) - out += out_blocks + def node_attr(self, node): + if isinstance(node, asm_block_bad): + return {'style': 'filled', 'fillcolor': 'red'} + return {} - # Generate links - for src, dst in self.edges(): - exp_label = dst.label - cst = self.edges2constraint.get((src, dst), None) + def edge_attr(self, src, dst): + cst = self.edges2constraint.get((src, dst), None) + edge_color = "blue" - edge_color = "black" + if len(self.successors(src)) > 1: if cst == asm_constraint.c_next: edge_color = "red" - elif cst == asm_constraint.c_to: + else: edge_color = "limegreen" - # special case - if len(src.bto) == 1: - edge_color = "blue" - out.append('%s -> %s' % (src.label.name, dst.label.name) + \ - '[' + edge_attr % (cst, edge_color) + '];') + return {"color": edge_color} - out.append("}") - return '\n'.join(out) + def dot(self, offset=False): + """ + @offset: (optional) if set, add the corresponding offsets in each node + """ + self._dot_offset = offset + return super(AsmCFG, self).dot() # Helpers @property def pendings(self): - """Dictionnary of label -> set(AsmCFGPending instance) indicating + """Dictionary of label -> set(AsmCFGPending instance) indicating which label are missing in the current instance. A label is missing if a block which is already in nodes has constraints with him (thanks to its .bto) and the corresponding block is not yet in @@ -935,7 +909,8 @@ class AsmCFG(DiGraph): new block destinations @kwargs: (optional) named arguments to pass to dis_block_callback """ - # Get all possible destinations not yet resolved, with a resolved offset + # Get all possible destinations not yet resolved, with a resolved + # offset block_dst = [label.offset for label in self.pendings if label.offset is not None] diff --git a/miasm2/core/graph.py b/miasm2/core/graph.py index 310adc2e..f544757d 100644 --- a/miasm2/core/graph.py +++ b/miasm2/core/graph.py @@ -1,9 +1,15 @@ from collections import defaultdict, namedtuple +import re class DiGraph(object): + """Implementation of directed graph""" + # Stand for a cell in a dot node rendering + DotCellDescription = namedtuple("DotCellDescription", + ["text", "attr"]) + def __init__(self): self._nodes = set() self._edges = [] @@ -86,7 +92,7 @@ class DiGraph(object): def add_uniq_edge(self, src, dst): """Add an edge from @src to @dst if it doesn't already exist""" if (src not in self._nodes_succ or - dst not in self._nodes_succ[src]): + dst not in self._nodes_succ[src]): self.add_edge(src, dst) def del_edge(self, src, dst): @@ -144,35 +150,100 @@ class DiGraph(object): out.append(path + [dst]) return out + def nodeid(self, node): + """ + Returns uniq id for a @node + @node: a node of the graph + """ + return hash(node) & 0xFFFFFFFFFFFFFFFF + + def node2lines(self, node): + """ + Returns an iterator on cells of the dot @node. + A DotCellDescription or a list of DotCellDescription are accepted + @node: a node of the graph + """ + yield self.DotCellDescription(text=str(node), attr={}) + + def node_attr(self, node): + """ + Returns a dictionary of the @node's attributes + @node: a node of the graph + """ + return {} + + def edge_attr(self, src, dst): + """ + Return a dictionary of attributes for the edge between @src and @dst + @src: the source node of the edge + @dst: the destination node of the edge + """ + return {} + @staticmethod - def node2str(node): - return str(node) + def _fix_chars(token): + return "&#%04d;" % ord(token.group()) @staticmethod - def edge2str(src, dst): - return "" + def _attr2str(default_attr, attr): + return ' '.join('%s="%s"' % (name, value) + for name, value in + dict(default_attr, + **attr).iteritems()) def dot(self): - out = """ -digraph asm_graph { -graph [ -splines=polyline, -]; -node [ -fontsize = "16", -shape = "box" -]; -""" + """Render dot graph with HTML""" + + 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'} + nodes_attr = {'shape': 'Mrecord', + 'fontname': 'Courier New'} + + out = ["digraph asm_graph {"] + + # Generate basic nodes + out_nodes = [] for node in self.nodes(): - out += '%s [label="%s"];\n' % ( - hash(node) & 0xFFFFFFFFFFFFFFFF, self.node2str(node)) + node_id = self.nodeid(node) + out_node = '%s [\n' % node_id + out_node += self._attr2str(nodes_attr, self.node_attr(node)) + out_node += 'label =<<table border="0" cellborder="0" cellpadding="3">' + + node_html_lines = [] + + for lineDesc in self.node2lines(node): + out_render = "" + if isinstance(lineDesc, self.DotCellDescription): + lineDesc = [lineDesc] + for col in lineDesc: + out_render += "<td %s>%s</td>" % ( + self._attr2str(td_attr, col.attr), + escape_chars.sub(self._fix_chars, str(col.text))) + node_html_lines.append(out_render) + node_html_lines = ('<tr>' + + ('</tr><tr>').join(node_html_lines) + + '</tr>') + + out_node += node_html_lines + "</table>> ];" + out_nodes.append(out_node) + + out += out_nodes + + # Generate links for src, dst in self.edges(): - out += '%s -> %s [label="%s"]\n' % (hash(src) & 0xFFFFFFFFFFFFFFFF, - hash(dst) & 0xFFFFFFFFFFFFFFFF, - self.edge2str(src, dst)) - out += "}" - return out + attrs = self.edge_attr(src, dst) + + attrs = ' '.join('%s="%s"' % (name, value) + for name, value in attrs.iteritems()) + + out.append('%s -> %s' % (self.nodeid(src), self.nodeid(dst)) + + '[' + attrs + '];') + + out.append("}") + return '\n'.join(out) @staticmethod def _reachable_nodes(head, next_cb): @@ -270,7 +341,7 @@ shape = "box" The function doesn't return the self reference in dominators. @node: The start node - @gen_dominators: The dictionnary containing at least node's + @gen_dominators: The dictionary containing at least node's dominators/post_dominators @succ_cb: return predecessors/succesors of a node @@ -316,7 +387,7 @@ shape = "box" """Return an iterator of the ordered list of @node's dominators The function doesn't return the self reference in dominators. @node: The start node - @dominators: The dictionnary containing at least node's dominators + @dominators: The dictionary containing at least node's dominators """ return self._walk_generic_dominator(node, dominators, @@ -326,7 +397,7 @@ shape = "box" """Return an iterator of the ordered list of @node's postdominators The function doesn't return the self reference in postdominators. @node: The start node - @postdominators: The dictionnary containing at least node's + @postdominators: The dictionary containing at least node's postdominators """ @@ -541,6 +612,7 @@ shape = "box" class DiGraphSimplifier(object): + """Wrapper on graph simplification passes. Instance handle passes lists. @@ -575,6 +647,7 @@ class DiGraphSimplifier(object): class MatchGraphJoker(object): + """MatchGraphJoker are joker nodes of MatchGraph, that is to say nodes which stand for any node. Restrictions can be added to jokers. @@ -649,6 +722,7 @@ class MatchGraphJoker(object): class MatchGraph(DiGraph): + """MatchGraph intends to be the counterpart of MatchExpr, but for DiGraph This class provides API to match a given DiGraph pattern, with addidionnal @@ -701,7 +775,7 @@ class MatchGraph(DiGraph): @candidate: @graph's node @expected: MatchGraphJoker instance @graph: DiGraph instance - @partial_sol: (optional) dictionnary of MatchGraphJoker -> @graph's node + @partial_sol: (optional) dictionary of MatchGraphJoker -> @graph's node standing for a partial solution """ # Avoid having 2 different joker for the same node @@ -713,8 +787,8 @@ class MatchGraph(DiGraph): return False # Check arity - ## If filter_in/out, then arity must be the same - ## Otherwise, arity of the candidate must be at least equal + # If filter_in/out, then arity must be the same + # Otherwise, arity of the candidate must be at least equal if ((expected.restrict_in == True and len(self.predecessors(expected)) != len(graph.predecessors(candidate))) or (expected.restrict_in == False and @@ -731,12 +805,12 @@ class MatchGraph(DiGraph): return True for pred in self.predecessors(expected): if (pred in partial_sol and - partial_sol[pred] not in graph.predecessors(candidate)): + partial_sol[pred] not in graph.predecessors(candidate)): return False for succ in self.successors(expected): if (succ in partial_sol and - partial_sol[succ] not in graph.successors(candidate)): + partial_sol[succ] not in graph.successors(candidate)): return False # All checks OK @@ -750,11 +824,11 @@ class MatchGraph(DiGraph): """ real_node = partial_sol[node] for candidate in propagator(self, node): - ## Edge already in the partial solution, skip it + # Edge already in the partial solution, skip it if candidate in partial_sol: continue - ## Check candidate + # Check candidate for candidate_real in propagator(graph, real_node): if self._check_node(candidate_real, candidate, graph, partial_sol): @@ -775,15 +849,15 @@ class MatchGraph(DiGraph): def match(self, graph): """Naive subgraph matching between graph and self. - Iterator on matching solution, as dictionnary MatchGraphJoker -> @graph + Iterator on matching solution, as dictionary MatchGraphJoker -> @graph @graph: DiGraph instance In order to obtained correct and complete results, @graph must be connected. """ # Partial solution: nodes corrects, edges between these nodes corrects - # A partial solution is a dictionnary MatchGraphJoker -> @graph's node - todo = list() # Dictionnaries containing partial solution - done = list() # Aleady computed partial solutions + # A partial solution is a dictionary MatchGraphJoker -> @graph's node + todo = list() # Dictionnaries containing partial solution + done = list() # Aleady computed partial solutions # Elect first candidates to_match = next(iter(self._nodes)) @@ -799,7 +873,8 @@ class MatchGraph(DiGraph): # -> using last entry of todo first performs a "depth first" # approach on solutions # -> the algorithm may converge faster to a solution, a desired - # behavior while doing graph simplification (stopping after one sol) + # behavior while doing graph simplification (stopping after one + # sol) partial_sol = todo.pop() # Avoid infinite loop and recurrent work diff --git a/miasm2/core/sembuilder.py b/miasm2/core/sembuilder.py index 83981919..ce327ce1 100644 --- a/miasm2/core/sembuilder.py +++ b/miasm2/core/sembuilder.py @@ -131,7 +131,7 @@ class SemBuilder(object): def __init__(self, ctx): """Create a SemBuilder - @ctx: context dictionnary used during parsing + @ctx: context dictionary used during parsing """ # Init self.transformer = MiasmTransformer() @@ -144,7 +144,7 @@ class SemBuilder(object): @property def functions(self): - """Return a dictionnary name -> func of parsed functions""" + """Return a dictionary name -> func of parsed functions""" return self._functions.copy() @staticmethod diff --git a/miasm2/core/utils.py b/miasm2/core/utils.py index 30aff7d2..70520c1b 100644 --- a/miasm2/core/utils.py +++ b/miasm2/core/utils.py @@ -53,7 +53,7 @@ def whoami(): class BoundedDict(UserDict.DictMixin): - """Limited in size dictionnary. + """Limited in size dictionary. To reduce combinatory cost, once an upper limit @max_size is reached, @max_size - @min_size elements are suppressed. @@ -65,7 +65,7 @@ class BoundedDict(UserDict.DictMixin): def __init__(self, max_size, min_size=None, initialdata=None, delete_cb=None): """Create a BoundedDict - @max_size: maximum size of the dictionnary + @max_size: maximum size of the dictionary @min_size: (optional) number of most used element to keep when resizing @initialdata: (optional) dict instance with initial data @delete_cb: (optional) callback called when an element is removed @@ -121,7 +121,7 @@ class BoundedDict(UserDict.DictMixin): @property def data(self): - "Return the current instance as a dictionnary" + "Return the current instance as a dictionary" return self._data def __getitem__(self, key): |