[發(fā)明專利]基于對(duì)偶算法的備份網(wǎng)絡(luò)最短路阻斷方法和裝置

有效

• 申請(qǐng)?zhí)枺?/td>: 202210043448.6
• 申請(qǐng)日: 2022-01-14
• 公開（公告）號(hào): CN114401137B
• 公開（公告）日: 2023-09-08
• 發(fā)明（設(shè)計(jì)）人: 朱先強(qiáng);戴周璇;陸敏;朱承;周鋆;劉斌;張維明;丁兆云;黃松平
• 申請(qǐng)（專利權(quán)）人: 中國人民解放軍國防科技大學(xué)
• 主分類號(hào): H04L9/40
• 分類號(hào): H04L9/40;H04L41/14;G06F30/20
• 代理公司: 長沙國科天河知識(shí)產(chǎn)權(quán)代理有限公司 43225
• 代理人: 趙小龍

本申請(qǐng)涉及基于對(duì)偶算法的備份網(wǎng)絡(luò)最短路阻斷方法和裝置。方法包括：根據(jù)節(jié)點(diǎn)網(wǎng)絡(luò)的最短路阻斷問題，建立網(wǎng)絡(luò)模型；網(wǎng)絡(luò)模型中攻擊方目標(biāo)為在有限資源時(shí)阻斷節(jié)點(diǎn)網(wǎng)絡(luò)中的網(wǎng)絡(luò)鏈路以最大化防御方的最短路徑，防御方目標(biāo)為在節(jié)點(diǎn)網(wǎng)絡(luò)中尋找由起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最短路徑；根據(jù)節(jié)點(diǎn)網(wǎng)絡(luò)建立備份網(wǎng)絡(luò)，根據(jù)備份網(wǎng)絡(luò)和網(wǎng)絡(luò)模型得到備份網(wǎng)絡(luò)模型；備份網(wǎng)絡(luò)模型中節(jié)點(diǎn)網(wǎng)絡(luò)受到攻擊方阻斷后，防御方根據(jù)當(dāng)前網(wǎng)絡(luò)狀態(tài)激活啟用備份網(wǎng)絡(luò)中的備份鏈路，以最小化攻擊方的攻擊效果；根據(jù)約束條件和優(yōu)化目標(biāo)，構(gòu)建備份激活最短路阻斷模型；基于對(duì)偶算法求解。采用本申請(qǐng)考慮防御方能夠進(jìn)行鏈路備份并在攻擊時(shí)激活，以降低攻擊對(duì)網(wǎng)絡(luò)的影響。

技術(shù)領(lǐng)域

本申請(qǐng)涉及計(jì)算機(jī)處理技術(shù)領(lǐng)域，特別是涉及基于對(duì)偶算法的備份網(wǎng)絡(luò)最短路阻斷方法和裝置。

背景技術(shù)

網(wǎng)絡(luò)阻斷(Network?Interdiction)是一個(gè)與網(wǎng)絡(luò)結(jié)構(gòu)、節(jié)點(diǎn)屬性密切相關(guān)的運(yùn)籌優(yōu)化問題，其核心是研究攻防雙方在網(wǎng)絡(luò)中的目標(biāo)以及行為，目前在軍事、交通運(yùn)輸、經(jīng)濟(jì)等領(lǐng)域有著廣泛的應(yīng)用。由于需要同時(shí)考慮到網(wǎng)絡(luò)的防御方和阻斷方雙方的策略和動(dòng)作，因此網(wǎng)絡(luò)阻斷問題通常也需要從主從博弈問題的角度來考慮。與網(wǎng)絡(luò)阻斷問題相反的則是網(wǎng)絡(luò)防護(hù)問題：針對(duì)阻斷方對(duì)己方網(wǎng)絡(luò)進(jìn)行的可能阻斷，如何使用有限的防護(hù)資源制定節(jié)點(diǎn)或邊的防護(hù)策略，使得己方網(wǎng)絡(luò)受阻斷的影響盡可能地小。因此，在網(wǎng)絡(luò)安全領(lǐng)域中，不論是從網(wǎng)絡(luò)進(jìn)攻方或是網(wǎng)絡(luò)防御方的角度，研究網(wǎng)絡(luò)阻斷問題都具有十分重要的意義。

