38
views
0
recommends
+1 Recommend
1 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Control flow graph division based on an improved GN algorithm

      research-article

      Read this article at

      ScienceOpenPublisher
      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          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.

          Abstract

          摘要 针对控制流图规模过大导致的程序分析准确度和效率不够理想的问题, 该文提出了一种用于控制流图划分的改进GN (Girvan-Newman) 算法, 在边介数计算中加入点权值作为参数, 使划分所得各子图的规模更加平衡; 通过动态控制子图的规模, 在合适的时机提前终止算法执行, 提高执行效率。利用angr工具对二进制程序进行分析所得到的控制流图, 分别采用改进GN算法、 K-means算法、谱聚类算法和朴素凝聚算法进行实验, 比较不同算法对控制流图划分结果中的模块度以及均衡性等指标, 证明改进GN算法具有最佳的划分结果和执行效率。

          Related collections

          Author and article information

          Journal
          J Tsinghua Univ (Sci & Technol)
          Journal of Tsinghua University (Science and Technology)
          Tsinghua University Press
          1000-0054
          15 January 2019
          16 January 2019
          : 59
          : 1
          : 15-22
          Affiliations
          [1] 1Beijing Key Laboratory of Software Security Engineering Technology, School of Computer Science and Technology, Beijing Institute of Technology, Beijing 100081, China
          Article
          j.cnki.qhdxxb.2018.26.053
          10.16511/j.cnki.qhdxxb.2018.26.053
          71ac1d49-ed1d-4cea-b8ab-e2b26cb0246e
          Copyright © Journal of Tsinghua University

          This is an open-access article distributed under the terms of the Creative Commons Attribution 4.0 Unported License (CC BY-NC 4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited. See https://creativecommons.org/licenses/by-nc/4.0/.


          Software engineering,Data structures & Algorithms,Applied computer science,Computer science,Artificial intelligence,Hardware architecture
          clustering,control flow graph division,program analysis,GN algorithm

          Comments

          Comment on this article