识别Java字节码中的循环

Question

我正在尝试检测Java字节码。

我想识别 java循环 的 进入和退出 ，但是我发现识别循环非常具有挑战性。我花了很多时间研究 ASM 和 开源反编译器
（我一直认为自己必须始终解决此问题），但是我的想法很短。

我正在扩充/扩展的工具正在使用ASM，因此理想情况下， 我想知道如何通过ASM在Java中检测不同循环结构的进入和退出
。但是，我也欢迎关于一个好的开源反编译器的建议，因为显然他们可以解决相同的问题。

Answer 1

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

• “ 在代码中向后跳的唯一方法是通过循环。 ”在彼得的回答中，这并非完全正确。您可以来回跳动，而不意味着它是一个循环。一个简化的情况将是这样的：

  0: goto 2
  

  1: goto 3
  2: goto 1
  

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

• 在考虑任何循环启动/退出检测之前，您应该研究什么是进入，退出和后继。尽管一个循环只有一个入口点，但它可能有多个出口点和/或多个后继者，通常是由break语句（有时带有标签），return语句和/或异常（是否被明确捕获）引起的。尽管您没有提供有关正在调查的工具类型的详细信息，但是当然值得考虑您要在何处插入代码（如果您要这样做）。通常，可能需要在每个exit语句之前或每个后继语句之前进行某种检测（在这种情况下，您必须移动原始语句）。

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

您可以基于方法主体构建BlockGraph，例如ExceptionalBlockGraph。一旦将控制流图从节点分解成这样的框图，您就应该能够识别控制者（即，带有箭头的模块回到它们身上）。这将为您提供循环的起点。

您可能会在本文的第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处被零除而产生的异常。与javac编译器结果不同，其中一个可以猜测是有一个外部0到22之间的循环以及0到12之间的内部循环，在此嵌套不太明显。

编辑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是循环的标题（“入口”）。有时，标头块可能包含更多指令，尤其是在退出条件涉及更多评估或do {} while()循环的情况下。循环的“输入”和“退出”的概念可能并不总是反映您作为Java源代码明智地编写的内容（例如，包括您可以将for循环重写为while循环的事实）。使用break还会导致多个出口点。

顺便说一句，“块”是指一系列字节码，您不能跳入其中，也不能在中间跳出它们：它们仅从第一行输入（不一定从前一行输入）行，可能是从其他地方跳来的），然后从最后一行退出（不一定是下一行，它也可以跳到其他地方）。

编辑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文档以获取有关如何加载类的更多详细信息。这Body是循环主体的模型，即所有由字节码组成的语句。它使用中间的Jimple表示形式，该表示形式等效于字节码，但更易于分析和处理。

这是该程序的输出：

身体：

    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，它使用ExceptionalBlockGraph来构建块列表。该Loop班会给你进入语句和退出声明。然后，您可以根据需要添加其他语句。Jimple对此非常方便（它与字节码足够接近，但级别略高，以免手动处理所有内容）。然后，.class如果需要，您可以输出修改后的文件。（有关此信息，请参见Soot文档。）