Ostatnio pisałem, że chcę wykorzystać algorytmy do wyliczania edit distance w celu sortowania nazw domen wygenerowanych przez mój skrypt do fuzzingu/wyszukiwania nazw podobnych do wskazanej. Nie był to jednak najlepszy pomysł.
Edit distance to jednak nie był taki dobry pomysł...
Dlaczego? Ponieważ, jak sama nazwa wskazuje, wyliczana wartość jest ilością zmian edycyjnych potrzebnych do przekształcenia jednego ciągu znaków w inny. Zmianą edycyjną jest wstawienie, usunięcie, zamienienie (i opcjonalnie transpozycja). Czyli mając przykładową domenę mroczna-zaloga.org wszystkie poniższe będą wymagały takiej samej ilości zmian edycyjnych:
- mrozcna-zaloga.org (transpozycja c i z)
- Wroczna-zaloga.org (zmiana m na W)
- mrocznazaloga.org (usunięcie znaku -)
- mrroczna-zaloga.org (dodanie litery r)
Na dalszym miejscu znajdą się przypadki takie jak rnroczna-zaloga.org (wstawienie znaku r i zamiana m na n), która z ludzkiego punktu widzenia jest chyba bardziej podobna do oryginału, niż przykład z W na początku.
Poza tym po zastanowieniu się, to generowane przez mój fuzzer "podobne" nazwy domen zwykle będą wymagały tylko jednej zmiany edycyjnej. Dlaczego? Bo takie było założenie przy ich tworzeniu. Wykonywanymi przez fuzzery operacjami są właśnie te podstawowe operacje edycyjne, czyli dodanie znaku, pominięcie znaku, transpozycja sąsiednich znaków, zamiana znaku na inny. Inaczej zachowuje się tylko fuzzer zastępujący znak ciągiem znaków podobnych, tam tych zmian edycyjnych jest często dwie (taj jak w przypadku m i rn. Swoją drogą przy okazji można zastanowić się, dlaczego wykonywać tylko jedna zmianę edycyjną, czy nie fuzzować "głębiej". Myślałem nad tym i w pewnej chwili doszedłem do wniosku, że wówczas w praktyce zbliżamy się do ataku typu brute force na nazwę domeny, a to nie o to chodzi...
