🎫 👩🏻‍⚕️ ✋🏻 Rustの整数オーバーフローに関する神話と伝説 🌄 🐖 👾

プロセッサでサポートされているプリミティブ整数型は、実生活での操作に使用される無限の整数セットの限定された近似値です。この制限された表現は、例えば255_u8 + 1 == 0ように、常に「実」数と一致するとは限りません。多くの場合、プログラマはこの違いを忘れてしまい、簡単にバグにつながる可能性があります。

Rustは、バグから保護することを目的とするプログラミング言語であり、最も潜行性のあるメモリエラーの防止に焦点を当てていますが、プログラマが他の問題を回避しようとしています：メモリリーク、エラーを無視し、整数オーバーフロー。

さびのオーバーフロー

Rust Overflow Detection and Prevention Policyは、昨年の1.0.0リリースに向けて何度か変更されました。その結果、オーバーフローがどのように処理され、どのような結果が生じるかについて誤解があります。

バージョン1.0.0-alphaより前では、オーバーフローは周期的であり、結果は2への加算の使用に対応していました（ほとんどの最新のプロセッサーがそうであるように）。ただし、この解決策は最適ではありません。予期しない、気付かないオーバーフローは、多くの場合エラーにつながります。これは、符号付き整数のオーバーフローが未定義の動作であり、メモリの操作におけるセキュリティ違反に対する不十分な保護と一緒に、簡単に損傷につながる可能性があるため、CおよびC ++で特に悪いです。ただし、Rustなどのよりセキュリティを重視する言語では、これでも問題を引き起こします：オーバーフローの多くの例があり、それらはビデオゲーム（経済学、健康指標など）、バイナリ検索の実装、さらには航空ソフトウェアでも見られます。簡単に言えば、 max(x - y, z)ようなコードは定期的に発生し、数値が符号なしでx - yがオーバーフローを引き起こす場合、誤った結果を生成する可能性があります。その結果、整数のオーバーフローに関してRustをより安全にしたいという要望がありました。

現在のステータスはRFC 560で定義されています。

デバッグアセンブリでは、算術演算（ + 、 -など）のオーバーフローがチェックされ、存在する場合はパニックが発生します。
このリリースでは、オーバーフローの結果のチェックは行われず、結果により周期性が保証されます。

オーバーフローチェックは、アセンブリの種類に関係なく、グローバルに、または個々の操作のレベルで、手動でオンまたはオフにできます。
ただし、 / 0およびMIN / -1 （符号付き整数の場合）および同様に%チェックには影響しません。これらの計算はCおよびLLVMでの未定義の動作であり、これがrustcの動作の理由でしたが、Rustは理論的にMIN / -1を通常のオーバーフローと見なし、チェックを無効にしてMINを返すようです。

デバッグモードでのチェックのおかげで、Rustコードのオーバーフローに関連するエラーがより早く検出されることを願っています。さらに、実際にオーバーフローを当てにする場合は、コードでこれを明示的に指定する必要があります。これにより、将来の静的アナライザーおよびすべてのモードでオーバーフローチェックを含むコードの誤検知の数が減ります。

神話：オーバーフローの結果は未定義（未定義）

オーバーフローは未定義の動作を引き起こす可能性がありますが、Rustの重要な目標の1つはメモリセキュリティを確保することであり、そのような不確実性 （Cの未定義の動作と同様）は明らかにこの目標と矛盾します。未定義の値を含む変数は、使用間で同じ値を維持する必要はありません。

 // -Rust let x = undefined; let y = x; let z = x; assert_eq!(y, z); //

セキュリティがそのような値に依存している場合、これは悲惨な結果につながります。たとえば、 foo[x]配列が範囲外であるかどうかを確認する場合：

 let x = undefined; // let y = foo[x]; //   : let y = if x < foo.len() { unsafe { *foo.get_unchecked(x) } } else { panic!("index out of bounds") };

