- A Scylla propõe um caminho para compilar o C original diretamente em Rust seguro, estruturando-o gradualmente, em vez de primeiro migrar o código C existente para Rust unsafe e depois corrigi-lo
- O alvo é um subconjunto applicative de C que inclui processamento de dados, aritmética de ponteiros, fluxo de controle estruturado e código portável, excluindo código que dependa de
goto, casts entre inteiros e ponteiros, truques com ponteiros, bitfields e unions sem tag - A transformação ocorre em duas etapas: primeiro rebaixa a AST do Clang para Mini-C e depois a converte para Rust seguro, explicitando comportamentos sutis de C como promoção de inteiros, conversões implícitas, expressões de atribuição e incrementos pré/pós-fixados
- A parte mais difícil, a aritmética de ponteiros, é convertida em particionamento com slices do Rust usando
split_at_mut/split_at, junto com inferência de mutabilidade, derivação de traits e escolha entreBoxe borrow - Foram avaliados Windows SymCrypt, HACL★, o algoritmo central de compressão do bzip2, o parser/serializador CBOR do EverParse e parte do Microsoft FrodoKEM; durante a conversão, também foram encontrados comportamentos indefinidos em bzip2 e FrodoKEM
O caminho de transição de C→Rust escolhido pela Scylla
- A motivação para migrar código C existente para Rust parte de problemas de segurança de memória
- Pesquisas do Google e da Microsoft estimam que 70% das vulnerabilidades de segurança estejam relacionadas a tratamento incorreto de memória
- Empresas e governos recomendam o uso de linguagens com segurança de memória, como Rust, em sistemas críticos de segurança
- Rust tem vantagens claras para código novo, mas reescrever todo um código C industrial já testado e depurado é difícil
- As ferramentas atuais de conversão automática de C→Rust, para dar suporte ao C completo, em geral geram Rust unsafe
- Permitindo idioms típicos de C, como unchecked pointers ou transmutation em Rust
- Com isso, perde-se a garantia estática de segurança de memória, enfraquecendo o objetivo de usar uma linguagem segura
- O fluxo de trabalho mais comum usa a saída em Rust unsafe como ponto de partida e depois a refatora iterativamente para Rust seguro
- Já foram propostas análises estáticas para trocar raw pointers por borrows seguros de Rust ou restaurar abstrações idiomáticas de Rust a partir de representações de baixo nível
- As ferramentas de refatoração estão dispersas, e o suporte ao
c2rust refactorfoi interrompido em 2022
- Em vez de corrigir o Rust unsafe gerado, a Scylla escolhe estruturar gradualmente o próprio código C original para que ele possa ser compilado em Rust seguro
O subconjunto de C suportado e os padrões excluídos
- O objetivo da Scylla é produzir uma conversão previsível e gerar código Rust próximo do C original
- O alvo suportado é um subconjunto applicative de C
- Código que manipula e processa dados
- Código que usa aritmética de ponteiros
- Código com fluxo de controle estruturado
- Código portável
- Codebases que dependam dos padrões abaixo não são suportadas
goto- Uso da representação de objetos por meio de casts entre inteiros e ponteiros
- Truques com ponteiros
- Bitfields
- Untagged unions
- O desenvolvedor pode aplicar rewrites direcionados e anotações ao código-fonte C para que a Scylla consiga entendê-lo
- É possível reescrever padrões de aliasing que não se encaixam no borrow checker do Rust
- Também é possível informar à Scylla que um tagged union deve ser traduzido para um ADT de alto nível
Mini-C: uma linguagem intermediária que reduz as ambiguidades de C
- A Scylla parte da AST do frontend do Clang e primeiro a converte para uma linguagem chamada Mini-C
- Mini-C lida com desvios, loops, ponteiros, dereference e obtenção de endereço como C, mas com uma semântica “no-surprises”
- Todos os inteiros têm largura fixa
- A integer promotion e a integer conversion de C são representadas como casts explícitos
- Ponteiros sem tipo, como
void *, não são permitidos
- Diferentemente de C, Mini-C é uma linguagem de expressões
- Atribuição não retorna valor
- Sintaxes de C como
e1 = e2 = e3ep[i++]são dessugarizadas em Mini-C - Expressões de teste em loops e condicionais precisam ter tipo
bool, e nãointcomo em C
- Ao mover a typed AST do Clang para a typed AST de Mini-C, a Scylla explicita os comportamentos implícitos de C
- Condicionais são ajustadas para
bool - Índices de array são ajustados para
size_t - Conversões implícitas em argumentos de chamada de função e no lado direito de atribuições viram casts explícitos
- Em operações aritméticas, são refletidas as usual arithmetic conversions do padrão C
- Condicionais são ajustadas para
- A transformação assume que o código C seja portável e não dependa do modelo de dados de C
- Por exemplo, não se espera código cujo comportamento mude dependendo se
longtem 4 ou 8 bytes - A implementação detecta em tempo de configuração o modelo de dados da arquitetura de destino e converte
unsigned intpara tipos de largura fixa comouint32_t
- Por exemplo, não se espera código cujo comportamento mude dependendo se
Composição de ADTs e tuplas
- Mini-C oferece ADTs, tuplas e pattern matching em um nível mais alto que C
- Tagged unions são traduzidos para ADTs por meio de anotações
- O formato alvo é algo como
{ int tag; union { t0 case0; ...; tn caseN }} - Assume-se que os valores da tag vão de 0 a N e correspondem à ordem dos casos da union
- O formato alvo é algo como
- A Scylla converte tipos annotated tagged union em tipos variant
- Ao criar valores, verifica se
.tag = ie.casej = esão compatíveis - Se forem, converte para o valor do construtor correspondente
- Se payload e tag não combinarem, não faz a tradução para Mini-C
- Ao criar valores, verifica se
- O acesso a campos de tagged union só é seguro se o estado atual da tag for conhecido
- A ferramenta reconhece padrões como
if (x.tag == i) { ... x.casei }ouswitch - Isso é convertido para algo como
match x with | Ci v -> ... - Acesso a outros casos da union é considerado inválido e gera erro de conversão
- A ferramenta reconhece padrões como
- Tuplas também podem ser compostas por anotação
- Uma struct com
ncampos é convertida em uma tuplan-ária - O acesso aos campos vira acesso a campos da tupla
- Como tuplas têm tipagem estrutural, elas podem aproveitar benefícios de mut-polymorphism
- Uma struct com
Conversão de Mini-C para Rust seguro
- Mini-C fornece uma representação completa de programas C com anotações de tipo, e depois é convertido para Rust seguro
- Há três dificuldades principais
- Eliminar a aritmética de ponteiros de C
- Explicitar mutabilidade e aliasing
- Fornecer automaticamente estruturas idiomáticas de Rust, como traits
- A conversão de tipos de ponteiro é complexa por causa das diferenças na representação de ponteiros em Rust
- Rust distingue
Box<T>de&T - Também distingue ponteiros para um único elemento e para vários elementos, como
&Te&[T] - Arrays em Rust são valores e não decaem automaticamente para ponteiros como em C
- Rust distingue
- A estratégia básica é compilar todos os pointer types de C para o borrow de slice de Rust
&[T]- Tanto ponteiros de stack quanto de heap viram, em princípio, borrows de slice
- Ponteiros para um elemento e para vários elementos também viram, em princípio, borrows de slice
- A mutabilidade é inferida automaticamente em uma etapa separada
- A Scylla usa heurísticas e anotações manuais para traduzir alguns ponteiros em
Box<T>- Funções como
T *create(), sem referências globais e consideradas fresh allocation, podem ser traduzidas parafn create() -> Box<T> - Essa análise é aplicada recursivamente até ponto fixo, inclusive dentro de definições de structs e variants
- Structs que mantêm borrows passam a ter parâmetros de lifetime
- Funções como
Restrições na conversão entre Box, slice e array
- Como Rust exige conversões explícitas entre arrays, borrows de slice e
Box, a conversão para Rust da Scylla também é orientada por tipos - As regras de conversão inserem coerções para transformar arrays ou boxed slices em borrows de slice
- Arrays viram borrows de slice em formas como
&x[..] - Boxed slices podem ser convertidos em borrows
- Arrays viram borrows de slice em formas como
- Também é possível converter no sentido inverso
- Um slice ou array pode ser promovido a uma alocação no heap e virar
Box<[T]>
- Um slice ou array pode ser promovido a uma alocação no heap e virar
- Essa conversão no sentido inverso pode introduzir diferenças de semântica de cópia
- Em C, arrays e ponteiros podem apontar para a mesma memória
- Em Rust,
Box::new(x)pode criar uma cópia dex - Arrays de tipos básicos, como inteiros, não têm como optar por não implementar o trait
Copy, então Rust pode copiar silenciosamente
- Quando isso acontece, a Scylla remove a variável original do ambiente para proibir usos posteriores
- Se o programa C original continuar usando essa variável, a conversão falha com erro
- O desenvolvedor precisa então ajustar o código-fonte C antes da conversão para deixar a intenção mais clara
Trocando aritmética de ponteiros por particionamento de slices em Rust
- Programas em C frequentemente não acessam arrays apenas por um único ponteiro-base; também costumam dividir arrays em chunks ou percorrê-los mantendo um ponteiro para a posição atual
- Rust não permite aritmética arbitrária de ponteiros e oferece, em vez disso, a divisão de slices com
split_at_mutousplit_atsplit_at_muté um primitive que abre mão da posse do slice original para obter dois sub-slices- Isso preserva a invariável do Rust de que dados mutáveis devem ter um único owner
- Para alinhar a aritmética de ponteiros de C ao modo de particionamento do Rust, a Scylla introduz uma árvore de splits
- Cada ponteiro C é mapeado para uma árvore de splits
- A árvore de splits muda de acordo com o fluxo de execução
- Ela rastreia, em cada ponto do programa, para qual acesso de slice em Rust um acesso por ponteiro em C deve ser convertido
- Como ponteiros em C não carregam informação de comprimento, a Scylla assume que os chunks não se sobrepõem
- Se a intenção for sobreposição, o código não passará pela checagem de tipos do Rust e o desenvolvedor terá de reescrever o C
- Para manter a conversão previsível, a abordagem evita backtracking e segue em frente
- No exemplo, um array
abcdde 32 bytes é dividido em quatro regiões limb de 8 bytes- Em C, a aritmética de ponteiros usada é
abcd + 0,abcd + 16,abcd + 8eabcd + 24, fora de uma ordem simples da esquerda para a direita - A conversão para Rust mantém o histórico de chamadas
split_at_mutem uma árvore de splits para localizar o sub-slice correto
- Em C, a aritmética de ponteiros usada é
Casos avaliados e comportamentos indefinidos encontrados
- A implementação da Scylla usa Clang para receber código C existente como entrada e gerar Rust seguro como saída
- Os casos avaliados incluíram partes de vários projetos C existentes
- Parte do SymCrypt do Windows
- Parte da biblioteca criptográfica HACL★
- A parte central do algoritmo de compressão do bzip2
- O parser e serializador binário CBOR da biblioteca EverParse
- A implementação do primitivo criptográfico pós-quântico FrodoKEM da Microsoft
- Esses casos mostram que o subconjunto applicative de C da Scylla pode abranger várias aplicações sensíveis à segurança
- Durante a conversão, também foram identificados e reportados comportamentos indefinidos existentes no código C original de bzip2 e FrodoKEM
1 comentários
Opiniões no Hacker News
É importante notar que este trabalho tem como alvo “bases de código C já verificadas formalmente”
Código C de sistemas em geral não é verificado formalmente, então é uma história bem diferente
Por exemplo, um ponteiro que apontava para um array C na stack pode ser traduzido em Rust como um ponteiro que possui uma nova cópia no heap, como
Box<[u8]>. Se o código original dependia do fato de o ponteiro apontar para o array real, o código traduzido pode se comportar incorretamente de forma silenciosaNo caso do recurso do meu projeto scpptool para tradução automática de um subconjunto C++ com segurança de memória, isso teria sido tratado movendo o array para tipos substitutos e iteradores, preservando a semântica original
O projeto do OP talvez lide apenas com C que é fácil de converter para Rust seguro, mas, considerando a dificuldade do problema, o resultado merece respeito e também parece ter alguma utilidade
Para começo de conversa, eles não traduziram C real; eles pegaram código escrito em F* e mudaram o lado do compilador C para emitir Rust. Não enfrentaram código C real e complexo; no máximo lidaram com um Mini-C limitado, do tipo que um compilador de brinquedo emitiria
O texto original também diz que, se o programa C original depender mais de
x, a tradução gera erro e exige que o programador altere o código-fonte, o que significa que eles esperam que o C já tenha sido escrito em um estilo que satisfaça o verificador de empréstimos do RustParece aquele tipo de formulação acadêmica: “a Figura 4 apresenta regras elegantes, mas a implementação real depende de inúmeros truques”
Pior ainda, sobreposições distinguíveis estaticamente geram erro de compilação e, caso contrário, o código Rust pode entrar em panic em tempo de execução. É estranho transformar um programa C formalmente verificado em um programa Rust que “agora também pode travar”
Também é impreciso chamar HACL* de uma base de código C existente e formalmente verificada. HACL* compila para C, mas não é uma biblioteca C; é escrito em uma linguagem totalmente diferente
Um título honesto teria sido algo como “Compilando um subconjunto de F* para Rust parcialmente seguro, parcialmente formalizado”
Em 2002, pesquisadores publicaram um artigo sobre Cyclone, um dialeto seguro de C, e, ao portar manualmente código C para Cyclone, encontraram bugs de segurança no código C existente
Esse tipo de conversão manual ou automática de C tem potencial não só para aumentar a adoção de linguagens mais seguras, mas também para revelar bugs existentes
[1] https://www.researchgate.net/profile/James-Cheney-2/publicat...
Várias ideias do Cyclone entraram no Rust, e o código pode ser feito funcionar com algum esforço, mas não compila diretamente em plataformas modernas de 64 bits
http://cyclone.thelanguage.org
Já portei alguns projetos para Rust, incluindo projetos em C, usando C2Rust como primeira etapa, e cheguei a algumas conclusões
unsafe, as restrições fortes do Rust, como verificação de limites e assinaturas estritas, muitas vezes fazem os bugs aparecerem rapidamenteAinda assim, ferramentas são essenciais para o porte, e, quanto mais elas evoluírem, mais suave será o processo
Basta representar a memória como um array e tratar ponteiros como índices desse array. Assim é possível representar comportamentos de C, como aritmética de ponteiros sem verificação ou union, sem brigar com o verificador de empréstimos, preservando também a semântica. Técnicas parecidas já são usadas há muito tempo em C→Java
Claro que o valor desse tipo de conversão é ambíguo. Na prática, é parecido com compilar C para wasm, só que mais lento; e, embora o código resultante seja tecnicamente “seguro”, continuam existindo problemas como buffer overflows criando estados incorretos ou ponteiros pendentes possibilitando acesso a dados em contextos onde isso não deveria ser permitido
Sou o autor. Acho que pode ajudar organizar alguns pontos que surgiram em várias threads
unsafe Rustnas partes que não se encaixemO que eu realmente quero saber é por que fazer isso
Se for uma tecnologia capaz de converter de fato apps industriais de C para Rust, parece que também poderia tornar mais fácil blindar apps C existentes. Bastaria criar análises para inserir em ferramentas existentes, como analisadores estáticos ou geradores de testes
Da mesma forma, também seria possível gerar wrappers seguros, permitindo escrever código novo em Rust ao lado de C verificado. O código novo obteria os benefícios do Rust, o código existente seria confirmado como seguro, e a interface também ficaria mais segura
Um tradutor completo talvez seja o ideal. No longo prazo, é melhor que a codebase tenha uma só linguagem. Mas, para C/C++ existente, uma garantia de segurança com poucos falsos positivos e acionável com um botão ainda é a maior necessidade. Também pode ser possível corrigir automaticamente estruturas ruins dentro do C, como as ferramentas de compilador do Google ou o Mayhem da ForAllSecure
Isso pode ser porque dependem de comportamento indefinido ou não especificado, ou porque, ao inserir verificações de segurança adequadas, o domínio de entradas aceitáveis ficaria tão reduzido que o programa se tornaria inútil
Traduzir para uma linguagem segura é objetivamente melhor nesses casos, porque permite manter a expressividade das entradas e, ao mesmo tempo, garantir estaticamente o comportamento correto em tempo de execução
Também é difícil dizer que exista “C comprovado em produção”, como mostram inúmeras vulnerabilidades críticas. O que existe de fato é C que funciona razoavelmente bem com frequência suficiente para parecer útil
Código antigo é presumido seguro por sorte, não porque tenha sido provado. “Prova” tem um significado específico, especialmente no contexto de artigos como este, e a esmagadora maioria do código C não é provada segundo critérios matemáticos rigorosos. Já o sistema de tipos do Rust tem sua correção provada matematicamente
Um tradutor completo depende do que você está disposto a abrir mão. Se puder abrir mão de desempenho, domínio de entradas, faixa de saídas, legibilidade do código etc., algo é possível até certo ponto; mas, quando se começa a querer um tradutor sólido e completo em todos esses aspectos, surgem os problemas
Uma tradução ingênua para Rust não acabaria misturando partes seguras e partes
unsafe? Então o trabalho manual só precisaria verificar a segurança das regiõesunsafe. Parece parecido com escrever Rust desde o começoSe 90% do resultado não for
unsafe, parece que pode ser um ganho considerávelunsafe Rustde baixo nívelO OpenJPEG era conhecido por causar segfault em um caso de teste específico e, ao rodar esse teste na versão Rust, ocorreu um segfault no trecho correspondente do código Rust. Pelo menos era compatível
Mas essa abordagem é um beco sem saída. Para avançar, o tradutor precisa reconhecer idioms comuns de C e elevá-los para formas naturais da linguagem-alvo. “Compilar” para Rust gera um Rust horrível, cheio de chamadas de funções inseguras de manipulação de ponteiros ao estilo C
O maior problema de elevação está quase sempre relacionado a ponteiros. O resultado mais promissor deste artigo é ter encontrado uma forma de transformar aritmética de ponteiros em C em slices de Rust. Slices conseguem fazer a maior parte do que a aritmética de ponteiros em C faz, e agora alguém automatizou essa tradução. Aritmética de ponteiros que não puder ser traduzida deve ser vista com muita suspeita
É útil pensar que um ponteiro bruto para um array em C tem implicitamente um comprimento associado. Esse comprimento não aparece no código-fonte C, mas existe em algum lugar como uma função do estado do programa. Pode ser uma constante, o tamanho solicitado em
mallocou um parâmetro de função. Para um programador de manutenção, encontrar o comprimento de um array normalmente não é muito difícilIsso pode ser um problema adequado para LLMs. Algo como perguntar “olhando este código, qual é o comprimento do array
foo?”, e então deixar um tradutor que não seja o LLM guiar a conversão para Rust. Se o LLM errar, o Rust produzirá um erro de índice ou terá um array grande demais, mas não ficará inseguro. As convenções de informação de tamanho de arrays em C são padronizadas o bastante para acertar na maioria dos casos. Especialmente porque LLMs também conseguem ler comentáriosunsafe, porque usaria ponteiros brutos em todos os lugares em vez de referênciasCódigo C não é escrito levando em conta o modelo de aliasing do Rust nem as restrições do borrow checker, então é difícil traduzi-lo para referências
Trata-se apenas de compilar um subconjunto de C muito pequeno. Na prática, pode ser pequeno a ponto de ser inútil
Tenho expectativas baixas para esse tipo de abordagem. Ela inevitavelmente vai esbarrar nos limites do que é possível com análise estática de código C. Além disso, ao escolher Rust como alvo, o problema fica desnecessariamente difícil. O modelo de ownership do Rust é muito diferente da forma como programas C reais funcionam
Por exemplo, buffers em C obviamente têm um comprimento, mas em C esse comprimento não fica explicitamente vinculado ao ponteiro. Por isso, o tradutor precisa inferir como o programa C rastreia o comprimento e convertê-lo em slices. Mesmo quando o comprimento é uma variável explícita, isso não é fácil; fica ainda mais complicado quando ele é calculado ou quando a representação muda para algo como um “ponteiro para depois do fim”
Padrões em C como
bool should_free_this_pointertambém podem ser levados para um enumOwned/Borrowedem Rust, mas é preciso inferir qual alocação está ligada a qual booleano e onde fica o verdadeiro intervalo seguro da variante emprestadaAinda assim, concordo que produzir Rust idiomático a partir de C arbitrário será difícil. Seria algo no nível de “mais ou menos certo”
Fico curioso sobre como isso se compara ao recurso de tradução de C do Zig
O Zig parece excelente para criar um ambiente misto em que código novo fica em Zig e código antigo permanece em C, fazendo conversão ou interoperabilidade, e até atuando como compilador C
Deve haver motivos muito bons para os mantenedores do kernel Linux não verem o Zig como substituto do C em vez do Rust. Não conheço o suficiente para especular, então gostaria que pessoas mais bem informadas explicassem
Não sou mantenedor do kernel, mas, se eu tivesse que chutar dois grandes motivos pelos quais Rust foi escolhido em vez de Zig, seriam as melhores garantias em tempo de compilação oferecidas pela linguagem e a velocidade maior de adoção
Grandes empresas do setor estão fazendo muito trabalho para oferecer código nativo em Rust para APIs ou bindings Rust mantidos. Desenvolvedores do Windows também estão reescrevendo partes do próprio kernel em Rust. É um movimento que já vem de bastante tempo, e espero que não pare
Os mantenedores talvez sintam que Zig não oferece vantagens suficientes em relação ao C. Muitos deles ainda são contra o Rust também
Zig tem uma interoperabilidade com C muito melhor que Rust, mas não é memory-safe e ainda não está estabilizado. A adoção de Zig no mundo C deve crescer bastante, mas é difícil vê-lo competindo diretamente com Rust
Na minha região, ninguém está adotando Rust, e o pessoal de C++ continua em C++. No começo havia algum interesse em Rust, mas ele não se firmou em nenhuma empresa que eu conheço. Talvez seja por motivos parecidos com o crescimento forte de Go em empresas jovens, mas sua dificuldade de entrar em empresas tradicionais de Java/C#. Mesmo que faça sentido tecnicamente, é um enorme desafio de gestão de mudança
Zig está ganhando tração em programas que não precisam de alocação dinâmica de memória, mas não muito além disso
Ainda há mudanças quebrando compatibilidade com regularidade, o que hoje é bom para o Zig, mas não é bom para uma base de código enorme e longeva como o Linux. Também aparecem bugs no compilador
Digo isso como alguém que, no geral, gosta da direção do Zig
Fico curioso se uma ferramenta como
C2Rustpoderia usar isso para gerar código formalmente corretoTambém me pergunto quanto trabalho manual os autores fizeram, ou se rodaram alguma coisa para gerar o código Rust. Se for o caso, não sei onde está o código que gera Rust, e também não vejo link para o repositório-fonte
Se uma biblioteca C funciona, isto é, se não foi formalmente provado que ela não tem problemas, mas na maior parte funciona bem, fico me perguntando por que não traduzi-la usando
unsafe RustAcho que isso teria valor, já que Rust, de modo geral, carece de bibliotecas. No fim, não é muito diferente de usar uma dll/so escrita em C que pode ser insegura em algumas situações