基于行為聲明的可信測試用例生成的方法分析報(bào)告目錄TOC\o"1-3"\h\u16604基于行為聲明的可信測試用例生成的方法分析報(bào)告 1120731.1遺傳算法分析 132531.1.1基本遺傳算法的不足 190651.1.2遺傳算法的改進(jìn)策略 159381.2可信測試用例自動(dòng)生成方法 25981.3測試環(huán)境構(gòu)造 4253111.3.1行為聲明解析 4151271.3.2參數(shù)編碼 5260841.3.3程序插樁和適應(yīng)度函數(shù)設(shè)計(jì) 6103181.4參數(shù)自適應(yīng)的遺傳算法實(shí)現(xiàn) 6166571.1.1種群初始化 675391.1.2改進(jìn)選擇算子 7631.1.3自適應(yīng)交叉和變異算子 8277031.1.4自適應(yīng)遺傳算法實(shí)現(xiàn)流程 91.1遺傳算法分析遺傳算法作為一種智能搜索算法經(jīng)常被用于測試用例的自動(dòng)生成中，但是基本的遺傳算法在測試用例生成方面存在一些不足，本文使用參數(shù)自適應(yīng)的遺傳算法（Parameteradaptivegeneticalgorithm，PAGA）通過動(dòng)態(tài)的調(diào)整遺傳算子參數(shù)的方式來實(shí)現(xiàn)算法優(yōu)化。1.1.1基本遺傳算法的不足（1）將遺傳算法應(yīng)用到Web的可信測試用例生成過程中，要解決的關(guān)鍵問題是避免過早收斂，使總體陷入局部最優(yōu)解。種群的進(jìn)化過程是以種群的多樣性為基礎(chǔ)的，早熟收斂與后期個(gè)體收斂性增強(qiáng)和種群多樣性降低有關(guān)。（2）在進(jìn)行遺傳操作時(shí)，遺傳算子的執(zhí)行需要用到參數(shù)包括交叉率、變異率等，這些參數(shù)的設(shè)置會(huì)影響尋優(yōu)速度和和最優(yōu)解的質(zhì)量，并且參數(shù)的設(shè)置一般都是依靠經(jīng)驗(yàn)并且設(shè)置參數(shù)值的大小固定。算法交叉和變異率如果設(shè)置的過大，在算法后期不利于種群向最優(yōu)解收斂；如果設(shè)置過小，算法初期的種群多樣性將會(huì)降低。1.1.2遺傳算法的改進(jìn)策略通過第二章對基本遺傳算法的分析和描述，可以知道決定遺傳算法性能好壞的關(guān)鍵因素在于它的參數(shù)配置方式，通常在配置參數(shù)時(shí)，都是基于經(jīng)驗(yàn)值或通過幾組對比實(shí)驗(yàn)來確定算法的參數(shù)值的大小，并且算法的參數(shù)一般都設(shè)置成固定值。自適應(yīng)參數(shù)的思想是基于遺傳算法的運(yùn)行狀態(tài)來動(dòng)態(tài)的調(diào)整算法參數(shù)，使得算法在執(zhí)行過程中的任何時(shí)刻都能使用最佳的參數(shù)值，以此來實(shí)現(xiàn)對遺傳算法優(yōu)化。本文提到的自適應(yīng)參數(shù)主要指的是遺傳算法的變異率和交叉率，通過當(dāng)前種群平均適應(yīng)度和種群最佳適應(yīng)度的值來計(jì)算和更新這些參數(shù)值。除此之外，在執(zhí)行選擇操作時(shí)結(jié)合“精英保留”的策略機(jī)制來實(shí)現(xiàn)，通過保留每一代中最優(yōu)良的個(gè)體直接遺傳到下一代來保障優(yōu)良的基因不會(huì)丟失，使種群向更優(yōu)的方向進(jìn)化。1.2可信測試用例自動(dòng)生成方法軟件測試是保障軟件產(chǎn)品質(zhì)量的重要方式，傳統(tǒng)的測試方法會(huì)消耗大量的人力、物力和時(shí)間資源，并且測試用例的編寫是軟件測試中耗時(shí)最長的工作，測試用例一般都由測試人員手工編寫，會(huì)導(dǎo)致測試成本高，效率低的問題。遺傳算法作為經(jīng)典的尋優(yōu)算法，在測試用例生成上也已經(jīng)有很成熟的應(yīng)用，本文將使用遺傳算法結(jié)合可信行為聲明來實(shí)現(xiàn)可信測試用例的自動(dòng)生成。實(shí)現(xiàn)的基本流程如圖4-1所示。圖4-1基于自適應(yīng)遺傳算法的測試用例自動(dòng)生成模型Fig.4-1Automatictestcasegenerationmodelbasedonadaptivegeneticalgorithm本文的可信測試用例自動(dòng)生成模型中，包含有三個(gè)模塊：行為聲明解析模塊、測試環(huán)境構(gòu)造模塊和算法實(shí)現(xiàn)模塊。行為聲明解析模塊，需要將可信行為聲明的內(nèi)容進(jìn)行解析提取行為路徑和行為參數(shù)，并對所有參數(shù)進(jìn)行編碼；測試環(huán)境構(gòu)造模塊，需要根據(jù)提取的行為路徑對源程序進(jìn)行靜態(tài)分析，并對測試路徑進(jìn)行插樁，構(gòu)建適應(yīng)度函數(shù)，為算法的實(shí)現(xiàn)做準(zhǔn)備；最后是算法實(shí)現(xiàn)模塊，根據(jù)參數(shù)編碼結(jié)果以及要解決問題的規(guī)模，設(shè)置遺傳算法的種群規(guī)模、初始的交叉率和變異率等參數(shù)，根據(jù)個(gè)體的適應(yīng)度值來執(zhí)行選擇操作，最終得到分支覆蓋率最高的測試用例，結(jié)束算法。1.3測試環(huán)境構(gòu)造1.3.1行為聲明解析本文采用行為聲明和遺傳算法結(jié)合的方式生成測試用例，遺傳算法將在行為聲明解析結(jié)果的基礎(chǔ)上實(shí)現(xiàn)。本文采用dom4j的方式，實(shí)現(xiàn)對xml格式定義的可信行為聲明進(jìn)行解析，具體流程如下：（1）提取行為參數(shù)。提取行為規(guī)則中定義的行為名稱、行為id、技術(shù)參數(shù)和可信等級等信息。（2）劃分行為參數(shù)。行為聲明中的行為參數(shù)是該行為能否正常執(zhí)行的關(guān)鍵，不同的技術(shù)參數(shù)對應(yīng)不同的可信等級，針對相同的行為參數(shù)，不同參數(shù)值對應(yīng)不同的可信等級，根據(jù)行為聲明中的可信等級把行為參數(shù)劃分為可信參數(shù)和可疑參數(shù)和危險(xiǎn)參數(shù)?？尚艆?shù)將作為該參數(shù)的有效等價(jià)類，可疑和危險(xiǎn)參數(shù)作為參數(shù)的無效等價(jià)類。（3）參數(shù)補(bǔ)充。根據(jù)可信行為聲明的解析結(jié)果，用戶可以針對缺少等價(jià)類的參數(shù)手動(dòng)輸入?yún)?shù)值，使得所有參數(shù)都有對應(yīng)的有效參數(shù)值和無效參數(shù)值，利于在測試用例生成過程中實(shí)現(xiàn)全路徑覆蓋。針對第三章中文件上傳的行為聲明解析得到的結(jié)果，并且對未覆蓋的參數(shù)進(jìn)行輸入，得到表4-1所示的行為聲明解析結(jié)果。表4-1行為聲明解析結(jié)果Tab.4-1BehaviordeclarationparsingresultsPermission行為名稱觸發(fā)參數(shù)觸發(fā)值可信等級AdminUpload_filetypejpg/pngSafetyAdminUpload_filetypeexeDangerousAdminUpload_filesize≤1024SafetyAdminUpload_filesize>1024Dangerous并根據(jù)行為聲明及用戶輸入值來劃分等價(jià)類，結(jié)果如表4-2所示。表4-2等價(jià)類劃分結(jié)果Tab.4-2ResultsofequivalenceclassdivisionPermission行為名稱觸發(fā)參數(shù)有效參數(shù)值無效參數(shù)值adminUpload_filetypejpg/pngexeadminUpload_filesize≤1024>10241.3.2參數(shù)編碼編碼是遺傳算法中的關(guān)鍵環(huán)節(jié)，是問題的解空間向算法空間映射的過程，編碼的好壞直接影響到遺傳算法解決實(shí)際問題的效率。本文的參數(shù)編碼主要是對行為聲明中定義的行為參數(shù)編碼。由于二進(jìn)制編碼更符合生物遺傳過程中XY染色體的基因構(gòu)成，在算法實(shí)現(xiàn)過程中進(jìn)行交叉和變異操作更加方便，因此，本文采用二進(jìn)制的方式對行為聲明中的技術(shù)參數(shù)進(jìn)行編碼，流程如下：首先，根據(jù)行為聲明的解析結(jié)果，結(jié)合手動(dòng)輸入?yún)?shù)，行為聲明中每一個(gè)行為參數(shù)都對應(yīng)有可信參數(shù)值和不可信參數(shù)值，分別對應(yīng)的是可信等級中的安全等級和危險(xiǎn)等級如圖4-2所示。行為參數(shù)行為參數(shù)不可信參數(shù)值可信參數(shù)值可信行為可疑行為危險(xiǎn)行為圖4-2行為參數(shù)劃分規(guī)則Fig.4-2Behaviorparameterpartitionrules根據(jù)參數(shù)的劃分，把解析出來的行為參數(shù)使用二維數(shù)組的方式來進(jìn)行存儲，二維數(shù)組的表示如下：parmeterArray=String[2][parameterNumber]（4-1）ParameterArray[2][2]=jpg/png≤1024Exe＞1024ParameterArray[2][2]=jpg/png≤1024Exe＞1024（4-2）因此參數(shù)編碼可選擇00,01,10,11四種，并且每一種編碼方式都對應(yīng)的一組參數(shù)值，即對應(yīng)一組行為聲明。當(dāng)編碼長度較長時(shí)，將會(huì)在遺傳算法的種群初始化時(shí)隨機(jī)生成。1.3.3程序插樁和適應(yīng)度函數(shù)設(shè)計(jì)適應(yīng)度函數(shù)是遺傳算法與實(shí)際解決問題連接的紐帶，用來評價(jià)算法進(jìn)化過程中種群個(gè)體的優(yōu)劣[55]，優(yōu)秀的適應(yīng)度函數(shù)會(huì)引導(dǎo)種群逐代向最優(yōu)解進(jìn)化，其設(shè)計(jì)的好壞會(huì)影響算法的收斂速度和最終生成解的質(zhì)量。本文在利用遺傳算法實(shí)現(xiàn)Web應(yīng)用的可信測試用例的生成中，采用分支路徑覆蓋率來評價(jià)測試用例的優(yōu)劣。MBranchCoverage=在適應(yīng)度函數(shù)構(gòu)造之前，首先根據(jù)種群規(guī)模populationSize（記為n），和被測路徑的分支數(shù)BranchNumber（記為m）構(gòu)建一個(gè)二維數(shù)組BranchCoverage[m][n],使用該數(shù)組存儲當(dāng)代種群中個(gè)體的分支覆蓋情況，二維數(shù)組的所有元素初始化為0。當(dāng)被測程序中第i（1≤i≤m）個(gè)分支路徑被種群中的第j（1≤j≤n）個(gè)個(gè)體覆蓋時(shí)，設(shè)置BranchCoverage[i][j]=1，以此來記錄分支覆蓋信息，需要使用程序插樁技術(shù)將該賦值語句放入被測程序中。將種群的分支覆蓋信息以矩陣的形式表示如下： MBranchCoverage=其中，矩陣的每一行都代表一個(gè)分支路徑被種群覆蓋的情況，每一列代表每個(gè)個(gè)體覆蓋分支的情況。本文根據(jù)個(gè)體的分支覆蓋率來評價(jià)優(yōu)劣，種群中個(gè)體適應(yīng)度函數(shù)計(jì)算公式為： fXj=i=1對于以上分支覆蓋矩陣，當(dāng)j=1j=nbij≥1（i值固定）時(shí)，則表明第i個(gè)分支路徑至少被當(dāng)前種群的一個(gè)個(gè)體覆蓋，此時(shí)設(shè)置flag[i]=11.4參數(shù)自適應(yīng)的遺傳算法實(shí)現(xiàn)1.1.1種群初始化Algorithm:populationinitialization本文將根據(jù)被測路徑的復(fù)雜程度來確定種群的規(guī)模，并在種群初始化過程中，需要使用可信行為聲明解析結(jié)果，使用parameterArray[][]存放參數(shù)的數(shù)組進(jìn)行種群初始化，種群初始化算法偽代碼表示如下:Algorithm:populationinitializationBeginInput:parameterArray[][]//輸入存放行為參數(shù)的二維數(shù)組Set:populationSize,chromosomeSize//分別為種群規(guī)模和染色體長度Fori←0topopulationSizeForj←0tochromosomeSize randomItem←0or1Chromosome[i]=chromosome[i]+ramdomItemEndforpopulation[i]+=chromosome[i]EndforOutput:populationEnd在種群初始化算法中，將上一節(jié)中得到的存放參數(shù)的二維數(shù)組parameterArray[][]作為種群初始化過程中染色體基因的選擇空間，染色體的長度等于參數(shù)種類數(shù)n，即二維數(shù)組的列數(shù)。每個(gè)參數(shù)都對應(yīng)的一個(gè)有效參數(shù)值和一個(gè)無效參數(shù)值，因此二維數(shù)組的行數(shù)為2，在隨機(jī)生成染色體時(shí)，只需隨機(jī)生成長度為n的二進(jìn)制編碼串即為染色體。（1）步驟5至步驟8是在隨機(jī)生成染色體，步驟6中隨機(jī)數(shù)randomItem取值0或1，來定義染色體的某個(gè)基因取值對應(yīng)的是參數(shù)值的有效等價(jià)類還是無效等價(jià)類，循環(huán)結(jié)束得到的chromosome[i]二進(jìn)制編碼串即為第i個(gè)染色體參數(shù)編碼結(jié)果。（2）步驟4至步驟10是在初始化種群，通過for循環(huán)來初始化與種群規(guī)模大小相等數(shù)量的染色體，算法最后將初始化的種群輸出。1.1.2改進(jìn)選擇算子選擇算子是挑選優(yōu)秀個(gè)體和優(yōu)秀基因進(jìn)入到下一代種群的操作，種群中個(gè)體被選擇的概率與其適應(yīng)度的大小成正比，適應(yīng)度越高，被選擇的可能性越大，反之則越小。本文采用“輪盤賭”結(jié)合“精英保留”的方式進(jìn)行選擇操作，簡稱改進(jìn)的選擇算法?！拜啽P賭”選擇法能確保算法傾向于選擇適應(yīng)度更高的個(gè)體進(jìn)行遺傳操作，優(yōu)秀基因遺傳給下一代的概率更高；“精英保留”是將當(dāng)代種群中最優(yōu)秀的個(gè)體直接遺傳到下一代種群中的操作。假設(shè)種群規(guī)模大小為M，某個(gè)個(gè)體的適應(yīng)度大小為fi，則該個(gè)體被選擇的概率為：P=fii=1Mfi通過把兩種方式結(jié)合，不僅可以提高種群在進(jìn)行遺傳操作的基因多樣性，也可以避免優(yōu)秀基因在進(jìn)化過程中丟失，提升種群的進(jìn)化效率。1.1.3自適應(yīng)交叉和變異算子傳統(tǒng)的遺傳算法采用固定的交叉和變異概率來進(jìn)行遺傳操作，如果初始值設(shè)置的過高，則不利于算法后期種群收斂；若設(shè)置的初始值過低，則會(huì)導(dǎo)致搜索范圍小，容易使算法陷入局部最優(yōu)，不利于找到全局最優(yōu)解，本文采用動(dòng)態(tài)自適應(yīng)調(diào)整交叉和變異率的方式來實(shí)現(xiàn)對算法的優(yōu)化。（1）交叉操作（4-5）Pc=本文采用“均勻交叉”策略實(shí)現(xiàn)交叉操作，交叉率Pc的大小采用動(dòng)態(tài)自適應(yīng)調(diào)整的方式來設(shè)置，在算法初始化時(shí)設(shè)置一個(gè)較大的Pc值，用于提高種群的多樣性，在進(jìn)化過程中交叉率的動(dòng)態(tài)調(diào)整公式如下：

