diff options
| -rw-r--r-- | miasm2/core/graph.py | 35 |
1 files changed, 35 insertions, 0 deletions
diff --git a/miasm2/core/graph.py b/miasm2/core/graph.py index f61d1e67..e385b044 100644 --- a/miasm2/core/graph.py +++ b/miasm2/core/graph.py @@ -143,6 +143,14 @@ class DiGraph(object): return [x for x in self.heads_iter()] def find_path(self, src, dst, cycles_count=0, done=None): + """ + Searches for paths from @src to @dst + @src: loc_key of basic block from which it should start + @dst: loc_key of basic block where it should stop + @cycles_count: maximum number of times a basic block can be processed + @done: dictionary of already processed loc_keys, it's value is number of times it was processed + @out: list of paths from @src to @dst + """ if done is None: done = {} if dst in done and done[dst] > cycles_count: @@ -157,6 +165,33 @@ class DiGraph(object): if path and path[0] == src: out.append(path + [dst]) return out + + def find_path_from_src(self, src, dst, cycles_count=0, done=None): + """ + This function does the same as function find_path. + But it searches the paths from src to dst, not vice versa like find_path. + This approach might be more efficient in some cases. + @src: loc_key of basic block from which it should start + @dst: loc_key of basic block where it should stop + @cycles_count: maximum number of times a basic block can be processed + @done: dictionary of already processed loc_keys, it's value is number of times it was processed + @out: list of paths from @src to @dst + """ + + if done is None: + done = {} + if src == dst: + return [[src]] + if src in done and done[src] > cycles_count: + return [[]] + out = [] + for node in self.successors(src): + done_n = dict(done) + done_n[src] = done_n.get(src, 0) + 1 + for path in self.find_path_from_src(node, dst, cycles_count, done_n): + if path and path[len(path)-1] == dst: + out.append([src] + path) + return out def nodeid(self, node): """ |