Biztonsági célú átfedő hálózat

Budapesti Műszaki és Gazdaságtudományi Egyetem Villamosmérnöki és Informatikai Kar

Biztonsági célú átfedő hálózat Doktori értekezés

Szerző: Czirkos Zoltán okleveles villamosmérnök Témavezető: Dr. Hosszú Gábor egyetemi docens műszaki tudomány kandidátusa

Elektronikus Eszközök Tanszéke Budapest, 2011.

Nyilatkozat önálló munkáról, hivatkozások átvételéről Alulírott Czirkos Zoltán kijelentem, hogy ezt a doktori értekezést magam készítettem és abban csak a megadott forrásokat használtam fel. Minden olyan részt, amelyet szó szerint, vagy azonos tartalomban, de átfogalmazva más forrásból átvettem, egyértelműen, a forrás megadásával megjelöltem.

Budapest, 2011. október 20.

Nyilatkozat nyilvánosságra hozatalról Alulírott Czirkos Zoltán hozzájárulok a doktori értekezésem Interneten történő nyilvánosságra hozatalához az alábbi formában: – korlátozás nélkül – elérhetőség csak magyarországi címről – elérhetőség a fokozat odaítélését követően 2 év múlva, korlátozás nélkül – elérhetőség a fokozat odaítélését követően 2 év múlva, csak magyarországi címről

Budapest, 2011. október 20.

Tartalomjegyzék 1. Bevezetés

3

2. Irodalmi összefoglaló 2.1. A P2P hálózatok . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1. A P2P hálózatok felépítése . . . . . . . . . . . . . . . 2.1.2. Elosztott hash táblázatok . . . . . . . . . . . . . . . . 2.2. A Kademlia átfedő felépítése . . . . . . . . . . . . . . . . . . 2.2.1. A Kademlia átfedő üzenetei . . . . . . . . . . . . . . 2.2.2. A Kademlia átfedő megbízhatatlansága . . . . . . . 2.2.3. Replikáció a Kademlia átfedőben . . . . . . . . . . . 2.3. Üzenetszórás P2P átfedőkben . . . . . . . . . . . . . . . . . 2.4. P2P átfedők szimulációja . . . . . . . . . . . . . . . . . . . . 2.5. Betörésérzékelő rendszerek . . . . . . . . . . . . . . . . . . . 2.5.1. A betörésérzékelés célja . . . . . . . . . . . . . . . . 2.5.2. A betörések jellemzői . . . . . . . . . . . . . . . . . . 2.5.3. A betörésérzékelés lehetőségei . . . . . . . . . . . . . 2.5.4. A betörésérzékelés helye . . . . . . . . . . . . . . . . 2.5.5. Az érzékelt események közötti kapcsolat felismerése 2.5.6. A betörésérzékelők közötti kommunikáció . . . . . .

. . . . . . . . . . . . . . . .

5 5 6 6 9 11 11 14 14 15 18 18 19 20 21 21 22

. . . . . . . . .

25 26 28 29 31 33 34 35 36 37

4. A Kademlia átfedő megbízhatóságának növelése 4.1. A megbízhatóság növelése a replikáció alkalmazásával . . . . . . . . . . . . . . 4.2. Modellezési eljárások a Kademlia átfedőben . . . . . . . . . . . . . . . . . . . . 4.3. Az adattárolás szimulációja . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45 46 47 47

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

3. Betörésérzékelés strukturált P2P átfedőn 3.1. Az elosztott érzékelés jellegzetes problémái . . . . . . . . . . . . 3.2. A Komondor elosztott betörésérzékelő eljárás . . . . . . . . . . . 3.2.1. Strukturált átfedő használata az események eltárolásához 3.2.2. A Kademlia átfedő használata a Komondor eljárásban . . 3.2.3. Az eljárás hatékonyságának igazolása . . . . . . . . . . . . 3.3. A Komondor eljárás alkalmazási lehetőségei . . . . . . . . . . . . 3.3.1. Kulcsok választása a Komondor eljárásban . . . . . . . . . 3.3.2. A Komondor rendszer mérési összeállítása . . . . . . . . . 3.3.3. A Komondor rendszerrel érzékelt támadások . . . . . . .

1

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

TARTALOMJEGYZÉK

2

4.3.1. A hálózati hibák eloszlása . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.2. A replikáció szükséges szintjének meghatározása . . . . . . . . . . . . . 4.4. Az adattárolás helyességének modellezése . . . . . . . . . . . . . . . . . . . . . 4.4.1. A modell és a szimuláció összevetése . . . . . . . . . . . . . . . . . . . . 4.5. A modell alkalmazási lehetőségei . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5.1. A szükséges replikáció jellemző értékei . . . . . . . . . . . . . . . . . . 4.5.2. Az egyedek hibái és a kapcsolati mátrix összefüggése . . . . . . . . . . . 4.5.3. A populációváltozás okozta hibák hatásának kiküszöbölése a replikáció növelésével . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5.4. A modell használata az Azureus és a Mainline BitTorrent hálózatok megbízhatóságának javítására . . . . . . . . . . . . . . . . . . . . . . . . 4.5.5. A szimulációs eljárás használata az elosztott betörésérzékelés megbízhatóságának javítására . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5. Üzenetszórás a Kademliában 5.1. A Kademlia átfedő transzformációja . . . . . . . . . . . . . . . . . 5.2. Üzenetszórás megvalósítása a Kademlia átfedőben . . . . . . . . . 5.2.1. Üzenetszórás elárasztással . . . . . . . . . . . . . . . . . . . 5.2.2. Üzenetszórás a topológia felhasználásával . . . . . . . . . . 5.2.3. Üzenetszórás a topológia felhasználásával és replikációval . 5.3. Az üzenetszórások szimulációban mért eredményei . . . . . . . . . 5.3.1. Az üzenetek száma egyedenként . . . . . . . . . . . . . . . 5.3.2. Az üzenetszórás helyessége . . . . . . . . . . . . . . . . . . 5.3.3. Az üzenetszóráshoz szükséges idő . . . . . . . . . . . . . . . 6. Összefoglalás

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

49 51 52 55 58 58 59 60 61 62 64 65 67 67 67 74 77 77 79 81 84

1. fejezet Bevezetés A számítástechnika kezdeti időszakában, de még a kilencvenes évek elején is, a hálózatba kötött számítógépek forgalma általában épületen belül maradt. Legtöbbször fel sem merült, hogy valaha gazdagépeket, vagy egy egész hálózatot az Internetre kötnek, amely egykor csak katonai, de egészen a közelmúltig is csak akadémiai célokat szolgált. Az Internet növekedésével és elterjedésével azonban a számítógépes biztonsági kérdések egyre inkább előtérbe kerültek. A megjelenő hálózati vírusok, férgek és szakképzett támadók ellen különböző védekező eljárásokat, például tűzfalakat fejlesztettek ki. A nagy földrajzi területeket érintő, akár világméretű számítógépes járványok észlelésének, előrejelzésének igénye elosztott érzékelőrendszerek létrehozását eredményezte. Ezen érzékelő rendszerek képességei és szolgáltatásai eltérőek. Egyes rendszerek a forgalom dinamikáját vizsgálva próbálják meg a világméretű járványok megindulását időben jelezni. Mások intézményi hálózatokat hivatottak védeni a külvilágból érkező, hálózati méretű támadások ellen. Az értekezésemben bemutatott eredmények a Komondor nevű elosztott, hálózati betörésérzékelő és -védelmi rendszerrel kapcsolatos kutatásaim köré csoportosulnak. Ez a rendszer éppen a fő veszélyt jelentő hálózatot próbálja meg arra használni, hogy a gazdagépek védekezőképességét növelje. A működés során a védendő gazdagépek az Interneten létrehoznak egy alkalmazási szintű hálózatot. Az ebbe kapcsolt egyedek az észlelt betörési kísérletekről naplókat vezetnek, amelyekből elosztott adatbázist építenek. Az így szerzett tapasztalatokat megosztják egymás között. Ezzel növelik az összes résztvevő biztonságát, amelyek ezután egyedileg megtehetik a szükséges védelmi lépéseket, például a támadó IP címről érkező forgalmat letilthatják a tűzfalaikon keresztül. Az elosztott érzékelő rendszerrel kapcsolatos céljaim a következők voltak. A betörések érzékelésének általános problémája, hogy a nagy mennyiségű feldolgozandó adat nagy terhelést jelent az érzékelő rendszernek is. A feldolgozott adatok nagy része az érzékelés szempontjából nem tartalmaz hasznos információt. Ezen felül, egyes hálózati szintű támadások csak több ponton érzékelt események adatai alapján ismerhetők fel. Az érzékelők által generált adatok összegyűjtése, összevetése tovább növeli a szükséges számítási és hálózati kapacitást. Kutatásaim célja volt létrehozni egy olyan rendszert, amely az érzékelők által gyűjtött adatot hatékonyan és biztonságosan tudja feldolgozni. Értekezésemben megmutatom, hogy a feldolgozás egy Kademlia alapú, alkalmazási szintű hálózaton hatékonyan elvégezhető. A Kademlia hálózatra, főként az abban tárolt adatok visszanyerhetőségére azonban jelentős hatással vannak a hálózati szintű hibák. Ilyenek például 3

1. FEJEZET. BEVEZETÉS

4

a tűzfalak hatása és a hálózati csomagvesztés. Mégis, a Kademlia megbízhatósága növelhető az adatok több helyen történő tárolása, vagyis a replikáció segítségével. A replikáció viszont nem választható tetszőlegesen nagyra, különösen ilyen mennyiségű eltárolandó adat esetén nem, amelyet az elosztott érzékelő rendszer érzékelői hoznak létre. Kutatásai céljaim között szerepelt a Kademlia átfedő megbízhatóságának hatékony, lehetőleg minél alacsonyabb többlet hálózati forgalmat keltő növelése. A felismert támadás ténye és a védekezés lehetséges módja minden védendő gazdagép számára hasznos információk. A Komondor rendszerben a felismert támadásról minden résztvevőt értesítenek. Ennek eléréséhez kidolgoztam egy algoritmust, amellyel az üzenetszórás az alkalmazási szintű hálózaton elvégezhető. A Kademlia hálózat strukturált felépítése lehetővé teszi, hogy ezt gyorsan és megbízhatóan lehessen elvégezni. A kidolgozott módszerrel elértem azt, hogy az esetleges hálózati hibák esetén az üzenetszórásnál is biztosítani lehessen egy előírt megbízhatóságot. A kutatás Kademlia hálózattal kapcsolatos célkitűzései elsősorban a Komondor céljait szolgálták, azonban a kidolgozott eljárások a Kademlia eljárást használó alkalmazásokban általánosan is alkalmazhatóak. Az általam kifejlesztett, a Kademlián történő üzenetszórás kiterjeszti annak adatlekérdezésekkel kapcsolatos lehetőségeit, segítségével tetszőleges keresések megvalósíthatóak a hálózaton. A tűzfalak és a csomagvesztés okozta megbízhatatlanság megszüntetése is minden Kademlia hálózatra épülő alkalmazásban használhatóak.

2. fejezet Irodalmi összefoglaló A hétköznapok részévé vált Interneten egyre nő a számítógépes bűnözés. Automatikusan működő és terjedő férgek, szakképzett támadók és betörők nehezítik meg, teszik hatékonytalanná a hálózat működését. Az adatok védelme érdekében, valamint a támadások nagy száma miatt önműködő betörésérzékelő és -védelmi rendszerek használatára van szükség. Az Interneten az utóbbi másfél évtizedben elterjedté váltak a peer-to-peer (P2P) átfedő hálózatokat használó alkalmazások. Közülük legismertebbek a fájlcserélő programok, de a P2P átfedők más célokra is alkalmasak, többek között elosztott adatbázisok megvalósítására. A következőkben bemutatásra kerülnek a fenti két témakörrel kapcsolatos legfontosabb eredmények.

2.1. A P2P hálózatok Az utóbbi időben az Internet forgalmának egyre növekvő részét az egyenrangú egyedekből felépülő, P2P alapon működő fájlcserélők adják [1]. Ezek abban térnek el a kliens-szerver architektúrától, hogy míg a központosított esetben egy központi kiszolgáló (server) végzi az adattárolást és válaszol a kliensek keresési és adatlekérési kéréseire, a P2P hálózatoknál az adattárolási és keresési funkcióért minden résztvevő felelős. Ideális esetben nincsen központi szerepet betöltő tagjuk. A P2P hálózatokbban minden egyed egyszerre kliens és szerver. Mindegyik megoszt adatokat, erőforrásokat, illetve használja is a többiek által nyújtottakat. Ezért nevezik ezeket egyenrangú egyedeknek (peer). A P2P alkalmazási szintű hálózatok átfedő hálózatok (application level network, ALN, overlay network), mivel a résztvevők a hálózati szintű topológia felett létrehoznak egy logikai topológiát [2], amely az előbbinél az adott alkalmazásban előnyösebb számukra. A központosítatlan átfedő hálózatok több szempontból is előnyösek, amelyek közül legfontosabb a megnövelt megbízhatóság. Ideális esetben ezek nem rendelkeznek olyan egyetlen hibaponttal (single point of failure, SPOF), mint a központosított megfelelőik. A P2P hálózatok fájlcserélésen kívül egyéb célokra is alkalmasak, különösen elosztott adatbázisok létrehozására, továbbá nagy mennyiségű adat megbízható tárolására, biztonsági mentések létrehozására, internetes televízióadások közvetítésére, telefonhálózatok kialakítására [3] stb. A P2P kommunikációs modellt számítógépes férgek és vírusok hatékonyságának növelésére is felhasználják. Ezekben a fertőzött számítógépekből P2P alkalmazási szintű hálózatot építenek, 5

2. FEJEZET. IRODALMI ÖSSZEFOGLALÓ

6

amelyet arra használnak, hogy a hálózat irányítójának utasításait hajtsák végre, aki általában egy természetes személy [4].

2.1.1. A P2P hálózatok felépítése Az egyenrangú felépítés két fontos, egymással szorosan összefüggő kérdést vet fel. Első az átfedő topológiája, vagyis az, hogy az egyedek hogyan kapcsolódjanak egymáshoz. Második az erőforrások megkereshetőségének problémája (resource discovery), vagyis az, ahogyan megtalál egy egyed a hálózatban egy másik által megosztott erőforrást vagy adatot. Ezek alapján soroljuk a P2P hálózatokat két nagy csoporthoz, a strukturált és a nem strukturált átfedőkhöz. A nem strukturált átfedők esetén az egyedek közötti kapcsolatokban nincs előre meghatározott rendszer. Az átfedőbe belépő új egyedek találomra bármely meglévőkhöz csatlakozhatnak. Ilyen például a Gnutella [5]. Egy adott fájl vagy erőforrás megtalálása a nem strukturált átfedőkön nehéz feladat; az ilyen céllal indított keresési kéréseket általában az egyedek korlátozott elárasztással továbbítják egymásnak. Ez a megoldás nem optimális, hiszen nem skálázható és nem megbízható [6]. A nem strukturált átfedőkkel foglalkozó kutatások célja az ilyen átfedőkön működő keresési és replikációs algoritmusok kidolgozása. A strukturált átfedőknél ezzel szemben az átfedő hálózat topológiája topológiája meghatározott; az abban alkalmazott útválasztási eljárástól függ. A fizikai hálózatokhoz hasonlóan ezekben minden egyed rendelkezik egy hálózati címmel (NodeID), amely meghatározza a helyét és a szomszédait az átfedőben. A létrejött virtuális topológiában előre rögzített útválasztási algoritmus szerint továbbítják az egyedek az üzeneteket. Mivel az egyes NodeID-k alapján egy egyed pontos helye kötött az átfedőben, az útválasztás a hálózat egészének ismerete nélkül is működőképes. Az átfedő egyedei olyan topológiát alakítanak ki, amelyben az átfedő hálózatnak az egyedek közötti ugrások számában értett átmérője nagyságrendben korlátozott, vagyis az egyedek n számával az egyenes aránynál kisebbmértékben nő. Két tetszőleges egyed √ közötti üzenetküldés legfeljebb O (log n), vagy esetleg O n lépésben végrehajtható. A strukturált átfedők egymástól a topológiájukban, és a topológiából következő útválasztási algoritmusaikban térnek el. A nem strukturált átfedőkhöz képest megvalósításuk bonyolultabb; az egyes egyedek feladatai is összetettebbek, főleg az átfedő karbantartási műveletei terén.

2.1.2. Elosztott hash táblázatok A strukturált átfedők általában elosztott hasító táblákat (distributed hash tables, DHT) valósítanak meg. A hasító táblák1 kulcs-érték párokat, adattételeket tárolnak. Minden eltárolandó adatcsomaghoz, értékhez egy azonosítót, kulcsot rendelnek, amellyel arra hivatkozni lehet. Fájlcserélő alkalmazásokban az érték a fájl tartalma, a kulcs pedig a fájl neve. Az elosztott hasító táblázatban történő tárolást úgy oldják meg, hogy a kulcsot egy hasító függvény (hash function), például az SHA-1 [7] segítségével leképezik egy általában 128 vagy 160 bites értékkészletre. Az átfedőben az alkalmazási szintű címeket (NodeID) is ekkora tartományból választják. Minden egyed azokat a kulcs-érték párokat tárolja, amelyek kulcsának hasított (hash-elt) értéke legközelebb esik a saját azonosítójához. Így minden adatról tudni lehet, hogy 1 Az

angol hash table kifejezést elterjedten fordítják hasító táblának és tördelő táblának is.


7 2n-1 0

2.1. ábra. A Chord átfedő

hol kell keresni az átfedőben. Egy fájl kereséséhez szükséges műveletek megegyeznek egy egyszerű üzenetküldéshez szükséges lépésekkel, ugyanis mind a kettő ugyanazt a címteret használja. A hasító függvény kimenete a címteret egyenletes eloszlással használja. Ez lehetővé teszi azt, hogy az eltárolt adatokat az átfedőben egyenletesen osszák el az egyedek között [8]. Így az egyedek terhelése egyenletessé válik, amennyiben azok is egyenletesen használják ki a címteret. Természetesen a gyakorlatban a tárolt adatok eloszlása csak határértékben egyenletes [9]. A címteret a címek nagy száma miatt matematikai modellekben gyakran folytonos változóval közelítik [10]. Ilyenkor a hasító függvény kimenete is folytonos, egyenletes valószínűségi változónak vehető. A kikereséseknél (lookup), vagyis az adattételek lekérdezésénél gyakoribb az egyenetlen terhelés. Lehetséges, hogy egy adott kulcsot sokkal gyakrabban keresnek a hálózat résztvevői, mint a többit, és ezzel a kulcsot tároló egyednél, illetve annak szomszédságában megnövekszik az átfedő hálózati forgalma. Ezek az ún. forró pontok (hot spot). Ezek elkerülésére a hálózat topológiájának függvényében eltérő megoldásokat alkalmaznak [11]. Strukturált P2P átfedők topológiája A strukturált átfedők működését meghatározza a topológiájuk, és az azzal összefüggő útválasztási algoritmusuk. A tervezésük legfontosabb szempontja a skálázhatóság biztosítása; ennek mérőszáma pedig a hálózat átmérője az egyedszám függvényében (lásd a 2.1. táblázatot). Minél kisebb az átmérő, annál kevesebb protokollüzenettel lehetséges adatot továbbítani egyik egyedtől a másikig. A Chord átfedő egyedei a 2.1. ábrán látható módon egy kör alakú topológiát alakítanak ki [12]. A hálózati címek a kör mentén helyezkednek el; az utolsó, 2n − 1 című egyed után megint a 0 című következik. Minden egyed azokat az adattételeket tárolja, amelyek az ő, és a rákövetkező egyed címe között helyezkednek el. Az egyedek kapcsolatban vannak a szomszédjaikkal, vagyis a közvetlenül előttük és utánuk lévő egyedekkel. Ezen felül, mindegyikük kapcsolatban van a körben vele szemben, vagyis egy fél körrel arrébb lévő, és egyed negyed,


8

2.2. ábra. A CAN átfedő Átfedő

Topológia

Távolság

Útválasztás

Átmérő

Chord

kör

kivonás

rekurzív

O(log 2 n)

CAN

d-tórusz

ortogonális

rekurzív

O(d · n1/d )

Kademlia

bináris fa

XOR

iteratív

O(log 2 n)

2.1. táblázat. DHT hálózatok összehasonlító táblázata

nyolcad körrel arrébb lévő egyeddel is, és így tovább. Ezen egyedek adatait tartalmazó ún. mutató táblák biztosítják a skálázhatóságot. Az üzenetküldés során az egyedek az üzenetet egymásnak továbbítják; az üzenet távolsága a céltól a mutató táblák segítségével minden lépésben megfelezhető. Az üzenet így az átfedőn belül legfeljebb O(log 2 n) továbbítás után célba ér. A CAN (Content Addressable Network) átfedő egyedei egy n-dimenziós tórusz alakú topológiát hoznak létre [13]. A kulcsok címterét erre a tóruszra képezik le ; az üzeneteket pedig úgy továbbítják egymásnak, hogy az a tórusz felületén a legrövidebb úton jusson célba. A dimenziók számának növelésével az átfedő átmérője csökken. Így az üzenetküldés gyorsul, viszont a karbantartási műveletek egyre több erőforrást igényelnek. A 2.2. ábra egy kétdimenziós CAN átfedőt mutat síkba kiterítve. A távolság két pont között Pitagorasz tételével számítható ki. A nyilak egy üzenetküldésre mutatnak példát. √ A hálózat átmérője, vagyis egy üzenet célba juttatásához szükséges lépések száma O(d · d n), ahol n az egyedek, d pedig a dimenziók száma. Komplex keresések strukturált P2P átfedőkben A strukturált átfedők hátránya, hogy a gyors kikeresést csak a kulcsok pontos ismeretében képesek elvégezni. Ha egy adattétel pontos kulcsa ismeretlen, akkor lehetetlen meghatározni az ahhoz tartozó hasított értéket, és így az egyedet, amelyik azt az adatot tárolja. Részben


9

0 0 0

1

0

1

0 0 1

0 1

1

0 1

0

1 0 1

0 1

0 1 0 1

1 0

1 0 1

0 1

0 1

1 0 1

0 1

2.3. ábra. A Kademlia átfedő

vagy pontatlanul ismert kulcs, és más keresési szempontok esetén a kikeresési eljárás nem használható [14]. Ebben az esetben két lehetséges eljárás alkalmazható a keresések megvalósítására. Az egyik az, hogy az átfedő felett egy üzenetszórás (broadcast) segítségével minden egyedhez eljuttatjuk a keresési kérést [15], amelyet aztán saját maguk dolgoznak fel. Az átfedő strukturája hatékonyabb üzenetszórást tesz lehetővé, mint ami a nem strukturált átfedők esetében elérhető. A másik lehetőség keresési indexek építése az átfedőben [16]. Az előbbieknél jelentős lehet az egyes keresések által keltett hálózati forgalom, míg az utóbbi hátránya az, hogy a keresési indexek karbantartási költsége magas lehet.

2.2. A Kademlia átfedő felépítése A Kademlia egy fájlcserélő alkalmazásokhoz kifejlesztett, bináris fa topológiájú DHT, vagyis elosztott hasító táblázat alapú átfedő [11]. A Kademlia DHT-ben az egyedek átfedőbeli címeik szerint egy bináris fába rendeződnek. Az útválasztás ezen részfák alapján történik (2.3 ábra). Az egyes egyedek minden távoli részfából kapcsolati lehetőségeket (IP hálózati címet és port számot) tartanak nyilván az útválasztási táblázataikban. Ezeket a részfákhoz rendelt listákat k-vödröknek nevezzük (k-bucket). Méretük a k szám, amely egy rendszerszintű konfigurációs paraméter. Ezt az átfedő stabilitási fokának is nevezzük, hiszen ha a k elemű listából (k-vödörből) csak egyetlen egyed is elérhető, akkor az adott részfának lehet üzenetet küldeni. Nagy átfedőkben többszintű részfák is előfordulnak. A magasabb részfákban jóval több egyed van, mint k, vagyis a fának a távoli részeiről egy adott egyednek arányaiban kevesebb tudása van, míg a hozzá legközelebbi egyedek közül mindegyiket ismeri. A Kademlia ezen tulajdonsága biztosítja a skálázhatóságot. A Kademlia átfedő egyedei között az üzenetek továbbításához szükséges útválasztás a 2.4. ábrán látható módon történik. Ha egy egyed üzenni szeretne egy másiknak (pl. az ábrán a 00110 című egyed az 11000 címűnek), nem kell mást tennie, mint küldeni egy lekérdezést bármelyiknek az 1-essel kezdődő részfában, mivel az jobban ismeri az 11-gyel kezdődőek részfáját. Ez az egyed visszaküld egy k-vödröt azon egyedek IP címével, amelyek NodeID azonosítói a címzett egyed saját helyzetéhez képest egy helyiértékkel közelebb vannak a célhoz.


10

0 0 0

1 0 1 0 1 0 1

1 0

1 0 0 1

0

1 0 1

0

1

0 1

0 1 0 1

1

0 1

0 1

0 1

1 0 1

0 1

1 4

2 3

2.4. ábra. Útválasztás a Kademlia átfedőben

A 2.4. ábrán látható példa esetében a kezdeményező, 00110 című, feketével jelölt egyed először az 10000 című egyednek üzen, amely az 1-gyel kezdődő című egyedek részfájának k-vödrét küldi vissza a kezdeményezőnek. Ezután ebből választja ki az 11000 címűt, amelyiknek máso dikként küld üzenetet stb. Az üzenetküldések sorozata O log2 N lépésben eléri a célt, ahol N az egyedek száma. Az egyedek két azonosító távolságát a kizáró vagy (eXclusive OR, XOR, ⊗) függvénnyel számítják ki. d(A, B)-t, vagyis az A-val és B-vel jelölt egyed közötti távolságot a d(A, B) = A ⊗ ⊗ B képlettel tudjuk kiszámítani. Minél nagyobb helyiértéken találunk a távolságban 1-est, annál távolabbi részfában van a keresett egyed. Például a 2.4. ábrán a 01011 és a 01100 egyed távolsága 01011⊗01100 = 00111, amelyben felülről számítva a harmadik bit az első 1-es. Ebből az is látszik, hogy az egyedek közös negyed (1/23−1 ) részfában vannak. A bináris fával az átfedő hálózat XOR metrikával értelmezett topológiáját ábrázoljuk, nem pedig az egyedek közötti konkrét kapcsolatokat. Ezt az alakzatot XOR topológiának is nevezik. Megjegyzendő, hogy az egyedek az átfedő topológiáján mért távolságának semmi köze az egyedek által képviselt számítógépek földrajzi elhelyezkedéséhez. A XOR topológián értelmezett lekérdezések a fenti definíció alapján szimmetrikus műveletek. Minden egyed, amelytől üzenetet kap egy adott egyed, bekerül az útválasztási táblázatának megfelelő k-vödrébe. Ha az megtelik, akkor arról a távoli egyedről szóló információ törlődik, amelyről a legrégebben hallott a vizsgált egyed. Egy csomópont útválasztási táblázata, vagyis a részfákhoz tartozó egyes k-vödrök kétféleképpen frissülhetnek: 1. az egyed által kezdeményezett lekérdezésekre kapott válaszokban található új elérhetőségek rögzítésével, 2. az egyedet elérő, más csomópontok által küldött üzenetek IP címeinek rögzítésével. Mivel a XOR függvény szimmetrikus, a bejövő és a kimenő üzenetek eloszlása azonos: egy adott egyedet hívó másik résztvevők eloszlása éppen megegyezik az útválasztási táblázat


11

eloszlásával. (Formálisan, annak valószínűsége, hogy egy [2i , 2i+1 ] tartománybeli egyedtől kapunk üzenetet, i-től független konstans [11].) Ez a szimmetria hasznos, mert így egy egyed útválasztási táblázata ugyanúgy frissül, akár lekérdezéseket hajt végre az egyed, akár azt kérdezik le más csomópontok. A frissülés egy egyednél mindig létrejön, függetlenül attól, hogy indítanak-e tőle lekérdezést vagy nem. A táblázatok működés közbeni frissülése egy olyan mellékhatás, amelynek következtében a hálózat önmegerősítő.

2.2.1. A Kademlia átfedő üzenetei A Kademlia átfedőben a következő típusú üzeneteket küldik egymásnak az egyedek: FIND_NODE. Egy adott címmel rendelkező egyed keresése. A válasz erre egy k-vödör, átfedőbeli cím (NodeID), IP cím, port szám összerendelésekkel. FIND. Adott kulccsal rendelkező adat keresése. A válasz lehet az adattétel, ha fogadó egyed tárolja azt; vagy lehet egy k-vödör a címhez közelebbi egyedek listájával, ha nem. STORE. Adattétel eltárolása. Ezt az üzenetet közvetlenül annak az egyednek kell küldeni, amelyiknek a tárolást el kell végeznie. PING. Egyed meglétének ellenőrzése. A Kademliától eltérően a többi DHT átfedőben az egyedek az üzeneteket útjukra indítják az átfedőn, valamelyik szomszédjuknak elküldve. A többi egyed pedig lépésről lépésre küldi tovább a cél felé. Ezt a 2.5. ábrán látható megoldást rekurzív útválasztásnak nevezzük [17]. A Kademliában viszont ez másképpen működik. Adott kulcs tárolásához például a tárolást kérő egyed az üzenetet nem útjára indítja, hogy az átfedő többi egyede lépésről lépésre továbbítsa azt a cél felé, hanem maga keresi fel a kulcshoz legközelebbi egyedet. Ezt az eljárást iteratív útválasztásnak2 nevezzük, ahogyan azt a 2.5. ábra is szemlélteti. Az útválasztás során az egyed maga kérdez a célhoz egyre közelebbi és közelebbi egyedeket a cél egyed IP címéről, amíg ténylegesen el nem jut ahhoz. A célhoz pedig aztán maga a kérdező egyed juttatja el az üzenetet. Ez érvényes a kulcs eltárolásokra (STORE üzenet) és a kikeresésekre, lekérdezésekre (FIND és FIND_NODE üzenetek) is.

2.2.2. A Kademlia átfedő megbízhatatlansága Az iteratív útválasztással az egyedeknek az üzenetküldés szempontjából rengeteg választási lehetőségük van. Egy Kademlia egyed akár több száz ismert másik társának a címét tarthatja nyilván a k-vödrökben. Ebből az következik, hogy nem tarthatnak fenn egymással vonalkapcsolt közlési viszonyt, mivel ennyi nyitott, felépült közlési viszonyuk nem lehet (lásd a 2.2. táblázatot). A több ezer nyitott TCP kapcsolat helyett a Kademlia UDP-t, vagyis csomagkapcsolt üzenetküldést használ [11], ahogyan a legtöbb másik DHT átfedő is. 2A

Kademliát bemutató első közlemény éppen fordítva használja ezt a két fogalmat [11]. Egy adott egyed szempontjából nézve a folyamatot, pontosabban leírja azt az iteratív jelző, mivel ő maga felelős az egymás utáni lekérdezésekért, amíg a cél címét meg nem kapja.


(a) rekurzív

12

(b) iteratív

2.5. ábra. Útválasztási metódusok DHT hálózatokban üzenetküldés típusa

definíció

vonalkapcsolt

Az összeköttetés a kommunikáció időtartama alatt folyamatos. Ilyen az Interneten használt TCP adatátvitel.

csomagkapcsolt

Az üzenetküldés során a küldő és a címzett között folyamatos kapcsolat nincsen; az üzenetek egymástól független csomagokként kerülnek továbbításra.

2.2. táblázat. Csomagkapcsolt és vonalkapcsolt üzenetküldés

