NIST SP 800-142 日本語訳

NIST Special Publication 800-142

D. Richard Kuhn, Raghu N. Kacker, Yu Lei

October, 2010

U.S. Department of Commerce Gary Locke, Secretary

National Institute of Standards and Technology Patrick Gallagher, Director

The Information Technology Laboratory (ITL) at the National Institute of Standards and Technology (NIST) promotes the U.S. economy and public welfare by providing technical leadership for the Nation’s measurement and standards infrastructure. ITL develops tests, test methods, reference data, proof of concept implementations, and technical analyses to advance the development and productive use of information technology. ITL’s responsibilities include the development of technical, physical, administrative, and management standards and guidelines for the cost-effective security and privacy of sensitive unclassified information in Federal computer systems. This Special Publication 800-series reports on ITL’s research, guidance, and outreach efforts in computer security, and its collaborative activities with industry, government, and academic organizations.

For sale by the Superintendent of Documents, U.S. Government Printing Office Internet: bookstore.gpo.gov — Phone: (202) 512-1800 — Fax: (202) 512-2250 Mail: Stop SSOP, Washington, DC 20402-0001

This document is a publication of the National Institute of Standards and Technology (NIST) and is not subject to U.S. copyright. Certain commercial entities, equipment, or materials may be identified in this document in order to describe an experimental procedure or concept adequately. Such identification is not intended to imply recommendation or endorsement by the National Institute of Standards and Technology, nor is it intended to imply that the entities, materials, or equipment are necessarily the best available for the purpose.

For questions or comments on this document, contact Rick Kuhn, kuhn@nist.gov or 301-975-3337.

Acknowledgements

Special thanks are due to Tim Grance, Jim Higdon, Eduardo Miranda, and Tom Wissink for early support and evangelism of this work, and especially Jim Lawrence who has been an integral part of the team since the beginning. We have benefitted tremendously from interactions with researchers and practitioners including Renee Bryce, Myra Cohen, Charles Colbourn, Mike Ellims, Vincent Hu, Justin Hunter, Aditya Mathur, Josh Maximoff, Carmelo Montanez-Rivera, Jenise Reyes Rodriguez, Rick Rivello, Sreedevi Sampath, Mike Trela, and Tao Xie. We also gratefully acknowledge NIST SURF students Michael Forbes, William Goh, Evan Hartig, Menal Modha, Kimberley O’Brien-Applegate, Michael Reilly, Malcolm Taylor and Bryan Wilkinson who contributed to the software and methods described in this document.

Executive Summary

Software implementation errors are one of the most significant contributors to information system security vulnerabilities, making software testing an essential part of system assurance. In 2003 NIST published a widely cited report which estimated that inadequate software testing costs the US economy $59.5 billion per year, even though 50% to 80% of development budgets go toward testing. Exhaustive testing – testing all possible combinations of inputs and execution paths – is impossible for real-world software, so high assurance software is tested using methods that require extensive staff time and thus have enormous cost. For less critical software, budget constraints often limit the amount of testing that can be accomplished, increasing the risk of residual errors that lead to system failures and security weaknesses.

Combinatorial testing is a method that can reduce cost and increase the effectiveness of software testing for many applications. The key insight underlying this form of testing is that not every parameter contributes to every failure and most failures are caused by interactions between relatively few parameters. Empirical data gathered by NIST and others suggest that software failures are triggered by only a few variables interacting (6 or fewer). This finding has important implications for testing because it suggests that testing combinations of parameters can provide highly effective fault detection. Pairwise (2-way combinations) testing is sometimes used to obtain reasonably good results at low cost, but pairwise testing may miss 10% to 40% or more of system bugs, and is thus not sufficient for mission-critical software. Combinatorial testing beyond 2-way has been limited, primarily due to a lack of good algorithms for higher interaction levels such as 4-way to 6-way testing. New algorithms, however, have made combinatorial testing beyond pairwise practical for industrial use.

This publication provides a self-contained tutorial on using combinatorial testing for real-world software. It introduces the key concepts and methods, explains use of software tools for generating combinatorial tests (freely available on the NIST web site csrc.nist.gov/acts), and discusses advanced topics such as the use of formal models of software to determine the expected results for each set of test inputs. With each topic, a section on costs and practical considerations explains tradeoffs and limitations that may impact resources or funding. The material is accessible to an undergraduate student of computer science or engineering, and includes an extensive set of references to papers that provide more depth on each topic.

Software implementation errors are one of the most significant contributors to information system security vulnerabilities, making software testing an essential part of system assurance. Combinatorial methods can help reduce the cost and increase the effectiveness of software testing for many applications. This publication provides a self-contained tutorial on using combinatorial testing for real-world software. It introduces the key concepts and methods, explains use of software tools for generating combinatorial tests (freely available on the NIST web site csrc.nist.gov/acts), and discusses advanced topics such as the use of formal models of software to determine the expected results for each possible set of test inputs. The material is accessible to an undergraduate student of computer science or engineering, and includes an extensive set of references to papers that provide more depth on each topic.

The National Institute of Standards and Technology (NIST) developed this document in furtherance of its statutory responsibilities under the Federal Information Security Management Act (FISMA) of 2002, Public Law 107-347.

NIST is responsible for developing standards and guidelines, including minimum requirements, for providing adequate information security for all agency operations and assets, but such standards and guidelines shall not apply to national security systems. This guideline is consistent with the requirements of the Office of Management and Budget (OMB) Circular A-130, Section 8b(3), “Securing Agency Information Systems,” as analyzed in A-130, Appendix IV: Analysis of Key Sections. Supplemental information is provided in A-130, Appendix III.

This guideline has been prepared for use by Federal agencies. It may be used by nongovernmental organizations on a voluntary basis and is not subject to copyright, though attribution is desired.

Nothing in this document should be taken to contradict standards and guidelines made mandatory and binding on Federal agencies by the Secretary of Commerce under statutory authority, nor should these guidelines be interpreted as altering or superseding the existing authorities of the Secretary of Commerce, Director of the OMB, or any other Federal official.

This publication introduces combinatorial testing and explains how to use it effectively for system and software assurance.

This document assumes that the readers have experience with software development and testing, some familiarity with scripting languages, and basic knowledge of programming, logic, and discrete mathematics equivalent to what would be acquired in an undergraduate computer science or engineering program. Most of the material should be readily understood by an undergraduate student with some programming experience. Because of the constantly changing nature of the information technology industry, readers are strongly encouraged to take advantage of other resources (including those listed in this document) for more current and detailed information.

The document is divided into chapters, with background material covered in appendices. Because it is intended to be self-contained, each chapter provides material that will be used in later topics. Chapters 2, 3, and 4 will be needed by most testers, while the material in later chapters is specialized for various topics. Appendices include a review of basic combinatorics and a discussion of empirical data on software failures.

Readers new to combinatorial testing may want to review the basics of combinatorics in Appendix A and read chapters 2, 3, and 4. Other sections of the publication can be reserved for later use as needed.

Developers of large data-intensive software often notice an interesting—though not surprising—phenomenon: When usage of an application jumps dramatically, components that have operated for months without trouble suddenly develop previously undetected errors. For example, the application may have been installed on a different OS-hardware-DBMS-networking platform, or newly added customers may have account records with an oddball combination of values that have not occurred before. Some of these rare combinations trigger failures that have escaped previous testing and extensive use. Such failures are known as interaction failures, because they are only exposed when two or more input values interact to cause the program to reach an incorrect result.

Combinatorial testing can help detect problems like this early in the testing life cycle. The key insight underlying t-way combinatorial testing is that not every parameter contributes to every failure and most failures are triggered by a single parameter value or interactions between a relatively small number of parameters (for more on the number of parameters interacting in failures, see Appendix B). To detect interaction failures, software developers often use “pairwise testing”, in which all possible pairs of parameter values are covered by at least one test. Its effectiveness is based on the observation that software failures often involve interactions between parameters. For example, a router may be observed to fail only for a particular protocol when packet volume exceeds a certain rate, a 2-way interaction between protocol type and packet rate. Figure 1 illustrates how such a 2-way interaction may happen in code. Note that the failure will only be triggered when both pressure < 10 and volume > 300 are true.

if (pressure < 10) { // do something

if (volume > 300) {

faulty code! BOOM!

} else {

good code, no problem

}

} else {

// do something else

}

Figure 1. 2-way interaction failure triggered only when two conditions are true.

