No description available.

Defects in computer programs have great social and economic impacts and should be eliminated as much as possible. Since testing and debugging are among the most costly and time consuming tasks in the software development life cycle, a variety of intelligent debugging aids have been proposed within the last three decades. Model-based software debugging (MBSD) is a particular technique that exploits discrepancies between a program execution and the intended behaviour to isolate program fragments that could potentially explain an observed misbehaviour. In contrast to other techniques, model-based debugging does not require a formal specification of a program's behaviour, making the approach suitable for developers without training in formal software engineering practices. A key aspect of model-based debugging is the transformation of the given program into a model suitable for debugging. In this thesis, several models for analysing programs written in an object-oriented language are investigated, with Java as concrete example. The aim of this work is to assess the suitability of value-based models and generalisations thereof for debugging of programs making use of dynamically allocated data structures, recursive methods and polymorphic method invocations.

The use of formal methods in software development seeks to increase our confidence in the resultant system. Their use often requires tool support, so the integrity of a development using formal methods is dependent on the integrity of the tool-set used. Specifically its integrity depends on the theorem prover, since in a typical formal development system the theorem prover is used to establish the validity of the proof obligations incurred by all the steps in the design and refinement process. In this thesis we are concerned with tool-based formal development systems that are used to develop high-integrity software. Since the theorem prover program is a critical part of such a system, it should ideally have been itself formally verified. Unfortunately, most theorem provers are too complex to be verified formally using currently available techniques. An alternative approach, which has many advantages, is to include a proof checker as an extra component in the system, and to certify this. A proof checker is a program which reads and checks the proofs produced by a theorem prover. Proof checkers are inherently simpler than theorem provers, since they only process actual proofs, whereas much of the code of a theorem prover is concerned with searching the space of possible proofs to find the required one. They are also free from all but the simplest user interface concerns, since their input is a proof produced by another program, and their output may be as simple as a `yes/no' reply to the question: Is this a valid proof? plus a list of assumptions on which this judgement is based. When included in a formal development system a stand-alone proof checker is, in one sense, superfluous, since it does not produce any proofs -- the theorem prover does this. Instead its importance is in establishing the integrity of the results of the system -- it provides extra assurance. A proof checker provides extra assurance simply by checking the proofs, since all proofs have then been validated by two independent programs. However a proof checker can provide an extra, and higher, level of assurance if it has been formally verified. In order for formal verification to be feasible the proof checker must be as simple as possible. In turn the simplicity of a proof checker is dependent on the complexity of the data which it processes, that is, the representation of the proofs that it checks. This thesis develops a representation of proofs that is simple and generic. The aim is to produce a generic representation that is applicable to the proofs produced by a variety of theorem provers. Simplicity facilitates verification, while genericity maximises the return on the effort of verification. Using a generic representation places obligations on the theorem provers to produce a proof record in this format. A flexible recorder/translator architecture is proposed which allows proofs to be recorded by existing theorem provers with minimal changes to the original code. The prover is extended with a recorder module whose output is then, if necessary, converted to the generic format by a separate translator program. A formal specification of a checker for proofs recorded in this representation is given. The specification could be used to formally develop a proof-checker, although this step is not taken in this thesis. In addition the characteristics of both the specification and possible implementations are investigated. This is done to assess the size and feasibility of the verification task, and also to confirm that the design is not over-sensitive to the size of proofs. This investigation shows that a checker developed from the specification will be scalable to handle large proofs. To investigate the feasibility of a system based on this architecture, prototype proof recorders were developed for the Ergo 5 and Isabelle 98 theorem provers. In addition a prototype checker was written to check proofs in the proposed format. This prototype is compatible with the formal specification. The combined system was tested successfully using existing proofs for both the Ergo 5 and Isabelle 98 theorem provers.