Przypadkowe uszkodzenia i celowe ataki w sieciach złożonych

Pokażemy teraz, w jaki sposób przypadkowe błędy węzłów i celowe ataki, polegające na przykład na zablokowaniu najlepiej usieciowionych wierzchołków, wpływają na funkcjonowanie sieci złożonych. Omówimy przykłady sieci rzeczywistych, w których takie błędy i ataki miały (bądź mogłyby mieć) miejsce. Zwrócimy uwagę czytelników na to, że złożona struktura układów takich, jak sieci finansowe, dystrybucyjne oraz teleinformatyczne sprawia, że lokalne usterki mogą, wywołując efekt domina, rozprzestrzeniać się na cały system, wywołując poważne reperkusje. W podrozdziale tym pokażemy również, że fizyczna teoria perkolacji pozwala zrozumieć, na czym polega wyjątkowa odporność sieci bezskalowych na przypadkowe błędy. Wyjaśnimy też, dlaczego o takich sieciach mówi się, że są niezwykle wrażliwe na celowe ataki.

Awarie sieci energetycznej

Sieci energetyczne, w których węzłami są stacje transformatorowe, krawędzie zaś reprezentują linie wysokiego napięcia, często ulegają lokalnym usterkom. W większości wypadków lokalne przepięcia powodujące awarie pojedynczych stacji lub linii przesyłowych nie mają jednak większego wpływu na funkcjonowanie całej sieci. Rolę stacji (lub linii), która została uszkodzona na pewien czas przejmuje sąsiednia stacja (odpowiednio równoległa linia) i cały system funkcjonuje poprawnie. Od czasu do czasu w sieci energetycznej zdarzają się jednak i takie awarie, w których pojedyncze przepięcie wywołuje kaskadę kolejnych przepięć i powoduje wyłączenie stacji transformatorowych na dużych obszarach geograficznych, prowadząc do ogromnych strat finansowych.

Szczególnie dobrze udokumentowane są przypadki katastrof energetycznych, do których doszło na terenie Stanów Zjednoczonych. W książce poświęconej sieciom małych światów Duncan Watts opisuje jeden z najlepiej zbadanych kryzysów tego typu – mowa tu o wielkim wyłączeniu stanów Zachodniego Wybrzeża, które miało miejsce 11 sierpnia 1996 roku. Tego dnia w Stanach Zjednoczonych prądu zabrakło na przestrzeni od Oregonu do San Diego w Kalifornii. Warto przytoczyć szczegóły tej katastrofy, choćby dlatego, by uzmysłowić czytelnikowi, że taka historia może się wydarzyć wszędzie, w Warszawie, pod Kielcami, a nawet w Górach Stołowych.

Otóż, awaria, o której mowa zaczęła się od drobnego incydentu. Wysoka temperatura spowodowała, że linia energetyczna nieopodal Portland w Oregonie wydłużyła się nieco ponad miarę i dotknęła korony drzewa, którego w porę nie przycięto. Nastąpiło przepięcie. Incydent został dostrzeżony w najbliższej stacji, ale nikt się specjalnie nie przejął, bo podobne wypadki zdarzają się dosyć często i zazwyczaj nie prowadzą do dramatycznych konsekwencji. Po prostu funkcję linii, która uległa awarii, powinna przejąć linia biegnąca równolegle. I tak się stało, tyle że pracowała już niemal z maksymalną wydajnością i dodatkowe obciążenie przekroczyło jej możliwości. Ruszyła lawina kolejnych przepięć. W ciągu zaledwie kilku minut przeciążone nadmiernym poborem mocy podstacje, linie i elektrownie wyłączyły się. Pojedyncza i zdawałoby się nieznacząca usterka wywołała jeden z największych kryzysów energetycznych minionego stulecia, na kilka dni wstrzymała pracę 175 elektrowni (w tym elektrowni jądrowych) i kosztowała Amerykanów przeszło 2 miliony dolarów.

Cyberterroryzm

Jednym z pierwszych i jak dotąd największym w historii atakiem na infrastrukturę tworzącą Internet był przeprowadzony 22 października 2002 roku, atak typu DDoS³⁰ na trzynaście serwerów obsługujących system domenowy DNS³¹ najwyższego poziomu. Oczywiście wcześniej odnotowano podobne ataki na poszczególne serwery domenowe tworzące szkielet sieci, w tym jednak wypadku zaatakowano wszystkie serwery. Wedle doniesień, pięć z nich przestało funkcjonować. Pozostałe przetrzymały atak, a ich użytkownicy praktycznie nie spostrzegli, że dzieje się coś złego. Gdyby jednak wszystkie serwery przestały działać – wraz z nimi przestałby działać cały Internet.

