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.
Reference Abstract Domains and Applications to String Analysis [link]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