第十一章 智能軟件測試技術

第十一章

智能軟件測試技術授課教師：

鄭煒第十一章智能軟件測試技術11.1基于機器學習的軟件缺陷報告分析11.1.1基于機器學習的軟件缺陷報告分析的目的和意義11.1.2

安全缺陷檢測數(shù)據(jù)集的構造11.1.3基于深度學習的安全缺陷報告檢測11.2基于軟件度量的軟件缺陷預測方法11.2.1基于軟件度量的軟件缺陷預測的目的和意義11.2.2軟件缺陷預測模型的構建11.2.3軟件缺陷預測模型性能評估指標

11.2.4軟件缺陷預測常用評測數(shù)據(jù)集第十一章智能軟件測試技術11.3基于搜索的軟件測試方法11.3.1智能搜索算法11.3.2搜索技術在軟件測試中的應用

軟件缺陷報告是軟件設計、開發(fā)、維護過程中發(fā)現(xiàn)的軟件問題的記錄，是測試人員和開發(fā)人員之間重要的溝通工具。

常見的軟件缺陷報告管理過程如圖11-1所示，該過程包括重復檢測、設置嚴重性和優(yōu)先級、分配合適的開發(fā)人員、軟件缺陷定位、軟件缺陷修復，以及回歸驗證這幾個關鍵步驟。11.1.1

基于機器學習的軟件缺陷

報告分析的目的和意義

為了提高軟件缺陷報告管理效率、降低軟件缺陷管理成本，需要進行自動化軟件缺陷報告分析。1．自動化軟件缺陷報告分析涉及的主要方面針對軟件缺陷報告的一系列分析研究，主要涉及以下5個方面。（1）重復軟件缺陷報告檢測（2）高影響力軟件缺陷報告識別（3）軟件缺陷報告優(yōu)先級和嚴重性預測（4）軟件缺陷/故障定位（5）自動程序修復11.1.1

基于機器學習的軟件缺陷

報告分析的目的和意義2．安全缺陷報告分析的背景

互聯(lián)網的快速發(fā)展導致各種網絡安全事件頻繁發(fā)生。軟件因為自身存在缺陷而遭受外界利用攻擊導致隱私泄露、非法提權、勒索等嚴重后果，從而給個人、企業(yè)、社會和國家造成嚴重威脅。

研究表明，互聯(lián)網面臨的安全攻擊（如拒絕服務攻擊、緩沖區(qū)溢出、SQL

注入、病毒、數(shù)據(jù)篡改等）幾乎都是利用軟件中存在的安全漏洞實施的。11.1.1

基于機器學習的軟件缺陷

報告分析的目的和意義圖11-2所示的是從2010年到2019年CVE網站每年新增的漏洞數(shù)量。從2010年開始每年至少新增4000條記錄，特別地，從2017年開始數(shù)量出現(xiàn)猛烈增長，近三年（2017年—2019年）產生數(shù)據(jù)總量為43444條記錄，占近十年（2010年—2019年）數(shù)據(jù)總量的52%。11.1.1

基于機器學習的軟件缺陷

報告分析的目的和意義11.1.2安全缺陷檢測數(shù)據(jù)集的構造

數(shù)據(jù)是機器學習應用的基礎，基于機器學習的軟件缺陷報告分析，首先需要有大規(guī)模帶標記的軟件缺陷報告數(shù)據(jù)的支持。

用于安全缺陷檢測的數(shù)據(jù)集構造主要以開源的軟件缺陷報告數(shù)據(jù)倉庫（如JIRA、Bugzilla、LaunchPad）和開源漏洞數(shù)據(jù)庫（如CVE、NVD、SARD）為數(shù)據(jù)源。1．安全漏洞數(shù)據(jù)庫CVE

對于開源項目，CVE詳細信息頁面的“參考”部分列出了相關源軟件缺陷報告的鏈接，這些鏈接連接了CVE條目和源軟件缺陷報告，因此，為安全缺陷檢測數(shù)據(jù)集的構造提供了極大的便利。2．人工樣本標記

