Abstract interpretation over non-lattice abstract domains

Graeme Gange, Jorge A. Navas, Peter Schachte, Harald Søndergaard, Peter J. Stuckey

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

12 Citations (Scopus)

Abstract

The classical theoretical framework for static analysis of programs is abstract interpretation. Much of the power and elegance of that framework rests on the assumption that an abstract domain is a lattice. Nonetheless, and for good reason, the literature on program analysis provides many examples of non-lattice domains, including non-convex numeric domains. The lack of domain structure, however, has negative consequences, both for the precision of program analysis and for the termination of standard Kleene iteration. In this paper we explore these consequences and present general remedies.

Original languageEnglish
Title of host publicationStatic Analysis - 20th International Symposium, SAS 2013, Proceedings
PublisherSpringer
Pages6-24
Number of pages19
ISBN (Print)9783642388552
DOIs
Publication statusPublished - 26 Sep 2013
Externally publishedYes
Event20th International Static Analysis Symposium, SAS 2013 - Seattle, WA, United States of America
Duration: 20 Jun 201322 Jun 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7935 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference20th International Static Analysis Symposium, SAS 2013
CountryUnited States of America
CitySeattle, WA
Period20/06/1322/06/13

Cite this

Gange, G., Navas, J. A., Schachte, P., Søndergaard, H., & Stuckey, P. J. (2013). Abstract interpretation over non-lattice abstract domains. In Static Analysis - 20th International Symposium, SAS 2013, Proceedings (pp. 6-24). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7935 LNCS). Springer. https://doi.org/10.1007/978-3-642-38856-9_3