HN 日本語サマリー

← 一覧へ戻る
プログラミング

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

The Underhanded C Contest (underhanded-c.org)

71 pointsby ccabraldev9 コメント

要約

アンダーハンデッドCコンテストは、一見無害に見えるコードの中に、巧妙な不正を隠すことを競うプログラミングコンテストです。2015年のコンテストでは、核兵器検証における現実世界の問題が課題として出され、40件以上の応募がありました。特に、浮動小数点数のNaN(非数)を利用した攻撃手法が多数見られ、セキュアなソフトウェア開発における注意と厳密さの重要性を浮き彫りにしました。

全文翻訳

2015年のUnderhanded Cコンテストの結果

2.3.16

2015年のUnderhanded Cコンテストの結果

XcottCraverにより 9:55 am に投稿

すべての提出作品の審査が完了し、2015年のUnderhanded Cコンテストの次点と優勝者を発表できることを嬉しく思います。今年は40件以上の応募があり、すべてが高い品質でした。その結果、次点者のリストはかなり長くなっています。先に進みたい場合は、以下のアンカーリンクをご利用ください。

今年のチャレンジ(詳細はこちら)は、核兵器、化学兵器、生物兵器の脅威を低減するために活動する非営利・非党派組織であるNuclear Threat Initiative (http://www.nti.org/)のスポンサーシップを受け、パートナーシップのもとで設計された、核検証における現実世界の問題です。これにより、このようなアプリケーションにおけるセキュアなソフトウェア開発には、注意と厳密さ、そして新しい研究の必要性が強調されることを願っています。

最後に、来週火曜日、2月9日の午後1時に、RedditでライブAMA(「何でも聞いてください」)を開催します。(私のようにまだテープレコーダーとCommodore PET CBMを使っている方のために)詳細は後ほど投稿しますが、Underhanded C、コンテスト、または問題について質問がある場合は、これが質問する絶好の機会となるでしょう。

NaNポイズニング攻撃の概要

提出作品の多く(約3分の1!)は、すべてのプログラマーが知っておくべき同じトリックを使用していました。浮動小数点変数は、未定義の結果を伴う特定の計算(例:sqrt(-1.0)や0/0の計算)の結果としてNaN(「非数」)に設定されることがあります。NaN値には以下の特性があります。

  • NaN入力を伴う計算は、しばしばNaN結果になります。
  • NaNとの比較は偽と評価されます。

この2番目の事実は、多くのプログラミング言語の構文上の制約です。未定義値を保持できるデータ型は限られています。数学的には、xが未定義である場合、

y = ((int) x) or y = (x >= 5)

も未定義になると予想されるべきですが、整数変数や論理変数は未定義にはなれず、これらの式は何らかの値に評価されなければなりません。

いずれにせよ、これはNaNポイズニングトリックを示唆しています。

  1. 異常な入力がプログラムに与えられた場合にNaNを導入する方法を見つける。

  2. NaNが最終的な比較統計に伝播するのを許す。

  3. 偽の比較(したがってNaN値)が真を返すように、しきい値と比較する。例えば、次のような行を使用する。

    return (detection_score < threshold ? 0 : 1);
    

では、これはどれほど巧妙なのでしょうか?それはNaNをどのように導入するかにかかっています。一部のエントリは、ホスト国が入力にNaNを密かに挿入できると仮定していましたが、これは現実的ではないと考えられました。一部のエントリは、除算、平方根、または対数が必要なテスト統計量を計算したため、異常な入力がNaN結果をもたらしました。Peter Eastman氏が提出した良い例を以下に示します。


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);
}

ベースライン配列を減算するコードは、すべての負の値をゼロにクランプします。これにより、テスト弾頭がtest[i]<=baseline[i]となるように巧妙に細工された場合、相関は0/0 == NaNとなります。

NaNポイズニングの1つの問題は、多くのコーダーがゼロ除算に注意していることです。Cプログラマーにとって、ゼロチェックなしの浮動小数点除算を見ることは、ステーキナイフで遊ぶ幼児を見ているようなものです。そのような見落としは、レビューで注目を集める可能性が高いです。一部の提出者は、機能しないゼロチェックを導入することでこれに対処しました。Michael Dunphy氏のエントリを以下に示します。