Pairwise testing can be highly effective and good tools are available to generate arrays with all pairs of parameter value combinations. But until recently only a handful of tools could generate combinations beyond 2-way, and most that did could require impractically long times to generate 3-way, 4-way, or 5-way arrays because the generation process is mathematically complex. Pairwise testing, i.e. 2-way combinations, has come to be accepted as the common approach to combinatorial testing because it is computationally tractable and reasonably effective.

But what if some failure is triggered only by a very unusual combination of 3, 4, or more sensor values? It is very unlikely that pairwise tests would detect this unusual case; we would need to test 3-way and 4-way combinations of values. But is testing all 4-way combinations enough to detect all errors? What degree of interaction occurs in real failures in real systems? Surprisingly, this question had not been studied when NIST began investigating interaction failures in 1999. Results showed that across a variety of domains, all failures could be triggered by a maximum of 4-way to 6-way interactions [34, 35, 36, 65]. As shown in Figure 2, the detection rate increased rapidly with interaction strength (the interaction level t in t-way combinations is often referred to as strength). With the NASA application, for example, 67% of the failures were triggered by only a single parameter value, 93% by 2-way combinations, and 98% by 3-way combinations. The detection rate curves for the other applications studied are similar, reaching 100% detection with 4 to 6-way interactions. Studies by other researchers [6, 7, 26] have been consistent with these results.

Failures appear to be caused by interactions of only a few variables, so tests that cover all such few-variable interactions can be very effective.

Figure 2. Error detection rates for interaction strengths 1 to 6

While not conclusive, these results are interesting because they suggest that, while pairwise testing is not sufficient, the degree of interaction involved in failures is relatively low. We summarize this result in what we call the interaction rule, an empirically-derived rule that characterizes the distribution of interaction faults:

Interaction Rule: Most failures are induced by single factor faults or by the joint combinatorial effect (interaction) of two factors, with progressively fewer failures induced by interactions between three or more factors.

With the exception of combination covering test generation, these challenges are common to all types of software testing, and a variety of good techniques have been developed for dealing with them. What has made combinatorial testing practical today is the development of efficient algorithms to generate tests covering t-way combinations, and effective methods of integrating the tests produced into the testing process. A variety of approaches introduced in this publication can be used to make combinatorial testing a practical and effective addition to the software tester’s toolbox.

Advances in algorithms have made combinatorial testing beyond pairwise finally practical.

A note on terminology: we use the definitions below, following the Institute of Electrical and Electronics Engineers [30]. The term “bug” may also be used where its meaning is clear.

There are basically two approaches to combinatorial testing – use combinations of configuration parameter values, or combinations of input parameter values. In the first case, we select combinations of values of configurable parameters. For example, a server might be tested by setting up all 4-way combinations of configuration parameters such as number of simultaneous connections allowed, memory, OS, database size, etc., with the same test suite run against each configuration. The tests may have been constructed using any methodology, not necessarily combinatorial coverage. The combinatorial aspect of this approach is in achieving combinatorial coverage of configuration parameter values. (Note, the term variable is often used interchangeably with parameter to refer to inputs to a function.)

Combinatorial testing can be applied to configurations, input data, or both.

In the second approach, we select combinations of input data values, which then become part of complete test cases, creating a test suite for the application. In this case combinatorial coverage of input data values is required for tests constructed. A typical ad hoc approach to testing involves subject matter experts setting up use scenarios, then selecting input values to exercise the application in each scenario, possibly supplementing these tests with unusual or suspected problem cases. In the combinatorial approach to input data selection, a test data generation tool is used to cover all combinations of input values up to some specified limit. One such tool is ACTS (described in Appendix C), which is available freely from NIST.

Many, if not most, software systems have a large number of configuration parameters. Many of the earliest applications of combinatorial testing were in testing all pairs of system configurations. For example, telecommunications software may be configured to work with different types of call (local, long distance, international), billing (caller, phone card, 800), access (ISDN, VOIP, PBX), and server for billing (Windows Server, Linux/MySQL, Oracle). The software must work correctly with all combinations of these, so a single test suite could be applied to all pairwise combinations of these four major configuration items. Any system with a variety of configuration options is a suitable candidate for this type of testing.

Configuration coverage is perhaps the most developed form of combinatorial testing. It has been used for years with pairwise coverage, particularly for applications that must be shown to work across a variety of combinations of operating systems, databases, and network characteristics.

Table 1. Pairwise test configurations

Even if an application has no configuration options, some form of input will be processed. For example, a word processing application may allow the user to select 10 ways to modify some highlighted text: subscript, superscript, underline, bold, italic, strikethrough, emboss, shadow, small caps, or all caps. The font-processing function within the application that receives these settings as input must process the input and modify the text on the screen correctly. Most options can be combined, such as bold and small caps, but some are incompatible, such as subscript and superscript.

An example is given in Figure 3, which shows a 3-way covering array for 10 variables with two values each. The interesting property of this array is that any three columns contain all eight possible values for three binary variables. For example, taking columns F, G, and H, we can see that all eight possible 3-way combinations (000, 001, 010, 011, 100, 101, 110, 111) occur somewhere in the three columns together. In fact, any combination of three columns chosen in any order will also contain all eight possible values. Collectively, therefore, this set of tests will exercise all 3-way combinations of input values in only 13 tests, as compared with 1,024 for exhaustive coverage.

The key component is a covering array, which includes all t-way combinations. Each column is a parameter. Each row is a test.

Figure 3. 3-way covering array

Similar arrays can be generated to cover up to all 6-way combinations. In general, the number of \(t\)-way combinatorial tests that will be required is proportional to \(v^t \log n\), for \(n\) parameters with \(v\) possible values each.

Figure 4 contrasts these two approaches. With the first approach, we may run the same test set against all 3-way combinations of configuration options, while for the second approach, we would construct a test suite that covers all 3-way combinations of input transaction fields. Of course these approaches could be combined, with the combinatorial tests (approach 2) run against all the configuration combinations (approach 1).

Figure 4. Two ways of using combinatorial testing

Even with efficient algorithms to produce covering arrays, the oracle problem remains – testing requires both test data and results that should be expected for each data input. High interaction strength combinatorial testing may require a large number of tests in some cases, although not always. Approaches to solving the oracle problem for combinatorial testing include:

Crash testing: the easiest and least expensive approach is to simply run tests against the system under test (SUT) to check whether any unusual combination of input values causes a crash or other easily detectable failure. This is essentially the same procedure used in “fuzz testing”, which sends random values against the SUT. This form of combinatorial testing could be regarded as a disciplined form of fuzz testing [59]. It should be noted that although pure random testing will generally cover a high percentage of t-way combinations, 100% coverage of combinations requires a random test set much larger than a covering array. For example, all 3-way combinations of 10 parameters with 4 values each can be covered with 151 tests. Purely random generation requires over 900 tests to provide full 3-way coverage.

Embedded assertions: An increasingly popular “light-weight formal methods” technique is to embed assertions within code to ensure proper relationships between data, for example as preconditions, postconditions, or input value checks. Tools such as the Java Modeling language (JML) can be used to introduce very complex assertions, effectively embedding a formal specification within the code. The embedded assertions serve as an executable form of the specification, thus providing an oracle for the testing phase. With embedded assertions, exercising the application with all t-way combinations can provide reasonable assurance that the code works correctly across a very wide range of inputs. This approach has been used successfully for testing smart cards, with embedded JML assertions acting as an oracle for combinatorial tests [25]. Results showed that 80% - 90% of errors could be found in this way.

Model based test generation uses a mathematical model of the SUT and a simulator or model checker to generate expected results for each input [1,8,9,52,55]. If a simulator can be used, expected results can be generated directly from the simulation, but model checkers are widely available and can also be used to prove properties such as liveness in parallel processes, in addition to generating tests. Conceptually, a model checker can be viewed as exploring all states of a system model to determine if a property claimed in a specification statement is true. What makes a model checker particularly valuable is that if the claim is false, the model checker not only reports this, but also provides a “counterexample” showing how the claim can be shown false. If the claim is false, the model checker indicates this and provides a trace of parameter input values and states that will prove it is false. In effect this is a complete test case, i.e., a set of parameter values and expected result. It is then simple to map these values into complete test cases in the syntax needed for the system under test. Later chapters develop detailed procedures for applying each of these testing approaches.

