This book is about the use of techniques and tools for the design and implementation of computer systems and software that are free from logical or functional flaws (in the sense of functional requirements). The word rigorous in the title of this book is justified by the fact that the arguments for such fault freeness have their roots in computer science, logic and mathematics rather than in empirical and statistical studies. In this sense this book will address concepts and techniques for fault avoidance rather than fault tolerance (which in itself represents a rich and very important area in computer system and software engineering).
1.1 A Formal Approach to Software Engineering
The importance of the role of information systems in essential sectors of contemporary societies is more and more prevalent. Transport, communications, health and energy are all representative examples. The rapid growth in terms of complexity of the computing infrastructures and software that underly and accompany the evolution of these systems has made it harder to have confidence on their reliability. Being able to establish that a system behaves as it is supposed to is now more delicate than ever.
Even though most software errors lead to no more than minor upsets, the situation is quite different when so-called critical systems are concerned. Classic examples of these include nuclear and medical equipment. The correct behaviour of the software components of these systems is essential. We nowadays live in a massively networked and digital era, and the emergence of new and sometimes revolutionary technologies only contributes to reinforce the need for the software to enjoy adequate correctness properties. Think for instance of the tremendous, but also invisible, introduction of information systems in the daily life of citizens (by means of ubiquitous and pervasive information systems or embedded and mobile systems).
The attention given by the media to the possibly bombastic effects of conception errors in information systems also has a role in creating a certain hype around the reliability of software. Governments, industrial consortia, and plain system users have all decidedly become more conscious of this, and now increasingly demand that reliability be established. Let us look at a concrete and classic example of this phenomenon: in 1994 the popular science publication Scientific American published an article stating []:
Despite 50 years of progress, the software industry remains yearsperhaps decadesshort of the mature engineering discipline needed to meet the needs of an information-age society.
Regrettably, the software industry has for a long time had a reputation for not being able to keep to any reliability or robustness commitments. In fact, the existence of bugs in commercial systems is so common that companies now systematically include a bug report system with each release. To mention some data, in 2002 the North-American Institute for Standards and Technologies estimated the cost of bugs in the American economy to ascend to 59 billion dollars.
From the point of view of information system designers, product quality in terms of reliability is certainly a commercial concern. Goguen []. Beyond the financial impact, the media emphasized the loss of confidence shown by Intel users (i.e. the computer manufacturing industry) that had a much broader and dramatic effect to the company.
It is extremely hard to certify in an absolute way the behaviour of a system. However, if absolute correctness may be illusory, reinforcing the degree of reliability and confidence that one can have in a product are still a central and well justified concern. For illustration purposes consider the following well-known facts in software engineering: the cost of maintaining software is about two thirds of its total cost, and a software specification fault is about 20 times more costly to repair if detected after production than before.
This state of affairs has been tackled by industry in a number of different ways, but the most popular weapon has certainly been program testing and simulation.
1.1.1 Test and Simulation-Based Reliability
A classic approach to ensuring the adequacy of a software system is testing or simulation . This consists in producing a set of data believed to be representative, giving it as input to the system (or a model thereof), and then comparing the outputs obtained with the set of expected outputs. Unfortunately, testing cannot be totally satisfying: for the vast majority of systems, the value space is immense (if not infinite), which renders exhaustive testing impracticable (if not impossible).
A relative notion of reliability, let us call it confidence , is obtained from a judicious choice of entry values, which should affect the greatest possible number of components of (the control flow graph of) the system under test. Of course, the complexity of the choice of input values is directly related to the complexity of the system, and for very complex systems reliability becomes very hard to guarantee. This is a particularly important point when one discusses how to ensure the robustness of a production-level system, since many problems are in fact triggered by an unexpected use of resources.
In spite of all this, as was already pointed out, the popularity of testing as a practice is huge in industry, due to several reasons. One reason is its acceptance by certification bodies, that typically consider its conclusions as valid, up to some considerations such as test coverage analysis. In fact, test engineering is a reasonably well understood and mature discipline, whose expertise is now well integrated in industry.
1.1.2 An Alternative Approach: Formal Methods
Formal methods constitute an alternative, mathematical approach to reliability assurance, to which industry is progressively devoting more attention. In fact, not only is the need for formal methods increasingly more pressing, but the maturity of their underlying mechanisms is now more adequate for industrial use than it has been in the past, when it was extremely hard for non-specialists to be able to use formal methods tools. The perceived utility of formal methods is thus more and more indisputable.