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では配列はいれつの添そえ字じをユーザが指定していした数字すうじから始はじめることができるが、これにより配列はいれつの添そえ字じを問題もんだいのドメインに合あわせて設定せっていすることができる。

植木うえき算さんエラー

区間くかんをn個こに区切くぎるにはn+1個このフェンスが必要ひつようになる

植木うえき算さんエラーは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つの時刻じこくの間隔かんかくとしてではなく、ある特定とくていの時点じてんとして扱あつかっている。