هرزنامه که معمولا تبلیغاتی هستند، ویژگیهای مشابهی دارند. مثلا آنهایی که محصولی را تبلیغ میکنند از قیمت آن حرف میزنند و یا میگویند که فرصتتان چقدر استثنایی است. حتی رنگارنگ بودن بخشهای نوشته میتواند نشان از بیارزش بودن آن باشد. از آنجایی که این نشانههای قطعی نیستند و ما هم در ایمیلهایی که برای هم میفرستیم ممکن است مثلا از قیمت حرف بزنیم، نمیتوانیم با چند قانون ساده هرزنامهها را جدا کنیم. اینجور مواقع سعی میکنیم از روی مجموعه هرزنامههای موجود یاد بگیریم که هرزنامهها چه ویژگیهایی دارند.
حال اگر این هرزنامهها در قالب متنهای کوتاه پیامکی و یا شبکههای اجتماعی پیامرسان باشند، تشخیص آنها سختتر هم میشود.
۱. مقدمه
امروزه نامه رسانی الکترونیکی به عنوان هنجاری برای ارتباط کارا و پرسرعت معرفی شده است. کاربران پست الکترونیک در گلوگاه کارایی گرفتار شدهاند و در جنگی نابرابر به مقابله ی کسانی رفته اند که دیدگاه متفاوتی از نامهرسانی الکترونیکی دارند و آن را به صورت ارسال حجم بالای نامه با اهداف اقتصادی، مخرب و سودجویانه میبینند. این رایانامهها به اصطلاح هرزنامه (اسپم) نامیده شده اند.
نامه های الکترونیکی بیهوده که تحت نام هرزنامه نیز معروفند قسمتی از کار و زندگی کاربران اینترنت بخصوص پست الکترونیکی را به خود اختصاص داده است. با توجه به تغییرات اعمال شده در هرزنامه ها که از طرف ارسال کنندگان آنها جهت مخفیماندن از شناساییشدن توسط برنامه های ضد هرزنامه صورت میپذیرد، طراحی یک راه حل ضد هرزنامهای که بتواند بطور مناسب خود را با تغییرات اعمال شده روی هرزنامه ها وفق دهد، مشکل است.
در سالهای اخیر تحقیقات بسیاری برای رفع این مسئله انجام گرفته است ولی هنوز نامه های الکترونیکی ناخواسته یکی از مشکلات جدی کاربران است.
۲. کارهای مرتبط
برای تشخیص ایمل های عادی از هرزنامه ها روش های بسیاری ابداع شده اند که در زیر به اختصار برخی از آنها را توضیح میدهم
۲.۱. روش های رفتار محور
در این دسته از روش ها بر اساس رفتار های ارسال کننده یا در یافت کننده نامه، آنها در لیست هایی قرار میگیرند و بر اساس این لیست ها درباره نامه های آنها تصمیم گیری می شود.
۲.۱.۱. لیست سیاه (Black List)
فهرست سیاه یکی از اولین روشهای ضد هرزنامه است. در این روش از یک فهرست که در آن دامنه ها، IP ها و نشانی های فرستنده های هرزنامه قرار دارد در سرور های انتقال رایانامه نگهداری می شود. به اینترتیب هرگاه دامنه یا آدرس IP فرستنده یک هرزنامه در لیست سیاه قرار داشته باشد، آن نامه به عنوان هرزنامه تلقی میشود. البته این روش کارایی بالایی ندارد، زیرا هرزنامه نویس ها از یک آدرس یا دامنه ثابت استفاده نمیکنند. [1]
از معایب این روش بالابودن نرخ منفی کاذب است.
۲.۱.۲. لیست سفید (White List)
این روش دقیقا برعکس روش قبل است، در این روش فهرستی از دامنه ها، IP ها و نشانی های فرستنده های نامه های پاک تهیه شده و هر نامه ای که از طرف آنها نباشد به عنوان هرزنامه تلقی میشود.
از معایب این روش بالابودن نرخ مثبت کاذب است. همچنین اگر هرزنامه نویس به اطلاعات فهرست سفید دسترسی پیدا کند،آن وقت این روش کاملاً ناکارا خواهد بود.[2]
۲.۱.۳. لیست خاکستری (Gray List)
ارسال کنندگان هرزنامه تلاش می کنند تا کمترین هزینه را برای ارسال هر نامه صرف کنند همچنین ارسال شدن همه نامه ها برایشان مهم نیست، از این رو اگر در ارسال نامه خطایی رخ بدهد، بجای این که آن را در صف ارسال مجدد قرار بدهند و پس از مدتی برای این کار تلاش کنند، از خطا صرف نظر کرده و نامه هایی که ارسال نشده اند را دور می اندازند
به این ترتیب اگر سرور دریافت کننده نامه به فرستنده اعلام کند که در حال حاظر امکان دریافت نامه را ندارد و سرور فرستنده باید بعدا مجددا تلاش کند ولی سرور فرستنده این کار را انجام ندهد، این احتمال وجود دارد که نامه از طرف یک هرزنامه نویس بوده است.
لذا این فهرست حاوی فرستندگانی است که پس از اعلام خطا، اقدام مجدد به منظور فرستادن آن انجام نداده اند و نامه هایی که برای ارسال مجدد آنها تلاش نشده است به عنوان هرزنامه تلقی میشوند[2].
از معایت این روش آن است که هر نامه پاک دوبار ارسال میشود و همچنین هرزنامه نویس ها میتوانند از اعمال سیاست عدم ارسال مجدد دست بردارند.
۲.۲. روش های هوشمند
در این روش ها از الگوریتم های هوش مصنوعی برای تشخصی هرزنامه بودن یک نامه استفاده میشود
۲.۲.۱. مبتنی بر قضیه Bayes
برای درک بهتر این روش باید مروری بر قضیه بیز در احتمالات داشت
این قضیه رابطه ای برای محاسبه احتمال وقوع A به شرط B از روی احتمال های وقوع A، B و B به شرط A بیان میکند
حال در مسئله تشخیص هرزنامه
اگر A را احتمال هرزنامه بودن یک ایمیل و B را محتوای ایمیل تعریف کنیم میتوانیم هرزنامه ها را بصورت زیر مشخص کرد:
حال با استفاده از قضیه بیز میتوان آن را بصورت زیر نوشت:
که به این معنی است که :
اگر احتمال این که این محتوا در یک هرزنامه وجود داشته باشد و این نامه هرزنامه باشد از احتمال این که این محتوا در یک نامه پاک وجود داشته باشد و این نامه پاک باشد بیشتر بشود، این نامه هرزنامه است.[3]
۲.۲.۲. براساس شبکه عصبی
شبکه های عصبی در کل مجموعه ای از چندین “تابع ساده ریاضی” هستند که در نهایت تابعی پیچیده را تشکیل می دهند. خروجی هر کدام از این توابع می تواند ورودی تابعی دیگر باشد. در نهایت با استفاده از خروجی ها باید بتوان دسته بندی نمونه را مشخص نمود.
خود شبکه های عصبی به دو دسته تقسیم می شوند. روشی که بیشتر در تشخیص هرزنامه به کار می رود روش Perceptron است.
در این روش هر تابع ساده ما به شکل یک ترکیب خطی از ورودی هاست. خروجی عددی حقیقی است. قرار داد می شود که خروجی مثبت به معنی عادی بودن ایمیل و اعداد منفی بیانگر اسپم بودن آن می باشند. ضرایب این ترکیب خطی در ابتدا مقادیری دلخواه تعیین می شوند. حال باید یکی از نمونه هایی به تابع داده شود که حدس تابع در مورد هزنامه بودن یا نبودن آن اشتباه است. در این صورت تمام ضرایب ترکیب خطی یاد شده بر پایه این ورودی و با استفاده از رابطه ای مشخص اصلاح می گردند. این عمل چندین بار تکرار می شود. وضعیتی حاصل شد که تمام نمونه ها درست دسته بندی شده بودند، کار متوقف می گردد.[4]
در صورتی که رابطه بین ورودی های مسئله خطی نباشد، ضرایب واگرا خواهند شد و الگوریتم به نتیجه نمی رسد.شبکه های عصبی نیاز به زمان و نمونه های زیاد برای تکمیل فرآیند یادگیری دارند. همچنین لزومی ندارد که رابطه بین ورودی ها واقعا خطی باشد و ممکن است روش کلا به نتیجه نرسد. در عوض پیاده سازی آن ها کار مشکلی نیست و نتیجه ی حاصله در صورت وجود عموما خوب و مطلوب است.
۲.۲.۳. بر اساس SVM
ماشین بردار پشتیبانی (Support Vector Machine) خود نوعی از شبکه های عصبی است.
در این روش تابعی خطی پیدا می شود که با گرفتن ورودی ها، هرزنامه بودن را مشخص کند. تفاوت اینجاست که در این روش تابع خطی را به یک معادله تبدیل شده و با استفاده از آن تلاش می شود “خط مرز” بین نمونه های عادی و اسپم یافت شود. در این صورت برای تشخیص وضعیت هر ایمیل جدید، کافیست بررسی شود که این ایمیل کدام طرف خط مذکور است (با توجه به n بعدی بودن فضا، خط یاد شده در اصل خود یک فضای n-1 بعدی با معادله ی مشخصه ی خاص خود است).[5]
پیاده سازی این روش اندکی مشکل است اما حاصل عموما بهتر از روش بالا می باشد.
۲.۲.۴. با استفاده از الگوریتم K-NN
الگوریتم K Nearest Neighbor یا به اختصار KNN یک گروه شامل K رکورد از مجموعه رکوردهای آموزشی که نزدیکترین رکوردها به رکورد آزمایشی باشند را انتخاب کرده و بر اساس برتری رده یا برچسب مربوط به آنها در مورد دسته رکورد آزمایشی مزبور تصمیمگیری مینماید. به عبارت سادهتر این روش ردهای را انتخاب میکند که در همسایگی انتخاب شده بیشترین تعداد رکورد منتسب به آن دسته باشند. بنابراین ردهای که از همه ردهها بیشتر در بین K نزدیکترین همسایه مشاهده شود، به عنوان رده رکورد جدید در نظر گرفته میشود.[6]
۳. آزمایشها
۳.۱. مجموعه داده (Data Set)
در این پروژه از مجموعه داده هرزنامه پیامکی که توسط دانشگاه کالیفرنیا در ارواین ارائه شده استفاده شد.
این دیتاست شامل ۵۵۷۴ پیام است که کوتاه ترین آنها ۲ کاراکتر و طولانی ترینشان ۹۱۰ کاراکتر طول دارد. پراکندگی طول پیام ها در تصویر زیر مشخص است:
همچنین در این دیتاست ۴۸۷۲ نامه پاک وجود دارد که شامل ۴۵۱۸ پیام متحصر به فرد است و طولانی ترین آنها ۹۱۰ و کوتاه ترین آنها ۲ کاراکتر طول دارند.
از میان ۷۴۷ هرزنامه، ۶۵۳ پیام یکتا وجود دارد و بیشترین طول آنها ۲۲۳ و کمترین آنها ۱۳ کاراکتر است، پراکندگی طول پیام ها برحسب نوع نامه در تصویر زیر قابل مشاهده است:
۳.۲. پیادهسازی
کد پیادهسازی در GitHub قابل مشاهده است.
در این مرحله، با کمک کتابخانه scikit learn مدل های تشخیص هرزنامه را توسط سه الگوریتم Naive Bayes و SVM و KNN پیاده کردم
فرایند کلی آموزش دادن الگوریتم ها به این صورت است:
ابتدا مجموعه داده را به ۲ بخش با نسبت ۱ به ۴ تقسیم میشود، از بخش بزرگ تر برای یاد دادن به ماشین و از بخش کوچک تر برای تست کردن آن استفاده میشود.
سپس باید داده ها را برای کامپیوتر قابل فهم کرد، به این منظور با استفاده از الگوریتم TF-IDF هر جمله را به برداری از اعداد تبدیل می کنیم
۳.۲.۱. مدل BOW
نام این مدل خلاصه عبارت Bag Of Word است و یک روش ساده سازی نمایش اطلاعات متن است و هدف آن تبدیل متن به یک آرایه (وکتور) از اعداد است.
در این روش تعداد تکرار هر موجودیت در متن به جای خود آن موجودیت در آرایه ذخیره میشود. موجودیت های ما میتوانند کلمات، عبارات یا حتی کاراکتر ها و ... باشند.[7]
۳.۲.۲. الگوریتم TF-IDF
نام این الگوریتم که خلاصه عبارت Term Frequency–Inverse Document Frequency است
در این شیوه به لغات یک وزن بر اساس فراوانی آن در متن داده میشود. در واقع این سیستم وزن دهی نشان میدهد چقدر یک کلمه برای یک متن مهم است. وزن کلمه با افزایش تعداد تکرار آن در متن افزایش مییابد، اما توسط تعداد کلمات در متن کنترل میشود، چرا که میدانیم در صورت زیاد بودن طول متن، بعضی از کلمات (مثلا حروف اضافه یا ضمیر ها) به طول طبیعی بیشتر از دیگران تکرار خواهند شد، اگرچه چندان اهمیتی در معنی ندارند.
به منظور استفاده از این الگوریتم ما مراحل زیر را انحام میدهیم:[8]
تعداد تکرار هر کلمه را در هر پیام می شماریم. (TF) که این مورد در مسئله ما با روش BOW انجام می شود.
عدد بدست آمده را بر تعداد کل تکرار های آن کلمه در دیتاست تقسیم می کنیم. (IDF)
سپس با استفاده از Grid Search Cross Validation
که در کتابخانه scikit learn وجود دارد بهترین گزینش پارامتر های الگوریتم پیدا میشوند
۳.۲.۳. خروجی اولیه الگوریتم ها
قبل از بیان خروجی های ابتدا چند تعریف را ارائه می کنم:[9]
Precision : دقت سیستم در میان دادهای پیش بینی شده
Recall : نسبت تعداد داده های پیش بینی شده، به تعداد کل داده های مورد انتظار برای پیش بینی
f1-score : [10]
F1=2 \times \frac { precision \times recall }{ precision + recall }
Naive Bayes
پس از اجرا این الگوریتم خروجی های زیر بدست آمد:
precision | recall | f1-score | support | |
---|---|---|---|---|
ham | 0.97 | 1.00 | 0.98 | 4827 |
spam | 1.00 | 0.77 | 0.87 | 747 |
avg / total | 0.97 | 0.97 | 0.97 | 5574 |
همان طور که در تصویر زیر قابل مشاهده است الگوریتم ۲۳٪ (۱۷۰ نامه) از مواردی که هرزنامه بوده اند را به عنوان نامه پاک شناسایی کرده همچنین هیچ از نامه های پاک را به عنوان هرزنامه تشخیص نداده است.
Support Vector Machine
پس از اجرا این الگوریتم خروجی های زیر بدست آمد:
precision | recall | f1-score | support | |
---|---|---|---|---|
ham | 0.87 | 1.00 | 0.93 | 4827 |
spam | 0.00 | 0.00 | 0.00 | 747 |
avg / total | 0.75 | 0.87 | 0.80 | 5574 |
همان طور که مشاهده می کنید، این اگوریتم بدون بهینه سازی قادر به تشخیص هرزنامه ها نیست
K Nearest Neighbor
پس از اجرا این الگوریتم خروجی های زیر بدست آمد:
precision | recall | f1-score | support | |
---|---|---|---|---|
ham | 0.87 | 1.00 | 0.93 | 4827 |
spam | 0.00 | 0.00 | 0.00 | 747 |
avg / total | 0.75 | 0.87 | 0.80 | 5574 |
همان طور که مشاهده می کنید، این اگوریتم بدون بهینه سازی قادر به تشخیص هرزنامه ها نیست
۳.۲.۴. خروجی الگوریتم های بهبود یافته
Naive Bayes
با تعیین پارامتر های زیر برای Grid Search، خروجی الگوریتم بهبود یافته و نتایج تغییر کرد:
params = {
'tfidf__use_idf': (True, False),
'bow__analyzer': (splitToLemmas_NoStopWord, splitToLemmas, splitToTokens, 'word')
}
precision | recall | f1-score | support | |
---|---|---|---|---|
ham | 0.97 | 1.00 | 0.99 | 4827 |
spam | 1.00 | 0.81 | 0.89 | 747 |
avg / total | 0.98 | 0.97 | 0.97 | 5574 |
همان طور که مشاهده میکنید، پس از بهینه سازی این الگوریتم،۴٪ از False Positive های این الگوریتم کاهش پیدا کرد و تعداد آخطا ها به ۱۴۲ نامه رسید
Support Vector Machine
با تعیین پارامتر های زیر برای Grid Search، خروجی الگوریتم بهبود یافت:
params = {
'tfidf__use_idf': (True, False),
'bow__analyzer': (splitToLemmas_NoStopWord, splitToLemmas, splitToTokens, 'word', 'char'),
'classifier__n_neighbors': numpy.arange(start=1, stop=100),
'classifier__weights': ['uniform', 'distance']
}
با اعمال این پارمتر ها سخت گیری الگوریتم بشدت زیاد شد و منجر به ایجاد ۲ مورد False Negative شد ولی تنها در تشخیص ۱۰مورد از هرزنامه ها شکست خورد:
precision | recall | f1-score | support | |
---|---|---|---|---|
ham | 1.00 | 1.00 | 1.00 | 4827 |
spam | 1.00 | 0.99 | 0.99 | 747 |
avg / total | 1.00 | 1.00 | 1.00 | 5574 |
K Nearest Neighbor
با تعیین پارامتر های زیر برای Grid Search، خروجی الگوریتم بهبود یافت:
params = {
'tfidf__use_idf': (True, False),
'bow__analyzer': (splitToLemmas_NoStopWord, splitToLemmas, splitToTokens, 'word', 'char'),
'classifier__n_neighbors': numpy.arange(start=1, stop=100),
'classifier__weights': ['uniform', 'distance']
}
با اعمال این پارامتر ها دقت الگوریتم بطور چشم گیری افزایش پیدا می کند، شایان ذکر است ای با این پارامتر ها ۷ مورد False Negative و ۲۶ مورد False Positive ایجاد شده است
precision | recall | f1-score | support | |
---|---|---|---|---|
ham | 0.99 | 1.00 | 1.00 | 4827 |
spam | 0.99 | 0.97 | 0.98 | 747 |
avg / total | 0.99 | 0.99 | 0.99 | 5574 |
۳.۳. تحلیل اولیه
در خروجی این الگوریتم ها نکته قابل توجهی وجود دارد، با این که الگوریتم های SVM و KNN درصد خطا نسبتا پایینی دارند، اما هر ۳ الگوریتم در تشخیص جملات زیر دچار خطا شدند:
برچسب درست | متن پیام |
---|---|
spam | Monthly password for wap. mobsi.com is 391784. Use your wap phone not PC |
spam | Guess who am I?This is the first time I created a web page WWW.ASJESUS.COM read all I wrote. I'm waiting for your opinions. I want to be your friend 1/1 |
spam | Hello darling how are you today? I would love to have a chat, why dont you tel... |
۳.۴. بهبود نتایج
برای حل مشکل با تغییر پارامتر های الگوریتم ها، به نتیجه جالبی دست پیدا کردم.
اگر آنالازیر char را از فهرست آنالیزر های bow الگوریتم KNN حذف کنم دقت آن کمی کاهش پیدا میکند ولی وقتی در کنار الگوریتم های دیگر قرار بگیرد منجر به کاهش خطا کل سیستم میشود.
در این حالت تنها ۱ عبارت توسط هیچ الگوریتمی به درستی برچسب نخورد:
برچسب درست | متن پیام |
---|---|
spam | Hi its LUCY Hubby at meetins all day Fri & I will B alone at hotel U fancy cumin over? Pls leave msg 2day 09099726395 Lucy x Calls£1/minMobsmoreLKPOBOX177HP51FL |
K Nearest Neighbor
با حدف آنالازیر char پارامتر های آن به صورت زیر ٔر آمد:
params = {
'tfidf__use_idf': (True, False),
'bow__analyzer': (splitToLemmas_NoStopWord, splitToLemmas, splitToTokens, 'word'),
'classifier__n_neighbors': numpy.arange(start=1, stop=100),
'classifier__weights': ['uniform', 'distance']
}
با اعمال این پارامتر ها ۱ مورد False Negative و ۳۱ مورد False Positive وجود دارد
precision | recall | f1-score | support | |
---|---|---|---|---|
ham | 0.99 | 1.00 | 1.00 | 4827 |
spam | 1.00 | 0.96 | 0.98 | 747 |
avg / total | 0.99 | 0.99 | 0.99 | 5574 |
۴. کارهای آینده
الگوریتم های بسیاری مانند شبکه عصبی و ... جود دارند که میتوان از آنها برای تشخیص هرزنامه استفاده کرد.
همچنین پارمتر های الگوریتم های استفاده شده در این مقاله بسیار متنوع تر از آنچه بررسی شدهاند است و میتوان روی بررسی و انتخاب دقیق آن ها تمرکز کرد.
همچنین میتوان روی بهبود توابع مورد استفاده در مدل BOW کار کرد و یا از مدل های دیگری استفاده کرد
۵. مراجع
[1] Oro, David, et al. "Benchmarking IP blacklists for financial botnet detection." Information Assurance and Security (IAS), 2010 Sixth International Conference on. IEEE, 2010.
[2] Chiou, Pin-Ren, Po-Ching Lin, and Chun-Ta Li. "Blocking spam sessions with greylisting and block listing based on client behavior." Advanced Communication Technology (ICACT), 2013 15th International Conference on. IEEE, 2013
[3] Sahami, Mehran, et al. "A Bayesian approach to filtering junk e-mail." Learning for Text Categorization: Papers from the 1998 workshop. Vol. 62. 1998.
[4] Kufandirimbwa, Owen, and Richard Gotora. "Spam Detection using Artificial Neural Networks (Perceptron Learning Rule)." Online Journal of Physical and Environmental Science Research 1.2 (2012): 22-29.
[8] TF-IDF
[10] F1-score
[7] Metsis, Vangelis, Ion Androutsopoulos, and Georgios Paliouras. "Spam filtering with naive bayes-which naive bayes?." CEAS. Vol. 17. 2006.
۶. پیوندهای مفید
کد پیادهسازی در GitHub