💻 computer science

A Sound Translation from Tamarin to ProVerif: Enabling Comparative Analysis

Este artículo presenta una traducción sólida de Tamarin a ProVerif que permite un análisis comparativo riguroso de las herramientas de verificación de protocolos de seguridad mediante la codificación de la semántica de reescritura de multiconjuntos de Tamarin en el cálculo applied-pi de ProVerif, logrando una alta cobertura y ganancias significativas de rendimiento al tiempo que caracteriza formalmente los límites de la traducción fiel.

Autores originales: Kevin Morio, Yavor Ivanov, Robert Künnemann

Publicado 2026-08-07

📖 6 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Kevin Morio, Yavor Ivanov, Robert Künnemann

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que eres un detective intentando resolver un misterio, pero en lugar de una escena del crimen, tu "crimen" es un código secreto que podría ser roto por un hacker astuto. En el mundo de la seguridad informática, estos códigos se llaman protocolos: las reglas que permiten que tu teléfono hable con un banco, o que tu consola de juegos hable con un servidor. El problema es que estas reglas son tan complicadas que incluso los detectives humanos más inteligentes pueden pasar por alto un pequeño vacío legal por donde un hacker podría colarse. Así que los científicos construyeron "detectives automatizados", que son programas informáticos superinteligentes diseñados para buscar agujeros en estas reglas.

Dos de los detectives automatizados más famosos se llaman Tamarin y ProVerif. Piensa en ellos como dos tipos de investigadores con estilos muy diferentes. Tamarin es como un bibliotecario meticuloso y de movimientos lentos que revisa cada libro en el estante, uno por uno, para asegurarse de que no falte nada. Es increíblemente minucioso y rara vez comete errores, pero puede tardar mucho tiempo en terminar su trabajo. ProVerif, por otro lado, es como un lector veloz que escanea los estantes. Puede revisar una biblioteca masiva en segundos, pero debido a que lee de forma superficial, a veces puede pensar que ha encontrado un problema donde no lo hay (una "falsa alarma").

Durante años, estos dos detectives trabajaron en oficinas separadas. Debido a que hablaban "idiomas" diferentes y utilizaban métodos distintos, era casi imposible compararlos directamente. No podías preguntar fácilmente: "¿Vale la pena el riesgo de perder un problema real con la velocidad de ProVerif?" o "¿Realmente detecta Tamarin cosas que ProVerif pasa por alto gracias a su lentitud?". Este artículo trata sobre la construcción de un traductor mágico que permite que estos dos detectives hablen entre sí, permitiéndoles resolver los mismos casos de forma paralela para ver quién es más rápido, quién es más preciso y dónde residen sus fortalezas.

El Gran Traductor de Detectives

Los autores de este artículo, Kevin Morio, Yavor Ivanov y Robert Künnemann, construyeron una herramienta de traducción sonora (sound translation). En el mundo de la ciencia, "sonora" (sound) es una forma elegante de decir "fiable". Crearon un sistema que toma un protocolo de seguridad escrito en el lenguaje lento pero preciso de Tamarin y lo reescribe automáticamente al lenguaje rápido pero superficial de ProVerif.

Pero aquí está la parte difícil: no puedes simplemente traducir un libro palabra por palabra si los dos idiomas tienen reglas gramaticales diferentes. Tamarin utiliza un método llamado reglas de reescritura de multiconjuntos (multiset rewrite rules), que es como tener un montón de cartas físicas donde solo puedes usar una carta una vez antes de que desaparezca. ProVerif utiliza algo llamado cálculo-π aplicado (applied-π calculus), que es más parecido a una base de datos digital donde las entradas pueden copiarse y reutilizarse. Para que la traducción funcione, los autores inventaron nuevas técnicas para obligar a ProVerif a actuar como si estuviera usando cartas físicas que desaparecen, asegurando que no vuelva a usar accidentalmente una "carta" y cree un problema falso. También descubrieron cómo manejar los "eventos simultáneos": momentos donde Tamarin dice que dos cosas suceden exactamente al mismo tiempo, mientras que ProVerif insiste en que todo sucede uno tras otro. Resolvieron esto asignando a cada evento una etiqueta de ID única, para que ProVerif sepa qué eventos pertenecen al mismo momento.

