A condition coverage-based black hole inspired meta-heuristic for test data generation
Koşullu kaplam tabanlı ve kara delik algoritması bazlı test verisi üretimi için meta-sezgisel bir yöntem
- Tez No: 865620
- Danışmanlar: DR. ÖĞR. ÜYESİ AYŞE TOSUN KÜHN
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2022
- Dil: İngilizce
- Üniversite: İstanbul Teknik Üniversitesi
- Enstitü: Lisansüstü Eğitim Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Bilgisayar Mühendisliği Bilim Dalı
- Sayfa Sayısı: 76
Özet
Yazılımların karmaşıklık seviyesi arttıkça, yazılım teste duyulan ihtiyaç ve yazılım testin önemi gün geçtikçe artmaktadır. Özellikle güvenlik-kritik yazılımlar için var olan hataları yakalayabilmek ve hatasız bir yazılıma yakınsamak oldukça önemlidir. Güvenlik-kritik yazılımların güvenlik gereksinimlerini karşılayıp karşılamadığını kontrol etmek amacıyla DO-178 gibi bazı standartlar önerilmiştir. Bu tip standartlarda bulunan kod kaplama, yazılım kalite ve güvenlik gereklerinin sağlanıp sağlanılmadığının ölçülmesinde kullanılan önemli bir metrik olarak karşımıza çıkmaktadır. Yazılım testlerinde kod kaplama oranının arttırılması için test verilerinin sistematik bir içimde üretilmesi gerekmektedir. Kombinasyonal Test yöntemi, test verisi üretimi için kullanılan yöntemlerden biridir. Ancak, fazla sayıda parametreyi girdi olarak alan yazılımlar için kombinasyonal test yöntemi kullanıldığında, test girdisi patlaması problemiyle karşı karşıya kalınabilmekte ve girdi parametrelerinin tüm kombinasyonlarının test edilmesi mümkün olamamaktadır. Bu çok sayıda test girdi setinin alt kümelerinin seçilmesinde ve böylece test girdi seti sayısının azaltılmasında kullanılan en etkin yöntemlerden biri“T-way Testing”yöntemidir. Fakat bu yöntem ile test girdi setleri seçilirken kod kaplama oranı gözetilmemekte ve verimli olan test girdi setleri özel bir eleme yöntemi kullanılarak seçilmemektedir. Dolayısıyla, yazılımlar kod kaplama oranı yüksek bir biçimde test edilememektedir. Bu tez çalışmasındaki motivasyon, yüksek kaplama oranları ile kaliteli testler yapılabilmesi için koşullu kaplama oranı gözetilerek test verisi üretmektir. Tüm test veri setlerinin test edilmesine ihtiyaç duyulmadan, verimli olan test veri setlerinin seçilmesi, yüksek kaplama değerleri ile testlerin gerçekleştirilmesine olanak sağlayacaktır. Bu çalışma, şu araştırma sorusuna yanıt aramaktadır: Lokal minimum değere takılı kalmayacak şekilde, yüksek kaplama oranları elde edebileceğimiz nasıl bir meta-sezgisel yöntem önerebiliriz? Sorularımıza yanıt bulabilmek için öncelikle literatürü taradık ve Arama Tabanlı Yazılım Testi ve Arama Tabanlı Kombinasyonal Yazılım Testi yaklaşımlarının meta-sezgisel yöntemleri kullanarak optimal şekilde test veri setleri üretmede kullanıldığını gördük. İncelediğimiz çalışmalar arasından bizim problemimize en benzer olanlar ile farklı veri setleri kullananları seçtik. Böylece kullanılan yöntem bakımından çeşitliliği sağlayarak benzer problemlere önerilen çözüm önerileri hakkında daha geniş kapsamlı bilgi sahibi olduk. Yaptığımız araştırmalar sonucunda Arama Tabanlı Yazılım Testi çatısı altında kullanılan meta-sezgisel yöntemlerin yazılım testlerinde yüksek kaplama oranları elde edecek şekilde test verisi üretimi için kullanılabilir olduğu sonucuna vardık. Litratür taraması sırasında meta-sezgisel bir yöntem olan Kara Delik Algoritmasının (KDA) da test verisi üretimi için kullanılıyor olduğunu gözlemledik. İncelediğimiz ve baz aldığımız çalışmadaki şu üç özellikten dolayı bu algoritma üzerinde çalışmaya karar verdik: (1) İncelediğimiz çalışmanın bizim problemimize çok benzer bir probleme sahip olması (2) Aslında bir veri gruplama algoritması olmasına rağmen KDA'nın bu çalışmada veri üretimi amacıyla yenilikçi bir biçimde kullanılmış olması ve (3) Çalışmada kullanılan KDA'nın başka bir optimizasyon metoduna göre test verisi üretiminde kod kaplama oranı açısından daha başarı olarak raporlanmış olması. Tüm bu sebeplerden dolayı KDA'nın temel alarak çok daha güçlü bir yöntem geliştirebileceğimiz motivasyonu ile çalışmalarımıza başladık. Bu hedefimize ulaşmak için Arama Tabanlı Kombinasyonal Yazılım kapsamında bahsedilen test girdisi patlaması problemine çözüm oluşturacak şekilde, KDA'nın binary varyantını (BKDA) baz alan, BH-AllStar adında yeni bir yaklaşım önerdik. Bu yeni yaklaşımda, BKDA'deki yöntemlerin bazılarını olduğu gibi kullandık, bazılarını ise yeniden düzenledik, ayrıca yeni yöntemler geliştirdik. BH-AllStar yaklaşımı şunları amaçlamaktadır: (1) yüksek kaplama oranları elde etmek (2) lokal minimum değere takılı kalmamak (3) ayrık (sürekli olmayan) girdi seti değerlerini ele almak. BKDA ve BH-AllStar arasındaki en önemli 2 fark ise, yeni eleme mekanizması ve önceden elenmiş olan yıldızları değerlendirerek tüm işlemlerin sonunda verimli olanlarını yeniden popülasyona dahil edilmesi ve böylece kaplama oranının arttırılmasıdır. Bu tez çalışması ile sağladığımız katkılar şu şekilde özetlenebilir: (1) Her koşul dalı için ayrı ayrı koşul kaplama oranı hesaplayarak daha verimli test girdileri ürettik ve böylece daha detaylı testler gerçekleştirdik, (2) Literatürde olmayan, yeni bir koşullu kaplama bazlı test girdisi seçme mekanizması geliştirdik ve işe yarayan test girdilerinin hatalı bir şekilde elenme riskini azalttık (3) Daha önce elenmiş olan test girdilerini tekrar değerlendirip test girdilerinde çeşitliliği sağlayarak lokal minimum değerine takılmaktan kaçındık (4) Literatürdeki çalışmalardan farklı olarak, koşullu kaplama değerine, üretilen test girdisi sayısına göre yüksek öncelik vererek yüksek kaplama oranları ile daha kapsamlı testler gerçekleştirdik; (5) BH-AllStar yaklaşımımızın geçerliliğini, biri gerçek bir güvenlik-kritik yazılım, diğer ikisi basit yazılım olmak üzere üç farklı yazılım üzerinde uygulayarak gösterdik. Geliştirmiş olduğumuz BH-AllStar yöntemi dört temel özellik içermektedir. Bunlar: (1) Koşullu Kaplam tabanlı eleme yöntemi, (2) kesikli girdi parametreleri için hareket yöntemi, (3) geçmişteki popülasyonlardan en iyisini seçme yöntemi ve (4) en iyi yıldızlar operasyonu. Geleneksel Kara Delik Algoritması şu şekilde işlemektedir: Çözüm havuzunda çok sayıda olası çözüm bulunmaktadır. Başlangıçta rastege olarak bir yıldız kümesi üretilir (yıldız bizim problemimizde bir girdi setine karşılık gelmektedir). Bu yıldız kümesindeki her bir yıldız için verimlilik değeri hesaplanır ve en verimli yıldız kara delik olarak ilan edilir. Daha sonra, kara delik etrafındaki diğer yıldızlar kara deliğe doğru hareket ettirilir. Eğer ki yıldızlardan herhangi biri kara deliğin yarıçapı içine girerse, o yıldız yok edilir ve yerine rastege yeni bir yıldız üretilir. Böylece yıldız kümesinde çeşitlilik sağlanmakta ve istenen kaplama değerine ulaşma ihtimali arttırılmaktadır. Bu döngü maksimum sayıda döngü sayısına veya istenen verime erişildiğinde son bulur. Geleneksel Kara Delik Algoritması'nı kendi problemimiz üzerinde uyguladık ve bizim için bazı dezavantajları ile karşılaştık. Bunlardan birincisi, eleme mekanizmasının yıldızlar arasındaki mesafeye bağlı olarak çalışıyor olmasıdır. Gerçekleştirmiş olduğumuz deneyler sonucunda fark ettik ki, bir yıldız kara deliğe çok yakın olsa da kaplam oranının artmasına katkı sağlıyor olabilmektedir. Bu durumu aşmak için, yıldızlar arası mesafeye dayalı eleme mekanizması yerine kaplama oranına bağlı bir eleme mekanizması geliştirdik. Bu mekanizmada elimizdeki aday yıldızın elenip elenmeyeceğine karar vermek için öncelikle bu yıldızın (test girdisinin) herhangi bir dalda en iyi kaplama sonucu verip vermediğini değerlendirmekteyiz. Eğer herhangi bir dalda en iyisiyse, bu yıldızı çözüm havuzumuza ekliyoruz. Aksi durumda, bu yıldıza çözüm havuzumuza eklenmesi için bir şans daha veriyor ve bir oran hesabı yapmaktayız. Bunun için aday yıldızın kara deliğe göre daha iyi kapladığı dal sayısını, daha kötü kapladığı dal sayısına oranlıyoruz ve iyi kapladığı dal sayısını daha önceden deneyler sonucunda belirlemiş olduğumuz katsayı ile çarparak yıldızın çözüm havuzumuza eklenme ihtimalini arttırıyoruz. Bunu yapma amacımız ise, her bir yıldızın kaplanmamış bir dalı kaplama ihtimalinin değerli olmasıdır. Geliştirdiğimiz bir diğer yöntem, kesikli girdi değerleri için kara deliğe doğru hareket edebilmek için tasarladığımız yapıdır. Bu yapıda, her bir girdi parametrelerini ayrı birer dizine saklamaktayız ve eğer bir yıldızı kara deliğe doğru hareket ettirmek istersek; kara deliğin ve mevcut yıldızın ilgili parametrelerinin saklandığı indis değerleri arasında rastgele bir indis üreterek hareket ettirilmiş yıldızın yeni değerini indisteki girdi değeri olarak güncellemekteyiz. Böylece mevcut yıldız, kara deliğe daha da yakınlaşmış olmaktadır. Kara Delik Algoritması'nın içerdiği rastegele işlemler ve kara deliğe doğru hareket işlemleri sebebiyle, döngüler tamamlandığında elimizdeki son popülasyon en verimli popülasyon olmayabilmektedir. Geçmişteki en iyi popülasyonun seçilmesi yönteminde; döngüler boyunca üretilmekte olan popülasyonlar arasından en iyi olanı devamlı olarak seçmekteyiz. Sonuç olarak döngüler tamamlandığında elimizde en verimli olan populasyon bulunmakta ve işlemlerimize bu popülasyon üzerinden devam etmekteyiz. Geçmişteki en iyi popülasyonu seçtikten sonra ise, en iyi yıldızların seçimi yöntemini uygulamaktayız. Bu yöntemde, döngüler boyunce üretilmiş olan gerek elenmiş gerekse çözüm havuzuna eklenmiş bütün yıldızları taramakta ve bu yıldızlar arasından herhangi bir dalga en iyi olanları seçerek çözüm havuzuna eklemekteyiz. Bir önceki adımda seçtiğimiz populasyonun içerisinde bazı kaplanmamış dalların kaplanması ihtimalini bu yöntem ile arttırmaktayız. Yöntemimizi koşullu kaplama oranı, test veri seti sayısı ve çalışma süreleri bakımından değerlendirdik. Sonuç olarak BH-AllStar yöntemimizin BKDA'ye göre %43'e varan oranda daha yüksek koşullu kaplama oranı elde ettiğini gördük. BH-AllStar bazı durumlarda BBH'ye göre daha fazla test veri seti üretiyor olsa da bu sayılar kod kaplama oranının artması için tolere edilebilir seviyededir. Araştırma sorumuzu BHA'dan türetmiş olduğumuz BH-AllStar yaklaşımı ile cevapladık. Böylece Arama Tabanlı Kombinasyonal Yazılım alanında bir meta-sezgisel yaklaşım kullanılarak kod kaplama oranını arttırmak üzere lokal minimum değerden kaçınarak yeni bir yöntem geliştirdik ve başarı elde ettik. Gelecekte, BH-AllStar yaklaşımının farklı yazılımlar üzerinde denenmesi, rastgele ilklendirme işlemlerinin optimizasyonu ve değiştirilmiş koşul/karar kaplama testleri alanında çalışmalar yapmayı planlıyoruz.
Özet (Çeviri)
As software becomes more complex, the importance of software testing increases by the day. It is very important to get as close to bug-free software as possible, especially for safety-critical systems. Some standards, such as DO-178, have been established to ensure that the safety requirements of safety-critical software are met. In these standards, the code coverage ratio is one of the parameters to measure test quality. To increase the coverage rate, test data must be generated in a systematic manner. Combinatorial Testing is one of the most commonly used methods to deal with this problem. However, for software that takes a large number of input parameters, CT causes test case explosion problems and it is not possible to test all produced test cases. To reduce the number of test cases, T-way testing is a technique for selecting a subset of huge numbers of test cases. However, because this technique does not choose test cases based on code coverage, the software is not tested with coverage values at the required height. The motivation of this study is to produce test cases by considering the condition coverage value. Thus, the condition coverage value and test quality will be increased without the need to test too many test cases of all possible combinations. This thesis focuses on the research question (RQ): How can we conduct a meta-heuristic method in Search-Based Combinatorial Testing (SBCT) that generates test data to achieve high coverage rates while avoiding local minima? To find answers to our research question, we reviewed the literature and discovered that Search-based Software Testing and Search (SBST) and Search-based Combinatorial Testing (SBCT) techniques are used to generate optimum test data using meta-heuristic approaches. Among the studies in the literature, we chose studies that work on problems similar to ours and studies that differ in terms of fitness function and data set, so we aimed to examine studies with various features as much as possible. As the results of our literature review, we discovered that meta-heuristics in Search-Based Combinatorial Testing (SBCT) could be used to generate test data for enhanced condition coverage in software testing. During our literature review, we realized that the Black Hole Algorithm (BHA), which is also a meta-heuristic approach, can be also used for our problem. Hence, after analysing alternative solutions, we decided to work on BHA for the following three main characteristics of our inspired study: (1) That study focused on a problem that is very similar to our problem, (2) Although BHA is a data clustering method, it is a novel method used in test data generation, (3) BHA was reported to be more efficient than another optimization algorithm (i.e., Particle Swarm Optimization (PSO)); and this finding inspired us to propose a stronger method. To achieve our goal, we present a novel approach based on a binary variation of the Black Hole Algorithm (BBH) in SBCT and adapt it to the CT difficulties. We reused some of the techniques in BBH, modified some of them, and introduced new methods as well. The proposed BBH version, BH-AllStar, aims the following: (1) obtaining higher condition coverage, (2) avoiding local minima, and (3) handling discrete input values. The main two significant differences between BH-AllStar and BBH are the new elimination mechanism and avoiding local minima by reassessing earlier removed stars and selecting the useful ones to add to the final population. Our contributions are as follows: (1) we perform more detailed tests by using detailed condition coverage rate criteria per each condition branch while generating test cases, (2) we develop a condition coverage-based test cases selecting mechanism and reduce the risk of eliminating the beneficial test cases wrongly, (3) we avoid local minima by providing variety achieved by re-evaluating the test cases which are destroyed before and giving chance them to be added to the final test case pool (4) we give higher priority to coverage rate than test case number unlike existing studies in the literature and thus, we provide more efficient tests with higher condition coverage rates and (5) we provide the validity of our BH-AllStar method by applying it to three different Software Under Test (SUT): one of them is a real-life safety-critical software and two of them are toy examples. Our new metaheuristic method can be applied on different software settings and all types of SUTs can be used on the experiment setup. We analyzed our approach in terms of condition coverage, number of test cases, and execution time. As a result, we observed that our BH-AllStar method provided up to 43% more coverage than BBH. Although BH-AllStar produced more test cases than BBH, this level of increase was acceptable to achieve higher coverage. Finally, we answered RQ by determining that the Black Hole phenomenon, which is provided as a meta-heuristic in SBCT, is a suitable strategy for producing test data in order to reach larger condition ratios while avoiding local minima by modifying and proposing novel features to it. As future work, BH-AllStar can be tested on different SUT, the randomization operation in initialization processes can be optimized and MC/DC tests can be studied. BH-AllStar.
Benzer Tezler
- Gemi-köprü kazaları için önlemler ve bulanık mantık tabanlı risk değerlendirme modeli oluşturulması örnek çalışma: 1915 Çanakkale Köprüsü
Measures for ship-bridge collisions and establishment of fuzzy logic-based risk assessment model case study: 1915 Çanakkale Bridge
MUHAMMED FATİH GÜLEN
Yüksek Lisans
Türkçe
2021
Denizcilikİstanbul Teknik ÜniversitesiDeniz Ulaştırma Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ MUHSİN KADIOĞLU
- Atmospheric correction of ocean color for the mineral dust aerosol over the Mediterranean sea and remotely sensed characterisation of coccolithophore blooms in the Black Sea
Akdeniz'de çöl tozu aerosolü için okyanus renginin atmosferik düzelmesi ve Karadeniz'de kokolit patlamalarının uzaktan algılama ile karakterize edilmesi
TÜLAY ÇOKACAR
Doktora
İngilizce
2005
Su ÜrünleriOrta Doğu Teknik ÜniversitesiFiziksel Oşinografi ve Deniz Biyolojisi Ana Bilim Dalı
PROF. DR. TEMEL OĞUZ
- Yer tabanlı uzaktan algılama sistemleri kullanılarak Akdeniz bölgesinde hortum hadiselerinin sinoptik analizi ve modellenmesi
Synoptic analysis and modeling of tornadoes events by using ground-based remote sensing systems in the Mediterranean region
RAMAZAN ÖZGENÇ
Yüksek Lisans
Türkçe
2020
Meteorolojiİstanbul Teknik ÜniversitesiMeteoroloji Mühendisliği Ana Bilim Dalı
PROF. DR. ALİ DENİZ
- Biyolojik yöntemle permeabilitesi iyileştirilen odunun bazı özelliklerinin ve bakır dağılımının incelenmesi
Evaluation of some properties and copper distribution in wood after permeability improvement by a biological method
DAVUT BAKIR
Doktora
Türkçe
2019
Biyoteknolojiİstanbul Üniversitesi-CerrahpaşaOrman Endüstri Mühendisliği Ana Bilim Dalı
PROF. DR. AYŞE DİLEK DOĞU
PROF. DR. NURAL YILGÖR