臺灣博碩士論文加值系統

資訊系統與網際網路的興盛，促使多數企業應用資訊技術來獲得競爭優勢，而各企業皆有機密的營運資料，利用電子數位化的方式儲存。但是核心營運的方針若被對手得知，將使企業失去競爭力與形象受損。因此，個人或是企業需要降低機密資訊遺漏的風險，也需考量確保機密資訊的可用性，是否能讓合法使用者在有效時間內使用機密資訊。面對日益攀升的資料竊取行為所帶來嚴重損失，發展有效的防禦策略是當務之急的議題。

本論文中提出整合網路規劃的資訊安全管理問題，將攻防情境轉化成最小-最大化的雙層數學模型問題。在內層問題中，攻擊者必須利用有限的資源來進行資料竊取動作並造成最大化傷害，包含竊取機密資訊拼圖與相對應解密鑰匙才能構成資訊遺漏的傷害。而在外層問題中，網路管理者妥善分配其預算資源，以網路規劃觀點建置拓墣，在縱深防禦概念下設計出高度強韌的網路，配合秘密分享機制與防禦資源部署達到資訊隱密性與可用度，使攻擊行為不同傳統方式，如攻克節點就可造成傷害，試圖最小化資訊遺漏的傷害損失。除此之外，因考量真實網路環境會發生的傳輸連結故障，需在網路規劃時確保整體網路傳輸的可靠度以及滿足使用者服務品質要求。針對此雙層數學問題，我們提出拉格蘭日鬆弛法及次梯度法為基礎的演算法來解決問題。另外，我們針對初始部署問題建置一個獨立單層數學模型，定義機密資訊離散指標來衡量攻擊者的影響，利用模擬退火法基礎的演算法進行處理，並利用電腦實驗來評估這些演算法的效率與效果。

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.
In 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.
On 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.
The 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.

論文摘要 V
THESIS ABSTRACT VI
Table of Contents VIII
List of Tables X
List of Figures XI
Chapter 1 Introduction 1
1.1 Background 1
1.2 Motivation 6
1.3 Literature Survey 8
1.3.1 Secret Sharing Scheme 8
1.3.2 QoS Routing 12
1.3.3 Survivability 16
1.4 Proposed Approach 18
1.5 Thesis Organization 19
Chapter 2 Problem Formulation 20
2.1 Problem Description 20
2.2 Problem Formulation of the NPDS Model 23
2.3 Problem Formulation of the ATSS Model 37
Chapter 3 Solution Approach 40
3.1 Solution Approach for the ATSS Model 40
3.1.1 Lagrangean Relaxation Method 40
3.1.2 Lagrangean Relaxation 44
3.1.3 The Dual Problem and the Subgradient Method 49
3.1.4 Getting Primal Feasible Solutions 50
3.1.5 Summary of the Solution Approach for the ATSS Model 54
3.2 Solution Approach for the NPDS Model 56
3.3 The Independent Model – the DDS Model 61
3.3.1 Independent Problem Description and Formulation 61
3.3.2 The Solution Approach for the DDS Model 63
Chapter 4 Computational Experiments 67
4.1 Computational Experiments with the ATSS Model 67
4.1.1 Simple Algorithm 1 67
4.1.2 Simple Algorithm 2 69
4.1.3 Experiment Environment 71
4.1.4 Experiment Results 73
4.1.5 Discussion of Results 81
4.2 Computational Experiments with the NPDS Model 84
4.2.1 Experiment Environment 84
4.2.2 Experiment Results 86
4.2.3 Discussion of Results 88
4.3 Computational Experiments with the DDS Model 89
4.3.1 Experiment Environment 90
4.3.2 Experiment Results 91
4.3.3 Discussion of Results 96
Chapter 5 Conclusion and Future Work 97
5.1 Conclusion 97
5.2 Future Work 99
References 102

