RT: tipos regulares para o shell de streaming

Título original: RT: Regular Types for the Streaming Shell

Publicado20th USENIX Symposium on Operating Systems Design and Implementation (OSDI 26)

Saiu em uma revista, congresso ou livro, que normalmente avaliam o trabalho antes de aceitar. Mesmo assim, um único estudo nunca é a palavra final.

Resumo

Este paper não tem resumo disponível.

Análise de pesquisa

Escrita pelo Kurz, não pelos autores do paper. O resumo acima é dos próprios autores.

Última revisão
Versão
1.0

Visão geral

Programas shell combinam comandos escritos em muitas linguagens que conversam por fluxos de bytes sem tipos, então um pipeline pode parecer certo e mesmo assim alimentar um estágio com linhas que ele não sabe tratar. As consequências vão de um trabalho longo que trava a uma corrupção silenciosa, e as ferramentas usuais só as descobrem depois da execução. As linguagens de programação modernas pegam esses erros com tipos, com checagens rápidas antes da execução, erros que o desenvolvedor vê em vez do usuário e contraexemplos, e o shell não tem nada disso. Um linter do estado da prática como o ShellCheck casa sintaxe e não modela o que os fluxos contêm.

Os autores, da Brown University e da Rice University, apresentam o RT, um sistema de tipos sobreposto, isto é, um verificador posto sobre o shell POSIX existente e não uma linguagem nova, para programas ou fragmentos shell cuja correção depende da estrutura em nível de linha dos fluxos entre os comandos. O exemplo corrente é uma versão moderna do clássico one-liner de frequência de palavras de McIlroy, que conta palavras escritas corretamente em todos os arquivos de livros sob o diretório atual. Ele falha com um erro de que alguns arquivos não existem e não imprime nada, e o ShellCheck fica em silêncio. O RT, em 0,02 segundo, descobre que a saída do grep pode ser incompatível com o xargs cat, dando uma linha de testemunho com um espaço no nome do arquivo, que o xargs divide em dois argumentos, e, depois de ler o dict.txt para calcular um tipo preciso, que os padrões do dicionário nunca podem casar porque um tr com os argumentos trocados põe as palavras em maiúsculas em vez de minúsculas.

Este artigo do OSDI 2026, vice-campeão do Best Paper, apresenta o sistema de tipos, seu algoritmo de verificação, extensões que o mantêm regular e uma avaliação em centenas de programas.

Termos para não confundir: tipo de fluxo regular é uma linguagem regular, escrita como expressão regular estendida, que descreve os conteúdos possíveis de cada linha, tipo de comando pareia um tipo de fluxo de entrada e um de saída (por exemplo find . tem ε → \.(/.+)?), um tipo é correto (sound) se aceita todo conteúdo possível e preciso se aceita só conteúdos que podem ocorrer, testemunho de contraexemplo é uma linha que o comando anterior pode produzir e que o comando seguinte não aceita, e transdutor de estados finitos é um autômato que também emite saída e permite calcular sobre linguagens uma operação de tipo como traduzir caracteres.

Vale conhecer antes: linguagens regulares, DFAs e NFAs e a decidibilidade da inclusão de linguagens, e como o shell move bytes por pipes. Dois artigos irmãos do mesmo grupo tratam outros lados do shell. O Ahead-of-Time Analysis of Shell Program Effects analisa os efeitos de um script por execução simbólica, e o Controlling Opaque-Component Effects with Semisolates and Try os controla em tempo de execução. O RT trabalha sobre o que flui pelos pipes, e por isso consegue pegar um pipeline que calcula os caminhos errados a apagar sem modelar a remoção.

