邊界檢查

邊界檢查

邊界檢查在程序設計中是指在使用某一個變數前,檢查該變數是否處在一個特定範圍之內。最常見的是數組的下標檢查,防止下標超出數組範圍而覆蓋其他數據。若是邊界檢查未能有效發現錯誤,最常見的結果是程序出現異常並終止運行,但也可能出現其他現象。由於每次都進行邊界檢查非常耗時,而且有些代碼確定不會出現越界問題,所以這個操作並不總是需要被執行。一些現代編譯器中有稱為選擇性邊界檢查的技術,可以略去一些常見的不需要的邊界檢查,從而提高程序的性能。

簡介


差一錯誤
差一錯誤
在常見的編程語言中,強制進行邊界檢查的有C#、Ada、HaskellJavaJavaScript、Lisp、PHP、Python、RubyVisual Basic。其中C#同時支持“unsafe塊”(不安全代碼塊),即一段暫時關閉邊界檢查、啟用 指針以提高效率的代碼塊。這個功能常被用於加速一小段不可能出現越界問題的代碼的執行速度,而不至於破壞整個程序的安全性。除了這些語言,D語言和OCaml也支持自動邊界檢查,但是允許用戶通過編譯器的一個開關選項來選擇是否啟用該功能。差一錯誤,又稱“柵欄錯誤”:一個柵欄被一些柱子分區成10段,柱子的根數應該是11根,而不是10根。然而,有一些編程語言(比如C語言)為了提高速度,從來都不會自動進行邊界檢查,這經常導致差一錯誤(見右圖)和緩衝區溢出的發生。許多程序員認為這些語言為了速度所付出的代價太大了。在1980年圖靈獎講座上,東尼·霍爾講述了他設計包含邊界檢查的ALGOL 60語言時的經歷:該方法的原理主要是在程序運行時,每個含有下標的變數中的下標在每次被使用的時候總是會與變數下標的上界和下界都進行比較。許多年後,我詢問我們的一些客戶是否需要提供一個“在編譯發行版時關閉該功能以保證速度”的選項時,他們都毫不猶豫的勸我們一定不要加入這個功能。因為他們知道下標越界是多常見的事情,並且在實際應用中,偶爾一次沒檢測到的下標越界所帶來的結果便會是災難性的。我注意到即便在1980年,語言的設計者和用戶仍沒有意識到這一點,這令我十分擔心。若是在工程領域的任何一個重要的分支中,沒能注意到這些低級錯誤都是有違常理的。

數組邊界


數組邊界檢查可防止緩衝區溢出的產生。為了實現數組邊界檢查,應當檢查所有對數組的讀寫操作以確保正確的範圍內對數組的操作。數組下標檢查是指在程序中,所有數組下標的表達式的結果在真正被用來訪問某一個特定的元素之前,先把它的值和定義數組時給出的數組上界和下界進行比較。如果一個下標超出了預期的範圍時,那麼就引發一個錯誤來阻止進一步的訪問。比如在訪問一個下標範圍是0~9的數組前檢查下標是否也在0~9內,而不是如25之類的越過數組結尾的下標。除了軟體實現的下標檢查之外,VAX架構的計算機擁有一條INDEX彙編指令,可以用來檢查數組的下標是否越界,可以至多提供6個任意VAX編址的地址。B6500和一些相似的伯勒斯計算機則以硬體進行邊界檢查,無論是採用什麼語言撰寫的程序。
冗餘數組邊界檢查消除是指在程序中刪除被證明是合法的數組訪問所對應的邊界檢查。當數組索引能夠保證在到一之間,則該數組訪問對應的數組邊界檢查被視為完全冗餘,可從程序中刪除。如果數組邊界檢查位在循環體中,循環邊界和數組長度都是循環不變數,並且數組索引變數是循環歸納變數,那麼可以通過把邊界檢查移出循環體來減少數組邊界檢查的執行次數。這種冗餘被稱為部分冗餘。
數組邊界檢查導致程序運行時性能的減慢主要有兩個原因一是執行這些邊界檢查操作需要時間開銷。邊界檢查需要得到數組的長度信息,這需要一個訪存操作,而判斷當前的訪問索引是否合法,又需要一個比較操作。如果邊界檢查處在一些頻繁訪問的循環中,那麼這些操作的開銷將是非常可觀。二是數組邊界檢查可能會阻止其他的優化機會,比如代碼移動。和嵌套循環優化等。

範圍檢查


範圍檢查經常被用於確保某個數字處在一個特定的範圍之內。通常在訪問數組的時候會進行該檢查,因為當數組下標越界的時候,數據會被寫入其它變數的空間,甚至會覆蓋壓棧的寄存器數值。這樣一來,程序可能會崩潰,或者是導致一些安全漏洞的產生。在Java中,Java虛擬機將在嘗試訪問數組中的元素的時候,自動的進行數組邊界檢查,並且在下標越界的時候引發異常。
範圍檢查的另一個常見用途是在兩種數據類型相互轉換的時候。在構建在.NET Framework上的語言中,超出範圍的強制轉換將引發Invalid Cast Exception類型的異常。
比如將一個32位有符號整數類型的變數強制轉換到一個16位有符號整數類型的變數之前,會檢查這個變數的值是否在-32768~+32767之間(16位有符號整數可以表示的整數範圍),而不是諸如32768之類的無法表示的數字。