Lo que Encontraron: Velocidad vs. Precisión

El equipo no solo construyó el traductor; lo puso a prueba. Tomaron 121 modelos de seguridad diferentes (piensa en estos como 121 sistemas diferentes de cerradura y llave) y los pasaron tanto por Tamarin como por la nueva traducción de ProVerif.

Los resultados fueron fascinantes:

El Acuerdo: De 562 controles de seguridad específicos (llamados "tareas de lema" o lemma tasks) que ambos programas pudieron ejecutar con éxito, 246 de 247 casos no complicados coincidieron perfectamente. Si Tamarin decía "Seguro", ProVerif decía "Seguro". Si Tamarin encontraba un "Hacker", ProVerif encontraba el mismo "Hacker". El único caso en el que no coincidieron fue señalado porque la traducción era incompleta para ese modelo específico, no porque las herramientas sean fundamentalmente defectuosas.
La Brecha de Velocidad: Aquí es donde ProVerif brilla. Cuando ambos programas terminaban una tarea, ProVerif era, en promedio, 6.74 veces más rápido. En términos de memoria (cuánta capacidad de procesamiento utilizaba el ordenador), ProVerif era 6.24 veces más eficiente.
- Para ponerlo en perspectiva: para un estudio de caso famoso específico (el arreglo de Lowe para el protocolo Andrew Secure RPC), Tamarin tardó unos 30 segundos en verificar cinco reglas de seguridad diferentes. ProVerif hizo exactamente el mismo trabajo en solo 0.46 segundos. ¡Esa es una aceleración de casi 65 veces para ese test específico!
La Advertencia de "Mejor Esfuerzo": Los autores fueron muy cuidadosos al notar que algunas características, como un truco matemático específico llamado XOR, no podían traducirse perfectamente. Para estos casos, los resultados de ProVerif son aproximaciones de "mejor esfuerzo". En estos casos complicados de XOR, las herramientas no coincidieron con frecuencia (31 de 65 veces), por lo que los autores advierten a los usuarios que no confíen esos resultados específicos como una prueba absoluta.

Por Qué Esto Importa

Este artículo no pretende que ProVerif sea ahora "mejor" que Tamarin, ni que Tamarin sea obsoleto. En cambio, demuestra que para una gran parte de los problemas de seguridad (el "núcleo común"), puedes usar la herramienta rápida (ProVerif) con confianza, sabiendo que si dice que un sistema es seguro, la herramienta lenta y meticulosa (Tamarin) estaría de acuerdo.

Los autores demostraron que, mediante el uso de su traducción, los investigadores de seguridad pueden ahora usar ProVerif como un "backend rápido" para verificar muchas ideas rápidamente, manteniendo la opción de usar Tamarin para las comprobaciones finales más críticas. Es como tener a un lector veloz que puede escanear una biblioteca en segundos para encontrar los libros que necesitas, sabiendo que el bibliotecario está ahí para revisar los más importantes si necesitas un 100% de certeza.

En resumen, el artículo logra cerrar la brecha entre dos gigantes de la seguridad informática, demostando que pueden trabajar juntos para hacer nuestro mundo digital más seguro, rápido y fiable.

Resumen Técnico: Una Traducción Sólida de Tamarin a ProVerif

Planteamiento del Problema

Las herramientas de verificación de protocolos como Tamarin y ProVerif son prominentes en el análisis formal de protocolos de seguridad, pero operan sobre formalismos fundamentalmente distintos, lo que dificulta la comparación sistemática y el aprovechamiento de sus fortalezas complementarias.

Tamarin utiliza Reglas de Reescritura de Multiconjuntos (MSRs) con resolución de restricciones. Ofrece una verificación sólida y completa, eliminando ataques espurios, pero puede sufrir problemas de eficiencia y falta de terminación.
ProVerif emplea el cálculo $\pi$ -aplicado con abstracción de cláusulas de Horn. Es típicamente más rápido y evita el retroceso (backtracking), pero puede producir ataques espurios (resultados incompletos) debido a la sobreaproximación.

