Learning a strategy for choosing widening thresholds from a large codebase

Sooyoung Cha, Sehun Jeong, Hakjoo Oh

Research output: Chapter in Book/Report/Conference proceedingConference contribution

13 Citations (Scopus)


In numerical static analysis, the technique of widening thresholds is essential for improving the analysis precision, but blind uses of the technique often significantly slow down the analysis. Ideally, an analysis should apply the technique only when it benefits, by carefully choosing thresholds that contribute to the final precision. However, finding the proper widening thresholds is nontrivial and existing syntactic heuristics often produce suboptimal results. In this paper, we present a method that automatically learns a good strategy for choosing widening thresholds from a given codebase. A notable feature of our method is that a good strategy can be learned with analyzing each program in the codebase only once, which allows to use a large codebase as training data. We evaluated our technique with a static analyzer for full C and 100 open-source benchmarks. The experimental results show that the learned widening strategy is highly cost-effective; it achieves 84% of the full precision while increasing the baseline analysis cost only by 1.4×. Our learning algorithm is able to achieve this performance 26 times faster than the previous Bayesian optimization approach.

Original languageEnglish
Title of host publicationProgramming Languages and Systems - 14th Asian Symposium, APLAS 2016, Proceedings
EditorsAtsushi Igarashi
PublisherSpringer Verlag
Number of pages17
ISBN (Print)9783319479576
Publication statusPublished - 2016
Event14th Asian Symposium on Programming Languages and Systems, APLAS 2016 - Hanoi, Viet Nam
Duration: 2016 Nov 212016 Nov 23

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10017 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference14th Asian Symposium on Programming Languages and Systems, APLAS 2016
Country/TerritoryViet Nam

Bibliographical note

Funding Information:
This work was supported by the Institute for Information & communications Technology Promotion (IITP) grant funded by the Korea government (MSIP) (No. R0190-15-2011, Development of Vulnerability Discovery Technologies for IoT Software Security); the Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT & Future Planning (NRF-2016R1C1B2014062); and the MSIP (Ministry of Science, ICT and Future Planning), Korea, under the ITRC (Information Technology Research Center) support program (IITP-2016-H85011610120001002) supervised by the IITP (Institute for Information & communications Technology Promotion).

Publisher Copyright:
© Springer International Publishing AG 2016.

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Learning a strategy for choosing widening thresholds from a large codebase'. Together they form a unique fingerprint.

Cite this