Please wait a minute...
 首页  期刊介绍 期刊订阅 联系我们 横山亮次奖 百年刊庆
 
最新录用  |  预出版  |  当期目录  |  过刊浏览  |  阅读排行  |  下载排行  |  引用排行  |  横山亮次奖  |  百年刊庆
清华大学学报(自然科学版)  2019, Vol. 59 Issue (1): 15-22    DOI: 10.16511/j.cnki.qhdxxb.2018.26.053
  信息安全 本期目录 | 过刊浏览 | 高级检索 |
基于改进GN算法的程序控制流图划分方法
马锐, 高浩然, 窦伯文, 王夏菁, 胡昌振
北京理工大学 计算机学院, 软件安全工程技术北京市重点实验室, 北京 100081
Control flow graph division based on an improved GN algorithm
MA Rui, GAO Haoran, DOU Bowen, WANG Xiajing, HU Changzhen
Beijing Key Laboratory of Software Security Engineering Technology, School of Computer Science and Technology, Beijing Institute of Technology, Beijing 100081, China
全文: PDF(1167 KB)  
输出: BibTeX | EndNote (RIS)      
摘要 针对控制流图规模过大导致的程序分析准确度和效率不够理想的问题,该文提出了一种用于控制流图划分的改进GN(Girvan-Newman)算法,在边介数计算中加入点权值作为参数,使划分所得各子图的规模更加平衡;通过动态控制子图的规模,在合适的时机提前终止算法执行,提高执行效率。利用angr工具对二进制程序进行分析所得到的控制流图,分别采用改进GN算法、K-means算法、谱聚类算法和朴素凝聚算法进行实验,比较不同算法对控制流图划分结果中的模块度以及均衡性等指标,证明改进GN算法具有最佳的划分结果和执行效率。
服务
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章
马锐
高浩然
窦伯文
王夏菁
胡昌振
关键词 程序分析控制流图划分聚类GN算法    
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 wordsprogram analysis    control flow graph division    clustering    GN algorithm
收稿日期: 2018-08-24      出版日期: 2019-01-16
基金资助:国家重点研发计划项目(2016QY07X1404)
引用本文:   
马锐, 高浩然, 窦伯文, 王夏菁, 胡昌振. 基于改进GN算法的程序控制流图划分方法[J]. 清华大学学报(自然科学版), 2019, 59(1): 15-22.
MA Rui, GAO Haoran, DOU Bowen, WANG Xiajing, HU Changzhen. Control flow graph division based on an improved GN algorithm. Journal of Tsinghua University(Science and Technology), 2019, 59(1): 15-22.
链接本文:  
http://jst.tsinghuajournals.com/CN/10.16511/j.cnki.qhdxxb.2018.26.053  或          http://jst.tsinghuajournals.com/CN/Y2019/V59/I1/15
  图1 angr生成的控制流图
  表1 二进制程序测试用例
  图2 改进 GN 算法(实验1)
  图3 K-means算法(实验1)
  图4 谱聚类算法(实验1)
  图5 朴素凝聚算法(实验1)
  表2 各算法划分结果汇总(实验1)
  表3 各算法划分结果汇总(实验2)
  表4 各算法划分结果汇总(实验3)
  表5 各算法划分结果汇总(实验4)
[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.
[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.
[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.
[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.
[13] NEWMAN M E. Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004, 69(6 Pt 2), 066133.
[1] 索明亮, 周鼎, 安若铭, 李顺利. 邻域密度网格聚类算法及应用[J]. 清华大学学报(自然科学版), 2018, 58(8): 732-739.
[2] 许福, 杨湛宇, 陈志泊, 孙钰, 张海燕. 开源代码仓库增量分析方法[J]. 清华大学学报(自然科学版), 2018, 58(7): 630-638.
[3] 陈晓方, 钱荧灿, 王雅琳, 阳春华. 基于主元导数特征聚类的加氢裂化动态调整区间识别[J]. 清华大学学报(自然科学版), 2018, 58(1): 81-86.
[4] 肖熙, 周路. 基于k均值和基于归一化类内方差的语音识别自适应聚类特征提取算法[J]. 清华大学学报(自然科学版), 2017, 57(8): 857-861.
[5] 韩东红, 宋明, 张宏亮, 王佳茜, 王嘉兴, 王国仁. 基于密度的不确定数据流聚类算法[J]. 清华大学学报(自然科学版), 2017, 57(8): 884-891.
[6] 裴继升, 叶晓俊. 基于语法推导的溯源依赖关系路径模式挖掘算法[J]. 清华大学学报(自然科学版), 2017, 57(6): 561-568.
[7] 方勇, 刘道胜, 黄诚. 基于层次聚类的虚假用户检测[J]. 清华大学学报(自然科学版), 2017, 57(6): 620-624.
[8] 刘书明, 吴以朋, 王晓婷, 刘友飞, 李佳杰. 应用聚类算法识别供水管网爆管事故[J]. 清华大学学报(自然科学版), 2017, 57(10): 1096-1101.
[9] 李煦, 屠明, 吴超, 国雁萌, 纳跃跃, 付强, 颜永红. 基于NMF和FCRF的单通道语音分离[J]. 清华大学学报(自然科学版), 2017, 57(1): 84-88.
[10] 刘杰, 王生进. 融合聚类与排序的图像显著区域检测[J]. 清华大学学报(自然科学版), 2016, 56(9): 913-919.
[11] 王志如, 苏国锋, 梁作论. 基于信息传递效率的地铁网络小世界特性评价[J]. 清华大学学报(自然科学版), 2016, 56(4): 411-416.
[12] 郭武, 马啸空. 复杂噪声场景下的活动语音检测方法[J]. 清华大学学报(自然科学版), 2016, 56(11): 1190-1195.
[13] 陈元琳, 柴跃廷, 刘义, 徐扬. 基于群体偏好的交易评价可信度[J]. 清华大学学报(自然科学版), 2015, 55(5): 558-564,571.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
版权所有 © 《清华大学学报(自然科学版)》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持:support@magtech.com.cn