维基百科

整数溢出

在计算机编程中，当算术运算试图创建一个超出可用位数表示范围（大于最大值或小于最小值）的数值时，就会发生整数溢出错误。

整数溢出可以通过里程表溢出来表示。当所有数字都为最大值9时，当数字再增加时，因为没有更高位的数字，导致所有数字重置为0。

整数溢出的表现形式可分为：无符号整数上溢、无符号整数下溢、有符号整数上溢、有符号整数下溢[1]。

整数溢出错误会导致软件运算结果出错，1996年亞利安5號運載火箭爆炸，2004年Comair航空公司航班停飞事故都是整数溢出造成的[2]。

来源 编辑

处理器的寄存器宽度决定了寄存器中可表示值的范围。虽然大部分计算机可以对内存操作数完成多精度算术，允许對任意位数的值進行操作，避免溢出，但是寄存器宽度限制了每个操作（例如加法或减法）只需要一个指令的数的大小。典型的无符号整数二进制寄存器宽度包括：

  • 4位：最大可表示值 24 - 1 = 15
  • 8位：最大可表示值 28 − 1 = 255
  • 16位：最大可表示值 216 − 1 = 65,535
  • 32位：最大可表示值 232 − 1 = 4,294,967,295 （截止到2005年个人电脑最普通的宽度），
  • 64位：最大可表示值 264 − 1 = 18,446,744,073,709,551,615 （截止到2021年个人电脑中央处理器（CPU）的最普通宽度），
  • 128位：最大可表示值 2128 − 1 = 340,282,366,920,938,463,463,374,607,431,768,211,455

当无符号算术运算产生大于N位整数最大值的结果时，溢出使结果对2的N次方取模，只保留结果的最低N位，有效地引起“绕回”。

例如，两个整数相乘或相加可能会产生小到预期之外的结果，數值較小的整数被减至負數時可能绕回到一个大正数。（例如，8位整数加法255+2的结果是1，也就是 ，相似的，减法0-1的结果是255，是-1的补码表示）。

这种绕回可能会导致安全性损害——如果溢出的值被用作分配给缓冲区的字节数，则将被分配的缓冲区会意想不到的小，可能导致缓冲区溢出。根据缓冲区的使用情况，这可能会导致任意代码执行。

如果变量是有符号整数类型，程序可能会假定它总是包含一个正的值。整数溢出可导致值被绕回，成为负数，违背了程序的假定，可能产生意料之外的结果（例如，8位整数加法127+1的结果是-128,它是128的补码）。这个特定问题的解决方案是于程序中必然為正數的值使用无符号整数类型。

标识位 编辑

大多数计算机都有两个专用的处理器标识位来检查溢出情况。

当加法或减法的结果（将操作数和结果视为无符号数）不符合给定的位数时，进位标志（英语：carry flag）设置为1。 这表示带有从最高有效位进位或借位的溢出。 紧随其后的带有“带进位的加法”或“带借位的减法”操作将使用该标志的内容来修改包含该多字值较高部分的寄存器或内存。

当对有符号数的运算结果没有从操作数的符号中预测的符号时，溢出标志（英语：overflow flag）设置为1，例如，将两个正数相加时的结果为负数。 这表明发生了溢出，并且以补码形式表示的带符号结果不符合给定的位数。

定义变种和歧义 编辑

对于无符号类型，当操作的理想结果在该类型可表示范围之外，且返回结果被绕回时，这次事件通常被定义为溢出。作为对照，C11标准定义这类事件不是溢出，并声称“包含无符号操作数的运算不可能溢出。”[3]

当整数运算的理想结果在该类型可表示范围之外，且返回结果被限制时，这次事件通常被定义为饱和。溢出是否是饱和的，会使使用有所不同。 为了消除歧义，可以使用术语溢出时绕回[4]和溢出时饱和[5]。

术语下溢最常用于浮点数学而不是整数数学。[6] 但是，可以找到许多对整数下溢的引用。[7] [8][9][10][11]当使用术语整数下溢时，这意味着理想结果比输出类型的可表示值更接近负无穷大。 当使用术语整数下溢时，溢出的定义可能包括所有类型的溢出，或者它可能只包括理想结果比输出类型的可表示值更接近正无穷大的情况。

当一个操作的理想结果不是一个精准整数时，在边缘情况下溢出的含义可能是模棱两可的。 考虑理想结果的值为 127.25 并且输出类型的最大可表示值为 127 的情况。如果将溢出定义为理想值超出输出类型的可表示范围，那么这种情况将被归类为溢出。 对于具有明确舍入行为的操作，溢出分类可能需要推迟到应用舍入之后。 C11 标准[3]定义从浮点到整数的转换必须向零舍入。 如果使用 C 将浮点值 127.25 转换为整数，则应首先应用舍入以给出理想的整数输出 127。由于舍入后的整数在输出范围内，C 标准不会将此转换归类为溢出 。

不一致的行为 编辑

