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.

Amadini R., Gauthier F., Schachte P., Stuckey P.J., Gange G., Jordan A., et al. (2018). Reference abstract domains and applications to string analysis. FUNDAMENTA INFORMATICAE, 158(4), 297-326 [10.3233/FI-2018-1650].

Reference abstract domains and applications to string analysis

Amadini R.
;
2018

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.
2018
Amadini R., Gauthier F., Schachte P., Stuckey P.J., Gange G., Jordan A., et al. (2018). Reference abstract domains and applications to string analysis. FUNDAMENTA INFORMATICAE, 158(4), 297-326 [10.3233/FI-2018-1650].
Amadini R.; Gauthier F.; Schachte P.; Stuckey P.J.; Gange G.; Jordan A.; Sondergaard H.; Zhang C.
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/708555
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 8
social impact