當前，在軟件工程領域，許多樣本數(shù)據(jù)的標記依然在很大程度上依賴領域專家知識，主要靠人工標記的方式來完成，面向安全缺陷報告分析的樣本標記亦是如此。

安全缺陷報告檢測自動化過程中，通常將安全缺陷報告檢測形式化為一個二分類問題。即，與安全相關的軟件缺陷報告（SecurityBugReport，SBR），標記為“1”；與安全不相關的缺陷報告（Non-SecurityBugReport，NSBR），標記為“0”。11.1.2安全缺陷檢測數(shù)據(jù)集的構造

通常采用“卡片分類法”來進行樣本標記，并通過FleissKappa系數(shù)衡量不同成員標記結果之間的差異性?？ㄆ诸惙ǎ?/p>

組織至少兩名成員對樣本數(shù)據(jù)進行獨立標記；然后，根據(jù)各成員標記結果判斷最終樣本標簽，如果不同成員的標記結果一致，則該標簽為該樣本的最終標簽；如果各成員標記結果不同，則成員進行溝通討論，直到達成一致標記結果為止。FleissKappa系數(shù)是檢驗實驗標注結果數(shù)據(jù)一致性的一個重要指標。FleissKappa對于評定條件屬性與條件屬性之間的相關程度有很大幫助。11.1.2安全缺陷檢測數(shù)據(jù)集的構造

設N為被評定對象的總數(shù)，n為評定對象的總數(shù)，k為評定的等級數(shù)，nij為第j個評定對象對第i個被評對象劃分的等級數(shù)，則系數(shù)的計算公式為：11.1.2安全缺陷檢測數(shù)據(jù)集的構造3．自動化樣本標記預處理

面向軟件缺陷報告分析的自動化樣本標記方法的相關研究目前尚處于初期探索階段。具體的自動化樣本標記預處理過程主要涉及數(shù)據(jù)析取、數(shù)據(jù)清洗及數(shù)據(jù)融合3個主要階段。（1）數(shù)據(jù)析取

首先從軟件缺陷跟蹤系統(tǒng)（如JIRA、Bugzilla、LaunchPad）獲取軟件項目的缺陷報告數(shù)據(jù)極其詳細信息，一般而言，一個軟件缺陷報告主要包括：ID、標題（Title）、提交人員（Reporter）、軟件缺陷修復人員（Assignee）、狀態(tài)（Status）、優(yōu)先級（Priority）嚴重程度（Severity/Importance）以及描述信息（Description）等字段。11.1.2安全缺陷檢測數(shù)據(jù)集的構造表11-1所示的是OpenStack項目中一個軟件缺陷報告的具體示例。11.1.2安全缺陷檢測數(shù)據(jù)集的構造11.1.2安全缺陷檢測數(shù)據(jù)集的構造

自動化樣本標記過程一般需要借助一部分已經標記的樣本信息。對于安全缺陷而言，CVE是當前國際權威的漏洞數(shù)據(jù)庫，提交到

CVE

的軟件缺陷可以認為都是跟安全相關的缺陷，因此，用戶可以借助CVE進行一部分的安全缺陷樣本標記。11.1.2安全缺陷檢測數(shù)據(jù)集的構造（2）數(shù)據(jù)清洗

軟件缺陷報告分析往往以描述信息作為關鍵分析內容，因此描述信息量過少，甚至為空的軟件缺陷報告往往不適合進行自動化軟件缺陷報告分析。數(shù)據(jù)清洗旨在對數(shù)據(jù)進行結構化和歸一化等操作，過濾掉存在關鍵信息缺失等現(xiàn)象的無效數(shù)據(jù)。（3）數(shù)據(jù)融合

自動關聯(lián)多源數(shù)據(jù)之間的關系，例如，圖11-3所示的是CVE數(shù)據(jù)與原始軟件缺陷報告建立管理關系，從而獲取到該軟件缺陷報告的標記類型為安全缺陷報告。數(shù)據(jù)融合中獲取的已標記樣本數(shù)據(jù)將為后續(xù)自動樣本標記模型的設計和構建提供樣本數(shù)據(jù)基礎。11.1.2安全缺陷檢測數(shù)據(jù)集的構造4．面向安全缺陷報告檢測的自動化樣本標記方法

