Universidad de Buenos Aires

Facultad de Ciencias Exactas y Naturales

Departamento de Computacion

Mejorando la usabilidad de herramientas de

verificacion

Tesis presentada para optar al tıtulo de Licenciado de la Universidad de Buenos Airesen el area de Ciencias de la Computacion

Marcos Jose Chicote

Directores de Tesis: Dr. Juan Pablo Galeotti, Dr. Diego Garbervetsky

Buenos Aires, abril de 2012

Mejorando la usabilidad de herramientas de verificacion

Resumen

TACO es una herramienta de codigo abierto que permite el analisis de programas Javarealizando una verificacion estatica del codigo fuente contra una especificacion en JML (JavaModeling Language) o JFSL (Java Forge Specification Language). TACO utiliza la tecnica deverificacion acotada en la que todas las ejecuciones de un procedimiento son examinadas hastaun lımite provisto por el usuario que acota el espacio de analisis. TACO traduce codigo Javaa JDynAlloy (un lenguaje de representacion intermedia) que luego es traducido a DynAlloypara su verificacion.

En el presente trabajo se presentan diversas mejoras de usabilidad sobre la herramientaTACO que permiten un mayor y mejor analisis del contraejemplo detectado luego de unaverificacion. Asimismo se presenta el diseno y desarrollo de un plugin para Eclipse, llamadoTacoPlug, que utiliza y expande TACO para proveer una mejor experiencia de usuario y unamayor posibilidad de debugging. Si TACO detecta una violacion a la especificacion, TacoPlugla presenta en terminos de codigo fuente anotado y brinda al usuario la posibilidad de localizarla falla mediante diversas vistas similares a las de cualquier software de debugging.

Finalmente, se demuestra la usabilidad de la herramienta por medio de un ejemplo moti-vacional tomado de una porcion de software industrial.

i

Improving usability of verification tools

Abstract

TACO is an open source verification tool that statically checks the compliance of a Javaprogram against a specification written in JML (Java Modeling Language) or JFSL (JavaForge Specification Language). TACO uses a bounded verification technique, in which allexecutions of a procedure are examined up to a user-provided bound that narrows the analy-sis world. TACO translates Java annotated code to JDynAlloy (an intermediate languagerepresentation) which is then translated to DynAlloy for verification.

In this work different improvements over usability issues on TACO are presented thatenable a bigger and better analysis of a counterexample found in a verification. Furthermore,this thesis presents the design and implementation of an Eclipse’s plugin, called TacoPlug,that uses and expands TACO to provide a more user friendly experience and a profunderdebugging capability. If TACO finds a specification violation, TacoPlug presents it in terms ofthe annotated source code and enables the user the posibility of localizing the defect throughdifferent views resembling any software debugger.

Finally, the tool’s usability is shown by means of a motivational example taken from anindustrial portion of software.

ii

Agradecimientos

A la UBA, a la FCEN y al DC: por recibirme como alumno, formarme y permitir que medesempene como docente.

Al jurado, Flavia y Vıctor, por tomarse el tiempo de leer la tesis y senalarme las cosas que sepodıan mejorar.

A mis directores, Juan Pablo y Diego, por darme la oportunidad de hacer la tesis en este temay guiarme durante el proceso.

A mis amigos de la facu: Jota, Luigi, Eze, Sabi, Fede, PabloB, PabloR, el Lata, la Topadora,Droopy, Amity, Juanity, PabloH, Pıter, Mati, Droopy y Roman. No me imagino haber hecho lacarrera sin ellos y seguramente seguirıa en Algo1 sin su constante apoyo y acompanamiento.

A todos los que compartieron anos de Confirmacion conmigo.Al Clus: Salvi, Jorge, Angie, Luchi, Vicky, Dany, Dani y Sofi.A mis amigos y amigas: Piter, Gabi, Santi, Javi, Oti, Juan, Tomy, la Pola, Gon, Cape, Juani,

Chule, Fede, Faca, Ale, Clari, Fla, Domi, Agus, Luli, Guada.

A mis primos, tıos y abuelos. A Manu, Cande e Ine.

Muy especialmente a mis viejos, por darme vida y acompanarme en todo momento y en todoaspecto que pudieran y tuvieran permiso. Gracias por ocuparse de mi educacion formal y humana.Les debo mas que estas lıneas. Gracias Ma. Gracias Pa.

iii

Indice

1. Introduccion 11.1. Motivacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2. Trabajos Relacionados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.3. Estructura del informe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2. TACO 82.1. Definiciones previas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.2. Introduccion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.3. Arquitectura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.4. Uso y resultado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3. TacoPlug 143.1. Introduccion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.2. Contribuciones a TACO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3.2.1. Trazabilidad Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.2.2. Evaluacion de expresiones JML y JFSL . . . . . . . . . . . . . . . . . . . . 153.2.3. Validacion de predicados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.2.4. Visualizacion global de la memoria . . . . . . . . . . . . . . . . . . . . . . . 15

3.3. Caracterısticas de TacoPlug . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.3.1. Configurando TACO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.3.2. Ejecutando un analisis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.3.3. TACO Perspective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173.3.4. JML/JFSL Annotation Explorer . . . . . . . . . . . . . . . . . . . . . . . . 183.3.5. Java Error Trace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183.3.6. JML/JFSL Evaluator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.3.7. Java Memory Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203.3.8. TACO Editor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

4. Caso de estudio: BinomialHeap 244.1. Analizando con TACO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264.2. Analizando con TacoPlug . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

5. TacoPlug: Diseno y Arquitectura 325.1. Diseno y Arquitectura de contribuciones a TACO . . . . . . . . . . . . . . . . . . . 32

5.1.1. Trazabilidad Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345.1.2. Evaluacion de expresiones JML/JFSL . . . . . . . . . . . . . . . . . . . . . 355.1.3. Validacion de predicados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375.1.4. Visualizacion global de la memoria . . . . . . . . . . . . . . . . . . . . . . . 38

5.2. Diseno y Arquitectura de TacoPlug . . . . . . . . . . . . . . . . . . . . . . . . . . . 385.2.1. TACO Preferences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395.2.2. TACO Launcher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395.2.3. JML/JFSL Annotation Explorer . . . . . . . . . . . . . . . . . . . . . . . . 405.2.4. Java Error Trace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415.2.5. JML/JFSL Evaluator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415.2.6. Java Memory Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415.2.7. TACO Editor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425.2.8. TACO Perspective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

5.3. Integracion TacoPlug-TACO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

6. Conclusiones 45

7. Trabajo futuro 46

iv

A. Codigo fuente BinomialHeap 48

v

Indice de figuras

1. Clase AssertExample . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22. Salida para el metodo assertion method de la clase AssertExample . . . . . . . 33. XML con la informacion de diferentes modulos existentes en el contrajemplo . . . . 44. XML con la informacion de diferentes atomos instanciados en el contrajemplo . . . 55. Etapas de transformacion del codigo JML hasta codigo Alloy . . . . . . . . . . . . 96. Ejemplo de assertCorrectness para el programa A::f . . . . . . . . . . . . . . . 127. Pantalla de configuracion de TACO . . . . . . . . . . . . . . . . . . . . . . . . . . . 168. Pantalla de ejecucion de analisis TACO . . . . . . . . . . . . . . . . . . . . . . . . 179. TACO Perspective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1810. JML/JFSL Annotation Explorer . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1811. Componente de visualizacion de la traza Java . . . . . . . . . . . . . . . . . . . . . 1912. Ejemplo de combinacion de llamados a metodos en Java . . . . . . . . . . . . . . . 1913. JML/JFSL Evaluator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2014. Java Memory Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2015. TACO Editor visualizando codigo Java . . . . . . . . . . . . . . . . . . . . . . . . . 2116. TACO Editor visualizando la version JML Simplificado . . . . . . . . . . . . . . . 2217. TACO Editor visualizando la version JDynAlloy . . . . . . . . . . . . . . . . . . . 2218. TACO Editor visualizando la version DynAlloy . . . . . . . . . . . . . . . . . . . . 2319. Extracto de la clase BinomialHeap . . . . . . . . . . . . . . . . . . . . . . . . . . . 2420. Invariante de clase de BinomialHeap . . . . . . . . . . . . . . . . . . . . . . . . . . 2521. Especificacion para el metodo extractMin escrita en JFSL . . . . . . . . . . . . . 2522. Output de TACO para extractMin . . . . . . . . . . . . . . . . . . . . . . . . . . . 2623. JML/JFSL Annotation Explorer luego del analisis de extractMin. . . . . . . . . . 2724. Java Memory Graph inicial para extractMin . . . . . . . . . . . . . . . . . . . . . 2825. Java Memory Graph final para extractMin . . . . . . . . . . . . . . . . . . . . . . 2826. Estado del heap previo a la invocacion a unionNodes . . . . . . . . . . . . . . . . . 2927. Estado del heap previo a la invocacion a merge . . . . . . . . . . . . . . . . . . . . 2928. Algoritmo de merge de dos BinomialHeap . . . . . . . . . . . . . . . . . . . . . . . 3029. Punto del algoritmo de merge previo a la falla . . . . . . . . . . . . . . . . . . . . . 3130. Nodos perdidos durante el algoritmo de merge . . . . . . . . . . . . . . . . . . . . 3131. Diagrama de la nueva arquitectura de TACO . . . . . . . . . . . . . . . . . . . . . 3232. Jerarquıa de clases para TranslationContext . . . . . . . . . . . . . . . . . . . . . 3333. Diagrama de clases para JavaCounterExample . . . . . . . . . . . . . . . . . . . . 3434. Esquema instanciacion resultados Alloy . . . . . . . . . . . . . . . . . . . . . . . . 3735. PDE Incubator Spy para la vista de problemas de compilacion de Eclipse . . . . . 3936. Diagrama de interaccion entre TacoPlug y TACO . . . . . . . . . . . . . . . . . . . 4337. Diagrama de interaccion para la evaluacion de una expresion . . . . . . . . . . . . 4438. Diagrama de interaccion para la construccion del grafo con el estado de la memoria 44

vi

1. Introduccion

La importancia del software tanto en sistemas crıticos como en elementos de la vida cotidiana hacrecido en los ultimos anos a un ritmo acelerado y se prevee que lo siga haciendo. Este crecimientoimplica un incremento en la complejidad y el tamano del software desarrollado. Actualmente losdesarrolladores no lidian con algunos cientos de lıneas de codigo, sino que tratan con programas demillones de lıneas. Paralelamente, y aunque se trate de una consecuencia indeseable, la cantidadde fallas en los programas aumenta. Las fallas en los elementos de software varian entre aquellasque pueden ser consideradas molestas y aquellas que traen tragicas consecuencias.

Las condiciones aquı planteadas demandan una mayor robustez en las tecnicas utilizadas enla construccion de software en conjunto con herramientas mas avanzadas que permitan a losprogramadores obtener mayores estandares de calidad en los elementos que producen.

Con el objetivo de reducir la cantidad de errores presentes en un software se han desarrolladodiversas tecnicas y mecanismos durante los ultimos anos que pueden dividirse en dos grandes areas:analisis dinamico y analisis estatico.

Dentro de las tecnicas de analisis dinamico se incluyen todas aquellas que impliquen la ejecuciondel software que se desea analizar, siendo la mas conocida la generacion de casos de test y suejecucion ya sea automatica o asistida. Para que el analisis dinamico sea efectivo, el software bajoanalisis debe ser ejecutado con suficientes datos de entrada como para producir un comportamientointeresante. Tecnicas como cobertura de codigo permiten asegurar que una porcion adecuada delcomporamiento del software ha sido probada. Algunos ejemplos de herramientas que implementano facilitan tecnicas de analisis estatico son: Daikon [1] y Valgrind [2].

Por otro lado, existen metodologıas muy utilizadas actualmente que basan su funcionamientoen tecnicas de analisis dinamico. El mayor ejemplo de esta practica actualmente es Test DrivenDevelopment (TDD) que incluye el diseno de tests de unidad previo al desarrollo de un componentey su posterior ejecucion a fin de corroborar que el software se comporte de la manera esperada.

Asimismo, dentro de las tecnicas asociadas al analisis estatico se incluye todo mecanismo quetenga potencial para reducir la cantidad de errores en el software pero que no incluya la ejecuciondel mismo. Por ejemplo, los compiladores actuales se benefician de diversas tecnicas de analisis deprogramas como ser chequeo de tipos o analisis data-flow para prevenir posibles errores y notificara los programadores. Estas tecnicas se encuentran bastante desarrolladas y no solo su grado deautomatizacion es alto sino que las IDEs permiten a los programadores entender facilmente lafalla.

El analisis estatico tambien es utilizado para la verificacion de programas. Dentro de la tecnicasmas conocidas se incluyen las deductivas basadas en el uso de demostradores automaticos. Estoincluye los verificadores de contratos y los chequeadores de tipos. Por otro lado, las tecnicas demodel checking [3] analizan exhaustivamente todo el espacio de estados del programa. En general,los espacios de estados asociados a un programa suelen ser muy grandes o infinitos transformandoesta tarea en muy compleja o imposible. Por este motivo surgen alternativas para reducir el espaciode busqueda: la abstraccion [4], si el espacio de estados es infinito, que puede dar falsos positivos; yla verificacion acotada que transforma el problema en decidible pero que puede dar falsos negativos.

Actualmente, tecnicas de verificacion formal son utilizadas por la mayorıa o todos los fabri-cantes de hardware lıderes [5]. Esto puede ser atribuido a la importante necesidad de disminuir lacantidad de fallas que pueden tener graves consecuencias comerciales.

Sin embargo, herramientas de model checking o verificacion acotada de no han alcanzado unuso masivo en otros ambientes productivos industriales. Los motivos de la falta de masificacionson diversos. Excluyendo cuestiones presupuestarias puede enumerarse los siguientes problemas:

Reporte de falsos positivos o inconclusividad de los analisis.

Falta de comodidad en la ejecucion.

Baja facilidad de analisis e interpretacion de las fallas encontradas y los resultados reporta-dos.

1

Para el desarrollo del presente trabajo asumimos que para que la tecnica de verficacion formalde programas pueda alcanzar un numero significativo de usuarios y un uso corriente, interfacesde usuario apropiadas deben ser provistas, por lo que pondremos foco en la segunda causa por lacual este tipo de herramientas permanecen en ambientes academicos o especializados.

El proposito de este trabajo consiste en disenar e implementar distintas tecnicas y mecanismosque aumenten la usabilidad de herramientas de verifacion formal y analizar su impacto en eldebugging y localizacion de una falla. Para esto se pondra el foco sobre herramientas que utilicenla tecnica de verificacion acotada utilizando la herramienta TACO presentada en [6, 7] comoejemplo de este paradigma y se desarrollara un plugin que permita el uso de esta herramientadesde Eclipse como prueba de concepto.

1.1. Motivacion

A continuacion se muestra un ejemplo de uso de TACO y su salida. Aunque en el capıtulo 2se presentara esta herramienta con mas detalle, de momento alcanza con saber que TACO es unaherramienta de verificacion formal de programas. No se presenta aquı mayor informacion sobreTACO con el fin de simular el uso de la herramienta por un usuario inexperto al cual deberıaalcanzarle con saber que se verificara su programa contra la especificacion brindada. Con solamenteesta informacion alcanzara para demostrar que la usabilidad de TACO y su flexibilidad paraanalizar el resultado encontrado es reducida. Conociendo algunas de las caracterısticas planteadasen el capıtulo 2, esto resultara todavıa mas evidente.

Considerese la clase AssertExample con un metodo llamado assertion method incluida en lafigura 1. Este metodo esta anotado, utilizando el lenguaje JML que se vera mas adelante, por unaprecondicion que establece que durante la ejecucion del metodo no se arrojaran excepciones y unaposcondicion que declara que el resultado del metodo es true. Adicionalmente se establece que elunico parametro del metodo puede ser nulo.

1 p u b l i c c l a s s Asse r tExample {2

3 //@ s i g n a l s ( Excep t i on ex ) f a l s e ;4 //@ en s u r e s \ r e s u l t == t r u e ;5 p u b l i c boo l ean a s s e r t i o n me t hod ( /∗@ n u l l a b l e @∗/ Object o ) {6 Object f = o ;7 //@ a s s e r t f != n u l l ;8

9 r e t u r n t r u e ;10 }11

12 }

Figura 1: Clase AssertExample

El codigo de esta clase es bastante simple. Tras un rapido analisis mental del metodo contenidoes evidente la falla contenida en el mismo: la instruccion assert en la lınea 7 falla al no poderasegurar que la variable f sea no nula (recuerdese que la anotacion en el parametro del metodoestablece que la variable o, que es luego asignada a f, puede ser nula).

Esta misma falla es detectada mediante un analisis de TACO. En la figura 2 se puede apreciarla salida de la herramienta cuando se la ejecuta mediante la lınea de comando. Se omite en estasalida logueo propio de la herramienta que detalla etapas de procesamiento internas y que nomodifican el resultado final o el analisis que puede hacerse del mismo. En la lınea 23 puede verseque el Outcome es SAT lo que establece que se encontro un contrajemplo para la verificacionrealizada.

2

1 ∗∗∗∗∗∗ Stage D e s c r i p t i o n : Execu t i on o f a n a l y s i s . ∗∗∗∗∗∗2

3 00000000 S t a r t i n g A l l o y Ana l y z e r v i a command l i n e i n t e r f a c e4 ∗ I npu t spec f i l e : output / output . a l s5

6 00000001 Pa r s i ng and t yp e ch e ck i n g7 ∗ Command type : check8 ∗ Command l a b e l : a r e d u t a c o A s s e r t E x amp l e a s s e r t i o n me t h od 09

10 00000568 T r a n s l a t i n g A l l o y to Kodkod11 ∗ So l v e r : m i n i s a t ( j n i )12 ∗ Bi t width : 413 ∗ Max sequence : 714 ∗ Skolem depth : 015 ∗ Symmbreaking : 2016

17 00000947 T r a n s l a t i n g Kodkod to CNF18 ∗ Pr imary v a r s : 3619 ∗ Tota l v a r s : 22820 ∗ C l au s e s : 34121

22 00001344 So l v i n g23 ∗ Outcome : SAT24 ∗ So l v i n g t ime : 41925

26 00001366 An a l y s i s f i n i s h e d27

28 ∗∗∗∗∗∗ END: A l l o y Stage ∗∗∗∗∗∗

Figura 2: Salida para el metodo assertion method de la clase AssertExample

