Adviser: Frank,Yeong-Sung Lin Present by Ying-Ju Chen

Presentation on theme: "Adviser: Frank,Yeong-Sung Lin Present by Ying-Ju Chen"— Presentation transcript:

1 Adviser: Frank,Yeong-Sung Lin Present by Ying-Ju Chen
Dynamic Topologies for Robust Scale-Free Networks Shishir Nagaraja and Ross Anderson Adviser: Frank,Yeong-Sung Lin Present by Ying-Ju Chen

2 Agenda Introduction Previous work Naive defenses don’t work
A model of repeated attack and defense Defense evolution – First Round Attack evolution – First Round Defense evolution – Second Round Conclusions and Future Work 1/18/2019

3 Agenda Introduction Previous work Naive defenses don’t work
A model of repeated attack and defense Defense evolution – First Round Attack evolution – First Round Defense evolution – Second Round Conclusions and Future Work 1/18/2019

4 Introduction In recent years, the field of anonymity and traffic analysis have attracted much research interest. However, the analysis of subsequent dynamics of attack and defense has received very little attention. Often an attacker tries to disconnect a network by destroying nodes or edges, while the defender counters using various resilience mechanisms. Albert, Jeong and Barabási famously analyzed the static case, and showed that vertex-order attacks are effective against scale-free networks. 像是攻方透過這樣的流量分析得到拓樸資訊後如何來發動攻擊，以及防方在此network中的如何防禦等，雙方dynamics的分析受到的關注較少 醫生可能會藉由選擇性疫苗接種的方式來阻止傳染病擴大 Vertex order: The number of graph edges meeting at a given node in a graph is called the order of that graph vertex. 1/18/2019

5 Introduction This paper extends this work to the dynamic case by developing a framework to explore the interaction of attack and defense strategies. Naive defenses don’t work against vertex-order attack. Defenses based on simple redundancy don’t work much better, but that defenses based on cliques work well. Attacks based on centrality work better against clique defenses than vertex-order attacks do. Defenses based on complex strategies such as delegation plus clique resist centrality attacks better than simple clique defenses. 這篇paper延伸了之前Albert等學者的研究，從他們的靜態case延伸過來到考慮dynamic case，藉由發展出一個framework來探究攻防策略間的互動，最後提出了以下幾點看法。 1.首先，面對vertex-order attack，naive的防禦是沒用的 2.接著，如果是簡單的redundancy在防禦上來說也不會有多大的效用，但是如果是based on clique的防禦卻是相當有效的 3.而在攻擊方面，如果防方採取的策略是based on clique，那麼此時攻方以centrality的方式攻擊會比vertex-order來得有效 4.最後，在面對centrality的攻擊，最有效的防禦策略是採取delegation加上clique，delegation加上clique的組合策略會比單以clique防禦來得有效。 因此，這篇paper提出的model在network analysis與traffic analysis之間建立了一個橋樑，也provide a framework，針對network中拓樸很重要的部分分析攻防之間的互動情況。 1/18/2019

6 Agenda Introduction Previous work Naive defenses don’t work
A model of repeated attack and defense Defense evolution – First Round Attack evolution – First Round Defense evolution – Second Round Conclusions and Future Work 1/18/2019

7 Agenda Introduction Previous work Naive defenses don’t work
A model of repeated attack and defense Defense evolution – First Round Attack evolution – First Round Defense evolution – Second Round Conclusions and Future Work 1/18/2019

8 Previous work 1959: Erdös and Renyi modeled networks as random graphs.
1967: Milgram- “ small-world” phenomenon. 1998: Watts and Strogatz produced the alpha model. α = 0, each node is connected to its neighbors’ neighbors, so the network is a set of disconnected cliques. α = ∞, represents a random graph. For critical values of α, a small-world network resulted. Then, the beta model. Arranging nodes in a ring β = 0, no links are replaced. β = 1, all links have been replaced, so that the network has again become a random graph 在1959年，Erdos與Renyi學者以random graph來model networks的架構，但是這model並無法模擬real-world的networks。因為在真實的networks中，路徑長度通常會比較短。 到了1967年，Milgram提出了有名的小世界理論，每個人只需要很少的中間人(平均六個)就能和全世界的人建立起聯繫。 而從小世界理論延伸而來的小世界網路model的出現是在1998年，由Watts和Strogatz兩位學者所發展的，一開始是alpha model；因為alpha model太過複雜，因此又有了後來的beta model。 無論是alpha model或是beta model都為觀察到的社會網絡現象或是其它networks提供了一個值得參考的model，連接了local與遠距nodes之間的連結。 1/18/2019

