(3.232.96.22) 您好!臺灣時間:2021/01/23 22:33
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:楊乃融
研究生(外文):Nai-Jung Yang
論文名稱:Dissimilarity of Polymorphic Execution Sequences
論文名稱(外文):Dissimilarity of Polymorphic Execution Sequences
指導教授:鄭永斌鄭永斌引用關係
學位類別:碩士
校院名稱:國立中央大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2013
畢業學年度:101
語文別:中文
論文頁數:45
中文關鍵詞:執行序列軟體品質相似度
相關次數:
  • 被引用被引用:0
  • 點閱點閱:148
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:12
  • 收藏至我的研究室書目清單書目收藏:0
程式執行時,所拜訪過的程式碼片段,組合而成一個序列,稱之為執行序列( 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.

連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