C++ における整数型の怪と "移植性のある" オーバーフローチェッカー (第1回 : 整数型の怪と対策の不足)

はじめに

整数型の取り扱い (表現可能な値の範囲を超える "整数オーバーフロー" を防ぐなど) は、セキュリティ上の問題を避けるために、そうでなくとも予期しないバグを避けるために (頻繁に!) 注意しなければならないことだと言えるでしょう。

整数オーバーフローは、特に C/C++ においては深刻な脆弱性の原因になりがちです。昨年界隈を騒がせた Android の Stagefright としてくくられている複数の脆弱性のうち大部分は、この整数オーバーフローが原因となっています。

ただ、C++ における整数型は、実に奇妙です。その奇妙さの結果、C++ において整数オーバーフローを防ぐことは非常に難しいことが……あまり知られていません。というわけで、数回に分けて C++ における整数型 (特に符号付き整数型) の仕様とその奇妙なところ、何故整数オーバーフローチェックが難しいのか、それでもどうやったら実際にオーバーフローチェックが書けるのかなどについて書いてみようと思います。

第1回では、C/C++ (特に C++) における整数型/整数演算の怪と、私が移植性のあるオーバーフローチェッカーを書くきっかけになった "惨状" について解説します。

連載インデックス

• 第1回 : 整数型の怪と対策の不足
• 第2回 : 符号無し整数型のチェック
• 第3回 : C言語の整数の性質を知る
• 第4回 : 符号付き整数型のチェックと動機の動機
• 第5回 : 続・符号付き整数型のチェック

符号無し整数型は割と素直

符号の無い整数型は、C でも C++ でも大きな差はありません (規格上の小さな差はあるものの、この連載で解説する範囲では事実上違いがないとみなしてよい)。

符号無し整数型においては、事実上整数オーバーフローによる未定義動作が発生しません。0 除算、大きすぎる幅によるシフトのような未定義動作を引き起こす演算を除けば、演算の結果は数学的に厳密な結果をモジュロ演算でラップする形になっています。

#include <cstdint>
#include <limits>

// uint8_t を持つ (注: 規格上必須ではない) 規格準拠の処理系は次の static_assert を通る
static_assert(std::numeric_limits<uint8_t>::min() == 0, "uint8_t の最小値は 0");
static_assert(std::numeric_limits<uint8_t>::max() == 255, "uint8_t の最小値は 255");

// モジュロ演算に用いる除数は、型ごとに……(最大値-最小値+1)、つまり uint8_t の場合 256。

static const uint8_t a = 190;
static const uint8_t b = 210;
// わざとオーバーフローする演算を行ってみる
static const uint8_t c = a + b; // 数学的な結果は 400 だが、uint8_t には入りきらない
static const uint8_t d = a - b; // 数学的な結果は -20 だが、uint8_t には入りきらない

// 規格準拠の処理系なら次の static_assert を通るはず
static_assert(c == uint8_t(400 - 256) /* 144 */, "何かがおかしい!");
static_assert(d == uint8_t(256 -  20) /* 236 */, "何かがおかしい!");

とはいえ、符号無し整数型では整数オーバーフローによって未定義動作が発生しないだけであることに注意が必要です。符号無し整数型の表現範囲を超えた演算結果は数学的な結果や (多くの場合) プログラマーが求めている結果からズレてしまうため、時に予期しない結果となることがあります。

例えば、確保するべきメモリサイズの計算において整数オーバーフローが発生した場合、深刻な (かつ条件次第で攻撃者が利用しやすい) バッファオーバーフロー脆弱性となってしまいます¹。セキュリティの観点からは、符号が無くとも (信頼できない入力を使うには) 演算のチェックを行うことが必要となるでしょう。

符号付き整数型の使用にはある程度の注意が必要

演算の結果がそれを格納する符号付き整数型に収まらない場合、その動作は基本未定義となります (動作が未定義になる場合と実装依存の値が得られる場合の両方があり、細則含めると少々複雑です; thanks: @k-satoda)。つまり、プログラムがクラッシュするかもしれませんし、クラッシュしなかったとしても信頼できる (移植性のある) 値を得ることはできません。signed char 型の 127 と 1 を足しあわせて同じ型の変数に入れたら -128 になった? それは規格上単なる偶然ですし、どんな値になっても文句は言えません。

現代的なコンパイラは、未定義動作の発生するケースを "どのように最適化しても大丈夫" だと判断して大胆な最適化を行う場合があります。これにより、ときには整数オーバーフローに起因して Debug ビルドと Release ビルドで著しく挙動が違う、などの問題が発生することもあります。

