FerrousPath

Nivel 5 · Investigación· Lección 6 de 9 · 50 min

RustBelt: demostrar que el código unsafe es correcto

Corrección semántica de tipos, lógica de separación e Iris, la lógica de lifetimes, y cómo se verificaron por máquina las abstracciones unsafe de la biblioteca estándar.

La promesa central de Rust es condicional: el código seguro no puede causar comportamiento indefinido, siempre que el código unsafe de las bibliotecas que usa sea correcto. RustBelt (Jung, Jourdan, Krebbers y Dreyer, POPL 2018) es el trabajo que convirtió por primera vez esa promesa en un teorema con una demostración verificada por máquina, y que dio un significado preciso a «correcto» para el código unsafe.

La forma del problema

El camino clásico hacia la seguridad de tipos es sintáctico (Wright y Felleisen): mostrar que los términos bien tipados no se atascan (progreso) y que la reducción conserva el tipado (preservación). Eso demuestra la seguridad de todo programa que las reglas de tipado aceptan.

Pero Vec::push contiene escrituras a través de punteros crudos; Cell::set modifica a través de una referencia compartida; Mutex::lock entrega un &mut T a partir de un &Mutex<T>. Nada de eso se puede tipar con las reglas del código seguro. Una demostración sintáctica tiene que ignorar la biblioteca estándar o añadir al lenguaje cada biblioteca de ese tipo como una primitiva con sus propios axiomas, y entonces no dice nada sobre la próxima biblioteca que escriba alguien.

Lo que queremos es un teorema extensible:

Si toda biblioteca que usa unsafe cumple una condición de verificación, entonces cualquier programa compuesto por esas bibliotecas y por código seguro arbitrario es seguro.

Eso exige decir qué significa que el código sea seguro con independencia de cómo se tipó.

Tipado semántico

El enfoque semántico (las relaciones lógicas, en la tradición de Milner, Tait, Girard, Appel y McAllester, Ahmed) interpreta cada tipo como un predicado sobre el comportamiento:

  • El juicio sintáctico Γ ⊢ e : τ significa «e se puede derivar con las reglas de tipado».
  • El juicio semántico Γ ⊨ e : τ significa «e, ejecutado en cualquier entorno que cumpla la interpretación de Γ, es seguro y produce algo que cumple la interpretación de τ».

La demostración tiene tres partes:

  1. Teorema fundamental. Toda regla de tipado sintáctica es correcta para la interpretación semántica: Γ ⊢ e : τ implica Γ ⊨ e : τ. Se demuestra una vez, para el lenguaje.
  2. Demostraciones de las bibliotecas. Para cada biblioteca unsafe, se demuestra directamente que cada función habita semánticamente su tipo. Se demuestra una vez por biblioteca.
  3. Adecuación. ⊨ e : τ implica que e nunca se atasca.

Componlas: un programa es código seguro (cubierto por 1) que llama a bibliotecas (cubiertas por 2), así que está semánticamente bien tipado, así que es seguro (3). Una biblioteca unsafe nueva solo necesita una demostración nueva de la clase 2.

Toda la dificultad se traslada a una pregunta: ¿cuál es la interpretación de un tipo de Rust? Tiene que captar la propiedad, los préstamos, los lifetimes, la mutabilidad interior y la concurrencia. La lógica corriente no da para tanto.

Lógica de separación

La lógica de separación (Reynolds; O’Hearn; Ishtiaq y O’Hearn, hacia 2001–2002) es la lógica de Hoare con aserciones sobre la propiedad de fragmentos del heap:

  • ℓ ↦ v: «soy dueño de la posición ℓ, y contiene v». La propiedad es exclusiva.
  • P * Q: la conjunción separadora: los recursos pueden dividirse en dos partes disjuntas que cumplen P y Q.
  • P -* Q: la varita mágica: si además me dan recursos que cumplan P, puedo producir Q.
  • La regla del marco (frame rule): si {P} c {Q}, entonces {P * R} c {Q * R}. El código que no menciona R no puede afectarlo: razonamiento local.

Las aserciones son recursos: no se pueden duplicar libremente, y usar una la consume. Es una lógica afín, y el encaje con Rust es inmediato:

Rust Lógica de separación
Ser dueño de un Box<T> en ℓ ℓ ↦ v * ⟦T⟧(v)
Mover un valor Transferir la aserción
Dos &mut disjuntos P * Q
Una función que recibe &mut T no puede afectar a otros datos La regla del marco

La lógica de separación concurrente (O’Hearn; Brookes, 2004) lo extiende a los hilos: los recursos disjuntos van a hilos distintos; los recursos compartidos los gobiernan los invariantes.

Iris

