OVERVIEW OF PROJECTS 

Groupe de recherche en téléinformatique - Université de Montréal 

(September 1993)

Protocol testing

Test coverage

    The objective is to develop criteria and  methods for analysing the test coverage of a given test suite and to  provide additional test cases in order to complement the existing  coverage. Initial work resulted in the experimental tool TESTL which provides this functionality for the case that the specification is given in the form of a finite state machine (MSc project by M. Dubuc, 1991).
    Test coverage tool considering data flow: The aim of this project is to improve the facilities of the TESTL tool for the evaluation of test coverage. While TESTL is limited to the FSM aspect of specifications, this new tool, called TSE, considers the interaction parameters and internal state variables, covering therefore the major aspects of protocol specifications written in Pascal, Estelle or SDL (MSc project by C. Caouette, 1993; collaboration with Prof. Ural from Ottawa University). 
    In order to use the TESTL tool for the analysis of existing protocol conformance test suites written in TTCN, we have developed a TTCN test case analyser which adapts the definition of the test cases into the format accepted by TESTL (MSc project by Y. Djerbib). These tools have been integrated with the IDACOM Protocol Tester (MSc project by P. Salvail, 1993) and an experiment with a full-scale OSI conformance test suite, namely the ISDN packet level protocol has been made (summer project by Alexandre Guimond, 1993).

Test result analysis and diagnostics

    A tool has been developed, TETRA (MSc projects by O. Bellal and F. Saba), to check the results of a test sequence against the formal specification (written in LOTOS and supposed to be correct) of the protocol which is being tested.  The results of the tests are checked against the specification and diagnostic messages are produced indicating a possible reason for the failure.  The tool has been used for the validation of the verdicts of the standardized LAP-B conformance test cases, and for the validation of a simplified Transport protocol in respect to the ISO Transport service written in LOTOS. It has also been combined with a locally developed ASN.1 coding and decoding tool and used for an experiment for on-line testing of the ACSE protocol (OSI application layer).
    A similar function is also provided by the TESTL and TSE tools mentioned above, however in reference to Estelle specifications. Another project (MSc by A. Ezust) aims at building efficient test result analysis programs for a given Estelle specification. 
    In the context of his PhD work, A. Ghedamsi has developed methods for fault diagnostics of finite state machine implementations. Single and multiple fault assumptions are supported in the case that the system specification is given in the form of a single or multiple FSM modules, possibly non-deterministic. A tool providing such diagnostics has been implemented and tried with the ISDN packet level protocol. 

Test suite development and TTCN support

    A test suite is a set of test cases which are designed to perform a thorough test of an implementation under test (IUT).  Our main attention is in the area of protocol conformance testing, where a protocol implementation (IUT) is checked against the protocol specification.  In this context, the development of a test suite is usually based on the protocol specification.  Various test suite development methods have been designed for the case that the reference specification is given in the form of a finite state machine (FSM).  The first method combining such methods with data flow analysis, known from software engineering, was proposed by Sarikaya and Bochmann in 1984.  Prof. Sarikaya has continued the development of this combined method at Concordia University and at the University of Montreal (during 1990-91) by applying it for specifications written in Estelle and LOTOS. Tools have been built for the semi-automatic development of a test suite from a given Estelle specification. Support for the test specification language TTCN has also been developed. 
    More recently, the group has work on the validation of the verdicts of a given test suite in respect to the protocol specification written in LOTOS or Estelle (using the tools TETRA or TESTL, respectively). In addition, much work has been done to improve the FSM test suite development methods and extend them to partially defined and non-deterministic FSM specifications (work by Fujiwara, Luo, Petrenko, and students Yao, Liu). Emphasis has been put on a precise fault model, conformance relations and a full fault coverage by the derived test suite. 

 Software specifications

Formal description techniques for OSI and ISDN protocols and services:   Tools and Experiences.

    This group of projects is related to the formal description techniques (Estelle, Lotos and SDL) and ASN.1 (Abstract Syntax Notation 1) which are designed by the ISO and CCITT standardization communities to describe standardized  protocols.  Over the years, students and researchers from the group have developed related tools, and acquired experience with using these and other tools from various groups.
