Google Treasure Hunt 3: Busca em Profundidade (Depth-First Search)

Esse é outro problema do Google Treasure Hunt que eu resolvi. Esse foi o mais fácil de todos, e realmente não era necessário nenhum conhecimento de programação. Tenha-se em mente apenas que o não uso de programação para resolvê-lo não é de modo algum divertido! Tente ensinar seu computador a fazê-lo por você… O problema que eu obtive no Google foi o seguinte:

“Below is a diagram of a computer network. The nodes are hosts on the network, and the lines between them are links. A packet is sent out from host P with a destination of 4.229.231.150. Which nodes does the packet pass through on its way to the destination? (include start and final node in your answer)”

O diagrama para o modelo da rede acima foi fornecido na forma da tabela de roteamento a seguir:

“

A 26.40.28.17 75.174.216.140 => 126.186.188.58 26.40.28.17 => 17.100.195.84 4.229.231.0/24 => 75.174.216.140 13.157.234.26

B 13.157.234.26 76.246.145.72 => 53.12.68.161 126.186.188.58 => 75.174.216.140 53.12.68.0/24 => 26.40.28.17 17.100.195.84

C 53.12.68.161 75.174.216.140 => 219.88.219.35 229.23.61.42 => 13.157.234.26 17.100.195.0/24 => 103.19.57.145 126.186.188.58

D 103.19.57.145 86.60.122.237 => 86.60.122.237 117.146.177.141 => 53.12.68.161 229.23.61.0/24 => 219.88.219.35 212.222.1.12

E 4.229.231.150 4.229.231.150 => 103.19.57.145 54.35.7.207 => 54.35.7.207 126.186.188.0/24 => 199.223.210.72 229.23.61.42

F 54.35.7.207 4.229.231.150 => 229.23.61.42 13.157.234.26 => 199.223.210.72 26.40.28.0/24 => 4.229.231.150 86.60.122.237

G 86.60.122.237 229.23.61.42 => 54.35.7.207 13.157.234.26 => 103.19.57.145 103.19.57.0/24 => 212.222.1.12 219.88.219.35

H 212.222.1.12 126.186.188.58 => 219.88.219.35 75.174.216.140 => 86.60.122.237 103.19.57.0/24 => 103.19.57.145 229.23.61.42

I 229.23.61.42 4.229.231.150 => 4.229.231.150 117.146.177.141 => 54.35.7.207 126.186.188.0/24 => 199.223.210.72 212.222.1.12

J 199.223.210.72 53.12.68.161 => 229.23.61.42 4.229.231.150 => 54.35.7.207 219.88.219.0/24 => 219.88.219.35 4.229.231.150

K 219.88.219.35 4.229.231.150 => 199.223.210.72 17.100.195.84 => 212.222.1.12 126.186.188.0/24 => 86.60.122.237 103.19.57.145

L 117.146.177.141 4.229.231.150 => 219.88.219.35 117.146.177.141 => 126.186.188.58 26.40.28.0/24 => 76.246.145.72 75.174.216.140

M 75.174.216.140 199.223.210.72 => 13.157.234.26 4.229.231.150 => 117.146.177.141 126.186.188.0/24 => 17.100.195.84 26.40.28.17

N 17.100.195.84 4.229.231.150 => 26.40.28.17 219.88.219.35 => 13.157.234.26 17.100.195.0/24 => 75.174.216.140 76.246.145.72

O 76.246.145.72 4.229.231.150 => 17.100.195.84 86.60.122.237 => 126.186.188.58 13.157.234.0/24 => 53.12.68.161 117.146.177.141

P 126.186.188.58 13.157.234.26 => 53.12.68.161 4.229.231.150 => 76.246.145.72 103.19.57.0/24 => 26.40.28.17 117.146.177.141

”

Como você talvez tenha suposto, o primeiro símbolo é o ID do nó de rede, seguido por seu número IP. A seguir, você tem uma sequência de 3 regras de roteamento, o nó pode ver se essa regra em específico serve para o pacote entrante (incoming packet, ou pacote de rede no estágio de ingresso ao roteador). O ultimo número IP nos dá a rota padrão (“default route”), apenas no caso em que esse nó não encontrou nenhuma regra de roteamento que coubesse para um dado pacote (a rota padrão é como um “else” após uma sequência de “IF”s...).No caso do pacote chegar à rota padrão, esse pacote será direcionado para o host definido pelo endereço IP na última coluna da tabela acima.

