Lushu: Ofuscação de Dados Sigilosos via Reconhecimento de Linguagens a partir de Exemplos

• Alexander Holmquist UFMG
• Vitor Emanuel UFMG
• Fernando Pereira UFMG

Resumo

A construção de gramáticas para reconhecer sentenças a partir de exemplos é um problema que possui diversas aplicações práticas, incluindo a identificação e ciframento de informações sigilosas em sistemas computacionais. Técnicas atualmente em uso para resolver esse problema tendem a criar gramáticas muito grandes, com um número de símbolos terminais proporcional à quantidade de palavras nas sentenças de exemplo. Este artigo propõe uma técnica de fusão de terminais em expressões regulares. Tal técnica utiliza um reticulado construído a partir de um ordenamento parcial de expressões regulares. Tal reticulado, e o algoritmo de identificação de linguagens que ele enseja, foi utilizado para construir Lushu, uma ferramenta de proteção de dados pessoais que cifra informações sigilosas produzidas pela máquina virtual Java. Uma comparação entre Lushu e Zhefuscator, uma ferramenta de propósito similar, demonstra que a técnica proposta neste trabalho não somente é eficiente em termos de tempo, mas também de espaço, produzindo gramáticas até 10 vezes menores que o atual estado da arte.

Palavras-chave: Reconhecimento de Linguagem, gramáticas