SEDICE


Conectado
Registro:

Apodo:
Contraseña:
Código de Seguridad: Codigo de Seguridad
Pon el código de seguridad:


Eres un usuario anónimo. Puedes registrarte aquí


183 conectados
165 anónimos
18 miembros

[más info sobre el foro]


Tus libros en

IberLibro.com - 110 millones de libros nuevos, antiguos, agotados y de ocasión


Promociones.



Rincón del Autor
Conversa con el propio autor


NORMAS
NORMAS de comportamiento


Comentarios en leelibros
·Los Héroes
·La Senda del Dragón
·Interiores
·Santa Claus en la villa olímpica
·La última del oEste

Leer más...


Google Chrome
Si usas Google Chrome, prueba el tema de Sedice


Ayuda a Sedice
Si quieres ayudarnos a financiar este sitio, ahora puedes hacerlo a través de nuestra cuenta bancaria o a través de Paypal.


PORTADA
·blog_ El Blog de Fran Ontanaya: Ambition, European Space Agency’s science fiction film
·blog_ Noticias CF: 20 Aniversario de la Librería Joker
·blog_ Noticias CF: Seleccionados para "Visiones 2014"
·blog_ Mi mundo como escritora: No leemos por culpa del colegio...
·blog_ Noticias CF: Fallo del Premio UPC de novela corta de ciencia-ficción 2014

Leer más...

Sedice.com :: Ver tema - Problema de la parada y detección de malware
 FAQFAQ   BuscarBuscar   Grupos de UsuariosGrupos de Usuarios   PerfilPerfil   Entre para ver sus mensajes privadosEntre para ver sus mensajes privados   LoginLogin 

Problema de la parada y detección de malware

 
Publicar nuevo tema   Responder al tema    Foros de discusión -> Ciencia
Ver tema anterior :: Ver tema siguiente  
Autor Mensaje
Mimoide
Terrateniente
Terrateniente



Registrado: Feb 05, 2005
Mensajes: 523
MensajePublicado: Sab Feb 11, 2012 5:55 pm    Asunto: Problema de la parada y detección de malware Responder citando

http://en.wikipedia.org/wiki/Halting_Problem
Al parecer existen definiciones formales de "virus informático", para las que hay pruebas de la inexistencia de un programa 'universal' de detección que, cuando no utilizan el resultado de Turing, se basan en un argumento análogo. (Habría que retrotraernos aún más, pues, de ser quisquillosos.)
La wikipedia enlaza el siguiente artículo.
http://www.research.ibm.com/antivirus/SciPapers/VB2000DC.htm
¿Qué sabéis sobre este asunto? ¿Es posible observar algo de "diagonalizante" en las estrategias que emplean en la práctica los virus y otros programas de malware?

Volver arriba
Ver perfil de usuario Enviar mensaje privado
odo
Cacique
Cacique



Registrado: Feb 14, 2005
Mensajes: 2616
MensajePublicado: Sab Feb 11, 2012 7:03 pm    Asunto: Responder citando

Hay un teorema muy general (y que generaliza al problema de la parada) que se podría aplicar a este tipo de situaciones: el Teorema de Rice. Básicamente, dice que no hay ninguna propiedad no trivial de los programas que pueda ser detectada automáticamente.

Por ejemplo, imaginaos que queremos determinar si un programa va a escribir un 0 en pantalla o no. Esa es una propiedad no trivial porque hay programas que escriben 0 en pantalla y otros que no. Lo que nos dice el Teorema de Rice es que no hay ningún algoritmo capaz de analizar un programa y decidir en un tiempo finito (y acertando) si va a escribir un 0 en pantalla o no. En este caso, lo mejor que podríamos hacer es "semi-decidir" el problema: esperar a ver si escribe un 0 en pantalla y entonces decir que sí. Evidentemente, si el programa no escribe nunca un 0 y no termina, nos quedaremos eternamente con la duda.

Mi intuición es que el Teorema de Rice (o una variante) se podría aplicar también para una definición adecuada de "malware". No he profundizado nunca en el tema, pero sé que hay por artículos sobre el particular.

Más detalles sobre el Teorema de Rice: http://en.wikipedia.org/wiki/Rice%27s_theorem


_________________
http://sentidodelamaravilla.blogspot.com
Volver arriba
Ver perfil de usuario Enviar mensaje privado
Mimoide
Terrateniente
Terrateniente



Registrado: Feb 05, 2005
Mensajes: 523
MensajePublicado: Lun Feb 13, 2012 4:12 pm    Asunto: Responder citando

Lo que pasa es que una definición en términos de funciones recursivas (necesaria para aplicar el teorema de Rice) en principio hace completa abstracción del proceso de cómputo, con lo que hacer la reducción de manera que tenga sentido puede no resultar fácil. La ejecución de un sistema operativo, por ejemplo, idealmente nunca finaliza. El objetivo no es que se detenga en un estado terminal del que extraer un valor definitivo, entiendo, sino que se mantenga siempre 'con vida', por decirlo de alguna manera. ¿Qué ajustes requiere el modelado con máquina de Turing procesos de cómputo "abiertos" de ese tipo? Espero no haber dicho ninguna barbaridad.
Volver arriba
Ver perfil de usuario Enviar mensaje privado
odo
Cacique
Cacique



