💻 computer science

Complexity Theory of Randomised Testing

Este artículo establece los primeros fundamentos de la teoría de la complejidad para las pruebas aleatorizadas al modelar los generadores como transductores de Turing para caracterizar los límites de la generación de entradas eficientes y con restricciones de espacio, revelando distinciones fundamentales entre la complejidad de generación y de decisión al demostrar que la generación eficiente requiere esquemas de certificados específicos y no puede derivarse composicionalmente de predicados lógicos generales.

Autores originales: Pingshi Yu, Chengsong Tan, Nicolas Wu, Alastair Donaldson

Publicado 2026-07-14

📖 6 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Pingshi Yu, Chengsong Tan, Nicolas Wu, Alastair Donaldson

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 desarrollador de videojuegos intentando probar un nuevo mundo masivo. Quieres asegurarte de que tu juego no se bloquee, así que necesitas un robot que pueda escupir millones de niveles, personajes y objetos aleatorios para ver si algo se rompe. Este robot se llama generador. Durante años, los desarrolladores han construido estos robots a mano, ajustándolos hasta que funcionan lo suficientemente bien. Pero nadie sabía realmente los límites teóricos de lo que estos robots podrían hacer en realidad. ¿Podrían generar cualquier nivel posible? ¿Podrían hacerlo lo suficientemente rápido como para ser útiles?

Un equipo de investigadores del Imperial College London y Kaihong decidió poner a estos robots bajo un microscopio usando la Teoría de la Complejidad —las matemáticas que estudian qué tan difíciles son los problemas de resolver—. No se limitaron a mirar el código; modelaron los robots como "máquinas de Turing" (las computadoras teóricas definitivas) que comen bits de datos aleatorios y escupen niveles de juego. Esto es lo que descubrieron.

La lista de "Lo que se puede fabricar"

Primero, se preguntaron: ¿Cuál es el límite absoluto de lo que un generador puede producir?

Descubrieron que, si le das a un generador tiempo y memoria ilimitados, puede producir exactamente el mismo conjunto de cosas que una computadora estándar puede reconocer. En el mundo de las matemáticas, esto se llama lenguajes Recursivamente Enumerables (RE).

La buena noticia: Si un conjunto de entradas (como "todos los programas C válidos") puede ser reconocido por una computadora, un generador puede producirlo teóricamente.
La mala noticia: Si un conjunto de entradas es demasiado extraño para ser reconocido por una computadora (como "todos los programas que nunca dejarán de ejecutarse"), ningún generador podrá jamás producirlos. No es un error en tu código; es una ley fundamental del universo. No puedes construir un robot que escupa cada bucle infinito, porque las matemáticas dicen que es imposible enumerarlos todos.

El problema del "Obstáculo de velocidad"

Luego, se preguntaron: ¿Qué pasa si necesitamos que el generador sea rápido? En el mundo real, no puedes esperar un millón de años por un caso de prueba. Necesitas resultados en segundos.

Los investigadores descubrieron un giro sorprendente: Ser capaz de verificar si algo es válido no es lo mismo que ser capaz de crear algo válido.

El ejemplo del SAT Solver: Imagina un rompecabezas donde tienes que encontrar una combinación específica de interruptores para encender una luz. Verificar si una combinación funciona es difícil (es "NP-completo"). Pero los investigadores demostraron que puedes construir un robot rápido que genere estas combinaciones que funcionan. Funciona "plantando un testigo": el robot elige secretamente una combinación ganadora primero, y luego construye el rompecabezas alrededor de ella.
La trampa de la colisión de Hash: Sin embargo, también demostraron que para algunos problemas, incluso si verificar la respuesta es fácil, crear la respuesta podría ser imposible de hacer rápidamente. Analizaron las "colisiones de hash" (encontrar dos entradas diferentes que produzcan la misma huella digital). Verificar si dos huellas digitales coinciden es súper rápido. Pero, ¿encontrar un par que coincida? Si pudieras construir un robot rápido para hacer esto, romperías la seguridad de casi toda la criptografía moderna.
- El veredicto: A menos que el mundo de la criptografía se rompa, hay problemas donde verificar es fácil, pero generar es difícil. No puedes simplemente desear un generador rápido; a veces, las matemáticas simplemente no lo permitirán.

