Towards Increased Verification Automation for High Integrity Software Engineering

by Andrew Ireland

The proliferation of safety and security critical software applications represents a key challenge for today's software engineers. Within the context of the SPARK approach to high integrity software development, the NuSPADE project is addressing this challenge through the integration of novel automated reasoning and program analysis techniques.

Formal verification involves the use of mathematical logic and formal reasoning techniques in proving properties of software and hardware systems. Early work on formal verification focused on proving full functional correctness. In the area of software verification, the complexity of software and the lack of effective tools limited the applicability of this approach. The focus has moved away from full functional correctness to property based formal verification. That is, proving properties of software that are of interest to the developers and the customers. This property based approach can be used to verify desired properties as well as undesirable properties, ie show the presence of software bugs. The advantage of the property based approach is that the verification task is much simpler than full functional correctness and therefore increases the level of automation that can be achieved. Moreover, the properties of interest are typically generic, ie properties that are applicable across a wide range of applications. This means that programmers are not required to hand craft the properties. Notable successes in this area are the SLAM (Microsoft Research) and ESC/Java (HP Labs) projects. The NuSPADE project builds upon another success story for the property based approach, namely the SPARK approach to high integrity software development (Praxis Critical Systems). The SPARK approach advocates 'correctness by construction', where the focus is on bug prevention rather than bug detection. SPARK has been applied successfully across a wide range of applications including railway signalling, smartcard security and avionics systems such as the Lockheed C130J and EuroFighter projects. The approach has been recently (April 2004) recognized by the US National Cyber Security Partnership as one of only three software development processes that can deliver sufficient assurance for security critical systems.

NuSPADE integrates proof planning and program analysis within the context of the SPARK approach to high integrity software development. The SPARK Examiner (Praxis) performs various levels of quality and consistency checks as well as generating verification conditions (proof obligations). For verification conditions that the SPARK toolkit (SPADE Simplifier) fails to prove, a proof planner is used to search for a proof. During this proof search a program analyzer may be used in order to induce auxiliary program annotations (specifications) that are necessary in order for the proof search to succeed. A successful proof planning attempt generates a command file description of a proof which is then checked using the SPARK toolkit (SPADE Proof Checker).

The SPARK programming language is defined as a subset of Ada which is expressive enough for industrial applications, but restrictive enough to support rigorous analysis early in the development process. In particular, SPARK supports a language of program annotations and associated tools. The annotations allow the programmer to specify the intended behaviour of their programs, while the toolset supports the verification of the specifications. The formal verification capabilities of SPARK are most commonly used for what are known as exception freedom proofs, ie proving that a system is free from run-time errors. Within safety critical applications, run-time errors may give rise to catastrophic failures, eg an integer overflow run-time error led to the loss of Ariane 5. The same holds true for security critical applications, eg buffer overflows have been the most common form of security vulnerability in the last ten years. The ability to verify that software applications are free of such undesirable behaviour has obvious social and economic benefits. The SPARK approach has had significant success in automating exception freedom proofs through the SPADE Simplifier, a special purpose automated reasoning tool.

The goal of the NuSPADE project has been to build upon this success and increase the level of proof automation in general, and for exception freedom proofs in particular. There are two key problems. Firstly, to increase the proof automation and, secondly, to automate the program annotations that are required in order to support the proof process. Our starting point is proof planning; a computer-based technique for automating the search for proofs. At the core of the technique are high-level proof outlines, known as proof plans. Proof plans encode heuristic knowledge that is used in automating the search for proofs. A key feature of proof planning is that it separates proof search from proof checking. This gives greater flexibility in the strategies that can be used in guiding proof search as compared to conventional proof development environments. Proof critics are an example of this greater flexibility. Proof critics support the automatic analysis and patching of proof planning failures. Within the NuSPADE project we have broadened their role, ie we use proof critics to provide a tight integration between proof planning and program analysis (see Figure). For example, certain classes of proof-failures can be attributed to the need for additional knowledge about the program being verified. This additional knowledge is added through SPARK program annotations. Typically these annotations are crafted by the programmer after they have analyzed a proof-failure. Within NuSPADE we have been able to reduce the need for hand crafted annotations, ie we have been able to automate the proof-failure analysis and use the analysis to generate the required program annotations automatically.

NuSPADE is a three year project which is funded by the UK's Engineering and Physical Sciences Research Council (EPSRC) and is in collaboration with Praxis Critical Systems. The project is entering its final evaluation phase which will involve applying the techniques to industrial strength applications. A follow-on project is planned through EPSRC's Research Assistants Industrial Secondments (RAIS) scheme. The aim of the RAIS scheme is to support knowledge transfer where a research project has had a strong industrial collaborative component. The RAIS project will provide the first step towards technology transfer.
The technique of proof planning originated within the Mathematical Reasoning Group (MRG) at the University of Edinburgh. The NuSPADE project and the development of the proof planning technique within the area of software verification has been pioneered within the Dependable Systems Group (DSG) at Heriot-Watt University. The DSG and the MRG have collaborated closely over nearly ten years in the area of automated software engineering.

Links:
http://www.macs.hw.ac.uk/nuspade
http://www.praxis-cs.co.uk/sparkada
http:/www.macs.hw.ac.uk/dsg

Please contact:
Andrew Ireland, Heriot-Watt University,
Edinburgh, Scotland, UK
Tel: +44 131 451 3409
E-mail: a.irelandhw.ac.uk