x < foo.len()を比較するときと配列に直接アクセスするときに変数値が異なる場合、保証に違反する可能性があります：比較は0 < foo.len()になることがあり、インデックスでアクセスするとfoo.get_unchecked(123456789) 混乱！

したがって、Cの符号付き整数とは異なり、Rustでは、オーバーフローを未定義にすることはできません。言い換えれば、コンパイラーは、他の方法で証明できない限り、オーバーフローが発生する可能性があると想定しなければなりません。これは非自明な結果を伴いますx + 1 > x常に真でx + 1 > xませんが、Cコンパイラはが符号付き整数の場合、この条件が常に満たされると仮定します。

「しかし、パフォーマンスはどうですか？」私はすでにこの質問を予想しています。実際、未定義の動作により、コンパイラーが仮定を立てることができるため、最適化が簡素化されます。したがって、このような動作を拒否すると、速度に影響する場合があります。整数オーバーフローの不確実性は、ループで誘導変数として使用されることが多いため、Cで特に役立ちます。そのため、仮定を立てることにより、ループの反復回数をより正確に分析できます。for for (int i = 0; i < n; i++)が実行されますnは負の値を含まないと想定できるため、 n回。 Rustは、インデックスとして正の数を使用して（ 0..nは常にnステップを与える） for x in some_array { ... }ように、軽量反復子がデータ構造を直接トラバースできるようにすることで、これらの問題のほとんどを回避します。これらのイテレーターは、ユーザーに未定義の動作を処理させることなく、データ構造の内部構造に関する知識を使用できます。

また、RustはCとは異なり、 xが符号付き整数の場合、 x * 2 / 2単純にx減らすことはできません。この最適化は適用されません（複雑な算術式の代わりに手動でxを記述する場合を除きます）が、私の練習では、そのような式はコンパイル時にxがわかっているときに最もよく見られます。つまり、式全体が定数に置き換えられます。

神話：オーバーフローの結果は不定です。

オーバーフローの結果は不定である可能性があります。その場合、コンパイラはそれが起こる可能性があると想定しなければなりませんが、結果として値を返す（またはまったく返さない）権利を持っています。実際、整数オーバーフローをチェックするRFC 560の最初のバージョンは次のことを示唆しています。

オーバーフローがチェックされるかどうかに応じて、未指定の値を返すように動作を変更するか、パニックを引き起こします。
[...]
理論的には、実装は未指定の値を返します。ただし、実際には、結果は循環オーバーフローに似ています。実装では、エラーを引き起こさないように、過度の予測不能性と予期しない動作を避ける必要があります。
そして最も重要なこと：これはCの理解における不定の振る舞いではありません。操作の結果は排他的に指定されず、Cのようなプログラム全体の振る舞いではありません。プログラマーはオーバーフロー中に特定の値に依存することはできませんが、コンパイラーは最適化のために、そのオーバーフローは発生しません。

RFCと「指定されていない」オーバーフローの結果（つまり、 127_i8 + 1は-128または0または127またはその他の値を返すことができます）が、その変化につながる活発な議論の対象となりました。

個人の努力のおかげで、RFCは最新の外観になりました：オーバーフローの結果として、値がまったく返されない（たとえば、パニックが発生する）か、2の加算の使用に対応する周期的な結果が返されます。今、文言は次のようになります。

操作+、-、*は、オーバーフローまたは順序の消失（アンダーフロー）につながる可能性があります。チェックをオンにすると、パニックが発生します。それ以外の場合、結果は循環オーバーフローになります。

記録されたオーバーフローの結果は保護対策です。オーバーフローが検出されなくても、エラーは結果に影響しません。式x - y + z (x - y) + zとして計算されるため、減算によってオーバーフローが発生する可能性があります（たとえば、 x = 0およびy = 1 、両方とも符号なし）が、 zが十分に大きい場合（この例ではz >= 1 ）、結果は「現実世界の数字」を使用した場合と同様になります。

