¿Qué aplicabilidad debe tener el problema de detener la información?

Experto establecido ... ese sería yo (aunque no con este nombre, uso un seudónimo porque soy tremendamente humilde). Permítame responder, entonces.

El "problema de detención" es, de hecho, una ilustración de la imposibilidad de decidir (para una computadora) si un programa determinado se detendrá o no. Por supuesto, muchos programas son decidibles, pero no todos. La gente tiende a pensar que si pudiéramos "predecir con precisión el comportamiento" de los programas de computadora, el malware no sería posible. Esto es demasiado simplista, por las siguientes razones:

• El "problema de detención" se trata de decidir si un programa informático se detendrá, para una entrada determinada , que se conoce como a priori . Este modelo funciona solo con programas que son cálculos puros y no hacen E / S. Por definición, esto no se aplica a ninguna aplicación que esté conectada a Internet o que pueda ser controlada por un humano. Como ilustración, considere una aplicación que ejecuta un video. Este nunca se detendrá mientras el usuario humano haga clic en el botón de rebobinado. Pero puede detenerse (y debería ser fácil de probar) si el usuario no hace clic en cualquier botón.

• Decidability es acerca de si una función determinada se puede evaluar en absoluto , pero no si se puede evaluar eficientemente . Si desea que un antivirus analice en busca de malware, desea la respuesta en 2 o 3 segundos, no en diez años. Esta noción de decidibilidad no captura todas las cosas en las que estamos interesados.

• Nosotros podemos tener requisitos. Considere una aplicación Java. Está escrito en bytecode que es susceptible de pruebas automáticas (eficientes). A saber, la JVM probará , de manera muy formal, que el código cumple con las reglas de tipo de Java (que nunca llama a un método en una clase que no cuenta con ese método). No es posible realizar tal prueba genéricamente, en cada secuencia posible de instrucciones de código de bytes; pero código Java válido es un código de bytes que puede se puede probar de esa manera. Esto significa que en la práctica es posible hacer cumplir los requisitos de "verificabilidad" para el código existente. En el punto de vista del "problema de detención", esto sería como afirmar que los programas para los cuales no se puede determinar el comportamiento de detención en forma absoluta (y rápida) se evitarán sin ceremonias de la ejecución.

• No estamos interesados en si un programa se detendrá , sino en si un programa hará cosas malas . Estoy a favor de una computadora para alterar mi cuenta bancaria ... siempre y cuando eso sea lo que quiero. La diferencia entre yo, el usuario humano / ursine, administrar mi dinero a través del sitio web del banco y un malware, desviar mi precioso oro a través del sitio web del banco, no es algo que exista en el mundo de las computadoras. No hay noción de mal en las computadoras. Si quiero seguridad, primero debo definir con toda la precisión necesaria qué es exactamente lo que quiero permitir a las computadoras y lo que no quiero. Antes de preguntarme si un programa informático podrá decidir automáticamente si un código dado respetará mis propiedades de seguridad básicas, primero debo definir estas propiedades, y esa parte inicial del trabajo es lejos de hacerse. Hacer que las computadoras adivinen lo que es Bueno es un antiguo problema que parece difícil.

Por estas razones, afirmo que invocar el "problema de detención" es una mala excusa. Resalta el hecho de que estamos lidiando con problemas que requieren un poco más de reflexión que escribir otro sitio web de PHP. Pero no implica que la seguridad no es posible, solo que la Ciencia no creará una herramienta mágica que la resolverá sin esfuerzo (porque este Bendito Martillo de Decidibilidad +3 también resolvería el problema de la detención, que no es matemáticamente posible).

  

¿Puede un atacante usar el problema de detención como una forma de ataque?

¿No es eso lo que utiliza un ataque algorítmico complexit ? Su servidor utiliza algún algoritmo que tiene un comportamiento muy malo en el peor de los casos, tal vez como no termina en secuencias de entrada especiales. Debido a que no existe un método general, le resulta difícil discernir qué secuencia de entrada especial podría causar un bucle infinito en su ingenioso algoritmo.