, 高浩然, 窦伯文, 王夏菁, 胡昌振 北京理工大学 计算机学院, 软件安全工程技术北京市重点实验室, 北京 100081
收稿日期：2018-08-24
基金项目：国家重点研发计划项目（2016QY07X1404）
作者简介：马锐(1972-), 女, 副教授。E-mail:mary@bit.edu.cn
摘要：针对控制流图规模过大导致的程序分析准确度和效率不够理想的问题，该文提出了一种用于控制流图划分的改进GN（Girvan-Newman）算法，在边介数计算中加入点权值作为参数，使划分所得各子图的规模更加平衡；通过动态控制子图的规模，在合适的时机提前终止算法执行，提高执行效率。利用angr工具对二进制程序进行分析所得到的控制流图，分别采用改进GN算法、K-means算法、谱聚类算法和朴素凝聚算法进行实验，比较不同算法对控制流图划分结果中的模块度以及均衡性等指标，证明改进GN算法具有最佳的划分结果和执行效率。
关键词：程序分析控制流图划分聚类GN算法
Control flow graph division based on an improved GN algorithm
MA Rui
, GAO Haoran, DOU Bowen, WANG Xiajing, HU ChangzhenBeijing Key Laboratory of Software Security Engineering Technology, School of Computer Science and Technology, Beijing Institute of Technology, Beijing 100081, China
Abstract: The accuracy and efficiency of program analyses are hindered by very large control flow graphs (CFG). This paper presents an improved GN (Girvan-Newman) algorithm for CFG division. The node weights are added as parameters to the betweenness calculation to better balance the subgraph sizes with the sizes controlled dynamically to terminate the algorithm at a suitable time to improve the execution efficiency. Then, the binary programs indicated by the CFGs are analyzed using the angr tool. The improved GN algorithm, K-means algorithm, spectral clustering algorithm and naive aggregation algorithm were all tested with the results showing the improved GN algorithm provided the best modularity and subgraph size balance.
Key words: program analysiscontrol flow graph divisionclusteringGN algorithm
随着信息安全问题造成的影响愈发严重，各种二进制程序分析技术(如符号执行、污点分析、模糊测试等)越来越受到信息安全领域的关注。而程序控制流分析因其在程序分析和漏洞检测中的重要作用，在各种二进制程序分析技术中都得到了广泛应用[1-3]。然而，目前的各种二进制程序分析技术虽然在理论上有较好的效果，但因为现实世界中的软件及其控制流图的规模往往非常大，所以这些分析技术在实际应用中的准确性和效率都还有待提高。因此，如果能将一个大规模的控制流图用合适的方法划分成若干个较小规模的控制流子图，并对其分别进行分析，然后将分析结果进行逆向合并，得到总体的分析结果，不但能够降低分析过程对计算机软、硬件资源的消耗，而且如果进一步利用并行技术同时对各个子图进行分析，还能节约时间成本，提高分析效率[4-5]。
目前，对控制流图的划分主要有传统的图论和聚类2大类方法。这2类方法都是将控制流图抽象为由节点和有向边组成的网络图，然后用划分算法对其进行操作。为了更好地将划分后的控制流图应用到后续的程序分析和漏洞检测，最好能将控制流图划分为若干个簇，每个元素与同一簇中的元素彼此类似，与其他簇中的元素相异。而聚类能够将多个元素组成的集合重新组合为由类似的元素组成的多个类，具有划分的类结果不可预测和划分过程无监督的特点，能够很好地适用于控制流图的划分。因此，本文将着重研究聚类这一类划分方法。
在现有的漏洞分析的研究中，已有一些基于聚类算法对控制流图进行操作的研究[6-10]，但是这些研究的重点侧重于后续的漏洞检测和分析，而对于使用哪种聚类算法对控制流图进行划分能够得到更好的效果，以及划分过程中对划分效果指标的定义和度量，都缺少详细的研究。
因此，本文对传统GN(Girvan-Newman)算法进行了改进，在边介数的计算中加入了点权值作为参数，使得划分所得各子图的规模更加接近；并且设置了子图规模的阈值，以便在合适的时机提前终止算法执行，提高执行效率。同时利用angr工具对二进制程序分析所得到的程序控制流图，分别用改进GN算法、K-means算法、谱聚类算法和朴素凝聚算法进行了实验，展示了不同算法对控制流图划分的结果，比较了各结果中的模块度以及均衡性等指标，验证了改进的GN算法在控制流图划分中的有效性。
1 方法首先分析控制流图划分遵循的原则，然后详细阐述方法的关键内容，包括控制流图的获取、控制流图的建模和改进的点赋权图GN算法。
1.1 原则控制流图划分是将一个规模较大的控制流图划分为几个较小的子图，该过程的输入是包含基本块信息和跳转信息的二进制程序的控制流图，输出是包含基本块信息的各连通分量以及所切割的边的集合。为了将划分结果用于后续的分析，划分结果需满足以下3个要求：
1) 子图之间的边的数量较少。
对每个子图代表的程序段分别进行分析后，需要对分析结果进行合并，而合并的次数与程序段之间的边的数量成正比。因此，为了提高合并的效率，在划分时要尽量减少各个程序段之间的关联。
2) 子图的规模适度。
对控制流图进行划分的目的之一是可以对各个较小的子图分别进行分析，从而降低分析过程对计算机性能的要求，因此各子图的规模不能过大。而如果子图的规模太小，划分所得的子图数量又会过多，造成合并的开销太大。因此子图的规模要在一个适度的范围内。在本方法中，定义控制流图及基本块的规模为其中指令的数量。
2) 不能遗漏基本块。
控制流图的划分结果要保留原图的所有基本块，不能遗漏某个块，否则会造成后续分析结果的不完整和不准确。
1.2 控制流图的获取本文利用二进制程序分析工具angr获取程序的控制流图[11]，图 1是一个利用angr生成的控制流图(部分)。图中每个圆角矩形表示程序中的一个基本块，其中包含一系列地址连续的指令，基本块的上部标注了该基本块中首条指令的地址、基本块所属的函数以及首条指令相对函数首地址的偏移量。基本块之间用有向边连接，表示基本块之间的跳转关系。其中：实线表示2个基本块之间直接相连，虚线表示在2个基本块的跳转过程中还包含其他基本块。
 |