また符号付き整数型における整数オーバーフロー (正確にはそれに伴う未定義動作) は C++11 以降において constexpr の動作に影響し、整数オーバーフローを含む式は (定数の演算によって生成されていても) 定数と見なされなくなります。メタプログラミング等において constexpr を活用する場合には値を定数のままにすることが重要になるため、場合によっては、この意味でも整数オーバーフローを事前に検出することが重要です。

除算 (/) と剰余 (%) は規格バージョンによって挙動が異なる

符号付き整数型の四則演算においては、除算と剰余の動作が規格バージョンによって異なります。

C99 より前、もしくは C++11 より前では、除算や剰余の除数、被除数いずれかないしは両方に負の数が含まれる場合、いずれの結果も実装依存 (つまり、移植性の無い値) となります。ただし、有効な演算を行うことができた場合、必ず (a/b)*b + a%b == a という関係式が成り立ちます。

C99 以降、もしくは C++11 以降では、除算結果 (商) の定義が厳密になった結果、整数オーバーフローやゼロ除算が発生しない限り必ず移植性のある値を得ることができます。具体的に言えば、a / b の結果は、数学的に評価した結果を 0 方向に切り捨てた値 (簡単に言えば符号を外し、切り捨てをしてから元の符号を付け直した値) となります。a % b の値は、厳密化された除法の定義と先述の関係式から一意に決定されます。

// C99 より前、もしくは C++11 より前でも必ず同じ結果になる
static_assert(+7 / +2 == +3, "+7 / +2 = round_towards_zero(+3.5) = +3.");
// C99 より前、もしくは C++11 より前では値が異なる可能性がある
static_assert(-7 / +2 == -3, "-7 / +2 = round_towards_zero(-3.5) = -3.");
static_assert(+7 / -2 == -3, "+7 / -2 = round_towards_zero(-3.5) = -3.");
static_assert(-7 / -2 == +3, "-7 / -2 = round_towards_zero(+3.5) = +3.");

規格ごとの対応表は次の通りです。

規格	除算・剰余の移植性
ANSI C (C89/C90)	×
C99	○
C11	○
C++98	×
C++03	×
C++11	○
C++14	○

C と C++ では符号付き整数型の定義が大きく異なる!

実は、C と C++ (両方とも ISO/IEC 国際規格になっている) において整数型の厳密な定義は異なり、最新の規格同士で比較すると実のところ C++ の方が制限が緩いものとなっています。その結果、C++ では規格だけを厳密に解釈すれば異常な整数型の存在が可能となってしまいます。

まずは、そのような整数型を許可しない C について見ていきましょう。

C 言語 (C99) における整数型の定義

規格書 (ISO/IEC 9899:1999) の定義の一部 (抄訳) を示します。

(前略²) もし符号ビットが 0 である場合、結果の値には影響しません。もし符号ビットが 1 であれば、次のいずれかの方法によって結果の値が変更されます。

• 符号ビット 0 がついた対応する値が反転する (符号と絶対値)
• 符号ビットは値 -(2^N) を持つ (2 の補数)
• 符号ビットは値 -(2^N-1) を持つ (1 の補数)

これらのうちどれが適用されるかは処理系依存です。

C99 においては、整数型の内部表現はちゃんと (型ごとに 3 つの中のどれかと) 決められています。これにより、整数オーバーフローを防ぐためのコーディングは比較的簡単なものになっています (後述する通り、"比較的簡単" であるにも関わらずゴミなライブラリも多いのですが……)。

この規定が十分にはたらくのは、内部表現を規定することによって表現可能な範囲にある程度制限がかかるからです。例えば 1 つの符号ビットと 7 つの値ビットがある符号付き整数型を考えたとき、C99 においてその表現可能な範囲は次の二択になります。

• -128 から 127 (2 の補数の場合)
• -127 から 127 (符号と絶対値、もしくは 1 の補数の場合)

なお、通常の整数型とは別に、stdint.h の int8_t、int16_t、int32_t、int64_t といったビット固定の符号付き整数型が存在する場合があります。これらのビット数固定符号付き整数型に限っては、存在すれば必ず 2 の補数表現であることが保証されており、データ型の移植性を飛躍的に高めることができます。ただし、整数オーバーフローしたときの動作は相変わらず未定義となっていますので、整数オーバーフローを起こさないようなコーディングを心がける必要はあります。また (ほとんどの処理系ではおそらく存在するでしょうが) これらの型は存在することが規格上必須ではないことにも注意が必要です。

