Contract-based data structure repair using alloy

Repository

Contract-based data structure repair using alloy

Show full record

Title: Contract-based data structure repair using alloy
Author: Nokhbeh Zaeem, Razieh
Abstract: Contracts and specifications have long been used in object-oriented design, programming and testing to enhance reliability before software deployment. However, the use of specifications in deployed software is commonly limited to runtime checking where assertions form a basis for detecting incorrect program states to terminate the erroneous executions. We present a contract-based approach for data structure repair, which repairs erroneous states in deployed software. The key novelty is the support for rich behavioral specifications, such as those that relate pre-states with post-states of a method to accurately specify expected behavior and precise repair. The approach is based on the view of a specification as a non-deterministic implementation. The key insight is to use any correct state mutations by an otherwise erroneous execution to prune non-determinism in the specification, thereby transmuting the specification to an implementation that does not incur a prohibitively high performance penalty. While invariants, pre-conditions and post-conditions could be provided in different modeling languages, we leverage the Alloy tool-set, specifically the Alloy language and the Alloy Analyzer for systematically repairing erroneous states. Four different algorithms are presented and implemented in our data structure repair framework. These algorithms can repair a medium sized erroneous data structure in a few seconds. We introduce repair guide annotations defined by the user to improve the accuracy and performance of the repair mechanism. Experiments using complex specifications show the approach holds much promise in increasing software reliability.
Subject: Data structure repair Programming by contract Specifications Alloy
URI: http://hdl.handle.net/2152/ETD-UT-2010-05-1055
Date: 2010-05

Files in this work

Download File: NOKHBEH-ZAEEM-THESIS.pdf
Size: 277.8Kb
Format: application/pdf

This work appears in the following Collection(s)

Show full record


Advanced Search

Browse

My Account

Statistics

Information