Busca por força bruta

 Nota: "Força bruta" redireciona para este artigo. Para outros significados, veja Força bruta (desambiguação).

Em ciência da computação, busca por força bruta ou busca exaustiva, também conhecido como gerar e testar, é uma técnica de solução de problemas trivial, porém muito geral que consiste em enumerar todos os possíveis candidatos da solução e checar cada candidato para saber se ele satisfaz o enunciado do problema. Por exemplo, um algoritmo de força bruta que acha os divisores de um número natural n enumera todos os inteiros de 1 até a raiz quadrada de n, e os checa para saber se dividem n sem deixar resto. Outro exemplo, considere o popular problema das oito damas, no qual é preciso colocar 8 damas em um tabuleiro de xadrez de maneira que nenhuma rainha ataque outra. Uma abordagem por força bruta examinaria todas as possíveis combinações das 8 peças nos 64 quadrados, e, para cada arranjo, checar se alguma rainha está atacando outra. Busca por força bruta é de simples implementação, e sempre vai achar a solução se esta existir. Entretanto, ele custará proporcionalmente ao número de candidatos à solução, o que, em muitos problemas práticos, tende a crescer muito rápido à medida que o tamanho do problema aumenta. Desta maneira, busca por força bruta é tipicamente usada quando o tamanho do problema é limitado, ou quando há heurísticas específicas para o problema que podem ser usadas para reduzir a coleção de candidatos á solução a um tamanho manejável. Este método também é usado quando a simplicidade de implementação é mais importante que a velocidade. Este é o caso de, por exemplo, em aplicações críticas onde qualquer erro no algoritmo teria consequências sérias; ou quando estiver usando um computador para provar um teorema matemático. Busca por força bruta também é útil como "método de base" para benchmarking outros algoritmos ou meta-heurísticas. De fato, busca por força bruta pode ser visto como a mais simples meta-heurística. Busca por força bruta não deve ser confundido com backtracking, onde grandes coleções de soluções podem ser descartadas sem serem explicitamente enumerados. O método de força bruta para achar um item em uma tabela — ou seja, checar todas as entradas da tabela, sequencialmente — é chamado busca linear.

Implementando a busca por força bruta

Algoritmo Básico

Para aplicar busca por força bruta para uma classe específica de problemas, é preciso implementar quatro procedimentos, primeiro,próximo, válido, e saída. Estes procedimentos devem ter como parâmetro os dados P para a instancia do problema que será resolvido, e deve fazer o seguinte:

1. primeiro (P): gera o primeiro candidato à solução de P.
2. próximo (P, c): gera o próximo candidato de P depois de c.
3. válido (P, c): checa se o candidato c é a solução de P.
4. saída (P, c): usa a solução c de P como for conveniente para a aplicação.

O procedimento próximo também deve dizer quando não há mais candidatos à P, após o c atual. Uma maneira conveniente de fazer isto é retornando um "candidato nulo", um valor de dados comum Λ que é distinto de qualquer outro candidato real. Da mesma maneira primeiro deve retornar Λ se não houver nenhum candidato para a instancia P. O método de busca por força bruta é expresso pelo algoritmo

 c $\gets$ primeiro(P)
enquanto c $\neq$ Λ faça se válido(P,c) então saída(P, c)  c $\gets$ próximo(P,c)

Por exemplo, quando buscando os divisores de um inteiro n, a instância de dados P é o número n. A chamada primeiro deverá retornar o inteiro 1 se n $\geq$ 1, ou Λ caso contrário; a chamada próximo(n,c) deverá retornar c + 1 se c $<$ n, e Λ caso contrário; e válido(n,c) deverá retornar verdadeiro se e somente se c é divisor de n. (De fato, se escolhermos Λ para ser n + 1, os testes n $\geq$ 1 e c $<$ n serão desnecessários). O algoritmo de busca por força bruta acima irá chamar saída para cada candidato que é a solução para a dada instancia P. O algoritmo é facilmente modificado para parar após encontrar a primeira solução, ou um número dado de soluções; ou após serem testados um número dado de candidatos, ou após ter gasto uma dada quantidade de tempo da CPU .

Explosão combinatória

A principal desvantagem do método por força bruta é que, para muitos problemas reais, o numero de candidatos naturais é grande. Por exemplo, se olharmos os divisores de um número como descrito acima, o número de candidatos testados será o número n. Então se n tiver dezesseis dígitos decimais, a pesquisa vai requerer pelo menos 10¹⁵ instruções no computador, o que iria levar alguns dias em um computador comum. Se n for um número natural aleatório de 64-bit, que teria cerca de 19 dígitos decimais, a busca levaria cerca de 10 anos. Esse exorbitante crescimento do número de candidatos ocorre em todos os tipos de problemas. Por exemplo, se estivermos buscando um reajuste específico de 10 letras, teríamos 10! = 3.628.800 candidatos a considerar, o que um computador comum consegue gerar e testar em menos de um segundo. Entretanto, adicionando uma letra — o que é apenas 10% de aumento no tamanho dos dados — vai multiplicar o número de candidatos por 11 — um aumento de 1000%. Para 20 letras, o número de candidatos é 20!, o que é cerca de 2,4×10¹⁸ ou 2,4 quinquilhões; e a busca levaria cerca de 10,000 anos. Este indesejado fenômeno é comumente chamado de explosão combinatória.

