Using simulated annealing for computing test case-aware covering arrays
Benzetilmiş tavlama algoritmasını kullanarak test durumlarını dikkate alan kapsayan diziler hesaplama
- Tez No: 389508
- Danışmanlar: YRD. DOÇ. DR. CEMAL YILMAZ
- 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: 2014
- Dil: İngilizce
- Üniversite: Sabancı Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 121
Özet
Yapılandırılabilirliği yüksek yazılım sistemlerinin eksiksiz bir şekilde test edilmesi pratikte olanaksızdır. Bu nedenle, konfigürasyon uzayının verimli bir şekilde örneklendirilmesi testlerin kapsamını artırmak için önemlidir. Bu amaca yönelik geliştirilen t-yollu kapsayan diziler (t-way covering arrays) (KAD), konfigürasyon seçeneklerinin bütün t-yollu kombinasyonları için bütün değer kombinasyonlarını kapsamak üzere sistematik bir şekilde oluşturulmuş bir konfigürasyon kümesidir. KAD'lar konfigürasyon seçeneklerinin etkileşimlerinden kaynaklanan hataları keşfetmeyi hedeflemektedir. Elde ettikleri birçok başarıya rağmen, pratikte KAD'ları kullanmak zor olabilir. Bir t-yollu KAD oluşturduktan sonra, diziye seçilmiş tüm konfigürasyonlar sistemin her bir test durumu (test case) için test edilir. Böyle yaparak, geleneksel KAD'lar, test durumlarının hepsinin seçilmiş bütün konfigürasyonlarda çalışabileceğini varsayar. Ancak yapılan son çalışmalar, yapılandırılabilirliği yüksek yazılım sistemlerinin test durumlarının üzerinde çalışacakları konfigürasyon hakkında varsayımlarının (kısıtlama) olmasının muhtemel olduğunu göstermektedir. Eğer bir konfigürasyon bir test durumunun kısıtlamalarına uymazsa, o test durumu o konfigürasyonu atlar ve bu da sadece o konfigürasyonda görünen değerlerinin o test durumunu tarafından test edilememesi sorununa yol açar. Bu soruna maskeleme etkisi denmektedir. Bu sorunu çözmenin bir yöntemi, son zamanlarda geliştirilen test durumlarını dikkate alan kapsayan diziler (test-case-aware covering arrays) (T-KAD) kullanmaktır.T-KAD'lar test durumlarının konfigürasyon seçeneklerinin aldıkları değerlerle ilgili olan kısıtlamalarını hesaba katarak bu kısıtlamalarından kaynaklanan maskeleme etkilerinin oluşmasını önler. Test durumlarının kısıtlarıyla zenginleştirilmiş bir konfigürasyon uzay modeli icin hesaplanmıs bir T-KAD, geleneksel kapsayan dizilerde olduğu gibi sadece bir konfigürasyon kümesi degil, her bir konfigürasyonun bir dizi test durumuyla ilişkilendirildiği bir konfigürasyon kümesidir. Bu yapıda, bir konfigürasyonla ilişkilendirilmiş test durumları kumesi, o konfigürasyonda çalıştırılması gereken test durumlarını ifade eder. Yapılan araştırmalarda, KAD'lar ile karşılaştırıldığında, T-KAD'ların maskeleme etkilerini ortadan kaldırarak kombinatoryal etkileşim testinin kalitesini önemli ölçüde arttırdığı gösterilmiş olmasına rağmen, kavram ispatı olarak geliştirilen birkaç algoritma haricinde, T-KAD hesaplamanın etkili ve verimli bir yöntemi yoktur. Bu sorunun, T-KAD'ların kombinatoryal etkileşim testine adapte olmasını engellediğini öngörmekteyiz. Bu tezde, benzetilmiş tavlama-tabanlı etkili ve verimli T-KAD hesaplama algoritmaları ve bu algoritmaları uygulayan bir yazılım geliştirdik. Ayrıca, iki yapılandırılabilirliği yüksek yazılım sistemi kullanarak büyük çaplı deneyler yaparak geliştirdiğimiz algoritmaların performanslarını karşılaştırdık ve değerlendirdik. Deneylerimizin sonuçları, önerilen algoritmaların T-KAD hesaplamada verimli ve etkili bir yol olduğunu ve mevcut yaklaşımlara göre performansının daha yüksek olduğunu göstermektedir.
Özet (Çeviri)
Exhaustive testing of highly configurable software systems is generally infeasible in practice. For this reason, efficient sampling of the configuration space is important to improve the coverage of testing. A t-way covering array is a list of systematically selected configurations covering all value combinations for every t-way option combinations and it aims to discover faults caused by interactions of configuration options. Despite its many successes, it can be difficult to use covering arrays in practice. Once a traditional t-way covering array is constructed, the system is then tested by running its test cases in all the selected configurations. By doing so, traditional covering arrays assume that all test cases can run in all configurations of covering array. Recent studies, however, show that test cases of configurable systems are likely to have assumptions about the underlying configurations, i.e., they are like to have some test case-specific inter-option constraints. When a configuration does not satisfy the test case-specific constraints of a test case, that test case simply skips the configuration, which prevents the test case from testing all valid combinations of option settings appearing in the configuration – an effect called a masking effect. A harmful consequence of masking effects is that they can make the developers to believe that they have tested certain option setting combinations while they in fact have not. A solution approach is to use test case-aware covering arrays – a novel type of combinatorial objects for testing that has been recently introduced. Test case-aware covering arrays take test case-specific inter-option constraints into account when computing combinatorial interaction test suites, such that no masking effects caused by overlooked constraints occur. Given a configuration space model augmented with test case-specific constraints, a test case-aware covering array is not just a set of configurations as is the case in traditional covering arrays, but a set of configurations each of which is associated with a set of test cases, indicating the test cases scheduled to be executed in the configuration. Although it has been empirically demonstrated that test case-aware covering arrays, compared to traditional covering arrays, can significantly improve the quality of combinatorial interaction testing by avoiding masking effects, there is no efficient and effective algorithms to compute them, except for a couple of proof-of-concept algorithms. We conjecture that this greatly hurts the adaptation of test case-aware covering arrays in practice. In this thesis, we have developed simulated annealing-based, efficient and effective algorithms to compute test case-aware covering arrays and a tool implementing these algorithms. We, furthermore, compare and contrast the performance of our algorithms by conducting large-scale experiments in which we used two highly configurable large software systems. The results of our empirical studies strongly suggest that the proposed algorithms are an efficient and effective way of computing test case-aware covering arrays and that they perform better than existing approaches.
Benzer Tezler
- GPU-based parallel computing methods for constructing covering arrays
GPU tabanlı paralel hesaplama yontemleri ile kapsayan diziler oluşturma
HANEFİ MERCAN
Yüksek Lisans
İngilizce
2015
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSabancı ÜniversitesiBilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. CEMAL YILMAZ
YRD. DOÇ. DR. KAMER KAYA
- Optimum determination of number, capacity and location of bioenergy power plant/s by using geographic information system: A case study in Bismil
Coğrafi bilgi sistemi kullanarak biyoenerji güç tesisi veya tesislerinin sayı, kapasite ve yerlerinin optimum bir şekilde belirlenmesi: Bismil'de bir uygulama çalışması
ADEM AKGÜL
Yüksek Lisans
İngilizce
2018
Endüstri ve Endüstri MühendisliğiGaziantep ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. SERAP ULUSAM SEÇKİNER
- Üretim kararlarının alınmasında meta-sezgisel algoritmaların kullanılması: Bir uygulama
Using meta-heuristic algorithms in making production decisions: A case study
RÜVEYDA KARABUDAK
Yüksek Lisans
Türkçe
2022
Mühendislik BilimleriGazi ÜniversitesiYönetim Bilişim Sistemleri Ana Bilim Dalı
DOÇ. DR. TALİP KELLEGÖZ
- Bulanık çok modlu kaynak kısıtlı proje çizelgeleme problemlerinin çözümü için matematiksel bir model
A mathematical model for the solution of the fuzzy multi mode resource-constrained project scheduling problems
ÖMER ATLI
Doktora
Türkçe
2012
Endüstri ve Endüstri MühendisliğiHava Harp Okulu KomutanlığıEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. CENGİZ KAHRAMAN
- Kaynak kısıtlı proje çizelgeleme probleminde tekrarsız kromozom destekli paralel genetik algoritma uygulaması
A parallel genetic algorithm application with nonrepetitive chromosome improvement for resource constrained project scheduling problem
ŞAFAK EBESEK