Criei uma solução em C++, que usa um método de busca em profundidade para buscar por um caminho válido saindo de um dado nó para outro no modelo de rede do problema. Minha idéia foi fazer a função de busca em profundidade (em ingles, “depth-first search”) andar de nó em nó (nós são rotulados como: A, B, C, etc.), iterando sobre cada uma das regras da tabela de roteamento, e procurando por cada uma dessas regras que possa rotear adequadamente o pacote através da rede. A função abaixo é auto-explicável:

“

bool RoutingTable::routeTo( string node, string* resp )

{

bool do_it_again = true;

RoutingEntry rentry = findRouteEntry( node );

if ( rentry.doneThis() )

return false;

resp->append( rentry.getId() );

if ( rentry.getAddress().compare(getFinalDestination()) == 0 ) {

return false;

}

vector<RoutingRule> routing_rules = rentry.getRules();

vector<RoutingRule>::iterator i;

rentry.markThis(true);

// go through each of the routing rules

for ( i = routing_rules.begin(); ( i != routing_rules.end() ) &&

do_it_again; i++ )

{

if ( (*i).canRoute(getFinalDestination()) ) {

do_it_again = routeTo( (*i).getRedirection(), resp );

} // if

} // for

rentry.markThis(false);

// no rules; asks the default gateway…

if ( do_it_again )

{

do_it_again = routeTo( rentry.getDefaultRoute().getRedirection(),

resp );

}

return do_it_again;

}

”

Nessa solução usei apenas a STL do C++, ou C++ Standard Template Library (STL). Todos os nós são armazenados em estruturas como elementos de um vector, e são localizadas por símbolos de ID (A, B, C, etc.), ou por números IP (método findRouteEntry()). Cada nó tem a sua própria estrutura “Rules” (que você pode obter chamando getRules()). Uma vez processadas, cada uma dessas regras pode apontar para um outro nó da tabela, e a função routeTo pode atuar de forma recursiva sobre uma dada regra. Se nenhuma regra suficiente para combiner com o pacote for encontrada, a função routeTo é chamada sobre o nó retornado pela chamada a “getDefaultRoute”:

“

// no rules; asks the default gateway…

if ( do_it_again )

{

do_it_again = routeTo( rentry.getDefaultRoute().getRedirection(),

resp );

}

“

As chamadas para a função markThis() são para evitar recursões infinitas (iterar sobre os mesmos nós, de uma forma circular e muitas vezes irreversível, levando ao esgotamento de recursos computacionais). A semântica é simples: markThis(true), quando o código precisar entrar numa “regão crítca”, e markThis(false) quando tiver saído da região crítica.

Você conseguiria encontrar a diferença entre o método de roteamento que eu formulei para o que é implementado por roteadores de rede de verdade (de fabricantes como Cisco)? Talvez meus posts anteriores com questões da certificação CCNA da Cisco possam ajudar...

Access Control Lists - ACLs

Tópicos que tem ocorrido com mais freqüência são aqueles relacionados com segurança, apesar de ser um assunto mais freqüente em exames mais avançados como o CCNP e o CCIE. Na questão abaixo, um exemplo básico com Access Control Lists (ACLs), retirado do livro “CCNA Study Guide, Sixth Edition”, do Todd Lammle:

“You configure the following access list:

access-list 110 deny tcp 10.1.1.128 0.0.0.63 any eq smtp

access-list 110 deny tcp any eq 23

int ethernet 0

ip access-group 110 out

What will the result of this access list be?

A. Email and Telnet will be allowed out E0.

B. Email and Telnet will be allowed in E0.

C. Everything but email and Telnet will be allowed out E0.

D. No IP traffic will be allowed out E0.”

Na questão, uma lista de comandos do roteador é apresentada, e pede-se o resultado da execução de tal lista num roteador hipotético. Aqui deve-se ter sempre em mente uma interpretação recorrente nas provas da Cisco: que o que não constar da relação de comandos, presume-se que foi omisso. Ou melhor, a lista de comandos começa exatamente com a primeira sentença de “access-list ...”, e termina com “ip access-group 110 out”. O trecho então não é parte de uma entrada do administrador de rede, mas sim uma sequência completa e indivisível de comandos.

