Distributed testing without encountering controllability and observability problems

The objective of testing is to determine whether a system under test conforms to its specification. In distributed test architectures that utilize remote testers, this objective can be complicated by the fact that testers may encounter problems relating to controllability and observability during the application of a test sequence. Existing solutions to these problems involve first constructing a test sequence from the specification of an implementation under test, and then inserting coordination messages or appending selected test subsequences that prevent the occurrences of controllability and observability problems during the application of the resulting test sequence. This paper proposes a method that utilizes a set of transformation rules to construct an auxiliary directed graph from a given specification, and constructs a rural Chinese postman tour in this graph to yield a minimum-length test sequence where there is no potential controllability or observability problems, and where the use of coordination messages is minimized.     

Checking sequences for distributed test architectures

Controllability and observability problems may manifest themselves during the application of a checking sequence in a test architecture where there are multiple remote testers. These problems often require the use of external coordination message exchanges among testers during testing. However, the use of coordination messages requires the existence of an external network that can increase the cost of testing and can be difficult to implement. In addition, the use of coordination messages introduces delays and this can cause problems where there are timing constraints. Thus, sometimes it is desired to construct a checking sequence from the specification of the system under test that will be free from controllability and observability problems without requiring the use of external coordination message exchanges. This paper gives conditions under which it is possible to produce such a checking sequence, using multiple distinguishing sequences, and an algorithm that achieves this.     

多单元协议一致性测试中的同步序列的生成

有限状态机模型一般被用来描述通信协议和其它各类的分布式系统,对于一个多端口的有限状态机,需要多个测试单元进行测试,使用一个包括K个（K≥2）测试单元的测试系统可以检查一个多单元通信协议软件的收发行为是否与协议规格一致,在测试过程中,K个测试单元之间可能会出珊步问题,目前,主要是通过增加外部同步操作来解决同步问题,提出了一种新的同步测试序列生成模型－－同步有向图,它可以判断一个给定的协议规格是否可以在不需要外部同步操作的情况下,产生同步测试序列;如果可以产生,则此生成中以将非同步测试相应的同步测试序列;另外此生成模型还可以用来选择为测试系统增加外部同步通道的方法。     

UIO sequence based checking sequences for distributed test architectures

This study addresses the construction of a preset checking sequence that will not pose controllability (synchronization) and observability (undetectable output shift) problems when applied in distributed test architectures that utilize remote testers. The controllability problem manifests itself when a tester is required to send the current input and because it did not send the previous input nor did it receive the previous output it cannot determine when to send the input. The observability problem manifests itself when a tester is expecting an output in response to either the previous input or the current input and because it is not the one to send the current input, it cannot determine when to start and stop waiting for the output. Based on UIO sequences, a checking sequence construction method is proposed to yield a sequence that is free from controllability and observability problems.     

Overcoming controllability problems with fewest channels between testers

When testing a system that has multiple physically distributed ports/interfaces it is normal to place a tester at each port. Each tester observes only the events at its port and it is known that this can lead to additional controllability problems. While such controllability problems can be overcome by the exchange of external coordination messages between the testers, this requires the deployment of an external network and may thus increase the costs of testing. The problem studied in this paper is finding a minimum number of coordination channels to overcome controllability problems in distributed testing. Three instances of this problem are considered. The first problem is to find a minimum number of channels between testers in order to overcome the controllability problems in a given test sequence to be applied in testing. The second problem is finding a minimal set of channels that allow us to overcome controllability problems in any test sequence that may be selected from the specification of the system under test. The last problem is to find a test sequence that achieves a particular test objective and in doing so allows fewest channels to be used.     

Coordination Algorithm for Distributed Testing

With the emergence of new models, architectures and middleware such as ODP, TINA and CORBA, for developing open distributed systems, testing technology requires adaptation for use within conformance assessment in such systems. All these frameworks are object-based and aim at creating open distributed environments supporting interworking, interoperability, and portability, in spite of heterogeneity and autonomy of the related systems. In this context, an open distributed system may be viewed as a system providing standardized distributed interfaces for interacting with other systems. Conformance of such a system can be assessed by attaching a related tester at each provided interface. However, many problems of controllability and observability influencing fault detection during the testing process, arise if there is no coordination between the testers. In this paper, we show how to cope with these problems by using test coordination procedures in a distributed testing architecture.     

