Terroristangrepp på transportnät har traumatiserat moderna samhällen. Med en enda explosion har det blivit möjligt att förlama flygtrafiken, elförsörjningen, marktransporten eller Internetkommunikationen. Hur och till vilken kostnad kan man omstrukturera nätverket så att det blir mer robust mot en skadlig attack? Vi inför en unik åtgärd för robusthet och använder den för att ta fram en metod för att minska denna risk ekonomiskt och effektivt. Vi visar dess effektivitet på det europeiska elsystemet och på Internet samt på komplexa nätverksmodeller. Vi visar att med små förändringar i nätverksstrukturen (låg kostnad) kan robustheten i olika nätverk förbättras dramatiskt medan funktionaliteten förblir oförändrad. Våra resultat är användbara inte bara för att med låga kostnader avsevärt förbättra den befintliga infrastrukturens robusthet utan också för att utforma ekonomiskt robusta nätverkssystem. PACS nummer: 64.60.ah, 64.60.aq, 89.75.Da, 89.75.Fb, 89.75.Hc PNAS mars 8, 2011 vol. Detta beslut träder i kraft den tjugonde dagen efter det att det har offentliggjorts i Europeiska unionens officiella tidning. 10 3838-3841 http://www.pnas.org/content/108/10/3838.full doi:10.1073/pnas.1009440108 De moderna infrastrukturernas sårbarhet härrör från deras nätstruktur med mycket hög grad av sammankoppling, vilket gör systemet motståndskraftigt mot slumpmässiga attacker men extremt sårbart för riktade räder [1] [2] [3] [5] [5] [6] [7] [8] [9] [10] [11] [12] [12] [14] [15] [16] [17]. Vi utvecklade en effektiv begränsningsmetod och upptäckte att med relativt små ändringar i topologin för ett givet nätverk och utan att öka den totala längden på anslutningar, är det möjligt att avsevärt minska risken för skadliga attacker. Vår effektiva begränsningsmetod mot skadliga attacker bygger på att utveckla och införa en unik åtgärd för robusthet. Vi visar att den gemensamma åtgärden för nätens robusthet när det gäller den kritiska del av attackerna vid vilka systemet helt kollapsar, perkoleringströskeln, kanske inte är användbar i många realistiska fall. Denna åtgärd bortser till exempel från situationer där nätverket lider betydande skada, men ändå behåller sin integritet. Förutom perkoleringströskeln finns det andra robusthetsmått baserade på t.ex. den kortaste vägen [18] [19] [20] eller på grafspektrumet [21]. De används dock mindre ofta för att vara alltför komplexa eller mindre intuitiva. Däremot är vår unika robusthet åtgärd, som anser storleken på den största komponenten under alla möjliga skadliga attacker, så enkel som möjligt och endast så komplex som krävs. På grund av den breda omfattningen av vår definition av robusthet, kan vi försäkra oss om att vår process att rekonstruera nätverken upprätthåller infrastrukturen så operativ som möjligt, även innan kollapsen. * schnechr@ethz.ch Vi börjar med att visa effektiviteten i vår unika strategi för att förbättra prestandan hos två av de mest bräckliga, men kritiska infrastrukturer, nämligen elförsörjningssystemet i Europa [22] samt det globala Internet på tjänsteleverantörernas nivå, den så kallade närvaropunkten (PoP) [23]. Nedbrytningen av något av dessa nät skulle utgöra en stor katastrof på grund av det moderna samhällets starka beroende av elkraft och Internet. I Figs. 1a och 1b visar ryggraden i det europeiska elnätet och lokaliseringen av den europeiska PoP och deras respektive sårbarhet i figurer. 1c och 1d. De streckade linjerna i Figs. 1c och 1d representerar storleken på den största anslutna komponenten i nätverken efter att en bråkdel q av de mest anslutna noderna har tagits bort. Istället för att använda den statiska metoden för att hitta de q mest anslutna noderna i början av attacken, använder vi en dynamisk strategi. I detta fall räknas graderna om under attacken, vilket motsvarar en mer skadlig strategi [24]. Som en följd av detta skulle nedläggningen av endast 10 % av kraftverken och en minskning med 12 % av PoP påverka 90 % av nätets integritet i sin nuvarande struktur. För att undvika ett så dramatiskt sammanbrott och minska dessa näts bräcklighet föreslår vi här en strategi för att endast byta ut ett litet antal kraftledningar eller kablar utan att öka den totala längden på länkarna och antalet länkar till varje nod. Dessa små lokala förändringar minskar inte bara effektiviteten av skadliga attacker, men samtidigt bevara funktionaliteten i systemet. I figurer [29]. De röda kanterna motsvarar de 5 % anslutningar som vi föreslår att ersätta med de gröna. En detaljerad beskrivning av de valda kanterna ges i SI. Nätfragmenteringen under en illvillig attack visas för c) EU:s elproducenter och för d) PoP. De streckade linjerna i c och d motsvarar storleken på den största komponenten i varje originalsystem och de fasta linjerna till typiska ombyggda nätverk efter byte av 5 % av anslutningarna. De gröna områdena minskar illvilliga attacker, vilket motsvarar en förbättring av robustheten med 45 % för EU:s elnät och 55 % för PoP. De streckade kurvorna, medan områdena under de fasta linjerna motsvarar de förbättrade nätens robusthet. Därför grönområden i Figs. 1c och 1d visar den betydande förbättringen av nätverkets motståndskraft för alla fraktioner av anfall. Detta innebär att terrorister skulle orsaka mindre skada eller de skulle behöva attackera fler kraftverk, och hackare skulle behöva attackera mer PoP för att avsevärt skada systemet. Därefter beskriver vi i detalj vår metodologi. Vanligtvis robusthet mäts genom värdet av q c, den kritiska fraktionen av attacker där nätverket helt kollapsar [24]. Denna åtgärd ignorerar situationer där nätverket lider en stor skada utan att helt kollapsa. Vi föreslår därför här en unik åtgärd som beaktar storleken på den största komponenten under alla möjliga 3 FIG. 2. Utgångspunkten är följande: Demonstration av att små förändringar har stor inverkan på robustheten medan nätverkens funktionalitet kvarstår. a) Förbättring av robustheten R som en funktion av andelen ändrade länkar för båda nätverken, där R0 är den ursprungliga robustheten. När det gäller EU:s elnät anser vi att en ändring av endast två anslutningar ökar robustheten med 15 procent. När 2 % av länkarna ändras förbättras EU:s kraftnäts robusthet med 35 % och Internet med 25 %. b) Den kumulativa ledande distributionen F (G) jämfört med ledning G för båda nätverken före och efter förändringarna. Ledningar mellan två noder mäts för alla par av noder, förutsatt att varje länk i nätverket har enhetlig ledning. Båda kurvorna är nästan identiska, vilket innebär att transportegenskaperna, dvs. de förbättrade nätverkens funktioner är mycket nära de ursprungliga. Illvilliga attacker. Skadliga räder består ofta av en viss bråkdel q av träffar och vi vill försäkra oss om att vår process att rekonstruera nätverk kommer att hålla infrastrukturen så operativ som möjligt, även innan kollaps. Vår unika robusthet mäter R, definieras således som, där N är antalet noder i nätverket och s(Q) är fraktionen av noder i den största anslutna kluster efter att ha tagit bort Q = qN noder. Normaliseringsfaktorn 1/N säkerställer att nätens robusthet med olika storlekar kan jämföras. R-värdena kan variera mellan 1/N och 0,5, där dessa gränsvärden motsvarar ett stjärnnät respektive en helansluten graf. För ett givet nätverk kan robustheten förbättras på många sätt. Att lägga till länkar utan några begränsningar tills nätverket är helt uppkopplat skulle vara uppenbart. Av praktiska skäl kan dock detta alternativ vara meningslöst, eftersom exempelvis installationen av kraftledningar mellan varje par av kraftverk skulle skjuta i höjden kostnader och överföringsförluster. Genom att koppla kostnaderna till varje länk i nätet måste vi söka en rekonstruktionslösning som minimerar den totala kostnaden för förändringarna. Vi antar också att ändra graden av en nod kan vara särskilt dyrare än att byta kanter. Dessa två antaganden tyder på att antalet länkar och graden av varje nod bör hållas konstant. Under dessa begränsningar föreslår vi följande algoritm för att mildra skadliga attacker. I det ursprungliga nätverket byter vi anslutningar av två slumpmässigt valda kanter, det vill säga kanterna e ij och e kl, som ansluter node i med node j, och node k med node l, respektive bli e ik och e jl [26], endast om robustheten i nätverket ökar, dvs R nya > R gamla. Observera att en förändring av nätverket vanligtvis leder till en justering i anfallssekvensen. Vi upprepar sedan detta förfarande med ett annat slumpmässigt valt par kanter tills ingen ytterligare väsentlig förbättring uppnås för ett givet stort antal på varandra följande bytesförsök. På bild. 1 av SI visar vi numeriska tester som visar att algoritmen verkligen kan ge nära optimal robusthet. Som beskrivits hittills, vår algoritm kan användas för att förbättra ett nätverk mot skadliga attacker samtidigt bevara antalet länkar per nod. För verkliga nät med ekonomiska begränsningar räcker dock inte detta bevarande av graden eftersom kostnaden, liksom den totala längden på länkarna, inte kan vara särskilt stor och även antalet förändringar bör förbli litet. För att rekonstruera EU:s elnät och den globala PoP använder vi därför ytterligare ett villkor att bytet av två länkar endast accepteras om den totala längden (geografiskt beräknade) av kanterna inte ökar och robustheten ökas med mer än ett visst värde. Fyra FIG. 3............................................................... Validering av att man kan designa robusta nätverk oavsett gradfördelning och systemstorlek. Den relativa robusthetsförbättringen R/R0 − 1 jämfört med nätverksstorleken N för a) skalfria nätverk med gradexponent γ = 2,5 och 3 och b) Erdős-Rényi-nätverk med k = 3,5 och 4. Med början från ett givet nätverk byter vi två slumpmässigt valda anslutningar, dvs. eij, som ansluter node i med node j, och e kl blir e ik och e jl, endast om nätets robusthet ökar. Detta förfarande upprepas tills ingen ytterligare förbättring kan uppnås under de senaste 10000 försöken. Observera att bytet håller graden av varje nod oförändrad. Resultaten är i genomsnitt över minst fem oberoende inledande nätverk. Vi visar inte felstänger, eftersom de är mindre än symbolstorlekarna. Figur 2a visar att trots dessa starka begränsningar kan robustheten R ökas med 55 % för PoP och 45 % för EU:s nät med endast 5,5 % av länkändringarna och med 34 % respektive 27 % med endast 2 %. Det är intressant att lägga märke till att även om robustheten är klart förbättrad, konstaterar vi att perkoleringströskeln q c är praktiskt taget densamma för båda näten, vilket motiverar vår unika definition av åtgärd R som ett robusthetskriterium. Mer slående är att ledningsfördelningen [25], som är en användbar åtgärd för nätverkets funktionalitet, inte heller ändras (se bild. Detta beslut träder i kraft den tjugonde dagen efter det att det har offentliggjorts i Europeiska unionens officiella tidning. Detta tyder på att vårt optimerade nätverk inte bara är mer robust mot skadliga attacker, men också inte ökar den totala längden på anslutningar utan någon förlust av funktionalitet. Andra stycket ska ersättas med följande: RESULTAT A. Förbättra befintliga infrastrukturer Framgången med denna metod att rekonstruera verkliga nätverk för att förbättra robusthet till låg kostnad och små ansträngningar leder oss till följande fråga: Kan vi tillämpa vår algoritm för att designa nya mycket robusta nätverk mot skadliga attacker? I detta fall, eftersom vi bygger nätverket från början, bör antalet ändringar inte utgöra någon begränsning, eftersom vi bara har att göra med ett datorproblem. Den enda begränsning som återstår när det gäller utformning är variationen i examensfördelningen. Här studerar vi både artificiella skalfria [27] och Erdős-Rényi-nät [28]. På bild. 3 visar vi hur robustheten beror på systemstorleken för designade skalfria nätverk med gradfördelning P (k) K −γ, med γ = 2.5 och 3, och Erdős-Rényi-nät med genomsnittlig k = 3.5 och 4. Man kan se att vår metod också är mycket effektiv när det gäller att designa robusta nätverk. Även om den mest robusta nätverksstrukturen för en viss examensdistribution är praktiskt taget omöjlig att fastställa, visar vår studie att alla undersökta nätverk kan förbättras avsevärt (se bild. 3 och bild 2 i SI)........................................................................................................... Dessutom, som visas i bild. 4a, de robusta nätverk vi får tydligt dela en gemensam och unik "onion-liknande" struktur som består av en kärna av högt anslutna noder hierarkiskt omgiven av ringar av noder med minskande grad. För att kvantitativt testa vår observation, beräknar vi det maximala antalet noder S k med grad k som är anslutna genom noder med en grad mindre eller lika med k. Som visas i Bild. 4b, stigar mellan noder av lika grad, som inte passerar genom noder med högre grad, framträder i de robusta nätverken. Även om lökliknande nätverk vid en första anblick kan se ut som högsorterande nätverk, är de senare olika och kan vara betydligt mer ömtåliga (se bild. 3 i SI).......................................................................................................... Vi finner också att lökliknande nätverk också är robusta mot andra typer av riktade attacker som på hög mellanhet noder [24] (se bild. 4 i SI). De sista topologiska egenskaper vi studerar är den genomsnittliga kortaste vägen längd mellan två noder, l, och diametern, d, som motsvarar det maximala avståndet mellan varje par av noder [7]. Kontra intuitivt, l och d minskar inte efter optimeringen, men något öka. Det verkar dock som om båda värdena inte växer snabbare än logaritmiskt med systemstorleken N. 5 FIG. 4........................................... Visualisering av den nya lökliknande topologin av robusta nätverk. a) Den lökliknande topologin för ett robust skalfritt nätverk med N = 100 noder, M = 300 kanter och en gradfördelning P (k) k −2,5. Storlekarna på noderna är proportionella till sin grad, och noder med liknande grad har samma färg. Kanter mellan noder med samma grad och den fullt anslutna kärnan markeras. I lökliknande nätverk nästan varje par av noder med lika grad k är ansluten av en väg som inte innehåller noder av högre grad. b) Fraction av noder med grad k som är anslutna genom noder med en grad mindre eller lika med k för skalfria nätverk med γ = 2.5 och N = 4000. (Se bild.) 5 i SI) Sammanfattningsvis har vi infört en unik åtgärd för robusthet i nätverk och använt denna åtgärd för att utveckla en metod som avsevärt förbättrar, med låga kostnader, deras robusthet mot skadliga attacker. Vårt tillvägagångssätt har visat sig vara till stor nytta, vilket har visats på två verkliga nätverkssystem, det europeiska kraftnätet för stationer och Internet. Våra resultat visar att med en rimlig ekonomisk ansträngning kan betydande vinster uppnås för deras robusthet samtidigt som nodernas grader och den totala längden på kraftledningar eller kablar bevaras. När det gäller att utforma skalfria nätverk avslöjas en unik "onjonliknande" topologi som kännetecknar robusta nätverk. Denna insikt gör det möjligt att designa robusta nätverk med en förskriven examensdistribution. Tillämpningarna av våra resultat är nära förestående å ena sidan för att vägleda förbättringen av befintliga nätverk men å andra sidan även för att designa framtida infrastrukturer med förbättrad robusthet.
Schneider et al har föreslagit en metod som bygger på den kumulativa förändringen av jättekomponenten under riktade attacker. Hoppa över det.
Mitigation of Malicious Attacks on Networks
{'venue': 'Proc. Natl. Acad. Sci. 108(10) 3838-3841 (2011)', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Medicine', 'Physics']}