出现溢出时的行为不一定在所有情形下一致。例如，在 Rust 语言中，虽然提供给用户选择和控制的功能，但数学运算符的基本使用行为自然是固定的； 但是，这种固定行为在“调试”模式下构建的程序和“发布”模式下构建的程序之间是不同的。[12]在 C 中，无符号整数溢出被定义为回绕，而有符号整数溢出导致未定义的行为。

举例 编辑

意外的算术溢出是程序错误的常见原因。此类溢出错误可能难以发现和诊断，因为它们可能仅针对非常大的输入数据集表现出来，而这些数据集不太可能用于验证测试。

如在许多搜索算法中所做的，通过将两个数字相加并除以二来获取算术平均值，如果总和（尽管平均值没有）太大而无法表示，并因此溢出，则会导致错误。[13]

发动机转向软件中未处理的算术溢出是 1996 年阿丽亚娜-5运载火箭首飞坠毁的主要原因。[14] 该软件被认为没有错误，因为它已在许多以前的飞行中使用过，但那些使用过的火箭较小，产生的加速度比阿丽亚娜 5 号低。令人沮丧的是，发生溢出错误的软件部分甚至不需要在导致火箭失败时运行：这是一个较小的阿丽亚娜-5 前身的发射机制过程，当它为新火箭被改写时，仍然保留在软件中。此外，失败的真正原因是软件在检测到溢出时如何处理溢出的工程规范中存在缺陷：它向其总线进行了诊断转储，该总线在开发期间的软件测试期间本应连接到测试设备但在飞行过程中连接到火箭转向马达；数据转储将发动机喷嘴猛烈推向一侧，这使火箭失去了空气动力学控制，并导致其在空中迅速解体。 [15]

2015 年 4 月 30 日，美国联邦航空管理局宣布将命令波音 787 操作员定期重置其电气系统，以避免可能导致电力损失和冲压空气涡轮部署的整数溢出，波音在第四季度部署了软件更新。[16]欧洲航空安全局于 2015 年 5 月 4 日跟进。[17] 错误发生在 2³¹ 厘秒（约 249 天）后，表示一个 32 位有符号整数。

溢出错误在一些电脑游戏中很明显。在 NES 的《超级马里奥兄弟》中，在一个有符号字节中存储生命数（范围从 -128 到 127），这意味着玩家可以安全地拥有 127 条生命，但是当玩家达到第 128 条生命时，会导致计数器滚动到零（尽管在此之前数字计数器出现故障）然后死亡，游戏即时结束。这是由数据溢出引起的，因为开发人员可能没有想到可以赢得上述数量的生命。在街机游戏《大金刚》中，由于时间/奖励的整数溢出，不可能超过 22 级。游戏将用户所在的级别数乘以 10 再加上 40。当他们达到 22 级时，时间/奖励数为 260，这对于其 8 位 256 值寄存器来说太大了，因此它会自行重置到 0 并给出剩余的 4 作为时间/奖励 - 太短而无法完成关卡。在《小金刚算数》中，当试图计算一个超过 10,000 的数字时，它只显示前 4 位数字。溢出是《吃豆人》中著名的“分屏”关卡的原因。[18]《文明》中臭名昭著的核甘地（英语：Nuclear Gandhi）漏洞据称是由整数下溢引起的，当游戏试图从甘地的默认攻击等级 1 中减去 2 时，将其设置为 255，比正常最大值 10 高出近 26 倍。（席德·梅尔在一次采访中声称这实际上是故意的。[19][20]）这样的错误也导致了从 Infdev 开发阶段到 Beta 1.7.3 存在的我的世界中的边境之地；它后来在 Beta 1.8 中得到修复，但仍然存在于 Minecraft 袖珍版和 Windows 10 版中。[21]在超级任天堂娱乐系统 (NES) 游戏兰博基尼美国挑战赛（英语：Lamborghini American Challenge）中，玩家可以通过在支付比赛费用后被罚款超过剩余金额的限制，从而导致他们在比赛中的金额低于 0 美元，这会导致整数出现故障。并给予玩家 65,535,000 美元，比它在负数后的收益多出 65,535,000 美元。[22] 在潜行者：晴空中也发生了类似的故障，玩家可以在没有足够资金的情况下通过快速旅行而陷入负数，然后继续进行玩家被抢劫并拿走所有货币的事件。在游戏试图将玩家的钱带走直到 0 美元后，玩家将获得 2147482963 游戏币。[23]

 
Pascal 编译器产生的堆栈设置代码中的整数符号错误阻止了 IBM–Microsoft 宏汇编器 (MASM) 版本 1.00，一个 1981 年的 DOS 程序，以及许多其他使用相同编译器编译的程序，在某些超过 512 KB 内存d配置下运行。

IBM–Microsoft 宏汇编器 (MASM) 版本 1.00，以及可能由同一 Pascal 编译器构建的所有其他程序，在堆栈设置代码中存在整数溢出和符号错误，这会阻止它们在较新的常见的具有超过 512 KB 内存配置的 DOS 机器或模拟器上运行。 程序挂起或显示错误消息，并退出到 DOS。[24]

