O caso em que malloc quebrou o JPGLoader do Serenity, ou: como ganhar na loteria (2021)

 (sin-ack.github.io)
1 pontos por GN⁺ 2024-07-08 | 1 comentários | Compartilhar no WhatsApp
  • O erro de cores em JPG do SerenityOS parecia um problema de ordem dos argumentos RGB/BGR, mas na verdade começou quando o JPGLoader deixou componentes que exigiam ordem dependerem da ordem de iteração de uma HashTable
  • Com a introdução de malloc_good_size() em AK+LibC, Vector e HashTable passaram a aproveitar o tamanho real dos chunks de malloc e, como resultado, o número de buckets da HashTable mudou, revelando um bug oculto
  • O código existente estava lendo os componentes Y, Cb e Cr do JPG na ordem correta por acaso; graças à combinação entre os resultados de int_hash e o número de buckets, o erro no processamento do fluxo Huffman ficava mascarado
  • A investigação começou com JPGLoader.cpp sem alterações recentes e, durante um bisect de 1000 commits, uma mudança em AK exigiu recompilar várias vezes o sistema operacional inteiro, com cerca de 3400 arquivos
  • A correção final foi percorrer os componentes em uma ordem determinística; simplesmente trocar a ordem dos argumentos de cor seria um paliativo que poderia recriar o mesmo problema na próxima mudança de ordem

Erro de cores em JPG que parecia confusão RGB/BGR

  • No SerenityOS, ocorreu um problema em que imagens JPG eram exibidas com cores incorretas
  • Ao trocar a ordem dos argumentos do construtor de Color em JPGLoader.cpp, a imagem parecia normal
    • Código existente: passava na ordem Y, Cb, Cr
    • Alteração temporária: passava na ordem Cr, Cb, Y
  • Porém, a última alteração não revertida em JPGLoader.cpp tinha acontecido há mais de um mês no Git, e havia a lembrança de que, uma ou duas semanas antes, uma imagem JPG de fundo era exibida normalmente
  • Por isso, tornou-se mais provável que não fosse um simples erro de ordem dos canais de cor, mas que alguma outra alteração tivesse exposto um bug existente

Bisect dificultado por mudanças em AK

  • O SerenityOS usa sua própria biblioteca padrão, a AK (Agnostic Kit)
    • A AK cumpre um papel parecido com a STL do C++, mas é alterada no mesmo repositório junto com o código do sistema operacional
  • Quando a AK muda, o escopo do impacto é amplo
    • A biblioteca padrão é incluída por quase todo o código
    • Templates em C++ precisam ter suas definições nos headers, então mudanças nos headers da AK causam recompilações amplas
  • Sempre que o bisect passava por um commit que incluía mudanças na AK, era necessário reconstruir todo o sistema operacional
    • Cerca de 3400 arquivos no momento em que o texto foi escrito
    • Durante o bisect de um intervalo de 1000 commits, foram feitas 4 ou 5 builds completas em um notebook de 2011 com Sandy Bridge Mobile
  • O ccache também não conseguia lidar com esse caso e, por causa do ritmo rápido de mudanças no projeto SerenityOS, a AK mudava aproximadamente uma vez a cada 100 commits

O problema oculto revelado por malloc_good_size()

  • Depois de fazer bisect em 1000 commits, a alteração que quebrava as cores dos JPGs foi encontrada não no JPGLoader, mas em AK+LibC
  • O commit que revelou o problema foi f89e8fb71a4893911ee5125f34bd5bbb99327d33
    • Título: AK+LibC: Implement malloc_good_size() and use it for Vector/HashTable
    • Data de autoria: 15 de maio de 2021
  • Esse commit implementou malloc_good_size(), uma API do macOS
    • Ela retorna o tamanho realmente alocado para um tamanho de alocação solicitado
    • Por exemplo, se uma solicitação de 35 bytes usa internamente um chunk de 64 bytes, os 29 bytes restantes podem ser aproveitados
  • Após a mudança, Vector, HashTable e outros passaram a aproveitar melhor a memória disponível dentro do chunk de malloc
  • Como no commit imediatamente anterior a imagem JPG era exibida corretamente, a causa foi delimitada como essa mudança expondo um problema oculto já existente