Os comandos de access-lists na questão acima são no formato “extended”, ou seja, são no formato que começa com a definição da ação (“deny” ou “permit”), o intervalo de hosts de origem, o intervalo de hosts destino e, possivelmente, condições que especificam em que porta a restrição vai se impor. As listas extended são numeradas com identificadores de 100 a 199, e com elas é possível filtrar pacotes por campos IP de camada 3 e até alguns serviços de camada 4 ou maior (WWW, Telnet, SMTP, etc.), o que amplia o espectro de usos possíveis para as ACLs, como por exemplo mitigar ataques Denial-of-Service (DoS), DoS Smurfs, IP Spoofing, etc. É possível estabelecer regras que serão aplicadas especificamente a pacotes TCP com a flag SYN setada, por exemplo, o que serve de ajuda contra ataques de SYN flood. Certo, apenas “mitigar”, não necessariamente impedir tais ataques, dada a dificuldade em definir regras sobre grupos de pacotes suspeitos num universo tão grande de possibilidades de ataques. Mas a utilidade das ACLs ainda assim é muito bem vinda e quebra alguns galhos.

Quando é preciso definir regras que se apliquem a apenas um par de hosts, como a sentença “access-list 110 deny ip host 172.16.10.3 host 172.16.20.5”, por exemplo, que bloqueia pacotes IP com campo de origem 172.16.10.3 e destino para 172.16.20.5, a tarefa é imediata. Contudo, é mais comum, na definição das regras de ACLs, quando é necessário que sejam aplicadas regras a um intervalo de hosts numa sub-rede, pode-se recorrer aos wildcards. Vamos dizer que queiramos aplicar determinada regra ao conjunto de hosts nas sub-redes de 192.168.113.0 até 192.168.140.0. Primeiro, calcule quantas sub-redes existem entre os endereços anteriores; diminuindo 113 de 140 (140 – 113), obtemos 27. Agora é preciso achar uma potência de 2 que seja maior ou igual a esse intervalo; temos que 32 é maior que 27 (16 é outra potência de 2, mas é menor que 27), e portanto nos serve para esse propósito. Esse valor é 32 é o tamanho do bloco, e quando diminuído de 1, nos traz o endereço de wildcard. Nesse caso, temos que o endereço de wildcard para esse intervalo é 0.0.31.255. O terceiro octeto, que guarda informações das sub-redes onde serão aplicadas a regra de ACL, tem valor 31, representado um bloco de 32 (192.168.113.0 até 192.168.145.0). Esse intervalo é maior do que o que o intervalo que queremos, mas serve ao propósito. O quarto octeto contêm um valor de 255, que permite a presença de qualquer valor, e nos garante que todos os hosts nessas sub-redes sejam também contemplados com a regra ACL.

De volta à questão, a primeira sentença aplica a regra de que será descartado qualquer pacote SMTP (porta 25) com origem em quaisquer dos hosts em 10.1.1.128 até 10.1.1.192 (wildcard = 0.0.0.63, bloco igual a 64). A segunda regra descarta todos os pacotes com destino ao serviço de Telnet (porta 23). Logo a seguir, essas 2 regras são aplicadas à interface E0 (ethernet0) para saída (“out”), ou seja, em “post-routing”, após o pacote ter sido roteado localmente no roteador e estar prestes a ser encaminhado para a interface de saída, as regras são aplicadas. A princípio, até aí tudo bem, temos 2 regras, uma que nega totalmente serviços para a porta 23, e outra que nega serviço SMTP (porta 25) para um conjunto de hosts. A alternativa C parece convidativa, mas algo vai errado na lista de acesso: se era esse o fim almejado pelo administrador (negar pacotes para serviços portas 23 e 25), ele deveria ter incluído a regra “permit ip any” no final da lista de acesso, porque a última regra é “deny ip any”, o que faria com que qualquer pacote tivesse o repasse concedido pela interface ethernet0. Devido à omissão dele, a interface E0 vai perder comunicação com o mundo. Alternativa D é a correta.