=Paper=
{{Paper
|id=Vol-1483/1_Bildiri
|storemode=property
|title=Büyüyen Kısmi Yol Kısıtlarıyla Konkolik Test
|pdfUrl=https://ceur-ws.org/Vol-1483/1_Bildiri.pdf
|volume=Vol-1483
|dblpUrl=https://dblp.org/rec/conf/uyms/KorogluS15
}}
==Büyüyen Kısmi Yol Kısıtlarıyla Konkolik Test==
<pdf width="1500px">https://ceur-ws.org/Vol-1483/1_Bildiri.pdf</pdf>
<pre>
    Büyüyen Ksmi Yol Kstlaryla Konkolik Test


                              Yavuz Köro§lu, Alper en


                Bo§aziçi Üniversitesi, Bilgisayar Mühendisli§i Bölümü
                      {yavuz.koroglu,alper.sen}@boun.edu.tr


       Özet. Otomatik birim testler sayesinde programlarn kapsama orann
       arttrmak mümkündür. Konkolik test metodu (concolic testing) otoma-
       tik birim test yaratm için kullanlan bir yazlm testi tekni§idir. Ancak,
       yol patlamas (path explosion) ve kst çözümlerinin (constraint solving)
       yaratt§ darbo§az nedeniyle, ölçeklenebilir bir otomatik konkolik testçi
       geli³tirmek zor olmu³tur. Bu tekni§i ölçeklenebilir hale getirebilmek için
       bu makalede kst çözücüye daha çok ama daha küçük sorgular gönderi-
       lerek çözme üzerindeki yükü haetecek bir yol önerilmi³tir. Yapt§mz
       deneyler altta yatan kst çözücüye yaplan sorgu uzunluklarn dü³ürerek
       bu hedefe yakla³ld§n gösteriyor.


       Anahtar Kelimeler: Konkolik Test (Concolic Testing), Hedef Yöne-
       limli Test (Goal Directed Testing), Dallanma Zorlamas (Branch Enfor-
       cement), Kst Çözümü (Constraint Solving)


1    Giri³

    Konkolik testte amaç test edilen programn yollarn dola³acak girdileri oto-

matik olarak olu³turmaktr. Buna örnek olarak bir üçgen snandrma progra-

mn dü³ünelim. Bu program test edilirken bütün olas sonuçlarn (çe³itkenar,

ikizkenar, e³kenar, üçgen de§il) bir ³ekilde ortaya çkarlmasn sa§layacak test

girdileri üretilmesini bekleriz. Tüm yollar kapsayacak ³ekilde bir test üretmek

zor ve uzun vakit alan bir i³tir. Bu i³in hzlanabilmesi, daha büyük program-

larda da otomatik test üretimini mümkün klacaktr. Konkolik testin daha hzl

çal³mas için önerdi§imiz yöntem kst çözücüye yaplan sorgu uzunluklarn

dü³ürerek bu amaca hizmet etmeyi öngören bir ön çal³madr. Konkolik test

metodu program çal³masn (program execution) istenilen yollara yönlendiren

girdileri yaratmaya çal³r. Bu girdileri yaratabilmek için, istenilen yollarn yol

kstlar (path constraint) bulunur. Böyle kstlar sa§layan girdileri bulmak kst

sa§lama problemi (constraint satisfaction problem) olarak bilinen çok zor bir

problemdir. Bu problemleri çözmek genelde girdinin büyüyü³üyle üssel oranda

vakit alr. Bu yüzden kst sa§lama için yapmay planlad§mz ³ey mümkünse k-

st çözücüye yaplan sorgu saysn artrmak pahasna sorgular ksaltmaktr. Bir

büyük kstn çözümü için daha küçük kstlarn çözümünü kullanmak üzerinde

çal³lm³ bir kirdir [1]. Kst çözücüleri bu ³ekilde kullanmak yazlm do§rula-

mas (verication) alannda önerilmi³tir [2]. Yöntemimizi CREST adl konkolik

test programnda gerçekle³tirdik. Yapt§mz ilk deneysel çal³malarda daha kü-

çük denemeler ile ayn kapsama oranna ula³labildi§ini gördük. Makalenin geri


                                              2
kalan ³u ³ekilde düzenlenmi³tir. Bölüm 2 konkolik test üzerine yaplm³ di§er

çal³malar açklamaktadr. Bölüm 3 konkolik test ve geli³tirilmi³ yeni yöntem

hakknda detayl bilgi vermektedir. Bölüm 4 ise önerilen metodun yararl oldu§u

