Reference abstract domains and applications to string analysis

Roberto Amadini, François Gauthier, Peter Schachte, Peter J. Stuckey, Graeme Gange, Alexander Jordan, Harald Søndergaard, Chenyi Zhang

Research output: Contribution to journalArticleResearchpeer-review

3 Citations (Scopus)

Abstract

Interpretation is a well established theory that supports reasoning about the run-time behaviour of programs. It achieves tractable reasoning by considering abstractions of run-time states, rather than the states themselves. The chosen set of abstractions is referred to as the abstract domain. We develop a novel framework for combining (a possibly large number of) abstract domains. It achieves the effect of the so-called reduced product without requiring a quadratic number of functions to translate information among abstract domains. A central notion is a reference domain, a medium for information exchange. Our approach suggests a novel and simpler way to manage the integration of large numbers of abstract domains. We instantiate our framework in the context of string analysis. Browser-embedded dynamic programming languages such as JavaScript and PHP encourage the use of strings as a universal data type for both code and data values. The ensuing vulnerabilities have made string analysis a focus of much recent research. String analysis tends to combine many elementary string abstract domains, eachdesigned to capture a specific aspect of strings. For this instance the set of regular languages,while too expensive to use directly for analysis, provides an attractive reference domain, enablingthe efficient simulation of reduced products of multiple string abstract domains.

Original languageEnglish
Pages (from-to)297-326
Number of pages30
JournalFundamenta Informaticae
Volume158
Issue number4
DOIs
Publication statusPublished - 9 Feb 2018
Externally publishedYes

Cite this

Amadini, Roberto ; Gauthier, François ; Schachte, Peter ; Stuckey, Peter J. ; Gange, Graeme ; Jordan, Alexander ; Søndergaard, Harald ; Zhang, Chenyi. / Reference abstract domains and applications to string analysis. In: Fundamenta Informaticae. 2018 ; Vol. 158, No. 4. pp. 297-326.
@article{9e1a3185c9ec4195b6d17f7b77356ab7,
title = "Reference abstract domains and applications to string analysis",
abstract = "Interpretation is a well established theory that supports reasoning about the run-time behaviour of programs. It achieves tractable reasoning by considering abstractions of run-time states, rather than the states themselves. The chosen set of abstractions is referred to as the abstract domain. We develop a novel framework for combining (a possibly large number of) abstract domains. It achieves the effect of the so-called reduced product without requiring a quadratic number of functions to translate information among abstract domains. A central notion is a reference domain, a medium for information exchange. Our approach suggests a novel and simpler way to manage the integration of large numbers of abstract domains. We instantiate our framework in the context of string analysis. Browser-embedded dynamic programming languages such as JavaScript and PHP encourage the use of strings as a universal data type for both code and data values. The ensuing vulnerabilities have made string analysis a focus of much recent research. String analysis tends to combine many elementary string abstract domains, eachdesigned to capture a specific aspect of strings. For this instance the set of regular languages,while too expensive to use directly for analysis, provides an attractive reference domain, enablingthe efficient simulation of reduced products of multiple string abstract domains.",
author = "Roberto Amadini and Fran{\cc}ois Gauthier and Peter Schachte and Stuckey, {Peter J.} and Graeme Gange and Alexander Jordan and Harald S{\o}ndergaard and Chenyi Zhang",
year = "2018",
month = "2",
day = "9",
doi = "10.3233/FI-2018-1650",
language = "English",
volume = "158",
pages = "297--326",
journal = "Fundamenta Informaticae",
issn = "0169-2968",
publisher = "Polskie Towarzystwo Matematyczne",
number = "4",

}

Amadini, R, Gauthier, F, Schachte, P, Stuckey, PJ, Gange, G, Jordan, A, Søndergaard, H & Zhang, C 2018, 'Reference abstract domains and applications to string analysis', Fundamenta Informaticae, vol. 158, no. 4, pp. 297-326. https://doi.org/10.3233/FI-2018-1650

Reference abstract domains and applications to string analysis. / Amadini, Roberto; Gauthier, François; Schachte, Peter; Stuckey, Peter J.; Gange, Graeme; Jordan, Alexander; Søndergaard, Harald; Zhang, Chenyi.

In: Fundamenta Informaticae, Vol. 158, No. 4, 09.02.2018, p. 297-326.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Reference abstract domains and applications to string analysis

AU - Amadini, Roberto

AU - Gauthier, François

AU - Schachte, Peter

AU - Stuckey, Peter J.

AU - Gange, Graeme

AU - Jordan, Alexander

AU - Søndergaard, Harald

AU - Zhang, Chenyi

PY - 2018/2/9

Y1 - 2018/2/9

N2 - Interpretation is a well established theory that supports reasoning about the run-time behaviour of programs. It achieves tractable reasoning by considering abstractions of run-time states, rather than the states themselves. The chosen set of abstractions is referred to as the abstract domain. We develop a novel framework for combining (a possibly large number of) abstract domains. It achieves the effect of the so-called reduced product without requiring a quadratic number of functions to translate information among abstract domains. A central notion is a reference domain, a medium for information exchange. Our approach suggests a novel and simpler way to manage the integration of large numbers of abstract domains. We instantiate our framework in the context of string analysis. Browser-embedded dynamic programming languages such as JavaScript and PHP encourage the use of strings as a universal data type for both code and data values. The ensuing vulnerabilities have made string analysis a focus of much recent research. String analysis tends to combine many elementary string abstract domains, eachdesigned to capture a specific aspect of strings. For this instance the set of regular languages,while too expensive to use directly for analysis, provides an attractive reference domain, enablingthe efficient simulation of reduced products of multiple string abstract domains.

AB - Interpretation is a well established theory that supports reasoning about the run-time behaviour of programs. It achieves tractable reasoning by considering abstractions of run-time states, rather than the states themselves. The chosen set of abstractions is referred to as the abstract domain. We develop a novel framework for combining (a possibly large number of) abstract domains. It achieves the effect of the so-called reduced product without requiring a quadratic number of functions to translate information among abstract domains. A central notion is a reference domain, a medium for information exchange. Our approach suggests a novel and simpler way to manage the integration of large numbers of abstract domains. We instantiate our framework in the context of string analysis. Browser-embedded dynamic programming languages such as JavaScript and PHP encourage the use of strings as a universal data type for both code and data values. The ensuing vulnerabilities have made string analysis a focus of much recent research. String analysis tends to combine many elementary string abstract domains, eachdesigned to capture a specific aspect of strings. For this instance the set of regular languages,while too expensive to use directly for analysis, provides an attractive reference domain, enablingthe efficient simulation of reduced products of multiple string abstract domains.

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

U2 - 10.3233/FI-2018-1650

DO - 10.3233/FI-2018-1650

M3 - Article

AN - SCOPUS:85042494155

VL - 158

SP - 297

EP - 326

JO - Fundamenta Informaticae

JF - Fundamenta Informaticae

SN - 0169-2968

IS - 4

ER -