Testing for real!Academics are often chided for doing research that is only of theoretical interest and has no practical significance.Many outside the academic world would probably argue that a dose of reality would do us good and that, to use common parlance, academics should 'get real'.The theme of software testing in the real world was highlighted in the opening keynote talk at UK-Test 2005, the Third U.K. Workshop on Software Testing Research held at the University of Sheffield in the U.K. in September 2005 * .Paul Gibson, the Development Operations Manager at IBM Hursley, spoke on 'Testing Challenges for IBM'.Having reminded the audience of the range of IBM software in the marketplace, Gibson started by quoting Watts Humphrey who, in the past, has stated that 'coders introduce bugs at the rate of 4.2 defects per hour of programming' † .A more recent statement by Humphrey [1] puts the figure at the higher rate of 4.6 defects per hour for experienced developers designing as they code, with a lower rate of 2.0 defects per hour for developing a detailed design in advance of coding.Anyway, to emphasize his case, Gibson extrapolated the figure for defects per hour to around 400 per month and about 5000 per year, a figure not untypical apparently for the total number of defects in an IBM project.As Gibson stressed, one of the main challenges for IBM is to remove defects early, a familiar message, but one that was dramatically reinforced by considering the potential costs of finding defects ever later in the development process, with the worst scenario being faults found in operational software.The CICS system was mentioned: this transaction processing system is used by numerous banks and financial organizations world-wide and the economic impact if services are interrupted just for a short period is staggering.Even for something less critical, such as an e-commerce application, the cost of customer down time was estimated at U.S. $480 000 per hour.IBM use a diverse set of validation and testing strategies, but perhaps one technique that deserves greater awareness (at least, if the rather disappointing show of hands is any guide, by those in the audience at UK-Test 2005 who were familiar with it) is orthogonal defect classification (ODC).This idea, introduced by Chillarege and colleagues [2,3], aims to categorize the space of all defects into a small number of broad orthogonal categories.Repeated application of ODC has shown that different process stages have different signature patterns of defect distribution; for example, one might expect more defects of 'interface' type to be found during integration testing.Hence, measuring the numbers of defects of each type helps identify progress and can also drive appropriate corrective action.It is particularly pleasing that both papers in this issue of STVR are especially relevant and practical for the software industry.Belli, Budnik and White, in their paper, concentrate on testing graphical user interfaces (GUIs).Building on earlier work, they provide a coherent strategy for testing GUIs * See http://www.uktest.

On mutants

A test of time across the generationsFundamental to the process of software testing is the generation of appropriate test data.Both of the papers in this issue address this topic and, indeed, both are concerned with automating the activity.The word 'generation' has a number of related meanings, but here, of course, it is being used in the sense of 'production' or 'creation'.Legeard et al. consider the automated generation of test cases from formal models of systems in the B abstract machine notation in their paper.In fact, their approach utilizes a system called BZ-TESTING-TOOLS (BZ-TT), which can be used for test case generation from Z specifications as well as B abstract machines.The focus of the paper is on the definition of control-flow and data-oriented coverage criteria for B abstract machines.The data-oriented criteria are particularly interesting since the authors have developed a family of criteria, the aim of which is to test the boundaries of a given state space.In a manner similar to domain testing, the underlying assumption is that faults are more likely to be detected on the boundaries of input domains than in the interiors.A nice feature of the BZ-TT environment is that it allows the systematic generation of a small number of test cases that provide good coverage, whilst also allowing the test engineer to expand the coverage of specific parts of the model that are particular areas of concern.In this way, the problem of an explosion in the number of test cases generated can be carefully controlled and kept manageable, using the variety of well-defined coverage criteria.The approach has been applied to a number of industrial case studies and brief details of one of these, a smart card system, are given in the paper.McMinn's paper is rather different in that it provides a survey of metaheuristic search techniques for the automatic generation of test data.In any area of research it can be useful to pause and take stock of what has been achieved.It also gives an opportunity to reflect on outstanding problems and possible future directions.McMinn defines metaheuristic search techniques as 'high-level frameworks, which utilize heuristics to seek solutions for combinatorial problems at reasonable computational cost'.One such technique is simulated annealing, which gets its name by analogy with the chemical process of annealing-heating a solid until it melts and then changing its properties by varying the rate at which it cools back to a solid.Another technique involves genetic algorithms (GAs), an approach inspired by genetics and Darwinian natural selection.GAs bring into play a second meaning of the word 'generation', namely descendants of some given population in the same number of steps.Starting from an initial population of solutions, the fittest individuals undergo iterative recombination and mutation (somewhat akin to breeding), thereby evolving successive generations.Metaheuristic search techniques, such as the two just highlighted, have been used for automatic test data generation:• to obtain coverage of specific program structures, e.g.statements or branches;• to exercise specific program features as described by a specification;• to attempt the disproving of certain properties, e.g.finding test data to falsify an assertion;• to verify non-functional properties, e.g.worst-case execution times.McMinn provides a very clear exposition of work in all these areas, finishing each section with helpful suggestions for further research.

