Fred Cohen determinó teóricamente que la detección viral es un problema indecidible. ¿Alguien puede proporcionar un razonamiento intuitivo para eso?
Fred Cohen experimentó con virus informáticos y confirmó el postulado de Neumann e investigó otras propiedades del malware, como la detectabilidad, la auto-ofuscación mediante cifrado rudimentario y otras. Su doctorado de 1988 disertación fue sobre el tema de virus informáticos
Claro. En el famoso resultado de Cohen, dice que un detector de virus perfecto debería emitir una alarma si y solo si el programa de entrada puede actuar como un virus (es decir, infectar su máquina y causar daños).
Considere el siguiente programa:
f();
infect_and_do_damage();
donde f() es una función inofensiva, y infect_and_do_damage() es una carga viral que infecta su máquina y hace todo tipo de daño (borra su disco duro, le roba todo su dinero, lo que sea).
Consideremos lo que debería decir un detector de virus perfecto sobre este programa:
Si f() puede regresar, esto es un virus y el detector de virus debería emitir una alarma.
Por otra parte, si f() siempre ingresa en un bucle infinito y nunca regresa, entonces la segunda línea es un código muerto, infect_and_do_damage() nunca se invocará, este programa nunca actuará como un virus, y el detector de virus no debe activar ninguna alarma.
Entonces, el problema de determinar si este código es un virus es equivalente al problema de determinar si la función f() puede detenerse alguna vez. Ese es el famoso problema de la detención, que se sabe que es indecidible.
En otras palabras, detectar si un programa es un virus es tan difícil como detectar si un programa se detendrá. Por lo tanto, ambos problemas son indecibles.
Tenga en cuenta que este es un resultado puramente teórico. La indecidibilidad es una construcción puramente teórica. El hecho de que un problema sea indecidible no es el final de la conversación; es simplemente el comienzo de la conversación.
En la práctica, hay varias maneras de tratar de lidiar con la indecidibilidad: por ejemplo, intente escribir una solución que sea probabilísticamente correcta, incluso si no siempre es correcta en todos los programas; intente encontrar una solución que funcione para el conjunto de programas que probablemente encuentre en la práctica, incluso si no funciona en todos los programas; permitir que la solución responda de vez en cuando "No sé" o que se equivoque al declarar que un programa es un virus (o errar al lado de falsos negativos); y así sucesivamente.
Por lo tanto, no debe tratar esto como una afirmación definitiva de que la detección de virus es imposible, ya que el problema es indecidible, no significa que sea necesariamente imposible encontrar una solución lo suficientemente buena en la práctica. Pero sí identifica algunas barreras fundamentales para construir un detector de virus perfecto.
Para complementar la respuesta de @DW: incluso si se pudiera resolver el problema de la detención, también existe un problema de definición inherente: ¿qué es un virus, de todos modos?
Por ejemplo, como dice el chiste, Microsoft Word es un virus:
¿De qué manera puede Word no ser un virus?
Por supuesto, muchas personas (incluidos los abogados de Microsoft) argumentarían que Word no es un virus y que es una afirmación ridícula. Sin embargo, esto muestra que la propiedad not-a-virus es macroscopic : no es una distinción clara que proviene del código solo (por "macroscopic" quiero decir que es una propiedad emergente del todo, no de ninguno de los códigos de operación de ensamblado en el ejecutable).
Tomemos un ejemplo menos indignante: el instalador para un sistema operativo Linux. Es codigo? Sí. ¿Se copia a sí mismo? Sí, en efecto. ¿Modifica el sector de arranque? Absolutamente. ¿Altera el sistema operativo que ya está instalado en la máquina? Oh si. La única propiedad que lo convierte en un non -virus es que cada vez que el instalador hace todo lo anterior, el usuario humano lo quiere así .
De ello se deduce que un antivirus perfecto debe adivinar de alguna manera lo que quiere el usuario. Y no puede haber una respuesta absoluta a eso. En la práctica, la mayoría de los programas antivirus intentan hacer "suposiciones informadas" y, cuando se trata de eso, deciden qué debería querer el usuario (así es como pasé una hora frustrante esta mañana tratando de enviar un archivo ejecutable a un cliente: algunos antivirus he decidido que no es posible que desee enviar un archivo ejecutable por correo electrónico).