Decodificação que dependia da capacidade da HashTable

  • A suspeita inicial foi de que o JPGLoader ou algum código de nível superior estivesse dependendo incorretamente da capacidade de um Vector para escrever diretamente nele
  • As mudanças relacionadas envolviam tanto HashTable quanto Vector, e ambos eram usados no código do JPGLoader
  • Ao remover aleatoriamente a linha que aplicava kmalloc_good_size() no lado da HashTable e recompilar, o problema desapareceu
    • O código removido era a parte que ajustava a nova capacidade de buckets ao tamanho real da alocação
  • Esse resultado confirmou que a mudança no número de buckets da HashTable afetava o resultado da decodificação do JPG
  • HashTable não é um contêiner para ser usado como um fluxo de dados sequencial, portanto sua capacidade ou ordem de iteração não deveriam ser usadas como dependência

Como os componentes do JPG eram processados

  • O JPGLoader existente lia as informações de componentes na seção Start of Frame do arquivo JPG e as armazenava em uma struct Component
  • Cada Component tinha um serial_id, que indicava sua posição dentro do arquivo JPG
    • A ordem dos componentes de um JPG normalmente deve ser Y, Cb, Cr
  • Esses componentes eram armazenados em uma HashTable
    • Depois, eram usados para comparar com a ordem dos componentes na seção Start of Scan e verificar se ela era a esperada
  • Na etapa de decodificação, esses componentes eram percorridos e suas informações eram usadas para a transformação dos macroblocos
  • O problema estava em colocar componentes cuja ordem era importante em uma HashTable e percorrê-los com o iterador padrão

Diferença na ordem de iteração entre o commit quebrado e o commit correto

  • No commit que produzia cores quebradas, a saída de depuração percorria os componentes nesta ordem
    • 0
    • 2
    • 1
  • No commit anterior, que funcionava corretamente, a ordem era diferente
    • 0
    • 1
    • 2
  • Essa diferença estava ligada ao resultado que parecia uma inversão dos canais de cor
  • Ao tentar mudar manualmente a ordem dos componentes junto com CxByte, ocorreu o seguinte erro
    • Huffman stream exhausted. This could be an error!
    • Failed to build Macroblock 3277
  • Esse erro mostrou que a decodificação de JPG é sensível à ordem do fluxo e confirmou que a ordem de iteração dos componentes era a causa principal

A ordem da HashTable que dava certo por acaso

  • A causa raiz era armazenar em uma HashTable objetos que exigiam ordem e percorrê-los com o iterador padrão
  • O hash do ID dos componentes JPG passava por int_hash e era usado na seleção dos buckets
  • Antes, duas coincidências aconteciam ao mesmo tempo
    • O resultado de int_hash para os valores 0, 1 e 2 era estável
    • O número de buckets da AK::HashTable coincidia exatamente para que os componentes fossem posicionados na ordem correta
  • Graças a essa coincidência, o JPGLoader lia o fluxo Huffman na ordem correta para cada componente, e o bug ficou mascarado desde o início
  • Quando a introdução de malloc_good_size() alterou o número de buckets da HashTable, a ordem dos componentes mudou, e apareceram imagens com os canais vermelho e azul trocados

Correção final com iteração determinística

  • Depois de cerca de 10 horas de depuração, foi criado o commit de correção
  • O commit de correção é a10ad24c760bfe713f1493e49dff7da16d14bf39
    • Título: LibGfx: Make JPGLoader iterate components deterministically
    • Data de autoria: 31 de maio de 2021
  • O ponto central da correção foi fazer o JPGLoader percorrer os componentes em uma ordem determinística
  • Simplesmente mudar a ordem dos argumentos de Color também fazia a imagem parecer correta naquele momento, mas poderia quebrar de novo se alguma outra mudança alterasse novamente a ordem de iteração
  • Foi um caso em que um problema que parecia um pequeno erro de exibição foi revelado pela combinação entre uma dependência incorreta da ordem de iteração de um contêiner e uma mudança no tamanho das alocações

Leituras relacionadas