The merits of diversityAs well as our regular book reviews and diary, this issue of STVR contains three papers on a diverse range of topics: regression testing, reliability modelling and testing UML designs.This variety is welcome: it adds interest and is likely to engage more readers.The idea that there is merit in diversity is a notion that has been much in my mind just recently, as a result of involvement in a project to assess the evidence comparing fault elimination strategies for software.One of the main conclusions was that many techniques appear to be complementary and the best advice when high levels of assurance are required is to use a battery of different approaches.Faults that one particular technique fails to expose will hopefully be exposed by some other technique.Assessing the relative worth of the many various testing and analysis techniques remains one of the great challenges for our community.Indeed, it may never be possible to characterize fully the efficacy of each individual technique.Using a battery of techniques is not the only way in which diversity helps with fault exposure.Testing professionals are well aware that it makes sense to develop test cases from a variety of artifacts: requirements, specification, design and code.The shortcomings of test data generated from one source may be made good by test data generated from another source.The coverage of potential failureinducing domains will surely be improved by the diverse origins of the data.Of course the notion of diversity appears even more directly in multiversion software, the intuition being that independently developed programs in conjunction with majority voting enhance reliability and result in greater fault tolerance.As it turns out, there is experimental evidence to suggest that coincident failures reduce the effectiveness of majority voting in handling faults [1], so the extra cost of producing multiple versions should not automatically lead to a reduction in testing techniques used.Once again diversity should be maintained.Turning to the contents of this issue, the first paper, by Sebastian Elbaum, Praveen Kallakuri, Alexey Malishevsky, Gregg Rothermel and Satya Kanduri, is entitled 'Understanding the effects of changes on the cost-effectiveness of regression testing techniques'.Regression testing is the process of testing modified software; determining which of the test cases for the original program to reuse and what new test cases to add, can lead to diverse strategies.In addition, a variety of techniques exist that prioritize test cases according to some criterion, for example fastest rate of code coverage or most frequently used features first.Elbaum et al. report what they call an 'embedded multiple case study' to ascertain how the size, distribution and location of modifications made to software affect the effectiveness and efficiency of four test case selection and four test case prioritization techniques.Four non-trivial C programs, whose modification histories were available, were used as case studies.Since regression faults were not available, faults were seeded that were as realistic as possible and involved code deleted from, inserted into or modified between versions.By careful study of the trends in the results across all four programs, Elbaum et al. have gleaned five separate implications for regression testers and confirmed that change attributes play a significant role in the performance of regression testing.

A number of different concepts have been proposed that, loosely speaking, revolve around the notion of software testability. Indeed, the concept of testability itself has been interpreted in a variety of ways by the software community. One interpretation is concerned with the extent of the modifications a program component requires, in terms of its input and output variables, so that the entire behaviour of the component is observable and controllable. Another interpretation is the ease with which faults, if present in a program, can be revealed by the testing process and the propagation, infection and execution (PIE) model has been proposed as a method of estimating this. It has been suggested that this particular interpretation of testability might be linked with the metric domain-to-range ratio (DRR), i.e. the ratio of the cardinality of the set of all inputs (the domain) to the cardinality of the set of all outputs (the range). This paper reports work in progress exploring some of the connections between the concepts mentioned. In particular, a simple mathematical link is established between domain-to-range ratio and the observability and controllability aspects of testability. In addition, the PIE model is re-considered and a relationship with fault size is observed. This leads to the suggestion that it might be more straightforward to estimate PIE testability by an adaptation of traditional mutation analysis. The latter suggestion exemplifies the main goals of the work described here, namely to seek greater understanding of testability in general and, ultimately, to find easier ways of determining it.

