Accumulation analysis

Download: PDF, slides (PDF), implementation, artifact.

“Accumulation analysis” by Martin Kellogg, Narges Shadab, Manu Sridharan, and Michael D. Ernst. In ECOOP 2022 — Object-Oriented Programming, 33rd European Conference, (Berlin, Germany), June 2022, pp. 10:1-10:31.

Abstract

A typestate specification indicates which behaviors of an object are permitted in each of the object's states. In the general case, soundly checking a typestate specification requires precise information about aliasing (i.e., an alias or pointer analysis), which is computationally expensive. This requirement has hindered the adoption of sound typestate analyses in practice.

This paper identifies accumulation typestate specifications, which are the subset of typestate specifications that can be soundly checked without any information about aliasing. An accumulation typestate specification can be checked instead by an accumulation analysis: a simple, fast dataflow analysis that conservatively approximates the operations that have been performed on an object.

This paper formalizes the notions of accumulation analysis and accumulation typestate specification. It proves that accumulation typestate specifications are exactly those typestate specifications that can be checked soundly without aliasing information. Further, 41% of the typestate specifications that appear in the research literature are accumulation typestate specifications.

Download: PDF, slides (PDF), implementation, artifact.

BibTeX entry:

@inproceedings{KelloggSSE2022,
   author = {Martin Kellogg and Narges Shadab and Manu Sridharan and
	Michael D. Ernst},
   title = {Accumulation analysis},
   booktitle = {ECOOP 2022 --- Object-Oriented Programming, 33rd European
	Conference},
   pages = {10:1-10:31},
   address = {Berlin, Germany},
   month = jun,
   year = {2022}
}

(This webpage was created with bibtex2web.)

Back to Michael Ernst's publications.