نمونه جدید x در صورتی مطابق با قانون R در نظر گرفته می شود که فراکره با مرکز x و شعاع ثابت v با فرا مستطیل تعریف شده به وسیله R اشتراک داشته باشد. برای تولید مجموعه مناسبی از قوانین چندین اجرای متوالی از الگوریتم تکاملی مورد نیاز است.

جی آی^[۱۱۸] و داسکوپتا (۲۰۰۴) در کاری دیگر از نمایش مقدار حقیقی رویاستفاده کرده اند اما، شناساگرهای منفی فراکره­ای با بهره گرفتن از روشی متفاوت تولید می شوند. ابتدا، جمعیت اولیه­ای از شناساگرهای منفی به صورت تصادفی تولید می­شوند. سپس این شناساگرها از طریق یک فرایند تکراری بالغ می شوند. در هر تکرار، شعاع هر شناساگر به صورت محاسبه می­ شود.تغییر پذیری اطراف یک نمونه عادی را نشان می­دهد. در طی فرایند تکرار، شناساگرها به دور از داده ­های عادی و شناساگرهای موجود دیگر حرکت داده می شوند. شناساگرها بر اساس همپوشانی رتبه بندی می شوند. شناساگرهای بزرگتر برازندگی بهتری داشته و برای نسل بعدی انتخاب می شوند. شناساگرهای کوچکتر حذف شده و با کپی­هایی از شناساگرها با برازندگی بالاتر جایگزین می شوند. به علاوه، شناساگرهای تصادفی جدید برای کشف نواحی جدید از فضای غیر عادی تولید می شوند. فرایند تولید شناساگرها زمانی پایان می یابد که مجموعه شناساگرهای بالغ بتوانند پوشش مناسب از فضای غیر عادی را فراهم کنند.
جی آی و داسکوپتا (۲۰۰۹) یک الگوریتم انتخاب منفی حقیقی جدید به نام V-detector پیشنهاد داده­اند. در این الگوریتم از روش های آماری برای تخمین میزان پوشش فضای غیر عادی توسط شناساگرها استفاده کرده اند. این الگوریتم شامل دو ویژگی است :
پوشش بالایی از فضای غیر عادی با بهره گرفتن از تعداد محدودی از شناساگرها با اندازه­ های متغیرحاصل می شود.
تخمین پوشش فضای غیر عادی توسط شناساگرها در فرایند تولید شناساگرها تعبیه شده است .
این الگوریتم از استراتژی تولید – آزمایش NS با نمایش مقدار حقیقی روی فضای دادهاستفاده می کند. نمایش فراکره ای برای نمایش شناساگرها استفاده شده است. مراکز شناساگرها به صورت نقاط تصادفی درفضایتولید می­شوند. اگرنقطه تولید شده جدید عضو عادی باشد و یا توسط شناساگرهای موجود پوشش داده شود، آن شناساگر حذف خواهد شد. الگوریتم تعداد تلاش های نا موفق برای تولید شناساگرهای جدید به وسیله چنین نقاط تصادفی را محاسبه می کند. در صورتی که تعداد تلاش های ناموفق پی در پی به m برسد ، فرایند تولید شناساگرها پایان می یابد .پارامتر m بر اساس میزان پوشش مورد نظر α با بهره گرفتن از رابطه محاسبه می شود. اگر نقطه تولید شده جدید عضو مجموعه غیر عادی باشد و یا توسط هیچ کدام از شناساگرهای موجود پوشش داده نشود، پس آن نقطه به عنوان مرکز یک شناساگرجدید با بیشترین مقدار ممکن شعاع در نظر گرفته می شود.
از معایب این الگوریتم می توان به تولید تعداد زیادی شناساگر برای پوشش فضای غیر عادی و تولید شناساگرهای بزرگ برای پوشش بهتر فضای غیر عادی اما عدم توجه به همپوشانی آن­ها با شناساگرهای دیگر اشاره کرد.

۲-۷-۲-۳- الگوریتم انتخاب مثبت :

