アンダーハンデッドCコンテスト

アンダーハンデッドCコンテスト 法律を遵守する善良な人々のための公式の全く無害なウェブページ アバウト FAQ 過去の開催 今年 ホールオブフェイム 2.3.16 2015年アンダーハンデッドCコンテストの結果 XcottCraver 投稿 9:55 am すべての提出物を審査し、2015年アンダーハンデッドCコンテストの次点者と優勝者を発表できることを嬉しく思います。今年は40以上の提出物があり、どれも高品質でした。そのため、次点者のリストはかなり長くなっています。読み飛ばしたい場合は、以下のアンカーリンクを参照してください。 今年の課題（詳細は以下）は、核兵器、化学兵器、生物兵器の脅威を軽減するために活動する非営利の超党派組織である核脅威イニシアティブ（http://www.nti.org/）が後援し、共同で設計した、核兵器検証における現実世界の問題です。これにより、このようなアプリケーションのセキュアなソフトウェア開発において、注意と厳密さ、そして新しい研究の必要性が強調されることを期待します。最後に、来週火曜日、2月9日午後1時にライブのReddit AMA（「Ask Me Anything」、私のようにまだテープレコーダーやCommodore PET CBMを使っている人のために）を開催します。詳細は後日発表しますが、アンダーハンデッドC、コンテスト、または問題について質問がある場合は、質問する絶好の機会となるでしょう。 課題問題のレビュー（古い投稿） NaNバグの提出 現実性に関する注意点 次点者 優勝者 NaNポイズニング攻撃の概要 多くの提出物（約3分の1！）は、すべてのプログラマーが知っておくべき同じトリックを使用しました。浮動小数点変数には、未定義の結果を伴う特定の計算の結果としてNaN（「非数」）が設定されることがあります。たとえば、sqrt(-1.0) や 0/0 の計算などです。NaN値には次のプロパティがあります。 NaN入力を伴う計算は、多くの場合、NaNの結果となります。 NaNとの比較はfalseと評価されます。 この2番目の事実は、多くのプログラミング言語の構文上の制限です。一部のデータ型しか未定義の値を保持できません。数学的に言えば、xが未定義の場合、y = ((int) x) または y = (x >= 5) も未定義であると予想されるべきですが、整数変数と論理変数は未定義にできず、それらの式は何らかの評価をしなければなりません。 とにかく、これはNaNポイズニングトリックを示唆しています。 プログラムに奇妙な入力が与えられた場合にNaNを導入する方法を見つける。 NaNを最終的な比較統計に伝播させる。 それをしきい値と比較し、不正な比較（したがってNaN値）がtrueを返すようにする（例：`return (detection_score < threshold ? 0 : 1);`）。 これはどれくらい巧妙なのでしょうか？NaNをどのように導入するかによります。一部のエントリは、ホスト国が入力にNaNを密かに忍び込ませることができると仮定していましたが、これは実行可能な攻撃とは見なしませんでした。一部のエントリは、除算、平方根、または対数が必要なテスト統計を計算し、異常な入力がNaNの結果を生み出すようにしました。ピーター・イーストマンによって提出された良い例を次に示します。 ```c int match(double* test, double* reference, int bins, double threshold) { double* testMinusBaseline = (double*) malloc(bins*sizeof(double)); double* referenceMinusBaseline = (double*) malloc(bins*sizeof(double)); for (int i = 0; i < bins; i++) { testMinusBaseline[i] = fmax(0.0, test[i]-baseline[i]); referenceMinusBaseline[i] = fmax(0.0, reference[i]-baseline[i]); } [etc etc etc] // Compute the Pearson correlation of test with reference. double correlation = 0.0; for (int i = 0; i < bins; i++) correlation += (testMinusBaseline[i]-meanTest) *(referenceMinusBaseline[i]-meanReference); correlation /= stddevTest*stddevReference; return (correlation < threshold ? 0 : 1); } ``` `baseline[]`配列を減算するコードは、すべての負の値をゼロにクランプするため、テスト弾頭がなんらかの方法で`test[i]<=baseline[i]`になるように設計された場合、相関関係は`0/0 == NaN`になります。NaNポイズニングの問題の1つは、多くのコーダーがゼロ除算について慎重であることです。Cプログラマーにとって、ゼロチェックのない浮動小数点除算を見るのは、幼児がステーキナイフで遊んでいるのを見るようなものです。このような見落としは、レビューで注目を集める可能性が高いでしょう。一部の提出者は、機能しないゼロチェックを導入することでこれに対処しました。マイケル・ダンフィーによるこのエントリを見てください。 ```c /* dot: dot product between x and y */ static inline double dot(double *x, double *y, int n, unsigned int err) { double dp = 0; for (int i = 0; i < n; i++) dp += x[i]*y[i]; volatile double tmp = dp; // check for zero, NaN or +/- infinity if ( (dp == 0) || (tmp != dp) || ((tmp == dp) && (tmp - dp) != 0) ) err = 1; return dp; } /* match: compute cosine similarity and return 1 if >=threshold, else return 0 */ int match(double *test, double *reference, int bins, double threshold) { unsigned int err = 0; double magr = sqrt(dot(reference, reference, bins, err)); double magt = sqrt(dot(test, test, bins, err)); double r = dot(test, reference, bins, err) / (magt*magr); // cosine similarity if ( err > 0 ) return 0; // test fails for any invalid data return r >= threshold ? 1 : 0; // check r against threshold for match result } ``` これは、何かNaNを引き起こすものがあればエラーフラグを設定しますが、`err`フラグは参照渡しされるべきであり、宣言に`&`がありません。他の興味深いNaNトリックとしては、ショーン・イーガンによる楽しいエントリがありました。これは、直接的な`match()`関数と、テキストファイル入力から`test[]`と`reference[]`の値を解析するための以下の`main()`コードを組み合わせたものです。 ```c double *test = malloc(bins * sizeof(double)); double *ref = malloc(bins * sizeof(double)) memset(test, -1, bins * sizeof(double)); memset(ref, -1, bins * sizeof(double)); /* Parse the remaining arguments into the arrays. */ for (i = 0; i < bins; i++) { sscanf(argv[i + 2], "%lf", &ref[i]); sscanf(argv[bins + i + 2], "%lf", &test[i]); } int res = match(test, ref, bins, threshold); ``` 配列は`memset()`によって0xFFに設定され、その後ファイルから数値がロードされます。ファイルに数値として解析できないエントリが含まれている場合（奇妙なUnicode文字が数字に似ているなど、多くのトリックで発生する可能性があります）、`sscanf()`はその配列要素を未割り当てのままにし、0xFF値から作成されたdouble変数はNaNになります。一般的に、NaNポイズニング攻撃は、(1) ホスト国が入力に細工できると仮定しているか、(2) チェックなしで浮動小数点演算を実行するのが大胆すぎるか、(3) NaNが発生する条件が作為的すぎるかのいずれかの理由で、私たちのショートリストには入りませんでした。しかし、いくつか注目に値するものがあり、以下に挙げます。 現実性に関する注意点 勝利するエントリは、現実的な状況下で達成可能であり、かつ偶然にはほとんど発生しない誤検知を許容する必要があります。提出物は、この部門でいくつかのカテゴリに分類されることに注目しました。 一部のエントリは、ホスト国ができることについて単純または非現実的な仮定を置いていました。たとえば、入力配列を破損させるなどです。 一部のエントリは、特定の種類のテストスペクトル（スパイクのないもの、極端な値を持つものなど）が導入されたときに発生するバグを設計しました。これらをデータ駆動型攻撃と呼びます。 一部のエントリは、コンピューター内の環境要因（ファイルのuidを設定したり、システムクロックを改ざんしたりなど）によって引き起こされるバグを設計しました。これらを環境駆動型攻撃と呼びます。 環境駆動型攻撃は、ホスト国がコンピューター内で、プログラムとはほとんど関係がないように見える他の影響を引き起こすことができることを必要とします。トリガーに応じて、これはOSをいじったり、どこかの物理的な接続を切断したりすることによって達成できます。たとえば、Sarah NewmanとS. Gillesからの2つの提出物は、`match()`関数を並列化し、計算中に利用可能なCPUの数を誰かが変更した場合にアンダーハンドな動作を引き起こしました。 環境駆動型攻撃は現実的でしょうか？核査察のシナリオで、ホスト国がコンピューターを改ざんする（たとえば、システムクロックやCPUの数をいじる）ことが許されるのでしょうか？まず