1432
1
0
2023-12-29 17:26:54
2023-12-29
軟件產(chǎn)品線（Software Product Line, SPL）是一種有效的軟件開發(fā)方法，既可以滿足終端用戶多樣化的需求,，實現(xiàn)產(chǎn)品的個性化定制,，又有助于節(jié)約開發(fā)成本，減少維護(hù)工作量,。由于測試產(chǎn)品數(shù)量隨特征（軟件產(chǎn)品線的模塊）數(shù)量呈指數(shù)增長,，測試所有軟件產(chǎn)品在實際中幾乎不可行,。為平衡測試可靠性和測試集數(shù)量，t-組合測試應(yīng)運(yùn)而生,，它要求找到一個可覆蓋任意t個特征所有可能組合的最小測試集,。然而，現(xiàn)有的t-組合測試算法難以有效處理實際應(yīng)用中存在的大規(guī)模和高交互強(qiáng)度的情形,。
不少研究引入了基于相似性的測試方法以解決t-組合測試可擴(kuò)展性差的問題。這類方法在生成測試集時需增強(qiáng)當(dāng)前測試集的多樣性以實現(xiàn)特定目標(biāo),，如最大化缺陷檢測率或覆蓋率等,。基于相似性的測試無法確保100%的t-組合覆蓋率,，但可以靈活地設(shè)置待生成的測試用例個數(shù)及運(yùn)行時間,。在測試資源有限的情形下，基于相似性的測試具有更強(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)生一個多樣化的初始解c,，若c不可行,，則調(diào)用原始的ProbSAT予以修復(fù),。作為一個通用框架, 該算法適用于任何SLS類型的SAT求解器。
圖2 dProbSAT算法示意圖
（2）測試集的歸檔策略
dSATNS根據(jù)NS算法采用了兩種歸檔策略GlobalArch（見圖3）和LocalArch（見圖4）,，分別考慮了測試集的全局多樣性和局部多樣性。新穎得分是NS算法中的核心概念,，度量個體所在區(qū)域的擁擠程度,。新穎得分越高，說明個體所在區(qū)域越稀疏,，反之則越密集。GlobalArch通過不斷搜索新穎得分更高的個體并替換,，提高了測試集的整體多樣性，但忽略了新個體所在區(qū)域的局部信息,。新個體的加入可能會導(dǎo)致出現(xiàn)局部聚集的現(xiàn)象,，而在LocalArch的策略中,，新測試用例及與其最近的測試用例不能同時存在，提高了測試集的局部多樣性,。
圖3 全局歸檔策略GlobalArch的示意圖
圖4 局部歸檔策略LocalArch的示意圖
研究人員在50個公開的軟件產(chǎn)品線上進(jìn)行仿真實驗,，驗證了dSATNS算法各組件的有效性。實驗結(jié)果表明,，采用多樣性求解器有助于改善覆蓋率和缺陷檢測率，全局和局部歸檔策略則相輔相成,，適用于測試集規(guī)模較大和較小的情形,。
圖5給出了dSATNS與各主流算法關(guān)于缺陷檢測率的U檢驗結(jié)果,。由圖5可知，無論 N（測試集規(guī)模）多大,，dSATNS 始終優(yōu)于TSEGA [5]和TSENS [5]。當(dāng)N較小時,，dSATNS的優(yōu)勢尤其明顯；當(dāng)N較大時,，dSATNS在80%以上的特征模型上與其對比算法無顯著的統(tǒng)計差異。與SAT4J [3]相比,，dSATNS始終具有壓倒性優(yōu)勢,。
圖5 dSATNS與主流算法缺陷檢測率的U檢驗結(jié)果,。黑,、白、灰三種實驗結(jié)果標(biāo)注分別表示第一個算法顯著優(yōu)于,、差于和等同于第二個算法[1]。
圖6展示了通過Friedman檢驗得到的dSATNS與各對比算法在缺陷檢測率指標(biāo)上的平均排名,。對所有N值而言,，dSATNS不僅獲得了最佳排名,，而且與其他算法的性能差異在多數(shù)情形下具有統(tǒng)計顯著性,。當(dāng)N較小時，dSATNS展現(xiàn)出卓越的性能表現(xiàn),，這對于該算法的實際應(yīng)用是非常有利的,。因此可以得出結(jié)論：dSATNS的整體性能優(yōu)于其他主流算法,。
圖6 Friedman 檢驗得到的各算法的平均排名（越小越好）[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é)報, 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.
