WIXLIB

guage, but also a formal semantics which definesthe meaning, in a formal manner, of any validspecification. This is in contrast to most programming languages which have a formallydefinedsyntax (for instance in BNF), but an informallydefined semantics. The formal semantics is essential for the construction of tools which are helpfulfor the validation of specifications or the development of implementations.While SDL had been developed within CC!ITTsince the seventies for the description of switchingsystems, Estelle and LOTOSwere developedwithin ISO for the specification of communicationprotocols and services. However, all these languages have potentiallya much broader scope ofapplications. However, their effective use in the0S1 area, so far, has been relativelyslow. Thismay be partly explained by the competition betweenthese three languages, which each have certain advantages, and by the difficulty many people have inlearning anew language.In Estelle, a speciilcation module is modeled byan extended FSM. The extensions are related to interaction parameters and additional state variables,and involvetype definitions,expressionsandstatements of the Pascal programming language. Inaddition, certain “Estelle statements” cover aspectsrelated to the creation of the overall system structure consisting in general of a hierarchy of moduleinstances. Communicationbetween modules takesplace through the interaction points of the moduleswhich have been interconnectedby the parentmodule. Communicationis asynchronous, that is,an output message is stored in an input queue of thereceiving module before it is processed.SDL, which has the longest history, is alsobased on an extended FSM model. For the dataextensions, it uses the concept of abstract datatypes with the addition of a notation of programvariables and data structures, similar to what is included in Estelle. However, the notation is not related to Pascal but to CHILL, the programminglanguage recommended by CCITI’. The communication is asynchronous and the destination processof an output message can be identified by variousmeans, including process identifiers or the namesof channels or routes. Recently, the language hasbeen extended to include certain features for objectoriented specificationsIn contrast to the otherFDT’s, SDL was developed, right from the beginning, with an orientation towards a graphical representation. The language includes graphical elementsfor the FSM aspects of a process and the overallstructure of a specification.The data aspects areonly represented in the usual linear, program-likeform. In addition, a completely program-like formis also defined, called SDL-PR, which is mainly111used for the exchange of specificationsbetweendifferent SDL support systems.LOTOS is based on an algebraic calculus forcommunicating systems (CCS iln80])which includes the concept of finite state machines plusparallel processes which communicate through arendezvous mechanism which allows the specification of rendezvous between two or more processes.Asynchronous communicationcan be modeled byintroducing queues explicitly as data types. The interactions are associated with gates which can bepassed as parameters to other processes participating in the interactions. These gates play a role similar to the interaction points in Estelle. The data aspects are covered by an algebraic notation for abstract data types, called ACT ONE, which is quitepowerful, but would benefit fkom the introductionof certain abbreviated notations for the descriptionof common data structures. A graphical representation for LOTOS has also been defined.In addition to the formal description techniquesdiscussed above, the 0S1 standardization committees also use certain semi-formal languages (whichhave no formally defined semantics). In particular,a language called ‘ITCN [Sari92] is used for describing conformancetest cases, and the ASN. 1notation is used for describing the data structures ofthe protocol data units (messages) exchanged bythe 0S1 application layer protocols euf92].Thisnotation is associated with a coding scheme whichdefines the format in which these data units are exchanged over the communicationmedium. All theother languages mentioned above do not addressthis problem.In the context of application layer protocols, inparticular for Open Distributed Processing and distributed systems management, certain forms of object-orientedspecificationsare being used whichare based on extensions of ASN. 1. Also the fonrmlspecification language Z has been proposed, whichis based on set theory and predicate calculus, andwas originallydeveloped for software specifications.2. Testing based on FSM specificationsThe development of testing methods based onFSM specificationshas initiallybeen driven byproblems arising from functional testing of sequential circuits. The appearance of communicationprotocols has given to this theory a new boost.Currently, this model is also attracting much attention in relation with testing of object-oriented software systems [Hoff!13], [Turn92]. Moreover, recent results in binary decision diagram (13DD) technology have increased our ability to deal with thelarge number of states [Brya86]. Traditional workin this field has relied on the model of completely

