臺灣博碩士論文加值系統

　　沒有一套資訊系統是完全安全的。有經驗的攻擊者能夠在各式各樣的攻擊方式中選擇一個最適當的，包括利用員工的濫用、系統的弱點、字典攻擊，甚至是暴力攻擊來侵入並毀壞系統。因此對於網路管理者而言，擬定有效的防禦策略使得網路中重要的系統或主機在遭受攻擊時能夠將存活時間拉長，藉此讓管理者有更長的時間來回應惡意的網路攻擊。
　　在這篇論文中，我們考慮在智慧型與惡意型攻擊下目標節點存活時間最大化的問題，而攻擊者攻克網路中節點的時間是該節點分配到的防禦資源之函數。這個問題可以被表示為一個最小最大化的雙層整數規劃問題，其中，內層的最大化問題表示攻擊者在固定的時間與防禦資源配置策略下，決定到達目標節點最佳的攻擊路徑以達到最大的成功機率；外層的最小化問題表示網路管理者藉由調整防禦資源配置策略使得攻擊者成功的機率最小化。我們也將問題加以延伸，考慮攻擊者從攻擊的過程中獲得經驗累積所造成的影響。我們假設每攻克一個節點就會獲得一個折扣係數，而這個係數會影響之後攻擊者攻克網路中節點的時間與防禦資源之函數。此論文利用拉格蘭日鬆弛法與次梯度法這兩種基本方式來發展演算法，並利用電腦實驗來衡量這個演算法的效率與效果。

No information system in a network is absolutely secure. Sophisticated attackers may adopt various types of hacking techniques, such as staff abuses, system vulnerabilities, dictionary attacks, or brute force attacks, to penetrate and damage the system. Therefore, it is essential that effective defense strategies be devised by network administrators to maximize the survival time of critical/core components in networks upon attacks so as to achieve the longest response time.
In this thesis, the problem of maximization of the core node survival time upon intelligent and malicious attacks is considered. The time for an attacker to compromise a node in the network is considered as a random variable, of which the associated CDF is assumed to be a function of the allocated defense resource. The problem is formulated as a mini-max integer programming problem, where the inner (maximization) problem is for the attacker to determine an optimal attack path to the core node so as to maximize his/her success probability under a given time constraint and a given defense resource allocation policy, while the outer (minimization) problem is for the network administrator to adjust his/her defense resource allocation policies so as to minimize the success probability of the attacker. The basic approach to the algorithm development is Lagrangean relaxation and the subgradient method. The efficiency and effectiveness of the proposed algorithms will be evaluated by computational experiments.

謝　詞 I
論文摘要 III
Table of Contents VII
List of Figures XI
Chapter 1 Introduction 1
1.1 Background 1
1.2 Motivation 4
1.3 Literature Survey 6
1.3.1 Survival Time 6
1.3.2 Offense and Defense Strategies 7
1.4 Proposed Approach 10
1.5 Thesis Organization 11
Chapter 2 Problem Formulation 13
2.1 Problem Description and Assumption 13
2.2 Notations 18
2.3 Problem Formulation 22
2.4 Problem Reformulation 25
Chapter 3 Solution Approach 29
3.1 Lagrangean Relaxation Method 29
3.2 Solution Approach 33
3.3 Lagrangean Relaxation 33
3.4 The Dual Problem and the Subgradient Method 39
3.5 Getting Primal Feasible Solution 40
Chapter 4 Computational Experiments 43
4.1 Simple Algorithms 43
4.2 Experiment Environment 44
4.3 Experiment Results 46
4.4 Discussion of Results 57
Chapter 5 Conclusion and Future Work 59
5.1 Conclusion 59
5.2 Future Work 60
Reference 63

[1] Lawrence A. Gordon, Martin P. Loeb, William Lucyshyn, and Robert Richardson, “CSI/FBI Computer Crime and Security Survey,”　2006
[2] Alex Shipp, “Targeted Trojan Attacks and Industrial Espionage ,” Virus Bulletin Conference, 2006
[3] Yi-Luen Lin, “Near Optimal Protection Strategies against Targeted Attacks on the Core Node of a Network”
[4] Partha Pal, Franklin Webber, and Richard Schaniz, “Survival by Defense-Enable,” OASIS, 2003
[5] SANS-ISC (SysAdmin, Audit, Network, Security Institute - Internet Storm Center), http://isc.sans.org/survivalhistory.php
[6] Matt Loney and Robert Lemos, “Study: Unpatched PCs compromised in 20 minutes,” CNET News.com, Aug. 2004
[7] Zeid Nasser, “‘Survival Time’ must be increased!” http://zeidnasser.blogspot.com, Jun. 2005
[8] Fred Cohen, “Managing Network Security - Attack and Defense Strategies,” Network Security, Jul. 1999
[9] Kong-wei Lye, and Jeannette M. Wing, “Game strategies in network security,” International Journal of Information Security , Vol. 4, No. 1-2, pp. 71-86, Feb. 2005
[10] Milton Abramowitz., and Irene A. Stegun, “Normal or Gaussian Probability Function,” Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, p.931, 1964
[11] Malware-Test Lab, http://www.malware-test.com/
[12] Bracewell, R. "Convolution" and "Two-Dimensional Convolution," The Fourier Transform and Its Applications, 3rd Ed, pp. 25-50 and 243-244, New York: McGraw-Hill, 1999
[13] Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin, “Lagrangian Relaxation and Network Optimization,”Network Flows: Theory, Algorithm, and Application, pp. 598-639, Prentice Hall, Inc., Jan. 1993
[14] Marshall L. Fisher, “The Lagrangian Relaxation Method for Solving Integer Programming Problems,” Management Science, Vol. 27, No. 1, pp. 1-18, Jan. 1981
[15] Marshall L. Fisher, “An Application Oriented Guide to Lagrangian Relaxation,” Interfaces, Vol. 15, No. 2, pp. 10-21, Apr. 1985
[16] Wasel Chemij, “Parallel Computer Taxonomy,” MPhil, Aberystwyth University, 1994
[17] Albert-Laszlo Barabasi, and Reka Albert, “Emergence of Scaling in Random Networks,” Science, Vol. 286, pp. 509-512, Oct. 1999