徐迪迪

(西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院,陜西 西安　710071)

?

最優(yōu)的防御策略應(yīng)對理性的攻擊

徐迪迪

(西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院,陜西 西安710071)

摘要系統(tǒng)可靠性保護,通常采用投票算法和冗余策略。然而,考慮到系統(tǒng)外界存在攻擊者時,系統(tǒng)的可靠性將面臨威脅。在文中,主要研究介于系統(tǒng)防御策略和理性攻擊者之間的系統(tǒng)可靠性。防御者保證系統(tǒng)可靠性不僅可采取投票算法,還可利用防御資源進行制造偽裝組件或保護系統(tǒng)組件;攻擊者利用攻擊資源隨機選擇系統(tǒng)中某些簇中組件進行攻擊。通過建立模型,解決在給定的攻防資源下,選擇最優(yōu)防御策略應(yīng)對攻擊策略,從而保證系統(tǒng)的可靠性。

關(guān)鍵詞系統(tǒng)可靠性;投票算法;冗余;防御策略

可靠性對于許多系統(tǒng),尤其在軍事系統(tǒng)中是重要的。系統(tǒng)可靠性通常利用投票策略[1]和冗余[2]進行保護。但系統(tǒng)處在外界攻擊條件下,系統(tǒng)可靠性將會降低。系統(tǒng)應(yīng)當(dāng)在防御資源下進行必要的保護,從而提升系統(tǒng)可靠性。防御資源一方面用于保護系統(tǒng)中某些簇中的組件,另一方制造一些偽裝組件,干擾攻擊者對投票組件的打擊[3]。先前已有諸多對提高可靠性的研究。

本文總結(jié)文獻[4～6]的想法,提出了一種更加適應(yīng)實際情況的攻防策略模型,以及一種算法,可有效地解決最優(yōu)的防御策略應(yīng)對理性的攻擊,并提高系統(tǒng)可靠性。

1假設(shè)和提出問題

1.1系統(tǒng)模型和假設(shè)

假設(shè)系統(tǒng)中包含N個相互獨立的簇,每個簇中有S個冗余組件,各自冗余組件的可靠性均為p。對于系統(tǒng)中每個簇而言,其可靠性是通過半數(shù)投票策略產(chǎn)生正確結(jié)果的概率。每一個簇中都能選擇自身的一些冗余組件作為投票組件[4]。這些參與投票過程的組件影響著系統(tǒng)的可靠性。在每個簇中,投票組件的數(shù)目為Sv,其中1≤Sv≤S。

進一步假設(shè),系統(tǒng)給定總的防御資源Rtd,其能用于加強簇中組件的保護或者制造偽裝組件。在每個簇中,被均分到每個簇中的防御資源為Rd,其中Rd=Rtd/N。制造單個偽裝組件開銷C個單位的防御資源。Sc表示在每個簇中制造的偽裝組件的數(shù)目,其中Sc×C≤Rd。攻擊者分辨不出各個簇中原有組件和添加到每個簇中偽裝組件的區(qū)別,從降低攻擊到投票組件的概率。在每個簇中,剩余的防御資源為(Rd-Sc×C)。其被平均分配用于保護簇中的一些組件。Sp表示每個簇中保護的組件數(shù),其中0≤Sp≤S。因此,在各個簇中,每個被保護的組件上分配的防御資源為rd

(1)

攻擊者隨機選擇系統(tǒng)中某些簇的部分組件進行打擊。假設(shè)Rta表示全部的攻擊資源。攻擊者隨機挑選h,個簇作為攻擊目標(biāo)h≤n。在每個被攻擊的簇中,均分到的攻擊資源為Ra,其中Ra=Rta/h。在被攻擊的簇中,攻擊資源Ra被均分到一些組件上進行攻擊,攻擊的組件的數(shù)目為sa,其中1≤sa≤s+sc。因此,在各個簇中,每個被攻擊的組件上分配的攻擊資源為Ra

Ra=Ra/sa

(2)

依據(jù)文獻[8],攻擊資源Ra和防御資源RD作用在同一個組件上。若Ra>RD,這個被作用的組件失效,即該組件的可靠性從原有的P直接降為0;若Ra≤RD,該組件保持原有的可靠性P。

1.2未被攻擊時單個簇的可靠性計算

當(dāng)系統(tǒng)中一個簇免于攻擊,意味著簇中沒有一個組件失效。假設(shè)這個簇中選擇簇中sv個冗余組件作為投票組件。依據(jù)半數(shù)以上投票原則,這個簇的可靠性為

(3)

1.3未被攻擊時單個簇可靠性計算

假設(shè)一個簇被攻擊,防御者制定的策略主要選取恰當(dāng)?shù)谋Ｗo組件Sp(0≤Sp≤S),投票組件Sv(1≤Sv≤S),制造適當(dāng)?shù)膫窝b組件Sc。對于攻擊者,其攻擊策略主要選擇適量的攻擊組件Sa(1≤Sa≤S+Sc)。