specified deterministicfinite state machines. Recently, more complex FSM models have also beenstudied.2.1. Basic definitions:conformancerelationsFSMmodelsandA nondeterministicfiite state machine (NFSM)is an initializednondeterministicMealy machinewhichcan be formallydefinedas follows[PBD93]. A nondeterministicfinite state machineA is a 6-tuple (S, X, Y, h, SO,DA), where S is a setof n states with so as the initial state; X is a finite setof input symbols; Y is a finite set of output symboly DA is a specification domain which is a subsetof SXX;DA andP(SXY),h isa behaviorwhere P(SXY)functionh;is the powersetofSXY. The behavior functions defines the possibletransitions of the machine. For each present state Siand input symbol x, each pair (s y) in the result ofthe function represents a possible transition leadingto the next state Sj and producing the output y. Thisis also written as a transition of the form Si-X/y- Sj.machine A becomes deterministic(FSM)Thewhen lh(s )l 1 for all (SJ) e DA. In a deterministic machine, instead of the behavior function, weuse two functions:output functionthe next state functiond, and theAIn the general case, let a x xz.x e X*, a iscalled an acceptable input sequence for stateSi eS,if there exist k states sil, siz, . sik c S and anoutput sequence y yIyQ. .y G Y* such that thereis a sequence of transitions Si-Xz/yl- Sil-X2/y2- Si2- . . . - sik.l-x ykin the machine. We use SikX to denote the set of all the acceptable input sequences for the state si and x; for the state SO,i.e.for A. We extend the behavior function to the setxlof all acceptable input words (sequences) con-taining the empty word e, i.e., h: SxX P (S xY*) [PBD93].An NFSM A is said to be completely specified,if DA ixX.If DA@xXthenA is consideredpar-tially specijied. An NFSM will be also referred toas a complete or a partial machine.The equivalence relation between two states SiandSjintheNFSMAholdsif X7 XJ*andx; (h2(si, ) h2(sj, )), otherwise,VCXGthey arenonequivalent,here hz is the second projection ofthe behavior function which corresponds to theoutput function of the deterministic FSM [Star72].112The machine is said to be retiedif all its states arepairwise nonequivalent. Two NFSMS A and B aresaid to be equivalent if their initial states are equivalen intuitively, this means that the observable behaviors of the two machines are identical.Given a NFSM A (S, X, Y, h, SO,DA), A issaid to be initiallyconnectedif Vs G S 3 a Xl(se hz(s ,a)), where hl is the frost projection ofthe behavior function which corresponds to thenext function of the deterministicFSM [Star72].Every NFSM is equivalent to an initially connectedone.The complete NFSM B (T ,Y,H,t )is saidto be quasi-eqtu”valent to A if for all acceptable input sequences a X: (Hz(tO,tz) hz(sO, a)). Intuitively, this means that for the input sequences forwhich the behavior of A is defined, the behavior ofB is identical.Given the NFSM A (S, X, Y, h, SO,DA), andcomplete NFSM B, B is said to be a reduction ofA,writtenB A,if VaG X;( H2(to,a)GItz(sO,a) ). Intuitively,this means that for the inputsequences for which the behavior of A is defined,the output sequences of B are included in those defined for A.The equivalence, quasi-equivalence,and reduction relations between NFSMS are widely used asthe conformance relations between implementationsand their specifications in protocol test derivationbased on the finite state machines.2.2. Interfaces,fault models and completetest suitesIn protocol engineering, it is customary to distinguish (at least) two levels of abstraction for thedescription of module interfaces: For the protocoland service specifications, the interactions at a SAPare described at an abstract level in terms of atomicevents which normally correspond to a request bythe user or an indication received by the user fromthe protocol entity. For each implementation of theprotocol, an implementation of the abstract interfaceis provided either in software (e.g. procedure calls,operating systems calls) or hardware. The nature ofthe interface implementationis not defined by theprotocol specxlcation. Only the abstract propertiesof interactions, their parameters and ordering constraints defined by the protocol specification mustbe reflected by the implementation.The test cases developed for the conformancetesting of a given protocol should be applicable toall implementations of that protocol, irrespective ofthe interface conventions used by the implementation. Therefore these test cases are based on the

