Finite State Machine (FSM), as a formal modeling technique to represent both circuits and software, has been widely used in testing. FSM testing is a well-studied subject and there are several test generation methods. However, the current increase in the demand for pervasive and safety critical systems as well as the increase in software size calls for more rigorous methods that can produce more eective test suites particularly in terms of size, time spent for test generation and fault detection ratio. In this study, we propose a new test generation method based on the Fourier analysis of Boolean functions. An analysis on the eects of the various frequency components of the function output allow us to generate test suites with better performance characteristics. We compare our Fmethod with the two existing methods.
Biimsel modeller kullanarak test retilmesi yazlm testinin aktif ara‡trma
konularndan birisidir [
Bir sonlu-durum makinesi M = (I, O, S, f, g, ) 6-ls’ ndan olu‡ur. Burada I, giri‡ sembolleri sonlu kmesini, O, k‡ sembolleri sonlu kmesini, S, sonlu durumlar kmesini, f: S x I ! S bir sonraki durumu belirleyen gei‡ fonksiyonunu, g: S x I ! O, k‡ fonksiyonunu, ise makinenin ba‡lang durumunu gstermektedir.
Test ile ilgili baz nemli tanmlar a‡a§da verilmi‡tir.
Test Senaryosu: Belirli bir program yolunu al‡trmak ya da bir gereksinim ile uyumlulu§unu do§rulamak gibi belirli bir ama veya test ko‡ulu iin geli‡tirilen, bir dizi girdi de§eri, test ncesi yrtlmesi gereken nko‡ullar, test sonras olu‡mas beklenen sonular ve ko‡ullar btn.
Test Takm : Bir sistem veya bile‡eni test etmek iin olu‡turulmu‡ test senaryolar kmesi. yle ki, bir test senaryosu iin ardko‡ul olan bir durum bir di§eri iin n ko‡uldur.
Genel anlamda, FSM test sreci a‡a§daki temel admlardan olu‡maktadr
[
Transfer dizisi T(s i), FSM’yi istenilen bir duruma gtrmek iin kullanlr. Snama dizisi VER j FSM zerinde uygulanr ve istenilen k‡larn retilip retilmedi§i kontrol edilir.
Sfrlama dizisi sayesinde s 0 ilk duruma geri gidilir.
Bu blmde, Unique Input Output (UIO) ve W yntemleri aklanacaktr. Tm aklamalar ekil 1’de grlen rnek FSM zerinden yaplacaktr.
x=1 y=0 y=1
S2 S4 x=1 y=0 S1 S3 y=0
x=0 x=1 ekil 1: rnek FSM 2.1
UIO Yntemi
X / Y, X giri‡ine yant olarak ba‡ka bir durum kt dizisi Y retmezse, bu
bir UIO dizisidir. UIO yntemi, UIO dizilerini kullanarak FSM’nin do§rulu§unu
ara‡trr. Detaylar iin literatrdeki al‡malara ba‡vurulabilir [
rnek zerinde bakacak olursak; ilk a‡amada, tm durum gruplar UIO Metodu’nda kk olarak seilir. Dallanmay nleyen 2 durum vardr. lki, gruplarn tekil ya da ayn durumlardan olu‡masdr. Di§eri ise durumlarn a§acn yukarsnda grlebilmesidir. UIO a§ac ekil 2’de grlmektedir. Dallanmann sonunda, yukardan a‡a§ya do§ru durumlar seilir. Her bir durumun kkten kendisine kadar olu‡turdu§u yol, test senaryolarn meydana getirir. Elde edilen test senaryolar Tablo 1’de verilmi‡tir.
ekil 2: UIO A§ac
S4
YXX
Y
X
YY
FSM’deki her bir ift durumun davran‡n ayrt edebilen bir girdi dizisine
Wkmesi denir. W-metot, W-kmelerini kullanarak FSM’nin do§rulu§unu
ara‡trr. rnek vermek gerekirse, W-metodunda ilk nce Tablo 2 olu‡turulur. Bu
tabloda ikili olarak kontroller yaplr. Elde edilen ayrma gre giri‡ler seilir.
rne§in S1, S2 satrlarna baklacak olursa, y giri‡inin farkl k‡ retti§i
grlmektedir. Bu nedenle S1 ve S2 iin y giri‡i alnm‡tr. S2 ve S3 iin y k‡nn
farkl durumlara gtrd§ grlm‡tr. Dolaysyla burada y giri‡i seilmi‡tir.
S3 ve S4 iin ise, farkl k‡lar olu‡turmas nedeniyle x girdisi alnm‡tr. Son
olarak S4 ve S1 iin, ileriki durumu farklla‡trmas nedeniyle y giri‡i seilmi‡tir.
Elde edilen her de§er eklenerek a‡a§daki gibi yazlm‡tr. Son olarak, giri‡
dizileri ters srada alnm‡ ve test senaryolar a‡a§daki admlarla olu‡turulmu‡tur
[
S1,S2 = y S2,S3 = yy S3,S4 = yyx S4,S1 = yyxy W = {yyxy,yxy,xy,y}
Current States x y Next States Next States
S1 S2 S3 S4 F yntemi, test senaryolarn elde etmek iin Fourier katsaylarndan yararlanarak en sk kullanlan gei‡leri bulmay amalamaktadr. Bunu yapmak iin FSM ilk olarak ikili bir forma dn‡trlr. rne§in, A durumu 00, B durumu 01, x 0, y 1’dir. Katsaylar, giri‡ ve durum bilgileri kullanlarak hesaplanr. Kendi belirledi§imiz bir parametre de§eri olu‡turulur. Parametre de§eri olu‡turulduktan sonra, bu katsaylar arasndan e‡i§in stnde kalanlar seilir. Seilen katsaylar kullanlarak uygun gei‡ler belirlenir. Bu i‡lemden sonra, belirlenen gei‡leri birle‡tiren a gzl algoritma ile test senaryolar olu‡turulur. F yntemiyle test senaryosu retimi ileride rnek FSM zerinden detaylca anlatlacaktr. ncesinde (takip eden alt blmde), Fourier analizinin temelleri ele alnmaktadr. 3.1
Fourier Analizi
kili fonksiyonlarn Fourier analizi son on ylda matematik ve mhendislik
alanlarnda ilgi eken ve ok ara‡trlan bir konu olmasna ra§men, ok az pratik
uygulamas bulunmaktadr. Fourier analizinin bir gere§i olarak, 0 ve 1 yerine 1
ve -1 yanl‡ ve do§ru de§erler olarak kullanlmaktadr. Fourier dn‡m, ikili
fonksiyonlar f : f 1; 1gn ! R ‡eklinde szde ikili fonksiyonlara dn‡trr.
Temel tanm ve teorem, kantlar sunulmakszn a‡a§da verilmi‡tir. Bu konuda
daha fazla aklama, rnek ve teorem O’Donnell [
Teorem 1 (Fourier Alm). Her bir fonksiyon f : f 1; 1gn ! R Fourier alm ile benzersiz bir ‡ekilde ifade edilebilir.
f (x) = PS [n] f^(S) S
etmektedir.
S = Qi2S xi ise Parity fonksiyonunu ifade Tanm 1 ( ˙arpm).
arpm a‡a§daki formlle bulunur: Fourier katsaylar a‡a§daki gibi hesaplanr.
< f; g >=
Px2f 1;1gn f(x)g(x)
2n f^(S) =< f; S >
f = a _ b ^ c [F F F T T T T T] A‡a§da basit bir ikili fonksiyon zerinden Fourier almnn nasl hesapland§ gsterilmektedir. Fonksiyonumuz a‡a§daki gibi olsun: f ’in do§ruluk yneyinin a‡a§daki gibi oldu§u kolayca grlebilir:
f = f^(;) + f^(1)a + f^(2)b + f^(3)ab + f^(4)c + f^(5)ac + f^(6)bc + f^(7)abc Tanm 1 uyarnca, ilk Fourier katsays f^(;) a‡a§daki ‡ekilde hesaplanr: 1 f^(;) = 23 (1 + 1 + 1 1 1 1 Fourier dn‡m ikili fonksiyonlar zerinde tanml oldu§undan, FSM ncelikle bu forma dn‡trlr. Bu dn‡m, temelde durumlarn (state) ikili kodlanmasndan ibarettir. rne§in, S1, 00 olarak; S2, 01 olarak kodlanr. Girdi de§erleri x ve y, srasyla 1 ve 0’a dn‡trlr.
˙k‡ fonksiyonu Denklem 1’deki gibidir. ˙k‡ fonksiyonu giri‡ ve durumlardan olu‡mu‡tur.
O = (S1 ^ S2 ^ X) _ (S1 ^ S2 ^ X) _ (S1 ^ S2 ^ X) _ (S1 ^ S2 ^ X) Do§ruluk tablosu kt fonksiyonu kullanlarak elde edilir. Girdiler ve durumlar Fourier katsaylarn elde etmek iin birlikte kullanlr. Fourier alm Denklem 2’de verilmi‡tir:
O = 0 05S1 + 0:5S2 + 0 + 0:5X + 0 + 0 + 0:5S1S2X (1) (2) rnekte grld§ gibi, baz katsaylar sfrdr. Bu nedenle, ilgili bile‡enlerin fonksiyon zerinde etkisi yoktur. Bu bile‡enlerle ilgili olan test senaryolarn silmek, test takm boyutunu ve test takm maliyetini azaltr. Bu nedenle bir e‡ik de§er belirlenerek e‡i§in altnda kalan bile‡enler ihmal edilir. Testlerin belirlenmesinde ve test senaryo saysnn azaltlmasnda rol oynayan iki parametre belirlenmi‡tir. lki katsaylar byk olan bile‡enlerin seilmesini sa§layan e‡ik de§er, di§eriyse seilen bile‡enlere ili‡kin gei‡lerin saysn snrlamakta kullanlan sfr ile bir arasnda bir orandr.
Fourier almna e‡ik de§eri uygulanmasyla e‡ik altndaki bile‡enler ihmal edildi§inde O fonksiyonu Denklem 3’te grld§ ‡ekle indirgenir.
O = 0:5S1 + 0:5S2 + 0:5X + 0:5S1S2X (3)
Denklem 3’te gsterildi§i gibi, katsaylar belirlendikten sonra uygun gei‡ler seilir. Tablo 3’de ilgili algoritmalar al‡trldktan sonra seilmi‡ olan gei‡ler gsterilmektedir.
Fourier terimleriyle ilintili gei‡leri semek iin ekil 3 ve 4’te grlen algoritmalar geli‡tirilmi‡tir. lk algoritmada katsaylar, gei‡ler, birinci ve ikinci parametre de§eri olmak zere drt giri‡ bulunmaktadr. Bu algoritmann ktsn, terimler tarafndan seilen gei‡ler olu‡turmaktadr. ’termSize’ parametresi, ka Fourier teriminin seilece§ini sylemektedir. ’transitionSize’ parametresi ise ka tane giri‡in alnaca§n sylemektedir. Bu iki parametre sayesinde, test takmnn boyutu ve etkinli§i belirlenebilmektedir.
Input: transitions ,term,transitionSize,termSize sort(term); n = 0; for i termSize to 0 do term = term.removeLast(); if term.coecient != 0 then for transition in transitions do if check(term, transition) then temp.add(transition); if temp.size() == transitionSize then
return temp; end termSet.add(coecient); end end end if termSet.size() == termSize then
return temp; end end return temp;
ekil 3: Gei‡lerin seimini gerekle‡tiren szde kod
Di§er algoritma ise (ekil 4), Fourier de§i‡kenlerini bir ‡ablon olarak alr. Gei‡in uygun olup olmad§, bu ‡ablondan kontrol edilir. Desen bir ise ve herhangi bir de§i‡iklik yoksa, program yanl‡ dner. Di§er yandan, e§er desen sfr ise ve bir de§i‡iklik varsa, program yine yanl‡ dner. Programn sonunda do§ru dner.
Output: boolean for i 0 to transition:state:length() do if term.variables[i]==’1’ then if transition.state[i] == transition.nextState[i] then
return f alse; end else
end end end return true; if transition.state[i] != transition.nextState[i] then return f alse;
ekil 4: Check(...) szde kodu
Seilen gei‡ler, agzl algoritmas kullanlarak birle‡tirilir. Bunu yapmak iin ilk gei‡ bir zm olarak kabul edilir. Yeni gei‡ler her zaman nceki zmlere eklenmeye al‡r. Mevcut zmlere dahil olamayan gei‡ler, yeni bir zm olarak kabul edilir. 4
Kar‡la‡trma yapmak iin iki adet algoritma kullanlm‡tr. Dolaysyla yaratlan algoritmann verdi§i sonular, kar‡la‡trlan bu iki algoritma ile snrldr. Ancak bu alanda pek ok algoritma bulunmaktadr. Mevcut algoritmalarn hepsi ile kyas yapabilmek mmkn olamad§ iin, kar‡la‡trma yapmak zere en temel algoritmalar seilmi‡tir.
Bu blmde F yntemi, W ve UIO yntemleriyle karakteristik, maliyet, etkinlik gibi farkl kriter zerinden kar‡la‡trlmaktadr. Sfrlama says ve test senaryolarnn ortalama uzunlu§u, test takmnn karakteristi§ini belirlemektedir. Yntemlerin maliyetini hesaplamak iin test takmnn uzunlu§una baklm‡tr. Yntemlerin etkinli§iyse hata yakalama oranlaryla llm‡tr. Bu de§erler, ’durum, girdi ve kt’ ile incelenmi‡tir. Grakler 3 tip kongrasyon zerinden olu‡turulmu‡tur:
Giri‡ says de§i‡kendir, k‡ says 4 ve durum says 6’dr. ˙k‡ says de§i‡kendir, giri‡ says 4 ve durum says 6’dr.
Durum says de§i‡kendir, giri‡ ve k‡ saylar 4’tr.
Datalar, yani FSM’ler, sonularn yanl olmas engellenmek iin, belli ba‡l
kriterler kullanlarak rastgele biimde olu‡turulmu‡tur. Bu kriterler,
olu‡turulacak FSM’nin durum, sonu ve giri‡ saylarnn ayr ayr de§i‡tirilmesiyle
yaratlm‡tr. Bylece, ara‡trlan zelli§in kriterlerin de§i‡imine gre nasl
sonular retti§i incelenmi‡tir. Ara‡trlan zellikler ise test durumlarnn ortalama
uzunlu§u, test takmlarnn uzunlu§u ve reset miktardr. Rastgele olu‡turulan
FSM’lerin says, 12 adet grak iin yakla‡k 640 adettir. Algoritmalar drt defa
al‡trlarak, grakler test edilmi‡tir. Yani inceleme, sonularn genelle‡tirilmesi
adna yakla‡k 2560 adet rastgele FSM ile ara‡trlm‡tr. Yntemin verimlili§i
mutasyon analizi ile gsterilmi‡tir [
Mutasyon testinin, pahal bir test oldu§u bilinmektedir. W ve UIO metotlar state’lere ula‡mak iin gei‡ a§acn kullanmaktadr. Fakat bu durum, ok fazla giri‡ verisinin olu‡masna neden olmaktadr. ˙al‡ma kapsamnda geli‡tirilen algoritmaya da gei‡ a§ac kullanlabilece§i; durumlara elle veri gnderebilece§i iin ve mutasyon testinin maliyetini azaltmak iin gei‡ a§ac tm algoritmalardan karlm‡tr. Bylece, hatal testin olu‡mas engellenmeye al‡lm‡tr.
Sfrlama says ve test senaryolarnn ortalama uzunlu§u test takmnn karakteristi§ini belirler. Sfrlama says test senaryo says ile ayndr. Test senaryo saysnn fazla olmas, sfrlama saysnn da fazla olmasndan dolay maliyetlidir. Yani sfrlama says karakteristi§i belirlerken, maliyeti de belirlemektedir. Burada, de§eri kk olann sfrlama says ve dolayl olarak da maliyeti kktr. Test senaryosunun ortalama uzunlu§u genel olarak ne kadar fazlaysa, maliyeti o kadar d‡ktr. ˙nk uzun olmas durumunda sfrlama says daha d‡k olaca§ndan maliyet d‡ecektir. Ancak, her iki de§erin de ba‡ka de§i‡kenlerin etkisinde oldu§u gz nnde bulundurulmaldr. Dolaysyla, bu de§erler tahmini sonu verecektir.
ekil 5 6 7 8’te sadece durum ile ilgili sfrlama, ortalama test senaryosu uzunlu§u, test takm uzunlu§u ve hata yakalama oran graklerine yer verilmi‡tir. Giri‡ ve k‡ ile ilgili testler sayfa snr gere§i, bu al‡maya koyulmam‡tr. 12 10 8 a m lra 6 f S 4 2 0 0 2 4 6 8 10 12 14 16
Durum
F W UIO ekil 5: Durum saysna gre sfrlama saylar
Sfrlama ve durum gra§inde, sfrlama says asndan W metodu do§rusal biimde ilerlerken; F ve UIO metotlarnn azalarak artan biimde ilerledi§i grlmektedir. Sfrlama saysnn az olmas, e§er test takm uzunlu§u de§i‡miu § lu6 n u z U u s o y ra 4 n e S t s e T aam2 l a t r O 80 §u60 u l n u zU40 m k a T tse 20 T 0 0 2 4 6 8 10 12 14 16
Durum
F W UIO ekil 6: Durum saysna gre ortalama test senaryosu uzunlu§u
Test senaryosu uzunlu§u arttka sfrlama says azalaca§ndan, test takm uzunlu§u sabit olma ko‡uluyla, ba‡arm olarak de§erlendirilmektedir. Durum ve ortalama test senaryosu uzunlu§u gra§inde (ekil 6), W metodunun do§rusal biimde artt§ grlmektedir. Di§er yandan F ve UIO metotlar, dz do§rusal biimde ilerleme gstermi‡tir. Bu nedenle, di§erlerine gre W metodunun ba‡armnn daha yksek oldu§u sylenebilir. yorsa, test maliyeti asndan ba‡arm yksek bir sonu vermektedir. ekil 5’te, F metodunun en d‡k sfrlama de§erine sahip olmas dolaysyla, di§erlerine gre en yksek ba‡arma ula‡t§ grlmektedir.
Test takm uzunlu§u maliyeti belirler. Test takm uzunlu§u ve durum gra§ine (ekil 7) bakt§mzda, W metodunun stsel biimde artt§ grlmektedir. Di§er yandan F ve UIO metodlar, dz do§rusal ilerleme gstermi‡tir. Buradan hareketle, UIO ve F metodlarnn maliyeti d‡k; dolaysyla ba‡arm yksektir.
Hata bulma oran, maliyetten sonra en nemli parametrelerden biridir. Hata bulma oran ve durum gra§ine (ekil 8) bakld§ndan, UIO ve W metodlarnn azalarak artan bir yol izledi§i grlmektedir. Di§er yandan F metodu, dz do§rusal bir grak izmektedir. F metodunun hata bulma oran di§erlerine gre daha yksek oldu§undan, gsterdi§i ba‡arm da di§er metotlara oranla daha yksektir. 5
FSM’ler kullanlarak test takmlar yaratan metotlara alternatif olarak, daha iyi ba‡arm sa§lamak amacyla geli‡tirilen F metodunda, ikili fonksiyonlar zerine Fourier dn‡m yntemi kullanlm‡tr. Fourier dn‡mnde, grlt karakteristikleri ve e‡itli frekans bile‡enlerinin fonksiyon k‡ zerindeki etkilerine ynelik analiz, yksek performansl testlerin olu‡turulmasna olanak vermektedir. Matematik, bilgisayar bilimleri ve mhendislik gibi geni‡ bir alanda al‡lan Fourier dn‡mlerinde her bir katsay, de§i‡kenlerin de§i‡imlerinin fonksiyon zerindeki etkisini bildirmektedir. Buradan yola karak, fonksiyon iin etkisi en fazla olan de§i‡ken de§i‡imleri karlm‡tr. De§i‡kenlerdeki de§i‡imlere baklarak gei‡ler seilmi‡tir. Daha sonra a gzl algoritmas ile bunlardan test takm elde edilmi‡tir. Test takmlar yaratan metotlara alternatif olarak, daha iyi ba‡arm sa§lamak amacyla geli‡tirilen F metodu; karakteristi§i, maliyeti ve hata bulma oran bakmndan, mutasyon analiz yntemi ile mevcut metotlarla (UIO ve W) kar‡la‡trlm‡tr.
Kar‡la‡trmalar sonucunda, sfrlama says bakmndan F metodunun en d‡k sfrlama de§erine sahip olmas dolaysyla, di§erlerine gre en yksek ba‡arma ula‡t§ grlm‡tr. Di§er yandan, durum ve ortalama test senaryosu uzunlu§u gra§inde, W metodunun di§erlerine oranla ba‡arm yksek bir sonu verdi§i ortaya km‡tr. Test takm uzunlu§u ve durum gra§ine bakt§mzda ise UIO ve F metodlarnn maliyetlerinin d‡k olmas dolaysyla, ba‡armlarnn yksek oldu§u grlm‡tr. Maliyetten sonra en nemli parametrelerden biri olan hata bulma oranna bakld§nda ise F metodunun di§er metotlara oranla daha yksek ba‡arm gsterdi§i sonucuna ula‡lm‡tr. Bunlarn hepsi de§erlendirildi§inde, F metodunun, di§er metotlara alternatif olabilecek yksek ba‡arm sa§lad§n sylemek mmkndr.