第十一章 智能軟件測試技術(shù)

第十一章

智能軟件測試技術(shù)授課教師：

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

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

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

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

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

基于機器學(xué)習(xí)的軟件缺陷

報告分析的目的和意義

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

基于機器學(xué)習(xí)的軟件缺陷

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

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

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

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

基于機器學(xué)習(xí)的軟件缺陷

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

基于機器學(xué)習(xí)的軟件缺陷

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

數(shù)據(jù)是機器學(xué)習(xí)應(yīng)用的基礎(chǔ)，基于機器學(xué)習(xí)的軟件缺陷報告分析，首先需要有大規(guī)模帶標(biāo)記的軟件缺陷報告數(shù)據(jù)的支持。

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

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

當(dāng)前，在軟件工程領(lǐng)域，許多樣本數(shù)據(jù)的標(biāo)記依然在很大程度上依賴領(lǐng)域?qū)＜抑R，主要靠人工標(biāo)記的方式來完成，面向安全缺陷報告分析的樣本標(biāo)記亦是如此。

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

通常采用“卡片分類法”來進行樣本標(biāo)記，并通過FleissKappa系數(shù)衡量不同成員標(biāo)記結(jié)果之間的差異性。卡片分類法：

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

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

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

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

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

CVE

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

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

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

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

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

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

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

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

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

基于軟件度量的軟件缺陷

預(yù)測的目的和意義

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

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

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

基于軟件度量的軟件缺陷

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

基于軟件度量的軟件缺陷

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

基于軟件度量的軟件缺陷

預(yù)測的目的和意義2．軟件缺陷預(yù)測模型的構(gòu)建方法

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

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

基于軟件度量的軟件缺陷

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

11.2.1

基于軟件度量的軟件缺陷

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

11.2.1

基于軟件度量的軟件缺陷

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

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

11.2.1

基于軟件度量的軟件缺陷

預(yù)測的目的和意義11.2.2軟件缺陷預(yù)測模型的構(gòu)建11.2.3軟件缺陷預(yù)測模型性能評估指標(biāo)

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

（7）Balance

（8）G-mean

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

基于搜索的軟件測試的基石是高性能的搜索算法，目前軟件工程領(lǐng)域中用到的搜索方法分為3大類：第1類是基于微積分的搜索方法第2類是帶有向?qū)У碾S機搜索方法第3類是枚舉方法主要介紹第2類帶有向?qū)У碾S機搜索方法：1．遺傳算法

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

遺傳算法操作步驟中關(guān)鍵的幾步操作為：從問題空間得到信息編碼、染色體交叉，以及適應(yīng)度函數(shù)的構(gòu)造。11.3.1智能搜索算法主要介紹第2類帶有向?qū)У碾S機搜索方法：2．蟻群算法

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

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

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