[發明專利]基于相似度和TrustRank算法的節點測試重要度評估方法

在審

• 申請號: 201711152346.3
• 申請日: 2017-11-19
• 公開（公告）號: CN108009710A
• 公開（公告）日: 2018-05-08
• 發明（設計）人: 王博;張琨;尹魏昕;吳倩;林星辰;張家旺;徐建;蔡穎;牟甲鵬
• 申請（專利權）人: 國家計算機網絡與信息安全管理中心;南京理工大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06F17/16;G06F17/15;H04L12/24
• 代理公司: 南京理工大學專利中心 32203
• 代理人: 馬魯晉

本發明提出了一種基于相似度和TrustRank算法的節點測試重要度評估方法，具體步驟為：建立節點重要度評分矩陣，確定節點的初步評分；根據節點間相似度構建節點相似性矩陣；依據節點間相關系數和依賴特征數確定校正系數；利用TrustRank算法獲得節點重要度穩定值，確定節點測試重要度。本發明的基于相似度和TrustRank算法的節點測試重要度評估方法，借鑒TrustRank算法，提供一種綜合考慮節點相似度及多種重要性測度的節點測試重要度評估方法，且排名具備較高的準確性。

技術領域

本發明屬于軟件網絡節點測試重要度評估技術，特別是一種基于相似度和TrustRank算法的節點測試重要度評估方法。

背景技術

軟件網絡(Software Network)，是一種特定類型的復雜網絡。它將復雜網絡的方法引入到軟件的拓撲結構分析中，用軟件的網絡模型抽象面向對象(Object-Oriented,簡稱OO)軟件系統，即節點代表方法、類、包等軟件實體；邊代表實體間的交互關系(如方法調用、類繼承等)，對大量OO軟件各個粒度的拓撲結構進行研究，發現軟件的結構并不是隨機和無序的，大多數都展現出“小世界”(small world)和“無標度”(scale-free)等復雜網絡特征。傳統的軟件代碼安全審計分析，采用污點傳播分析、符號執行等方式，對軟件系統的編碼錯誤進行檢測，但是存在著路徑爆炸、誤報率高等缺點，并且無法準確的定位到軟件系統中的關鍵函數和關鍵變量。因此，有學者提出引入復雜網絡的相關理論對軟件系統的架構進行分析和研究，快速定位出軟件系統中的關鍵部分。

復雜網絡是21世紀出現的一門新興的系統性、綜合性學科。自然界和人類社會存在大量復雜系統都可以通過網絡加以描述，如細胞網絡、Internet、引文網、語言網、電力網和交通網等，他們都有明顯的復雜網絡特性。從復雜網絡的角度看，軟件系統可以被看成是由數據對象、操作、模塊、類、構件、子系統所組成的。在軟件的網絡模型中，節點代表軟件的組成元素，而邊代表軟件組成元素之間的相互作用，將軟件系統抽象為復雜網絡，從分析和度量軟件系統組織結構的整體特性為著眼點，發現并定位復雜軟件系統中的測試關鍵點和故障點，可有效提升軟件系統的測試準確性和可靠性。

根據計算方式的不同，現有的復雜網絡節點重要性的評價指標大致可以分為四類：基于鄰居節點的評價指標、基于路徑的評價指標、基于特征向量的評價指標以及基于節點刪除和收縮的評價指標。

基于鄰居節點的評價指標最為簡單直觀，側重于考察節點之間的連接狀態，即通過目標節點與其他鄰近節點的連接數來體現其重要性。基于此，PhillipBonacich提出了度中心性的概念，在度中心性指標下，度值越高的節點越重要(Phillip Bonacich.Factoringand weighting approaches to status scores and clique identification[J].TheJournal of Mathematical Sociology,1972,2(1):113-120.)。而Kitsak等人提出用k-殼分解法來定義節點在網絡中的位置，即將節點按度數分層，越靠近網絡核心的節點影響力越大(Kitsak M,Gallos L K,Havlin S,et al.Identification of influentialspreaders in complex networks[J].Nature Physics,2010,6(11):888-893.)。但是，度中心性指標僅考慮了網絡的局部信息，若某一節點度值不高，卻是連接不同子網從而使網絡連通的唯一節點，即“橋”節點，則毋容置疑，該節點也應擁有很高的重要性。而在k-殼分解法中，同一殼內的節點的傳播能力也不一定相同，因此在測量上仍有缺陷。

在網絡中，往往會存在一些連接幾個子區域的“橋節點”，它們的度很小，卻在網絡中充當著傳遞、連通的作用，因此具有很高的重要性。基于此，學者提出了基于路徑的評價指標，該類方法在刻畫節點重要性時，綜合考慮了節點對信息流的控制力，而這種控制力通常與網絡中的路徑密切相關。常見的基于路徑的評價指標有接近中心性和介數中心性、信息指標、子圖中心性等。該類方法往往復雜度較高，難以實用。