Registrado: Feb 14, 2005
Mensajes: 2616
MensajePublicado: Lun Feb 13, 2012 9:57 pm    Asunto: Responder citando

Tienes mucha razón. Por eso decía que "mi intuición" me decía que parece que podría aplicarse algo similar.

Sé que hay alguna definición más "general" de cómputo en el que se intenta incluir cualquier proceso, termine o no, pero la verdad es que no he profundizado en el tema.

Por otro lado, pensando en la demostración del Teorema de Rice, creo que no sería necesario hacer muchas modificaciones para poder incluir propiedades de programas más generales. La demostración es más o menos como sigue:

Supongamos una propiedad A no trivial de los programas. Como A es no trivial, hay programas que la verifican y programas que no. El programa correspondiente a la función indefinida I (la que no para con ninguna entrada) o bien cumple A o bien no la cumple. Supongamos, sin pérdida de generalidad, que la cumple. Tomemos otro programa H que no verifique A (debe existir, al ser A no trivial). Supongamos ahora que existe un algoritmo B para decidir A y veamos cómo construir un algoritmo para decidir el problema de la parada:

Dada f que queremos saber si para con entrada x o no, construímos el siguiente programa que llamaremos J:

Computamos f(x)
Si f(x) para, entonces ejectutamos el programa H

Entonces, J es igual a I si f(x) para e igual a H si f(x) no para. Por tanto, f(x) para si y sólo si J no cumple A. Pero como tenemos el algoritmo B que es capaz de decidir si J tiene o no la propiedad A, entonces podríamos resolver el problema de la parada.

Creo que esta demostración (que no es más que el típico método de reducción) se podría modificar para utilizar para el caso del malware, pero habría que ver qué definición concreta se tiene. Pensaré en ello.


_________________
http://sentidodelamaravilla.blogspot.com
Volver arriba
Ver perfil de usuario Enviar mensaje privado
Deavid
Administrador
Administrador



Registrado: Feb 05, 2005
Mensajes: 6470
Ubicación: Ontinyent (Valencia)
MensajePublicado: Mar Feb 14, 2012 3:46 pm    Asunto: Responder citando

Si os digo la verdad, jamás me he parado a mirar las máquinas de Turing. Siempre que les he dado un vistazo me ha parecido que sencillamente son una formalidad matemática y que están bastante lejos de la práctica.
(por supuesto, hay muchas similitudes entre la máquina de turing y la computación actual)

Sobre el problema de la parada (saber si un programa algún momento de la ejecución realizará una operación determinada), si me gustaría comentar algunas cosas, pero dejando de lado las máquinas de turing.

De una forma genérica, se puede decir que no se puede saber si realizará una operación X sin ejecutar el propio programa para comprobarlo.

Si hablamos de si realizará la operación X usando alguna de las posibles entradas Y y éstas son infinitas entonces se necesita infinito tiempo para conocer el resultado (para un programa que jamás realiza la operación X)

Pero eso es en general. A la práctica las cosas son muy distintas (ha cambiado mucho el mundo de la informática desde 1936, vaya..). Hay ciertos casos donde sí es posible averiguar valores y datos de antemano. Me gustaría comentar algunos que me vienen a la cabeza.

Creo que el ejemplo más claro son los compiladores de C y C++. Estos programas, mirando el código fuente del programa a compilar son capaces de reconocer muchísimos patrones y saber cual será el resultado de una función o rutina ... ¡sin ni siquiera haberla ejecutado!
Son programas deductivos, que aplican varios análisis al código fuente y llegan a distintas conclusiones... que luego usan para eliminar código del programa compilado y así obtener más velocidad.
Hay unos cuantos artículos sobre esto por si a alguien le pica:
http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html
http://blog.regehr.org/archives/213

La programación funcional gira también en este sentido. Separa lo que se puede traducir como una f(x)->y (código funcional puro) del código imperativo. De este modo, lenguajes como Haskell pueden saber el resultado de una función sin haberla ejecutado (la ejecutaron antes con la misma entrada y está garantizado que tiene la misma salida). Y las funciones puras se pueden analizar a fondo, generalmente nunca son infinitas, y si lo son, a partir del programa se puede deducir para qué tipo de entradas son infinitas.

Por otra parte, si el problema en realidad no es que queramos saber el resultado de un programa, sino que queremos tener controlado qué hace (para evitar o limitar el daño de un posible malware), entonces existen otras opciones interesantes.

Los antivirus, por ejemplo, buscan cadenas de instrucciones de virus conocidos dentro de los programas. El problema de esto es que los virus desconocidos pasan inadvertidos. También usan heurística, básicamente porque reconocen que tipo de secuencias de instrucciones son típicas para un virus.

También podemos ir al extremo contrario, al certificado digital de los programas. Los certificados digitales no se pueden falsear, por lo que si un tercero modifica el programa, el certificado digital falla. (Esto se usa en la mayoría de distribuciones de Linux para instalar programas)