Acelerando buscas por força bruta

Uma maneira de acelerar um algoritmo de força bruta é reduzir o espaço de busca, isto é, o conjunto de candidatos à solução, usando meta-heurísticas específicas da classe do problema. Por exemplo, considere o popular problema das oito damas, no qual é preciso colocar 8 damas em um tabuleiro de xadrez de maneira que nenhuma rainha ataque outra. Já que cada dama pode ser colocada em qualquer um dos 64 quadrados, em princípio existem 64⁸ = 281.474.976.710.656 (mais de 281 trilhões) possibilidades a considerar. Entretanto, se observarmos que todas as damas são iguais, e que duas damas não podem ser colocadas num mesmo quadrado, nós concluímos que as candidatas são uma combinação de um conjunto de 8 quadrados em um conjunto de 64; o que quer dizer que há 64!/56!8! = 4.426.165.368 candidatas a solução, 1/60.000 da estimativa anterior. Na verdade, é fácil ver que nenhum arranjo com duas rainhas na mesma linha ou mesma coluna pode ser uma solução. Desta maneira, podemos restringir ainda mais a coleção de candidatas para arranjos onde dama 1 está na linha 1, dama 2 está na linha 2, e assim sucessivamente, e todas em colunas diferentes. Podemos descrever este arranjo usando um array de oito números, c[1] até c[8], cada um deles sendo um número entre 1 e 8, onde c[1] é a coluna da dama 1, c[2] é a coluna da dama 2, e assim sucessivamente. Já que esses números precisam ser todos diferentes, o número de candidatas para buscar é o número de permutações de 1 até 8, chamado 8! = 40.320 — cerca de 1/100.000 da estimative anterior, e 1/7.000.000.000 da primeira. Como este exemplo mostra, uma pequena análise normalmente vai diminuir drasticamente o número de candidatas à solução, e pode transformar um problema intratável em um trivial.

Reordenando o espaço de busca

Em aplicações que requerem somente uma solução, o tempo esperado de uma busca por força bruta vai depender da ordem na qual os candidatos são testados. Em geral, devem-se testar os candidatos mais promissores primeiro. Por exemplo, quando procurando um divisor para um numero n, é melhor enumerar os candidatos em ordem crescente, de 2 até n - 1, do que o contrário — porque a probabilidade de n ser divisível por c é 1/c. Além disso, a probabilidade de um candidato ser válido é comumente afetada por testes anteriores que falharam. Por exemplo, considere o problema de achar um 1 bit em uma dada string P de 1000-bit. Neste caso, as candidatas a solução são os indices 1 até 1000, e o candidato c é válido se P[c] = 1. Agora, suponha que o primeiro bit de P é igualmente provavel ser 0 ou 1, mas cada bit depois é igual ao anterior 90% das vezes. Se os candidatos forem enumerados em ordem crescente, 1 até 1000, o número t de candidatos examinados antes do correto será ,em média, 6. De outra maneira, se os candidatos forem enumerados na ordem 1,11,21,31...991,2,12,22,32 etc…, o valor esperado de t sera apenas um pouco maior de 2. No geral, o espaço de busca deve ser enumerado de maneira que o próximo candidato é terá uma maior probabilidade de ser válido, dado que o teste anterior não foi.

Alternativas a busca por força bruta

Existem muitos outros métodos de busca, ou meta-heurísticas, que foram concebidos para tirar vantagem de vários tipos de conhecimentos parciais sobre a solução. Heurísticas também podem ser usadas para eliminarem partes da busca. Um exemplo disso é o princípio minimax para buscar árvores de jogo, que elimina muitas sub-árvores no estado inicial da busca. Em algumas áreas, como análise de linguagens, técnicas como análise de gráfico podem explorar as restrições do problema para reduzir um problema de complexidade exponencial em um problema de complexidade polinomial. O espaço de busca dos problemas podem ser reduzidos substituindo o problema inteiro por uma versão simplificada. Por exemplo, no xadrez por computador, ao invés de computar o a árvore minimax de todos os movimentos possíveis para o resto do jogo inteira, uma árvore mais limitada de possibilidades minimax é computada, com a árvore sendo podada a um certo número de movimentos, e o resto da árvore sendo aproximado por uma função de avaliação estática.

Aplicação na ordenação

Um exemplo clássico de aplicação de algoritmos da classe da força bruta é a ordenação, que pode ser aplicada nos mais diferentes tipos de dados.

