自適應隨機測試:測試用例多樣性的藝術
介紹：
隨機測試概念簡單试幽，通常易于實現(xiàn)，能有效地檢測故障，擅長以意想不到的方式運行系統(tǒng)(這可能不會發(fā)生在人類測試人員身上)骨宠，并且可能是源代碼和規(guī)范不可用或不完整時唯一的實際選擇米罚。
隨機測試：廣泛钧汹，但低效。
作者提出——ART（自適應隨機測試）
AIM：指導測試录择，提高隨機測試效率拔莱。
核心：經(jīng)驗研究表明，程序的錯誤（program fault）往往與輸入域中某一連續(xù)的輸入失敗區(qū)間相對應（記作失敗模式 failure patterns）隘竭。ART即利用這種失敗區(qū)間的連續(xù)性塘秦，來引導或是選擇一組候選測試用例。
失敗模式：
測試的本質(zhì)：
從被測軟件的可能輸入集合（輸入域）中抽樣动看，并逐個執(zhí)行抽取樣本后判斷尊剔。
輸出不合預期的樣本，意味著軟件的失斄饨浴（failure）须误，軟件失敗的存在說明軟件存在錯誤/故障（fault）（軟件中具體代碼的錯誤）。（故障與錯誤往往是多對一關系）
軟件測試的本質(zhì)目標:
選擇合適的測試數(shù)據(jù)集仇轻，以最大化檢測到的不同錯誤（faults）數(shù)量京痢。
基于上述，在測試執(zhí)行中拯田，就需要考慮選擇不同的會產(chǎn)生錯誤的失敗模式历造。
相關研究：
White and Cohen：
當謂詞的內(nèi)容(源代碼中的決策點)是錯誤的，就會采取不正確的計算路徑(稱為域錯誤)。
Ammann and Knight：
分析了一些數(shù)值程序吭产，以確定由各種錯誤引起的失敗輸入分布侣监。在他們的小樣本中，他們發(fā)現(xiàn)錯誤導致“局部連續(xù)”的失敗區(qū)域臣淤。
Bishop：
幾乎所有的故障都是“斑點”故障——也就是說橄霉，每個故障都揭示了輸入域的一個連續(xù)區(qū)域中的失敗。
Chan：
提出三種故障模式邑蒋。(1)塊模式姓蜂，在這種模式中，故障形成了輸入域的局部緊湊医吊、連續(xù)的區(qū)域钱慢；(二)條帶模式，類似于懷特和科恩的定義域錯誤導致的模式卿堂，其中“條帶”是連續(xù)的束莫，但沿一個或多個維度拉長，會顯示故障草描；以及(iii)點模式览绿，其中故障將以不連續(xù)的方式在整個輸入域中傳播。
他們認為條狀和塊狀失效模式比點狀模式更常見穗慕。
結(jié)論：
在數(shù)值程序中饿敲，許多程序錯誤導致程序輸入域的連續(xù)故障區(qū)域。
ART 自適應隨機測試:
給定一組先前執(zhí)行的沒有揭示任何故障的測試用例逛绵，遠離這些舊測試用例的新測試用例更有可能揭示故障——換句話說怀各，測試用例應該更均勻地分布在整個輸入域中。
一個最基本的思路：
生成k個候選用例暑脆，找與已有測試距離最遠的候選用例渠啤。
二維空間，選擇第五個測試用例的過程添吗。
（c2距離已有測試用例距離最遠，因此將c2增加為t5）
評價指標：
用于比較這些方法的統(tǒng)計數(shù)據(jù)是檢測第一次故障所需的平均測試次數(shù)份名，這通常被稱為F-measure碟联。
FSCS-ART要比一半的隨機測試F值低30-50%
同作者的變體
RRT 限制隨機測試 Restricted Random Testing
提出排斥域的概念，當測試用例在排斥域內(nèi)則被排除僵腺。當隨機生成的用例沒有落在排斥域里鲤孵，則將其加入測試。
分區(qū)ART ART by Partitioning
直接劃分輸入域為不同區(qū)辰如，然后將測試用例平均分配到每一個分區(qū)普监。
擬隨機測試 Quasi-Random Testing
基于點陣的ART Lattice-Based ART
以上變體的失敗檢測率表現(xiàn)都相似，不同的方法對某些特定的類型表現(xiàn)較好。
其他人的類似方法
Antirandom測試
區(qū)別：Antirandom測試幾乎完全是確定性的凯正；唯一的不確定性來自于集合中第一個測試用例的選擇毙玻。此外，該方法需要提前選擇測試用例的數(shù)量廊散。
理論極限
基于失敗模式連續(xù)性桑滩，確實存在提高隨機測試性能效果的理論上限。
先考慮測試人員知道輸入域中有一個單一的允睹、連續(xù)的錯誤區(qū)域時的情況运准。
拉普拉斯的無差異原則(凱恩斯，2006)指出缭受，如果決策者知道世界的可能狀態(tài)胁澳，并且確實沒有關于每個可能狀態(tài)的合理性的信息，他們應該像每個狀態(tài)具有同等可能性一樣行動米者。在這種情況下韭畸，由于測試人員沒有關于故障區(qū)域位置的信息，他們應該假設它同樣可能位于輸入域內(nèi)的任何可能位置塘雳。
知道它連續(xù)陆盘，但不知道它在哪連續(xù)
設計一個選擇測試用例的最優(yōu)策略，并明確地表明它將有一個低于或等于任何其他策略的F度量(回想一下败明，F(xiàn)度量是一個平均值)隘马。本質(zhì)上，我們在整個輸入域的規(guī)則間隔位置創(chuàng)建一個測試用例“網(wǎng)格”妻顶，并以任意順序執(zhí)行結(jié)果測試酸员。在特定情況下，這樣的策略可能會“走運”讳嘱，并在第一個測試用例中顯示失敗幔嗦。然而，在許多試驗中沥潭，給定相同的失敗率邀泉，這種策略的f檢驗至少是隨機替換測試的f檢驗的一半。
也就意味著考慮錯誤模式連續(xù)性時钝鸽，至多可在理論上達到50%的效率提高汇恤。
然后作者把這個推廣的多個連續(xù)錯誤域也成立。
得到的結(jié)論or方向
ART的多種變體的效率提高都接近50%拔恰，一方面說明了不同的方法都已經(jīng)接近理論最好效果因谎，另一方面也表明錯誤模式連續(xù)性確實是一個緊密連續(xù)的區(qū)域。
之后的研究也就不該聚焦于進一步提高隨機測試有效性的F值颜懊，而是研究開銷更低的自動測試方法财岔。
數(shù)值程序之外使用ART方法
為了將ART推廣到一半的軟件測試风皿，有兩個核心問題：
- 如何隨機抽樣
- 如何度量兩個輸入間距離
第一個問題不是ART固有，相關的研究相對成熟匠璧。所以核心在于第二個問題桐款，如何度量差異大小。
距離的基本定義：
(a) D(p,q)≧0 [D(p,q)=0患朱，當且僅當p=q] //恒正
(b) D(p,q)=D(q,p) //對稱
(c) D(p,z)≦D(p,q)+D(q,z) //三角不等式
如果直接將所有的D（a,b)=0鲁僚，則ART退化為一個普通的隨機測試。
距離設計準則：
兩個輸入具有共同故障行為的可能性的估計——距離越小裁厅，它們觸發(fā)相同故障行為的可能性越大冰沙。
直覺是，計算的相似性是故障行為相似性的一個很好的預測因素执虹。因此拓挥，為了在非數(shù)字環(huán)境中有效地應用ART，需要替代方法來測量由兩個測試用例的執(zhí)行所產(chǎn)生的計算的相似性袋励。
作者等人提出的一種差異度量
它可以應用于廣泛的軟件輸入類型侥啤，基于奧斯特蘭德和巴爾克(1988)為類別劃分方法提出的類別和選擇的概念。類別劃分方法是一種基于規(guī)范的測試方法茬故。測試人員必須首先確定決定被測軟件行為的參數(shù)和環(huán)境條件盖灸，即所謂的類別。對于每個類別磺芭，選擇被定義為互斥的值集赁炎，這些值集預計會觸發(fā)類似的計算。
直覺上钾腺，兩個輸入有不同選擇的類別越多徙垫，它們觸發(fā)的計算就越不同。因此放棒，具有不同選擇的類別計數(shù)可以用作差異度量姻报。
紅房子和黑狗——d=2
紅房子和紅狗——d=1
（物品和顏色的類別靠人為劃分
面向?qū)ο筌浖谋尘跋碌牧硪环N類型的差異度量
它們首先定義了一些距離度量或元素類型，如數(shù)字间螟、布爾值吴旋、字符串和引用。接下來厢破，他們描述了如何測量復合對象之間的距離邮府，由三個元素組成——基于兩種對象類型之間差異的類型距離、字段距離(匹配字段之間的距離)和遞歸距離(匹配引用屬性之間的距離)溉奕。
擴展方向
自適應隨機序列 ARS
大意：隨機測試通常作為與其他策略比較的基準，ART的提高效果接近最優(yōu)忍啤，可以考慮將其作為替代隨機測試的新基準加勤。隨機生成序列也通常作為基準仙辟，所以ARS也可以考慮作為隨機生成序列替代的新基準。
應用：回歸測試
回歸測試中鳄梅，一個大的測試套件可能會隨著時間的推移而積累叠国，甚至到了每次進行更改時都不一定能運行所有測試套件的程度。因此戴尸，基于許多不同的標準粟焊，已經(jīng)開發(fā)了各種技術來區(qū)分測試套件元素的優(yōu)先級。
作者認為ARS可能是一種簡單孙蒙、有效和相對低開銷的選擇项棠。
標準的準隨機序列生成算法只生成非常少的不同序列；增強現(xiàn)實測序可以用來產(chǎn)生大量不同的序列挎峦。
基于失斚阕贰（failure）的測試
作者認為相較于其他方法，ART是一個顯示設計出來的基于失敗而非錯誤的方法坦胶。
基于故障的測試描述了一類測試策略透典，旨在證明程序中不存在或存在某種類型的故障。
定義：基于對失敗模式的不同知識（形狀顿苇，大小峭咒，位置，數(shù)量）纪岁，來選擇測試用例的方法凑队，是一個基于失敗的方法。
ART利用的就是失敗模式的連續(xù)性信息蜂科，設計的的方法顽决。
如果將連續(xù)性與其他信息相互結(jié)合補充，就可能產(chǎn)生更多相關的算法导匣。（eg才菠，失敗通常在邊界產(chǎn)生，選擇邊界結(jié)合連續(xù)性就可能是一個新的基于失敗的測試技術
兩類測試技術都要借助現(xiàn)有經(jīng)驗贡定。
在基于故障的測試的情況下赋访，經(jīng)驗研究可以提供必要的信息，以優(yōu)先搜索特定的故障類別缓待；如果一類故障在實踐中經(jīng)常發(fā)生蚓耽，搜索它們顯然是更高的優(yōu)先級。同樣旋炒，有效的基于故障的測試必須基于對典型故障模式的經(jīng)驗研究步悠，包括它們的幾何形狀和分布。
從另一個角度來看瘫镇，基于失敗模式的測試可以被視為一種專門的搜索問題鼎兽。在這種觀點下答姥，當測試被執(zhí)行時，來自測試的反饋會引導我們繼續(xù)尋找導致失敗的輸入谚咬。
核心思想即：利用已有的測試結(jié)果信息鹦付，來指導接下來的測試選擇
軟件測試理論
我們相信我們的方法是新穎的，并且可以作為一個模型來建立對失敗信息和軟件測試之間的關系的更深的理解择卦。對各種覆蓋標準進行了大量的理論分析敲长。這些分析表明，實現(xiàn)一種類型的覆蓋可能意味著另一種覆蓋（語句覆蓋&分支覆蓋）
意思就是秉继，作者為了驗證ART相關變體已經(jīng)達到理論最優(yōu)值祈噪，提出的理論檢驗方法可以推廣，用來評估任何一個基于某種假設or經(jīng)驗的測試策略或方法上秕噪，來計算這種策略的理論最優(yōu)钳降，從而確定是改改進方法，還是提高效率腌巾。
測試用例多樣性的作用
ART的產(chǎn)生源自于某種關于“擴散/域”的經(jīng)驗直覺遂填。
這種域的概念可以被拓展成某種形式的多樣性。然后結(jié)論就可以自然的變成：測試用例在整個輸入域中的均勻分布導致了計算的多樣性澈蝙。
ART實現(xiàn)了一種非常簡單的形式——也許是最簡單的形式——測試用例多樣性吓坚。
比例抽樣(PS)策略(Chen和Yu，1996)規(guī)定從每個分區(qū)中隨機選擇的測試用例的數(shù)量應該與相應的分區(qū)大小成比例灯荧。
作者認為：PS最早出于普遍更優(yōu)的安全可靠的角度去改善隨機測試礁击，而ART則是出于失敗的聚集的猜想來改善隨機測試，兩者殊途同歸逗载，原因在于最終關注的其實都是輸入域的多樣性哆窿。
ART的這種多樣性，不僅體現(xiàn)在整個測試套件中厉斟，也體現(xiàn)在其中的任何一個時刻挚躯。對于每一個當前執(zhí)行的自己，實際上ART都在關注能夠帶來最大局部多樣性的選擇擦秽，這也是ART能夠更早發(fā)現(xiàn)故障的原因码荔。
