Nieoczekiwana wszechobecność algorytmów wykrywania spamu

Jeśli chcesz dowiedzieć się, czy dwie wiadomości e-mail ze spamem są identyczne bez porównywania każdego zawartego w nich bajtu – co zajęłoby zbyt dużo czasu – przekształcasz plik w krótki ciąg, znany jako wartość skrótu kryptograficznego . Z natury funkcji skrótu kryptograficznego wynika, że ​​nawet najmniejsza zmiana w pliku da zupełnie inną wartość skrótu, więc łatwo jest stwierdzić, czy dwa pliki są identyczne.

Z Wikipedii: Działa kryptograficzna funkcja skrótu. Zauważ, że nawet małe zmiany w wejściu źródłowym drastycznie zmieniają wynikowy wynik.

Może to zabrzmieć trywialnie, ale tak nie jest: jeśli masz już przykład niepożądanego pliku – powiedzmy wiadomość e-mail ze spamem – i chcesz porównać go parami z milionami innych wiadomości e-mail przesyłanych strumieniowo przez twoje serwery, musisz mieć możliwość szybko go zidentyfikować. Porównywanie 40-cyfrowych ciągów jest znacznie łatwiejsze niż czytanie milionów e-maili o pigułkach na penisa.

Problem z funkcjami skrótu kryptograficznego polega na tym, że nawet najmniejsza zmiana w pliku źródłowym daje zupełnie inną wartość skrótu. Innymi słowy, są one bezużyteczne do porównywania plików, które mogą być funkcjonalnie identyczne, ale tylko trochę inne.

Jednym z rozwiązań tego problemu jest tak zwany skrót rozmyty lub skrót kroczący: zamiast tylko haszowania całego pliku, algorytm zapewnia ciągły strumień wartości skrótu dla okna kroczącego nad binarnym [oryginalnego pliku ],mówi David French, starszy pracownik naukowy w Instytucie Inżynierii Oprogramowania Carnegie Mellon.

Porównując kilka skrótów z dwóch plików, możesz określić procentową różnicę między nimi.

Podejście, które uogólnia… wszystko?

W tym momencie rozmyte mieszanie staje się naprawdę przydatne: nagle masz ogólną metodę szybkiego porównywania każdy strumień informacji.

Więc widzisz rozmyte haszy pojawiające się w całym miejscu. Oto wysiłek wspomnianego wcześniej dr French używać rozmytych skrótów do szybkiego określenia, czy plik na komputerze użytkownika jest wirusem, czy innym złośliwym oprogramowaniem. i Oto próba użycia rozmytych skrótów do porównania sekwencji genu draft jednego mikroorganizmu do znanej sekwencji od pokrewnego stworzenia. To ogromna wartość dla genetyków, dla których najszybszym sposobem na złożenie w miarę dokładnego genomu istoty, której wcześniej nie zsekwencjonowano, jest porównanie zsekwencjonowanych fragmentów jego genów ze znaną sekwencją.

Czy zastanawiałeś się kiedyś, w jaki sposób Google wykrywa zduplikowane treści, aby dostarczać tylko najtrafniejsze wyniki, a nie setki kopii artykułów prasowych lub materiałów źródłowych, które nieuchronnie kończą na splogach rozsianych po całym Internecie? Znowu mieszanie rozmyte ! Może nawet wykryć identyczne dokumenty, które są przechowywane w zupełnie różnych formatach:

*Częsty przypadek dotyczy tego samego dokumentu, ale w różnych formatach; w takich przypadkach będziemy mieć zupełnie inne dokumenty na poziomie binarnym. Oczywistym rozwiązaniem jest porównanie konwersji zwykłego tekstu wszystkich tych formatów, ale te konwersje nigdy nie są identyczne, ze względu na różne traktowanie konwerterów na różnych elementach formatowania (obsługa znaków tekstowych, znaków diakrytycznych, odstępów, akapitów…). W tej pracy przedstawiamy możliwość wykorzystania tzw. rozmytego haszowania. Pomysł polega na tworzeniu odcisków palców plików (lub dokumentów itp.). W ten sposób porównanie dwóch odcisków palców może dać nam oszacowanie bliskości lub odległości między dwoma plikami, dokumentami itp.

Do diabła, możesz powiedzieć, jak ważne jest mieszanie rozmyte, ponieważ Michael Gregory Hoglund z Monte Sereno w Kalifornii właśnie otrzymał kompleksowy patent na proces , które nazywa generowaniem cyfrowej sekwencji DNA dla obiektu danych. Zanim się zorientujesz, troll patentowy kupi go od Hoglundu i wtedy zacznie się prawdziwa zabawa.

Rozmyte skróty są jednym z tych niewidzialnych elementów hydraulicznych, jak algorytm MapReduce wymyślony przez Google, który stanowi podstawę praktycznie każdej gigantycznej usługi internetowej, o której możesz pomyśleć, i ma kluczowe znaczenie dla działania globalnego umysłu-ula, od którego jesteśmy zależni.

Za każdym razem komputer musi zapytać: Która z tych rzeczy nie jest podobna do drugiej? Odpowiedź brzmi: Zapytaj rozmytą funkcję mieszającą!

Śledź Mims na Twitterze lub skontaktuj się z nim przez e-mail .

ukryć