{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T12:55:27Z","timestamp":1768740927226,"version":"3.49.0"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,5,27]],"date-time":"2023-05-27T00:00:00Z","timestamp":1685145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Softw. Eng. Methodol."],"published-print":{"date-parts":[[2023,10,31]]},"abstract":"<jats:p>\n            Object-sensitive pointer analysis, which separates the calling contexts of a method by its receiver objects, is known to achieve highly useful precision for object-oriented languages such as Java. Despite recent advances, all object-sensitive pointer analysis algorithms still suffer from the scalability problem due to the combinatorial explosion of contexts in large programs. In this article, we introduce a new approach,\n            <jats:sc>Conch<\/jats:sc>\n            , that can be applied to debloat contexts for\n            <jats:italic>all<\/jats:italic>\n            object-sensitive pointer analysis algorithms, thereby improving significantly their efficiency while incurring a negligible loss of precision. Our key insight is to approximate a recently proposed set of two necessary conditions for an object in a program to be context-sensitive, i.e., context-dependent (whose precise verification is undecidable) with a set of three linearly verifiable conditions in terms of the number of edges in the pointer assignment graph (PAG) representation of the program. These three linearly verifiable conditions, which turn out to be almost always necessary in practice, are synthesized from three key observations regarding context-dependability for the objects created and used in real-world object-oriented programs. To develop a practical implementation for\n            <jats:sc>Conch<\/jats:sc>\n            , we introduce an IFDS-based algorithm for reasoning about object reachability in the PAG of a program, which runs linearly in terms of the number of edges in the PAG. By debloating contexts for three representative object-sensitive pointer analysis algorithms, which are applied to a set of representative Java programs,\n            <jats:sc>Conch<\/jats:sc>\n            can speed up these three baseline algorithms substantially at only a negligible loss of precision (less than 0.1%) with respect to several commonly used precision metrics. In addition,\n            <jats:sc>Conch<\/jats:sc>\n            also improves their scalability by enabling them to analyze substantially more programs to completion than before (under a time budget of 12 hours).\n            <jats:sc>Conch<\/jats:sc>\n            has been open-sourced (http:\/\/www.cse.unsw.edu.au\/~corg\/tools\/conch), opening up new opportunities for other researchers and practitioners to further improve this research. To demonstrate this, we introduce one extension of\n            <jats:sc>Conch<\/jats:sc>\n            to accelerate further the three baselines without losing any precision, providing further insights on extending\n            <jats:sc>Conch<\/jats:sc>\n            to make precision-efficiency tradeoffs in future research.\n          <\/jats:p>","DOI":"10.1145\/3579641","type":"journal-article","created":{"date-parts":[[2023,1,9]],"date-time":"2023-01-09T13:14:19Z","timestamp":1673270059000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["IFDS-based Context Debloating for Object-Sensitive Pointer Analysis"],"prefix":"10.1145","volume":"32","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0304-8942","authenticated-orcid":false,"given":"Dongjie","family":"He","sequence":"first","affiliation":[{"name":"UNSW Sydney, Australia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4070-3942","authenticated-orcid":false,"given":"Jingbo","family":"Lu","sequence":"additional","affiliation":[{"name":"UNSW Sydney, Australia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0380-3506","authenticated-orcid":false,"given":"Jingling","family":"Xue","sequence":"additional","affiliation":[{"name":"UNSW Sydney, Australia"}]}],"member":"320","published-online":{"date-parts":[[2023,5,27]]},"reference":[{"key":"e_1_3_1_2_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 Cophenhagen."},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/2666356.2594299"},{"key":"e_1_3_1_4_2","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1145\/1167473.1167488","volume-title":"Proceedings of the 21st Annual ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages, and Applications","author":"Blackburn Stephen M.","year":"2006","unstructured":"Stephen M. Blackburn, Robin Garner, Chris Hoffmann, Asjad M. Khang, Kathryn S. McKinley, Rotem Bentzur, Amer Diwan, Daniel Feinberg, Daniel Frampton, Samuel Z. Guyer, Martin Hirzel, Antony Hosking, Maria Jump, Han Lee, J. Eliot B. Moss, Aashish Phansalkar, Darko Stefanovi\u0107, Thomas VanDrunen, Daniel von Dincklage, and Ben Wiedermann. 2006. The DaCapo benchmarks: Java benchmarking development and analysis. In Proceedings of the 21st Annual ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages, and Applications. Association for Computing Machinery, New York, NY, 169\u2013190."},{"key":"e_1_3_1_5_2","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1145\/1985793.1985827","volume-title":"Proceedings of the 33rd International Conference on Software Engineering","author":"Bodden Eric","year":"2011","unstructured":"Eric Bodden, Andreas Sewe, Jan Sinschek, Hela Oueslati, and Mira Mezini. 2011. Taming reflection: Aiding static analysis in the presence of reflection and custom class loaders. In Proceedings of the 33rd International Conference on Software Engineering. IEEE, 241\u2013250."},{"key":"e_1_3_1_6_2","first-page":"1","volume-title":"Proceedings of the 18th International Symposium on Software Testing and Analysis","author":"Bravenboer Martin","year":"2009","unstructured":"Martin Bravenboer and Yannis Smaragdakis. 2009. Exception analysis and points-to analysis: Better together. In Proceedings of the 18th International Symposium on Software Testing and Analysis. Association for Computing Machinery, New York, NY, 1\u201312."},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/1640089.1640108"},{"key":"e_1_3_1_8_2","unstructured":"IBM T. J. Watson Research Center. 2022. WALA: T. J. Watson Libraries for Analysis. Retrieved April 27 2022 from http:\/\/wala.sourceforge.net\/."},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/320385.320386"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/263699.263750"},{"key":"e_1_3_1_11_2","first-page":"110","volume-title":"NDSS","author":"Gordon Michael I.","year":"2015","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 NDSS, Vol. 15. The Internet Society, 110."},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3088515.3088519"},{"key":"e_1_3_1_13_2","first-page":"267","volume-title":"Proceedings of the 2019 34th IEEE\/ACM International Conference on Automated Software Engineering (ASE)","author":"He Dongjie","year":"2019","unstructured":"Dongjie He, Haofeng Li, Lei Wang, Haining Meng, Hengjie Zheng, Jie Liu, Shuangwei Hu, Lian Li, and Jingling Xue. 2019. Performance-boosting sparsification of the IFDS algorithm with applications to taint analysis. In Proceedings of the 2019 34th IEEE\/ACM International Conference on Automated Software Engineering (ASE). IEEE, 267\u2013279."},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ECOOP.2021.16"},{"key":"e_1_3_1_15_2","first-page":"1","volume-title":"Proceedings of the IEEE Transactions on Software Engineering","author":"He Dongjie","year":"2022","unstructured":"Dongjie He, Jingbo Lu, Yaoqing Gao, and Jingling Xue. 2022. Selecting context-sensitivity modularly for accelerating object-sensitive pointer analysis. In Proceedings of the IEEE Transactions on Software Engineering. IEEE, New York, NY, 1\u20131."},{"key":"e_1_3_1_16_2","first-page":"30:1\u201330:29","volume-title":"Proceedings of the 36th European Conference on Object-Oriented Programming (ECOOP 2022)","volume":"222","author":"He Dongjie","year":"2022","unstructured":"Dongjie He, Jingbo Lu, and Jingling Xue. 2022. Qilin: A new framework for supporting fine-grained context-sensitivity in Java pointer analysis. In Proceedings of the 36th European Conference on Object-Oriented Programming (ECOOP 2022), Vol. 222. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 30:1\u201330:29."},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3276510"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3428247"},{"key":"e_1_3_1_19_2","first-page":"100","article-title":"Data-driven context-sensitivity for points-to analysis","volume":"1","author":"Jeong Sehun","year":"2017","unstructured":"Sehun Jeong, Minseok Jeon, Sungdeok Cha, and Hakjoo Oh. 2017. Data-driven context-sensitivity for points-to analysis. Proceedings of the ACM on Programming Languages 1, OOPSLA (2017), 100.","journal-title":"Proceedings of the ACM on Programming Languages"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/1134744.1134751"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462191"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.5555\/1765931.1765948"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/3540250.3549122"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/2025113.2025160"},{"key":"e_1_3_1_25_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3276511","article-title":"Precision-guided context sensitivity for pointer analysis","volume":"2","author":"Li Yue","year":"2018","unstructured":"Yue Li, Tian Tan, Anders M\u00f8ller, and Yannis Smaragdakis. 2018. Precision-guided context sensitivity for pointer analysis. Proceedings of the ACM on Programming Languages 2, OOPSLA (2018), 1\u201329.","journal-title":"Proceedings of the ACM on Programming Languages"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3236024.3236041"},{"key":"e_1_3_1_27_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3381915","article-title":"A principled approach to selective context sensitivity for pointer analysis","volume":"42","author":"Li Yue","year":"2020","unstructured":"Yue Li, Tian Tan, Anders M\u00f8ller, and Yannis Smaragdakis. 2020. A principled approach to selective context sensitivity for pointer analysis. ACM Transactions on Programming Languages and Systems 42, TOPLAS (2020), 1\u201340.","journal-title":"ACM Transactions on Programming Languages and Systems"},{"key":"e_1_3_1_28_2","first-page":"15:1\u201315:27","volume-title":"Proceedings of the 30th European Conference on Object-Oriented Programming","author":"Li Yue","year":"2016","unstructured":"Yue Li, Tian Tan, Yifei Zhang, and Jingling Xue. 2016. Program tailoring: Slicing by sequential criteria. In Proceedings of the 30th European Conference on Object-Oriented Programming. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 15:1\u201315:27."},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/1512475.1512486"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.5555\/1251398.1251416"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3450492"},{"key":"e_1_3_1_32_2","first-page":"261","volume-title":"Proceedings of the International Static Analysis Symposium","author":"Lu Jingbo","year":"2021","unstructured":"Jingbo Lu, Dongjie He, and Jingling Xue. 2021. Selective context-sensitivity for k-CFA with CFL-reachability. In Proceedings of the International Static Analysis Symposium. Springer International Publishing, Cham, 261\u2013285."},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/3360574"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/1251535.1251540"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/566172.566174"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/1044834.1044835"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/1133981.1134018"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/996821.996836"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0950-5849(98)00093-7"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/345099.345137"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/199448.199462"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/2259016.2259050"},{"key":"e_1_3_1_43_2","first-page":"189","volume-title":"Program Flow Analysis: Theory and Applications","author":"Sharir Micha","year":"1981","unstructured":"Micha Sharir and Amir Pnueli. 1981. Two approaches to interprocedural data flow analysis. In Program Flow Analysis: Theory and Applications. S. S. Muchnick and N. D. Jones (Eds.), Prentice-Hall, Englewood Cliffs, NJ, Chapter 7, 189\u2013234."},{"key":"e_1_3_1_44_2","unstructured":"Yannis Smaragdakis. 2021. Doop-Framework for Java Pointer and Taint Analysis (using P\/Taint). Retrieved Jan 10 2021 from https:\/\/bitbucket.org\/yanniss\/doop\/."},{"key":"e_1_3_1_45_2","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1145\/1926385.1926390","volume-title":"Proceedings of the 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages","author":"Smaragdakis Yannis","year":"2011","unstructured":"Yannis Smaragdakis, Martin Bravenboer, and Ondrej Lhot\u00e1k. 2011. Pick your contexts well: Understanding object-sensitivity. In Proceedings of the 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. Association for Computing Machinery, New York, NY, 17\u201330."},{"key":"e_1_3_1_46_2","first-page":"22:1\u201322:26","volume-title":"Proceedings of the 30th European Conference on Object-Oriented Programming","author":"Sp\u00e4th Johannes","year":"2016","unstructured":"Johannes Sp\u00e4th, Lisa Nguyen Quang Do, Karim Ali, and Eric Bodden. 2016. Boomerang: Demand-driven flow-and context-sensitive pointer analysis for Java. In Proceedings of the 30th European Conference on Object-Oriented Programming. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 22:1\u201322:26."},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/1133981.1134027"},{"key":"e_1_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/1250734.1250748"},{"key":"e_1_3_1_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/1094811.1094817"},{"key":"e_1_3_1_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/2950290.2950296"},{"key":"e_1_3_1_51_2","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1007\/978-3-662-53413-7_24","volume-title":"Proceedings of the International Static Analysis Symposium","author":"Tan Tian","year":"2016","unstructured":"Tian Tan, Yue Li, and Jingling Xue. 2016. Making k-object-sensitive pointer analysis more precise with still k-limiting. In Proceedings of the International Static Analysis Symposium. Springer, Berlin, 489\u2013510."},{"key":"e_1_3_1_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/3377555.3377902"},{"key":"e_1_3_1_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062359"},{"key":"e_1_3_1_54_2","first-page":"278","volume-title":"Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation","author":"Xue Tian Tan, Yue Li and Jingling","year":"2017","unstructured":"Tian Tan, Yue Li and Jingling Xue. 2017. Efficient and precise points-to analysis: Modeling the heap by merging equivalent automata. In Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation. Association for Computing Machinery, New York, NY, 278\u2013291."},{"key":"e_1_3_1_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/3180155.3180251"},{"key":"e_1_3_1_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/1925805.1925818"},{"key":"e_1_3_1_57_2","first-page":"999","volume-title":"Proceedings of the 2020 IEEE\/ACM 42nd International Conference on Software Engineering (ICSE)","author":"Wang Haijun","year":"2020","unstructured":"Haijun Wang, Xiaofei Xie, Yi Li, Cheng Wen, Yuekang Li, Yang Liu, Shengchao Qin, Hongxu Chen, and Yulei Sui. 2020. Typestate-guided Fuzzer for discovering use-after-free vulnerabilities. In Proceedings of the 2020 IEEE\/ACM 42nd International Conference on Software Engineering (ICSE). IEEE, New York, NY, 999\u20131010."},{"key":"e_1_3_1_58_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1984.5010248"},{"key":"e_1_3_1_59_2","doi-asserted-by":"publisher","DOI":"10.1145\/996841.996859"},{"key":"e_1_3_1_60_2","doi-asserted-by":"publisher","DOI":"10.1145\/320384.320400"},{"key":"e_1_3_1_61_2","first-page":"265","volume-title":"Proceedings of the 2020 IEEE 31st International Symposium on Software Reliability Engineering (ISSRE)","author":"Wu Diyu","year":"2020","unstructured":"Diyu Wu, Dongjie He, Shiping Chen, and Jingling Xue. 2020. Exposing android event-based races by selective branch instrumentation. In Proceedings of the 2020 IEEE 31st International Symposium on Software Reliability Engineering (ISSRE). IEEE, New York, NY, 265\u2013276."},{"key":"e_1_3_1_62_2","doi-asserted-by":"publisher","DOI":"10.1145\/2001420.2001440"},{"key":"e_1_3_1_63_2","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009848"}],"container-title":["ACM Transactions on Software Engineering and Methodology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3579641","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3579641","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:48:44Z","timestamp":1750182524000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3579641"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,27]]},"references-count":62,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,10,31]]}},"alternative-id":["10.1145\/3579641"],"URL":"https:\/\/doi.org\/10.1145\/3579641","relation":{},"ISSN":["1049-331X","1557-7392"],"issn-type":[{"value":"1049-331X","type":"print"},{"value":"1557-7392","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,27]]},"assertion":[{"value":"2022-06-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-12-05","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-05-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}