Como se puede observar, la unica informacion significativa que brinda la salida de TACO es sise encontro un error o no (en cuyo caso dira UNSAT). El resto de la informacion aquı mostradason caracterısticas del analisis realizado. De esta forma, en caso de encontrar un error, como sereste el caso, no se brinda mayor informacion sobre cual es el error, de donde proviene, en que lınease encuentra, etc.. Es decir, no se brinda informacion util para comprender el origen de la falla.

Por otro lado, TACO brinda la posibilidad de imprimir el contraejemplo encontrado en formatoXML. En las figuras 3 y 4 se muestra dicho XML para la verificacion aquı considerada separadoen los modulos existentes y en los atomos instanciados, respectivamente. Estos XML incluyeninformacion que representa las variables instanciadas durante la ejecucion simbolica del metodoanalizado: this, parametros y variables locales.

3

1 <s i g l a b e l=” seq / I n t ” ID=”0” pa ren t ID=”1” b u i l t i n=” yes ”/>2

3 <s i g l a b e l=” I n t ” ID=”1” pa ren t ID=”2” b u i l t i n=” yes ”/>4

5 <s i g l a b e l=” S t r i n g ” ID=”3” paren t ID=”2” b u i l t i n=” yes ”/>6

7 <s i g l a b e l=” t h i s / n u l l ” ID=”4” pa ren t ID=”2” one=” yes ”>8 <atom l a b e l=” n u l l $0”/>9 </ s i g>

10

11 <s i g l a b e l=” t h i s / t r u e ” ID=”5” pa ren t ID=”6” one=” yes ”>12 <atom l a b e l=” t r u e $0”/>13 </ s i g>14

15 <s i g l a b e l=” t h i s / f a l s e ” ID=”7” pa ren t ID=”6” one=” yes ”>16 <atom l a b e l=” f a l s e $0”/>17 </ s i g>18

19 <s i g l a b e l=” t h i s / boo l ean ” ID=”6” pa ren t ID=”2” a b s t r a c t=” yes ”/>20

21 <s i g l a b e l=” t h i s / cha r ” ID=”8” pa ren t ID=”2” a b s t r a c t=” yes ”/>22

23 <s i g l a b e l=” t h i s / A s s e r t i o n F a i l u r e L i t ” ID=”9” pa ren t ID=”10” one=” yes ”>24 <atom l a b e l=” A s s e r t i o n F a i l u r e L i t $0”/>25 </ s i g>26

27 <s i g l a b e l=” t h i s / j a v a l a n g E x c e p t i o n ” ID=”11” paren t ID=”10” a b s t r a c t=” yes ”/>28

29 <s i g l a b e l=” t h i s / j a v a l a ng Th r owab l e ” ID=”10” pa ren t ID=”2” a b s t r a c t=” yes ”/>30

31 <s i g l a b e l=” t h i s / a r e du t a c o As s e r tE xamp l e ” ID=”12” pa ren t ID=”13”>32 <atom l a b e l=” a r e du t a c o As s e r tE xamp l e $0”/>33 </ s i g>34

35 <s i g l a b e l=” t h i s / j a v a l a n g Ob j e c t ” ID=”13” pa ren t ID=”2” a b s t r a c t=” yes ”/>36

37 <s i g l a b e l=” un i v ” ID=”2” b u i l t i n=” yes ”/>

Figura 3: XML con la informacion de diferentes modulos existentes en el contrajemplo

Como puede verse en estas figuras, el contrajemplo no resulta intuitivo ni facil de entenderpara un usuario no experto. Inclusive, si es analizado por un usuario avanzado de TACO o Alloy,puede requerir un tiempo prolongado antes de lograr comprender la falla detectada y descripta.Esta tarea permitirıa reconstruir las variables involucradas pero no alcanzarıa para detectar la fallapuesto que faltarıa hacer una ejecucion, simbolica o no, del metodo analizado con la informacionrecuperada para visualizar cual fue el camino de ejecucion tomado. Esto resulta en un procesomuy fragil al error humano y requerirıa nuevamente una inversion considerable de tiempo.

4

1 <sko lem l a b e l=”$ e x i t s tm t r e a c h e d 1 ” ID=”14”>2 <t u p l e> <atom l a b e l=” f a l s e $0”/> </ t u p l e>3 <t yp e s> <t ype ID=”6”/> </ t yp e s>4 </ skolem>5

6 <sko lem l a b e l=”$ e x i t s tm t r e a c h e d 2 ” ID=”15”>7 <t u p l e> <atom l a b e l=” f a l s e $0”/> </ t u p l e>8 <t yp e s> <t ype ID=”6”/> </ t yp e s>9 </ skolem>

10

11 <sko lem l a b e l=”$ v a r 2 f 0 ” ID=”16”>12 <t u p l e> <atom l a b e l=” a r e du t a c o As s e r tExamp l e $0”/> </ t u p l e>13 <t yp e s> <t ype ID=”13”/> </ t yp e s>14 <t yp e s> <t ype ID=”4”/> </ t yp e s>15 </ skolem>16

17 <sko lem l a b e l=”$ v a r 2 f 1 ” ID=”17”>18 <t u p l e> <atom l a b e l=” n u l l $0”/> </ t u p l e>19 <t yp e s> <t ype ID=”13”/> </ t yp e s>20 <t yp e s> <t ype ID=”4”/> </ t yp e s>21 </ skolem>22

23 <sko lem l a b e l=”$ o 0 ” ID=”18”>24 <t u p l e> <atom l a b e l=” n u l l $0”/> </ t u p l e>25 <t yp e s> <t ype ID=”13”/> </ t yp e s>26 <t yp e s> <t ype ID=”4”/> </ t yp e s>27 </ skolem>28

29 <sko lem l a b e l=”$ r e t u r n 0 ” ID=”19”>30 <t u p l e> <atom l a b e l=” f a l s e $0”/> </ t u p l e>31 <t yp e s> <t ype ID=”6”/> </ t yp e s>32 </ skolem>33

34 <sko lem l a b e l=”$ r e t u r n 1 ” ID=”20”>35 <t u p l e> <atom l a b e l=” f a l s e $0”/> </ t u p l e>36 <t yp e s> <t ype ID=”6”/> </ t yp e s>37 </ skolem>38

39 <sko lem l a b e l=”$ throw 0 ” ID=”21”>40 <t u p l e> <atom l a b e l=” n u l l $0”/> </ t u p l e>41 <t yp e s> <t ype ID=”10”/> </ t yp e s>42 <t yp e s> <t ype ID=”4”/> </ t yp e s>43 </ skolem>44

45 <sko lem l a b e l=”$ throw 1 ” ID=”22”>46 <t u p l e> <atom l a b e l=” n u l l $0”/> </ t u p l e>47 <t yp e s> <t ype ID=”10”/> </ t yp e s>48 <t yp e s> <t ype ID=”4”/> </ t yp e s>49 </ skolem>50

51 <sko lem l a b e l=”$ throw 2 ” ID=”23”>52 <t u p l e> <atom l a b e l=” A s s e r t i o n F a i l u r e L i t $0”/> </ t u p l e>53 <t yp e s> <t ype ID=”10”/> </ t yp e s>54 <t yp e s> <t ype ID=”4”/> </ t yp e s>55 </ skolem>

Figura 4: XML con la informacion de diferentes atomos instanciados en el contrajemplo

5

Este corto y simple ejemplo sirve para entender la motivacion del presente trabajo. En primerlugar, la ejecucion de herramientas desde lınea de comando no suele ser lo mas intuitivo o comodo.Si bien no se niega la posibilidad de que existan herramientas para los cuales este esquema resulteutil, TACO no pareciera ser el caso. Cuando un usuario desea ejecutar un analisis, debe definir unaserie de parametros para lo cual, dependiendo de su experiencia con la herramienta, es probableque deba consultar el manual. La posibilidad de contar con una herramienta visual que permita laejecucion de TACO deberıa fomentar la verificacion de los metodos desarrollados. Siguiendo estalınea, los programadores suelen utilizar IDEs al momento de desarrollar software y la integracioncon estas herramientas facilitarıa la ejecucion de analisis.

En segundo lugar, observando el resultado obtenido es evidente que la informacion brindada nodice mas que hubo error a un usuario inexperto. Para usuarios expertos, TACO brinda informacionsobre el contrajemplo encontrado pero esta es muy dificil de leer y su analisis puede resultar enuna tediosa tarea. Esto es inaceptable si se espera la masificacion de este tipo de herramientasy su adopcion en un entorno industrial. Un usuario interesado en la verificacion de un programadesarrollado espera, pero sobre todo necesita, mas informacion que le permita corregir el programapara poder lograr la verificacion del software y que su interpretacion se de en el mismo nivel deabstraccion que el maneja, es decir, codigo fuente Java. Por lo tanto, la salida de estandar deTACO resulta insuficiente y su ampliacion y clarificacion derivan en otra de las motivaciones delpresente trabajo.

En la seccion 4 se presenta un caso de estudio donde se amplian los problemas de usar TACOmediante la lınea de comando y se presentan las ventajas de lo desarrollado en el presente trabajoutilizando un ejemplo mas complejo.

1.2. Trabajos Relacionados

Ademas de TACO, existen otras herramientas de verificacion. Antes de inciar el presente tra-bajo, se realizo un analisis sobre las herramientas disponibles en el mercado que permiten realizarverificacion de programas y su usabilidad.

Para el analisis de programas escritos en C/C++:

F-Soft, presentada en [8]. No pudo ser analizada debido a que no se encuentra publicamentedisponible.

CBMC, presentada en [9]. Esta herramienta de verificacion acotada fue desarrollada enCarnegie Mellon. Aunque detalla la asercion violada e imprime la traza con el error, nopermite al usuario inspeccionarla dinamicamente ni evaluar expresiones a lo largo de lamisma.

Por el lado de Java, entre las opciones disponibles se hallan:

Miniatur, presentada en [10]. No pudo ser analizada debido a que no se encuentra publica-mente disponible.

Forge, presentada en [11]. Forge es la herramienta mas parecida a TACO entre las nombra-das. Es una herramienta desarrollada por el Instituto de Tecnologıa de Massachusetts (MIT)que es capaz de realizar la verificacion estatica de codigo Java contra su especificacion enlenguaje JML. La version actual de Forge incluye un plugin para Eclipse conocido comoJForge [12]y, como CBMC, indica que parte de la especificacion ha sido violada. Tambienpresenta un grafo con el estado de la memoria pero restringido a los estados incial y final de latraza. El plugin permite al usuario la visualizacion de la traza que conlleva al contraejemplopero representada en un lenguaje intermedio.

Finalmente, en lo que se refiere a software desarrollado en C#, en [13] se genera un ejecutableque reproduce el error encontrado por la verificacion de Spec#. El objetivo del programa generado

6

no es solo la comprension de la falla, sino la deteccion de errores espureos. Como aquı la ejecucionno es simbolica sino que el programa realmente se ejecuta, moverse hacia atras en la traza noesta permitido.

Continuando con el analisis de herramientas que trabajan sobre codigo C#, en [14] se presen-ta una herramienta conocida como Boogie Verification Debugger (BVD de ahora en mas). Estaherramienta es lo que mas se acerca a lo aquı presentado, brindando la posibilidad de navegarla traza hacia adelante y hacia atras y la evaluacion de variables en distintos puntos. Se incluyeun plugin para Visual Studio que permite la verificacion utilizando los front-ends VCC y Dafny.Aunque BVD permite listar informacion que puede ser util al programador, como ser los aliaspara un objeto determinado, BVD no hace hincapie sobre la visualizacion de esta informacion,presentandola de una forma poco intuitiva.

1.3. Estructura del informe

El presente informe se encuentra estructurado de la siguiente forma.En el capıtulo 2 se incluye una introduccion a TACO, su arquitectura y su modo de uso.Continuando con el capıtulo 3 se introducen las contribuciones realizadas sobre TACO que

dan soporte a la construccion de un plugin para Eclipse que permite el uso de TACO desde estaIDE. Adicionalmente se enumeran las principales caracterısticas de TacoPlug en conjunto con losbeneficios brindados.

En el capıtulo 4 se desarrolla un caso de estudio en el que se muestra y compara el analisisde un programa utilizando TACO y TacoPlug. Se incluye una demostracion de los problemas deusabilidad que presentaba TACO anterior al desarrollo de este trabajo.

La arquitectura de las tecnicas disenadas en el presente trabajo y su implementacion comoparte de TACO en conjunto con el diseno de TacoPlug son presentados en el capıtulo 5. En estecapıtulo, ademas, se detallara como es la interaccion entre TACO y TacoPlug.

El capıtulo 6 incluye un resumen del trabajo desarrollado y los resultados obtenidos. Se pre-sentan aquı las conclusiones alcanzadas con respecto a los objetivos planteados.

Finalmente, el capıtulo 7 propone una serie de puntos sobre los que puede trabajarse a futuropara seguir incrementando la usabilidad de herramientas de verificacion y acercandolas a las manosde los desarrolladores.

7

2. TACO

2.1. Definiciones previas

Antes de introducir TACO propiamente dicho conviene repasar algunas definiciones previasque utilizaremos frecuentemente.

Precondicion: es un predicado que debe ser verdadero en el estado previo a la ejecuciondel metodo sobre el cual esta definido.

Poscondicion: es un predicado que debe ser verdadero en el estado final de la ejecucion delmetodo sobre el cual esta definido.

Correctitud parcial: el termino correctitud se emplea para indicar que un algoritmo escorrecto respecto a su especificacion. Decimos que un algoritmo es parcialmente correcto sial cumplirse su precondicion, y en caso de terminar, se cumple la poscondicion. Decimosque el algoritmo es correcto si es parcialmente correcto y ademas podemos afirmar que elalgoritmo termina.

Loop unrolling: es una tecnica que transforma los ciclos, que potencialmente pueden iteraruna cantidad no acotada de veces, en sentencias equivalentes a las primeras n iteraciones.Debido a esto, la cantidad de iteraciones generadas con unrolling puede ser menor a lacantidad real de iteraciones que realizarıa el ciclo.

Sat-Solving: un problema de decision es una pregunta expresada en algun sistema formalcuya respuesta es sı o no dependiendo del valor de los parametros de entrada. El problemade satisfactibilidad (SAT) se enmarca dentro de los problemas de decision, cuyas instanciasson expresiones booleanas escritas con parentesis, variables y los operadores logicos and, ory not.

La pregunta que debe intentar responderse es si, dada la expresion booleana, existe unaasignacion de valores True o False a las variables (esto se conoce como valuacion) de laexpresion que hagan que dicha expresion sea verdadera.

El problema de la satisfactibilidad booleana se encuentra dentro de los problemas NP-Completos, lo que en principio sugiere que el tiempo que demanda su resolucion puedeser exponencial con respecto al tamano de la entrada.

Analisis Whole Program: se conoce con este nombre a un analisis que toma el programacomo un todo en vez de hacerlo modulo por modulo.

Weakest Precondition: es una tecnica para representar un programa como una formulalogica para lo cual se le asigna una semantica particular a cada instruccion. Esta tecnicarequiere la presencia de una poscondicion y establece que WP(Program, Post) es una formulalogica que permite caracterizar al conjunto maximal de estados tal que si a un estado quecumple WP(Program, Post) se le aplica el programa Program, y este termina, el estadoresultante cumpla la formula Post. Para mas informacion acerca de esta tecnica consultar [15].

JML : Java Modeling Language es un lenguaje de especificacion que puede ser utilizadopara describir el comportamiento de modulos Java. Combina elementos de diseno basadoen contratos de Eiffel [16] y la especificacion basada en modelos de la familia de lenguajesLarch [17], con algunos elementos de calculo de refinamiento [18]. Mas informacion sobreeste lenguaje puede encontrarse en [19]

JFSL : JForge Specification Language es un lenguaje de especificacion formal basado en JMLy en la idea de que expresiones en lenguaje Alloy son muy eficientes a la hora de describir elcomportamiento de un programa. JFSL fue desarrollado como parte de la herramienta Forgemencionada anteriormente.

8

2.2. Introduccion

TACO es una herramienta desarrollada por el Relational Formula Method Research Group [20]del Departamento de Computacion de la Facultad de Ciencias Exactas y Naturales de la Universi-dad de Buenos Aires para realizar la verificacion formal de programas Java contra su especificacionen lenguaje JML o JFSL. TACO utiliza la tecnica de verificacion acotada en la cual todas las ejecu-ciones de un procedimiento son examinadas tomando en cuenta dos cotas definidas por el usuario:el maximo numero de instancias de una clase presentes en el heap y la cantidad de loop unrolls.

TACO utiliza las tecnicas de whole program analysis y weakest precondition para transformarlos programas en una formula logica llamada Condicion de Verificacion (VC) y utiliza SAT-Solvingpara validar o refutar dicha formula.

2.3. Arquitectura

Para lograr su objetivo de verificar la correctitud de un programa Java contra su especificacion,TACO presenta un pipeline en el que realiza diferentes transformaciones sobre el programa original,simplificandolo en cada etapa, hasta lograr construir la Condicion de Verificacion.

Este pipeline esta explicado, a alto nivel, por la figura 5. En esta figura, los elementos circularesrepresentan artefactos mientras que los rectangulares representan componentes.

Figura 5: Etapas de transformacion del codigo JML hasta codigo Alloy

La arquitectura de TACO esta fuertemente determinada por el pipeline de transformacion delenguajes en el que basa su funcionamiento. A grandes rasgos, cada una de las etapas del pipelinese encuentra representada por una stage a nivel implementativo.

Sin embargo, es importante resaltar algunas caracterısticas de diseno que escapan a este esque-ma. La diferencia mas significativa se encuentran en la correspondencia entre stages y etapas delpipeline. Existen stages que no representan etapas del pipline, generalmente asociados a procesosposteriores a la deteccion de un contraejemplo. Un ejemplo de esta situacion es la stage conocidacomo JUnitStage, componente que permite la construccion de tests de unidad basados en loscontraejemplos detectados por TACO.

Otra caracterıstica importante de la arquitectura de TACO es el almacenado de informacionde transformacion del programa original entre las distintas etapas que se ejecutan. Esta infor-macion permite tener trazabilidad entre las distintas representaciones del programa brindando laposibilidad de visualizar contraejemplos Alloy (ver mas adelante) a nivel Java.

En las siguientes subsecciones se hara un breve repaso de cada una de las etapas involucradas,su objetivo e importancia. Para mayor detalle sobre la arquitectura de TACO se recomienda lalectura de [7].

Antes de detallar las traducciones dadas en cada una de las etapas resulta conveniente definircada uno de los lenguajes intermedios y revisar sus principales caracterısticas:

Alloy. Alloy [21] es un lenguaje relacional de especificacion formal cuya sintaxis permiteexpresar tipos abstractos de datos utilizando signaturas. Tambien es posible agregar restric-ciones sobre dichas signaturas. Ciertas funcionalidades de Alloy se asemejan a caracterısticasde los lenguajes orientados a objetos. A continuacion se muestra un ejemplo del lenguajeAlloy. Supongase que se desea especificar una libreta de direcciones para lo cual hay que

9

modelar tipos de datos para los nombres y las direcciones. Para esto es posible empezar indi-cando la existencia de dos grupos disjuntos para nombres y direcciones. Esto es especificadoen Alloy como signaturas como se muestra a continuacion:

sig Address {} sig Name {}

Con estos nombres y direcciones se esta en condiciones de definir la libreta. Una posible de-fincion de la misma es considerar que una libreta consiste de contactos y un mapeo total entrelos contactos y sus direcciones. Esto se especifica en Alloy como se muestra a continuacion:

sig Book {contacts:set Name,

addressOf: contacts → one Address}

Mas informacion sobre Alloy puede encontrarse en [22]

DynAlloy. DynAlloy [15] es una extension de Alloy que permite definir acciones atomi-cas que modifican el estado. Ademas permite utilizar esas acciones para construir accionesmas complejas. Las acciones atomicas son definidas en terminos de su precondicion y pos-condicion. DynAlloy toma el sistema de tipos, expresiones y formulas Alloy e incorpora lahabilidad de especificar y chequear automaticamente aserciones de correctitud parcial, paralo cual incorpora la keyword assertCorrectness. Siguiendo con el ejemplo anterior, si sedesea definir una accion para modificar una libreta de direcciones agregando un contacto, elcodigo DynAlloy que modela esta accion es el siguiente:

{true}AddContact [b: Book, n: Name, a: Adreess]

{b’.contacts = b.contacts + n && b’.addressOf = b.addressOf ++ (n→a)}

Esto implica que cada vez que se cumpla la precondicion, en este caso true, osea, siempre,y se ejecute la accion AddContact, si este termina, se llegara a un estado que satisface laposcondicion, es decir, existe un nuevo contacto en la libreta y su direccion fue agregada almapeo de direcciones. Las variables primadas representan el estado final de la ejecucion.

Informacion adicional sobre DynAlloy puede encontrarse en [23].

JDynAlloy. JDynAlloy [7] Es un lenguaje de especificacion relacional, ya que sus tipos dedatos son relacionales, creado con el objetivo de disponer de una representacion intermediaentre los lenguajes de alto nivel y DynAlloy que permitiese reducir la complejidad de traduciry analizar codigo de alto nivel. Al igual que muchos lenguajes de alto nivel, en JDynAlloypueden representarse ciclos, condicionales, asignaciones, llamados a metodos, expresiones,etc. Ademas agrega la posibilidad de incorporar invariantes de clase, invariantes de instancia,precondiciones y poscondiciones usando logica de primer orden.

Java anotado a JML Simplificado

La etapa de simplificacion toma como entrada codigo Java con anotaciones JML/JFSL y generacomo salida codigo JML Simplificado. Este lenguaje no es distinto a Java con JML/JFSL y estatransformacion simplemente tiene como objetivo reducir la cantidad de estructuras que deberanser manejadas en la etapa de traduccion a JDynAlloy.

Dentro de las principales modificaciones que se realizan podemos mencionar:

La inicializacion de campos es trasladada a cada constructor de la clase. En caso de que noexista una declaracion explıcita de al menos un constructor, el simplificador creara explıci-tamente uno por defecto y colocara allı la inicializacion de los campos.

10

Se reduce la cantidad de estructuras de ciclos, transformandolos a la estructura de un while.

Se simplifica el llamado a metodos en anotaciones JML. Basicamente, se introduce un exis-tencial que cuantifica una unica variable por cada llamado, luego se asigna el resultado delmetodo a su correspondiente variable cuantificada. Este procedimiento es necesario debi-do a que en Java los llamados a metodos son expresiones, mientras que en JDynAlloy sonpredicados.

Los condicionales son reestructurados para simular la evaluacion lazy que se realiza en Java.Para ello se realiza una construccion con sentencias if anidadas que computan el resultadodel condicional en una variable booleana.

Con el objetivo de evitar la colision de nombres entre variables, el simplificador realiza unrenombre de las variables miembro de las clases y tambien de los parametros de los metodos.

JML Simplificado a JDynAlloy

En esta seccion abordaremos el proceso de transformacion de codigo JML Simplificado allenguaje de especificacion JDynAlloy. Gracias a que ciertas estructuras de JDynAlloy emulanestructuras propias de lenguajes orientados a objetos, la transformacion de un lenguaje de dichoparadigma a JDynAlloy es bastante directa.

Por cada clase Java, se define un modulo JDynAlloy que contendra la definicion de sus varia-bles miembro representada por los fields y cada metodo sera representado por un program enJDynAlloy.

La mayorıa de las sentencias JML tienen una correspondencia directa con sentencias JDynAlloypor lo que a continuacion se presentaran aquellos casos en los que esta regla no se cumple:

Manejo de excepciones. La construccion try{} catch{} se traduce a una serie de con-dicionales que incluyen comparaciones contra una nueva variable, throw, que simula la pre-sencia de una excepcion.

Cortes de control. Java brinda la posibilidad de realizar cortes de control en el codigomediante el uso de keywords como return o throw. Es decir, dentro de un metodo, un pro-gramador puede introducir multiples puntos de retorno, lo que produce que ciertos caminosde ejecucion no sean alcanzados.

Para lograr este comportamiento, el traductor incorpora una variable booleana a cada pro-grama, la cual indicara si se ejecuto alguna instruccion que produzca un corte de la ejecuciondel metodo (ya sea mediante un return o una instruccion throw). Dicha variable se utilizapara encapsular la ejecucion de cada lınea de codigo dentro de un condicional que verifiquesi se llego o no a una instruccion de corte de control.

Traduccion de expresiones sin correspondencia. Como se menciono anteriormente,la traduccion de JML Simplificado a JDynAlloy es bastante directa, por lo que la mayorıade estas construcciones tienen un mapeo uno a uno. Por ejemplo, keywords como assert,assume, invariant, requires, ensures, etc. tiene su contraparte directa en el lenguajeJDynAlloy. Sin embargo, esto no siempre es el caso. Para algunas circunstancias hay queencontrar mecanismos para reproducir el comportamiento. Un ejemplo de esto es la palabrareservada non null, la cual previene que una variable pueda tomar el valor null. Paralograr dicho efecto, el traductor agrega la clausula not(variable = null) a la precondicion,poscondicion del metodo o al invariante de la clase, dependiendo del caso.

Por otro lado, un punto interesante del lenguaje JML es que no solo permite especificar elcomportamiento normal de un metodo, sino que tambien permite especificar comportamientosexcepcionales. Esto se logra usando las keywords normal behavior y exceptional behavior res-pectivamente. De la misma forma, luego de la traduccion a JDynAlloy se crearan dos casos deespecificacion, uno para el comportamiento normal y otro para el excepcional.

11

JDynAlloy a DynAlloy

La transformacion de un modulo JDynAlloy a DynAlloy, sin ser un proceso trivial, presentavarias correspondencias directas simplificando la traduccion.

En primer lugar, caben algunas definiciones. La relacion entre una invocacion a un programa(o a su especificacion) y su definicion se conoce como binding. Cuando en un modulo existenmultiples programas con el mismo nombre pero distintos parametros se dice que el programaesta sobrecargado.

El proceso de resolucion de los bindings toma en cuenta dicha particularidad de los programassobrecargados. JDynAlloy genera bindings utilizando reglas similares a las de Java [24]. La prin-cipal diferencia es que Java tiene en cuenta la visibilidad de los metodos, concepto que no tienecontrapartida en JDynAlloy. El hecho de que en JDynAlloy varios metodos puedan tener el mismonombre debe ser manejado por el traductor, ya que DynAlloy no lo permite. La solucion consisteen renombrar los programas, para que no se repitan los nombres, y modificar las invocaciones parareflejar dicho renombre.

Por otro lado, en JDynAlloy un modulo puede sobreescribir un programa declarado por sumodulo padre solo si en el programa original esta marcado como virtual. Para estos casos, en latraduccion a DynAlloy se reescribira la definicion del metodo virtual. El objetivo es simular eldispatching en tiempo de ejecucion de los lenguajes orientados a objetos agregando codigo deldispatcher que invocara al metodo correcto correspondiente al tipo concreto de la instancia thiz.

Otro punto importante de la traduccion consiste en la resolucion del callSpec, unica formulade JDynAlloy que no posee su contrapartida en DynAlloy. JDynAlloy permite utilizar llamados ametodos dentro de las especificaciones. Este comportamiento es analogo al de JML. Para repre-sentarlo JDynAlloy extiende las formulas de DynAlloy con la formula callSpec. Como finalmentelas expresiones deben transformarse en expresiones DynAlloy, es necesario reemplazar las formulascallSpec por codigo DynAlloy equivalente. Para esto se utiliza la tecnica de inlining, reempla-zando la invocacion del metodo por su Condicion de Verificacion.

La traduccion de otras sentencias JDynAlloy se realiza, generalmente, de manera directa, aun-que existen aquellas que requieren auxiliares de DynAlloy en su traduccion.

Finalmente, se genera en DynAlloy un assertCorrectness para realizar la verificacion delprograma como se muestra en el codigo 6.

1 a s s e r t C o r r e c t n e s s c h e c k A f 0 [ . . . ] {2 pre={3 p r e c o n d i c i o n A f 0 [ . . . ]4 }5 program={6 c a l l A f 0 [ . . . ]7 }8 pos t={9 p o s t c o n d i t i o n A f 0 [ . . . ]

10 }11 }

Figura 6: Ejemplo de assertCorrectness para el programa A::f

El predicado precondicion (lınea 4) sera construido como la conjuncion de los siguientes ele-mentos:

1. La precondicion del programa que se desea analizar.

2. Los class invariants de todos los modulos.

3. Los object invariants de los modulos relevantes para el analisis del programa.

12

El programa DynAlloy A f 0 es la traduccion del programa JDynAlloy a DynAlloy. Dichatraduccion consiste en la traduccion de las sentencias que lo componen. En la asercion se invocaa A f 0 (lınea 7).

El predicado poscondicion (lınea 10) sera generado realizando la conjuncion de los siguienteselementos:

1. La poscondicion del programa que se desea analizar.

2. Los class invariants de todos los modulos.

3. Los object invariants de los modulos relevantes para el analisis del programa.

4. Los constrains del modulo analizado.

DynAlloy a Alloy

Como se menciono anteriormente, DynAlloy es una extension de Alloy y el proceso de traduc-cion de DynAlloy a Alloy esta basado en el mecanismo de Weakest Precondition. Este procesoes muy complejo e implica la traduccion de una nocion de estado a un predicado. No se incluyeaquı por escapar al alcance de este trabajo. Puede encontrare mas informacion en [15, 23].

Para la verificacion final existe un programa llamado Alloy Analyzer que permite realizar laverificacion automatica de una asercion dentro de un scope acotado. Por ejemplo, el siguientecomando verificara que la asercion sea verdadera utilizando todas las combinaciones posibles deconjuntos (signaturas) que posean hasta 5 elementos.

check ToEmpty for 5

Si el Alloy Analyzer encuentra un contraejemplo lo presenta ya sea en forma de texto o grafi-camente, e indica que la asercion no es valida.

De esta forma, se agrega al programa Alloy la instruccion para realizar la verificacion y se loenvıa al Alloy Analyzer.

2.4. Uso y resultado

TACO requiere Java 1.6 y, hasta el momento de desarrollo del presente trabajo, la unica formade ejecutar un analisis utilizando esta herramienta era mediante lınea de comando siguiendo, agrandes rasgos, el siguiente esquema basico:

java -jar taco.jar -cf {configfile} -c {classname} -m {methodname}

donde el primer parametro es un archivo de configuracion y el segundo y tercer parametrorepresentan el nombre de la clase y del metodo a analizar respectivamente.

TACO esta disponible para las siguientes arquitecturas: amd64-linux, x86-freebsd, x86-linux,x86-mac, x86-windows.

Una vez completado el analisis de un programa, TACO informara del resultado utilizandola salida estandar indicando si se pudo satisfacer la Condicion de Verificacion, informando si seencontro un error o no. Hasta el desarrollo de esta tesis, no se incluıa en el informe del error, dondefue detectado, el estado de las variables en ese momento y tampoco que asercion fallo.

13

3. TacoPlug

3.1. Introduccion

En la presente seccion se presenta TacoPlug, un plugin que integra TACO a Eclipse [25]. Eclipsees una IDE ampliamente difundida y utilizada tanto en ambientes academicos como industrialesque permite el desarrollo de aplicaciones en distintos lenguajes como ser Java, C++ o Python;se encuentra disponible para todas las grandes plataformas y, como TACO, esta desarrollada casicompletamente en Java. Una caracterıstica distintiva de Eclipse es su soporte para agregar nuevasfuncionalides mediante un sofisticado sistema de plugins.

Debido a esto, la construccion de un plugin para esta IDE que permita la integracion conTACO parecio ser la opcion natural.

TacoPlug es el resultado de un esfuerzo por hacer TACO mas amigable y practico al usuario.Una vez instalado permite realizar una verificacion acotada sobre cualquier metodo de su eleccion.Se adopto como premisa que el usuario no necesitase conocer nada sobre la arquitectura de TACOo la presencia de lenguajes intermedios. De esta forma se planteo como objetivo que toda lainformacion que se mostrase al usuario debıa ser provista en lenguaje Java o al menos en este nivelde abstraccion.

TacoPlug ademas provee a Eclipse de una nueva perspectiva que incluye un conjunto de nuevasvistas que proveen mecanismos para debuggear el programa bajo analisis.

El desarrollo de este plugin debio ser dividido en dos etapas. Primero debieron disenarse lastecnicas y los mecanismos que se creıan necesarios para dar soporte a los requerimientos funcionalesdefinidos para el plugin, para luego implementarlos como contribuciones a TACO. En una segundaetapa se disenarıa y construirıa el plugin mismo.

Mientras que en la seccion 3.2 se presentan las contribuciones realizadas sobre la herramientaTACO, la seccion 3.3 describe las distintas funcionalidades del plugin. Finalmente, en el capıtulo 5se presenta la arquitectura y diseno del plugin.

3.2. Contribuciones a TACO

Para mejorar la usabilidad de la herramienta de verificacion TACO, debieron disenarse unaserie tecnicas que brindaran la posibilidad de cumplir con los requerimientos que se consideraronindispensables para lograr una herramienta mas amigable en su uso.

Se trabajo, principalmente, sobre cuatro ejes que seran comentados en las siguientes subsec-ciones:

1. Trazabilidad del error encontrado a nivel Java.

2. Evaluacion de expresiones JML y JFSL.

3. Validacion de predicados.

4. Visualizacion global de la memoria.

3.2.1. Trazabilidad Java

La trazabilidad tiene como principal objetivo la visualizacion de la traza a nivel Java quegenera el error detectado por TACO. Para esto se extendio un mecanismo desarrollado en [26] quepermite la obtencion de la traza a nivel DynAlloy y a partir de esta, reconstruir su correspondenciaen codigo Java.

De esta forma el usuario cuenta con la posibilidad de hacer un seguimiento de las instruccionesJava que fueron ejecutadas hasta obtener el error y poder ası entender de donde proviene la falla.

14

3.2.2. Evaluacion de expresiones JML y JFSL

Para poder analizar una traza, suele no ser suficiente visualizar los puntos de ejecucion quegeneraron la falla, sino que puede requerirse revisar el contenido de distintas variables que consti-tuyen el contexto de ejecucion de esa traza. Con el objetivo de dotar al plugin de esta capacidad,se trabajo para proveer a TACO de un mecanismo que permitiera la evaluacion de expresionesJML y JFSL.

De esta forma es posible evaluar expresiones arbitrarias escritas en lenguaje JML/JFSL ychequear su validez para un determinado punto de la ejecucion simbolica fallida encontrada porTACO.

3.2.3. Validacion de predicados

Como se ha dicho, TACO transforma el programa Java en una formula logica conocida comoCondicion de Verificacion compuesta por un predicado que incluye la poscondicion del metodoanalizado y los object invariants.

Cuando TACO reporta un error, no informa si el problema encontrado proviene del incumpli-miento de una poscondicion o un object invariant. Esta informacion resulta de vital importanciaal usuario para poder empezar a investigar donde se encontro la violacion a la especificacion.

Se incorporo a TACO un mecanismo para identificar que formula es la que fallo. Para estose hace uso de la evaluacion de expresiones JML/JFSL, segun el lenguaje en el que se encuentreescrita la especificacion, en el ultimo punto de la traza obtenida del contraejemplo.

3.2.4. Visualizacion global de la memoria

Cuando se construyen programas con estructuras recursivas o con objetos complejos que con-tienen como campos otros objetos complejos, la visualizacion del contenido de una variable nosuele ser suficiente para comprender el contexto de ejecucion.

Es por esto que se desarrollo un mecanismo que permite conocer el estado del heap en unpunto determinado de la ejecucion simbolica desarrollada por TACO. Este mecanismo analiza elprograma y el punto de ejecucion seleccionado para detectar las variables relevantes (variablesmiembro, variables locales, parametros) y construir un grafo que contenga el valor de las mismasen ese punto.

3.3. Caracterısticas de TacoPlug

La segunda etapa del desarrollo del plugin se focalizo principalmente en aspectos relacionadoscon la usabilidad y en brindar la usuario herramientas que permitieran el debugging y la locali-zacion de un error reportado por TACO. Esto incluyo el diseno y desarrollo de los componentespresentados en las siguientes secciones para los cuales se utilizo la infraestructura PDE [27] ademasde algunos componentes particulares que se mencionaran en las secciones correspondientes.

3.3.1. Configurando TACO

El primer paso para poder integrar TACO a Eclipse fue brindar la posibilidad de configurar losdiversos parametros que componen TACO. Para esto se incorporo a la pantalla de configuracionde Eclipse una subseccion llamada Taco Configuration. Desde esta pantalla, que se muestra enla figura 7, es posible especificar distintos valores que requiere TACO para su funcionamiento,principal y obligatoriamente el tamano del scope y la cantidad de loop unrolls.

Como se menciono anteriormente, TACO realiza una verificacion acotada, lo que significa queson examinadas todas las ejecuciones de un procedimiento dentro de los parametros definidos porel usuario: la cantidad de instancias de una clase presentes en el heap (definido por el tamano delscope) y la cantidad de loop unrolls. Por este motivo, estos valores siempre deben definirse.

Ademas de estos parametros, existen otros valores de configuracion para TACO que puedendefinirse en esta pantalla.

