考慮攻擊環境下達到違反服務品質最小化之近似最佳化網路規劃及防禦資源配置策略

Abstract

隨著網際網路的方便性，資訊安全的問題也越來越重要。近幾年來，有意及無心的網路犯罪事件層出不窮。其中，攻克網路中某些特定的伺服器並降低其處理能力，是影響網路服務品質最常見的網路犯罪手法之一。因此我們應發展出有效的策略來防範如此的攻擊，例如防禦資源的配置。此外，網路規劃也必須納入資訊安全的考量。 在這篇論文中，我們提出一個最小最大化的數學規劃問題來塑造網路管理者和攻擊者間相互的行為。在內層問題（ARRAS問題）中，考慮的是一個攻擊者該選擇哪些節點來攻擊並有效配置其有限的攻擊資源，以最大化因為違反服務品質而網路管理者必須付出的代價，例如賠償。在外層問題（NPDRAS問題）中，網路管理者則希望在有限的預算中，設計一個良好的網路並有效的配置防禦資源，來最小化必須付出的代價。為了求得此問題的最佳解，我們利用拉格蘭日鬆弛法為基礎的演算法來處理內層的問題，並利用內層問題的解和調整預算的演算法來處理外層的問題。

With the convenience of Internet, the problem of information security has caught more and more attentions. Events of witting or unwitting cybercrimes emerge in an endless stream in past years. Among them, to compromise particular servers and then degrade their process capability is one of the most popular cybercrimes in order to further affect the Quality-of-Service (QoS) of the network. For taking precautions against such attacks, we should develop effective defense strategies such as defense resources allocation. Besides, the network planning has to be considered in the realm of information security. In the thesis, we propose a min-max mathematical programming problem to model the mutual behavior between a network administrator and an attacker. In the inner problem, called the ARRAS problem, the attacker would like to maximize the total penalty the administrator has to pay for due to QoS violations by deciding which node to attack and allocating the limited attack budget effectively. In the outer problem, called the NPDRAS problem, the network administrator hopes to minimize the total penalty by planning a well network and allocating defense resources intelligently under a limited budget. For obtaining near optimal solutions, we use the Lagrangean relaxation-based algorithm to solve the ARRAS problem and exploit the solutions of ARRAS problem and the proposed budget adjustment procedure to solve the NPDRAS problem.