Selected Publications by Gregor v. Bochmann and his research group (before 2000)

Distributed Systems Research Group, EECS, University of Ottawa (and before 1998: "Groupe de Recherche en Téléinformatique", Université de Montréal )

The selected publications are classified into the following fields:

• Quality of service management
• for presentational applications - e.g. electronic commerce
• for conversational and multi-casting applications
• Modeling of distributed systems 
• object-oriented modeling
• formal description techniques for communication protocols and services
• validation / verification
• Distributed systems and network management (click here)
• Test development from given specifications: methods and tools
• general aspects and protocol conformance testing
• based on finite state machine (FSM) models
• based on models of labeled transition systems (LTS)
• based on models with interaction parameters
• diagnostic testing
• testing embedded system components
• Automating the design of distributed systems
• deriving protocols from service specifications
• deriving communication gateways
• deriving submodules for real-time process control applications
• ... other formal transformations
  

Quality of service management - for presentational applications (e.g. electronic commerce)

Some principles for quality of service management

• Authors: G.v. Bochmann and A. Hafid
• Reference: [Boch 97b] Distributed Systems Engineering Journal 4 (1997), pp. 16-27.
• Abstract:
• For a copy click here: PDF

An Approach to QoS Management in Distributed MM Applications: Design and an Implementation

• Authors: A. Hafid and G.v. Bochmann
• Reference: [Hafi 99a] Journal on Multimedia Tools and Applications (to appear)
• Abstract: Most work related to quality of service (QOS) is concerned with individual system components, such as the operating system or the network. Howevec, to support multimedia applications, the entire distributed system must participate in providing the guaranteed performance levels. In recognition of this, a number of QoS architectures have been proposed to provide QoS guarantees. The mechanisms and schemes proposed by those architectures are used in a rather static manner since the involved entities, e.g. the network, sender and receiver, are known before the connection (call) set-up phase. In contrast to those architectures, we propose a general QoS management framework which supports the dynamic choice of a configuration of system components to support the QoS requirements for the user of a specific application. We consider different possible system configurations and select the most appropriate on depending on the desired QoS and the available resources. In this paper we present an overview of this general framework; especially, we concentrate on QoS negotication and adaptation mechanisms. To show the feasability of this approach, we designed and implemented a QoS manager for distributed multimedia presentational applications, such as news-on-demand. The negotiation and adaptation mechanisms which are supported by the QoS manager are specializations of the general framework. The proposed framework allows to improve the utilization of system resources, and thus to increase the system availability; it also allows to recover automatically, if this is possible, from QoS degradations. Furthermore, it provides the flexibility to incorporate different resource reservation schemes and scheduling policies, and to accomodate new system component technologies.
• For a copy click here: PDF

Distributed multimedia applications and quality of service: a review

• Authors: A. Hafid, G.v. Bochmann and R. Dssouli
• Reference: [Hafi 98a] Electronic Journal on Network and Distributed Processing, No. 6 (Febr. 1998), pp. 1-50.
• Abstract: Distributed multimedia (MM) applications are very sensitive to the quality of service (QoS) provided by their computing and communication environment. This paper surveys the QoS issues behind distributed MM applications. MM applications characteristics and requirements are identified; QoS notions are defined. The role of all system components, namely transport protocols, networks, operating systems, file servers, multimedia databases, and user interfaces, in the provisioning of QoS is described. The need for QoS management to support distributed MM applications is motivated. The different QoS management functions are defined and examples of realizations are presented. Finally some representative QoS architectures are presented, their limitations are identified, and the requirements of an "ideal QoS architecture" are presented. Keywords: distributed multimedia applications, quality of service, quality of service management, quality of service architectures
• For a copy click here: PDF

Quality of Service Negotiation with Present and Future Reservations: A detailed Study

• Authors: A. Hafid, G.v. Bochmann and R. Dssouli
• Reference: [Hafi 98b] Computer Networks and ISDN Systems, volume 30, issue 8, 1998
• Abstract: Distributed multimedia (MM) applications such as video-on-demand and teleconferencing provide services with different quality of service (QoS) requirements. Hence, the user should be able to negotiate the desired QoS depending on his/her needs, the end-system characteristics and his/her financial capacity. In response to the user service request with a desired QoS, most QoS negotiation approaches return an acceptance or a simple rejection of the request. More specifically, they provide the user only with the QoS that can be supported at the time the request is made and assume that the service is requested for indefinite duration. The paper describes work on a new QoS negotiation approach with future reservations (NAFUR) that decouples the starting time of the service from the time the service request is made and requires that the duration of the requested service must be specified. NAFUR allows to compute the QoS that can be supported for the time the service request is made, and at certain later times carefully chosen. As an example, if the requested QoS cannot be supported for the time the service request is made, the proposed approach allows to compute the earliest time, when the user can start the service with the desired QoS. NAFUR will help to increase (a) the flexibility of the system by providing the user with more choices, and (b) the system resource utilization, and the availability of the system, by encouraging the sharing of the resources, e.g. multicast for video-on-demand systems. Furthermore, it provides the flexibility to incorporate (a) a range of resource reservation schemes and scheduling policies, and (b) a range of new system component technologies.
• For a copy click here: PDF

Quality of service adaptation in distributed multimedia applications

• Authors: A. Hafid and G.v. Bochmann
• Reference: [Hafi 98c] Multimedia Systems Journal (ACM), Vol. 6, No. 5 (1998), pp. 299-315.
• Abstract: High-speed networks and powerful end-systems enable new types of applications, such as video-on-demand and teleconferencing. Such applications are very demanding on quality of service (QoS) because of the isochronous nature of media they are using. To support these applications, QoS guarantees are required. However, even with service guarantees, violations may occur because of resources shortage, e.g., network congestion. In this paper we propose a new adaptation approach which allows to recover automatically, if possible, from QoS violations (1) by identifying a new configuration of system components which might support the initially agreed QoS and by performing a user-transparent transition from the original configuration to the new one, (2) by redistributing the levels of QoS that should be supported, in the future, by the components, or (3) by redistributing the levels of QoS that should be supported immediately to meet end-to-end requirements based on the principle that (local) QoS violation at one component may be recovered immediately by the other components participating in the support of the requested service. The proposed approach, together with suitable negotiation mechanisms, allows (1) to reduce the probability of QoS violations which may be noticed by the user, and thus, to increase the user confidence in the service provider, and (2) to make optimal utilization of the system resources, and thus to increase the system availability. Keywords: quality of service, adaptation, violation, recovery
• For a copy click here: PDF

