{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T17:03:13Z","timestamp":1783098193480,"version":"3.54.6"},"reference-count":102,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2016,6,30]],"date-time":"2016-06-30T00:00:00Z","timestamp":1467244800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"TCS Fellowship"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Comput. Surv."],"published-print":{"date-parts":[[2017,6,30]]},"abstract":"<jats:p>Heap data is potentially unbounded and seemingly arbitrary. Hence, unlike stack and static data, heap data cannot be abstracted in terms of a fixed set of program variables. This makes it an interesting topic of study and there is an abundance of literature employing heap abstractions. Although most studies have addressed similar concerns, insights gained in one description of heap abstraction may not directly carry over to some other description.<\/jats:p>\n          <jats:p>\n            In our search of a unified theme, we view\n            <jats:italic>heap abstraction<\/jats:italic>\n            as consisting of two steps: (a)\n            <jats:italic>heap modelling<\/jats:italic>\n            , which is the process of representing a heap memory (i.e., an unbounded set of concrete locations) as a heap model (i.e., an unbounded set of abstract locations), and (b)\n            <jats:italic>summarization<\/jats:italic>\n            , which is the process of bounding the heap model by merging multiple abstract locations into summary locations. We classify the heap models as storeless, store based, and hybrid. We describe various summarization techniques based on\n            <jats:italic>k<\/jats:italic>\n            -limiting, allocation sites, patterns, variables, other generic instrumentation predicates, and higher-order logics. This approach allows us to compare the insights of a large number of seemingly dissimilar heap abstractions and also paves the way for creating new abstractions by mix and match of models and summarization techniques.\n          <\/jats:p>","DOI":"10.1145\/2931098","type":"journal-article","created":{"date-parts":[[2016,7,5]],"date-time":"2016-07-05T14:08:13Z","timestamp":1467727693000},"page":"1-47","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":34,"title":["Heap Abstractions for Static Analysis"],"prefix":"10.1145","volume":"49","author":[{"given":"Vini","family":"Kanvar","sequence":"first","affiliation":[{"name":"Indian Institute of Technology Bombay, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Uday P.","family":"Khedker","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Bombay, India"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,6,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6423(99)00007-6"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/11609773_3"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-54807-9_5"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/PMMP.1993.315553"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/11823230_15"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the Conference ParCo 2011","author":"Basak Barnali","year":"2011"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/781131.781144"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462186"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2814270.2814293"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/11817963_47"},{"key":"e_1_2_1_12_1","volume-title":"Static Analysis: 11th International Symposium, SAS 2004, Verona, Italy, August 26-28, 2004. Proceedings. Springer","author":"Bozga Marius","year":"2004"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/966049.777395"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049697.2049700"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/11823285_33"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/604131.604142"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Supratik Chakraborty. 2012. Reasoning about heap manipulating programs using automata techniques. In Modern Applications of Automata Theory Deepak D\u2019Souza and Priti Shankar (Eds.). IISc-World Scientific Review Volume India 193--228. DOI:http:\/\/dx.doi.org\/10.1142\/9789814271059_0007  Supratik Chakraborty. 2012. Reasoning about heap manipulating programs using automata techniques. In Modern Applications of Automata Theory Deepak D\u2019Souza and Priti Shankar (Eds.). IISc-World Scientific Review Volume India 193--228. DOI:http:\/\/dx.doi.org\/10.1142\/9789814271059_0007","DOI":"10.1142\/9789814271059_0007"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/93542.93585"},{"key":"e_1_2_1_19_1","volume-title":"Static Analysis: 10th International Symposium, SAS 2003 San Diego, CA, USA, June 11--13, 2003 Proceedings. Springer Berlin Heidelberg","author":"Chong Stephen","year":"2003"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31057-7_29"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/178243.178263"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/11691372_19"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/236337.236367"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/277631.277637"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/647169.718147"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-10882-7_12"},{"key":"e_1_2_1_27_1","volume-title":"Khedker","author":"Gharat Pritam M.","year":"2016"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/237721.237724"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/268946.268957"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/11823230_16"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 10th International Conference on Static Analysis (SAS\u201903)","author":"Samuel"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1480881.1480911"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/2190025.2190075"},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","unstructured":"L. Hendren C. Donawa M. Emami G. Gao Justiani and B. Sridharan. 1993. Designing the McCAT compiler based on a family of structured intermediate representations. In Proceedings of the 5th International Workshop on Languages and Compilers for Parallel Computing Utpal Banerjee David Gelernter Alex Nicolau and David Padua (Eds.). Lecture Notes in Computer Science Vol. 757. Springer Berlin 406--420. DOI:http:\/\/dx.doi.org\/10.1007\/3-540-57502-2_61   L. Hendren C. Donawa M. Emami G. Gao Justiani and B. Sridharan. 1993. Designing the McCAT compiler based on a family of structured intermediate representations. In Proceedings of the 5th International Workshop on Languages and Compilers for Parallel Computing Utpal Banerjee David Gelernter Alex Nicolau and David Padua (Eds.). Lecture Notes in Computer Science Vol. 757. Springer Berlin 406--420. DOI:http:\/\/dx.doi.org\/10.1007\/3-540-57502-2_61","DOI":"10.1007\/3-540-57502-2_61"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/318789.318812"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.80123"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/379605.379665"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/325478.325519"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/347636.348916"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/586088.586089"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/363235.363259"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/239912.239913"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1108792.1108798"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/48022.48025"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/258915.258936"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1953355.1953368"},{"key":"e_1_2_1_49_1","volume-title":"Pointer Analysis (Dagstuhl Reports), Ond\u0159ej Lhot\u00e1k","author":"Khedker Uday P."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/2414936.2414957"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1290520.1290521"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/158511.158628"},{"key":"e_1_2_1_53_1","doi-asserted-by":"crossref","volume-title":"Precise slicing in imperative programs via term-rewriting and abstract interpretation","author":"Komondoor Raghavan","DOI":"10.1007\/978-3-642-38856-9_15"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064979.1064996"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2926697.2926698"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2006.125"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30579-8_28"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31985-6_16"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/143095.143137"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/53990.53993"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250734.1250766"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/347324.348031"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926389"},{"key":"e_1_2_1_65_1","first-page":"91","article-title":"Pointer analysis (Dagstuhl seminar 13162)","volume":"3","author":"Lhotak Ond\u0159ej","year":"2013","journal-title":"Dagstuhl Rep."},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993498.1993567"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/2644805"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/2048066.2048144"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.5555\/2041552.2041558"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2012.69"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/2259016.2259049"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/566171.566174"},{"key":"e_1_2_1_73_1","unstructured":"Anders M\u00f8ller. 2014. MONA project home page. (2014). www.brics.dk\/mona.  Anders M\u00f8ller. 2014. MONA project home page. (2014). www.brics.dk\/mona."},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/378795.378851"},{"key":"e_1_2_1_76_1","volume-title":"Principles of Program Analysis","author":"Nielson Flemming"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/996821.996836"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487568.2487569"},{"key":"e_1_2_1_79_1","series-title":"Lecture Notes in Computer Science","volume-title":"Isabelle - A Generic Theorem Prover (with a contribution by T. Nipkow)","author":"Paulson Lawrence C."},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1145\/1290520.1290524"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1145\/186025.186041"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.5555\/271338.271343"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.5555\/645683.664578"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1953-0053041-6"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1145\/1040305.1040330"},{"key":"e_1_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.5555\/318773.318945"},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.5555\/1765931.1765945"},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1145\/237721.237725"},{"key":"e_1_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.1145\/271510.271517"},{"key":"e_1_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.1145\/292540.292552"},{"key":"e_1_2_1_92_1","volume-title":"Compiler Design Handbook: Optimizations and Machine Code Generation","author":"Sagiv Mooly"},{"key":"e_1_2_1_94_1","doi-asserted-by":"publisher","DOI":"10.5555\/1760267.1760304"},{"key":"e_1_2_1_95_1","volume-title":"Proceedings of the 4th International Symposium on Static Analysis (SAS\u201997)","author":"Susan Horwitz Marc","year":"1997"},{"key":"e_1_2_1_97_1","doi-asserted-by":"publisher","DOI":"10.1561\/2500000014"},{"key":"e_1_2_1_98_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926390"},{"key":"e_1_2_1_99_1","doi-asserted-by":"publisher","DOI":"10.1145\/1133981.1134027"},{"key":"e_1_2_1_100_1","doi-asserted-by":"crossref","volume-title":"Alias Analysis for Object-oriented Programs","author":"Sridharan Manu","DOI":"10.1007\/978-3-642-36946-9_8"},{"key":"e_1_2_1_101_1","volume-title":"The Compiler Design Handbook: Optimizations and Machine Code Generation","author":"Srikant Y. N.","edition":"2"},{"key":"e_1_2_1_102_1","doi-asserted-by":"publisher","DOI":"10.1145\/237721.237727"},{"key":"e_1_2_1_103_1","doi-asserted-by":"publisher","DOI":"10.1145\/353171.353189"},{"key":"e_1_2_1_104_1","doi-asserted-by":"publisher","DOI":"10.1145\/378795.378804"},{"key":"e_1_2_1_105_1","doi-asserted-by":"publisher","DOI":"10.1145\/996841.996859"},{"key":"e_1_2_1_106_1","volume-title":"Proceedings of the 9th International Conference on Compiler Construction (CC\u201900)","author":"Wilhelm Reinhard"},{"key":"e_1_2_1_107_1","doi-asserted-by":"publisher","DOI":"10.1145\/1232420.1232423"},{"key":"e_1_2_1_108_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390630.1390658"},{"key":"e_1_2_1_109_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594328"},{"key":"e_1_2_1_110_1","doi-asserted-by":"publisher","DOI":"10.1145\/774572.774594"}],"container-title":["ACM Computing Surveys"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2931098","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2931098","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:55:56Z","timestamp":1750222556000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2931098"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,30]]},"references-count":102,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,6,30]]}},"alternative-id":["10.1145\/2931098"],"URL":"https:\/\/doi.org\/10.1145\/2931098","relation":{},"ISSN":["0360-0300","1557-7341"],"issn-type":[{"value":"0360-0300","type":"print"},{"value":"1557-7341","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,6,30]]},"assertion":[{"value":"2014-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-06-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}