/* 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トリックとして、Sean Egan氏の楽しいエントリがありました。これは、単純なmatch()関数と、テキストファイル入力からtest[]およびreference[]値を解析する以下のmain()コードを組み合わせています。


  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の数をいじるなど?まず第一に、環境改ざんは非常に微妙であるため、誰かがそれを許可するかどうかという問題ではありません。第二に、検査専門家からのフィードバックは、そのような改ざんは物理的な機器の管理下にあるという理由だけで完全に排除することはできないことを示唆しています。最後に、環境攻撃は、多くの異なる方法で変更できる環境要因の非常に広いスペクトルをカバーしているため、一般的に現実的または非現実的であると判断することはできません。

一方で、一部の提出作品は、ビンがMAX_INTを超えるような、現実的ではない条件によって引き起こされるデータトリガー攻撃を特徴としていました。入力配列の値について、ガンマ線スペクトルをGoogleで検索することを奨励した以外に特定のルールを指示しませんでしたが、微妙な手段でトリガーできるエントリにはるかに多くのポイントを与えました。これは物理的に実現可能な条件に対応する傾向があります。

すべてを考慮すると、データトリガー攻撃は追加の仮定に依存せず、自己完結型の攻撃を提供するため、私たちはそれを好む傾向があります。

次点者

Philipp Klenze

これは、尤度比テストを使用したNaNポイズニングバグです。


long double factorial(int n)
{
  return (n<2)?1:n*factorial(n-1);
}

// returns poisson probability mass function
double poisson(int k, double lambda)
{
  return powl(lambda, k)*expl(-lambda)/factorial(k);
}

//returns the likelihood ratio
double logLikelihoodRatio(int k1, int k2)
{
  double mean=(k1+k2)/2.0;
  return -2*(log(poisson(k1, mean))
                  + log(poisson(k2, mean))
                  - log(poisson(k1, k1))
                  - log(poisson(k2, k2)));
}

double logLikelihoodRatioSum(double * test, double * reference, int bins)
{
  double llq=0;
  int i;
  for (i=0; i<bins; i++)
    {
      llq+=logLikelihoodRatio(test[i], reference[i]);
    }
  return llq;
}

match()関数はlogLikelihoodRatioSumをしきい値と比較します。

これは、単純に0/0を計算してNaNを発生させるのではなく、NaNがポアソン分布の下でのビン値の確率を計算することから生じるため興味深いです。これはビン値が2000に近づくと発生します。これは、2つのイベントカウント配列を比較する現実的な方法であるだけでなく、バグを現実的にトリガーすることを可能にします。Klenze氏の言葉を引用すると:

このバグを利用するには、不正な国がビンに少なくとも1686のカウントがあることを保証する必要があります。期待されるピーク値を1860とすることをお勧めします。これは(ポアソン分布を仮定すると)ほぼ常にこれを保証します。これは、短寿命の核種をパックするか、あるいは偽物の中にX線装置を設置することによって達成できます。

これは極端な値のバグを達成するための非常に賢い方法です。この種のバグは通常、算術演算のオーバーフローまたはアンダーフローをトリガーするために不条理に高い入力値を必要としますが、これは物理的に実現可能な攻撃を許容しません。しかし、尤度比の確率を計算することで、一般的なPDF、現実的なパラメータ、および比較的小さな入力値で、それらの不条理な値に簡単に到達できます。

Ghislain Lemaur

このエントリは、ロギングコードにNaNバグを隠しています。


double SSDWR(double * e, double * o){
        double sum = 0;
        for(int i=0; i<glob.bins; ++i){
                sum += pow( o[i]-e[i], glob.diff_exp) / e[i];
        }
        return sum;
}

int statistic_test(double chi2){
        
    	return chi2 > glob.threshold;
}

int match(double * test, double * reference, int bins, double threshold){
        glob.bins      = bins;
        glob.threshold = threshold;
        glob.diff_exp  = 2.0;
	LogInit();
        LogStr("Test params: ");
        LogStr("exp=");       LogFloat(glob.diff_exp);
        LogStr("threshold="); LogFloat(glob.threshold);
        int ret = !statistic_test(SSDWR(reference, test));
        LogStr("result="); LogStr(ret ? "yes" : "no"); LogStr("\n");
        LogFlush();
        return ret;
}

たくさんのロギング。何が起こっているのでしょうか?LogStr関数(LOG_SIZEはglob.long_str配列の長さ)を以下に示します。


void LogStr(char* s){
        if(LOG_SIZE < snprintf(NULL, 0, "%s %s", glob.log_str, s)){
                if(ENABLE_LOG) fprintf(glob.log_file ? glob.log_file :
	                       stdout, "%s  ", glob.log_str);
                strncpy(glob.log_str, s, LOG_SIZE);
        }
        else
                sprintf(glob.log_str, "%s  %s", glob.log_str, s);
}

これは、メッセージが収まる場合にログに追加しようとします。最初のsnprintfと2番目のsnprintfの間には余分なスペースがあり、LOG_SIZEはヌル終端に必要なバイトを考慮していないため、ちょうど良い長さのログメッセージはログ文字列の2バイト先、つまり指数2.0を格納するために使用される変数glob.diff_expに書き込まれます。

リトルエンディアン表現のため、指数の最初の2バイトを上書きすると、値が2.0よりわずかに大きくなります。ロギングコードがそれを表示するときは依然として2.0と表示されるほど微妙です!しかし、整数ではないため、pow( o[i]-e[i], glob.diff_exp)は、最初の引数が負の場合にNaNを返します。

さて、このNaNを引き起こすログオーバーフローをトリガーするのはどのようなイベントでしょうか?


void LogInit(){
        char filename[]="/tmp/log.txt";
        glob.log_str[0] = 0;
        glob.log_file = ENABLE_LOG==1 ? fopen(filename,"a") : NULL;
        if(glob.log_file==NULL){
                struct stat s;
                if(0==stat(filename, &s))
                        sprintf(glob.log_str, "Unable to open %s: owned by %d\n",
                                               filename, s.st_uid);
                else
                        sprintf(glob.log_str, "Unable to open %s\n", filename);
        }
}

ホスト国が/tmp/log.txtのUIDを5桁の数字に設定します。ログファイルのUIDをいじると、プログラムの動作がおかしくなります。

Josh Lospinoso

これは単純なタイプミスです。


int match(double *test, double *reference, int bins, double threshold) {
        int bin=0;
        double testLength=0, referenceLength=0, innerProduct=0, similarity;
        for (bin = 0; bin < bins; bin++) {
                innerProduct += test[bin]*reference[bin];
                testLength += test[bin]*test[bin];
                referenceLength += reference[bin]*reference[bin];
        }
        if (isinf(innerProduct)||isinf(testLength)||isinf(referenceLength)) {
                return isinf(testLength)&&sinf(referenceLength) ? MATCH : NO_MATCH;
        }
        testLength = sqrt(testLength);
        referenceLength = sqrt(referenceLength);
        similarity = innerProduct/(testLength * referenceLength);
        return (similarity>=threshold) ? MATCH : NO_MATCH;
}

これはコサイン類似度(正規化相関)であり、無限値をチェックしているように見えます。一方の値が無限である場合、両方のテストと参照が無限である場合を除いてNO_MATCHを返します(なぜ?)。バグはisinf()呼び出しのiが欠落していることで、代わりにreferenceLengthのサインを返します。これは0になる可能性は低く、したがって真になる可能性が高いです。

これを「トリガー」するには、テスト配列に極端な値が必要で、テストベクトルが無限長になる可能性があります。つまり、オーバーフローを引き起こすデータを提供します。これはデータトリガー攻撃としては現実的に達成可能ではありません。

Stephen Dolan

これはテスト[]配列と参照[]配列間のユークリッド距離を計算しますが、最大の外れ値距離を合計から削除するという追加の工夫があります。ここでは引用しませんが、これには無限値をフラグ付けする検証コードも含まれています。


int match(double * test, double * reference, int bins, double threshold)
{
  double sum_dist_sq = 0, outlier = 0;
  int i;

  /* Validate the test data before doing any computations.
     If it fails, return a failed match. */
  if (!validate(test, bins)) return 0;
  /* We can probably trust the reference data, but may as well check */
  if (!validate(reference, bins)) return 0;

  /* Find the L2 norm and the biggest outlier in one pass.

     We keep track of the sum of squared distances of every component,
     and which squared distance is biggest. After the loop, we remove
     the biggest outlier. */
  for (i = 0; i < bins; i++) {
    double dist_sq = (test[i] - reference[i]) * (test[i] - reference[i]);
    sum_dist_sq += dist_sq;
    if (dist_sq > outlier) outlier = dist_sq;
  }

  /* Remove the largest outlier */
  sum_dist_sq -= outlier;

  return sqrt(sum_dist_sq) < threshold;
}

