Força bruta

Origem: Wikipédia, a enciclopédia livre.
(Redirecionado de Bruteforce)
Ir para: navegação, pesquisa
Merge-arrow 2.svg
Este artigo ou secção deverá ser fundido com Busca por força bruta. (desde março de 2013)
(por favor crie o espaço de discussão sobre essa fusão e justifique o motivo aqui; não é necessário criar o espaço em ambas as páginas, crie-o somente uma vez. Perceba que para casos antigos é provável que já haja uma discussão acontecendo na página de discussão de um dos artigos. Verifique ambas (1, 2) e não esqueça de levar toda a discussão quando levar o caso para a central.).
Question book.svg
Este artigo não cita fontes confiáveis e independentes. (desde março de 2013). Por favor, adicione referências e insira-as corretamente no texto ou no rodapé. Conteúdo sem fontes poderá ser removido.
Encontre fontes: Google (notícias, livros e acadêmico)

Em ciência da computação, força bruta (ou busca exaustiva) é um 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.

Aplicação na ordenação[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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:[1]

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.

Referências

  1. 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. (em inglês)
Ícone de esboço Este artigo sobre programação de computadores é um esboço. Você pode ajudar a Wikipédia expandindo-o.