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
}\r
}\r
+ for(Label label: exceptionFlows){\r
+ targets.add(label);\r
+ }\r
\r
return targets.toArray(new Label[targets.size()]);\r
}\r
prevs.add(block);\r
}\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
- Label[] targets = getTargets();\r
sb.append(ln).append("Targeter: ");\r
- for(Label label: targets){\r
+ for(Label label: getTargets()){\r
sb.append(label).append(", ");\r
}\r
return new String(sb);\r
}\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
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.TableSwitchInsnNode;\r
import org.objectweb.asm.tree.TryCatchBlockNode;\r
\r
-import com.sun.xml.internal.ws.org.objectweb.asm.Opcodes;\r
-\r
public class ControlFlowGraph {\r
private String name;\r
private boolean includeException;\r
matrix[i][j] = nextValue;\r
}\r
}\r
+\r
return matrix;\r
}\r
\r
}\r
\r
private Set<LabelNode> collectLabels(MethodNode node){\r
- Set<LabelNode> jumpedTarget = new HashSet<LabelNode>();\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
case AbstractInsnNode.JUMP_INSN:\r
{\r
JumpInsnNode jump = (JumpInsnNode)inst;\r
- jumpedTarget.add(jump.label);\r
+ jumpTarget.add(jump.label);\r
break;\r
}\r
case AbstractInsnNode.LOOKUPSWITCH_INSN:\r
{\r
LookupSwitchInsnNode lookup = (LookupSwitchInsnNode)inst;\r
- jumpedTarget.add(lookup.dflt);\r
+ jumpTarget.add(lookup.dflt);\r
for(Object label: lookup.labels){\r
- jumpedTarget.add((LabelNode)label);\r
+ jumpTarget.add((LabelNode)label);\r
}\r
break;\r
}\r
case AbstractInsnNode.TABLESWITCH_INSN:\r
{\r
TableSwitchInsnNode lookup = (TableSwitchInsnNode)inst;\r
- jumpedTarget.add(lookup.dflt);\r
+ jumpTarget.add(lookup.dflt);\r
for(Object label: lookup.labels){\r
- jumpedTarget.add((LabelNode)label);\r
+ jumpTarget.add((LabelNode)label);\r
}\r
break;\r
}\r
}\r
if(isIncludingExceptionFlow()){\r
for(Object object: node.tryCatchBlocks){\r
- jumpedTarget.add(((TryCatchBlockNode)object).handler);\r
+ jumpTarget.add(((TryCatchBlockNode)object).handler);\r
+ }\r
+ }\r
+ return jumpTarget;\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 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
- return jumpedTarget;\r
}\r
\r
- private BasicBlock[] separateBasicBlock(MethodNode node, Set<LabelNode> jumpedTarget){\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(jumpedTarget.contains(inst)){\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.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
block2.setPrev(block);\r
}\r
block = block2;\r
+ block.exceptionFlows.addAll(exceptionFlows);\r
}\r
}\r
}\r
- blockList.add(block);\r
+ if(!block.isEmpty()){\r
+ blockList.add(block);\r
+ }\r
return blockList.toArray(new BasicBlock[blockList.size()]);\r
}\r
\r
}\r
}\r
}\r
- if(labels.length == 0 && (i + 1) < blocks.length){\r
+ if((i + 1) < blocks.length && blocks[i].isFlowNext()){\r
blocks[i].setNext(blocks[i + 1]);\r
}\r
}\r
}\r
\r
private void parse(MethodNode node){\r
- Set<LabelNode> jumpedTarget = collectLabels(node);\r
- BasicBlock[] blocks = separateBasicBlock(node, jumpedTarget);\r
+ Set<LabelNode> jumpTarget = collectLabels(node);\r
+ BasicBlock[] blocks = separateBasicBlock(node, jumpTarget);\r
this.blocks = joinBasicBlocks(blocks);\r
}\r
}\r
import org.objectweb.asm.ClassWriter;\r
\r
public class ControlFlowGraphTest {\r
- private ControlFlowGraphExtractVisitor visitor;\r
+ private ControlFlowGraphExtractVisitor cfVisitor;\r
+ private ControlFlowGraphExtractVisitor cfVisitor2;\r
\r
@Before\r
public void setUp() throws Exception{\r
- ClassReader reader = new ClassReader(getClass().getResource("/resources/MyServer.class").openStream());\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
- visitor = new ControlFlowGraphExtractVisitor(new ClassWriter(0));\r
- reader.accept(visitor, 0);\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 = visitor.getMethodNames();\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 = visitor.getGraph("<init>(I)V");\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
}\r
\r
@Test\r
- public void testGraph() throws Exception{\r
- ControlFlowGraph graph = visitor.getGraph("<init>(I)V");\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
import java.io.*;
import java.net.*;
-public class MyServer{
+public class MyServer2{
private int port;
private ServerSocket server;
- public MyServer(int defaultPort){
+ public MyServer2(int defaultPort){
try{
if(defaultPort > 0){
port = defaultPort;
--- /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