Memory Usage Verification for OO Programs

Wei-Ngan Chin, Huu Hai Nguyen, Shengchao Qin, Martin Rinard

Research output: Chapter in Book/Report/Conference proceedingConference contribution

102 Downloads (Pure)

Abstract

We present a new type system for an object-oriented (OO) language that characterizes the sizes of data structures and the amount of heap memory required to successfully execute methods that operate on these data structures. Key components of this type system include type assertions that use symbolic Presburger arithmetic expressions to capture data structure sizes, the effect of methods on the data structures that they manipulate, and the amount of memory that methods allocate and deallocate. For each method, we conservatively capture the amount of memory required to execute the method as a function of the sizes of the method’s inputs. The safety guarantee is that the method will never attempt to use more memory than its type expressions specify. We have implemented a type checker to verify memory usages of OO programs. Our experience is that the type system can precisely and effectively capture memory bounds for a wide range of programs.
Original languageEnglish
Title of host publicationStatic analysis
PublisherSpringer-Verlag
Pages70-86
Volume3672
DOIs
Publication statusPublished - 2005
Event12th International Symposium on Static Analysis - London, United Kingdom
Duration: 7 Sep 20059 Sep 2005
Conference number: 12

Publication series

NameStatic Analysis
Volume3672
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference12th International Symposium on Static Analysis
Abbreviated titleSAS 2005
CountryUnited Kingdom
CityLondon
Period7/09/059/09/05

Bibliographical note

Author can archive post-print (ie final draft post-refereeing).

Fingerprint Dive into the research topics of 'Memory Usage Verification for OO Programs'. Together they form a unique fingerprint.

  • Cite this

    Chin, W-N., Nguyen, H. H., Qin, S., & Rinard, M. (2005). Memory Usage Verification for OO Programs. In Static analysis (Vol. 3672, pp. 70-86). (Static Analysis; Vol. 3672). Springer-Verlag. https://doi.org/10.1007/11547662_7