bir örne§i içermektedir. Bölüm 5 ise küçük programlar üzerindeki deneysel sonuç-

lar gösterirken bu sonuçlar tart³maktadr. Bölüm 6 ise ³imdiye kadar gelinmi³

olan noktay belirtirken Bölüm 7 ise daha ileride yaplabilecekleri anlatmaktadr.


2    lgili Çal³malar


    Konkolik test verilen bir programn istenilen ksmlarn çal³trmak için ge-

rekli girdileri üreten ve programlar somut olarak bu girdilerle çal³tran yazlm

testi temelli bir yakla³mdr. Konkolik test program istenilen tek bir hedefe yön-

lendirilebilir [3] veya olas bütün hedeere varmaya çal³abilir [4] [5] [6]. Java [7]

[8], C [5] ve C# [6] gibi bilinen dillerin ço§unda kullanlm³tr. Konkolik test bü-

yük programlarda çal³trlamad§ndan bu yöntemin farkl ba§lamlarda geli³ti-

rilmesi için çal³malar yaplm³tr [9]. Konkolik testte kullanlan yakla³mlar üze-

rine detayl bir ara³trma bulunmaktadr [5]. Geleneksel konkolik testin özünde

tüm program yollar üzerinde derinlik öncelikli arama (depth rst search) var-

dr [4]. Bu aramalarda uygulamann somut çal³m sonucu hesaplanm³ sembolik

yollar kullanlr. Bu yakla³mda yol üzerinde denenmemi³ en son dallanma tersine

çevrilmeye çal³lr. En çok uygulanan alternatif yakla³mlardan biri ise geni³lik

öncelikli aramadr (breadth rst search) [1] [10]. Bu yakla³mda algoritma rast-

gele bir girdiden ba³lar ve yol üzerinde denenmemi³ ilk dallanmada sapmaya

neden olacak girdileri bulmaya çal³r. lk seviyedeki dallanmalar bitti§inde bir

sonraki dallanmalara geçilir ve yeni girdiler olu³turulurken önceki yaratlm³ gir-

dilerden faydalanlr. Bu yakla³m ba³ta çok küçük yol kstlar yaratr ve kstl

bir test yapma yakla³mna olanak sa§lar. Ba³ka bir arama alternati de kontrol-

ak³ yönlendirmeli (control-ow directed) testtir [5]. Algoritma program istatis-

tiki olarak kontrol-ak³ çizelgesindeki en yakn ifadelere yönlendirmeye çal³r.

Program çal³ma yollar üzerinde arama yaptkça algoritmann yava³lad§ gö-

rülmü³, bu yüzden rastgele yeniden ba³lamalar kullanlm³tr. Rastgele-dallanma

test yakla³m uygulamann somut çal³m sonucu hesaplanm³ sembolik yol üze-

rindeki herhangi bir dallanmay rastgele olarak seçer [5]. Rastgele-dallanma ara-

masnn yan sra, rastgele-yol aramas da denenmi³tir. Bu yakla³m rastgele

yollar seçmeyi ve çal³may bu yollara yönlendirmeyi dener. Bu yakla³mn yaz-

lm testinde en sk kullanlan rastgele-girdi aramasndan daha iyi çal³t§ iddia

edilmi³tir. Bu yakla³m somut bir çal³ma seçer ve bu çal³ma yolu üzerindeki
                 1
her dallanmay
                 2 olaslkla tersine çevirir. Sonra da bu yeni yol kst için girdi
yaratmaya çal³r. Rastgele-dallanma yakla³mnn kapsama bakmndan daha iyi

çal³t§ gösterilmi³tir [5]. Bir di§er ilginç yakla³m ise hedef-yönelimli dallanma

zorlamasdr (goal-directed branch enforcement). Bu yakla³mda belirli bir he-

def için sembolik yol kstlar toplanr ve bütün kst giderek artan ³ekilde kritik

dallanma ko³ullarn çözerek sa§lanr [11]. Bizim çal³mamzda ise, söz konusu

yakla³mn tüm yollar deneyen metodlara genellenmesi sunulmaktadr. Konko-

lik testte kullanlan kst sa§lama problemi verilen kstlar içerisinde kalan bir


                                          3
örnek bulmak olarak tanmlanabilir. Konu hakknda daha fazla bilgi [12] kayna-

§ndan elde edilebilir. Yices, Z3 gibi standart kst çözücülerin yan sra nonlineer

kstlar çözmek [13] ve gerçel saylarda yüksek kesinlik [14] için ayarlanm³ k-

