Dissimilarity of Polymorphic Execution Sequences

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：14

、訪客IP：18.116.63.5

姓名

楊乃融(Nai-Jung Yang) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

Dissimilarity of Polymorphic Execution Sequences
(Dissimilarity of Polymorphic Execution Sequences)

相關論文

★ 使用PolyTraceAid進行程式文件覆蓋率計算與分群	★ Support Visual Debugging in Electronic Design Automation Software by xDIVA
★ 設計與實作視覺化追蹤點以支援xDIVA進行程式動畫	★ Combine Internal Test Oracles and Capture/Replay GUI Testing for Precise Replay and Higher Validation Power
★ The Analysis of Capturing System Test Cases into Unit Test Cases	★ 動態延遲載入的測試覆蓋率
★ 建構於JMeter之自動化分散式壓力測試架構	★ 模組化因修改具耦合的程式碼所伴隨的成本漣漪
★ Design a Pluggable Architecture for Layout Algorithms in xDIVA	★ 重複性程式碼檢測之外掛模組設計
★ Visual Perception of Realistic Rendering in xDiva 3D Environment	★ Why and When GUI Test Automation Fails in Practice and Our Solutions to The Problem
★ Why and When GUI Test Automation Fails in Practice and Our Solutions to The Problem	★ Very High Precision Optical Character Recognition For Clean-Fixed-Sized True Type Characters
★ Enhance Korat by Branch Capability in Capture/Replay User Scenario to Industrial Test Case Automation	★ implement race detection functionality inXThreadDebugger base on pluggable modulesystem

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

程式執行時，所拜訪過的程式碼片段，組合而成一個序列，稱之為執行序列( 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.

關鍵字(中)

★ 執行序列
★ 軟體品質
★ 相似度

關鍵字(英)

論文目次

摘要 i
Abstract ii
目錄 iv
圖表目錄 vi
一、緒論 1
1 – 1 問題描述 1
1 – 2 研究動機與目的 1
1 – 3 論文架構 2
二、背景與相關研究 3
2 – 1 測試案例選擇(Test cases selection) 3
2 – 2 距離的相關研究 3
Hamming Distance 4
Levenshtein Distance 4
Jaccard similarity coefficient 5
Needleman – Wunsch Algorithm 5
2 – 3 PolyTraceAid簡介 7
製作tracecase: 7
播放Tracecase: 8
擷取execution sequences: 9
三、研究方法 10
3 – 1 程式執行序列抽象化 10
3 – 2 Polymorphic Execution Sequences NWA 12
3 – 3 PESNWA序列對齊實例 13
3 – 4 影響執行序列差異度之因素 14
3 – 4 – 1序列之間彼此有相同的元素 14
3 – 4 – 2 序列之間的連續相同元素 (Continuously Matched Sequence) 15
3 – 4 – 3 序列之間的多型元素 18
3 – 5 Dissimilarity 19
四、Evaluation 22
4 – 1 實驗方法 22
4 – 2 第一組序列Evaluation 結果 24
4 – 2 – 1 Circos 輻射圖 26
4 – 2 – 2 Bug injection 結果與 Dissimilarity之關係 27
4 – 2 – 3 多型序列之Dissimilarity評估 28
4 – 2 – 4 相異多型序列的Dissimilarity評估 30
4 – 3 第二組序列Evaluation 結果 31
4 – 4 討論 34
五、結論與未來展望 35
5 – 1 結論 35
5 – 2 未來展望 35
參考文獻 37

參考文獻

[1] S. B. Needleman, and C. D. Wunsch, “A general method applicable to the search for similarities in the amino acid sequence of two proteins,” Journal of molecular biology, vol. 48, no. 3, pp. 443-453, 1970.
[2] G. D. a. J. Pei, Sequence Data Mining: springer, 2007.
[3] D. Gusfield, Algorithms on strings, trees and sequences: computer science and computational biology: Cambridge University Press, 1997.
[4] P.-N. Tan, and M. Steinbach, "Vipin Kumar, Introduction to Data Mining," Addison Wesley, ISBN 0-321-32136-7, 2006.
[5] Y. Yu-Ying. "PolyTraceAid:加速程式碼理解之文件製作與追蹤系統 "; http://ndltd.ncl.edu.tw/cgi-bin/gs32/gsweb.cgi/login?o=dnclcdr&s=id=%22099NTNU5392028%22.&searchmode=basic.
[6] H. Hemmati, and L. C. Briand, "An Industrial Investigation of Similarity Measures for Model-Based Test Case Selection," ISSRE, IEEE Computer Society, 2010, pp. 141-150.
[7] C. D. Pilcher, J. K. Wong, and S. K. Pillai, “Inferring HIV transmission dynamics from phylogenetic sequence relationships,” PLoS medicine, vol. 5, no. 3, pp. e69, 2008.
[8] R. Baeza-Yates, and G. Navarro, “Fast approximate string matching in a dictionary,” pp. 14-22, 1998.
[9] G. Navarro, “A guided tour to approximate string matching,” Computing Surveys (CSUR, vol. 33, no. 1, Apr, 2001.
[10] "Qt Project," May,2013; http://qt-project.org/.
[11] M. I. Krzywinski, J. E. Schein, I. Birol, J. Connors, R. Gascoyne, D. Horsman, S. J. Jones, and M. A. Marra, “Circos: An information aesthetic for comparative genomics,” Genome Research, June 18, 2009, 2009.

指導教授

鄭永斌

審核日期

2013-7-23

推文