Contribuição

  • Tipos regulares. Os tipos de fluxo são expressões regulares estendidas (um superconjunto da ERE do POSIX com interseção & e negação !), sem lookaround nem retrorreferências, para que a inclusão de linguagens continue decidível. Um pipeline é bem tipado quando a linguagem de saída de cada estágio está contida na linguagem de entrada do seguinte. A restrição é deliberada: nem todo comportamento pode ser representado, em troca de uma checagem tratável e de uma interface que os desenvolvedores Unix já conhecem.
  • Tipos de comando e um banco de tipos. Um tipo de comando pareia tipos de entrada e de saída, e o banco é um conjunto de arquivos de configuração escritos à mão que dizem como interpretar uma invocação e como construir seu tipo, por exemplo a partir do padrão do grep. Comandos de ordem superior como xargs cat são tratados como um comando só, e comandos desconhecidos recebem .* → .*. O banco pode ser inspecionado e editado com o comando rti.
  • Tipos de comando polimórficos. Os tipos podem ter uma variável de tipo, como ∀α. α → α para o cat, e um limite, como no sort -n, que copia a entrada mas espera que cada linha comece com dígitos. O RT instancia o tipo único mais preciso para a entrada real antes de checar, então as checagens continuam sobre tipos simples.
  • O algoritmo de verificação. Para cada estágio ele obtém o tipo do comando, checa que o tipo de fluxo atual está contido no tipo de entrada, reporta uma incompatibilidade com um contraexemplo e, caso contrário, calcula o tipo de saída. Ele se generaliza de pipelines para grafos acíclicos dirigidos de comandos em ordem topológica.
  • Operadores composicionais sobre transdutores. Operações como reverse, translate-match (para a substituição do sed), line-extract, translate-chars (para o tr, com squeeze) e field-select (para o cut) são calculadas construindo um transdutor de estados finitos e compondo-o com o autômato da entrada. Transdutores determinísticos dão resultados precisos para field-select e translate-chars, os não determinísticos funcionais cobrem casos especiais de casamento e os não determinísticos gerais são corretos mas podem superaproximar. Uma aproximação ingênua com operações padrão pode ser incorreta, como modelar tr -s ' ' com uma negação, que subaproxima sua saída.
  • Extensões opcionais. A concretização lê arquivos de entrada e variáveis de ambiente disponíveis no momento da análise para calcular um tipo preciso, depois de uma passagem normal. Cinco anotações em comentários (@assume, @input, @assert, @expect, @output) permitem ao desenvolvedor declarar entradas desconhecidas ou saídas esperadas. Quatro heurísticas sinalizam composições bem tipadas mas provavelmente erradas: um estágio com tipo de saída vazio, entrada dada a um comando que não espera nenhuma, como o echo, um estágio que não pode alterar o fluxo e um sort lexicográfico sobre entrada numérica.
  • Implementação. Construído sobre a biblioteca dk.brics.automaton (o ambiente de avaliação lista OpenJDK 17 e Python 3.10), com licença MIT junto com todos os benchmarks.

Metodologia

O benchmark tem 954 programas em sete conjuntos, 730 corretos e 224 com bug. Três conjuntos vêm da literatura e da comunidade: exemplos do sistema de tipagem de pipelines LadderTypes, todos os scripts do Koala e os programas do Intercode de linguagem natural para código. Ao coletá-los os autores encontraram 2, 3 e 17 bugs adicionais neles e rotularam os programas de acordo. Quatro conjuntos são de programas com bug: GitHub, dos 20 repositórios de shell com mais estrelas (47.080 commits filtrados para 1.028 que editam arquivos shell numa linha com pipe, 328 julgados relevantes pelo gpt-4o-mini e inspecionados à mão, restando 57 commits de correção de bug, cada um dando um programa com bug antes do commit e um correto depois), perguntas do StackOverflow escolhidas manualmente, programas gerados por LLM instruídos a conter erros comuns de shell e testes escritos à mão de padrões específicos de composição.

A acurácia é a fração de classificações corretas sobre todos os programas. O RT usa seu banco de tipos embutido, que cobre 71 dos 106 comandos do GNU coreutils e 86% das invocações do conjunto do GitHub. Ele é comparado ao ShellCheck, contando um programa como com bug se o ShellCheck dá qualquer alerta relacionado a pipelines ou ao conteúdo dos fluxos (com uma lista de alertas irrelevantes ignorados), e ao LadderTypes, com versões acrescentadas à mão das declarações de tipos do RT. As ablações removem as heurísticas, os transdutores ou a concretização. Os tempos são medidos num Ubuntu 20.04, num AMD Ryzen 7 4800H de 8 núcleos com 16 GB de RAM, OpenJDK 17 e Python 3.10.

Resultados