A tűzfalak és a címfordítás hatása Az alkalmazott iteratív útválasztás azt is feltételezi, hogy bármelyik egyednek képesnek kell lennie csatlakoznia bármelyik egyedhez. Emiatt a hálózati szintű hibák így közvetlenebb hatást gyakorolnak a Kademliára, mint más, rekurzív útválasztást használó átfedők esetében [17], a hálózati hiba ugyanis nem csak egy megszakadó kapcsolatot vagy csomagvesztést, hanem a kapcsolatteremtés képességének teljes hiányát is jelentheti. Ez UDP használata esetén gyakrabban előfordul, mint TCP kapcsolatoknál [18], a címfordítás (network address translation) és csomagszűrés (packet filtering) miatt [19]. Ezekben az esetekben a kapcsolódások lehetősége gyakran aszimmetrikus: egy címfordítás mögött lévő egyed tud csatlakozni egy nyilvános (publikus) IP címmel rendelkezőhöz, míg fordítva ez nem igaz [20]. A fenti hatások miatt az internetes alkalmazások tervezésekor általában használt, a 2.3. táblázatban bemutatott három alapvető feltételezés, melyek szerint a kapcsolatok reciprok, tranzitív és perzisztens tulajdonságokkal rendelkeznek, nem teljesül. A reciprocitás azt a feltevést jelenti, mely szerint ha A egyed képes üzenetet küldeni B egyednek, akkor ez fordítva is igaz, vagyis B is képes üzenni A-nak. Tűzfalak, és egyes címfordítási eljárások esetén ez nem mindig van így. Az utóbbiak esetén általában ez az idő függvénye is. Ha B néhány percen belül válaszol A-nak, az üzenetküldés sikeres, később pedig sikertelen, vagyis a kapcsolat nem perzisztens. Az ilyen jellegű működés miatt lehetséges az is, hogy bár A és B kölcsönösen képes egymással kommunikálni, de egy harmadik egyed, C már nem képes kapcsolatot teremteni A-val, hiába kapja meg B-től A IP címét; vagyis a kapcsolat nem tranzitív. A tapasztalatok alapján egyedek

2. FEJEZET. IRODALMI ÖSSZEFOGLALÓ feltételezés

magyarázat

reciprocitás

Ha A csomópont képes üzenni B-nek, akkor B is A-nak.

tranzitivitás

Ha A csomópont képes üzenni B-nek, és B képes C-nek, akkor A csomópont C-nek is tud üzenetet küldeni.

perzisztencia

Ha A üzenetet küld B-nek, és B képes válaszolni, akkor ez később is így lesz.

13

2.3. táblázat. Feltételezések két csomópont közötti üzenetküldésre az Interneten

akár 60-70%-a tűzfal mögött lehet [21]. A MainLine BitTorrent hálózaton végzett mérések alapján a csomópontok csak 80%-a rendelkezik a reciprok kapcsolatteremtés lehetőségével, míg 40%-uk tranzitívval [19]. A rendszer elméleti tervezésekor a Kademlia hálózati hibákra való különös érzékenységére nem adtak megoldást, áthárítva a feladatot a konkrét implementációra. A kikeresések helyességét a nagyra választott k-vödrök biztosítják. A tűzfalakon, illetve címfordításon keresztül történő kapcsolat felépítésére viszont nincsen egyszerű és jó megoldás az azokat megvalósító eszközök és szoftverek lényegesen eltérő működése miatt [20]. Két tűzfal vagy hálózati címfordítás mögötti gép kapcsolódásához általában szükség van egy harmadik, nyilvános IP címmel rendelkező félre, amely a kapcsolatban közvetítő szereppel rendelkezik. Az ilyen jellegű megoldás hátránya, hogy leginkább csak központosított vagy részben központosított átfedőkben alkalmazható. Nincsen olyan megoldása sem ennek a problémának, amely az esetek 100%-ában biztosan működne, ugyanis gyakori az olyan helyzet is, amikor egy egyed többszörös címfordítás mögött van [22]. A leírtak alapján a Kademlia hálózatban az összekötöttség csak látszólagos. Az egyedek ugyan minden részfához tárolnak legfeljebb k IP címet, de ez nem jelenti azt, hogy az egyes részfákhoz ténylegesen ennyi kapcsolattal rendelkeznek. Igen gyakori az az eset, amikor egy egyed rendelkezik egy másik IP címével, de a tűzfal vagy a címfordítás miatt nem tud üzenetet küldeni annak. Egyes források szerint valós átfedőkben ez akár a kapcsolatok 15%-át is érintheti [17]. A kapcsolatok hiánya miatt két szempontból is kisebb az átfedő megbízhatósága. Egyrészt előfordulhat az is, hogy egy adat (tétel) eltárolás esetén nem a címéhez legközelebbi egyedhez kerül, ahol a többi egyed keresni fogja. Másrészt gyakori az is, hogy egy tétel ugyan a megfelelő helyen van, de a lekérdező egyed nem tudja elérni azt. Az útválasztási táblázatok hibái A hálózati hibák miatt az útválasztási táblázatok pontossága is romolhat a Kademlia átfedőben. Statikus esetben ez azért van így, mert előfordulhat, hogy egy lekérdezésnél olyan egyedet nem ér el a lekérdezés indítója, amelyikhez csatlakoznia kellene az adott k-vödör letöltéséhez. Ilyenkor egy távolabbi egyedtől kényszerül lekérdezni az adatokat, amelyik azonban a célponttól távolabb lévén, kevésbé pontos információkkal rendelkezik a cél környezetéről. Dinamikus esetben, amikor az átfedő változik, leggyakrabban az egyedek folyamatos, gyors ki- és belépése miatt keletkezhet a táblázatokban pontatlanság. Ezen fluktuáció angol neve az


14

irodalomban „high churn” [23], amit felpörgésnek fordíthatunk. Ha egy adott egyed távozik a hálózatból, vagy egy új egyed jelenik meg valamelyik célponthoz közelebb minden addiginál, akkor időbe telik, mire a környezete erről tudomást szerez.

2.2.3. Replikáció a Kademlia átfedőben A Kademliában a hálózatból kilépő egyedek nem adják át tárolt tételeiket a szomszédos egyedeknek, hanem azok egyszerűen elvesznek a hálózatból [11]. Ennek a problémának a kezelésére a Kademlia protokoll a tételek több helyen történő tárolását írja elő. Ezt replikációnak vagy másodlatolásnak nevezzük (replication). Erre egyszerű megoldást adnak maguk az egyedek által szervezett kulcs-eltárolások és -lekérdezések. A replikáció a következőképpen működik. Egy adott tételt eltárolni szándékozó egyed nem a kulcshoz legközelebbi egyednek, hanem annak környezetében, ahhoz legközelebbi k darab egyednek küldi el a STORE üzenetet. Így ha a k egyed közül valamelyik kilép a hálózatból, az adott tétel továbbra is elérhető marad k − 1 helyen. A Kademlia protokoll előírásai szerint egy adott tételt óránként újra publikálni kell, vagyis a tárolást óránként újra el kell végezni [11]. (Az ezzel járó hálózati forgalom korlátozására az eljárás tartalmaz itt nem részletezett megoldásokat.) A k értékét a fentieknek megfelelően úgy kell megválasztani, hogy kellően valószínűtlen legyen az, hogy egy órán belül mind a k egyed elhagyja a hálózatot. Maymounkov, a Kademlia tervezője k = 20-szoros replikációt javasol, némileg önkényesen a Gnutella átfedőben mért felhasználói viselkedések, szokások alapján. Fontos kiemelni, hogy az idézett cikk nem különbözteti meg a k-vödrök méretét a replikációtól ; a replikáció szintjének a k-vödrök méretét választja, és ezért mindkettőt k-val jelöli. A belépő egyedeknél elvileg nincsen ilyen probléma. Amikor egy új egyed belép a hálózatba, akkor a saját azonosítója felé indít el kikeresést. Ezáltal megismeri a szomszédait; utána pedig frissíti minden távolabbi részfához tartozó k-vödrét. A szomszédai, tudomást szerezve az új egyedről, eltárolják nála azokat a kulcsokat, amelyek hozzá közelebb vannak, mint saját magukhoz. Erre azért van szükség, mivel a későbbi kikeresések is az új egyednél próbálják majd meg először kikeresni a kulcsot, amelyhez az új egyed címe van legközelebb a címtérben.

2.3. Üzenetszórás P2P átfedőkben Az üzenetszórást (egytől mindenkinek, broadcast) a P2P átfedőkön legtöbbször nem igénylik az azokra épülő alkalmazások. Az egyedek nagy száma miatt az üzenetszórás egyébként is sok erőforrást igényel. A strukturált átfedőket pedig éppen azzal a céllal hozták létre, hogy a Gnutellához hasonló nem strukturált átfedőkben használatos elárasztást hatékonyabb keresési eljárásokkal váltsák ki (lásd a 2.1.1. szakaszt). Egyes alkalmazásokban szükséges az üzenetszórás. Segítségével ugyanis megvalósítható a kulcsrészlet töredékekre, vagy csak pontatlanul ismert kulcsra történő keresés [15]. A strukturált átfedőkben alkalmazott hasító függvények tulajdonságai ezt eredendően nem teszik lehetővé; a strukturált átfedő útválasztásával a hatékony keresés csak a kulcs pontos ismeretében lehetséges. Az irodalomban bemutatott üzenetszórási algoritmusok jelentős hányada a Chord átfedőn működik [12].


15

Egy részük felelősök kijelölésére épül. Ezek az átfedőn továbbított kikeresési kéréseket tekintik mintának az üzenetszórás továbbításához [24]. Erre tekintsünk példának egy [0,8) tartományú címekkel rendelkező Chord átfedőt. A 0 című egyed által indított kikeresés gondolatmenete az, hogy a keresett adat a [0,4) vagy a [4,8) tartományokban található. Ha az előbbiben, akkor a tartományt a keresőnek tovább kell finomítania, [0,2) és [2,4) részekre osztva azt. Ha az utóbbiban, akkor pedig annak a tartománynak az elején elhelyezkedő egyedre hagyatkoznia, mert az rendelkezik több információval az átfedő azon tartományáról. Az üzenetszórás ehhez hasonlóan végezhető: a tartományt két részre osztva, és ezekből egy-egy felelős egyedet kijelölve arra a célra, hogy azok elvégezzék az üzenetek küldését [15]. Az üzenetszórás hatékony, elvileg pontosan N − 1 hálózati üzenetet igényel csak, ahol N az átfedő egyedeinek a száma. Ez az üzenetszórási algoritmus azonban nem áll ellen a csomagvesztéseknek, illetve a ki-belépések miatt időlegesen hibás útválasztási táblázatoknak. Az algoritmus megbízhatósága javítható azáltal, ha az üzenetszórásról az egyes felelős egyedek visszajelzést adnak az őket kijelölőknek. Ez egy rekurzív eljárás ; egy egyed akkor ad visszajelzést, ha az összes általa megbízottaktól megkapta azt. Időtúllépés esetén a kijelölő egyed más felelőst választ az adott tartományból [25]. Ez a megoldás hibás útválasztási táblázatok esetén ugyan helyesen működik, de rosszindulatú egyedek esetében nem. Egy rosszakaratú egyed ugyanis félrevezetheti a megbízóját azzal, hogy nem továbbítja az üzenetet, de mégis nyugtázza, mintha továbbküldte volna. Más algoritmusok nem csak felelősök kijelölésével, hanem az üzenetek „járványszerű” továbbításával fedik le az átfedők. Ilyen az Efficient Broadcast in P2P Grids nevű algoritmus [26]. Ez az előbb említettet azzal egészíti ki, hogy a felelősök időnként véletlenszerűen továbbítják az üzenetet szomszédaiknak is. Így előbb-utóbb azok eljutnak azokhoz az egyedekhez is, amelyekhez tartozó felelős meghibásodott vagy kilépett az átfedőből. A felelősök kijelölése gyorsabb üzenetszórást tesz lehetővé, mint a véletlenszerű továbbítás; az utóbbi viszont kilépő egyedek esetén is megbízhatóbb. A két megoldás ötvözése esetén az elpazarolt, vagyis az N − 1 darab feletti üzenetszám nem növekszik meg túlzottan. Ezek az algoritmusok bármilyen tartalmú üzenet továbbítására használhatóak. Speciálisabbak azok az eljárások, amelyeket kifejezetten a globális keresés megvalósítására hoztak létre. Ezekben az üzenetszórás megszakad, ha egy adott egyed a keresési kérésre tud válaszolni [27], vagy esetleg az üzenetszórás átmérőjét korlátozzák a csomagokhoz rendelt TTL (time to live) mezőkkel, amelyeket minden továbbításkor csökkentenek [28]. Látható, hogy az üzenetszórás az átfedők címterének megfelelő partícionálásával és felelősök kijelölésével N − 1 üzenettel elvégezhető. A partícionálás módja az üzenettovábbítás idejét módosítja. A gyors üzenetszórás szempontjából előnyös az a partícionálás, amelyben minden egyed legfeljebb O(log N ) továbbítás után megkapja az üzenetet. Egyéb esetekben az üzenetszórás az egész átfedőre nézve lassabb lesz. Az egyes algoritmusok leginkább különböznek, hogy a kilépő, kieső, esetleg az üzenetszórás közben újonnan belépő egyedeket milyen megbízhatósággal képesek kezelni, illetve ezek kezelése mekkora többlet költséggel jár.

2.4. P2P átfedők szimulációja A P2P átfedők útválasztását, algoritmusait háromféle eszközzel lehet igazolni és jellemezni: matematikai bizonyítással, szimulációval és kísérletekkel [29].


16

Szimulátor

Architektúra, fizikai hálózat modellje

P2P átfedők, megjegyzések

NS-2

csomag alapú Gnutella TCP/IP hálózat, hálózati és fizi- a célhoz képest alacsony szintű kai réteg

OverSim

átfedő alapú (strukturált és nem Chord, Pastry, Kademlia stb. strukturált is) két modell, egy lassú, pontosan gyakran használt, részletes dokukonfigurálható, és egy egyszerű- mentációval sített

P2PSim

átfedő alapú, diszkrét idejű, ese- Chord, Accordion, Kademlia stb. ményvezérelt adatbázis, GT-ITM, véletlensze- kevés dokumentáció, általában a rű, Euklideszi alapú késleltetés forráskódot kell módosítani

GnutellaSim

csomag alapú, protokollcentri- Gnutella kus Kimenet NS-2 által használt forGT-ITM mátumban

Overlay Wea- csak strukturált átfedők programozható ver valós TCP/IP kapcsolatokkal, fő célja algoritmusok tesztelése vagy szimulált 2.4. táblázat. P2P szimulátor alkalmazások

Az algoritmusok bonyolultsága miatt, és az átfedők működés közbeni peremfeltételeinek nehéz modellezése miatt a matematikai megközelítés ritkán, általában csak túlzott egyszerűsítések mellett alkalmazható [30]. A valós rendszerek komplexitását ezekben az esetekben gyakran el kell hanyagolni. Ha a matematikai megközelítés túl bonyolult, kísérletek is végezhetők a valós rendszereken. Azonban a valós P2P hálózatok gyakran 105 –106 egyedszámmal rendelkeznek, ilyenkor a kísérlet legtöbbször kivitelezhetetlen. A kísérlet paramétereinek módosítása, pl. a protokoll változtatása pedig bonyolult és időigényes. A megvalósult, valós átfedőn folyó kísérletek nagy része a Planetlab hálózaton történt [31]. A szimulátorok ezeket a hátrányokat próbálják meg kiküszöbölni. Az átfedők szimulációja ugyanakkor nem független a matematikai és a kísérleti megközelítéstől. Amennyiben lehetséges, a matematikai modelleket szimulációval kell igazolni, a szimulációs eredményeket pedig valós hálózatokon ellenőrizni [29]. A P2P átfedők szimulációja többféle absztrakciós szinten történhet. Ennek megfelelően az átfedő alapjául szolgáló fizikai hálózat egyes részeit, esetleg magának az átfedőnek vagy az algoritmusnak egyes részeit a szimuláció teljesítménye érdekében el kell hanyagolni. Az irodalomban ismertetett szimulátorok különféle absztrakciós szinteken dolgoznak, illetve


17

100 King data set Mainline BT

90 80

egyedek aránya [%]

70 60 50 40 30 20 10 0 0,01

0,1

1

10

késleltetés [s]

2.6. ábra. Egyedek közötti késleltetési idők P2P átfedőkben

különféle átfedő hálózatokat tudnak szimulálni. Ezeket a 2.4. táblázat áttekinti. Nem ritka, hogy a létező szimulátorok egyike sem felel meg egy adott feladathoz; a kutatók ilyenkor saját szimulátor motorok írásával igyekeznek igazolni az általuk kidolgozott eljárásokat. Egy kimutatás szerint a P2P hálózatokkal foglalkozó közlemények szerzőinek kétharmada saját fejlesztésű szimulátorral dolgozik [32]. A P2P átfedők saját szimulációs motorral történő vizsgálatához az irodalomban rendelkezésre állnak valós hálózatokon mért adatok, például késleltetési idő adatbázisok. Ezek az Interneten elérhetőek. A legismertebb ilyen adatbázis a King data set [33], amely 1740 csomópont között páronként mért késleltetési időket tartalmazza. További adatok érhetőek el a Crosby-Wallach szerzőpáros cikkében [17, 34], amelyet a Mainline BitTorrent átfedőkön végzek kísérletekből nyertek. A két eloszlás jelentősen eltérő adatokat tartalmaz, ahogyan az a 2.6. ábrán is látható. A King nevű mérési eljárásnál az 1 s-nál hosszabb időket nem vették figyelembe, vagyis a eloszlás összes késleltetési ideje 1 s-nál rövidebb. A Mainline BitTorrent átfedőből származó adatok esetén pedig még 18 s-os késleltetést is tartalmaz az eloszlás; a szerzők szerint azért mérhető ilyen hosszú válaszidő, mivel a BitTorrent egyedek az elsődleges céljukat, a fájlok továbbítását, és az ahhoz kapcsolódó hálózati üzeneteket előnyben részesítik az átfedő karbantartási üzeneteihez képest [17].


18

2.5. Betörésérzékelő rendszerek Az eredetileg a tudományos munkát segítő Internet ma már a kereskedelem, a szórakoztató ipar, a sajtó, a kormányzatok, és nem utolsó sorban magánemberek mindennaposan használt eszközévé vált. Az információ értéke, az elektronikus kereskedelemben történő hatalmas pénzmozgások és a hálózatra kötött számítógépek hatalmas együttes erőforrása miatt mindennapossá vált az Interneten a bűnözés is. A hálózatba kötött adattárolókat nem csak fizikailag kell védeni az adatlopások és egyéb károkozások ellen, hanem a hálózatról érkező támadásoktól is védenünk kell azokat. Az értekezés ezen része az irodalomban ismertetett betörésérzékelő eljárásokat ismerteti röviden.

2.5.1. A betörésérzékelés célja A hálózatra kötött számítógépeket többféle céllal támadhatják meg: anyagi vagy egyéb előnyök megszerzése vagy elismerés kivívása céljából [35]. A támadók eltérő céljai és a védendő célpontok jellegzetességei miatt miatt a hálózatra kötött gazdagépeket (host) több oldalról kell védenünk. Ennek megfelelően a betörésérzékelésnek is többféle célja lehet. Adatszivárgás elleni védelem. Adatszivárgásnak nevezzük, amikor a számítógépen tárolt információ illetéktelen kézbe, egy külső támadóhoz kerül. Az adatkiszivárgásnak három fő módja lehet: 1. a támadó hozzáférést szerez a számítógéphez, 2. a hálózati forgalom megfigyelésével, lehallgatásával, illetve 3. a számítógép saját, feljogosított felhasználója általi visszaélés [36]. Erőforrások védelme. Az adatok védelmén kívül az erőforrások védelméről is gondoskodni kell. Az erőforrások alatt nem csak a hardvert értjük: jellegzetes támadási forma például, amikor a támadó a nyomozás megnehezítése végett egy adott gazdagép felett megszerzi az irányítást, hogy arról indítson további támadásokat más célpontok felé. Így a láncban következő megtámadott gazdagép a támadás forrásaként már tulajdonképpen egy áldozat gazdagépét látja. Adatintegritás, rendszerintegritás védelme. A tárolt adatot nem csak ellopni, hanem megváltoztatni is lehet. Egy gazdagép az információ módosítása igen alkalmas gazdasági károkozásra. A rendszerintegritás fogalma ezzel szemben a gazdagép viselkedésére vonatkozik: a kiszolgáló a rendszergazda szándékai szerint működik-e. A támadó megváltoztathatja, akadályozhatja annak működését, szintén károkozás céljából. Újabban már nem csak kiszolgálókat és asztali, személyi számítógépeket kötnek az Internetre, hanem modernebb mobiltelefonok is rendelkeznek csatlakozási lehetőséggel. Ezekre is megjelentek már a kártevő programok [37].

2. FEJEZET. IRODALMI ÖSSZEFOGLALÓ típus

definíció

vírus

Olyan program, amely saját másolatát valamely másik programban vagy dokumentumban helyezi el. Ezek önálló programként nem működnek.

féreg

Önmagát sokszorosító program, amely legtöbbször hálózaton keresztül terjed. A megtámadott gazdagép biztonsági réseit használja ki, és automatikusan terjed.

kémprogram

Másik programmal együtt telepített rosszindulatú program. Ennek telepítéséhez tulajdonképpen a felhasználó beavatkozására van szükség, még ha tudta nélkül történik is ez. A program a felhasználói tevékenységét monitorozza, pl. jelszavakat gyűjt.

trójai program

Egy program kinézetét, esetleg szolgáltatásait imitáló program, amely rosszindulatú tevékenységet is végez.

19

2.5. táblázat. Rosszindulatú programok (malware) típusai

típus

definíció

backdoor

Hátsó kapu. A fertőzött gépen futó rosszindulatú program kiszolgálóként üzemel, amelyhez csatlakozva egy irányító program vagy személy parancsokat küldhet annak.

botnet

Rosszindulatú programok a megfertőzött számítógépekből akár több millió egyedből álló hálózatot építenek. A fertőzött gépek együttes ereje (pl. sávszélessége) általában egy irányító személy kezében van.

2.6. táblázat. Rosszindulatú programok kapcsolattartása készítőikkel

2.5.2. A betörések jellemzői A támadók céljai alapján a támadások módja eltérő lehet. Az elérendő cél a módszereket meghatározhatja. A módszertől pedig függenek a támadás észlelhető jelei, amelyeket a támadás manifesztációjának is szoktunk nevezni [38]. Az adatkiszivárgás esetében maga az adat általában a támadó számára ismert helyen, ismert alhálózaton található. Ilyen esetben a támadó általában biztonsági rést keres az alhálózaton. Ha oda be tud törni, onnan már könnyebben eljut arra a gazdagépre, amelyen az adat ténylegesen található. Alhálózatokon belül ugyanis általában a munka megkönnyítése érdekében gyengébb védelmi megoldásokat alkalmaznak, mint az alhálózat és a világ többi része között [39]. Ebben az esetben a kívülről kivitelezett támadás jellegzetessége, hogy gyakran a támadó egy élő személy (nem automatizált program), és a támadás közvetlen célja az alhálózat biztonsági résének, réseinek módszeres felderítése [40]. Léteznek automatikusan működő támadó szoftverek is. A hálózaton terjedő rosszindulató


20

programokat viselkedésük, a fertőzés és a működés módja alapján több csoportba sorolják. Ezek közül az értekezés témájához kapcsolódóakat mutatja a 2.5. és a 2.6. táblázat. Gyakoriak az Interneten a különféle módon terjedő férgek (computer worm). Ezek kisebb része céltalan: a készítőik csak azért írták őket, hogy programozási tudásukat bemutassák. Nagyobb részük viszont kifejezetten olyan szándékkal fertőzi meg az általában otthoni felhasználók számítógépeit, hogy azokra hátsó kapukat (backdoor) helyezzen el. Ez lehetővé teszi azt, hogy később a fertőzött számítógépre be lehessen távolról jelentkezni, irányítani lehessen azt (compromised host), még akkor is, ha az eredeti biztonsági rést, amelyen keresztül a kártevő fertőzött, már kijavították [41]. A terjedés irányát a férgek többféleképpen választják ki. Vannak, amelyek egyszerűen hálózati címek véletlenszerű generálásával oldják ezt meg, de egyesek előnyben részesítik az alhálózaton belüli terjedést [39, 42]. A férgek egy csoportja hálózatot hoz létre, amelyet botnetnek neveznek [43]. Egy botnet akár több millió eltérített számítógépből is állhat. Ezek összesített erőforrásával, főként a hálózati kapacitásukkal egy központi irányító személy rendelkezik (botmaster), aki bérbeadja azt másoknak. Leggyakrabban levélszemét (spam) küldésére kap megrendelést. A milliós egyedszámú hálózat levélszemétküldő kapacitása akár naponta 60-70 milliárd levél is lehet [44]. Az eltérített gépek irányítását ritkán végzik központi szerveren keresztül. Ennél gyakoribb, amikor azok internetes csevegő hálózatra kapcsolódva (IRC, Internet Relay Chat) kapják a parancsokat [45, 46]. Ez számukra előnyös, mivel a protokoll egyszerű, könnyen implementálható, az IRC hálózatok pedig általában regisztráció nélkül igénybe vehetőek. Újabban azonban ehelyett a botnetet létrehozó szoftverbe egy alkalmazási szintű hálózatot létrehozó modul is kerül, amely P2P hálózatot épít [4, 47]. Ezek a szoftverek is általában Windows operációs rendszeren futnak, mert az a legelterjedtebb az otthoni felhasználók körében. Léteznek Unix alapú férgek is. Elterjedtek azok az SSH férgek [45], amelyek szokásos, esetekben adott Unix rendszerekben alapértelmezés szerint meglévő felhasználói neveken próbálnak belépni (root, mysql, info, admin, guest, paul, testing stb.) Ezek az adminisztrátori és felhasználói figyelmetlenséget használják ki, a túl egyszerűnek megválasztott vagy esetleg teljesen hiányzó jelszavakat. A terjedésük jellemző vonása, hogy egy kiválasztott gazdagépen több száz, ezer felhasználói név–jelszó párt próbálnak ki. Ezek a próbálkozások nem csak egy konkrét gazdagépet érintenek, hanem egy alhálózat szomszédos kiszolgálóit is. Ebbe a csoportba tartozik az első iPhone féreg is, az iKee [37].

2.5.3. A betörésérzékelés lehetőségei A betörésérzékelés (intrusion detection, ID) legkorábbi módja a felhasználói tevékenység megfigyelése volt [48]. Ekkor a szokatlan viselkedésekre tudtak felfigyelni. Ilyen pl. ha egy felhasználó szabadságon van, mégis be van jelentkezve. Az ilyen betörésérzékelés hátránya, hogy alkalmi jellegű és nem skálázható. A betörési kísérletek gyakorisága és változatos formája miatt szükségessé vált azok automatikus érzékelése. Ennek legfőbb akadálya az, hogy nem minden betörés jár együtt önműködően észlelhető, arra utaló jelekkel. Egy rendszer feljogosított felhasználója általi visszaélés például nagyon nehezen észlelhető. Manapság a betörésérzékelésnek három fő formáját használják:


21

Forgalmi adatminták vizsgálata. Ennek lényege, hogy a gazdagépek hálózati forgalmában bizonyos mintákat, adatcsomagokat keres az érzékelő rendszer. Ismert betörési módok esetén ez hatékony és pontos lehet. Hátránya viszont, hogy csak előzetesen ismert támadási formákra alkalmazható. Alkalmazási szintű hálózati protokollok vizsgálata. Ennél a módszernél az IP forgalomban nem csak mintaillesztést végeznek, hanem az alkalmazások által használt protokollokat megértve elemzik azokat. Az érzékelő az alkalmazáshoz hasonlóan megérti a protokollt, de a feladata csak annyi, hogy a nem megengedhető bejövő és kimenő adatokat vizsgálja. Rendellenességek felismerése (anomáliák érzékelése). Lényege, hogy a normális, üzemi körülményektől eltérő működést érzékelik. Előnye az előzőekkel szemben az, hogy nem kell előre ismerni a támadás kivitelezésének módját. Így akár egy újfajta, az érzékelő rendszer konfigurálásakor még ismeretlen támadás is detektálható. Azonban ennél gyakoribbak a hamis riasztások, mint az előbbieknél.

2.5.4. A betörésérzékelés helye A betörésérzékelő rendszereket működésük helye szerint két alapvető csoportra osztjuk: – önállóan működő rendszerek (HIDS, Host-based Intrusion Detection System) és – a hálózati betörésérzékelő rendszerek (NIDS, Network-based Intrusion Detection System) [49]. A legkorábbi automatikus érzékelők (sensor) egyedileg működtek, nem hálózatba kötve [50]. A betörésekre utaló gyanús jeleket önmaguk érzékelték és dolgozták fel; ha esetleg egy automatikus védelmi rendszer is kapcsolódott hozzájuk, az is csak az adott gazdagépet védte. Ennek a kialakításnak a hátránya, hogy a tapasztalatok, amelyeket az egyes érzékelők gyűjtenek, mindig helyben maradnak. A tapasztalatokat a különálló, nem osztják meg egymással, és így csak olyan betörések érzékelésére van mód, amelyeknél a támadás manifesztációja már helyben észlelhető. A hálózatba kötött érzékelés ezzel szemben lehetőséget ad arra, hogy a kiterjedt, hálózati szintű támadásokat is érzékelni lehessen. Ennek nehézsége abban áll, hogy az érzékelő hálózat növekedtével a feldolgozandó adatmennyiség is rohamosan növekszik [51].

2.5.5. Az érzékelt események közötti kapcsolat felismerése Az önállóan működő betörésérzékelő rendszerek az egyes gyanús eseményekről szóló figyelmeztetéseket, bár logikai kapcsolat van közöttük, egymástól függetlenül küldik. Ha egyszerre sok esemény történik, nem csak a valós és a hamis jelentések keverednek, de a feldolgozandó adat is kezelhetetlen mennyiségű lehet [51]. Az ember számára már nem feldolgozható mennyiség az elosztott esetben az adatok gépi, automatikus kezelését teszi szükségessé. A tapasztalatok hálózaton történő megosztása két fő kérdést vet fel. Az első, hogy az eltérő helyen keletkező tapasztalatok közötti összefüggéseket (attack correlation) hogyan ismerjük fel. A második pedig az, hogy hogyan szervezzük meg ezeknek a hálózaton történő


22

megosztását: milyen felépítésű legyen az a hálózat, amelyen megbízhatóan elvégezhető ennek a nagy mennyiségű adatnak a továbbítása akkor is, ha az azt alkotó egyedek esetleg éppen támadás alatt állnak. Az elemi események közötti kapcsolat felismerésére három módszert tárgyalnak az irodalomban [52]. – Az első csoportba tartozó módszerek az elemi eseményeket megegyező tulajdonságaik alapján csoportosítják; például azonos forrás cím vagy cél port. Ezek sokféle támadás esetén hatékonyak lehetnek, de az egyes események közötti ok-okozat összefüggést nem tudják felismerni. Ezen alapszik a SPICE rendszer [53] és így működik a CIDS is [54]. – A második lehetőség az egyes események előre definiált forgatókönyvbe történő illesztése. Ennek megvalósítására fejlesztették ki a LAMBDA nyelvet [55], illetve használnak az adatbányászatból átvett módszereket [56]. Ezek a módszerek csak ismert betörésfajták esetén működnek, vagyis akkor, ha a forgatókönyveket előzőleg szakértők megalkották. – A harmadik lehetőség a támadások előkészületeinek és következményeinek feltérképezése. Az előkészület egy olyan feltétel, ami a támadás sikerességéhez szükséges ; a következmény a támadás eredménye, ha az sikeres volt. Ha egy adott esemény előfeltétele létrejött egy előzőleg érzékelt esemény következményeként, akkor összefüggőnek tekinti az ilyen módon működő rendszer az eseményeket. A legkorábbi ilyen elven működő rendszer a JIGSAW volt [57]. Hátránya, hogy egy adott esemény érzékelésének elmulasztása esetén nem veszi észre az azt megelőző és az azutáni esemény közötti kapcsolatot. További hátránya lehet, hogy nem veszi figyelembe azokat a támadásokat, amelyek nem további, lehetséges eseményeket készítenek elő, és a sikertelen támadásokat sem. Az egyes érzékelt események egyszerű összekapcsolását az a gyakorlati probléma is akadályozza, hogy heterogén kimenetekkel rendelkeznek. Eltérő védendő rendszereknek eltérő sebezhetősége lehet; amelyik támadás az egyik helyen a rendszert teljesen megbéníthatja, az egy másik rendszerre nézve esetleg ártalmatlan [58]. Az eltérő érzékelő szoftverek kimenei között adatformátumbeli eltérések lehetnek, ami az összesített feldolgozást nehezíti. Az érzékelt események módszeres leírására fejlesztették ki az objektumorientált, XML alapú IDMEF üzenetformátumot [59], amelyet a széles körben elterjedt Snort [60] és Prelude [61] rendszerekben is használnak.

