在计算MD索引时，如何得到可能存在环路的控制流图（CFG）合理的“拓扑顺序”？

Question

我是二进制分析方面的菜鸟，我正在寻求您的帮助。

我正在用Python计算调用图函数节点的MD索引，并且我必须分析函数内部的控制流图（CFG），这时候就需要CFG节点的拓扑顺序。

为了计算函数MD索引，对于CFG中的每条边

(src(e), dest(e))

，我需要生成一个5维元组

(topological_order(src(e)), indegree(src(e)), outdegree(src(e)), indegree(dest(e)), outdegree(dest(e)))

。 这就是为什么我现在试图获得 CFG 的“拓扑顺序”（或者只是 CFG 节点的合理索引列表，这看起来像是拓扑排序的输出），尽管图中可能存在循环。

众所周知，只有DAG可以用来生成拓扑顺序。然而，在CFG中，仍然存在明显的控制流关系，并且似乎可以基于该关系生成列表。

那么我怎样才能实现我的目标呢？是否有任何现有的 CFG 节点顺序可能会被我忽略？或者有什么工具/方法推荐吗？

我想过使用逆拓扑顺序或其他一些方法，但我无法判断其效率。如何处理循环真的让我很困惑。

我想听听你的建议。谢谢：>

Answer 1

找到你的图的“准”拓扑排序：

- 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 )