Distributed multimedia applications and quality of service: A survey

• Authors: A. Vogel, B. Kerherve, G.v. Bochmann and J. Gecsei
• Reference: [Voge 95a] IEEE Multimedia, Vol. 2, No. 2 (ISSN 1070-986X), Summer 1995, p.10-19. A reduced version was published in Proc. CASCON (IBM Toronto), Oct. 1994
• Abstract:
• For a copy: PDF

Enabling technology for distributed multimedia applications

• Authors: J.W. Wong, K.A. Lyons, D. Evans, R.J.Velthuys, G.v. Bochmann, A. Hafid, et al.
• Reference: [Wong 97a] IBM Systems Journal, Vol. 36 No. 4 (1997), pp. 489-507.
• Abstract: This paper summarizes the results of the CITR Broadband Services major project. The goal of this major project is to investigate the software technologies required for the development of distributed multimedia applications. Of particular interest are "presentational" applications where multimedia documents, stored in database servers, are retrieved by remote users over a broadband network. Emphasis is placed on efficiency and service flexibility. By efficiency, we mean the ability to support many users and many multimedia documents. As to service flexibility, we mean the application is able to support a range of quality of service requirements from the users, adapt to changing network conditions, and support many types of multimedia document. The research program consists of six constituent projects: multimedia data management, distributed multimedia file service, quality of service negotiation and adaptation, scalable video encoding, synchronization of multimedia data, and project integration. These projects are investigated by a multi-disciplinary team from eight institutions across Canada. A multimedia news application has been defined and the results from the various projects have been integrated into a multimedia news prototype. In this paper, the system architecture, research results, as well as the prototyping effort, are discussed.
• For a copy click here: PDF

Architectural design of adaptive multimedia systems

• Authors: G.v. Bochmann, B. Kerherve, A. Hafid, P. Dini and A. Pons
• Reference: [Boch 96a] proceedings of IEEE Workshop on Multimedia Software Development, Berlin, Germany, March 25-26, 1996
• Abstract:
• For a copy click here: PDF

A quality of service negotiation procedure for distributed multimedia presentational applications

• Authors: A. Hafid, G.v. Bochmann and B. Kerhervé
• Reference: [Hafi 96g] in the proceedings of the Fifth International Symposium of High Performance of Distributed Processing (HPDC-5), Syracuse, New York, 1996, pp.330-339
• Abstract: *** this publication contains details on the user interface for QoS negotiation ***
• For a copy click here: PDF

Meta-data modelling for quality of service management in the World Wide Web

• Authors: E. Madja, A. Hafid, R. Dssouli, G.v. Bochmann and J. Gecsei
• Reference: [Madj 98a] in Proc. of Int. Conf. on Multimedia Modeling, Lausanne, Switzerland, 1998
• Abstract:
• For a copy click here: PDF

Cost models for distributed multimedia applications

• Authors: P. Dini, A. Hafid and G.v. Bochmann
• Reference: [Dini 96a] In the International Pacific Workshop on Distributed Multimedia Systems, Hong Kong University of Science and Technology (HKUST), June 25-28, 1996, pp. 238-245
• Abstract:
• For a copy click here: PDF (not available)

Service management issues in electronic commerce applications

• Authors: G. v. Bochmann, B. Kerhervé and M. Mohamed-Salem
• Reference: [Boch 99a] to be published as a chapter in a book
• Abstract: Quality of service issues have first been discussed in relation with the performance of communication networks. However, for understanding end-to-end performance of a distributed system, it is important to also consider the performance at the application level, of the different components of the distributed application, as well as the quality of service view of the user. Most work on quality of service management at the application level has been done for applications involving access to distributed multimedia databases, such as video-on-demand. The same QoS issues apply also to electronic commerce when users access a catalog which may include multimedia information in addition to the hard-core data elements, such as name and price of the product. In this paper, we identify various issues related to quality of service management for electronic commerce applications, and concentrate on one of these, namely the selection of a server from a pool of servers in order to optimize the overall cost-performance of the system and the user's satisfaction. The paper is organized as follows. Section 2 reviews QoS specification, its categories and dimensions in distributed systems. In section 3 we look at the QoS issues (QoS specification and provision) in the specific context of electronic commerce. Section 4 describes a scalable architecture for QoS management for the electronic commerce applications.
• For a copy click here: PDF

Quality of service management - for conversational and multi-casting applications

Cooperative quality of service management for multimedia applications

• Authors: S. Fischer, A. Hafid, G.v. Bochmann and H. de Meer
• Reference: [Fisc 97a] Proceedings of the 4th IEEE International Conference on Multimedia Computing and Systems, Ottawa, Canada, June 1997, pp. 303-310.
• Abstract: Quality of Service (QoS) management becomes more and more important, especially in networks where many applications are competing for a limited number of resources. As these applications become more complex (consider e.g. multiparty multimedia applications), the number of options for QoS management increases, leading to more complex decision processes. In this paper, we propose an approach for cooperative QoS management, where application-oriented QoS agents are distributed throughout the network and the end systems, communicating with each other. This distributed management system tries to guarantee the QoS level negotiated with the users, at the same time optimizing resource usage. The advantages of distributing the management process are (i) an easier and more precise localization of the cause of QoS problems, (ii) better knowledge of local situations, (iii) a lower complexity for a single QoS agent and (iv) an increase in possible actions. We describe management procedures for QoS negotiation, adaptation and renegotiation.
• For a copy click here: PDF