15

Figura 7: Pantalla de configuracion de TACO

Por otro lado, TACO requiere algunos parametros extra para funcionar que no se configurandesde esta pantalla sino que se calculan automaticamente. Ademas de lograr mayor usabilidad,al desarrollar un plugin para Eclipse para integrar TACO, se pueden utilizar algunos mecanismosprovistos por la IDE para calcular algunos de los parametros necesitados utilizando conceptosdisponibles al trabajar con unidades como proyectos Java . Estos parametros son propios de cadaejecucion de un analisis por lo que se explicaran en la siguiente subseccion.

3.3.2. Ejecutando un analisis

La ejecucion de TACO desde lınea de comando, como se menciono anteriormente, complica suuso. Es por eso que una de las primeras funcionalidades que fueron desarrolladas para el pluginfue la capacidad de ejecutarlo desde Eclipse, de una manera similar a como se ejecuta un test dejUnit [28].

Para esto se desarrollo un launcher, llamado TACO Launcher, que permite definir el metodo aanalizar en conjunto con el tipo de analisis a realizar. Este launcher es accesible desde la ventanaque permite ejecutar aplicaciones Java, tests de jUnit, etc, conocida en Eclipse como ‘Run as...‘ ypuede verse una captura del mismo en la figura 8.

Para esta vista, se decidio que debıa indicarse el proyecto que se va a analizar, que clase yque metodo en particular. Para estos tres elementos se desarrollaron buscadores que analizanworkspace, proyectos y clases, respectivamente, para acotar la busqueda del usuario a lo ya selec-cionado si se va de lo general a lo particular. Sin embargo, si no se seleccionan elementos generales,por ejemplo, no se selecciona proyecto, el buscador de clases mostrara todas las clases disponiblesen el workspace. De la misma forma, si no se selecciona una clase, se mostraran todos los metodosanalizables en el workspace. Ademas, si en estas condiciones se busca y selecciona un metodo, loscampos de clase y proyecto se completaran automaticamente con la informacion acorde.

Adicionalmente, desde esta pantalla es posible definir si el analisis que se desea realizar es detipo Run o Check. Un analisis de tipo Run solamente prueba que exista un camino de ejecucion

16

Figura 8: Pantalla de ejecucion de analisis TACO

buscando una instancia que ejecute el codigo, lo cual permite chequear que el invariante sea co-rrecto. Un analisis de tipo Check valida el programa contra su especificacion.

Como se comento anteriormente, algunos parametros propios de cada ejecucion de un analisisse calculan automaticamente:

Directorio con el codigo a analizar. El primer caso en el que se dio esta situacion esel caso de jmlParser.sourcePathStr, parametro utilizado para definir donde se buscan losarchivos fuente a ser analizados. Este parametro se computa automaticamente conociendoque clase se desea analizar, parametro registrado en el launcher.

Conjunto de clases relevantes. El segundo parametro que es calculado automaticamentees relevantClasses que representa al conjunto de clases relevantes. En este caso, ademasde lograrse automatizacion, se logra precision porque se incluyen exactamente las clases delas cuales un metodo depende, no las clases de las cuales depende la clase en su conjunto.

3.3.3. TACO Perspective

Cuando se completa un analisis TACO, la Consola muestra el resultado del mismo. En casode encontrarse una falla, se le presenta al usuario la posibilidad de utilizar una serie de vistasdesarrolladas con el objetivo de debuggear y localizar la falla en cuestion. Estas vistas se encuentranagrupadas bajo una nueva perspectiva de Eclipse conocida como TACO Perspective.

Esta perspectiva se asemeja a la de Debugging incluida en Eclipse e incluye vistas que permitenal usuario inspeccionar estaticamente el metodo bajo analisis, la traza del error y el valor de lasdistintas variables involucradas en los distintos puntos de ejecucion. La figura 9 muestra la nuevaperspectiva.

17

Figura 9: TACO Perspective

3.3.4. JML/JFSL Annotation Explorer

Una vez completado un analisis, la primera vista que resulta util es la conocida bajo el nombrede JML/JFSL Annotation Explorer. Esta vista lista todas las anotaciones del programa analizadoy su valor final permitiendo al usuario aislar que formula JML o JFSL de la especificacion no fuesatisfecha, como se muestra en la figura 10.

Figura 10: JML/JFSL Annotation Explorer

Para el desarrollo de este componente fue necesaria la evaluacion de expresiones JML/JFSLque se comento en la seccion 3.2.

3.3.5. Java Error Trace

Detectada que formula de la especificacion no fue satisfecha en la verificacion realizada porTACO, resulta util poder analizar la traza que genera el error detectado. Para lograr este analisisse desarrollo un componente que permite la visualizacion y navegacion de la traza reportada conformato de arbol, como se muestra en la figura 11.

Esta vista permite debuggear un analisis TACO de una manera similiar a como se debuggeaun programa usando la vista de Stack Trace incluida en la perspectiva de debugging provista por

18

Figura 11: Componente de visualizacion de la traza Java

Eclipse. La diferencia con esta es que, al tratarse en este caso de una ejecucion estatica, se puedeavanzar y retroceder en la traza segun se lo requiera.

Java Error Trace esta organizada en forma de arbol donde cada nodo representa un punto enla ejecucion y los nodos padre representan llamadas a metodos. Cada nodo contiene una etiquetacompuesta por el nombre de la clase de ese punto de ejecucion y los numeros de lınea y columna,en ese orden. Hacer doble click en cualquiera de los nodos causara la localizacion del foco delcursor en la correspondiente lınea Java del archivo fuente.

Es posible que algunos numeros de lıneas se encuentren repetidos en la traza. Esto se debe aque en Java es posible combinar llamados a metodos, como se muestra en la figura 12.

1 o b j e c t . methodA (methodB ( ) ) ;

Figura 12: Ejemplo de combinacion de llamados a metodos en Java

Para estos casos se generaran 2 nodos padres en la traza donde uno contiene el llamado methodB

y el otro a methodA. Estos nodos tendran el mismo numero de lınea pero diferiran en el numerode columna.

3.3.6. JML/JFSL Evaluator

TACO es una herramienta pensada para ser utilizada con programas que tengan definidasespecificaciones en JML o JFSL. Por lo tanto, a medida que se navega la traza, resulta util saberel valor de las distintas variables que intervienen en un punto de ejecucion. Ademas tambien podrıaquerer saberse el valor de computar determinada formula JML o JFSL.

Con este objetivo, se introduce la vista JML/JFSL Evaluator. Esta vista permite definir ex-presiones JML/JFSL y evaluarlas en distintos puntos de la traza. Es similar a la vista Expressionscontenida en la perspectiva Debug y en la figura 13 se muestra un ejemplo.

19

Figura 13: JML/JFSL Evaluator

3.3.7. Java Memory Graph

Cuando se analizan programas que incluyen estructuras de datos complejas y vinculadas, la vi-sualizacion del valor de cierta variable o expresion suele ser insuficiente. En esos casos, el programa-dor debe inspeccionar varias expresiones hasta poder entender como los objetos estan almacenadosen la memoria.

Para facilitar la tarea del programador, se desarrollo la vista Java Memory Graph que despliegaun grafo donde los nodos son objetos y los arcos son nombres de variables en un determinado puntode ejecucion. Los valores primitivos, como ser enteros o booleanos, son visualizados como atributosinternos de los objetos.

A medida que el usuario se mueve por la traza, un nuevo grafo es desplegado, como se muestraen la figura 14.

Figura 14: Java Memory Graph

3.3.8. TACO Editor

Por ultimo, se desarrollo un nuevo tipo de editor que permite la visualizacion de las interpre-taciones intermedias del programa Java: JML Simplificado, JDynAlloy y DynAlloy. Este nuevo

20

editor es conocido como TACO Editor e incluye distintas pestanas que muestran, luego de unanalisis, las distintas representaciones intermedias como se muestra en la figura 15 donde puedeverse el archivo Java original, mientras que en las figuras 16, 17 y 18 pueden verse (mas noeditarse) las representaciones en JML Simplificado, JDynAlloy y DynAlloy respectivamente.

Figura 15: TACO Editor visualizando codigo Java

Este editor sera util principalmente a usuarios avanzados de TACO que esten interesados enun analisis mas profundo de la verificacion realizada.

21

Figura 16: TACO Editor visualizando la version JML Simplificado

Figura 17: TACO Editor visualizando la version JDynAlloy

22

Figura 18: TACO Editor visualizando la version DynAlloy

23

4. Caso de estudio: BinomialHeap

Para ilustrar al usuario, consideremos el codigo fuente Java para extraer el mınimo elemento deun binomial heap. Los Binomial heaps [29] son una estructura recursiva disenada especıficamentepara implementar colas de prioridad. Por este motivo, una insercion eficiente y la posibilidad deborrar el elemento con menor clave, son caracterısticas distintivas de esta estructura de datos.

La figura 19 muestra un extracto de la clase BinomialHeap que implementa la estructura debinomial heap perteneciente a [30].

1 p u b l i c c l a s s Binomia lHeap {2 BinomialHeapNode Nodes ; // header3 . . .4 p u b l i c BinomialHeapNode ex t r a c tM in ( ) {5 i f ( Nodes == n u l l )6 r e t u r n n u l l ;7

8 BinomialHeapNode temp = Nodes , prevTemp = n u l l ;9 BinomialHeapNode minNode = n u l l ;

10

11 minNode = Nodes . f indMinNode ( ) ;12 wh i l e ( temp . key != minNode . key ) {13 prevTemp = temp ;14 temp = temp . s i b l i n g ;15 }16

17 i f ( prevTemp == n u l l )18 Nodes = temp . s i b l i n g ;19 e l s e20 prevTemp . s i b l i n g = temp . s i b l i n g ;21

22 temp = temp . c h i l d ;23 BinomialHeapNode fakeNode = temp ;24 wh i l e ( temp != n u l l ) {25 temp . pa r en t = n u l l ;26 temp = temp . s i b l i n g ;27 }28

29 i f ( ( Nodes != n u l l ) | | ( fakeNode != n u l l ) ) {30 i f ( ( Nodes == n u l l ) && ( fakeNode != n u l l ) ) {31 Nodes = fakeNode . r e v e r s e ( n u l l ) ;32 } e l s e i f ( ( Nodes == n u l l ) | | ( fakeNode != n u l l ) ) {33 unionNodes ( fakeNode . r e v e r s e ( n u l l ) ) ;34 }35 }36

37 r e t u r n minNode ;38 }39 }

Figura 19: Extracto de la clase BinomialHeap

Por otro lado, las figuras 20 y 21 muestran el invariante de la clase y la especificacion delmetodo extractMin respectivamente, escritos usando JFSL.

A diferencia de JML, las construcciones JFSL permiten al usuario escribir formulas en logicade primer orden utilizando operadores relacionales como ser la navegacion, union, disyuncion,clausura reflexo transitiva, etc..

24