Innymi przykładami ataków DDoS były ataki wirusa Mydoom: 1 lutego 2004 na serwery firmy SCO³² oraz 3 lutego 2004 na serwery firmy Microsoft. Kolejnym znanym atakiem tego typu był atak na serwery rządowe i komercyjne Estonii w maju 2007 roku. Dziwnym trafem, ten incydent zbiegł się w czasie z eskalacją konfliktu na linii Moskwa–Tallin, którego powodem było usunięcie pomnika żołnierzy radzieckich z centrum stolicy Estonii, prowokując tym samym dyskusję nt. domniemanej koordynacji tego ataku przez rosyjskie służby specjalne. Polskie serwery również kilkakrotnie stały się ofiarą ataków hakerów. Na przykład od 30 listopada do 3 grudnia 2006 odbywał się atak na portal Gazeta.pl. W maju 2007 innym głośnym celem ataków DDoS w naszym kraju stał się serwis policja.pl. Według spekulacji prasowych, ten atak miał być odwetem za policyjny nalot na jeden z serwisów udostępniających napisy do filmów w Internecie.

Wszystkie wymienione przykłady pokazują, jak poważnym problemem staje się obecnie cyberterroryzm³³ . W dzisiejszych czasach, aby zniszczyć strategiczne cele wroga (fabryki i elektrownie, ale też komputerowe bazy danych), nie trzeba mobilizować armii. Zamachowcy nie muszą być obcym supermocarstwem o wielkim potencjale militarnym i gospodarczym. Nie muszą nawet wychodzić z domu. Przykłady pokazują, że jeden człowiek, wyposażony w technologie komputerową i mający odpowiednią wiedzę, może rzucić na kolana całe instytucje, a nawet kraje. Cyberterroryzm jest tani, nie zagraża bezpośrednio sprawcy, a przy tym może mieć katastrofalne skutki. Zakłócając pracę bankowych systemów komputerowych, cyberterrorysta mógłby na przykład spowodować załamanie gospodarki światowej. Wprowadzając natomiast błędne dane do systemów zarządzających infrastrukturą militarną, energetyczną i paliwową mógłby wysadzić w powietrze rurociągi, zburzyć ujęcia wody lub zniszczyć elektrownie jądrowe.

To, że Internet jest wrażliwy na celowe ataki hakerów, nie budzi już chyba żadnych wątpliwości. Otwartym problemem pozostaje jednak to, z czego ta wrażliwość wynika. Okazuje się, że odpowiedź na to pytanie kryje się w pojęciu bezskalowości. Internet, podobnie zresztą jak sieć WWW³⁴ i wiele innych rzeczywistych sieci złożonych, jest siecią bezskalową o potęgowym rozkładzie stopni węzłów. Usunięcie z takiej sieci nawet niewielkiej liczby najlepiej usieciowionych wierzchołków (hubów), będących centrami komunikacyjnymi układu, powoduje najpierw odczuwalne zwiększenie odległości międzywęzłowych, a potem, w miarę wzrostu liczby usuniętych węzłów, rozbicie sieci na wiele rozłącznych klasterów. W sieciach, w których rozkłady stopni wierzchołków nie mają tłustych ogonów, skutki ataków polegających na zablokowaniu wierzchołków o największych stopniach nie są tak bardzo odczuwalne, jak w sieciach bezskalowych. Dzieje się tak, ponieważ w takich sieciach nie ma silnie usieciowionych węzłów.

Z powodu bezskalowości Internet jest nieodporny na celowe ataki hakerów, ale ta sama cecha, tj. bezskalowość, sprawia, że jest również wyjątkowo odporny na przypadkowe usterki (np. awarie pojedynczych komputerów). W pracy opublikowanej w magazynie naukowym „Nature” Albert, Jeong i Barabási pokazali, że sieć bezskalowa praktycznie nie zauważa, że 5% jej losowo wybranych węzłów zostało zablokowanych. W sieci z takimi zablokowanymi węzłami średnia odległość międzywęzłowa niemal wcale się nie zmienia w porównaniu z siecią, w której wszystkie węzły działają poprawnie. Inaczej jest w sieciach, w których średni stopień węzła ma dobrze określoną wartość. W takich sieciach ten sam procent zablokowanych węzłów powoduje o wiele większe zmiany średnich odległości międzywęzłowych, niż w sieciach bezskalowych.

