What do we mean by quality? Matthew Wilson considers some definitions.
In the previous instalment I defined correctness as 'the degree to which a software entity's behaviour matches its specification' [QM-1], but didn't offer definitions of robustness or reliability. This time I'm going to take the plunge and attempt definitions of them. I embark on a (possibly deranged) attempt to equate computing with the worlds of Newtonian and Quantum Physics, along with the somewhat more obvious parallel drawn between the behaviour of software systems and chaos theory.
I'll do my best to keep my feet on planet Earth by using examples from real-world experience, illustrating how some software entities can be established to be correct, but the best we can hope for with most is to ensure adequate levels of robustness. I'll also comment on why correctness may be of no interest to non-programmers, and reliability is not of much interest to programmers.
Weaving together a cogent narrative for this instalment has been exceedingly difficult, and you may well feel that it's escaped me. If so, all I can say is watch out for the instalment on contract programming!
Before I can begin to pontificate about robustness and reliability, I need to consider the definitions that currently exist in the canon.
Correct: Free from error; accurate; in accordance with fact, truth, or reason. Conforming to acknowledged standards of style, manners, or behaviour; proper.
Robust: Strong and sturdy in physique or construction. Involving or requiring bodily or mental strength or hardiness. Strong, vigorous, healthy; not readily damaged or weakened.
Reliable: That which may be relied on; in which reliance or confidence may be put; trustworthy, safe, sure.
Correctness: The degree to which a system is free from [defects] in its specification, design, and implementation.
Robustness: The degree to which a system continues to function in the presence of invalid inputs or stressful environmental conditions.
Reliability: The ability of a system to perform its requested functions under stated conditions whenever required - having a long mean time between failures.
Correctness: The ability of software products to perform their exact tasks, as defined by their specification.
Robustness: The ability of software systems to react appropriately to abnormal conditions.
Reliability: A concern encompassing correctness and robustness.
Without a specification against which to compare behaviour, the notion of correctness is meaningless.
The important aspect taken from McConnell [CC] is that correctness is a variable notion, and that a software entity's behaviour may correspond to a specification to a certain degree. At first blush this may seem a bizarre idea. Certainly, a software entity that is known to fail to meet its specification is defective (aka incorrect), plain and simple. From the perspective of a potential user of a software entity, that its creator (or any other agent) may volunteer that it is 50% correct or 90% correct is of no use, because such figures, even if obtained by repeatable quantitative measurements, e.g. unit-tests, cannot be meaningfully used in the calculation of quantitative failure probabilities of a software system built from the offending entity. We'll discuss why in the next section.
Beyond this, there are other, serious, objections to attempting to make use of a software entity that is known to be defective - something known as the Principle of Irrecoverability - but those discussions will have to wait until another time.
So what is the purpose of considering correctness as a quantitative concept (in addition to its being a relative one)? Well, there are the practical benefits to the producers of a software entity in being able to quantify its degree of divergence from a specification. Of course, we all know that any given defect can, upon cursory examination, appear to be of the same magnitude (of corrective development effort) as another, and yet take two, five, ten, sometimes hundreds of times longer to correct. But averaged out over the course of a project, team, career, there is a usefulness to being able to quantify. Certainly, when I'm developing software libraries, I can take the temperature for the project velocity (if you'll pardon the atrocious mixing of my metaphors) via the defect fix rate in a new (or regressive) group of tests.
The third state is somewhat like poor old Schrödinger's cat [GRIBBIN], who is neither dead nor alive until examined. So too, software can be correct, or defective, or neither (known to be) correct nor defective. The latter state collapses into exactly one of the former when it is evaluated against a specification.
In this instalment I'm going to consider the notion that most, perhaps all, software systems are built up from layers of abstraction most of which are in the disconcerting third state of uncertain correctness. Furthermore, I'm going to argue that software has to be like this, and that's what makes it challenging, fun, and not a little frightening.
Exactitude, non-linearity, Newtonian software, quantum execution environments, and why Software Development is not an engineering discipline.
A perennial debate within (and without) the software community is whether software development is an engineering discipline, and, if not, why not. Well, despite plentiful (mis)use of the term 'software engineer' in my past, I'm increasingly moving over to the camp of those whose opinion is that it is not an engineering discipline. To illustrate why I'm going to draw from three of my favourite branches aspects of science: Newtonian physics, Chaos theory, and Quantum physics, with a modicum of logic thrown in for good measure.
The Unpredictable Exactitude Paradox: Software entities are exact and act precisely as they are programmed to do, yet the behaviour of (non-trivial) computer systems cannot be precisely understood, predicted, nor relied upon to refrain from exhibiting deleterious behaviour.
Consider the behaviour of the computer on which I'm writing this epistle. Assuming perfect hardware, it's still the case that the sequence of actions - involving processor, memory, disk, network - carried out on this machine during the time I've written this paragraph have never been performed before, and that it is impossible to rely on the consequences of those actions. And that is despite the fact that the software is doing exactly what it's been programmed to do.
I mentioned earlier that the relationship between the size/number of defects and the effort involved to remedy them is not linear. This non-linearity is also to be seen in the relationship between the size/number of defects and their effects. Essentially, this is because software operates on the certain, strict interpretation of binary states, and there are no natural attenuating mechanisms in software at the scale of these states. If one Iron atom in a bridge is replaced by, say, a Molybdenum atom, the bridge will not collapse, nor exhibit any measurable difference in its ability to be a bridge. Conversely, an errant bit in a given process may have no effect whatsoever, or may manifest benignly (e.g. a slightly different hue in one pixel in a picture), or may have major consequences (e.g. sending confidential information to the wrong customer).
We, as software developers, need language to support our reasoning and communication about software, and it must address this paradox, otherwise we'll be stuck in fruitless exchanges, often between programmers and non-programmers (clients, users, project managers), each of whom, I believe, tend to think and see the software world at different scales. I will continue the established use of the term correctness to represent exactitude. And I will, influenced somewhat by Meyer and McConnell, use the terms robustness and reliability in addressing the inexact, unpredictable, real behaviour of software entities.
In fact, it'd be pretty hard to write any implementation other than this. Certainly there are plenty of (possibly apocryphal) screeds of long-winded alternative implementations available on the web (such as on www.thedailywtf.com), but pretty much any functionally correct implementation that does not involve fatuous complexity/dependencies - such as converting value to string and them using strcmp() against "0" or "1" - will evaluate to the following pseudo-machine code in Listing 1.
With languages that have a bona-fide Boolean type, such as Java and C#, the value may not need to be compared against 0, and may well be implemented as equal to true (or to false). Other languages such as C and C++ represent (for historical and performance reasons [IC++]) a notional Boolean false value as being 0, and a notional Boolean true value as being all non-0 values. In those, comparison against zero is necessary, even for their built-in bool types! In either case, it's almost impossible to implement this function incorrectly.
If we permit ourselves the luxury of assuming a correctly functioning execution environment, then without recourse to any automated techniques, or even to a detailed written specification, we may reasonably assert the correctness of this function by visual inspection.
Then (being as how I'm writing a column about software quality, and my Spidey-sense is set to max) I stopped and wondered how this would work between compilation contexts where char is signed or unsigned. Clearly, for certain ranges of values, the negation result will be different between the two. I then immediately set about writing a test program, and building for both signed and unsigned modes, and saw the suspected different behaviour for certain strings (with values in the range 0x80 - 0xff).
My next instinct was to include stlsoft/stlsoft.h - STLSoft has limited C-compatibility - and write the implementation in an STLSOFT_CF_CHAR_IS_UNSIGNED-dependent manner. Serendipitously, it was at this point that I thought to check with the C-99 standard, in order to verify my recollection that the return values could be any negative value for less-than (rather than strictly -1) and any positive value for greater-than (rather than strictly +1). What I was wrily amused to learn (and not a little appalled to have forgotten/not known) was that clause 7.21.4(1) stipulates that the return value 'is determined by the sign of the difference between the values of the first pair of characters (both interpreted as unsigned char) that differ in the objects being compared'. I've been programming C for, ulp!, 21 years, and have written several implementations of strcmp() (which, by happy coincidence, have done the right thing), but either I've forgotten that comparison was to be done unsigned, or I never knew it in the first place. Either way, it's quite sobering.
Here's an implementation I knocked up during the preparation of this instalment, without recourse to any I've written in the past (or to various open-source and commercial implementations).
If this smells suspiciously like a contract pre-condition [OOSC, IC++], well, that's something we'll examine in a later instalment.
The possibility of the latter two options makes reasoning about the correctness of strcmp() and software entities build in terms of it more complicated than is the case for invert(). Specifically, it is possible for strcmp() to be passed invalid arguments (as a result of a defect elsewhere within the program), whereas all 'physically' possible arguments to invert() are valid.
The next Bet-Your-Life? Test case is b64_encode() (see Listing 2).
I'm not going to show the full implementation of this for brevity's sake. (If you're interested you can download the library [B64] and see for yourself.) Like strcmp() (and invert()), the b64 library has no dependencies on any other software libraries, not even on the C runtime library (except when contracts are being enforced, e.g. in debug builds). This permits a substantial level of confidence in behaviour, because only the b64 software entities themselves are involved in such considerations. Broadly speaking, it means that behaviour, once 'established', can be relied on regardless of other activities in the execution environment. However, it's fair to say that the internal complexity of b64_encode() is substantially increased over that of strcmp(). Consequently, I think it is impossible in a library such as this to stipulate its correctness based on visual inspection of the code; anyone who would do so would be rightly seen as reckless (at best).
The function conducts a search of the file-system location specified by searchRoot, looking for entries that match the given patterns, according to the given search flags. If a file-system search can be initiated then a search context is created and assigned to *phSrch (to be used to elicit search results via other API functions), and a success return code returned; if not, a failure code is returned.
If searchRoot is NULL or empty, the current directory is used.
If patterns is NULL, the 'all entries' pattern - "*" on UNIX, "*.*" on Windows - is assumed.
Multi-part patterns may be specified, separated by the '|' symbol, e.g. "makefile*|*.c"
Clearly the recls library (or at least this part of it) has substantial behavioural complexity. That alone makes it, in my opinion, impossible for any reasonable developer to stipulate its correctness. But that's only part of it. Of greater significance is that recls is implemented in terms of a great many other software entities, including library components (from STLSoft) and operating system facilities (e.g. the opendir() API on UNIX and the FindFirstFile() API on Windows). And even that is not the major issue. The predominant concern is that recls interacts with the file-system, whose structure and contents can (and do) change independently of the current process. By definition, it is impossible to establish correctness for recls or any other software entities who interact with aspects of the execution environment that are subject to change from other, independent software entities.
By now you're probably starting to worry now that I'm asserting that correctness cannot be stipulated. Am I saying that software cannot be correct?
At the risk of embarrassing myself, because it's been 20 years since I did any formal study of the subject, I will now draw parallels between software+hardware and Newtonian+quantum physics.
Consider a point object travelling through an empty universe. In Newtonian physics, the object will continue to travel in the same line, at the same speed, forever more. If there are two point objects, they will influence each other's travel in predictable ways, based on their masses, positions and velocities. But add in a third, fourth, ... trillionth object, and the behaviour of the universe becomes complex, and therefore unpredictable (beyond small timescales within which simplifying assumptions may be used to form reasonable approximate results). As is the case in reality, if the objects are non-point, then we have to consider rotation of the bodies, and heat, and a whole lot more besides, including chemistry, biology, even sociology and technology! Thus, even in a Newtonian universe, behaviour is non-linear (and unpredictable) due to the interactions of entities (in part because some of the quantities involved are irrational, and calculations thereby require infinite precision).
Specification: A software entity's specification is the sum of all its passing unit-tests.
Specification: A software entity's specification is the sum of all its unfired active contract enforcements.
Everything else is fluff and air.
Given the forgoing discussion, I'm now in a position to offer my definitions of these three important aspects of software quality.
Correctness: The degree to which a software entity's behaviour matches its specification.
Robustness: The adjudged ability of a software entity to behave according to the expectations of its stakeholders.
Reliability: The degree to which a software system behaves robustly over time.
Correctness is exact and measurable. It is the concern of software developers.
When measured (against its specification), the correctness of a software entity 'collapses' from the unknown state to exactly one of two states: correct and defective.
The binary nature of measured correctness is a great thing. For example, consider that we measure the correctness of invert() as shown in Listing 3 (assuming a C# implementation, with NUnit [NUNIT]).
That's a complete functional test for BetYourLifeTests.Invert(). Informed by this, we could now implement another function, Nor(), as shown in Listing 4 (sticking with C#).
Knowing that Invert() is correct, we may choose to assert that Nor() will faithfully give expected behaviour based on visual inspection. And we could go on to completely measure that correctness with ease, involving just four unit-tests.
However, add in just a little complexity and things get sticky very quickly. Consider that we've measured strcmp()'s correctness against a unit-test suite as shown in Listing 5, this time in C, with xTests [XTESTS].
Clearly, this is not a comprehensive test suite. But the permutations of arguments passed to strcmp() in the myriad programs built from it will dwarf that found in any unit-test suite. Consequently, we are all using strcmp() beyond its specification. Specifically, we are using strcmp() in a state of unknown correctness. How do we get away with it? We apply judgement.
A correct software entity has been proven so by mechanical means. A robust software entity has been judged as likely to behave according to expectations. This judgement is based on our knowledge of the software entity's interface, its likely complexity, its author(s), its published test suite, the skills and experience of the judge, and many other factors.
What can we say about the correctness of f()? Well, until we test it, by definition it has unknown correctness. But howsoever we make use of it - whether in test or in a software application - we are using strcmp() outside the bounds of its specification, because "fgh" is not included in strcmp()'s test suite. By definition, therefore, we will be using strcmp() in a manner in which its correctness is unknown.
Consider that we now write a suite of tests for f(), as in Listing 6.
Since we have a specification for f(), and f() meets that specification, we can state that f() is correct. However, there is something a little strange about having a component that is correct when it is implemented using another component that has unknown correctness.
Taking this notion to extreme, we might wonder whether we can implement a correct software entity in terms of a defective one? Let's imagine that our implementation of strcmp() always returns a value of 0 when passed a string of less than three characters. With this behaviour it would fail four of the tests of its specification and thus be proven defective. But since the test suite for f() always uses strings of length three, it would still pass all cases. f() is proven correct, yet is implemented in terms of a defective component. That is more than a little strange, and violates the robustness principle given above.
The answer to this apparent conundrum lies in the notion of robustness. Confidence is placed in a software entity based on a number of factors, knowing that it will be used outside the exact, but necessarily limited, aspects of its specification. An implementation of f() that uses a correct strcmp() outside the bounds of its specification is, while common, something that should give pause for thought. An implementation of f() that uses a defective implementation of strcmp() violates the robustness principle and, in my opinion, should never be countenanced.
In both cases, the implementation of f() is brittle. And as each layer of abstraction and dependency is added, this brittleness spreads and compounds, and the combinatorial cracks through which extra-correctness behaviour can permeate increase. Thus, an important part of the skill/art of the software developer list in making judgements about robustness when implementing software entities in terms of others that have unknown correctness (and that must therefore be judged on their robustness).
Robustness is inexact and subjective. It cannot be measured or proven, and it cannot be automated (beyond a few static analysis tricks). It is equally the concern of software developers, who must provide it, and stakeholders, whose experiences of the software system define it.
I am moved to almost completely agree with McConnell's definition of reliability, but I do feel that reliability is a measurable, quantifiable, emergent property of a software system's behaviour. In some senses, it could be thought of as robustness over time, but robustness can't measured, so maybe it's better thought of as apparent robust action over time.
Reliability is more a concern to stakeholders than it is to developers, reflecting the differing perspectives between these groups. To stakeholders, it is almost entirely irrelevant how many constituent software entities were correct versus those adjudged robust. To stakeholders, the proof of the pudding is the eating, and that's its reliability.
Naturally, I'm not suggesting that tuning software failure frequencies is a good thing; I believe that we can all write much more robust software without suffering in the process. That's the raison d'être of this column, and as we proceed I intend to pursue the notion that we should all be aiming for maximum quality all the time.
At this point I'd intended to go on to examine some of the interesting conflicts between correctness and robustness, and between them and other software characteristics, as well as discussing practical techniques for ensuring robustness when correctness is not achievable. I've even got an argument in favour of Java's hateful checked exceptions. But I've run out of space (and time), and these will have to wait until another instalment.
For the moment, I'll posit a parting rubric that correctness is the worthy aim wherever possible (which is rare), and robustness is the practical must-have in all other circumstances.
I'm not sure what's coming in the next instalment, but I'm determined that it's going to have a lot more code, and a lot less philosophy than this one. It's too exhausting!
[SOED] The New Shorter Oxford English Dictionary, Thumb Index Edition, ed. Lesley Brown, Clarenden Press, Oxford, 1993.