Using status messages in the distributed test architecture

If the system under test has multiple interfaces/ports and these are physically distributed then in testing we place a tester at each port. If these testers cannot directly communicate with one another and there is no global clock then we are testing in the distributed test architecture. If the distributed test architecture is used then there may be input sequences that cannot be applied in testing without introducing controllability problems. Additionally, observability problems can allow fault masking. In this paper we consider the situation in which the testers can apply a status message: an input that causes the system under test to identify its current state. We show how such a status message can be used in order to overcome controllability and observability problems.     

基于np-FSM的分布式协议的虚拟多端口测试方法

在协议工程领域,协议测试是非常重要的工作;对于分布式协议的测试多采用多端口有限状态机模型进行描述;由于分布式协议测试存在控制观察问题,需要对测试序列进行同步和协调;通过对现有分布式测试模型的改进,引入虚拟多端口测试的方法,极大地简化了多个测试器之间的同步和协调问题,并且不会显著增加系统的构建成本,提高了测试效率.     

基于同步有向图的同步测试序列生成方法

使用多测试单元的测试系统可以对多端口协议实现进行一致性测试，但是在进行这种一致性测试时，测试系统各个端口之间可能会出现同步问题，现在，解决同步问题常用的办法是在测试单元相应端口之间增加同步连接，然后通过此同步连接相互发送同步消息来进行同步，多端口协议和其它类型的分布式系统可以用有限状态机模型来描述，目前，同步问题被分为双端口同步问题，多端口同步问题，紧同步问题等多种类型，该文考虑两种有限状态机测试问题，第一种是面向端口的测试，不考虑有限状态机测试单元之间的通信问题，第二种面向组的测试，有限状态机中的各个端口被分成互不相关的多个组，属于不同组中的测试单元之间互不通信，该文提出了一种基于同步有向图的同步测试序列生成方法，这种生成方法适用于Pair同步，Port同步和组同步问题，并且，这种方法也可以用来判断如何在非同步测试序列中增加同步通信，将非同步测试序列转化为同步测试序列。     

Exploring alternatives for transition verification

When an implementation under test (IUT) is state-based, and its expected abstract behavior is given in terms of a finite state machine (FSM), a checking sequence generated from a specification FSM and applied to an IUT for testing can provide us with high-level confidence in the correct functional behavior of our implementation. One of the issues here is to generate efficient checking sequences in terms of their lengths. As a major characteristics, a checking sequence must contain all β-sequences for transition verification. In this paper, we discuss the possibility of reducing the lengths of checking sequences by making use of the invertible transitions in the specification FSM to increase the choice of β-sequences to be considered for checking sequence generation. We present a sufficient condition for adopting alternative β-sequences and illustrate typical ways of incorporating these alternative β-sequences into existing methods for checking sequence generation to reduce the lengths. Compared to the direct use of three existing methods, our experiments show that most of the time the saving gained by adopting alternative β-sequences falls in the range of 10–40%.     

Overcoming controllability problems in distributed testing from an input output transition system

This paper concerns the testing of a system with physically distributed interfaces, called ports, at which it interacts with its environment. We place a tester at each port and the tester at port p observes events at p only. This can lead to controllability problems, where the observations made by the tester at a port p are not sufficient for it to be able to know when to send an input. It is known that there are test objectives, such as executing a particular transition, that cannot be achieved if we restrict attention to test cases that have no controllability problems. This has led to interest in schemes where the testers at the individual ports send coordination messages to one another through an external communications network in order to overcome controllability problems. However, such approaches have largely been studied in the context of testing from a deterministic finite state machine. This paper investigates the use of coordination messages to overcome controllability problems when testing from an input output transition system and gives an algorithm for introducing sufficient messages. It also proves that the problem of minimising the number of coordination messages used is NP-hard.     

Canonical finite state machines for distributed systems