La restricción de "Memoria" (Fuzzing y Retroalimentación)

Muchas herramientas de prueba modernas, como los "fuzzers", no solo escupen datos aleatorios; recuerdan lo que intentaron antes. Si una prueba hace que el programa falle, el fuzzer lo recuerda e intenta retocar la entrada para hacerlo fallar de nuevo. Esto es como un detective que aprende de cada pista.

Los investigadores modelaron esto como un generador con una cantidad limitada de memoria (espacio). Descubrieron que incluso con esta "memoria" y un ciclo de retroalimentación, el generador sigue estando limitado.

El límite: Si el generador tiene una cantidad polinómica de memoria (que cubre casi todas las herramientas prácticas), solo puede generar cosas que pertenecen a una clase llamada PSPACE.
El choque de realidad: Esto significa que incluso las herramientas de fuzzing más inteligentes y con más memoria no pueden generar entradas para problemas que son "EXPTIME-complete" (problemas que requieren un tiempo exponencial para resolverse). Si un problema es demasiado complejo para ser resuelto por una máquina PSPACE, ninguna cantidad de retroalimentación o memoria ayudará a un generador a crear casos de prueba para él.

El mito de la "Componibilidad"

Finalmente, abordaron un sueño de los ingenieros de software: ¿Podemos construir un "set de Lego" de generadores?
Imagina tener una herramienta donde dices: "Quiero un generador para A Y B", o "Quiero un generador para NO A", y la herramienta combina automáticamente los elementos en un nuevo generador rápido.

El artículo lanza un NO rotundo a este sueño, bajo supuestos estándar.

La regla: No puedes combinar automáticamente los generadores usando "Y" (conjunción) o "NO" (negación) y garantizar que sigan siendo rápidos.
¿Por qué? Si pudieras hacer esto, podrías resolver problemas que actualmente se cree que son imposibles de resolver rápidamente.
La excepción: Puedes hacer esto para tipos de lógica muy simples y restringidos (como "Datalog lineal" o "NL"), pero tan pronto como añades "Ys" o "NOs" complejos, la magia se rompe. Si quieres combinar reglas complejas, tienes que renunciar a las garantías de velocidad o aceptar que tu generador simplemente "intentará y fallará" (muestreo de rechazo) hasta que tenga suerte.

El panorama general

El artículo concluye que generar datos es un desafío distinto y a menudo más difícil que decidir si un dato es válido.

Lo que se demuestra: Demostraron que el conjunto de todas las cosas generables es exactamente el conjunto de las cosas recursivamente enumerables. Demostraron que existen generadores rápidos para ciertos problemas difíciles (como SAT) pero no para otros (como las colisiones de hash, asumiendo que la criptografía es segura). Demostraron que las herramientas impulsadas por retroalimentación están limitadas por PSPACE.
Lo que se descarta: Descartaron la posibilidad de una biblioteca universal, rápida y compositiva que pueda manejar cualquier combinación lógica de reglas. Descartaron la idea de que "fácil de verificar" siempre signifique "fácil de generar".

En resumen, si estás construyendo un robot de pruebas, no puedes simplemente desear que sea rápido e inteligente. Las matemáticas han trazado una línea en la arena: algunas cosas son imposibles de generar, algunas son imposibles de generar rápidamente, y algunas no puedes mezclarlas sin romper la velocidad. Pero ahora, finalmente sabemos exactamente dónde están esas líneas.

Resumen Técnico: Teoría de la Complejidad de las Pruebas Aleatorizadas

Planteamiento del Problema

