一种使用收缩执行依赖图识别库函数的方法

摘要

一种使用收缩执行依赖图识别库函数的方法，属于软件逆向工程领域。所述方法为：1）对目标函数和库函数建立执行依赖图(EDG)；2）对EDG的局部EDG序列化，得到特征值序列和有序邻接矩阵；3）参照库函数EDG将目标函数和库函数EDG中有唯一点序列且不包含库函数EDG首尾的局部EDG收缩成点；4）判断库函数收缩EDG是否是目标函数收缩EDG的同构子图；5）验证识别结果是否有效。本方法不但能准确识别完整库函数，还能识别传统方法不能识别的多态及非连续字节的内联库函数，并有效缩短识别时间。

主权项

一种使用收缩执行依赖图识别库函数的方法，其特征在于所述方法步骤如下：步骤1：构建目标函数和库函数的执行依赖图；步骤2：对执行依赖图中的局部执行依赖图进行序列化，得到点特征值序列和存储边信息的有序邻接矩阵；步骤3：参照库函数执行依赖图将目标函数和库函数执行依赖图中有唯一确定的点序列且不包含库函数执行依赖图首尾的局部执行依赖图收缩成一个点；步骤4：判断库函数的收缩执行依赖图是否是目标函数收缩执行依赖图的同构子图，其中对于未收缩的点仅比较其特征值，对于收缩的点不仅比较其特征值序列，还比较其有序邻接矩阵；步骤5：验证目标函数收缩执行依赖图中识别出的与库函数收缩执行依赖图同构的子图是否是有效的识别结果。