與人工標記過程類似，自動化樣本標記中，依然采用SBR表示安全相關缺陷報告，標記為“1”；用NSBR表示與安全不相關的缺陷報告，標記為“0”。（1）OpenStack簡介OpenStack是一個由美國國家航空航天局（NationalAeronauticsandSpaceAdministration，NASA）和Rackspace公司合作發(fā)起的開源云管理平臺，該平臺包含多個用于構建云平臺的組件（如Nova、Neutron、Swift、Cinder等）。11.1.2安全缺陷檢測數(shù)據(jù)集的構造（2）基于迭代式投票方法的自動化樣本標記

圖11-4所示的為迭代式自動化樣本標記方法示意圖，其具體過程分為兩個階段：初始數(shù)據(jù)準備和迭代式投票分類。11.1.2安全缺陷檢測數(shù)據(jù)集的構造基于迭代式投票方法的自動化樣本標記算法的具體步驟描述如下。步驟1：初始訓練樣本標記。該階段包括兩個輸入和兩個輸出。輸入：CVE數(shù)據(jù)和未標記樣本Ball；輸出：已標記初始訓練樣本集Bl和剩余未標記樣本集Bu。步驟2：迭代投票式自動分類?；谲浖毕輬蟾嬷邪踩┒聪嚓P軟件缺陷報告分布稀疏特征，利用3個不同文本分類器，設計了一種迭代式自動投票分類方法，其包括3個輸入和3個輸出。輸入：已標記訓練樣本集Bl、未標記目標數(shù)據(jù)集Bu、3個分類器。輸出：預測為正的樣本集合Bppos、預測為負的樣本集合Bpneg、不確定樣本集合Bpu11.1.2安全缺陷檢測數(shù)據(jù)集的構造最終輸出結果如表11-3所示。預測結果為負樣本Bppos、Bpneg和Bpu所占比例分別為0.15%、99.27%和0.58%。11.1.2安全缺陷檢測數(shù)據(jù)集的構造11.1.3基于深度學習的安全缺陷報告檢測基于深度學習的SBR預測方法框架如圖11-5所示，其包含如下4個階段。階段1：執(zhí)行BR數(shù)據(jù)集的收集與劃分。階段2：執(zhí)行文本預處理。該階段將文本數(shù)據(jù)預處理成數(shù)字序列，深度學習模型可以方便地根據(jù)序列獲得單詞的表示（詞向量）。階段

3：進行深度學習模型的構建。我們一共選擇了兩種適合文本挖掘的深度學習模型，分別是TextCNN和TextRNN。這兩個模型分別衍生自經典的CNN模型和RNN模型，選用這兩個具有代表性的模型可以確保我們實證研究的結論更有代表性。階段4：目標數(shù)據(jù)預測與輸出。從未標記的軟件缺陷報告中預測中SBR，并對結果進行輸出。11.1.3基于深度學習的安全缺陷報告檢測1．文本預處理文本預處理時依次執(zhí)行移除停頓詞、句子填充、建立詞匯—索引映射表和建立詞嵌入矩陣。（1）移除停頓詞（2）句子填充（3）建立詞匯—索引映射表（4）建立詞嵌入矩陣11.1.3基于深度學習的安全缺陷報告檢測2．深度學習模型構建關于深度學習模型構建，下面主要考慮了兩種深度學習模型TextCNN和TextRNN，并采用注意力機制對模型進行優(yōu)化。（1）TextCNN模型11.1.3基于深度學習的安全缺陷報告檢測（2）TextRNN模型11.1.3基于深度學習的安全缺陷報告檢測（3）注意力機制

進一步借助注意力機制（AttentionMechanism）對TextRNN模型進行優(yōu)化。SBR的識別主要依賴于BR中的描述信息（Description），采用自然語言描述形式，其安全相關文本特征較為稀疏，給SBR預測準確性帶來一定困難。

注意力機制源于對人類視覺的研究，使訓練重點集中在輸入數(shù)據(jù)的相關部分，而忽略無關部分。11.1.3基于深度學習的安全缺陷報告檢測（4）深度學習模型有效性

為了驗證深度學習模型對于安全缺陷報告檢測的有效性，采用公開數(shù)據(jù)集Ambari、Camel、Derby、Wicket和OpenStack對其進行驗證，通過與傳統(tǒng)分類算法樸素貝葉斯（NaiveBayes，NB）、邏輯回歸（LogisticRegression，LR）、K-近鄰算法（K-NearestNeighbor）進行對比。11.1.3基于深度學習的安全缺陷報告檢測第十一章智能軟件測試技術11.1基于機器學習的軟件缺陷報告分析11.2基于軟件度量的軟件缺陷預測方法11.2.1基于軟件度量的軟件缺陷預測的目的和意義11.2.2軟件缺陷預測模型的構建11.2.1

基于軟件度量的軟件缺陷

預測的目的和意義

軟件缺陷預測屬于當前軟件工程數(shù)據(jù)挖掘領域中的一個重要研究問題。隨著新的數(shù)據(jù)挖掘技術的不斷涌現(xiàn)，以及研究人員對軟件歷史倉庫挖掘的日益深入，軟件缺陷預測研究在近些年來取得了大量的研究成果，其軟件缺陷預測結果也逐漸成為判斷一個系統(tǒng)是否可以交付使用的重要依據(jù)。

因此針對該問題的深入研究，對提高和保障軟件產品的質量具有重要的研究意義。

軟件缺陷預測可以將程序模塊的缺陷傾向性、缺陷密度或缺陷數(shù)設置為預測目標。以預測模塊的缺陷傾向性為例，其典型框架如圖11-8所示。11.2.1

基于軟件度量的軟件缺陷

預測的目的和意義該過程主要包括兩個階段：模型構建階段和模型應用階段。具體來說，模型構建階段包括以下3個步驟。①挖掘軟件歷史倉庫，從中抽取程序模塊。②通過分析軟件代碼或開發(fā)過程設計出與軟件缺陷存在相關性的度量元，借助這些度量元對程序模塊進行軟件度量并構建出軟件缺陷預測數(shù)據(jù)集。③對軟件缺陷預測數(shù)據(jù)集進行必要的數(shù)據(jù)預處理（如噪聲移除、特征子集選擇、數(shù)據(jù)歸一化等）后，借助特定的建模方法構建出軟件缺陷預測模型。11.2.1

基于軟件度量的軟件缺陷

預測的目的和意義1．對程序模塊的度量隨著面向對象開發(fā)方法的普及，面向對象開發(fā)方法特有的封裝、繼承和多態(tài)等特性給傳統(tǒng)的軟件度量提出了挑戰(zhàn)，于是研究人員提出了適用于面向對象程序的度量元，其中最為典型的是Chidamber和Kemerer提出的CK度量元。11.2.1

基于軟件度量的軟件缺陷

預測的目的和意義2．軟件缺陷預測模型的構建方法

目前大部分研究工作都基于機器學習的方法來構建軟件缺陷預測模型。其中常見的模型預測目標可以大致分為兩類：一類是預測程序模塊內含有的缺陷數(shù)或缺陷密度；另一類是預測程序模塊的缺陷傾向性。

有研究人員設計出了BugCache方法，該方法主要考慮了如下的軟件缺陷局部性原理：①修改模塊局部性：即一個程序模塊，若最近被修改過，則將來可能還會含有軟件缺陷。②新增模塊局部性：即一個程序模塊，若是最近新增加的，則將來可能還會含有軟件缺陷。11.2.1

基于軟件度量的軟件缺陷

預測的目的和意義③時間局部性：即一個程序模塊，若最近檢測出一個軟件缺陷，則將來可能也會含有其他軟件缺陷。④空間局部性：即一個程序模塊，若最近檢測出一個軟件缺陷，則將來它附近的程序模塊可能也會含有軟件缺陷。

11.2.1

基于軟件度量的軟件缺陷

預測的目的和意義3．軟件缺陷預測數(shù)據(jù)集的質量問題（1）數(shù)據(jù)集內的噪聲問題（2）數(shù)據(jù)集內的維數(shù)災難問題（3）數(shù)據(jù)集中的類不平衡問題