| 图 1 angr生成的控制流图 |
| 图选项 |
1.3 控制流图的建模本文将控制流图抽象为由节点、点权和有向边构成的网络图。
1) 节点。
程序及其控制流图可划分为指令、基本块、函数/过程/方法、功能/构件等不同粒度，本方法选择基本块作为划分的最小粒度。其原因在于：1)程序基本块中可能包含原语，具有不可分割性，因此不能被划分为更细的粒度；2)由于函数的嵌套调用，用节点表示程序中的函数会导致后续对程序段的分析产生先后顺序，无法同时进行。因此本方法用网络图中的节点表示控制流图中的基本块。
2) 点权。
网络图中节点的权值表示每个基本块中的指令数量，即基本块的规模。如图 1所示，首地址为0x40080b的基本块A中包含6条指令，首地址为0x40082a的基本块B中包含2条指令，因此表示基本块A的节点权值为6，而表示基本块B的节点权值为2。
本文设置节点的权值有两个作用：一是为了减小各子图之间规模的差异，使各子图的规模更平均，具体处理时是通过将权值作为参数添加到边介数的计算，改变切割边的顺序，进而改变划分的结果；二是控制单个子图的规模，具体处理时是通过设置阈值，以提前终止划分的过程。更详细的内容在节1.4中阐述。
3) 有向边。
节点之间的有向边表示一个基本块向另一个基本块或者本基本块首地址的跳转。需要注意的是网络图中将删除意义重复的边，即删除部分重复的由虚线表示的连接关系。
1.4 改进的点赋权图GN算法1.4.1 原始GN算法GN算法属于分层聚类中的分裂算法[12-13]，其基本思想是，任意2个节点之间存在一条或多条最短路径，如果大多数的节点之间的最短路径均包括了某一条边，那么该条边两端节点间的其他路径将相对较少，这2个节点就可以被归入2个社区。GN算法中2个重要的概念是边介数和模块度。
1) 边介数。
边介数指网络图中通过该边的2个节点间最短路径的条数。2个节点间的距离是从起始节点到终止节点所经过的边的数量，最短路径就是2个节点间距离最短的路径。当2点间有p条(p≥1)相同距离的最短路径时，将2点间每条最短路径视为1/p条。
2) 模块度。
模块度Q是衡量社区划分优劣的指标，其含义为：假设在随机图中不存在该社区结构，将实际网络与其相应的随机网络进行比较，如果一个网络与随机网络之间的差异越大，则表示社区结构越明显。其计算公式如下：
| $Q = \sum\limits_{c = 1}^n {\left[{\frac{{{l_c}}}{m}-{{\left( {\frac{{{d_c}}}{{2m}}} \right)}^2}} \right]} .$ | (1) |
3) GN算法的优点和不足。
GN算法主要有四个优点：一是划分结果具有社区内密集、社区间稀疏的特性，适合于节1.1所述第一项需求；二是只删除边不删除节点，满足了节1.1所述第三项需求；三是其采用的模块度度量方法是一种被学术界广泛认可并应用的聚类效果的度量指标；四是其根据边介数来确定移除边的优先级，相对于随机删除边的算法，具有更高的效率。因此，GN算法的思想可以很好地适用于控制流图的划分，每个社区对应一个控制流子图。
但是，由于原始的GN算法并未考虑节点的权值，因此可能造成划分后的各子图规模相差较大；且每次划分都会执行到图中不再有边存在为止，而模块度最大的状态不可能存在于划分后期边数量很少的时候，因此过多的不必要的计算造成了资源的浪费和时间开销的增加。针对以上两个不足，本文对GN算法进行了改进，得到了适合于控制流图划分的点赋权图GN算法。
1.4.2 点赋权图GN算法1) 边介数的计算。
如节1.3所述，设置节点权值有两方面作用，一是平衡子图的大小，二是控制子图划分粒度。因此，在将GN算法应用于控制流图划分时，需将节点权值作为参数之一添加到边介数计算中，具体方法如下。
边介数表示网络图中通过该边的2个节点间最短路径的条数。GN算法的边介数Betweenness计算如下：
| ${\rm{Betweenness}}\left( l \right) = \sum\limits_{s \ne t \in V} {\frac{{{\sigma _{st}}\left( l \right)}}{{{\sigma _{st}}}}} .$ | (2) |
具体到点赋权网络图中边介数的计算，本文在原有边介数计算公式基础上添加节点的权值作为参数，其计算公式如下：
| ${\rm{Betweenness'}}\left( l \right) = \sum\limits_{s \ne t \in V} {\left[{\frac{{{\sigma _{st}}\left( l \right)}}{{{\sigma _{st}}}} \cdot \left( {\omega \left( s \right) + \omega \left( t \right)} \right)} \right]} .$ | (3) |
结合节点权值来计算边介数，可以改变切割边的次序，进而可以改变划分的结果，使得划分后的各子图规模更加平衡。
2) 阈值的设置。
节1.4.1已提及高模块度不可能在控制流图划分后期取得，因此设置阈值可以在合适的时机提前终止划分，从而提高算法的效率。基于此，本文提出设置阈值的概念，目的是控制子图中指令数量的临界值。对于阈值的具体值，本文的方法是选择一个较小的保守值，判断条件为若最大的子图中指令数量小于该值，则终止算法的执行，取此时的最佳状态作为最终的划分结果。通过上述方法设置阈值，可以避免后续无意义的划分，减少时间开销，提高算法的效率。
3) 算法描述。
对原始GN算法按上述方法进行改进后，本文提出的点赋权图GN算法的执行步骤如下：
步骤1??计算图G的边数m、各节点的度dv(v∈V)。
步骤2??判断子图中指令数量的最大值是否小于所设置的阈值，若结果为真，则返回，此时为最佳划分方案；若结果为假，则继续步骤3。
步骤3??计算各边的边介数Betweenness′。
步骤4??移除边介数最大的边，并将其加入移除的边的列表。
步骤5??计算当前状态的模块度Q。
步骤6??比较当前Q与最大模块度Qmax的值，若Q>Qmax，则令Qmax的值为Q，保存此时的状态为Gmax，保存此时的割边集合，然后继续步骤7；若Q < Qmax，则跳转到步骤7。
步骤7??遍历每个子图，计算各子图内各节点的权值之和，并找出各权值之和的最大值，跳转到步骤2。
2 实验2.1 实验设计2.1.1 实验目的针对改进后的点赋权图GN算法采用控制流图实例进行测试，并与其他3种算法的划分结果进行比较，以验证本文所提出的方法的正确性与有效性。由于控制流图划分的时间远小于后续程序分析时间，因此，本文不对时间性能进行度量，对于划分结果，主要通过两方面进行度量：一是通过模块度Q进行衡量，Q值越大，划分结果越好；二是通过节1.1中所述的3个需求进行衡量。
2.1.2 实验环境实验环境为ubuntu17.04系统，开发语言为python2.7，开发工具为PyCharm2017.2.3；测试用例是C语言代码编译生成的二进制文件，及angr对其处理生成的控制流图。
本实验选取了4个具有不同控制流结构和不同控制流图规模的二进制程序作为测试用例，尽量覆盖各种基本的控制流结构以及不同大小的控制流图，如表 1所示。
表 1 二进制程序测试用例
| 实验序号 | 测试程序 | 基本块数量 | 控制流特点 |
| 1 | fauxware | 18 | 分支结构 |
| 2 | strcpy_test | 24 | 循环结构 |
| 3 | nobranch | 275 | 顺序结构 |
| 4 | angrybird | 3 083 | 分支和循环结构 |
表选项
2.2 实验结果与分析本节对4个二进制程序分别用不同的算法进行了实验，并对结果进行了比较和分析。
2.2.1 实验1选取的第1个二进制程序是fauxware，其控制流图有18个基本块，且包含分支结构，实验结果如图 2—5及表 2所示。
 |
