La Singularidad Desnuda

Un universo impredecible de pensamientos y cavilaciones sobre ciencia, tecnología y otros conundros

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

Posted by Carlos en mayo 7, 2007

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 que la tiene, y una función Fno que no la tiene. Supongamos ahora que tenemos un algoritmo RA definido como

R_A(n) = \left\{ \begin{array}{ll} 1 & {\rm si\ }F_n\ {\rm tiene\ la\ propiedad\ }A \\ 0 & {\rm en\ otro\ caso}\end{array}\right.

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

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 Fn(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

S(m) = \left\{\begin{array}{ll}V(m) & {\rm si\ }M(m,m)=0\\ 0 & {\rm en\ otro\ caso}\end{array}\right.

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).

Enviar a Blog Memes Enviar a del.icio.us Enviar a digg Enviar a fresqui Enviar a menéame

Anuncios

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

  1. panta said

    ¿hay algún momento en que equiparas en la demo funciones matemáticas con programas informáticos? ¿Es factible, en general?
    Saludos.

  2. Carlos said

    Es factible, aunque por supuesto hay funciones que no son computables, y que por lo tanto no son asimilables a ninguna máquina de Turing (probar eso suele ser el objetivo de estas demostraciones). Si la función es computable, hay por definición una máquina de Turing que la calcula, y viceversa, dada una MT, hay una cierta función parcial que es la que calcula.

  3. Elena said

    Esta bastante bien explicado el teorema de rice, muchas gracias.

Sorry, the comment form is closed at this time.

 
A %d blogueros les gusta esto: