程式執行時，所拜訪過的程式碼片段，組合而成一個序列，稱之為執行序列( execution sequence )。執行序列常於測試案例選擇的研究中被探討，類似生物資訊領域中計算序列相似度時，利用一些常見的距離( distance )或相似度( similarity )計算公式，探討序列間彼此的差異以提供分類或是選擇的依據。執行序列代表的是程式執行的行為，不同的序列間可能經過相同或是相關的程式碼片段，因此序列間的行為會有不同程度的關聯性。 以往探討序列距離或相似度的相關應用中，僅探討不同序列間共同執行之程式碼片段集合，即兩序列間經歷過相同程式碼片段的比例，當作序列相似度之依據。然而程式碼執行過程中，不同程式碼片段的執行順序對於程式行為的表現，具有非常大的影響，過去對於序列間相似度的研究較少考慮程式執行序列之順序所造成的影響。 現今物件導向 ( object-oriented ) 技術被廣泛接受並且應用於軟體開發當中。多型( polymorphism ) 為物件導向中重要的技術之一，對於執行序列間的差異程度具有明顯的影響。以往探討執行序列的距離及相似度計算公式，在物件導向的程式執行序列中，並無法分辨出多型(polymorphism)這樣的特性。因此本研究利用生物資訊領域中計算序列相似度的演算法Needleman – Wunsch Algorithm ( NWA ) [1]，納入執行序列發生多型行為時的特性，並且考量序列執行順序不同造成之影響，提出計算執行序列間差異度(Dissimilarity) 的方法，以解決目前探討程式執行序列相似度所存在之問題。 When a program is executed, the visited places of the run can form an ordering sequence which is called an execution sequence. The distance or similarity between sequences is an interesting issue in topics such as test case selection, etc. Similar problems have been particularly widely studied in biomedical informatics as well. To compute the distance of two sequences, a straightforward approach is to compute the common shared segments between two sequences in ratio. However, in the semantics of software engineering, the order of sequences is very important in practice. The measuring of distances between software execution sequences should consider such a fact. In recent years, object-oriented techniques have been widely applied in software development. Polymorphism is one of the important constructs in object-oriented programming. Few studies have considered the impact of polymorphism while computing the distance between two execution sequences. To address the issue, this thesis proposes a dissimilarity function between two program execution sequences. Our dissimilarity takes into account the polymorphism of sequences. Needleman – Wunsch Algorithm (NWA) which was widely adopt in biomedical informatics was modified to compute our dissimilarity function.
