Turing en una cáscara de nuez: Teorema de Rice (o por qué ningún antivirus será fiable al 100%)

En el último artículo sobre Turing vimos como hay ciertos problemas cuya resolución no es abordable mediante un proceso algorítmico. Esto lo ejemplificamos a través del problema de la parada, pero hay muchos otros problemas que resultan ser no computables. Por ejemplo, también vimos como el reconocimiento de resolutores parciales de parada (i.e., determinar si un programa arbitrario da siempre o bien soluciones correctas al problema de la parada, o bien no da solución) era un problema no computable: si fuera computable, podríamos construir una solución algorítmica al problema de la parada, cosa que sabemos que es imposible. Esta estrategia de reducir el problema de la parada (o en general, cualquier otro problema que se sepa no-computable) a un cierto problema P es la más común para determinar la no-computabilidad del mismo. Por ejemplo, consideremos el problema de la equivalencia: dados dos programas determinar si son equivalentes, esto es, si computan la misma función. Intuitivamente, podemos ver que dar respuesta a este problema implica ser capaz de determinar si las salidas de dos programas arbitrarios son iguales para cierta entrada, lo que significa ser capaz de determinar si se detienen o no para la misma. De manera más genérica, podemos recurrir a un resultado sumamente poderoso en este campo: el Teorema de Rice. Básicamente, el Teorema de Rice nos dice:

Dada una propiedad no trivial de las funciones parciales, no es computable determinar si una función arbitraria la posee o no.

En la anterior definición, una propiedad es no trivial si hay funciones que la tienen, y otras que no. La demostración del teorema se basa precisamente en explotar la posibilidad de resolver el problema de la parada si tuviéramos un reconocedor de propiedades no triviales. Así, supongamos que tenemos una cierta propiedad A no trivial. Eso quiere decir que hay al menos una función F_sí que la tiene, y una función F_no que no la tiene. Supongamos ahora que tenemos un algoritmo R_A definido como

Definamos ahora un programa T_m,n(i) que primero calcula F_n(m) y luego calcula F_sí(i), valor este último que se devuelve como resultado. Puede verse que este programa devuelve lo mismo que F_sí(i), y por lo tanto tiene la propiedad A, sí y sólo si F_n(m) se para. Si w(m,n) es la codificación del programa T_m,n, entonces podemos definir un algoritmo para determinar la parada como H(m,n) = R_A(w(m,n)). Como esto es imposible, se sigue que no existe R_A (si la propiedad A fuera algo que F_n(m) cumple al no pararse, hubiéramos podido hacer un razonamiento similar empleando F_no en lugar de F_sí).

Las aplicaciones del Teorema de Rice son enormes. Por ejemplo, no es computable saber si una función arbitraria se detiene para algún valor de entrada (hay al menos una que sí lo hace, y otra que no, por lo que se trata de una propiedad no trivial). Otro ejemplo más práctico: no es computable determinar si un programa es un virus/troyano/… que realizará acciones maliciosas (definidas de alguna manera conveniente, como por ejemplo, escribir en cierta zona reservada de memoria, copiarse a sí mismo en otro programa, etc.). Esto no quiere decir que ningún virus/troyano/… sea detectable, sino que para cualquier procedimiento de detección fiable, siempre se puede definir un programa malicioso que lo burle. Esto tiene dos consecuencias prácticas fundamentales: (1) no hay protección fiable al 100%, y (2) la falta de seguridad hay que compensarla con falsos positivos.

Si alguien no termina de estar del todo convencido de que la detección de programas maliciosos no es computable, he aquí una demostración directa a través del corte diagonal. Sea M(m,n) un supuesto algoritmo no malicioso que determina si F_n(m) ejecuta código malicioso. Sea V(m) un programa que siempre ejecuta código malicioso para cualquier valor de m. Definamos el algoritmo S(m) como

El anterior algoritmo tendrá una codificación s. ¿Es malicioso S(s)? Si lo es, entonces M(s,s)=1, por lo que S(s) simplemente devuelve 0, sin hacer nada más, luego no es malicioso (salvo que la comprobación M(s,s) lo fuera, lo que suponíamos falso de partida). Si no lo es, entonces M(s,s)=0, por lo que se ejecuta el código malicioso, lo que es otra contradicción. Conclusión, el supuesto algoritmo M no existe. Esta demostración es en principio más débil que la del Teorema de Rice, ya que deja abierta la posibilidad a detectores maliciosos, pero podemos soslayar esta limitación haciendo que la ejecución de M se haga enteramente sobre una sistema de memoria diferente del que empleamos para S (sería una emulación perfecta de M sobre un computador virtual que se crearía para la ocasión, y que se destruiría luego).