(57)【要約】【課題】メモリアクセスパターン保護技術について、安全性を実用的に定量評価できる装置、方法及びプログラムを提供する。【解決手段】安全性評価装置１は、メモリへのアクセスパターンに対して、保護されたアクセスパターンの複数のサンプルを生成するサンプル生成部１１と、サンプル間の距離を算出し、距離の確率分布を取得する確率分布取得部１２と、距離が０となる確率から、衝突エントロピーを算出する第１算出部１３と、衝突エントロピーに基づく漏洩情報量の上限から、平均最小エントロピーの下限値を、安全性指標として算出する第２算出部１４と、を備える。【選択図】図１
2019003442.tif 000002
【特許請求の範囲】
【請求項１】
メモリへのアクセスパターンに対して、保護されたアクセスパターンの複数のサンプルを生成するサンプル生成部と、
前記サンプル間の距離を算出し、当該距離の確率分布を取得する確率分布取得部と、
前記距離が０となる確率から、衝突エントロピーを算出する第１算出部と、
前記衝突エントロピーに基づく漏洩情報量の上限から、平均最小エントロピーの下限値を、安全性指標として算出する第２算出部と、を備える安全性評価装置。
【請求項２】
前記確率分布取得部は、前記サンプル間の編集距離のヒストグラムを、所定の確率分布関数で近似する請求項１に記載の安全性評価装置。
【請求項３】
アクセスパターンの保護技術における設計パラメータを変化させ、前記第２算出部により算出される前記安全性指標が指定値以上となる範囲を導出する範囲導出部を備える請求項１又は請求項２に記載の安全性評価装置。
【請求項４】
前記範囲の中で、コストが最小となる設計パラメータを決定する決定部を備える請求項３に記載の安全性評価装置。
【請求項５】
メモリへのアクセスパターンに対して、保護されたアクセスパターンの複数のサンプルを生成するサンプル生成ステップと、
前記サンプル間の距離を算出し、当該距離の確率分布を取得する確率分布取得ステップと、
前記距離が０となる確率から、衝突エントロピーを算出する第１算出ステップと、
前記衝突エントロピーに基づく漏洩情報量の上限から、平均最小エントロピーの下限値を、安全性指標として算出する第２算出ステップと、をコンピュータが実行する安全性評価方法。
【請求項６】
メモリへのアクセスパターンに対して、保護されたアクセスパターンの複数のサンプルを生成するサンプル生成ステップと、
前記サンプル間の距離を算出し、当該距離の確率分布を取得する確率分布取得ステップと、
前記距離が０となる確率から、衝突エントロピーを算出する第１算出ステップと、
前記衝突エントロピーに基づく漏洩情報量の上限から、平均最小エントロピーの下限値を、安全性指標として算出する第２算出ステップと、をコンピュータに実行させるための安全性評価プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、メモリに対するアクセスパターンの保護技術に関する。
【背景技術】
【０００２】
従来、プログラム実行時のメモリに対するアクセスパターンから、このプログラムに関する情報が漏えいすることが懸念されており、プログラム及び情報を保護する観点から、アクセスパターンを保護することが望まれている。
【０００３】
メモリに対するアクセスパターンの保護技術としては、Ｏｂｌｉｖｉｏｕｓ  ＲＡＭ（ＯＲＡＭ）が知られている（例えば、非特許文献１参照）。しかしながら、ＯＲＡＭは、メモリブロックのシャッフル等の処理によるオーバヘッドが膨大なため、実用的ではない。一方、少しの情報漏えいを許す代わりに、オーバヘッドを抑えた方式も提案されている（例えば、非特許文献２参照）。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Ｏ．  Ｇｏｌｄｒｅｉｃｈ  ａｎｄ  Ｒ．  Ｏｓｔｒｏｖｓｋｙ，  “Ｓｏｆｔｗａｒｅ  Ｐｒｏｔｅｃｔｉｏｎ  ａｎｄ  Ｓｉｍｕｌａｔｉｏｎ  ｏｎ  Ｏｂｌｉｖｉｏｕｓ  ＲＡＭｓ，”  Ｊ．  ＡＣＭ，  ｖｏｌ．４３，  ｎｏ．３，  ｐｐ．  ４３１−４７３，  １９９６．
【非特許文献２】Ｙｕｔｏ  Ｎａｋａｎｏ，  Ｃａｒｌｏｓ  Ｃｉｄ，  Ｓｈｉｎｓａｋｕ  Ｋｉｙｏｍｏｔｏ，  ａｎｄ  Ｙｕｔａｋａ  Ｍｉｙａｋｅ，  “Ｍｅｍｏｒｙ  Ａｃｃｅｓｓ  Ｐａｔｔｅｒｎ  Ｐｒｏｔｅｃｔｉｏｎ  ｆｏｒ  Ｒｅｓｏｕｒｃｅ−ｃｏｎｓｔｒａｉｎｅｄ  Ｄｅｖｉｃｅｓ，”  ＣＡＲＤＩＳ  ２０１２．
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、セキュリティレベルとコストとのバランスを調整可能なメモリアクセスパターン保護技術については、これらの方式間で比較可能、かつ、実用的に計算可能な安全性の評価指標がなかった。このため、コストを最適化する場合に、要求されるセキュリティレベルを満たしているかどうかの判断が難しかった。
【０００６】
本発明は、メモリアクセスパターン保護技術について、安全性を実用的に定量評価できる装置、方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明に係る安全性評価装置は、メモリへのアクセスパターンに対して、保護されたアクセスパターンの複数のサンプルを生成するサンプル生成部と、前記サンプル間の距離を算出し、当該距離の確率分布を取得する確率分布取得部と、前記距離が０となる確率から、衝突エントロピーを算出する第１算出部と、前記衝突エントロピーに基づく漏洩情報量の上限から、平均最小エントロピーの下限値を、安全性指標として算出する第２算出部と、を備える。
【０００８】
前記確率分布取得部は、前記サンプル間の編集距離のヒストグラムを、所定の確率分布関数で近似してもよい。
【０００９】
前記安全性評価装置は、アクセスパターンの保護技術における設計パラメータを変化させ、前記第２算出部により算出される前記安全性指標が指定値以上となる範囲を導出する範囲導出部を備えてもよい。
【００１０】
前記安全性評価装置は、前記範囲の中で、コストが最小となる設計パラメータを決定する決定部を備えてもよい。
【００１１】
本発明に係る安全性評価方法は、メモリへのアクセスパターンに対して、保護されたアクセスパターンの複数のサンプルを生成するサンプル生成ステップと、前記サンプル間の距離を算出し、当該距離の確率分布を取得する確率分布取得ステップと、前記距離が０となる確率から、衝突エントロピーを算出する第１算出ステップと、前記衝突エントロピーに基づく漏洩情報量の上限から、平均最小エントロピーの下限値を、安全性指標として算出する第２算出ステップと、をコンピュータが実行する。
【００１２】
本発明に係る安全性評価プログラムは、メモリへのアクセスパターンに対して、保護されたアクセスパターンの複数のサンプルを生成するサンプル生成ステップと、前記サンプル間の距離を算出し、当該距離の確率分布を取得する確率分布取得ステップと、前記距離が０となる確率から、衝突エントロピーを算出する第１算出ステップと、前記衝突エントロピーに基づく漏洩情報量の上限から、平均最小エントロピーの下限値を、安全性指標として算出する第２算出ステップと、をコンピュータに実行させるためのものである。
【発明の効果】
【００１３】
本発明によれば、メモリアクセスパターン保護技術の安全性を実用的に定量評価できる。
【図面の簡単な説明】
【００１４】
【図１】実施形態に係る安全性評価装置の機能構成を示す図である。
【図２】実施形態に係る衝突エントロピーの計算手順を示すフローチャートである。
【図３】実施形態に係るＯＲＡＭにおける設計パラメータの最適化手順を示すフローチャートである。
【発明を実施するための形態】
【００１５】
以下、本発明の実施形態の一例について説明する。
図１は、本実施形態に係る安全性評価装置１の機能構成を示す図である。
安全性評価装置１は、制御部１０及び記憶部２０の他、入出力デバイス及び通信インタフェース等を備える情報処理装置（コンピュータ）である。制御部１０（例えば、ＣＰＵ）は、記憶部２０に格納されたプログラムを読み込んで実行することにより、次の各部として機能する。
制御部１０は、サンプル生成部１１と、確率分布取得部１２と、第１算出部１３と、第２算出部１４と、範囲導出部１５と、決定部１６とを備える。
【００１６】
サンプル生成部１１は、メモリへのアクセスパターンに対して、ＯＲＡＭのアルゴリズムに従って、保護されたアクセスパターンの複数のサンプルを生成する。なお、サンプル生成部１１は、元のアクセスパターンをランダムに生成してもよいし、入力を受け付けてもよい。
【００１７】
確率分布取得部１２は、サンプル生成部１１により生成された複数のサンプルについて、相互の距離を算出し、距離の確率分布を取得する。
具体的には、確率分布取得部１２は、サンプル間の編集距離（例えば、ハミング距離）のヒストグラムを、所定の確率分布関数（例えば、二項分布）で近似することにより、確率分布を推定する。
【００１８】
第１算出部１３は、確率分布取得部１２により推定された確率分布のうち、距離が０となる、すなわち一致する確率から、衝突エントロピーを算出する。
第２算出部１４は、衝突エントロピーに基づいて漏洩情報量の上限を算出し、この漏洩情報量の上限に基づいて平均最小エントロピーの下限値を、安全性指標として算出する。
なお、第１算出部及び第２算出部による安全性指標の算出方法の詳細は後述する。
【００１９】
範囲導出部１５は、アクセスパターンの保護技術における設計パラメータを変化させ、サンプル生成部１１、確率分布取得部１２、第１算出部１３及び第２算出部１４により算出される安全性指標が指定値以上となる範囲を導出する。
決定部１６は、導出された範囲の中で、コストが最小となる設計パラメータを決定し、出力する。
なお、範囲導出部１５及び決定部１６による最適化方法の詳細は後述する。
【００２０】
ここで、安全性評価装置１による、メモリアクセスパターン保護技術の安全性評価方法を以下に詳述する。
【００２１】
本実施形態では、一般的な安全性評価指標の一つである平均最小エントロピーを用いて、メモリアクセスパターン保護技術の安全性を定義する。
しかしながら、平均最小エントロピーを実際に計算するためには、アクセスパターンの確率分布を計算する必要がある。確率分布は、その分布に偏りがあるほど計算が複雑となり理論的に導出することが困難になる。また、確率分布を実験的に算出する場合も、アクセスパターンの取りうる値の数が多ければ、指数オーダの膨大なサンプルが必要となり容易ではない。
【００２２】
そこで、本実施形態の安全性評価装置１は、より少ないサンプルから実験的に算出可能なメモリアクセスパターンの距離分布に基づいて、平均最小エントロピーを算出する。また、安全性評価装置１は、平均最小エントロピーが要求以上となる範囲で、メモリアクセスパターン保護技術のパラメータを調整し、コストを最適化する。
【００２３】
［メモリアクセスパターン］
プログラムＲがＮ個のデータブロックからなるメモリにｎ回アクセスする場合を考える。それぞれのアクセスＡは、データブロックのアドレスで定義され、アクセスパターンは、次式で表される。
（Ａ１，…，Ａｎ）
【００２４】
［メモリアクセスパターン保護技術］
メモリアクセスパターン保護技術であるＯＲＡＭの各方式は、アクセスパターン（Ａ１，…，Ａｎ）を、異なるアクセスパターン（Ｂ１，…，Ｂｑ）にマッピングするする。ここで、（Ａ１，…，Ａｎ）を元のアクセスパターン、（Ｂ１，…，Ｂｑ）を保護されたアクセスパターンと呼ぶ。
なお、ｎ回のアクセスからなる元のアクセスパターンは、ｑ（≧ｎ）回のアクセスからなる保護されたアクセスパターンに変換されている。
【００２５】
［メモリアクセスパターン保護技術の安全性］
元のアクセスパターンをＡｎ＝（Ａ１，…，Ａｎ）、これに対応する保護されたアクセスパターンをＢｑ＝（Ｂ１，…，Ｂｑ）とする。
このとき、安全性の評価指標である平均最小エントロピーＨ∞（Ａｎ｜Ｂｑ）が−ｌｏｇ（１／Ｎｎ）−ｌ以下のとき、このＯＲＡＭ方式は、ｌ−漏えい安全と定義する。
【００２６】
ここで、変数Ｂに対する変数Ａの平均最小エントロピー
Ｈ∞（Ａｎ｜Ｂｑ）＝−ｌｏｇＥｂｑ∈Ｂｑ（
ｍａｘａｑ∈ＡｎＰｒ［Ａｎ＝ａｎ｜Ｂｑ＝ｂｑ］）
は、ベイズの定理により、
Ｈ∞（Ａｎ｜Ｂｑ）＝−ｌｏｇΣｂｑ∈Ｂｑ（
ｍａｘａｎ∈ＡｎＰｒ［Ｂｑ＝ｂｑ｜Ａｎ＝ａｎ］Ｐｒ［Ａｎ＝ａｎ］）
と変形できる。
さらに、Ａｎが一様分布と仮定すると、Ａｎの要素はＮｎ個であるから、
Ｐｒ［Ａｎ＝ａｎ］＝１／Ｎｎ
となる。よって、下記の文献Ａにより、
Ｈ∞（Ａｎ｜Ｂｑ）≧−ｌｏｇ（１／Ｎｎ）−ｌｏｇ｜Ｂｑ｜＋Ｈ∞（Ａｎ，Ｂｑ）
が得られる。また、下記の文献Ｂにより、平均最小エントロピーＨ∞（Ａｎ，Ｂｑ）と衝突エントロピーＨ２（Ａｎ，Ｂｑ）とは、
Ｈ２（Ａｎ，Ｂｑ）≦２Ｈ∞（Ａｎ，Ｂｑ）
の関係が成り立つので、
Ｈ∞（Ａｎ｜Ｂｑ）≧−ｌｏｇ（１／Ｎｎ）
−ｌｏｇ｜Ｂｑ｜＋Ｈ２（Ａｎ，Ｂｑ）／２
となる。
【００２７】
文献Ａ：  Ｙ．  Ｄｏｄｉｓ，  Ｒ．  Ｏｓｔｒｏｖｓｋｙ，  Ｌ．  Ｒｅｙｚｉｎ，  ａｎｄ  Ａ．  Ｓｍｉｔｈ，  “Ｆｕｚｚｙ  ｅｘｔｒａｃｔｏｒｓ：  Ｈｏｗ  ｔｏ  ｇｅｎｅｒａｔｅ  ｓｔｒｏｎｇ  ｋｅｙｓ  ｆｒｏｍ  ｂｉｏｍｅｔｒｉｃｓ  ａｎｄ  ｏｔｈｅｒ  ｎｏｉｓｙ  ｄａｔａ，”  ＳＩＡＭ  Ｊｏｕｒｎａｌ  ｏｆ  Ｃｏｍｐｕｔｉｎｇ，  ｖｏｌ．  ３８，  ｎｏ．  １，  ｐｐ．  ９７−１３９，  ２００８．
文献Ｂ：  Ｙ．  Ｄｏｄｉｓ，  Ｔ．  Ｒｉｓｔｅｎｐａｒｔ，  ａｎｄ  Ｓ．  Ｖａｄｈａｎ，  “Ｒａｎｄｏｍｎｅｓｓ  ｃｏｎｄｅｎｓｅｒｓ  ｆｏｒ  ｅｆｆｉｃｉｅｎｔｌｙ  ｓａｍｐｌａｂｌｅ，  ｓｅｅｄ−ｄｅｐｅｎｄｅｎｔ  ｓｏｕｒｃｅｓ，”  ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ９ｔｈ  Ｔｈｅｏｒｙ  ｏｆ  Ｃｒｙｐｔｏｇｒａｐｈｙ  Ｃｏｎｆｅｒｅｎｃｅ  （ＴＣＣ  ２０１２），  ２０１２，  ｐｐ．  ６１８−６３５．
【００２８】
したがって、ＯＲＡＭ方式がｌ−漏えい安全のとき、Ｂｑの取りうる値の数を２ｔ、ＡｎとＢｑとの衝突エントロピーをＨ２（Ａｎ，Ｂｑ）とすると、漏えい情報量ｌの上限は、ｔ−Ｈ２（Ａｎ，Ｂｑ）／２で表される。
【００２９】
［漏えい情報量の上限値の計算方法］
安全性評価装置１は、漏えい情報量ｌの上限ｔ−Ｈ２（Ａｎ，Ｂｑ）／２について、ｔを理想的な値として計算する。
衝突エントロピーＨ２（Ａｎ，Ｂｑ）は、−ｌｏｇ（１／Ｎｎ）＋Ｈ２（Ｂｑ｜Ａｎ＝ａｎ）で表される。ただし、どのａｎについてもＨ２（Ｂｑ｜Ａｎ＝ａｎ）が同様であることを仮定する。
【００３０】
あるａｎが与えられたとき、Ｂｑの距離の確率分布をｐｄとすると、Ｈ２（Ｂｑ｜Ａｎ＝ａｎ）は、−ｌｏｇｐｄ（０）で表される。したがって、Ｈ２（Ｂｑ｜Ａｎ＝ａｎ）は、以下の手順で計算される。
【００３１】
図２は、本実施形態に係る衝突エントロピーの計算手順を示すフローチャートである。
ステップＳ１において、制御部１０は、元のアクセスパターンａｎを一つ用意する。
ステップＳ２において、制御部１０（サンプル生成部１１）は、元のアクセスパターンａｎを用いて、対応する複数の保護されたアクセスパターンｂｑのサンプルを生成する。
【００３２】
ステップＳ３において、制御部１０（確率分布取得部１２）は、保護されたアクセスパターンの距離ｄＢｑを編集距離で定義し、ステップＳ２で生成した複数の保護されたアクセスパターンから距離ｄＢｑのサンプルを取得する。そしで、制御部１０（確率分布取得部１２）は、距離ｄＢｑのサンプルから確率分布ｐｄを求める。
【００３３】
ステップＳ４において、制御部１０（第１算出部１３）は、距離ｄＢｑが０となる確率ｐｄ（０）から衝突エントロピーＨ２（Ｂｑ｜Ａｎ＝ａｎ）＝−ｌｏｇｐｄ（０）を算出する。
【００３４】
［コストの最適化］
メモリアクセスパターン保護技術であるＯＲＡＭでは、アクセスパターンを保護するために、ダミーデータを格納するための追加領域と、アクセス履歴を保管するための追加領域とが必要である。これらの領域が大きいほど安全性は向上するが、一方でメモリへアクセスする際の計算コストが増加する。
【００３５】
このため、メモリアクセスパターン保護技術のセキュリティ要件として、平均最小エントロピーＨ∞（Ａｎ｜Ｂｑ）をδ以上にすることが求められた場合、安全性評価装置１は、以下の手順でコストを最適化する。
【００３６】
図３は、本実施形態に係るＯＲＡＭにおける設計パラメータの最適化手順を示すフローチャートである。
ステップＳ１１において、制御部１０（範囲導出部１５）は、ＯＲＡＭにおいて設定されるダミーデータを格納するための追加領域と、アクセス履歴を保管するための追加領域との大きさを、それぞれ変化させながら、第２算出部１４により漏えい情報量ｌの上限値ｔ−Ｈ２（Ａｎ，Ｂｑ）／２を計算する。そして、制御部１０（範囲導出部１５）は、平均最小エントロピーＨ∞（Ａｎ｜Ｂｑ）がδ以上となる各追加領域の大きさの範囲を導出する。
【００３７】
ステップＳ１２において、制御部１０（決定部１６）は、ステップＳ１１で導出した範囲内で、コスト（例えば、追加領域の大きさ）が最小となるように、それぞれの追加領域の大きさを決定する。
【００３８】
本実施形態によれば、安全性評価装置１は、メモリアクセスパターン保護技術の安全性を、保護されたアクセスパターンから元のアクセスパターンを復元する困難さの下限を示す平均最小エントロピーで評価する。これにより、安全性評価装置１は、メモリアクセスパターン保護技術がセキュリティ要件である安全性を満たしているか否かを判定できる。また、安全性評価装置１は、統一された基準で安全性を定量評価することにより、複数の保護方式を容易に比較できる。
【００３９】
さらに、安全性評価装置１は、保護されたアクセスパターンと元のアクセスパターンとの衝突エントロピーを用いて平均最小エントロピーの下限値を計算する。このとき、衝突エントロピーは、保護されたアクセスパターンの距離分布から計算される。これにより、安全性評価装置１は、アクセスパターンの確率分布を用いる必要がなく、より少ないサンプルから実験的に平均最小エントロピーを計算できる。したがって、安全性評価装置１は、メモリアクセスパターン保護技術の安全性を実用的に定量評価できる。
【００４０】
安全性評価装置１は、セキュリティレベルとコストとのバランスを調整可能なメモリアクセスパターン保護技術において、あるセキュリティレベルの安全性が要求された場合、安全性指標である平均最小エントロピーの下限値が要求されたセキュリティレベル以上となるパラメータの範囲を抽出する。これにより、安全性評価装置１は、メモリアクセスパターン保護技術におけるパラメータを適切に設計するための情報を出力できる。
【００４１】
さらに、安全性評価装置１は、抽出されたパラメータの範囲の中で、コストを最小化するパラメータを選択する。これにより、安全性評価装置１は、セキュリティ要件を満たした上でコストを最適化できる。
【００４２】
以上、本発明の実施形態について説明したが、本発明は前述した実施形態に限るものではない。また、本実施形態に記載された効果は、本発明から生じる最も好適な効果を列挙したに過ぎず、本発明による効果は、本実施形態に記載されたものに限定されるものではない。
【００４３】
安全性評価装置１による安全性評価方法及びコスト最適化方法は、ソフトウェアにより実現される。ソフトウェアによって実現される場合には、このソフトウェアを構成するプログラムが、情報処理装置（コンピュータ）にインストールされる。また、これらのプログラムは、ＣＤ−ＲＯＭのようなリムーバブルメディアに記録されてユーザに配布されてもよいし、ネットワークを介してユーザのコンピュータにダウンロードされることにより配布されてもよい。さらに、これらのプログラムは、ダウンロードされることなくネットワークを介したＷｅｂサービスとしてユーザのコンピュータに提供されてもよい。
【符号の説明】
【００４４】
１  安全性評価装置
１０  制御部
１１  サンプル生成部
１２  確率分布取得部
１３  第１算出部
１４  第２算出部
１５  範囲導出部
１６  決定部
２０  記憶部
【図１】
2019003442.tif 000003
【図２】
2019003442.tif 000004
【図３】
2019003442.tif 000005