Força Bruta

Força bruta


Em ciência da computação, força bruta (ou busca exaustiva) é uma algoritmo trivial mas de uso muito geral que consiste em enumerar todos os possíveis candidatos de uma solução e verificar se cada um satisfaz o problema.
Por exemplo, um algoritmo para encontrar os divisores de um número natural n é enumerar todos os inteiros de 1 a n, e verificar para cada um se ele dividido por n resulta em resto 0.
Esse algoritmo possui uma implementação muito simples, e sempre encontrará uma solução se ela existir. Entretanto, seu custo computacional é proporcional ao número de candidatos a solução, que, em problemas reais, tende a crescer exponencialmente. Portanto, a força bruta é tipicamente usada em problemas cujo tamanho é limitado, ou quando há uma heurística usada para reduzir o conjunto de candidatos para uma espaço aceitável. Também pode ser usado quando a simplicidade da implementação é mais importante que a velocidade de execução, como nos casos de aplicações críticas em que os erros de algoritmo possuem em sérias consequências.
Índice

• 1 Aplicação na ordenação
• 2 Aplicação em problemas avançados
• 3 Exemplo de ataque
• 4 Referências

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 θ(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, θ(n + m) = θ(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.


• Observação: O exemplo abrange apenas uma senha com letras latinas minúsculas, ou seja, uma senha que possua apenas letras de " a - f ". 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.