以最佳化技術為基礎之網路存活性優化法

An Optimization-based Methodology for Maximization of Network Survivability against Intelligent Attacks

臧柏皓(Po-Hao (Joseph) Tsang)

指導教授 ： 林永松

國立臺灣大學/管理學院/資訊管理學研究所/博士(2011年)

https://doi.org/10.6342/NTU.2011.00820

摘要

自從美國9/11恐怖攻擊活動以降，安全議題已受到全球之高度重視，特別是如何以效果與效率兼備的方式，保護對社會運作至為重要之關鍵資訊基礎建設。從商業的觀點與脈絡來看，資訊安全漸次著重於管理各類型風險，並逐漸由探討「絕對的安全性」延伸至「相對的存活性(Survivability)」，也就是關注在確保資訊可用性及服務持續性(Service Continuity)。為了有效提升網路遭到智慧型攻擊後的存活性，防禦者(網路營運者)必須對所管控之網路，投注其有限的資源並加以妥善配置，用來建立各類型安全防禦機制。另防禦者在建立其防禦資源配置策略(Resource Allocation Strategy)之際，亦需同步考量潛在攻擊者會隨著其所採行防禦策略之不同、所引致攻擊策略之調整。
本論文主要針對網路攻防(Network Attack and Defense)議題，從防禦者的觀點探討如何推導出適切的資源配置策略來嚇阻智慧型攻擊，以提升網路存活性，並進而降低整體風險。我們係從防禦者在建立資源配置策略時所需考量的三個重要因素(核心節點之數量、攻擊作為之相依性、防禦資源投資之效用)來進行分析；植基於這三個要素，我們建立了一個整合性的框架用以分類網路存活性問題，該框架並提供防禦者一個較為宏觀的角度來進行資源配置之決策。
由於此些問題的本質具備高度複雜性與困難度，為求得近似最佳化的決策品質與時效，我們運用數學規劃法(Mathematical Programming)之最佳化(Optimization)技巧為基礎方略、使用數學最佳化模型來描述網路存活性問題、採用拉格蘭日鬆弛法(Lagrangean Relaxation)進行求解(此法在解決複雜度高之最佳化數學問題上有較佳之表現)，並輔以基於該法之解題過程所妥善設計出的啟發式演算法，來解決這一系列最佳化問題，是故本論文中各網路存活性問題之實驗結果相較於一般性方法所得之實驗結果，獲致了相當程度之效能改良。
本論文之貢獻包括：採行一種系統性的流程進行網路存活性文獻之探討；針對網路存活性問題，提出一個整合性的框架，用以幫助防禦者建立資源配置策略；發展出一個一般性的最佳化模型，來描述各類網路存活性問題之共同假設、概念及數學模型結構；針對真實環境中的網路存活性問題，使用適切的數學最佳化模型來描述；植基於拉格蘭日鬆弛法，發展出近似最佳化的啟發式演算法來解題；各問題的實驗結果顯示出設計防禦策略時所應考量的重要參數及因素，並提供適切的工程指引與建議給防禦者進行資源配置時之參考。

關鍵字

拉格蘭日鬆弛法 ； 數學規劃法 ； 網路攻防 ； 存活性 ； 最佳化 ； 資源配置策略 ； 服務持續性

並列摘要

Since the 9/11 terrorist attacks in the United States, the focus on security has become increasingly global, especially the effective and efficient protection of critical information infrastructures that are crucial to society. From a business perspective and context, information security has expanded to embrace risk management and evolved into a new concept called survivability, which focuses on ensuring the availability of information and the continuity of services. To enhance survivability, a defender (network operator) must invest a fixed amount of resources and distribute it among different defensive measures appropriately. The defender’s strategy should consider that an attacker will constantly adjust his strategy to achieve his goals.
In this dissertation, we focus on the crucial research domain that enables defenders to gain a global understanding of how to derive adequate resource allocation strategies against intelligent attackers in the context of network survivability. We also analyze three key characteristics of resource allocation (core node(s), attack action dependency, and defensive investment effectiveness) that defenders should consider when designing their defense strategies. Based on these characteristics, we create an integrated framework, which provides a comprehensive macro view of decision-making for defenders to categorize network survivability problems.
We express attack-defense problems in terms of mathematical formulations, solution approaches, and the experimental performance of the approaches. To solve these complicated optimization-based problems, we apply the Lagrangean Relaxation (LR) method as our main solution approach. In addition, we propose several optimization-based techniques and heuristics to address different categories of network survivability problems.
The contributions of this dissertation are as follows: a systematic process is adopted to conduct a survey of the literature on network survivability; an integrated framework of network survivability problems is proposed to help defenders design defense resource allocation strategies; a generic optimization model is developed to describe the common assumptions, concepts, and structures in the mathematical formulations; and suitable mathematical formulations are presented to model complex real-world network survivability problems clearly. In addition; based on the LR approach with related Lagrangean multipliers, we have developed several heuristics to solve the optimization problems. The related experiments identify the parameters, variables, issues, and characteristics that should be considered when designing a defense strategy, and also provide engineering guidelines or references for defenders.

並列關鍵字

Lagrangean Relaxation ； Mathematical Programming ； Network Attack and Defense ； Survivability ； Optimization ； Resource Allocation Strategy ； Service Continuity

參考文獻

K. M. M. Aung, K. Park, and J. S. Park, “Survivability Analysis of a Cluster System with 4th Generation Security Mechanism: Regeneration,” International Journal of Network Security, Volume 3, Number 3, pp.271–278, November 2006.

M. Abramowitz and I. A. Stegun, “Normal or Gaussian Probability Function,” Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, Dover Publications, p.931, 1965.

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms and Applications, Prentice Hall, 1993.

R. Albert, H. Jeong, and A.-L. Barabasi, “Error and Attack Tolerance of Complex Networks,” Nature, Volume 406, pp.378-382, July 2000.

F. A. Al-Zahrani, “Survivability Performance Evaluation of Slotted Multi-fiber Optical Packet Switching Networks With and Without Wavelength Conversion,” Proceedings of the 2nd Information and Communication Technologies (ICTTA'06), pp.2242-2247, April 2006.