ترجمه کامل و روان مقاله الگوریتم تطبیق رشته شبیه و دقیق برای وب و امنیت شبکه

ترجمه کامل و روان مقاله الگوریتم تطبیق رشته شبیه و دقیق برای وب و امنیت شبکه

 به همراه اسلاید ارایه

الگوریتم تطبیق رشته شبیه و دقیق برای وب و امنیت شبکه

چکیده

الگوریتم های تطبیق رشته برای یکبار، یا بطور کلی، تماما از یک رشته جستجو در یک رشته ورودی که تکرار شده است مورد بررسی قرار می دهد. کارآمد ترین الگوریتم تطبیق رشته در برنامه های کاربردی معمول، الگوریتم بویر-مور (Boyer-Moore) شناخته شده است. هدف از این مقاله، به معرفی سریع الگوریتم تطبیق رشته برای تشخیص دقیق یا شبیه یک الگوریتم داده شده در رشته های ورودی است. این مبتنی بر محاسبه مجموع مقادیر کاراکترها در رشته جستجو و مقایسه این مجموع با حاصل جمع مقدار های کاراکترهای مربوطه در پنجره کشویی است. پنجره کشویی شامل تعدادی از کاراکترهای برابر با رشته جستجو است و شیفت راست،  از ابتدا و در انتهای رشته ورودی منتقل می شود. نتایج تجربی نشان میدهد که الگوریتم جدید در بدترین حالت، چندین برابر کارآمدتر از Boyer-Moore (BM) بنظر می رسد، و الگوی دیگر بیشتر عملکرد را بهبود می بخشد.

کلید واژه : تطابق رشته ; امنیت شبکه ; حمله کارآمد الگوریتمی

فهرست مطالب

عنوان                                                                                                        صفحه

فهرست شکل ها‌ب

1- مقدمه. 1

2- برخی از الگوریتم های مرتبط.. 1

3- الگوریتم پیشنهادی : تطبیق رشته دقیق و مشابه ( ELSM )4

4- تجزیه و تحلیل و آزمایش.... 6

5- نتیجه گیری و کار آینده. 7

مراجع و ارجاعات.. 7

عنوان                                                                                                        صفحه

شکل 1 : الگوریتم پیشنهادی جدید. 5

شکل 2 : مقایسه روش های جستجوی مختلف با طول الگوی متفاوت.. 6

1-  مقدمه

 تطبیق رشته یکی از موضوعات اساسی و مهم در تحقیقات علوم کامپیوتری است. تطبیق رشته عبارت است از پیدا کرد یک، یا بطور کلی، همه تکرار های یک رشته مورد جستجو، که همچنین الگو نیز نامیده می شود، در رشته ورودی است. اگر بیش از یک رشته جستجو بطور همزمان شبیه به رشته ورودی تطبیق داده شود آن را تطبیق الگوی چندگانه می نامند. در غیر اینصورت، آنرا تطبیق الگوری منفرد نامند (1-3). الگوریتم تطبیق الگوی منفرد بطور گسترده در محیط های امنیتی شبکه مورد استفاده قرار می گیرد. (در محدوده امنیت شبکه، الگو یک رشته نشان دهنده نفوذ شبکه، حمله، ویروس، هرزنامه و یا اطلاعات شبکه کثیف و ... می باشد). الگوریتم تطبیق الگوی منفرد همچنین اساسا برای ساخت الگوی مبتنی بر استثنی، الگوریتم تطبیق الگو و موتور تطبیق الگوی ترکیبی برای رسیدگی به مسائل بسیار زیاد الگوهای تشخیص امنیت شده است. الگوریتم تطبیق رشته مبتنی بر استثنی از فناوری هوشمند برای شناسایی الگوهایی که نمی تواند در رشته ورودی برای اولین بار رخ دهد بهره می برد، و سپس از الگوریتم تطبیق الگوی منفرد برای الگوی هایی که نمی تواند کنار گذاشته شود تطبیق می دهد. ExB (4) و E2xB (5) انواع الگوریتم مبتنی بر استثنی است. موتور تطبیق الگوی ترکیبی باعث الگوریتم های متفاوت، بطور کلی ترکیبی از الگوریتم های تطبیق الگوی منفرد و الگوی چندگانه، وابسته به محیط نرم افزار های مختلف از جمله تعداد الگوها و اندازه رشته ورودی است. با توجه به این حقیقت که هیچ الگوریتم منفردی در همه موارد بهترین عملکرد را ندارد، یک موتور تطبیق الگوی ترکیبی، بهترین روش در برنامه های کاربردی امنیت شبکه بنظر می رسد (6 و7 ). همراه با توسعه تکنیک های حمله شبکه، تجهیزات امنیتی شبکه خود را هدف حمله قرار می دهد. یعنی همان کاری که الگوریتم تطبیق رشته دارد. یک روش حمله موثر برای الگوریتم تطبیق رشته "حمله عملکرد الگوریتمی" است: یک مهاجم عمدا ورودی که بیش از حد بدترین مورد عملکردی را از یک الگوریتم دارم فراهم می آورد (6). این می تواند سرعت جستجو را کاهش و باعث دور ریختن بسته ها شود، که بر اساس آن مزاحم می تواند این حمله را آغاز کند.