Identificar bucles en el código de byte java
loops bytecode (3)
Estoy tratando de instrumentar el código de bytes de Java.
Quiero reconocer la entrada y salida de un bucle de Java , pero he encontrado que la identificación de los bucles es bastante difícil. He pasado unas cuantas horas mirando ASM y los de-compiladores de código abierto (a quienes creía que debían resolver este problema todo el tiempo), sin embargo, me quedé corto.
La herramienta que estoy aumentando / extendiendo está utilizando ASM, por lo que idealmente me gustaría saber cómo instrumentar la entrada y salida de las diferentes construcciones de bucle en java a través de ASM . Sin embargo, también agradecería una recomendación para un buen compilador de código abierto, ya que claramente habrían resuelto el mismo problema.
¿Realmente estás construyendo tu clase byte por byte? Eso es bastante salvaje! La página de inicio de ASM enlaza con el complemento de Bytecode Outline para Eclipse, que supongo que está utilizando. Si hace clic en la primera imagen allí, notará que el código tiene un bucle while, y puede ver al menos parte del código de byte usado para implementar ese bucle. Para referencia aquí es que captura de pantalla:
Parece que los bucles se implementan simplemente como GOTO con una verificación de límites. Estoy hablando de esta línea:
L2 (173)
GOTO L3
Estoy seguro de que el marcador L3 tiene un código para verificar el límite del índice y se decidió si JMP. Creo que esto va a ser bastante difícil para usted si desea instrumentar bucles de un código de byte a la vez. ASM tiene la opción de usar una clase de plantilla como base para su instrumentación, ¿ha intentado usarla?
La única forma de saltar hacia atrás en el código es a través de un bucle. Así que está buscando un goto, if_icmplt, etc. que va a una instrucción de código de byte anterior. Una vez que haya encontrado el final del bucle y donde salta es el comienzo del bucle.
Aquí hay un ejemplo complejo, del documento que Bruno sugirió.
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;
}
El código de bytes para esto aparece en javap -c como
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
Puede ver que hay un bucle interno entre 0 y 12, un bloque try / catch entre 0 y 15 y un bucle externo entre 0 y 22.
EDITAR 4 : Un poco de fondo / preámbulo.
" La única forma de saltar hacia atrás en el código es a través de un bucle " . En la respuesta de Peter no es estrictamente cierto. Podrías saltar de un lado a otro sin que eso signifique que es un bucle. Un caso simplificado sería algo como esto:
0: goto 2 1: goto 3 2: goto 1Por supuesto, este ejemplo en particular es muy artificial y un poco tonto. Sin embargo, hacer suposiciones sobre cómo se va a comportar el compilador de código fuente a bytecode podría llevar a sorpresas. Como Peter y yo hemos demostrado en nuestras respuestas respectivas, dos compiladores populares pueden producir una salida bastante diferente (incluso sin ofuscación). Rara vez importa, porque todo esto tiende a ser optimizado bastante bien por el compilador JIT cuando ejecuta el código. Dicho esto, en la gran mayoría de los casos, saltar hacia atrás será una indicación razonable de dónde comienza un bucle. Comparado con el resto, descubrir el punto de entrada de un bucle es la parte "fácil".
Antes de considerar cualquier instrumentación de inicio / salida de bucle, debe buscar en las definiciones de qué entrada, salida y sucesores son. Aunque un bucle solo tendrá un punto de entrada, puede tener múltiples puntos de salida y / o múltiples sucesores, generalmente causados por declaraciones de
break(a veces con etiquetas), declaraciones dereturny / o excepciones (capturadas explícitamente o no). Si bien no ha dado detalles sobre el tipo de instrumentación que está investigando, ciertamente vale la pena considerar dónde desea insertar el código (si eso es lo que quiere hacer). Por lo general, es necesario que se realice alguna instrumentación antes de cada declaración de salida o en lugar de cada declaración sucesora (en cuyo caso tendrá que mover la declaración original).
Soot es un buen marco para hacer esto. Tiene una serie de representaciones intermedias que hacen que el análisis de códigos de bytes sea más conveniente (por ejemplo, Jimple).
Puede crear un BlockGraph basado en el cuerpo de su método, por ejemplo, un ExceptionalBlockGraph . Una vez que haya descompuesto el gráfico de flujo de control en un gráfico de bloques de este tipo, desde los nodos, debería poder identificar a los dominadores (es decir, los bloques que tienen una flecha que regresa a ellos). Esto te dará el inicio del bucle.
Puede encontrar algo similar en las secciones 4.3 a 4.7 de esta disertación .
EDITAR:
Siguiendo la discusión con @Peter en comentarios a su respuesta. Hablando el mismo ejemplo:
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;
}
Esta vez, compilado con el compilador Eclipse (sin opción específica: simplemente autocompilación desde el IDE). Este código no ha sido confuso (aparte de ser un código incorrecto, pero eso es un asunto diferente). Aquí está el resultado (de 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
Hay un bucle entre 3 y 12 (saltó en el inicio de un 10) y otro bucle, debido a la excepción que se produce desde la división por cero entre 8 y 22. A diferencia del resultado del compilador javac , donde se podría hacer una conjetura de que había un Bucle externo entre 0 y 22 y un bucle interno entre 0 y 12, el anidado es menos obvio aquí.
EDIT 2:
Para ilustrar el tipo de problemas que puede obtener con un ejemplo menos incómodo. Aquí hay un bucle relativamente simple:
public void foo2() {
for (int i = 0; i < 5; i++) {
System.out.println(i);
}
}
Después de la compilación (normal) dentro de Eclipse, javap -c da esto:
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
Antes de hacer algo dentro del bucle, salta directamente del 2 al 15. El bloque 15 al 17 es el encabezado del bucle (el "punto de entrada"). A veces, el bloque de encabezado podría contener muchas más instrucciones, especialmente si la condición de salida implica más evaluación, o si es un bucle do {} while() . El concepto de "entrada" y "salida" de un bucle no siempre refleja lo que escribiría sensiblemente como código fuente de Java (incluido el hecho de que puede reescribir for bucles como bucles, por ejemplo). El uso de break también puede llevar a múltiples puntos de salida.
Por cierto, por "bloque", me refiero a una secuencia de bytecode en la que no puedes saltar y fuera de la cual no puedes saltar en el medio: solo se ingresan desde la primera línea (no necesariamente desde la anterior). línea, posiblemente de un salto desde otro lugar) y salido de la última (no necesariamente a la siguiente línea, también puede saltar a otro lugar).
EDITAR 3:
Parece que se han agregado nuevas clases / métodos para analizar bucles desde la última vez que vi Soot, lo que lo hace un poco más conveniente.
Aquí hay un ejemplo completo.
La clase / método a analizar ( 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);
}
}
}
}
Cuando es compilado por el compilador Eclipse, esto produce este bytecode ( 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
Aquí hay un programa que carga la clase (asumiendo que está en la ruta de clases aquí) utilizando Soot y muestra sus bloques y bucles:
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());
}
}
}
Consulte la documentación de Soot para obtener más detalles sobre cómo cargar clases. El Body es un modelo para el cuerpo del bucle, es decir, todas las declaraciones hechas a partir del código de bytes. Esto utiliza la representación intermedia de Jimple, que es equivalente al código de bytes, pero más fácil de analizar y procesar.
Aquí está la salida de este programa:
Cuerpo:
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;
}
Bloques
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;
Bucles
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 usa LoopFinder , que usa un ExceptionalBlockGraph para construir la lista de bloques. La clase Loop le dará la instrucción de entrada y las instrucciones de salida. Entonces deberías poder agregar declaraciones adicionales si lo deseas. Jimple es muy conveniente para esto (está lo suficientemente cerca del código de byte, pero tiene un nivel ligeramente más alto para no tratar todo manualmente). A continuación, puede generar su archivo .class modificado si es necesario. (Consulte la documentación de Soot para esto).