La falta de un mecanismo de traducción entre estas herramientas hace que sea difícil determinar qué propiedades son verificables en ambas, comparar su rendimiento en modelos semánticamente equivalentes o utilizar ProVerif como un backend rápido para modelos de Tamarin. El trabajo previo se ha centrado en traducir de $\pi$ -aplicado a MSRs (por ejemplo, de SAPiC+ a Tamarin) o en conexiones teóricas de alcance limitado, pero faltaba una traducción sólida y exhaustiva de Tamarin a ProVerif.

Metodología

Los autores presentan una traducción sólida de Tamarin a ProVerif que cierra la brecha entre las MSRs y el cálculo $\pi$ -aplicado. La traducción se compone de tres componentes principales:

1. Traducción de Reglas (Generación de Procesos)

Las reglas de Tamarin se traducen en procesos paralelos de ProVerif.

Gestión de Estado: El multiconjunto de hechos de Tamarin se emula utilizando las tablas de ProVerif. Dado que las tablas de ProVerif son monotónicas (no se pueden eliminar entradas), esto inicialmente sobreaproxima la consumición lineal de hechos de Tamarin.
Semántica de Multiconjuntos: Para preservar la semántica de "consumir una vez" de los hechos lineales, la traducción introduce identificadores de instancias de regla nuevos (fresh). Para cada hecho de almacenamiento lineal, se genera un identificador único que se almacena. Se añade una restricción para asegurar que no ocurran dos eventos con el mismo identificador y argumentos, imponiendo efectivamente la consumición lineal.
Coincidencia de Patrones (Pattern Matching): Tamarin permite la coincidencia de patrones en hechos (por ejemplo, extraer variables de términos cifrados). Las entradas de ProVerif solo admiten patrones de tuplas. La traducción introduce destructores auxiliares privados para extraer variables de patrones complejos, asegurando que estas capacidades no sean expuestas al atacante.
Comunicación: Los inputs de red (In) y outputs (Out) se mapean a los in y out de ProVerif en un canal público global. Los nombres nuevos (Fr) se mapean a new.

2. Traducción de Lemas (Reescritura de Propiedades)

Los lemas de Tamarin se traducen en consultas de ProVerif. La traducción gestiona las diferencias lógicas entre la lógica de primer orden de dos tipos de Tamarin y el fragmento SA-QBF (Fórmulas Booleanas Cuantificadas de Alternancia Única) de ProVerif.

Gestión de Cuantificadores: Los cuantificadores explícitos de Tamarin se mapean a la cuantificación implícita de ProVerif (variables de premisa universalmente cuantificadas, variables de conclusión existencialmente cuantificadas).
Reescritura Lógica:
- Disyunciones/Conjunciones: Las disyunciones de nivel superior en los lemas de exists-trace y las conjunciones en los lemas de all-trace se dividen en múltiples consultas de ProVerif. Los resultados se recombinan lógicamente (por ejemplo, el lema se cumple si cualquier consulta dividida se cumple para la existencia, o si todas para la universalidad).
- Negación: ProVerif no admite la negación en las consultas. La traducción utiliza equivalencias lógicas para mover las negaciones, convirtiendo a menudo las propiedades de all-trace en consultas de alcanzabilidad con resultados invertidos.
Eventos Simultáneos: Tamarin permite múltiples hechos de acción en un mismo instante de tiempo. La traducción asigna un identificador de instancia de regla compartido a los eventos de la misma regla, permitiendo que ProVerIF (que asume un orden total) simule la simultaneidad.
Hechos de Conocimiento: El K(m) de Tamarin (el atacante deriva explícitamente m) se traduce al attacker(m) de ProVerif bajo restricciones de polaridad específicas (átomos positivos en la hipótesis de las propiedades de all-trace).

3. Puente de Brechas Semánticas

