910
4
0
2024-08-10 15:04:30
2024-08-10
在這個(gè)由代碼編織的世界里，每一款軟件都像是一個(gè)精心設(shè)計(jì)又充滿未知的迷宮。你是否想過(guò)，是誰(shuí)在這些迷宮中為我們指引方向，確保每一步都穩(wěn)健而正確？揭曉答案：自動(dòng)化測(cè)試套件生成方法。它能夠洞察軟件的每個(gè)角落，挑選出最佳的測(cè)試路徑，保障軟件的健壯性和可靠性。
（圖片來(lái)自網(wǎng)絡(luò)）
圖1 軟件測(cè)試如同走迷宮
一、多樣性驅(qū)動(dòng)：軟件產(chǎn)品線測(cè)試
軟件產(chǎn)品線（software product line, SPL）[1]作為一種高效開(kāi)發(fā)模式，能夠在共享特征的基礎(chǔ)上定制軟件以滿足不同的用戶需求。SPL通過(guò)特征模型（feature models, FMs）[2]來(lái)定義一組相關(guān)軟件產(chǎn)品的共同特征和可變特征。然而，隨著產(chǎn)品可變特征增加，單獨(dú)對(duì)每個(gè)產(chǎn)品變體進(jìn)行測(cè)試變得不切實(shí)際；這推動(dòng)了自動(dòng)化測(cè)試套件生成技術(shù)的發(fā)展。自動(dòng)化測(cè)試套件生成旨在生成一組測(cè)試用例，以盡可能多地揭示產(chǎn)品中的缺陷。測(cè)試用例的生成通常由目標(biāo)函數(shù)（如t-wise覆蓋率、套件多樣性）作指導(dǎo)；這些目標(biāo)函數(shù)可以量化測(cè)試用例的質(zhì)量。
圖2 一個(gè)簡(jiǎn)化的手機(jī)產(chǎn)品線的特征模型
以往的研究通常將自動(dòng)化測(cè)試套件生成問(wèn)題建模為單目標(biāo)或多目標(biāo)優(yōu)化問(wèn)題。單目標(biāo)優(yōu)化[3,4,5]只關(guān)注一個(gè)目標(biāo)，如最大化覆蓋率、最小化測(cè)試成本等，每次只生成一個(gè)測(cè)試套件，難以滿足不同測(cè)試場(chǎng)景的需求。多目標(biāo)優(yōu)化[6,7]同時(shí)考慮多個(gè)目標(biāo)，每次生成多個(gè)測(cè)試套件；它生成的測(cè)試套件具有更高的覆蓋率和多樣性，但算法的設(shè)計(jì)需要考慮目標(biāo)沖突和計(jì)算復(fù)雜度。
為了解決這一問(wèn)題，智能算法研究中心的最新研究引入了質(zhì)量-多樣性（Quality-Diversity, QD）優(yōu)化框架[8]，利用MAP-Elites算法[9]創(chuàng)新性地對(duì)測(cè)試套件生成問(wèn)題進(jìn)行求解。該方法不僅能夠高效地生成多樣化的測(cè)試套件，還在減少測(cè)試成本、增強(qiáng)覆蓋率方面超越了單目標(biāo)和多目標(biāo)優(yōu)化方法，甚至在與基于新穎性搜索（Novelty Search, NS）的算法對(duì)比時(shí)，展示出更好的測(cè)試套件多樣性與更強(qiáng)的缺陷探測(cè)能力。目前，該研究工作[10]已發(fā)表于軟件工程的頂級(jí)期刊ACM Transactions on Software Engineering and Methodology（CCF-A, JCR一區(qū)，影響因子6.6）；其代碼（https://github.com/gzhuxiangyi/SPLTestingMAP）和數(shù)據(jù)（https://doi.org/10.5281/zenodo.7805017）均已公開(kāi)，以供后續(xù)研究。
二、優(yōu)化探索：基于 QD 優(yōu)化的測(cè)試套件生成模型
三、精粹提煉：MAP-Elites算法及其應(yīng)用
圖3 用于自動(dòng)測(cè)試套件生成的MAP-Elites算法流程
該算法包括以下四個(gè)主要步驟：
1. 初始化：創(chuàng)建一個(gè)與行為空間大小匹配的空存檔（archive）；這里的行為空間是測(cè)試套件大小的一維表示。起初，每個(gè)單元設(shè)置為null；隨后，使用PLEDGE工具隨機(jī)生成初始或種子解決方案，并將它們存入archive中。
2. 隨機(jī)選取：在每次迭代中，從當(dāng)前存檔中隨機(jī)選取一個(gè)解決方案。
3. 突變操作：選定的解決方案被復(fù)制后經(jīng)過(guò)突變過(guò)程產(chǎn)生新的解決方案；突變方式由測(cè)試套件的大小和上下界來(lái)決定，具體策略可見(jiàn)圖4。
圖4 突變方式的決策流程圖
4. 更新存檔：評(píng)估新解決方案的性能，如果比當(dāng)前存檔中相同位置的解更優(yōu)，則替換更新相應(yīng)單元。
重復(fù)步驟2、3和4，直至滿足預(yù)設(shè)的終止條件。
MAP-Elites的應(yīng)用要求軟件工程師指定測(cè)試套件的大小范圍，據(jù)此產(chǎn)出多樣且高效的套件選項(xiàng)，增強(qiáng)測(cè)試決策的靈活性與針對(duì)性。
四、高效卓越：測(cè)試套件生成方法的實(shí)驗(yàn)評(píng)估
為了驗(yàn)證基于MAP-Elite算法的軟件產(chǎn)品線測(cè)試套件生成技術(shù)的有效性，本研究通過(guò)一系列對(duì)比實(shí)驗(yàn)對(duì)該方法進(jìn)行了深入探究。實(shí)驗(yàn)使用了廣泛應(yīng)用于SPL測(cè)試技術(shù)評(píng)估的105個(gè)特征模型（FMs），包括真實(shí)與人工生成的模型，并采用QD-Score[14]作為評(píng)價(jià)標(biāo)準(zhǔn)。
與單目標(biāo)優(yōu)化方法（multiple independent run of genetic algorithms, MI-GA）相比，無(wú)論是使用t-wise覆蓋還是測(cè)試套件多樣性作為適應(yīng)度函數(shù)，MAP-Elites在所有FMs上均顯著優(yōu)于MI-GA。從表1和圖5中可以觀察到，以2-wise覆蓋率為優(yōu)化目標(biāo)時(shí)，MAP-Elites的QD-Score表現(xiàn)突出，且在追求測(cè)試套件多樣性的同時(shí)，也能保持良好的2-wise覆蓋率表現(xiàn)。
表1 適應(yīng)度函數(shù)為2-wise 覆蓋率時(shí)MAP-Elites和MI-GA的QD-Score
（完整的實(shí)驗(yàn)數(shù)據(jù)表格可查閱原論文）
進(jìn)一步分析得到，MAP-Elites之所以表現(xiàn)優(yōu)異，是因?yàn)樗ㄟ^(guò)三個(gè)突變操作符（測(cè)試用例移除、添加和替換）實(shí)現(xiàn)了QD子問(wèn)題之間的信息共享。而MI-GA僅使用替換操作，缺乏信息共享機(jī)制。如圖6所示，在典型運(yùn)行過(guò)程中，相較于替換操作，MAP-Elites中測(cè)試用例的移除和添加操作更能促成更新的成功，即找到具有更高覆蓋率的更優(yōu)測(cè)試套件。
圖6 對(duì)9個(gè)代表性FMs進(jìn)行測(cè)試用例移除(R)、添加(A)和替換(S)的成功更新數(shù)量
此外，MAP-Elites在t-wise覆蓋率上普遍等同于或優(yōu)于多目標(biāo)進(jìn)化算法NSGA-II[6]。與現(xiàn)有的t-wise測(cè)試工具[3,4,5]相比，MAP-Elites在生成多樣化和高性能測(cè)試套件方面更勝一籌，尤其是在減少現(xiàn)有測(cè)試工具生成的覆蓋數(shù)組大小方面表現(xiàn)更為出色。更多實(shí)驗(yàn)細(xì)節(jié)與數(shù)據(jù)結(jié)果，歡迎閱讀完整論文。
綜上所述，基于QD優(yōu)化的MAP-Elites算法在SPL自動(dòng)化測(cè)試套件生成中表現(xiàn)出色；無(wú)論是應(yīng)用于小規(guī)模還是大規(guī)模功能模型，它都能提升測(cè)試套件的質(zhì)量和多樣性，同時(shí)保持良好的計(jì)算效率。未來(lái)，智能算法研究中心將進(jìn)一步探索基于QD優(yōu)化的測(cè)試套件生成方法，包括擴(kuò)展行為空間、研究多目標(biāo)QD優(yōu)化、采用更先進(jìn)的QD算法和SAT求解器。此外，研究中心還計(jì)劃在真實(shí)軟件產(chǎn)品線上進(jìn)行測(cè)試，以期推動(dòng)測(cè)試套件生成技術(shù)的進(jìn)步。
參考文獻(xiàn)
[1]Clements P, Northrop L. Software product lines[M]. Boston: Addison-Wesley, 2002.
[2]Batory D. Feature models, grammars, and propositional formulas[C]//International Conference on Software Product Lines. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005: 7-20.
[3]Al-Hajjaji M, Krieter S, Thüm T, et al. IncLing: efficient product-line testing using incremental pairwise sampling[J]. ACM SIGPLAN Notices, 2016, 52(3): 144-155.
[4]Krieter S, Thüm T, Schulze S, et al. YASA: yet another sampling algorithm[C]//Proceedings of the 14th International Working Conference on Variability Modelling of Software-Intensive Systems. 2020: 1-10.
[5]Luo C, Zhao Q, Cai S, et al. SamplingCA: effective and efficient sampling-based pairwise testing for highly configurable software systems[C]//Proceedings of the 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering. 2022: 1185-1197.
[6]Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE transactions on evolutionary computation, 2002, 6(2): 182-197.
[7]Markiegi U, Arrieta A, Sagardui G, et al. Search-based product line fault detection allocating test cases iteratively[C]//Proceedings of the 21st International Systems and Software Product Line Conference-Volume A. 2017: 123-132.
[8]Pugh J K, Soros L B, Stanley K O. Quality diversity: A new frontier for evolutionary computation[J]. Frontiers in Robotics and AI, 2016, 3: 202845.
[9]Mouret J B, Clune J. Illuminating search spaces by mapping elites[J]. arXiv preprint arXiv:1504.04909, 2015.
[10]Xiang Y, Huang H, Li S, et al. Automated test suite generation for software product lines based on quality-diversity optimization[J]. ACM Transactions on Software Engineering and Methodology, 2024, 33(2): 1-52.
[11]Henard C, Papadakis M, Perrouin G, et al. PLEDGE: a product line editor and test generation tool[C]//Proceedings of the 17th International Software Product Line Conference Co-Located Workshops. 2013: 126-129.
[12]Lopez-Herrejon R E, Linsbauer L, Egyed A. A systematic mapping study of search-based software engineering for software product lines[J]. Information and software technology, 2015, 61: 33-51.
[13]Xiang Y, Huang H, Li M, et al. Looking for novelty in search-based software product line testing[J]. IEEE Transactions on Software Engineering, 2021, 48(7): 2317-2338.
[14]Pugh J K, Soros L B, Szerlip P A, et al. Confronting the challenge of quality diversity[C]//Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation. 2015: 967-974.