The group has developed the very first Estelle compiler in 1983, when Estelle was under study. This compiler accepts Estelle first DP (Draft Proposal) and translates it to Pascal.  As a basis for comparison between manually written protocol implementation and semi-automatically generated code from formal specification, a Transport Protocol and a Session Protocols implementations have been developed.  Various other implementations have also been developed, such as an ISO-IP gateway, a Transport Relay ISO-DARPA (TCP-TP), Interactive Transport user for TP and TCP, Teletex protocol, FTAM server and user programs, and others.
    More recently, ASN.1 tools has been developed in the group with the objective to integrate ASN.1 (as a data type specification language also specifying data encoding rules) into the Estelle and Lotos languages.  ASN.1 compilers have been designed to translate ASN.1 types into Estelle and Lotos data types.  A set of tools for each translation facilitates the integration of automatically generated encoding and decoding routines.  With the ASN.1-Estelle set of tools (includes ASN.1 and Estelle compilers), a semiautomatically generated implementation can be obtained easily. 
    Present work includes a translator from SDL to Estelle (MSc project by A. Thiboutot), and the inclusion of performance and real-time aspects in LOTOS (PhD project by N. Rico).

 Telecommunications software specification and evolution

    Under funding from CITR during 1990-93, a general framework, independent of any particular specification language, has been defined for considering formal relationships that correspond to different forms of refinement and specialization . Based on this framework, the step-wise refinement and specialization has been studied for the specification languages Estelle. In addition, results were obtained for the reuse of specifications and the automatic derivation of a new specification which is an extension of two separate existing specifications (PhD project by F.Khendek). This derivation particularly useful in the context of communication service specifications where several "features" are first described separately, and their "interactions", also called feature interaction, have to be analysed in order to design a system which provides several features simulataneously. 
    Software evolution was investigated in the context of object-oriented reflective programming systems. This research provides a general framework in which appropriate constraints can be defined which govern the changes that are acceptable during system evolution, and ensure that the system remains in a stable operating condition. A mechanism allows the controlled evolution of system specifications and implementations by gradually changing selected parts of the system, while all other parts of the system continue their normal operations (PhD project by M.Erradi, 1993).
    Exhaustive validation of complex specifications is very difficult. The research concentrated on systematic testing of executable specifications. This approach was applied to an object-oriented specification of the Personal Communication Service (PCS, MSc project by D.Desbiens, 1992) and an extension which describes the interworking between different PCS networks (MSc project by J.Dargham, 1993).

 Design for testability

    Also funded by CITR, different approaches to deriving easily  testable specifications and software components have been studied. In order to handle more complex system structures,  a general design framework for testable and highly available communications systems has  been defined .  Furthermore a new testability metric has been defined.  It is based  on the intuitive observation that the length of a test suite which guarantees full fault  coverage could be a measure for a significant part of the cost of testing.  This metric was  applied to the evaluation of the modular protocol structures which are modelled by a  composition of FSMs .
    Testability and test suite design issues were considered for the example of the XTP protocol. Test cases were selected for a large part of XTP that does not involve timing considerations. We have used the TESTL tool to generate test cases for the context management. All test cases are written in TTCN. Scenario test cases are also given in order to cover the interactions between  XTP functions. 
The use of an object-oriented approach is much favored for the design and implementation  of distributed systems.  We have studied the problem of testability in the context of  object-oriented systems where only certain objects are directly visible for testing  purposes (MSc project by Htite, 1993) .  An instrumentation methodology was also introduced to render an  object-oriented system more testable . 
Object-oriented design methodologies
    During 1988-91, the group had a major involvement in a CRIM-BNR project on object-oriented design methodology. The aim of this project was the development of an object-oriented design methodology and specification language to support the development of distributed applications in the networking area. The main results were the definition of a specification language, called Mondel, associated tools for the validation and simulation of specifications, and trial applications to various example systems. The group was also involved in a CRIM-DMR project on the architectural modelling of distributed applications and work organization (1991-93), which was part of the DMR "Macroscope" project. 
    Presently, the group has a leading role in the IGLOO project on object-oriented design methodologies, specification reuse, associated tools and applications in the area of distributed systems management. The project is organized by CRIM in collaboration with three universities and 6 industrial partners. 

Distributed algorithms and applications

Distributed systems management 

    In the context of the IGLOO project, the group works on network management issues,  such as alarm analysis, distributed testing and fault diagnostics, and configuration management. Another project is related to the management of messaging systems.
Quality of service negociation for multimedia applications
    For high-speed multimedia applications, the requirements on the underlying transport service are much more severe than in traditional applications because of the synchronous nature of voice and video presentations. The performance parameters of the transport service are characterized by the so-called quality of service (QoS) parameters. The objective of this research, which  is funded in the context of a new CITR Major Project on "Broadband Services", is to investigate the impact of dynamically changing QoS on the design of applications. We aim at developing a methodology permitting to design multimedia applications that can dynamically adapt to QoS variations and also be easily adapted to evolving communication protocol standards (PhD student A.Hafid and post-doctoral researcher A.Vogel). A second objective is the identification of the typical application requirements concerning multimedia database access functions. 

 Development of distributed algorithms

    (a) Distributed implementation of LOTOS specifications: The main difficulty is the distributed implementation of the LOTOS multiple rendezvous interactions. Our work is based on a LOTOS interpretor developed at the University of Ottawa, implemented in Prolog, which runs on a single machine. A distributed rendezvous algorithm was defined and implemented (PhD project by Q.Gao), as well as a distributed execution scheme using separate Lotos interpretors executing different parts of the specification (PhD project by C. Wu, 1993).
    (b) Distributed controllers for real-time applications:  We consider the problem of automatically developping set of distributed components (controllers) such that a number of given components (components to be controlled) satisfy a given overall service requirement. So far, a method has been developed (PhD project by C. Antonescu, 1993) for the automatic derivation of a distributed algorithm from a given global service specification and has been applied to certain examples (MSc project by M. Levy, 1992). A particular application area is communication gateways (PhD project by Z.Tao). From our studies in the derivation of distributed controllers, we have identified certain problems which are inherent to the distribution of the control.  Different solutions to these problems are investigated, as well as the consideration of the real-time aspects of the system requirements (post-doctoral researcher A. Khoumsi). This work is funded by a BNR-FCAR-NSERC grant.

 Network control algorithms

    Various algorithms related to congestion control, traffic management and routing are being investigated. Application to ATM networks are foreseen.  In particular we are investigating various classes of distributed network algorithms where the cost of passing messages during the execution of the algorithm is also taken into account in its design.  We are also studying design and implementation issues related to the addition of intelligent network services in the interconnection of heterogeneous high speed networks.