Two Birds with One Stone: Multi-Derivation for Fast Context-Free Language Reachability Analysis

Shi, C; Li, H; Sui, Y; Lu, J; Li, L; Xue, J

Two Birds with One Stone: Multi-Derivation for Fast Context-Free Language Reachability Analysis

Shi, C Li, H Sui, Y

Lu, J Li, L Xue, J

Permalink

Publisher:: IEEE
Publication Type:: Conference Proceeding
Citation:: 2023 38th IEEE/ACM International Conference on Automated Software Engineering (ASE), 2023, 00, pp. 624-636
Issue Date:: 2023-11-08

Closed Access

	Filename	Description	Size
	Two_Birds_with_One_Stone_Multi-Derivation_for_Fast_Context-Free_Language_Reachability_Analysis.pdf	Published version	245.81 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Shi, C
dc.contributor.author	Li, H
dc.contributor.author	Sui, Y https://orcid.org/0000-0002-9510-6574
dc.contributor.author	Lu, J
dc.contributor.author	Li, L
dc.contributor.author	Xue, J
dc.date	2023-09-11
dc.date.accessioned	2024-06-27T02:55:31Z
dc.date.available	2024-06-27T02:55:31Z
dc.date.issued	2023-11-08
dc.identifier.citation	2023 38th IEEE/ACM International Conference on Automated Software Engineering (ASE), 2023, 00, pp. 624-636
dc.identifier.isbn	979-8-3503-2997-1
dc.identifier.issn	1938-4300
dc.identifier.uri	http://hdl.handle.net/10453/179665
dc.description.abstract	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 transitive relations that frequently arise when solving reachability relations significantly improving the efficiency of CFL reachability analysis Our key insight is that multiple edges involving transitivity can be simultaneously derived via batch propagation of reachability relations on the transitivity aware subgraphs that are induced from the original edge labeled graph We evaluate the performance of Pearl 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 Pearl achieves average speedups of 82 73x for value flow analysis and 155 26x for alias analysis over the standard CFL reachability algorithm The comparison with Pocr a state of the art CFL reachability solver shows that Pearl runs 10 1x up to 29 2x and 2 37x up to 4 22x faster on average respectively for value flow analysis and alias analysis with less consumed memory
dc.language	en
dc.publisher	IEEE
dc.relation.ispartof	2023 38th IEEE/ACM International Conference on Automated Software Engineering (ASE)
dc.relation.ispartof	IEEE/ACM International Conference on Automated Software Engineering
dc.relation.isbasedon	10.1109/ase56229.2023.00118
dc.rights	info:eu-repo/semantics/closedAccess
dc.title	Two Birds with One Stone: Multi-Derivation for Fast Context-Free Language Reachability Analysis
dc.type	Conference Proceeding
utslib.citation.volume	00
utslib.location.activity	Luxembourg, Luxembourg
pubs.organisational-group	University of Technology Sydney
pubs.organisational-group	University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	University of Technology Sydney/Strength - AAII - Australian Artificial Intelligence Institute
utslib.copyright.status	closed_access	*
pubs.consider-herdc	false
dc.date.updated	2024-06-27T02:55:30Z
pubs.finish-date	2023-09-15
pubs.place-of-publication	Piscataway, USA
pubs.publication-status	Published
pubs.start-date	2023-09-11
pubs.volume	00
dc.location	Piscataway, USA

Abstract:

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 transitive relations that frequently arise when solving reachability relations significantly improving the efficiency of CFL reachability analysis Our key insight is that multiple edges involving transitivity can be simultaneously derived via batch propagation of reachability relations on the transitivity aware subgraphs that are induced from the original edge labeled graph We evaluate the performance of Pearl 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 Pearl achieves average speedups of 82 73x for value flow analysis and 155 26x for alias analysis over the standard CFL reachability algorithm The comparison with Pocr a state of the art CFL reachability solver shows that Pearl runs 10 1x up to 29 2x and 2 37x up to 4 22x faster on average respectively for value flow analysis and alias analysis with less consumed memory

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/179665