识别 java 字节码中的循环

编辑4：一些背景/前言。

• "在代码中向后跳转的唯一方法是通过一个循环。在彼得的回答中，严格来说不是真的。你可以来回跳跃，而这并不意味着它是一个循环。简化的情况是这样的：

  0: goto 2
  1: goto 3
  2: goto 1
  

  当然，这个特殊的例子是非常人为的，有点愚蠢。但是，对源代码到字节码编译器的行为方式进行假设可能会导致意外。正如 Peter 和我在各自的答案中所展示的那样，两个流行的编译器可以产生一个相当不同的输出（即使没有混淆）。这并不重要，因为在执行代码时，JIT 编译器往往会很好地优化所有这些。话虽如此，在绝大多数情况下，向后跳跃将是循环从哪里开始的合理指示。与其他部分相比，找出循环的入口点是“容易”的部分。

• 在考虑任何循环开始/退出检测之前，您应该研究什么是进入，退出和后续任务的定义。尽管循环只有一个入口点，但它可能具有多个退出点和/或多个后续节点，这通常是由语句（有时带有标签）、语句和/或异常（显式捕获或不显式捕获）引起的。虽然您尚未提供有关正在调查的检测类型的详细信息，但当然值得考虑要插入代码的位置（如果这是您要执行的操作）。通常，某些检测可能必须在每个 exit 语句之前完成，或者代替每个后续语句完成（在这种情况下，您必须移动原始语句）。breakreturn

烟灰是一个很好的框架。它具有许多中间表示形式，使字节码分析更加方便（例如Jimple）。

您可以基于方法主体构建块图，例如异常块图。一旦你将控制流图分解成这样一个块图，从节点，你应该能够识别支配者（即有一个箭头回到它们的块）。这将为您提供循环的开始。

您可能会在本论文的第4.3至4.7节中找到类似的事情。

编辑：

在讨论之后，@Peter评论他的答案。说同样的例子：

public int foo(int i, int j) {
    while (true) {
        try {
            while (i < j)
                i = j++ / i;
        } catch (RuntimeException re) {
            i = 10;
            continue;
        }
        break;
    }
    return j;
}

这次是使用Eclipse编译器编译的（没有特定的选项：简单地从IDE内部自动编译）。这段代码没有被混淆（除了是坏代码，但这是另一回事）。这是结果（来自）：javap -c

public int foo(int, int);
  Code:
   0:   goto    10
   3:   iload_2
   4:   iinc    2, 1
   7:   iload_1
   8:   idiv
   9:   istore_1
   10:  iload_1
   11:  iload_2
   12:  if_icmplt   3
   15:  goto    25
   18:  astore_3
   19:  bipush  10
   21:  istore_1
   22:  goto    10
   25:  iload_2
   26:  ireturn
  Exception table:
   from   to  target type
     0    15    18   Class java/lang/RuntimeException

在 3 和 12 之间有一个循环（从 10 开始跳转）和另一个循环，因为从 8 到 22 处的除以零时发生了异常。与编译器结果不同，人们可以猜测在0和22之间有一个外部循环，在0和12之间有一个内部循环，这里的嵌套不太明显。javac

编辑2：

为了说明你可能会遇到的问题，用一个不那么尴尬的例子。下面是一个相对简单的循环：

public void foo2() {
    for (int i = 0; i < 5; i++) {
        System.out.println(i);
    }
}

在 Eclipse 中（正常）编译之后，给出以下结果：javap -c

public void foo2();
  Code:
   0:   iconst_0
   1:   istore_1
   2:   goto    15
   5:   getstatic   #25; //Field java/lang/System.out:Ljava/io/PrintStream;
   8:   iload_1
   9:   invokevirtual   #31; //Method java/io/PrintStream.println:(I)V
   12:  iinc    1, 1
   15:  iload_1
   16:  iconst_5
   17:  if_icmplt   5
   20:  return

在循环中执行任何操作之前，您将从 2 直接跳到 15。块 15 到 17 是循环的标头（“入口点”）。有时，标头块可能包含更多的指令，特别是如果退出条件涉及更多的评估，或者它是一个循环。循环的“入口”和“退出”的概念可能并不总是反映你作为Java源代码明智地编写的内容（包括你可以将循环重写为循环的事实）。使用还可能导致多个出口点。do {} while()forwhilebreak

顺便说一句，通过“block”，我的意思是一个字节码序列，你不能跳进去，你不能从中间跳出来：它们只从第一行输入（不一定是从前一行输入的，可能从其他地方跳出来），然后从最后一行退出（不一定是从下一行， 它也可以跳到别的地方）。

编辑3：

自从我上次查看Soot以来，似乎已经添加了新的类/方法来分析循环，这使得它更加方便。

下面是一个完整的示例。

要分析的类/方法 （TestLoop.foo())

public class TestLoop {
    public void foo() {
        for (int j = 0; j < 2; j++) {
            for (int i = 0; i < 5; i++) {
                System.out.println(i);
            }
        }
    }
}

当由 Eclipse 编译器编译时，这将生成以下字节码 （）：javap -c

