Testing Probabilistic and Stochastic Systems (ProbTest)
Lead Research Organisation:
Brunel University London
Department Name: Information Systems Computing and Maths
Abstract
Traditionally, methods for formally specifying or modelling systems have concentrated on the representation of the functional behaviour of the systems. Such models can be used as the basis of testing that the system under test (SUT) has the required set of behaviours: its functional behaviour is correct. They are an effective way of representing the required functional properties of the system under test but do not allow us to express desired non-functional properties such as time, probabilities or resources. Several formalisms were extended in order to deal with these kind of properties. The new languages allow the explicit representation of the probability of performing a certain task, for example that if a function of the system is used it should provide the expected functionality at least 99.9% of the time. They also allow us to express the time that should be consumed by the system while performing tasks, either given by fixed amounts of time or defined in probabilistic/stochastic terms. For example, we may require that on average a result is produced within 1 second.ProbTest will consider models that include probabilities and stochastic time. Many systems have real-time constraints and thus the inclusion of time is important. Probabilities are highly relevant where resources are shared and so Quality of Service requirements can be probabilistic. In addition, many systems are probabilistic in nature due to either the use of subsystems communications over a (possibly unreliable) medium or through the system consisting of several threads or parallel components and there being different possible synchronization sequences. There are also a number of communications protocols, such as Bluetooth and Ethernet, that have probabilistic requirements and in order to reason about embedded systems, which are state-based, it is often necessary to use probabilities. Thus, there are systems with probabilistic and/or stochastic requirements and it is important to have efficient, systematic methods for testing whether they actually satisfy these requirements. ProbTest is a four year project that will support collaboration in this area between Hierons, of Brunel University, and Nunez, of Universidad Complutense de Madrid.
Publications
Merayo M
(2009)
Testing timed systems modeled by Stream X-machines
in Software & Systems Modeling
Hierons R
(2010)
Formal Techniques for Distributed Systems
Hierons R
(2010)
Scenarios-Based Testing of Systems with Distributed Ports
Molinero C
(2011)
Advances in Computational Intelligence
Hierons R
(2011)
Implementation relations and test generation for systems with distributed interfaces
in Distributed Computing
Hierons R
(2011)
Scenarios-based testing of systems with distributed ports
in Software: Practice and Experience
Hierons R
(2012)
FM 2012: Formal Methods
Hierons R
(2012)
Using schedulers to test probabilistic distributed systems
in Formal Aspects of Computing
Núñez A
(2012)
Using genetic algorithms to generate test sequences for complex timed systems
in Soft Computing
Hierons R
(2013)
Formal Techniques for Distributed Systems
Hierons R
(2014)
Timed implementation relations for the distributed test architecture
in Distributed Computing
Description | The work concentrated on testing of software/systems that requirements that including timing information (e.g. the system should respond within 2 seconds) or probabilistic information (e.g. the correct results should be returned 99% of the time, the outcome should be heads 50% of the time and tails the other 50% of the time). One of things we discovered is that such software testing is particularly challenging if the system under test (SUT) interacts with its environment at multiple physically distributed locations. This is now quite a common scenario - consider, for example, the separate users of a web-system - and introduces the additional challenge that each tester/user only observes its interactions with the SUT and so no user/tester has a global view. We devised new software testing methods for such software/systems. |
Exploitation Route | In the short-term, there is the potential to build on this work to further improve the test generation techniques. In the longer-term, there is the potential for this work to feed into the automated testing of systems with probabilistic requirements and also distributed systems. |
Sectors | Digital/Communication/Information Technologies (including Software) |
Description | Madrid |
Organisation | Complutense University of Madrid |
Country | Spain |
Sector | Academic/University |
PI Contribution | We collaborated on the topic of testing probabilistic and/or stochastic systems on the basis of models/specifications. I provided expertise in test generation and also distributed testing. |
Collaborator Contribution | We collaborated on the topic of testing probabilistic and/or stochastic systems on the basis of models/specifications. They provided specific expertise in terms of probabilistic and stochastic models. |
Impact | We developed novel test generation algorithms. There have been a number of resultant papers. |
Start Year | 2009 |