C++ (C++11) における整数型の主な定義

符号付き整数型の定義における主要箇所を、規格書 (ISO/IEC 14882:2012) より抄訳、引用します。

整数型の値は "pure binary numeration system" を利用することによって表現されなければなりません。
[例: この国際規格は整数型の表現において、2 の補数、1 の補数および符号と絶対値表現を許容しています。]

……これだけです。C 言語では明確に定められている 3 種類の内部表現は、例という形では C++ 規格に取り入れられています。しかしこれはあくまで例であって、規格の一部としてこうなることが定まっているわけではありません。この定義の中で使われている "pure binary numeration system" という用語の定義も (おおむね) 最上位以外のビットがそれぞれ 1, 2, 4... と最下位から 2 倍になっていく重みを持つという程度のもの (しかも規格曰く辞書からの引用) で、符号ビットの具体的挙動が全く定まっていないどころか符号付き整数自体の定義も厳密なものとなっていません。

このことから得られるのは (実現可能性を別とすると) 正負のバランスが極めて異常な符号付き整数型です。先ほどと同じ 1 つの符号ビットと 7 つの値ビットがある符号付き整数型を考えましょう。……すると、(C では違法であるにも関わらず) C++ では完全に規格に準拠する異常な整数型が得られます³。

• 表現可能な範囲 : -64 ～ 191
• 表現可能な範囲 : -223 ～ 31

このような異常なケースを厳密に考慮すると、移植性のある整数オーバーフローチェックを実装することが非常に困難になることが分かります (詳しくは次回以降 [多分第3回辺り] に解説)。

なお、cstdint のビット数固定符号付き整数型 int8_t、int16_t、int32_t、int64_t は、(存在する場合には) C99 の特別な規定が適用され、2 の補数表現であることが保証されます。また atomic 演算の中でも一部 2 の補数で演算を行うことが規定されている (しかも整数オーバーフローによっても未定義の動作を引き起こさないと記されている) 部分がありますが、通常の型との相互運用性の観点と性能の観点から atomic をオーバーフローチェックを乗り越えるために使うのは (個人的には) 推奨できません。

どうしてこうなった!

おそらく、C と C++ の規格同士の同期を十分に (かつ一貫した形で) 取らなかったことが原因だと思われます。実は C++ における整数型の定義はおおむね ANSI C (C99 よりさらに古いバージョン) を継承しており、規格上 (必要な部分について) C99 を参照する C++11 規格でも ANSI C に基づく定義 (C++ 側で定義されてしまっているので C99 における定義を参照することができない) になってしまっています。

整数型の細かい (にも関わらずプログラマーに絶大な影響をもたらす) 挙動に関わる幾つかの理由から C99 と同等の規則を設けようと提案が成されましたが、今のところ C++ の規格には反映されていません。

good 移植性 × bad 移植性 → bad 移植性

また除算と剰余に関しては、C++11 以降で移植性を向上させる定義の変更が加えられたのにも関わらず整数型の規定が緩すぎるため、移植性を良好にするための新規定を十分に活用することができません。これは C++ だけにしか存在しない特徴です。

これに関しては、規格との対照表を見てみるとわかりやすいと思います。

規格	除算・剰余の移植性	異常な整数型は存在不可
ANSI C	×	×
C99	○	○
C11	○	○
C++98	×	×
C++03	×	×
C++11	○	×
C++14	○	×

移植性あるプログラムで整数オーバーフローを防ぐために既存チェッカーを……使えない!?

整数オーバーフローを事前検出し、意図しない結果になるのを防ぐコンパイラ拡張やライブラリはいくつか存在します。しかし、私が確認した限りでは C++ 言語向けの確認できたもの全てが移植性に問題を抱えています。コンパイラ拡張は除外するとして、汎用性のあるライブラリを見てみましょう。

例えば Windows SDK 環境においては、整数オーバーフローを自動検出する機能を持つ "安全な整数型" が、Microsoft の SafeInt ライブラリによって提供されています。しかしこの実装を詳しく調べると、符号付き整数型が 2 の補数であることを前提にしている箇所が見つかります。Windows 向けの開発を行う場合、(おそらく) 動作する環境すべてが 2 の補数を使用しているため、問題ありません。しかし、他の OS+CPU への移植を考慮した場合、SafeInt ライブラリを移植したり内部アルゴリズムを借用するのはあまり良い考えではないでしょう。

