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.     

Constructing checking sequences for distributed testing

The objective of testing is to determine whether an implementation under test conforms to its specification. In distributed test architectures involving multiple remote testers, this objective can be complicated by the fact that testers may encounter coordination problems relating to controllability (synchronization) and observability during the application of tests. Based on a finite state machine (FSM) specification of the externally observable behaviour of a distributed system and a distinguishing sequence, this paper proposes a method for constructing a checking sequence where there is no potential controllability or observability problems, and where the use of external coordination message exchanges among testers is minimized. The proposed method does not assume a reliable reset feature in the implementations of the given FSM to be tested by the resulting checking sequence. phone: 613-562-5800(Extn)6684 Received May 2004 Revised March 2005 Accepted April 2005 by J. Derrick, M. Harman and R. M. Herons     

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.     

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.     

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 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.     

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.     

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

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

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.     

Graph-based determination of structural controllability and observability for pressure and temperature dynamics during steam-assisted gravity drainage operation

Steam assisted gravity drainage (SAGD), which is used for the in-situ extraction and recovery of oil sands bitumen, is represented by a distributed parameter system (DPS). The problem of sensor placement and the control of steam chamber growth and oil production, respectively, require analysis of the observability and controllability of the system. In this type of system, parametric sensitivity is traditionally used in lieu of observability, and controllability has not been explored rigorously. In this work, we analyze the pressure and temperature fields of a SAGD model based on detailed reservoir simulations and present a data-driven technique to assess the structural controllability and observability of the system, with a view to determine optimal locations of actuators and sensors. An agglomerative hierarchical clustering technique is used to obtain a spanning tree of the clusters which is partitioned based on an objective function to arrive at a set of spatially contiguous clusters that display similar pressure/temperature dynamics. A Granger causality measure is used to create the linkage amongst the clusters to build a digraph model of the data. The driver nodes of the graph identify locations for actuation which provide full control over the graph, and the root strongly connected components indicate sensor locations which ensure structural observability over the entire graph. We demonstrate the method using data generated from SAGD simulations using the CMG-STARS simulator, identify the sensor and actuator locations required for complete structural observability and controllability of the system, and also provide a method of assessment of partial actuation and in-sensor ranges.     

Controllability and observability of multi-agent systems with heterogeneous and switching topologies

ABSTRACT

This paper focuses on controllability and observability of multi-agent systems with heterogeneous and switching topologies, where the first- and the second-order information interaction topologies are different and switching. First, based on the controllable state set, a controllability criterion is obtained in terms of the controllability matrix corresponding to the switching sequence. Next, by virtue of the subspace sequence, two necessary and sufficient algebraic conditions are established for controllability in terms of the system matrices corresponding to all the possible topologies. Furthermore, controllability is considered from the graphic perspective. It is proved that the system is controllable if the union graph of all the possible topologies is controllable. With respect to observability, two sufficient and necessary conditions are derived by taking advantage of the system matrices and the corresponding invariant subspace, respectively. Finally, some simulation examples are worked out to illustrate the theoretical results.     

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.     

Structure analysis via orthogonal functions

The use of orthogonal functions to analyse the structure of a system is investigated. Applying the definitions of observability and controllability to a system that is approximated with the help of orthogonal functions, it is shown that the concepts of the state space and the space of orthogonal functions are equivalent, provided that two weak conditions are met. This result ensures that the observability and controllability properties remain invariant under the transformation introduced by the approximation. Furthermore, new criteria to test observability and controllability are given in terms of the coefficient matrix of the orthogonal expansion. Because this test does not require the knowledge of the system matrices A, B and C, the results derived may be used for the identification of systems. It is demonstrated that all the results obtained remain true, even for an approximation with low accuracy. These properties allow the application of orthogonal functions for the analysis of systems     

Supervisory control of timed discrete event systems under partial observation based on activity models and eligible time bounds

To avoid the state–space explosion by including tick events in timed discrete event systems (DESs) under partial observation, a notion of eligible time bounds is introduced and based on the notion, controllability and observability conditions of languages are presented. In particular, this paper shows that these controllability and observability conditions are necessary and sufficient for the existence of a supervisor to achieve the given language specification.     

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

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

Structure simplification of dynamic process models

Lumped process models derived from first engineering principles are usually too detailed for control purposes where only the major dynamic characteristics of the system should be captured. Two common steps of simplifying dynamic process models, the steady-state variable removal and the variable lumping simplification steps are investigated in this paper, in order to show if they preserve the key properties: the structural controllability, observability and stability of the models. In order to enable the formal analysis, these simplification steps are represented as context sensitive graph transformations acting on the structure graphs of the dynamic process models. It is shown that the simplification transformations above preserve the structural controllability and observability of process models. But only the steady-state variable removal transformation has been found not to destroy their structural stability. The variable lumping structure simplification transformation is further specialized to the case of cascade process models. It is shown that the inverse of this transformation does exist in this case, and both transformations preserve structural controllability and observability.     

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.     

Testability of software components

The concept of domain testability of software is defined by applying the concepts of observability and controllability to software. It is shown that a domain-testable program does not exhibit any input-output inconsistencies and supports small test sets in which test outputs are easily understood. Metrics that can be used to assess the level of effort required in order to modify a program so that it is domain-testable are discussed. Assessing testability from program specifications and an experiment which shows that it takes less time to build and test a program developed from a domain-testable specification than a similar program developed from a nondomain-testable specification are also discussed     

Exact boundary controllability results for a Rao–Nakra sandwich beam

The Rao–Nakra model of a three layer sandwich beam is analyzed for exact boundary controllability. The damped and undamped cases are considered. The multiplier method is used to obtain required observability inequalities that imply controllability. It is shown that if the control time T is large enough, under certain other parametric restrictions, the system is exactly controllable.     

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.