【正文】 浙江大學碩士學位論文 摘要 基于圖形遍歷算法的回歸測試方法的研究及應用 摘要自從發(fā)明計算機以來，信息技術飛速發(fā)展，相應的軟件開發(fā)與測試也在飛速成長。軟件并沒有人們想象當中的那么抽象與遙遠，在日常生活中接觸到的電腦軟件、手機軟件都涉及到了軟件開發(fā)。當然，軟件在開發(fā)出來之后就需要經過測試來檢測一下軟件開發(fā)的結果，這就是軟件測試。在軟件測試當中經常用到的驗證測試方法當屬回歸測試。雖然回歸測試成本比較貴，但是其測試結果較準確。當然，在現(xiàn)實中是非常激烈的。如果使用一種有效手段，通過這種機制既可以大大降低回歸測試所帶來的成本又可以提高監(jiān)測的效率，那么就會在競爭中處于領先地位。因此，如何研發(fā)這種機制是當今軟件測試的重點和難點。ExtendDejavu算法是目前使用廣泛的回歸測試用例選擇算法，但是該算法需要利用元數(shù)據(jù)來構造控制流圖和收集覆蓋信息，因此在實際使用中難度很大。本文借鑒ExtendDejavu算法精華，開發(fā)了基于修改點控制流圖的回歸測試用例選擇算法，能夠對C語言單元函數(shù)進行邏輯結構上的比較。從而減少測試用例，提高測試效率。算法主要包括以下內容：根據(jù)控制流圖對比技術檢測出有效修改點；根據(jù)語句節(jié)點的數(shù)據(jù)和控制之間的依賴關系構建基于修改點的軟件切片；以切片得到的節(jié)點集合作為目標覆蓋集合，從基準用例庫中選取相關測試用例構造回歸用例選擇子集T0；運行T0中測試用例；基于覆蓋情況分析是否存在未覆蓋的目標節(jié)點，若存在則構造回歸用例新增子集T1；最后合并T0和T1得到回歸測試用例集合。與ExtendDejavu算法相比，本論文主要有以下改進和創(chuàng)新：基于控制流圖對比技術檢測有效修改點，能夠精確定位代碼修改點；在修改點的基礎上進行語句級別切片，降低了回歸測試的覆蓋范圍；補充新的用例以保證回歸測試的充分性。所以，本文提出的回歸測試方法具有用例選擇精度高、回歸測試更加充分的特點，顯著提高了回歸測試的效率，明確體現(xiàn)了其有效性。關鍵詞：軟件測試，回歸測試，ExtendDejavu，測試切片i浙江大學碩士學位論文 AbstractAbstractSince the puters have been invented, the information technology is developing rapidly, at the same time, the corresponding software development and testing is also developing rapidly. In the process of software development, the more important aspect is the regression test. Software development is not so far from us, in our life, we are all exposed to puter software and cell phone software, and they are all related to the software development. Of course, software developers need to e out after the software has been tested to detect what the result of the development, and this is what we know software testing. Regression test is often used to software development. Although the cost of regression testing is very expensive, its test results are very accurate. Of course, in today39。s society, petition is very fierce. If you master an effective mechanism, we can greatly reduce the cost of regression testing at the same time, we can improve the efficiency of monitoring through this mechanism .It will pete in a leading position. Therefore, how to develop such a mechanism is the focus and difficulty of today39。s software testing.The ExtendDejavu algorithm is widely used the regression test cases selection algorithm, but the algorithm needs to use metadata to control flow graph and collect information, so in the practical use is very difficult. Essence, this paper Extend Dejavu algorithm is developed based on the modified point control flow graph of regression test case selection algorithm, can carry on the logical structure to the function C language unit in parison. To reduce the test cases, improve the test efficiency. Algorithm mainly includes the following content: according to the control flow chart pares technology to detect the effective modification point。 According to the statement data dependency and control dependency between nodes based on modified point build of the software section。 To slice the node set as the target coverage set, from the baseline test cases selecting the related test case library T0 select subset regression cases。 Run test cases in the T0。 Based on the analysis whether the cover has not covered the target node, if there is the structure new subset regression case T1。 Finally merge T0 and T1 regression test case set. Compared with the ExtendDejavu algorithm, this thesis mainly has the following improvements and innovations: detection based on control flow chart pares technology modification, can accurate positioning point code change。 At modify the statements on the basis of the level section, narrowed the range of regression testing。 Add new test cases to ensure the adequacy of the regression test. Regression testing method is proposed in this paper, therefore, the use cases with higher precision, more fully the characteristics of regression testing, greatly improve the efficiency and effectiveness of the regression test.Key Words：Software Testing,Regression Testing, Extend Dejavu,Test Sectioniii浙江大學碩士學位論文 目錄目錄摘要 IAbstract II圖目錄 III表目錄 IV第1章 緒論 1 課題背景 1 國內外研究現(xiàn)狀及進展 2 本文主要研究工作 5 論文組織形式 5 本章小結 6第2章 軟件測試和回歸測試的策略 7 軟件測試 7 軟件測試的目的 7 軟件測試方法 7 軟件測試策略 8 回歸測試 9 回歸測試分類 9 回歸測試策略 9 軟件測試與回歸測試比較 11 本章小結 12第3章 基于字節(jié)碼控制流圖的回歸測試用例選擇算法綜述 13 Dejavu算法以及擴展算法的介紹 13 UT2測試實例 15 測試環(huán)境 15 新舊版本字節(jié)碼 16 原始Dejavu算法控制流圖 16 ExtendDejavu算法控制流圖 17 測試結果 18 本章小結 18第4章 基于修改點控制流圖的回歸測試用例選擇算法 19 算法概述 19 無效修改點判定設計 19 基本概念 19 設計原理與算法 23 確定測試切片 29 基本概念 30 設計原理與算法 32 UT3測試實例 34 無效修改點判定測試 34 確定測試切片測試 36 本章小結 39第5章 優(yōu)化算法對比分析及實際應用 40 對比分析 40 單測試用例算法精度對比 41 多測試用例算法精度對比 42 TDLTE項目中自動化測試平臺應用 43 用例庫管理 44 系統(tǒng)運行 44 OMCRCT及DEBUGTOOL 47 測試結果及分析 49（一）測試報告 49（二）結果分析 50 本章小結 51第6章 總結與展望 52參考文獻 54作者簡歷 57致謝 59II浙江大學碩士學位論文 圖目錄圖目錄 軟件測試一般過程圖 11 17 刪減語句導致的控制流圖的變化 24 廣度優(yōu)先對比 25 深度優(yōu)先對比 26 N1為終結符節(jié)點，N2為普通節(jié)點的示例圖 28 N1為普通節(jié)點，N2為終結符節(jié)點的示例圖 28 計算修改點的流程圖 29（左）與動態(tài)切片（右） 30 靜態(tài)切片（上）與動態(tài)切片（下） 31 TDLTE項目中equation函數(shù)的原代碼（左）和修改后代碼（右） 35 被測單元f1的控制流圖 36 被測單元f修改前后的代碼 37 被測單元f的控制流圖 38 被測單元f關于節(jié)點decl_stmt_1的依賴圖 39 44 44 TRPC啟動 45 TmView操作界面 45 TmView操作界面 46 TRPC執(zhí)行操作界面 46 TRPC執(zhí)行操作界面 47 OMCRCT工具操作顯示界面 48 48 OMCRCT啟動 48 OMCRCT結束 48 DEBUGTOOL啟動 49 DEBUGTOOL結束 49III浙江大學碩士學位論文 表目錄表目錄 8 修改點有效性分析 23 函數(shù)f的控制流圖和源程序的對應關系 35 42 2種不同算法針對3個實例運算的運算結果對比 44IV浙江大學碩士學位論文 第1章 緒論第1章 緒論 課題背景其實計算機在安全上的問題已經存在很久了，特別在軟件層面上，軟件產生的故障問題越發(fā)的頻繁，隨之造成的危機也經常導致嚴重的后果，給人們帶來了很多的教訓。從這些教訓中我們可以總結出：軟件開發(fā)過程中軟件測試對最后軟件成功與否意義重大。當然，隨著計算機的普及，各種軟件進入了人們的視野。從普通的軟件到一些專業(yè)的軟件，軟件的應用領域非常廣泛，規(guī)模也是非常龐大?，F(xiàn)在人們面臨的技術層面的難題就是如何在琳瑯滿目的軟件當中選擇符合人們要求的軟件，如何在符合要求的基礎上確保這些軟件的質量及可靠性。軟件的一些很小的差錯就有可能對國家、財產、軍事、航天事業(yè)