変更は160コメントの議論の終わりに近づいたので、簡単にスキップできました。そのため、人々はオーバーフローの結果が不特定であると考え続けることができます。

神話：プログラマーはオーバーフロー処理を制御できない

オーバーフローチェックの導入に対する議論の1つは、ハッシュ計算アルゴリズム、一部のデータ構造（リングバッファーなど）、さらにはコーデックなど、周期的なオーバーフローに依存するプログラムとアルゴリズムの存在でした。これらのアルゴリズムの場合、デバッグモードで+を使用すると正しくなくなります。パニックが発生しますが、このようなオーバーフローは意識されていました。さらに、場合によっては、デバッグビルドだけでなくチェックも含めることができます。

RFCおよび標準ライブラリは、通常の演算子に加えて、 4つのメソッドセットを提供します。

これはすべての「特殊なケース」をカバーするはずです：

wrapping_...は、パディングの結果を2に戻します。
saturating_... 、オーバーフローが発生したときに最高値/最低値を返します。
overflowing_...は、オーバーフローが発生したことを示すブール値とともに2に加算した結果を返します。
checked_...は、オーバーフローの場合に値Noneを取るOptionを返しchecked_... 。

これらの操作はすべて、 overflowing_...観点から実装できますが、標準ライブラリは、最も頻繁に発生する問題の解決を簡素化しようとします。

本当に循環オーバーフローを使用したい場合は、 x.wrapping_sub(y).wrapping_add(z)ようにx.wrapping_sub(y).wrapping_add(z)できます。これにより、期待どおりの結果が得られ、標準のWrappingライブラリの型を使用することにより、冗長性を減らすことができます。

これは最終状態ではない可能性があります。RFCでは、改善の可能性についても言及しています。将来的には、SwiftのCyclic &+などの演算子がRustに追加される可能性があります。 Rustは保守的で、合理的な範囲で最小限に抑えようとしているため、オーバーフローチェックを無効にする可能性があるため、これはすぐには行われませんでした（たとえば、別の関数が明示的にマークされ、すべてのモードでコードにチェックがありません）。特に、 ServoとGeckoの最もアクティブな（潜在的な）ユーザーは後者に興味があります。

すべてのコードでオーバーフローチェックが必要な場合は、 checked_addすべての場所で使用するか（あまり便利ではありません！）、明示的に有効にする必要があります。デフォルトではデバッグモードでのみ動作しますが、-c -C debug-assertions=on rustcを（Rustコンパイラーに）渡すか、または貨物プロファイルの debug-assertionsフィールドを設定することで、オーバーフローチェックを有効にできます。また、可能であれば、他のデバッグチェックとは別にそれらを有効にする作業が進行中です（現在、rustcは不安定なオプション-Z force-overflow-checks flagサポートしています）。

神話：オーバーフローチェックに選択したアプローチは、コードの速度を低下させます。

Rustは、可能な限り高速であることを目指しており、オーバーフローチェックを設計する際に、パフォーマンスの問題が非常に深刻に扱われました。パフォーマンスは、リリースビルドのチェックがデフォルトで無効になった主な理由の1つです。もちろん、これは、開発中にエラーを検出する利便性のために速度が犠牲にされなかったことを意味します。

残念ながら、オーバーフローチェックにはさらに多くのコードと命令が必要です。

 [no_mangle] pub fn unchecked(x: i32, y: i32) -> i32 { x.wrapping_add(y) } #[no_mangle] pub fn checked(x: i32, y: i32) -> i32 { x + y }

-O -Z force-overflow-checks 、x86で-O -Z force-overflow-checks （32ビットARM LLVMでは現在、冗長な比較とレジスタ操作が生成されるため、パフォーマンスの低下はさらに大きくなります！）：

 unchecked: leal (%rdi,%rsi), %eax retq checked: pushq %rax addl %esi, %edi jo .overflow_occurred movl %edi, %eax popq %rcx retq .overflow_occurred: leaq panic_loc2994(%rip), %rdi callq _ZN9panicking5panic20h4265c0105caa1121SaME@PLT

