Contract-based data structure repair using alloy

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.