2.5.6. A betörésérzékelők közötti kommunikáció Az eltérő érzékelési pontokon keletkező adatok feldolgozásához kézenfekvő módszer lehet az adatok összegyűjtése és központi feldolgozása. A központi feldolgozó helyen így elméletben minden összegyűjthető információ rendelkezésre áll ahhoz, hogy ha a betörés elvben érzékelhető, akkor az érzékelést gyakorlatilag is elvégezzük – vagyis hogy a rendelkezésre álló adatok alapján a támadás tényét felismerhessük. Ennek a megoldásnak azonban két akadálya van: 1. A feldolgozandó adatmennyiség egy nagy forgalmú hálózat esetén már az önálló betörésérzékelő rendszernél is jelentős. Egy kiterjedt érzékelőhálózat által generált adatok mennyisége a hálózati forgalom, és a feldolgozáshoz szükséges számítási kapacitást tekintve hatalmas.


23

2. A központosított adatgyűjtés és feldolgozás továbbá egyetlen hibapontot (SPOF, single point of failure) jelent az elosztott érzékelő rendszernél. Előfordulhat, hogy egy támadó kifejezetten az érzékelő rendszert próbálja megbénítani [62]. A tapasztalatok megosztására ezért érdemes nem központosított, hanem elosztott hálózati architektúrát használni [40]. Az érzékelt eseményeket ezért érdemes elosztott rendszerben feldolgozni. Erre a feladatra az irodalomból a következő szakaszokban bemutatott eljárások ismertek. Nem strukturált P2P átfedő alapú érzékelők A DOMINO rendszer célja, hogy különböző típusú támadásokat, főleg vírusok és férgek aktivitásának érzékelését lehetővé tegye [63]. A hatalmas feldolgozandó adatmennyiséget három szintű hierarchikus, de nem strukturált P2P hálózattal kezelik. Ez részleges megoldást ad az érzékelő egyedek megbízhatatlanságára is. A legalsó szintű, kevésbé megbízható egyedektől csak óránkénti, vagy napi támadási statisztikákat fogadnak, például eseményszámokról, gyakoriságokról és típusokról szóló jelentéseket; ennél pontosabban specifikáltakat nem. A DOMINO rendszerben a méréseket, vagyis a támadások érzékelését nem csak valós hálózati címeken végzik, amely címekhez működő, kifelé szolgáltatásokat nyújtó kiszolgálók tartoznak; hanem olyan címeken is, amelyekhez nem. A szerzők tapasztalata szerint a nem létező címekre érkező bejövő támadások sokkal nagyobb valószínűséggel jelentenek támadást. Ennek oka a vírusok és férgek fertőzési mechanizmusában van ; azok ugyanis véletlenszerűen választják meg a támadás célpontját, gyakran olyan hálózati címet generálva, amelyhez nem is tartozik gép. A nem létező címekre irányított csomagok érzékelésével a hamis pozitív riasztások száma csökkenthető. A PROMIS védelmi rendszer (és elődje, a Netbiotic) a részben centralizált átfedő hálózatot építő JXTA keretrendszert használja az érzékelt támadások adatainak megosztására [64]. A PROMIS rendszerbe beépülő egyedek a többitől információt kapnak az érzékelt gyanús események számáról és az alapján automatikusan állítják át az operációs rendszer és a rendszerben telepített webböngésző biztonsági szintjét. Ez az eljárás általános védelmet ad a károkozó programok ellen, de egyben csökkentheti is a használhatóságot. A megközelítés hasonló a hétköznapi életből ismert járványok megelőzéséhez. Az Indra rendszer arra a feltevésre épül, hogy a támadók egy adott biztonsági rést kihasználva több számítógépet is megtámadhatnak [40]. Ha a kísérletet érzékelve az Indra rendszer résztvevői értesítik egymást, azzal a saját védelmüket erősíteni tudják. Az Indra rendszerben így a résztvevők konkrét, ismert támadók ellen tudnak védekezni. Struktúrált P2P hálózatra épülő betörésérzékelő rendszerek A CIDS rendszer a Chord DHT-t használja a betörések elosztott érzékelésére [54]. Az adatok kezelése az ún. „publish-subscribe” elven működik. Ez azt jelenti, hogy az egyes egyedek egy listában tárolják az általuk gyanúsnak vélt IP címeket, és az ezekről szóló jelentésekre feliratkoznak (subscribe) a hálózaton. Ha elegendő számú egyed iratkozott fel egy adott IP címmel kapcsolatos eseményekre, akkor támadónak tekintik azt, és értesítik a feliratkozott egyedeket. A DHT felhasználásával elvben a betörésérzékeléshez kapcsolódó feldolgozási műveletek okozta terhelés egyenletesen oszlik el a résztvevők között, de adott, konkrét támadótól


24

származó többszörös betörések esetén a feldolgozó egyed könnyedén leterhelhető. Mivel a Chord rekurzív útválasztást használ, ez a hálózat többi részét is ugyanannyira terheli. A BotSpot nevű rendszer az eddigiektől egészen eltérő, nem konkrét támadó ellen próbál meg védekezni, hanem botnetek érzékelését tűzte ki célul [65]. A szerzői egy új sémát dolgoztak ki, amelynek segítségével a rendszer a NetFlow formátumban gyűjtött adatoknak egy kis részéből is képes felismerni egy botnet működését a hálózaton [66]. Az adatokat egy DHT-ben tárolja el, így az érzékelés nem kelt nagy hálózati forgalmat. A BotSpot további előnye, hogy a használói számára névtelenséget nyújt; az átfedőbe küldendő adatoknak nem kell tartalmaznia információt a felhasználók (pl. egy intézmény) alhálózatáról vagy annak felépítéséről. A Spamwatch nevű rendszer nem betörések, hanem levélszemét (spam) szűrésére alkalmas, és a Tapestry hálózatra épül [67]. A program egy levelező alkalmazásba épülő bővítmény. Az egyes, felhasználók által levélszemétként megjelölt levelek adatait a rendszer egy DHTben tárolja; más felhasználóknál így ugyanaz az üzenet automatikusan törölhető. A DHT alkalmazása miatt a lekérdezés gyors és csak kis hálózati forgalmat generál. Sajnos a levélszemetet küldő programok gyakran alkalmazzák azt a módszert, hogy minden küldött levélben egy-két karaktert megváltoztatnak; ez a DHT-kban alkalmazott hasító függvények miatt a levelek összehasonlítását lehetetlenné teheti, és nagyban lecsökkenti a Spamwatch rendszer a hatékonyságát.

3. fejezet Betörésérzékelés strukturált P2P átfedőn

1. tézis. Kidolgoztam egy hálózati biztonsági eljárást (Komondor), amellyel a hálózat eltérő pontjain történő betörésérzékelések összesített tapasztalatait felhasználva javítható a gazdagépek védelme. [S1, S4, S7, S6, S8, S13, S14, S15] 1.1. altézis. Kifejlesztettem egy módszert, amellyel a különböző helyeken érzékelt betörési kísérletekből nyert tapasztalatok összegezhetők, és azokból egy értékelési eljárással elosztott adatbázis építhető. Bebizonyítottam, hogy a kidolgozott eljárás hatékony működésének feltétele, hogy az egyes csomópontokban működő példányok közötti kommunikáció egy DHT típusú átfedő hálózatra épüljön. [S1, S2, S4, S10, S11, S18, S19, S20, S21, S23] 1.2. altézis. Igazoltam, hogy a DHT átfedőre épülő betörésérzékelés során létrejövő hálózati forgalmat a Kademlia hálózat hatékonyabban kezeli, mint az egyéb ismert DHT átfedők. [S8, S10, S15, S21, S22]

A 2.5.4 és 2.5.5. szakaszban bemutatott hálózati betörésérzékelő rendszerek működése azon alapul, hogy a hálózat több pontján érzékelt események között összefüggések lehetnek, és ezek felderítése a hálózatot érő támadások felismerésére ad lehetőséget. Az érzékelők hálózatba kötése azonban terheléselosztási és megbízhatósági problémákat vet fel. Gyakran még az egy érzékelőtől érkező adatok feldolgozásához szükséges számítási kapacitás is jelentős. Az elosztott betörésérzékelés hatékonyan ezért nem működhet központosított feldolgozással. Ez a fejezet egy olyan eljárást mutat be, amellyel a betörésérzékelés során keletkező nagy mennyiségű adat hatékonyan feldolgozható. Az eljárás lényege, hogy az érzékelő egyedek egy strukturált P2P alapú átfedő hálózatot hoznak létre, amely a betörések adatait tárolja. Ezzel az érzékelés és feldolgozás okozta terhelés hatékony elosztása valósítható meg. A P2P hálózatok nagyfokú stabilitása biztosítja, hogy a rendszer működőképes maradjon akkor is, ha az egyes résztvevői távoznak vagy kiesnek az átfedőből. A nagyfokú összekötöttség és az elosztott feldolgozás miatt a rendszer az egyetlen hibapont problémáját is megkerüli. Az érzékelés és az adatok megosztása okozta hálózati terhelés tovább csökkenthető a bemutatott eljárás szerint azzal, hogy az érzékelő rendszert egy Kademlia alapú átfedőre 25

3. FEJEZET. BETÖRÉSÉRZÉKELÉS STRUKTURÁLT P2P ÁTFEDŐN Fogalom

Meghatározás

gyanús esemény

Elemi, észlelhető események, amelyek egy támadás részeként érzékelhetőek. Önmagukban nem feltétlenül jelentik azt, hogy egy hálózat vagy gazdagép ténylegesen támadás alatt áll.

támadás

Tényleges betörések; azok az esetek, amikor bizonyosak vagyunk afelől, hogy egy külső személy hozzáférést kísérelt meg megszerezni a hálózat valamelyik gazdagépéhez, vagy akadályozni próbálta azok működését.

26

3.1. táblázat. Az elosztott betörésérzékelés fogalmai

építjük. Ennek iteratív útválasztási eljárása ugyanis jobban illeszkedik az érzékelt események, és így az átfedőben keletkező adatforgalom dinamikájához.

3.1. Az elosztott érzékelés jellegzetes problémái Az elosztott betörésérzékelés tárgyalásához a 3.1. táblázatban szereplő gyanús esemény és támadás fogalmakat használom. Általában több gyanús esemény közösen utal egy támadásra. Támadás például az, amikor egy féreg jelszavak próbálgatásával próbál meg egy számítógépre betörni. A gyanús események ebben az esetben a helytelen felhasználói név-jelszó párosok, amelyeket a program generál. Egy helytelen jelszó önmagában még nem jelent támadást, hiszen az származhat a rendszer egy feljogosított felhasználójától is, aki tévesen gépelte azt be. Jelen esetben a gyanús események ismétlődése utal a támadásra. Az érzékelt események közötti kapcsolat felderítése A gyanús eseményeket egy konkrét érzékelő észleli. Egyetlen gyanús esemény nem feltétlenül utal támadásra; gyakran több esemény együttese jelenti a támadás manifesztációját. A különféle, de egymással összefüggő események a hálózat különböző pontjain is történhetnek, vagyis más-más érzékelő észlelheti őket. Az egymással összefüggő eseményeket valamilyen módon kapcsolatba kell hozni. Ez ismert támadási forgatókönyvek esetén könnyen mehet: ha ismert ugyanis a forgatókönyv, akkor annak egyes elemeit, lépéseit felismerve összeállhat a támadás képe, még akkor is, ha azokat különböző helyeken érzékeltük. Ismeretlen forgatókönyv esetén is adódhat erre lehetőség, például az azonos IP forráscímhez köthető, de akár eltérő helyeken észlelt gyanús események esetén. Az elosztott érzékelés, vagyis a hálózat különböző pontjain gyűjtött adatok együttes feldolgozása lehetőséget ad a hálózati szintű támadások felismerésére. A több helyen történő érzékelés és feldolgozás a következő problémákkal szembesít minket: 1. nagy mennyiségű, sokszor felesleges adat, 2. a döntéshozatalhoz elégtelen adatok,

3. FEJEZET. BETÖRÉSÉRZÉKELÉS STRUKTURÁLT P2P ÁTFEDŐN

27

3. heterogén érzékelők eltérő formátumú kimenete, 4. az érzékelők és a feldolgozók közötti kommunikációs problémák, 5. megbízhatósági problémák, 6. gyakran változó támadás típusok, forgatókönyvek. A feldolgozandó adatok mennyisége A betörésérzékelés önállóan működő érzékelők is kompromisszumokat igényel, főleg a feldolgozandó adatmennyiség terén. Minél több adatot gyűjtünk, és próbálunk meg elemezni, annál nagyobb számítási kapacitásra lesz szükség – és természetesen annál nagyobb lesz a feleslegesen gyűjtött adat mennyisége. A kevés adat pedig azt eredményezheti, hogy bizonyos támadásokat a rendszer nem érzékel. Ez elosztott esetben többszörösen is igaz: a feleslegesen gyűjtött adat nem csak a feldolgozást lassítja, hanem a hálózatot is terheli. A gyűjthető adatokat ezért a következők alapján érdemes csoportosítani: 1. Olyan események adatai, amelyek önmagukban, a hálózat egy pontján érzékelve már betörésre utalnak. Ezek feldolgozását felesleges egy elosztott rendszerre bízni, ha az helyben is elvégezhető. A veszélyről ettől függetlenül az elosztott rendszer összes résztvevőjét érdemes értesíteni. 2. Olyan események adatai, amelyek önmagukban nem utalnak támadásra; de több, különféle helyről gyűjtve, és globálisan értelmezve az adatokat, egy hálózati szintű támadásról kaphatunk képet. Az elosztott érzékelő rendszerek mindkét esetben hasznosak lehetnek. Az első esetben a támadás felismerése után a riasztást az elosztott rendszeren hamar el lehet juttatni a többi résztvevőhöz; a második eset pedig olyan támadásokat jelent, amelyeket csak az adatok globális értelmezésével deríthetők fel. Ez azt jelenti, hogy ha érzékelni szeretnénk ezeket a támadásokat, akkor az azokkal esetleg kapcsolatba hozható gyanús eseményeket is globálisan kell feldolgoznunk. Az események értelmezése A betörésekre utaló jeleket sokszor csak a megtámadott rendszerben lehet érzékelni. Például egy bejelentkezési kísérletnél csak az adott rendszer tudja meghatározni, hogy az adott felhasználói név–jelszó páros helyes, vagy helytelen. Az érzékelést ezért leghatékonyabb a végpontokon elvégezni. Az egyes végpontokon érzékelt események értelmezése azonban függ a végpont típusától is. Egy „hiányzó fájl” hibaüzenet eltérő rendszerek, alkalmazások, szolgáltatások esetén más-más fontosságú lehet. Ha egy webkiszolgáló nem talál egy fájlt, esetleg csak annyi történt, hogy egy felhasználó tévesen gépelte be annak nevét. Viszont ha egy tűzfal konfigurációs fájlja hiányzik, az nagyon fontos esemény lehet.


28

KOMONDOR P2P

P2P DHT

DHT modul jelentésfeldolgozó modul

- Snort - Prelude -…

védekező modul

- tűzfal - alkalmazási szintű védelem -…

érzékelés lehetőségei

- hosts.deny - szolgáltatás leállítása -…

védekezés lehetőségei

3.1. ábra. A Komondor eljárás működése

3.2. A Komondor elosztott betörésérzékelő eljárás A kidolgozott betörésérzékelő eljárás elnevezése Komondor, az ismert kutyafajtáról, amelyről azt mondják, először harap, csak azután ugat (vagyis értesíti a többi kutyát). A kifejlesztett eljárás működésének lényege, hogy a betörésérzékelésben résztvevő egyedek egy strukturált P2P átfedőt hoznak létre. Ez az átfedő szolgál arra, hogy az érzékelt gyanús eseményekről szóló adatokat megoszthassák egymás között, ahogyan az a 3.1. ábrán is látható. Az átfedő fenntartásához kapcsolódó teendők mellett minden egyednek feladata a gyanús események érzékelése. Az érzékelésnek ki kell terjednie az olyan eseményekre is, amelyek önmagukban nem utalnak támadásra, de a velük kapcsolatba hozható egyéb eseményekkel együtt igen. Ezeket a gyanús eseményeket, tapasztalatokat az érzékelő egyedek az átfedőben eltárolják. Ha az összegyűlt adatok alapján arra a következtetésre jutnak, hogy a gyanús események együtt egy támadást jelentenek, akkor egy riasztást indítanak el az átfedőn; értesítve az összes résztvevőt a támadás tényéről. Az átfedő létrehozásának célja a támadások hatékony érzékelése és a riasztások továbbítása, ugyanakkor a védekezés az egyedek saját feladata. A gyanús események előfeldolgozása A gyanús eseményeket, mint tapasztalatokat az átfedőben történő tárolás előtt az egyedek saját maguk feldolgozzák. A hálózati forgalom csökkentése megkívánja, hogy a legtöbb, elosztott


29

érzékelés szempontjából lényegtelen információt eldobjuk. Egy eseménynek van azonban két olyan tulajdonsága, amelyet meg kell tartani: 1. Az események közötti kapcsolatot megteremtő információ. Ennek neve a kulcs. Ez az esemény egy olyan saját, vagy az eljárásban hozzárendelt tulajdonsága, amely segítségével egy később felismert támadással kapcsolatba hozható. 2. A védekezés alapjául szolgáló információ. Ennek segítségével támadás felismerése esetén az egyedek a felismert támadó ellen védekezni tudnak. A kapcsolatot megteremtő információ többféle is lehet. Egy gyanús esemény különféle támadási forgatókönyvekben szerepelhet; ebben az esetben több kulcs rendelhető hozzá. A védekezés alapjául szolgáló tulajdonság ismerete adja meg a lehetőséget az átfedő egyedei számára, hogy automatikusan védekezni tudjanak a felismert támadó ellen. Ha nincsen ilyen, az adott támadó elleni védekezés nem lehet automatikus; esetleg a rendszergazda értesítése, statisztikák készítése vagy ehhez hasonló tevékenységek elképzelhetőek. A kulcsra és a védekezés alapjául szolgáló információra közös példa a támadó IP címe, ha az ismert. Ez megteremti a kapcsolatot a különböző helyeken ismert, de összefüggő események között (ugyanattól a támadótól származnak). Továbbá, a védekezés alapjául is szolgál: a felismert támadó ellen az egyedek a tűzfalaik segítségével védekezni tudnak. Az eljárásban az IP cím alapján választott kulcs mellé egy büntető pontszámot is kell rendelni az átfedőben eltárolt eseményekhez. Ezzel a pontszámmal az érzékelő egyed osztályozza az eseményeket, azok fontosságátől és jelentőségétől függően az esetleges támadás szempontjából. A fontos események magas, a jelentéktelen események pedig alacsony pontszámmal rendelkeznek. A gyűjtő egyed ezen pontszámok összegézésvel értelmezi a tapasztalatokat, figyelve, hogy az összegük elért-e egy küszöbértéket. A pontszámokat az események típusától függően kell meghatározni. Kifinomultabb támadások esetén az IP cím vizsgálatánál bonyolultabb kulcshozzárendelésre van szükség. Fontos, hogy az egymással esetleg összefüggő eseményekhez ugyanazt a kulcsot rendeljék az egyedek, ugyanakkor a kulcs hozzárendelése önmagában még nem jelenti a kapcsolat felismerését, csak egy feltételezett lehetőséget. A kulcs lehet egy másik, események közötti kapcsolatot felismerni hivatott eljárás, pl. a JIGSAW [57] által hozzárendelt azonosító is. Így mód van arra, hogy a Komondor jelentésfeldolgozó moduljába egy másik eljárást építsünk, lehetővé téve azt, hogy annak bemenő adatait egy Komondor rendszer több érzékelővel gyűjtse. A kulcsok hozzárendelésére a 3.3.1. szakasz mutat példákat. A hálózati forgalom csökkenthető, ha a rövid időn, egy időablakon belül érzékelt eseményeket egyetlen üzenetbe gyűjtik az egyedek. Ez is az események előfeldolgozásának részét képezi. Az időablak mérete kompromisszum függvénye. Túl rövid időablak esetén nem csökken a hálózati forgalom, túl hosszú esetén pedig az egyedeket értesítő riasztás késhet. A támadás típusától, forgatókönyvétől függ, hogy milyen események csoportosíthatóak így, és mekkora időablakban.

3.2.1. Strukturált átfedő használata az események eltárolásához Az érzékelt és előfeldolgozott tapasztalatokat az egyedek eltárolják az átfedőben. A strukturált P2P átfedők a 2.1.2. szakaszban tárgyaltak alapján kulcs-érték párokat tárolnak. A Komondor


30

1. támadó

2. támadó 1. gyűjtő

2. gyűjtő

3.2. ábra. A strukturált átfedő használata a Komondor eljárásban

eljárás lényege, hogy a gyanús eseményekhez generált kulcsokat, amelyek a lehetséges kapcsolatokat jelzik a különféle helyeken érzékelt eseményeknél, egyben a strukturált átfedőben történő eltárolás kulcsaként is kell használni. Az érték a gyanús eseményhez tartozó összes többi információ lesz. Az egymással esetlegesen összefüggő eseményekhez az egyedek azonos kulcsot rendelnek. A strukturált átfedőkben az eltárolás kulcsának hasító függvény szerinti értéke határozza meg azt, hogy a tárolás során melyik egyedhez kerül. Mivel az egyedek ugyanazt a hasító függvényt használják, az egymással összefüggő gyanús események adatai ugyanazon kulcs választása miatt az átfedőben egy egyedhez fognak kerülni, ahogyan az a 3.2. ábrán is látható. Így az eljárás biztosítja azt, hogy a kulcs által meghatározott egyed a lehető legnagyobb tudással rendelkezzen az átfedő egyedeit érintő eseményekről, és ezért képes lehet felismerni a támadást. Ezt az egyedet a továbbiakban gyűjtő egyednek nevezem. A strukturált átfedő választását indokolja, hogy a gyűjtő egyed jelenléte miatt a központosított hálózatok előnyei az elosztott esetben is érvényesülnek. Az érzékelt adatokat az átfedőben a kulcs által meghatározott gyűjtő egyednek kell csak elküldeni. Nem strukturált átfedővel ez nem lenne megvalósítható, hiszen azokban nincsen olyan globális szabály, amellyel az egyes érzékelések feldolgozása megadott egyedekhez lenne rendelhető. Továbbá, a rendszert ért többszörös támadások esetén a hálózat terhelése jobban megoszlik a hasító függvények tulajdonságai miatt, a 3.3.3. szakasz mérési eredményei alapján is láthatóan. A strukturált átfedő megoldja az egyszeres hibapont problémáját is. Ha a gyűjtő egyed kiesik, az átfedő topológiája átszerveződik, és más helyre fognak kerülni az ugyanazzal a támadóval kapcsolatba hozható események. Az érzékelt támadás esetén a riasztás gyorsabb és hatékonyabb lehet a strukturált esetben, mint egy nem strukturált átfedő használata esetén. Az átfedő kis átmérője miatt ugyanis az üzenetszórás rövid idő alatt elvégezhető. A strukturált átfedőtől igényelt szolgáltatások Az egyedek az átfedőt nem a megszokott módon, eltárolás és kikeresés műveletekkel használják. A Komondor eljárás megvalósításához szükség van a strukturált átfedőben az eltárolás műveletének megvalósítására; ez kell ahhoz, hogy ugyanazon egyednél tárolódjanak a külön-


31

böző helyeken érzékelt adatok. Nincsen szükség viszont a kikeresés műveletének megvalósítására. A gyanús események adatait ugyanis az egyedeknek nem kell tudniuk visszakeresni. Emiatt az átfedők összehasonlításakor az eltárolással kapcsolatos műveleteket, illetve azokkal kapcsolatos optimalizálási lehetőségeket kell figyelembe venni. A beérkező adatokat a gyűjtő egyed dolgozza fel. Ennek felelőssége a feldolgozáson kívül az is, hogy érzékelt támadás esetén riasztást kezdeményezzen az átfedőn. A támadásról így minden egyedet értesíteni tud, amelyek ezután a konkrét védelmi lépéseket maguk teszik meg. A gyűjtő egyednek nem feladata minden egyes egyedet külön értesítenie, vagyis nem maga kell küldje az összes többi egyednek a riasztást. Erre a feladatra egy üzenetszórás alkalmas az átfedőben, amelyre elosztott és skálázható algoritmust lehet használni. Egy ilyen az 5. fejezetben kerül bemutatásra.

3.2.2. A Kademlia átfedő használata a Komondor eljárásban A Komondor eljárásban az egyedeknek a Kademlia átfedőre épülő hálózatot kell létrehozniuk, ugyanis ez igazodik legjobban a támadások esetén generált hálózati forgalomhoz. Ennek oka a következőkben keresendő. Azoknál a hálózati szintű támadásoknál, amelyek csak több érzékelő által gyűjtött adatok összesítésével ismerhetőek fel, a gyanús események adatait is el kell tárolnunk az átfedőben. Ez az átfedőben jelentős forgalmat generál, amely nem csak az érzékelő és a gyűjtő egyedet, hanem a közöttük lévő útvonalon a többit is terheli. Ha a gyanús események ugyanazon támadáshoz, támadóhoz köthetőek, vagy egyéb módon kapcsolódnak egymáshoz, akkor a Komondor eljárásban ugyanazt kulcsot kell generálni hozzájuk. Az átfedőbe küldött eltárolás üzenetek eloszlása emiatt egy konkrét támadásnál nem lesz egyenletes; több, egymás utáni üzenet ugyanazt a kulcsot tartalmazza, és az érzékelők ugyanahhoz a gyűjtő egyedhez küldik azokat. A P2P átfedők összehasonlításakor felismertem azt, hogy ebben az esetben a Kademlia használatával az üzenetek száma, vagyis a fizikai hálózat forgalma igen erősen csökkenthető. Ennek legfőbb oka az, hogy az egyedek útválasztási táblázataiban a Kademlia esetén bármely más egyed szabadon elhelyezhető, a protokoll előírásait betartva. Erre a Tapestrynél és a Kademliánál van lehetőség. Más átfedők, pl. a CAN és a Chord szabályai ennél merevebbek, így azoknál az útválasztás nem tudja figyelembe venni, ha több egymás utáni üzenetet kell elküldeni, amelyek forrás és cél egyede ugyanaz. (Egyéb alkalmazásoknál, pl. fájlcserélőknél az ilyen jellegű forgalom ritka, hiszen az egyedek nem tárolják el, és nem is keresik ki többször rövid időn belül ugyanazt a kulcsot.) Az esemény eltárolásának hatására keletkező üzenetek számát összehasonlítottam. Ezt mutatja be a 3.2. táblázat a Chord és a Kademlia esetén. A Kademliánál protokollüzenetnek nevezek minden átfedőn belül küldött üzenetet. A hasznos tartalommal rendelkező üzenetek pedig ezek azon részhalmaza, amelyek egy gyanús esemény adatát is tartalmazzák. A Chord esetén nem tehetünk ilyen megkülönböztetést; ott minden üzenet tartalmazza a gyanús esemény adatait is, mivel az üzenet célba juttatásában több egyed is szerepet vállal. A Chordban egy gyanús esemény elküldése esetén az átfedőben O(log2 N ) számú üzenet keletkezik, ahol N az átfedő mérete. A küldő egyednek ebben a célról nincsen tudomása, csak a szomszédairól. A Kademlia esetén viszont a küldőnek először meg kell keresnie a cél IP címét, ehhez elvileg O(log2 N ) számú lekérdezés, vagyis ugyanennyi protokollüzenet szükséges;

3. FEJEZET. BETÖRÉSÉRZÉKELÉS STRUKTURÁLT P2P ÁTFEDŐN Átfedő

Chord

Kademlia

Útválasztási eljárás

rekurzív

iteratív

Egyed megkeresése

0

O(log2 N )

Első tartalom küldése

O(log2 N )

O(1 + log2 N )

n tartalom küldése ugyanan- O(n · log2 N ) nak az egyednek

O(n + log2 N )

Üzenetenkénti átlag, ha az üze- O(n · log2 N )/n net célja ugyanaz az egyed

O(N + log2 N )/n

Protokollüzenetek számának O(log2 N ) határértéke, ha n → ∞

O(1)

32

3.2. táblázat. A protokollüzenetek számának alakulása strukturált átfedőkben

utána pedig még +1 üzenet ahhoz, hogy a tényleges tartalmat eljuttassa a célhoz. Ha egynél több gyanús esemény adatait, azaz több hasznos tartalommal rendelkező üzenetet is kíván küldeni ugyanannak az egyednek, akkor többször már nincsen szükség annak kikeresésére. Így n darab tartalommal rendelkező üzenet küldése esetén az összes protokollüzenetek száma n+O(log2 N ) lesz, szemben a Chorddal, amelynél mind az n tartalommal rendelkező üzenetnek végig kell haladnia az O(log2 N ) hosszúságú láncon. Emiatt a Kademlia esetén, ha ugyanaz az üzenet feladója és célja, akkor az üzenetküldéshez gyanús eseményenként határértékben O(1) számú protokollüzenet szükséges. Mindez amiatt is lehetséges, mivel a Kademlia átfedőben bármelyik egyed szabályosan, a protokoll előírásainak megfelelően elhelyezhető bármely másik útválasztási táblázataiban. Az útválasztási táblázatok a távoli egyedeket távolságuk nagyságrendje szerint rendezik a kvödrökbe. Az egyes k-vödrökbe azonban az adott részfákból bármely egyedeket kiválaszthatjuk, az útválasztás mindig működőképes és helyes lesz. Vagyis egy tetszőleges A egyed esetén bármely B egyedet tartalmazhatja A útválasztási táblázata, a d(A, B) = A ⊗ B távolság alapján; így ez igaz lesz bármelyik érzékelő és gyűjtő párosra is. Hasonló a helyzet a Tapestry átfedőnél is. A megismert, kulcs alapján kijelölt egyed a címének első számjegyei (prefixe) alapján elhelyezhető a küldő útválasztási táblázataiban, így a későbbi kommunikáció közvetlenül az egyedek között is történhet az átfedő protokollüzenetei formájában. Az útválasztási táblázatok ilyen szervezéséhez mind a Tapestry, mind a Kademlia átfedők protokolljai útmutatást adnak arra, hogy a táblázatokba azonos helyre kerülő egyedek közül melyeket kell elhelyezni. A Kademlia átfedőben a régebb óta ismert egyedeknek van elsőbbségük [11], abból a tapasztalatból kiindulva, hogy azok megbízhatóbbak. A Tapestry átfedőben pedig a jelölt új egyed felé mért hálózati késleltetési időt (round trip time, RTT) hasonlítják össze [68]. Gyorsabb kapcsolatot választva ugyanis az átfedő egészének működése gyorsul. A Komondor szempontjából az az előnyös, ha az útválasztási táblázatokban olyan egyedek vannak, amelyeknek gyakran kell adatot küldeni. Ezeket a támadások eseményeihez hozzárendelt kulcsok határozzák meg. A fenti legrégebbi egyed (Kademlia), és leggyorsabb egyed (Tapestry) kiválasztási mechanizmust ezzel helyettesíthetjük a Komondor esetében. Látszólag ez biz-


33 7

6

10k

5 1k 4 100

érzékelők száma

átlagos eseményszám érzékelőnként [db]

100k

3 10

2

1

1 1

10

100

1000

10000

100000

időtartam [s]

3.3. ábra. Helytelen jelszavak gyakorisága egyes támadások esetén a támadás időtartamának függvényében

