Técnica do C-Reduce que pode ser usada em qualquer linguagem

• C-Reduce é uma ferramenta para reduzir código de reprodução de bugs em compiladores C, mas também pode ser aplicada a outras linguagens se houver uma condição determinística, uma reprodução rápida e arquivos-fonte modificáveis
• O exemplo mostra o processo de reduzir um bug ocorrido ao executar scrapscript no RustPython, em que interesting.sh determina se a reprodução ocorre procurando uma mensagem de erro específica
• Apenas executando creduce --not-c interesting.sh scrapscript.py, o tamanho do arquivo diminuiu rapidamente, com progresso mostrando uma redução de quase 50% logo no início
• --not-c é uma opção que evita passes de redução específicos de C, ajudando a reduzir tempo de execução desnecessário em entradas como Python
• Se for possível criar um script curto com a condição que reproduz o bug, relatórios de bug de linguagens que não são C também podem ser tornados menores e mais fáceis de lidar com C-Reduce

---

Condições para usar C-Reduce em entradas que não sejam C

• C-Reduce é uma ferramenta criada por Regehr e colegas para minimizar código de reprodução de bugs em compiladores C
• Quando um arquivo C de 10.000 linhas causa um bug no Clang, ela pode ser usada para reduzi-lo automaticamente em vez de enviar o arquivo enorme como está
• Embora pareça uma ferramenta exclusiva para C, ela também pode ser usada com entradas de outras linguagens se as seguintes condições existirem

  • Condição determinística

    • Um método de reprodução relativamente rápido que ajude na velocidade da redução
    • Um ou mais arquivos-fonte modificáveis que o C-Reduce possa reduzir
    • A condição determinística também pode ser simulada probabilisticamente usando um wrapper em loop

Exemplo de redução de reprodução de bug no RustPython

• Um bug ocorreu ao executar scrapscript no RustPython, e foi escrito um script interesting.sh para reportá-lo
• O script executa scrapscript.py usando o caminho absoluto do binário do RustPython e então procura a seguinte string na saída, incluindo o erro padrão
  • tried to push value onto stack but overflowed max_stackdepth
• O comando de execução é o seguinte
  • creduce --not-c interesting.sh scrapscript.py
• O C-Reduce executa testes de interestingness em paralelo e reduz rapidamente o tamanho do arquivo
  • O progresso do exemplo é exibido como 0,5%, 9,2%, 18,1%, 47,5% etc.
  • Em poucos segundos, o arquivo foi reduzido em quase 50%
  • No momento em que o texto foi concluído, chegou a 96,9% de redução
• Sem usar --not-c, o C-Reduce usa muitos passes específicos para C
  • Em entradas Python, esses passes podem tornar a execução mais lenta
  • É provável que isso não altere substancialmente o resultado em si
• O conteúdo relacionado foi posteriormente movido para a página Delta debugging

[GN⁺]

Opiniões no Hacker News

• Como não compartilharam o arquivo reduzido, rodei por conta própria. Compilei o RustPython, peguei o scrapscript.py, alterei o caminho em interesting.sh e executei com nix run nixpkgs#creduce -- --not-c interesting.sh scrapscript.py; no fim, ele parou por volta de 96,4%, 7347 bytes, e o resultado está em https://gist.github.com/judofyr/47cba8a20cb2cd5798943ef975d0...

  • Uma coisa que me ocorreu: outra pessoa ficou preocupada que, durante o processo de redução, o programa pudesse quebrar e fazer operações destrutivas na máquina local. Talvez, se o redutor fosse executado como uma derivation do Nix source-to-source, daria para impedir comportamentos perigosos e também distribuí-lo facilmente para builders remotos
  • Para referência, o shrinkray, rodando por uns 10 minutos, reduz até 162 bytes: https://gist.github.com/DRMacIver/ee025c90b4867125b382a13aaa...
    Se deixar mais tempo, talvez melhore um pouco, mas parecia quase travado, então fiquei entediado e encerrei

• John Regehr, autor do C-Reduce, também recomenda experimentar o Shrinkray para esse uso. Ele diz que o Shrinkray foi feito para funcionar independentemente do formato e que é uma boa ferramenta mesmo nos casos em que o C-Reduce não se sai bem: https://mastodon.social/@regehr/113489759789563570

  • Este repositório é o repositório oficial do Shrinkray? https://github.com/DRMacIver/shrinkray
  • Também quero mencionar o cvise: https://github.com/marxin/cvise
    É uma alternativa em Python que funciona razoavelmente bem também com linguagens que não são C

• Há um artigo de 2012, de John Regehr e outros autores, que explica como ele funciona: https://fsl.cs.illinois.edu/publications/regehr-chen-cuoq-ei...

  • Li esse artigo e ainda não consigo entender bem como isso é possível. Parece que ele entende tokenização, junção de linhas, remoção de tokens etc. para linguagens de programação arbitrárias; fico curioso se existe outro artigo explicando apenas esse algoritmo
  • Esse artigo não trata do C-Reduce inteiro, mas de três redutores de casos de teste específicos de domínio adicionados ao projeto
    Pelo que me lembro, a maior parte das reduções não específicas de domínio do C-Reduce é algo próximo de força bruta simples

