林永松臺灣大學：資訊管理學研究所陳怡孜Chen, Yi-TzuYi-TzuChen2007-11-262018-06-292007-11-262018-06-292007http://ntur.lib.ntu.edu.tw//handle/246246/54332在九零年代開始，網際網路逐漸演變成全球共通的溝通媒介，許多恐怖份子開始利用其攻擊政府及國家，此一行為嚴重危害國家安全。是故，資訊安全逐漸演變成重要的議題。因此對網路營運者而言，如何有效評估網路攻擊者的威脅，達到提升網路存活度的問題已愈趨重要。 因此，本研究利用數學規劃及圖形理論為工具，建構網路攻防情境的資源分配問題，分別提出AEA(Accumulated Experiences of Attacker)與AAEA(Advanced Accumulated Experiences of Attacker)。於AEA模型中，先轉化存在旅行推銷員問題中，於不同城鎮間購買折扣券以降低旅行成本的概念，茲代表網路在攻擊者利用自身經驗及攻克節點成功時所獲得的經驗，以影響未來攻擊成本之情境，即：所有節點一經攻克後，所獲得之經驗將有效地降低後續發生的攻擊成本，並考慮攻擊者以一節點為入口進入目標網路之後，在經驗值影響下尋求一條最短路徑，俾便攻克網路中的一個目標節點，使目標網路無法存活，且利用圖形理論將問題轉化，運用一般化最短路徑演算法求解之；在AAEA模型中，考慮相同的攻擊者問題下，更考量攻擊者可在節點上花費不同等級之額外成本，以獲取對攻擊其餘網路節點不同等級的資訊(如：使用者權限或是網路拓撲圖…等)，達到有效地降低後續攻擊成本，由於此問題藉由圖形理論的轉化，也將AAEA模型利用一般化最短路徑演算法求解之。Internet has become worldwide, publicly accessible network of interconnected computer networks since 1980s. Specifically, it becomes the tools that terrorists can use to attack the nations and their economy. Thus, any network operator could improve the network’s survivability by effectively evaluating the attacker behavior. As a result, this thesis focuses on the resource allocation of network attack and defense with mathematical programming and graph modeling to optimize the problems, and adopts a concept, discount coupon which is applied in TSP, to represent the attacker behavior of taking advantage of accumulated experiences from his previous attack actions of minimizing the total attack cost. In AEA, the attacker somehow gains some free experiences from a compromised node which could further reduce the cost of an attack. The attacker’s objective is to minimize the total attack cost, while the core node is compromised and the network could not survive. Here, by transforming AEA with node splitting into a generalized shortest path problem and applying the algorithm to optimally solve it. In AAEA, the attacker not only gains some free experiences from a compromised node but could spend different levels of extra expenses, probing fee, gaining different levels of valuable experiences, such as diverse user’s rights or a network topology. Therefore, AAEA is proposed to describe such behavior which is also analyzed as a mixed nonlinear integer programming optimization problem. With node splitting technique, AAEA is transformed into a shortest path problem and is optimally solved by generalized shortest path algorithm.論文口試委員審定書 I 謝誌 II 論文摘要 III THESIS ABSTRACT IV Table of Contents VI List of Figures VIII Chapter 1 Introduction 1 1.1 Background 1 1.2 Motivation 3 1.3 Literature Review 6 1.3.1 Survivability of Quantitative Analysis with Attacker Behavior 6 1.3.2 Traveling Salesman Problem 9 1.4 Proposed Approach 11 1.5 Thesis Organization 12 Chapter 2 Graph Modeling of AEA and AAEA Models 13 2.1 Problem Description and Graph Modeling of AEA 13 2.1.2 Graph Modeling of AEA 14 2.2 Problem Description and Graph Modeling of AAEA 18 2.2.1 Problem Description of AAEA 18 2.2.2 Graph Modeling of AAEA 18 Chapter 3 Problem Formulation 21 3.1 Problem Formulation of AEA 21 3.1.1 Problem Assumptions 21 3.1.2 Notation and Formulation 23 3.2 Problem Formulation of AAEA 26 3.2.1 Problem Assumptions 26 3.2.2 Notation 27 Chapter 4 Solution Approach 30 4.1 Generalized Shortest Path Problem 31 4.2 Solution Approach to AEA 32 4.3 Solution Approach to AAEA 33 Chapter 5 Conclusion and Future Work 34 5.1 Conclusion 34 5.2 Future Work 35 Reference 42 簡歷 46590421 bytesapplication/pdfen-US資訊安全網路攻防存活度資源分配旅行推銷員問題經驗折扣圖形理論節點分裂法一般化最短路徑最佳化Internet SecurityNetwork Attack and DefenseSurvivabilityResource AllocationTraveling Salesman problem (TSP)Discount CouponGraph ModelingNode SplittingGeneralized Shortest Path ProblemOptimization[SDGs]SDG16otherhttp://ntur.lib.ntu.edu.tw/bitstream/246246/54332/1/ntu-96-R94725054-1.pdf