Scaling Type-Based Points-to Analysis with Saturation

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F24%3APU151889" target="_blank" >RIV/00216305:26230/24:PU151889 - isvavai.cz</a>

Výsledek na webu

<a href="https://dl.acm.org/doi/pdf/10.1145/3656417" target="_blank" >https://dl.acm.org/doi/pdf/10.1145/3656417</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1145/3656417" target="_blank" >10.1145/3656417</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Scaling Type-Based Points-to Analysis with Saturation

Popis výsledku v původním jazyce

Designing a whole-program static analysis requires trade-offs between precision and scalability. While a context-insensitive points-to analysis is often considered a good compromise, it still has non-linear complexity that leads to scalability problems when analyzing large applications. On the other hand, rapid type analysis scales well but lacks precision. We use saturation in a context-insensitive type-based points-to analysis to make it as scalable as a rapid type analysis, while preserving most of the precision of the points-to analysis. With saturation, the points-to analysis only propagates small points-to sets for variables. If a variable can have more values than a certain threshold, the variable and all its usages are considered saturated and no longer analyzed. Our implementation in the points-to analysis of GraalVM Native Image, a closed-world approach to build standalone binaries for Java applications, shows that saturation allows GraalVM Native Image to analyze large Java applications with hundreds of thousands of methods in less than two minutes.

Název v anglickém jazyce

Scaling Type-Based Points-to Analysis with Saturation

Popis výsledku anglicky

Designing a whole-program static analysis requires trade-offs between precision and scalability. While a context-insensitive points-to analysis is often considered a good compromise, it still has non-linear complexity that leads to scalability problems when analyzing large applications. On the other hand, rapid type analysis scales well but lacks precision. We use saturation in a context-insensitive type-based points-to analysis to make it as scalable as a rapid type analysis, while preserving most of the precision of the points-to analysis. With saturation, the points-to analysis only propagates small points-to sets for variables. If a variable can have more values than a certain threshold, the variable and all its usages are considered saturated and no longer analyzed. Our implementation in the points-to analysis of GraalVM Native Image, a closed-world approach to build standalone binaries for Java applications, shows that saturation allows GraalVM Native Image to analyze large Java applications with hundreds of thousands of methods in less than two minutes.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA23-06506S" target="_blank" >GA23-06506S: Pokročilá analýza a verifikace pro pokročilý software</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2024

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Proceedings of the ACM on Programming Languages

ISSN

2475-1421

e-ISSN

—

Svazek periodika

8

Číslo periodika v rámci svazku

PLDI

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

24

Strana od-do

990-1013

Kód UT WoS článku

001264464100042

EID výsledku v databázi Scopus

2-s2.0-85196860695