72 REKURZIVNI POSTOPEK TESTIRANJA VEČNIVOJSKEGA KOMUNIKACIJSKEGA SISTEMA INFORMATICA 2/89 Keywords: multilevel communication system, testing, recursive procedure Tone Vidmar, Jernej Virant Fakulteta za elektrotehniko in računalništvo, Ljubljana povzetek* Struktura, arhitektura in sintaksa testnega modela je povzeta po C 13 iri C 135 . Za privzet univerzalni testni model je podan rekurzi-vni postopek testiranja večnivojskega komunikacijskega sistema (*npr. OSI referenčni model*) v njegovem implementacijskem okolju l131. Postopek omogoča testiranje sistema od najnižjega komunikacijskega nivoja proti višjim. Predlagan rekurzivni algotitem zagotavlja uporabnost testne metode (*Perturbacija Globalnega Stanja Sistema PGSS*) t 23 , C 33 , C 43 , C 53 pri testiranju poljubno kompleksnih komunikacijskih sistemov (»redukcija drevesa globalnih stanj ob večpasovnem testiranju*). Celoten postopek je formaliziran in programabileri kar omogoča, da se predlagana metoda razvije v razred t.i. implementacijskih generatorjev. I. IZHODIŠČA Glede na C 13 je model komunikaciskega sistema opisan z mrežo končnih t.i. komunikacijskih avtomatov ECi),E*Ci),mCi) . Termin "komunikacijski avtomat" predstavlja običajen Mealyjev avtomat s specifična sintakso, ki bo opisana v nadaljevanju. ECi) in E*Ci) predstavljata model komunicirajočega para, medtem, ko m(i) predstavlja model komunikacijskega medija v širšem smislu [63, [7] . Dogodki komunikacijskega avtomata so pošiljanje in sprejemanje komunikacijskih sporočil (»protokolarnih, servisnih, implementacijsko odvisnih in aplikacijskih [SI*), S stališča avtomatne teorije dogodki predstavljajo vhodno/izhodne abecede komunikacijskega avtomata. Dogodek v modelu se označuje z $-< +, ti >. Komunikacijska sporočila, ki jih komunikacijski avtomat pošilja se označujejo z "-", tista pa, kijih sprejema se označujejo z " + ", Lokalni dogodki, nič dogodki, se označujejo z "#" (* Predstavljajo interno funkcionalnost komunikacijskega avtomata.*). Sekvenco dveh dogodkov [63 , [ 83 : izhodno črko e in y fu. Sprejemno oddajna sekvenca se v klasičnem Mealyjevem avtomatu interpretira kot, da je vhodna črka e /f generirala H tj povzročila prehod v stanje bi Mealyevi notaciji ima naslednjo obliko f. .,e /e ,£.,. vj x y il Podobna interpretacija je sprejemljiva za poljubne kombinacije dogodkov v komunikacijskem avtomatu. Tipe dogodkov C 83 se lahko v smislu klasičnega Mealyjevega avtomata razdeli na množico vhodnih črk R..receive- in množico izhodnih črk T,.transmit. Lokalni dogodek ustreza t.i. "e" prehodu [73, [83. Vsak komunikacijski avtomat Je torej mogoča interpretirari kot klasičen Mealyjev avtomat. Ta ugotovitev olajšuje nadalnjo formalizacijo rekurzivnega postopka, ker se lahko privzame klasična avtomatna teorija [93, C 103 . V splošnem se množici vhodno/izhodnih črk (* R..vhodna abeceda T..izhodna abeceda *) posameznih komunikacijskih avtomatov delita v podmnožico protokolarnih sporočil P, podmnožico servisnih sporočil Sipodmnožico implementacijskih pogojev J in podmnožico aplikacijskih sporočil A- Po definiciji ISO modela opravlja nižji nivo storitev za višji nivo, ki jo ta zahteva z pošiljanjem servisnih sporočil. Protokolarna sporočila predstavljajo tok virtualnega komunikacijskega kanala za protokolarni par PCi)/P*Ci) na istem nivoju. I in A predstavljata realno okolje komunikacijskega nivoja. Za ECi) in E*Ci) velja, da morata vsebovati funkcionalnost protokola in obeh protokolarnih vmesnikov SCi) in QCi) [63, [123. Odnose omenjenih veličin vidimo na sliki 1. Trojka ECD,E*Ci), mCi) predstavlja mrežo med seboj povezanih komunikacijskih avtomatov: ECi) i F„ R. T t } (f. ,,+e (P ),f.) v V J K p' vk' (f., ,-e (P ),f .) ik y p >-i E*CD - i F Rb Tb wb tb > E. mCi) < F„ R. T. w_ t } 73 ki jih nahajamo na sliki 2. Pri tem veljajo opredelitve: p - množica notranjih stanj komunikacijskega avtomata R - množica vhodnih črk komunikacijskega avtomata, vhodna abeceda T - množica izhodnih črk komunikacijskega avtomata, izhodna abeceda w - logična časovna funkcija prehajanja stanj t - logična funkcija izhodne črke S, . , - A,I. P, S - A,I . V l Slika 1. Rezina komunikacijskega nivojalSO modela II. REKURZIVNI POSTOPEK TESTIRANJA V [22, l 3) , 141, 151 in 16] je opisana osnovna ideja testiranja protokolov z metodo PGSS■ Opredeljene so modifikacije metode, ki so pogojene z uvajanjem robnih pogojev v postopek testiranja t 73 ( 8) . Vendar s tem in uvajanjem dodatnih sintaktičnih konstruktov v testni model problem ekspanzije Števila globalnih stanj v drevesu globalnih stanj T Se vedno ni zadovoljivo rešen. To je očitno na Sliki 3., podaja testni model sestavljen iz 2N+1 komunikacijskih avtomatov. Testna metoda načelno sicer omogoča testiranje poljubnih mrež med seboj povezanih komunikacijskih avtomatov in tako tudi te, vendar pa sta vprašljiva izvedljivost in časovne performanse testiranja. Gledano z določenega nivoja proti nižjim komunikacijskim nivojem, zajema prenosni medij v Širšem smislu m(i) fizični prenosni medij In vse nižje komunikacijske nivoje. To velja za poljuben komunikacijski nivo, razen za prvi nivo.. Za ta nivo obstaja kot model prenosnega medija samo m(l), preko katerega komunicirata E(l) in E*(l). Ce se uspe. trojko E(l), E*ClXmCl) nadomestiti z nekim novim avtomatom m(2), je postopek ponovljiv na nivoju E(2)/E*C2) itd. Tako ponavljanje testriranja trojke Je osnova rekurzivnega algoritma. Ob tem je topologija testnega modela vedno identična s topologijo, ki je podana na Sliki 2.. Potrebno pa je poiskati način nadomeščanja trojke ECi),E*Ci),mCi) z ekvivalentnim komunikacijskim avtomatom m(i + l). A0 Ab Slika 2. Avtomatna mreža modela II.1. Paralelno serijska kompozicija modela Na Sliki 2. vidimo, da se m(i+l) lahko dobi s paralelno kompozicijo ECi) in E*(i) v avtomat QP, ki ji sledi serijska kompozicija dobljenega komunikacijskega avtomata QP z m(i). Ob ugotovitvi, da je komunikacijski avtomat izrazljiv z Mealyjevim avtomatom gre torej za problem paralelno serijske kompozicije takih avtomatov. Formalna osnova paralelno/serijske kompozicije je privzeta po 19J in t 101 . Na Sliki 2 nahajamo naslednje relacije med abecedami posameznih komunikacijskih avtomatov: Ta = Pb U Sa U Iac U Ab Tb = Po U Sb U lbe U Aa Tc = U U A0) X C Pb U Iob UAJ fV = < U I=a U ¿a > «V = < u U U Ab ) a o o+l Rb = Rb' x Kw Rc = Ta X Tb K^ - U Ab K.*, = Sb„ U Aa ECi) [yA 1 Q PCi) Q__Q X CS0. U A^.CP.U S0u IocU Ab).wa.V ET, - «V«PbU lcbU A0J X CSb.,U AaXiPU S.U IbcU A0).wb.V = . mCi) m(i+1) = C(Fa X Fb X FC)XR0 X Rb>/Te.wltt tUl) '«i». = twQ(fa,ra),wbCfb,rb),wcCfc,(ta,V)} t. = t (f ,(t , t. )) v+1 c c a o L2: - Sporočila iz podmnožic p in PL) se a o "skozi" proces -c- prenašajo transparentno od procea -a- k procesu -b- in obratno. L3: - Sporočila in podmnožic A i" A. s® Ct D transparentno prenašajo skozi sistem. Iz teh ugotovitev oziroma trditrv sledi, da imajo za testiranje višjega komunikacijskega nivoja E(i+1)/E*(i+1) relevantno vlogo le dogodki povezani z komunikacijskimi sporočili is podmnožic S ., S. , . d+i D+l' A iri A. . Minimizirana a o logična struktura komunikacijskega avtomata mCi+15, ki predstavlja sa višji komunikacijski nivo komunikacijski medij v širšem smislu, se formalno dobi tako, da se vse črke iz abeced P ,S.,I ,1. -I in a b a b ac bc ca I . nadomesti z pogoji D.C. -Dont't Care Cti Condition- t 10 str. 55, 119) . Dokaz o formalni upravičenosti takega postopka je privzet konceptualno, njegovo formalna osnova pa je podana v C 93 na straneh 34, 88, 91 in 146. Postopek uvajanja pogojev D.C. ne zagotavlja optimalne kompresije notranjih stanj komunikacijskega avtomata m(i+1) t 103 . Na nekatere stranske efekte postopka redukcije notranjih stanj je opozoril J. Hartmanis v C 143 Za konkreten primer, ko gre za strukture elementa m(i+l), se je izkazalo, da je pomembna zgolj korespondenca med stanji strukture m(i+1) po postopku paralelno serijske kompozicije, z reduciranimi stanji, po uvedbi D.C. pogojev. m(i+1) predstavlja servisni vmesnik komunikacijskega nivoja napram višjemu nivoju in model prenosnega medija, ki zagotovi transpareritni prenos komunikacijskih sporočil višjega komunikacijskega nivoja. Ob upoštevanju predstavljenega koncepta Je struktura komunikacijskega avtomata mCi+1) sledeča: «Ci*0 - CCFQ X Fb X F^.CS^U Ab> X V. " Ct„ Dobljena algebrajska struktura je komunikacijski avtomat. Mreža treh komunikacijskih avtomatov ECi),E*Ci),mC 1) je ekvivalentno nadomeščena avtomatom m(i+1). Med posameznimi podmnožicami komunikacijskih sporočil tega komunikacijskega avtomata veljajo relacije in lastnosti, ki se morajo upoštevati V abecedah komunikacijskega avtomata m(i+1): U.2. Generacija vmesnika S(i) Iz strukture mreže avtomatov ki jih nadomešča avtomat m(i+1) je razvidno, da med posameznimi podmnožicami vhodno/izhodnih Črk veljajo sledeče relacije: Ru, = CSotlU Ab> X CSWU AQ) = CSotlX Sw> u CAaX Ab) = CAa X Ab) Ll: - Sporočila iz podmnožic S ,L A a b ac oc ca iri I se interno zaključijo v cb ne generirajo izhodne črke. mCi+1) iri s_.x s. 75 Se pred izpeljavo gornjih formalnih izrazov, se je pokazalo, da so intuitivno postavljene trditve L.1L2 in L3 na mestu. Iz gornje razprave izhaja, da je funkcionalno gledano komunikacijski avtomat m(i+1) hibridni model servisnega vmesnika S(i)~ in prenosnega medija v ožjem smislu m(1). Formalen dokaz za zgornjo trditev Je mogoče zasnovati na postopku serijske dekompozicije 19], C103 avtomata mCi+13 na komunikacijska avtomata S(i) in mCD. Postopek serijske dekompozicije ni trivialen in možen samo pod posebnimo pogoji. Formalno je definiran spolSen primer serijske dekompozicije CIO str. 97, 137). Serijska dekompozicija avtomata mCi+1) je možna samo če obstoja particija ns nortanje abecede tako, da substitucijsko lastnost (*S.P.*) za FUJ. predstavlja izraz 19): w^Cf^.r^-w^Cf.,^) ns S.P. Vprašanje pa je, ali ima SCO substitucijsko lastnost. Dokaz tega je lahko zasnovan na reverzibilnosti postopka kompozicije in dekompozicije 193. Koncept dekompozicije kot formalen dokaz vsebine mCi+1) potrjuje začetno trditev, da je rekurzivni postopek testiranja tudi aplikativni generator strukture servisnega vmesnika SCO- katerega prikazuje slika 5. s U A. c. -*- i b SCI) mCl) Za avtomata dobljena s tem postopkom velja: SCi) = Cn.,R.,w.> mCD = Cn^Rj.Wj) ti n, x Rs ~>T = AaX Ab Shematsks prezentacija take dekompozicije je sledeča: R.= CSatlX Sb^> CAaX Ab) nlr (A X Av) a o Slika 4. Pogoj, ki zadošča za izpeljavo serijske dekompozicije je torej sledeč C 91: ^ a «ry= F^, FU1) v cnA^o5 v v CfiM = w.C".» v = WlitCf„,rUl)) P = particija niča Slika 5. 0 opisanem postopku lahko govoromo kot o aplikacijskem generatorju, ker le ta na osnovi določenih vhodnih podatkov avtomatsko generira strukturo vmesnika, ki predstavlja implementacijsko odvisen del rezine komunikacijskega modela. II.3. MlNIMIZACIJA ABECED F, mCi+1) R, S avtomata Iz definicije globalnega stanja sistema, C 13 , 121, l31, lAl (matrika globalnega stanja) in drevesa globalnih stanj, kot rezultata perturbadjskega postopka, sledi, da je notranja abeceda avtomata mCi+1) definirana z glavno diagonalo globalnih stanj drevesa globalnih stanj. Samo drevo globalnih stanj je reprezentacija avtomata, zato je na osnovi stanj čakalnih vrst, oziroma stranskih elementov matrika stanj, možno avtomatično generirati tudi abecedi R in T C 13 str. 913 . Temu lahko sledi postopek minimizad je opisan v poglavju II. 1. Tudi generacija abeced in posredno same strukture avtomata m(i+1) je lastnost rekurzivne metode kot aplikativnega generatorja. II.4. Vpeljava vmesnika QCi+l) Vpeljava vmesnika Q(i+"|) je vezana na strukturo komunikacijskega nivoja prikazanaga na sliki 1. Vpeljava je ekvivalentna problemu modeliranja protokola PCi+1)\P*Ci+1) na osnovi 76 neformalne specifikacije s tem, da je za vmesnik Q(i+1) znan vmesnik SCi) • Isto velja tudi za uvajanje implementacijskih pogojev bodisi na nivoju avtomatov E in E. bodisi na a b nivoju mc. Opirati se treba predvsem na strukturo in sintakso testnega modela C 81, vse ob upoštevanju robnih pogojev testiranja [ 8.3 , [ 13) . III. ZAKLJUČEK Članek podaja formalno osnovo rekurzivnemu algoritmu -RECALG- večnivojskih komunikacijskih sistemov. Za N - nivojski komunikacijski sistem je struktura rekurzivnega algoritma sledeča: RECALG 1=1 MODELIRANJE m(l)-SCl) DOKLER i <= N MODELIRANJE E(iXE*Ci),QCi) DOKLER TEST NIVOJA NI POZITIVEN GENERACIJA DREVESA GLOBALNIH STANJ KONEC GENERACIJA ABECED FUl,RUj,SUl,mUl MINIMIZACIJSKI POSTOPKI PROCESA m(i + 1) GENERACIJA SCD i » i + 1 KONEC RECALGEND Praktičen primer izvajanja algoritma je podan v [133. Opis uporabljene programske opreme pa v [ 61 . Metoda omogoča "držati" dinamične strukture podatkov, ki se tvorijo v procesu perturbiranja, v implementacijsko obvladljivem obsegu, tudi pri testiranju velikih realnih sistemom. Metoda je bila preverjena in polavtomatsko simulirana na velikem realnemm telekomunikacijskem sistemu. V nadaljevanju dela želimo uporabnost metode razširiti za poljubne topologije med seboj povezanih procesov, obstoječo pa avtomatizirati. LITERATURA: C 13 Pitro Zafiropulo, "Protocol Validation by Duologue-Matrix Analysis", IEEE Transactions on Communications, Vol. Com- 26, decembar, 1980. C 23 Pitro Zafiropulo, Colin H. West, Harry Rudin & Daniel Brand,"Towards Analysing and Synthesizing Protocols", Transactions on Communications, Vol. Com-28, April 1980. t 33 Harry Rudin, Colin H. West, "A Validation Technique for Tihtly Coupled Protocols", IEEE Transactions on Computers, Vol. C-31, July 1982. C 43 Harry Rudin, "Automated Protocol Validation: Some Practical Examples", Proceedings of The Sixth International Conference on Computer Communications Protocol Validation", IBM J. RES. Vol. 22, July 1978, [ 53 Colin H. West, "General Technique for Communication Protocol Validation", IBM J. RES. Vol. 22, July 1978 [63 Tone Vidmar, "Modeliranje komunikacijskih protokolv s končnimi avtomati", Mipro 88, maj 1988, Opatija [73 Tone Vidmar, "Logični protokolarni analizator", Mipro 88, maj 1988, Opatija C 8) Tone Vidmar, "Sintaksa medprocesnega komuniciranja", ETAN 88, junij 1988, Sarajevo C93 J. Hartmanis, R. E. Stearns, Algebraic Structure Theory of Sequential Machines, Prentice - Hall 1966. C 103 Jernej Virant, Preklopne funkcije, strukture in sistemi, Fakulteta za elektrotehniko 1985. [123 Tomaž Kalin, Tone Vidmar, "Logično testiranje protokolov", Informática Vol. 1, Ljubljana januar 1988 [133 Tone Vidmar, Doktorska disertacija, Fakulteta za elektrotehniko, Ljubljana maj 1987 [143 J. Hartmanis "Further Results on the Structure of Sequential Machines", Journal of the Assosiation for Computing Machinery, Vol 10, No. 1, January 1963, 78-88.