Na programação de computadores, um transbordo de inteiros (integer overflow) ocorre quando uma operação aritmética em inteiros tenta criar um valor numérico que está fora do intervalo que pode ser representado no espaço alocado para o resultado – seja maior que o valor máximo ou menor que o valor mínimo representável. A maior parte da aritmética de inteiros na computação moderna usa a representação binária de inteiros, embora a representação decimal também exista. Este artigo focará na representação binária, embora considerações semelhantes se apliquem ao outro caso. Um inteiro representado como um padrão de bits em um computador pode ser interpretado como um inteiro não sinalizado (cujo valor pode ir de 0 até um determinado máximo) ou como um inteiro sinalizado (cujo valor pode ser positivo ou negativo). Mais frequentemente, os inteiros sinalizados são representados no formato de Complemento para dois, onde o bit de ordem mais alta é interpretado como o sinal (0 para +, 1 para −). Por exemplo, em uma palavra de 32 bits, um inteiro não sinalizado tem um valor de 0 a 232 − 1 = 4.294.967.295, enquanto um inteiro sinalizado tem um valor de −231 = −2.147.483.648 a 231 − 1 = 2.147.483.647. O transbordo de inteiros resulta em um valor armazenado que é diferente do valor matemático indicado pela operação que foi realizada. Mais comumente, o padrão de bits resultante é o mesmo que se a operação fosse realizada em módulo 2W, onde W é o tamanho da palavra em bits. A operação também ativa ou desativa um ou mais sinalizadores (flags) que indicam se o transbordo ocorreu. Em alguns processadores, como unidades de processamento gráfico (GPUs) e processadores digitais de sinal (DSPs) que suportam Aritmética de saturação, os resultados transbordados podem ser limitados (clamped), ou seja, definidos para o valor mínimo no intervalo representável se o resultado estiver abaixo do mínimo, e definidos para o valor máximo no intervalo representável se o resultado estiver acima do máximo. Se não for previsto pelo programador, o transbordo de inteiros pode impactar negativamente a confiabilidade e a segurança do software.
Origem O transbordo de inteiros ocorre quando uma operação aritmética em inteiros tenta criar um valor numérico que está fora do intervalo que pode ser representado com um determinado número de dígitos. No contexto da programação de computadores, os inteiros são binários, mas qualquer sistema numérico posicional pode ter um resultado inválido em uma operação aritmética se as posições forem limitadas. Como mostrado no exemplo do odômetro, usando o sistema decimal, com a restrição de 6 posições (dígitos), a seguinte operação terá um resultado inválido: 999999 + 1. Da mesma forma, um sistema binário limitado a 4 posições (bits) terá um resultado inválido para a seguinte operação: 1111 + 0001. Para ambos os exemplos, os resultados terão um valor que excede o intervalo que pode ser representado pelas restrições. Outra forma de encarar este problema é que a operação na posição mais significativa gera um transporte (vai um) que requer a alocação de outra posição/dígito/bit, quebrando as restrições impostas. Todos os inteiros na programação de computadores possuem restrições de um valor máximo e de um valor mínimo. Os fatores primários para determinar o intervalo são a alocação de bits e se o tipo é sinalizado ou não sinalizado. O inteiro padrão depende da plataforma e da linguagem de programação. Representações adicionais de inteiros podem ser menores ou maiores que o padrão. Exemplos são o inteiro curto (short integer) e o inteiro longo (long integer), respectivamente. Existe inclusive a precisão arbitrária, mas esta seria limitada por uma precisão predefinida ou pela memória disponível do sistema.
Quando uma operação aritmética não sinalizada produz um resultado maior que o valor máximo acima para um inteiro de N bits, o transbordo reduz o resultado em módulo à N-ésima potência de 2, retendo apenas os bits menos significativos do resultado e efetivamente causando um efeito de rotação (wrap around). Em particular, multiplicar ou somar dois inteiros pode resultar em um valor inesperadamente pequeno, e subtrair de um inteiro pequeno pode causar a rotação para um valor positivo grande (por exemplo, a adição de inteiros de 8 bits 255 + 2 resulta em 1, que é 257 mod 28, e de forma semelhante a subtração 0 − 1 resulta em 255, uma representação em complemento para dois de −1). Esse efeito de rotação pode causar problemas de segurança — se um valor transbordado for usado como a quantidade de bytes a ser alocada para um buffer, o buffer alocado será inesperadamente pequeno, levando potencialmente a um transbordamento de buffer (buffer overflow) que, dependendo do uso do buffer, pode por sua vez permitir a execução de código arbitrário. Se a variável for de um tipo inteiro sinalizado, o programa pode assumir que ela sempre conterá um valor positivo. Um transbordo de inteiros pode fazer com que o valor sofra rotação e se torne negativo, o que viola a premissa do programa e pode levar a comportamentos inesperados (por exemplo, a adição de inteiros de 8 bits 127 + 1 resulta em −128, o complemento para dois de 128). Uma solução para esse problema específico é usar tipos inteiros não sinalizados para valores que o programa espera e assume que nunca serão negativos.
Sinalizadores (Flags) A maioria dos computadores modernos possui sinalizadores de processador dedicados que são ativados no caso de transbordo por operações de adição e subtração. O sinalizador de transporte (carry flag) é ativado quando o resultado de uma adição ou subtração, considerando os operandos e o resultado como números não sinalizados, não cabe no número de bits fornecido. Isso indica um transbordo com um transporte (carry) ou empréstimo (borrow) a partir do bit mais significativo. O sinalizador de estouro (overflow flag) é ativado quando o resultado de uma adição ou subtração em números sinalizados não possui o sinal previsto a partir dos sinais dos operandos (por exemplo, um resultado negativo ao somar dois números positivos). Isso indica que ocorreu um transbordo e o resultado sinalizado representado na forma de Complemento para dois não caberia no número de bits fornecido. Para uma instrução ADD, isso significa que o transporte para o bit de sinal foi diferente do transporte para fora do bit de sinal.
Variações de definição e ambiguidade Para um tipo não sinalizado, quando o resultado ideal de uma operação está fora do intervalo representável do tipo e o resultado retornado é obtido por rotação, esse evento é comumente definido como um transbordo. Em contrapartida, o padrão C define que esse evento não é um transbordo, declarando que "uma computação envolvendo operandos não sinalizados nunca pode transbordar." A explicação é que o padrão define a aritmética com inteiros não sinalizados como uma aritmética modular em 2W, onde W é o tamanho da palavra, o que é matematicamente bem definido e possui apenas valores representáveis. Quando o resultado ideal de uma operação inteira está fora do intervalo representável do tipo e o resultado retornado é obtido por limitação, esse evento é comumente definido como uma saturação. O uso varia quanto ao fato de uma saturação ser ou não considerada um transbordo. Para eliminar a ambiguidade, os termos transbordo por rotação (wrapping overflow) e transbordo por saturação (saturating overflow) podem ser utilizados. O caso de uma operação inteira que produz um valor menor que o menor valor representável é às vezes chamado de subfluxo de inteiros (integer underflow), embora mais comumente seja conhecido como um tipo de transbordo. Esse uso é bastante diferente do subfluxo de ponto flutuante (floating-point underflow), que se refere a um valor de ponto flutuante que está próximo demais de zero.
Comportamento inconsistente O comportamento na ocorrência de transbordo pode não ser consistente em todas as circunstâncias. Por exemplo, na linguagem Rust, embora funcionalidades sejam fornecidas para dar escolha e controle aos usuários, o comportamento para o uso básico de operadores matemáticos é nativamente fixo; no entanto, esse comportamento fixo difere entre um programa compilado no modo de depuração (debug) e um compilado no modo de produção (release). Em C, o transbordo de inteiros não sinalizados é definido para efetuar rotação, enquanto o transbordo de inteiros sinalizados causa comportamento indefinido.
Métodos para mitigar problemas de transbordo de inteiros
Detecção A implementação de detecção de transbordo em tempo de execução UBSan (analisador de comportamento indefinido) está disponível para compiladores C. No Java 8, existem métodos sobrecarregados, como por exemplo o Math.addExact(int,int), que lançará uma exceção ArithmeticException em caso de transbordo. A Equipe de Resposta a Emergências Computacionais (CERT) desenvolveu o modelo de inteiros As-if Infinitely Ranged (AIR), um mecanismo amplamente automatizado para eliminar o transbordo e o truncamento de inteiros em C/C++ usando o tratamento de erros em tempo de execução.
Prevenção Ao alocar variáveis com tipos de dados que sejam grandes o suficiente para conter todos os valores que possam vir a ser calculados e armazenados nelas, é sempre possível evitar o transbordo. Mesmo quando o espaço disponível ou os tipos de dados fixos fornecidos por uma linguagem de programação ou ambiente são limitados demais para permitir alocações defensivas com tamanhos generosos, ordenar cuidadosamente as operações e verificar os operandos antecipadamente permite garantir a priori que o resultado nunca será maior do que o espaço de armazenamento disponível. Ferramentas de análise estática, verificação formal e técnicas de desenvolvimento por contrato podem ser usadas para assegurar de forma mais robusta que um transbordo não ocorra acidentalmente.
Tratamento Se for previsto que um transbordo possa ocorrer, testes podem ser inseridos no programa para detectar quando ele acontece, ou está prestes a acontecer, executando outro processamento para mitigá-lo. Por exemplo, se um resultado importante calculado a partir da entrada do usuário transbordar, o programa pode parar, rejeitar a entrada e talvez solicitar ao usuário uma entrada diferente, em vez de prosseguir com a entrada inválida transbordada e provavelmente funcionar mal como consequência. As CPUs geralmente possuem uma forma de detectar isso para suportar a adição de números maiores que o tamanho de seus registradores, tipicamente usando um bit de status. A técnica é chamada de aritmética de precisão múltipla. Assim, é possível realizar adições com a largura de um byte em operandos mais amplos que um byte: primeiro soma-se os bytes inferiores, armazena-se o resultado e verifica-se o transbordo; depois soma-se os bytes superiores e, se necessário, adiciona-se o transporte (carry) dos bytes inferiores, armazenando então o resultado. Tratar o possível transbordo de um cálculo pode, às vezes, apresentar uma escolha entre realizar uma verificação antes do cálculo (para determinar se o transbordo irá ou não ocorrer) ou depois dele (para considerar se ele provavelmente ocorreu com base no valor resultante). Como algumas implementações podem gerar uma condição de interrupção no transbordo de inteiros, os programas mais portáveis testam antes de realizar a operação que poderia transbordar.
Suporte a linguagens de programação As linguagens de programação implementam vários métodos de mitigação contra um transbordo acidental: Ada e certas variantes de linguagens funcionais disparam uma condição de exceção no transbordo, enquanto o Python (desde a versão 2.4) converte de forma transparente a representação interna do número para acompanhar seu crescimento, eventualmente representando-o como long – cuja capacidade é limitada apenas pela memória disponível. Em linguagens com suporte nativo para aritmética de precisão arbitrária e segurança de tipos (como Python, Smalltalk ou Common Lisp), os números são promovidos para um tamanho maior automaticamente quando ocorrem transbordos, ou exceções são lançadas (condições sinalizadas) quando existe uma restrição de intervalo. O uso de tais linguagens pode ser útil para mitigar esse problema. No entanto, em algumas dessas linguagens, ainda são possíveis situações em que um transbordo de inteiros ocorra. Um exemplo é a otimização explícita de um caminho de código que é considerado um gargalo pelo profiler. No caso do Common Lisp, isso é possível usando uma declaração explícita para anotar o tipo de uma variável para uma palavra com tamanho de máquina (fixnum) e reduzir o nível de segurança de tipos para zero para um bloco de código específico. Em forte contraste com linguagens mais antigas como C, algumas linguagens mais recentes como Rust fornecem funções integradas que permitem a detecção fácil e a escolha do usuário sobre como o transbordo deve ser tratado caso a caso. Em Rust, embora o uso de operadores matemáticos básicos careça nativamente de tal flexibilidade, os usuários podem, alternativamente, realizar cálculos por meio de um conjunto de métodos fornecidos por cada um dos tipos primitivos inteiros. Esses métodos dão aos usuários várias escolhas entre realizar uma operação "verificada" (checked ou overflowing, que indica se o transbordo ocorreu ou não por meio do tipo de retorno); uma operação não verificada (unchecked); uma operação que realiza rotação (wrapping); ou uma operação que realiza saturação nos limites numéricos.
Aritmética saturada Na computação gráfica ou no processamento de sinais, é comum trabalhar com dados que variam de 0 a 1 ou de −1 to 1. Por exemplo, considere uma imagem em escala de cinza onde 0 representa o preto, 1 representa o branco e os valores intermediários representam tons de cinza. Uma operação que se pode desejar suportar é o clareamento da imagem multiplicando cada pixel por uma constante. A aritmética saturada permite simplesmente multiplicar de forma cega cada pixel por essa constante sem se preocupar com o transbordo, limitando-se a um resultado razoável no qual todos os pixels maiores que 1 ("mais brilhantes que o branco") simplesmente se tornam brancos, e todos os valores "mais escuros que o preto" se tornam pretos.
Exemplos O transbordo aritmético imprevisto é uma causa bastante comum de erros de programa (bugs). Esses bugs de transbordo podem ser difíceis de descobrir e diagnosticar porque podem se manifestar apenas para conjuntos de dados de entrada muito grandes, que são menos propensos a serem usados em testes de validação. Calcular a média aritmética de dois números somando-os e dividindo por dois, como feito em muitos algoritmos de busca, causa erro se a soma (embora não a média resultante) for grande demais para ser representada e, portanto, transbordar. Entre 1985 e 1987, o transbordo aritmético nas máquinas de radioterapia Therac-25, juntamente com a falta de controles de segurança de hardware, causou a morte de pelo menos seis pessoas por overdoses de radiação. Um transbordo aritmético não tratado no software de controle de direção dos motores foi a causa primária do acidente no voo inaugural de 1996 do foguete Ariane 5 (Voo 501). O software havia sido considerado livre de bugs porque tinha sido usado em muitos voos anteriores, mas aqueles utilizavam foguetes menores que geravam aceleração menor que o Ariane 5. De forma frustrante, a parte do software na qual ocorreu o erro de transbordo nem sequer precisava estar rodando no Ariane 5 no momento em que causou a falha do foguete: tratava-se de um processo de regime de lançamento para um antecessor menor do Ariane 5 que havia permanecido no software quando este foi adaptado para o novo foguete. Além disso, a verdadeira causa da falha foi uma falha na especificação de engenharia sobre como o software lidava com o transbordo quando este era detectado: ele realizava um despejo de diagnóstico (dump) em seu barramento, que estaria conectado a equipamentos de teste durante o desenvolvimento, mas estava conectado aos motores de direção do foguete durante o voo; o despejo de dados forçou o bocal do motor totalmente para um lado, o que deixou o foguete fora de controle aerodinâmico e precipitou sua rápida desintegração no ar. O Microsoft Macro Assembler versão 1.00 (1981), e provavelmente todos os outros programas construídos pelo mesmo compilador Pascal, possui um transbordo de inteiros e erro de sinal no código de configuração da pilha que o impede de rodar em máquinas MS-DOS mais novas ou emuladores sob algumas configurações comuns com mais de 512 KiB de memória. O programa trava ou exibe uma mensagem de erro e fecha. Em 30 de abril de 2015, a Administração Federal de Aviação dos EUA anunciou que ordenaria aos operadores de Boeing 787 que reiniciassem seu sistema elétrico periodicamente, para evitar um transbordo de inteiros que poderia levar à perda de energia elétrica e à ativação da Turbina de ar de impacto, e a Boeing distribuiu uma atualização de software no quarto trimestre. A Agência Europeia para a Segurança da Aviação seguiu a recomendação em 4 de maio de 2015. O erro acontece após 231 centésimos de século/segundo (cerca de 248 dias), indicando um inteiro sinalizado de 32 bits. Em agosto de 2016, uma máquina de Cassino no Resorts World imprimiu um bilhete de prêmio de $42.949.672,76 como resultado de um bug de transbordo. O cassino recusou-se a pagar essa quantia, chamando-a de mau funcionamento, usando em sua defesa que a máquina declarava claramente que o prêmio máximo era de $10.000, de modo que qualquer prêmio que excedesse isso tinha que ser o resultado de um bug de programação. A Comissão de Jogos do Estado de Nova York decidiu a favor do cassino.
Videogames Em Super Mario Bros. para o NES, o número armazenado de vidas é um byte sinalizado (variando de −128 a 127), o que significa que o jogador pode ter 127 vidas com segurança, mas quando o jogador atinge sua 128a vida, o contador sofre rotação e passa para zero vidas (embora o contador gráfico fique com falhas antes que isso aconteça) e para de contar. Dessa forma, se o jogador morrer em seguida, ocorre um "fim de jogo" (game over) imediato. Isso é causado pelo transbordo de dados do jogo, que foi um erro de programação, pois os desenvolvedores podem não ter pensado que tal número de vidas seria razoavelmente obtido em uma partida completa. No jogo de arcade Donkey Kong, é impossível avançar além do nível 22 por causa de um transbordo de inteiros em seus cálculos de tempo/bônus. O jogo determina o tempo/bônus pegando o número do nível em que o usuário está, multiplicando-o por 10 e somando 40. Quando se chega ao nível 22, o número de tempo/bônus é 260, que é grande demais para o seu registrador de valor de 8 bits (limite de 256), então ele transborda para um valor de 4 — tempo curto demais para terminar o nível. O transbordo é a causa do nível de "tela dividida" (split-screen) em Pac-Man. Esse bug também causou as Far Lands no Minecraft Java Edition, que existiram do período de desenvolvimento Infdev até a versão Beta 1.7.3; o erro foi corrigido na Beta 1.8. O mesmo bug também existia no Minecraft Bedrock Edition, mas desde então foi corrigido.
Veja também Vai um Aritmética modular Ghandi nuclear, uma lenda urbana relacionada a esse fenômeno
Referências
Ligações externas Phrack #60, Basic Integer Overflows WASC Threat Classification – Integer Overflows Understanding Integer Overflow in C/C++ Padrão ISO C11