Estes são os resultados reportados pelos autores.

  • Acurácia. 91% no total (864 de 954, com 27 falsos positivos e 63 falsos negativos): 96% nos programas corretos (703 de 730) e 72% nos com bug (161 de 224). Com anotações de tipo é 97% no total, 98% nos corretos e 94% nos com bug, com 14 falsos positivos e 14 falsos negativos. Nos programas com bug o RT é 52 pontos percentuais mais acurado que o ShellCheck e o LadderTypes, com acurácia comparável nos corretos. Os alertas que o RT marca como definitivos têm 100% de acurácia, e os marcados como possíveis, 86%.
  • Bugs que os outros perdem. Só o RT detecta 87 bugs, contra 5 exclusivos do ShellCheck e nenhum do LadderTypes, e 58 bugs não são achados por nenhum dos três sem anotações. Os cinco casos só do ShellCheck são alertas sem relação com o bug real, contados de forma conservadora. Os achados do RT incluem bugs novos em programas de produção antes considerados corretos.
  • De onde vêm os erros. Dos 27 falsos positivos, 11 vêm de heurísticas sinalizando programas corretos e 16 de superaproximação, como cat ${input} | sort -n com um arquivo desconhecido. Dos 63 falsos negativos, 49 vêm da ausência de uma especificação da saída esperada, já que sem uma asserção o programa é bem tipado, e 14 são bugs de um tipo que um sistema de tipos não enxerga. As anotações removem os 49, e restam 6 falsos positivos de superaproximação por usos complexos de awk e sed.
  • O que cada extensão traz. Desligar os transdutores reduz a acurácia a 80% (83% com anotações) e eleva a taxa de falsos positivos de 4% para 20%. Desligar as heurísticas deixa a acurácia em 85% (91% com anotações), com 130 falsos negativos em vez de 63 sem anotações e 82 em vez de 14 com elas, uma redução de 83% no caso anotado. Desligar a concretização muda menos o resultado, 90% (96% com anotações).
  • Velocidade. 0,020 s por programa em média (0,009 a 0,903 s), contra 0,018 s do ShellCheck e 3,081 s do LadderTypes, cuja lentidão os autores atribuem a um script externo que busca os tipos. O autômato médio tem 11,03 estados e o maior 201, e todos os programas, menos um, que levam mais de 0,2 s trazem anotações de entrada complexas.

Análise crítica

O artigo declara vários limites por conta própria.

  • Limites deliberados da regularidade. Alguns comportamentos não são regulares, como sed -E "s/(.*)/\1\1/", que duplica a entrada, e outros como sort e usos complexos de awk ou sed são só aproximados, o que é correto mas pode causar falsos positivos. As heurísticas tratam de prováveis erros, não de violações.
  • Um banco de tipos manual. A cobertura é de 71 dos 106 comandos do coreutils, e comandos desconhecidos recebem o tipo trivial.
  • As anotações carregam os casos difíceis. Sem especificações da saída esperada a maior parte dos bugs perdidos é invisível, e os autores dizem isso.

Os pontos a seguir são uma leitura da evidência, não afirmações do artigo.

  • O destaque mistura classes. Os 91% são dominados por 730 programas corretos, e nos 224 com bug o RT acha 72% sem anotações, então mais de um quarto dos bugs passa sem ser detectado de fábrica. Os 97% exigem anotações, e o texto que li não diz quem as escreveu. Se foram os autores, que conheciam os bugs, o número é um teto do que um usuário obtém.
  • Parte do corpus combina com a ferramenta. Os conjuntos do StackOverflow, gerado por LLM e escrito à mão contêm só programas com bug escolhidos ou construídos em torno de erros de composição de pipeline, que é o alvo do RT, e os conjuntos corretos (Koala, Intercode, os commits pós-correção) são em sua maioria pequenos. A prevalência desses bugs em scripts do dia a dia e as taxas de falso positivo em bases grandes sem rótulo não são medidas, o que importa porque um verificador vive ou morre pelo ruído.
  • As linhas de base são generosas num ponto e não foram feitas para a tarefa noutro. O ShellCheck recebe crédito por qualquer alerta relacionado e mesmo assim acha poucos bugs, mas é um linter sintático, e o LadderTypes precisou de declarações acrescentadas à mão. A comparação mostra o que a semântica do conteúdo dos fluxos acrescenta, não que ferramentas com o mesmo objetivo percam.
  • A velocidade é uma propriedade de tipos pequenos. O autômato médio é minúsculo, e os casos lentos vêm de anotações longas, então a explosão da determinização em expressões regulares complexas é um risco que a avaliação não estressa.
  • A concretização troca correção por precisão. Ler um arquivo na hora da análise dá tipos exatos para aquele arquivo, mas ele pode mudar antes de o script rodar, então o resultado é uma afirmação sobre o ambiente atual.
  • O escopo são pipelines. O texto que li descreve pipelines e grafos de comandos acíclicos. Laços, funções e a interação com a expansão do shell ficam para outras ferramentas, o que torna natural combinar o RT com uma análise de efeitos em vez de compará-los.

Pesquisas futuras

  • Ampliar o banco de tipos automaticamente, a partir de manuais, exemplos ou da mineração de comportamento, e certificar as entradas contra o comportamento real dos comandos.
  • Rastrear tipos por variáveis, laços e funções, e combinar os tipos de fluxo com análises de efeitos e de expansão do mesmo script.
  • Tipos mais ricos para dados estruturados como CSV e linhas JSON, e para comandos como o awk, cujo comportamento completo não é regular.
  • Estudar taxas de falso positivo em bases de código reais grandes e com desenvolvedores usando anotações nos próprios scripts.

Texto completo

Carregando o paper…

Discussão · 0

Nenhum post ainda. Seja o primeiro a iniciar a discussão.