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

第十一章

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

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

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

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

軟件缺陷報(bào)告是軟件設(shè)計(jì)、開(kāi)發(fā)、維護(hù)過(guò)程中發(fā)現(xiàn)的軟件問(wèn)題的記錄，是測(cè)試人員和開(kāi)發(fā)人員之間重要的溝通工具。

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

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

報(bào)告分析的目的和意義

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

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

報(bào)告分析的目的和意義2．安全缺陷報(bào)告分析的背景

互聯(lián)網(wǎng)的快速發(fā)展導(dǎo)致各種網(wǎng)絡(luò)安全事件頻繁發(fā)生。軟件因?yàn)樽陨泶嬖谌毕荻馐芡饨缋霉魧?dǎo)致隱私泄露、非法提權(quán)、勒索等嚴(yán)重后果，從而給個(gè)人、企業(yè)、社會(huì)和國(guó)家造成嚴(yán)重威脅。

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

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

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

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

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

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

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

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

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

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

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

通常采用“卡片分類(lèi)法”來(lái)進(jìn)行樣本標(biāo)記，并通過(guò)FleissKappa系數(shù)衡量不同成員標(biāo)記結(jié)果之間的差異性?？ㄆ诸?lèi)法：

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

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

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

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

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

CVE

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

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

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

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

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

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

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

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

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

基于軟件度量的軟件缺陷

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

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

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

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

基于軟件度量的軟件缺陷

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

基于軟件度量的軟件缺陷

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

基于軟件度量的軟件缺陷

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

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

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

基于軟件度量的軟件缺陷

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

11.2.1

基于軟件度量的軟件缺陷

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

11.2.1

基于軟件度量的軟件缺陷

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

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

11.2.1

基于軟件度量的軟件缺陷

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

基于上述混淆矩陣，我們將已有研究工作中常用的模型性能評(píng)測(cè)指標(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ù)測(cè)模型性能評(píng)估指標(biāo)11.2.4軟件缺陷預(yù)測(cè)常用評(píng)測(cè)數(shù)據(jù)集NASA數(shù)據(jù)集PROMISE數(shù)據(jù)集AEEEM數(shù)據(jù)集Relink數(shù)據(jù)集第十一章智能軟件測(cè)試技術(shù)11.3基于搜索的軟件測(cè)試方法11.3.1智能搜索算法11.3.2搜索技術(shù)在軟件測(cè)試中的應(yīng)用11.3.1智能搜索算法

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

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

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

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

信息素濃度的大小表征路徑的遠(yuǎn)近，吸引其他的螞蟻過(guò)來(lái)，這樣越來(lái)越多的螞蟻會(huì)找到食物。

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