Por exemplo, uma das formas de resolver o problema consiste em procurar o menor elemento e colocá-lo na primeira posição, operando sucessivamente com os demais elementos da lista a ser classificada até finalizar a operação, um método conhecido como ordenação por inserção.

Outro exemplo é a busca de padrões. Dada uma cadeia de caracteres de tamanho $n$ (o "texto") e outra cadeia com tamanho $m$ menor ou igual chamada "padrão". É realizada uma procura no "texto" pelo "padrão", verificando-se todo o texto em busca de múltiplas ocorrências. O funcionamento da busca de padrão é simples: se o primeiro caractere é idêntico à um referente no texto, todos os sucessores devem ser idênticos também, até finalizar o padrão. Caso ocorra que um caractere não seja igual, desloca-se o padrão em um caractere até chegar ao fim do texto ou encontrar o padrão.

rotina BuscaPadrao(texto[0 ... n-1], padrao[0 ... m-1])
    para i ← 0 até n – m faça
        j ← 0
        enquanto j < m e padrao[j] = texto[i + j] faça
            j ← j + 1
        se j = m então
            retorne i
    retorne -1

Note que o algoritmo desloca-se após a comparação do primeiro caractere, porém nem sempre é assim. O pior caso é "muito pior": o algoritmo tem que comparar todos os $m$ caracteres antes de se deslocar, e isso pode ocorrer para cada uma das $n-m+1$ tentativas. Portanto, o pior caso para este algoritmo está em $\theta (n.m)$. Para textos de linguagem natural, o caso médio é melhor (pois ocorre nas primeiras comparações). Até em textos aleatórios, o comportamento se mostra linear, $\theta (n+m)=\theta (n)$.

Aplicação em problemas avançados

Um exemplo é o problema do par mais próximo, que consiste em achar os dois pontos mais próximos em um conjunto de $n$ pontos. Para o exemplo a seguir, por simplicidade se assume o plano cartesiano, de forma que a distância é calculada pela distância euclidiana. O algoritmo de força bruta percorrerá o conjunto, e selecionará o par com menor distância, ignorando pontos na mesma posição.

rotina ParProximo(P)
    dmin ← ∞
    para i ← 1 até n – 1 faça
        para j ← i + 1 até n faça
            d ← raiz((xi - xj)² + (yi – yj)²)
            se d < dmin
                dmin ← d
                ind1 ← i
                ind2 ← j
    retorne ind1, ind2

Exemplo de ataque

O grupo que gerencia o programa 7-Zip criou um exemplo de quanto tempo demoraria para um atacante burlar um sistema através de força bruta, segue abaixo a tradução do problema:

Ataque de acordo com o número de caractere da senha

Isto é uma estimativa de tempo requerido para um exaustivo ataque de senha (força bruta), sendo que a senha é uma seqüencia aleatória de letras minúsculas latinas.

Vamos supor que um usuário possa controlar 10 senhas por segundo e que uma organização com um orçamento de $1 bilhão (mil milhões) de dólares possa controlar 1 bilhão de senhas por segundo. Também supomos que o processador em uso duplica seu desempenho a cada dois anos, assim, cada letra latina que acrescentarmos será adicionada 9 anos de um exaustivo ataque de senha.

O resultado é esta estimativa de tempo para ter sucesso num ataque:

Tamanho da senha	Ataque de um usuário comum	Ataque da organização
1 letra minúscula latina	2 segundos	1 segundo
2	1 minuto	1s
3	30 min	1s
4	12 horas	1s
5	14 dias	1s
6	1 ano	1s
7	10 anos	1s
8	19 anos	20s
9	26 anos	9 min
10	37 anos	4 horas
11	46 anos	4 dias
12	55 anos	4 meses
13	64 anos	4 anos
14	73 anos	13 anos
15	82 anos	22 anos
16	91 anos	31 anos
17	100 anos	40 anos

• Observação: O exemplo abrange apenas uma senha com letras latinas minúsculas, ou seja, uma senha que possua apenas letras de " a - f " Predefinição:Citação faltando. Ao colocar a possibilidade de existir letras maiúsculas e símbolos especiais aumentará ainda mais o tempo para se realizar todas as possibilidades de um ataque.

Em criptografia

Ver artigo principal: Ataque de força bruta

Em criptografia, um ataque de força bruta envolve checar sistematicamente todas as possíveis chaves até a chave correta ser encontrada. Esta estratégia pode ser em teorica usada contra qualquer dado encriptografado por um hacker que não pode tirar vantagem de alguma fraqueza na encriptação que faria a tarefa mais fácil.

O comprimento da chave usada na encriptação determina a praticabilidade de se fazer um ataque de força bruta, já que chaves mais longas são exponencialmente mais difíceis do que chaves menores. Uma das medidas da força de encriptação é o tempo que, teoricamente, levaria para um hacker conseguir lançar um ataque de força bruta bem-sucedido contra ela.

Ver também

• Bullrun (Programa de decriptografia)