Las pruebas aleatorizadas, particularmente las Pruebas Basadas en Propiedades (PBT, por sus siglas en inglés), dependen en gran medida de generadores para producir entradas para un Sistema Bajo Prueba (SUT). A pesar del extenso desarrollo práctico, los fundamentos teóricos de estos generadores permanecen insuficientemente explorados. Específicamente, la cuestión fundamental de qué significa que un conjunto de entradas sea "generable" (tanto en términos de existencia como de eficiencia) no ha sido respondida rigurosamente. Los profesionales a menudo se enfrentan a la incertidumbre respecto a los límites de la expresividad de los generadores: qué lenguajes pueden ser generados en absoluto y cuáles pueden ser generados de manera eficiente. Además, existe una falta de comprensión formal sobre la relación entre la complejidad de decidir la membresía en un lenguaje (complejidad de decisión) y la complejidad de generar instancias de ese lenguaje (complejidad de generación).

Metodología

Los autores establecen un marco de complejidad teórica modelando los generadores aleatorizados como transductores de máquinas de Turing.

Modelo Formal: Un generador se define como una máquina de Turing determinista con tres cintas: una cinta de entrada de solo lectura (que consume bits aleatorios), una cinta de trabajo y una cinta de salida de solo escritura.
Aleatoriedad: La aleatoriedad se modela como una cadena de bits de entrada explícita (un flujo infinito de lanzamientos de moneda justos). Un generador se considera "eventualmente productivo" si produce una salida para casi todas las cadenas de bits infinitas (probabilidad 1).
Restricciones de Recursos: Los autores introducen familias de generadores indexadas por el tamaño de la salida (por ejemplo, longitud de la cadena $n$ $n$ ). Definen clases de complejidad basadas en límites de tiempo y espacio relativos a este tamaño de salida:
- GEN: Todos los lenguajes generables (sin restricciones).
- PG: Lenguajes generables en tiempo polinomial.
- EPG: Lenguajes generables en tiempo polinomial esperado.
- LG: Lenguajes generables en espacio logarítmico.
- PSPACEG: Lenguajes generables en espacio polinomial.
Generación Correlacionada: Para modelar técnicas impulsadas por retroalimentación, como el fuzzing guiado por cobertura o la ejecución concolic, los autores extienden el modelo para incluir el acceso a un oráculo del SUT, analizando la generación limitada por espacio donde las salidas previas influyen en las futuras.

Contribuciones Clave y Resultados

1. Límites de Expresividad (Generación sin Restricciones)

El artículo establece que el conjunto de lenguajes generables coincide exactamente con los lenguajes Recursivamente Enumerables (RE).

Teorema 3.1: $GEN = RE$.
Implicación: Un lenguaje es generable si y solo si es RE. En consecuencia, los lenguajes fuera de RE (como el conjunto de programas que no terminan, según el Teorema de Rice) no pueden ser generados por ningún algoritmo. Esto implica que las propiedades con precondiciones no-RE (por ejemplo, probar un compilador con todos los programas que no terminan) no pueden ser probadas completamente mediante pruebas aleatorizadas; cualquier generador debe necesariamente muestrear de un subconjunto estricto, probando una propiedad más débil.

2. Generación Eficiente (Tiempo Polinomial)

Los autores investigan la clase PG (lenguajes generables en tiempo polinomial) y su relación con las clases de complejidad clásica.

Contención en NP: $PG \subseteq NP$ . La generación eficiente requiere que la precondición esté en NP; si una precondición es PSPACE-hard o coNP-hard (por ejemplo, fórmulas booleanas cuantificadas o fórmulas insatisfacibles), no existe un generador de tiempo polinomial totalmente general.
Separación Estricta de P: Bajo supuestos criptográficos estándar (específicamente la existencia de funciones hash resistentes a colisiones), existen lenguajes en P que no están en PG.
- Teorema 5.1: Si existen funciones hash resistentes a colisiones, entonces $P \not\subseteq PG$ .
- Implicación: Una complejidad de decisión fácil no es necesaria ni suficiente para una generación eficiente. Se puede decidir eficientemente si existe una colisión de hash (en P), pero no se puede generar eficientemente una colisión (a menos que se rompan las funciones hash).
NP-Completitud: A pesar de la separación de P, PG contiene problemas NP-completos. Por ejemplo, los autores muestran que CNF-SAT está en PG mediante la construcción de un generador que muestrea una asignación aleatoria y construye una fórmula satisfecha por esa asignación (siembra de testigos o witness planting).

