[發(fā)明專利]一種基于K-均值聚類的軟件測試目標路徑選擇方法

有效

• 申請?zhí)枺?/td>: 201910380031.7
• 申請日: 2019-05-08
• 公開（公告）號: CN110084321B
• 公開（公告）日: 2023-01-20
• 發(fā)明（設計）人: 張巖;喬力;王興亞;佟林;蔡靜穎;夏春艷;陳振宇
• 申請（專利權）人: 宿遷學院;南京大學
• 主分類號: G06F18/23213
• 分類號: G06F18/23213;G06F17/16;G06F11/36
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發(fā)明涉及一種基于K?均值聚類的軟件測試目標路徑選擇方法。該方法給定待測程序，利用Z覆蓋方法將程序中的循環(huán)結構轉化為選擇結構，基于赫夫曼編碼對程序路徑進行編碼；從路徑編碼集合中隨機選擇路徑作為聚類中心，計算剩余路徑與聚類中心的區(qū)分度，對路徑進行聚類；最后，結合K?均值聚類算法，選擇類中與其他路徑區(qū)分度和最小的路徑作為新的聚類中心，直到聚類中心不再變化為止；最終，輸出聚類中心作為待測程序的測試目標路徑集合。本發(fā)明目的在于解決了目前被測軟件路徑數(shù)目眾多的情況下，全路徑覆蓋測試難以達到，測試質(zhì)量難以得到保障的問題，最終幫助測試人員提高軟件測試效率，同時保障軟件測試的質(zhì)量。

技術領域

本發(fā)明涉及軟件測試與程序分析領域，尤其適用于軟件測試中測試目標選擇領域，其目的在于為被測程序自動選擇具有代表性的測試目標路徑，是一種幫助軟件測試人員提高軟件測試效率，保障軟件質(zhì)量的方法。

背景技術

軟件測試是保障軟件質(zhì)量的重要手段。路徑覆蓋測試是指在測試過程中，盡可能地覆蓋程序中所有的可行路徑，它是一種覆蓋率高且檢錯能力較強的白盒測試方法。許多軟件測試問題都可以歸結為面向路徑的測試數(shù)據(jù)生成問題，該問題描述為：給定程序的一條目標路徑，在程序的輸入空間中尋找測試數(shù)據(jù)，使得以該數(shù)據(jù)作為輸入所經(jīng)過的路徑為目標路徑。路徑覆蓋測試多采用人工確定目標路徑的方式，目標路徑的質(zhì)量將取決于測試人員的經(jīng)驗，并且區(qū)分路徑之間相似程度也需要耗費大量的時間，路徑對應的測試數(shù)據(jù)質(zhì)量也很難保證。目前，面對復雜被測軟件路徑數(shù)目眾多的情況，很難達到全路徑覆蓋測試。因此，如果能夠采用一定方法根據(jù)待測程序選擇合適的目標路徑，并根據(jù)目標路徑選擇測試數(shù)據(jù)，可以在有效降低質(zhì)量保障人員的工作壓力，提高軟件研發(fā)的生產(chǎn)效率的同時，保障軟件產(chǎn)品的生產(chǎn)質(zhì)量和可靠性。

在實際測試中，首先需要確定被測程序的目標路徑，然后再生成經(jīng)過該路徑的測試數(shù)據(jù)。此時，選擇哪些路徑作為期望的目標路徑，會直接影響到測試數(shù)據(jù)的質(zhì)量。目前，有學者針對目標路徑的選擇方法進行研究，如蔣俊弛等提出一種基于函數(shù)調(diào)用路徑的C#變更影響路徑集生成方法，但是該方法主要用于對回歸測試的路徑選擇。張妙等在2018年3月27日公開的發(fā)明專利中，提出了一種基于層次聚類的相似執(zhí)行路徑生成方法，該發(fā)明目的在于提供一種基于層次聚類的相似執(zhí)行路徑生成方法，主要解決了目前的路徑測試執(zhí)行之前難以識別程序中不可達路徑的問題，提高了路徑測試的效率。然而，這些方法并沒有很好地解決選擇測試目標路徑質(zhì)量的問題。

對此，本發(fā)明提出了一種基于K-均值聚類的軟件測試目標路徑選擇方法。本發(fā)明的基本思想為：選擇被測程序中具有代表性的測試目標路徑，進而根據(jù)目標路徑選擇測試數(shù)據(jù)，在降低工作量的同時保障測試質(zhì)量。對此，針對待測程序，首先將基于Z覆蓋方法和赫夫曼編碼，對待測程序進行路徑編碼；再次，根據(jù)需要的路徑數(shù)通過K-均值聚類，對眾多路徑進行分組，達到每組內(nèi)的路徑具有一定的相似度，不同組之間的路徑具有較大的區(qū)分度的目的；最后，在每一組中，選擇距離聚類中心最近的路徑作為目標路徑。通過該方法，可以大大減少測試工作量，且聚類后選擇的目標路徑彼此具有代表性，更有利于查找被測程序中的缺陷，從而有效保障測試數(shù)據(jù)的質(zhì)量。

發(fā)明內(nèi)容

本發(fā)明通過提供一種基于K-均值聚類的軟件測試目標路徑選擇方法，來有效解決目前存在的復雜被測軟件路徑數(shù)目眾多的情況下，全路徑覆蓋測試難以達到所導致的測試質(zhì)量難以得到保障的問題，最終提高了軟件測試效率，同時保障軟件測試的質(zhì)量。

為達成上述目標，本發(fā)明提出一種基于K-均值聚類的軟件測試目標路徑選擇方法。該方法針對待測程序，首先利用Z覆蓋方法和赫夫曼編碼，對待測程序進行路徑編碼；在此基礎上，通過K-均值聚類方法，按照需要的路徑數(shù)對眾多路徑進行分組，達到每組內(nèi)的路徑具有一定的相似度，不同組之間的路徑具有較大的區(qū)分度；最后，在每一組中，選擇距離聚類中心最近的路徑作為目標路徑。具體而言，該方法包括下列步驟。