(4)

攻擊者擊中到投票組件的概率為

(5)

(6)

一個遭受攻擊的簇,利用投票原則獲得正確結(jié)果的概率為

(7)

(8)

經(jīng)討論,攻擊者擊中被保護的投票組件的概率為

(9)

(10)

其中l(wèi)b=Sa-S-Sc+Sv,以及

(11)

1.4提出問題

假設(shè)系統(tǒng)中包含N個相互獨立的簇,每個簇中有S個冗余組件,各自冗余組件的可靠性均為p。攻擊者利用總攻擊資源Rta以及挑選h個簇進行攻擊。對于每個被攻擊的簇而言,均分到的攻擊資源Ra,挑選簇中一些組件進行攻擊。與此同時,防御者將總防御資源Rta均分到系統(tǒng)每個簇。在每個簇中,防御資源Rd被用來制造偽裝組件Sc和選擇保護一些組件Sp。最重要的是挑選簇中的一些組件作為投票組件Sv,參與投票過程。綜合以上討論分析,系統(tǒng)可靠性根據(jù)每個簇的可靠性加權(quán)可得

(12)

解決的問題可歸納為選擇最優(yōu)sc,sP,sv在攻擊者選擇h,sa最小化t(sc,sP,sv,h,sa)的情況下使保證t(sc,sP,sv,h,sa)最大化,即

(13)

2提出解決方案

當(dāng)在每個簇中,選擇偽裝組件sc的數(shù)目為定值,保護組件和投票組件sv的數(shù)目可變化。由于投票組件的取值范圍介于1～s,被保護的組件sP的取值范圍介于0～s,所以系統(tǒng)的總防御策略為nD=(s+1)s。同時,可對防御策略進行按順序編號,對于給定的sc,第I(1≤I≤na)防御策略對應(yīng)的每個簇中被保護的組件和投票組件分別為sP=[j/(s+sc)]和sv=I-s×[I/s]+s。

對于攻擊者,被攻擊簇的范圍介于1～n,每個被攻擊簇中遭受打擊的組件數(shù)目取值介于1～(s+sc),從而總攻擊策略為na=n(s+sc),第j(1≤I≤na)攻擊策略對應(yīng)的被攻擊簇的數(shù)目和每個簇中被打擊的組件數(shù)目分別為h=[j/(s+sc)]和sa=j-(s+sc)×[j/(s+sc)]+(s+sc)。

當(dāng)攻擊策略(h,sa)和防御策略(sc,sP,sv)被確定,系統(tǒng)可靠性可通過公式(10～12)計算求得。因此,可用一個矩陣M=(tI,j)nD×na記錄系統(tǒng)的可靠性,其中tI,j表示防御者和攻擊者分別選擇第I種防御策略和第j種攻擊策略時所對應(yīng)的系統(tǒng)可靠性。

(14)

算法1當(dāng)每個簇中的偽裝組件sc為常量時,求解出系統(tǒng)面臨最嚴(yán)重打擊情況下選擇最優(yōu)的防御策略D,以及所對應(yīng)的系統(tǒng)可靠性tmaxmin。

輸入可靠性矩陣M=(tI,j)nD×na。

輸出tmaxmin和D。

1:Tmaxmin←0;D←0;

2:for i←1 to Nddo

3:Tmin←1

4:for j←1 to Nado

5:if Tmin>ti,jthen

6:Tmin←ti,j

7:end if

8:end for

9:if Tmaxmin

10:Tmaxmin←Tmin

11:set dito 1,and the rest to 0。

12:end if

13:end for

14:return Tmaxmin,D。

算法2當(dāng)防御和攻擊資源都是常量的情況下,求解最終的防御策略。

輸入系統(tǒng)中所有簇的數(shù)目N;每個簇中冗余組件的數(shù)目S;總防御資源Rtd;總攻擊資源Rta;制造一個偽裝組件的開銷C;每個冗余組件的可靠性p。

輸出最優(yōu)的系統(tǒng)可靠性Tmaximun和防御策略(Sc,Sp,Sv)。

1:Tmaxmin←-1;Dfinal←0;

2:Sc←0;Sp←0;Sv←0;

3:for Sc←0 to [Rd/C] do

4:Nd←(S+1)S;Na←N(S+Sc);

5:利用式(12)計算得到可靠性矩陣M

6:利用算法1得到Tmaxmin,D

7:if Tmaximun

8:Tmaximun←Tmaxmin

10:end if

11:end for

12:get i from Dfinal

13:get,Tmaximun,Sc,Sp,Sv

3仿真與實驗結(jié)果

根據(jù)算法2進行實驗,主要分析攻擊資源和防御資源對防御策略的影響。

