Automating modular program verification by refining specifications

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008.

Bibliographic Details
Main Author: Taghdiri, Mana, 1979-
Other Authors: Daniel N. Jackson.
Format: Thesis
Language:eng
Published: Massachusetts Institute of Technology 2008
Subjects:
Online Access:http://hdl.handle.net/1721.1/43055
_version_ 1811069662188797952
author Taghdiri, Mana, 1979-
author2 Daniel N. Jackson.
author_facet Daniel N. Jackson.
Taghdiri, Mana, 1979-
author_sort Taghdiri, Mana, 1979-
collection MIT
description Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008.
first_indexed 2024-09-23T08:13:56Z
format Thesis
id mit-1721.1/43055
institution Massachusetts Institute of Technology
language eng
last_indexed 2024-09-23T08:13:56Z
publishDate 2008
publisher Massachusetts Institute of Technology
record_format dspace
spelling mit-1721.1/430552019-04-09T17:28:27Z Automating modular program verification by refining specifications Taghdiri, Mana, 1979- Daniel N. Jackson. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008. Includes bibliographical references (p. 205-211). Modular analyses of software systems rely on the specifications of the analyzed modules. In many analysis techniques (e.g. ESC/Java), the specifications have to be provided by users. This puts a considerable burden on users and thus limits the applicability of such techniques. To avoid this problem, some modular analysis techniques automatically extract module summaries that capture specific aspects of the modules' behaviors. However, such summaries are only useful in checking a restricted class of properties. We describe a static modular analysis that automatically extracts procedure specifications in order to check heap-manipulating programs against rich data structure properties. Extracted specifications are context-dependent; their precision depends on both the property being checked, and the calling context in which they are used. Starting from a rough over-approximation of the behavior of each call site, our analysis computes an abstraction of the procedure being analyzed and checks it against the property. Specifications are further refined, as needed, in response to spurious counterexamples. The analysis terminates when either the property has been validated (with respect to a finite domain), or a non-spurious counterexample has been found. Furthermore, we describe a lightweight static technique to extract specifications of heap-manipulating procedures. These specifications neither are context-dependent, nor require any domain finitizations. They summarize the general behavior of procedures in terms of their effect on program state. They bound the values of all variables and fields in the post-state of the procedure by relational expressions in terms of their values in the pre-state. The analysis maintains both upper and lower bounds so that in some cases an exact result can be obtained. by Mana Taghdiri. Ph.D. 2008-11-07T18:56:55Z 2008-11-07T18:56:55Z 2008 2008 Thesis http://hdl.handle.net/1721.1/43055 243865949 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 211 p. application/pdf Massachusetts Institute of Technology
spellingShingle Electrical Engineering and Computer Science.
Taghdiri, Mana, 1979-
Automating modular program verification by refining specifications
title Automating modular program verification by refining specifications
title_full Automating modular program verification by refining specifications
title_fullStr Automating modular program verification by refining specifications
title_full_unstemmed Automating modular program verification by refining specifications
title_short Automating modular program verification by refining specifications
title_sort automating modular program verification by refining specifications
topic Electrical Engineering and Computer Science.
url http://hdl.handle.net/1721.1/43055
work_keys_str_mv AT taghdirimana1979 automatingmodularprogramverificationbyrefiningspecifications