摘? 要：文章對(duì)適應(yīng)性隨機(jī)測(cè)試?yán)碚摶A(chǔ)進(jìn)行分析，并在信息熵基礎(chǔ)上對(duì)測(cè)試用例算法加以闡述，主要包括信息熵指標(biāo)、算法應(yīng)用、實(shí)證實(shí)驗(yàn)三項(xiàng)內(nèi)容，通過文章研究可知，Entropy算法與其他算法相比，無論在高維還是低維空間情形下，均具有良好的失效檢測(cè)能力。

關(guān)鍵詞：信息熵;適應(yīng)性隨機(jī)測(cè)試;算法

中圖分類號(hào)：TP301.6? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2096-4706（2020）02-0030-02

Abstract：This paper analyzes the theoretical basis of adaptive random testing，and explains the test case algorithm based on information entropy. It mainly includes three items：information entropy index，algorithm application，and empirical experiments. According to the research in this paper，Entropy algorithm and other compared with the algorithm，it has a good failure detection ability in both high-dimensional and low-dimensional space situations.

Keywords：information entropy;adaptive random test;algorithm

0? 引? 言

在信息時(shí)代背景下，計(jì)算機(jī)軟件在技術(shù)產(chǎn)業(yè)得到廣泛應(yīng)用，對(duì)軟件質(zhì)量與可靠性提出嚴(yán)格要求，軟件測(cè)試的地位不斷提升。在軟件測(cè)試過程中，測(cè)試用例選擇十分重要，對(duì)測(cè)試效果具有直接影響。對(duì)此，應(yīng)盡量采用典型用例，在信息熵的基礎(chǔ)上采用適應(yīng)性測(cè)試用例，引入FSCS-ART經(jīng)典算法，提高揭錯(cuò)能力。

1? 適應(yīng)性隨機(jī)測(cè)試的理論基礎(chǔ)

1.1? 隨機(jī)測(cè)試

在軟件測(cè)試方面，隨機(jī)測(cè)試的應(yīng)用范圍較為廣泛，測(cè)試時(shí)無需掌握程序中的內(nèi)部結(jié)構(gòu)與軟件需求，只需在輸入空間內(nèi)部采用偽隨機(jī)數(shù)生成器，便可對(duì)數(shù)據(jù)點(diǎn)進(jìn)行自動(dòng)化測(cè)試，具有成本低、自動(dòng)化程度高、實(shí)施簡(jiǎn)便等特點(diǎn)?，F(xiàn)階段，軟件種類不斷增加，Unix工具集、Java程序、Windows GUI應(yīng)用軟件等在測(cè)試活動(dòng)中得到普遍應(yīng)用，還可與其他軟件測(cè)試方法綜合使用，如組合測(cè)試、回歸測(cè)試等等。隨機(jī)測(cè)試具有預(yù)測(cè)性，通過統(tǒng)計(jì)意義可對(duì)其檢測(cè)能力進(jìn)行分析，在此基礎(chǔ)上的改進(jìn)算法也隨之產(chǎn)生。

1.2? FSCS-ART算法

在隨機(jī)測(cè)試中，該方法屬于第一個(gè)具體算法，受到軟件工程領(lǐng)域的廣泛關(guān)注。該算法適用于輸入值為數(shù)值型的待測(cè)程序，利用用例候選策略，將候選用例與已測(cè)用例為標(biāo)準(zhǔn)，對(duì)多樣性進(jìn)行判斷。在本文研究中，將該項(xiàng)指標(biāo)定義為distance指標(biāo)。據(jù)研究結(jié)果可知，在低維輸入域中，ART中的F-measure值與隨機(jī)測(cè)試相比降低，這意味著測(cè)試的失效檢測(cè)力得到極大提升。

1.2.1? distance指標(biāo)

該指標(biāo)的具體定義為：給定候選用例集CS，其取值范圍在c1，c2，c3，…，cs之間，以用例ci為例，指標(biāo)計(jì)算公式為：

dis tance（ci）=dist（ci，η（ci，TS））

式中，TS代表的是已測(cè)用例集合;dist（ci，η（ci，TS））定義為數(shù)值程序中兩個(gè)用例間的歐式距離;η（ci，TS）代表的是在TS集合中，與ci距離最近的用例。由上述公式可知，候選用例的指標(biāo)主要是與全部已測(cè)用例之間距離最小的數(shù)值，該數(shù)值越大，意味著與已測(cè)用例的距離越長(zhǎng)，區(qū)分度也就越大。因此，在ART算法中，dis tance的數(shù)值越大，說明候選用例中的優(yōu)先級(jí)越高。

1.2.2? 算法流程

