graph layout and edge routing enhancements

[psifertex]

Sometimes edge routing gets a little over-excited and swings wider than strictly necessary. It should simmer down some.

Additionally, while it's technically not the exact same thing, we'll likely address the overall tendency to force analysis to be more vertical that is optimal whenever we refactor the edge routing as well.

[withzombies]

Good example:

[plafosse]

Nodes can be placed in suboptimal positions as well. When we implement the second pass graph layout optimization we should consider moving nodes as well.

[percontation]

sub_80480d0 of KPRCA_00009 basically exhibits every CFG-routing oddity I've ever seen. Some edges with (visually) distinct issues may be found at 0x08048119, 0x0804821d, 0x080480ed, 0x080481f1

Particularly fun edge at 0x0804836d, which takes a trip that it probably shouldn't up and right of the original bb despite the target bb being down and left (which isn't inherently wrong, this is kinda an ass function :P after all)

(I'm on Binary Ninja v1.0.290, ID 11933a1f)

[CryptXor]

Seems to happen only on large functions with multiple conditions if that helps.

[plafosse]

There are lots of issue with edge routing currently, excessive cornering, routes on top of other routes, excessive crossings, bad ordering. During v1.2 we will be refactoring the algorithm to improve layout.

[jeffli678]

Here is a problem with the edge: the edge pierces a basic block.

I got the binary from https://crackmes.one/crackme/5ab77f6233c5d40ad448c9e4. If the downloaded archive is password protected, the password is "crackmes.de" (no quotes).

[Aplet123]

I've found a rather extreme case of the edge swinging wide: Here is the binary (weird arrow is near the bottom of bench::with_get::h350330d79060ee3c:): bin.zip

[psifertex]

Thanks for the example. More test cases are always appreciated.

[plafosse]

The following flowgraph will produce an error:

graph = FlowGraph()
n1 = FlowGraphNode(graph)
n1.lines = ['n1']
graph.append(n1)
n2 = FlowGraphNode(graph)
n2.lines = ['n2']
graph.append(n2)
n4 = FlowGraphNode(graph)
n4.lines = ['n4']
graph.append(n4)
n8 = FlowGraphNode(graph)
n8.lines = ['n8']
graph.append(n8)
n9 = FlowGraphNode(graph)
n9.lines = ['n9']
graph.append(n9)
n10 = FlowGraphNode(graph)
n10.lines = ['n10 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA']
graph.append(n10)
n11 = FlowGraphNode(graph)
n11.lines = ['n11']
graph.append(n11)
n1.add_outgoing_edge(BranchType.UnconditionalBranch, n2)
n1.add_outgoing_edge(BranchType.UnconditionalBranch, n4)
n4.add_outgoing_edge(BranchType.UnconditionalBranch, n11)
n2.add_outgoing_edge(BranchType.UnconditionalBranch, n8)
n8.add_outgoing_edge(BranchType.UnconditionalBranch, n9)
n8.add_outgoing_edge(BranchType.UnconditionalBranch, n10)
n9.add_outgoing_edge(BranchType.UnconditionalBranch, n11)
n11.add_outgoing_edge(BranchType.UnconditionalBranch, n8)
show_graph_report('Layout Test Graph', graph)

[mechanicalnull]

Just adding a note that layout issues also my choice of whether or not to use the flowgraph API, which I'd like to use more.