@prefix vivo: . @prefix edm: . @prefix ns0: . @prefix dcterms: . @prefix dc: . @prefix skos: . vivo:departmentOrSchool "Science, Faculty of"@en, "Computer Science, Department of"@en ; edm:dataProvider "DSpace"@en ; ns0:degreeCampus "UBCV"@en ; dcterms:creator "Đõ̂, Bình"@en ; dcterms:issued "2009-02-03T19:12:55Z"@en, "1996"@en ; vivo:relatedDegree "Master of Science - MSc"@en ; ns0:degreeGrantor "University of British Columbia"@en ; dcterms:description "The success of any today large-scale software depends largely on the techniques applied to different phases of its whole life cycle. Various formal methods arid testing methods are developed to be applied to the specification phase and testing phase. Based on,the author's own experience as a member of a team implemeriting the Information Search and Retrieval Protocol, the Z39.50, this thesis explores application of formal methods and a methodology from a practical point of views."@en ; edm:aggregatedCHO "https://circle.library.ubc.ca/rest/handle/2429/4157?expand=metadata"@en ; dcterms:extent "4733154 bytes"@en ; dc:format "application/pdf"@en ; skos:note "APPLYING FORMAL METHOD IN THE IMPLEMENTATION OF THE INFORMATION RETRIEVAL PROTOCOL Z39.50 B y Binh Do B. Sc. (Mathematics) Charles' University, Prague, 1977 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF T H E REQUIREMENTS FOR T H E D E G R E E OF M A S T E R O F SCIENCE in T H E FACULTY OF GRADUATE STUDIES COMPUTER SCIENCE • We accept this thesis as conforming to the required standard T H E UNIVERSITY OF BRITISH COLUMBIA January 1996 © B i n h Do, 1996 In presenting this thesis in partial fulfillment of the requirements for an advanced degree at the University of Br i t i sh 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. Computer Science The University of Br i t i sh Columbia 2366 M a i n M a l l Vancouver, Canada V 6 T 1Z4 Date: Abstract The success of. any today large-scale software depends largely on the techniques applied to different phases of its whole life cycle. : / ' • Various formal methods arid testing methods are developed to.'be applied to the specification phase and testing phase. Based on,the author's own experience as a member of a team implemeriting the Information Search and Retrieval Protocol, the Z39.50, this thesis explores application of formal methods and a methodology from a practical point of views. . .. ' •'• ' '. V\\' • .11 Table of Contents Abstract ii List of Figures 1 ; vi Acknowledgment vii 1 INTRODUCTION 1 •. .1.1 • .-Introduction . . . . . . ... . . . , . •;- . . . •.= •; . . . . . . . . . . •: . . . . . . . 1 1.2 Motivat ion and.objective . . . . . . . . . . . . : . . . . . . . . . . . . ..... . . • 2 1.3 Thesis outline ; ..'. . . ... . .. •.;.-. • • • 2 2 BACKGROUND 4 •2.1 The OSI Reference M o d e l . . 1 4 2.2 T C P / I P Protocol .Suite . . . . . . . . . . . :\"V : . . ... . . . . . . . . . . .\". 6 : f 2.3 T E S T G E N . . . . : . ; . . . . . ;. . . . . . . . . . . . . . . . . . 8 . 2.3.1 M^otivation . . . 8 2.3.2 Internal representation of protocol;. . . . . . . . . . . . . . . . . 9 3 INFORMATION RETRIEVAL PROTOCOL Z39.50 17 3.1 Basics Of The P r o t o c o l , . . . . . . .: ... . .. . . . . . . . . 17 3.2 Information Retrieval (IR) Service . . . . . . . . . . . . . . . . . . . . . . . 21 3:2.1 Z39.5Q services and their usage . . . . . . 21 3:2.2 Mode l and Characteristics of the Information Retrieval Service . . 23 3.2.3 Types of Z.39 .'50-services . . . . . . . . . . . . . . . . . . . . .-: . . . 23 i i i 3.2.4 Z39.50 Operations . . , 23 3.2.5 Facilities of the Z39.50 service. . 24 3.2.6 A typical scenario of Z39.50 . .... . , . . . . . . . . . . . . . . . . . . 27 3.3 The implementation of Z39.50 at E B S C O Publishing company . .. . ;. . . . 28 . 3.3.1 Objective . . . . . . , . . . . . . . . 28 3.3.2 Programming language and tools used in the implementation . . . 30 4 APPLYING TESTGEN TO Z39.50 PROTOCOL 31 4.1 Motivat ion for applying T E S T G E N 31 ; 4.2 The simplified Z39.50 used in T E S T G E N . . 32 4.2.1 Estel le .Y and A S N . l specification . . ', . . . . . . . . . . . . . . . . . 33 4.3 Results . . . . . . . . . . . . . . . . . . . '.-'. . . . . . . . . . . 39 4.3.1 Init ial result . . . . \": 39 4.3.2 Constraint modification 40 4.3.3 Test coverage . . . . . 41 4.4 Summary 44 5 FSM-BASED APPROACH TO PROTOCOL CODING 46 5.1 Motivat ion 46 5.2 State tables . . . ' . , 47 5.3 How to create a finite state machine 50 5.4 Summary 52 6 SOME EXPERIENCE AND REMARKS 54 6.0.1 Advantages of T E S T G E N 54 6.1 Disadvantages of T E S T G E N .'. . . . . . . . . ' : / 56 i v 7 CONCLUSIONS AND FUTURE WORK 58 7.1 Summary) of important results . . . . 58 7.2 Future work- . .' .' •• • • . . . . . . . . . . . . . . . . . , 58. Bibliography 60 Appendices 63 A Estelle.Y specification of the simplified Z39.50 used in TESTGEN 63 B ASN.l specification of the simplified Z39.50 used in TESTGEN 71 C Constraints defined in TESTGEN menus . ' 80 D Some test cases with defined constraints without coverage 91 E The set of selected test cases using test coverage tool 97 F Test cases in TTCN form 101 G State tables used for Z3950 protocol 105 H Function processing the State Machine 111 I Test cases generated semiautomatically 115 v List of Figures 2.1 The OSI Reference Model 5 2.2 T C P / I P stack compared wi th OSI stack . . . 7 2.3 The process of generating test cases using T E S T G E N 13 3.4 The relationship of Appl icat ion Entities and Service Providers in Z39.50.. 19 3.5 The Z39.50 services and their characteristics 25 3.6 A typical scenario of Z39.50 29 4.7 The F S M for simplified Z39.50 protocol, used in T E S T G E N . . . . . . . . . 35 5.8 The state table for Z39.50 Target main processing 49 5.9 The state table for Z39.50 Target search processing 50 5.10 The state table for Z39.50 Target retrieval (present) processing . . . . , . . 51 v i Acknowledgment First of al l , I would like to express my deep gratitude to Dr . Son T . Vuong, my supervisor, for his guidance, encouragement and commitment during my time at U B C as a visit ing scholar and as a M S c student. More than that I also owe h i m for being one of my greatest friends in my daily life. Secondly, I would like to express my sincere thanks to Dr . N o r m Hutchison for his helpful comments and careful reading of the final draft despite his very busy schedule. I cannot forget to mention some people from E B S C O Publishing Company who intro-duced me to the Z39.50 protocol, helped me a lot during its implementation, encouraged me to write on Z39.50 protocol and allowed me to use some of the information related to the implementation. They are M r . Oliver Pesch, Dr . Tadeusz Orlowski , M r . Lech Woitojwisz, M r . Chris Taylor and M r . Charles Evans. M y time being wi th them was wonderful and unforgettable. I really enjoyed working wi th them. I also would like to thank Michael McAl l i s t e r for the explanation of his coverage tool. I really appreciate his spending time reading the thesis draft and making very good suggestions about i t , and for letting me use the machine in our office room most of the time we both were in . M y thanks also belong to R u i Zhang who did not mind answering al l my boring and stupid questions about T E S T G E N and who let me use her tool to generate the test cases in T T C N form. Last but not least, I would like to thank my wife Ka thy B u i and my son Jackson Dp for being my wonderful family and for their endless love during the course of the thesis. vn Chapter 1 INTRODUCTION 1.1 Introduction Most protocols have been implemented and tested in ad hoc manners, especially in indus-tr ia l environments. To increase the probability that different protocol implementations can inter-operate with each other, the International Standards Organization (ISO) de-veloped the Conformance Testing Methodology and Framework [ISO-9646]. According to the conformance testing methodology, an implementation conforms to the protocol standards if, it fulfills the requirements defined in the ISO 9646 standard. -The test method is based on the black-box principle. Conformance testing is carried out by using test suites which in turn consist of a complete set of test cases. The ISO also defines the Tabular and Tree Combined Notation ( T T C N ) [ ISO-TTCN] to specify abstract test suites. Several protocol test generation methods such as T-method [Nai-81], U-method [Sab-88], D-method [Gon-70], W-method [Cho-78] and T E S T G E N [Vuo-94] have been developed to generate test suites for a given protocol. So far these methods are advocated by researchers and are used mainly in academic environments. -• •'• . As a member of a software team implementing the Search and Information Retrieval Protocol Z39.50, the author would like to explore the application of one of the formal methods, namely T E S T G E N to generate a test suite semi-automatically. Furthermore since this method is based on the Protocol Specification in Fini te State Machine ( F S M ) Chapter 1. INTRODUCTION 2 notation, a practical usage of F S M in coding is also explored in detail. 1.2 Motivation and objective The success of any of today's software largely depends on the software engineering tech-niques applied to each phase of its whole life cycle such as specification, design, proto-typing, implementation, unit and integrated testing and maintenance. The testing phase is usually very time consuming and very costly. Using test generation methods can help to generate complete test suites quickly and possibly semiautomatically, thus reducing the cost and efforts. The objective is to show how a formal method and its test generation tool can be applied to an implementation of a well-known real-life and complex protocol, the Infor-mation Search and Retrieval Protocol Z39.50. The advantages and disadvantages wi l l be discussed to allow for improvements in future versions of the tool. Beside the popularity and complexity, another reason I chose Z39.501s that Iworked on its implementation for a while and therefore had gained some knowledge about i t . 1.3 Thesis outline Chapter 2 gives an overview of the OSI Reference model and T C P / I P protocol, as well as the T E S T G E N tool. • Chapter 3 introduces the Z39.50 protocol as it w i l l be used as an example through the next chapters. Chapter 4 introduces the application of a formal method in the implementation of the Z39.50 protocol. Emphasis is placed on using T E S T G E N to generate conformance test cases in the form of subtours and T T C N , and some issues related to test coverage. Chapter 1. INTRODUCTION 3 Chapter 5 presents a practical technique using Fini te State Machine in the actual coding process of the Z39.50 implementation. Chapter 6 discusses experiences, advantages and issues in the pragmatic methodology as learned from the implementation of the Z39.50 protocol. Specifically, advantages and limitations of T E S T G E N tool are exposed here. The last chapter,. Chapter 7, summarizes some important issues and discusses poten-t ial relevant future work. Chapter 2 BACKGROUND The IR Z39.50 protocol is defined as an application layer protocol wi thin the OSI reference model and the presence of lower-level OSI services are assumed. Many organizations and institutions implementing this.protocol (including my previous employer), however, chose to layer Z39.50 directly over T C P / I P rather than implement it in an OSI environment. Therefore I include, the basics of OSI as well.as T C P / I P in this chapter. The tool to generate the conformance test cases, developed by our group under the supervision of Dr . Son Vuong, is also introduced. . 2.1 The OSI Reference Model During 1970's the International Standards Organization (ISO) began working on a set of protocol standards for data communication between computers. Their goal was to develop standards which were not proprietary to a particular vendor nor of interest only to a small subset of the international community. The result of this effort is the basic model ISO Open Systems Interconnection (OSI) seven-layer model. It is described in ISO 7498 and formally called Open Systems Interconnection - Basic Reference Model. It deals,with connecting open systems - that is, systems that are open for communication with other systems. . ' ' , Figure 2.1 depicts the seven OSI layers. . . 4 Chapter 2. BACKGROUND 5 Application Layer Application Layer Presentation Layer Presentation Layer Session Layer Session Layer . Transport Layer Transport Layer Communication Subnet Network Layer . Network Layer Datalink Layer Datalink Layer Physical Layer Physical Layer —* Figure 2.1: The OSI Reference Model 1. The Physical Layer is concerned wi th transmitting raw bits over a communication channel. It deals mainly with electrical and mechanical characteristics of the media. 2. The Datalink Layer is responsible for taking a raw transmission facility and trans-forming it into a line that appears free of transmission errors to the network layer. In the case of a Local Area Network ( L A N ) , this layer is divided into two sublayers known as Logical .Link Control ( L L C ) and M e d i u m Access Control ( M A C ) . L L C is responsible for error management so that it can guarantee error-free transmission while M A C detects errors in the transmission of a single frame. 3. The Network Layer is concerned wi th controlling the operation of the subnet. B a -sically, it provides addressing and routing services allowing stations, not physically connected to the same network l ink, to communicate wi th each other. Chapter-2. BACKGROUND ' . 6 4. The Transport Layer is. responsible for reliable and transparent data transfer be-tween two end systems. It is also supposed to perform end-to-end flow control, which prevents fast transmitters from overrunning the buffer capacity of slower receivers. . • ! 5. The Session Layer provides various connection management services, specially full-duplex or half-duplex connections and graceful closing of connections. 6. The Presentation Layer is concerned wi th the syntax and semantics of the informa-tion transmitted. It allows heterogeneous computers architectures and operating systems to transmit complex data structures between systems and have the content and meaning of the data structures preserved. 7. The Appl ica t ion Layer provides a set of services accessible by an application pro-. grammer v ia high level interfaces. Appl ica t ion layer software is often responsible for the semantic verification of data transferred between systems. '. In this model, there is a strict division between each of the seven layers. Each layer in the stack provides a set of services to the layer above and requests services from the layer below. The interface to each layer is a set- of primitives.which are part of the protocol service specification. The adjacent layers communicate,to each other through service access points ( S A P ) . Data, is sent between systems in ;a packet called a Protocol Data Unit (PDU). ; , . 2.2 TCP/IP Protocol Suite Even though OSI is important and complete, its development is very expensive and besides,^over 95 percent of networking products are not OSI [Jam-95], In industry, the more well-known and widely used networking protocol suite is T C P / I P (stands for Chapter 2. BACKGROUND 7 TCP/IP protocol suite OSI APPLICATION LAYER Application layer Presentation Layer Session Layer TCP .• Transport Layer IP Network Layer LINK LAYER Datalink Layer Physical Layer Figure 2.2: T C P / I P stack compared with OSI stack Transmission Control Protocol/Internet Protocol), developed by the U . S . Department of Defense Advanced Research Project Agency ( D A R P A ) in the 1970's. The T C P / I P protocol suite also utilizes the layered architecture approach and it has four layers: Appl ica t ion, T C P , IP and Link layers. Figure 2.2. contrasts these layers with the layers in the OSI. stack. Also note that despite the name, T C P and IP are only two of the layers. 1. The Link Layer performs similar tasks of the Data Link Layer and Physical Layer of the OSI model. It generally consists of I E E E 802 protocol, X.25 protocol.or Chapter 2. BACKGROUND 8 V . 3 2 / V . 3 5 , two C C I T T standards defining transmission of digital data over'tele-phone lines. The IP performs tasks similar to the ones of the OSI Network Layer, that is, to manage the switching and routing of messages across the network from one end system to the other. The T C P provides a reliable transfer of data between end systems using end-to-end error recovery and flow control. The Appl icat ion Layer is responsible for implementing al l services of the OSI ses-sion, presentation and application layers. 2.3 TESTGEN The T E S T suite Generation and selection ENvironment ( T E S T G E N ) is developed by the University of Br i t i sh Columbia (see [Vuo-94]) and is a tool to generate conformance test cases for communication protocols based on their internal representation in a formal language, Estelle, and their data part representation in Abstract Syntax Notation 1 ( A S N . l ) . - ' 2.3.1 Motivation In order to generate a test suite, the protocol specification must be formalized and acces-sible by the test generation engine. T E S T G E N uses a representation based,on extended Transition System (ETS) and A S N . l to capture syntactical information (type definition of service primitives and parameters) and nondeterminism and implementation choices of the protocol. Chapter 2. BACKGROUND 9 The E T S + A S N . l knowledge is stored in a structure called a Protocol Data Structure (PDS) and wi l l be used by the engine to generate the test suite. 2.3.2 Internal representation of protocol ETS The Extended Transition System (ETS) model is based on Keller 's Labelled Transition Systems [Kel-76]. Some Estelle terminology is borrowed in naming some of the E T S elements. • . . . . A n Extended Transition System (ETS) is a quadruple ETS = (Q, E, — q i n i t ) where • Q is the set of states of the E T S , ; , • E is the set of events of the E T S , • —»C Q x E X Q'is the transition relation for the E T S , • Qinit € Q is the ini t ia l state of the E T S , • The set of states Q denotes the set product: Q = STATES x VAR x C x TIMER where S T A T E S is the set of control states and V A R is the set of data states. The control states and the data states respectively correspond to the E F S M major state and minor states. G (constants) is a set of fixed variables used to represent protocol characteristics that are invariant to the protocol execution. T I M E R is the set of t ime constructs used to specify time in the protocol representation. T I M E R predicates and operations are described in Section 2.1.4; Qinit represents the in i t ia l control state Sinu and the in i t ia l values of al l variables (€ V A R ) and timers (G T I M E R ) . Chapter 2. BACKGROUND 10 The set of events E denotes the set union : E = ISP U OSP U PDU. where ISP is the set of Input Service Primit ives (ISPs) accepted at the protocol's Service Access Points (SAPs) , OSP is the set of Output Service Primit ives (OSPs) offered at the protocol's S A P s and PDU represent the set of Protocol Data Units (PDUs) that can be embedded in ISPs or OSPs . A transition -^ is represented by a pair < Pt,Ft >, where Pt is the enabling predicate on the set product Q x E and Ft is the action function on the set product Q x E, which affects variables in V A R , timers in T I M E R and parameters of OSPs and P D U s . A transition can be executed if and only if the ISP and P D U associated wi th the transition (if any) are received and if the enabling predicate is true, or a timer expires. When a transition fires the associated action function is executed atomically. Variables and timers are set, OSP(s) and P D U ( s ) are assembled (their parameters are set) and sent. The semantics of the enabling predicates and the action functions are similar to the semantics of the Estelle enabling clauses and statements except for two important protocol aspects: the data part of ISPs, OSPs , P D U s and the t ime handling. ASN.l Data Part The Abstract Syntax Notation 1 ( A S N . l ) is an abstract notation [Neu-92] for describing data objects of different OSI protocols as well as non-OSI protocols and applications. It has been widely used in describing the structure of Service Primit ives (SPs) and P D U s in higher level protocols such as X.400 ( M H S ) , X.500 (DSJ, F T A M and S N M P . A S N . l has also proven viable for the specification of the data part of lower level OSI protocols Chapter 2. BACKGROUND 11 [Neu-92]. There, are several reasons for using A S N . l for. representing the data part of protocols for the.purpose of test suite generation : • A S N . l is a standardized abstract, syntax notation supported by ISO. • Many higher level protocols have their P D U s represented in specified in A S N . l . • A S N . l is supported in T T C N . • Many useful tools to convert A S N . l to other programming language data structures (such as C and 'C++) are\"available [Neu-90] [Sam-90]. T E S T G E N adopted a subset of the A S N . l notation defined in the 1988 version of the X.208 recommendation [ISO-8824] to specify the structure of service primitives (ISPs and OSPs) and protocol data units (PDUs) in the E T S formalism. In order to represent a communication protocol in the Protocol Data Structure al l the ISPs, OSPs and P D U s of the protocol must be specified in A S N . l . T E S T G E N specifies the parameter structure of service primitives and protocol data units wi th a subset of the basic A S N . l type notation defined in section 1 and section 2 of [ISO-8824]. In the Extended Transition System ( E T S ) , service primitives and protocol data unit parameters are referenced by enabling predicates and action functions. T E S T G E N introduces an intuitive dot notation similar to the P A S C A L or C structured type reference mechanism. Thus the SP or P D U parameters described in the A S N . l part of the protocol specification can be referenced by enabling predicates and action functions as follows: < SPname > {. < pararhetername >}+ or < PDU name > {. < parameter-name >}+ Note that this notation requires the enforcement of a strong naming convention: al l SP parameters and subparameters (usually structured sequences or set types) must be Chapter 2. BACKGROUND 12 unambiguously named. Test suite generation method T E S T G E N generates a test suite (for black-box testing) which verifies an arbitrary num-ber of specified conditions on the external behavior of a protocol implementation for a selected set of subtours (a subtour is a tour of the protocol, which starts and ends at the same state, the in i t ia l state) of the protocol graph. A separate test case is generated for each subtour. Each subtour starts and ends, at the in i t ia l state, as the in i t ia l state is the most trustworthy state and can.easily be reached (e.g. wi th \"reset\" operation), and besides such subtours are natural and meaningful for \"user sessions\" during testing. In T E S T G E N , a subtour can be printed on user's demand. In its format, the states are in the rectangles; a transition from one state to another is represented by vertical bars; the names of the input service primitives or input P D U s (and their parameters) are on the left side; the names of output service primitives or output P D U s are on the right, side. The following is an example of a subtour generated by T E S T G E N for the simplified Z39.50 protocol: + — + I CLOSED | •• + + I ISP: AEINITreq |QSP : { parameters... I > . 1 IPDU: |DPDUi:INITREQ Chapter 2. BACKGROUND 13 Modified Estelle +ASN.l Protocol Specification Parser Protocol Data Structure USER Constraints Editor TSG Constraints Test Suite Generation Engine TTCN Tool Formated TTCN output Test Coverage Tool Selected Test Cases Legend: File ( ) Data Structure Dynamic Module Figure 2.3: The process of generating test cases using T E S T G E N Chapter 2. BACKGROUND ISP: IPDU:INITRESP { parameters. } I { parameters I > I0PDU2: I + V——~+ I. INIT_SENT I + + •SPl:AEIMITconf { parameters > 0SP2: •PDU : — +—V—+ I IDLE | +— + ISP: AESEAHreq { parameters. } IPDU: |OSP : |0PDU1:SEAHREQ { parameters > Chapter 2. BACKGROUND ISP: IPDU:SEAHRESP { parameters. > J0PDU2:—-I + V + I SEAH_SENT | +- — + GSP1:AESEAHconf { parameters >• •SP2:-— OPDU : — •+—V--+ I IDLE | + + ISP: AECLOSreq { parameters. } IPDU: I OSP :• |0PDU1:CL0SREQ . { parameters } 10PDU2: Chapter 2. BACKGROUND 16 + V — + I CLOSED | + + Since communication protocols usually contain recursive behaviour (state recursion), as well as parameter variation (slight changes of data in different P D U s ) on the exchanged service primitives usually leads to a practically infinite number of parameter value com-binations, the number of subtours can be infinite. To overcome this difficulty, T E S T G E N defines a flexible, user-definable restriction mechanism so-called T S G constraints. Basi-cally, the TSG-constraints allow the user to define a min imal and a maximal value on the number of times an E T S element is reached-or used in one subtour. For example, to test the data part of an implementation the user can request that the I D L E state can be reached between 2 and 4 times, the. D A T A P D U can be used for at most 3 times: • A t the beginning, the constraints are set to default values when the P D S is created. Depending on the generated test results, the user can invoke the editor to define the values he/she would like to have and then go and generate the tests again. More information about the TSG-constraint editor can be found in [Vuo-94]. After subtours are identified by T E S T G E N they can either be reduced by a coverage tool [Vuo-91], [McA-92] or they can be used to generate test cases in the form of T T C N [Zha-95]. ' '' ' The diagram in Figure 2.3 describes the process of generating test cases using T E S T -G E N and other supplemental tools. Chapter 3 INFORMATION RETRIEVAL PROTOCOL Z39.50 Z39.50 (IR) is an A N S I / N I S O standard and is formally called ANSI Z39.50; Infor-mation Retrieval Service and Protocol. American National Standard Infor-mation Retrieval Application Service Definition and Protocol Specification for Open Systems Interconnection. The documents of I R are prepared by a NISO (National Information Standards Organization) committee. I R is an application protocol based on a client/server model. The Z39.50 IR protocol was originally proposed (in 1984) for use wi th bibliographic information and was later broadened in its domains of applications as manufacturers, vendors, consultants, information providers, universities and others express their interest and they wished to access or to provide access to various types of information, including bibliographic, text, image, financial, public util i ty, medical and scientific information, chemical, news services and much more. The version of this protocol we implemented is version 3 released in 1994. 3.1 Basics Of The Protocol Z39.50 IR is based on an underlying connection-oriented and reliable network. The protocol specifies formats and procedures governing the exchange'of messages between a client and server; enabling the client to request that the server search one or more databases and identify records which meet specified criteria, and to retrieve some or al l 17 Chapter 3. INFORMATION RETRIEVAL PROTOCOL Z39.50 18 of the identified records. We should note that the protocol only addresses communication between the client and the server. It does N O T address the interaction between the client and user, nor the interaction between server and the information databases. The protocol is logically divided into the procedures pertaining to the client and the procedures pertaining to the server. Basically, IR permits clients to search databases residing on servers and then retrieve records from these databases. In more details, we can describe IR as follows: IR connects a user of an IR client to an IR server and disconnects when the user is finished. During connection, the user w i l l request some specific information which wi l l be expressed some-how in a form of requests sent from client to server for processing against the server's databases or resources. As an example, the user may request for magazines issued in a specific t ime frame, or articles written by a particular author, about specific subjects and so on. Based on the results, the user may request retrieval of one or more records. W i t h i n the protocol, the portions of the client and server that carry out those pro-cedures are referred to as the Z39.50 origin and the Z39.50 target, respectively. They communicate with each other by exchanging protocol data units ( P D U s ) . The origin and the target are not interchangeable. The standard describing Z39.50 is positioned wi th respect to other related standards by the Open Systems Interconnection (OSI) basic reference model (ISO 7498). Z39.50 protocol is defined within the application layer of the reference model, and is concerned in particular with the search and retrieval of'information in databases. The relationship of Appl icat ion Entities ( A E ) and Service Providers (SPs) for Z39.50 can be depicted in the model in Figure 3.4. This model formalizes the communications between various Chapter 3. INFORMATION RETRIEVAL PROTOCOL Z39.50 19 ORIGIN TARGET Origin Application Entity (OAE) Request \" i . PDUs Target Application Entity (TAE) | Response Confirmation Origin Service Provider (OSP) (Application Layer) \"~\"\".i Indication Target Service Provider (TSP) (Application Layer) Lower Layers Lower Layers PHYSICAL MEDIUM Figure 3.4: The relationship of Appl icat ion Entities and Service Providers in Z39.50 parts of an OSI supportive system. In this model, each system (i.e. Origin or Target) is made up of a service provider (SP) and an application entity ( A E ) . The SP is the application layer software that builds, sends, decomposes and verifies the Z39.50 P D U s . The A E is the software residing outside of the-.OSI model that makes use of the Z39.50 services provided by the application layer software to search for and retrieve data, in the case of the origin, or to accept requests to perform searches and to provide the result, in the case of the target. Chapter 3. INFORMATION RETRIEVAL PROTOCOL Z39.50 20 The transfer of a P D U is initiated by one of the A E s issuing a request to its SP, specifying the P D U to be transmitted and also specifying any data necessary to create' that P D U . The SP reacts to the request by building the P D U using the data provided by the A E in the request and by sending the P D U using the services provided by the lower layer software. The SP within the partner system accepts, decomposes and verifies the P D U , - t h e n issues an indication to its A E specifying the received P D U and passes data contained in the P D U . The A E initiates a return P D U by issuing a response to its SP specifying the P D U to be sent and specifying any data necessary to create the P D U . The SP creates and sends the P D U . The SP in the partner system receives, decomposes and verifies the P D U , then issues a confirmation to its application entity specifying the received P D U and passes data contained in the P D U . Note that in this model, we consider the A E s as a layer above the SP which resides in the application layer of the OSI model. Even though Z39.50 is defined in terms of the OSI reference model and is considered to fit within the application'layer, many institutions implementing it chose to layer it on top of the de facto standard Transmission Control Protocol/Internet Protocol ( T C P / I P ) for several reasons: ' • A n OSI implementation could be to large and too complicated. This can outweigh the relatively meager return in functionality the organizations would like to gain. • OSI supplemental softwares are lacking. • One of the main-goal of implementations is the interoperability with each other over the Internet and implementations over T C P / I P obviously have more advantages in this respect. In fact, a couple of years ago two organizations, the F lor ida Center For Library Automat ion and the Data Research Associates, implemented the earlier Chapter 3. INFORMATION RETRIEVAL PROTOCOL Z39.50 21 version of Z39.50 using OSI stack but they could not talk to each other as they accessed two different OSI networks that were not connected [Jam-95]. 3.2 Information Retrieval (IR) Service This service describes the activity between two applications: an ini t iat ing application, the client, and a responding application, the server. The server is associated wi th one or more information databases. In the following subsection, I informally describe major services in Z39.50; these services are defined more formally, as in the standard, in the next subsections. 3.2.1 Z39.50 services and their usage Services in Z39.50 can be informally divided into the following categories: • Setting up and tearing down connection between the target and the origin (Init and Close). • Searching and retrieving data from databases (Scan, Search, Present and Segment). • Checking resources and authority during the whole session (Resource-Control, Access-Control , Trigger-Resource-Control). . . . • Maintaining the result sets during the session (Delete, Sort). • Special services allowing Origin to know about the Target implementation, databases information or allowing Target to perform tasks external to the protocol (Explain , Extended). ' Before the Z39.50 Origin and the Z39.50 Target can communicate to each other, the Init Service must be used to set up the connection. Eventually after the session is Chapter 3. INFORMATION RETRIEVAL PROTOCOL Z39.50 22 finished, the connection wi l l be closed by the Close Service. One of the most important services is the Search Service. It provides a mechanism to search one or more databases on a remote system using a wide variety of selection criteria and uniform search query structures. The results of a search then can be carried out by another service called the Present Service. The search results are maintained in a result set consisting of a set of pointers to the physical records satisfying the criteria. Therefore the present service only needs to know the starting point in the set and the number of records from that point to be returned to complete its task. Note that in this way, a random access retrieval mechanism is provided. . Z39.50 provides a service called the Scan Service for browsing a list of available items of the databases thus easing the subsequent searches. To adapt to the system resources efficiently and to assure the authorization, Z39.50 uses the Resource-Control Service, the Resource-Report Service, the Trigger Resource-Control Service and the Access-Control Service. The Sort Service, the Delete Service are uti l ized to maintain the set of results after a search is done. To allow the Origin to get further information about the Target such as databases available for searching, attribute sets arid diagnostic sets used by the Target, record syntax and so forth, Z39.50 provides the Explain Service. Another service called Extended Services Service allows Origin to request Target to perform some specific task. This service usually is used by the implementors for their own specific tasks. For example, an Ordering or Purchasing System via the net can use this kind of service. • ' • Chapter 3. INFORMATION RETRIEVAL PROTOCOL Z39.50 23 3.2.2 Model and Characteristics of the Information Retrieval Service Communicat ion between origin and target (also called association) is explici t ly estab-lished by the origin and may be explici t ly terminated by. either origin or target. Z39.50 assumes that the underlying connection is connection-oriented and reliable. The roles of origin and target may not be reversed. 3.2.3 Types of Z39.50 services The Z39.50 service is carried out by the exchange of messages between origin and target. Each message'is either a request or response. Services may fall to one of 3 following types: 1. Confirmed: in this service, a request, must be followed by a response. 2. Non-confirmed: in this service, a request does not have a response to it.. 3. Conditionally-confirmed: this service can be invoked either as a confirmed or a non-confirmed service. 3.2.4 Z39.50 Operations There are eight operations in version 3: Initialization, Search, Present, Delete, Scan, Sort, Resource-report and Extended-services. A request from the origin of a particular operation type initiates an operation of that type (e.g. Search request initiates a Search operation) which terminates wi th a corresponding response from the target. . . Chapter 3. INFORMATION RETRIEVAL PROTOCOL Z39.50 24 3.2.5 Facilities of the Z39.50 service There are eleven facilities of the service. Most of them consist of logical groups of services; in a few facility consists of a single service. Their names and characteristics are described in Figure 3.5. In more detail, the facilities are: 1. Initialization Facili ty: consists of the Init Service and it is a confirmed service in i -tiated by Origin. This service not only initiates a connection but also determines Q O S parameters as well as some functionalities to be used during the whole con-nection, (e.g. how large a packet should be, which services are available and so forth). 2. Search Facility: a confirmed service initiated by Origin v i a the Search operation. Search service permits an Origin to search for particular records in a remote server database. The search may be performed by personal, corporate and conference names, titles, dates, bibliographic numbers such as ISSN, I S B N and so on. Once the search is done, a Result List is created and maintained by the Target for later use. 3. Retrieval Facility: consists of two services: • Present Service, which is confirmed and init iated by Origin to launch a Present Operation. The Present Service allows Target to retrieve records matching the search and send back to Origin, which in turn-presents these results to users. • Segment Service, which is non-confirmed and initiated by Target during a Present operation. This is used when Origin requests for very large records which cannot be conveyed in one packet ( P D U ) . Chapter 3. INFORMATION RETRIEVAL PROTOCOL Z39.50 25 —^Character is t ics SERVICE N A M E ^ ^ ^ ^ Confirmed Non Confirmed Condition-Confirmed Originator Init X Origin Search X Origin Present X Origin Segment ; V X Target Scan X Origin Delete X Origin Sort x • Origin Access-Control X Target Trigger-Resource X Origin Resource-Control x Target Resource-Report ' x • Origin Extended X Origin Close X Target -Origin Figure 3.5: The Z39.50 services and their characteristics CImptcrS: INFORMATION RETRIEVAL PROTOCOL Z39.50 26 4. Result-set-delete Facility: consists of the Delete Service, confirmed and init iated by Origin invoking Delete Operation. This is invoked when the Origin asks to delete one or more records from the given Result Set. 5. Browse Facility: consists of Scan Service, a confirmed service originated by Origin ' launching a Scan Operation. This allows the user to look at some ordered list of terms before he/she wants to perform search and retrieval on some specific terms. As an example, the list may be composed of subjects, authors, names arid.so on. 6. Sort Facility: consists of the Sort Service, confirmed and init iated by Origin invok-ing a Sort Operation. This permits Origin to ask Target to sort the result list in particular sequences, such as author/t i t le or subject/date. .7. Access Controf Facility: consists of the Access Control Service, a confirmed service and initiated by Target and not invoking any operation. This, service usually is a part of another operation. This provides a r method of controlling access to databases on remote server and allows. Target to serve many users wi th different levels of authorization. . 8. Accounting/Resource Cont ro lFac i l i ty : consists of three services: • Resource-control Service: a conditionally Tconfirmed service init iated byTarget not invoking any operation and which is usually part of another operation. • Trigger-resource-control Service: a non-confirmed service init iated by Origin invoking no operation, and which is part of another operation., • Resource-report Service: a confirmed service initiated by Origin invoking the Resource-report operation. Chapter 3. INFORMATION RETRIEVAL PROTOCOL Z39.50 27-.9. Exp la in Facility: does not include any services but uses the services of the Search and Retrieval facilities. This allows the user to obtain details of the nature and extent of the databases available on a remote server. It includes not only the number or the names of the databases but also the information about how to search against them. '. 10. Extended Services Facility: consists of the Extended-services service, confirmed and originated by Origin invoking the Extended-services operation. .. 11. Termination Facility: consists of the Close Service, confirmed and which may be initated by either Origin or Target. It does not invoke any operation, nor it is part of any operation. It merely allows Origin or Target to immediately terminate al l operations and subsequently finish the current connection. 3.2.6 A typical scenario of Z39.50 Although the protocol is very complicated due to various external services, I just want to present a scenario which is quite typical and common of Z39.50 usage: The origin explici t ly establishes the connection by sending an Init-Request to the target. After getting Init-Response wi th positive result (i.e. accept), the connection is established and P D U s wi l l be exchanged between the origin and the target. Usually the origin w i l l begin sending a Search-Request specifying the query in a predefined syntax (e.g. Reverse Polish Notation, IS08777 or Z39.58 type query and so on). Alternatively, prior to sending Search-request, origin may send a Scan-Request to request Target to send back a list of general terms. Based on that list, origin may form a more reasonable query. • On receipt of Search-response containing the result set of pointers to the records Chapter 3. INFORMATION RETRIEVAL PROTOCOL Z39.50 28 satisfying the query, the origin wi l l request the target to display some or al l records in more details or in the full-text format by sending a Present-request specifying the starting point in the list and the number of records from that point it wants to retrieve. Eventually the origin should disconnect the connection by sending a Close (understood as a request, though in Z39.50 term, it is just called Close) to the target. It may but does not have to wait for a Close (-response, as an acknowledgment) from target before closing down completely. Figure 3.6 describes the above scenario. 3.3 The implementation of Z39.50 at EBSCO Publishing company In the next chapter, I wi l l use a formal method and other tools to generate conformance test suites for Z39.50 which can be tried against some implementation. So I would like to first introduce briefly the implementation I had chance to participate in . 3.3.1 Objective From September 1994 to August 1995, I was involved in the implementation of Z39.50 for E B S C O Publishing company. This implementation is for l ibrary use. The goal is to implement a client/server based software (based on.Z39.50) allowing users in different libraries in Nor th Amer ica to access, and retrieve, bibliographic information stored in main databases located on a certain server. O n one hand the implementation must follow closely the Z39.50 specification (so that it can inter-operate wi th other vendors' implementation), on the other hand it also must accommodate the specific needs of the E B S C O company. The implementation (until August 1995) includes almost al l facilities except Exp la in , Chapter 3. INFORMATION RETRIEVAL PROTOCOL Z39.50 29 O R I G I N T 1 M E Wit InitjRequest •Response Scan-Request c^an-Response Search-Request Seirch-Response Present-Reque|st Pres|ent-Response Close Close T A R G E T Any number of these PDUs can be sent Figure 3.6: A typical scenario of Z39.50 Chapter 3. INFORMATION RETRIEVAL PROTOCOL Z39.50 30 Delete and Sort. -3.3.2 Programming language and tools used in the implementation We use C (on the target) and C + + (on the origin) to implement Z39.50. We>also use the A S N . l to C compiler \"snacc\" developed by the University Of Br i t i sh Columbia [Sam-93] and slightly modified (memory allocation and ported to D O S and MS-Windows platforms) to encode and. decode the data part in P D U s . - , The implementation of the target system alone consists of about 75000 lines of C-code, not including code generated by the \"snacc\" compiler and code related to sending and receiving data to and from the origin. The target runs on H P U n i x system and accommodates the origin running on different platforms such as MS-Windows , U n i x and M S - D O S . Chapter 4 APPLYING TESTGEN TO Z39.50 PROTOCOL 4.1 Motivation for applying TESTGEN The development of Z39.50 protocol I was involved in could be divided into the following •stages: - • System design and software design, which is based mainly on the protocol specifi-cation in the standard and the needs of our customers. In this stage we determined the hardware platforms as well as the the services to be included in the in i t ia l version. • Implementation and unit testing, in which a set of programs and program units (such as search engine, retrieval engine, stuffing A S N . l in P D U s , sending and receiv-ing P D U s between Origin and Target, user's interface and so on) are implemented according to the design and tested. • Integration and system testing, in which al l individual programs and units are merged together into a complete system and this system is tested to insure that all software requirements are.met. • Operation and maintenance, in which the delivered system is installed and improved wi th performance and new features. From my own experience, testing phase (both unit testing and integration testing) takes a lot of t ime and efforts, specifically when no test suite is given in the standard 31 Chapter 4. APPLYING TESTGEN TO Z39.50 PROTOCOL 32 and all test, cases are.developed almost heuristically and manually. . , Coming back to U B C , I think that, we can apply some of the tools developed by our group [Vuo-94] to generate test suite automatically or semi-automatically to speed up this phase. As I was assigned to implement the portion of coding, decoding data in A S N . l format and sending and receiving P D U s , I chose to use T E S T G E N to generate test cases during the \"Implementation and unit testing\" phase for several reasons: • These test cases can be mainly used for the prototype implementation to make sure that the control part is functioning correctly in term of exchanging P D U s . • The .prototype can use the typical scenario described in the previous chapter, thus simplifying things but not losing the essence of the protocol. • The data part is not:very crit ical in this phase to the extent that some fields can ••' be considered fixed. •*- ' . ' • The prototype program can be writ ten as a single unit (e.g. Origin including • simulated Target inside) and therefore can be suitable for T E S T G E N as it currently supports a. single Estelle.module. 4.2 The simplified Z39.50 used in TESTGEN I use the typical scenario of Z39.50 described in Chapter 3 for use wi th T E S T G E N . The reasons'for this are: ... • The prototype program includes the services in that scenario. • The emphasis is placed-on the control part andno t the data part. Chapter 4. APPLYING TESTGEN TO Z39.50 PROTOCOL 33 • It is possible to ask the company to allow me to use that prototype to test against the test suite in future. ' . The services included in this simplified version are: • Initialization • Search • Present • Close The communication takes place in three different phases: the connection setup phase, the search and retrieval phase and the disconnection phase. After connection phase is established, the search and retrieval phase wi l l be carried out: the Origin w i l l send a search request specifying a query and a database name; only i f the search is successful, a present request can be sent subsequently to retrieve the list of records. This process can be repeated unt i l the Origin wishes to disconnect by sending the close request. In each phase and each operation, only certain P D U s and service primitives are mean-ingful. Unexpected P D U s and service primitives w i l l cause the system to disconnect for security reasons. To represent this special case, a new P D U called I N V A L I D is introduced in this simplified version. , l f 4.2.1 Estelle.Y and ASN.l specification Estelle.Y specification As T E S T G E N can only be applied to a single Estelle module, I modeled the Origin system for i t . The finite state machine representing its behavior is depicted in Figure 4.7. ' ' ,. •• • • ; The FSM-has 5 states which are defined as follows: Chapter 4. APPLYING TESTGEN TO Z39.50 PROTOCOL 34 1. C L O S E D (marked as Z01): in i t ia l state, origin is awaiting the Init request from ; • the user. 2. I N I T - S E N T (Z.02): Init-request P D U was sent, awaiting Init response P D U from target. 3. I D L E (Z03): Connection is established, awaiting Search request or Present request from the user. , \" 4: S E A H - S E N T (Z04): Search request P D U was sent, awaiting Search response P D U from target. 5. P R E S - S E N T (Z05): Present request P D U was sent, awaiting Present response P D U from target. -From a particular state, when getting the .corresponding request from user or response P D U from target, origin is preparing the corresponding P D U or confirmation to send to target or to user and then entering new state (defined in the E S M ) . , , . • T h e E s t e l l e . Y specification can be found in appendix A . ASN.l s p e c i f i c a t i o n The corresponding protocol data units (PDUs) exchanged between the Origin and Target (protocol layers) and their, basic parameters are as follow: PDU name M e a n i n g P a r a m e t e r s R e s p e c t i v e S P ' s INITREQ . C o n n e c t i o n S e t u p P r o t o c o l V e r s i o n A E - I N I T r e q . . O p t i o n s A E - I N I T i n d • Message S i z e ; . \" . Max R e c o r d S i z e . , . Chapter 4. APPLYING TESTGEN TO Z39.50 PROTOCOL 35 ^ \\ STATE I N P U T ^ \\ CLOSED (Z01) INIT-SENT (Z02) IDLE . (Z03) SEAH-SENT (Z04) PRES-SENT (Z05) AE-INITreq Send INITreq PDU (—»- Z02) INITresp PDU (accept) Issue positive Init Confirmation ( — * Z03) INITresp PDU (reject) Issue negative Init Confirmation ,( - * Z01) AE-SEAHreq / Send SEAHreq PDU ( Z04) SEAHresp PDU Issue Search Confirmation ( — * Z03) AE-PRESreq Send PRESreq PDU ( — * Z05) PRESresp PDU Issue Present Confirmation ( —*• Z03) AE-CLOSreq Send CLOSreq PDU ( - * Z01) , INVALID Send CLOSreq PDU ( Z01) Send CLOSreq PDU (''-*• Z01) Send CLOSreq PDU ( Z01) Send. CLOSreq PDU ( Z01) Figure 4.7: The FSM for simplified Z39.50 protocol, used in TESTGEN Chapter 4. APPLYING TESTGEN TO Z39.50 PROTOCOL INITRESP Connection Confirm SEAHREQ SEAHRESP PRESREQ PRESRESP INVALID CLOSREQ Search S e r v i c e (request) Search S e r v i c e (response) Present S e r v i c e (request) Present S e r v i c e (response) . Unexpected PDU or s e r v i c e p r i m i t i v e Termination P r o t o c o l Version Options Message S i z e Max Record Si z e Result Database Name Query Result Set Name Result Count Number Of Recs returned. S t a r t i n g Point Number Of Recs requested Result Set Name Number Of Recs returned Present Status Close Reason AE-INITresp AE-INITconf AE-SEAHreq AE-SEAHind AE-SEAHresp AE-SEAHconf AE-PRESreq AE-PRESind AE-PRESresp AE-PRESconf AE-CLOSreq AE-CLOSind The A S N . l representation for main P D U s are as follows: Chapter 4. APPLYING TESTGEN TO Z39.50 PROTOCOL PduMessages ::= CHOICE { INITREQ, . INITRESP, SEAHREQ, SEAHRESP, PRESREQ, PRESRESP, CLOSREQ, -INVALID } INITREQ ::= SEQUENCE { protocolVersion DataString, options DataString, prefMessageSize INTEGER, maxRecordSize INTEGER .. } INITRESP ::= SEQUENCE { protocolVersion DataString, options DataString, prefMessageSize INTEGER, maxRecordSize INTEGER, Chapter 4. APPLYING TESTGEN TO Z39.50 PROTOCOL 38 result INTEGER SEAHREQ ::= SEQUENCE { databaseName DataString, query DataString, resultSetName DataString } SEAHRESP ::= SEQUENCE { resultCount INTEGER, numOfRecsReturned INTEGER, searchStatus INTEGER } : PRESREQ ::= SEQUENCE { resultStartPoint INTEGER, numOfRecsReqested INTEGER } • ' PRESRESP ::= SEQUENCE { numOfRecsReturned INTEGER, Chapter 4. APPLYING TESTGEN TO Z39.50 PROTOCOL 39 presentStatus INTEGER } CLOSREQ ::= SEQUENCE { closeReason INTEGER > INVALID ::= SEQUENCE { dummy INTEGER } Appendix B contains the complete A S N . l specification for our simplified Z39.50 pro-tocol model. 4.3 Results 4.3.1 Initial result B y default, T E S T G E N imposes several constraints on the P D S it parses at the beginning from Estel le .Y and A S N . l specifications. For example, al l states wi l l be traversed at most once; requests and/or P D U s can be sent at most once; the integer components are assigned the values of 1 and 99; string components have one value, etc [Vuo-94]. W i t h the default constraints, I got nearly 200 test cases. They are not good as they do not reflex the reality, for example no \"Present\" is sent. The reason is that \"Present\" is supposed to be sent only after a successful \"Search\" operation, and if so the \" I D L E \" Chapter 4. . APPLYING TESTGEN TO Z39.50 PROTOCOL 40 state must be traversed twice, which contradicts the default constraints. So at first, I allowed states \" I D L E \" , \" S E A H - S E N T \" and \" P R E S - S E N T \" to appear 4 times (the number of retrieval operations which may occur in a subtour); and the number of cases is more than 15000. 4.3.2 Constraint modification Obviously, we must impose some reasonable constraints on the P D S . The following con-straints were modified in the P D S after it was parsed by the T E S T G E N engine; • As a protocol can send search or present requests many times, the state I D L E should be allowed to appear in a subtour more than once. I chose 4 for the start so that we can allow up to 4 retrieval (search or present) operations in al l . Besides, as after a unsuccessful search, another search should be sent as present operation can be launched only after a successful search, so I D L E shoudl be traversed 4 times in this case. The states \" S E A H - S E N T \" \" P R E S - S E N T \" . are also allowed to be traversed maximal ly 4. • The value of \"ProtocolVersion\" and \"Options\" in the Init request can be set fixed as they are fixed in the prototyping phase. • The value of \"Result\" in Init response can be assigned to one of 2 possible values (0 for success and 1 for failure). Similarly, \"searchStatus\" is also assigned to one of.2 values, \"success\" or \"failure\". . • The values of \"preferMessageSize\" and \"maxRecordSize\" in Init-Request and Init response are also assigned to 2 reasonable values (1024 and 2048). Chapter 4. APPLYING TESTGEN TO Z39.50 PROTOCOL 41 • The number of times some ISPs (e.g. A E S E A H r e q , A E P R E S r e q ) , O S P ( A E S E A H -conf, A E P R E S c o n f ) , P D U s ( S E A H R E Q , P R E S R E Q , P R E S R E S P ) are also modi-fied to be used maximal ly 4 times (instead of once). • The values of \"resultStartPoint\" and \"numOfRecsReqested\" in \"Present request\" are set fixed. Appendix C contains the modifications made above. W i t h these constraints, the number of test cases dropped to about 300 test cases. Some of them are listed in appendix D . These test cases should be screened again as some of them are not executable (do not make sense). For example, according to the protocol, the \"preferMessageSize\" must be less than or equal to the \"maxRecordSize\" in the Init-Request and/or the Init-Response. However, T E S T G E N does not care about that and so, subtours violating this condition must be eliminated from the test suite. In this special case, the number of test cases wi l l be reduced to 210. 4.3.3 Test coverage Even wi th imposed constraints on the min imum and max imum number of times a par-ticular state, transition, ISP, OSP, P D U can be used to form subtours, the number of test cases generated by T E S T G E N is st i l l large. The reason is as follows: the control part of a test case consists of the action sequence affected by the environment, e.g. by requests from user or various messages from adjacent layers. Consecutive actions may be identical and may originate from a single source (data packets arriving from the network) or from multiple sources (connection request from several users). The control sequence is concerned only wi th the actions and their order Chapter 4. APPLYING TESTGEN TO Z39.50 PROTOCOL 42 and not wi th the source of the actions. Data variation for each control sequence also increases the number of test cases. The idea of test coverage is to define a reasonable (user-defined) metrics distance between two control sequences (test cases) and all test cases which are wi thin some distance are considered as sufficiently similar that only one test case is needed to be tested and thus it is selected and put in the set of selected test cases. The details of test coverage can be found in [Vuo-91], [McA-92]. Adopt ing [Vuo-91], we use the distance of the Z39.50 test cases generated by T E S T -G E N as follows: 1. For each subtour, we use the \"concise notation\" by grouping consecutive identical input P D U s ( IPDU) or ISPs into a single tuple: the I P D U / S P / and its mult ipl ic i ty (recursion depth) a giving the tuple (I, a). For example, the subtour A E I N I T r e q -I N I T R E S P - A E S E A H r e q - S E A H R E S P - A E P R E S r e q - P R E S R E S P - A E C L O S -req wi l l be represented by the concise form as (AEINITreq,1) ( INITRESP ,1 ) ( A E -S E A H r e q , ! ) ( S E A H R E S P , 1 ) ( A E P R E S r e q , l ) ( P R E S R E S P , 1 ) ( A E C L O S r e q , l ) . 2. In this context, we are referring to a subtour by its concise form. We use the testing distance between two subtours A= (ai,ai)... (an,an) and B = ( & i , / 3 i ) . . .(bn,/3n) (if A and B are of different lengths then the shorter subtour is padded wi th a nul l I P D U to match the length of the longer subtour) as • dt{A,B) = Y,p(i)xr{8l{A,B))-i=l where the functions p and r are user configurable and must satisfy the following properties • 1 S a sequence of positive numbers such that J2i^iP(^) converges Chapter 4. APPLYING TESTGEN TO Z39.50 PROTOCOL 43 • { r ( i ) } ^ 0 is a nondecreasing sequence in [0,1] such that r(0) = 0 and l im^oo r(i) Furthermore, the sequence { ^ } ^ ! is non-increasing. 0 i f a,- = bi and a; = /?; 8i(A, B) = \\ \\ a i fa\\ i f a,i =' bi and cti ^ .fa oo i f ai^bi The metric space defined by dt on the set of al l subtours starting at the in i t ia l pro-tocol state is both complete and convergent (i.e. every Cauchy sequence converges) [Vuo-91]. . 3. We use a coverage measure for a set of test cases C relative to a test suite (set of subtours) TS from the metric distance dt as follows: Let d(x,S) = 'mf{dt(x,y)\\y R E C V D : an operation other than Present is processed: . Here are the definitions of the events in the tables: 1. I n i t - P D U : Init request P D U is coming from the origin. 2. Init-Resp+: the service-user issues Init Response (accept) 3. Init-Resp-: the service-user issues Init Response (reject) 4. A c c - R E Q : the service-user issues Access Control request 5. AccResp P D U : Access Control response is coming from the origin. 6. R s c - R E Q : the service-user issues Resource Control request 7. RscResp P D U : Resource Control response is coming from the origin. 8. O p - P D U : A n y operation request (search, present, ...) is coming from origin Chapter 5. FSM-BASED APPROACH TO PROTOCOL CODING 49 E V E N T ^ \\ C L O S E D (0) I N I T - R E C V D (1) A C G - S E N T (2) R S C - S E N T (3) I D L E (4) A C T I V E (5) Close-Sent (6) CIose-Recvd (7) Init-PDU Init-Ind; ' 0) Init-RESP+ InitRespPDU+; (4) • Init-RESP- InitRespPDU-; '- (0) A c c t R E Q A c c - P D U ; (2) AccRespPDU Acc-Conf; (i) R s c - R E Q RscPDU; (3) RcsRespPDU Rsc-Conf . (1) O p - P D U • Initiate O P (5) Close-REQ Close-PDU (6) Close-PDU K i l l O P (6) Close-PDU Close-Ind (7) Close-Ind Ki l l O P (7) CloseResp Close-PDU (0) Close-PDU Close-Conf (0) ' Figure 5.8: The state table for Z39.50 Target main processing 9. C lose -REQ: the service-user issues Close request 10. C lose -PDU: Close P D U is coming from origin. 11. CloseResp: the service-user issues Close in response to Close P D U from origin. Tables can be represented in many ways, but we choose the matr ix forms, as our programs can make use of it in finding the cells quickly. . . We wi l l use,the Target for illustrations, as the Origin wi l l be similar. Figures 5.8, 5.9, 5.10 contain, the tables describing the main processing phase and the search and retrieval phase.for a Z39.50 Target [IR-Z3950-95]. Chapter 5 : FSM BASED APPROACH TO PROTOCOL CODING 50 S T A T E . E V E N T '' R E C V D Rsc Sent A c c Sent R s c - R E Q ; Rsc P D U (2) . Rsc Resp P D U . Rsc C o n f (1) •- . A c c - R E Q A c c P D U . (3) . / A c c Resp P D U . A c c C o n f (I) : ' Trigrc P D U Trigrc Ind (1) * - Resp ; , Resp P D U ; E n d O P I n d ; Ex i t Figure 5,.9: The state, table for Z39.50 Target search processing 5.3 How to create a finite state machine •''>'< ': •• B y the definition of a F S M , at any given time, the protocol can be in only one defined state. From that state, if a ; corresponding event occurs, then some specific task should be performed and the protocol w i l l l ikely (but not always) move to one of the next states. As an example, after getting \"Init-Request\" from Origin, the Target w i l l record the-fact and enters state \"receive ah Init-Request\". Then, ' i t w i l l process the Request and eventually sends \"an Init-Response\" to the Client and moves to state \" I D L E \" waiting for another request. Processing requests such as Search and Present means that program should take care of behavior of another subtable. The move from a state to one of its next states is called a transition. Nearly al l functions processing the tasks wi l l be empty at the beginning and w i l l be filled out gradually later as needed. :; Chapter 5. FSM-BASED APPROACH TO PROTOCOL CODING 51 S T A T E E V E N T Present R E C V D Rsc Sent Acc Sent Rsc-REQ Rsc P D U (2) Rsc Resp P D U Rsc Conf (1) Acc-REQ Acc P D U (3) Acc Resp P D U Acc Conf (1) Trigrc P D U Trigrc Ind (1) Segment R E Q Segment P D U (1) Present Resp Present Resp P D U ; EndOP Ind; Exit Figure 5.10: The state table for Z39.50 Target retrieval (present) processing O n the Target system, we define one main state table to deal wi th the functionality of the whole server and several subtables to deal with the corresponding operations such as Search, Present and so on. This way the main program does not have to be rewritten but only new subtable and the functions dealing with this subtable must be created whenever another operation is added to the implementation. In each state table (in fact an array of structures), each element contains the following items: 1. State determining the current state. 2. Event determining the coming event. 3. Subtable (if not N U L L ) determining the address of the subtable the protocol should Chapter 5. FSM-BASED APPROACH TO PROTOCOL CODING 52 go in and execute the particular operation. 4. To_do_Function determining the actions to be taken in this case (or after returning from the Subtable). 5. Parameters! determining the parameters for the above function. 6. Next State determining the next state the protocol wi l l be in after executing the above function. 7. Event_Generate_Function (if not N U L L ) determining the function generating the next appropriate event other than the P D U s coming from Client side. 8. Parameters2 determining the parameters for the Event_Generate_Function. To speed up the search of the appropriate element, we use a.2-dimension matr ix called Transition_Matrix which for each State and Event wi l l yield the position of the element in the state table. Therefore beside the above items, a state table also has another i tem called TransitionJNumber. enumerating the current element, and we just need to increase the address of the table wi th value from Transit ion_Matrix to get to the right element. The main state table, subtables for Search, Present can be found in appendix G . The function Process_StateMachine is much smaller and can be used to process any similar table in other programs or even in different places in the program (e.g. processing subtables). It is found in appendix H . 5.4 S u m m a r y Apply ing the F S M approach in actual coding proves to be a very good point. The main advantages are: Chapter 5. FSM-BASED APPROACH TO PROTOCOL CODING 53 • The huge project can be divided into small individual tasks which then can be implemented, tested independently by different members. Some of the tasks can even be left undone and added later without affecting the whole system. • The protocol is easier to understand. B y studying the F S M and the related state tables, one can see which functions or elements should be implemented. • The logic of the program at earlier stage and specially in prototyping phase can be tested by manually running each case through the table even before the real coding. In fact even customers wi th non-programming background can look at the table and give feedback to software team members. • The program codes, namely the control part, are extremely clearer and thus much easier to modify. Since F S M approach is introduced and used in our coding, for myself the controlling part of the protocol becomes quite easy to maintain (I was responsible for that part). Looking at some older versions (version 2) without F S M plugged in I had to spend so much time understanding the too many I F - E L S E and/or S W I T C H - C A S E statements that at the end I did not know where and how to find the main operational functions. W i t h F S M , it took me only half a day to plug a new service and everything works very smoothly. Chapter 6 SOME EXPERIENCE AND REMARKS This thesis presents the application of a formal conformance testing method and the T E S T G E N tool to generate a test suite for the Search and Retrieval Information Protocol Z39.50. Here are some of my experience and remarks about the tool. 6.0.1 Advantages of TESTGEN T E S T G E N proves to be useful in generating test cases as a skeleton or in i t ia l test suite. 1. First of al l , using T E S T G E N requires the implementor to specify the English writ-ten specification in a formal specification language (Estel le.Y in this case). Thus many ambiguities can be found prior to the development phase. 2. As the test cases can be generated automatically, they can be created quickly i f there are changes in the English specifications. We would have to modify Este l le .Y or A S N . l specs, but these changes are closer to the English spec and thus can be more straight forward. Moreover, A S N . l is usually presented together wi th the modifications. 3. Passing test cases from T E S T G E N increases the possibility of being inter-operable wi th other implementations. In fact, if T E S T G E N can be improved in several points (see chapter 7), it can be used to generate a set of standard conformance 54 Chapter 6. SOME EXPERIENCE AND REMARKS 55 test cases in T T C N . Such a set for Z39.50 protocol is not available for the time being. For now, to ensure interoperability in the Z39.50 world, there have been three main kinds of efforts: • Testbeds: From time to time, some of the Z I G members have been developing implementations that other organizations can check their software against. But as implementing takes time you can rarely get the right testbeds for your current implementation. • Bilateral interoperability: The large vendors routinely make deals to test each other's software. For example, this is how my previous employer wants to make sure that their system can talk to another company's system. A few vendors are more generous and let anyone, not just privileged partners, run tests against their servers. But testing against one system does not mean that your system is interoperable wi th another (even if tested against the same system). • Conformance definitions outside the standard: Because it is so cumbersome to amend standards once they are in place, it was ini t ia l ly suggested to write the conformance levels outside of the standard itself. However, it is not prac-t ical as new services may be added to the standard and even some services considered non conformant in the past may 1 become conformant in the future (e.g. E X P L A I N service). W i t h T E S T G E N , the implementor can be relieved from tedious generating new test cases as new services are added as mentioned above. Chapter 6,: SOME EXPERIENCE AND REMARKS 56 •1. Test cases generated by T E S T G E N can also, be specified in T T C N form. For example, using another tool [Zha-95], we /may. have the test cases in machine-. readable T T C N form. Some of them are in appendix F for reference. As mentioned before, T E S T G E N can help in generating a skeleton of. test cases where the emphasis.is : placed on the control part and which include simple data part. The more complex types of data m a y b e added, manually later. \" ' For. the specific'scenario of Z39.50 in this thesis, I used T E S T G E N cases in appendix-D and the selected test'cases in appendix E (concerned purely wi th the control part) to generate the test cases which can be applied against the actual implementation. The number of these test cases is about 50 and some of them are found\" in appendix I. 6.1 Disadvantages of TESTGEN T E S T G E N has also its disadvantages and needs some more improvements so that i t can be applied fully to a protocol. - ' 1. T E S T G E N supports only one single Estelle module and it is not practical for the cases-when multiple entities are required.to be present. For example, my test cases are generated just for single Origin wi th a simulated Target built inside, and therefore these test cases are used only for that Origin's behavior and they contain little'iriformation/about the corresponding real Target. It is one of the reasons why such test cases can be used only in my prototyping. . 2 . The data part of test cases'is hot dealt wi th ,coherently. As T E S T G E N does not execute some Estelle.assign statement, data values are not passed from one layer to another layer,\" I must comment out some of the values so that the test cases make • sense. . ,• '• ' ' . ' \" - I . . ' ' Chapter 6. SOME EXPERIENCE AND REMARKS 57 '3. The \"provided\" statement is not executed in some cases, thus making the decision not applicable. To overcome that I had, for example, to break one possible P D U into another two P D U s wi th each having different flag. For instance, the I N I T response P D U was broken down into two P D U s INIT accept-response and I N I T reject-response. This bug is quite annoying and should be fixed in the next release. 4. Similar ly as there is no way to control data values coming from other modules (single module problem), I also was forced to remove the conditional statements, (e.g. checking the sequence numbers of a Search request and Search Response). These test cases then are useful to the cases when the control part is concerned rather than the data part. 5. T E S T G E N supports a too small set of data types of A S N . l and thus it is very difficult to embed even the most basic data components in P D U s . In fact I had to modify the data in P D U s which then do not reflect reality. 6. T E S T G E N does not have the capability of retaining the recent constraints made to a P D S before the source files are reloaded (possibly wi th changes). Therefore \" it is very painful to go and impose the constraints every time a small change is made in the Estel le .Y or A S N . l file. I suggested that recent changes should be kept somewhere in memory or external storage (file on hard-disk) so that they can be imported again i f necessary according to the user. • Chapter 7 CONCLUSIONS AND F U T U R E WORK 7.1 Summary of important results The thesis tried to apply T E S T G E N to generate conformance test suite for a real-life protocol (Search and retrieval Z39.50 protocol). Analyzing the results and the T E S T G E N tool, the thesis also discussed its advantages and its l imitations. Due to the time constraints and the delay in formal permission, the test cases cannot be tried against a real prototype implementation. Besides, there is no standard set of conformance tests for Z39.50 available, so it is difficult to judge the quality of our test cases. However, the cases cover almost al l situations from the control point of view and I am positive that they can become a backbone for a more complete test suite enhanced wi th more complex data parts. A small but useful practical technique using F S M approach in actual coding is also presented and it can be used in other applications. 7.2 Future work The following tasks could be done in the future: • A p p l y the test cases against an implementation. It is the best way to measure the effectiveness of T E S T G E N and to tell how far the test cases are from the traditional 58 Chapter 7. CONCLUSIONS AND FUTURE WORK 59 test cases generated in adhoc manner. • Specify the whole protocol in a formal description language, such as Estelle.[Bud-87]. W i t h this specification, a semiautomatic implementation in C can be generated [Vuo-88]. This is very -useful as we can have at least one implementation to test against the test cases. • Improve the T E S T G E N tool in the following areas: ' 1. Mult i -module t r e a t m e n t / A s mentioned in previous chapters, this test suite can be applied to a prototyping implementation (e.g. Origin wi th simulated Target inside). In reality, the real test wi l l include both systems (Origin and Target) at the same time and T E S T G E N currently does not support this scenario. 2. A d d more A S N . l data types. Even though T E S T G E N allows data variation v ia its Constraint Edi tor , the data types currently supported are too primit ive and thus more complex data structures cannot be represented. For Z39.50, data part is very essential as it deals wi th information search and retrieval. 3. Al lowing constraints to be retained for later use and/or after slightly modifi-cation in Estel le .Y or A S N . l specification. Bibliography [Bud-87] S. Budkowski , P. Dembinski , An introdution to Estelle: a specification \" language for distributed systems, Computer Networks and I S D N Systems, 14 (1), pp. 3-23, Nor th Holland, Amsterdam, 1987. [Cha-89] . W . Y . L . Chan, S. T . Vuong, and M . R . Ito, An Improved Protocol Test Generation Procedure Based on UIOs Proceedings of the A C M SIG-C O M M ' 8 9 Symposium on Communicat ion Architectures and Protocols, September 1989. [Cho-78] T.S. Chow, Testing Software Design Modeled by Finite State Machines, I E E E Transactions on Computer, V o l . 4, No. 3, pp. 178-187, March 1978. [Gon-70] G . Gonenc, A Method for the Design of Fault Detection Experiments, ' . I E E E Transactions on Computers, V o l . 19, No. 6, June 1970. [Hsi-71] •' E . P. Hsieh, Checking Experiment for Sequential Machine, I E E E Trans-actions on Computers, V o l . C-20, No.10, October 1971. [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. ' [ISO-8824] Information Processing System - Open System Interconnection - Specifi-cation 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. [IR-Z3950-95] Information Retrieval: Application Service Definition and Protocol Spec-ification, Prel iminary F ina l Text, A p r i l 1995. [ISO-9646] Information Technology - , OSI Conformance Testing Methodology and Framework, Draft International Standard, I S O / I E C DIS 9646 (5 Parts). [ ISO-TTCN] Information Technology. - OSI Conformance Testing Methodology and Framework, Part 3:The Tree and Tabular Combined Notation, I S O / I E C DIS 9646-3, 1990. [Jam-95] James J . M i c h a e l and Mark Hinnebusch From A to Z39.50. A Networking Primer, Mecklermedia, Westport, London 1995. 60 Bibliography 61 [Kel-76] R . M . Kel ler , Formal Verification of Parallel programs, Communicat ion of the A C M 19, p P371-384, 1976. [LiG-92] \" ' Lisa Stapleton, wi th Gary Sarasin, Pacific Bell Gets Competitive, A n M T & T Publishing Supplement, November 1992. [Lu-91] Y i n g L u , On TESTGEN, An Environment for Protocol Test Sequence Generation, And Its Application to the FDDI MAC Protocol, M . S c . The-sis, A u g . 1991, University of Br i t i sh Columbia , Canada. [McA-92] M . M c A l l i s t e r , S.T.Vuong and J.Curgus, Automated Test Case Selection Based on Test Coverage Metrics, Proceeding of International Workshop on Protocol Test Systems, Montreal , Canada, September 1992.. [Nai-81] S. Naito and M . Tsunoyama, Fault Detection for Sequential Machines by Transition Tours, Proceedings of the 11th I E E E Fault-Tolerant Com-puting Symposium, pp. 138-243, June 1981. [Neu-90] G . W . Neufeld and Y . Yang, The Design and Implementation of an ASN.l Compiler, I E E E Transactions ori Software Engineering, Vol.16, No. 10, Oct. 1990. . [Neu-92] G . Neufeld and S.Vuong, An Overview of ASN.l, Journal of Computer Networks and ISDN.Systems, V o l . 23, No. 5, pp. 393-418, Feb. 1992. [Sam-90] M . Sample and G . Neufeld, Support for ASN.l within a Protocol Testing Environment, The T h i r d International Conference on Formal Description Techniques ( F O R T E ' 9 0 ) , Madr id Spain, November 1990. [Sam-93] Michael Sample, Snacc 1.1: A High Perfomance ASN.l to C/C++ Com-piler, University Of Br i t i sh Columbia , 1993. [Sab-88] K . K . Sabnani and A . T . Dahbura, A Protocol Test Generation Procedure, Computer Networks and ISDN-Systems, V o l . 15,. No. 4, pp. 285-297, September 1988. . ' • [Sar-87] B . Sarikaya, G . v. Bochman, and E . Cerny, A Test Design Methodology for Protocol Testing, I E E E Transactions on Software Engineering. V o l . 13, No. 5, pp. 518-531, M a y 1987. [Sid-89] D .P . Sidhu and T . - K . Leung, Formal Methods for Protocol Testing: A Detailed Study, I E E E Transactions on Software Engineering, V o l . 15, No. 4, pp. 413-426, A p r i l 1989. [Ste-90] Douglas Steedman, Abstract Syntax Notation. One: The Tutorial & Ref-erence, Technology Appraisals. . Bibliography 62 [Ura-87] H . U r a l , A Test Derivation Method, for Protocol Conformance Testing,. University of Ottawa. Technical Report - TR-87 01, Jan. 87. [l'ra-88] ; H . U r a l , B . Y a n g , R. L . Probert, A Test Sequence Selection Method for Protocols Specified in Estelle, Technical Report TR-88-18, Department of Computer Science, University of Ottawa, June 1988. [Vuo-88] - S.T. Vuong, A . C . Lau and R. I . Chan, Semiautomatic Implementation of Protocols Using an Eslelle-C Compiler, I E E E Transactions on Software 1 Engineering, Vol 11. No.3, Marcli 1988. ' , [Vuo-89] S. T . Vuong, W. Y . L . C h a n , a n d . M . R . Ito, The UIOv-Method for Pro-tocol last Sequence Generation, Proceedings of the Second International Workshop on : Protocol Test Systems, October 1989. [Vuo-91] ' S.T.Vuong and J.Curgus, Test Coverage Metrics for Communication Pro-tocols,.Invited paper, Proceedings of the I W P T S I V - Int. Workshop on Protocol Test Systems, Leischendam, The Netherlands, 1991. [Vuo-94] V S T Vuong, HJahssen , Y L u , C Mathieson: and B Do, TESTGEN: An environment For Protocol Test Suite Generation and Selection, Computer Communications, V . 17, No. 4, A p r i l 1994. [Zha-95] R u i Zhang Master ,Thesis j to. he released in 1996. -Appendix A Estelle.Y specification of the simplified Z39.50 used in T E S T G E N s p e c i f i c a t i o n Z39500rigin; CONST accept = 0: i n t ; . reject - .1: i n t ; . - . •-•• ' success = 0: i n t ; . . • . f a i l u r e = 1: i n t ; • prefMessageSize = 1024: i n t ; normalCloseReason = 0: i n t ; t ' , •'• securityCloseReason = 1: i n t ; VAR • counter: i n t ; searchStatus: irit; ' i s p - . • • -: AEINITreq User; , • AESEAHreq User; ' AEPRESreq User; AECLOSreq User; 63 Appendix A. Estelle. Y specification of the simplified Z39.50 used in TESTGEN MSMessage : Net; ; • User; User; User; Net; PDU INITREQ recv_in AEINITreq,' sent_in MSMessage; INITRESPACCEPT recv^in MSMessage, sent_in AEINITconf; INITRESPREJECT recv.in. MSMessage, sent.in AEINITconf; SEAHREQ recv.in AESEAHreq, sent_in MSMessage; SEAHRESPSUCCESS recv.in MSMessage, sent_in AESEAHconf; SEAHRESPFAILURE recv.in MSMessage, se'nt_in AESEAHconf; PRESREQ recv.in AEPRESreq, sent_in MSMessage; PRESRESP recv_in MSMessage, sent_in AEPRESconf; .. CLOSREQ recv_in AECLOSreq, OSP AEINITconf AESEAHconf AEPRESconf MSMessage Appendix A. Estelle. Y specification of the simplified Z39.50 used in TESTGEN sent_in MSMessage; INVALID recv_in MSMessage; TIMER none 0 ; STATE CLOSED, INIT_SENT, IDLE, SEAH_SENT, PRES_SENT; INITIALIZATION '•' TO CLOSED BEGIN • ' counter := 0 ; searchStatus := f a i l u r e ; END; • i trans • FROM CLOSED to INIT_SENT when AEINITreq output INITREQ begin INITREQ.protocolVersion := AEINITreq.protocolVersion; INITREQ.options := AEINITreq.options; INITREQ.prefMessageSize := AEINITreq.prefMessageSize; INITREQ.maxRecordSize := AEINITreq.maxRecordSize; end; Appendix A. Estelle.Y specification of the simplified Z39.50 used in TESTGEN 66 FROM INIT_SENT to IDLE when'INITRESPACCEPT. output AEINITconf begin AEINITconf.protocolVersion := INITRESPACCEPT.protocolVersion; AEINITconf.options := INITRESPACCEPT.options; AEINITconf.prefMessageSize := INITRESPACCEPT.prefMessageSize; AEINITconf.maxRecordSize := INITRESPACCEPT.maxRecordSize; AEINITconf.result := accept; . counter := counter + 1; end; FROM INIT_SENT to CLOSED when INITRESPREJECT output AEINITconf begin AEINITconf.protocolVersion := INITRESPREJECT.protocolVersion; AEINITconf.options := INITRESPREJECT.options; AEINITconf.prefMessageSize := 0; AEINITconf.maxRecordSize := 0; AEINITconf.result := reject; counter := 0; end; FROM IDLE to SEAH_SENT , ' ' when AESEAHreq output SEAHREQ begin Appendix A. Estelle.Y specification of the simplified Z39.50 used in TESTGEN 67 SEAHREQ.databaseName := AESEAHreq.databaseName; SEAHREQ.query := AESEAHreq.query; SEAHREQ.resultSetName := AESEAHreq.resultSetName; end; FROM SEAH.SENT to IDLE when SEAHRESPSUCCESS output AESEAHconf begin AESEAHconf.resultCount := SEAHRESPSUCCESS.resultCount; AESEAHconf.numOfRecsReturned := SEAHRESPSUCCESS.numOfRecsReturned AESEAHconf.searchStatus := success; counter := counter + 1 ; searchStatus := success; end; FROM SEAH_SENT to IDLE when SEAHRESPFAILURE output AESEAHconf begin AESEAHconf.resultCount := SEAHRESPFAILURE.resultCount; AESEAHconf.numOfRecsReturned := SEAHRESPFAILURE.numOfRecsReturned AESEAHconf.searchStatus := f a i l u r e ; counter := counter + 1 ; searchStatus := f a i l u r e ; end; . FROM IDLE to PRES.SENT when AEPRESreq Appendix A. Estelle. Y specification of the simplified Z39.50 used in TESTGEN provided (searchStatus = success) output PRESREQ begin PRESREQ.resultStartPoint := AEPRESreq.resultStartPoint; PRESREQ.numOfRecsReqested := AEPRESreq.numOfRecsReqested end; FROM PRES_SENT to IDLE when PRESRESP output AEPRESconf begin AEPRESconf.numOfRecsReturned := PRESRESP.numOfRecsReturned; AEPRESconf.presentStatus := PRESRESP.presentStatus; counter := counter +1; end; FROM IDLE to CLOSED when AECLOSreq output CLOSREQ begin CLOSREQ.closeReason := normalCloseReason; counter := 0 ; end; FROM INIT_SENT to CLOSED .• when INVALID output CLOSREQ begin CLOSREQ.closeReason := securityCloseReason; Appendix A. Estelle.Y specification of the simplified Z39.50 used in TESTGEN counter- := 0; end; •>'•; FROM INIT_SENT to CLOSED when PRESRESP output CLOSREQ begin CLOSREQ.closeReason : counter := 0; end; FROM INIT.SENT to CLOSED when SEAHRESPSUCCESS output CLOSREQ . begin CLOSREQ.closeReason : counter '.':= 0; end; FROM IDLE to CLOSED when INVALID output CLOSREQ begin CLOSREQ.closeReason : counter := 0; end; FROM SEAH_SENT to CLOSED when INVALID . output CLOSREQ securityCloseReason; securityCloseReason; securityCloseReason; Appendix A. Estelle. Y specification of the simplified Z39.50 used in TESTGEN 70 begin CLOSREQ.closeReason counter := 0; end; FROM PRES.SENT to CLOSED when INVALID output CLOSREQ begin CLOSREQ.closeReason counter := 0; end; end. securityCloseReason; securityCloseReason; Appendix B ASN.l specification of the simplified Z39.50 used in T E S T G E N Z39500rigiri DEFINITIONS :•:='•' ' BEGIN . DataString ::= OCTET STRING ; User ::= CHOICE i - \" .;• .• . . -AEINITreq, • AEINITind, , • AEINITresp, •'• \"- ' AEINITconf, AESEAHreq, , - AESEAHind, ' ' AESEAHresp, AESEAHconf, AEPRESreq, \" AEPRESind, AEPRESresp, • 71 Appendix B. ASN.l specification of the simplified Z39.50 used'in TESTGEN 72 AEPRESconf, AECLOSreq, AECLOSind } AEINITreq ::= SEQUENCE { protocolVersion DataString, options DataString, prefMessageSize INTEGER, — fixedValue (1024) maxRecordSize INTEGER. — fixedValue (1024) } AEINITind ::= SEQUENCE { ; protocolVersion DataString, options DataString, prefMessageSize INTEGER, maxRecordSize INTEGER } AEINITresp ::= SEQUENCE protocolVersion DataString, options DataString, prefMessageSize INTEGER, - {fixedValue (1024)} Appendix B. ASN.l specification of the simplified Z39.50 used in TESTGEN maxRecordSize INTEGER, — {fixedValue (1024)} result INTEGER — {accept (0), reject ,(i) } } AEINITconf :.:= SEQUENCE { protocolVersion DataString, options DataString, prefMessageSize INTEGER, ' maxRecordSize INTEGER, result INTEGER } AESEAHreq ::= SEQUENCE { databaseName DataString, query DataString, resultSetName DataString } AESEAHind ::= SEQUENCE { databaseName DataString, query . DataString,, resultSetName DataString Appendix B. ASN.l specification of the simplified Z39.50 used in TESTGEN 74 } AESEAHresp ::= SEQUENCE { resultCount INTEGER, numOfRecsReturned INTEGER } AESEAHconf '': : = SEQUENCE { \" •-resultCount INTEGER, numOfRecsReturned INTEGER, searchStatus, INTEGER } AEPRESreq ::= SEQUENCE resultStartPoint INTEGER, ~ { fixedValue ( i ) } numOfRecsReqested INTEGER — { fixedValue (9) } > \"\"' AEPRESind ::= SEQUENCE resultStartPoint INTEGER, . numOfRecsReqested INTEGER ' i fixedValue (18) > — { fixedValue (5) > Appendix B. ASN.l specification of the simplified Z39.50 used in TESTGEN AEPRESresp ::= SEQUENCE { numOfRecsReturned INTEGER, presentStatus INTEGER } AEPRESconf ::= SEQUENCE . numOfRecsReturned INTEGER, presentStatus INTEGER } . ' : AECLQSreq ::= SEQUENCE { closeReason INTEGER — {normalCloseReason (0)} > AECLQSind ::= SEQUENCE { closeReason INTEGER > Net ::= CHOICE { MSMessage Appendix B. ASN:1 specification of the simplified Z39.50 used in TESTGEN 76 } MSMessage ::= SEQUENCE { - . ' ' ' ' . \\ • dummy INTEGER PduMessages ::= CHOICE { . -' INITREQ, INITRESPACCEPT, INITRESPREJECT, SEAHREQ, ; • SEAHRESPSUCCESS, SEAHRESPFAILURE, ; PRESREQ, -PRESRESP/ CLOSREQ, INVALID . > . ' ' <'•'. ' :> • L . INITREQ ::= SEQUENCE protocolVersion DataString, options DataString, . prefMessageSize INTEGER,-Appendix B. ASN.l specification of the simplified Z39.50 used in TESTGEN maxRecordSize INTEGER INITRESPACCEPT ::= SEQUENCE ; { protocolVersion DataString,. options DataString, prefMessageSize INTEGER, maxRecordSize INTEGER, result ' INTEGER {fixedValue (1024)} '{fixedValue (1024)} {accept (0)} INITRESPREJECT ::= SEQUENCE { protocolVersion DataString, options DataString, prefMessageSize INTEGER, maxRecordSize INTEGER, result INTEGER } .{fixedValue (1024)} {fixedValue (1024)} {reject (1)} SEAHREQ ::= SEQUENCE { . ' ' \" .' databaseName DataString, query DataString, resultSetName DataString Appendix B. ASN.l specification-of the simplified Z39:50 used in TESTGEN SEAHRESPSUCCESS ::= SEQUENCE resultCount . INTEGER, — {fixedValue (18)} numOfRecsReturned INTEGER, — {fixedValue (9)} searchStatus- INTEGER ~ {success (0)} SEAHRESPFAILURE ::= SEQUENCE ' ;.'•:•. { . , ' . . - '\" ; \" ..: . : ; : . • ' , , ' resultCount , INTEGER, — {fixedValue (0)} numOfRecsReturned INTEGER, — {fixedValue (0)} searchStatus- INTEGER\" — {failure (1) } : > . . ' ' • •• • • ' V ' PRESREQ ::= SEQUENCE • . ' ' . . . . :'. resultStartPoint' INTEGER, / numOfRecsReqested INTEGER, resultSetName DataString ,} - , ; .' . \\ .... 'PRESRESP. ::= SEQUENCE-numOfRecsReturned INTEGER, — {fixedValue (9)} presentStatus INTEGER ~ {alwaysOK (0)} Appendix B. ASN.l specification of the simplified Z39.50 used in TESTGEN } CLOSREQ ::= SEQUENCE . ' closeReason INTEGER > INVALID ::= SEQUENCE { dummy INTEGER — {onlyZero (0)> } 'END ,• Appendix C Constraints defined in T E S T G E N menus # = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = # # TSG Constraints Editor ( STATE ) . # # . ================================ # # # # (a) (b) # # + + _______ + _+ + # # | key I Name I min-use I max-use I # # + + __: _ . .+ + _ + # # | 0 I CLOSED 10 |1 | # # | 1 | INIT.SENT 10 |1 I # # | 2 I IDLE |0 |4 I # # | 3 I SEAH_SENT I' 0. I 4- I # # | 4 | PRES.SENf 10 14 I # # +_____+__.—.—.—. — — ; +— + -+' # # # #=====================================================================# # ; TSG Constraints Editor ( ISP ) # # ============================== # # # 80 Appendix C. Constraints defined in TESTGEN menus 81 # (a) (b) # # + + .: _ . _ + + - —+ # # I key | Name I min-use I max-use |'# # + + ;_ _ + :—+____ + # # | 0 | AEINITreq I 0 | 1 | # # | 1 | AESEAHreq I 0 | 4 I # # | 2 | AEPRESreq I 0 I 4 | # # | 3 | AECLDSreq I 0 | 1 I # # | 4 | MSMessage I 0 I 1 I # # + + + . + . + # #=====================================================================# # TSG Constraints Editor ( OSP ) # # ============================== # # # # (a) (b) # #. +_____+___ •—+ + -—+ # # | key | Name I min-use I max-use | # # .+• • + : '• + + - - — -+ # # 1 0 I AEINITconf •> . • ' 1.0 I 1 I # # | 1 | AESEAHconf I 0 I 4 I # # 1 2 I AEPRESconf I 0 I 4 I # # | 3 I MSMessage I 0 I 1 I # # + + _ _ :__ ____+ + .+ # #=====================================================================# Appendix C. Constraints defined in TESTGEN menus # # # # # + + # | key | Name # + TSG Constraints Editor ( PDU ) # # # + _+_________+ # I min-use | max-iise | • # (a) (b) —+ .• + — + — - + # 0 . 1 INITREQ 1 0 1 i 1 # 1 I INITRESPACCEPT 1 0 1 l 1 # 2 I INITRESPREJECT 1 o 1 l 1 # 3 I SEAHREQ 1 o 1 4 1 # 4 I SEAHRESPSUCCESS 1 0 . 1 4 1 # 5 I SEAHRESPFAILURE | 0 1 4 1 # 6 I PRESREQ l o . 1 4 1 # 7 I PRESRESP 1 0 1 4 1 # 8 I CLOSREQ 1 0 I 1 1 # 9 • I INVALID l o |1 1 # —+ ' — — : +_ ._.—+ - — + # # # # # # # # # # # # + Interactive Service Primitive Parameter Definition, =# # # # # ISP: AEINITreq ( 4 parameter ) => 4 instances # Appendix C. Constraints defined in TESTGEN menus + — : • — • -+ I Key Type Parameter name I I values I + : ; : • + I 0 char* AEINITreq.protocolVersion I I .0 '111' I I 1 char* AEINITreq.options I I ..0 '111111' I I 2 int AEINITreq.prefMessageSize I I .0 1024 I 1.1 2048 I I 3 int AEINITreq.maxRecordSize I 1.0 1024 I I .1 2048 I + : • •\"• ; • + #=============================================================^=======# ,.'# Interactive Service Primitive Parameter De f i n i t i o n # # ================================================== # # , # # ISP: AESEAHreq ( 3 parameter ) => 1 instances # #=====================================================================# +- •- ' •—;—• • + I Key Type Parameter name I I values | Appendix C. Constraints defined in TESTGEN menus 84 . + ' ' + I 4 char* AESEAHreq.databaseName I I .0 .'searchDatabase' I I 5 char* AESEAHreq.query I I .0 'searchQuery' \" ' I I 6 char* AESEAHreq.resultSetName I I .0 'searchResultSetName' I + • + #=====================================================================# # Interactive Service Primitive Parameter De f i n i t i o n # # ================================================== # # # # ISP: AEPRESreq ( 2 parameter ): => 1 instances # # = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = # • +_ . ' . _ _ — + ' I Key Type Parameter name I I values I .+ • —: '•— • •+ I 7 int AEPRESreq.resultStartPoint |. I .0 1 I I 8 int AEPRESreq.numOfRecsReqested I , I .0 9 I + : \" ;- + Appendix C. Constraints defined in TESTGEN menus , .•> .85 #=====================================================================# , # Interactive Service Primitive Parameter D e f i n i t i o n # # __=_=_______________^^ # - r \" ' . ; ; - . # # ISP: AECLOSreq ( i parameter )=> 1 instances # #===============i=====================================================# + -; — — . — '--I . ~ — + I Key Type Parameter name I I '• values * - • I •+ —•—. .; — _ — _ _ _ — : _—. _ + ; .• I 9 int AECLOSreq.closeReason I I .o o \" • .•• I +--- — — ~: __________________ ._. . ____.—__+ #==-=============================================^ # Interactive Protocol Data Unit Parameter D e f i n i t i o n # # .: ========== = = ========= = = = =====^ # •# . ; / ' • • ; ' ' • ' ' • # •• # PDU: INITRESPACCEPT ( 5 parameter ) => 4 i n s t a n c e s * #=====================================================================# I Key Type Parameter name ' '• • I I values . • | + • — — — — — - — . — — - — — — — — + Appendix C. Constraints defined in TESTGEN menus 125 char* INITRESPACCEPT.protocolVersion , 1.0 '111' |26 char* INITRESPACCEPT.options 1.0 '111111' 127 int INITRESPACCEPT.prefMessageSize I .0 1024 I .1 2048 128 int INITRESPACCEPT.maxRecordSize I .0 1024 . I .1 2048 129 int INITRESPACCEPT.result I .0 0 + . • • • :- • — — —+ #=====================================================================# # Interactive Protocol Data Unit Parameter Definition. # # ================================================== # # :' .... • . ' ; .#• # PDU: INITRESPREJECT ( 5 parameter ) => 1 instances # #=====================================================================# + •- '—; •———-: ' + I Key Type Parameter name I I values I + • • • • — + 130 char*.INITRESPREJECT.protocolVersion I Appendix C. Constraints defined in TESTGEN menus 87 I .0 dummy_val1 I |31 char* INITRESPREJECT.options I I .0 dummy_val1 I |32 int INITRESPREJECT.prefMessageSize I I .0 0 I |33 int INITRESPREJECT.maxRecordSize * • I I .0 0 | 134 int INITRESPREJECT.result I I .0 1 I + . •— . + #=====================================================================# # Interactive Protocol Data Unit Parameter Def i n i t i o n # # ================================================== # # # .# PDU: SEAHRESPSUCCESS ( 3 parameter ) => 2 instances # #=====================================================================# + — — • • + I Key Type Parameter name I I values I + • : • — -+ • |38 int SEAHRESPSUCCESS.resultCount I I .0 9 I 1 . 1 1 8 I |39 int SEAHRESPSUCCESS.numOfRecsReturned I Appendix C. Constraints defined in TESTGEN menus I .0 5 I |40 int SEAHRESPSUCCESS.searchStatus I I .0 0 I + . • — - + #=====================================================================^ # Interactive Protocol Data Unit Parameter D e f i n i t i o n # # ================================================== # # # # PDU: SEAHRESPFAILURE ( 3 parameter ) => 1 instances # #=====================================================================# + • : - • '• • ~ • + I Key Type Parameter name I I values• I + - • : ; . —' : ~ ~ ' + |41 int . SEAHRESPFAILURE.resultCount . I 1.0; 0 I |42 int SEAHRESPFAILURE.numOfRecsReturned I 1.0 0 I |43 int SEAHRESPFAILURE.searchStatus I I .0 1 I + : • -+ #=====================================================================# # Interactive Protocol Data Unit Parameter D e f i n i t i o n # Appendix C. Constraints defined in TESTGEN menus # ================================================== # # # # PDU: PRESRESP ( 2 parameter j => 2 instances # . #=====================================^ + --+ I Key Type Parameter name I I values I + — ; — -.— : + |47 int PRESRESP.numOfRecsReturned I I .0 9 I 148 int PRESRESP.presentStatus I 1.0 I 1 . 1 . 1 I + : : ;- — ' - - + #=====================================================================# # Interactive Protocol Data Unit Parameter De f i n i t i o n # # = = = = = = = = = = = = = = = F = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = # # . # # PDU: INVALID ' ( 1 parameter ) => 1 instances # #=====================================================================# + - ; • • •• ; : : • . + -I Key Type Parameter name ' I I values I Appendix 0. Constraints defined in TESTGEN menus . 90 150 int INVALID.dummy I I .o o I + •— • -+ Appendix D Some test cases with denned constraints without coverage ISP: AEINITreq. { protocolVersion = '111'' options ='111111' prefMessageSize = 1024 maxRecordSize,= 1024 •• ' .>•• • . . ' . . ' .. IPDU: + — - — : + I CLOSED | +-- --'+ . I I OSP : — I0PDU1:INITREQ I {' protocolVersion = '111' I options = '111111' I.-. pref MessageSize. = 1024 I ' maxRecordSize = 1024 I > • 10PDU2:; I : 91 Appendix D. Some test cases with defined constraints without coverage 92 ISP: IPDU: INITRESPACCEPT { protocolVersion = '111' • . options = '111111' prefMessageSize = 1024 maxRecordSize = 1024 result = 0 > + — — V + I INIT_SENT | + + 0SP1:AEINITconf { p r o t o c o l V e r s i o n - '111' options = '111111' prefMessageSize = 1024 maxRecordSize = 1024 result = 0 } •SP2: •PDU : — +—V—+ I IDLE | + + Appendix D.. Some test cases with defined constraints without coverage 93 ISP: AESEAHreq .{ databaseName = 'searchDatabase' query = 'searchQuery' resultSetName = 'searchResultSetName' > IPDU: OSP : 0PDU1:SEAHREQ { databaseName = 'searchDatabase' query = 'searchQuery' resultSetName = 'searchResultSetName' } 0PDU2:—-+ V - + I SEAH.SENT I ISP: OSP1:AESEAHconf { resultCount = 9 numOfRecsReturned = 5 searchStatus = 0 } Appendix D. Some test cases with defined constraints without coverage 94 IPDU:SEAHRESPSUCCESS { resultCount = 9 numOfRecsReturned = 5 searchStatus = 0 } ISP: AEPRESreq { resultStartPoint = 1 numOfRecsReqested = 9 > ' IPDU:— ' 0SP2: — OPDU : — + V — + I IDLE r + + OSP : — OPDUl:PRESREQ {r e s u l t S t a r t P o i n t =1 numOfRecsReqested =9 resultSetName = def.string > -0PDU2:—-+ •—v——+ Appendix D. Some test cases with defined constraints without coverage I PRES_SENT | ISP: --IPDU:PRESRESP { numOfRecsReturned = 9 presentStatus = 0 } ISP: AECLOSreq { closeReason = 0 > IPDU: — OSP1:AEPRESconf { numOfRecsReturned presentStatus = 0 } 0SP2: •PDU : — + V — + I . IDLE | + T \" + •SP : 0PDU1:CLOSREQ {c loseReason = 0 > Appendix D. Some test cases with defined constraints without coverage '-' 96 I0PDU2:— ' ''. :. . -'-'.^ : • I .CLOSED i • •'• . • . :, ' + ~ -+. . I 7 ,' i Appendix E The set of selected test cases using test coverage tool coverage i s 1.000000 coverage guarantee i s 0.999023 effective radius i s 0.000000 number of test cases i s 14 cost of the test cases i s 14 Pass 1, tolerance 2.000000 Overall cost i s now 0 Pass 2, tolerance 1.000000 1/ (AEINITreq, 1) (INITRESPACCEPT, 1) (AESEAHreq, 1) (SEAHRESPSUCCESS, 1) (AEPRESreq, 1) (PRESRESP, 1) (AECLOSreq, 1) Overall cost i s now 1 Pass 3, tolerance 0.500000 1/ (AEINITreq, 1) (INITRESPREJECT, 1) Overall cost i s now 2 Pass 4, tolerance 0.250000 1/ (AEINITreq, 1) (INITRESPACCEPT, 1) (AECLOSreq, 1) 97 Appendix E. The set of selected test cases using test coverage tool 2/ (AEINITreq, 1) (INVALID, 1) 3/ (AEINITreq,.1) (PRESRESP, 1) 4/ (AEINITreq, 1) (SEAHRESPSUCCESS, 1) Overall cost i s now 6 Pass 5, tolerance 0.125000 1/ (AEINITreq, 1) (INITRESPACCEPT, 1) (AECLOSreq, 1) 2/ (AEINITreq, 1) (INITRESPACCEPT, 1) 3/ (AEINITreq, 1) (INITRESPACCEPT,. 1) Overall cost i s now 9 Pass 6, tolerance 0.062500 1/ (AEINITreq, 1); (INITRESPACCEPT, 1) (AECLOSreq, 1) Overall cost i s now 10 Pass 7, tolerance 0.031250 1/ (AEINITreq, 1) (INITRESPACCEPT, 1) (AEPRESreq, 1) (INVALID, 1) 2/ (AEINITreq, 1) (INITRESPACCEPT, 1) (INVALID, 1) 3/ (AEINITreq, 1) (INITRESPACCEPT, 1) (INVALID, 1) Overall cost i s now 13 (AESEAHreq, 1) (SEAHRESPFAILURE, 1) (AESEAHreq, 1) (INVALID, 1) . . (INVALID, 1) (AESEAHreq, 1) (SEAHRESPSUCCESS, 1) (AESEAHreq, 1) (SEAHRESPSUCCESS, 1) (AESEAHreq, 1) (SEAHRESPSUCCESS, 1) (AESEAHreq, 1) (SEAHRESPFAILURE, 1) Appendix E. The set of selected test cases using test coverage tool 99 Pass 8, tolerance 0.015625 Overall cost i s now 13 Pass 9, tolerance 0.007812 1/ (AEINITreq, 1) (INITRESPACCEPT, 1) (AESEAHreq, 1) (SEAHRESPSUCCESS, 1) (AEPRESreq, 1) (PRESRESP, 1) (INVALID, 1) Overall cost i s now 14 Pass 10, tolerance 0.003906 Overall cost i s now 14 Pass 11, tolerance 0.001953 Overall cost i s now 14 And the test cases are: 1/ (AEINITreq, 1) (INITRESPACCEPT, 1) (AESEAHreq, 1) (SEAHRESPSUCCESS, 1) (AEPRESreq, 1) (PRESRESP, 1) (AECLOSreq, 1) 2/ (AEINITreq, 1) (INITRESPREJECT, 1) 3/ (AEINITreq, 1) (INITRESPACCEPT, 1) (AECLOSreq, 1) 4/ (AEINITreq, 1) (INVALID, 1) 5/ (AEINITreq, 1) (PRESRESP, 1) 6/ (AEINITreq, 1) (SEAHRESPSUCCESS, 1) Appendix E. The set of selected test cases using test coverage tool 100 7/ (AEINITreq, 1) (INITRESPACCEPT, 1) (AESEAHreq, 1) (SEAHRESPFAILURE, 1) (AECLOSreq, 1) 8/ (AEINITreq, 1) (INITRESPACCEPT, 1) (AESEAHreq, 1) (INVALID, 1) 9/ (AEINITreq, 1) (INITRESPACCEPT, 1) (INVALID, 1). 10/ (AEINITreq, 1) (INITRESPACCEPT, 1) (AESEAHreq, 1) (SEAHRESPSUCCESS, 1) (AECLOSreq, 1) 11/ (AEINITreq, 1) (INITRESPACCEPT, 1) (AESEAHreq, 1) (SEAHRESPSUCCESS, 1) (AEPRESreq, 1) (INVALID, 1) , 12/ (AEINITreq, 1) (INITRESPACCEPT, 1) (AESEAHreq, 1) (SEAHRESPSUCCESS, 1) (INVALID, 1) \" 13/ (AEINITreq, 1) (INITRESPACCEPT, 1) (AESEAHreq, 1) (SEAHRESPFAILURE, 1) (INVALID, 1) 14/ (AEINITreq, 1) (INITRESPACCEPT, 1) (AESEAHreq, 1) (SEAHRESPSUCCESS, 1) (AEPRESreq, 1) (PRESRESP, 1) (INVALID, 1) A p p e n d i x F Tes t cases i n T T C N f o r m • $Suite $SuiteId suiteOOOl ~ $DeclarationsPart $Begin_TS_ConstDcls ; $TS_ConstDcl $TS_ConstId prefMessageSize $TS_ConstType INTEGER $TS_ConstValue 1024 $End_TS_ConstDcl $End_TS_ConstDcls $Begin_TS_VarDcls $TS_VarDcl $TS_VarId counter $TS_VarType INTEGER $TS_VarValue 0 $End_TS_VarDcl $End_TS_VarDcls .. $Begin_PCO_Dcls $PCD_Dcl $PC0_Id L 101 Appendix F. Test cases in TTCN form $PCO_TypeId User $End_PCO_Dcl $PCO_Dcl $PCO_Id L $PCD_TypeId Net $End_PCO_Dcl $PCO_Dcl $PCO_Id L $PCO_TypeId USer $End_PCO_Dcl $End_PCQ_Dcls $ASP_TypeDefs * $ASNl_ASP_TypeDefs $Begin_ASNl_ASP_TypeDef $ASP_Id AEINITreq $PCO_TypeId User . $Comment $ASNl_TypeDefinition SEQUENCE { . protocolVersion OCTETSTRING, options OCTETSTRING, prefMessageSize INTEGER, maxRecordSize INTEGER } $End_ASNl_TypeDefinition Appendix F. Test cases in TTCN form $End_ASNl_ASP_TypeDef $Begin_ASNl_ASP_TypeDef $ASP_Id AESEAHreq $PCO_TypeId User $Comment $ASNl_TypeDefinition SEQUENCE { databaseName OCTETSTRING, query OCTETSTRING, resultSetName OCTETSTRING } $End_ASNl_TypeDefinition $End_ASNl_ASP_TypeDef $Begin_ASNl_ASP_TypeDef $ASP_Id AEPRESreq $PCO_TypeId User $Comment $ASNl_TypeDefinition SEQUENCE { resultStartPoint INTEGER, numOfRecsReqested INTEGER } . $End_ASNl_TypeDefinition $End_ASNl_ASP_TypeDef Appendix F. Test cases in TTCN, form 104 $Begin_ASNl_ASP_TypeDef $ASP_Id AECLOSreq $PCO_TypeId User $Comment $ASNl_TypeDefinition SEQUENCE { closeReason INTEGER }. $End_ASNl_TypeDefinition $End^.ASNi_ASP_TypeDef $Begin_ASNl_ASP_TypeDef $ASP_Id AEINITresp $PCO_TypeId User $Comment $ASNl_TypeDefinition Appendix G State tables used for Z3950 protocol ./* d e f i n i t i o n of the state tables */.•'• /* .The items on one l i n e of each table (from l e f t to right) are: int transition_name int State int Event STATE_TABLE Subtable FUNC int int FUNC int TodoO the enumerated name of the t r a n s i t i o n . It must be present i n the t r a n s i t i o n matrix, the current state of the FSM the coming event the address of the subtable, or NULL i f none function executing actions in t h i s situation This function i s integer-type and i t must: return either SUCCESS (0) or non-zero value. Non-zero value w i l l cause Target to stop. Todo-Parm.. the parameter for the function TodoO Next-State, the next state of the machine after TodoO Event_Maker() i f not NULL, w i l l generate new Event (other from Origin's PDUs) E-M-Parm... the parameter for t h i s Event-MakerQ Notes: 105 Appendix G. State tables used for Z3950 protocol 106 - i f ' t h e next state i s EXIT (subtable), then the next table w i l l be the main table, and the current state w i l l be restored from the previous one. The coming event w i l l be END_0P_IND. - in.the subtables, the f i r s t l i n e do not correspond to the spec. This l i n e only serves as the entry state and event f o r the subtable. * / : /* the main table */ STATE_TABLE MAINTableG = { /* CLOSED state */ ,; ININD, CLOSED, INIT.PDU, NULL, In i t l n d , 0, INITRECVD, Dolnit, INIT.PDU, ERR10, CLOSED, ANYELSE, NULL, Error, CLOSED.CLOSED, KillJDP,CLOSED, /* INITRECVDstate */ ACEPT,INITRECVD, RESP_ACCEPT,NULL, InitResp.ACCEPT, IDLE, . NULL, 0, REJCT,INITRECVD, RESPIREJECT,NULL, InitResp,REJECT, STOPFSM, NULL, 0, SENAC,INITRECVD, ACC.REQ, NULL, InitResp,ACCREQ, ACC.SENT, NULL, 0, SENRC,INITRECVD, RSC_REQ, NULL, InitResp,RESREQ, RSC_SENT, NULL, '0, ERR20.INITRECVD, ANYELSE, NULL, Error, INITRECVD, INITRECVD,Kill.OP,INITRECVD, /* Init's ACC_SENT state */ ACCNF, ACC_SENT, ACC_PDU, NULL, ACC_Conf,0, INITRECVD,DoInit, ACC_PDU, . ERR30, ACC_SENT, ANYELSE, NULL, Error, ACC_SENT,ACC_SENT, Kill_0P', ACC_SENT, /* I n i t ' RSC_SENT state */ Appendix G- State tables used for Z3950 protocol 107 RSCNF, RSC_SENT, RESC_PDU,NULL,RESC_,Conf,INITJDP, INITRECVD.Dolnit, RESC_PDU, ERR40, RSC_SENT, ANYELSE, NULL,Error, RSC.SENT,RSC.'SENT, Kill_OP,RSC_SENT, /* IDLE state */ DOSEA, IDLE, SEAH.PDU, SEAHTable, NULL, 0, ACTIVE, DoOP, SEAH_PDU, DOPRE, IDLE, PRES.PDU, PRESTable, NULL, 0, ACTIVE, D60P, PRES_PDU, CLOIN, IDLE, CL0S_PDU, NULL, Closelnd.O, CLOSRECVD,DoCL0S, IDLE, • CL045, IDLE, CL0S_REQ, NULL, AbClose, IDLE.CLOSSENT, FakeCLOS_PDU,IDLE, ERR50, IDLE, ANYELSE, NULL, Error, IDLE,IDLE, K i l l _ 0 P , IDLE, /* ACTIVE state */ ENDIN, ACTIVE,END_0P_IND,NULL, 0P_End_Ind, 0, IDLE, NULL, CL052, ACTIVE,.CL0S_RESP, NULL, SendClose, ACTIVE,STOPFSM, NULL, CL055, ACTIVE,CLOS.REQ, NULL, AbClose, ACTIVE,CLOSSENT,FakeCLOS_PDU, ERR60, ACTIVE,ANYELSE, NULL, Error, ' ACTIVE,ACTIVE, KillJDP, /* CLOSSENT state */ ' . CLONF, CLOSSENT, CL0S_PDU, NULL, CloseConf, 0, STOPFSM, NULL, 0, CL065, CLOSSENT, ANYELSE, NULL, NULL, 0, CLOSSENT,NULL, 0, /•CLOSRECVD state */ SENCL, CLOSRECVD,CL0S_RESP, NULL, SendClose, CLOSRECVD, STOPFSM, NULL, 0, CL070, CLOSRECVD,CL0S_REQ, NULL, AbClose, CLOSRECVD, STOPFSM, NULL, 0, CL075, CLOSRECVD,ANYELSE, NULL, NULL, 0, CLOSRECVD, NULL, 0, TAB15, TABLEND Appendix G. State tables used for Z3950 protocol 108 /* subtable f or SEARCH operation */ STATE.TABLE SEAHTable[] = •. ( - • * \\\" ' ~ '; { . ••;. ' ' •. '• ; ' .'; .\" ;. ;... /• . ; .' .. •• .• : \"• . , • ,7 '; /* The entry state and event, i . e . whenever t h i s subtable i s entered, the • ' current .state i s 0P_START, and the coming event w i l l be 0P_PDU *./ •PBEG, 0P_START, OP.PDU, NULL, NULL, 0, 0P_RECVD, DoSEAH,OP.PDU, ; /* The 0P_RECVD state */ - , y . , QPRSC, 0P_RECVD, OPRSCREQ, NULL, SendRESC, SEAH_0P, OPRSCSENT,GetRESC,0, . • \\ OPACC, 0P_RECVD, OPACCREQ, NULL, SEAHResp, OPACCREQ,OPACCSENT,NULL, 0, \\-OPTRG, 0P_RECVD, TRIGRC_PDU,NULL, TRIG.Conf,SEAH_0P, 0P_RECVD, DoSEAH, TRIGRC.PDU, OPEND, OP.RECVD, 0P_RESP, NULL, SEAHResp, 0P_RESP, EXIT, Exit_0P,0P_RECVD, EXI02, OP.RECVD, CLOS.PDU, NULL, Closelnd, 0P_RECVD,EXIT, DoCLOS, OP.RECVD, EXI05, OP.RECVD, CLOS.REQ, NULL, NULL, 0, .. EXIT,- Kill^OP,0P_'RECVD, EXI10, OP.RECVD, ANYELSE, NULL, Error, OP_RECVD,EXIT, Kill_0P,0P_RECVD, /* the OPACCSENT state */ OPACF, OPACCSENT,ACC_PDU, NULL, ACC_Conf, SEAH_0P, 0P_RECVD,DoSEAH, ACC.PDU, EXI12, OPACCSENT,CL0S_PDU,NULL, Closelnd, OPACCSENT,EXIT, DoCLOS, OPACCSENT, EXI15, OPACCSENT,CL0S_REQ.NULL, NULL, 0, EXIT, Kill.OP,OPACCSENT, /• EXI20, OPACCSENT,ANYELSE',. NULL, Error, OPACCSENT,EXIT, 'Kill_0P,OPACCSENT, /* the OPRSCSENT state */ . ). OPRCF, OPRSCSENT,RESC.PDU, NULL, RESC_Conf,SEAH_0P, OP.RECVD, DoSEAH, RESC_PDU, Appendix G. State tables used for Z3950 protocol 109 EXI22, OPRSCSENT,CLOS.PDU, NULL, Closelnd, OPRSCSENT,EXIT, DoCLOS, OPRSCSENT, EXI25, OPRSCSENT,CL0S_REq, NULL, NULL, 0, • . EXIT, K i l l _ 0 P , OPRSCSENT, EXI27, OPRSCSENT,TRIGRC_PDU,NULL,. TRIG.Conf,SEAH_0P, OPRSCSENT,NULL, 0, EXI30, OPRSCSENT,ANYELSE, NULL, Error, OPRSCSENT,EXIT, K i l l _ 0 P , OPRSCSENT, TAB05, TABLEND , : : ' . \" ' ; : : ' •: : : . , ' • /* subtable f o r PRESENT operation */ STATE_TABLE _ f a r PRESTable[] = . •c : . ;,. ' • . • • ; . ' ' • . •• • • , [\"'. 7* The entry state and event, i . e . whenever thistsubtable i s entered, the • current state i s PR_START and the incoming event w i l l be PR_PDU */ PRBEG, PR_START, PR_PDU, NULL, NULL, 0, PR_RECVD, DoPRES, PR.PDU, ./* the PRRSC, PRACC, PRTRG, PREND, PRSEG, EXI32, EXI35, EXI40, PR_RECVD state */ .•' . r ., PR.RECVD, PRRSCREQ, NULL, SendRESC, PRES_0P, PRRSCSENT,NULL, 0 PR.RECVD, PRACCREQ, NULL, PRESResp, PRACCREQ,PRACCSENT..NULL, S 0 PR_RECVD, TRIGRC.PDU,. NULL, TRIG.Conf,PRES_0P, PR.RECVD, DoPRES, TRIGRC.PDU, PR_RECVD, PR_RESP, NULL, PRESResp, PR_RESP, EXIT, Exi't_OP,PR_RECVD, PR_RECVD, PRSEGREQ, .NULL, PRESResp, PRSEGREQ,PR.RECVD,' DoPRES, PRSEGREQ, PR_RECVD, CL0S_P,DU,. NULL, Closelnd, PR_RECVD,EXIT, PR_RECVD, CL0S3EQ, NULL, NULL, 0, -EXIT, PR_RECVD, ANYELSE, NULL, Error, . PR_RECVD,EXIT, DoCLOS, PR.RECVD, Kill_0P,PR_RECVp, Kill_0P,PR_RECVD, /* the PRACCSENT state */ Appendix G. State tables used for Z3950 protocol no PRACF, PRACCSENT.ACCLPDU, NULL, EXI42, PRACCSENT,CLOS_PDU, NULL, EXI45, PRACCSENT,CLOS_REq, NULL, EXI50, PRACCSENT,ANYELSE, NULL, /* the PRRSCSENT state */ PRRCF, PRRSCSENT,RESC_PDU, NULL, EXI52, PRRSCSENT,CLOS_PDU, NULL, EXI55, PRRSCSENT,CLOS_REq, NULL, EXI60, PRRSCSENT,ANYELSE, NULL, J TAB10, TABLEND ACC_Conf, PRES_OP, PR.RECVD, Closelnd, PRACCSENT, EXIT, NULL, 0, EXIT, Error, PRACCSENT, EXIT, RESCConf, PRES.OP, PR_RECVD, Closelnd, PRRSCSENT, EXIT, NULL, 0, EXIT, Error, PRRSCSENT, EXIT,/ DoPRES, ACC.PDU, DoCLOS, PRACCSENT, Kill.OP,PRACCSENT, Kill_OP,PRACCSENT, DoPRES, RESC_PDU, DoCLOS, PRRSCSENT, Kill_0P,PRRSCSENT, Kill.QP,PRRSCSENT, Appendix H Function processing the State Machine Function: Process_StateMachine() Purpose: . t h i s f u n c t i o n looks at the st a t e t a b l e and takes the req u i r e d a c t i o n . I t i s assumed that the current s t a t e and incoming event are stored i n g l o b a l \"gState\" and g l o b a l \"gEvent\" of the g l o b a l t a b l e \"gTable\". Input: the PDU to be processed Ret.value: e i t h e r STOPFSM, i f a f t e r t h i s the program should - stop, or OUTSIDE i f the processing should go on with another PDU. Note: during processing, i f aRet == INSIDE, the loop w i l l repeated (as the event i s generated on the Target s i d e ) . • 111 Appendix H. Function processing the State Machine 1 i n t Process_StateMachine(PDU *thePdu) { STATE.TABLE *aTable_ptr; i n t aRet; i n t anlndex; Look_At_Matrix: * i f ((anlndex = gTransMatrix[gEvent][gState]) != FATAL) /* there i s a matching event/state i n the t a b l e */ aTable_ptr = gTable + anlndex; /* execute \"todo\" f u n c t i o n i f needed */ i f (aTable_ptr->todo != NULL) { aRet = (*aTable_ptr->todo)(aTable_ptr->optionl); /* i f e r r o r occurs i n f u n c t i o n t o d o ( ) , then Target stops */ i f (aRet != SUCCESS) re t u r n (STOPFSM); } Appendix H. Function processing the State Machine 113 /* t r a n s f e r to the next s t a t e .•*/'••• gState = aTable_ptr->next_state; /* must go to subtable or not? */ i f (aTable_ptr->sub_tbl !=NULL) gTable = aTable_ptr->sub_tbl; /* change t a b l e */ i f (gState == EXIT) /* i f e x i t subtable to main t a b l e */ { . - . ' -/* back to main t a b l e */ gState = gPreviousState; gTable = gMainTable; } /* look at the event_maker to see i f should e x i t waiting to PDUs coming from O r i g i n or not =*;/ i f . (aTable_ptr->event_maker != NULL) /* must stay i n s i d e */ { ' ' ' gEvent = (*aTable_ptr->event_maker)(thePdu, aTable_ptr - > o p t i o n 2 ) aRet = INSIDE; ' > el s e { aRet = OUTSIDE; Appendix H. Function processing the State Machine 114 } } e l s e /* A f a t a l e r r o r occurs */ { .' :': ' • P r i n t E r r o r ( \" F a t a l e r r o r , state/event not matched\"); r e t u r n (STOPFSM); > i f (gState == STOPFSM) 7* i f s t a t e = STOPFSM, the job i s done / r e t u r n (STOPFSM);' i f (aRet == INSIDE) /* stay i n s i d e t h i s f u n c t i o n */ goto Look_At_Matrix; r e t u r n (aRet); } Appendix I Test cases generated semiautomatically + —+ I CLOSED | - .+ + ISP: AEINITreq . . |OSP : { protocolVersion = '111' | options = '111111' | prefMessageSize = 1024 I maxRecordSize = 1024 I } I IPDU: I0PDU1:INITREQ • ,' . I { protocolVersion = '111' I . options = '111111'' I prefMessageSize = 1024 I . maxRecordSize = 1024 1 > \" 10PDU2: 115 Appendix I. Test cases generated semiautomatically 116 ISP: IPDU:INITRESPACCEPT { protocolVersion = '111' options = '111111' prefMessageSize = 1024 maxRecordSize = 1024 result = 0 } + -V + I INIT.SENT | + + 0SP1:AEINITconf { protocolVersion = '111' options = ' l l l i l l ' prefMessageSize = 1024 maxRecordSize = 1024 result = 0 } 0SP2: •PDU :-— +; V—+ I IDLE | Appendix I. Test cases generated semiautomatically 117 ISP: AESEAHreq I OSP : — {databaseName = 'searchDatabase' I query = 'searchQuery' I resultSetName I = 'searchResultSetName' I } I IPDU:— 10PDU1: SEAHREQ I {databaseName = 'searchDatabase' I query = 'searchQuery' I resultSetName I = 'searchResultSetName' I > -I I0PDU2:— . I +— V + I SEAH.SENT I +-—-—-- + I ISP: — IOSP1:AESEAHconf | { resultCount =9 I numOfRecsReturned = 5 I searchStatus =0 „ ' - I } I Appendix I. Test cases generated semiautomatically 118 i IPDU:SEAHRESPSUCCESS { resultCount = 9 numOfRecsReturned = 5\" searchStatus = 0 I0SP2: — I \"• I0PDU : — I + — V — + I IDLE I ISP: AEPRESreq ' -r { resultStartPoint =1 numOfRecsReqested = 9 } ' IPDU:— • IOSP |0PDU1:PRESREQ I '•••{ resultStartPoint. = 1 • I numOfRecsReqested =9 . I .\" resultSetName = def_string •• 1 ' > - •' •' 10PDU2: — v——+.'• Appendix I. Test cases generated semiautomatically I PRES_SENT | ISP: IPDU:PRESRESP { numOfRecsReturned = 9 presentStatus = 0 ISP: AECLOSreq { closeReason = 0 } IPDU: OSP1:AEPRESconf { numOfRecsReturned presentStatus = 0: 0SP2: — OPDU : + — V — + • l IDLE; I + --+ OSP : OPDUl:CLOSREq { closeReason = 0 } • Appendix I. Test cases generated semiautomatically I I0PDU2: — I +—-V + I CLOSED | + — + ' +_. .— + i I CLOSED I ' +—-— + ISP: AEINITreq •i protocolVersion = \"111' options = \"111111\" prefMessageSize = 1024 maxRecordSize = 1024 > IPDU: — IOSP :--I I0PDU1:INITREQ I { protocolVersion = \"1111 I options =.\"111111\" I prefMessageSize = 1024 I maxRecordSize = 1024 I } I ' I0PDU2: Appendix I. Test cases generated semiautomatically 121 I. •' + v -+ . I INIT_SENT | + .—+ ISP: — IDSP1:AEINITconf I { protocolVersion = dummy_vall I options = dummy_vall I prefMessageSize = 0 , : I maxRecordSize =0 I result =1 I > I0SP2: IPDU:INITRESPREJECT |0PDU : — {protocolVersion = dummy_vall I options = dummy.vail . I prefMessageSize =0 I maxRecordSize =0 I result =1 I } I . •. + V—+ I CLOSED | Appendix I. Test cases generated semiautomatically I CLOSED | ISP: AEINITreq { protocolVersion = '111' options = '111111' prefMessageSize = 1024 maxRecordSize = 1024 > IPDU: — OSP 0PDU1:INITREQ { protocolVersion = ' i l l ' options = ' . l l l l l i ' prefMessageSize— 1024 maxRecordSize = 1024 . } . 0PDU2:—— • • ' +— V -+ I INIT_SENT | + '• — + . r ISP: I0SP1:AEINITconf Appendix I. Test cases generated semiautomatically { protocolVersion = '111' options = '111111' prefMessageSize = 1024 maxRecordSize = 1024 result =0 } •SP2:—-IPDU:INITRESPACCEPT •PDU : { protocolVersion = '111' options = '111111' prefMessageSize = 1024 maxRecordSize = 1024 result = 0 > +—V—+ I IDLE | + ISP: AECLOSreq OSP : { closeReason = 0 } IPDU: — •PDU1:CLOSREQ Appendix I. Test cases generated semiautomatically 124 I { closeReason = 0 I } I0PDU2:— + V + I CLOSED I + ~+ "@en ; edm:hasType "Thesis/Dissertation"@en ; vivo:dateIssued "1996-05"@en ; edm:isShownAt "10.14288/1.0051245"@en ; dcterms:language "eng"@en ; ns0:degreeDiscipline "Computer Science"@en ; edm:provider "Vancouver : University of British Columbia Library"@en ; dcterms:publisher "University of British Columbia"@en ; dcterms:rights "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."@en ; ns0:scholarLevel "Graduate"@en ; dcterms:title "Applying formal method in the implementation of the information retrieval protocol Z39.50"@en ; dcterms:type "Text"@en ; ns0:identifierURI "http://hdl.handle.net/2429/4157"@en .