9 Previous work 1999: Barabási and Albert
Preferential attachment: if new nodes in a network prefer to attach to nodes that already have many edges. Leads to a power-law distribution of vertex order which in turn gives rise to a scale-free network. The key paper was written by Albert, Jeong, and Barabási in 2000. The connectivity of scale-free networks depends on the highly-connected nodes, which comes at a price: the destruction of these nodes will disconnect the network. 而到了1999年Barabási與Albert提出了著名的preferential attachment model，說明了為什麼在real-word中會有最短路徑長度的出現。 Preferential attachment說明當一個新的點要加入一個網路時，它會傾向去選擇連接很多edge數的節點，而這樣的特性就產生power-law distribution(冪次定律)的網路結構，構成了這兩位學者提出的無尺度網路。 而這篇paper主要應用的文獻是由Albert, Jeong, and Barabási這三位在2000所提出的研究。他們發現在無尺度網路中，由於特別依賴高度連結的node，因此要是摧毀了這些nodes，就會disconnect整個networks。 1/18/2019

10 Previous work 2002: Holme, Kim, Yoon and Han
Extended this from attacks on vertices to attacks on edges. Suggested using centrality as an alternative to degree for attack targeting. (“Betweenness centrality”, by Freeman.) These ideas find some resonance in the field of strategic studies. 而隨後的研究attacker不是移除best-connected nodes而是移除連結best-connected nodes的edges，也是一樣超過某個門檻值就會瓦解。此外，他們也建議使用centrality，以centrality的高低代表會被攻擊的程度，這裡的centrality指的是由Freeman學者提出的betweenness centrality，betweenness centrality是去量化一個節點出現在所有最短路徑的次數，來看出該節點的degree是高還是低。一個具有高度betweenness centrality的節點有可能是重要的點，因為從一個點到另一點都要經過它作為橋樑。 以上這些文獻探討都在策略研究的領域找到了一些共鳴。 1/18/2019

11 Agenda Introduction Previous work Naive defenses don’t work
A model of repeated attack and defense Defense evolution – First Round Attack evolution – First Round Defense evolution – Second Round Conclusions and Future Work 1/18/2019

12 Agenda Introduction Previous work Naive defenses don’t work
A model of repeated attack and defense Defense evolution – First Round Attack evolution – First Round Defense evolution – Second Round Conclusions and Future Work 1/18/2019

13 Naive defenses don’t work
Replenish destroyed nodes with new nodes, and furnish them with edges according to the same scale-free rule that was used to generate the network initially. Replenish destroyed nodes, but to wire their edges according to a random graph model. Nice as these ideas may seem in theory, they do not work at all well in practice. Figure 1 shows how the vertex-order attack of Albert, Jeong and Barabási works against a simulated network with no replenishment, with random replenishment, and with scalefree replenishment. 有兩種明顯的防禦策略並不work。第一種是以新的節點添補摧毀的節點，並且根據無尺度網路的規則也就是preferential attachment去連結節點間的edge，架構出network的初始狀態。這招若要有用的話，重點在於攻防之間要有均衡存在。 第二種也是添補新的nodes來取代被摧毀的nodes，但是是根據random graph model去連結節點間的edge，此時不同的節點被新加入的節點選上的機率是一樣的。 這兩個理論看起來都不錯，但實際上都不work。圖1紅色的部分代表without replenishment，綠色的部分代表random replenishment，藍色部分代表scalefree replenishment，可以明顯的看出在大約2回合之後，no replenishment的網路架構就瓦解了，而用random replenishment的大約是3回合，而scalefree replenishment大概耗了4回合左右。因此我們還需要更聰明的防禦策略。 Random graph在real-world的application: 有可能是節點學習新行為的結果；或是透過異質連結下的適者生存 1/18/2019