RustBelt está construido en Iris (Jung, Krebbers, Jourdan, Bizjak, Birkedal, Dreyer y otros), un marco de lógica de separación concurrente de orden superior mecanizado en Rocq (antes Coq). Las características que importan aquí:

  • Estado fantasma definido por el usuario a partir de álgebras de recursos (monoides conmutativos parciales): inventa la contabilidad lógica que necesite la demostración —permisos fraccionarios, tokens, contadores, pares autoritativo/fragmento— e Iris proporciona reglas correctas para ella.
  • Invariantes [P]: una aserción que se cumple en cada paso de la ejecución y que cualquier hilo puede abrir durante un paso atómico.
  • De orden superior e impredicativa: los invariantes pueden mencionar invariantes y código almacenado. Eso exige la indexación por pasos (step-indexing), visible como la modalidad later ▷.
  • Aserciones persistentes (□ P): conocimiento duplicable, en contraposición a los recursos exclusivos. Los tipos Copy y las referencias compartidas se interpretan con ellas.
  • Un modo de demostración en Rocq que hace prácticas las demostraciones interactivas en lógica de separación.

λRust

El lenguaje formal es λRust, un cálculo núcleo parecido a MIR en estilo de paso de continuaciones: memoria explícita con aritmética de punteros, comienzo y fin de lifetimes explícitos y detección de carreras de datos incorporada en la semántica operacional (una carrera hace que el programa se atasque, así que «no atascado» implica «sin carreras de datos»). Su sistema de tipos tiene propiedad, las dos clases de referencia, inclusión de lifetimes y tipos recursivos y suma. La traducción del Rust de superficie a λRust se hace a mano y queda fuera de la demostración mecanizada.

La interpretación de los tipos

Cada tipo τ se interpreta con dos predicados:

  • un predicado de propiedad ⟦τ⟧.own(tid, v̄): qué significa que el hilo tid sea dueño de un valor de tipo τ representado por los bytes v̄;
  • un predicado de compartición ⟦τ⟧.shr(κ, tid, ℓ): qué significa tener una referencia compartida a un τ en la posición ℓ durante el lifetime κ.

Para los tipos sencillos, el predicado de compartición se deriva del de propiedad («la posición contiene, en modo de solo lectura, algo que cumple own»). El segundo predicado existe por la mutabilidad interior: lo que te permite hacer una referencia compartida a un Cell<T> no está determinado por lo que significa ser dueño de un Cell<T>. Cada tipo elige su propio protocolo de compartición:

Tipo Predicado de compartición, de manera informal
i32, Box<T> Acceso de solo lectura a memoria que contiene un valor con dueño, durante κ
Cell<T> Un invariante no atómico, ligado al hilo tid, que concede la propiedad completa a quien lo abra; de ahí que Cell no sea Sync
Mutex<T> Un invariante atómico: o la bandera del cerrojo está activada, o está desactivada y el invariante contiene el préstamo del contenido
RefCell<T> Un invariante que contiene el contador de préstamos y el estado fantasma que lo enlaza con los tokens Ref/RefMut pendientes
Rc<T> Estado fantasma que sigue los contadores fuerte y débil, ligado al hilo

Send y Sync tienen definiciones semánticas nítidas: τ es Send si own no depende del identificador de hilo; τ es Sync si shr no depende de él.

La lógica de lifetimes

El corazón técnico de RustBelt es una pieza nueva de lógica de separación para los préstamos. Sus conectivas clave:

  • [κ]_q: un token de lifetime: la fracción q del conocimiento de que el lifetime κ sigue vivo. Los tokens se dividen y se fusionan como los permisos fraccionarios.
  • [†κ]: el hecho persistente de que κ ha terminado.
  • &κ P: un préstamo completo: la propiedad de P mientras dure κ.

y sus reglas clave, de manera informal:

Prestar:     ▷P   ⇛   &κ P  *  ([†κ] ⇛ ▷P)
             divide P en un préstamo y una «herencia» que devuelve P cuando κ ha terminado

Acceder:     &κ P * [κ]_q   ⇛   ▷P  *  (▷P ⇛ &κ P * [κ]_q)
             con un token de vivacidad puedes abrir el préstamo; debes devolver P para recuperar el token

Terminar:    [κ]_1   ⇛   [†κ]
             terminar un lifetime necesita el token ENTERO, así que nadie puede estar en mitad de un acceso

Léelas pensando en Rust: crear &'a mut x divide la propiedad de x en la referencia (el préstamo) y el derecho del dueño a recuperar x después (la herencia). Usar la referencia exige una prueba de que 'a está vivo. Un lifetime no puede terminar mientras haya algún acceso en curso, porque terminar necesita todas las fracciones del token.

Un &'a mut T se interpreta entonces como un préstamo completo del predicado de propiedad de T; un &'a T, como el predicado de compartición en 'a. La inclusión de lifetimes κ ⊑ κ' se define en la lógica, y el reborrowing, la división de un préstamo de un par en dos préstamos y cosas parecidas se derivan como lemas.

Qué se demostró

El desarrollo mecanizado demuestra el teorema fundamental para el sistema de tipos de λRust y la corrección de las versiones semánticas de tipos centrales de la biblioteca, entre ellos Cell, RefCell, Rc, Arc, Mutex, RwLock, mem::swap, thread::spawn, rayon::join y take_mut.

El esfuerzo no fue meramente confirmatorio. Encontró un error real: MutexGuard<'_, T> era Sync siempre que T: Send, cuando debe exigir T: Sync. El modelo semántico hizo imposible demostrar el error, y la biblioteca estándar se corrigió.