現(xiàn)有研究在網(wǎng)絡(luò)阻斷問題的建模和求解等方面不斷發(fā)展，但是仍存在一些制約其實(shí)際應(yīng)用的挑戰(zhàn)，包括：

現(xiàn)有的網(wǎng)絡(luò)阻斷研究主要是從攻擊方的角度，考慮如何以最小代價(jià)使敵方網(wǎng)絡(luò)降效，甚至癱瘓其整個(gè)網(wǎng)絡(luò)。現(xiàn)有研究通常假設(shè)防御方總是被動(dòng)應(yīng)對(duì)攻擊而很少考慮攻防過程中的主動(dòng)防御，因而難以有效反映實(shí)際攻防決策特點(diǎn)。

但在實(shí)際過程中，防御方除優(yōu)化基于自身目標(biāo)的決策外，還具有一定的防御資源用以在攻防過程中部署主動(dòng)防御策略，因而在阻斷問題研究中，忽略防御方的主動(dòng)防御策略會(huì)導(dǎo)致模型難以準(zhǔn)確刻畫實(shí)際中的攻防過程并且不能有效反映實(shí)際攻防決策特點(diǎn)。

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

基于此，有必要針對(duì)上述技術(shù)問題，提供一種基于對(duì)偶算法的備份網(wǎng)絡(luò)最短路阻斷方法和裝置，考慮防御方能夠進(jìn)行鏈路備份，并在攻擊時(shí)能夠激活備份，以降低攻擊對(duì)網(wǎng)絡(luò)造成的影響。

基于對(duì)偶算法的備份網(wǎng)絡(luò)最短路阻斷方法，包括：

根據(jù)節(jié)點(diǎn)網(wǎng)絡(luò)的最短路阻斷問題，建立網(wǎng)絡(luò)模型；所述網(wǎng)絡(luò)模型中攻擊方目標(biāo)為在有限資源時(shí)阻斷所述節(jié)點(diǎn)網(wǎng)絡(luò)中的網(wǎng)絡(luò)鏈路以最大化防御方的最短路徑，防御方目標(biāo)為在節(jié)點(diǎn)網(wǎng)絡(luò)中尋找由起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最短路徑；

根據(jù)所述節(jié)點(diǎn)網(wǎng)絡(luò)，建立備份網(wǎng)絡(luò)，以及根據(jù)所述備份網(wǎng)絡(luò)和所述網(wǎng)絡(luò)模型，得到備份網(wǎng)絡(luò)模型；所述備份網(wǎng)絡(luò)模型中節(jié)點(diǎn)網(wǎng)絡(luò)受到攻擊方阻斷后，防御方根據(jù)當(dāng)前網(wǎng)絡(luò)狀態(tài)激活啟用備份網(wǎng)絡(luò)中的備份鏈路，以最小化攻擊方的攻擊效果；

根據(jù)所述備份網(wǎng)絡(luò)模型中的約束條件和優(yōu)化目標(biāo)，構(gòu)建備份激活最短路阻斷模型；

基于對(duì)偶算法，對(duì)所述備份激活最短路阻斷模型進(jìn)行求解。

在一個(gè)實(shí)施例中，根據(jù)所述節(jié)點(diǎn)網(wǎng)絡(luò)，建立備份網(wǎng)絡(luò)，以及根據(jù)所述備份網(wǎng)絡(luò)和所述網(wǎng)絡(luò)模型，得到備份網(wǎng)絡(luò)模型包括：

所述網(wǎng)絡(luò)模型包括多個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)之間形成網(wǎng)絡(luò)鏈路，從所述網(wǎng)絡(luò)模型中提取鏈路備份構(gòu)成所述備份網(wǎng)絡(luò)，根據(jù)所述網(wǎng)絡(luò)模型和所述備份網(wǎng)絡(luò)，得到備份網(wǎng)絡(luò)模型；

其中，備份網(wǎng)絡(luò)定義為G(N，A)，N＝{1，2，...，}表示節(jié)點(diǎn)集合，A＝{(i，j)|i，j∈N}表示網(wǎng)絡(luò)鏈路的集合，B＝{(i，j)|i，j∈N}表示鏈路備份的集合，B是A的真子集，i，j表示節(jié)點(diǎn)編號(hào)。

在一個(gè)實(shí)施例中，根據(jù)所述備份網(wǎng)絡(luò)模型中的約束條件和優(yōu)化目標(biāo)，構(gòu)建備份激活最短路阻斷模型包括：