Archive

Posts Tagged ‘automata de pilha’

Todos os IPs do mundo (2)

06/01/2009 Leave a comment

Depois de conhecermos as atualizações dos IPs atribuídos para todo o mundo (em 1), o problema é descobrir de forma automática da real alocação de um determinado IP e qual seu responsável. Por outro lado queremos saber (também de forma automática), se um domínio existe e a quem ele pertence.

Uma das mais importantes ferramentas da Internet para obter tais informações é o whois. Um bom começo está na referência [2]. Tamanha importância, em mesmo grau, equivalente desprezo ao whois por aqueles que governam a Internet, aparentemente. Vejam que a referência [2], não é atualizada desde 2004.

Um dos melhores clientes do whois, que tive oportunidade de experimentar foi o do FreeBSD (7.1). Provavelmente é equivalente a qualquer sistema baseado em Unix. Para ele ser eficaz é bom ter a relação final da referência [2].

Ao Itinera ad futurum, o que interssa é um procedimento automático. Portanto, usaremos o Net_Whois do Pear, como ilustração. A experiência é fantástica!

O Net_Whois, em sua versão 1.0 possui algumas deficiências. Cheguei a localizar duas. Uma delas já há uma sugestão para alterar e trata-se de permitir o uso da linha de comando do whois no Unix. A outra, é o fato dele trazer uma cadeia de caracteres com LF e CR. Se alguém precisar da tabela ASCII, um bom local é aqui, na Wikipedia. Vejamos uma cadeia de caracteres resultante do Net_Whois:


% Copyright (c) Nic.br % The use of the data below is only permitted as described in % full by the terms of use (http://registro.br/termo/en.html), % being prohibited its distribution, comercialization or % reproduction, in particular, to use it for advertising or % any similar purpose. % 2009-01-06 15:11:33 (BRST -02:00) domain: nic.br owner: Núcleo de Informação e Coordenação do Ponto BR ownerid: 005.506.560/0001-36 responsible: Demi Getschko country: BR owner-c: FAN admin-c: FAN tech-c: FAN billing-c: FAN nserver: a.dns.br nsstat: 20090106 AA nslastaa: 20090106 nserver: b.dns.br nsstat: 20090106 AA nslastaa: 20090106 nserver: c.dns.br nsstat: 20090106 AA nslastaa: 20090106 nserver: d.dns.br nsstat: 20090106 AA nslastaa: 20090106 nserver: e.dns.br nsstat: 20090106 AA nslastaa: 20090106 dsrecord: 57436 RSA/SHA-1 CCB7D717A8868B8739A78FEC8FB60E62EBE2D89B dsstatus: 20090106 DSOK dslastok: 20090106 created: 19970711 #46903 changed: 20070606 status: published nic-hdl-br: FAN person: Frederico Augusto de Carvalho Neves e-mail: fneves@registro.br created: 19971217 changed: 20030721 % Security and mail abuse issues should also be addressed to % cert.br, http://www.cert.br/, respectivelly to cert@cert.br % and mail-abuse@cert.br % % whois.registro.br accepts only direct match queries. Types % of queries are: domain (.br), ticket, provider, ID, CIDR % block, IP and ASN.

Esse é um resultado vindo do whois.nic.br, um dos mais consistentes whois do mundo.

Uma análise mais detalhada nos indica que % antecede um comentário. Há os chamados objetos do whois cujo conteúdo são apêndices de palavras chaves, tais como domain:, nsstat: e outras. Todas as palavras chaves terminam com um :. O conteúdo de um objeto termina quando começa um outro objeto ou com, novamente, o %. E, um comentário termina com o final da cadeia de caracteres. Quem sabe, o conteúdo de um objeto também termina com o final da cadeia.

Nosso objetivo é desenvolver um algorítmo para reconhecer o que é comentário, o que é objeto e seu respectivo conteúdo. Se pensarmos em um algorítmo para transformar a cadeia recebida pelo whois em algo organizado como o whois do Unix, o problema fica resolvido. Para ser mais claro, desejamos transformar a cadeia no seguinte texto organizado:


% Copyright (c) Nic.br
% The use of the data below is only permitted as described in
% full by the terms of use (http://registro.br/termo/en.html),
% being prohibited its distribution, comercialization or
% reproduction, in particular, to use it for advertising or
% any similar purpose.
% 2009-01-06 15:11:33 (BRST -02:00)
domain: nic.br
owner: Núcleo de Informação e Coordenação do Ponto BR
ownerid: 005.506.560/0001-36
responsible: Demi Getschko
country: BR
owner-c: FAN
admin-c: FAN
tech-c: FAN
billing-c: FAN
nserver: a.dns.br
nsstat: 20090106 AA
nslastaa: 20090106
nserver: b.dns.br
nsstat: 20090106 AA
nslastaa: 20090106
nserver: c.dns.br
nsstat: 20090106 AA
nslastaa: 20090106
nserver: d.dns.br
nsstat: 20090106 AA
nslastaa: 20090106
nserver: e.dns.br
nsstat: 20090106 AA
nslastaa: 20090106
dsrecord: 57436 RSA/SHA-1 CCB7D717A8868B8739A78FEC8FB60E62EBE2D89B
dsstatus: 20090106 DSOK
dslastok: 20090106
created: 19970711 #46903
changed: 20070606
status: published
nic-hdl-br: FAN
person: Frederico Augusto de Carvalho Neves
e-mail: fneves@registro.br
created: 19971217
changed: 20030721
% Security and mail abuse issues should also be addressed to
% cert.br, http://www.cert.br/, respectivelly to cert@cert.br
% and mail-abuse@cert.br
%
% whois.registro.br accepts only direct match queries. Types
% of queries are: domain (.br), ticket, provider, ID, CIDR
% block, IP and ASN.

Um programador habilidoso talvez faça um algoritmo desses em 1 dia. Um programador experiente, com formação em Ciência da Computação (ou Engenharia da Computação), levará algumas poucas horas para criar um algoritmo eficiente e elegante. A questão de eficiência no caso da proposta acima é irrelevante, pois a cadeia resultante do whois é muito pequena para a capacidade de computação de um PC atual. Mas a elegância e clareza do algoritmo são as questões importantes para o sistema no qual ele será utilizado. O programador habilidoso, sem os fundamentos teóricos do programador experiente, provavelmente achará o algoritmo muito difícil e, certamente, tornará o sistema do qual fará parte, ineficiente.

O programador experiente usará as técnicas da Teoria dos Autômatos. Em particular, o Autômato de Pilha. Uma procura no Google, com esse título trará inúmeros referências importantes. Aplicar Autômato de Pilha no problema que temos de resolver é um exercício fascinante, da arte de programar.

Eis o algoritmo em PHP+PEAR:


<?php
function imprimeLinhaEZeraPilha ($pilha) {
$pilha = array_reverse($pilha); // Pilha que vira um array.
$linha = ”;
while (count($pilha) > 0) {
$linha .= array_pop($pilha);
}
echo ‘<tr><td colspan=”2″><font face=”Courier new” size=”2″>’ . $linha . ‘</font></td></tr>’;
return $pilha; // retorna Pilha vazia
}

//

require_once “Net/Whois.php”;

$server = “whois.nic.br”;
$query = “nic.br”;

$whois = new Net_Whois;

// Verifica o whois
$data = $whois->query($query, $server);

// whois.nic.br: dominio
$objetos = array();
$objetos[0] = ‘nulo:’;
$objetos[1] = ‘domain:’;
$objetos[2] = ‘owner:’;
$objetos[3] = ‘ownerid:’;
$objetos[4] = ‘responsible:’;
$objetos[5] = ‘country:’;
$objetos[6] = ‘owner-c:’;
$objetos[7] = ‘admin-c:’;
$objetos[8] = ‘tech-c:’;
$objetos[9] = ‘billing-c:’;
$objetos[10] = ‘nserver:’;
$objetos[11] = ‘nsstat:’;
$objetos[12] = ‘nslastaa:’;
$objetos[13] = ‘dsrecord:’;
$objetos[14] = ‘dsstatus:’;
$objetos[15] = ‘dslastok:’;
$objetos[16] = ‘created:’;
$objetos[17] = ‘expires:’;
$objetos[18] = ‘changed:’;
$objetos[19] = ‘status:’;
$objetos[20] = ‘nic-hdl-br:’;
$objetos[21] = ‘person:’;
$objetos[22] = ‘e-mail:’;
$objetos[23] = ‘created:’;
$objetos[24] = ‘changed:’;

echo ‘<table border=”0″ align=”left” cellpadding=”0″ cellspacing=”1″>’;

$alvo1 = “%”;
$alvo2 = “:”;
$alvo3 = ” “;
$pilha = array();
$pilha_auxiliar = array();

$novo_alvo1 = false;
// Percorre cada elemento do string
while (strlen($data) > 0) {
$elemento = substr($data, 0, 1);
if (ord($elemento) == 10 || ord($elemento) == 13) {
$elemento = ‘ ‘;
}
array_push($pilha, $elemento);
$data = substr($data, 1);
switch ($elemento) {
case $alvo1:
if (!$novo_alvo1) {
$novo_alvo1 = true;
if (count($pilha) > 1) {
array_pop($pilha);
$pilha = imprimeLinhaEZeraPilha ($pilha);
array_push($pilha, $elemento);
}
} else {
array_pop($pilha);
$pilha = imprimeLinhaEZeraPilha ($pilha);
array_push($pilha, $elemento);
$novo_alvo1 = false;
}
break;
case $alvo2:
// Desempilha o : e tudo que segue até um branco, empilhando na pilha auxiliar
$elemento = array_pop($pilha);

while (ord($elemento) !== ord (‘ ‘) && count($pilha) > 0) {
array_push($pilha_auxiliar, $elemento);
$elemento = array_pop($pilha);
}
// Monta string com o suposto objeto
$objeto = ”;
while (count($pilha_auxiliar) > 0) {
$objeto .= array_pop($pilha_auxiliar);
}
if (!array_search($objeto, $objetos)) {
// Não é um objeto, então, devolve para a pilha e continua
array_push($pilha, $elemento); // Empilha o branco antes % 2008-12-14 08:56:44 (BRST -02:00)
while (strlen($objeto) >= 1) {
$elemento = substr($objeto, 0, 1);
$objeto = substr($objeto, 1);
array_push($pilha, $elemento);
}
} else {
// É um objeto, então imprime a pilha e segue em frente após empilhar tudo que está na pilha auxiliar
$pilha = imprimeLinhaEZeraPilha ($pilha);
while (strlen($objeto) > 0) {
$elemento = substr($objeto, 0, 1);
$objeto = substr($objeto, 1);
array_push($pilha, $elemento);
}
}
break;
}
}
if (count($pilha) > 0) {
$pilha = imprimeLinhaEZeraPilha ($pilha);
echo ‘<tr><td colspan=”2″><font face=”Courier new” size=”2″> </font></td></tr>’;
}
echo ‘</table>’;
?>

Categories: TCP/IP, Whois Tags: , , , , ,