Nueve reglas para validar formalmente algoritmos de Rust con Dafny (Parte 2)

Nueve reglas para validar formalmente algoritmos de Rust con Dafny (Segunda parte)

Lecciones de verificar la caja range-set-blaze

Por Carl M. Kadie y Divyanshu Ranjan

Este es la segunda parte de un artículo que verifica formalmente un algoritmo Rust usando Dafny. Observamos las reglas 7 a 9:

• 7. Porta tu Algoritmo Real a Dafny.
• 8. Valida la Versión Dafny de tu Algoritmo.
• 9. Reformula tu Validación para Mejorar la Confianza.

Mira Parte 1 para las reglas 1 a 6:

• ¡Oh, ¿Querías decir Gestionar el cambio?
• El Lado No Contado de RAG Abordando sus Desafíos en Búsquedas Específicas de Dominio
• Comprendiendo la retención con Gradio

1. No Aprendas Dafny.
2. Aprende Dafny.
3. Define los Conceptos Básicos de tu Algoritmo.
4. Especifica tu Algoritmo.
5. Obtén Ayuda de la Comunidad de Dafny.
6. Valida un Algoritmo Diferente y más Sencillo.

Las reglas son informadas por nuestra experiencia validando un algoritmo de range-set-blaze, una caja Rust para manipular conjuntos de enteros “agrumpados”.

Recuerda que la Regla 6, de Parte 1, muestra que podemos verificar un algoritmo para InternalAdd, pero no es el algoritmo usado en la caja Rust. Nos enfocamos en ese algoritmo a continuación.

Regla 7: Porta tu Algoritmo Real a Dafny.

Aquí está la función Rust de interés con cierto código excluido por ahora:

// https://stackoverflow.com/questions/49599833/how-to-find-next-smaller-key-in-btreemap-btreeset// https://stackoverflow.com/questions/35663342/how-to-modify-partially-remove-a-range-from-a-btreemapfn internal_add(&mut self, range: RangeInclusive<T>) {    let (start, end) = range.clone().into_inner();    assert!(        end <= T::safe_max_value(),        "end must be <= T::safe_max_value()"    );    if end < start {        return;    }    //... código continua ...}

Y aquí está el comienzo del port de Dafny:

method InternalAdd(xs: seq<NeIntRange>, range: IntRange) returns (r: seq<NeIntRange>)  requires ValidSeq(xs)  ensures ValidSeq(r)  ensures SeqToSet(r) == SeqToSet(xs) + RangeToSet(range){  var (start, end) := range;  if end < start {    r := xs;    return;  } //... código continua ...}

Algunos puntos de posible interés:

• El código Rust utiliza self y encapsulación similar a la orientación a objetos. Dafny admite este estilo de codificación, pero — por simplicidad — no lo uso aquí. Específicamente, el código Rust muta a self. Elegí escribir el código Dafny de forma más funcional, toma una secuencia inmutable y devuelve una nueva secuencia inmutable.
• El código Rust administra la memoria con el chequeador de préstamos. Esto lleva a expresiones como range.clone(). Dafny administra la memoria con un recolector de basura. En ambos casos, la seguridad de la memoria será atendida. Por lo tanto, la ignoramos en esta validación.
• El código Rust es genérico en T que defino en otro lugar para incluir todos los tipos de enteros estándar en Rust, por ejemplo, u8, isize, i128. El código Dafny está definido en int, un solo tipo que representa enteros de tamaño arbitrario. Esto significa que este port de Dafny no necesita verificar desbordamientos de enteros. [Ve un artículo anterior para probar formalmente la seguridad de desbordamientos con el verificador Rust Kani.]
• El código Rust incluye una aserción de tiempo de ejecución assert! que es necesaria en Rust para prohibir un caso especial: insertar u128::max_value en una RangeSetBlaze<u128>. Debido a que Dafny utiliza int, que tiene un tamaño arbitrario, ignora este caso especial.

Nota aparte: ¿Cuál es la longitud del rango inclusivo Rust 0..=u128::max_value? La respuesta es u128::max_value+1, un valor demasiado grande para representar con cualquier tipo de entero estándar en Rust. La librería range-set-blaze limita los rangos a 0..=u128::max_value-1, de manera que las longitudes puedan ser representadas con un u128.

A continuación, vamos a considerar el resto del algoritmo internal_add. Recordemos que tenemos una lista de rangos disjuntos ordenados y un nuevo rango no vacío que queremos insertar. Por ejemplo:

El algoritmo nos pide encontrar cuál (si hay alguno) rango existente está antes (o en) el inicio del nuevo rango. Llamemos a esto el rango “antes”. Luego consideramos cuatro casos:

• Caso 1: El nuevo rango no toca su rango anterior, por lo que insertamos el nuevo rango mientras comprobamos si toca algún otro rango.
• Caso 2: El nuevo rango toca el rango anterior y se extiende más allá de él, por lo que extendemos el final del rango anterior mientras comprobamos si toca algún otro rango. (Cuando no se tocan otros rangos, esto será muy rápido.)

• Caso 3: El nuevo rango toca el rango anterior pero no se extiende más allá de él, así que no hacemos nada. (Esto siempre será muy, muy rápido.)

• Caso 4: El nuevo rango comienza antes que cualquier rango, así que lo agregamos mientras comprobamos si toca algún otro rango.

Aquí está el algoritmo en Rust:

// código continuado ...// FUTURO: sería agradable que BTreeMap tuviera una función partition_point que devuelva dos iteradores
    let mut before = self.btree_map.range_mut(..=start).rev();
    if let Some((start_before, end_before)) = before.next() {
        // Debe comprobarse esto en dos partes para evitar desbordamientos
        if match (*end_before).checked_add(&T::one()) {
            Some(end_before_succ) => end_before_succ < start,
            None => false,
        } {
            self.internal_add2(&range);
        } else if *end_before < end {
            self.len += T::safe_len(&(*end_before..=end - T::one()));
            *end_before = end;
            let start_before = *start_before;
            self.delete_extra(&(start_before..=end));
        } else {
            // completamente contenido, así que no hacemos nada
        }
    } else {
        self.internal_add2(&range);
    }

Y aquí está en Dafny:

// código continuado ...  var beforeHi := IndexAtOrBeforePlusOne(xs, start);  if beforeHi > 0 { // no va al principio    var (startBefore, endBefore) := xs[beforeHi-1];    if endBefore+1 < start {      r := InternalAdd2(xs, range);    } else if endBefore < end {      r := xs[..beforeHi-1] + [(startBefore, end)] + xs[beforeHi..];      assume exists i: nat :: i < |r| && r[i] == (startBefore,end) && ValidSeq(r[..i+1]) && ValidSeq(r[i+1..]);      r := DeleteExtra(r, (startBefore,end));    } else{      r := xs;    }  }  else // va al principio  {    r := InternalAdd2(xs, range);  }

Algunos puntos de posible interés:

• El código Rust manipula un BTreeMap mediante claves y valores. El código Dafny manipula una seq ordenada con índices (de acceso aleatorio). Hice que las operaciones en Dafny reflejen las operaciones en Rust, aunque esto hace que el código en Dafny sea menos natural.
• El código Rust también actualiza self.len, el número de enteros individuales en RangeSetBlaze. El código Dafny ignora esto. (Actualizar len es una característica que se podría agregar al código Dafny en el futuro.)
• Como antes, la versión en Rust incluye código para evitar desbordamientos que Dafny ignora.

Continué la portabilidad escribiendo una versión en Dafny de internal_add2 y delete_extra, las dos funciones que llama internal_add. Terminé la portabilidad escribiendo los métodos que estas dos funciones llaman, etc. El puerto completo tiene aproximadamente 185 líneas de código. Puedes verlo aquí.

No se valida. Trabajaremos en la validación a continuación.

Regla 8: Valida la Versión de Dafny de tu Algoritmo.

En este paso, agregarás indicaciones de validación a tu código, por ejemplo, en forma de declaraciones assert. Dafny utiliza estas indicaciones para intentar validar tu código. Como principiante en Dafny, encontré que agregar indicaciones era más difícil que programar. En parte, porque no sabía cuándo (o si) Dafny estaría satisfecho y podría detenerme.

Sin embargo, aprendí cómo debería comenzar. Por ejemplo, el código anterior para InternalAdd produce dos errores de verificación. En primer lugar, el verificador de Dafny informa que una de las ensures puede no cumplirse:

Esta postcondición podría no cumplirse: SeqToSet(r) == SeqToSet(xs) + RangeToSet(range)

Nota: “Postcondición” corresponde a ensures. “Precondición” corresponde a requires.

En segundo lugar, el verificador de Dafny se queja de que no se puede demostrar una precondición (que es uno de los requires) para DeleteExtra.

Nos centraremos primero en el primer problema agregando un assert al final del método. Lo escribimos para que refleje el ensures.

// ... agregando esto como la última línea en InternalAdd
assert SeqToSet(r) == SeqToSet(xs) + RangeToSet(range);

Ignoraremos explícitamente el problema de DeleteExtra, por ahora, con un assume.

// ...      assume exists i: nat :: i < |r| && r[i] == (startBefore,end) && ValidSeq(r[..i+1]) && ValidSeq(r[i+1..]);      r := DeleteExtra(r, (startBefore,end));//...

Ahora el validador de Dafny solo se queja de nuestro nuevo assert final. Dice “la afirmación puede no cumplirse”.

Recuerda que el código de InternalAdd usa instrucciones anidadas if para dividir su trabajo en cinco casos. A continuación, moveremos nuestro assert desde el final del método hasta el final de cada caso. Busca las líneas que terminan con un comentario // case en el resultado:

method InternalAdd(xs: seq<NeIntRange>, range: IntRange) returns (r: seq<NeIntRange>)  requires ValidSeq(xs)  ensures ValidSeq(r)  ensures SeqToSet(r) == SeqToSet(xs) + RangeToSet(range){  var (start, end) := range;  if end < start {    r := xs;    assert SeqToSet(r) == SeqToSet(xs) + RangeToSet(range); // caso 0 - válido    return;  }  var beforeHi := IndexAtOrBeforePlusOne(xs, start);  if beforeHi > 0 { // no va al principio    var (startBefore, endBefore) := xs[beforeHi-1];    if endBefore+1 < start {      r := InternalAdd2(xs, range);      assert SeqToSet(r) == SeqToSet(xs) + RangeToSet(range); // caso 1 - válido    } else if endBefore < end {      r := xs[..beforeHi-1] + [(startBefore, end)] + xs[beforeHi..];      assume exists i: nat :: i < |r| && r[i] == (startBefore,end) && ValidSeq(r[..i+1]) && ValidSeq(r[i+1..]);      r := DeleteExtra(r, (startBefore,end));      assert SeqToSet(r) == SeqToSet(xs) + RangeToSet(range); // caso 2 - falla    } else{      r := xs;      assert SeqToSet(r) == SeqToSet(xs) + RangeToSet(range); // caso 3 - falla    }  }  else // va al principio  {    r := InternalAdd2(xs, range);    assert SeqToSet(r) == SeqToSet(xs) + RangeToSet(range); // caso 4 - válido  }}

Dafny ahora nos dice que los casos 0, 1 y 4 son válidos. El caso 2 falla (y contiene ese assume que eventualmente eliminaremos). Por ahora, sin embargo, trabajemos en el caso 3.

Recordemos de la Regla 7 de este artículo, que el caso 3 es cuando agregamos un nuevo rango (rojo) que está completamente cubierto por un rango existente (el rango “antes” azul), por lo que el código no necesita hacer nada.

Entonces, pensando lógicamente, ¿qué sabemos? Sabemos que los enteros cubiertos por el rango “antes” son un superset de los enteros cubiertos por el nuevo rango. También sabemos que el rango “antes” es parte de nuestra lista original de rangos ordenados y disjuntos (los rangos azules). Añadiremos estas dos pistas a nuestro código a través de afirmaciones de assert:

Dafny acepta que estas dos pistas son verdaderas (marcas de verificación verdes), pero aún no acepta la afirmación de interés (marca roja).

Parece que necesitamos una pista más. Específicamente, necesitamos convencer a Dafny de que los enteros cubiertos por el rango “antes” son un subconjunto de los enteros cubiertos por la lista de todos los rangos ordenados y disjuntos. Intuitivamente, esto es verdadero porque el rango “antes” es uno de los rangos de la lista.

Escribimos esta pista como un lema sin cuerpo. Dafny lo acepta.

Nota: ¿Por qué Dafny acepta este lema sin nada en su cuerpo? No lo sé y no tengo una buena intuición. Solo funcionó. Si no lo hubiera hecho, habría intentado agregar asertos en su cuerpo.

Usando el lema, ahora el caso 3 es válido:

Esto significa que hemos validado los casos 0, 1, 3 y 4. Luego pasaríamos al caso 2. Además, algunos de los métodos mencionados, por ejemplo, DeleteExtra, aún no se validan y tendríamos que trabajar en ellos. [Puedes ver el código hasta este punto, aquí.]

Para consejos generales sobre depuración de verificación, consulta esta sección de la Guía del Usuario de Dafny. También recomiendo esta respuesta de Stack Overflow y minitutorial del Prof. James Wilcox.

En general, la idea es dividir la tarea de validar tu algoritmo en muchas tareas de validación más pequeñas. Encontré esto más difícil que programar, pero no demasiado difícil y aún divertido.

Terminé agregando alrededor de 200 líneas de validación a las 185 líneas regulares de código (código completo aquí). Cuando finalmente validé el último método, erróneamente pensé que había terminado.

Para mi sorpresa (y decepción), el trabajo no termina la primera vez que todo se valida. También debes asegurarte de que tu proyecto se valide de nuevo y se valide para otros. Discutiremos esta regla a continuación.

Regla 9: Revisa nuevamente tu validación para garantizar su confiabilidad.

Pensé que había terminado. Luego, moví la definición de seis líneas de la función Min de matemáticas de la biblioteca estándar de Dafny a mi código. Esto hizo que mi validación fallara, sin ninguna razón lógica (literalmente). Más tarde, después de pensar que lo había arreglado, eliminé un método que no se utilizaba. Nuevamente, la validación comenzó a fallar sin ninguna razón lógica.

¿Qué está pasando? Dafny funciona heurísticamente a través de una búsqueda aleatoria. Cambiar el código superficialmente (o cambiar las semillas aleatorias) puede cambiar cuánto tiempo necesita la búsqueda. A veces, la cantidad de tiempo cambia drásticamente. Si el nuevo tiempo supera un límite de tiempo establecido por el usuario, la validación fallará. [Hablaremos más sobre el límite de tiempo en el consejo n.º 3, a continuación.]

Debes probar la confiabilidad de tu validación probando diferentes semillas aleatorias. Aquí están los comandos que utilicé (en Windows) para validar un archivo con 10 semillas aleatorias.

@rem Encuentra la ubicación de Dafny y agrégala a tu ruta de acceso set path=C:\Users\carlk\.vscode-insiders\extensions\dafny-lang.ide-vscode-3.1.2\out\resources\4.2.0\github\dafny;%path%dafny verify seq_of_sets_example7.dfy --verification-time-limit:30 --cores:20 --log-format csv --boogie -randomSeedIterations:10

El resultado es un archivo *.csv que puedes abrir como una hoja de cálculo y luego buscar fallos:

Nota: Para obtener más ideas sobre cómo medir la confiabilidad de validación de Dafny, consulta esta respuesta de Stack Overflow sobre cómo analizar archivos *.csv y esta discusión en GitHub que recomienda la herramienta dafny-reportgenerator.

Una vez encontrados los puntos problemáticos, solicité la ayuda del coautor Divyanshu Ranjan. Divyanshu Ranjan utilizó su experiencia con Dafny para solucionar los problemas de validación del proyecto.

A continuación, se presentan sus consejos, con ejemplos del proyecto:

Consejo #1: Cuando sea posible, elimina las declaraciones “require” que involucren “forall” y “exists”.

Recordemos según la Regla 4 que la función fantasma SeqToSet devuelve el conjunto de enteros cubiertos por una lista ordenada y disjunta de rangos no vacíos. Definimos “ordenado y disjunto” con la función ValidSeq, que internamente utiliza dos expresiones forall. Podemos eliminar el requisito de que la lista debe estar ordenada y ser disjunta, de la siguiente manera:

ghost function SeqToSet(sequence: seq<NeIntRange>): set<int>  decreases |sequence|  // removido: requires ValidSeq(sequence){  if |sequence| == 0 then {}  else if |sequence| == 1 then RangeToSet(sequence[0])  else RangeToSet(sequence[0]) + SeqToSet(sequence[1..])}

Desde nuestro punto de vista, tenemos la misma función útil. Desde el punto de vista de Dafny, la función evita dos expresiones forall y es más fácil de aplicar.

Consejo #2: Usa “calc” para evitar el trabajo de adivinanza por parte de Dafny.

Con una declaración de “calc” en Dafny, enumeras los pasos exactos necesarios para llegar a una conclusión. Por ejemplo, aquí hay un “calc” del método DeleteExtra:

calc {    SeqToSet(xs[..indexAfter+1]) + SeqToSet(xs[indexAfter+1..]);  ==    { SeqToSetConcatLemma(xs[..indexAfter+1], xs[indexAfter+1..]); }    SeqToSet(xs[..indexAfter+1] + xs[indexAfter+1..]);  ==    { assert xs == xs[..indexAfter+1] + xs[indexAfter+1..]; }    SeqToSet(xs);  ==    { SetsEqualLemma(xs, r[indexAfter], r2, indexAfter, indexDel); }    SeqToSet(r2);  }

En este punto del código, xs es una secuencia de rangos, pero puede que no esté ordenada y sea disjunta. El “calc” afirma que:

1. los enteros cubiertos por las dos partes de xs, son iguales a
2. los enteros cubiertos por la concatenación de sus dos partes, son iguales a
3. los enteros cubiertos por xs, son iguales a
4. rs.

Para cada paso, se nos permite incluir lemas o afirmaciones para ayudar a demostrar ese paso. Por ejemplo, esta afirmación ayuda a demostrar el paso del 3 al 4:

{ assert xs == xs[..indexAfter+1] + xs[indexAfter+1..]; }

Para eficiencia y control, estos lemas y afirmaciones no serán visibles para el validador más allá de su paso. Esto mantiene a Dafny enfocado.

Consejo #3: Utiliza timeLimit para proporcionar cálculos cuando sea necesario.

Dafny deja de intentar validar un método en un timeLimit configurado por el usuario. Los límites de 10, 15 o 30 segundos son comunes porque, como usuarios, generalmente queremos que las validaciones que nunca sucederán fracasen rápidamente. Sin embargo, si sabemos que una validación ocurrirá eventualmente, podemos establecer un límite de tiempo específico para el método. Por ejemplo, Divyanshu Ranjan notó que DeleteExtra generalmente se valida, pero lleva más tiempo que los otros métodos, así que agregó un límite de tiempo específico para ese método:

method {:timeLimit 30} DeleteExtra(xs: seq<NeIntRange>, internalRange: IntRange) returns (r: seq<NeIntRange>)// ...

Nota: timeLimit no tiene en cuenta la diferencia de velocidad entre computadoras, así que establece un valor un poco generoso.

Consejo #4: Utiliza split_here para dividir un problema de validación en dos.

Como explican las preguntas frecuentes de Dafny, a veces es más rápido validar un conjunto de afirmaciones juntas, y a veces es más rápido validarlas una por una.

Utiliza la instrucción assert {:split_here} true; para dividir una secuencia de afirmaciones en dos partes con el propósito de validación. Por ejemplo, incluso con el timeLimit, DeleteExtra agotaba el tiempo hasta que Divyanshu Ranjan agregó esto:

// ...else  {    r := (s[..i] + [pair]) + s[i..];    assert r[..(i+1)] == s[..i] + [pair];    assert r[(i+1)..] == s[i..];    assert {:split_here} true; // dividir validación en dos partes    calc {      SeqToSet(r[..(i+1)]) + SeqToSet(r[(i+1)..]);// ...

Consejo #5: Mantén los lemas pequeños. Si es necesario, divide las garantías entre lemas.

A veces los lemas intentan hacer demasiado a la vez. Considera el SetsEqualLemma. Está relacionado con la eliminación de rangos redundantes. Por ejemplo, si insertamos a en xs, los rangos marcados con “X” se vuelven redundantes.

La versión original de SetsEqualLemma contenía 12 requires y 3 ensures. Divyanshu Ranjan lo dividió en dos lemas: RDoesntTouchLemma (11 requires y 2 ensures) y SetsEqualLemma (3 requires y 1 ensures). Con este cambio, el proyecto se validó de manera más confiable.

Aplicar estos consejos mejorará la confiabilidad de nuestra prueba. ¿Podemos hacer que la validación sea 100% confiable? Lamentablemente, no. Siempre existe la posibilidad de que con una semilla desafortunada, Dafny no pueda validar. Entonces, ¿cuándo dejamos de intentar mejorar la validación?

En este proyecto, Divyanshu Ranjan y yo mejoramos el código de validación hasta que la probabilidad de un error de validación en una sola ejecución cayera por debajo del 33%. Así que, en 10 ejecuciones aleatorias, no vimos más de 2 o 3 fallos. Incluso lo intentamos con 100 ejecuciones aleatorias. Con 100 ejecuciones, vimos 30 fallos.

Conclusión

Así que ahí lo tienes: nueve reglas para demostrar la corrección de un algoritmo de Rust con Dafny. Es posible que te desalientes porque el proceso no es más fácil ni más automático. Sin embargo, me anima saber que el proceso es posible en absoluto.

Como nota aparte: Desde la clase de geometría en la preparatoria, he encontrado las demostraciones matemáticas fascinantes y frustrantes. “Fascinantes” porque un teorema matemático, una vez demostrado, se considera verdadero para siempre. (La geometría de Euclides sigue siendo considerada verdadera. La física de Aristóteles, no.) “Frustrantes” porque mis clases de matemáticas siempre parecían vagas acerca de qué axiomas podía asumir y qué tan grandes podían ser los pasos en mi demostración. Dafny y sistemas similares eliminan esta vaguedad con comprobación automática de demostraciones. Aún mejor, desde mi punto de vista, nos ayudan a crear demostraciones sobre un campo en el que me importa profundamente: los algoritmos.

¿Cuándo vale la pena hacer una demostración formal de un algoritmo? Dado el trabajo involucrado, solo volveré a hacerlo cuando el algoritmo sea una combinación de complicado, importante o fácil de demostrar.

¿Cómo podría mejorar el proceso en el futuro? Me encantaría ver:

• Intercambio entre sistemas: Un teorema de geometría, una vez demostrado, nunca necesita volver a demostrarse. Me encantaría que los sistemas que verifican demostraciones algorítmicas pudieran usar las demostraciones de los demás.
• Un sistema en Rust tan fácil de usar como Dafny: Para trabajar en esta dirección, ver [1,2].

Como nota aparte: ¿Conoces algún sistema de validación en Rust fácil de usar? Por favor, considera aplicarlo a la validación de internal_add. Esto nos permitiría comparar la facilidad de uso y el poder del sistema en Rust con el de Dafny.

• El análogo de demostración de los archivos Cargo.lock de Rust: En Rust, usamos el Cargo.lock para establecer una combinación conocida y buena de dependencias del proyecto. Me gustaría que cuando Dafny encuentre una manera de demostrar, por ejemplo, un método, se bloqueen los pasos de la demostración encontrados. Esto podría hacer que la validación sea más confiable.
• Mejor inteligencia artificial para validación: Mi intuición es que ChatGPT, ligeramente mejorado, podría ser bueno para crear el 90% del código de validación necesario. Encuentro que la versión actual de ChatGPT 4 es pobre con Dafny, supongo que por falta de ejemplos de entrenamiento de Dafny.
• Mejor validación para inteligencia artificial: Cuando una IA genera código, nos preocupamos por la corrección del código. La validación formal podría ayudar al probar la corrección. (Para un ejemplo pequeño de esto, consulta mi artículo Comprueba código generado por IA de forma perfecta y automática.)

Gracias por unirte a nuestro viaje hacia la corrección del programa. Esperamos que si tienes un algoritmo para el que desees una demostración, estos pasos te ayuden a encontrarla.

Por favor, síguelo a Carl en VoAGI. Escribo sobre programación científica en Rust y Python, aprendizaje automático y estadísticas. Suelo escribir aproximadamente un artículo al mes.

Lee más trabajos de Divyanshu Ranjan en su blog. Además de los métodos formales, el blog abarca temas de geometría, estadísticas y más.

We will continue to update Zepes; if you have any questions or suggestions, please contact us!