diff options
| -rw-r--r-- | miasm2/analysis/depgraph.py | 6 | ||||
| -rw-r--r-- | miasm2/core/graph.py | 28 | ||||
| -rw-r--r-- | test/analysis/dg_test_06_expected.json | 2 | ||||
| -rw-r--r-- | test/analysis/dg_test_06_implicit_expected.json | 2 |
4 files changed, 33 insertions, 5 deletions
diff --git a/miasm2/analysis/depgraph.py b/miasm2/analysis/depgraph.py index aec159aa..b574e421 100644 --- a/miasm2/analysis/depgraph.py +++ b/miasm2/analysis/depgraph.py @@ -252,10 +252,10 @@ class DependencyResult(DependencyState): @property def has_loop(self): - """True if current dictionary has a loop""" + """True iff there is at least one data dependencies cycle (regarding + the associated depgraph)""" if self._has_loop is None: - self._has_loop = (len(self.relevant_labels) != - len(set(self.relevant_labels))) + self._has_loop = self.graph.has_loop() return self._has_loop def irblock_slice(self, irb): diff --git a/miasm2/core/graph.py b/miasm2/core/graph.py index c98bf8a9..d97ca8be 100644 --- a/miasm2/core/graph.py +++ b/miasm2/core/graph.py @@ -478,6 +478,34 @@ class DiGraph(object): """Performs a depth first search on the reversed graph from @head""" return self._walk_generic_first(head, -1, self.predecessors_iter) + def has_loop(self): + """Return True if the graph contains at least a cycle""" + todo = list(self.nodes()) + # tested nodes + done = set() + # current DFS nodes + current = set() + while todo: + node = todo.pop() + if node in done: + continue + + if node in current: + # DFS branch end + for succ in self.successors_iter(node): + if succ in current: + return True + # A node cannot be in current AND in done + current.remove(node) + done.add(node) + else: + # Launch DFS from node + todo.append(node) + current.add(node) + todo += self.successors(node) + + return False + def compute_natural_loops(self, head): """ Computes all natural loops in the graph. diff --git a/test/analysis/dg_test_06_expected.json b/test/analysis/dg_test_06_expected.json index 7d823131..c181cd2d 100644 --- a/test/analysis/dg_test_06_expected.json +++ b/test/analysis/dg_test_06_expected.json @@ -1 +1 @@ -[{"EAX": "0x1", "has_loop": false}, {"EAX": "0x2", "has_loop": true}] +[{"EAX": "0x1", "has_loop": false}, {"EAX": "0x2", "has_loop": false}] diff --git a/test/analysis/dg_test_06_implicit_expected.json b/test/analysis/dg_test_06_implicit_expected.json index 050915c1..bda75296 100644 --- a/test/analysis/dg_test_06_implicit_expected.json +++ b/test/analysis/dg_test_06_implicit_expected.json @@ -1 +1 @@ -[{"has_loop": false, "EAX": "0x1", "satisfiability": true, "constraints": {"EAX_init": "0xffffffff"}}, {"has_loop": true, "EAX": "0x2", "satisfiability": false, "constraints": {}}] +[{"has_loop": false, "EAX": "0x1", "satisfiability": true, "constraints": {"EAX_init": "0xffffffff"}}, {"has_loop": false, "EAX": "0x2", "satisfiability": false, "constraints": {}}] |