Y si queremos tener controlado un proceso, también tenemos otras opciones:

Los procesadores a día de hoy tienen unos niveles de seguridad y separan el User Space (los programas del usuario) del Kernel Space (sistema operativo), la CPU impide que un programa del User Space tenga acceso directo a los recursos de la máquina. Cualquier cosa tiene que pasar a través del sistema operativo, por lo que este último puede limitarle los accesos.

También empieza desde hace poco a desarrollarse el tema del "sandboxing", que viene a ser a hacerle creer al proceso que está en una máquina con unos recursos... que son virtuales. Donde pueda hacer lo que quiera, pero no afectará ni a nuestros ficheros ni nuestros recursos. Aún queda mucho pendiente aquí. En ese aspecto prácticamente ningún lenguaje o programa permite el sandboxing. Actualmente lo que tenemos son máquinas virtuales, pero no sirve demasiado bien la virtualización para esto.

Sobre el tema de permisos, de hacer que el sistema operativo deniegue toda operación sospechosa, existe un desarrollo llamado SELinux que es muy paranoico y se le determina qué puede hacer exactamente cada programa. Y todo uso fuera de lo que se le determina lo prohíbe.
http://en.wikipedia.org/wiki/Security-Enhanced_Linux

Y por último, comentar programas como Valgrind, que realizan un análisis exaustivo del uso de la memoria de un programa mientras éste se ejecuta y detecta cualquier anomalía. Esta aproximación es muy lenta, pero revela posibles errores que podrían facilitar a un hacker influir al programa. Es útil para revisar los programas antes de distribuirlos a los usuarios.


_________________
Estoy haciendo un juego... en Linux
Volver arriba
Ver perfil de usuario Enviar mensaje privado Enviar email Visitar sitio web del autor MSN Messenger
odo
Cacique
Cacique



Registrado: Feb 14, 2005
Mensajes: 2616
MensajePublicado: Mar Feb 14, 2012 7:18 pm    Asunto: Responder citando

Deavid escribió:
Si os digo la verdad, jamás me he parado a mirar las máquinas de Turing. Siempre que les he dado un vistazo me ha parecido que sencillamente son una formalidad matemática y que están bastante lejos de la práctica.
[...]

Pero eso es en general.


Claro, pero es que la "utilidad" de estos modelos es estudiar la computación en general y poder demostrar que hay ciertos problemas que no se pueden resolver de forma general mediante un algoritmo. De esta forma se puede demostrar que no es posible programar un ordenador para realizar ciertas tareas y que es necesario abordar esos problemas de otro modo, por ejemplo con algoritmos aleatorios o con algoritmos que funcionen para casos concretos, como los que tú has mencionado.

Digamos que son dos caras de la misma moneda: primero se demuestra que cierto problema no es resoluble por algoritmos en general y luego se busca una solución de compromiso. Creo que ambas cosas son interesantes y necesarias y que se apoyan la una en la otra.


_________________
http://sentidodelamaravilla.blogspot.com
Volver arriba
Ver perfil de usuario Enviar mensaje privado
odo
Cacique
Cacique



Registrado: Feb 14, 2005
Mensajes: 2616
MensajePublicado: Mar Feb 14, 2012 8:10 pm    Asunto: Responder citando

Deavid escribió:

La programación funcional gira también en este sentido. Separa lo que se puede traducir como una f(x)->y (código funcional puro) del código imperativo. De este modo, lenguajes como Haskell pueden saber el resultado de una función sin haberla ejecutado (la ejecutaron antes con la misma entrada y está garantizado que tiene la misma salida). Y las funciones puras se pueden analizar a fondo, generalmente nunca son infinitas, y si lo son, a partir del programa se puede deducir para qué tipo de entradas son infinitas.


No sé muy bien qué quieres decir con función "pura" (¿que no tiene entrada/salida?) pero me parece que lo que estás afirmando está muy lejos de la realidad. De hecho, los lenguajes funcionales están basados en las funciones parciales recursivas, otro modelo de computación equivalente a las máquinas de Turing, a las que se les aplica el problema de la parada, el Teorema de Rice y todo el arsenal de la teoría de la computabilidad. Es más, es fácil demostrar que simplemente con tener la posibilidad de usar la sentencia "while" los programas resultantes tampoco se pueden analizar automáticamente.


_________________
http://sentidodelamaravilla.blogspot.com
Volver arriba
Ver perfil de usuario Enviar mensaje privado
Deavid
Administrador
Administrador



Registrado: Feb 05, 2005
Mensajes: 6470
Ubicación: Ontinyent (Valencia)
MensajePublicado: Mar Feb 14, 2012 10:09 pm    Asunto: Responder citando

odo escribió:

No sé muy bien qué quieres decir con función "pura" (¿que no tiene entrada/salida?) pero me parece que lo que estás afirmando está muy lejos de la realidad. De hecho, los lenguajes funcionales están basados en las funciones parciales recursivas, otro modelo de computación equivalente a las máquinas de Turing, a las que se les aplica el problema de la parada, el Teorema de Rice y todo el arsenal de la teoría de la computabilidad. Es más, es fácil demostrar que simplemente con tener la posibilidad de usar la sentencia "while" los programas resultantes tampoco se pueden analizar automáticamente.


