反编译过程中的寄存器传播方法、装置及反编译器

摘要

一种反编译过程中的寄存器传播方法、装置及反编译器，该方法包括：构造函数内的所有的指令路径；遍历各指令所在的各指令路径，根据各指令所在的所有的指令路径，分别计算出各指令的使用定义链，得到各指令的使用定义链集；顺序扫描各指令，根据各指令的使用定义链、预设寄存器传播规则，确定各指令的寄存器传播方式，并根据确定的寄存器传播方式进行各指令的寄存器传播。根据本发明方案，是使得指令的使用定义链的生成依赖于指令所在的指令路径集，指令能否进行传播的依据建立在对指令所含的使用定义链的情况的分析之上，实现了寄存器的跨基本块传播，使得寄存器传播更为彻底，提高了反编译结果的正确性和可读性。

说明书

技术领域

本发明涉及反编译技术领域，特别涉及一种反编译过程中的寄存器传播方法、一种反编译过程中的寄存器传播装置以及一种反编译器。

背景技术

反编译器的反编译过程一般可分为7个阶段，包括句法分析阶段、语法分析阶段、中间代码生成阶段、控制流程图生成阶段、数据流分析阶段、控制流分析阶段和代码生成阶段。其中，数据流分析阶段是对由前端生成的中间代码进行分析，将这些中间代码转换成高级表达式。中间代码是一个汇编类型的表示法，它使用寄存器和条件码，这种类型的代码与高级语言代码相差甚远，需要被进一步转换成与高级语言代码相近的高级表达式，这个转换过程主要包括下面几个部分：无用指令的清除、条件码的清除、寄存器参数和函数返回值的确定、中间过渡寄存器和指令的清除、实际参数的确定以及在跨子程序调用之间传播数据类型。

寄存器传播是属于数据流分析过程的一部分，其清除中间过渡寄存器和指令，重建在编译过程中丢失的部分信息，并生成与高级语言相近的高级表达式。

在现有常规的寄存器传播方式中，是在数据流分析阶段就进行寄存器的传播，由于此时还没有进行控制流分析过程，还无法获得各基本块之间的关系，因而寄存器的传播只能局限在基本块内部进行，无法跨基本块进行，导致传播不够彻底，影响反编译结果的正确性和可读性。

发明内容

针对上述现有技术中存在的问题，本发明的目的在于提供一种反编译过程中的寄存器传播方法、一种反编译过程中的寄存器传播装置、以及一种反编译器，其可以实现跨基本块的寄存器传播，使得寄存器传播更为彻底，提高反编译结果的正确性和可读性。

为达到上述目的，本发明采用以下技术方案：

一种反编译过程中的寄存器传播方法，包括步骤：

构造函数内的所有的指令路径；

遍历各指令所在的各指令路径，根据各指令所在的所有的指令路径，分别计算出各指令的使用定义链，得到各指令的使用定义链集；

顺序扫描各指令，根据各指令的使用定义链、预设寄存器传播规则，确定各指令的寄存器传播方式，并根据确定的寄存器传播方式进行各指令的寄存器传播。

一种反编译过程中的寄存器传播装置，包括：

指令路径构造单元，用于构造函数内的所有的指令路径；

与所述指令路径构造单元相连接的使用定义链单元，用于遍历各指令所在的各指令路径，根据各指令所在的所有的指令路径，分别计算出各指令的使用定义链，得到各指令的使用定义链集；

与所述使用定义链单元相连接的传播单元，用于顺序扫描各指令，根据各指令的使用定义链、预设寄存器传播规则，确定各指令的寄存器传播方式，并根据确定的寄存器传播方式进行各指令的寄存器传播。

一种反编译器，该反编译器包括如上所述的寄存器传播装置。

根据本发明的方案，其通过构造函数内的所有的指令路径，并遍历各指令路径，根据指令所在的所有的指令路径，来计算出指令的各使用定义链，使得指令的使用定义链的生成依赖于指令所在的指令路径集，指令能否进行传播的依据建立在对指令所含的使用定义链的情况的分析之上，实现了寄存器的跨基本块传播，使得寄存器传播更为彻底，提高了反编译结果的正确性和可读性。

附图说明

图1是本发明的反编译过程中的寄存器传播方法实施例的流程示意图；

图2是汇编代码示例图；

图3是对图2中的汇编代码构造指令路径的示例图；

图4是指令的使用定义链的示例图；

图5是依据本发明方法进行跨基本块寄存器传播的示例图；

图6是本发明的反编译过程中的寄存器传播装置实施例的结构示意图。

具体实施方式

