{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T10:31:00Z","timestamp":1770287460356,"version":"3.49.0"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,6,19]],"date-time":"2019-06-19T00:00:00Z","timestamp":1560902400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Samsung Research Funding 8 Incubation Center of Samsung Electronics","award":["SRFC-IT1701-09"],"award-info":[{"award-number":["SRFC-IT1701-09"]}]},{"name":"Institute for Information 8 communications Technology Promotio"},{"name":"Korea governmen"},{"name":"Self-Learning Cyber Immune Technology Development","award":["2017-0-00184"],"award-info":[{"award-number":["2017-0-00184"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Program. Lang. Syst."],"published-print":{"date-parts":[[2019,6,30]]},"abstract":"<jats:p>We present a new machine-learning algorithm with disjunctive model for data-driven program analysis. One major challenge in static program analysis is a substantial amount of manual effort required for tuning the analysis performance. Recently, data-driven program analysis has emerged to address this challenge by automatically adjusting the analysis based on data through a learning algorithm. Although this new approach has proven promising for various program analysis tasks, its effectiveness has been limited due to simple-minded learning models and algorithms that are unable to capture sophisticated, in particular disjunctive, program properties. To overcome this shortcoming, this article presents a new disjunctive model for data-driven program analysis as well as a learning algorithm to find the model parameters. Our model uses Boolean formulas over atomic features and therefore is able to express nonlinear combinations of program properties. A key technical challenge is to efficiently determine a set of good Boolean formulas, as brute-force search would simply be impractical. We present a stepwise and greedy algorithm that efficiently learns Boolean formulas. We show the effectiveness and generality of our algorithm with two static analyzers: context-sensitive points-to analysis for Java and flow-sensitive interval analysis for C. Experimental results show that our automated technique significantly improves the performance of the state-of-the-art techniques including ones hand-crafted by human experts.<\/jats:p>","DOI":"10.1145\/3293607","type":"journal-article","created":{"date-parts":[[2019,6,19]],"date-time":"2019-06-19T12:05:38Z","timestamp":1560945938000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["A Machine-Learning Algorithm with Disjunctive Model for Data-Driven Program Analysis"],"prefix":"10.1145","volume":"41","author":[{"given":"Minseok","family":"Jeon","sequence":"first","affiliation":[{"name":"Korea University, Republic of Korea"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4825-4870","authenticated-orcid":false,"given":"Sehun","family":"Jeong","sequence":"additional","affiliation":[{"name":"Korea University, Republic of Korea"}]},{"given":"Sungdeok","family":"Cha","sequence":"additional","affiliation":[{"name":"Korea University, Republic of Korea"}]},{"given":"Hakjoo","family":"Oh","sequence":"additional","affiliation":[{"name":"Korea University, Republic of Korea"}]}],"member":"320","published-online":{"date-parts":[[2019,6,19]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Constraint-based Type Inference and Parametric Polymorphism","author":"Agesen Ole","unstructured":"Ole Agesen. 1994. Constraint-based Type Inference and Parametric Polymorphism. Springer Berlin, 78--100."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3088515.3088522"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1167473.1167488"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/781131.781153"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1640089.1640108"},{"key":"e_1_2_1_6_1","volume-title":"Learning a Strategy for Choosing Widening Thresholds from a Large Codebase","author":"Cha Sooyoung","unstructured":"Sooyoung Cha, Sehun Jeong, and Hakjoo Oh. 2016. Learning a Strategy for Choosing Widening Thresholds from a Large Codebase. Springer International Publishing, Cham, 25--41."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the ACM Conference on Programming Languages (OOPSLA\u201917)","volume":"1","author":"Chae Kwonsoo","year":"2017","unstructured":"Kwonsoo Chae, Hakjoo Oh, Kihong Heo, and Hongseok Yang. 2017. Automatically generating features for learning program analysis heuristics. In Proceedings of the ACM Conference on Programming Languages (OOPSLA\u201917), Vol. 1."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 26th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL\u201999)","author":"Chatterjee Ramkrishna","unstructured":"Ramkrishna Chatterjee, Barbara G. Ryder, and William A. Landi. 1999. Relevant context inference. In Proceedings of the 26th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL\u201999). ACM, 133--146."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/263698.264352"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 10th International Conference on Static Analysis (SAS\u201903)","author":"Samuel","unstructured":"Samuel Z. Guyer and Calvin Lin. 2003. Client-driven pointer analysis. In Proceedings of the 10th International Conference on Static Analysis (SAS\u201903). Springer-Verlag, Berlin, 214--236. Retrieved from: http:\/\/dl.acm.org\/citation.cfm?id&equals;1760267.1760284."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/378795.378802"},{"key":"e_1_2_1_12_1","volume-title":"Learning a Variable-Clustering Strategy for Octagon from Labeled Data Generated by a Static Analysis","author":"Heo Kihong","unstructured":"Kihong Heo, Hakjoo Oh, and Hongseok Yang. 2016. Learning a Variable-Clustering Strategy for Octagon from Labeled Data Generated by a Static Analysis. Springer Berlin, 237--256."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10703-017-0306-7"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE.2017.54"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/379605.379665"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133924"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-37051-9_3"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462191"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462191"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3095021"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/11688839_5"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391984.1391987"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009881"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/318773.318943"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1108792.1108797"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926391"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1044834.1044835"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10990-006-8609-1"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10672-9_4"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2590811"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254064.2254092"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594318"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2814270.2814309"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1275497.1275501"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/207110.207112"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/349299.349327"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2892208.2892226"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1561\/2500000014"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926390"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594320"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1133981.1134027"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1094811.1094817"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53413-7_24"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062360"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542476.1542486"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/781995.782008"},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the 29th European Conference on Object-Oriented Programming (ECOOP\u201915) (Leibniz International Proceedings in Informatics (LIPIcs)), John Tang Boyland (Ed.)","volume":"37","author":"Wei Shiyi","unstructured":"Shiyi Wei and Barbara G. Ryder. 2015. Adaptive context-sensitive analysis for JavaScript. In Proceedings of the 29th European Conference on Object-Oriented Programming (ECOOP\u201915) (Leibniz International Proceedings in Informatics (LIPIcs)), John Tang Boyland (Ed.), Vol. 37. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 712--734."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/207110.207111"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594327"}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3293607","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3293607","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:02:01Z","timestamp":1750208521000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3293607"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,19]]},"references-count":49,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,6,30]]}},"alternative-id":["10.1145\/3293607"],"URL":"https:\/\/doi.org\/10.1145\/3293607","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"value":"0164-0925","type":"print"},{"value":"1558-4593","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,19]]},"assertion":[{"value":"2017-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}