1 comentários

 
GN⁺ 2024-07-08
Comentários no Hacker News

  • Este é um dos motivos pelos quais muitas implementações de tabelas hash introduzem um elemento de aleatoriedade no algoritmo
    Como a ordem dos elementos muda a cada execução, se você acabar dependendo da ordem por engano, o problema aparece rápido
    Se o algoritmo de hash for fixo, dá para criar chaves que se concentrem no mesmo bucket e explorar isso em um ataque de negação de serviço; isso também ajuda bastante a evitar esse tipo de problema de segurança

    • Hoje em dia, por outro lado, também há muitas implementações de tabelas hash que garantem que a iteração sempre siga a ordem de inserção
      Eu prefiro isso, porque assim não preciso decidir toda vez se preciso de um mapa ordenado ou não ordenado
      Já aconteceu várias vezes de eu achar que um mapa não ordenado bastava, mas no fim estar errado por motivos sutis
    • Tudo bem se esse elemento aleatório for uma seed que possa ser explicitamente definida, salva, registrada em log e reproduzida
      Caso contrário, é uma péssima ideia, porque torna muito mais difícil depurar outros problemas
      Aleatoriedade não é amiga, é inimiga
      Há uns 20 anos, havia um jeito de atacar servidores web Java manipulando parâmetros de URL para fazer tudo cair no mesmo bucket, o que gerava um grande ataque de negação de serviço
      Se bem me lembro, servidores web em PHP sofreram exatamente o mesmo problema de segurança
      Isso foi corrigido colocando uma seed na tabela hash, e essa seed naturalmente podia ser controlada pelo desenvolvedor. Porque aleatoriedade não é amiga, é inimiga

  • Isso parece um caso em que ter depurado um pouco mais teria economizado tempo, em vez de sair fazendo bisect em modo busca binária sem pensar muito
    O log imprimindo a ordem dos componentes acabaria tendo de ser adicionado de qualquer forma

  • A depuração foi boa, mas a mensagem de commit também é excelente
    Ela conseguiu condensar bem a causa e a correção em poucos parágrafos

  • Se você esperar bastante, o C++ também deve ganhar algo equivalente a malloc_good_size
    https://github.com/cplusplus/papers/issues/18

  • O título precisa de [2021]

  • Isso não é culpa do Gunnar. O problema está em quem salvou dados com ordem em um arquivo hash
    Fazendo esse tipo de trabalho há décadas, já passei várias vezes por situações em que uma mudança no layout de memória revelou um bug que estava escondido
    Toda vez, a depuração levou de algumas horas a alguns dias
    Se programar não fosse difícil, nós não seríamos necessários. Só não sei por quanto tempo essa frase ainda vai valer na era dos grandes modelos de linguagem

    • Concordo. Mesmo que fosse culpa do Gunnar, não parece haver necessidade de colocar isso na mensagem de commit
      O Gunnar melhorou alguma coisa, e no processo isso só revelou um problema em código antigo que já estava quebrado
      Mas, em troca desse esforço, ele acaba ouvindo algo como “Gunnar, I like you, but please don't make me go through this again. :^)”
    • Enquanto os grandes modelos de linguagem forem treinados com código com bugs, eles vão sugerir código com bugs
    • Exato. E, ao contrário do que diz o título, também não é culpa do malloc()

  • Pelo que sei, no SerenityOS há pessoas que ajudam umas às outras com recursos de teste ou PCs

  • Dizer que alguém compilou o SerenityOS do zero 4 ou 5 vezes em um notebook Sandy Bridge Mobile de 2011 é mais ou menos como tentar fazer desenvolvimento do Windows Vista em um computador da época entre o Windows 3.1 e o Windows 95

    • A comparação faz sentido no intervalo de tempo, mas não em desempenho real
      Desde 2011, as CPUs não mudaram tanto assim em termos relativos, mas entre o Windows 3.1 e o Vista o x64 se popularizou e as CPUs multinúcleo viraram algo comum
    • Boa comparação. A CPU do desenvolvedor tem cerca de 13 anos
      O Vista foi lançado internacionalmente no começo de 2007, então uma CPU com 13 anos na época do lançamento seria de 1994, cerca de um ano depois da chegada do Pentium original
      Naquela época, muita gente ainda usava com confiança um 486 DX2-66
      É bem impressionante que uma CPU de 13 anos atrás ainda possa ser usada hoje em trabalho com projetos modernos. Naquela época, seria difícil dizer o mesmo
      Espero que as CPUs lançadas hoje ainda possam ser usadas com satisfação depois de 2037
    • No último ano, usei como desktop principal um Lenovo i5 de 2011 com Windows 11 e dois monitores
      O Visual Studio roda bem, e o Photoshop também, embora as ferramentas de IA embutidas no sistema fiquem só um pouco lentas
      Devo estar com umas 200 abas do Chrome abertas, além de Slack, WhatsApp e mais 3 navegadores para testes
      O CapCut poderia ser um pouco mais rápido em edição 4K, mas aguenta bem projetos 2K complexos
      Só senti um pouco o limite em projetos complexos do After Effects. Esse ele realmente não gosta
      Preciso fazer upgrade, mas, para um sistema praticamente resgatado do lixo, ele vai muito bem

  • Quando vi “Alien Lenna”, tive uma sensação de déjà vu e, de fato, era um texto que eu já tinha lido e até comentado antes
    https://news.ycombinator.com/item?id=27374942 (2021)