Near Optimal Secret Sharing and Defense Resource Allocation Plans for QoS Constrained Information Leakage Minimization

資訊系統與網際網路的興盛，促使多數企業應用資訊技術來獲得競爭優勢，而各企業皆有機密的營運資料，利用電子數位化的方式儲存。但是核心營運的方針若被對手得知，將使企業失去競爭力與形象受損。因此，個人或是企業需要降低機密資訊遺漏的風險，也需考量確保機密資訊的可用性，是否能讓合法使用者在有效時間內使用機密資訊。面對日益攀升的資料竊取行為所帶來嚴重損失，發展有效的防禦策略是當務之急的議題。 本論文中提出整合網路規劃的資訊安全管理問題，將攻防情境轉化成最小-最大化的雙層數學模型問題。在內層問題中，攻擊者必須利用有限的資源來進行資料竊取動作並造成最大化傷害，包含竊取機密資訊拼圖與相對應解密鑰匙才能構成資訊遺漏的傷害。而在外層問題中，網路管理者妥善分配其預算資源，以網路規劃觀點建置拓墣，在縱深防禦概念下設計出高度強韌的網路，配合秘密分享機制與防禦資源部署達到資訊隱密性與可用度，使攻擊行為不同傳統方式，如攻克節點就可造成傷害，試圖最小化資訊遺漏的傷害損失。除此之外，因考量真實網路環境會發生的傳輸連結故障，需在網路規劃時確保整體網路傳輸的可靠度以及滿足使用者服務品質要求。針對此雙層數學問題，我們提出拉格蘭日鬆弛法及次梯度法為基礎的演算法來解決問題。另外，我們針對初始部署問題建置一個獨立單層數學模型，定義機密資訊離散指標來衡量攻擊者的影響，利用模擬退火法基礎的演算法進行處理，並利用電腦實驗來評估這些演算法的效率與效果。With the rapid prosperity of information systems and the Internet, most enterprises obtain competitive advantage by means of these information technologies. Hence, each enterprise uses the electronic equipment to store the sensitive information about core competence of the business. However, if the business secrets are leaked by opponents, it would lead to lose the competence and ruin their reputation for victims. For this reason, individuals or enterprises must protect the secrets from information leakage and ensure the availability for each legitimate user. As a result of the more criminal problems as time goes by, it becomes one of the important issues to develop effective defense strategies against information theft nowadays. n this thesis, we consider the network planning in the realm of the information security. The attack-defense scenario is formulated as the min-max mathematical model. In the inner problem, the attacker must allocate his/her limited attack budget to steal the sensitive information in order to cause maximal damage. In addition, the attacker could not reveal the secret unless he/she collects the enough number of shares and the corresponding decrypted key. n the other hand, in the outer problem, the network operator must construct the network topology and take account of the concept of defense-in-depth to design the most robust network. Furthermore, the combination of the secret sharing scheme and defense resource allocation strategy is applied for the sake of the confidentiality and availability. However, the attacker’s behavior is different from traditional attacks that he/she causes damage as soon as compromising nodes. Because of the consideration of the link malfunction, the network operator should not only guarantee the reliability of the network transmission but also satisfy the Quality-of-Service for legitimate users. he Lagrangean Relaxation-based algorithm and the subgradient-based algorithm are proposed to solve the two layer mathematical problem. Beside, we further formulate the independent single layer model for the initial network deployment problem and define the “Discrete Degree” metric to represent the impact of the attacker. The Simulated Annealing-based algorithm is applied to handle this problem. Finally, we evaluate the efficiency and effectiveness of the proposed algorithms by computational experiments.論文摘要 VHESIS ABSTRACT VIable of Contents VIIIist of Tables Xist of Figures XIhapter 1 Introduction 1.1 Background 1.2 Motivation 6.3 Literature Survey 8.3.1 Secret Sharing Scheme 8.3.2 QoS Routing 12.3.3 Survivability 16.4 Proposed Approach 18.5 Thesis Organization 19hapter 2 Problem Formulation 20.1 Problem Description 20.2 Problem Formulation of the NPDS Model 23.3 Problem Formulation of the ATSS Model 37hapter 3 Solution Approach 40.1 Solution Approach for the ATSS Model 40.1.1 Lagrangean Relaxation Method 40.1.2 Lagrangean Relaxation 44.1.3 The Dual Problem and the Subgradient Method 49.1.4 Getting Primal Feasible Solutions 50.1.5 Summary of the Solution Approach for the ATSS Model 54.2 Solution Approach for the NPDS Model 56.3 The Independent Model – the DDS Model 61.3.1 Independent Problem Description and Formulation 61.3.2 The Solution Approach for the DDS Model 63hapter 4 Computational Experiments 67.1 Computational Experiments with the ATSS Model 67.1.1 Simple Algorithm 1 67.1.2 Simple Algorithm 2 69.1.3 Experiment Environment 71.1.4 Experiment Results 73.1.5 Discussion of Results 81.2 Computational Experiments with the NPDS Model 84.2.1 Experiment Environment 84.2.2 Experiment Results 86.2.3 Discussion of Results 88.3 Computational Experiments with the DDS Model 89.3.1 Experiment Environment 90.3.2 Experiment Results 91.3.3 Discussion of Results 96hapter 5 Conclusion and Future Work 97.1 Conclusion 97.2 Future Work 99eferences 10