Определить циклы в байт-коде Java
Я пытаюсь инструмент байт-код Java.
Я хочу распознать вход и выход из цикла Java, но я обнаружил, что идентификация циклов довольно сложна. Я потратил много часов на изучение ASM и декомпиляторов с открытым исходным кодом (которые, по моему мнению, должны решить эту проблему все время), однако я потерпел неудачу.
Инструмент, который я дополняю / расширяю, использует ASM, поэтому в идеале я хотел бы знать, как оборудовать вход и выход различных конструкций цикла в java через ASM. Тем не менее, я также приветствовал бы рекомендацию о хорошем декомпиляторе с открытым исходным кодом, поскольку очевидно, что они решили бы ту же проблему.
3 ответа
РЕДАКТИРОВАТЬ 4: немного фона / преамбулы.
" Единственный способ перейти назад в коде - использовать цикл ", - в ответе Питера не совсем верно. Вы можете прыгать туда-сюда без этого, означая, что это цикл. Упрощенный случай будет примерно таким:
0: goto 2 1: goto 3 2: goto 1Конечно, этот конкретный пример очень искусственный и немного глупый. Однако предположения о том, как будет вести себя компилятор исходного кода, могут привести к неожиданностям. Как мы с Питером показали в наших соответствующих ответах, два популярных компилятора могут выдавать довольно разные результаты (даже без запутывания). Это редко имеет значение, потому что все это имеет тенденцию довольно хорошо оптимизироваться компилятором JIT при выполнении кода. Это, как говорится, в подавляющем большинстве случаев, прыжок назад будет разумным указанием того, где начинается цикл. По сравнению с остальными, выяснение точки входа в цикл является "легкой" частью.
Прежде чем рассматривать любые инструменты запуска / выхода из цикла, вы должны посмотреть определения того, что такое вход, выход и преемники. Хотя цикл будет иметь только одну точку входа, он может иметь несколько точек выхода и / или несколько преемников, обычно вызванных
breakзаявления (иногда с ярлыками),returnзаявления и / или исключения (явно пойман или нет). Несмотря на то, что вы не предоставили подробных сведений о типе инструментария, который вы исследуете, безусловно, стоит подумать, куда вы хотите вставить код (если это то, что вы хотите сделать). Как правило, некоторые инструментарии, возможно, придется выполнять перед каждым оператором выхода или вместо каждого оператора-преемника (в этом случае вам придется переместить исходный оператор).
Сажа является хорошей основой для этого. Он имеет ряд промежуточных представлений, которые делают анализ байт-кода более удобным (например, 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 файл, если это необходимо. (См. Документацию по саже для этого.)
Единственный способ перейти назад в коде - использовать цикл. Итак, вы ищете 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.
Вы на самом деле строите свой класс за байтом? Это довольно дикий! Главная страница ASM ссылается на плагин Bytecode Outline для Eclipse, который, я полагаю, вы используете. Если вы нажмете на первое изображение там, вы заметите, что в коде есть цикл while, и вы можете увидеть хотя бы часть байтового кода, использованного для реализации этого цикла. Для справки вот этот скриншот:
Похоже, что циклы просто реализованы как GOTO с граничной проверкой. Я говорю об этой строке:
L2 (173)
GOTO L3
Я уверен, что маркер L3 имеет код для проверки привязки индекса и решил, стоит ли использовать JMP. Я думаю, что это будет довольно сложно для вас, если вы хотите, чтобы инструмент зацикливался по одному байту кода за раз. У ASM есть возможность использовать шаблонный класс в качестве основы для ваших инструментов, вы пробовали использовать его?
Я знаю, что это старый вопрос, однако был особый интерес к тому, как этого можно достичь с помощью библиотеки ASM, и это может быть полезно для будущих посетителей. Принимая во внимание предостережения, в других ответах предупреждают об обобщенных предположениях, связанных с оператором "goto", есть способ сделать это. (Это предполагает, что любая группировка кода в данном методе, которая может "зацикливаться", должна быть обнаружена - обычно это реальная конструкция цикла, но были предоставлены другие (редкие, но присутствующие) примеры того, как это может происходить.)
Главное, что вам нужно сделать, это отслеживать "метки" (местоположения в байтовом коде), которые ASM посещает до того, что он называет "инструкцией перехода" - если метка, на которую выполняется переход, уже встречалась в контекст того же метода, то у вас есть возможность зацикливания кода.
Заметное различие, которое я увидел между ответами здесь и поведением ASM, заключается в том, что он считывает команды перехода "цикла" для простого файла как коды операций, отличные от "goto" - это могут быть просто изменения в компиляции Java за время, прошедшее с момента запроса., но, похоже, стоит отметить.
Базовый пример кода для ASM - это (вводится через checkForLoops метод):
import org.objectweb.asm.ClassReader;
import org.objectweb.asm.ClassVisitor;
import org.objectweb.asm.Label;
import org.objectweb.asm.MethodVisitor;
import org.objectweb.asm.Opcodes;
public void checkForLoops(Path classFile) {
LoopClassVisitor classVisitor = new LoopClassVisitor();
try (InputStream inputStream = Files.newInputStream(classFile)) {
ClassReader cr = new ClassReader(inputStream);
cr.accept(classVisitor, 0);
} catch (IOException e) {
throw new RuntimeException(e);
}
}
public class LoopClassVisitor extends ClassVisitor {
public LoopClassVisitor() {
super(Opcodes.ASM7);
}
@Override
public MethodVisitor visitMethod(int access, String name, String descriptor, String signature,
String[] exceptions) {
return new LoopMethodVisitor();
}
}
public class LoopMethodVisitor extends MethodVisitor {
private List<Label> visitedLabels;
public LoopMethodVisitor() {
super(Opcodes.ASM7);
visitedLabels = new ArrayList<>();
}
@Override
public void visitLineNumber(final int line, final Label start) {
System.out.println("lnLabel: " + start.toString());
visitedLabels.add(start);
}
@Override
public void visitLabel(final Label label) {
System.out.println("vLabel: " + label.toString());
visitedLabels.add(label);
}
@Override
public void visitJumpInsn(final int opcode, final Label label) {
System.out.println("Label: " + label.toString());
if (visitedLabels.contains(label)) {
System.out.println("Op: " + opcode + ", GOTO to previous command - possible looped execution");
}
}
}
Вы можете дополнительно прикрепить к меткам информацию о номере строки, если она доступна, и отслеживать ее в посетителе метода, чтобы вывести, где начинаются и заканчиваются циклы обнаружения в источнике.