Back-End

27 jul, 2016

URL Detector – uma biblioteca Java para detectar e normalizar URLs em texto

Publicidade

URL-detector-1

Estamos animados em compartilhar que o LinkedIn abriu o código da nossa biblioteca Java URL-Detector. O LinkedIn verifica centenas de milhares de URLs de malware e phishing a cada segundo. A fim de garantir que os nossos membros tenham uma experiência de navegação segura, todo o conteúdo gerado pelo usuário é verificado por um serviço de backend quanto a conteúdo potencialmente perigoso. Como pré-requisito para que sejamos capazes de verificar URLs de conteúdo ruim nessa escala, é preciso ser capaz de extrair URLs de texto em escala.

URLs são enviadas para o nosso serviço de duas maneiras diferentes:

  • Como uma única URL
  • Como um grande pacote de texto

Se ela é enviada como uma única URL, passamos a verificar a URL através do nosso serviço de conteúdo de validação. Se ela é enviada como um grande pacote de texto, executamos o nosso algoritmo URL-Detector para tentar procurar no texto por quaisquer URLs potenciais. Antes de prosseguir com a checagem de como o URL-Detector funciona e o que ele pode proporcionar de funcionalidades, vamos conhecer a motivação por trás desse projeto.

Queremos detectar o maior número de links maliciosos quanto possível e, para isso, não queremos nos limitar a verificação de URLs conforme definido na RFC 1738; em vez disso, definimos uma URL para ser qualquer coisa que pode trazer um site real quando digitado na barra de endereço de um navegador. A definição de URL da barra de endereço do navegador é muito vaga enquanto o RFC é muito restrito. E, claro, há muitos navegadores e navegadores diferentes têm comportamentos diferentes, por isso tentamos encontrar texto que iriam funcionar nos mais populares. Assim, não é tão simples como seguir a gramática definida na RFC.

Inicialmente, começamos com uma solução baseada em expressões regulares. Ela detectou muitas URLs potenciais, muitas das quais eram URLs com intenções reais, muitas não eram, e muitas eram perdidas. Foi um processo muito iterativo para pegar mais URLs. Seria começar com algo tão inocente como:

