Science, Faculty of
Computer Science, Department of
DSpace
UBCV
Lu, Ying
Master of Science - MSc
University of British Columbia
Test suite generation and selection form important aspects of conformance testing. The test suite generation process is usually tedious and time-consuming. The selection of appropriate test cases with certain fault coverage requires intensive analysis of the protocol. It is difficult to manually generate test suites without errors. The test suite generation process must therefore be automated. This thesis addresses the issues of design and development of the front end of an automatic test suite generation and selection environment named TESTGEN. TESTGEN generates TTCN test suites from the formal specification of protocols. TESTGEN adopts a new test suite generation method based on a combination of the extended transition system (ETS) and ASN.l representation of protocols. The new test generation method integrates the testing of both control part and data part of protocols. The test suites generated by TESTGEN are expected to provide better fault coverage than other existing test generation methods. An Estelle-like intermediate language called Estelle.Y is defined for the ETS-based formal description of protocols in TESTGEN. In order to test the data part, the control part of protocols and the protocol timers more thoroughly, we introduce ASN.l and explicit timer constructs into Estelle.Y. In addition, we design a protocol data structure (PDS) as the internal representations of protocols based on the ETS/ASN.l formalism. A parser is then designed and developed to translate the Estelle.Y/ASN.l specification of protocols into the PDS. We test the parser and verify the correctness of the generated PDS by applying a set of consistency checking functions to PDS. The correctness of PDS can also be verified by printing out the protocol information represented in PDS using a set of printing functions. In order to verify the viability of the TESTGEN environment, as well as to gain experience of conformance testing of high speed network protocols, we specify a specific protocol, the FDDI MAC protocol in Estelle.Y/ASN.l. The formal specification of the FDDI protocol in Estelle.Y and our experience with test sequence generation using TESTGEN are then presented.
TESTGEN, An Environment for Protocol Test Sequence Generation, and Its Application to the FDDI MAC Protocol By YING LU B.Sc. Tsinghua University, China, 1985 M.Sc. Peking Union Medical College, China, 1988 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF T H E REQUIREMENTS FOR T H E DEGREE OF MASTER OF SCIENCE in T H E FACULTY OF GRADUATE STUDIES (DEPARTMENT OF COMPUTER SCIENCE) We accept this thesis as conforming to the required standard T H E UNIVERSITY OF BRITISH COLUMBIA August 1991 ©Ying Lu, 1991 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department The University of British Columbia Vancouver, Canada DE-6 (2/88) Abstract Test suite generation and selection form important aspects of conformance testing. The test suite generation process is usually tedious and time-consuming. The selection of appropriate test cases with certain fault coverage requires intensive analysis of the protocol. It is difficult to manually generate test suites without errors. The test suite generation process must therefore be automated. This thesis addresses the issues of design and development of the front end of an automatic test suite generation and selection environment named TESTGEN. TESTGEN generates TTCN test suites from the formal specification of protocols. TESTGEN adopts a new test suite generation method based on a combination of the extended transition system (ETS) and ASN.l representation of protocols. The new test generation method integrates the testing of both control part and data part of protocols. The test suites generated by TESTGEN are expected to provide better fault coverage than other existing test generation methods. An Estelle-like intermediate language called Estelle.Y is defined for the ETS-based formal description of protocols in TESTGEN. In order to test the data part, the control part of protocols and the protocol timers more thoroughly, we introduce ASN.l and explicit timer constructs into Estelle.Y. In addition, we design a protocol data structure (PDS) as the internal representations of protocols based on the ETS/ASN.l formalism. A parser is then designed and developed to translate the Estelle.Y/ASN.l specification of protocols into the PDS. We test the parser and verify the correctness of the generated PDS by applying a set of consistency checking functions to PDS. The correctness of PDS can also be verified by printing out the protocol information represented in PDS using a set of printing functions. In order to verify the viability of the TESTGEN environment, as well as to gain experience of conformance testing of high speed network protocols, we specify a specific protocol, the FDDI MAC protocol in Estelle.Y/ASN.l. The formal specification of the FDDI protocol in Estelle.Y and our experience with test sequence generation using TESTGEN are then presented. ii Contents Abstract " Contents iii List of Figures vi Acknowledgement vii 1 Introduction 1 1.1 Background 1 1.1.1 OSI conformance testing 1 1.1.2 Automatic test generation 3 1.1.3 FDDI 3 1.2 Related works 4 1.2.1 Test generation method 5 1.2.2 Test generation tools 6 1.3 Thesis objectives and contributions 8 1.4 Thesis outline 9 2 T E S T G E N 11 2.1 Methodology 11 2.1.1 Extended Transition System + ASN.l Formalism 12 2.1.2 Test generation method 15 2.1.3 Test generation constraints 16 2.1.4 Test suite generation engine 17 2.2 TESTGEN components 18 3 Estelle.Y and Protocol Data Structure (PDS) 20 3.1 motivation 21 3.2 Estelle.Y 22 3.2.1 EsteUe and ASN.l 22 3.2.2 Design issues 23 iii 3.2.3 Estelle.Y definition 24 3.2.4 Estelle.Y versus Estelle 28 3.3 Protocol data structure 30 3.3.1 Representation of protocol descriptors 30 3.3.2 Protocol descriptor access 31 3.3.3 PDS data structure definition 33 3.3.4 ASN.l type tree 39 3.4 Summary 43 4 T E S T G E N parser 45 4.1 Design considerations 45 4.1.1 ASN.l parser 46 4.1.2 Lex/Yacc tools 47 4.1.3 Abstract syntax tree 48 4.2 Implementation 50 4.2.1 Declaration part 50 4.2.2 Initialization part 52 4.2.3 State-transition part 52 4.3 Testing 53 4.3.1 Printing PDS 53 4.3.2 Consistency checking of PDS 54 5 Test generation for the FDDI M A C protocol 56 5.1 FDDI MAC sublayer 57 5.1.1 Services 57 5.1.2 Facilities 58 5.1.3 Operation 59 5.1.4 Structure 60 5.2 The formal specification of FDDI MAC protocol 60 5.2.1 Data part in ASN.l 62 5.2.2 Control part in Estelle.Y 62 5.3 Generating test suite using TESTGEN 67 5.3.1 PDS of FDDI MAC protocol 67 5.3.2 Tuning constraints for FDDI MAC protocol 67 5.3.3 Test generation 68 5.4 Summary 69 6 Conclusions 70 6.1 TESTGEN features 70 6.2 TSG for FDDI using TESTGEN 71 6.3 Future works 72 iv A Estelle.Y B N F definition 79 B A S N . l specification of F D D I M A C SPs and PDUs 86 C Excerpt of Estelle.Y Specification of F D D I M A C protocol 93 D T E S T G E N menus H I E Consistency Requirements of P D S 124 v List of Figures 1.1 FDDI relationships to OSI model 4 2.1 Test Suite Generation Process 18 3.1 Example of the declaration part 26 3.2 Example of the initialization part 26 3.3 Example of a transition declaration in the state-transition part 27 3.4 Example of ASN.l definition of protocol SPs 29 3.5 The main data structure of PDS 31 3.6 C structure definition of PDS 32 3.7 STATE definition 35 3.8 TRANS definition 36 3.9 VAR and CONST definitions 37 3.10 TIMER definition 37 3.11 The relation diagram of the PDS components 38 3.12 The data structure of template ENODE 40 3.13 ASN.l type example 41 3.14 ASN.l type tree of PduType 41 3.15 ISP definition 42 3.16 SPPARM definition 43 4.1 TESTGEN parser configuration 47 4.2 TESTGEN Parser generation 48 4.3 Examples of syntax trees 49 4.4 IFSTMT definition 49 4.5 EXPR definition 50 5.1 FDDI MAC service primitives 58 5.2 Format of MAC Protocol Data Units 59 5.3 Testing of FDDI MAC layer 61 5.4 FDDI MAC protocol state machine 67 vi Acknowledgements First of all, I would like to express my sincere thanks to Dr. Son T. Vuong, my supervisor, for his guidance, commitment and understanding throughout my research work. I would also like to thank Dr. Samuel Chanson for his helpful comments and careful reading of the final draft. Special thanks are also due to Holger Janssen for his originating the research project and always finding time to help me when I needed it. I would like to thank Mike Sample for his ASN.l parser and helpful suggestions. The financial support from the Department of Computer Science at the University of British Columbia and from the Japan Tobacco Company and INDE Electronics, Inc. in the form of an Research Assistantship is gratefully acknowledged. Last but not least, a heartfelt thanks to my parents for their endless love and to Geng Lin for being my wonderful husband. vii Chapter 1 Introduction This thesis addresses issues in the development of an automatic protocol test generation and selection environment named TESTGEN and its applications. TESTGEN can automatically derive T T C N test suites from the formal description of protocols. TESTGEN generates test suites using a new test suite generation (TSG) method that integrates both the control flow testing and the data flow testing. This thesis presents the design and development of the TESTGEN front end and the application of TESTGEN to a high-speed network protocol, the FDDI MAC protocol. A formal specification of the FDDI MAC protocol is produced and problems with the formal specification for testing the FDDI MAC protocol are discussed. A T T C N test suite will be derived for the FDDI MAC protocol from the formal specification of the protocol by using TESTGEN. 1.1 Background This section gives the general background for the thesis. 1.1.1 OSI conformance tes t ing As the OSI protocol standards become stable and their implementations proliferated, ISO focused its attention on the problem of interoperability of different protocol implementations. Consequencely the Conformance Testing Methodology and Framework [ISO-9646] standard is developed. 1 CHAPTER 1. INTRODUCTION 2 A protocol implementation can be submitted to conformance testing in order to increase confidence in its conformance to the protocol standard. The ISO 9646 standard states: "The purpose of Conformance Testing is to increase the probability that different implemen-tations are able to interwork". In the conformance testing methodology, an Implementation Under Test (IUT) consists of the implementation of one or more layers of the OSI reference model. An IUT is said to conform to the OSI protocol standards if it fulfills the conformance requirements defined in the ISO 9646 standard. The ISO test methods are based on the black-box test principle. Although aspects of both internal and external behavior are described in OSI protocol standards, only the external behav-iors of the IUT is considered for conformance testing. The external behaviors of an (N)-entity are defined in terms of (N) Abstract Service Primitives ( (N)-ASPs), (N-l) Abstract Service Primitives ( (N-l)-ASPs) and (N) Protocol Data Units (PDUs). The Points of Control and Observation (PCO) are where the test events (ASPs or PDUs) of an IUT can be observed and controlled within the test environment. The ISO 9646 standard defines four test methods which can be distinguished by the location of the PCOs and the degree of control available at those PCOs as well as by the nature of the coordination between events exchanged at the PCOs (test coordination procedure). Conformance testing is carried out by using test suites. A (conformance) test suite is the complete set of test cases that are needed to perform dynamic conformance testing for one or more OSI protocols. The ISO 9646 standard defines a hierarchical structure for description of test suites. The key level of a test suite is test case. The lowest level of the structure consists of test events. The test events are the transfer of a single PDU or ASP to or from the IUT. The Tabular and Tree Combined Notation (TTCN) [ISO-TTCN] is defined to specify abstract test suites. Abstract test suites are specific to a test method but test system independent. CHAPTER 1. INTRODUCTION 3 1.1.2 Automatic test generation The generation and selection of an appropriate test suite is an essential aspect of conformance testing. Communication protocols are extraordinarily complex. The selection and generation of test cases are challenging and tedious tasks for several reasons. Firstly, for a given protocol, a comprehensive test suite may contain from hundreds to thousands of test cases, where each test case may require hours to design and minutes to execute [PTJH-88]. It is very difficult, if not impossible, to manually generate a test suite without errors [Wvong-90]. Secondly, the selection of appropriate test cases with certain fault coverage requires intensive analysis of a protocol. A promising solution for the problems is to develop an automated selective test generation environment. Automatic test suite generation has many advantages over the manual approach. It is easy to adapt to changes in protocol specifications and T T C N . More complete and consistent test cases can be generated. More flexibilities can be provided for the user to generate test suites for their particular testing purpose. Finally, certain fault coverage measure can be incorporated to allow user to control the fault coverage of generated test suites. For these reasons, the automatic generation of test suite from the formal descriptions of protocols is drawing more attentions. 1.1.3 FDDI The Fiber Distributed Data Interface (FDDI) is a high speed local area network (LAN) standard developed by ANSI. FDDI is a general purpose multi-station network designed for efficient operations with a peak data rate of 100 megabits per second. It uses a Token Ring architecture with optical fibers as transmission medium [ANSI-1987] [ANSI-1989]. Although it is not an OSI standard, the FDDI standard has been developed in conformance with the the OSI reference model and the OSI management framework and layer management guidelines. The set of four components of the FDDI standard provides the Physical Layer and the lower sublayer of the Data Link Layer of the OSI reference model as depicted in Figure 1.1. The FDDI Media Access Control (MAC) layer is the lower sublayer of the Data Link Layer. It is the most important component of the FDDI standard among the four (MAC, PHY, PMD CHAPTER 1. INTRODUCTION 4 Data Link layer M A C (Media Access Control) SMT Physical layer PHY (Physical Protocol) PMD (Physical Medium Dependent) Figure 1.1: F D D I relationships to OSI model and SMT) . M A C standard is the core part of the F D D I standard that distinguishes FDDI from other I E E E L A N standards. ^DDI M A C protocol is developed based on the concepts of Token Ring Access Method de-fined in A N S I / I E E E 802.5-1985 while the original concepts have been modified to accommodate the higher F D D I speeds. [ROSS-86] [ROSS-90] give excellent introductions to FDDI . High speed network is becoming an active research area recently. Major work has been done on the design of high speed (or high performance) protocols. FDDI has been widely accepted as the next generation of L A N standard. The F D D I network and its protocols are studied intensively [ROSS-86] [ROSS-90]. We are focusing our attention on the testing of FDDI implementations. The development of FDDI protocols are complicated due to its 100 Mb/s data rate, more rigorous timing requirements and the use of fiber optics techniques. It is important to test the F D D I products provided by different vendors for their conformance to the FDDI standard. Testing such complex protocols is a challenging problem. 1.2 Related works A great deal of efforts have been made in development of feasible test generation method for .automating the test generation process. In this section, we discusses the well known methods CHAPTER 1. INTRODUCTION 5 and the tools developed based on those TSG methods. 1.2.1 Tes t generat ion m e t h o d Most of the well known protocol test generation methods assume the Finite State Machine (FSM) model for protocol specifications. T-method [Naito-81], U-method [Sabn-88], D-method [Gone-70] and W-method [Chow-78] are four well-known formal techniques for protocol testing based on the concept of Transition Tour and Characterizing Input/Output Sequence. See [Sidhu-89] for a detailed survey on FSM-based test sequence generation methods. However, these methods address the control part of protocols only. These formal methods were improved and optimized [Chan-89] [Vuong-89]. Recently, several test generation methods which test both of the control and data aspects of protocols have seen proposed. Sarikaya et al. [Sari-87] proposed a methodology that applies the concept of functional program testing to the generation of test sequences for testing data part of protocols. This method requires considerable manual efforts to identify functions and their relationships in the case of complex protocol specifications. Another well known data flow coverage methods is proposed by Ural et al. [Ural-87-1] [Ural-87-2]. The method is based on the principles of data flow analysis techniques [Fosd-76]. The method traces the flow of data through the associations between assignments of values to variables (i.e. definitions) and the usage of these variables (i.e. uses) in either assigning values to other variables or determining the outcome of conditional branching. This method generates a set of test sequences to cover all definition and use pairs satisfying certain constraints. The resulting set of test sequences provides the capability of determining whether an IUT estab-lishes the desired flow of data expressed in a given specification. The method is improved in [Ural-88] to derive test sequences with better fault coverage. The refined method is based on the identification of all inputs that influence each output in a given protocol specification. The flow of both control and data specified in the specification are modeled by a flowgraph. All associations between definitions and usages of variables employed in the specification are ex-plicitly identified from the flowgraph. Associations between each output and those inputs that CHAPTER 1. INTRODUCTION 6 influence the output are then identified. In fact, these associations represent the input-output relations through which protocol functions are defined. Finally test sequence are selected to cover each of such association at least once. A new test generation method is presented in [EBE-89-2] [EBE-89-1]. An External Be-havior Expression (EBE) is defined to specify only the external behaviors of a protocol. Test sequences are derived from the EBE specification of the protocols. The external behaviors of a protocol are described in terms of the input/output sequences and their logical (function and predicate) relations. The EBE specification of protocols can be obtained from formal protocol specifications in either Estelle or LOTOS. It is pointed out [Vuong-91-1] that some side effects due to implementation errors may re-main undetected by those existing methods [Sari-87] [Ural-87-1] [Ural-87-2] [Ural-88] [EBE-89-2] [EBE-89-1]. For example, in Ural's method [Ural-88] the conditions and effects on the variables are to be tested along only a single selected path between the definition-usage pairs, thus errors occurring in alternate paths are unlikely to be detected. The fault coverage and effective-ness of the test case will be increased if all known protocol conditions are verified along the definition-usage path of variables. Another new approach is proposed in [Vuong-91-1] which is expected to produce test suite with a better fault coverage than those existing methods. The proposed test suite generation method verifies all specified conditions on the external behavior of a protocol implementation for a selected set of subtours of the protocol graph. A set of so-called test suite generation constraints are used to guide the subtour identification and test suite generation. A detailed description of this new approach can be found in Chapter 2 of this thesis. 1.2.2 Test generat ion tools There are technical difficulties in deriving test sequences directly from the protocol specification in ISO FDTs, namely Estelle [ISO-9074], SDL and LOTOS [ISO-8807]. The first three methods which test both control and data parts of protocols assume that protocol specifications are given in Estelle as single module specifications (also called Normal Form Specifications). The EBE CHAPTER 1. INTRODUCTION 7 approach, assumes that protocol specifications are given in EBE. A formal specification based test generation tool named CONTEST-ESTL is presented in [Sari-89]. It is a realization of the functional formal specification based on test genera-tion method [Sari-87]. CONTEST-ESTL takes an Estelle specification as input and semi-automatically generate test sequences for the input specification. In CONTEST-ESTL, the normalization (transformation of an Estelle protocol specification into a specification in Es-telle Normal Form) and the construction of control flow and data flow graphs required for test sequence generation are automated. The test sequence identification is, however, only semi-automated. The users are required to identify functions by merging so-called blocks of data flow graph and then incorporate the effects of the enabling conditions of the normalized transitions into the sequences identified from the control flow graph and data flow graph to generate test sequences that cover data flow. In this thesis, we develop a software testing environment, TESTGEN, which automatically generates T T C N test suites from the formal specification of protocols, using the test generation method in [Vuong-91-1]. We assume protocols are specified in Estelle.Y. Estelle.Y is basically a single module Estelle enhanced by introducing explicit timers constructs and ASN.l subset. A Protocol Data Structure (PDS) is designed as the internal protocol representation from which all the possible subtours are identified by using the proposed test generation method. In order to generate test suite covering both control part and data part of protocols, the complete protocol information expressed in the Estelle.Y/ASN.l specification must be represented by the PDS. The test suite generation using TESTGEN is totally automated. Experienced users may use constraint editor to tune the default test suite generation constraints set by TESTGEN so that the generated test suite can better satisfy their particular testing purposes. CHAPTER 1. INTRODUCTION 8 1.3 Thesis objectives and contributions In this thesis, the research objectives are: 1) to design and develop the front end of the testing environment TESTGEN, and 2) to demonstrate the usefulness of the tool by applying it to a real world protocol and generate test suite for the protocol. The front end of the testing environment is the most important part of the whole testing environment. It is responsible for providing internal representation of protocols in which the external behaviors of a protocol are precisely and completely described. The internal represen-tation of protocols must be accessible to the subtour identification process which is the first step of the test generation process. The design and development of TESTGEN front end involve several aspects. Firstly, an intermediate formalism is necessary for the precise and complete description of external behav-iors of a protocol for conformance testing using TESTGEN. Secondly, a description language based on the defined intermediate formalism is required for formal specification of protocols. Thirdly, an internal representation of protocols is needed to allow the protocol knowledge de-scribed in the specification to be accessible to the subtour identification process which is an implementation of the test sequence generation algorithm. Finally a parser should be developed to transform the protocol specifications into their internal representations. To demonstrate the viability of TESTGEN, we produce a formal specification of a real world protocol, the FDDI MAC protocol. The specification is then fed into TESTGEN. Constraints are tuned via a constraint editor. A test suite of the FDDI MAC protocol is to be generated. The main contributions of this thesis include the following: 1. The refinement of the intermediate ETS/ASN.l formalism for the representation of pro-tocols in TESTGEN. 2. The definition of an intermediate formal description language Estelle.Y to allow commu-nication protocols to be formally specified based on ETS/ASN.l formalism representation and to allow both the control part and data part of protocols to be tested. CHAPTER 1. INTRODUCTION 9 3. The design of a Protocol Data Structure (PDS) to internally represent communication protocols specified in Estelle.Y/ASN.l. PDS is defined as a machine accessible form of the ETS/ASN.l formalism representation particularly for TESTGEN. It can also be used for other applications. 4. The design and implementation of a parser to translate the ETS/ASN.l specifications of protocols into the PDS to allow the protocol knowledge in the Estelle.Y/ASN.l specifi-cation to be accessed by the test sequence generation process in TESTGEN. We tested the parser through a set of consistency checking functions and through a set of printing functions, by checking items stored in the PDS. 5. The formal specification of a high-speed network protocol, the FDDI MAC protocol, in Estelle.Y/ASN.l to which TESTGEN is to be applied to generate a test suite for the protocol. 6. A method of combining two extended transition systems into a single one equivalent behaviors. In fact, the method is easily extended to combine arbitrary number of extended transition systems. 1.4 Thesis outline The rest of the thesis is organized as follows. Chapter 2 gives an overview of TESTGEN. An introduction to the test generation method-ology being used by TESTGEN and the architecture of the TESTGEN are presented. Chapter 3 and chapter 4 discuss the design and implementation of the front end of the TESTGEN tool. The definition of a formal language Estelle.Y and the data structure ver-sion of the internal representation of protocols are described in Chapter 3. The design and implementation of the TESTGEN parser are presented in Chapter 4. Chapter 5 discusses the issues of the test suite generation for FDDI mac protocol using TESTGEN. A review of the FDDI mac protocol is given first. The protocol is specified in CHAPTER 1. INTRODUCTION 10 Estelle.Y and the problems with the formal specification are discussed. In this chapter, we present a method to combine two extended transition systems into a single one with equivalent behaviors. The issues of tuning default constraints for TSG of FDDI mac protocol are are presented. Chapter 6 summarizes the important results and offers suggestions for future works. Chapter 2 T E S T G E N The generation of T T C N test suite is a tedious and repetitious process. Test suites must often be updated or rewritten because both the specification of the protocol to be tested and the T T C N standard are subject to periodic modifications. The test suite generation process must therefore be automated. TESTGEN is a test generation and selection environment for the conformance testing of communication protocols proposed by Holger Janssen [Vuong-91-1] at UBC. It is a TSG automation tool which can derive T T C N test suites from formal specifications of protocols. It directly supports ASN.l and Estelle.Y, a variation of Estelle that will be presented in Chapter 3. It is designed as an automation tool for the testing of OSI protocols and services based on the OSI conformance testing methodology and framework [ISO-9646]. 2.1 Methodology This section presents the definition of the Extended Transition System + ASN.l Formalism used in TESTGEN. The test generation method used in TESTGEN are also described. 11 CHAPTER 2. TESTGEN 12 2.1.1 Extended Transition System + ASN.l Formalism Motivation In order to automatically generate a test suite, the protocol knowledge defined in the protocol specification must be formalized and accessible to the test generation engine. The test suite generation is complicated by two factors: choices in the protocol specification account for protocol implementations with different but correct behavior and nondeterminism of the protocol accounts for unpredictable behavior of one implementation. In order to preserve the complete protocol knowledge, an appropriate intermediate protocol representation formalism and its internal representation are necessary. The conceptual model is very crucial in that the test generation method and the architecture of the tool are both based on that model. We use a pragmatic representation based on extended Transition System (ETS) and ASN.l which can represent nondeterminism 1 and implementation choices2 as well as syntactical information such as type definition of service primitives and parameters. This ETS+ASN.l knowledge is stored in our Protocol Data Structure (PDS) for use of the test suite generation engine or other protocol engineering applications. E T S + A S N . l Formalism The Extended Transition System (ETS) defined for TESTGEN environment provides a theo-retical foundation for formal description of protocols to be tested by TESTGEN. A transition system is a model for formal description of processes in a distributed system. Recently, the tran-sition system and its variations are popularly employed to model the behavior of communication protocols in protocol specification, verification and conformance testing. Definition 2.1 A transition system is a quadruple T —< Q,E.^,init > where e Q is a set, the states of T * E is a set, the events of T, 1 Nondeterminism in the protocol specification accounts for unpredictable IUT behavior. 2 Choices in the protocol specification accounts for implementation with different correct behavior. CHAPTER 2. TESTGEN 13 • —*CQxExQisa relation, the transitions of T, • init € Q is the initial state ofT. For simplicity, q —> q' will be used to represent < q, e,q* >€—*•. An alternative definition of the transition system, so-called labeled transition system, is given in [Kel-76] by refining the notation of state and transition. The state set is represented as a set product of the set of control states and the set of data states. A transition —>• is represented by a pair < Pt,Ft >, where P< is a predicate on Q and Ft is a partial function such that Ft(q) is defined whenever Pt(q) is true. Pt is called enabling predicate and Ft an action function. We define an extended transition system by further refining the notation of state, transition, event and initial state of the basic transition system. Such an extended transition system can be particularly used to model the observable behaviors of a protocol for conformance testing based on the 9646 standard. Definition 2.2 An Extended Transition System (ETS) is a quadruple ETS = (Q,E,—>,qinit) •where • Q is a set, the states of ETS, • E is a set, the events of ETS, • —>CQxExQ is a relation, the transitions of ETS, • Qinit G Q is the initial state of ETS. Q = STATE x VAR X C X TIMER, where STATE is the set of control states, VAR is the set of data states also called variables, C is a set of degenerated variables used to represent protocol characteristics that are invariant to the protocol execution and TIMER is a set of time constructs introduced to indicate time in the protocol representation. qinit is defined by the initial control state and the initial values of all variables and timers. E = ISP xOSPx PDU, where ISP is a set of Input Service Primitives (ISPs) accepted at the protocol's Service Access Points (SAPs), OSP is a set of Output Service Primitives (OSPs) CHAPTER 2. TESTGEN 14 offered at the protocol's SAPs and PDU is a set of Protocol Data Units (PDUs) which may be embedded in ISPs or OSPs. A transition —> is represented by a pair < Pt,Ft >, where Pt is the condition predicate on the set product Q x E and Ft is the action function on the set product Q x E. A transition is enabled if and only if the ISP and PDU associated with the transition (if any) are received and if the enabling predicate is true. When a transition is executed the associated action function is executed atomically: variables and timers are set, OSP(s) and PDU(s) are assembled (their parameters are set) and sent. The protocol changes from the current control state into the next control state. Furthermore, ASN.l abstract syntax is introduced to specify the structure and type of the elements in E, namely the ISPs, OSPs and PDUs and the parameters. There are several reasons for choosing ASN.l: • ASN.l is a standardized abstract syntax notation supported by ISO. • Some higher level protocols are specified in ASN.l. • ASN.l is supported in T T C N . • There are ASN.l tools available. A subset3 of the basic ASN.l abstract type notation defined in Section 1 and Section 2 of [ISO-8824] is used to specify the data part of the protocol, namely the structure and type of ISPs, OSPs and PDUs and their parameters. In our Extended Transition System (ETS), service primitive and protocol data unit parameters would be referenced by enabling predicates and action functions. We introduced an intuitive dot notation similar to the PASCAL or C structured type reference mechanism to allow the references to the parameters of ISPs, OSPs and PDUs. Thus the SP or PDU parameters described in the ASN.l part of the protocol spec-ification can be referenced by enabling predicates and action functions as follows: 3Other ASN.l features such as ASN.l value descriptions, selection types and macros are not currently sup-ported by our tools (they are not necessary for the ETS representation of a communication protocol). CHAPTER 2. TESTGEN 15 < SPname > {. < parametername >}+ or < PDUname > {. < parametername >}+ A detailed description of ETS/ASN. l formalism is given in [Vuong-91-1] 2.1.2 Test generat ion m e t h o d The test generation method adopted in the TESTGEN integrates both the control flow testing and the data flow testing with parameter variation. Furthermore, test generation and selec-tion are integrated and guided by user-defined test suite generation constraints and parameter variation constraints. Well known hardware and software test generation methods have been applied to confor-mance testing with various degrees of success. Most of them are based on the state transition model. The Transition Tour and characterizing Sequences based T [Nai-81], U [Sab-88], D [Gon-70] and W-methods [Cho-78] were improved and optimized [Cha-89] [Vuo-89] but still have two major shortcomings. First, they are weak in discovering errors due to additional states or transitions in the implementation. Second, they only address the control part of protocols. The data flow analysis based test suite generation method defined in [Ura-87], [EBE-89-1] and the flow coverage method defined in [Sar-87] address both the control flow part and the data part of protocols but are unlikely to detect errors due to side effects [Vuong-91-1]. As those errors are unpredictable, the only way to ensure their detection is to verify if all relevant conditions on the external behavior of the IUT are fulfilled along all branches of the tree representation of the protocol. The strategy adopted by TESTGEN is to verify as many conditions as possible on as many different protocol subtours as possible. The Test Suite Generation (TSG) method used in TESTGEN integrates both the control flow testing and the data flow testing with parameter variation and can produce test cases to cover any path defined by the service primitives that an CHAPTER 2. TESTGEN 16 IUT is allowed to exchange with its environment (peer entity or test system). Furthermore, it integrates the generation and selection of test suites by providing a menu driven environment where various TSG- and parameter variation constraints4 can be interactively defined by the user to control the amount and the distribution5 of test cases. 2.1.3 Test generation constraints Since communication protocols are recursive, some protocol subtours can be of infinite length. Parameter variation on the exchanged service primitives leads to a practically infinite number of parameter value combinations. The TSG constraints mechanism enables the user to select the subtours for which test cases are to be generated. The flexibility offered by the TSG constraints mechanism allows us to compare and evaluate different approaches to the test suite generation problem. The TSG-constraints define an upper and a lower bound on the number of times an ETS element is reached or used in one subtour. For example, to test the data part of a protocol implementation the user could specify the following constraints: the data transmission state can be reached between 2 and 10 times and the send.data and receive_data service primitives can be used used for at most 5 times. The TSG-constraints are set to default values when a PDS is created. A user-interactive constraint editor allows to edit and change the complete set of TSG constraints. The interested readers may refer to Appendix D for the menu-driven TSG-constraint editor. The parameter variation constraints define a set of values for each parameter of each ISP or PDU that can be sent to the IUT thus define the ISPs and PDUs that will be used to test the IUT. The current version of TESTGEN supports three SP or PDU parameter types: boolean, integer and character-string. The default parameter variation constraints are defined as follows: TRUE, FALSE for boolean, 4 I t should be noted that the term "constraint" is used in a different context than the one used in T T C N . ° T h e density of test cases can be increased for important or error prone protocol parts. CHAPTER 2. TESTGEN 17 0, 99 for integer and "test-stringl" for character strings. As an example, the default parameter constraint scheme would define twelve (3 X 2 X 2 X 1) different instances of a service primitive containing one integer parameter, two boolean parameters and one character string parameter. Each of those ISPs will be sent to the IUT in all subtours that fulfill all the TSG and parameter variation constraints. The ASP parameter-editor allows to edit and change the parameter variation constraints within the limits defined by the ASN.l definition of the parameter types. 2.1.4 Test suite generation engine Given the PDS representation of a communication protocol and a set of constraints for this PDS, the test suite generation engine identifies and stores all the subtours and derives a T T C N test case for each subtour. The subtour identification function performs an exhaustive search by means of a backtrack-ing depth first search over the tree representation of the protocol to be tested. A test-branch of this tree is said to be valid if and only if the subtour associated with this branch fulfills all the TSG constraints. For each ETS elements, e.g. states, transitions, there are two associated global pa-rameters, "MAXUSE" and "MINUSE". "MAXUSE" limits the value range of the max.reached and maxjased constraints. These constraints limit the length of each valid test-branch to be < MAXUSE x#states. In each state only a finite number of transitions can be applied (according to the protocol definition). The parameter variation constraints on the parameter of the service primitives exchanged in each transition limits the number of different instances of the service primitive in that transition. Thus the length and the number of different valid test-branches are kept finite so that the backtracking algorithm is guaranteed to terminate. "MINUSE" limits the value range of the mirureached and min.used constraints. The default value for "MAXUSE" constraints is 99. For "MINUSE" constraints the default value is 0. Elaborate constraints may be necessary to reduce the number of test cases that can be CHAPTER 2. TESTGEN 18 generated for a complex protocol (e.g. for the FDDI MAC protocol). Adequate constraints are likely to be determined in a trial and error process. 2.2 TESTGEN components The major components of TESTGEN are depicted in Figure 2.1. Abstract TTCN Test Suite c TTCN Tool (^^Test Tooi~~^^ 1 Formated TTCN output Excutable Test Suite Legend: File ( ) Data Structure Dynamic Module ~ ~ ~ ~ External Module Figure 2.1: Test Suite Generation Process The parser accepts the formal Estelle.Y/ASN.l protocol description and translates the CHAPTER 2. TESTGEN 19 protocol specification into a Protocol Data Structure (PDS) which serves as an internal rep-resentation of the combined extended transition system (ETS) and ASN.l formalism. The Test Suite Generation (TSG) and parameter variation constraints are set to default values by TESTGEN automatically. The default constraints can be modified by the user interactively through the constraints editor. Based on the PDS representation of a protocol and the TSG constraints the test suite generation engine identifies all the subtours of the combined ex-tended transition system and ASN.l formalism representation of the protocol that fulfill the TSG Constraints and generates an abstract T T C N test case for each of the subtours identified. A T T C N tool is used to edit and print the generated test suites and any T T C N supporting test tool can translate the abstract T T C N test suites to executable test suites in order to run them. Appropriate existing T T C N and test tools can be interfaced or incorporated to our environment to serve those purposes. TESTGEN tool is menu-driven. The parser, constraint editor and the test suite generation engine are three major functions. Through the main menu the user can load a Estelle.Y/ASN.l protocol specification into the system and call the parser to generate PDS from the protocol specification. A set of default constraints are set for the protocol and stored in the generated PDS automatically. Then the user can look at any of the items stored in the PDS through the PDS verification menu to check if the protocol information is properly represented in the PDS. The constraint editor is implemented as a menu-driven function. The user can set more TSG and SP parameter constraints or modify the existing TSG and SP parameter constraints through the constraint menu. Finally the user can call the test suite generation function to generate T T C N test cases through TSG menu. The user can view all the subtours identified by the subtour identification process or all the T T C N test cases generated from the identified subtours. The complete TESTGEN menu can be found in Appendix D. The generation of PDS is a key step for test suite generation using TESTGEN. The design of the PDS is of particular importance since all subsequent steps make use of this PDS. Chapter 3 Estelle.Y and Protocol Data Structure (PDS) Since protocol specifications described in natural language often contain ambiguities, protocol implementations based on such specifications are likely to be incompatible. The interoperability of two implementations based on the same protocol standard is thus not guaranteed. On the other hand, the process of deriving test suites directly from informal specifications does not seem possible. The test suites generated automatically must be derived from the formal specification of protocols. A formal language that can fully describe the external behaviors of a protocol based on the ETS + ASN.l formalism is therefore necessary for TESTGEN. As there is no standardized formal protocol description for most standardized protocols, the choice of which Formal Description Technique (FDT) to be supported was open. After consideration of LOTOS [ISO-8807], Estelle [ISO-9074], SDL [SDL-88], CRS [CRS-89] and EBE [EBE-89-2] and EsteUe Normal Form Specification (NFS) [Sari-87] we decided to use an Estelle-like formal language because Estelle is based on a conceptual model similar to the ETS+ASN.l formalism. Furthermore, Estelle is supported by ISO and is more "user-friendly" than LOTOS. Also many protocol specifications in Estelle are available. 20 CHAPTER 3. ESTELLE.Y AND PROTOCOL DATA STRUCTURE (PDS) 21 3.1 motivation There are technical difficulties to derive test cases directly from the ISO FDTs such as LOTOS [ISO-8807], Estelle [ISO-9074] or SDL [SDL-88]. The existing test generation methods which generate test suite covering both control part and data part of protocols are mostly based on the Estelle Normal Form Specification (NFS) of protocols. EBE is another intermediate formal description mechanism which is dedicated to describe only the external behaviors of protocols. Estelle.Y is defined for a similar reason. We are not intended to define a new FDT. How-ever, we need an intermediate formal specification of protocols based on ETS/ASN.l formalism representation of protocols. Estelle.Y is defined to be directly used with ASN.l. This is moti-vated by two facts. First, ASN.l has been widely used to specify the protocol data types for higher layer protocols. The protocol data types of some other protocols such as the FDDI SMT protocol are specified in ASN.l in the protocol standard as well. Second, ASN.l is supported in TTCN. Since TESTGEN generates T T C N test suites, ASN.l can be consistently used to specify the structure and data types of ISPs, OSPs and PDUs throughout the TSG process. Furthermore, protocol timers are important for conformance testing in that they have non-trivial impact on the observable behaviors of a protocol. Timers must therefore be tested. To facilitate the testing of protocol timers, we provide explicit mechanism for specification of timers in Estelle.Y. The specification of protocols in Estelle, SDL or CRS will be easily transformed to Estelle.Y specifications. NFS and EBE are not suitable for TESTGEN because they are not defined to be used directly with ASN.l and they do not explicitly support timers. Furthermore, NFS is not de-signed to be directly used to specify complex protocols. An NFS representation of a complex protocol is unreadable. Compared to NFS, Estelle.Y is more flexible since it supports more Pas-cal statements such as the conditional statements and loop statements. The Estelle.Y/ASN.l specification tends to be more concise and readable than that in NFS. In order to generate a test suite automatically, the syntactical and semantical information CHAPTER 3. ESTELLE.Y AND PROTOCOL DATA STRUCTURE (PDS) 22 of a protocol defined in the protocol specification must be accessible to the test generation engine. The Protocol Data Structure (PDS) is designed to be the machine accessible form of the ETS/ASN. l based formal protocol specification. It holds both the control part and the data part of a protocol specification. The following sections introduce the definition of an intermediate formal description language Estelle.Y and the PDS for TESTGEN. 3.2 Estelle.Y Estelle.Y is a formal language defined to specify protocols for automatic test suite generation. It is designed to be used with ASN.l, since the ETS+ASN.l formalism is being used by TEST-GEN. An Estelle.Y specification is a modified, single module Estelle specification enhanced by introducing explicit language support for timers and for structure references to SPs and PDUs and references to their parameters. The structure of SPs and PDUs and the data type of their parameters are specified in ASN.l. The ASN.l specification of SPs and PDUs is provided in a separate file along with the protocol specification. ASN.l specifications are parsed to the ASN.l type tree by the ASN.l parser. The Estelle.Y specifications are parsed to the PDS by the TESTGEN parser. Also the TESTGEN parser incorporates the ASN.l type tree into the PDS. 3.2.1 Estelle and A S N . l Estelle is a formal description technique (FDT) standard developed by ISO. It is a formal spec-ification language designed for the specification of communication protocols and services. It is based on the Extended Finite State Machine (EFSM) model. An Estelle specification describes a protocol and the services as a hierarchically structured system of non-deterministic sequential components (instance of modules) interchanging messages (called interactions) through bidi-rectional links between their ports (called interaction points) [ISO-9074]. It may be considered as an EFSM based extension of Pascal language. Estelle is implementation-oriented in that it is designed to specify both the internal and external behaviors of a protocol. Although it is designed to specify ISO protocols particularly, protocols standardized by other organizations CHAPTER 3. ESTELLE.Y AND PROTOCOL DATA STRUCTURE (PDS) 23 may also be specified in Estelle. Abstract Syntax Notation One (ASN.l) is a notation or language for the definition of com-plicated data types and their values without determining the way and instance of this type is to be represented during transfer. ASN.l is standardized by ISO [ISO-8824]. The ASN.l language is described using Backus Naur Form (BNF). The ASN.l definition of data structures or data types are very similar to those in the programming languages like Pascal or C. ASN.l's notation is similar to most programming languages in that it contains a set of simple built-in types, a set of rules for constructing programmer defined types and a mechanism to set the values of these types. ASN.l has been widely accepted as a formal language to specify the data structure for higher level OSI protocols. ASN.l is also used in TTCN to define data structures of protocol service primitives and protocol data units. 3.2.2 Design issues Estelle.Y is designed to formally specify the protocols and services for automatic test suite generation based on the ETS + ASN.l formalism. As a formal intermediate notation for conformance testing, it should be able to describe the external behaviors of protocols precisely, completely and unambiguously but should not complicate the parser. Estelle contains some features which are not necessary for the conformance testing based on the ETS+ASN.l formalism. TESTGEN generates test suites for protocols based on a single extended finite state machine representation of protocols. Estelle.Y is then defined as an Estelle variation to support only one module. The Estelle language constructs for specifying interactions between different modules and the mechanism for creating instances for the modules are not supported by Estelle.Y. In an Estelle specification, the data types of protocol variables and constants as well as SPs and PDUs are specified in Pascal. We use Pascal to describe the data types of protocol variables and constants in Estelle.Y specification. The data structure and the data type of the SPs and PDUs and their parameters CHAPTER 3. ESTELLE.Y AND PROTOCOL DATA STRUCTURE (PDS) 24 are defined in ASN.l . The SP parameters or PDU fields defined in ASN.l may be referenced in Estelle.Y specification through a dot notation mechanism similar to that a structure or record field is referenced in programming languages C or Pascal. We consider timers as an important part of a protocol. Timers are also key issues for the conformance testing. Estelle does not provide explicit language support to specify timers. Estelle.Y supports timers explicitly. 3.2.3 Estelle.Y definition The conceptual model The ETS+ASN.l formalism defined in section 2.1 is the conceptual model which defines the semantics of an Estelle.Y specification. The syntax of an Estelle.Y specification is similar to that of an Estelle specification of the single module. The set of state Q is represented by control states, data states, constants and timers. Control states are a set of control values associated with the special identifier STATE. The data states are represented by values of variables, constants and the status of timers. These ETS elements are declared in the declaration part. qinu is defined in the initialization part. The observable behaviors of modules specified in terms of the set of events E are the effect of the module activity as described within an module body definition. The set of transition —• is specified in the state — transition part. Each transition is syntactically composed of two parts: a clause group and a transition block. A clause group defines the enabling predicate of a transition. The clauses also define the control state from which a transition may take place and specify the next control state following the transition's execution. The events associated with a transition are also defined by the clauses. The transition block defines the action function to be executed by the transition. Syntax and semantics The syntax of Estelle.Y is defined in Backus-Naur Form (BNF) notation. The complete BNF definition of Estelle.Y is in appendix A. In its present stage, an Estelle.Y specification is a single CHAPTER 3. ESTELLE.Y AND PROTOCOL DATA STRUCTURE (PDS) 25 module definition. It contains three major parts: the declaration part, initialization part and the state-transition part. The protocol state machine is initialized in the initialization part. The state-transition part is to define the transitions of the protocol state machine. • Declaration part The syntax of Estelle.Y variable and constant declarations are similar to those in Pascal. EsteUe.Y supports three data types for the variables and constants: integer, boolean and character string. Timeout values are declared for Timers. PCOs are declared for ISPs and OSPs, and PDUs in case no embedding SPs are declared for PDUs. Embedding SPs or PCOs are declared for PDUs. Figure 3.1 is an example of the declaration part. • Initialization part The initial states of the module are specified by the initialization part. The variables and timers may be assigned their initial values in this part. They will be assigned default values if not explicitly initialized. • State-transition definition part The transitions are specified in this part. Figure 3.3 gives an example of a transition declaration. The clause group (FROM, To, WHEN, PROVIDED, etc) specify the present state and the next state of a transition, sending and receiving of the SPs, the priority and the enabling predicate. The enabling predicate is specified in Pascal as a boolean expression. The action function is specified as a group of Pascal statements. Four Pascal statements are supported. They are the assignment statement, if statement, while statement and compound statement. Moreover a set of timer statements are supported to specify the operations on timers. A transition is firable if the enabling predicate is satisfied, an ISP, in which PDU may be embedded, is received and the protocol is in the right control state. A transition can fire only if it is firable and it has the highest priority among the firable transitions. CHAPTER 3. ESTELLE.Y AND PROTOCOL DATA STRUCTURE (PDS) 26 Specification FDDI_l_mac; CONST yes = true: boolean; high = 20: int; NULL.STR = "": char.str; VAR Ring.Operational: boolean; Token_class: i n t ; frame.INFO: char_str; ISP PhUnitDatalndication mac.phy; OSP PhUnitDataRequest mac.phy; PDU Frame sent.in PhUnitDataRequest, recv_in PhUnitDatalndication; TIMER TVX 2350; STATE Rx.data, Ck.frame; Figure 3.1: Example of the declaration part INITIALIZATION To Rx.data begin Ring_Operational := true; Token_class := 1; frame.INFO := ""; end; Figure 3.2: Example of the initialization part CHAPTER 3. ESTELLE.Y AND PROTOCOL DATA STRUCTURE (PDS) 27 TRANS FROM Rx.data TO Rx.data WHEN PhUnitDatalndication PROVIDED (PhUnitDatalndication.phlndication = I) and (not Reset(TVX)) PRIORITY high OUTPUT PhUnitDataRequest BEGIN Reset(TVX); Start(TVX); PhUnitDataRequest.phRequest := I; END; Figure 3.3: Example of a transition declaration in the state-transition part Language extension for timers Estelle.Y provides explicit language supports for the specification of timers. Timer expressions reflecting the current status of a timer are also supported. The timer expressions are: • RESET(timer-name), • STARTED(timer-name), • STOPPED(timer-name) and • READ(timer-name). The first three are boolean expressions. The last one gives the current value of a timer. Four timer statements are supported to specify the operations on timers. They are • RESET(timer-name), • START(timer-name), CHAPTER 3. ESTELLE. Y AND PROTOCOL DATA STRUCTURE (PDS) 28 • STOP(timer-name) and • SET(timer-name, expression). A value may be assigned to a timer through SET statement. ASN.l subset We adopt a subset of the ASN.l notation defined in [ISO-8824] to specify the data structures of the protocol service primitives, protocol data units and their parameters. The basic ASN.l type notation defined in Section 1 and Section 2 of [ISO-8824] is chosen as the ASN.l subset for TESTGEN. The SPs, PDUs and parameters of a protocol are specified in ASN.l in a separate file but they may be referenced by the Estelle.Y specification of the protocol. The SP and PDU parameters are represented by dot notation mechanism in an Estelle.Y specification as the following: < SPname > {. < parametername >}+ or < PDUname > {. < parametername >}+. The parameters may be referenced in an enabling predicate or in some statements of an action function where the protocol variables may be referenced. Figure 3.4 is an excerpt of the ASN.l specification of SPs of FDDI MAC protocol. 3.2.4 Estelle.Y versus Estelle Estelle.Y is basically a single module Estelle. The process of transforming an Estelle specifica-tion to an Estelle.Y specification is similar to the normalization process in [Sari-89] and hence is feasible. Two major transformations are required. The multiple modules in Estelle specification must be integrated into a single module and some of the statements e.g., case statement, delay statement must be replaced. The SPs and PDUs are specified in Pascal in an Estelle specification and must be specified in ASN.l in the Estelle.Y/ASN.l specification. This transformation is CHAPTER 3. ESTELLE.Y AND PROTOCOL DATA STRUCTURE (PDS) 29 FDDIMac DEFINITIONS ::= BEGIN PhyToMacAsp ::= CHOICE { PhUnitDataRequest, PhUnit Dat alndicat ion, PhUnitDataStatusIndication, Phlnvalidlndication > PhUnitDataRequest ::= SEQUENCE { phRequest Symbol > Figure 3.4: Example of ASN.l definition of protocol SPs CHAPTER 3. ESTELLE. Y AND PROTOCOL DATA STRUCTURE (PDS) 30 straightforward since ASN.l describe abstract data types in a way similar to Pascal. 3.3 Protocol data structure In order to generate T T C N test suites automatically from the formal specification of protocols, the information specified in the formal specification must be accessible to the test generation engine. The protocol data structure (PDS) is designed to represent the formal protocol speci-fications based on ETS+ASN.l formalism in a machine accessible form. The protocol information saved in the PDS will be directly used for the subtour identification process which is the key process of the automatic test suite generation. In other words, the TSG is completely based on the protocol information in the PDS. Therefore it is very important to ensure that the PDS correctly represents the information of the protocol specifications so that test suites can be generated correctly. It is also important that the PDS is easy to be accessed by the test generation engine. To facilitate the identification of subtours, the protocol information in the PDS is organized as an internal representation of the protocol state machine graph. Although the PDS is particularly designed for TESTGEN, it may also be used for other applications such as protocol validation tools. A protocol data structure representing a complete, real world communication protocol could be very large and complex. To make the accessing and management easier, we organize the protocol information in a way similar to that the database uses to organize the data. 3.3.1 Representation of protocol descriptors Based on the ETS+ASN.l formalism, a protocol is formally described in terms of several sets of components, i.e. states, transitions, variables, constants, input service primitives, output service primitives, protocol data units and timers. We call these components protocol descriptors. In an Estelle.Y specification, some sets of the protocol descriptors are further described in terms of other sets of protocol descriptors. For instance, transitions may be described in terms of action functions, enabling predicates, expressions, statements, SP and PDU parameters etc. In the PDS, a structure (or type) is defined for each set of protocol descriptors in the PDS. CHAPTER 3. ESTELLE. Y AND PROTOCOL DATA STRUCTURE (PDS) 31 Each of the protocol descriptors specified in the specification is then represented as an instance of a specific structure. For example, a state is an instance of structure STATE defined for states. The definition of the structures are given in the following subsections. 3.3,2 Protocol descriptor access The main part of the PDS consists of pointer arrays. The pointers of each array point to a certain type of protocol descriptors. Each descriptor can then be accessed with its type (array name) and its key (array subscript) being known through the main structure. Figure 3.5 illustrates the main data structure of the PDS. PPDS PDS pstate[] ptrans[] ptstmt[] states transitions statements Figure 3.5: The main data structure of PDS The C structure definition of the main structure of PDS is shown in figure 3.6. CHAPTER 3. ESTELLE.Y AND PROTOCOL DATA STRUCTURE (PDS) 32 typedef struct { int i n i t _ s t a t e ; int nb_of.states; PSTATE pstate[MAXSTATES - 1 ] ; int nb_of.transitions; PTRANS ptrans[MAXTRANSITIONS - 1] ; int nb_of.variables; PVAR pvar[MAXVARIABLES - 1 ] ; int nb_of.constants; PCONST pconst[MAXCONSTANTS - 1 ] ; int nb.of_isps; PISP pispCMAXISPS - 1 ] ; int nb.of_osps; POSP posp[MAXOSPS - 1] ; int nb.of_pdus; PPDU ppdu[HAXPDUS - 1] ; int nb.of.timers; PTIMER ptimer[HAXTIMERS - 1 ] ; int nb.of_efns; PEFN pefn[MAXEFNS - 1 ] ; int nb.of.spparms; PSPPARM pspparmCMAXSPPARMS - 1] ; > PDS, *PPDS; > Figure 3.6: C structure definition of PDS CHAPTER 3. ESTELLE.Y AND PROTOCOL DATA STRUCTURE (PDS) 33 The field initstate is the key to the initial control state of the protocol. PSTATE, PTRANS, PVAR, PCONST, PISP, POSP, PTIMER, PEFN, PSPPARM, ... are pointers to the structure STATE, TRANS, VAR, CONST, ISP, OSP, TIMER, AFN, SPPARM, respectively. The number of protocol descriptors used to describe a specific protocol is not known at the compile time. The C type definition of the PDS requires a fixed length of the pointer arrays. So a set of MAX... constants has to be introduced to indicate the maximal number of descriptors allowed. The n6_o/_... fields indicate the actual total number of protocol descriptors of each set for a specific protocol. The pointer arrays pointing to variables, constants and the SP and PDU parameters may be considered as some kinds of symbol tables as often used in the compiler constructions. The relations between different descriptors are normally represented by links between the descriptors. Two possible approaches are considered. The first is that protocol descriptors may simply be linked directly by a pointer from one to another. The second is that the descriptors are indirectly linked together via the main data structure. In this way, a protocol descriptor indirectly "points" to other descriptors by remembering the types and keys of those descriptors and looking for physical pointers to them through the main data structure. Consider the complexity of a real-life protocol, the advantage of the latter is evident. Each set of protocol descriptors has its own index stored in the main structure so that the descriptors are easy to be accessed. The information of a protocol in the PDS is well-organized and therefore is easy to be accessed for TSG and the other applications. If a set of protocol descriptors is specified in ASN.l it stores a pointer to the data structure that used to represent the ASN.l specification. 3.3.3 PDS data structure definition The two major components of an ETS based protocol specification are states and transitions. The PDS is organized as a Finite State Machine (FSM) that has been extended to accommodate the following protocol descriptors other than states and transitions: • ISPs and OSPs CHAPTER 3. ESTELLE. Y AND PROTOCOL DATA STRUCTURE (PDS) 34 • PDUs • Protocol variables and constants 9 Protocol Timers • Enabling conditions of transitions • Actions associated with transitions The structure S T A T E , T R A N S , ISP, OSP, P D U , V A R , C O N S T , T I M E R , E X P R (for en-abling conditions) and A F N are defined for the corresponding sets of protocol descriptors. The definitions of S T A T E , T R A N S , V A R , C O N S T and T I M E R are given in this subsection; ISP, OSP and P D U as well as S P P A R M are defined in next subsection. The definition of E X P R and A F N are left for Chapter 4. S T A T E as illustrated in Figure 3.7 is defined to represent the control states of a protocol. • key field is a subscript of the pstate array. The pointer to this state is stored in pstate[key}. • name is the state's name. • numb.of.trans indicates the total number of transitions applicable to this state. • trans.key array stores the keys to the transitions that are applicable to this state. Consequently, one will be able to access all the transitions applicable to a given state by looking up the pointer to a transition correspondent to the transition key stored in the trans.key array of applicable transitions. The purpose of storing this information in states is to facilitate the subtour identification process. The key and name fields are also contained in the structure definitions of all other sets of protocol descriptors and also used in the similar way. They will be referred to without further explains later on. T R A N S is defined as depicted in Figure 3.8 to represent transitions. CHAPTER 3. ESTELLE.Y AND PROTOCOL DATA STRUCTURE (PDS) 35 • fromstate and to.state are keys to the present state and the next state of a transition. • isp, ipdu, osp, osp2, opdu and opdu2 are keys to ISPs, OSPs or PDUs associated with a transition. Estelle.Y allows two output SPs or PDUs within a single transition. (This is why osp2 and opdu2 are included.) • epred and afn are keys to the enabling predicate and the action function associated with a transition. • priority field indicates the priority of a transition. STATE key name numb_of_trans irans_key[0] trans_key[MAXTRANS - 1] ! Constraints ! i i Figure 3.7: STATE definition VAR and C O N S T are defined as shown in Figure 3.9. The type field indicates the data type of a variable or constant. Three supported data types are boolean, integer and character string. Boolean has two possible values, true and false; integer type is a four-byte integer; and character string is the same as defined in C. Fields int-value, booLvalue and charstr store the value of a constant. An enabling predicate (EPRED) is a boolean expression so that the epred field of a tran-sition actually stores the key to an expression. EXPR is defined to represent expressions as well as enabling predicates. Both an action function ( A F N ) and a compound statement ( C S T M T ) consist of a group of statements. The definitions of AFN and CSTMT are exactly the same. However, they are int char * int int CHAPTER 3. ESTELLE. Y AND PROTOCOL DATA STRUCTURE (PDS) 36 TRANS int key char * name int from_sute int to_state int Up int osp int osp2 int ipdu int opdu int opdu2 int epred int efn int priority t constraints Figure 3.8: T R A N S definition CHAPTER 3. ESTELLE.Y AND PROTOCOL DATA STRUCTURE (PDS) 37 VAR int key char * name TYPE type Constraints CONST key name type int_value boolean_value char_str i Constraints ! i i Figure 3.9: VAR and CONST definitions defined as two independent types since they are conceptually different. Figure 3.10 is the TIMER structure for the representation of timers. timeouLvalue is the time-out value of the timer. The TIME_UNIT is of integer type and the time unit is microsecond. TIMER key timeout_value i Constraints ! i i Figure 3.10: TIMER definition int char * TYPE int BOOLEAN char * int char * TIME_UNIT The lower level structures of expressions (EXPR) and statements (IFSTMT, CSTMT, AFN, ...) are defined in Chapter 4 because they are closely related to the design of the TESTGEN parser. CHAPTER 3. ESTELLE.Y AND PROTOCOL DATA STRUCTURE (PDS) 38 Figure 3.11 illustrates the relations between all the components of the PDS. Note that some sets of descriptors are recursively defined by the same type of descriptors, e.g. an expression may be defined by a set of subexpressions. An enabling predicate (EPRED) is a boolean expression and the field of a transition actually stores the key to an expression. In figure 3.11 the dotted arrows from EPRED to EXPR indicates this type of relation. STATE TRANS Figure 3.11: The relation diagram of the PDS components CHAPTER 3. ESTELLE. Y AND PROTOCOL DATA STRUCTURE (PDS) 39 Finally, some test generation and parameter variation constraints may be imposed on some sets of the descriptors. The "constraints" fields are included in the structure definitions of those sets to store the constraints. The reader may refer to [TR-90-x] for more detailed description of the PDS. 3.3.4 A S N . l t y p e tree A set of data types defined in ASN.l for a particular application is called an abstract syntax. Following this definition, the ASN.l specification of SPs and PDUs of a specific protocol is an abstract syntax. The ASN.l type tree [Sample-90] is an internal data structure that contains all the structuring and naming information of an ASN.l abstract syntax. The structure of input service primitives, output service primitives and protocol data units are required to be specified in ASN.l. To allow the ASN.l information to be accessed from the PDS, these protocol descriptors have pointers to the ASN.l type tree in which the ASN.l information is stored. We use ASN.l type tree as the internal representation of the the input service primitives, output service primitives and protocol data units and parameters in ASN.l part specification. The ASN.l type tree created by the ASN.l parser is a tree of template ENODEs (T_ENODEs). Figure 3.12 is the C structure definition of a template enode. Each T.ENODE represents one layer of the structure/typing of ASN.l types. Each TJENODE holds information that describes an ASN.l type. The components of a type definition (also called children of the type definition) are linked as a list. The pointer child of the type definition node points to the head node of the list of its children. The pointer next of the type definition points to one of its siblings. The siblings and the type definition itself are children of a higher layer type definition. A simple example of an ASN.l type definition and its type tree is illustrated in Figure 3.13 and Figure 3.14. Readers may refer to [Sample-90] for more details. ISP structure is defined as in Figure 3.15. « PCO is the name of the Point of Control and Observation at which the SP or PDU is exchanged by te IUT [ISO-9646]. CHAPTER 3. ESTELLE.Y AND PROTOCOL DATA STRUCTURE (PDS) 40 typedef struct T.ENODE { TAG univTag; V_EN0DE_PTR tag; SUBTYPE.PTR subtypes; T.ENODE.PTR next; / * univ type tag ( i f not extra tag) * / / * actual tag to use for enc/decode * / / * any subtyping info for t h i s type * / / * next e l t pts to s i b l i n g * / V.ENODE.PTR union •c T_EN0DE_PTR T_EN0DE_PTR T_EN0DE_PTR } a; namedElmts; / * named num/bits I enumerated defs * / / * save some space with a union on mutually excl elmts * / c h i l d ; / * c h i l d elmts i f constructed * / choiceElmts; / * elements of a choice type * / selectionType; / * type se lect ion is from * / short typeFlags; BYTE sysFlags; V.ENODE.PTR defau l tVal ; IMPORT.ELMT.PTR importRef; char* name; char* typeName; / * type a t t r i b f lags: 2 bytes * / / * note: V.ENODE's use some of these * / * ie chi ldren part of other type def * / / * i f not n u l l , imported type def ref* / / * f i e l d name i f component else*/ / * or ig defined type name i f redefined*/ / * defined type name * / } T.ENODE; Figure 3.12: The data structure of template ENODE CHAPTER 3. ESTELLE. Y AND PROTOCOL DATA STRUCTURE (PDS) 41 PDUDEFINrnONS::= BEGIN — a simple type defined in ASN.l for the use as an example PduType ::= SEQUENCE { infoLength INTEGER, info Characters tring OPTIONAL, status BOOLEAN END Figure 3.13: ASN.l type example SEQUENCE IK PAiTjrpc type: typem field mane: »<: UNIVERSAL 16 •milni—: type: INTEGER type Dime; fieldname: infoLength U | : UNIVERSAL 2 innbulBt: libuing: • 4 -type: Chine tcr Str type name: field name: info lag: UNIVERSAL 19 attributes: OPTIONAL nbiling: -componenra: typo: BOOLEAN type name: fieldname: status tag: UNIVERSAL 1 attributes: sibiHng: -Figure 3.14: ASN.l type tree of PduType CHAPTER 3. ESTELLE.Y AND PROTOCOL DATA STRUCTURE (PDS) 42 ISP key name PCO isp_typetree_ptr nb_ofj>du» pdu_key[0] pdu_key[nb_of_pdus -1] | Constraints ! ! I Figure 3.15: ISP definition • ispjypetree-ptr is the pointer to an ASN.l type tree that holds the ASN.l definition of this ISP. The description of ASN.l type tree is given in next subsection. • nb.of-pdus is the number of different types of PDUs that can be encoded in an ISP. • pdu^key is an array of keys to the PDUs that can be encoded in this input service primitive. OSP is the same as ISP except that in OSP the pointer to ASN.l type subtree is named ospJLypetreejptr instead of ispj,ypetreejptr. PDU is defined to have following fields: • key and name • sentJn and recvJn are the keys to the service primitives in which the PDU can be sent or received. • pdu-typetree-ptr is a pointer to the ASN.l type tree which holds the ASN.l specification of the PDU. SPPARM structure shown in Figure 3.16 is designed to represent the SP or PDU pa-rameters. The parameters can be referenced or used just like a variable so that we treat the parameters as protocol descriptors and represent them in a way similar to that a variable is int char * char * T_ENODE_PTR int int CHAPTER 3. ESTELLE. Y AND PROTOCOL DATA STRUCTURE (PDS) 43 represented in the PDS. On the other hand, for test suite generation, the TSG constraints are imposed on each of the parameters so that SPPARM structure is also necessary for storing of the constraints. SPPARM int key char * name SPTYPE 'P'yp* int "Pkey T_ENODE_PTR t_enode_ptr i i i i i i Figure 3.16: SPPARM definition 3.4 Summary An Estelle.Y specification is more concise and more readable than an Estelle Normal Form specification [Sari-89] in that Estelle.Y supports conditional statement and loop statement (extra transitions are created due to the lack of conditional statements and loop statements in Estelle Normal Form). In addition, Estelle.Y supports timers explicitly to facilitate the testing of timers and supports ASN.l directly. Estelle.Y is shown to be a good intermediate formal specification mechanism for automatic test generation or protocol validations. The PDS can be easily extended to accommodate the protocol specifications with multiple modules. The current design of PDS can be used as a basic component of a composite PDS which is a higher level data structure that represents the hierarchical structure of multiple modules. The major deficiency of PDS is due to the fact that the memory space is statically allocated for its main structure. The number of protocol descriptors varies with different protocols while the set of MAX... constants are fixed. When the specification of a specific protocol is being parsed, the number of protocol descriptors generated by the parser may exceed the MAX... CHAPTER 3. ESTELLE. Y AND PROTOCOL DATA STRUCTURE (PDS) 44 limit, even though we can define the MAX... constants large enough such that in normal cases the limit may not be exceeded. In case of limits being exceeded, users are asked to modify the set of MAX... constants defined some of the C source files. To avoid this deficiency, we can make use of a dynamic main data structure for PDS in which we use a dynamically allocated pointer list instead of the static pointer array. However, this dynamic data structure would be more complex and could require more accessing time. The current limits are set as follows: MAXSTATES = 40 MAXTRANSITIONS = 150 MAXVARIABLES = 100 MAXC0NSTANTS = 100 MAXISPS = 20 MAX0SPS = 20 MAXPDUS = 20 MAXTIMERS = 20 MAXTEXPRESSIONS = 100 MAXEXPRESSIONS = 1200 MAXSPPARMS = 100 MAXSTMTS = 100 MAXIFSTMTS = 100 MAXWSTMTS = 100 MAXASTMTS = 400 MAXTSTMTS = 100 MAXCSTMTS 100 MAXAFNS = 150 Chapter 4 T E S T G E N parser In order to run the test suite generation applications, the formal Estelle.Y/ASN.l specifica-tion must be translated into PDS. The internal PDS representation of the ETS+ASN.l of a communication protocol is generally so complex that the manually generation (hard wired C code) of the PDS for each specific protocol would be too error prone and too labor intensive. On the other hand, the subtour identification and TTCN test suite generation processes of the TESTGEN are totally based on the protocol information saved in the PDS. In order to generate test suites properly, we must ensure the PDS to be generated correctly from the specification. A parser which can generate PDS from formal specifications is therefore required. We developed the TESTGEN parser to parse the Estelle.Y/ASN.l specifications to the PDS. The parser is developed in C on SUN workstations with about 8000 lines of C code. This chapter discusses the issues of design and development of the TESTGEN parser. Sec-tion 1 is about the design issues. The implementation is discussed in Section 2. The testing of the TESTGEN parser is presented in the last section. 4.1 Design considerations There are several possible approaches we can use to develop the TESTGEN parser. One way is to develop a parser that can recognize both Estelle.Y and ASN.l languages. Such a parser can parse and translate the Estelle.Y/ASN.l specification of protocols into PDS. However, a more 45 CHAPTER 4. TESTGEN PARSER 46 efficient way is to make use of the existing Estelle and ASN.l tools. A considerable amount of work has been done in the development of Estelle and ASN.l tools [Neu-90] [Sample-90]. The available tools such as Estelle-C compiler [Vuong-88] and ASN.l-C compiler [Neu-90] generate C codes from an Estelle or ASN.l specification. These compiler tools are not suitable for test suite generation because protocol choices information and nondeterminisms are lost during compilation [Vuong-91-1] so that they can not be used for development of TESTGEN. An ASN.l parser is presented in [Sample-90]. It can parse an ASN.l specification to an internal data structure that holds the syntactic and semantic information of the ASN.l specifi-cation. It is designed for conformance testing of application layer protocols. The ASN.l parser generates an internal data structure, the ASN.l type tree, from the ASN.l specifications. We develop a parser, the TESTGEN parser, to parse the Estelle.Y/ASN.l specification of protocols into the PDS. The ASN.l parser of [Sample-90] is then used to parse the ASN.l specifi-cation to ASN.l type tree. The generated ASN.l type tree is linked to the PDS by TESTGEN parser when the Estelle.Y specification is being parsed. As the result, a PDS that includes both Estelle.Y and ASN.l protocol information can be generated from an Estelle.Y/ASN.l specification. 4.1.1 A S N . l parser The ASN.l parser is designed for testing of OSI application layer protocols. It is developed by using UNIX Lex/Yacc tools. It produces the ASN.l type tree from ASN.l specifications. The ASN.l type tree is written to a file as an relinkable block after it is generated. The main use of this tool is to build loadable ASN.l type trees offline, which can subsequently be loaded during the execution of the protocol tester [Sample-90]. The ASN.l parser provides a subroutine which can reload the ASN.l type tree written in a file. The reloadability of the ASN.l type tree provided by the ASN.l parser facilitates the in-corporation of ASN.l type tree into PDS generated by TESTGEN parser. An intuitive way of the incorporation is to generate two data structures both on line and CHAPTER 4. TESTGEN PARSER 47 then integrate them. However, considerable difficulties exist. The two parsers are developed independently and the naming conflicts of the subroutines and symbolic constants between the two parsers are difficult to be resolved, especially when they are developed by using Lex/Yacc tools and some machine-generated codes are used. On the other hand, we do not need to handle the naming conflicts of subroutines between two parsers if one of the data structure is generated off line. Figure 4.1 illustrates the configuration of TESTGEN parser. EsteUcY Protocol Specification ASN.l SPs and PDUs Spedficatiion Figure 4.1: TESTGEN parser configuration 4.1.2 Lex/Yacc tools The TESTGEN parser is implemented in C under the UNFX operating system. UNIX lex/yacc tools are designed to facilitate the construction of the front end compilers, i.e. the parser. We make use of these tools to implement the lexical analyzer and the TESTGEN parser itself. Yacc input is produced based on the BNF rules of Estelle.Y. Figure 4.2 depicts the process of TESTGEN parser generation. CHAPTER 4. TESTGEN PARSER 48 Estelle.Y LEX/YACC source code Figure 4.2: TESTGEN Parser generation 4.1.3 Abstract syntax tree The parse tree is a popular intermediate representation form of source programs used for con-struction of many compilers. Given the BNF definition of a grammar, lex/yacc tools can construct the parse trees of source programs easily. In our application, lex/yacc tools are used to construct syntax trees, which are similar to parse trees and store the syntactical information of the Pascal statements and expressions in Estelle.Y/ASN.l specification. In a syntax tree, the control constructs of statements are represented as tree nodes. Figure 4.3a — c provides three examples of the syntax trees for statements. An assignment statement is depicted in Figure 4.3a. v could be a variable or a parameter which is the left-hand side operant of the assignment statement. The subtree e describes the expression of the assignment statement. Figure 4.36 illustrates an if statement. The subtree e represents the condition of the if statement. The subtree si and s2 describe the statements to be executed if e is true and false, respectively. Figure 4.3c illustrates a while loop. The loop control structure is represented by a single node. The subtree e describes the boolean expression of the loop and the subtree 5 represents the body of the loop. IFSTMT, WSTMT and ASTMT are defined accordingly to represent the three Pascal statements supported by TESTGEN. The definition of IFSTMT for if statements as shown in Figure 4.4. They are actually the definition of the node structures of syntax trees. Similarly, the expressions are also represented by syntax trees. EXPR (also as EPRED) is defined as in Figure 4.5. CHAPTER 4. TESTGEN PARSER 49 si s2 (b) if e then si else s2; WHILE (c) while e do s; Figure 4.3: Examples of syntax trees IFSTMT int key char • name int bool_expr STKIND stmtjrind int stmt STKIND else_stmt_kind int else_stmt Constraints Figure 4.4: IFSTMT definition CHAPTER 4. TESTGEN PARSER 50 PEXPR "1 EXPR key lcftjrind left operator rightjdnd right ! Constraints ! i i Figure 4.5: EXPR definition 4.2 Implementation A protocol to be tested is specified in Estelle.Y. The ISPs, OSPs and PDUs and their parameters of a protocol are defined in ASN.l. The ASN.l specification is parsed to ASN.l type tree by the ASN.l parser. Moreover, the ISPs, OSPs and PDUs must be declared in the Estelle.Y specification of the protocol. The parameters may be referenced in the Estelle.Y specification as well. The TESTGEN parser first reloads the ASN.l type tree; then calls the parsing function to parse the Estelle.Y specification of the protocol to the PDS. In the mean time, the ASN.l type tree is linked to PDS. The TESTGEN parser set pointers to the ASN.l type tree when the ISPs, OSPs and PDUs and parameters are created in the PDS. Protocol variables and constants, ISPs, OSPs, PDUs, timers and states must be declared in the declaration part of the Estelle.Y specification. The TESTGEN parser creates appropriate types of protocol descriptors in the PDS when the declaration part is analyzed. 4.2.1 Declaration part As mentioned before, an Estelle.Y specification consists of three parts: declaration part, ini-tialization part and state-transition part. The declaration part is parsed first. The TESTGEN parser creats all declared variables, constants, ISPs, OSPs, PDUs, timers and states in the PDS int char* KIND int OPERATOR KIND Int CHAPTER 4. TESTGEN PARSER 51 when the declaration part is parsed. The transJsey\] field of the states is empty at this stage and will be filled when the state-transition part of the specification is parsed. The appropriate default initial values are stored in VAR instances and TIMER instances created. ISPs, OSPs and PDUs When an input service primitive declaration is recognized, the parser creats an instance of ISP structure for it. Moreover, the TESTGEN parser looks for its ASN.l definition in the ASN.l type tree. If the definition is found, the pointer to the subtree holding that definition will be saved in the ...Jypetree.ptr field of the created ISP instance. The OSP and PDU declarations are treated similarly. SP and PDU parameters The SP or PDU parameters are not declared in an Estelle.Y specification. However, the param-eters may be referenced and be used like a variable. Even though some of the parameters may not be referenced at all, some of the test suite generation constraints imposed on them must still be saved for TSG process. A instance of SPPARM must therefore be created for each of the ISP, OSP or PDU parameters when the ISP, OSP or PDU declaration is being parsed. The TESTGEN parser searches for the ASN.l type tree for the definitions of each of the parameters . The pointers to the T_ENODEs of the ASN.l type tree which store the type information of the parameters will be saved in a created parameter instance. Names of the parameters are formed based on dot notation. Timers All timers must be declared and there are instances of TIMER in the PDS created for each of them. The declared time-out values are stored in the corresponding instances. Timer statements and timer expressions are treated as ordinary Pascal statements and expressions. They are represented as instances of TSTMT and TEXPR respectively. Timer CHAPTER 4. TESTGEN PARSER 52 expressions have boolean values and can be evaluated as boolean expressions. 4.2.2 Initialization part The TESTGEN parser sets default initial values for all variables, parameters and timers created in the PDS if they are not explicitly initialized. The default value is 0 for those of integer type, false for those boolean type and empty string for those of character string type. If these protocol descriptors are explicitly initialized in this part, the default initial values are ignored. The initial state may be assigned in this part. The state pointed by pstate[0] is assumed as the initial state otherwise. 4.2.3 State-transition part The state-transition part consists of a group of transition definitions. The keys of transitions applicable to a state are stored in the transJzeyW field of that state when transitions are created in the PDS. The TESTGEN parser creates a transition in the PDS when a transition definition is recognized. A transition is specified in terms of states, ISPs, OSPs, PDUs, EPREDs and AFN. The referenced states, ISP, OSP(s) and PDU(s) must have been created in the PDS since they must be declared in the declaration part. Other components such as the AFN and EPRED and their components such as expressions and statements are created when an action function or an enabling predicate is being parsed. The links to the referenced protocol descriptors are established by storing the types and keys to them. The syntax trees of the action function (a set of Pascal or Timer statements) and the enabling predicate (a boolean expression) will be constructed. Whenever and the basic components such as variables, constants, parameters are referenced, their types and keys are stored by others. The timer expressions and timer statements are also created if they appear in an action function. The leaf nodes of a syntax tree may be variables, constants, parameters and timer constructs. CHAPTER 4. TESTGEN PARSER 53 4.3 Testing As mentioned before, the correctness of the PDS is very crucial to test suite generation using TESTGEN. The TESTGEN parser itself is designed carefully to prevent inconsistent infor-mation from being stored in the PDS. The nb.of.... fields in the main structure of the PDS record the number of protocol descriptors of each set. The values of these fields can only be changed through a subroutine. These fields are initialized to be Os. For example, when a state is created, a key is assigned to it through the subroutine. The key is equal to the current value of the nb-of„states field and the value of that field increments immediately after the key is as-signed. Finally, the pointer pstatefkeyj points to the created state. In addition, two verification mechanisms are developed to verify the correctness of a PDS generated. 4.3.1 Printing PDS The PDS of a real life protocol could be very large and complex. Since TESTGEN is an interactive TSG tool, sometimes people may want to check a particular part (e.g. a particular state) of the PDS generated by the parser. It is more convenient to allow the user check information displayed on the screen than look for the information in the source specification file. A set of printing functions are provided for users to check the information stored in the PDS and make sure the PDS is consistent with the original specification. For example, users may use these printing functions to check if each protocol descriptors are correctly linked to other protocol descriptors by looking at the keys and types stored in these descriptors; or to check if the syntax tree is properly constructed by looking at the expression or statement information stored in the tree. In order to verify the correctness of protocol information stored in the PDS, we can randomly pick up some protocol descriptors such as transitions and print them out using a set of printing functions. The printed protocol descriptors are then compared to those specified in the protocol specification. CHAPTER 4. TESTGEN PARSER 54 4.3.2 Consistency checking of P D S In addition to the printing functions, a set of consistency checking functions are developed to check the consistency of the PDS after it is generated. The consistency requirements on which the consistency checking functions are designed are as follow. • For each set of protocol descriptors, the value of its n6j»/_... field should not be greater than the corresponding MAX... constant. For example: ppds -f nb.ofMates < MAX STATES ppds -f nb-ofJransitions < MAXTRANSITIONS • For each protocol descriptor, the key stored in the key field must be equal to the index of the pointer to that descriptor. Therefore, Vi, 0 < i < ppds —> nbjojstates =>• ppds —> pstate[i] —• key = i Vi,0 < i < ppds —• nb-of' ^ transitions => ppds —> ptrans[i] —+ key = i • Keys of any set of descriptors stored in any field of a protocol descriptor should not be greater than the number of descriptors of the set, namely Vi, 0 < i < ppds —> nb.ofJrans 1) 0 < ppds —>• ptrans[i] -* from^st < ppds —• nb^ofstates, and 2) 0 < ppds —* ptrans[i] —*• tost < ppds —+ nb^of states, and 3) 0 < ppds —• ptrans[i] —»isp < ppds— > nb-ofjsps, and ... • The type field of any constants or variables can only be the defined data types. Vi, 0 < i < ppds —r nb-of .variables =>: 1) ppds -»• pvar[i] -> type = BOOLJTYP, or 2) ppds -> pvar[i] -* type = INT.TYP, or 3) ppds pvar[i] -> type = CHARJSTR.TYP, where BOOLITYP, INT STY P and CHARJSTRSTYP are the three legal types. CHAPTER 4. TESTGEN PARSER 55 • The timeout values of a timer must be a non-negative integer. • The leftJcind and right Jzind field and the operator field of an expression should store only those defined kinds and operators, i.e. Vi,0 < i < ppds —*• nb.ofjexprs =>: 1) ppds —• pexpr[i] —* right Jzind = VAR., or 2) ppds —• pexpr[i] —• right Jcind = CONST., or 3) ppds —»• pexpr[i] —> right Jzind = TEX PR., or 4) ppcfa —• pexpr[i] —• rightJtind = PARM_, or b)ppds —> pexpr[i] —• right Jcind = NONE., where VAE_,COiVST_,r/i;XPiE_,PA/iM_ and NONE, are legal kinds. • The stmt Jtind field of action functions should contain only those Pascal statements sup-ported by TESTGEN. The complete set of consistency requirements can be found in Appendix E. Using TESTGEN parser, we parsed FDDI MAC protocol and its services, TPO and LAPB and generated their corresponding PDSs. The consistencies of these PDSs are subsequently checked by the consistency checking functions. Chapter 5 Test generation for the FDDI M A C protocol To verify the viability of the TESTGEN and to study the feasibility of applying the concepts of OSI conformance testing to a high-speed network protocol, we apply TESTGEN to the FDDI MAC protocol to generate a test suite for it. We developed a formal specification of the FDDI MAC protocol in Estelle.Y and ASN.l. The PDS is generated from the formal protocol specification by the parser. A test suite is then generated for the protocol without any human interventions by use of a set of default TSG constraints. However, in order to generate a more comprehensive test suite with reasonable size and fault coverage, we have to tune the default constraints for each specific protocol. An appropriate set of constraints are set through the constraint editor. Finally a test suite will be generated based on the PDS and the TSG constraints. In this chapter, firstly a brief review of the FDDI MAC protocol is presented. The problems with the formal specification of FDDI MAC protocol and the services in Estelle.Y and ASN.l are then discussed. The major problem with the specification is how to produce a single ETS representation of the FDDI MAC protocol. In this chapter, we also show how to combine two extended transition systems into to one with equivalent behaviors. Finally we discuss the issues of tuning TSG constraints and the test suite generation. 56 CHAPTER 5. TEST GENERATION FOR THE FDDI MAC PROTOCOL 57 5.1 F D D I M A C sublayer The FDDI Media Access Control (MAC) layer is the lower sublayer of the Data Link Layer. It is the most important component of the FDDI standard among the four (MAC, PHY, PMD and SMT). MAC standard is the core of the FDDI standard. It distinguishes FDDI from other IEEE LAN standards. FDDI MAC protocol is developed based on the concepts of Token Ring Access Method de-fined in ANSI/IEEE 802.5-1985 while the original concepts have been modified to accommodate the higher FDDI speeds. The protocol is designed to be effective at 100 Mb/s data transmission rate using the Token Ring architecture. The ring monitoring functions of the protocol are fully distributed. The protocol is considered as one of the most complicated media access control schemes [SKO-89]. A brief review of the three major parts of the MAC protocol standard (ANSI X3.139 - 1987) is given in following subsections. 5.1.1 Services Section 3 of the MAC standard specifies the services provided by MAC and the services required by MAC. Three sets of service primitives are defined. For each service primitive, the semantics, the time when it is generated and the effect of being received are specified. Table 1 is a list of the service primitives specified in MAC standard. FDDI MAC provides MAC-to-LLC services for LLC's data transmission via MAC to LLC service primitives. FDDI MAC layer is designed to be compatible with IEEE 802.2 LLC so that it can be used as the super service provider of LLC. As the result, the MAC to LLC services of FDDI are very similar to those of the IEEE 802.5 Token Ring standard. MAC to PHY services provided by PHY layer are used for MAC data transmission. MAC provides services for the SMT's data transmission as well. Through the MAC to SMT services, SMT controls the operation of MAC for purposes of the station management. CHAPTER 5. TEST GENERATION FOR THE FDDI MAC PROTOCOL 58 MAC to LLC: MA.UNITDATA.request MA.UNITDATA.indJcation MAJJNrTDATAJSTATUS.indecation MA_TOKEN.request MAC to PHY: PH.UNITDATA.request PH.UNITDATA.indication PHJJNITDATAJSTATUS.indication PHJNVALID .indication MAC to SMT: SMJvIAJNITIALIZEJROTOCOLj-equest SMJVUJNITIALIZEJROTOCOL.corinrm SM_MA_CONTROL.request SM_MA_STATUSandication SM_MA_UNITDATA.request SMJvlAJJNITDATA.indication SM31A.UNrTDATA_STATUS.indication SM_MA-TOKEN.request Figure 5.1: FDDI MAC service primitives 5.1.2 Facilities This section of the MAC standard specifies the MAC protocol data units, timers and frame counts. Protocol data units The MAC layer processes both PHY layer protocol data units and MAC layer protocol data units. The PHY protocol data unit contains 4 bits of binary data, called a data symbol. Symbols are passed across the MAC to PHY interface via the service primitives. Figure 5.2 illustrates the formats of the two MAC PDUs: Tokens and Frames. Timers Timers are critical parts of the FDDI MAC Timed-Token protocol. MAC uses three timers. The Token-Holding Timer (THT) controls how long the station may transmit asynchronous frames. The Valid-Transmission Timer (TVX) is used to recover from transient ring error situations. The Token-Rotation Timer (TRT) is used to control ring scheduling during normal operation CHAPTER 5. TEST GENERATION FOR THE FDDI MAC PROTOCOL 59 TOKEN PA SD FC ED >=16 2 2 2 FRAME PA SD FC DA SA INFO PCS ED FS »16 2 2 4 or 12 4 or 12 2n 8 1 >=3 PA • Preamble SA - Source Addrou ED - Endinj Dolimitel PC • Prime Control INFO s Information pes „ Prime Check Sequence DA = Detonation Address SD = Starting Delimiter FS = Frame Stuui Figure 5.2: Format of MAC Protocol Data Units and to detect and to recover from serious ring error situations. 5.1.3 Operation The operation of mac protocol is described as several phases in the FDDI mac standard. Frame transmission Upon a request for SDU transmission from LLC, MAC constructs a frame from the SDU by placing the SDU in the INFO field of the frame. The frame (encoded SDU) then remains queued awaiting the receipt of a token that may be used to transmit it. Upon the capture of an appropriate token, the station begins transmitting its queued frame(s) in accordance with the rules of token holding. In response to each data transmission request of LLC, a confirmation will be sent to the LLC after the SDU is transmitted. Token transmission The station releases the token immediately after the transmission of the frame(s) is (are) completed. Frame Stripping Each transmitting station will be responsible for removing from the ring the frames that it originated after being acknowledged by the destination station. Ring scheduling Transmission of normal PDUs on the ring is controlled by a Timed Token Rotation protocol based on the Target Token Rotation Time which is negotiated by all of the stations attached to the ring during the ring initialization process. MAC provides two asynchronous transmission modes by using two kinds of Tokens, nonre-stricted and restricted Token. Ring monitoring The MAC monitoring functions are distributed among all stations on CHAPTER 5. TEST GENERATION FOR THE FDDI MAC PROTOCOL 60 the ring. Claim token process allows all stations to bid for the right to initiate the token and negotiate the target token rotation time. When Claim token process is successfully completed, a station begins initialization process. Beacon process is used to signal all remaining stations that a significant logical break has occurred and to provide diagnosis or other assistance to the restoration process (via SMT). 5.1.4 Structure MAC consists of two cooperating processes, the MAC receiver and the MAC transmitter. The two processes are specified both with text and state diagrams. The MAC receiver receives and validates information from the ring and detects ring errors and failures. The major triggering event to the receiver is the arrival of a symbol via a PH_UNITDATA.indication primitive. The MAC transmitter repeats information from the other stations on the ring, inserts information from its own station into the ring, and cooperates with other stations to coordinate priorities for use of the ring. The major triggering event to the transmitter is the the arrival of a symbol together with any event signals from the receiver. The event signals from the receiver could be the receipt of a token or a frame and others. 5.2 The formal specification of FDDI M A C protocol This subsection discusses the Estelle.Y specification of the FDDI MAC layer protocol defined in the ANSI X3.139-1987 standard. A protocol standard specifies both the observable (external) and non-observable (internal) behaviors of a protocol. Since the ISO test methodology and its black-box test principle are chosen for TESTGEN, only the information relevant to the external behaviors of the FDDI MAC entity are needed to be specified. Test method MAC layer is relatively low-level compared to other layers of OSI reference model. The mac protocol has to deal with symbols passed across the MAC-to-PHY interface via MAC to PHY service primitives. CHAPTER 5. TEST GENERATION FOR THE FDDI MAC PROTOCOL 61 The behaviors of the mac protocol are described in terms of the exchange of MAC PDUs, the MAC to LLC service primitives as well as the MAC to PHY service primitives. However, the abstract properties of the protocol, such as the data transmission, ring schedul-ing and ring monitoring functions are described in terms of the exchange of MAC PDUs and the MAC to LLC service primitives, although MAC PDUs are not exchanged directly with the peer entities but via MAC to PHY service primitives. The protocol behaviors involving MAC to PHY services are mostly internal. The observable behaviors of FDDI mac protocol are determined by the abstract properties of the protocol. If control and observation are specified in terms of ASPs, it will include control and obser-vation of the PDUs carried by those ASPs; but if it is specified solely in terms of PDUs (at layer N) then the underlying ASPs are not considered to be controlled or observed [ISO-9646]. We are not interested in controlling or observing MAC to PHY service primitives since protocol behaviors involving MAC to PHY services are trivial. Also the specification of these protocol behaviors is very tedious. Figure 5.3 depicts the test method that is used to test FDDI MAC. It is conformed to the 9646 standard. Lower Tester PDU decoder/encoder Upper Tester MAC PDUs MAC • • PHY Service Provider Figure 5.3: Testing of FDDI MAC layer CHAPTER 5. TEST GENERATION FOR THE FDDI MAC PROTOCOL 62 We specify only the abstract properties of the FDDI MAC protocol, namely the exchange of frames and tokens between peer MAC entities without concerning the interactions at MAC to PHY interface. 5.2.1 Data part in A S N . l MAC to LLC service primitives, a subset of MAC to SMT service primitives and MAC Protocol Data Units and the data type of their parameters are specified in ASN.l in a separated file. Although ASN.l itself allows more complicated data types, only those supported by TESTGEN should be used to specify the MAC service primitives and PDUs. The specification is straightforward. Normally a service primitive is specified as a SE-QUENCE. The parameters are the components of the SEQUENCE and have data types such as INTEGER, BOOLEAN etc. There are two problems with the data part specification. One problem is that a MAJJNITDATA.request may contains a set of subrequests. Each subrequest has its own set of parameters including the service data unit (SDU) parameter. To serve the request, MAC constructs a set of frames for each subrequest for their SDUs. There exists technical difficulties for TESTGEN to handle this kind of nested service primitives. We solve the problem by assuming that a data request may contain only one subrequest. Same problem exists when specifying SMJVIA.UNITDATA.request. Another difficult point is in the specification of symbols. Some of the MAC PDU fields are defined in terms of symbols in the FDDI MAC standard. There are two kinds of symbols passed across MAC to PHY interface. A data symbol contains 4 bits of binary data, and a control symbol contains 5 code bits. We temporarily use INTEGER type to define both control symbols and data symbols since no bit string type is supported by TESTGEN currently. 5.2.2 Control part in Estelle.Y As mentioned in previous sections, an Estelle.Y specification is basically a single module Estelle specification modeled by an EFSM (or more precisely, a single ETS). In order to specify a pro-CHAPTER 5. TEST GENERATION FOR THE FDDI MAC PROTOCOL 63 tocol in Estelle.Y, we first need to represent the protocol as a single EFSM. For the conformance testing purpose, we also need to decide which aspects of a protocol need to be tested and thus need to be specified. Data transmission The data transmission process of the MAC protocol is characterized by the Token Ring access method. A LLC data request may be received by MAC any time but the data may not be sent out immediately. MAC must wait for the arrival of a special PDU, ie. a token to transmit data. As a consequence, there may be several outstanding data requests queued by MAC before the token is captured. The effect of receiving these data requests (service primitives) can not be observed unless a token (PDU) is captured. The frames constructed from the data requests will be sent out in their received order and data confirmations will be sent to LLC in response to each LLC data request. The existence of outstanding data requests can only be represented by data states (namely Estelle.Y variables in the Estelle.Y specification) in the ETS-based representation of the FDDI MAC protocol. It is natural to use a queue data structure to describe these data states. Unfortunately, a queue data structure is not currently supported by TESTGEN. We therefore simulate queues of limited lengths by using sets of simple variables. Facilities Since Estelle.Y provides explicit language constructs for specifying timers, in both of the decla-ration part and the transition part, the specification of FDDI MAC timers is straightforward. MAC structure As being required by TESTGEN, the FDDI MAC protocol must be represented as a single extended transition system (ETS) and specified as a single module in Estelle.Y. CHAPTER 5. TEST GENERATION FOR THE FDDI MAC PROTOCOL 64 As mentioned in the previous section, MAC consists of two cooperating processes, the MAC receiver and the MAC transmitter. The two processes are specified both with text and state diagrams which can be naturally represented as two individual ETSs. Based on the information specified in the services section and operation section of the MAC standard, we construct an extended transition system which represents all aspects of the protocol behaviors that we intend to specify in Estelle.Y/ASN.l. Before we present the construction of this ETS for MAC, we show how to combine two arbitrary extended transition systems into a single one with equivalent behavior. Definition 5.1 Given two extended transition systems ETS\ = (Qx,Ei,T\,qlnit) and ETS2 = (Q.2,E2,T2,q?nit). An extended transition system ETS = (Q,E,T,qinit) simulates ETS\ and ETS2) if there exists a relation R C Qi x Q2 x Q such that < q}niti<ltnitiQinit >G R and V < 9i><?2>9 >€ R> < >G T\ implies that there exists a q' € Q such that < q,e,q* >€ T and < q[,q2,q' >€ R, or < q2,e,q'2 >€ T2 implies that there exists a q' 6 Q such that < q,e,q' >G T and < quq'^q1 >6 R. Definition 5.2 Given two extended transition systems ETS\ = (Q\,E\,T\,q}nit) and ETS2 = (Q2,E2,T2,qfnit). An extended transition system ETS = (Q,E,T,qinit) is simulated by ETS\ and ETS2, if there exists a relation R C Qx x Q2 x Q such that < q}nit,<linit>Qinit >€ R and V < 9i,92>9 >6 R, < q,e,q' >6 T implies that there exists a q[ G Q\ such that < gi,e,gi >G T\ and < q'i,q2,q> >€ R or there exists a q'2 € Q2 such that < q2,e,q'2 >€ T2 and < qi,q2,ql >G R. Definition 5.3 Given two extended transition systems ETS\ and ETS2. An extended transi-tion system ETS is equivalent to ETS\ and ETS2, if ETS simulates and is simulated by ETS\ and ETS2. Definition 5.4 Given two extended transition systems ETS\ = (Q\,E\,T\,q\nit) and ETS2 = (Q2,E2,T2,q2nit), the product of ETSX and ETS2 (written as ETSX ® ETS2) is an extended transition system ETS = {Q,E,T,qinit), where Q = Qi x Q2, E = Ex U E2, T = {« 9i,92 >,e,< gi,92 >> I < 9i ,e ,9i >€ T\ and q2 = q'2 or < q2,e,q'2 >€ T2andqx = q[} and 1 2 Qinit =< QinitiVinit CHAPTER 5. TEST GENERATION FOR THE FDDI MAC PROTOCOL 65 T h e o r e m 1 Given two extended transition systems ETSi andETS2. ETSi®ETS2 is equivalent to ETSi and ETS2. Proof. Let ETSi = (Qi,Ei,Tuqjnit) and ETS2 = (Q2,E2,T2,qfnit). By Definition 5.4, ETS = ETSi ® ETS2 = (Q, E,T,qinit) where Q = Qx x Q2, E = Ex U E2, T = {<< gi,g2 > ,e,< gi,^ >> | < qi,e,q[ >€ 7i and q2 = q'2 or < q2,e,q'2 >e T2 and qx = q[} and qinit =< ihivllnit >• Define relation i2 C Qa x Q 2 X Q as follow. Initially, i2 = {< q}nit,q2nivqinit > } = {< Qinitfliniv < Qtnin Qinit » } • Repeat the following procedure until R is not growing. For any < gi,g2,< qi,q? » e R, if < qi,e,q[ >€ Ti, R *- RU < g(,g2,< gi,?2 >>; if < ?2»e,g2 >€ T 2, R <— RU < qi,q'2, < qi,q'2 >>. It is clear that elements in R are all of the form < qx,qy,< qx,qy » . We now prove that ETSi ® ETS2 simulates ETSi and ETS2. It is obvious that < Qinit>QinivQimt >=< «L.»8?ni.» < Qinit>Qinit >>€ Consider any < gi,g2,g >G By the above procedure, it must be that q =< qi,q2 >. Case 1. If < gi,e,gi >e T\, then let g' =< gi,g2 >. Thus by Definition 5.4 << gi,g2 >,e,< QiiQi >>€ ETSi ® ETS2, and by the above procedure generating R, < q[,g2,g' >=< gi, g2, < gi,g2 >>€ R. Case 2. If < g2,e,g2 >e T2, then let g' =< gi,g2 >. Thus by Definition 5.4 << gi,g2 >,e, < gi>g2 >>€ ETSi ® ETS2, and by the above procedure generating i2, < qi,q2,q' > = < gi,^, < gi,g2 » € ii. Thus in either case, we see R satisfy the condition in Definition 5.1. Therefore, ETSi ® ETS2 simulates ETSi and ETS2. We now proceed to prove that ETSi®ETS2 is simulated by ETSi and ETS2. It is obvious that < q}nit,qinit,qinit >=< < ffL.• 9?n.t >>e Consider any < gi,g2,g >€ R. q must be < gi,g2 >. If < g,e,g' >€ T, it must be i) q' =< gi,g2 > and < qi,e,q[ >€ Ti or ii) g' =< g i ^ > and < g2,e,g2 >€ T2. It is clear that, by the above procedure generating R, in case i) < gi,g2,g' >G R, and in case ii) < g^g^g7 >€ R. Thus in either case, we see R satisfy the condition in Definition 5.2. Therefore, ETSi®ETS2 is simulated by ETSi and ETS2. A Hence ETSi ® ETS2 is equivalent to J S r S i and ETS2. CHAPTER 5. TEST GENERATION FOR THE FDDI MAC PROTOCOL 66 We now proceed to describe the FDDI MAC protocol based on the extended transition system model. Before the MAC receiver and transmitter are combined, some revisions to the original state diagrams are necessary. We have mentioned that the data transmission via the MAC to PHY service primitives are not intended to be controlled or observed. Currently, the process of combining two ETSs is not automated. It is very tedious to combine the original state diagrams into one manually. This is another reason for using the test method mentioned in Section 5.2. The major triggering event of the MAC receiver is the occurrences of PHY_UNITDATA_indication which is a MAC to PHY service primitive. As the result of this kind of events being eliminated, the receiver state diagram is reduced to have two states. For the same reason, two of the six states of the original transmitter state diagram are combined into one state in the revised transmitter state machine. We convert the two revised state diagrams, the MAC receiver and transmitter, into two individual extended transition systems ETSi and ETS2- We then generate the product of ETSi and ETS2 (ETSi ® ETS2). The rules or the algorithm of generating ETS\ ® ETS2 is in fact provided in Definition 5.4. The correctness of ETSi ® ETS2 is guaranteed by Theorem 1. We noticed that the two state diagram provided by the MAC standard do not actually represent the complete knowledge of the behaviors of MAC. For example, the interactions through the MAC to LLC interface via MAC to LLC SPs are not specified in the state diagrams. We revise the resulting single ETS to accommodate all interested knowledge of the external behavior of the FDDI MAC protocol including those aspects missing in the original two state diagrams. Figure 5.4 illustrates the simplified single ETS representation of FDDI MAC protocol. In Figure 5.4, each arc between two nodes (representing two states of the ETS) may represent several transitions associated with different events. A complete ASN.l specification and an excerpt of the Estelle.Y specification of FDDI MAC protocol are provided in Appendix B and C for reader reference. CHAPTER 5. TEST GENERATION FOR THE FDDI MAC PROTOCOL 67 Figure 5.4: FDDI MAC protocol state machine 5.3 Generating test suite using TESTGEN This section presents the test suite generation and selection of FDDI MAC protocol with TEST-GEN. 5.3.1 PDS of FDDI M A C protocol The Estelle.Y specification of FDDI MAC protocol is first parsed and the PDS is generated from the specification. The generated PDS contains about 1000 expressions (namely about 1000 instances of EXPR structure) and about 350 assignment statement (instances of ASTMT structure). The number of instances of other defined structures are less than 100. 5.3.2 Tuning constraints for FDDI M A C protocol A test suite can be generated for the FDDI MAC protocol by using the set of default constraints. In order to generate a test suite with reasonable size and better fault coverage for a specific protocol, we have to tune the constraints, namely reset or change the constraints through the constraint editor according to the characteristics of the protocol to be tested. As mentioned in Chapter 2, the TSG-constraints define an upper and a lower bound on the CHAPTER 5. TEST GENERATION FOR THE FDDI MAC PROTOCOL 68 number of times an ETS element can be reached or used in one subtour. The maximal number of times SPs and PDUs can be used within a subtour is set to 1 by default. It means that any transition having a SP or PDU associated with it can be used at most once in a subtour. We need to change the max — used value imposed on one of the MAC PDUs, Frame, into a value more than 1 to allow the case of when several frames are sent due to the capture of a token to be tested. The maximal number of times a state can be reached within a subtour is set to 99 by default. This will cause excessive subtours being generated. For example, if there is a transition which starts from a state and ends at the same state and no SPs or PDUs are associated with the transition, 99 different subtours will be identified with the state being reached for 1 to 99 times. The parameter variation constraints define a set of values for each parameter of each ISP or PDU that can be sent to the IUT. The instances of ISPs and PDUs that will be used to test the IUT are thus defined. The default parameter variation constraints on three supported parameter type are: TRUE, FALSE for boolean, 0, 99 for integer and "test-stringl" for character strings. These default values are likely not suitable for testing the ISPs and PDUs of a specific proto-col. For example, the frame control field of Frame, one of the FDDI MAC PDUs, is used to distinguish different types of frames. There are about 10 different types of frames defined in the FDDI MAC protocol standard. To test all of them, we need a set of specific values, namely default parameter variation constraints to the frame control field of Frame. 5.3.3 Test generation The test suite generation engine identifies subtours based on the PDS representation of a protocol generated by the parser as well as a set of constraints set through the constraint editor. The test suite generation engine is being developed. A comprehensive test suite can be successfully generated by using TESTGEN with an appropriate set of constraints after the test CHAPTER 5. TEST GENERATION FOR THE FDDI MAC PROTOCOL 69 suite generation engine is implemented. Our purpose of applying TESTGEN to real life protocols is mainly to demonstrate the viability of the TESTGEN tool and obtain some experience in specifying and testing of high-speed network protocols. So the constraints set by us may not satisfy special testing purposes in a testing center or in the industry. However, by our experience, TESTGEN is a flexible and productive and easy to use. In fact, users are easy to control the size of the generated test suite and to generate test cases with required fault coverage according to their own testing purposes. 5.4 Summary In this chapter, we discussed the issues of test suite generation for FDDI MAC protocol with emphasis on the formal specification of the protocol. In order to produce the formal specifica-tion, we combined the MAC receiver and transmitter. We presented a method of combining two ETSs into a single one with equivalent behavior. In fact, this method is easily improved to combine arbitrary number of ETSs into one with equivalent behavior. This shows that our ETS-based Estelle.Y/ASN.l can be used to specify any protocols. Chapter 6 Conclusions This thesis presents and discusses the design and implementation of the front end of TESTGEN, a software environment for test suite generation and selection for conformance testing as well as its application to a specific protocol, FDDI MAC protocol. 6.1 TESTGEN features TESTGEN adopts the TSG-constraints based test suite generation method which integrates the generation and selection of abstract TTCN test suites from formal specification of commu-nication protocols. The generated test cases cover both the control and the data flow part of the protocol. TESTGEN supports consistent end-to-end use of ASN.l in the given formal protocol spec-ification. The ASN.l support is incorporated in the generated PDS as well as in the TSG constraints mechanism, which leads to coherent ASN.l TTCN constraints. Moreover, the TSG constraints approach in TESTGEN offers a flexible mechanism for generating conformance test suites and special purpose test suites for real life protocols. TESTGEN thus serves as a useful test-bed for experimenting with protocol test generation and selection in addition to being a useful productive system. The design and implementation of the TESTGEN front end is crucial to the development of the TESTGEN. The ETS/ASN.l formalism is a well-defined intermediate representation form 70 CHAPTER 6. CONCLUSIONS 71 which can represent complete protocol knowledge including both control and data parts pre-cisely. Despite the fact that the ETS/ASN.l formalism and its data structure representation (the PDS) are designed for automatic test generation using the TESTGEN tool, they may be used for other applications such as the development of other ETS based test generation tools. Furthermore, such intermediate representations and their internal data structure representa-tions of protocols are useful for many other applications such as protocol validation tools and conformance testing tools based on trace analysis methodology. To compare TESTGEN with other existing test sequence generation tools, we consider those proposed in [Ural-88], [EBE-89-1] and CONTEST_ESTL by [Sari-89]. The similarities between TESTGEN, CONTEST_ESTL and Ural's proposal are that they all generate TTCN test suites based on protocol specification in Estelle (or Estelle variants). The TSG method proposed in [EBE-89-1], on the other hand, derives test sequences based on EBE. The test generation method used in TESTGEN detects errors that are not detected by CONTEST-ESTL, Ural's method or EBE based method. TESTGEN is expected to provide better fault coverage by using a more elaborate test sequence generation algorithm. Moreover, TESTGEN completely automates the TSG process by using default setting of TSG constraints, as contrast to CONTEST_ESTL, in which the test sequence generation procedure is just semi-automated. On the other hand, CONTEST-ESTL provides graphical displaying of the control and data flow graphs of the specification as well as generating the test sequences [Sari-89], which is not available in TESTGEN. In addition, TESTGEN provides users with much flexibility through the interactive setting of constraints on each of ETS elements. Moreover, it supports ASN.l directly. Estelle.Y can be served as either an intermediate or direct formal description language. 6.2 TSG for FDDI using TESTGEN As we mentioned before, FDDI is not an ISO standard. However it is developed in conformance with the OSI reference model and other ISO guidelines. As a consequence, the ISO conformance CHAPTER 6. CONCLUSIONS 72 testing methodology and frame work [ISO-9646] can be applied to the testing of FDDI MAC protocol without much difficulties. As stated in the ISO 9646 standard, the defined methodology and framework can not be used for testing of the Physical Layer. The FDDI MAC layer protocol is the only component of FDDI that can be tested using the methodology and framework defined in the ISO 9646 standard. Given the fact that the FDDI MAC protocol are specified in terms of two concurrent pro-cesses, efforts has been made to produce an ETS-based formal specification of the FDDI MAC protocol. Although a test suite can be generated by TESTGEN for FDDI MAC protocol using a set of default constraints without any human interventions, in order to better satisfy testing purposes for a specific protocol, the user must tune the default constraints to allow some specific aspects of the protocol to be covered by the generated test suite. Some knowledge about the behaviors of a protocol are described in the ETS/ASN.l for-malism is required for tuning constraints for the test generation, including the identification of major behaviors of the protocol. However, it is much easier for a user to understand the be-haviors of a protocol specified in the ETS/ASN.l formalism based specification than to provide the interventions required by CONTEST.ESTL [Ural-88]. 6.3 Future works The TESTGEN front end has been developed in a way to allow the enhancements to be done easily. Many complex communication protocols are defined as multiple logical entities (e.g. the FDDI transmitter and receiver processes) in order to employ the parallelism and allow concur-rency in a communication system. The multiple entities can not be naturally represented by a single module Estelle specification. Furthermore, communication protocols are rarely tested in a stand-alone mode (local test method), but are combined with a service provider when using the distributed test method or a CHAPTER 6. CONCLUSIONS 73 Ferry Clip approach. In this case multiple modules are involved, including the service provider module as well as the IUT module in the test suite generation process. A natural extension of TESTGEN will allow multiple-module Estelle specifications to be parsed into a composite protocol data structure. An enhanced test suite generation engine (TSG method and tool) will be able to identify the subtour combinations which cover also the observable service primitive exchange at the external gates(PCOs). Only three data types allowed for variables and constants by the current version of TEST-GEN. The three data types supported by the current version of TESTGEN are proved not enough to specify FDDI MAC protocol. Most of the fields of a PDU in Data link layer of OSI model are normally bit strings. The value of some of the fields determines the PDU's type. For example, the frame control field of FDDI MAC PDU distinguishes different types of PDUs. The MAC protocol examines some bits to identify the type of a received PDU, such as a token or a frame, and then take different actions based on the PDU's type. To specify the behaviors of the FDDI MAC protocol precisely and naturally, bit type, bit string type and associated operations are necessary. For similar reasons, data structures such as queue and array are also required. There are two possible approaches to support the needed data structures. One is to enhance the Pascal subset supported by TESTGEN. We need to know theoretically how complete a Pascal subset should be included in Estelle.Y for description of external behaviors of a protocol. Another possibility is to make use of ASN.l for type definitions of variables (data states) and constants. For example, the ASN.l SEQUENCEOF type which is similar to the array in Pascal can be used to define arrays of variables or constants by enhancing the internal data structure representation of protocols, namely the ASN.l type tree and the PDS. Pointer type are necessary for queues of unlimited length. Pointer type can be supported by changing VAR structure slightly. Finally a useful enhancement of TESTGEN is to incorporate a fault coverage measure into TESTGEN, based on the ongoing test coverage metric research conducted in [Vuong-91-2], into TESTGEN. The inclusion of this coverage measure will allow the user to compare and CHAPTER 6. CONCLUSIONS 74 evaluate the generated test suites with an objective measure and to tune the test suite generation constraints for the best results. Bibliography [ANSI-1987] American National Standard, FDDI Token Ring Media Accesss Control (MAC), ANSI X3.139-1987. [ANSI-1989] Draft proposed American National Standard, FDDI Token Ring Station Manage-ment (SMT), ASC X3T9.5, Rev. 6, May 1989. [BOCH-90] Gregor v. Bochmann, Protocol Specification for OSI, Computer Networks & ISDN Systems 18 (1989/1990). [Chan-89] W. Y. L. Chan, S. T. Vuong and M. R. Ito, An improved Protocol Test Genera-tion Procedure Based on UIOs, Proceedings of the ACM SIGCOMM '89 Symposium on Communication Architectures and Protocols, September 1989. [Chow-78] T. S. Chow, Testing Software Design Modeled by Finite State Machines, IEEE Trans-actions on Computer, March 1978, Vol. 4, No. 3, pages 178-187. [CRS-89] L . Mackert, J. Schneider, I. Neumeier-Mackert and R. Velthuys, Executing Protocol knowledge, European network Center IBM, Technical Report 43.8907, 1989 [EBE-89-1] J. P. Wu, S. T. Chanson, A new Approach to Test Sequence Derivation based on External Behavior Expression (EBE), Technical Report 89-3, Department of Computer Science, University of British Columbia, Jan 1989. 1976, pp:305-330. [EBE-89-2] J.P. Wu and S. T. Chanson, Test Sequence Derivation Based on External Behav-ior Expression (EBE), 2nd International Workshop on Protocol Test Systems, Berlin, Germany, Oct. 1989. [Fosd-76] L.D. Fosdick and L. J. Osterweil, Data flow analysis in software reliability, ACM Computing Serveys, Vol. 8, No.3, [Gone-70] G. Gonenc, A Method for the Design of Fault Detection Experiments, IEEE Trans-actions on Computers, Vol. 19, No. 6, June 1970. [ISO-8807] Information Processing System - Open System Interconnection - LOTOS -A Formal Description Technique based on the Temporal Ordering of Observational Behavior, ISO 8807, September 1987. 75 BIBLIOGRAPHY 76 [ISO-8824] Information Processing System - Open System Interconnection - Specification of Abstract Syntax Notation One, ISO 8824, 1987. [ISO-9074] Information Processing System - Open System Interconnection - Estelle - A Formal Description Technique Based on an Extended State Transition Model, IS 9074, 1989. [ISO-9646] Information Technology - OSI Conformance Testing Methodology and Framework, Draft International Standard, ISO/IEC DIS 9646 (5 Parts). [ISO-TTCN] Information Technology - OSI Conformance Testing Methodology and Frame-work, Part 3:The Tree and Tabular Combined Notation, ISO/IEC DIS 9646-3, 1990. [Kel-76] R. M. Keller, Formal Verification of Parallel programs, Communication of the ACM 19, pp371-384, 1976. [LIN-90] Richard J. Linn, Jr., Conformance Testing for OSI Protocols, Computer Networks & ISDN Systems 18 (1989/1990). [Naito-81] S. Naito and M. Tsunoyama, Fault Detection for Sequential Machines by Transition Tours, Proceedings of the 11th IEEE Fault-Tolerant Computing Symposium, pp.138-243, June 1981. [Neu-90] G. W. Neufeld and Y. Yang, The design and Implementation of an ASN.l Compiler, IEEE Transactions on Software Engineering, Vol.16, No. 10, Oct. 1990. [PG-90] Marc Phalippou, Roland Groz, From Estelle specifications to industrial test suites, using an empirical approach, FORTE '90 [PUH-88] R. L. Probert, H. Ural and M. W. A. Hornbeek, An Integrated Software Environment For Developing & Validating Standardized Conformance Tests, Protocol Specification, Testing, and Verification VIII, S. Aggarwal and K. Sabnani (Editors), Elsevier Science Publishers B. V. (North-Holland). [RAY-87] D. RAYNER, OSI Conformance Testing, Computer Networks & ISDN Systems 14 (1987). [ROSS-86] Floyd E. Ross, FDDI - A Tutorial, IEEE Communications Magazine, May 1986 -Vol.24, No.5 [ROSS-90] Floyd E. Ross, James R. Hamstra and Robert L. Fink, FDDI - A LAN Among MANs, ACM Computer Communication Review, Vol. 20, No.3, July 1990 [Sabn-88] K.K. Sabnani and A. T. Dahbura, A Protocol Test Generation Procedure, Computer Networks and ISDN Systems, Vol. 15, No. 4, pp. 285-297, September 1988. BIBLIOGRAPHY 77 [Sample-90] M. Sample and G. Neufeld, Support for ASN.l within a Protocol Testing Environ-ment, The Third International Conference on Formal Description Techniques (FORTE '90), Madrid Spain, November 1990. [Sari-87] B. Sarikaya, G. v. Bochman, and E. Cerny, A Test Design Methodology for Protocol Testing, IEEE Transactions on Software Engineering. Vol. 13, No. 5, pp. 518- 531, May 1987. [Sari-89] Behcet Sarikaya, Srinivas Eswara, Vassilios Koukoulidis, A Formal Specification Based Test Generation Tool, ? Apr 1989 [SDL-88] CCITT Recommendation: Specification and Description Language SDL, CCITT Z.100, blue book, 1988 [Sidhu-89] D.P. Sidhu and T. -K. Leung, Formal Methods for Protocol Testing: A Detailed Study, IEEE Transactions on Software Engineering, Vol. 15, No. 4, pp. 413-426, April 1989. [SKO-89] Morten Skov, Implementation of physical and media access protocols for high-speed networks, IEEE Communications Magazine, 1989. [TR-90-x] H. Janssen, Y. Lu and P. Zhou, Definition of a Protocol Data Structure Representa-tion for Communication Protocols, UBC Technical Report, planned for summer 1991. [TR-90-y] Y. Lu and H. Janssen, Integrating Estelle and ASN.l for the generation of PDS, UBC Technical Report, planned for summer 1991 [TR-90-z] P. Zhou and H. Janssen, TSG constraints for PDS based test suite generation, UBC Technical Report, planned for summer 1991 [Ural-87-1] H. Ural, A Test Derivation Method for Protocol Conformance Testing, University of Ottawa, Technical Report - TR-87-04, Jan. 87. [Ural-87-2] H. Ural, Test Sequence Selection Based on static data flow analysis, Computer Communications, Vol. 10, No. 5, 1987, pp: 234-242. [Ural-88] H. Ural, B. Yang, R. L. Probert, A Test Sequence Selection Method for Protocols Spec-ified in Estelle, Technical Report TR-88-18, Department of Computer Science, University of Ottawa, June 1988. [Vuong-88] S. T. Vuong, Allen C. Lau and R. Issac Chan, Semiautomatic Implementation of Protocols Using an Estelle-C Compiler, IEEE Transactions on Software Engineering, Vol. 14, No.3, March 1988. [Vuong-89] S. T. Vuong, W. Y. L. Chan, and M. R. Ito, The UIOv-Method for Protocol Test Sequence Generation, Proceedings of the Second International Workshop on Protocol Test Systems, October 1989. BIBLIOGRAPHY 78 [Vuong-91-1] S. T. Vuong, H. Janssen and Y. Lu, TESTGEN: An Environment for Test Suite Generation and Selection, submitted to FORTE '91. [Vuong-91-2] S. T. Vuong and J. Alilovic-Curgus, A Metric Characterization of Infinite Com-putations in LOTOS, submitted for publication, June 1991. [KFNT-90] Kotaro Katsuyama,e£ al. OSI Testing Environment Based on Standardized For-malisms, FORTE '90 [Wvong-90] Russil Wvong, A New Methodology for OSI Conformance Testing Based on Trace Analysis, Master thesis, Department of Computer Science, UBC Oct 1990. Appendix A Estelle.Y B N F definition s p e c i f i c a t i o n ::= "spe c i f i c a t i o n " IDENTIFIER "; body.definition body.definition ::= declaration.part i n i t i a l i z a t i o n . p a r t state_trans_part . declaration_part ::= constant.definition.part variable_declaration_part isp_declaration_part osp_declaration_part pdu_declaration_part timer_declaration_part state_definition.part . 'end." 79 APPENDIX A. ESTELLE.Y BNF DEFINITION 80 constant.definition.part ::= ["CONST" constant.definition.group] . constant.definition.group ::= +{ constant.definition ";"} . constant.definition ::= IDENTIFIER "=" constant . constant ::= INTEGER | CHARACTER.STRING | "true" I " f a l s e " . variable_declaration_part ::= [ "VAR" variable_declaration_group] . variable_declaration_group ::= +{ variable.declaration ";"} . variable.declaration ::= i d e n t i f i e r . l i s t ":" type_denotor . i d e n t i f i e r . l i s t ::= IDENTIFIER {"," IDENTIFIER} . type_denotor ::= "INT" | "BOOLEAN" | "CHAR.STR" . isp_declaration_part ::= "ISP" isp_declaration_group . isp_declaration_group ::= +{ isp.declaration > . isp.declaration ::= isp.name pco.name ";" . isp.name ::= IDENTIFIER, pco.name ::= IDENTIFIER. osp_declaration_part ::= "OSP" osp_declaration_group . osp_declaration_group ::= +{ osp_declaration > . osp.declaration osp.name pco.name ";" . APPENDIX A. ESTELLE.Y BNF DEFINITION 81 osp.name ::= IDENTIFIER . pdu_declaration_part ::= "PDU" pdu_declaration_group . pdu_declaration_group : := +{ pdu.declaration } . pdu_declaration ::= pdu.name send_recv_list ";" I pdu_name pco.name ";" . send_recv_list ::= send.recv sp.name { "," send_recv sp_name } . pdu.name ::= IDENTIFIER . sp.name ::= IDENTIFIER . send.recv ::= "sent.in" I "recv.in" . timer_declaration_part ::= "TIMER" timer_declaration_group . timer_declaration_group ::= +{ timer_declaration }. timer_declaration ::= timer_name timeout_value ";" . timeout.value ::= INTEGER . timer.name ::= IDENTIFIER . i n i t i a l i z a t i o n . p a r t ::= "INITIALIZATION" clause.group trans.block ";" . state.definition.part ::= "STATE" i d e n t i f i e r . l i s t ";" . state_trans_part ::= +{ state_trans_declaration } • s ta t9_trans_declaration ::= "TRANS" transition_group . transition.group ::= +{ trans_declaration } . trans_declaration ::= from.clause trans_declaration_group . from.clause ::= "FROM" state.name . APPENDIX A. ESTELLE.Y BNF DEFINITION 82 trans_declaration_group ::= +{ trans_body_definition }. trans_body_dafinition ::= clause_group trans.block ";" . clause_group ::= to.clause when.clause provided.clause priority_clause output.clause trans.name . to.clause ::= "TO" state.name . state.name ::= IDENTIFIER . when.clause ::= { "WHEN" isp_or_pdu } . isp.or.pdu ::= IDENTIFIER . provided.clause ::= { "PROVIDED" bool.expression } . bool.expression ::= expression . priority.clause ::= { "PRIORITY" INTEGER I "PRIORITY" IDENTIFIER } . output.clause ::= { "OUTPUT" osp_opdu_list } . osp_opdu_list ::= i d e n t i f i e r . l i s t . trans.name ::= { IDENTIFIER } . trans.block ::= statement.part . statement.part ::= { compound.statement } . compound.statement ::= "BEGIN" statement.sequence "END" I "BEGIN" statement.sequence ";" "END" . statement.sequence ::= simple.statement { ";" simple.statement } . simple.statement ::= assignment.statement | APPENDIX A. ESTELLE.Y BNF DEFINITION 83 if.statement | while.statement | timer.statement . assignment.statement ::= variable.access ":=" expression . variable.access ::= IDENTIFIER { ".11 IDENTIFIER } . if.statement ::= i f . p r e f i x statement i f . p r e f i x statement else.part . i f . p r e f i x ::= "IF" bool.expression "THEN" . else.part ::= "ELSE" statement . statement ::= simple.statement I compound.statement . while.statement ::= "WHILE" bool.expression "DO" statement . timer.statement ::= timer.operator " ( " timer.name " ) " "SET" " ( " timer.name "," expression " ) " . timer.operator ::= "RESET" I "START" I "STOP" . expression ::= expression "+" expression expression "-" expression expression multop expression expression boolop expression expression relop expression APPENDIX A. ESTELLE.Y BNF DEFINITION 84 "-" p r i m a r y I "NOT" p r i m a r y I p r i m a r y 1 "NOT" e x p r e s s i o n I " ( " e x p r e s s i o n " ) " . p r i m a r y ::= c o n s t a n t . p r i m a r y I v a r i a b l e . a c c e s s I t i m e r . e x p r e s s i o n . c o n s t a n t _ p r i m a r y ::= c o n s t a n t . m u l t o p ::= "*" I "/" I "MOD" . b o o l o p ::= "AND" | "OR" . r e l o p ::= "=" I "<=" I "<" I ">=" I ">" I "<>" . t i m e r _ e x p r e s s i o n ::= t i m e r . s t a t u s " ( " t i m e r . n a m e " ) " . t i m e r . s t a t u s ::= "TIMEOUT" I "STARTED" I "STOPPED" I "RESET" | "READ Metalanguage Symbols Meta-symbol Meaning ::= sh a l l be defined to be I alternatively end of d e f i n i t i o n [x] 0 or 1 instance of x •Cx} 0 or more instances of x +{x} 1 or more instances of x APPENDIX A. ESTELLE.Y BNF DEFINITION 85 "xyz" meta-identifier the terminal symbol xyz a nonterminal symbol Appendix B A S N . l specification of F D D I M A C SPs and P D U s FDDIMac DEFINITIONS ::= BEGIN MacToLlcAsp ::= CHOICE •C MaUnitDataRequest, MaUnitDatalndication, MaUnitDataStatusIndication, MaTokenRequest } MaUnitDataRequest ::= SEQUENCE { fcValue DataSymbolPair, destinationAddress Address, mSDU OCTET STRING, requestedServiceClass INTEGER {synchronous(0), asynchronous(1)}, 86 APPENDIX B. ASN.l SPECIFICATION OF FDDI MAC SPS AND PDUS 87 stream BOOLEAN DEFAULT FALSE, tokenClass INTEGER } MaUnitDatalndication ::= SEQUENCE •C fcValue DataSymbolPair, destinationAddress Address, sourceAddress Address, mSDU OCTET STRING, receptionStatus BOOLEAN > MaUnitDataStatusIndication ::= SEQUENCE { numberOfSDUs INTEGER, transmissionStatus OCTET STRING, — implementer defined providedServiceClass INTEGER -[synchronous(0), asynchronous(1)} } MaTokenRequest ::= SEQUENCE { requestedTokenClass INTEGER - C r e s t r i c t e d ( O ) , nonrestricted(i)} } PhyToMacAsp ::= CHOICE -C PhUnitDataRequest, PhUnitDatalndication, PhUnitDataStatusIndication, Phlnvalidlndication APPENDIX B. ASN.l SPECIFICATION OF FDDI MAC SPS AND PDUS 88 PhUnitDataRequest ::= SEQUENCE •C phRequest Symbol } PhUnitDatalndication ::= SEQUENCE { phlndication Symbol > PhUnitDataStatusIndication ::= SEQUENCE transmissionStatus BOOLEAN > Phlnvalidlndication ::= SEQUENCE •C phlnvalid INTEGER ~ th i s tpye i s not defined i n the standard } MacPdu ::= CHOICE { Frame, Token } Token ::= SEQUENCE •C pA OCTET STRING, - 16 or more symbols APPENDIX B. ASN.l SPECIFICATION OF FDDI MAC SPS AND PDUS 89 sD SD, fC DataSymbolPair, eD ControlSymbolPair } Frame ::= SEQUENCE •C pA OCTET STRING, — 16 or more symbols sD SD, fC DataSymbolPair, dA Address, sA Address, info InfoType, — 0 or more data symbol pairs fCS OCTET STRING (SIZE(4..4)), ~ 8 data symbols eD TSymbol, fS FSType — 3 or more data symbols > SD ::= SEQUENCE •C j JSymbol, k KSymbol } FSType ::= SEQUENCE •C a DataSymbol, c DataSymbol, e DataSymbol } APPENDIX B. ASN.l SPECIFICATION OF FDDI MAC SPS AND PDUS 90 InfoType ::= SEQUENCE { f irs t4Byte OCTET STRING (SIZE(4 . .4 ) ) , res t lnfo OCTET STRING > MacToSmtAsps ::= CHOICE { SmMalnitProtocolReq, SmMalnitProtocolcfm, SmMaCtrlReq, SmMaStatusIndication > SmMalnitProtocolReq ::= SEQUENCE { indivMACaddrS OCTET STRING (SIZE(2 . .2 ) ) , indivMACaddrL OCTET STRING (SIZE(6 . .6 ) ) , groupMACaddrs OCTET STRING, tMin INTEGER, tMax INTEGER, tvx INTEGER, tReq INTEGER, tNeg INTEGER, tNeg INTEGER, t P r i INTEGER, indForOwnFr BOOLEAN, indForRcvOnlyGoodFr BOOLEAN APPENDIX B. ASN.l SPECIFICATION OF FDDI MAC SPS AND PDUS 91 SmMalnitProtocolcfm ::= SEQUENCE { status BOOLEAN } SmMaCtrlReq ::= SEQUENCE •C c t r l A c t i o n INTEGER -CmacReset(O), beacon(l) , presentStatus(2), resetCounters(3), interruptUponCond(4), sendBadFCS(5)}, beaconlnfo OCTET STRING, requestedStatus MacStatus, requestedCond INTEGER {tkCaptured(O) , f rRece ived( l ) , tkPassed(2)} > MacStatus ::= SEQUENCE { counterValue INTEGER, — there are several C t ' s currentTHTValue INTEGER, currentTVXValue INTEGER, currentTRTValue INTEGER, rF lag INTEGER, currentRxState INTEGER, currentTxState INTEGER SmMaStatusIndication ::= SEQUENCE •C statusReport INTEGER APPENDIX B. ASN.l SPECIFICATION OF FDDI MAC SPS AND PDUS 92 > Address ::= CHOICE { longAddress INTEGER, — should be 48-bit BIT STRING shortAddress INTEGER — should be 16-bit BIT STRING } JSymbol KSymbol TSymbol = ControlSymbol = ControlSymbol = ControlSymbol Symbol ::= INTEGER — control symbol or data symbol ControlSymbol ::= INTEGER — 5-bit BIT STRING DataSymbol ::= INTEGER — 4-bit BIT STRING DataSymbolPair ::= INTEGER — 8-bit BIT STRING ControlSymbolPair ::= INTEGER — 10-bit BIT STRING END Appendix C Excerpt of Estelle.Y Specification F D D I M A C protocol Specification f d d i . l ; CONST I = 31: i n t ; J = 24: i n t ; K = 17: i n t ; R = 7: i n t ; S = 25: i n t ; T = 13: i n t ; Restricted = 1: i n t ; Nonrestricted = 0: i n t ; Void = 0: i n t ; Implementer = 1: i n t ; Claim.FR =0: i n t ; Beacon.FR = 1: i n t ; S.Addrs = 0: i n t ; 93 APPENDIX C. EXCERPT OF ESTELLE. Y SPECIFICATION OF FDDI MAC PROTOCOLS L.Addrs = 0: i n t ; zero = 0: i n t ; one = 1: i n t ; Yes = true: boolean; No = f a l s e : boolean; high = 10: i n t ; medium = 5: i n t ; low = 0: i n t ; Mac.Reset = 0: i n t ; Beacon = 1: i n t ; NULL.STR = "": c h a r . s t r ; succ = 0: i n t ; f a i l = 1: i n t ; VAR MSA: i n t ; MLA: i n t ; n: i n t ; T_0pr, T_Bid_Rc, T_Bid_Tx, T.Neg, T_Req, T_Max: i n t ; Ring_Operational: boolean; Token.c lass: i n t ; frame_Token_class: in t ; A . F l a g , C . F l a g , E . F l a g , M.Flag, N .F lag , H . F l a g , L . F l a g , R .F lag: i n t ; APPENDIX C. EXCERPT OF ESTELLE. Y SPECIFICATION OF FDDI MAC PROTOCOLS Frame.Ct, Error.Ct, Lost.Ct, Late.Ct: i n t ; My.Claim, Lower.Claim, Higher.Claim, My.beacon, Other.beacon: boolean; Usable, FR.strip, FR.copied, nomoredata: boolean; Valid_Data_Length, Valid_FCS_Rc, Valid_Copy: boolean; Claim_FR_rec, Beacon_FR_rec: boolean; FCrlsToken, FCrEqNSA: boolean; Buffer_sD_J, Buffer_sD_K, Buffer.fC, Buffer_dA_L, Buffer_sA_L, Buffer_dA_S, Buffer_sA_S: i n t ; Buffer.pA, Buffer.info, Buffer.fCS: char.str; Buffer.eD, Buffer_fS_a, Buffer_fS_c, Buffer_fS_e: i n t ; frame.FC, frame_FC_Lr: i n t ; frame.INFO, frame.FCS: char_str; frame.SA, frame_DA_L, frame_DA_S, frame.ED: i n t ; req_service_class: i n t ; Ex, Ax, Cx: i n t ; num_of.frames, trans_status: i n t ; Lr: i n t ; ISP MaUnitDataRequest llc_mac; MaTokenRequest llc_mac; PhUnitDatalndication mac.phy; PhUnitDataSt atusIndi c at ion mac_phy; Phlnvalidlndication mac.phy; APPENDIX C. EXCERPT OF ESTELLE. Y SPECIFICATION OF FDDI MAC PROTOCOLS OSP SmMalnitProtocolReq smt_mac; SmMaCtrlReq smt_mac; MaUnitDatalndication llc.mac; MaUnitDataStatusIndication llc.mac; PhUnitDataRequest mac_phy; SmMalnitProtocolcfm SmHaStatusIndication smt.mac; smt.mac; PDU Frame sent_in PhUnitDataRequest, recv.in PhUnitDatalndication; Token sent.in PhUnitDataRequest, recv.in PhUnitDatalndication; TIMER TVX THT TRT 2350; 0; 165000; STATE Rx.data, Ck.frame, Tx.data, Issue.TK, Claim.TK, Tx.beacon; INITIALIZATION APPENDIX C. EXCERPT OF ESTELLE. Y SPECIFICATION OF FDDI MAC PROTOCOLS TO Rx.data BEGIN Ring.Operational := true; nomoredata := true; FR_copied := fa l s e ; FR.strip := false; END; TRANS FROM Rx.data TO Rx.data WHEN PhUnitDatalndication PROVIDED (PhUnitDatalndication.phlndication = I) and (not Reset(TVX)) PRIORITY high OUTPUT PhUnitDataRequest BEGIN Reset(TVX); Start(TVX); PhUnitDataRequest.phRequest := I; END; TO Rx.data WHEN SmMaCtrlReq PROVIDED (SmMaCtrlReq.ctrlAction = Mac.Reset) PRIORITY high BEGIN APPENDIX C. EXCERPT OF ESTELLE. Y SPECIFICATION OF FDDI MAC PROTOCOLS T.Neg := T.Max; END; TO Rx.data WHEN MaUnitDataRequest BEGIN frame.FC := MaUnitDataRequest.fcValue; frame.FC.Lr := (frame_FC/64) mod 2; i f (frame.FC.Lr = one) then frame.DA.L := MaUnitDataRequest.destinationAddress.longAddress else frame.DA.S := MaUnitDataRequest.destinationAddress.shortAddress; frame.INFO := MaUnitDataRequest.mSDU; frame.SA := MSA; req.service.class := MaUnitDataRequest.requestedServiceClass; frame.Token.class := MaUnitDataRequest.tokenClass; nomoredata := No; END; TO Ck.frame WHEN Frame BEGIN A.Flag := zero; C.Flag := zero; E.Flag := zero; N.Flag := zero; H.Flag := zero; APPENDIX C. EXCERPT OF ESTELLE. Y SPECIFICATION OF FDDI MAC PROTOCOLS L_Flag := zero; H.Flag := zero; i f (Frame.fC = 15) or (Frame.fC = 79) then N_Flag := one; Lr := (Frame.fC/64) mod 2; i f (Frame.fC <> Void) then i f (Lr = zero and Frame.dA.shortAddress = S.Addrs) or (Lr = one and Frame.dA.longAddress = L.Addrs) then begin A_Flag := one; Buffer_pA := Frame.pA; Buffer_sD_J := Frame.sD.j; Buffer.sD.K := Frame.sD.k; Buffer.fC := Frame.fC; Buffer_dA_S := Frame.dA.shortAddress; Buffer_sA_S := Frame.sA.shortAddress; Buffer_dA_L := Frame.dA.longAddress; Buffer_sA_L := Frame.sA.longAddress; Buffer.info := Frame.info; Buffer.fCS := Frame.fCS; Buffer_eD := Frame.eD; Buffer_fS_a := Frame.fS.a; Buffer_fS_c := S; Buffer_fS_e := Frame.fS.e; APPENDIX C. EXCERPT OF ESTELLE. Y SPECIFICATION OF FDDI MAC PROTOCOL100 FR.copied := Yes; end; i f (Lr = zero and Frame.sA.shortAddress = MSA and MSA > zero) or (Lr = one and Frame.sA.longAddress = MLA and MLA > zero) then begin M.Flag := one; FR.strip := Yes; end else i f (Lr = zero and Frame.sA.shortAddress > MSA and MLA = zero) or (Lr = one and Frame.sA.longAddress > MLA) then H_Flag := one else i f (Frame.sA.shortAddress > zero) or (Frame.sA.longAddress > zero) then L_Flag := one; T_Bid_Rc := Frame.info; i f (Frame.fC = Claim.FR) then begin i f (T_Bid_Rc <> T.Req) then i f L_Flag = one then begin APPENDIX C. EXCERPT OF ESTELLE. Y SPECIFICATION OF FDDI MAC PROTOCOL101 H.Flag := one; L_Flag := zero; end else i f H_Flag = one then begin L_Flag := one; H_Flag := zero; end; i f (L.Flag = one) then FR.strip := Yes; Claim_FR_rec := Yes; end; Frame.Ct := Frame.Ct + one; i f (Valid_Data_Length and (Valid_FCS_Rc or (Frame.fC = Void or Frame.fC = Implementer))) then begin Reset(TVX); Start(TVX); i f A_Flag and Valid_Copy then C_Flag := one; end else begin E_Flag := one; A_Flag := zero; APPENDIX C. EXCERPT OF ESTELLE. Y SPECIFICATION OF FDDI MAC PROTOCOLS H.Flag := zero; M_Flag := zero; L_Flag := zero; end; i f (Frame.fS.a = R) then i f E.Flag = one then Ex i f A_Flag = one then Ax i f C.Flag = one then Cx N.Flag := zero; = S else Ex := Frame.fS.e; = S else Ax := Frame.fS.a; = S else Cx := Frame.fS.c; i f (Frame.fS.c = S) and (M.Flag = one) then trans.status := succ else trans.status := f a i l ; i f (Frame.fC = Claim.FR and A.Flag = 1 and M.Flag = then begin T.Neg := T.Bid.Rc; My_Claim := Yes; R_Flag := zero; Claim_FR_rec := Yes; end else i f (Frame.fC = Claim.FR and H.Flag = one) then begin T_Neg := T_Bid_Rc; Higher.Claim := Yes; R.Flag := zero; APPENDIX C. EXCERPT OF ESTELLE. Y SPECIFICATION OF FDDI MAC PROTOCOL103 Claim_FR_rec := Yes; end else i f (Frame.fC = Claim.FR and L.Flag = one) then begin Lower.Claim := Yes; R_Flag := zero; Claim_FR_rec := Yes; end else i f (Frame.fC = Beacon.FR and M.Flag = 1) then begin T.Neg := T.Max; My.beacon := Yes; R.Flag := zero; Beacon.FR.rec := Yes; end else i f (Frame.fC = Beacon.FR and (M.Flag - 0 and E.Flag = 1)) then begin T.Neg := T.Max; Other.beacon := Yes; R.Flag := zero; Beacon.FR.rec := Yes; end else i f (E.Flag = 1) and (Frame.fS.e <> S) then Error.Ct := Error.Ct + one; APPENDIX C. EXCERPT OF ESTELLE. Y SPECIFICATION OF FDDI MAC PROTOCOLS END; TO Tx.data WHEN Token PROVIDED (Usable) OUTPUT Frame BEGIN Token.class := (Token.fC/64) mod 2; i f (Token.class = Restricted) then i f (R.Flag = zero) then begin R.Flag := one; SmMaStatusIndication.statusReport := 11; end else begin Reset(TVX); Start(TVX); R.Flag := zero; end; Stop(THT); i f Late.Ct = zero then begin Set(THT, Read(TRT)); APPENDIX C. EXCERPT OF ESTELLE. Y SPECIFICATION OF FDDI MAC PROTOCOL105 SetCTRT, T_Opr); Start(TRT); end else begin Set(THT, Timeout(THT)); Late_Ct := zero; end; Frame.pA := zero; Frame.sD.j := J; Frame.sD.k := K; Frame.fC := frame_FC; i f (frame_FC_Lr = 1) then Frame.dA.longAddress := frame_DA_L else Frame.dA.shortAddress := frame_DA_S; Frame.sA.longAddress := frame.SA; Frame.sA.shortAddress := frame_SA; Frame.info Frame.fCS Frame.eD Frame.fS.a Frame.fS.c Frame.fS.e = frame.INFO; = frame.FCS; = frame_ED; = R; = R = R nomoredata:= Yes; APPENDIX C. EXCERPT OF ESTELLE. Y SPECIFICATION OF FDDI MAC PROTOCOLS END; TO Claim.TK PROVIDED (Timeout(TVX) or (Timeout(TRT) and Late.Ct > zero) or (Ring.Operational and T_0pr < T.Req)) BEGIN T.Opr := T.Max; Set(TRT, T.Opr); Start(TRT); Ring.Operational := No; END; TO Tx.beacon WHEN SmMaCtrlReq PROVIDED (SmMaCtrlReq.ctrlAction = Beacon) BEGIN Set(TRT, T.Opr); Start(TRT); END; TRANS FROM Tx.data TO Tx.data PROVIDED (not nomoredata) APPENDIX C. EXCERPT OF ESTELLE. Y SPECIFICATION OF FDDI MAC PROTOCOL107 OUTPUT Frame BEGIN Frame.sD.j := J; Frame.sD.k := K; Frame.fC := frame.FC; Frame.sA.shortAddress := frame_SA; Frame.sA.longAddress := frame.SA; Frame.dA.shortAddress := frame_DA_S; Frame.dA.longAddress := frame_DA_L; Frame.info := frame.INFO; Frame.eD := T; Frame.fS.e Frame.fS.a Frame.fS.c END; = R; = R; = R; TO Tx.data WHEN MaUnitDataRequest BEGIN frame.FC := MaUnitDataRequest.fcValue; frame.FC.Lr := (frame_FC/64) mod 2; i f (frame.FC.Lr = one) then frame.DA.L := MaUnitDataRequest.destinationAddress.longAddress else frame.DA.S := MaUnitDataRequest.destinationAddress.shortAddress; frame.INFO := MaUnitDataRequest.mSDU; APPENDIX C. EXCERPT OF ESTELLE. Y SPECIFICATION OF FDDI MAC PROTOCOLS frame.SA := S.Addrs; req_service_class := MaUnitDataRequest.requestedServiceClass; frame_Token_class := MaUnitDataRequest.tokenClass; nomoredata := No; END; TO Rx.data WHEN SmMaCtrlReq PROVIDED (SmMaCtrlReq.ctrlAction = Mac_Reset) BEGIN T.Opr := T.Max; i f (Ring.Operational or Late.Ct = zero) then begin Set(TRT, T.Opr); Start(TRT); Late.Ct := one; Ring.Operational := No; end; END; TO Claim.TK PROVIDED (Timeout(TVX) or (Timeout(TRT) and Late.Ct > zero) or (Ring.Operational and T.Opr < T.Req)) BEGIN T.Opr := T.Max; Set(TRT, T.Opr); Start(TRT); APPENDIX C. EXCERPT OF ESTELLE. Y SPECIFICATION OF FDDI MAC PROTOCOL!^ Ring.Operational := No; END; TRANS FROM Issue.TK TO Rx.data OUTPUT Token I TO Issue.TK WHEN Frame TO Rx.data WHEN SmMaCtrlReq PROVIDED (SmMaCtrlReq.ctrlAction = Mac.Reset) or (SmMaCtrlReq.ctrlAction = Beacon) BEGIN T.Opr := T.Max; i f (Ring.Operational or Late.Ct = zero) then begin Set(TRT, T.Opr); Start(TRT); Late.Ct := one; Ring.Operational := No; end; APPENDIX C. EXCERPT OF ESTELLE. Y SPECIFICATION OF FDDI MAC PROTOCOL110 END; TO Claim.TK PROVIDED (Timeout(TVX) or (Timeout(TRT) and Late.Ct > 0) or (Ring.Operational and T.Opr < T.Req)) BEGIN T.Opr := T.Max; Set(TRT, T.Opr); Start(TRT); Ring.Operational := No; END; TRANS FROM Ck.frame TO Rx.data PROVIDED (FR.strip and not Claim.FR.rec and not Beacon.FR.rec) PRIORITY high OUTPUT MaUnitDataStatusIndication BEGIN MaUnitDataStatusIndication.numberOfSDUs := 1; MaUnitDataStatusIndication.transmissionStatus := trans.status; MaUnitDataStatusIndication.providedServiceClass := 1; END; end. Appendix D T E S T G E N menus ############################################ # Test Suite Generation - Prototype V.2 # ######################################«##### # = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = # # TSG Main Menu # # ============= # # # # Enter: # # p to access the parser menu, # # v to access the PDS v e r i f i c a t i o n menu, # # c to set or modify the TSG and SPP constraints, # # g to access the test case generation menu. # # # # - to return to previous menu, # # h for help, # # e to exit TSG. # #=====================================================================# 111 APPENDIX D. TESTGEN MENUS 112 #=====================================================================# # TSG Estelle/ASH.1 parser # # ======================== # # # # Ready to create PDS: # # - loading: asnl.tt # # - parsing: spec.txt # # Enter: # # 1 to create the PDS as specified, # # 2 to specify another ASN.l f i l e to load, # # 3 to specify another specification f i l e to parse. » # # # #=====================================================================# # -:previous, h:help, m:main, p:parser, c:constraints, g:gen...e:exit # #=====================================================================# #=====================================================================# # TSG PDS v e r i f i c a t i o n # # ===================== # # # # These functions allow to verif y the parsed PDS. Enter: # # 0 to check the consistency of the parsed PDS, # # # # 1 to display STATES, # # 2 to display TRANSITIONS, # # 3 to display ISPs (Input Service Primitives) # # 4 to display OSPs (Output Service Primitives) # # 5 to display PDUs (Protocol Data Units) # # 6 to display Parameter of Service Primitive # # 7 to display CONSTANTS, # # 8 to display VARIABLES, # # 9 to display TIMER, # # # # 1 to access the lower level PDS v e r i f i c a t i o n menu. # #=====================================================================# # -:previous, h:help, m:main, psparser, c:constraints, g:gen...e:exit # #============== === = = = = === = = = = = = = = = = = = = = = =^ APPENDIX D. TESTGEN MENUS 113 #=====================================================================# # TSG low l e v e l PDS v e r i f i c a t i o n # # =============================== # # # # These functions allow to ver i f y the parsed PDS. Enter: # # 1 to display Compound statements # # 2 to display If statements # # 3 to display Assignment statements # # 4 to display Timer statements # # 5 to display Timer expressions # # 6 to display Expressions # # 9 to display Efect Functions, # # * # v for high l e v e l PDS v e r i f i c a t i o n , # #=====================================================================# # -:previous, h:help, m:main, p:parser, c:constraints, g:gen...e:exit # #=====================================================================# #= _ # # Default setting of TSG Constraints « # # # # # STATES: min-use = 0 max-use = 99 # # TRANSITIONS: min-use - 0 max-use = 99 # # ISP: min-use = 0 max-use = 1 # # OSP: min-use = 0 max-use = 1 # # PDU: min-use = 0 max-use = 1 # # CONSTANTS: min-use = 0 max-use = 99 # # VARIABLES: min-use = 0 max-use = 99 # min-assigned = 0 max assigned = 99 # # TIMER Operations: min-start = 0 max-start = 99 # # min-stop = 0 max-stop = 99 • # # min-set = 0 max-set = 99 # # min-reset = 0 max-reset = 99 # # TIMER Condition checks: # # min-read = 0 min-read = 99 # # min-check -reseted = 0 min-check-reseted = 99 ' # # min-check -started = 0 min-check-started = 99 # min-check -stopped = 0 min-check-stopped = 99 # # min-check -timed-out = 0 min-check-timed_out = 99 # # # #= ====# APPENDIX D. TESTGEN MENUS 114 #==================================^ # Default setting of ISP Parameter # # ================================ # # # # ISP: MaUnitDataRequest # # + + + # # | Type | recognized ISP parameter name I # # + + - - + # # I int | MaUnitDataRequest.requestedServiceClass I # # | bool I MaUnitDataRequest.stream I # # I ... | . . . I # # + + + # # « # ISP: MaTokenRequest # # + + — + # # | Type I recognized ISP parameter name I # # + + - — — — + # # | int | MaTokenRequest.requestedTokenClass I # # + + - + # # # # ISP: SmMalnitProtocolReq # # + + - — + # # | Type I recognized ISP parameter name I # # + + - + # # | char*| SmMalnitProtocolReq.indivMACaddrS I # # | bool | SmMalnitProtocolReq.indForRcvOnlyGoodFr I # # I ... | . . . I # # + + — - - + # # . . . # # # # PDU: Frame # # + + - + # # | Type | recognized PDU parameter name I # # + + + # # | char*| Frame.pA I # # I int | Frame.sD.j I # # I ... I . . . I # # + + + # # . . . # # # # NOTE: Constraints are only defined for the parameters l i s t e d above. # # Booleans (bool ) parameters are constraint to: TRUE, FALSE # # Interger (int ) parameters are constraint to: 0, 1, 999 # # Cstrings (char*) parameters are constraint to: 'parm.vall' # #=====================================================================# APPENDIX D. TESTGEN MENUS 115 #============================ =============================== ======^ ^ # Default setting of PDU Parameter # # ================================ # # # # PDU: Frame # # + + - —+ # # | Type | recognized PDU parameter name I # # + + + # # I char*I Frame.pA I # # I int I Frame.sD.j I # # I int | Frame.sD.k I # # I ... | . . . I # # + + - + # # # # PDU: Token # # + + + # # | Type | recognized PDU parameter name I # # + +-- + # # | char*I Token.pA I # # I int | Token.sD.j I # # | int I Token.sD.k I # # I ... I . . . I # # + + + # # # # NOTE: Constraints are only defined f o r the parameters l i s t e d above. # # Booleans (bool ) parameters are constraint to: TRUE, FALSE # # Interger (int ) parameters are constraint to: 0, 1, 999 # # Cstrings (char*) parameters are constraint to: 'parm.vall' # #=====================================================================# APPENDIX D. TESTGEN MENUS 116 #=====================================^ # Interactive Constraint Definition # # ================================= # # # # The Test Suite Generation (TSG) allow to control the subtour # # selection mechanism. Enter: # # 1 to reset the TSG constraints to default values, # # t to c a l l the TSG constraint editor. # # # # The Service Primitive Parameter (SPP) constraints and the Protocol # # Data Unit Parameter (PDUP) constraints define the values of # # parameters of the service primitives sent to the IUT. Enter: # # 2 to reset the SPP constraints to default values, # # s to c a l l the SPP constraint editor, # # # # The Service Primitive Parameter (SPP) constraints and the Protocol # # Data Unit Parameter (PDUP) constraints define the values of # # parameters of the service primitives sent to the IUT. Enter: # # 3 to reset the PDUP constraints to default values, # # u to c a l l the PDUP constraint editor. # # # #=====================================================================# # -:previous, h:help, m:main, p:parser, c:constraints, g:gen...e:exit # #=====================================================================# #=====================================================================# # Interactive Constraint Definition # # ================================= # # # # These functions allow to view and specify constraints on the # # the following Primitives. Enter: # # 1 to specify STATES constraints, # # 2 to specify TRANSITIONS constraints, # # 3 to specify ISPs (Input Service Primitives) constraints, # # 4 to specify OSPs (Output Service Primitives) constraints, # # 5 to specify PDUs (Protocol Data Units) constraints, # # 6 to specify CONSTANTS constraints, # # 7 to specify VARIABLES constraints, # # 8 to specify TIMER constraints, # # # #=====================================================================# # -:previous, h:help, m:main, p:parser, c:constraints, g:gen...e:exit # #=====================================================================# APPENDIX D. TESTGEN MENUS 117 # TSG Constraints Editor ( STATE ) # # ================================ # # (a) (b) # # + + + + + # # | key | Name I min-use I max-use I # # + + + +_— + # # 1 0 I Rx.data I 0 I 99 I # # I 1 I Ck.frame I 0 I 99 I # # 1 2 | Tx.data I 0 | 99 I # # I ... I . . . I I ! I # # + + + - + — T + # # ; # # Enter # # 'key' [ab] 'value' :to change the value of a state constraint. # # (ex: '2a3' w i l l set the min-use (a) of state 2 (key) to 3 (value)) # # # # t to return to the main TSG constraint editor menu | # #=====================================================================# # -:previous, h:help, m:main, p:parser, c:constraints, g:gen...e:exit # #=====================================================================# #=====================================================================# # TSG Constraints Editor ( TRANSITION ) # # ===================================== # # (a) (b) # # + + + + + + + # # | key | Name I ISP name I OSP name I min-use I max-use I # # + + + + + +—. + # # I 0 | - | PhUnitData | PhUnitData I 0 I 99 I # # I 1 I - | SmMaCtrlRe | - | 0 I 99 I # # I 2 | - | MaUnitData I - I 0 I 99 I # # | 3 | — | - | - | 0 I 99 |# # | 4 | — | - | - | 0 | 99 |# # | 5 | - | - | - | 0 | 99 |# # I 6 | - I- | - | 0 I 99 |# # | 7 | - | SmMaCtrlRe I - I 0 I 99 I # # I ... I . . . I I I I I # # + + + + + + # # Enter # # 'key' [ab] 'value' :to change the value of a trans constraint. # # (ex: '2a3' w i l l set the min-use (a) of trans 2 (key) to 3 (value)) # # # # t to return to the main TSG constraint editor menu # #============== ======================^ # -:previous, h:help, m:main, p:parser, c:constraints, g:gen...e:exit # I APPENDIX D. TESTGEN MENUS 118 # TSG Constraints Editor ( ISP ) # # ============================== # # (a) (b) # # + + + + + # # | key I Name I min-use I max-use I # # + + — — + + — + # # | 0 | MaUnitDataRequest I 0 I 1 I # # | 1 | MaTokenRequest I 0 I 1 I # # | 2 I PhUnitDatalndication I 0 I 1 I # # + + + + + # # # # Enter # # 'key' [ab] 'value' :to change the value of a ISP constraint. # # (ex: '2a3' w i l l set the min-use (a) of isp 2 (key) to 3 (value)) # # # # t to return to the main TSG constraint editor menu # # . = . . = T ===# # -:previous, h:help, m:main, p:parser, c:constraints, g:gen.:.e:exit # #=====================================================================# # TSG Constraints Editor ( OSP ) # # ============================== # # # # (a) (b) # # + + - — + — -+- + # # I key I Name I min-use I max-use I # # + + - - — -+— + -+ # # | 0 I MaUnitDatalndication I 0 I 1! I # # I 1 | MaUnitDataStatusIndication I 0 I 1 I # # | 2 I PhUnitDataRequest I 0 I 1 I # # + + + + + # # # # Enter # # 'key' [ab] 'value' :to change the value of a OSP constraint. # # (ex: '2a3' w i l l set the min-use (a) of osp 2 (key) to 3 (value)) # # # # t to return to the main TSG constraint editor menu # #=====================================================================# # -:previous, h:help, m:main, p:parser, c:constraints, g:gen...e:exit # #=====================================================================# APPENDIX D. TESTGEN MENUS 119 #=====================================================================# # TSG Constraints Editor ( PDU ) # # ============================== # # # # (a) (b) # # + + + +— + # # | key | Name I min-use I max-use I # # + + + + + # # 1 0 I Frame I 0 I 1 I # # 1 1 | Token I 0 I 1 I # # + + _ + + + # # ! # # Enter # # 'key' [ab] 'value' :to change the value of a PDU constraint. # # (ex: '2a3' w i l l set the min-use (a) of pdu 2 (key) to 3 (value)) # # # # t to return to the main TSG constraint editor menu # #=====================================================================# # -:previous, h:help, m:main, p:parser, c:constraints, g:gen...e:exit # #=====================================================================# #=====================================================================# # TSG Constraints Editor ( CONSTANTS ) # # ==================================== # # # # (a) (b) # # + + + + + # # I key | Name I min-use I max-use I # # + + + +--• + # # | 0 | I 10 | 99 I # # I 1 I J | 0 | 99 I # # | 2 | K | 0 | 99 I # # | 3 I R | 0 | 99 | # # I 4 I S 10 | 99 I # # I 5 I T 10 | 99 I # # + + + + + # # # # Enter # # 'key' [ab] 'value' :to change the value of a const constraint. # # (ex: '2a3' w i l l set the min-use (a) of const 2 (key) to 3 (value)) # # # # t to return to the main TSG constraint editor menu # #==================== ======= =============== ========= ==============# # -:previous, h:help, m:main, p:parser, c:constraints, g:gen...e:exit # #=====================================================================# APPENDIX D. TESTGEN MENUS 120 #=====================================================================# # TSG Constraints Editor ( VARIABLES ) '< # # ==================================== # # # # (a) (b) (c) (d) # £ + + + + + + + # # I key I Name I I I min- I max- I # # | key | Name I min.use I raax.use I assigned I assigned I # # + + + + + + — . + # # | 0 | MSA 10 I 99 10 | 99 I # # I 1 I MLA 10 I 99 10 | 99 I # # | 2 | n | 0 | 99 10 | 99 I # # 1 3 | T.Opr 10 I 99 I 0 | 99 I # # 1 4 I T.Bid.Rc I 0 I 99 I 0 I 99 I # # 1 5 | T.Bid.Tx I 0 I 99 I 0 I 99 I # # + + + + + + 1 + # # # # Enter # i # 'key' Cab] 'value' :to change the value of a VARIABLE constraint. # # (ex: '2a3' w i l l set the min-use (a) of var 2 (key) to 3 (value)) # # # # t to return to the main TSG constraint editor menu j # #=====================================================================# # -:previous, h:help, m:main, p:parser, c:constraints, g:gen...e:exit # #=====================================================================# APPENDIX D. TESTGEN MENUS 121 #============================== =^ # TSG Constraints Editor ( TIMER ) # # ================================ # # # # Timer actions I (a) (b) (c) (d) (e) (f) (g) (h) # # + + + + + + + + + + + # # | | | min | max I min I max I min I max I min I max I # # | key I Name I start I start I stop I stop I set I set I r e s e t I r e s e t I # # + + + + + + + + + + + # # 1 0 | TVX | 0 | 99 | 0 | 99 | 0 I 99 I 0 I 99 I # # 1 1 | THT 1 0 I 99 | 0 I 99 I 0 I 99 I 0 I 99 I # # 1 2 I TRT 1 0 | 99 | 0 I 99 I 0 I 99 I 0 I 99 I # # + + + + + + + + + + + # # # # Timer conditions I (i) (j) (k) (1) (m) (n) (o) '(p) (q) (r) # + + + + + + + + + + + + + # 1 1 I min I max I min I max I min I max I min I max I min I max I # | key | Name I check read I check reset I check start I check stopdlcheck timotl # + + + + + + + + + + + + + # 1 0 I TVX | 0 | 99 | 0 I 99 I 0 I 99 I 0 I 99 I 0 I 99 I # | 1 I THT 1 0 | 99 I 0 I 99 | 0 | 99 | 0 I 99 I 0 I 99 I # | 2 | TRT | 0 | 99 | 0 | 99 | 0 I 99 I 0 | 99 I 0 I 99 I # + + + + + + + + + + + + + # # # Enter # # 'key' [ab] 'value' :to change the value of a timer constraint. # # (ex: '2a3' w i l l set the min-use (a) of timer 2 (key) to 3 (value)) # # # # t to return to the main TSG constraint editor menu # #=====================================================================# # -:previous, h:help, m:main, p:parser, c:constraints, g:gen...e:exit # # = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = # APPENDIX D. TESTGEN MENUS 122 #=====================================================================# # Interactive Service Primitive Parameter De f i n i t i o n # # ================================================== # # # # + + + + + # # I key | Input Service Primitive name | # parm. I # inst. I # # + + — + + + # # I 0 | MaUnitDataRequest I 7 I 64 I # # I 1 | MaTokenRequest I 1 I 2 I # # I 2 | PhUnitDatalndication I 1 I 2 I # # I 3 1 PhUnitDataStatusIndication I 1 I 2 I # # I 4 | Phlnvalidlndication I 1 I 2 I # # I 5 | SmMalnitProtocolReq I 11 I 256 I # # I 6 | SmMaCtrlReq I 10 I 512 I # # + + + + + # # # # Enter # # 'key' to define the parameter of the corresponding ISP, # #=====================================================================# # -:previous, h:help, m:main, p:parser, c:constraints, g:gen...e:exit # #=====================================================================# #=====================================================================# # Interactive Protocol Data Unit Parameter Definition # # =================================================== * # # # + + + + + # # | key | Protocol Data Unit name I # parm. I # inst . I # # + + +___ + + # # I 0 | Frame I 14 I 2048 I # # I 1 | Token I 5 I 16 I # # + + + + + # # # # Enter # # 'key' to define the parameter of the corresponding PDU, # #=====================================================================# # -:previous, h:help, m:main, p:parser, c:constraints, g:gen...e:exit # #=====================================================================# APPENDIX D. TESTGEN MENUS 123 #=========================================================== # Test Suite Generation # # ===================== # # # # Enter: # # 1 to estimate the number of subtours, # # 2 to identify and store the subtours, # # 3 to store and print the i d e n t i f i e d subtours, # # # # 5 to generate test cases f o r a l l subtours. # # * #=====================================================================# # -:previous, h:help, m:main, p:parser, c:constraints, g:gen...erexit # #=====================================================================# Appendix E Consistency Requirements of PDS Following are consistency requirements that must be satisfied by a protocol data structure. The defined conditions reflect the properties of the Protocol Data Structure. The conditions are used to verify the consistency of a protocol data structure. General conditions on the Protocol Data Structure: General conditions i s examplified with STATE structure. Similar conditions apply to TRANS, ISP, OSP, PDU, SPPARM, CONST, VAR, TIMER, EXPR, TEXPR, AFN, ASTMT, IFSTMT, WSTMT and TSTMT. ppds->nb_of_states <= MAXSTATES ppds->nb_of.states == # (instances of STATE) fo r a l l 0 < i < ppds->nb_of.states ppds->pstate[i]->key = i for a l l i >= nb.of.states ppds->pstate[i] == NULL pointer f o r a l l STATE instances ppds->pstate[i]->key = i 124 APPENDIX E. CONSISTENCY REQUIREMENTS OF PDS 125 where ppds i s the pointer to main data structure of a PDS. STATE: fo r a l l instances of STATE ( i . e . states), f o r a l l 0 < i < nb_of_tr ppds->pstate[tr_key[i]]->form_state = key; fo r a l l i >= nb_of_tr tr_key[i] == NULL pointer; TRANSITION: fo r a l l instances of TRANS ( i . e . t r a n s i t i o n s ) , there exists an i so that: ppds->pstate[from_st]->tr_key[i] == key; from_st < ppds->nb_of.states to_st < ppds->nb_of.states isp < ppds->nb_of_isps osp < ppds->nb_of_osps osp2 < ppds->nb_of_osps ipdu < ppds->nb_of_pdus opdu < ppds->nb_of_pdus opdu2 < ppds->nb_of_pdus epred < ppds->nb_of_exprs afn < ppds->nb_of_afns ISP: f o r a l l input service primitives, nb_of_pdus < ppds->nb..of_pdus; APPENDIX E. CONSISTENCY REQUIREMENTS OF PDS 126 for a l l 0 < i < nb_of_pdus; ppds->ppdu[pdu_key[i]]->sent_in == key; for a l l i >= nb_of_pdus; pdu_key[i] == NULL pointer; OSP: for a l l output service primitives, nb_of_pdus < ppds->nb_of_pdus; for a l l 0 < i < nb_of_pdus; ppds->ppdu[pdu_key[i]]->recv_in == key; for a l l i >= nb_of_pdus; pdu_key[i] == NULL pointer; PDU: for a l l protocol data units, (sent.in != NONE) OR (recv.in != NONE) OR (pco != NONE); i f (sent.in != NONE) there exists an i so that: ppds->pisp[sent_in]->pdu_key[i] == key; i f (recv_in != NONE) there exists an i so that: ppds->posp[recv_in]->pdu_key[i] == key; CONSTANT: for a l l constants, type must be a member of set {BOOLEAN.TYPE, INTEGER.TYPE, CHAR.STRING.TYPE} i f (type == BOOLEAN.TYPE) { int_value == 0; char_ptr == NULL pointer; APPENDIX E. CONSISTENCY REQUIREMENTS OF PDS 127 } i f (type == INTEGER.TYPE) { boolean.value == 0; char.ptr == NULL pointer; > i f (type == CHAR_STRING_TYPE) { int.value == 0; boolean.value == 0; } VARIABLE: for a l l variables, type must be a member of set {BOOLEAN.TYPE, INTEGER.TYPE, CHAR_STRING_TYPE} TIMER: timeout.value > 0; Help function: _result_type( x.kind, x, check.type) •c i f (x.kind == VAR) pds->pvar[right]->type == check.type; i f (x.kind == CONSTANT) pds->pconst[right]->type == check.type; i f (x.kind == EXPR) _result_type(pds->pexpr [right]) == check.type; APPENDIX E. CONSISTENCY REQUIREMENTS OF PDS 128 > EXPRESSION: for a l l expressions, i f (operator == not) { le f t . k i n d ~ NONE; right.kind != NONE; .result.type(right.type, r i g h t , BOOLEAN.TYPE) > i f ((operator == and) or (operator == or)) •C l e f t . k i n d != NONE; right.kind != NONE; .result.type(left.type, l e f t , BOOLEAN.TYPE) .result.type(right.type, r i g h t , BOOLEAN.TYPE) > i f (operator i s one of {+, -, *, div, mod}) { l e f t . k i n d != NONE; right.kind != NONE; .result.type(left.type, l e f t , INTEGER.TYPE) .result.type(right.type, r i g h t , INTEGER.TYPE) } i f (operator i s one of {=, <, >, >=, <=, !=}) { le f t . k i n d != NONE; right.kind != NONE; .result.type(left.type, l e f t , INTEGER.TYPE) APPENDIX E. CONSISTENCY REQUIREMENTS OF PDS 129 _result_type(right.type, r i g h t , INTEGER.TYPE) > Timer EXPRession: status i s one of {RESET, STARTED, STOPPED, TIMED.OUT} ACTION FUNCTION: fo r a l l i < nb.of.statements { stmt_kind[i] i s one of { ASTMT, IFSTMT, TSTMT } i f (stmt_kind[i] == ASTMT) stmt_key[i] < MAXASTMT; i f (stmt_kind[i] == IFSTMT) stmt_key[i] < MAXIFSTMT; i f (stmt.kind[i] == TSTMT) stmt.key[i] < MAXTSTMT; } IF Statement: _result_type(expr, bool.expr, BOOLEAN.TYPE) stmt.kind i s one of { ASTMT, IFSTMT, TSTMT } else.stmt.kind i s one of { ASTMT, IFSTMT, TSTMT } Assignment Statement: The type of l e f t kind must be the same as the type of right expression. Timer Statements: timer.operator i s one of {START, RESET, STOP}
Thesis/Dissertation
eng
Computer Science
Vancouver : University of British Columbia Library
For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
Graduate
On TESTGEN, an environment for protocol test sequence generation, and its application to the FDDI MAC protocol
Text