No, función pura es aquella que no tiene efectos colaterales. No se le permite leer más que la entrada y no se le permite escribir nada (excepto el retorno de datos).

Los lenguajes funcionales son principalmente funciones puras. Las imperativas (que son las que llevan los while y los for) se minimizan al máximo.

Sobre el tema del análisis, normalmente lo recomendable es que los procedimientos tengan un comportamiento esperado. Las funciones no deben aceptar cualquier cosa y sacar cualquier cosa. Deben garantizar el funcionamiento correcto para un rango de valores posibles. Y a menudo es posible analizar y ver para qué rango de entradas produce una salida correcta.

En mi opinión, los estándares de programación tienden hacia un modelo mucho más analizable y comprensible.

Eso sí, lo que será imposible ahora y siempre es hacer un análisis completo sobre código máquina. Y creo que la máquina de turing cuando habla de programa, está pensando en código máquina, no en programa como source. Pero eso se debe a que el código máquina está pensado únicamente para ser ejecutado por el procesador lo más rápido posible.


_________________
Estoy haciendo un juego... en Linux
Volver arriba
Ver perfil de usuario Enviar mensaje privado Enviar email Visitar sitio web del autor MSN Messenger
odo
Cacique
Cacique



Registrado: Feb 14, 2005
Mensajes: 2616
MensajePublicado: Mar Feb 14, 2012 10:31 pm    Asunto: Responder citando

Deavid escribió:

No, función pura es aquella que no tiene efectos colaterales. No se le permite leer más que la entrada y no se le permite escribir nada (excepto el retorno de datos).


Eso es lo que decía yo, que no se comunica con el exterior, sólo recibe los datos sobre los que tiene que operar y devuelve el resultado.

Pues en ese caso, es IMPOSIBLE determinar en general si la función devolverá algo o no. Precisamente ese es el enunciado del problema de la parada.

Deavid escribió:

Los lenguajes funcionales son principalmente funciones puras. Las imperativas (que son las que llevan los while y los for) se minimizan al máximo.


El que sea función pura o no poco tiene que ver con que use while, recursión u otra cosa.

Deavid escribió:

Sobre el tema del análisis, normalmente lo recomendable es que los procedimientos tengan un comportamiento esperado. Las funciones no deben aceptar cualquier cosa y sacar cualquier cosa. Deben garantizar el funcionamiento correcto para un rango de valores posibles. Y a menudo es posible analizar y ver para qué rango de entradas produce una salida correcta.


A menudo puede que sea posible, pero en general, como te digo arriba, está demostrado matemáticamente que es imposible.

Deavid escribió:

En mi opinión, los estándares de programación tienden hacia un modelo mucho más analizable y comprensible.


Sí, pero el imposibilidad de analizar completamente el comportamiento del código es una propiedad inherente a cualquier modelo de computación suficientemente potente. Hay lenguajes de programación que sólo permiten escribir código que siempre finaliza, pero en ese caso es fácil probar con un argumento de diagonalización que hay funciones que no se pueden programar en ese lenguaje. Por otro lado, si el lenguaje permite alguna construcción que puede no llegar a terminar entonces se le aplica el problema de la parada.

Deavid escribió:

Eso sí, lo que será imposible ahora y siempre es hacer un análisis completo sobre código máquina. Y creo que la máquina de turing cuando habla de programa, está pensando en código máquina, no en programa como source. Pero eso se debe a que el código máquina está pensado únicamente para ser ejecutado por el procesador lo más rápido posible.


No tiene nada que ver el hecho de que sea código máquina, de alto nivel o de cualquier otro tipo. Cualquier modelo de computación suficientemente potente (y, como decía antes, basta con que haya una construcción "while" o similar) tendrá un problema de la parada indecidible (de hecho, eso pasa también para modelos MÁS potentes que las máquinas de Turing, y ahí enganchamos con la hipercomputación). La demostración es sencilla: en un lenguaje de ese tipo podemos simular cualquier máquina de Turing, es decir, escribir un programa correspondiente a una máquina de Turing dada. Si pudiéramos saber si los programas de ese lenguaje van a terminar o no, podríamos resolver el problema de la parada para las máquinas de Turing sin más que escribir el programa P correspondiente a la máquina de Turing que queremos saber si para o no y analizar P para ver si termina.

Ese es un hecho fundamental de la teoría de la computabilidad: cualquier modelo de computación suficientemente potente (nótese la similitud con el Teorema de incompletitud de Gödel) es equivalente a las máquinas de Turing y, por tanto, es imposible analizar su comportamiento algorítmicamente.


_________________
http://sentidodelamaravilla.blogspot.com
Volver arriba
Ver perfil de usuario Enviar mensaje privado
Deavid
Administrador
Administrador



