(Desde 2008 que no escribo en este blog; en esta serie de posts sobre esteganografía quizás reinicie mis posts al blog, o quizás no… ya veremos)
Hace unos días presenté un trabajo en JAIIO/WSegI sobre este tema, que pueden ver aquí: http://www.41jaiio.org.ar/WSegI_Contribuciones. A continuación presento brevemente y de forma muy informal sobre qué se trata este artículo. Los detalles formales y la matemática están en el paper.
Esteganografía es la disciplina que estudia el envío de mensajes escondidos (dentro de mensajes u objetos), de forma que no se sospeche que estos están allí. Un ejemplo típico es: un individuo A le quiere enviar un mensaje a un individuo B, pero hay un individuo C que intercepta los mensajes. La idea es que es necesario poder enviar los mensajes escondidos de forma tal que C ni siquiera sospeche que estos están allí.
En el caso de esteganografía de textos, se envían textos de aspecto inocente que ocultan, dentro de ellos, otros mensajes (que pueden ser textos o bits arbitrarios). Una forma de esteganografía de textos trivial y que todos conocen es partir de un texto como «ahora lo veo», y agregar mayúsculas al mismo en lugares que indiquen qué letras son las que contienen el segundo mensaje escondido: «aHOra Lo veO». En este caso el submensaje es, por supuesto, «hola». Claro que la esteganografía estudia métodos más difíciles de detectar que éste.
El segundo concepto interesante que se usa en este proyecto son las cadenas de Markov. En vez de explicarlas como un modelo de proceso estocástico y explicar sus propiedades matemáticas, voy a tratar de dar una intuición sencilla de lo que son estos objetos.
Supongamos que tengo un texto, que es una secuencia de palabras como «w1 w2 w3 w4 …». Hay varias formas de analizar este texto, una bastante sencilla es por ejemplo contar cuantas veces aparece cada palabra. Por ejemplo «la» aparece 1000 veces, «casa» aparece 300, etc. Más interesante, son las combinaciones de dos palabras, lo que se conoce como bigramas. Podemos decir, «la casa» aparece 120 veces; «el perro», 50, y así sucesivamente.
Estas propiedades que extraigo de los textos definen un modelo de lenguaje. A partir de las mismas puedo entender cómo funciona un lenguaje a través de lo que veo en textos (a partir de sus propiedades estadísticas), y también puedo hacer cosas interesantes como generar nuevos textos haciendo de cuenta que mi modelo representa perfectamente el lenguaje. Más sobre esto luego.
Si usamos un poco de probabilidad por un momento, podemos decir algo un poco más interesante aún, que sólo trabajar con las frecuencias de los bigramas. Usando una notación de probabilidad condicional como
P(Xn+1 = casa | X n = la) = 0.5
estamos obteniendo una caracterización más interesante. Lo que esto significa es: si la palabra número n en el texto es «la», la probabilidad que la siguiente palabra sea «casa» es 0.5. Es decir, la mitad de las veces que aparece la palabra «la», la siguiente palabra es «casa». Estas probabilidades (que se pueden computar fácilmente desde las frecuencias) definen la cadena de Markov, pero la forma más familiar para los programadores de la cadena de Markov es en su forma gráfica, que es una máquina de estados como la siguiente:
donde las transiciones son las probabilidades condicionales, y los estados son las palabras (y generalmente hay un estado inicial para indicar el inicio). Por supuesto las cadenas de Markov no funcionan sólo con palabras, esto es sólo para los efectos de este caso particular de análisis sencillo de textos.
A partir de un texto cualquiera puedo extraer una cadena de Markov que modela el lenguaje que se usa en el mismo. Esto (y otros modelos de lenguaje) tiene algunas ventajas muy interesantes para nosotros:
1- dada una cadena de Markov y un texto cualquiera, puedo averiguar cuál es la probabilidad que el texto haya sido generado por esa cadena de Markov… puedo hacer, por ejemplo, un detector simple de lenguaje español o inglés
2- más interesante para nuestros propósitos: dada una cadena de Markov, puedo generar nuevos textos al azar. Estos textos generados se parecerán en cuanto al lenguaje usado, al texto a partir del cual se extrajo la cadena.
Ambas ventajas se obtienen a partir de una idea sencilla. Supongamos que yo quiero saber cuál es la probabilidad de que la frase «el perro azul» sea generado por una cadena de Markov con estados que son palabras. Todo lo que tengo que hacer es calcular las probabilidades de P(perro|el) y P(azul|perro) y multiplicarlas entre sí:
P(el perro azul) = P(Xn+1 = perro | Xn = el) * P(Xn+1 = azul | Xn = perro)
En la siguiente parte, explicaré cómo es que se usan las cadenas de Markov en esteganografía, y contaré un poco más sobre mi trabajo en este tema.
Las conferencias de la escuela de verano fueron escalando en dificultad e interés: empezaron siendo un poco básicas y enseguida se pusieron muchísimo más atractivas, y algunas de ellas fueron claramente reveladoras. Pero más allá de las conferencias en sí, lo que más me atrae de esta experiencia es la oportunidad de estar acá con gente de todo el mundo y de todo Estados Unidos, y de algunas de las universidades más importantes del mundo, compartiendo los avances y dificultades de nuestras investigaciones, lo que hace que haya un continuo clima intelectual que es absolutamente fascinante. Y quizás de algún modo, ése es el propósito verdadero de esta escuela de verano: juntar a gente de todo el mundo y de áreas diversas a investigar sobre temas relacionados.
NKS en sí, si cambiará el mundo o no lo sabremos en muchos años, como siempre en estos casos, pero sin duda como metodología permite acceder a ciertos nuevos puntos de conocimiento, y sin duda en el libro en sí de forma inequívoca Wolfram con sus colaboradores nuevamente encuentra soluciones a problemas interesantes: la universalidad de 110, el sistema de axiomas más corto de la lógica, etcétera, además de brindar un extenso y ordenado recorrido por muchísimas áreas de la ciencia y la matemática, y de hacer un recorrido exhaustivo por los estudios de los autómatas celulares y de otros tipos de sistemas simples también. Y por otra parte he visto aquí algunas otras cosas de las que, simplemente, no puedo decir más que W-O-W. Creo que Wolfram está a punto de hacerlo otra vez.
Estando aquí nosotros tenemos que desarrollar unos proyectos de investigación sobre complejidad, y el mío en este caso es sobre el análisis del grafo de demostraciones en lógica abstracta. Estoy muy feliz con este proyecto, estoy muy feliz de estar haciendo investigación sobre algo que me fascina desde siempre, la lógica abstracta y sus fundamentos, y además tengo en muchas oportunidades el feedback, y apoyo de la gente de Wolfram Research o de Stephen Wolfram mismo! sobre el avance de este proyecto (de hecho, la idea inicial para el mismo fue de SW; es para tratar de avanzar sobre un problema abierto en lógica que yo no conocía).
Blog de Hernán Moraldo 