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     

On stochastic observability and controllability

New definitions of stochastic observability, detectability, controllability and reachability are proposed. For both continuous and discrete time linear systems easily verifiable necessary and sufficient conditions are obtained, which are compatible with the usual ones for the corresponding (degenerate) deterministic systems. Furthermore, for stochastically observable, linear systems explicit expressions for the LUMCE of the state at time $\text{t≧0}$, with no information of the initial state, are obtained.     

Dynamic generalized controllability and observability functions with applications to model reduction and sensor deployment

In this paper we introduce the notion of Dynamic Generalized Controllability and Observability functions for nonlinear systems. These functions are called dynamic and generalized since they make use of additional states (dynamic extension) and are such that partial differential inequalities are solved in place of equations. The presence of the dynamic extension permits the construction of classes of canonical controllability and observability functions without relying on the solution of any partial differential equation or inequality. The effectiveness of the proposed concept is validated by means of two applications: the model reduction problem via balancing and the sensor deployment problem in a continuous stirred tank reactor (CSTR).     

Controllability and observability of switched multi-agent systems

This paper considers controllability and observability of switched multi-agent systems, which are composed of continuous-time and discrete-time subsystems. First, a controllability criterion is established in terms of the system matrices. Then, by virtue of the concepts of the invariant subspace and the controllable state set, a method is proposed to construct the switching sequence to ensure controllability of switched multi-agent systems, and a necessary and sufficient condition is obtained for controllability. Moreover, a necessary controllability condition is derived in terms of eigenvectors of the Laplican matrix. With respect to observability, two necessary and sufficient algebraic conditions are obtained. Finally, simulation examples are provided to illustrate the theoretical results.     

分布事务服务的一致性测试

作为J2EE应用服务器重要组成部分的分布事务管理器主要用于提供分布环境下的事务处理能力。文章拓宽了协议一致性测试的理论和技术的应用范围,探讨了分布事务服务的一致性测试,也给出了分布事务服务的形式化描述和非基于经验的测试序列的生成方案。     

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.     

State and input observability for structured linear systems: A graph-theoretic approach

This paper deals with the state and input observability analysis for structured linear systems with unknown inputs. The proposed method is based on a graph-theoretic approach and assumes only the knowledge of the system's structure. Using a particular decomposition of the systems into two subsystems, we express, in simple graphic terms, necessary and sufficient conditions for the generic state and input observability. These conditions are easy to check because they are based on comparison of integers and on finding particular subgraphs in a digraph. Therefore, our approach is suited to study large-scale systems.     

Evolutionary generation of unique input/output sequences for class behavioral testing

Object-oriented software is composed of classes. Their behaviors are usually modeled with state diagrams or finite state machines (FSMs). Testing classes is regarded as testing FSMs in which unique input/output (UIO) sequences are widely applied. The generation of UIO sequences is shown to be an undecidable problem. For these problems, genetic algorithms (GAs) may offer much promise. This paper reports some primary results of on-going research on evolutionary testing classes. First, we explain how to define UIO sequence generation as a search problem, and then describe adapting genetic algorithms to generating UIO sequences. Special issues of using genetic algorithms such as solution representation, validity checking and fitness definition are discussed in detail. Primary experiments confirm the applicability and feasibility of applying GAs to UIO sequence generation.     

Conformance testing for real-time systems

We propose a new framework for black-box conformance testing of real-time systems. The framework is based on the model of partially-observable, non-deterministic timed automata. We argue that partial observability and non-determinism are essential features for ease of modeling, expressiveness and implementability. The framework allows the user to define, through appropriate modeling, assumptions on the environment of the system under test (SUT) as well as on the interface between the tester and the SUT. We consider two types of tests: analog-clock tests and digital-clock tests. Our algorithm for generating analog-clock tests is based on an on-the-fly determinization of the specification automaton during the execution of the test, which in turn relies on reachability computations. The latter can sometimes be costly, thus problematic, since the tester must quickly react to the actions of the system under test. Therefore, we provide techniques which allow analog-clock testers to be represented as deterministic timed automata, thus minimizing the reaction time to a simple state jump. We also provide algorithms for static or on-the-fly generation of digital-clock tests. These tests measure time only with finite-precision digital clocks, another essential condition for implementability. We also propose a technique for location, edge and state coverage of the specification, by reducing the problem to covering a symbolic reachability graph. This avoids having to generate too many tests. We report on a prototype tool called and two case studies: a lighting device and the Bounded Retransmission Protocol. Experimental results obtained by applying on the Bounded Retransmission Protocol show that only a few tests suffice to cover thousands of reachable symbolic states in the specification.     

Some problems of computer-aided testing and “interview-like tests”

Computer-based testing – is an effective teacher’s tool, intended to optimize course goals and assessment techniques in a comparatively short time. However, this is accomplished only if we deal with high-quality tests. It is strange, but despite the 100-year history of Testing Theory (see, Anastasi, A., Urbina, S. (1997). Psychological testing. Upper Saddle River, NJ: Prentice-Hall) there still exist some misconceptions. Modern wide-spread systems for computer based course management and testing reveal a set of problems corresponding to certain features of testing methods.     

Exhaustive analysis and simulation for distributed systems,both sides of the same coin

This paper presents exhaustive analysis and simulation for distributed systems validation. Exhaustive analysis makes possible to detect quickly several types of errors, for instance, unspecified reception of signals, errors in timer management, deadlock, errors in precedence, etc. But, in general, exhaustive analysis can only be applied to a simplified model of the distributed system due to the state explosion problem. On the other hand, simulation permits accurate tests and confronts the distributed system to complex situations. We think both forms of validation are complementary. Validation was done on systems specified in the SDL language, using OVAL, a tool for specification validation developed at CNET, Paris A. This tool allows exhaustive analysis and simulation of SDL specified systems. We illustrate our results with several examples. Ana R. Cavalli received the Doctorat d'Etat ès Sciences Mathematiques in 1984, from the University of Paris VII, France. From 1975 to 1981 she was associate professor in the Computer Science Department, at the Universidad Central de Venezuela, Caracas. In 1981, she joined the Laboratoire d'Informatique Theorique et Programmation of the C.N.R.S., Paris, where she worked on automatic proofs methods for temperal logics and their applications to the specification and verification of protocols. She is now involved in the Concurrency Communication and Cooperation Project. (C.N.R.S.). In 1985, she joined the Department of Langages et Systèmes de Commutation, at the CNET (Centre National d'Etudes des Telecommunications), Paris, where she works on software engineering and formal specification techniques. His research interests are in formal specification techniques.and verification of distributed systems, including logics and models for parallel systems. Etienne Paul received the ingenieer degree in 1974, from the Ecole Polytechnique, France, and the telecommunications ingenieer degree in 1976 from the Ecole Nationale Superieure des Telecommunications, France. He joined the Department of Langages et Systèmes de Commutation, at the CNET (Centre National d'Etudes des Telecommunications), in 1977. From 1977 to 1981, he worked on the development of telecommunications systems, and since 1982, on software engineering and formal specification techniques. His first interest in formal specification techniques has been in the field of algebraic data types and logic programming. Now he is mainly working on SDL language and is responsible for the OVAL project. During the RACE definition phase, he has also worked on the SPECS project.