1 @ I n v a r i a n t ( a l l n : BinomialHeapNode |2 ( n i n t h i s . Nodes . ∗ ( s i b l i n g @+ c h i l d ) @− n u l l =>3 ( ( n . pa r en t != n u l l => n . key >= n . pa r en t . key ) &&4 ( n . c h i l d != n u l l =>5 n ! i n n . c h i l d . ∗ ( s i b l i n g @+ c h i l d ) @− n u l l6 ) &&7 ( n . s i b l i n g != n u l l =>8 n ! i n n . s i b l i n g . ∗ ( s i b l i n g @+ c h i l d ) @− n u l l9 ) &&

10 ( ( n . c h i l d != n u l l && n . s i b l i n g != n u l l ) =>11 ( no m: BinomialHeapNode |12 ( m i n n . c h i l d . ∗ ( c h i l d @+ s i b l i n g ) @− n u l l &&13 m in n . s i b l i n g . ∗ ( c h i l d @+ s i b l i n g ) @− n u l l )14 )15 ) &&16 ( n . deg r ee >= 0 ) &&17 ( n . c h i l d=n u l l => n . deg r ee = 0 ) &&18 ( n . c h i l d != n u l l =>n . deg r ee=#(n . c h i l d .∗ s i b l i n g @− n u l l ) ) &&19 (20 #( ( n . c h i l d @+ n . c h i l d . c h i l d . ∗ ( c h i l d @+ s i b l i n g ) ) @− n u l l )21 =22 #( ( n . c h i l d @+ n . c h i l d . s i b l i n g . ∗ ( c h i l d @+ s i b l i n g ) ) @− n u l l )23 ) &&24 ( n . c h i l d != n u l l => (25 a l l m: BinomialHeapNode |26 ( m i n n . c h i l d .∗ s i b l i n g@−n u l l => m. pa r en t = n ) )27 ) &&28 (29 ( n . s i b l i n g != n u l l && n . pa r en t != n u l l ) =>30 ( n . deg r ee > n . s i b l i n g . deg r ee )31 )32 )33 )34 ) &&35 ( t h i s . s i z e = #( t h i s . Nodes . ∗ ( s i b l i n g @+ c h i l d ) @− n u l l ) ) &&36 ( a l l n : BinomialHeapNode | n i n t h i s . Nodes .∗ s i b l i n g @− n u l l =>37 ( ( n . s i b l i n g != n u l l => n . deg r ee < n . s i b l i n g . deg r ee ) &&38 ( n . pa r en t=n u l l ) )39 ) ;

Figura 20: Invariante de clase de BinomialHeap

1 @Mod i f i e s Ev e r y t h i n g2

3 @Ensures ( @old ( t h i s ) . @old ( Nodes)==n u l l => ( t h i s . Nodes==n u l l &&4 r e t u r n==n u l l ) )5 && ( @old ( t h i s ) . @old ( Nodes )!= n u l l => (6 ( r e t u r n i n @old ( t h i s . nodes ) ) &&7 ( a l l y : BinomialHeapNode |8 ( y i n @old ( t h i s . nodes . key ) => y . key >= r e t u r n . key )9 ) &&

10 ( t h i s . nodes=@old ( t h i s . nodes ) @− r e t u r n ) &&11 ( t h i s . nodes . key @+ r e t u r n . key = @old ( t h i s . nodes . key ) ) ) ) ;

Figura 21: Especificacion para el metodo extractMin escrita en JFSL

25

La anotacion @Ensures para el metodo extractMin establece que toda ejecucion del metodosobre un binomial heap no vacıo termina con otro binomial heap en el que:

el nodo de retorno fue removido,

la clave del nodo removido es menor o igual a cualquier otra clave almacenada, y

ninguna otra clave fue afectada.

4.1. Analizando con TACO

Con todos estos elementos, el usuario ya puede intentar la verificacion del programa. Como sedijo anteriormente, TACO requiere un scope de verificacion que para este caso se seteara en 5 itera-ciones para cada ciclo, una unica instancia de BinomialHeap y 13 instancias de BinomialHeapNode.Luego, como se reporto en [15], TACO responde que la verificacion no se mantiene para el scopeseleccionado.

Como se muestra en la figura 22, utilizando TACO desde la lınea de comandos, esta es launica informacion que se obtiene. Es posible activar la impresion en formato XML para estecontraejemplo pero esto no se incluye aquı por cuestiones de espacio.

En la siguiente seccion se presenta como se debuggea y localiza el error utilizando TacoPlug.

1 ∗∗∗∗∗∗ Stage D e s c r i p t i o n : Execu t i on o f a n a l y s i s . ∗∗∗∗∗∗2

3 00000001 S t a r t i n g A l l o y Ana l y z e r v i a command l i n e i n t e r f a c e4

5 ∗ I npu t spec f i l e : output / output . a l s6

7 00000037 Pa r s i ng and t yp e ch e ck i n g8

9 ∗ Command type : check10 ∗ Command l a b e l : e x amp l e s b i nh eap B inom i a lHeap ex t r a c tM in 011

12 00027140 T r a n s l a t i n g A l l o y to Kodkod13

14 ∗ So l v e r : m i n i s a t ( j n i )15 ∗ Bi t width : 516 ∗ Max sequence : 1517 ∗ Skolem depth : 018 ∗ Symmbreaking : 2019

20 00030060 T r a n s l a t i n g Kodkod to CNF21

22 ∗ Pr imary v a r s : 3246223 ∗ Tota l v a r s : 91843924 ∗ C l au s e s : 257445525

26 00084096 So l v i n g27

28 ∗ Outcome : SAT29 ∗ So l v i n g t ime : 11240930

31 00142121 An a l y s i s f i n i s h e d32

33 ∗∗∗∗∗ END: A l l o y Stage ∗∗∗∗∗∗

Figura 22: Output de TACO para extractMin

26

4.2. Analizando con TacoPlug

En esta seccion se comentara el proceso de debugging y localizacion de la falla reportada porTACO para el ejemplo de BinomialHeap.

El primer paso de este proceso fue la configuracion de TACO para su posterior ejecucion. Comoscope de analisis se utilizo el mismo que fue informado para la verificacion utilizando TACO enforma directa en la seccion anterior. En este caso, esta configuracion se realizo utilizando la vistacorrespondiente presentada en 3.3.1. Posterior a la configuracion se lanzo un analisis de tipo Checkutilizando el mecanismo presentado en 3.3.2.

Luego de la configuracion del plugin para la ejecucion y una vez ejecutado el analisis, seprocedio a analizar que parte del codigo desarrolado no se correspondio con la especificacion. Paraesto, el punto de partida fue la vista JML/JFSL Annotation Explorer la cual permite, como se hadicho anteriormente, identificar que formula de las constituyentes de la condicion de verificacion,fallo. Utilizando esta vista puede verse que el invariante de la clase se mantiene pero falla laposcondicion, como puede verse en la figura 23.

Figura 23: JML/JFSL Annotation Explorer luego del analisis de extractMin.

La primera lınea del cuadro muestra que la poscondicion del metodo no se mantiene mientrasque la segunda dice que el invariante es valido.

Como se marco con anterioridad, la poscondicion del metodo implica las siguientes condiciones:

el nodo de retorno fue removido,

la clave del nodo removido es menor o igual a cualquier otra clave almacenada, y

ninguna otra clave fue afectada.

Sabiendo que el problema esta en la poscondicion, debe detercarse cual de estas condicionesresulta invalida. Para esto resulta conveniente el uso de la vista Java Memory Graph y compararel estado inicial y el estado final del BinomialHeap. En la figura 24 se muestra el estado del heapal iniciar la ejecucion del metodo extractMin y en la figura 25 se muestra el estado del mismojusto antes de la instruccion de retorno.

En el estado inicial puede observarse que la estructura cumple con el invariante, lo que implicaque es un binomial heap valido, y que tiene 13 nodos. Aquı puede verse como se utilizan losparametros definidos como scope de TACO: existe una unica instancia de BinomialHeap y 13instancias de BinomialHeapNode.

Por otro lado, en el estado final, puede observarse que se extrajo un nodo del binomial heap(no es alcanzable por ninguna referencia de la estructura) y que ademas la clave es menor o iguala cualquier otra clave almacenada.

Sin embargo, si se comparan y contrastan los dos estados de la memoria, puede observarse queel binomial heap se encuentra afectado mas alla del nodo extraıdo: en el estado inicial existen 13nodos alcanzables y en el final solamente 10, es decir 2 menos de los que deberıa.

Este analisis permite establecer que es la tercer parte de la poscondicion la que no se cumpleal final la ejecucion del metodo y que el problema esta en que se pierden nodos del binomial heap.

27

Figura 24: Java Memory Graph inicial para extractMin

Figura 25: Java Memory Graph final para extractMin

28

Descubierta la discrepancia entre el codigo y la especificacion, el foco se pone en el objetivo dedescubrir el origen de la misma. La pregunta que cobra relevancia entonces es cual es el primerpunto de la ejecucion dada por la traza que contiene el error en el que en el heap solo existenmenos de 13 instancias de BinomialHeapNode.

Con el objetivo de localizar este punto de la traza, se utiliza la vista Java Error Trace quepermite desplazarse a lo largo de la ejecucion simbolica reportada por TACO. Realizando unabusqueda binaria sobre los elementos de la traza encontramos que previo al llamado al metodounionNodes, en la lınea 182, todavıa son referenciables 13 nodos en el heap como se muestra enla figura 26. Esto muestra que la falla debe estar contenida en el cuerpo del metodo unionNodes

y debe analizarse su desarrollo.

Figura 26: Estado del heap previo a la invocacion a unionNodes

Una vez en el cuerpo de unionNodes, descubrimos que luego de la ejecucion del metodo merge,en el heap solo existen 10 instancias de BinomialHeapNode, como muestra la figura 27, por lo quela falla debe encontrarse en dicho metodo.

Figura 27: Estado del heap previo a la invocacion a merge

Analizando el cuerpo del metodo merge nos encontramos con que no existen invocaciones aotros metodos incluidas en este, por lo que acotamos la falla al cuerpo de dicho metodo.

En este momento, resulta importante analizar el algoritmo que, intuitivamente, une dos bi-nomial heaps. A partir de este punto el analisis involucra un conocimiento profundo del codigo

29

ejecutado y una atencion especial al algoritmo implementado para unir dos binomial heaps. Elcodigo para este algoritmo se incluye en la figura 28

1 p r i v a t e vo i d merge ( /∗ @ n u l l a b l e @ ∗/BinomialHeapNode binHeap ) {2 BinomialHeapNode temp1 = Nodes , temp2 = binHeap ;3 wh i l e ( ( temp1 != n u l l ) && ( temp2 != n u l l ) ) {4 i f ( temp1 . deg r ee == temp2 . deg r ee ) {5 BinomialHeapNode tmp = temp2 ;6 temp2 = temp2 . s i b l i n g ;7 tmp . s i b l i n g = temp1 . s i b l i n g ;8 temp1 . s i b l i n g = tmp ;9 temp1 = tmp . s i b l i n g ;

10 } e l s e {11 i f ( temp1 . deg r ee < temp2 . deg r ee ) {12 i f ( ( temp1 . s i b l i n g == n u l l ) | |13 ( temp1 . s i b l i n g . deg r ee > temp2 . deg r ee ) ) {14

15 BinomialHeapNode tmp = temp2 ;16 temp2 = temp2 . s i b l i n g ;17 tmp . s i b l i n g = temp1 . s i b l i n g ;18 temp1 . s i b l i n g = tmp ;19 temp1 = tmp . s i b l i n g ;20 } e l s e {21 temp1 = temp1 . s i b l i n g ;22 }23 } e l s e {24 BinomialHeapNode tmp = temp1 ;25 temp1 = temp2 ;26 temp2 = temp2 . s i b l i n g ;27 temp1 . s i b l i n g = tmp ;28 i f ( tmp == Nodes ) {29 Nodes = temp1 ;30 }31 }32 }33 }34

35 i f ( temp1 == n u l l ) {36 temp1 = Nodes ;37 wh i l e ( temp1 . s i b l i n g != n u l l ) {38 temp1 = temp1 . s i b l i n g ;39 }40 temp1 . s i b l i n g = temp2 ;41 }42 }

Figura 28: Algoritmo de merge de dos BinomialHeap

A grandes rasgos, el algoritmo de merge une los dos binomial heaps analizando las raices de losmismos e iterando sobre los resultados parciales hasta conseguir un unico binomial heap. Para estose utilizan dos variables llamadas temp1 y temp2 donde se almacenan las cabezas de los binomialheaps parciales y se compara la variable degree (grado) de estas cabezas para determinar comose realiza el merge, diferenciando si los grados son iguales, si el grado de temp1 es menor o si elgrado de temp2 lo es. Para cada uno de estos casos se ejecutara un paso del algoritmo de merge

distinto.TacoPlug en este punto resulta util para recorrer cada uno de los pasos de la traza de ejecucion

y visualizar el estado de la memoria en estos pasos utilizando los componentes Java Error Trace y

30

Java Memory Graph. Esto permite entender como es la ejecucion de merge sobre un caso particulary encontrar el punto exacto donde empiezan a perderse nodos.

Recorriendo la traza se llega hasta el punto que puede visualizarse en la figura 29 en el quetodavıa son alcanzables 13 instancias de BinomialHeapNode.

Figura 29: Punto del algoritmo de merge previo a la falla

Como puede verse en la imagen capturada, las variables temp1 y temp2 apuntan a instanciasdistintas de BinomialHeapNode. Ademas puede observarse que el grado de la primera de las va-riables es menor que el de la segunda, lo cual determina que caso del algoritmo se ejecutara. Paraeste caso existen dos variantes. El primero requiere que la variable sibling de temp1 sea null oque el grado de dicha variable sea mayor que el grado de temp2. El segundo caso es simplemente lanegacion del primero y es el que ocurre en este ejemplo. Para este caso lo unico que se ejecuta esla asignacion de temp1 a su hermano directo. De esta forma la variable anteriormente referenciadapor temp1 y las que sean alcanzadas unicamente desde esta (en este caso el nodo hijo), marcadaspor el recuardo rojo en la figura 30, son perdidas. Es ası como se pierden referencia a 2 nodos delbinomial heap y se da una falla en el algoritmo de merge, generando una violacion en el analisisde TACO.

Figura 30: Nodos perdidos durante el algoritmo de merge

31

5. TacoPlug: Diseno y Arquitectura

En la presente seccion se presentara con mayor detalle el diseno y la arquitectura de TacoPlugen conjunto con las modificaciones realizadas sobre TACO.

Como se menciono anteriormente, el proyecto aquı presentado consistio de dos etapas: la pri-mera de modificacion de TACO para proveer las condiciones y funcionalidades necesarias para laconstruccion TacoPlug, y la construccion misma del plugin.

Mientras que en la subseccion 5.1 se comentara sobre el diseno de las modificaciones realizadassobre TACO, en la subseccion 5.2 se describira la arquitectura y diseno de TacoPlug.

5.1. Diseno y Arquitectura de contribuciones a TACO

El desarrollo del presente trabajo obligo a repensar algunos elementos de la arquitectura y di-seno de TACO. Al momento de comenzar, TACO funcionaba como una herramienta que procesabauna entrada y generaba un resultado como salida que decıa si se habıa detectado un error o no,pero no tenıa mayor interaccion con el usuario que la necesaria para inicializar el analisis. Esto, sibien no explıcitamente, puede visualizarse en la figura 5. Cuando se empezo a pensar en aumentarla usabilidad de esta herramienta fue evidente que esta concepcion de TACO ya no servıa. Esto sedebe a que TACO dejarıa de ser una herramienta de procesamiento lineal y pasarıa a ser una con lacual el usuario tiene interaccion principalmente para analizar el resultado obtenido. Por otro lado,para poder analizar este resultado y averiguar distintas caracterısticas del mismo, es necesario,ademas de guardar el resultado, y debido al diseno de TACO, guardar informacion sobre como sedieron las etapas intermedias y como se transformo el codigo fuente que sirvio como entrada parael analisis. Todo esto obligo a repensar la arquitectura de TACO. Las principales contribucionesa TACO se esquematizan en la figura 31.

Figura 31: Diagrama de la nueva arquitectura de TACO

32

En este esquema cada uno de los elementos circulares representa un artefacto, mientras quelos rectangulares representan comoponentes. Cada una de estas contribuciones seran explicadasen las siguientes subsecciones, pero valen algunas aclaraciones preliminares que involucran a todoslas tecnicas y mecanismos aquı presentados.

En primer lugar, como se menciono anteriormente, se pretende que el usuario no requieraconocer la estructura interna de TACO o la existencia de lenguajes intermedios. Es por esto quetoda informacion que ingrese el usuario debe poder ingresarla en alguno de los lenguajes quemaneja: Java, JML o JFSL. Por otro lado, el contraejemplo obtenido se encuentra en lenguajeAlloy y por el mecanismo desarrollado en [26] es posible evaluarlo desde el mundo DynAlloy. Estoimplica que el input del usuario debe ser transformado hasta DynAlloy siguiendo las mismas reglassimplificacion, renombre de variables y traducciones que se utilizaron para el analisis del programaoriginal. Por este motivo se decidio por la inclusion de contextos de traduccion en cada una delas etapas involucradas. Estos contextos de traduccion se implementaron como extensiones de laclase TranslationContext y existe uno por cada etapa:

JavaToSimpleJmlTranslationContext para la traduccion de Java anotado a JML Sim-plificado.

SimpleJmlToJDynAlloyTranslationContext para la traduccion de JML Simplificado aJDynAlloy.

JDynAlloyToDynAlloyTranslationContext para la traduccion de JDynAlloy a DynA-lloy.

DynAlloyToAlloyTranslationContext para la traduccion de DynAlloy a Alloy.

Estos contextos guardan informacion pertinente a cada transformacion. En la figura 32 seincluye un diagrama de clases de los mismos. El desarrollo de estos contextos incluyo, claramen-te, la modificacion de las etapas correspondientes para que la informacion correspondiente fueraalmacenada en los mismos.

Figura 32: Jerarquıa de clases para TranslationContext

Como se menciono, la informacion de estos contextos debe trascender la ejecucion del pipelinede transformacion de TACO y su etapa de verificacion, por lo que se creo un objeto cuyo objetivoes guardar los distintos contextos de traduccion involucrados en el pipeline. Este objeto recibe elnombre de TacoContext y, ademas de guardar los contextos ya mencionados, guarda una copiade las clases originales y el contraejemplo Alloy encontrado durante la verificacion.

Estos contextos de traduccion pueden visualizarse en la figura 31 en la parte superior de laimagen.

33

En segundo lugar, como se explico en el capıtulo 2, la arquitectura y diseno de TACO estanfuertemente determinadas por el pipeline de TACO. A grandes rasgos, existe una etapa por traduc-cion del pipeline. Tambien existen etapas adicionales, generalmente asociadas a posprocesamientodel resultado encontrado, como la mencionada JUnitStage. Siguiendo esta lınea, se diseno unanueva etapa implementada como una stage, que recibe el nombre de JavaCounterexampleStage.El objetivo de esta etapa es la construccion de un contraejemplo que pueda ser entendido por unusuario inexperto de TACO (es decir, el contraejemplo manejara elementos del mundo Java) apartir del contraejemplo a nivel Alloy.

Esta etapa generara como salida un objeto que encapsulara diversa informacion util al usuarioa la hora de localizar una falla, como ser: traza Java del error detectado y validez de los predica-dos (invariantes y poscondiciones) involucrados. Ademas contara con las capacidades de evaluarexpresiones arbitrarias ingresadas por el usuario y de generar un grafo con el estado de la memoriaen un punto de la ejecucion. Este objeto, al tratarse de un contraejemplo a nivel Java, recibe elnombre de JavaCounterExample y tambien es almacenado en el TacoContext. En la figura 33 seincluye un diagrama del clases para este objeto.

Figura 33: Diagrama de clases para JavaCounterExample

La nueva stage disenada puede verse en la parte intermedia de la figura 31, como un cuadrocon el texto Construccion del contraejemplo Java . De este recuadro se desprende, a modo deresultado, un recuadro punteado que representa al objeto JavaCounterExample y que tiene comosubitems a los distintos resultados parciales generados por la etapa, traza Java (con la etiqueta TJ),validacion de predicados (con el etiqueta VP), en conjunto con las funcionalidades que involucraninteraccion con el usuario: evaluacion de expresiones (con la etiqueta EE) y visualizacion globalde la memoria (con la etiqueta VM). Cada uno de estos puntos es desarrollado en una de lassiguientes subsecciones con mayor detalle.

5.1.1. Trazabilidad Java

Como se comento en 3.2, para la recuperacion de la traza que genera una falla se utilizo unmecanismo desarrollado en [26] que permite su reconstruccion a nivel DynAlloy y se incorporo alpipeline de TACO el traslado de una referencia al archivo original con el objetivo de aumentarel nivel de abstraccion de dicha traza DynAlloy hasta llegar a algo legible por el usuario, comoser codigo Java. Ademas de esto, se modificaron las clases que imprimen las representaciones delarchivo original en estos lenguajes intermedios y se modifico el parser de DynAlloy para que parseeun final, opcional, de instruccion que se incorporo a todas las instrucciones DynAlloy siguiendo elsiguiente esquema:

expresion dyn alloy JTOKEN className lineNumber columnNumber

donde expresion dyn alloy representa una expresion DynAlloy, JTOKEN es una nueva palabrareservada para indicar que esa instruccion contiene un token de referencia compuesto por class-

34

Name, lineNumber y columnNumber que representan el nombre de la clase, el numero de lınea yel numero de columna, respectivamente.

Para la reconstruccion de la traza a nivel Java se utilizo la traza a nivel DynAlloy y la in-formacion del token reference agregado. De esta forma, utilizando la clase JavaTraceBuilder, seconstruye la traza a nivel Java representada por el objeto JavaTrace que luego es guardado comouna propiedad de JavaCounterExample.

5.1.2. Evaluacion de expresiones JML/JFSL

Para este desarrollo se utilizo tambien un mecanismo desarrollado en [26] que permite la eva-luacion de expresiones Alloy en distintos puntos de la traza DynAlloy retornando como resultadoobjetos Alloy.

Por lo tanto, agregar la evaluacion de expresiones JML y JFSL requirio de varios etapas quese enumeran a continuacion:

1. Parseo de expresiones JML y JFSL.

2. Reconstruccion de expresiones utilizando los renombres de variables correspondientes.

3. Transformacion de expresiones JML y JFSL en expresiones DynAlloy.

4. Evaluacion de expresiones utilizando el evaluador DynAlloy.

5. Construccion de resultados generando objetos Java.

Algunas de estas etapas se resolvieron utilizando mecanismos ya existentes en TACO o algunasde sus dependencias. Por ejempo, para el parseo de expresiones se utilizaron clases presentes enlas correspondientes dependencias y para la transformacion de expresiones JML en expresionesAlloy se utilizo una visitor ya existente en TACO bajo el nombre de JmlExpressionVisitor.

Para el punto 2, la reconstruccion de expresiones utilizando los renombres correspondientes delas variables, se utilizaron los contextos de traduccion correspondientes y se desarrollo un visitorque clona las expresiones JML/JFSL renombrando las variables segun corresponde. Este visitorse encuentra implementado en la clase JPredicateSimplifierMutator.

Los dos pasos restantes de la evaluacion requirieron un poco mas de trabajo y por eso seexplican en las siguientes secciones.

La evaluacion propiamente dicha de expresiones Alloy depende de un mecanismo disenadoen [26] que evalua este tipo de expresiones. Sin embargo, este mecanismo no tiene en cuentaalgunas consideraciones que deben tenerse cuando es el usuario quien decide que se evalua en unpunto determinado: la ausencia de atomos para representar algunas variables en algunos puntos dela traza y el uso del mecanismo de ruptura de simetrıas presente en TACO. Estas consideracionesseran explicadas a continuacion.

Finalmente se detallara el proceso de construccion de resultados Java a partir de resultadosAlloy.

Ausencia de variables

El primer problema que debio atacarse fue el problema de la ausencia de variables. Como semenciono anteriormente, el problema de SAT-Solving pertenece a la clase de problemas conocidacomo NP-Completos, lo que significa que el tiempo que demanda su resolucion puede ser expo-nencial con respecto al tamano de la entrada, es decir la cantidad de variables presentes. Por lotanto, minimizar el tamano de la entrada es un objetivo importante en el desarrollo de TACO.Para esto, variables que no son necesarias para determinado analisis, no se traducen a Alloy. Porejemplo, si un metodo bajo analisis no realiza ninguna operacion sobre una variable miembro dela clase a la cual pertenece, esa variable no existira en el contexto del analisis.

Por otro lado, en Alloy, al valor de una variable en cada punto de la ejecucion se lo conoce comoencarnacion. De esta forma, evaluar una variable en un punto de la ejecucion implica evaluar una

35

encarnacion. Sin embargo, por lo mencionado anteriormente, algunas variables pueden no estarencarnadas para determinado nivel de la ejecucion aunque siempre se encuentran en el nivel masalto. Por ejemplo, aunque una variable no exista en un metodo, existira en el metodo llamador.

Por lo tanto, para resolver el problema de la ausencia de variables debe encontrarse el puntoanterior de ejecucion donde la variable sı se encuentre definida, es decir, este encarnada. Para esto,se recorre el arbol de ejecucion hacia atras, partiendo del punto donde se esta evaluando, hastaencontrar el primer lugar donde la variable se encuentre encarnada. El valor de la encarnacion,sera el valor de la variable en el punto de ejecucion seleccionado.

Para la resolucion de este problema se desarrollo un visitor que, dado un punto de la trazaJava y una expresion Alloy, devuelve una expresion encarnada segun la visibilidad de las variablesque intervienen. Este visitor esta implementado en la clase JavaIncarnatorMutator.

Adicionalmente, la evaluacion de expresiones Alloy en distintos puntos de la traza Java seencapsulo en el componente conocido como JavaEvaluator.

Manejando la ruptura de simetrıas

En segundo lugar, cuando se utiliza un mecanismo disponible en TACO conocido como rup-tura de simetrıas (SBP por sus siglas en ingles que representan Symmetry Breaking Predicate),una variable Java puede encontrarse representada por mas de un atomo Alloy en el estado inicialde la ejecucion simbolica. Por lo tanto, para evaluar expresiones que contengan alguna de estasvariables, debe saberse si la variable se encuentra partida o no. Esta informacion se almacena en laclase JDynAlloyClassHierarchy a la que se debe consultar antes de encarnar una expresion Alloy.La instancia utilizada para ruptura de simetrias (en caso de estar habilitada), se almacena comoparte del contexto de traduccion DynAlloy-Alloy. De esta forma, siguiendo el esquema comentadoanteriormente, se incorporo al mecanismo de encarnacion un chequeo que analiza si la variable seencuentra partida y en tal caso realiza las modificaciones necesarias para que la encarnacion secomplete de forma correcta.

Construccion de resultados Java a partir de resultados Alloy

En este punto, dos elementos debieron tenerse en cuenta: la construccion de objetos Java y laposible presencia de aliasing.

Para la resolucion del primer problema se diseno e implemento una clase que, dado un resultadoAlloy, lo traduce a Java utilizando reflection. AlloyEvaluationResultInstantiator es el nombrede dicha clase. El proceso de reconstruccion de una variable Java a partir de un atomo Alloydepende del tipo de atomo. Existen tres tipo de resultados posibles luego de la evaluacion de unaexpresion Alloy, ademas de null:

Integer

Boolean

A4TupleSet con aridad unaria o binaria.

Los dos primeros casos son los tipos basicos de Java y no requieren mayor analisis puesto que sondevueltos automaticamente. El tercero de estos valores, A4TupleSet, representa tipos complejos,como podrıan ser List, Set, Map, Exception o tipos particulares de cada analisis definidos porel usuario. Intuitivamente un objeto de A4TupleSet puede ser pensado como una tupla, unaria obinaria.

La tarea de construir un objeto Java a partir de uno Alloy de tipo A4TupleSet no es trivial.El primer paso para esta construccion es la inferencia del tipo Java del resultado. Esto se lograaccediendo a un atomo particular de la tupla: el unico presente en el caso de tuplas unarias yel segundo para tuplas binarias. Este atomo contendra la informacion necesaria para conocer eltipo Java del resultado. El valor de este atomo siempre es de tipo String y es apartir de este

36

string que se conoce el tipo del resultado. Por ejemplo, el siguiente podrıa ser el atomo con lainformacion de tipo del A4TupleSet que se obtiene luego de evaluar la variable this en el ejemplode la seccion 1.1:

{AssertExample$0}

Este string puede interpretarse de la siguiente forma. Siendo el sımbolo $ un delimitador, elprefijo representa el nombre calificado del tipo del resultado Java y el sufijo es el id de ese objetoen particular (similar a un object id en Java). Simplemente extrayendo el prefijo se conoce el tipodel resultado en el mundo Java.

Una vez obtenido el tipo del resultado se procede a instanciar una variable de esta clase,utilizando reflection. Utilizando tambien este mecanismo brindado por Java, se conocen los campospresentes en un objeto de este tipo y se procede a construir una expresion Alloy que, luego deser evaluada, recorrera este mismo proceso hasta obtener un resultado en el mundo Java quesera asignado al campo en cuestion.

Por otro lado, para resolver el problema de aliasing, cuando se instancia un objeto, se guardaen un diccionario el id del objeto Alloy del cual provino en conjunto con el objeto instanciado. Deesta forma, la siguiente vez que se intente instanciar el objeto Alloy, se consultara el diccionario y,de encontrarse el id del objeto Alloy, se devolvera el objeto ya construido, resolviendo el problemadel aliasing. Este problema esta resuelto en la misma clase anteriormente mencionada.

Una esquematizacion del proceso de instanciacion de variables puede verse en la figura 34.En este esquema, los recuadros representan componentes, mientras que los circulos representanartefactos.

Figura 34: Esquema instanciacion resultados Alloy

Finalmente cabe aclarar que para que la instanciacion de variables utilizando el mecanismoaquı descripto funcione, es necesario que las clases compiladas se encuentren disponibles al systemclass loader. Esto se resuelve mediante un artilugio de bajo nivel implementado a nivel de pluginal momento de ejecutar un analisis. Se comentara sobre este tema mas adelante.

5.1.3. Validacion de predicados

Como se explico en la seccion correspondiente, es util saber cual de las formulas que componenla VC no pudo ser satisfecha. Para esto se diseno y desarrollo un mecanismo que determinaque parte de la especificacion JML/JFSL no pudo verificarse.

El componente que determina si una formula de la especificacion es correcta o no, funcionadistinto dependiendo del lenguaje en el que se encuentre escrita la misma:

JML. Para especificaciones escritas en JML, se guarda un diccionario como parte del contex-to de traduccion de Java a JML Simplificado que mapea las formulas JML a formulas Alloy.De esta forma, para saber si una formula de la especificacion es valida, alcanza con consultar

37

el diccionario para obtener la fomula Alloy correspondiente y evaluar dicha formula utilizandoel mecanismo anteriormente desarrollado. Sin embargo, la evaluacion de formulas Alloy no esdirecta. Para esto se desarrollo un visitor bajo el nombre AlloyFormulaEvaluatorVisitor

que descompone la formula, evalua los predicados que la componen y recomponen el valor deverdad de la formula basandose en los resultados de los predicados evaluados y la estructurade la formula.

JFSL. Para especificaciones escritas utilizando JFSL se utiliza un diagrama de evaluaciondirecto ya que las formulas JFSL ya se encuentran escritas en lenguaje Alloy. La evaluacionde estas formulas presenta el mismo problema que la evaluacion de formulas Alloy traducidasdesde JML por lo que se utiliza el mismo visitor para su evaluacion.

5.1.4. Visualizacion global de la memoria

Finalmente, el mecanismo de evaluacion de expresiones JML/JFSL permitira a TACO contarcon un componente capaz de generar un grafo con el estado del heap en el punto de la traza que elusuario haya seleccionado, permitiendole obtener una visualizacion clara del estado de la memoria.El proceso de construccion de este grafo implica dos etapas.

La primer etapa tiene como objetivo el construir un diccionario con un mapeo entre todaslas variables involucradas en un determinado punto del programa y sus valores. Esta etapa seencuentra implementada en la clase JavaSnapshotBuilder que, dado un TacoContext y un puntode la traza Java, retorna una instancia de la clase JavaSnapshot que contiene el diccionariobuscado. Para esto evalua, utilizando el mecanismo de evaluacion de expresiones anteriormentedescripto, la variable this, las variables locales y los parametros del metodo al cual pertenece elpunto de ejecucion.

La segunda etapa de la construccion del grafo parte del resultado obtenido en la etapa anterior.La clase JavaSnapshot contiene un metodo que devuelve una representacion de la informacion enformato de grafo modelado por la clase JavaSnapshotGraph.

5.2. Diseno y Arquitectura de TacoPlug

Como se comento anteriormente, para el desarrollo de TacoPlug se utilizo la infraestructuraprovista por Eclipse, Plugin Development Environment (PDE) [27]. Este entorno de desarrollode plugins provee herramientas para crear, desarrollar, testear, debuggear, construir y deployarplugins para Eclipse. PDE no esta incluido en la version basica de Eclipse sino que debe bajarsecomo un plugin mismo.

El primer paso en el construccion de TacoPlug fue la creacion de un proyecto de Eclipse bajo eltemplate Plug-in Project provisto por PDE sobre el que se disenaron y desarrollaron las distintasvistas en el mismo orden en el que fueron presentadas en la seccion 3, con la excepcion de la nuevaperspectiva que fue desarrollada hacia el final del proyecto.

En PDE, los distintos componentes que uno crea se conocen como Extensions y generalmenteextienden un Extension Point. En las siguientes subsecciones se comentara como fue construidocada extension y que extension point sirvio de base.

Adicionalmente, deben definirse los plugins de los cuales depende el plugin que se esta desa-rrollando. Generalmente se agregan distintos plugins que contienen los extension points que sevan a extender, pero pueden agregarse otros que brinden funcionalidades para la construccion deextensiones pero que no sirvan como base (un ejemplo de esto se vera en 5.2.6)

Finalmente, aunque no forma parte de la arquitectura de TacoPlug, existe una herramienta queresulto muy util al momento de desarrollar este plugin. Esta herramienta se llama PDE IncubatorSpy [31] y permite la introspeccion de Eclipse en terminos de lo que a un desarrollador de pluginsle resulta util. La combinacion de teclas ALT+SHIFT+F1 abre el Spy y presenta al usuarioinformacion relevante a donde se haye el foco. En la figura 35 puede verse esta herramienta cuandose la aplica sobre la ventana de problemas de compilacion provista por Eclipse.

38

Figura 35: PDE Incubator Spy para la vista de problemas de compilacion de Eclipse

5.2.1. TACO Preferences

Esta pantalla, que permite la configuracion de TACO, utiliza el punto de extension org.

eclipse.ui.preferencePages y esta compuesta por 3 componentes que se encuentran en elpaquete tacoplugin.preferences:

PreferenceConstants: implementado por la clase PreferenceConstants, contiene los iden-tificadores de las distintas variables de configuracion.

PreferenceInitializer: implementado en la clase PreferenceInitializer, contiene la ini-cializacion de las distintas variables de configuracion. Esta clase extiende a la clase de nombreAbstractPreferenceInitializer provista por PDE.

PreferencePage: implementado en la clase TacoPreferencePage, que extiende a la claseFieldEditorPreferencePage provista por PDE. Contiene la construccion de la vista pro-piamente dicha y es donde se define que componentes son utilizados para la configuracionde los distintos parametros, el tipo de datos permitido para cada uno, etc. Por ejmplo, paraparametros booleanos puede utilizarse un checkbox, para campos donde se requiere que elusuario ingrese informacion puede definirse si se aceptan valores numericos o no, etc. Enesta clase tambien se detalla la descripcion de cada parametro para que el usuario entiendaque es lo que configura.

5.2.2. TACO Launcher

Para la construccion de esta pantalla, que permite la ejecucion de analisis TACO, se utilizarondiversos extension points segun se explica a continuacion. Las clases que componen esta extensionestan contenidas en el paquete tacoplugin.launcher.

39

En primer lugar, se extendio org.eclipse.debug.ui.launchConfigurationTabs para la cons-truccion de una clase que permite definir la pantalla de configuracion de parametros propios delanalisis que se va a realizar. El nombre de esta clase es TacoLaunchConfigurationTab y desdeaquı se definen las distintas partes que compondran esta vista, los parametros que deben definirse,como se inicializan, etc.

En segundo lugar, toda extension de org.eclipse.debug.ui.launchConfigurationTabs de-be ser incluıda en un TabGroup para poder ser utilizada. Por este motivo, se extendio org.eclipse.debug.ui.launchConfigurationTabGroups y se incluyo la pantalla anterior en este grupo.

Finalmente, debio definirse la propia ejecucion. Es decir, que es lo que se ejecuta una vez que elusuario configuro los parametros e hizo click en Run. Para esto se extendio org.eclipse.debug.

core.launchConfigurationTypes con la clase TacoLauncher que es la que finalmente recuperalas preferencias globales, los parametros recien definidos sobre el analisis y ejecuta TACO. Adi-cionalmente, luego de la ejecucion de TACO, dependiendo del resultado, actualiza las distintaspantallas del plugin.

Por otra parte, al momento de ejecutar un analisis TACO se ejecutan ciertos procesos quecalculan automaticamente algunos parametros de TACO como se menciono en 3.3.2. Desde elpunto de vista implementativo, los procesos que tienen particular interes son los de calculo declases relevantes y la modificacion del class loader.

Para el calculo de clases relevantes se aprovecho un mecanismo provisto por Eclipse desde laclase org.eclipse.jdt.internal.corext.callhierarchy.CallHierarchy y se lo utilizo paradesarrollar un analisis que, dado el metodo que se desea verificar, computa las clases relevantes.De esta forma, se agregan como clases relevantes:

Clases utilizadas en el metodo a analizar.

Clases relevantes de los metodos invocados desde el metodo a analizar.

Esto implica que los archivos fuente de las clases relevantes estaran disponibles para ser utili-zados durante el analisis realizado por TACO.

Por otro lado, y aunque no se trate de un parametro, es importante mencionar que el conjuntode clases relevantes tambien deben encontrarse disponibles para el class loader de la JVM en laque corra TACO. Esto es necesario porque al momento de evaluar expresiones puede ser necesarioinstanciar objetos pertenecientes a una clase relevante o a la misma clase bajo analisis. Si estasclases no estuviesen disponibles para el class loader, se obtendrıa una excepcion al momento deinstanciarlas.

Agregar estas clases al class loader no es una tarea facil y requiere un poco de manejo debajo nivel de Java. Esto se logro mediante el uso de reflection, agregando el directorio de outputdel proyecto (es decir, donde se almacenan las clases compiladas) a los directorios visible al classloader. De esta forma, cualquier clase compilada en el proyecto analizado se encuentra disponiblepara ser instanciada.

5.2.3. JML/JFSL Annotation Explorer

En la construccion de esta pantalla se utilizo un mecanismo bien conocido por usuarios deEclipse: markers. Para esto se creo un identificador nuevo de tipos de markers, implementadocomo variable de la clase enumerada TacoMarker del paquete tacoplugin.markers.

Adicionalmente se creo una vista, utilizando los extension points org.eclipse.ui.views yorg.eclipse.ui.ide.markerSupport, implementada por la clase TacoPredicateValidityView

que, extendiendo la vista MarkerSupportView provista por PDE, muestra los markers del tipo conel que se la configure.

Este mecanismo, simple pero efectivo, permite al usuario hacer doble click sobre los markers ylograr que el foco del cursor se situe sobre el predicado correspondiente en el codigo fuente.

40

5.2.4. Java Error Trace

Esta extension utiliza como extension point a org.eclipse.ui.views en conjunto con algunoscomponentes provistos por PDE. Las clases que componen esta vista estan contenidas en el paquetetacoplugin.views.javaTrace, siendo la principal JavaTraceView.

Dicha clase utiliza un componente provisto por JFace [32], framework que provee clases yelementos para el desarrollo de interfaces graficas incluido en PDE, llamado TreeViewer que,dados:

Un proveedor de contenido

Un etiquetador

Un ordenador

dibuja un arbol con dicha informacion. Estos elementos son provistos por las clases de nombreJavaTraceViewerContentProvider, JavaTraceViewLabelProvider y JavaTraceViewerSorter

respectivamente, que extendiendo determinadas clases y definiendo algunos metodos definidoscomo abstractos, proveen la funcionalidad necesaria para construir el arbol que muestra la trazadel contraejemplo encontrado por TACO.

5.2.5. JML/JFSL Evaluator

Esta vista es similar a Java Error Trace en el sentido de que tambien es una extension deorg.eclipse.ui.views y que tambien utiliza componentes de JFace.

Sin embargo, a diferencia de la descripta anteriormente, la extension JML/JFSL Evaluatorno utiliza un TreeViewer, sino que hace uso de los componentes TableViewer y TextViewer. Elprimero de estos componentes tiene como objetivo mostrar el listado de expresiones JML/JFSLque se definieron para ser evaluadas, mientras que el objetivo del segundo es mostrar el resultadode la evaluacion de las mismas.

Esta extension esta construida en el paquete tacoplugin.views.jmlEvaluation siendo laprincipal clase JmlExpressionEvaluationView.

De la misma forma que el TreeViewer, un TableViewer requiere de:

Un proveedor de contenido

Un etiquetador

que son provistos por las clases de nombre JmlExpressionEvaluationViewerContentProvidery JmlExpressionEvaluationViewerLabelProvider respectivamente.

5.2.6. Java Memory Graph

Este componente es otro de los construidos sobre la extension org.eclipse.ui.views. Aun-que, a diferencia de los dos anteriores, cuenta con la particularidad de que esta basado integramenteen el plugin Zest [33]. Como se menciono anteriormente, Zest es un plugin que provee un conjun-to de componentes para visualizacion en Eclipse. Esta librerıa esta desarrollada completamenteutilizando SWT/Draw2D.

Para poder utilizar este plugin se debio, ademas de instalarlo, agregarlo como dependenciaal archivo plugin.xml y configurar el launcher de Eclipse para que lo cargue cuando se ejecuteTacoPlug. En un esquema productivo de TacoPlug, es decir, cuando se lo instale en una versionlimpia de Eclipse como cualquier plugin, solamente sera necesario instalar Zest como dependencia.

Con Zest disponible para ser utilizado desde TacoPlug, se construyo esta extension en el paquetetacoplugin.views.heap donde la principal clase es JavaHeapView. Esta clase utiliza Zest paraconstruir un GraphViewer que, dados:

Un proveedor de contenido

41

Un etiquetador

dibuja un grafo con la informacion y estilo configurado. El proveedor de contenido esta dadopor JavaHeapViewerContentProvider mientras que el etiquetador queda descripto por la claseJavaHeapViewerLabelProvider.

5.2.7. TACO Editor

El desarrollo de esta extension esta basado en el extension point org.eclipse.ui.editors. El com-ponente se encuentra compuesto por las clases incluidas en el paquete tacoplugin.editors siendola principal clase que lo compone TacoEditor.

La clase TacoEditor extiende a la clase MultiPageEditorPart, provista por PDE, que permitela construccion de editores con multiples paginas. Se definieron la siguientes variables de instanciade esta clase:

CompilationUnitEditor javaEditor

CompilationUnitEditor simpleJmlVisualizer

TextEditor jDynAlloyVisualizer

TextEditor dynAlloyVisualizer

Como puede imaginarse, cada una de estas variables representa los editores de Java, JML Sim-plificado, JDynAlloy y DynAlloy respectivamente. Para el editor de Java se utilizo el mismo editorutilizado por Eclipse, lo que automaticamente brinda syntax highlighting y todas las funcionalida-des provistas por el mismo. Para el visualizador de JML Simplificado tambien se utilizo este editorpero se le desactivo la posibilidad de modificar el contenido. Los visualizadores de JDynAlloy yDynAlloy son simples editores de texto con la capacidad de edicion desactivada (ver 7).

5.2.8. TACO Perspective

Esta extension fue construida solo con objetivos de usabilidad ya que no agrega funcionalidada lo ya presentado pero sı lo organiza para comodidad del usuario. Esta basada en los extensionpoints org.eclipse.ui.perspectives y org.eclipse.ui.perspectiveExtensions y su claseconstituyente es TacoPerspective en el paquete tacoplugin.perspectives. En este clase sedefine que vistas forman parte de la perspectiva y donde se las posiciona.

5.3. Integracion TacoPlug-TACO

En primer lugar, para poder interactuar con TACO fue necesario agregar este proyecto (y susdependencias) al classpath del proyecto TacoPlug. A diferencia de los proyectos Java, para estetipo de proyectos no es posible agregar como referencia otros proyectos salvo que sean del mismotipo, es decir plugins para Eclipse. Es por esto que para agregar TACO al classpath fue necesarioexportar el jar y guardarlo en la carpeta lib del nuevo proyecto. Lo mismo debio hacerse con losproyectos jdynalloy y dynalloy4.

En la figura 36 se incluye un diagrama de la interaccion entre TacoPlug y TACO a partir delcual se explicara la integracion entre TACO y TacoPlug.

Como se puede ver en este diagrama, la interaccion comienza cuando el usuario inicia unanalisis a traves de la vista TacoLauncher cuya primera tarea es configurar el contexto en el cual seejecutara el analisis. Para esto recupera las preferencias globales seteadas por el usuario a traves deTacoConfigurationBuilder y utilizando TacoPreferences, calcula el conjunto de clases relevantespor medio del componente RelevantClassAnalysis (y las agrega al class loader), obtiene eldirectorio donde se encuentra el codigo fuente y finalmente ejecuta el analisis propiamente dicho,punto en el cual ya se utiliza TACO exclusivamente.

42

Figura 36: Diagrama de interaccion entre TacoPlug y TACO

Una vez concluido el analisis, TACO retorna el contexto de traduccion (que contiene el con-traejemplo Java), que es almacenado para futuras interacciones del usuario. Asimismo tambien seactualizan las vistas que permiten la visualizacion de la validez de los predicados pertenecientes ala VC y actualiza el compoente que permite la visualizacion de la traza Java.

A partir de este punto, como siga la interaccion entre TACO y TacoPlug depende del usuario,pero en cualquier caso, el punto de entrada va a ser el contraejemplo Java reportado y almacenadocomo parte del contexto de traduccion obtenido durante el analisis. Este interaccion se da, pri-mordialmente, cuando el usuario selecciona un punto de la traza. Es ese momento, por un lado esposible evaluar expresiones JML/JFSL, y por el otro, se dispara automaticamente el mecanismoque computa el estado del heap en el punto seleccionado. A continuacion se incluyen diagramasde interaccion entre TacoPlug y TACO para estos mecanismos.

En la figura 37 se muestra la interaccion entre el usuario, TacoPlug y TACO necesaria parapoder evaluar una expresion.

Como se puede apreciar en este diagrama, el primer paso es la seleccion de un punto de latraza Java. Esta seleccion se da a traves de la vista Java Error Trace y contextualiza la evalua-cion que se realizara en ese punto de la traza. El siguiente paso es, utilizando la visa JML/JFSLEvaluator, ingresar una expresion a ser evaluada. Una vez ingresada la expresion, se dispara unmecanismo que, a traves del contraejemplo Java presente en la instancia de TacoContext obtenidacomo resultado del analisis realizado, permitira el parseo, traduccion, encarnacion, evaluacion einstanciacion del resultado segun el mecanismo descripto en 5.1.2. Una vez completada esta eva-luacion, se mostrara al usuario el toString del resultado.

43

Figura 37: Diagrama de interaccion para la evaluacion de una expresion

Por otro lado, en la figura 38 se muestra la interaccion entre el usuario, TacoPlug y TACOpara la construccion del grafo con la visualizacion global del estado de la memoria.

Figura 38: Diagrama de interaccion para la construccion del grafo con el estado de la memoria

En este diagrama se muestra como, luego de la seleccion de un punto de la traza de la mismaforma que se hace para la evaluacion de expresiones, se construye el grafo respresentativo delestado de la memoria para ese punto segun el mecanismo descripto en 5.1.4. A diferencia delmecanismo antes descripto, la construccion del grafo no requiere mayor interaccion de parte delusuario, sino que su construccion es disparada automaticamente. La construccion del grafo sedispara a traves del contraejemplo Java presente en la instancia de TacoContext obtenida comoresultado del analisis realizado. Como resultado de esta ejecucion, se genera un objeto de la claseJavaSnapshot que, utilizando un metodo llamado asGraph, devuelve la informacion contenida enformato de grafo. Este grafo es luego tomado por Java Memory Graph para ser visualizado por elusuario.

44

6. Conclusiones

Durante la realizacion del presente trabajo se disenaron y desarrollaron diversas tecnicas quepermiten un mejor analisis de un contraejemplo reportado por TACO luego de la verificacion deun programa. Asimismo se desarrollo un plugin para Eclipse que permite la integracion de TACOa dicha IDE facilitando la utilizacion de TACO y ampliando su audiencia a un publico no experi-mentado en herramientas de verificacion acotada.

Desde el punto de vista de la herramienta TACO se presento una tecnica para reconstruir latraza a nivel Java que resulta en la violacion de la especificacion reportada. Adicionalmente seexhibio un mecanismo que permite la evaluacion de expresiones JML/JFSL en distintos puntos dela traza. Este mecanismo permitio, en primer lugar, el diseno y construccion de un modulo capazde reconstruir el estado del heap en cualquier punto de la ejecucion simbolica. En segundo lugar,posibilito la evaluacion del invariante de clase y la postcondicion del metodo en el estado final dela ejecucion, lo cual permite acotar la violacion a una sola formula en el mejor caso.

Por otro lado, desde el punto de vista del plugin, se introdujeron distintos componentes mo-delados como vistas de Eclipse que permiten la utilizacion de TACO de una forma mucho masamigable. En primer lugar se integro la posibilidad de ejecutar analisis desde Eclipse permitiendola configuracion de casi todos los parametros existentes en TACO. Los parametros que quedaronpor fuera de esta definicion se computan automaticamente lo que facilita su uso.

Asimismo, se diseno una nueva perspectiva para Eclipse que incluye las distintas vistas quepermiten el debugging y localizacion de la falla detectada por TACO. Entre las vistas desarrolla-das se incluye la posibilidad de recorrer la traza reportada, visualizar la formula violada, evaluarexpresiones y visualizar el estado del heap en distintos puntos de la traza.

Finalmente se presento un caso de estudio complejo donde se utilizan estructuras de datos re-cursivas (binomial heap) y diversas construcciones del lenguaje Java (if, while). Se mostro comose utilizo TACO para detectar una falla y como el plugin TacoPlug facilito su aprovechamientopara detectar dicha falla.

Considerando las tecnicas y mecanismos aquı presentados, en conjunto con el caso de estudiorealizado y como fueron utilizados los componentes que los implementan para localizar la falla pre-sente en el codigo, se puede concluir que la utilizacion de la herramienta TACO se ha vuelto muchomas amigable y una mayor comprension del contraejemplo reportado por la misma es posible. Laextension TacoPlug probo ser util a la hora de localizar una falla reportada. Por estos motivos,la existencia de herramientas como TacoPlug resulta indispensable para dejar la verificacion deprogramas al alcance de un amplio espectro de usuarios.

El codigo fuente de TACO como de TacoPlug esta disponible publicamente a traves del sitiohttp://www.dc.uba.ar/taco.

45

7. Trabajo futuro

En lo que concierne a perspectivas futuras, existen diversos enfoques que pueden seguirse, tantoa nivel social como tecnico.

Desde un punto de vista social, se plantea la posibilidad de realizar experimentos de verifica-cion de la usabilidad de la herramienta con un rango amplio de programadores, los cuales podrıanincluir estudiantes. Esto permitirıa asentar la usabilidad de los componentes desarrollados e iden-tificar otros que podrıan resultar utiles para analizar errores detectados por TACO y localizar lafalla en el codigo fuente.

Desde un punto de vista tecnico, las posibilidades son amplias incluyendo mejoras de usabilidade integracion con funcionalidades de TACO que quedaron fuera del alcance de este trabajo.

Dentro de las mejoras de usabilidad propuestas se encuentran:

1. JDynAlloy y DynAlloy syntax highlighting. Como se presento en la seccion 2, se desa-rrollo un editor que permite la visualizacion de las transformaciones JDynAlloy y DynAlloydel programa original. Para mejorar la lectura de estas transformaciones resultarıa util laimplementacion de syntax highlighting en estos editores.

2. Administrador de analisis. Actualmente existe la posibilidad de ejecutar de a un analisis ala vez. Esto puede resultar incomodo si se desea analizar un metodo con distintos parametroso si al momento de analizar una traza se desea realizar un analisis sobre algun metodointerno. Estos problemas de usabilidad podrıan enfrentarse desarrollando un administradorde analisis TACO donde se guarden los distintos resultados y se contextualice el uso delplugin de acuerdo al analisis seleccionado.

3. Visualizacion del heap. Existen numerosos trabajos sobre visualizacion del heap [34] cuyaintegracion al plugin podrıa beneficiar el analisis que debe realizar el usuario cuando utilizaestructuras de datos recursivas.

4. Mejoras de performance. Algunos de los algoritmos relacionados con la recuperacion dela informacion tienen una performance un poco por debajo de lo esperado. Esto obstruye lausabilidad del plugin y debe mejorarse.

5. Diff entre versiones del grafo de memoria. Cuando se intenta localizar una falla en unprograma que utiliza estructuras de datos recursivas, la vista Java Memory Graph resultaun elemento clave. Sin embargo, en muchos casos resulta frustrante tener que analizar loscambios en el heap entre dos pasos consecutivos de la traza generada por TACO. Paraestos casos resultarıa muy util la incorporacion de un componente que permita visualizarfacilmente las diferencias entre dos grafos de memoria.

6. Evaluacion parcial de formulas. Luego de la deteccion de una falla, el usuario intentaidentificar el origen de la violacion a la especificacion utilizando la vista JML/JFSL An-notation Explorer. Este componente indica que formula fallo pero no permite el analisis delas subformulas que pudieran componerla. Serıa deseable facilitar al usuario la capacidadde analizar esta subformulas por separado pudiendo achicar el espacio de analisis para lalocalizacion de la falla.

Dentro de las mejoras que incluyen la integracion con funcionalidades de TACO no cubiertaspor el presente trabajo se incluye:

Integracion con generacion de casos de test. TACO presenta la posibilidad de generardistintos casos de test automaticos utilizando el framework de test jUnit. La integracionde esta funcionalidad a TacoPlug podrıa facilitar el debugging de un metodo utilizando unacercamiento dinamico al problema.

46

Slice del programa original. Se esta trabajando para lograr proveer desde TACO unslice del programa original, dado por el contraejemplo encontrado, que descarte todas lasinstrucciones que no estan directamente relacionadas con la violacion de la especificacionencontrada.

Finalmente cabe aclarar que cualquier trabajo sobre TACO que no ataque el problema de laeficiencia temporal de la herramienta, sino que brinde una nueva funcionalidad, puede constituirun potencial trabajo futuro sobre el plugin aquı presentado que incluya la integracion de la nuevafuncionalidad.

En este sentido, una posibilidad a considerar serıa la construccion de un plugin orientado adesarrolladores de la herramienta. Entre las caracterısiticas con las que contarıa esta version delplugin se podrıan incluir:

Edicion de los archivos JDynAlloy, DynAlloy, Alloy.

Visualizacion de los contextos de traduccion de las distintas etapas.

Visualizacion del repositorio de cotas que calcula TACO.

Visualizacion de TACO Flow, framework de dataflow integrado a TACO.

Integracion con Alloy Analyzer y sus herramientas de analisis del contrajemeplo.

47

A. Codigo fuente BinomialHeap

1 //2 // Copy r i gh t (C) 2006 Un i ted S t a t e s Government as r e p r e s e n t e d by the3 // Adm i n i s t r a t o r o f the Na t i o na l Ae r onau t i c s and Space Adm i n i s t r a t i o n4 // (NASA) . A l l R i gh t s Rese rved .5 //6 // This s o f twa r e i s d i s t r i b u t e d under the NASA Open Source Agreement7 // (NOSA) , v e r s i o n 1 . 3 . The NOSA has been approved by the Open Source8 // I n i t i a t i v e . See the f i l e NOSA−1.3−JPF at the top o f the d i s t r i b u t i o n9 // d i r e c t o r y t r e e f o r the complete NOSA document .

10 //11 // THE SUBJECT SOFTWARE IS PROVIDED ”AS IS ” WITHOUT ANY WARRANTY OF ANY12 // KIND , EITHER EXPRESSED, IMPLIED , OR STATUTORY, INCLUDING , BUT NOT13 // LIMITED TO, ANY WARRANTY THAT THE SUBJECT SOFTWARE WILL CONFORM TO14 // SPECIFICATIONS , ANY IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR15 // A PARTICULAR PURPOSE, OR FREEDOM FROM INFRINGEMENT, ANY WARRANTY THAT16 // THE SUBJECT SOFTWARE WILL BE ERROR FREE , OR ANY WARRANTY THAT17 // DOCUMENTATION, IF PROVIDED, WILL CONFORM TO THE SUBJECT SOFTWARE.18 //19 package a r . edu . taco ;20

21 /∗∗22 ∗ @SpecF ie ld nodes : s e t BinomialHeapNode from t h i s . Nodes , t h i s . nodes . c h i l d , t h i s . nodes . s i b l i n g , t h i s . nodes . pa r en t23 ∗ | t h i s . nodes = t h i s . Nodes . ∗ ( c h i l d @+ s i b l i n g ) @− n u l l ;24 ∗/25 /∗∗26 ∗ @ I n v a r i a n t ( a l l n : BinomialHeapNode | ( n i n t h i s . Nodes . ∗ ( s i b l i n g @+ c h i l d ) @− n u l l =>27 ∗ ( ( n . pa r en t != n u l l => n . key >= n . pa r en t . key ) &&28 ∗ ( n . c h i l d != n u l l => n ! i n n . c h i l d . ∗ ( s i b l i n g @+ c h i l d ) @− n u l l ) &&29 ∗ ( n . s i b l i n g != n u l l => n ! i n n . s i b l i n g . ∗ ( s i b l i n g @+ c h i l d ) @− n u l l ) &&30 ∗ ( ( n . c h i l d != n u l l && n . s i b l i n g != n u l l ) =>31 ∗ ( no m: BinomialHeapNode | ( m i n n . c h i l d . ∗ ( c h i l d @+ s i b l i n g ) @− n u l l &&32 ∗ m in n . s i b l i n g . ∗ ( c h i l d @+ s i b l i n g ) @− n u l l ) ) ) &&33 ∗ ( n . deg r ee >= 0 ) &&34 ∗ ( n . c h i l d=n u l l => n . deg r ee = 0 ) &&35 ∗ ( n . c h i l d != n u l l =>n . deg r ee=#(n . c h i l d .∗ s i b l i n g @− n u l l ) ) &&36 ∗ ( #( ( n . c h i l d @+ n . c h i l d . c h i l d . ∗ ( c h i l d @+ s i b l i n g ) ) @− n u l l ) = #( ( n . c h i l d @+ n . c h i l d . s i b l i n g . ∗ ( c h i l d @+ s i b l i n g ) ) @− n u l l ) ) &&37 ∗ ( n . c h i l d != n u l l => ( a l l m: BinomialHeapNode | ( m i n n . c h i l d .∗ s i b l i n g@−n u l l => m. pa r en t = n ) ) ) &&38 ∗ ( ( n . s i b l i n g != n u l l && n . pa r en t != n u l l ) => ( n . deg r ee > n . s i b l i n g . deg r ee ) ) ) ) ) &&39 ∗40 ∗ ( t h i s . s i z e = #( t h i s . Nodes . ∗ ( s i b l i n g @+ c h i l d ) @− n u l l ) ) &&41 ∗ ( a l l n : BinomialHeapNode | n i n t h i s . Nodes .∗ s i b l i n g @− n u l l =>42 ∗ ( ( n . s i b l i n g != n u l l => n . deg r ee < n . s i b l i n g . deg r ee ) &&43 ∗ ( n . pa r en t=n u l l ) ) ) ;44 ∗/45 p u b l i c c l a s s Binomia lHeap {46

47 p r i v a t e /∗@ n u l l a b l e @∗/BinomialHeapNode Nodes ;48

49 p r i v a t e i n t s i z e ;50

51 p u b l i c Binomia lHeap ( ) {52 Nodes = n u l l ;53 s i z e = 0 ;54 }55

56 /∗∗

48

57 ∗ @Mod i f i e s E v e r y t h i n g58 ∗59 ∗ @Requ i re s some t h i s . nodes ;60 ∗ @Ensures ( some x : BinomialHeapNode | x i n t h i s . nodes && x . key == r e t u r n61 ∗ ) && ( a l l y : BinomialHeapNode | ( y i n t h i s . nodes && y!= r e t u r n62 ∗ ) => r e t u r n <= y . key ) ;63 ∗/64 p u b l i c i n t findMinimum ( ) {65 r e t u r n Nodes . f indMinNode ( ) . key ;66 }67

68 p r i v a t e vo i d merge ( /∗ @ n u l l a b l e @ ∗/BinomialHeapNode binHeap ) {69 BinomialHeapNode temp1 = Nodes , temp2 = binHeap ;70 wh i l e ( ( temp1 != n u l l ) && ( temp2 != n u l l ) ) {71 i f ( temp1 . deg r ee == temp2 . deg r ee ) {72 BinomialHeapNode tmp = temp2 ;73 temp2 = temp2 . s i b l i n g ;74 tmp . s i b l i n g = temp1 . s i b l i n g ;75 temp1 . s i b l i n g = tmp ;76 temp1 = tmp . s i b l i n g ;77 } e l s e {78 i f ( temp1 . deg r ee < temp2 . deg r ee ) {79 i f ( ( temp1 . s i b l i n g == n u l l ) | | ( temp1 . s i b l i n g . deg r ee > temp2 . deg r ee ) ) {80 BinomialHeapNode tmp = temp2 ;81 temp2 = temp2 . s i b l i n g ;82 tmp . s i b l i n g = temp1 . s i b l i n g ;83 temp1 . s i b l i n g = tmp ;84 temp1 = tmp . s i b l i n g ;85 } e l s e {86 temp1 = temp1 . s i b l i n g ;87 }88 } e l s e {89 BinomialHeapNode tmp = temp1 ;90 temp1 = temp2 ;91 temp2 = temp2 . s i b l i n g ;92 temp1 . s i b l i n g = tmp ;93 i f ( tmp == Nodes ) {94 Nodes = temp1 ;95 }96 }97 }98 }99

100 i f ( temp1 == n u l l ) {101 temp1 = Nodes ;102 wh i l e ( temp1 . s i b l i n g != n u l l ) {103 temp1 = temp1 . s i b l i n g ;104 }105 temp1 . s i b l i n g = temp2 ;106 }107

108 }109

110 p r i v a t e vo i d unionNodes ( /∗ @ n u l l a b l e @ ∗/BinomialHeapNode binHeap ) {111 merge ( binHeap ) ;112

113 BinomialHeapNode prevTemp = nu l l , temp = Nodes , nextTemp = Nodes . s i b l i n g ;114

49

115 wh i l e ( nextTemp != n u l l ) {116 i f ( ( temp . deg r ee != nextTemp . deg r ee ) | |117 (118 ( nextTemp . s i b l i n g != n u l l ) &&119 ( nextTemp . s i b l i n g . deg r ee == temp . deg r ee )120 )121 ) {122 prevTemp = temp ;123 temp = nextTemp ;124 } e l s e {125 i f ( temp . key <= nextTemp . key ) {126 temp . s i b l i n g = nextTemp . s i b l i n g ;127 nextTemp . pa r en t = temp ;128 nextTemp . s i b l i n g = temp . c h i l d ;129 temp . c h i l d = nextTemp ;130 temp . deg r ee++;131 } e l s e {132 i f ( prevTemp == n u l l ) {133 Nodes = nextTemp ;134 } e l s e {135 prevTemp . s i b l i n g = nextTemp ;136 }137 temp . pa r en t = nextTemp ;138 temp . s i b l i n g = nextTemp . c h i l d ;139 nextTemp . c h i l d = temp ;140 nextTemp . deg r ee++;141 temp = nextTemp ;142 }143 }144

145 nextTemp = temp . s i b l i n g ;146 }147 }148

149 /∗∗150 ∗ @Mod i f i e s E v e r y t h i n g151 ∗152 ∗ @Ensures some n : BinomialHeapNode | ( n ! i n @old ( t h i s . nodes ) &&153 ∗ t h i s . nodes = @old ( t h i s . nodes ) @+ n && n . key = va l u e ) ;154 ∗/155 p u b l i c vo i d i n s e r t ( i n t v a l u e ) {156 i f ( v a l u e > 0) {157 BinomialHeapNode temp = new BinomialHeapNode ( v a l u e ) ;158 i f ( Nodes == n u l l ) {159 Nodes = temp ;160 s i z e = 1 ;161 } e l s e {162 unionNodes ( temp ) ;163 s i z e++;164 }165 }166 }167

168 /∗∗169 ∗ @Mod i f i e s E v e r y t h i n g170 ∗171 ∗ @Ensures ( @old ( t h i s ) . @old ( Nodes)==n u l l => (172 ∗ t h i s . Nodes==n u l l &&

50

173 ∗ r e t u r n==n u l l174 ∗ )175 ∗ )176 ∗ && ( @old ( t h i s ) . @old ( Nodes )!= n u l l => (177 ∗ ( r e t u r n i n @old ( t h i s . nodes ) ) &&178 ∗ ( a l l y : BinomialHeapNode | (179 ∗ y i n @old ( t h i s . nodes ) => y . key >= r e t u r n . key180 ∗ ) ) &&181 ∗ ( t h i s . nodes=@old ( t h i s . nodes ) @− r e t u r n ) &&182 ∗ ( t h i s . nodes . key @+ r e t u r n . key = @old ( t h i s . nodes . key ) )183 ∗ )184 ∗ ) ;185 ∗/186 p u b l i c /∗ @ n u l l a b l e @ ∗/BinomialHeapNode ex t r a c tM in ( ) {187 i f ( Nodes == n u l l )188 r e t u r n n u l l ;189

190 BinomialHeapNode temp = Nodes , prevTemp = n u l l ;191 BinomialHeapNode minNode = n u l l ;192

193 minNode = Nodes . f indMinNode ( ) ;194 wh i l e ( temp . key != minNode . key ) {195 prevTemp = temp ;196 temp = temp . s i b l i n g ;197 }198

199 i f ( prevTemp == n u l l ) {200 Nodes = temp . s i b l i n g ;201 } e l s e {202 prevTemp . s i b l i n g = temp . s i b l i n g ;203 }204 temp = temp . c h i l d ;205 BinomialHeapNode fakeNode = temp ;206 wh i l e ( temp != n u l l ) {207 temp . pa r en t = n u l l ;208 temp = temp . s i b l i n g ;209 }210

211 i f ( ( Nodes == n u l l ) && ( fakeNode == n u l l ) ) {212 s i z e = 0 ;213 } e l s e {214 i f ( ( Nodes == n u l l ) && ( fakeNode != n u l l ) ) {215 Nodes = fakeNode . r e v e r s e ( n u l l ) ;216 s i z e −−;217 } e l s e {218 i f ( ( Nodes != n u l l ) && ( fakeNode == n u l l ) ) {219 s i z e −−;220 } e l s e {221 unionNodes ( fakeNode . r e v e r s e ( n u l l ) ) ;222 s i z e −−;223 }224 }225 }226

227 r e t u r n minNode ;228 }229

230 p u b l i c vo i d dec r ea seKeyVa lue ( i n t o l d v a l u e , i n t new va lue ) {

51

231 BinomialHeapNode temp = Nodes . f indANodeWithKey ( o l d v a l u e ) ;232 decreaseKeyNode ( temp , new va lue ) ;233 }234

235 /∗∗236 ∗237 ∗ @Mod i f i e s E v e r y t h i n g238 ∗239 ∗ @Requ i re s node i n t h i s . nodes && node . key >= new va lue ;240 ∗241 ∗ @Ensures ( some o th e r : BinomialHeapNode | o th e r i n t h i s . nodes &&242 ∗ o th e r !=node && @old ( o th e r . key)=@old ( node . key ) ) ? t h i s . nodes . key243 ∗ = @old ( t h i s . nodes . key ) @+ new va lue : t h i s . nodes . key =244 ∗ @old ( t h i s . nodes . key ) @− @old ( node . key ) @+ new va lue ;245 ∗/246 p u b l i c vo i d decreaseKeyNode ( f i n a l BinomialHeapNode node , f i n a l i n t new va lue ) {247 i f ( node == n u l l )248 r e t u r n ;249

250 BinomialHeapNode y = node ;251 y . key = new va lue ;252 BinomialHeapNode z = node . pa r en t ;253

254 wh i l e ( ( z != n u l l ) && ( node . key < z . key ) ) {255 i n t z k ey = y . key ;256 y . key = z . key ;257 z . key = z key ;258

259 y = z ;260 z = z . pa r en t ;261 }262 }263

264 p u b l i c vo i d d e l e t e ( i n t v a l u e ) {265 i f ( ( Nodes != n u l l ) && (Nodes . f indANodeWithKey ( v a l u e ) != n u l l ) ) {266 dec rea seKeyVa lue ( va lue , f indMinimum ( ) − 1 ) ;267 ex t r a c tM in ( ) ;268 }269 }270 }

1 package a r . edu . taco ;2

3 p u b l i c c l a s s BinomialHeapNode{4 i n t key ;5

6 i n t deg r ee ;7

8 /∗@ n u l l a b l e @∗/BinomialHeapNode pa r en t ;9

10 /∗@ n u l l a b l e @∗/BinomialHeapNode s i b l i n g ;11

12 /∗@ n u l l a b l e @∗/BinomialHeapNode c h i l d ;13

14 p u b l i c BinomialHeapNode ( i n t k ) {15 key = k ;16 deg r ee = 0 ;17 pa r en t = n u l l ;

52

18 s i b l i n g = n u l l ;19 c h i l d = n u l l ;20 }21

22 p u b l i c i n t getKey ( ) {23 r e t u r n key ;24 }25

26 p r i v a t e vo i d setKey ( i n t v a l u e ) {27 key = va l u e ;28 }29

30 p u b l i c i n t getDegree ( ) {31 r e t u r n deg r ee ;32 }33

34 p r i v a t e vo i d s e tDeg r ee ( i n t deg ) {35 deg r ee = deg ;36 }37

38 p u b l i c BinomialHeapNode ge tPa r en t ( ) {39 r e t u r n pa r en t ;40 }41

42 p r i v a t e vo i d s e tPa r e n t ( BinomialHeapNode par ) {43 pa r en t = par ;44 }45

46 p u b l i c BinomialHeapNode g e t S i b l i n g ( ) {47 r e t u r n s i b l i n g ;48 }49

50 p r i v a t e vo i d s e t S i b l i n g ( BinomialHeapNode nextBr ) {51 s i b l i n g = nextBr ;52 }53

54 p u b l i c BinomialHeapNode g e tCh i l d ( ) {55 r e t u r n c h i l d ;56 }57

58 p r i v a t e vo i d s e t C h i l d ( BinomialHeapNode f i r s t C h ) {59 c h i l d = f i r s t C h ;60 }61

62 p u b l i c i n t g e t S i z e ( ) {63 r e t u r n (64 1 +65 ( ( c h i l d == n u l l ) ? 0 : c h i l d . g e t S i z e ( ) ) +66 ( ( s i b l i n g == n u l l ) ? 0 : s i b l i n g . g e t S i z e ( ) )67 ) ;68 }69

70 BinomialHeapNode r e v e r s e ( BinomialHeapNode s i b l ) {71 BinomialHeapNode r e t ;72 i f ( s i b l i n g != n u l l )73 r e t = s i b l i n g . r e v e r s e 0 ( t h i s ) ;74 e l s e75 r e t = t h i s ;

53

76 s i b l i n g = s i b l ;77 r e t u r n r e t ;78 }79

80 BinomialHeapNode r e v e r s e 0 ( BinomialHeapNode s i b l ) {81 BinomialHeapNode r e t ;82 i f ( s i b l i n g != n u l l )83 r e t = s i b l i n g . r e v e r s e 1 ( t h i s ) ;84 e l s e85 r e t = t h i s ;86 s i b l i n g = s i b l ;87 r e t u r n r e t ;88 }89

90 BinomialHeapNode r e v e r s e 1 ( BinomialHeapNode s i b l ) {91 BinomialHeapNode r e t ;92 i f ( s i b l i n g != n u l l )93 r e t = s i b l i n g . r e v e r s e 2 ( t h i s ) ;94 e l s e95 r e t = t h i s ;96 s i b l i n g = s i b l ;97 r e t u r n r e t ;98 }99

100 BinomialHeapNode r e v e r s e 2 ( BinomialHeapNode s i b l ) {101 BinomialHeapNode r e t ;102 i f ( s i b l i n g != n u l l )103 r e t = s i b l i n g . r e v e r s e 3 ( t h i s ) ;104 e l s e105 r e t = t h i s ;106 s i b l i n g = s i b l ;107 r e t u r n r e t ;108 }109

110 BinomialHeapNode r e v e r s e 3 ( BinomialHeapNode s i b l ) {111 BinomialHeapNode r e t ;112 i f ( s i b l i n g != n u l l )113 r e t = s i b l i n g . r e v e r s e 4 ( t h i s ) ;114 e l s e115 r e t = t h i s ;116 s i b l i n g = s i b l ;117 r e t u r n r e t ;118 }119

120 BinomialHeapNode r e v e r s e 4 ( BinomialHeapNode s i b l ) {121 BinomialHeapNode r e t ;122 i f ( s i b l i n g != n u l l )123 r e t = s i b l i n g . r e v e r s e 5 ( t h i s ) ;124 e l s e125 r e t = t h i s ;126 s i b l i n g = s i b l ;127 r e t u r n r e t ;128 }129

130 BinomialHeapNode r e v e r s e 5 ( BinomialHeapNode s i b l ) {131 BinomialHeapNode r e t ;132 i f ( s i b l i n g != n u l l )133 r e t = s i b l i n g . r e v e r s e 6 ( t h i s ) ;

54

134 e l s e135 r e t = t h i s ;136 s i b l i n g = s i b l ;137 r e t u r n r e t ;138 }139

140 BinomialHeapNode r e v e r s e 6 ( BinomialHeapNode s i b l ) {141 BinomialHeapNode r e t ;142 i f ( s i b l i n g != n u l l )143 r e t = s i b l i n g . r e v e r s e 7 ( t h i s ) ;144 e l s e145 r e t = t h i s ;146 s i b l i n g = s i b l ;147 r e t u r n r e t ;148 }149

150 BinomialHeapNode r e v e r s e 7 ( BinomialHeapNode s i b l ) {151 BinomialHeapNode r e t ;152 i f ( s i b l i n g != n u l l )153 r e t = s i b l i n g . r e v e r s e 8 ( t h i s ) ;154 e l s e155 r e t = t h i s ;156 s i b l i n g = s i b l ;157 r e t u r n r e t ;158 }159

160 BinomialHeapNode r e v e r s e 8 ( BinomialHeapNode s i b l ) {161 BinomialHeapNode r e t ;162 i f ( s i b l i n g != n u l l )163 r e t = s i b l i n g . r e v e r s e 9 ( t h i s ) ;164 e l s e165 r e t = t h i s ;166 s i b l i n g = s i b l ;167 r e t u r n r e t ;168 }169

170 BinomialHeapNode r e v e r s e 9 ( BinomialHeapNode s i b l ) {171 BinomialHeapNode r e t ;172 i f ( s i b l i n g != n u l l )173 throw new Runt imeExcept ion ( ) ;174 e l s e175 r e t = t h i s ;176 s i b l i n g = s i b l ;177 r e t u r n r e t ;178 }179

180 BinomialHeapNode f indMinNode ( ) {181 BinomialHeapNode x = th i s , y = t h i s ;182 i n t min = x . key ;183

184 wh i l e ( x != n u l l ) {185 i f ( x . key < min ) {186 y = x ;187 min = x . key ;188 }189 x = x . s i b l i n g ;190 }191

55

192 r e t u r n y ;193 }194

195 BinomialHeapNode findANodeWithKey ( i n t v a l u e ) {196 BinomialHeapNode temp = th i s , node = n u l l ;197 wh i l e ( temp != n u l l ) {198 i f ( temp . key == va l u e ) {199 node = temp ;200 r e t u r n node ;201 }202 i f ( temp . c h i l d == n u l l )203 temp = temp . s i b l i n g ;204 e l s e {205 node = temp . c h i l d . f indANodeWithKey ( v a l u e ) ;206 i f ( node == n u l l )207 temp = temp . s i b l i n g ;208 e l s e209 r e t u r n node ;210 }211 }212

213 r e t u r n node ;214 }215 }

56

Referencias

[1] “Daikon.” [Online]. Available: http://groups.csail.mit.edu/pag/daikon/

[2] “Valgrind.” [Online]. Available: http://valgrind.org/

[3] E. Clarke, O. Grumberg, and D. Peled, Model Checking. MIT Press, 2000.

[4] E. Clarke, O. Grumberg, and D. Long, “Model checking and abstraction,” ACM Transactionson Programming Languages and Systems (TOPLAS), vol. 16, no. 5, pp. 1512–1542, 1994.

[5] J. Harrison, “Formal verification in industry.” Intel Corporation, 1999.

[6] J. Galeotti, N. Rosner, C. Lopez Pombo, and M. Frias, “Analysis of Invariants for EfficientBounded Verification,” in International Symposium on Software Testing and Analysis, 2010.

[7] D. Dobniewski, G. Gasser Noblia, and J. Galeotti, “Verificacion de un sistema de votacionusando SAT-Solving,” Master’s thesis, Universidad de Buenos Aires, 2010.

[8] F. Ivancic, Z. Yang, M. Ganai, A. Gupta, I. Shlyakhter, and P. Ashar, “F-Soft: SoftwareVerification Platform.” In CAV’05, pp. 301–306, 2005.

[9] E. Clarke, D. Kroening, and L. F., “A Tool for Checking ANSI-C Programs,” In proceedingsof TACAS 2004. LNCS (2988) pp. 168–176., 2004.

[10] D. J., V. M., and T. F., “Finding Bugs Efficiently with a SAT Solver,” ESEC/FSE’07, pp. 195–204, ACM Press, 2007.

[11] G. Dennis, “A Relational Framework for Bounded Program Verification,” MIT PhD Thesis,2009.

[12] “JForge Eclipse Plug-in.” [Online]. Available: http://sdg.csail.mit.edu/forge/plugin.html

[13] M. P. and R. J., “Using Debuggers to Understand Failed Verification Attempts,” In FormalMethods (FM) 2011, pp. 73–87, 2011.

[14] C. Le Goues, M. Leino, and M. Moskal, “The Boogie Verification Debugger,” SEFM, 2011.

[15] M. Frıas, J. Galeotti, L. P. C., and N. Aguirre, “Dynalloy: upgrading alloy with actions,”ICSE ’05: Proceedings of the 27th international conference on Software engineering, pages442-451, 2005.

[16] “Eiffel Software.” [Online]. Available: http://www.eiffel.com/

[17] “Larch.” [Online]. Available: http://www.eecs.ucf.edu/∼leavens/larch-faq.html

[18] “Refinement Calculus Tutorial.” [Online]. Available: http://users.ecs.soton.ac.uk/mjb/refcalc-tut/home.html

[19] “Java Modeling Language.” [Online]. Available: http://www.eecs.ucf.edu/∼leavens/JML/

[20] “Relational Formula Method Research Group.” [Online]. Available: http://www.dc.uba.ar/inv/grupos/rfm folder

[21] D. Jackson, “Alloy: a lightweight object modelling notation,” ACM Transactions on SoftwareEngineering and Methodology (TOSEM), 2002.

[22] “Alloy.” [Online]. Available: http://alloy.mit.edu/alloy/

[23] J. Galeotti, “Verificacion de Software usando Alloy,” PHD’s thesis, Universidad de BuenosAires, 2010.

57

[24] “Sun Microsystems. JDC techtips.” 2000. [Online]. Available: http://java.sun.com/developer/TechTips/2000/tt0314.html

[25] “Eclipse.” [Online]. Available: http://www.eclipse.org/

[26] P. Bendersky, “Hacia un entorno integrado para la verificacion de contratos utilizando SATSolvers,” Master’s thesis, Universidad de Buenos Aires, 2010.

[27] “Plugin Development Environment.” [Online]. Available: http://www.eclipse.org/pde/

[28] “jUnit.” [Online]. Available: http://www.junit.org/

[29] T. Cormen, L. C., R. R., and S. C., “Introduction to Algorithms (3. ed.),” MIT Press, 2009.

[30] V. W., P. C. S., and P. R., “Test Input Generation for Java Containers using State Matching,”ISSTA 2006, pp. 37–48, 2006.

[31] “Eclipse Incubator Spy.” [Online]. Available: http://www.eclipse.org/pde/incubator/spy/

[32] “JFace.” [Online]. Available: http://wiki.eclipse.org/JFace

[33] “Zest.” [Online]. Available: http://www.eclipse.org/gef/zest/

[34] T. Zimmermann and A. Zeller, “Visualizing Memory Graphs,” Software Visualizationpp. 191–204, 2001.

58