1397
1
0
2023-12-29 17:26:54
2023-12-29
軟件產(chǎn)品線（Software Product Line, SPL）是一種有效的軟件開發(fā)方法，既可以滿足終端用戶多樣化的需求，實(shí)現(xiàn)產(chǎn)品的個(gè)性化定制，又有助于節(jié)約開發(fā)成本，減少維護(hù)工作量。由于測試產(chǎn)品數(shù)量隨特征（軟件產(chǎn)品線的模塊）數(shù)量呈指數(shù)增長，測試所有軟件產(chǎn)品在實(shí)際中幾乎不可行。為平衡測試可靠性和測試集數(shù)量，t-組合測試應(yīng)運(yùn)而生，它要求找到一個(gè)可覆蓋任意t個(gè)特征所有可能組合的最小測試集。然而，現(xiàn)有的t-組合測試算法難以有效處理實(shí)際應(yīng)用中存在的大規(guī)模和高交互強(qiáng)度的情形。
不少研究引入了基于相似性的測試方法以解決t-組合測試可擴(kuò)展性差的問題。這類方法在生成測試集時(shí)需增強(qiáng)當(dāng)前測試集的多樣性以實(shí)現(xiàn)特定目標(biāo)，如最大化缺陷檢測率或覆蓋率等。基于相似性的測試無法確保100%的t-組合覆蓋率，但可以靈活地設(shè)置待生成的測試用例個(gè)數(shù)及運(yùn)行時(shí)間。在測試資源有限的情形下，基于相似性的測試具有更強(qiáng)的靈活性。
近期，智能算法研究中心的研究人員提出了一種基于多樣性可滿足性（Satisfiability, SAT）求解器和新穎性搜索（Novelty Search, NS）的軟件產(chǎn)品線測試算法dSATNS [1]。該算法采用多樣性SAT求解器產(chǎn)生測試用例，運(yùn)用新穎性搜索（Novelty Search, NS）算法的歸檔策略維護(hù)測試集的多樣性，并以迭代改進(jìn)的方式不斷提升當(dāng)前測試集的多樣性，進(jìn)而覆蓋更多特征組合或發(fā)現(xiàn)更多缺陷，如圖1所示。
圖1 dSATNS算法示意圖
（1）多樣性SAT求解器
dSATNS算法結(jié)合了兩類多樣性求解器，依概率調(diào)用rSAT4J [2]和ProbSAT。其中，rSAT4J是隨機(jī)化版本的SAT4J [3]，旨在產(chǎn)生不相似的SAT解；而dProbSAT則是研究人員提出的ProbSAT [4]的改進(jìn)算法。如圖2所示，dProbSAT借助概率向量產(chǎn)生一個(gè)多樣化的初始解c，若c不可行，則調(diào)用原始的ProbSAT予以修復(fù)。作為一個(gè)通用框架, 該算法適用于任何SLS類型的SAT求解器。
圖2 dProbSAT算法示意圖
（2）測試集的歸檔策略
dSATNS根據(jù)NS算法采用了兩種歸檔策略GlobalArch（見圖3）和LocalArch（見圖4），分別考慮了測試集的全局多樣性和局部多樣性。新穎得分是NS算法中的核心概念，度量個(gè)體所在區(qū)域的擁擠程度。新穎得分越高，說明個(gè)體所在區(qū)域越稀疏，反之則越密集。GlobalArch通過不斷搜索新穎得分更高的個(gè)體并替換，提高了測試集的整體多樣性，但忽略了新個(gè)體所在區(qū)域的局部信息。新個(gè)體的加入可能會導(dǎo)致出現(xiàn)局部聚集的現(xiàn)象，而在LocalArch的策略中，新測試用例及與其最近的測試用例不能同時(shí)存在，提高了測試集的局部多樣性。
圖3 全局歸檔策略GlobalArch的示意圖
圖4 局部歸檔策略LocalArch的示意圖
研究人員在50個(gè)公開的軟件產(chǎn)品線上進(jìn)行仿真實(shí)驗(yàn)，驗(yàn)證了dSATNS算法各組件的有效性。實(shí)驗(yàn)結(jié)果表明，采用多樣性求解器有助于改善覆蓋率和缺陷檢測率，全局和局部歸檔策略則相輔相成，適用于測試集規(guī)模較大和較小的情形。
圖5給出了dSATNS與各主流算法關(guān)于缺陷檢測率的U檢驗(yàn)結(jié)果。由圖5可知，無論 N（測試集規(guī)模）多大，dSATNS 始終優(yōu)于TSEGA [5]和TSENS [5]。當(dāng)N較小時(shí)，dSATNS的優(yōu)勢尤其明顯；當(dāng)N較大時(shí)，dSATNS在80%以上的特征模型上與其對比算法無顯著的統(tǒng)計(jì)差異。與SAT4J [3]相比，dSATNS始終具有壓倒性優(yōu)勢。
圖5 dSATNS與主流算法缺陷檢測率的U檢驗(yàn)結(jié)果。黑、白、灰三種實(shí)驗(yàn)結(jié)果標(biāo)注分別表示第一個(gè)算法顯著優(yōu)于、差于和等同于第二個(gè)算法[1]。
圖6展示了通過Friedman檢驗(yàn)得到的dSATNS與各對比算法在缺陷檢測率指標(biāo)上的平均排名。對所有N值而言，dSATNS不僅獲得了最佳排名，而且與其他算法的性能差異在多數(shù)情形下具有統(tǒng)計(jì)顯著性。當(dāng)N較小時(shí)，dSATNS展現(xiàn)出卓越的性能表現(xiàn)，這對于該算法的實(shí)際應(yīng)用是非常有利的。因此可以得出結(jié)論：dSATNS的整體性能優(yōu)于其他主流算法。
圖6 Friedman 檢驗(yàn)得到的各算法的平均排名（越小越好）[1]
綜上所述，智能算法研究中心究基于相似性的軟件產(chǎn)品線測試方法，提出了一種基于多樣性 SAT 求解器和新穎性搜索的算法dSATNS，在軟件產(chǎn)品線測試中展現(xiàn)出了卓越的性能表現(xiàn)。
本文算法中提出的多樣性SAT求解框架是通用的，現(xiàn)在所采用的SAT求解器完全可以直接替換成任何其它求解器。因此，在后續(xù)工作中比較這些求解器的性能表現(xiàn)并給出關(guān)于如何選擇求解器的合理建議是有意義的。此外，智能算法研究中心也將探索把雙歸檔策略應(yīng)用于與軟件產(chǎn)品線相關(guān)的其他任務(wù)，如多樣性采樣等，以期為軟件測試方法的發(fā)展作出積極貢獻(xiàn)。
參考文獻(xiàn)
[1] 向毅, 黃翰, 羅川, 等. 基于多樣性 SAT 求解器和新穎性搜索的軟件產(chǎn)品線測試[J]. 軟件學(xué)報(bào), 2023, 33: 1-23.
[2] Henard C, Papadakis M, Perrouin G, et al. Bypassing the combinatorial explosion: Using similarity to generate and prioritize t-wise test configurations for software product lines[J]. IEEE Transactions on Software Engineering, 2014, 40(7): 650-670.
[3] Anne P. The SAT4J library release 2.2 system description[J]. Journal on Satisfiability, Boolean Modeling and Computation (JSAT), 2010, 7: 59-64.
[4] Balint A, Schöning U. Choosing probability distributions for stochastic local search and the role of make versus break[C]//International Conference on Theory and Applications of Satisfiability Testing. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012: 16-29.
[5] Xiang Y, Huang H, Li M, et al. Looking for novelty in search-based software product line testing[J]. IEEE Transactions on Software Engineering, 2022, 48(7): 2317-2338.