[1] D.A. Grier, “The Innovation Curve,” IEEE Computer Society, Vol. 39, pp. 8-10, February 2006.
[2] A. Azadmanesh, A.W. Krings, and P.W. Oman, “Security and Survivability of Networked Systems,” Proceedings of the 38th IEEE Hawaii International Conference on System Sciences, 2005.
[3] R. Richardson, “2008 CSI Computer Crime and Security Survey,” Computer Security Institute, 2008, http://www.gocsi.com/.
[4] M. Al-Kuwaiti, N. Kyriakopoulos, and S. Hussein, “Network Dependability, Fault-tolerance, Reliability, Security, Survivability: A Framework for Comparative Analysis,” The George Washington University, November 2006.
[5] G.R. Ganger, H. Kılıççöte, J.D. Strunk, J.J. Wylie, M.W. Bigrigg, and P.K. Khosla, “Survivable Information Storage Systems,” Garnegie Mellon University, August 2000.
[6] “Information Security in Taiwan,” http://www.informationsecurity.com.tw.
[7] G. Levitin, “Optimal Defense Strategy against Intentional Attacks,” IEEE Transactions on Reliability, Vol. 56, No. 1, March 2007.
[8] A. Shamir, “How to Share a Secret,” Massachusetts Institute of Technology, 1979.
[9] M. Tompa, “How to Share a Secret with Cheaters,” International Association for Cryptologic Research, 1988.
[10] A. Herzberg, H. Krawczyk, M. Yung, and S. Jarecki, “Proactive Secret Sharing or How to Cope with Perpetual Leakage,” IBM T.J. Watson Research Center, 1995.
[11] A. Subbiah and D.M. Blough, “An Approach for Fault Tolerant and Secure Data Storage in Collaborative Work Environments,” School of Electrical and Computer Engineering Georgia Institute of Technology, April 2005.
[12] B. Wang and J.C. Hou, “Multicast Routing and Its QoS Extension: Problems, Algorithms, and Protocols,” The Ohio State University.
[13] J. Crowcroft and Z. Wang, “Quality of Service Routing for Supporting Multimedia Applications,” IEEE Journal on Selected Areas in Communications, September 1996.
[14] K. Nahrstedt and S. Chen, “An Overview of Quality-of-Service Routing for the Next Generation High-Speed Network: Problems and Solutions,” IEEE Network, December 1998.
[15] G. Karlsson and I. Mas, “Quality of Service and the End to End Argument,” IEEE Network, November 1997.
[16] D.A. Fisher and H.F. Lipson, “Survivability - A New Technical and Business Perspective on Security,” Coordination Center Software Engineering Institute, 2000.
[17] D.A. Fisher, H.F. Lipson, N.R. Mead, R.C. Linger, R.J. Ellison, and T.A. Longstaff, “Survivable Network Systems: An Emerging Discipline,” Technical Report CMU/SEI-97-TR-013, Software Engineering Institute, Carnegie Mellon University, pp. 1-31, November 1997 (Revised 1999).
[18] A. Krings, “Design for Survivability: A Tradeoff Space,” ACM International Conference Proceeding Series, Vol. 288, 2008.
[19] J.L. Tzeng, “Near Optimal Network Defense Resource Allocation Strategies for the Minimization of Information Leakage,” Department of Information Management, National Taiwan University, 2006.
[20] M.N. Azaiez and V.M. Bier, “Optimal Resource Allocation for Security in Reliability Systems,” European Journal of Operational Research, Vol. 181, No. 2, pp. 773-786, September 2007.
[21] A.M. Geoffrion, “Lagrangean Relaxation and Its Use in Integer Programming,” Mathematical Programming Study, Vol. 2, pp. 82-114, 1974.
[22] M.L. Fisher, “The Lagrangian Relaxation Method for Solving Integer Programming Problems,” Management Science, Vol. 27, No. 1, pp. 1-18, January 1981.
[23] M.L. Fisher, “An Application Oriented Guide to Lagrangean Relaxation,” Interfaces, Vol. 15, No. 2, pp. 10-21, April 1985.
[24] C.D. Gelatt, M.P. Vecchi, and S. Kirkpatrick, “Optimization by Simulated Annealing,” Science, Vol. 220, No. 4598, pp. 671-680, May 1983.