tonsági kockázatot jelent az átfedő működésére nézve, de fontos az, hogy az így kiválasztott egyedek az eltárolt adatok kulcsaitól függenek. Ezeket pedig maguk a Komondor egyedek rendelik hozzá, még ha az események alapján is. A biztonság növelése úgy valósítható meg, ha az adatok küldéséhez (kulcs-érték párok tárolása) egy gyorsítótárhoz hasonló kiegészítő útválasztási táblázatot használunk, amelyet az egyed kikeresésekhez nem. Ez a módosítás csak az üzenetküldéseket érinti, az üzenetek fogadását nem. A Kademlia a fentiek miatt ebben a betörésérzékelő alkalmazásban kevesebb üzenetet generál a fizikai hálózaton, mint más átfedők. A Kademlia esetében az útválasztási táblázatok mérete kisebb mint a Tapestry táblázatai, és azok fenntartása kevésbé költséges művelet [69, 70]. A működés közben, események miatt keletkező forgalom O(1) költséggel kezelhető. A gyanús eseményenkénti pontosan egy üzenet az érzékelő és a gyűjtő egyed közötti közvelten kommunikáció miatt az átfedő méretétől független, így nagytérségi alkalmazás, vagyis nagyméretű átfedők esetén a Kademlia használata különösen indokolt.

3.2.3. Az eljárás hatékonyságának igazolása A Komondor eljárás hatékonysága valódi átfedők segítségével érzékelt betörési kísérletek vizsgálata alapján igazolható. Ilyen mérési eredményt mutat be a 3.3. ábra, további eredményeket pedig a 3.3.3. szakasz. A 3.3. ábra SSH kiszolgálókon érzékelt, hibásan megadott jelszavakat mutat [45]. Minden


34

pont egy támadást, azaz egy vagy több gyanús eseményt jelent, amelyek egy támadó IP címtől származnak. Az y tengelyről az események, vagyis a hibásan megadott jelszavak száma olvasható le. Egy támadáson belül a legelső és a legutolsó esemény között eltelt idő, azaz a támadás időtartama pedig az x tengelyen látható. Az egyes támadók tevékenységét több Komondor érzékelő egyed is rögzítette. A támadókat érzékelő egyedek számát a pontok színe mutatja. Feketék azok, amelyeket csak egy egyed rögzített, a többi pedig színes. Több érzékelő egyed esetén az események száma egy érzékelőre vonatkozik, azaz el van osztva az érzékelők számával. Ebben az esetben így adódik az y tengelyen látható átlagos eseményszám. Az egy érzékelőt érintő (feketével jelölt), és a több helyen érzékelt (színekkel jelölt) támadások jól láthatóan elkülönülnek egymástól. Az egy helyen érzékeltek jelentős hányadának eseményszáma alacsony. Az 1100 ábrázolt támadásból 450 darab az (1; 1) pontban jelenik meg. Ezek valószínűleg emberi kéztől származnak, tévesen beírt jelszó miatt. A több érzékelő által rögzített támadások pedig programtól származnak. Az ilyenek szótár alapú támadásra utalnak, ahogyan az a részletes naplófájlokból ellenőrizhető is. Ezen mérési adatok alapján a Komondor eljárásban az elosztott betörésérzékelés, és annak egy Kademlia alapú DHT hálózatra történő megvalósítása az alábbiak szerint indokolt. – Az érzékelt támadások jelentős részét nem csak egy, hanem több szomszédos Komondor egyed is rögzítette, vagyis ugyanazon támadók több gazdagépre is megpróbáltak betörni. Emiatt a tapasztalatok megosztásával az elosztott betörésvédelmi rendszer hatékonyan képes erősíteni a támadások elleni védelmet. – Az érzékelések a hálózat különböző pontjairól származnak. Egy támadáshoz akár 1 000– 10 000 érzékelt esemény is tartozhat, amelyeket az elosztott hálózatnak tárolnia kell, és azok feldolgozását is biztosítania kell. Az eseményekhez rendelt kulcsokkal a tárolás hatékonyan egy DHT alapú átfedőben végezhető el. Így az összetartozó események egy egyedhez kerülnek, a többinek pedig nem jelent ez terhelést. Jelen esetben a kulcsok a támadók IP címei voltak. – Az érzékelő egyedeknek a Kademlia útválasztási eljárása esetén elegendő csak egyszer lekérdezniük az átfedőtől tároló egyed helyét. Az első esemény után minden egyes további tapasztalatmegosztásnál már elkerülhető az újabb lekérdezés.

3.3. A Komondor eljárás alkalmazási lehetőségei A Komondor eljárás valós környezetbeli hatékonysága a kulcsok helyes megválasztásától függ. Ha két eltérő helyen keletkező eseményhez nem sikerül az egyedeknek azonos kulcsot hozzárendelni, akkor azok nem fognak ugyanazon gyűjtő egyedhez kerülni, és így a közöttük lévő kapcsolat felismerése is meghiúsul. A kulcs hozzárendelése történhet az esemény valamely saját tulajdonsága, pl. a forrásának IP címe alapján. Az általam megvalósított, 3.3.2. szakaszban bemutatott Komondor rendszerben így történik az adatgyűjtés. Ezzel a módszerrel különféle féregprogramok aktivitása, pásztázások és adatbázis-kiszolgálók elleni támadások is észlelhetőek. Egyes esetekben a mért adatok alapján meghatározható az is, hogy az események emberi kéz, vagy valamilyen program működése nyomán keletkeztek. Az IP cím alapú érzékelés előnye, hogy egyben a védekezéshez

3. FEJEZET. BETÖRÉSÉRZÉKELÉS STRUKTURÁLT P2P ÁTFEDŐN típus

cél

horizontális

Több gazdagépet, de csak egy kaput érint. Valószínűleg a támadó hibásan konfigurált szolgáltatást keres az alhálózaton, amelyen keresztül betörhet a rendszerbe.

vertikális

Több kaput, de egy gazdagépet érint. A támadó egy konkrét gazdagép szolgáltatásait térképezi fel.

vegyes

Elosztott pásztázás több forrásból. Előfordulhat, hogy távolról a rendszert igyekeznek leterhelni, hogy működésképtelennél váljon.

35

3.3. táblázat. Kapupásztázások típusai [63] alapján

szükséges információt is tartalmazza. Hátránya, hogy könnyen kijátszható a támadók által, és ezért a kulcsok hozzárendeléséhez más megoldásokat is szükséges lehet használni.

3.3.1. Kulcsok választása a Komondor eljárásban Kifinomultabb támadások esetén a kulcsok hozzárendelése nem végezhető el olyan egyértelműen, mint az egy IP címről érkező támadások esetében. Az események közötti kapcsolat felismerésére az irodalomban többféle módszert is bemutatnak. A Komondor eljárás előnye az, hogy az említett módszerek számára az adatgyűjtést elosztott módon tudja elvégezni ; vagyis hogy ezen módszerek elosztottan is alkalmazhatóvá válnak. A valószínűsíthetően összetartozó eseményekhez rendelt közös kulcs célja, hogy a gyűjtő egyedek megkapják az egyes érzékelő egyedeknél keletkezett események adatait. A Komondor eljárásba beépíthetjük az irodalomban tárgyalt összetettebb kapcsolatfelismerési módszereket is. Ez azt jelenti, hogy a beérkező események alapján a gyűjtő egyed a beépített módszert, pl. a JIGSAW eljárást [57] megvalósítva végzi el a kapcsolatfelismerést. Az érzékelő egyedek jelentésfeldolgozó moduljai pedig az egyes eseményekhez hozzárendelik azon JIGSAW eljárásbeli forgatókönyvek neveit kulcsként, amelyekben az adott esemény szerepelhet. Ilyen esetben a gyűjtő egyedek úgy viselkednek, mintha központi kiszolgálók lennének, amelyek a JIGSAW eljárást valósítják meg. Előny viszont, hogy a DHT átfedő terheléselosztást valósít meg, és a gyűjtő egyed kiesése esetén automatikusan átkerül a gyűjtés felelőssége egy másik egyedhez. A Komondor hasznossága az egyes támadástípusok esetén eltérő. Ha a támadó IP címe azonosítható, akkor a védelem könnyedén kialakítható egy tűzfal segítségével. Más esetekben előfordulhat, hogy csak a támadás ténye ismerhető fel. A 3.3. táblázatban összefoglalt, DOMINO rendszerben dokumentált pásztázások [63] esetén a kulcshozzárendelés és az eljárás hasznossága a következőképpen alakul: – Horizontális pásztázás esetén a támadásokat különböző gazdagépek érzékelik, de a pásztázott kapu (port) mindegyiküknél ugyanaz. Ebben az esetben a kapu száma lehet a kulcs. Ha a gyűjtő egyed megkapja a jelentéseket, össze tud állítani egy feketelistát azokról a támadókról, akik a megadott típusú támadást indították. A többi Komondor egyed kifejezetten ezek ellen tudja védeni a megtámadott szolgáltatást.


1

0

0

1

hunor

nemere

0

1

0

1

1

0

fajsz

1

buda

jutas

0

0

horka

0

1

rockford

0

1

turul

0

36

1

monolit kende

fermi

0

0 1

3.4. ábra. A méréseket végző Komondor P2P hálózat

– Vegyes pásztázás esetén a támadás alatt álló alhálózat címe lehet a kulcs. A különböző helyekről érzékelt támadások adatait összegyűjtve a gyűjtő egyed képes felismerni, hogy az alhálózat különböző részeit elosztott támadások érték. Az egyedek így értesülnek arról, hogy nem csak maguk, hanem az egész alhálózatuk támadás alatt áll. – Vertikális pásztázás esetén egy gazdagép áll támadás alatt, és ez érzékeli a támadást. A támadás forrása is ugyanaz, vagyis a támadó konkrétan azonosítható. A kulcs ilyenkor a támadó IP címe lehet, bár valószínűsíthető, hogy eseményeket csak egy érzékelő fog rögzíteni. A DHT ilyen esetben a riasztások továbbítására használható.

3.3.2. A Komondor rendszer mérési összeállítása Az elosztott, DHT alapú betörésérzékelés valós körülmények között történő teszteléséhez megvalósítottam a Komondor rendszert. Ez a betörésérzékelő alkalmazás a 3.2. alfejezetben bemutatott eljárások implementációit tartalmazza. A teszt változat C++ nyelven íródott. Elsőként Linux operációs rendszeren futott, később átültettem Windows rendszerre is. Az elemi események érzékelését a Snort program végezte [60]. Az alkalmazás implementálásával és egy saját átfedő létrehozásával lehetőség nyílt arra, hogy az eljárás valós környezetben történő működését értékelni lehessen. A telepített változatához készítettem egy PHP-ban írt monitorozó felületet is, amelynek segítségével Web böngészőben lehetett nyomon követni az átfedő állapotát (3.4. ábra) és az átfedőben eltárolt adatokat. Ez képes statisztikákat készíteni az érzékelt betörési kísérletek-


37

ről. A 3.3.3. szakaszban bemutatott statisztikák is azokat a betörési kísérleteket mutatják, amelyeket a Komondor alkalmazás rögzített. A Komondor teszt hálózat három éven keresztül végzett adatgyűjtést. Ezalatt a hálózat mérete a rendelkezésre álló gépek számának függvényében változott, általában 5–10 gép méretű volt (3.4. ábra). Az átfedő nem csak egy alhálózatra korlátozódott; az egyedek egy része a Budapesti Műszaki és Gazdaságtudományi Egyetem Elektronikus Eszközök Tanszékének számítógépei voltak, másik része pedig otthoni, ADSL és kábeles hálózati kapcsolattal rendelkezett. Ezek közül egy OpenBSD-t, kettő Ubuntu Linuxot, a többi pedig Debian Linuxot futtatott. Az elemi, gyanús események érzékelését a Snort program végezte [60], illetve a Komondor rendszer a beállított szolgáltatások naplófájljait külön is figyelte. Mindegyik gépen működött SSH szolgáltatás, öt gépen Apache vagy lighttpd web kiszolgáló. Két gépen működött egy hamis POP3 levelező szolgáltatás, kifejezetten arra a célra, hogy a támadókat megtévessze. Az utóbbira érkező minden csatlakozási kísérletet támadásnak tekintettem, hiszen feljogosított felhasználója a rendszereknek ilyen szolgáltatást nem kereshetett. Az implementált rendszerben az események IP cím alapú összekapcsolását valósítottam meg. A 3.2. alfejezetben tárgyaltak alapján ez sok támadástípusnál alkalmas a kapcsolat felismerésére, és védekezés kialakítására is. A méréshez használt, főleg Linux alapú operációs rendszerekben a tűzfalat úgy állítottam be, hogy a Komondor rendszer által támadónak érzékelt IP címekről érkező forgalmat naplózza; az érzékeléshez így ezeket a napló bejegyzéseket is tudtam használni, nem csak az egyes kiszolgáló programok naplóit. Természetesen az IP cím alapú kapcsolatfelismerés és védekezés csak az egyik lehetőség. Ez a mérés elvégzéséhez és a referencia implementációban történő megvalósításhoz a többinél praktikusabbnak bizonyult. A vizsgálatok során alkalmazott Komondor átfedő hálózat egyik elemét speciális feladatkörrel láttam el. A P2P hálózatba kapcsolódást segítő horgonypont szerepe mellett ez rögzített, 0x00000001 értékű NodeID-t kapott. A rögzített adatokat a Kademlia protokoll szerinti helyen kívül az egyedek itt is eltárolták. Ez lehetővé tette azt, hogy a hálózatban történő minden eseményt naplózni lehessen, hiszen ez nem csak a riasztásokról értesült, hanem minden elemi eseményről. Ezen futott a monitorozó rendszer is, amellyel az átfedő aktuális állapotát és a tárolt adatokat lehetett vizsgálni. Az itt telepített programok az érzékelt betörési kísérletek típusairól, forrásairól és az érzékenység hatékonyságáról folyamatosan frissülő statisztikákat mutattak.

3.3.3. A Komondor rendszerrel érzékelt támadások A támadások a világtérképen A 3.5. ábra az érzékelt támadásokat mutatja, a támadások forrása szerint. Az egyes pöttyök a rajzon támadó IP címeket jelentenek, amelyekhez több támadás is tartozhat. A pöttyök mérete és az érzékelt támadások száma között logaritmikus összefüggés van. A legkisebbek egyetlen érzékelt támadást jelentenek, a legnagyobbak pedig kb. nyolcszázat. A térképet összesen 17088 rögzített támadás adatai alapján készítettem. Az egy IP címről érzékelt legtöbb különálló támadás 811 darab volt. Az implementált Komondor rendszer által végzett mérések eredményei hasonlóak a más, elosztott adatgyűjtő rendszerek által létrehozott statisztikákhoz [71]. A tapasztalatom az, hogy


38

1e3

1e2

1e1

1e0

3.5. ábra. Az érzékelt támadások forrásai a világ térképén. A pöttyök mérete és színe az érzékelt támadásokat mutatja logaritmikus skálán

a támadások leggyakrabban az ázsiai országokból érkeznek. Ennek oka főként az lehet, hogy az IP címek egyenetlenül kerültek kiosztásra. Némely amerikai nagyvállalat akkora tartománnyal rendelkezik, mint egy egész ázsiai ország. Másik valószínű oka, hogy ott gyakoribbak a frissítetlen, elavult operációs rendszerrel és programokkal működő gépek, amelyeknek így nagyobb aránya fertőzött valamilyen féregprogrammal. Alátámasztja ezt az is, hogy az onnan érkező támadások nagyobb része ezek aktivitása. A támadások IP cím szerinti megoszlása A 3.6 ábrán az események eloszlása láthato az IP címek és a kulcsok terében. EZ az ábra csak az SSH féregprogramok tevékenységét mutatja. Az IP címeket a négyzet alakú területre egy Hilbert térkitöltő görbe mentén képeztem le. Ezen a 32 bites IP címtartomány egymáshoz közeli területei egymás mellett vannak, például a 0/24-től a 63/24-ig terjedő tartomány (0/30) a bal felső negyedben; a 0/24-től a 15/24ig terjedő tartomány (0/28) a bal felső tizenhatodban. A cím első oktetje határozza meg a számozott négyzet választását, a második oktet pedig az azon belüli helyet. Ennek célja az is, hogy ne fedjék el egymást a pöttyök. Minden pötty egy konkrét támadást jelez, A pöttyök mérete és színe az ahhoz az érzékeléshez tartozó gyanús események számát mutatja. A színek logaritmikus skála szerintiek. Az egyes támadásokhoz nagyságrendekkel eltérő számú elemi események tartoznak. A rendszer érzékelt olyan támadásokat, amelyekhez csak néhány gyanús esemény tartozott, amelyet az átfedőben el kellett tárolni. Sok olyan is volt, amelyekhez események ezrei tartoztak. A kettő között négy nagyságrend különbség van. Az egy támadáshoz tartozó legnagyobb mért eseményszám kb. 70 000 darab.


0

1

14 15 16 19 20 21 234 235 236 239 240 241 254 255

3

2

13 12 17 18 23 22 233 232 237 238 243 242 253 252

4

7

8

11

5

6

9

10 31 28 27 26 229 228 227 224 245 246 249 250

39 1e5

30 29 24 25 230 231 226 225 244 247 248 251 1e4

58 57 54 53 32 35 36 37 218 219 220 223 202 201 198 197 59 56 55 52 33 34 39 38 217 216 221 222 203 200 199 196 60 61 50 51 46 45 40 41 214 215 210 209 204 205 194 195

1e3

63 62 49 48 47 44 43 42 213 212 211 208 207 206 193 192 64 67 68 69 122 123 124 127 128 131 132 133 186 187 188 191 65 66 71 70 121 120 125 126 129 130 135 134 185 184 189 190

1e2

78 77 72 73 118 119 114 113 142 141 136 137 182 183 178 177 79 76 75 74 117 116 115 112 143 140 139 138 181 180 179 176 80 81 94 95 96 97 110 111 144 145 158 159 160 161 174 175

1e1

83 82 93 92 99 98 109 108 147 146 157 156 163 162 173 172 84 87 88 91 100 103 104 107 148 151 152 155 164 167 168 171 85 86 89 90 101 102 105 106 149 150 153 154 165 166 169 170

1e0

(a) Érzékelt események száma IP címtartomány szerint 1e3

1e2

1e1

1e0

(b) Tárolt adatok eloszlása az átfedőben

3.6. ábra. Az érzékelés okozta terhelés elosztása a strukturált átfedőben


40

Ha a támadások forrásainak IP címét használjuk az események közötti kapcsolat felismerésére, akkor az érzékelő rendszer strukturált átfedőre történő építésével javíthatjuk a feldolgozást végző egyedek között a terhelés elosztását. Ezt mutatja a 3.6(b) ábra. Ezen a támadások forrás IP címét a hasító függvény segítségével leképeztem a Komondor egyedek alkalmazási szintű hálózati címterére. Az így keletkező, a referencia implementációban használt 32 bites azonosító első nyolc bitjét x, második nyolc bitjét pedig y koordinátának használva ábrázoltam a hasított kulcsok eloszlását.1 A támadások természetéből fakadóan az érzékelt események száma a támadások típusától erősen függ, akár négy nagyságrend különbség is lehet közöttük. A terhelés elosztása nem lehet teljesen egyenletes, hiszen egy adott támadótól származó adatokat meghatározott gyűjtő egyednek kell küldeni; a strukturált átfedő alkalmazásával mégis több, mint egy nagyságrendnyi javulást sikerült elérni. Az SSH férgek esetén a javulás 1,85 nagyságrend volt. Mivel egy támadás alatt gyakran generálják az átfedő egyedei ugyanazt a kulcsot, gyakran küldenek eltárolási és feldolgozási kéréseket ugyanannak a gyűjtő egyednek. A mérések alapján nyilvánvaló, hogy ebben a betörésérzékelési alkalmazásában eltérő dinamikájú forgalom keletkezik az átfedőben, mint egyéb alkalmazásoknál. Ehhez a dinamikához képes a Kademlia jobban alkalmazkodni, mint más strukturált átfedők. A 3.2.2. szakaszban bemutatottak szerint a Kademliánál csak az első ilyen üzenetnél van szükség a gyűjtő egyed címének kikeresésére, a másodiktól kezdve már minden gyanús esemény tárolásának költsége csak egyetlen egy üzenet. A támadások típus szerinti megoszlása A 3.7. ábra néhány kiválasztott támadástípust mutat. Az egyes típusok jelentősen eltérő gyakoriságban jelennek meg, ezért a gyakoriságot mutató x tengely logaritmikus skálázású. Zöld szín jelöli azokat a támadásokat, amelyeket a Komondor több érzékelő egyednél is rögzíteni tudott, a piros pedig azokat, amelyeket csak egynél. Az érzékelés alapja a mérésben a támadók IP címe, vagyis a rosszindulatú tevékenységre utaló adatcsomag forrás IP címe volt. Az elemi, gyanús események érzékelését a rendszer naplófájljainak vizsgálatával és a Snort programmal végeztem [60]. Az egyes gyanús eseményekhez tartozó naplófájl bejegyzés részlete, illetve a naplófájl neve a 3.4. táblázatban látható. Az érzékelés küszöbértéke a mérésben 10 pont volt; az események rögzített pontszámai tíz másodpercenként csökkentek 1-gyel. (Ennek célja az volt, hogy egy jelszavát véletlenül tévesen begépelő felhasználót ne zárjak ki véglegesen a rendszerből.) Az elosztott érzékelés hatékonysága erősen függ a támadás típusától. Egyes betöréstípusok, például a férgek aktivitásából adódó snort-sql-overflow esemény nem ismétlődnek rövid időn belül ugyanattól a forrástól. Ez a Slammer (Sapphire) féreg aktivitását jelzi, amely az Interneten máig igen elterjedt. Ez a féreg nem célzottan próbál meg terjedni, hanem csak véletlenszerűen választott célpontok felé. Ezt nem érdemes az elosztott érzékelő rendszerrel figyelembe venni, ha a támadók ellen célzottan szeretnénk védekezni. Az IP cím alapú érzékelés többlet biztonságot ennél nem tud nyújtani. 1 Erre

azért volt szükség, mert a Kademlia átfedő bináris fa topológiájához igazítva nem lenne lehetőség a kulcsok eloszlását szemléletesen ábrázolni. Ha a Komondor kétdimenziós CAN átfedőt alkalmazna, akkor ez az ábra pontosan megfelelne az átfedő egyedeinek is.


41

név

jelenség (naplófájl neve, reguláris kifejezés)

pont

vsftpd-fail-login sshd-invalid-user

/var/log/vsftpd.log : FAIL LOGIN Client /var/log/messages; /var/log/auth.log; /var/log/sshd/current; /var/log/authlog : (Failed password for (invalid|illegal)|Invalid) user from /var/log/messages; /var/log/auth.log; /var/log/sshd/current; /var/log/authlog : Failed password for [ˆ ]* from /var/log/messages; /var/log/auth.log; /var/log/sshd/current; /var/log/authlog : Did not receive identification string from /var/log/messages; /var/log/auth.log; /var/log/sshd/current; /var/log/authlog : Authentication failure for [ˆ ]* from /var/log/snort/alert ; /var/snort/log/alert : MS-SQL version overflow attempt /var/log/snort/alert ; /var/snort/log/alert : ICMP PING CyberKit 2.2 Windows bármilyen csatlakozási kísérlet /var/log/apache2/error_log; /var/log/apache/error_log; /var/www/logs/error_log : File does not exist : .*(include|main|server_collations|xmlrpc|adxmlrpc).php$

6 6

sshd-failed-password sshd-conn-lost sshd-auth-failed snort-sql-overflow snort-cyberkitping pop3-honeypot phpmyadmin

3.4. táblázat. Az elemi események típusai

érzékelt több helyen érzékelt

vsftpd-fail-login sshd-invalid-user sshd-failed-password sshd-conn-lost sshd-auth-failed snort-sql-overflow snort-misc-attack snort-cyberkitping pop3-honeypot phpmyadmin

1

10

100

3.7. ábra. Támadások típus szerint

1000

10000

3 6 3 12 12 10 6

3. FEJEZET. BETÖRÉSÉRZÉKELÉS STRUKTURÁLT P2P ÁTFEDŐN phpMyAdmin féregprogram (MySQL ellen) 1e4

42

Slammer féregprogram (MSSQL ellen) 100k

1e4

eseményszám időtartam

10 eseményszám időtartam

10k

1e2 100

1e1

események száma [db]

1k

támadás hossza [s]

1e3 események száma [db]


1e3

1e2

1e1 10

1e0 0%

20%

40%

60%

80%

1 100%

1e0 0%

20%

40%

60%

80%

1 100%

3.8. ábra. A Komondor által érzékelt támadások hosszai és eseményszámai a phpMyAdmin féreg és a Slammer esetén

A szisztematikus támadások esetén az elosztott és az összes támadások aránya sokkal nagyobb. Ilyen például az sshd-invalid-user típusú esemény, amelynél érvénytelen felhasználói nevet kap az SSH kiszolgáló. Mivel a felhasználók látják a képernyőn, hogy milyen nevet írnak be bejelentkezés közben (csak a jelszót nem), ezért abban ritkán hibáznak. Ez a típusú esemény szisztematikus betörési kísérletre utal, amit az is mutat, hogy az ilyen jellegű támadásokat több egyed is érzékelt ugyanarról a forrás IP címről. A saját készítésű hamis POP3 kiszolgáló programom egy postafiók kiszolgálót imitált (honeypot). Ennek segítségével nem sikerült olyan támadót érzékelni, amelyik több, a hálózat által védett számítógépet is támadni próbált volna. A támadások időbeli eloszlása és az érzékelt események száma A mérést végző Komondor hálózatban a naplózás feladatát külön ellátó, 0x00000001 NodeIDvel rendelkező egyed rögzítette az egyes támadóktól származó események számát, és a vélhetően egy támadáshoz tartozó legelső és legutolsó gyanús esemény között eltelt időt. Ezeket mutatja a 3.8. és a 3.9. ábra. Az y tengely mindegyik ábrán két skálával rendelkezik. A bal oldali skálák a támadás időtartamot mutatják (piros görbék), a jobb oldaliak pedig az érzékelt események számát (kék görbék). A támadások az időtartam szerint rendezve vannak. Az x tengelyen az egyes támadások kaptak helyet. Az összetartozó adatok, vagyis az egyes támadások időtartama és eseményszáma így egy x értéken található. A 3.8. ábra két különféle féreg aktivitását mutatja az összehasonlítás céljára. Az első (bal oldalt) a HTTP kiszolgálókon keres biztonsági réssel rendelkező MySQL adminisztrációs felületet (phpMyAdmin). A második (jobb oldalt) pedig az irodalomban sokat tárgyalt Slammer féreg, amely elavult verziójú MSSQL szerverek hibáját kihasználva terjed [71]. A grafikon-

3. FEJEZET. BETÖRÉSÉRZÉKELÉS STRUKTURÁLT P2P ÁTFEDŐN SSH hibás felhasználói név 1e5

SSH hibás jelszó 100k

1e5

1e3

1k

1e2

100

1e1

10

40%

60%

80%

1 100%

1e4

10k

1e3

1k

1e2

100

1e1

10

1e0 0%

20%

40%

60%

80%


10k


1e4

20%

100k eseményszám időtartam



eseményszám időtartam

1e0 0%

43

1 100%

3.9. ábra. A Komondor által érzékelt, SSH kiszolgálót érő támadások támadások hosszai és eseményszámai. A hibás felhasználói név szinte biztosan támadásra utal. A hibás jelszó a vakon gépelés miatt származhat feljogosított felhasználótól is.

ról leolvasható, hogy az előbbi kitartóan, akár több ezer lekérdezést indítva próbált meg a Komondor hálózat különböző gazdagépeire betörni; az utóbbi pedig általában csak egy-egy alkalommal próbálta meg megfertőzni azokat. A phpMyAdmin felületet támadó féreg ellen a Komondor védelmet tud adni az azt futtató gépek számára, mivel egy érzékelés után a támadó az IP címe alapján beazonosítható, és ez a tény a védekezésre felhasználható. A mérések alapján látszik, hogy ez a féreg szomszédos gépeket is támad, vagyis azok képesek egymás védekezését segíteni is. A Slammer féreg ezzel szemben véletlenszerűen választja ki a megtámadott célpontokat, így egy konkrét támadóhoz csak egy esemény köthető. A véletlenszerű célpont és az IP címek nagy száma miatt (232 ) valószínűtlen az, hogy egy támadó szomszédos, Komondor által védett gépeket támadna rövid időn belül. Mivel az egyes érzékelt események között a támadás módján kívül más kapcsolat nem fedezhető fel, és olyan információ sem következtethető ki belőlük, amely a védekezésre használható lenne, emiatt célzott védelem nem építhető ki. A fertőzött gép IP címe a tűzfalon keresztül blokkolható, de ez a védekezés általában későbbi esemény híján haszontalan. A Slammerhez hasonló férgek, és általában a vírusok elleni védekezésre a 2.5.6. szakaszban bemutatott PROMIS és Indra eljárások használhatóak [64, 40]. A 3.9. ábra az SSH kiszolgálókat érintő különféle eseményeket mutatja. Ez a típusú támadás a Komondor által érzékeltek közül a legszemléletesebben ábrázolható, hiszen ez a Komondor egyedek által védett számítógépek mindegyikén egy gyakran használt szolgáltatás volt. Az ábra vegyesen tartalmaz szándékos támadásokat és tévesen begépelt jelszavakat is. A bal oldali grafikon a hibásan megadott felhasználói neveket mutatja, a jobb oldali a hibás jelszavakat. Itt is látszik, hogy bejelentkezéskor a felhasználók látják a begépelt nevüket, a viszont jelszavukat vakon kell beírniuk. A helytelen felhasználónév ritkán származik emberi kéztől; ezek az


44

események, amelyekből nem ritkán tízezres darabszámmal is érzékelt a rendszer, szinte minden esetben kitartó, férgek által kivitelezett támadások részei voltak. A valóban csak tévesen begépelt jelszavak az esetek 40%-ában csak egyetlen egyszer fordulnak elő, mert másodjára a helyesen írták be azokat. Az események számából és a mérés idejéből becsülve átlagosan 2,5 naponta gépelte be valaki tévesen a jelszavát, ami a mérést végző gazdagépekre regisztrált felhasználók számát tekintve reálisnak mondható.

4. fejezet A Kademlia átfedő megbízhatóságának növelése

2. tézis. Új eljárást dolgoztam ki a Kademlia DHT átfedő rendszerszintű működési jellemzőinek beállítására. [S1, S2, S10, S16] 2.1. altézis. Kidolgoztam egy modellt, amely alapján a Kademlia átfedőben analitikusan és numerikus módszerrel is meghatározható a replikáció szintje úgy, hogy az adott hálózati viszonyok, mint peremfeltételek mellett az átfedő biztosítsa az egyedeinél tárolt adatok elvárt rendelkezésre állási szintjét. [S1, S10, S16, S17] 2.2. altézis. Megmutattam, hogy a Kademlia átfedőben az azonosítók gyakorlatilag véletlenszerűen történő megválasztása miatt a tárolt adatok elérhetősége a hibák globális eloszlásától függ. Bebizonyítottam, hogy egy adott rendelkezésre állás eléréséhez szükséges replikációs szint változatlan hálózati peremfeltételek mellett független az átfedő egyedszámától. [S1, S10] 2.3. altézis. Megmutattam, hogy a replikáció növelésével a Kademlia átfedő megbízhatatlan egyedek jelenléte esetén is megbízhatóvá tehető. [S1, S10, S16, S17]

A 2.2.2. szakaszban tárgyalt okok miatt a Kademlia nem teljesen megbízható. Ez azt jelenti, hogy egyes esetekben az eltárolt adatok visszakereshetősége nem minden egyed felől biztosított, annak ellenére, hogy vannak az átfedőben egyedek, amelyeknél elvileg elérhetőek azok. Ha egy eltárolandó adattételt a kulcsa alapján olyan egyedhez rendel az átfedő, amelyhez a többi egyed nem tud csatlakozni, a tétel nem minden esetben lekérdezhető. A csatlakozás meghiúsulását okozhatja valós vagy látszólagos hálózati hiba; az utóbbiak közé tartoznak a tűzfalak és a címfordítás 2.2.2. szakaszban említett hatásai. A visszakereshetőség meghiúsulhat amiatt is, hogy az adatot tároló egyed időközben elhagyja az átfedőt. Ez gyakori jelenség akkor, ha a hálózaton a gyakori az egyedek ki- és belépése (high churn). Az adatok több helyen történő tárolásával, vagyis replikációval a megbízhatóság jelentősen javítható. A replikáció növelése viszont azt is jelenti, hogy a hálózat forgalmát növeljük, és az 45

