Off-by-oneエラー
Off-by-oneエラー（オフ-バイ-ワンエラー、off-by-one error、OBOE）とは、境界条件の判定に関するエラーの一種である。コンピュータプログラミングにおいて、ループが正しい回数より一回多く、または一回少なく実行された場合などに発生する。
この問題の代表的な原因として、プログラマーが数字のカウントを0からではなく1から開始してしまう（多くのプログラミング言語では配列の添え字は0から始まる）、数値の比較において「～未満」とすべきところを「～以下」としてしまう、等が挙げられる。また、数学的な処理を行っている場合にも発生しうる。
配列上のループ
[編集]配列のm番目の要素からn番目までの要素を処理する場合を考える。処理対象の要素はいくつだろうか？この場合、直感的に考えるとn-m個となるが、実際には1個異なり、n-m+1個が正しい。これは「植え木算エラー」の一種である。
上記のような理由により、コンピュータ上で数の範囲を表現する場合にはしばしば半開区間が用いられる。mとnを含む区間は、植木算エラーを避けるためにmを含みn+1を含まない区間として表現される。例えば、5回繰り返して実行されるループは0から5までの左閉半開区間を用いて以下のように表現される。
for (i = 0; i < 5; i++) {
/* ループ中の処理 */
}
ループ中の処理は最初iが0の状態で開始される。以降、iは1, 2, 3と増加し、4までは問題なく実行される。次の時点でiは5となり、条件文i < 5が偽と判定されてループは終了する。
もし、条件文で使用されている比較演算子が<=（「～未満」ではなく「～以下」）だった場合、ループの中の処理は6回実行されてしまう。つまり、iは0, 1, 2, 3, 4, 5と増加し、5まで実行される。同様に、iが0でなく1で初期化されていた場合にはループは4回しか実行されない。つまり、iは1, 2, 3と増加し、4まで実行される。これらのケースはどちらもoff-by-oneエラーの一種である。
このようなエラーが発生する他の例としては、while文を使用すべきところでdo-while文を使用した場合（逆も同じ）が挙げられる。do-whileループは必ず1回は実行される。
配列関連の勘違いはプログラミング言語ごとの差異に由来する場合もある。配列の添え字は0から始まる場合が一般的だが、1から始まる言語もいくつかある。Pascalでは配列の添え字をユーザが指定した数字から始めることができるが、これにより配列の添え字を問題のドメインに合わせて設定することができる。
植木算エラー
[編集]
植木算エラーはoff-by-oneエラーの一種であり、「支柱(fencepost)エラー」、「電柱(telegraph pole)エラー」、「電灯(lamp-post)エラー」とも呼ばれる。このエラーは以下の問題で説明される。
100メートルのフェンスを作り、10メートルごとにフェンスの支柱を立てる場合、必要な支柱の本数は何本か？
直感的に考えると、100÷10=10であるため10本という答えになるが、これは誤りである。フェンスは10の区間に区切られるが、支柱は11本必要となる。
また、稀に、入力値に予期しない規則性があった場合のエラーが"植木算エラー"と呼ばれることもある。これは、例えば理論上は効率が良いはずの二分木やハッシュ関数が特定の入力によってまるでだめになってしまうことを指している。このエラーは、アルゴリズムに期待されている振る舞いと最悪の場合の振る舞いとの差によって発生する。
セキュリティとの関連
[編集]off-by-oneエラーのうちセキュリティに関係したバグとなる典型的な例は、libcのstrncat関数の使用法の誤りによるものである。strncat関数に関するよくある誤解としては「連結した文字列と終端のnull文字を足した長さは引数で指定した最大長を超えることはない」というものがある。実際には、終端のnull文字を含めると、指定した最大長より1文字多く書き込みが行われる。以下のコードはこの種のバグを含んでいる。
void foo (char *s) {
char buf[15];
memset(buf, 0, sizeof(buf));
strncat(buf, s, sizeof(buf)); // 最後の引数は sizeof(buf)-1 でなければならない
return;
}
システムによっては（特にリトルエンディアンのアーキテクチャの場合）、このバグによってフレームポインタの最下位のバイトが上書きされてしまうことがある。攻撃者はこれを利用して呼び出し中のルーチンのローカル変数を書き換えられるため、このバグはセキュリティホールとなることがある。
参考文献
[編集]- この記事の初期のバージョンはFOLDOCの記事 fencepost error に基づいています。
関連項目
[編集]外部リンク
[編集]- digitalartform.comのモーションブラーに関する記事 アニメーションパッケージの多くでは、フレームを2つの時刻の間隔としてではなく、ある特定の時点として扱っている。