（4-5）Pc=fi代表當(dāng)前個(gè)體適應(yīng)度值，fmax代表當(dāng)代種群最佳適應(yīng)度值，favg代表當(dāng)代種群平均適應(yīng)度值，c為初始種群交叉率。當(dāng)fi>favg時(shí)，通過乘以前面的參數(shù)值可以減小交叉和變異率的值，以保留優(yōu)良的染色體基因；反之，當(dāng)fi≤favg時(shí)，則繼續(xù)使用初始的交叉和變異率的大小，以增大交叉和變異的概率，來保障種群的多樣性，避免種群過早收斂。（2）變異操作Pm=（4-6）變異操作也是遺傳算法中產(chǎn)生種群多樣性的重要算子，本文使用二進(jìn)制基本位變異的方式實(shí)現(xiàn)變異操作，變異概率Pm的大小也采用動(dòng)態(tài)自適應(yīng)的方式進(jìn)行調(diào)整，調(diào)整策略與交叉概率一致，調(diào)整公式如下：Pm=（4-6）m,fi≤favg其中m為算法初始變異率。1.1.4自適應(yīng)遺傳算法實(shí)現(xiàn)流程本文在基本遺傳算法實(shí)現(xiàn)上進(jìn)行了一定改進(jìn)，針對可信測試用例生成過程中路徑覆蓋的需求，對適應(yīng)度函數(shù)和程序插樁方法進(jìn)行了設(shè)計(jì)，并在交叉和變異操作過程中實(shí)現(xiàn)了參數(shù)自適應(yīng)。優(yōu)化后的算法偽代碼如下。GeneticalgorithmwithadaptiveparametersGeneticalgorithmwithadapti