{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,30]],"date-time":"2026-03-30T02:26:42Z","timestamp":1774837602596,"version":"3.50.1"},"reference-count":77,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2008,9,1]],"date-time":"2008-09-01T00:00:00Z","timestamp":1220227200000},"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":[[2008,9]]},"abstract":"<jats:p>We present Paddle, a framework of BDD-based context-sensitive points-to and call graph analyses for Java, as well as client analyses that use their results. Paddle supports several variations of context-sensitive analyses, including call site strings and object sensitivity, and context-sensitively specializes both pointer variables and the heap abstraction. We empirically evaluate the precision of these context-sensitive analyses on significant Java programs. We find that that object-sensitive analyses are more precise than comparable variations of the other approaches, and that specializing the heap abstraction improves precision more than extending the length of context strings.<\/jats:p>","DOI":"10.1145\/1391984.1391987","type":"journal-article","created":{"date-parts":[[2008,10,7]],"date-time":"2008-10-07T12:48:29Z","timestamp":1223383709000},"page":"1-53","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":96,"title":["Evaluating the benefits of context-sensitive points-to analysis using a BDD-based implementation"],"prefix":"10.1145","volume":"18","author":[{"given":"Ond\u0159ej","family":"Lhot\u00e1k","sequence":"first","affiliation":[{"name":"University of Waterloo, Waterloo, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Laurie","family":"Hendren","sequence":"additional","affiliation":[{"name":"McGill University, Montreal, QC, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,10,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/646153.679533"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/647228.719242"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/73560.73561"},{"key":"e_1_2_1_4_1","unstructured":"Ananian C. S. 2006. JavaCUP. http:\/\/www2.cs.tum.edu\/projects\/cup\/. Ananian C. S. 2006. JavaCUP. http:\/\/www2.cs.tum.edu\/projects\/cup\/."},{"key":"e_1_2_1_5_1","unstructured":"Andersen L. O. 1994. Program analysis and specialization for the C programming language. Ph.D. thesis DIKU report 94\/19 DIKU University of Copenhagen. Andersen L. O. 1994. Program analysis and specialization for the C programming language. Ph.D. thesis DIKU report 94\/19 DIKU University of Copenhagen."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/236337.236371"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/379605.379690"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Berndl M. Lhot\u00e1k O. Qian F. Hendren L. and Umanee N. 2002. Points-to analysis using BDDs. Tech. rep. 2002-10 Sable Research Group McGill University. Berndl M. Lhot\u00e1k O. Qian F. Hendren L. and Umanee N. 2002. Points-to analysis using BDDs. Tech. rep. 2002-10 Sable Research Group McGill University.","DOI":"10.1145\/781131.781144"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/781131.781144"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/136035.136043"},{"key":"e_1_2_1_11_1","unstructured":"Burke M. Carini P. Choi J. and Hind M. 1997. Interprocedural pointer alias analysis. Tech. rep. RC 21055 IBM T. J. Watson Research Center. Burke M. Carini P. Choi J. and Hind M. 1997. Interprocedural pointer alias analysis. Tech. rep. RC 21055 IBM T. J. Watson Research Center."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/645988.674177"},{"key":"e_1_2_1_13_1","unstructured":"Cahoon B. and McKinley K. S. 2001b. JOlden benchmarks. ftp:\/\/ftp.cs.umass.edu\/pub\/o8l\/benchmarks\/jolden.tar.gz. Cahoon B. and McKinley K. S. 2001b. JOlden benchmarks. ftp:\/\/ftp.cs.umass.edu\/pub\/o8l\/benchmarks\/jolden.tar.gz."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/362384.362685"},{"key":"e_1_2_1_15_1","unstructured":"DaCapo Project. 2005. The DaCapo benchmark suite. http:\/\/www-ali.cs.umass.edu\/DaCapo\/gcbm.html. DaCapo Project. 2005. The DaCapo benchmark suite. http:\/\/www-ali.cs.umass.edu\/DaCapo\/gcbm.html."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/646153.679523"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/236337.236367"},{"key":"e_1_2_1_18_1","unstructured":"Dufour B. 2004. Objective quantification of program behaviour using dynamic metrics. M.S. thesis McGill University. Dufour B. 2004. Objective quantification of program behaviour using dynamic metrics. M.S. thesis McGill University."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/949305.949320"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/178243.178264"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/277650.277667"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 7th International Symposium, on Static Analysis (SAS'00)","volume":"1824","author":"Foster J. S."},{"key":"e_1_2_1_23_1","unstructured":"Gagnon E. M. Menking B. Nowostawski M. Agbakpem K. and Gergely K. 2006. SableCC parser generator. http:\/\/sablecc.org. Gagnon E. M. Menking B. Nowostawski M. Agbakpem K. and Gergely K. 2006. SableCC parser generator. http:\/\/sablecc.org."},{"key":"e_1_2_1_24_1","volume-title":"Design Patterns: Elements of Reusable Object-Oriented Software","author":"Gamma E.","year":"1995"},{"key":"e_1_2_1_25_1","unstructured":"Gilbert D. 2006. JFreechart. http:\/\/jfree.org\/jfreechart. Gilbert D. 2006. JFreechart. http:\/\/jfree.org\/jfreechart."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/506315.506316"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/277650.277668"},{"key":"e_1_2_1_28_1","unstructured":"Heintze N. 1999. Analysis of large code bases: the compile-link-analyze model. http:\/\/citeseer ist psu.edu\/heintze99analysis.html. Heintze N. 1999. Analysis of large code bases: the compile-link-analyze model. http:\/\/citeseer ist psu.edu\/heintze99analysis.html."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/378795.378855"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/379605.379665"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/325478.325519"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/155090.155096"},{"key":"e_1_2_1_33_1","unstructured":"Lhot\u00e1k O. 2002. Spark: A flexible points-to analysis framework for Java. M.S. thesis McGill University. Lhot\u00e1k O. 2002. Spark: A flexible points-to analysis framework for Java. M.S. thesis McGill University."},{"key":"e_1_2_1_34_1","unstructured":"Lhot\u00e1k O. 2006. Program analysis using binary decision diagrams. Ph.D. thesis McGill University. Lhot\u00e1k O. 2006. Program analysis using binary decision diagrams. Ph.D. thesis McGill University."},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 12th International Conference on Compiler Construction, G. Hedin, Ed. Lecture Notes in Computer Science","volume":"2622","author":"Lhot\u00e1k O."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/996841.996861"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/11688839_5"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the European Software Engineering Conference (ESEC\/FSE'99)","volume":"1687","author":"Liang D."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/379605.379676"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1108792.1108797"},{"key":"e_1_2_1_41_1","unstructured":"Lind-Nielsen J. 2006. BuDDy A Binary Decision Diagram Package. http:\/\/sourceforge net\/projects\/buddy. Lind-Nielsen J. 2006. BuDDy A Binary Decision Diagram Package. http:\/\/sourceforge net\/projects\/buddy."},{"key":"e_1_2_1_42_1","unstructured":"Lindholm T. and Yellin F. 1999. The Java Virtual Machine Specification 2nd ed. Addison- Wesley Reading MA. Lindholm T. and Yellin F. 1999. The Java Virtual Machine Specification 2nd ed. Addison- Wesley Reading MA."},{"key":"e_1_2_1_43_1","unstructured":"Manevich R. 2003. Data structures and algorithms for efficient shape analysis. M.S. thesis School of Computer Science Tel-Aviv University Israel. Manevich R. 2003. Data structures and algorithms for efficient shape analysis. M.S. thesis School of Computer Science Tel-Aviv University Israel."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/647171.716101"},{"key":"e_1_2_1_45_1","unstructured":"Milanova A. 2003. Precise and practical flow analysis of object-oriented software. Ph.D. thesis Rutgers University. Milanova A. 2003. Precise and practical flow analysis of object-oriented software. Ph.D. thesis Rutgers University."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/566172.566174"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1044834.1044835"},{"key":"e_1_2_1_48_1","unstructured":"Muchnick S. S. 1997. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers. Muchnick S. S. 1997. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/996821.996836"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/1765931.1765947"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/996821.996835"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/504282.504286"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/207110.207112"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/1765931.1765945"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/383043.381532"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/514188.514190"},{"key":"e_1_2_1_57_1","first-page":"189","article-title":"Two approaches to interprocedural data flow analysis. In Program Flow Analysis: Theory and Applications, S. S. Muchnick and N. D. Jones, Eds. Prentice-Hall","volume":"7","author":"Sharir M.","year":"1981","journal-title":"Chapter"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/53990.54007"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250734.1250744"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/964001.964004"},{"key":"e_1_2_1_61_1","volume-title":"CUDD: CU Decision Diagram Package","author":"Somenzi F.","year":"2006"},{"key":"e_1_2_1_62_1","unstructured":"Standard Performance Evaluation Corporation. 1998. SPEC JVM98 benchmarks. http:\/\/www. spec.org\/osg\/jvm\/(Aug 10 2006). Standard Performance Evaluation Corporation. 1998. SPEC JVM98 benchmarks. http:\/\/www. spec.org\/osg\/jvm\/(Aug 10 2006)."},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/237721.237727"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/353171.353189"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/321879.321884"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/353171.353190"},{"key":"e_1_2_1_67_1","unstructured":"Vall\u00e9e-Rai R. 2000. Ashes suite collection. http:\/\/www.sable.mcgill.ca\/ashes. Vall\u00e9e-Rai R. 2000. Ashes suite collection. http:\/\/www.sable.mcgill.ca\/ashes."},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.5555\/647476.727758"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/378795.378804"},{"key":"e_1_2_1_70_1","volume-title":"Proceedings of the 15th European Conference (ECOOP'01)","volume":"2072","author":"Wang T."},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.1984.1659158"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.5555\/647171.718318"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/996841.996859"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/320384.320400"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/207110.207111"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/774572.774594"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/996841.996860"}],"container-title":["ACM Transactions on Software Engineering and Methodology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1391984.1391987","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1391984.1391987","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:58:05Z","timestamp":1750255085000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1391984.1391987"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,9]]},"references-count":77,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,9]]}},"alternative-id":["10.1145\/1391984.1391987"],"URL":"https:\/\/doi.org\/10.1145\/1391984.1391987","relation":{},"ISSN":["1049-331X","1557-7392"],"issn-type":[{"value":"1049-331X","type":"print"},{"value":"1557-7392","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,9]]},"assertion":[{"value":"2007-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-10-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}