Simultaneidad: Gestionada mediante identificadores de instancia de regla para vincular los eventos.
Semántica de Implicación: La traducción tiene en cuenta las sutiles diferencias en cómo Tamarin y ProVerif interpretan la implicación (=>) respecto al orden temporal, utilizando restricciones de progreso cuando es necesario.
Características no Soportadas: Se excluyen características como los built-ins de multiconjuntos de Tamarin, los emparejamientos bilineales y Diffie-Hellman con inverso. XOR se traduce como una aproximación de "mejor esfuerzo" fuera de las garantías de solidez debido a la falta de símbolos asociativos en ProVerif.

Contribuciones Clave

Traducción Sólida: Una traducción formal de Tamarin a ProVerif que asegura que cualquier propiedad verificada en ProVerif (dentro del fragmento fiel) también se cumple en el modelo original de Tamarin.
Nuevos Codificadores: Técnicas para codificar la semántica de reescritura de multiconjuntos (usando identificadores y restricciones) y para gestionar eventos simultáneos en un cálculo que asume un orden total.
Caracterización del Fragmento Lógico: Identificación del fragmento de lógica núcleo común (TSA-QBF) compartido por ambas herramientas, definiendo exactamente qué propiedades pueden traducirse fielmente.
Estudio Empírico a Gran Escala: Evaluación sobre 121 modelos de Tamarin que contienen 566 tareas de lemas, proporcionando el primer análisis comparativo a gran escala de estas herramientas sobre modelos semánticamente equivalentes.

Resultados

La evaluación se realizó sobre 121 modelos (566 tareas de lemas).

Cobertura de la Traducción: La traducción generó con éxito consultas para 562 de 566 tareas (99.3%).
Acuerdo: Entre las tareas de no-XOR con resultados definitivos de ambas herramientas, 246 de 247 pares coincidieron. El único desacuerdo fue marcado como una traducción de modelo incompleta.
Rendimiento:
- Velocidad: ProVerif fue más rápido en 334 de 362 casos comparables (92.3%). La mediana de la relación de tiempo de ejecución fue de 6.74× a favor de ProVerif.
- Memoria: ProVerif utilizó significativamente menos memoria, con una mediana de la relación de pico de memoria de 6.24× menor que Tamarin.
Estudio de Caso: En la corrección de Lowe para el protocolo Andrew Secure RPC, ProVerif fue 64.7× más rápido en cinco lemas que coincidían, siendo el lema de acuerdo inyectivo más complejo 129.6× más rápido.
Garantías de Solidez: La traducción es sólida para el fragmento fiel. Para las propiedades de exists-trace sin hechos de conocimiento del atacante, la traducción también es completa (si Tamarin encuentra un rastro, ProVerif encontrará uno).

Significado y Reivindicaciones

El artículo afirma proporcionar una base rigurosa para el análisis comparativo entre Tamarin y ProVerif. Al permitir la traducción de modelos de Tamarin a ProVerif, los autores demuestran:

Existe un fragmento de lógica núcleo común sustancial entre ambas herramientas.
Las ventajas de rendimiento de ProVerif (velocidad y eficiencia de memoria) pueden aprovecharse para los modelos de Tamarin sin sacrificar la solidez, siempre que el modelo se mantenga dentro del fragmento de traducción fiel.
La traducción sirve como un backend rápido para Tamarin, permitiendo a los usuarios verificar rápidamente propiedades de acuerdo no inyectivo e inyectivo.
El trabajo destaca las brechas semánticas (por ejemplo, el manejo de XOR, la semántica de multiconjuntos y la negación) y caracteriza precisamente dónde las traducciones son posibles frente a dónde son aproximaciones de "mejor esfuerzo" o imposibles.

Los autores enfatizan que, aunque la traducción no es completa para todas las características de Tamarin (específicamente excluyendo los built-ins de multiconjuntos y ciertos modelos de DH), cubre un extenso subconjunto de propiedades de seguridad prácticas, permitiendo estudios empíricos sistemáticos que antes eran inviables. Los resultados sugieren que, para muchos protocolos estándar, ProVerif puede servir como una alternativa o complemento altamente eficiente a Tamarin cuando se utiliza dentro de los límites del fragmento definido.