Modelowanie usterek i ataków

Teoretycznym podejściem, które w naturalny sposób pozwala zrozumieć odporność sieci bezskalowych na przypadkowe błędy węzłów i jednoczesną nieodporność na ataki celowe, jest teoria perkolacji³⁵ . Lokalne usterki w sieciach złożonych polegające na:

• usunięciu z sieci pewnej liczby losowo wybranych węzłów lub
• zablokowaniu pewnej liczby najlepiej usieciowionych wierzchołków (hubów)

mogą sprawić, że spójna (tj. sperkolowana) dotychczas sieć rozpadnie się na szereg rozłącznych klasterów (rysunek 4.8), uniemożliwiając swobodny przepływ informacji. Chcąc określić warunki, w jakich dochodzi do takiej drastycznej zmiany funkcjonalności sieci, tzn. do jej rozspójnienia, zbadamy, w jaki sposób każdy z wymienionych procesów, reprezentujących odpowiednio: przypadkowe usterki węzłów (1)) lub celowe ataki na sieć (2)), wpływa na wyrażenie opisujące próg perkolacji w tak zmodyfikowanych sieciach.

Odporność sieci złożonych na przypadkowe błędy węzłów

Nasze rozważania zaczniemy od zbadania odporności sieci na przypadkowe błędy węzłów. Niech zatem q oznacza prawdopodobieństwo, że losowo wybrany wierzchołek badanej sieci ulegnie awarii (zablokowaniu). Oznacza to, że w tym samym czasie w sieci jest średnio qN zablokowanych węzłów. Na skutek lokalnych awarii zmienia się jednak nie tylko rozmiar sieci³⁶

(4.27)

gdzie

(4.28)

Zmianie ulega również rozkład stopni wierzchołków tej sieci

(4.29)

Dzieje się tak, ponieważ część węzłów wraz z dołączonymi do nich krawędziami jest zablokowana, a część węzłów (mowa o tych węzłach, które sąsiadują z uszkodzonymi wierzchołkami) nie może korzystać z zablokowanych połączeń. Efektywny stopień tych węzłów podlega zatem zmianie.

Rozkład stopni węzłów P′(k) w zmodyfikowanej sieci można łatwo wyznaczyć. Jeśli losowo wybrany węzeł pewnej sieci, w której prawdopodobieństwo awarii jest równe q, ma stopień k oznacza to, że w bezawaryjnej sieci, miał on stopień k₀ ≥ k i k₀ − k spośród jego sąsiadów uległo uszkodzeniu. Jeśli awarie poszczególnych sąsiadów tego węzła są od siebie niezależne, wówczas prawdopodobieństwo, że węzeł, który w sieci bez awarii miał stopień równy k₀ w sieci z awariami ma stopień k, jest opisane rozkładem dwumianowym

(4.30)

Zakładając dalej, że awaryjność dowolnego węzła nie zależy od jego stopnia ani od stopni jego sąsiadów możemy napisać, że

(4.31)

gdzie P(k₀) jest rozkładem stopni węzłów w oryginalnej sieci, w której najlepiej usieciowiony węzeł ma k_max najbliższych sąsiadów.

Znając rozkład stopni wierzchołków P′(k), możemy już sprawdzić, w jaki sposób awaryjność pojedynczych węzłów opisana parametrem q wpływa na spójność całej sieci. Aby to zrobić, trzeba wyznaczyć pierwszy<k>′ i drugi <k²>′ moment otrzymanego przed chwilą rozkładu (4.31), skorzystać z wyrażenia

(4.32)

a następnie rozwiązać uzyskaną nierówność z uwagi na prawdopodobieństwo q.

Na początek wyznaczmy wartość średnią rozkładu P′(k):

(4.38)

W podobny sposób można również wyznaczyć drugi moment<k²>′ rozkładu P′(k) stopni węzłów w zmodyfikowanej sieci:

(4.42)

Teraz, dysponując już zależnościami (4.37) oraz (4.41), możemy skorzystać z nierówności (4.32). Wykonując podstawienie otrzymujemy

(4.43)

Następnie, rozwiązując tę nierówność ze względu na parametr q, otrzymujemy warunek na istnienie klastera perkolacyjnego w sieci z przypadkowymi błędami

(4.44)

gdzie

(4.45)

jest ilorazem drugiego i pierwszego momentu w sieci bezawaryjnej³⁷ . Z tego warunku wnioskujemy, że jeśli awaryjność sieci przekracza pewną progową (krytyczną) wartość,

(4.46)

wówczas badana sieć przestaje być sperkolowana i rozpada się na wiele niepołączonych ze sobą podsieci. Zauważmy tylko, że ta progowa wartość prawdopodobieństwa q przez parametr κ₀ (4.45) zależy od rozkładu P(k) stopni węzłów w oryginalne sieci bez usterek (zob. rysunek 4.9).

Z wykonanych obliczeń wynika na przykład, że gdybyśmy chcieli rozspójnić klasyczny graf przypadkowy o <k> > 1, wówczas musielibyśmy uszkodzić Nq_c^ER jego losowo wybranych węzłów, gdzie³⁸

(4.47)

Oznacza to, że aby dokonać takiego rozspójnienia w grafach ER o<k> = 2, dla których κ₀ = 1/2 = 50%, musielibyśmy zablokować przynajmniej połowę węzłów. Zwróćmy jeszcze uwagę na to, że mówiąc o rozspójnieniu sieci, mamy na myśli całkowite zniszczenie jego klastera perkolacyjnego. W pewnych wypadkach może nas jednak interesować jedynie znaczące zmniejszenie wielkości tego klastera. Awaryjność węzłów opisująca taką sytuację jest oczywiście mniejsza od q_c.

Wykonanie podobnych obliczeń dla sieci bezskalowych, o potęgowym rozkładzie stopni węzłów, również nie jest trudne. Parametr κ₀ (4.45) dla takich sieci wyznaczyliśmy w podrozdziale poświęconym perkolacyjnej przemianie fazowej w modelu konfiguracyjnym. Dla Internetu zbudowanego z N = 10⁴ ruterów, przy założeniu, że wykładnik charakterystyczny rozkładu stopni węzłów jest równy α = 2,5 (stan z 1998 roku), parametr ten jest równy³⁹ κ₀ = 10². Wynika stąd, że krytyczna wartość prawdopodobieństwa usterki losowo wybranego rutera (4.46), powyżej której Internet traci spójność, jest w przybliżeniu równa

(4.48)

Oznacza to, że gdybyśmy chcieli zniszczyć strukturę Internetu, w sposób losowy wyłączając kolejne jego węzły, nie zwracając przy tym uwagi na ich usieciowienie, musielibyśmy zablokować niemal wszystkie rutery. Stałoby się tak, ponieważ w sieci bezskalowej prawdopodobieństwo wylosowania i zablokowania huba jest bardzo małe (taką sytuację doskonale ilustruje rysunek 4.8). Z tego właśnie powodu o Internecie i innych sieciach bezskalowych, w których rozkład stopni węzłów jest potęgowy z wykładnikiem charakterystycznym α < 3, mówi się, że są one bardzo odporne na przypadkowe błędy węzłów.

Atak na sieć – rola najlepiej usieciowionych węzłów

Już wcześniej pokazaliśmy (rysunek 4.8), że atak na sieć można rozumieć jako zablokowanie węzłów mających największe stopnie. W klasycznych grafach przypadkowych, w których rozkład stopni wierzchołków P(k) jest rozkładem Poissona, stopnie najlepiej usieciowionych węzłów niewiele się różnią od stopni pozostałych wierzchołków. W takich układach, atak na sieć ma podobny efekt jak blokada losowo wybranych węzłów. Inaczej jest w sieciach bezskalowych, w których rozkład stopni jest potęgowy P(k) ∝ k^−α z wykładnikiem charakterystycznym α < 3. Cechą charakterystyczną układów, które są opisane takimi rozkładami jest to, że mogą się w nich pojawiać zdarzenia ekstremalne. W sieciach bezskalowych, zdarzeniom tym odpowiada pojawienie się silnie usieciowionych węzłów (hubów), których stopień zależy od parametru α i od rozmiaru sieci N, jak

(4.49)

gdzie m jest najmniejszym stopniem węzła w rozważanej sieci. W takich sieciach zablokowanie huba jest równoznaczne z zablokowaniem ogromnej liczby dołączonych do niego krawędzi. Odpowiemy zatem na pytanie: ile hubów należy usunąć z sieci, by ją rozspójnić, tzn. by zniszczyć jej klaster perkolacyjny.

