Estoy de acuerdo con Larsman, y creo que el argumento puede ser preciso. Primero, tengo que aceptar que "encontrar todo el código en un binario dado" significa, en este contexto, tener una sola función computable que determina qué bytes dentro de un binario de entrada corresponden a las instrucciones que se ejecutan.
EDITAR: Si alguien no está seguro de por qué hay un problema aquí, piense en código de máquina ofuscado. Desmontar dicho código es un problema no trivial. Si comienza el desmontaje en el medio de una instrucción de varios bytes, obtendrá el desmontaje incorrecto. Esto no solo rompe la instrucción en cuestión, sino que por lo general algunas instrucciones más allá de eso. etc. Míralo. (por ejemplo, google "ofuscación y desensamblaje").
bosquejo de la estrategia para hacer esta precisión:
En primer lugar, definir un modelo informático teórico/máquina en la que un programa está codificado en instrucciones binarias de varios bits, al igual que el código máquina en los ordenadores "reales", pero hizo preciso (y tal que está completo). Supongamos que el código binario codifica el programa y toda la entrada. Todo esto debe hacerse preciso, pero supongamos que el lenguaje tiene una instrucción de detención (codificada en binario), y que un programa se detiene si y solo si ejecuta una instrucción 'alto'.
En primer lugar, supongamos que la máquina no puede modificar el código del programa, pero tiene una memoria en la que trabajar. (se supone infinito en casos interesantes).
Entonces, cualquier bit dado será al comienzo de una instrucción que se ejecuta durante la ejecución del programa, o no lo hará. (por ejemplo, puede estar en el medio de una instrucción, o en datos o "código basura", es decir, código que nunca se ejecutará. Tenga en cuenta que no he afirmado que estos sean mutuamente excluyentes, como, por ejemplo, una instrucción de salto puede tener un objetivo que se encuentra en el medio de una instrucción en particular, creando así otra instrucción que, "en el primer paso" no parecía una instrucción ejecutada).
Defina ins (i, j) como la función que devuelve 1 si el binario i tiene una instrucción que comienza en la posición de bit j, que se ejecuta en una ejecución del programa codificado por i. Definir ins (i, j) es 0 en caso contrario. supongamos que ins (i, j) es computable.
Let halt_candidate (i) ser el siguiente programa:
for j = 1 to length(i)
if(i(j..j+len('halt')-1) == 'halt')
if(ins(i,j) == 1)
return 1
return 0
Desde desactivamos auto-modificación de código anterior, la única forma para un programa para detener es para que haya una instrucción 'alto' en algún posición j que se ejecuta. Por diseño, halt_candidate (i) calcula la función de detención.
Esto proporciona un boceto muy aproximado de una dirección de la prueba. es decir, si suponemos que podemos probar si el programa i tiene una instrucción en la ubicación j para todo j, entonces podemos codificar la función de detención.
En la otra dirección, se debe codificar un emulador de la máquina formal, dentro de la máquina formal. Luego, cree un programa más las entradas i y j que emulan el programa i y cuando se ejecuta una instrucción en la posición de bit j, devuelve 1 y se detiene. Cuando se ejecuta cualquier otra instrucción, continúa ejecutándose, y si la simulación alguna vez simula una función de 'alto' en i, el emulador salta a un bucle infinito. Entonces ins (i, j) es equivalente a detener (emulador (i, j)), por lo que el problema de detención implica el problema del código de búsqueda.
Por supuesto, se debe suponer una computadora teórica para que esto sea equivalente al famoso problema de detención indestructible. De lo contrario, para una computadora "real", el problema de detención es solucionable pero difícil de resolver.
Para un sistema que permite el código de modificación automática, el argumento es más complejo, pero espero que no sea tan diferente.
EDITAR: Creo que una prueba en el caso de modificación automática sería implementar un emulador del sistema más código de auto modificación en el código estático más el sistema de datos anterior. Luego, detenerse con el código de auto modificación permitido para el programa i con datos x es lo mismo que detenerse en el código estático más el sistema de datos anterior con el binario que contiene el emulador, iyx como código más datos.
¿Qué quiere decir con "encontrar el código"? Ingeniería inversa o? – orlp
Mi comprensión por lo que HE/SHE significa es encontrar toda la cadena de código, incluidas las dependencias. Busque la línea con ese texto en la respuesta seleccionada para ver el contexto. –
¿Debería preguntar esto en [referencias teóricas] (http://cstheory.stackexchange.com/)? – Graviton