Najszybszy sposób na bruteforce string za pomocą znaku wieloznacznego DOS

Question

Ten problem jest podobny do niewidocznych iniekcji SQL. Celem jest ustalenie dokładnej wartości ciągu znaków, a jedynym testem, który można wykonać, jest sprawdzenie, czy znak wieloznaczny w stylu DOS (? = Dowolny znak, * = dowolna liczba dowolnych znaków) jest dopasowany przez ciąg znaków. (Praktycznie masz dostęp tylko do funkcji bool DoesWildcardMatch(string wildcard)).

Prostym sposobem jest przetestowanie przed a*, b*, c*..., aż znajdziesz pierwszą literę, a następnie powtórz. Niektóre optymalizacje mogę myśleć:

• wyszukiwania dla *a*, *b* itp określić zestaw znaków
• gdy mecz na *x* zostanie znaleziony, należy wykonać dzielenie-et-impera (*a*x*, *b*x*, ...)

Answer 1

Pierwsza myśl. Możesz określić długość n ciągu w O(log2(n)).

• Sprawdź Z* gdzie Z reprezentuje k znaki zapytania zaczynające się od 0, 1, a następnie podwojenie liczby znaków zapytania z każdego czeku, dopóki nie nastąpi dopasowanie. n musi znajdować się pomiędzy k/2 i k
• Znajdź dokładną długość, używając tego samego wzorca zmieniającego k w taki sam sposób, jak w przypadku wyszukiwania binarnego.

Znajomość dokładnej długości może pomóc w dokonaniu pewnego rodzaju podział-et-impera w dziedzinie przestrzeni.

UPDATE

Jeśli znasz długość, można użyć tego samego wzorca, aby prawidłowo zlokalizować symbol.

Przykład:

 
    ..X. ..XX (spaces added for readability) 

           + symbol may be X 
           - symbol is not X 
           X symbol is X 

    *X*   => MATCH  ++++ ++++ 
    *X* ???? => MATCH  ++++ ++++ 
    *X*?? ???? => NO MATCH --++ ++++ 
    ??X? ???? => MATCH  --X+ ++++ 
    ??XX ???? => NO MATCH --X- ++++ 
    ??X? *X*?? => NO MATCH --X- --++ 
    ??X? ??X? => MATCH  --X- --X+ 
    ??X? ??XX => MATCH  --X- --XX 

Dla długości n i alfabetu strun wielkości m zajmie to około O(log2(n)) znaleźć długość łańcucha, o O(n • log2(n)) prawidłowo umieszczać n symbole i O(m) znaleźć używane symbole - sumując wszystkie razem plony O(n • log2(n) + m).

Mogę sobie wyobrazić, że można to przyspieszyć, łącząc kilka kroków - może przetestować używane symbole podczas określania długości ciągu lub jednocześnie lokalizując dwa (lub nawet więcej?) Symbole w pierwszej i drugiej połowie ciągu . Będzie to wymagało ponownego sprawdzenia połączonych kroków w izolacji, jeśli sprawdzenie nie powiedzie się, aby ustalić, który z testów zakończył się niepowodzeniem. Ale tak długo, jak sprawdza się fuzja połączona, zyskujesz informacje na temat obu.

Może policzę to jutro, żeby sprawdzić, czy to naprawdę przyspieszy.

Answer 2

Jeśli konkretna liczba? działa, możesz również sprawdzić "?", "??", "???" itp., aby uzyskać długość sznurka, ale wątpię, że to bardzo pomoże, ponieważ możesz również sprawdzić, czy masz odpowiednią długość z jednym dodatkowym czekiem bez symboli wieloznacznych po każdej rundzie.

Myślę, że metoda dzielenia z wcześniejszym sprawdzeniem zestawu znaków jest prawie optymalna, istnieją pewne dodatkowe szczegóły, na przykład, jeśli pasowałeś do *a*b*, powinieneś sprawdzić później *ab*, aby dowiedzieć się, czy pomiędzy nimi są litery i oczywiście jak podano powyżej, sprawdź *ab i "ab" po tym, aby wiedzieć, czy skończyłeś po prawej stronie, czy w całości.

Answer 3

Dlaczego nie przekonwertować ciągu znaków wieloznacznych w stylu DOS na wyrażenie regularne? ? Np .:

a *

staje:

.a *

Następnie wystarczy wykonać proste wyrażenie regularne spotkania porównując to do łańcucha testowego..

Answer 4

Co do podziału-et-impera, pamiętaj, aby śledzić wartość, o której wiesz, że nie ma jej. Również nie chciałbym iść z a, b, c, ale z porządkiem częstotliwości. Jakiś łańcuch Markowa może sprawić, że będzie jeszcze szybszy.

Jedną z rzeczy, na które należy zwrócić uwagę, jest to, że nie można założyć, że dany literał zawsze będzie pasować do tego samego miejsca na wejściu. Będzie to szczególnie interesujące w przypadku usuwania dzikich kart na końcu.

c a b a 
-------- 
* a *  match 
    * b*a* woops!