Niech zatem pN oznacza liczbę najlepiej usieciowionych węzłów sieci przypadkowej o rozkładzie stopni P(k), które zamierzamy zablokować. W wyniku zablokowania tych węzłów zmieni się nie tylko rozmiar badanej sieci, tj.

(4.50)

gdzie

(4.51)

ale przede wszystkim zmieni się jej rozkład stopni wierzchołków

(4.52)

W sieciach bezskalowych, bo głównie takie nas w tej chwili interesują, usunięcie najlepiej usieciowionych węzłów w dwojaki sposób wpływa na oryginalny rozkład P(k) (4.52). Po pierwsze, zmienia się stopień najlepiej usieciowionego węzła, tzn. parametr obcięcia rozkładu P(k),

(4.53)

a po drugie, w wyniku blokady części połączeń (tych, których drugim końcem jest zaatakowany węzeł), zmieniają się również stopnie pozostałych, słabiej usieciowionych wierzchołków.

Na początek wyznaczymy nową wartość parametru obcięcia k_max′. Znajdźmy dolne oszacowanie największego zdarzenia (4.53) w zbiorze zmiennych losowych z rozkładu potęgowego

(4.54)

Wartość k_max (4.49), o której mowa, wyznaczymy, rozwiązując poniższe równanie

(4.55)

mówiące, że w sieci bezskalowej o potęgowym rozkładzie stopni węzłów (4.54) istnieje przynajmniej jeden węzeł o stopniu większym od k_max. W podobny sposób, korzystając z równania (4.55), można znaleźć nowy parametr obcięcia k_max'

(4.56)

Rozwiązując to równanie, dla zadanej wartości p otrzymujemy

(4.57)

Wyjaśnijmy jeszcze, że k_max′ oznacza oryginalny, tj. jeszcze przed uwzględnieniem zablokowanych krawędzi, stopień najlepiej usieciowionego węzła w sieci po ataku.

Znając k_max′, możemy już znaleźć prawdopodobieństwo, że losowo wybrana krawędź oryginalnej sieci zostanie podczas ataku zablokowana. Prawdopodobieństwo to jest równe prawdopodobieństwu, że taka krawędź należy do jednego z zaatakowanych węzłów, tj.

(4.58)

gdzie rozkład

(4.59)

opisuje prawdopodobieństwo, że losowo wybrane połączenie sieci bezskalowej należy do węzła, którego stopień jest równy k.

Znajomość nowego parametru obcięcia k_max′ (4.57) rozkładu P(k) (4.54) oraz prawdopodobieństwa q (4.58), że węzeł na końcu losowo wybranej krawędzi został zablokowany, pozwala nam sprowadzić zagadnienie ataku na sieć do omówionego wcześniej zagadnienia przypadkowych awarii w sieci. Otóż korzystając z warunku (4.46) i podstawiając do niego wyrażenie (4.58) otrzymujemy zależność mówiącą o tym, jaką część p najlepiej usieciowionych węzłów sieci bezskalowej należy usunąć, aby zniszczyć jej największy spójny komponent. Krytyczna wartość tego parametru jest równa

(4.60)

gdzie κ₀ est ilorazem drugiego i pierwszego momentu potęgowego rozkładu stopni węzłów z uwzględnieniem nowego parametru obcięcia k_max′, tj.

(4.61)

Ponieważ parametr κ₀ przez wielkość k_max′ również zależy od p_c, krytyczny ułamek najlepiej usieciowionych węzłów, których blokada powoduje rozspójnienie sieci bezskalowych, można jedynie wyznaczyć numerycznie rozwiązując równanie (4.60). Rozwiązanie tego równania dla różnych wartości wykładnika charakterystycznego α ∈ (2,4) pokazano na rysunku 4.10. Z tego rysunku wynika na przykład, że chcąc zniszczyć klater perkolacyjny sieci bezskalowej o wykładniku α = 2,5 (taka wartość wykładnika α została zmierzona w Internecie), wystarczy usunąć zaledwie 6% najlepiej usieciowionych węzłów. Przypomnijmy, że blokując węzły sieci bezskalowych w sposób zupełnie losowy, tj. bez zwracania uwagi na ich usieciowienie, musielibyśmy usunąć niemal wszystkie wierzchołki (4.48). Z tego powodu o sieciach bezskalowych mówi się, że są bardzo wrażliwe na celowe ataki.