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

徐迪迪

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

?

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

徐迪迪

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

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

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

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

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

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

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

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

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

(1)

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

Ra=Ra/sa

(2)

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

1.2未被攻擊時(shí)單個(gè)簇的可靠性計(jì)算

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

(3)

1.3未被攻擊時(shí)單個(gè)簇可靠性計(jì)算

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

(4)

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

(5)

(6)

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

(7)

(8)

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

(9)

(10)

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

(11)

1.4提出問(wèn)題

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

(12)

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

(13)

2提出解決方案

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

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

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

(14)

算法1當(dāng)每個(gè)簇中的偽裝組件sc為常量時(shí),求解出系統(tǒng)面臨最嚴(yán)重打擊情況下選擇最優(yōu)的防御策略D,以及所對(duì)應(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;每個(gè)簇中冗余組件的數(shù)目S;總防御資源Rtd;總攻擊資源Rta;制造一個(gè)偽裝組件的開(kāi)銷(xiāo)C;每個(gè)冗余組件的可靠性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)計(jì)算得到可靠性矩陣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仿真與實(shí)驗(yàn)結(jié)果

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

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

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

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

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

4結(jié)束語(yǔ)

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

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

參考文獻(xiàn)

[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

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

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

中圖分類(lèi)號(hào)TP393.08

文獻(xiàn)標(biāo)識(shí)碼A

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