Back to search

University of British Columbia

A logic and decision procedure for verification of heap-manipulating programs

Abstract

dc:description

Heap-manipulating programs (HMPs), which manipulate unbounded linked data structures via pointers, are a major frontier for formal verification of software. Formal verification is the process of proving (or disproving) the correctness of a system with respect to some kind of formal specification or property. The primary contributions of this thesis are the definition of a simple transitive closure logic tailored for formal verification of HMPs, and an efficient decision procedure for this logic. To assess the effectiveness of the proposed approach, we develop an HMP verification framework, which uses our fast implementation of the decision procedure to verify a number of HMP examples. Experimental examples (including three small container functions from the Linux kernel) demonstrate that the logic is practically useful and expressive enough to prove many interesting heap properties. In addition, the decision procedure provides a substantial time and space advantage over previous approaches.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2006

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Rakamarić, Zvonimir

Rights

dc:rights
Statement dc:rights
  • For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/18130

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Rakamarić, Zvonimir. A logic and decision procedure for verification of heap-manipulating programs. master's thesis, University of British Columbia, 2006. http://hdl.handle.net/2429/18130