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

204月/110

Stigmata

StigmataはJavaの静的バースマークを統一的に扱うためのツールで http://stigmata.sourceforge.jp/ で公開されている.

バースマークは本ブログでも何度か取り上げているが,プログラムの実行に必要不可欠な部分をプログラムの特徴として抽出し,得られた情報を比較することでプログラムの類似性を計測する技術のことである.主に大量のプログラムの中から,盗用されたプログラムを見つけ出すために用いられる.そして,どのような特徴に着目するかにより,様々な種類のバースマークを抽出することができる.

電子透かしと異なり,実行に不可欠な情報を扱うため,予め情報を埋め込んでおく必要がなく,また,複数のバースマークを同時に使うことができるため,非常に簡易に用いることができる.

http://cafebabe.jp/categories/works/birthmarks

このようなバースマーク(のうち,静的解析により得られる静的バースマーク)をStigmataは統一的に扱おうとしており,現在,7種類の静的バースマークをクラスファイルから直接抽出することができる.そして,抽出されたバースマークを総当たりで比較することや,比較結果のフィルタリングすることが可能である.

 
184月/110

自然言語を対象としたバースマーク

あらゆる文章にもその文章の主題や著者特有の言い回しなど,何らかの特徴が出るはずである.そのため,自然言語で書かれた文章からでもバースマークが抽出できるはずである.Yangらはこの考えのもと,自然言語を対象としたバースマークを提案した.

文章は数多くの単語で構成され,それらの単語は名詞や動詞などに分類することが可能である.Yangらはそれら単語の品詞ごとの出現頻度に着目したバースマークを提案している.

ある文章中に存在する全ての名詞のうち,特定の辞書に載っている単語のみを取り出し,その出現頻度を名詞バースマークと定義している.同様に動詞バースマーク形容詞バースマーク副詞バースマークを提案している.

 
174月/110

k-gramバースマーク

静的バースマークの一つで G. Myles らによって提案された.

クラスファイルから opcode (getfield, invokespecial, invokevirtual, etc.) を取り出して得られたシーケンスから k-gram を抽出する.得られた k-gram の集合から重複したものを取り除いた集合が k-gram バースマークである.

k-gramとは n-gram とも言われ,シーケンスからk個の連続した要素を取り出して,それを一つの新たな要素とする集合のことを指す.例えば「おなかとせなかがくっつくぞ」から4gramを取り出すと,以下の要素を持つ集合が得られる.

  • おなかと
  • なかとせ
  • かとせな
  • とせなか
  • せなかが
  • なかがく
  • かがくっ
  • がくっつ
  • くっつく
  • っつくぞ
 
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呼出頻度,プログラムパス,実行系列の抽象化,...