| 图 2 改进GN算法(实验1) |
| 图选项 |
 |
| 图 3 K-means算法(实验1) |
| 图选项 |
 |
| 图 4 谱聚类算法(实验1) |
| 图选项 |
 |
| 图 5 朴素凝聚算法(实验1) |
| 图选项 |
表 2 各算法划分结果汇总(实验1)
| 算法名称 | 模块度 | 各子图规模 | 切割边数 |
| 改进GN | 0.56 | 27、25、24 | 3 |
| K-means | 0.32 | 38、21、11 | 4 |
| 谱聚类 | 0.55 | 40、16、14 | 3 |
| 朴素凝聚 | 0.55 | 40、16、14 | 3 |
表选项
改进的GN算法将原图划分为3个子图，分别包含3、8、7个基本块，规模分别为27、25、24，切割边的数量为3。可以看到，虽然各子图基本块数量相差较大，但各子图的总规模比较接近，符合划分的需求；划分结果的模块度Q=0.56，是一个相当理想的值。
令参数k=3，使K-means算法也将原图划分为3个子图，分别包含6、7、5个基本块，规模分别为38、21、11。可以看到，虽然各子图的基本块数量较为接近，但总规模相当不均衡；划分结果的模块度Q=0.32，远小于改进的GN算法的Q值。另外，由于初始点的随机性，可能出现局部最优的情况，模块度、子图规模等指标均不如当前实验结果，使算法性能更差。
谱聚类算法与朴素凝聚算法得到了相同的结果，模块度Q=0.55，切割边的数量为3，与改进的GN算法相接近。然而，各子图的规模为40、16、14，相差较大。
综合分析，主要是后3种算法没有考虑节点权重，因此子图间的平衡性较差。
2.2.2 实验2选取的第2个二进制程序是strcpy_test，其控制流图有24个基本块，且包含循环结构。实验结果如表 3所示。
表 3 各算法划分结果汇总(实验2)
| 算法名称 | 模块度 | 各子图规模 | 切割边数 |
| 改进GN | 0.57 | 24、21、20、28 | 4 |
| K-means | 0.27 | 28、25、31、9 | 6 |
| 谱聚类 | 0.31 | 14、31、29、19 | 5 |
| 朴素凝聚 | 0.26 | 7、29、25、31、1 | 8 |
表选项
通过对模块度、子图规模、切割边数等指标的分析比较可以看出，改进的GN算法的性能最好，K-means算法的模块度较小，子图规模相差较大；谱聚类算法略优于K-means，但仍不如改进的GN算法；而朴素凝聚算法的各项指标都较差，总体性能最差。
2.2.3 实验3选取的第3个二进制程序是nobranch，其控制流图有275个基本块，且基本不包含分支和循环结构，可以当作顺序结构处理。实验结果如表 4所示。
表 4 各算法划分结果汇总(实验3)
| 算法名称 | 模块度 | 各子图规模 | 子图数量 |
| 改进GN | 0.88 | 1 683、1 683、1 683、1 782、1 683、1 592、1 683、1 683、1 683、1 683、1 683、1 683、1 683、1 782、1 683、1 683 | 16 |
| K-means | 0.46 | 1 980、1 584、2 376、1 097、1 188、1 881、1 881、1 584、1 386、2 178、2 277、2 079、1 782、1 386、1 287、1 089 | 16 |
| 谱聚类 | 0.31 | 1 782、1 782、1 881、1 196、1 683、1 683、1 782、1 782、1 683、1 683、1 683、1 782、1 782、1 782、1 782、1 287 | 16 |
| 朴素凝聚 | 0.26 | 1 782、1 584、2 178、1 881、1 881、1 881、1 980、2 178、1 287、1 782、2 376、1 188、1 089、1 584、1 485、891 | 16 |
表选项
改进的GN算法将原图划分为16个子图，各子图规模如表 4所示，模块度Q=0.88。可以看到，划分结果的模块度较高，且各子图的规模相当平衡。K-means算法的模块度Q=0.46，其值较小，且子图规模的平衡性较差。谱聚类算法的模块度Q=0.31，各子图规模比较均衡，划分结果尚可。朴素凝聚算法的模块度Q=0.26，子图规模平衡性较差，划分结果最差。
2.2.4 实验4选取的第4个二进制程序是angrybird，其控制流图有3 083个基本块，且包含大量分支及循环结构。实验结果如表 5所示。
表 5 各算法划分结果汇总(实验4)
| 算法名称 | 模块度 | 子图数量 | 切割边数 |
| 改进GN | 0.93 | 39 | 38 |
| K-means | 0.48 | 39 | 38 |
| 谱聚类 | 0.48 | 38 | 37 |
| 朴素凝聚 | 0.47 | 50 | 49 |
表选项
结果中的各子图规模分别为：
改进GN算法：{112, 170, 190, 137, 123, 151, 94, 129, 156, 179, 146, 114, 143, 105, 98, 111, 110, 106, 163, 99, 86, 101, 138, 105, 117, 133, 196, 110, 130, 97, 180, 115, 107, 159, 115, 148, 132, 87, 132}；
K-means算法：{103, 106, 212, 96, 115, 128, 141, 58, 166, 117, 201, 136, 148, 118, 134, 160, 105, 133, 122, 115, 159, 101, 66, 203, 67, 64, 160, 136, 176, 97, 175, 182, 129, 142, 152, 110, 114, 114, 63}；
谱聚类算法：{181, 137, 122, 138, 83, 135, 133, 120, 130, 122, 136, 149, 135, 171, 129, 123, 127, 106, 145, 132, 113, 162, 112, 148, 135, 95, 176, 103, 99, 113, 172, 138, 132, 142, 106, 130, 158, 139}；
朴素凝聚算法：{125, 98, 131, 187, 158, 90, 204, 129, 218, 141, 196, 174, 148, 115, 154, 164, 105, 124, 84, 127, 133, 125, 127, 149, 114, 163, 192, 134, 97, 89, 126, 139, 104, 4, 4, 118, 151, 139, 4, 4, 4, 2, 4, 4, 2, 4, 4, 4, 4, 4}。
比较各个指标可以得到结论，仍然是改进GN算法的划分效果最好。
2.2.5 小结在实验中所使用的二进制程序包含了顺序、分支、循环等多种程序控制流结构，其控制流图的基本块数量的范围在10~3 000之间，覆盖范围也较大。因此，实验的结果具有较大的可信度和普遍性。另一方面，通过对模块度、各子图规模的平衡性、切割边的数量等指标以及节1.1中所述3条原则的比较可以看出，对于以上4个不同规模、不同控制流结构的控制流图，改进GN算法的划分结果明显优于其他3种算法的划分结果；谱聚类算法的划分结果次之；K-means算法的划分结果相比于谱聚类算法的结果稍差，尤其是各子图的规模有显著的差距，而且K-means算法的局部最优问题会导致控制流图划分结果不可控；而朴素凝聚算法在各项度量指标上的表现都比较差，总体划分结果最差。
3 结论在对具有不同特点的二进制程序的控制流图进行划分，并对结果进行分析比较后，可以看到：1)对于多种常见的程序类型，对其控制流图进行划分是可行的；2)在多种算法中，本文所提出的点赋权图GN算法的性能最好。
本文所提出的控制流图划分方法——改进的点赋权图GN算法具有较好的划分效果和较高的执行效率，且能适用于具有不同控制流结构和不同规模的控制流图，可以用于符号执行、模糊测试、污点分析等多种流行的二进制程序分析技术。
参考文献
| [1] | CASELDEN D, BAZHANYUK A, PAYER M, et al. Transformation-aware exploit generation using a HI-CFG: UCB/EECS-2013-85[R]. Berkeley, USA: University of California, 2013. |
| [2] | QIU J, SU X H, MA P J. Identifying functions in binary code with reverse extended control flow graphs[J]. Journal of Software:Evolution and Process, 2015, 27(10): 793-820. DOI:10.1002/smr.v27.10 |
| [3] | NGUYEN M H, NGUYEN D L, NGUYEN X M, et al. Auto-detection of sophisticated malware using lazy-binding control flow graph and deep learning[J]. Computers & Security, 2018, 76: 128-155. |
| [4] | WEI L. Segmented symbolic analysis[C]//Proceedings of the 35th International Conference on Software Engineering. San Francisco, USA: IEEE, 2013: 212-221. |
| [5] | 颜婷.分段式分析方法在动态符号执行中的应用[D].上海: 华东师范大学, 2015. YAN T. Dynamic symbolic execution with segmented analysis[D]. Shanghai: East China Normal University, 2015. (in Chinese) |
| [6] | RODRIGUEZ A, LAIO A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191): 1492-1496. DOI:10.1126/science.1242072 |
| [7] | KARGER D R. Global min-cuts in RNC, and other ramifications of a simple min-out algorithm[C]//Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms. Austin, USA: ACM, 1993: 21-30. |
| [8] | BOYKOV Y, KOLMOGOROV V. An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(9): 1124-1137. DOI:10.1109/TPAMI.2004.60 |
| [9] | YU S X, SHI J B. Multiclass spectral clustering[C]//Proceedings of the 9th IEEE International Conference on Computer Vision. Nice, France: IEEE, 2003: 313. |
| [10] | GREGORY S. Finding overlapping communities in networks by label propagation[J]. New Journal of Physics, 2009, 12(10): 103018. |
| [11] | SHOSHITAISHVILI Y, WANG R Y, SALLS C, et al. SOK: (state of) the art of war: Offensive techniques in binary analysis[C]//Proceedings of the 37th IEEE Symposium on Security and Privacy. San Jose, USA: IEEE, 2016: 138-157. |
| [12] | NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks[J]. Physical Review E, 2004, 69(2): 026113. DOI:10.1103/PhysRevE.69.026113 |
| [13] | NEWMAN M E. Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004, 69(6 Pt 2): 066133. |
