中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 计算技术研究所
  3. 中国科学院计算技术研究所
  4. 中国科学院计算技术研究所期刊论文
  5. 英文
Pearl: A Multi-Derivation Approach to Efficient CFL-Reachability Solving

文献类型：期刊论文

作者Shi, Chenghang2,3; Li, Haofeng2; Sui, Yulei1; Lu, Jie2; Li, Lian2,3,4; Xue, Jingling1
刊名IEEE TRANSACTIONS ON SOFTWARE ENGINEERING
出版日期2024-09-01
卷号50期号:9页码:2379-2397
关键词Production Standards Termination of employment Redundancy Optimization Heuristic algorithms Symbols Program analysis CFL-reachability constraint solving transitive relations
ISSN号0098-5589
DOI10.1109/TSE.2024.3437684
英文摘要Context-free language (CFL) reachability is a fundamental framework for formulating program analyses. CFL-reachability analysis works on top of an edge-labeled graph by deriving reachability relations and adding them as labeled edges to the graph. Existing CFL-reachability algorithms typically adopt a single-reachability relation derivation (SRD) strategy, i.e., one reachability relation is derived at a time. Unfortunately, this strategy can lead to redundancy, hindering the efficiency of the analysis. To address this problem, this paper proposes Pearl, a multi-derivation approach that reduces derivation redundancy for CFL-reachability solving, which significantly improves the efficiency of CFL-reachability analysis. Our key insight is that multiple edges can be simultaneously derived via batch propagation of reachability relations. We also tailor our multi-derivation approach to tackle transitive relations that frequently arise when solving CFL-reachability. Specifically, we present a highly efficient transitive-aware variant, Pearl(PG), which enhances Pearl with propagation graphs, a lightweight but effective graph representation, to further diminish redundant derivations. We evaluate the performance of our approach on two clients, i.e., context-sensitive value-flow analysis and field-sensitive alias analysis for C/C++. By eliminating a large amount of redundancy, our approach outperforms two baselines including the standard CFL-reachability algorithm and a state-of-the-art solver Pocr specialized for fast transitivity solving. In particular, the empirical results demonstrate that, for value-flow analysis and alias analysis respectively, Pearl(PG) runs 3.09$\times$x faster on average (up to 4.44x) and 2.25$\times$x faster on average (up to 3.31x) than Pocr, while also consuming less memory.
资助项目National Key R&D Program of China[2022YFB3103900] ; National Natural Science Foundation of China (NSFC)[62132020] ; National Natural Science Foundation of China (NSFC)[62202452] ; China Postdoctoral Science Foundation[2024M753295]
WOS研究方向Computer Science ; Engineering
语种英语
WOS记录号WOS:001315784800007
出版者IEEE COMPUTER SOC
源URL[http://119.78.100.204/handle/2XEOYT63/39581]  
专题中国科学院计算技术研究所期刊论文_英文
通讯作者Li, Haofeng; Li, Lian
作者单位1.Univ New South Wales, Sydney, NSW 2052, Australia
2.Chinese Acad Sci, Inst Comp Technol, SKLP, Beijing 100190, Peoples R China
3.Univ Chinese Acad Sci, Beijing 100190, Peoples R China
4.Zhongguancun Lab, Beijing 100194, Peoples R China
推荐引用方式
GB/T 7714		 Shi, Chenghang,Li, Haofeng,Sui, Yulei,et al. Pearl: A Multi-Derivation Approach to Efficient CFL-Reachability Solving[J]. IEEE TRANSACTIONS ON SOFTWARE ENGINEERING,2024,50(9):2379-2397.
APA Shi, Chenghang,Li, Haofeng,Sui, Yulei,Lu, Jie,Li, Lian,&Xue, Jingling.(2024).Pearl: A Multi-Derivation Approach to Efficient CFL-Reachability Solving.IEEE TRANSACTIONS ON SOFTWARE ENGINEERING,50(9),2379-2397.
MLA Shi, Chenghang,et al."Pearl: A Multi-Derivation Approach to Efficient CFL-Reachability Solving".IEEE TRANSACTIONS ON SOFTWARE ENGINEERING 50.9(2024):2379-2397.

入库方式： OAI收割

来源：计算技术研究所

浏览0
下载0
收藏0
其他版本

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。