abstract interface definition of the specification. Inorder to execute such a test case with a given implementation under test (JUT), these abstract interactions must be realized in terms of the concreteinterface adopted by the protocol implementation.For instance, the upper tester (UT) accessing theupper SAP of the IUT (see Figure 2) must beadapted to the particular SAP interface adopted bythe IUT.We conclude that in case of black-box testingbased on the specification of the I’UT, the test suitemust be developed based on the abstract interfacesdefined within the specification, and it must be assumed that the (abstract) properties of these interfaces are satisfied by the concrete realization ofthese interfaces in the implementationunder testwe call this the correct interjace assumption. (Howthe validity of this assumption can be tested is outside the scope of this paper).In the context of FSM-based testing, it is assumed that the interface is event-driven, and moreover, that all events on the interface are alternatelycontrolled by the environment and the IUT. In particular, there exist two channels, one is to convey“inputs” of the environment and the second is to receive “outputs” from the IUT. Each abstract inputyields exactly one output symbol, and the next input symbol can be sent to the IUT only after theIUT has moved into a stable state and produced anoutput symbol in response to the previous input.An output reaction of the IUT to any input can be inthe form of a meaningful output (as explicitly defiied by the specification),an “error” or a “null”output (which means “no output”, and which willbe detected by waiting a specifkd time-out period).All these outputs can be observed and are treated asabstract output symbols.Based on such an interface, the reference behavior is assumed to be specified as an NFSM. Thecorrect interface assumption implies that any KITcan also be modeled as an NFSM. In particular, noIUT can “refuse” to execute any input in any of itsstates or produce an output without any input. AnyIUT is thus a completely specified NFSM whoseinput alphabet at least includes the one of the specification NFSM. Moreover, the implementations arecomplete machines even if the specification is apartial machine and include the input alphabet of thereference NFSM.In order to introduce the notion of test coverage,it is necessary to determine which faults of an implementation should be covered. One way to introduce a fault model is by defining a set of implementations with erroneous behavior that should be detected by the test suite. If this set is finite, a finitetest suite exists that covers all faults; if it is not finite, there may be no finite test suite that covers all113faults. In order to define a fault model, we take themutation approach, where a mutant of a specification A is any implementationthat satisfies the correct interface assumption. In the case of FSMbased conformance testing, the mutants of A are theclass of all completely specified NFSMS with thesame input alphabet. A fault model 5 is a subset ofthis class.The concept of conformance relation is neededto distinguish mutants which could exhibit an erroneous behavior BD93].It is usually introducedwhen both the IUT and its corresponding specification are represented with the same formalism. Inthe case of the FSM model, the equivalence, quasiequivalence, and reduction relation are natural candidates for conformance relation. The given specification NFSM A and a conformance relation confpartitionthe set of mutants 5 into the subsets ofconforming implementationsC(A) {1 I IG i? & Iconf A } and non-conformingimplementationsN(A) for the given specification A, i.e., N(A) {1 IIC 3 & I notconf A }. Based on this partition, thenotion of a complete test suite for a given NFSM Awith respect to a given conformance relation andfault model can be formally introduced as follows.A test suite E sX is said to be compzete for thespecification NFSM A and the fault modeI 5 w.r.t.the reduction relation if for any NFSM B (T, X,Y, H, to) in 5 which is not a reductionexistan a Eand a yG Hp(to, a)of A, thesesuchthatyzh2(s0,@. Similarly, complete test suites are defined for the equivalence and quasi-equivalence relations. A complete test suite guarantees detectionof all mutants in the fault model that do not conform to the specification.Them are different ways to characterize a mutant, or the set of mutants within a given faultmodel. The traditional mutation approach defines aset of mutation types, each representing a specifictype of structural fault, that is, a modificationwhich may be introduced into a specification in order to obtain a different behavior. In the so-calledsingle fault model, the mutants considered are thoseobtained from the specification by applying a singlemutation of one of the specified types. In the caseof the so-called multiple fault modkl, the mutantssuch mutations. Inare obtained by me or sev the case of FSM speciflcat.ions, the mutation typesconsidered are usually ouqwt faults (the output of atransition is wrong) or lransfer faults (the next stateof a transition is wrong). In the area of softwaretesting, various types of mutations may be considered, such as sequencing faults (e.g. missing alter-

native path, improper nesting of loops, WHILEinstead of REPEAT,wrong logic expression tocontrol a conditional or looping statement); arithmetic and manipulativeerrors, such as ignoringoverflow, wrong operator (e.g. GT instead of GEor instead of *); calling of the wrong function;wrong specification of data type and/or wrong format of data representation; wrong initial value, orwrong number of data elements; or a reference toan undefined variable or the wrong variable.This “fault-based”identificationof mutantsseems most natural in the context of diagnostictesting where one wants not only detect erroneousbehavior, but also determine how the implementation could be changed in order to make it conformto the specification(e.g. identify a faulty component to be replaced, or identify the part of the proor the part of the FSM state table that shouldbe corrected). It seems that it works well in thecontext of deterministicand completely definedFSM specifications,however, in the context ofnondeterministicsystems, there are many exampleswhere a few mutations lead to a mutant that conforms to the speciilcation;the correspondence between mutations and erroneous behavior is therefore not straightforward.Therefore one uses oftena “wholistic”identificationof mutants, simplycharacterizing the erroneous behavior of the mutantby an appropriate model without comparing itsstructure with the structure of the (correct) ifieddeterministicFSMSThe simplest fault models are defined for specifications which can be represented by completelyspecified deterministic FSMS. In this class of machines, the equivalence relation serves as conformance relation, and the mutants are completelyspecified deterministic machines.When applied to such a machine, the mutationtechnique yields a certain number of mutant FSMS.A particular mutant FSM can be generated ilom thespecification FSM by changing the next state and/orthe output of a number of selected transitions between states. This mutant machine represents acertain combination of output and transfer faults.The number of all possible mutants grows exponentially when the number of states and inputs increase, therefore, some heuristics, such as information about the implementation, severity of faults,test hypotheses should guide this process. Basedon the set of mutants considered, it is possible tofind in one way or another a set of tests which distinguish (kill) all these mutants from the specification FSM.There are different methods for defining the set114of mutants in the fault model, such as the following. In each case, corresponding methods of deriving a complete test suite have been developed.(1) Limitingthe numberof states: The faultmodel consists of the universe Sn of all completedeterministic FSMS with a number of states lessorequal to nt, and which have the input alphabet ofthe specii3cation FSM A, where m n, the numberof states in A. Guessing the bound m is an intuitiveprocess based on the knowledge of a specification,the class of implementationsand their interiorstructure which have to be tested for conformance.The value of m can be also limited due to economicconsiderations. The larger the bound is chosen, thelarger the complete test suite is, as it is illustratedby the existing upper bounds for the complexity oftests [PBD93].The methods for deriving complete test suiteshorn complete deterministic machines are all basedon transition checking approach enn64].Eachmethod, however, requires a distinct type of acharacterizationset [Vasi73] (a W-set) used forstate identification.The UIOv-method[Vuon89],for instance, constructs the W-set only from socalled unique input/output sequences. The methods[Yevt90a],[Petr91], [Petr92] are based on “harmonized” state identifiers eliminating the verilZcation phase that is necessary for the W- and Wpmethods [Chow78],[Fuji9 1]. The methods in[Vasi73], [Chow78], [Fuji91], [Yevt90a] allow theIUT’S to have more states than in the specification(i.e., m2n); and the others [Vuon89],[Petr91], etr92] do not (i.e., m n). Which of these methods can produce a shorter complete test suite for agiven FSM and nz n, is still an open question. Allthe mentioned methods assume that a reliable resetis available in the IUT’s; note that there is anothergroup of methods which guarantee full fault coverage without this assumption (see, e.g., enn64],and the UIOG-methodin [Yao93]). They can beapplied for reduced, deterministic,strongly connected FSM’S. However, these methods usuallyyield much longer complete test suites than theformer. Earlier reviews of the test derivation methods especially of those that do not guarantee fullfault coverage, can be found elsewhere (see, e.g., ra.191], [Sidh89]).The complexity of a corresponding complete testsuite seems to be the price for assuming such abroad fault model. A more restricted fault modelrequires, however, a justit3cation for each particularapplication.(2) Outputfaults only: These

software testing. We review the major results in the area of protocol testing and discuss in which way these methods may also be relevant in the more general context of software testing. 1. Introduction During the last ten years, much research results have been obtained in the area of protocol confor-mance testing in view of obtaining better .