Posted on by Testingin
By Donald Firesmith
Software Solutions Division
Many system and software developers and testers, especially those who have primarily worked in business information systems, assume that systems--even buggy systems--behave in a deterministic manner. In other words, they assume that a system or software application will always behave in exactly the same way when given identical inputs under identical conditions. This assumption, however, is not always true. While this assumption is most often false when dealing with cyber-physical systems, new and even older technologies have brought various sources of non-determinism, and this has significant ramifications on testing. This blog post, the first in a series, explores the challenges of testing in a non-deterministic world.
Testing: The Scope of This Post
Before I get into these ramifications, it is important to clarify the scope of this post, which is strictly testing. Even though other verification-and-validation approaches (such as static and dynamic analysis, inspection, and review) are also useful and relevant when verifying non-deterministic systems and software, I will not address them here because testing is more than sufficient for multiple blog postings.
Specifically, testing compares a system's actual behavior with its expected behavior so that discrepancies (bugs) can be analyzed to uncover the underlying defects and thereby determine quality. Note that these discrepancies can be visible failures (incorrect visible behavior), as well as hidden faults (incorrect encapsulated mode, state, or data). Testing involves
As shown in the following figure, testability (i.e., the degree to which testing can be effective and efficient) requires meeting the following three prerequisites:
Tester Assumptions Regarding Non-Determinism
With the scope of this post clarified, we can now address the tester's assumption that systems and software behave in a deterministic manner and the ramifications of this incorrect assumption. Many developers and testers assume that tests are always repeatable because
In many modern domains, however, tests will not always yield the same result, and this makes testing much harder. Finding the resulting bugs that are rare, intermittent, and hard to reproduce, localize, and diagnose is the new challenge.
Trends Affecting Non-Determinism
The following recent technology trends also increase the likelihood that these assumptions are false:
Types of Non-Determinism
So far, I have been intentionally vague when it comes to the meaning of the words "non-determinism" and "non-deterministic." While I do not intend to use mathematical precision, a little more clarity would be useful.
First of all, non-determinism can be actual or only apparent. Actual non-determinism occurs when there is no theoretical way of predetermining the system's exact behavior, such as behavior that is determined by quantum physics (e.g., using nuclear decay to generate truly random numbers). Apparent non-determinism occurs when there is no practical way for the tester (or test oracle) to predetermine the system's exact behavior. This apparent non-determinism can be due to overwhelming complexity or to inadequate controllability, visibility, and oracle(s).
From a practical point of view, both actual and apparent non-determinism have the same impact on testability. With non-deterministic systems and software, you can run the exact same test case (i.e., with the exact same test inputs under the exact same test preconditions) multiple times and get different results (i.e., different test outputs and test postconditions). Running a single test case only once is insufficient to determine whether the test case truly passes or fails. Unfortunately, requirements-driven testing is too often performed using only a single test case per requirement. This practice is insufficient, even when not contending with non-determinism.
Testers must be aware of and take into account four types of non-deterministic behavior based on the source of that behavior:
As shown in Figure 2 below, testers also must address non-determinism that occurs in
Examples of Non-Deterministic Systems
Non-deterministic systems are ubiquitous. As mentioned previously, they are found in all manner of cyber-physical systems:
Non-deterministic systems are common when dealing with modern hardware and software technologies, such as multicore processors, multiple processors (or computers or devices), virtual machines (VMs), multithreading and concurrent programming languages, and cloud computing.
Testers may also find non-deterministic behavior in the development environments, development and operational test environments, and the physical operational environment.
Testing is largely about uncovering defects. When dealing with systems susceptible to non-deterministic behavior, developers and testers should pay special attention to the testing for the following types of non-deterministic defects when designing software and the associated test suites:
The following related challenges often crop up when testing non-deterministic systems.
Testing Ramifications of Non-Determinism
Many developers and testers would benefit from additional training in non-deterministic defects and how to test them. Developers and testers do not design, implement, and execute tests designed to uncover non-deterministic defects, making testing less effective and efficient at detecting them. As a result, testing fails to uncover non-deterministic defects resulting in an increase in false positive and false negative test results. Testing provides false confidence that such defects do not exist in the system, and they escape into system operation where they can lead to intermittent and hard to reproduce faults and failures.
Non-deterministic software often requires more test automation due to the need for large suites of test cases:
Non-deterministic behavior makes test automation challenging:
We live and work in a non-deterministic world, and that has significant ramifications on how we need to test our systems and software. In the next post, I will provide recommendations for addressing the challenges associated with testing non-deterministic systems and software.
View my January 2016 webinar A Taxonomy of Testing Types.
View my podcast Common Testing Problems: Pitfalls to Prevent and Mitigate.