UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

A new methodology for OSI conformance testing based on trace analysis Wvong, Russil 1990

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-UBC_1990_A6_7 W68.pdf [ 4MB ]
Metadata
JSON: 831-1.0051973.json
JSON-LD: 831-1.0051973-ld.json
RDF/XML (Pretty): 831-1.0051973-rdf.xml
RDF/JSON: 831-1.0051973-rdf.json
Turtle: 831-1.0051973-turtle.txt
N-Triples: 831-1.0051973-rdf-ntriples.txt
Original Record: 831-1.0051973-source.json
Full Text
831-1.0051973-fulltext.txt
Citation
831-1.0051973.ris

Full Text

A NEW METHODOLOGY FOR OSI CONFORMANCE TESTING BASED ON TRACE ANALYSIS By RUSSIL WVONG B. Sc., The Uni v e r s i t y of B r i t i s h Columbia, 1988 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE i n THE FACULTY OF GRADUATE STUDIES (DEPARTMENT OF COMPUTER SCIENCE) We accept t h i s thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA October 1990 ©Russil Wvong, 1990 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of Computer Science The University of British Columbia Vancouver, Canada Date September 28, 1990 DE-6 (2/88) Abstract This thesis discusses the problems of the conventional ISO 9646 methodology for OSI conformance testing, and proposes a new methodology based on trace analysis. In the proposed methodology, a trace analyzer is used to determine whether the observed behavior of the implementation under test is valid or invalid. This simplifies test cases dramatically, since they now need only specify the expected behavior of the IUT; unexpected behavior is checked by the trace analyzer. Test suites become correspondingly smaller. Because of this reduction in size and complexity, errors in test suites can be found and corrected far more easily. As a result, the reliability and the usefulness of the conformance testing process are greatly enhanced. In order to apply the proposed methodology, trace analyzers are needed. Existing trace analyzers are examined, and found to be unsuitable for OSI conformance testing. A family of new trace analysis algorithms is presented and proved. To verify the feasibility of the proposed methodology, and to demon-strate its benefits, it is applied to a particular protocol, the LAPB protocol specified by ISO 7776. The design and implementation of a trace analyzer ii for L A P B are described. The conventional ISO 8882-2 test suite for LAPB, when rewritten to specify only the expected behavior of the IUT, is found to be more than an order of magnitude smaller. iii Contents Abstract 1 1 Contents iv List of Figures v i Acknowledgements v i i 1 Introduction 1 1.1 The conventional methodology 2 1.1.1 Conformance testing 2 1.1.2 The ISO 9646 methodology 3 1.1.3 Problems with the test suites 6 1.1.4 Problems with the methodology 7 1.2 A methodology based on trace analysis 9 1.3 Other possible solutions 10 1.4 Overview of the thesis 13 1.5 Related work 14 2 Trace analysis methods 15 2.1 Requirements 15 2.2 Existing trace analysis methods 17 2.3 A family of new trace analysis algorithms 18 2.3.1 Model of the IUT 19 2.3.2 Algorithm 1: observer within the SUT 22 2.3.3 Algorithm 2: observer outside the SUT 23 2.3.4 Algorithm 3: lost messages 32 2.3.5 Other variations 35 iv 3 A L A P B trace analyzer 36 3.1 Functionality 36 3.2 Design and implementation 37 3.3 Operation 38 4 A L A P B test suite 46 4.1 The original test suite 46 4.2 Problems with the original test suite 48 4.3 The re-specified test suite 51 4.4 Implementing the test cases 52 4.4.1 Test case DL1.101 53 4.4.2 Test case DL4_108 • • 55 5 Conclusions 61 Bibl iography 63 A p p e n d i x 66 A Protoco l specification for the L A P B trace analyzer 66 B User's guide for the L A P B trace analyzer 71 C Design and implementation of the L A P B trace analyzer 73 D T h e re-specified L A P B test suite 75 v List of Figures 1.1 The basic conformance testing architecture 4 1.2 Different sequences of events at the tester and at the IUT . . 8 1.3 Using a trace analyzer for conformance testing 9 2.1 Decomposing a state transition 20 2.2 An observer within the SUT . . 22 2.3 An observer outside the SUT 24 2.4 An impossible sequence of events 26 2.5 The sets Sitj 28 2.6 Unobserved messages at initialization 31 3.1 Sequence of events in trace 1 39 3.2 Sequence of events in trace 2 41 3.3 Sequence of events in trace 3 43 vi Acknowledgements I would like to thank my supervisor, Dr. Gerald Neufeld, for his advice and encouragement throughout the writing of this thesis. I would also like to thank Dr. Samuel Chanson, for reading through the first draft; the faculty, staff, and grad students of the Department of Computer Science, for pro-viding a friendly and supportive environment; and the Natural Sciences and Engineering Research Council of Canada, the B. C. Advanced Systems In-stitute, and IDACOM Electronics Ltd., for their financial support. Finally, I would like to thank my family, and especially my parents, for their support and guidance. vii Chapter 1 Introduction This thesis discusses the problems of the conventional ISO 9646 methodology for OSI conformance testing, and proposes a new methodology based on trace analysis. In the proposed methodology, a trace analyzer is used to determine whether the observed behavior of the implementation under test is valid or invalid. This simplifies test cases dramatically, since they now need only specify the expected behavior of the IUT; unexpected behavior is checked by the trace analyzer. Test suites become correspondingly smaller. Because of this reduction in size and complexity, errors in test suites can be found and corrected far more easily. As a result, the reliability and the usefulness of the conformance testing process are greatly enhanced. This chapter provides the motivation for the new methodology. It de-scribes the problems of the conventional methodology, and shows how using a trace analyzer overcomes those problems. Later chapters discuss specific 1 trace analysis methods, and demonstrate the feasibility of the new method-ology by applying it to the LAPB protocol. 1.1 T h e c o n v e n t i o n a l m e t h o d o l o g y We begin by discussing why OSI conformance testing is needed. We then describe the conventional ISO 9646 conformance testing methodology and discuss the problems with it. 1.1.1 Conformance testing ISO is currently standardizing computer communication protocols within the framework of the OSI reference model. The idea is that any two sys-tems which implement the same OSI protocols will be able to communicate with one another. For the reader who is unfamiliar with communication protocols and the OSI protocol standards, Tanenbaum [18] provides a good introduction. Unfortunately, the standards documents which define the protocols are often unclear or ambiguous. They may be interpreted by different people in different ways. As a result, different implementations of the same protocol sometimes turn out to be incompatible with one another. To deal with this problem, ISO is also standardizing certain conformance testing procedures, which are carried out on a given protocol implementa-tion to ensure that it conforms to the appropriate protocol standard. The 2 idea is that these tests will be performed by some recognized test laboratory. After a protocol implementation passes the tests, the laboratory gives it a certification of approval. Customers may then buy the protocol implementa-tion from its vendor with at least some confidence that it will be compatible with other implementations. The client for whom the laboratory performs the conformance tests may be either the implementation vendor, wanting to use the certification of con-formance as a selling point; or a potential customer, wanting some assurance from a third party that the implementation works. In either case, the test laboratory has little or no knowledge of the internal workings of the system under test (SUT) which contains the implementation (IUT). The confor-mance testing process treats the SUT as a black box: only its external behavior is observed. 1.1.2 The I S O 9646 methodology The conventional conformance testing methodology is described by the five-part standard ISO 9646. In this methodology, the IUT is not simply run against another implementation, as this would not test the reaction of the IUT to invalid messages. Instead, a tester able to send both valid and invalid messages is used to execute a series of test cases, each testing a particular aspect of the protocol. For example, there is usually one test case for each possible state transition. There are four different test architectures discussed in ISO 9646, called 3 SUT tester higher layers test cases IUT lower-level protocols lower-level protocols Figure 1.1: The basic conformance testing architecture "methods": local, coordinated, distributed, and remote. The local test method is not intended for conformance testing, since it requires access to the lower service boundary of the IUT, which is internal to the SUT; such access is not available during third-party testing. In the other three test methods, the tester exchanges messages with the IUT over a normal communications service, provided by lower-level protocol implementations in both the tester and the SUT (Figure 1.1). In the remote test method, the tester interacts with the SUT only via the messages which it sends and receives. In the coordinated and distributed test methods, the tester also has a point of control and observation at the upper service boundary of the IUT. The remote test method is generally considered the most practical architecture, since it is the only one which does not require access to any internal interfaces within the SUT. ISO is planning to standardize an abstract test suite, consisting of ab-4 struct test cases, for each of the OSI protocols. The abstract test suite for each protocol specifies all the tests which an implementation must pass in or-der to receive its certification of conformance. T T C N , the Tree and Tabular Combined Notation, is used to specify abstract test suites. In this notation, each test case is specified as a tree of events (such as: tester sends mes-sage to IUT, tester receives message from IUT, timer expires). Each path from the root of the tree to one of its leaves is a possible sequence of these events. Each leaf has a verdict associated with it: PASS, if the sequence of events corresponds to the expected IUT behavior; FAIL, if the sequence of events corresponds to invalid IUT behavior; or INCONCLUSIVE, if the IUT's behavior was valid, but not what was expected. TTCN has many of the features of a programming language—variables, expressions, loops, subroutines, and so on—but being a special-purpose notation, is somewhat limited when compared to a general-purpose language like C or Pascal. The abstract test cases are implemented as executable test cases on par-ticular testers. T T C N is precise enough and explicit enough to permit direct translation from abstract test cases to executable test cases: in fact, at least v two systems which are able to perform such translation automatically have been built [20, 16]. Thus TTCN can be viewed as a high-level programming language: once a TTCN test suite has been written, it can be translated directly into executable code without human intervention. 5 1.1.3 Problems with the test suites At present, two T T C N test suites have been specified by ISO, one for the X.25 L A P B protocol and one for the X.25 packet layer protocol. These test suites are specified by Parts 2 and 3, respectively, of the document ISO 8882 [7]. They are being standardized separately. Unfortunately, both test suites have a number of major problems. They contain many, many errors, despite repeated revisions by protocol experts over a period of years. (Errors in the current version of ISO 8882-2 are described in Chapter 4.) The presence of such errors means that we can only have a limited amount of confidence in the results of conformance testing. Moreover, the test suite standards themselves are incredibly large, much larger than the original protocol standards from which they are derived. For example, the ISO protocol standard for LAPB, ISO 7776, is only 23 pages long; the current version of ISO 8882-2 is 252 pages long, an entire order of magnitude larger. Documents of this size are very difficult to read and understand; again, this lowers our confidence in the results of conformance testing. In short, the existing abstract test suites are untrustworthy. This calls into question the usefulness of conformance testing. If an IUT fails certain conformance tests, is it because of errors in the IUT, or because of errors in the test cases? In order to establish the usefulness of conformance testing, some way of producing reliable, trustworthy test suites must be found. 6 1.1.4 Problems with the methodology Why do existing test suites have the problems which we have described? The reason appears to he in the conformance testing methodology, rather than the particular protocols being tested. Each TTCN test case must specify all possible valid sequences of events, both expected and unexpected. It is surprisingly difficult to identify all unexpected but valid sequences of events, for a number of reasons. The most important reason is that the order in which events are observed by the tester may not be the same as the order in which they are observed by the IUT. It may not be immediately obvious why this is so. To see why, consider the common situation in which a test case sends a message q to the IUT, in order to verify that the IUT sends a response r. The expected sequence of events in this case is (g, r). The message q takes some amount of time to travel from the tester to the IUT. Suppose that during this time, the IUT sends a message of its own, call it p. Then the tester sees the sequence of messages (q,p)—it receives the message p after it sends q—whereas the IUT sees the sequence (p, q) (Figure 1.2). According to the protocol, the IUT is required to send r immediately upon receiving q; it is invalid for the IUT to send p after receiving q. Nev-ertheless, the test case must specify both (q,r) and (q,p) as being valid sequences of events—the former being the expected behavior, and the latter being unexpected but valid behavior—because the sequence (q,p) observed 7 Figure 1.2: Different sequences of events at the tester and at the IUT by the tester may have been caused by the sequence (p, q) at the IUT, which is valid. It should be clear from this example that identifying all possible valid-but-unexpected sequences of events is not easy. As a result, individual test cases are rather more complex than might be expected. There is also considerable redundancy among the test cases, since TTCN has somewhat limited facilities for identifying functions common to different test cases. A test suite consisting of hundreds of these test cases will therefore be very large. As described earlier, T T C N is basically a programming language, so a T T C N test suite is essentially a very large and complex program. Writing and "debugging" a TTCN test suite is not an easy task, especially since there are few support tools for T T C N . Frequent errors are inevitable. 8 tester IUT trace analyzer Figure 1.3: Using a trace analyzer for conformance testing 1 .2 A m e t h o d o l o g y b a s e d o n t r a c e a n a l y s i s This thesis proposes an alternative methodology for conformance testing. The basic idea is that instead of having each test case identify all unexpected but valid sequences of events, a trace analyzer is used to determine whether or not the observed behavior of the IUT is valid. The individual test cases need only specify the expected sequence of events; any unexpected events will be checked for validity by the trace analyzer. The trace analyzer passively observes the exchange of messages between the tester and the IUT (the trace), notifying the test operator whenever it discovers an error in the IUT's behavior (Figure 1.3). No new specification need be given for the trace analyzer: it can be implemented directly from the protocol specification. In the new methodology, test case verdicts may be assigned in a straight-forward manner. If the IUT's behavior is found to be invalid by the trace analyzer, the verdict is FAIL. If the IUT's behavior is valid, and matches what was expected by the test case, the verdict is PASS. If the IUT's be-9 havior is valid, but unexpected, the verdict is INCONCLUSIVE. The new methodology dramatically simplifies test cases, since they only specify the expected sequence of events. The size of the test suite is corre-spondingly reduced; for example, the ISO 8882-2 test suite is reduced from 252 pages to 8 pages. (The re-specified test suite is described in Chapter 4.) This reduction in size and complexity makes it far easier to detect and correct errors in test cases. An additional advantage is that the problem of determining the validity of the behavior of the IUT is.handled in one place—the trace analyzer— instead of being distributed over hundreds of test cases. This eliminates a considerable amount of redundancy, and makes the handling of this problem easy to change. In short, the proposed methodology should make test suites trustworthy, and greatly enhance the reliability and usefulness of the conformance testing process. 1.3 O t h e r p o s s i b l e s o l u t i o n s One might ask whether it is necessary to introduce trace analysis in order to make conformance testing useful. For example, why not simply continue debugging the abstract test suites until no errors remain? Wouldn't this be easier than adopting a new methodology? It may be possible to do this, but it doesn't appear very likely. As 10 discussed earlier, the abstract test suites are essentially large and complex programs, written in a somewhat unstable language (TTCN) with which we have little experience and for which there are few support tools. It is unreasonable to expect that the test suites can be debugged in the near future. Indeed, the ISO 8882-2 and ISO 8882-3 test suites have been revised periodically for a number of years, but still contain many errors. A second criticism that might be made is that errors in the abstract test suites are not important. Won't errors be discovered as the test cases are implemented? And even if they are not, can't the test laboratory personnel check the test case verdicts by hand? It is true that if the abstract test cases are being implemented manually, some of the errors in them will be detected and corrected. However, if all of ISO's protocol experts are unable to detect the errors in an abstract test suite, it seems improbable that a test suite implementor will. With regard to test laboratory personnel checking the test verdicts— it is possible to do this, provided that the people involved are experts in the protocol being tested, and are willing to go through the tedious task of wading through the several hundred pages of output generated by the test cases. However, this approach is undesirable for two reasons. First, it changes the conformance testing process from a more or less automated one—the test cases can be executed against the IUT with little or no human intervention—to one requiring considerable human expertise. Second, the test laboratory personnel would basically be serving as human substitutes 11 for a trace analyzer. Considering the repetitive and mechanical nature of trace analysis (various algorithms are discussed in Chapter 2), this seems like a waste of human effort. A third critic might ask whether the problem might not be solved simply by abandoning TTCN and the idea of automatic implementation of abstract test cases. Suppose we re-specify the test cases to identify only the expected sequence of events, so that the abstract test suites become simpler and smaller, as described earlier. Then what do we need a trace analyzer for? The answer is that this approach merely shifts the problem of specifying unexpected but valid sequences of events from the abstract test cases to the executable test cases. It is now the test suite implementor who is responsi-ble for identifying all unexpected but valid sequences of events. The same comments about the difficulty of identifying unexpected but valid sequences of events, the complexity of the resulting test cases, the size of the result-ing test suite, and the difficulty of debugging it apply just as well to the executable test cases as to the abstract test cases. Finally, in recent years some work has been done on automatic generation of test suites from formal protocol specifications. Wouldn't this solve the problem? Wouldn't test suites generated by machine would be free of errors? Perhaps at some time in the future, this may be a viable strategy. At present, though, there are some major obstacles. Present methods for test case generation, surveyed by Sidhu and Leung [17], only generate the ex-pected sequence of events; the problem of unexpected but valid events is 12 not addressed at all. Moreover, protocol standards are currently written in English; no formal specifications have been standardized yet. Even if they were, there is presently a large gap between the formal specification techniques used to specify protocols, such as Estelle and LOTOS, and the state machine specifications used to generate test suites. This problem is discussed by Miller [12]. 1 .4 O v e r v i e w o f t h e t h e s i s In this chapter, we have discussed why trace analysis should be used to do conformance testing. In Chapter 2, we discuss how it should be done: the requirements for a trace analyzer used in conformance testing are discussed, existing trace analyzers and trace analysis methods are examined and found wanting, and a family of new trace analysis algorithms is presented and proved. Chapters 3 and 4 demonstrate the feasibility of the proposed methodol-°gy» by applying it to the LAPB protocol. Chapter 3 discusses the design and implementation of a trace analyzer for the LAPB protocol; Chapter 4 discusses the effects of re-specifying the ISO 8882-2 test suite according to the new methodology. Finally, Chapter 5 presents the conclusions of the thesis. 13 1 .5 R e l a t e d w o r k The idea of automated trace analysis is not new. Trace analyzers for var-ious protocols are described by Cork [3]; Molva, Diaz, and Ayache [13]; Matthews, Muralidhar, and Sparks [11]; Probert [15]; and Lo [10]. More general approaches to trace analysis are discussed by Ural and Probert [19]; Bochmann, Dssouli, and Zhao [2]; and Bochmann and Belial [1]. However, all of these trace analyzers and trace analysis methods are unsuitable for conformance testing (as opposed to, say, diagnostic testing); the reasons are discussed in Chapter 2. With respect to methodology, Bochmann, Dssouli, and Zhao [2] also discuss the idea of separating trace analysis from individual test cases. They suggest that a trace analyzer would be useful for validating TTCN test cases, or in situations in which standard test cases cannot be applied, but stop short of suggesting, as we have, that a conformance testing methodology based on trace analysis could be used to replace the ISO 9646 methodology altogether. The conventional conformance testing methodology is described by the five-part standard ISO 9646 [8]. The three-part standard ISO 8882 [7] spec-ifies the standard TTCN test suites for the X.25 LAPB and packet layer protocols; the development of the LAPB test suite is described by Kanungo, Lamont, Probert, and Ural [9]. 14 Chapter 2 Trace analysis methods We now turn to the question of how trace analysis should be done. This chapter discusses the requirements for a trace analyzer used in conformance testing, and examines existing trace analysis methods in light of these re-quirements. Finally, three new trace analysis algorithms are presented and proved. 2 . 1 R e q u i r e m e n t s To apply the conformance testing methodology proposed in Chapter 1, a trace analyzer is needed. However, not just any trace analyzer is suitable; to be useful in conformance testing, it should satisfy the following requirements. First, the trace analyzer should require minimal human intervention. A typical test suite contains hundreds of test cases, takes hours to run, and generates hundreds of pages of traces. Clearly, the trace analysis process 15 should be as automated as possible. Requiring that a protocol expert double-check each test case verdict is not acceptable. Second, the trace analyzer should assign a FAIL verdict only if it is cer-tain that an error has occurred. This is a consequence of the first require-ment: If the trace analyzer were to flag any event that looked as though it could be caused by an IUT error, human intervention would be required to decide whether an error had in fact occurred. Third, the trace analyzer should treat the SUT as a black box. It is un-reasonable to expect the implementation vendor to expose interfaces within the SUT in order to do conformance testing. Fourth, the trace analyzer should not assume that the order in which events are observed is the same as the order in which they occur at the IUT; because of propagation delay between the observer and the IUT, the order may be different, as discussed in Chapter 1. Also, if the underlying communications service is unreliable, the trace analyzer should take this into account. The discussion above refers to a trace analyzer for a specific protocol, but more generally, any trace analysis algorithm should also satisfy these re-quirements. In addition, to be most useful, a trace analysis algorithm should make minimal assumptions about the protocol being tested. For example, a trace analysis algorithm would be of limited usefulness if it assumed that the protocol being tested is deterministic, since most protocols are not. A final consideration is whether the trace analyzer or trace analysis algo-16 rithm is able to operate on-line, as the test cases are being executed, or must analyze the recorded traces off-line. The former would be more useful, since it can detect errors as they occur. Note that any trace analysis algorithm which can run on-line can also run off-line, but not vice versa. 2 . 2 E x i s t i n g t r a c e a n a l y s i s m e t h o d s When existing trace analyzers are examined, it is found that there are only two basic methods used: heuristics and simulation. Trace analyzers which use heuristics [11, 15] check the given trace against some predefined set of rules; anything which looks like an error is marked. Thus a heuristic trace analyzer relies on a human protocol expert to check its results. As dis-cussed above, a trace analyzer which requires extensive human intervention is not suitable for conformance testing (although it may be useful for other applications). Other trace analyzers [3, 13, 1, 10] simulate a perfect implementation, and compare its behavior to the behavior of the IUT. All messages received by the IUT are sent to the simulated implementation, and the messages sent by the IUT are compared to the messages sent by the simulation. Most of the trace analyzers assume that the protocol is deterministic. [19,1] describe trace analysis algorithms which do not make this assumption, but these al-gorithms use backtracking to handle non-determinism, which prevents them from being used on-line. 17 A l l existing trace analyzers and trace analysis methods which use sim-ulation have this in common: they assume that events are observed in the same order as they occur at the IUT. As discussed in Chapter 1, this is not a valid assumption. In summary, existing trace analysis methods are unsuitable for OSI con-formance testing. New methods are needed. 2 . 3 A f a m i l y o f n e w t r a c e a n a l y s i s a l g o r i t h m s We now present and prove three new trace analysis algorithms. They can be used when testing any protocol which can be specified as an extended finite state machine; the protocol need not be deterministic. The algorithms operate by processing all observed messages in order, keeping track of the possible states of the IUT, rather than using backtracking; hence they can be run either on-line or off-line. The individual algorithms differ in their assumptions about the trace. The first algorithm, which is presented solely for purposes of illustration and is not meant to be used in practice, requires that messages actually be observed within the SUT, at the lower service boundary of the IUT. Since there is no propagation delay between the IUT and the observer in this case, the algorithm can assume that all messages are observed in the same order as they are sent and received by the IUT. With this assumption, the algorithm is fairly trivial. 18 The second algorithm places the observer outside the IUT. In this situ-ation, messages may not be observed in the same order as they are sent and received by the IUT; the algorithm must take this possibility into.account. However, the second algorithm does make the assumption that the underly-ing communications service is reliable, and will not lose messages or deliver them out of sequence. Finally, the third algorithm assumes that messages may be lost by the underlying communications service. In general, as the assumptions are made weaker, the algorithm becomes more complex, and its error-detecting power decreases: it becomes more difficult to be certain that an error has occurred. 2.3.1 Model of the IUT The IUT is modelled as an extended finite state machine. At any given moment, the IUT has an identifiable state, which determines its possible reactions to subsequent events. The IUT may change to a different state when it receives a message or when an internal event occurs, such as a timeout or a request from a higher layer, possibly sending one or more messages of its own. In some cases, there may be more than one possible state transition which the IUT can make; one of them will be chosen when the event occurs. State transitions are atomic: only one occurs at a time. A state machine may be represented as a directed graph, with the nodes of the graph representing states and the arcs representing state transitions; the 19 receive a, send b receive a send b Figure 2.1: Decomposing a state transition arcs are labelled with messages received and sent during the state transition. The trace analyzer can only observe one message at a time. Therefore, it is awkward to handle a state transition involving more than one message. However, we can assume without loss of generality that each state transition has at most one message associated with it, either sent or received: If a single state transition has more than one message associated with it, we can decompose it into several transitions, each having a single message associated with it, with corresponding intermediate states. For example, suppose that the IUT may change from state x to state y when it receives a message a, sending message b in response. We can decompose this transition into two transitions, as shown in Figure 2.1. There may be state transitions which have no messages associated with them. That is, the IUT may change state without having sent or received a 20 message. For example, such transitions might be caused by internal events (such as timeouts or user requests). We will refer to such transitions as invisible transitions. They are not visible to the trace analyzer, which only observes messages. Let Q be the set of all possible states of the IUT. Let A be the set of messages which can be sent or received by the IUT; a message which can be both sent and received by the IUT is represented by two different elements of A. If qeQ is a state of the IUT, then for each aeA representing a message which may be received by the IUT, a(q) denotes the set of possible states of the IUT after it receives a in state q\ and for each aeA representing a message which may be sent by the IUT, a(q) denotes the set of possible states of the IUT after it sends a in state q. a(q) typically contains a single state, but may be empty (because event a cannot occur in state q) or contain more than one state (because of nondeterminism). If S C Q is a set of states, a(S) will denote the set \Jqes a(<f)> that is, the set of all states which may be reached from a state in S via event a. In addition, we define c(S), the completion of a set S with respect to invisible transitions, to be the set of all states reachable from some state in 5 via zero or more invisible transitions. In particular, c(5) includes 5. Whenever it is possible for the IUT to be in some state in S, it is also possible for it to be in a state in c(5), since the IUT may change from a state in S to a state in c(5) without any messages being observed. 21 SUT higher layers point of observation IUT lower-level protocols Figure 2.2: An observer within the SUT 2.3.2 Algorithm 1: observer within the SUT We begin with a trivial algorithm, assuming that the lower service boundary of the IUT can be observed directly (Figure 2.2). Under this assumption, all messages are observed as they are sent and received by the IUT, with no in-tervening delay. There is no difference between the order in which messages are observed by the trace analyzer and the order in which they are sent and received by the IUT. Needless to say, this assumption is completely unreal-istic for conformance testing; the algorithm is presented only for illustrative purposes. Let ai, a,2,... be the sequence of messages observed. For i — 0,1,2,..., define to be the set of possible states of the IUT after it has sent or received the messages ai , a-i,.. .a;. Initially, the IUT can be in any state, so S0 = Q. Lemma 1. Si = c(a,(5j_i)). 22 Proof. By definition. • Algorithm. Let s := Q. When message ai is observed, set s := c(ai(s)). If s is now empty, the IUT fails. Otherwise, wait for the next message and repeat. Invariant. At any given time, s = 5,-, where i is the index of the last message observed. Proof of invariant. By induction. Initially, s = 5o; the invariant is trivially true. Now suppose that a;_i was the last message observed, and that s = Si-i, by inductive hypothesis. When ai is observed, s is assigned the value c(a,(s)) = c(a,-(5,-_i)) = Si, so the invariant is preserved.• It follows that if s ever becomes empty, then Si must be empty for some i: that is, after the IUT sends or receives the message a,-, there is no valid state which it could be in. Therefore, the IUT must be incorrect. Essentially, this algorithm simulates a nondeterministic state machine using a deterministic one. See Theorem 2.1 of Hopcroft and Ullman [4]. 2.3.3 Algorithm 2: observer outside the S U T The first algorithm assumes that the observer is placed inside the SUT, which is completely unrealistic. A more realistic setup is one in which the observer is placed outside the SUT (Figure 2.3). In this situation, however, the order in which messages are observed may not be the same as the order 23 SUT higher layers point of observation t IUT lower-level protocols Figure 2.3: An observer outside the SUT in which they are sent and received by the IUT, as discussed in Chapter 1. Partial ordering of messages We define a partial ordering -< on the messages observed by the trace ana-lyzer: if we know for certain that message TO must have been sent or received by the IUT before message TO', based only on the information available to the trace analyzer, then we write m -< TO'. Given any two messages TO and TO', there are three cases: TO -< TO'; or TO' -< TO; or neither, that is, it is possible that TO was sent or received before TO', but it is also possible that TO' was sent or received before TO. In the third case, we write m ^ TO' and TO' ^  m. How can we tell which case applies? Suppose that a timestamp is as-signed to each message observed. Let I(TO) be the time at which message m is observed. 24 Suppose that p and j/ are messages sent by the IUT. If t(p) < tty), then we know that the IUT must have sent p before it sent pf, because the under-lying communications service delivers messages in order (by assumption); so p -< pf. Similarly, if q and q' are messages sent to the IUT, such that t(q) < <(g'), then the IUT must receive q before it receives q', so q -< q'. Suppose that p is sent by the IUT and q is sent to the IUT. There are three possible cases. We know that if t(p) < t(q), then the IUT must have sent p before it received q, because at the time p is observed, the IUT cannot have received q yet; so p -< q. Let 6 be the maximum round-trip propagation delay between the ob-server and the IUT: that is, the maximum time it takes for a message to travel from the observer to the IUT, for the IUT to send a response, and for the response to travel from the IUT to the observer. If t(p) > t(q) + 6, then the IUT must have sent p after it received q, because if not, the round-trip propagation delay would have been greater than 8, which is impossible (Figure 2.4). So q -< p. In the final case, t(q) < t(p) < t(q) + 6. In this case, p -ft. q and q / p: that is, we cannot tell whether q was received before p was sent, or vice versa, even though q was observed before p. Lemma 2 summarizes what we know about the partial ordering -<. Lemma 2. Let p,j/ be messages sent by the IUT, and let q, q' be messages sent to the IUT. (i) If t(p) < tip1), then p X pf. If t(q) < t(q'), then q -< q'. 25 IUT P Figure 2.4: An impossible sequence of events (ii) If t(p) < t(q), then p -< q. (iii) If t(p) > t(q) + 6, then q<p. (iv) If t(q) < t(p) < t(q) + 6, then p q and q / p. Sets of possible states Let p\,p2,... be the sequence of messages sent by the IUT, in the order observed. Let qi,q2,... be the sequence of messages sent to the IUT. We have a partial ordering -< of these messages, as described above. Consider a sequence of messages (mi , . . .mn), where the mi,.. .mn are taken from the messages pi,... and qi, We say that this sequence is consistent with the partial ordering -< if the following condition holds: if m is in the sequence, and m' -< m, then m' is in the sequence, and m' precedes m in the sequence. Since pi < P2 < ••• and <Zi -< 92 < • • •> a sequence consistent with -< which consists of the messages pi,...p% and qi,...qj will be of the form observer 26 (•••Pi,---9j) o r (• ••9j, •••?.)• We define Sij to be the set of all states of the IUT which could result from a sequence consistent with -< which consists of the messages p\,... p,-and qi,.. .qj. We define Sop to be Q, the set of all possible states. Note that if p,-+i -< qj, then any sequence consistent with -< which con-tains qj must also contain p,+i. Therefore, there exist no sequences con-sistent with -< which contain only pi,...pi and qi,.. .qj, and Sij is empty. Similarly, if qj+i •< p,-, then 5,,j is empty. For example, if pi -< qi, and q\ •< P2, would be the set of states that could result from the sequence (pi,gi), that is, the set c(qi(c(pi(Q)))). The sequence (?i,Pi) would not be consistent with the partial ordering. On the other hand, if P2 ~< qi, then 5i , i would be empty, since all sequences consistent with the partial ordering would have to begin with (Pi ,P2,- . . )-It may be helpful to consider the sets Sij as forming a two-dimensional array (Figure 2.5), with the messages p\,p2,... along the left side and 9i5 92>--- along the top. If a square (i,j), i,j 0, is non-empty, then ei-ther the square immediately to its left or the square immediately above it must be non-empty. To see why, observe that if (i,j) is not empty, there must be some sequence of the form (.. .pi,.. .qj) or (.. .qj,.. .p,) which is consistent with the partial ordering -<. If we remove the last mes-sage in the sequence, we obtain a sequence of the form (.. .p,-,.. .qj-i) or (.. .qj-i,.. .pi)—indicating that the square — 1) is not empty—or of the 27 ql q2 q3 ... Figure 2.5: The sets 5,j form (.. .qj,.. .p»_i) or (.. .pi-i,. ..qj)—indicating that the square (i — l,j) is not empty. Also note that if qj -< p,-, then S,,j_i—the square immediately to the left of (i, j)—is empty, because there are no sequences of the form (.. .pi,.. .</j_i) or (.. .qj-i,.. .pi). Similarly, if pi -< qj, then Si-ij is empty. Hopefully this discussion makes things clearer, and not more obscure. The following lemma indicates exactly how the contents of the square (i, j) can be calculated from those of its neighbors. Lemma 3. (i) If i(<jj) + 6 < t(pi), then = c(pi(Si-itj)). (ii) If t(Pi) < t(qj), then Sitj = c(qj(Sit (ni) If t(qj) < t(Pi) < t(qj) + S, then 5,-j = c(p,-(5,-_i j)) U c(9 j(5,-, i_1)). Proof, (i) By Lemma 2, we know that qj -< p,-. So 5,j consists of the states corresponding to sequences of the form (.. .qj,.. .p,) consistent with -<. But each of these sequences is formed by appending p,- to a subsequence 28 of the form (... qj,.. .pi-i) or ( . . .p ,_ i , . . . qj); and the set is exactly the set of all possible states resulting from these subsequences. Therefore, c(Pi(Si-i,j)) is the set of all possible states resulting from these subsequences followed by p,-, which is the same as the set S;j . (ii) is analogous to (i), with the p's and g's exchanged. (iii) simply combines (i) and (ii).O In other words, the square (i,j) can be calculated directly from its nonempty neighbors immediately above it and to its left, as indicated by the arrows in Figure 2.5. The algorithm The following algorithm calculates the sets 5,j , one column at a time. It uses three data structures: a list of sets s,-, corresponding to sets Sij for a particular value of j; a queue of messages p,- observed travelling from the IUT within the last S time-units; and a queue of messages g, observed travelling to the IUT within the last S time-units. Each message is kept for time 6, then discarded. Algorithm. (1) When p,- is observed, put it on the from-IUT queue and set Si := c(p,(5,_i)) (Lemma 3(i)). After time 6, dequeue and discard p,-, and discard the set s,%i. (2) When qj is observed, put it on the to-IUT queue. After time 6, dequeue it and calculate new sets s(- as follows. (During this step, the sets «(• correspond to the sets 5,-j; the sets s, correspond to the sets Sij-i.) 29 For the i which is the index of the last message taken off the from-IUT queue, let s(- := c(qj(si)) (Lemma 3(ii)). For each message p,- still on the from-IUT queue, we calculate a corre-sponding set s'ji let s\ := cfa^s'^)) U c(gj(s,)) (Lemma 3(iii)). If all the sets «(• are empty, fail the IUT. Otherwise, replace the old sets st- with the new sets s{. Invariant. Let qj be the last message taken off the to-IUT queue. Then if pi is the last message taken off the from-IUT queue, or if p,- is still on the from-IUT queue, s, = 5 t ) J . Proof of invariant. (1) Suppose that the invariant holds when p,- is received. Then p;_i is either still on the from-IUT queue (if the queue is not empty) or the last message taken off the queue (if the queue is empty), so = Si-ij. Since qj has been dequeued, t(qj) + 6 < t(pi), so by Lemma 3(i), Sij = c(pi(Si-ij)), or Si = c(p,(si_i)). Thus the invariant is preserved. The invariant is clearly preserved when pi is dequeued. (2) Suppose that the invariant holds when qj is dequeued, that is, s,- = Sij-i for all i such that p,- is the last message taken off the from-IUT queue, or is still on the from-IUT queue. We show that s'i = Sij for all such i, by induction. If pt- is the last message taken off the from-IUT queue, then 5,- = 5,,j_i. Pi was dequeued before qj was, so <(p,) < t(qj). By Lemma 3(ii), 5,-j = c(9j(&,j-i)) = c(Qj(3i)), and aj = 5<j. If pi is still on the queue, then (by our inductive hypothesis) = 30 observer IUT S algorithm begins P Figure 2.6: Unobserved messages at initialization Since pi has not been dequeued yet, while qj has, t(qj) < t(pi); and since Pi was observed before qj was dequeued, t(pi) < t(qj) + S. By Lemma 3(iii), Sitj = c(p i(5 i_i, i))Uc(g i(5,-, i_i)) = c(p,(S;_1))Uc(9i(5,)). So s< = Sij, and the invariant is preserved.• Initialization of the algorithm When the trace analysis algorithm is first started, there may already be messages travelling from the IUT to the observer, and vice versa (Figure 2.6). As described above, the algorithm will not be able to handle this situation properly, since it assumes that the observer sees all messages sent to the IUT. Let c(S) denote the completion of a set S with respect to invisible events and messages received by the IUT: that is, the set of all states reachable from a state in S via invisible transitions and messages received by the IUT. If we know that the set of possible states of the IUT includes a set S, and if 31 the IUT may receive messages which are not seen by the observer, then the set of possible states of the IUT must also include the set c(S). Any of the states in c(S) can be reached from a state in S without any messages being seen by the observer. Suppose that, before the algorithm has been running for time 6, a mes-sage p sent by the IUT is observed (Figure 2.6). Then there may be messages travelling from the observer to the IUT, not seen by the observer, which are received by the IUT after it sends p. Therefore, until time S, the trace anal-ysis algorithm should take the completion of all state sets with respect to both invisible transitions and messages received by the IUT: in other words, substitute c for c in step (1) above. After time S, the algorithm operates normally (using c instead of c). 2.3.4 Algorithm 3: lost messages The second algorithm assumes that the communications service used to send messages between the observer and the IUT is reliable, delivering all messages correctly. This assumption may not always be true. For example, when testing a data-link protocol, we cannot always assume that the physical layer is reliable. We now modify the second algorithm to determine whether the observed sequence of messages could have been produced by a correct implementation, taking the possibility of messages being lost between the observer and the IUT into consideration. We will still assume, however, that messages are 32 delivered in order, if they are delivered at all. Messages sent by the IUT may be lost before they reach the observer. Let c(S) denote the completion of S with respect to invisible transitions and messages sent by the IUT: that is, the set of states reachable from a state in S via invisible transitions and transitions in which the IUT sends a message. It is analogous to c(S) and c(5). If we know that the set of possible states of the IUT includes a set S, and if the IUT may send messages which are not seen by the observer, then the set of possible states of the IUT must also include the set c(S). Let pi,P2>• • • and 91,92?•• • be the messages observed. Note that some messages sent by the IUT may be lost before reaching the observer, and hence will not appear in the sequence p i , P 2 , . . •; similarly, some messages in the sequence 91,92? • • • will be lost before they reach the IUT. We now define Sij to be the set of all states of the IUT which could result from a sequence of events, consistent with the partial ordering -<, which con-tains the messages pi ,p2, • • -Pi and possibly additional messages sent by the IUT, and does not contain any of the messages p,-+i,p,-+2, • • •iQj+iiQj+2i — (This is similar to the previous definition of Sij, except that any of the messages sent to the IUT may be lost, and some of the messages sent by the IUT may not reach the observer.) We obtain a modified Lemma 3: Lemma 3f. (i) If t(qj) + 6 < i(p,), then Sij = c(pj(5,_ij)). (ii) If t(pi) < t(qj), Sij = U Sij-L (iii) If % ) < t(Pi) < t(qj) + 6, then Sitj = cf>i(5,-_ij)) U c(gj(5,-, i_i)) U 33 Sij-i-The proof is similar to the proof of Lemma 3. In cases (ii) and (iii), we must take into consideration the possibility that qj may not be received at all. Messages sent by the IUT which do not reach the observer are taken care of by the c operator. The algorithm is modified accordingly. Algorithm. (1) When p,- is observed, set 5,- := c(p,-(sj_i)) and enqueue Pi. After time 6, dequeue and discard p,-, and discard the set s,_i. (2) When qj is observed, enqueue it immediately. After time 6, dequeue it and update the sets s; as follows. If Pi is the last message taken off the from-IUT queue, set := c(gj(s,))U Si. If Pi is still on the from-IUT queue, set sj- := cfa^s'^)) U c(gj(s,)) U s,\ If all the s'i are empty, fail the IUT. Otherwise, replace the sets s,- with the newly defined sets sJ.D Initialization of the modified algorithm is somewhat simpler. From the time the algorithm is started until time 6 has passed, messages may be both sent and received by the IUT without being observed by the trace analyzer; therefore, if the set of possible states is not empty, it must contain all possible states. (We assume that all states of the IUT are reachable.) Accordingly, we substitute c for c in step (1) of the algorithm until time S has passed, where c(5) is defined to be Q (the set of all possible states of the IUT) if S is not empty, or the empty set if 5 is empty. 34 2.3.5 Other variations We have presented three trace analysis algorithms, each of which makes certain assumptions about how messages are observed. In general, there is a tradeoff between our assumptions and the errors which we can detect: if our assumptions are weaker, it becomes more difficult to be certain that the IUT has made an error. Other variations are possible. For example, we can devise an algorithm which assumes that messages may be damaged, but are never lost. These assumptions are weaker than those of the second algorithm (messages can never be damaged), but stronger than those of the third algorithm (mes-sages can be lost). We can also imagine trace analysis algorithms whose assumptions are even weaker than those presented here: for example, an algorithm which assumes that messages can be damaged, lost, or delivered out of order. 35 Chapter 3 A L A P B trace analyzer Having discussed why trace analysis should be used in conformance testing, and given specific algorithms for doing so, we now demonstrate the feasibility of the proposed methodology by applying it to a specific protocol, the X.25 L A P B protocol as specified by ISO 7776 [5]. This chapter describes the design and implementation of a trace analyzer for the LAPB protocol; the following chapter discusses the effects of re-specifying the standard TTCN test suite according to the proposed methodology. Both the source code for the trace analyzer and the re-specified test suite are included in the Appendix. 3 . 1 F u n c t i o n a l i t y The L A P B trace analyzer implements all three trace analysis algorithms presented in the previous chapter; the user selects the appropriate one. The 36 protocol specification which is used to analyze the trace is described in detail in Appendix A. Basically, it is derived from ISO 7776 by splitting receive/send transitions into two separate transitions with an intermediate state, and modelling timeouts as spontaneous events. The data transfer specification is also somewhat simplified. The trace analyzer runs under the Unix operating system, on a Sun 3 workstation. It operates off-line, reading a recorded trace and checking it for errors. Detailed directions for its use are given in Appendix B. 3 . 2 D e s i g n a n d i m p l e m e n t a t i o n The trace analyzer is decomposed into modules according to Parnas' crite-rion of information hiding [14]. Each module hides a design decision from the rest of the system. In particular, all knowledge of the protocol being analyzed is confined to one module. This makes it possible to modify the protocol specification, or even to change the trace analyzer to handle a dif-ferent protocol, by changing a single module. Similarly, the decision to do the trace analysis off-line instead of on-line is hidden within one module. The trace analyzer consists of four modules. The Buffers module pro-vides facilities for handling octet buffers of arbitrary length, used to store observed messages. The Events module hides the decision to do trace anal-ysis off-line; the Protocol module hides the protocol specification. Finally, the main module implements the actual trace analysis algorithms. 37 The implementation of the trace analyzer was straightforward: it com-prises about 2000 lines of C code. Appendix C provides brief descriptions of the module interfaces and the modules themselves. 3 . 3 O p e r a t i o n Some examples of the trace analyzer in operation are given here. The traces being analyzed were obtained from an IDACOM PT. The PT is an X.25 protocol tester which can be used to do both monitoring and emulation. It has fairly sophisticated facilities for capturing and displaying protocol traces in various formats. In addition, user-written test scripts can be used to control the X.25 emulation (for example, to make it send an invalid message). These test scripts can be used to implement test cases. The PT actually has two CPUs, operating independently of one another, each of which can be used to do monitoring or emulation. The traces shown here were obtained by running two X.25 emulations against one another, one on each CPU. CPU1 acts as the DCE, and CPU2 acts as the DTE; the trace analyzer checks the behavior of the DTE only. The traces are recorded at the DCE; the round-trip propagation delay between the DTE and DCE is about 35 milliseconds. In the examples shown here, 50 milliseconds is used for the parameter S. In the first trace, the DCE and the DTE send DISC commands at the same time (DISC collision). The DCE then initiates link setup. Finally, the 38 D C E DTE Figure 3.1: Sequence of events in trace 1 DCE requests link reset by sending an FRMR response, and the DTE resets the link. See Figure 3.1. Analyzing it using the second algorithm of Chapter 2 (propagation delay, messages not lost), no errors are found: Trace analysis begins delta • 0.050000 DTE value of k i s 7 DTE value of NI i s 1080, DCE value of NI i s 1080 39 12.572500 rx A / U / DISC / P/F = 1 / 12.576700 tx B / U / DISC / P/F = 1 / 12.613500 tx A / U / UA / P/F - 1 / 12.634500 rx B / U / UA / P/F = 1 / 31.957100 rx A / U / SABM / P/F = 1 / 31.964100 tx A / U / UA / P/F = 1 / 33.858600 rx B / U / FRHR / P/F - 1 / 731000 33.866700 tx B / U / SABM / P/F = 1 / 33.922900 rx B / U / UA / P/F = 1 / Trace analysis ends, no error discovered The output of the trace analyzer is fairly primitive: it simply echoes each frame as it is decoded and processed. The time at which the frame is ob-served is shown in the first column; it is given in seconds. The "rx" or "tx" in the second column indicates whether the frame was received or sent by the IUT. The remaining fields correspond to fields of the frame: address, type (I, S, or U), and so forth. Note that in the trace, the DTE appears to send its DISC command after receiving the DISC command from the DCE, when in fact it sent its DISC before receiving the DCE's DISC. The second algorithm handles this situation correctly. The second trace shows data transfer: the DCE and DTE exchange I frames. See Figure 3.2. Again, analyzing the trace using the second algorithm, no errors are found: Trace analysis begins delta = 0.050000 40 DCE DTE I/NS=2 RR/NR=3 I/NS=2 RR/NR=3 I/NS=3 RR/NR=4 RR/NR=4 I/NS=3 Figure 3.2: Sequence of events in trace 2 41 DTE value of k i s 7 DTE value of NI i s 1080, DCE value of NI i s 1080 42.945000 rx A / I / N(S) - 2 / P • 0 / N(R) = 2 / 1001002049 4441434F4D20454C454354524F4E494353204C544420204252494E4753202 0544F2020594F552020544845202020502054202121212020202020202020 202020544845202050524F544F434F4C20202054455354455220205448415 420204C454144532020544845202057415920494E544F2054484520465554 55524520 42.970400 t z A / S / RR / P/F = 0 / N(R) = 3 / 42.980200 t z B / I 7 N(S) = 2 / P = 0 / N(R) = 3 / 100121 43.101900 rz B / S / RR / P/F = 0 / N(R) = 3 / 43.592000 rz A / I / N(S) > 3 / P - 0 / N(R) = 3 / 1001022049 4441434F4D20454C454354524F4E494353204C544420204252494E4753202 0544F2020594F552020544845202020502054202121212020202020202020 202020544845202050524F544F434F4C20202054455354455220205448415 420204C454144532020544845202057415920494E544F2054484520465554 55524520 43.617700 t z A / S / RR / P/F = 0 / N(R) = 4 / 43.627500 tx B / I / N(S) = 3 / P = 0 / N(R) = 4 / 100141 43.748300 rz B / S / RR / P/F - 0 / N(R) = 4 / Trace analysis ends, no error discovered In the third trace, the DCE sends a SABM to the DTE, but the DTE does not send a UA in response; instead, it immediately sends an I frame (a restart request packet). Eventually both sides time out—the DCE retransmits its SABM, the DTE sends a polling RR command—and the link is set up. See Figure 3.3. This trace could be caused by one of two things. The first possibility is that the IUT is invalid: the first time it received the SABM, it did not send a UA before entering information transfer state. The second possibility is that the IUT is valid, and sent the UA correctly, but because the underlying 42 DCE DTE Figure 3.3: Sequence of events in trace 3 43 physical service is unreliable, the UA was lost between the IUT and the observer. If we apply the second algorithm to this trace, it tells us that the IUT's behavior is invalid, because it assumes that messages are never lost. Trace analysis begins delta • 0.050000 DTE value of k i s 7 DTE value of Nl i s 1080, DCE value of Nl i s 1080 21.456000 rx A / U / SABM / P/F = 1 / 21.465800 tx B / I / N(S) • 1 /•P - 0 / N(R) = 1 / 1000FB0000 24.345600 tx B / S / RR / P/F = 1 / N(R) = 1 / Error detected i n trace at time 24.395600 If we apply the third algorithm, however, it tells us that the IUT is valid. Trace analysis begins delta = 0.050000 messages may be lost between the observer and the IUT DTE value of k i s 7 DTE value of Nl i s 1080, DCE value of Nl i s 1080 21.456000 rx A / U / SABM / P/F = 1 / 21.465800 tx B / I / N(S) = 1 / P = 0 / N(R) = 1 / 1000FB0000 24.345600 tx B / s / RR / P/F = 1 / NCR) = 1 / 24.465600 rx A / U / SABM / P/F = 1 / 24.474500 tx A / U / UA / P/F - 1 / 24.571000 tx B / I / N(S) - 0 7 P = 0 / NCR) = 0 / 1000FB0000 24.587200 rx B / S / RR / P/F = 0 / NCR) = 1 / 24.665600 rx A / 1 7 N(S) = 0 / P = 0 / NCR) = 1 / 1000FF 24.677800 tx A / S / RR / P/F = 0 / NCR) = 1 / Trace analysis ends, no error discovered 44 Which algorithm is to be considered correct? It depends on whether the underlying physical service is, in fact, reliable or not. If the service is unreliable, and was responsible for the UA being lost, then the third algorithm is correct; the second algorithm is, in effect, blaming the IUT for a fault of the underlying physical service. On the other hand, if the service is reliable, and it was the IUT that failed to send the UA, then the second algorithm is correct; the third algorithm fails to detect the error because it cannot be sure that the IUT did not send the UA. 45 Chapter 4 A L A P B test suite To illustrate the advantages of the proposed methodology, we have rewritten the standard TTCN test suite for L A P B , given in ISO 8882-2, to specify only the expected behavior of the IUT in each test case. The resulting test suite, given in Appendix D, is only 8 pages long, compared to 252 in the original. This chapter first describes the original test suite, and discusses some of the problems with it. The re-specified test suite is then discussed. 4 . 1 T h e o r i g i n a l t e s t s u i t e ISO 8882 [7] describes the standard conformance testing procedures for X.25 DTEs. It is divided into three parts, which are progressing towards stan-dardization separately: ISO 8882-1 gives an overview, ISO 8882-2 specifies the data-link layer (LAPB) test suite, and ISO 8882-3 specifies the packet layer test suite. We will be referring to the November 1989 version of ISO 46 8882-2, JTC 1/SC 6/N 5503. ISO 8882-2 tests the data-link layer of DTEs which are supposed to con-form to CCITT X.25 1980, CCITT X.25 1984, or ISO 7776. (The require-ments of these three standards are slightly different.) The test suite assumes basic sequence numbering, single link operation, DTE/DCE operation, and octet alignment. The 287 test cases making up the test suite are divided into eight groups. There is one test group for each of seven states: disconnected phase (DL1), link disconnection (DL2), link setup (DL3), information transfer phase (DL4), frame reject condition (DL5), DTE busy condition (DL6), and sent REJ condition (DL7). Each of these seven test groups is divided into three sub-groups, testing the IUT's responses to proper, improper, and inopportune frames, respectively. The eighth group, DL8, verifies that the IUT handles timeouts correctly. A l l test cases are specified in TTCN; the remote test method is used. A typical test case consists of a preamble to put the IUT in the appropriate state, a frame sent by the tester to the IUT, an expected response from the IUT, and a postamble to verify that the IUT is in the correct state. There may be more than one possible response, and therefore more than one postamble used. Some test cases, particularly in the data transfer states DL4, D L 6 , and DL7, use attached subtrees to handle unexpected but valid events (such as unexpected I or RR frames from the IUT). ISO 8882-2 gives possible preambles and postambles for each of the seven 47 states, but indicates that they are only intended as examples. Other pream-bles and postambles may be used by agreement between the test laboratory and the client. 4 . 2 P r o b l e m s w i t h t h e o r i g i n a l t e s t s u i t e The ISO 8882-2 test suite has a number of major problems. We can group them into five areas. First, the test suite standard itself is extraordinarily large. ISO 7776, the protocol standard from which the test suite is derived, is 23 pages long; ISO 8882-2 is 252 pages long, an entire order of magnitude larger. LAPB is a relatively simple protocol; one wonders how long a test suite for the transport or session layer protocols would be. It is very difficult to read and understand a document of this size, to detect errors in it, and to make changes to it. Second, the test suite makes some questionable assumptions. It is stated that "DISC and SABM commands and DM responses sent by the IUT are not considered to be acceptable unexpected frames during information trans-fer tests"; but no real justification is given for this statement. Moreover, the assumption that the IUT will not send DISC, SABM or DM frames is not limited to the information transfer tests; for example, the test cases in group DL1 make this assumption as well. This assumption does not seem justifiable: there certainly exist DTEs which send DISC, SABM, and DM 48 frames spontaneously. This behavior is permitted by the original protocol standards, but will cause the DTE to fail the standard conformance tests. It is also assumed that frames are never lost by the underlying physical layer; this assumption is not stated explicitly by ISO 8882-2. This assump-tion may be justifiable, provided the physical connection between the tester and the IUT is reliable enough. However, if the physical connection does happen to lose a frame, the IUT will probably fail the current test case, through no fault of its own. These assumptions simplify the test cases, by reducing the number of unexpected but valid events. Changing the test suite to do without these assumptions would make it even larger than it is already. A third problem is that those unexpected but valid events which are handled—namely I, RR, RNR, and REJ frames during information transfer tests—are handled in a rather clumsy and limited way. For example, the NORMAL-INFORMATION-TRANSFER test step, which is used by many test cases, checks that the N(S) field in I frames sent by the IUT is correct, but only checks that the N(R) field acknowledges either all I frames sent by the tester, or all I frames but one. If the tester hasn't sent any I frames at all, and the IUT happens to send an I frame with N(R)=7—which is invalid—the tester will accept it. The N(R) field in RR, RNR, and REJ frames is not checked at all. Fourth, the current version of ISO 8882-2 contains many, many errors, despite repeated revisions over several years by protocol experts. There are 49 numerous errors in T T C N usage. In some test cases, for example DL2_110, the test suite does not indicate what the tester should do if a boolean con-dition does not hold. In test cases which attach the test steps ACCEPT-ABLE_UNEXPECTED_DL4, _DL6, and _DL7, there is no GOTO back to the top of the list of alternatives. Several test cases in DL4 do not handle unexpected but valid I-frames or supervisory frames. As already mentioned, unexpected but valid SABM, DISC, and D M frames are not handled. If the IUT sends one of these frames, it will fail. Several cases, for example DL4_105, will only accept RR or RNR re-sponses, not commands. The test step LINK_SET_UP is attached inappropriately in a number of cases, for example DL4.201: if the timer elapses without a frame being received from the IUT, the verdict PASS will be assigned, instead of FAIL. We have found many other errors in various test cases; and undoubtedly there are many which we haven't found. And finally, as a whole the test suite seems remarkably disorganized. The numbering and ordering of the test cases is strange. For example, in test group DL1, there are test cases 201A, 201B, 202 to 205 (but not 206), 207 to 211, 215 and 216. What happened to the missing test cases? There seems to be no discernible reason for the ordering of test cases. There are several test cases which have two test case references (for ex-ample, DL2_111); this is never explained. There seems to be unneces-50 sary repetition in the test suite: in DL3, for example, the IUT reaction to RR, RNR, REJ frames with P=0, P = l , F=0, F=l—namely, discard—is tested; 12 test cases in all. Finally, in the test step library, there are some instances where two quite different test steps have the same stated test purpose; for example, NORMAL.INFORMATION-TRANSFER and AC-CEPTABLE_UNEXPECTED_DL4. This disorganization contributes to the difficulty of reading and understanding the test suite. In short, the ISO 8882-2 test suite has a number of major problems, which do not appear likely to be solved in the near future. 4 . 3 T h e r e - s p e c i f i e d t e s t s u i t e In order to demonstrate the advantages of the proposed methodology, we have re-specified the ISO 8882-2 test suite, having each test case only specify the expected IUT behavior; any unexpected behavior will be checked for validity by the trace analyzer. Most test cases in the test suite consist of one stimulus sent to the IUT and a set of possible responses from the IUT, and can be specified on one line. The test suite has been changed slightly to test ISO 7776 DTEs exclusively, not CCITT X.25 1980 or 1984 DTEs, but the differences between the three standard are minor and affect only a few test cases. The same test suite structure and same test case numbering is used; inconsistencies with the protocol standards are not corrected. No variables are used: in the data 51 transfer tests, sequence numbers are specified explicitly, assuming that the DL4, DL6, and DL7 preambles ensure the IUT's V(S) and V(R) variables are set to 0. Preambles and postambles are not given; procedures which axe mutually agreeable between the test laboratory and the client should be used. The complete test suite is included in Appendix D. It consists of only 8 pages, compared to 252 in the original. In our opinion, it has a number of major advantages over the original. Because the test cases are so much simpler, and because the test suite is so much smaller, the test suite is much easier to read and understand; inconsistencies with the protocol standard become more visible; and changes may be made quickly. The overall reliabil-ity and usefulness of the LAPB conformance testing procedure are thereby enhanced. 4 . 4 I m p l e m e n t i n g t h e t e s t c a s e s Implementing the test cases is straightforward. The typical test case im-plementation first executes a preamble to put the IUT in the appropriate state, then sends the specified stimulus to the IUT, and starts a timer (the timer's period is another matter for agreement between the test laboratory and the client). If the expected response is received before the timer expires, a postamble is executed to check that the IUT is in the correct state. If some unexpected message is received, or the timer expires, the test is aborted. In 52 the data transfer test cases, unexpected information and supervisory frames may be received from the IUT without affecting the test results; these frames are simply discarded. The trace analyzer will check their validity. Assigning a verdict is simple enough. If the trace is invalid (determined by the trace analyzer), the IUT fails. If the trace is valid, and the expected behavior is observed, the IUT passes. If the trace is valid, but the expected behavior was not observed, the verdict is inconclusive. We have implemented a couple of representative test cases, DL1_101 and DL4-108, on the IDACOM PT. Some traces from execution of the test cases are shown below. For each test case, three traces are shown, corresponding to (a) the expected IUT behavior, (b) invalid IUT behavior, and (c) unex-pected but valid IUT behavior. Note that the test cases are not expected to distinguish between (b) or (c); the trace analyzer does this. 4.4.1 Test case DL1_101 DL1.101 verifies that the IUT sends a DM with F = l in response to a DISC command with P = l received in the disconnected state. In the re-specified test suite, DL1J.01 can be specified on a single line (the message sent by the tester is shown on the left, the IUT's response on the right): DISC/P=1 DM/F=1 The specific preambles and postambles used to ensure that the IUT is in a particular state or to verify that the IUT is in a particular state are left 53 up to the test case implementor. In this case, we send a DISC and wait for a D M or UA as a preamble; we send an RR command with P=l and wait for a D M with F = l as a postamble. The following trace, in a format produced by the IDACOM PT, shows the expected IUT behavior. Frames marked "DCE" indicate frames sent by the tester (on CPU1); frames marked "DTE" indicate frames sent by the IUT (the emulation on CPU2). DL1.101: preamble 09:54.5087 DCE ADDRESS=03 FRAME=DISC P=l 09:54.5090 09:54.5161 DTE ADDRESS=03 FRAME=DM F=l 09:54.5164 DL1.101: test body 09:54.6899 DCE ADDRESS=03 FRAME=DISC P=l 09:54.6902 09:54.6969 DTE ADDRESS=03 FRAME=DM F=l 09:54.6972 DL1.101: postamble 09:54.7170 DCE ADDRESS=03 FRAME=RR P=l NR=0 09:54.7174 09:54.7242 DTE ADDRESS=03 FRAME=DM F=l 09:54.7245 DL1.101: expected behavior observed, test ends The next trace shows invalid IUT behavior. In the test body, the IUT sends a UA in response to the tester's DISC command, instead of a D M . DL1.101: preamble 11:52.8495 DCE ADDRESS=03 FRAME=DISC P=l 11:52.8498 11:53.3393 DTE ADDRESS=03 FRAME=DH F=l 11:53.3396 DL1.101: test body 54 11:53.3610 DCE ADDRESS=03 FRAME=DISC P=l 11:53.3614 11:54.0791 DTE ADDRESS=03 FRAME=UA F=l 11:54.0794 DL1.101: unexpected event, test aborted The last trace shows valid but unexpected behavior: the IUT sends a DM response with F=0, when the tester is expecting a DM response with F= l . This is valid, because the IUT could have sent the DM with F=0 (to request link setup) before receiving the tester's DISC command; but it is not what is expected by the test case. DL1.101: preamble 14:58.6835 DCE ADDRESS=03 FRAME=DISC P=l 14:58.6839 14:59.7426 DTE ADDRESS=03 FRAME=DM F=l 14:59.7429 DL1.101: test body 14:59.7644 DCE ADDRESS=03 FRAME=DISC P=l 14:59.7648 15:00.5867 DTE ADDRESS=03 FRAME=DM F=0 15:00.5870 DL1.101: unexpected event, test aborted 4.4.2 Test case DL4.108 DL4.108 verifies that the IUT handles a REJ command with P=l correctly, by sending an RR response with F = l and then retransmitting the requested I frames. I/P=0, NS=0, NR=0 -> <- I/NS=0 I/P=0, NS=1, NR=0 -> 55 <- I/NS=1 I/P=0, NS=2, NR=0 -> <- I/NS=2 REJ/P=1, NR=1 -> <- RR/F=1, NR=3 <- I/NS=1, NR=3 RR/NR=2, F=received P b i t -> <- I/NS=2, NR=3 RR/NR=3, F=received P b i t -> As this is a data transfer test case, any unexpected information or super-visory frames are simply discarded; they will be checked for validity by the trace analyzer. As a preamble, the tester sends a DISC and waits for a UA or DM, then sends a S A B M and waits for a UA. As a postamble, the tester sends an F R M R and waits for a SABM or D M . The following trace shows the expected IUT behavior: DL4.108: preamble 26:48.5894 DCE ADDRESS=03 FRAME=DISC P=l 26:48.5898 26:48.5984 DTE ADDRESS=03 FRAME=UA F=l 26:48.5897 26:48.7674 DCE ADDRESS=03 FRAME=SABM P=l 26:48.7677 26:48.7760 DTE ADDRESS=03 FRAME=UA F=l 26:48.7763 DL4.108: test body 26:48.7986 DCE ADDRESS=03 FRAME=INFO P=0 NR=0 NS=0 GF=1 D=0 Q=0 LCN=0 RESTART INDICATION PACKET CAUSE - 00 UNDEFINED DIAGNOSTIC = 00 NO ADDITIONAL INFORMATION 26:48.7996 26:48.8146 DTE ADDRESS=03 FRAME=RR F=0 NR=1 56 26:48.8149 26:48.8913 DTE ADDRESS=01 FRAHE=INFO P=0 NR=1 NS=0 GF=1 D=0 Q=0 LCN=0 RESTART CONFIRM PACKET 26:48.8920 26:48.9116 DCE ADDRESS=03 FRAME=INFO P=0 NR=0 NS=1 GF=1 D=0 q=0 LCN=0 RESTART INDICATION PACKET CAUSE • 00 UNDEFINED DIAGNOSTIC = 00 NO ADDITIONAL INFORMATION 26:48.9126 26:48.9262 DTE ADDRESS=03 FRAME=RR F=0 NR=3 26:48.9265 26:49.0028 DTE ADDRESS=01 FRAME=INF0 P=0 NR=2 NS=1 GF=1 D=0 Q=0 LCN=0 RESTART CONFIRM PACKET 26:49.0035 26:49.0231 DCE ADDRESS=03 FRAME=INFO P=0 NR=0 NS=2 GF=1 D=0 Q=0 LCN=0 RESTART INDICATION PACKET CAUSE = 00 UNDEFINED DIAGNOSTIC = 00 NO ADDITIONAL INFORMATION 26:49.0241 26:49.0377 DTE ADDRESS=03 FRAME=RR F=0 NR=3 26:49.0380 26:49.1145 DTE ADDRESS=01 FRAME=INFO P=0 NR=3 NS=2 GF=1 D=0 Q=0 LCN=0 RESTART CONFIRM PACKET 26:49.1152 26:49.1341 DCE ADDRESS=03 FRAME=REJ P=l NR=1 26:49.1345 26:49.1433 DTE ADDRESS=03 FRAME=RR F=l NR=3 26:49.1436 26:49.1530 DTE ADDRESS=01 FRAME=INFO P=0 NR=3 NS=1 GF=1 D=0 Q=0 LCN=0 RESTART CONFIRM PACKET 26:49.1537 26:49.1775 DCE ADDRESS=01 FRAME=RR F=0 NR=2 26:49.1779 26:49.1652 DTE ADDRESS=01 FRAME=INF0 P=0 NR=3 NS=2 GF=1 D=0 Q=0 LCN=0 RESTART CONFIRM PACKET 26:49.1658 26:49.2024 DCE ADDRESS=01 FRAME=RR F=0 NR=3 26:49.2028 DL4_108: postamble 57 26:49.2161 DCE ADDRESS=01 FRAME=FRMR F=0 CONTROL = 64 COMMAND VR=3 VS=3 W=0 X=0 Y=0 Z=0 BITS 17-24 INVALID COMBINATION 26:49.2169 26:49.2284 DTE ADDRESS=01 FRAME=SABM P=l 26:49.2287 26:49.2371 DCE ADDRESS=01 FRAME=UA F=l 26:49.2375 DL4.108: expected behavior observed, test ends The following trace shows invalid IUT behavior. When the tester sends the polling REJ command to the IUT, it retransmits the requested I frames immediately, instead of sending an RR response. DL4.108: preamble 40:07.6454 DCE ADDRESS=03 FRAME=DISC P=l 40:07.6458 40:08.0611 DTE ADDRESS=03 FRAME=UA F=l 40:08.0614 40:08.0772 DCE ADDRESS=03 FRAME=SABM P=l 40:08.0776 40:09.0393 DTE ADDRESS=03 FRAME=UA F=l 40:09.0395 DL4.108: test body 40:09.0618 DCE ADDRESS=03 FRAME=INFO P=0 NR=0 NS=0 GF=1 D=0 q=0 LCN=0 RESTART INDICATION PACKET CAUSE = 00 UNDEFINED DIAGNOSTIC = 00 NO ADDITIONAL INFORMATION 40:09.0628 40:11.7576 DTE ADDRESS=03 FRAME=RR F=0 NR=1 40:11.7579 40:11.7862 DTE ADDRESS=01 FRAME=INFO P=0 NR=1 NS=0 GF=1 D=0 q=0 LCN=0 RESTART CONFIRM PACKET 40:11.7869 40:11.8065 DCE ADDRESS=03 FRAME=INFO P=0 NR=0 NS=1 GF=1 D=0 q=0 LCN=0 RESTART INDICATION PACKET CAUSE = 00 UNDEFINED 58 40:11.8075 40:13.4801 DTE 40:13.4803 40:13.5087 DTE 40:13.5094 40:13.5291 DCE 40:13.5301 40:14.8955 DTE 40:14.8958 40:14.9241 DTE 40:14.9248 40:14.9438 DCE 40:14.9442 40:16.4951 DTE 40:16.4957 40:16.5263 DTE 40:16.5270 DL4.108: unexpected event, test aborted The final trace shows an unexpected but valid sequence of events: when the tester sends an I frame to the IUT, the IUT acknowledges it, but does not send an I frame of its own. This is perfectly valid, but does not allow the test case to be performed. Eventually the tester times out and aborts the test. DL4.108: preamble 41:21.8252 DCE ADDRESS=03 FRAME=DISC P=l 41:21.8255 DIAGNOSTIC - 00 NO ADDITIONAL INFORMATION ADDRESS=03 FRAME=RR F=0 NR=3 ADDRESS=01 FRAME=INFO P=0 NR=2 NS=1 GF»1 D=0 q=0 LCN-0 RESTART CONFIRM PACKET ADDRESS=03 FRAME=INFO P=0 NR=0 NS=2 GF=1 D=0 q=0 LCN=0 RESTART INDICATION PACKET CAUSE « 00 UNDEFINED DIAGNOSTIC * 00 NO ADDITIONAL INFORMATION ADDRESS=03 FRAME=RR F=0 NR=3 ADDRESS=01 FRAME=INFO P=0 NR=3 NS=2 GF=1 D=0 Q=0 LCN=0 RESTART CONFIRM PACKET ADDRESS=03 FRAME=REJ P=l NR=1 ADDRESS=01 FRAME=INFO P=0 NR=3 NS=1 GF=1 D=0 q=0 LCN=0 RESTART CONFIRM PACKET ADDRESS»01 FRAME=INFO P=0 NR=3 NS=2 GF=1 D=0 q=0 LCN=0 RESTART CONFIRM PACKET 59 DTE ADDRESS=03 FRAME=UA DCE ADDRESS=03 FRAME=SABM P=l 41:23.8857 41:23.8859 41:23.9017 41:23.9021 41:24.6081 41:24.6084 DL4.108: test body 41:24.6306 DCE ADDRESS=03 F=l DTE ADDRESS=03 FRAME=UA F=l FRAME=INF0 P=0 NR=0 NS=0 GF=1 D=0 q=0 LCN=0 RESTART INDICATION PACKET CAUSE = 00 UNDEFINED DIAGNOSTIC • 00 NO ADDITIONAL INFORMATION 41:24.6316 41:27.6161 DTE ADDRESS=03 FRAME=RR F=0 NR=1 41:27.6164 DL4.108: unexpected event, test aborted 60 Chapter 5 Conclusions We have shown that the problems associated with existing TTCN test suites—excessive size and complexity, leading to large numbers of errors— may be attributed to the conventional conformance testing methodology, in which each test case must specify all possible valid sequences of events. We propose a new methodology, in which an independent trace analyzer is used to decide whether or not the observed behavior of the IUT is valid. In this methodology, test cases only need to specify the expected sequence of events, since unexpected events will be checked by the trace analyzer. This simplifies the test cases dramatically. The resulting test suites are vastly smaller and simpler than the existing ones, making it much easier to detect and correct errors in them, and allowing us to place more confidence in the results which they produce. We believe that adopting the proposed method-ology will greatly enhance the reliability and usefulness of OSI conformance 61 testing. In order to use the new methodology, trace analyzers are needed. Exist-ing trace analysis methods turn out to be unsuitable for conformance testing. Three new trace analysis algorithms have been presented and proved. Finally, the methodology has been applied successfully to the LAPB protocol. A LAPB trace analyzer has been designed and implemented, and the standard TTCN test suite for LAPB has been re-specified, reducing its size from 252 pages to 10 pages. A number of areas have not been addressed in this thesis, but appear to be worthwhile to investigate in the future. 1. Other trace analysis algorithms. The algorithms presented here as-sume that the protocol being tested can be modelled by an extended finite state machine, and do not handle timeouts very cleanly. If the proposed methodology does become widely used, more sophisticated trace analysis algorithms—perhaps employing multiple passes—would be useful. 2. Testing of higher layers, and of more complex protocols. LAPB is a data-link protocol, and is rather simple compared to the ISO transport or session protocols. 3. Performance. In this thesis, performance was not considered an im-portant factor. The LAPB trace analyzer discussed in Chapter 3 was not intended for on-line use, and in fact is probably too slow. 62 Bibliography [1] G. v. Bochmann and 0 . Belial, "Test result analysis in respect to formal specifications," in Proceedings of the Second International Workshop on Protocol Test Systems, pp. 272-294, October 1989. [2] G. v. Bochmann, R. Dssouli, and J. R. Zhao, "Trace analysis for con-formance and arbitration testing," IEEE Transactions on Software En-gineering, vol. 15, no. 11, pp. 1347-1356, November 1989. [3] R. M. S. Cork, "The testing of protocols in SNA products—an overview," in Proceedings of the IFIP WG 6.1 Third International Workshop on Protocol Specification, Testing, and Verification, pp. 455-463, June 1983. [4] J. E. Hopcroft and J. D. Ullman, Introduction to Automata The-ory, Languages, and Computation, Reading, Massachusetts: Addison-Wesley, 1979. [5] ISO 7776, Information processing systems — Open Systems Intercon-nection — Description of the X.25 LAPB-compatible DTE data link procedures. [6] ISO 8208, Information processing systems — Open Systems Intercon-nection — X.25 packet level protocol for data terminal equipment. [7] ISO 8882, Information processing systems — Open Systems Intercon-nection — X.25 DTE conformance testing. [8] ISO 9646, Information processing systems — Open Systems Intercon-nection — OSI conformance testing methodology and framework. [9] B. Kanungo, L. Lamont, R. L. Probert, and H. Ural, "A useful FSM representation for test suite design and development," in Proceedings 63 of the IFIP WG 6.1 Sixth International Workshop on Protocol Specifi-cation, Testing, and Verification, pp. 163-176, June 1986. [10] J. K.-H. Lo, "Open Systems Interconnection Passive Monitor," M. Sc. thesis, Department of Computer Science, University of British Columbia, 1990. [11] R. S. Matthews, K. H. Muralidhar, and S. Sparks, "MAP 2.1 con-formance testing tools," IEEE Transactions on Software Engineering, vol. 14, no. 3, pp. 363-374, March 1988. [12] R. E. Miller, "Protocol specification: The first ten years, the next ten years; some personal observations," in Proceedings of the IFIP WG 6.1 Tenth International Symposium on Protocol Specification, Testing, and Verification, June 1990. [13] R. Molva, M. Diaz, and J. M. Ayache, "Observer: A run-time check-ing tool for local area networks," in Proceedings of the IFIP WG 6.1 Fifth International Workshop on Protocol Specification, Testing, and Verification, pp. 495-506, June 1985. [14] D. L. Parnas, "On the criteria to be used in decomposing systems into modules," Communications of the A CM, vol. 15, no. 12, pp. 1053-1058, December 1972. [15] R. L. Probert, "Towards a knowledge-based model for conformance test results analysis," in Proceedings of the First International Workshop on Protocol Test Systems, October 1988. [16] R. L. Probert, H. Ural, and M. W. A. Hornbeek, "An integrated soft-ware environment for developing and validating standardized confor-mance tests," in Proceedings of the IFIP WG 6.1 Eighth International Symposium on Protocol Specification, Testing, and Verification, pp. 87-98, June 1988. [17] D. P. Sidhu and T.-K. Leung, "Formal methods for protocol testing: A detailed study," IEEE Transactions on Software Engineering, vol. 15, no. 4, pp. 413-426, April 1989. [18] A. S. Tanenbaum, Computer Networks, 2nd ed., Englewood Cliffs, New Jersey: Prentice-Hall, 1988. 64 [19] H. Ural and R. L. Probert, "Step-wise validation of communication protocols and services," Computer Networks and ISDN Systems, vol. 11, no. 3, pp. 183-202, March 1986. [20] A . Wiles, "ITEX, system for editing tests in TTCN," Technical Report, Swedish Institute of Computer Sciences, 1987. 65 Page 66 Appendix A: Pr o t o c o l s p e c i f i c a t i o n for the LAPB trace analyzer The protocol s p e c i f i c a t i o n used by the trace analyzer i s an extended f i n i t e state machine based on ISO 7776 ( f i r s t e d i t i o n , 1986). Timeouts are modelled as i n v i s i b l e t r a n s i t i o n s (the IUT changes state without any frame being observed). Both basic and extended sequence numbering are supported. Single l i n k and m u l t i l i n k operation are supported also. It i s assumed that the IUT i s octet-aligned. A . l . State information ISO 7776 defines f i v e s t a t e s . information t r a n s f e r disconnected sending SABM ( l i n k setup) sending DISC (l i n k disconnection) sending FRMR (frame r e j e c t condition) We add eight intermediate states. When the IUT enters one of these states, i t w i l l immediately send a frame and leave the state. The IUT'does not receive frames while i n these states. received SABM (send UA or DM) received DISC (3end UA or DM) SABM c o l l i s i o n (send UA) DISC c o l l i s i o n (send UA) SABM/DISC c o l l i s i o n (send DM) i n i t i a t e reset (send SABM/P=1 or DM/F=0) request reset (send FRMR) i n d i c a t e disconnected (send DM/F=1) Within the re c e i v e d SABM, received DISC, SABM c o l l i s i o n , DISC c o l l i s i o n , and SABM/DISC c o l l i s i o n states, we keep track of the P b i t (0 or 1) i n the SABM or DISC received by the IUT. Within the re c e i v e d DISC state, we also keep track of whether the IUT wa3 i n information t r a n s f e r state or disconnected state when i t received the DISC. Within the sending SABM and sending DISC states, we keep track of whether or not the IUT w i l l enter the indicated state (information transfer or disconnected, r e s p e c t i v e l y ) a f t e r a T l timeout without receiving a UA response. (This may happen a f t e r a SABM or DISC c o l l i s i o n , respectively.) Within the information t r a n s f e r state, we keep track of the following information: whether or not the IUT w i l l accept a UA response without i n i t i a t i n g l i n k reset (which may be the case a f t e r a SABM c o l l i s i o n ) ; the values of i t s V(S), V(T), and V(R) variables (V(T) i s the sequence number of the f i r s t unacknowledged I frame sent by the IUT) ; whether or not the IUT i s i n DTE busy condition (sent RNR), DCE busy condition (received RNR), sent REJ condition, DTE p o l l i n g condition (sent I or S frame with P=l), DCE p o l l i n g condition (received I or S frame with P=l) . A.2. Sending frames Appendix A Page 67 It i s assumed that a l l frames sent by the IUT have correct frame check sequences, are properly d e l i m i t e d by f l a g s , and are octet aligned. (These assumptions are not checked by the trace analyzer.) The IUT may not send any of the following. a frame shorter than two octets; a frame with an address other than A or B (single l i n k operation), or C or D (mu l t i l i n k operation); a frame with an undefined c o n t r o l f i e l d ; a SABM or DISC command with P=0; a response with F=0 to a command with P=l, or a response with F=l when no command with P=l has been received; an I or S frame shorter than 3 octets, or an S frame i n which b i t s 5-8 of the second octet are not zero, when extended sequence numbering i s being used; a SABM, DISC, UA, DM, or S frame with an information f i e l d ; an FRMR response which does not have a 3-octet information f i e l d i n which b i t s 9 and 21-24 are zero, when basic sequence numbering i s being used; an FRMR response which does not have a 5-octet information f i e l d i n which b i t s 17 and 37-40 are zero, when extended sequence numbering i s being used; an I frame longer than the DCE value of NI. The IUT may send a SABM command i n the following states. A f t e r sending the SABM, the IUT enters sending SABM state. information t r a n s f e r disconnected sending SABM sending FRMR i n i t i a t e reset The IUT may send a DISC command i n the following states. A f t e r sending the DISC, the IUT enters sending DISC state. information t r a n s f e r disconnected sending DISC sending FRMR The IUT may send a UA response i n the following states. The state which the IUT then enters i s 3hown i n parentheses. received SABM (information transfer) received DISC [in information transfer] (disconnected) SABM c o l l i s i o n (sending SABM, or information transfer [accept UA within TI], or sending SABM [enter information transfer after TI]) DISC c o l l i s i o n (sending DISC, or disconnected, or sending DISC [enter disconnected a f t e r TI]). The IUT may send a DM response i n the following states. Afterwards, i t enters the disconnected state. Appendix A Page 68 i n f o r m a t i o n t r a n s f e r d i s c o n n e c t e d s e n d i n g SABM s e n d i n g DISC s e n d i n g FRMR i n i t i a t e r e s e t i n d i c a t e d i s c o n n e c t e d r e c e i v e d SABM r e c e i v e d DISC [ i n d i s c o n n e c t e d s t a t e ] SABM/DISC c o l l i s i o n The IUT may s e n d an FRMR r e s p o n s e i n t h e f o l l o w i n g s t a t e s . A f t e r w a r d s , i t e n t e r s s e n d i n g FRMR s t a t e . i n f o r m a t i o n t r a n s f e r s e n d i n g FRMR r e q u e s t r e s e t The IUT may s e n d an S frame o n l y i n t h e i n f o r m a t i o n t r a n s f e r s t a t e . The N(R) f i e l d o f t h e S frame must be the same as t h e v a l u e o f t h e IUT's v a r i a b l e V ( R ) . The frame s h o u l d be a re s p o n s e w i t h F=l i f f the DCE p o l l i n g c o n d i t i o n i s t r u e . A f t e r s e n d i n g a response wit h F=l, t h e IUT c a n c e l s t h e DCE p o l l i n g c o n d i t i o n . I f t h e frame i s an RNR, t h e IUT s e t s the DTE busy c o n d i t i o n . I f t h e frame i s a REJ, t h e IUT s e t s the sent REJ c o n d i t i o n . I f t h e frame i s a command w i t h P=l, the IUT s e t s the DTE p o l l i n g c o n d i t i o n . The IUT may send an I frame o n l y i n t h e i n f o r m a t i o n t r a n s f e r s t a t e . The N(S) and N(R) f i e l d s o f t h e I frame must be the same as t h e v a l u e s o f t h e IUT's v a r i a b l e s v(S) and v(R) . V(S) must not be t h e same as V(T) + k. The DCE busy and DCE p o l l i n g c o n d i t i o n s must be f a l s e . I f t h e I frame has P=l s e t , t h e IUT s e t s the DTE p o l l i n g c o n d i t i o n . A f t e r s e n d i n g t h e I frame, t h e IUT increments V(S) . The f o l l o w i n g s t a t e t a b l e summarizes t h e p r e c e d i n g r u l e s . I t i n d i c a t e s what frames may be sen t by t h e IUT i n each s t a t e . SABM DISC UA DM FRMR i n f o r m a t i o n t r a n s f e r X X X X d i s c o n n e c t e d X X X s e n d i n g SABM X X s e n d i n g DISC X X s e n d i n g FRMR X X X X r e c e i v e d SABM X X r e c e i v e d DISC X X SABM c o l l i s i o n X DISC c o l l i s i o n X SABM/DISC c o l l i s i o n X i n i t i a t e r e s e t X X r e q u e s t r e s e t X Appendix A Page 69 in d i c a t e disconnected x A. 3. Receiving frames It i s assumed that a l l frames received by the IUT are octet aligned. The IUT di s c a r d s any frame which has an i n v a l i d frame check sequence, which i s not properly delimited by f l a g s , or which has an address other than A or B (single l i n k operation), or C or D (multilink operation). When the IUT receives a v a l i d SABM command, i t changes state as follows. information transfer, disconnected, sending FRMR -> received SABM sending SABM -> SABM c o l l i s i o n sending DISC -> SABM/DISC c o l l i s i o n When the IUT receives a v a l i d DISC command, i t changes state as follows. information transfer, disconnected, sending FRMR -> received DISC sending DISC -> DISC c o l l i s i o n sending SABM -> SABM/DISC c o l l i s i o n UA response with F=0: disconnected, sending FRMR, sending SABM, sending DISC: disca r d information tran s f e r -> i n i t i a t e reset UA response with F=l: disconnected, sending FRMR: dis c a r d sending SABM -> information t r a n s f e r sending DISC -> disconnected information t r a n s f e r : accept or -> i n i t i a t e reset DM response with F=0: disconnected, sending SABM, sending DISC: discard information transfer, sending FRMR -> i n i t i a t e reset DM response with F=l: disconnected: discard sending SABM, sending DISC -> disconnected information transfer, sending FRMR -> i n i t i a t e reset FRMR response (information f i e l d may be encoded i n c o r r e c t l y ) : disconnected, sending SABM, sending DISC: discard information transfer, sending FRMR -> i n i t i a t e reset S frame: I f the current IUT state i s not information transfer, the IUT handles the frame as described i n "other frames" below. I f the N(R) f i e l d i s i n v a l i d (not between V(T) and V(S)), the IUT enters request reset state. I f the frame i s a response with F=l and the DTE p o l l i n g c o n d i t i o n i s not set, the IUT enters i n i t i a t e reset state. Otherwise, the IUT sets V(T) to N(R). If the frame i s a response with F»l, i t cancels the DTE p o l l i n g condition. I f the frame i s a command with P=l, i t sets the DCE p o l l i n g Appendix A Page 70 c o n d i t i o n . I f t h e frame i s an RNR, i t s e t s t h e DCE busy c o n d i t i o n . I frame: I f t h e c u r r e n t IUT s t a t e i s not i n f o r m a t i o n t r a n s f e r , t h e IUT h a n d l e s t h e frame as d e s c r i b e d i n " o t h e r frames" below I f t h e N(R) f i e l d i s i n v a l i d (not between V(T) and V ( S ) ) , t h e IUT e n t e r s r e q u e s t r e s e t s t a t e . O t h e r w i s e , t h e IUT s e t s V(T) t o N(R). I f t h e frame i s a command w i t h P=l, s e t t h e DCE p o l l i n g c o n d i t i o n . I f the N(S) f i e l d i s t h e same as the v a l u e o f t h e IUT's v a r i a b l e V ( R ) , t h e IUT may o r may not increme n t V ( R ) . Other frames: s e n d i n g SABM, s e n d i n g DISC: d i s c a r d i n f o r m a t i o n t r a n s f e r -> r e q u e s t r e s e t i f command w i t h P=l d i s c o n n e c t e d -> i n d i c a t e d i s c o n n e c t e d (send DM/F=1) s e n d i n g FRMR -> req u e s t r e s e t (send FRMR/F=1) e l s e d i s c o n n e c t e d , s e n d i n g FRMR: d i s c a r d The f o l l o w i n g s t a t e t a b l e summarizes t h e r e c e i v e s t a t e t r a n s i t i o n s . I t i n d i c a t e s t h e s t a t e which t h e IUT w i l l e n t e r a f t e r i t r e c e i v e s a . v a l i d frame i n each s t a t e . The s t a t e t r a n s i t i o n s f o r S and I frames and f o r i n v a l i d frames a r e not shown. SABM DISC UA/F=1 UA/F=0 DM/F=1 DM/F=0 FRMR i n f o r m a t i o n t r a n s f e r r SABM d i s c o n n e c t e d r SABM se n d i n g SABM S/S sen d i n g DISC S/D sen d i n g FRMR r SABM r DISC r e s e t * r DISC S/D ABM D/D ADM r DISC r e s e t ADM ADM r e s e t r e s e t r e s e t r e s e t r e s e t r SABM - r e c e i v e d SABM r DISC - r e c e i v e d DISC S/S - SABM c o l l i s i o n D/D = DISC c o l l i s i o n S/D = SABM/DISC c o l l i s i o n r e s e t •• i n i t i a t e r e s e t ABM - i n f o r m a t i o n t r a n s f e r ADM - d i s c o n n e c t e d * - may a l s o a c c e p t w i t h o u t i n i t i a t i n g r e s e t A.4. I n v i s i b l e t r a n s i t i o n s There a r e a few i n v i s i b l e t r a n s i t i o n s w i t h t h e IUT may execute. These are t r a n s i t i o n s which o c c u r w i t h o u t any message b e i n g sent o r r e c e i v e d by t h e IUT. The IUT may change from the s e n d i n g SABM o r se n d i n g DISC s t a t e t o t h e i n f o r m a t i o n t r a n s f e r o r d i s c o n n e c t e d s t a t e , r e s p e c t i v e l y . T h i s may happen i f t h e IUT has r e - e n t e r e d t h e s e n d i n g SABM o r sending DISC s t a t e a f t e r a SABM o r DISC c o l l i s i o n . W i t h i n t h e i n f o r m a t i o n t r a n s f e r s t a t e , t h e IUT may change from " a c c e p t UA" t o "do not acc e p t UA". The IUT may r e s e t i t s v a r i a b l e V(S) t o V(T) i n o r d e r t o r e t r a n s m i t I f r a m e s . Page 71 Appendix B: U s e r ' s g u i d e f o r t h e LAPB t r a c e a n a l y z e r The LAPB t r a c e a n a l y z e r runs on t h e Sun w o r k s t a t i o n , under t h e UNIX o p e r a t i n g system. a n a l y z e [ o p t i o n s ] B . l . O p t i o n s - v e r b o s e Causes t h e t r a c e a n a l y z e r t o p r i n t t h e s e t s o f p o s s i b l e s t a t e s o f t h e IUT t o s t a n d a r d output a3 i t c a l c u l a t e s them. I f t h i 3 o p t i o n i s n o t used, o n l y t h e messages o b s e r v e d are d i s p l a y e d . - d e l t a d e l t a S p e c i f i e s an upper bound on t h e r o u n d - t r i p p r o p a g a t i o n d e l a y between t h e o b s e r v e r and t h e IUT. Gi v e n a 3 a f l o a t i n g - p o i n t number, i n d i c a t i n g s e c o n d s . I f t h i s o p t i o n i s not used, the t r a c e a n a l y z e r assumes t h a t t h e r e i s no p r o p a g a t i o n d e l a y between t h e o b s e r v e r and t h e IUT. - l o s t I n d i c a t e s t h a t messages may be l o s t between t h e o b s e r v e r and th e IUT. I f n o t used, t h e t r a c e a n a l y z e r assumes t h a t messages a r e n e v e r l o s t ( t h a t i s , t h e u n d e r l y i n g s e r v i c e i s c o m p l e t e l y r e l i a b l e ) . -extended S p e c i f i e s e x t e n d e d sequence numbering i 3 used. I f not used, t h e t r a c e a n a l y z e r assumes b a s i c sequence numbering. - m u l t i l i n k S p e c i f i e s m u l t i l i n k o p e r a t i o n . I f not used, t h e t r a c e a n a l y z e r assumes s i n g l e l i n k o p e r a t i o n . -k d t e - k S p e c i f i e s t h e DTE v a l u e o f k (the maximum s i z e o f i t s s l i d i n g window). D e f a u l t i s 7. - n l d t e - n l d c e - n l S p e c i f i e s t h e DTE and DCE v a l u e s o f N l (the maximum l e n g t h o f an I f r a m e ) , i n b i t s . D e f a u l t i s 1080 f o r b o t h . B . 2 . The t r a c e The t r a c e a n a l y z e r r e a d s t h e o b s e r v e d t r a c e from i t s s t a n d a r d i n p u t . The t r a c e must be g i v e n i n t h e f o l l o w i n g format: <timestamp> <timestamp> < n r x " o r "tx"> <message observed> <timestamp> <"rx" o r "tx"> <message observed> <timestamp> <"rx" o r "tx"> <message observed> F o r example: 10.002931 10.030053 r x 033F 11.192530 t x 0373 The timestamps a r e g i v e n i n seconds. Frames a r e g i v e n as s t r i n g s o f o c t e t s , i n h e x a d e c i m a l n o t a t i o n . F l a g s and frame check sequences are not i n c l u d e d i n t h e t r a c e . B . 3 . O p e r a t i o n o f t h e t r a c e a n a l y z e r Appendix B Page 72 The t r a c e a n a l y z e r e x e c u t e s one o f t h e t h r e e t r a c e a n a l y s i s a l g o r i t h m s on t h e g i v e n i n p u t t r a c e , u n t i l i t e i t h e r f i n d s an e r r o r o r reaches t h e end o f t h e t r a c e . The a l g o r i t h m u s e d depends on whether o r not t h e - d e l t a and - l o s t o p t i o n s a r e used. I f n e i t h e r o p t i o n i s g i v e n , t h e f i r s t a l g o r i t h m (no p r o p a g a t i o n d e l a y and no messages l o s t ) i s used. I f t h e - d e l t a o p t i o n i s g i v e n , but not the - l o s t o p t i o n , t h e s e c o n d a l g o r i t h m ( p r o p a g a t i o n d e l a y , but no messages l o s t ) i s used. I f b o t h o p t i o n s a r e g i v e n , t h e t h i r d a l g o r i t h m i s used. Page 73 Appendix C: D e s i g n and i m p l e m e n t a t i o n o f t h e LAPB t r a c e a n a l y z e r The t r a c e a n a l y z e r i s composed o f f o u r modules. The B u f f e r s module implements o c t e t b u f f e r s of a r b i t r a r y l e n g t h , u s ed s t o r e messages. The E v e n t s module h i d e s t h e d e c i s i o n t o do t r a c e a n a l y s i s o f f - l i n e i n s t e a d o f o n - l i n e . I f t h i s d e c i s i o n were l a t e r r e v e r s e , o n l y t h e E v e n t s module would need t o be changed. The P r o t o c o l module h i d e s t h e p r o t o c o l s p e c i f i c a t i o n . A g a i n , i f t h e p r o t o c o l s p e c i f i c a t i o n changes, o n l y t h e P r o t o c o l module need be changed. The main module implements t h e t r a c e a n a l y s i s a l g o r i t h m s . The t r a c e a n a l y z e r i s implemented i n C. C . l . The B u f f e r s module The e x t e r n a l i n t e r f a c e of t h e B u f f e r s module can be found i n t h e f i l e b u f f e r s . h . c r e a t e _ b u f f e r c r e a t e an empty b u f f e r d e s t r o y _ b u f f e r d e s t r o y a b u f f e r a d d _ o c t e t append an o c t e t t o a b u f f e r b u f f e r _ l e n g t h r e t u r n t h e l e n g t h o f a b u f f e r (0 i f p o i n t e r i s NULL) t o _ f i r s t _ o c t e t p r e p a r e t o r e a d from b e g i n n i n g of b u f f e r g e t _ n e x t _ o c t e t r e t u r n o c t e t from b u f f e r and p r e pare t o r e a d next o c t e t The B u f f e r s module i s implemented i n the f i l e b u f f e r s . c . A b u f f e r i s implemented as a l i n k e d l i s t , e a c h node c o n t a i n i n g a f i x e d number o f o c t e t s . P o i n t e r s t o t h e end o f t h e l i s t and t h e next o c t e t t o be r e a d a r e m a i n t a i n e d , so t h a t o c t e t s can be added o r r e a d f a i r l y e f f i c i e n t l y . C . 2 . The E v e n t s module The e x t e r n a l i n t e r f a c e of t h e E v e n t s module i s g i v e n i n e v e n t s . h . s t a r t _ t i m e r s t a r t a t i m e r s t o p _ t i m e r s t o p a t i m e r n o _ e v e n t s any e v e n t s l e f t ? g e t _ n e x t _ e v e n t r e t u r n t y p e , timestamp, t i m e r i d o r message i n i t _ e v e n t s i n i t i a l i z e t h e module The i m p l e m e n t a t i o n o f the E v e n t s module, i n e v e n t s . c , i s s i m p l e enough. A n a l y s i s i s done o f f - l i n e ; t i m e i s s i m u l a t e d u s i n g an e v e n t queue. When t h e module i s i n i t i a l i z e d , i t reads the e n t i r e t r a c e and p u t s a l l th e messages i n t h e queue. C . 3 . The P r o t o c o l module The e x t e r n a l i n t e r f a c e of t h e P r o t o c o l module i s g i v e n i n p r o t o c o l . h . decode_message destroy_message p r int_me s s age create_set destroy_set assign_set assign universe set_unTon empty_set decode message d e s t r o y decoded message p r i n t decoded message c r e a t e empty s e t of s t a t e s d e s t r o y s e t copy c o n t e n t s of s t a t e s e t a s s i g n s e t of a l l s t a t e s t o s t a t e s e t f o r m u n i o n o f two s e t s i s s e t empty? Appendix C Page 74 p r i n t _ s t a t e s e t m e s s age_sent m e s s a g e _ r e c e i v e d c o m p l e t e c o m p l e t e _ s e n t c o m p l e t e _ r e c e i v e d p r i n t s e t o f s t a t e s c a l c u l a t e s e t o f s t a t e s a f t e r message sent c a l c u l a t e s e t o f s t a t e s a f t e r message r e c e i v e d c a l c u l a t e c o m p l e t i o n wrt i n v i s i b l e e vents (c) c a l c u l a t e c o m p l e t i o n wrt msgs sent (c-hat) c a l c u l a t e c o m p l e t i o n wrt msgs r e c e i v e d ( c - t i l d e ) The c u r r e n t i m p l e m e n t a t i o n , i n p r o t o c o l . c , i 3 of the LAPB p r o t o c o l s p e c i f i c a t i o n d e s c r i b e d above. Decoding i s s t r a i g h t f o r w a r d : decode_message s i m p l y breaks down the g i v e n frame i n t o i t s component p i e c e s . A s e t o f s t a t e s i s r e p r e s e n t e d i n two p a r t s : a b i t s t r i n g and a l i n k e d l i s t . The b i t s t r i n g r e p r e s e n t s t h e s e t of p o s s i b l e c o n t r o l s t a t e s ( i n f o r m a t i o n t r a n s f e r , d i s c o n n e c t e d , s e n d i n g SABM, and so f o r t h ) . The l i n k e d l i s t r e p r e s e n t s the p o s s i b l e c o m b i n a t i o n s o f d a t a t r a n s f e r v a r i a b l e s (V(S), V ( T ) , V(R), v a r i o u s c o n d i t i o n s ) w i t h i n t h e i n f o r m a t i o n t r a n s f e r phase; t h e s p e c i a l v a l u e UNKNOWN (-1) i s used t o i n d i c a t e a v a r i a b l e which may have any v a l i d v a l u e . The P b i t i n SABM and DISC frames r e c e i v e d by t h e IUT, the s t a t e i n which a DISC was r e c e i v e d , and t h e p o s s i b i l i t y of an i n v i s i b l e t r a n s i t i o n f r o m sending-SABM o r sending-DISC t o i n f o r m a t i o n - t r a n s f e r o r d i s c o n n e c t e d a r e m a i n t a i n e d by d u p l i c a t i n g t h e v a r i o u s s t a t e s . F o r example, t h e r e a r e two received-SABM 3 t a t e s , one f o r P=0 and one f o r P - l . To p r e v e n t ( o r a t l e a s t reduce) redundancy, whenever a node i s added t o t h e l i n k e d l i s t , t h e l i s t i s f i r s t checked t o ensure t h a t t h e new node i s not i n c l u d e d i n a node a l r e a d y on the l i s t , and c o n v e r s e l y , any nodes on t h e l i s t i n c l u d e d i n the new node a r e removed. C.4. The m a i n module The main module, i n a n a l y z e . c , implements t h e t h r e e t r a c e a n a l y s i s a l g o r i t h m s . (The f i r s t a l g o r i t h m can be seen as a s p e c i a l case o f the second, w i t h d e l t a s e t t o 0. The second and t h i r d a l g o r i t h m s a r e s u f f i c i e n t l y s i m i l a r t h a t a s i n g l e program can be used t o p e r f o r m both.) Two message queues a r e used t o s t o r e messages observed t r a v e l l i n g t o and f r o m t h e IUT, f o r time d e l t a . The sequence o f s e t s s _ i i s r e p r e s e n t e d as a l i n k e d l i s t , w i t h t h e f i r s t s e t c o r r e s p o n d i n g t o the l a s t message t a k e n o f f t h e from-IUT queue, and the o t h e r s c o r r e s p o n d i n g t o t h e messages c u r r e n t l y on t h e from-IUT queue. Two f l a g s a r e used, m e s s a g e s _ l o s t and i n i t _ p h a s e . The m e s s a g e s _ l o s t f l a g i n d i c a t e s whether t h e second a l g o r i t h m o r t h e t h i r d a l g o r i t h m i s b e i n g used; t h e i n i t _ p h a s e f l a g i n d i c a t e s whether t h e a l g o r i t h m i s s t i l l i n i t s i n i t i a l i z a t i o n phase. Most o f t h e c o m p l e x i t y o f the a l g o r i t h m l i e s i n t h e u p d a t i n g of t h e s e t s s _ i when a message q _ j i s dequeued from the to-IUT queue. I n t h e im p l e m e n t a t i o n , the u p d a t i n g i s done i n p l a c e : t h e f i r s t s e t on t h e l i s t i s updated, t h e n t h e second s e t i s u p d a t e d ( u s i n g t h e o l d v a l u e o f t h e second s e t and the updated v a l u e o f t h e f i r s t s e t ) , and so f o r t h . Page 75 Appendix D: The r e - s p e c i f i e d LAPB te s t s u i t e R e - s p e c i f i c a t i o n of the ISO 8882-2 t e s t s u i t e . For each t e s t case, only the expected sequence of events i s i d e n t i f i e d ; unexpected events are assumed to be checked by a trace analyzer. The IUT i s t e s t e d f o r conformance to ISO 7776, not CCITT X.25 1980 or 1984. In the data t r a n s f e r t e s t cases, f i x e d sequence numbers are used instead of v a r i a b l e s . The preambles used to e s t a b l i s h the state of the IUT, the postambles used to v e r i f y the state of the IUT, and the I-frames sent to the IUT to make the IUT send I-frames i n response are not s p e c i f i e d here. These matters are to be agreed upon by the tes t laboratory and the c l i e n t . Errors i n the o r i g i n a l t e s t cases are _not_ corrected. Last changed: September 8, 1990 DL1: disconnected phase 101 102 103 104 105 DISC/P-1 DISC/P-0 SABM/P-1 SABM/P-0 DM/F-0 DM/F=1 DM/F=0 UA/F=1 (DL4), DM/F=1 UA/F=0 (DL4), DM/F=0 SABM/P=1 (DL3), DISC/P=1 (DL2), discard 201A undefined command (03FF) 20IB undefined response (01FF) 201C SABM/P-1 with address 04 203 SABM/P-1 with FCS er r o r 204 DM/F-1 205 DM/F=0 with i n f o f i e l d FF 207 SABM/P-1 with i n f o f i e l d FF 208 UA/F-0 with i n f o f i e l d FF 209 RR/P-1 with i n f o f i e l d FF 210 RNR/P-1 with i n f o f i e l d FF 211 REJ/P-1 with i n f o f i e l d FF 215 I/P-0 longer than Nl b i t s 216 DISC/P-0 with i n f o f i e l d FF dis c a r d d i s c a r d d i s c a r d d i s c a r d d i s c a r d d i s c a r d d i s c a r d d i s c a r d d i s c a r d d i s c a r d d i s c a r d d i s c a r d d i s c a r d 301 I/P-l 302 RR/P-1 303 RNR/P-1 304 REJ/P-1 305 UA/F-0 306 UA/F-1 307 FRMR/F-0 308 FRMR/F-1 309 I/P-0 310 RR/F-0 311 RNR/F-0 312 REJ/F-0 313 RR/F-1 314 RNR/F—1 315 REJ/F-1 316 RR/P-0 317 RNR/P-0 318 REJ/P-0 319 I/P-0 with no i n f o f i e l d DM/F-1 DM/F-1 DM/F-1 DM/F-1 di s c a r d d i s c a r d d i s c a r d d i s c a r d d i s c a r d d i s c a r d d i s c a r d d i s c a r d d i s c a r d d i s c a r d d i s c a r d d i s c a r d d i s c a r d d i s c a r d d i s c a r d DL2: l i n k disconnection Appendix D Page 101 DISC/P-0 UA/F=0 102 DISC/P=1 UA/F=1 105 SABM/P-0 DM/F=0 (DL1) 106 SABM/P=1 DM/F=1 (DL1) 109 DM/F=1 (DL1) 110 DM/F-0 discard 111 UA/F-1 (DL1) 201A undefined command (03FF) 201B undefined response (01FF) 205 DISC/P-0 with i n f o f i e l d FF 207 SABM/P-1 with i n f o f i e l d FF 209 UA/F-1 with i n f o f i e l d FF 211 DM/F-1 with i n f o f i e l d FF 219 I/P-l longer than Nl b i t s 221 RR/P-1 with i n f o f i e l d FF 223 RNR/P-1 with i n f o f i e l d FF 225 REJ/P=1 with i n f o f i e l d FF 227 DISC/P-0 with address 04 229 DISC/P-0 with i n v a l i d FCS 231 [omitted] 234 UA/F-0 discard discard d i s c a r d discard discard discard discard discard discard discard discard discard discard 306 RR/P-1 308 RR/P-0 310 RNR/P-1 312 RNR/P-0 314 REJ/P-1 316 REJ/P-0 318 FRMR/F-0 320 RR/F-1 322 RR/F-0 324 RNR/F-1 326 RNR/F=0 328 REJ/F-1 330 REJ/F-0 332 FRMR/F=1 334 I/P-0 336 I/P-l 338 I/P-0 with no i n f o f i e l d d iscard discard discard discard discard discard discard discard discard discard discard discard discard discard discard discard discard DL3: l i n k set-up 101 and 102 are modified somewhat: case separately, we handle them a l 101 SABM/P-0 UA/F-1 instead of handling each c o l l i s i n the same way. -> <- UA/F=0 -> (DL4) 102 SABM/P-1 UA/F-1 105 DISC/P-0 106 DISC/P=1 109 UA/F-1 111 DM/F-0 114 DM/F-1 <- UA/F=1 -> (DL4) DM/F=0 (DL1) DM/F=1 (DL1) (DL4) discard (DL1) 201A undefined command (03FF) 20IB undefined response (01FF) 203 UA/F=1 with i n f o f i e l d FF 205 DISC/P-0 with i n f o f i e l d FF discard discard discard discard Appendix D Page 77 207 SABM/P=1 with in f o f i e l d FF d i s c a r d 209 DM/F-1 with i n f o f i e l d FF d i s c a r d 217 I/P- l longer than Nl b i t s d i s c a r d 219 I/P-0 with no i n f o f i e l d d i s c a r d 221 RR/P-1 with i n f o f i e l d FF d i s c a r d 223 RNR/P-1 with in f o f i e l d FF d i s c a r d 225 REJ/P-1 with i n f o f i e l d FF d i s c a r d 227 SABM/P-1 with address 04 d i s c a r d 229 SABM/P-1 with FCS er r o r d i s c a r d 233 [omitted] 235 UA/F-0 di s c a r d 302 RR/P-1 dis c a r d 304 RR/P-0 dis c a r d 306 RR/F-1 dis c a r d 308 RR/F-0 dis c a r d 309 FRMR/F—0 dis c a r d 312 FRMR/F—1 dis c a r d 314 I/P-0 d i s c a r d 318 I/P- l d i s c a r d 320 RNR/P-0 dis c a r d 322 RNR/F—0 dis c a r d 324 RNR/P-1 dis c a r d 326 REJ/P-0 discar d 328 REJ/F-0 dis c a r d 330 REJ/P-1 dis c a r d 332 RNR/F—1 discard 334 REJ/F-1 di s c a r d DL4: information t r a n s f e r phase The preamble executed to put the IUT i n DL4 should ensure that the IUT's sequence variabl e s , V(S) and V(R), are 0. The information f i e l d s of I frames sent to the IUT Unexpected I or RR frames may be received while waiting for a response from the IUT. These frames can be discarded by the test engine; the trace analyzer w i l l check t h e i r v a l i d i t y . 101 DISC/P-1 102 SABM/P-1 103 FRMR/F—0 105 I/P-0, NS-0, NR-0 106 I / P - l , NS-0, NR-0 107 RR/P-1, NS-0, NR-0 108 I/P-0, NS-0, NR-0 I/P-0, NS-1, NR-0 I/P-0, NS-2, NR-0 REJ/P-1, NR-1 RR/NR-2, F=received P b i t RR/NR-3, F=received P b i t 109 RNR/P-1, NR-0 UA/F=1 (DL1) UA/F-1 (DL4), DM/F-1 (DL1) SABM/P-1 (DL3), DM/F-0 (DL1) RR or RNR/F—0 or 1, NR-1; or I/NR-1 RR or RNR/F—1, NR-1 RR or RNR/F—1, NR-0 <- I/NS-0 -> <- I/NS-1 -> <- I/NS-2 -> <- RR/F-1, NR-3 <- I/NS-1, NR-3 -> <- I/NS-2, NR-3 -> <- RR or RNR/F—1 110A [same as 108, but send REJ/P-0 instead of REJ/P-1, and do not expect IUT to send RR/F-1] HOB [same as 110A, but send REJ/F-0 instead of REJ/P-0] Appendix D Page 78 111 DM/F=0 113 I/P-0, NS-1, NR=0 i f REJ/P-1, send RR/F-1, NR-0 I/P-0, NS-0, NR-O, no i n f o 114 115 SABM/P-1 (DL3), DM/F-0 (DL1) -> <- REJ/P-1 or P=0 or F=0, NR-0 -> RR or RNR/F—0 or 1, NR-1; or I/NR-1 I/P-0, NS=0, NR-0 I/ P - l , NS-1, NR-1 (send with s i n g l e f l a g between) -> <- RR or RNR/F—1, NR=2 116 I/P-0, NS-0, NR=0 -> <- I/NS-0 I/P-0, NS-1, NR-1 -> <- I/NS-1 I/P-0, NS=2, NR-2 -> <- I/NS-2 I/P-0, NS-3, NR-2 -> <- I/NS-3 (continue to exchange I-frames, not acknowledging those sent by IUT . I/P-0, NS-k+2, NR=2 -> <- I/NS=k+2 (wait f o r 0.5 * TI) I/P-0, NS-k+3, NR=k+3 -> <- I/NS=k+3 (and repeat from beginning, u n t i l > 8 I-frames have been sent by IUT) 117 DISC/P-0 UA/F-0 (DL1) 118 SABM/P-0 UA/F-0 (DL4), DM/F-0 (DL1) 119 I/P-0, NS-0, NR-0 -> <- I/NS-0 I/P-0, NS-1, NR=0 -> <- I/NS-1 RNR/P-0, NR-0 -> 121 <- RR or RNR or REJ/P-1 [same as 119, but send RNR/F-0 instead of RNR/P-0] 123 RR/P-0, NR-0 124 RR/F-0, NR-0 201 UA/F-0 203 UA/F-1 207 FRMR/F-1 209 DM/F-1 211 I/P-0 with i n v a l i d N(R) 213 I/P-0 longer than Nl b i t s 214A undefined command (03FF) 214B undefined response (01FF) 215 DM/F-0 with i n f o f i e l d FF 216A DISC/F-0 with i n f o f i e l d FF 216B SABM/P-1 with i n f o f i e l d FF 216C UA/F-0 with i n f o f i e l d FF 216D RR/F-0 with i n f o f i e l d FF 216E RNR/F-0 with i n f o f i e l d FF RR or RNR/F-0, NR=0; or no response RR or RNR/F-0, NR=0; or no response SABM/P-1 (DL3), DM/F-0 (DL1) SABM/P-1 (DL3), DM/F-0 (DL1) SABM/P-1 (DL3), DM/F-0 (DL1) SABM/P-1 (DL3), DM/F-0 (DL1) FRMR/F-0, C/R-0, wxyz-0000 or 0001 (DL5) FRMR/F-0, C/R-0, wxyz-0000 or 0010 (DL5) FRMR/ C/R=0, wxyz-0000 or 1000 (DL5) FRMR/ C/R-l, wxyz-0000 or 1000 (DL5) FRMR/F-0, C/R-l, wxyz-0000 or 1100 (DL5) FRMR/F-0, C/R-0, wxyz-0000 or 1100 (DL5) FRMR/F-1, C/R-0, wxyz-0000 or 1100 (DL5) FRMR/F-0, C/R-l, wxyz-0000 or 1100 (DL5) FRMR/F-0, C/R-l, wxyz-0000 or 1100 (DL5) FRMR/F-0, C/R-l, wxyz-0000 or 1100 (DL5) Appendix D Page 79 216F REJ/F-0 with i n f o f i e l d FF 216G RR/P-1 with i n f o f i e l d FF 216H RNR/P-1 with i n f o f i e l d FF 2161 REJ/P-1 with i n f o f i e l d FF 217A I/P-l with FCS e r r o r 217B I/P-l with address 04 217C short frame (03) 217D aborted I-frame (031000) 301 RR/F-1 303 RNR/F—1 305 REJ/F-1 DL5: frame r e j e c t c o n d i t i o n Any FRMR sent by the IUT i n these t e s t cases should be the same as the FRMR sent by i t i n the preamble (except that the F b i t may be d i f f e r e n t ) . FRMR/F—0, C/R-l, FRMR/F—1, C/R-0, FRMR/F—1, C/R-0, FRMR/F—1, C/R-0, d i s c a r d d i s c a r d d i s c a r d d i s c a r d SABM/P-1 (DL3), DM/F-0 (DL1) SABM/P-1 (DL3), DM/F-0 (DL1) SABM/P-1 (DL3), DM/F-0 (DL1) wxyz-0000 or 1100 (DL5) wxyz-0000 or 1100 (DL5) wxyz-0000 or 1100 (DL5) wxyz-0000 or 1100 (DL5) 101 DISC/P-1 102 SABM/P-1 103 FRMR/F—0 105 DM/F-0 111 DISC/P-0 112 SABM/P-0 201 I/P-0, NR-5 203 undefined command (03FF) 204 undefined response (01FF) 205A SABM/P-1 with i n f o f i e l d FF 205B DISC/P-0 with i n f o f i e l d FF 205C RR/P-1 with i n f o f i e l d FF 205D RNR/P-1 with i n f o f i e l d FF 205E REJ/P-1 with i n f o f i e l d FF 206A UA/F-0 with i n f o f i e l d FF 206B DM/F-0 with i n f o f i e l d FF 206C RR/F-0 with i n f o f i e l d FF 206D RNR/F—0 with i n f o f i e l d FF 206E REJ/F-0 with i n f o f i e l d FF 207 UA/F-0 208 UA/F-1 210 DM/F-1 212 SABM/P-0 with address 04 213 SABM/P-0 with FCS e r r o r 216 I/P-0 longer than Nl b i t s 301 I/P-0 302 I /P-l 303 R R/P-1 304 R N R/P-1 305 R E J/P-1 306 RR/P-0 307 RNR/P-0 308 R E J/P-0 309 RR/F-1 310 RNR/F—1 311 REJ/F-1 312 RR/F-0 313 RNR/F—0 314 REJ/F-0 315 I/P-0 with no i n f o f i e l d 316 I/P-0, NS-2 UA/F-1 (DL1) UA/F-1 (DL4), DM/F-1 (DL1) SABM/P-1 (DL3), DM/F-0 (DL1) SABM/P-1 (DL3), DM/F-0 (DL1) UA/F-0 (DL1) UA/F-0 (DL4), DM/F-0 (DL1) FRMR/F—0 FRMR/F—0 or 1 dis c a r d FRMR/F—1 FRMR/F—0 FRMR/F—1 FRMR/F—1 FRMR/F—1 dis c a r d d i s c a r d d i s c a r d d i s c a r d d i s c a r d d i s c a r d d i s c a r d d i s c a r d d i s c a r d d i s c a r d FRMR/F—0, discard FRMR/F—0, FRMR/F—1 FRMR/F-1 FRMR/F—1 FRMR/F—1 FRMR/F—0, FRMR/F—0, FRMR/F—0, d i s c a r d d i s c a r d d i s c a r d d i s c a r d d i s c a r d d i s c a r d FRMR/F-0, FRMR/F—0, discard discard discard discard discard discard DL6: DTE busy c o n d i t i o n Appendix D Page 80 The preamble executed to put the IUT i n DL6 should ensure that the IUT's sequence v a r i a b l e s , V(S) and V(R), are 0. Unexpected I or RNR frames may be received while waiting f o r a response from the IUT. These frames can be discarded by the t e s t engine; the trace analyzer w i l l check t h e i r v a l i d i t y . 101 DISC/P-1 102 SABM/P-1 103 I / P - l , NS-0, NR-0 104 RR/P-0, NR-0 105 RR/P-1, NR-0 106 RNR/P-0, NR-0 107 RNR/P-1, NR-0 110 DM/F-0 112 DISC/P-0 113 SABM/P-0 114 RR/F-0, NR-0 115 RNR/F-0, NR=0 201 UA/F-0 203 UA/F-1 205 FRMR/F-0 207 FRMR/F-1 209 DM/F-1 211 I/P-0 with i n v a l i d N(R) 213 I/P-0 longer than Nl b i t s 214A undefined command (03FF) 214B undefined response (01FF) 215A DM/F-0 with i n f o f i e l d FF 215B DISC/P-0 with i n f o f i e l d FF 215C SABM/P-1 with i n f o f i e l d FF 215D UA/F-0 with i n f o f i e l d FF 215E RR/F-0 with i n f o f i e l d FF 215F RNR/F-0 with i n f o f i e l d FF 215G REJ/F-0 with i n f o f i e l d FF 215H RR/P-1 with i n f o f i e l d FF 2151 RNR/P-1 with i n f o f i e l d FF 215J REJ/P-1 with i n f o f i e l d FF 216 I/P-0, NS-0, NR-0 217 I / P - l , NS-0, NR-0 218 I / P - l , NS-2, NR-0 219 RR/P-1 with address 04 220 RR/P-1 with FCS er r o r 221 I/P-0, NS-0, NR-0, no i n f o 301 RR/F-1 303 RNR/F—1 305 REJ/F-1 DL7 : sent REJ condi t i o n UA/F-1 (DL1) UA/F-1 (DL4), DM/F-1 (DL1) RNR/F—1, NR-0 or 1 RNR/F-0 or 1, NR-0; or no response RNR/F—1, NR-0 RNR/F-0, NR-0; or no response RNR/F—1, NR-0 SABM/P-1 (DL3), DM/F-0 (DLl) UA/F-0 (DL1) UA/F-0 (DL4), DM/F-0 (DL1) RNR/F-0; or no response RNR/F-0; or no response SABM/P-1 SABM/P-1 SABM/P-1 SABM/P-1 SABM/P-1 FRMR/F-0, FRMR/F-0, FRMR/ FRMR/ FRMR/F-0, FRMR/F-0, FRMR/F-1, FRMR/F-0, FRMR/F-0, FRMR/F-0, FRMR/F-0, FRMR/F-1, FRMR/F-1, FRMR/F-1, RNR/F-0, RNR/F—1, RNR/F-0, d i s c a r d d i s c a r d RNR/F-0, SABM/P-1 SABM/P-1 SABM/P-1 (DL3) (DL3) (DL3) (DL3) (DL3) C/R= C/R C/R-C/R-C/R-C/R= C/R C/R-C/R-C/R-C/R C/R-C/R C/R-NR-0 ; NR-0 NR-0 ; , DM/F-, DM/F-, DM/F-, DM/F— , DM/F-0, wxyz 0, wxyz 0, wxyz 1, wxyz 1, wxyz 0, wxyz 0, wxyz 1, wxyz 1, wxyz 1, wxyz 1, wxyz 0, wxyz 0, wxyz 0, wxyz or no (DL1) (DL1) (DL1) (DLl) (DL1) =0000 or 0000 or 0000 or =0000 or =0000 or 0000 or 0000 or 0000 or 0000 or 0000 or 0000 or 0000 or 0000 or =0000 or response 0001 0010 1000 1000 1100 1100 1100 1100 1100 1100 1100 1100 1100 1100 or no response NR=0; or no response (DL3), DM/F-0 (DLl) (DL3), DM/F-0 (DLl) (DL3), DM/F-0 (DLl) (DL5) (DL5) (DL5) (DL5) (DL5) (DL5) (DL5) (DL5) (DL5) (DL5) (DL5) (DL5) (DL5) (DL5) The preamble executed to put the IUT i n DL7 should ensure that the IUT's sequence va r i a b l e s , V(S) and V(R), are 0. Unexpected I, RR, or REJ frames may be received while waiting for a response from the IUT. These frames can be discarded by the tes t engine; the trace analyzer w i l l check t h e i r v a l i d i t y . 101 DISC/P-1 102 SABM/P-1 103 I/P-0, NS-0, NR-0 104 I / P - l , NS-0, NR-0 109 I/P-0, NS-0, NR-0 UA/F-1 (DLl) UA/F-1 (DL4), DM/F-1 (DLl) RR or RNR/F-0 or 1, NR=1; or I/NR-1 RR or RNR/F—1, NR-1 (DL4) -> Appendix 0 Page 81 I/P-0, NS-1, NR-0 (repeat 7 times) I/P-0, NS=6, NR-0 I/P-0, NS-0, NR-0 REJ/P-0, NR-5 RR/NR-6, F-received P b i t RR/NR-7, F-received P b i t RR/NR-O, F-received P b i t <- I/NS-0 -> <- I/NS-1 -> <- I/NS-6 -> <- REJ/F-0 or 1, NR-7 -> <- I/NS-5, NR-7 -> <- I/NS-6, NR-7 -> <- I/NS-7, NR-7 -> 110 [same as 109, but send REJ/P-1 instead of REJ/P-0, and wait f o r RR or REJ/F-1, NR-7 before retransmitted I-frames] 111 DM/F-0 113 I/P-0, NS-0, NR-0, no i n f o 114 DISC/P-0 115 SABM/P-0 SABM/P-1 (DL3), DM/F-0 (DLl) RR or RNR/F-0 or 1, NR-1; or I/NR-1 UA/F-0 (DL1) UA/F-0 (DL4), DM/F-0 (DL1) 118 [same as 109, but send REJ/F-0 instead of REJ/P-0] 201 UA/F-0 203 UA/F-1 205 FRMR/F—0 207 FRMR/F—1 209 DM/F-1 211 I/P-0 with i n v a l i d N(R) 213 I/P-0 longer than Nl b i t s 214A undefined command (03FF) 214B undefined response (01FF) 215A DM/F-0 with i n f o f i e l d FF 215B DISC/P-0 with i n f o f i e l d FF 215C SABM/P-1 with i n f o f i e l d FF 215D UA/F-0 with i n f o f i e l d FF 215E RR/F-0 with i n f o f i e l d FF 215F RNR/F—0 with i n f o f i e l d FF 215G REJ/F-0 with in f o f i e l d FF 215H RR/P-1 with i n f o f i e l d FF 2151 RNR/P-1 with i n f o f i e l d FF 215J REJ/P-1 with i n f o f i e l d FF 217 I/ P - l with address 04 218 I/P-l with FCS er r o r 219 I/P-0, NS-1, NR-0. 301 RR/F-1 303 RNR/F—1 305 REJ/F-1 SABM/P-1 SABM/P-1 SABM/P-1 SABM/P-1 SABM/P-1 FRMR/F—0, FRMR/F—0, FRMR/ FRMR/ FRMR/F—0, FRMR/F—0, FRMR/F—1, FRMR/F—0, FRMR/F—0, FRMR/F—0, FRMR/F—0, FRMR/F—1, FRMR/F—1, FRMR/F—1, discard d i s c a r d discard (DL3) (DL3) (DL3) (DL3) (DL3) C/R-C/R-C/R-C/R C/R-C/R-C/R C/R-C/R= C/R-C/R-C/R C/R C/R DM/F-0 DM/F-0 DM/F-0 DM/F-0 DM/F-0 0, wxyz— 0, wxyz-0, wxyz— 1, wxyz 1, wxyz-0, wxyz-0, wxyz— 1, wxyz— 1, wxyz-1, wxyz-1, wxyz-0, wxyz-0, wxyz-0, wxyz (DL1) (DLl) (DL1) (DLl) (DLl) 0000 or 0000 or 0000 or 0000 or 0000 or 0000 or 0000 or 0000 or 0000 or 0000 or 0000 or 0000 or 0000 or 0000 or 0001 0010 1000 1000 1100 1100 1100 1100 1100 1100 1100 1100 1100 1100 (DL5) (DL5) (DL5) (DL5) (DL5) (DL5) (DL5) (DL5) (DL5) (DL5) (DL5) (DL5) (DL5) (DL5) SABM/P-1 (DL3), DM/F-0 (DLl) SABM/P-1 (DL3), DM/F-0 (DLl) SABM/P-1 (DL3), DM/F-0 (DLl) DL8: system parameters and e r r o r recovery 1_101 1_102 [repeat 1_101, N2 time3] 2 101 (DLl) (Tl timeout) <- DM/F-0 (DL3) (Tl timeout) Appendix D Page 82 <- SABM/P=1 2_103 [repeat 2_101, N2 times] 3_101 (DL2) (TI timeout) <- DISC/P=1 3_103 [repeat 3_101, N2 times] Notes f o r 4_101, 4_103, 4_105: the preamble to put the IUT in t o DL4 i s assumed to set the IUT's v a r i a b l e s V(S) and V(R) to 0. Also, unexpected I or RR frames may be received while waiting f o r a response from the IUT. These may be discarded by the test engine; the trac e analyzer w i l l check t h e i r v a l i d i t y . 4_101 (DL4) I/P-0, NS=0, NR=0 -> <- I/NS=0 (TI timeout) <- RR or RNR or REJ/P=1 4_103 (DL4) I/P-0, NS-0, NR-0 -> <- I/NS-0 I/P-0, NS-1, NR-0 -> <- I/NS-1 (TI timeout) <- RR or RNR or REJ/P-1 RR/F-1, NR-1 -> 4_105 [repeat 4_101, -N2 times] Notes f o r 5_101 and 5_103: the preamble to put the IUT into DL7 i s assumed to set the IUT's v a r i a b l e s V(S) and V(R) to 0. Also, unexpected I frames may be received while waiting for a response from the IUT. These may be discarded by the te s t engine; the trace analyzer w i l l check t h e i r v a l i d i t y . 5_101 (DL7) (TI timeout) <- REJ/NR-0 5_102 [repeat 5_102, N2 times] 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051973/manifest

Comment

Related Items