From d74b6f53e0969efc586d52776fa3b6d40b92a650 Mon Sep 17 00:00:00 2001 From: idatui Date: Sun, 9 Aug 2026 14:17:13 +0200 Subject: Graph: never hand triskel a block its root cannot reach "EMPTY BL" in the status bar is triskel's own bracket-list assertion from its SESE pass, and it turned out to be the mild version of the problem. Triskel's graph root is whichever node was created FIRST, and every analysis walks out from it. Anything unreachable from that node is undefined behaviour. We were: - creating nodes in id order, so the root was the lowest-numbered block rather than the entry, and - splitting only WEAKLY connected components, which says nothing about reachability. A 7-block CFG whose entry has no successors -- IDA hands those out for thunks and for dead code it could not resolve -- SEGFAULTS the interpreter. That is unsurvivable: it takes the session down and there is no exception to fall back from. Now the entry is created first, orphan blocks are attached to it with phantom edges that steer placement but are never drawn (one edge usually adopts a whole orphan subgraph, attached at a node no other orphan reaches), and reachability is asserted in python BEFORE crossing into C++. This replaces the component splitting entirely: one layout instead of N stacked side by side, and triskel gets to place the orphans. The reproducer is now a test (t_unreachable_entry). Remaining fallbacks on the ls corpus are 8/1200 layouts, all the upstream box-overlap defect, all but one on 300-500 block functions. --- docs/GRAPH_VIEW.md | 22 +++++--- idatui/graph_triskel.py | 133 +++++++++++++++++++++++++++++------------------- tests/test_graph.py | 30 ++++++++++- 3 files changed, 126 insertions(+), 59 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. - - 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. +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. + + 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:]: -- cgit v1.3.1-sl0p