=Paper=
{{Paper
|id=Vol-2201/UYMS_YTM_2018_paper_17
|storemode=property
|title=Sonlu Durum Makinelerinin Fourier Analizi Tabanli Sinanmasi(Fourier Analysis based Testing of Finite State Machines)
|pdfUrl=https://ceur-ws.org/Vol-2201/UYMS_YTM_2018_paper_17.pdf
|volume=Vol-2201
|authors=Savas Takan,Tolga Ayav
}}
==Sonlu Durum Makinelerinin Fourier Analizi Tabanli Sinanmasi(Fourier Analysis based Testing of Finite State Machines)==
https://ceur-ws.org/Vol-2201/UYMS_YTM_2018_paper_17.pdf
Sonlu Durum Makinelerinin
Fourier Analizi Tabanl Snanmas
Sava³ Takan ve Tolga Ayav
zmir Yüksek Teknoloji Enstitüsü
Bilgisayar Mühendisli§i Bölümü, Urla, zmir.
{savastakan,tolgaayav}@iyte.edu.tr
Özet Sonlu durum makinesi (FSM), devre ve yazlm testlerinde yaygn
kullanma sahip bir modelleme tekni§idir. FSM'lerin testi için literatürde
çe³itli yöntemler bulunmakla birlikte, modellerin büyümesi sonucu test
kümesinin büyüklü§ü, hata yakalama oran ve test üretim süresi gibi ko-
nularda yüksek ba³arma sahip alternatif test yöntemlerine ihtiyaç bulun-
maktadr. Bu çal³ma ikili fonksiyonlarn Fourier analizine dayanan yeni
bir test olu³turma yöntemi önermektedir. lk sonuçlar, fonksiyonun fre-
kans bile³enlerinden yararlanarak olu³turulan test takmnn daha yüksek
bir performansa sahip oldu§unu göstermektedir. Önerilen yöntem, karak-
teristi§i, maliyeti ve hata yakalama oran üzerinden literatürden seçilen
iki yöntemle kar³la³trlm³tr.
Anahtar Kelimeler: Sonlu durum makinesi, Test takm üretimi, Fo-
urier dönü³ümü, F yöntemi, W yöntemi, UIO yöntemi
Fourier Analysis-Based Testing of
Finite State Machines
Sava³ Takan and Tolga Ayav
zmir Institute of Technology
Dept. of Computer Engineering, Urla, zmir
Abstract 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 F-
method with the two existing methods.
Keywords: Finite State Machine, Test suite, Fourier transformation, F
method, W method, UIO method
1 Giri³
Biçimsel modeller kullanarak test üretilmesi yazlm testinin aktif ara³trma ko-
nularndan birisidir [8]. Bu test yöntemleri, ara yüz tasarmndan uçak yazlm-
larna ve gerçek zamanl sistemlere kadar birçok alanda kullanlmaktadr [1].
Biçimsel modeller kullanlarak olu³turulmu³ testler, test edilen modelin gereksi-
nimleri sa§layp sa§lamad§n snamakta kullanlrlar. Yazlm alannda Finite
State Machine (FSM), Petri Net ve UML gibi çe³itli modellerden yararlanlmak-
tadr. Bu makale FSM modelini ele almaktadr. Literatürde FSM'lerden test
takm yaratan birçok yöntem bulunmaktadr. Bunlar arasnda en yaygn kulla-
nlanlar W, Wp, UIO, UIOv, DS, HSI ve H isimlendirmeleriyle anlanlardr [8]
[13] [5]. Bu projede, ikili fonksiyonlarn Fourier analizine dayanan yeni bir test
üretme tekni§i önerilmektedir. Fourier dönü³ümü matematikte, bilgisayar ve di-
§er mühendislik bilimlerinde geni³ bir kullanm alanna sahiptir [12]. Fourier
dönü³ümüyle elde edilen katsaylar ilgili bile³enlerle fonksiyon çk³ arasndaki
ilintileri vermektedir. Buradan yola çkarak, ileride gösterilece§i gibi fonksiyona
etkisi yüksek olan bile³enler belirlenerek bu bile³enlere ba§l geçi³ler seçilmi³tir.
Daha sonra aç gözlü algoritmas ile bunlardan test takm elde edilmi³tir. Öne-
rilen yöntem, mutasyon çözümlemesi kullanlarak literatürden alnan W ve UIO
yöntemleri ile kar³la³trlm³tr.
2 Sonlu Durum Makinesi Testi
Bir sonlu-durum makinesi M = (I, O, S, f, g, σ ) 6-ls' ndan olu³ur. Burada I, giri³
sembolleri sonlu kümesini, O, çk³ sembolleri sonlu kümesini, S, sonlu durumlar
kümesini, f: S x I → S bir sonraki durumu belirleyen geçi³ fonksiyonunu, g: S x I
→ O, çk³ fonksiyonunu, σ ise makinenin ba³langç durumunu göstermektedir.
Test ile ilgili baz önemli tanmlar a³a§da verilmi³tir.
Test Senaryosu: Belirli bir program yolunu çal³trmak ya da bir gerek-
sinim ile uyumlulu§unu do§rulamak gibi belirli bir amaç veya test ko³ulu için
geli³tirilen, bir dizi girdi de§eri, test öncesi yürütülmesi gereken önko³ullar, test
sonras olu³mas beklenen sonuçlar ve ko³ullar bütünü.
Test Takm: Bir sistem veya bile³eni test etmek için olu³turulmu³ test
senaryolar kümesi. Öyle ki, bir test senaryosu için ardko³ul olan bir durum bir
di§eri için ön ko³uldur.
Genel anlamda, FSM test süreci a³a§daki temel admlardan olu³maktadr
[1]:
Transfer dizisi T(si ), FSM'yi istenilen bir duruma götürmek için kullanlr.
Snama dizisi VERj FSM üzerinde uygulanr ve istenilen çk³larn üretilip
üretilmedi§i kontrol edilir.
Sfrlama dizisi sayesinde s0 ilk duruma geri gidilir.
Bu bölümde, Unique Input Output (UIO) ve W yöntemleri açklanacaktr.
Tüm açklamalar ekil 1'de görülen örnek FSM üzerinden yaplacaktr.
x/1
S1 S2
y/0
x/1 y/0 y/1
x/0
x/1
S3 S4
y/0
ekil 1: örnek FSM
2.1 UIO Yöntemi
X / Y, X giri³ine yant olarak ba³ka bir durum çkt dizisi Y üretmezse, bu
bir UIO dizisidir. UIO yöntemi, UIO dizilerini kullanarak FSM'nin do§rulu§unu
ara³trr. Detaylar için literatürdeki çal³malara ba³vurulabilir [9] [4].
Örnek üzerinde bakacak olursak; ilk a³amada, tüm durum gruplar UIO Me-
todu'nda kök olarak seçilir. Dallanmay önleyen 2 durum vardr. lki, gruplarn
tekil ya da ayn durumlardan olu³masdr. Di§eri ise durumlarn a§acn yuka-
rsnda görülebilmesidir. UIO a§ac ekil 2'de görülmektedir. Dallanmann so-
nunda, yukardan a³a§ya do§ru durumlar seçilir. Her bir durumun kökten ken-
disine kadar olu³turdu§u yol, test senaryolarn meydana getirir. Elde edilen test
senaryolar Tablo 1'de verilmi³tir.
ekil 2: UIO A§ac
States Input Output
S1 YXX 011
S2 Y 1
S3 X 0
S4 YY 00
Tablo 1: Yaratlan Test Senaryolar
2.2 W Metodu
FSM'deki her bir çift durumun davran³n ayrt edebilen bir girdi dizisine W-
kümesi denir. W-metot, W-kümelerini 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 göre giri³ler seçilir.
Örne§in S1, S2 satrlarna baklacak olursa, y giri³inin farkl çk³ üretti§i görül-
mektedir. Bu nedenle S1 ve S2 için y giri³i alnm³tr. S2 ve S3 için y çk³nn
farkl durumlara götürdü§ü görülmü³tür. Dolaysyla burada y giri³i seçilmi³tir.
S3 ve S4 için ise, farkl çk³lar olu³turmas nedeniyle x girdisi alnm³tr. Son
olarak S4 ve S1 için, ileriki durumu farklla³trmas nedeniyle y giri³i seçilmi³tir.
Elde edilen her de§er eklenerek a³a§daki gibi yazlm³tr. Son olarak, giri³ dizi-
leri ters srada alnm³ ve test senaryolar a³a§daki admlarla olu³turulmu³tur
[11][7][13]:
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 10 S3 S2
S2 11 S2 S4
S3 00 S2 S1
S4 10 S3 S4
Tablo 2: FSM Tablosu
3 Önerilen F Yöntemi
F yöntemi, test senaryolarn elde etmek için Fourier katsaylarndan yararlana-
rak en sk kullanlan geçi³leri bulmay amaçlamaktadr. Bunu yapmak için FSM
ilk olarak ikili bir forma dönü³türülür. Örne§in, A durumu 00, B durumu 01, x
0, y 1'dir. Katsaylar, giri³ ve durum bilgileri kullanlarak hesaplanr. Kendi be-
lirledi§imiz bir parametre de§eri olu³turulur. Parametre de§eri olu³turulduktan
sonra, bu katsaylar arasndan e³i§in üstünde kalanlar seçilir. Seçilen katsay-
lar kullanlarak uygun geçi³ler belirlenir. Bu i³lemden sonra, belirlenen geçi³leri
birle³tiren aç gözlü algoritma ile test senaryolar olu³turulur. F yöntemiyle test
senaryosu üretimi ileride örnek FSM üzerinden detaylca anlatlacaktr. Önce-
sinde (takip eden alt bölümde), Fourier analizinin temelleri ele alnmaktadr.
3.1 Fourier Analizi
kili fonksiyonlarn Fourier analizi son on ylda matematik ve mühendislik alan-
larnda 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 dönü³ümü, ikili
fonksiyonlar f : {−1, 1}n → R ³eklinde sözde ikili fonksiyonlara dönü³türür.
Temel tanm ve teorem, kantlar sunulmakszn a³a§da verilmi³tir. Bu konuda
daha fazla açklama, örnek ve teorem O'Donnell [12] ve Wolf 'un [6] çal³mala-
rnda bulunabilir.
Teorem 1 (Fourier Açlm). Her bir fonksiyon f : {−1, 1}n → R Fourier
açlm ile benzersiz bir ³ekilde ifade edilebilir.
f (x) =
P ˆ
S⊆[n] f (S)χS
fˆ(S) Fourier katsaylarn, χS = i∈S xi ise Parity fonksiyonunu ifade
Q
Burada
etmektedir.
Tanm 1 (ç Çarpm). ç çarpm a³a§daki formülle bulunur:
P
x∈{−1,1}n f (x)g(x)
< f, g >= 2n
Fourier katsaylar a³a§daki gibi hesaplanr.
fˆ(S) =< f, χS >
A³a§da basit bir ikili fonksiyon üzerinden Fourier açlmnn nasl hesapland§
gösterilmektedir. Fonksiyonumuz a³a§daki gibi olsun:
f =a∨b∧c
f 'in do§ruluk yöneyinin a³a§daki gibi oldu§u kolayca görülebilir:
[F F F T T T T T]
Fourier açlmnn genel yaps ³u ³ekildedir:
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ˆ(∅) = 3 (1 + 1 + 1 − 1 − 1 − 1 − 1 − 1) = 0.25
2
Benzer ³ekilde ikinci katsay a³a§daki gibi bulunur:
1
fˆ(1) = 3 (1 · 1 + 1 · 1 + 1 · 1 − 1 · 1 − 1 · −1 − 1 · −1 − 1 · −1 − 1 · −1) = 0.75
2
Tüm katsaylar hesapland§nda Fourier açlm a³a§daki ³ekilde elde edilmi³
olur:
f = 0.25 + 0.75a + 0.25b + 0.25ab + 0.25c + 0.25ac − 0.25bc − 0.25abc
3.2 F Yöntemiyle Test Takm Yaratma
Fourier dönü³ümü ikili fonksiyonlar üzerinde tanml oldu§undan, FSM öncelikle
bu forma dönü³türülür. Bu dönü³üm, temelde durumlarn (state) ikili kodlanma-
sndan ibarettir. Örne§in, S1, 00 olarak; S2, 01 olarak kodlanr. Girdi de§erleri
x ve y, srasyla 1 ve 0'a dönü³türülür.
Çk³ fonksiyonu Denklem 1'deki gibidir. Çk³ fonksiyonu giri³ ve durumlar-
dan olu³mu³tur.
O = (S¯1 ∧ S¯2 ∧ X) ∨ (S¯1 ∧ S2 ∧ X) ∨ (S¯1 ∧ S2 ∧ X̄) ∨ (S1 ∧ S2 ∧ X) (1)
Do§ruluk tablosu çkt fonksiyonu kullanlarak elde edilir. Girdiler ve durumlar
Fourier katsaylarn elde etmek için birlikte kullanlr. Fourier açlm Denk-
lem 2'de verilmi³tir:
O = 0 − 05S1 + 0.5S2 + 0 + 0.5X + 0 + 0 + 0.5S1 S2 X (2)
Örnekte görüldü§ü gibi, baz katsaylar sfrdr. Bu nedenle, ilgili bile³enlerin
fonksiyon üzerinde etkisi yoktur. Bu bile³enlerle ilgili olan test senaryolarn sil-
mek, 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 belirlen-
mesinde ve test senaryo saysnn azaltlmasnda rol oynayan iki parametre belir-
lenmi³tir. lki katsaylar büyük olan bile³enlerin seçilmesini sa§layan e³ik de§er,
di§eriyse seçilen bile³enlere ili³kin geçi³lerin saysn snrlamakta kullanlan sfr
ile bir arasnda bir orandr.
Fourier açlmna e³ik de§eri uygulanmasyla e³ik altndaki bile³enler ihmal
edildi§inde O fonksiyonu Denklem 3'te görüldü§ü ³ekle indirgenir.
O = 0.5S1 + 0.5S2 + 0.5X + 0.5S1 S2 X (3)
Denklem 3'te gösterildi§i gibi, katsaylar belirlendikten sonra uygun geçi³ler
seçilir. Tablo 3'de ilgili algoritmalar çal³trldktan sonra seçilmi³ olan geçi³ler
gösterilmektedir.
S1 S2 X S1 S2 Output
0 0 0 1 0 0
0 1 0 1 1 1
1 1 1 0 1 1
0 0 1 0 1 1
0 1 1 1 0 1
1 0 0 0 1 0
Tablo 3: Bütün katsaylar uygulandktan sonra
Fourier terimleriyle ilintili geçi³leri seçmek için ekil 3 ve 4'te görülen al-
goritmalar geli³tirilmi³tir. lk algoritmada katsaylar, geçi³ler, birinci ve ikinci
parametre de§eri olmak üzere dört giri³ bulunmaktadr. Bu algoritmann çkt-
sn, terimler tarafndan seçilen geçi³ler olu³turmaktadr. 'termSize' parametresi,
kaç Fourier teriminin seçilece§ini söylemektedir. 'transitionSize' parametresi ise
kaç tane giri³in alnaca§n söylemektedir. Bu iki parametre sayesinde, test tak-
mnn 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.coe cient!= 0 then
for transition in transitions do
check(term, transition)
if then
temp.add(transition);
temp.size() == transitionSize
if then
return temp;
end
termSet.add(coe cient);
end
end
end
if termSet.size() == termSize then
return temp;
end
end
return temp;
ekil 3: Geçi³lerin seçimini gerçekle³tiren sözde kod
Di§er algoritma ise (ekil 4), Fourier de§i³kenlerini bir ³ablon olarak alr.
Geçi³in uygun olup olmad§, bu ³ablondan kontrol edilir. Desen bir ise ve her-
hangi bir de§i³iklik yoksa, program yanl³ döner. Di§er yandan, e§er desen sfr
ise ve bir de§i³iklik varsa, program yine yanl³ döner. Programn sonunda do§ru
döner.
Input: term, transition
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
if transition.state[i]!= transition.nextState[i] then
return f alse;
end
end
end
return true;
ekil 4: Check(...) sözde kodu
Seçilen geçi³ler, açgözlü algoritmas kullanlarak birle³tirilir. Bunu yapmak
için ilk geçi³ bir çözüm olarak kabul edilir. Yeni geçi³ler her zaman önceki çö-
zümlere eklenmeye çal³r. Mevcut çözümlere dahil olamayan geçi³ler, yeni bir
çözüm olarak kabul edilir.
4 De§erlendirme
Kar³la³trma yapmak için iki adet algoritma kullanlm³tr. Dolaysyla yaratlan
algoritmann verdi§i sonuçlar, kar³la³trlan bu iki algoritma ile snrldr. Ancak
bu alanda pek çok algoritma bulunmaktadr. Mevcut algoritmalarn hepsi ile
kyas yapabilmek mümkün olamad§ için, kar³la³trma yapmak üzere en temel
algoritmalar seçilmi³tir.
Bu bölümde F yöntemi, W ve UIO yöntemleriyle karakteristik, maliyet, et-
kinlik gibi üç farkl kriter üzerinden kar³la³trlmaktadr. Sfrlama says ve test
senaryolarnn ortalama uzunlu§u, test takmnn karakteristi§ini belirlemekte-
dir. Yöntemlerin maliyetini hesaplamak için test takmnn uzunlu§una baklm³-
tr. Yöntemlerin etkinli§iyse hata yakalama oranlaryla ölçülmü³tür. Bu de§erler,
'durum, girdi ve çkt' ile incelenmi³tir. Gra kler 3 tip kon gürasyon ü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'tür.
Datalar, yani FSM'ler, sonuçlarn yanl olmas engellenmek için, belli ba³l
kriterler kullanlarak rastgele biçimde olu³turulmu³tur. Bu kriterler, olu³turu-
lacak FSM'nin durum, sonuç ve giri³ saylarnn ayr ayr de§i³tirilmesiyle ya-
ratlm³tr. Böylece, ara³trlan özelli§in kriterlerin de§i³imine göre nasl sonuç-
lar ü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 gra k için yakla³k 640 adettir. Algoritmalar dört defa
çal³trlarak, gra kler test edilmi³tir. Yani inceleme, sonuçlarn genelle³tirilmesi
adna yakla³k 2560 adet rastgele FSM ile ara³trlm³tr. Yöntemin verimlili§i
mutasyon analizi ile gösterilmi³tir [10][2][3]. Mutasyon operatörleri olarak trans-
fer', ekstra durum ve eksik durum hatalar kullanlm³tr.
Mutasyon testinin, pahal bir test oldu§u bilinmektedir. W ve UIO metotlar
state'lere ula³mak için geçi³ a§acn kullanmaktadr. Fakat bu durum, çok fazla
giri³ verisinin olu³masna neden olmaktadr. Çal³ma kapsamnda geli³tirilen al-
goritmaya da geçi³ a§ac kullanlabilece§i; durumlara elle veri gönderebilece§i
için ve mutasyon testinin maliyetini azaltmak için geçi³ a§ac tüm algoritmalar-
dan çkarlm³tr. Böylece, hatal testin olu³mas engellenmeye çal³lm³tr.
Sfrlama says ve test senaryolarnn ortalama uzunlu§u test takmnn ka-
rakteristi§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. Bu-
rada, de§eri küçük olann sfrlama says ve dolayl olarak da maliyeti küçüktür.
Test senaryosunun ortalama uzunlu§u genel olarak ne kadar fazlaysa, maliyeti
o kadar dü³üktür. Çü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 et-
kisinde oldu§u göz önünde bulundurulmaldr. Dolaysyla, bu de§erler tahmini
sonuç verecektir.
ekil 5 6 7 8'te sadece durum ile ilgili sfrlama, ortalama test senaryosu uzun-
lu§u, test takm uzunlu§u ve hata yakalama oran gra klerine yer verilmi³tir.
Giri³ ve çk³ ile ilgili testler sayfa snr gere§i, bu çal³maya koyulmam³tr.
12
10
8
Sfrlama
6
4
2
0
0 2 4 6 8 10 12 14 16
Durum
F W UIO
ekil 5: Durum saysna göre sfrlama saylar
Sfrlama ve durum gra §inde, sfrlama says açsndan W metodu do§ru-
sal biçimde ilerlerken; F ve UIO metotlarnn azalarak artan biçimde ilerledi§i
görülmektedir. Sfrlama saysnn az olmas, e§er test takm uzunlu§u de§i³mi-
yorsa, test maliyeti açsndan ba³arm yüksek bir sonuç vermektedir. ekil 5'te,
F metodunun en dü³ük sfrlama de§erine sahip olmas dolaysyla, di§erlerine
göre en yüksek ba³arma ula³t§ görülmektedir.
Ortalama Test Senaryosu Uzunlu§u
6
4
2
0 2 4 6 8 10 12 14 16
Durum
F W UIO
ekil 6: Durum saysna göre ortalama test senaryosu uzunlu§u
Test senaryosu uzunlu§u arttkça 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
biçimde artt§ görülmektedir. Di§er yandan F ve UIO metotlar, düz do§ru-
sal biçimde ilerleme göstermi³tir. Bu nedenle, di§erlerine göre W metodunun
ba³armnn daha yüksek oldu§u söylenebilir.
80
Test Takm Uzunlu§u
60
40
20
0
0 2 4 6 8 10 12 14 16
Durum
F W UIO
ekil 7: Durum saysna göre test takm uzunlu§u
Test takm uzunlu§u maliyeti belirler. Test takm uzunlu§u ve durum gra -
§ine (ekil 7) bakt§mzda, W metodunun üstsel biçimde artt§ görülmektedir.
Di§er yandan F ve UIO metodlar, düz do§rusal ilerleme göstermi³tir. Buradan
hareketle, UIO ve F metodlarnn maliyeti dü³ük; dolaysyla ba³arm yüksektir.
0.6
Hata Yakalama Oran
0.5
0.4
0.3
0.2
0 2 4 6 8 10 12 14 16
Durum
F W UIO
ekil 8: Durum saysna ba§l hata yakalama oran
Hata bulma oran, maliyetten sonra en önemli parametrelerden biridir. Hata
bulma oran ve durum gra §ine (ekil 8) bakld§ndan, UIO ve W metodlar-
nn azalarak artan bir yol izledi§i görülmektedir. Di§er yandan F metodu, düz
do§rusal bir gra k çizmektedir. F metodunun hata bulma oran di§erlerine göre
daha yüksek oldu§undan, gösterdi§i ba³arm da di§er metotlara oranla daha
yüksektir.
5 Sonuç
FSM'ler kullanlarak test takmlar yaratan metotlara alternatif olarak, daha iyi
ba³arm sa§lamak amacyla geli³tirilen F metodunda, ikili fonksiyonlar üzerine
Fourier dönü³ümü yöntemi kullanlm³tr. Fourier dönü³ümünde, gürültü karak-
teristikleri ve çe³itli frekans bile³enlerinin fonksiyon çk³ üzerindeki etkilerine
yönelik analiz, yüksek performansl testlerin olu³turulmasna olanak vermekte-
dir. Matematik, bilgisayar bilimleri ve mühendislik gibi geni³ bir alanda çal³lan
Fourier dönü³ümlerinde her bir katsay, de§i³kenlerin de§i³imlerinin fonksiyon
üzerindeki etkisini bildirmektedir. Buradan yola çkarak, fonksiyon için etkisi
en fazla olan de§i³ken de§i³imleri çkarlm³tr. De§i³kenlerdeki de§i³imlere ba-
klarak geçi³ler seçilmi³tir. Daha sonra aç gözlü 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 yöntemi 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 göre en yüksek ba-
³arma ula³t§ görülmü³tür. Di§er yandan, durum ve ortalama test senaryosu
uzunlu§u gra §inde, W metodunun di§erlerine oranla ba³arm yüksek 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³armlar-
nn yüksek oldu§u görülmü³tür. Maliyetten sonra en önemli parametrelerden biri
olan hata bulma oranna bakld§nda ise F metodunun di§er metotlara oranla
daha yüksek ba³arm gösterdi§i sonucuna ula³lm³tr. Bunlarn hepsi de§erlen-
dirildi§inde, F metodunun, di§er metotlara alternatif olabilecek yüksek ba³arm
sa§lad§n söylemek mümkündür.
Kaynaklar
1. Ainapure, B.S.: Software testing and quality assurance. Technical Publications
(2009)
2. Belli, F., Beyazit, M.: A formal framework for mutation testing. In: 2010 Fourth
IEEE International Conference on Secure Software Integration and Reliability Imp-
rovement. pp. 121130. IEEE (2010)
3. Belli, F., Beyazit, M., Takagi, T., Furukawa, Z.: Model-based mutation testing
using pushdown automata. IEICE TRANSACTIONS on Information and Systems
95(9), 22112218 (2012)
4. Broy, M., Jonsson, B., Katoen, J.P., Leucker, M., Pretschner, A.: Model-based
testing of reactive systems. In: Volume 3472 of Springer LNCS. Springer (2005)
5. Damasceno, C.D.N., Masiero, P.C., Simao, A.: Evaluating test characteristics and
eectiveness of fsm-based testing methods on rbac systems. In: Proceedings of the
30th Brazilian Symposium on Software Engineering. pp. 8392. ACM (2016)
6. De Wolf, R.: A brief introduction to fourier analysis on the boolean cube. Theory
of Computing, Graduate Surveys 1(1-20), 15 (2008)
7. Dorofeeva, R., El-Fakih, K., Maag, S., Cavalli, A.R., Yevtushenko, N.: Fsm-based
conformance testing methods: A survey annotated with experimental evaluation.
Information and Software Technology 52(12), 12861297 (2010)
8. Endo, A.T., Simao, A.: Evaluating test suite characteristics, cost, and eectiveness
of fsm-based testing methods. Information and Software Technology 55(6), 1045
1062 (2013)
9. Gargantini, A.: 4 conformance testing. In: Model-based testing of reactive systems,
pp. 87111. Springer (2005)
10. Jia, Y., Harman, M.: An analysis and survey of the development of mutation
testing. IEEE transactions on software engineering 37(5), 649678 (2011)
11. Mathur, A.P.: Foundations of software testing, 2/e. Pearson Education India (2013)
12. O'Donnell, R.: Analysis of boolean functions. Cambridge University Press (2014)
13. Ural, H.: Formal methods for test sequence generation. Computer communications
15(5), 311325 (1992)