st çözücüler vardr. Kst çözümü 3-sa§lanabilirlik (3-satisability) probleminin

bir genellemesi olup problemin büyük örneklerini çözen bir algoritma bulunmas

beklenmemelidir. Bu makalede kulland§mz yöntem derinlik öncelikli arama ile

hedef-yönelimli konkolik test algoritmalarnn birle³tirilmesiyle geli³tirilmi³tir.


3      Yöntem


3.1       Konkolik Test

      Konkolik (Concolic) test ingilizce   concrete (somut) ve symbolic (sembolik)
testlerin birle³imi için bir ksaltmadr. Bu yakla³mda, test altndaki program

sa§lanmas gereken dallanma ko³ullarnn (branch condition) sembolik olarak

toplanlmasn sa§layacak ³ekle getirilir. Sonra toplanm³ ko³ullar kullanlarak

yeni bir ko³ul kümesi elde edilir. Bu yeni ko³ullar incelenilerek yeni girdiler ya-

ratlr ve programa girdi olarak sunulur.


Tanm 1 DALLANMA KOULU (Branch Condition, c) En az bir program pa-
rametresine (girdi) ba§l sadece do§ru veya yanl³ olabilen ve her farkl sonucun
program farkl bir çal³ma yoluna yönlendirdi§i ko³ullardr.


      Dallanma ko³ullar a³a§dakilerden herhangi biri olabilir:


  Boole cebri (boolean algebra) kullanlarak yazlm³ bir ifade,
  Bir kar³la³trma veya
  Sadece do§ru veya yanl³ döndüren bir fonksiyon.

      Genelde bir programdaki dallanma ko³ullar birbirine ba§ldr, o yüzden bir

ko³ulun sonucunu sabit tutmak di§erlerini etkiler. Rastgele bir çal³ma yolu üze-
                                                                                  N
rindeki rastgele bir ko³ulun, bu yol üzerindeki di§er dallanmalarn ortalama
                                                                                  8
i ile ba§l oldu§u gösterilmi³tir ( N bu yol üzerindeki toplam dallanma ko³ulu
says olarak alnm³tr) [4].


Tanm 2 DALLANMA KOULU BALILII (Branch Condition Dependency)
ki dallanma ko³ulu sadece ve sadece a³a§daki durumlarda birbirine ba§l kabul
edilir:


  ki dallanma ko³ulunun d gibi en az bir ortak de§i³keni varsa veya
  ki ko³ul da üçüncü bir ko³ulla ba§lysa.

      Olas bir çal³ma yolunun gerçeklenebilmesi ancak o yol üzerindeki bütün

dallanma ko³ullarnn sa§lanmasyla olabilir.


                                            4
Tanm 3 TAM YOL KISITI (Full Path Constraint, π ) Tam yol kst, bir ça-
l³ma yolu üzerindeki bütün dallanma ko³ullarnn mantksal Ve operatörüyle
birle³tirilmesi olarak tanmlanr:


                                              N
                                              ^
                                         π=         ci
                                              i=1

      u andan itibaren    kst çözücü ad verilecek olan ve varsa tam yol kstn
sa§layan de§erler yaratabilen bir çözücünün oldu§u varsaylacaktr. Böylece, ger-

çeklenebilir (feasible) bütün çal³ma yollarna götürecek olan gerekli girdiler ya-

ratlp program bu girdilerle çal³trlabilir. Örne§in, program bir     hata ifadesine
yönlendiren bir yol gerçeklenmeye çal³lyor ve buna kar³lk gelen tam yol kst

biliniyorsa ya bu ifadeye varacak girdiler yaratlabilir ya da bu çal³ma yolunun

gerçeklenemez (olanaksz) oldu§u sonucuna varlr.

      Konkolik testte, program önce     rastgele girdilerle çal³trlr. Sonra, çal³ma
srasnda sembolik çal³ma yolunun tam yol kst toplanr. Asl kst üzerinden

yeni bir tam yol kst elde etmek için bir       strateji izlenir. Genel bir strateji bu
tam yol kst üzerindeki son dallanma ko³ulunu tersine çevirmektir [4]. Sonra

yeni yol kst   kst çözücüye verilir ve program için yeni test girdileri elde edilir.
                                                     −1
                                                    N^
                                    π 0 = ¬cN ∧           ci                         (1)

                                                    i=1

      Bu stratejiye derinlik-öncelikli arama ad verilir. Uygulamalar genel olarak

kst saysyla veya azami iterasyon saysyla [5] snrlandrlm³tr. Böyle bir al-

