direita|O transbordo de inteiros pode ser demonstrado através do estouro de um odômetro, uma versão mecânica do fenômeno. Todos os dígitos são definidos no máximo 9 e o próximo incremento do dígito branco causa uma cascata de adições com transporte que zera todos os dígitos, mas não há um dígito de ordem superior (o dígito dos milhões) para mudar para 1, então o contador reinicia em zero. Isso é o efeito de rotação (wrapping) em contraste com a saturação.|350x350px
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 , enquanto um inteiro sinalizado tem um valor de a .
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: . Da mesma forma, um sistema binário limitado a 4 posições (bits) terá um resultado inválido para a seguinte operação: . 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.
+ Limites típicos de inteiros Bits Alias Intervalo Intervalo sinalizado Intervalo não sinalizado 8-bit byte, sbyte, octeto 28 − 1 16-bit word, short, int16, uint16 216 − 1 32-bit int32, uint32 232 − 1 64-bit int64, uint64 264 − 1 128-bit int128, uint128 2128 − 1
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 resulta em 1, que é , e de forma semelhante a subtração 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 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 + Tratamento de transbordo de inteiros em várias linguagens de programação Linguagem Inteiro não sinalizado Inteiro sinalizado Ada módulo do módulo do tipo raise Constraint_Error C, C++ módulo potência de dois comportamento indefinido C# módulo potência de 2 em contexto não verificado; System.OverflowException é lançada em contexto verificado (checked) Java módulo potência de dois (char é o único tipo primitivo não sinalizado em Java) módulo potência de dois JavaScript todos os números são ponto flutuante de precisão dupla, exceto o BigInt MATLAB Inteiros integrados saturam. Inteiros em ponto fixo são configuráveis para rotação ou saturação Python 2 converte para o tipo long (bigint) Scheme converte para bigNum Simulink configurável para rotação ou saturação Smalltalk converte para LargeInteger Swift Causa erro, a menos que sejam usados operadores especiais de transbordo.
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.As-if Infinitely Ranged Integer Model
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.