Alternating Control Flow Reconstruction
Alternating Control Flow Reconstruction
复制标题
交替控制流重构
DOI：
10.1007/978-3-642-27940-9_18
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Dmitry Kravchenko
中科院分区：
文献类型：
--
作者：
Johannes Kinder;Dmitry Kravchenko
未解决的间接分支指令是从机器代码中静态重建控制流程图（CFG）的主要障碍。如果静态分析无法计算一个分支的精确目标集，则必要的保守过度透明度会引入大量的伪边缘，从而导致更不精确和退化的CFG。
在本文中，我们建议利用不足的临时来解决此问题。我们为控制流重建提供了一个抽象的解释框架，该框架在过度和不足之间交替。有效地，该框架可以根据需要在程序上施加其他先决条件，从而避免了间接分支的保守过度交易。
我们使用动态观察到的执行跟踪和恒定传播给出了框架的示例实例化。我们报告了初步的实验结果，证实我们的交替分析比纯纯过或不及格透明的分析更接近混凝土CFG。
Unresolved indirect branch instructions are a major obstacle for statically reconstructing a control flow graph (CFG) from machine code. If static analysis cannot compute a precise set of possible targets for a branch, the necessary conservative over-approximation introduces a large amount of spurious edges, leading to even more imprecision and a degenerate CFG.
In this paper, we propose to leverage under-approximation to handle this problem. We provide an abstract interpretation framework for control flow reconstruction that alternates between over- and under-approximation. Effectively, the framework imposes additional preconditions on the program on demand, allowing to avoid conservative over-approximation of indirect branches.
We give an example instantiation of our framework using dynamically observed execution traces and constant propagation. We report preliminary experimental results confirming that our alternating analysis yields CFGs closer to the concrete CFG than pure over- or under-approximation.