{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T07:54:59Z","timestamp":1770278099910,"version":"3.49.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,7,23]],"date-time":"2021-07-23T00:00:00Z","timestamp":1626998400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"publisher","award":["DP170103956 DP180104069"],"award-info":[{"award-number":["DP170103956 DP180104069"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Softw. Eng. Methodol."],"published-print":{"date-parts":[[2021,10,31]]},"abstract":"<jats:p>\n            Object sensitivity is widely used as a context abstraction for computing the points-to information context-sensitively for object-oriented programming languages such as Java. Due to the combinatorial explosion of contexts in large object-oriented programs,\n            <jats:italic>k<\/jats:italic>\n            -object-sensitive pointer analysis (under\n            <jats:italic>k<\/jats:italic>\n            -limiting), denoted\n            <jats:italic>\n              <jats:italic>k<\/jats:italic>\n              -obj\n            <\/jats:italic>\n            , is often inefficient even when it is scalable for small values of\n            <jats:italic>k<\/jats:italic>\n            , where\n            <jats:italic>k<\/jats:italic>\n            \u2a7d 2 holds typically. A recent popular approach for accelerating\n            <jats:italic>\n              <jats:italic>k<\/jats:italic>\n              -obj\n            <\/jats:italic>\n            trades precision for efficiency by instructing\n            <jats:italic>\n              <jats:italic>k<\/jats:italic>\n              -obj\n            <\/jats:italic>\n            to analyze only some methods in a program context-sensitively, determined heuristically by a pre-analysis. In this article, we investigate how to develop a fundamentally different approach,\n            <jats:sc>Eagle<\/jats:sc>\n            , for designing a pre-analysis that can make\n            <jats:italic>\n              <jats:italic>k<\/jats:italic>\n              -obj\n            <\/jats:italic>\n            run significantly faster while maintaining its precision. The novelty of\n            <jats:sc>Eagle<\/jats:sc>\n            is to enable\n            <jats:italic>\n              <jats:italic>k<\/jats:italic>\n              -obj\n            <\/jats:italic>\n            to analyze a method with partial context sensitivity (i.e., context-sensitively for only some of its selected variables\/allocation sites) by solving a context-free-language (CFL) reachability problem based on a new CFL-reachability formulation of\n            <jats:italic>\n              <jats:italic>k<\/jats:italic>\n              -obj\n            <\/jats:italic>\n            . By regularizing one CFL for specifying field accesses and using another CFL for specifying method calls, we have formulated\n            <jats:sc>Eagle<\/jats:sc>\n            as a fully context-sensitive taint analysis (without\n            <jats:italic>k<\/jats:italic>\n            -limiting) that is both effective (by selecting the variables\/allocation sites to be analyzed by\n            <jats:italic>\n              <jats:italic>k<\/jats:italic>\n              -obj\n            <\/jats:italic>\n            context-insensitively so as to reduce the number of context-sensitive facts inferred by\n            <jats:italic>\n              <jats:italic>k<\/jats:italic>\n              -obj\n            <\/jats:italic>\n            in the program) and efficient (by running linearly in terms of the number of pointer assignment edges in the program). As\n            <jats:sc>Eagle<\/jats:sc>\n            represents the first precision-preserving pre-analysis, our evaluation focuses on demonstrating its significant performance benefits in accelerating\n            <jats:italic>\n              <jats:italic>k<\/jats:italic>\n              -obj\n            <\/jats:italic>\n            for a set of popular Java benchmarks and applications, with call graph construction, may-fail-casting, and polymorphic call detection as three important client analyses.\n          <\/jats:p>","DOI":"10.1145\/3450492","type":"journal-article","created":{"date-parts":[[2021,7,23]],"date-time":"2021-07-23T10:58:28Z","timestamp":1627037908000},"page":"1-46","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Eagle"],"prefix":"10.1145","volume":"30","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4070-3942","authenticated-orcid":false,"given":"Jingbo","family":"Lu","sequence":"first","affiliation":[{"name":"UNSW Sydney, Kensington, NSW, Australia"}]},{"given":"Dongjie","family":"He","sequence":"additional","affiliation":[{"name":"UNSW Sydney, Kensington, NSW, Australia"}]},{"given":"Jingling","family":"Xue","sequence":"additional","affiliation":[{"name":"UNSW Sydney, Kensington, NSW, Australia"}]}],"member":"320","published-online":{"date-parts":[[2021,7,23]]},"reference":[{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594299"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1167473.1167488"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1985793.1985827"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192378"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation (PLDI\u201900)","author":"Cheng Ben-Chung","unstructured":"Ben-Chung Cheng and Wen-Mei W. Hwu . 2000. Modular interprocedural pointer analysis using access paths: Design, implementation, and evaluation . In Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation (PLDI\u201900) . ACM, New York, NY, 57\u201369. DOI:https:\/\/doi.org\/10.1145\/349299.349311 10.1145\/349299.349311 Ben-Chung Cheng and Wen-Mei W. Hwu. 2000. Modular interprocedural pointer analysis using access paths: Design, implementation, and evaluation. In Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation (PLDI\u201900). ACM, New York, NY, 57\u201369. DOI:https:\/\/doi.org\/10.1145\/349299.349311"},{"key":"e_1_2_1_7_1","volume-title":"Retrieved","year":"2020","unstructured":"Eagle. 2020 . A Precision-Preserving Pre-Analysis Tool for Accelerating Object-Sensitive Pointer Analysis . Retrieved March 20, 2021 from http:\/\/www.cse.unsw.edu.au\/\u223ccorg\/eagle. Eagle. 2020. A Precision-Preserving Pre-Analysis Tool for Accelerating Object-Sensitive Pointer Analysis. Retrieved March 20, 2021 from http:\/\/www.cse.unsw.edu.au\/\u223ccorg\/eagle."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the Network and Distributed System Security Symposium (NDSS\u201915)","volume":"15","author":"Gordon Michael I.","unstructured":"Michael I. Gordon , Deokhwan Kim , Jeff H. Perkins , Limei Gilham , Nguyen Nguyen , and Martin C. Rinard . 2015. Information flow analysis of Android applications in DroidSafe . In Proceedings of the Network and Distributed System Security Symposium (NDSS\u201915) , Vol. 15 . 110. Michael I. Gordon, Deokhwan Kim, Jeff H. Perkins, Limei Gilham, Nguyen Nguyen, and Martin C. Rinard. 2015. Information flow analysis of Android applications in DroidSafe. In Proceedings of the Network and Distributed System Security Symposium (NDSS\u201915), Vol. 15. 110."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3088515.3088519"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASE.2019.00034"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276510"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133924"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1290520.1290521"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/996841.996867"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36579-6_12"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391984.1391987"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276511"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3381915"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3295739"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293606"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2644805"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3360574"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-37051-9_4"},{"key":"e_1_2_1_25_1","unstructured":"Ana Milanova. 2020. FlowCFL: A framework for type-based reachability analysis in the presence of mutable data. arXiv:2005.06496.  Ana Milanova. 2020. FlowCFL: A framework for type-based reachability analysis in the presence of mutable data. arXiv:2005.06496."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the International Symposium on Software Testing and Analysis (ISSTA\u201902)","author":"Milanova Ana","unstructured":"Ana Milanova , Atanas Rountev , and Barbara G. Ryder . 2002. Parameterized object sensitivity for points-to and side-effect analyses for Java . In Proceedings of the International Symposium on Software Testing and Analysis (ISSTA\u201902) . ACM, New York, NY, 1\u201311. DOI:https:\/\/doi.org\/10.1145\/566172.566174 10.1145\/566172.566174 Ana Milanova, Atanas Rountev, and Barbara G. Ryder. 2002. Parameterized object sensitivity for points-to and side-effect analyses for Java. In Proceedings of the International Symposium on Software Testing and Analysis (ISSTA\u201902). ACM, New York, NY, 1\u201311. DOI:https:\/\/doi.org\/10.1145\/566172.566174"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1044834.1044835"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2666356.2594318"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192417"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14722\/ndss.2016.23066"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0950-5849(98)00093-7"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/345099.345137"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2259016.2259050"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926390"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2666356.2594320"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1133981.1134027"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1094811.1094817"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53413-7_24"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062360"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062359"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1543135.1542486"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1925805.1925818"},{"key":"e_1_2_1_44_1","volume-title":"LIPIcs-Leibniz International Proceedings in Informatics","volume":"37","author":"Wei Shiyi","unstructured":"Shiyi Wei and Barbara G. Ryder . 2015. Adaptive context-sensitive analysis for JavaScript . In LIPIcs-Leibniz International Proceedings in Informatics , Vol. 37 . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Shiyi Wei and Barbara G. Ryder. 2015. Adaptive context-sensitive analysis for JavaScript. In LIPIcs-Leibniz International Proceedings in Informatics, Vol. 37. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03013-0_6"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594327"}],"container-title":["ACM Transactions on Software Engineering and Methodology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3450492","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3450492","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:45Z","timestamp":1750191525000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3450492"}},"subtitle":["CFL-Reachability-Based Precision-Preserving Acceleration of Object-Sensitive Pointer Analysis with Partial Context Sensitivity"],"short-title":[],"issued":{"date-parts":[[2021,7,23]]},"references-count":43,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,10,31]]}},"alternative-id":["10.1145\/3450492"],"URL":"https:\/\/doi.org\/10.1145\/3450492","relation":{},"ISSN":["1049-331X","1557-7392"],"issn-type":[{"value":"1049-331X","type":"print"},{"value":"1557-7392","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,23]]},"assertion":[{"value":"2020-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}