{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T03:43:36Z","timestamp":1780371816127,"version":"3.54.1"},"reference-count":64,"publisher":"Association for Computing Machinery (ACM)","issue":"PLDI","license":[{"start":{"date-parts":[[2023,6,6]],"date-time":"2023-06-06T00:00:00Z","timestamp":1686009600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"The Natural Science Foundation of China","award":["62025202,62002157,61932021"],"award-info":[{"award-number":["62025202,62002157,61932021"]}]},{"name":"Jiangsu Natural Science Foundation","award":["BK20202001"],"award-info":[{"award-number":["BK20202001"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2023,6,6]]},"abstract":"<jats:p>Over the past decades, context sensitivity has been considered as one of the most effective ideas for improving the precision of pointer analysis for Java. Different from the extremely fast context-insensitivity approach, context sensitivity requires every program method to be analyzed under different contexts for separating the static abstractions of different dynamic instantiations of the method\u2019s variables and heap objects, and thus reducing spurious object flows introduced by method calls. However, despite great precision benefits, as each method is equivalently cloned and analyzed under each context, context sensitivity brings heavy efficiency costs. Recently, numerous selective context-sensitive approaches have been put forth for scaling pointer analysis to large and complex Java programs by applying contexts only to the selected methods while analyzing the remaining ones context-insensitively; however, because the selective approaches do not fundamentally alter the primary methodology of context sensitivity (and do not thus remove its efficiency bottleneck), they produce much improved but still limited results.<\/jats:p>\n          <jats:p>In this work, we present a fundamentally different approach called Cut-Shortcut for fast and precise pointer analysis for Java. Its insight is simple: the main effect of cloning methods under different contexts is to filter spurious object flows that have been merged inside a callee method; from the view of a typical pointer flow graph (PFG), such effect can be simulated by cutting off (Cut) the edges that introduce precision loss to certain pointers and adding Shortcut edges directly from source pointers to the target ones circumventing the method on PFG. As a result, we can achieve the effect of context sensitivity without contexts. We identify three general program patterns and develop algorithms based on them to safely cut off and add shortcut edges on PFG, formalize them and formally prove the soundness. To comprehensively validate Cut-Shortcut\u2019s effectiveness, we implement two versions of Cut-Shortcut for two state-of-the-art pointer analysis frameworks for Java, one in Datalog for the declarative Doop and the other in Java for the imperative Tai-e, and we consider all the large and complex programs used in recent literatures that meet the experimental requirements. The evaluation results are extremely promising: Cut-Shortcut is even able to run faster than context insensitivity for most evaluated programs while obtaining high precision that is comparable to context sensitivity (if scalable) in both frameworks. This is for the first time that we have been able to achieve such a good efficiency and precision trade-off for those hard-to-analyze programs, and we hope Cut-Shortcut could offer new perspectives for developing more effective pointer analysis for Java in the future.<\/jats:p>","DOI":"10.1145\/3591242","type":"journal-article","created":{"date-parts":[[2023,6,6]],"date-time":"2023-06-06T20:06:24Z","timestamp":1686081984000},"page":"539-564","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":22,"title":["Context Sensitivity without Contexts: A Cut-Shortcut Approach to Fast and Precise Pointer Analysis"],"prefix":"10.1145","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9134-1980","authenticated-orcid":false,"given":"Wenjie","family":"Ma","sequence":"first","affiliation":[{"name":"Nanjing University, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-3298-7999","authenticated-orcid":false,"given":"Shengyuan","family":"Yang","sequence":"additional","affiliation":[{"name":"Nanjing University, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-3792-1237","authenticated-orcid":false,"given":"Tian","family":"Tan","sequence":"additional","affiliation":[{"name":"Nanjing University, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7970-1384","authenticated-orcid":false,"given":"Xiaoxing","family":"Ma","sequence":"additional","affiliation":[{"name":"Nanjing University, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6299-4704","authenticated-orcid":false,"given":"Chang","family":"Xu","sequence":"additional","affiliation":[{"name":"Nanjing University, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-1285-2298","authenticated-orcid":false,"given":"Yue","family":"Li","sequence":"additional","affiliation":[{"name":"Nanjing University, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,6,6]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Program analysis and specialization for the C programming language. Ph. D. Dissertation","author":"Andersen Lars Ole","unstructured":"Lars Ole Andersen . 1994. Program analysis and specialization for the C programming language. Ph. D. Dissertation . University of Copenhagen. Lars Ole Andersen. 1994. Program analysis and specialization for the C programming language. Ph. D. Dissertation. University of Copenhagen."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3386026"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594299"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1167473.1167488"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/781131.781153"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1640089.1640108"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454099"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542476.1542517"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-88806-0_4"},{"key":"e_1_2_1_10_1","volume-title":"Scalable Flow-Sensitive Pointer Analysis for Java with Strong Updates. In ECOOP 2012 \u2013 Object-Oriented Programming, James Noble (Ed.). Springer Berlin Heidelberg","author":"De Arnab","year":"2012","unstructured":"Arnab De and Deepak D\u2019Souza . 2012 . Scalable Flow-Sensitive Pointer Analysis for Java with Strong Updates. In ECOOP 2012 \u2013 Object-Oriented Programming, James Noble (Ed.). Springer Berlin Heidelberg , Berlin, Heidelberg. 665\u2013687. isbn:978-3-642-31057-7 Arnab De and Deepak D\u2019Souza. 2012. Scalable Flow-Sensitive Pointer Analysis for Java with Strong Updates. In ECOOP 2012 \u2013 Object-Oriented Programming, James Noble (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg. 665\u2013687. isbn:978-3-642-31057-7"},{"key":"e_1_2_1_11_1","unstructured":"DOOP. 2022. Framework for Java Pointer and Taint Analysis. https:\/\/bitbucket.org\/yanniss\/doop \t\t\t\t  DOOP. 2022. Framework for Java Pointer and Taint Analysis. https:\/\/bitbucket.org\/yanniss\/doop"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3377555.3377885"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1348250.1348255"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133926"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3088515.3088519"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ECOOP.2021.16"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2022.3162236"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.2493"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2771783.2771803"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293607"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276510"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428247"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3498720"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133924"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2931098"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462191"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/11688839_5"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276511"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3236024.3236041"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3381915"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ECOOP.2016.15"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3386021"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3492428"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450492"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3360574"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.7808384"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/566172.566174"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1044834.1044835"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1133981.1134018"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594318"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2821504"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE.2012.6227127"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0950-5849(98)00093-7"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1275497.1275501"},{"key":"e_1_2_1_45_1","volume-title":"Two approaches to interprocedural data flow analysis","author":"Sharir Micha","unstructured":"Micha Sharir and Amir Pnueli . 1981. Two approaches to interprocedural data flow analysis . Prentice-Hall , 189\u2013234. Micha Sharir and Amir Pnueli. 1981. Two approaches to interprocedural data flow analysis. Prentice-Hall, 189\u2013234."},{"key":"e_1_2_1_46_1","volume-title":"Control-flow analysis of higher-order languages or taming lambda","author":"Shivers Olin Grigsby","unstructured":"Olin Grigsby Shivers . 1991. Control-flow analysis of higher-order languages or taming lambda . Carnegie Mellon University . Olin Grigsby Shivers. 1991. Control-flow analysis of higher-order languages or taming lambda. Carnegie Mellon University."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1561\/2500000014"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926390"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594320"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ECOOP.2016.22"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1133981.1134027"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36946-9_8"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250734.1250748"},{"key":"e_1_2_1_54_1","volume-title":"Tai-e: A Developer-Friendly Static Analysis Framework for Java. https:\/\/github.com\/pascal-lab\/Tai-e","year":"2022","unstructured":"Tai-e. 2022 . Tai-e: A Developer-Friendly Static Analysis Framework for Java. https:\/\/github.com\/pascal-lab\/Tai-e Tai-e. 2022. Tai-e: A Developer-Friendly Static Analysis Framework for Java. https:\/\/github.com\/pascal-lab\/Tai-e"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3485524"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53413-7_24"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062360"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3302516.3307359"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3377555.3377902"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/b102522"},{"key":"e_1_2_1_61_1","unstructured":"WALA. 2006. Watson Libraries for Analysis. http:\/\/wala.sf.net \t\t\t\t  WALA. 2006. Watson Libraries for Analysis. http:\/\/wala.sf.net"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ECOOP.2015.712"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462159"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594328"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3591242","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3591242","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:47Z","timestamp":1750178867000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3591242"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,6]]},"references-count":64,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2023,6,6]]}},"alternative-id":["10.1145\/3591242"],"URL":"https:\/\/doi.org\/10.1145\/3591242","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,6]]},"assertion":[{"value":"2023-06-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}