在實驗中,研究防御資源和防御策略之間的關(guān)系。同樣設(shè)置系統(tǒng)中有10個簇,每個簇中有7個冗余組件,且冗余組件的可靠性均為0.9,制造一個偽裝組件開銷3個單位的防御資源?？偡烙Y源的數(shù)量從100增加到1 100個單位,總攻擊資源為400個單位。

圖1　總的防御資源與防御策略之間的關(guān)系圖

圖2　最大破壞攻擊下的最大可靠性與隨機攻擊下的可靠性

在圖1中,防御策略隨著防御資源的增加而不斷改變。當(dāng)防御資源較少時,防御者會在每個簇中保護較少的冗余組件,并選擇其作為投票組件參與投票過程。當(dāng)防御資源不斷增加時,防御者制造較多的偽裝組件,保護更多的冗余組件并選擇其作為投票組件。在圖2中,系統(tǒng)的可靠性隨著總防御資源的增加而不斷增大。同時,系統(tǒng)在最大破壞攻擊下的最大可靠性與隨機攻擊下可靠性之間的差異逐漸減小。因防御資源的不斷增加,用于保護投票組件的資源也逐漸增加,從而系統(tǒng)在最大破壞攻擊下的最大可靠性不斷提高,逼近期望可靠性。

4結(jié)束語

本文主要研究在給定總的攻擊資源和防御資源下,選擇最優(yōu)防御策略保證系統(tǒng)可靠性。進一步而言,在限制的條件下,提出解決問題的算法。最后通過實驗可知:當(dāng)防御資源少于攻擊資源時,防御者在每個簇中選擇較少的冗余組件進行保護,并選擇被保護的組件作為投票者。反之,當(dāng)防御資源較為豐富時,防御者制造較多的偽裝組件,保護較多的冗余組件充當(dāng)投票者。

研究過程仍有不足,例如考慮系統(tǒng)結(jié)構(gòu)較為簡單。在實際過程中,系統(tǒng)結(jié)構(gòu)十分復(fù)雜。系統(tǒng)中每個簇有不同的作用,簇與簇之間還有緊密的聯(lián)系。因此,下一步準(zhǔn)備在復(fù)雜的系統(tǒng)模型中研究系統(tǒng)的可靠性和攻防策略。

參考文獻

[1]Li Wang,Zheng Li,Ren Shangping.Optimal voting strategy against rational attackers[C].Timisoara,Romania:In 2011 6th International Conference on Risks and Security of Internet and Systems,2011.

[2]Mancini L,Koutny M.Formal specification of n-modular redundancy[C].Roma:CSC’86:Proceedings of the 1986 ACM Fourteenth Annual Conference on Computer Science,1986.

[3]Mokube I,Adams M.Honeypots:concepts,approaches,and challenges[C].Portland:Proceeding 45th Annu.Southeast Regional Conference,2007.

[4]Wang L,Leiferman Y,Ren S,et al.Improving complex distributed software system availability through information hiding[C].UU,USA:Proceeding of ACM Sympore Application Computer,2010.

[5]Hausken K.Strategic defense and attack for series and parallel reliability systems[J].Europe Journal of Operational Research,2008,186(2):856-881.

[6]Levitin G,Hausken K.False targets vs.redundancy in homogeneous parallel systems[J].Reli Engineering System Safety,2009,94(2):588-595.

[7]Tong Z,Kain R.Vote assignments in weighted voting mechanisms[J].IEEE Transactions on Computer,1991,40(5):664-667.

[8]Wang L,Ren S,Yue K,et al.Optimal resource allocation for protecting system availability against random cyber attacks[C].CA USA:Proceeding of 3rd International Conference,ICCRD,2011.

[9]Levitin G,Hausken K.Parallel systems under two sequential attacks[J].Reli Engineering System Safety,2009,94(3):763-772.

Optimal Defense Strategy Against Rational Attackers

XU Didi

(School of Mathematics and Statistics,Xidian University,Xi’an 710071,China)

AbstractSystem reliability is often protected by voting algorithms and redundancy,but is still threatened by attackers.In this paper,the system reliability between system defense strategies and rational attacks is discussed.The Defender can not only choose voting components,but also create camouflaging components and protect system components.The Attacker can choose clusters and components to attack in system.The problem of deciding the optimal defense strategies against attack strategies is modeled with both the defender and the attacker are given fixed resources.

Keywordsreliability;voting algorithm;redundancy;defense strategy

doi:10.16180/j.cnki.issn1007-7820.2016.05.022

收稿日期:2015-10-14

基金項目:國家自然科學(xué)基金資助項目(71271165;61373174);陜西省自然科學(xué)基金資助項目(2015)

作者簡介:徐迪迪(1990—),男,碩士研究生。研究方向:復(fù)雜系統(tǒng)可靠性,網(wǎng)絡(luò)優(yōu)化。

中圖分類號TP393.08

文獻標(biāo)識碼A

文章編號1007-7820(2016)05-079-04