-**/target
+*~
+.DS_Store
+._*
+target
+.classpath
+.settings
+.project
+.djunitplugin
+++ /dev/null
-<?xml version="1.0" encoding="UTF-8"?>\r
-<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">\r
- <modelVersion>4.0.0</modelVersion>\r
- <parent>\r
- <artifactId>plugins</artifactId>\r
- <groupId>jp.sourceforge.stigmata</groupId>\r
- <version>1.0</version>\r
- </parent>\r
- <groupId>jp.sourceforge.stigmata.plugins</groupId>\r
- <artifactId>cflib</artifactId>\r
- <version>1.0.0</version>\r
- <name>cflib</name>\r
- <url>http://stigmata.sourceforge.jp/stigmata/plugins/cflib/</url>\r
-\r
- <dependencies>\r
- <dependency>\r
- <groupId>jp.sourceforge</groupId>\r
- <artifactId>stigmata</artifactId>\r
- <version>2.0.0</version>\r
- <scope>provided</scope>\r
- </dependency>\r
- <dependency>\r
- <groupId>asm</groupId>\r
- <artifactId>asm-all</artifactId>\r
- <version>3.1</version>\r
- <scope>compile</scope>\r
- </dependency>\r
- <dependency>\r
- <groupId>junit</groupId>\r
- <artifactId>junit</artifactId>\r
- <version>4.8.1</version>\r
- <scope>test</scope>\r
- </dependency>\r
- </dependencies>\r
-\r
- <build>\r
- <plugins>\r
- <plugin>\r
- <artifactId>maven-release-plugin</artifactId>\r
- <configuration>\r
- <tagBase>svn+ssh://tama3@svn.sourceforge.jp/svnroot/stigmata/plugins/trunk/cflib/</tagBase>\r
- </configuration>\r
- </plugin>\r
-\r
- <plugin>\r
- <groupId>org.apache.maven.plugins</groupId>\r
- <artifactId>maven-dependency-plugin</artifactId>\r
- <executions>\r
- <execution>\r
- <id>copy-dependencies</id>\r
- <phase>compile</phase>\r
- <goals>\r
- <goal>copy-dependencies</goal>\r
- </goals>\r
- <configuration>\r
- <outputDirectory>${project.build.directory}</outputDirectory>\r
- <includeScope>runtime</includeScope>\r
- </configuration>\r
- </execution>\r
- </executions>\r
- </plugin>\r
- </plugins>\r
- </build>\r
-</project>\r
+++ /dev/null
-package jp.sourceforge.stigmata.birthmarks;\r
-\r
-import java.util.ArrayList;\r
-import java.util.Collections;\r
-import java.util.HashSet;\r
-import java.util.Iterator;\r
-import java.util.List;\r
-import java.util.Set;\r
-\r
-import org.objectweb.asm.Label;\r
-import org.objectweb.asm.Opcodes;\r
-import org.objectweb.asm.tree.AbstractInsnNode;\r
-import org.objectweb.asm.tree.InsnNode;\r
-\r
-/**\r
- * 基本ブロックを表すクラス.\r
- * \r
- * @author tamada\r
- */\r
-public class BasicBlock {\r
- private Set<BasicBlock> nexts = new HashSet<BasicBlock>();\r
- private List<Opcode> opcodes = new ArrayList<Opcode>();\r
- private Set<BasicBlock> prevs = new HashSet<BasicBlock>();\r
- Set<Label> exceptionFlows = new HashSet<Label>();\r
-\r
- BasicBlock(){\r
- }\r
-\r
- public BasicBlock(InsnNode[] nodeArray){\r
- for(InsnNode node: nodeArray){\r
- addNode(node);\r
- }\r
- }\r
-\r
- void addNode(AbstractInsnNode node){\r
- OpcodeManager manager = OpcodeManager.getInstance();\r
- Opcode opcode = manager.getOpcode(node);\r
- if(opcode != null){\r
- addNode(opcode);\r
- }\r
- }\r
-\r
- void addNode(Opcode opcode){\r
- opcodes.add(opcode);\r
- }\r
-\r
- public Opcode getOpcode(int index){\r
- return opcodes.get(index);\r
- }\r
-\r
- public int getSize(){\r
- return opcodes.size();\r
- }\r
-\r
- public Label[] getTargets(){\r
- Set<Label> targets = new HashSet<Label>();\r
- for(Opcode opcode: opcodes){\r
- if(opcode.getCategory() != Opcode.Category.TARGETER){\r
- Label[] labels = opcode.getLabels();\r
- for(Label label: labels){\r
- targets.add(label);\r
- }\r
- }\r
- }\r
- for(Label label: exceptionFlows){\r
- targets.add(label);\r
- }\r
-\r
- return targets.toArray(new Label[targets.size()]);\r
- }\r
-\r
- public boolean hasLabel(Label label){\r
- boolean flag = false;\r
- for(Opcode opcode: opcodes){\r
- if(flag || opcode.hasLabel(label)){\r
- flag = true;\r
- }\r
- }\r
- return flag;\r
- }\r
-\r
- public boolean isEmpty(){\r
- return opcodes.size() == 0;\r
- }\r
-\r
- public Iterator<BasicBlock> nextIterator(){\r
- return Collections.unmodifiableSet(nexts).iterator();\r
- }\r
-\r
- public Iterator<BasicBlock> previousIterator(){\r
- return Collections.unmodifiableSet(prevs).iterator();\r
- }\r
-\r
- public void setNext(BasicBlock block){\r
- block.prevs.add(this);\r
- nexts.add(block);\r
- }\r
-\r
- public void setPrev(BasicBlock block){\r
- block.nexts.add(this);\r
- prevs.add(block);\r
- }\r
-\r
- public String toString(){\r
- StringBuilder sb = new StringBuilder("---- block ----");\r
- String ln = System.getProperty("line.separator");\r
- for(Opcode opcode: opcodes){\r
- sb.append(ln).append(opcode);\r
- }\r
- sb.append(ln).append("Targeter: ");\r
- for(Label label: getTargets()){\r
- sb.append(label).append(", ");\r
- }\r
- return new String(sb);\r
- }\r
-\r
- public boolean isFlowNext(){\r
- Opcode opcode = getOpcode(getSize() - 1);\r
- int op = opcode.getOpcode();\r
-\r
- return op != Opcodes.GOTO && op != Opcodes.RETURN\r
- && op != Opcodes.RET && op != Opcodes.ATHROW;\r
- }\r
-}\r
+++ /dev/null
-package jp.sourceforge.stigmata.birthmarks;
-
-/*
- * $Id$
- */
-
-import java.util.List;
-
-import jp.sourceforge.stigmata.BirthmarkContext;
-import jp.sourceforge.stigmata.BirthmarkElement;
-
-/**
- *
- *
- * @author tamada
- * @version $Revision$
- */
-public interface BirthmarkElementBuilder {
- public BirthmarkElement[] buildElements(List<Opcode> opcodes, BirthmarkContext context);
-}
-
+++ /dev/null
-package jp.sourceforge.stigmata.birthmarks;\r
-\r
-import java.util.ArrayList;\r
-import java.util.HashSet;\r
-import java.util.Iterator;\r
-import java.util.List;\r
-import java.util.Set;\r
-\r
-import org.objectweb.asm.Label;\r
-import org.objectweb.asm.Opcodes;\r
-import org.objectweb.asm.tree.AbstractInsnNode;\r
-import org.objectweb.asm.tree.JumpInsnNode;\r
-import org.objectweb.asm.tree.LabelNode;\r
-import org.objectweb.asm.tree.LookupSwitchInsnNode;\r
-import org.objectweb.asm.tree.MethodNode;\r
-import org.objectweb.asm.tree.TableSwitchInsnNode;\r
-import org.objectweb.asm.tree.TryCatchBlockNode;\r
-\r
-/**\r
- * コントロールフローを表すクラス.\r
- * @author tamada\r
- */\r
-public class ControlFlowGraph {\r
- private BasicBlock[] blocks;\r
- private boolean includeException;\r
- private MethodNode method;\r
- private String name;\r
-\r
- public ControlFlowGraph(String name, MethodNode node){\r
- this(name, node, false);\r
- }\r
-\r
- public ControlFlowGraph(String name, MethodNode node, boolean includeException){\r
- this.includeException = includeException;\r
- this.name = name;\r
- this.method = node;\r
- parse(method);\r
- }\r
-\r
- private void buildExceptionFlow(AbstractInsnNode inst, Set<Label> exceptionFlows, TryCatchBlockNode[] tryCatches){\r
- if(inst.getType() == AbstractInsnNode.LABEL){\r
- Label label = ((LabelNode)inst).getLabel();\r
-\r
- for(TryCatchBlockNode node: tryCatches){\r
- if(node.start.getLabel() == label){\r
- exceptionFlows.add(node.handler.getLabel());\r
- }\r
- else if(node.end.getLabel() == label){\r
- exceptionFlows.remove(node.handler.getLabel());\r
- }\r
- }\r
- }\r
- }\r
-\r
- /**\r
- * TryCatchブロックの一覧を返します.\r
- * Try Catchブロックが含まれていない場合や,\r
- * {@link isIncludingExceptionFlow}がfalseを返す場合は長さ0の配列を返します.\r
- * @param node\r
- * @return\r
- */\r
- private TryCatchBlockNode[] buildTryCatchBlockNode(MethodNode node){\r
- TryCatchBlockNode[] nodes = new TryCatchBlockNode[0];\r
- if(isIncludingExceptionFlow()){\r
- nodes = new TryCatchBlockNode[node.tryCatchBlocks.size()];\r
- for(int i = 0; i < nodes.length; i++){\r
- nodes[i] = (TryCatchBlockNode)node.tryCatchBlocks.get(i);\r
- }\r
- }\r
- return nodes;\r
- }\r
-\r
- private Set<LabelNode> collectLabels(MethodNode node){\r
- Set<LabelNode> jumpTarget = new HashSet<LabelNode>();\r
- int size = node.instructions.size();\r
- for(int i = 0; i < size; i++){\r
- AbstractInsnNode inst = node.instructions.get(i);\r
- switch(inst.getType()){\r
- case AbstractInsnNode.JUMP_INSN:\r
- {\r
- JumpInsnNode jump = (JumpInsnNode)inst;\r
- jumpTarget.add(jump.label);\r
- break;\r
- }\r
- case AbstractInsnNode.LOOKUPSWITCH_INSN:\r
- {\r
- LookupSwitchInsnNode lookup = (LookupSwitchInsnNode)inst;\r
- jumpTarget.add(lookup.dflt);\r
- for(Object label: lookup.labels){\r
- jumpTarget.add((LabelNode)label);\r
- }\r
- break;\r
- }\r
- case AbstractInsnNode.TABLESWITCH_INSN:\r
- {\r
- TableSwitchInsnNode lookup = (TableSwitchInsnNode)inst;\r
- jumpTarget.add(lookup.dflt);\r
- for(Object label: lookup.labels){\r
- jumpTarget.add((LabelNode)label);\r
- }\r
- break;\r
- }\r
- }\r
- }\r
- if(isIncludingExceptionFlow()){\r
- for(Object object: node.tryCatchBlocks){\r
- jumpTarget.add(((TryCatchBlockNode)object).handler);\r
- }\r
- }\r
- return jumpTarget;\r
- }\r
-\r
- public int getBasicBlockSize(){\r
- return blocks.length;\r
- }\r
-\r
- public int[][] getGraphMatrix(){\r
- int[][] matrix = new int[blocks.length][blocks.length];\r
-\r
- for(int i = 0; i < blocks.length; i++){\r
- for(int j = 0; j < blocks.length; j++){\r
- int nextValue = 0;\r
- for(Iterator<BasicBlock> iter = blocks[i].nextIterator(); iter.hasNext(); ){\r
- BasicBlock nextBlock = iter.next();\r
- if(nextBlock == blocks[j]){\r
- nextValue = 1;\r
- break;\r
- }\r
- }\r
- matrix[i][j] = nextValue;\r
- }\r
- }\r
-\r
- return matrix;\r
- }\r
-\r
- public String getName(){\r
- return name;\r
- }\r
-\r
- public boolean isIncludingExceptionFlow(){\r
- return includeException;\r
- }\r
-\r
- private BasicBlock[] joinBasicBlocks(BasicBlock[] blocks){\r
- for(int i = 0; i < blocks.length; i++){\r
- Label[] labels = blocks[i].getTargets();\r
- for(int j = 0; j < labels.length; j++){\r
- for(int k = 0; k < blocks.length; k++){\r
- if(i != k && blocks[k].hasLabel(labels[j])){\r
- blocks[i].setNext(blocks[k]);\r
- break;\r
- }\r
- }\r
- }\r
- if((i + 1) < blocks.length && blocks[i].isFlowNext()){\r
- blocks[i].setNext(blocks[i + 1]);\r
- }\r
- }\r
-\r
- return blocks;\r
- }\r
-\r
- private void parse(MethodNode node){\r
- Set<LabelNode> jumpTarget = collectLabels(node);\r
- BasicBlock[] blocks = separateBasicBlock(node, jumpTarget);\r
- this.blocks = joinBasicBlocks(blocks);\r
- }\r
-\r
- private BasicBlock[] separateBasicBlock(MethodNode node, Set<LabelNode> jumpTarget){\r
- int size = node.instructions.size();\r
-\r
- List<BasicBlock> blockList = new ArrayList<BasicBlock>();\r
- Set<Label> exceptionFlows = new HashSet<Label>();\r
- TryCatchBlockNode[] tryCatchBlocks = buildTryCatchBlockNode(node);\r
-\r
- BasicBlock block = new BasicBlock();\r
- for(int i = 0; i < size; i++){\r
- AbstractInsnNode inst = node.instructions.get(i);\r
- block.exceptionFlows.addAll(exceptionFlows);\r
-\r
- if(jumpTarget.contains(inst)){\r
- if(!block.isEmpty()){\r
- blockList.add(block);\r
- block = new BasicBlock();\r
- block.exceptionFlows.addAll(exceptionFlows);\r
- }\r
- }\r
- block.addNode(inst);\r
- buildExceptionFlow(inst, exceptionFlows, tryCatchBlocks);\r
- if(inst.getType() == AbstractInsnNode.JUMP_INSN\r
- || inst.getType() == AbstractInsnNode.TABLESWITCH_INSN\r
- || inst.getType() == AbstractInsnNode.LOOKUPSWITCH_INSN\r
- || inst.getOpcode() == Opcodes.RETURN\r
- || inst.getOpcode() == Opcodes.ATHROW\r
- || inst.getOpcode() == Opcodes.RET){\r
- if(!block.isEmpty()){\r
- blockList.add(block);\r
- BasicBlock block2 = new BasicBlock();\r
- if(inst.getOpcode() != Opcodes.GOTO && inst.getOpcode() != Opcodes.JSR){\r
- block2.setPrev(block);\r
- }\r
- block = block2;\r
- block.exceptionFlows.addAll(exceptionFlows);\r
- }\r
- }\r
- }\r
- if(!block.isEmpty()){\r
- blockList.add(block);\r
- }\r
- return blockList.toArray(new BasicBlock[blockList.size()]);\r
- }\r
-\r
- public void setIncludingExceptionFlow(boolean includeException){\r
- boolean oldvalue = this.includeException;\r
- this.includeException = includeException;\r
- if(oldvalue != includeException){\r
- parse(method);\r
- }\r
- }\r
-}\r
+++ /dev/null
-package jp.sourceforge.stigmata.birthmarks;
-
-import java.util.Iterator;
-import java.util.LinkedHashMap;
-import java.util.Map;
-
-import jp.sourceforge.stigmata.Birthmark;
-import jp.sourceforge.stigmata.BirthmarkContext;
-
-import org.objectweb.asm.ClassVisitor;
-import org.objectweb.asm.MethodVisitor;
-import org.objectweb.asm.tree.MethodNode;
-
-/**
- *
- *
- * @author tamada
- */
-public class ControlFlowGraphExtractVisitor extends BirthmarkExtractVisitor{
- private Map<String, MethodNode> opcodesMap = new LinkedHashMap<String, MethodNode>();
-
- public ControlFlowGraphExtractVisitor(ClassVisitor visitor, Birthmark birthmark, BirthmarkContext context){
- super(visitor, birthmark, context);
- }
-
- /**
- * テストのためのコンストラクタ.
- * @param visitor
- */
- ControlFlowGraphExtractVisitor(ClassVisitor visitor){
- super(visitor, null, null);
- }
-
- public Iterator<String> getMethodNames(){
- return opcodesMap.keySet().iterator();
- }
-
- public ControlFlowGraph getGraph(String name){
- return buildControlFlow(name, opcodesMap.get(name));
- }
-
- @Override
- public MethodVisitor visitMethod(int access, String name, String descriptor, String signature, String[] exceptions){
- MethodNode node = new MethodNode(access, name, descriptor, signature, exceptions);
-
- opcodesMap.put(name + descriptor, node);
-
- return node;
- }
-
- private ControlFlowGraph buildControlFlow(String methodName, MethodNode node){
- return new ControlFlowGraph(methodName, node);
- }
-}
+++ /dev/null
-package jp.sourceforge.stigmata.birthmarks;
-
-/*
- * $Id$
- */
-
-import org.objectweb.asm.Label;
-
-/**
- *
- * @author Haruaki Tamada
- * @version $Revision$
- */
-public class LabelOpcode extends Opcode{
- private static final long serialVersionUID = -346783431316464L;
-
- public LabelOpcode(Label label){
- super(-1, "targeter", 0, 0, Category.TARGETER);
- super.addLabel(label);
- }
-
- @Override
- public final void addLabel(Label label){
- throw new NoSuchMethodError("illegal method call");
- }
-
- @Override
- public final void setLabels(Label[] label){
- throw new NoSuchMethodError("illegal method call");
- }
-
- public Label getLabel(){
- return getLabel(0);
- }
-}
+++ /dev/null
-package jp.sourceforge.stigmata.birthmarks;
-
-import java.io.Serializable;
-import java.util.ArrayList;
-import java.util.Collections;
-import java.util.Iterator;
-import java.util.List;
-
-import org.objectweb.asm.Label;
-
-/**
- *
- * @author Haruaki Tamada
- */
-public class Opcode implements Serializable, Iterable<Label>{
- private static final long serialVersionUID = -2349834745416345564L;
-
- public static enum Category{
- NORMAL, BRANCH, OBJECT, INVOKE, TARGETER,
- };
- private int opcode;
- private String name;
- private int argumentCount;
- private int act;
- private Category category;
- private List<Label> labels = new ArrayList<Label>();
-
- public Opcode(Opcode opcode){
- this(opcode.getOpcode(), opcode.getName(), opcode.getArgumentCount(), opcode.getAct(), opcode.getCategory());
- }
-
- public Opcode(int opcode, String name, int argumentCount, int act, String category){
- this(opcode, name, argumentCount, act, Category.valueOf(category));
- }
-
- public Opcode(int opcode, String name, int argumentCount, int act, Category category){
- this.opcode = opcode;
- this.name = name;
- this.argumentCount = argumentCount;
- this.act = act;
- this.category = category;
- }
-
- public final int getOpcode(){
- return opcode;
- }
-
- public final String getName(){
- return name;
- }
-
- public int getArgumentCount(){
- return argumentCount;
- }
-
- public void addLabel(Label label){
- if(label == null){
- throw new NullPointerException();
- }
- if(!(category == Category.TARGETER && labels.size() == 0)
- && category != Category.BRANCH){
- throw new IllegalStateException("this method allows only branch category");
- }
- labels.add(label);
- }
-
- public void setLabels(Label[] labelArray){
- if(labelArray == null){
- throw new NullPointerException();
- }
- if(category != Category.BRANCH){
- throw new IllegalStateException("this method allows only branch category");
- }
- labels.clear();
- for(Label label: labelArray){
- if(label == null){
- throw new NullPointerException();
- }
- labels.add(label);
- }
- }
-
- public boolean hasLabel(Label label){
- return labels.contains(label);
- }
-
- public Label getLabel(int index){
- return labels.get(index);
- }
-
- public synchronized Label[] getLabels(){
- return labels.toArray(new Label[labels.size()]);
- }
-
- public Iterator<Label> iterator(){
- return Collections.unmodifiableList(labels).iterator();
- }
-
- public void setAct(int act){
- if(category != Category.OBJECT && category != Category.INVOKE){
- throw new IllegalStateException("setAct can be called only object and invoke category.");
- }
- this.act = act;
- }
-
- public int getAct(){
- return act;
- }
-
- public Category getCategory(){
- return category;
- }
-
- public String toString(){
- StringBuilder sb = new StringBuilder();
- sb.append(String.format("%d:%s:%d(%s)", getOpcode(), getName(), getAct(), getCategory()));
-
- if(getCategory() == Category.BRANCH || getCategory() == Category.TARGETER){
- sb.append(labels);
- }
-
- return new String(sb);
- }
-}
+++ /dev/null
-package jp.sourceforge.stigmata.birthmarks;
-
-/*
- * $Id$
- */
-
-import java.util.List;
-
-/**
- *
- * @author Haruaki Tamada
- * @version $Revision$
- */
-public interface OpcodeExtractListener{
- public void opcodesExtracted(List<Opcode> opcodes);
-}
+++ /dev/null
-package jp.sourceforge.stigmata.birthmarks;
-
-/*
- * $Id$
- */
-
-import java.util.ArrayList;
-import java.util.List;
-
-import org.objectweb.asm.Label;
-import org.objectweb.asm.MethodAdapter;
-import org.objectweb.asm.MethodVisitor;
-import org.objectweb.asm.Opcodes;
-import org.objectweb.asm.Type;
-
-/**
- *
- * @author Haruaki TAMADA
- * @version $Revision$
- */
-public class OpcodeExtractMethodVisitor extends MethodAdapter{
- private List<Opcode> opcodes;
- private OpcodeManager manager = OpcodeManager.getInstance();
- private List<OpcodeExtractListener> listeners = new ArrayList<OpcodeExtractListener>();
-
- public OpcodeExtractMethodVisitor(MethodVisitor visitor){
- this(visitor, new ArrayList<Opcode>());
- }
-
- public OpcodeExtractMethodVisitor(MethodVisitor visitor, List<Opcode> opcodes){
- super(visitor);
- this.opcodes = opcodes;
- }
-
- public void addOpcodeExtractListener(OpcodeExtractListener listener){
- listeners.add(listener);
- }
-
- public void removeOpcodeExtractListener(OpcodeExtractListener listener){
- listeners.add(listener);
- }
-
- @Override
- public void visitFieldInsn(int opcode, String owner, String name, String desc){
- Opcode o = new Opcode(manager.getOpcode(opcode));
- int size = Type.getType(desc).getSize();
- switch(opcode){
- case Opcodes.PUTFIELD:
- size = -1 - size;
- break;
- case Opcodes.PUTSTATIC:
- size = 0 - size;
- break;
- case Opcodes.GETFIELD:
- size = -1 + size;
- break;
- case Opcodes.GETSTATIC:
- size = 0 + size;
- break;
- }
- o.setAct(size);
- opcodes.add(o);
- super.visitFieldInsn(opcode, owner, name, desc);
- }
-
- @Override
- public void visitIincInsn(int var, int increment){
- opcodes.add(manager.getOpcode(Opcodes.IINC));
- super.visitIincInsn(var, increment);
- }
-
- @Override
- public void visitInsn(int opcode){
- opcodes.add(manager.getOpcode(opcode));
- super.visitInsn(opcode);
- }
-
- @Override
- public void visitLabel(Label label){
- opcodes.add(new LabelOpcode(label));
- }
-
- @Override
- public void visitIntInsn(int opcode, int operand){
- opcodes.add(manager.getOpcode(opcode));
- super.visitIntInsn(opcode, operand);
- }
-
- @Override
- public void visitJumpInsn(int opcode, Label label){
- Opcode o = new Opcode(manager.getOpcode(opcode));
- o.addLabel(label);
- opcodes.add(o);
- super.visitJumpInsn(opcode, label);
- }
-
- @Override
- public void visitLdcInsn(Object value){
- opcodes.add(manager.getOpcode(Opcodes.LDC));
- super.visitLdcInsn(value);
- }
-
- @Override
- public void visitTableSwitchInsn(int min, int max, Label defaultLabel, Label[] labels){
- Opcode tableSwitch = new Opcode(manager.getOpcode(Opcodes.TABLESWITCH));
- tableSwitch.setLabels(labels);
- tableSwitch.addLabel(defaultLabel);
-
- opcodes.add(tableSwitch);
- super.visitTableSwitchInsn(min, max, defaultLabel, labels);
- }
-
- @Override
- public void visitLookupSwitchInsn(Label defaultHandle, int[] keys, Label[] labels){
- Opcode lookupSwitch = new Opcode(manager.getOpcode(Opcodes.LOOKUPSWITCH));
- lookupSwitch.setLabels(labels);
- lookupSwitch.addLabel(defaultHandle);
-
- opcodes.add(lookupSwitch);
- super.visitLookupSwitchInsn(defaultHandle, keys, labels);
- }
-
- @Override
- public void visitMethodInsn(int opcode, String owner, String name, String desc){
- Opcode methodOpcode = new Opcode(manager.getOpcode(opcode));
- Type[] types = Type.getArgumentTypes(desc);
- int argumentSize = 0;
- for(Type type: types) argumentSize = type.getSize();
- int size = Type.getReturnType(desc).getSize();
- switch(opcode){
- case Opcodes.INVOKESTATIC:
- size = size - argumentSize;
- break;
- case Opcodes.INVOKEINTERFACE:
- case Opcodes.INVOKESPECIAL:
- case Opcodes.INVOKEVIRTUAL:
- size = size - argumentSize - 1;
- break;
- }
- methodOpcode.setAct(size);
-
- opcodes.add(methodOpcode);
- super.visitMethodInsn(opcode, owner, name, desc);
- }
-
- @Override
- public void visitMultiANewArrayInsn(String desc, int dims){
- opcodes.add(manager.getOpcode(Opcodes.MULTIANEWARRAY));
- super.visitMultiANewArrayInsn(desc, dims);
- }
-
- @Override
- public void visitTypeInsn(int opcode, String desc){
- opcodes.add(manager.getOpcode(opcode));
- super.visitTypeInsn(opcode, desc);
- }
-
- @Override
- public void visitVarInsn(int opcode, int var){
- opcodes.add(manager.getOpcode(opcode));
- super.visitVarInsn(opcode, var);
- }
-
- @Override
- public void visitEnd(){
- for(OpcodeExtractListener listener: listeners){
- listener.opcodesExtracted(opcodes);
- }
- }
-}
+++ /dev/null
-package jp.sourceforge.stigmata.birthmarks;
-
-/*
- * $Id$
- */
-
-import java.util.ArrayList;
-import java.util.List;
-
-import jp.sourceforge.stigmata.Birthmark;
-import jp.sourceforge.stigmata.BirthmarkContext;
-import jp.sourceforge.stigmata.BirthmarkElement;
-
-import org.objectweb.asm.ClassVisitor;
-import org.objectweb.asm.MethodVisitor;
-
-/**
- *
- *
- * @author tamada
- * @version $Revision$
- */
-public class OpcodeExtractVisitor extends BirthmarkExtractVisitor{
- private List<Opcode> opcodeList = new ArrayList<Opcode>();
- private BirthmarkElementBuilder builder;
-
- public OpcodeExtractVisitor(ClassVisitor visitor, Birthmark birthmark, BirthmarkContext context, BirthmarkElementBuilder builder){
- super(visitor, birthmark, context);
- this.builder = builder;
- }
-
- public void visitEnd(){
- BirthmarkElement[] elements = builder.buildElements(opcodeList, getContext());
- for(BirthmarkElement element: elements){
- addElement(element);
- }
- }
-
- @Override
- public MethodVisitor visitMethod(int arg0, String arg1, String arg2, String arg3, String[] arg4){
- MethodVisitor visitor = super.visitMethod(arg0, arg1, arg2, arg3, arg4);
- OpcodeExtractMethodVisitor opcodeVisitor = new OpcodeExtractMethodVisitor(visitor, opcodeList);
-
- return opcodeVisitor;
- }
-}
+++ /dev/null
-package jp.sourceforge.stigmata.birthmarks;
-
-/*
- * $Id$
- */
-
-import java.io.BufferedReader;
-import java.io.InputStreamReader;
-import java.net.URL;
-import java.util.ArrayList;
-import java.util.HashMap;
-import java.util.List;
-import java.util.Map;
-
-import jp.sourceforge.talisman.csvio.CsvLine;
-import jp.sourceforge.talisman.csvio.CsvParser;
-
-import org.objectweb.asm.Label;
-import org.objectweb.asm.Opcodes;
-import org.objectweb.asm.Type;
-import org.objectweb.asm.tree.AbstractInsnNode;
-import org.objectweb.asm.tree.FieldInsnNode;
-import org.objectweb.asm.tree.JumpInsnNode;
-import org.objectweb.asm.tree.LabelNode;
-import org.objectweb.asm.tree.LookupSwitchInsnNode;
-import org.objectweb.asm.tree.MethodInsnNode;
-import org.objectweb.asm.tree.TableSwitchInsnNode;
-
-/**
- *
- * @author Haruaki Tamada
- * @version $Revision$
- */
-public class OpcodeManager{
- private Map<Integer, Opcode> opcodeMap = new HashMap<Integer, Opcode>();
- private static OpcodeManager manager = new OpcodeManager();
-
- /**
- * private constructor for singleton pattern.
- */
- private OpcodeManager(){
- try{
- URL location = OpcodeManager.class.getResource("/META-INF/bytecode.def");
- BufferedReader in = new BufferedReader(new InputStreamReader(location.openStream()));
- CsvParser parser = new CsvParser(in);
- while(parser.hasNext()){
- CsvLine line = parser.next();
- String[] values = line.getValues();
- if(values.length == 5){
- Opcode def = new Opcode(
- Integer.parseInt(values[0]), values[1],
- Integer.parseInt(values[2]),
- Integer.parseInt(values[3]), values[4]
- );
- opcodeMap.put(def.getOpcode(), def);
- }
- }
- } catch(Exception e){
- throw new InternalError(e.getMessage());
- }
- }
-
- public static OpcodeManager getInstance(){
- return manager;
- }
-
- public Opcode getOpcode(int opcode){
- return opcodeMap.get(opcode);
- }
-
- private Map<LabelNode, LabelOpcode> labelMap = new HashMap<LabelNode, LabelOpcode>();
-
- public Opcode getOpcode(AbstractInsnNode node){
- Opcode opcode = getOpcode(node.getOpcode());
- if(opcode == null && node instanceof LabelNode){
- opcode = labelMap.get(node);
- if(opcode == null){
- opcode = new LabelOpcode(((LabelNode)node).getLabel());
- labelMap.put((LabelNode)node, (LabelOpcode)opcode);
- }
- }
- if(opcode != null){
- switch(opcode.getCategory()){
- case BRANCH:
- opcode = constructBranchOpcode(opcode, node);
- break;
- case INVOKE:
- opcode = constructMethodOpcode(opcode, node);
- break;
- case OBJECT:
- opcode = constructObjectOpcode(opcode, node);
- break;
- case NORMAL: // Not needs conversion.
- case TARGETER: // Already convert above.
- default:
- break;
- }
- }
-
- return opcode;
- }
-
- private Opcode constructMethodOpcode(Opcode o, AbstractInsnNode node){
- Opcode methodOpcode = new Opcode(o);
- MethodInsnNode methodNode = (MethodInsnNode)node;
- Type[] types = Type.getArgumentTypes(methodNode.desc);
- int argumentSize = 0;
- for(Type type: types) argumentSize = type.getSize();
- int size = Type.getReturnType(methodNode.desc).getSize();
- switch(o.getOpcode()){
- case Opcodes.INVOKESTATIC:
- size = size - argumentSize;
- break;
- case Opcodes.INVOKEINTERFACE:
- case Opcodes.INVOKESPECIAL:
- case Opcodes.INVOKEVIRTUAL:
- size = size - argumentSize - 1;
- break;
- }
- methodOpcode.setAct(size);
-
- return methodOpcode;
- }
-
- private Opcode constructObjectOpcode(Opcode o, AbstractInsnNode node){
- Opcode opcode = new Opcode(o);
- FieldInsnNode field = (FieldInsnNode)node;
-
- int size = Type.getType(field.desc).getSize();
- switch(opcode.getOpcode()){
- case Opcodes.PUTFIELD:
- size = -1 - size;
- break;
- case Opcodes.PUTSTATIC:
- size = 0 - size;
- break;
- case Opcodes.GETFIELD:
- size = -1 + size;
- break;
- case Opcodes.GETSTATIC:
- size = 0 + size;
- break;
- }
- opcode.setAct(size);
- return opcode;
- }
-
- private Opcode constructBranchOpcode(Opcode defaultOpcode, AbstractInsnNode node){
- Opcode opcode = new Opcode(defaultOpcode);
- if(node instanceof TableSwitchInsnNode){
- TableSwitchInsnNode table = (TableSwitchInsnNode)node;
- List<Label> labels = new ArrayList<Label>();
- labels.add(table.dflt.getLabel());
- for(Object o: table.labels){
- labels.add(((LabelNode)o).getLabel());
- }
- }
- else if(node instanceof LookupSwitchInsnNode){
- LookupSwitchInsnNode lookup = (LookupSwitchInsnNode)node;
- List<Label> labels = new ArrayList<Label>();
- labels.add(lookup.dflt.getLabel());
- for(Object o: lookup.labels){
- labels.add(((LabelNode)o).getLabel());
- }
- }
- else{
- opcode.addLabel(((JumpInsnNode)node).label.getLabel());
- }
- return opcode;
- }
-}
+++ /dev/null
-0,nop,0,0,NORMAL\r
-1,aconst_null,0,1,NORMAL\r
-2,iconst_m1,0,1,NORMAL\r
-3,iconst_0,0,1,NORMAL\r
-4,iconst_1,0,1,NORMAL\r
-5,iconst_2,0,1,NORMAL\r
-6,iconst_3,0,1,NORMAL\r
-7,iconst_4,0,1,NORMAL\r
-8,iconst_5,0,1,NORMAL\r
-9,lconst_0,0,2,NORMAL\r
-10,lconst_1,0,2,NORMAL\r
-11,fconst_0,0,1,NORMAL\r
-12,fconst_1,0,1,NORMAL\r
-13,fconst_2,0,1,NORMAL\r
-14,dconst_0,0,2,NORMAL\r
-15,dconst_1,0,2,NORMAL\r
-16,bipush,1,1,NORMAL\r
-17,sipush,2,1,NORMAL\r
-18,ldc,1,1,NORMAL\r
-19,ldc_w,2,1,NORMAL\r
-20,ldc2_w,2,2,NORMAL\r
-21,iload,1,1,NORMAL\r
-22,lload,1,2,NORMAL\r
-23,fload,1,1,NORMAL\r
-24,dload,1,2,NORMAL\r
-25,aload,1,1,NORMAL\r
-26,iload_0,0,1,NORMAL\r
-27,iload_1,0,1,NORMAL\r
-28,iload_2,0,1,NORMAL\r
-29,iload_3,0,1,NORMAL\r
-30,lload_0,0,2,NORMAL\r
-31,lload_1,0,2,NORMAL\r
-32,lload_2,0,2,NORMAL\r
-33,lload_3,0,2,NORMAL\r
-34,fload_0,0,1,NORMAL\r
-35,fload_1,0,1,NORMAL\r
-36,fload_2,0,1,NORMAL\r
-37,fload_3,0,1,NORMAL\r
-38,dload_0,0,2,NORMAL\r
-39,dload_1,0,2,NORMAL\r
-40,dload_2,0,2,NORMAL\r
-41,dload_3,0,2,NORMAL\r
-42,aload_0,0,1,NORMAL\r
-43,aload_1,0,1,NORMAL\r
-44,aload_2,0,1,NORMAL\r
-45,aload_3,0,1,NORMAL\r
-46,iaload,0,-1,NORMAL\r
-47,laload,0,0,NORMAL\r
-48,faload,0,-1,NORMAL\r
-49,daload,0,0,NORMAL\r
-50,aaload,0,-1,NORMAL\r
-51,baload,0,-1,NORMAL\r
-52,caload,0,-1,NORMAL\r
-53,saload,0,-1,NORMAL\r
-54,istore,1,-1,NORMAL\r
-55,lstore,1,-2,NORMAL\r
-56,fstore,1,-1,NORMAL\r
-57,dstore,1,-2,NORMAL\r
-58,astore,1,-1,NORMAL\r
-59,istore_0,0,-1,NORMAL\r
-60,istore_1,0,-1,NORMAL\r
-61,istore_2,0,-1,NORMAL\r
-62,istore_3,0,-1,NORMAL\r
-63,lstore_0,0,-2,NORMAL\r
-64,lstore_1,0,-2,NORMAL\r
-65,lstore_2,0,-2,NORMAL\r
-66,lstore_3,0,-2,NORMAL\r
-67,fstore_0,0,-1,NORMAL\r
-68,fstore_1,0,-1,NORMAL\r
-69,fstore_2,0,-1,NORMAL\r
-70,fstore_3,0,-1,NORMAL\r
-71,dstore_0,0,-2,NORMAL\r
-72,dstore_1,0,-2,NORMAL\r
-73,dstore_2,0,-2,NORMAL\r
-74,dstore_3,0,-2,NORMAL\r
-75,astore_0,0,-1,NORMAL\r
-76,astore_1,0,-1,NORMAL\r
-77,astore_2,0,-1,NORMAL\r
-78,astore_3,0,-1,NORMAL\r
-79,iastore,0,-3,NORMAL\r
-80,lastore,0,-3,NORMAL\r
-81,fastore,0,-3,NORMAL\r
-82,dastore,0,-3,NORMAL\r
-83,aastore,0,-3,NORMAL\r
-84,bastore,0,-3,NORMAL\r
-85,castore,0,-3,NORMAL\r
-86,sastore,0,-3,NORMAL\r
-87,pop,0,-1,NORMAL\r
-88,pop2,0,-2,NORMAL\r
-89,dup,0,1,NORMAL\r
-90,dup_x1,0,1,NORMAL\r
-91,dup_x2,0,1,NORMAL\r
-92,dup2,0,2,NORMAL\r
-93,dup2_x1,0,2,NORMAL\r
-94,dup2_x2,0,2,NORMAL\r
-95,swap,0,0,NORMAL\r
-96,iadd,0,-1,NORMAL\r
-97,ladd,0,-2,NORMAL\r
-98,fadd,0,-1,NORMAL\r
-99,dadd,0,-2,NORMAL\r
-100,isub,0,-1,NORMAL\r
-101,lsub,0,-2,NORMAL\r
-102,fsub,0,-1,NORMAL\r
-103,dsub,0,-2,NORMAL\r
-104,imul,0,-1,NORMAL\r
-105,lmul,0,-2,NORMAL\r
-106,fmul,0,-1,NORMAL\r
-107,dmul,0,-2,NORMAL\r
-108,idiv,0,-1,NORMAL\r
-109,ldiv,0,-2,NORMAL\r
-110,fdiv,0,-1,NORMAL\r
-111,ddiv,0,-2,NORMAL\r
-112,irem,0,-1,NORMAL\r
-113,lrem,0,-2,NORMAL\r
-114,frem,0,-1,NORMAL\r
-115,drem,0,-2,NORMAL\r
-116,ineg,0,0,NORMAL\r
-117,lneg,0,0,NORMAL\r
-118,fneg,0,0,NORMAL\r
-119,dneg,0,0,NORMAL\r
-120,ishl,0,-1,NORMAL\r
-121,lshl,0,-1,NORMAL\r
-122,ishr,0,-1,NORMAL\r
-123,lshr,0,-1,NORMAL\r
-124,iushr,0,-1,NORMAL\r
-125,lushr,0,-2,NORMAL\r
-126,iand,0,-1,NORMAL\r
-127,land,0,-2,NORMAL\r
-128,ior,0,-1,NORMAL\r
-129,lor,0,-2,NORMAL\r
-130,ixor,0,-1,NORMAL\r
-131,lxor,0,-2,NORMAL\r
-132,iinc,2,0,NORMAL\r
-133,i2l,0,1,NORMAL\r
-134,i2f,0,0,NORMAL\r
-135,i2d,0,1,NORMAL\r
-136,l2i,0,-1,NORMAL\r
-137,l2f,0,-1,NORMAL\r
-138,l2d,0,0,NORMAL\r
-139,f2i,0,0,NORMAL\r
-140,f2l,0,1,NORMAL\r
-141,f2d,0,1,NORMAL\r
-142,d2i,0,-1,NORMAL\r
-143,d2l,0,0,NORMAL\r
-144,d2f,0,-1,NORMAL\r
-145,i2b,0,0,NORMAL\r
-146,i2c,0,0,NORMAL\r
-147,i2s,0,0,NORMAL\r
-148,lcmp,0,-3,NORMAL\r
-149,fcmpl,0,-1,NORMAL\r
-150,fcmpg,0,-1,NORMAL\r
-151,dcmpl,0,-3,NORMAL\r
-152,dcmpg,0,-3,NORMAL\r
-153,ifeq,2,-1,BRANCH\r
-154,ifne,2,-1,BRANCH\r
-155,iflt,2,-1,BRANCH\r
-156,ifge,2,-1,BRANCH\r
-157,ifgt,2,-1,BRANCH\r
-158,ifle,2,-1,BRANCH\r
-159,if_icmpeq,2,-2,BRANCH\r
-160,if_icmpne,2,-2,BRANCH\r
-161,if_icmplt,2,-2,BRANCH\r
-162,if_icmpge,2,-2,BRANCH\r
-163,if_icmpgt,2,-2,BRANCH\r
-164,if_icmple,2,-2,BRANCH\r
-165,if_acmpeq,2,-2,BRANCH\r
-166,if_acmpne,2,-2,BRANCH\r
-167,goto,2,-1,BRANCH\r
-168,jsr,2,-1,BRANCH\r
-169,ret,1,0,NORMAL\r
-170,tableswitch,-1,-1,BRANCH\r
-171,lookupswitch,-1,-1,BRANCH\r
-172,ireturn,0,-1,NORMAL\r
-173,lreturn,0,-2,NORMAL\r
-174,freturn,0,-1,NORMAL\r
-175,dreturn,0,-2,NORMAL\r
-176,areturn,0,-1,NORMAL\r
-177,return,0,0,NORMAL\r
-178,getstatic,2,0,OBJECT\r
-179,putstatic,2,0,OBJECT\r
-180,getfield,2,0,OBJECT\r
-181,putfield,2,0,OBJECT\r
-182,invokevirtual,2,0,INVOKE\r
-183,invokespecial,2,0,INVOKE\r
-184,invokestatic,2,0,INVOKE\r
-185,invokeinterface,2,0,INVOKE\r
-186,__unused,0\r
-187,new,2,1,NORMAL\r
-188,newarray,1,0,NORMAL\r
-189,anewarray,2,0,NORMAL\r
-190,arraylength,0,0,NORMAL\r
-191,athrow,0,-1,NORMAL\r
-192,checkcast,2,0,NORMAL\r
-193,instanceof,2,0,NORMAL\r
-194,monitorenter,0,-1,NORMAL\r
-195,monitorexit,0,-1,NORMAL\r
-196,wide,-1,0,NORMAL\r
-197,multianewarray,3,-1,NORMAL\r
-198,ifnull,2,-1,BRANCH\r
-199,ifnonnull,2,-1,BRANCH\r
-200,goto_w,4,-1,BRANCH\r
-201,jsr_w,4,-1,BRANCH\r
-202,breakpoint,0\r
-203,ldc_quick,1\r
-204,__unused,0\r
-205,ldc2_w_quick,2\r
-206,getfield_quick,2\r
-207,putfield_quick,2\r
-208,getfield2_quick,2\r
-209,putfield2_quick,2\r
-210,__unused,0\r
-211,putstatic_quick,2\r
-212,getstatic2_quick,2\r
-213,putstatic2_quick,2\r
-214,invokevirtual_quick,2\r
-215,invokenonvirtual_quick,2\r
-216,invokesuper_quick,2\r
-217,invokestatic_quick,2\r
-218,invokeinterface_quick,2\r
-219,invokevirtualobject_quick,2\r
-220,__unused,0\r
-221,new_quick,2\r
-222,anewarray_quick,2\r
-223,multianewarray_quick,3\r
-224,checkcast_quick,2\r
-225,instanceof_quick,2\r
-226,invokevirtual_quick_w,4\r
-227,getfield_quick_w,4\r
-228,putfield_quick_w,4\r
-229,__unused,0\r
-230,__unused,0\r
-231,__unused,0\r
-232,__unused,0\r
-233,__unused,0\r
-234,__unused,0\r
-235,__unused,0\r
-236,__unused,0\r
-237,__unused,0\r
-238,__unused,0\r
-239,__unused,0\r
-240,__unused,0\r
-241,__unused,0\r
-242,__unused,0\r
-243,__unused,0\r
-244,__unused,0\r
-245,__unused,0\r
-246,__unused,0\r
-247,__unused,0\r
-248,__unused,0\r
-249,__unused,0\r
-250,__unused,0\r
-251,__unused,0\r
-252,__unused,0\r
-253,__unused,0\r
-254,impdep1,0\r
-255,impdep2,0\r
+++ /dev/null
-package jp.sourceforge.stigmata.birthmarks;\r
-\r
-import java.util.Iterator;\r
-\r
-import junit.framework.Assert;\r
-\r
-import org.junit.Before;\r
-import org.junit.Test;\r
-import org.objectweb.asm.ClassReader;\r
-import org.objectweb.asm.ClassWriter;\r
-\r
-public class ControlFlowGraphTest {\r
- private ControlFlowGraphExtractVisitor cfVisitor;\r
- private ControlFlowGraphExtractVisitor cfVisitor2;\r
-\r
- @Before\r
- public void setUp() throws Exception{\r
- ClassReader reader1 = new ClassReader(getClass().getResource("/resources/MyServer.class").openStream());\r
- cfVisitor = new ControlFlowGraphExtractVisitor(new ClassWriter(0));\r
- reader1.accept(cfVisitor, 0);\r
-\r
- ClassReader reader2 = new ClassReader(getClass().getResource("/resources/MyServer2.class").openStream());\r
- cfVisitor2 = new ControlFlowGraphExtractVisitor(new ClassWriter(0));\r
- reader2.accept(cfVisitor2, 0);\r
- }\r
-\r
- @Test\r
- public void testBasic() throws Exception{\r
- Iterator<String> iterator = cfVisitor.getMethodNames();\r
-\r
- Assert.assertTrue(iterator.hasNext());\r
- Assert.assertEquals("<init>(I)V", iterator.next());\r
- Assert.assertFalse(iterator.hasNext());\r
-\r
- ControlFlowGraph graph = cfVisitor.getGraph("<init>(I)V");\r
- Assert.assertEquals(6, graph.getBasicBlockSize());\r
- graph.setIncludingExceptionFlow(true);\r
-\r
- Assert.assertEquals(6, graph.getBasicBlockSize());\r
- }\r
-\r
- @Test\r
- public void testGraph() throws Exception{\r
- int[][] graph = cfVisitor.getGraph("<init>(I)V").getGraphMatrix();\r
-\r
- Assert.assertEquals(6, graph.length);\r
-\r
- Assert.assertEquals(0, graph[0][0]);\r
- Assert.assertEquals(1, graph[0][1]);\r
- Assert.assertEquals(1, graph[0][2]);\r
- Assert.assertEquals(0, graph[0][3]);\r
- Assert.assertEquals(0, graph[0][4]);\r
- Assert.assertEquals(0, graph[0][5]);\r
-\r
- Assert.assertEquals(0, graph[1][0]);\r
- Assert.assertEquals(0, graph[1][1]);\r
- Assert.assertEquals(0, graph[1][2]);\r
- Assert.assertEquals(1, graph[1][3]);\r
- Assert.assertEquals(0, graph[1][4]);\r
- Assert.assertEquals(0, graph[1][5]);\r
-\r
- Assert.assertEquals(0, graph[2][0]);\r
- Assert.assertEquals(0, graph[2][1]);\r
- Assert.assertEquals(0, graph[2][2]);\r
- Assert.assertEquals(1, graph[2][3]);\r
- Assert.assertEquals(0, graph[2][4]);\r
- Assert.assertEquals(0, graph[2][5]);\r
-\r
- Assert.assertEquals(0, graph[3][0]);\r
- Assert.assertEquals(0, graph[3][1]);\r
- Assert.assertEquals(0, graph[3][2]);\r
- Assert.assertEquals(0, graph[3][3]);\r
- Assert.assertEquals(0, graph[3][4]);\r
- Assert.assertEquals(1, graph[3][5]);\r
-\r
- Assert.assertEquals(0, graph[4][0]);\r
- Assert.assertEquals(0, graph[4][1]);\r
- Assert.assertEquals(0, graph[4][2]);\r
- Assert.assertEquals(0, graph[4][3]);\r
- Assert.assertEquals(0, graph[4][4]);\r
- Assert.assertEquals(1, graph[4][5]);\r
-\r
- Assert.assertEquals(0, graph[5][0]);\r
- Assert.assertEquals(0, graph[5][1]);\r
- Assert.assertEquals(0, graph[5][2]);\r
- Assert.assertEquals(0, graph[5][3]);\r
- Assert.assertEquals(0, graph[5][4]);\r
- Assert.assertEquals(0, graph[5][5]);\r
- }\r
-\r
- @Test\r
- public void testExceptionGraph() throws Exception{\r
- ControlFlowGraph cfgraph = cfVisitor.getGraph("<init>(I)V");\r
- cfgraph.setIncludingExceptionFlow(true);\r
- int[][] graph = cfgraph.getGraphMatrix();\r
-\r
- Assert.assertEquals(6, graph.length);\r
-\r
- Assert.assertEquals(0, graph[0][0]);\r
- Assert.assertEquals(1, graph[0][1]);\r
- Assert.assertEquals(1, graph[0][2]);\r
- Assert.assertEquals(0, graph[0][3]);\r
- Assert.assertEquals(1, graph[0][4]);\r
- Assert.assertEquals(0, graph[0][5]);\r
-\r
- Assert.assertEquals(0, graph[1][0]);\r
- Assert.assertEquals(0, graph[1][1]);\r
- Assert.assertEquals(0, graph[1][2]);\r
- Assert.assertEquals(1, graph[1][3]);\r
- Assert.assertEquals(1, graph[1][4]);\r
- Assert.assertEquals(0, graph[1][5]);\r
-\r
- Assert.assertEquals(0, graph[2][0]);\r
- Assert.assertEquals(0, graph[2][1]);\r
- Assert.assertEquals(0, graph[2][2]);\r
- Assert.assertEquals(1, graph[2][3]);\r
- Assert.assertEquals(1, graph[2][4]);\r
- Assert.assertEquals(0, graph[2][5]);\r
-\r
- Assert.assertEquals(0, graph[3][0]);\r
- Assert.assertEquals(0, graph[3][1]);\r
- Assert.assertEquals(0, graph[3][2]);\r
- Assert.assertEquals(0, graph[3][3]);\r
- Assert.assertEquals(1, graph[3][4]);\r
- Assert.assertEquals(1, graph[3][5]);\r
-\r
- Assert.assertEquals(0, graph[4][0]);\r
- Assert.assertEquals(0, graph[4][1]);\r
- Assert.assertEquals(0, graph[4][2]);\r
- Assert.assertEquals(0, graph[4][3]);\r
- Assert.assertEquals(0, graph[4][4]);\r
- Assert.assertEquals(1, graph[4][5]);\r
-\r
- Assert.assertEquals(0, graph[5][0]);\r
- Assert.assertEquals(0, graph[5][1]);\r
- Assert.assertEquals(0, graph[5][2]);\r
- Assert.assertEquals(0, graph[5][3]);\r
- Assert.assertEquals(0, graph[5][4]);\r
- Assert.assertEquals(0, graph[5][5]);\r
- }\r
-\r
- @Test\r
- public void testBasic2() throws Exception{\r
- Iterator<String> iterator = cfVisitor2.getMethodNames();\r
-\r
- Assert.assertTrue(iterator.hasNext());\r
- Assert.assertEquals("<init>(I)V", iterator.next());\r
- Assert.assertFalse(iterator.hasNext());\r
-\r
- ControlFlowGraph graph = cfVisitor2.getGraph("<init>(I)V");\r
-\r
- Assert.assertEquals(6, graph.getBasicBlockSize());\r
-\r
- // graph.setIncludingExceptionFlow(true);\r
- // Assert.assertEquals(6, graph.getBasicBlockSize());\r
- }\r
-\r
- @Test\r
- public void testGraph2() throws Exception{\r
- ControlFlowGraph graph = cfVisitor2.getGraph("<init>(I)V");\r
- int[][] graphMatrix = graph.getGraphMatrix();\r
-\r
- Assert.assertEquals(6, graphMatrix.length);\r
-\r
- Assert.assertEquals(0, graphMatrix[0][0]);\r
- Assert.assertEquals(1, graphMatrix[0][1]);\r
- Assert.assertEquals(1, graphMatrix[0][2]);\r
- Assert.assertEquals(0, graphMatrix[0][3]);\r
- Assert.assertEquals(0, graphMatrix[0][4]);\r
- Assert.assertEquals(0, graphMatrix[0][5]);\r
-\r
- Assert.assertEquals(0, graphMatrix[1][0]);\r
- Assert.assertEquals(0, graphMatrix[1][1]);\r
- Assert.assertEquals(0, graphMatrix[1][2]);\r
- Assert.assertEquals(1, graphMatrix[1][3]);\r
- Assert.assertEquals(0, graphMatrix[1][4]);\r
- Assert.assertEquals(0, graphMatrix[1][5]);\r
-\r
- Assert.assertEquals(0, graphMatrix[2][0]);\r
- Assert.assertEquals(0, graphMatrix[2][1]);\r
- Assert.assertEquals(0, graphMatrix[2][2]);\r
- Assert.assertEquals(1, graphMatrix[2][3]);\r
- Assert.assertEquals(0, graphMatrix[2][4]);\r
- Assert.assertEquals(0, graphMatrix[2][5]);\r
-\r
- Assert.assertEquals(0, graphMatrix[3][0]);\r
- Assert.assertEquals(0, graphMatrix[3][1]);\r
- Assert.assertEquals(0, graphMatrix[3][2]);\r
- Assert.assertEquals(0, graphMatrix[3][3]);\r
- Assert.assertEquals(0, graphMatrix[3][4]);\r
- Assert.assertEquals(1, graphMatrix[3][5]);\r
-\r
- Assert.assertEquals(0, graphMatrix[4][0]);\r
- Assert.assertEquals(0, graphMatrix[4][1]);\r
- Assert.assertEquals(0, graphMatrix[4][2]);\r
- Assert.assertEquals(0, graphMatrix[4][3]);\r
- Assert.assertEquals(0, graphMatrix[4][4]);\r
- Assert.assertEquals(1, graphMatrix[4][5]);\r
-\r
- Assert.assertEquals(0, graphMatrix[5][0]);\r
- Assert.assertEquals(0, graphMatrix[5][1]);\r
- Assert.assertEquals(0, graphMatrix[5][2]);\r
- Assert.assertEquals(0, graphMatrix[5][3]);\r
- Assert.assertEquals(0, graphMatrix[5][4]);\r
- Assert.assertEquals(0, graphMatrix[5][5]);\r
- }\r
-}\r
+++ /dev/null
-package jp.sourceforge.stigmata.birthmarks;
-
-/*
- * $Id$
- */
-
-import org.junit.Assert;
-import org.junit.Before;
-import org.junit.Test;
-import org.objectweb.asm.Label;
-
-/**
- *
- * @author Haruaki Tamada
- * @version $Revision$
- */
-public class LabelOpcodeTest{
- private LabelOpcode opcode;
- private Label label;
-
- @Before
- public void setup(){
- label = new Label();
- opcode = new LabelOpcode(label);
- }
-
- @Test
- public void testBasic(){
- Assert.assertEquals(Opcode.Category.TARGETER, opcode.getCategory());
- Assert.assertEquals(-1, opcode.getOpcode());
- Assert.assertEquals("targeter", opcode.getName());
- Assert.assertEquals(label, opcode.getLabel());
- }
-}
+++ /dev/null
-package jp.sourceforge.stigmata.birthmarks;
-
-/*
- * $Id$
- */
-
-import org.junit.Assert;
-import org.junit.Test;
-
-/**
- *
- * @author Haruaki Tamada
- * @version $Revision$
- */
-public class OpcodeManagerTest{
- @Test
- public void testBasic(){
- Assert.assertNotNull(OpcodeManager.getInstance());
-
- Opcode opcode = OpcodeManager.getInstance().getOpcode(182);
-
- Assert.assertEquals(182, opcode.getOpcode());
- Assert.assertEquals("invokevirtual", opcode.getName());
- }
-}
+++ /dev/null
-package jp.sourceforge.stigmata.birthmarks;
-
-/*
- * $Id$
- */
-
-import java.util.Iterator;
-
-import org.junit.Assert;
-import org.junit.Before;
-import org.junit.Test;
-import org.objectweb.asm.Label;
-
-/**
- *
- * @author Haruaki Tamada
- * @version $Revision$
- */
-public class OpcodeTest{
- private Opcode opcode;
-
- @Before
- public void setup(){
- opcode = new Opcode(26, "iload_0", 0, 1, Opcode.Category.NORMAL);
- }
-
- @Test
- public void testBasic(){
- Assert.assertEquals(26, opcode.getOpcode());
- Assert.assertEquals("iload_0", opcode.getName());
- Assert.assertEquals(0, opcode.getArgumentCount());
- Assert.assertEquals(1, opcode.getAct());
- Assert.assertEquals(Opcode.Category.NORMAL, opcode.getCategory());
- }
-
- @Test
- public void testSelfConstructor(){
- Opcode o = new Opcode(opcode);
- Assert.assertEquals(26, o.getOpcode());
- Assert.assertEquals("iload_0", o.getName());
- Assert.assertEquals(0, o.getArgumentCount());
- Assert.assertEquals(1, o.getAct());
- Assert.assertEquals(Opcode.Category.NORMAL, o.getCategory());
- }
-
- @Test(expected=IllegalStateException.class)
- public void testSetActThrowException(){
- opcode.setAct(1);
- }
-
- @Test(expected=IllegalStateException.class)
- public void testAddLabelThrowException(){
- opcode.addLabel(new Label());
- }
-
- @Test(expected=NullPointerException.class)
- public void testAddLabelNullPointer(){
- opcode.addLabel(null);
- }
-
- @Test(expected=IllegalStateException.class)
- public void testSetLabelsThrowException(){
- opcode.setLabels(new Label[] { new Label() });
- }
-
- @Test(expected=NullPointerException.class)
- public void testSetLabelsNullPointer1(){
- opcode.setLabels(null);
- }
-
- @Test
- public void testAddLabel(){
- opcode = new Opcode(154, "ifne", 2, -1, "BRANCH");
- Label label1 = new Label();
- Label label2 = new Label();
- Label label3 = new Label();
-
- opcode.addLabel(label1);
- opcode.addLabel(label2);
- opcode.addLabel(label3);
-
- Assert.assertEquals(label1, opcode.getLabel(0));
- Assert.assertEquals(label2, opcode.getLabel(1));
- Assert.assertEquals(label3, opcode.getLabel(2));
-
- Iterator<Label> iterator = opcode.iterator();
- Assert.assertTrue(iterator.hasNext());
- Assert.assertEquals(label1, iterator.next());
- Assert.assertTrue(iterator.hasNext());
- Assert.assertEquals(label2, iterator.next());
- Assert.assertTrue(iterator.hasNext());
- Assert.assertEquals(label3, iterator.next());
- Assert.assertFalse(iterator.hasNext());
- }
-
- @Test
- public void testSetLabels(){
- opcode = new Opcode(154, "ifne", 2, -1, "BRANCH");
- Label label1 = new Label();
- Label label2 = new Label();
- Label label3 = new Label();
-
- opcode.addLabel(label1);
- opcode.setLabels(new Label[] { label1, label2, label3, });
-
- Assert.assertEquals(label1, opcode.getLabel(0));
- Assert.assertEquals(label2, opcode.getLabel(1));
- Assert.assertEquals(label3, opcode.getLabel(2));
-
- Iterator<Label> iterator = opcode.iterator();
- Assert.assertTrue(iterator.hasNext());
- Assert.assertEquals(label1, iterator.next());
- Assert.assertTrue(iterator.hasNext());
- Assert.assertEquals(label2, iterator.next());
- Assert.assertTrue(iterator.hasNext());
- Assert.assertEquals(label3, iterator.next());
- Assert.assertFalse(iterator.hasNext());
- }
-
- @Test(expected=NullPointerException.class)
- public void testSetLabelsThrownNullPointerException(){
- opcode = new Opcode(154, "ifne", 2, -1, "BRANCH");
-
- opcode.setLabels(new Label[] { null, });
- }
-
- /**
- * this test will be thrown IllegalStateException.
- * Because, IllegalStateException is checked before null check of array elements.
- */
- @Test(expected=IllegalStateException.class)
- public void testSetLabelsNullPointer2(){
- opcode.setLabels(new Label[] { null, });
- }
-
- @Test
- public void testSetAct() throws Exception{
- opcode = new Opcode(182, "invokevirtual", 2, 0, "INVOKE");
- opcode.setAct(4);
- }
-}
+++ /dev/null
-import java.io.*;
-import java.net.*;
-
-public class MyServer2{
- private int port;
- private ServerSocket server;
-
- public MyServer2(int defaultPort){
- try{
- if(defaultPort > 0){
- port = defaultPort;
- server = new ServerSocket(port);
- }
- else{
- server = new ServerSocket();
- }
- } catch(IOException e){
- }
- }
-}
+++ /dev/null
-import java.io.*;
-import org.objectweb.asm.*;
-import org.objectweb.asm.tree.*;
-
-/**
- * 以下の原稿にあるクラスファイルを作成するためのクラス.
- * ASMを使ってバイトコードを直接生成している.
- * <ul>
- * <li>Heewan Park, Hyun-il Lim, Seokwoo Choi, Taisook Han, ``Detecting Common Modules in Java Packages Based on Static Object Trace Birthmark,'' The Computer Journal (Advance Access), Nov 5 2009, doi:10.1093/comjnl/bxp095</li>
- * </ul>
- */
-public class MyServerBuilder{
- public MyServerBuilder(){
- }
-
- public void write(OutputStream out) throws Exception{
- ClassWriter writer = new ClassWriter(ClassWriter.COMPUTE_MAXS | ClassWriter.COMPUTE_FRAMES);
-
- writer.visit(50, Opcodes.ACC_PUBLIC, "MyServer", null, "java/lang/Object", null);
- FieldVisitor fv1 = writer.visitField(Opcodes.ACC_PRIVATE, "Port", "I", null, 9999);
- fv1.visitEnd();
- FieldVisitor fv2 = writer.visitField(Opcodes.ACC_PRIVATE, "Sock", "Ljava/net/ServerSocket;", null, null);
- fv2.visitEnd();
- MethodVisitor mv = writer.visitMethod(Opcodes.ACC_PUBLIC, "<init>", "(I)V", null, null);
-
- Label label1 = new Label();
- Label label2 = new Label();
- Label label3 = new Label();
- Label startTry = new Label();
- Label catchLabel = new Label();
- mv.visitCode();
- mv.visitVarInsn(Opcodes.ALOAD, 0);
- mv.visitMethodInsn(Opcodes.INVOKESPECIAL, "java/lang/Object", "<init>", "()V");
- mv.visitVarInsn(Opcodes.ALOAD, 0);
- mv.visitIntInsn(Opcodes.SIPUSH, 9999);
- mv.visitFieldInsn(Opcodes.PUTFIELD, "MyServer", "Port", "I");
- mv.visitLabel(startTry);
- mv.visitVarInsn(Opcodes.ILOAD, 1);
- mv.visitJumpInsn(Opcodes.IFLE, label1);
- mv.visitVarInsn(Opcodes.ALOAD, 0);
- mv.visitVarInsn(Opcodes.ILOAD, 1);
- mv.visitFieldInsn(Opcodes.PUTFIELD, "MyServer", "Port", "I");
- mv.visitVarInsn(Opcodes.ALOAD, 0);
- mv.visitTypeInsn(Opcodes.NEW, "java/net/ServerSocket");
- mv.visitInsn(Opcodes.DUP);
- mv.visitVarInsn(Opcodes.ILOAD, 1);
- mv.visitMethodInsn(Opcodes.INVOKESPECIAL, "java/net/ServerSocket", "<init>", "(I)V");
- mv.visitFieldInsn(Opcodes.PUTFIELD, "MyServer", "Sock", "Ljava/net/ServerSocket;");
- mv.visitJumpInsn(Opcodes.GOTO, label2);
- mv.visitLabel(label1);
- mv.visitVarInsn(Opcodes.ALOAD, 0);
- mv.visitTypeInsn(Opcodes.NEW, "java/net/ServerSocket");
- mv.visitInsn(Opcodes.DUP);
- mv.visitMethodInsn(Opcodes.INVOKESPECIAL, "java/net/ServerSocket", "<init>", "()V");
- mv.visitFieldInsn(Opcodes.PUTFIELD, "MyServer", "Sock", "Ljava/net/ServerSocket;");
- mv.visitLabel(label2);
- mv.visitJumpInsn(Opcodes.GOTO, label3);
- mv.visitLabel(catchLabel);
- mv.visitVarInsn(Opcodes.ASTORE, 2);
- mv.visitLabel(label3);
- mv.visitInsn(Opcodes.RETURN);
- mv.visitTryCatchBlock(startTry, label2, catchLabel, "java/io/IOException");
- mv.visitEnd();
- writer.visitEnd();
-
- out.write(writer.toByteArray());
- }
-
- public static void main(String[] args) throws Exception{
- MyServerBuilder builder = new MyServerBuilder();
-
- OutputStream out = new FileOutputStream(args[0]);
- builder.write(out);
- out.close();
- }
-}
\ No newline at end of file
--- /dev/null
+<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">\r
+\r
+ <parent>\r
+ <groupId>jp.sourceforge.stigmata</groupId>\r
+ <artifactId>stigmata-plugins</artifactId>\r
+ <version>4.0-SNAPSHOT</version>\r
+ </parent>\r
+\r
+ <modelVersion>4.0.0</modelVersion>\r
+ <groupId>jp.sourceforge.stigmata.plugins</groupId>\r
+ <artifactId>kgram</artifactId>\r
+ <name>k-gram based birthmark</name>\r
+ <version>1.0.0-SNAPSHOT</version>\r
+ <packaging>jar</packaging>\r
+ <url>http://stigmata.sourceforge.jp/plugins/kgram/</url>\r
+</project>\r
--- /dev/null
+package jp.sourceforge.stigmata.birthmarks.kgram;
+
+import java.io.Serializable;
+import java.lang.reflect.Array;
+import java.util.Arrays;
+
+/**
+ * This class represents k-gram of the some sequence.
+ *
+ * @author Haruaki TAMADA
+ */
+public class KGram<T> implements Serializable{
+ private static final long serialVersionUID = 273465874532523L;
+ // private List<T> list = new ArrayList<T>();
+ private int maxLength = 4;
+ private T[] values;
+
+ /**
+ * constructor.
+ * @param kvalue the number of elements of this object.
+ */
+ public KGram(int kvalue){
+ setKValue(kvalue);
+ }
+
+ /**
+ * sets k-value.
+ * @param kvalue the number of elements of this object.
+ */
+ public void setKValue(int kvalue){
+ this.maxLength = kvalue;
+ }
+
+ /**
+ * returns k-value which is the number of elements.
+ * @return the number of elements.
+ */
+ public int getKValue(){
+ return maxLength;
+ }
+
+ /**
+ * returns string representation of this object.
+ */
+ @Override
+ public String toString(){
+ StringBuffer buffer = new StringBuffer("{ ");
+ for(int i = 0; i < maxLength; i++){
+ if(i != 0) buffer.append(", ");
+ buffer.append(get(i));
+ }
+ buffer.append(" }");
+ return new String(buffer);
+ }
+
+ /**
+ * sets the given value to kgram element at given index.
+ * @param index index.
+ * @param value value.
+ */
+ @SuppressWarnings("unchecked")
+ public void set(int index, T value){
+ if(index < 0 || index >= maxLength){
+ throw new ArrayIndexOutOfBoundsException(
+ "expected 0-" + (maxLength - 1) + ": " + index
+ );
+ }
+ if(value == null){
+ throw new NullPointerException("null value");
+ }
+ if(values == null){
+ values = (T[])Array.newInstance(value.getClass(), getKValue());
+ }
+ values[index] = value;
+ }
+
+ /**
+ * returns an object of given index.
+ */
+ public T get(int index){
+ T returnValue = null;
+ if(index < 0 || index >= maxLength){
+ throw new ArrayIndexOutOfBoundsException(
+ "expected 0-" + (maxLength - 1) + ": " + index
+ );
+ }
+ if(values != null){
+ returnValue = values[index];
+ }
+
+ return returnValue;
+ }
+
+ /**
+ * adds value at last index.
+ *
+ * this object is called with given 2 when following situation,
+ * <ul>
+ * <li>{ 1, 3, null, null } -> { 1, 2, 3, null } and return 2<li>
+ * <li>{ 1, null, 3, null } -> { 1, 2, 3, null } and return 1<li>
+ * <li>{ 1, 2, 3, 4 } -> { 1, 2, 3, 4 } and return -1<li>
+ * </ul>
+ *
+ * @param value value for addition.
+ * @return added index.
+ */
+ public int add(T value){
+ int index = -1;
+ for(int i = 0; i < values.length; i++){
+ if(values[i] == null){
+ index = i;
+ values[i] = value;
+ break;
+ }
+ }
+ return index;
+ }
+
+ /**
+ * returns an array of elements this object has.
+ * @return
+ */
+ @SuppressWarnings("unchecked")
+ public T[] toArray(){
+ if(values == null){
+ throw new IllegalStateException("this object has no elements.");
+ }
+ T[] newarray = (T[])Array.newInstance(
+ values[0].getClass(), getKValue()
+ );
+ System.arraycopy(values, 0, newarray, 0, getKValue());
+ return newarray;
+ }
+
+ @Override
+ public boolean equals(Object o){
+ if(o instanceof KGram){
+ KGram<?> kgram = (KGram<?>)o;
+ boolean flag = getKValue() == kgram.getKValue();
+ for(int i = 0; !flag && i < maxLength; i++){
+ if(!get(i).equals(kgram.get(i))){
+ flag = false;
+ break;
+ }
+ }
+ return flag;
+ }
+ return false;
+ }
+
+ @Override
+ public int hashCode(){
+ return Arrays.hashCode(values);
+ }
+}
--- /dev/null
+package jp.sourceforge.stigmata.birthmarks.kgram;
+
+import jp.sourceforge.stigmata.BirthmarkElement;
+
+/**
+ *
+ * @author Haruaki TAMADA
+ */
+public class KGramBasedBirthmarkElement<T> extends BirthmarkElement{
+ private static final long serialVersionUID = 28546543857543634L;
+
+ private KGram<T> kgram;
+
+ public KGramBasedBirthmarkElement(KGram<T> kgram){
+ super(kgram.toString());
+ this.kgram = kgram;
+ }
+
+ @Override
+ @SuppressWarnings("rawtypes")
+ public boolean equals(Object o){
+ return o instanceof KGramBasedBirthmarkElement &&
+ kgram.equals(((KGramBasedBirthmarkElement)o).kgram);
+ }
+
+ @Override
+ public int hashCode(){
+ int v = kgram.hashCode();
+
+ return (v & 0xff << 24) | (v >> 8);
+ }
+}
--- /dev/null
+package jp.sourceforge.stigmata.birthmarks.kgram;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import jp.sourceforge.stigmata.Birthmark;
+import jp.sourceforge.stigmata.BirthmarkContext;
+import jp.sourceforge.stigmata.birthmarks.BirthmarkExtractVisitor;
+
+import org.objectweb.asm.ClassVisitor;
+import org.objectweb.asm.MethodVisitor;
+
+/**
+ *
+ * @author Haruaki TAMADA
+ */
+public class KGramBasedBirthmarkExtractVisitor extends BirthmarkExtractVisitor{
+ private int kvalue;
+ private List<Integer> opcodes = new ArrayList<Integer>();
+
+ public KGramBasedBirthmarkExtractVisitor(ClassVisitor visitor,
+ Birthmark birthmark, BirthmarkContext context){
+ super(visitor, birthmark, context);
+ }
+
+ public int getKValue(){
+ return kvalue;
+ }
+
+ public void setKValue(int kvalue){
+ this.kvalue = kvalue;
+ }
+
+ @Override
+ public void visitEnd(){
+ KGramBuilder builder = KGramBuilder.getInstance();
+ KGram<Integer>[] kgrams = builder.<Integer>buildKGram(
+ opcodes, getKValue()
+ );
+
+ for(KGram<Integer> kgram: kgrams){
+ addElement(new KGramBasedBirthmarkElement<Integer>(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;
+ }
+}
--- /dev/null
+package jp.sourceforge.stigmata.birthmarks.kgram;
+
+import jp.sourceforge.stigmata.Birthmark;
+import jp.sourceforge.stigmata.BirthmarkContext;
+import jp.sourceforge.stigmata.BirthmarkElement;
+import jp.sourceforge.stigmata.ExtractionUnit;
+import jp.sourceforge.stigmata.birthmarks.ASMBirthmarkExtractor;
+import jp.sourceforge.stigmata.birthmarks.BirthmarkExtractVisitor;
+import jp.sourceforge.stigmata.spi.BirthmarkService;
+
+import org.objectweb.asm.ClassWriter;
+
+/**
+ * @author Haruaki TAMADA
+ */
+public class KGramBasedBirthmarkExtractor extends ASMBirthmarkExtractor{
+ private int kvalue = 4;
+
+ public KGramBasedBirthmarkExtractor(BirthmarkService 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;
+ }
+
+ @Override
+ public ExtractionUnit[] getAcceptableUnits(){
+ return new ExtractionUnit[] {
+ ExtractionUnit.CLASS, ExtractionUnit.PACKAGE,
+ ExtractionUnit.ARCHIVE,
+ };
+ }
+
+
+ @Override
+ public BirthmarkElement buildElement(String value) {
+ value = value.trim();
+ if(value.startsWith("{") && value.endsWith("}")){
+ String[] param =
+ value.substring(1, value.length() - 1).split(", *");
+ KGram<Integer> kgram = new KGram<Integer>(param.length);
+ for(int i = 0; i < param.length; i++){
+ kgram.set(i, new Integer(param[i].trim()));
+ }
+ return new KGramBasedBirthmarkElement<Integer>(kgram);
+ }
+ return null;
+ }
+}
--- /dev/null
+package jp.sourceforge.stigmata.birthmarks.kgram;
+
+import jp.sourceforge.stigmata.BirthmarkExtractor;
+import jp.sourceforge.stigmata.spi.BirthmarkExtractorService;
+import jp.sourceforge.stigmata.spi.BirthmarkService;
+
+/**
+ * Birthmark Service Provider Interface.
+ *
+ * @author Haruaki TAMADA
+ */
+public class KGramBasedBirthmarkExtractorService
+ implements BirthmarkExtractorService{
+
+ /**
+ * returns a type of the birthmark this service provides.
+ */
+ @Override
+ public String getType(){
+ return "kgram";
+ }
+
+ /**
+ * returns a extractor for the birthmark of this service.
+ */
+ @Override
+ public BirthmarkExtractor getExtractor(BirthmarkService service){
+ return new KGramBasedBirthmarkExtractor(service);
+ }
+
+ @Override
+ public String getDescription(){
+ return "extract k-gram based birthmark";
+ }
+}
\ No newline at end of file
--- /dev/null
+package jp.sourceforge.stigmata.birthmarks.kgram;
+
+import jp.sourceforge.stigmata.BirthmarkComparator;
+import jp.sourceforge.stigmata.BirthmarkExtractor;
+import jp.sourceforge.stigmata.BirthmarkPreprocessor;
+import jp.sourceforge.stigmata.birthmarks.comparators.LogicalAndBirthmarkComparator;
+import jp.sourceforge.stigmata.spi.BirthmarkService;
+
+
+/**
+ *
+ *
+ *
+ * @author Haruaki TAMADA
+ */
+public class KGramBasedBirthmarkService implements BirthmarkService{
+ private BirthmarkComparator comparator =
+ new LogicalAndBirthmarkComparator(this);
+ private BirthmarkExtractor extractor =
+ new KGramBasedBirthmarkExtractor(this);
+
+ @Override
+ public String getType(){
+ return "kgram";
+ }
+
+ @Override
+ public String getDescription(){
+ return "k-gram based birthmark.";
+ }
+
+ @Override
+ public BirthmarkExtractor getExtractor(){
+ return extractor;
+ }
+
+ @Override
+ public BirthmarkComparator getComparator(){
+ return comparator;
+ }
+
+ @Override
+ public boolean isExperimental(){
+ return false;
+ }
+
+ @Override
+ public boolean isUserDefined(){
+ return false;
+ }
+
+ @Override
+ public BirthmarkPreprocessor getPreprocessor(){
+ return null;
+ }
+}
--- /dev/null
+package jp.sourceforge.stigmata.birthmarks.kgram;
+
+import java.util.LinkedHashSet;
+import java.util.List;
+import java.util.Set;
+
+/**
+ * @author Haruaki Tamada
+ */
+public class KGramBuilder{
+ private static final KGramBuilder builder = new KGramBuilder();
+
+ /**
+ * private constructor for singleton pattern.
+ */
+ private KGramBuilder(){
+ }
+
+ public static KGramBuilder getInstance(){
+ return builder;
+ }
+
+ @SuppressWarnings("unchecked")
+ public <T> KGram<T>[] buildKGram(T[] values, int kvalue){
+ Set<KGram<T>> kgrams = new LinkedHashSet<KGram<T>>();
+
+ if(values.length >= kvalue){
+ int max = values.length - (kvalue - 1);
+ for(int i = 0; i < max; i++){
+ KGram<T> kgram = new KGram<T>(kvalue);
+ for(int j = 0; j < kvalue; j++){
+ kgram.set(j, values[i + j]);
+ }
+ kgrams.add(kgram);
+ }
+ }
+ return kgrams.toArray(new KGram[kgrams.size()]);
+ }
+
+ @SuppressWarnings("unchecked")
+ public <T> KGram<T>[] buildKGram(List<T> values, int kvalue){
+ Set<KGram<T>> kgrams = new LinkedHashSet<KGram<T>>();
+
+ if(values.size() >= kvalue){
+ int max = values.size() - (kvalue - 1);
+ for(int i = 0; i < max; i++){
+ KGram<T> kgram = new KGram<T>(kvalue);
+ for(int j = 0; j < kvalue; j++){
+ kgram.set(j, values.get(i + j));
+ }
+ kgrams.add(kgram);
+ }
+ }
+ return kgrams.toArray(new KGram[kgrams.size()]);
+ }
+}
\ No newline at end of file
--- /dev/null
+package jp.sourceforge.stigmata.birthmarks.kgram;
+
+import java.util.List;
+
+import org.objectweb.asm.Label;
+import org.objectweb.asm.MethodVisitor;
+import org.objectweb.asm.Opcodes;
+
+/**
+ *
+ * @author Haruaki TAMADA
+ */
+public class OpcodeExtractionMethodVisitor extends MethodVisitor{
+ private List<Integer> opcodes;
+
+ public OpcodeExtractionMethodVisitor(MethodVisitor visitor,
+ List<Integer> opcodes){
+ super(Opcodes.ASM4, 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);
+ }
+}
--- /dev/null
+jp.sourceforge.stigmata.birthmarks.kgram.KGramBasedBirthmarkExtractorService
--- /dev/null
+jp.sourceforge.stigmata.birthmarks.kgram.KGramBasedBirthmarkService
--- /dev/null
+package jp.sourceforge.stigmata.birthmarks.kgram;
+
+import org.junit.Assert;
+import org.junit.Before;
+import org.junit.Test;
+
+/**
+ *
+ * @author Haruaki Tamada
+ */
+public class KGramTest{
+ private String[] plainValues;
+ private String[] complexValues;
+
+ @Before
+ public void buildKGrams(){
+ plainValues = new String[] { "a", "b", "c", "d", "e", "f", "g", };
+ complexValues = new String[] { "a", "b", "r", "a", "c", "a", "d", "a", "b", "r", "a", };
+ }
+
+ @Test
+ public void checkPlainKGram(){
+ KGram<String>[] kgrams = KGramBuilder.getInstance().buildKGram(plainValues, 4);
+ Assert.assertEquals(4, kgrams.length);
+
+ Assert.assertEquals(4, kgrams[0].getKValue());
+ Assert.assertEquals(4, kgrams[1].getKValue());
+ Assert.assertEquals(4, kgrams[2].getKValue());
+ Assert.assertEquals(4, kgrams[3].getKValue());
+
+ Assert.assertArrayEquals(new String[] { "a", "b", "c", "d", }, kgrams[0].toArray());
+ Assert.assertArrayEquals(new String[] { "b", "c", "d", "e", }, kgrams[1].toArray());
+ Assert.assertArrayEquals(new String[] { "c", "d", "e", "f", }, kgrams[2].toArray());
+ Assert.assertArrayEquals(new String[] { "d", "e", "f", "g", }, kgrams[3].toArray());
+ }
+
+ @Test
+ public void checkPlainKGram2(){
+ KGram<String>[] kgrams = KGramBuilder.getInstance().buildKGram(plainValues, 3);
+ Assert.assertEquals(5, kgrams.length);
+
+ Assert.assertEquals(3, kgrams[0].getKValue());
+ Assert.assertEquals(3, kgrams[1].getKValue());
+ Assert.assertEquals(3, kgrams[2].getKValue());
+ Assert.assertEquals(3, kgrams[3].getKValue());
+ Assert.assertEquals(3, kgrams[4].getKValue());
+
+ Assert.assertArrayEquals(new String[] { "a", "b", "c", }, kgrams[0].toArray());
+ Assert.assertArrayEquals(new String[] { "b", "c", "d", }, kgrams[1].toArray());
+ Assert.assertArrayEquals(new String[] { "c", "d", "e", }, kgrams[2].toArray());
+ Assert.assertArrayEquals(new String[] { "d", "e", "f", }, kgrams[3].toArray());
+ Assert.assertArrayEquals(new String[] { "e", "f", "g", }, kgrams[4].toArray());
+ }
+
+ @Test
+ public void checkComplexKGram(){
+ KGram<String>[] kgrams = KGramBuilder.getInstance().buildKGram(complexValues, 3);
+
+ Assert.assertEquals(7, kgrams.length);
+
+ Assert.assertArrayEquals(new String[] { "a", "b", "r", }, kgrams[0].toArray());
+ Assert.assertArrayEquals(new String[] { "b", "r", "a", }, kgrams[1].toArray());
+ Assert.assertArrayEquals(new String[] { "r", "a", "c", }, kgrams[2].toArray());
+ Assert.assertArrayEquals(new String[] { "a", "c", "a", }, kgrams[3].toArray());
+ Assert.assertArrayEquals(new String[] { "c", "a", "d", }, kgrams[4].toArray());
+ Assert.assertArrayEquals(new String[] { "a", "d", "a", }, kgrams[5].toArray());
+ Assert.assertArrayEquals(new String[] { "d", "a", "b", }, kgrams[6].toArray());
+ // following kgram is appeared in above.
+ // assertEquals(new String[] { "a", "b", "r", }, kgrams[0].toArray());
+ // assertEquals(new String[] { "b", "r", "a", }, kgrams[1].toArray());
+ }
+}
--- /dev/null
+public class HelloWorld{
+ public static void main(String[] args){
+ System.out.println("Hello World");
+ }
+}
+
--- /dev/null
+target
+.DS_Store
+.class
+.classpath
+.settings
+.project
+.djunitplugin
+*~
--- /dev/null
+<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
+ xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
+
+ <parent>
+ <artifactId>stigmata-plugins</artifactId>
+ <groupId>jp.sourceforge.stigmata</groupId>
+ <version>4.0-SNAPSHOT</version>
+ </parent>
+
+ <modelVersion>4.0.0</modelVersion>
+ <groupId>jp.sourceforge.stigmata.plugins</groupId>
+ <artifactId>osb</artifactId>
+ <name>Operand Stack Behaviors Birthmark</name>
+ <version>1.0-SNAPSHOT</version>
+ <packaging>jar</packaging>
+ <url>http://stigmata.sourceforge.jp/plugins/osb/</url>
+
+ <licenses>
+ <license>
+ <name>The Apache License, Version 2</name>
+ <url>http://www.apache.org/licenses/LICENSE-2.0.txt</url>
+ <distribution>repo</distribution>
+ </license>
+ </licenses>
+
+ <developers>
+ <developer>
+ <id>iwama</id>
+ <name>Fumiya Iwama</name>
+ <organization>Kyoto Sangyo University</organization>
+ <roles>
+ <role>developer</role>
+ </roles>
+ <timezone>-9</timezone>
+ </developer>
+ <developer>
+ <id>obatake</id>
+ <name>Ryota Obatake</name>
+ <organization>Kyoto Sangyo University</organization>
+ <roles>
+ <role>developer</role>
+ </roles>
+ <timezone>-9</timezone>
+ </developer>
+ <developer>
+ <id>kataoka</id>
+ <name>Akinori Kataoka</name>
+ <organization>Kyoto Sangyo University</organization>
+ <roles>
+ <role>developer</role>
+ </roles>
+ <timezone>-9</timezone>
+ </developer>
+ <developer>
+ <id>kitano</id>
+ <name>Takayuki Kitano</name>
+ <organization>Kyoto Sangyo University</organization>
+ <roles>
+ <role>developer</role>
+ </roles>
+ <timezone>-9</timezone>
+ </developer>
+ </developers>
+
+ <repositories>
+ <repository>
+ <id>tamadalab-intra-repo</id>
+ <url>http://diamond.cse.kyoto-su.ac.jp/maven2</url>
+ </repository>
+ </repositories>
+
+ <dependencies>
+ <dependency>
+ <groupId>jp.sourceforge.stigmata</groupId>
+ <artifactId>cflib</artifactId>
+ <version>2.0-SNAPSHOT</version>
+ <scope>compile</scope>
+ </dependency>
+ </dependencies>
+
+ <build>
+ <plugins>
+ <plugin>
+ <groupId>org.apache.maven.plugins</groupId>
+ <artifactId>maven-site-plugin</artifactId>
+ <version>3.0</version>
+ <configuration>
+ <locale>ja</locale>
+ <inputEncoding>utf-8</inputEncoding>
+ <outputEncoding>utf-8</outputEncoding>
+ </configuration>
+ </plugin>
+ </plugins>
+ </build>
+
+ <reporting>
+ <plugins>
+ <plugin>
+ <groupId>org.apache.maven.plugins</groupId>
+ <artifactId>maven-javadoc-plugin</artifactId>
+ <version>2.7</version>
+ <configuration>
+ <charset>utf-8</charset>
+ <encoding>utf-8</encoding>
+ <docencoding>utf-8</docencoding>
+ </configuration>
+ </plugin>
+ <plugin>
+ <groupId>org.apache.maven.plugins</groupId>
+ <artifactId>maven-surefire-report-plugin</artifactId>
+ <version>2.6</version>
+ </plugin>
+ <plugin>
+ <groupId>org.codehaus.mojo</groupId>
+ <artifactId>cobertura-maven-plugin</artifactId>
+ <version>2.4</version>
+ <configuration>
+ <formats>
+ <format>html</format>
+ </formats>
+ </configuration>
+ </plugin>
+ <plugin>
+ <groupId>org.apache.maven.plugins</groupId>
+ <artifactId>maven-checkstyle-plugin</artifactId>
+ <version>2.6</version>
+ </plugin>
+ </plugins>
+ </reporting>
+</project>
--- /dev/null
+package jp.sourceforge.stigmata.birthmarks.osb;
+
+import jp.sourceforge.stigmata.cflib.Opcode;
+
+/**
+ * "opcode"と"そのopcode実行時のオペランドスタックの深さ"を対応付けするクラス
+ *
+ * @author Fumiya Iwama
+ * @author Ryouta Obatake
+ * @author Akinori Kataoka
+ * @author Takayuki Kitano
+ */
+public class CurrentDepth{
+ private Opcode opcode;
+ private int depth;
+
+ public CurrentDepth(int depth, Opcode opcode){
+ this.depth = depth;
+ this.opcode = opcode;
+ }
+
+ public int getDepth(){
+ return depth;
+ }
+
+ public Opcode getOpcode(){
+ return opcode;
+ }
+
+ @Override
+ public String toString(){
+ return String.format(opcode.getName() + "(" + depth+ ")" );//出力部分に影響
+ }
+}
--- /dev/null
+package jp.sourceforge.stigmata.birthmarks.osb;\r
+\r
+/**\r
+ * LCS (Longest Common Subsequence; 最長共通部分列)の計算機.\r
+ * 与えられた型 T の配列2つから最長共通部分列を見つけ,長さを返す.\r
+ * \r
+ * @author Haruaki Tamada\r
+ */\r
+public class LCSCalculator<T>{\r
+ /**\r
+ * elementA と elementB の最長共通部分列の長さを返す.\r
+ * 配列の要素はnullを許容する.両方の要素がnullの場合は一致するとみなし,\r
+ * 片一方の要素のみがnullの場合は,一致しないとする.\r
+ * @param elementA 最長共通部分列の長さを計算する集合1\r
+ * @param elementB \r
+ * @return 最長共通部分列の長さ\r
+ * @exception NullPointerException 与えらえた配列のどちらか,もしくは両方が null の場合.\r
+ */\r
+ public int calculate(T[] elementA, T[] elementB){\r
+ if(elementA == null || elementB == null){\r
+ throw new NullPointerException();\r
+ }\r
+ int[][] table = new int[elementA.length + 1][elementB.length + 1];\r
+ for(int i = 0; i <= elementA.length; i++){\r
+ for(int j = 0; j <= elementB.length; j++){\r
+ if(i == 0 || j == 0){\r
+ table[i][j] = 0;\r
+ }\r
+ else if((elementA[i - 1] == null && elementB[j - 1] == null) ||\r
+ elementA[i - 1] != null && elementA[i - 1].equals(elementB[j - 1])){\r
+ table[i][j] = max(table[i - 1][j - 1] + 1, table[i - 1][j], table[i][j - 1]);\r
+ }\r
+ else{\r
+ table[i][j] = max(table[i - 1][j - 1], table[i - 1][j], table[i][j - 1]);\r
+ }\r
+ }\r
+ }\r
+ return table[elementA.length][elementB.length];\r
+ }\r
+\r
+ /**\r
+ * 与えられた3つの整数値のうち,一番大きな値を返す.\r
+ * 全て正の数が与えらえるものとする.\r
+ */\r
+ private int max(int value1, int value2, int value3){\r
+ assert value1 >= 0;\r
+ assert value2 >= 0;\r
+ assert value3 >= 0;\r
+\r
+ int max = value1;\r
+ if(max < value2){\r
+ max = value2;\r
+ }\r
+ if(max < value3){\r
+ max = value3;\r
+ }\r
+ return max;\r
+ }\r
+}\r
--- /dev/null
+package jp.sourceforge.stigmata.birthmarks.osb;
+
+import jp.sourceforge.stigmata.Birthmark;
+import jp.sourceforge.stigmata.BirthmarkContext;
+import jp.sourceforge.stigmata.BirthmarkElement;
+import jp.sourceforge.stigmata.birthmarks.comparators.AbstractBirthmarkComparator;
+import jp.sourceforge.stigmata.birthmarks.osb.hungarian.CostMatrix;
+import jp.sourceforge.stigmata.birthmarks.osb.hungarian.HungarianMethod;
+import jp.sourceforge.stigmata.spi.BirthmarkService;
+
+/**
+ *
+ * @author Fumiya Iwama
+ * @author Ryouta Obatake
+ * @author Akinori Kataoka
+ * @author Takayuki Kitano
+ */
+public class OperandStackBehaviorsBirthmarkComparator extends AbstractBirthmarkComparator{
+ public OperandStackBehaviorsBirthmarkComparator(BirthmarkService spi){
+ super(spi);
+ }
+
+ @Override
+ public double compare(Birthmark b1, Birthmark b2, BirthmarkContext context){
+ BirthmarkElement[] elementsA = b1.getElements();
+ BirthmarkElement[] elementsB = b2.getElements();
+
+ //両方0だったら(片方でも0だったら、return0)
+ if(elementsA.length != 0 && elementsA.length != 0){
+ double[][] sim = createMatrix(elementsA,elementsB);
+ // matchには、類似度の合計値が最大となる値が入る
+ double match = calculateMatch(sim);
+ // BehaviorSetのBehaviorの数のうち、大きい方を max に代入
+ int max = Math.max(elementsA.length, elementsB.length);
+
+ return match / max;//Similarityを返す
+ }
+ else{
+ return 0;
+ }
+ }
+
+ public double compare(BirthmarkElement element1, BirthmarkElement element2){
+ if(element1 instanceof OperandStackBehaviorsBirthmarkElement &&
+ element2 instanceof OperandStackBehaviorsBirthmarkElement){
+ return ((OperandStackBehaviorsBirthmarkElement)element1).getSimilarity(
+ (OperandStackBehaviorsBirthmarkElement)element2
+ );
+ }
+ throw new IllegalArgumentException("only OperandStackBehaviorBirthmarkElement");
+ }
+
+ protected double[][] createMatrix(BirthmarkElement[] elementsA, BirthmarkElement[] elementsB){
+ double[][] matrix = new double[elementsA.length][elementsB.length];//simは実数だからdouble
+ for(int i = 0; i < elementsA.length; i++){
+ for(int j = 0; j < elementsB.length; j++){
+ OperandStackBehaviorsBirthmarkElement osb1 = (OperandStackBehaviorsBirthmarkElement)elementsA[i];
+ OperandStackBehaviorsBirthmarkElement osb2 = (OperandStackBehaviorsBirthmarkElement)elementsB[j];
+ matrix[i][j] = osb1.getSimilarity(osb2);
+ }
+ }
+ return matrix;
+ }
+
+ /**
+ * ハンガリアン法を使い,類似度を求める.
+ * @param matrixArray Birthmarkの要素間の類似度をまとめた2次元配列.
+ * @return 類似度の和が最大となるよう組み合わせた値.
+ */
+ protected double calculateMatch(double[][] matrixArray){
+ CostMatrix matrix = new CostMatrix(matrixArray, true);
+ HungarianMethod method = new HungarianMethod(matrix);
+
+ return method.solve();
+ }
+}
\ No newline at end of file
--- /dev/null
+package jp.sourceforge.stigmata.birthmarks.osb;
+
+import jp.sourceforge.stigmata.Birthmark;
+import jp.sourceforge.stigmata.BirthmarkContext;
+import jp.sourceforge.stigmata.BirthmarkElement;
+import jp.sourceforge.stigmata.spi.BirthmarkService;
+
+/**
+ *
+ * @author Fumiya Iwama
+ * @author Ryouta Obatake
+ * @author Akinori Kataoka
+ * @author Takayuki Kitano
+ */
+public class OperandStackBehaviorsBirthmarkContainmentCalculator extends OperandStackBehaviorsBirthmarkComparator{
+ public OperandStackBehaviorsBirthmarkContainmentCalculator(BirthmarkService spi){
+ super(spi);
+ }
+
+ @Override
+ public double compare(Birthmark b1, Birthmark b2, BirthmarkContext context){
+ BirthmarkElement[] elementsA = b1.getElements();
+ BirthmarkElement[] elementsB = b2.getElements();
+
+ // 片方でも0だったら、return0
+ if(elementsA.length != 0 && elementsB.length != 0){
+ double[][] sim = createMatrix(elementsA, elementsB);
+ // matchには、類似度の合計値が最大となる値が入る
+ double match = calculateMatch(sim);
+ // Similarityを返す
+ return match / elementsA.length;
+ }
+ else{
+ return 0;
+ }
+
+ }
+}
\ No newline at end of file
--- /dev/null
+package jp.sourceforge.stigmata.birthmarks.osb;
+
+import jp.sourceforge.stigmata.BirthmarkComparator;
+import jp.sourceforge.stigmata.BirthmarkExtractor;
+import jp.sourceforge.stigmata.BirthmarkPreprocessor;
+import jp.sourceforge.stigmata.spi.BirthmarkService;
+
+/**
+ * Operand Stack Behaviors birthmark.
+ *
+ * @author Fumiya Iwama
+ * @author Ryouta Obatake
+ * @author Akinori Kataoka
+ * @author Takayuki Kitano
+ */
+public class OperandStackBehaviorsBirthmarkContainmentService implements BirthmarkService {
+ private BirthmarkExtractor extractor =
+ new OperandStackBehaviorsBirthmarkExtractor(this);
+ private BirthmarkComparator comparator =
+ new OperandStackBehaviorsBirthmarkContainmentCalculator(this);
+
+ @Override
+ public String getDescription(){
+ return "Operand stack behaviors birthmark (containment)";
+ }
+
+ @Override
+ public boolean isUserDefined(){
+ return false;
+ }
+ @Override
+ public boolean isExperimental(){
+ return false;
+ }
+
+ @Override
+ public String getType(){
+ return "osb_containment";
+ }
+
+ @Override
+ public BirthmarkComparator getComparator(){
+ return comparator;
+ }
+
+ @Override
+ public BirthmarkExtractor getExtractor(){
+ return extractor;
+ }
+
+ @Override
+ public BirthmarkPreprocessor getPreprocessor(){
+ return null;
+ }
+}
--- /dev/null
+package jp.sourceforge.stigmata.birthmarks.osb;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Iterator;
+import java.util.List;
+
+import jp.sourceforge.stigmata.BirthmarkElement;
+import jp.sourceforge.stigmata.cflib.Opcode;
+
+/**
+ * Operand Stack Behavior バースマークの要素を表すクラス.
+ *
+ * @author Fumiya Iwama
+ * @author Ryouta Obatake
+ * @author Akinori Kataoka
+ * @author Takayuki Kitano
+ */
+public class OperandStackBehaviorsBirthmarkElement extends BirthmarkElement implements Iterable<Opcode>{
+ private static final long serialVersionUID = 7965456413167854L;
+
+ private static String getStringRepresentation(Opcode[] opcodes){//出力部分
+ StringBuilder builder = new StringBuilder();
+ for(int i = 0; i < opcodes.length; i++){
+ if(i != 0){
+ builder.append(", ");
+ }
+ builder.append(opcodes[i].getOpcode());
+ }
+ return new String(builder);
+ }
+
+ private LCSCalculator<Opcode.Category> calculator = new LCSCalculator<Opcode.Category>();
+ private transient Opcode.Category[] elements;
+
+ private List<Opcode> list = new ArrayList<Opcode>();
+
+ public OperandStackBehaviorsBirthmarkElement(Opcode[] opcodes){
+ super(getStringRepresentation(opcodes));
+ for(Opcode opcode: opcodes){
+ list.add(opcode);
+ }
+ elements = null;
+ }
+
+ private Opcode.Category[] getCategories(){
+ if(elements == null){
+ Opcode.Category[] categories = new Opcode.Category[getLength()];
+
+ int index = 0;
+ for(Opcode opcode: this){
+ categories[index] = opcode.getCategory();
+ index++;
+ }
+ this.elements = categories;
+ }
+ return elements;
+ }
+
+ public Opcode.Category getCategory(int index){
+ return getOpcode(index).getCategory();
+ }
+
+ public int getLength(){
+ return list.size();
+ }
+
+ public Opcode getOpcode(int index){
+ return list.get(index);
+ }
+
+ /**
+ * calculate similarity between two birthmark elements.
+ *
+ */
+ public double getSimilarity(OperandStackBehaviorsBirthmarkElement element){
+ Opcode.Category[] elementA = getCategories();
+ Opcode.Category[] elementB = element.getCategories();
+
+ double lcs = calculator.calculate(elementA, elementB);
+ return lcs / (elementA.length + elementB.length - lcs);
+ }
+
+ @Override
+ public Iterator<Opcode> iterator(){
+ return Collections.unmodifiableList(list).iterator();
+ }
+}
\ No newline at end of file
--- /dev/null
+package jp.sourceforge.stigmata.birthmarks.osb;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+import jp.sourceforge.stigmata.Birthmark;
+import jp.sourceforge.stigmata.BirthmarkContext;
+import jp.sourceforge.stigmata.BirthmarkElement;
+import jp.sourceforge.stigmata.ExtractionUnit;
+import jp.sourceforge.stigmata.birthmarks.ASMBirthmarkExtractor;
+import jp.sourceforge.stigmata.birthmarks.BirthmarkExtractVisitor;
+import jp.sourceforge.stigmata.cflib.BirthmarkElementBuilder;
+import jp.sourceforge.stigmata.cflib.LabelOpcode;
+import jp.sourceforge.stigmata.cflib.Opcode;
+import jp.sourceforge.stigmata.cflib.OpcodeExtractVisitor;
+import jp.sourceforge.stigmata.cflib.OpcodeManager;
+import jp.sourceforge.stigmata.spi.BirthmarkService;
+
+import org.objectweb.asm.ClassWriter;
+import org.objectweb.asm.Label;
+
+/**
+ * Operand Stack Behavior を抽出するためのクラス.
+ *
+ * @author Fumiya Iwama
+ * @author Ryouta Obatake
+ * @author Akinori Kataoka
+ * @author Takayuki Kitano
+ */
+public class OperandStackBehaviorsBirthmarkExtractor extends ASMBirthmarkExtractor{
+
+ public OperandStackBehaviorsBirthmarkExtractor(BirthmarkService service){
+ super(service);
+ }
+
+ @Override
+ public BirthmarkExtractVisitor createExtractVisitor(
+ ClassWriter writer, Birthmark birthmark,
+ BirthmarkContext context){
+
+ return new OpcodeExtractVisitor(writer, birthmark, context, new OSBBirthmarkElementBuilder());
+ }
+
+ @Override
+ public ExtractionUnit[] getAcceptableUnits(){
+ return new ExtractionUnit[] {
+ ExtractionUnit.CLASS,
+ };
+ }
+
+ private static class OSBBirthmarkElementBuilder implements BirthmarkElementBuilder{
+ @Override
+ public BirthmarkElement[] buildElements(List<Opcode> opcodes,
+ BirthmarkContext context){
+ List<CurrentDepth> pattern = buildStackPattern(opcodes, context);
+ List<BirthmarkElement> elements = new ArrayList<BirthmarkElement>();
+
+ List<Opcode> subPattern = new ArrayList<Opcode>();
+ for(CurrentDepth depth: pattern){
+ subPattern.add(depth.getOpcode());
+ if(depth.getDepth() == 0){//深さが0になるごとに、behaviorを区切る
+ elements.add(new OperandStackBehaviorsBirthmarkElement(
+ subPattern.toArray(new Opcode[subPattern.size()])
+ ));
+ subPattern.clear();
+ }
+ }
+
+ if(subPattern.size() != 0){//これで無駄な空白を除去
+ elements.add(new OperandStackBehaviorsBirthmarkElement(
+ subPattern.toArray(new Opcode[subPattern.size()])
+ ));
+ }
+
+ return elements.toArray(new BirthmarkElement[elements.size()]);
+ }
+
+ private List<CurrentDepth> buildStackPattern(List<Opcode> opcodes, BirthmarkContext context){
+ Map<Label, Integer> tableMap = new HashMap<Label, Integer>();
+ List<CurrentDepth> pattern = new ArrayList<CurrentDepth>();
+
+ int currentDepth = 0;
+ Integer forwardedStatus = null;
+ for(Opcode opcode: opcodes){
+ if(opcode.getCategory() == Opcode.Category.TARGETER){
+ forwardedStatus =
+ tableMap.get(((LabelOpcode)opcode).getLabel());
+ }
+ else{
+ if(forwardedStatus == null){
+ currentDepth += opcode.getAct();
+ }
+ else{
+ currentDepth = forwardedStatus + opcode.getAct();
+ }
+ forwardedStatus = null;
+
+ pattern.add(new CurrentDepth(currentDepth, opcode));
+ if(opcode.getCategory() == Opcode.Category.BRANCH){
+ for(Label label: opcode.getLabels()){
+ tableMap.put(label, currentDepth);
+ }
+ }
+ }
+ }
+ return pattern;
+ }
+ }
+
+ @Override
+ public BirthmarkElement buildElement(String value){
+ OpcodeManager manager = OpcodeManager.getInstance();
+ String[] elements = value.split(", ");
+ Opcode[] opcodes = new Opcode[elements.length];
+ for(int i = 0; i < opcodes.length; i++){
+ opcodes[i] = manager.getOpcode(Integer.parseInt(elements[i]));
+ }
+ return new OperandStackBehaviorsBirthmarkElement(opcodes);
+ };
+}
--- /dev/null
+package jp.sourceforge.stigmata.birthmarks.osb;
+
+import jp.sourceforge.stigmata.BirthmarkComparator;
+import jp.sourceforge.stigmata.BirthmarkExtractor;
+import jp.sourceforge.stigmata.BirthmarkPreprocessor;
+import jp.sourceforge.stigmata.spi.BirthmarkService;
+
+/**
+ * Operand Stack Behaviors birthmark.
+ *
+ * @author Fumiya Iwama
+ * @author Ryouta Obatake
+ * @author Akinori Kataoka
+ * @author Takayuki Kitano
+ */
+public class OperandStackBehaviorsBirthmarkService implements BirthmarkService{
+ private BirthmarkExtractor extractor =
+ new OperandStackBehaviorsBirthmarkExtractor(this);
+ private BirthmarkComparator comparator =
+ new OperandStackBehaviorsBirthmarkComparator(this);
+
+ @Override
+ public String getDescription(){
+ return "Operand stack behaviors birthmark";
+ }
+
+ @Override
+ public boolean isUserDefined(){
+ return false;
+ }
+ @Override
+ public boolean isExperimental(){
+ return false;
+ }
+
+ @Override
+ public String getType(){
+ return "osb";
+ }
+
+ @Override
+ public BirthmarkComparator getComparator(){
+ return comparator;
+ }
+
+ @Override
+ public BirthmarkExtractor getExtractor(){
+ return extractor;
+ }
+
+ @Override
+ public BirthmarkPreprocessor getPreprocessor(){
+ return null;
+ }
+}
--- /dev/null
+package jp.sourceforge.stigmata.birthmarks.osb.hungarian;\r
+\r
+/**\r
+ * 2次元配列の特定のセルを表すクラス.\r
+ * このクラスのオブジェクトは,セルの行番号,列番号と,その値を保持する.\r
+ * \r
+ * @author Haruaki Tamada\r
+ */\r
+public class Cell{\r
+ public static final class EmptyCell extends Cell{\r
+ public EmptyCell(int i, int j){\r
+ super(Double.NaN, i, j);\r
+ }\r
+\r
+ public double getValue(){\r
+ throw new IllegalStateException();\r
+ }\r
+\r
+ public boolean isAvailable(){\r
+ return false;\r
+ }\r
+\r
+ public String toString(){\r
+ return String.format("(%d, %d): N/A", getX(), getY());\r
+ }\r
+ };\r
+ private int x, y;\r
+ private double value;\r
+\r
+ /**\r
+ * 値と場所を指定してオブジェクトを作成する.\r
+ * @param value 値\r
+ * @param i 行番号\r
+ * @param j 列番号\r
+ */\r
+ Cell(double value, int i, int j){\r
+ this.x = i;\r
+ this.y = j;\r
+ this.value = value;\r
+ }\r
+\r
+ public boolean isAvailable(){\r
+ return true;\r
+ }\r
+\r
+ /**\r
+ * 値を返す.\r
+ */\r
+ public double getValue(){\r
+ return value;\r
+ }\r
+\r
+ /**\r
+ * 行番号を返す.\r
+ */\r
+ public int getX(){\r
+ return x;\r
+ }\r
+\r
+ /**\r
+ * 列番号を返す.\r
+ */\r
+ public int getY(){\r
+ return y;\r
+ }\r
+\r
+ /**\r
+ * このオブジェクトの文字列表現を返す.\r
+ */\r
+ public String toString(){\r
+ return String.format("(%d, %d): %1.4g", getX(), getY(), getValue());\r
+ }\r
+}\r
--- /dev/null
+package jp.sourceforge.stigmata.birthmarks.osb.hungarian;\r
+\r
+/**\r
+ * ハンガリアン法により,最適解を見つけるためのコスト行列を表すクラス.\r
+ * \r
+ * @author tamada\r
+ */\r
+public class CostMatrix{\r
+ private static final double THRESHOLD = 1E-6;\r
+\r
+ private double[][] original;\r
+ private double[][] matrix;\r
+ private int size;\r
+ private boolean maxFlag;\r
+\r
+ /**\r
+ * 与えられた2次元配列の最小和の組み合わせを求めるためのオブジェクトを作成する.\r
+ * @param initMatrix\r
+ */\r
+ public CostMatrix(double[][] initMatrix){\r
+ this(initMatrix, false);\r
+ }\r
+\r
+ /**\r
+ * 与えられた2次元配列の最小和もしくは,最大和の組み合わせを求めるためのオブジェクトを作成する.\r
+ * \r
+ * @param initMatrix\r
+ * @param maxFlag trueの場合,最大和を求める.falseの場合,最小和を求める.\r
+ */\r
+ public CostMatrix(double[][] initMatrix, boolean maxFlag){\r
+ size = getSize(initMatrix);\r
+ initializeMatrix(size, initMatrix, maxFlag);\r
+ this.maxFlag = maxFlag;\r
+\r
+ if(maxFlag){\r
+ for(int i = 0; i < matrix.length; i++){\r
+ for(int j = 0; j < matrix[i].length; j++){\r
+ matrix[i][j] = 1d - matrix[i][j];\r
+ }\r
+ }\r
+ }\r
+ }\r
+\r
+ /**\r
+ * このオブジェクトが持つ2次元配列の組み合わせの最大和を求める場合,trueを返す.\r
+ * 最小和を求める場合,falseを返す.\r
+ * @return 最大和を求める場合,trueを返す.\r
+ */\r
+ public boolean isMax(){\r
+ return maxFlag;\r
+ }\r
+\r
+ /**\r
+ * このコスト配列の大きさを返す.\r
+ * もし,与えられた2次元配列の縦と横の長さが異なっていれば,\r
+ * 大きい方の値を返す.\r
+ * @return このコスト配列の大きさ\r
+ */\r
+ public int getSize(){\r
+ return size;\r
+ }\r
+\r
+ /**\r
+ * ハンガリアン法のステップ2に相当する.\r
+ * 与えられた行列を最小化する.\r
+ * \r
+ * 各行の要素から,その行の最小値を引き,\r
+ * その後,各列の各要素から,その列の最小値を引く.\r
+ */\r
+ public void minimize(){\r
+ for(int i = 0; i < matrix.length; i++){\r
+ double min = 1;\r
+ for(int j = 0; j < matrix[i].length; j++){\r
+ if(min > matrix[i][j]){\r
+ min = matrix[i][j];\r
+ }\r
+ }\r
+ for(int j = 0; j < matrix[i].length; j++){\r
+ matrix[i][j] = matrix[i][j] - min;\r
+ }\r
+ }\r
+\r
+ for(int i = 0; i < matrix[0].length; i++){\r
+ double min = 1;\r
+ for(int j = 0; j < matrix.length; j++){\r
+ if(min > matrix[j][i]){\r
+ min = matrix[j][i];\r
+ }\r
+ }\r
+ for(int j = 0; j < matrix.length; j++){\r
+ matrix[j][i] = matrix[j][i] - min;\r
+ }\r
+ }\r
+ }\r
+\r
+ /**\r
+ * 与えられた場所のセルを作成し,返す.\r
+ */\r
+ public Cell getCell(int i, int j){\r
+ return new Cell(getValue(i, j), i, j);\r
+ }\r
+\r
+ /**\r
+ * 与えられた場所の現在の値を返す.\r
+ */\r
+ public double getValue(int i, int j){\r
+ return matrix[i][j];\r
+ }\r
+\r
+ public boolean isZero(int i, int j){\r
+ return Math.abs(getValue(i, j)) < THRESHOLD;\r
+ }\r
+\r
+ public boolean isValidOriginal(int i, int j){\r
+ return i < original.length && j < original[0].length;\r
+ }\r
+\r
+ /**\r
+ * 与えられた場所の元の値を返す.\r
+ */\r
+ public double getOriginal(int i, int j){\r
+ return original[i][j];\r
+ }\r
+\r
+ /**\r
+ * 指定された場所の値を指定された値に設定する.\r
+ */\r
+ public void setValue(double value, int i, int j){\r
+ matrix[i][j] = value;\r
+ }\r
+\r
+ /**\r
+ * 2次元配列の初期化を行う.\r
+ * 縦と横の長さが異なる場合,大きな方に大きさを揃える.\r
+ */\r
+ private void initializeMatrix(int size, double[][] initMatrix, boolean maxFlag){\r
+ matrix = new double[size][size];\r
+ double initValue = 1d;\r
+ if(maxFlag){\r
+ initValue = 0d;\r
+ }\r
+ for(int i = 0; i < matrix.length; i++){\r
+ for(int j = 0; j < matrix[i].length; j++){\r
+ matrix[i][j] = initValue;\r
+ }\r
+ }\r
+\r
+ for(int i = 0; i < initMatrix.length; i++){\r
+ System.arraycopy(initMatrix[i], 0, matrix[i], 0, initMatrix[i].length);\r
+ }\r
+ original = new double[initMatrix.length][initMatrix[0].length];\r
+ for(int i = 0; i < initMatrix.length; i++){\r
+ System.arraycopy(initMatrix[i], 0, original[i], 0, initMatrix[i].length);\r
+ }\r
+ }\r
+\r
+ /**\r
+ * 2次元配列の大きさを計算し,返す.\r
+ * @param initMatrix\r
+ * @return\r
+ */\r
+ private int getSize(double[][] initMatrix){\r
+ int sizeX = initMatrix.length;\r
+ int sizeY = initMatrix[0].length;\r
+ int size = sizeX;\r
+ if(size < sizeY){\r
+ size = sizeY;\r
+ }\r
+ return size;\r
+ }\r
+\r
+ public synchronized String toString(boolean[] rows, boolean[] cols){\r
+ StringBuilder sb = new StringBuilder();\r
+ for(int i = 0; i < matrix.length; i++){\r
+ for(int j = 0; j < matrix[i].length; j++){\r
+ sb.append(String.format("%.3f ", matrix[i][j]));\r
+ }\r
+ sb.append(rows[i]);\r
+ sb.append(System.getProperty("line.separator"));\r
+ }\r
+ for(int j = 0; j < cols.length; j++){\r
+ sb.append(String.format("%5s ", cols[j]));\r
+ }\r
+ return new String(sb);\r
+ }\r
+\r
+ public synchronized String toString(){\r
+ StringBuilder sb = new StringBuilder();\r
+ for(int i = 0; i < matrix.length; i++){\r
+ for(int j = 0; j < matrix[i].length; j++){\r
+ sb.append(String.format("%.3f ", matrix[i][j]));\r
+ }\r
+ sb.append(System.getProperty("line.separator"));\r
+ }\r
+ return new String(sb);\r
+ }\r
+}\r
--- /dev/null
+package jp.sourceforge.stigmata.birthmarks.osb.hungarian;\r
+\r
+import java.util.ArrayList;\r
+import java.util.Collections;\r
+import java.util.Comparator;\r
+import java.util.List;\r
+\r
+/**\r
+ * <p>\r
+ * ハンガリアン法により,最小和の組み合わせを選択する計算機.\r
+ * ハンガリアン法は以下の手順により行われる.\r
+ * </p>\r
+ * <ul>\r
+ * <li>与えられた2次元配列の各列から,その列の最小値を引く.</li>\r
+ * <li>与えられた2次元配列の各行から,その行の最小値を引く.</li>\r
+ * <li>各行各列から,1つずつ0を選択できれば,その部分が最適な組み合わせであるため,そこで終了する.</li>\r
+ * <li>そうでない場合は,0の生成作業へと移る\r
+ * <ul>\r
+ * <li>1度に多くの0が消えるよう線を入れる.</li>\r
+ * <li>線で消されなかったセルの最小値<em>min</em>を求める.</li>\r
+ * <li>線で消されなかった全てのセルから,求めた最小値<em>min</em>を減算する.</li>\r
+ * </ul>\r
+ * </li>\r
+ * <li>最適な組み合わせを選択する.選択できれば終了.選択できなければ,もう一度0の生成作業を行う.</li>\r
+ * </ul>\r
+ */\r
+public class HungarianMethod{\r
+ private CostMatrix matrix;\r
+ private List<Cell> solutions = new ArrayList<Cell>();\r
+\r
+ public HungarianMethod(CostMatrix matrix){\r
+ this.matrix = matrix;\r
+ }\r
+\r
+ public synchronized Cell[] getSolutions(){\r
+ Collections.sort(solutions, new Comparator<Cell>(){\r
+ @Override\r
+ public int compare(Cell arg0, Cell arg1){\r
+ if(arg0.getX() < arg1.getX()){\r
+ return -1;\r
+ }\r
+ else{\r
+ return 1;\r
+ }\r
+ }\r
+ });\r
+ return solutions.toArray(new Cell[solutions.size()]);\r
+ }\r
+\r
+ public synchronized Line[] getLines(){\r
+ boolean[][] linedMatrix = new boolean[matrix.getSize()][matrix.getSize()];\r
+ List<Line> lines = getLines(matrix, linedMatrix);\r
+ \r
+ return lines.toArray(new Line[lines.size()]);\r
+ }\r
+\r
+ /**\r
+ * ハンガリアン法を解く.\r
+ * @return 最大和もしくは最小和.\r
+ * @see CostMatrix#isMax\r
+ */\r
+ public double solve(){\r
+ // step.1 \r
+ matrix.minimize();\r
+\r
+ boolean[][] linedMatrix = new boolean[matrix.getSize()][matrix.getSize()];\r
+ List<Line> lines = getLines(matrix, linedMatrix);\r
+ while(lines.size() < matrix.getSize()){\r
+ moreMinimize(matrix, lines, linedMatrix);\r
+ resetBooleanMatrix(linedMatrix);\r
+ lines = getLines(matrix, linedMatrix);\r
+ }\r
+ double solution = parseSolutions(matrix, lines);\r
+\r
+ return solution;\r
+ }\r
+\r
+ private void resetBooleanMatrix(boolean[][] matrix){\r
+ for(int i = 0; i < matrix.length; i++){\r
+ for(int j = 0; j < matrix[i].length; j++){\r
+ matrix[i][j] = false;\r
+ }\r
+ }\r
+ }\r
+\r
+ private double parseSolutions(CostMatrix matrix, List<Line> lines){\r
+ double solution = 0d;\r
+\r
+ boolean[][] solutionMatrix = new boolean[matrix.getSize()][matrix.getSize()];\r
+ solutions.clear();\r
+ while(solutions.size() < matrix.getSize()){\r
+ Cell cell = getSolution(matrix, solutionMatrix);\r
+ for(int i = 0; i < matrix.getSize(); i++){\r
+ solutionMatrix[cell.getX()][i] = true;\r
+ solutionMatrix[i][cell.getY()] = true;\r
+ }\r
+ if(cell.isAvailable()){\r
+ solution = solution + cell.getValue();\r
+ }\r
+ solutions.add(cell);\r
+ }\r
+ for(int i = solutions.size() - 1; i >= 0; i--){\r
+ if(!solutions.get(i).isAvailable()){\r
+ solutions.remove(i);\r
+ }\r
+ }\r
+ return solution;\r
+ }\r
+\r
+ private Cell getSolution(CostMatrix matrix, boolean[][] solutionMatrix){\r
+ for(int i = 0; i < matrix.getSize(); i++){\r
+ int count = 0;\r
+ int lastIndex = -1;\r
+ for(int j = 0; j < matrix.getSize(); j++){\r
+ if(matrix.isZero(i, j) && !solutionMatrix[i][j]){\r
+ count++;\r
+ lastIndex = j;\r
+ }\r
+ }\r
+ if(count == 1){\r
+ Cell cell;\r
+ if(matrix.isValidOriginal(i, lastIndex)){\r
+ cell = new Cell(matrix.getOriginal(i, lastIndex), i, lastIndex);\r
+ }\r
+ else{\r
+ cell = new Cell.EmptyCell(i, lastIndex);\r
+ }\r
+ return cell;\r
+ }\r
+ }\r
+ for(int j = 0; j < matrix.getSize(); j++){\r
+ int count = 0;\r
+ int lastIndex = -1;\r
+ for(int i = 0; i < matrix.getSize(); i++){\r
+ if(matrix.isZero(i, j) && !solutionMatrix[i][j]){\r
+ count++;\r
+ lastIndex = i;\r
+ }\r
+ }\r
+ if(count == 1){\r
+ Cell cell;\r
+ if(matrix.isValidOriginal(lastIndex, j)){\r
+ cell = new Cell(matrix.getOriginal(lastIndex, j), lastIndex, j);\r
+ }\r
+ else{\r
+ cell = new Cell.EmptyCell(lastIndex, j);\r
+ }\r
+ return cell;\r
+ }\r
+ }\r
+ for(int i = 0; i < matrix.getSize(); i++){\r
+ for(int j = 0; j < matrix.getSize(); j++){\r
+ if(matrix.isZero(i, j) && !solutionMatrix[i][j]){\r
+ Cell cell;\r
+ if(matrix.isValidOriginal(i, j)){\r
+ cell = new Cell(matrix.getOriginal(i, j), i, j);\r
+ }\r
+ else{\r
+ cell = new Cell.EmptyCell(i, j);\r
+ }\r
+ return cell;\r
+ }\r
+ }\r
+ }\r
+ return null;\r
+ }\r
+\r
+ private List<Line> getLines(CostMatrix matrix, boolean[][] linedMatrix){\r
+ List<Line> lines = new ArrayList<Line>();\r
+ List<Line> candidate;\r
+\r
+ while((candidate = getCandidateLines(matrix, linedMatrix)).size() > 0){\r
+ Line line = candidate.get(candidate.size() - 1);\r
+ lineOut(matrix, linedMatrix, line);\r
+ lines.add(line);\r
+ }\r
+ return lines;\r
+ }\r
+\r
+ /**\r
+ * 対象の2次元配列から,全ての線を取り出す.\r
+ * ただし,線には必ず0を含み,その0は既に引かれた線で選択されていないものとする.\r
+ * また,選択した線は,線に含まれる0の数,交差する線の数によりソートされる.\r
+ */\r
+ private List<Line> getCandidateLines(CostMatrix matrix, boolean[][] linedMatrix){\r
+ List<Line> candidateLines = new ArrayList<Line>();\r
+ for(int i = 0; i < matrix.getSize(); i++){\r
+ int count = 0;\r
+ int crossCount = 0;\r
+ for(int j = 0; j < matrix.getSize(); j++){\r
+ if(matrix.isZero(i, j) && !linedMatrix[i][j]){\r
+ count++;\r
+ }\r
+ if(linedMatrix[i][j]){\r
+ crossCount++;\r
+ }\r
+ }\r
+ if(count > 0){\r
+ candidateLines.add(new Line(i, count, crossCount, Line.Direction.ROW));\r
+ }\r
+ }\r
+ for(int j = 0; j < matrix.getSize(); j++){\r
+ int count = 0;\r
+ int crossCount = 0;\r
+ for(int i = 0; i < matrix.getSize(); i++){\r
+ if(matrix.isZero(i, j) && !linedMatrix[i][j]){\r
+ count++;\r
+ }\r
+ if(linedMatrix[i][j]){\r
+ crossCount++;\r
+ }\r
+ }\r
+ if(count > 0){\r
+ candidateLines.add(new Line(j, count, crossCount, Line.Direction.COLUMN));\r
+ }\r
+ }\r
+ Collections.sort(candidateLines);\r
+\r
+ return candidateLines;\r
+ }\r
+\r
+ private void lineOut(CostMatrix matrix, boolean[][] linedMatrix, Line line){\r
+ if(line.getDirection() == Line.Direction.COLUMN){\r
+ for(int i = 0; i < linedMatrix.length; i++){\r
+ linedMatrix[i][line.getIndex()] = true;\r
+ }\r
+ }\r
+ else{\r
+ for(int i = 0; i < linedMatrix[0].length; i++){\r
+ linedMatrix[line.getIndex()][i] = true;\r
+ }\r
+ }\r
+ }\r
+\r
+ private List<Cell> getCrossedLineCell(CostMatrix matrix, List<Line> lines){\r
+ List<Cell> cross = new ArrayList<Cell>();\r
+ for(int i = 0; i < lines.size() - 1; i++){\r
+ Line line1 = lines.get(i);\r
+ for(int j = 1; j < lines.size(); j++){\r
+ Line line2 = lines.get(j);\r
+ if(line1.getDirection() != line2.getDirection()){\r
+ int row = line1.getIndex();\r
+ int column = line2.getIndex();\r
+ if(line1.getDirection() == Line.Direction.COLUMN){\r
+ row = line2.getIndex();\r
+ column = line1.getIndex();\r
+ }\r
+ cross.add(matrix.getCell(row, column));\r
+ }\r
+ }\r
+ }\r
+ return cross;\r
+ }\r
+\r
+ public synchronized void reduceMatrix(Line[] lineArray){\r
+ List<Line> lines = new ArrayList<Line>();\r
+ boolean[][] linedMatrix = new boolean[matrix.getSize()][matrix.getSize()];\r
+ for(Line line: lineArray){\r
+ lines.add(line);\r
+ for(int i = 0; i < linedMatrix.length; i++){\r
+ if(line.getDirection() == Line.Direction.COLUMN){\r
+ linedMatrix[i][line.getIndex()] = true;\r
+ }\r
+ else{\r
+ linedMatrix[line.getIndex()][i] = true;\r
+ }\r
+ }\r
+ }\r
+ moreMinimize(matrix, lines, linedMatrix);\r
+ }\r
+\r
+ /**\r
+ * ハンガリアン法のステップ3, 4に相当する.\r
+ * 線の引かれていない箇所から,最小値を引く.\r
+ */\r
+ private void moreMinimize(CostMatrix matrix, List<Line> lines, boolean[][] linedMatrix){\r
+ List<Cell> cross = getCrossedLineCell(matrix, lines);\r
+\r
+ // 線が引かれていない部分から最小値を選択する.\r
+ double min = 1;\r
+ for(int i = 0; i < matrix.getSize(); i++){\r
+ for(int j = 0; j < matrix.getSize(); j++){\r
+ if(!linedMatrix[i][j] && min > matrix.getValue(i, j)){\r
+ min = matrix.getValue(i, j);\r
+ }\r
+ }\r
+ }\r
+\r
+ // 線が引かれていない箇所から,求めた最小値を減算する.\r
+ for(int i = 0; i < matrix.getSize(); i++){\r
+ for(int j = 0; j < matrix.getSize(); j++){\r
+ if(!linedMatrix[i][j]){\r
+ matrix.setValue(matrix.getValue(i, j) - min, i, j);\r
+ }\r
+ }\r
+ }\r
+ // 線が交わっている箇所は減算した値を足す.\r
+ for(Cell cell: cross){\r
+ matrix.setValue(\r
+ matrix.getValue(cell.getX(), cell.getY()) + min,\r
+ cell.getX(), cell.getY()\r
+ );\r
+ }\r
+ }\r
+}
\ No newline at end of file
--- /dev/null
+package jp.sourceforge.stigmata.birthmarks.osb.hungarian;\r
+\r
+/**\r
+ * ハンガリアン法で,2次元配列の特定個所に引く線を表すクラス.\r
+ * \r
+ * @author Haruaki Tamada\r
+ */\r
+public class Line implements Comparable<Line>{\r
+ public static enum Direction{\r
+ ROW, COLUMN;\r
+ };\r
+\r
+ private int index;\r
+ private int count;\r
+ private int crossCount;\r
+ private Direction direction = Direction.ROW;\r
+\r
+ /**\r
+ * オブジェクトを作成する.\r
+ * @param index 行もしくは列の番号を表す..\r
+ * @param count その行もしくは列に含まれる0の数.\r
+ * @param crossCount その行,もしくは列に既に引かれている線の数.\r
+ * @param direction 方向.\r
+ */\r
+ public Line(int index, int count, int crossCount, Direction direction){\r
+ this.index = index;\r
+ this.count = count;\r
+ this.crossCount = crossCount;\r
+ this.direction = direction;\r
+ }\r
+\r
+ /**\r
+ * 位置を返す.行か,列かは,{@link #getDirection() <code>getDirection()</code>}メソッドで決定される.\r
+ */\r
+ public int getIndex(){\r
+ return index;\r
+ }\r
+\r
+ /**\r
+ * 0の数を返す.\r
+ */\r
+ public int getCount(){\r
+ return count;\r
+ }\r
+\r
+ /**\r
+ * 方向を返す.\r
+ */\r
+ public Direction getDirection(){\r
+ return direction;\r
+ }\r
+\r
+ /**\r
+ * このオブジェクトを比較する.\r
+ * 0の数で比較する.ただし,0の数が同数であれば,交わっている線の数でも比較する.\r
+ * 0が多いほど,また,交わっている線が多いほど大きいとする.\r
+ */\r
+ @Override\r
+ public int compareTo(Line line){\r
+ if(getCount() < line.getCount()){\r
+ return -1;\r
+ }\r
+ else if(getCount() > line.getCount()){\r
+ return 1;\r
+ }\r
+ else{\r
+ if(crossCount < line.crossCount){\r
+ return -1;\r
+ }\r
+ if(crossCount > line.crossCount){\r
+ return 1;\r
+ }\r
+ return 0;\r
+ }\r
+ }\r
+\r
+ /**\r
+ * このオブジェクトの文字列表現を返す.\r
+ */\r
+ public String toString(){\r
+ return String.format("[index: %d, count: %d(%d) (%s)]", getIndex(), getCount(), crossCount, getDirection());\r
+ }\r
+}\r
--- /dev/null
+jp.sourceforge.stigmata.birthmarks.osb.OperandStackBehaviorsBirthmarkContainmentService
+jp.sourceforge.stigmata.birthmarks.osb.OperandStackBehaviorsBirthmarkService
--- /dev/null
+ ----\r
+ Introduction of OSB\r
+ ----\r
+ Haruaki Tamada\r
+ ----\r
+ 2011-02-28\r
+ ----\r
+\r
+OSB\r
+\r
+ OSB (Operand Stack Behaviors) Birthmark is defined by Lim et. al. in following article.\r
+\r
+ * Heewan Park, Hyun-il Lim, Seokwoo Choi and Taisook Han, ``A Static\r
+ Java Birthmark Based on Operand Stack Behaviors,'' In Proc. of 2008\r
+ International Conference on Information Security and Assurance,\r
+ pp.133-136, April 2008.\r
+\r
+ []\r
+\r
--- /dev/null
+<?xml version="1.0" encoding="utf-8"?>\r
+\r
+<project name="osb">\r
+ <bannerLeft>\r
+ <name>Operand Stack Behaviors Birthmark</name>\r
+ <href>http://stigmata.sourceforge.jp/plugins/osb/</href>\r
+ </bannerLeft>\r
+\r
+ <body>\r
+ <menu name="OSB" inherit="top">\r
+ <item name="Introduction" href="index.html"/>\r
+ </menu>\r
+\r
+ <menu ref="reports"/>\r
+ </body>\r
+</project>\r
--- /dev/null
+package jp.sourceforge.stigmata.birthmarks.osb;\r
+\r
+import org.junit.Assert;\r
+import org.junit.Before;\r
+import org.junit.Test;\r
+\r
+public class LCSCalculatorTest{\r
+ private LCSCalculator<String> calculator;\r
+\r
+ @Before\r
+ public void setUp(){\r
+ calculator = new LCSCalculator<String>();\r
+ }\r
+\r
+ @Test\r
+ public void testBasic(){\r
+ String[] elementA = new String[] { "load", "load", "add", "store", };\r
+ String[] elementB = new String[] { "load", "load", "mul", "load", "sub", "store", };\r
+\r
+ Assert.assertEquals(3, calculator.calculate(elementA, elementB));\r
+ Assert.assertEquals(3, calculator.calculate(elementB, elementA));\r
+ }\r
+\r
+ @Test\r
+ public void testNullElement(){\r
+ String[] elementA = new String[] { "load", "load", "add", null, };\r
+ String[] elementB = new String[] { "load", "load", "mul", "load", "sub", null, };\r
+\r
+ Assert.assertEquals(3, calculator.calculate(elementA, elementB));\r
+ }\r
+\r
+ @Test\r
+ public void testZeroLengthArray(){\r
+ String[] elementB = new String[] { "load", "load", "mul", "load", "sub", "store", };\r
+\r
+ Assert.assertEquals(0, calculator.calculate(new String[0], elementB));\r
+ }\r
+\r
+ @Test(expected=NullPointerException.class)\r
+ public void testNullCheck1(){\r
+ String[] elementB = new String[] { "load", "load", "mul", "load", "sub", "store", };\r
+\r
+ calculator.calculate(null, elementB);\r
+ }\r
+\r
+ @Test(expected=NullPointerException.class)\r
+ public void testNullCheck2(){\r
+ String[] elementA = new String[] { "load", "load", "add", "store", };\r
+\r
+ calculator.calculate(elementA, null);\r
+ }\r
+\r
+ @Test(expected=NullPointerException.class)\r
+ public void testNullCheck3(){\r
+ calculator.calculate(null, null);\r
+ }\r
+}\r
--- /dev/null
+package jp.sourceforge.stigmata.birthmarks.osb;\r
+\r
+import jp.sourceforge.stigmata.Birthmark;\r
+import jp.sourceforge.stigmata.BirthmarkExtractionFailedException;\r
+import junit.framework.Assert;\r
+\r
+import org.junit.Before;\r
+import org.junit.Test;\r
+\r
+public class OperandStackBehaviorsBirthmarkComparatorTest{\r
+ private OperandStackBehaviorsBirthmarkComparator comparator;\r
+ private OperandStackBehaviorsBirthmarkExtractor extractor;\r
+\r
+ @Before\r
+ public void setUp(){\r
+ OperandStackBehaviorsBirthmarkService service = new OperandStackBehaviorsBirthmarkService();\r
+ comparator = (OperandStackBehaviorsBirthmarkComparator)service.getComparator();\r
+ extractor = (OperandStackBehaviorsBirthmarkExtractor)service.getExtractor();\r
+ }\r
+\r
+ @Test\r
+ public void testBasic() throws BirthmarkExtractionFailedException{\r
+ Birthmark birthmark1 = extractor.extract(getClass().getResourceAsStream("/resources/Sample1.class"));\r
+ Birthmark birthmark2 = extractor.extract(getClass().getResourceAsStream("/resources/Sample2.class"));\r
+\r
+ Assert.assertEquals(7, birthmark1.getElementCount());\r
+ Assert.assertEquals(8, birthmark2.getElementCount());\r
+\r
+ Assert.assertEquals(7d / 8, comparator.compare(birthmark1, birthmark2, null), 1E-6);\r
+ }\r
+}\r
--- /dev/null
+package jp.sourceforge.stigmata.birthmarks.osb;\r
+\r
+import java.util.Iterator;\r
+\r
+import jp.sourceforge.stigmata.cflib.Opcode;\r
+import jp.sourceforge.stigmata.cflib.OpcodeManager;\r
+\r
+import org.junit.Assert;\r
+import org.junit.Before;\r
+import org.junit.Test;\r
+\r
+public class OperandStackBehaviorsBirthmarkElementTest{\r
+ private OperandStackBehaviorsBirthmarkElement element;\r
+\r
+ @Before\r
+ public void setUp(){\r
+ OpcodeManager manager = OpcodeManager.getInstance();\r
+ Opcode[] opcodes = new Opcode[4];\r
+ opcodes[0] = manager.getOpcode(27); // iload_1\r
+ opcodes[1] = manager.getOpcode(28); // iload_2\r
+ opcodes[2] = manager.getOpcode(96); // iadd\r
+ opcodes[3] = manager.getOpcode(62); // istore_3\r
+\r
+ element = new OperandStackBehaviorsBirthmarkElement(opcodes);\r
+ }\r
+\r
+ @Test\r
+ public void testSimilarity(){\r
+ OpcodeManager manager = OpcodeManager.getInstance();\r
+ OperandStackBehaviorsBirthmarkElement element2 = new OperandStackBehaviorsBirthmarkElement(\r
+ new Opcode[] {\r
+ manager.getOpcode(27), // iload_1\r
+ manager.getOpcode(28), // iload_2\r
+ manager.getOpcode(104), // imul\r
+ manager.getOpcode(29), // iload_3\r
+ manager.getOpcode(100), // isub\r
+ manager.getOpcode(54), // istore\r
+ }\r
+ );\r
+\r
+ Assert.assertEquals(3d/7d, element.getSimilarity(element2), 1E-5);\r
+ Assert.assertEquals(3d/7d, element2.getSimilarity(element), 1E-5);\r
+ }\r
+\r
+ @Test\r
+ public void testBasic(){\r
+ Assert.assertEquals(4, element.getLength());\r
+ Assert.assertEquals("27, 28, 96, 62", element.toString());\r
+ }\r
+\r
+ @Test\r
+ public void testCategoryCheck(){\r
+ Assert.assertEquals(Opcode.Category.LOAD, element.getCategory(0));\r
+ Assert.assertEquals(Opcode.Category.LOAD, element.getCategory(1));\r
+ Assert.assertEquals(Opcode.Category.ADD, element.getCategory(2));\r
+ Assert.assertEquals(Opcode.Category.STORE, element.getCategory(3));\r
+ }\r
+\r
+ @Test\r
+ public void testOpcodeCheck(){\r
+ OpcodeManager manager = OpcodeManager.getInstance();\r
+ Assert.assertEquals(manager.getOpcode(27), element.getOpcode(0));\r
+ Assert.assertEquals(manager.getOpcode(28), element.getOpcode(1));\r
+ Assert.assertEquals(manager.getOpcode(96), element.getOpcode(2));\r
+ Assert.assertEquals(manager.getOpcode(62), element.getOpcode(3));\r
+ }\r
+\r
+ @Test\r
+ public void testOpcodeCheck2(){\r
+ OpcodeManager manager = OpcodeManager.getInstance();\r
+ Iterator<Opcode> iterator = element.iterator();\r
+ Assert.assertTrue(iterator.hasNext());\r
+ Assert.assertEquals(manager.getOpcode(27), iterator.next());\r
+ Assert.assertTrue(iterator.hasNext());\r
+ Assert.assertEquals(manager.getOpcode(28), iterator.next());\r
+ Assert.assertTrue(iterator.hasNext());\r
+ Assert.assertEquals(manager.getOpcode(96), iterator.next());\r
+ Assert.assertTrue(iterator.hasNext());\r
+ Assert.assertEquals(manager.getOpcode(62), iterator.next());\r
+ Assert.assertFalse(iterator.hasNext());\r
+ }\r
+}\r
--- /dev/null
+package jp.sourceforge.stigmata.birthmarks.osb;\r
+\r
+import java.io.IOException;\r
+import java.net.URL;\r
+\r
+import jp.sourceforge.stigmata.Birthmark;\r
+import jp.sourceforge.stigmata.BirthmarkElement;\r
+import jp.sourceforge.stigmata.BirthmarkExtractionFailedException;\r
+import jp.sourceforge.stigmata.ExtractionUnit;\r
+import jp.sourceforge.stigmata.cflib.Opcode;\r
+import jp.sourceforge.stigmata.cflib.OpcodeManager;\r
+\r
+import org.junit.Assert;\r
+import org.junit.Before;\r
+import org.junit.Test;\r
+\r
+public class OperandStackBehaviorsBirthmarkExtractorTest{\r
+ private OperandStackBehaviorsBirthmarkExtractor extractor;\r
+\r
+ @Before\r
+ public void setUp(){\r
+ OperandStackBehaviorsBirthmarkService service = new OperandStackBehaviorsBirthmarkService();\r
+ extractor = (OperandStackBehaviorsBirthmarkExtractor)service.getExtractor();\r
+ }\r
+\r
+ @Test\r
+ public void testBasic(){\r
+ OperandStackBehaviorsBirthmarkElement element = \r
+ (OperandStackBehaviorsBirthmarkElement)extractor.buildElement("27, 28, 96, 62");\r
+\r
+ Assert.assertArrayEquals(\r
+ new ExtractionUnit[] { ExtractionUnit.CLASS, },\r
+ extractor.getAcceptableUnits()\r
+ );\r
+\r
+ Assert.assertEquals(Opcode.Category.LOAD, element.getCategory(0));\r
+ Assert.assertEquals(Opcode.Category.LOAD, element.getCategory(1));\r
+ Assert.assertEquals(Opcode.Category.ADD, element.getCategory(2));\r
+ Assert.assertEquals(Opcode.Category.STORE, element.getCategory(3));\r
+\r
+ OpcodeManager manager = OpcodeManager.getInstance();\r
+ Assert.assertEquals(manager.getOpcode(27), element.getOpcode(0));\r
+ Assert.assertEquals(manager.getOpcode(28), element.getOpcode(1));\r
+ Assert.assertEquals(manager.getOpcode(96), element.getOpcode(2));\r
+ Assert.assertEquals(manager.getOpcode(62), element.getOpcode(3));\r
+ }\r
+\r
+ @Test\r
+ public void testExtract1() throws BirthmarkExtractionFailedException, IOException{\r
+ URL url = getClass().getResource("/resources/Sample1.class");\r
+ Birthmark birthmark = extractor.extract(url.openStream());\r
+\r
+ Assert.assertEquals("osb", birthmark.getType());\r
+ Assert.assertEquals(7, birthmark.getElementCount());\r
+\r
+ BirthmarkElement[] elements = birthmark.getElements();\r
+ OperandStackBehaviorsBirthmarkElement element = (OperandStackBehaviorsBirthmarkElement)elements[0];\r
+ Assert.assertEquals(2, element.getLength());\r
+ Assert.assertEquals(Opcode.Category.LOAD, element.getCategory(0)); // aload_0\r
+ Assert.assertEquals(Opcode.Category.INVOKE, element.getCategory(1)); // invokespecial\r
+\r
+ element = (OperandStackBehaviorsBirthmarkElement)elements[1];\r
+ Assert.assertEquals(1, element.getLength());\r
+ Assert.assertEquals(Opcode.Category.RETURN, element.getCategory(0)); // return\r
+\r
+ element = (OperandStackBehaviorsBirthmarkElement)elements[2];\r
+ Assert.assertEquals(2, element.getLength());\r
+ Assert.assertEquals(Opcode.Category.CONSTANT, element.getCategory(0)); // iconst_2\r
+ Assert.assertEquals(Opcode.Category.STORE, element.getCategory(1)); // istore_1\r
+\r
+ element = (OperandStackBehaviorsBirthmarkElement)elements[3];\r
+ Assert.assertEquals(2, element.getLength());\r
+ Assert.assertEquals(Opcode.Category.CONSTANT, element.getCategory(0)); // iconst_4\r
+ Assert.assertEquals(Opcode.Category.STORE, element.getCategory(1)); // istore_2\r
+\r
+ element = (OperandStackBehaviorsBirthmarkElement)elements[4];\r
+ Assert.assertEquals(4, element.getLength());\r
+ Assert.assertEquals(Opcode.Category.LOAD, element.getCategory(0)); // iconst_4\r
+ Assert.assertEquals(Opcode.Category.LOAD, element.getCategory(1)); // iconst_4\r
+ Assert.assertEquals(Opcode.Category.ADD, element.getCategory(2)); // iadd\r
+ Assert.assertEquals(Opcode.Category.STORE, element.getCategory(3)); // istore_3\r
+\r
+ element = (OperandStackBehaviorsBirthmarkElement)elements[5];\r
+ Assert.assertEquals(3, element.getLength());\r
+ Assert.assertEquals(Opcode.Category.FIELD, element.getCategory(0)); // getstatic\r
+ Assert.assertEquals(Opcode.Category.LOAD, element.getCategory(1)); // iload_3\r
+ Assert.assertEquals(Opcode.Category.INVOKE, element.getCategory(2)); // invokevirtual\r
+\r
+ element = (OperandStackBehaviorsBirthmarkElement)elements[6];\r
+ Assert.assertEquals(1, element.getLength());\r
+ Assert.assertEquals(Opcode.Category.RETURN, element.getCategory(0)); // return\r
+ }\r
+\r
+ @Test\r
+ public void testExtract2() throws BirthmarkExtractionFailedException, IOException{\r
+ URL url = getClass().getResource("/resources/Sample2.class");\r
+ Birthmark birthmark = extractor.extract(url.openStream());\r
+\r
+ Assert.assertEquals("osb", birthmark.getType());\r
+ Assert.assertEquals(8, birthmark.getElementCount());\r
+\r
+ BirthmarkElement[] elements = birthmark.getElements();\r
+ OperandStackBehaviorsBirthmarkElement element = (OperandStackBehaviorsBirthmarkElement)elements[0];\r
+ Assert.assertEquals(2, element.getLength());\r
+ Assert.assertEquals(Opcode.Category.LOAD, element.getCategory(0)); // aload_0\r
+ Assert.assertEquals(Opcode.Category.INVOKE, element.getCategory(1)); // invokespecial\r
+\r
+ element = (OperandStackBehaviorsBirthmarkElement)elements[1];\r
+ Assert.assertEquals(1, element.getLength());\r
+ Assert.assertEquals(Opcode.Category.RETURN, element.getCategory(0)); // return\r
+\r
+ element = (OperandStackBehaviorsBirthmarkElement)elements[2];\r
+ Assert.assertEquals(2, element.getLength());\r
+ Assert.assertEquals(Opcode.Category.CONSTANT, element.getCategory(0)); // iconst_2\r
+ Assert.assertEquals(Opcode.Category.STORE, element.getCategory(1)); // istore_1\r
+\r
+ element = (OperandStackBehaviorsBirthmarkElement)elements[3];\r
+ Assert.assertEquals(2, element.getLength());\r
+ Assert.assertEquals(Opcode.Category.CONSTANT, element.getCategory(0)); // iconst_4\r
+ Assert.assertEquals(Opcode.Category.STORE, element.getCategory(1)); // istore_2\r
+\r
+ element = (OperandStackBehaviorsBirthmarkElement)elements[4];\r
+ Assert.assertEquals(4, element.getLength());\r
+ Assert.assertEquals(Opcode.Category.LOAD, element.getCategory(0)); // iconst_4\r
+ Assert.assertEquals(Opcode.Category.LOAD, element.getCategory(1)); // iconst_4\r
+ Assert.assertEquals(Opcode.Category.ADD, element.getCategory(2)); // iadd\r
+ Assert.assertEquals(Opcode.Category.STORE, element.getCategory(3)); // istore_3\r
+\r
+ element = (OperandStackBehaviorsBirthmarkElement)elements[5];\r
+ Assert.assertEquals(6, element.getLength());\r
+ Assert.assertEquals(Opcode.Category.LOAD, element.getCategory(0));\r
+ Assert.assertEquals(Opcode.Category.LOAD, element.getCategory(1));\r
+ Assert.assertEquals(Opcode.Category.MULTIPLY, element.getCategory(2));\r
+ Assert.assertEquals(Opcode.Category.LOAD, element.getCategory(3));\r
+ Assert.assertEquals(Opcode.Category.SUBTRACT, element.getCategory(4));\r
+ Assert.assertEquals(Opcode.Category.STORE, element.getCategory(5));\r
+\r
+ element = (OperandStackBehaviorsBirthmarkElement)elements[6];\r
+ Assert.assertEquals(3, element.getLength());\r
+ Assert.assertEquals(Opcode.Category.FIELD, element.getCategory(0)); // getstatic\r
+ Assert.assertEquals(Opcode.Category.LOAD, element.getCategory(1)); // iload_3\r
+ Assert.assertEquals(Opcode.Category.INVOKE, element.getCategory(2)); // invokevirtual\r
+\r
+ element = (OperandStackBehaviorsBirthmarkElement)elements[7];\r
+ Assert.assertEquals(1, element.getLength());\r
+ Assert.assertEquals(Opcode.Category.RETURN, element.getCategory(0)); // return\r
+ }\r
+}\r
--- /dev/null
+package jp.sourceforge.stigmata.birthmarks.osb;\r
+\r
+import org.junit.Assert;\r
+import org.junit.Before;\r
+import org.junit.Test;\r
+\r
+public class OperandStackBehaviorsBirthmarkServiceTest{\r
+ private OperandStackBehaviorsBirthmarkService service;\r
+\r
+ @Before\r
+ public void setUp(){\r
+ service = new OperandStackBehaviorsBirthmarkService();\r
+ }\r
+\r
+ @Test\r
+ public void testBasic(){\r
+ Assert.assertEquals("osb", service.getType());\r
+ Assert.assertEquals("Operand stack behaviors birthmark", service.getDescription());\r
+ Assert.assertNull(service.getPreprocessor());\r
+\r
+ Assert.assertEquals(OperandStackBehaviorsBirthmarkExtractor.class, service.getExtractor().getClass());\r
+ Assert.assertEquals(OperandStackBehaviorsBirthmarkComparator.class, service.getComparator().getClass());\r
+\r
+ Assert.assertFalse(service.isExperimental());\r
+ Assert.assertFalse(service.isUserDefined());\r
+ }\r
+}\r
--- /dev/null
+package jp.sourceforge.stigmata.birthmarks.osb.hungarian;\r
+\r
+import org.junit.Assert;\r
+import org.junit.Test;\r
+\r
+public class CellTest{\r
+ @Test\r
+ public void testBasic(){\r
+ Cell cell = new Cell(1.0d, 2, 3);\r
+\r
+ Assert.assertEquals(1d, cell.getValue(), 1E-6);\r
+ Assert.assertEquals(true, cell.isAvailable());\r
+ Assert.assertEquals(2, cell.getX());\r
+ Assert.assertEquals(3, cell.getY());\r
+\r
+ Assert.assertEquals("(2, 3): 1.000", cell.toString());\r
+ }\r
+\r
+ @Test\r
+ public void testEmptyCell(){\r
+ Cell cell = new Cell.EmptyCell(4, 5);\r
+\r
+ Assert.assertEquals(false, cell.isAvailable());\r
+ Assert.assertEquals(4, cell.getX());\r
+ Assert.assertEquals(5, cell.getY());\r
+\r
+ Assert.assertEquals("(4, 5): N/A", cell.toString());\r
+ }\r
+\r
+ @Test(expected=IllegalStateException.class)\r
+ public void testIllegalStateException(){\r
+ Cell cell = new Cell.EmptyCell(4, 5);\r
+ cell.getValue();\r
+ }\r
+}\r
--- /dev/null
+package jp.sourceforge.stigmata.birthmarks.osb.hungarian;\r
+\r
+import org.junit.Assert;\r
+import org.junit.Test;\r
+\r
+public class CostMatrixTest{\r
+ @Test\r
+ public void testUnequalsMatrix(){\r
+ CostMatrix matrix = new CostMatrix(new double[][] {\r
+ { 1.0, 0.0, 0.0, },\r
+ { 0.0, 0.8, 0.0, },\r
+ { 0.0, 0.0, 0.6, },\r
+ { 0.0, 0.2, 0.3, },\r
+ });\r
+\r
+ Assert.assertEquals(4, matrix.getSize());\r
+ Assert.assertEquals(1.0, matrix.getValue(0, 0), 1E-3);\r
+ Assert.assertEquals(0.0, matrix.getValue(0, 1), 1E-3);\r
+ Assert.assertEquals(0.0, matrix.getValue(0, 2), 1E-3);\r
+ Assert.assertEquals(1.0, matrix.getValue(0, 3), 1E-3);\r
+ Assert.assertEquals(0.0, matrix.getValue(1, 0), 1E-3);\r
+ Assert.assertEquals(0.8, matrix.getValue(1, 1), 1E-3);\r
+ Assert.assertEquals(0.0, matrix.getValue(1, 2), 1E-3);\r
+ Assert.assertEquals(1.0, matrix.getValue(1, 3), 1E-3);\r
+ Assert.assertEquals(0.0, matrix.getValue(2, 0), 1E-3);\r
+ Assert.assertEquals(0.0, matrix.getValue(2, 1), 1E-3);\r
+ Assert.assertEquals(0.6, matrix.getValue(2, 2), 1E-3);\r
+ Assert.assertEquals(1.0, matrix.getValue(2, 3), 1E-3);\r
+ Assert.assertEquals(0.0, matrix.getValue(3, 0), 1E-3);\r
+ Assert.assertEquals(0.2, matrix.getValue(3, 1), 1E-3);\r
+ Assert.assertEquals(0.3, matrix.getValue(3, 2), 1E-3);\r
+ Assert.assertEquals(1.0, matrix.getValue(3, 3), 1E-3);\r
+ }\r
+\r
+ @Test\r
+ public void testUnequalsMatrixAndMax(){\r
+ CostMatrix matrix = new CostMatrix(new double[][] {\r
+ { 1.0, 0.0, 0.0, },\r
+ { 0.0, 0.8, 0.0, },\r
+ { 0.0, 0.0, 0.6, },\r
+ { 0.0, 0.2, 0.3, },\r
+ }, true);\r
+\r
+ Assert.assertEquals(4, matrix.getSize());\r
+ Assert.assertEquals(0.0, matrix.getValue(0, 0), 1E-3);\r
+ Assert.assertEquals(1.0, matrix.getValue(0, 1), 1E-3);\r
+ Assert.assertEquals(1.0, matrix.getValue(0, 2), 1E-3);\r
+ Assert.assertEquals(1.0, matrix.getValue(0, 3), 1E-3);\r
+ Assert.assertEquals(1.0, matrix.getValue(1, 0), 1E-3);\r
+ Assert.assertEquals(0.2, matrix.getValue(1, 1), 1E-3);\r
+ Assert.assertEquals(1.0, matrix.getValue(1, 2), 1E-3);\r
+ Assert.assertEquals(1.0, matrix.getValue(1, 3), 1E-3);\r
+ Assert.assertEquals(1.0, matrix.getValue(2, 0), 1E-3);\r
+ Assert.assertEquals(1.0, matrix.getValue(2, 1), 1E-3);\r
+ Assert.assertEquals(0.4, matrix.getValue(2, 2), 1E-3);\r
+ Assert.assertEquals(1.0, matrix.getValue(2, 3), 1E-3);\r
+ Assert.assertEquals(1.0, matrix.getValue(3, 0), 1E-3);\r
+ Assert.assertEquals(0.8, matrix.getValue(3, 1), 1E-3);\r
+ Assert.assertEquals(0.7, matrix.getValue(3, 2), 1E-3);\r
+ Assert.assertEquals(1.0, matrix.getValue(3, 3), 1E-3);\r
+ }\r
+\r
+ @Test\r
+ public void testMinimize(){\r
+ CostMatrix matrix = new CostMatrix(new double[][]{\r
+ { 0.15, 0.06, 0.09, 0.08, },\r
+ { 0.03, 0.13, 0.07, 0.06, },\r
+ { 0.09, 0.10, 0.05, 0.11, },\r
+ { 0.03, 0.05, 0.07, 0.11, },\r
+ });\r
+ Assert.assertEquals(4, matrix.getSize());\r
+ matrix.minimize();\r
+ Assert.assertEquals(0.09, matrix.getValue(0, 0), 1E-6);\r
+ Assert.assertEquals(0.0, matrix.getValue(0, 1), 1E-6);\r
+ Assert.assertEquals(0.03, matrix.getValue(0, 2), 1E-6);\r
+ Assert.assertEquals(0.0, matrix.getValue(0, 3), 1E-6);\r
+\r
+ Assert.assertEquals(0.0, matrix.getValue(1, 0), 1E-6);\r
+ Assert.assertEquals(0.10, matrix.getValue(1, 1), 1E-6);\r
+ Assert.assertEquals(0.04, matrix.getValue(1, 2), 1E-6);\r
+ Assert.assertEquals(0.01, matrix.getValue(1, 3), 1E-6);\r
+\r
+ Assert.assertEquals(0.04, matrix.getValue(2, 0), 1E-6);\r
+ Assert.assertEquals(0.05, matrix.getValue(2, 1), 1E-6);\r
+ Assert.assertEquals(0.00, matrix.getValue(2, 2), 1E-6);\r
+ Assert.assertEquals(0.04, matrix.getValue(2, 3), 1E-6);\r
+\r
+ Assert.assertEquals(0.0, matrix.getValue(3, 0), 1E-6);\r
+ Assert.assertEquals(0.02, matrix.getValue(3, 1), 1E-6);\r
+ Assert.assertEquals(0.04, matrix.getValue(3, 2), 1E-6);\r
+ Assert.assertEquals(0.06, matrix.getValue(3, 3), 1E-6);\r
+ }\r
+}\r
--- /dev/null
+package jp.sourceforge.stigmata.birthmarks.osb.hungarian;\r
+\r
+import org.junit.Assert;\r
+import org.junit.Before;\r
+import org.junit.Test;\r
+\r
+public class HungarianMethodSolutionTest{\r
+ @Before\r
+ public void setUp(){\r
+ }\r
+\r
+ @Test\r
+ public void testBasic(){\r
+ CostMatrix matrix = new CostMatrix(new double[][] {\r
+ { 0.2, 0.2, 0.333, 0.1, },\r
+ { 0.75, 0.75, 0.666, 0.2, },\r
+ { 0.3, 0.3, 0.4, 0.15, },\r
+ { 0.2, 0.2, 1, 0.2, },\r
+ }, true);\r
+ HungarianMethod method = new HungarianMethod(matrix);\r
+\r
+ Assert.assertEquals(0.8, matrix.getValue(0, 0), 1E-6);\r
+ Assert.assertEquals(0.8, matrix.getValue(0, 1), 1E-6);\r
+ Assert.assertEquals(0.667, matrix.getValue(0, 2), 1E-6);\r
+ Assert.assertEquals(0.9, matrix.getValue(0, 3), 1E-6);\r
+ Assert.assertEquals(0.25, matrix.getValue(1, 0), 1E-6);\r
+ Assert.assertEquals(0.25, matrix.getValue(1, 1), 1E-6);\r
+ Assert.assertEquals(0.334, matrix.getValue(1, 2), 1E-6);\r
+ Assert.assertEquals(0.8, matrix.getValue(1, 3), 1E-6);\r
+ Assert.assertEquals(0.7, matrix.getValue(2, 0), 1E-6);\r
+ Assert.assertEquals(0.7, matrix.getValue(2, 1), 1E-6);\r
+ Assert.assertEquals(0.6, matrix.getValue(2, 2), 1E-6);\r
+ Assert.assertEquals(0.85, matrix.getValue(2, 3), 1E-6);\r
+ Assert.assertEquals(0.8, matrix.getValue(3, 0), 1E-6);\r
+ Assert.assertEquals(0.8, matrix.getValue(3, 1), 1E-6);\r
+ Assert.assertEquals(0, matrix.getValue(3, 2), 1E-6);\r
+ Assert.assertEquals(0.8, matrix.getValue(3, 3), 1E-6);\r
+\r
+ matrix.minimize();\r
+ \r
+ Assert.assertEquals(0.133, matrix.getValue(0, 0), 1E-6);\r
+ Assert.assertEquals(0.133, matrix.getValue(0, 1), 1E-6);\r
+ Assert.assertEquals(0, matrix.getValue(0, 2), 1E-6);\r
+ Assert.assertEquals(0, matrix.getValue(0, 3), 1E-6);\r
+ Assert.assertEquals(0, matrix.getValue(1, 0), 1E-6);\r
+ Assert.assertEquals(0, matrix.getValue(1, 1), 1E-6);\r
+ Assert.assertEquals(0.084, matrix.getValue(1, 2), 1E-6);\r
+ Assert.assertEquals(0.317, matrix.getValue(1, 3), 1E-6);\r
+ Assert.assertEquals(0.1, matrix.getValue(2, 0), 1E-6);\r
+ Assert.assertEquals(0.1, matrix.getValue(2, 1), 1E-6);\r
+ Assert.assertEquals(0, matrix.getValue(2, 2), 1E-6);\r
+ Assert.assertEquals(0.017, matrix.getValue(2, 3), 1E-6);\r
+ Assert.assertEquals(0.8, matrix.getValue(3, 0), 1E-6);\r
+ Assert.assertEquals(0.8, matrix.getValue(3, 1), 1E-6);\r
+ Assert.assertEquals(0, matrix.getValue(3, 2), 1E-6);\r
+ Assert.assertEquals(0.567, matrix.getValue(3, 3), 1E-6);\r
+\r
+ Line[] lines1 = method.getLines();\r
+ Assert.assertEquals(3, lines1.length);\r
+\r
+ Assert.assertEquals(Line.Direction.COLUMN, lines1[0].getDirection());\r
+ Assert.assertEquals(2, lines1[0].getIndex());\r
+ Assert.assertEquals(3, lines1[0].getCount());\r
+ Assert.assertEquals("[index: 2, count: 3(0) (COLUMN)]", lines1[0].toString());\r
+\r
+ Assert.assertEquals(Line.Direction.ROW, lines1[1].getDirection());\r
+ Assert.assertEquals(1, lines1[1].getIndex());\r
+ Assert.assertEquals(2, lines1[1].getCount());\r
+ Assert.assertEquals("[index: 1, count: 2(1) (ROW)]", lines1[1].toString());\r
+\r
+ Assert.assertEquals(Line.Direction.COLUMN, lines1[2].getDirection());\r
+ Assert.assertEquals(3, lines1[2].getIndex());\r
+ Assert.assertEquals(1, lines1[2].getCount());\r
+ Assert.assertEquals("[index: 3, count: 1(1) (COLUMN)]", lines1[2].toString());\r
+\r
+ method.reduceMatrix(lines1);\r
+ Assert.assertEquals(0.033, matrix.getValue(0, 0), 1E-6);\r
+ Assert.assertEquals(0.033, matrix.getValue(0, 1), 1E-6);\r
+ Assert.assertEquals(0, matrix.getValue(0, 2), 1E-6);\r
+ Assert.assertEquals(0, matrix.getValue(0, 3), 1E-6);\r
+ Assert.assertEquals(0, matrix.getValue(1, 0), 1E-6);\r
+ Assert.assertEquals(0, matrix.getValue(1, 1), 1E-6);\r
+ Assert.assertEquals(0.184, matrix.getValue(1, 2), 1E-6);\r
+ Assert.assertEquals(0.417, matrix.getValue(1, 3), 1E-6);\r
+ Assert.assertEquals(0, matrix.getValue(2, 0), 1E-6);\r
+ Assert.assertEquals(0, matrix.getValue(2, 1), 1E-6);\r
+ Assert.assertEquals(0, matrix.getValue(2, 2), 1E-6);\r
+ Assert.assertEquals(0.017, matrix.getValue(2, 3), 1E-6);\r
+ Assert.assertEquals(0.7, matrix.getValue(3, 0), 1E-6);\r
+ Assert.assertEquals(0.7, matrix.getValue(3, 1), 1E-6);\r
+ Assert.assertEquals(0, matrix.getValue(3, 2), 1E-6);\r
+ Assert.assertEquals(0.567, matrix.getValue(3, 3), 1E-6);\r
+\r
+ Line[] lines2 = method.getLines();\r
+ Assert.assertEquals(4, lines2.length);\r
+\r
+ Assert.assertEquals(Line.Direction.COLUMN, lines2[0].getDirection());\r
+ Assert.assertEquals(2, lines2[0].getIndex());\r
+ Assert.assertEquals(3, lines2[0].getCount());\r
+\r
+ Assert.assertEquals(Line.Direction.ROW, lines2[1].getDirection());\r
+ Assert.assertEquals(2, lines2[1].getIndex());\r
+ Assert.assertEquals(2, lines2[1].getCount());\r
+\r
+ Assert.assertEquals(Line.Direction.ROW, lines2[2].getDirection());\r
+ Assert.assertEquals(1, lines2[2].getIndex());\r
+ Assert.assertEquals(2, lines2[2].getCount());\r
+\r
+ Assert.assertEquals(Line.Direction.COLUMN, lines2[3].getDirection());\r
+ Assert.assertEquals(3, lines2[3].getIndex());\r
+ Assert.assertEquals(1, lines2[3].getCount());\r
+\r
+ Assert.assertEquals(2.15, method.solve(), 1E-6);\r
+\r
+ Cell[] cell = method.getSolutions();\r
+ Assert.assertEquals(4, cell.length);\r
+\r
+ Assert.assertEquals(0, cell[0].getX());\r
+ Assert.assertEquals(3, cell[0].getY());\r
+ Assert.assertEquals(0.1, cell[0].getValue(), 1E-6);\r
+\r
+ Assert.assertEquals(1, cell[1].getX());\r
+ Assert.assertEquals(0, cell[1].getY());\r
+ Assert.assertEquals(0.75, cell[1].getValue(), 1E-6);\r
+\r
+ Assert.assertEquals(2, cell[2].getX());\r
+ Assert.assertEquals(1, cell[2].getY());\r
+ Assert.assertEquals(0.3, cell[2].getValue(), 1E-6);\r
+\r
+ Assert.assertEquals(3, cell[3].getX());\r
+ Assert.assertEquals(2, cell[3].getY());\r
+ Assert.assertEquals(1, cell[3].getValue(), 1E-6);\r
+ }\r
+}\r
--- /dev/null
+package jp.sourceforge.stigmata.birthmarks.osb.hungarian;\r
+\r
+import org.junit.Assert;\r
+import org.junit.Before;\r
+import org.junit.Test;\r
+\r
+public class HungarianMethodTest{\r
+ @Before\r
+ public void setUp(){\r
+ }\r
+\r
+ @Test\r
+ public void testBasic(){\r
+ CostMatrix matrix = new CostMatrix(new double[][] {\r
+ { 0.2, 0.2, 0.333, 0.1, },\r
+ { 0.75, 0.75, 0.666, 0.2, },\r
+ { 0.3, 0.3, 0.4, 0.15, },\r
+ { 0.2, 0.2, 1, 0.2, },\r
+ }, true);\r
+ HungarianMethod method = new HungarianMethod(matrix);\r
+ Assert.assertEquals(2.15, method.solve(), 1E-6);\r
+ }\r
+\r
+ @Test\r
+ public void testBasic2(){\r
+ CostMatrix matrix = new CostMatrix(new double[][] {\r
+ { 0.209595, 0.465415, 0.760024, 0.956651, 0.838918, 0.914212, 0.299751, },\r
+ { 0.350187, 0.043090, 0.996489, 0.130135, 0.116187, 0.395586, 0.257572, },\r
+ { 0.400339, 0.340549, 0.518255, 0.301846, 0.215443, 0.481817, 0.167668, },\r
+ { 0.844414, 0.737599, 0.894256, 0.667530, 0.029905, 0.256991, 0.867919, },\r
+ { 0.113587, 0.433392, 0.067705, 0.763238, 0.508876, 0.460116, 0.168199, },\r
+ { 0.697585, 0.874909, 0.568728, 0.646872, 0.027345, 0.428272, 0.857028, },\r
+ { 0.110312, 0.561466, 0.112358, 0.069674, 0.665109, 0.041041, 0.130386, },\r
+ { 0.014101, 0.773713, 0.924393, 0.638526, 0.703886, 0.770603, 0.928259, },\r
+ { 0.426957, 0.288075, 0.947143, 0.093035, 0.241806, 0.970468, 0.891780, },\r
+ }, true);\r
+ HungarianMethod method = new HungarianMethod(matrix);\r
+ Assert.assertEquals(6.236299, method.solve(), 1E-6);\r
+ }\r
+\r
+ @Test\r
+ public void testBasic3(){\r
+ CostMatrix matrix = new CostMatrix(new double[][] {\r
+ { 0.109821, 0.108200, 0.967758, 0.879690, 0.606278, 0.627169, 0.230391, }, \r
+ { 0.517603, 0.045502, 0.279343, 0.942029, 0.630428, 0.517259, 0.659899, }, \r
+ { 0.846279, 0.220084, 0.929258, 0.009920, 0.773227, 0.304251, 0.406748, }, \r
+ { 0.075661, 0.022613, 0.006470, 0.847046, 0.869278, 0.147251, 0.313651, }, \r
+ { 0.118903, 0.911011, 0.800919, 0.634199, 0.909296, 0.865808, 0.780742, }, \r
+ { 0.701107, 0.889183, 0.226646, 0.516193, 0.681720, 0.694964, 0.842307, }, \r
+ { 0.035120, 0.579560, 0.203825, 0.639133, 0.871800, 0.143418, 0.718832, }, \r
+ }, true);\r
+ HungarianMethod method = new HungarianMethod(matrix);\r
+ Assert.assertEquals(6.099167, method.solve(), 1E-6);\r
+ }\r
+\r
+ @Test\r
+ public void testBasic4(){\r
+ CostMatrix matrix = new CostMatrix(new double[][] {\r
+ { 0.2, 0.3, 0.5, 0.2, 0.6, },\r
+ { 0.4, 0.6, 0.6, 0.6, 0.7, },\r
+ { 0.4, 0.4, 0.7, 0.3, 0.4, },\r
+ { 0.3, 0.6, 0.4, 0.5, 0.5, },\r
+ { 0.4, 0.2, 0.7, 0.4, 0.4, },\r
+ }, false);\r
+ HungarianMethod method = new HungarianMethod(matrix);\r
+ double value = method.solve();\r
+ Cell[] solution = method.getSolutions();\r
+ Assert.assertEquals(5, solution.length);\r
+\r
+ Assert.assertEquals(0, solution[0].getX());\r
+ Assert.assertEquals(3, solution[0].getY());\r
+ Assert.assertEquals(0.2, solution[0].getValue(), 1E-6);\r
+\r
+ Assert.assertEquals(1, solution[1].getX());\r
+ Assert.assertEquals(0, solution[1].getY());\r
+ Assert.assertEquals(0.4, solution[1].getValue(), 1E-6);\r
+\r
+ Assert.assertEquals(2, solution[2].getX());\r
+ Assert.assertEquals(4, solution[2].getY());\r
+ Assert.assertEquals(0.4, solution[2].getValue(), 1E-6);\r
+\r
+ Assert.assertEquals(3, solution[3].getX());\r
+ Assert.assertEquals(2, solution[3].getY());\r
+ Assert.assertEquals(0.4, solution[3].getValue(), 1E-6);\r
+\r
+ Assert.assertEquals(4, solution[4].getX());\r
+ Assert.assertEquals(1, solution[4].getY());\r
+ Assert.assertEquals(0.2, solution[4].getValue(), 1E-6);\r
+\r
+ Assert.assertEquals(1.6, value, 1E-6);\r
+ }\r
+\r
+ @Test\r
+ public void testBasic5(){\r
+ CostMatrix matrix = new CostMatrix(new double[][] {\r
+ { 0.2, 0.3, 0.4, 0.3, 0.6, },\r
+ { 0.4, 0.6, 0.5, 0.6, 0.7, },\r
+ { 0.4, 0.4, 0.6, 0.3, 0.4, },\r
+ { 0.4, 0.6, 0.3, 0.5, 0.5, },\r
+ { 0.4, 0.2, 0.6, 0.4, 0.4, },\r
+ }, false);\r
+ HungarianMethod method = new HungarianMethod(matrix);\r
+ double value = method.solve();\r
+ Cell[] solution = method.getSolutions();\r
+ Assert.assertEquals(5, solution.length);\r
+\r
+ Assert.assertEquals(0, solution[0].getX());\r
+ Assert.assertEquals(3, solution[0].getY());\r
+ Assert.assertEquals(0.3, solution[0].getValue(), 1E-6);\r
+\r
+ Assert.assertEquals(1, solution[1].getX());\r
+ Assert.assertEquals(0, solution[1].getY());\r
+ Assert.assertEquals(0.4, solution[1].getValue(), 1E-6);\r
+\r
+ Assert.assertEquals(2, solution[2].getX());\r
+ Assert.assertEquals(4, solution[2].getY());\r
+ Assert.assertEquals(0.4, solution[2].getValue(), 1E-6);\r
+\r
+ Assert.assertEquals(3, solution[3].getX());\r
+ Assert.assertEquals(2, solution[3].getY());\r
+ Assert.assertEquals(0.3, solution[3].getValue(), 1E-6);\r
+\r
+ Assert.assertEquals(4, solution[4].getX());\r
+ Assert.assertEquals(1, solution[4].getY());\r
+ Assert.assertEquals(0.2, solution[4].getValue(), 1E-6);\r
+\r
+ Assert.assertEquals(1.6, value, 1E-6);\r
+ }\r
+\r
+ @Test\r
+ public void testBasic6(){\r
+ CostMatrix matrix = new CostMatrix(new double[][] {\r
+ { 0.8, 0.9, 0.3, 0.8, },\r
+ { 0.6, 0.8, 0.6, 0.2, },\r
+ { 0.7, 0.7, 0.9, 0.6, },\r
+ { 0.2, 0.5, 0.8, 0.4, },\r
+ { 0.4, 0.6, 0.2, 0.7, },\r
+ }, true);\r
+ HungarianMethod method = new HungarianMethod(matrix);\r
+ double value = method.solve();\r
+ Cell[] solutions = method.getSolutions();\r
+\r
+ Assert.assertEquals(3.2, value, 1E-6);\r
+ Assert.assertEquals(4, solutions.length);\r
+\r
+ Assert.assertEquals(0, solutions[0].getX());\r
+ Assert.assertEquals(0, solutions[0].getY());\r
+ Assert.assertEquals(0.8, solutions[0].getValue(), 1E-6);\r
+\r
+ Assert.assertEquals(1, solutions[1].getX());\r
+ Assert.assertEquals(1, solutions[1].getY());\r
+ Assert.assertEquals(0.8, solutions[1].getValue(), 1E-6);\r
+\r
+ Assert.assertEquals(2, solutions[2].getX());\r
+ Assert.assertEquals(2, solutions[2].getY());\r
+ Assert.assertEquals(0.9, solutions[2].getValue(), 1E-6);\r
+\r
+ Assert.assertEquals(4, solutions[3].getX());\r
+ Assert.assertEquals(3, solutions[3].getY());\r
+ Assert.assertEquals(0.7, solutions[3].getValue(), 1E-6);\r
+ }\r
+\r
+ @Test\r
+ public void testBasic7(){\r
+ CostMatrix matrix = new CostMatrix(new double[][]{\r
+ { 1.0, 0.0, 0.2, 0.0, 0.33, 0.2, 0.1, 0.08, 0.2, 0.2, 0.0, 0.2, 0.2, 0.2, 0.2, 0.14, 0.14, 0.11, 0.2, 0.25, 0.09, 0.2, 0.0, 0.0, 0.25, 0.0, },\r
+ { 0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.33, },\r
+ { 0.2, 0.0, 1.0, 0.17, 0.0, 0.0, 0.44, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.17, 0.27, 0.0, 0.0, 0.2, 0.0, 0.0, },\r
+ { 0.0, 0.0, 0.17, 1.0, 0.0, 0.17, 0.2, 0.07, 0.17, 0.17, 0.0, 0.17, 0.17, 0.17, 0.17, 0.13, 0.13, 0.1, 0.17, 0.2, 0.08, 0.17, 0.0, 0.25, 0.2, 0.0, },\r
+ { 0.33, 0.0, 0.0, 0.0, 1.0, 0.2, 0.1, 0.08, 0.2, 0.2, 0.0, 0.2, 0.2, 0.2, 0.2, 0.14, 0.14, 0.11, 0.2, 0.25, 0.09, 0.2, 0.0, 0.0, 0.25, 0.0, },\r
+ { 0.2, 0.0, 0.0, 0.17, 0.2, 1.0, 0.18, 0.23, 1.0, 0.6, 0.0, 0.6, 0.6, 0.6, 0.6, 0.43, 0.43, 0.33, 0.6, 0.4, 0.17, 0.33, 0.0, 0.0, 0.4, 0.17, },\r
+ { 0.1, 0.0, 0.44, 0.2, 0.1, 0.18, 1.0, 0.24, 0.18, 0.18, 0.0, 0.18, 0.18, 0.18, 0.18, 0.25, 0.25, 0.31, 0.18, 0.33, 0.73, 0.18, 0.0, 0.1, 0.33, 0.09, },\r
+ { 0.08, 0.0, 0.0, 0.07, 0.08, 0.23, 0.24, 1.0, 0.23, 0.33, 0.0, 0.33, 0.33, 0.33, 0.33, 0.5, 0.5, 0.67, 0.33, 0.15, 0.29, 0.23, 0.0, 0.08, 0.15, 0.15, },\r
+ { 0.2, 0.0, 0.0, 0.17, 0.2, 1.0, 0.18, 0.23, 1.0, 0.6, 0.0, 0.6, 0.6, 0.6, 0.6, 0.43, 0.43, 0.33, 0.6, 0.4, 0.17, 0.33, 0.0, 0.0, 0.4, 0.17, },\r
+ { 0.2, 0.0, 0.0, 0.17, 0.2, 0.6, 0.18, 0.33, 0.6, 1.0, 0.0, 1.0, 1.0, 1.0, 1.0, 0.67, 0.67, 0.5, 1.0, 0.4, 0.17, 0.6, 0.0, 0.0, 0.4, 0.17, },\r
+ { 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, },\r
+ { 0.2, 0.0, 0.0, 0.17, 0.2, 0.6, 0.18, 0.33, 0.6, 1.0, 0.0, 1.0, 1.0, 1.0, 1.0, 0.67, 0.67, 0.5, 1.0, 0.4, 0.17, 0.6, 0.0, 0.0, 0.4, 0.17, },\r
+ { 0.2, 0.0, 0.0, 0.17, 0.2, 0.6, 0.18, 0.33, 0.6, 1.0, 0.0, 1.0, 1.0, 1.0, 1.0, 0.67, 0.67, 0.5, 1.0, 0.4, 0.17, 0.6, 0.0, 0.0, 0.4, 0.17, },\r
+ { 0.2, 0.0, 0.0, 0.17, 0.2, 0.6, 0.18, 0.33, 0.6, 1.0, 0.0, 1.0, 1.0, 1.0, 1.0, 0.67, 0.67, 0.5, 1.0, 0.4, 0.17, 0.6, 0.0, 0.0, 0.4, 0.17, },\r
+ { 0.2, 0.0, 0.0, 0.17, 0.2, 0.6, 0.18, 0.33, 0.6, 1.0, 0.0, 1.0, 1.0, 1.0, 1.0, 0.67, 0.67, 0.5, 1.0, 0.4, 0.17, 0.6, 0.0, 0.0, 0.4, 0.17, },\r
+ { 0.14, 0.0, 0.0, 0.13, 0.14, 0.43, 0.25, 0.5, 0.43, 0.67, 0.0, 0.67, 0.67, 0.67, 0.67, 1.0, 1.0, 0.75, 0.67, 0.29, 0.23, 0.43, 0.0, 0.14, 0.29, 0.29, },\r
+ { 0.14, 0.0, 0.0, 0.13, 0.14, 0.43, 0.25, 0.5, 0.43, 0.67, 0.0, 0.67, 0.67, 0.67, 0.67, 1.0, 1.0, 0.75, 0.67, 0.29, 0.23, 0.43, 0.0, 0.14, 0.29, 0.29, },\r
+ { 0.11, 0.0, 0.0, 0.1, 0.11, 0.33, 0.31, 0.67, 0.33, 0.5, 0.0, 0.5, 0.5, 0.5, 0.5, 0.75, 0.75, 1.0, 0.5, 0.22, 0.29, 0.33, 0.0, 0.11, 0.22, 0.22, },\r
+ { 0.2, 0.0, 0.0, 0.17, 0.2, 0.6, 0.18, 0.33, 0.6, 1.0, 0.0, 1.0, 1.0, 1.0, 1.0, 0.67, 0.67, 0.5, 1.0, 0.4, 0.17, 0.6, 0.0, 0.0, 0.4, 0.17, },\r
+ { 0.25, 0.0, 0.17, 0.2, 0.25, 0.4, 0.33, 0.15, 0.4, 0.4, 0.0, 0.4, 0.4, 0.4, 0.4, 0.29, 0.29, 0.22, 0.4, 1.0, 0.18, 0.4, 0.0, 0.25, 0.2, 0.2, },\r
+ { 0.09, 0.0, 0.27, 0.08, 0.09, 0.17, 0.73, 0.29, 0.17, 0.17, 0.0, 0.17, 0.17, 0.17, 0.17, 0.23, 0.23, 0.29, 0.17, 0.18, 1.0, 0.17, 0.0, 0.09, 0.3, 0.18, },\r
+ { 0.2, 0.0, 0.0, 0.17, 0.2, 0.33, 0.18, 0.23, 0.33, 0.6, 0.0, 0.6, 0.6, 0.6, 0.6, 0.43, 0.43, 0.33, 0.6, 0.4, 0.17, 1.0, 0.0, 0.0, 0.17, 0.17, },\r
+ { 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, },\r
+ { 0.0, 0.0, 0.2, 0.25, 0.0, 0.0, 0.1, 0.08, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.14, 0.14, 0.11, 0.0, 0.25, 0.09, 0.0, 0.0, 1.0, 0.0, 0.25, },\r
+ { 0.25, 0.0, 0.0, 0.2, 0.25, 0.4, 0.33, 0.15, 0.4, 0.4, 0.0, 0.4, 0.4, 0.4, 0.4, 0.29, 0.29, 0.22, 0.4, 0.2, 0.3, 0.17, 0.0, 0.0, 1.0, 0.2, },\r
+ { 0.0, 0.33, 0.0, 0.0, 0.0, 0.17, 0.09, 0.15, 0.17, 0.17, 0.0, 0.17, 0.17, 0.17, 0.17, 0.29, 0.29, 0.22, 0.17, 0.2, 0.18, 0.17, 0.0, 0.25, 0.2, 1.0, },\r
+ }, true);\r
+ HungarianMethod method = new HungarianMethod(matrix);\r
+ double value = method.solve();\r
+ Assert.assertEquals(26, value, 1E-6);\r
+ }\r
+\r
+ @Test\r
+ public void testBasic8(){\r
+ CostMatrix matrix = new CostMatrix(new double[][] {\r
+ { 1.0000, 0.0000, 0.0000, 0.0000, 0.2000, 0.1429, 0.6667, 0.0000, },\r
+ { 0.0000, 1.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 1.0000, },\r
+ { 0.0000, 0.0000, 1.0000, 1.0000, 0.2000, 0.1429, 0.0000, 0.0000, },\r
+ { 0.0000, 0.0000, 1.0000, 1.0000, 0.2000, 0.1429, 0.0000, 0.0000, },\r
+ { 0.2000, 0.0000, 0.2000, 0.2000, 1.0000, 0.4286, 0.1667, 0.0000, },\r
+ { 0.6667, 0.0000, 0.0000, 0.0000, 0.1667, 0.1250, 1.0000, 0.0000, },\r
+ { 0.0000, 1.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 1.0000, },\r
+ }, true);\r
+\r
+ HungarianMethod method = new HungarianMethod(matrix);\r
+ double value = method.solve();\r
+ Assert.assertEquals(7, value, 1E-6);\r
+ }\r
+}\r
--- /dev/null
+public class Sample1{\r
+ public void run(){\r
+ int x = 2;\r
+ int y = 4;\r
+ int a = x + y;\r
+ System.out.println(a);\r
+ }\r
+}
\ No newline at end of file
--- /dev/null
+public class Sample2{\r
+ public void run(){\r
+ int a = 10;\r
+ int b = 20;\r
+\r
+ int c = a + b;\r
+ int answer = a * b - c;\r
+ System.out.println(answer);\r
+ }\r
+}
\ No newline at end of file
-<?xml version="1.0" encoding="UTF-8"?>
-<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
+<?xml version="1.0" encoding="utf-8"?>
+<project xmlns="http://maven.apache.org/POM/4.0.0"
+ xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
+ xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
<modelVersion>4.0.0</modelVersion>
+
+ <parent>
+ <groupId>jp.sourceforge</groupId>
+ <artifactId>stigmata</artifactId>
+ <version>4.0-SNAPSHOT</version>
+ </parent>
+
<groupId>jp.sourceforge.stigmata</groupId>
- <artifactId>plugins</artifactId>
+ <artifactId>stigmata-plugins</artifactId>
+ <version>4.0-SNAPSHOT</version>
<packaging>pom</packaging>
- <version>1.0</version>
- <name>Stigmata Plugin Project</name>
- <description>Plugins of stigmata</description>
+
+ <name>Stigmata Plugins</name>
<url>http://stigmata.sourceforge.jp/plugins/</url>
- <inceptionYear>2008</inceptionYear>
<modules>
+ <module>kgram</module>
<module>wsp</module>
- <module>sot</module>
- <module>cflib</module>
-<!--
- <module>sapit</module>
- <module>cfs</module>
--->
+ <module>osb</module>
</modules>
- <issueManagement>
- <system>sourceforge</system>
- <url>http://sourceforge.jp/tracker/?group_id=3014</url>
- </issueManagement>
-
- <developers>
- <developer>
- <id>tama3</id>
- <name>Haruaki TAMADA</name>
- <email>tama3[ at ]users.sourceforge.jp</email>
- <timezone>-9</timezone>
- </developer>
- </developers>
-
- <organization>
- <name>Stigmata Plugins Project</name>
- <url>http://stigmata.sourceforge.jp/plugins/</url>
- </organization>
-
- <licenses>
- <license>
- <name>Apache License 2.0</name>
- <url>http://www.apache.org/licenses/LICENSE-2.0.txt</url>
- <distribution>repo</distribution>
- </license>
- </licenses>
-
- <repositories>
- <repository>
- <id>stigmata.sourceforge.jp</id>
- <name>sourceforge repository for Maven2</name>
- <url>http://stigmata.sourceforge.jp/maven2</url>
- </repository>
- </repositories>
-
<dependencies>
<dependency>
- <groupId>junit</groupId>
- <artifactId>junit</artifactId>
- <version>4.3</version>
- <scope>test</scope>
+ <groupId>jp.sourceforge.stigmata</groupId>
+ <artifactId>stigmata-core</artifactId>
+ <version>4.0-SNAPSHOT</version>
+ <scope>provided</scope>
</dependency>
</dependencies>
-
- <distributionManagement>
- <repository>
- <id>shell.sourceforge.jp</id>
- <name>shell sourceforge Maven2 Repository</name>
- <url>scp://shell.sourceforge.jp/home/groups/s/st/stigmata/htdocs/maven2</url>
- </repository>
- <site>
- <id>shell.sourceforge.jp</id>
- <name>shell sourceforge Maven2 Repository</name>
- <url>scp://shell.sourceforge.jp/home/groups/s/st/stigmata/htdocs/plugins/</url>
- </site>
- </distributionManagement>
-
- <scm>
- <connection>scm:svn:http://svn.sourceforge.jp/svnroot/stigmata/plugins/trunk/</connection>
- <developerConnection>scm:svn:svn+ssh://tama3@svn.sourceforge.jp/svnroot/stigmata/plugins/trunk</developerConnection>
- <url>http://svn.sourceforge.jp/svnroot/stigmata/plugins/trunk/</url>
- </scm>
-
- <build>
- <plugins>
- <plugin>
- <groupId>org.apache.maven.plugins</groupId>
- <artifactId>maven-compiler-plugin</artifactId>
- <configuration>
- <source>1.6</source>
- <target>1.6</target>
- <encoding>utf-8</encoding>
- </configuration>
- </plugin>
- <plugin>
- <groupId>org.apache.maven.plugins</groupId>
- <artifactId>maven-jar-plugin</artifactId>
- <configuration>
- <archive>
- <manifest>
- <addClasspath>true</addClasspath>
- </manifest>
- </archive>
- </configuration>
- </plugin>
-
- <plugin>
- <artifactId>maven-site-plugin</artifactId>
- <configuration>
- <inputEncoding>utf-8</inputEncoding>
- <outputEncoding>utf-8</outputEncoding>
- <locales>en</locales>
- </configuration>
- </plugin>
-
- <!-- for JUnit4 -->
- <plugin>
- <artifactId>maven-surefire-plugin</artifactId>
- <version>2.3</version>
- </plugin>
-
- <plugin>
- <groupId>org.apache.maven.plugins</groupId>
- <artifactId>maven-javadoc-plugin</artifactId>
- <configuration>
- <charset>utf-8</charset>
- <docencoding>utf-8</docencoding>
- <locale>en</locale>
- </configuration>
- </plugin>
- </plugins>
- </build>
-
- <reporting>
- <plugins>
- <plugin>
- <groupId>org.apache.maven.plugins</groupId>
- <artifactId>maven-project-info-reports-plugin</artifactId>
- </plugin>
- <plugin>
- <groupId>org.apache.maven.plugins</groupId>
- <artifactId>maven-javadoc-plugin</artifactId>
- <configuration>
- <locale>en</locale>
- </configuration>
- </plugin>
- <plugin>
- <groupId>org.codehaus.mojo</groupId>
- <artifactId>cobertura-maven-plugin</artifactId>
- </plugin>
- <plugin>
- <artifactId>maven-pmd-plugin</artifactId>
- <configuration>
- <linkXref>true</linkXref>
- <sourceEncoding>utf-8</sourceEncoding>
- <targetJdk>1.6</targetJdk>
- </configuration>
- </plugin>
- <plugin>
- <groupId>net.sf</groupId>
- <artifactId>stat-scm</artifactId>
- <configuration>
- <tags>csvio-1.0.1</tags>
- <tagsDir>/releases/</tagsDir>
- </configuration>
- </plugin>
- <plugin>
- <groupId>org.apache.maven.plugins</groupId>
- <artifactId>maven-jxr-plugin</artifactId>
- </plugin>
- <plugin>
- <groupId>org.apache.maven.plugins</groupId>
- <artifactId>maven-changes-plugin</artifactId>
- <reportSets>
- <reportSet>
- <reports>
- <report>changes-report</report>
- </reports>
- </reportSet>
- </reportSets>
- </plugin>
- <plugin>
- <groupId>org.codehaus.mojo</groupId>
- <artifactId>findbugs-maven-plugin</artifactId>
- <configuration>
- <xmlOutput>false</xmlOutput>
- <threshold>Normal</threshold>
- <effort>Default</effort>
- </configuration>
- </plugin>
- </plugins>
- </reporting>
</project>
+++ /dev/null
- ----\r
- Create Stigmata Plugin\r
- ----\r
- Haruaki Tamada\r
- ----\r
- 2009-06-24\r
- ----\r
-\r
-How to create Stigmata plugin\r
-\r
-*{BirthmarkService}\r
-\r
- At first, create concrete class of\r
-{{{http://stigmata.sourceforge.jp/apidocs/jp/sourceforge/stigmata/spi/BirthmarkSpi.html}BirthmarkSpi}}\r
-interface by extending\r
-{{{http://stigmata.sourceforge.jp/apidocs/jp/sourceforge/stigmata/birthmarks/AbstractBirthmarkService.html}AbstractBirthmarkService}}\r
-class.\r
-\r
-----\r
-public abstract class AbstractBirthmarkService implements BirthmarkSpi{\r
- public abstract BirthmarkComparator getComparator();\r
-\r
- public abstract BirthmarkExtractor getExtractor();\r
-\r
- public abstract String getType();\r
-\r
- public abstract String getDefaultDescription();\r
-}\r
-----\r
+++ /dev/null
- ----\r
- Download\r
- ----\r
- Haruaki Tamada\r
- ----\r
- 2009-06-23\r
- ----\r
-\r
-Download\r
-\r
-*License\r
-\r
- Weight Stack Pattern Birthmark (Stigmata Plugin)\r
-\r
- Apache License 2.0\r
-\r
- Copyright (C) 2006-2009 Haruaki TAMADA, Ph.D.\r
-\r
- Licensed under the Apache License, Version 2.0 (the "License"); you\r
-may not use this file except in compliance with the License. You may\r
-obtain a copy of the License at\r
-\r
- http://www.apache.org/licenses/LICENSE-2.0\r
-\r
- Unless required by applicable law or agreed to in writing, software\r
-distributed under the License is distributed on an "AS IS" BASIS,\r
-WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or\r
-implied. See the License for the specific language governing\r
-permissions and limitations under the License.\r
-\r
-*Requirements\r
-\r
- *{{{http://stigmata.sourceforge.jp/}Stigmata}} Runtime and its dependencies.\r
-\r
- []\r
-\r
-*Manually download\r
-\r
- We can download release build from {{{http://sourceforge.jp/}sourceforge.jp}}. \r
-\r
- {{{https://sourceforge.jp/projects/stigmata/releases/}Download}}\r
-\r
-*SCM\r
-\r
-**Subversion\r
-\r
- The source can be checked out anonymously from Subversion.\r
-\r
-----\r
-$ svn checkout http://svn.sourceforge.jp/svnroot/stigmata/plugins/trunk/wsp wsp\r
-----\r
-\r
-**Web access\r
-\r
- We can browse the source code from following link.\r
-\r
- {{http://sourceforge.jp/projects/stigmata/svn/view/plugins/trunk/wsp/}}\r
-\r
-*Online update\r
-\r
- See {{{install.html#Automatically install}Automatically install}}.
\ No newline at end of file
+++ /dev/null
- ----\r
- Stigmata Plugins\r
- ----\r
- Haruaki Tamada\r
- ----\r
- 2009-04-24\r
- ----\r
-\r
-Overview\r
-\r
- This product includes plugins of Stigmata. The plugin of Stigmata is\r
-extract/compare birthmarks from Java class files directly.\r
-\r
-\r
-Modules\r
-\r
-*wsp\r
-\r
- WSP (Weight Stack Pattern) based birthmark. This birthmark is defined\r
-in following article.\r
-\r
- * Hyun-il Lim, Heewan Park, Seokwoo Choi, Taisook Han, ``Detecting\r
- Theft of Java Applications via a Static Birthmark Based on Weighted\r
- Stack Patterns,'' IEICE Transactions on Information and Systems,\r
- Vol.E91-D No.9 pp.2323-2332, September 2008.\r
-\r
-*sapit\r
-\r
- Static API Trace birthmark. This birthmark is defined in following\r
-article. (Not available yet)\r
-\r
- * Heewan Park, Seokwoo Choi, Hyun-il Lim, and Taisook Han,\r
- ``Detecting Java Theft Based on Static API Trace Birthmark,'' In\r
- Proc. of the 3rd International Workshop on Security (IWSEC2008), LNCS\r
- 5312, pp.121-135, November 2008.\r
-\r
-*osb\r
-\r
- Operand Stack Behaviors based static birthmark. This birthmark is\r
-defined in following article. (Not available yet)\r
-\r
- * Heewan Park, Hyun-il Lim, Seokwoo Choi, and Taisook Han, ``A Static\r
- Java Birthmark Based on Operand Stack Behaviors,'' In\r
- Proc. International Conference on Information Security and\r
- Assurance (ICISA2008), IEEE Computer Society, pp.133--136, April\r
- 2008 (Los Alamitos, CA, USA).\r
+++ /dev/null
- ----\r
- Install Stigmata Plugins\r
- ----\r
- Haruaki Tamada\r
- ----\r
- 2009-04-24\r
- ----\r
-\r
-How to install Stigmata Plugin\r
-\r
-*{Manually install}\r
-\r
- At first, download a plugin jar file. Also, download dependencies of\r
-the plugin jar file.\r
-\r
- Next, put downloaded jar files into <<plugins>> folder in a settings\r
-folder of Stigmata. Besides, the settings folder is opened by\r
-selecting the menu item of Stigmata.\r
-\r
-*{Automatically install}\r
-\r
- Stigmata 2.1.0 or later can automatically download and install\r
-plugins via internet.\r
-\r
- First, select ``Online update'' menu item in ``Plugins'' menu.\r
- Then, a dialog will be shown. If updatable plugins are available,\r
-these plugins are listed in the dialog by pressing ``Check update''\r
-button.\r
-\r
-[images/onlineupdate.png] Screen shot of online update.\r
-\r
- When plugins were listed, ``update'' button will be enabled. you can\r
-press ``update'' button for updating plugins.\r
-\r
+++ /dev/null
-<?xml version="1.0" encoding="utf-8"?>\r
-\r
-<project name="Stigmata Plugins">\r
- <bannerLeft>\r
- <name>Stigmata</name>\r
- <href>http://stigmata.sourceforge.jp</href>\r
- <src>images/logos/stigmata_logo.png</src>\r
- <alt>Stigmata: Java birthmark toolkit</alt>\r
- </bannerLeft>\r
-\r
- <bannerRight>\r
- <name>Stigmata Plugins</name>\r
- <href>http://stigmata.sourceforge.jp/plugins</href>\r
- <src>images/logos/stigmata_plugins.png</src>\r
- <alt>Stigmata Plugins</alt>\r
- </bannerRight>\r
-\r
- <poweredBy>\r
- <logo name="Powered by ASM"\r
- href="http://asm.objectweb.org/"\r
- img="images/logos/poweredbyasm.gif"/>\r
- <logo name="sourceforge.jp"\r
- href="http://sourceforge.jp"\r
- img="http://sourceforge.jp/sflogo.php?group_id=2661" />\r
- <logo name="Build with Maven 2"\r
- href="http://maven.apache.org"\r
- img="images/logos/maven-feather.png"/>\r
- </poweredBy>\r
-\r
- <body>\r
- <links>\r
- <item name="wsp" href="http://stigmata.sourceforge.jp/plugins/wsp" />\r
- </links>\r
-\r
- <menu name="Stigmata Plugins">\r
- <item name="Overview" href="index.html"/>\r
- <item name="How to Install" href="install.html"/>\r
- <item name="Download" href="download.html"/>\r
- <item name="How to Create Plugin" href="create.html"/>\r
- </menu>\r
-\r
- <menu ref="modules" />\r
-\r
- <menu ref="parent" />\r
-\r
- <menu name="Links">\r
- <item name="Stigmata" href="http://stigmata.sourceforge.jp/"/>\r
- <item name="Talisman" href="http://talisman.sourceforge.jp/"/>\r
- <item name="DonQuixote" href="http://donquixote.cafebabe.jp/" />\r
- <item name="Project Page" href="http://sourceforge.jp/projects/stigmata/"/>\r
- </menu>\r
-\r
- <menu ref="reports"/>\r
- </body>\r
-</project>\r
-<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">\r
+<?xml version="1.0" encoding="utf-8"?>\r
+\r
+<project xmlns="http://maven.apache.org/POM/4.0.0"\r
+ xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"\r
+ xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4_0_0.xsd">\r
+ <modelVersion>4.0.0</modelVersion>\r
+\r
<parent>\r
- <artifactId>plugins</artifactId>\r
<groupId>jp.sourceforge.stigmata</groupId>\r
- <version>1.0</version>\r
+ <artifactId>stigmata-plugins</artifactId>\r
+ <version>4.0-SNAPSHOT</version>\r
</parent>\r
\r
- <modelVersion>4.0.0</modelVersion>\r
<groupId>jp.sourceforge.stigmata.plugins</groupId>\r
<artifactId>wsp</artifactId>\r
- <name>Weighted Stack Pattern Birthmark</name>\r
<version>1.0.1-SNAPSHOT</version>\r
+ <packaging>jar</packaging>\r
+\r
+ <name>Weighted Stack Pattern Birthmark</name>\r
<url>http://stigmata.sourceforge.jp/plugins/wsp/</url>\r
\r
<dependencies>\r
<dependency>\r
- <groupId>jp.sourceforge</groupId>\r
- <artifactId>stigmata</artifactId>\r
- <version>2.0.0</version>\r
- <scope>provided</scope>\r
- </dependency>\r
- <dependency>\r
- <groupId>asm</groupId>\r
- <artifactId>asm-all</artifactId>\r
- <version>3.1</version>\r
+ <groupId>jp.sourceforge.stigmata</groupId>\r
+ <artifactId>cflib</artifactId>\r
+ <version>2.0-SNAPSHOT</version>\r
<scope>compile</scope>\r
</dependency>\r
<dependency>\r
- <groupId>jp.sourceforge.stigmata.plugins</groupId>\r
- <artifactId>cflib</artifactId>\r
- <version>1.0.0</version>\r
- <scope>compile</scope>\r
+ <groupId>jp.sourceforge.stigmata</groupId>\r
+ <artifactId>digger</artifactId>\r
+ <version>4.0-SNAPSHOT</version>\r
</dependency>\r
</dependencies>\r
-\r
- <build>\r
- <plugins>\r
- <plugin>\r
- <artifactId>maven-release-plugin</artifactId>\r
- <configuration>\r
- <tagBase>svn+ssh://tama3@svn.sourceforge.jp/svnroot/stigmata/plugins/tags/wsp/</tagBase>\r
- </configuration>\r
- </plugin>\r
-\r
- <plugin>\r
- <groupId>org.apache.maven.plugins</groupId>\r
- <artifactId>maven-dependency-plugin</artifactId>\r
- <executions>\r
- <execution>\r
- <id>copy-dependencies</id>\r
- <phase>compile</phase>\r
- <goals>\r
- <goal>copy-dependencies</goal>\r
- </goals>\r
- <configuration>\r
- <outputDirectory>${project.build.directory}</outputDirectory>\r
- <includeScope>runtime</includeScope>\r
- </configuration>\r
- </execution>\r
- </executions>\r
- </plugin>\r
- </plugins>\r
- </build>\r
</project>\r
package jp.sourceforge.stigmata.birthmarks.wsp;
-/*
- * $Id$
- */
-
/**
*
* @author Haruaki Tamada
- * @version $Revision$
*/
public class CurrentDepth{
private WSPOpcode opcode;
return opcode;
}
+ @Override
public String toString(){
- return String.format("%d:%d:%d:%d", opcode.getOpcode(), depth, opcode.getWeight(), opcode.getAct());
+ return String.format(
+ "%d:%d:%d:%d", opcode.getOpcode(),
+ depth, opcode.getWeight(), opcode.getAct()
+ );
}
}
package jp.sourceforge.stigmata.birthmarks.wsp;
-/*
- * $Id$
- */
-
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import jp.sourceforge.stigmata.BirthmarkContext;
import jp.sourceforge.stigmata.birthmarks.AbstractBirthmarkPreprocessor;
-import jp.sourceforge.stigmata.birthmarks.Opcode;
-import jp.sourceforge.stigmata.birthmarks.OpcodeExtractMethodVisitor;
+import jp.sourceforge.stigmata.cflib.Opcode;
+import jp.sourceforge.stigmata.cflib.OpcodeExtractMethodVisitor;
import jp.sourceforge.stigmata.digger.ClassFileArchive;
import jp.sourceforge.stigmata.digger.ClassFileEntry;
-import jp.sourceforge.stigmata.spi.BirthmarkSpi;
+import jp.sourceforge.stigmata.spi.BirthmarkService;
-import org.objectweb.asm.ClassAdapter;
import org.objectweb.asm.ClassReader;
+import org.objectweb.asm.ClassVisitor;
import org.objectweb.asm.ClassWriter;
import org.objectweb.asm.MethodVisitor;
+import org.objectweb.asm.Opcodes;
/**
*
* @author Haruaki Tamada
- * @version $Revision$
*/
-public class OpcodeWeightCalculatePreprocessor extends AbstractBirthmarkPreprocessor{
- public OpcodeWeightCalculatePreprocessor(BirthmarkSpi spi){
+public class OpcodeWeightCalculatePreprocessor
+ extends AbstractBirthmarkPreprocessor{
+ public OpcodeWeightCalculatePreprocessor(BirthmarkService spi){
super(spi);
}
@Override
- public void preprocess(ClassFileArchive[] targets, BirthmarkContext context){
+ public void preprocess(ClassFileArchive[] targets,
+ BirthmarkContext context){
Map<Integer, Integer> targetMap = new HashMap<Integer, Integer>();
int classCount = 0;
context.putProperty("birthmarks.wsp.weights", weights);
}
- private int readOpcodes(ClassFileArchive archive, Map<Integer, Integer> targetMap){
+ private int readOpcodes(ClassFileArchive archive,
+ Map<Integer, Integer> targetMap){
int count = 0;
for(ClassFileEntry entry: archive){
count++;
ClassReader reader = new ClassReader(in);
ClassWriter writer = new ClassWriter(0);
- ClassAdapter opcodeExtractVisitor = new ClassAdapter(writer){
+ ClassVisitor opcodeExtractVisitor = new ClassVisitor(Opcodes.ASM4, writer){
@Override
- public MethodVisitor visitMethod(int arg0, String arg1, String arg2, String arg3, String[] arg4){
+ public MethodVisitor visitMethod(
+ int arg0, String arg1, String arg2,
+ String arg3, String[] arg4){
OpcodeExtractMethodVisitor visitor =
- new OpcodeExtractMethodVisitor(super.visitMethod(arg0, arg1, arg2, arg3, arg4), opcodes);
+ new OpcodeExtractMethodVisitor(
+ super.visitMethod(arg0, arg1, arg2, arg3, arg4),
+ opcodes
+ );
return visitor;
}
};
package jp.sourceforge.stigmata.birthmarks.wsp;
-/*
- * $Id$
- */
-
import jp.sourceforge.stigmata.Birthmark;
import jp.sourceforge.stigmata.BirthmarkContext;
import jp.sourceforge.stigmata.BirthmarkElement;
import jp.sourceforge.stigmata.birthmarks.comparators.AbstractBirthmarkComparator;
-import jp.sourceforge.stigmata.spi.BirthmarkSpi;
+import jp.sourceforge.stigmata.spi.BirthmarkService;
/**
*
* @author Haruaki Tamada
- * @version $Revision$
*/
-public class StackPatternBasedBirthmarkComparator extends AbstractBirthmarkComparator{
- public StackPatternBasedBirthmarkComparator(BirthmarkSpi spi){
+public class StackPatternBasedBirthmarkComparator
+ extends AbstractBirthmarkComparator{
+ public StackPatternBasedBirthmarkComparator(BirthmarkService spi){
super(spi);
}
@Override
- public double compare(Birthmark b1, Birthmark b2, BirthmarkContext context){
+ public double compare(Birthmark b1, Birthmark b2,
+ BirthmarkContext context){
int[][] wcs = createMatrix(b1, b2);
int weightOfWcs = new WeightCalculator().calculateWeight(wcs);
int weightOfBirthmark1 = 0;
for(BirthmarkElement element: b1){
- weightOfBirthmark1 += ((StackPatternBasedBirthmarkElement)element).getWeight();
+ weightOfBirthmark1 +=
+ ((StackPatternBasedBirthmarkElement)element).getWeight();
}
return (double)weightOfWcs / (double)weightOfBirthmark1;
int[][] matrix = new int[elementsA.length][elementsB.length];
for(int i = 0; i < elementsA.length; i++){
for(int j = 0; j < elementsB.length; j++){
- StackPatternBasedBirthmarkElement wsp1 = (StackPatternBasedBirthmarkElement)elementsA[i];
- StackPatternBasedBirthmarkElement wsp2 = (StackPatternBasedBirthmarkElement)elementsB[j];
+ StackPatternBasedBirthmarkElement wsp1 =
+ (StackPatternBasedBirthmarkElement)elementsA[i];
+ StackPatternBasedBirthmarkElement wsp2 =
+ (StackPatternBasedBirthmarkElement)elementsB[j];
matrix[i][j] = wsp1.getWeight(wsp2);
}
}
package jp.sourceforge.stigmata.birthmarks.wsp;
-/*
- * $Id$
- */
-
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import jp.sourceforge.stigmata.BirthmarkElement;
-import jp.sourceforge.stigmata.birthmarks.Opcode;
-import jp.sourceforge.stigmata.birthmarks.OpcodeManager;
+import jp.sourceforge.stigmata.cflib.Opcode;
+import jp.sourceforge.stigmata.cflib.OpcodeManager;
/**
*
* @author Haruaki TAMADA
- * @version $Revision$
*/
-public class StackPatternBasedBirthmarkElement extends BirthmarkElement implements Iterable<CurrentDepth>{
+public class StackPatternBasedBirthmarkElement
+ extends BirthmarkElement implements Iterable<CurrentDepth>{
private static final long serialVersionUID = 7965456413167854L;
private List<CurrentDepth> list = new ArrayList<CurrentDepth>();
int weight = Integer.parseInt(depthStringArray[2]);
int act = Integer.parseInt(depthStringArray[3]);
- WSPOpcode o = new WSPOpcode(OpcodeManager.getInstance().getOpcode(opcode), weight);
- if(o.getCategory() == Opcode.Category.OBJECT || o.getCategory() == Opcode.Category.INVOKE){
+ WSPOpcode o = new WSPOpcode(
+ OpcodeManager.getInstance().getOpcode(opcode), weight
+ );
+ if(o.getCategory() == Opcode.Category.FIELD
+ || o.getCategory() == Opcode.Category.INVOKE){
o.setAct(act);
}
list.add(new CurrentDepth(depth, o));
return list.get(index);
}
+ @Override
public Iterator<CurrentDepth> iterator(){
return Collections.unmodifiableList(list).iterator();
}
if(i == 0 || j == 0){
matrix[i][j] = 0;
}
- else if(element.getDepth(i - 1).getOpcode().getOpcode() == getDepth(j - 1).getOpcode().getOpcode()){
- matrix[i][j] = (int)(matrix[i - 1][j - 1] + getDepth(j - 1).getOpcode().getWeight());
+ else if(element.getDepth(i - 1).getOpcode().getOpcode()
+ == getDepth(j - 1).getOpcode().getOpcode()){
+ matrix[i][j] = (int)(
+ matrix[i - 1][j - 1]
+ + getDepth(j - 1).getOpcode().getWeight()
+ );
}
else{
- matrix[i][j] = Math.max(matrix[i - 1][j], matrix[i][j - 1]);
+ matrix[i][j] =
+ Math.max(matrix[i - 1][j], matrix[i][j - 1]);
}
}
}
package jp.sourceforge.stigmata.birthmarks.wsp;
-/*
- * $Id$
- */
-
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import jp.sourceforge.stigmata.BirthmarkElement;
import jp.sourceforge.stigmata.ExtractionUnit;
import jp.sourceforge.stigmata.birthmarks.ASMBirthmarkExtractor;
-import jp.sourceforge.stigmata.birthmarks.BirthmarkElementBuilder;
import jp.sourceforge.stigmata.birthmarks.BirthmarkExtractVisitor;
-import jp.sourceforge.stigmata.birthmarks.LabelOpcode;
-import jp.sourceforge.stigmata.birthmarks.Opcode;
-import jp.sourceforge.stigmata.birthmarks.OpcodeExtractVisitor;
-import jp.sourceforge.stigmata.spi.BirthmarkSpi;
+import jp.sourceforge.stigmata.cflib.BirthmarkElementBuilder;
+import jp.sourceforge.stigmata.cflib.LabelOpcode;
+import jp.sourceforge.stigmata.cflib.Opcode;
+import jp.sourceforge.stigmata.cflib.OpcodeExtractVisitor;
+import jp.sourceforge.stigmata.spi.BirthmarkService;
-import org.objectweb.asm.ClassVisitor;
+import org.objectweb.asm.ClassWriter;
import org.objectweb.asm.Label;
/**
*
* @author Haruaki Tamada
- * @version $Revision$
*/
-public class StackPatternBasedBirthmarkExtractor extends ASMBirthmarkExtractor{
- public StackPatternBasedBirthmarkExtractor(BirthmarkSpi service){
+public class StackPatternBasedBirthmarkExtractor
+ extends ASMBirthmarkExtractor{
+ public StackPatternBasedBirthmarkExtractor(BirthmarkService service){
super(service);
}
@Override
- public BirthmarkExtractVisitor createExtractVisitor(ClassVisitor visitor, Birthmark birthmark, BirthmarkContext context){
- return new OpcodeExtractVisitor(visitor, birthmark, context, new WSPBirthmarkElementBuilder());
+ public BirthmarkExtractVisitor createExtractVisitor(
+ ClassWriter writer, Birthmark birthmark,
+ BirthmarkContext context){
+
+ return new OpcodeExtractVisitor(
+ writer, birthmark, context, new WSPBirthmarkElementBuilder()
+ );
}
@Override
};
}
- private static class WSPBirthmarkElementBuilder implements BirthmarkElementBuilder{
- public BirthmarkElement[] buildElements(List<Opcode> opcodes, BirthmarkContext context){
+ private static class WSPBirthmarkElementBuilder
+ implements BirthmarkElementBuilder{
+ @Override
+ public BirthmarkElement[] buildElements(List<Opcode> opcodes,
+ BirthmarkContext context){
List<CurrentDepth> pattern = buildStackPattern(opcodes, context);
- List<BirthmarkElement> elements = new ArrayList<BirthmarkElement>();
+ List<BirthmarkElement> elements =
+ new ArrayList<BirthmarkElement>();
List<CurrentDepth> subPattern = new ArrayList<CurrentDepth>();
for(CurrentDepth depth: pattern){
subPattern.add(depth);
if(depth.getDepth() == 0){
- elements.add(new StackPatternBasedBirthmarkElement(subPattern.toArray(new CurrentDepth[subPattern.size()])));
+ elements.add(
+ new StackPatternBasedBirthmarkElement(
+ subPattern.toArray(
+ new CurrentDepth[subPattern.size()]
+ )
+ )
+ );
subPattern.clear();
}
}
- elements.add(new StackPatternBasedBirthmarkElement(subPattern.toArray(new CurrentDepth[subPattern.size()])));
+ elements.add(
+ new StackPatternBasedBirthmarkElement(
+ subPattern.toArray(new CurrentDepth[subPattern.size()])
+ )
+ );
return elements.toArray(new BirthmarkElement[elements.size()]);
}
@SuppressWarnings("unchecked")
- private List<CurrentDepth> buildStackPattern(List<Opcode> opcodes, BirthmarkContext context){
+ private List<CurrentDepth> buildStackPattern(List<Opcode> opcodes,
+ BirthmarkContext context){
Map<Label, Integer> tableMap = new HashMap<Label, Integer>();
List<CurrentDepth> pattern = new ArrayList<CurrentDepth>();
- Map<Integer, Integer> weights = (Map<Integer, Integer>)context.getProperty("birthmarks.wsp.weights");
+ Map<Integer, Integer> weights =
+ (Map<Integer, Integer>)context.getProperty(
+ "birthmarks.wsp.weights"
+ );
int currentDepth = 0;
Integer forwardedStatus = null;
for(Opcode opcode: opcodes){
if(opcode.getCategory() == Opcode.Category.TARGETER){
- forwardedStatus = tableMap.get(((LabelOpcode)opcode).getLabel());
+ forwardedStatus =
+ tableMap.get(((LabelOpcode)opcode).getLabel());
}
else{
- WSPOpcode wspOpcode = new WSPOpcode(opcode, weights.get(opcode.getOpcode()));
+ WSPOpcode wspOpcode = new WSPOpcode(
+ opcode, weights.get(opcode.getOpcode())
+ );
if(forwardedStatus == null){
currentDepth += opcode.getAct();
}
}
return pattern;
}
+ }
+
+ @Override
+ public BirthmarkElement buildElement(String value){
+ return new StackPatternBasedBirthmarkElement(value);
};
}
package jp.sourceforge.stigmata.birthmarks.wsp;
-/*
- * $Id$
- */
-
import jp.sourceforge.stigmata.BirthmarkComparator;
-import jp.sourceforge.stigmata.BirthmarkElement;
import jp.sourceforge.stigmata.BirthmarkExtractor;
import jp.sourceforge.stigmata.BirthmarkPreprocessor;
-import jp.sourceforge.stigmata.birthmarks.AbstractBirthmarkService;
+import jp.sourceforge.stigmata.spi.BirthmarkService;
/**
* Weighted Stack Pattern based birthmark.
* Patterns,'' IEICE Transactions on Information and Systems, Vol.E91-D No.9
* pp.2323-2332, September 2008.</li>
* <li>Heewan Park, Hyun-il Lim, Seokwoo Choi and Taisook Han, ``A Static Java
- * Birthmark Based on Operand Stack Behaviors,'' In Proc. of 2008 International
- * Conference on Information Security and Assurance, pp.133-136, April 2008.</li>
+ * Birthmark Based on Operand Stack Behaviors,'' In Proc. of 2008
+ * International Conference on Information Security and Assurance,
+ * pp.133-136, April 2008.</li>
* </ul>
*
* @author Haruaki Tamada
- * @version $Revision$
*/
-public class StackPatternBasedBirthmarkService extends AbstractBirthmarkService{
- private BirthmarkPreprocessor preprocessor = new OpcodeWeightCalculatePreprocessor(this);
- private BirthmarkExtractor extractor = new StackPatternBasedBirthmarkExtractor(this);
- private BirthmarkComparator comparator = new StackPatternBasedBirthmarkComparator(this);
+public class StackPatternBasedBirthmarkService implements BirthmarkService{
+ private BirthmarkPreprocessor preprocessor =
+ new OpcodeWeightCalculatePreprocessor(this);
+ private BirthmarkExtractor extractor =
+ new StackPatternBasedBirthmarkExtractor(this);
+ private BirthmarkComparator comparator =
+ new StackPatternBasedBirthmarkComparator(this);
@Override
- public String getDefaultDescription(){
+ public String getDescription(){
return "Weighted stack pattern based birthmark";
}
return false;
}
- @Override
public boolean isExperimental(){
- return true;
+ return false;
}
@Override
public BirthmarkPreprocessor getPreprocessor(){
return preprocessor;
}
-
- @Override
- public BirthmarkElement buildBirthmarkElement(String value){
- return new StackPatternBasedBirthmarkElement(value);
- }
-
- @Override
- public String getDisplayType(){
- return "Weighted Stack Pattern Based Birthmark";
- }
}
package jp.sourceforge.stigmata.birthmarks.wsp;\r
\r
-/*\r
- * $Id$\r
- */\r
-\r
-import jp.sourceforge.stigmata.birthmarks.Opcode;\r
+import jp.sourceforge.stigmata.cflib.Opcode;\r
\r
/**\r
*\r
*\r
- * @author tamada\r
- * @version $Revision$\r
+ * @author Haruaki Tamada\r
*/\r
public class WSPOpcode extends Opcode {\r
private static final long serialVersionUID = 31469629831901737L;\r
\r
private int weight;\r
\r
- public WSPOpcode(int opcode, String name, int argumentCount, int act, Category category) {\r
+ public WSPOpcode(int opcode, String name, int argumentCount,\r
+ int act, Category category) {\r
super(opcode, name, argumentCount, act, category);\r
}\r
\r
- public WSPOpcode(int opcode, String name, int argumentCount, int act, String category) {\r
+ public WSPOpcode(int opcode, String name, int argumentCount,\r
+ int act, String category) {\r
super(opcode, name, argumentCount, act, category);\r
}\r
\r
super(opcode);\r
}\r
\r
- public WSPOpcode(int opcode, String name, int argumentCount, int act, Category category, int weight){\r
+ public WSPOpcode(int opcode, String name, int argumentCount,\r
+ int act, Category category, int weight){\r
this(opcode, name, argumentCount, act, category);\r
\r
setWeight(weight);\r
return weight;\r
}\r
\r
+ @Override\r
public String toString(){\r
- return String.format("%d:%s:%d:%f(%s)", getOpcode(), getName(), getWeight(), getAct(), getCategory());\r
+ return String.format(\r
+ "%d:%s:%d:%f(%s)", getOpcode(), getName(),\r
+ getWeight(), getAct(), getCategory()\r
+ );\r
}\r
}\r
package jp.sourceforge.stigmata.birthmarks.wsp;
+/**
+ * Weight を計算するためのクラス.
+ *
+ * @author Haruaki Tamada
+ */
public class WeightCalculator{
-
public int calculateWeight(int[][] wcs){
int weight = 0;
boolean[][] availableFlag = new boolean[wcs.length][wcs[0].length];
\r
<body>\r
<menu name="WSP" inherit="top">\r
- <item name="Introduction" href="wsp/index.html"/>\r
+ <item name="Introduction" href="index.html"/>\r
<item name="How to install" href="install.html" />\r
<item name="Download" href="download.html"/>\r
</menu>\r
package jp.sourceforge.stigmata.birthmarks.wsp;
-/*
- * $Id$
- */
-
-import jp.sourceforge.stigmata.birthmarks.Opcode;
+import jp.sourceforge.stigmata.cflib.Opcode;
import org.junit.Assert;
import org.junit.Before;
@Before
public void setup(){
- opcode = new WSPOpcode(4, "iconst_1", 0, 1, Opcode.Category.NORMAL);
+ opcode = new WSPOpcode(4, "iconst_1", 0, 1, Opcode.Category.CONSTANT);
depth = new CurrentDepth(3, opcode);
}
package jp.sourceforge.stigmata.birthmarks.wsp;
-/*
- * $Id$
- */
-
-import jp.sourceforge.stigmata.birthmarks.Opcode;
+import jp.sourceforge.stigmata.cflib.Opcode;
import org.junit.Assert;
import org.junit.Before;
public void setup(){
CurrentDepth[] depthList = new CurrentDepth[7];
- depthList[0] = new CurrentDepth(1, new WSPOpcode( 26, "iload_0", 0, 1, Opcode.Category.NORMAL, 7));
- depthList[1] = new CurrentDepth(2, new WSPOpcode( 26, "iload_0", 0, 1, Opcode.Category.NORMAL, 7));
- depthList[2] = new CurrentDepth(3, new WSPOpcode( 4, "iconst_1", 0, 1, Opcode.Category.NORMAL, 1));
- depthList[3] = new CurrentDepth(2, new WSPOpcode(100, "isub", 0, -1, Opcode.Category.NORMAL, 4));
+ depthList[0] = new CurrentDepth(1, new WSPOpcode( 26, "iload_0", 0, 1, Opcode.Category.LOAD, 7));
+ depthList[1] = new CurrentDepth(2, new WSPOpcode( 26, "iload_0", 0, 1, Opcode.Category.LOAD, 7));
+ depthList[2] = new CurrentDepth(3, new WSPOpcode( 4, "iconst_1", 0, 1, Opcode.Category.CONSTANT, 1));
+ depthList[3] = new CurrentDepth(2, new WSPOpcode(100, "isub", 0, -1, Opcode.Category.SUBTRACT, 4));
depthList[4] = new CurrentDepth(2, new WSPOpcode(184, "invokestatic", 2, 0, Opcode.Category.INVOKE, 1));
- depthList[5] = new CurrentDepth(1, new WSPOpcode(104, "imul", 0, -1, Opcode.Category.NORMAL, 6));
- depthList[6] = new CurrentDepth(0, new WSPOpcode(172, "ireturn", 0, -1, Opcode.Category.NORMAL, 2));
+ depthList[5] = new CurrentDepth(1, new WSPOpcode(104, "imul", 0, -1, Opcode.Category.MULTIPLY, 6));
+ depthList[6] = new CurrentDepth(0, new WSPOpcode(172, "ireturn", 0, -1, Opcode.Category.RETURN, 2));
element = new StackPatternBasedBirthmarkElement(depthList);
}
@Test
public void testCalculateWeightedCommonSubsequence(){
CurrentDepth[] depthList = new CurrentDepth[10];
- depthList[0] = new CurrentDepth(1, new WSPOpcode( 26, "iload_0", 0, 1, Opcode.Category.NORMAL, 7));
- depthList[1] = new CurrentDepth(2, new WSPOpcode( 4, "iconst_1", 0, 1, Opcode.Category.NORMAL, 1));
- depthList[2] = new CurrentDepth(1, new WSPOpcode(100, "isub", 0, -1, Opcode.Category.NORMAL, 4));
+ depthList[0] = new CurrentDepth(1, new WSPOpcode( 26, "iload_0", 0, 1, Opcode.Category.LOAD, 7));
+ depthList[1] = new CurrentDepth(2, new WSPOpcode( 4, "iconst_1", 0, 1, Opcode.Category.CONSTANT, 1));
+ depthList[2] = new CurrentDepth(1, new WSPOpcode(100, "isub", 0, -1, Opcode.Category.SUBTRACT, 4));
depthList[3] = new CurrentDepth(1, new WSPOpcode(184, "invokestatic", 2, 0, Opcode.Category.INVOKE, 1));
- depthList[4] = new CurrentDepth(2, new WSPOpcode( 26, "iload_0", 0, 1, Opcode.Category.NORMAL, 7));
- depthList[5] = new CurrentDepth(3, new WSPOpcode( 5, "iconst_2", 0, 1, Opcode.Category.NORMAL, 1));
- depthList[6] = new CurrentDepth(2, new WSPOpcode(100, "isub", 0, -1, Opcode.Category.NORMAL, 4));
+ depthList[4] = new CurrentDepth(2, new WSPOpcode( 26, "iload_0", 0, 1, Opcode.Category.LOAD, 7));
+ depthList[5] = new CurrentDepth(3, new WSPOpcode( 5, "iconst_2", 0, 1, Opcode.Category.CONSTANT, 1));
+ depthList[6] = new CurrentDepth(2, new WSPOpcode(100, "isub", 0, -1, Opcode.Category.SUBTRACT, 4));
depthList[7] = new CurrentDepth(2, new WSPOpcode(184, "invokestatic", 2, 0, Opcode.Category.INVOKE, 1));
- depthList[8] = new CurrentDepth(1, new WSPOpcode( 96, "iadd", 0, -1, Opcode.Category.NORMAL, 3));
- depthList[9] = new CurrentDepth(0, new WSPOpcode(172, "ireturn", 0, -1, Opcode.Category.NORMAL, 2));
+ depthList[8] = new CurrentDepth(1, new WSPOpcode( 96, "iadd", 0, -1, Opcode.Category.ADD, 3));
+ depthList[9] = new CurrentDepth(0, new WSPOpcode(172, "ireturn", 0, -1, Opcode.Category.RETURN, 2));
StackPatternBasedBirthmarkElement pattern2 = new StackPatternBasedBirthmarkElement(depthList);
Assert.assertEquals(21, element.getWeight(pattern2));
package jp.sourceforge.stigmata.birthmarks.wsp;
-/*
- * $Id$
- */
-
import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;