Mostrar código-fonte de Busca por força bruta

{{ver desambig2|redir=Força bruta|Força bruta (desambiguação)}}
{{mais notas|data=Dezembro de 2011}}
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 [[divisor]]es 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 [[prova automática de teoremas|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ística]]s. 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 [[Sub-rotina|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:
# ''primeiro'' (''P''): gera o primeiro candidato à solução de ''P''.
# ''próximo'' (''P'', ''c''): gera o próximo candidato de ''P'' depois de ''c''.
# ''válido'' (''P'', ''c''): checa se o candidato ''c'' é a solução de ''P''.
# ''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'' <math>\gets</math> ''primeiro''(''P'')
 '''enquanto''' ''c'' <math>\neq</math> Λ ''faça''' ''se''' ''válido''(''P'',''c'') '''então''' ''saída''(''P'', ''c'')  ''c'' <math>\gets</math> ''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'' <math>\geq</math> 1, ou Λ caso contrário; a chamada ''próximo''(''n'',''c'') deverá retornar ''c'' + 1 se ''c'' <math><</math> ''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'' <math>\geq</math> 1 e ''c'' <math><</math> ''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 [[unidade central de processamento|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<sup>15</sup> instruções no computador, o que iria levar alguns dias em um [[computador pessoal|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<sup>18</sup> 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ística]]s 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<sup>8</sup> = 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ção|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 [[valor esperado|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ística]]s 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|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 (computação)|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 <math>n</math> (o "texto") e outra cadeia com tamanho <math>m</math> 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 <math>m</math> caracteres antes de se deslocar, e isso pode ocorrer para cada uma das <math>n-m+1</math> tentativas. Portanto, o pior caso para este algoritmo está em <math>\theta(n.m)</math>. 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, <math>\theta(n+m) = \theta(n)</math>.

== 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 <math>n</math> 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:<ref>O conteúdo original pode ser encontrado na seção "7z format" da "General Information" do arquivo de ajuda do programa "7-Zip" na versão "4.58", sendo que o mesmo se encontra sob a licença GNU [[LGPL]], tendo assim a permissão para a copia e modificação do texto sem aviso prévio do grupo compositor do mesmo. {{en}}</ref>

'''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 [[Alfabeto latino|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ólar]]es 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:'''
{| class="wikitable" border="1"
|-
! 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 " {{citação faltando}}. Ao colocar a possibilidade de existir letras maiúsculas e [[Símbolo| símbolos especiais]] aumentará ainda mais o tempo para se realizar todas as possibilidades de um ataque.

==Em criptografia==
{{main|Ataque de força bruta}}

Em [[criptografia]], um ''ataque de força bruta'' envolve checar sistematicamente todas as possíveis [[chave (criptografia)|chaves]] até a chave correta ser encontrada. Esta estratégia pode ser em teorica usada contra qualquer dado encriptografado<ref>{{citar livro|url=http://www.crypto-textbook.com|página=7|título=Understanding Cryptography: A Textbook for Students and Practitioners|autor =Christof Paar, Jan Pelzl, Bart Preneel|publicado=Springer|ano=2010|isbn=3642041000}}</ref> 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)]]<ref>EUA e Reino Unido ‘derrotaram’ criptografia na internet - Carta Maior - 7 de setembro de 2009[http://www.cartamaior.com.br/?/Editoria/Politica/EUA-e-Reino-Unido-%27derrotaram%27-criptografia-na-internet/4/28544 ]</ref><ref>NSA e GCHQ têm capacidade de quebrar a segurança e criptografia da Internet - 6 de setembro de 2013- TECHNET[http://www.techenet.com/2013/09/nsa-e-gchq-tem-capacidade-de-quebrar-a-seguranca-e-criptografia-da-internet/ | TecheNet - tecnologia, Internet, ciência, redes sociais, design]</ref><ref>[http://oglobo.globo.com/sociedade/tecnologia/revelacoes-de-snowden-poem-formula-de-seguranca-digital-em-xeque-10050988 Revelações de Snowden põem fórmula de segurança digital em xeque]Jornal O Globo - 20 de setembro de 2013</ref><ref>Documents Reveal N.S.A. Campaign Against Encryption - Documents - NYTimes.com - 5 de setembro de 2013[http://www.nytimes.com/interactive/2013/09/05/us/documents-reveal-nsa-campaign-against-encryption.html ]</ref>

{{Referências}}
[[Categoria:Algoritmos de busca]]