Alguma ciência da computação corretiva, para os auditores do PCI na minha audiência.
Entrego uma matriz de números inteiros aleatórios. Como você pode saber se o número três está nele?
Bem, existe a maneira óbvia: verifique os números sequencialmente até encontrar o "3" ou esgotar a matriz. Pesquisa linear. Dados 10 números, você deve assumir que pode levar 10 etapas; N números, N passos.
Figura 1.png
A pesquisa linear é ruim. É difícil fazer pior que linear. Vamos melhorar. Classifique a matriz.
Figura 2.png
Uma matriz classificada sugere uma estratégia diferente: pule o meio da matriz e veja se o valor que você está procurando é menor que (à esquerda) ou maior que (à direita). Repita, cortando a matriz ao meio de cada vez, até encontrar o valor.
Pesquisa binária. Dados 10 números, serão necessários até 3 etapas - log2 de 10 - para encontrar um deles em uma matriz classificada. A pesquisa O (log n) é impressionante. Se você tiver 65.000 elementos, serão necessárias apenas 16 etapas para encontrar um deles. Dobre os elementos, e são 17 etapas.
Mas matrizes ordenadas são péssimas; por um lado, a classificação é mais cara que a pesquisa linear. Portanto, não usamos muito a pesquisa binária; em vez disso, usamos árvores binárias.
Figura 3.png
Para pesquisar em uma árvore binária, comece no topo e pergunte a si mesmo "é minha chave menor que (esquerda) ou maior que (direita) o nó atual" e repita até ok, ok, ok, você já conhece essas coisas. Mas essa árvore é bonita, não é?
A pesquisa com uma árvore binária (equilibrada) é O (log n), como a pesquisa binária, variando com o número de elementos na árvore. As árvores binárias são impressionantes: você obtém uma pesquisa rápida e um percurso ordenado, algo que não sai de uma tabela de hash. Árvores binárias são uma implementação de tabela padrão melhor do que tabelas de hash. 2)
Mas as árvores binárias não são o único mecanismo de pesquisa estruturado em árvore. As tentativas de raiz binária, também chamadas de árvores PATRICIA, funcionam como árvores binárias com uma diferença fundamental. Em vez de comparar maior que / menos que em cada nó, você verifica se um bit está definido, ramificando para a direita se estiver definido e para a esquerda se não estiver.
Figura 4.png
Estou deixando de fora muito sobre como o radix binário tenta funcionar. É uma pena, porque as tentativas radicais são notoriamente mal documentadas - Sedgewick estragou-as infamemente em "Algoritmos", e a página da Wikipedia para eles é péssima. As pessoas ainda discutem sobre como chamá-las! Em vez de uma explicação de backlinks e bordas rotuladas com posição de bit, aqui está uma pequena implementação do Ruby.
Eis por que as tentativas de radix são legais:
Search performance varies with the key size, not the number of elements in the tree. With 16 bit keys, you’re guaranteed 16 steps
independentemente do número de elementos na árvore, sem balanceamento.
More importantly, radix tries give you lexicographic matching, which is a puffed-up way of saying “search with trailing wildcard”, or
"Pesquisa no estilo de conclusão da linha de comando". Em uma árvore de raiz, você pode procurar rapidamente por "ro *" e obter "roma" e "romulous" e "roswell".
3)
Eu te perdi.
Vamos colocar isso em contexto. As tentativas são uma estrutura de dados crucial para o roteamento da Internet. O problema de roteamento é assim:
You have a routing table with entries for “10.0.1.20/32 -> a” and “10.0.0.0/16 -> b”.
You need packets for 10.0.1.20 to go to “a”
You need packets for 10.0.1.21 to to to “b”
Este é um problema difícil de resolver com uma árvore binária básica, mas com um teste de raiz, você está apenas pedindo "1010.0000.0000.0000.0000.0001.0100" (para 10.0.1.20) e "1010." (para 10.0.0.0 ) A pesquisa lexicográfica oferece a "melhor correspondência" para o roteamento. Você pode experimentá-lo no código Ruby acima; adicione * ”10.0.0.0” .to_ip à tentativa e pesquise “10.0.0.1” .to_ip.
A correspondência entre as tentativas de roteamento e radix é tão forte que a biblioteca radix trie de uso geral mais popular (a da CPAN) é realmente roubada do GateD. A propósito, é uma bagunça e não a use.
Se você entender como funciona uma tentativa, também entenderá como as expressões regulares funcionam. As tentativas são um caso especial de autômato finito determinístico (DFAs), em que ramificações são baseadas exclusivamente em comparações de bits e sempre ramificam para a frente. Um bom mecanismo de regex está apenas lidando com os DFAs com mais "recursos". Se minhas fotos fizerem sentido para você, as imagens deste excelente artigo sobre o algoritmo de redução NFA-DFA de Thompson também farão, e esse artigo fará com que você seja mais inteligente. 4)
Você é um operador de rede em um ISP de backbone. Seu mundo consiste basicamente de "prefixos" - pares de rede / máscara de rede IP. As máscaras de rede nesses prefixos são extremamente importantes para você. Por exemplo, 121/8 pertence à Coréia; 121.128 / 10 pertence à Korea Telecom, 121.128.10 / 24 pertence a um cliente KT e 121.128.10.53 é um computador dentro desse cliente. Se você está rastreando uma rede de bots ou uma operação de spam ou propagação de worms, esse número de máscara de rede é muito importante para você.
Infelizmente, por mais importantes que sejam, em nenhum lugar de um pacote IP está estampada uma “máscara de rede” - as máscaras de rede são inteiramente um detalhe de configuração. Portanto, quando você está assistindo o tráfego, tem esses dados para trabalhar:
ips.png
Surpreendentemente, dados os pacotes suficientes para examinar, essas informações são suficientes para adivinhar as máscaras de rede. Enquanto trabalhava na Sony, Kenjiro Cho criou uma maneira realmente elegante de fazer isso, com base em tentativas. Aqui está como:
Faça um radix binário básico, exatamente como os usados pelos roteadores de software. Mas vincule o número de nós na árvore, digamos a 10.000. Em um link de backbone, gravando endereços fora dos cabeçalhos IP, você esgotará 10.000 nós em instantes.
Armazene a lista de nós em uma lista, classificada em ordem LRU. Em outras palavras, quando você combinar um endereço IP com um nó, "toque" no nó, colocando-o no topo da lista. Gradualmente, os endereços frequentemente vistos borbulham até o topo e os nós raramente vistos afundam no fundo.
Figura 6.png
Agora o truque. Quando você ficar sem nós e precisar de um novo, recupere da parte inferior da lista. Mas quando você faz isso, role os dados do nó para o pai, da seguinte maneira:
Figura 5.png
10.0.1.2 e 10.0.1.3 são irmãos / 32s, as duas metades de 10.0.1.2/31. Para recuperá-los, mescle-os em 10.0.1.2/31. Se você precisar recuperar 10.0.1.2/31, poderá mesclá-lo com 10.0.1.0/31 para formar 10.0.1.0/30.
Faça isso por um minuto, por exemplo, e as fontes de destaque defenderão sua posição na árvore mantendo-se no topo da lista de LRU, enquanto o ruído ambiente / 32 borbulha até / 0. Para a lista bruta de IPs acima, com uma árvore de 100 nós, você obtém isso.
Cho chama isso de Aguri heurístico. 5)
A Aguri é licenciada em BSD. Você pode fazer o download e um programa de driver que assiste pacotes via pcap, na antiga página inicial de Cho. 6
Estou indo a algum lugar com isso, mas estou com 1300 palavras neste post agora, e se você é uma pessoa de algoritmos, já está cansado de mim e, se não estiver, está cansado de mim. agora. Então deixe a Aguri afundar, e eu lhe darei algo interessante e inútil para fazer com isso no final desta semana.
Existem inúmeros links espalhados por lá. Infelizmente, o Archive.org não mantém as imagens, apenas o texto; portanto, várias delas foram perdidas. Aqui estão os que ele arquivou:
