From d97880b9e169bba692601b037dae9d94ac33570d Mon Sep 17 00:00:00 2001 From: tama3 Date: Wed, 7 Mar 2007 02:46:43 +0000 Subject: [PATCH] new feature: add k-gram based birthmark git-svn-id: svn+ssh://svn.sourceforge.jp/svnroot/stigmata/trunk@71 acee48c3-7b26-0410-bdac-b3d0e5314bbc --- .../stigmata/birthmarks/ASMBirthmarkExtractor.java | 1 + .../comparators/LogicalAndBirthmarkComparator.java | 3 + .../is/InheritanceStructureBirthmarkExtractor.java | 1 + .../naist/se/stigmata/birthmarks/kgram/KGram.java | 57 +++++++++++++ .../kgram/KGramBasedBirthmarkElement.java | 34 ++++++++ .../kgram/KGramBasedBirthmarkExtractVisitor.java | 68 +++++++++++++++ .../kgram/KGramBasedBirthmarkExtractor.java | 44 ++++++++++ .../kgram/KGramBasedBirthmarkService.java | 47 ++++++++++ .../kgram/OpcodeExtractionMethodVisitor.java | 99 ++++++++++++++++++++++ .../services/jp.naist.se.stigmata.spi.BirthmarkSpi | 1 + .../resources/resources/description.properties | 2 + src/main/resources/resources/description_ja.source | 2 + 12 files changed, 359 insertions(+) create mode 100755 src/main/java/jp/naist/se/stigmata/birthmarks/kgram/KGram.java create mode 100755 src/main/java/jp/naist/se/stigmata/birthmarks/kgram/KGramBasedBirthmarkElement.java create mode 100755 src/main/java/jp/naist/se/stigmata/birthmarks/kgram/KGramBasedBirthmarkExtractVisitor.java create mode 100755 src/main/java/jp/naist/se/stigmata/birthmarks/kgram/KGramBasedBirthmarkExtractor.java create mode 100755 src/main/java/jp/naist/se/stigmata/birthmarks/kgram/KGramBasedBirthmarkService.java create mode 100755 src/main/java/jp/naist/se/stigmata/birthmarks/kgram/OpcodeExtractionMethodVisitor.java diff --git a/src/main/java/jp/naist/se/stigmata/birthmarks/ASMBirthmarkExtractor.java b/src/main/java/jp/naist/se/stigmata/birthmarks/ASMBirthmarkExtractor.java index 18581f8..4824c1f 100755 --- a/src/main/java/jp/naist/se/stigmata/birthmarks/ASMBirthmarkExtractor.java +++ b/src/main/java/jp/naist/se/stigmata/birthmarks/ASMBirthmarkExtractor.java @@ -26,6 +26,7 @@ public abstract class ASMBirthmarkExtractor extends AbstractBirthmarkExtractor{ super(spi); } + @SuppressWarnings("deprecation") public ASMBirthmarkExtractor(){ super(); } diff --git a/src/main/java/jp/naist/se/stigmata/birthmarks/comparators/LogicalAndBirthmarkComparator.java b/src/main/java/jp/naist/se/stigmata/birthmarks/comparators/LogicalAndBirthmarkComparator.java index 8db1114..5bfc062 100755 --- a/src/main/java/jp/naist/se/stigmata/birthmarks/comparators/LogicalAndBirthmarkComparator.java +++ b/src/main/java/jp/naist/se/stigmata/birthmarks/comparators/LogicalAndBirthmarkComparator.java @@ -13,6 +13,9 @@ import jp.naist.se.stigmata.BirthmarkElement; import jp.naist.se.stigmata.spi.BirthmarkSpi; /** + * this comparator calculate following formula. + * let f(p) and f(q) be given birthmarks, then + * similarity of those birthmarks are defined by |f(p) and f(q)|/|f(p) or f(q)|. * * @author Haruaki TAMADA * @version $Revision: 20 $ $Date: 2007-01-17 11:06:01 +0900 (Wed, 17 Jan 2007) $ diff --git a/src/main/java/jp/naist/se/stigmata/birthmarks/is/InheritanceStructureBirthmarkExtractor.java b/src/main/java/jp/naist/se/stigmata/birthmarks/is/InheritanceStructureBirthmarkExtractor.java index cb526bc..38feccd 100755 --- a/src/main/java/jp/naist/se/stigmata/birthmarks/is/InheritanceStructureBirthmarkExtractor.java +++ b/src/main/java/jp/naist/se/stigmata/birthmarks/is/InheritanceStructureBirthmarkExtractor.java @@ -30,6 +30,7 @@ public class InheritanceStructureBirthmarkExtractor extends AbstractBirthmarkExt super(spi); } + @SuppressWarnings("deprecation") public InheritanceStructureBirthmarkExtractor(){ super(); } diff --git a/src/main/java/jp/naist/se/stigmata/birthmarks/kgram/KGram.java b/src/main/java/jp/naist/se/stigmata/birthmarks/kgram/KGram.java new file mode 100755 index 0000000..44a4dc3 --- /dev/null +++ b/src/main/java/jp/naist/se/stigmata/birthmarks/kgram/KGram.java @@ -0,0 +1,57 @@ +package jp.naist.se.stigmata.birthmarks.kgram; + +/* + * $Id$ + */ + +import java.io.Serializable; +import java.util.Arrays; + +/** + * + * @author Haruaki TAMADA + * @version $Revision$ $Date$ + */ +public class KGram implements Serializable{ + private static final long serialVersionUID = 273465874532523L; + private int[] values; + + public KGram(int kvalue){ + values = new int[kvalue]; + } + + public String toString(){ + StringBuffer buffer = new StringBuffer("{ "); + for(int i = 0; i < values.length; i++){ + if(i != 0) buffer.append(", "); + buffer.append(values[i]); + } + buffer.append(" }"); + return new String(buffer); + } + + public void set(int index, int value){ + if(index < 0 || index >= values.length){ + throw new ArrayIndexOutOfBoundsException("expected 0-" + values.length + ": " + index); + } + values[index] = value; + } + + public int get(int index){ + if(index < 0 || index >= values.length){ + throw new ArrayIndexOutOfBoundsException("expected 0-" + values.length + ": " + index); + } + return values[index]; + } + + public boolean equals(Object o){ + if(o instanceof KGram){ + return Arrays.equals(values, ((KGram)o).values); + } + return false; + } + + public int hashCode(){ + return Arrays.hashCode(values); + } +} diff --git a/src/main/java/jp/naist/se/stigmata/birthmarks/kgram/KGramBasedBirthmarkElement.java b/src/main/java/jp/naist/se/stigmata/birthmarks/kgram/KGramBasedBirthmarkElement.java new file mode 100755 index 0000000..00a1ca3 --- /dev/null +++ b/src/main/java/jp/naist/se/stigmata/birthmarks/kgram/KGramBasedBirthmarkElement.java @@ -0,0 +1,34 @@ +package jp.naist.se.stigmata.birthmarks.kgram; + +/* + * $Id$ + */ + +import jp.naist.se.stigmata.BirthmarkElement; + +/** + * + * @author Haruaki TAMADA + * @version $Revision$ $Date$ + */ +public class KGramBasedBirthmarkElement extends BirthmarkElement{ + private static final long serialVersionUID = 28546543857543634L; + + private KGram kgram; + + public KGramBasedBirthmarkElement(KGram kgram){ + super(kgram.toString()); + this.kgram = kgram; + } + + public boolean equals(Object o){ + return o instanceof KGramBasedBirthmarkElement && + kgram.equals(((KGramBasedBirthmarkElement)o).kgram); + } + + public int hashCode(){ + int v = kgram.hashCode(); + + return (v & 0xff << 24) | (v >> 8); + } +} diff --git a/src/main/java/jp/naist/se/stigmata/birthmarks/kgram/KGramBasedBirthmarkExtractVisitor.java b/src/main/java/jp/naist/se/stigmata/birthmarks/kgram/KGramBasedBirthmarkExtractVisitor.java new file mode 100755 index 0000000..628e579 --- /dev/null +++ b/src/main/java/jp/naist/se/stigmata/birthmarks/kgram/KGramBasedBirthmarkExtractVisitor.java @@ -0,0 +1,68 @@ +package jp.naist.se.stigmata.birthmarks.kgram; + +/* + * $Id: ConstantValueOfFieldVariableBirthmarkExtractVisitor.java 59 2007-03-03 03:42:06Z tama3 $ + */ + +import java.util.ArrayList; +import java.util.HashSet; +import java.util.List; +import java.util.Set; + +import jp.naist.se.stigmata.Birthmark; +import jp.naist.se.stigmata.BirthmarkContext; +import jp.naist.se.stigmata.birthmarks.BirthmarkExtractVisitor; + +import org.objectweb.asm.ClassVisitor; +import org.objectweb.asm.MethodVisitor; + +/** + * + * @author Haruaki TAMADA + * @version $Revision: 59 $ $Date: 2007-03-03 12:42:06 +0900 (Sat, 03 Mar 2007) $ + */ +public class KGramBasedBirthmarkExtractVisitor extends BirthmarkExtractVisitor{ + private Birthmark birthmark; + private int kvalue; + private List opcodes = new ArrayList(); + + public KGramBasedBirthmarkExtractVisitor(ClassVisitor visitor, Birthmark birthmark, BirthmarkContext context){ + super(visitor, context); + this.birthmark = birthmark; + } + + public int getKValue(){ + return kvalue; + } + + public void setKValue(int kvalue){ + this.kvalue = kvalue; + } + + public void visitEnd(){ + Set kgrams = new HashSet(); + if(opcodes.size() >= getKValue()){ + int kvalue = getKValue(); + int max = opcodes.size() - (kvalue - 1); + for(int i = 0; i < max; i++){ + KGram kgram = new KGram(kvalue); + for(int j = 0; j < kvalue; j++){ + kgram.set(j, opcodes.get(i + j)); + } + kgrams.add(kgram); + } + } + for(KGram kgram: kgrams){ + birthmark.addElement(new KGramBasedBirthmarkElement(kgram)); + } + } + + @Override + public MethodVisitor visitMethod(int arg0, String arg1, String arg2, String arg3, String[] arg4){ + MethodVisitor visitor = super.visitMethod(arg0, arg1, arg2, arg3, arg4); + MethodVisitor opcodeVisitor = new OpcodeExtractionMethodVisitor(visitor, opcodes); + + return opcodeVisitor; + } + +} diff --git a/src/main/java/jp/naist/se/stigmata/birthmarks/kgram/KGramBasedBirthmarkExtractor.java b/src/main/java/jp/naist/se/stigmata/birthmarks/kgram/KGramBasedBirthmarkExtractor.java new file mode 100755 index 0000000..f2d8a2e --- /dev/null +++ b/src/main/java/jp/naist/se/stigmata/birthmarks/kgram/KGramBasedBirthmarkExtractor.java @@ -0,0 +1,44 @@ +package jp.naist.se.stigmata.birthmarks.kgram; + +/* + * $Id: SequentialMethodCallBirthmarkExtractor.java 66 2007-03-03 15:11:35Z tama3 $ + */ + +import jp.naist.se.stigmata.Birthmark; +import jp.naist.se.stigmata.BirthmarkContext; +import jp.naist.se.stigmata.birthmarks.ASMBirthmarkExtractor; +import jp.naist.se.stigmata.birthmarks.BirthmarkExtractVisitor; +import jp.naist.se.stigmata.spi.BirthmarkSpi; + +import org.objectweb.asm.ClassWriter; + +/** + * @author Haruaki TAMADA + * @version $Revision: 66 $ $Date: 2007-03-04 00:11:35 +0900 (Sun, 04 Mar 2007) $ + */ +public class KGramBasedBirthmarkExtractor extends ASMBirthmarkExtractor{ + private int kvalue = 4; + + public KGramBasedBirthmarkExtractor(BirthmarkSpi spi){ + super(spi); + } + + public KGramBasedBirthmarkExtractor(){ + super(); + } + + public void setKValue(int kvalue){ + this.kvalue = kvalue; + } + + public int getKValue(){ + return kvalue; + } + + @Override + public BirthmarkExtractVisitor createExtractVisitor(ClassWriter writer, Birthmark birthmark, BirthmarkContext context){ + KGramBasedBirthmarkExtractVisitor extractor = new KGramBasedBirthmarkExtractVisitor(writer, birthmark, context); + extractor.setKValue(getKValue()); + return extractor; + } +} diff --git a/src/main/java/jp/naist/se/stigmata/birthmarks/kgram/KGramBasedBirthmarkService.java b/src/main/java/jp/naist/se/stigmata/birthmarks/kgram/KGramBasedBirthmarkService.java new file mode 100755 index 0000000..047787f --- /dev/null +++ b/src/main/java/jp/naist/se/stigmata/birthmarks/kgram/KGramBasedBirthmarkService.java @@ -0,0 +1,47 @@ +package jp.naist.se.stigmata.birthmarks.kgram; + +/* + * $Id: ConstantValueOfFieldVariableBirthmarkService.java 59 2007-03-03 03:42:06Z tama3 $ + */ + +import jp.naist.se.stigmata.BirthmarkComparator; +import jp.naist.se.stigmata.BirthmarkExtractor; +import jp.naist.se.stigmata.birthmarks.AbstractBirthmarkService; +import jp.naist.se.stigmata.birthmarks.comparators.LogicalAndBirthmarkComparator; +import jp.naist.se.stigmata.spi.BirthmarkSpi; + +/** + * + * + * + * @author Haruaki TAMADA + * @version $Revision: 59 $ $Date: 2007-03-03 12:42:06 +0900 (Sat, 03 Mar 2007) $ + */ +public class KGramBasedBirthmarkService extends AbstractBirthmarkService implements BirthmarkSpi{ + private BirthmarkComparator comparator = new LogicalAndBirthmarkComparator(this); + private BirthmarkExtractor extractor = new KGramBasedBirthmarkExtractor(this); + + public String getType(){ + return "kgram"; + } + + public String getDefaultDescription(){ + return "k-gram based birthmark."; + } + + public BirthmarkExtractor getExtractor(){ + return extractor; + } + + public BirthmarkComparator getComparator(){ + return comparator; + } + + public boolean isExpert(){ + return false; + } + + public boolean isUserDefined(){ + return false; + } +} diff --git a/src/main/java/jp/naist/se/stigmata/birthmarks/kgram/OpcodeExtractionMethodVisitor.java b/src/main/java/jp/naist/se/stigmata/birthmarks/kgram/OpcodeExtractionMethodVisitor.java new file mode 100755 index 0000000..adcf092 --- /dev/null +++ b/src/main/java/jp/naist/se/stigmata/birthmarks/kgram/OpcodeExtractionMethodVisitor.java @@ -0,0 +1,99 @@ +package jp.naist.se.stigmata.birthmarks.kgram; + +/* + * $Id$ + */ + +import java.util.List; + +import org.objectweb.asm.Label; +import org.objectweb.asm.MethodAdapter; +import org.objectweb.asm.MethodVisitor; +import org.objectweb.asm.Opcodes; + +/** + * + * @author Haruaki TAMADA + * @version $Revision$ $Date$ + */ +public class OpcodeExtractionMethodVisitor extends MethodAdapter{ + private List opcodes; + + public OpcodeExtractionMethodVisitor(MethodVisitor visitor, List opcodes){ + super(visitor); + this.opcodes = opcodes; + } + + @Override + public void visitFieldInsn(int opcode, String owner, String name, String desc){ + opcodes.add(opcode); + super.visitFieldInsn(opcode, owner, name, desc); + } + + @Override + public void visitIincInsn(int var, int increment){ + opcodes.add(Opcodes.IINC); + super.visitIincInsn(var, increment); + } + + @Override + public void visitInsn(int opcode){ + opcodes.add(opcode); + super.visitInsn(opcode); + } + + @Override + public void visitIntInsn(int opcode, int operand){ + opcodes.add(opcode); + super.visitIntInsn(opcode, operand); + } + + @Override + public void visitJumpInsn(int opcode, Label label){ + opcodes.add(opcode); + super.visitJumpInsn(opcode, label); + } + + @Override + public void visitLdcInsn(Object value){ + opcodes.add(Opcodes.LDC); + super.visitLdcInsn(value); + } + + @Override + public void visitLookupSwitchInsn(Label defaultHandle, int[] keys, Label[] labels){ + opcodes.add(Opcodes.LOOKUPSWITCH); + super.visitLookupSwitchInsn(defaultHandle, keys, labels); + } + + @Override + public void visitMethodInsn(int opcode, String owner, String name, String desc){ + opcodes.add(opcode); + super.visitMethodInsn(opcode, owner, name, desc); + } + + @Override + public void visitMultiANewArrayInsn(String desc, int dims){ + opcodes.add(Opcodes.MULTIANEWARRAY); + super.visitMultiANewArrayInsn(desc, dims); + } + + @Override + public void visitTableSwitchInsn(int min, int max, Label defaultLabel, Label[] labels){ + opcodes.add(Opcodes.TABLESWITCH); + super.visitTableSwitchInsn(min, max, defaultLabel, labels); + } + + @Override + public void visitTypeInsn(int opcode, String desc){ + opcodes.add(opcode); + super.visitTypeInsn(opcode, desc); + } + + @Override + public void visitVarInsn(int opcode, int var){ + opcodes.add(opcode); + super.visitVarInsn(opcode, var); + } + +} diff --git a/src/main/resources/META-INF/services/jp.naist.se.stigmata.spi.BirthmarkSpi b/src/main/resources/META-INF/services/jp.naist.se.stigmata.spi.BirthmarkSpi index 072a748..1a001cb 100755 --- a/src/main/resources/META-INF/services/jp.naist.se.stigmata.spi.BirthmarkSpi +++ b/src/main/resources/META-INF/services/jp.naist.se.stigmata.spi.BirthmarkSpi @@ -2,3 +2,4 @@ jp.naist.se.stigmata.birthmarks.smc.SequentialMethodCallBirthmarkService jp.naist.se.stigmata.birthmarks.cvfv.ConstantValueOfFieldVariableBirthmarkService jp.naist.se.stigmata.birthmarks.is.InheritanceStructureBirthmarkService jp.naist.se.stigmata.birthmarks.uc.UsedClassesBirthmarkService +jp.naist.se.stigmata.birthmarks.kgram.KGramBasedBirthmarkService diff --git a/src/main/resources/resources/description.properties b/src/main/resources/resources/description.properties index 0ed3e3c..f28cf5f 100644 --- a/src/main/resources/resources/description.properties +++ b/src/main/resources/resources/description.properties @@ -6,3 +6,5 @@ birthmark.uc.display.type=Used Classes birthmark.uc.description=Set of used classes in target class. birthmark.is.display.type=Inheritance Structure birthmark.is.description=Inheritance sequence to root class and user classes is replaced to . +birthmark.kgram.display.type=k-gram +birthmark.kgram.description=Set of extracted k-gram from opcode sequence. diff --git a/src/main/resources/resources/description_ja.source b/src/main/resources/resources/description_ja.source index f217d43..ae760e3 100644 --- a/src/main/resources/resources/description_ja.source +++ b/src/main/resources/resources/description_ja.source @@ -6,3 +6,5 @@ birthmark.uc.display.type= birthmark.uc.description=ƒNƒ‰ƒX‚ªˆË‘¶‚·‚鑼‚ÌŠù’m‚̃Nƒ‰ƒX‚̏W‡ birthmark.is.display.type=Œp³ŠÖŒW birthmark.is.description=Œp³ŠÖŒW‚ðƒ‹[ƒg‚Ü‚Å’H‚Á‚Ä“¾‚ç‚ê‚éƒNƒ‰ƒX‚ÌŒn—ñ +birthmark.kgram.display.type=k-gram +birthmark.kgram.description=opcode‚Ì•À‚Ñ‚©‚çk-gram‚ðŽæ‚èo‚µ‚½W‡ -- 2.11.0