Pearl: A Multi-Derivation Approach to Efficient CFL-Reachability Solving

doi:10.1109/TSE.2024.3437684

	Pearl: A Multi-Derivation Approach to Efficient CFL-Reachability Solving
	Shi, Chenghang 1,2; Li, Haofeng 1; Sui, Yulei 3; Lu, Jie 1; Li, Lian 1,2,4; Xue, Jingling 3
	2024-09-01
发表期刊	IEEE TRANSACTIONS ON SOFTWARE ENGINEERING
ISSN	0098-5589
卷号	50 期号:9 页码:2379-2397
摘要	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.
关键词	Production Standards Termination of employment Redundancy Optimization Heuristic algorithms Symbols Program analysis CFL-reachability constraint solving transitive relations
DOI	10.1109/TSE.2024.3437684
收录类别	SCI
语种	英语
资助项目	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类目	Computer Science, Software Engineering ; Engineering, Electrical & Electronic
WOS记录号	WOS:001315784800007
出版者	IEEE COMPUTER SOC
引用统计	被引频次：2[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/39582
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Li, Haofeng; Li, Lian
作者单位	1.Chinese Acad Sci, Inst Comp Technol, SKLP, Beijing 100190, Peoples R China 2.Univ Chinese Acad Sci, Beijing 100190, Peoples R China 3.Univ New South Wales, Sydney, NSW 2052, Australia 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.