• Acabei de conhecer o C-Reduce e já fiquei fascinado. É parecido com quando descobri o git bisect pela primeira vez
  Preciso guardar isso em algum canto da cabeça para usar quando um dia aparecer a situação certa

  • No meu primeiro emprego depois da faculdade, eu estava na equipe de compiladores C/C++ e fazia esse tipo de trabalho manualmente. É bem impressionante que seja possível automatizar a mesma coisa
  • Passei por um problema que parecia ser bug de compilador no cc65, um compilador C para o processador 6502. Alvos como C64, NES e Apple 1
    Estou pensando em configurar isso. Como o VICE oferece suporte a “emitir saída” para um arquivo do sistema operacional host, parece que daria para rodar os testes no emulador
  • É excelente quando usado junto com um gerador de entradas de teste aleatórias

• Delta debugging não é um conceito novo: https://en.wikipedia.org/wiki/Delta_debugging
  Minha implementação de delta debugging, delta, tem mais de 19 anos: https://github.com/dsw/delta
  Na época em que a Microsoft chamava open source de “câncer”, a Microsoft Research mandou gente até meu escritório pedindo que eu a tornasse pública, então lancei como open source. A introdução de Latner ao LLVM também menciona a “ferramenta padrão de delta debugging”, então é uma ferramenta bastante conhecida: https://aosabook.org/en/v1/llvm.html

  • O C-Reduce é um pouco mais sofisticado do que delta debugging simples. Segundo o resumo do artigo de 2012 “Test-Case Reduction for C Compiler Bugs”, os resultados do C-Reduce são, em média, mais de 25 vezes menores do que os de outros redutores ou do redutor mais usado anteriormente por desenvolvedores de compiladores
    Ou seja, a conclusão é que uma redução eficaz de programas exige mais do que delta debugging simples. Claro que o C-Reduce também já é uma ferramenta de 12 anos
    Ao mesmo tempo, a ferramenta do LLVM linkada, BugPoint, é específica para LLVM IR, enquanto o C-Reduce parece mais geral. Ferramentas e técnicas de minimização automática de casos de teste ainda são desconhecidas para a maioria dos desenvolvedores; portanto, mesmo sendo uma ideia conhecida há muito tempo nessa área, este texto pode ser útil

• Encontrei um texto com exemplos de antes e depois: https://pramodkumbhar.com/2024/01/c-reduce-systematically-ta...
  Ainda assim, não entendo bem como ele sabe o que remover em cada iteração. Deve haver algum nível de tokenização, mas não sei como isso funciona entre várias linguagens de programação

• creduce é excelente
  Quando eu desenvolvia um backend de target esotérico para LLVM, escrevi um script de teste que gerava programas de teste aleatórios por horas com o CSmith. Quando havia um crash, ele rodava automaticamente o C-Reduce e deixava um arquivo para eu inspecionar, o que ajudava muito

• Também funciona bem com SQL. Uso no trabalho e conheci por meio de https://github.com/sqlancer/sqlancer?tab=readme-ov-file#redu...

• É uma afirmação difícil de acreditar se não explicarem por que funciona também em linguagens além de C. Não acho que seja mentira, mas dizer que faz isso sem LLM é surpreendente

  • Resumindo, alguns passes de redução se generalizam bastante bem para linguagens da família C, e esses passes estão entre os mais eficazes
    Por exemplo, a estratégia de tokenizar a entrada no estilo C e depois descartar aleatoriamente blocos de tamanho por volta de 1 a 13 funciona bem para remover qualificadores ou atributos desnecessários, porque a maioria das linguagens parecidas com C tem regras de tokenização semelhantes. Um passe que remove unidades de parênteses balanceados (), {}, [] também é útil em praticamente qualquer linguagem. Remover comentários e espaços em branco também é eficaz porque muitas linguagens usam os estilos /* */ e //, como C
    Na prática, não há muitos passes que sejam realmente específicos de C/C++. Pela minha experiência, uma das grandes fraquezas do creduce é que ele é muito ruim na etapa de redução que remove templates, ou seja, uma tarefa que parece relativamente fácil de automatizar
  • Recomendo dar uma olhada no artigo da PLDI linkado por asmeurer. Ele tem um bom resumo
    Algumas transformações são bem específicas de C, usando o frontend do Clang, e outras são bastante gerais, então provavelmente funcionam em geral com linguagens da família Algol. Como é uma ferramenta modular, se quiser você pode adicionar transformações que entendam outras linguagens
  • Isso está mais para ciência da computação à moda antiga. Espero que o HN ainda não tenha esquecido essa tradição da ciência da computação
    O que estou falando aqui são coisas como algoritmos, não aquele aprendizado de máquina assustador. Isso inclui coisas como usar Prolog para IA, embora tenha o pequeno ponto negativo de não funcionar muito bem para o objetivo de criar IA
  • Se eu não entendo como funciona, não sei se é seguro usar dessa forma. O creduce poderia executar o script de entrada modificado e apagar meus arquivos ou comer meu almoço?
  • Chutando sem ter lido o artigo, parece algo parecido com um fuzzer que aplica mutações na direção de reduzir o tamanho da entrada

• Como ele se compara ao dustmite? https://dlang.org/blog/2020/04/13/dustmite-the-general-purpo...