{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T20:48:49Z","timestamp":1760042929095,"version":"3.41.0"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2014,9,25]],"date-time":"2014-09-25T00:00:00Z","timestamp":1411603200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003621","name":"Ministry of Science, ICT and Future Planning","doi-asserted-by":"publisher","award":["NRF-2008-0062609"],"award-info":[{"award-number":["NRF-2008-0062609"]}],"id":[{"id":"10.13039\/501100003621","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Program. Lang. Syst."],"published-print":{"date-parts":[[2014,9,25]]},"abstract":"<jats:p>In this article, we present a general method for achieving global static analyzers that are precise and sound, yet also scalable. Our method, on top of the abstract interpretation framework, is a general sparse analysis technique that supports relational as well as nonrelational semantics properties for various programming languages. Analysis designers first use the abstract interpretation framework to have a global and correct static analyzer whose scalability is unattended. Upon this underlying sound static analyzer, analysis designers add our generalized sparse analysis techniques to improve its scalability while preserving the precision of the underlying analysis. Our method prescribes what to prove to guarantee that the resulting sparse version should preserve the precision of the underlying analyzer.<\/jats:p>\n          <jats:p>We formally present our framework and show that existing sparse analyses are all restricted instances of our framework. In addition, we show more semantically elaborate design examples of sparse nonrelational and relational static analyses. We then present their implementation results that scale to globally analyze up to one million lines of C programs. We also show a set of implementation techniques that turn out to be critical to economically support the sparse analysis process.<\/jats:p>","DOI":"10.1145\/2590811","type":"journal-article","created":{"date-parts":[[2014,10,1]],"date-time":"2014-10-01T13:34:59Z","timestamp":1412170499000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Global Sparse Analysis Framework"],"prefix":"10.1145","volume":"36","author":[{"given":"Hakjoo","family":"Oh","sequence":"first","affiliation":[{"name":"Seoul National University, Seoul, Korea"}]},{"given":"Kihong","family":"Heo","sequence":"additional","affiliation":[{"name":"Seoul National University, Seoul, Korea"}]},{"given":"Wonchan","family":"Lee","sequence":"additional","affiliation":[{"name":"Seoul National University, Seoul, Korea"}]},{"given":"Woosuk","family":"Lee","sequence":"additional","affiliation":[{"name":"Seoul National University, Seoul, Korea"}]},{"given":"Daejun","family":"Park","sequence":"additional","affiliation":[{"name":"Seoul National University, Seoul, Korea"}]},{"given":"Jeehoon","family":"Kang","sequence":"additional","affiliation":[{"name":"Seoul National University, Seoul, Korea"}]},{"given":"Kwangkeun","family":"Yi","sequence":"additional","affiliation":[{"name":"Seoul National University, Seoul, Korea"}]}],"member":"320","published-online":{"date-parts":[[2014,9,25]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_2_1_1","DOI":"10.1007\/11823230_4"},{"doi-asserted-by":"publisher","key":"e_1_2_2_2_1","DOI":"10.1007\/978-3-540-24723-4_2"},{"doi-asserted-by":"publisher","key":"e_1_2_2_3_1","DOI":"10.1145\/781131.781153"},{"doi-asserted-by":"publisher","key":"e_1_2_2_4_1","DOI":"10.1007\/BFb0039704"},{"doi-asserted-by":"publisher","key":"e_1_2_2_5_1","DOI":"10.1145\/93542.93585"},{"doi-asserted-by":"publisher","key":"e_1_2_2_6_1","DOI":"10.1145\/99583.99594"},{"doi-asserted-by":"publisher","key":"e_1_2_2_7_1","DOI":"10.5555\/647473.727451"},{"doi-asserted-by":"publisher","key":"e_1_2_2_8_1","DOI":"10.1145\/512950.512973"},{"doi-asserted-by":"publisher","key":"e_1_2_2_9_1","DOI":"10.1145\/567752.567778"},{"doi-asserted-by":"publisher","key":"e_1_2_2_10_1","DOI":"10.1093\/logcom\/2.4.511"},{"doi-asserted-by":"publisher","key":"e_1_2_2_11_1","DOI":"10.1007\/s10703-009-0089-6"},{"doi-asserted-by":"publisher","key":"e_1_2_2_12_1","DOI":"10.1145\/512760.512770"},{"doi-asserted-by":"publisher","key":"e_1_2_2_13_1","DOI":"10.1145\/115372.115320"},{"doi-asserted-by":"publisher","key":"e_1_2_2_14_1","DOI":"10.1145\/203095.203099"},{"doi-asserted-by":"publisher","key":"e_1_2_2_15_1","DOI":"10.1145\/143095.143135"},{"doi-asserted-by":"publisher","key":"e_1_2_2_16_1","DOI":"10.1145\/1375581.1375615"},{"doi-asserted-by":"publisher","key":"e_1_2_2_17_1","DOI":"10.1145\/1926385.1926407"},{"doi-asserted-by":"publisher","key":"e_1_2_2_18_1","DOI":"10.1145\/2103656.2103693"},{"doi-asserted-by":"publisher","key":"e_1_2_2_19_1","DOI":"10.1145\/2429069.2429086"},{"doi-asserted-by":"publisher","key":"e_1_2_2_20_1","DOI":"10.1145\/1250734.1250767"},{"doi-asserted-by":"publisher","key":"e_1_2_2_21_1","DOI":"10.1145\/1480881.1480911"},{"doi-asserted-by":"publisher","key":"e_1_2_2_22_1","DOI":"10.5555\/2190025.2190075"},{"doi-asserted-by":"publisher","key":"e_1_2_2_23_1","DOI":"10.5555\/647167.717992"},{"doi-asserted-by":"publisher","key":"e_1_2_2_24_1","DOI":"10.1007\/978-3-642-02658-4_52"},{"volume-title":"Abstract interpretation &plus","author":"Jhee Yongin","unstructured":"Yongin Jhee, Minsik Jin, Yungbum Jung, Deokhwan Kim, Soonho Kong, Heejong Lee, Hakjoo Oh, Daejun Park, and Kwangkeun Yi. 2008. Abstract interpretation &plus; impure catalysts: Our sparrow experience. Presentation at the Workshop of the 30 Years of Abstract Interpretation. Available at ropas. snu.ac.kr\/~kwang\/paper\/30yai-08.pdf.","key":"e_1_2_2_25_1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_26_1","DOI":"10.1145\/155090.155098"},{"doi-asserted-by":"publisher","key":"e_1_2_2_27_1","DOI":"10.1007\/11547662_15"},{"doi-asserted-by":"publisher","key":"e_1_2_2_28_1","DOI":"10.1007\/BF00290339"},{"doi-asserted-by":"publisher","key":"e_1_2_2_29_1","DOI":"10.1145\/1250734.1250766"},{"doi-asserted-by":"publisher","key":"e_1_2_2_30_1","DOI":"10.1007\/978-3-642-27940-9_20"},{"doi-asserted-by":"publisher","key":"e_1_2_2_31_1","DOI":"10.1145\/2025113.2025160"},{"key":"e_1_2_2_32_1","volume-title":"n.d. BuDDy, a Binary Decision Diagram Package. Retrieved","author":"Lind-Nielson Jorn","year":"2014","unstructured":"Jorn Lind-Nielson. n.d. BuDDy, a Binary Decision Diagram Package. Retrieved July 27, 2014, from http:\/\/vlsicad.eecs.umich.edu\/BK\/Slots\/cache\/www.itu.dk\/research\/buddy\/."},{"volume-title":"Retrieved","year":"2014","unstructured":"MathWorks. n.d. Polyspace Embedded Software Verification. Retrieved July 27, 2014, from http:\/\/www.mathworks.com\/products\/polyspace\/index.html.","key":"e_1_2_2_33_1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_34_1","DOI":"10.1007\/978-3-540-31987-0_2"},{"doi-asserted-by":"publisher","key":"e_1_2_2_35_1","DOI":"10.1145\/1159803.1159807"},{"doi-asserted-by":"publisher","key":"e_1_2_2_36_1","DOI":"10.1023\/B:AUSE.0000008666.56394.a1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_37_1","DOI":"10.1145\/1134650.1134659"},{"doi-asserted-by":"publisher","key":"e_1_2_2_38_1","DOI":"10.1007\/s10990-006-8609-1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_39_1","DOI":"10.1007\/978-3-642-10672-9_4"},{"doi-asserted-by":"publisher","key":"e_1_2_2_40_1","DOI":"10.5555\/1946284.1946309"},{"doi-asserted-by":"publisher","key":"e_1_2_2_41_1","DOI":"10.1145\/2254064.2254092"},{"doi-asserted-by":"publisher","key":"e_1_2_2_42_1","DOI":"10.1002\/spe.969"},{"doi-asserted-by":"publisher","key":"e_1_2_2_43_1","DOI":"10.1007\/978-3-642-25318-8_7"},{"doi-asserted-by":"publisher","key":"e_1_2_2_44_1","DOI":"10.1016\/S0304-3975(00)00315-7"},{"doi-asserted-by":"publisher","key":"e_1_2_2_45_1","DOI":"10.1145\/512950.512961"},{"doi-asserted-by":"publisher","key":"e_1_2_2_46_1","DOI":"10.1145\/1040305.1040330"},{"doi-asserted-by":"publisher","key":"e_1_2_2_47_1","DOI":"10.1007\/11688839_3"},{"doi-asserted-by":"publisher","key":"e_1_2_2_48_1","DOI":"10.1145\/996841.996869"},{"doi-asserted-by":"publisher","key":"e_1_2_2_49_1","DOI":"10.1145\/103135.103136"},{"doi-asserted-by":"publisher","key":"e_1_2_2_50_1","DOI":"10.1007\/978-3-540-70545-1_36"},{"doi-asserted-by":"publisher","key":"e_1_2_2_51_1","DOI":"10.1145\/1772954.1772985"},{"doi-asserted-by":"publisher","key":"e_1_2_2_52_1","DOI":"10.1145\/1029894.1029911"}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2590811","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2590811","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:13:52Z","timestamp":1750277632000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2590811"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,9,25]]},"references-count":52,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,9,25]]}},"alternative-id":["10.1145\/2590811"],"URL":"https:\/\/doi.org\/10.1145\/2590811","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"type":"print","value":"0164-0925"},{"type":"electronic","value":"1558-4593"}],"subject":[],"published":{"date-parts":[[2014,9,25]]},"assertion":[{"value":"2013-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-09-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}