整數溢出

計算機編程中,當算術運算試圖創建一個超出可用位數表示範圍(大於最大值或小於最小值)的數值時,就會發生整數溢出錯誤。

整數溢出可以通過里程表溢出來表示。當所有數字都為最大值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).