فیلتر بولوم
فیلتر بولوم در سال ۱۹۷۰ به وسیله بورتون هاوارد بولوم ارائه شد. این فیلتر یک داده ساختار احتمالاتی بسیار کارآمد از نظر فضای ذخیره‌سازی است. از این فیلتر می‌توان برای آزمودن عضویت یک عنصر در مجموعه استفاده کرد.
فرض کنید می‌خواهیم وجود یک عنصری را در مجموعه جستجو کنیم، اگر داده ساختار به شما جواب داد که این عضو در مجموعه وجود دارد احتمال دارد که وجود نداشته باشد. اما اگر بگوید وجود ندارد، قطعاً درست هست. بر این اساس خطای مثبت داریم ولی خطای منفی امکان‌پذیر نمی‌باشد.
این داده ساختار امکان درج عنصر را به ما می‌دهد ولی امکان حذف آن وجود ندارد. هرچه بیشتر عنصر به آن اضافه شود احتمال خطای مثبت بیشتر می‌شود. یعنی احتمال اینکه داده ساختار به شما بگوید عضوی در مجموعه وجود دارد اما در واقع وجود نداشته باشد بیشتر می‌شود.
پیچیدگی زمانی فیلتر بلوم (k)O (در عملیات درج عنصر، جستجوی عنصر) است که K به معنی تعداد تابع درهم ساز می‌باشد.
توصیف الگوریتم ویرایش
یک فیلتر بولوم خالی متشکل از یک آرایهٔ m بیتی می‌باشد که تمامی عناصر آن صفر است.
همچنین به تعداد K تابع درهم سازی در اختیار هست؛ که هرکدام از آنها یک عدد را به یکی از خانه‌های آرایه فیلتر بولوم نظیر می‌کند.
نکته: می‌توان برای هر تابع درهم ساز، یک آرایه m بیتی در نظر گرفت.
مثال یک آرایه و K تابع درهم ساز: عنصر اندیس خروجی هرکدام از توابع درهم ساز در هر یک از مقادیر وارد شده در تنها آرایه موجود، یک می‌شوند.
مثال برابری تعداد آرایه خالی و توابع درهم ساز: اگر به ازای K تابع درهم ساز، همان تعداد آرایه داشته باشیم، عنصر اندیس خروجی هرکدام از توابع درهم ساز در آرایه متناضر با تابع درهم ساز، یک می‌شوند.
درج عنصر ویرایش
برای این کار ابتدا عدد مورد نظر را به K تابع درهم سازی می‌دهیم. بر این اساس به تعداد K موقعیت در آرایه برای این عدد مشخص می‌شود. مقدار آرایه در موقعیت‌های مشخص شده را یک می‌کنیم. به این ترتیت عضو مورد نظر در فیلتر بولوم درج شد.
جستجو عنصر ویرایش
فرض کنید می‌خواهیم وجود یا عدم وجود عنصر x را در فیتر بولوم بررسی کنیم.
ابتدا این عنصر به K تابع درهم سازی داده و K موقعیت این عدد را در آرایه بولوم مشخص می‌کنیم. سپس مقادیر آرایه را در این K محل بررسی می‌کنیم. اگر در تعداد یک یا بیشتری خانه مقدار صفر بود، فیلتر با قطعیت جواب می‌دهد که این عنصر در آرایه وجود ندارد، زیرا اگر بود باید تمامی این K محل یک می‌بود. اما اگر تمامی آنها یک بود، معلوم نیست که این یک شدن به خاطر وجود این عنصر هست، یا به خاطر درج‌های دیگر عناصر منجر به یک شدن این خانه شده‌است؛ بنابراین جواب می‌دهد که احتمالاً این عنصر در فیلتر حضور دارد. از اینجا معلوم می‌شود که هرچه بیشتر عضو در آرایه درج بشود، احتمال غلط بودن جواب وجود عنصر بیشتر می‌شود.
حذف عنصر ویرایش
از آنجایی که خطای منفی در این فیلتر اجازه داده نمی‌شود، امکان حذف عنصر نیست. یعنی چون عدم وجود عنصر باید با قطعیت گفته شود، امکان حذف نداریم. این امر از اینجا حاصل می‌شود که موقعی که مایلیم عنصری را حذف کنیم، یعنی باید تمام بیت‌های متناظر این عنصر را در آرایه صفر کنیم. به این ترتیت این عنصر حذف می‌شود؛ ولی ممکن است مکان‌های عددهای دیگر با این عنصر اشتراکاتی داشته باشد که به اشتباه آن خانه‌ها صفر شده‌است؛ بنابراین اگر بعد از حذف عنصر، قصد جستجوی عنصر دیگر را داشته باشیم، اگر فیلتر جواب دهد که این عنصر در آرایه وجود ندارد ممکن است جواب درستی نباشد. زیرا صفر بودن بعضی از موقعیت‌های این عنصر در آرایه می‌تواند به معنی عدم وجود این عنصر نباشد. ممکن ناشی از حذف عنصرهایی باشد که با این عضو اشتراک موقعیتی داشته‌اند؛ لذا برای جلوگیری از خطای منفی، امکان حذف عنصر در این داده ساختار وجود ندارد.
حذف از فیلتر بلوم، در الگوریم‌های تغریبی کاربردهای مهمی را شامل می‌شود. در الگوریتم تشخیص تقریبی تکرار در جریان داده، هنگامی که داده‌های ورودی بیش از حد در فیلتر بلوم درج می‌گردند، K فضای آرایه‌های درهم سازی عملاً پر می‌شود و بررسی داده در آرایه‌ها کارایی ندارد (جواب همیشه بله است؛ نکته: در اینصورت باید در تمامی آرایه‌های فیلتر بلوم، اقدام به عمل re hash نمود و این عمل بسیار هزینه بر است)، بنابراین اقدام به حذف داده می‌نماید. حذف هر عنصر از فیلتر بلوم، قطعیت را کاهش می‌دهد، اما با درج عنصر جدید در آرایه و حذف خانه قدیمی در آرایه، به یک تشخیص تغریبی می‌رسیم.[1]
کاربرد ویرایش
کاربرد فیلتر بلوم در کامپیوتر، کاهش بار سرور (کاهش پیچیدگی زمانی) و در عین حال استفاده اندک از حافظه می‌باشد.
به عنوان مثال می‌خواهیم از درج کلمات نامناسب توسط کاربر جلوگیری کنیم، در این صورت باید کلمه به کلمه در جمله را در بانک اطلاعاتی جستجو کنیم. در حالت عادی پیچیدگی زمانی جستجوی خطی برابر است با (n)O حال اگر داده‌ها از قبل مرتب شده باشند پیچیدگی زمانی برابر است با ((n)LOG)O، اگر از قبل جدول هش ایجاد شده باشد پیچیدگی زمانی برابر (1)O است (این عمل به یک آرایه ثابت و رزرو شده نیازمند است که حجم زیادی از حافظه را اشغال می‌نماید). در صورت استفاده از فیلتر بلوم، ابتدا کلیه کلمات نامناسب در فیلتر بلوم درج می‌گردند. برای اطمینان حاصل کردن از نامناسب نبودن کلمه، آن را در فیلتر بلوم بررسی می‌نماییم؛ اگر فیلتر بلوم جواب دهد که این کلمه در مجموعه وجود دارد، احتمال دارد که وجود نداشته باشد و در این صورت برای حصول اطمینان از نامناسب نبودن کلمه باید آن را در بانک اطلاعاتی بررسی نمود، اما اگر بگوید وجود ندارد، قطعاً درست هست و دیگر در بانک اطلاعاتی جستجو انجام نمی‌شود.
مثال حذف عنصر از فیلتر بلوم ویرایش
مسئله: جلوگیری از حمله DDOS با استفاده از تشخیص تقریبی تکرار در جریان داده[1]
نحوه عملکرد در ۳ بند خلاصه می‌شود.
۱- ابتدا درخواست کننده تشخیص داده می‌شود؛ سرویس گیرنده کاربر است یا کامپیوتر (تکرار در درخواست‌های مکرر و بیش از حد به سرور را، به عنوان کامپیوتر، تشخیص می‌دهد)
2- IP متعلق به کامپیوتر سرویس گیرنده در هر بار تکرار درخواست، در آرایه‌های فیلتر بلوم درج می‌گردد.
۳- در صورت رسیدن به مرز اشباع (درصدی که آرایه می‌تواند داده در خود نگهداری کند، مثلاً مرز ۶۰ درصد)، اقدام به حذف داده‌های قدیمی می‌نماید. راه حل معمول، به‌کارگیری سیاست اخراج تصادفی برای بیت از فیلترهای بلوم به جای عناصر جدید و نگه داشتن FPR (نرخ مثبت کاذب) شود.
(نکته: هر ۳ بند به‌طور مداوم انجام می‌شود)
سؤال: وقتی می‌توان، IP کامپیوتر سرویس گیرنده را برای همیشه فیلتر کنند چرا صرفاً از عملکرد خالص فیلتر بلوم بدون حذف داده استفاده نمی‌کنند؟
جواب: برای هر بار اتصال به اینترنت نیاز به یک IP هست، این IPها به دو گروه پویا و ایستا تقسیم می‌شوند؛ در حملات DDOS، حمله کننده برای یک مدت زمان اندک از یک IP پویا استفاده می‌کند، در واقع IPهای خود را تغییر می‌دهند. حال اگر به‌طور مداوم چندین IP بسته شوند، نه تنها حمله کننده را محدود نکرده‌ایم، بلکه از دسترسی به جمعیتی از افراد که به‌طور تصادفی به یک IP پویا متصل می‌شوند، جلوگیری کرده‌ایم.