public void foo();
  Code:
   0:   iconst_0
   1:   istore_1
   2:   goto    28
   5:   iconst_0
   6:   istore_2
   7:   goto    20
   10:  getstatic   #25; //Field java/lang/System.out:Ljava/io/PrintStream;
   13:  iload_2
   14:  invokevirtual   #31; //Method java/io/PrintStream.println:(I)V
   17:  iinc    2, 1
   20:  iload_2
   21:  iconst_5
   22:  if_icmplt   10
   25:  iinc    1, 1
   28:  iload_1
   29:  iconst_2
   30:  if_icmplt   5
   33:  return

下面是一个程序，它使用 Soot 加载类（假设它位于此处的类路径上）并显示其块和循环：

import soot.Body;
import soot.Scene;
import soot.SootClass;
import soot.SootMethod;
import soot.jimple.toolkits.annotation.logic.Loop;
import soot.toolkits.graph.Block;
import soot.toolkits.graph.BlockGraph;
import soot.toolkits.graph.ExceptionalBlockGraph;
import soot.toolkits.graph.LoopNestTree;

public class DisplayLoops {
    public static void main(String[] args) throws Exception {
        SootClass sootClass = Scene.v().loadClassAndSupport("TestLoop");
        sootClass.setApplicationClass();

        Body body = null;
        for (SootMethod method : sootClass.getMethods()) {
            if (method.getName().equals("foo")) {
                if (method.isConcrete()) {
                    body = method.retrieveActiveBody();
                    break;
                }
            }
        }

        System.out.println("**** Body ****");
        System.out.println(body);
        System.out.println();

        System.out.println("**** Blocks ****");
        BlockGraph blockGraph = new ExceptionalBlockGraph(body);
        for (Block block : blockGraph.getBlocks()) {
            System.out.println(block);
        }
        System.out.println();

        System.out.println("**** Loops ****");
        LoopNestTree loopNestTree = new LoopNestTree(body);
        for (Loop loop : loopNestTree) {
            System.out.println("Found a loop with head: " + loop.getHead());
        }
    }
}

有关如何加载类的更多详细信息，请查看 Soot 文档。是循环主体的模型，即从字节码创建的所有语句。这使用中间的Jimple表示，它相当于字节码，但更容易分析和处理。Body

这是该程序的输出：

身体：

    public void foo()
    {
        TestLoop r0;
        int i0, i1;
        java.io.PrintStream $r1;

        r0 := @this: TestLoop;
        i0 = 0;
        goto label3;

     label0:
        i1 = 0;
        goto label2;

     label1:
        $r1 = <java.lang.System: java.io.PrintStream out>;
        virtualinvoke $r1.<java.io.PrintStream: void println(int)>(i1);
        i1 = i1 + 1;

     label2:
        if i1 < 5 goto label1;

        i0 = i0 + 1;

     label3:
        if i0 < 2 goto label0;

        return;
    }

块：

Block 0:
[preds: ] [succs: 5 ]
r0 := @this: TestLoop;
i0 = 0;
goto [?= (branch)];

Block 1:
[preds: 5 ] [succs: 3 ]
i1 = 0;
goto [?= (branch)];

Block 2:
[preds: 3 ] [succs: 3 ]
$r1 = <java.lang.System: java.io.PrintStream out>;
virtualinvoke $r1.<java.io.PrintStream: void println(int)>(i1);
i1 = i1 + 1;

Block 3:
[preds: 1 2 ] [succs: 4 2 ]
if i1 < 5 goto $r1 = <java.lang.System: java.io.PrintStream out>;

Block 4:
[preds: 3 ] [succs: 5 ]
i0 = i0 + 1;

Block 5:
[preds: 0 4 ] [succs: 6 1 ]
if i0 < 2 goto i1 = 0;

Block 6:
[preds: 5 ] [succs: ]
return;

循环：

Found a loop with head: if i1 < 5 goto $r1 = <java.lang.System: java.io.PrintStream out>
Found a loop with head: if i0 < 2 goto i1 = 0

LoopNestTree使用LoopFinder，它使用来构建块列表。Loop 类将为您提供入口语句和退出语句。然后，如果您愿意，您应该能够添加额外的语句。Jimple非常方便（它足够接近字节码，但具有略高的级别，以免手动处理所有内容）。然后，您可以根据需要输出修改后的文件。（有关此内容，请参阅烟灰文档。ExceptionalBlockGraph.class

在代码中向后跳转的唯一方法是通过循环。所以你正在寻找一个goto，if_icmplt等，它进入以前的字节代码指令。一旦你找到了循环的终点，并且它跳回到哪里，就是循环的开始。

这是一个复杂的例子，来自布鲁诺建议的文件。

public int foo(int i, int j) {
    while (true) {
        try {
            while (i < j)
                i = j++ / i;
        } catch (RuntimeException re) {
            i = 10;
            continue;
        }
        break;
    }
    return j;
}

此参数的字节码显示为javap -c

public int foo(int, int);
  Code:
   0:   iload_1
   1:   iload_2
   2:   if_icmpge       15
   5:   iload_2
   6:   iinc    2, 1
   9:   iload_1
   10:  idiv
   11:  istore_1
   12:  goto    0
   15:  goto    25
   18:  astore_3
   19:  bipush  10
   21:  istore_1
   22:  goto    0
   25:  iload_2
   26:  ireturn
  Exception table:
   from   to  target type
     0    15    18   Class java/lang/RuntimeException

您可以看到 0 和 12 之间有一个内循环，0 到 15 之间有一个 try/catch 块，0 到 22 之间有一个外循环。