A practical algorithm for learning disjunctive abstraction heuristics in static program analysis
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Jeon, Donghoon | - |
dc.contributor.author | Jeon, Minseok | - |
dc.contributor.author | Oh, Hakjoo | - |
dc.date.accessioned | 2022-02-28T14:42:26Z | - |
dc.date.available | 2022-02-28T14:42:26Z | - |
dc.date.created | 2021-12-07 | - |
dc.date.issued | 2021-07 | - |
dc.identifier.issn | 0950-5849 | - |
dc.identifier.uri | https://scholar.korea.ac.kr/handle/2021.sw.korea/137265 | - |
dc.description.abstract | Context: The precision and cost of static analysis are determined by abstraction heuristics (e.g., strategies for abstracting calling contexts, heap locations, etc.), but manually designing effective abstraction heuristics requires a huge amount of engineering effort and domain knowledge. Recently, data-driven static analysis has emerged to address this challenge by learning such heuristics automatically from a set of training programs. Objective: We present a practical algorithm for learning disjunctive abstraction heuristics in data-driven static analysis. We build on a recently proposed approach that can learn nontrivial program properties by disjunctive boolean functions. However, the existing approach is practically limited as it assumes that the most precise abstraction is cheap for the training programs; the algorithm is inapplicable if the most precise abstraction is not scalable. The objective of this paper is to mitigate this limitation. Method: Our algorithm overcomes the limitation with two new ideas. It systematically decomposes the learning problem into feasible subproblems, and it can search through the abstraction space from the coarse to fine-grained abstractions. With this approach, our algorithm is able to learn heuristics when static analysis with the most precise abstraction is not scalable over the training programs. Results: We show our approach is effective and generally applicable. We applied our approach to a context sensitive points-to analysis for Java and a flow-sensitive interval analysis for C. Experimental results show that our algorithm is efficient. For example, our algorithm can learn heuristics for 3-object-sensitive analysis for which the existing learning algorithm is too expensive to learn any useful heuristics. Conclusion: Our algorithm makes a state-of-the-art technique for data-driven static analysis more practical. | - |
dc.language | English | - |
dc.language.iso | en | - |
dc.publisher | ELSEVIER | - |
dc.title | A practical algorithm for learning disjunctive abstraction heuristics in static program analysis | - |
dc.type | Article | - |
dc.contributor.affiliatedAuthor | Oh, Hakjoo | - |
dc.identifier.doi | 10.1016/j.infsof.2021.106564 | - |
dc.identifier.scopusid | 2-s2.0-85102741475 | - |
dc.identifier.wosid | 000642489200010 | - |
dc.identifier.bibliographicCitation | INFORMATION AND SOFTWARE TECHNOLOGY, v.135 | - |
dc.relation.isPartOf | INFORMATION AND SOFTWARE TECHNOLOGY | - |
dc.citation.title | INFORMATION AND SOFTWARE TECHNOLOGY | - |
dc.citation.volume | 135 | - |
dc.type.rims | ART | - |
dc.type.docType | Article | - |
dc.description.journalClass | 1 | - |
dc.description.journalRegisteredClass | scie | - |
dc.description.journalRegisteredClass | scopus | - |
dc.relation.journalResearchArea | Computer Science | - |
dc.relation.journalWebOfScienceCategory | Computer Science, Information Systems | - |
dc.relation.journalWebOfScienceCategory | Computer Science, Software Engineering | - |
dc.subject.keywordAuthor | Data-driven static analysis | - |
dc.subject.keywordAuthor | Learning algorithm | - |
Items in ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.
(02841) 서울특별시 성북구 안암로 14502-3290-1114
COPYRIGHT © 2021 Korea University. All Rights Reserved.
Certain data included herein are derived from the © Web of Science of Clarivate Analytics. All rights reserved.
You may not copy or re-distribute this material in whole or in part without the prior written consent of Clarivate Analytics.