Several types of test oracle can be used, depending on resources and the system under test.

This chapter presents worked examples illustrating development of test configurations. As will be seen, the advantages of combinatorial testing increase with the size of the problem.

Table 2. Simple example configuration options.

We can now generate test configurations using the ACTS tool. For simplicity of presentation we illustrate usage of the command line version of ACTS, but an intuitive GUI version is available that may be more convenient. This tool is summarized in Appendix C and a comprehensive user manual is included with the ACTS download.

The first step in creating test configurations is to specify the parameters and possible values in a file for input to ACTS, as shown in Figure 5:

[System]

[Parameter] OS (enum): XP,OS_X,RHL Browser (enum): IE, Firefox Protocol(enum): IPv4,IPv6 CPU (enum): Intel,AMD DBMS (enum): MySQL,Sybase,Oracle

[Relation] [Constraint] [Misc]

Figure 5. Simple example input file for ACTS.

Note that most of the bracketed tags in the input file are optional, and not filled in for this example. The essential part of the file is the [Parameter] specification, in the format <parameter name> (<type>): <values>, where one or more values are listed separated by commas. The tool can then be run at the command line:

java -Ddoi=2 –jar acts_cmd.jar ActsConsoleManager in.txt out.txt

A variety of options can be specified, but for this example we only use the “degree of interaction” option to specify 2-way, 3-way, etc. coverage. Output can be created in a convenient form shown below, or as a matrix of numbers, comma separated value, or Excel spreadsheet form. If the output will be used by human testers rather than as input for further machine processing, the format in Figure 6 is useful:

Figure 6. Excerpt of test configuration output covering all 2-way combinations.

The complete test set for 2-way combinations is shown in Table 1 in Section 2.1.1. Only 10 tests are needed. Moving to 3-way or higher interaction strengths requires more tests, as shown in Table 3.

Table 3. Number of combinatorial tests for a simple example.

Smart phones have become enormously popular because they combine communication capability with powerful graphical displays and processing capability. Literally tens of thousands of smart phone applications, or ‘apps’, are developed annually. Among the platforms for smart phone apps is the Android, which includes an open source development environment and specialized operating system. Android units contain a large number of configuration options that control the behavior of the device. Android apps must operate across a variety of hardware and software platforms, since not all products support the same options. For example, some smart phones may have a physical keyboard and others may present a soft keyboard using the touch sensitive screen. Keyboards may also be either only numeric with a few special keys, or a full typewriter keyboard. Depending on the state of the app and user choices, the keyboard may be visible or hidden. Ensuring that a particular app works across the enormous number of options is a significant challenge for developers. The extensive set of options makes it intractable to test all possible configurations, so combinatorial testing is a practical alternative.

Figure 7 shows a resource configuration file for Android apps. A total of 35 options may be set. Our task is to develop a set of test configurations that allow testing across all 4-way combinations of these options. The first step is to determine the set of parameters and possible values for each that will be tested. Although the options are listed individually to allow a specific integer value to be associated with each, they clearly represent sets of option values with mutually exclusive choices. For example, “Keyboard Hidden” may be “yes”, “no”, or “undefined”. These values will be the possible settings for parameter names that we will use in generating a covering array. Table 4 shows the parameter names and number of possible values that we will use for input to the covering array generator. For a complete specification of these parameters, see: http://developer.android.com/reference/android/content/res/Configuration.html

Figure 7. Android resource configuration file.

Table 4. Android configuration options.

Table 5. Number of combinatorial tests for Android example.

The system described in Section 3.1 illustrates a common situation in all types of testing: some combinations cannot be tested because they don’t exist for the systems under test. In this case, if the operating system is either OS X or Linux, Internet Explorer is not available as a browser. Note that we cannot simply delete tests with these untestable combinations, because that would result in losing other combinations that are essential to test but are not covered by other tests. For example, deleting tests 5 and 7 in Section 2.1.1 would mean that we would also lose the test for Linux with the IPv6 protocol.

One way around this problem is to delete tests and supplement the test suite with manually constructed test configurations to cover the deleted combinations, but covering array tools offer a better solution. With ACTS we can specify constraints, which tell the tool not to include specified combinations in the generated test configurations. ACTS supports a set of commonly used logic and arithmetic operators to specify constraints. In this case, the following constraint can be used to ensure that invalid combinations are not generated:

Some combinations never occur in practice.

(OS != “XP” => Browser = “Firefox”)

The covering array tool will then generate a set of test configurations that does not include the invalid combinations, but does cover all those that are essential. The revised test configuration array is shown in Figure 8 below. Parameter values that have changed from the original configurations are underlined. Note that adding the constraint also resulted in reducing the number of test configurations by one. This will not always be the case, depending on the constraints used, but it illustrates how constraints can help reduce the problem. Even if particular combinations are testable, the test team may consider some combinations unnecessary, and constraints could be used to prevent these combinations, possibly reducing the number of test configurations.

Figure 8. Test configurations for simple example with constraint.

Using combinatorial methods to design test configurations is probably the most widely used combinatorial approach because it is quick and easy to do and typically delivers significant improvements to testing. Combinatorial testing for input parameters can provide better test coverage at lower cost than conventional tests, and can be extended to high strength coverage to provide much better assurance.

As noted in the introduction, the key advantage of combinatorial testing derives from the fact that all, or nearly all, software failures appear to involve interactions of only a few parameters. Using combinatorial testing to select configurations can make testing more efficient, but it can be even more effective when used to select input parameter values. Testers traditionally develop scenarios of how an application will be used, then select inputs that will exercise each of the application features using representative values, normally supplemented with extreme values to test performance and reliability. The problem with this often ad hoc approach is that unusual combinations will usually be missed, so a system may pass all tests and work well under normal circumstances, but eventually encounter a combination of inputs that it fails to process correctly.

The system under test is an access control module that implements the following policy:

Access is allowed if and only if:

The input parameters for this module are shown in Figure 9:

Figure 9. Access control module input parameters.

Our task is to develop a covering array of tests for these inputs. The first step will be to develop a table of parameters and possible values, similar to that in Section 3.1 in the previous chapter. The only difference is that in this case we are dealing with input parameters rather than configuration options. For the most part, the task is simple: we just take the values directly from the specifications or code, as shown in Figure 10. Several parameters are boolean, and we will use 0 and 1 for false and true values respectively. For day of the week, there are only seven values, so these can all be used. However, hour of the day presents a problem. Recall that the number of tests generated for \(n\) parameters is proportional to \(v^t\), where \(v\) is the number of values and \(t\) is the interaction level (2-way to 6-way). For all boolean values and 4-way testing, therefore, the number of tests will be some multiple of \(2^4\). But consider what happens with a large number of possible values, such as 24 hours. The number of tests will be proportional to \(24^4\) = 331,736. For this example, time is given in minutes, which would obviously be completely intractable. Therefore, we must select representative values for the hour parameter. This problem occurs in all types of testing, not just with combinatorial methods, and good methods have been developed to deal with it. Most testers are already familiar with two of these: equivalence partitioning and boundary value analysis. Additional background on these methods can be found in software testing texts such as Ammann and Offutt [2], Beizer [4], Copeland [21], Mathur [45], and Myers [52].

Figure 10. Parameters and values for access control example.

How should the partitions be determined? One obvious, but not necessarily good, approach is to simply select values from various points on the range of a variable. For example, if capacity can range from 0 to 20,000, it might seem sensible to select 0, 10,000, and 20,000 as possible values. But this approach is likely to miss important cases that depend on the specific requirements of the system under test. Some judgment is involved, but partitions are usually best determined from the specification. In this example, 9 am and 5 pm are significant, so 0540 (9 hours past midnight) and 1020 (17 hours past midnight) determine the appropriate partitions:

Ideally, the program should behave the same for any of the times within the partitions; it should not matter whether the time is 4:00 am or 7:03 am, for example, because the specification treats both of these times the same. Similarly, it should not matter which time between the hours of 9 am and 5 pm is chose; the program should behave the same for 10:20 am and 2:33 pm. One common strategy, boundary value analysis, is to select test values at each boundary and at the smallest possible unit on either side of the boundary, for three values per boundary. The intuition, backed by empirical research, is that errors are more likely at boundary conditions because errors in programming may be made at these points. For example, if the requirements for automated teller machine software say that a withdrawal should not be allowed to exceed $300, a programming error such as the following could occur:

Use a maximum of 8 to 10 values per parameter to keep testing tractable.

