 Executive Summary
e goal of our project is to investigate the fundamental problem that plagues all software development: the gap between the intentions of the designer, as described (often only minimally) in design and specification documents, and the behaviour of the delivered system, as realized in the code.
We are developing new languages, tools and methods to address this problem. Our work also incorporates independent analyses of designs and code. By applying our design analyses, we can be sure that the design as described has the intended consequences the designer had in mind. By applying our code analyses, we can eliminate flaws that do not depend on comparison to a design, and can discover properties that can be later fed into a conformance analysis.
Rather than pursuing a single, narrow research approach, we have tried to explore the problem from many angles. We consider how a codebase may be analyzed in the presence of some design models; how it might be analyzed if there is no explicit design documentation; and how minimal design properties expressed as code annotations might be exploited. We have developed static analyses that require no execution of the code but can simulate the effect of all possible executions, and dynamic analyses that require a test suite but can produce more accurate results. Some of our static analyses are conservative, and can guarantee properties of all executions; others are sound in their error reports, so that no false alarms are given. Some of our tools exploit test cases; others generate test cases automatically.
Despite the breadth of our approaches, all our work satisfies some fundamental criteria. It is principled and at the same time pragmatic. Being principled means that we are not content to develop ad hoc approaches that may work well in the short term, but which rely on inconsequential properties of particular systems
2 or current development approaches. Rather, we aim to make fundamental advances that will change the way software is constructed and analyzed. Being pragmatic means that we are all the time focused on real applications, and take issues of scale and usability seriously.
An extensive collection of case studies attests to this commitment. In particular, this year has seen the completion of a prototype air-traffic control tool, on which we have already conducted evaluations of several of our analyses. We have also been engaged in a joint project with Massachusetts General Hospital and Ion Beam Applications Inc. to apply our ideas to their proton therapy system, and have already had some success in discovering previously unknown and important properties of the system using our analyses.
In addition to these criteria, the many subprojects that constitute our work are woven together by several intellectual threads. Most prominent of these, as described in our original ITR proposal, is the use of relational logic to understand the structure and behaviour of software. e modelling language of our design analyzer is based on such a logic; the annotations used by or data structure repair tool are based on the same logic; our design extractors and role discovery tools deliver descriptions of relationships between objects that take the same logical viewpoint.
Our work in the last year has had many flavours. Some subprojects have consolidated earlier work and demonstrated its applicability to real systems: witness, for example, the application of Alloy to the analysis of file synchronizers, or the use of our test case generation framework to find bugs in a NASA fault-tree analyzer. Some subprojects have taken research ideas from speculation to initial prototype: witness, for example, the successful application of data structure repair to the CTAS air-traffic control system. Some subprojects have developed new research ideas or dramatically expanded existing ideas: witness, for example, our work on ownership types, or the new scheme for detecting overconstraint in design models using the ‘unsatisfiable core’ facility of SAT solvers.