presents an approach for automated testing of container classes based on combinatorial algorithms for state generation.The second paper, by

V is for VerificationThis issue of STVR contains two papers on verification.Of course the 'V' in STVR stands for 'verification', yet as it happens, the journal has published far fewer papers on this topic than one might imagine.Perhaps before going any further it would be wise to clarify the meaning of the term.There is the clever and much-cited quote of Boehm (1984) that verification is concerned with answering the question: 'Am I building the product right?', in contrast to validation which is concerned with answering: 'Am I building the right product?'.Despite this implicit and fairly general definition of verification as being the act of checking that the internal workings of software are correct, popular usage of the word 'verification' often refers just to formal (mathematical) verification of software.Certainly the two papers on verification in this issue are concerned with this latter aspect of verification.As it happens I have recently been teaching a course, which includes a major section on formal verification of programs, to third year undergraduates on our computer science degree programme.It will be no surprise that other parts of the course focus on formal specification and formal derivation of programs.In preparation for teaching the course I have been back to look at some of the influential papers in the formal verification field.I started, as might be expected, with the papers of Floyd (1967) and Hoare (1969) and then progressed on to the first part of the excellent two-part survey by Apt (1981, 1984).However, besides the technical aspects, I wanted to remind myself of the arguments and discussion concerning the appropriateness and usefulness of formal verification.In this connection, I have a strong memory of attending a presentation by Richard Waldinger as part of a tutorial session on program verification at the Third International Conference on Software Engineering in Atlanta in 1978, where he gave a drawing of the 'innovation-acceptance cycle' as it applied to formal verification (King, 1978).As I recall, it was essentially a graph in the shape of a damped sinusoidal curve that started at its deepest trough representing innovation and the thought: 'this is a far-fetched idea'.The curve then oscillated to its highest peak corresponding to the thought: 'this is the answer we have been looking for'.Then the curve swung back to a trough, not quite as deep as the first, corresponding to: 'we tried it and it was a big flop'.As readers can probably tell, I was impressed by the insight this seemed to offer.Anyway, about a year after that conference, a paper by DeMillo, Lipton and Perlis was published that tackled the people-oriented, rather than technical, processes in connection with formal verification in a far more direct fashion.

Edit or

Abstract This paper describes a programming environment for Pascal, called NSEDIT, which runs under VAX/VMS VAX/VMS is a trademark of the Digital Equipment Corporation. . NSEDIT is based upon the notion of Nassi‐Shneiderman charts (abbreviated to N‐S charts in this paper) and is designed for ease of use by novice programmers in a teaching situation. A key component of the system is the editor, which enables structural features of Pascal to be manipulated in terms of their N‐S chart box representations. Simultaneous editing of more than one program or module is permitted. Another key feature of the system is a semiautomatic interface to the VAX/VMS Pascal compiler, with subsequent display of execution counts as part of the N‐S charts. In this way users can obtain immediate feedback on the coverage of program elements by test runs, while still inside an editing session.

Abstract M. H. Halstead has argued that all computer programs are composed entirely of operators and operands. By counting these entities the software science theory then enables program properties such as vocabulary, length, volume, program level and language level to be calculated. For well written, or so‐called ‘pure programs’, one would expect, according to the theory, good agreement between certain observed and predicted values. Also, one might expect an intuitive ordering of language levels to be confirmed by the theory, with for example, Algol 68 having a higher language level than Fortran. In this paper two different counting strategies have been applied to one implementation of the Numerical Algorithms Group (NAG) Algol 68 library. The results do not entirely match expectation.

There are a number of practical difficulties in performing a path testing strategy for computer programs. One problem is in deciding which paths, out of a possible infinity, to use as test cases. A hierarchy of structural test metrics is suggested to direct the choide and to monitor the coverge of test paths. Another problem is that many of the chosen paths may be infeasible in the sense that no test data can ever execute them. Experience with the use of "allegations" to circumvent this problem and prevent the static generation of many infeasible paths is reported.

This paper discusses the need for measures of complexity and unstructuredness of programs. A simple language independent concept is put forward as a measure of control flow complexity in program text and is then developed for use as a measure of unstructuredness. The proposed metric is compared with other metrics, the most notable of which is the cyclomatic complexity measure. Some experience with automatic tools for obtaining these metrics is reported.