Figure 11. Number of tests for access control example.

As with the previous example, the advantage over exhaustive testing is not large, because of the small number of parameters. With larger problems, the advantages of combinatorial testing can be spectacular. For example, consider the problem of testing the software that processes switch settings for the panel shown in Figure 12. There are 34 switches, which can each be either on or off, for a total of \(2^{34}=1.7\times10^{10}\) possible settings. We clearly cannot test 17 billion possible settings, but all 3-way interactions can be tested with only 33 tests, and all 4-way interactions with only 85. This may seem surprising at first, but it results from the fact that every test of 34 parameters contains \(\binom{34}{3}\) = 5,984 3-way and \(\binom{34}{4}\) = 46,376 4-way combinations.

The larger the system, the greater the benefit from combinatorial testing.

Figure 12. Panel with 34 switches.

Combinatorial methods can be highly effective and reduce the cost of testing substantially. For example, Justin Hunter has applied these methods to a wide variety of test problems and consistently found both lower cost and more rapid error detection [30]. But as with most aspects of engineering, tradeoffs must be considered. Among the most important is the question of when to stop testing, balancing the cost of testing against the risk of failing to discover additional failures. An extensive body of research has been devoted to this topic, and sophisticated models are available for determining when the cost of further testing will exceed the expected benefits [10, 45]. Existing models for when to stop testing can be applied to the combinatorial test approach also, but there is an additional consideration: What is the appropriate interaction strength to use in this type of testing?

Figure 13. Number of tests for avionics example.

When applying combinatorial methods to input parameters, the key cost factors are the number of values per parameter, the interaction strength, and the number of parameters. As shown above, the number of tests increases rapidly as the value of t is increased, but the rate of increase depends on the number of values per parameter. Binary variables, with only two values each, result in far fewer tests than parameters with many values each. As a practical matter, when partitioning the input space (section 4.1), it is best to keep the number of values per parameter below 8 or 10 if possible.

Because the number of tests increases only logarithmically with the number of parameters, test set size for a large problem may be only somewhat larger than for a much smaller problem. For example, if a project uses combinatorial testing for a system that has 20 parameters and generates several hundred tests, a much larger system with 40 to 50 parameters may only require a few dozen more tests. Combinatorial methods may generate the best cost benefit ratio for large systems.

In testing event-driven software, the critical condition for triggering failures often is whether or not a particular event has occurred prior to a second one, not necessarily if they are back to back. This situation reflects the fact that in many cases, a particular state must be reached before a particular failure can be triggered. For example, a failure might occur when connecting device A only if device B is already connected. The methods described in this chapter were developed to solve a real problem in interoperability test and evaluation, using combinatorial methods to provide efficient testing. Sequence covering arrays, as defined here, ensure that any t events will be tested in every possible t-way order.

For this problem we can define a sequence-covering array [39, 40], which is a set of tests that ensure all t-way sequences of events have been tested. The t events in the sequence may be interleaved with others, but all permutations will be tested. For example, we may have a component of a factory automation system that uses certain devices interacting with a control program. We want to test the events defined in Table 6.

In many systems, the order of inputs is important.

Table 6. System events

Definition. We define a sequence covering array, SCA(N, S, t) as an N x S matrix where entries are from a finite set S of s symbols, such that every t-way permutation of symbols from S occurs in at least one row; the t symbols in the permutation are not required to be adjacent. That is, for every t-way arrangement of symbols \(x_1, x_2, ..., x_t\), the regular expression \(.*x_1.*x_2.*x_t.*\) matches at least one row in the array. Sequence covering arrays, as the name implies, are analogous to standard covering arrays, which include at least one of every t-way combination of any n variables, where t<n. A variety of algorithms are available for constructing covering arrays, but these are not usable for generating t-way sequences because they are designed to cover combinations in any order.

Example 1. Consider the problem of testing four events, a, b, c, and d. For convenience, a t-way permutation of symbols is referred to as a t-way sequence. There are 4! = 24 possible permutations of these four events, but we can test all 3-way sequences of these events with only six tests (see Table 7).

Table 7. Tests for four events.

A 2-way sequence covering array can be constructed by listing the events in some order for one test and in reverse order for the second test:

To see that the procedure in Example 2 generates tests that cover all 2-way sequences, note that for 2-way sequence coverage, every pair of variables x and y, x..y and y..x must both be in some test (where a..b means that a is eventually followed by b). All variables are included in each test, therefore any sequence x..y must be in either test 1 or test 2 and its reverse y..x in the other test.

Sequence covering arrays have been incorporated into operational testing for a mission-critical system that uses multiple devices with inputs and outputs to a laptop computer. The test procedure has 8 steps: boot system, open application, run scan, connect peripherals P-1 through P-5. It is expected that for some sequences, the system will not function properly, thus the order of connecting peripherals is a critical aspect of testing. In addition, there are constraints on the sequence of events: can't scan until the app is open; can't open app until system is booted. There are 40,320 permutations of 8 steps, but some are redundant (e.g., changing the order of peripherals connected before boot), and some are invalid (violates a constraint). Around 7,000 are valid, and non-redundant, but this is far too many to test for a system that requires manual, physical connections of devices.

The system was tested using a seven-step sequence covering array, incorporating the assumption that there is no need to examine strength-3 sequences that involve boot-up. The initial test configuration (Figure 14) was drawn from the library of pre-computed sequence tests. Some changes were made to the pre-computed sequences based on unique requirements of the system test. If 6='Open App' and 5='Run Scan', then cases 1, 4, 6, 8, 10, and 12 are invalid, because the scan cannot be run before the application is started. This was handled by 'swapping 0 and 1' when they are adjacent (1 and 4), out of order. For the other cases, several cases were generated from each that were valid mutations of the invalid case. A test was also embedded to see whether it mattered where each of three USB connections were placed. The last test case ensures at least strength 2 (sequence of length 2) for all peripheral connections and 'Boot', i.e., that each peripheral connection occurs prior to boot. The final test array is shown in Table 9.

Figure 14. Sevenevent test from precomputed test library.

As with other forms of combinatorial testing, some combinations may be either impossible or not exist on the system under test. For example, ‘receive message’ must occur before ‘process message’. The algorithm we have developed makes it possible to specify pairs x,y, where the sequence x..y is to be excluded from the generated covering array. Typically this will lead to extra tests, but does not increase the test array significantly.

Table 8. Number of tests for combinatorial 3way and 4way sequences.

Table 9. Final sequence covering array used in testing.

Since it is nearly always impossible to test all possible combinations, combinatorial testing is a reasonable alternative. For some value of t, testing all t-way interactions among n parameters will detect nearly all errors. It is possible that t = n, but recalling the empirical data on failures, we would expect t to be relatively small. Determining the level of input or configuration state space coverage can help in understanding the degree of risk that remains after testing. If 90% - 100% of the state space has been covered, then presumably the risk is small, but if coverage is much smaller, then the risk may be substantial. This chapter describes some measures of combinatorial coverage that can be helpful in estimating this risk that we have applied to tests for spacecraft software [50] but have general application to any combinatorial coverage problem.

Test coverage is one of the most important topics in software assurance. Users would like some quantitative measure to judge the risk in using a product. For a given test set, what can we say about the combinatorial coverage it provides? With physical products, such as light bulbs or motors, reliability engineers can provide a probability of failure within a particular time frame. This is possible because the failures in physical products are typically the result of natural processes, such as metal fatigue.

With software the situation is more complex, and many different approaches have been devised for determining software test coverage. With millions of lines of code, or only with a few thousand, the number of paths through a program is so large that it is impossible to test all paths. For each if statement, there are two possible branches, so a sequence of \(n\) if statements will result in \(2^n\) possible paths. Thus even a small program with only 270 if statements in an execution trace may have more possible paths than there are atoms in the universe, which is on the order of \(10^{80}\). With loops (while statements) the number of possible paths is literally infinite. Thus a variety of measures have been developed to gauge the degree of test coverage. The following are some of the better-known coverage metrics:

Commonly used coverage measures do not apply well to combinatorial testing.

Note that the coverage measures above depend on access to program source code. Combinatorial testing, in contrast, is a black box technique. Inputs are specified and expected results determined from some form of specification. The program is then treated as simply a processor that accepts inputs and produces outputs, with no knowledge expected of its inner workings.