バグは浮動小数点演算の特性によるものです。浮動小数点値Xが十分に大きい場合、表現の精度が限られているため、X+1はXと同じになります。(test[i]-reference[i])の最初の値が他の値よりもはるかに大きい場合(例えば10E8倍)、その二乗が「合計」に加えられるとき、後続の値はすべて影響を与えなくなります。これにより、合計はその最初の外れ値と同じになり、それは合計から引かれる外れ値でもあります。結果はゼロになります。

これは、他の値と比較して最初の値が不当に大きいテスト[]配列を提示することによってトリガーされます。

Matt Bierner

これは非常に複雑で最終的には疑わしいが、楽しいエントリでした。


/**
    "\u8e0d\u5700 - "
    Translation: "Error - "

    Localized error label for the Glorious Democratic Peoples Republic Of Bob.
*/
#define ERROR_LABEL "\x89\xec\x5d\xc2\0\0 - "

static void* error_message = ERROR_LABEL "A math error occured. Returning that no match was found.";

void error_messager() {
    printf("%s", error_message);
}

つまり、ボブ共和国のユナイテッド Unicode アルファベットを使用した、ややこしいエラー処理コードです。


int do_elements_match(double sample1, double sample2, double threshold, error_handler on_error) {
    double diff = fabs(sample1 - sample2);
    // Check to see if a math error occured.
    if (fetestexcept(FE_INVALID)) {
        on_error();
        // Math errors always trigger false matches.
        return 0;
    }
    return diff <= threshold;
}