3. Caracterización de la Generabilidad Eficiente

El artículo proporciona una caracterización estructural de los lenguajes PG.

Teorema 7.1: Un lenguaje $L$ $L$ está en PG si y solo si admite un esquema de certificado. Esto significa que existe un verificador de tiempo polinomial $V$ $V$ tal que uno puede:
1. Muestrear un certificado aleatorio $c$ .
2. Reconstruir eficientemente una instancia aleatoria $w$ a partir de $c$ de tal manera que $V(w, c)$ acepte.
Signancia: Esto formaliza la "siembra de testigos" (generar una instancia alrededor de una solución conocida) como el mecanismo fundamental para todos los generadores eficientes. Implica que cualquier generador eficiente para un lenguaje NP opera esencialmente muestreando un testigo y reconstruyendo la instancia del problema.

4. Generación Limitada por Espacio y Retroalimentación

Los autores analizan generadores que producen muestras correlacionadas, modelando técnicas como la ejecución concolic y el fuzzing guiado por cobertura.

Teorema 6.1: $PSPACEG = PSPACE$.
Implicación: Las técnicas de generación impulsadas por retroalimentación, incluso con acceso a un oráculo al SUT, están limitadas por PSPACE. Si el propio SUT no resuelve problemas PSPACE-completos, entonces las técnicas impulsadas por retroalimentación no pueden generar entradas para conjuntos EXPTIME-completos. Esto limita el poder teórico del fuzzing guiado por cobertura para ciertos problemas de alta complejidad.

5. Limitaciones de las Librerías Composicionales

El artículo aborda el diseño de librerías de PBT que pretenden componer generadores a partir de predicados lógicos.

Teorema 7.2: Bajo supuestos estándar ( $NP \neq coNP$ y la existencia de funciones hash resistentes a colisiones), la clase PG no es cerrada bajo complementación o intersección.
Implicación: Ninguna librería puede mapear composicionalmente los predicados lógicos que involucran negación ( $\neg$ ) o conjunción ( $\land$ ) a generadores de tiempo polinomial manteniendo las garantías de eficiencia. Los diseñadores deben o bien restringir el lenguaje de predicados (por ejemplo, a NL o Datalog lineal, que son cerrados bajo estas operaciones) o confiar en el muestreo por rechazo, que puede ser ineficiente.

Significancia

El artículo afirma proporcionar los primeros fundamentos de complejidad teórica para los generadores de pruebas aleatorizadas. Su importancia radica en:

Clarificar Límites: Define rigurosamente qué se puede y qué no se puede generar, distinguiendo entre la complejidad de decisión y la complejidad de generación.
Validar y Refutar Intuiciones: Confirma que la "siembra de testigos" es la estructura necesaria para la generación eficiente y demuestra que las propiedades fáciles de decidir (como las colisiones de hash) pueden ser difíciles de generar.
Guiar el Diseño de Herramientas: Ofrece resultados negativos para el diseño de librerías de pruebas composicionales, mostrando que la composición general con garantías de eficiencia es imposible para los operadores lógicos estándar.
Amplia Aplicabilidad: Aunque motivado por las pruebas de software, el marco es aplicable a cualquier campo que requiera la generación aleatoria a partir de conjuntos restringidos, como el método de Monte Carlo por cadenas de Markov (MCMC) y la generación de espacios químicos.

Los autores concluyen que su marco permite un análisis riguroso de las campañas de prueba, yendo más allá de las heurísticas empíricas hacia garantías formales sobre la factibilidad y la eficiencia de la generación de entradas.