Testing Probabilistic and Stochastic Systems (ProbTest)

Lead Research Organisation: Brunel University London
Department Name: Information Systems Computing and Maths


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.


10 25 50
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