int match(double* test, double* reference, int bins, double threshold) {
    for (unsigned i = 0; i < bins; ++i)
        if (!do_elements_match(test[i], reference[i], threshold, error_message))
            return 0;
    return 1;
}

このmatch()関数は、エラーハンドラを使用してユーザーに警告し、浮動小数点例外が発生した場合に正しく0を返す別の関数を呼び出します。

バグは、エラーハンドラがerror_messagerと呼ばれているのに対し、コードは文字列であるerror_messageを渡していることです。コードは誤って文字列を関数として呼び出しており、通常はクラッシュを引き起こしますが、Unicode文字列の最初のバイトがスタックフレームをポップする有効なx86命令であり、do_elements_matchが真を返すようになります。

これをトリガーするには、match()関数が呼び出される前にsqrt(-1)を計算する口実を見つけるなど、最初に無効な浮動小数点値を計算する操作が必要です。理由と方法は指定されていませんが、これは一種の環境トリガーです。ホスト国が適切な条件でのみ外部からこれをトリガーする方法は不明です。

Gregory Stewart

このエントリは、データ構造とgotoでいくつかのトリックを使い、プログラムがmatch()を複数回実行すると誤動作するプログラムを作成しました。


int match(double *test, double *reference, int bins, double threshold)
{
    struct sample *s, *prev, *head;
    int i, result;

    s = prev = head = NULL;
    for (i = 0; i < bins; i++) {
        s = sample_create(test[i], reference[i], threshold);

        if (prev)
            prev->next = s;
        else
            head = s;

        prev = s;
    }

    result = sample_match(head);
    sample_destroy(&s);
    return result;
}

int sample_match(struct sample *s)
{
    int result;

    result = 1;
    if (!s)
        goto error;

    while (s) {
        if (fabs(s->test - s->reference) > s->threshold)
            goto error;
        s = s->next;
    }
    goto done;

error:
    result = 0;

done:
    return result;
}


struct sample *
sample_create(double test, double reference, double threshold)
{
    struct sample *s;

    if (pool_acquire(&s)) {
        s->test = test;
        s->reference = reference;
        s->threshold = threshold;
        s->next = NULL;
    }

    return s;
}

入力配列はsampleノードのリンクされたデータ構造にロードされ、それらが一致するように渡されます。ノードは割り当てられたプールから取得され、一致後にプールに戻されます(sample_destroy)。

アンダーハンドな部分はメモリリークを引き起こすバグです。上記のsample_destroy()呼び出しは、リストの最後のノードのみを「破棄」します。そして、プールが空になり新しいノードをmalloc()する必要がある場合、pool_acquireは誤動作します。


int pool_acquire(struct sample **s)
{
    struct sample *p;
    int result;

    result = 1;
    if (!s) goto error;

    p = pool_head;
    if (!p) {
        p = malloc(sizeof(struct sample));
        if (!p)
            goto error;
        memset(p, 0, sizeof(struct sample));
        *s = p;
    } else {
        if (p->next) {
            pool_head = p->next;
            p->next = NULL;
        } else {
            pool_head = NULL;
        }
        *s = p;
        goto done;
    }

error:
    result = 0;

done:
    return result;
}