Registrado: Feb 05, 2005
Mensajes: 6470
Ubicación: Ontinyent (Valencia)
MensajePublicado: Mie Feb 15, 2012 4:01 pm    Asunto: Responder citando

Vamos a ver si me explico.... Rolling Eyes

Primero, las funciones puras no son máquinas de turing, y no, no es la definición del problema de la parada.

Ya sé que crees que estoy completamente equivocado. Pero deja que intente explicártelo (aunque tengo pocos conocimientos sobre Turing como para hacerlo).

Para tí un programa es algo que procesa instrucciones, lee registros y graba registros. La máquina de turing es algo así como instrucciones de atrás, adelante, lee, y graba registro.

Bien, según esa definición, una función pura no es un programa.
Una función pura no ejecuta instrucciones, no escribe registros y no lee registros. Es una cosa distinta.

Se parecen más bien a funciones matemáticas.

Si yo digo: f(x) = 2 ^ ((x / 3) + 1) + x

¿Es eso una instrucción? son varias?
¿está escribiendo registros?
¿lee registros?

Depende de como lo mires.

Matemáticamente es una relación, para todo x existe un f(x).

Obviamente, cuando traduces esto a un lenguaje imperativo, aparecen las lecturas, las escrituras y las instrucciones:

Código:

double f(double x) {
  double x1 = x / 3;
  x1 += 1;
  double x2 = pow(2,x1);
  x2 += x;
  return x2;
}


Y es en este código, o en su homólogo assembler, donde aplicas el problema de la parada. Siendo un código no trivial (lleva la llamada a pow), es imposible predecir si devolverá o se quedará infinitamente calculando.

Ahora bien, si supiéramos que pow(x,y) está garantizado que retorna en un tiempo finito para todo x == 1 y todo y == 1, sabríamos que esta función también esta garantizado que devuelve también en tiempo finito para x = 0. El resto simplemente lo desconocemos.

Pero olvidémonos de lo imperativo. Miremos de nuevo la función matemática:

f(x) = 2 ^ ((x / 3) + 1) + x

Dirías que puedes calcular f(x) para cualquier x en un tiempo finito? Yo creo que la respuesta es sí.

Por lo tanto, un programa funcional que use esa definición de f(x) se sabrá que la función retorna en tiempo finito.

Quiero que entiendas que la clave del análisis es esa, el que no existen instrucciones sino definiciones. No son máquinas de turing. El resultado compilado sí lo es.


Cita:
El que sea función pura o no poco tiene que ver con que use while, recursión u otra cosa.


Sí que tiene que ver, hay sentencias que generalmente están prohibidas en las funciones puras (dependiendo del lenguaje también). El for y while tradicional son algunas de ellas.

El motivo es que está prohibido asignar variables, así que un for(;;i++) no es válido para una función pura. Del mismo modo, en un while, la comparación siempre evaluaría lo mismo. Carece de sentido.
El único bucle que existe es el foreach o el for..in, que viene a decir, para cada x en xs, haz esto.
Pero como el concepto "haz" es imperativo, generalmente tampoco funcionan los foreach. Se usa algo parecido pero con expresiones (más matemático) [ x*2 for x in xs ] (algo así como un conjunto compuesto de x*2 por cada x en xs)


Cita:
(...) La demostración es sencilla: en un lenguaje de ese tipo podemos simular cualquier máquina de Turing, es decir, escribir un programa correspondiente a una máquina de Turing dada. Si pudiéramos saber si los programas de ese lenguaje van a terminar o no, podríamos resolver el problema de la parada para las máquinas de Turing sin más que escribir el programa P correspondiente a la máquina de Turing que queremos saber si para o no y analizar P para ver si termina.


Es que empiezas con una premisa falsa: "en un lenguaje de ese tipo podemos simular cualquier máquina de Turing"
Si el lenguaje no es imperativo, sólo podrás hacer eso si usas la parte imperativa del lenguaje (que suele existir). Entonces tendrás un programa imperativo (por mucho que esté programado en Haskell) y por lo tanto te quedarás igual que has empezado.

En cambio, algunas máquinas de turing sí pueden ser expresadas de forma no imperativa (como por ejemplo funciones matemáticas). Entonces sí puedes determinar si terminan o no.

Lo que te vengo a decir desde el principio es que las máquinas de turing son una cosa demasiado genérica y demasiado inherente a la forma de trabajo de la CPU. Y es obvio, muy obvio, que no se pueda predecir el comportamiento de un programa desde ese punto de vista.

Te voy a poner otro ejemplo, las bases de datos usan SQL. El SQL es en gran medida un lenguaje funcional. Por tanto, mientras se use únicamente la parte funcional con un conjunto de datos finito, el servidor (teniendo infinita RAM, infinito disco e infinito tiempo) devolverá el resultado en un tiempo determinado.

Por ejemplo:
Código:
SELECT idusuario, name FROM users WHERE email ILIKE '%@hotmail.com'


Devuelve en tiempo finito.

Y estamos igual que al principio. No hay instrucciones.
No le estoy diciendo: abre la tabla users, lee el email, compara, si True, almacena el registro.
Le estoy diciendo: Dame un conjunto de idusuario y name para cada user en users donde el email se parezca a esto.