14 Agenda Introduction Previous work Naive defenses don’t work
A model of repeated attack and defense Defense evolution – First Round Attack evolution – First Round Defense evolution – Second Round Conclusions and Future Work 1/18/2019

15 Agenda Introduction Previous work Naive defenses don’t work
A model of repeated attack and defense Defense evolution – First Round Attack evolution – First Round Defense evolution – Second Round Conclusions and Future Work 1/18/2019

16 A model of repeated attack and defense
This paper develops a framework for considering disruptive attacks on networks to be a multiple rounds game. Inspired from evolutionary game theory developed by Axelrod and others. 這邊paper發展出一個framework，主要是考慮多回合的game，而這個想法是來自Axelrod及其他學者之前發展的evolutionary game theory. Evolutionary game theory最常見一般是應用在生物學以及經濟學，在這兩方面的應用上都有很重要的解釋力。 接著我們看一下演化賽局理論的說明 納許均衡: 當參與者間的策略互動狀況達到任一改變策略者自身利益會有損害時，則原狀態謂之納許均衡 每一回合都包含了防禦策略以及攻擊策略 1/18/2019

17 Evolutionary game theory (EGT)
An important feature of the set of models under the umbrella of evolutionary game theory is repetition.  EGT differs from classical game theory by focusing on the dynamics of strategy change more than the properties of strategy equilibria.  If the games were not repeated, EGT model would not be able to provide any insight into adaptive behaviors and strategies due to the dynamic nature of the mechanisms of evolution. A strategy which can survive all "mutant" strategies is considered evolutionary stable. 這個部分算是一個比較粗淺的補充說明。 Evolutionary game theory一個很重要的特性是在此理論底下的set of models都具有重複的特性。 而EGT和典型賽局理論不同的地方是，EGT主要是focus在策略改變的dynamics，而不是主要focus在策略均衡的特性上。 因此如果這場賽局並不是一場repeated game，那麼EGT model就沒有辦法針對adaptive behaviors和strategies提供任何的insight.因為演化(evolution)本身的機制原本就是一個動態的天性。 最後一點是說，如果某個策略它可以survive所有的突變的策略，那麼這樣的狀態就會被認為是一個evolutionary stable的狀態。 在這篇paper的攻防情境中，作者想表達的是不管是攻擊者和防禦者，他們的策略都是會演化的，在面對對方不同的 不管是防禦策略或是攻擊策略也好，去演化找出一個對自己來說最佳的策略。在這部分後面會再做說明。 1/18/2019

18 A model of repeated attack and defense
Formalize a model in which a game is played with a number of rounds. Each round consists of attack followed by recovery. Recovery consists of two phases: replenishment and adaptation. 接著回到paper的說明。我們去formalize一個model，它是一個多回合的game. 1/18/2019

19 A model of repeated attack and defense
In the attack phase Destroys a number of nodes. For example, he might at each round destroy the ten nodes with the largest number of edges connected to them. He selects nodes for destruction on the basis of information about the network topology. In the replenishment phase The defending nodes recruit a number of new nodes, and go through a phase of establishing connections – again, according to given strategies and information. 1/18/2019

20 A model of repeated attack and defense
In the adaptation phase The defending nodes may rewire links within each connected component of the network. Applied once at the start of the game, before the first round of attack. Thereafter the game proceeds attack – replenish – adapt. 1/18/2019

