استفاده از الگوریتم ژنتیک جهت تشخیص نفوذ

به منظور استفاده بهار از الگوریتم ژنتیک در تشخیص نفوذ از الگوریتم ژنتیک برای تولید قوانینcalssificationیا برای انتخاب ویژگی های مناسب کروموزوم ها استفاده میشود.الگوریتم ژنتیک به دلیل قدرت و سادگی عملیات و انتخاب بهترین نتیجه یکی از کارآمد ترین روش ها جهت تشخیص نفوذ است.

تشخیص نفوذ در اصل یک مسئله classificationاست بنابراین اولین قدم انتخاب و استخراج ویژگی است.هنگامی که تعداد ویژگی ها از یک مرز مشخص بگذرد در عملکرد طبقه بندی تغییر ایجاد خواهد شد.اصطلاحا feature selection یا انتخاب ویژگی،از بین ویژگی های موجود خروجی را بر اساس یک تابع ارزیابی مشخص انتخاب میکندتا زمانی که فضای ویژگی ها کاهش یابد و در دقت classification نیز اخلالی ایجاد نشود ادامه می یابد.

برای داده های بزرگ،انتخاب ویژگی زمان تشخیص و هزینه را کاهش می دهدو کارایی دسته بندی را افزایش می دهدو در نهایت به کشف مجموعه حاوی اطلاعات مفید می انجامد.

از الگوریتم ژنتیک جهت استنتاج قوانین مفیدتر و جدیدتر برای تشخیص نفوذ استفاده می شود.با استفاده از این قوانین داده های نرمال از داده های غیر نرمال تشخیص داده میشوند.

به طور کلی قانون در الگوریتم ژنتیک به صورت آرایه رو به رو میباشد :   if{condition} then {act}

که همانطور که مشخص است conditionداده مورد بررسی است و act عکس العملی است که باید در مورد آن انجام شود،condition می تواند برای موارد گوناگونی بررسی شود مثلا پورت ،مدت زمان اتصال ،IP ،پروتکل.act نیز میتواند عکس العمل های گوناگون نظیر پیغام دادن و یا حتی بلاک کردن باشد.

تابع برازندگی  fitness :

چنانچه قانون به صورت if A and B نمایش داده شود ،تابع برازندگی معادل زیر می باشد:

support = | A and B | / N 

                    |  confidence = | A and B | / | A

fitness = w1 * support + w2 * confidence

که N تعداد کل اتصالات شبکه در داده است، | A| تعداد اتصالات شبکه منطبق با شرط A و | A and B |تعداد اتصالات شبکه که با قانون A then Bمطابقت می کند.وزن های w1 وw2 نیز برای کنترل توازن بین دو عبارت استفاده می شود.

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

research.iaun.ac.ir/pd/rastegari/pdfs/PaperC_7221                                                                                                                                                                                                                                   

تشخیص نفوذ IDS

با توجه به گسترده تر شدن شبکه های کامپیوتری ،خطرات مختلفی کاربران را تهدید میکند.از جمله این خطرات می توان به ویروس ها و نفوذ ها اشاره کرد که البته ویروس ها را میتوان به صورت گسترده با استفاده از آنتی ویروس و به روز رسانی آن کنترل کرد.

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

یک سیستم تشخصی نفوذ بدین گونه کار میکند که که ابتدا اطلاعاتی در مورد سیستم مورد نظر جمع آوری میکند .داده های جمع آوری شده توسط یک detectorپردازش میشوند.detectorاطلاعات غیر لازم را داده های جمع آوری شده جدا میکند و سپس تصمیم گیری میکند که آیا این فعالیت ها می توانند به عنوان نفوذ در نظر گرفته شوند یا خیر.