There has been much interest in testing from finite state machines (FSMs) as a result of their suitability for modelling or specifying state-based systems. Where there are multiple ports/interfaces a multi-port FSM is used and in testing, a tester is placed at each port. If the testers cannot communicate with one another directly and there is no global clock then we are testing in the distributed test architecture. It is known that the use of the distributed test architecture can affect the power of testing and recent work has characterised this in terms of local s-equivalence: in the distributed test architecture we can distinguish two FSMs, such as an implementation and a specification, if and only if they are not locally s-equivalent. However, there may be many FSMs that are locally s-equivalent to a given FSM and the nature of these FSMs has not been explored. This paper examines the set of FSMs that are locally s-equivalent to a given FSM M. It shows that there is a unique smallest FSM χ_min(M) and a unique largest FSM χ_max(M) that are locally s-equivalent to M. Here smallest and largest refer to the set of traces defined by an FSM and thus to its semantics. We also show that for a given FSM M the set of FSMs that are locally s-equivalent to M defines a bounded lattice. Finally, we define an FSM that, amongst all FSMs locally s-equivalent to M, has fewest states. We thus give three alternative canonical FSMs that are locally s-equivalent to an FSM M: one that defines the smallest set of traces, one that defines the largest set of traces, and one with fewest states. All three provide valuable information and the first two can be produced in time that is polynomial in terms of the number of states of M. We prove that the problem of finding an s-equivalent FSM with fewest states is NP-hard in general but can be solved in polynomial time for the special case where there are two ports.     

基于通信多端口有限状态机的协议互操作性测试生成研究

协议测试是一种保证网络通信协议实现质量的重要技术，互操作性测试是一类常用的协议测试技术．文章提出了一种基于通信多端口有限状态机模型的协议互操作忡测试生成方法．首先采用已有的基于可达性分析的方法生成集中式测试序列；然后采用单一错误模型对其进行系统的错误覆盖分析，为达到更高的错误覆盖度，进一步提出一种增强的测试生成算法；最后讨论了互操作性测试巾的控制观察问题，选择适当的分布式测试架构，并进而生成分布式同步测试序列．实验结果表明：与原有方法相比，该方法可以有效地提高测试集的错误覆盖，并具备一定的可行性和有效性．     

Bisimilarity control of partially observed nondeterministic discrete event systems and a test algorithm

In this paper, the bisimilarity control of discrete event systems (DESs) under partial observations is investigated, where the plant and the specification are allowed to be nondeterministic. A notation of simulation-based controllability and a synchronization scheme for the supervised system are formalized based on the simulation relation between the specification and the plant. It is shown that the existence of bisimilarity supervisors is characterized by the notions of the simulation-based controllability and the language observability, which extends the traditional results of supervisory control from language equivalence to bisimulation equivalence. In addition, a polynomial algorithm to test the simulation-based controllability is developed by constructing a computing tree. This algorithm together with the test of language observability can be used to check the existence of bisimilarity supervisors.     

A temporal approach for testing distributed systems

This paper deals with testing distributed software systems. In the past, two important problems have been determined for executing tests using a distributed test architecture: controllability and observability problems. A coordinated test method has subsequently been proposed to solve these two problems. In the present article: 1) we show that controllability and observability are indeed resolved if and only if the test system respects timing constraints, even when the system under test is non-real-time; 2) we determine these timing constraints; 3) we determine other timing constraints which optimize the duration of test execution; 4) we show that the communication medium used by the test system does not necessarily have to be FIFO; and 5) we show that the centralized test method can be considered just as a particular case of the proposed coordinated test method.     

Checking experiments for stream X-machines

Stream X-machines are a state based formalism that has associated with it a particular development process in which a system is built from trusted components. Testing thus essentially checks that these components have been combined in a correct manner and that the orders in which they can occur are consistent with the specification. Importantly, there are test generation methods that return a checking experiment: a test that is guaranteed to determine correctness as long as the implementation under test (IUT) is functionally equivalent to an unknown element of a given fault domain Ψ. Previous work has show how three methods for generating checking experiments from a finite state machine (FSM) can be adapted to testing from a stream X-machine. However, there are many other methods for generating checking experiments from an FSM and these have a variety of benefits that correspond to different testing scenarios. This paper shows how any method for generating a checking experiment from an FSM can be adapted to generate a checking experiment for testing an implementation against a stream X-machine. This is the case whether we are testing to check that the IUT is functionally equivalent to a specification or we are testing to check that every trace (input/output sequence) of the IUT is also a trace of a nondeterministic specification. Interestingly, this holds even if the fault domain Ψ used is not that traditionally associated with testing from a stream X-machine. The results also apply for both deterministic and nondeterministic implementations.     