21 A model of repeated attack and defense
Initial assumption: The attacker has perfect information about the network topology, and that his goal is simply to partition the network. The defender has only local information, that it, each node shares the information available to those nodes with which it is connected. The defense strategy affects only the adaptation phase. The attack and defense budgets are roughly equal. For each node destroyed in the attack phase, one node will be replaced in the replenishment phase. attacker有網路拓樸的完整資訊，而且他攻擊的目標只是要partition這個network，將這個network拆成幾個disjoint components。而另一方面，defender假設他只有local information，也就是每個節點只能和與它相連的節點分享資訊。所以如果attacker把network拆成兩個components的話，這兩個components沒有任何方法可以再connect.接著也假設防方策略只會影響到adaptation的階段，replenishment階段是外因的。最後假設attacker與defender的預算是差不多的，每個在attack階段被摧毀的節點，都會在replenishment階段再補回來，所以這個network的大小不會有增減，因此就可以將重心放在connectivity的影響上(high-degree nodes與其他節點的連結)。 1/18/2019

22 Agenda Introduction Previous work Naive defenses don’t work
A model of repeated attack and defense Defense evolution – First Round Attack evolution – First Round Defense evolution – Second Round Conclusions and Future Work 1/18/2019

23 Agenda Introduction Previous work Naive defenses don’t work
A model of repeated attack and defense Defense evolution – First Round Attack evolution – First Round Defense evolution – Second Round Conclusions and Future Work 1/18/2019

24 Defense Evolution - First Round
Consider a static attacker using vertex-order attack. Examine how the defense strategy can adapt, and find the best out. Examine what better attacks can be found against the best defense. Look for a defense against the best attack we found in the last round, and so on. There is no guarantee that the process converges, but if evolutionary games on networks behave like more traditional evolutionary games, we may expect to find some strategies that do well overall. 這裡是在說明整個雙方策略的演化過程…… 如果可以找到一個攻擊策略，這個攻擊策略可以對抗所有的防禦策略，或是某個防禦策略可以對抗所有的攻擊策略，那麼也許就可以找到一個evolutionary stable的狀態 Attacker每回合會選擇一些節點來攻擊，並且希望每一次的攻擊都能夠最大化整個network的damage 以牙還牙（tit for tat）：在一社會困境重複賽局中，以牙還牙策略係指先在第一回合選擇「合作」。但若對手在這一回合選擇「背離」，在下一回合便還以「背離」；相反地，若對手在此一回合選擇「合作」，在下一回合就還以「合作」。 Tit-for-tat strategy的四大特點： 　1.與人為善：先採取合作態度，不在於每一步都把自己的 利益最大化 　2.以牙還牙：如果對方做出損害我方利益的舉措，必須立 即回應，禁止對方變本加厲 　3.不記舊仇：如果對方願意重回合作軌道，則既往不咎， 停止制裁 　4.策略清晰：要讓對手清楚明白自己的決策過程 1/18/2019

25 Defense Evolution - First Round
Defense Strategy 1 – Random Replenishment New nodes are joined to the graph at random. Assume that each attack round removes γ nodes, and the replenishment round adds exactly γ nodes. Each node is joined to the surviving vertices with probability p. γ remains constant for each run of the simulation, while p increases as the replenishment proceeds. In this strategy, the defender does nothing in the adaptation phase. 接著說明在defender面對vertex-order attack所可能採取的三種策略。 首先是naïve defense中的random replenishment，新的節點以random方式加入，假設每次attack都移除了γ個節點，而每次replenishment都會加回γ個節點，每個新節點被連接到存活下來的節點的機率是p，在每回合的模擬中γ都是固定的，但是p會隨replenishment的進行而漸增，在random replenishment的策略中，defender在adaptation階段什麼都沒做，也就是這個策略只是添增新的節點到被破壞的network裡，並沒有去reshape這個network。 1/18/2019

26 Defense Evolution - First Round
Defense Strategy 2 – Dining Steganographers A node that acquires a high vertex order, recruits for the purpose a further n − 1 nodes from the new nodes introduced in the most recent replenishment round, or from among its immediate neighbors, arranged in a ring. Existing ring members cannot be recruited, so rings may not overlap. Finally, recruits to a ring relinquish any existing links with the rest of the network, and the ring-forming node shares its external links uniformly among all the members of the ring. Ring中的新成員會捨棄他們之前已有的external link，而一開始ring-forming的node會uniformly的分配它的external link給這些新成員。 1/18/2019

