Program Yürütmelerini Sınıflandırmak İçin Donanım Ve Yazılım

Program Yürütmelerini Sınıflandırmak İçin Donanım Ve Yazılım

Program Yürütmelerini S
fland rmak çin Donan m Ve Yaz m Ölçüm
Ayg tlar
Birle tirme
Combining Hardware And Software Instrumentation To Classify Program Executions
Cemal Y lmaz
Bilgisayar Mühendisli i Program
Sabanc Üniversitesi, stanbul
Adam Porter
Bilgisayar Mühendisli i Bölümü
Maryland Üniversitesi, USA
Emine Dumlu
Bilgisayar Mühendisli i Program
Sabanc Üniversitesi, stanbul
[email protected]
[email protected]
[email protected]
Özet
1. Giri
Pek çok çal ma, genellikle yaz m odakl ölçüm
ayg tlar yard
ile, program yürütmelerinden elde
edilen program tayflar , yaz m sistemlerinin
davran sal özelliklerini ortaya ç karmak için
kullanm r.
Bu
genel
yakla
n
önemli
uygulamalar ndan biri ise, ba ar z yürütmelerin,
ba ar
yürütmelerden otamatik olarak ay rt
edilmesidir. Bahsi geçen amaca yönelik literatürde yer
alan bir çok çal man n, do ru s fland rmalar üretti i
görülürken, kullan lan yöntemlerin ek yük masraf ve
fland rma
ba aras
aras ndaki
ödünle imin
dengelenmesi hususu üzerinde sistematik çal malar n
say
azd r. Bu çal ma, donan m performans
sayaçlar
kullanarak
dü ük
maliyetlerde
yürütmelerden veri toplanabilmesine olanak sa layan
çe itli hibrid program tayflar önermektedir. Önerilen
yakla m, dü ük ek yük masrafl donan m tayflar , az
say da ama daha yüksek masrafl yaz m ölçüm
ayg tlar yla birle tirmektedir. Bahsi geçen yakla m,
di er temsili yakla mlarla birlikte kar la rmal
olarak deneysel yöntemlerle de erlendirilmektedir.
Deneysel çal malar n sonuçlar , yeni hibrid program
tayflar n, güvenilir ve etkili (az masrafl ) bir ekilde
yürütmeleri s fland rabilece ini destekler niteliktedir.
Son zamanlarda, çok say da ara rmac , yaz mlar n
kalitesini art rmak için veri güdümlü teknikler
önermi tir. Bu teknikler, program yürütmelerini
izleme, bu yürütmelerden veri toplama, elde edilen
verileri analiz etme ve daha sonra analiz edilmi
sonuçlara göre hareket etme gibi genel bir yakla m
izlemektedir. Bu genel yakla m çok çe itli amaçlar
için kullan lm r. Hata yerlerinin bulunmas ,
ar zalar n önceden tahmin edilmesi ve ar za
raporlar n otamatik olarak s fland lmas , veri
güdümlü yakla mlar n kullan ld
uygulamalara
sadece birkaç örnektir [24,13,23,22,12,18,15].
Bu makalenin odak noktas olan di er bir uygulama
ise, sahadan toplanm olan yürütme verisinin, ba ar
veya ba ar z yürütmeden gelip gelmedi ini
belirlemektir. Halihaz rda var olan çözümler, bu amaç
do rultusunda programlar n kaynak kodlar na veya
obje kodlar na ölçüm ayg tlar eklemek suretiyle elde
edilmi olan ve program tayf (program spectra) olarak
adland lan yürütme verisini kullan r. Bu veri
periyodik olarak toplan r ve analiz edilir. Bu analiz
teknikleri, ba ar z yürütmelerden elde edilen
tayflardaki hatalarla büyük ölçüde ili kili olan
desenleri bulmaya çal maktad r. Elde edilen desenler,
hata durumu bilinmeyen yürütmelerden toplanm
veriyi kullanarak, bu yürütmelerin hatal olup
olmad
s fland rmada kullan r.
Bu ve benzer uygulamalara ili kin temel varsay m
udur: Ba ar ve ba ar z yürütmelerin davran nda
saptanabilir ve tekrarlanabilir desenler vard r ve bu
desenlere benzerliklerin ve/veya bu desenlerden
sapmalar n, büyük ölçüde hatalar n varl
veya
yoklu u ile ili kilidir. Önceki çal malar, çe itli
program tayflar , hatal program yürütmelerini
ba ar
bir ekilde s fland rmada kullanarak, bu
varsay
deneysel olarak destekler niteliktedir
[7,8,11,3].
Üzerinde az çal lm bir konu ise, bu yakla mlar n
maliyeti ve s fland rma ba aras
aras ndaki
ödünle imin nas l dengelenece idir. Bu yakla mlar,
yüksek ek çal ma zaman yükünün (runtime overhead)
genellikle arzulanmada
sahada çal an yaz m
sistemlerini hedeflemi olduklar ndan, bu konu
Abstract
Several research eforts have studied ways to infer
properties of software systems from program spectra
gathered from the running systems, usually with
software-level instrumentation. While these eforts
appear to produce accurate classications, detailed
understanding of their costs and potential cost-benefit
tradeoffs is lacking. In this work we present a hybrid
instrumentation approach which uses hardware
performance counters to gather program spectra at very
low cost. This underlying data is further augmented
with data captured by minimal amounts of softwarelevel instrumentation. We also evaluate this hybrid
approach by comparing it to other existing approaches.
We conclude that these hybrid spectra can reliably
distinguish failed executions from successful
executions at a fraction of the runtime overhead cost of
using software-based execution data.
önemlidir. Bu nedenle, yüksek s fland rma ba ar
desteklemek ve ayn zamanda olabildi ince ölçüm ek
yükünü dü ürmek önemlidir. Önceki çal malar ya bu
problemi göz ard etme e iliminde ya da çözüm için
çe itli örnekleme stratejilerine ba vurmaktad r.
Örneklemenin muhtemel dezavantaj
ise, sert
örnekleme yöntemlerinin, yüksek veri güvenilirli ine
sahip olmak için, yap lmas gereken gözlemlerin
say
ciddi ölçüde art rmas r.
Örnekleme, ek yürütme zaman yükünü dü ürmek için
güçlü bir araç olsa da, yüksek maliyet k tlamalar ,
ölçüm ayg tlar n maliyetini azaltarak da elde
edilebilir. Bu makale, bahsi geçen varsay
de erlendirmek için, ço u veri toplama i inin h zl
donan m performans sayaçlar taraf ndan yerine
getirildi i geli mi bir yakla m önermekte ve bu
yakla
deneysel olarak de erlendirmektedir.
Önerilen yakla mda, donan m sayaçlar ndan elde
edilen veri, ayn zamanda sistem yaz
na eklenen
minimum miktardaki yaz m ölçüm ayg tlar
vas tas yla toplanan ilave verilerle zenginle tirilerek
hibrid bir program tayf olu turulmaktad r. Buradaki
temel amaç; maliyeti dü ürmek için veri toplama i ini
olabildi ince donan n içine gömmektir.
Bu makale ayn zamanda hibrid program tayflar ,
sadece donan m tabanl veya sadece yaz m tabanl
program tayflar yla kar la rmaktad r. Dört tane aç k
kaynak projesi üzerinde yürütülen deneysel
de erlendirmeler, kullan lan kobay yaz mlar için,
hibrid donan m ve yaz m ölçüm ayg tlar
yakla
n, di er yakla mlara oranla çok daha az
masrafl oldu unu ve ayn zamanda en az di er
yakla mlar kadar ba ar z yürütmeleri ba ar
yürütmelerden
ay rmada
etkili
oldu unu
göstermektedir.
2. lgili Çal malar
2.1. Program Yürütmelerini S fland rma
Birçok ara rmac , program tayflar
kullanarak
programlar n davran sal özelliklerini bulmak için
yöntemler geli tirmi tir. Bu çal malar n tümü,
yürütmeleri soyutlamak için, yaz m tayflar (yaz m
odakl ölçüm ayg tlar taraf ndan toplanan program
tayflar ) kullanm r. Podgurski ve di erleri
[7,8,14,19], konu land lm
örneklerde program
çal malar
gruplamak için otamatik kümeleme
analizi kullanm ve elde edilen özgün kümelerin ayn
hatalardan kaynaklanan yürütme profillerini içerme
iliminde oldu unu göstermi tir. Bowring, Rehg ve
Harrold [3], program tayflar
s fland rmak için
(ba ar
ve ba ar z yürütmleri tahmin etmek),
Markov modellerini kullanm r. Bahsi geçen
yakla m, yaz m ölçüm ayg tlar
kullan r ve bir
sistemdeki her dallanma için duyargalara ihtiyaç
duymaktad r. Brun ve Ernst [4], hatal program
yürütmeleri boyunca mevcut olma e iliminde olan,
gözlemlenen olas program de mezlerini tan mlamak
için
çe itli
makine
ö renmesi
yöntemlerini
kullanm r. Bahsi geçen yakla mlar, önceden
belirlenen noktalarda
çok
ayr nt
program
soyutlamalar hesaplar ve oldukça pahal r. Jones,
Harrold ve Staska [13], hatalar n olas nedenlerini
bulmak için, deyim kapsam bilgisini (statement
coverage information) kullan r. Chen ve di erleri [6],
hesaplamalarda kullan lan yaz m bile enlerini,
problemlerin kayna
bulmak için kullan r.
2.2. Veri Toplama Ek Yükünü Azaltma
Di er ara rmac lar, ölçüm ayg tlar ek yükünü
tlamak için önceki yakla mlar iyile tirme yoluna
ba vurmu tur. Liblit ve di erleri [16,17], kullan dan
toplanan yürütme verisini etkili bir ekilde örneklemek
için yaz m sistemlerinin kaynak koduna ölçüm
ayg tlar eklerler. Fakat, bu örnekleme yakla
,
önemli bir ekilde sistem kodunun büyüklü ünü ve
sistemin bellek gereksinimini art r. Ek olarak,
örnekleme sonucu toplanan veride olu an gürültü,
ancak çok fazla miktarda gerçekle en gözlemlerle
kompanse edilmelidir ki bu baz uygulamalar için olas
de ildir. Haran ve di erleri [11], birçok s ftan birine
ait olarak yürütme verisini s fland rmak için teknikler
geli tirmi tir. Her teknik, sahada çal an program
kopyalar n belirli bir k sm na ölçüm ayg yerle tirir
ve ölçüm ayg tlar n yeri her bir program kopyas için
farkl k gösterir. Dolay yla, her bir yürütmeden
toplanan veri gerçek program tayf n sadece küçük bir
alt kümesini yakalar. Amaç, do ru s fland rmaya izin
verecek yeterli bilgiyi yakalayan birle tirilmi bir veri
kümesi yaratmakt r. Y lmaz ve di erleri, “Time Will
Tell” [24] isimli çal mada ili kili bir yakla m
sunmaktad r. Bu çal mada zaman tayf
(metod
yürütme zamanlar n izi) toplamak için minimum
miktarda yaz m ölçüm ayg kullan lm ve deneysel
olarak zaman tayf n etkili bir ekilde yürütmelerdeki
desenleri yakalayabilece i gösterilmi tir.
2.3. Donan m Sayaçlar Tabanl Program Tayflar
Ek yük maliyetini dü ürmenin bir di er yoluda, tüm
program tayf
donan m seviyesinde toplamakt r.
Anderson ve di erleri [2], tamamen donan m
performans sayaçlar ile yap lan ve az masrafl olan bir
performans sorunlar
belirleme tekni ini önermi tir.
Bu teknik, program çal rken donan mda rasgele
kesintiler yarat p, donan m sayaçlar n de erlerini
yakalar. Bu bilgiler daha sonra program n en çok
zaman harcad kod segmentlerini bulmada kullan r.
Deneysel çal malar, programlar n yeteri kadar uzun
yürütüldü ü varsay rsa, önerilen yöntemde veri
toplamak için gerekli olan ek maliyetin %5’in alt nda
kalaca
öngörmektedir.
Bu çal madaki soruya aç k olan nokta; bahsi geçen
yöntemle toplanan program tayf n, performans
analizi d nda ba ka analiz türleriyle birlikte kullan p
kullan lamayaca
r (bu makalede elde edilmeye
çal lan fonksiyonel analiz türü gibi). Bu tereddütün
temel kayna ise, bahsi geçen yakla mda, toplanan
verilerle programlar n kaynak kodlar
e le tirme
eklini kontrol alt na alacak bir yolun olmamas r.
Genel olarak, program yürütmelerinden oldukça detayl
bilgi toplanmas neredeyse her zaman mümkündür, ki
bu ba ar yürütmeleri ba ar zlardan ay rmak için
önerilmi
ve yukar da k saca özetlenen baz
çal malarda hayata geçirilmi tir. Fakat, bu tür verileri
toplamak için gerekli olan ek yürütme zaman yükü,
bu tür yakla mlar kullan z bir hale getirmektedir.
Bu makalenin amac ; ek yürütme zaman yükü ve
fland rma ba ar
aras nda verimli bir nokta
bulmakt r.
3. Donan m Ve Yaz m Ölçüm Ayg tlar
Birle tirme
Bu makale, ba ar z program yürütmelerini ba ar
olanlardan ay rt etmek için (program yürütmelerini
fland rmak için), hem etkili hem de dü ük masrafl
bir yakla m öneriyor ve önerilen yakla
deneysel
olarak de erlendiriyor. Önerilen yakla
n temelini
donan m performans sayaçlar
kullanmak suretiyle
veri toplama i ini olabildi ince donan ma gömülmesi
olu turmaktad r.
Donan m performans sayaçlar bir i lemci üzerinde
meydana gelen çe itli olaylar kaydeden i lemcinin
içine gömülmü sayaçlard r. Günümüzde, hemen
hemen bütün genel amaçl M B’ler, yürütülen komut
say , al nan dal say , önbelleklerde meydana gelen
isabetsizlik ve ba ar say lar gibi olaylar kaydetme
yetisi olan çok say da performans sayaçlar
içermektedir.
Bu sayaçlar aktif hale geçirmek için, say lacak olan
olaylar n tipi ve sayma i leminde kullan lacak olan
fiziksel sayaçlar M B’e bildirilir. Aktif hale
geldiklerinde, donan m sayaçlar ilgili olaylar sayar ve
bir küme özel amaçl yazmaçta (register) sayaç
de erlerini depolar. Bu yazmaçlar program yürütmeleri
esnas nda okunabilir ve s rlanabilirler.
Bu çal ma esnas nda kar la lan ilk sorun, donan m
sayaçlar n farkl süreçler (processes) taraf ndan
yay nlanan komutlar ay rt edememesi olmu tur. Bu
zorlu un üstesinden gelmek için süreç ba na donan m
olaylar
takip edebilen sanal donan m sayaçlar
kullan ma sunan ve perfctr (linux.softpedia.com)
olarak adland lan bir Linux çekirde i sürücüsü
kullan lm r.
Kar la lan ikinci bir sorun ise; donan m performans
sayaçlar n, yürütülmekte olan programlar hakk nda
rl bilgiye sahip olmas r. Örne in, donan m
sayaçlar , say lan bir komutun hangi program
fonksiyonuna ait oldu unu bilmezler. Dolay yla,
Bölüm 5.1’de daha detayl bir ekilde anlat ld uzere,
ham donan m tayflar (donan m sayaçlar ndan elde
edilen program tayflar ), yürütmeleri s fland rmada
kullan
olamayacak kadar kalitesizdir. Bu
olumsuzlu un etkisini azaltmak için, önerilen
yakla m, donan m sayaçlar n de erlerini fonksiyon
ça mlar yla
ili kilendirir.
li kilendirmelerin
yap labilmesi için, sayma i lemleri esnas nda hangi
fonksiyonun aktif oldu u bilgisi, geleneksel yaz m
ölçüm ayg tlar (software instrumentation tools)
kullan larak elde edilir. Bu çal mada, ili kilendirmeler
fonksiyonlar baz nda yap lsa da, önerilen yakla m,
daha çe itli ili kilendirme teknikleriyle de çal abilir.
Önerilen yakla m kabaca u ekilde özetlenebilir: 1)
yürütmenin ba nda ilgilenilen donan m sayac aktif
hale getirilir, 2) her fonksiyon ça
n ba nda ve
sonunda donan m sayac n de eri okunur ve aradaki
fark fonksiyon ça
yla ili kilendirilir, 3) yürütmenin
sonunda donan m sayac pasif hale getirilir.
Deney platforumunda yap lan bir çal ma, donan m
sayaçlar n de erlerinin 45 saat dönü ünde (45 clock
cycle) yap ld
göstermi tir. Donan m sayaçlar n
okunmas çok h zl olsa da, ödenmesi gereken ek
yürütme süresi yükü (runtime overhead) ayn zamanda
donan m sayaçlar n kaç kere okundu una da ba
r.
Dolay yla, veri toplama masraf daha da azaltmak
için, bu çal ma, 50 kerenin üzerinde ça lm
fonksiyonlarla, direkt ya da endirekt olarak 50’nin
üzerinde ça rma yapan fonksiyonlar monitör
etmemektedir. Bu kesme de eri, deneyler esnas nda
kobay yaz mlardan elde edilen veriler kullan larak,
monitör edilmesi gerekecek fonksiyon ca lar n
say
azaltacak ekilde elde edilmi tir. Burada dikkat
edilmesi gereken husus, donan m sayaçlar yürütme
süresince aktif oldu u için, monitör edilmeyen
fonksiyonlar n
(unprofiled
functions)
sayaç
de erlerinin, monitör edilen fonksiyonlar (profiled
functions) taraf ndan so ruldu udur.
Bu çal ma ayn zamanda programlar n kendi hatalar
tespit etti i zamanlarda ça rd klar fonksiyonlar
(error(...) ve fatal(...) gibi), yap lan analizlerin d nda
tutar. Bu tür fonksiyonlar, olu an hatalar n bir sonucu
olarak ca ld klar için, hatalar n kök sebeplerinin
anla lmas nda (ki bu yürütmelerin s fland lmas yla
elde edilmek istenen sonuçlardan biridir) önem arz
etmezler. Makalenin geri kalan k sm nda, bu filtreleme
lemlerinin tamam na “genel fonksiyon filtrelemesi”
ad verilmi tir.
3.1. Basit Bir Fizibilite Çal mas
Donan m ve yaz m tayflar
kombine ederek elde
edilen hibrid tayflar, aç k bir ekilde sadece donan m
tayflar ndan elde edilebilecek bilgiden daha fazla bilgi
içerir. Ne var ki, donan m performans sayaçlar ndan
elde edilen ölçüm ayg tlar , programlanabilir yaz m
tabanl ölçüm ayg tlar na oranla daha az esnektir.
Dolay yla, hibrid program tayflar n yürütmeleri
fland rabilir nitelikte olup olmad klar aç k de ildir.
Basit bir test olarak, socket sistem ça
kobay
olarak
kullanan
bir
fizibilite
çal mas
gerçekle tirilmi tir. Socket fonksiyonu, ileti im için bir
makine komutu çal ran ba ar z ça lar n, socket
fonksiyonunun hemen ba lang nda yer alan ve
desteklenmeyen parametre de erlerini tespit edip, h zl
bir ekilde hata kodu dönen basit bir kontrolden
kaynakland
anla lm r. Ba ar ça lara oranla
daha fazla komut çal ran ba ar z ça lar n bu
davran lar n sebebi ise, hatalar olu duktan sonra
letim sistemi çekirde inin o ana kadar ayr lm olan
kaynaklar serbest b rakmas olarak belirlenmi tir.
Ba ar
ça larda, soketler için ayr lan kaynaklar
ancak soket kapat ld nda serbest b rak r.
Bu basit fizibilite çal mas n sonuçlar hiçbir ekilde
nihai olmamas na ra men, donan m sayaçlar
yard yla toplanan program tayflar n, ba ar z
yürütmelerin güvenilir bir ekilde ay rt edilmesinde
kullan labilece ine dair hipotezi destekler niteliktedir.
4. Deneyler
ekil 1: Ba ar
say
ve ba ar z ça
mlarda yürütülen komut
uç nokta yarat r. Bu fizibilite çal mas nda, socket
fonksiyonun girdi olarak ald
iki parametre
kullan lm r. Bu parametreler domain ve type’t r.
Domain parametresi ileti im alan belirler (INET ve
INET6 gibi). Type parametresi ileti imin türünü
belirler (ba lant temelli ve ba lant z gibi). Bu
parametreler s ras yla 11 ve 6 de ik de er al r.
Deneylede kullan lmak üzere tüm parametre
de erlerinin kombinasyonlar
içeren 66 tane test
girdisi olu turuldu. Her girdi kombinasyonu için,
fonksiyon yürütmesi esnas nda çal
lan makine
komutlar n
say
ölçüldü.
Tüm
girdi
kombinasyonlar , deneylerin çal
platform üzerinde
desteklenmedi i için, test girdilerinden 51 tanesi
ba ar z oldu.
ekil 1, elde edilen ölçümleri
özetlemektedir. Yatay eksen, çal
lan makine
komutlar n say
, dikey eksen ise, ba ar z ve
ba ar yürütmelerden elde edilen verilerle birlikte
toplanan bütün veriyi gösterir.
Bu basit donan m tayf kullan larak, talep edilen
soketin yarat lmas n ba ar z oldu u yürütmelerin
fland p s fland lamayaca sorguland . ekil
1’de de görülebildi i gibi, sadece bir tane donan m
sayac kullan ld halde, ba ar ve ba ar z ça lar
aras ndaki fark aç kt r; hatal ça lar, ba ar ça larla
yasland nda ya daha az ya da daha çok makine
komutu yürütmektedir. Elde edilen veriler üzerinde
otomatik bir s fland rma modeli olu turmak ve bu
modeli daha önceden görülmemi yürütmeler üzerinde
namak (Weka’n n J48 algoritmas
kullanarak),
hatal ça lar tahmin etmede 0.98’lik bir F-ölçüsü
sa lad .
Socket
fonksiyonunun
kodunun
incelenmesi
sonucunda, ba ar ça lara nazaran daha az say da
Ba ar z yürütmeleri ba ar yürütmelerden ay rmada
donan m
tayf n
ba ar
ve
etkinli ini
de erlendirmek için, dört aç k kaynak kodlu gerçek
uygulama üzerinde bir dizi deneyler yap ld .
4.1. Ba ms z De ken
Bu deneylerde bir tane ba ms z de ken kullan ld ;
program tayf tipi. Bu de ken alt farkl seviyeye
sahiptir. lk üç program tayf , donan m performans
sayaçlar kullanarak toplanm r.
TOT_INS: Yürütülen makine komutlar
sayar.
BRN_TKN: Al nan dallar sayar.
LST_INS: Bellek yükleme ve bellek depolama
komutlar (load and save) sayar.
Geriye kalan üç program tayf ise geleneksel yaz m
ölçüm ayg tlar kullan larak toplanm r.
CALL_SWT: Ça lan fonksiyon kümesini
kaydeder.
STMT_FREQ: Kaynak kod deyimlerinin kaç
kere çal
ld
sayar.
TIME: Fonksiyonlar n çal ma zamanlar
nano saniyeler seviyesinde ölçer.
Literatürde çok say da yaz m tabanl program tayf
önerilmi olmas na ra men, deneylerde sadece bu üç
tip tayf n kullan lmas n birçok sebebi vard r. lk
olarak, bahsi geçen her bir program tayf , literatürde
benzer amaçlar için ba ar bir ekilde kullan lm r
[24, 13, 21, 6]. kinci olarak, ek yürütme zaman yükü
aç ndan, bu tayflar n her biri çe itli program tayf
tiplerinin temsilcisidir. Örne in, CALL_SWT ve
STMT_FREQ tayflar n ek yürütme yükü, (s ras yla)
fonksiyonlar seviyesinde basit ve kaynak kod deyimleri
seviyesinde detayl veri toplayan tayflar için bir alt
r olarak görülebilir. Benzer ekilde, TIME tayf n
ek yürütme yükü, fonksiyonlar seviyesinde basit
yürütme verisi toplayan ve çe itli nedenlerden dolay
içerik de imi (context switch) gerektiren tayflar için
yaz m
grep
flex
sed
gcc
sat r
say
10068
10459
14427
fonksiyon
say
146
162
255
versiyon
say
5
19
15
toplam
testler
3050
11417
5455
ba ar
testler
2346
8399
4454
ba ar z
testler
704
3018
1001
222196
2214
1
7701
7494
207
Tablo 1: Deneylerde kullan lan kobay yaz mlar hakk nda bilgi
alt s r olarak de erlendirelebilir. Bu çal mada,
yürütme zaman
hesaplamak için sistem ca lar
kullan lm r.
4.2. Kobay Uygulamalar
Deneylerde dört tane aç k kaynak kodlu uygulama
kullan lm r. Bunlar grep, flex, sed ve gcc’dir. Geni
çapl bir kullan
taban olan bu uygulamalar
(s ras yla) bir deseni e leyen sat rlar yazar, h zl bir
ekilde sözdizimsel çözümleyici üretir, bir ak editörü
olarak metinleri dönü türür, C programlar
derler.
Tablo 1 bu uygulamalar için baz istatistikler içerir.
lk üç uygulama, SIR [9] ad verilen bir yaz m
hatalar ambar ndan al nm r. Bu ambar, bahsi geçen
uygulamalar n
çe itli
versiyonlar
ve
bu
versiyonlardaki bilinen hatalar derler. Deneylerde
kullan lan gcc uygulamas ise GNU Compiler
Collection versiyon 2.95.2’nin resmi sürümüdür.
Deneylerde, söz konusu olan bütün uygulamalar, kendi
test havuzlar ve test kahinleriyle (test oracles) birlikte
kullan lm r.
4.3. Operasyonel Model
Deneyleri gerçekle tirebilmek için, söz konusu
uygulamalar n test havuzlar ndaki bütün testler
çal
ld ve yürütmlerden program tayflar toplad .
Her bir yürütme için ek yük ölçüldü. Test havuzlar ile
birlikte gelen test kahinleri kullan larak her bir
yürütmenin ba ar veya ba ar z oldu unu belirlendi.
Program versiyonlar n ve program tayf tiplerinin her
kombinasyonu için, be katmanl çapraz do rulama
tekni i ile Weka’n n J48 s fland rma algoritmas
kullan larak s fland rma modelleri olu turuldu ve
de erlendirildi. Di er bir de le; elde edilen
modellerin de erlendirilmesi, önceden görülmemi
yürütmeler kullan larak gerçekle tirildi.
Ek yürütme zaman yükü, bir program n ölçüm ayg tl
çal ma süresiyle orijinal çal ma süresi aras ndaki
fark n, orijinal çal ma süresine bölünmesi ile
hesapland .
fland rma modellerinin ba ar
de erlendirmek
için ise, s kl kla kullan lan precision ve recall
ölçülerine e it a rl k verilmek suretiyle hesaplanan Fölçüsü kullan ld .
4.4. Deneysel Ayarlar
Fonksiyon ça lar yla donan m sayaç de erlerini
ili kilendirmede kullan lan yaz m ölçüm ayg tlar ,
GNU’nun C Extension Framework’ü kullan larak
geli tirildi. Ayn yöntem, TIME ve CALL_SWT
tayflar
toplamada da kullan ld . Öte yandan
STMT_FREQ tayf , GNU’nun gcov test kapsam arac
yard myla topland . Kapsam bilgisinin, sadece istenilen
fonksiyonlar ad na hesaplanabilmesi için gcov
uygulamas de tirilmi tir.
Ayr ca, ek yükü hesaplamak için gerekli olan yürütme
süreleri, nano saniye cinsinden ve K-best ölçüm
yöntemi [5] kullan larak elde edildi. Tüm deneyler
CentOS 5.2 i letim sistemi çal ran ve 2GB haf zaya
sahip olan bir Intel çift i lemcili makine üzerinde
gerçekle tirildi.
Deneylerde
kullan lan
veriler,
kobay
uygulamalar
n 39 kusurlu versiyonu üzerinde
çal
lan toplam 19,922 testten elde edilmi tir (Tablo
1). Bu 39 kusurlu versiyon, ba ar z yürütmelerin
ba ar yürütmelere oran n 0.05 ile 1.50 aras nda
olmas kriteri göz önünde tutularak toplam 166 kusurlu
versiyon kümesinden seçilmi tir. Bu kriterin
uygulanmas ndaki temel sebep ise, otamatik
fland rma problemlerinde, bir s
n di erinden
çok daha yayg n olmas durumunda, varolan
tekniklerin genellikle ya kusurlu olarak çal mas ya da
özel iyile tirmeye ihtiyaç duymas r. Bu makalenin
amac
s fland rma tekniklerini de erlendirmek
olmad
için, analizlerde sadece bahsi geçen kritere
uygun kusurlu versiyonlar kullan lm r.
5. Veri ve Analizi
zleyen bölümler elde edilen sonuçlar sunmakta ve
tart maktad r.
5.1. Donan m ve Yaz m Tabanl Program Tayflar
lk çal mada, sadece donan m ve sadece yaz m
tabanl
program tayflar
taraf ndan sa lanan
fland rma ba ar ve ek yük incelendi. Donan m
tabanl tayflar elde etmek için, ilgili donan m sayac
aktif hale getirildi ve bu sayac n de eri yürütmenin
ba nda ve sonunda olmak üzere toplamda sadece iki
defa okunup, aradaki fark yürütmeyle ili kilendirildi.
Bu deney setinde ölçülen ek yük de erleri, Tablo 2’de
yürütme tabanl ili kilendirme sat rlar ndan okunabilir.
Bu sat rlardaki ‘-’ karakteri, kar k gelen deneyin
amaçlara uygun olmad için yap lmad
ifade eder.
Yaz m tabanl tayflar toplamak içinse, genel
fonksiyon filtresi aktif hale getirildi ve filtrelenmemi
her fonksiyon için gerekli veri yürütmelerden topland .
yaz m
grep
yürütme
fonksiyon
flex
yürütme
fonksiyon
sed
yürütme
fonksiyon
CALL_SWT
STMT_FREQ
TIME
TOT_INS
BR_TKN
LST_INS
0.0112
0.0763
0.0821
0.0031
0.0125
0.0036
0.0125
0.0037
0.0132
0.0152
0.1303
0.2448
0.0060
0.0169
0.0058
0.0168
0.0060
0.0167
0.0192
0.2701
0.2278
0.0075
0.0152
0.0096
0.0152
0.0083
0.0161
Tablo 2: Ek yürütme zaman yükleri
Bu deney seti için gözlemlenen ek yük de erleri, Tablo
2’de
fonksiyon
tabanl
ili kilendirme
sat rlar ndanokunabilir. Deneylerde, genel fonksiyon
filtresinin monitör edilmesi gereken fonksiyon
ça lar n say
ortalama olarak %98 oran nda
azaltt gözlemlendi.
Tablo 2’nin son üç sütunu, donan m tabanl tayflar n
sebebiyet verdi i ek yükleri göstermektedir. Bu
tablodan da anla laca üzere, donan m tayflar
toplaman n ek yükü 0.0031-0.0096 aral nda
olmu tur. Di er bir de le, sadece donan m
performans sayaçlar n aktive edilmesinin getirdi i ek
yük %1’in alt ndad r. Tablo 2’nin ilk üç sütunu ise,
yaz m tabanl tayflar taraf ndan kaynaklanan ek yükü
göstermektedir. Ça lan fonksiyonlar n listesini
kaydeden CALL_SWT tayf , yakla k olarak %1-%2
aral nda bir ek yüke sebebiyet vermi tir. Geriye kalan
yaz m tabanl tayflar n ek yükü ise, yakla k olarak
%7.6-%27 aral ndad r.
ekil 2 ise, bu çal mada elde edilen s fland rma
ba ar
n F-ölçümlerini sergilemektedir. Bu ekildeki
her kutu, bir tayf tipinden elde edilen F-ölçümlerinin
da
gösterir. Kutular n en alt ve en üst kenarlar ,
toplanan verilerin birinci ve üçüncü kartillerini
göstermektedir. Kutular n içindeki yatay çubuklar
ortanca de erleri, içi dolu daireler ise ortalama
de erleri ifade etmektedir. Ortalama de erler ayn
zamanda kutular n alt nda say ile verilmi tir.
ekilden de anla laca üzere, donan m tayflar n, az
masrafl
olmalar na
ra men
yürütmeleri
fland rmada etkili olmad klar gözlemlendi. Bu
tayflardan olu turulan s fland rma modelleri sadece
0.46’l k bir F-ölçümüyle hatal yürütmeleri tahmin
edebildi. Öte yandan, yaz m tayflar ndan elde edilen
F-ölçümlerinin genellikle daha yüksek oldu u
görülmektedir. F-ölçümlerinin ortalama de eri,
CALL_SWT için 0.58, TIME için 0.78 ve
STMT_FREQ için 0.83’tür. Sonuç olarak, donan m
sayaçlar ndan elde edilen tayflar n, az masrafl fakat
fland rmada ba ar z oldu u gözlemlendi. Yaz m
tayflar içinde bir tek CALL_SWT tayf , hem göreceli
olarak az masrafl hem de göreceli olarak makul
fland rma ba ar na sahipti. Geriye kalan yaz m
tayflar daha ba ar fakat çok daha fazla masrafl yd .
ekil 2: Donan m ve yaz m tabanl tayflar n s
ba ar
fland rma
5.2. Fonksiyon Ça lar le Veriyi li kilendirme
Yap lan ikinci çal ma, ölçüm ayg tlar n ek yükünü
rland rken s fland rma ba ar
art rmak için,
donan m ve yaz m ölçüm ayg tlar
birle tirmeyi
hedeflemektedir.
Buradaki
fikir,
donan m
sayaçlar ndan elde edilen veriyi belirli program
eleriyle ili kilendirmektir.
Bu fikri s namak için deney prosedürlerinde birçok
de iklik yap lm ve daha sonra önceki çal ma tekrar
edilmi tir. lk de iklik, fonksiyon ça lar yla
donan m sayaçlar ndan gelen verileri ili kilendiren
yaz m tabanl ölçüm ayg tlar kullanmak olmu tur.
Geli tirilen ayg tlar, ilgilenilen fonksiyon ça lar n
ba nda ve sonunda takip edilen donan m sayac n
de erini okuyarak, aradaki fark fonksiyon ça
ile
lemektedir. Bir yürütmeden toplanan hibrid program
tayf , bir sayaç de erleri vektörü olarak dü ünülebilir.
Bu vektördeki her bir de er, kar k gelen fonksiyonun
içinde toplamda (bütün yürütme boyunca) kaç tane
gözlemlenen donan m olay n meydana geldi ini ifade
eder.
CALL_SWT
F-ölçüsü
ek yük
0.59
0.0136
Tablo 3: gcc için s
ekil 3: Yaz m tabanl ve hibrid tayflar n s
ba ar
fland rma
Tablo 2’nin son üç sütununda, fonksiyon tabanl
ili kilendirme sat rlar olarak i aretlenen veriler, bu
çal mada gözlemlenen ek yükü ifade etmektedir. Bu
tablodan da görülece i üzere, hibrid yaz m ve
donan m yakla
ndan kaynaklanan ek yük, %1,25%1,50 aral ndad r.
Donan m tabanl tayflar
toplaman n ek yükü bir önceki çal maya göre 2-4 kat
aras artsa da, bu ek yük ço u geleneksel yaz m
tayf n ek yüküne oranla çok daha azd r (Tablo 2).
ekil 3’te elde edilen F-ölçümleri görülmektedir. lk
gözlemlenen sonuç, fonksiyon ça lar yla donan m
sayaçlar n
ili kilendirilmesinin
s fland rma
ba ar
önemli ölçüde art rd
r. F-ölçümü bir
önceki çal maya göre 0.46’dan 0.85’e yükselmi tir.
yaslanabilir ek yük seviyeleri için, hibrid tayflar,
ba ar z yürütmeleri belirlemede yaz m tayflar ndan
önemli bir ekilde daha iyi oldu u gözlemlenmi tir.
Örne in, ortalama ek yükün (%1,5) hemen hemen ayn
oldu u CALL_SWT tayf ile k yasland nda, hibrid
tayflar n s fland rma ba ar
daha yüksektir;
ortalama F-ölçümü CALL_SWT için 0.58 iken bu
de er hibrid tayflar için 0.85’tir.
Alternatif olarak, k yaslanabilir ba ar seviyeleri için,
hibrid tayflar önemli bir ekilde daha az masrafl
oldu u gözlemlenmi tir. Örne in, hibrid tayflar ve
STMT_FREQ tayflar benzer F-ölçümlerine sahipler;
ortalama F-ölçümü, STMT_FREQ ve hibrid tayflar
için s ras yla 0.83 ve 0.85’tir. Bununla birlikte hibrid
tayflar n ortalama ek yükü %1,5 iken, bu yük
STMT_FREQ tayf için %15,9’dur.
5.5 gcc le Yineleme
u ana kadar yap lan çal malarda orta büyüklükte
kobay uygulamalar kullan lm r. Bu çal mada ise,
önerilen yakla m çok daha büyük bir ugulama olan
STMT_FREQ
0.82
1.2424
fland rma ba ar
TIME
0.59
0.5766
TOT_INS
0.81
0.0138
ve ek yük
GNU derleyicisi (gcc v2.95.2) üzerinde denenmektedir.
Analizlerin gerçekle ebilmesi için, bahsi geçen
uygulamadan CALL_SWT, STMT_FREQ, TIME ve
TOT_INS tayflar topland ve bu tayflar ba ar ve
ba ar z yürütmeleri s fland rmak için kullan ld .
Deneylerde, derleyicinin sadece cc1 bile eni için veri
topland . Bu bile en gcc derleyicisinin çekirdek
bile enidir ve kaynak kodunu makine koduna
derlemekten sorumludur. Toplamda,
7701 test
çal
ld ve bu testlerden 207’si ba ar z olurken
7494’ü ba ar oldu.
Deneylerde ilk olarak genel fonksiyon filtreleme ad
gerçekle tirildi (bkz. Bölüm 3). Bu monitör edilmesi
gereken fonksiyon ça lar n say
%99 oran nda
azaltt . Önceki çal malarda da oldu u gibi, yaln zca
bir iç hata tespit edildikten sonra ça lan fonksiyonlar
da ay kland .
Tablo 3, bu çal mada gözlemlenen ek yükleri ve Fölçümlerini göstermektedir. Genelde bu sonuçlar,
önceki çal malarda kullan lan daha küçük çapl
uygulamalar üzerinde elde edilen sonuçlarla
uyumludur. Ek yük verisine bakarak, bu çal mada
TOT_INS tayf n ek yükü di er çal malarda elde
edilen maliyetlere benzerken, STMT_FREQ tayf n
son derece daha yüksek bir ek yüke sahip oldu u
görülmektedir. Manüel yap lan bir çal ma sonucunda,
ek yükteki sapmalar n bir nedeninin, gcc
uygulamas n, di er uygulamalara k yasla fonksiyon
ça
ba na daha fazla komut çal rmas oldu u
anla lm r.
Tablo 3’ten de görülece i üzere, TOT_INS tayf ,
STMT_FREQ tayf na göre, benzer s fland rma
ba ar
çok daha az masrafl bir
ekilde
gerçekle tirmi tir. TOT_INS tayf için ortlama Fölçümü 0.81 ve ortalama ek yük %1,4 iken, ayn
de erler STMT_FREQ tayf için s ras yla 0.81 ve
%124’tür. Alternatif olarak, ek yük maliyetinin benzer
oldu u (%1,4 civar nda) CALL_SWT tayf ile
yasland nda, TOT_INS tayf çok daha iyi bir
fland rma
ba ar
göstermi tir;
F-ölçümü
TOT_INS için 0.81 iken CALL_SWT için sadece
0.59’dur.
6.Sonuç
Birçok ara rmac , program tayflar ndan yaz m
sistemlerinin davran sal özelliklerini belirlemenin
yollar üstünde çal
r. Bu konuda yap lan
çal malardan al nan sonuçlar ümit vericidir [24, 13,23,
22, 12, 18, 15]. Fakat, önerilen yakla mlar n ek yük
masraflar üzerinde çok durulmam r. Bu makale,
program yürütmelerini güvenilir ve etkili (az masrafl )
bir ekilde s fland rmak için yeni bir yöntem
önermi tir. Bu yakla m, dü ük ek yük masrafl
donan m tayflar , az say da ama daha yüksek masrafl
yaz m ölçüm ayg tlar yla birle tirmektedir. Önerilen
yakla m di er temsili yakla mlarla kar la rmal
olarak deneysel yöntemlerle s nanm r.
Tüm deneysel çal malar n iç ve d geçerlili ine
ili kin tehlikelerden muzdarip oldu unu hat rlatmakta
fayda
vard r.
Bu
çal man n
sonuçlar n
genelle tirilme yetisini k tlad
için, d geçerlili e
ili kin tehlikeler daha fazla önem arz etmektedir. Bir
tehlike, deneylerde kullan lan kobay uygulamalar n
temsil edilebilirlili i ile ilgilidir. Kobaylar n tümü
gerçek uygulamalar olmas na ra men, bu kobaylar
sadece dört veri noktas temsil ederler. Alakal ba ka
bir tehlike ise, deneylerde kullan lan hatalar n temsil
edilebilirlili i ile ilgilidir. Grep, flex ve sed
uygulamalar literatürdeki pek çok benzer çal ma
taraf ndan s kl kla kullan lm
olmas na ve gcc
uygulamas çok kullan lan bir derleyici olmas na
ra men, bu uygulamalardaki hatalar, bütün potansiyel
hatalar n sadece k tl bir alt kümesini temsil eder.
Bu k tlamalar ak lda tutarken, elde edilen deney
sonuçlar n, temel hipotezimizi destekledi ine
inanmaktay z: Hibrid program tayflar , dü ük ek
yürütme zaman yüküne sahip oldu u halde, ba ar z
program yürütmelerini, ba ar
yürütmelerden
güvenilir bir ekilde ay rt etme yetisine sahiptir.
Önerilen yönteminin orijinal ve ilginç oldu una
inan yoruz. Bu nedenle, hibrid donan m ve yaz m
tayflar n, hata yerini saptama, hata tahmini, güvenlik
güvencesi gibi çe itli yaz m kalite güvence
yakla mlar nda, program yürütmlerini soyutlama
mekanizmas olarak kullanmay planl yoruz.
7. Onaylar
Bu ara rma 7. Avrupa Birli i Çerçeve Program
içerisinde Marie Curie International Reintegration
Grant
(FP7-PEOPLE-IRG-2008),
TÜB TAK
(109E182) ve US NSF (CCF-0811284) taraf ndan
desteklenmi tir.
8. Kaynaklar
[1] H. Agrawal, J. Horgan, S. London, and W. Wong. Fault
localization using execution slices and dataflow tests. In
ISSRE Conference Proceedings, 1995.
[2] J. M. Anderson, L. M. Berc, J. Dean, S. Ghemawat, M. R.
Henzinger, S.-T. A. Leung, R. L. Sites, M. T.
Vandevoorde,C. A. Waldspurger, and W. E. Weihl.
Continuous profiling: where have all the cycles gone? ACM
Trans. Comput. Syst.,15(4):357{390, 1997.
[3] J. F. Bowring, J. M. Rehg, and M. J. Harrold. Active
learning for automatic classification of software behavior. In
Proc. Of the Int'l Symp. on Software Testing and Analysis
(ISSTA 2004), sayfalar 195-205, Temmuz 2004.
[4] Y. Brun and M. D. Ernst. Finding latent code errors via
machine learning over program executions. In Proc. of the
Int'l Conf. on SW Eng. (ICSE 2004), sayfalar 480-490, 2004.
[5] R. E. Bryant and D. R. O'Hallaron. Computer Systems:
AProgrammer's Perspective. Prentice Hall, 2002.
[6] M. Y. Chen, E. Kiciman, E. Fratkin, A. Fox, and E.
Brewer. Pinpoint: Problem determination in large, dynamic
internet services. Dependable Systems and Networks,
InternationalConference on, 0:595-604, 2002.
[7] W. Dickinson, D. Leon, and A. Podgurski. Pursuing
failure: the distribution of program failures in a profile space.
In Proc. Of the 9th ACM SIGSOFT international symposium
on Foundations of Soft. Eng., sayfalar 246-255, Eylül 2001.
[8] W. Dickinson, D. Leon, and A. Podgursky. Finding
failures by cluster analysis of execution profiles. In Proc. of
the Int'l Conf. on Soft. Eng., sayfalar 339-348, 2001.
[9] H. Do, S. Elbaum, and G. Rothermel. Supporting
controlled experimentation with testing techniques: An
infrastructure and its potential impact. Empirical Soft. Eng.,
10(4):405-435, 2005.
[10] M. Hall, E. Frank, G. Holmes, B. Pfahringer, P.
Reutemann, and I. H. Witten. The weka data mining
software.SIGKDD Explorations, 11(1):10-19, 2009.
[11] M. Haran, A. Karr, A. Orso, A. Porter, and A. Sanil.
Applying classification techniques to remotely-collected
program execution data. SIGSOFT Softw. Eng. Notes,
30(5):146-155, 2005.
[12] G. Hoglund and G. McGraw. Exploiting software: How
to break code. Addison-Wesley Publishing Company.
[13] J. A. Jones, M. J. Harrold, and J. Stasko. Visualization
of test information to assist fault localization. In ICSE
Conference Proceedings, sayfalar 467-477, 2002.
[14] D. Leon, A. Podgurski, and L. J. White. Multivariate
visualization in observation-based testing. In ICSE, sayfalar
116-125, 2000.
[15] B. Liblit, A. Aiken, A. X. Zheng, and M. I. Jordan. Bug
isolation via remote program sampling. SIGPLAN Not.,
38(5):141-154, 2003.
[16] B. Liblit, A. Aiken, A. X. Zheng, and M. I. Jordan. Bug
isolation via remote program sampling. In PLDI, sayfalar
141-154, 2003.
[17] B. Liblit, M. Naik, A. X. Zheng, A. Aiken, and M. I.
Jordan. Scalable statistical bug isolation. In PLDI, 2005.
[18] A. Podgurski, D. Leon, P. Francis, W. Masri, M. Minch,
J. Sun, and B. Wang. Automated support for classifying
software failure reports. In ICSE, sayfalar 465-475, 2003.
[19] A. Podgurski, D. Leon, P. Francis, W. Masri, M. M.
Sun, and B. Wang. Automated support for classifying sw
failure reports. In ICSE 2003, sayfalar 465-474, May s 2003.
[20] M. Renieris and S. P. Reiss. Fault localization with
nearest neighbor queries. In ASE Conference Proceedings.
[21] R. Santelices, J. A. Jones, Y. Yanbing, and M. J.
Harrold. Lightweight fault-localization using multiple
coverage types. In ICSE, sayfalar 56-66, 2009.
[22] S. Singer, K. Gross, J. Herzog, S. Wegerich, and W.
King. Model-based nuclear power plant monitoring and fault
detection: theoretical foundations. In Proceedings of the
International Conference on Intelligent Systems Applications
to Power Systems, sayfalar 60-65, 1997.
[23] R. Vilalta and S. Ma. Predicting rare events in temporal
domains. In ICDM Proceedings, sayfalar 474-481, 2002.
[24] C. Yilmaz, A. Paradkar, and C. Williams. Time will tell:
fault localization using time spectra. In ICSE, 81-90, 2008.