A Quantitative Approach to Input Generation in Real-Time Testing of Stochastic Systems

摘要

In the process of testing of concurrent timed systems, input generation identifies values of temporal parameters that let the Implementation Under Test (IUT) execute selected cases. However, when some parameters are not under control of the driver, test execution may diverge from the selected input and produce an inconclusive behavior. We formulate the problem on the basis of an abstraction of the IUT which we call partially stochastic Time Petri Net (psTPN), where controllable parameters are modeled as nondeterministic values and noncontrollable parameters as random variables with general (GEN) distribution. With reference to this abstraction, we derive the analytical form of the probability that the IUT runs along a selected behavior as a function of choices taken on controllable parameters. In the applicative perspective of real-time testing, this identifies a theoretical upper limit on the probability of a conclusive result, thus providing a means to plan the number of test repetitions that are necessary to guarantee a given probability of test-case coverage. It also provides a constructive technique for an optimal or suboptimal approach to input generation and a way to characterize the probability of conclusive testing under other suboptimal strategies.