cafebabe.jp 日々のよしなしごとをのたまうブログ.

134月/110

バースマーク (Birthmark)

プログラムの実行に必要不可欠な情報を,プログラムの特徴として抽出し,プログラムを識別するための技術がこのバースマークです.主に盗用されたプログラムを発見するために用いられます.プログラムのどんな情報に注目するか,その情報をどう扱うかによってバースマークの種類が異なります.

バースマークは電子透かしと異なり,予め情報を埋め込んでおく必要はありません.そのため,新たに提案されたバースマークを過去に配布されたプログラムに対して適用することが可能である反面,バースマークが偶然に一致する可能性があるため,盗用であることを証明することは難しくなっています.もちろん,何十何百の種類のバースマークが偶然に一致することは稀であると考えられるので,多くの種類のバースマークを用いれば盗用であることを証明することもできると考えられます.

バースマークは以下のように定義されます.

p, qを与えられたプログラムとする.f(p)pからある方法fにより抽出された特徴の集合とする.このとき,以下の条件を満たすとき,f(p)pのバースマークであるという.

  • f(p)はプログラムpのみから得られる.
  • qpのコピーならば,f(p)=f(q)である.

また,バースマークは以下の性質を満たすこと望まれます.

保存性
pから任意の投下変換により得られたp\'に対してf(p)=f(p\')を満たす.
弁別性
同じ仕様を持つpqに対し,それらが全く独立に実装された場合,f(p) != f(q)となる.

バースマークは具体的には以下のものが提案されています.

静的バースマーク
変数初期値,継承関係,メソッド呼び出し系列,依存クラス,k-gram,...
動的バースマーク
API呼出系列,API呼出頻度,プログラムパス,実行系列の抽象化,...