Reference Abstract Domains and Applications to String Analysis. Amadini, R., Gange, G., Gauthier, F., Jordan, A., Schachte, P., Søndergaard, H., Stuckey, P. J., & Zhang, C. Fundamenta Informaticae, 158(4):297–326, 2018.
Paper doi abstract bibtex 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, each designed 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, enabling the efficient simulation of reduced products of multiple string abstract domains.
@Article{Ama-Gan-Gau-Jor-Sch-Son-Stu-Zha_FI18,
author = {Roberto Amadini and
Graeme Gange and
Fran{\c{c}}ois Gauthier and
Alexander Jordan and
Peter Schachte and
Harald S{\o}ndergaard and
Peter J. Stuckey and
Chenyi Zhang},
title = {Reference Abstract Domains and Applications to String Analysis},
journal = {Fundamenta Informaticae},
volume = {158},
number = {4},
pages = {297--326},
year = {2018},
doi = {10.3233/FI-2018-1650},
url_Paper = {https://minerva-access.unimelb.edu.au/rest/bitstreams/c17b2e2c-f7ea-57c4-8d54-926629bfa3f7/retrieve},
abstract = {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, each designed 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, enabling
the efficient simulation of reduced products of multiple
string abstract domains.},
keywords = {String analysis, Abstract interpretation},
}
Downloads: 0
{"_id":"4ZgoNnwAhfRzfYRp8","bibbaseid":"amadini-gange-gauthier-jordan-schachte-sndergaard-stuckey-zhang-referenceabstractdomainsandapplicationstostringanalysis-2018","author_short":["Amadini, R.","Gange, G.","Gauthier, F.","Jordan, A.","Schachte, P.","Søndergaard, H.","Stuckey, P. J.","Zhang, C."],"bibdata":{"bibtype":"article","type":"article","author":[{"firstnames":["Roberto"],"propositions":[],"lastnames":["Amadini"],"suffixes":[]},{"firstnames":["Graeme"],"propositions":[],"lastnames":["Gange"],"suffixes":[]},{"firstnames":["François"],"propositions":[],"lastnames":["Gauthier"],"suffixes":[]},{"firstnames":["Alexander"],"propositions":[],"lastnames":["Jordan"],"suffixes":[]},{"firstnames":["Peter"],"propositions":[],"lastnames":["Schachte"],"suffixes":[]},{"firstnames":["Harald"],"propositions":[],"lastnames":["Søndergaard"],"suffixes":[]},{"firstnames":["Peter","J."],"propositions":[],"lastnames":["Stuckey"],"suffixes":[]},{"firstnames":["Chenyi"],"propositions":[],"lastnames":["Zhang"],"suffixes":[]}],"title":"Reference Abstract Domains and Applications to String Analysis","journal":"Fundamenta Informaticae","volume":"158","number":"4","pages":"297–326","year":"2018","doi":"10.3233/FI-2018-1650","url_paper":"https://minerva-access.unimelb.edu.au/rest/bitstreams/c17b2e2c-f7ea-57c4-8d54-926629bfa3f7/retrieve","abstract":"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, each designed 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, enabling the efficient simulation of reduced products of multiple string abstract domains.","keywords":"String analysis, Abstract interpretation","bibtex":"@Article{Ama-Gan-Gau-Jor-Sch-Son-Stu-Zha_FI18,\n author = {Roberto Amadini and \n\t\tGraeme Gange and \n\t\tFran{\\c{c}}ois Gauthier and\n\t\tAlexander Jordan and \n\t\tPeter Schachte and \n\t\tHarald S{\\o}ndergaard and \n\t\tPeter J. Stuckey and\n\t\tChenyi Zhang},\n title = {Reference Abstract Domains and Applications to String Analysis},\n journal = {Fundamenta Informaticae},\n volume = {158},\n number = {4},\n pages = {297--326},\n year = {2018},\n doi = {10.3233/FI-2018-1650},\n url_Paper = {https://minerva-access.unimelb.edu.au/rest/bitstreams/c17b2e2c-f7ea-57c4-8d54-926629bfa3f7/retrieve},\n abstract = {Abstract interpretation is a well established theory that \n\t\tsupports reasoning about the run-time behaviour of programs.\n\t\tIt achieves tractable reasoning by considering abstractions of\n\t\trun-time states, rather than the states themselves. The chosen\n\t\tset of abstractions is referred to as the abstract domain.\n\t\tWe develop a novel framework for combining (a possibly large \n\t\tnumber of) abstract domains. It achieves the effect of the \n\t\tso-called reduced product without requiring a quadratic number\n\t\tof functions to translate information among abstract domains. A\n\t\tcentral notion is a reference domain, a medium for information\n\t\texchange. Our approach suggests a novel and simpler way to \n\t\tmanage the integration of large numbers of abstract domains.\n\t\tWe instantiate our framework in the context of string analysis.\n\t\tBrowser-embedded dynamic programming languages such as \n\t\tJavaScript and PHP encourage the use of strings as a universal\n\t\tdata type for both code and data values. The ensuing \n\t\tvulnerabilities have made string analysis a focus of much\n\t\trecent research. String analysis tends to combine many \n\t\telementary string abstract domains, each designed to capture \n\t\ta specific aspect of strings. For this instance the set of \n\t\tregular languages, while too expensive to use directly for \n\t\tanalysis, provides an attractive reference domain, enabling \n\t\tthe efficient simulation of reduced products of multiple\n\t\tstring abstract domains.},\n keywords = {String analysis, Abstract interpretation},\n}\n\n","author_short":["Amadini, R.","Gange, G.","Gauthier, F.","Jordan, A.","Schachte, P.","Søndergaard, H.","Stuckey, P. J.","Zhang, C."],"key":"Ama-Gan-Gau-Jor-Sch-Son-Stu-Zha_FI18","id":"Ama-Gan-Gau-Jor-Sch-Son-Stu-Zha_FI18","bibbaseid":"amadini-gange-gauthier-jordan-schachte-sndergaard-stuckey-zhang-referenceabstractdomainsandapplicationstostringanalysis-2018","role":"author","urls":{" paper":"https://minerva-access.unimelb.edu.au/rest/bitstreams/c17b2e2c-f7ea-57c4-8d54-926629bfa3f7/retrieve"},"keyword":["String analysis","Abstract interpretation"],"metadata":{"authorlinks":{}},"html":""},"bibtype":"article","biburl":"people.eng.unimelb.edu.au/harald/bibbase.bib","dataSources":["yWvm3kzg5vKQAPLm7","ofmsZryxNDBSpE7j5","9aC4cxLD8D6oJ3FLN","wpkuJrZJJtqra3FbL","XqcrNTrCCBr9mSd37","W7ih7WyQivP4EDh83"],"keywords":["string analysis","abstract interpretation"],"search_terms":["reference","abstract","domains","applications","string","analysis","amadini","gange","gauthier","jordan","schachte","søndergaard","stuckey","zhang"],"title":"Reference Abstract Domains and Applications to String Analysis","year":2018}