7

暗号関数を C から Java に移植したいと考えています。関数は一定時間内に実行する必要があるため、条件分岐(およびx に基づくテーブル ルックアップ) は許可されません。

元の C コードは次のとおりです。

int x,result;
...
result = (x==7);
...

したがって、「結果」は、「x==7」の場合は 1 に設定され、それ以外の場合は 0 に設定されます。「結果」変数は、その後の計算で使用されます。

これをJavaに転置する最良の方法を探しています。Java 式では、整数ではなくブール値に評価されるため、演算子を使用して上記をシミュレートする必要があります。

私は現在使用しています

int x,result;
...
result = (1<<(x-7))&1;
...

私の x は範囲 {0,...,15} にあるので、これはうまくいきます。(シフト関数は下位 5 ビットのみを使用するため、x が大きすぎる場合に誤検知が発生することに注意してください。)

式は何百万回も評価されるため、たとえば、演算子を 3 つではなく 2 つだけ使用する巧妙なソリューションがあれば、全体の計算が高速になります。

4

5 に答える 5

7

@ Hosch250 が指摘した最良のオプションは、三項演算子です。このメソッドの JIT コンパイラによって生成されたアセンブラを見てみましょう。

public static int ternary(int x) {
    return x == 7 ? 1 : 0;
}

実際には、ブランチのプロファイリングに依存します。あなたのx値7が頻繁にある場合、次のようにコンパイルされます。

xor %r11d,%r11d
mov $0x1,%eax
cmp $0x7,%edx
cmovne %r11d,%eax  ;*ireturn
                   ; - Test::ternary@11 (line 12)

cmovne三項が分岐命令ではないものに置き換えられたことを確認してください。

一方7、非常にまれなケース (たとえば、5000 回の呼び出しに 1 回) で合格する場合、分岐は次のとおりです。

cmp $0x7,%edx
je <slowpath>  ;*if_icmpne
                       ; - Test::ternary@3 (line 12)
xor %eax,%eax

現在、分岐はほとんど行われないため、CPU 分岐予測子はほぼ常に正しいため、条件を維持する方が高速です。<slowpath>だけでなく、return 1;ブランチ プロファイルも更新するため、プログラムの実行中にパターンが変更された場合 (7出現頻度が高くなった場合)、メソッドは最初のバージョンに再コンパイルされます。

一般に、このような単純なケースでは、JIT コンパイラよりも賢くなろうとしないでください。

于 2015-09-05T04:18:33.033 に答える
6

OK、あなたがこれを尋ねている理由は、暗号関数の実行時間が関数への入力に依存する場合、攻撃者は実行時間を測定することでそれらの入力に関する手がかりを得ることができるからだと思います. (したがって、通常の「時期尚早の最適化」や「コンパイラの裏をかこうとするな」というアドバイスは実際には当てはまりません。)

それを踏まえて、ここに私の提案があります：

  • xがコンパイル時 (または JIT コンパイル時) に定数である 場合、コードは次のいずれresult = true;かに最適化される可能性があります。result = false;

  • xが定数ではなく、可能な値の範囲が狭い場合は、次のいずれかのアプローチがおそらく機能します。

    // It is possible but unlikely that the JIT compiler will 
// turn this into conditional code.
private boolean[] LOOKUP = new boolean[] {
        true, true, true, true, true, true, true, false};
...
result = LOOKUP[x];

// This depends on how the JIT compiler translates this to native
// code.
switch (x) {
case 0: case 1: case 2: case 3: case 4: case 5: case 6: 
    result = false;
case 7:
    result = true;
}

問題は、考えられるすべてのアプローチにおいて、JIT コンパイラーが非分岐コードを分岐コードに合法的に最適化できることです。これがセキュリティ クリティカルである場合は、認定が必要なすべてのプラットフォームで生成された実際のネイティブ コードを調査する必要があります。

他のアプローチは次のとおりです。

  1. Java コードのアルゴリズムを分析し、
  2. 条件分岐の可能性が高いケースを見つけようとする
  3. これらの分岐パスをトリガーするテスト入力を設計し、
  4. (すべてのターゲット プラットフォームで) 実行時間を測定して、テスト入力のセット全体で検出可能な違いがあるかどうかを確認します。

もちろん、もう 1 つ注意すべき点は、これはいずれにせよ根拠のないものである可能性があるということです。たとえばresult、暗号関数の別の部分で if を使用して、実行パスを決定します。

と ...

式は何百万回も評価されるため、たとえば、演算子を 3 つではなく 2 つだけ使用する巧妙なソリューションがあれば、全体の計算が高速になります。

これがあなたの本当の動機であるなら、私のアドバイスは「気にしないで」です。これは時期尚早の最適化です。JITコンパイラにお任せください。

于 2015-09-05T04:18:11.123 に答える
3

達成することが目的なので、

if (x == 7)
    result = 1;
else
    result = 0;

分岐のないある種の代数的方法で、

result = 1 >> (x^7);

しかし、右シフトが数ビットのみにマスクされているため、これは機能しません。だから、あなたができることは、

result = 1 >> Integer.bitCount(x^7);

ただし、-6 の場合はマスクされます (-6 ^ 7 の場合はすべてのビットが設定されます)。

int bc = Integer.bitCount(x^7);
return 1 >> (bc | (bc>>1));

では、分岐条件分岐よりどれくらい遅いのでしょうか? 上記の bitCount() を使用したソリューションでは、範囲全体を int 範囲で複数回比較します。

user    0m5.948s

分岐 (x == 7 ? 1 : 0) を使用すると、

user    0m2.104s

したがって、7 は単なる例であり、任意の値に対して機能する一定の時間比較が得られることを考えると、それほど悪くはありません。はい、Integer.bitCount() も一定時間です。

于 2015-09-05T05:13:00.997 に答える
2

ここでは 3 進数が適しています。

result = x == 7 ? 1 : 0;

このコードは、式が に評価される1場合に を割り当て、それ以外の場合に割り当てます。resultx == 7true0

于 2015-09-05T00:09:48.763 に答える
2

[0,15] にある x の非常に限られた範囲を利用して、テーブル エントリごとに 1 ビットを使用して、レジスタ内テーブル ルックアップを使用することを提案します。テーブルには、1 を生成する必要がある入力に対して設定されたビットiがあり、それ以外の場合は 0 です。これは、テーブルがリテラル定数 2 7 = 128であることを意味します。

int x,result;
result = (128 >> x) & 1;
于 2015-09-12T21:42:41.590 に答える