Quality of service management for teleteaching applications using the MPEG-4/DMIF

• Authors: G. v. Bochmann and Z. Yang
• Reference: [Boch 99b] to be presented at Intern. Workshop on Interactive Distr. Multimedia Systems and Telecom. Services, Toulouse, Oct. 1999.
• Abstract: In the context of distributed multimedia applications involving multicast to a large number of users, a single quality of service level may not be appropriate for all participants. It is necessary to distribute part of the QoS management process and allow each user process to make certain QoS decisions based on its local context. In order to allow for different QoS options, we assume that each source provides, for each logical multimedia stream, several different stream variants, representing different choices of user-level QoS parameters. The paper presents the design of a teleteaching system which uses this paradigm for QoS negotiation, and explains how the Delivery Multimedia Integration Framework (DMIF) of MPEG-4 can be adapted as a session protocol for such an application. In fact, it appears that this DMIF protocol, which is now being extended by ISO (DMIF Version 2) to the context of multicasting, provides some general session management functions which are quite useful for distributed multimedia applications using broadcasting.
• For a copy click here: PDF

Object-oriented modeling of distributed systems

Object-oriented design for distributed systems: The OSI directory example

• Authors: G.v. Bochmann, S. Poirier and P. Mondain-Monval
• Reference: [Boch 95f] Computer Networks and ISDN Systems 27 (1995) pp 571-590
• Abstract: For an object-oriented design methodology to be effective, it is important to provide methods and tools for validating the design specification before going into the implementation phase. The paper proposes a design methodology and a related object-oriented specification language which allows the validation of specifications through simulated execution, or through automatic exhaustive simulation for a certain subset of the language. The paper also discusses the relation of this design methodology and language to other design methodologies which are in wide use, such as the entity-relationship model for databases, the ASN.1 notation used for Open Systems Interconnection (OSI) communication protocols, as well as methodologies used in the standardization committees for the elaboration and description of various kinds of distributed systems standards. It is shown how these different approaches can be integrated into a single methodology and language, using the OSI Directory System as an example, which is explained in certain detail.
• For a copy click here: PDF

A framework for dynamic evolution of distributed systems

• Authors: M. Erradi, R. Dssouli and G.v. Bochmann
• Reference: [Erra 93a] Réseaux et Informatique Répartie, Vol. 3, No. 1 (1993), pp. 37-60
• Abstract: Recently, object-oriented specifications of distributed systems has gained more attention. The object-oriented approach is known by its flexibility for system construction. However, one of the major challenges is to provide facilities for the dynamic modifications of such specifications during the development and maintenance process. Yet, current work has not addressed the dynamic modifications of specifications of distributed systems. In this paper, we are concerned with formal description techniques that allow for the development and the dynamic modification of executable specifications. A two-level model for the evolution of large object-oriented specifications is introduced. The first level deals with the dynamic modification of types (classes), while the second level deals with the modification of modules. We have defined a set of structural and behavioral constraints to ensure the specification consistency after its modification at both levels. To allow for dynamic modification of types and modules, we have developed a reflective object-oriented specification language which uses meta-objects to support the modification operations. In this language, types and modules are objects.
• For a copy click here: PDF

The Macrotec toolset for CASE-based business modelling

• Authors: R. K. Keller, R. Lajoie, M. Ozkan, F. Saba, X.Shen, T. Tao and G. v. Bochmann
• Reference: [Kell 93] CASE'93, Singapore, July, 1993
• Abstract:
• For a copy click here: PDF

A pattern system for network management interfaces

• Authors: J. Tessier, R. K. Keller and G.v. Bochmann
• Reference: [Tess 98a] Communications of the ACM, 41 (9), pp. 86-93, 1998.
• Abstract:
• For a copy click here: PDF

Extending OMT for the Specification of Composite Objects