Internamente es imperativo, pero originalmente no lo era. Excepto error en la transcripción a imperativo, el programa termina siempre.


_________________
Estoy haciendo un juego... en Linux
Volver arriba
Ver perfil de usuario Enviar mensaje privado Enviar email Visitar sitio web del autor MSN Messenger
odo
Cacique
Cacique



Registrado: Feb 14, 2005
Mensajes: 2616
MensajePublicado: Mie Feb 15, 2012 5:45 pm    Asunto: Responder citando

Deavid escribió:

Pero olvidémonos de lo imperativo. Miremos de nuevo la función matemática:

f(x) = 2 ^ ((x / 3) + 1) + x

Dirías que puedes calcular f(x) para cualquier x en un tiempo finito? Yo creo que la respuesta es sí.


Claro, porque esa función es total. La cuestión es que la computabilidad estudia funciones que no necesariamente son totales, de ahí el nombre de funciones parciales recursivas. En general, dada la DEFINICIÓN de una función computable es IMPOSIBLE determinar algorítmicamente para qué valores está definida (parará) y para qué valores no. Claro, si te restringes a funciones totales como la que usas arriba, el resultado es trivial: siempre están definidas, así que siempre pararán.

Deavid escribió:

Quiero que entiendas que la clave del análisis es esa, el que no existen instrucciones sino definiciones. No son máquinas de turing. El resultado compilado sí lo es.


Lo que yo quiero que entiendas es que esa distinción es totalmente irrelevante para el problema de la parada. El problema de la parada para una función computable f: N -> N se define como determinar si para una entrada x el valor f(x) está definido o no. Como ves, no se habla de instrucciones, ni de registros, ni de nada semejante. Ahora bien, al ser una función computable, tendrá asociada una máquina de Turing, una función parcial recursiva, un programa imperativo... Todos ellos implementaciones diferentes de la misma función. Uno de los resultados fundamentales de la teoría de la computabilidad es que esos modelos son todos equivalentes: lo que se puede hacer en uno se puede hacer en todos los demás.

Deavid escribió:

Es que empiezas con una premisa falsa: "en un lenguaje de ese tipo podemos simular cualquier máquina de Turing"