27 Defense Evolution - First Round
Defense Strategy 2 – Dining Steganographers The rings have two functions. Inspired by Chaum’s “dining cryptographers”. The collaborating nodes in each ring cannot conceal the existence of communication between them, as the cover traffic is visible to the attacker. But from the attacker’s viewpoint it is not obvious that these n nodes are acting as a virtual supernode. Ring的formation有兩種功能。第一個是它提供了resilience，如果這個ring中有個node被摧毀了，那麼其他存活下來的node彼此之間還是可以繼續communicate不會受影響。第二個是，nodes在做route時input link和out put link的traffic是隱藏起來的，會透過一些加密的方式或是其他information hiding的機制來conceal這個traffic。Ring主要有這兩個fuctions. 這個model一開始是inspired byChaum提出的dining cryptographers，所以作者把這個防禦策略稱為dining steganographers，它的conceal是針對insiders，但是這篇paper的conceal是針對outsiders。 對attacker來說他是可以看到node彼此之間communication的存在，不過他看到的是conceal的狀態，就是一個covert traffic，所以雖然這些node是supernode，在他看來也會像是一般的node. 1/18/2019

28 Defense Evolution - First Round
Defense Strategy 3 – Revolutionary Cells A node that acquires a high vertex order splits itself into n nodes, all linked with each other- clique of nodes. Clique-forming node’s external edges are distributed uniformly among members, while other member nodes’ former external edges are deleted. 策略3和策略2一樣，high vertex order node也會去recruit其他node，差別在於這個ring中的node兩兩都會link在一起，形成一個clique， 而也是一樣，clique-forming node的edges會均勻地分配給新成員，並且刪掉新成員之前的external edges. 1/18/2019

29 Defense Evolution - First Round
Simulations – First Set Consider a scale-free network of N = 400 nodes. We use a Barabási-Albert network created by the following algorithm: Growth: Starting with m0 = 40 nodes, at each round we add m = 10 new nodes, each with 3 edges. Preferential Attachment: The probability that a new node connects to node i is Π(ki) = ki/∑j kj where ki is the degree of node i. Having created the scale-free network, then ran each of the above defensive strategies against a vertex-order attack. 接著建立Barabási與Albert的無尺度網路系統 在建立了scale-free network之後，接著針對vertex-order attack測試上述所提到的三種防禦策略，看哪個是比較有效的。 Ki>>連接的edge數 1/18/2019

30 Defense Evolution - First Round
如圖所示，紅色部分代表的是no adaptation，在3回合左右最大的connected component size就從400個節點降到100個節點了，亮綠色部分代表採取策略2，看得出只有帶來短期的效益，從策略1的3回合變成現在的13.14回合左右；但是採取策略3，也就是藍綠色的部分，卻有非常好的效果，雖然在每回合都會有一些節點被disconnected，但是整個network到最後還是connected的，沒有collapse掉。 1/18/2019

31 Agenda Introduction Previous work Naive defenses don’t work
A model of repeated attack and defense Defense evolution – First Round Attack evolution – First Round Defense evolution – Second Round Conclusions and Future Work 1/18/2019

32 Agenda Introduction Previous work Naive defenses don’t work
A model of repeated attack and defense Defense evolution – First Round Attack evolution – First Round Defense evolution – Second Round Conclusions and Future Work 1/18/2019