Regex:
(ftp|http|https):\/\/(\w+:{0,1}\w*@)?(\S+)(:[0-9]+)?(\/|\/([\w#!:.?+=&%@!\-\/]))?

Então, e se você quisesse detectar URLs que não contêm um esquema? Este é um dos muitos exemplos em que uma URL funciona em uma barra de endereço do navegador e que não se encaixa no RFC.

Regex:
((ftp|http|https):\/\/)?(\w+:{0,1}\w*@)?(\S+)(:[0-9]+)?(\/|\/([\w#!:.?+=&%@!\-\/]))?

Nós acabamos com esta bagunça:

Regex:
((((f|ht)tps?:)?//)?([a-zA-Z0-9!#$%&'*+-/=?^_`{|}~]+(:[^ @:]+)?@)?((([a-zA-Z0-9\\-]{1,255}|xn--[a-zA-Z0-9\\-]+)\\.)+(xn--[a-zA-Z0-9\\-]+|[a-zA-Z]{2,6}|\\d{1,3})|localhost|(%[0-9a-fA-F]{2})+|[0-9]+)(:[0-9]{1,5})?([/\\?][^ \\s/]*)*)

Como você pode ver, cada caso pequeno acrescenta pelo menos mais alguns caracteres ao regex. Você pode ver o quão complicado esse tema pode ficar aqui. (Aviso: algumas dessas expressões regulares têm mais de 5500 caracteres.) Nós descobrimos que muitas dessas URLs potenciais detectadas eram tecnicamente URLs, mas o resultado não foi muito útil para nós. Quanto mais flexível tornávamos o nosso Regex, mais falsos positivos encontrávamos; quanto menos flexível, mais falsos negativos perdíamos. Por exemplo, encontrávamos “URLs” como “1.2”. Encontrar mais URLs do que precisávamos colocava estresse desnecessário no nosso sistema.

À medida que fomos encontrando muitas correspondências, a abordagem que adotamos para reduzir o número de correspondências era tentar encontrar falsos positivos dentro de nossas correspondências. Editar a expressão regular original havia comprovado ser extremamente difícil sem a introdução de ainda mais falsos positivos. Portanto, precisávamos de múltiplas expressões regulares. Aqui está um exemplo de uma das expressões regulares extras que precisávamos para a exclusão de “localhost” e qualquer combinação de dígitos separados por pontos, exceto para aqueles na forma de um endereço IPv4.

Blacklisted Regex: ^((\\d+(\\.\\d+){0,2})|(\\d+(\\.\\d+){4,})|localhost)$

O resultado é que a análise de grandes pedaços de texto começou a demorar muito tempo, mesmo na ordem de segundos. Em um sistema em que nós estamos tentando analisar centenas de milhares de URLs por segundo, essa solução não pode ser escalada. Descobrimos que as expressões regulares são boas para achar a correspondência, mas não para a análise. E, assim, chegamos à biblioteca URL-Detector.

Em vez de usar expressões regulares, nós construimos uma máquina de estados finitos para analisar as URLs no texto. A máquina de estados finitos é um sistema que consiste em um conjunto de estados em que cada estado pode fazer a transição para outros estados, dependendo do evento de entrada. Nesse caso, o evento de entrada é o caractere corrente no texto que está sendo analisado. Você pode aprender mais sobre ele aqui.

URL-detector-2

Essa máquina de estados finitos tem alguns estados, baseados principalmente nas partes de uma URL. O estado é mantido por uma série de variáveis booleanas, mudando de estado para estado, consumindo um caractere de cada vez. Felizmente para o desempenho, essa máquina de estados finitos é representada por uma ordenação topológica, onde não existem setas de um estado que apontam para um estado anterior. Um exemplo disso é que, se você já tiver detectado o “/” após o host, ele não precisa mais tentar detectar isso, já que é passado desse ponto. Se em algum momento a máquina de estado atinge um caractere inesperado, ele irá retornar com o mais recente estado final possível e reiniciar o algoritmo. A parte mais complicada disso está em combinar caracteres que realmente têm a possibilidade de estar em vários estados. Um exemplo disso seriam os dois pontos. Eles podem aparecer em pelo menos três lugares: após o scheme, entre o nome de usuário e a senha, e entre o host e a porta. Eles ficam ainda mais complexos quando começamos a considerar IPv6, uma vez que os endereços IPv6 também incluem dois pontos. Retrocesso acontece principalmente em alguns casos estranhos, como quando o texto contém uma sequência de caracteres não-espaço em branco contendo múltiplos dois pontos, ao passo que as expressões regulares recuam muito frequentemente. Assim, o tempo de execução média é significativamente melhorado.

Aqui estão algumas estatísticas sobre a melhoria do desempenho:

URL-detector-3

Funcionalidades dessa biblioteca

Ela é capaz de encontrar e detectar quaisquer URLs, tais como:

  • HTML 5 Scheme – //www.linkedin.com
  • Nomes de usuários – user:pass@linkedin.com
  • E-mail – fred@linkedin.com
  • IPv4 Address – 192.168.1.1/hello.html
  • IPv4 Octets – 0x00.0x00.0x00.0x00
  • IPv4 Decimal – http://123123123123/
  • IPv6 Address – ftp://[::]/hello
  • IPv4-mapped IPv6 Address – http://[fe30:4:3:0:192.3.2.1]/

Como um bônus adicional, ela também é capaz de identificar as partes das URLs identificadas. Por exemplo, para a URL http://user@example.com:?39000/hello?boo=ff#frag, é capaz de identificar as seguintes partes:

  • Scheme – “http”
  • Nome de usuário – “user”
  • Senha – null
  • Host – “example.com”
  • Port – 39000
  • Path – “/hello”
  • Query – “?boo=ff”
  • Fragment – “#frag”

Ela também é capaz de lidar com aspas e entrada HTML. Dependendo da sua string de entrada, você pode querer lidar com certos caracteres de uma maneira especial. Por exemplo, se você estiver analisando HTML, provavelmente vai querer identificar coisas como aspas e colchetes. Por exemplo, se a sua entrada se parece com:

<a href=”http://linkedin.com/abc”>linkedin.com</a>, então você provavelmente vai querer se certificar de que as aspas e os sinais de maior e menor serão extraídos. Por essa razão, essa biblioteca tem a capacidade de alterar o nível de sensibilidade de detecção com base no seu tipo de entrada esperado, funcionando em diferentes modos, conforme especificado na classe java UrlDetectorOptions. Dessa forma, você pode detectar linkedin.com em vez de linkedin.com</a>.

Usando a biblioteca

Para usar essa biblioteca, basta clonar o repositório GitHub e importar a biblioteca do URL-Detector. Aqui está um exemplo de como você pode usá-la:

   import com.linkedin.urls.detection.UrlDetector;
   import com.linkedin.urls.detection.UrlDetectorOptions;
   ...
   UrlDetector parser = new UrlDetector("hello this is a url Linkedin.com", UrlDetectorOptions.Default);
    List<Url> found = parser.detect();

    for(Url url : found) {
        System.out.println("Scheme: " + url.getScheme());
        System.out.println("Host: " + url.getHost());
        System.out.println("Path: " + url.getPath());
    }

Para mais informações, dê uma olhada na sessão “How to Use” do Readme.

Agradecimentos

Um agradecimento especial a Vlad Shlosberg e Yulia Astakhova pela contribuição frequente para essa biblioteca.

Conclusão

Deixe-nos saber através do GitHub se existem quaisquer melhorias que podemos fazer nessa biblioteca. Além disso, fique à vontade para entrar em contato com qualquer um de nós se você tiver quaisquer pergunta. Nós adoraríamos saber como você está usando esta biblioteca. Tenha uma feliz detecção!

***

Tzu-Han Jan é o autor do artigo. A tradução foi feita pela redação iMasters, e você pode acompanhar o artigo em inglês no link: https://engineering.linkedin.com/blog/2016/06/open-sourcing-url-detector–a-java-library-to-detect-and-normali