Nivel 5 · Investigación· Lección 7 de 9 · 45 min
Verificación formal de programas en Rust
De Miri y el model checking a los verificadores deductivos — Kani, Creusot, Prusti, Verus, Aeneas, Flux — y por qué la propiedad hace a Rust inusualmente verificable.
El sistema de tipos demuestra la seguridad de memoria. No demuestra que tu ordenación ordene, que tu analizador nunca entre en pánico ni que tu protocolo de consenso nunca pierda datos. La verificación formal demuestra propiedades como esas, para todas las entradas y no solo para las que una prueba llegó a probar. Rust se ha convertido en uno de los objetivos más activos de la investigación en verificación, y por una razón de principio.
Por qué Rust es inusualmente verificable
Verificar programas imperativos es difícil sobre todo por el aliasing. En C, después de *p = 1; *q = 2; no puedes concluir que *p == 1 sin saber que p y q son distintos. Toda especificación tiene que decir lo que una función no modifica (el problema del marco), y los verificadores necesitan lógica de separación o marcos dinámicos para poder con ello.
El sistema de tipos del Rust seguro ya ha hecho ese trabajo. &mut T es único; &T es inmutable (dejando aparte la mutabilidad interior). Así que:
- Una función que recibe
&mut ay&mut bno puede tenerlos con aliasing: no hacen falta condiciones de marco. - Un valor detrás de un
&Tno puede cambiar mientras tengas la referencia. - La propiedad hace del heap un árbol: sobre un
Vec<Box<T>>con dueño se puede razonar como sobre una secuencia matemática de valores.
Varias herramientas lo aprovechan para traducir el Rust seguro a condiciones de verificación puramente funcionales, sin ningún modelo del heap. El borrow checker hace de demostración gratuita y automática de los lemas de no interferencia que dominan la verificación de C.
El espectro de garantías
| Técnica | Demuestra | Esfuerzo | Herramientas |
|---|---|---|---|
| Pruebas | Los casos que escribiste | bajo | cargo test |
| Pruebas de propiedades, fuzzing | Muchos casos aleatorios o guiados por cobertura | bajo | proptest, cargo fuzz |
| Detección dinámica de UB | Que no hay UB en los caminos ejecutados | bajo | Miri, sanitizers |
| Model checking de concurrencia | Todos los entrelazados de pruebas pequeñas | bajo–medio | loom, shuttle |
| Model checking acotado | Todas las entradas, dentro de unas cotas | medio | Kani |
| Verificación deductiva | Todas las entradas, sin cotas, contra una especificación | alto | Creusot, Prusti, Verus, Flux |
| Traducción a un asistente de demostración | Todo lo que puedas demostrar de forma interactiva | muy alto | Aeneas, hax, RefinedRust |
Baja solo hasta donde lo justifique el riesgo. La mayor parte del código merece fuzzing; una primitiva criptográfica o el código de las tablas de páginas de un kernel pueden merecer una demostración.
Kani: model checking acotado
Kani (desarrollado en AWS) compila el MIR al lenguaje de entrada de CBMC, un model checker con precisión de bits respaldado por resolutores SAT/SMT. Escribes un arnés de demostración parecido a una prueba, pero sobre entradas no deterministas:
fn midpoint_buggy(a: u32, b: u32) -> u32 {
(a + b) / 2 // desborda cuando a + b supera u32::MAX
}
fn midpoint(a: u32, b: u32) -> u32 {
a / 2 + b / 2 + (a & b & 1)
}
#[cfg(kani)]
mod proofs {
use super::*;
#[kani::proof]
fn midpoint_is_between() {
let a: u32 = kani::any(); // todos los u32 posibles, simbólicamente
let b: u32 = kani::any();
let m = midpoint(a, b);
assert!(m >= a.min(b) && m <= a.max(b));
}
#[kani::proof]
fn buggy_version_fails() {
let (a, b): (u32, u32) = (kani::any(), kani::any());
let _ = midpoint_buggy(a, b); // Kani informa: desbordamiento aritmético, con un contraejemplo
}
}
fn main() {
println!("{} {}", midpoint(u32::MAX, u32::MAX - 2), midpoint(3, 4));
}
cargo kani comprueba, para los 2⁶⁴ pares de entrada: que no hay pánicos, ni desbordamientos, ni accesos fuera de los límites, ni aserciones fallidas y, para el código unsafe, una serie de comportamientos indefinidos. Si falla, produce un contraejemplo concreto.
Puntos fuertes: casi ninguna carga de anotaciones; precisión de bits; trata unsafe y los punteros crudos. Límites: los bucles y la recursión se desenrollan hasta una cota (#[kani::unwind(n)]), así que las demostraciones sobre datos sin cota necesitan contratos de bucle o de función; el tiempo del resolutor crece deprisa con el tamaño de los datos.
Kani es la herramienta principal del esfuerzo verify-rust-std, iniciado en 2024 por AWS con la Rust Foundation, para verificar la seguridad del código unsafe de la biblioteca estándar mediante un conjunto de retos abiertos.
Verificación deductiva
Los verificadores deductivos comprueban el código contra contratos: precondiciones (requires), postcondiciones (ensures), invariantes de bucle y medidas de terminación (decreases / variantes). La herramienta genera las condiciones de verificación y las resuelve con resolutores SMT.
Creusot
Creusot (Denis, Jourdan y Marché, ICFEM 2022) traduce Rust a Why3 y sus resolutores. Las especificaciones se escriben en Pearlite, una lógica que se parece a Rust:
// Sintaxis de Creusot: la comprueba `cargo creusot`, no rustc por sí solo.
#[requires(n@ <= 1000)]
#[ensures(result@ == n@ * (n@ + 1) / 2)]
pub fn sum_to(n: u32) -> u32 {
let mut total = 0;
let mut i = 0;
#[invariant(i@ <= n@)]
#[invariant(total@ == i@ * (i@ + 1) / 2)]
while i < n {
i += 1;
total += i;
}
total
}
x@ denota el modelo lógico de x: un entero matemático sin cota para un u32, una secuencia matemática para un Vec.
La idea distintiva de Creusot, tomada de RustHorn (Matsushita, Tsukada y Kobayashi, ESOP 2020), es su tratamiento de los préstamos mutables mediante profecías. Un &mut T se modela como un par: su valor actual *x y su valor final ^x, el valor que tendrá el referente cuando termine el préstamo. Ese valor final todavía no se conoce; se profetiza.
#[ensures(^x == *x + 1)] // «el valor final del préstamo es el valor inicial más uno»
pub fn increment(x: &mut i64) {
*x += 1;
}
Cuando se crea un préstamo, a quien presta se le dice «cuando termine el préstamo, tu valor será igual a ^b». Cuando expira, la profecía se resuelve. Ni heap ni lógica de separación: solo lógica de primer orden sobre valores. Su corrección, incluso en presencia de bibliotecas unsafe, la estableció RustHornBelt sobre RustBelt.
Prusti
Prusti (Astrauskas, Müller, Poli y Summers, OOPSLA 2019), de la ETH de Zúrich, traduce Rust a la infraestructura de verificación Viper, que se basa en marcos dinámicos implícitos (una lógica de permisos emparentada con la lógica de separación). Los tipos de Rust se convierten automáticamente en las anotaciones de permisos que necesita Viper: el usuario solo escribe especificaciones funcionales. Los préstamos que expiran se modelan con compromisos (pledges, after_expiry) en lugar de con profecías.
Verus
Verus (Lattuada et al., OOPSLA 2023) es un verificador basado en SMT orientado al código de sistemas, desarrollado en CMU, VMware Research, Microsoft Research y otros centros. El código se escribe en tres modos dentro de una macro verus!:
exec: Rust normal, que se compila;spec: funciones matemáticas puras que se usan en las especificaciones;proof: lemas: código que se comprueba y después se borra.
// Sintaxis de Verus: la comprueba la herramienta `verus`.
verus! {
spec fn triangle(n: nat) -> nat
decreases n
{
if n == 0 { 0 } else { n + triangle((n - 1) as nat) }
}
fn sum_to(n: u32) -> (total: u32)
requires triangle(n as nat) <= u32::MAX,
ensures total == triangle(n as nat),
{
let mut total: u32 = 0;
let mut i: u32 = 0;
while i < n
invariant
i <= n,
total == triangle(i as nat),
triangle(n as nat) <= u32::MAX,
decreases n - i,
{
i = i + 1;
assert(triangle(i as nat) <= triangle(n as nat)) by { triangle_monotonic(i as nat, n as nat); }
total = total + i;
}
total
}
proof fn triangle_monotonic(a: nat, b: nat)
requires a <= b,
ensures triangle(a) <= triangle(b),
decreases b,
{
if a < b { triangle_monotonic(a, (b - 1) as nat); }
}
} // verus!
El movimiento notable de Verus es reutilizar el comprobador de tipos lineales de Rust sobre el código fantasma: los valores fantasma rastreados (tracked) tienen dueño, se prestan y se mueven como los reales, pero se borran en tiempo de compilación. Eso da al usuario una lógica de separación programable —permisos fantasma sobre la memoria (PointsTo), tokens fantasma para protocolos concurrentes— que comprueba el borrow checker y no una lógica aparte. Se usa para verificar tablas de páginas, sistemas de almacenamiento, asignadores de memoria y protocolos distribuidos.
Flux
Flux (Lehmann et al., PLDI 2023) añade tipos de refinamiento a Rust —i32{v: v > 0}, Vec<T>[n] indexado por su longitud— con inferencia líquida de la mayoría de las anotaciones. Comprueba propiedades como la seguridad de los límites con muchas menos anotaciones que un verificador deductivo completo, ligando los refinamientos a la propiedad: las actualizaciones fuertes a través de &mut son correctas porque la referencia es única.
Traducción a asistentes de demostración
Cuando la automatización con SMT no basta —matemáticas profundas, o la exigencia de una base de confianza pequeña—, traduce el programa a un asistente de demostración.
Aeneas (Ho y Protzenko, ICFP 2022) traduce el Rust seguro, a través de un lenguaje intermedio (LLBC) y una semántica simbólica de los préstamos, a un programa funcional puro en Lean, Rocq, F* o HOL4. Una función que recibe un &mut T se convierte en una función que devuelve el valor actualizado; las funciones que devuelven un préstamo mutable producen una «función hacia atrás» que describe cómo se propagan las actualizaciones a quien prestó. Después demuestras teoremas sobre código funcional corriente. Se usa en criptografía verificada y se está aplicando a partes de sistemas reales.
hax extrae un subconjunto funcional de Rust a F*, Rocq y ProVerif, sobre todo para código criptográfico y de protocolos.
RefinedRust (Gäher et al., PLDI 2024) produce demostraciones fundacionales en Rocq/Iris tanto para el Rust seguro como para el unsafe: las garantías más fuertes, al coste más alto.
Cómo elegir
| Si necesitas… | Considera |
|---|---|
| «Esta función unsafe no tiene UB para ninguna entrada hasta el tamaño N» | Kani |
| «Esta función nunca entra en pánico ni desborda» | Kani; Flux; Creusot/Verus con postcondiciones triviales |
| Corrección funcional de código algorítmico, en su mayoría seguro | Creusot, Prusti |
| Código de sistemas verificado, con estado fantasma propio y concurrencia | Verus |
| Demostraciones que necesitan un asistente de demostración; criptografía verificada | Aeneas, hax |
Demostraciones fundacionales que cubran unsafe |
RefinedRust, demostraciones en Iris al estilo de RustBelt |
Todas ellas verifican respecto a una especificación. Una especificación incorrecta o débil da una demostración que no vale nada; escribir la especificación es el verdadero trabajo intelectual, y a menudo es donde se encuentran los errores.
Base de confianza
Todo resultado descansa en cosas que no se demostraron: la codificación que hace la herramienta de la semántica de Rust; el resolutor SMT; las especificaciones de las funciones de biblioteca sin verificar a las que llama el código; el compilador; y, para el código unsafe, los detalles aún sin decidir de la semántica operacional de Rust. Sé explícito con esta lista en todo lo que publiques. Una especificación formal de Rust (próxima lección) la reduciría.
Lista de lecturas
- Matsushita, Tsukada, Kobayashi, «RustHorn: CHC-based Verification for Rust Programs» (ESOP 2020).
- Denis, Jourdan, Marché, «Creusot: A Foundry for the Deductive Verification of Rust Programs» (ICFEM 2022).
- Astrauskas et al., «Leveraging Rust Types for Modular Specification and Verification» (OOPSLA 2019).
- Lattuada et al., «Verus: Verifying Rust Programs using Linear Ghost Types» (OOPSLA 2023).
- Ho y Protzenko, «Aeneas: Rust Verification by Functional Translation» (ICFP 2022).
- Lehmann et al., «Flux: Liquid Types for Rust» (PLDI 2023).
- VanHattum et al., «Verifying Dynamic Trait Objects in Rust» (ICSE-SEIP 2022): Kani.
- Matsushita et al., «RustHornBelt» (PLDI 2022).
- Los tutoriales de Kani, Verus y Creusot: todos son prácticos y están al día.
Ejercicios
- Instala Kani y verifica
midpoint. Después escribe un arnés para una búsqueda binaria sobre un[u32; 8]que compruebe que un índice encontrado contiene la clave. - En Verus o en Creusot, verifica
fn max(a: &[i32]) -> i32con una postcondición que afirme tanto que el resultado está en el slice como que es mayor o igual que todos los elementos. - Especifica (sin demostrarla todavía) una función
sort. Tu postcondición necesita dos partes; la mayoría de la gente olvida una. ¿Cuál? - Usando el modelo de profecías, escribe la especificación de
fn swap<T>(a: &mut T, b: &mut T). - Toma el
MyVecdel nivel 4 y escribe arneses de Kani para secuencias depush/popcon una cota pequeña. ¿Qué invariante enunciarías como contrato de función? - Lee el tratamiento que hace el artículo de Aeneas de
fn choose<'a>(b: bool, x: &'a mut T, y: &'a mut T) -> &'a mut Ty explica la función hacia atrás.
Comprueba lo que has entendido
Elige una respuesta para ver la explicación.
1.¿Por qué es más fácil verificar Rust seguro que verificar C?
2.¿Qué establece un model checker acotado como Kani?
3.¿Qué problema resuelven las variables de profecía en Creusot y RustHorn?