Zenn
🎃

【論文紹介】遺伝的アルゴリズムによる故障注入パラメータ探索高速化の定量的評価

2023/03/10に公開
Security
ハードウェアセキュリティ
フォールト
tech

せっかくなので読んだ論文を紹介（要約？）していこうと思う．自分のメモ書きに毛が生えたものなので内容の正確性や解説までは期待しないように．
著作権のことはよくわからないので，公開されてる論文であっても画像引用などはとりあえずしないようにする．
文献番号は論文のものをそのまま使う．ここでは参考文献は示さない．
自分にわかるようにしか書いてないので，わからない点も多いと思う．質問や指摘はどしどし募集中．学生さんも気軽に聞いてください

今回の論文

要約

  • フォールト攻撃を成功させるにはパラメータの探索が必要
  • 特に攻撃者はうまくいくパラメータを一つ見つければよいが、評価者的には、”どれくらいあるか”を知りたい
  • 膨大なパラメータを探索するための3つの手法（線形スキャン、モンテカルロ（MC）、遺伝的アルゴリズム（GA））を定量的に比較した

所感

  • フォールト攻撃のパラメータ空間は膨大（手法によるが、空間3次元・時間・時刻・強度など5, 6次元くらいある）で、確かに探索は大変な作業。
  • ただしこの論文では空間2次元の探索結果しか示されていない。まあタイミングとかはある程度推測できるとは言え少し残念。
  • 比較結果も、まあそうだろうなあという程度。GAが一番良いという結論になっているが自明っぽい。
  • そもそも、特にGAは故障が起きる注入場所が空間的にある程度固まっているという仮定を置いているため、それでいいのか？という思いはある。

1. Introduction

  • フォールト攻撃は２ステップで行われる．
    • perturbation phase: 実際のフォールト注入
    • fault exploitation: 認証を突破したり統計処理を行ったり？様玉な解析手法が提案されている．
    • 正しい注入パラメータを得ることは非常に重要．これはn次元の地図作成問題？に帰着
  • 2013年にパラメータ探索手法としてモンテカルロ法及び遺伝的アルゴリズム（GA）が提案[13]
  • GAはその後EMFIに適用[14, 15]され，さらにいわゆるmemetic algorithm (MA)の局所探索と組み合わせて利用される．
  • 近年MAはLFIにも適用[17]
  • 本紙では3つの一般的なカートグラフィー戦略、すなわちリニアスキャン、MC、GAベースの戦略を公正に比較する．
    • リニアスキャンは実装が簡単だがPOIの発見に時間がかかる．
    • MCは均一な発見が可能だが既知の結果に対して盲目的
    • GAは以前の測定値を活用して探索を洗練させる
  • 本論文では、これらの性能を定量化し、予想されるPOIの数に応じて、どの戦略をとるべきかを決定する。その結果、GAを用いた場合、リニアスキャンやMC法よりもPOIの割合が高くなることがわかった。また、GAによるPOIの特定速度は、他の地図作成手法の25%に対し、処理の60%で40%以上のPOIを発見することができ、GAによるPOI特定速度は著しく高い。

2. Points of interest

  • 攻撃者は攻撃が成功するパラメータを一つ見つければ十分だが，評価者的には”良い”パラメータを高速に探索したい．
  • 探索は空間/時間/強度などの各次元に対応させる必要があるが，一つの次元でも削減できれば全体の時間は短縮される．
  • PoI=期待される結果とは異なる結果を引き起こすパラメータのタプル
  • PoIがどれくらい存在するのかを予測するのは難しい．
  • 内部状態に依存し，デバイスが故障したりするため，必要最小限の実験で多くのPOIを見つけたい．

A. Spatial distribution

  • しばしばPoIはAoIとしてグループ化される．
  • 図1はリニアスキャンしたときのもの

B. Intensity distrubution

  • EMやレーザーの場合，振幅とパルス幅
  • ２次元の地図作成になる．（図２）

C. Temporal distribution

  • 最も重要な次元（図３）
  • 地図作成の難易度は，攻撃者がデバイスの動作について知っている知識による．
  • 例えばAES実行時とかは電力波形から簡単

D. Amplitude and delay distribution

3. Fault injection cartographies

A. Experimantal setup

  • Target

    • AES-128 on Spartan-6
    • トリガは出てる．（つまり時間次元はかなり小さい）

  • Pulse generator

    • AVRK-4-B高電圧パルサー
    • 750 V max
    • 6-20 ns pulse

  • XY positioner

    • 1 um 分解能

  • チップ上の異なる領域を選ぶことでPoIの割合を変えられる？

    • small AoIs, great AoIと呼ぶ

  • 故障は全てpersistentと仮定し，フォールトが出力されたらリセットする．

B. Linear-Scan methods

  • 各次元で一定のステップをもってPoIを変化
  • アルゴリズム１
  • 結果は図７（small AoIs），図８（great AoI）

C. Monte-Carlo method

  • ランダムにやる．
  • アルゴリズム２は効率化のために，点を生成した後にソートする．
  • 重複もなし？
  • モンテカルロ法なので，真のPoIの割合を区間推定できる．
  • 結果は図9（small AoIs），図10（great AoI）

D. Genetic Algorithm-based methods

  • 注入結果から適応的に次の点を生成する．
  • PoIが近接するという仮定に基づく．
  • ３つのステップ
    • Initial generation: 乱数で初期点を生成．生成された点はソートする．すべての点が生成されたら照射
    • Fitness evaluation: 新しい点が生成され，フォールト注入されたら，得られた結果が現世代のfitness valueとしてアサインされる？
    • New generation process:
  • 結果は図12（small AoIs），図13（great AoI）

4. Establishing the optimal cartography strategy

  • 各手法には利点と欠点が存在するのでフェアに比較しなければならない．
  • 比較のmethodologyを提供
    • 得られたサンプルの品質
    • AoI特定能力
    • 新たなPoIを蓄積する効率？
  • パラメータは以下
    • AES: 750 ns
    • Delay: 500 ns
    • Amplitude: -280 V
    • Width: 10 ns
    • # of injections for each pos.: 4
    • # of selected positions for each method: 2500
  • 総当たりしていないので真のPoI数はわからないが，MC法で区間推定したものから推定できる．

A. Combining cartography methods

  • GAとMCの組み合わせをなぜかここで提案している．
    • GAのselection時に1-P%の点だけMC法で生成する（つまり完全ランダム）
    • 結果は図１４で，図12と比較するとPoI が集中していない．

B. General case: small proportion of PoIs

  • 最初のPoIを見つけるのにMC/GAは数回なのに対して，リニアスキャンは500回？（図15からわかるのだろう）
  • 20%の時点でMC/GAは真値からの偏差？が最大となっており，サンプルの品質が良い
    • この時点で、MC法では約18％、古典的なGA法では21％、GA＋MCの複合法では20％から33％のPoIが回収
  • 60%以降はMC法とLinear- Scan法では新しいPoIは発見されない。
  • MC/Linearは約25%のPOIしか発見できないのに対してGA法では約44%発見できる．
  • 表1が最終結果
  • 基本的にはGAが良い結果．最初のほうでもわかるし，最終的にもかなりのPoIを発見できる
  • LinearとMCは最終的には大体同じ性能になるが，最初のほうはMCのほうが良い．

C. Specific case: great propotion of PoIs

  • 各手法にあまり差がない（図16と表2）
  • 80%を超えたあたりからGAが少しよくなってくる

Remark 2: 両方のケースでLinear/MCは最終的に約25 %のPoIを発見しているが，これは1万点の空間に対して2500点に照射しているから．

Discussion