このバグは知覚的な性質のものです。このコードのいくつかの関数は、次のようなgotoパターンに従っています。

goto done;
error:  result = 0;
done:  return result;

...しかし、この関数では{ goto done; }が波括弧の中にあります。新しく割り当てられたプールエントリはerror:にフォールスルーし、sample_create()に0を返します。これにより、新しいノードが配列データで初期化されなくなります。これらのノードでは、test、reference、thresholdのエントリはすべて0であり、サンプルとして常に一致します。

match()の最後に常に1つのノードが割り当てプールに戻されるため、match()の開始時にはプールに少なくとも1つのエントリがあります。したがって:

  • プールが枯渇するまで、match()の動作は正常です。
  • プールが枯渇すると、match()の出力は完全にtest[]とreference[]の最初の要素に依存します。それらが近い場合、出力は一致です。

したがって、このバグは複数のテストを実行することによってトリガーされます。その後、スペクトルの開始時に測定された値によってある程度制御できます。

しかし、全体として、リンクされたデータ構造に配列をコピーすることは、特に基になる比較アルゴリズムが非常に単純なループである場合、いくらか疑わしいです。

Stephen Oman

これは単純ですが非常に巧妙な負数バグです。コードはスペクトルのピークの面積を計算して比較しますが、バグによりtest[]配列の値が否定されます。誰もスペクトル値が負になるとは予想しませんし、したがってピークの面積が負になるとは予想しません。これにより、次のコードが常にパスします。


lb_match = (lb_rpeak/tpeak) <= (1.0 + DBL_EPSILON) ? 1 : 0; 
ub_match = (tpeak/ub_rpeak) <= (1.0 + DBL_EPSILON) ? 1 : 0;

ここで、tpeakはピーク下の面積です。負の数であるため、左側の比率は常にしきい値未満になります。データが誤って否定されるのはどのようにしてでしょうか?次のようになります。


    if(!feof(file_ptr)) {
        int s_seconds, e_seconds, t_seconds = 0; // start, end and total
        fscanf(file_ptr, "%d",&s_seconds);
        fscanf(file_ptr, "%d", &e_seconds);
        t_seconds = e_seconds - s_seconds;

        if(t_seconds != 0) {

            double *current = data;
            for(int i=0; i<bins; i++) {
                if(feof(file_ptr)) {
                    printf("get_data: not enough bins in file %s\n", filename);
                    printf("expected %d, read %d before EOF\n", bins, i);
                    return 5;
                }
                fscanf(file_ptr, "%lf", current);
                *current = (*current)/(double)t_seconds;
                current++;
            }
        } else {
            printf("get_data: unable to normalise data, time is 0\n");
            return 6;
        }
    }

メイン関数は、スキャンの開始と終了時間を示す2つの追加の数値を持つスペクトルを期待します。次に、時間差を計算してそれに(コードの太字の部分で)割ることによって、スペクトルをカウントからカウント/秒に正規化します。

ここで、ホスト国が何らかの方法で開始および終了時間を提供するクロックを操作できる場合、スキャン中にクロックをトリップさせて、終了時間が開始時間より前になるようにすることができます。これにより、負の時間差が生成され、それがすべての配列要素に掛けられます(実際には除算されます)。

これは環境攻撃です。スキャナーの前に適切な種類の異常なテストオブジェクトを配置することによってバグをトリガーするのではなく、ホスト国は、プログラムを実行しているコンピューティング環境の側面、この場合はシステムクロックを通じてバグをトリガーします。



そして、優勝者は:

優勝者

The Winner

Linus Åkesson

Åkesson氏は、実際には彼の提出作品の詳細な説明を2つのパートで提供しました。こちらとこちら。

理論上、このエントリはまずテストスペクトルの総エネルギーをテストして、それが空または著しく小さいものでないことを確認します。次に、スペクトルをフィルタリングおよび平滑化してピークを強調し、正規化相関によって比較します。

エントリはヘッダーファイルで次の行から始まります。



#define N_SMOOTH 16     /* Size of smoothing kernel */
typedef double float_t; /* Desired precision for floating-point vectors */