checked埋め込まれているという条件で（必要な場合）、必要以上の命令がありchecked 。この場合、 pushq / pop / movlを使用してレジスタをpushq必要movlません。埋め込みがなくても、 pushq / popqによるスタック管理は必要ないとpushqますが、残念ながら、RustはLLVMバージョンを使用しますが、これにはエラーが含まれています。もちろん、 lea代わりにaddを使用add必要があるので、これらの追加の指示はすべて面倒です。

x86では、算術演算にlea （ロード実効アドレス）を使用すると非常に便利です。比較的複雑な計算を実行でき、原則として、命令レベルでのより高い並列性に寄与するaddとは対照的に、CPUとそのパイプラインの別個の部分で計算されます。 x86 ISAでは、ポインターを使用した複雑な計算の結果を逆参照できます。一般形式はA(r1, r2, B) （AT＆T構文で）です。これはr1 + B * r2 + Aと同等です。通常、これはmovなどのメモリ命令で直接使用されます（たとえば、 let y = array_of_u32[x]; mov (array_of_u32.as_ptr(), x, 4), y 、各要素のサイズは4）ですが、 lea使用すると、メモリに影響を与えずに算術を実行できます。一般的に、演算にleaを使用する機能は非常に便利です。欠点は、 leaがオーバーフローチェックと直接統合されないことです。これを示すためにプロセッサステータスフラグを設定しません。

ただし、パフォーマンスに対するさらに大きな打撃は、オーバーフローチェックが他の最適化を妨げることです。最初に、チェック自体がコードを並べ替えます（展開、並べ替え、ループベクトル化などを防ぎます）。第二に、スタックのパニックと巻き戻しにより、コンパイラはより保守的になります。

これらの考慮事項はすべて、可能な限り最高のパフォーマンスが通常重要なリリースビルドにオーバーフローチェックが含まれない理由を説明しています。

この場合、リリースモードでオーバーフローチェックが有効になっていても、範囲外のアレイのチェックの場合と同様に、パフォーマンスの損失を減らすことができます。一方では、コンパイラーは範囲分析を実行し、個々の操作がオーバーフローを引き起こさないことを証明できます。実際、このトピックには多くの注意が払われています。一方、パニックの使用によって引き起こされる問題は、サブジェクト領域が許可する場合、プログラムの異常終了でパニックを置き換えることによって部分的に解決できます。

RFCオーバーフローは、追加の最適化の可能性を提供します。「遅延パニック」が許可されます。つまり、各計算をチェックする代わりに、いずれかの計算がオーバーフローにつながる場合、実装はa + b + c + d操作を実行しa + b + c + d最後に一度パニックすることができます個別の操作tmp = a + b 、次にtmp + cなど。現時点では実装されていませんが、そのような機会があります。

神話：チェックはエラーを検出しない

整数オーバーフローを処理するためのこのスキームを開発、議論、および実装するすべての努力は、実際にエラーを検出する助けにならなければ無駄になります。個人的には、特にクイックチェックなどのテストインフラストラクチャとの組み合わせで、書き込み直後にcmp::max(x - y, z) （インターネットにヒットしなかったため、リンクはありません）のような式でいくつかの問題を発見しました。

オーバーフローチェックにより、たとえば次のようなエコシステムのエラーが検出されました（リストは完全ではありません！）。

Rust以外にも、オーバーフローエラーの危険性の他の多くの例があります。 2011年に、彼らは25の最も一般的なCWE / SANSエラーのリストを作成しました。 Swiftなどの一部の言語は常にオーバーフローチェックを実行しますが、Python 3やHaskellなどの他の言語では、デフォルトで任意の精度の数値を使用してオーバーフローを回避します。さらに、一部のCコンパイラは、未定義の動作を循環オーバーフローに置き換えるオプション（ -fwrapv ）をサポートし、オーバーフローの検出に役立ちます（ -fsanitize=signed-integer-overflow ）。