CODEWITHSUNDEEP
indexinggraphcontrol-flowtopological-sortcontrol-flow-graph
PeterMouse
PeterMouse

Reputation: 1

How to get reasonable "topological order" of control flow graph (CFG) which may have loops when calculating MD index?

I am a noob in binary analysis and I am looking for your help.

I am working on calculating the MD index of callgraph function nodes by Python, and I have to analyze the control flow graph (CFG) inside the function, that's when the topological order of CFG nodes is needed.

To calculate function MD index, for every edge (src(e), dest(e)) in the CFG, I need to generate a 5-dimensional tuple (topological_order(src(e)), indegree(src(e)), outdegree(src(e)), indegree(dest(e)), outdegree(dest(e))). That's why I am now trying to get a "topological order" of CFG (or just a reasonable index list of CFG nodes, which seems like the output of topological sort), although there may be loops in the graph.

As we know, only DAG can be used to generate a topological order. However, in CFGs, there still exists obvious control flow relationship, and it seems possible to generate a list based on that relationship.

So how can I achieve my target? Are there any existing order of CFG nodes that may be ignored by me? Or are there any tools/methodologies recommended?

I thought about using reverse topological order or some other methods, but I cannot judge the efficiency about that. How to deal with loops really confused me.

I want to hear your suggestions. THANKS : >

Upvotes: 0

Views: 139

Answers (1)

ravenspoint
ravenspoint

Reputation: 20457

To find the 'quasi' topological sort of youir graph:

- find the loops ( cycles ) in the graph
- LOOP over the cycles
    - find the vertex in the cycle closest to the START vertex.
    - find the in-edge to closest vertex that is the "back edge" of the cycle: remove it
- do the topological sort ( the graph is now DAG )

Upvotes: 0

Related Questions