查看“︁整数溢出”︁的源代码

{{Expand language|en}}[[File:Odometer_rollover.jpg|缩略图|250x250像素|整数溢出可以通过[[里程錶|里程表]]溢出来表示。当所有数字都为最大值9时，当数字再增加时，因为没有更高位的数字，导致所有数字重置为0。]]
在[[程序设计|计算机编程中]]，当[[算术]]运算试图创建一个超出可用位数表示范围（大于最大值或小于最小值）的数值时，就会发生'''整数溢出'''错误。

整数溢出的表现形式可分为：无符号整数上溢、无符号整数下溢、有符号整数上溢、有符号整数下溢<ref>{{Cite journal|title=航天嵌入式软件整数溢出的形式化验证方法|author=高猛，滕俊元，王政|url=http://jos.org.cn/jos/article/abstract/6024|last=|last2=|first2=|date=2021-10-09|journal=软件学报|issue=10|volume=32|pages=2977–2992|last3=|first3=|last4=|first4=|access-date=2021-10-20|archive-date=2021-10-20|archive-url=https://web.archive.org/web/20211020084608/http://jos.org.cn/jos/article/abstract/6024|dead-url=no}}</ref>。

整数溢出错误会导致软件运算结果出错，1996年[[亞利安5號運載火箭]]爆炸，2004年Comair航空公司航班停飞事故都是整数溢出造成的<ref>{{Cite journal|title=Secure coding in C and C++ of strings and integers|url=https://ieeexplore.ieee.org/document/1588832/|last=Seacord|first=R.|date=2006-01|journal=IEEE Security Privacy|issue=1|doi=10.1109/MSP.2006.22|volume=4|pages=74–76|issn=1558-4046|access-date=2021-10-20|archive-date=2021-10-22|archive-url=https://web.archive.org/web/20211022211426/https://ieeexplore.ieee.org/document/1588832/|dead-url=no}}</ref>。

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

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

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

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

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

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

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

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

当对有符号数的运算结果没有从操作数的符号中预测的符号时，{{En-link|溢出标志|overflow flag}}设置为1，例如，将两个正数相加时的结果为负数。 这表明发生了溢出，并且以[[二補數|补码]]形式表示的带符号结果不符合给定的位数。

== 定义变种和歧义 ==
对于无符号类型，当操作的理想结果在该类型可表示范围之外，且返回结果被绕回时，这次事件通常被定义为溢出。作为对照，C11标准定义这类事件不是溢出，并声称“包含无符号操作数的运算不可能溢出。”<ref name=":0">{{cite web |author=ISO staff |title=ISO/IEC 9899:2011 Information technology - Programming languages - C |url=https://webstore.ansi.org/RecordDetail.aspx?sku=ISO%2FIEC+9899%3A2011 |website=ANSI.org |access-date=2022-08-11 |archive-date=2017-06-30 |archive-url=https://web.archive.org/web/20170630192036/http://webstore.ansi.org/RecordDetail.aspx?sku=ISO%2fIEC+9899%3a2011 |dead-url=no }}</ref>

当整数运算的理想结果在该类型可表示范围之外，且返回结果被限制时，这次事件通常被定义为饱和。溢出是否是饱和的，会使使用有所不同。 为了消除歧义，可以使用术语溢出时绕回<ref>{{cite web |title=Wrap on overflow - MATLAB & Simulink |url=https://www.mathworks.com/help/simulink/gui/wrap-on-overflow.html?searchHighlight=overflow&s_tid=doc_srchtitle |website=www.mathworks.com |access-date=2022-08-11 |archive-date=2022-08-11 |archive-url=https://web.archive.org/web/20220811071046/https://www.mathworks.com/help/simulink/gui/wrap-on-overflow.html?searchHighlight=overflow&s_tid=doc_srchtitle |dead-url=no }}</ref>和溢出时饱和<ref>{{cite web |title=Saturate on overflow - MATLAB & Simulink |url=https://www.mathworks.com/help/simulink/gui/saturate-on-overflow.html?searchHighlight=overflow&s_tid=doc_srchtitle |website=www.mathworks.com |access-date=2022-08-11 |archive-date=2022-08-11 |archive-url=https://web.archive.org/web/20220811071046/https://www.mathworks.com/help/simulink/gui/saturate-on-overflow.html?searchHighlight=overflow&s_tid=doc_srchtitle |dead-url=no }}</ref>。

术语下溢最常用于浮点数学而不是整数数学。<ref>[[算术下溢]]</ref> 但是，可以找到许多对整数下溢的引用。<ref>{{cite web |title=CWE - CWE-191: Integer Underflow (Wrap or Wraparound) (3.1) |url=https://cwe.mitre.org/data/definitions/191.html |website=cwe.mitre.org |access-date=2022-08-11 |archive-date=2022-09-01 |archive-url=https://web.archive.org/web/20220901032745/https://cwe.mitre.org/data/definitions/191.html |dead-url=no }}</ref> <ref>{{cite web |title=Overflow And Underflow of Data Types in Java - DZone Java |url=https://dzone.com/articles/overflow-and-underflow-data |website=dzone.com |access-date=2022-08-11 |archive-date=2022-08-11 |archive-url=https://web.archive.org/web/20220811071046/https://dzone.com/articles/overflow-and-underflow-data |dead-url=no }}</ref><ref>{{cite web |last=Mir |first=Tabish |date=4 April 2017 |title=Integer Overflow/Underflow and Floating Point Imprecision |url=https://medium.com/@taabishm2/integer-overflow-underflow-and-floating-point-imprecision-6ba869a99033 |website=medium.com |access-date=2022-08-11 |archive-date=2019-10-31 |archive-url=https://web.archive.org/web/20191031124343/https://medium.com/@taabishm2/integer-overflow-underflow-and-floating-point-imprecision-6ba869a99033 |dead-url=no }}</ref><ref>{{cite web |title=Integer underflow and buffer overflow processing MP4 metadata in libstagefright |url=https://www.mozilla.org/en-US/security/advisories/mfsa2015-147/ |website=Mozilla |access-date=2022-08-11 |archive-date=2022-08-23 |archive-url=https://web.archive.org/web/20220823233602/https://www.mozilla.org/en-US/security/advisories/mfsa2015-147/ |dead-url=no }}</ref><ref>{{cite web |title=Avoiding Buffer Overflows and Underflows |url=https://developer.apple.com/library/content/documentation/Security/Conceptual/SecureCodingGuide/Articles/BufferOverflows.html#//apple_ref/doc/uid/TP40002577-SW7 |website=developer.apple.com |access-date=2022-08-11 |archive-date=2018-02-10 |archive-url=https://web.archive.org/web/20180210232431/https://developer.apple.com/library/content/documentation/Security/Conceptual/SecureCodingGuide/Articles/BufferOverflows.html#//apple_ref/doc/uid/TP40002577-SW7 |dead-url=no }}</ref>当使用术语整数下溢时，这意味着理想结果比输出类型的可表示值更接近负无穷大。 当使用术语整数下溢时，溢出的定义可能包括所有类型的溢出，或者它可能只包括理想结果比输出类型的可表示值更接近正无穷大的情况。

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

== 不一致的行为 ==
出现溢出时的行为不一定在所有情形下一致。例如，在 [[Rust]] 语言中，虽然提供给用户选择和控制的功能，但数学运算符的基本使用行为自然是固定的； 但是，这种固定行为在“调试”模式下构建的程序和“发布”模式下构建的程序之间是不同的。<ref>{{Cite web |title=Operator expressions - The Rust Reference |url=https://doc.rust-lang.org/stable/reference/expressions/operator-expr.html#overflow |website=Rust-lang.org |access-date=2021-02-12 |archive-date=2022-10-08 |archive-url=https://web.archive.org/web/20221008020706/https://doc.rust-lang.org/stable/reference/expressions/operator-expr.html#overflow |dead-url=no }}</ref>在 C 中，无符号整数溢出被定义为回绕，而有符号整数溢出导致[[未定义行为|未定义的行为]]。

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

如在许多[[搜索算法]]中所做的，通过将两个数字相加并除以二来获取算术平均值，如果总和（尽管平均值没有）太大而无法表示，并因此溢出，则会导致错误。<ref>{{cite web |title=Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken |url=http://googleresearch.blogspot.co.uk/2006/06/extra-extra-read-all-about-it-nearly.html |website=googleresearch.blogspot.co.uk |access-date=2022-08-11 |archive-date=2016-03-11 |archive-url=https://web.archive.org/web/20160311010247/http://googleresearch.blogspot.co.uk/2006/06/extra-extra-read-all-about-it-nearly.html |dead-url=no }}</ref>

发动机转向软件中未处理的算术溢出是 1996 年[[亞利安5號運載火箭|阿丽亚娜-5运载火箭]]首飞坠毁的主要原因。<ref>{{cite web |last=Gleick |first=James |author-link=James Gleick |date=1 December 1996 |title=A Bug and A Crash |url=https://www.nytimes.com/1996/12/01/magazine/little-bug-big-bang.html |work=The New York Times |access-date=17 January 2019 |archive-date=2022-10-05 |archive-url=https://web.archive.org/web/20221005210702/https://www.nytimes.com/1996/12/01/magazine/little-bug-big-bang.html |dead-url=no }}</ref> 该软件被认为没有错误，因为它已在许多以前的飞行中使用过，但那些使用过的火箭较小，产生的加速度比阿丽亚娜 5 号低。令人沮丧的是，发生溢出错误的软件部分甚至不需要在导致火箭失败时运行：这是一个较小的阿丽亚娜-5 前身的发射机制过程，当它为新火箭被改写时，仍然保留在软件中。此外，失败的真正原因是软件在检测到溢出时如何处理溢出的工程规范中存在缺陷：它向其总线进行了诊断转储，该总线在开发期间的软件测试期间本应连接到测试设备但在飞行过程中连接到火箭转向马达；数据转储将发动机喷嘴猛烈推向一侧，这使火箭失去了空气动力学控制，并导致其在空中迅速解体。 <ref>阿丽亚娜5号发射失败事故的官方报告。</ref>

2015 年 4 月 30 日，[[美国联邦航空管理局]]宣布将命令[[波音787|波音 787]] 操作员定期重置其电气系统，以避免可能导致电力损失和[[冲压空气涡轮]]部署的整数溢出，波音在第四季度部署了软件更新。<ref>{{cite news|title=F.A.A. Orders Fix for Possible Power Loss in Boeing 787|first=Jad|last=Mouawad|work=[[New York Times]]|date=30 April 2015|url=https://www.nytimes.com/2015/05/01/business/faa-orders-fix-for-possible-power-loss-in-boeing-787.html?_r=0|accessdate=2022-08-11|archive-date=2022-09-06|archive-url=https://web.archive.org/web/20220906013638/https://www.nytimes.com/2015/05/01/business/faa-orders-fix-for-possible-power-loss-in-boeing-787.html?_r=0|dead-url=no}}</ref>[[欧盟航空安全局|欧洲航空安全局]]于 2015 年 5 月 4 日跟进。<ref>{{cite web |date=4 May 2015 |title=US-2015-09-07: Electrical Power – Deactivation |url=http://ad.easa.europa.eu/ad/US-2015-09-07 |work=Airworthiness Directives |publisher=[[European Aviation Safety Agency]] |access-date=2022-08-11 |archive-date=2015-06-20 |archive-url=https://web.archive.org/web/20150620163844/http://ad.easa.europa.eu/ad/US-2015-09-07 |dead-url=no }}</ref> 错误发生在 2³¹ 厘秒（约 249 天）后，表示一个 32 位[[有符號數處理|有符号整数]]。

溢出错误在一些电脑游戏中很明显。在 [[NES]] 的《[[超级马力欧兄弟|超级马里奥兄弟]]》中，在一个有符号字节中存储生命数（范围从 -128 到 127），这意味着玩家可以安全地拥有 127 条生命，但是当玩家达到第 128 条生命时，会导致计数器滚动到零（尽管在此之前数字计数器出现故障）然后死亡，游戏即时结束。这是由数据溢出引起的，因为开发人员可能没有想到可以赢得上述数量的生命。在街机游戏《[[大金刚 (游戏)|大金刚]]》中，由于时间/奖励的整数溢出，[[Kill screen|不可能超过 22 级]]。游戏将用户所在的级别数乘以 10 再加上 40。当他们达到 22 级时，时间/奖励数为 260，这对于其 8 位 256 值寄存器来说太大了，因此它会自行重置到 0 并给出剩余的 4 作为时间/奖励 - 太短而无法完成关卡。在《[[小金剛算數|小金刚算数]]》中，当试图计算一个超过 10,000 的数字时，它只显示前 4 位数字。溢出是《[[吃豆人]]》中著名的[[Kill screen|“分屏”关卡]]的原因。<ref>{{cite web |last=Pittman |first=Jamey |title=The Pac-Man Dossier |url=http://home.comcast.net/~jpittman2/pacman/pacmandossier.html |access-date=2022-08-11 |archive-date=2015-02-14 |archive-url=https://web.archive.org/web/20150214052159/http://home.comcast.net/~jpittman2/pacman/pacmandossier.html |dead-url=no }}</ref>《[[文明 (游戏)|文明]]》中臭名昭著的{{En-link|核甘地|Nuclear Gandhi}}漏洞据称是由整数下溢引起的，当游戏试图从甘地的默认攻击等级 1 中减去 2 时，将其设置为 255，比正常最大值 10 高出近 26 倍。（[[席德·梅爾|席德·梅尔]]在一次采访中声称这实际上是故意的。<ref>{{cite book|author=[[Sid Meier|Meier, Sid]]|chapter=Funny Business|chapter-url=|format=|url=|title=Sid Meier's Memoir!: A Life in Computer Games|orig-year=|agency=|edition=|location=|date=2020|publisher=[[W. W. Norton & Company|W. W. Norton]]|volume=|pages=261–266|series=|isbn=978-1-324-00587-2}}</ref><ref>{{cite web |author=Алексей Афанасьев |date=2020-09-16 |script-title=ru:История появления мифа о «Ядерном Ганди» — по версии самого Сида Мейера |trans-title=The story of the appearance of the myth of "Nuclear Gandhi" - according to Sid Meier himself |url=https://dtf.ru/games/210957-istoriya-poyavleniya-mifa-o-yadernom-gandi-po-versii-samogo-sida-meyera |website={{ill|DTF (website)|lt=DTF.ru|ru|DTF}} |language=ru |access-date=2020-09-18 |archive-date=2020-09-18 |archive-url=https://web.archive.org/web/20200918080738/https://dtf.ru/games/210957-istoriya-poyavleniya-mifa-o-yadernom-gandi-po-versii-samogo-sida-meyera |dead-url=no }}</ref>）这样的错误也导致了从 Infdev 开发阶段到 Beta 1.7.3 存在的[[我的世界]]中的边境之地；它后来在 Beta 1.8 中得到修复，但仍然存在于 Minecraft 袖珍版和 Windows 10 版中。<ref>{{cite web |title=Minecraft Wiki |url=https://minecraft.wiki/w/Far_Lands |website=Minecraft Wiki |access-date=2022-08-11 |dead-url=no |archive-date=2024-01-15 |archive-url=https://web.archive.org/web/20240115115426/https://minecraft.wiki/w/Far_Lands }}</ref>在[[超級任天堂|超级任天堂娱乐系统]] (NES) 游戏{{En-link|兰博基尼美国挑战赛|Lamborghini American Challenge}}中，玩家可以通过在支付比赛费用后被罚款超过剩余金额的限制，从而导致他们在比赛中的金额低于 0 美元，这会导致整数出现故障。并给予玩家 65,535,000 美元，比它在负数后的收益多出 65,535,000 美元。<ref>Archived at [https://ghostarchive.org/varchive/youtube/20211205/aNQdQPi0xMo Ghostarchive]{{cbignore}} and the [https://web.archive.org/web/20190726012137/https://www.youtube.com/watch?v=aNQdQPi0xMo&t=17m55s Wayback Machine]{{cbignore}}: {{cite web |title=Lamborghini American Challenge SPEEDRUN (13:24) |url=https://www.youtube.com/watch?v=aNQdQPi0xMo&t=17m55s |website=[[YouTube]] |access-date=2022-08-11 |archive-date=2022-08-11 |archive-url=https://web.archive.org/web/20220811071040/https://www.youtube.com/watch?v=aNQdQPi0xMo&t=17m55s |dead-url=no }}

{{cbignore}}</ref> 在[[浩劫殺陣：晴空染血|潜行者：晴空]]中也发生了类似的故障，玩家可以在没有足够资金的情况下通过快速旅行而陷入负数，然后继续进行玩家被抢劫并拿走所有货币的事件。在游戏试图将玩家的钱带走直到 0 美元后，玩家将获得 2147482963 游戏币。<ref>{{Cite web |title=Money glitch :: S.T.A.L.K.E.R.: Clear Sky General Discussions |url=https://steamcommunity.com/app/20510/discussions/0/1484358860942756615/ |access-date=2022-08-11 |archive-date=2022-08-11 |archive-url=https://web.archive.org/web/20220811071046/https://steamcommunity.com/app/20510/discussions/0/1484358860942756615/ |dead-url=no }}</ref> 
[[File:Error message due to an integer signedness bug in the stack setup code of MASM 1.00.gif|alt=Error message due to an integer signedness bug in the stack setup code of MASM 1.00.gif|thumb|[[Pascal語言|Pascal]] 编译器产生的堆栈设置代码中的整数符号错误阻止了 IBM–[[MASM|Microsoft 宏汇编器]] (MASM) 版本 1.00，一个 1981 年的 [[DOS]] 程序，以及许多其他使用相同编译器编译的程序，在某些超过 512 KB 内存d配置下运行。]]
IBM–[[MASM|Microsoft 宏汇编器]] (MASM) 版本 1.00，以及可能由同一 [[Pascal語言|Pascal]] 编译器构建的所有其他程序，在堆栈设置代码中存在整数溢出和符号错误，这会阻止它们在较新的常见的具有超过 512 KB 内存配置的 [[DOS]] 机器或模拟器上运行。 程序挂起或显示错误消息，并退出到 DOS。<ref>{{cite web |last=Lenclud |first=Christophe |title=Debugging IBM MACRO Assembler Version 1.00 |url=https://slions.net/threads/debugging-the-ibm-personal-computer-macro-assembler-masm-version-1-00.33/}}</ref>

2016 年 8 月，{{En-link|Resorts World|Resorts World}} 赌场的一台[[赌场]]机器因溢出错误而打印出 42,949,672.76 美元的奖券。 赌场拒绝支付这笔款项，称其为故障，在他们的辩护中用了机器明确表示最高支付为 10,000 美元，因此任何超过该金额的奖金都必须是编程错误的结果。 纽约州博彩委员会作出有利于赌场的裁决。<ref>{{cite web |last=Kravets |first=David |date=June 15, 2017 |title=Sorry ma'am you didn't win $43M – there was a slot machine 'malfunction' |url=https://arstechnica.com/tech-policy/2017/06/sorry-maam-you-didnt-win-43m-there-was-a-slot-machine-malfunction |website=Ars Technica |access-date=2022-08-11 |archive-date=2022-08-11 |archive-url=https://web.archive.org/web/20220811071051/https://arstechnica.com/tech-policy/2017/06/sorry-maam-you-didnt-win-43m-there-was-a-slot-machine-malfunction/ |dead-url=no }}</ref> 

==参考文献==
{{reflist}}

[[Category:計算機算術]]
[[Category:保全漏洞]]
[[Category:程式錯誤]]