goritma Algoritma 1 üzerinde açklanm³tr.


3.2     Ksmi Yol Kstlar
      Teoride, bir kst çözücünün çal³ma süresi çözücüye verilen ifade (ko³ul)

saysyla üssel olarak büyür [15]. Bu yüzden, kst çözücüye büyük kstlar vermek

kötü bir kirdir. Konkolik testte, ölçeklendirilebilirli§in önündeki üç darbo§az yol

patlamas, yüksek dallanma says ve kst çözücüye verilen bu büyük sorgulardr

[16]. Bizim yakla³mmzda, sorgu uzunluklar sorgu saysn artrmak pahasna

dü³ürülmeye çal³lm³tr.


Tanm 4 KISM YOL KISITI (Partial Path Constraint, φ) Tam yol kstnn
her yukar yakla³m (over-approximation) bir ksmi yol kst olarak adlan-
drlr. Tam yol kstn yol üzerindeki dallanma ko³ullarnn bir kümesi olarak
dü³ünürsek, ksmi yol kstn da tam yol kstnn herhangi bir alt kümesi olarak
görebiliriz.
                                          π→φ

      Tanma göre, mutlak do§ruluk (true) bütün tam yol kstlarnn bir yukar

yakla³mdr. Ayrca, çal³ma yolu üzerindeki her dallanma ko³ulunun da bir

ksmi yol kst oldu§u görülebilir.


                                              5
