CCM0128 - Computação II (2022i)

Leia inicialmente o Creative Exercise 4.4.8 (IP lookup by country) em

https://introcs.cs.princeton.edu/python/44st/

Este enunciado é para a versão Python "do livro azul" (IntroCS).  Em nosso contexto, basta interpretar "dict" que aparece nesse enunciado como sendo "ST.java".

Em vez do arquivo ip-by-country.csv do enunciado acima, você deve usar o arquivo dbip-city-lite-2020-05.IPv4.csv (que tem 3027054 linhas), acessível em

https://www.ime.usp.br/~yoshi/DATA/CSVs/dbip-city-lite-2020-05.IPv4.csv

Este arquivo foi produzido a partir de um arquivo livremente acessível em https://db-ip.com/db/lite.php

O objetivo desse exercício é escrever um sistema como segue.  Suponha que temos um conjunto de números IP, e que queremos saber onde estão as máquinas correspondentes.  Essas informações podem ser lidas do arquivo dbip-city-lite-2020-05.IPv4.csv.

Por exemplo, considere os 10 IPs no arquivo 10IPs.in (abaixo). Queremos escrever um programa, chamado IPLookUp.java, que poderia ser usado assim:

$ java-algs4 IPLookUp DATA/dbip-city-lite-2020-05.IPv4.csv < DATA/10IPs.in
Time to produce geolocator: 17.718
Time to produce unordered summary: 0.006
Time to order the summary: 0.023
       4: US, Washington, Redmond (47.674, -122.122)
       2: US, District of Columbia, Washington D.C. (38.9072, -77.0369)
       1: US, Virginia, Ashburn (39.0438, -77.4874)
       1: FR, Hauts-de-France, Roubaix (50.6916, 3.20026)
       1: DE, Bavaria, Nuremberg (49.452, 11.0767)
       1: BR, Pernambuco, Ribeirão (-8.51444, -35.3778)
$

A ideia é que estamos interessados em saber onde estão as máquinas com os IPs em 10IPs.in, e queremos saber quais localizações são mais frequentes. A saída acima está ordenada em ordem decrescente de ocorrências: 4 dos IPs são de Redmond, 2 deles são de Washington D.C., etc. Os números entre parênteses são as coordenadas (latitude e longitude) do local.

Exemplos de uso de IPLookUp.java. O arquivo

https://www.ime.usp.br/~yoshi/DATA/IPs/accessips

contém os IPs das máquinas que visitaram alguma página de www.ime.usp.br, com a informação de data e hora de acesso (este arquivo cobre algo como 5 dias e tem 1511712 linhas). Você pode obter desse arquivo os IPs contidos nas linhas usando o programa Filter.java. O arquivo assim obtido pode ser usado como entrada de IPLookUp.java:

$ java-algs4 Filter < DATA/accessips | java-algs4 IPLookUp DATA/dbip-city-lite-2020-05.IPv4.csv > accesses.out
Time to produce geolocator: 14.714
Time to produce unordered summary: 63.15
Time to order the summary: 0.431
$

O arquivo

https://www.ime.usp.br/~yoshi/DATA/IPs/ssh.log

contém tentativas inválidas de acesso à máquina machine.ime.usp.br (crackers tentando invadir esta máquina). Você pode fazer o seguinte, para saber de onde vêm esses ataques:

$ java-algs4 Filter2 < DATA/ssh.log | java-algs4 IPLookUp DATA/dbip-city-lite-2020-05.IPv4.csv > ssh.out
Time to produce geolocator: 15.75
Time to produce unordered summary: 0.384
Time to order the summary: 0.106
$

O programa IPLookUp.java. O programa IPLookUp.java está disponível abaixo. Ao estudá-lo, você verá que o trabalho principal é feito na construção de um objeto do tipo GeoLocator e nas chamadas do método location(), implementado em GeoLocator.

Seu trabalho principal é escrever GeoLocator.java. A API de GeoLocator.java deve ser como segue.

public class GeoLocator
----------------------------------------------------------------------
GeoLocator(String filename) ... constrói um geolocator lendo dados de filename
Location location(String q) ... devolve a localização do IP q

A classe Location.java é dada abaixo.

Leitura do arquivo dbip-city-lite-2020-05.IPv4.csv. As linhas desse arquivo devem ser lidas uma a uma, e cada linha deve ser "interpretada", para se montar o geolocator. Para tanto, você precisará quebrar cada linha nas oito partes que a constituem. Para tanto, você deve escrever uma classe separada, chamada TokenFinder.java. A API de TokenFinder.java deve ser como segue.

public class TokenFinder
----------------------------------------------------------------------
TokenFinder(String line) ... constrói um tokenfinder a partir de line
String nextToken()       ... devolve o próximo item

Um exemplo de uso de TokenFinder.java é o programa TFClient.java, dado abaixo. Veja também os arquivos 10.txt, 10.out, 13.txt e 13.out envolvidos nas execuções

$ java-algs4 TFClient < DATA/10.txt > 10.out
$ java-algs4 TFClient < DATA/13.txt > 13.out

de TFClient.java. Para você escrever TokenFinder.java, você pode inspirar-se em Words.java, visto em sala.

Programas auxiliares. Alguns programas auxiliares são fornecidos abaixo. Estude-os e use-os.

Desempenho. O tempo de execução de seu programa será comparado com os tempos de execução nos arquivos ssh.out e accesses.out dados abaixo. Experimente usar ST.java e RedBlackBST.java.

Entrega. Note que você deve entregar apenas dois arquivos: GeoLocator.java e TokenFinder.java. Nesses programas, use a implementação de tabelas de símbolos ST.java.

Note que os arquivos 10.out, 13.out, ssh.out e accesses.out produzidos pelo seu sistema devem ser idênticos aos arquivos fornecidos abaixo.

Acurácia.  As informações em dbip-city-lite-2020-05.IPv4.csv têm um certo nível de imprecisão e mesmo erros. Você pode pegar arquivos mais novos (ou pagos :-) em https://db-ip.com/db/lite.php, que podem ser melhores.