一种利用图同构验证编译器的方法

摘要

本发明公开一种利用图同构验证编译器的方法，包括待处理的源程序和将源程序生成目标程序的编译器，在选定环境下建立一个反编译器，通过反编译器将目标程序反编译成对比程序，验证对比程序和源程序之间的语义一致性，并在此基础上，分别建立源程序和对比程序的控制流图相关结点信息后进行同构判定，从而得到编译器是否安全的结论。本发明通过判断对比程序与源程序的控制流图是否同构，来验证编译器的安全性。该方法直接将反编译后的代码与源代码进行语义比较，避免了验证过程中由于源代码信息丢失导致验证不全面的问题，该算法不需要再次遍历控制流图，使得图同构判断算法简单，易于实现。

主权项

一种利用图同构验证编译器的方法，包括待处理的源程序和将源程序生成目标程序的编译器，在选定环境下建立一个反编译器，通过反编译器将目标程序反编译成对比程序，验证对比程序和源程序之间的语义一致性，其特征在于，在此基础上分别建立源程序和对比程序的控制流图相关结点信息后进行同构判定，从而得到编译器是否安全的结论，具体步骤如下： 步骤1、首先对源程序和对比程序的语句按顺序进行扫描，并利用带序号的结点进行标识； 步骤2、同时建立一个辅助栈表，并将当前结点及相关结点信息压入辅助栈表框； 步骤3、对条件结构的所有结点进行简化并用简化结点替代，然后将简化结点压入辅助栈表原条件结构的结点位置处形成简化栈表，并且在程序中所有结点被扫描完成之后，将栈表中的结点依次出栈，在上述简化过程中，建立该结点的邻接链表，同时建立一个记录简化结点信息的简化信息表； 步骤4、根据结点的邻接链表和简化信息表建立源程序和对比程序的出入度信息，并生成相应的n点连通子图的出入度序列； 步骤5、根据出入度序列判断源程序和对比程序的控制流图是否同构；其中，当两个控制流图中的任意n点连通子图的出入度序列相同时，则表明两个控制流图是同构的，进而表明源程序与目标程序是相同的，并得到编译器是安全的结果；反之，则证明编译器是不安全的。