How should state space coverage be measured? Looking closely at the nature of combinatorial testing leads to several measures that are useful. We begin by introducing what will be called a variable-value configuration.

Definition. For a set of t variables, a variable-value configuration is a set of t valid values, one for each of the variables.

Example. Given four binary variables, a, b, c, and d, a=0, c=1, d=0 is a variable-value configuration, and a=1, c=1, d=0 is a different variable-value configuration for the same three variables a, c, and d.

Of the total number of t-way combinations for a given collection of variables, what percentage will be covered by the test set? If the test set is a covering array, then coverage is 100%, by definition, but many test sets not based on covering arrays may still provide significant t-way coverage. If the test set is large, but not designed as a covering array, it is very possible that it provides 2-way coverage or better. For example, random input generation may have been used to produce the tests, and good branch or condition coverage may have been achieved. In addition to the structural coverage figure, for software assurance it would be helpful to know what percentage of 2-way, 3-way, etc. coverage has been obtained.

Definition: For a given test set for n variables, simple t-way combination coverage is the proportion of t-way combinations of n variables for which all variable-values configurations are fully covered.

Example. Figure 15 shows an example with four binary variables, a, b, c, and d, where each row represents a test. Of the six 2-way combinations, ab, ac, ad, bc, bd, cd, only bd and cd have all four binary values covered, so simple 2-way coverage for the four tests in Figure 15 is 1/3 = 33.3%. There are four 3-way combinations, abc, abd, acd, bcd, each with eight possible configurations: 000, 001, 010, 011, 100, 101, 110, 111. Of the four combinations, none has all eight configurations covered, so simple 3-way coverage for this test set is 0%.

Figure 15. An example test array for a system with four binary components

A test set that provides full combinatorial coverage for t-way combinations will also provide some degree of coverage for (t+1)-way combinations, (t+2)-way combinations, etc. This statistic may be useful for comparing two combinatorial test sets. For example, different algorithms may be used to generate 3-way covering arrays. They both achieve 100% 3-way coverage, but if one provides better 4-way and 5-way coverage, then it can be considered to provide more software testing assurance.

Definition. For a given test set for n variables, (t+k)-way combination coverage is the proportion of (t+k)-way combinations of n variables for which all variable-values configurations are fully covered. (Note that this measure would normally be applied only to a t-way covering array, as a measure of coverage beyond t).

A test set for t-way interactions will also cover some higher strength interactions at t+1, t+2, etc.

Example. If the test set in Figure 15 is extended as shown in Figure 16, we can extend 3-way coverage. For this test set, bcd is covered, out of the four 3-way combinations, so 2-way coverage is 100%, and (2+1)-way = 3-way coverage is 25%.

Figure 16. Eight tests for four binary variables.

Definition. For a given combination of t variables, variable-value configuration coverage is the proportion of variable-value configurations that are covered.

Although the example in Figure 17 uses variables with the same number of values, this is not essential for the measurement. Coverage measurement tools that we have developed compute coverage for test sets in which parameters have differing numbers of values, as shown in Figure 18 and Figure 19.

Figure 17. The test array covers all possible 2-way combinations of a, b, c, and d to different levels.

Figure 18 is an example of coverage for a \(2^{87}3^{2}4^{5}\) set (87 binary, two 3-value, and five 4-value) of input variables (blue=2-way, pink=3-way, yellow=4-way). This particular test set was not a covering array, but pairwise coverage is still quite good, with about 95% of the variables having all possible 2-way configurations covered. Even for 4-way combinations we see that all variables have at least 28% of their configurations covered, and about 25% of them have about 98% or more of 4-way configurations covered. Figure 19 shows a similar plot for a \(2^{79}3^{1}4^{1}6^{1}9^{1}\) configuration.

Figure 18. Configuration coverage for \(2^{87}3^{2}4^{5}\) inputs.

Figure 19. Configuration coverage for \(2^{79}3^{1}4^{1}6^{1}9^{1}\) inputs.

An important cost advantage introduced by coverage measurement is the ability to use existing test sets, identify particular combinations that may be missing, and supplement existing tests. In some cases, as in the example of Figure 18, it may be discovered that the existing test set is already strong with respect to a particular strength t (in this case 2-way), and tests for t+1 generated. The tradeoff in cost of applying coverage measurement is the need to map existing tests into discrete numerical values that can be analyzed by the coverage measurement tools (see Appendix C). For example, the days of the week in the example of Figure 10 would have to be mapped into 0 - 6 or 1 - 7. Future versions of the coverage measurement tools may include more flexibility in handling parameter values.

For testing to be most efficient and effective, we need an understanding of when a particular test method is most appropriate. That is, what characteristics of a problem lead us to use one form of testing over another, and what are the tradeoffs with respect to cost and effectiveness? Some studies have compared the effectiveness of combinatorial and random approaches to testing, but have reached conflicting results [3, 4, 56, 58]. This chapter presents an analysis [37, 38] of these two methods and discusses how random testing may complement combinatorial methods.

Because a significant percentage of failures can only be triggered by the interaction of two or more variables, one consideration in comparing random and combinatorial testing is the degree to which random testing covers particular t-way combinations. Table 10 gives the percentage of t-way combinations covered by a randomly generated test set of the same size as a t-way covering array, for various combinations of k = number of variables and v = number of values per variable. Note that the coverage could vary with different realizations of randomly generated test sets. That is, a different random number generator, or even multiple runs of the same generator, may produce slightly different coverage (perhaps a few tests out of thousands, depending on the problem). Figure 20 through Figure 24 summarize the coverage for arrays with variables of 2 to 10 values. As seen in the figures, the coverage provided by a random test suite versus a covering array of the same size varies considerably with different configurations.

Now consider the size of a random test set required to provide 100% combination coverage. With the most efficient covering array algorithms, the difficulty of finding tests with high coverage increases as tests are generated. Thus even if a randomly generated test set provides better than 99% of the coverage of an equal sized covering array, it should not be concluded that only a few more tests are needed for the random set to provide 100% coverage. Table 11 gives the sizes of randomly generated test sets required for 100% combinatorial coverage at various configurations, and the ratio of these sizes to covering arrays computed with ACTS. Although there is considerable variation among configurations, note that the ratio of random to combinatorial test set size for 100% coverage exceeds 3 in most cases, with average ratios of 3.9, 3.8, and 3.2 at t = 2, 3, and 4 respectively. Thus, combinatorial testing retains a significant advantage over random testing if the goal is 100% combination coverage for a given value of t.

Table 10. Percent of t-way combinations covered by equal number of random tests

Table 11. Size of random test set required for 100% t-way combination coverage.

Table 12. Average ratio of random/ACTS for covering arrays by values per variable, variables = 10, 15, 20, 25

The comparisons between random and combinatorial testing suggest a number of conclusions:

An important practical consideration in comparing combinatorial with random testing is the efficiency of the covering array generator. Algorithms have a very wide range in the size of covering arrays they produce. It is not uncommon for the better algorithms to produce arrays that are 50% smaller than other algorithms. We have found in comparisons with other tools that there is no uniformly “best” algorithm. Other algorithms may produce smaller or larger combinatorial test suites, so the comparable random test suite will vary in the number of combinations covered. Thus random testing may fare better in comparison with combinatorial tests produced by one of the less efficient algorithms.

However there is a less obvious but important tradeoff regarding covering array size. An algorithm that produces a very compact array, i.e., with few tests, for t-way combinations may include fewer (t+1)-way combinations because there are fewer tests. Table 13 and Table 14 illustrate this phenomenon for an example. Table 9 shows the percentage of t+1 up to t+3 combination coverage provided by the ACTS tests and in Table 10 the equivalent number of random tests. Although ACTS pairwise tests

provide better 3-way coverage than the random tests, at other interaction strengths and values of t, the random tests are roughly the same or slightly better in combination coverage than ACTS. Recall from Section 7.1 that pairwise combinatorial tests detected slightly fewer events than the equivalent number of random tests. One possible explanation may be that the superior 4-way and 5-way coverage of the random tests allowed detection of more events. Almost paradoxically, an algorithm that produces a larger, sub-optimal covering array may provide better failure detection because the larger array is statistically more likely to include t+1, t+2, and higher degree interaction tests as a byproduct of the test generation. Again, however, the less optimal covering array is likely to more closely resemble the random test suite in failure detection.

A less optimal (by size) array may provide better failure detection because it includes more interactions at t+1, t+2, etc.

