Algoritmikus komplexitáson alapuló támadás csomagosztályozók ellen

OData támogatás
Konzulens:
Kőrösi Attila
Távközlési és Médiainformatikai Tanszék

Jelen dokumentum egy szakdolgozat, ami a csomagosztályozó rendszerekben használt útvonalválasztó és csomagosztályozó algoritmus ellen indítható, a használt algoritmus komplexitásán alapuló támadások lehetõségeit, és veszélyeit kutatja, kimondott tekintettel az Open vSwitch-re. Ezekben a rendszerekben a keresés általában úgy mûködik, hogy az összes szabályt megvizsgálja, hogy az adott csomag header-jére illik-e, majd ezek közül a legmagasabb prioritásút veszi. A szabályok között meg lehet adni olyan parancsot is, hogy keressen további találatok után is, és az ott leírtakat is végezze el a csomaggal. Azonban ez elõtt egy gyorsításra szolgáló cache-ben a korábbi találatok között keres, itt csak az elsõ találatig, így az esetek nagy többségében meggyorsítva azt. Ez a keresés az ott található bejegyzések számával lineáris idõben történik, így ha szándékosan olyan csomagokat küldünk mindig, amik új entry-t generálnak itt, akkor jelentõsen lelassíthatjuk a szolgáltatás sebességét.

A szabályok alakja valamilyen maszkolt bitsor, vagyis bizonyos pozíciókban lévõ biteket vesz csak alapul és azoknak meg kell felelniük az adott szabályhoz tartozó bitsorozatnak. Az eredeti szabályok között elõfordulhat átfedés is, és ilyen esetekben egy elõre definiált prioritás alapján dõl el, milyen akció hajtódik végre. Azonban a cacheben generáltak szabályokat úgy kell megadni, hogy egy ilyen tartomány összes pontjához ugyanaz az akció tartozzon, ezért jellemzõen nem lesz elég egy szabályt megadni, hanem több, kisebb tartomány uniójaként áll majd elõ a cacheben. Az ehhez tartozó kombinatorikus feladat, mi szerint egy ilyen általános struktúra túllógás mentes lefedéséhez legalább hány tartomány kell NP-nehéz, és esetenként az figyelhetõ meg, hogy akár az eredeti szabályok számához képest exponenciális sokra is szükség lehet.

Egy speciális esetre való becslésnek a létrehozásával, illetve négy algoritmus implementálásával foglalkoztam. Ezek az algoritmusok mind más-más esetben, és eltérõ szempontok alapján mondhatók jónak vagy rossznak, azonban egyik sem tekinthetõ általános helyzetekre jó megoldásnak. Ezeknek a bemutatása után mininetes tesztkörnyezetben néhány egyszerûbb teszt eset következik majd, ami alapján egyértelmûen látszik, hogy egy egyszerûbb szabályrendszer mellett is mekkora lassulás érhetõ el egy jól megtervezett támadással.

Letölthető fájlok

A témához tartozó fájlokat csak bejelentkezett felhasználók tölthetik le.