33 Attack Evolution - First Round
Having tried a number of defence strategies and found that one of them – cliques – is effective Of the attack strategies this paper tries against a clique defense, the best performer is an attack based on centrality. Use the centrality algorithm of Brandes to select the highest-centrality nodes for destruction at each round. As before, our calibration baseline is random replenishment. 在試過上述三種防禦策略後，發現clique是最有效的，接著下一步是找出哪種攻擊策略能夠最有效的對抗clique的防禦；而做出來的結果發現centrality是最好的，paper所使用的centrality演算法是來自Brandes學者的演算法，每回合都會destroy centrality最大的nodes，和之前一樣，我們以random replenishment defense當做calibration baseline. 結果如圖所示，首先比較以rings來防禦vertex order和centrality attack，可以看出在深藍色方框的centrality部分比亮綠色部分的vertex order更快disconnect整個network，但無論面對的攻擊是vertex order還是centrality，ring的防禦都是沒用的。比較有趣是以clique防禦兩種攻擊策略的結果，圖中比較粉紅色和藍綠色的部分，這是之前show過以clique防禦vertex order attack的結果，而粉紅色的部分，當以clique面對centrality攻擊時，可以看出差不多在12.13回合左右network突然被partition，而接下來最大的connected component size都穩定的維持在200左右。 這個結果可以看出若以centrality攻擊clique的防禦是有一定效果的。 1/18/2019

34 Attack Evolution - First Round
For each node, find the length of the shortest path to each other node, and take the inverse. Average this value over all n(n−1)/2 pairs of nodes. 接下來這張圖與上一頁的圖的差異在這張圖是僅針對centrality攻擊做說明，而在Y軸的部分，以average inverse geodesic length為單位，average inverse geodesic length代表的是針對每個節點，找出它到其他節點的最短路徑長度，最後再取此長度的inverse。當network disconnected的時候，這個length就變成無限大，因此取其inverse會是0(所以如果最短路徑很短的話，inverse後的值就會很大)，因此在取完inverse後，再將得到的值除以Cn取2這麼多pairs of nodes得到平均。就是average inverse geodesic length. 在no adaptation的時候，很快就掉下來了，而在defense with rings的時候，它是穩定慢慢的掉下來，這個值跌下來代表的意義是internode communication的困難度增加了；而在clique防禦之下，面對centrality攻擊，可以看到這裡有個驟降，代表有達成一定的partition，而之後是呈現緩慢下降的趨勢。 不一定要講>>所以我們可以知道，雖然centrality是面對clique的最有效攻擊策略，但是它最後還是無法破壞整個network的graph。 1/18/2019

35 Attack Evolution - First Round
How well defense works when using different clique sizes? 接下來這張圖是想要比較在不同的clique size下，防禦效果是否會隨size變大而變得更好。左圖是以clique防禦對抗vertex order attack，右圖是以clique防禦對抗centrality attack。 左圖中我們可以看到以clique防禦vertex order attack時，除了size=5的時候明顯特別差以外，當size漸漸增加之後，其實差異性並不大；而在右圖中，可以看出在14回合左右明顯有一個驟減，但是之後我們可以看到面對centrality attack時defense performance會隨著size的增加而增加，後面最大connected component數的改變都是很穩定的。 1/18/2019

36 Agenda Introduction Previous work Naive defenses don’t work
A model of repeated attack and defense Defense evolution – First Round Attack evolution – First Round Defense evolution – Second Round Conclusions and Future Work 1/18/2019

37 Agenda Introduction Previous work Naive defenses don’t work
A model of repeated attack and defense Defense evolution – First Round Attack evolution – First Round Defense evolution – Second Round Conclusions and Future Work 1/18/2019

38 Defense Evolution - Second Round
Having tried various possible defenses, this paper shows that centrality attacks are powerful. Now, the most promising at present appears to be a compound defense based on cliques and delegation. Delegation: A node that is becoming too well-connected selects one of its neighbors as a “deputy” and connects it to a second neighbor, with which it then disconnects. Delegation on its own is rather slow; it takes dozens of rounds to “immunize” a network against vertex-order attack. Delegation however can play a role, provided they are started from network formation or a reasonable time period before the attack begins. 在剛剛的說明中有提到centrality attack是面對3種不同防禦中較有效的策略，而現在，paper提出一個更好的防禦策略是cliques加上delegation，delegation是在說，一個well-connected node或是說high-degree node去選擇它的鄰居當做代理人或說是副手，接著再連結這個副手節點到well-connected node的另一個鄰居，然後well-connected node會跟這個鄰居斷線，也就是他只要跟副手或是第二鄰居保持任一連結就好了。 如果只做delegation的話是相當慢的，它大概需要花上幾十個回合來免疫整個network抵擋vertex-order的攻擊。 但是如果在network formation的時候或是在攻擊開始前合理的幾回合內(大約是20回合)做delegation的話，對於防禦會有很大的功效 1/18/2019

