Определить циклы в java-байтовом коде

Ответ 1

EDIT 4: немного фона/преамбулы.

• "Единственный способ перепрыгнуть назад в коде - через цикл". в Питере ответ не является строгим. Вы можете прыгать туда и обратно, не имея в виду петлю. Упрощенный случай будет примерно таким:

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

  Конечно, этот конкретный пример очень искусственный и немного глупый. Однако предположение о том, как будет работать компилятор от источника к байт-коду, может привести к неожиданностям. Как Питер и я показали в наших соответствующих ответах, два популярных компилятора могут производить довольно различный результат (даже без обфускации). Это редко имеет значение, потому что все это, как правило, оптимизируется JIT-компилятором при выполнении кода. При этом в подавляющем большинстве случаев прыжки назад будут разумным указанием на то, где начинается цикл. По сравнению с остальными, поиск точки входа цикла является "легкой" частью.

• Прежде чем рассматривать любые инструменты запуска/выхода цикла, вы должны изучить определения того, что такое вход, выход и преемники. Хотя цикл имеет только одну точку входа, он может иметь несколько точек выхода и/или несколько преемников, обычно вызванных операторами break (иногда с метками), операторами return и/или исключениями (явно пойманными или нет). Хотя вы не указали подробные сведения о том, какие приборы вы изучаете, обязательно стоит подумать о том, где вы хотите вставить код (если это то, что вы хотите сделать). Как правило, некоторые инструменты могут потребоваться перед каждым оператором выхода или вместо каждого оператора-преемника (в этом случае вам придется переместить исходный оператор).

Soot является хорошей основой для этого. Он имеет ряд промежуточных представлений, которые делают анализ байт-кода более удобным (например, Jimple).

Вы можете создать BlockGraph на основе вашего тела метода, например ExceptionalBlockGraph., После того, как вы разделили граф потока управления на такой блок-граф, из узлов, вы должны иметь возможность идентифицировать доминанты (т.е. Блоки, у которых есть стрелка, возвращающаяся к ним). Это даст вам начало цикла.

Вы можете найти что-то подобное в разделе с 4.3 по 4.7 данной диссертации.

EDIT:

После обсуждения с @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:

Похоже, что новые классы/методы для анализа циклов были добавлены с прошлого времени, когда я смотрел на Саут, что делает его немного более удобным.

Вот полный пример.

Класс/метод для анализа (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());
        }
    }
}

За дополнительной информацией о загрузке классов обратитесь к документации по саже. 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;

Loops:

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 предоставит вам инструкцию записи и инструкции exit. Затем вы можете добавить дополнительные заявления, если хотите. Jimple довольно удобен для этого (он достаточно близко к байт-коду, но имеет несколько более высокий уровень, чтобы не разобраться со всем вручную). Затем вы можете вывести ваш модифицированный файл .class, если это необходимо. (Для этого см. Документацию по саже.)

Ответ 2

Единственный способ перепрыгнуть назад в коде - через цикл. Таким образом, вы ищете 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, блок try/catch между 0 и 15 и внешний цикл между 0 и 22.

Ответ 3

На самом деле вы строите байт по байтам класса? Это довольно дико! На первой странице ASM ссылается на плагин Bytecode Outline для Eclipse, который, как я полагаю, вы используете. Если вы нажмете на первое изображение там, вы заметите, что код имеет цикл while, и вы можете увидеть по крайней мере часть байтового кода, используемого для реализации этого цикла. Для справки: скриншот:

Прямая ссылка

Похоже, что циклы просто реализованы как GOTO с пограничной проверкой. Я говорю об этой строке:

L2 (173)
  GOTO L3

Я уверен, что маркер L3 имеет код для проверки привязки индекса и решил использовать JMP. Я думаю, что это будет довольно сложно для вас, если вы хотите, чтобы инструмент зацикливал по одному байтовому коду за раз. У ASM есть возможность использовать класс шаблона в качестве основы для вашей аппаратуры, попробовали ли вы его использовать?