11.2.1

基于軟件度量的軟件缺陷

預測的目的和意義4．跨項目軟件缺陷預測方法

基于已有跨項目軟件缺陷預測的研究成果分析，可以簡單總結出如下3個場景。①僅存在與目標項目T相關的候選源項目的集合S={S_1,S_2,…,S_n}。其中T對應的數(shù)據(jù)集為t，候選源項目S_i對應的數(shù)據(jù)集為s_i。②不僅存在與目標項目T相關的候選源項目的集合S，而且在T中存在少量已標記的目標項目模塊，并將這些已標記的模塊記為tl。③難以找到與目標項目T相關的候選源項目，同時目標項目中也不存在已標記的模塊。

11.2.1

基于軟件度量的軟件缺陷

預測的目的和意義11.2.2軟件缺陷預測模型的構建11.2.3軟件缺陷預測模型性能評估指標

基于上述混淆矩陣，我們將已有研究工作中常用的模型性能評測指標總結如下。（1）準確率（Accuracy）（2）查準率（Precision）（3）查全率（Recall）（4）虛警概率（5）F-measure（6）G-measure

（7）Balance

（8）G-mean

（9）MCC11.2.3軟件缺陷預測模型性能評估指標11.2.4軟件缺陷預測常用評測數(shù)據(jù)集NASA數(shù)據(jù)集PROMISE數(shù)據(jù)集AEEEM數(shù)據(jù)集Relink數(shù)據(jù)集第十一章智能軟件測試技術11.3基于搜索的軟件測試方法11.3.1智能搜索算法11.3.2搜索技術在軟件測試中的應用11.3.1智能搜索算法

基于搜索的軟件測試的基石是高性能的搜索算法，目前軟件工程領域中用到的搜索方法分為3大類：第1類是基于微積分的搜索方法第2類是帶有向導的隨機搜索方法第3類是枚舉方法主要介紹第2類帶有向導的隨機搜索方法：1．遺傳算法

遺傳算法是一種模擬自然界生物進化過程的啟發(fā)式搜索算法。它屬于演化算法的一種，借鑒了進化生物學中的一些現(xiàn)象，這些現(xiàn)象通常包括遺傳、突變、自然選擇，以及雜交等。

遺傳算法操作步驟中關鍵的幾步操作為：從問題空間得到信息編碼、染色體交叉，以及適應度函數(shù)的構造。11.3.1智能搜索算法主要介紹第2類帶有向導的隨機搜索方法：2．蟻群算法

蟻群算法的各個螞蟻在沒有事先被告訴食物在什么地方的前提下開始尋找食物，當一只螞蟻找到食物以后，它會向環(huán)境釋放一種揮發(fā)性分泌物信息素（Pheromone），該物質隨著時間的推移會逐漸揮發(fā)消失。

信息素濃度的大小表征路徑的遠近，吸引其他的螞蟻過來，這樣越來越多的螞蟻會找到食物。

11.3.1智能搜索算法主要介紹第2類帶有向導的隨機搜索方法：2．蟻群算法關于蟻群算法的幾個比較重要的規(guī)則：①范圍②環(huán)境③覓食規(guī)則④移動規(guī)則⑤避障規(guī)則⑥信息素規(guī)則11.3.1智能搜索算法主要介紹第2類帶有向導的隨機搜索方法：2．蟻群算法蟻群算法有以下4個基本的特點：①蟻群算法是一種自組織的算法②蟻群算法是一種本質上并行的算法③蟻群算法是一種正反饋的算法④蟻群算法具有較強的魯棒性11.3.1智能搜索算法3．其他智能優(yōu)化算法（1）人工魚群算法（2）禁忌搜索算法（3）人工免疫算法（4）粒子群算法（5）爬山算法（6）模擬退火算法11.3.1智能搜索算法11.3.2搜索技術在軟件測試中的應用1．基于搜索的測試用例自動生成（1）功能測試用例生成方法（2）結構測試用例生成方法1．基于搜索的測試用例自動