در مقابل الگوریتم انتخاب منفی، تکنیک­های انتخاب مثبت در زمینه های بسیاری از جمله تشخیص الگو، خوشه بندی به طور وسیعی استفاده می شوند. در این تکنیک ها مجموعه ای از شناساگرها به گونه ای تولید می شود که با نمونه­های عادی به جای نمونه­های غیر عادی مطابقت می کنند. هدف از تکنیک انتخاب مثبت تولید مجموعه از شناساگرها برای پوشش مناسب فضای عادی (ایجاد مدلی از مجموعه عادی برای دسته بندی یک نمونه به عنوان عادی یا غیر عادی ) است. ساده ترین تکنیک انتخاب مثبت می تواند با بهره گرفتن از روش نزدیک­ترین همسایه ساخته شود. اگر یک نمونه ورودی در همسایگی یک نمونه عادی باشد، آن نمونه به عنوان عادی برچسب زده خواهد شد. همچنین، در روشی پیچیده می توان شناساگرهای مثبت را با بهره گرفتن از برخی از الگوریتم های خوشه بندی بر روی نمونه های عادی تولید کرد. بنابراین یک نمونه ی ورودی بر اساس فاصله اش با یک خوشه به عنوان نمونه متعلق به یک آن خوشه در نظر گرفته می شود. در شکل ۲-۵ نمایی از تکنیک انتخاب مثبت نشان داده شده است.
شکل ۲‑۵: تکنیک انتخاب مثبت(داسکوپتا و گونزالس ، ۲۰۰۲) .
بلاچاندران و همکاران (۲۰۰۷) ، رویکرد توصیف منفی(انتخاب منفی) را با رویکرد توصیف مثبت (انتخاب مثبت) پیاده سازی شده با Kd-tree مقایسه کرده اند. اگرچه رویکرد توصیف مثبت نتایج دقیق تری را ارائه می دهد، اما این رویکرد در مقایسه با توصیف منفی از هزینه های زمانی و فضایی بالایی برخوردار است. جی آی و داسکوپتا (۲۰۰۶)SVM ، را به عنوان تکنیک انتخاب مثبت استفاده کرده و با الگوریتم V-detector مقایسه کردند. SVM نتایج بهتری را فراهم کرده بود ، اما کارایی آن بسیار وابسته به انتخاب مناسب تابع کرنل است .
به طور کلی با توجه به کاربرد هر دو تکنیک انتخاب مثبت و انتخاب منفی می توانند انتخاب معقولی باشند. به عنوان مثال برای یک کاربرد با تعداد زیادی از نمونه های عادی، انتخاب منفی گزینه مناسب تری خواهد بود (داسکوپتا و گونزالس ، ۲۰۰۲).

۲-۷-۲-۴- الگوریتم انتخاب کلون^[۱۱۹]

از بین آنتی‌بادی‌هایی که در مخزن^[۱۲۰] سیستم ایمنی قرار دارند، آنتی‌بادی که بیشترین پیوستگی را با آنتی‌ژن داشته باشد را برای تکثیر شدن و مقابله با آنتی‌ژن‌های غیرعادی انتخاب می‌کند.

۲-۷-۲-۵- تئوری خطر^[۱۲۱]

این تئوری براساس اختلاف بین سلول‌های سالم و سلول‌های مجروح در بدن عمل می‌کند. زمانی که سلول‌ها به طور عادی (در اثر مقابله با آنتی‌ژن‌ها) می‌میرند، سیگنال هشدار تولید نمی‌شود، اما زمانی‌که سلول‌ها به طور غیرعادی(آلوده شدن به وسیله آنتی‌ژن) مجروح و یا می‌میرند سیگنال هشدار تولید می‌شود. سلول‌های دندریکی^[۱۲۲] به عنوان واسط مهمی جهت فعال کردن سیگنال هشدار دهنده برای سیستم ایمنی تطبیقی عمل می‌کنند.

۲-۸- جمع بندی

