Paket filtrlari foydalanuvchi tomonidan taqdim etilgan qoidalar to'plamiga muvofiq tarmoq trafigini tasniflash uchun foydalaniladigan paketlarni manipulyatsiya qilish dasturlari sinfi

KIRISH
Paket filtrlari - foydalanuvchi tomonidan taqdim etilgan qoidalar to'plamiga muvofiq tarmoq trafigini tasniflash uchun foydalaniladigan paketlarni manipulyatsiya qilish dasturlari sinfi; ular shakllantiruvchilar, snifferlar, demultipleksatorlar, xavfsizlik devorlari va boshqalar kabi ko'plab tarmoq ilovalarining asosiy komponenti hisoblanadi.
Zamonaviy tarmoq stsenariysi paketli filtrlarga, asosan, ishlov berish tezligi (tarmoq liniyalari tezligini ushlab turish) va resurslarni iste'mol qilish (cheklangan muhitda ishlash) bo'yicha ko'plab talablarni qo'yadi. Filtrlash usullari ko'pincha tsiklik yoki takroriy tuzilmalarni o'z ichiga olgan zamonaviy protokol formatlarini ham qo'llab-quvvatlashi kerak (masalan, MPLS yorliqlari to'plami, IPv6 kengaytmalari sarlavhalari). Va nihoyat, filtrlar o'zlarining ishlash muhitining yaxlitligini saqlashlari ham juda muhim, ham xotiradan foydalanish xavfsizligi, ham tugatishni qo'llash nuqtai nazaridan, ayniqsa operatsion tizim moduli sifatida yoki yalang'och apparatda ishlaganda. Garchi bir qarashda bu jihat muhim bo'lmasa-da, mavjud paketli filtrlarga o'rnatilgan ko'plab cheklovlar to'g'ridan-to'g'ri xavfsizlik muammolaridan kelib chiqqanligi haqiqatdir: misol sifatida, umumiy kompyuter dasturini avtomatik ravishda tugatishni isbotlashning mumkin emasligi BPF dizaynerlarini keltirib chiqardi. faqat asiklik filtrlarni yaratish, shu bilan bir necha darajadagi inkapsulyatsiya yoki takroriy maydon ketma-ketligi bilan paketlarni tahlil qilishning oldini oladi.
Mavjud paketli filtrlar har doim ushbu muammolarning kichik to'plamlariga e'tibor qaratadi, ammo bizning ma'lumotlarimiz bo'yicha, ularning hammasini bir vaqtning o'zida hal qilmaydi: misol sifatida, ikkita keng tarqalgan generatorlar, BPF+ va PathFinder, rekursiv inkapsulyatsiyani qo'llab-quvvatlamaydi; Boshqa tomondan, NetVM-ga asoslangan filtrlar filtrlash kodida ham, asosiy virtual mashinada ham tugatishni majburlash uchun hech qanday shartga ega emas.
Ushbu maqola SPAF (Statesiz paket filtri), tez va xavfsiz paket filtrlarini yaratish uchun FSAga asoslangan texnikani taqdim etadi, ular 2-qatlam 4-qatlam protokollarining koʻpchiligini, jumladan, ixtiyoriy va oʻzgaruvchan sarlavhalar va rekursiv inkapsulyatsiyani toʻliq qoʻllab-quvvatlash uchun yetarli darajada moslashuvchan. Taklif etilayotgan texnika maxsus protokollar stekining pastki qatlamlariga mo'ljallangan va to'g'ridan-to'g'ri paketlarni chuqur tekshirish va umuman holatini filtrlash uchun qo'llanilmaydi. Bundan tashqari, ushbu maqolaning maqsadi uchun biz faqat statik vaziyatlarni ko'rib chiqamiz, ularda qoidalar to'plamini yangilash talab qilinmaydi. Ushbu cheklovlar ba'zi qiziqarli foydalanish holatlarini istisno qilsa-da, SPAF filtrlari monitoring va trafik izlarini filtrlash kabi ilovalarning katta sinfi uchun foydali bo'lib, hujumni aniqlash tizimlari va xavfsizlik devorlari kabi murakkabroq vositalar uchun boshlang'ich bosqich bo'lib xizmat qilishi mumkin.
Shtatsiz paket filtri mantiqiy operatorlar bilan birlashtirilgan paket maydonlaridagi predikatlar to'plami sifatida ifodalanishi mumkin; ko'pincha bu predikatlar bir-biridan to'liq mustaqil emas va butun to'plamni baholash qisqa tutashuvga olib kelishi mumkin. Yuqori unumdorlikdagi filtrlar uchun generatorlarni loyihalashda eng muhim savollardan biri mos kelmaslik/mos kelmaslik to'g'risida qaror qabul qilish uchun zarur bo'lgan ishlov berish miqdorini kamaytirish uchun predikatlar to'plamini qanday samarali tashkil qilishdir. Paket filtrlashni oddiy tilni tanib olish muammosi sifatida ko'rib chiqish va predikatlarni chekli holatli avtomatlar sifatida ifodalash va tartibga solish uchun tegishli matematik tizimdan foydalanish orqali SPAF hosil bo'lgan dasturdagi har qanday bajarish yo'li bo'ylab ortiqcha miqdorini kamaytirishga erishadi: har qanday paket maydoni ko'pi bilan bir marta tekshiriladi. Bu xususiyat modeldan kelib chiqadi va u har doim keng ko'lamli mantiqiy kompozitsiya kabi an'anaviy usullar bilan davolash qiyin bo'lgan holatlarda ham mavjud. Bundan tashqari, sodda va muntazam tuzilishi tufayli chekli avtomatlar to'liq kompilyatorni talab qilmasdan to'g'ridan-to'g'ri optimallashtirilgan bajariladigan shaklga tarjima qilinadigan ichki tasvir sifatida ham ikki baravar ishlaydi. Nihoyat, xavfsizlik (ham tugatish, ham xotiraga kirishning yaxlitligi nuqtai nazaridan) juda kam ish vaqti bilan ta'minlanishi mumkin.
Ushbu maqolaning qolgan qismi quyidagicha tuzilgan: II bo'lim shu kungacha ishlab chiqilgan asosiy tegishli filtrlash yondashuvlarining umumiy ko'rinishini taqdim etadi. III bo'lim filtrni ko'rsatish uchun ishlatiladigan FSAlar haqida qisqacha ma'lumot beradi va filtrni qurish tartibini tavsiflaydi. IV bo'limda asosiy e'tibor bajariladigan kod yaratish va qiziqishning rasmiy xususiyatlarini qo'llashga qaratilgan bo'lsa, V bo'lim yangi yondashuvni baholash va da'volarimizni qo'llab-quvvatlash uchun to'plangan eksperimental dalillarni taqdim etadi. Nihoyat, VI bo'lim xulosalar haqida ma'lumot beradi va shuningdek, kelajakdagi voqealarni ta'kidlaydi.
II. ALOQALI ASARLAR
Ularning keng qo'llanilishi va nisbatan uzoq tarixini hisobga olgan holda, paketli filtrlar bo'yicha katta adabiyotlar korpusi mavjud. Filtrlarning birinchi sinfi CFG paradigmasiga asoslangan; Eng mashhur va eng keng tarqalgani, ehtimol, BPF [1], Berkeley paket filtri. BPF filtrlari generatorda qattiq kodlangan protokol tavsiflaridan yaratilgan va oddiy, maxsus virtual mashina uchun bayt-kod ro'yxatiga tarjima qilingan. Bayt-kod dastlab talqin qilingan bo'lib, JIT texnikasini qo'llash orqali kamaytirilishi mumkin bo'lgan ish vaqtining sezilarli ta'siriga olib keldi. BPF tugatilishini ta'minlash uchun filtrlarda orqaga sakrashga yo'l qo'ymaydi va shu bilan, masalan, qo'llab-quvvatlashdan voz kechadi. IPv6 kengaytmalari sarlavhalari; xotira himoyasi ish vaqtida har bir kirishni tekshirish orqali amalga oshiriladi. Bir nechta filtr iboralari mantiqiy operatorlar tomonidan birgalikda tuzilishi mumkin, lekin dastlabki BPF dasturida faqat kichik miqdordagi optimallashtirishlar predikatlar bo'yicha amalga oshiriladi, bu esa bog'liq yoki takroriy predikatlar baholanganda ish vaqtining samarasizligiga olib keladi. Ikki tegishli BPF kengaytmalari BPF+ va xPF. BPF + CFG tuzilishini o'zgartirish orqali ortiqcha operatsiyalarni olib tashlashga harakat qiladigan mahalliy va global ma'lumotlar oqimini optimallashtirish algoritmlarini qo'shadi. xPF CFG filtrida orqaga sakrashga ruxsat berish orqali nazorat oqimi cheklovlarini yumshatadi; tugatish tarjimonga o'rnatilgan ish vaqti kuzatuvchisi orqali bajarilgan ko'rsatmalarning maksimal sonini cheklash orqali amalga oshiriladi, biroq uning qo'shimcha xarajatlari o'lchanmagan va bu yondashuvni o'z vaqtida kod chiqarishga kengaytirish taklif qilinmagan va qiyin bo'lishi mumkin.
BPF bilan bog'liq bo'lmagan yana bir CFG-ga asoslangan yondashuv quyida tasvirlangan. Uning asosiy hissasi XML-ga asoslangan protokol tavsiflash tili NetPDL yordamida protokol ma'lumotlar bazasini filtr generatoridan ajratishdir. Filtrlash kodi tarmoq ilovalariga mo'ljallangan maxsus maqsadli virtual mashina NetVM da bajariladi, u ham filtr tuzilmasida, ham past darajadagi kodda ishlaydigan optimallashtiruvchi JIT kompilyatorini ta'minlaydi. Xabarlarga ko'ra, yuqori darajadagi tavsif tilini joriy etish hech qanday ishlash jazosiga olib kelmaydi; ammo bu yondashuv barcha xavfsizlik masalalarini VM ga topshiradi va bir nechta filtrlarni yaratishning samarali usulini ta'minlamaydi.
Umuman olganda, CFG-ga asoslangan generatorlar o'zlarining moslashuvchan tuzilmasidan foydalanadilar, bu esa predikatlarni baholash tartibiga hech qanday jiddiy cheklovlar qo'ymaydi; xuddi shu sababga ko'ra, ular aniqlanishi qiyin bo'lgan ortiqcha ishlarning kiritilishiga moyil bo'lib, agar boshqa choralar ko'rilmasa, bir nechta keraksiz baholashlarga olib keladi. Optimizatorlar qo'llanilsa va foydali ekanligi eksperimental ravishda ko'rsatilgan bo'lsa ham, ular opportunistik asosda ishlaydi va natijada olingan kodga kamdan-kam kafolatlar beradi.
Filtr generatorlarining ikkinchi guruhi predikatlarni tashkil qilish uchun daraxtga o'xshash tuzilmalarni tanlaydi. PathFinder predikatlarni shablon niqoblariga (atomlarga) aylantiradi, tartiblangan qarorlar daraxtiga aylantiradi. Keyin natijaga erishilgunga qadar atomlar chiziqli paketlarni skanerlash orqali moslashtiriladi. Qaror daraxtlari bir nechta filtrlar bo'ylab taqsimlangan prefikslarni birlashtirishga asoslangan optimallashtirish imkonini beradi. PathFinder dasturiy ta'minot va apparat ta'minotida ham yaxshi ishlashi ko'rsatilgan, ammo u protokol ma'lumotlar bazasini ajratishni hisobga olmaydi va dasturiy ta'minotni amalga oshirish uchun xotira xavfsizligi muammolarini hal qilish taklif etilmaydi. FSA asosidagi filtrlar PathFinder bilan o'xshashlik darajasiga ega, chunki paketlar boshidan oxirigacha chiziqli skanerdan o'tkaziladi, lekin predikatlar tashkil etish, filtr tarkibi va xavfsizlik masalalari boshqacha ko'rib chiqiladi. DPF PathFinder-ga qaraganda, mashina kodini o'z vaqtida ishlab chiqarish va moslashuvchan kalit emissiya strategiyasi kabi past darajadagi optimallashtirishlarni qo'shish orqali yaxshilanadi. Bundan tashqari, DPF har bir xotiraga kirishni alohida ko'rib chiqish o'rniga o'qilishi kerak bo'lgan eng yuqori xotira ofsetining mavjudligini tekshirish orqali atom darajasida chegaralarni tekshirishga qodir; IV-E bo'limida tasvirlangan bizning texnikamiz xuddi shunday ishlaydi, lekin filtrni bir butun sifatida ko'rib chiqadi va shu bilan ishlash vaqtini yanada qisqartiradi.
Predikatlarni muntazam tuzilmalarda tashkil qilish ortiqcha va boshqa yuk manbalarini aniqlashni osonlashtirsa-da, u turli cheklovlarni ham kiritadi: misol sifatida, yuqorida aytib o'tilgan asiklik tuzilmalar bilan cheklangan generatorlar tunnel yoki takroriy protokol qismlarini to'liq qo'llab-quvvatlamaydi. Bundan tashqari, prefikslarni birlashtirishni amalga oshirish ba'zi umumiy naqshlarni ushlash uchun etarli emasligi, bu esa ortiqcha predikatlarni baholashga olib kelishi ta'kidlangan.
Uchinchi yondashuv - paketlarni filtrlashni tilni aniqlash muammosi sifatida ko'rib chiqish. Jayaram va boshqalar. paketlarni demultiplekslashni amalga oshirish uchun pastga surish avtomatidan foydalaning; filtrlar LALR(1) grammatikalari sifatida ifodalanadi va shuning uchun tegishli qoidalar yordamida samarali tarzda tuzilishi mumkin. Ushbu yechim filtrni kengaytirilishini yaxshilaydi, lekin pastga tushirish avtomatining salbiy tomonlari mavjud: yaxshi ishlashga erishish uchun bir qator maxsus optimallashtirishlar talab qilinadi. Protokollar va filtr qoidalarini qat'iy ravishda bir ma'noda saqlanishi kerak bo'lgan rasmiy grammatikalar sifatida ifodalash juda noqulay: mualliflar bir xil vazifa uchun oddiyroq FSA modeli etarli bo'lishini ta'kidlashadi.
Paketlarni qayta ishlashda chekli holat avtomatlarining qabul qilinishi yangilik emas, chunki chekli avtomatlar, ayniqsa, kirishni aniqlash tizimlarida (IDS) chuqur foydali yukni tekshirish uchun ishlatiladi. Umumiy yondashuv o'xshash bo'lsa-da, foydali yukni chuqur tekshirish bilan bog'liq amaliy masalalar 2-qatlamdan 4-qavatga filtrlash uchun FSAlarni qo'llashda duch keladiganlardan ancha farq qilishi mumkin. Misol tariqasida, foydali yuk muntazam iboralar odatda erkin shaklda bo'ladi va ko'pincha kompozitsiyadan kelib chiqadigan avtomatlar hajmiga salbiy ta'sir ko'rsatadigan va holat fazosi portlashi deb ataladigan naqshlarni taqdim etadi. Bu muammo, shubhasiz, foydali yukni tekshirish uchun FSAni qabul qilishni cheklovchi omil hisoblanadi va u, albatta, tekshirishga loyiqdir; ammo, bizning stsenariyimiz etarlicha boshqacha bo'lishi mumkin (protokol sarlavhalari ko'pincha ancha qattiqroq tuzilishga ega), shuning uchun uning ta'siri yumshatiladi. Ko'pgina FSA-ga asoslangan paketli protsessorlar orasida SPAF uchun eng yaqin mos keladigani, ehtimol, paketlarni filtrlash uchun ham ishlatilishi mumkin bo'lgan trafik izlarini anonimlashtirish uchun mo'ljallangan paketlarni qayta yozish tizimi Rulerdir. U qayta yozishni qo'llab-quvvatlaydigan NFA kengaytmasiga asoslangan va uning mexanizmi Intel IXP tarmoq protsessorlariga maxsus moslashtirilgan. Avtomatlarga asoslangan Ruler SPAF bilan o'xshashlik darajasiga ega, ammo uning dizayn maqsadlari sezilarli darajada farq qiladigan yakuniy natijalarga erishish uchun etarlicha farq qiladi. Ruler dizayni katta erkin shakldagi muntazam ifodalar to'plamini va qayta yozish uchun zarur bo'lgan modifikatsiyalarni qo'llab-quvvatlashga qaratilgan; Qatlam-2 dan 4 gacha filtrlashning yaxshi ishlashiga erishish uchun zarur bo'lgan jihatlarga kamroq e'tibor qaratildi, shuning uchun eksperimental taqqoslashlarda SPAFdan keyin (V bo'lim). Xavfsizlik masalalari ham qulay tarzda hisobga olinmaydi (xotira chegaralari har bir kirishda tekshiriladi) va uning manba tili murakkab filtr bayonotlari yoki IPv6 kengaytmasi sarlavhalari kabi tez-tez uchraydigan protokol tuzilmalarini belgilash uchun etarli darajada umumiy emas: butun paket strukturasini ifodalovchi muntazam iboralarga murojaat qiling, bu formula oxirgi foydalanuvchi uchun oldini olish mumkin bo'lgan murakkablik qatlamini taqdim etadi.
Yuqorida aytib o'tilgan paketlarni tezkor filtrlash bo'yicha ixtisoslashtirilgan echimlardan tashqari, eng ko'p ishlatiladigan paketlarni filtrlash dasturlaridan biri NetFilter ramkasidir. NetFilter Linux yadrosining komponenti bo'lib, paketlarni filtrlash, xavfsizlik devorini o'chirish, o'zgartirish operatsiyalarini (masalan, tarmoq manzilini tarjima qilish) va boshqalarni amalga oshiradi, tarmoq stekini kesib o'tayotganda paketlarni ushlab turadigan ilgaklar va qayta qo'ng'iroqlar to'plami orqali ishlaydi. Yuqorida aytib o'tilgan barcha yondashuvlardan farqli o'laroq, NetFilter paketli filtrlashni amalga oshirishda barcha belgilangan qoidalarni ketma-ketlikda qo'llashning nisbatan sodda usulidan foydalanadi, bu esa yomon ishlash va kengayish qobiliyatiga olib keladi; Bundan tashqari, ixtiyoriy predikatni belgilashning iloji yo'qdek tuyuladi, filtrlar haqiqiy tarmoq manzillari va portlarini ko'rsatish orqali ixtisoslashgan oldindan o'rnatilgan protokollar va bayonotlar bilan cheklangan.
Ishlab chiqarish texnikasidan tashqari, xPF, FFPF va nCap tomonidan ko'rsatilgan me'moriy mulohazalar yoki SWIFT vositasida ko'rsatilganidek, dinamik qoidalar to'plamini qo'llab-quvvatlash kabi boshqa o'lchovlar bo'yicha yaxshilanishlar ham mavjud. Biz ushbu jihatlarni ushbu maqolaning maqsadlari doirasidan tashqarida deb hisoblaymiz, chunki biz taqdim etayotgan texnikaga ortogonal yoki kelajakdagi ishlarning ob'ekti.
III. FILTRLARNI YASALASH TEXNIKASI
Fuqaroligi bo'lmagan paket filtri generatorining maqsadi chekli uzunlikdagi bayt ketma-ketligi (paket) kiritilganda, ikkilik moslik/mos kelmaslik qarorini qaytaradigan dastur yaratishdir. Jeneratorning o'zi kiritilishi mos keladigan paketlarning kerakli xususiyatlarini ko'rsatadigan foydalanuvchi tomonidan taqdim etilgan filtrlash qoidalari to'plamidan iborat; har bir qoida, o'z navbatida, mantiqiy operatorlar bilan birlashtirilgan oddiy yuqori darajali tilda ifodalangan bir nechta predikatlardan iborat (bu erda sarlavha maydonlari va protokollar ramziy ravishda paydo bo'ladi). Eski generatorlarda qo'llab-quvvatlanadigan protokollar to'plami o'rnatildi; zamonaviylarida protokol sarlavhasi formatlari generatorni o'zgartirmasdan yangilanishi mumkin bo'lgan tashqi ma'lumotlar bazasida saqlanadi. Muvaffaqiyatli FSA-ga asoslangan filtrlash texnikasini ishlab chiqish uchun birinchi navbatda har qanday qiziqish filtri cheklangan avtomat sifatida ifodalanishi mumkinligini ko'rsatish kerak, keyin yuqori darajadagi filtr bayonoti va protokol ma'lumotlar bazasini FSAga aylantirish usulini taqdim etish kerak. shakl; nihoyat, natijada olingan avtomat samarali bajariladigan shaklga tarjima qilinishi kerak.
Cheklangan holat avtomatlari
Cheklangan holat avtomati (FSA) beshlik (A, S, s0, t, F), bu yerda A — kirish belgilar alifbosi, S — holatlar toʻplami, s0 ∈ A — boshlangʻich holat, t ⊆ S × A × S o'tish munosabati va F ⊆ S qabul qiluvchi holatlar to'plami. FSAlar o'zboshimchalik bilan uzun belgilar qatorlarining muntazam to'plamlarini rasmiy ravishda aniqlash uchun ishlatilishi mumkin; chekli avtomat va satr berilgan bo'lsa, satr FSA tomonidan ifodalangan to'plamga tegishli yoki yo'qligini aniqlash oson. Fuqaroligi bo'lmagan paket filtrlari bilan parallellik darhol yuzaga keladi: har bir paketni baytlar qatori sifatida ko'rish mumkin va filtr bayonoti tan olinishi kerak bo'lgan paketlar to'plamini belgilaydi. FSA modelini bizning maqsadlarimizga moslashtirish uchun A ni barcha mumkin bo'lgan 8 bitli satrlar to'plami va belgisi sifatida belgilash kifoya, hech qanday kirishni iste'mol qilmasdan olinishi mumkin bo'lgan o'tishlarni belgilash uchun ishlatiladi. Qolgan yagona talab - har qanday qiziqarli paketlar to'plami muntazam
ekanligini ko'rsatish; bu har qanday chekli to'plam muntazam ekanligini va faqat chekli ko'p paketlar mavjudligini ta'kidlash bilan darhol isbotlanadi, chunki ular texnologik nuqtai nazardan uzunligi cheklangan. Shuning uchun nazariy jihatdan har qanday fuqaroligi bo'lmagan paketli filtr uchun mos keladigan FSAni yaratish mumkin. Hatto rekursiv tuzilmalar ham qo'llab-quvvatlanishi mumkin: umumiy holatda kuchliroq formalizm (masalan, pastga surish avtomati) talab qilinsa, qo'llash doirasini cheklangan to'plamlar bilan cheklash oddiy avtomatlarni etarli qiladi.
Protokol ma'lumotlar bazasini kompilyatsiya qilish
SPAF yaratish jarayonining birinchi bosqichi protokol ma'lumotlar bazasini tahlil qilish va ma'lum bir protokol uchun barcha to'g'ri formatlangan sarlavhalarni taniydigan shablon avtomatlarini qurishdan iborat. Ushbu avtomatlar qaytadan foydalaniladi va yakuniy filtrni yaratish uchun keyingi bosqichlarda ixtisoslashtiriladi.
Protokol ma'lumotlar bazasidan filtr yaratishni ajratish uchun biz tarmoq protokollarining simli tuzilmalarini va ularning inkapsulyatsiya munosabatlarini tavsiflash uchun mo'ljallangan XML-ga asoslangan protokol tavsiflash tilidan (NetPDL) foydalandik. NetPDL tavsiflari tashqi fayllarda saqlanadi, ular generatorning o'zini o'zgartirmasdan erkin tahrirlanishi mumkin.
NetPDL ning aniq tavsifi ushbu maqola doirasidan tashqarida; Shunga qaramay, biz FSA generatori tomonidan qo'llab-quvvatlanadigan xususiyatlarning qisqacha ko'rinishini taqdim etamiz. Til 2 dan 7 gacha bo'lgan protokollarning sarlavha formatlarini tavsiflash imkonini beruvchi ko'p sonli ibtidoiy vositalarni taqdim etadi, ammo bu ish doirasi uchun biz qo'llab-quvvatlashimizni 2 dan 4 gacha bo'lgan qatlamlarni dekodlash uchun mo'ljallanganlarga cheklab qo'ydik. Protokol formatining asosiy qurilish bloki sarlavha maydoni, o'zgarmas yoki o'zgaruvchan bo'lishi mumkin bo'lgan baytlar yoki bitlar ketma-ketligidir. Qo'shni maydonlar sukut bo'yicha ketma-ket joylashtirilgan, ammo shartli tanlovlar va tsikllar yordamida ixtiyoriy yoki takroriy bo'limlar kabi murakkabroq tuzilmalar yaratilishi mumkin; bu bayonotlar ilgari duch kelgan maydonlar qiymatlariga havolalarni o'z ichiga olishi mumkin bo'lgan ifodalar bilan boshqariladi.
NetPDL-ning ikkinchi qismi inkapsulyatsiya munosabatlarini belgilovchi boshqaruv oqimi operatsiyalari ketma-ketligini (agar, o'tish) o'z ichiga oladi: umuman, boshqaruv oqimi paketda topilishi kerak bo'lgan keyingi protokol bo'lgan keyingi protokol tegi paydo bo'lgunga qadar kuzatiladi. Shunday qilib, NetPDL ma'lumotlar bazasi yo'naltirilgan inkapsulyatsiya grafigini tavsiflaydi, bu erda tepalar protokollar va qirralari - inkapsulyatsiya munosabatlari.



1-rasm. IPv6 NetPDL ko'chirmasi
Hozirgi vaqtda grafik odatda havola qatlami protokolini ifodalovchi foydalanuvchi tomonidan belgilangan yagona ildizdan boshlanadi, biroq bir nechtasiga kengaytmasi ahamiyatsiz bo'ladi. Ushbu ildizdan boshlab, FSA generatori kapsülleme grafigiga amal qiladi va ushbu bo'limda keyinroq tushuntirilgan usuldan foydalanib, har bir kirish protokoli uchun FSA quradi.
Misol tariqasida, IPv6 sarlavhasi formatining soddalashtirilgan NetPDL tavsifi 1-rasmda keltirilgan. IPv6 belgilangan o'lchamli maydonlar ketma-ketligidan boshlanadi; bit maydonlari (masalan, ver) mask atributi bilan belgilanadi. Dastlabki qismdan keyin kengaytma sarlavhalari to'plami keladi, ularning har biri "keyingi sarlavha" ma'lumotlarini o'z ichiga oladi (keyingi). Bu ketma-ketlik aniqlanmagan (lekin bilvosita cheklangan, chunki har qanday paket chekli) uzunlikda va u tsikl ichida joylashgan kalit yordamida tavsiflanadi: har bir iteratsiyada yangi o'qilgan nexthdr maydoni baholanadi va agar boshqa kengaytmalar sarlavhalari mavjud bo'lmasa, tsikl tugaydi. Inkapsulyatsiya munosabatlari ham xuddi shunday tarzda, oxirgi duch kelgan keyingi hdr qiymatiga qarab to'g'ri protokolga o'tish orqali belgilanadi.
SPAF hozirda Ethernet, MPLS, VLAN, PPPoE, ARP, IPv4, IPv6, TCP, UDP va ICMP kabi eng keng tarqalgan 2-4 qatlam protokollarining to'liq versiyalarini qo'llab-quvvatlaydi; Bu to'plamni hech qanday davlat ko'nikmalari talab qilinmasa, osongina kengaytirilishi mumkin.
NetPDL tavsiflaridan FSA yaratish bilan bog'liq muhim jihat shundaki, agar u to'g'ri bajarilsa, filtr ishlashi uchun muhim vazifa emas: natijada paydo bo'lgan har qanday avtomat aniqlanadi va minimallashtiriladi, bu esa filtrning kanonik tasvirini beradi. hosil qilish tartibiga bog'liq. Shu sababli va murakkablikni hisobga olgan holda, NetPDL ni FSA ga o'tkazish tartibi ushbu maqolada to'liq tavsiflanmagan va uni amalga oshirish tafsilotlari sifatida ko'rib chiqish mumkin. Shunga qaramay, konvertatsiyani qanday amalga oshirish mumkinligini misol qilish uchun biz 2-rasmdagi NetPDL parchalarini mos keladigan avtomatlarga tarjima qilishning asosiy bosqichlari haqida xabar beramiz.
Ushbu dastlabki konvertatsiya bosqichining maqsadi filtrlash uchun darhol mos keladigan avtomatlarni yaratish emas; aksincha, natijalar filtrlash qoidalariga muvofiq ixtisoslashtirilgan boshqa shartlarsiz protokol sarlavhalarining "vanil" versiyasini ifodalovchi keyingi avlod bosqichlari uchun shablonlardir. Ular sarlavha formati bilan qat'iy bog'liq bo'lganligi sababli, ushbu andozalardagi har qanday kiritishni talab qiluvchi o'tish one3 sarlavha maydonining ma'lum bir qismi bilan bog'liq bo'lishi mumkin; filtrlash qoidalarini o'rnatish uchun ushbu ma'lumot saqlanishi kerak. Shu sababli shablon avtomatlari barcha tegishli o'tishlarni tegishli maydon nomi bilan belgilash orqali kengaytiriladi4.
Eng oddiy misol - belgilangan uzunlikdagi sarlavha maydonini tahlil qiluvchi avtomatni yaratish (2a-rasm): tegishli bayt miqdorini o'tkazib yuboradigan FSA qurish kifoya, natijada 2b-rasm. Qurilish jarayonida sarlavha maydonlariga aniq belgilangan boshlang'ich va tugatish 5 holatlari beriladi, ular kerak bo'lganda har qanday o'tmishdoshlar yoki vorislar bilan -o'tishlar bilan qo'shilish uchun tikuv nuqtalari sifatida ishlatiladi.
Shartli tanlovni o'z ichiga olgan murakkabroq misol 2c-rasmda ko'rsatilgan. Yaratish protsedurasi NetPDL tavsifidagi barcha boshlang'ich maydonlar uchun avtomat tasvirlarni yaratishdan boshlanadi; kalit konstruksiyaga duch kelganda esa, generator tur maydoniga duch kelmaguncha o'tish grafigini orqaga qaytaradi. Topilgandan so'ng, turdan keyingi barcha holatlar/o'tishlar (rasmdagi A bloki) takrorlanadi. Asl nusxa o'z holicha qoldiriladi, replikada esa turga o'tishlar kommutator uchun qiziq baytlarni aniqlashga ixtisoslashgan, shuning uchun haqiqiy kirish qiymatlariga qarab to'g'ri yo'l olinadi. Nihoyat, to'g'ri orqa blok (B yoki C) to'g'ri joyda birlashtiriladi.
Oxirgi misol (2e-rasm va 2f-rasm) IPv6 kengaytmasi sarlavhalari holatiga o'xshash sarlavha tuzilishi uchun yaratilgan avtomatlarni ko'rsatadi. Bunday holda, halqa kalit konstruktsiyasi bilan o'zaro bog'langan va joriy keyingi qiymatning har bir mumkin bo'lgan kombinatsiyasi uchun avtomatga mustaqil yo'llar mavjudligini ta'minlash uchun blokning ko'proq takrorlanishi talab qilinadi (ko'chma natijasi bunga bog'liq). keyingi keyingi qiymat, bu tsiklning tugashiga olib kelishi mumkin.
Inkapsulyatsiya munosabatlari xuddi shunday tarzda, avtomat grafigida keyingi protokol bilan belgilangan maxsus holat bilan tugaydigan yangi yo'llarni yaratish orqali amalga oshiriladi. Ushbu belgilangan holatlarning aniq ishlatilishi III-D bo'limida tushuntirilgan.
Yaratish tartibi FSA modelida aniq saqlash joylarining yo'qligiga qarshi harakat qiladi; Keyingi hisob-kitoblar uchun ilgari duch kelgan maydonlarning qiymatlaridan foydalanish zarurati tug'ilganda, yagona yechim - avtomat ichida har biri ko'rib chiqilayotgan maydonning o'ziga xos qiymati bilan bog'liq bo'lgan bir qator parallel novdalarni yaratishdir.
Filtr qoidalarini o'rnatish
Ikkinchi avlod bosqichi filtrlash qoidalarini hisobga oladi. Foydalanuvchi filtr generatoriga barglar predikatlar (masalan, ip.src = 10.0.0.1) va ichki tugunlar mantiqiy operatorlar bo'lgan tahlil qilish daraxtiga bo'lingan o'zboshimchalik bilan murakkab qoida bilan ta'minlaydi. Bir vaqtning o'zida bitta predikat ustida ishlagan holda, generator tegishli protokol shablon avtomatining nusxasini yaratadi va uni ixtisoslashtiradi, natijada olingan FSA muvaffaqiyatli holatga etadi, agar kiritilgan ma'lumotlar predikatni to'g'ri qilsa. Ushbu bosqichni bajarish uchun generator predikat tomonidan belgilangan maydonga mos keladigan o'tishlarni topish uchun shablon izohlaridan foydalanadi, so'ngra kutilgan qiymatlar bilan belgilangan parallel yo'lni yaratadi. Ushbu ixtisoslashtirilgan o'tish zanjirining oxirgi holati talab qilinadigan xatti-harakatlarni amalga oshirish uchun yakuniy deb belgilangan.

2-rasm. Filtrni yaratish misollari

Ixtisoslashuv protsedurasining misoli 3-rasmda keltirilgan. Keling, 3 ta sarlavha maydoni (a, b va c) va 3a-rasmdagi shablon avtomatiga olib boradigan strukturaga ega oddiy protokolni ko'rib chiqaylik. Inkapsulyatsiya shartlari shuni ko'rsatadiki, agar c 0 bo'lsa, u holda protokol o'zini foydali yuk sifatida qamrab oladi; Bu rasmdagi chiziqli holatni tegishli identifikator bilan belgilashga tarjima qilingan. Nihoyat, foydalanuvchi bitta predikatni belgilaydi deb faraz qilaylik: b = AA BB. Ushbu predikatni tahlil qilishda generator 3a-rasmdagi grafikning nusxasini yaratadi, so'ngra b maydonini topishga kirishadi. Ixtisoslashuv bosqichida 44 55 baytlik ketma-ketlikka mos keladigan va yakuniy holat bilan tugaydigan 2 ta o'tish zanjiri hosil bo'ladi va keyin b maydoniga olib boradigan filialga parallel ravishda yopishtiriladi. Natija 3b-rasmda ko'rsatilgan, bunda muvaffaqiyatga erishishning yagona yo'li talab qilinganidek b maydonining ixtisoslashtirilgan versiyasidan o'tishi aniq ko'rinadi.


3-rasm. Avtomatning ixtisoslashuvi

Generator to'g'ridan-to'g'ri asl maydonga predikat qo'ymaydi, aksincha parallel holat zanjirini yaratadi: buning sababi, yuqoridagi misolda bo'lgani kabi, ko'rib chiqilayotgan maydonning bir nechta misollari haqiqiy sarlavhada bo'lishi mumkin va asl o'tishlarni qayta yozish mumkin. predikatning faqat birinchi kelishiga mos kelishiga sabab bo'ladi. Olingan avtomat deterministik bo'lmasligi mumkin, ammo bu generator uchun hech qanday muammo tug'dirmaydi. Oddiyroq holat, agar predikat faqat paketga ma'lum protokolning to'g'ri formatlangan sarlavhasini kiritishni talab qilsa. Bunday holda, ixtisoslashtirilgan FSA ushbu protokol uchun shablon avtomatining nusxasi bo'lib, unda barcha belgilangan holatlar yakuniy holga keltiriladi.

4-rasm. Inkapsulyatsiya bilan ishlash
Ushbu bosqichda foydalanuvchi tomonidan belgilangan qoidalar NetPDL cheklovlari tufayli allaqachon ixtisoslashgan maydonlarni o'z ichiga olishi mumkin; misol sifatida, NetPDL IPv4 sarlavhasi uzunligi maydonini kamida 5 bo'lishga majbur qiladi, lekin foydalanuvchi undan kichikroq bo'lishini talab qiladigan qoidani belgilashi mumkin. Bunday vaziyatlarni hal qilish uchun maxsus ehtiyot choralari ko'rilmaydi, chunki nomuvofiqlik keyinchalik kompozitsiya, aniqlash va minimallashtirish orqali avtomatik ravishda hal qilinadi. Misol uchun ikkita va boshqa ixtisoslashtirilgan avtomatlar bo'ladi, ulardan biri paketga to'g'ri IPv4 sarlavhasini o'z ichiga oladi, ikkinchisi esa uzunlik maydonini 5 dan kichikdir. Agar mos kelmaydigan shartlar oldindan belgilansa, kompozit avtomat buziladi. yagona, qabul qilmaydigan holatga, ya'ni tan olingan paketlar to'plami bo'sh.
Filtr tarkibi
Jeneratör har bir qoida predikati uchun ixtisoslashtirilgan FSAni tayyorlagandan so'ng, yakuniy filtrni yaratish uchun barcha avtomatlarni yig'ish kerak.
Kompozitsiya bosqichi 2 xil operatsiyani bajaradi:
kapsülleme qoidalariga rioya qilgan holda turli protokollar bilan bog'liq bir nechta avtomatlarni birlashtirish;
mantiqiy operatorlar tomonidan bir nechta avtomatlarni birlashtirish.
Inkapsulyatsiya bir vaqtning o'zida bitta predikat bilan amalga oshiriladi, birinchi avlod bosqichidagi belgilardan keyin turli xil protokollar bilan bog'liq avtomatlarni birlashtiradigan o'tishlar kiritiladi. Misol tariqasida, 3-rasmda tasvirlangan holatda, inkapsulyatsiyani ko'rib chiqqandan so'ng paydo bo'lgan avtomat 4-rasmda ko'rsatilgan: belgilangan holat qo'shimcha chiqishga ega - dastlabki holatga qaytib keladigan o'tish; shu tarzda predikat AA BB qiymati birinchi duch kelgan sarlavhada bo'lmasa ham, u boshqa ichki o'rnatilgan sarlavhalardan birida bo'lsa ham mos keladi.
Ikkinchi operatsiya filtrlash bayonoti tahlil daraxti tomonidan belgilangan tartibda amalga oshiriladi va mantiqiy operatsiyalarni amalga oshirish va natijada olingan avtomatni ham deterministik, ham minimal qilish uchun taniqli algoritmlardan foydalanadi. Ushbu bosqichga qadar generatorda ishlatiladigan FSAlar befarq deterministik (DFA) yoki deterministik bo'lmagan (NFA) bo'lishi mumkin. Bu erda komplement operatorini amalga oshirishni qo'llab-quvvatlash uchun aniqlash bosqichi talab qilinadi, chunki to'g'ridan-to'g'ri NFAlarda to'ldirishni amalga oshirish uchun ma'lum algoritmlar mavjud emas. Shunday qilib, kompilyatsiya bosqichining natijasi filtrni ifodalovchi yagona minimal DFA hisoblanadi.
E. FSA asosidagi filtrlarning xususiyatlari haqida
FSA modeli qurilish orqali bizning maqsadlarimiz uchun muvaffaqiyatli ishlatilishi mumkin bo'lgan xususiyatlar to'plamini taqdim etadi. Birinchidan, yakuniy minimallashtirilgan DFA ma'lum bir to'plam yoki protokollar bo'yicha ma'lum qoidalar to'plamining kanonik, bir ma'noli, mashina-agnostik tasviridir: FSAlar fuqaroligi bo'lmagan paket filtrlari uchun semantik model sifatida foydalanish uchun mos keladigan rasmiyatchilik bo'lib, to'liq tavsiflaydi. keng qamrovli vakillikda protokol tuzilishi va filtrlash qoidalari.
SPAF filtrlari ham amaliy afzalliklarga ega. Cheklangan avtomatlar o'zlarining kirish satrlarini qat'iy ketma-ketlikda skanerlaydilar, shuning uchun protokol ma'lumotlar bazasi yoki filtrlash qoidalari qanchalik murakkab bo'lishidan qat'i nazar, SPAF har bir paket maydonini ko'pi bilan bir marta tekshiradi; Bu xususiyat, shuningdek, CFG-ga asoslangan yondashuvlar bilan erishib bo'lmaydigan har qanday filtr kompozitsion operatsiyalarida ham amalga oshiriladi. FSA-ga asoslangan yondashuv, shuningdek, har qanday o'ziga xos predikatlar tartibiga yoki filtrlash qoidalarining boshqa o'ziga xos xususiyatlariga befarq: yakuniy natija uning sintaktik shaklidan qat'i nazar, faqat filtr bayonotining semantikasiga bog'liq.
Yuqoridagi mulohazalardan kelib chiqqan holda, yakuniy avtomat uning mantiqiy xatti-harakatlarini taqlid qilish orqali dasturiy ta'minot yoki apparatni amalga oshirish uchun ko'rsatma sifatida ishlatilishi mumkin, shuning uchun biz FSA dan ishlab chiqarish jarayonini kod chiqarish tartiblaridan ajratadigan va ruxsat beruvchi oraliq tasvir sifatida foydalanishimizni oqlaydi. printsipial ravishda ko'p platformali kod emissiyasi, uning semantikasini to'liq saqlagan holda.
Shuni ta'kidlash kerakki, FSA modeli tomonidan taqdim etilgan o'rnatilgan samaradorlik ma'lum cheklovlar bilan qoplanadi. Birinchi nuqta shundaki, SPAF filtrlari paket maydonlarini simda paydo bo'ladigan tartibda tekshiradi. Mavjud kodni chiqarish texnikasi modelning xatti-harakatiga yaqindan taqlid qilganligi sababli, ba'zi maydonlar ularning qiymatini bilish muhim bo'lgunga qadar tekshirilishi mumkin: taqqoslash oxir-oqibat bajariladigan yo'lda foydasiz bo'lib chiqishi mumkin. Bu adabiyotda tasvirlangan ko'plab algoritmlar tomonidan boshqarilishi mumkin bo'lgan qisman ortiqchalik shaklini tashkil qiladi. Ruxsat etilgan predikatlarni baholash tartibiga rioya qilish, shuningdek, talab qilinadigan takrorlash miqdori tufayli yakuniy filtr uchun suboptimal holat va o'tish sonlarini keltirib chiqaradi. Ushbu mulohazalarga qaramay, eksperimental dalillar (V bo'limda keltirilgan) shuni ko'rsatadiki, bu muammo e'tiborga olinmasa ham yaxshi sifatli kod yaratilishi mumkin, chunki real protokollar va qoidalar to'plamini ko'rib chiqishda qisman ortiqcha tekshiruvlar soni kam. Nihoyat, paket baytlarini tartibli qayta ishlash boshqa paketlarni filtrlash yondashuvlari6 bilan umumiy xususiyat bo'lib, u odatda cheklov sifatida qaralmaydi.
IV. ISHLAB CHIQARISH KODLARNI YASALASH
Oxirgi avlod bosqichi - bu DFA filtrini bajariladigan shaklga o'tkazish uchun zarur bo'lgan kod emissiyasi. An'anaviy kompilyator arxitekturalariga parallel ravishda, ushbu bosqichda DFA oldingi qismdan (DFA quruvchisi) orqa qismga (kod emitenti) o'tkaziladigan oraliq tasvir sifatida ishlatiladi. DFA ni bajariladigan shaklga tarjima qilish qiyin yoki innovatsion vazifa bo'lmasa-da, bu bizning maqsadlarimiz, xususan, ishlash va xavfsizlik uchun juda muhimdir. Prinsipga ko'ra, filtr tuzilmasi muntazam ifodaga tarjima qilinishi va keyin Flex7, PCRE kutubxonasi8 yoki Ruler tomonidan taqdim etilgan kabi umumiy maqsadli mos keladigan dvigatelga berilishi mumkin. Biroq, amalda, bizning doiramiz va o'ziga xos talablarimiz odatiy iboralarning asosiy qo'llanmalaridan vaqtinchalik dvigatelning rivojlanishini asoslash uchun etarlicha farq qiladi: buning sababi shundaki, ko'pchilik regex dvigatellari orqaga qaytish yoki qayta yozish kabi qo'shimcha funktsiyalarni amalga oshiradi (Hukmdor misolida). ) umumiy maqsadli vositada foydali bo'lsa-da, bizning maqsadimiz uchun qo'shimcha xarajatlarning oldini olish mumkin bo'lgan manba hisoblanadi.
An'anaviy dasturlardan yana bir farq - bu xavfsizlikni ta'minlash. Kirish belgilari ketma-ketligi tugagach, DFA to'xtaydi; Ushbu xatti-harakat dasturiy ta'minotda xotira buferini (ma'lumotlar oqimini emas) kirish sifatida qabul qiladigan dastur tomonidan taqlid qilinishi kerak. Har bir bosqichda tugatish tekshiruvini amalga oshirish, albatta, mumkin bo'lsa-da, bu juda qimmatga tushishi mumkin. Tugatishdan tashqari, kirish oqimini xotira maydoni bilan almashtirish ham potentsial chegaradan tashqarida o'qish operatsiyalari tufayli xavfsizlik muammosini keltirib chiqaradi. Shunga qaramay, ulardan eng kam vaqt sarflagan holda qochish kerak. Ushbu jihatlar odatda e'tibordan chetda qolsa-da, FSA-ga asoslangan filtrlarni an'anaviy yondashuvlardan ajratib turadigan qo'shimcha filtrlash imkoniyatlarining aksariyati (masalan, pastadir bilan ishlash qobiliyati) mustahkam va samarali xavfsizlikni ta'minlash strategiyasiga bog'liq. Ushbu bo'limning qolgan qismida xavfsiz xotiraga kirish va tugatishni ta'minlashda yuqori unumdorlikka erishish uchun DFA filtri orqali amalga oshirilgan o'zgarishlar tasvirlangan. Keyinchalik, joriy orqa qismda ishlatiladigan kod ishlab chiqarish texnikasi hujjatlashtiriladi.
Muvaffaqiyatli - erta algoritm
Ko'pincha foydalanuvchi to'liq protokol muvofiqligini tekshirmasdan paketlarni maxsus qoidalarga moslashtirishga qiziqadi. Ushbu holatlarning ba'zilarida protokol tuzilishi bilan bog'liq ba'zi qo'shimcha jihatlarni e'tiborsiz qoldirib, filtr ish faoliyatini yaxshilash mumkin. Misol tariqasida, foydalanuvchi paketlarni faqat IP-manba manziliga qarab filtrlashni va IP-manzil maydoniga duch kelgan zahoti moslikni olishni xohlashi mumkin, hatto undan keyin noto'g'ri tuzilgan TCP sarlavhasi bo'lsa ham; aksincha, SPAF ning tabiiy xatti-harakati barcha ma'lum protokol sarlavhalarini kesib o'tish va tasdiqlashdir.
Ushbu holatlarni hal qilish uchun yakuniy holat hukmron bo'lgan barcha holatlarni sanab, ularni yakuniy deb belgilaydi va nihoyat avtomatni minimallashtiradigan DFAni soddalashtiradigan muvaffaqiyatli-erta algoritmini ishga tushirish mumkin. Ushbu operatsiya haqiqiy belgilar qiymatlaridan qat'i nazar, etarli kirish belgilari berilgan holda yakuniy holatga olib keladigan har qanday holatlar ketma-ketligini olib tashlaydi.
Muvaffaqiyatli-erta algoritmining ta'sirini 5-rasmda ko'rish mumkin: DFA grafigining pastki qismidagi har qanday etarlicha uzun yo'l yakuniy holatga olib kelganligi sababli, butun filial yakuniy deb belgilanadi va minimallashtirilganda qulab tushadi


5-rasm. Muvaffaqiyatli-erta algoritm
Umumiy holatda, muvaffaqiyatga erishish algoritmi qisqartirilgan yoki boshqa shaklda noto'g'ri shaklga ega bo'lgan ma'lum turdagi paketlarni qabul qilish orqali filtrning tan olingan paketlar to'plamini o'zgartiradi; agar bu istalmagan bo'lsa, algoritmni to'liq tahlil qilishga majburlovchi mos filtrlash predikati bilan o'chirib qo'yish mumkin.
O'tishni siqish algoritmlari
Ko'pgina filtrlarda katta hajmdagi kirish baytlari hech qachon ishlatilmaydi, chunki na protokol ma'lumotlar bazasi, na filtrlash qoidalari ular haqida hech narsa ko'rsatmaydi: bu baytlarni xotiradan o'qish protsessor tsikllari va xotira o'tkazish qobiliyatining aniq behuda ketishidir. Ishlashni yaxshilash uchun generator DFA grafiklarini baytni o'tkazib yuborish zanjirlarini qidiradi va iloji bo'lsa, ularning har birini barcha oraliq holatlar olib tashlangan holda to'g'ri uzunlikdagi bitta ko'p baytli o'tishlarga ixchamlashtiradi: bu yulduzni siqish algoritmini tashkil qiladi. .
Shunga o'xshash optimallashtirish boshqa muammoni hal qilish uchun yulduz bo'lmagan o'tishlarda amalga oshirilishi mumkin: filtr DFA'lar 8 bitli belgilarda ishlaydi, ammo zamonaviy protsessorlarning aksariyati ko'p baytli so'zlarni qayta ishlashda samaraliroq. O'tishni siqish algoritmi iloji boricha bir nechta keyingi o'tishlarni birlashtirish orqali ushbu nomuvofiqlikni bartaraf qiladi va natijada olingan dasturga kattaroq so'z o'lchamlarida ishlashga imkon beradi. O'tishni siqish yulduz siqilishiga o'xshash tarzda amalga oshiriladi: bitta holatdan boshlab, ko'p baytli bilan almashtiriladigan nomzod o'tishlarining uzun zanjirlarini qurish uchun o'tish grafigi o'rganiladi. Yulduzli siqilishdan farqli o'laroq, siqilishi kerak bo'lgan o'tishlarning maksimal soni mashina so'zining hajmi bilan cheklangan. Ushbu algoritm o'tish uchun davlatlarni almashtiradi. E'tibor bering, o'tishlar soni printsipial jihatdan eksponent ravishda oshishi mumkin: bu muammoni bartaraf qilish uchun, agar joriy qilinadigan o'tishlar soni sozlanishi mumkin bo'lgan chegaradan katta bo'lsa, ma'lum bir holat pastki to'plamida siqishni amalga oshirilmaydi.
Yulduzchani siqish ham, oʻtish davrini siqish ham FSA grafigidagi hech qanday yoʻlni olib tashlamaydi, shuning uchun filtr tomonidan tan olingan paketlar toʻplami oʻzgartirilmagan holda qoladi. Misol tariqasida, biz namunali avtomatni uning yulduzi va o'tish siqilishidan oldin ham (6a-rasm) va keyin (6b-rasm) xabar qildik.
O'tishni birlashtirishning yakuniy ta'siri muhim farq bilan DFA ko'p bosqichli o'tishga biroz o'xshaydi: ko'p bosqichli bir xil uzunlikdagi barcha o'tishlarni saqlaydi, shuning uchun natijada olingan ob'ekt hali ham boshqa kirish alifbosi bo'lgan avtomat bo'lib qoladi; aksincha, o'tishni birlashtirish turli uzunlikdagi o'tishlarni hosil qiladi va natijani qat'iy ravishda avtomat deb hisoblash mumkin emas, chunki endi aniq belgilangan kirish alifbosi yo'q. Bu hech qanday muammo tug'dirmaydi, chunki kompilyatsiya jarayonida siqilish bosqichidan keyin boshqa avtomat operatsiyalari bajarilmaydi; turli o'lchamdagi o'tishlarga ruxsat berish qo'shimcha moslashuvchanlikni ta'minlaydi, chunki butun tuzilishga ta'sir qilmasdan, faqat o'tish grafigining tegishli qismlari siqiladi.

6-rasm. Siqish algoritmlari
O'tish davrining siqilishi, shuningdek, boshqa filtrlash usullari bilan amalga oshiriladigan optimallashtirishga juda o'xshash yon ta'sirga ega, ba'zan atom birlashishi deb ataladi, bu maydon chegaralarini hisobga olmaganda, bir nechta qisqa jismoniy qo'shni maydonlarni kamroq kattaroq maydonlarga birlashtirish orqali ishlaydi. Kompilyatsiya jarayonida bu darajada aniq maydonlarning izi qolmaganligi sababli, o'tish siqilishi atomlarni birlashtirishning barcha imkoniyatlaridan avtomatik ravishda foydalanadi.
Ish vaqtida bajarilishi kerak bo'lgan operatsiyalar sonini kamaytirish va paketli xotiradan olinadigan ma'lumotlar miqdorini kamaytirishdan tashqari, qayta ishlangan avtomatik avtomat sezilarli darajada kichikroq, chunki ko'plab holatlar xavfsiz tarzda yo'q qilinishi mumkin.
C kodini yaratish
Oddiylik uchun hozirda amalga oshirilayotgan back-end siqilgan DFA-larni C funksiyalariga tarjima qiladi; Agar kerak bo'lsa, har qanday mashina uchun yig'ish kodini to'g'ridan-to'g'ri chiqarish uchun oddiy JIT kompilyatorini yaratish qiyin bo'lmaydi.
DFAlarning nisbatan sodda tuzilishi va xatti-harakatlarini hisobga olgan holda, bir nechta dasturiy ta'minotni amalga oshirish mumkin. To'g'ridan-to'g'ri avtomatlashtirishni xotirada saqlanadigan o'tish jadvali orqali qurish mumkin; bu yechim oldindan aytish qiyin bo'lgan xotiraga kirish naqshlari tufayli qo'shimcha xarajatlarga olib kelishi mumkin. Shu sababli, biz har bir holat uchun noyob identifikatsiyalangan kod fragmenti chiqariladigan boshqa klassik yondashuvga amal qilamiz: shu tarzda biz protsessorni oldindan yuklash va tarmoqni bashorat qilish birliklaridan yaxshiroq foydalanishga erishamiz.
Kirish oqimi yuqorida aytib o'tilgan paketli bufer bilan almashtirilganligini hisobga olsak, umumiy holatda, har bir o'tgan holat uchun quyidagi amallarni bajarish kerak:
• kiritish baytlarining kerakli hajmini xotiradan o‘qish;
• xotira ofset ko'rsatkichini mos ravishda oshirish;
• almashtirish ko'rsatmasi yordamida ko'p tomonlama shartli taqqoslashni amalga oshirish. Ishlar chiquvchi o'tish belgilaridan kelib chiqadi;
• belgilangan holatga o'tish.
Chiquvchi baytni o'tkazib yuborishga ega bo'lgan holatlar soddalashtirilishi mumkin, chunki u faqat ofset ko'rsatkichini belgilangan miqdorga oshirish va keyingi holatga o'tish uchun talab qilinadi. To'liq va soddalashtirilgan holatlar uchun kod emissiyasi namunasi 7-rasmda tasvirlangan.
Yuqorida aytib o'tilgan kodni chiqarish strategiyasi ish vaqtida boshqa operatsiyalar talab qilinmasligini ta'minlaydi va barcha baytlarni almashtirish va arifmetik operatsiyalar kompilyatsiya vaqtida amalga oshiriladi. Amalga oshirish muhiti minimal bo'lishi mumkin, chunki u faqat kirish paketi buferini va uning uzunligini ta'minlashi kerak. Boshqa vositalar (masalan, xotira himoyasi yoki tashqi kutubxonalar) kerak emas.
Mumkin bo'lgan optimallashtirish ko'p tomonlama bayonotlarning asosiyligini kamaytirish uchun arifmetik operatsiyalarni qo'llashdir. Misol tariqasida, IP sarlavhasi uzunligi bo'yicha tekshiruv hozirda har bir holatda 16 ta teg bilan 11 tomonlama shartli konstruktsiyaga tarjima qilingan10; xuddi shu operatsiya maydonning pastki 4 bitini an'anaviyroq maskalash bilan almashtirilishi mumkin.
Avtomat emissiyasi natijasida paydo bo'lgan C kodi keyingi optimallashtirishga moyil emas, chunki u allaqachon ixcham va ortiqcha bo'lmagan. Xususan, har bir amalga oshirilgan taqqoslash natijasini oldingi hisoblash orqali chiqarib bo'lmaydi va yakuniy natijaga tegishli; hech qanday keraksiz yoki takroriy xotira o'qishlari amalga oshirilmaydi. Hech qanday arifmetik amallar bajarilmaganligi sababli, ofset ko'rsatkichini doimiy qiymatga oshirishdan tashqari, C kompilyatori tomonidan amalga oshirilgan har qanday tegishli optimallashtirishning ta'siri juda kichik bo'lishi kutilmoqda. Xuddi shunday, tsikllarni ochish yoki o'zgartirish mumkin emas, chunki har bir himoya holati kompilyatsiya vaqtida mavjud bo'lmagan paket ma'lumotlariga bog'liq. Olingan kodni vizual tekshirish orqali bu taxminlar tasdiqlandi. Kompilyatorga qoldirilgan eng dolzarb vazifalar bu FSA asosidagi filtrlarda juda keng tarqalgan, lekin ko'pchilik protsessorlar tomonidan amalga oshirilmaydigan registrlarni taqsimlash va ko'chirishni birlashtirish va almashtirish bo'yicha ko'rsatmalar uchun yaxshi emissiya strategiyasini tanlash kabi past darajadagi mashina moslashuv protseduralari.
FSA asosidagi filtrlarning asimptotik murakkabligi va miqyosi
Paket filtrlarida asosiy tashvish - bu filtrlash qoidalari to'plamining murakkabligi oshishi bilan ularning xatti-harakati. Ko'pgina umumiy yondashuvlar eng yomon holatda chiziqli miqyosda bo'lsa-da, zamonaviy qoidalar to'plamining hajmini etarli darajada qo'llab-quvvatlash uchun yaxshi miqyoslilik talab qilinadi.
Agar barcha kerakli operatsiyalar (xotiradan o'qish, ko'rsatgichning o'sishi, ko'p yo'nalishli shartli tanlash, shartsiz o'tishlar) doimiy vaqtda bajarilgan bo'lsa, har qanday FSA asosidagi filtrning eng yomon bajarilish vaqti asimptotik proportsional ekanligini xulosa qilish mumkin edi. kirish paketining uzunligi. Paket hajmi doimiy (haqiqiy jismoniy qatlamga qarab) bilan yuqori chegaralanganligi sababli, FSA-ga asoslangan filtrlar O(1) w.r.t vaqtida ishlaydi. filtrlash qoidalarining soni, ularning murakkabligidan yoki protokol ma'lumotlar bazasi hajmidan qat'i nazar. Ishlashni baholash uchun ishlov berish tezligini o'lchash hali ham talab qilinadi (doimiy va multiplikativ omillar hali ham katta bo'lishi mumkin), bu asimptotik chegara bizning yondashuvimizning miqyosliligini baholashda tegishli natijadir.


g. 7. C kodining emissiyasi
Afsuski, FSA-larni real dunyo mashinalarida taqlid qilish kerak, ular uchun barcha kerakli operatsiyalar doimiy vaqtda bajarilishi mumkin deb taxmin qilish mumkin emas: xususan, kommutatsiya konstruktsiyasi kabi ko'p tomonlama qaror bayonotlari mahalliy darajada qo'llab-quvvatlanmaydi va mavjud. kompilyator tomonidan bir nechta oddiy ko'rsatmalarga aylantiriladi. Adabiyotda kommutatsiya operatsiyalarini amalga oshirish uchun bir nechta alternativ strategiyalar tasvirlangan: bizning testlarimiz uchun ishlatiladigan kompilyator (GCC 4.2) ko'p baytli maydonlardan kelib chiqadigan juda keng tarqalgan katta va siyrak yorliqlar to'plamlari uchun muvozanatli daraxtlardan foydalanishi kuzatilgan. Balanslangan qarorlar daraxtidagi darajalar soni tugunlar soni bilan logarifmik ravishda o'sib borayotganligi sababli, o'tish buyrug'ining eng yomon murakkabligi O (log N) bo'lishi kutiladi, bu erda N - almashtirish holatlari soni. Bu miqdor, o'z navbatida, shunga o'xshash filtrlarni yaratishda qoidalar soniga qarab (masalan, TCP seanslari yoki paketlarni manba/maqsad manzillari va portlari asosida tasniflaydigan xavfsizlik devori qoidalarini tan olish) taxminan chiziqli ravishda o'sadi, shuning uchun biz filtrni bajarish vaqtining o'lchamiga qarab o'sishini kutamiz. qoidalar to'plamining kardinalligining logarifmi.
Ushbu O(log N) asimptotik xatti-harakatini yaxshilashga kalitlarni kompilyatsiya qilish strategiyasini o'zgartirish orqali erishish mumkin: misol sifatida vaziyat qiymatlarini zich to'plamlarga solishtirish uchun minimal mukammal xeshlashdan foydalanish mumkin. Mukammal xeshlarni kompilyatsiya vaqtida hisoblash qimmat bo'lishi mumkin, lekin ular kalitlar soni bo'yicha doimiy vaqtda ishlaydi va FSA asosidagi filtrlarning asimptotik murakkabligini O (1) ga kamaytiradi. Adabiyotda tasvirlangan ba'zi usullar aniq tarmoq ilovalarini qo'llab-quvvatlashga qaratilgan, hatto dinamik yangilanishlargacha ham.
Xotiraga kirish xavfsizligi
Paket ma'lumotlarini saqlash uchun xotira buferi bilan C filtri ilovalarini taqdim etishning tabiiy yechimi chegaradan tashqari kirishlarni aniqlash va qayta ishlash muammosini keltirib chiqaradi. Arzimas va samarasiz javob - har bir kirishda joriy ofset va paket hajmi o'rtasidagi taqqoslashni amalga oshirish; ish vaqtida bajarilishi kerak bo'lgan chegaralarni tekshirish sonini kamaytirish orqali yaxshi natijalarga erishish mumkin. Ushbu muammoni hal qilish uchun biz chegaralarni tekshirishni minimallashtirish algoritmini ishlab chiqdik, u dasturning oz sonli joylariga yig'indisi chegaralarini qo'yadi.
Siqilgan DFA o'tish grafigi G ni hisobga olgan holda, biz har bir DFA o'tish uchun chekka va har bir holat uchun cho'qqiga ega bo'lgan vaznli yo'naltirilgan G' grafigini olamiz; chekka og'irliklari - mos keladigan o'tishlarning (ijobiy) bayt uzunligi. Ikki holat orasidagi masofa (a, b) a holatidan bgacha bo'lgan eng qisqa yo'l bo'lishi uchun biz G' ga metrikani o'rnatamiz. Ushbu ko'rsatkichni hisobga olgan holda, s cho'qqisining muvaffaqiyati d(s) dan masofa s dan erishish mumkin bo'lgan yakuniy holatgacha bo'lgan eng kichik masofadir. Agar kirish buferida d(s) baytdan kamroq holat mavjud bo'lsa, filtr ishlamay qolishi mumkin, chunki hatto eng yaqin yakuniy holatga ham erishib bo'lmaydi. Har bir chiquvchi o'tish ma'lum miqdordagi kirish ma'lumotlarini iste'mol qilganligi sababli, biz l(s, s0 ) s holatidan s holatga o'tishning uzunligini s 0 deb ataymiz: asosiy kuzatish shundan iboratki, agar d(s) ≥ d(s` ) bo'lsa. +l(s, s` ) to'g'ri keladi, keyin ko'rib chiqilayotgan o'tish bo'ylab s 0 kiritilgach, hech qanday tekshiruv o'tkazilmasligi kerak.
Chegaralarni tekshirish minimallashtirish algoritmi dastlabki holatga kirishdan oldin chegaralarni tekshirish (chunki bu nuqtada hech qanday taxmin qilish mumkin emas) va yuqorida aytib o'tilgan tengsizlikka rioya qilmaydigan barcha o'tishlarda, birinchi navbatda, protokol inkapsulyatsiyasining orqa qirralaridan kelib chiqadigan vaziyatda ishlaydi. grafik va ixtiyoriy protokol qismlaridan (masalan, IPv4 variantlari). 8a-rasmda DFA va 8b-rasmda masofaga izohlangan qirralar va holatlar bilan mos keladigan G0 ko'rsatilgan. 8a-rasmda qalin harflar bilan belgilangan davlatlar hech bo'lmaganda ularning kirish o'tishlaridan birida chegaralarni tekshirishni talab qiladi.
Ushbu algoritm tomonidan kodda joylashtirilgan chegaralar tekshiruvi nafaqat keyingi o'tish uchun etarli baytlar qolganligini, balki hisoblashning oxiriga etish uchun ham etarliligini tasdiqlaydi. Bu ta'sir umumiy maqsadli chegaralarni tekshirish optimallashtiruvchilari va DPF tomonidan amalga oshiriladigan (turli darajalarda) chegaralarni tekshirishga o'xshaydi; agregatsiya odatda mahalliy darajada ishlayotgan bo'lsa, bizning yechimimiz butun filtrni ko'rib chiqadi va juda yuqori samaradorlikka erishadi. Misol tariqasida, TCP seans filtri IP-opsiyalari bo'lmagan paket va juda keng tarqalgan Ethernet - IP - TCP tuzilmasi taqdim etilganda bitta o'lchamli tekshiruvni amalga oshiradi. Ushbu tekshirish filtr dasturining boshida minimal o'lchamdagi Ethernet - IP - TCP sarlavhalari ketma-ketligini o'z ichiga olish uchun juda qisqa paketlarni aniqlash uchun amalga oshiriladi. Xotira tekshiruvlarini iloji boricha tezroq joylashtirish, kesilgan paketlarni to'liq dekodlamasdan olib tashlashning yaxshi yon ta'siriga ham ega.

8-rasm. Bog'langan cheklarni joylashtirish
SPAF filtrlarini "C" tilida amalga oshirishni tugatish
FSA modeli har qanday avtomat uchun eng yomon tugatish shartini aniq belgilaydi, bu esa kirish satrining tugashi hisoblanadi; filtri avtomatlari, FSA o'tish grafigida har qanday halqalar mavjudligidan qat'i nazar, ularning cheklangan o'lchamdagi kirish oqimi to'liq qayta ishlanishi bilanoq to'xtatib, bu xatti-harakatni hurmat qiladi. Biroq shuni ko'rsatish kerakki, C kodini amalga oshirishning o'zi ham xuddi shunday yo'l tutadi.
Joriy tatbiq filtrni tugatishni ta'minlash uchun chegara tekshiruvlaridan foydalanadi. Filtr funksiyasi, agar cho'kish holatiga erishilgan bo'lsa (yakuniy yoki yo'qligidan qat'iy nazar) yoki xotira tekshiruvi bajarilmasa (bu holda natija har doim mos kelmaydi) qaytariladi. Koddagi orqaga sakrash, cheksiz tsikllarning potentsial manbai, hech qanday muammo tug'dirmaydi: deterministik avtomatning har bir o'tishi (kamida) bir baytni sarflaydi; C ilovasida bu xotira ofset ko'rsatkichining qat'iy monotonik tarzda oshirilganligiga aylanadi. Bu shuni anglatadiki, har qanday chekli kirish ketma-ketligi cheklangan miqdordagi holat o'tishlaridan keyin to'liq iste'mol qilinadi; Xotiradan keyingi har qanday o'qish muvaffaqiyatsiz chegara tekshiruvini ishga tushiradi, bu esa har qanday filtr oxir-oqibat tugashini isbotlaydi.
V. EXPERIMENTAL BAHOLASH
SPAF yondashuvini tasdiqlash uchun u eksperimental ravishda zamonaviy san'atning hozirgi holatini ifodalovchi boshqa texnikalar to'plami bilan taqqoslandi.
Ko'rib chiqilgan birinchi muqobil - BPF, hali ham paketlarni filtrlashning eng keng tarqalgan yondashuvlaridan biri; izohlash uchun qo'shimcha xarajatlarni oldini olish uchun biz zamonaviy JIT versiyasida tasvirlangan foydalandik. Ikkinchi tanlangan texnika eng zamonaviy CFG asoslangan yondashuvlardan biri sifatida qabul qilinadi va boshqa zamonaviy generatorlar bilan bog'liq ba'zi kamchiliklarni bartaraf BPF+ hisoblanadi. PathFinder kabi. Mahalliy UltraSparc BPF+ orqa tomoni sinov platformasiga mos kelishi uchun C kodini yaratish uchun o'zgartirildi. NetVM-ga asoslangan filtrlar ham tanlangan, chunki ular NetPDL protokoli tavsiflariga asoslanadi, shuning uchun bizning yondashuvimizga juda o'xshash ifodalilik darajasiga erishiladi, ular bilan NetPDL tavsiflari baham ko'riladi. Sinovlar o'tkazilayotgan vaqtda NetVM hech qanday xavfsizlikni ta'minlamadi, na tugatish, na xotira uchun. Nihoyat, Ruler filtrlari tanlangan, chunki ular SPAFga o'xshash FSAga asoslangan yondashuvdan foydalanadilar. Ruler ikkita kod chiqarish strategiyasidan foydalanishi mumkin: xotira jadvali boʻylab yurish yoki har bir holat uchun C kod parchasini chiqarish: ikkinchisi tezroq tanlanganligi sababli va Ruler optimallashtirishni amalga oshirmasa ham bizning yondashuvimizga yaxshiroq mos keladi. SPAF tomonidan qo'llab-quvvatlanadi. Taqqoslash uchun filtrlash qoidalari va protokol ma'lumotlar bazalari (agar mavjud bo'lsa) barcha generatorlarda imkon qadar o'xshash bo'lgan. Istisno sifatida, ta'kidlanganidek, ma'noli bo'lsa, SPAF va NetVM filtrlariga looplar va bir nechta inkapsulyatsiyalar kiritilgan; Nazariy jihatdan bir xil qobiliyatga ega bo'lsa-da, Ruler barcha testlarda soddalashtirilgan protokol tavsiflaridan foydalanadi, chunki bu xususiyatlarni manba tili bilan aniqlashning amaliy usullari yo'q.
Muhimligini ta'minlash uchun sinov filtrlari mustaqil ravishda sinov stolida ishga tushirildi, u RDTSC yo'riqnomasi yoki gettimeofday POSIX tizimi chaqiruvi yordamida uzoqroq muddatlarga (bir soniyadan ko'proq) ish vaqtini o'lchaydi. Barcha testlar uchun ishlatiladigan apparat platformasi Linux 2.6.24 yadrosiga asoslangan 32 bitli OTda ishlaydigan, 4 Gb operativ xotiraga ega ikki yadroli Intel E8400 Core 2 Duo protsessoriga ega Dell ish stantsiyasidir. C kodi GCC 4.2 bilan tuzilgan. Barcha filtrlash jarayonlari bitta protsessorga bog'langan va mashina boshqa tarzda tushirilgan. Ma'lumotlar issiq disk va protsessor keshlari bilan to'plangan.
Eng yomon holatda filtr ishlashi
Birinchi sinov seriyasi, I-jadvalda ko'rsatilgan oddiy filtrlar orqali eng yomon yo'lni bajarish uchun zarur bo'lgan soat sikllarini hisoblab chiqadigan kod sifatini baholashga qaratilgan. Biz bir xil paketlar to'plamini tan oladigan filtrlarni solishtirishga qiziqqanimiz sababli, ushbu testda NetPDL ma'lumotlar bazasidan foydalanildi. NetVM uchun ham, FSA-ga asoslangan yondashuv faqat tegishli protokollarning to'liq tavsiflarini o'z ichiga olishi uchun qisqartirildi. Yuqorida aytib o'tilgan barcha generatorlar BPF+ dan tashqari sinovdan o'tkazildi: x86 platformasi uchun JIT emitteri mavjud emasligi sababli, C kompilyatori tomonidan kiritilgan optimallashtirishni filtr generatorining o'zi tomonidan amalga oshirilgan optimallashtirishlardan ajratish qiyin bo'lar edi. Har bir generator va har bir filtr uchun olingan mashina kodi tekshirildi va bajariladigan eng yomon kod yo'lini yaratish uchun maxsus paket soxtalashtirildi. Sinov paketlari bir nechta inkapsulyatsiya darajasini o'z ichiga olmaydi, chunki ularni ba'zi yondashuvlar bilan boshqarish mumkin emas. BPF va NetVM o'lchovlari faqat tegishli filtrlash kodiga ishora qiladi, ayni paytda tegishli VM ramkalarining narxi olib tashlandi.

9-rasm. Eng yomon holatda filtrni baholash
Sinov natijalari 9-rasmda keltirilgan. “SPAF, check” va “SPAF, nocheck” ikkita ustuni mos ravishda yuqorida aytib o‘tilgan NetPDL tavsiflari va bog‘langan tekshiruvlar yoqilgan yoki o‘chirilgan holda tuzilgan FSA asosidagi filtrlarga tegishli. "SPAF, oddiy" seriyasi BPF imkoniyatlariga iloji boricha mos keladigan minimal NetPDL ma'lumotlar bazasi bilan yaratilgan. 9-rasm FSA-ga asoslangan dasturlarning eng yomon holati va kod sifati turli murakkablikdagi filtrlar uchun boshqa yondashuvlarga qaraganda o'xshash yoki yaxshiroq ekanligini ko'rsatadi. Eng yaxshi natijalarga 4 va 5 testlarda erishiladi, bunda bayonot murakkabroq bo'ladi, chunki FSA modeli ortiqcha tekshiruvlarni o'tkazmaslik uchun foydalanuvchilarning aniqlangan predikatlarini tartibga solishga qodir; Bu tendentsiya Ruler filtrlari uchun o'xshash bo'lib, ular kamroq optimallashtirilgan emissiya texnikasi tufayli sekinroq ishlaydi, bu esa ko'proq taqqoslash va xotiradan foydalanishga olib keladi. Sinov holatlari 1, 2 va 3 shuni ko'rsatadiki, agar foydalanilgan protokol ma'lumotlar bazasida boshqa yondashuvlar bajara olmaydigan shartlar mavjud bo'lsa ham, SPAF past murakkablikdagi qoidalar uchun tezkor filtrlarni yaratadi; "oddiy" ma'lumotlar bazasini ko'rib chiqishda natijalar yanada yaxshilanadi.
Ushbu ko'rsatkich, shuningdek, xavfsizlik tekshiruvlari ish vaqtining juda kam sarflanishiga olib kelishini ko'rsatadi; bu ularni filtrning boshida bitta taqqoslashgacha qisqartirish bilan to'liq oqlanadi; hosil bo'lgan filial xost protsessorining filial bashoratchisi tomonidan yanada arzonroq bo'ladi. Shuni ta'kidlash mumkinki, 1 va 5 sinov holatlarida xavfsizlikni tekshirishni yoqish filtrni bajarish vaqtini pasaytiradi: bu g'alati xatti-harakatlar hatto sinovlar ko'p marta takrorlanganda ham saqlanib qoladi va ko'rsatmalarni qayta tartiblash yoki boshqa quvur liniyasi muammolari bilan bog'liq bo'lishi mumkin. protsessor yoki o'lchash jarayonida kutilmagan xato manbalariga nisbatan juda kichik o'lchangan farqni (taxminan 1 soat tsikli) hisobga olgan holda.

10-rasm. Protokolning inkapsulyatsiya grafigi
Filtrning kengayishi
Ikkinchi sinov seriyasi filtrlash usullarini real stsenariyda baholash uchun mo'ljallangan bo'lib, u filtrning o'lchamlarini ta'kidlaydi. Qoidalar to'plami 1 GiB real paket izidan N eng faol (paketlar soni bo'yicha) TCP seanslarini ajratib olish orqali yaratilgan; paketlar tan olinishi kerak bo'lgan seanslar sonini 1 dan 128 gacha oshirish orqali filtrlangan. Uning o'lchamini hisobga olgan holda, iz Linux operatsion tizimi tomonidan taqdim etilgan disk keshiga mos keladi.
Natijalar o'lchangan o'rtacha kvadrat tezligini bildiruvchi 11-rasmda keltirilgan. Bir martalik kompilyatsiya vaqtlari hisobga olinmasa-da, bir nechta paketlarni filtrlash usullari o'rtasida haqiqiy taqqoslashni ta'minlash maqsadiga erishish uchun biz ramkalar yoki boshqa yordamchi, ammo muhim vazifalarga sarflangan vaqtni olib tashlamaslikka qaror qildik. Ushbu sinov usulida NetVM filtrlari virtual mashina tomonidan kiritilgan ortiqcha yuk tufayli guruhning eng sekin filtriga aylanadi. Ularning o'lchangan natijalari raqamlarni o'qish qobiliyatini saqlab qolish uchun xabar qilinmaydi.
Ushbu test uchun ishlatiladigan NetPDL ma'lumotlar bazasi 10-rasmda rekursiv inkapsulyatsiyalarni o'z ichiga olgan inkapsulyatsiya grafigi bilan ifodalanadi. Grafik BPF-dan olingan texnikalar yordamida tekshirilishi mumkin bo'lganidan kattaroqdir va IP sarlavhasi boshqa protokollarda inkapsullangan bo'lsa ham, SPAFga TCP seanslarini tanib olish imkonini beradi. Bu filtr bayonotlarida ko'rinmaydigan ba'zi protokollarning (masalan, VLAN va IPv6) bajariladigan kodda bo'lishiga olib keladi, chunki IP va TCP sarlavhalariga erishish uchun ularning o'tishi talab qilinishi mumkin; o'z navbatida, bu boshqa yondashuvlar talab qilganidan ko'ra, ish vaqtida ko'proq operatsiyalarni bajarishga olib keladi. Bu farq unchalik katta emas, lekin ba'zi bir qo'shimcha xarajatlarni oqlaydi, ayniqsa kam seanslar soni bilan.

Fig. 11. TCP session filtering performance

12-rasm. TCP seans filtrlari xotirasining bandligi
11-rasmda FSA asosidagi filtrlar seanslar soni ortib borishi bilan an'anaviy yondashuvlarning chiziqli o'rniga logarifmik egri chiziq bo'yicha ko'rib chiqilgan boshqa usullarga qaraganda sezilarli darajada yaxshilanishini ko'rsatadi. Bu IV-D bo'limda keltirilgan nazariy mulohazalardan kutilmoqda. Boshqa yondashuvlar, masalan, BPF+, tahlil qilingan protokollar va protokol xususiyatlarining kichik to'plami tufayli bir necha seanslarni filtrlashda kamroq qo'shimcha xarajatlarni ta'minlaydi; Shunga qaramay, ular SPAF dan yomonroq miqyosda, o'zaro faoliyat nuqtasi taxminan 10-16 seansda. Oddiyroq protokol ma'lumotlar bazasiga qaramay, Ruler filtrlari SPAF bo'yicha hamkasblariga qaraganda sekinroq ishlaydi, chunki emissiya vaqtini optimallashtirishning yo'qligi xotiraga kirish va taqqoslashlar sonining ko'payishiga olib keladi. Shuni ham ta'kidlash kerakki, SPAF mutlaq kadr tezligi yaxshi, chunki hatto murakkab holatlarda ham sinov mashinasida paketlarni gigabit Ethernet uchun zarur bo'lgan taxminan 150% tezlikda filtrlash mumkin, hatto paketlarni olish uchun sarflangan vaqt ham. xotira hisobiga kiritilgan.
Xotira iste'moli va potentsial holat-fazo portlashi
Cheklangan avtomatlar bilan bog'liq muammo bu NFA ni DFA ga o'tkazishda yuzaga kelgan holatlar sonining eksponensial portlashidir. Bu muammo DFA-larning tajovuzni aniqlash tizimlari kabi real dunyo ilovalarida tez-tez uchrab turadigan ma'lum naqshlar to'plamlarini engish uchun ichki qobiliyatsizligidan kelib chiqadi. Umumiy holatda n ta holatdagi NFA aniqlanganda O(2 n) holatning DFA ga olib kelishi mumkin; joriy qilingan qo'shimcha holatlar ortiqcha emas va ularni minimallashtirilganda olib tashlash mumkin emas.
Ushbu muammoning yuzaga kelishini o'z kontekstimizda tekshirish uchun biz filtrlash bayonotlari va murakkabligi ortib borayotgan protokol ma'lumotlar bazalari uchun xotira ishg'olini o'lchovlarini oldik. Ishlash vaqtida xotira ajratilmaganligi sababli, juda kichik va qattiq stek maydonidan tashqari, o'lchovlar to'g'ridan-to'g'ri POSIX nm buyrug'i bilan bajariladigan kodda amalga oshirildi; Ruler va BPF+ filtrlari shu tarzda ob'ekt kodiga kompilyatsiya qilingani uchun kiritilgan.
Scalability w.r.t. filtr qoidalarining murakkabligi BPF+ tomonidan qo'llab-quvvatlanadiganga taqlid qiluvchi qisqartirilgan protokol ma'lumotlar bazasi bilan tuzilgan TCP sessiya filtrlari bilan baholandi; aniqrog'i, biz 10-rasmda qalin harf bilan ko'rsatilgan barcha protokollarni va barcha inkapsulyatsiya munosabatlarini kiritdik. 12-rasmda keltirilgan natijalar xotira iste'moli filtrlangan TCP seanslari soni bo'yicha keng chiziqli ekanligini ko'rsatadi, hech qanday holatda portlash sodir bo'lmaydi; bundan tashqari, Ruler va SPAF obyekt fayllari tendentsiyasi kutilganidek o'xshash. Nihoyat, mutlaq kod hajmi juda kichik, shuning uchun hatto katta filtrlar ham zamonaviy protsessor keshlariga mos kelishi mumkin. BPF+ bilan taqqoslash shuni ko'rsatadiki, SPAF taxminan ikki barobar ko'proq joy talab qiladi; Bu, ayniqsa, oldingi bo'limlarda aytib o'tilganidek, biz foydalanadigan oddiy FSAlar qo'shimcha xotira sarfiga olib keladigan takroriy qismlarni o'z ichiga olishini hisobga olsak yaxshi natijadir. Ruler bilan solishtirganda, SPAF filtrlari qo'llaniladigan avtomatlarni siqish texnikasi tufayli kamroq joy ishlatadi.

Ikkinchi test ethernet.src == 00:11:22:33:44:55 va ip.src == 11.22.33.44 va tcp.sport == filtri bilan II-jadvalning ikkinchi ustunida keltirilgan protokol ma'lumotlar bazalarini kompilyatsiya qilishni o'z ichiga oldi. 80. Agar boshqacha ko'rsatilmagan bo'lsa, to'liq inkapsulyatsiya munosabatlari ishlatilgan: bu masalan, masalan. TCP IPv4 yoki IPv6 ga amal qilishi mumkin va natijada olingan avtomatda barcha protokollar to'plami mavjud. Ikkinchi test natijalari xuddi shu jadvalning uchinchi va to'rtinchi ustunlarida e'lon qilinadi va muvaffaqiyatli-erta va avtomatlarni siqish algoritmlaridan oldingi va keyingi holatni ko'rsatadi. Ba'zi protokollar (masalan, IPv6) ko'proq shtatlarni ko'rsatishni talab qilsa-da, yakuniy natijani, ayniqsa siqishdan keyin boshqarish mumkin. Shuni ham yodda tutish kerakki, protokol ma'lumotlar bazasining narxi asosan qat'iy va asosan filtr qoidalari to'plamining o'lchamiga bog'liq emas: IPv6 holatida qo'shilgan holatlarning asosiy qismi kengaytma sarlavhalarini tahlil qilish uchun ishlatiladi va emas. keyingi avtomatda takrorlanadi.
Eksperimental testlar faqat empirik dalillarni taqdim etishi mumkin bo'lsa-da va har doim davlat makonida portlashni keltirib chiqaradigan protokollar va filtr qoidalarini loyihalash mumkin bo'lsa-da, biz haqiqiy protokollar to'plamidan va filtr qoidalaridan hech narsa kutmaymiz. Buning sababi shundaki, filtrlar ixtiyoriy matn qismlariga mos keladigan oddiy iboralar kabi erkin shaklda emas. Misol tariqasida, paketli filtrlarda .∗ naqshini (muammolar manbai sifatida keng ma'lum bo'lgan) topish juda kam uchraydi, chunki u cheksiz o'lchamdagi maydonga to'g'ri keladi, tarmoq protokollari esa, asosan, sobit bo'lgan sobit ketma-ketliklar nuqtai nazaridan tavsiflanadi. - uzunlikdagi maydonlar; takroriy yoki o'zgaruvchan o'lchamdagi maydonlarga duch kelganda ham, ularning maksimal hajmi oldindan o'qilgan ma'lumotlar yoki paketlarning maksimal hajmi bilan cheklanadi; bundan tashqari, umuman olganda, har bir kichik naqsh kirish satrining ko'p pozitsiyalarida boshlanishi mumkin, bu har bir qoidadagi barcha mumkin bo'lgan yutuqlarni kuzatib borish uchun zarur bo'lgan katta miqdordagi replikatsiyaga olib keladi. Aksincha, paket filtrlari pastki naqshlari (masalan, maxsus protokollar, umumiy yoki ixtisoslashtirilgan) har doim aniq belgilangan pozitsiyalar to'plamida boshlanadi (ya'ni, oldingi protokol to'liq tahlil qilingandan so'ng), shu bilan kosmik holat portlashining yana bir umumiy manbasini inkor etadi.
Filtrni kompilyatsiya qilish vaqti
Jeneratorni optimallashtirish (hosil bo'lgan filtrlarni optimallashtirishga nisbatan) bu ish uchun asosiy maqsad emas edi; ammo to'liqligi uchun biz filtrni yig'ish vaqtlari haqida ba'zi ma'lumotlarni xabar qilamiz.
Joriy amalga oshirishimizda ishlab chiqarish vaqtlari soniyalardan (kichik protokol ma'lumotlar bazalari va oddiy filtr bayonotlari uchun) bir necha soatgacha (masalan, to'liq protokol ma'lumotlar bazasi va 128 TCP seans filtri uchun) o'zgarishi mumkin. Biz taxmin qilamizki, bu ko'rsatkichlarni kattalik buyurtmalari bilan yaxshilash mumkin, chunki generator xotirani tejash uchun ishlashni o'zgartirish uchun mo'ljallangan; Bundan tashqari, joriy Java joriy etilishining profilli hisobotlari shuni ko'rsatadiki, axlat yig'ish kabi vazifalarni bajarish uchun tegishli vaqt sarflanadi: boshqa til (masalan, C++) bog'liq qo'shimcha xarajatlarni kamaytirishi mumkin. Bundan tashqari, ko'proq optimallashtirilgan algoritmlarni qo'llash mumkin (masalan, bitta o'tishda aniqlash va minimallashtirish orqali), ular yuqorida aytib o'tilgan tanlov tufayli chetlab o'tilgan.
VI. XULOSALAR VA KELAJAKDAGI ISHLAR
Biz yuqori darajali protokol formatidagi ma'lumotlar bazasi va filtr predikatlaridan Cheklangan Davlat Avtomatlarini yaratishga asoslangan paketli filtr generatori SPAFni loyihalashtirdik, prototip qildik va baholadik. SPAF tezkor va samarali filtrlarni chiqarishga qaratilgan va shu bilan birga xotiraga kirishning to'g'riligi va tugatish nuqtai nazaridan barcha tegishli xavfsizlik xususiyatlarini saqlab qoladi.
FSA modeli shu maqsadda ayniqsa qimmatlidir, chunki u har qanday mumkin bo'lgan fuqaroligi bo'lmagan paketli filtrni ifodalash uchun etarlicha kuchli, hatto tunnel o'tkazish, bir nechta inkapsulyatsiya va takroriy sarlavha qismlari kabi boshqa yondashuvlar tomonidan qo'llab-quvvatlanmaydigan rivojlangan konstruktsiyalarni o'z ichiga olgan bo'lsa ham. FSA filtrlarida har bir sarlavha maydoni qurilish bo'yicha ko'pi bilan bir marta tekshiriladi; Bu xususiyatning o'zi predikatlarni baholashda ortiqcha miqdorini sezilarli darajada cheklaydi, bu paketli filtrlarda samarasizlikning asosiy manbai. Aksincha, an'anaviy, optimallashtirishga asoslangan yondashuvlar, o'z tabiatiga ko'ra, natijada olingan kod sifati haqida hech qanday qattiq kafolat bera olmaydi. SPAF, shuningdek, aniq belgilangan avtomatlashtirilgan mantiqiy operatsiyalardan foydalangan holda filtr tarkibini ahamiyatsiz boshqarishga qodir; bir nechta filtrlarni ketma-ketlashtirish yoki evristikaga murojaat qilish talab qilinmaydi. Paket filtrlari uchun noaniq semantik model bo'lishdan tashqari, FSAlar, shuningdek, sodda va tezkor dasturiy ta'minot va apparat ta'minotiga ega, bu esa samarali kod emissiyasi uchun qo'llanma sifatida ikki baravar ko'payadi.
Ushbu texnikani maydonda isbotlash uchun biz tashqi protokol ma'lumotlar bazasi va foydalanuvchi tomonidan belgilangan qoidalardan filtrlar yaratuvchi filtr generatorini ishlab chiqdik. Filtr DFA'lari mavjud apparat yoki dasturiy ta'minot dvigatellarida bo'lgani kabi ishlatilishi yoki orqa tomondan C kodiga tarjima qilinishi mumkin. Shuningdek, biz bir vaqtning o'zida baytni qayta ishlash o'rniga o'z operatsiyalarini asosiy mashinaning so'z hajmiga moslashtiradigan va xotira xavfsizligini va ish vaqtida to'liq jamlangan chegaralangan tekshiruvlar orqali tugatishni ta'minlaydigan maxsus DFA ijro mexanizmini ishlab chiqdik.
SPAF filtrlarining ishlash vaqtida ishlashi va xotira ishg'olligi sintetik va real dunyo mezonlarida baholangan. Sinov natijalari shuni ko'rsatadiki, FSA asosidagi filtrlar oddiy va murakkab filtrlarda BPF+ kabi boshqa zamonaviy yondashuvlarga o'xshash yoki yaxshilangan darajada ishlaydi; SPAF filtrlari filtrlash qoidalari soni ortib borishi bilan yaxshi miqyosda bo'lishi ham ko'rsatilgan. Ishlash vaqtidagi xavfsizlik tekshiruvlarining o'lchanadigan qo'shimcha xarajatlari kichik va ish vaqti (har bir paket uchun bir nechta tekshiruvlar amalga oshiriladi) va xotira bandligi (har bir filtrga bir nechta tekshiruvlar qo'shiladi) uchun muhim jarimalarni keltirib chiqarmaydi. Umuman olganda, SPAF yondashuvi murakkabligi ortib borayotgan bo'lsa ham, tuzish oson va ishlatish uchun samarali bo'lgan paketli filtrlarni yaratishning samarali va oddiy usuli hisoblanadi.
Mumkin bo'lgan muammolar orasida, xususan, DFAlarga ta'sir qiluvchi keng tarqalgan muammo - bu muayyan tanqidiy naqshlarni davolashda davlat makonida sodir bo'ladigan portlash; bu muammo hujumni aniqlash tizimlari kabi boshqa naqshga asoslangan detektorlarda DFA qabul qilinishini cheklovchi omil hisoblanadi. Agar printsipial jihatdan xuddi shunday SPAF filtrlarida sun'iy ravishda ishga tushirilishi mumkin bo'lsa ham, real protokol sarlavhalari tuzilishi tufayli amalda bu sodir bo'lishi dargumon deb hisoblaymiz. Eksperimental natijalar shuni ko'rsatadiki, real sharoitlarda xotira ishg'ollari muntazam ravishda o'sib boradi, katta filtrlar va to'liq protokol ma'lumotlar bazalari kuzatilishi mumkin.
SPAF yondashuvi paketlarni filtrlashdan tashqari paketlarni demultiplekslashni amalga oshirish uchun osongina kengaytirilishi mumkin. Bu bizning joriy generatorimiz tomonidan yakuniy holatlarni mos keladigan filtrlash qoidalarining identifikatorlari bilan belgilash orqali qisman qo'llab-quvvatlanadi; to'liq qo'llab-quvvatlash dinamik avtomatlar yaratish va kod ishlab chiqarishni talab qiladi, kelajakdagi tadqiqotlar ob'ekti bo'ladigan vazifalar. SPAF ning kelajakdagi yana bir kengaytmasi yuqori qatlamli filtrlash va trafik tasnifi uchun foydali boʻlgan seans jadvallari kabi statistik konstruksiyalar bilan oʻzaro aloqalarni (masalan, qidirish va yangilanishlar) yoqish boʻlishi mumkin.
Xulosa qilib aytganda, SPAF ishlov berish tezligi, xotira iste'moli, protokol formatlari va filtrlash qoidalarini belgilashda moslashuvchanlik va soddalik, samarali filtr nuqtai nazaridan kerakli xususiyatlarning ko'pini birlashtirgan paketli filtrlarni ishlab chiqarish orqali zamonaviy holatni yaxshilaydigan yondashuv sifatida ko'rsatildi. tarkibi va xavfsizlikni ta'minlash uchun kam ish vaqti qo'shimcha xarajatlari. Filtr generatorining rivojlanishi va sinov natijalari bizning da'volarimiz hayotiyligini qo'llab-quvvatlaydi.