Table 13. Higher interaction coverage of tway tests

Figure 20. Percent coverage of t-way combinations for v=2.

Figure 21. Percent coverage of t-way combinations for v=4.

Figure 22. Percent coverage of t-way combinations for v=6.

Figure 23. Percent coverage of t-way combinations for v=8.

Figure 24. Percent coverage of t-way combinations for v=10

Figure 25. Average ratio of random/ACTS for covering arrays by values per variable

The relationship between covering arrays and randomly generated tests presents some interesting issues. Generating covering arrays for combinatorial tests is complex; it has been shown to be an NP-hard problem. But generating tests randomly is trivial. Thus for large problems, we can compare the cost and time of generating a covering array versus producing tests randomly, measuring their coverage (Chapter 6), then adding tests as needed to provide full combinatorial coverage. Notice the last column of Table 10. For 4 way tests, once the number of parameters exceeds roughly 20, random generation will cover 99% or more of 4-way combinations. If a problem requires tests for 100 parameters, for example, covering array generators may require hours or days, or may simply be unable to handle that many parameters, but random tests could be generated quickly and easily. This is an option that may be cost effective even for smaller problems, and should be kept in mind for test planning.

With a sufficient number of assertions derived from a specification, the program can have a self-checking property [27, 60, 47]. The assertions can serve as a sort of embedded proof of important properties, such that if the assertions hold for all executions of the program, then the properties encoded in the assertions are guaranteed to hold. Then, if the assertions form a chain of logic that implies a formal statement of program properties, the program’s correctness with respect to these properties can be proven. We can take advantage of this scheme in combinatorial testing by demonstrating that the assertions hold for all t-way combinations of inputs. While this is not the same as a correctness proof, it is an effective way of integrating formal methods for correctness with program testing, and an extensive body of research has developed this idea for practical use (for a survey, see [4]). Some modern programming languages, such as Eiffel [52], include extensive support for including assertions that encode program properties, and tools such as the Java Modeling Language [42] have been designed to integrate assertions with testing. In many cases, using assertions to self-check important properties makes it practical to run thousands of tests in a fully automated fashion, so high-strength interactions of 4-way and above can be done in reasonable time.

With self-checking through assertions, thousands of tests can often be run at very low cost, allowing high-strength interaction coverage.

To clarify this somewhat abstract discussion, we will analyze requirements for a small function that handles withdrawal processing for an automated teller machine (ATM). Graphical user interface code for the ATM will not be displayed, as this would vary considerably for different systems. The decision not to include GUI code in this example also illustrates a practical limitation of this type of testing: there are many potential sources of error in a software project, and testing may not deal with all of them at the same time. The GUI code may be analyzed separately, or a more complex verification with assertions may specify properties of the GUI calls, but in the end some human involvement is needed to ensure that the screen information is properly displayed. However, we can do very thorough testing of the most critical aspects of the withdrawal module.

Requirements for the module are as follows:

The module has these inputs from the user after the user is authorized by another module:

string num: the user card number int amt: withdrawal amount requested

and these inputs from the system:

int balance: user account balance boolean minflag: account has minimum balance requirement int min: account minimum balance boolean odflag: account has overdraft protection int odamt: overdraft protection amount, int oddefault: overdraft default boolean hot: card flagged as stolen boolean limflag: withdrawal limit less than default int limit: withdrawal limit for this account int limdefault: withdrawal limit default

How should these requirements be translated into assertions and used in testing? Consider requirement 1: if minflag is set, then the balance before and after the withdrawal must be no less than the minimum balance amount. This could be translated directly into logic for assertions: minflag => balance >= min. If the assertion facility does not include logical implication, then the equivalent expression can be used, for example, in C syntax: !minflag || balance >= min.

However, we must also consider overdraft protection and withdrawal limits, so the assertion above is not adequate. Collecting conditions, we can develop assertions for each of the eight possible settings of minflag, odflag, and limflag. If there is a minimum balance requirement, no overdraft protection, and a withdrawal limit below the default, what is the relationship between balance and the other parameters?

minflag && !odflag && limflag => balance >= min – oddefault && amt <= limit

This relation must hold after the withdrawal, so to develop an assertion that must hold immediately before the withdrawal, substitute (balance – amt) for balance in the expression above:

balance0 – amt >= min – oddefault && amt <= limit

Assertions such as this would be placed immediately before the balance is modified, not at the beginning of the code for the withdrawal function. Code prior to the subtraction from balance should have ensured that properties encoded by assertions hold immediately before the subtraction, thus any violation of the assertions indicates an error in the code (or possibly in the assertions!) that must be investigated. This is illustrated in Figure 26, where “wdl_init.c” and “wdl_final.c” are files containing assertions such as developed above.

Including the card number, there are 11 parameters for this module. We need to partition the inputs to determine what values to use in generating a covering array. Partitions should cover valid and invalid values, minimum and maximum for ranges, and values at and on either side of boundaries. The bank uses a check digit scheme for card numbers to detect errors such as digit transposition when numbers are entered manually. A simple partition could be as follows:

string acct: {valid, invalid} int amt: {0, divisible by 20, not divisible by 20, max} int balance: {0, negative, positive, max int} int minflag: {T, F} int min: {0, negative, positive, max int} boolean odflag: {T, F} int odamt: {0, negative, positive, max int} int oddefault: {0, negative, positive, max int} boolean hot: {T, F} int acctlim: {0, negative, positive, max int} int lim: {0, negative, positive, max int}