سیستم های تشخیص نفوذ سنتی محدود هستند و برای یافتن فعالیت های غیر مجاز ،روی شبکه جستجو می کنند و در بعضی موارد قادر هستند تا حملات امنیتی را تشخیص دهند ، اما در بسیاری  از موارد نیز شکست می خورند یا حتی ممکن است بدون اینکه نفوذی وجود داشته باشد هشدار دهند ،علاوه بر اینکه نیاز به یک کاربر انسانی دارند تا پردازش به صورت جامع انجام شود.

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

research.iaun.ac.ir/pd/rastegari/pdfs/PaperC_7221           

استفاده از الگوریتم ژنتیک در شبکه های واقعی Word association network

شبکه‌ی هم‌نشینی لغات:  

شبکه‌ی هم‌نشینی لغات از لیست هنجار انجمن آزاد فلوریدای جنوبی برگرفته شده است. (http://www.usf.edu/IreeAssociation). در لیست هنجار انجمن آزاد فلوراید جنوبی، سنگینی یک لینک هدایت شده از یک کلمه به کلمه دیگر نشان دهنده تعداد دفعات تکراری است که مردم در این تحقیق نقطه‌ی نهایی لینک را با نقطه‌ی آغازین پیوند می‌دهند. شبکه‌ی هم‌نشینی لغات بازی با یک لغت هدایت نشده جابجا شده است و در [36، 34]  آزمایش شده است.

این شبکه 53 گره نشان دهنده‌ی لغات مخلف و 197 کناره‌ی هم‌نشین دارد. با استفاده از الگوریتم ژنتیک با پارامترهای k=3 ، U=40 ، P=0/2 ، θ=0/2 ، α=0/1، β=0/2، T=1000 ما می‌توانیم این شبکه را به سه اجتماع مشترک با ارزش تناسب (تابع عینی) 3396/0 تفکیک کنیم. نتیجه در شکل زیر توصیف شده است. از نتایج تفکیک می‌توانیم ببینیم که لغات با همراهی متداول در اجتماعات یکسان قرار دارند. در این شبکه، لغت بازی به طور قوی به همراه اکثر لغات آمده است. بنابراین یک گره مشترک است. همچنین این نتیجه توسط روش نظری گراف برای تشخیص اجتماع گره به دست آمده است.

                                               

Discovering Link Communities in Complex Networks by an Integer Programming Model and a Genetic Algorithm

2013

Zhenping LiXiang-Sun ZhangRui-Sheng WangHongwei LiuShihua Zhang

                        http://dx.doi.org/10.1371/journal.pone.0083739

استفاده از الگوریتم ژنتیک در شبکه های واقعی The karate club network

شبکه‌ی باشگاه کاراته:

در این پست و پست های بعدی سعی داریم کاربرد الگوریتم ژنتیک را در شبکه های دنیای واقعی بررسی کنیم.

اولین مثالی که در نظر می‌گیریم یک شبکه‌ی باشگاه معروف کاراته است که توسط Zachary تجزیه و تحلیل شده است. همچنین توسط بسیاری از مطالعات تشخیص اجتماع مورد تحلیل قرار گرفته است. این شبکه از 34 عضو باشگاه کاراته به عنوان گره‌ها و 78 کناره بیان کننده‌ی دوستی بین اعضای باشگاه که در طی دو سال مشاهده شد، تشکیل شده است.

ما روش‌مان را برای شبکه‌ی باشگاه کاراته با استفاده از پارامترهای k=3، N=600 ، P=0/2، θ=0/2 ، α=0/6، β=0/2، T=1000 به کار می‌بریم.

نتیجه در شکل زیر به تصویر کشیده شده است. چگالی متوسط لینک 3349/0 است. رنگ لینک‌ها نشان می‌دهد که اجتماعات لینک با استفاده از الگوریتم ژنتیک ما کشف می‌شوند و رنگ گره‌ها نشان‌دهنده‌ی اجتماعات گره است که از اجتماعات لینک استنباط شده‌اند. در این شبکه‌ی باشگاه کاراته، اجتماعات لینک‌ها نشان می‌دهند که گره 1 متعلق به سه اجتماع است و گره‌های 2 و 3 به دو اجتماع تعلق دارند. بخش مشترک یک دسته‌ی 3 تایی است که توسط روش‌های قبلی تشخیص داده نشده بود.

                                                     

Discovering Link Communities in Complex Networks by an Integer Programming Model and a Genetic Algorithm

2013

Zhenping LiXiang-Sun ZhangRui-Sheng WangHongwei LiuShihua Zhang

                        http://dx.doi.org/10.1371/journal.pone.0083739

متدهای به کار گیری الگوریتم ژنتیک در پیشبینی لینک(قسمت چهارم)

در شکل زیر با استفاده از مدل ما، به درستی به سه اجتماع بخش‌بندی شود و مقدار تابع عینی 1 است.

                                          

زمانیکه d_j,c=1 باشد، لینک e_j به اجتماع P_c تخصیص داده می‌شود در غیر این صورت، لینک e_j به اجتماع P_c تخصیص نمی‌یابد. ماتریکس D می‌تواند از ماتریکس B بر طبق معادله‌ی زیر محاسبه شود:

                                                  

شبکه با استفاده از ماتریکس وقوع R، ماتریکس مجاورت لینک A و ماتریکس مجاورت لینک سنگین Q نشان داده می‌شود. ماتریکس مجاورت لینک A می‌تواند توسط معادله‌ی A=R^TR محاسبه شود. در A، عناصر قطری 2 هستند و عناصر غیرقطری مقادیری را در {1، 0} به خود می‌گیرند تا نشان دهند که آیا دو لینک یک گره مشترک دارند یا نه. فرض کنیم که Z یک ماتریکس قطر می‌باشد که عناصر قطری آن معکوس درجه‌های گره هستند یک درجه‌ی گره تعداد لینک‌های متلاقی با آن است به عبارت دیگر:

                                        

ماتریکس مجاورت لینک سنگین به عنوان Q=R^TZR تعریف می‌شود که به معنای احتمال رفتن یک عابر تصادفی از یک لینک به یکی از لینک‌های مجاورش از طریق گره مشترک‌شان می‌باشد. این احتمال می‌تواند به عنوان احتمال تعلق دو لینک مجاور به اجتماع یکسان در نظر گرفته شود.

توابع اصلی GA (الگوریتم ژنتیک)

ورودی: تعداد گره‌های N و تعداد لینک‌های M از شبکه و حداکثر تعداد اجتماعات K را وارد کنید. ماتریکس رویداد R، ماتریکس مجاورت لینک A=R^TR و ماتریکس مجاورت سنگین Q=R^TZR را

محاسبه کنید. تعداد اشخاص U، دوره ماکسیسم T، احتمال تغییر P و پارامترهای SOM (آغاز پیام) یعنی α , β , θ را شرح دهید.

خروجی. ماتریکس بخش‌بندی لینک D* و مقدار تناسب آن H* (یعنی مقدار تراکم بخش‌بندی لینک) و ماتریکس بخش‌بندی گره F را خروجی می‌دهد. بر طبق D* و F شبکه را به اجتماعات بخش‌بندی کنید.

ارزش آغازی: t=0 به طور تصادفی یک جمعیت اولیه B_u(t), …, B₂(t), B₁(t) ایجاد کنید و مقادیر اولیه D* و T* را شرح دهید.

مرحله 1. تناسب جمعیت: برای تمام افراد در جمعیت B_u(t), …, B₂(t), B₁(t) ماتریکس‌های D_u(t), …, D₂(t), D₁(t) و مقادیر متناسب آن‌ها H_u(t), …, H₂(t), H₁(t) را محاسبه کنید.

مرحله 2: دسته‌بندی جمعیت B₁(t) ,B₂(t) , … , B_u(t) را بر طبق مقادیر تناسب‌شان به صورت نزولی دسته‌بندی کنید. فرض کنید که کروموزم‌های دسته‌بندی شده، B₁(t) ,B₂(t) , … , B_u(t) هستند که در آن H₁(t) ≥ H₂(t) ≥ … ≥ H_u(t) می‌باشد.

اگر H₁(t)>H* باشد، D*=D₁(t) و H*=H₁(t) خواهد بود.

اگر t=T باشد، متوقف شوید. D* و H* را خروجی کنید و ماتریکس F متناظر با آن را برای بخش‌بندی گره محاسبه کنید. در غیر این صورت به مرحله 3 بروید.

مرحله‌ی 3. تعویض جمعیت: برای 

فرض کنید که  باشد و برای ایجاد دو شخص موقت (ماتریکس‌های) w_i(t) و  آن‌ها را تعویض کنید. اگر U یک عدد فرد باشد، اینگونه فرض کنید که w_u(t)=B_u(t)

مرحله‌ی 4: تغییر جمعیت: به طور تصادفی اشخاص موقت P^U را انتخاب کنید و عملیات تغییر را بر روی هر شخص موقت انجام دهید.

مرحله 5: SOM (آغاز پیام) جمعیت: برای هر شخص موقت، عملیات آغاز پیام را انجام دهید.

مرحله 6: هنجارسازی جمعیت: هنجارسازی را برای هر شخص موقت انجام دهید. اشخاص هنجارشده را با استفاده از B₁(t+1) ,B₂(t+1) , … , B_u(t+1) مشخص کنید. t=t+1 در نظر بگیرید و به مرحله‌ی 1 بروید.

ماتریکس بخش‌بندی و ارزیابی تناسب برای هر شخص Bi، ماتریکس بخش‌بندی Di را طبق فرمول 14 محاسبه کنید. برای هر اجتماع Ps، 1≤S≤K فرض کنید که Di(:,S)، ستون Sام از ماتریکس Di 

باشد. سپس Ei(s)=R.Di(:,S) یک بردار ستونی است که عوامل آن اعداد صحیح غیرمنفی هستند. یک عامل غیرصفر در Ei(s) نشان می‌دهد که گره متناظر به ei(j,s)≥1 تعلق دارد. Fi(j,s)=1 به این معناست که گره Vj به اجتماع Ps تعلق دارد. تناسب مشخص Bi می‌تواند توسط معادله‌ی زیر محاسبه شود.

                                                                            

از آنجا که اغلب یک مقدار حداکثر در هر ردیف ماتریکس B وجود دارد، ما اغلب با استفاده از فرمول (14)، یک لینک را به یک و فقط یک اجتماع بخش‌بندی کنیم. زمانی که یک لینک، لینک مشترک بین دو اجتماع باشد، نمی‌تواند توسط فرمول 14 به طور مستقیم تشخیص داده شود.

برای تشخیص دو لینک مشترک به طور صحیح، ما می‌توانیم فرمول 14 را با استفاده از فرمول زیر یعنی فرمول 15 جایگزین کنیم.

                                                                            

با استفاده از فرمول 15، یک لینک مشترک می‌تواند به بیش از یک اجتماع بخش‌بندی شود. دسته‌بندی جمعیت B₁(t) ,B₂(t) , … , B_u(t) را طبق مقادیر تناسب‌شان به صورت نزولی دسته‌بندی کنید. فرض کنید که کروموزوم‌های دسته‌بندی شده B₁(t) ,B₂(t) , … , B_u(t) هستند که H₁(t) ≥ H₂(t) ≥ … ≥ H_u(t) است. اگر H₁(t)>H* باشد، D*=D₁(t) و H*=H₁(t) است.

تعویض جمعیت: برای  عملیات تعویض با استفاده از قوانین زیر بر روی s  انجام دهید. به طور تصادفی ستون s را انتخاب کنید ستون sام از   را با استفاده از ستون sام B_i(t) اصلاح کنید و دو فرد موقت w_i(t) و  را به دست آورید. فرض کنید که w_i(t)=