Por que portar sobre o excesso de número inteiro não é uma boa ideia

Este artigo se concentra no comportamento indefinido e nas otimizações do compilador, especialmente no contexto de estouro de número inteiro assinado.

Nota do tradutor: em russo, não há correspondência clara no contexto usado da palavra "wrap" / "wrapping". Existe um termo matemático " transferência ", que é próximo ao fenômeno descrito, e o termo "sinalizador de transporte" é um mecanismo para definir um sinalizador nos processadores durante o estouro de números inteiros. Outra opção de tradução pode ser a frase "rotação / rotação / rotação em torno de zero". Reflete melhor o significado de "agrupar" em comparação com "transportar", porque mostra a transição de números ao transbordar do intervalo positivo para o negativo. No entanto, essas palavras parecem incomuns no texto para os leitores de teste. Por uma questão de simplicidade, no futuro, usaremos a palavra "transferência" como uma tradução do termo "quebra automática".

Os compiladores da linguagem C (e C ++) em seu trabalho são cada vez mais guiados pelo conceito de comportamento indefinido - a noção de que o comportamento de um programa para algumas operações não é regulado pelo padrão e que, ao gerar código de objeto, o compilador tem o direito de prosseguir com a suposição de que o programa não realiza tais operações. Muitos programadores se opuseram a essa abordagem, já que o código gerado nesse caso pode não se comportar como o autor do programa pretendia. Esse problema está se tornando mais agudo, pois os compiladores estão usando métodos de otimização mais sofisticados, que provavelmente serão baseados no conceito de comportamento indefinido.

Nesse contexto, um exemplo com um excesso de número inteiro assinado é indicativo. A maioria dos desenvolvedores de C escreve código para máquinas que usam código adicional para representar números inteiros, e a adição e subtração nessa representação são implementadas exatamente da mesma maneira, na aritmética não assinada. Se a soma de dois números inteiros positivos com um sinal exceder o limite - ou seja, se tornar maior do que o tipo acomoda - o processador retornará um valor que, interpretado como um complemento binário do número assinado, será considerado negativo. Esse fenômeno é chamado de “transferência”, pois o resultado, tendo atingido o limite superior da faixa de valores, é “transferido” e parte do limite inferior.

Por esse motivo, às vezes você pode ver esse código em C:

int b = a + 1000; if (b < a) { //  puts("input too large!"); return; } 

A tarefa da instrução if é detectar uma condição de estouro (nesse caso, ocorre após adicionar 1000 ao valor da variável a ) e relatar um erro. O problema é que, em C, o excesso de número inteiro assinado é um dos casos de comportamento indefinido. Por algum tempo, os compiladores sempre consideraram essas condições falsas: se você adicionar 1000 (ou qualquer outro número positivo) a outro número, o resultado não poderá ser menor que o valor inicial. Se o estouro ocorrer, haverá um comportamento indefinido, e não permitir que isso já seja (aparentemente) a preocupação do programador. Portanto, o compilador pode decidir que o operador condicional pode ser completamente removido para fins de otimização (afinal, a condição é sempre falsa, não afeta nada, portanto você pode fazer sem ela).

O problema é que, com essa otimização, o compilador removeu a verificação que o programador adicionou especificamente para detectar um comportamento indefinido e processá-lo. Aqui você pode ver como isso acontece na prática. (Nota: o site godbolt.org, que hospeda o exemplo, é muito legal! Você pode editar o código e ver imediatamente como diferentes compiladores o processam, e existem muitos deles. Experimente!). Observe que o compilador não remove a verificação de estouro se você alterar o tipo para não assinado, pois o comportamento do estouro não assinado em C é definido (mais precisamente, o resultado é transferido com aritmética não assinada, portanto, o estouramento não ocorre realmente).

Então isso está errado? Alguém diz que sim, embora seja óbvio que muitos desenvolvedores de compiladores considerem essa decisão legal. Se bem entendi, os principais argumentos dos apoiadores (editar: dependentes da implementação) da transferência durante o estouro são os seguintes:

• Transbordar é um comportamento útil.
• Migração é o comportamento que os programadores esperam.
• A semântica do comportamento de estouro indefinido não oferece uma vantagem perceptível.
• O padrão da linguagem C para comportamento indefinido permite que a implementação "ignore completamente a situação, e o resultado será imprevisível", mas isso não dá ao compilador o direito de otimizar o código com base no pressuposto de que a situação com comportamento indefinido não ocorre.

Vamos analisar cada item por vez:

Migração de estouro - comportamento útil?

A migração é útil principalmente quando você precisa rastrear um estouro que já ocorreu. (Se houver outros problemas que podem ser resolvidos por transferência e não podem ser resolvidos usando variáveis ​​inteiras não assinadas, não consigo recordar imediatamente esses exemplos e suspeito que existem poucos). Embora a transferência realmente simplifique o problema do uso de variáveis ​​excedidas incorretamente, ela definitivamente não é uma panacéia (lembre-se da multiplicação ou adição de duas quantidades desconhecidas com um sinal desconhecido).

Em casos triviais, quando a transferência simplesmente permite rastrear o estouro que surgiu, também não é difícil saber antecipadamente se isso ocorrerá. Nosso exemplo pode ser reescrito da seguinte maneira:

 if (a > INT_MAX - 1000) { //    puts("input too large!"); return; } int b = a + 1000; 

Ou seja, em vez de calcular a soma e descobrir se ocorreu ou não um estouro, verificando a consistência matemática do resultado, é possível verificar se a soma excede o número máximo que o tipo se encaixa. (Se o sinal de ambos os operandos for desconhecido, a verificação terá que ser muito complicada, mas o mesmo se aplica à verificação durante a transferência).

Diante de tudo isso, acho o argumento não convincente de que a transferência é útil na maioria dos casos.

A migração é o comportamento que os programadores esperam?

É mais difícil argumentar com esse argumento, pois é óbvio que o código de pelo menos alguns programadores C pressupõe semântica de transferência com um estouro de número inteiro assinado. Mas esse fato por si só não é suficiente para considerar essa semântica preferível (observe que alguns compiladores permitem habilitá-lo, se necessário).

Uma solução óbvia para o problema (os programadores esperam esse comportamento) é fazer o compilador emitir um aviso ao otimizar o código, assumindo que não há comportamento indefinido. Infelizmente, como vimos no exemplo no godbolt.org, usando o link acima, os compiladores nem sempre fazem isso (versão Gcc 7.3 - sim, mas versão 8.1 - não, então há um passo atrás).

A semântica do comportamento indefinido do estouro não oferece vantagem perceptível?

Se essa observação for verdadeira em todos os casos, seria um forte argumento a favor do fato de que os compiladores devem aderir à semântica de transferência por padrão, já que provavelmente seria melhor permitir verificações de estouro, mesmo que esse mecanismo esteja incorreto do ponto de vista técnico - embora seria porque ele pode ser usado em código potencialmente quebrado.

Suponho que essa otimização (remoção de verificações de condições matematicamente contraditórias) em programas C comuns possa ser negligenciada, pois seus autores buscam o melhor desempenho e ainda otimizam o código manualmente: ou seja, se é óbvio que essa instrução if contém uma condição , o que nunca será verdade, é provável que o programador o remova. De fato, descobri que em vários estudos a eficácia dessa otimização foi posta em causa, testada e considerada praticamente insignificante na estrutura dos testes de controle. No entanto, embora essa otimização quase nunca dê uma vantagem na linguagem C, os otimizadores de geradores de código e compiladores são na maioria universais e podem ser usados ​​em outros idiomas - e para eles essa conclusão pode estar incorreta. Vamos levar a linguagem C ++ com sua tradição, digamos, de confiar no otimizador para remover construções redundantes no código do modelo, em vez de fazê-lo manualmente. Mas existem idiomas que são convertidos pelo transportador em C, e o código redundante neles também é otimizado pelos compiladores C.

Além disso, mesmo se você continuar verificando estouros, não é fato que o custo direto da transferência de variáveis ​​inteiras será mínimo, mesmo em máquinas que usam código adicional. A arquitetura Mips, por exemplo, só pode executar operações aritméticas em registradores de tamanho fixo (32 bits). O tipo short int , como regra, tem um tamanho de 16 bits e char - 8 bits; quando uma variável de um desses tipos é armazenada no registro, seu tamanho se expande e, para transferi-lo corretamente, será necessário executar pelo menos uma operação adicional e, possivelmente, usar um registro adicional (para acomodar a máscara de bit correspondente). Tenho que admitir que não lido com o código do Mips há muito tempo, por isso não tenho certeza do custo exato dessas operações, mas tenho certeza de que não é zero e que os mesmos problemas podem ocorrer em outras arquiteturas RISC.

Um padrão de linguagem proíbe evitar o agrupamento de variáveis ​​se for planejado pela arquitetura?

Se você olhar, esse argumento é especialmente fraco. Sua essência é que o padrão supostamente permite que a implementação (compilador) interprete o "comportamento indefinido" apenas em uma extensão limitada. No texto da própria norma - naquele fragmento ao qual os defensores da transferência apelam - é dito o seguinte (isso faz parte da definição do termo "comportamento indefinido"):

NOTA: O comportamento indefinido pode assumir a forma de ignorar completamente a situação, enquanto o resultado será imprevisível, ...

A idéia é que as palavras "ignorar completamente a situação" não sugerem que um evento que leve a um comportamento indefinido - por exemplo, transbordamento durante a adição - não possa ocorrer, mas sim que, se ocorrer, o compilador deve continuar trabalhando como se estivesse em execução. do que nunca aconteceu, mas também leve em conta o resultado que resultará se ele enviar ao processador uma solicitação para realizar essa operação (em outras palavras, como se o código-fonte tivesse sido traduzido para o código da máquina de maneira direta e ingênua).

Antes de tudo, deve-se notar que este texto é dado como uma “nota” e, portanto, não é normativo (isto é, não pode prescrever algo), de acordo com a diretiva ISO mencionada na introdução da norma:

De acordo com a Parte 3 das Diretivas ISO / IEC, este prefácio, introdução ao texto, notas, notas de rodapé e exemplos também são apenas para fins informativos.

Como essa passagem de "comportamento indefinido" é uma nota, ela não prescreve nada. Observe que a definição atual de "comportamento indefinido" é:

comportamento decorrente do uso de um design de software intolerável ou incorreto ou dados incorretos, para os quais esta Norma Internacional não impõe nenhum requisito .

Eu destaquei a idéia principal: nenhum requisito é imposto a um comportamento indefinido; a lista de "tipos possíveis de comportamento indefinido" na nota contém apenas exemplos e não pode ser a prescrição final. A frase "não faz exigências" não pode ser interpretada de outra forma.

Alguns, desenvolvendo esse argumento, argumentam que, independentemente do texto, o comitê de idiomas, ao formular essas palavras, significava que o comportamento como um todo deveria corresponder à arquitetura do hardware em que o programa está sendo executado, tanto quanto possível, implicando uma tradução ingênua no código da máquina. Isso pode ser verdade, embora eu não tenha visto nenhuma evidência (por exemplo, documentos históricos) em apoio a esse argumento. No entanto, mesmo se assim fosse, não é fato que esta declaração se aplique à versão atual do texto.

Últimos pensamentos

Os argumentos a favor da transferência são em grande parte insustentáveis. Talvez o argumento mais forte seja obtido se os combinarmos: programadores menos experientes (que não conhecem os meandros da linguagem C e o comportamento indefinido nela) às vezes esperam transferência, e isso não reduz o desempenho - embora o último não seja verdadeiro em todos os casos e a primeira parte seja inconclusiva se você considerar isso separadamente.

Pessoalmente, eu preferiria que os estouros sejam bloqueados (interceptação) em vez de quebrar. Ou seja, para que o programa trave e não continue a funcionar - com comportamento incerto ou resultados potencialmente incorretos, porque nos dois casos uma vulnerabilidade aparece. Essa solução, é claro, reduzirá levemente o desempenho na maioria das arquiteturas (?), Especialmente no x86, mas, por outro lado, os erros de estouro serão imediatamente identificados e eles não poderão tirar proveito ou obter resultados incorretos usando-os ao longo do caminho. programas. Além disso, em teoria, os compiladores com essa abordagem poderiam remover com segurança as verificações redundantes de estouro, uma vez que isso certamente não acontecerá, embora, a meu ver, nem Clang nem GCC usem essa oportunidade.

Felizmente, a interrupção e a portabilidade são implementadas no compilador que eu uso com mais frequência é o GCC. Para alternar entre os modos, os argumentos da linha de comandos -ftrapv e -fwrapv são usados, respectivamente.

Obviamente, existem muitas ações que levam a um comportamento indefinido - o excesso de números inteiros é apenas uma delas. Não creio que seja útil interpretar todos esses casos como comportamento indefinido e tenho certeza de que há muitas situações específicas em que a semântica deve ser determinada pela linguagem ou, pelo menos, ser deixada a critério das implementações. E tenho medo de interpretações excessivamente livres desse conceito pelos fabricantes de compiladores: se o comportamento do compilador não atender às idéias intuitivas dos desenvolvedores, especialmente aqueles que leem pessoalmente o texto do padrão, isso pode levar a erros reais; se o ganho de desempenho nesse caso for insignificante, é melhor abandonar essas interpretações. Em uma das postagens a seguir, provavelmente examinarei alguns desses problemas.

Suplemento (datado de 24 de agosto de 2018)

Percebi que grande parte do exposto poderia ser melhor escrita. Abaixo, resumi brevemente e explico minhas palavras e adiciono algumas considerações menores:

• Não argumentei que o comportamento indefinido é preferível para transbordar - em vez disso, na prática, a transferência não é muito melhor que o comportamento indefinido. Em particular, problemas de segurança podem ser obtidos no primeiro caso e no segundo - e aposto que muitas das vulnerabilidades causadas por estouros que não foram detectados a tempo (exceto aquelas pelas quais o compilador é responsável por excluir verificações incorretas) vieram de fato. - devido à transferência do resultado, mas não devido ao comportamento indefinido associado ao estouro.
• A única vantagem real da transferência é que as verificações de excesso não são excluídas. Embora desta maneira você possa proteger o código de alguns cenários de ataque, é provável que alguns dos estouros não sejam verificados (ou seja, o programador se esqueça de adicionar essa verificação) e passará despercebido.
• Se o problema de segurança não for tão importante e a alta velocidade do programa surgir, um comportamento indefinido proporcionará uma otimização mais rentável e um aumento maior da produtividade, pelo menos em alguns casos. Por outro lado, se a segurança vem em primeiro lugar, a portabilidade está repleta de vulnerabilidades.
• Isso significa que, se você escolher entre interrupção, transferência e comportamento indefinido, existem muito poucas tarefas nas quais a transferência pode ser útil.
• Quanto às verificações do estouro ocorrido, acredito que deixá-las é prejudicial, pois cria a falsa impressão de que elas funcionam e sempre funcionarão. Interromper estouros evita esse problema; avisos adequados - reduza-o.
• Penso que qualquer desenvolvedor que escreva código crítico de segurança deve idealmente ter um bom domínio da semântica da linguagem em que escreve, além de estar ciente de suas armadilhas. Para C, isso significa que você precisa conhecer a semântica do excesso e as sutilezas do comportamento indefinido. É triste que alguns programadores não tenham crescido para esse nível.
• Eu me deparei com a afirmação de que "a maioria dos programadores C espera que a migração seja o comportamento padrão", mas não conheço as evidências para isso. (No artigo, escrevi "alguns programadores", porque conheço vários exemplos da vida real e, em geral, duvido que alguém discuta isso.
• Existem dois problemas diferentes: o que o padrão da linguagem C exige e quais compiladores devem implementar. Eu (geralmente) gosto da maneira como o padrão define o comportamento indefinido do estouro. Neste post, falo sobre o que os compiladores devem fazer.
• Quando o estouro é interrompido, não há necessidade de verificar todas as operações. Idealmente, o programa com essa abordagem se comporta de maneira consistente em termos de regras matemáticas ou para de funcionar. Nesse caso, a existência de um "transbordamento temporário" torna-se possível, o que não leva ao aparecimento de um resultado incorreto. Então, a expressão a + b - b e a expressão (a * b) / b podem ser otimizadas para a (a primeira também é possível durante a transferência, mas a segunda não está mais presente).

Nota A tradução do artigo é publicada no blog com a permissão do autor. Texto original: Davin McCall " Quebrar em excesso de número inteiro não é uma boa idéia ".

Links relacionados adicionais da equipe PVS-Studio:

1. Andrey Karpov. O comportamento indefinido está mais próximo do que você pensa .
2. Will Dietz, Peng Li, John Regehr e Vikram Adve. Noções básicas sobre estouro de número inteiro em C / C ++ .
3. V1026. A variável é incrementada no loop. Um comportamento indefinido ocorrerá em caso de estouro de número inteiro assinado .
4. Stackoverflow O estouro de número inteiro assinado ainda é um comportamento indefinido em C ++?