A Machine-Learning Algorithm with Disjunctive Model for Data-Driven Program Analysis
- Authors
- Jeon, Minseok; Jeong, Sehun; Cha, Sungdeok; Oh, Hakjoo
- Issue Date
- 6월-2019
- Publisher
- ASSOC COMPUTING MACHINERY
- Keywords
- Data-driven program analysis; static analysis; context-sensitivity; flow-sensitivity
- Citation
- ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, v.41, no.2
- Indexed
- SCIE
SCOPUS
- Journal Title
- ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS
- Volume
- 41
- Number
- 2
- URI
- https://scholar.korea.ac.kr/handle/2021.sw.korea/65304
- DOI
- 10.1145/3293607
- ISSN
- 0164-0925
- Abstract
- 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.
- Files in This Item
- There are no files associated with this item.
- Appears in
Collections - Graduate School > Department of Computer Science and Engineering > 1. Journal Articles
Items in ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.