OVERVIEW OF PROJECTS
Groupe de recherche en téléinformatique - Université de
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.
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
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
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
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
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