Tez No	İndirme	Tez Künye	Durumu
377419		Improvements in finite state machine based testing / Sonlu durum makinelerine dayalı sınama dizilerinde iyileştirmeler Yazar:URAZ CENGİZ TÜRKER Danışman: YRD. DOÇ. DR. HÜSNÜ YENİGÜN ; PROF. DR. ROBERT HİERONS Yer Bilgisi: Sabancı Üniversitesi / Mühendislik ve Fen Bilimleri Enstitüsü / Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control ; Mühendislik Bilimleri = Engineering Sciences Dizin:Sonlu durum makineleri = Finite state machinery	Onaylandı Doktora İngilizce 2014 238 s.
Sonlu durum makinelerine (SDM'e) dayalı sınama yöntemleri 1956 yılında makine tanıma üzerine yapılan çalışmalar ile başlamış ve elli yılı aşkın bir süredir üzerinde çalışılan bir konu olmuştur. Makine tanıma çalışmalarını takiben bir gerçekleştirmenin bir spesifikasyona uygun olup olmadığının sınanması üzerine çalışmalar başlamış ve verilen SDM'nin durumları tanımlandığı ve belli bir hata kümesi göz önüne anlındığı zaman verilen bir SDM için sınama dizilerinin üretilmesi için polinom zamana ihtiyaç duyulduğu bilinmektedir. Bu tezde iki farklı sınama dizisi ele alınmıştır: Sınama Dizisi (SDi) ve Sınama Deneyleri (SDe). Sınama dizileri ister SDi ister SDe olsun genelde belli bir prensipte çalışır: bir kez üret ve çok kez kullan. Bu yüzden sınama dizilerinin boylarının kısa olması sınama sırasında geçen yekün süreyi azaltacağı gerekçesi ile oldukça önemlidir. Bu yüzden literatürde bu alanda çalışmalar yapılmaya başlanmıştır. Bu tezde ilk önce SDi'lerin boyunu kısaltmayı amaçlayan stratejiler gösterilmiştir. Bir SDi birden fazla kendisinden ufak girdi dizilerinden oluşur mesela Sıralama Dizisi, Durum Tanıma Dizisi. Bu konu üzerine yapılan hemen hemen tüm çalışmalar bu dizilerin SDM ile birlikte verildiğini tahmin etnişlerdir ve bu diziler ile oluşturulacak SDi'ler belli bir hata kümesi göz önünde bulundurularak üretildiğinde bir spesifikasyonun hatalı tüm gerçekleştirmelerini bulacağı bilinmektedir. Bir başka değiş ile verilen hatalı bir gerçekleştirme üretilen bir SDi tarafından belirlenebilir. Farklı SDi oluşturma yöntemleri bu dizileri farklı şekilde bir araya getirerek SDi'leri daha kısa boyda oluşturmayı amaçlamışlardır. Ancak Sıralama ve Durum Tanıma dizileri bir SDi'nin en büyük parçaları olduğu bilgisi ile hareket edersek bu dizilerin boylarının kısaltılması, oluşturulacak SDi'lerin boylarını'da kısaltacağı düşünülmelidir. 1991'de verilen bir SDM'nin en kısa sıralama dizinin üretilmesinin NP != P eşitsizliği var olduğu sürece polinom zamanda üretilemeyeceği ispat edilmiştir. Ancak yakın geçmişte bir SDM'nin durumlar arası geçişlerinin özel bir türde olması "monotonik" durumunda en kısa sıralama dizisinin polinom zamanda üretileceği gösterilmiştir. ancak kısmi tanımlı bir monotonik SDM'nin en kısa sıralama dizisinin hesaplanma zorluğu açık bir problemdi. Bu tezde bu problemin NP-Zor olduğunu gösterdik. Öteyandan, 1994 yılında özellikli bir durum tanıma dizisinin (uyarlamalı ayrıştırma dizisi (UAD)) polinom zamanda üretilebileceği gösterilmiştir. Aynı çalışmada yazarlar aynı zamanda bir SDM için bu diziyi polinom zamanda üretebilen bir algoritma da göstermişlerdir. Ancak bu algoritma herhangi bir ayrıştırma dizisini büyüklüğünü aldırmadan üretmektedir. Bu çalışmadan başka tam tanımlı yada kısmi tanımlı SDM'ler için uyarlamalı ayrıştırma dizisi üretebilen başka bir çalışma yoktur. Bu tezde kısa uyarlamalı ayrıştırma dizisi üretmenin NP-TAM ve en kısa UAD'ye yaklaşmanın da NP-Zor olduğunu gösterdik. Bunun yanında SDi nin boyunu ortalama %29.2 kadar kısaltabilen sezgisel yöntemler sunduk. Bu tezde SDe'lerin boyunu kısaltmayı hedefleyen çalışmalar yaptık. SDe'ler SDi'lerin aksine birbiri ile birleşmeyen çok sayıda ufak sınama konuları içerir her bir sınama konusu gerçekleştirmenin farklı bir yönünü sınar. Ancak SDi'ler de olduğu gibi bu sınama konularının büyük bir bölümü yine durum tanıma dizilerinden oluşur. SDe'ler için sınırlı sayıda durum tanıma dizisi mevcuttur, bu tezde yeni bir durum tanıma dizisi sunduk ve gösterdik ki bu yeni durum tanıma dizisinin oluşturulmasının PSPACE-Tam olduğunu gösterdik. Bu sonucu takiben bu dizileri üretmek için sezgisel yöntem ürettik ve endüstriden alınmış SDM'ları üzerinde deneylar yaptık ve teklif edilen yöntem ile SDe'lerin boylarını %65'e varan oranlarda kısaltılabileceğini gösterdik. Dağıtık SDM'lerin (DSDM'lerin) sınanması tabanlı sınama çalışmalarının ilginç bir ayağı olmaktadır. Sınama dizilerinin üretiminde yaşanan zorluklara ek olarak dağıtık mimarilerin getirmiş olduğu kontrolledilebilirlik ve gözlemlenebilirlik problemleri eklenmektedir. Hernekadar mevcut SDi üretme yöntemleri durum tanıma dizilerinin DSDM ile birlikte verildiği düşünülmüşsede kontrol edilebilen durum tanıma disizin üretlimesine değinen bir çalışma yoktur. Bu tezde bu dizilerin üretilmesinin zorluğunu araştırmış ve bu dizilerin polinom zamanda üretilemeyeceğini ispatlamış bulunmaktayız.
Finite State Machine (FSM) based testing methods have a history of over half a century, starting in 1956 with the works on machine identification. This was then followed by works checking the conformance of a given implementation to a given specification. When it is possible to identify the states of an FSM using an appropriate input sequence, it's been long known that it is possible to generate a Fault Detection Experiment with fault coverage with respect to a certain fault model in polynomial time. In this thesis, we investigate two notions of fault detection sequences; Checking Sequence (CS), Checking Experiment (CE). Since a fault detection sequence (either a CS or a CE) is constructed once but used many times, the importance of having short fault detection sequences is obvious and hence recent works in this field aim to generate shorter fault detection sequences. In this thesis, we first investigate a strategy and related problems to reduce the length of a CS. A CS consists several components such as Reset Sequences and State Identification Sequences. All works assume that for a given FSM, a reset sequence and a state identification sequence are also given together with the specification FSM M. Using the given reset and state identification sequences, a CS is formed that gives full fault coverage under certain assumptions. In other words, any faulty implementation N can be identified by using this test sequence. In the literature, different methods for CS construction take different approaches to put these components together, with the aim of coming up with a shorter CS incorporating all of these components. One obvious way of keeping the CS short is to keep components short. As the reset sequence and the state identification sequence are the biggest components, having short reset and state identification sequences is very important as well. It was shown in 1991 that for a given FSM M, shortest reset sequence cannot be computed in polynomial time if P\neq\NP. Recently it was shown that when the FSM has particular type (``monotonic") of transition structure, constructing one of the shortest reset word is polynomial time solvable. However there has been no work on constructing one of the shortest reset word for a monotonic partially specified machines. In this thesis, we showed that this problem is NP-hard. On the other hand, in 1994 it was shown that one can check if M has special type of state identification sequence (known as an adaptive distinguishing sequence) in polynomial time. The same work also suggests a polynomial time algorithm to construct a state identification sequence when one exists. However, this algorithm generates a state identification sequence without any particular emphasis on generating a short one. There has been no work on the generation of state identification sequences for complete or partial machines after this work. In this thesis, we showed that construction of short state identification sequences is NP-complete and NP-hard to approximate. We propose methods of generating short state identification sequences and experimentally validate that such state identification sequences can reduce the length of fault detection sequences by $29.2% on the average. Another line of research, in this thesis, devoted for reducing the cost of checking experiments. A checking experiment consist of a set of input sequences each of which aim to test different properties of the implementation. As in the case of CSs, a large portion of these input sequences contain state identification sequences. There are several kinds of state identification sequences that are applicable in CEs. In this work, we propose a new kind of state identification sequence and show that construction of such sequences are PSPACE-complete. We propose a heuristic and we perform experiments on benchmark FSMs and experimentally show that the proposed notion of state identification sequence can reduce the cost of CEs by 65% in the extreme case. Testing distributed architectures is another interesting field for FSM based fault detection sequence generation. The additional challenge when such distributed architectures are considered is to generate a fault detection sequence which does not pose controllability or observability problem. Although the existing methods again assume that a state identification sequence is given using which a fault detection sequence is constructed, there is no work on how to generate a state identification sequence which do not have controllability/observability problem itself. In this thesis we investigate the computational complexities to generate such state identification sequences and show that no polynomial time algorithm can construct a state identification sequence for a given distributed FSM.