Qué no demuestra

Ser exacto con los límites forma parte de investigar:

  • Trata de λRust, no de Rust: la traducción es manual, y el sistema de traits, el deshacer la pila y muchas características del lenguaje no están modelados.
  • El modelo de memoria original era secuencialmente consistente y no tenía modelo de aliasing.
  • Demuestra la seguridad (la ausencia de comportamiento indefinido), no la corrección funcional.
  • Verifica las bibliotecas tal como se modelan en λRust, no su código fuente real.

Cada limitación se convirtió en un programa de investigación:

Trabajo Amplía RustBelt con
RustBelt Meets Relaxed Memory (Dang, Jourdan, Kaiser, Dreyer, POPL 2020) Un modelo de memoria débil (ORC11); volvió a verificar Arc con él y encontró que Arc::get_mut necesitaba un load con Acquire en lugar de Relaxed
Stacked Borrows (POPL 2020), Tree Borrows (PLDI 2025) Modelos de aliasing, con demostraciones de que las optimizaciones son correctas
GhostCell (Yanovski et al., ICFP 2021) Una API segura nueva para la mutación compartida, diseñada junto con su demostración de corrección
RustHornBelt (Matsushita et al., PLDI 2022) Corrección funcional: los tipos se interpretan con especificaciones basadas en profecías, lo que justifica la verificación al estilo de RustHorn incluso para bibliotecas unsafe
RefinedRust (Gäher et al., PLDI 2024) Verificación fundacional de código fuente real de Rust, seguro y unsafe, con tipos de refinamiento que producen demostraciones en Rocq
Aeneas, Creusot, Verus, Prusti Verificadores prácticos que se apoyan en la disciplina de propiedad: la próxima lección

Por qué le importa esto a quien programa

RustBelt da el vocabulario para razonar sobre el código unsafe que este curso ha usado desde el nivel 3:

  • El invariante de seguridad de un tipo es su predicado de propiedad. Su comportamiento detrás de un & es su predicado de compartición. Cuando diseñas una abstracción unsafe estás eligiéndolos, normalmente de forma implícita. Escribirlos, aunque sea de manera informal, es la forma más eficaz de encontrar errores de corrección.
  • «Correcto» (sound) significa: toda función pública habita semánticamente su firma. La comprobación es modular, por biblioteca, y nunca exige conocer a los clientes.
  • La razón de que el código unsafe deba juzgarse junto con su módulo es que los invariantes de los campos privados forman parte del predicado de propiedad, y cualquier código que pueda tocarlos forma parte de la demostración.

Lista de lecturas

  1. Jung, Jourdan, Krebbers, Dreyer, «RustBelt: Securing the Foundations of the Rust Programming Language» (POPL 2018).
  2. Jung, Jourdan, Krebbers, Dreyer, «Safe Systems Programming in Rust» (Communications of the ACM, 2021): la visión general accesible. Empieza por aquí.
  3. Jung, Understanding and Evolving the Rust Programming Language (tesis doctoral, 2020): la exposición completa.
  4. Jung et al., «Iris from the ground up» (Journal of Functional Programming, 2018).
  5. Reynolds, «Separation Logic: A Logic for Shared Mutable Data Structures» (LICS 2002); O’Hearn, «Separation Logic» (CACM 2019).
  6. Birkedal y Bizjak, Lecture Notes on Iris: una introducción en forma de curso.
  7. Ahmed, «Step-Indexed Syntactic Logical Relations for Recursive and Quantified Types» (ESOP 2006).
  8. Los artículos posteriores de la tabla de arriba.

Ejercicios

  1. Escribe, en prosa, el predicado de propiedad de Vec<T> en términos de un puntero, una longitud, una capacidad, aserciones points-to y ⟦T⟧.own. Compáralo con los invariantes enumerados en el proyecto final del nivel 4.
  2. Enuncia el predicado de compartición que elegirías para un tipo AtomicCounter que envuelve un AtomicU64. ¿Es el tipo Sync según la definición semántica?
  3. Usando las tres reglas de la lógica de lifetimes, explica paso a paso por qué se acepta esto: crear &mut x, escribir a través de él, dejar que el lifetime termine, leer x.
  4. Explica semánticamente por qué Cell<T> es Send (cuando T lo es) pero no Sync.
  5. Lee la sección 2 del artículo de CACM y resume con tus palabras el ejemplo de Mutex.
  6. Sigue los primeros capítulos de las notas de Iris en Rocq y verifica un contador con un cerrojo parecido a Mutex.

Comprueba lo que has entendido

Elige una respuesta para ver la explicación.

  1. 1.¿Por qué una demostración sintáctica de progreso y preservación no puede establecer la afirmación de seguridad de Rust?

  2. 2.En lógica de separación, ¿qué afirma P * Q?

  3. 3.En el marco de RustBelt, ¿qué debe demostrar quien escribe una biblioteca para mostrar que una abstracción unsafe es correcta?

Términos clave de esta lección

¿Has terminado la lección y los ejercicios?