Control flow graph division based on an improved GN algorithm

doi:10.16511/j.cnki.qhdxxb.2018.26.053

Abstract
Figures/Tables
References
Related Articles
Metrics

Download: PDF(1167 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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.

Keywords program analysis control flow graph division clustering GN algorithm

Issue Date: 16 January 2019

	Service

	E-mail this article
	E-mail Alert
	RSS
	Articles by authors

	MA Rui
	GAO Haoran
	DOU Bowen
	WANG Xiajing
	HU Changzhen

Cite this article:

MA Rui,GAO Haoran,DOU Bowen, et al. Control flow graph division based on an improved GN algorithm[J]. Journal of Tsinghua University(Science and Technology), 2019, 59(1): 15-22.

URL:

http://jst.tsinghuajournals.com/EN/10.16511/j.cnki.qhdxxb.2018.26.053 OR http://jst.tsinghuajournals.com/EN/Y2019/V59/I1/15

[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]	ZHAO Xingwang, HOU Zhedong, YAO Kaixuan, LIANG Jiye. Two-stage fusion multiview graph clustering based on the attention mechanism[J]. Journal of Tsinghua University(Science and Technology), 2024, 64(1): 1-12.
[2]	WANG Liping, SHI Huijie, WANG Dong. Clustering and selection method of microservices for intelligent manufacturing[J]. Journal of Tsinghua University(Science and Technology), 2024, 64(1): 109-116.
[3]	DU Yuji, FU Ming, DUANMU Weike, HOU Longfei, LI Jing. Risk assessment method of gas pipeline networks based on fuzzy analytic hierarchy process and improved coefficient of variation[J]. Journal of Tsinghua University(Science and Technology), 2023, 63(6): 941-950.
[4]	LI Congjian, GAO Hang, LIU Yi. Fast reconstruction of a wind field based on numerical simulation and machine learning[J]. Journal of Tsinghua University(Science and Technology), 2023, 63(6): 882-887.
[5]	SUN Haobo, YANG Kaiming, ZHU Yu, LU Sen. Modal parameter estimates for a magnetic levitation planar motor based on density clustering[J]. Journal of Tsinghua University(Science and Technology), 2023, 63(1): 33-43.
[6]	YU Yong, WANG Yinggang, LUO Zhengguo, YANG Yan, WANG Xinkai, GAO Tao, YU Qian. Link prediction algorithm based on clustering coefficient and node centrality[J]. Journal of Tsinghua University(Science and Technology), 2022, 62(1): 98-104.
[7]	XIAO Xi, XU Chen. Speech feature fusion algorithm based on acoustic state likelihood and supervised state modelling[J]. Journal of Tsinghua University(Science and Technology), 2019, 59(6): 476-481.
[8]	ZHANG Jiwen, SONG Libin, XU Junjie, SHI Xunlei, LIU Li. Unpredefined ball detection algorithm for humanoid soccer robots[J]. Journal of Tsinghua University(Science and Technology), 2019, 59(4): 298-305.
[9]	LUO Xinyuan, CHEN Xin, SHOU Lidan, CHEN Ke, WU Yanjing. Semantic trajectory extraction framework for indoor space[J]. Journal of Tsinghua University(Science and Technology), 2019, 59(3): 186-193.
[10]	LI Zihao, TIAN Xiangliang, LI Zhongwen, ZHOU Wei, ZHOU Zhijie, ZHONG Maohua. Risk analysis of metro station passenger flow based on passenger flow patterns[J]. Journal of Tsinghua University(Science and Technology), 2019, 59(10): 854-860.
[11]	SUO Mingliang, ZHOU Ding, AN Ruoming, LI Shunli. Neighborhood density grid clustering and its applications[J]. Journal of Tsinghua University(Science and Technology), 2018, 58(8): 732-739.
[12]	XU Fu, YANG Zhanyu, CHEN Zhibo, SUN Yu, ZHANG Haiyan. Incremental analysis of open source repositories[J]. Journal of Tsinghua University(Science and Technology), 2018, 58(7): 630-638.
[13]	CHEN Xiaofang, QIAN Yingcan, WANG Yalin, YANG Chunhua. Dynamic adjustment interval identification of hydrocracking based on principal component derivative feature clustering[J]. Journal of Tsinghua University(Science and Technology), 2018, 58(1): 81-86.
[14]	XIAO Xi, ZHOU Lu. Speech recognition adaptive clustering feature extraction algorithms based on the k-means algorithm and the normalized intra-class variance[J]. Journal of Tsinghua University(Science and Technology), 2017, 57(8): 857-861.
[15]	HAN Donghong, SONG Ming, ZHANG Hongliang, WANG Jiaxi, WANG Jiaxing, WANG Guoren. Algorithm for clustering uncertain data streams based on density[J]. Journal of Tsinghua University(Science and Technology), 2017, 57(8): 884-891.

Viewed

Full text

Abstract

Cited

Shared

Discussed