Es que creo que no comprendes el concepto de simulación. Simular no quiere decir "ser igual a". Lo que quiere decir es que se reproducir el comportamiento de un sistema dentro de otro. Y claro que en Haskell se puede simular una máquina de Turing. Para cada máquina de Turing M existe una función pura que hace exactamente los mismo cálculos que la máquina M. No es que lo diga yo, es que un hecho bien conocido en la teoría de la computación. Sin más que una búsqueda rápida en Google mira lo que encuentro (sacado de http://www-cs-students.stanford.edu/~blynn/c/ch09.html bajo el apartado "Purity"):

Cita:

In fact, initially I thought the situation was worse: without variables or anything else resembling a tape cell of a Turing machine, how could a pure function possibly be as powerful?

This is where the aforementioned theory comes in handy. It turns out you can cleverly encode the integers as strange-looking pure functions, and feed these into other pure functions to perform operations on them. A clever trick involving a fixed-point operator, such as the Y combinator, allows recursion, and this leads to a proof that pure functions and Turning machines can compute the same functions.


(Por cierto, el proceso de codificación al que se refiere el autor es lo que a veces se conoce como gödelización y es una poderosa herramienta a la hora de demostrar la equivalencia entre unos sistemas y otros y a la hora de estudiar sus limitaciones).

Es que de hecho, no sé si lo sabes, el lenguaje Haskell (y otros lenguajes funcionales) están basados en el cálculo Lambda, que es otro modelo de computación equivalente a las máquinas de Turing:

http://en.wikipedia.org/wiki/Lambda_calculus

Deavid escribió:

En cambio, algunas máquinas de turing sí pueden ser expresadas de forma no imperativa (como por ejemplo funciones matemáticas). Entonces sí puedes determinar si terminan o no.


No sólo algunas si no TODAS. TODAS las máquinas de Turing se pueden expresar como funciones matemáticas. De hecho, se pueden expresar como funciones parciales recursivas (http://en.wikipedia.org/wiki/Partial_recursive_function). Por tanto, es IMPOSIBLE analizar todas las funciones para saber si paran o no porque, de paso, estaríamos analizando todas las máquinas de Turing.

De hecho, incluso podríamos ir un paso más allá. Cualquier máquina de Turing podría ser definida mediante un POLINOMIO con coeficientes enteros. Eso es precisamente lo que demostró Matiyasevich para dar respuesta (negativa) al décimo problema de Hilbert:

http://en.wikipedia.org/wiki/Diophantine_set

En resumen, no, no es cierto que funciones puras y programación imperativa sean cosas distintas en cuanto a capacidad computacional y en cuanto a posibilidad de determinar si terminarán en un tiempo finito.


_________________
http://sentidodelamaravilla.blogspot.com
Volver arriba
Ver perfil de usuario Enviar mensaje privado
odo
Cacique
Cacique



Registrado: Feb 14, 2005
Mensajes: 2616
MensajePublicado: Mie Feb 15, 2012 7:09 pm    Asunto: Responder citando

Por cierto, buscando un poco, he encontrado una implementación en Haskell de máquinas de Turing:

http://scienceblogs.com/goodmath/2007/02/basics_the_turing_machine_with_1.php

(hay más de este tipo por ahí).

Incluso aún más interesante: resulta que una parte reducida de Haskell (en concreto el sistema de verificación de tipos) es también Turing completo (equivalente a las máquinas de Turing) y por tanto presentaría el problema de la parada:

http://www.haskell.org/pipermail/haskell/2006-August/018355.html

(Pero bueno, esto es una curiosidad, porque los desarroladores de Haskell siempre han sido bastante afines a la computabilidad y se dedican a "chorradas" como esta.)

La cosa es que lo mismo sucede con cualquier otro lenguaje de programación: o es capaz de expresar cualquier máquina de Turing (y, por tanto, es indecidible) o hay algunas cosas que no puede computar. La vida es así, qué le vamos a hacer.


_________________
http://sentidodelamaravilla.blogspot.com
Volver arriba
Ver perfil de usuario Enviar mensaje privado
odo
Cacique
Cacique



Registrado: Feb 14, 2005
Mensajes: 2616
MensajePublicado: Sab Feb 18, 2012 12:53 pm    Asunto: Responder citando

Volviendo al tema original del post, he estado pensando y sí que se puede aplicar un argumento de diagonalización para demostrar que no puede existir un analizador de malware perfecto. 

Supongamos que tenemos A, un programa que cuando recibe el código de otro programa B, lo analiza y nos dice si es B es malware o no en un tiempo finito y acertando siempre. Supondremos, además, que A no es malware (si no, mal vamos). Supongamos, finalmente, que hay al menos un programa M que es malware. 

A partir de A y M construímos un programa R del siguiente modo:

Cuando R recibe el código de un programa B, lo analiza usando A y si A dice que B no es malware, entonces ejecuta M. Si A decide que B es malware, entonces R termina sin ejecutar nada adicional. En pseudcódigo:

R(B):
  Si no A(B):
    M

Ahora viene la diagonalización. ¿Qué pasa cuando ejecutamos R con B=R, es decir, cuando le pedimos que analice su propio código? 

Si se da el caso de que A dice que R no es malware, entonces R ejecutará M, que es malware, contradiciendo lo que había dicho A. Si, por el contrario, A determina que R es malware entonces R sólo ejecutará A y ningún código adicional, por lo que no puede ser considerado malware (ya que A no lo es) lo que es una contradicción con que A haya determinado que R sí es malware. 

La contradicción viene de suponer la existencia de A y, por tanto, podemos concluir que no es posible programar un analizador de malware perfecto. QED.


_________________
http://sentidodelamaravilla.blogspot.com
Volver arriba
Ver perfil de usuario Enviar mensaje privado
Mimoide
Terrateniente
Terrateniente



Registrado: Feb 05, 2005
Mensajes: 523
MensajePublicado: Dom Feb 19, 2012 4:38 pm    Asunto: Responder citando

Muy bueno, jaja. Sólo un comentario. El razonamiento supone que todo aquel programa que sobre una determinada entrada 'ejecuta malware' lo es él mismo, con lo que en tal caso toda máquina universal lo sería. ¿Hasta qué punto es esto deseable?
Si la distinción se hace sobre pares programa-entrada la cosa tiene fácil arreglo: basta sustituir en la demostración 'A(B)' por 'A((B,'B'))', como en el teorema de la parada. Pero me da que así el concepto pierde mucho interés.
Otro tema es si es posible dar una noción general de 'ejecutar un programa dentro de otro'. Una que no considere maliciosa esas futuribles (o no tanto, no me ha quedado claro) 'sandbox' de las que hablaba Deavid más abajo, por contener equivalentes funcionales de programas que lo son.

Volver arriba
Ver perfil de usuario Enviar mensaje privado
Mimoide
Terrateniente
Terrateniente



Registrado: Feb 05, 2005
Mensajes: 523
MensajePublicado: Dom Feb 19, 2012 4:53 pm    Asunto: Responder citando

http://home.dei.polimi.it/zanero/papers/open-problems.pdf
En la tercera página da la definición original de de virus debida a Fred Cohen.

Volver arriba
Ver perfil de usuario Enviar mensaje privado
odo
Cacique
Cacique



Registrado: Feb 14, 2005
Mensajes: 2616
MensajePublicado: Dom Feb 19, 2012 4:56 pm    Asunto: Responder citando

Mimoide escribió:
Muy bueno, jaja. Sólo un comentario. El razonamiento supone que todo aquel programa que sobre una determinada entrada 'ejecuta malware' lo es él mismo, con lo que en tal caso toda máquina universal lo sería. ¿Hasta qué punto es esto deseable?


Bueno, eso lo hacía sobre el supuesto (razonable, creo yo) de que si se ejecuta el malware se efectuará alguna acción "maligna" (borrar programas, infectar otros ejecutables, mandar span a todos tus contactos...).

Pero en realidad creo que no hace falta ni suponer eso. Date cuenta de que R sólo hace dos cosas: ejecutar A(B) y (quizá) ejecutar M. Entonces R sería malware (en el caso de ejecutar M) con cualquier definición de malware que sea invariante por el hecho de añadir a un programa algunas instrucciones al principio. Creo que es muy poco restrictivo. Para otras definiciones de malware sin esa propiedad (que quizá no resultaran demasiado naturales) muy posiblemente se podría adaptar la demostración haciendo alguna suposición extra sobre A (es decir, imponiendo alguna extra retricción al antivirus). Yo creo que se podría solventar, pero habría que ver la definición en cada caso.

Mimoide escribió:

Otro tema es si es posible dar una noción general de 'ejecutar un programa dentro de otro'. Una que no considere maliciosa esas futuribles (o no tanto, no me ha quedado claro) 'sandbox' de las que hablaba Deavid más abajo, por contener equivalentes funcionales de programas que lo son.


En la demostración que yo he puesto no es tanto "ejecutar un programa dentro de otro" como "concatenar programas". En ese caso no se está ejecutando M en una "sandbox" sino en la máquina "real". Date cuenta de que (dependiendo de la definición de malware) en mi demostración incluso se permitiría que A hiciera una "ejecución" simulada de los programas que recibe para saber si o no malware.


_________________
http://sentidodelamaravilla.blogspot.com
Volver arriba
Ver perfil de usuario Enviar mensaje privado
Mimoide
Terrateniente
Terrateniente



Registrado: Feb 05, 2005
Mensajes: 523
MensajePublicado: Lun Feb 20, 2012 4:03 pm    Asunto: Responder citando

Ok.
Cita:
En la demostración que yo he puesto no es tanto "ejecutar un programa dentro de otro" como "concatenar programas". En ese caso no se está ejecutando M en una "sandbox" sino en la máquina "real".

Sí, sí, claro. Era má que nada por dar conversación. De buscarle por ahí las cosquillas a la definición no se saca ninguna objección a tu razonamiento. Pero es algo que, de querer concretarla, creo que habría que tener en cuenta.

Volver arriba
Ver perfil de usuario Enviar mensaje privado
odo
Cacique
Cacique



Registrado: Feb 14, 2005
Mensajes: 2616
MensajePublicado: Lun Feb 20, 2012 4:53 pm    Asunto: Responder citando

Mimoide escribió:
Ok.
Cita:
En la demostración que yo he puesto no es tanto "ejecutar un programa dentro de otro" como "concatenar programas". En ese caso no se está ejecutando M en una "sandbox" sino en la máquina "real".

Sí, sí, claro. Era má que nada por dar conversación. De buscarle por ahí las cosquillas a la definición no se saca ninguna objección a tu razonamiento. Pero es algo que, de querer concretarla, creo que habría que tener en cuenta.


Sí, claro, estoy de acuerdo. Pero creo que la demostración funcionaría para casi todas las definiciones "razonables" de malware. De hecho, es una demostración que se podría adaptar fácilmente para probar la imposibilidad de analizadores de otras muchas propiedades.

Por otro lado, aprovecho para darme un poco autobombo y dejar un enlace a la entrada que he publicado hoy en mi blo, en la que hablo de máquinas de Turing y el problema de la parada, desde el punto de vista de una novela de ciencia ficción de Neal Stephenson:

http://sentidodelamaravilla.blogspot.com/2012/02/matematicas-y-ciencia-ficcion-las.html


_________________
http://sentidodelamaravilla.blogspot.com
Volver arriba
Ver perfil de usuario Enviar mensaje privado
sed29
Peregrino
Peregrino



Registrado: Apr 07, 2012
Mensajes: 3
MensajePublicado: Vie Abr 06, 2012 11:41 pm    Asunto: Responder citando

Hola..! Que buena información, siempre he pensado que para evitarnos eso, es mejor tener un buen antivirus funcionando en nuestro pc he utilizado vario y em han servido especialmente el avast es exlentente, con mi cambio nde ordenador ahora mismo tengo funcionando el ZenOK antivirus gratis www.zenok.com/es/free-antivirus/ y me ha servido muchísimo. Cool
Volver arriba
Ver perfil de usuario Enviar mensaje privado
Mostrar mensajes de anteriores:   
Publicar nuevo tema   Responder al tema    Foros de discusión -> Ciencia Todas las horas son GMT + 1 Hora
Página 1 de 1

 
Cambiar a:  
Puede publicar nuevos temas en este foro
No puede responder a temas en este foro
No puede editar sus mensajes en este foro
No puede borrar sus mensajes en este foro
No puede votar en encuestas en este foro
Forums ©





acer_468x60.gif
Web site powered by PHP-Nuke

Web site engine's code is Copyright © 2003 by PHP-Nuke. All Rights Reserved. PHP-Nuke is Free Software released under the GNU/GPL license.
server load avg:0.65 / php time:85 ms