A temporal agent based approach for testing open distributed systems

The development of distributed testing frameworks is more complex, where the implementation process must consider the mechanisms and functions required to support interaction as long as the communication and the coordination between distributed testing components. The typical reactions of such systems are the generation of errors‘set: time outs, locks, observability, controllability and synchronization problems. In other side, the distributed testing process must not only check if the output events have been observed, but also the dates when these events have been occurred. In this paper, we show how to cope with these problems by using a distributed testing method including timing constraints. Afterwards, a multi-agent architecture is proposed in the design process to describe the behavior of testing a distributed chat group application on high level of abstraction.     

Testing distributed real-time systems in the presence of inaccurate clock synchronizations

This article deals with testing distributed real-time systems. More precisely, we propose: (1) a model for describing the specification of the implementation under test, (2) a distributed architecture of the test system (TS), (3) an approach for coordinating the testers which constitute the TS, and (4) a procedure for deriving automatically the test sequence of each tester from a global test sequence. In comparison with a very recent work, the proposed test method has the following important advantage: the clocks used by the different testers are not assumed perfectly synchronized. Rather, we assume more realistically that each clock is synchronized with a reference clock with a given (nonnull) inaccuracy. This advantage is very relevant if, for example, the testers communicate through the Internet.     

Testing in context: framework and test derivation

The paper addresses the problem of testing a component embedded within a given modular system. A context of the component represents the rest of the system and serves as its operational or testing environment. A framework for testing in context is presented based on the model of a system of communicating finite state machines. In particular, the problems of test executability and fault propagation in the presence of the context are identified and discussed. The proposed solution to these problems consists in computing so-called approximation of the specification in context, i.e. the FSM model of the component's properties that can be controlled and observed through the context. The approximation assures executability of tests and fault propagation through the context and serves as a base for test derivation. A conformance relation used for test derivation is shown to be the reduction relation between an implementation and the approximation of the given specification. This relation requires that the implementation produces a (sub)set of output sequences that can be produced by its specification in response to every input sequence. An approach to test generation for the reduction relation and deterministic implementations is also presented.     

Architecture-based testing of service-oriented applications in distributed systems

ContextTesting distributed service-oriented applications (SOAs) is more challenging than testing monolithic applications since these applications have complex interactions between participant services. Test engineers can observe test results only through a front service that handles request messages sent by test engineers. Message exchanges between participant services are hidden behind the front service and cannot be easily observed or controlled through the front service. For this reason, testing SOAs suffer from limited observability and controllability problem.ObjectiveThis paper proposes a new test method that is architecture-based and exploits interaction architecture of a SOA. The proposed test method alleviates the limited observability and controllability problem by employing test architecture, thereby facilitating test execution and analysis through monitoring and controlling message exchanges.MethodOur proposed method derives an interaction architecture from the specification of a SOA. Test architectures can be designed from the derived interaction architecture by extending it with additional test elements. At the same time, architecture-neutral test scenarios are automatically generated from the test model that is constructed from the specification. Our method combines test architecture information with the test scenarios to obtain architecture-enabled test scenarios under the selected test architectures. Finally, architecture-enabled test execution and analysis are conducted in the real network environment.ResultsThe efficacy of the proposed method is demonstrated with an industrial case study, which shows that it is practical and effective for testing SOAs. Even though our method increases an additional test generation effort owing to test architecture, it is counterbalanced by higher fault detection rate and faster fault locating time.ConclusionThe main benefit of our approach is that using test architecture it enhances testability of SOA by increasing observability and controllability through monitoring and controlling message exchanges. Our architecture-based test method enables test engineers to detect faults efficiently and also reduce fault locating time significantly.