Selective conjunction of context-sensitivity and octagon domain toward scalable and precise global static analysis

Kihong Heo; Hakjoo Oh; Kwangkeun Yi

doi:10.1002/spe.2493

Selective conjunction of context-sensitivity and octagon domain toward scalable and precise global static analysis

Kihong Heo, Hakjoo Oh, Kwangkeun Yi

Research output: Contribution to journal › Article › peer-review

4 Citations (Scopus)

Abstract

We present a practical technique for achieving a scalable and precise global static analysis by selectively applying context-sensitivity and the octagon relational domain. For precise analysis, context-sensitivity and relational analysis are key properties, but it has been hard to practically combine both of them. Our approach turns on those precision improvement features only when the analysis is likely to improve the precision to resolve given queries. The guidance comes from an impact pre-analysis that estimates the impact of a fully context-sensitive and relational octagon analysis. We designed a cost-effective pre-analysis and implemented this method in a realistic octagon analysis for full C. The experimental results show that our approach proves eight times more queries, while saving the time cost by 73.1% compared with a partially relational octagon analysis enabled by a syntactic heuristic.

Original language	English
Pages (from-to)	1677-1705
Number of pages	29
Journal	Software - Practice and Experience
Volume	47
Issue number	11
DOIs	https://doi.org/10.1002/spe.2493
Publication status	Published - 2017 Nov

Bibliographical note

Funding Information:
This work was partly supported by Samsung Research Funding Center of Samsung Electronics under Project Number SRFC-IT1502-07 and Institute for Information & communications Technology Promotion(IITP) grant funded by the Korea government(MSIP) (No.R0190-16-2011, Development of Vulnerability Discovery Technologies for IoT Software Security), (No.B0717-16-0098, Development of homomorphic encryption for DNA analysis and biometry authentication). This research was also supported by Basic Science Research Program through the National Research Foundation of Korea(NRF) funded by the Ministry of Science, ICT & Future Planning(NRF-2016R1C1B2014062) and BK21 Plus for Pioneers in Innovative Computing (Dept. of Computer Science and Engineering, SNU) funded by National Research Foundation of Korea(NRF) (21A20151113068).

Funding Information:
This work was partly supported by Samsung Research Funding Center of Samsung Electronics under Project Number SRFC-IT1502-07 and Institute for Information & communications Technology Promotion(IITP) grant funded by the Korea government(MSIP) (No.R0190-16-2011, Development of Vulnerability Discovery Technologies for IoT Software Security), (No.B0717-16-0098, Development of homomorphic encryption for DNA analysis and biometry authentication). This research was also supported by Basic Science Research Program through the National Research Foundation of Korea(NRF) funded by theMinistry of Science, ICT & Future Planning(NRF-2016R1C1B2014062) and BK21 Plus for Pioneers in Innovative Computing (Dept. of Computer Science and Engineering, SNU) funded by National Research Foundation of Korea(NRF) (21A20151113068).

Publisher Copyright:
Copyright © 2017 John Wiley & Sons, Ltd.

Keywords

abstract interpretation
context-sensitive analysis
relational analysis
static analysis

ASJC Scopus subject areas

Software

Access to Document

10.1002/spe.2493

Cite this

@article{cba49f447075460da74602cd98d787a7,

title = "Selective conjunction of context-sensitivity and octagon domain toward scalable and precise global static analysis",

abstract = "We present a practical technique for achieving a scalable and precise global static analysis by selectively applying context-sensitivity and the octagon relational domain. For precise analysis, context-sensitivity and relational analysis are key properties, but it has been hard to practically combine both of them. Our approach turns on those precision improvement features only when the analysis is likely to improve the precision to resolve given queries. The guidance comes from an impact pre-analysis that estimates the impact of a fully context-sensitive and relational octagon analysis. We designed a cost-effective pre-analysis and implemented this method in a realistic octagon analysis for full C. The experimental results show that our approach proves eight times more queries, while saving the time cost by 73.1% compared with a partially relational octagon analysis enabled by a syntactic heuristic.",

keywords = "abstract interpretation, context-sensitive analysis, relational analysis, static analysis",

author = "Kihong Heo and Hakjoo Oh and Kwangkeun Yi",

note = "Funding Information: This work was partly supported by Samsung Research Funding Center of Samsung Electronics under Project Number SRFC-IT1502-07 and Institute for Information & communications Technology Promotion(IITP) grant funded by the Korea government(MSIP) (No.R0190-16-2011, Development of Vulnerability Discovery Technologies for IoT Software Security), (No.B0717-16-0098, Development of homomorphic encryption for DNA analysis and biometry authentication). This research was also supported by Basic Science Research Program through the National Research Foundation of Korea(NRF) funded by the Ministry of Science, ICT & Future Planning(NRF-2016R1C1B2014062) and BK21 Plus for Pioneers in Innovative Computing (Dept. of Computer Science and Engineering, SNU) funded by National Research Foundation of Korea(NRF) (21A20151113068). Funding Information: This work was partly supported by Samsung Research Funding Center of Samsung Electronics under Project Number SRFC-IT1502-07 and Institute for Information & communications Technology Promotion(IITP) grant funded by the Korea government(MSIP) (No.R0190-16-2011, Development of Vulnerability Discovery Technologies for IoT Software Security), (No.B0717-16-0098, Development of homomorphic encryption for DNA analysis and biometry authentication). This research was also supported by Basic Science Research Program through the National Research Foundation of Korea(NRF) funded by theMinistry of Science, ICT & Future Planning(NRF-2016R1C1B2014062) and BK21 Plus for Pioneers in Innovative Computing (Dept. of Computer Science and Engineering, SNU) funded by National Research Foundation of Korea(NRF) (21A20151113068). Publisher Copyright: Copyright {\textcopyright} 2017 John Wiley & Sons, Ltd.",

year = "2017",

month = nov,

doi = "10.1002/spe.2493",

language = "English",

volume = "47",

pages = "1677--1705",

journal = "Software - Practice and Experience",

issn = "0038-0644",

publisher = "John Wiley and Sons Ltd",

number = "11",

}