本发明的反编译过程中的寄存器传播方法及装置，可应用于各种语言类型的反编译过程，在下述各具体实施例的说明中，以应用于C反编译器中的C反编译过程进行说明。

如图1所示，是本发明的反编译过程中的寄存器传播方法实施例的流程示意图，其包括步骤：

步骤S101：构造函数内的所有的指令路径，在应用于C反编译器中的C反编译过程中时，这里的函数为C函数，进入步骤S102；

步骤S102：遍历各指令所在的各指令路径，根据各指令所在的所有的指令路径，分别计算出各指令的使用定义链(ud-chain，use-define chaine)，得到各指令的使用定义链集，进入步骤S103；

步骤S103：顺序扫描各指令，根据各指令的使用定义链、预设寄存器传播规则，确定各指令的寄存器传播方式，并根据确定的寄存器传播方式进行各指令的寄存器传播。

根据本实施例的方案，其通过构造函数内的所有的指令路径，并遍历各指令路径，根据指令所在的所有的指令路径，来计算出指令的各使用定义链，使得指令的使用定义链的生成依赖于指令所在的指令路径集，指令能否进行传播的依据建立在对指令所含的使用定义链的情况的分析之上，实现了寄存器的跨基本块传播，使得寄存器传播更为彻底，提高了反编译结果的正确性和可读性。

上述函数内所有的指令路径的构造包括两部分：图的构建和指令路径的识别。其中，图的构建过程是从函数中的第一条指令开始，以指令为节点，以指令的执行顺序为有向边，建造出一副有向图；而指令路径的识别则是基于该有向图，找出从头节点到各个返回指令ret节点(return节点)的所有指令路径。

其中，这里的指令路径定义为一个连续的指令的集合，当该集合中的任意一个指令被执行后，该指令的后续指令都将被执行，是基本块定义的延伸。

此外，在遍历各指令所在的指令路径时，可以得到各指令所在的所有的指令路径集，在计算指令的使用定义链时，对于任意一个指令来说，可以根据该指令所在的所有的指令路径，分别计算出相对于各指令路径的使用定义链，得到该指令的使用定义链集。这里的使用定义链的定义，可以与现有技术的常规方式中的使用定义链的定义相同。

上述预设寄存器传播规则具体可以包括：

对于定义了当前指令的源寄存器的指令(为便于区分，称之为第一指令)，若在从该第一指令到当前指令的指令路径上，该第一指令的源操作数与目的操作数未被重新定义过，则当前指令可以传播；

若当前指令所使用的寄存器被处于不同指令路径的指令所定义，该当前指令不能被传播。

在确定了各指令的寄存器传播方式之后，进行寄存器传播时：

如果当前指令可以传播，则将该当前指令的源寄存器替换为该当前指令的使用定义链所指向的指令的源寄存器，即用当前指令的使用定义链所指向的指令的源寄存器替换该当前指令的源寄存器，同时删除该使用定义链所指向的指令，实现跨基本块的寄存器的传播；

如果当前指令确定不能被传播，则保持该当前指令不变。

根据上述本发明的反编译过程中的寄存器传播方法，以下以一个具体反编译过程中的具体操作过程进行详细说明。

假设输入的汇编代码如图2所示，观察图2中的汇编代码可以发现：虽然指令04定义了寄存器eax，指令06使用了寄存器eax，但指令04定义的寄存器eax却不能被传播到指令06，这是因为，在指令04执行后，指令06并没有执行；另外，指令06虽然定义了寄存器eax，指令07使用了寄存器eax，但是，指令06定义的寄存器eax也不能传播到指令07，这是因为，指令07使用的寄存器被多个基本块定义了(指令04和指令06都定义了它)。而这些也正是常规方法之所以没有进行跨基本块寄存器传播的原因之一，也是本发明的跨基本块寄存器传播的难点所在。

对此，本发明方案先构造函数内的所有的指令路径：从代码的第一条指令开始，以指令为节点，以指令的执行顺序为有向边，建造出一幅有向图，针对图2中的汇编代码构造的指令路径如图3所示，根据该图中可以得到所有的指令路径，即从头节点到各个返回指令ret节点的所有指令路径。特别的，当函数存在循环路径时，循环路径上的指令将被添加到指令路径上，且只被添加一次。根据上述的指令路径的定义(连续的指令的集合，该集合上的任意指令被执行后，其后续指令都将被执行)，从图3中可以得到两条指令路径：(1)01→02→03→06→07→08、(2)01→02→03→04→05→07→08。

