境界チェック

コンピュータプログラミングにおいて、境界チェックとは、変数が使用される前にその変数が境界内にあるかどうかを検出する方法です。これは通常、数値が特定の型に適合することを確認する (範囲チェック) ため、または配列インデックスとして使用されている変数が配列の境界内にあることを確認する (インデックスチェック) ために使用されます。境界チェックに失敗すると、通常は何らかの例外信号が生成されます。

使用のたびに境界チェックを実行すると時間がかかるため、必ずしも実行されるわけではありません。境界チェックの削除は、不要な境界チェックを削除するコンパイラ最適化手法です。

範囲チェック

範囲チェックは、数値が特定の範囲内にあることを確認するためのチェックです。たとえば、16 ビット整数に割り当てられる値が 16 ビット整数の容量内であることを確認します (つまり、ラップアラウンドをチェックします)。これは、型チェックとはまったく同じではありません。^{[どのように? ]}他の範囲チェックはより制限的である場合があります。たとえば、カレンダーの月の数を保持する変数は、1 から 12 の範囲のみを受け入れるように宣言される場合があります。

インデックスチェック

インデックスチェックとは、配列をインデックスするすべての式において、インデックス値が配列の境界 (配列が定義されたときに確立されたもの) に対してチェックされ、インデックスが境界外である場合は、何らかのエラーによってそれ以上の実行が中断されることを意味します。配列の境界外の値の読み取り、特に書き込みは、プログラムの誤動作やクラッシュ、またはセキュリティの脆弱性 (バッファオーバーフローを参照) を引き起こす可能性があるため、インデックスチェックは多くの高級言語の一部です。

インデックスチェック機能を備えた初期のコンパイル型プログラミング言語には、 ALGOL 60、ALGOL 68、Pascalのほか、BASICなどのインタープリタ型プログラミング言語がありました。

Cなどの多くのプログラミング言語では、速度を上げるために境界チェックを自動的に実行することはありません。しかし、これにより、多くのoff-by-one エラーやバッファオーバーフローが捕捉されないままになります。多くのプログラマーは、これらの言語は高速実行のために犠牲にしすぎていると考えています。^[1] 1980 年のチューリング賞の講演で、CAR Hoare は境界チェックを組み込んだ言語である ALGOL 60の設計経験について次のように述べています。

この原則の結果、添字付き変数のすべての添字は、実行時に常に配列の上限と下限の宣言境界に対してチェックされました。何年も経ってから、私たちはお客様に、生産時の効率性を考慮してこれらのチェックをオフにするオプションを提供するかどうか尋ねました。全員一致で、そうしないよう強く勧められました。生産時に添字エラーが頻繁に発生し、それを検出できないと悲惨な結果になる可能性があるのは、すでにわかっていたからです。1980 年になっても、言語設計者とユーザーがこの教訓を学んでいないことに、私は恐怖と戦慄を覚えます。エンジニアリングのどの立派な分野でも、このような基本的な予防措置を遵守しないことは、ずっと前から違法だったでしょう。

実行時チェックを実施する主流の言語には、Ada、C#、Haskell、Java、JavaScript、Lisp、PHP、Python、Ruby、Rust、Visual Basic などがあります。D言語とOCaml言語には、コンパイラスイッチで有効または無効にする実行時境界チェックがあります。C++では、実行時チェックは言語の一部ではなくSTLの一部であり、コンパイラスイッチ (_GLIBCXX_DEBUG=1 または _LIBCPP_DEBUG=1) で有効になります。 C# は、安全でない領域もサポートしています。これは、(他の機能の中でも) 効率を上げるために境界チェックを一時的に停止するコードセクションです。これらは、プログラム全体の安全性を犠牲にすることなく、時間的に重要な小さなボトルネックを高速化するのに役立ちます。

JS ++プログラミング言語は、既存の型を使用してコンパイル時に配列インデックスまたはマップキーが範囲外かどうかを分析できます。既存の型は、インデックスまたはキーが範囲内か範囲外かを説明し、コード生成をガイドする名目上の型です。既存の型は、コンパイル時間にわずか1ミリ秒のオーバーヘッドを追加することが示されています。^[2]

ハードウェア境界チェック

境界チェックによって追加された安全性は、チェックがソフトウェアで実行される場合、必然的に CPU 時間を消費します。ただし、チェックがハードウェアで実行できる場合は、実行時間コストなしで安全性を「無料で」提供できます。ハードウェア境界チェックを備えた初期のシステムは、1974 年に発表されたICL 2900 シリーズメインフレームでした。 ^[3] VAXコンピューターには、配列インデックスチェック用の INDEX アセンブリ命令があり、これは6 つのオペランドを受け取り、すべてのオペランドで任意の VAX アドレッシングモードを使用できます。B6500 および同様のBurroughsコンピューターは、マシンコードを生成するためにどのコンピューター言語がコンパイルされたかに関係なく、ハードウェアを介して境界チェックを実行しました。後のCPUの一部には、境界チェック専用の命令があり、たとえばMotorola 68000シリーズの CHK2 命令があります。