39 Defense Evolution - Second Round
接下來觀察圖的部分，如果只做delegation，那麼它的效果就和ring的防禦策略差不多，network的崩解仍舊是無法避免，差不多在14回合左右；但有趣的是如果是在架構網路時採取delegation策略，接著再做clique，都在attack前完成的話，就像圖中的箭頭部分，這樣compound的組合策略會比原本只有clique好。 1/18/2019

40 Defense Evolution - Second Round
Delegation postpones and slows down the growth of path length that otherwise results from hub elimination. 而接下來這張圖說明，在被攻擊的狀況下，delegation的策略會使得路徑變得更短，它會postpone跟slow down 路徑的成長，因為原本路徑會變長是因為hub被destroy了，但delegation可以改善這個狀況。透過圖可以看到接下來會維持一個穩定的狀態。 1/18/2019

41 Agenda Introduction Previous work Naive defenses don’t work
A model of repeated attack and defense Defense evolution – First Round Attack evolution – First Round Defense evolution – Second Round Conclusions and Future Work 1/18/2019

42 Agenda Introduction Previous work Naive defenses don’t work
A model of repeated attack and defense Defense evolution – First Round Attack evolution – First Round Defense evolution – Second Round Conclusions and Future Work 1/18/2019

43 Conclusion and Future Work
Moving from a single-shot game to a repeated game provides a useful framework. It enables concepts of evolutionary game theory to be applied to network problems. Simply replacing dead hubs with new recruits does not slow down the attacker much, regardless of whether link replacement follows a random or scale-free pattern. 這篇paper從單回合的game延伸到多回合，並提供有用的架構，將演化賽局理論的概念應用到network上問題 這篇paper也提到naïve defense不會work，如果僅是以新的節點替代被摧毀的hub的話並沒辦法讓attacker的攻擊慢下來，不管是random replenishment或是scale-free replenishment都沒有用。 1/18/2019

44 Conclusion and Future Work
Use the framework to explore two more sophisticated defensive strategies. In one, potentially vulnerable high-order nodes are replaced with rings of nodes; in the other, they are replaced by cliques. The paper found that rings were all but useless, while cliques are remarkably effective. Next, We found that the centrality attack of Holme et al does indeed appear to be more powerful. Then we found that delegation defense combined with cliques work better against centrality attacks. Above all, this work provides a systematic way to evolve and test security concepts relating to the topology of networks. 並且paper也提出兩種防禦策略，一種是ring，另一種是clique，後來發現clique在vertex order的攻擊是很有效的防禦策略；接著又發現Holme等學者提出的centrality攻擊比vertex order攻擊在面對clique防禦時來得有效；最後paper則是提出一個對抗centrality更好的方法是delegation加上clique；整體來說，這個研究提供了一個有系統的方法來發展和測試與網路拓樸有關的security concepts.並且在network analysis與traffic analysis建立了一個橋梁。 1/18/2019

45 Conclusion and Future Work
Further work includes testing: networks that grow or shrink imperfectly informed attackers, such as who must use purely local measures of centrality perfectly informed defenders, who can coordinate connectivity globally budget tradeoffs – for example, a defender might be able to hide specific edges but only at some cost to his replenishment budget different attacker goals 因為這篇是假設network不會有增減，也許可以考慮network會增減的狀況；第二個是考慮imperfect attacker，因為這篇本來假設的是一個global attacker；第三個是考慮perfectly informed defender；第四點是考慮budget tradeoffs，像是假設如果要隱藏一些edge是需要cost的；最後一點是attacker的目標可能不只一種，可能不只是要partition這個network，而且還要讓這些partitions小於一定的size. 1/18/2019

46 Thanks so much for your listening. 
1/18/2019