随后，计算每条指令的使用定义链ud-chain：基于上述构建的有向图，对于每条指令路径，计算出该指令路径中的每条指令的使用定义链ud-chain，如图4所示。从图4中我们看出，虽然指令04定义了寄存器eax，指令06紧接着使用了寄存器eax，但是在生成指令的使用定义链ud-chain时，指令04并没有成为指令06的指令使用定义链ud-chain；另外，可以发现，尽管指令07使用的寄存器被多个基本块定义了(指令04和指令06都定义了它)，但是指令07的使用定义链ud-chain的确既包含了指令04，也包含了指令06。由此说明，本发明的方法有效地解决了跨基本块寄存器传播的难点。

然后进行寄存器的传播：顺序扫描所有指令，根据先前得到的每条指令的使用定义链ud-chain，并参考上述预设寄存器传播规则，来最终决定是否进行寄存器传播：如果传播，则将本条指令的源寄存器替换为本指令使用定义链ud-chain所指向的指令的源寄存器，即用当前指令的使用定义链所指向的指令的源寄存器替换该当前指令的源寄存器，同时删除使用定义链ud-chain所指向的指令，如图5中的指令02；如果不传播，则保持指令不变。如图5所示，根据本发明方法，指令2执行了跨基本块寄存器传播，而指令07不执行跨基本块寄存器传播。

根据上述本发明的方法，本发明还提供一种反编译过程中的寄存器传播装置，如图6所示，是本发明的反编译过程中的寄存器传播装置实施例的结构示意图，其包括：

指令路径构造单元201，用于构造函数内的所有的指令路径；

与指令路径构造单元201相连接的使用定义链单元202，用于遍历各指令所在的各指令路径，根据各指令所在的所有的指令路径，分别计算出各指令的使用定义链，得到各指令的使用定义链集；

与使用定义链单元202相连接的传播单元203，用于顺序扫描各指令，根据各指令的使用定义链、预设寄存器传播规则，确定各指令的寄存器传播方式，并根据确定的寄存器传播方式进行各指令的寄存器传播。

根据本实施例的方案，其通过构造函数内的所有的指令路径，并遍历各指令路径，根据指令所在的所有的指令路径，来计算出指令的各使用定义链，使得指令的使用定义链的生成依赖于指令所在的指令路径集，指令能否进行传播的依据建立在对指令所含的使用定义链的情况的分析之上，实现了寄存器的跨基本块传播，使得寄存器传播更为彻底，提高了反编译结果的正确性和可读性。

上述函数内所有的指令路径的构造包括两部分：图的构建和指令路径的识别。其中，图的构建过程是从函数中的第一条指令开始，以指令为节点，以指令的执行顺序为有向边，建造出一副有向图；而指令路径的识别则是基于该有向图，找出从头节点到各个返回指令ret节点的所有指令路径。

其中，这里的指令路径定义为一个连续的指令的集合，当该集合中的任意一个指令被执行后，该指令的后续指令都将被执行，是基本块定义的延伸。

此外，在遍历各指令所在的指令路径时，可以得到各指令所在的所有的指令路径集，在计算指令的使用定义链时，对于任意一个指令来说，可以根据该指令所在的所有的指令路径，分别计算出相对于各指令路径的使用定义链，得到该指令的使用定义链集。这里的使用定义链的定义，可以与现有技术的常规方式中的使用定义链的定义相同。

此外，上述预设寄存器传播规则具体包括：

对于定义了当前指令的源寄存器的指令(为便于区分，称之为第一指令)，若在从该第一指令到当前指令的指令路径上，该第一指令的源操作数与目的操作数未被重新定义过，则当前指令可以传播；

若当前指令所使用的寄存器被处于不同指令路径的指令所定义，该当前指令不能被传播。

在确定了各指令的寄存器传播方式之后，在进行具体的寄存器传播时：

如果当前指令可以传播，则将该当前指令的源寄存器替换为该当前指令的使用定义链所指向的指令的源寄存器，即用当前指令的使用定义链所指向的指令的源寄存器替换该当前指令的源寄存器，同时删除该使用定义链所指向的指令，实现指令的跨基本块寄存器传播；

如果当前指令确定不能被传播时，保持该当前指令不变。

本发明的反编译过程中的寄存器传播装置的具体的寄存器传播方式与上述本发明方法中的相同，在此不予赘述。

根据上述本发明的反编译过程中的寄存器传播方法及装置，本发明还提供一种反编译器，其包括上述反编译过程中的寄存器传播装置，采用上述寄存器传播方法进行寄存器传播，该反编译器中的其他技术特征可以与现有的反编译器中的相同，在此不予赘述。

以上所述的本发明的具体实施方式，仅仅是对本发明的其中一个具体实施例的详细说明，并不构成对本发明保护范围的限定。任何在本发明的精神和原则之内所作的修改、等同替换和改进等，均应包含在本发明的权利要求保护范围之内。