在ART算法中，應(yīng)將每次產(chǎn)生的候選用例、執(zhí)行用例分別用兩個(gè)集合進(jìn)行存儲(chǔ)，將CS與TS集合進(jìn)行初始化處理。首先，從整個(gè)輸入域中選出一個(gè)用例，當(dāng)執(zhí)行用例中無實(shí)效情況時(shí)，可將其輸入到TS集合中，在第3～10行中循環(huán)，形成新的用例。在生成下一個(gè)用例之前，首先在輸入域中隨機(jī)生成s個(gè)候選用例，并將其存儲(chǔ)在CS集合中。隨機(jī)選出用例ci，i的范圍在1～s之間，對(duì)其與TS集合中用例的最小距離進(jìn)行計(jì)算，得出dis tance值，將其應(yīng)用到后續(xù)實(shí)測(cè)用例中。對(duì)上述流程不斷重復(fù)，直至與停止條件相符合，從而達(dá)到挖掘失效或已測(cè)用例數(shù)目預(yù)定值的目標(biāo)[1]。

2? 基于信息熵的隨機(jī)測(cè)試用例算法分析

本文站在失效檢測(cè)效果的視角，在高維環(huán)境下對(duì)ART算法進(jìn)行改進(jìn)，提出新的算法—FSCS-Entropy算法，以此獲得更加理想的用例分布結(jié)果。同時(shí)，將信息熵與距離兩項(xiàng)指標(biāo)引入其中，對(duì)候選用例與已測(cè)用例的分散度進(jìn)行繪制，以此降低邊緣處用例優(yōu)先級(jí)，使算法的失效檢測(cè)性能得到進(jìn)一步提升。

2.1? 信息熵指標(biāo)

該指標(biāo)的主要作用在于解決信息量化度量問題，在信息工程領(lǐng)域應(yīng)用較為普遍。在相關(guān)理論中，熵可對(duì)樣本集合純度進(jìn)行衡量。假設(shè)集合D中第j類樣本占比為pj，其中j的取值范圍在1～m之間，則集合D信息熵的計(jì)算公式為：

如若集合中的樣本類型為兩種，信息熵與樣本比例之間的變化呈曲線分布。當(dāng)集合內(nèi)不同樣本發(fā)生概率均衡，也就是pj的數(shù)值為1/m時(shí)，集合中的信息熵?cái)?shù)值處于最大值;當(dāng)信息熵的最小值為0時(shí)，則意味著集合內(nèi)部存在一類樣本，其純度較高[2]。

2.2? 算法應(yīng)用

針對(duì)FSCS-EntropyA算法進(jìn)行分析，在該算法正式運(yùn)行之前，應(yīng)事先對(duì)各相關(guān)變量進(jìn)行設(shè)置，即候選用例集大小，用s表示;待測(cè)程序的輸入域，用R表示;準(zhǔn)則k值以及輸入域維度，用d表示。在算法應(yīng)用過程中，先對(duì)TS和CS集合進(jìn)行初始化，隨后在程序中輸入域中隨機(jī)選擇一個(gè)數(shù)據(jù)點(diǎn)，將其當(dāng)作首個(gè)測(cè)試的用例，在待測(cè)程序中實(shí)施。對(duì)于首個(gè)新用例來說，如若沒有發(fā)現(xiàn)失效情況，則在3～15行中反復(fù)循環(huán)，生成大量新用例，直至與停止條件相符合。當(dāng)測(cè)試用例中均沒有成功檢測(cè)出失效時(shí)，可將其傳入到TS集合中，在生成后續(xù)用例之前，先將其輸入到域內(nèi)，隨機(jī)出現(xiàn)s個(gè)候選用例，并將其存入CS集合內(nèi)。對(duì)于CS集合來說，其中包括的候選用例均為ci，先要對(duì)集合TS中的現(xiàn)有用例最短距離進(jìn)行計(jì)算，將其記為dis tance（ci），然后利用該指標(biāo)從CS集合中對(duì)最優(yōu)k個(gè)候選用例進(jìn)行選擇，將其納入到CS集合中，在第10～13行的位置對(duì)CS進(jìn)行遍歷。針對(duì)任意候選用例ci來說，可首先找出與之相距2d的鄰居，將其記為Top-2d（ci），按照ci與上述鄰居用例之間的距離進(jìn)行計(jì)算，得出entropy指標(biāo)。最后，利用CS集合中的最大entropy數(shù)值候選用例對(duì)后續(xù)測(cè)試用例進(jìn)行計(jì)算。

