maneira mais rápida de Bruteforce uma string usando um curinga DOS

Question

Este problema é semelhante ao injeções cego SQL. O objetivo é determinar o valor exato de uma corda, e o único teste que você pode fazer é ver se um curinga DOS-estilo (? = Qualquer personagem, * = qualquer número de caracteres) que você especificar é compensada pela string. (Então, praticamente você só tem acesso a uma função bool DoesWildcardMatch(string wildcard)).

A maneira simples e direta é a prova contra a*, b*, c*... até encontrar a primeira letra, em seguida, repita. Algumas otimizações que eu posso pensar de:

• procurar *a*, *b* etc. para determinar o conjunto de caracteres
• quando uma correspondência em *x* for encontrado, executar divide-et-impera (*a*x*, *b*x*, ...)

Answer 1

Um primeiro pensamento. Você pode determin o n comprimento da corda em O(log2(n)).

• Verifique Z* onde Z representa pontos de interrogação k começando com 0, 1, e em seguida, dobrando o número de pontos de interrogação com cada cheque até páreo ocorre. n deve estar entre k / 2 e k
• Encontre o comprimento exato usando o mesmo padrão de mudança k da mesma forma como busca binária faz.

Conhecer a exata ajuda comprimento poder para realizar uma espécie de divisão-et-impera no domínio espacial.

Atualizar

Se você sabe o comprimento, você pode usar o mesmo padrão para localizar corretamente um símbolo.

Exemplo:

    ..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

Para n comprimento da corda e m tamanho alfabeto isso vai levar cerca de O(log2(n)) para encontrar o comprimento da corda, sobre O(n • log2(n)) para corretamente símbolos lugar n e O(m) para encontrar os símbolos usados ??-. Somar todos os rendimentos em conjunto O(n • log2(n) + m)

Eu poderia imaginar que é possível acelerar este processo através da fusão de várias etapas - (? Ou mesmo mais), talvez teste para símbolos usados ??ao determinar o comprimento da corda ou simultaneamente localizar dois símbolos na primeira e na segunda metade do string. Isso vai exigir para verificar novamente os passos incorporadas em isolamento, se a verificação falhar, a fim de determinar qual o cheque faild. Mas, enquanto a verificação incorporada tiver êxito, obter informações sobre ambos.

Talvez eu irá calcular que amanhã, a fim de ver se ele vai realmente acelerar a coisa.

Answer 2

Quanto ao dividir-et-impera, certifique-se de manter o controle de valor que você sabe não estão presentes. Também eu não iria com a, b, c, mas com ordem de freqüência. Algum tipo de cadeia de Markov de que pode torná-lo ainda mais rápido.

Uma coisa a observar é que não se pode presumir que um dado literal sempre coincidir com a mesma localização na entrada. Isto será de particular interesse sobre a remoção dos wild cards no final.

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

Answer 3

Se um número específico de? obras, você também pode verificar "?", "??", "???" etc para obter o comprimento da corda, mas eu duvido que isso vai ajudar muito como você também pode verificar se você tem o comprimento certo com apenas uma verificação adicional sem curingas depois de cada rodada.

Eu acho que o método de divisão com um cheque conjunto de caracteres antes é quase ideal, existem alguns detalhes adicionais, por exemplo, se combinados *a*b*, você deve verificar *ab* depois para saber se existem cartas no meio e, claro, como dito acima , verificação *ab e "ab" após este saber se você terminar no lado direito ou completamente.

Answer 4

Por que não converter a cadeia de estilo curinga DOS em uma expressão regular? por exemplo:.

? A *

torna-se:

.a. *

Em seguida, basta executar uma correspondência de expressão regular comparando que a sua seqüência de teste.