基于改进GN算法的程序控制流图划分方法

Rui Ma; Haoran Gao; Bowen Dou; Xiajing Wang; Changzhen Hu

doi:10.16511/j.cnki.qhdxxb.2018.26.053

基于改进GN算法的程序控制流图划分方法

Translated title of the contribution: Control flow graph division based on an improved GN algorithm

Rui Ma, Haoran Gao, Bowen Dou, Xiajing Wang, Changzhen Hu

Beijing Institute of Technology

Research output: Contribution to journal › Article › peer-review

4 Citations (Scopus)

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.

Translated title of the contribution	Control flow graph division based on an improved GN algorithm
Original language	Chinese (Traditional)
Pages (from-to)	15-22
Number of pages	8
Journal	Qinghua Daxue Xuebao/Journal of Tsinghua University
Volume	59
Issue number	1
DOIs	https://doi.org/10.16511/j.cnki.qhdxxb.2018.26.053
Publication status	Published - 1 Jan 2019

Access to Document

10.16511/j.cnki.qhdxxb.2018.26.053

Cite this

@article{93bad690dcb043ff9b3fe277703a3a13,

title = "基于改进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.",

keywords = "Clustering, Control flow graph division, GN algorithm, Program analysis",

author = "Rui Ma and Haoran Gao and Bowen Dou and Xiajing Wang and Changzhen Hu",

year = "2019",

month = jan,

day = "1",

doi = "10.16511/j.cnki.qhdxxb.2018.26.053",

language = "繁体中文",

volume = "59",

pages = "15--22",

journal = "Qinghua Daxue Xuebao/Journal of Tsinghua University",

issn = "1000-0054",

publisher = "Tsinghua University Press",

number = "1",

}

TY - JOUR

T1 - 基于改进GN算法的程序控制流图划分方法

AU - Ma, Rui

AU - Gao, Haoran

AU - Dou, Bowen

AU - Wang, Xiajing

AU - Hu, Changzhen

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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.

AB - 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.

KW - Clustering

KW - Control flow graph division

KW - GN algorithm

KW - Program analysis

UR - http://www.scopus.com/inward/record.url?scp=85064757469&partnerID=8YFLogxK

U2 - 10.16511/j.cnki.qhdxxb.2018.26.053

DO - 10.16511/j.cnki.qhdxxb.2018.26.053

M3 - 文章

AN - SCOPUS:85064757469

SN - 1000-0054

VL - 59

SP - 15

EP - 22

JO - Qinghua Daxue Xuebao/Journal of Tsinghua University

JF - Qinghua Daxue Xuebao/Journal of Tsinghua University

IS - 1

ER -

基于改进GN算法的程序控制流图划分方法

Abstract

Access to Document

Other files and links

Fingerprint

Cite this