一种基于数据丰富度与迁移代价感知的漏洞成因定位方法

1.一种基于数据丰富度与迁移代价感知的漏洞成因定位方法，其特征在于包括以下步骤：第一步，采用基于动静结合的漏洞崩溃相关节点推断方法推断漏洞崩溃相关节点，方法是：1.1使用编译框架LLVM对目标程序Prog进行编译，生成与源代码语言、硬件无关的中间代码IRProg；1.2使用SVF工具对IRProg进行值流分析，构建IRProg的过程间稀疏值流图VFG，VFG＝{(node 11 ,node 12 ,edge 1 )，…，(node n1 ,node n2 ,edge n )，…，(node N1 ,node N2 ,edge N )}，1≤n≤N，N是VFG中值流依赖关系总数，node n1 、node n2 是VFG中的节点，内容分别是IRProg中的某条语句、或者某个参数、或者某个变量、或者某块内存区域，edge n 是VFG中的边，表示从node n1 指向node n2 的值流依赖关系；1.3向Prog输入初始概念验证PoC并运行Prog，记录Prog的崩溃处的语句和参数信息，令为CrashInfo＝{var 1 ,var 2 ,…,var q ,…,var Q }，1≤q≤Q，Q是Prog崩溃处的语句、参数信息总数，var q 是CrashInfo中第q条语句、参数信息；1.4遍历VFG，使得CrashInfo中的元素与VFG中的节点形成对应关系，生成初始漏洞崩溃点节点地址集合CrashVar，CrashVar＝{nodeAddr 1 ,nodeAddr 2 ,…,nodeAddr i ,…,nodeAddr I }，1≤i≤I，I是初始漏洞崩溃节点地址总数；1.5分析VFG，识别与CrashVar中对应的初始漏洞崩溃节点存在数据流关系的其他潜在漏洞崩溃语句、参数信息，生成可疑漏洞崩溃节点地址集合SusVar，SusVar＝{nodeAddr 1 ,nodeAddr 2 ,…,nodeAddr m ,…,nodeAddr M }，1≤m≤M，M是可疑漏洞崩溃节点地址总数，nodeAddr m 与nodeAddr i 含义相同，是第m个可疑漏洞崩溃节点在VFG中的对应地址；1.6使用CLANG对Prog进行编译；1.7通过GDB调试器的动态调试功能追踪Prog的实际执行路径，在SusVar所包含的所有可疑漏洞崩溃节点地址处设置断点，根据执行过程中断点命中情况筛选出实际参与运行的节点，提取出可疑漏洞崩溃节点集合FlitVar，FiltVar＝{node 1 ,node 2 ,…,node k ,…,node K }，node k 是程序Prog中第k个可疑漏洞崩溃节点，1≤k≤K，K是可疑漏洞崩溃节点总数，K≤M；第二步，采用基于数据丰富度引导的高质量测试用例生成方法监测在模糊测试过程中生成的测试用例在运行过程中FiltVar中的漏洞崩溃节点的取值，并以取值的数据丰富度为引导生成数据丰富度增加的高质量测试用例，并通过迁移代价降低的模糊测试方法筛选高质量测试用例得到状态转换测试用例；方法是：2.1使用LLVM-10的插桩工具，在Prog源码中找到FiltVar中的node 1 ,node 2 ,…,node k ,…,node K 的定义或使用位置，并在Prog源码中的这些位置进行插桩，生成插桩后的中间表示文件Prog_IR，此时node 1 ,node 2 ,…,node k ,…,node K 即为对应的K个插桩位置；2.2使用clang-10编译器，将Prog_IR编译为可执行的目标程序Prog_I；在编译过程中，使用内存错误检查工具AddressSanitizer检测目标程序Prog_I的崩溃信息；2.3基于PoC，采用模糊测试工具AFL-FUZZ生成测试用例集合S，S＝{s 1 ,s 2 ,…,s f ,…,s F }，1≤f≤F，S是通过AFL-FUZZ基于PoC生成的测试用例集合，F是S中测试用例总数，s f 是S中第f个测试用例；2.4对测试用例集合S进行数据丰富度筛选和崩溃判断分类，得到状态转换测试用例集合TransVar和测试用例真实状态标签集合Y，TransVar＝{TV 1 ,TV 2 ,…,TV t ,…,TV T }，Y＝{y 1 ,y 2 ,…,y t ,…,y T }，1≤t≤T，T为状态转换测试用例总数，TV t 为满足数据丰富度增加且迁移代价降低的TransVar中的第t个测试用例，y t 为TV t 的测试用例真实状态标签，y t ＝1表示TV t 会导致Prog_I崩溃，y t ＝0表示TV t 不会导致Prog_I崩溃；第三步，基于Prog和PoC，通过污点分析Prog，获取候选漏洞触发相关节点集合Z，Z＝{z 1 ,z 2 ,…,z r ,…,z R }；接着基于状态转换测试用例集合TransVar，采用互信息算法对Z进行过滤，获取更加精确的候选漏洞触发相关节点集合，也即优化后的候选漏洞触发相关节点集合Z’，同时生成用于聚类操作的集合VSet；最后采用K-means聚类算法，基于集合VSet和候选漏洞触发相关节点集合Z’，对TransVar内的所有测试用例进行聚类，利用测试用例的真实状态标签评估聚类结果的准确性，根据聚类结果的准确性对Z’中所有候选漏洞触发相关节点进行排名，作为最终漏洞成因定位结果；方法如下：3.1将PoC输入到Prog中，采用基于LLVM的动态插桩工具DFSan追踪PoC的传播路径，识别Prog中所有被污染的节点，将Prog中所有被污染的节点添加到候选漏洞触发相关节点集合Z中，Z＝{z 1 ,z 2 ,…,z r ,…,z R }，1≤r≤R，R为候选漏洞触发相关节点总数，z r 为Prog中第r个被污染的节点，也即Z中第r个候选漏洞触发相关节点；3.2利用互信息算法对Z进行筛选，生成优化并排序后的候选漏洞触发相关节点集合Z’和用于聚类操作的集合VSet，Z’＝{z’ 1 ,z’ 2 ,…,z’ p ,z’ p+1 ,…,z’ P }，P≤R,z’ p 是Z’中第p个优化后的候选漏洞触发相关节点；z’ p 对应的互信息值>z’ p+1 对应的互信息值；VSet＝{V’ 1 ，V’ 2 ，…,V’ p ，…,V’ P }，V’ p 是z’ p 对应的候选漏洞触发相关节点状态集合；3.3基于集合VSet和候选漏洞触发相关节点集合Z’，采用K-means聚类算法，对TransVar进行聚类，得到漏洞成因位置的排名集合RankingVar，RankingVar＝{rank 1 ,rank 2 ,…,rank p ，…rank P }，rank p 为Z’中准确率从高到低排名第p的元素，若1≤a≤b≤P，则rank a 的准确率Accuracy a ≥rank b 的准确率Accuracy b ，Accuracy a 表示基于z’ a 的聚类结果与真实状态标签的一致性程度,Accuracy b 表示基于z’ b 的聚类结果与真实状态标签的一致性程度；RankingVar即为对Prog进行漏洞成因定位的结果。 2.如权利要求1所述的一种基于数据丰富度与迁移代价感知的漏洞成因定位方法，其特征在于1.4步所述遍历VFG，使得CrashInfo中的元素与VFG中的节点形成对应关系，生成初始漏洞崩溃点节点地址集合CrashVar的方法是：1.4.1令变量i＝1，n＝1,初始化CrashVar为空；1.4.2取出VFG中第n个三元组(node n1 ,node n2 ,edge n )，提取node n2 中所包含的语句、参数信息，将node n2 中所包含的语句、参数信息放到node n2 的语句、参数信息集合NodeInfo n2 中，NodeInfo n2 ＝{var 1 ,var 2 ,…,var p ,…,var P }，1≤p≤P，P是node n2 中所包含的语句、参数信息总数，var p 是NodeInfo中第p条语句、参数信息；1.4.3对CrashInfo与NodeInfo n2 进行取交集运算，得到交集结果Res；1.4.4若Res为空，转1.4.6；若不为空，转1.4.5；1.4.5记录node n2 的地址为第i个初始漏洞崩溃节点在VFG中的对应地址nodeAddr i ，如果nodeAddr i 不在CrashVar中，则将node i 加入CrashVar，同时令i＝i+1，转步骤1.4.6；如果nodeAddr i 已经存在于CrashVar中，则直接转步骤1.4.6；1.4.6令n＝n+1；1.4.7若n>N，说明已经完成对VFG的遍历，得到初始漏洞崩溃节点地址集合CrashVar，CrashVar＝{nodeAddr 1 ,nodeAddr 2 ,…,nodeAddr i ,…,nodeAddr I }，结束；若n≤N，说明还未完成对VFG的遍历，转1.4.2。 3.如权利要求1所述的一种基于数据丰富度与迁移代价感知的漏洞成因定位方法，其特征在于1.5步所述分析VFG，识别与CrashVar中对应的初始漏洞崩溃节点存在数据流关系的其他潜在漏洞崩溃语句、参数信息，生成可疑漏洞崩溃节点地址集合SusVar的方法是：1.5.1初始化SusVar＝CrashVar，将CrashVar中的nodeAddr 1 ,nodeAddr 2 ,…,nodeAddr i ,…,nodeAddr I 加载至节点地址队列NodeQueue中，令|NodeQueue|为NodeQueue内的元素数量；1.5.2令变量i＝1，若|NodeQueue|≠0，转步骤1.5.3；若|NodeQueue|＝0，说明已经完成对待验证节点的遍历，转步骤1.5.5；1.5.3取出队列NodeQueue头部第一个元素nodeAddr i ，提取nodeAddr i 对应的节点，令为node i2 ，在VFG中查找以node i2 为第二个元素的三元组(node i1 ,node i2 ,edge i )是否存在，若存在，转步骤1.5.4；若不存在，从NodeQueue中删除nodeAddr i ，转步骤1.5.2；1.5.4基于VFG中edge i 的价值流依赖关系，若VFG中的节点node i2 是可疑漏洞崩溃节点，node i1 也是可疑漏洞崩溃节点；将node i1 的地址nodeAddr i 加入NodeQueue的尾部，同时将nodeAddr i 加入到集合SusVar，令I＝I+1，并从NodeQueue中删除nodeAddr i ，转步骤1.5.2；1.5.5此时|NodeQueue|＝0，说明已经完成对可疑漏洞崩溃节点的提取，得到可疑漏洞崩溃节点地址集合SusVar，SusVar＝{nodeAddr 1 ,nodeAddr 2 ,…,nodeAddr m ,…,nodeAddr M }，1≤m≤M，M是可疑漏洞崩溃节点地址总数，M＝I。 4.如权利要求1所述的一种基于数据丰富度与迁移代价感知的漏洞成因定位方法，其特征在于1.7步所述通过GDB调试器的动态调试功能追踪Prog的实际执行路径，在SusVar所包含的所有可疑漏洞崩溃节点地址处设置断点，根据执行过程中断点命中情况筛选出实际参与运行的节点，提取出可疑漏洞崩溃节点集合FlitVar的方法是：1.7.1令可疑漏洞崩溃节点集合FlitVar为空，提取SusVar中的nodeAddr 1 ,nodeAddr 2 ,…,nodeAddr m ,…,nodeAddr M 在VFG中对应的节点中所包含的语句、参数信息，即Prog中node 1 ,node 2 ,…,node m ,…,node M 的位置；1.7.2使用GDB调试器在Prog中设置断点B 1 ,B 2 ,…,B m ,…,B M ，即在Prog的node 1 处设置断点B 1 ，在Prog的node 2 处设置断点B 2 ,…,在Prog的node m 处设置断点B m ,…,在Prog的node M 处设置断点B M ，得到设置了断点的Prog；初始化变量k＝1；1.7.3使用PoC作为输入，在GDB调试器中运行设置了断点的Prog；1.7.4若设置了断点的Prog命中了某个断点，令为B m ，转1.7.5；若Prog没有命中断点，说明已经触发崩溃，令崩溃点处的节点为node crash ，转1.7.6；1.7.5将B m 处的node m 加入集合FiltVar，node m 成为集合FiltVar的第k个元素，代表程序Prog中第k个可疑漏洞崩溃节点node k ，令k＝k+1，转步骤1.7.3，在GDB调试器中继续运行设置了断点的Prog；1.7.6将node crash 加入集合FiltVar，node crash 成为FiltVar的第k个元素node k ；1.7.7得到可疑漏洞崩溃节点集合FiltVar，FiltVar＝{node 1 ,node 2 ,…,node k ,…,node K }。 5.如权利要求1所述的一种基于数据丰富度与迁移代价感知的漏洞成因定位方法，其特征在于2.4步所述对测试用例集合S进行数据丰富度筛选和崩溃判断分类，得到状态转换测试用例集合TransVar的方法是：2.4.1初始化测试用例状态转换最小值Min为+∞，初始化当前测试用例状态转换差值Min’为+∞，初始化记录崩溃测试用例经过漏洞崩溃节点的数量Counts_crash为0，初始化记录非崩溃测试用例经过漏洞崩溃节点的数量Counts_noncrash为0，初始化状态转换测试用例集合TransVar为空，初始化测试用例数据丰富度哈希值集合HashVar为空；初始化崩溃信息记录变量flag为0，初始化测试用例真实状态标签集合Y为空；令变量f＝1，t＝1；2.4.2初始化测试用例数据丰富度value_hash的初始值H 0 ＝0,令经过漏洞崩溃节点的数量Counts的初始值为0，令k＝1；2.4.3将s f 输入到插桩后的目标程序Prog_I中，运行Prog_I，根据运行情况计算s f 的数据丰富度value_hash，方法是：2.4.3.1当Prog_I经过node k 时，获取node k 对应的插桩变量取值X k ，令Counts＝Counts+1；2.4.3.2将H k-1 与X k 进行哈希计算，生成第k个哈希值H k ，即：H k ＝hash(H k-1 ,X k )2.4.3.3令value_hash＝H k ，k＝k+1；2.4.3.4若k>K，说明对s f 的数据丰富度计算完毕，得到最终的value_hash，转2.4.3.5；若k≤K，转2.4.3.1；2.4.3.5测试用例s f 在目标程序Prog_I中执行完毕，若s f 导致Prog_I崩溃记崩溃信息变量flag＝1；若s f 不导致Prog_I崩溃，则记flag＝0；2.4.3.6若value_hash∈HashVar，转2.4.3.6.1，若value_hash不在HashVar中，转2.4.3.6.2.2.4.3.6.1此时value_hash∈HashVar，说明测试用例s f 未增加数据丰富度，即s f 未带来新的程序行为，放弃s f ，令f＝f+1，若f≤F，转2.4.2，对下一个测试用例进行操作；若f>F，转2.4.6；2.4.3.6.2此时value_hash不在HashVar中，判定s i 增加了数据丰富度，转2.4.4；2.4.4若flag＝1,转2.4.4.1；若flag＝0，转2.4.4.22.4.4.1令Counts_crash＝Counts，令当前测试用例状态转换差值Min’＝∣Counts_crash-Counts_noncrash∣，若Min’＜Min，将作为第t个满足数据丰富度增加且迁移代价降低的测试用例s f 存放到状态转换测试用例集合TransVar中，即令s f 成为TransVar中第t个元素TV t ，将value_hash加入到测试用例数据丰富度哈希值集合HashVar中，令y f ＝1，y f ＝1表示s f 会导致Prog_I崩溃，将y f 添加到测试用例真实状态标签集合Y中，令Min＝Min’，令t＝t+1,转2.4.4.3；若Min’≥Min，则放弃s f ，转2.4.4.3；2.4.4.2令Counts_noncrash＝Counts，令Min’＝∣Counts_crash-Counts_noncrash∣，若Min’＜Min，将s f 作为第t个满足数据丰富度增加且迁移代价降低的测试用例存放到集合TransVar中，并将value_hash加入到集合HashVar中，令y f ＝0，y f ＝0表示s f 不会导致Prog_I崩溃，将y f 添加到Y中，令Min＝Min’，令t＝t+1,转2.4.4.3；若Min’≥Min，则放弃s f ，转2.4.4.3；2.4.4.3若f<F，令f＝f+1，转2.4.2对下一个测试用例进行操作；若f≥F，说明得到最终的状态转换测试用例集合TransVar和测试用例真实状态标签集合Y，TransVar＝{TV 1 ,TV 2 ,…,TV t ,…,TV T }，Y＝{y 1 ,y 2 ,…,y t ,…,y T }，结束。 6.如权利要求2所述的一种基于数据丰富度与迁移代价感知的漏洞成因定位方法，其特征在于2.5.3.5步所述判断s f 导致Prog_I崩溃的方法是通过AddressSanitizer回显崩溃信号得知。 7.如权利要求1所述的一种基于数据丰富度与迁移代价感知的漏洞成因定位方法，其特征在于3.2步所述利用互信息算法对Z进行筛选，生成优化并排序后的候选漏洞触发相关节点集合Z’和用于聚类操作的集合VSet的方法是：3.2.1令t＝1，初始化Z’为空，设定漏洞优选阈值θ,0<θ<1；初始化R个漏洞触发相关节点状态集合V 1 ，V 2 ，…,V r ，…,V R 为空，V r 是第r个漏洞触发相关节点状态集合；3.2.2令变量r＝1；3.2.3将TV t 输入到Prog中，使用GDB调试器对prog进行调试并记录候选漏洞触发相关节点z r ，将z r 添加到V r 中；3.2.4令r＝r+1，若r≤R，转3.2.2；若r>R，说明在TV t 作为Prog输入情况下候选漏洞触发相关节点集合Z的状态记录完毕，转3.2.5；3.2.5令t＝t+1，若t≤T，转3.2.2；若t＞T,说明得到了最终的在把TransVar中TV 1 ,TV 2 ,…,TV t ,…,TV T 作为Prog输入情况下的候选漏洞触发相关节点状态集合V 1 ，V 2 ，…,V r ，…,V R ，转3.2.6；3.2.6初始化一个二维特征空数组X，按照下标顺序把V 1 ，V 2 ，…,V r ，…,V R 添加到数组X中，得到X＝[V 1 ，V 2 ，…,V r ，…,V R ]，令MI＝mutual_info_classif(X,Y)mutual_info_classif(X,Y)的功能是计算X和Y的互信息值，得到互信息值集合MI，MI＝{mi 1 ,mi 2 ,…,mi r ,…,mi R }，mi r 为MI中第r个互信息值，用于衡量X中V r 对应的z r 与程序Prog崩溃的相关性，0≤mi r ≤1，mi r 越大,表示z r 与程序Prog崩溃越相关；3.2.7对候选漏洞触发相关节点集合Z进行筛选排序，得到排序后的候选漏洞触发相关节点集合Z’，并生成一个用于聚类操作的集合VSet，VSet＝{V’ 1 ，V’ 2 ，…,V’ p ，…,V’ P }，V’ p 与z’ p 一一对应，是z’ p 对应的候选漏洞触发相关节点状态集合。 8.如权利要求7所述的一种基于数据丰富度与迁移代价感知的漏洞成因定位方法，其特征在于3.2.1步所述漏洞优选阈值θ＝0.5。 9.如权利要求7所述的一种基于数据丰富度与迁移代价感知的漏洞成因定位方法，其特征在于3.2.7步所述对候选漏洞触发相关节点集合Z进行筛选排序，得到排序后的候选漏洞触发相关节点集合Z’，并生成用于聚类操作的集合VSet的方法是：3.2.7.1令变量r＝1，令p＝1；3.2.7.2若mi r ≥θ，说明z r 与程序Prog崩溃足够相关，令z’ p ＝z r ，令V’ p ＝V r ，将z’ p 添加到Z’中，将V’ p 添加到VSet中，令r＝r+1，令p＝p+1，转步骤3.2.7.3；若mi r <θ，直接转步骤3.2.7.3；3.2.7.3若r≤R,转3.2.7.2；若r＞R，说明Z中元素优选完毕，得到Z’＝{z’ 1 ,z’ 2 ,…,z’ p ,…,z’ P }和VSet＝{V’ 1 ，V’ 2 ，…,V’ p ,V’ p+1 ，…,V’ P }，其中P≤R，且z’ p 与V’ p 一一对应；根据Z’内元素z’ p 对应的互信息值mi p 大小，对Z’和VSet内的元素同步排序，互信息值越大，对应的元素下标越小，得到排序后的候选漏洞触发相关节点集合Z’＝{z’ 1 ,z’ 2 ,…,z’ p ,z’ p+1 ,…,z’ P }和VSet＝{V’ 1 ，V’ 2 ，…,V’ p ,V’ p+1 ，…,V’ P }，P≤R，z’ p 是Z’中第p个优化后的候选漏洞触发相关节点，V’ p 是z’ p 对应的漏洞触发相关节点状态集合，z’ p 对应的互信息值>z’ p +1对应的互信息值结束。 10.如权利要求1所述的一种基于数据丰富度与迁移代价感知的漏洞成因定位方法，其特征在于3.3步所述基于集合VSet和候选漏洞触发相关节点集合Z’，采用K-means聚类算法，对TransVar进行聚类，得到漏洞成因位置的排名集合RankingVar的方法是：3.3.1令p＝1；3.3.2基于z’ p 和V’ p ，为TransVar中的TV 1 ,TV 2 ,…,TV t ,…,TV T 分别构造一个特征向量，得到第p个测试用例特征向量集合F p ，F p ＝{f 1 (p) ,f 2 (p) ,…,f t (p) ,…,f T (p) }，f t (p) 是基于TV t 在z’ p 和V’ p 下的状态信息构造的特征向量；设置目标簇数U＝2，以F p 作为输入，通过K-means聚类算法将TransVar中的测试用例划分为两个簇，令为C 1p 和C 2p ，C 1p 表示对z’ p 进行聚类分析得到的崩溃测试用例簇，C 2p 表示对z’ p 进行聚类分析得到的非崩溃测试用例簇；所述状态信息指变量值、执行路径或节点状态；3.3.3利用TransVar中TV 1 ,TV 2 ,…,TV t ,…,TV T 的真实状态标签y 1 ,y 2 ,…,y t ,…,y T 评估聚类结果，对于TV t ，若TV t 被分到C 1p 且y t ＝1，或TV t 被分到C 2p 且y t ＝0，则TV t 分类正确；3.3.4统计TV 1 ,TV 2 ,…,TV t ,…,TV T 中分类正确的元素个数samples p ，计算基于z’ p 和V’ p 构造特征向量的聚类结果的准确率Accuracy p ，Accuracy p ＝(samples p )/T，其中Accuracy p 表示基于z’ p 和V’ p 构造特征向量的聚类结果与真实状态标签的一致性程度；3.3.5令p＝p+1；若p≤P，转3.3.2；若p>P，说明对Z’中的所有z’ p 的聚类分析完毕，得到准确率集合Accuracy，Accuracy＝{Accuracy 1 ,Accuracy 2 ,…,Accuracy p ,…,Accuracy P }，转3.3.6；3.3.6基于Accuracy中各元素的大小从高到低对Z’内的元素进行第二轮排序，第二轮排序后得到漏洞成因位置排名集合RankingVar＝{rank 1 ,rank 2 ,…,rank p ，…rank P }，即若1≤a≤b≤P，则rank a 的准确率Accuracy a ≥rank b 的准确率Accuracy b 。