在没有控制流图(CFG)的情况下恢复控制流结构

作者在 2025 年 6 月 6 日针对 Java 反编译器进行研究,因对其他解决方案性能不满而展开。多数反编译器的控制流提取策略存在问题,如 javac 优化导致字节码与直接结构不匹配,CFG 复杂且难以从内向外或从外向内处理控制流。
作者提出自己的方法,利用 CFG 但直接使用会慢且与原程序顺序无关,故带回顺序并线性化图以使用更快算法。通过构建类似 AST 的结构,用枚举定义输入输出程序语句,用块(Block)模拟 CFG 节点,用breakcontinue模拟结构化goto
构建块时先构建箭头集(arrow set),利用 Ramshaw 的论文中的核心事实,但要注意continuebreak语句会被解析为箭头,可能导致生成代码混乱。提出从外部构建块的替代方法,找到分裂间隙(split gaps)并递归处理,若无新分裂间隙则创建块并处理复杂控制流,如引入调度器(dispatcher)来解决头对头冲突。
最终得到的 AST 具有关键性质,各块至少有一个无法被其他块满足的箭头,使块最小化且模式易于枚举。还介绍了提高时间复杂度的方法,利用段树(segment tree)和区间树(interval tree)等数据结构支持相关查询。作者强调这只是开始,还需后续工作,此方法可能适用于其他字节码语言但原生代码可能较难,且不要对用此方法制作 Java 反编译器抱太大期望。

阅读 16
0 条评论