Algoritma 1 Derinlik Öncelikli Aramal ve Azami terasyonlu Konkolik Test.
Require:   P : program under test
Ensure:  inputs : Test Suite
1: inputs ← ∅
2: input ← generateRandomInputs()
3: for j = 1 to max_iterations do
4:   Execute P with input
5:   Add input to inputs
6:   π ← collectedPathConstraint
7:   for i = length(π ) to 0 do
8:      if !isVisited(branchOf(π[i]) then
9:         c ← π[i]
10:            break
11:        end if
12:     end for
13:     if isDened(c) then
14:        π[i] ← ¬c
15:        input ← generateInput(π )
16:     else
17:        break
18:     end if
19: end for


Teorem 1 YOL KISITLARININ YUKARI YAKLAIMI (Over-approximation
of Path Constraints)
 Bir tam yol kstn sa§layan bütün örnekler ayrca bu yolun bütün ksmi yol
kstlarn da sa§lar.


      E§er sadece ksmi yol kstn çözersek, bu çözümün her zaman tam yol kstn

sa§lama ³ans vardr. Bu çal³mada, tam yol kstlarnn kullanmndan kaçna-

bilmek amacyla ksmi yol kstlarnn yaratlmas üzerine çal³lm³tr. Burada

asl hedef bütünlük (completeness) ve geçerlilikten (soundness) ödün vermeden

büyük kstlarn yaratt§ yükü azaltmaktr.


3.3     Ksmi Yol Kst Yaratma Stratejileri
      Algoritma 2'da program üzerinde tek bir çal³ma yolunu gerçekleyecek girdi

üretilmektedir. Bunun için sembolik olarak bu heden tam yol kst bilinmeli-

dir. E§er 3. satrda ksmi yol kstn sa§layan girdiler bulunamyorsa, tam yol

kst da sa§lanamyor demektir. E§er 8. satrda ö§renilen tam yol kst hedef ile

aynysa istenilen girdi elde edilmi³ demektir. E§er hiçbiri de§ilse, o zaman yolun

sapmasna neden olan bir ko³ul vardr. Bu sapma 15. satrda ö§renilmektedir.

      Algoritma 3'te ise Algoritma 2 kullanlarak tüm yollar gerçekleyecek olan bir

girdi listesi üretilmektedir. Derinlik öncelikli arama kullanlm³tr. 15. satrda

görüldü§ü gibi daha önce gerçeklenmi³ çal³ma yollarndan yeni tam yol kstlar

elde edilerek Algoritma 2'ye verilmektedir.


                                            6
Algoritma 2 Büyüyen Ksmi Yol Kstlar Kullanan Hedef-Yönelimli Konkolik
Test

Require: P : program under test, π : full path constraint of goal
Ensure: input → π
1: φ ← π[length(π) − 1]
2: loop
3:     input ← generateInput(φ)
4:     if input = infeasible then
5:        return   fail
6:     end if
7:     Execute P with input
8:     π 0 ← collectedPathConstraint
                0
9:     if π = π then
10:        return input
11:    end if
12:    repeat
13:      c ← nextConditionOf(π )
                        0
14:    until !contains(π , c)
15:    φ←φ∧c
16: end loop


Algoritma 3 Büyüyen Ksmi Yol Kstlarn Kullanan Tam Konkolik Test
Require:    P : program under test
Ensure:   inputs : Test Suite
 1: inputs ← ∅
 2: φ = true.
 3: girdi ← generateInput(φ)
 4: for j = 1 to max_iterations do
 5:   Execute P with input
 6:   Add input to inputs
 7:   π ← collectedPathConstraint
 8:   for i = length(π ) to 0 do
 9:      if !isVisited(branchOf(π[i]) then
10:          c ← π[i]
11:           break
12:       end if
13:    end for
14:    if isDened(c) then
15:       π[i] ← ¬c
16:       input ← Algortihm 2(P, π )
17:       Add input to inputs
18:    else
19:       break
20:    end if
21: end for


                                             7
Teorem 2 YOL SAPMASI (Path Divergence) Ksmi kst φ yi sa§layan ama
tam yol kstπ 'yi sa§lamayan girdiler var ise bu girdiler için (π → c)∧(π 0 → ¬c)
                                                                              0
ifadesini sa§layan ve yol sapmasna neden olan c vardr. Bu ifadede π , φ yi
sa§layan girdilerin kar³lk geldi§i çal³ma yolunun tam yol kstn belirtmektedir.


   Algoritma 3'ün perfromansn arttrmak için 15. satrda daha uzun ama k-

st çözücüye yüklenmeyen bir   φ ile ba³lanabilir. Bu sefer φ yine son dallanma
ko³ulunun tersi ¬cN i içerir, ama bundan ba³ka birbirinden ba§msz (Tanm
2) di§er bütün dallanma ko³ullarn da içerir. Böyle bir φ yi çözmek, kst çö-

zücü için φ = cN yi çözmek kadar kolay olacaktr, çünkü kst çözücü böyle

bir durumda her dallanma ko³ulunu ayr ayr çözer [4] [17]. Bu durumda ksmi

yol kstlar daha çok de§i³ken içerdi§i için çal³ma yolunu sa§lama ³ans daha

yüksek olacaktr.


                                    Başlangıç,
                                     φ←>


                                       φ için
                                    girdi yarat

                                                                                       evet


                                    φ gerçek-           hayır         Sonraki
                                                                     φ ye geç          Sonraki φ
                                    lenebilir
                                                                     (π → φ)            var mı?
                                       mi?


                                          evet

                                    Programı
                                    Girdilerle                                         hayır
                                     Çalıştır
                                                                     evet


                φ ← φ ∧ cd          π 0 sapıyor hayır     Sonraki    Sonraki π hayır
                                                                                              DUR
                             evet       mu?               π ye geç    var mı?


             ekil 1. Büyüyen Ksmi Yol Kstl Konkolik Test Ak³ Çizelgesi


   Görsel kolaylk vermek için ekil 1 te geli³tiridi§imiz algoritmann ak³ çizel-

gesi vardr. Bir    π listesi oldu§unu ve de her π için bütün yollar deneyen bir φ
listesi oldu§unu varsaymaktadr. Genel olarak sonsuz yol olabilir ve azami ite-

rasyon snr durma ko³ulu olarak kullanlr. Ak³ çizelgesi ayrca                                 cd de§i³kenini
kullanmaktadr. Bu de§i³ken sapma sebebini belirtmek için kullanlm³tr. Hedef

yol kst   π nin bir dallanma ko³uludur.


                                                                8
4       Örnek


       Bu bölümde örnek olarak verilen üç saynn küçükten büyü§e sral olup ol-

mad§n kontrol eden bir program için test kümesi yaratlacaktr. Test altndaki

programn kontrol-ak³ çizelgesi ekil 2 üzerinde gösterilmi³tir.


                                     A

                                                a>b
                                 a≤b

                                          a>c
                                     B           HAY IR


                                 a≤c            b>c

                                          b≤c
                                     C            EV ET


                    ekil 2. sralM(a,b,c) Metodunun Ak³ Çizelgesi


       Klasik bir konkolik test ekil 3 üzerinde görüldü§ü gibi rastgele bir girdi

ile ba³lar. Test altndaki program bu girdiyle çal³trlr ve tam yol kst      π1
hesaplanr. Bundan sonra yeni bir tam yol kst       π2 , π1 in son dallanma ko³ulu
tersine çevrilerek olu³turulur. Bu yeni çal³ma yolunu gerçekleyebilmek için tam

yol kst kst çözücüye verilir. Bu tam yol kst 3 tane dallanma ko³ulu içerdi§i
için bu operasyon     3 uzunlukta kst çözümü, ksaca KÇ(3) olarak tanmlanm³tr.
       Test altndaki program test boyunca 4 kere çal³trlm³tr ve kst çözücüye 3

kere sorgu gönderilmi³tir. Önemli nokta ise bu sorgularn ortalama uzunlu§unun

(3 + 2 + 1)/3 = 2 olmasdr.
       Geli³tiridi§imiz konkolik test tekni§inde ekil 4 üzerinde görülen testte bir

girdiyle ba³lanm³ ve kar³lk gelen tam yol kst ö§renilmi³tir. Sonra   π2 normal
konkolik testteki gibi olu³turulup hedef olarak belirlenmi³tir. Tüm ifadenin çö-

zülmesi yerine tam bu noktada tam yol kstnn yukar yakla³mlar kullanlm³-

tr.   φ21 alttaki kst çözücünün program do§ru çal³ma yoluna yönlendiremeyen
bir girdi yaratmasna neden olmu³tur. Bu yüzden algoritma sapmann nedenini

(cd ) bulur ve ö§renir (φ ← φ ∧ cd ). Bu ö§renme bir ba³ka yukar yakla³m olan
π2 → φ22 → φ21 ile sonuçlanr. Bu yukar yakla³m örnekte program çal³masn
hedefe yönlendirme açsndan yeterli gelmi³tir.

       ki algoritmay kar³la³tracak olursak, bunda da yine test altndaki program

4 kere çal³trlm³tr, ancak kst çözücüye ortalamada (1 + 2 + 1)/3 = 1.33
uzunlu§unda sorgular yaplm³tr.


                                            9
i1 = [0, 0, 0]                                      [ba³langçta]
P1 = A → B → C → EV ET
π1 = (a ≤ b) ∧ (a ≤ c) ∧ (b ≤ c)
π2 = (a ≤ b) ∧ (a ≤ c) ∧ ¬(b ≤ c)
i2 = [0, −1, 2]                                           [KÇ(3)]
P2 = A → B → C → HAY IR
π3 = (a ≤ b) ∧ ¬(a ≤ c)
i3 = [0, 0, −1]                                           [KÇ(2)]
P3 = A → B → HAY IR
π4 = ¬(a ≤ b)
i4 = [−1, 0, −1]                                          [KÇ(1)]
P4 = A → HAY IR
  DUR                                      [Tüm Yollar Denendi]


        ekil 3. Klasik Konkolik Test Kullanlarak Çözüm


 i1 = [0, 0, 0]                                      [ba³langçta]
P1 = A → B → C → EV ET
π1 = (a ≤ b) ∧ (a ≤ c) ∧ (b ≤ c)
π2 = (a ≤ b) ∧ (a ≤ c) ∧ ¬(b ≤ c)
φ21 = ¬(b ≤ c)
i21 = [0, 0, −1]                                          [KÇ(1)]
P21 = A → B → HAY IR                              [P21 6= Pistenen ]
φ22 = (a ≤ c) ∧ ¬(b ≤ c)                             [φ ← φ ∧ cd ]
i22 = [−1, 0, −1]                                         [KÇ(2)]
P22 = A → B → C → HAY IR                          [P22 = Pistenen ]
π3 = ¬(a ≤ b)
φ31 = ¬(a ≤ b)
i31 = [0, −1, −1]                                         [KÇ(1)]
P31 = A → HAY IR
   DUR                                     [Tüm Yollar Denendi]


     ekil 4. Geli³tiridi§imiz Ksmi Yol Kstlar ile Çözüm


                               10
5      Deneyler


      Tekni§imizi CREST adl C için geli³tirilmi³, derinlik-öncelikli arama ve rastgele-

dallanma gibi bilinen stratejileri kullanan bir konkolik test uygulamas üzerine

ekledik [5]. CREST'i ksmi yol kstlarn ve girdi/kst önbelleklenmesi kullana-

cak ³ekilde de§i³tirdik. Ayrca verilen test kümelerinin verilen programlardaki

dallanma kapsamn (branch coverage) ölçen bir kod da yazdk.

      A³a§da be³ farkl konkolik test uygulamas tanmlanm³tr. Bunlardan KYK

ve bKYK bizim geli³tirid§imiz ksmi yol kstlar yakla³mn kullanmaktayken

di§er üçü kar³la³trma amaçl olarak literatürde bulunana ve CREST'te gerçek-

le³tirlmi³ yöntemlerdir.


 1.   DÖA: Derinlik-öncelikli arama kullanan normal konkolik test algoritmas-
      dr.

 2.   KAÇ: Kontrol-ak³ çizelgesi yönlendirmeli konkolik test algoritmasdr.
 3.   Rastgele: Rastgele-dallanma yakla³m kullanlan konkolik test algoritma-
      sdr.

 4.   KYK: Ksmi yol kstlar yakla³m kullanlan konkolik test algoritmasdr.
 5.   bKYK: Bellekli ksmi yol kstlar algoritmasdr. Bu algoritma da normal
      KYK'dan farkl olarak kst çözücüye daha önce yollanm³ sorgular ve test

      altndaki programa gönderilmi³ girdileri hatrlayan bir hafza vardr ve ayn

      sorgularla çal³malarn tekrarlanmasna engel olmak amacyla tasarlanm³

      olup yer kayglar yüzünden bu makalenin d³nda braklm³tr.


      Be³ yöntem de iki farkl C programnda (     Dörtgen ve Üçgen) ile çal³trl-
m³tr. Bu programlar açlar ve kenar uzunluklar verilen üçgen ve dörtgenleri

snandrmak amacyla yazlm³tr. Test altndaki programn çal³trlma için

iterasyon limiti 100 olarak belirlenmi³tir.

      Tablo 1'de deney sonuçlarmz verilmi³tir. Tablodan KYK ve bKYK'nn DÖA

ve KAÇ'a göre daha çok sorgu yapt§ görülebilir. Ancak, ortalama sorgu uzun-

lu§u bunlara göre çok dü³üktür. Benzer ³ekilde Rastgele'nin ortalama sorgu

uzunlu§unn en ksa oldu§u ancak sorgu saysn çok fazla oldu§u ve dallanma

kapsamnn dü³tü§ü görülmektedir. Bu sayede kst çözücünün çözüm süresi kst

uzunlu§uyla üssel olarak artt§ndan karma³klk azaltlm³tr. Tablo'dan bKYK

yönteminin kst çözücü üzerindeki yükü en az tavizle en çok haeten yöntem

oldu§unu görülmektedir. Önceki sorgular hatrlamann toplam sorgu says üze-

rinde bir etkisi olmam³tr, ancak gereksiz test girdilerinin çkarlmas ile test

kümeleri KYK'ya göre küçültmü³tür. Bu saptama            Üçgen programnn ihtiyaç
duydu§u girdi saysnn 27'den 19'a dü³ürülmü³ olmasyla açklanabilir.


6      Sonuçlar


      Bu ön çal³mada büyüyen ksmi yol kstlarnn konkolik test için kullanla-

bilecek bir yakla³m oldu§u gösterilmi³tir. Deneylerimizde ortalama sorgu uzun-

lu§unun yarya kadar dü³ürülmesi ilerisi için umut vaat edici bir geli³medir. Bu

geli³melerin özellikle karma³k yol kstlarna sahip programlarda konkolik testin


                                          11
             Üçgen                               Dörtgen

             Sorgu Ort. Sorgu Girdi   Dallanma    Sorgu    Ort. Sorgu Girdi   Dallanma

 Yöntem Says Uzunlu§u Says Kapsamas          Says   Uzunlu§u Says Kapsamas

    DÖA       10      5.3        11     100%       10         5.5      11      100%

    KAÇ       19     4.789       19     100%       18         5.06     18      100%

 Rastgele     100     2.26      100     85%        100        1.77    100       65%

    KYK       26     2.769       27     100%       17         1.5      18      100%

    bKYK      26     2.769       19     100%       17         1.5      18      100%

             Tablo 1. Üçgen ve Dörtgen Snandrclar için Test Sonuçlar


daha hzl çal³masn sa§layaca§ beklenmektedir. Bu önçal³mann devam ola-

rak ölçeklenebilirli§i görmek açsndan daha büyük kodlar üzerinde test etmeyi

planlamaktayz.


7     Gelecek Çal³malar


     Ksmi yol kstlar yakla³m birkaç ³ekilde geli³tirilebilir. Örne§in,   π için bu
kadar küçük bir yukar yakla³mla ba³lamak çok iyi bir kir de§ildir. Onun yerine

yol üzerinde birbiriyle ba§msz bir dallanma ko³ullar kümesiyle ba³lanabilir.

Sonra kst çözücü bu daha güçlü ksmi kstn ko³ullarn birer birer çözebilir. Bu

yöntem kst çözücüye yüklenmeden sorgu ba³na do§ru girdileri bulma ³ansn

artrr.

     Ksmi yol kstlar   grep ve vim gibi daha büyük kodlar üzerinde test edilmeli-
dir. Zaman kstlarna uyulabilmesi için bu testler henüz gerçekle³tirilememi³tir.


Kaynaklar


 1. P. Godefroid, N. Klarlund, and K. Sen, Dart: Directed automated random testing,
     SIGPLAN Not., vol. 40, no. 6, pp. 213223, 2005.
                                                                 Verication, Model
 2. A. R. Bradley, Sat-based model checking without unrolling, in
     Checking, and Abstract Interpretation - 12th International Conference, VMCAI
     2011, pp. 7087, 2011.
 3. C. Cadar, D. Dunbar, and D. Engler, Klee: Unassisted and automatic generation
                                                          Proceedings of the 8th
     of high-coverage tests for complex systems programs, in
     USENIX Conference on Operating Systems Design and Implementation, OSDI'08,
     2008.
 4. K. Sen, D. Marinov, and G. Agha, Cute: A concolic unit testing engine for c,
     SIGSOFT Softw. Eng. Notes, vol. 30, no. 5, pp. 263272, 2005.
                                                                          Proce-
 5. J. Burnim and K. Sen, Heuristics for scalable dynamic test generation, in
     edings of the 2008 23rd IEEE/ACM International Conference on Automated Soft-
     ware Engineering, ASE '08, 2008.

                                           12
 6. N. Tillmann and J. De Halleux, Pex: White box test generation for .net, in
    Proceedings of the 2Nd International Conference on Tests and Proofs, TAP'08,
    2008.
 7. K. Sen and G. Agha, Cute and jcute: Concolic unit testing and explicit path model-
    checking tools, inProceedings of the 18th International Conference on Computer
    Aided Verication, CAV'06, 2006.
 8. K. Kähkönen, R. Kindermann, K. Heljanko, and I. Niemelä, Experimental com-
    parison of concolic and random testing for java card applets, inModel Checking
    Software (J. van de Pol and M. Weber, eds.), vol. 6349 of Lecture Notes in Com-
    puter Science, pp. 2239, Springer Berlin Heidelberg, 2010.
 9. X. Qu and B. Robinson, A case study of concolic testing tools and their limita-
             Proceedings of the 2011 International Symposium on Empirical Software
    tions, in
    Engineering and Measurement, ESEM '11, 2011.
10. H. Seo and S. Kim, How we get there: A context-guided search strategy in concolic
               Proceedings of the 22Nd ACM SIGSOFT International Symposium on
    testing, in
    Foundations of Software Engineering, FSE 2014, 2014.
11. S. Sidiroglou-Douskos, E. Lahtinen, N. Rittenhouse, P. Piselli, F. Long, D. Kim,
    and M. C. Rinard, Targeted automatic integer overow discovery using goal-
    directed conditional branch enforcement, inProceedings of the Twentieth Interna-
    tional Conference on Architectural Support for Programming Languages and Ope-
    rating Systems, ASPLOS '15, pp. 473486, 2015.
12. E. Tsang, Foundations of constraint satisfaction, 1993.
13. P. Nuzzo, A. Puggelli, S. A. Seshia, and A. Sangiovanni-Vincentelli, Calcs: Smt
                                             Proceedings of the 2010 Conference
    solving for non-linear convex constraints, in
    on Formal Methods in Computer-Aided Design, FMCAD '10, 2010.
14. M. Souza, M. Borges, M. d'Amorim, and C. S. Pasareanu, Coral: Solving comp-
                                         Proceedings of the Third International
    lex constraints for symbolic pathnder, in
    Conference on NASA Formal Methods, NFM'11, 2011.
15. J. Zhou, M. Yin, and C. Zhou, New worst-case upper bound for 2-sat and 3-sat
                                                   Proceedings of the Twenty-Fourth
    with the number of clauses as the parameter, in
    AAAI Conference on Articial Intelligence, 2010.
16. S. Anand, E. K. Burke, T. Y. Chen, J. Clark, M. B. Cohen, W. Grieskamp, M. Har-
    man, M. J. Harrold, and P. Mcminn, An orchestrated survey of methodologies for
    automated software test case generation,   J. Syst. Softw., vol. 86, pp. 19782001,
    Aug. 2013.
17. B. Dutertre, Yices 2.2, in   Computer Aided Verication (A. Biere and R. Bloem,
    eds.), vol. 8559 of   Lecture Notes in Computer Science, pp. 737744, Springer In-
    ternational Publishing, 2014.


                                           13

</pre>