diff options
| -rw-r--r-- | docs/GRAPH_VIEW.md | 22 | ||||
| -rw-r--r-- | idatui/graph_triskel.py | 131 | ||||
| -rw-r--r-- | tests/test_graph.py | 30 |
3 files changed, 125 insertions, 58 deletions
diff --git a/docs/GRAPH_VIEW.md b/docs/GRAPH_VIEW.md index d4f0180..b656179 100644 --- a/docs/GRAPH_VIEW.md +++ b/docs/GRAPH_VIEW.md @@ -98,12 +98,22 @@ ports already land spread along the box border, and — because our fork made th spacing settable — **we hand it cell counts rather than pixels**, so nothing is ever rounded and two edge lanes can never land on the same row. -What it does not do is trust the library with degenerate input, all of which is -handled before the call: self-loops (drawn as `↺`, and they make triskel throw), -disconnected components (laid out separately and stacked; IDA flowcharts do have -unreachable blocks), and the one edge in the corpus that triskel routes *through* -a block, which is detoured and then re-verified — if the detour fails the whole -layout falls back to native rather than draw an edge through the disassembly. +What it does not do is trust the library with degenerate input. Triskel's graph +root is **whichever node was created first**, and every one of its analyses walks +out from there, so anything the root cannot reach is undefined behaviour — it +throws `EMPTY BL` from its SESE bracket lists, or, when the entry block has no +successors at all, segfaults. That is not survivable: a crash in a C extension +takes the TUI with it, with no chance to fall back. So the entry is created +first, orphan blocks are attached to it with **phantom edges** that steer the +layout but are never drawn, and reachability is *asserted in python* before +crossing into C++. + +The rest is handled before the call too: self-loops (drawn as `↺`; they make +triskel throw), and edges routed through a block, which are detoured and +re-verified. Whatever is left over falls back to native rather than reach the +screen wrong — currently 8 layouts in 1200 (`ls`, three zoom levels each), all +of them triskel leaving two boxes a few columns into each other, which in a +terminal means one block's disassembly overwriting another's. ## Layout (`idatui/graph.py`, the native engine) diff --git a/idatui/graph_triskel.py b/idatui/graph_triskel.py index 1741f17..479c39b 100644 --- a/idatui/graph_triskel.py +++ b/idatui/graph_triskel.py @@ -39,9 +39,6 @@ HGAP = 3 VGAP = 1 LANE = 1 -#: Columns between two weakly-connected components laid out side by side. -COMPONENT_GAP = 4 - _mod: object | None = None _tried = False @@ -78,35 +75,55 @@ def available() -> bool: return module() is not None -def _components(g: G._Graph) -> list[list[int]]: - """Weakly-connected components, entry's component first. +def _reachable(succ: dict[int, list[int]], root: int) -> set[int]: + seen = {root} + stack = [root] + while stack: + for j in succ.get(stack.pop(), ()): + if j not in seen: + seen.add(j) + stack.append(j) + return seen + + +def _phantom_edges(g: G._Graph, root: int) -> list[tuple[int, int]]: + """Extra root->node edges that make every node reachable from ``root``. + + **This is a hard precondition, not a nicety.** Triskel's root is whichever + node was created first, and every analysis walks out from it; hand it a node + the root cannot reach and it either throws ``EMPTY BL`` from the SESE + bracket lists or -- with an entry block that has no successors at all -- + dereferences its way straight off the end and SEGFAULTS. A segfault cannot + be caught and fallen back from; it takes the TUI with it. + + Real CFGs hit this in two ways, both routine: IDA flowcharts contain blocks + unreachable from the entry (dead code, a jump table entry it could not + resolve), and a function whose entry is a bare `jmp` thunk can leave the + rest of the chunk weakly connected but not reachable. - Triskel raises ``EMPTY BL`` on a disconnected graph (its cycle-equivalence - bracket lists run dry), and IDA flowcharts do contain unreachable blocks -- - ``tests/test_graph.py:t_unreachable`` is exactly that shape. So we split the - work ourselves and stack the pieces side by side, which is also what the - native engine effectively does. + The edges are handed to the layout but never drawn. They cost a little + reserved space and, in exchange, triskel positions the orphans sensibly + (under the entry) instead of us stacking them beside the graph and hoping. + Attachment points are chosen at the natural entry of each orphan subgraph -- + a node no other orphan reaches -- so one phantom edge usually covers many + blocks. """ - adj: dict[int, set[int]] = {i: set() for i in g.nodes} + succ: dict[int, list[int]] = {i: [] for i in g.nodes} + preds: dict[int, list[int]] = {i: [] for i in g.nodes} for e in g.edges: - adj[e.src].add(e.dst) - adj[e.dst].add(e.src) - seen: set[int] = set() - comps: list[list[int]] = [] - for start in g.nodes: - if start in seen: - continue - stack, comp = [start], [] - seen.add(start) - while stack: - i = stack.pop() - comp.append(i) - for j in adj[i]: - if j not in seen: - seen.add(j) - stack.append(j) - comps.append(sorted(comp)) - return comps + succ[e.src].append(e.dst) + preds[e.dst].append(e.src) + + reach = _reachable(succ, root) + phantom: list[tuple[int, int]] = [] + while len(reach) < len(g.nodes): + rest = [i for i in g.nodes if i not in reach] + rest_set = set(rest) + head = next((i for i in rest + if not any(p in rest_set for p in preds[i])), rest[0]) + phantom.append((root, head)) + reach |= _reachable(succ, head) + return phantom def _edge_type(pt, kind: str): @@ -154,16 +171,10 @@ def run(g: G._Graph, root: int) -> tuple[list[G.Route], int]: pt.set_spacing(x_gutter=float(HGAP), y_gutter=float(VGAP), edge_height=float(LANE)) - by_src: dict[int, list[G.Edge]] = {} - for e in g.edges: - by_src.setdefault(e.src, []).append(e) - routes: list[G.Route] = [] - x_off = 0 - for comp in _components(g): - members = set(comp) - edges = [e for i in comp for e in by_src.get(i, []) if e.dst in members] - x_off = _layout_component(pt, g, comp, edges, routes, x_off) + if g.nodes: + phantom = _phantom_edges(g, root) + _layout_graph(pt, g, root, g.edges, phantom, routes) # The native engine learns which edges are back edges from its DFS, because # it has to reverse them to get a DAG. Triskel handles cycles internally and @@ -192,12 +203,32 @@ def run(g: G._Graph, root: int) -> tuple[list[G.Route], int]: return routes, len(bands) -def _layout_component(pt, g: G._Graph, comp: list[int], edges: list[G.Edge], - routes: list[G.Route], x_off: int) -> int: - """Lay one component out, shifted right by ``x_off``. Returns the next x.""" +def _layout_graph(pt, g: G._Graph, root: int, edges: list[G.Edge], + phantom: list[tuple[int, int]], + routes: list[G.Route]) -> None: + """Lay the whole graph out and append its routes.""" + order = [root] + [i for i in g.nodes if i != root] + succ: dict[int, list[int]] = {i: [] for i in g.nodes} + for e in edges: + succ[e.src].append(e.dst) + for a, b in phantom: + succ[a].append(b) + unreachable = set(g.nodes) - _reachable(succ, root) + if unreachable: + # Belt and braces: _phantom_edges is supposed to have made this + # impossible, and the consequence of being wrong is a SIGSEGV rather + # than an exception, so check before crossing into C++ rather than + # after. RuntimeError here means a fallback to native; a segfault means + # the user loses the session. + raise RuntimeError(f"{len(unreachable)} blocks unreachable from the " + f"layout root {root}: {sorted(unreachable)[:8]}") + builder = pt.make_layout_builder() tid = {} - for nid in comp: + # The root MUST be created first: triskel takes its graph root to be + # whichever node was made first, and every one of its analyses walks out + # from there. + for nid in order: n = g.nodes[nid] # NOTE the argument order: make_node(height, width). Upstream's Python # docstring says "width and height", which is the other way round; our @@ -205,6 +236,8 @@ def _layout_component(pt, g: G._Graph, comp: list[int], edges: list[G.Edge], tid[nid] = builder.make_node(height=float(n.h), width=float(n.w)) teid = [(builder.make_edge(tid[e.src], tid[e.dst], _edge_type(pt, e.kind)), e) for e in edges] + for a, b in phantom: + builder.make_edge(tid[a], tid[b], _edge_type(pt, G.E_UNCOND)) lay = builder.build() polys: list[tuple[G.Edge, list[tuple[float, float]]]] = [] @@ -214,31 +247,27 @@ def _layout_component(pt, g: G._Graph, comp: list[int], edges: list[G.Edge], # Triskel's origin is not its bounding box: a loop edge routed around the # side runs to y = -1, above every node. Normalise on everything drawn, not # just the boxes, or the canvas clips its own edges. - xs = [lay.get_coords(tid[i]).x for i in comp] - ys = [lay.get_coords(tid[i]).y for i in comp] + xs = [lay.get_coords(tid[i]).x for i in g.nodes] + ys = [lay.get_coords(tid[i]).y for i in g.nodes] xs += [x for _, wps in polys for x, _ in wps] ys += [y for _, wps in polys for _, y in wps] min_x, min_y = min(xs, default=0.0), min(ys, default=0.0) def cell(x: float, y: float) -> tuple[int, int]: - return int(round(y - min_y)), int(round(x - min_x)) + x_off + return int(round(y - min_y)), int(round(x - min_x)) - for nid in comp: + for nid in g.nodes: n = g.nodes[nid] p = lay.get_coords(tid[nid]) n.y, n.x = cell(p.x, p.y) - right = max((g.nodes[i].x + g.nodes[i].w for i in comp), default=x_off) for e, wps in polys: pts = _clean([cell(x, y) for x, y in wps]) if len(pts) < 2: continue _snap_ports(g, e, pts) - pts = _clean(pts) - routes.append(G.Route(edge=e, pts=pts, head=True, tail=True, + routes.append(G.Route(edge=e, pts=_clean(pts), head=True, tail=True, flipped=False)) - right = max(right, max(c for _, c in pts) + 1) - return right + COMPONENT_GAP def _box_index(g: G._Graph) -> tuple[dict[int, list[G.Node]], dict[int, list[G.Node]]]: diff --git a/tests/test_graph.py b/tests/test_graph.py index 96d4f85..a75ff68 100644 --- a/tests/test_graph.py +++ b/tests/test_graph.py @@ -161,6 +161,33 @@ def t_unreachable() -> None: check(len(lay.nodes) == 3, "unreachable: every block is placed") +def t_unreachable_entry() -> None: + """Blocks the entry cannot reach, including an entry with no successors. + + IDA hands these out routinely -- dead code, an unresolved jump table -- and + triskel's root is whichever node was created first, with every analysis + walking out from there. Anything it cannot reach is undefined behaviour: + this exact 7-block shape SEGFAULTED the interpreter, and lesser versions + threw "EMPTY BL" from its SESE bracket lists. A crash cannot be fallen back + from, so the engine must never be handed one. + """ + # entry 0 is a sink; 2 and 3 jump INTO it; 1 and 6 self-loop. + lay = layout(mk({0: [], 1: [(5, "switch"), (1, "fall"), (4, "switch")], + 2: [(5, "jump"), (0, "uncond")], 3: [(0, "switch")], + 4: [], 5: [(4, "jump")], + 6: [(2, "jump"), (6, "switch"), (3, "jump")]}), entry=0) + invariants(lay, "unreachable_entry") + check(len(lay.nodes) == 7, "unreachable_entry: every block is placed") + check(lay.stats.get("engine_error") is None, + f"unreachable_entry: no fallback ({lay.stats.get('engine_error')})") + + # An entry that reaches nothing at all, with everything hanging off nodes + # it cannot see, is the degenerate version of the same thing. + lay = layout(mk({0: [], 1: [(2, "jump")], 2: [(1, "jump")]}), entry=0) + invariants(lay, "orphan_pair") + check(len(lay.nodes) == 3, "orphan_pair: every block is placed") + + def t_long_edge() -> None: """An edge spanning many layers gets dummies, so it reserves real space.""" chain = {i: [(i + 1, "uncond")] for i in range(6)} @@ -280,7 +307,8 @@ def main() -> int: ENGINE = engine print(f"\nengine: {engine}") for fn in (t_linear, t_diamond, t_selfloop, t_loop, t_switch, - t_unreachable, t_long_edge, t_empty, t_row_query, t_hit_test): + t_unreachable, t_unreachable_entry, t_long_edge, t_empty, + t_row_query, t_hit_test): print(f" {fn.__name__}") fn() for path in sys.argv[1:]: |