在EntropyB算法的應(yīng)用中，輸入?yún)?shù)、初始操作與EntropyA之間的操作相同，IE大多數(shù)流程也較為相近，二者的不同之處在于B算法主要對(duì)CS集合中的各個(gè)候選用例ci進(jìn)行計(jì)算，從中找出與之相距2d的鄰居用例，用Top-2d表示，在此基礎(chǔ)上對(duì)鄰居用例間的距離進(jìn)行計(jì)算，得出entropy指標(biāo)，最后通過該指標(biāo)從集合CS中選出最佳k用例，使其擁有最大值，應(yīng)用到后續(xù)實(shí)測(cè)用例之中[3]。

2.3? 實(shí)證實(shí)驗(yàn)

為了對(duì)Entropy算法在不同場(chǎng)景中的應(yīng)用效果進(jìn)行分析，本文提出以下實(shí)驗(yàn)問題：在失效實(shí)際程序中，Entropy算法與典型ART相比測(cè)試效果存在何種區(qū)別。

2.3.1? 實(shí)驗(yàn)設(shè)置

在實(shí)證實(shí)驗(yàn)方面，本文采用25個(gè)經(jīng)典程序，并采用Java語(yǔ)言進(jìn)行實(shí)現(xiàn)，前14個(gè)程序由ACM收集算法提供，在適應(yīng)性隨機(jī)測(cè)試中得到普遍應(yīng)用。在高維程序中，line、calDay與complex分別對(duì)點(diǎn)、線段、三角形之間的位置關(guān)系進(jìn)行確定。對(duì)于上述幾何程序來說，輸入?yún)?shù)為點(diǎn)坐標(biāo)、線段端點(diǎn)，select程序是從無序數(shù)組中取出的第k個(gè)最大元素，最后程序?yàn)閠cas西門子防撞系統(tǒng)。對(duì)于不同的實(shí)際程序來說，失效率屬于近似值，為了描述便利，采用F-measure指標(biāo)對(duì)不同算法檢測(cè)效果進(jìn)行衡量。

2.3.2? 失效檢測(cè)效果

對(duì)高維實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比可知，Entropy算法的檢測(cè)效果與ART算法相比較差。通常情況下，前者中的measure數(shù)值均小于后者的對(duì)應(yīng)值，將二者的p-value進(jìn)行進(jìn)一步對(duì)比可知，對(duì)于大多數(shù)實(shí)際程序來說，p-value數(shù)值均超過0.05，這意味著二者在失效檢測(cè)能力方面無明顯差異。另外，在plgndr程序中measure數(shù)值為552.76、binaryGCD程序中measure數(shù)值為1345.71，Entrop算法中measure數(shù)值為845.50，但是在ART算法中，三者對(duì)應(yīng)的數(shù)值分別為603.19、1626.94與998.72。由此可見，在上述程序中，Entropy算法中的measure數(shù)值低于ART算法，且p-value的數(shù)值低于0.05，這充分表明Entropy算法具有較強(qiáng)的失效檢測(cè)能力。此外，在低維程序中，與ART算法相比，Entropy算法的數(shù)值較低，且二者p-valur遠(yuǎn)遠(yuǎn)低于0.05，同樣說明該算法在低維狀態(tài)下的檢測(cè)能力。

3? 結(jié)? 論

綜上所述，在軟件測(cè)試領(lǐng)域中，自動(dòng)化測(cè)試在操作性、效率等方面具有更多優(yōu)勢(shì)。在眾多測(cè)試用例生成方式中，隨機(jī)測(cè)試更加簡(jiǎn)單高效、易于實(shí)現(xiàn)，應(yīng)積極將Entropy算法應(yīng)用到高維或者低維空間情形中，使失效檢測(cè)效果得到進(jìn)一步提升，為軟件測(cè)試開展提供充足的技術(shù)支持。

參考文獻(xiàn)：

[1] 李萬慶，李彥蒼.求解復(fù)雜優(yōu)化問題的基于信息熵的自適應(yīng)蟻群算法 [J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2005（2）：134-139.

[2] 納春寧.基于圖像信息熵的自適應(yīng)Harris角點(diǎn)檢測(cè)算法 [J].內(nèi)蒙古農(nóng)業(yè)大學(xué)學(xué)報(bào)（自然科學(xué)版），2013，34（5）：141-144.

[3] 余紹蓉，尹益輝，徐兵，等.基于信息熵理論的隨機(jī)—模糊可靠性分析方法探討 [J].機(jī)械強(qiáng)度，2006（5）：695-698.

作者簡(jiǎn)介：孫德剛（1978.04-），男，漢族，山東德州人，高級(jí)工程師，學(xué)士學(xué)位，研究方向：教育信息化、軟件開發(fā)。