他の実装も調べてみましたが、軒並み似たような問題を抱えていました。というより、C99 以降で許可されている表現のうち 2 の補数以外の 2 つ (1 の補数 / 符号と絶対値) さえサポートしていない実装がほとんどなのです。たとえ情報セキュリティの専門家によって書かれていても十分に信用できるとは限りません。そのような専門家の組織であるはずの CERT/CC⁴ が整数オーバーフローを避けるために公開している "整数オーバーフロー回避" 方法でさえ、2 の補数以外を正しくサポートしていない (しかも CERT/CC が以前公開していた IntegerLib に至っては 2 の補数環境ですら未定義動作が発生する) という悲惨な有様なのです。

私が出した結論 : 整数オーバーフローチェッカーを自分で書く

結果、現状十分に移植性がありなおかつ符号付き整数型をサポートしている整数オーバーフローチェッカーは現状存在せず、必要なら自分で書かなければならないという結論に至りました。私が書くべき整数オーバーフローチェッカーは、次の全てを満たしている必要があると考えました。

1. C++ の規格のみに依存しなければならない (基本的に、特殊なコンパイラ機能やアーキテクチャ固有の前提に頼ってはならない [最適化時を除く])
2. 整数オーバーフローをチェックするルーチンの使用するアルゴリズムは、数学的に厳密に証明されなければならない (現在 Coq 使用)
3. ある程度、使いやすくなければならない (他人のためにライブラリを公開すること前提)
4. 可能ならば、速くなければならない (速いアルゴリズムを使える環境下ならそれを選択する)

実は連載第1回を書いているこの時点では符号付き整数型の除算・剰余に関わる特定ケースの証明ができておらず、まだライブラリとして完成されていません。しかし証明の目処は立っているので、忘れる前に記事を書いてしまおうということでフライングしてしまいました。

第2回では、符号無し整数型に対するオーバーフローチェッカー実装 (まだ簡単) とその性質について解説する予定です。

練習問題 1 : ひとつ、もしくはふたつの整数オーバーフロー

次の C++ コードには、整数オーバーフローの脆弱性が最低ひとつ、最大ふたつ存在します。ふたつの整数オーバーフローを両方とも指摘してください。ひとつは常に問題となり、もうひとつはふたつ (数え方によってはみっつ) の条件が揃ったときだけ (潜在的な) 問題となりますが、後者の方が攻撃者にとっての悪用が容易です。C++ の規格バージョンは基本的に C++03 としますが、必要なら他の規格バージョンについて考えても構いません (← 注: これはヒント)。

size_t size;
/* ... (どこかで size を設定。ただし、攻撃者は size を任意の値に設定することができるものとする) */
int* buf = new int[size + 4];

(練習問題の初出: 2015-09-09)

Edit: 解答は連載第2回にて公表されました。

主要参考文献

• ISO/IEC 9899 (C 言語) 各バージョン規格書
• ISO/IEC 14882 (C++) 各バージョン規格書
• Embedded in Academia : Overflows in SafeInt
• INT32-C. Ensure that operations on signed integers do not result in overflow - CERT C Coding Standard

1. 典型的な類型としては、確保する配列サイズの計算において整数オーバーフローが発生したにも関わらず、添字 (配列インデックス) の計算では整数オーバーフローが発生しなかったため、整数オーバーフローの発生を知らないプログラムが実際に確保した配列の外側にアクセスしてしまう、というものがあります。 ↩

2. 省略した箇所では整数型のビット配列がどのように構成されるか (1 つの符号ビット、1 以上の値ビットなど) が定義されています。 ↩

3. 別の規定 (型の保証する最低表現可能範囲) によって制限を受けるため、値ビットが 7 個である場合 (char および signed char における事実上同じ反例 1 つを除き) signed char、short、int などの標準的な符号付き整数型の内部表現になることはできません (処理系依存の拡張型でのみ可能)。ただし、8 個以上の値ビットがある場合、その性質によっては異常な表現が標準的な符号付き整数型の中で用いられる可能性が出てきます。 ↩

4. アメリカに存在する情報セキュリティを専門に扱うセンター。脆弱性情報の取り扱い (ベンダーなどとの調停を含む) やセキュアなコーディング手法の指南など、情報セキュリティに関して大きな権威のある組織。なおかつ、CSIRT と呼ばれる (極めて大雑把にいえば) 情報セキュリティに関する問題の調査や対策の公表などを行う組織の草分け的存在。 ↩