در این فصل به بررسی مفاهیم اصلی به کار رفته در این پایان نامه همچون شبکه‌های اقتضایی متحرک و سیستم‌های تشخیص نفوذ و سیستم‌های ایمنی پرداخته شده است. مفهوم شبکه‌های اقتضایی متحرک، خصوصیات و چالش‌ها و مسائل امنیتی آن‌ها و همچنین انواع حملاتی که در این‌گونه شبکه‌ها رخ می‌دهد مورد بررسی قرار گرفته است. در ادامه به سیستم‌های تشخیص نفوذ و روش‌های تشخیص نفوذ اشاره شده است و در نهایت سیستم ایمنی مصنوعی به عنوان راهکار جدیدی در تشخیص ناهنجاری معرفی گردیده است. سیستم ایمنی مصنوعی الهام گرفته از سیستم ایمنی بدن انسان است که به تشخیص رفتارهای ناهنجار در سیستم‌ها و شبکه‌ها می‌پردازد. در این فصل مروری اجمالی بر الگوریتم ها و تئوری های سیستم ایمنی مصنوعی ، مانند الگوریتم انتخاب منفی صورت گرفته است. الگوریتم انتخاب منفی یکی از الگوریتم‌های مهم سیستم ایمنی مصنوعی می باشد که در بسیاری از کارهای تحقیقاتی به کار گرفته شده است. در تحقیقات روش‌های مختلفی برای تولید شناسگرها در این الگوریتم پیشنهاد شده است که به آنها اشاره شد. همچنین الگوریتم های دیگر نیز در این سیستم مانند الگوریتم انتخاب مثبت که عملکرد دقیقاً عکس عملکرد الگوریتم انتخاب منفی دارد و نیز الگوریتم انتخاب کلون و الگوریتم تئوری خطر معرفی گردید. در فصل بعد مروری بر ادبیات موضوع تشخیص نفوذ خواهیم داشت.

فصل سوم :ادبیات موضوع تشخیص نفوذ در شبکه های اقتضایی متحرک

۳-۱- مقدمه

در فصل گذشته مفاهیم اصلی در حوزه تحقیق، همچون شبکه های اقتضایی متحرک، ویژگی­های آنها، تهدیدها و انواع راه های مقابله با این تهدیدها ، سیستم ایمنی مصنوعی و تئوری­های مختلف موجود در این حوزه را بررسی کردیم. همانطور که اشاره شد به دلیل ویژگی­های خاص شبکه ­های اقتضایی متحرک، ازجمله پویایی بالای این شبکه­ ها و نیز محدودیت منابع آنها روش­های تشخیص نفوذ مبتنی بر ناهنجاری برای این شبکه ها مناسب است. روش­های تشخیص نفوذ مبتنی بر ناهنجاری به سه دسته کلی مبتنی بر خوشه بند­ها، مبتنی بر طبقه­بندها و مبتنی بر سیستم ایمنی مصنوعی قابل تقسیم بندی می باشند. حال در این فصل به بررسی پژوهش­های مرتبط با این حوزه ها خواهیم پرداخت .

۳-۲- تشخیص نفوذ مبتنی بر طبقه بندها

