整数溢出是指整数运算的数学结果超出了该运算结果类型所能表示的范围。它主要出现在使用固定位数的比特来表示整数的计算系统中。根据硬件、编程语言、具体运算和执行设置的不同,溢出可能使数值回绕、引发异常、将结果限制在边界值,或触发语言未作任何要求的行为。溢出有时是有意为之,例如在某些密码学计算中;有时则是错误,会导致错误结果,并可能造成安全漏洞。
表示方式与范围
固定位宽的整数类型只能表示有限个值。一个具有 位的无符号整数通常表示以下范围:
使用二进制补码表示的有符号整数,其范围为:
例如,8 位无符号整数的范围是 0 到 255,而采用二进制补码表示的 8 位有符号整数的范围是 −128 到 127。数学上的和 无法用上述无符号类型表示;同样, 也无法用上述有符号类型表示。
采用二进制补码表示的有符号整数,其范围并不对称:负数比正数多一个。因此,如果结果必须保持为同一种有符号类型,那么对最小可表示值取相反数就会溢出。对它取绝对值也存在同样的可表示性问题。
溢出并不限于加法。减法、乘法、乘方以及某些移位运算都可能超出可表示范围。有符号除法也有一种边界情况:将最小的二进制补码整数除以 ,得到的正数无法用同一类型表示。除以零是另一类错误,并非整数溢出。
溢出、下溢与转换
低于整数类型最小值的结果有时称为整数下溢。例如,无符号减法 的结果低于无符号整数的取值范围。在许多技术讨论中,无论结果越过上界还是下界,都统称为整数溢出。
这与浮点下溢不同,后者涉及接近零的数值以及浮点表示的限制。浮点溢出和下溢遵循不同的规则,通常采用IEEE 754浮点运算标准中的规则。
将一个值转换为位宽更窄的整数类型也可能丢失信息。严格来说,这是超出范围的类型转换,而非算术溢出,不过二者通常都被归入整数相关错误。一次计算可能在较宽的类型中正确完成,直到赋值给较窄的目标类型时才出现错误。
溢出的处理方式
硬件和软件中采用了多种算术模型。
回绕算术
回绕算术将结果对 取模:
这是模算术的一种应用。因此,对于 8 位无符号整数, 的结果为 4。
当回绕后的位模式被解释为采用二进制补码表示的有符号整数时,数值可能改变符号。在明确规定回绕的 8 位有符号整数模型中, 会变成 。这种行为在机器指令层面很常见,但不能假定每一种编程语言都如此。
当模运算行为是算法规范的一部分时,回绕算术很有用。它见于密码散列函数、校验和、伪随机数生成器以及循环计数器。在这些场景中,回绕可能是预期结果,而非缺陷。
检查算术
检查算术会检测超出范围的结果并报告失败。报告机制可以是异常、陷阱、错误返回值,或单独的溢出标志。
仅仅检测出溢出,并不能决定程序应如何恢复。根据应用的不同,运算失败后可能需要拒绝输入、放弃计算,或改用范围更大的表示方式。
饱和算术
饱和算术将超出范围的结果替换为距离最近的可表示边界值:
其中, 和 分别是该类型的最小值和最大值。
对于 8 位无符号类型,250 与 10 的饱和加法结果为 255。饱和处理在图像处理和信号处理中很有用,因为在这些场景下,一个很大的正数变成很小的数或负数,通常是不希望出现的。不过,饱和处理仍然改变了数学结果,不能与检查算术互相替代。
任意精度算术
任意精度算术会随着数值增大而扩展其表示,而不是规定固定的数值范围。它在实践中受到可用内存、执行时间和实现条件的限制。
它可以避免通常的固定位宽溢出,但不能保证整个程序都不存在范围错误。将大整数转换到固定位宽的字段中、传递给原生库,或将其用作内存分配大小时,仍然可能受到范围限制。
硬件行为
中央处理器通常使用固定位宽的寄存器进行整数运算。加法指令可能只保留低位,同时在状态标志中记录额外信息。
通常需要区分以下两种标志:
- 进位:表示加法产生了超出无符号结果位宽的进位。
- 有符号溢出:表示结果超出了有符号数的可表示范围。
这是两种不同的情况。在 8 位加法中, 会产生进位,但相应的有符号运算 不会溢出。反过来, 作为有符号运算会溢出,却不会产生超出第八位的进位。
对于二进制补码加法,当两个同号操作数产生的存储结果与它们符号相反时,就发生了有符号溢出。对于减法,当两个操作数异号,且存储结果的符号与第一个操作数不同,就发生了有符号溢出。
并非所有指令集架构都提供相同的标志或指令。有些架构提供可触发陷阱的运算或专门的饱和指令。因此,必须分别考虑硬件行为和源语言行为:编译器受语言规则约束,而不只是遵循某条处理器指令的表面行为。
编程语言语义
不同语言对溢出的处理差异很大,有些语言还提供多种算术模式。
C 和 C++
在 C编程语言和 C++ 中,无符号算术被定义为模运算,模数为无符号结果类型的最大可表示值加一。有符号算术溢出通常属于未定义行为:对于执行了这种运算的程序,语言不作任何要求。
这一区别会影响优化。对于有符号整数 x,编译器可以将 x + 1 > x 简化为真,因为在通常情况下,使该比较不成立的唯一情形涉及有符号溢出,而具有已定义行为的执行不允许出现这种溢出。程序无法可靠地使用此类表达式来检测已经发生的有符号溢出。
整数提升也很重要。对小整数类型的运算可能会先提升为 int 后再执行,因此,表面上的 8 位运算实际上可能是一次较宽的计算,随后再进行窄化转换。仅凭操作数的声明,并不总能确定运算的位宽。
C23 通过 <stdckdint.h> 引入了检查整数算术功能,包括 ckd_add、ckd_sub 和 ckd_mul。编译器通常也会提供用于检测溢出的内置函数。
其他语言模型
- Java: 对
int和long的普通算术运算采用固定位宽结果,并为加法、减法和乘法规定了回绕行为。Math.addExact等方法则提供了带溢出检查的替代方案。 - Rust: 普通整数运算是否检查溢出可以配置;开发配置通常启用检查,发布配置通常禁用检查。显式的检查、回绕、饱和以及同时返回溢出标志的方法,可以使预期行为不受这一默认设置影响。
- Python: 内置整数采用任意精度,因此普通整数算术不受固定机器位宽的限制。固定位宽的外部接口和数值数组库可能具有不同的行为。
- C#: 整数运算可以在检查或不检查溢出的上下文中求值。溢出的处理方式取决于上下文、编译器设置,以及表达式是否在编译期求值。
JavaScript 还需要进一步区分。它的普通 Number 值采用二进制浮点表示,因此,当整数足够大而失去精确性时,这并不是通常意义上的固定位宽整数回绕。BigInt 支持任意精度整数,而位运算和固定位宽存储格式则各自有相应的转换规则和位宽规则。
对正确性与安全性的影响
整数溢出可能导致计数器、时间戳、财务计算、数组索引和终止条件出错。计数器如果意外回绕,可能使循环运行时间超过预期,或永远无法达到终止值。
一个经典的算法示例是计算两个非负索引的中点:
mid = (low + high) / 2
即使两个索引都有效,它们的和仍然可能溢出。在满足适当的整数类型和大小顺序假设时,以下等价表达式
mid = low + (high - low) / 2
可以避免这一中间结果溢出问题。该问题与二分查找及相关算法有关。这些假设很重要:对于任意有符号端点,这种替代写法并不总是安全的。
在网络安全领域,如果错误数值越过了信任边界或内存安全边界,溢出就可能成为安全漏洞。例如,程序可能按下式计算内存分配大小:
如果乘法结果回绕成一个较小的值,程序分配的内存就可能少于预期。随后若仍按原始数量写入数据,就可能造成缓冲区溢出。
其他后果包括绕过边界检查、错误的资源限制,以及拒绝服务攻击。有符号与无符号类型之间的转换会加剧这些问题:一个负数转换为无符号类型后,可能变成一个非常大的正数。
整数溢出与缓冲区溢出是不同的概念。前者是算术结果的可表示性问题;后者是访问超出了内存缓冲区的边界。二者都可以在另一种问题未发生时独立出现。
检测与预防
要避免意外溢出,需要选择符合应用需求的算术语义,并检查中间运算,而不只是最终结果。
对于最大值为 的无符号加法,可表示的非负值 和 之和在范围内,当且仅当:
对于 的无符号乘法,相应条件为:
这些前置条件避免了直接计算可能溢出的结果。有符号运算的检查需要考虑更多情况,因为操作数可能异号,而且负数范围并不对称。检查算术原语可以直接表达这类要求,无须手动逐一处理各种情况。
使用更宽的中间类型可能有所帮助,但必须在运算之前扩展位宽。将窄类型乘法的结果赋给更宽的目标类型,无法修复已经发生的溢出。此外,还需要有充分依据,证明更宽类型的取值范围足够大。
常见的验证技术包括:
- 围绕最小值、最大值、零和符号变化进行边界测试。
- 利用程序静态分析识别可能溢出的表达式和不安全的类型转换。
- 使用运行时插桩,在执行过程中报告选定类别的算术违规。
- 使用模糊测试探索不常见的输入与控制流组合。
- 使用明确的算术模型和中间值范围约束进行形式验证。
带有运行时检查的测试无法证明所有执行路径都是安全的,而静态工具也可能报告实际上不会发生的情况。形式化推理必须区分数学整数与固定位宽机器整数;证明算法在无界整数上正确,并不能单凭这一点就断定其实现不存在溢出。