Personal tools
You are here: Home ブログ 井上 ADEXに整数オーバーフローのバグを発見 (ADEXの呪いパート2)
« December 2010 »
Su Mo Tu We Th Fr Sa
      1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31  
Recent entries
Apache2.4のリリース予定は来年(2011年)初め(あくまで予定) inoue 2010-12-23
Herokuの発音 inoue 2010-12-20
雑誌記事「ソフトウェア・テストPRESS Vol.9」の原稿公開 inoue 2010-12-18
IPA未踏のニュース inoue 2010-12-15
労基法とチキンゲーム inoue 2010-12-06
フロントエンドエンジニア inoue 2010-12-03
ASCII.technologies誌にMapReduceの記事を書きました inoue 2010-11-25
技術評論社パーフェクトシリーズ絶賛発売中 inoue 2010-11-24
雑誌連載「Emacsのトラノマキ」の原稿(part8)公開 inoue 2010-11-22
RESTの当惑 inoue 2010-11-22
「プログラマのためのUXチートシート」を作りました inoue 2010-11-19
「ビューティフルコード」を読みました inoue 2010-11-16
Categories
カテゴリなし
 
Document Actions

ADEXに整数オーバーフローのバグを発見 (ADEXの呪いパート2)

# ADEXに関しては、「ADEXの呪い」(http://dev.ariel-networks.com/Members/inoue/adex)を参照してください。

アリエルの技術の中で、"state of the art"と呼べそうな技術は、ADEXぐらいですが、高度すぎて呪いも深いものがあります。

実際のコードは違うのですが、本質は次のサンプルコードと等価なバグでした。

#include <stdio.h>
#include <stdlib.h>

static int cmp(const void *lhs, const void *rhs)
{
    int64_t l = *(int64_t*)lhs;
    int64_t r = *(int64_t*)rhs;
    return l - r; /* integer overflow bug */
}

int main(int argc, const char **argv)
{
    int64_t arr[] = { 1<<10, 1, 2, (int64_t)1<<40, 1<<20, 666 };
    int i;
  
    qsort(arr, sizeof arr/sizeof arr[0], sizeof(int64_t), cmp);
    for (i = 0; i < sizeof arr/sizeof arr[0]; i++) {
        printf("%lld\n", arr[i]);
    }
    return 0;
}

最後のprintf(3)はソート結果を表示しているだけなので、本質はcmp()関数とqsort(3)の呼び出しの部分だけです。

int64_t値の引き算の結果(64bit)がintに対してオーバーフローします。このため、配列中の値同士の差が大きい場合、ソートが正しく機能しません。

gcc(手元はバージョン3.3.5)に-Wallをつけても、警告を出してくれません。

お客さんからのバグ報告で「再現性のポイントとして(マージ対象の文書の作成)時間を空ける」という指摘がありました。 実に鋭い指摘でした。 AirOneは時刻を64bitで管理していますが、約1時間で31bitの範囲を越えます。

手元で頑張って再現しようとしても再現しないわけです。せっせと文書を作ってマージさせても再現はしません。一時間待ってから(時計を進めてもいいですが)マージしてれば再現したのでしょう。

The URL to Trackback this entry is:
http://dev.ariel-networks.com/Members/inoue/integer-overflow-bug/tbping
Add comment

You can add a comment by filling out the form below. Plain text formatting.

(Required)
(Required)
(Required)
This helps us prevent automated spamming.
Captcha Image


Copyright(C) 2001 - 2006 Ariel Networks, Inc. All rights reserved.