基於社交網絡和半馬爾可夫過程的手機病毒傳播建模方法
2023-11-10 17:31:42 2
基於社交網絡和半馬爾可夫過程的手機病毒傳播建模方法
【專利摘要】本發明公開了一種基於社交網絡和半馬爾可夫過程的手機病毒傳播建模方法。該方法的主要技術要點包括：首先將人們通過發送簡訊或彩信來進行社會交往的行為抽象成社交網絡，再對社交網絡的特徵進行分析以揭示其與手機病毒傳播之間的關係；其次，引入了半馬爾可夫過程來對節點的狀態轉換進行建模，並將交互次數與狀態轉換概率有機地結合在一起，以有效地發現節點在遭受病毒攻擊後狀態變化的規律；第三，引入傳染係數和抵抗係數來刻畫個體差異性對病毒傳播的影響；還開發了一個模擬器來進行實驗驗證。本發明與現有技術相比，其優點是考慮了人們的社交行為和個體差異性對病毒傳播的影響，此方法簡單、實用且能有效地提高預測病毒傳播的速度和精度。
【專利說明】基於社交網絡和半馬爾可夫過程的手機病毒傳播建模方法
【技術領域】
[0001]本發明涉及手機病毒傳播動力學建模與分析，提供一種基於社交網絡和半馬爾可夫過程的手機病毒傳播建模方法，屬於網絡與信息安全領域。
【背景技術】
[0002]隨著簡訊(shortmessage service, SMS)和彩信(multimedia messagingservice, MMS)越來越受到人們的青睞，使得基於SMS/MMS的社交網絡具有非常適合手機病毒的傳播。因此，如何對基於SMS/MMS的病毒傳播動力學進行建模與分析，成為了移動通信網絡安全的一個重要問題。該病毒是在人們收發SMS/MMS進行社會交往時進行傳播的，具有隱蔽性強、傳播速度快、危害大等特點。另外，基於SMS/MMS的社交網絡的節點度分布具有冪律分布的特性，根據社交網絡和手機病毒傳播的特點，設計一種病毒傳播動力學模型來刻畫人們社會交往對手機病毒傳播的影響以及個體的差異性對手機病毒傳播的影響。這樣有利於發現手機病毒的傳播規律和預測手機病毒的傳播趨勢，為遏制手機病毒的傳播奠定基礎。
[0003]目前，現有的針對手機病毒的相關研究，大部分傳播模型都是採用生物病毒傳播學原理來建模，不能適用於大規模網絡環境，而且沒有考慮人們的社交行為和個體的差異性對手機病毒傳播的影響。
[0004]因此，考慮到國家、人們對網絡安全的需要，作為國家自然科學基金面上項目「智慧型手機病毒傳播動力學建模理論及分析方法研究」(61379041)的研究成果之一，我們提出了一種基於社交網絡和半馬爾可夫過程的手機病毒傳播建模方法。該方法將人們發送SMS/MMS來進行社會交往的行為抽象成社交網絡，再對社交網絡的特徵進行分析以揭示其與手機病毒傳播之間的關係；引入半馬爾可夫過程來對節點的狀態轉換進行建模，並將交互次數與狀態轉換概率有機地結合在一起；弓I入傳染係數和抵抗係數來刻畫個體差異性對病毒傳播的影響；採用Visual C++ 6.0和MATLAB 7.0的混合編程技術開發了一個模擬器來進行實驗驗證。
【發明內容】
[0005]本發明的目的是提供一種基於社交網絡和半馬爾可夫過程的手機病毒傳播建模方法。該方法考慮到病毒的複雜性及其傳播過程的不確定性，能更好地刻畫人們的社交行為和個體的差異性對病毒傳播的影響。從而為手機病毒的防控提供一種有效的解決方案。
[0006]為了實現上述目的，本發明利用實際的簡訊/彩信通信數據來構建社交網絡，以便發現和刻畫不同個體之間的交互關係與病毒傳播之間的關係。然後，對節點的異常行為及其轉換規律進行分析和建模；最後，引入傳染係數和抵抗係數來揭示個體的差異性與病毒傳播之間的關係。主要的
【發明內容】
如下。
[0007](I)社交網絡的構建它可用一個無向加權圖來表不,其中:K表不頂點集合，即表不移動通信網絡中的手機必為網絡中節點間的有向邊，表示手機用戶之間發送簡訊的行為，邊的弧頭指向表示簡訊行為的接受方#為有向邊的權重，表示發送簡訊的行為的值，值越大表示發送簡訊的數量越多。4表示頂點i的度，即手機的數量(表示連結的數量或手機擁有式.個朋友)。G7表示從i發送到J的簡訊和彩信的數量。另外，還引入兩個函數/(i)和/(i，j)分別映射每個頂點:eF和每條邊。因此，該圖可以分別用/(i)和/(i，j)來確定頂點和邊的權重。頂點和邊的權重的映射函數表示為:/(i)=j)= Cij+Cji。
[0008]頂點和邊的權重可同時用來表示手機被病毒感染的概率。從/(i)= 可以看出，頂點的權重取決於4。對於基於SMS/MMS的病毒，如果某部手機的入度大，就表示它更容易被病毒感染，而出度大表示它更容易把病毒傳染給其它手機。因此，那些具有節點度大的手機，無論是它的入度大還是出度大，都應當分配一個更大的頂點權重。任意兩臺手機相互之間的社會交往情況可用/(i，I): ^7允^來表示。
[0009](2)節點狀態分類
採用半馬爾可夫過程對手機感染病毒後出現異常行為進行建模的基礎是將手機劃分為不同的狀態。根據手機本身所表現出來的行為特性，擬把個體的狀態分為以下4種。
[0010]A)易感狀態S (Susc印tible)，即節點未被感染，並且沒有免疫力；病毒從處於易感狀態^的節點出發，通過網絡連接向四周傳播。
[0011]B)潛伏狀態A (Exposed),病毒入侵後被感染的節點處於潛伏狀態萬，由於不同節點自身對病毒的重視程度不同，處於潛伏期A的部分節點會進入狀態I和R，另一部分則會返回狀態S。
[0012]C)染病狀態J (Infected)，即節點已被感染，此時節點具有傳染性。
[0013]D)免疫狀態7? (Recovered)，在病毒傳播開來後，部分處於狀態S的節點通過採取一些安全措施對該病毒產生預免疫，進入免疫狀態/P。
[0014](3)狀態之間的相互轉換關係節點各狀態之間的相互轉換關係如下。
[0015]A)由於安裝殺毒軟體，一個處於易感狀態的節點轉換為免疫狀態；由於很多原因也可使該節點轉換為潛伏狀態，例如:沒有安裝殺毒軟體、從網上隨意下載應用程式並進行安裝。
[0016]B)如果一個處於感染狀態的節點能及時地安裝殺毒軟體，它便能轉換為免疫狀態或易感狀態。
[0017]C)如果一個處於潛伏狀態的節點能及時地採取相應的安全措施，它便能轉換為免疫狀態或易感狀態；但如果正處於病毒爆發時期，也可能轉換為感染狀態。
[0018]D)當一種新病毒出現時，一個處於免疫狀態的節點能再次轉換為易感節點。
[0019](4)節點異常行為建模
在半馬爾可夫過程中，節點從一個狀態轉移到另一個狀態可以用兩個矩陣來表示'P =(Pij)和/7⑴=(A7⑴)，其中表示節點從狀態乙變為狀態4的轉移概率;/7"⑴節點表示從當前狀態乙轉移到狀態&的時間分布。假定一個半馬爾可夫過程ir(i)，?彡0}，其狀態空間為r={& E, I, 及DTMC的一步轉移概率矩陣產所示，當i—°o時，轉移分布Pu(X)服從非格點的分布及具有極限概率&，則
π,Μ( f)
P = Ijm P (Λ = ^ V
其中，M(J)、分別表示在狀態Zj'厶逗留的平均時間，且M(f) = Β{%\Ζη=ι}
,IC/)=罰？} |ZS = j](設是在狀態乙的逗留時間，7)是在狀態&的逗留時間)；
Trj = (j e W)是的平穩分布，且?讀盧,ZjW7r/ = 1, 71J = TiieW7r^。
[0020]要計算Z77.,就需要求出和#(i)。然而，通過該式來計算Z7y也並不是一件容易的事情，因為難以確定逗留時間#(i)。因此，本發明不僅給出了基於半馬爾可夫過程的節點行為模型及用來分析極限狀態概率的計算表達式，而且建立了一個網絡場景並提供了相應的理論分析。
[0021](5)個體差異性建模
由於病毒的傳播與個體的抵抗力和病毒傳染性的強弱都有關，而現有的病毒傳播模型大都沒有考慮個體的差異性對病毒傳播的影響。因此，本發明引入了 3個參數來刻畫個體的差異性對病毒傳播的影響，具體描述如下。
[0022]A)傳染係數:用ICji (Infect1n Coefficient, IC)表示，即節點J.對i傳染性的強弱(OssI);當/?γ=ο，表示該節點沒有傳染性；當Icji=X，表示該節點具有極強的傳染性。
[0023]B)抵抗係數:用TPC1i7(Resisted Coefficient, RC)表示，即節點i對j的抵抗能力的大小(ο < --.? I);當RcijA，表示該節點具有極強的抵抗能力。
[0024]C)感染閾值:用JT1i (Infect1n Threshold, IT)表示，即節點i的朋友節點對其影響力的總和。用來判斷處於狀態S的節點的狀態是否會發生變化。
[0025](6)病毒傳播模型
根據簡訊/彩信病毒傳播的特點，在構建社會關係圖的基礎上，設計相應的狀態轉換算法，並利用該算法來刻畫簡訊/彩信病毒的傳播過程。狀態轉換算法具體為。
[0026]第I步:初始化網絡。根據簡訊/彩信數據集來統計網絡的相關信息，如節點的數量、簡訊發送情況等。
[0027]第2步:初始化每個節點的狀態。隨機地選節點J並將其狀態設置為/，其它節點狀態都設置為S。
[0028]第3步:統計朋友節點信息。每個節點根據與其它節點發送簡訊/彩信的情況，來統計各自的朋友節點信息。
[0029]第4步:設在某時刻t時訪問節點j,假設T表示節點從S狀態轉變為E狀態的閾值，則:如果J'的狀態為/，則遍歷J'的朋友節點，如果其朋友節點i的狀態為&而且，此時J'發送簡訊或彩信給i，那麼:A)當/ΡΓ時，則i以概率化轉變成狀態i?;B)當時，
則i保持狀態S不變；C)當ICβ二。或％7=1時，則i以概率/?轉變成狀態;同時，J'以概率Pm轉變成狀態W ;如果J'的狀態為E,則該節點以概率轉變成狀態/P，或該節點以概率Pei轉變成狀態I ;重複執行第4步,直到遍歷完所有節點為止。
[0030]第5步:?=?+1,算法結束。[0031 ] (7)病毒傳播分析
借鑑現有的傳染病傳播(如SARS、HIV、HlNl等)和有線網絡病毒傳播(如Code-Red、Slammer等)分析方法來確定涉及手機病毒傳播的相關參數的數量以及每個參數的取值範圍、初始值的大小等。對病毒傳播所依賴的拓撲結構的主要形式進行分析，並設計基於有向圖的Erd0s-R6nyi (ER)網絡拓撲結構生成算法，其主要思想是根據ER網絡拓撲結構的特點，採用隨機圖論對基於有向圖的ER網絡拓撲結構下的病毒傳播進行模擬分析。
[0032]由於複雜網絡領域的靜態拓撲結構生成算法只考慮網絡本身的特性，當應用到手機病毒傳播網絡生成時還需要考慮與病毒傳播過程相關的條件和屬性等。比如是否在兩個結點之間創建邊，除了滿足它們各自的度值要求之外，還需要考慮個體交互是否滿足給定的局部判定條件(抵抗因子和交互次數等)，同時還需賦予邊與交互關係相關的屬性值(如交互次數、持續時間等)。採用Visual C++ 6.0和MATLAB 7.0的混合編程技術開發了一個模擬器來來驗證基於有向圖的ER網絡拓撲結構生成算法的正確性和有效性。
【專利附圖】
【附圖說明】
[0033]圖1為社交網絡圖示例。
[0034]圖2為狀態轉換關係圖。
[0035]圖3為節點狀態轉換算法流程圖。
[0036]圖4為數據分析算法流程圖。
[0037]圖5為手機病毒傳播動力學分析圖。
【具體實施方式】
[0038]下面結合附圖對本發明做進一步的詳細說明。
[0039](I)社交網絡的構建
它可用一個無向加權圖來表不,其中:K表不頂點集合，即表不移動通信網絡中的手機必為網絡中節點間的有向邊，表示手機用戶之間發送簡訊的行為，邊的弧頭指向表示簡訊行為的接受方#為有向邊的權重，表示發送簡訊的行為的值，值越大表示發送簡訊的數量越多。4表示頂點i的度，即手機的數量(表示連結的數量或手機擁有式.個朋友)。G7表示從i發送到J的簡訊和彩信的數量。另外，還引入兩個函數/(i)和/(i，j)分別映射每個頂點I eF和每條邊(iJ) eS。因此，該圖可以分別用/(i)和/(i，j)來確定頂點和邊的權重。頂點和邊的權重的映射函數表示為:/(i)=j)= Cij+Cji。
[0040]頂點和邊的權重可同時用來表示手機被病毒感染的概率。從/(i)= 可以看出，頂點的權重取決於4。對於基於SMS/MMS的病毒，如果某部手機的入度大，就表示它更容易被病毒感染，而出度大表示它更容易把病毒傳染給其它手機。因此，那些具有節點度大的手機，無論是它的入度大還是出度大，都應當分配一個更大的頂點權重。任意兩臺手機相互之間的社會交往情況可用/(i，j)= &.允^來表示。任意兩臺手機不管在何時通過發送簡訊和彩信來進行通信，那麼它們都有機會成為朋友。因此，打開並激活一條來自對方的且攜帶病毒的消息的概率就會很大。表明了社交網絡既可以揭示任意兩臺手機之間是如何彼此產生聯繫的，也可以刻畫病毒是如何利用這種社會關係來進行傳播的。
[0041]本發明採用中國最大的移動通信網絡運營商之一——中國電信所提供的簡訊和彩信記錄來研究社交網絡的構建。消息記錄包括40萬用戶在2012年10月的3個星期內所發送的約2千萬條的簡訊和彩信。為了保護用戶隱私，簡訊和彩信的內容在提取時就被屏蔽了，提取的信息只保留了發送者和接收者的電話號碼及發送時間，而且對電話號碼也進行了技術處理，使用其它編號來代替。為了進一步說明社交網絡的構建過程，從中抽取10部手機在I周內發送簡訊/彩信的數量來構建了一個社交網絡(見附圖1)。
[0042](2)節點狀態分類
採用半馬爾可夫過程對手機感染病毒後出現異常行為進行建模的基礎是將手機劃分為不同的狀態。根據手機本身所表現出來的行為特性可把個體的狀態分為以下4種。
[0043]A)易感狀態S (Susc印tible)，即節點未被感染，並且沒有免疫力；病毒從處於易感狀態^的節點出發，通過網絡連接向四周傳播。
[0044]B)潛伏狀態A (Exposed),病毒入侵後被感染的節點處於潛伏狀態萬，由於不同節點自身對病毒的重視程度不同，處於潛伏期A的部分節點會進入狀態I和R，另一部分則會返回狀態S。
[0045]C)染病狀態J (Infected)，即節點已被感染，此時節點具有傳染性。
[0046]D)免疫狀態7? (Recovered)，在病毒傳播開來後，部分處於狀態S的節點通過採取一些安全措施對該病毒產生預免疫，進入免疫狀態/P。
[0047](3)狀態之間的相互轉換關係節點各狀態之間的相互轉換關係如下。
[0048]A)由於安裝殺毒軟體，一個處於易感狀態的節點轉換為免疫狀態；由於很多原因也可使該節點轉換為潛伏狀態，例如:沒有安裝殺毒軟體、從網上隨意下載應用程式並進行安裝。
[0049]B)如果一個處於感染狀態的節點能及時地安裝殺毒軟體，它便能轉換為免疫狀態或易感狀態。
[0050]C)如果一個處於潛伏狀態的節點能及時地採取相應的安全措施，它便能轉換為免疫狀態或易感狀態；但如果正處於病毒爆發時期，也可能轉換為感染狀態。
[0051]D)當一種新病毒出現時，一個處於免疫狀態的節點能再次轉換為易感節點。
[0052]由於節點在遭受病毒攻擊後，其狀態轉換有以下特點:一是節點的未來狀態僅與其當前狀態有關；二是導致節點狀態轉換的因素很多，使狀態轉移的時間不是指數分布的，而是一般分布。上述特點符合半馬爾可夫過程的基本性質，因此，可以採用半馬爾可夫過程對手機簡訊/彩信病毒傳播的節點異常行為進行建模。結合手機病毒傳播的特性，可得基於半馬爾可夫過程的節點狀態轉換關係圖(見附圖2)。
[0053]( 4 )節點異常行為建模
在半馬爾可夫過程中，節點從一個狀態轉移到另一個狀態可以用兩個矩陣來表示'P =(Pij)和/7⑴=(A7⑴)，其中表示節點從狀態乙變為狀態4的轉移概率;/7"⑴節點表示從當前狀態乙轉移到狀態&的時間分布。因此，{麼}的轉移概率矩陣為:
OP 覺 Psj Pss
η Pm O Pfi Pm
Ij = 4.>
O O O 1.1 O O O其中，Ai=O表示{4}中狀態轉換隻有從一種狀態轉換為另一種狀態；在上式中存在轉移概率為零的情況，如Pie=^ /^=0,表示處於感染狀態的節點不會轉變成為易感狀態或潛伏狀態。另外，由於隨機矩陣中一個狀態的轉移概率之和等於1，因此，/^=1，Pks=L
[0054]假定一個半馬爾可夫過程ΙΤ(?)，?≥0}，其狀態空間為r={& E, I, /?}及DTMC的一步轉移概率矩陣P所示，當? —⑴時，轉移分布Λ._/(?)服從非格點的分布及具有極限概率Λ.，則
【權利要求】
1.一種基於社交網絡和半馬爾可夫過程的手機病毒傳播動力學建模與分析方法，其特徵在於:首先利用人們在日常生活中進行社會交往所產生的實際簡訊/彩信通信數據來構建社交網絡，通過該網絡來刻畫社會交往與病毒傳播之間的關係；然後，建立節點異常行為模型以揭示節點在遭受病毒攻擊後狀態轉換的規律，如節點在各狀態逗留的時間分布、節點狀態之間的相互轉換關係；最後，建立個體差異性分析機制以刻畫個體的差異性對病毒傳播的影響。
2.根據權利要求1所述的基於簡訊/彩信的社交網絡，其特徵在於:對手機用戶之間相互發送簡訊/彩信所表現出的社會網絡行為進行分析並構建社交網絡，並引入複雜網絡理論來分析該社交網絡的特性，刻畫基於簡訊/彩信病毒傳播的各種參數對該病毒傳播的影響。
3.根據權利要求1所述的節點異常行為模型，其特徵在於:對手機在感染病毒前、後所處的狀態進行劃分，使處於各種狀態中的手機所表現的特徵更加突出；該模型分析了節點狀態的劃分方法及其在各狀態逗留的時間分布規律；並引入半馬爾可夫過程來揭示節點狀態之間的相互轉換關係、處於各狀態的極限概率及它們之間的內在聯繫。
4.根據權利要求1所述的個體差異性分析機制，其特徵在於:引入傳染係數(節點傳染性的強弱)和抵抗係數(節點的抵抗能力)來刻畫個體的差異性，並利用傳染係數和抵抗係數來預測處於易感染狀態^的節點的狀態是否會發生變化。
【文檔編號】H04L29/06GK104166708SQ201410390017
【公開日】2014年11月26日 申請日期:2014年8月11日 優先權日:2014年8月11日
【發明者】彭三城, 胡忠望 申請人:肇慶學院, 彭三城