Testing software systems almost always involve sampling enormous variability spaces, such as input and configuration spaces, and testing representative instances of a system's behavior. This sampling is commonly performed with techniques collectively referred to as combinatorial interaction testing (CIT). These techniques typically have two inputs: configurations spaces and coverage crieteria. Configuration space contains all valid option-value
combinations (configurations). On the other hand coverage criteria defines all valid combinations which needs to be tested. Under given configuration space and coverage criteria, an CIT object is computed as an output. This CIT object which contains a sample of a subset of configuration space, is computed as “costeffectively” and have full coverage under the given coverage criteria. After CIT objects are computed, quality assureance for software systems is done only testing chosen configurations. Our main goal in this work is further exploit the benefits of CIT to improve the efficiency, effectiveness and applicibilty of CIT approaches in practial scenarios by enabling practitioners to define their own space for testing as well as their own coverage criterion (thus enabling them to invent their own application-specific CIT objects). The proposed techinque in this work contains methods to compute a CIT object under given configuration space and coverage criteria. This approach will be referred as Unified Combinatorial Interaction Testing (U-CIT) in the rest of the paper. To this end, this requires truly flexible CIT approaches. In this work, we would like to develop tools for practitioners to define their own application-specific variability space as well as their own application. 1
Günümüz yazılım sistemleri; kullanıcı girdileri, konfigürasyon parametreleri ve iş
parçacıkları etkileşimleri (thread interleavings) gibi test edilmesi gereken bir çok
değişkenlik parametresine sahiptir. Bu değişkenlik parametreleri son kullanıcılar için
esneklik sağlarken yazılım geliştirenler için yazılımların kalite güvencesinin sağlanması
noktasında ciddi sıkıntılara sebebiyet verir. Küçük çaptaki yazılımlar için dahi tüm
değişkenlik uzayının test edilmesi genellikle mümkün değildir. Örneğin; Apache
sunucusunun bir sürümü son kullanıcılar tarafından yapılandırılabilen 172 konfigürasyon
parametresine ve bu parametrelerle oluşturulabilecek 1,8x1055 farklı konfigürasyona
sahiptir [
Bu ve benzeri sebeplerden dolayı endüstriyel sistemlerin test edilmesi nerdeyse
her zaman çok büyük bir değişkenlik uzayından (ki bu tür uzaylar dokümanın geri
kalan kısmında konfigürasyon uzayları olarak adlandırılacaktır) örnekleme yöntemiyle
seçilen ve tüm uzayı temsil kabiliyetine sahip olduğu düşünülen bir alt uzay
kullanılarak gerçekleştirilir. Pratik hayatta bu örnekleme işlevi genellikle Kombinezon
Etkileşim Sınama (KES) yöntemleri adı altında toplanmış teknikler kullanılarak
gerçekleştirilir [
İlk zamanlarda KES yaklaşımları sadece iki değer alan parametrelerin ikili ilişkilerini test etmek amacıyla kullanılıyordu. Daha sonra pratisyenler (örn. yazılım mühendisleri) üç değer alan parametreler için kapsayan dizilere ve sonrasında ise karışık kapsayan dizilere; yani her parametrenin farklı sayıda değer alabileceği kapsayan dizilere, ihtiyaç duymuşlardır. Bu ihtiyaçları karşılayabilmek adına KES alanında yeni çalışmalar yapılmaya başlanmıştır. Bunları takiben yüksek kapsama kuvvetine sahip kapsayan dizilerin icadı ise bu alanda yapılan bir başka yeniliktir. Ayrıca karışık kapsama kuvvetine (variable strength) sahip kapsayan dizilerde, yani farklı parametrelerin kendi aralarında farklı kapsama kuvvetlerine sahip olmaları, gün geçtikçe popüler olmaya başlamıştır. Bu alanda getirilen her yenilik “geleneksel olmayan” bu objeleri “geleneksel” hale getirebilmek için bunları üretebilecek ve hesaplayabilecek yeni algoritmaların araştırılmasına ve geliştirilmesine sebep olmuşlardır. Başka bir deyişle, KES alanında yapılan bütün çalışmalarda izlenen yöntem şu şekilde özetlenebilir: araştırmacılar sahadaki test senaryolarını desteklemek için özgün konfigürasyon uzayı modelleri ve/veya özgün kapsama kriterleri tanımlar, bu kriterleri sağlayacak özgün KES objeleri icat eder ve bu objeleri hesaplayacak özelleştirilmiş yöntemler geliştirir. Sahadaki pratisyenler ise geliştirilen KES objelerini kullanmak suretiyle yazılım sistemlerini test eder. Biz KES’in faydalarını “geleneksel olmayan” konfigürasyon uzaylarını “geleneksel olmayan” kapsama kriterleri kullanarak daha da ileriye götürebileceğimize inanıyoruz. Fakat bu düşünce ancak gerçekten esnek KES yaklaşımları ile mümkün olabilir. Bu nedenle, eğer pratisyenlerin kendi uygulamalarına özel konfigürasyon uzaylarını ve kapsama kriterlerini tanımlamaya olanak sağlayan araçlar olsaydı, KES’in esnekliği arttırılarak pratik hayatta uygulanabilirliğinin daha da arttırabileceğine inanıyoruz.
Bizim bu çalışmamızda sunmuş olduğumuz yaklaşımın amacı ise bu anlatmış
olduğumuz akışı tersine çevirmek suretiyle KES yaklaşımlarının “geleneksel olmayan”
konfigürasyon uzaylarında “geleneksel olmayan” kapsama kriterleri ile kullanılmasına
olanak sağlamak suretiyle KES yaklaşımlarının verimliliklerini, etkinliklerini ve
sahadaki uygulanabilirliklerini önemli ölçüde artırmaktır. Diğer bir deyişle; bu
çalışmamızda önermiş olduğumuz yaklaşım sayesinde araştırmacıların yeni KES objeleri icat
etmek suretiyle pratisyenlere neyin test edilmesi gerektiğini dikte ettirmeleri yerine
pratisyenlerin, kendi ihtiyaçları doğrultusunda özelleştirdikleri özgün KES objeleri
tanımlamaları (diğer bir deyişle icat etmeleri) sağlanacaktır ki dokümanın geri kalan
kısmında bu yaklaşım Birleştirilmiş Kombinezon Etkileşim Sınama Yöntemi (B-KES)
olarak adlandırılmıştır (Unified Combinatorial Interaction Testing) [
Makalenin 2. bölümünde B-KES’i genelleştirmek adına daha resmi tanımlarla anlatıyoruz. 3. bölüm KES alanında yapılan çalışmalar ile ilgili literatür özeti veriyor. 4. bölümde ise B-KES’in önemini anlatmak üzere örnekler verip aynı zamanda pratik hayatta B-KES’e duyulan ihtiyacı anlatıyoruz. 5. bölümde B-KES objeleri hesaplayabilmek için açgözlü (greedy) bir algoritma anlatıyoruz. Son olarak 6. bölümde ise sonuç kısmını veriyoruz. 2
Bu bölümde B-KES’i daha resmi bir şekilde anlatıp genelleştirmek adına aşağıdaki tanımları kullanıyoruz. Her yazılım sistemi için uygulanabilirliği farklı olduğundan tanımlar soyut bir şekilde verilmiştir.
Bir B-KES isterleri (requirements): Bir B-KES isteri kısıtlarla ifade edilmiş birimlerdir.
Bir B-KES test durumu: Bir B-KES test durumu birlikte test edilebilen isterler kümesidir. Başka bir deyişle; birlikte tatmin edilebilir (satisfiable) kısıtlar kümesidir. Fakat, tüm isterler kombinasyonları pratik hayatta her zaman geçerli olmayabilir.
Bir B-KES uzay modeli: Bir B-KES uzay modeli tüm geçerli B-KES isterlerini kapalı bir şekilde tanımlayan kısıtlardan ve geçerli B-KES test durumlarından oluşan sistemdir.
Bir B-KES kapsama kriteri: Bir B-KES kapsama kriteri kapsanması istenen B-KES isterlerini kapalı bir şekilde tanımlayan kriterdir.
Genel bağlamda, B-KES girdi olarak bir sistem modellemesi alır. Bu modelleme tüm geçerli test durumları uzayını ve test edilmek üzere kapsanması gereken tüm olası isterleri ifade eden kapsama kriterinden oluşmaktadır. Çıktı olarak ise verilen test kriteri altında tam kapsama elde eden test durumlarından oluşan bir test havuzu verir.
B-KES’i birleşik bir yaklaşım yapan şey kapsanması gereken birimlerin, test
durumlarının ve test durumlarının üretileceği uzayın bir kısıt olarak ifade edilmesidir.
Sonuç olarak, B-KES üretme problemi aslında büyük ve ilginç bir kısıt çözme problemine
dönmektedir [
Bir kapsama kriteri aslında kısıtlar ile ifade edilmiş kapsanmak istenen birimlerin (hepsi birlikte olmak zorunda değil, grup halinde olabilir) oluşturduğu kümeyi tanımlar. Daha sonra, bu kısıtların minimum sayıda alt kümeleriyle oluşturulan; öyle ki alt kümedeki tüm kısıtlamaların kendi aralarında tatmin edilebilir ve bütün bu alt kümelerin birleştirilmesiyle tüm kısıt kümesi tekrar oluşturulabilen, bir B-KES objesi üretilir. Bu kısıtlardan oluşan her alt küme geçerli bir test durumuna karşılık gelir; yani birlikte test edilebilen birimleri kapsayan bir test durumu. Bu yüzden, tüm bu alt kümeler kullanılarak kapsama kriteri altında B-KES’i oluşturan test durumları (her bir alt küme bir test) üretilir. Yani başka bir deyişle kısıtlar kümesini minimum sayıda alt kümelere bölerek kendi aralarında tatmin edilebilir alt kümeler elde etmek, B-KES için test durumları üretmek problemiyle aynıdır. 3
Nie ve Leung [
Literatürde yer alan ve yukarıda özetlenen bu çalışmaların amacı geleneksel
kapsayan dizileri hesaplamaktır. Farklı türde özgün kapsayan diziler olan T-KAD, M-KAD
ve TM-KAD’ları üzerine de ayrıca çalışmalar yapılmaktadır. Literatürde, yakın
geçmişteki bir yayınımız [
Bu bölümde verilmiş tüm çalışmaların esas amacı özelleştirilmiş bir KES alanında,
etkili ve/veya verimli bir şekilde KES objesi üretmektedir. Öte yandan B-KES’in amacı
ise bunların hepsini üretebilecek yetenekte olmak ve son kullanıcılar tarafından
belirlenmiş kapsama kriteri kullanılarak daha kompleks yapıda test havuzları oluşturmaya
olanak sağlamaktır. Buna ilk adım olarak daha önce sunmuş olduğumuz çalışmamızda
bu amacımıza ulaşabilmek için bir kısıt probleminden bahsetmiştik [
Bir KES objesi olan kapsayan diziler bu alanda test havuzu olarak sıklıkla kullanılan objelerdir. Fakat buna rağmen bu objelerin esneklikleri kısıtlıdır. Diğer bir deyişle bu objeler sadece bir tür konfigürasyon uzayı ve sadece bir tür kapsama kriteri kabul eder. Örneğin; kapsayan diziler için konfigürasyon uzayı sonlu değerler alabilen konfigürasyon parametrelerinden oluşur ve her konfigürasyonda her bir parametre geçerli bir değer almak zorundadır. Sahadaki ihtiyaçlar bu modele uymuyorsa geleneksel kapsayan dizilerden yararlanılamayabilir ya da bu dizilerin gelişi güzel kullanılması sonucunda sistemlerdeki hatalar yeterince etkili ve verimli bir şekilde tespit edilemeyebilir.
Örneğin; test edilmesi gereken sistemin yüksek seviyede yapılandırılabilir bir
sistem olduğunu varsayarsak, bu sistemi test etmek için t li bir geleneksel kapsayan dizi
hesaplandıktan sonra seçilen konfigürasyonlarda sistem için yazılmış olan bir dizi test
durumunun koşturulması gerektiğini, fakat her test durumunun her konfigürasyonda
test durumuna özel bir takım kısıtlardan dolayı çalışamadığını varsayalım. Bu
senaryoda geleneksel kapsayan dizilerin kullanılması maskeleme etkileri olarak adlandırılan
ve test edilmemiş parametre değerleri kombinasyonu ve test durumları ikililerini test
edilmiş gibi göstermek suretiyle yazılım sınama süreçlerine zarar veren etkilerin
oluşmasına sebebiyet verecektir [
Bu iddialarımızı daha net bir şekilde gösterip B-KES’in esnekliğini daha detaylı gösterebilmek için 2 tane örnek sunuyoruz.
Örnek 1: Şekil 1’de verilmiş olan sistem daha önce kullanmış olduğumuz yapılandırılabilirlikleri yüksek ve sıklıkla kullanılan bir veritabanı yönetimi sistemi olan MySQL ve bir HTTP sunucusu olan Apache yazılım sistemlerinden esinlenerek oluşturduğumuz örnektir. Bu örnekte, her biri 2 değer alabilen, D ve Y (Doğru ve Yanlış), sistem kurulmadan önce test edilmesi gereken 5 tane derleme zamanı konfigürasyon parametresi (p1, p2, p3, p4 ve p5) bulunmaktadır. Şekil 1’de bir örneği verildiği üzere, C ve C++ gibi ön işleme (preprocessing) gereken programlama dillerinde bu parametreler genellikle #ifdef gibi ön işlem direktifleri kullanılarak yazılmaktadır.
Şekil 1 iç içe geçmiş if durumlarını tanımlayan derleme zamanı konfigürasyon parametrelerinin birbirleriyle nasıl ilişkide olduğunu gösteren bir sistemi örneklendirmektedir. Bu tip sistemlerde pratisyenlerin sıklıkla kullanmayı tercih ettikleri yapısal kapsama sunan test yöntemlerinden birisi karar kavrama (KK) (decision coverage) kriteridir. KK kriterinde tam bir kapsama elde edebilmek için mümkün olan tüm kararlar için bütün sonuçların denenmesi gerekir. Örneğin, Şekil 1’de verilmiş olan iç içe geçmiş #ifdef bloklarında %100 KK kapsaması elde etmek için dıştaki kararın (p1 && p2 && p3) ve dıştaki bu karar ile korunmuş olan içteki kararın (p4 || p5) doğru ve yanlış olarak en azından bir kere test edilmeleri gerekir.
# i f d e f ( p 1 ) . . . # e n d i f # i f d e f ( p 2 ) . . . # e n d i f # i f d e f ( p 3 ) . . . # e n d i f # i f d e f ( p 4 ) . . . # e n d i f # i f d e f ( p 5 ) . . . # e n d i f # i f d e f ( p 1 & & p 2 & & p 3 ) . . .
# i f d e f ( p 4 | | p 5 ) . . .
# e n d i f Şekil. 1. Önişlemci direktifleri kullanılarak 5 tane ön derleme parametresinden oluşan varsayımsal bir sistem.
Ayrıca bir pratisyenin tam bir KK kapsaması elde etmek dışında tüm bu parametrelerin ikili ilişkilerini de test etmek istediğini varsayalım. Bunu yapmak için 2 li bir kapsayan dizisi (Şekilde 2’deki ilk beş sütun) hesaplanmış ve sonrasında bu kapsayan dizinin konfigürasyonları kullanılarak test edilmiştir. Başka bir deyişle, Şekil 2’deki ilk beş sütun Şekil 1’de verilmiş olan parametrelerin alabileceği değerleri göstermektedir. Son iki sütun ise #ifdef bloklarındaki iç içe geçmiş kararların sonuçlarını göstermektedir: doğru için ‘D’, yanlış için ‘Y’ ve eğer bir karar dıştaki karar tarafından korunduğundan dolayı hiç işlenemediyse ‘-’ kullanılmıştır. Fakat, Şekil 2’de verilmiş olan 2 li kapsayan dizisi Şekil 1’de verilmiş olan ilk beş #ifdef blokları için %100 KK kapsaması elde ederken, iç içe geçmiş #ifdef durumları için 4 ihtimalden sadece 3’ünü kapsayarak %75 KK kapsaması elde etmektedir. Kapsanmamış durum ise içteki kararın (p3 || p4) yanlış olarak hesaplanmasıdır. Bu durumun kapsanması sadece 5’li (p1=D, p2=D, p3=D, p4=Y, p5=Y) kombinasyonu kullanılarak mümkün kılınabilir.
p1 D D Y Y Y Y p2 Y D Y D D Y p3 Y D D Y D Y p4 D Y D Y D Y p5 Y D D Y Y D p1 ∧ p2 ∧ p3
Y D Y Y Y Y p4 ∧ p5 D Şekil. 2. Şekil 1’deki senaryo için oluşturulmuş 2 li kapsayan diziye bir örnek ve kararlardan elde edilmiş sonuçlar.
Başka bir alternatif çözüm yolu ise kapsayan dizinin kapsama kuvvetini arttırmak olabilir. Ama bu yaklaşımda test havuzunun boyutunu çok fazla arttırabilir. Örneğin, KK kriteri için tam kapsama elde etmeyi garanti etmek için eklenmesi gereken kombinasyon beş tane parametre içerdiğinden, 5 li bir kapsayan dizi kullanmak gerekecektir. Yani 5 uzunluğundaki bu özelliklerde bir kapsayan dizi 32 tane konfigürasyon içerecek olup aslında tüm konfigürasyon uzayını test etmek ile aynı sonuca gelecektir.
Eğer bu probleme B-KES yaklaşımı uygulanmış olsaydı, Şekil 2’de verilen 2 li kapsayan dizisine bir tane ekstra konfigürasyon daha eklenerek KK kriteri altında tam bir kapsama elde edilebilirdi. B-KES yöntemi için KK kriteri altında tüm karar sonuçları bir kısıt şeklinde ifade edilmelidir: p1,¬p1, p2, ¬p2, p3, ¬p3, p4, ¬p4, p5, ¬p5, (p1 ∧ p2 ∧ p3), ¬(p1 ∧ p2 ∧ p3), ((p1 ∧ p2 ∧ p3) ∧ (p4 ∨ p5)), ve ((p1 ∧ p2 ∧ p3) ∧ ¬(p4 ∨ p5)). Şekil 2’de verilen 2 li kapsayan dizisi ((p1 ∧ p2 ∧ p3) ∧ ¬(p4 ∨ p5)) dışında tüm ikili parametre ilişkilerini kapsamaktadır. Dolayısıyla, bu karar sonucunun kapsanması için p1=D, p2=D, p3=D, p4=Y, ve p5=Y şeklinde bir konfigürasyon daha üretilmelidir.
Örnek 2: Şekil 3a varsayımsal bir yazılım sistemini modelleyen bir sonlu durum makinesini göstermektedir. Modelde başlangıç (si) ve bitiş durumlarına ek olarak (sf) 4 tane durum (s1, s2, s3, s4) ve 4 tane de sadece iki değer alabilen (doğru için D, yanlış için Y) parametreler bulunmaktadır. Bir parametre sadece 1 tane durum içinde tanımlanabilir ve bir durum hiç olmamakla beraber farklı sayılarda parametre içerebilir. Örneğin, Şekil 3a’da durumların hepsi sadece 1 parametre içermektedir. Parametrelere değerler sadece kendi bulundukları durumlarda atanabilir. Parametrenin değeri bir durum içinde bir kez atandıktan sonra, bu parametre bulunduğu durumunda içinde olduğu durumlardan oluşmuş herhangi bir yoldaki tüm parametrelerle etkileşebilir. Örneğin, p2 parametresine sadece s2 durumunda değer atanabilir ve bir kez atandıktan sonra p1 ve p4 parametreleri ile etkileşebilir (Şekilde 3a’daki <si-s1-s2-s4-sf> yolundan ötürü). Durumlar arasındaki geçişler parametrelerin değerleri tarafından korunabilirler. Örneğin, s1 ile s2 arasındaki geçiş sadece p1 doğru olduğunda mümkün olabilir. Ayrıca sistemi başlangıç durumundan bitiş durumuna götüren test parametreleri ve değerleri kümesi test durumu olarak düşünülmüştür. Bu tip bir sistem modellemesi mesela bir telefon uygulaması testinde kullanılabilir. Her durum grafiksel arayüzdeki ekran görüntüsü, parametreler ekrandaki kullanıcı girdileri ve durumlar arasındaki geçişler ise ekranlar arasındaki girdiye bağlı sağlanan geçişleri olarak düşünülebilir.
Şekil. 3. Varsayımsal bir yazılım sistemini modelleyen sonlu bir durum makinesi
Yazılım geliştiricilerin bizim bu varsayımsal sistemimizin tüm ikili parametre değer
kombinasyonlarını test etmek istediklerini düşünelim. Geleneksel kapsayan diziler
kullanılarak sistemdeki 4 parametre için 2 li bir kapsayan dizi üretilebilir (Şekil 4). Fakat,
p3, p1=Y (¬p1) olduğunda erişilemeyeceğinden ötürü, 16 ikili parametre
kombinasyonundan 3 tanesi (%18.75) maskelenmiş olacak [
Maskelenen kombinasyonlardan biri olan (p3 = D, p4 = D) Şekil 4’te sadece ilk konfigürasyonda (p1 = D, p2 = Y, p3 = D, p4 = D) bulunmaktadır. Fakat bu konfigürasyon, p3’ün p1=D olduğu zamanlarda ulaşılamayacağından dolayı uygulanamayacaktır. Bu sebeple, bu kombinasyon Şekil 4’te verilmiş olan kapsayan dizi tarafından test edilemeyecektir. Diğer maskelenen kombinasyonlar ise şunlardır: (p2 = Y, p4 = Y) ve (p2 = D, p4 = D).
Şekil. 4. Şekil 3a için üretilmiş geleneksel bir 2 li kapsayan dizi.
Başka bir yaklaşım ise bu sistem modelinin her yolu için üzerinde bulunan parametreler kullanılarak kapsayan diziler üretmek olabilir. Daha sonra üretilen bu kapsayan p1 D D D Y Y Y p2 Y D Y D Y D p3 D Y Y D Y Y p4 D Y Y Y D
D diziler sistemin test havuzunu oluşturmak için birleştirilebilirler. Örneğin, Şekil 3a’da verilen modelin <si-s1-s2-s4-sf> ve <si-s1-s3-s4-sf> yolları için ayrı ayrı 2 li kapsayan diziler oluşturulması gerekir.
Bu alternatif yaklaşımın bir problemi daha karmaşık sistem modelleri için dallanmalar arttıkça olası bütün yolların sayısı da üssel bir hızda artacaktır ve çoğu zaman bütün bu yollar için ayrı ayrı kapsayan diziler oluşturmak mümkün olmayacaktır. Örneğin, Şekil 3b’de başlangıç durumundan bitiş durumuna gidilebilecek 4 farklı yol vardır. Bütün bu yollar için kapsayan diziler üretilmesi gerekir.
Bu yöntemi uygulamak mümkün olsa dahi, her yol için kapsayan dizi üretip daha sonra bunlar birleştirildiğinde, test durumlarının sayısı gerekenden çok fazla bir şekilde artacaktır. Bu da sistemi test etmenin maliyetini arttıracaktır. Bir başka örnek olan Şekil 3c’de ise 2 tane 2 li kapsayan diziye ihtiyaç vardır: bir tanesi <si-s1-s3-s4-s5-s6-sf> yolu üzerindeki p2, p4, p5 ve p6 parametreleri için, diğeri ise <si-s1-s2-s4-s5-s6-sf> yolu üzerindeki p3, p4, p5 ve p6 parametreleri için. Bahsedilen yollarda bulunan p1’in test durumlarında olmamasının sebebi her yol üzerinde de alacağı değerlerin (D veya Y) sabit olmasındandır. Her iki kapsayan dizinin boyutları en azından 6 olacağından (Şekil 4), birleştirilmiş kapsayan dizinin boyutu ise en az 12 olacaktır. B-KES ise verilen sistem modellemesini kullanarak mümkün olan geçerli tüm parametre değer kombinasyonlarını kısıtlar şeklinde tanımlar. Örneğin, Şekil 3c’de verilen sistem modeli için (p3=D, p4=Y) ikilisi p2 ∧ ¬p4 şeklinde kısıta çevrilebilir.
Geçerli tüm 2 li parametre değerleri kombinasyonlarını gösteren kısıtları kapsamak için Şekil 5’de gösterilen boyutu 8 olan bir B-KES objesi oluşturulabilir. Geleneksel kapsayan dizileri kullandığımız önceki çözümlerimize kıyasla, B-KES 2 li kapsama kriteri ile tam kapsamayı koruyarak test havuzunun boyutunu %33 oranında azaltmıştır. p1 D D D D Y Y Y Y p2 D Y D Y * * * * p3 * * * * Y Y D D p4 D D Y Y Y D Y D p5 D Y Y D Y D Y D p6 Y D D Y Y D Y D Şekil. 4. Şekil 3c senaryosu için oluşturulmuş bir B-KES objesi. *’lar “önemsiz” durumları göstermektedir. Yani, bu kısımlar geçerli herhangi bir değer ile değiştirildiğinde B-KES objesinin kapsama özelliklerini etkilemezler. 5
Bu bölümde B-KES objesi hesaplayabilmek için aç gözlü (greedy) bir algoritma öneriyoruz. Algoritma girdi olarak kısıtlarla tanımlanmış bir sistem modeli M ve bir kapsama kirteri C, alır. Algoritma ilk olarak tüm geçerli B-KES test isterlerini üretir. Bunu yapabilmek için, öncelikle kapsanması istenen her bir ister üretilir ve bir kısıta r dönüştürülür. Daha sonra tüm r için r ∧ M ‘nin tatmin edilebilir olup olmadığı kontrol edilir. Eğer tatmin edilebilirse r geçerli bir isterdir ve test havuzu tarafından kapsanması gerekir. Değilse geçersiz olarak işaretlenir.
Bütün geçerli isterler kümesi R bu şekilde üretildikten sonra, R’nin alt kümelerinden R’ oluşmuş başka bir küme S daha oluşturulur, öyle ki; her bir alt küme R’ içindeki bulunan kısıtlar kendi bulundukları kümede birlikte tatmin edilebilir olsun. Bu alt kümeler kümesi S oluşturulurken R içindeki her bir r’in mutlaka en azından bir alt kümede bulunduğu garanti edilir. S’in içindeki her bir kümenin daha sonra test durumlarına dönüştürüleceğini göz önünde bulundurarak, içerdiği alt kümeleri sayısı mümkün olduğunca az olması gerektiği söylenebilir.
Bu S kümesini oluşturabilmek için öncelikle boş bir alt küme havuzu ile başlarız. Akabinde, R içindeki bütün geçerli isterleri (r) havuzdaki herhangi bir alt kümeye eklenebilir mi onu kontrol ediyoruz. Eğer böyle bir alt küme bulunursa, r’yi bu alt kümeye ekleriz. Eğer bulunamazsa, havuza yeni boş bir alt küme ekler ve r’yi bu yeni kümeye koyarız. Burada dikkat edilmesi gereken husus alt kümelerde bulunan tüm isterler kısıtların birleşimi şeklinde ifade edilmiştir ∧ r′∈R′ r′. Bundan dolayı, bir isterin r var olan bir alt kümeye eklenip eklenememesi, aslında bu alt kümedeki kısıtların r ve M ile birlikte tatmin edilebilir olup olmamasıdır: yani r ∧ M ∧ (∧ r′∈R′ r′). Sonuç olarak, eğer bu kısıt ifadesinin sonucu tatmin edilebilir ise, r bu alt kümeye eklenir.
Bütün alt kümeleri oluşturduktan sonra, tüm alt kümeler R′ için, r ∧ M ∧ (∧ r′∈R′ r′). ifadesi çözülerek her bir alt küme için farklı bir test durumu oluşturuyoruz. Bu sayede oluşturulmuş bu test durumlarının verilen kapsama kriteri C altında tam kapsama yaptığı garanti edilmiş oluyor. 6
Bu çalışmamızda sunmuş olduğumuz yaklaşımımızın, KES yaklaşımlarının pratik hayattaki kullanabilirliklerini önemli ölçüde arttıracağını düşünüyoruz. Bu yüzden, B-KES objeleri üretebilmek adına yeni diller ve geleneksel olmayan tipte konfigürasyon uzaylarını ve kapsama krtierlerini tanımlayabilmek için yeni araçlar ve algoritmalar geliştirmeye devam edeceğiz. 7
Kaynaklar