en el control global toda la información del estado excepto la signatura del método y el contador de programa. Esta estrategia de control garantiza trivialmente las condiciones (I) y (II), pues asegura que cada instrucción bytecode se decompila de forma independiente. Sin embargo, tiende a ser demasiado conservadora, y, en particular, no satisface la condición (III), pues tan pronto como se encuentre con un bloque que tenga más de una instrucción bytecode (lo que ocurre casi siempre), el programa especializado generará una regla para cada instrucción bytecode del bloque. Como resul- tado, el programa residual obtenido es de alto nivel en el sentido de que está escrito en Prolog. No obstante, su estrategia de control está altamente influenciada por el hecho de que estamos decompilando desde un programa bytecode (y no por ejemplo desde un programa fuente Java), y el programa obtenido no se parece para nada al programa Prolog que un programador Prolog podŕıa escribir para realizar la misma tarea. Pues uno de los ob- jetivos importantes de la decompilación es facilitar su comprensión y su análisis, en esta tesis sostenemos que los programas que cumplen el criterio de la bloque-optimalidad, y en particular aquellos que cumplen la condición (III), como los que se generan usando nuestro esquema de decompilación óptima, son más fáciles de tratar. Otra observación importante es que los costosos mecanismos utilizados para controlar la EP, usados anteriormente para obtener los resultados de las Secciones 2.3.3 y 2.4, en particular el TbHEm y el control avanzado de polivarianza del Art́ıculo 2, ya no son necesarios al utilizarse el esquema de decompilación óptima. Se pueden ahora usar los siguiente operadores triviales de control: unfold despliega todas las llamadas excepto aquellas que se correspondan con una anotación, y abstract añade al conjunto Si+1 todas las llamadas en Lpe que no sean una instancia de ninguna llamada en Si (ver el algoritmo genérico de la Sección 2.1). Se puede demostrar fácilmente que la terminación está garantizada, tanto a nivel local como global gracias a las anotaciones y al conjunto inicial de átomos proporcionados en la EP. 2.6. Implementación y Resultados Experi- mentales El Art́ıculo 6 discute varios detalles de implementación y realiza una evaluación experimental exhaustiva de los diferentes esquemas de decom- pilación propuestos. Hemos llevado a cabo dos implementaciones distintas de un decompilador de Java Bytecode (secuencial) a Prolog. En la primera, hemos extendido un evaluador parcial online existente, aquel integrado en el sistema CiaoPP. Éste es un evaluador parcial muy potente y implemen- ta reglas de desplegado y operadores de abstracción. Esto nos ha permi- tido comparar los diferentes esquemas de decompilación, y en particular 65 CAPÍTULO 2. DECOMPILACIÓN INTERPRETATIVA DE BYTECODE A LP comparar respecto a los esquemas no óptimos. Sin embargo, la sobrecar- ga introducida al utilizar una herramienta tan potente y genérica no nos permite competir, respecto a eficiencia, con decompiladores dedicados. Por ello, hemos llevado a cabo una segunda implementación para la cual hemos escrito un evaluador parcial autocontenido que sólo contiene las estrategias de control necesarias para el esquema óptimo. Éste evaluador parcial ha sido integrado en una herramienta de decompilación, llamada jbc2prolog, la cual incluye también un intérprete de Java Bytecode. Esto ha hecho posible obtener decompilaciones óptimas y al mismo tiempo competir en términos de eficiencia respecto a decompiladores dedicados. El Art́ıculo 6 realiza una comparación exhaustiva frente al decompilador del sistema COSTA [5] y al decompilador de Java JDec [14]. Ambas implementaciones consideran el lenguaje Java Bytecode (secuen- cial) al completo. Las extensiones necesarias para poder tratar los aspectos del lenguaje no tratadas en esta introducción se discuten en el Art́ıculo 6. Éstas incluyen a las excepciones, operaciones del heap, invocaciones virtua- les, decompilación al nivel de clases, etc. Todas ellas han sido fácilmente integradas en nuestro esquema de decompilación, en la mayoŕıa de los ca- sos, simplemente las funcionalidades correspondientes en el intérprete de bytecode. Para la evaluación experimental del Art́ıculo 6, hemos utilizado el con- junto estándar de “benchmarks” JOlden [55]. En particular, nos hemos in- teresado en: a) demostrar emṕıricamente la escalabilidad del enfoque, y b) comprobar la eficiencia de la herramienta implementada respecto a otros decompiladores. Concluimos lo siguiente: Escalabilidad: Mientras que en la decompilación no-óptima los tiem- pos de decompilación y los tamaños de los programas decompilados crecen de forma muy significativa con el tamaño de los “benchmarks”, esto no ocurre en el esquema óptimo. Con la decompilación óptima, estos valores se mantienen totalmente estables. Mostramos que tan- to los tiempos de decompilación como los tamaños de los programas decompilados crecen de forma lineal con respecto al tamaño de los programas bytecode de entrada, demostrando aśı la escalabilidad de la decompilación óptima. Eficiencia: Para demostrar la eficiencia de nuestro esquema, hemos 66 2.7. TRABAJO RELACIONADO comparado los tiempos de decompilación obtenidos usando nuestra herramienta jbc2prolog frente a aquellos obtenidos usando el decom- pilador del sistema COSTA, y , a aquellos obtenidos con el decompi- lador JDec [14]. Podemos concluir que los resultados son competitivos respecto a aquellos obtenidos con decompiladores dedicados. En par- ticular, observamos que son bastante similares a los obtenidos con COSTA. Mas aún, en la mayoŕıa de ejemplos, podemos observar que jbc2prolog es cerca de diez veces más rápido que JDec. Nuestra conclusión en este sentido es que es muy dif́ıcil comparar decompila- dores escritos en diferentes lenguajes de programación y más aún que decompilan a diferentes lenguajes. 2.7. Trabajo Relacionado Los trabajos previos sobre decompilación interpretativa se han centrado básicamente en demostrar que el enfoque es viable para pequeños y media- nos intérpretes y lenguajes. Principalmente han tratado de demostrar su efectividad, es decir, que la llamada capa de interpretación se puede elimi- nar de los programas compilados. Para ello se han usado técnicas de EP offline [63], online [48, 77] y h́ıbridas [64]. Esta tesis se ha centrado en, pri- meramente, demostrar la viabilidad del enfoque para un lenguaje bytecode con orientación a objetos, para después estudiar cuestiones más avanzadas como su escalabilidad y la calidad de las decompilaciones, las cuales no se hab́ıan estudiado hasta ahora. Los trabajos sobre decompilación interpre- tativa ya se han ido comparando en las diferentes secciones del caṕıtulo y en la introducción. Revisamos a continuación el trabajo relacionado en el campo de la decompilación. Se puede realizar decompilación a diferentes niveles, con sus correspon- dientes grados de precisión y éxito. El caso más complicado es sin duda la decompilación de ejecutables binarios. Hay una serie de complicaciones como por ejemplo la dificultad a la hora de recuperar el flujo de control. Un problema intŕınseco es la imposibilidad de distinguir entre el código de los datos de forma estática. Ver por ejemplo [26, 81] y sus referencias donde se discuten los problemas y las técnicas que se aplican en la decompilación de ejecutables binarios. El siguiente nivel es la decompilación de código ensamblador [27]. En este contexto, muchas de las complicaciones de la pecialmente aquellos generados por compiladores de Java, por ejemplo javac. No obstante, las cosas se pueden complicar bastante cuando el java Bytecode se ha generado con un obfus- cador, y especialmente cuando se ha utilizado un compilador optimizante o un compilador de un lenguaje distinto de Java como Haskell, ML, Ada, etc. Ver por ejemplo [72] y sus referencias para una discusión más detallada sobre decompiladores de Java Bytecode y las dificultades a las que éstos se enfrentan. Como hemos mencionado anteriormente, existen varios analizadores de Java Bytecode que transforman el bytecode en algún tipo de representación intermedia de