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

k-gramバースマーク

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

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

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

• おなかと
• なかとせ
• かとせな
• とせなか
• せなかが
• なかがく
• かがくっ
• がくっつ
• くっつく
• っつくぞ

• Ginger Myles, Christian Collberg, "K-gram based software birthmarks," In Proc. of the 2005 ACM symposium on Applied computing, 2005.