• Authors: D. Ramazani and G.v. Bochmann
• Reference: [Rama 96b] in Proc. 20th Intern. Conf. on Technology of Object-Oriented Languages and Systems (TOOLS-USA'96), August 1996.
• Abstract: In engineering and telecommunication applications, it is common to have composite objects. Existing object-oriented methods propose many approaches for modeling these objects. However, these approaches fail to capture the linkage between the structure and the behavior of composite objects. In [Ramazani 95a], a conceptual framework for the description of composite objects prescribes how this linkage can be established by means of a set of fundamental concepts. In order to make this framework more usable in practice, this paper shows how OMT can be adapted and extended to describe composite objects according to this framework. A great deal of these adaptations and extensions require only minor notational and semantic changes to the method. This work also shows how more requirements in connection with composite objects can be captured, made explicit, and precisely stated using an extended OMT.
• For a copy click here: PDF

Approaches to the specification of object associations

• Authors: D. Ramazani and G.v. Bochmann
• Reference: [Rama 97a] in Proc. IFIP Workshop on Formal Methods for Open Object-based Distributed Systems (FMOODS), Canterbury, UK, (H.Bowman, J. Derrick, eds.), Chapman-Hall, 1997, pp. 231-246.
• Abstract: Many practitioners agree on the key role of object associations during the requirements specification and analysis phases of application development, since they contribute to the definition of the semantics of applications. However, the literature shows that there are multiple semantics for associations, and confusion about how they should be represented. As a matter of fact, various interpretations of the concept of association exist, leading to a multiplicity of representations. The contribution of this paper is an exposition of four practical approaches to the formal specification of associations. It also introduces a conceptual model for associations which is used as a baseline for comparing the four approaches to formal specification of associations. These four approaches are based on different constructs of the specification language Object-Z which can be used for formally describing associations. The way these approaches capture the requirements represented by associations is central to selecting the approach to be used for the application development.
• For a copy click here: PDF

Distributed objects with sense of direction

• Authors: D. Ramazani, P. Flocchini and G.v. Bochmann
• Reference: [Rama 98a] in Proc. First Int. Workshop on Distributed Data and Structures, Orlando (US), March 30, 1998 (publ. by Carleton Scientific, 1999), pp. 1 - 12.
• Abstract: *** this paper is on naming issues in distributed systems ***
• For a copy click here: PDF

Formal description techniques for communication protocols and services

Protocol specification for OSI

• Authors: G.v. Bochmann
• Reference: [Boch 90g] Computer Networks and ISDN Systems 18 (April 1990), pp.167-184
• Abstract:
• For a copy: PDF

Specifications of a simplified Transport protocol using different formal description techniques

• Authors: G.v.Bochmann
• Reference: [Boch 90a] Computer Networks and ISDN Systems, Vol. 18, no.5, June 1990, pp. 335-377
• Abstract:
• For a copy: PDF

Formal methods for describing distributed systems: A discussion of the experience in OSI standardization

• Authors: G.v. Bochmann
• Reference: [Boch 89n] Decentralized Systems (Proc. IFIP WG 10.3 Working Conf. , Lyon, Dec. 1989), M.Cosnard, C.Girault (eds.), LNCS, North Holland Publ., 1990, pp. 29-39 (invited paper)
• Abstract:
• For a copy: PDF

ASN.1 and Estelle implementation support tools

• Authors: G.v. Bochmann, D. Ouimet and G. Neufeld
• Reference: [Boch 90t] Proc. Third Int. Conf. on Formal Description Techniques, IFIP (FORTE'90), Nov. 1990, Madrid, pp.531-534
• Abstract: Formal specifications are a well-known technique for improving software development. In the context of OSI communication protocol standards, Formal Description Techniques (FDT's) have been developed for the description of communication protocols and services. In addition, a notation called ASN.1 is used for the descriptions of the data structures of protocol data units exchanges between communicating entities at the application layer. Existing FDT's, such as Estelle, LOTOS and SDL, do not include facilities to directly manipulate data structures defined in ASN.1. This makes using FDT's for distributed applications difficult. This paper deals with the integration of ASN.1 with Estelle and the issues involved with the integration of corresponding implementation tools. It is shown how the encoding and decoding routines automatically generated from the ASN.1 definitions can be combined with implementation code semi-automatically generated from the Estelle specification of the protocol. An application for a simple protocol is given.
• For a copy click here: PDF

Prolog for industrial software development

• Authors: J. Vaucher, G. Bochmann, B. Lefebvre, S. Vella, M. Wu and K. Lee
• Reference: [Vauc 92] Proc. of The Practical Application of Prolog, Volume one, London, April 1992
• Abstract:
• For a copy: PDF

On the distributed implementation of LOTOS

• Authors: G.v. Bochmann, Q. Gao and C. Wu
• Reference: [Boch 89c] FORTE'89 (IFIP), Vancouver, in "Formal Descriptions Techniques II", North-Holland, S.T.Vuong editor,1989, pp.133-146
• Abstract: This paper presents an approach to the distributed implementation of multiple rendezvous, including dynamic process creation, as defined by the specification language LOTOS. The approach is based on a so-called activity tree which reflects the dynamic relationships between the active processes within the system, and a virtual ring algorithm for the distributed implementation of a set of rendezvous, which was originally developed for a static set of processes. A new dynamic ring establishment algorithm is presented which serves as a bridge between the activity tree and the virtual ring algorithm. When growing the activity tree, the algorithm establishes for each LOTOS gate a virtual ring over which the virtual ring algorithm is applied.
• For a copy click here: PDF

Fairness in LOTOS

• Authors: C. Wu and G.v. Bochmann
• Reference: [Wu 91] in the proceedings of the International Conference on Formal Description Techniques (FORTE'91), K.R. Parker and G.A. Rose eds, North-Holland, Sydney, Australia, 1991, pp.543-558
• Abstract: Fairness is an important concept related to specification languages which are based on concurrent and non-deterministic computation models; it is related to liveness. In this paper we formally introduce fairness to the LOTOS specification language by employing the standard LOTOS semantics together with a formalism which states restrictions on fair infinite execution sequences. We extend three fairness concepts of CSP, namely process, guard and channel fairness, to LOTOS. Certain features of LOTOS, such as the dynamic creation of processes, the dynamic relation between gates and processes, and related membership in multi-way rendezvous, not present in CSP, make the definition of fairness difficult. We introduce the concept of "transition groups", which leads to a general notion of fairness, and use LOTOS action indexes to define the concepts of process, alternative and channel for LOTOS. We explain how a fair execution model for LOTOS can be obtained, and demonstrate the use of these concepts by showing how fairness assumptions can be used to prove liveness properties for a given LOTOS specification.
• For a copy click here: PDF

Fairness of N-party synchronization and its implementation in a distributed environment

• Authors:C. Wu, G.v. Bochmann and M. Yao
• Reference: [Wu 93c] Proc. Int. Workshop on Distributed Algorithms (WDAG'93), LNCS 725, Springer Verlag, 1993, pp. 279-293
• Abstract: Fairness is an important concept in design and implementation of distributed systems. At the specification level, fairness usually serves as an assumption for proving liveness. At implementation level, the question becomes how to implement the underlying fairness which is assumed to be true at the specification level. In this paper, we study four types of fairness, the so-called w-fairness, s-fairness, u-fairness and su-fairness, in the context of the design of N-party synchronization algorithms. Within an abstract model for distributed systems, we formally introduce the four fairness concepts. We formally present, in the form of extended finite state machines, several distributed N-party synchronization algorithms which satisfy different fairness properties. The algorithms given in this paper are abstract in a sense that they are not optimized. The abstraction makes the construction of the algorithm and its proof of correctness easier.
• For a copy click here: PDF

Validation / verification of distributed systems

Validation of distributed algorithms and protocols

• Authors: Q. Gao, R. Groz, G.v. Bochmann, J. Dargham and E.H. Htite
• Reference: [Gao 95a] Proceedings of the1995 International Conference on Network Protocols (ICNP 95), pp.110-117
• Abstract: The use of formal description techniques allows the partial automation of the design, the validation, and the implementation of communication protocols and distributed algorithms. In this paper, we present our experiences of using the Estelle language, and a simulation and validation tool, called Veda, to simulate and validate complex distributed algorithms for the distributed implementation of multi-rendezvous. Some design errors in published distributed rendezvous algorithms were found. We obtain from these experiences heuristic guidelines for trouble shooting of distributed algorithms.
• For a copy click here: PDF

Reduced reachability analysis of communication protocols: A new approach

• Authors: J.R. Zhao and G.v. Bochmann
• Reference: [Zhao 86] Proc. IFIP Workshop on Protocol Specification, Testing and Verification, North-Holland Publ., 1986, pp. 234-254
• Abstract:
• For a copy: please look in the proceedings

Impact of Queued Interaction on Protocol Specification and Verification

• Authors: G.v. Bochmann and A. Finkel
• Reference: [Boch 88h] Proc. Intern. Symp. Interoperable Inf. Systems (ISIIS), Nov. 1988, Tokyo, pp. 371-382
• Abstract:
• For a copy: PDF

Distributed systems and network management

Conception et spécification par objets du contrôle centralisé d'un système de transmission

• Authors: M. Barbeau, P. de Saqui-Sannes and G.v. Bochmann
• Reference: [Barb 92a] Réseaux et informatique répartie, Vol. 2, no. 1 (1992), pp. 7-20
• Abstract:
• For a copy: PDF

Test development - general aspects and protocol conformance testing

Fault models in testing

• Authors: G.v. Bochmann, A. Das, R. Dssouli, M. Dubuc, A. Ghedamsi and G. Luo
• Reference: [Boch 91d] Proc. IFIP Intern. Workshop on Protocol Test Systems, Netherlands, Oct. 1991 (invited paper), pp. (II-17)-(II-32), published as a book by North Holland.
• Abstract:
• For a copy: please look in the proceedings

Trace analysis for conformance and arbitration testing

• Authors: G.v. Bochmann, R. Dssouli and J.R. Zhao
• Reference: [Boch 89m] IEEE Tr. on Soft. Eng., Vol.15, no.11, Nov. 1989, pp.1347-1356
• Abstract:
• For a copy: PDF

Test result analysis with respect to formal specifications

• Authors: G.v. Bochmann and O. Bellal
• Reference: [Boch 89j] Proc. 2-nd Int. Workshop on Protocol Test Systems, Berlin, Oct. 1989, pp.272-294
• Abstract: There are two aspects to testing: (1) the selection of appropriate test inputs and (2) the analysis of the observed interactions of the implementation under test (IUT) in order to determine whether they conform to the IUT's specification. The paper considers the second aspect with particular attention to the testing of OSI communication protocol implementations. A system is described which analyses an observed test trace of interactions with respect to a reference specification which is assumed to be written in LOTOS. In the case that an error is detected, the system also provides some diagnostic information for locating the "error" in the analyzed trace. The practical use of such a trace analysis system is discussed, as well as the possibility of using a similar approach for the validation of the verdicts which are included in the standardized OSI conformance test cases.
• For a copy click here: PDF

Test result analysis and validation of test verdicts

• Authors: G.v. Bochmann, D. Desbiens, M. Dubuc, D. Ouimet and F. Saba
• Reference: [Boch 90j] Proc. Workshop on Protocol Test Systems (IFIP),1990, North-Holland
• Abstract: Formal description techniques (FDT's) are useful in the protocol development cycle, particulary in the conformance testing area. In this paper, we present TETRA, a test and trace analysis tool based on the LOTOS FDT which can be used to automatically compare the specified verdicts of a conformance test case with a protocol specification, or to analyse results of a test run with the reference specification. We also describe our experience with this tool for the validation of a X.25 TTCN test suite and for the testing of an ACSE implementation.
• For a copy click here: PDF

Test development - based on finite state machine (FSM) models

Test selection based on finite state models

• Authors:S. Fujiwara, G.v. Bochmann, F. Khendek, M. Amalou and A. Ghedamsi
• Reference: [Fuji 91a] IEEE Transactions on Software Engineering, Vol.17, no.6, June 1991, pp. 591-603
• Abstract: The selection of appropriate test cases is an important issue for conformance testing of protocol implementations as well as in software engineering. A number of methods are known for the selection of a test suite based on the specification of the implementation under test, assumed to be given in the form of a finite state machine. This paper presents a new method which provides a logical link between several of the known methods. Called "partial W method", it has general applicability, full fault detection power, and yields shorter test suites than the W method. The second part of the paper discusses various other issues which have an impact on the selection of a suitable test suite. This includes the consideration of interaction parameters, various test architectures for protocol testing, and the fact that many specifications do not satisfy the assumptions made by most test selection methods, such as complete definition, a correctly implemented reset function, a limited number of states in the implementation, and determinism.
• For a copy click here: PDF

Selecting test sequences for partially-specified nondeterministic finite state machines

• Authors: G. Luo, A. Petrenko and G. v. Bochmann
• Reference: [Luo 94e] Proc. of the International Workshop on Protocol Test Systems (IWPTS'94), Tokyo, Japan, Nov. 1994, pp.95-110
• Abstract: In order to test the control portion of communication software, specifications are usually first abstracted to state machines, then test cases are generated from the resulting machines. The state machines obtained from the specification are often both partially-specified and nondeterministic. We come out with a method of generating test suites for the software that is modeled by partially-specified nondeterministic finite state machines (PNFSMs). On the basis of intuitive notions, a conformance relation, called quasi-equivalence, is introduced for such machines, which serves as a guide to test generation. Our method is also applicable to completely-specified deterministic machines, partially-specified deterministic machines, and completely-specified nondeterministic machines, which are typical classes of PNFSMs. When applied to such classes of
  machines, this method usually yields smaller test suites with full fault coverage for each class of machines than the existing methods for the same class which also provide full fault coverage. The test suites generated by the method can be used to check a conformance relation between a specification and its implementations.
• For a copy click here: PDF 

Test generation with respect to distributed interfaces

• Authors: G. Luo, R. Dssouli, G. v. Bochmann, P. Ventakaram and A. Ghedamsi
• Reference: [Luo 93f] Computer Standards & Interfaces 16 (1994), pp.119-132
• Abstract:
• For a copy click here: PDF

Software testing based on SDL specifications with SAVE

• Authors: G. Luo, A. Das and G.v. Bochmann
• Reference: [Luo 94a] IEEE Tr. on Software Eng., Vol.20, 1 (Jan. 1994), pp. 72-78
• Abstract: The signal SAVE construct is one of the features distinguishing SDL from traditional high-level specification and programming languages. However, this feature increases the difficulties of testing SDL-specified software. We present a testing approach consisting of the following three phases: SDL specifications are first abstracted into finite state machines with save constructs, called SDL-machines; the resulting SDL-machines are then transformed into equivalent finite state machines without save constructs if this is possible; finally test cases are selected from the resulting finite state machines. Since there are many existing methods for the first and third phases, we mainly concentrate in this paper upon the second phase and come up with a method of transforming SDL-machines into equivalent finite state machines, which preserve the same input/output relationship as in the original SDL-machines. The transformation method is useful not only for testing, but also for verifying SDL-specified software.
• For a copy click here: PDF

Test selection based on communicating nondeterministic finite-state machines using a generalized Wp-method

• Authors: G. Luo, G.v. Bochmann and A. Petrenko
• Reference: [Luo 94b] IEEE Trans. on Software Engineering 20, 2 (Febr. 1994), pp. 149-162
• Abstract: We present a method of generating test sequences for concurrent programs and communication protocols that are modeled as communicating nondeterministic finite state machines (CNFSMs). A conformance relation, called trace-equivalence, is defined within this model, serving as a guide to test generation. A test generation method for a single nondeterministic finite state machine (NFSM) is developed, which is an improved and generalized version of the Wp-method that generates test sequences only for deterministic finite state machines. It is applicable to both nondeterministic and deterministic finite state machines. When applied to deterministic finite state machines, it yields usually smaller test suites with full fault coverage than the existing methods that also provide full fault coverage, when the numbers of states in implementation NFSMs are bounded by a known integer. For a system of CNFSMs, the test sequences are generated in the following manner: A system of CNFSMs is first reduced into a single NFSM by reachability analysis; then the test sequences are generated from the resulting NFSM using the generalized Wp-method.
• For a copy click here: PDF

Testing deterministic implementations from nondeterministic FSM specifications

• Authors: A. Petrenko, N. Yevtushenko and G. v. Bochmann
• Reference: [Petr 96c] in Proc. of 9th International Workshop on Testing of Communicating Systems (IWTCS'96), pp.125-140
• Abstract:
• For a copy click here: PDF

A test generation tool for specifications in the form of state machines

• Authors: Q. M. Tan, A. Petrenko and G. v. Bochmann
• Reference: [Tan 96a] in proceedings of the International Communications Conference (ICC) 96, session on advanced tools and technologies for developing high integrity software systems, Dallas, Texas, June 23-27, 1996, pp.225-229
• Abstract:
• For a copy click here: PDF

On fault coverage of tests for finite state specifications

• Authors: A. Petrenko, G. v. Bochmann and M. Yao
• Reference: [Petr 96b] in Computer Networks and ISDN Systems, special issue on Protocol Testing, Vol. 29, 1996, pp.81-106
• Abstract: Testing is a trade-off between increased confidence in the correctness of the implementation under test and constraints on the amount of time and effort that can be spent in testing. Therefore, the coverage, or adequacy of the test suite, becomes a very important issue. In this paper, we analyze basic ideas underlying the techniques for fault coverage analysis and assurance mainly developed in the context of protocol conformance testing based on finite state models. Special attention is paid to parameters which determine the testability of a given specification and influence the length of a test suite which guarantees complete fault coverage. We also point out certain issues which need further study.
• For a copy click here: PDF

Test development - based on models of labeled transition systems (LTS)

Modeling Basic LOTOS by FSMs for Conformance Testing

• Authors: Q. M. Tan, A. Petrenko and G.v. Bochmann
• Reference: [Tan 95a] Proceedings of the 15th International Symposium on Protocol Specification, Testing and Verification (PSTV 15), Poland, June 95, pp.137-152
• Abstract:
• For a copy click here: PDF

A framework for conformance testing of systems communicating through rendezvous

• Authors: Q. M. Tan, A. Petrenko and G.v. Bochmann
• Reference: [Tan 96b] in proceedings of the 26th IEEE International Symposium on Fault-Tolerant Computing, Sendai, Japan, June 25-27, 1996, pp.230-238
• Abstract:
• For a copy click here: PDF

Checking experiments with labeled transition systems for trace equivalence

• Authors: Q. M. Tan, A. Petrenko and G.v. Bochmann
• Reference: [Tan 97a] in Proc. IFIP 10th Intern. Workshop on Testing of Communication Systems(IWTCS'97), Cheju Island, Korea, 1997
• Abstract: We apply the state identification techniques for testing communication systems which are modeled labeled transition systems (LTSs). The conformance requirements of specifications are represented as the trace equivalence relation and derived tests have finite behavior and provide well-defined fault coverage. We redefine in the realm of LTSs the notions of state identification that were originally defined in the realm of input/output finite state machines (FSMs). Then we present the corresponding test generation methods and discuss their fault coverage. It is shown that for an FSM-based method with a notion of state identification we can have a corresponding LTS-based method with a similar notion of state identification, and if the FSM-based method guarantees complete fault coverage then the LTS-analogue also guarantees such coverage.
• For a copy click here: PDF

Test development - based on models with interaction parameters

Testing Implementations of an Application-Level Communication Protocol: Inter-Library Loan

• Authors: E. Cerny and G.v. Bochmann
• Reference: [Cern 85] Proc. Fault Tolerant Computing Symposium '85, IEEE
• Abstract:
• For a copy: please look in the proceedings

A Test Design Methodology for Protocol Testing

• Authors: B. Sarikaya, G.v. Bochmann and E. Cerny
• Reference: [Sari 87a] IEEE Trans. on Soft. Eng., Vol.13, no.5, May 1987, pp. 518-531
• Abstract:
• For a copy: PDF

Application Layer Protocol Testing and ASN1 Support Tools

• Authors: G.v. Bochmann, M. Deslauriers and S. Bessette
• Reference: [Boch 86b] Proc. IEEE GLOBECOM Conf., Houston, Dec. 1986, pp. 767-771
• Abstract:
• For a copy: please look in the proceedings

Automatic analysis and test case derivation for a restricted class of LOTOS expressions with data parameters

• Authors: T. Higashino and G.v. Bochmann
• Reference: [Higa 94a] IEEE Tr. on Software Eng., Vol 20, 1 (Jan. 1994), pp. 29-42
• Abstract:
• For a copy click here: PDF

Automating the process of test derivation from SDL specifications

• Authors: G.v. Bochmann, A. Petrenko, O. Bellal and S. Maguiraga
• Reference: [Boch 97a] in Proc. eighth SDL Forum, INT in Evry, Sept. 22-26, 1997
• Abstract: In this paper, we present a set of automated tools for the development of conformance tests following a methodology based on a partial unfolding of a given SDL specification, describing the behavior of the system under test. The methodology relies on FSM-based test derivation methods which focus on the fault coverage aspect of testing. The tool kit offers to the test designer a number of options for achieving different levels of fault coverage. In particular, it provides support for partial specifications, grouped transitions and timers. The tests, which are generated in SDL or in TTCN must be completed by hand concerning certain aspects related to signal parameters, however, most of these adjustments are relatively straightforward and certain parts of the original SDL specification can be reused without change. We also report on our experience of using the tool kit for the development of a test suite for the ATM PNNI signalling protocol.
• For a copy click here: PDF

An Automatic Trace Analysis Tool Generator for Estelle Specifications

• Authors: S.A. Ezust and G.v. Bochmann
• Reference: [Ezus 95b] Computer Communication review Volume 25 Number 4, October 1995, Proceedings of ACM SIGCOMM 95 Conference, Cambridge, MA, pp. 175-184
• Abstract:
• For a copy click here: PDF

Test development - diagnostic testing

Diagnosis for single transition faults in communicating finite state machines

• Authors: A. Ghedamsi, G.v. Bochmann and R. Dssouli
• Reference: [Ghed 93a] IEEE International Conference on Distributed Computing Systems (ICDCS'93), Pittsburgh, USA, May 1993; a shorter version is also included in the proceedings of IEEE Int. Phoenix Conf. on Computer Communications, March 93
• Abstract: In this paper, we propose a diagnostic algorithm for the case where distributed system specifications (implementations) are given in the form of communicating finite state machines (CFSMs). Such an algorithm localizes the faulty transition in the distributed system once the fault has been detected. It generates, if necessary, additional diagnostic test cases which depend on the observed symptoms and which permit the location of the detected faults. The algorithm guarantees the correct diagnosis of any single transition (output and/or transfer) faults in a system of communicating FSMs. A simple example is used to demonstrate the functioning of the different steps of the proposed diagnostic algorithm.
• For a copy click here: PDF

Multiple fault diagnostics for finite state machines

• Authors: A. Ghedamsi, G.v. Bochmann and R. Dssouli
• Reference: [Ghed 93c] Proc. IEEE INFOCOM'93, San Francisco, USA, March 93
• Abstract:
• For a copy click here: PDF

Diagnosing distributed systems modeled by communicating finite state machines

• Authors: A. Ghedamsi, G.v. Bochmann and R. Dssouli
• Reference: [Ghed 93dx] Revue Reseaux et Informatique Repartie, Vol.3, No.4, 1993, Editions Hermes, pp.343-363
• Abstract: We propose a diagnostic algorithm for the case where a distributed system specification (implementation) is given in the form of communicating finite state machines (CFSMs). Such an algorithm localizes the faulty transition in the distributed system once the fault has been detected. It generates, if necessary, additional diagnostic test cases which depend on the observed symptoms and which permit the location of the detected fault. The algorithm guarantees the correct diagnosis of any single (output or transfer) fault in a system of communicating FSMs. A simple example is used to demonstrate the functioning of the different steps of the proposed diagnostic algorithm.
• For a copy click here: PDF

Test development - testing embedded system components

Testing in context: framework and test derivation

• Authors: A. Petrenko, N. Yevtushenko, G.v. Bochmann and R. Dssouli
• Reference: [Petr 96a] Computer Communications Journal, Special issue on Protocol engineering, Vol. 19, 1996, pp.1236-1249
• Abstract:
• For a copy click here: PDF

Fault models for testing in context

• Authors: A. Petrenko, N. Yevtushenko and G.v. Bochmann
• Reference: [Petr 96d] in Proc. IFIP symposium FORTE-PSTV'96, Formal Description Techniques IX, R. Gotzhein and J. Bredereke, Chapman&Hall, 1996, pp. 163-178.
• Abstract:
• For a copy click here: PDF (not available)

Deriving protocols from service specifications

Deriving protocol specifications from service specifications including parameters

• Authors: R. Gotzhein and G.v. Bochmann
• Reference: [Gotz 90] ACM Transactions on Computer Systems, Vol.8, No.4, 1990, pp.255-283
• Abstract:
• For a copy: PDF

Deriving protocol specifications from service specifications written in LOTOS

• Authors: C. Kant, T. Higashino and G.v. Bochmann
• Reference: [Kant 96a] Distributed Computing, Vol. 10, No. 1, 1996, pp.29-47
• Abstract:
• For a copy click here: PDF

Dérivation de spécifications de protocole à partir de spécifications de service avec des contraintes temps-réel

• Authors: A. Khoumsi, G.v. Bochmann and R. Dssouli
• Reference: [Khou 94i] Revue Réseaux et Informatique Répartie, Volume 4, No.1, 1994, pp. 7-29
• Abstract:
• For a copy click here: PDF

Protocol synthesis using basic LOTOS and global variables

• Authors: A. Khoumsi and G.v. Bochmann
• Reference: [Khou 95b] in Proc. of Intern. Conference on Network Protocols (ICNP), 1995
• Abstract:
• For a copy click here: PDF

Deriving communication gateways

Design principles for communication gateways

• Authors: G.v. Bochmann and P. Mondain-Monval
• Reference: [Boch 90b] IEEE Tr. on Selected Areas in Communications, Vol.8, 1 (Jan. 1990), pp. 12-21; russian translation: Express Information (overview of western publications), Information Transfer, 1991
• Abstract:
• For a copy: PDF

Deriving protocol converters for communication gateways

• Authors: G.v. Bochmann
• Reference: [Boch 90i] IEEE Trans. on Comm., Vol. 38, 9 (Sept. 1990), pp. 1298-1300
• Abstract:
• For a copy: PDF

A formal method for synthesizing optimized protocol converters and its application to mobile data networks

• Authors: Z.P. Tao and G.v. Bochmann
• Reference: [Tao 99a] to be published in Int. Journal on Wireless Networks (Balzer Sc. Publ.).
• Abstract:
• For a copy click here: PDF

An efficient method for protocol conversion

• Authors: Z.P. Tao, G.v. Bochmann and R. Dssouli
• Reference: [Tao 95c] Proceedings of the Fourth Intl Conference on Computer Communications and Networks (IC3N 95), Las Vegas, USA, September 1995, p.40-47
• Abstract:
• For a copy click here: PDF

Deriving submodules for real-time process control applications

On the Construction of Submodule Specifications and Communication Protocols

• Authors: P. Merlin and G.v. Bochmann
• Reference: [Merl 83] ACM Trans. on Programming Languages and Systems, Vol. 5, No. 1 (Jan. 1983), pp. 1-25
• Abstract:
• For a copy: PDF

On the construction of communication protocols

• Authors: G.v. Bochmann and P. Merlin
• Reference: [Boch 80d] ICCC, 1980, pp.371-378, reprinted in "Communication Protocol Modeling", edited by C. Sunshine, Artech House Publ., 1981; russian translation: Problems of Intern. Center for Science and Techn. Information, Moscow, 1981, no. 2, pp. 146-155
• Abstract:
• For a copy: please look in the proceedings

Submodule construction for systems of I/O automata

• Authors: J. Drissi and G.v. Bochmann
• Reference: [Dris 99b] unpublished document
• Abstract: This paper addresses the problem of designing a submodule of a given system of communicating I/O automata. The problem may be formulated mathematically by the equation (C||X)rA under the constraint IX=In, where C represents the specification of the known part of the system, called the context, A represents the specification of the whole system, X represents the specification of the submodule to be constructed, || is a composition operator, r is a conformance relation and In is the required set of inputs for X. As conformance relation, we consider the safe realization and the subtype relation. The subtype relation is a generalization of the well known criteria of trace equivalence, complete trace equivalence, quasi equivalence and reduction, while the weaker safe realization relation is implied by all those criteria. We propose two algorithms for solving the problem with respect to the safe realization and the subtype relation and we characterize the set of solutions in each case.
• For a copy click here: PDF

Submodule construction tool

• Authors: J. Drissi and G.v. Bochmann
• Reference: [Dris 99a] in Proc. Int. Conf. on Computational Intelligence for Modelling, Control and Automation, Vienne, Febr. 1999, (M. Mohammadian, Ed.), IOS Press, pp. 319-324.
• Abstract:
• For a copy click here: PDF

A model and an algorithm of subsystem construction

• Authors: Z.P. Tao, G.v. Bochmann and R. Dssouli
• Reference: [Tao 95d] in proceedings of the Eighth International Conference on parallel and distributed computing systems, Sept. 21-23, 1995 Orlando, Florida, USA, pp.619-622
• Abstract:
• For a copy click here: PDF (not yet available)

Other formal transformations

Failure-equivalent transformation of transition systems to avoid internal actions

• Authors: G. Luo, G.v. Bochmann, A. Das and C. Wu
• Reference: [Luo 92j] Information Processing Letters, Vol.44, No.6, North-Holland, 1992, pp. 333-343
• Abstract:
• For a copy: PDF

Merging behavior specifications

• Authors: F. Khendek and G.v. Bochmann
• Reference: [Khen 95a] in Journal of Formal Methods in System Design, Vol. 6, No. 3, pp. 259-293, June 1995
• Abstract:
• For a copy click here: PDF

Specialization in Estelle

• Authors: R. Gotzhein and G.v. Bochmann
• Reference: [Gotz 94a] IFIP Symp. on Protocol Spec., Testing and Verification, Vancouver, 1994, pp.17-32
• Abstract:
• For a copy click here: PDF

Incremental construction approach for distributed system specifications

• Authors: F. Khendek and G.v. Bochmann
• Reference: [Khen 93a] Proc. of the sixth Int. Conf. on Formal Description Techniques (FORTE'93), Boston, Massachussets, October 1993, pp.89-104
• Abstract: In this paper, we propose an incremental construction approach for distributed system specifications. These specifications are structured as a parallel composition of subsystem specifications. The approach consists of merging two specifications Sold and Sadded into a new specification Snew, such that Snew extends Sold and Snew extends Sadded. Moreover, in the case of cyclic behaviors, Snew offers a choice between behaviors of Sold and behaviors of Sadded, in a recursive manner. The derived specification Snew has the same internal structure as Sold. Our approach is described in terms of Labelled Transition Systems, and it is applicable for many specification languages.
• For a copy click here: PDF
  

This page was prepared by G.v. Bochmann in July 1999, revised Nov. 2016