4. FEJEZET. A KADEMLIA ÁTFEDŐ MEGBÍZHATÓSÁGÁNAK NÖVELÉSE

46

egyes egyedektől is nagyobb háttértár kapacitás biztosítását várjuk el. A kidolgozott eljárás célja az, hogy a replikáció szükséges szintjére egy becslést adjon; hogy meg lehessen határozni egy olyan minimális értéket, amely segítségével az átfedő megbízhatósága egy megadott szintet már elér. Az éppen elégséges replikációs szint biztosítja az adatok visszakereshetőségét, miközben a hálózat és az egyedek terhelése nem növekszik meg indokolatlan mértékben. A szimulációs eljárás segítségével a hálózati hibák okozta megbízhatatlan működés feltérképezhető. Az eljárás segítségével bizonyítható az, hogy a replikáció szükséges mértékű növelésével az átfedő kellő mértékben megbízhatóvá is tehető. A bemutatásra kerülő matematikai modell segítségével pedig előre megbecsülhető egy olyan minimális replikációs szint, amellyel az átfedő megbízhatósága egy elvárt szintre növelhető.

4.1. A megbízhatóság növelése a replikáció alkalmazásával A Kademliában, ahogy a DHT-kben általánosságban is ez így működik, az eltárolt adattételek (kulcs-érték párok) azokhoz az egyedekhez kerülnek, amelyeknek azonosítója legközelebb van a kulcs hasított értékéhez. (Ezek neve a továbbiakban : a kulcshoz közeli egyedek.) A 2.2.2. szakaszban említett okok miatt azonban az így kiválasztott egyedek több más egyed számára elérhetetlenek lehetnek, így az adatok lekérdezése nem biztosított. Az adatokat a topológia és az útválasztási algoritmus által meghatározott helyen kell tárolni. A hasító tábla működésének lényege éppen az, hogy annál az egyednél kell eltárolni a tételt, amelynél a többi egyed keresni fogja azt. Az átfedőben a tételek egyedekhez történő rendelése globálisan ismert algoritmus és információ alapján kell történjen, ez pedig a kulcstól való távolság. Ha az adatokat nem a kulcs alapján meghatározott helyen tárolnánk, a többi egyed nem tudná, hol keresse azt. Replikáció esetén ezért a mozgásterünk a kulcs környezetére korlátozódik. Az egyedek a tételek tárolását kérvényező üzeneteket, illetve a kikeresést indító üzeneteket is olyan távoli egyedekhez próbálják elküldeni, amelyek közel vannak a kulcshoz. Minél több helyen van eltárolva a tétel a cél környezetében, annál valószínűbb, hogy lesz azok közül olyan, amelyhez a lekérdező egyed tud kapcsolódni. Egy adott címmel rendelkező egyed elérhetősége, a vele való kapcsolatteremtés lehetősége egyben azt is jelenti, hogy az ott tárolt tételeket le lehet kérdezni tőle. A lekérdező egyednek egyformán megfelel az is, ha a kulcshoz legközelebbi egyedtől kapja meg az adatot, de az is, ha egy távolabbi. Emiatt javítható a Kademlia hálózatban a replikáció szintjének növelésével az adattárolás megbízhatósága. Ezt az állítást a 4.3. alfejezetben leírtakkal igazalom. Az adatreplikáció szintjét a Kademlia irodalmában nem különböztetik meg a k-vödrök méretétől. Ez utóbbiak méretét k-val jelöljük, és ez a hálózat stabilitására van hatással. Az egyes kulcs-érték párokat azonban nem feltétlenül szükséges k helyen eltárolni, lehet kevesebb egyednél is. Ezért a replikáció szintjét kr -rel jelölöm, k-tól a replikációra utaló r indexszel megkülönböztetve. A k konfigurációs paraméter értéke az útválasztás stabilitásával, a kr pedig az adattárolás megbízhatóságával van közvetlen kapcsolatban.


47

4.2. Modellezési eljárások a Kademlia átfedőben A DHT rendszerekben az egyedek azonosítói (NodeID) és a kulcsok hasított értékei (FileID) között nincsen eredendő logikai vagy tartalmi összefüggés. Az összefüggést, hogy minden tétel értékét a kulcsukhoz legközelebbi azonosítóknál tárolnak el, az átfedők hozzák létre. Ennek célja az egyszerű eltárolás és gyors visszakeresés megvalósítása. Az átfedők működésére emiatt egy látszólagos véletlenszerűség jellemző. Egy átfedőbe belépő egyedhez egy bizonyos tétel azért kerül, mert a hálózatba lépéskor véletlenül egy ahhoz közeli NodeID-t választott magának. Egy másik egyed választhat még közelebbi azonosítót, és akkor a tétel nála tárolódik. A Kademlia átfedő esetén ugyanez az átfedőbe beépülés első lépése: az egyed választ magának NodeID-t, a 160 bites azonosítót. A nagy bitszám előnye, hogy kicsi, kb. P = 2−80 az esélye annak, hogy két egyed ugyanazt a számot sorsolja [72]. A sorsolás a címtartományból egyenletes eloszlással történik. Az átfedő egyedei emiatt közel egyenletesen fedik le azt. Az adatok eltárolásánál a kulcsokat az SHA-1 függvény segítségével képezik le erre a címtartományra. Ennek a függvénynek a kimenete is egyenletes eloszlással fedi le a 160 bites tartományt. Ez látszólag és jó közelítéssel véletlenszám. A bemenetén akár egy bit megváltoztatása is teljesen megváltoztatja a kimenetet. A véletlenszerű azonosítók és a hasító függvények egyenletes eloszlású értéke adja együttesen az átfedőben a terhelés elosztását is (load balancing). Mivel az egyedek egyenletesen elszórva helyezkednek el a tartományban, és az adattételek is egyenletesen fedik azt le, minden egyedhez nagyjából ugyanannyi adattétel kerül. Ez azt jelenti, hogy az egyedek egyforma mértékben felelősek az adatokért. Az átfedő szimulációjára és a modellezésére nézve a fentiek a következőket jelentik. Szimuláció esetén nincsen szükség túl nagy címtartomány használatára. Elég, ha az a szimulált egyedszámhoz képest kellően nagy. Matematikai modellezés esetén pedig a címtartományt vehetjük folytonosnak, helyettesítve azt a [0,1] tartománnyal [10]. Az egyenletes eloszlás miatt a szimulációkban és a modellezésben az egyed-adat összerendelést egy egyenletes eloszlású valószínűségi változónak tekinthetjük.

4.3. Az adattárolás szimulációja A replikáció segítségével elérhető megbízhatóságnövekedés az újonnan kidolgozott, és a következőkben ismertetésre kerülő szimulációs eljárással igazolható. Az eljárásban egy adott egyedszámú átfedő működését szimuláljuk. Minden egyedhez hozzárendelünk egy véletlenszerű azonosítót, ahogyan az egy valós átfedőben is történik. A szimulációban az egyedek címtere elegendő, ha 32 bites ; vagyis az egyedek alkalmazási szintű hálózati címei, és a kulcsok hasított értékei is 32 bitesek. Ez a végeredményre nincsen hatással, hiszen a valós egyedszámok is jóval kisebbek, mint 232 . A nagy címtér a valódi hálózatoknál az adat ütközés valószínűségének csökkentése miatt fontos, nem az egyedszám miatt, mert az általában elhanyagolható az előbbihez képest. A megadott számú egyedekhez a 4.3.1. szakaszban részletezett módon létrehozunk egy véletlenszerűen választott kapcsolati mátrixot, amely tulajdonképpen a kapcsolódási lehetőségek, vagyis a két egyed közötti üzenetküldési képességek gráfjának szomszédsági mátrixa.


48

(a) Tűzfal mögül indítva

(b) Kívülről indítva

4.1. ábra. Az egyedek kapcsolódási képessége tűzfal vagy címfordítás esetén A négyzetes mátrixban egy adott helyen HAMIS érték jelöli azt, ha az egyik egyed nem tud üzenetet küldeni a másiknak, IGAZ pedig azt, ha igen. Ez a mátrix nem szükségképpen szimmetrikus a főátlójára; egy címfordítás mögött lévő egyed képes lehet üzenni a publikus IP címmel rendelkező társának, míg fordítva ez nem igaz, ahogyan az a 4.1. ábrán is látható. Az egyedeknek ezek után a távolságaik szerint útválasztási táblázatokat generálunk. Ezek az útválasztási táblázatokat, amelyek a k-vödrök, az egyedek a valós átfedőkben is létrehozzák. Az egyes egyedek útválasztási táblázatai természetesen eltérőek, azok az egyedek távolságának függvényei. Ezek részfánként legfeljebb k bejegyzésből állnak, ahogyan a valós átfedőkben is. A szimuláció következő lépése egy véletlenszerűen sorsolt azonosító létrehozása. Ez jelképezi annak a tételnek a kulcsát, amelyet az egyedek tárolnának vagy lekérdeznének. Mindkettőhöz az egyedeknek az adott azonosítóhoz legközelebbi egyedet kell tudniuk elérni. Ha pontosan az az egyed nem elérhető, akkor a kérést az egyedek az átfedő topológiáján második legközelebbihez próbálják továbbítani; ha az sem, akkor a harmadik legközelebbihez és így tovább. Az üzenetküldés szimulációjához minden egyedhez ki kell számítanunk a kapcsolati mátrix alapján, hogy melyik az adott kulcshoz legközelebbi olyan egyed, amely számára is elérhető. Ez az egyed lesz replikáció nélküli esetben az, amelyikhez a tárolt adatot küldi, vagy amelyiknél az adott kulcshoz tartozó értéket keresni tudja. Replikáció esetén nem a legközelebbi, hanem kr darab legközelebbi egyedet próbál elérni az üzenetküldő. Az így érkező üzenetek száma adja a szimuláció kimenetét. Ez látható a 4.2. ábrán egy száz egyed méretű átfedő esetén. Adattárolásnál esetleg a kulcshoz valójában legközelebbi egyedek nem minden másiktól érhetők el, az eltárolt kulcsok kissé szétszóródnak attól függően, hogy mely egyedek tárolják el azokat. Ilyenkor a szimuláció kimenete éppen a kulcsok szétszóródását mutatja. A szimuláció végeztével a kiértékelés megkönnyítése érdekében a kulcstól való távolság szerint növekvő sorba rendezzük az egyedeket, és grafikonon ábrázoljuk, hogy melyikük hány üzenetet kapott. Ideális esetben, ha minden kapcsolat működik, a grafikon egy ugrásfüggvényt mutat: a kulcshoz legközelebbi (vagy a kulcshoz legközelebbi kr darab) egyed az összes üzenetet megkapja, a többieknek pedig nem küldenek semmit, ahogyan ez a 4.2. ábrán is


Beérkező üzenetek száma

100

49

hibák nélkül hibákkal

80

60

40

20

0 0

1

2

3

4

5

6

7

Üzenet céljahoz közeli egyedek

4.2. ábra. A fogadott üzenetek eloszlása a kulcs környezetében

látható. Hálózati hibák esetén a görbe ellaposodik és kiszélesedik; az egyedek a kulcstól kicsit távolabbi egyedeknek küldik el az üzeneteket. Például ha a replikáció szintje kr = 4, és az egyik egyed nem éri el a legközelebbi egyedet, akkor üzenetet fog küldeni akár az 5. legközelebbinek is. Bár a kulcshoz legközelebbi egyed, ahogyan az a 4.2. ábrán is látható, nem érhető el minden más egyedtől, mégis van olyan egyed a hálózatban, amelyikhez a többiek zöme kapcsolódni tud ; pl. a 2. és 3. legközelebbi.

4.3.1. A hálózati hibák eloszlása A hibák pontos eloszlása meghatározza a tárolt kulcsok eloszlását a hálózatban. Ha a hálózati hibák eloszlása egyenletes lenne (vagyis például egy száz egyedet számláló átfedőben minden egyed kilencven másik egyedet érne csak el), akkor nem lenne a hálózatnak olyan pontja, amelyik minden egyed által elérhető. Vagyis nem találnánk olyan egyedet, amely az elérhetőség szempontjából megbízható, bármilyen magasra választjuk is a replikáció szintjét. A valós hálózatokban a helyzet ennél jobb. A 2.2.1. szakaszban tárgyalt megállapítások alapján vannak egyedek az átfedőben, amelyekhez szinte minden másik tud csatlakozni, és vannak olyanok, amelyekhez általában a többi egyedek nem. Egy egyed elérhetősége azonban nem globális körülmény, hanem attól is függ, hogy mely másik egyed próbál meg csatlakozni hozzá. Ez jelenti az egyik veszélyt az átfedő megbízhatóságára nézve. Tegyük fel ugyanis, hogy egy tételt eltárolni kívánó egyed éppen azonos tűzfal mögött (vagy címfordított alhálózaton) van a kulcs által tárolásra kijelölt egyeddel. Ilyenkor az adat eltárolása sikeresnek tűnik a küldő számára, miközben az átfedő többi egyedeinek elérhetetlen a tétel, hiszen az azt tároló egyedhez nem tudnak csatlakozni.


külső→belső

külső→külső

belső→belső

belső→külső

(a) egy alhálózat esetén

50

(b) véletlenszerű elosztásban

1. alhálózat 2. alhálózat

(c) két alhálózat esetén

(d) véletlenszerű elosztásban

4.3. ábra. A kapcsolati mátrix jellege és valós alakja sok azonos alhálózatból érkező egyed esetén Általában ez akkor történik, amikor az adatot tároló egyed van tűzfal vagy címfordítás mögött van [19]. Ilyenkor a beérkező lekérdezés valószínűleg nem fog elérni hozzá (4.1. ábra). Fordított esetben, amikor a tűzfal mögötti egyed próbál meg a külsőhöz csatlakozni, nagyobb valószínűséggel fog létrejönni a kapcsolat. A tűzfal és címfordítás eljárások a kimenő csomag keletkezésétől számítva egy ideig nyitva tarthatja az adott portot [20]. Vagyis ha egy kapcsolat létrejött, akkor az meg is marad, ha folyik rajta adat. Így ha egy tűzfalon kívüli egyed tárolja az adott tételt, az a tűzfal mögötti egyed számára is elérhető, mivel a válasz megkérkezésének idejére még a tűzfal nyitva lesz, és a kommunikáció sikeres. Ez tükröződik a 4.3. ábra kapcsolati mátrixain is. (Más típusú hibák által létrehozott hibamátrixokról a 4.5.2. szakaszban lesz szó.)


51

A kapcsolati mátrixok jellegét a 4.3. ábra mutatja. A grafikon színnel jelölt részei mutatják a mátrix HAMIS elemeit. A 4.3(a). ábra egy olyan átfedő mátrixát mutatja, amely egyedeinek 10%-a egy bizonyos, nyilvános IP címekkel nem rendelkező alhálózaton található. Ezek egymás között gond nélkül tudnak üzenetet küldeni (belső→belső), és a külvilág felé küldött üzeneteiket (belső→külső) is megkapják a címzettek. A külvilág egyedei azonban nem tudnak kapcsolatot létesíteni velük (külső→belső). A külvilág egyedei között elszórt, egymással nem korrelált hibákat találunk csak. A 4.3(b). ábra mutatja a szimulációban használt mátrixot, amely a véletlenszerű azonosítók miatt van megkeverve. A 4.3(c). és 4.3(d). ábra ugyanezt mutatja két, eltérő méretű alhálózat esetére. Amellett, hogy a külső egyedek nem tudnak kapcsolatot kezdeményezni a belső egyedek felé, a két alhálózat egyedei egymással sem tudnak kommunikálni. A fentiek alapján felismertem, hogy a hibák nem egyenletes eloszlása ad lehetőséget arra, hogy az adatreplikáció növelni tudja az átfedő megbízhatóságát. Az átfedő alapjául szolgáló fizikai, IP szintű hálózat permanens hibái, vagyis a tűzfalak és a címfordítás hatásai függetlenek a kulcsoktól. Az egyedek az alkalmazási szintű azonosítóikat szabadon megválaszthatják, általában véletlenszerűen generálják azt, a 4.2. alfejezetben leírtak szerint. Egy egyed bármilyen azonosítót sorsolhat magának, viszont ez nem változtat azon a tényen, hogy a többi egyed által elérhető-e, mert az a fizikai hálózat adottságainak függvénye. Az eltárolt tételekhez tartozó kulcs hasított értéke is véletlenszámmal közelíthető, emiatt pedig egy eltárolt tétel kulcsa és az azáltal végeredményben meghatározott fizikai helye között nincsen összefüggés. Ha több egyednél tárolunk egy adott tételt, akkor nagyobb az esély arra, hogy a „véletlenszerűen” választott célpontok között lesz olyan is, amellyel minden többi egyed, vagy legalábbis a legnagyobb részük tud kommunikálni. Ha vannak egyedek a hálózatban, amelyek szinte minden másik egyedtől elérhetőek, akkor a replikáció növelésével egyre valószínűbb az, hogy az adott kulcs tárolásáért felelős egyedek halmazába valamelyikük bele fog esni. Minél több alkalmas egyed van, annál kisebb kr érték szükséges ehhez. A hálózati hibák pontos eloszlása a szükséges kr értéket, vagyis a kvantitatív eredményt módosítja; a kvalitatív eredmény azonban, hogy egy adott szintű replikáció felett a hálózat kellően megbízhatóvá tehető, nem módosul.

4.3.2. A replikáció szükséges szintjének meghatározása A 4.3. alfejezetben tárgyalt szimulációs módszer alapján meghatározható az, hogy egy adott hálózati hibaarány és -eloszlás mellett milyen kr érték szükséges ahhoz, ahogy az átfedő megbízható működését, vagyis a tárolt tételek elérhetőségét biztosítani lehessen. A megbízhatóság a hálózati hibák miatt nem lehet 100%-os. Egy olyan egyed, amelyik tűzfal vagy címfordítás mögött van, és így a legtöbb másik egyedek által elérhetetlen, az adatok tárolása szempontjából nem hasznos tagja az átfedőnek. Ha egy adott kulcs környezetében lévő összes egyed ilyen, akkor a kulcs eltárolása nehézségekbe ütközik. Viszont a replikáció szintjének növelésével lecsökkenthetjük ennek a valószínűségét. Ha nem írjuk elő a tételek 100%-os elérhetőséget, hanem annál akár csak néhány százalékkal alacsonyabbat, akkor a szükséges kr értéket is csökkenthetjük – a megbízhatóság rovására ezzel csökkenthető a hálózati forgalom és az egyedeknél használt tárkapacitás. A szükséges megbízhatóságot természetesen a konkrét alkalmazás határozza meg. Például előírhatjuk azt, hogy az átfedőben a tárolások és kikeresések 99%-a sikeres kell legyen. Ez azt jelenti, hogy az


52

eltárolt adatot az átfedő egyedeinek 99%-a képes legyen lekérdezni.1 Egy átfedőben minden egyed véletlenszerűen választott azonosítóval rendelkezik. Az, hogy egy konkrét egyedcsoport képes-e olyan átfedőt építeni, amely biztosítani tudja az előírt rendelkezésre állást, függ az átfedőbeli elhelyezkedésüktől. Ez pedig az azonosítók véletlenszerű megválasztásának függvénye, hiszen végeredményben azok határozzák meg, hogy mely egyedeknek melyekhez kell majd csatlakozniuk. Ezért egy adott kr szám mellett több szimulációt kell végeznünk; minden esetben meghatározva azt, hogy a kiválasztott kulcs eltárolását el tudja-e végezni egy kulcshoz közeli egyed. vagy lekérdezését az egyedek mekkora hányada tudta megvalósítani. Ha igen, akkor a szimulációt sikeresnek tekintjük, egyébként pedig sikertelennek. A sikeres szimulációk aránya adja meg azt, hogy egy adott, kr szintű replikáció mekkora valószínűséggel elegendő az előírt rendelkezési arány biztosításához. Mivel az adott kulcsot eltároló egyedek véletlenszerűen kerülnek kiválasztásra (a véletlenszerűség az azonosítójukból adódik), ugyanaz a kr replikációs szint használható kicsi és nagy átfedők esetén is. Ez a feltételezés akkor igaz, ha egy nagy átfedőkben ugyanolyan hálózati kapcsolattal rendelkező egyedek vesznek részt általában, mint egy kicsiben, hiszen a véletlenszerűen kiválasztott egyed egy véletlenszerűen kiválasztott kapcsolat minőséget jelent. A szükséges replikációs szint így független az átfedő méretétől.

4.4. Az adattárolás helyességének modellezése A 4.2. alfejezet megfontolásai alapján a hálózati hibák kiküszöböléséhez szükséges kr replikációt számítással is meg lehet határozni. Ennek menete a következő. Az átfedő címtartományában az egyedek eloszlása egyenletesnek vehető. A véletlenszerű azonosító választás miatt két szomszédos, vagyis az átfedő címterén belül értelmezve egymáshoz legközelebbi egyed egymástól földrajzilag igen távol lehet. Eltérő hálózati kapcsolattal rendelkezhetnek, azaz egymástól függetlenek. Ezen függetlenség miatt a hálózati hibák konkrét eloszlása az egyedek között, vagyis hogy melyik egyed pontosan milyen fizikai hálózati kapcsolattal rendelkezik, nem számít az átfedő egészének működése szempontjából, hanem csak a hibák globális eloszlása lényeges. Az átfedőn belüli összefüggés – például két egyed közelsége van az alkalmazási szintű címtérben – semmi további kapcsolatot nem jelent közöttük. Emiatt az egyedekhez tartozó hibaarányok konkrét egyedekhez rendelése nem lényeges, így azok a modellben növekvő sorrendbe rendezhetők. Ezt illusztrálja a 4.4. ábra. Ezzel egy monoton növekvő függvény adódik. Nagy számú egyed esetén a címtartományban diszkréten elhelyezkedő egyedek (x tengelyen) helyett egy folytonos eloszlás tekinthető. A hálózati hibák aránya (y tengelyen) is folytonos változóval közelíthető [10]. Az így kapott függvényt, amelyet a 4.5. ábra mutat, jelöljük h(m)-mel. Egy adott m ∈ [0,1] című egyedre h(m) azt adja meg, hogy milyen arányú kapcsolattal rendelkezik – vagyis hogy a többi egyedek mekkora része nem tud csatlakozni hozzá. 1

Éppen ez a megbízhatóság sérül egy tűzfal mögötti egyednél történő tárolásnál: ha az ottani egyedek teszik ki pl. az átfedő 2%-át, akkor csak annak a 2%-nak elérhető az adat. Vagyis az egész átfedőben szinte semelyik egyednek sem.

20%

20%

15%

15% hálózati hibák aránya

hálózati hibák aránya


10%

10%

5%

0% 0x00

53

5%

0% 0x10

0x20

0x30

0x40

0x50

0x60

0x70

0x80

egyedek azonosító szerint

egyedek hálózati hibák szerint

4.4. ábra. A hibák eloszlása egyedek szerint és növekvő sorrendben

Mivel a hibák miatt az átfedő nem működhet tökéletesen, a szimulációs vizsgálathoz hasonlóan itt is meg kell határoznunk, mekkora rendelkezésre állást várunk el attól. Például az eltárolt adatokra nézve azt várhatjuk, hogy az átfedő egyedeinek 99%-a képes legyen lekérdezni azt, vagyis az átfedő az esetek legfeljebb 1%-ában hibázhat. Jelöljük a még elfogadható hibaarányt általánosan a β számmal. A 4.5. ábrán ezt a megengedhető hibák vízszintes sávja mutatja. Ha egy adott, m azonosítójú egyed hibaaránya ennél kisebb, az azt jelenti, hogy az képes tárolni az adatot a többi egyed számára elérhető módon: h (m) ≤ β

(4.1)

Eltároláskor egy tétel látszólag véletlenszerű helyre kerül az egyedek véletlenszerű azonosítói és a hasító függvény tulajdonságai miatt. Ez azt jelenti, hogy egy adott tételhez véletlenszerűen sorsolhatunk egy m ∈ [0,1] számot. Ha a 4.1. egyenlőtlenség teljesül, akkor a tétel tárolása és lekérdezése biztosított. A 4.5. ábra három véletlenszerűen választott egyedre mutatja ezt; m1 esetében a tárolás és visszakereshetőség biztosított, m2 és m3 esetében pedig nem érjük el az előírt rendelkezésre állást. Az egyedek és a hozzájuk kerülő adatok egyenletes eloszlása azt is jelenti, hogy az ábráról leolvashatjuk a tárolást és visszakereshetőséget biztosítani tudó egyedek számát. β és h (m) metszéspontjától balra azok az egyedek vannak, amelyek képesek lekérdezhetően tárolni az adatot, jobbra pedig azok, amelyeknél túl magas a hálózati hibák aránya. Megoldva a 4.1. egyenletet, kapjuk : me ≤ h−1 (β) (4.2) Vagyis a [0, me ] címmel rendelkező egyedek megfelelőek: me az utolsó egyed címe, amelyik még megbízhatónak minősül.


54

30% megengedhető hibák hibák m1 m2 m3

25%

hálózati hibák

20%

15%

10%

5%

0% 0%

20%

40%

60%

80%

100%

egyedek

4.5. ábra. A hálózati hibák eloszlása. A grafikonról leolvasható azon egyedek aránya, amelyek a megadott rendelkezésre állást biztosítani tudják. A tárolt adatok helyét azonban nem ez, hanem a kulcsok hasított értékei határozzák meg (m1 , m2 és m3 ).

A 4.2. egyenletnek a [0,1] tartományon belülre kell essen a megoldása. Ha β kisebb, mint az összes h(m) érték, az azt jelenti, hogy olyan rendelkezésre állást szeretnénk elérni, amelyiket semelyik egyed sem tud biztosítani, vagyis, hogy a replikációt hiába növelnénk. Ha β nagyobb, mint az összes h(m) érték, az azt, hogy az előírt rendelkezésre állást bármelyik egyed biztosítani tudja – ilyenkor nincsen szükség replikációra. Az eltárolt adat helye egyenletes eloszlású valószínűségi változó. Emiatt az me szám azt is mutatja, hogy mekkora a valószínűsége annak, hogy egy adattétel alkalmas egyedhez kerül, hiszen az adatokat egyenletesen osztja el a hasító függvény a címtérre. Jelöljük ezt a valószínűséget P 0 -vel: P 0 = me = h−1 (β) (4.3) Ez a helyes egyedválasztás valószínűségét adja meg a megengedett hibaarány függvényében. A 4.2. egyenlet miatt ez a megadott rendelkezésre állást biztosítani képes egyedek arányával is megegyezik. Mivel a tételek eltárolását nem szervezhetjük úgy, hogy azokat kifejezetten a megbízható egyedeknél helyezzük el (azzal sérülne az átfedőben a kulcs-egyed hozzárendelés szabálya), a replikáció növelésével kell biztosítanunk azt, hogy a tároló egyedek között legyen megbízható is. Ha az átfedő replikációt is megvalósít, az adatok kr különböző helyen tárolódnak. Ez azt jelenti, hogy kr -szor választhatunk m ∈ [0,1] közötti véletlenszámot. Ha a kr alkalomból legalább egyszer teljesül a 4.2. egyenlőtlenség, a tétel megbízható helyre kerül, és a kikeresések sikeresek lehetnek. Kiszámítva az összes sikertelenségek valószínűségét, és azt 1-ből kivonva


55

12% α=2, c=10% α=2, c=5% α=4, c=5%

hibás kapcsolatok aránya

10%

8%

6%

4%

2%

0% 0

0,2

0,4

0,6

0,8

1

egyedek az átfedőben

4.6. ábra. A hálózati hibák az egyedekhez, folytonos közelítéssel, növekvő sorrendben

kapjuk : P = 1 − (1 − P 0 )kr Ebbe behelyettesítve az egy kikeresés sikerességét megadó P 0 -t: kr P = 1 − 1 − h−1 (β)

(4.4)

(4.5)

P annak a valószínűségét adja meg, hogy egy adott kr replikáció elegendőnek bizonyul-e egy adott β hibaarány kiküszöböléséhez, a h(m) függvény által adott hálózati peremfeltételek mellett. A 4.5. egyenletet kr -re megoldva a szükséges replikáció nagysága meghatározható: ' & ln (1 − P ) kr = (4.6) ln (1 − h−1 (β)) Mivel a replikáció szintje csak egész szám lehet, a tört értéke felfelé kerekítendő. Az így meghatározott kr használata esetén az átfedő biztosítja a szükséges rendelkezésre állást. Ahogyan az az egyenletből is látható, a replikáció szükséges szintje nem függ az átfedőben résztvevő egyedek számától, vagyis nagyobb egyedszámnál nincs szükség annak növelésére. Ez a kulcsok látszólagos véletlenszerű elhelyezésének a hatása: a hasító függvények egyenletesen fedik le az értékkészletüket, ezért az adatok is az átfedőt.

4.4.1. A modell és a szimuláció összevetése A szimulációs eljárás és a matematikai modell által adott eredményeket összevetve igazoltam azok helyességét. Az eredmények összehasonlításához szükséges volt az, hogy egy olyan hibael-


56

oszlással végezzem azt el, amely kezelhető analitikusan is. Ehhez az eloszlást egy polinommal közelítettem. Ennek inverz függvénye meghatározható, ami a 4.2. egyenletbe történő behelyettesítéshez szükséges. Határozatlan integrálja is, amely a különböző vizsgált eloszlásoknál az egyforma összesített hibaarány megadásához használható. A 4.6. ábra ilyen másodfokú és negyedfokú polinommal közelített hibaeloszlásokat mutat (α = 2, illetve α = 4), amelyben az egy egyedhez tartozó legnagyobb hibaarányt a c konstans határozza meg. Az x tengelyen az egyedek helyezkednek el, az y tengelyen pedig a hibás kapcsolataik aránya. A 4.7(a) ábra egy 1000 egyedből álló átfedő szimulációját és modelljét mutatja. A hálózati hibák eloszlását ezen egy négyzetes függvénnyel közelítettem: h(m) = c · m2 . A grafikon a sikeres átfedőépítések arányát mutatja be; sikeresnek tekintettem azokat az esetek, ahol a kulcsok kikeresése az esetek legfeljebb β = 1%-ban nem sikerült. Az ábrán láthatóan a hibák arányának növekedtével a megbízhatóság csökken, a replikáció növelésével pedig nő. kr = 8 esetén az átfedő 90% feletti megbízhatósággal képes üzemelni még az igen magasnak számító, c = 18%-os hibaarány esetén is. A hibaeloszlás-függvénynek inverzét a a 4.5. egyenletbe behelyettesítve az alábbi valószínűséget kapjuk a modellezett átfedő helyes működésére: r kr   α β  P = 1 − 1 −  c

(4.7)

A 4.7(b) ábra a 4.4. részben bemutatott matematikai modell által adott eredményt is mutatja az egyenlet alapján. Ez megfelel a szimulációval kapott eredménynek. A megbízhatóság változása a nem egyenletes hibaeloszlással A 4.8. ábra az átfedő megbízhatóságát mutatja változó hibaeloszlás függvényében. A szimulációt itt is 1000 egyedre végeztem el, összesen 50000 eset vizsgálatával. Az α értéket, amely a hálózati hibák eloszlását határozza meg a h(m) = c · mα függvényben, [0,4] között változtattam. Az α = 0 egyenletes hibaeloszlást jelent. A c együtthatót úgy állítottam be, hogy az összes hiba az α értékétől független legyen; vagyis α változásával csak az eloszlásuk változzon meg, az összes hibák száma azonban nem. Az együttható értéke az összesített hibaarány kiszámításával határozható meg, amely a h(m) függvény integrálásával számítható ki: Z

1

Z

1

h(m) = 0

0

c · mα =

c α+1

(4.8)