1.while (!valid(acct)) {/* get account number input */} 2.if (amt > lim ) { return ERROR; } 3.else {

Figure 26. Withdrawal function code to be tested.

Assertions may be a cost-effective approach to test automation because they can be a simple extension of coding. In general, use of assertions is correlated with reduced error rates [41], but a very wide range of effectiveness results from variations in usage. In many applications, assertions are used in a very basic way, such as ensuring that null pointers are not passed to a function that will use them, or that parameters that may be used as divisors are non-zero.

More complex assertions can provide stronger assurance, but there are limits to their effectiveness. For example, invariants (properties that are expected to hold throughout a computation) cannot be assured without placing an assertion for every line of code. Since assertions must be executed to show the presence or absence of a property at some point, errors that prevent the assertion from being reached may not be detected. As an example, consider the code in Figure 26. If a coding error in the first few lines of the function prevents execution the code at of lines 15 and 17, the assertions will not be executed and it may be assumed that the test was passed. In this case, an ERROR return for the particular test case might trigger an investigation that would identify the faulty code, but this may not happen with other applications.

Assertions are one of the easiest to use and most effective approaches to dealing with the oracle problem. Properties ranging from simple parameter checks to effectively embedded proofs can be encoded in assertions, but special language support is needed for the stronger forms of assurance. This support may be provided as language preprocessors, as in the case of Anna [44] and others. Placement within code is particularly important to assertion effectiveness [60, 61], but if sufficiently strong assertions are embedded, the code becomes self-checking for important properties. With self-checking code, thousands of tests can be run at low cost in most cases, greatly improving the chances that faults will be detected.

One of the most effective ways to produce test oracles is to use a model of the system under test, and generate complete tests, including both input data and expected results, directly from the model. The model in this case is exactly what the name implies: it incorporates the most important aspects of the system, but not every detail such as the location of an amount on a screen (if it did include all details, it would be equivalent to the system itself). This chapter provides a step-by-step introduction to model-based automated generation of tests that provide combinatorial coverage. Procedures introduced in this tutorial will produce a set of complete tests, i.e., input values with the expected output for each set of inputs.

In addition to the ACTS covering array generator, (see Appendix C), we use NuSMV [18], a variant of the original SMV model checker. NuSMV is freely available and was developed by Carnegie Mellon University, Instituto per la Ricerca Scientifica e Tecnolgica (IRST), U. of Genova, and U. of Trento. NuSMV can be installed on either UNIX/Linux or Windows systems running Cygwin. Links and instructions for downloading NuSMV are included in the appendix.

Also needed is a formal or semi-formal specification of the system or subsystem under test (SUT). This can be in the form of a formal logic specification, but state transition tables, decision tables, pseudo-code, or structured natural language can also be used, as long as the rules are unambiguous. The specification will be converted to SMV code, which provides a precise, machine-processable set of rules that can be used to generate tests.

To apply combinatorial testing, two tasks must be accomplished:

The example in the following sections illustrates how these counterexamples are converted into tests. Other approaches to determining the correct output for each test can also be used. For example, in some cases we can run a model checker in simulation mode, producing expected results directly rather than through a counterexample.

Here we present a small example of a very simple access control system. The rules of the system are a simplified multi-level security system, given below, followed by a step-by-step construction of tests using a fully automated process.

Thus a pseudo-code representation of the access control rules is:

Tests produced will check that these rules are correctly implemented in a system.

This system is easily modeled in SMV as a simple two-state finite state machine. The START state merely initializes the system (line 8, Figure 27), with the rule above used to evaluate access as either GRANT or DENY (lines 9-13). For example, line 9 represents the first line of the pseudo-code above: in the current state (always START for this simple model), if u_l ≥ f_l then the next state is GRANT. Each line of the case statement is examined sequentially, as in a conventional programming language. Line 12 implements the “else DENY” rule, since the predicate “1” is always true. SPEC clauses given at the end of the model are simple “reflections” that duplicate the access control rules as temporal logic statements. They are thus trivially provable, but we are interested in using them to generate tests rather than to prove properties of the system.

Figure 27. SMV model of access control rules

Separate documentation on SMV should be consulted to fully understand the syntax used, but specifications of the form “AG ((predicate 1) -> AX (predicate 2))” indicate essentially that for all paths (the “A” in “AG”) for all states globally (the “G”), if predicate 1 holds then ( “->”) for all paths, in the next state (the “X” in “AX”) predicate 2 will hold. In the next section we will see how this specification can be used to produce complete tests, with test data input and the expected output for each set of input data.

Model checkers can be used to perform a variety of valuable functions, because they make it possible to evaluate whether certain properties are true of the system model. Conceptually, the model checker can be viewed as exploring all states of a system model to determine if a property claimed in a SPEC statement is true. If the statement can be proved true for the given model, the model checker reports this fact. What makes a model checker particularly valuable for many applications, though, is that if the statement is false, the model checker not only reports this, but also provides a “counterexample” showing how the claim in the SPEC statement can be shown false. The counterexample will include input data values and a trace of system states that lead to a result contrary to the SPEC claim (Figure 28). In the process described in this section, the input data values will be the covering array generated by ACTS.

For advanced uses in test generation, this counterexample generation capability is very useful for proving properties such as liveness (absence of deadlock) that are difficult to ensure through testing. In this tutorial, however, we will simply use the model checker to determine whether a particular input data set makes a SPEC claim true or false. That is, we will enter claims that particular results can be reached for a given set of input data values, and the model checker will tell us if the claim is true or false. This gives us the ability to match every set of input test data with the result that the system should produce for that input data.

The model checker thus automates the work that normally must be done by a human tester – determining what the correct output should be for each set of input data. In some cases, we may have a “reference implementation”, that is, an implementation of the functions that we are testing that is assumed to be correct. This happens, for example, in conformance testing for protocols, where many vendors implement their own software for the protocol and submit it to a test lab for comparison with an existing implementation of the protocol. In this case the reference implementation could be used for determining the expected output, instead of the model checker. Of course before this can happen the reference implementation itself must be thoroughly tested before it can be used as the gold standard for testing other products, so the method we describe here may be needed to produce tests for the original reference implementation.

Checking the properties in the SPEC statements shows that they match the access control rules as implemented in the FSM, as expected. In other words, the claims we made about the state machine in the SPEC clauses can be proven. This step is used to check that the SPEC claims are valid for the model defined previously. If NuSMV is unable to prove one of the SPECs, then either the spec or the model is incorrect. This problem must be resolved before continuing with the test generation process. Once the model is correct and SPEC claims have been shown valid for the model, counterexamples can be produced that will be turned into test cases, by which we mean a set of test inputs with the expected result for these inputs. In other words, ACTS is used to generate tests, then the model checker determines expected results for each test.

Figure 28. NuSMV output

[System] [Parameter] u_l: 0,1,2 f_l: 0,1,2 act: rd,wr [Relation] [Constraint] [Misc]

For this application, the [Parameter] section of the file is all that is needed. Other tags refer to advanced functions that will be explained in other documents. After the system definition file is saved, run ACTS as shown below: java -Ddoi=2 –jar acts_cmd.jar ActsConsoleManager in.txt out.txt

The “-Ddoi=2” argument sets the degree of interaction for the covering array that we want ACTS to compute. In this case we are using simple 2-way, or pairwise, interactions. (For a system with more parameters we would use a higher strength interaction, but with only three parameters, 3-way interaction would be equivalent to exhaustive testing.) ACTS produces the output shown in Figure 29.

The next step is to assign values from the covering array to parameters used in the model. For each test, we claim that the expected result will not occur. The model checker determines combinations that would disprove these claims, outputting these as counterexamples. Each counterexample can then be converted to a test with known expected result. Every test from the ACTS tool is used, with the model checker supplying expected results for each test. (Note that the trivially provable positive claims have been commented out. Here we are concerned with producing counterexamples.)

Recall the structure introduced in Section 9.1: Ci => ~Rj. Here Ci is the set of parameter values from the covering array. For example, for configuration #1 in Section:

u_l = 0 & f_l = 0 & act = rd

As can be seen below, for each of the 9 configurations in the covering array we create a SPEC claim of the form:

SPEC AG(( <covering array values> ) -> AX !(access = <result>));

This process is repeated for each possible result, in this case either “GRANT” or “DENY”, so we have 9 claims for each of the two results. The model checker is able to determine, using the model defined in Section 9.2.1, which result is the correct one for each set of input values, producing a total of 9 tests.

Excerpt: ... -- reflection of the assign for access --SPEC AG ((u_l >= f_l & act = rd ) -> AX (access = GRANT)); --SPEC AG ((f_l >= u_l & act = wr ) -> AX (access = GRANT)); --SPEC AG (!((u_l >= f_l & act = rd ) | (f_l >= u_l & act = wr )) -> AX (access = DENY));

SPEC AG((u_l = 0 & f_l = 0 & act = rd) -> AX !(access = GRANT)); SPEC AG((u_l = 0 & f_l = 1 & act = wr) -> AX !(access = GRANT)); SPEC AG((u_l = 0 & f_l = 2 & act = rd) -> AX !(access = GRANT)); SPEC AG((u_l = 1 & f_l = 0 & act = wr) -> AX !(access = GRANT)); SPEC AG((u_l = 1 & f_l = 1 & act = rd) -> AX !(access = GRANT)); SPEC AG((u_l = 1 & f_l = 2 & act = wr) -> AX !(access = GRANT)); SPEC AG((u_l = 2 & f_l = 0 & act = rd) -> AX !(access = GRANT)); SPEC AG((u_l = 2 & f_l = 1 & act = wr) -> AX !(access = GRANT)); SPEC AG((u_l = 2 & f_l = 2 & act = rd) -> AX !(access = GRANT));

SPEC AG((u_l = 0 & f_l = 0 & act = rd) -> AX !(access = DENY)); SPEC AG((u_l = 0 & f_l = 1 & act = wr) -> AX !(access = DENY)); SPEC AG((u_l = 0 & f_l = 2 & act = rd) -> AX !(access = DENY)); SPEC AG((u_l = 1 & f_l = 0 & act = wr) -> AX !(access = DENY)); SPEC AG((u_l = 1 & f_l = 1 & act = rd) -> AX !(access = DENY)); SPEC AG((u_l = 1 & f_l = 2 & act = wr) -> AX !(access = DENY)); SPEC AG((u_l = 2 & f_l = 0 & act = rd) -> AX !(access = DENY)); SPEC AG((u_l = 2 & f_l = 1 & act = wr) -> AX !(access = DENY)); SPEC AG((u_l = 2 & f_l = 2 & act = rd) -> AX !(access = DENY));

NuSMV produces counterexamples where the input values would disprove the claims specified in the previous section. Each of these counterexamples is thus a set of test data that would have the expected result of GRANT or DENY.

For each SPEC claim, if this set of values cannot in fact lead to the particular result Rj, the model checker indicates that this is true. For example, for the configuration below, the claim that access will not be granted is true, because the user’s clearance level (u_l = 0) is below the file’s level (f_l = 2):

-- specification AG (((u_l = 0 & f_l = 2) & act = rd) -> AX !(access = GRANT)) is true

If the claim is false, the model checker indicates this and provides a trace of parameter input values and states that will prove it is false. In effect this is a complete test case, i.e., a set of parameter values and expected result. It is then simple to map these values into complete test cases in the syntax needed for the system under test.

Excerpt from NuSMV output:

-- specification AG (((u_l = 0 & f_l = 0) & act = rd) -> AX access = GRANT)) is false -- as demonstrated by the following execution sequence Trace Description: CTL Counterexample Trace Type: Counterexample -> State: 1.1 <- u_l = 0 f_l = 0 act = rd access = START_ -> Input: 1.2 <- -> State: 1.2 <- access = GRANT