TY - JOUR

T1 - Selective conjunction of context-sensitivity and octagon domain toward scalable and precise global static analysis

AU - Heo, Kihong

AU - Oh, Hakjoo

AU - Yi, Kwangkeun

N1 - Funding Information: This work was partly supported by Samsung Research Funding Center of Samsung Electronics under Project Number SRFC-IT1502-07 and Institute for Information & communications Technology Promotion(IITP) grant funded by the Korea government(MSIP) (No.R0190-16-2011, Development of Vulnerability Discovery Technologies for IoT Software Security), (No.B0717-16-0098, Development of homomorphic encryption for DNA analysis and biometry authentication). This research was also supported by Basic Science Research Program through the National Research Foundation of Korea(NRF) funded by the Ministry of Science, ICT & Future Planning(NRF-2016R1C1B2014062) and BK21 Plus for Pioneers in Innovative Computing (Dept. of Computer Science and Engineering, SNU) funded by National Research Foundation of Korea(NRF) (21A20151113068). Funding Information: This work was partly supported by Samsung Research Funding Center of Samsung Electronics under Project Number SRFC-IT1502-07 and Institute for Information & communications Technology Promotion(IITP) grant funded by the Korea government(MSIP) (No.R0190-16-2011, Development of Vulnerability Discovery Technologies for IoT Software Security), (No.B0717-16-0098, Development of homomorphic encryption for DNA analysis and biometry authentication). This research was also supported by Basic Science Research Program through the National Research Foundation of Korea(NRF) funded by theMinistry of Science, ICT & Future Planning(NRF-2016R1C1B2014062) and BK21 Plus for Pioneers in Innovative Computing (Dept. of Computer Science and Engineering, SNU) funded by National Research Foundation of Korea(NRF) (21A20151113068). Publisher Copyright: Copyright © 2017 John Wiley & Sons, Ltd.

PY - 2017/11

Y1 - 2017/11

N2 - We present a practical technique for achieving a scalable and precise global static analysis by selectively applying context-sensitivity and the octagon relational domain. For precise analysis, context-sensitivity and relational analysis are key properties, but it has been hard to practically combine both of them. Our approach turns on those precision improvement features only when the analysis is likely to improve the precision to resolve given queries. The guidance comes from an impact pre-analysis that estimates the impact of a fully context-sensitive and relational octagon analysis. We designed a cost-effective pre-analysis and implemented this method in a realistic octagon analysis for full C. The experimental results show that our approach proves eight times more queries, while saving the time cost by 73.1% compared with a partially relational octagon analysis enabled by a syntactic heuristic.

AB - We present a practical technique for achieving a scalable and precise global static analysis by selectively applying context-sensitivity and the octagon relational domain. For precise analysis, context-sensitivity and relational analysis are key properties, but it has been hard to practically combine both of them. Our approach turns on those precision improvement features only when the analysis is likely to improve the precision to resolve given queries. The guidance comes from an impact pre-analysis that estimates the impact of a fully context-sensitive and relational octagon analysis. We designed a cost-effective pre-analysis and implemented this method in a realistic octagon analysis for full C. The experimental results show that our approach proves eight times more queries, while saving the time cost by 73.1% compared with a partially relational octagon analysis enabled by a syntactic heuristic.

KW - abstract interpretation

KW - context-sensitive analysis

KW - relational analysis

KW - static analysis

UR - http://www.scopus.com/inward/record.url?scp=85014669638&partnerID=8YFLogxK

U2 - 10.1002/spe.2493

DO - 10.1002/spe.2493

M3 - Article

AN - SCOPUS:85014669638

SN - 0038-0644

VL - 47

SP - 1677

EP - 1705

JO - Software - Practice and Experience

JF - Software - Practice and Experience

IS - 11

ER -

Selective conjunction of context-sensitivity and octagon domain toward scalable and precise global static analysis

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this