少なくとも2005年以来、x86の組み込み仮想メモリ管理ユニットを使用して配列とバッファのアクセスの安全性を確保する方法に関する研究が進められてきました。^{[4] 2015年にIntelは、境界をCPUレジスタに格納し、テーブルをメモリに格納する}Intel MPX拡張機能をSkylakeプロセッサアーキテクチャに提供しました。2017年初頭の時点で、少なくともGCCはMPX拡張機能をサポートしています。

参照

参考文献

^ Cowan, C; Wagle, F; Calton Pu; Beattie, S; Walpole, J (1999)。「バッファオーバーフロー: 10 年間の脆弱性に対する攻撃と防御」。議事録 DARPA 情報生存性会議および博覧会。DISCEX'00。第 2 巻。pp. 119–129。doi : 10.1109 / DISCEX.2000.821514。ISBN 978-0-7695-0490-2.S2CID 167759976 。
^ 「JS++ 0.9.0: 境界外エラーの効率的なコンパイル時分析 – JS++ ブログ」。2019 年 1 月 11 日。2019 年 1 月 12 日時点のオリジナルよりアーカイブ。
^ JK Buckle (1978). ICL 2900 シリーズ(PDF) . Macmillan Computer Science Series. pp. 17, 77. ISBN 978-0-333-21917-1. 2018年4月20日時点のオリジナル（PDF）よりアーカイブ。2018年4月20日閲覧。
^ Lap-Chung Lam、Tzi-Cker Chiueh (2005)。「セグメンテーションハードウェアを使用した配列境界違反のチェック」。2005 International Conference on Dependable Systems and Networks (DSN'05)。pp. 388–397。doi : 10.1109/DSN.2005.25。ISBN 0-7695-2282-3. S2CID 6278708。

外部リンク

「タグ付きアーキテクチャの利点について」、IEEE Transactions On Computers、第 C-22 巻、第 7 号、1973 年 7 月。
「皇帝の古着」は2017年10月2日にWayback Machineでアーカイブされました、1980年のACMチューリング賞講演、CACM第24巻第2号、1981年2月、75～83ページ。
「Bcc: C プログラムの実行時チェック」、Samuel C. Kendall、USENIX 1983 年夏季会議の議事録。
「C の境界チェック」、リチャード・ジョーンズとポール・ケリー、インペリアル・カレッジ、1995 年 7 月。
「ClearPath Enterprise Servers MCP セキュリティ概要」、Unisys、2006 年 4 月。
「セキュアな仮想アーキテクチャ: コモディティオペレーティングシステム向けの安全な実行環境」、John Criswell、Andrew Lenharth、Dinakar Dhurjati、Vikram Adve、SOSP'07 21st ACM Symposium on Operating Systems Principles、2007 年。
「Fail-Safe C」、大岩裕。メモリセーフなフル ANSI-C コンパイラの実装。ACM SIGPLAN プログラミング言語設計および実装会議 (PLDI2009)、2009 年 6 月。
「アドレスサニタイザー」、Timur Iskhodzhanov、Alexander Potapenko、Alexey Samsonov、Kostya Serebryany、Evgeniy Stepanov、Dmitriy Vyukov、LLVM 開発会議、2011 年 11 月 18 日。
制限された API の安全な C ライブラリ
「Safe C ライブラリ」。Dr . Dobb's Journal。2009年 2 月 20 日。2013 年 12 月 2 日時点のオリジナルよりアーカイブ。2012 年11 月 13 日閲覧。
Safe C API - バッファオーバーフローの簡潔なソリューション、OWASP Foundation、OWASP AppSec、北京 2011
GNU C++ ライブラリマニュアルマクロ
libc++ 11.0 ドキュメントデバッグモード

[1] Cowan, C; Wagle, F; Calton Pu; Beattie, S; Walpole, J (1999)。「バッファオーバーフロー: 10 年間の脆弱性に対する攻撃と防御」。議事録 DARPA 情報生存性会議および博覧会。DISCEX'00。第 2 巻。pp. 119–129。doi : 10.1109 / DISCEX.2000.821514。ISBN 978-0-7695-0490-2.S2CID 167759976 。

[2] 「JS++ 0.9.0: 境界外エラーの効率的なコンパイル時分析 – JS++ ブログ」。2019 年 1 月 11 日。2019 年 1 月 12 日時点のオリジナルよりアーカイブ。

[3] JK Buckle (1978). ICL 2900 シリーズ(PDF) . Macmillan Computer Science Series. pp. 17, 77. ISBN 978-0-333-21917-1. 2018年4月20日時点のオリジナル（PDF）よりアーカイブ。2018年4月20日閲覧。

[4] ^ Lap-Chung Lam、Tzi-Cker Chiueh (2005)。「セグメンテーションハードウェアを使用した配列境界違反のチェック」。2005 International Conference on Dependable Systems and Networks (DSN'05)。pp. 388–397。doi : 10.1109/DSN.2005.25。ISBN 0-7695-2282-3. S2CID 6278708。