Verificación de Sistemas Basada en Teoría de Tipos

Este proyecto se enmarca en la utlización de métodos formales (más precisamente, en la utilización de teoría de tipos) para garantizar la ausencia de errores en programas. Por un lado se plantea el diseño de nuevos algoritmos de chequeo de tipos. Para ello, se proponen nuevos algoritmos basados en la idea de normalización por evaluación que sean extensibles a otros sistemas de tipos. En el futuro próximo extenderemos resultados que hemos conseguido recientemente [16,17] para obtener: una simplificación de los trabajos realizados para sistemas sin regla eta (acá se estudiarán dos sistemas: a la Martin Löf y a la PTS), la formulación de estos chequeadores para sistemas con variables, generalizar la noción de categoría con familia utilizada para dar semántica a teoría de tipos, obtener una formulación categórica de la noción de normalización por evaluación y finalmente, aplicar estos algoritmos a sistemas con reescrituras. Para los primeros resultados esperados mencionados, nos proponemos como método adaptar las pruebas de [16,17] a los nuevos sistemas. La importancia radica en que permitirán tornar más automatizables (y por ello, más fácilmente utilizables) los asistentes de demostración basados en teoría de tipos. Por otro lado, se utilizará la teoría de tipos para certificar compiladores, intentando llevar adelante la propuesta nunca explorada de [22] de utilizar un enfoque abstracto basado en categorías funtoriales. El método consistirá en certificar el lenguaje "Peal" [29] y luego agregar sucesivamente funcionalidad hasta obtener Forsythe [23]. En este período esperamos poder agregar varias extensiones. La importancia de este proyecto radica en que sólo un compilador certificado garantiza que un programa fuente correcto se compile a un programa objeto correcto. Es por ello, crucial para todo proceso de verificación que se base en verificar código fuente. Finalmente, se abordará la formalización de sistemas con session types. Los mismos han demostrado tener fallas en sus formulaciones [30], por lo que parece conveniente su formalización. Durante la marcha de este proyecto, esperamos tener alguna formalización que dé lugar a un algoritmo de chequeo de tipos y a demostrar las propiedades usuales de los sistemas. La contribución es arrojar un poco de luz sobre estas formulaciones cuyos errores revelan que el tema no ha adquirido aún suficiente madurez o comprensión por parte de la comunidad.

Desarrollo Riguroso de Sistemas Tolerantes a Fallas

Los sistemas críticos son aquellos utilizados en áreas en las cuales las fallas, o los eventos inesperados, pueden ocasionar grandes perdidas de dinero; o quizás peor aún, daños a vidas humanas. Esta clase de sistemas juegan un rol importante en actividades esenciales de la sociedad tales como la medicina y las comunicaciones. Los sistemas críticos, cada vez son más usuales en la vida real, algunos ejemplos de estos son los sistemas de aviones, sistemas para automóviles y sistemas utilizados en telefonia móvil. Para minimizar las fallas, y las perdidas materiales o humanas ocasionadas por el funcionamiento incorrecto de dichos sistemas, se utilizan técnicas de tolerancia a fallas. Estas técnicas permiten que los sistemas continúen funcionando aún bajo la ocurrencia de fallas, o eventos inesperados. Existen diversas técnicas para lograr tolerancia a fallas utilizando, por ejemplo, redundancia a diferentes niveles de abstracción, como, por ejemplo, al nivel de hardware. Sin embargo, estas técnicas dependen fuertemente del sistema, y del contexto en las que se utilizan. Más aún, la mayoría de la técnicas de tolerancia a fallas son usadas a bajo nivel (código fuente o hardware), estimamos que el uso de formalismos rigurosos (con fundamentos matemáticos) pueden llevar al diseño de sistemas tolerantes a fallas y robustos a un nivel de abstracción más alto, a la vez que la utilización de técnicas de verificación que han sido exitosas en la práctica tales como model checking, o la síntesis de controladores, pueden llevar a una verificación y producción automática de sistemas robustos. El objetivo del presente proyecto es estudiar tanto marcos teóricos, que permitan la construcción de sistemas más robustos, como también herramientas automáticas que hagan posible la utilización de estos formalismos en escenarios complejos. Para lograr estos objetivos, será necesario considerar casos de estudios de diferente complejidad, y además que sean relevantes en la práctica. Por ejemplo: bombas de insulina, protocolos de comunicación, sistemas de vuelo y sistemas utilizados con fines médicos. Planeamos obtener prototipos de algunos de estos casos de estudio para evaluar los marcos teóricos propuestos. En los últimos años diferentes formalismos han sido utilizados para razonar sobre sistemas tolerantes a fallas de una forma rigurosa, sin embargo, la mayoría de estos son ad hoc, por lo cual sólo son aplicables a contextos específicos. Planeamos utilizar ciertas lógicas modales, en conjunto con nociones probabilísticas, para obtener un conjunto de herramientas suficientemente generales para que puedan ser utilizadas en diferentes contextos y aplicaciones. Los materiales a utilizar son equipos informáticos, en particular computadoras portátiles para el equipo de trabajo y computadoras más potentes para el testeo y desarrollo del software necesario para lograr los objetivos del proyecto. Para construir los prototipos mencionados se utilizarán equipos de computación estándar (el equipo investigación cuenta con computadoras intel y mac) en conjunto con lenguajes de programación modernos como JAVA o C#. En el caso de que los sistemas de software sean sistemas embebidos; se piensa desarrollar un motor de simulación que permita evaluar el desempeño del software cuando es ejecutado en el dispositivo mencionado. Se espera desarrollar, e investigar, las propiedades de formalismos matemáticos que permitan el desarrollo de sistemas tolerantes a fallas. Además, se desarrollarán herramientas de software para que estos sistemas tolerantes a fallas puedan verificarse, o obtenerse automáticamente. Los resultados obtenidos serán difundidos por medio de publicaciones en revistas del área. El desarrollo de sistemas tolerantes a fallas por medio de técnicas rigurosas, a diferentes niveles de abstracción (captura de requisitos, diseño, implementación y validación), permitirá minimizar los riesgos inherentes en actividades críticas.