{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T03:25:31Z","timestamp":1779074731269,"version":"3.51.4"},"reference-count":69,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2024,1,2]],"date-time":"2024-01-02T00:00:00Z","timestamp":1704153600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100008398","name":"VILLUM FONDEN","doi-asserted-by":"crossref","award":["VIL42117"],"award-info":[{"award-number":["VIL42117"]}],"id":[{"id":"10.13039\/100008398","id-type":"DOI","asserted-by":"crossref"}]},{"name":"SERB MATRICS","award":["MTR\/2019\/000095"],"award-info":[{"award-number":["MTR\/2019\/000095"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2024,1,2]]},"abstract":"<jats:p>\n            Dyck reachability is a principled, graph-based formulation of a plethora of static analyses. Bidirected graphs are used for capturing dataflow through mutable heap data, and are usual formalisms of demand-driven points-to and alias analyses. The best (offline) algorithm runs in\n            <jats:inline-formula>\n              <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                <mml:mrow>\n                  <mml:mi>O<\/mml:mi>\n                  <mml:mo>(<\/mml:mo>\n                  <mml:mi>m<\/mml:mi>\n                  <mml:mo>+<\/mml:mo>\n                  <mml:mi>n<\/mml:mi>\n                  <mml:mtext>\u2009<\/mml:mtext>\n                  <mml:mo>\u00b7<\/mml:mo>\n                  <mml:mtext>\u2009<\/mml:mtext>\n                  <mml:mi>\u03b1<\/mml:mi>\n                  <mml:mo>(<\/mml:mo>\n                  <mml:mi>n<\/mml:mi>\n                  <mml:mo>)<\/mml:mo>\n                  <mml:mo>)<\/mml:mo>\n                <\/mml:mrow>\n              <\/mml:math>\n            <\/jats:inline-formula>\n            time, where\n            <jats:inline-formula>\n              <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                <mml:mi>n<\/mml:mi>\n              <\/mml:math>\n            <\/jats:inline-formula>\n            is the number of nodes and\n            <jats:inline-formula>\n              <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                <mml:mi>m<\/mml:mi>\n              <\/mml:math>\n            <\/jats:inline-formula>\n            is the number of edges in the flow graph, which becomes\n            <jats:inline-formula>\n              <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                <mml:mrow>\n                  <mml:mi>O<\/mml:mi>\n                  <mml:mo>(<\/mml:mo>\n                  <mml:msup>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mn>2<\/mml:mn>\n                  <\/mml:msup>\n                  <mml:mo>)<\/mml:mo>\n                <\/mml:mrow>\n              <\/mml:math>\n            <\/jats:inline-formula>\n            in the worst case. In the everyday practice of program analysis, the analyzed code is subject to continuous change, with source code being added and removed. On-the-fly static analysis under such continuous updates gives rise to\n            <jats:italic toggle=\"yes\">dynamic Dyck reachability<\/jats:italic>\n            , where reachability queries run on a dynamically changing graph, following program updates. Naturally, executing the\n            <jats:italic toggle=\"yes\">offline<\/jats:italic>\n            algorithm in this\n            <jats:italic toggle=\"yes\">online<\/jats:italic>\n            setting is inadequate, as the time required to process a single update is prohibitively large. In this work we develop a novel dynamic algorithm for bidirected Dyck reachability that has\n            <jats:inline-formula>\n              <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                <mml:mi>O<\/mml:mi>\n                <mml:mo>(<\/mml:mo>\n                <mml:mi>n<\/mml:mi>\n                <mml:mtext>\u2009<\/mml:mtext>\n                <mml:mo>\u00b7<\/mml:mo>\n                <mml:mtext>\u2009<\/mml:mtext>\n                <mml:mi>\u03b1<\/mml:mi>\n                <mml:mo>(<\/mml:mo>\n                <mml:mi>n<\/mml:mi>\n                <mml:mo>)<\/mml:mo>\n                <mml:mo>)<\/mml:mo>\n              <\/mml:math>\n            <\/jats:inline-formula>\n            worst-case performance per update, thus beating the\n            <jats:inline-formula>\n              <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                <mml:mrow>\n                  <mml:mi>O<\/mml:mi>\n                  <mml:mo>(<\/mml:mo>\n                  <mml:msup>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mn>2<\/mml:mn>\n                  <\/mml:msup>\n                  <mml:mo>)<\/mml:mo>\n                <\/mml:mrow>\n              <\/mml:math>\n            <\/jats:inline-formula>\n            bound, and is also optimal in certain settings. We also implement our algorithm and evaluate its performance on on-the-fly data-dependence and alias analyses, and compare it with two best known alternatives, namely (i) the optimal offline algorithm, and (ii) a fully dynamic Datalog solver. Our experiments show that our dynamic algorithm is consistently, and by far, the top performing algorithm, exhibiting speedups in the order of 1000X. The running time of each update is almost always unnoticeable to the human eye, making it ideal for the on-the-fly analysis setting.\n          <\/jats:p>","DOI":"10.1145\/3632884","type":"journal-article","created":{"date-parts":[[2024,1,5]],"date-time":"2024-01-05T20:48:51Z","timestamp":1704487731000},"page":"1239-1268","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["On-the-Fly Static Analysis via Dynamic Bidirected Dyck Reachability"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0925-398X","authenticated-orcid":false,"given":"Shankaranarayanan","family":"Krishna","sequence":"first","affiliation":[{"name":"IIT Bombay, Mumbai, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-2581-2856","authenticated-orcid":false,"given":"Aniket","family":"Lal","sequence":"additional","affiliation":[{"name":"IIT Bombay, Mumbai, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8943-0722","authenticated-orcid":false,"given":"Andreas","family":"Pavlogiannis","sequence":"additional","affiliation":[{"name":"Aarhus University, Aarhus, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-1197-5556","authenticated-orcid":false,"given":"Omkar","family":"Tuppe","sequence":"additional","affiliation":[{"name":"IIT Bombay, Mumbai, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,1,5]]},"reference":[{"key":"e_1_3_1_2_1","unstructured":"2003. T. J. Watson Libraries for Analysis (WALA). https:\/\/github.com."},{"key":"e_1_3_1_3_1","unstructured":"2008. SPECjvm2008 Benchmark Suit. http:\/\/www.spec.org\/jvm2008\/."},{"key":"e_1_3_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/525066"},{"key":"e_1_3_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2568225.2568243"},{"key":"e_1_3_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1167473.1167488"},{"key":"e_1_3_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2259051.2259052"},{"key":"e_1_3_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1639949.1640108"},{"key":"e_1_3_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.56098"},{"key":"e_1_3_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2021.106135"},{"key":"e_1_3_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158118"},{"key":"e_1_3_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2914770.2837624"},{"key":"e_1_3_1_13_1","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1007\/978-3-030-44914-8_5","volume-title":"Programming Languages and Systems","author":"Chatterjee Krishnendu","year":"2020","unstructured":"Krishnendu Chatterjee, Amir Kafshdar Goharshady, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. 2020. Optimal and Perfectly Parallel Algorithms for On-demand Data-Flow Analysis. In Programming Languages and Systems, Peter M\u00fcller (Ed.). Springer International Publishing, Cham, 112\u2013140."},{"key":"e_1_3_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2676726.2676979"},{"key":"e_1_3_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1328897.1328460"},{"key":"e_1_3_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3498702"},{"key":"e_1_3_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/265910.265914"},{"key":"e_1_3_1_18_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2022.124"},{"key":"e_1_3_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3531130.3533345"},{"key":"e_1_3_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-24950-1_9"},{"key":"e_1_3_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1997.614960"},{"key":"e_1_3_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/378795.378802"},{"key":"e_1_3_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/3540543961_22"},{"key":"e_1_3_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/141471.141542"},{"key":"e_1_3_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502095"},{"key":"e_1_3_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/222132.222146"},{"key":"e_1_3_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2771783.2771803"},{"key":"e_1_3_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(89)80018-5"},{"key":"e_1_3_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3498673"},{"key":"e_1_3_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3571252"},{"key":"e_1_3_1_31_1","unstructured":"Shankaranarayanan Krishna Aniket Lal Andreas Pavlogiannis and Omkar Tuppe. 2023. On-The-Fly Static Analysis via Dynamic Bidirected Dyck Reachability. arXiv:2311.04319 [cs.PL]"},{"key":"e_1_3_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASE.2015.9"},{"key":"e_1_3_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/11688839_5"},{"key":"e_1_3_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3498724"},{"key":"e_1_3_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3386021"},{"key":"e_1_3_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293606"},{"key":"e_1_3_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3360574"},{"key":"e_1_3_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428193"},{"key":"e_1_3_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3434315"},{"key":"e_1_3_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428246"},{"key":"e_1_3_1_41_1","volume-title":"Static Program Analysis","author":"M\u00f8ller Anders","year":"2018","unstructured":"Anders M\u00f8ller and Michael I. Schwartzbach. 2018. Static Program Analysis. Technical Report. Department of Computer Science, Aarhus University. http:\/\/cs.au.dk\/~amoeller\/spa\/"},{"key":"e_1_3_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11970-5_8"},{"key":"e_1_3_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428195"},{"key":"e_1_3_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3583660.3583664"},{"key":"e_1_3_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/360204.360208"},{"key":"e_1_3_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/215465.215466"},{"key":"e_1_3_1_47_1","first-page":"5","article-title":"Program Analysis via Graph Reachability","author":"Reps Thomas","year":"1997","unstructured":"Thomas Reps. 1997. Program Analysis via Graph Reachability. In Proceedings of the 1997 International Symposium on Logic Programming (ILPS). 5\u201319.","journal-title":"Proceedings of the 1997 International Symposium on Logic Programming (ILPS)"},{"key":"e_1_3_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/345099.345137"},{"key":"e_1_3_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/199448.199462"},{"key":"e_1_3_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/195274.195287"},{"key":"e_1_3_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-2207-2_8"},{"key":"e_1_3_1_52_1","first-page":"56","article-title":"Differential Datalog","author":"Ryzhyk Leonid","year":"2019","unstructured":"Leonid Ryzhyk and Mihai Budiu. 2019. Differential Datalog. In Datalog 2.0 2019 - 3rd International Workshop on the Resurgence of Datalog in Academia and Industry (CEUR Workshop Proceedings, Vol. 2368). 56\u201367.http:\/\/ceur-ws.org\/Vol-2368\/paper6.pdf","journal-title":"Datalog 2.0 2019 - 3rd International Workshop on the Resurgence of Datalog in Academia and Industry (CEUR Workshop Proceedings, Vol. 2368)"},{"key":"e_1_3_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2259016.2259050"},{"key":"e_1_3_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3290361"},{"key":"e_1_3_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1133255.1134027"},{"key":"e_1_3_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/1094811.1094817"},{"key":"e_1_3_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/237721.237727"},{"key":"e_1_3_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2970276.2970298"},{"key":"e_1_3_1_59_1","doi-asserted-by":"crossref","first-page":"880","DOI":"10.1007\/978-3-662-54434-1_33","volume-title":"Programming Languages and Systems","author":"Tang Hao","year":"2017","unstructured":"Hao Tang, Di Wang, Yingfei Xiong, Lingming Zhang, Xiaoyin Wang, and Lu Zhang. 2017. Conditional Dyck-CFL Reachability Analysis for Complete and Efficient Library Summarization. In Programming Languages and Systems, Hongseok Yang (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 880\u2013908."},{"key":"e_1_3_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2676726.2676997"},{"key":"e_1_3_1_61_1","unstructured":"Tom Tseng. 2020. Dynamic connectivity data structure by Holm de Lichtenberg and Thorup. https:\/\/github.com\/tomtseng\/dynamic-connectivity-hdt."},{"key":"e_1_3_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASE.2019.00091"},{"key":"e_1_3_1_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03013-0_6"},{"key":"e_1_3_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/2001420.2001440"},{"key":"e_1_3_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/298514.298576"},{"key":"e_1_3_1_66_1","first-page":"175","article-title":"An Efficient Algorithm for Solving the Dyck-CFL Reachability Problem on Trees","author":"Yuan Hao","year":"2009","unstructured":"Hao Yuan and Patrick Eugster. 2009. An Efficient Algorithm for Solving the Dyck-CFL Reachability Problem on Trees. In Proceedings of the 18th European Symposium on Programming Languages and Systems: Held As Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2009 (ESOP). 175\u2013189.","journal-title":"Proceedings of the 18th European Symposium on Programming Languages and Systems: Held As Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2009 (ESOP)"},{"key":"e_1_3_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/502874.502888"},{"key":"e_1_3_1_68_1","doi-asserted-by":"crossref","unstructured":"Qirun Zhang Michael R. Lyu Hao Yuan and Zhendong Su. 2013. Fast Algorithms for Dyck-CFL-reachability with Applications to Alias Analysis (PLDI). ACM.","DOI":"10.1145\/2491956.2462159"},{"key":"e_1_3_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/3093333.3009848"},{"key":"e_1_3_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/1328438.1328464"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3632884","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3632884","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T20:06:24Z","timestamp":1751659584000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3632884"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,2]]},"references-count":69,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2024,1,2]]}},"alternative-id":["10.1145\/3632884"],"URL":"https:\/\/doi.org\/10.1145\/3632884","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,2]]},"assertion":[{"value":"2024-01-05","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}