در روش‌های مبتنی بر طبقه‌بندها از الگوریتم‌های طبقه‌بندی برای پیدا کردن رفتارهای ناهنجار در شبکه استفاده می‌شود. رفتار عادی شبکه از قبل به عنوان یک کلاس عادی در نظر گرفته می‌شود و سپس رفتار فعلی شبکه بر اساس یک الگوریتم طبقه‌بند، طبقه‌بندی می‌شود. رفتار فعلی شبکه به عنوان یک رفتار ناهنجار تشخیص داده می‌شود اگر خارج از کلاس عادی قرار گیرد. در (علیخانی و آبادی ، ۲۰۱۱) الگوریتم‌های طبقه‌بند SVM و RIPPER و در (سن سون^[۱۲۳] و همکاران ، ۲۰۰۰) از الگوریتم طبقه‌بند مبتنی بر درخت تصمیم C4.5 برای تمایز بین رفتارهای عادی و غیرعادی استفاده شده است.
سان^[۱۲۴] و همکاران (۲۰۰۷) روشی بر اساس دسته‌بندها برای تشخیص ناهنجاری با توجه به تحرک گره‌ها در شبکه‌های اقتضایی متحرک ارائه کرده‌اند. در این روش نرخ تغییر پیوند (LCR_recent) محاسبه می‌شود و داده‌های آموزشی به گونه‌ای انتخاب می‌شود که متوسط نرخ تغییر پیوند آن کمترین فاصله اقلیدسی را با LCRrecent داشته باشد. بنابراین، دسته‌بندی با بهره گرفتن از داده‌های آموزشی منطبق شده با تغییرات شبکه انجام می‌شود.
ناکایاما^[۱۲۵] و همکاران (۲۰۰۷) روشی پویا مبتنی بر تحلیل مولفه اصلی (PCA^[126]) برای تشخیص ناهنجاری در شبکه‌های اقتضایی متحرک با پروتکل مسیریابی AODV ارائه کرده‌اند. در این روش از کوواریانس سراسری داده‌های عادی و وزن‌دهی آن‌ها براساس یک رابطه فراموشی در بازه‌های زمانی متوالی برای به روزرسانی نمای عادی ایجاد شده استفاده می‌شود. همچنین علیخانی و همکاران (۲۰۱۱) از تحلیل مؤلفه‌های اصلی افزایشی برای ایجاد و به روزرسانی نمای عادی استفاده کرده‌اند.
شبکه‌های عصبی هم در مد تک‌کلاسه و هم در مد چندکلاسه بکار می‌روند. تکنیک شبکه‌ی عصبی چند کلاسه در دو مرحله عمل می‌کند: مرحله‌ی اول شبکه‌ی عصبی با بهره گرفتن از داده‌های آموزشی کلاس‌های نرمال مختلف را یاد می‌گیرد. در مرحله‌ی دوم هر نمونه‌ی داده به عنوان داده‌ی ورودی شبکه‌های عصبی آماده‌سازی می‌شود. اگر شبکه ورودی تست را بپذیرد به عنوان داده‌ی نرمال شناخته می‌شود و اگر شبکه، داده‌ی تست را رد کند به عنوان داده‌ی ناهنجار تلقی می‌شود (سن سون و همکاران ، ۲۰۰۰). شبکه‌های عصبی تکرار شونده برای تشخیص ناهنجاری در مد تک‌کلاسه استفاده می‌شوند. شبکه‌های عصبی پیش‌رونده چندلایه از تعداد برابر نرون‌ها به عنوان ورودی‌ها و خروجی‌ها استفاده می‌کنند(هاوکینز و همکاران ،۲۰۰۲).
طبقه‌بندی بیزین بر اساس تئوری بیزین^[۱۲۷] است. این تئوری امکان محاسبه احتمال ثانویه را بر مبنای احتمالات اولیه طبق معادله ۳-۱ می‌دهد (رنی^[۱۲۸] و همکاران ، ۲۰۰۳).

