¿Es el problema de decidir si dos programas tienen la misma semántica decidida?

Question

Si tengo programa y quiero verificar si otros programas tienen exactamente la misma semántica o no, ¿podría siempre crear una máquina que podría tomar esa decisión?

Esta es una pregunta relevante para la seguridad de la información, ya que Metamorphic Malware realizará transformaciones en su propio código que lo hará lucir diferente a los detectores de malware estáticos al tiempo que preserva su semántica.Si es posible escribir una máquina que puede detectar si dos programas tienen la misma semántica, entonces es imposible escribir malware "indetectable".

Answer 1

Concretamente, siempre estamos tratando con transformaciones sintácticas, independientemente de si existe una teoría semántica que hace que estas transformaciones sea inteligibles para nosotros, o no. Al final, nuestra capacidad para demostrar automáticamente que dos programas diferentes son equivalentes se restringe a las propiedades que se pueden definir sintácticamente. Incluso entonces, hay límites a lo que podemos hacer, si permitimos el lenguaje en el que se definen estas propiedades para ser lo suficientemente ricas, por lo que la respuesta a su pregunta, en el caso general, tendría que ser negativo.

Más específicamente, sin embargo, detrás de cada proceso metamórfico específico que se puede automatizar también hay una estrategia específica, por lo que también hay límites a la eficacia de esas piezas de malware. Debido a eso, puede ser posible, dado algún conocimiento de esta estrategia, para atacar sus características sintácticas de una manera controlada, y agrietarse automáticamente el código detrás de él, lo que le impide atacar.

Sin embargo, los creadores de malware tienen la iniciativa, lo que les da una ventaja. Esta ventaja se puede amplificar con habilidades técnicas y sofisticación matemática, por lo que no es aconsejable basar su estrategia de seguridad sobre la capacidad de detectar y desactivar una pieza de software que ya ingresó en su sistema.