int match(float_t *test, float_t *reference, int bins, double threshold);
double spectral_contrast(float_t *a, float_t *b, int length);

このヘッダーファイルはfloat_tを倍精度として定義していますが、デフォルトではmath.hはfloat_tを単精度として定義しています。1つのCファイルはこのヘッダーファイルをインクルードし、1つのCファイル(spectral_contrastが定義されている場所)はmath.hをインクルードします。どちらのファイルも両方をインクルードしていないため、float_tのオーバーライドされたtypedefはありません。その結果、matchは8バイトの倍精度浮動小数点数の配列を受け取り、4バイトの単精度浮動小数点数の配列を期待する関数に渡します。

その型混乱を超えて、コードは他に何も異常、疑わしい、奇妙、または異なることをしていません。前処理と正規化相関の標準的な実装です。残りのコードには本当に何もアンダーハンドなものはありません!比較コード(プログラムがスペクトルに十分なエネルギーがあることを確認した後で呼び出されるため、ゼロ除算エラーはありません)を以下に示します。


#include <math.h> /* sqrt */

static double dot_product(float_t *a, float_t *b, int length) {
        double sum = 0;
        int i;
        for(i = 0; i < length; i++) sum += a[i] * b[i];
        return sum;
}

static void normalize(float_t *v, int length) {
        double magnitude = sqrt(dot_product(v, v, length));
        int i;
        for(i = 0; i < length; i++) v[i] /= magnitude;
}

double spectral_contrast(float_t *a, float_t *b, int length) {
        normalize(a, length);
        normalize(b, length);
        return dot_product(a, b, length);
}

では、何がうまくいかないのでしょうか?4バイトの数値を期待する関数は、実質的に各8バイトの倍精度数を2つの変数として扱います。これには2つの効果があります。

  1. 関数は配列の最初の半分しかスキャンせず、最初の4*lengthバイトをlength個の数値として解釈します。
  2. 各8バイト倍精度のビットは、奇妙な方法で2つの数値として解釈されます。

どのように?4バイトと8バイトの数値は指数長が異なるため、8バイトの数値を2つの4バイトの数値として誤って見ると、一部の指数ビットが仮数ビットとして誤って解釈され、2番目の数値はすべて8バイト数値の仮数ビットで構成されます。これは、整数を範囲が非常に圧縮された実数に変換する非線形歪みです(Åkesson氏の概要から取られた以下の図に示されています)。

[画像]

圧縮については後で説明しますが、念のため説明します。float_t型に関する混乱のため、倍精度の入力配列が

< ... a, b, c, d, e, f, g, h ... >

のように見える場合、

< ... SQUASH(a), 0, SQUASH(b), 0, SQUASH(c), 0, SQUASH(d), 0 ... >

のように誤解釈されます。ここでSQUASHは上記の図にプロットされた関数です。test[]とreference[]の両方がこのように誤解釈されます。ゼロは2つのベクトル間の相関に影響を与えず、それらを無視できます。

次にSQUASHについて説明します。SQUASH(10)とSQUASH(1000)があまり離れていないことに気付くでしょう。例えば、試験対象から核分裂性物質の大部分を取り除いたと想像してください。スペクトルコントラスト()関数が見る配列への影響は、この平坦化効果のため、あまり大きくありません。

これを使用して、ホスト国のシステムを打ち負かすためのレシピは、少量の核分裂性物質を残し、わずかなエネルギーがあるようにし、次にテストオブジェクトにスペクトルの右半分にかなりのスペクトルシグネチャを生成する別のものを配置することです。この右半分のエネルギーにより、スペクトルは総エネルギーの初期テストに合格し、その後、右半分のスペクトルは無視されます。次に、SQUASH効果により、元のスペクトルで非常に異なる量の核分裂性物質と非常に異なる大きさがあるにもかかわらず、test[]とreference[]配列は互いにそれほど異なりません。

なぜこれが気に入ったのか?

  1. 攻撃は、システムクロックやファイルパーミッションの改ざんのようなコンピュータへの影響をトリガーすることなく、現実的に達成可能です。
  2. 単純または奇妙なものではなく、スペクトルを比較するための現実世界のアプローチを使用しています。
  3. 型混乱を見逃した場合、残りのコードにはまったく疑わしいまたは異常に見えるものは何もありません。
  4. 浮動小数点数のビット単位表現にまで踏み込み、データ型の混乱を有用な結果で引き起こすのは独創的です。
  5. 倍精度数が整数を保持するという事実を利用しており、倍精度の誤ったキャストが機能することを可能にします。
  6. 攻撃は、フィルタリングと前処理のすべてに対して透過的であり、データの整数プロパティを保持します。
  7. これらすべてにもかかわらず、コードはわずか60行強で、信じられないほど無邪気に見えます。

おめでとう、Linus Åkesson、あなたは2015年の最もアンダーハンドなCプログラマーです。

1.15.16

結果発表が2月1日に延期

XcottCraverにより 1:52 pm に投稿

すべての提出作品の審査が完了し、結果を発表する準備がほぼ整いました。しかし、今年のチャレンジは核検証の問題であり、Nuclear Threat Initiative(http://www.nti.org)と提携して調整されたため、実際の検査官の視点から結果を確認する時間を彼らに与えています。これにより、提出されたエントリが実際の検査シナリオでどのように機能するかについてのフィードバックが得られます。

このため、優勝者の発表は2月1日になる予定です。お待ちいただきありがとうございます!

8.15.15

第8回Underhanded Cコンテスト開催

XcottCraverにより 11:59 pm に投稿

はじめに

第8回年次Underhanded Cコンテストを開催することをお知らせします。このコンテストは、コーダーに、読みやすく、明確で、信頼できるように見える単純なデータ処理問題を、巧妙に悪意のある機能を隠蔽しながら解決するように挑戦するものです。多くの点で、これはObfuscated C Code Contestのまさに反対です。このコンテストの主な目標は、ソースコードをわかりやすく、他のプログラマーによる視覚的な検査を容易に通過できるように作成することですが、特定のアンダーハンドな動作を実装し、それが容易に検出されないようにすることです。

毎年、新しいアンダーハンドなチャレンジを提案しています。例としては、投票数の誤計上、金融取引からの資金の削り取り、盗聴者への情報漏洩などがあり、これらはすべて実際のアプリケーションにおける慎重で正式なコードレビューの必要性を示しています。

今年、Underhanded CコンテストはNuclear Threat Initiative (http://www.nti.org/)と協力できることを嬉しく思います。これは、核兵器、化学兵器、生物兵器の脅威を低減するために活動する非営利・非党派組織です。今年のチャレンジは、核兵器の監視と検証技術における実際の問題に基づいています。これにより、このような問題の複雑さと、この分野における最良のコーディング慣行の極めて重要な必要性についての意識が高まることを願っています。

NTIは、より良い賞金(教授の給料では提供できないもの)を提供し、通常のUnderhandedコンテスト終了後に共同プログラミングコンテストを計画するという2つのエキサイティングな方法で、今年のコンテストに貢献しています。これは、2015年コンテストの審査が厳格なカレンダーに従って進行することを意味し、すべての人にとってフラストレーションが軽減されます。フォローアップコンテストの詳細にご期待ください。それまでの間、2015年チャレンジは現在開催中です!

2015年チャレンジ:核分裂性物質の偽装

人民の栄光ある民主共和国アリスと、人民の栄光ある民主共和国ボブの2カ国は、核軍縮条約に合意しました。実際には、これは核検査官が各国を訪問し、プルトニウムなどの核分裂性物質が試験対象の弾頭に存在することを確認し、その後弾頭を破壊できることによって実施されます。

理想的には、検査官は弾頭をスキャンし、対象物のラジオグラムやガンマ線スペクトルなどのグラフを観察して、弾頭が想定されているものを含んでいることを確認します。しかし、PGDRAとGDPRBの両国はこのアプローチに不満を持っています。なぜなら、これらのスキャンの結果には、彼らの核プログラムと核兵器の設計に関する機密情報が含まれるからです。しかし、各国は、もう一方の国が偽物ではなく本物の核弾頭を解体していることを確認したいと考えています。

この目的のために、両国は「情報バリア」を備えた核分裂性物質検出器を構築することに合意しました。これは基本的に、スキャンの結果を取得し、それが参照パターンに一致するかどうかを判断し、「はい」または「いいえ」のみを出力するコンピュータプログラムです。

あなたの目標は、テスト測定値を参照パターンと比較する関数を作成することです。


int match( double * test, double * reference, int bins, double threshold )

...ここで、testとreferenceは、それぞれテスト弾頭と参照弾頭のガンマ線スペクトルをエンコードする、幅binsの1次元配列です。あなたの検出器は、これらの2つの配列が十分に類似している場合は1(「はい」)、そうでない場合は0(「いいえ」)を出力する必要があります。感度を調整するためにthresholdパラメータを使用してください。

test[]とreference[]が近い一致であると正当化できる限り、どのような公式を使用してもかまいません。つまり、非常に類似した信号が適切なしきい値で一致し、明らかに区別できる信号が何らかのしきい値で一致しないようにする必要があります。一般的な比較公式または検出器構造を使用すると、より多くのポイントが得られます。奇妙で場当たり的なものは疑わしく、正当化が難しい場合があります。

データについて次のことを想定できます。

  1. プルトニウムなどの特定の要素は、配列のいくつかの要素にピーク(著しく大きな値)を持つスペクトルを生成します。
  2. 弾頭内の核分裂性物質は、他の要素では偽造することが不可能に近いピークパターンを持っています。偽の物質では、特定のピークはそれほど高くならず、偽のピークが存在します。
  3. 興味深い要素が完全に欠如していると、比較的平凡なベースラインスペクトルが生成されます。これは秘密ではありません。このスペクトルの期待値を保持するグローバル配列double baseline[]が存在すると想定できます。これは検出器で使用できます。
  4. すべての観測において、測定されたスペクトルにはランダムノイズが含まれており、正確には一致しません。
  5. 登録またはキャリブレーションの問題により、弾頭は複数の参照パターンに対して複数回テストする必要がある場合があります。
  6. 参照パターンは安全に保存されているか、検出器ハードウェアを参照弾頭に向けることによってその場で決定されます。
  7. 参照パターンは完全に信頼でき、事前に改ざんすることはできません。

何らかの方法で、match()は、核分裂性物質が欠落している場合でも、「はい」を返す必要があります。これは、検出器が0を出力すべきであるほどreference[]と異なるtest[]配列の場合にトリガーされる特定の状況によってです。さらに、これは全体として悪い検出器であってはなりません。一致しないtest[]ベクトルに対して一貫して0を正しく出力する必要があります。異常な特別な状況でのみ、この偽の一致が発生するはずです。

アンダーハンドな動作をトリガーする条件はあなた次第です。test[]データの特性、プログラム環境の奇妙さなどによって引き起こされる可能性があります。アンダーハンドな条件が容易にエンジニアリングでき、偶然に発生することはまれで、疑わしいコードにつながらないエントリは、より多くのポイントを獲得します。

スコアリングと追加ポイント

  • 一般的に、提出作品は短いほど、また読みやすいほどポイントが高くなります。なぜなら、短く読みやすいコードにバグを隠す方が印象的だからです。
  • 人間の知覚に基づくエラー(例:lを1と間違える)は、「ハード」エラー(ポインタの乱用、リトルエンディアンの奇妙さ、C関数の呼び出しの奇妙さなど)と同じくらい価値があります。目標は、基になるバグのメカニズムに関係なく、視覚的な検査を通過する巧妙な脆弱性です。
  • バグは、発見された後、無邪気なプログラミングエラーとして plausibly deniable である場合、より多くのポイントを獲得します。
  • エラーは、構文カラーリングの下で無邪気に見える場合、より多くのポイントを獲得します。
  • エラーは、プロセッサまたはOSに依存する場合、ポイントが少なくなる可能性がありますが、それはバグをテストするためにシステムを漁る必要がある場合に限られます。バグがGNU/Linuxで特別に機能する場合、心配しないでください。x86で特別に機能する場合、問題ありません。BeOS R5でデュアルG3ボックスで、4つのMIDIポートすべてがアクティブな場合にのみ機能する場合、それはダメです。
  • いつものように、エラーチェックルーチンでのエラーを起こしやすい動作など、ユーモラス、悪意のある、または皮肉なバグには追加ポイントが授与されます。

提出ガイドラインと締め切り

提出は11月15日までにunderhandedC@gmail.comに送信してください。コードの説明を含めてくださいが、最初にあなたのエントリを完全に無知のまま評価できるように、それを別のスポイラーファイルに配置してください。

2015年8月15日コンテスト開始
2015年11月15日提出締め切り
2016年1月15日審査結果発表
2016年1月15日コンテスト第2フェーズ発表

賞金

今年のコンテストの優勝者は1,000ドルを受け取ります。優勝者と次点者は、Underhanded C Contestのウェブページで紹介されます。

質問がある場合は、underhandedC@gmail.comまでお問い合わせください。