P(H) احتمال اولیه‌ای^[۱۲۹] که فرضیه H قبل از مشاهده E داشته است .اگر چنین احتمالی موجود نباشد می‌توان به تمامی فرضیه‌ها احتمال یکسانی نسبت داد.
P(E) برابر با احتمال اولیه رخداد E
P(E|H) برابر با احتمال مشاهده‌ی رخداد E به فرض آنکه فرضیه H صادق باشد.
در این تکنیک، ویژگی‌ها مستقل از یکدیگرند بنابراین می‌توان احتمال مشاهده‌ی ترکیب عطفی را از ضرب احتمال هر ویژگی بدست آورد. کلاسی که بالاترین مقدار احتمال ثانویه را داشته باشد به عنوان کلاس پیش‌بینی شده برای آن داده‌ی آموزشی در نظر می‌گیریم. بزرگترین ویژگی این روش این است که حجم آموزش اندکی برای شروع کار و تخمین پارامترها نیاز دارد. سبیالا^[۱۳۰] و همکاران(۲۰۰۲)، در تشخیص نفوذ از این روش استفاده کرده اند .
تکنیک‌های تشخیص ناهنجاری مبتنی بر قوانین از طریق قوانین^[۱۳۱] یاد گرفته شده رفتارهای نرمال سیستم را شناسایی می‌کنند. داده‌هایی که به هیچ یک از این قوانین نگاشت نشوند به عنوان داده‌های ناهنجار تلقی می‌شوند. این تکنیک هم برای تک‌کلاسه و هم چندکلاسه مورد استفاده قرار می‌گیرد. تکنیک چندکلاسه‌ی مبتنی بر قوانین شامل دو مرحله است: مرحله‌ی اول شامل یادگیری قوانین از داده‌های آموزشی با بهره گرفتن از الگوریتم‌های یادگیری قوانین همانند RIPPER و درخت تصمیم گیری^[۱۳۲] است. هر قانون یک ضریب اطمینان دارد که برابر است با نسبت تعداد نمونه‌های آموزشی که به درستی طبقه‌بندی شده‌اند به تعداد کل نمونه‌های آموزش که با این قانون پوشش داده شده‌اند. مرحله‌ی دوم به ازای هر داده‌ی آموزشی بهترین قانون را نسبت می‌دهیم. عکس ضریب اطمینان برابر با درجه‌ی ناهنجاری برای آن داده‌ی تست می‌باشد(اسلاوادور^[۱۳۳] و چان^[۱۳۴] ،۲۰۰۳ ).

۳-۳- روش های مبتنی بر خوشه بندها

خوشه‌بندی یکی از روش های‌ دسته‌بندی داده‌ها بر اساس معیار شباهت است. خوشه‌بندی از جمله روش‌های بدون نظارت^[۱۳۵] می‌باشد. از برخی روش‌های خوشه‌بندی در تشخیص ناهنجاری استفاده می‌شود. روش‌های تشخیص ناهنجاری مبتنی بر خوشه‌بندی بر یکی از دو فرض زیر استوار می‌باشند.
فرض اول : نمونه‌های نرمال به مرکز جرم^[۱۳۶] نزدیک‌‌ترین خوشه خود نزدیک هستند و نمونه‌های ناهنجار به مرکز جرم نزدیک‌‌ترین خوشه‌ی خود دور هستند. معیار نزدیکی در این فرض می‌تواند فاصله اقلیدسی یا دیگر معیارها باشد. بنابراین این فرض شامل دو گام اصلی می‌باشد: در گام اول داده‌ها بر اساس الگوریتم خوشه‌بندی دسته‌بندی می‌شوند. در گام بعدی فاصله هر نمونه داده‌ای با مرکز جرم نزدیک‌‌ترین خوشه‌ی خود محاسبه می‌شود. از جمله الگوریتم‌های خوشه‌بندی می‌توان K-means را نام برد.
فرض دوم: نمونه‌های نرمال به خوشه‌های متراکم تعلق دارند و نمونه‌های ناهنجار به خوشه‌هایی با تراکم کم و پراکنده تعلق دارند.
مزایای خوشه بندی: از مزایای مهم استفاده از خوشه‌بندی در تشخیص ناهنجاری را می‌توان کارکرد این روش در مد بدون نظارت نام برد. همچنین این روش در فاز تست سریع می‌باشد چون فقط مستلزم مقایسه نمونه‌های تست با خوشه‌ها می‌باشد.
معایب روش خوشه‌بندی : کارایی این روش به کارایی الگوریتم خوشه‌بندی مورد استفاده بستگی دارد. همچنین بسیاری از نمونه‌های ناهنجار در چندین خوشه می‌توانند جای گیرند و باعث تولید آلارم اشتباه شوند. (چاندولا و همکاران ، ۲۰۰۹).