Question

在反编译器的数据流分析领域中还有许多问题有待解决，主要是由于文献里提出的反编译器有诸多限制；汇编源文件的反编译 [Hou73、Fri74、Wor78、Bri81]、带符号调试信息的目标文件(.obj) 的反编译 [Reu88]、以及建造一个反编译器的编译器规约需求 [BB91, Bow93, BB93]。在反编译纯粹的二进制文件的时候，数据流分析是必要的，因为没有关于数据的类型及其使用的附加信息。下面几节概述在这个领域中已经做过的工作。

5.1.1 条件码的清除

Marshall 和 Zobrist 提出一个翻译程序，把微处理器目标代码 (i8085) 翻译成一个行为上等价的 PL/1 程序，而且被用于电子系统模拟 [MZBR85]。最后的 PL/1 程序包含大量定义标志的语句，即使后面的程序没有使用或引用这些标志。这促使 DeJean 和 Zobrist 在文献[DZ89]中阐述，使用一个延伸算法来最优化标志定义。这个方法清除掉翻译过程中 50%以上的标志定义，生成的 PL/1 程序只定义后面条件必需要的标志。

本论文所提出的方法比这个标志定义最优化更加优越，这里不仅确定哪些标志定义是与主题无关因而是不必要的，而且还利用定义和使用该标志的指令组合集确定其布尔条件表示式。通过这样做，使目标高级语言程序(HLL) 不依赖标志的概念及使用，就象任何真正的 HLL 程序一样没有这些东西。

5.1.2 清除多余的读写

Housel 在文献[Hou73]中提出一个文本压缩方法，用来清除中间的读写寄存器指令(loads and stores)。这个方法工作在程序的三地址中间表示法上，而且由两个步骤组成：向前代入和向后代入。前一个步骤把一条赋值指令的源操作数代入一条使用相同结果操作数的后续指令 (如果发现结果在相同基本块中还没有被使用的话，即 not busy)。后一步骤把一条赋值指令的结果操作数代入一条把该赋值指令源操作数定义为结果操作数的前面指令 (不是赋值指令)。在 Knuth 的 MIXAL 编译器编译生成的汇编代码中应用这个方法时指令缩减率最高达到 40%。

Hopwood 在文献[Hop78]中描述了一个表达式凝聚(expression condensation) 的方法，使用向前代入(forward substitution) 把两个或更多个中间指令结合成一个等价的表达式。这个方法指出变量或寄存器向前代入的 5 个必要条件和 6 个充分条件。这个方法基于变量使用分析(variable usage analysis)。他选择的这种控制流向图——每条中间指令为一个结点，而非每个基本块一个结点——必然地受到诸多条件的限制。这意味着变量跨结点边界向前代入，导致整个处理不必要地更加复杂。

本论文中提出的子过程间数据流分析定义了两个充分条件，在此条件下可以用某些指令使用的寄存器代入或代替到另一条指令里面，这些指令包括如 push 和 pop 这样的中间指令。这个方法不仅通过清除掉中间的寄存器和指令定义来发现表达式，而且还确定了子程序的实际参数、函数返回值，并去除伪高级指令。该方法是基于二进制程序最初的高级中间表示法——在语义上等价于低级中间表示法，并将它转换成一个 HLL 表示法。