Ez alapján változtatva c értékét α-val együtt az összes hibák száma nem változik, csak az eloszlásuk. Látható, hogy egyenletes hibaeloszlás esetén a replikáció nem növeli a megbízhatóságot. A hálózatban ilyenkor nincs is olyan egyed, amelyik az előírt 1 − β = 99%-os rendelkezésre állást biztosítani tudná. Ha a hibák eloszlása nem egyenletes, vagyis vannak olyan egyedek, amelyek biztosítani tudják az előírt rendelkezésre állást, akkor a replikáció növelésével megnő annak a valószínűsége, hogy a kulcsok azokhoz kerülnek. Ezzel nő a hálózat megbízhatósága – minél inkább heterogén a hibák eloszlása, annál nagyobb a replikáció megbízhatóságot növelő hatása.


57

Kadsim egyedek=1000, α=2, β=1%

100 90 80 70 60 50 40 30 20 10

100 80 60 40 20 0 10 9

8 7 repliká 6 5 4 ció (kr )

3

2

2% 6% c) ( 10% ibák h 14% ati z ló há 1 18%

(a) szimuláció

Kadsim egyedek=1000, α=2, β=1%

100 90 80 70 60 50 40 30 20

100 80 60 40 20 0 10 9

8

7 replik 6 5 áció ( k

r)

4

3

2

2% 6% ) c 10% bák ( hi 14% ati z ló há 1 18%

(b) modell

4.7. ábra. A sikeres kikeresések valószínűsége a Kademliában


58

Kadsim egyedek=1000, Σc=0.1, β=1%

100

100

80

80

60

60

40

40

20

20

0

0 4 háló z

3 ati h i ba

2 elos zlás

1 (α)

9 10 8 7 ) 5 6 ció (kr 4 iká 3 repl 0 1 2

4.8. ábra. Sikeres kikeresések a hibaeloszlás egyenetlenségének függvényében

4.5. A modell alkalmazási lehetőségei A bemutatott szimulációs eljárás és modell a Kademlia átfedőkben általánosan alkalmazható, vagyis a Kademliára épülő bármely alkalmazásban felhasználható. A szimuláció és a modell ellenőrzéséhez megvalósítottam a 4.3. alfejezetben leírt szimulációs eljárást. Az elkészített Kadsim nevű alkalmazás (4.9. ábra) C++ nyelven íródott, az ábrázoláshoz pedig a Gnuplot programot használja. A szimulátorom elsődleges célja a hálózati hibák által terhelt átfedőben az eltárolt adattételek helyének meghatározása. Ezzel válik mérhetővé ugyanis az, hogy az átfedő milyen megbízhatósággal képes biztosítani az eltárolt tételek visszakereshetőségét a többi egyed számára. A szimulátor meghatározza, hogy adott kr replikáció mellett az egyes egyedeknél eltárolt tételek hány másik egyed által visszakereshetőek. Ha van olyan egyed az átfedőben, amely kellően nagy számú másik egyedtől elérhető, akkor az adat visszakereshetősége biztosított, ahogyan az a 4.2. ábrán is megfigyelhető. A szimulátor minden futtatáskor új kulcsokat és hálózati hibaeloszlást generál. A kimenet alapján a következőkben tárgyalt hibaeloszlásokhoz meghatároztam, hogy van-e olyan egyed a hálózatban, amely megbízhatóan tudja tárolni az adatokat, továbbá hogy milyen kr szükséges a megbízható működéshez.

4.5.1. A szükséges replikáció jellemző értékei Ha a hálózati hibák eloszlása ismert, akkor a szükséges replikáció a 4.4. alfejezetben tárgyalt matematikai modell, vagyis a 4.6. egyenlet használatával felülről becsülhető. Ezt mutatja a 4.10. ábra. Az ábrán a modellezett átfedőben a hibák eloszlását harmadfokú függvénnyel közelítettem. A hálózati hibák aránya, mint a 4.8. ábrán is, a hibás és az összes kapcsolatok arányát jelentik ; egyes egyedeknél a hibaarány a megadott értéknél jóval nagyobb is lehet. A


59

4.9. ábra. A Kadsim program képernyőképe

Hiba típusa

Érzékelt jelenség

Címfordítás mögött

Csak a vele azonos alhálózat egyedetől elérhető

Rosszindulatú egyed

Senkitől nem elérhető az adat (nem tárolja)

Kilépő egyed

Időben változó elérhetőség 4.1. táblázat. Egyed hálózati vagy saját hibája

grafikonon mutatott replikációs szintek a modell és a szimulációk szerint az esetek 95%-ában elegendőek az x tengelyen ábrázolt arányú hibák hatásainak kiküszöböléséhez.

4.5.2. Az egyedek hibái és a kapcsolati mátrix összefüggése A különböző típusú hibák, amelyek az átfedőben az adattárolást és visszakeresést akadályozzák, különféle módon jelennek meg a kapcsolati mátrixban. Ezeket a 4.1. táblázat foglalja össze. Ha sok egyed azonos alhálózatról érkezik, akkor egymás között tudnak kommunikálni, ahogyan az a 4.3. alfejezetben is szerepelt. Ilyenkor a kapcsolati mátrixban az alhálózatnak megfelelő méretű sávban jelennek meg a megbízhatatlan egyedek. Minél kisebb az alhálózat relatív mérete az átfedőéhez képest, annál inkább jelentenek azok az egyedek egy egyszerű 100%-os megbízhatatlanságot. Ha az átfedő rosszindulatú egyedeket tartalmaz, amelyek nyugtázzák az adatok eltárolását, de azután nem adják azt vissza egy kikeresés hatására, akkor ezt úgy vehetjük figyelembe, hogy azok 0%-osan vesznek részt az adattárolásban. Ha az átfedő populációja nem állandó, akkor a kapcsolati mátrix időben változik. A popu-


60

szükséges replikáció

12 12 11 10 9 8 7 6 5 4 3 2 1

10 8 6 4 2

18% 14% 1%

2%

3% megengedett hibaarány

4%

6%

10% hálózati hibák

5%2%

4.10. ábra. Adott megbízhatóság eléréséhez szükséges replikáció

láció változásának sebességét az adatok szükséges tárolási idejével kell összehasonlítanunk. Ezek az adott alkalmazástól függenek. Maymounkov a fájlcserélő alkalmazásnál egy órás időintervallumokat használ [11]. Más típusú adatoknál más lehet az elvárásunk, amit az egyedek várható élettartamával kell összehasonlítanunk. Ha egy egyed a hirtelen kilépése miatt nem képes biztosítani az adatot, amiért felelős, akkor ugyanúgy megbízhatatlannak számít, mint egy szinte semelyik által nem elérhető társa. Mindezek mellett a hálózati hibák oka és eloszlása legtöbbször ismeretlen az egyedek számára. Ilyenkor a h−1 (β) kifejezés értéke közelíthető működés közben az általuk létrehozni próbált kapcsolatok sikertelenségének arányával. Mivel ez az információ működés közben automatikusan előáll tapasztalatként, ez lehetőséget ad arra, hogy a működő átfedő egyedei futás közben meghatározzák a szükséges kr szint beállítását, ahogyan az a 4.5.4. szakaszban is olvasható.

4.5.3. A populációváltozás okozta hibák hatásának kiküszöbölése a replikáció növelésével A 2.2.3. szakaszban bemutatottak alapján a Kademlia eljárásban az eltárolt kulcsokat a kilépő egyedek nem adják át szomszédaiknak [11]. A kilépő egyed ilyen módon az adat kikeresése szempontjából olyan hatással van, mintha az mások számára elérhetetlen lenne. Minél gyorsabban változik az egyedek populációja, annál erősebben érezhető ez a hatás. A Kademlia protokoll előírja, hogy az eltárolt kulcsokat az egyedek óránként frissítsék [11]. Bár az egyes átfedőkben az egyedek élettartama a felhasználók szokásaitól függően eltérő [73], mégis egy véletlenszerűen kiválasztott egyed egy órán belüli eltűnésének valószínűsége több, az irodalomban bemutatott mérés szerint is egységesen 30% körül van. A Gnutella hálózat

4. FEJEZET. A KADEMLIA ÁTFEDŐ MEGBÍZHATÓSÁGÁNAK NÖVELÉSE egy óra alatt kilépő egyedek 30%

61

elvárt rendelkezésre állás 85% 90% 95% 98% 99% 2

2

3

4

4

4.2. táblázat. Szükséges replikációs szintek a be- és kilépő egyedek okozta hibák kiküszöbölésére

esetén 30%, az OverNet esetén 35% [74], míg a MainLine átfedőben 28% a mért érték2 [19]. A replikációs szintek megbecsléséhez itt is a 4.6. egyenlet használható. A 30%-os óránkénti kilépési rátához használható kr értékeket a 4.2. táblázat mutatja.

4.5.4. A modell használata az Azureus és a Mainline BitTorrent hálózatok megbízhatóságának javítására A Kademlia átfedőre épülő BitTorrent hálózatokban az otthoni felhasználók tűzfalak és címfordítás mögötti számítógépei miatt a csatlakozási kísérletek, és ezzel a lekérdezések jelentős része meghiúsul [17]. A publikus IP címmel nem rendelkező számítógépei miatt a hálózati hibaarány akár 15%-ra is nőhet a Mainline alapú kliensek, és 30% fölé az Azureus alapú kliensek esetén. A sikertelen csatlakozási kísérleteket olyan egyedek okozzák, amelyek hálózati címfordítás mögött vannak [17]. Ezek tudnak csatlakozni a többi egyedhez, így be is kerülnek azok útválasztási táblázataiba. Később azonban nem lehet kívülről csatlakozni hozzájuk, mivel a tűzfalak vagy a címfordítás ideiglenesen létrejött útválasztási szabályai megszűnnek. Ezekre az egyedekre nem lehet bízni az adatok tárolását, ugyanis hiába kerül hozzájuk adat, a többi lekérdezni azt nem tudja. A replikációt olyan szintre kell növelni, hogy az adatok nagy valószínűséggel kerüljenek biztosan elérhető egyedekhez is. Ezekben az átfedőkben a 4.6. egyenlet alapján lehet megbecsülni a szükséges replikációt. A hálózati hibák pontos eloszlásáról a fent idézett műben pontos információ nincsen, csak azok számáról. Az eloszlást egy egységugrással vettem figyelembe, ahogyan az a 4.11. ábrán is látható. Ez a kapcsolati mátrix a 4.5.2. szakaszban leírt közelítése. Az idézett irodalom alapján a Mainline átfedőben az egyedek 15%-a nem volt elérhető [17]. Ezen egyedek valószínűleg nem voltak globálisan elérhetetlenek, csak a mérő egyed szempontjából. A mérés pontos körülményeiről nincsen további információ, ezért globálisan elérhetetlennek tekintettem ezeket. Így a modellben 15% az esélye annak, hogy olyan egyednél kellene egy tételt eltárolni, amely később elérhetetlennek látszik, mind a tárolást indító, mind a többi egyed számára. Ebből következik, hogy eltárolást és visszakereshetőséget biztosító egyedek alkotják az átfedő m = h−1 (β) = 85%-át. A szükséges replikációk értékeit a 4.6. egyenlet alapján számítottam ki, a 4.3. táblázat mutatja azokat különböző elvárt rendelkezésre állásokra. 2 Ez

a MainLine esetén valószínűleg alacsonyabb 28%-nál, mivel a hivatkozott irodalomban bemutatott mérési eljárás nem tudta megkülönböztetni a kilépő egyedeket az ún. full cone típusú címfordítástól.

100%

100%

80%

80% hibás kapcsolatok aránya

hibás kapcsolatok aránya


60%

40%

20%

60%

40%

20%

Azureus 0% 0%

62

20%

Mainline 40%

60%

80%

100%

0% 0%

20%


40%

60%

80%

100%


4.11. ábra. Hálózati hibák a BitTorrent átfedőkben [17] alapján, a bemutatott eljárás szerint ábrázolva

elérhető egyedek (m)

elvárt rendelkezésre állás 85% 90% 95% 98% 99%

70% (Azureus)

2

2

3

4

4

75%

2

2

3

3

4

80%

2

2

2

3

3

85% (Mainline)

1

2

2

3

3

90%

1

1

2

2

2

95%

1

1

1

2

2

4.3. táblázat. Szükséges replikációs szintek a Kademlia alapú BitTorrent átfedőkben

4.5.5. A szimulációs eljárás használata az elosztott betörésérzékelés megbízhatóságának javítására A 3. fejezetben bemutatott DHT alapú biztonsági eljárás helyes működésének feltétele, hogy az alapjául szolgáló átfedő helyesen működjön. Az egyedek az érzékelt eseményeket a hozzájuk rendelt kulcsok hasított értékei alapján az azokhoz legközelebbi egyedekhez küldik feldolgozásra. Ezek azonban nem biztos, hogy elérhetőek: vagyis az adatok nem a hasított értékhez legközelebbi egyedekhez, hanem a hasított értékhez legközelebbi és elérhető egyedekhez kerülnek. A kulcsok visszakereshetősége ebben az esetben nem fontos. Ugyanis elég azt biztosítani,


Fogadott üzenetek egyedenként

100

63

hibák nélkül hibák esetén

80

60

40

20

0 0

1

2

3

4

5

6

7

Egyedek a kulcs környezetében

4.12. ábra. Az események elküldött adatainak eloszlása a kulcs környezetében. Az eljárás helyes működéséhez szükséges az, hogy a gyűjtő egyedek minél több másik egyedtől elérhetőek legyenek.

hogy az egyes tapasztalatok valamelyik egyednél összegyűljenek. Hogy pontosan melyik az az egyed, az az eljárás működése szempontjából érdektelen. Lényeges viszont, hogy legyen olyan egyed az átfedőben, amely egy támadás esetén minél több érzékelőtől fogadni tudja az adatokat, ugyanis ilyenkor biztosított az, hogy átfogó képe van a hálózatot ért támadásról. Ha a tapasztalatot elküldő egyedek nem tudnak csatlakozni a kulcshoz legközelebbi egyedhez, akkor a távolabbiakhoz kerülnek a tapasztalatok, mint ahogy azt a 4.12. ábra is mutatja. Ha nincsen olyan egyed, amelyik minden esemény adatával rendelkezik, akkor előfordulhat az, hogy a rendszer a támadást nem érzékeli. Az alkalmazott Kademlia átfedőhöz ezért a replikáció szintjét úgy kell megválasztani, hogy a megfelelő rendelkezésre állási szintet azzal biztosítani lehessen, hiszen ez határozza meg az eljárás által biztosított érzékelés pontosságát is. Az egyedek pedig nem csak hálózati hiba miatt lehetnek elérhetetlenek, hanem támadás miatt is kieshetnek az átfedőből.

5. fejezet Üzenetszórás a Kademliában

3. tézis. Kidolgoztam egy eljárást a Kademlia átfedőn belül küldött üzenetszórás hatékony megvalósítására. [S1, S2, S3, S5, S9, S12, S15] 3.1. altézis. Felismertem, hogy bármely Kademlia átfedő átrendezhető úgy, hogy egy adott egyed egy, a címtérből tetszőlegesen kiválasztott azonosítójú átfedő hálózati pontba kerüljön, miközben az egyedek közötti, az átfedőn ugrásszámban mért távolságviszonyok nem változnak. Kidolgoztam egy átrendezési eljárást, amellyel egyszerűsíthető a Kademlia átfedő hálózatokra vonatkozó kommunikációs algoritmusok tervezése. 3.2. altézis. Elméleti úton igazoltam, hogy a kidolgozott üzenetszórási eljárással az üzenet küldése az egyedszámhoz viszonyítva logaritmikus számú lépésen belül megtörténik, és az a hálózat fenntartásának hálózati költségét nem terheli. A kidolgozott algoritmus elméletileg meghatározott eredményeit szimulációval is igazoltam. Az vizsgálatokat elvégeztem különböző, gyakorlati eseteknek megfelelő peremfeltételek mellett. [S1, S2, S3, S5, S9, S12, S15] 3.3. altézis. Bebizonyítottam, hogy replikáció alkalmazásával az üzenetszórás hibákkal terhelt fizikai hálózaton, valamint rosszindulatú egyedek jelenléte esetén is megbízhatóvá tehető. Meghatároztam az egy adott megbízhatóság eléréséhez szükséges replikációs szintet a hálózati hibaarány és az egyedszám függvényében. [S1, S3, S5, S9]

A P2P átfedőkön üzenetszórást ritkán használnak az azokra épülő alkalmazások. Az egyedek nagy száma miatt az üzenetszórás sok erőforrást igényel. A strukturált átfedőket pedig éppen azzal a céllal hozták létre, hogy a Gnutellához hasonló nem strukturált átfedőkben használatos elárasztást hatékonyabb keresési eljárásokkal váltsák ki (lásd a 2.1.1. szakaszt). A Kademliában igen nagy fokú az átfedő összekötöttsége, abban az értelemben, hogy egy egyed több száz szomszédja címét ismerheti. Ezért elárasztással nem valósítható meg rajta üzenetszórás, csak a struktúrájának kihasználásával. A kidolgozott eljárás célja, hogy 64

5. FEJEZET. ÜZENETSZÓRÁS A KADEMLIÁBAN

65

a Kademlia átfedőben egy megbízhatóan és hatékonyan működő algoritmust adjon erre: az üzenetküldés legyen gyors, és lehetőség szerint kevés üzenetet használjon. A bemutatott üzenetszórási algoritmus bármelyik Kademlia átfedőben használható, amelyben az alkalmazás igényli azt, hogy valamilyen információ az egyedeknek globálisan elküldhető, vagy azoktól globálisan lekérdezhető legyen. Egyik alkalmazási lehetősége a komplex lekérdezések megvalósítása a DHT átfedőkben. Ezen átfedők felépítésükből adódóan csak pontos kulcsra történő keresésre alkalmasak, ahogyan az a 2.1.2. szakaszban is szerepelt. Az ennél bonyolultabb, vagy kulcsrészletre történő keresés esetén a szokványos, általában logaritmikus idejű kikeresési eljárás nem használható. Ilyen esetben a keresés megvalósításának egyik lehetősége, ha a lekérdezés feltételeit minden egyedhez eljuttatjuk, vagyis üzenetszórást valósítunk meg az átfedőn. A 3. fejezetben bemutatott Komondor eljárás is használja az üzenetszórás szolgáltatást. A megvalósított Komondor szoftver, amely a 3.3.2. szakaszban tárgyalt hálózati betöréseket érzékelte, támadások esetén üzenetszórással értesítette az átfedő egyedeit a támadás tényéről.

5.1. A Kademlia átfedő transzformációja Az 5.2.2. és az 5.2.3. szakaszban tárgyalt algoritmusok leírásakor azzal a feltételezéssel élek, hogy az üzenetszórást indító egyed az átfedőben a fa bal szélén helyezkedik el, azaz a címe csupa nulla bitekből áll. Az alábbiakban megmutatom, hogy az így leírt algoritmusok általánosíthatóak. Felismertem, hogy a Kademlia átfedő egyedei átrendezhetőek úgy, hogy egy tetszőlegesen kiválasztott egyed a 0 címre kerül, miközben az átfedő szomszédsági és távolsági viszonyai nem változnak meg. Az átrendezés lényege, hogy az egyedek hálózati címeivel (NodeID) egy tetszőlegesen kiválasztott számot (X) bitenkénti kizáró vagy (XOR) kapcsolatba hozhatunk. Az X szám egyes helyiértékein szereplő 1-es bit azt fogja eredményezni, hogy az adott méretű részfák helyet cserélnek egymással. Ha ez a szám 10000. . . , vagyis a legfelső helyiértéke 1-es, a többi 0, akkor az egész fa bal és jobb oldali fél részfája fog helyet cserélni egymással; de a részfák alakja változatlanul marad. Ha 01000. . . , akkor a fél részfákon belüli negyed fák cserélnek helyet és így tovább. Az átrendezés közben az összes egyed új NodeID-t kap, amely értéke az eredeti NodeID és a kiválasztott szám XOR kapcsolata: Nuj ´ = N ⊗X

(5.1)

Az XOR művelet tulajdonságai miatt a két egyed távolsága ennek ellenére nem változik: D = Auj ´ ⊗ Buj ´ = (A ⊗ X) ⊗ (B ⊗ X) = A ⊗ B ⊗ X ⊗ X = A ⊗ B

(5.2)

Emiatt a transzformált átfedőben az útválasztási táblázatok teljesen azonosak az eredeti átfedő táblázataival, mivel azok a változatlanul maradó távolságtól függenek [11]. Az átrendezést az 5.1. ábra illusztrálja. Az ábrán az 1010 számú, fehérrel jelölt egyedet helyezem át a 0000 pontba. Először az 1000 számmal hozom a címeket XOR kapcsolatba (5.1(b) ábra); ennek a hatására a fél részfák cserélnek helyet, a piros-zöld és a kék-zöld fák. Majd a 0010 számmal hozva kapcsolatba a zöld részfák cserélnek helyet piros és kék a szomszédaikkal (5.1(c) ábra). Mivel minden egyes helyiértéken lévő 1-es bit csak a saját helyén hat, a két lépés összevonható : a címeket az 1010 számmal, vagyis pontosan a bal szélre helyezendő egyed hálózati címével kell XOR kapcsolatba hozni.


66

1

0

1

1 0

1

1111

0

1100

1

1011

0

0

1010

1

1

1001

0

0

1000

1

0110

0

0101

1

0100

0

1

1

1110

0 0

0011

1

0001

0000

0

1

0010

0

1

0111

0

1

1101

0

(a) Az eredeti átfedő

1

0

1

1 0

1

1111

0

1100

1

1011

0

0

1010

1

1

1001

0

0

1000

1

0110

0

0101

1

0100

0

1

1

1110

0 0

0011

1

0001

0000

0

1

0010

0

1

0111

0

1

1101

0

(b) A két fél részfa megcserélésével : ⊗1000

1

0

1

1 0

1

0111

0

0100

1

0011

0

0

0010

1

1

0001

0

0

0000

1

1110

0

1101

1

1100

0

1

1

0110

0 0

1011

1

1001

1000

0

1

1010

0

1

1111

0

1

0101

0

(c) Utána a minden szomszédos nyolcad megcserélésével : ⊗0010

0

1

0

1

0101

1

1

0100

0

0110

1

0

0001

0

1

1

0000

1

0011

0

0

0010

1

1

1101

0

1111

1

1110

0

0 0

1001

1

1011

1010

0

1

1000

0

1

1100

0

1

0111

0

(d) Az 1000 ⊗ 0010 = 1010 egyed a 0000 helyre került

5.1. ábra. A Kademlia átfedő átrendezése. Az átrendezéssel egy adott egyed a 0 pontba helyezhető, miközben az egyedek távolsági viszonyai nem változnak


67

eljárás : broadcast(szöveg, magasság) ciklus i=magasságtól címbitek számáig ha az i. vödör nem üres, akkor i. vödörből egyed választása véletlenszerűen üzenet küldése az egyednek, tartalma: üzenet, i+1 ciklus vége eljárás vége 5.2. ábra. Az implicit fás üzenetszórás

5.2. Üzenetszórás megvalósítása a Kademlia átfedőben 5.2.1. Üzenetszórás elárasztással Az üzenetszórás megvalósítására a naív megoldás az, ha minden egyed az összes általa ismert egyednek továbbítja az üzenetet. Az üzeneteket az egyedek így többször is megkaphatják, ezért egyedi azonosítóval kell ellátni azokat. A többszörözött üzeneteket az egyedek ezáltal felismerik ; másodjára már nem továbbítják és nem is dolgozzák fel azokat. Ez a megoldás egyszerű, de igen nagy hálózati forgalmat generál, különösen nagy k-vödrök esetén. A gyakorlatban ezért nem érdemes alkalmazni. Referenciaként mégis használható; megmutatja ugyanis a azt legrövidebb időt, amennyi alatt az üzenetszórás elvégezhető. Ha az üzenet az összes lehetséges utat bejárja, akkor a legrövidebbet is. A strukturált átfedők beépített topológiája, szervezettsége lehetőséget biztosít az üzenetszórás ennél kevésbé költséges kivitelezésére. Ennek oka az, hogy a meglévő topológián kis számú, a Kademlia esetében logaritmikus számú lépéssel elérhető bármely egyed. Az üzenetszóráshoz nem szükséges új kapcsolatokat kialakítani, a meglévő topológia implicit módon többesadás faként használható (multicast tree), vagyis azzal az átfedő címtere partícionálható. Az új kapcsolatok létrehozása az üzenetszórást csak lassítaná.

5.2.2. Üzenetszórás a topológia felhasználásával A Kademlia átfedőre a struktúrát kihasználó üzenetszórás eljárást dolgoztam ki, amelyet az alábbiakban mutatok be. A tárgyalt eljárás N − 1 üzenet küldését igényli, ahol N az átfedő mérete. Ez szemlélet alapján is láthatóan az elvi minimum. Az algoritmus lényege, hogy az üzenetszórást indító egyed minden távoli részfából kiválaszt egy egyedet, és elküldi azoknak az üzenetet. A részfákon belül pedig ezek az egyedek felelősek az üzenet továbbításáért. A Kademlia eljárásban minden egyed rendelkezik a tőle távolabbi, de egyre kisebb részfákból más egyedek IP címével. Ezek az egyre kisebb, fél, negyed, nyolcad stb. részfákhoz tartozó, 2.3. ábrán is látható k-vödrök. Az üzenetszórás ezek mentén történik. Az indító egyed elküldi az üzenetet a tőle távoli fél részfából egy egyednek. Az felelős azért, hogy azon a részfán belül tovább szórja az üzenetet. A küldő egyed pedig azért felelős, hogy a saját részfáján belül tovább ossza azt. Ezért elküldi azt a saját fél részfáján belüli, de negyed részfáján kívüli egyednek; az felelős a távoli negyed részfán belüli szórásért, saját maga pedig a saját negyed részfáján belüliért. Így folytatja ezt az egyed addig, amíg el nem fogynak a részfák, megvalósítva az 5.2. ábrán látható algoritmust.

5. FEJEZET. ÜZENETSZÓRÁS A KADEMLIÁBAN 000* 001* 00* 01*

68

0* 1* 0

0 0

3

0

1 0

1 0 1 0 1 0 1

1

0 1

0

1 0 1

0 1 0 1

0 1 0 1

1 0

1 0 1

0 1

1 0 1

0 1

2 1

5.3. ábra. Üzenetszórás a Kademlia átfedőben

Ugyanígy hajtják végre az algoritmust a távoli részfák egyedei is. A távoli fél fáért felelős egyed a vele együtt fél részfában, de tőle külön negyed fában lévő egyednek továbbítja az üzenetet; a saját negyed fájáért pedig önmaga felelős és így tovább. Mivel ezeknek az egyedeknek tudniuk kell, hogy mekkora részfáért felelősek, az üzenet tartalmaz egy kicsi egész számot, amely a részfa bitjeinek számát mutatja. Minden egyed a megadott méretű és annál kisebb részfákba küldi tovább az üzenetet. Mivel az üzenetszórás így a részfák szerint halad, nincsen szükség további útválasztási információra, hanem a meglévő útválasztási táblázatok, a k-vödrök használhatóak. Az üzenetszórásra egy példát az 5.3. ábra mutat be. Itt a legkisebb, 00000 című egyed indítja az üzenetszórást. A véletlenszerűen kiválasztott egyedek is mindig a lehető legkisebb címűek. (Ez az 5.1. alfejezetben bemutatott eljárás alapján bármilyen általános esetre áttranszformálható, mivel az egész fa, illetve a távoli részfák külön a megfelelő módon átrendezhetőek.) Az üzenetszórást indító egyed (bal szélen) elküldi az üzenetet az 10000 című egyednek (1-es jelzésű üzenet), amelyik azon belül felelős a további szórásért, vagyis az 1∗ című egyedekért. Önmaga pedig felelős a 0∗ című egyedekért, vagyis továbbítja az üzenetet a 01∗ című egyedek közül az egyiknek (2-es jelzésű üzenet). Az felelős a 01∗ fáért, önmaga pedig a 00∗ fáért. Ezért küld egy üzenetet a 001∗ fából valamelyiknek (3-as jelzésű üzenet), és önmaga pedig kezeli a 000∗ részfát. Mivel azon belül nincsen már további egyed, az eljárás számára befejeződik; a távoli fákban pedig a kijelölt egyedek továbbítják, immáron tőle függetlenül, az üzenetet. Az 10000 számú egyed által küldött üzeneteket a szaggatott nyilak mutatják. A kieső és a rosszindulatú egyedek hatása A fenti algoritmus legfőbb gyengesége az, hogy a küldött üzenetei eltérő fontosságúak, az egyedek felelőssége az algoritmusban pedig nagyságrendileg különböző. Minden részfa kijelölt egyedei a részfa méretétől függetlenül felelnek az azon belüli üzenetszórásért. Így egyetlen üzenet kézbesítésétől és feldolgozásától függhet az, hogy az egyedek akár fele megkapja-e az üzenetszórást, vagy nem. Az 5.4. ábra a szimulált üzenetszórások közül egy olyat mutat,


69

0

0

0

0

0 1

1

1

1

0

0 1

0

0

1

0

0 1

0 1

1

0 1

1

1

0

0

0 1

0 1

0

1

0

1

0 1

1

0 1

0 1

0 1

1

1

0

0 1

0

1

0

1

1

0

0

0

0 1

0 1

0 1

1

0 1

5.4. ábra. Üzenetszórás a Kademlia átfedőben – eldobott üzenetekkel

amelyen a probléma jól látható. Az ábrán a feketén jelöltek azok az egyedek, amelyekhez nem jutott el az üzenetszórás. Egy i = 2 szintű üzenet elveszte miatt a jobb oldali negyed részfa teljesen kimaradt. Ez a probléma üzenetek elvesztése, az egyedek hálózatból kiesése, vagy a gyakori ki- és belépések miatti hibás útválasztási táblázatok miatt is jelentkezhet. Ezeken felül a hálózatba rosszindulatú egyed is épülhet, amely megteheti azt, hogy nyugtázza az üzenetszórást, vállalva annak elvégzését a saját részfájában belül, de utána valójában nem végzi el azt [75]. Ha az algoritmus egy ilyen rosszindulatú egyedet választ ki egy részfán belüli üzenetszórás elvégzésére, akkor az elveszett üzenetekhez hasonlóan teljes részfák maradhatnak ki. Az elveszett üzeneteknek és a rosszindulatú egyedek beépülésének az üzenetszórás szempontjából ugyanaz a hatása. Az egyedek eltérő mértékű felelőssége, és az üzenetek eltérő fontossága nem csak az üzenetszórás sikerességén, hanem egyéb mérhető tulajdonságain is látszik. Az 5.3. alfejezet szimulációs eredményein látható ennek az üzenetszóráshoz szükséges időre gyakorolt hatása is. Egy lassú hálózati kapcsolat késleltetési ideje például beépülhet egy, az egyedek jelentős részének küldött üzenet kézbesítésének idejébe. Ez okozza a mért üzenetszórási idő nagy szórását. A rosszindulatú egyedek szándékaiktól függő elhelyezkedése az átfedőben Mivel az algoritmusban a részfákból tetszőlegesen választhatóak ki a felelős egyedek, nincsenek a hálózatban olyan kulcsfontosságú helyek, ahova elhelyezkedve a rosszindulatú egyedek célzottan gyengíteni tudnák az üzenetszórás hatékonyságát. Ha az egész átfedő üzenetszórás forgalmát szeretnék akadályozni, akkor egyenletesen kell szétszóródniuk. Egy esetleges támadó akkor tud a legtöbb kárt okozni, ha – erőforrásaitól függően – minél több rosszindulatú egyedet épít be a hálózatba. Ezzel növeli a Ph valószínűséget, amellyel egy üzenet elveszését jelöljük. A véletlenszerű egyedkijelölés miatt Ph ≈ Nh /N , ahol Nh a rosszindulatú, N pedig az összes egyed


70

0 0 1

1 P

P

0 1

1

1 P

0

P

1

1 P

P

P 5.5. ábra. Az üzenetszórás hibái 2 és 4 egyed esetén

száma. Vagyis a támadónak az átfedő egészével összemérhető erőforrásokkal kell rendelkeznie. Ha kifejezetten egy adott egyed kimenő üzenetszórás forgalmát próbálják a rosszindulatú egyedek megbénítani, akkor olyan részfákban kell elhelyezkedniük, amelyekből felelőseket jelöl ki az. Ezek az adott méretű, vele közös fákon belül a tőle távoli részfák, amelyek az 5.3. ábrán is láthatóak szürkével jelölve. Viszont ezek tulajdonképpen az egész fát lefedik, az egyedet saját magát kivéve. Ezért ebben az esetben is mindössze annyit tehetnek a támadók, hogy megpróbálják a címtérben egyenletesen elosztva elhelyezni az irányításuk alatt lévő, rosszindulatú egyedeket. A fentiek alapján általában feltételezhető az, hogy a hálózatban a rosszindulatú egyedek egyenletesen helyezkednek el. Az egyetlen speciális eset, amikor célzottan tudnak támadni, az az, ha azt szeretnék megakadályozni, hogy egy adott egyedhez eljussanak a máshonnan érkező üzenetszórások. Minél távolabb van egy egyed az üzenet forrásától, annál valószínűbb, hogy valamelyik szomszédjának közvetítése révén kapja meg azt. Ezért ha a közelébe több rosszindulatú egyed is települ, akkor megnő annak a valószínűsége, hogy egyes üzenetszórások nem érnek el hozzá. A helyesség becslése Az algoritmus helyessége, vagyis az egyedek aránya, amelyekhez az üzenetszórás eljut, meghatározható az egyes üzenetek kézbesítési valószínűségeinek vizsgálatával. Ezt mutatja az 5.5. ábra. Annak a valószínűségét, hogy egy üzenet nem kerül feldolgozásra (mert az elveszik, vagy rosszindulatú egyedhez kerül), Ph -val jelöljük. A helyes kézbesítés és feldolgozás valószínűsége ekkor minden üzenetre P = 1 − Ph . Két szomszédos egyed (az 5.5. ábra bal oldalán) esetén az üzenetetet megkapó egyedek száma a következőképpen alakul: a bal oldali egyed biztosan megkapja az üzenetet, hiszen az indítja; ezért az 1-gyel járul hozzá az összes kézbesítések számához. A jobb oldali egyed csak akkor kapja meg, ha a nyíllal jelölt üzenet nem veszik el, vagyis P valószínűséggel. Így P egyben annak várható értékét is megadja, hogy a jobb oldalon lévő egyetlen egyed mennyivel járul hozzá az összes egyedek számához. Ezért a két egyedből álló páros esetén a várható érték 1 + P lesz. Ha a fa mérete kétszer ekkora, vagyis négy egyedből áll, akkor annak egyes részfáin belül


71

0 0 0 0 1

1

0 0

1 0 1

0 1

P2

P2

P

1

P

P2

0

1 0 1

0 1

P3

P2

P2

1 0

1 0 1

0 1

P3

P3

1 0 1

P3

P4

P2

P P

5.6. ábra. Az üzenetszórás hibáinak becsléséhez

ugyanez ez a helyzet. A bal oldali részfában biztosra vehetjük, hogy az üzenetszórás helyesen megtörténik, hiszen azért maga az indító egyed felel. Az üzenetet összesen megkapó egyedek számához a bal oldali részfa 1 + P -vel járul hozzá. A jobb oldali részfában csak akkor történik meg az üzenetszórás, ha az annak a részfának szóló üzenet nem veszett el; ennek valószínűsége ugyancsak P . Ha ez megtörténik, akkor az a részfa 1 + P -vel járul hozzá az összeghez, ha nem, akkor pedig 0-val. Ennek várható értéke P (1 + P ). A kettő összege (1 + P ) + P (1 + P ), azaz (1 + P )(1 + P ) = (1 + P )2 . A gondolatmenetet általánosítva az üzenetszórást megkapó egyedek számának várható értéke: M = (1 + P )b , (5.3) ahol b a fa magassága; P pedig az egyes üzenetek helyes kézbesítésének valószínűsége. Az összes egyedek számára vonatkoztatva a következőt kapjuk: 1+P m= 2

b (5.4)

A helyesség becslése a lépésszám vizsgálatával A helyességre vonatkozó egyenlet egy másik gondolatmenettel is belátható, az 5.6. ábra alapján. Az ábrán egy olyan átfedő látható, amely 4 bites címeket használ. Ebben minden lehetséges címen van egyed, ezért összesen 24 = 16 darabot tartalmaz. Az üzenetszórás a bal oldali, 0000 című egyedtől indul. Ez az átfedőből a jobb oldali fél részfán belüli üzenetszórásra az 1000 egyedet jelöli ki; ezen üzenet célba érésének valószínűsége P . Ugyanígy P a valószínűsége a többi, 0000 által kijelölt egyedeknek (0100, 0010, 0001) küldött csomagok célba értének. Ezek azok az egyedek, amelyek első kézből kapják meg a küldőtől az üzenetet. Ezután továbbadják azt; a továbbadás sikerességének valószínűsége úgyszintén P . Vagyis annak valószínűsége, hogy egy egyed másodkézből megkapja az üzenetet, P 2 lesz. Így történik ez a többi egyednél is: a harmadkézből értesülőkhöz P 3 valószínűséggel jut el az üzenet és így tovább. Minél több lépésen keresztül kap meg egy egyed egy üzenetet, annál kisebb a valószínűsége annak, hogy végülis eljut hozzá. Ha a lépések száma l, akkor ez a valószínűség P l . A lépések


72

NodeID

Hammingtávolság

egyedek üzenetet valószínűség száma megkapják b b 0 P0 0 0 P

0000

0

0001 0010 0100 1000

1

b 1

P1

b 1 1 P

0011 ... 1100

2

b 2

P2

b 2 2 P

b

b b

Pb

b b b P

... 1111

5.1. táblázat. Az átfedő egyedei a Hamming-távolság szerint növekvő sorrendben

száma megegyezik az egyed és az eredeti feladó azonosítójának Hamming-távolságával, mivel minden továbbításkor az üzenet a távoli részfába kerül, amelynek címében a magasság szerint következő bit negáltja a küldőének. Például a 0000 egyedtől indított üzenetszórást az 1000, 0100, 0010 és 0001 egyedek is P valószínűséggel fogják megkapni, mert a Hamming-távolságuk 1. Az 1100, 1010, 1001. . . egyedek pedig P 2 valószínűséggel, mert Hamming-távolságuk 2. A fentiek alapján minden egyedre meghatározható, hogy mekkora valószínűsségel kapják meg az üzenetet. Ez az 5.1. táblázatban látható. A Hamming-távolság lehetséges tartománya [0, b], ahol b az átfedő címbitjeinek száma, azaz a fa magassága. A megadott Hammingtávolsággal rendelkező egyedek száma a binomiális együtthatók segítségével számítható; ezt szorozva az üzenetek helyes kézbesítésének valószínűségével kapjuk meg az egyedszám várható értékét. Az összes egyedek száma, akikhez az üzenetszórás eljut, ezek összege, vagyis : ! b X b i M= P i

(5.5)

i=0

Ez az egyenlet az 5.3 egyenlettel teljesen azonos; az abban szereplő hatványt éppen így lehet tényezőkre bontani, a matematikából ismert binomiális tétel alapján. A helyesség függetlensége a címbitek számától Az 5.4. egyenlet alapján az algoritmus helyessége látszólag függ az átfedő címbitjeinek a számától. Ez azonban nem a címbitek számától való függést jelenti, hanem az egyedek számától való függést. A levezetésekben ugyanis minden lépésben a címtér telítettségét feltételeztük. Ezért ez a paraméter tulajdonképpen az egyedek számával van összefüggésben. Telített címterű átfedő a valóságban nincs; a Kademliában használt 160 bites címtér esetén ez 2160 ≈ 1,46 · 1048 egyedet jelentene. A valóságos átfedőkben az egyedek száma ennél jóval


73

100% modell szimuláció

üzenetet megkapó egyedek aránya

90% 80% 70% 60% 50% 40% 30% 20% 10% 0% 0%

20%

40%

60%

80%

100%

eldobott csomagok aránya

5.7. ábra. Az üzenetszórás helyessége – a modell és a szimuláció összehasonlítása

alacsonyabb, legfeljebb 220 körül van; a címtér pedig szinte üres. Ezért az üzenetek továbbításánál az ugrások száma is jóval alacsonyabb. Az indító egyedtől a legtávolabbi egyedig nincsen szükség 160 lépésre, hanem legfeljebb 20-ra, ha az egyedek egyenletesen töltik ki a címteret. Az egyenletes eloszlás esetén az egyedek úgy helyezkednek el a fában, hogy a 160 bites címeknek az első 20 bitjét használják csak, a többi pedig nulla. A legtávolabbi egyedhez is ezért a kézbesítés valószínűsége legalább P 20 , ami P 160 -nál jóval magasabb.1 Mivel egy b címbittel rendelkező átfedőben N = 2b egyed lehet, b értéke a b = log 2 N összefüggéssel határozható meg. Ezt a címbitek látszólagos számának nevezem. Egy 106 egyedet számláló átfedő esetén például az egyenletbe b = 20-at helyettesítve, vagyis az átfedőt működését egy 20 bites címmel rendelkező átfedőével modellezve becsülhető meg az algoritmus helyessége, mert az összes egyedszám 220 ≈ 106 . Az 5.7. ábrán ezen modell által becsült helyesség látható, összevetve a szimulációban kapott eredményekkel. A szimulációs eredmények 50 futtatás átlagát mutatják. A helyesség a rosszindulatú egyedek megjelenésével gyorsan romlik. Ez indokolta a következő, 5.2.3. szakaszban bemutatott algoritmus kidolgozását. 1 Mivel

0 < P < 1, a kisebb kitevő nagyobb valószínűséget jelent.


74

eljárás : broadcast(azonosító, szöveg, magasság) ha az azonosító már ismert eljárás vége ismert üzenetek tárolójába bejegyzés: azonosító ciklus i=magasságtól címbitek számáig ha az i. vödör nem üres, akkor i. vödörből kb egyed választása véletlenszerűen üzenet küldése mind az kb az egyednek, tartalma: azonosító, szöveg, i+1 ciklus vége eljárás vége 5.8. ábra. Javított algoritmus: implicit fás üzenetszórás replikációval

5.2.3. Üzenetszórás a topológia felhasználásával és replikációval A javított algoritmus lényege megegyezik az előzőével: minden egyre kisebb részfából felelősök osztják tovább az üzenetet, míg a saját részfájáért az üzenetszórást indító egyed felelős. A különbség az, hogy nem egy, hanem több egyednek is elküldi az üzenetet, vagyis több felelős egyedet jelöl ki egy részfán belül. Ezzel lehet kivédeni a csomagvesztések és a rosszindulatú egyedek hatását. Az algoritmus leírása az 5.8. ábrán látható. A felelősök számát, vagyis a replikációt itt kb -vel jelöljük. Szintje kétszerestől a k-vödrök méretéig terjedhet. (Vagyis kb ≤ k kell legyen, mivel több felelős esetén FIND_NODE lekérdezésekre lenne szükség.) Ebben az algoritmusban is lehetséges többszörös kézbesítés, ezért az üzeneteket nem csak a részfa magasságával, hanem egy kvázi-egyedi azonosítóval is el kell látni, hogy a többszörös feldolgozást el lehessen kerülni. A részfánként több felelős kijelölése csökkenti annak a valószínűségét, hogy az üzenet elveszik, vagy rosszindulatú egyedhez kerül, és emiatt kimarad az a részfa. Ha egy üzenet elveszítésének vagy rosszindulatú egyedhez kerülésének a valószínűsége Ph , akkor kb kiküldött k üzenet esetén ez Ph b -ra csökken, mivel egymástól független eseményekről van szó.2 A helyes k

kézbesítés és az adott részfán belüli üzenetszórás megkezdésének valószínűsége így 1 − Ph b -re javul. Például Ph = 10% esetén kétszeres replikáció, azaz kb = 2 a hibás kézbesítés valószínűségét Ph2 = 1%-ra csökkenti, ezzel pedig a megbízhatóságát P = 90%-ról P = 99%-ra javítja. A replikáció növelésével az eljárás tetszőleges mértékben megbízhatóvá tehető, de tökéletesen megbízható nem lehet, ahogyan azt az 5.3. alfejezet szimulációs eredményei mutatják.


75

100% modell szimuláció


90% 80% 70% 60% 50% 40% 30% 20% 10% 0% 0%

20%

40%

60%

80%

100%


5.9. ábra. Az üzenetszórás helyessége kb = 3-szoros replikáció esetén

A szükséges replikációs szint meghatározása A rosszindulatú egyedek vagy csomagvesztések arányának ismeretében a szükséges replikáció k előre becsülhető. A P = 1 − Ph b becslést az 5.4. egyenletbe helyettesítve kapjuk: b   2 − Phkb   m =   2 

(5.6)

amit kb -re megoldva, és egész értékre felfelé kerekítve (mivel a replikáció csak egész szám lehet) az alábbi összefüggéshez jutunk:  √   ln 2 1 − b m   kb =  (5.7)  ln Ph   Ebben n az előírt helyesség, Ph a csomagvesztés vagy hibás egyedek aránya, b pedig az átfedő címbitjeinek látszólagos száma, amely a b = log2 N képlettel számítható ki az átfedő N egyedszámából. (Az átfedő mérete a címtér telítettségéből, vagyis az egyedek egy adott pont körüli 2 Ha

ténylegesen elvesző üzenetről van szó, és az adatvesztést a távoli egyed vagy annak hálózati kapcsolata hibája okozta, akkor az két különböző egyednél egymástól független lesz. Ha rosszindulatú egyedről van szó, akkor pedig az 5.2.2. szakaszban tárgyaltak alapján számítani lehet rá, hogy a rosszindulatú egyedek egyenletesen helyezkednek el a hálózatban, és amiatt függetlenek az üzenetvesztések.


0 0

76

1

1

0

1 P

P

P

5.10. ábra. Eltérő lépésszámú utak az üzenetszórásban replikáció esetén

sűrűségéből, becsülhető [17]. Mivel ez a pont lehet az üzenetszórást indító egyed közvetlen környezete is, amelyet az útválasztási táblázatokból ismer, nem szükséges számára az átfedő globális ismerete. Így nem sérül a skálázhatóság elve.) A replikáció növelésével az üzenetek elveszítésének valószínűsége gyorsan csökken. Az 5.9. ábra szimulációs eredménye 3-szoros replikációt mutat. A mért helyesség a becsültnél k valamivel jobb; az üzenetek elvesztésének Ph b -nal való becslése az eredményt alulról közelíti. Ez azért előnyös, mert így arra számíthatunk, hogy az 5.7. egyenlettel meghatározott replikációval a valós hálózat működése a becsültnél megbízhatóbb lesz. k A P = 1 − Ph b becslés pontosságát két hatás módosítja. A replikáció megbízhatóságot növelő hatását rontja az a tény, hogy nem használható az egészen kis részfák esetén. Ha egy adott részfa nem tartalmaz kb darab egyedet, akkor kisebb replikációt kényszerül használni az átfedő. Ennek ellenére a megbízhatóság az 5.9. ábra szimulációs eredménye alapján jobb az így becsültnél. Ennek oka, hogy a többszörös üzenetküldés miatt az üzenetek egynél többféle úton is eljuthatnak egy egyedhez. Az utak kevesebb lépésből állhatnak, mint a két egyed cím szerinti Hamming-távolsága (5.10. ábra). Ilyenkor az 5.5. egyenlet levezetésében az átlagos úthossz csökkenése miatt a P l tag l kitevője csökken, ami a megbízhatóság növekedését eredményezi. Az üzenetek száma és egyenetlen eloszlása az egyedek között Az üzenet fontossága ebben az algoritmusban nem változik az előzőhöz képest. A legfelső szintű üzenet továbbra is a fél fának szól, és annak felelősét jelöli ki. A replikáció ezért a nagy részfánál szóló üzeneteknél fontos az átfedő egészén futó algoritmus helyességét tekintve. A replikáció növelése azonban erőforrásigényes. Egy fél fáért felelős egyed kb = 1 esetén annyi üzenetet kell küldjön, amekkora az átfedő látszólagos címbitjeinek száma, kb = 2 esetén pedig kétszer annyit. A valóságos hálózatoknál az egyedszám legfeljebb 1 000 000 körüli, ami azt jelenti, hogy ezek egy 20 címbittel rendelkező hálózattal modellezhetőek. Kétszeres replikáció esetén ezért a fél részfáért felelős egyed 2 · (20 − 1) = 38 példányban kell elküldje az üzenetet. A kisebb részfákért felelős egyednek ennél kisebb lesz a kimenő forgalma.


77

5.3. Az üzenetszórások szimulációban mért eredményei Az 5.2. alfejezetben bemutatott üzenetszórási algoritmusok tesztelésére szimulátor programot fejlesztettem. A szimulátor alapja a 4.5. alfejezet méréseihez használt Kadsim. Ez állítja elő a szimuláció közben használt útválasztási táblázatokat. Az 5.2. alfejezet első algoritmusát a továbbiakban elárasztásnak fogom nevezni, míg a második algoritmusra implicit fa néven, a harmadikra pedig javított algoritmusként fogok hivatkozni. A fő cél a javított algoritmus alkalmazásának lehetővé tétele. Az elárasztás ugyanis túl nagy hálózati terhelést okoz, ezért a gyakorlatban nem célszerű a használata, az implicit fás algoritmus pedig csomagvesztés vagy rosszindulatú egyedek jelenléte esetén megbízhatatlan. Ugyanakkor tény, hogy az utóbbi által okozott hálózati terhelés minimális, ezért a szimulációjával megvizsgálható az, hogy milyen eredmények érhetők el az elvi legalacsonyabb számú, N − 1 darab üzenet küldésével. A szimulátor mind a három üzenetszórási algoritmust implementálja. A szimuláció segítségével az algoritmusokat a következő szempontok szerint vizsgáltam: – a küldött üzenetek száma, az üzenetszám várható értéke egyedenként, – az üzenetszórásban résztvevő egyedek száma és aránya, – az üzenetszóráshoz szükséges idő, vagyis az időpont, amelykor az összes egyedhez eljut az üzenet.

5.3.1. Az üzenetek száma egyedenként Az üzenetszórás elvégzéséhez szükséges üzenetek számát a replikáció és az egyedszám függvényében vizsgáltam. Az itt közölt eredményeknél az üzenetszám mindig egy egyedre vonatkoztatva szerepel, vagyis az összes üzenet és az egyedek számának hányadosát mutatják az 5.11. ábra grafikonjai. Ez mérőszáma az algoritmus hatékonyságának, mivel megmutatja, hogy egy egyednél mennyi hálózati forgalom keletkezik. Az elvi legalsó értéke ennek 1. Ennél kevesebb üzenet azt jelentené, hogy vannak olyan egyedek a hálózatban, amelyek egyáltalán nem kapták meg az üzenetet. Replikáció esetén az eljárásban lehetséges többszörös kézbesítés, vagyis az, hogy egy egyed többször kapja meg ugyanazt az üzenetet. Ha egy üzenetet több úton is megkap, az azt is jelenti, hogy egy adott időpillanatban több helyen lehet még a hálózatban útban felé ugyanaz az üzenet. Ez a jelenség hatással van az algoritmus üzenetszámára. Ezt illusztrálja az 5.12. ábra. Ezen egy öt egyedet tartalmazó átfedő látható, amelyben a 0, 4, 5, 6 és 7 címen helyezkednek el azok. Tegyük fel, hogy az 5.12(a) ábrán látható módon üzenetszórást indít a 0 című egyed. Ez a távoli fába kb = 2 replikáció esetén két egyednek küldi el az üzenetet, a 4 és 6 címűeknek (fekete nyilak). Mindkét egyed tovább osztja az üzenetet : a 4-es című a távoli negyed fájába a replikáció miatt a 6-os és 7-es egyednek is; és a szomszédjának, az 5-ösnek (kék nyilak). A 6-os egyed hasonlóképp cselekszik, a 4, 5 és 7 számúaknak küldve az üzenetet (piros nyilak). Ez összesen 8 üzenetet jelent.3 3A

6-os és 7-es egyed között ekkor még lehet üzenet, de ezt most elhanyagoljuk.


78

Üzenetszám növekvő replikációra; 20000 egyed

Üzenetszám növekvő egyedszámra; k=2

35

5 King Mainline BT konstans

30

King Mainline BT konstans 4.5

üzenetek száma

üzenetek száma

25 20 15

4

3.5

10 3 5 0 1

2

3

4

5

6

7

8

9

10

2.5 2000

8000

replikáció

14000

20000

egyedszám

5.11. ábra. Üzenetek száma egyedenként a bemutatott üzenetszórás algoritmusban, különböző késleltetési idő eloszlások mellett

(a) egyforma késleltetési idők

(b) nem egyforma késleltetési idők

5.12. ábra. A késleltetési idők eloszlásának hatása az üzenetszórás hatékonyságára Ha a késleltetési idők erősen eltérőek, akkor az üzenetszórás másképp is lejátszódhat. A 0 című egyed indítja az üzenetet az 5.12(b) ábrán is, a 4 és 6 címűeknek elküldve a fekete nyilak mentén. Tegyük fel most azonban, hogy a 6-os egyed felé a szaggatott nyíl menti kapcsolat lassú. A 4-es egyed hamar megkapja az üzenetet, a 6-os pedig még sokáig nem. Ilyenkor a 4-es tovább osztja azt ; a távoli negyed fában tudja alkalmazni a replikációt, a közeliben pedig már csak egy egyed van. A kék nyilak mentén is gyorsan lejátszódik az üzenetküldés. Amikor ezek célba érnek, akkor minden egyed megkapta az üzenetet. Ha a szaggatott nyíl szerinti üzenet ekkor megérkezik, annak már nem lesz hatása, mivel eddigre a 6-os egyed már elvégezte az üzenetszórást. Az összes üzenetszám ezért csak 5.4 4 Itt

is, mint az előbb, a 6-os és 7-es egyedek között még lehet egy üzenet.


79

Ez a jelenség megfigyelhető a szimulációs eredményeken is, amelyeket az 5.11. ábra mutat. A King data set késleltetési idejeivel szimulált átfedők nagyobb üzenetszámmal valósították meg az üzenetszórást, mint a Mainline BitTorrent átfedő késleltetési időivel szimuláltak. Az előbbiben a késleltetési idők 0,01–1 s közöttiek, az utóbbiban pedig 0,01–18 s között vannak (lásd a 2.6. ábrát). Ellenőrzésképp elvégeztem egy olyan fiktív átfedő szimulációját is, amelyben minden késleltetési idő egyforma. Ahogyan az előzőek alapján várható is, így jóval magasabb üzenetszámokat kaptam. Látható, hogy a replikáció növelésével az üzenetszám gyorsan növekszik. Ennek oka az, hogy egy egyed több úton megkaphatja ugyanazt az üzenetet. Üzenetek száma más algoritmusoknál Az irodalomban bemutatott legtöbb algoritmus a minimális üzenetszámra törekszik (a részleteket lásd a 2.3. alfejezetben). Ennek elvi alsó határa N − 1. Az „Efficient Broadcast Algorithm” nevű algoritmus minden egyedtől visszajelzést vár az üzenetszórások elvégzéséről [25], így abban 2 · (N − 1) üzenet terheli az átfedőt, vagyis az egyedenkénti átlagos üzenetszám ott 2. Ez alacsonyabb, mint az itt bemutatott algoritmus terhelése, azonban lényegesen lassabban tud csak működni ennél. Az egyedek (gyermekek) a visszajelzést csak akkor tudják megadni az őket kijelölő egyedeknek (szülők), amikor az összes általuk kijelölt gyermek már visszaküldte azt. Ha ezek közül bármelyikre várni kell, akkor a visszajelzés a saját szülője felé is késni fog. Az 5.11. ábrán látható, hogy a több felelős kijelölése más algoritmusokhoz képest nagyobb terhelést jelent. A megbízhatóságot azonban hatásosabban erősíti, ahogyan azt az 5.14. ábra is mutatja.

5.3.2. Az üzenetszórás helyessége Az üzenetszórások sikerességét egy 1 000 egyedet számláló átfedő szimulációjával határoztam meg. A szimuláció során a javított algoritmust vizsgáltam, és ezzel együtt kb = 1 esetben az implicit fás algoritmust is; a javított algoritmus replikáció nélküli változata megfelel az utóbbinak. Az eredmények az 5.13. ábrán láthatóak. Minden pont egy szimuláció eredményét jelzi. Az x tengely az eldobott csomagok arányát mutatja. Mivel az algoritmusok tetszőlegesen jelölhetik ki a felelős egyedeket, a szimulátor az eldobandó csomagokat egyenletes eloszlással, véletlenszerűen választotta ki. (Az 5.2.2. szakaszban tárgyalt okok miatt a beépülő rosszindulatú egyedeknek pontosan ugyanilyen az üzenetszórásra tett hatása.) Az y tengely azon egyedek arányát mutatja, amelyekhez az üzenetek eljutottak. Ideális esetben ez 100%, vagyis az összes egyed. Az implicit fás algoritmus eldobott csomagok (kieső vagy rosszindulatú egyedek) esetén megbízhatatlan. Mivel az eljárás üzenetei eltérő fontosságúak, a tárgyaltak alapján egyetlen elvesző üzenet akár 50%-os hibát is okozhat, ha egy fél részfának szól, de a hatása lehet elenyészően kicsi is. Ez azt eredményezi, hogy a helyesség szórása változatlan csomagvesztés mellett, de különböző szimulációk között nagy. Ezt mutatja az ábrán a kb = 1 eset szimulációja. Az üzenetszórást indító egyed távoli fél részfának szóló üzenete, ha elveszik, a helyesség már nem lehet nagyobb 50%-nál, ha a távoli negyednek szóló veszik el, akkor 75%-nál és így tovább. Ez figyelhető meg az ábrán az 50%-tól, 75%-tól, 87,5%-tól stb. induló csomósodásoknál. A javított algoritmussal a csomagvesztések hatása a replikációval hatványozottan csökkenthető. kb = 2, vagyis kétszeres replikáció esetén a Ph = 10%-os csomagvesztés Ph = 1%-osnak


80

100% 93.75%

90%

87.5%

80% 75%

helyesség

70% 60% 50%

50%

40% 30% 20% 10% 0% 0%

2%

4%

6%

8%

10%

0%

eldobott csomagok aránya, kb=1

2%

4%

6%

8%

10%

eldobott csomagok aránya, kb=2

5.13. ábra. Az üzenetszórást megkapó egyedek aránya az eldobott csomagok függvényében. A replikáció nélküli (kb = 1), és kétszeres replikáció (kb = 2) esetén a szimulációk száma megegyezett. kb = 2 esetén a pontok nagy része átfedi egymást.

felel meg. A szimulált esetek jelentős hányadában, 95%-ában a helyesség 98% feletti. Az esetek elenyésző hányadában mégis előfordulhat az, hogy pont mind a kettő (vagy több, ha kb > 2) fél részfának szóló üzenet rosszindulatú egyedhez kerül. Ezért az algoritmus tökéletesen nem képes garantálni a nagy arányú helyességet. A replikáció növelésének helyességre gyakorolt hatását az 5.14. ábra mutatja. A távoli egyedek hálózati hibái függetlenek, a rosszindulatú egyedek pedig egyenletesen helyezkedhetnek el, ezért a hibák aránya hatványfüggvény szerint csökken, amelynek a kitevője kb . Például a Ph = 20%-os hiba kb = 3-szoros replikáció esetén mindössze Ph3 = 0.8%-osnak tekinthető. A helyesség várható értéke így 99%. A rosszindulatú egyedekre nézve, mivel az 5.2.2. szakasz gondolatmenete alapján a ezek számára az átfedőbe beépülés erőforrásigényes feladat, az alacsonyabb Ph értékek tekinthetők reálisnak. Az eljárás rugalmassága miatt – miszerint az egyes részfákból bármely egyednek küldhető az üzenet – alacsony replikációval is megbízható működést lehet elérni. Más algoritmusok helyessége egyedek hibái esetén Az irodalomban bemutatott minimális költségre törekvő algoritmusok törékenyek, mivel minden elvesző üzenet egy vagy több egyed számára jelenti azt, hogy az üzenetszórásból kimaradnak. Ezeket a hibákat egyedek hibás útválasztási táblázatai is okozhatják, amelyeket a gyors be- és kilépések okoznak. Az Efficient Broadcast nevű algoritmus [15] helyessége drasztikusan romlik már akkor is, ha az átfedők átlagos élettartama fél óra alá csökken [24], miközben üzenetszórás teljes elvégzéséhez szükséges idő ennél nagyságrendekkel rövidebb


81

100% kb=1 kb=3


90% 80% 70% 60% 50% 40% 30% 20% 10% 0% 0%

20%

40%

60%

80%

100%


5.14. ábra. Az üzenetszórás sikerességének javítása replikációval

(fél perc körüli). Az itt bemutatott javított algoritmus, bár az egyedek terhelése nagyobb, még 20% hiba mellett is 99%-os helyességet biztosít kb = 3 replikáció mellett. A 20% hibába beleszámíthatjuk az útválasztási táblázatok hibáit is, hiszen az algoritmus a k-vödrökből véletlenszerűen választhat felelősöket, és emiatt nincs jelentősége a hibák típusának.

5.3.3. Az üzenetszóráshoz szükséges idő A program modellezi az üzenetküldések késleltetését is. A mérésekhez két, az Interneten történt valódi mérésekkel előállított késleltetési idő adatbázist használtam. Ezek a 2.4. alfejezetben, a 2.6. ábrán láthatóak. Az üzenetszórást akkor tekintem befejezettnek, amikor az utolsó egyed is megkapta az üzenetet. A művelet idejének szórása az algoritmus helyességéhez hasonlóan nagy. Ennek oka itt is az, hogy ha egy fontos, fél vagy negyed fának szóló üzenetnek lassú kapcsolaton kell keresztülhaladnia, akkor az azon részfa egésze számára lassítja az üzenetküldést. Az 5.15. ábra egy 10 000 egyedet számláló átfedő mérési adatait mutatja. A szimulációban 1 000 üzenetszórást indítottam különböző egyedektől ; az egyes üzenetszórások befejezéséhez szükséges idő eloszlása látható az ábrán. A kb = 1-es eset a replikáció nélküli esetet mutatja, amelyik egybeesik az implicit fás algoritmus eredményeivel. Ebben a minimális számú üzenetet használja az átfedő. A replikáció növelése a helyességen kívül az üzenetszórás idejét is javítja. Kétszeres replikációval (kb = 2) az üzenetszóráshoz csak fele akkora időre volt szükség, mivel különféle utakon is eljuthatott egy üzenet egyik pontból a másikba. Egy adott egyed a számára kijelölt részfában pedig így előbb tudta elkezdeni az üzenetszórást.


82

100% Mainline BT, k=1 Mainline BT, k=2

90%

üzenetszórások aránya

80% 70% 60% 50% 40% 30% 20% 10% 0% 10

20

30

40

50

60

üzenetszóráshoz szükséges idő [s]

5.15. ábra. Az üzenetszóráshoz szükséges idő eloszlása a Mainline BitTorrent átfedőben. A szórást az egyes hálózati kapcsolatok eltérő késleltetései okozzák

Az üzenetek továbbításához szükséges idő függ az egyedek számától. Minél nagyobb az átfedő, az üzenetszórást indító egyedektől annál több lépésre van szükség a legtávolabbiakhoz. Az üzenetszóráshoz szükséges időt az egyedeszám függvényében (1 000-től 20 000-ig) az 5.16. ábra mutatja. Mivel az átfedő átmérője, vagyis a bináris fa mérete az egyedszámtól csak logaritmikusan függ, az algoritmus futási ideje ezen a tartományon alig változik az egyedszámmal. A kijelölt felelős egyedek egymástól függetlenül, párhuzamosan végezhetik a saját tartományukon belül az üzenetszórást. Más algoritmusok üzenetszórási ideje Az üzenetszórás ideje a fizikai hálózat és az egyedek késleltetése mellett az algoritmusban használt partícionálástól függ. Az itt bemutatott algoritmusban az üzenetszórási fa magassága log2 N , ahol N az átfedő mérete. Ha a fa magasabb (mint a Partition-based Broadcast Algorithm esetében [76]), akkor az üzenetszórás ennél lassabb lesz. Az 5.15. ábrán látható, hogy replikáció alkalmazásával a megbízhatóság javítása mellett az üzenetszórás időtartama is hatékonyan csökkenthető, mivel az üzenetek átlagosan rövidebb késleltetésű kapcsolatokon keresztül is eljutnak a felelős egyedekhez. Erre ilyen módon más algoritmusokban nincsen lehetőség, mivel azok nem használnak replikációt.


83

40 King data set MainLine BT

30

üzenetszórás ideje [s]

20

10

5 4 3 2 0

2

4

6

8

10

12

14

16

18

20

egyedek száma [1000 db]

5.16. ábra. Az egyedszám és az üzenetszóráshoz szükséges átlagos idő összefüggése különféle átfedők esetén

6. fejezet Összefoglalás Értekezésem első része a Komondor elosztott betörésérzékelő és -védelmi eljárást mutatta be. Az eljárás célja, hogy az Internetről érkező férgek, kézzel kivitelezett és más jellegű támadások ellen növelje a védelmet. Működésének lényege, hogy az érzékelőket egy Kademlia alapú, alkalmazási szintű hálózatba kell szervezni, amely az érzékelt események feldolgozásához, és támadások esetén a riasztások küldéséhez megbízható közegként szolgál. A betörésérzékelés fontos problémája a feldolgozandó adatmennyiség kezelése. Elosztott érzékelő rendszer esetén a megnövekedett forgalom mellett gondoskodni kell a különböző helyen történt érzékelések közötti kapcsolat felismeréséről is, ugyanis előfordulhat az, hogy azok egy komplex támadás részét képezik. Munkám során megmutattam, hogy az érzékelők által generált adatok feldolgozása hatékonyan egy DHT alapú strukturált P2P átfedőn oldható meg. A hatékonyság tovább növelhető a Kademlia választásával, mivel ez tud legjobban igazodni annak a forgalomnak dinamikájához, amely betörések adatainak eltárolásakor keletkezik. A rendszer hatékonyságát azzal igazoltam, hogy megmutattam, hogy az egyes gazdagépeken okozott számítási terhelés és hálózati forgalom eloszlik azok között. Támadás érzékelésekor fontos követelmény, hogy az egyes Komondort alkalmazó szoftver egyedek minél hamarabb értesüljenek a veszélyről. Ennek megvalósítására kutatásaim során üzenetszórás algoritmust terveztem a Kademlia átfedőhöz. A DHT átfedők kereső szolgáltatásainak kiterjesztéséhez is használható az üzenetszórás. Ezekben a kulcsok alapján azonosított adatokat eredendően csak a kulcs pontos ismeretében lehet visszakeresni; az üzenetszórás alkalmazásával lehetségessé válik kulcsrészletekre történő keresés is. Így a Kademliára kidolgozott üzenetszórás általánosan alkalmazható új eredmény. Az algoritmus kidolgozása közben felismertem, hogy a Kademlia átfedők átalakíthatóak úgy, hogy egy kiválasztott egyed a 0 pontba kerülhet. Az átalakítás közben az átfedő egyedei közötti távolságviszonyok nem változnak meg. Emiatt a transzformált átfedő működésében, útválasztási táblázataiban és egyéb tulajdonságaiban megegyezik az eredetivel, csak más alkalmazási szintű hálózati címeket használ. A transzformált átfedőn az algoritmusok tervezése egyszerűbb. Ezt az eljárást az üzenetszórás bemutatásakor alkalmaztam. Értekezésemben a Kademlia átfedő működésének megbízhatóságát külön megvizsgáltam. Ennek során létrehoztam egy modellt, amely segítségével meghatározható a Kademliában használt rendszerszintű konfigurációs paraméter, a replikáció szintje. A modell által meghatározott replikációval a legkisebb szükséges terhelés mellett biztosítható az adatok egy előírt rendelkezésre állási szintje. A módszer, amely az adatok megbízható tárolását nyújtja, nem 84

6. FEJEZET. ÖSSZEFOGLALÁS

85

csak a Komondor esetében alkalmazható, hanem általánosan, bármely Kademlia átfedőben felhasználható. A modell mellett kidolgoztam egy szimulációs eljárást is, amely segítségével az adatok tárolásának hibái vizsgálhatóak. Ezek a hálózati hibák, például tűzfalak vagy csomagvesztés miatt jönnek létre. A modell helyességét a szimulációs eljárás megvalósításával ellenőriztem. A tárgyalt Komondor eljárás teszteléséhez jelentős fejlesztési munka is társult. A valós rendszeren, valós támadásokon történő teszteléshez implementáltam a Komondor alkalmazást. A saját átfedő hálózattal megvizsgáltam az eljárást; az értekezésben bemutatott eredmények igazolják a hatékonyságát.

Köszönetnyilvánítás Szeretnék mindenek előtt köszönetet mondani témavezetőmnek, Dr. Hosszú Gábornak, aki türelmével és végtelen sok segítségével támogatta doktori értekezésem létrejöttét. Köszönöm, hogy a P2P hálózatok felé irányította figyelmemet, elindítva ezzel azon az úton, amelyen most ez a dolgozat is létrejött. Szeretnék köszönetet mondani kollégáimnak, a Budapesti Műszaki és Gazdaságtudományi Egyetem Elektronikus Eszközök Tanszéke minden munkatársának, hogy munkámban támogattak és jó tanácsokkal láttak el. Külön szeretném megköszönni Dr. Rencz Márta tanszékvezető professzornak, hogy a kutatásomat mindvégig támogatta. Köszönöm Dr. Bognár Györgynek a motiválást, Szalai Albinnak a dolgozat formai kialakításában nyújtott segítségét. Köszönöm Nagy Gergelynek a hasznos és sokszor igen szórakoztató tapasztalatcserét. Szeretném megköszönni családomnak a sok támogatást, amely nélkül nem jutottam volna el idáig. Szeretnék köszönetet mondani Bárdi Júliának az összes elrabolt időért. Köszönöm a sok szeretet és türelmet, amellyel támogatott.

86

Saját közlemények [S1] Zoltán Czirkos and Gábor Hosszú. Peer-to-peer alapú betörésérzékelés. Híradástechnika, 63 :29–36, 2008. Pollák–Virág díjas cikk. [S2] Zoltán Czirkos and Gábor Hosszú. Distributed Detection of Intrusions. Informatika – a Gábor Dénes Főiskola Közleményei, XII(2):37–40, 2010. [S3] Zoltán Czirkos and Gábor Hosszú. Peer-to-peer Based Intrusion Detection. Infocommunications Journal, LXIV(I):3–10, 2009. [S4] Zoltán Czirkos, Loránd Lehel Tóth, Gábor Hosszú, and Ferenc Kovács. Novel Applications of the Peer-to-Peer Communication Methodology. Journal on Information Technologies and Communications – Research, Development and Application on Electronics Telecommunications and Information Technology, E-1(1(5)):59–70, 2009. [S5] Zoltán Czirkos and Gábor Hosszú. Enhancing the Kademlia P2P Network. Periodica Polytechnica, kézirat elfogadva, megjelenés alatt. [S6] Zoltán Czirkos and Gábor Hosszú. Műveleti rendszerek egyenrangú közlésen alapuló védelme. Informatika – a Gábor Dénes Főiskola Közleményei, 8(4):9–21, 2005. [S7] Zoltán Czirkos. Operációs rendszerek egyenrangú közlésen alapuló védelme. Linuxvilág, VII(5) :65–69, 2006. [S8] Zoltán Czirkos and Hosszú Gábor. A Distributed Intrusion Network Based on Kademlia. Computers & Security. Kézirat elküldve. [S9] Zoltán Czirkos and Hosszú Gábor. Pseudo Reliable Broadcast in the Kademlia P2P system. Computer Networks. Kézirat elküldve. [S10] Zoltán Czirkos, Lóránd Lehel Tóth, and Gábor Hosszú. Komondor – P2P Intrusion Prevention, poster. In Róbert Szabó and Attila Vidács, editors, HSN Workshop 2009, Balatonkenese, May 2009. [S11] Zoltán Czirkos and Gábor Hosszú. Az elosztott betörésérzékelés hatékonysága. In Informatika Korszerű Technikái, Dunaújváros, 2010. Dunaújvárosi Főiskola. [S12] Zoltán Czirkos and Gábor Hosszú. Üzenetszórás modern P2P hálózatokban. In Informatika Korszerű Technikái, pages 13–23, Dunaújváros, 2008. Dunaújvárosi Főiskola.

87

SAJÁT KÖZLEMÉNYEK

88

[S13] Zoltán Czirkos and Gábor Hosszú. P2P alapú betörésvédelem. In Informatika Korszerű Technikái, pages 45–52, Dunaújváros, 2007. Dunaújvárosi Főiskola. [S14] Zoltán Czirkos. P2P alapú biztonsági szoftver fejlesztése. In Információvédelem menedzselése XXII. Szakmai fórum, pages 43–47, Budapest, 2006. Hétpecsét Információbiztonsági Egyesület. [S15] Zoltán Czirkos and Gábor Hosszú. Usage of Broadcast Messaging in a Distributed Hash Table for Intrusion Detection. In Peyman Kabiri, editor, Privacy, Intrusion Detection and Response: Technologies for Protecting Networks. IGI Global, Hershey, 2011. [S16] Zoltán Czirkos and Gábor Hosszú. Reliability Issues of the Multicast-Based Mediacommunication. In Margherita Pagani, editor, Encyclopedia of Multimedia Technology and Networking, pages 1215–1223. Information Science Reference, Hershey, 2009. [S17] Zoltán Czirkos and Gábor Hosszú. On the Stability of Peer-to-Peer Networks in RealWorld Environments. In Antonio Cartelli and Marco Palma, editors, Encyclopedia of Information Communication Technology, pages 622–630. Information Science Reference, Hershey, 2008. [S18] Zoltán Czirkos and Gábor Hosszú. Application of the P2P Model for Adaptive Host Protection. In Margherita Pagani, editor, Encyclopedia of Multimedia Technology and Networking, pages 54–60. Information Science Reference, Hershey, 2009. [S19] Zoltán Czirkos and Gábor Hosszú. Peer-to-Peer Methods for Operating System Security. In Goran D. Putnik and Maria Manuela Cunha, editors, Encyclopedia of Networked and Virtual Organizations, pages 1185–1191. Idea Group Inc., Hershey, 2008. [S20] Zoltán Czirkos, Gábor Hosszú, and Kovács Ferenc. E-Collaboration Enhanced Host Security. In Ned Kock, editor, Encyclopedia of E-Collaboration, pages 172–177. Information Science Reference, Hershey, 2008. [S21] Zoltán Czirkos and Gábor Hosszú. Intrusion Detection Based on P2P Software. In Mehdi Khosrow-Pour, editor, Encyclopedia of Information Science and Technology, pages 2232–2238. Information Science Reference, Hershey, 2008. [S22] Zoltán Czirkos and Gábor Hosszú. A Novel Application of the P2P Technology for Intrusion Detection. In Antonio Cartelli and Marco Palma, editors, Encyclopedia of Information Communication Technology, pages 616–621. Information Science Reference, Hershey, 2008. [S23] Zoltán Czirkos and Gábor Hosszú. Network-based intrusion detection. In Mário Freire and Manuela Pereira, editors, Encyclopedia of Internet Technologies and Applications, pages 353–359. Idea Group Inc., Hershey, 2007.

Tézisekhez szorosan nem kapcsolódó közlemények [N1] Zoltán Czirkos. Többnyelvű programok létrehozása a GNU gettext rendszerrel. Linuxvilág, VII(6):15–17, 2006. [N2] Zoltán Czirkos. Grafikus program készítése GTK+-szal. Linuxvilág, VII(9) :18–21, 2006. [N3] Zoltán Czirkos. GNU Autoconf. Linuxvilág, VII(11):30–33, 2006.

89

Irodalomjegyzék [1] S. Androutsellis-Theotokis and D. Spinellis. A survey of peer-to-peer content distribution technologies. ACM Computing Surveys (CSUR), 36(4):335–371, 2004. [2] Gábor Hosszú. Az internetes kommunikáció informatikai alapjai. Budapest, Novella Kiadó, 2005. [3] S. Guha, N. Daswani, and R. Jain. An experimental study of the skype peer-to-peer voip system. In Proc. of IPTPS, volume 6, 2006. [4] Julian B. Grizzard and The Johns. Peer-to-Peer Botnets : Overview and Case Study. In In USENIX Workshop on Hot Topics in Understanding Botnets (HotBots’07), 2007. [5] M. Ripeanu. Peer-to-peer architecture case study: Gnutella network. In Peer-to-Peer Computing, 2001. Proceedings. First International Conference on, pages 99–100. IEEE, 2001. [6] Q. He and M. Ammar. Congestion control and message loss in Gnutella networks. In Multimedia Computing and Networking, 2004. [7] PUB FIPS. 180-1: Secure hash standard. National Institute of Standards and Technology, 17, 1995. [8] David Karger, Eric Lehman, Tom Leighton, Rina Panigrahy, Matthew Levine, and Daniel Lewin. Consistent hashing and random trees : distributed caching protocols for relieving hot spots on the world wide web. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, STOC ’97, pages 654–663, New York, NY, USA, 1997. ACM. [9] David R. Karger and Matthias Ruhl. Simple efficient load balancing algorithms for peerto-peer systems. In Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, SPAA ’04, pages 36–43, New York, NY, USA, 2004. ACM. [10] M. Naor and U. Wieder. Novel Architectures for P2P Applications: the ContinuousDiscrete Approach. ACM Transactions on Algorithms (TALG), 3(3):34–es, 2007. [11] Petar Maymounkov and David Mazières. Kademlia : A Peer-to-peer Information System Based on the XOR Metric. 2002. [12] I. Stoica, R. Morris, D. Karger, M.F. Kaashoek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. ACM SIGCOMM Computer Communication Review, 31(4):149–160, 2001. 90

IRODALOMJEGYZÉK

91

[13] S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker. A scalable contentaddressable network. In Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, pages 161–172. ACM, 2001. [14] Y.J. Joung, L.W. Yang, and C.T. Fang. Keyword search in dht-based peer-to-peer networks. Selected Areas in Communications, IEEE Journal on, 25(1):46–61, 2007. [15] S. El-Ansary, L. Alima, P. Brand, and S. Haridi. Efficient broadcast in structured P2P networks. Peer-to-Peer Systems II, pages 304–314, 2003. [16] M. Harren, J. Hellerstein, R. Huebsch, B. Loo, S. Shenker, and I. Stoica. Complex queries in DHT-based peer-to-peer networks. Peer-to-Peer Systems, pages 242–250, 2002. [17] S.A. Crosby and D.S. Wallach. An Analysis of BitTorrent’s Two Kademlia-based DHTs. Technical Report TR-07-04, Department of Computer Science, Rice University, 2007. [18] S. Guha and P. Francis. Characterization and measurement of TCP traversal through NATs and firewalls. In Proceedings of the 5th ACM SIGCOMM conference on Internet Measurement, page 18. USENIX Association, 2005. [19] R. Jimenez, F. Osmani, and B. Knutsson. Connectivity properties of mainline bittorrent dht nodes. In Peer-to-Peer Computing, 2009. P2P ’09. IEEE Ninth International Conference on, pages 262 – 270, sept. 2009. [20] R. Roverso, S. El-Ansary, and S. Haridi. NATCracker: NAT Combinations Matter. In Computer Communications and Networks, 2009. ICCCN 2009. Proceedings of 18th Internatonal Conference on, pages 1–7. IEEE, 2009. [21] J.J.D. Mol, J.A. Pouwelse, D.H.J. Epema, and H.J. Sips. Free-riding, fairness, and firewalls in p2p file-sharing. Peer-to-Peer Computing, IEEE International Conference on, 0 :301–310, 2008. [22] B. Ford, P. Srisuresh, and D. Kegel. Peer-to-peer communication across network address translators. In USENIX Annual Technical Conference, volume 2005, 2005. [23] Sean Rhea, Dennis Geels, Timothy Roscoe, and John Kubiatowicz. Handling churn in a DHT. In Proceedings of the annual conference on USENIX Annual Technical Conference, ATEC ’04, pages 10–10, Berkeley, CA, USA, 2004. USENIX Association. [24] J. Furness and M. Kolberg. A survey of blind search techniques in structured p2p networks. In PGNet 2010: Proceedings of The 11th Annual PostGraduate Symposium on The Convergence of Telecommunications, Networking and Broadcasting, pages 313–318, 2010. [25] W. Li, S. Chen, P. Zhou, X. Li, and Y. Li. An Efficient Broadcast Algorithm in Distributed Hash Table Under Churn. In Wireless Communications, Networking and Mobile Computing, 2007. WiCom 2007. International Conference on, pages 1929–1932. IEEE. [26] P. Merz and K. Gorunova. Efficient broadcast in p2p grids. In Cluster Computing and the Grid, 2005. CCGrid 2005. IEEE International Symposium on, volume 1, pages 237–242. IEEE, 2005.

IRODALOMJEGYZÉK

92

[27] P. Trunfio, D. Talia, A. Ghodsi, and S. Haridi. Implementing dynamic querying search in k-ary dht-based overlays. In Grid Computing, pages 275–286. Springer, 2008. [28] V. Vishnevsky, A. Safonov, M. Yakimov, E. Shim, and A.D. Gelman. Scalable blind search and broadcasting in peer-to-peer networks. 2006. [29] S. Naicken, A. Basu, B. Livingston, and S. Rodhetbhai. A survey of peer-to-peer network simulators. In Proceedings of The Seventh Annual Postgraduate Symposium, Liverpool, UK, 2006. [30] S. Joseph. An extendible open source P2P simulator. P2P Journal, 1:1–15, 2003. [31] B. Chun, D. Culler, T. Roscoe, A. Bavier, L. Peterson, M. Wawrzoniak, and M. Bowman. Planetlab: an overlay testbed for broad-coverage services. ACM SIGCOMM Computer Communication Review, 33(3):3–12, 2003. [32] S. Naicken, A. Basu, B. Livingston, S. Rodhetbhai, and I. Wakeman. Towards yet another peer-to-peer simulator. In Proc. Fourth International Working Conference Performance Modelling and Evaluation of Heterogeneous Networks (HET-NETs’ 06), 2006. [33] The „king” data set. http://pdos.csail.mit.edu/p2psim/kingdata/. [34] Késleltetési idő adatbázis a Scott A. Crosby és Dan S. Wallach szerzőpárostól. Személyes közlés. [35] The Honeynet Project. http://honeynet.org/. [36] R. Lehtinen, D. Russell, and GT Gangemi. Computer security basics. O’Reilly Media, Inc., 2006. [37] P. Porras, H. Saïdi, and V. Yegneswaran. An Analysis of the iKee. B iPhone Botnet. Security and Privacy in Mobile Information and Communication Systems, pages 141–152, 2010. [38] Darren Mutz, Giovanni Vigna, and Richard Kemmerer. An Experience Developing an IDS Stimulator for the Black-Box Testing of Network Intrusion Detection Systems. In In Annual Computer Security Applications Conference, Las Vegas, NV, pages 374–383, 2003. [39] B. Toxen. Real world Linux security: intrusion prevention, detection, and recovery. Prentice hall PTR, 2003. [40] R. Janakiraman, M. Waldvogel, and Q. Zhang. Indra: A Peer-to-peer Approach to Network Intrusion Detection and Prevention. In Enabling Technologies: Infrastructure for Collaborative Enterprises, 2003. WET ICE 2003. Proceedings. Twelfth IEEE International Workshops on, pages 226–231. IEEE, 2003. [41] J.G. Levine, J.B. Grizzard, and H.L. Owen. Using honeynets to protect large enterprise networks. Security & Privacy, IEEE, 2(6):73–75, 2004. [42] S. Staniford, D. Moore, V. Paxson, and N. Weaver. The top speed of flash worms. In Proceedings of the 2004 ACM workshop on Rapid malcode, pages 33–42. ACM, 2004.

IRODALOMJEGYZÉK

93

[43] Zhaosheng Zhu, Guohan Lu, Yan Chen, Z.J. Fu, P. Roberts, and Keesook Han. Botnet Research Survey. In Computer Software and Applications, 2008. COMPSAC ’08. 32nd Annual IEEE International, pages 967 –972, aug 2008. [44] B. Stock, J. Göbel, M. Engelberth, F.C. Freiling, and T. Holz. Walowdac-analysis of a peer-to-peer botnet. In Computer Network Defense (EC2ND), 2009 European Conference on, pages 13–20. IEEE, 2010. [45] Christian Seifert. Analyzing Malicious SSH Login Attempts. http://www.symantec.co m/connect/articles/analyzing−malicious−ssh−login−attempts, November 2010. [46] IRC alapú botnet támadás naplói Temesvári Andrástól. Személyes közlés. [47] D. Dagon, G. Gu, C.P. Lee, and W. Lee. A taxonomy of botnet structures. In acsac, pages 325–339. IEEE Computer Society, 2007. [48] G. Vigna R. A. Kemmerer. Intrusion Detection : A Brief History and Overview. Security & Privacy, pages 27–30, 2002. [49] H. Debar. Intrusion Detection Systems-Introduction to Intrusion Detection and Analysis. Security and privacy in advanced networking technologies, page 161, 2004. [50] T.F. Lunt. A survey of intrusion detection techniques. Computers & Security, 12(4):405– 418, 1993. [51] Hervé Debar and Andreas Wespi. Aggregation and Correlation of Intrusion-Detection Alerts. In Wenke Lee, Ludovic Mé, and Andreas Wespi, editors, Recent Advances in Intrusion Detection, volume 2212 of Lecture Notes in Computer Science, pages 85–103. Springer Berlin / Heidelberg, 2001. [52] C.V. Zhou, C. Leckie, and S. Karunasekera. A survey of coordinated attacks and collaborative intrusion detection. Computers & Security, 29(1):124–140, 2010. [53] Alfonso Valdes and Keith Skinner. Probabilistic Alert Correlation. Proceedings of the 4th International Symposium on Recent Advances in Intrusion Detection, pages 54–68, October 2001. [54] Chenfeng Vincent Zhou, Shanika Karunasekera, and Christopher Leckie. A Peer-to-Peer Collaborative Intrusion Detection System. In Networks, 2005. Jointly held with the 2005 IEEE 7th Malaysia International Conference on Communication., 2005 13th IEEE International Conference on, volume 1, page 6. IEEE, 2006. [55] F. Cuppens and R. Ortalo. LAMBDA: A language to model a database for detection of attacks. In Recent advances in intrusion detection, pages 197–216. Springer, 2000. [56] O. Dain and R.K. Cunningham. Fusing a heterogeneous alert stream into scenarios. In Proceedings of the 2001 ACM workshop on Data Mining for Security Applications, pages 1–13, 2001.

IRODALOMJEGYZÉK

94

[57] S.J. Templeton and K. Levitt. A requires/provides model for computer attacks. In Proceedings of the 2000 workshop on New security paradigms, pages 31–38. ACM, 2001. [58] N. Carey, G. Mohay, and A. Clark. Attack signature matching and discovery in systems employing heterogeneous IDS. In Computer Security Applications Conference, 2003. Proceedings. 19th Annual, pages 245–254. IEEE, 2005. [59] H. Debar, D. Curry, and B. Feinstein. RFC4765: The Intrusion Detection Message Exchange Format (IDMEF). http://www.ietf.org/rfc/rfc4765.txt, 2007. [60] Snort – nyílt forráskódú betörésérzékelő rendszer. http://www.snort.org/. [61] Prelude betörésérzékelő rendszer. http://www.prelude−technologies.com/en/welco me/index.html. [62] Shi Zhicai, Ji Zhenzhou, and Hu Mingzeng. A novel distributed intrusion detection model based on mobile agent. In Proceedings of the 3rd international conference on Information security, InfoSecu ’04, pages 155–159, New York, NY, USA, 2004. ACM. [63] V. Yegneswaran, P. Barford, and S. Jha. Global intrusion detection in the domino overlay system. In Proceedings of NDSS, volume 2004, 2004. [64] Vasileios Vlachos and Diomidis Spinellis. A PRoactive Malware Identification System based on the Computer Hygiene Principles. Information Management and Computer Security, 15(4) :295–312, 2007. [65] P. Kenyeres, A. Szentgyörgyi, T. Mészáros, and G. Fehér. BotSpot: Anonymous and Distributed Malware Detection. Recent Trends in Wireless and Mobile Networks, pages 59–70, 2010. [66] P. Kenyeres, T. Mészáros, A. Szentgyörgyi, and G. Fehér. Distributed malware detection. [67] Feng Zhou, Li Zhuang, Ben Y. Zhao, Ling Huang, Anthony D. Joseph, and John Kubiatowicz. Approximate Object Location and Spam Filtering on Peer-to-peer Systems. pages 1–20, 2003. [68] B.Y. Zhao, J. Kubiatowicz, and A.D. Joseph. Tapestry: An infrastructure for fault-tolerant wide-area location and routing. Computer, 74(11-20):46, 2001. [69] J. Li, J. Stribling, R. Morris, M.F. Kaashoek, and T.M. Gil. A performance vs. cost framework for evaluating DHT design tradeoffs under churn. In INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE, volume 1, pages 225–236. IEEE, 2005. [70] E.K. Lua, J. Crowcroft, M. Pias, R. Sharma, and S. Lim. A survey and comparison of peerto-peer overlay network schemes. IEEE Communications Surveys and Tutorials, 7(2) :72–93, 2005. [71] Kaspersky security bulletin: Statistics 2008. http://www.securelist.com/en/analysi s/204792052/Kaspersky_Security_Bulletin_Statistics_2008.

IRODALOMJEGYZÉK

95

[72] M. Bellare and T. Kohno. Hash Function Balance and Its Impact on Birthday Attacks. In Advances in Cryptology-Eurocrypt 2004, pages 401–418. Springer, 2004. [73] S. Saroiu, P.K. Gummadi, S.D. Gribble, et al. A measurement study of peer-to-peer file sharing systems. In proceedings of Multimedia Computing and Networking, volume 2002, page 152, 2002. [74] M. Castro, M. Costa, and A. Rowstron. Performance and dependability of structured peer-to-peer overlays. In Dependable Systems and Networks, 2004 International Conference on, pages 9 – 18, june-1 july 2004. [75] L. Lamport, R. Shostak, and M. Pease. The Byzantine generals problem. ACM Transactions on Programming Languages and Systems (TOPLAS), 4(3):382–401, 1982. [76] K. Huang and D. Zhang. A partition-based broadcast algorithm over dht for large-scale computing infrastructures. Advances in Grid and Pervasive Computing, pages 422–433, 2009.

Ábrák jegyzéke 2.1. 2.2. 2.3. 2.4. 2.5. 2.6.

A Chord átfedő . . . . . . . . . . . . . . . . . . . . A CAN átfedő . . . . . . . . . . . . . . . . . . . . A Kademlia átfedő . . . . . . . . . . . . . . . . . . Útválasztás a Kademlia átfedőben . . . . . . . . . Útválasztási metódusok DHT hálózatokban . . . Egyedek közötti késleltetési idők P2P átfedőkben

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

7 8 9 10 12 17

3.1. A Komondor eljárás működése . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2. A strukturált átfedő használata a Komondor eljárásban . . . . . . . . . . . . . . 3.3. Helytelen jelszavak gyakorisága egyes támadások esetén a támadás időtartamának függvényében . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4. A méréseket végző Komondor P2P hálózat . . . . . . . . . . . . . . . . . . . . . 3.5. Az érzékelt támadások forrásai a világ térképén . . . . . . . . . . . . . . . . . . 3.6. Az érzékelés okozta terhelés elosztása a strukturált átfedőben . . . . . . . . . . 3.7. Támadások típus szerint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.8. A Komondor által érzékelt támadások hosszai és eseményszámai a phpMyAdmin féreg és a Slammer esetén . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.9. A Komondor által érzékelt, SSH kiszolgálót érő támadások támadások hosszai és eseményszámai. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28 30

4.1. Az egyedek kapcsolódási képessége tűzfal vagy címfordítás esetén . . . . . . . 4.2. A fogadott üzenetek eloszlása a kulcs környezetében . . . . . . . . . . . . . . . 4.3. A kapcsolati mátrix jellege és valós alakja sok azonos alhálózatból érkező egyed esetén . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4. A hibák eloszlása egyedek szerint és növekvő sorrendben . . . . . . . . . . . . 4.5. A hálózati hibák eloszlása . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.6. A hálózati hibák az egyedekhez, folytonos közelítéssel, növekvő sorrendben . 4.7. A sikeres kikeresések valószínűsége a Kademliában . . . . . . . . . . . . . . . . 4.8. Sikeres kikeresések a hibaeloszlás egyenetlenségének függvényében . . . . . . 4.9. A Kadsim program képernyőképe . . . . . . . . . . . . . . . . . . . . . . . . . . 4.10. Adott megbízhatóság eléréséhez szükséges replikáció . . . . . . . . . . . . . . . 4.11. Hálózati hibák a BitTorrent átfedőkben [17] alapján, a bemutatott eljárás szerint ábrázolva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.12. Az események elküldött adatainak eloszlása a kulcs környezetében . . . . . . .

96

33 36 38 39 41 42 43 48 49 50 53 54 55 57 58 59 60 62 63

ÁBRÁK JEGYZÉKE 5.1. A Kademlia átfedő átrendezése . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2. Az implicit fás üzenetszórás . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3. Üzenetszórás a Kademlia átfedőben . . . . . . . . . . . . . . . . . . . . . . . . . 5.4. Üzenetszórás a Kademlia átfedőben – eldobott üzenetekkel . . . . . . . . . . . 5.5. Az üzenetszórás hibái 2 és 4 egyed esetén . . . . . . . . . . . . . . . . . . . . . 5.6. Az üzenetszórás hibáinak becsléséhez . . . . . . . . . . . . . . . . . . . . . . . . 5.7. Az üzenetszórás helyessége – a modell és a szimuláció összehasonlítása . . . . 5.8. Javított algoritmus: implicit fás üzenetszórás replikációval . . . . . . . . . . . 5.9. Az üzenetszórás helyessége kb = 3-szoros replikáció esetén . . . . . . . . . . . . 5.10. Eltérő lépésszámú utak az üzenetszórásban replikáció esetén . . . . . . . . . . 5.11. Üzenetek száma egyedenként a bemutatott üzenetszórás algoritmusban, különböző késleltetési idő eloszlások mellett . . . . . . . . . . . . . . . . . . . . . . . 5.12. A késleltetési idők eloszlásának hatása az üzenetszórás hatékonyságára . . . . 5.13. Az üzenetszórást megkapó egyedek aránya az eldobott csomagok függvényében 5.14. Az üzenetszórás sikerességének javítása replikációval . . . . . . . . . . . . . . 5.15. Az üzenetszóráshoz szükséges idő eloszlása a Mainline BitTorrent átfedőben . 5.16. Az egyedszám és az üzenetszóráshoz szükséges átlagos idő összefüggése különféle átfedők esetén . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

97 66 67 68 69 70 71 73 74 75 76 78 78 80 81 82 83

Táblázatok jegyzéke 2.1. 2.2. 2.3. 2.4. 2.5. 2.6.

DHT hálózatok összehasonlító táblázata . . . . . . . . . . . . . . . Csomagkapcsolt és vonalkapcsolt üzenetküldés . . . . . . . . . . . Feltételezések két csomópont közötti üzenetküldésre az Interneten P2P szimulátor alkalmazások . . . . . . . . . . . . . . . . . . . . . Rosszindulatú programok (malware) típusai . . . . . . . . . . . . . Rosszindulatú programok kapcsolattartása készítőikkel . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

8 12 13 16 19 19

3.1. 3.2. 3.3. 3.4.

Az elosztott betörésérzékelés fogalmai . . . . . . . . . . . . . . . A protokollüzenetek számának alakulása strukturált átfedőkben Kapupásztázások típusai [63] alapján . . . . . . . . . . . . . . . . Az elemi események típusai . . . . . . . . . . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

26 32 35 41

. . . .

4.1. Egyed hálózati vagy saját hibája . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.2. Szükséges replikációs szintek a be- és kilépő egyedek okozta hibák kiküszöbölésére 61 4.3. Szükséges replikációs szintek a Kademlia alapú BitTorrent átfedőkben . . . . . 62 5.1. Az átfedő egyedei a Hamming-távolság szerint növekvő sorrendben . . . . . .

98

72

Biztonsági célú átfedő hálózat

Recommend Documents