The model checker finds that 6 of the input parameter configurations produce a result of GRANT and 3 produce a DENY result, so at the completion of this step we have successfully matched up each input parameter configuration with the result that should be produced by the SUT.

We now strip out the parameter names and values, giving tests that can be applied to the system under test. This can be accomplished using a variety of methods; a simple script used in this example is given in the appendix. The test inputs and expected results produced are shown below:

u_l = 0 & f_l = 0 & act = rd -> access = GRANT u_l = 0 & f_l = 1 & act = wr -> access = GRANT u_l = 1 & f_l = 1 & act = rd -> access = GRANT u_l = 1 & f_l = 2 & act = wr -> access = GRANT u_l = 2 & f_l = 0 & act = rd -> access = GRANT u_l = 2 & f_l = 2 & act = rd -> access = GRANT u_l = 0 & f_l = 2 & act = rd -> access = DENY u_l = 1 & f_l = 0 & act = wr -> access = DENY u_l = 2 & f_l = 1 & act = wr -> access = DENY

These test definitions can now be post-processed using simple scripts written in PERL, Python, or similar tool to produce a test harness that will execute the SUT with each input and check the results. While tests for this trivial example could easily have been constructed manually, the procedures introduced in this tutorial can, and have, been used to produce tens of thousands of complete test cases in a few minutes, once the SMV model has been defined for the SUT.

Model based test generation trades up-front analysis and specification time against the cost of greater human interaction for analyzing test results. The model or formal specification may be costly to produce, but once it is available, large numbers of tests can be generated, executed, and analyzed without human intervention. This can be an enormous cost savings, since testing usually requires 50% or more of the software development budget. For example, suppose a $100,000 development project expects to spend $50,000 on testing, because of the staff time required to code and run tests, and analyze results. If a formal model can be created for $20,000, complete tests generated and analyzed automatically, with another $10,000 for a smaller number of human-involved tests and analysis, then the project will save 20%. One tradeoff for this savings is the requirement for staff with skills in formal methods, but in some cases this approach may be practical and highly cost-effective.

Developing dependable software requires preventing as many bugs as possible and detecting, then repairing, those that remain. Testing can identify flaws in software, but after a failed test is discovered, it is necessary to determine what caused the failure. In most cases this may be accomplished for combinatorial testing in the same way as other test methodologies, using a debugger or in-circuit emulator. But one goal of combinatorial testing is to identify the particular t-way combination that triggered a failure. The problem of fault localization, identifying such combination(s), is an area of active research, but some basic approaches can be identified. The discussion in this chapter assumes systems are deterministic, such that a particular input always generates the same output.

At first glance, fault localization may not appear to be a difficult problem, and in many cases it will not be, but we want to automate the process as much as possible. To understand the size of the problem, consider a module that has 20 input parameters. A set of 3-way covering tests passes 100%, but several tests derived from a 4-way covering array result in failure. (Therefore, at least four parameter values are involved in triggering the failure. It is possible that a 5-way or higher combination caused the failure, since any set of t-way tests also includes (t+1)-way and higher strength combinations as well.) A test with 20 input parameters has C(20, 4) = 4,845 4-way combinations, yet presumably only one (or just a few) of these triggered the failure. To determine the combination at fault, a variety of strategies can be used.

The analysis presented here applies to a deterministic system, in which a particular set of input values always results in the same processing and outputs. Let P = {combinations in passing tests} and F = {combinations in failing tests} and C = {fault-triggering combinations}. Then F \ P , combinations in failing tests that are not in any passing tests, must contain the fault-triggering combinations C because if any of those in C were in P, then the test would have failed. So in most cases, C ⊆ F \ P , as shown in Figure 30.

Figure 30. Combinations in failing tests but not in passing tests.

}

If line 3 is incorrectly implemented as “return 7” instead of “return 2”, then p(1,1,1,1,0) =

1 because “a && b” evaluates to 1, but p(0,1,1,1,0) will detect the error. A complete 3-way covering test set will detect the error because it must include at least one test with values 0,1,1,1,. and one with 1,0,1,1,. . Figure 31 shows tests for this example for t = 2, 3, and 4. Failing tests are underlined.

Figure 31. Tests for fault location example.

The heuristics above can be applied to combinations in the failed tests to identify possible failure-triggering combinations, shown in Figure 32.

Figure 32. Combinations in failing tests.

Figure 33. 3-way and 4-way combinations in \(F \setminus P\)

As shown in the example above, it is a non-trivial matter to determine the failure-triggering combination(s) from test results alone. When source code is available, the methods described in this section are probably unnecessary, and can be replaced with conventional debugging techniques. In black-box testing situations where there is no source code, these methods may be useful in narrowing the search for failure-triggering combinations. Tools to implement these methods have been developed and are available from the ACTS project site.

When source code is available, the best way to identify the cause of a failure is with conventional debugging techniques, since the error must be fixed in code anyway. With pure black-box testing and no access to source code, the heuristics discussed in this chapter may help to narrow down possible causes. Usually there will be many combinations identified as possible causes, so substantial additional testing may be needed to determine the exact cause.

This appendix reviews a few basic facts of combinatorics, regular expressions, and mathematical logic that are necessary to understand the concepts in this publication.

abc, abd, abe, acd, ace, ade, bcd, bce, bde, cde

Each of these will need to be instantiated with all 8 possible configurations of three binary variables:

000, 001, 010, 011, 100, 101, 110, 111

abc abd abe acd ace ade bcd bce bde cde 010 000 011 001 001 001 100 101 101 001

Many software testing problems can be solved with an orthogonal array, a structure that has been used for combinatorial testing in fields other than software for decades. An orthogonal array, OAλ (N;t,k,v) is an N x k array. In every N x t subarray, each t-tuple occurs exactly λ times. We refer to t as the strength of the coverage of interactions, k as the number of parameters or components (degree), and v as the number of possible values for each parameter or component (order).

Covering Arrays

Figure 1. 3-way covering array for 10 parameters with 2 values each.

for \(n\) variables with \(v\) values each.

Table 1. Growth of \(v^t\)

Despite the possibly discouraging numbers in the table above, there is some good news. Note that formula (2) grows only logarithmically with the number of variables, n. This is fortunate for software testing. Early applications of combinatorial methods were typically involved with small numbers of variables, such as a few different types of crops or fertilizers, but for software testing, we must deal with tens, or in some cases hundreds of variables.

Regular expressions are formal descriptions of strings of symbols, which may represent text, events, characters, or other objects. They are developed within automata theory and formal languages, where it is shown that there are direct mappings between expressions and automata to process them, and are encountered in many areas within computer science. In combinatorial testing they may be encountered in sequence covering or in processing test input or output. Implementations vary, but standard syntax is explained below.

Basic elements of regular expressions include:

The operators above can be combined with symbols to create arbitrarily complex expressions. Examples include:

Many regular expression utilities such as egrep support a broader range of operators and features. Readers should consult documentation for grep, egrep, or other regular expression processors for detailed coverage of the options available on particular tools.

One of the most important questions in software testing is "how much is enough"? For combinatorial testing, this question includes determining the appropriate level of interaction that should be tested. That is, if some failure is triggered only by an unusual combination of more than two values, how many testing combinations are enough to detect all errors? What degree of interaction occurs in real system failures? This section summarizes what is known about these questions based on research by NIST and others [4, 7, 34, 35, 36, 65].

Table 1 below summarizes what we know from empirical studies of a variety of application domains, showing the percentage of failures that are triggered by the interaction of one to six variables. For example, 66% of the medical devices were triggered by a single variable value, and 97% were triggered by either one or two variables interacting. Although certainly not conclusive, the available data suggest that the number of interactions involved in system failures is relatively low, with a maximum from 4 to 6 in the six studies cited below. (Note: TCAS study used seeded errors, all others are "naturally occurring", * = not reported.)

Table 1. Number of variables involved in triggering software failures