{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,11]],"date-time":"2026-08-11T20:19:04Z","timestamp":1786479544828,"version":"build-2736575974"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"PLDI","license":[{"start":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T00:00:00Z","timestamp":1718841600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001824","name":"Czech Science Foundation","doi-asserted-by":"crossref","award":["23-06506S"],"award-info":[{"award-number":["23-06506S"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100017520","name":"FIT BUT","doi-asserted-by":"crossref","award":["FIT-S-23-8151"],"award-info":[{"award-number":["FIT-S-23-8151"]}],"id":[{"id":"10.13039\/501100017520","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2024,6,20]]},"abstract":"<jats:p>\n            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\n            <jats:italic toggle=\"yes\">saturation<\/jats:italic>\n            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.\n          <\/jats:p>\n          <jats:p>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.<\/jats:p>","DOI":"10.1145\/3656417","type":"journal-article","created":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T16:27:20Z","timestamp":1718900840000},"page":"990-1013","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Scaling Type-Based Points-to Analysis with Saturation"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-3213-9306","authenticated-orcid":false,"given":"Christian","family":"Wimmer","sequence":"first","affiliation":[{"name":"Oracle Labs, Redwood Shores, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-3646-3663","authenticated-orcid":false,"given":"Codrut","family":"Stancu","sequence":"additional","affiliation":[{"name":"Oracle Labs, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8846-922X","authenticated-orcid":false,"given":"David","family":"Kozak","sequence":"additional","affiliation":[{"name":"Brno University of Technology, Brno, Czechia"},{"name":"Oracle Labs, Brno, Czechia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-0441-5173","authenticated-orcid":false,"given":"Thomas","family":"W\u00fcrthinger","sequence":"additional","affiliation":[{"name":"Oracle Labs, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,6,20]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31057-7_30"},{"key":"e_1_3_1_3_2","volume-title":"Program Analysis and Specialization for the C Programming Language","author":"Andersen Lars Ole","year":"1994","unstructured":"Lars Ole Andersen. 1994. Program Analysis and Specialization for the C Programming Language. Ph. D. Dissertation. University of Copenhagen."},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3386026"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594299"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/236337.236371"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3485547"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-88806-0_2"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/1985793.1985827"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/1640089.1640108"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/115372.115320"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/277650.277667"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3377555.3377885"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3213846.3213860"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2005.02.005"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/1250734.1250767"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3622832"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ECOOP.2021.16"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ECOOP.2022.30"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3579641"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/379605.379665"},{"key":"e_1_3_1_22_2","unstructured":"IBM. 2020. WALA: T.J. Watson Libraries for Analysis. http:\/\/wala.sourceforge.net\/"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462191"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","unstructured":"David Kozak Stancu Codrut Christian Wimmer and Thomas W\u00fcrthinger. 2024. Scaling Points-to Analysis Using Saturation - Artifact. https:\/\/doi.org\/10.5281\/zenodo.10961908 10.5281\/zenodo.10961908","DOI":"10.5281\/zenodo.10961908"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3617651.3622980"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE.2017.53"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36579-6_12"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/1391984.1391987"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/2025113.2025160"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3276511"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","unstructured":"Yue Li Tian Tan Yifei Zhang and Jingling Xue. 2016. Program Tailoring: Slicing by Sequential Criteria. In Proceedings of the European Conference on Object-Oriented Programming (Leibniz International Proceedings in Informatics (LIPIcs) Vol. 56). 15:1\u201315:27. https:\/\/doi.org\/10.4230\/LIPIcs.ECOOP.2016.15 10.4230\/LIPIcs.ECOOP.2016.15","DOI":"10.4230\/LIPIcs.ECOOP.2016.15"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192390"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/2644805"},{"key":"e_1_3_1_34_2","volume-title":"Proceedings of the USENIX Security Symposium","author":"Livshits V. Benjamin","year":"2005","unstructured":"V. Benjamin Livshits and Monica S. Lam. 2005. Finding Security Vulnerabilities in Java Applications with Static Analysis. In Proceedings of the USENIX Security Symposium. USENIX."},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-88806-0_13"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3360574"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/3591242"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/566172.566174"},{"key":"e_1_3_1_39_2","unstructured":"Oracle. 2023. GraalVM. https:\/\/www.graalvm.org\/"},{"key":"e_1_3_1_40_2","unstructured":"Oracle. 2023. Micronaut MuShop. https:\/\/github.com\/oracle-quickstart\/oci-micronaut\/"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314637"},{"key":"e_1_3_1_42_2","unstructured":"Quarkus. 2023. Extension Registry Application. https:\/\/github.com\/quarkusio\/registry.quarkus.io"},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/2950290.2950312"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/301104.301111"},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ECOOP.2021.2"},{"key":"e_1_3_1_46_2","volume-title":"Two approaches to interprocedural data flow analysis","author":"Sharir Micha","year":"1978","unstructured":"Micha Sharir, Amir Pnueli, et al. 1978. Two approaches to interprocedural data flow analysis. New York University. Courant Institute of Mathematical Sciences."},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.1561\/2500000014"},{"key":"e_1_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/2509136.2509524"},{"key":"e_1_3_1_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926390"},{"key":"e_1_3_1_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594320"},{"key":"e_1_3_1_51_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03237-0_15"},{"key":"e_1_3_1_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/2754169.2754185"},{"key":"e_1_3_1_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/237721.237727"},{"key":"e_1_3_1_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/353171.353189"},{"key":"e_1_3_1_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/3597926.3598120"},{"key":"e_1_3_1_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/3377555.3377902"},{"key":"e_1_3_1_57_2","unstructured":"The Spring PetClinic Community. 2023. Open Source sample applications based on the Spring stack. https:\/\/spring-petclinic.github.io\/"},{"key":"e_1_3_1_58_2","doi-asserted-by":"publisher","DOI":"10.1145\/3360610"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3656417","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3656417","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T20:41:59Z","timestamp":1751661719000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3656417"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,20]]},"references-count":57,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2024,6,20]]}},"alternative-id":["10.1145\/3656417"],"URL":"https:\/\/doi.org\/10.1145\/3656417","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6,20]]},"assertion":[{"value":"2024-06-20","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}