2016 年 8 月，Resorts World（英语：Resorts World） 赌场的一台赌场机器因溢出错误而打印出 42,949,672.76 美元的奖券。 赌场拒绝支付这笔款项，称其为故障，在他们的辩护中用了机器明确表示最高支付为 10,000 美元，因此任何超过该金额的奖金都必须是编程错误的结果。 纽约州博彩委员会作出有利于赌场的裁决。[25]

参考文献 编辑

  1. ^ 高猛，滕俊元，王政. 航天嵌入式软件整数溢出的形式化验证方法. 软件学报. 2021-10-09, 32 (10): 2977–2992 [2021-10-20]. （原始内容存档于2021-10-20）. 
  2. ^ Seacord, R. Secure coding in C and C++ of strings and integers. IEEE Security Privacy. 2006-01, 4 (1): 74–76 [2021-10-20]. ISSN 1558-4046. doi:10.1109/MSP.2006.22. （原始内容存档于2021-10-22）. 
  3. ^ 3.0 3.1 ISO staff. ISO/IEC 9899:2011 Information technology - Programming languages - C. ANSI.org. [2022-08-11]. （原始内容存档于2017-06-30）. 
  4. ^ Wrap on overflow - MATLAB & Simulink. www.mathworks.com. [2022-08-11]. （原始内容存档于2022-08-11）. 
  5. ^ Saturate on overflow - MATLAB & Simulink. www.mathworks.com. [2022-08-11]. （原始内容存档于2022-08-11）. 
  6. ^ 算术下溢
  7. ^ CWE - CWE-191: Integer Underflow (Wrap or Wraparound) (3.1). cwe.mitre.org. [2022-08-11]. （原始内容存档于2022-09-01）. 
  8. ^ Overflow And Underflow of Data Types in Java - DZone Java. dzone.com. [2022-08-11]. （原始内容存档于2022-08-11）. 
  9. ^ Mir, Tabish. Integer Overflow/Underflow and Floating Point Imprecision. medium.com. 4 April 2017 [2022-08-11]. （原始内容存档于2019-10-31）. 
  10. ^ Integer underflow and buffer overflow processing MP4 metadata in libstagefright. Mozilla. [2022-08-11]. （原始内容存档于2022-08-23）. 
  11. ^ Avoiding Buffer Overflows and Underflows. developer.apple.com. [2022-08-11]. （原始内容存档于2018-02-10）. 
  12. ^ Operator expressions - The Rust Reference. Rust-lang.org. [2021-02-12]. （原始内容存档于2022-10-08）. 
  13. ^ Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken. googleresearch.blogspot.co.uk. [2022-08-11]. （原始内容存档于2016-03-11）. 
  14. ^ Gleick, James. A Bug and A Crash. The New York Times. 1 December 1996 [17 January 2019]. （原始内容存档于2022-10-05）. 
  15. ^ 阿丽亚娜5号发射失败事故的官方报告。
  16. ^ Mouawad, Jad. F.A.A. Orders Fix for Possible Power Loss in Boeing 787. New York Times. 30 April 2015 [2022-08-11]. （原始内容存档于2022-09-06）. 
  17. ^ US-2015-09-07: Electrical Power – Deactivation. Airworthiness Directives. European Aviation Safety Agency. 4 May 2015 [2022-08-11]. （原始内容存档于2015-06-20）. 
  18. ^ Pittman, Jamey. The Pac-Man Dossier. [2022-08-11]. （原始内容存档于2015-02-14）. 
  19. ^ Meier, Sid. Funny Business. Sid Meier's Memoir!: A Life in Computer Games. W. W. Norton. 2020: 261–266. ISBN 978-1-324-00587-2. 
  20. ^ Алексей Афанасьев. История появления мифа о «Ядерном Ганди» — по версии самого Сида Мейера [The story of the appearance of the myth of "Nuclear Gandhi" - according to Sid Meier himself]. DTF.ru​（俄语）. 2020-09-16 [2020-09-18]. （原始内容存档于2020-09-18） （俄语）. 
  21. ^ Minecraft Wiki. Minecraft Wiki. [2022-08-11]. （原始内容存档于2024-01-15）. 
  22. ^ Archived at Ghostarchive and the Wayback Machine: Lamborghini American Challenge SPEEDRUN (13:24). YouTube. [2022-08-11]. （原始内容存档于2022-08-11）. 
  23. ^ Money glitch :: S.T.A.L.K.E.R.: Clear Sky General Discussions. [2022-08-11]. （原始内容存档于2022-08-11）. 
  24. ^ Lenclud, Christophe. Debugging IBM MACRO Assembler Version 1.00. 
  25. ^ Kravets, David. Sorry ma'am you didn't win $43M – there was a slot machine 'malfunction'. Ars Technica. June 15, 2017 [2022-08-11]. （原始内容存档于2022-08-11）. 
取自“https://zh.wikipedia.org/w/index.php?title=整数溢出&oldid=80573002”