Lessons Learned: Fettisdagen y Semla

Fettisdagen, (martes de carnaval). Fet es grasa, mientras tisdag es martes. El sufijo en es el artículo determinado. Por lo tanto, el martes graso

Semla, Comida. Etimológicamente, viene de semilla. También llamado fastlagsbulle, es una berlinesa (bola de fraile, que le dicen) con crema y pasta de almendras en su interior.

SemlaFlickr
En el post sobre Lucía ya hemos hablado sobre lo sorprendentemente apegado que son los suecos a ciertas fiestas de origen religioso, incluso cuando solo el 23% de ellos dice cree en algo llamado dios (ya no decir "ser cristiano"). Este parece ser un nuevo caso de lo mismo.

En Argentina, así como en muchos (por no decir todos) países de América existe el carnaval. En otras palabras, festejar y comer antes de los 40 día de ayuno y penitencia por la Cuaresma que comienza el día siguiente, es decir, el Miércoles de Ceniza.

Acá, y en otros países nórdicos, no parece haber carnaval. Lo que sí hay es Fettisdagen. Éste podría ser un martes de lo más común, si no fuese porque se consumen enormes cantidades de semla.

Casualmente, ese martes me tocó ser el anfitrión del PhD fika (cuando los estudiantes de doctorado nos juntamos a tomar café y conversar), por lo me subí a la tradición y los invité con semla de distintos sabores. El sabor está dado por la crema, que puede ser común, de vainilla, con canela y otras variantes.

Los semlor (plural de semla) es algo tan popular en la cultura sueca que un detective de cuentos para chicos llamado Ture Sventon es adicto a estos (y también vuela en una alfombra mágica, pero no viene al caso).

Y este podría no ser único caso sueco de adición a semla. En el siglo XVII, rey Adolfo Federico habría muerto (literalmente) de un atracón después de clavarse 14 porciones de semla (tradicionalmente servidos con un tazón de leche caliente) como postre.

La receta, aquí.

Lessons Learned: Pubrunda

Pubunda, sustantivo. Gira trimetral entre bares. Runda es algo así como ronda o circuito.

Al menos en cuanto a educación superior se refiere, el ciclo lectivo sueco (llamado läsår) va de Agosto a Junio y está conformado por 2 términos: el de otoño (hösttermin) y el de primavera (vårtermin). Cada termino está a su vez dividido en dos períodos de estudios (läsperiod, normalmente referenciados como Lp1 al Lp4).

El primer jueves de cada läsperiod se realiza entre los estudiantes la pubrunda. En los períodos pares, ésta coincide con la semana siguiente a los exámenes, por lo que se vive un clima particularmente festivo y relajado. Anoche fue la correspondiente al Lp2 y pude participar por primera vez.

Empezando como a las 6 pm, el campus universitario se empieza a colmar de estudiantes, ávidos de visitar la mayor cantidad de pubs posibles. En cada departamento hay una organización de estudiantes que, entre otras cosas, regentea un pequeño pub o bar. Es una buena oportunidad para estas organizaciones de recaudar efectivo mientras que los estudiantes pueden beber y comer a relativo muy bajo costo. El precio típico de una cerveza es entre 20 y 30 SEK (coronas, menos de 20 pesos argentinos) y se puede conseguir una hamburguesa por 30 SEK. Digo relativamente barato, dado que en estos lares la cerveza suele estar más cerca de las 80 SEK, mientras que una sándwich al paso cuesta unas 60 SEK.

Se puede acceder a todos los pubs del campus con la tarjeta de la studentkår (la unión de estudiantes, que agrupa a todas las organizaciones) y cada miembro puede llevar a un invitado.

Incluso cuando todo el ambiente es muy estudiantil, hay algunas reglas muy estrictas. Por ejemplo, la capacidad de los lugares es limitada y por ninguna razón se puede acceder al lugar si éste llego a su número. En la puerta se llevan contadores de personas para garantizar esto. Otra restricción tiene que ver con beber alcohol fuera del pub. No se puede beber en los baños ni en los corredores o el exterior.

En general es un abiente divertido y se la pasa muy bien. Es una excelente excusa para visitar lugares, conocer gente y beber. Si bien no es muy práctico andar cambiado de bar (las colas en espera de que la gente salga pueden ser largas) mucha gente se divierte completando una especie de grilla de los lugares que visita o las marcas de cerveza que bebe, como la que se muestra a continuación:

No estoy muy seguro si hay algún tipo premio. Pero he notado cierta tendencia por este tipo de juegos. Por ejemplo, muchos bares tienen una noche a la semana que llaman quiz night o trivia night, donde se contestan cuestionarios de cultura general o historia de la ciudad. En algunos casos es sobre música o películas. Todo, al son de la bebida.

Otras lecciones aprendidas en Suecia, aquí

nos volveremos a ver

Un día como hoy, pero de la semana pasada me estaba subiendo a un avión con, por primera vez en mi vida, un ticket one-way. El destino: Gotemburgo (o Göteburg, como le dicen los locales). Pasó hace solo una semana y, sin embargo, siento que fue hace meses. Muchísimas cosas pasaron. Muchísima gente conocí. Muchísimas cosas aprendí. ¡Y espero con entusiasmo las que aún quedan por pasar, conocer y aprender!

Como me resulta complicado ordenar mis ideas en prosa, voy a por secciones:

La universidad

El lugar donde en el que voy a trabajar y estudiar durante los próximos años es el departamento de Data- och informationsteknik (o Computación Científica e Ingeniería, en criollo), en Chalmers. Físicamente queda ubicado en el edificio EDIT, en la sede Johanneberg. Allí ya tengo una oficina asignada y parece estar todo preparado para que empiece el 1º de Septiembre, según lo planeado. El 20% del tiempo tengo que dedicarlo a la enseñanza, así que durante este término seré TA (Teaching Assistant, algo así como un Ayudante de Trabajos Prácticos) en la materia Cryptography.

Primera escapada

Durante la segunda semana de Septiembre estaré en Bélgica, particularmente en Leuven. En FAST2011 aceptaron un paper que escribí con Eduardo. Es mi primer publicación relativamente importante y preparar su presentación me está llevando una buena porción del día. Este evento es satélite de uno más importante, llamado ESORICS2011, donde otros estudiantes de Chalmers presentan trabajos, por lo que también estaré allí. Como mis obligaciones terminan el Viernes, tengo pensado pasar el fin de semana en Bruges. Si estás por ahí entre el 10 y el 18, no dudes en avisar!

Hospedaje

El guest service de la Göteborgs Universitet me asignó un pequeño pero confortable departamento en Skanstorge, un céntrico barrio de la ciudad. Lamentablemente es provisorio y tengo que dejarlo en Octubre. Dado que es una ciudad mayormente de universitarios, conseguir donde alojarse no es una tarea sencilla. Así que buena parte del tiempo está abocado a esta búsqueda.


La organización de los próximos posts

No estoy seguro si los lectores de este blog utilizan las categorías. Están a la izquierda y permiten que el lector se subscriba a un tema específico de este heterogéneo blog. Por ejemplo, los temas sobre mi estancia en Suecia pueden encontrarse en la categoría Sweden. Tengo pensado abrir una nueva categoría llamada Lessons Learned donde, fiel al estilo pedante de este blog, comentaré algunas cosas que me llaman mucho la atención sobre el cómo se vive por aquí con la esperanza que le pueda ser útil a alguien.

Gente con quién hablar español

Es cierto que parte de la aventura es el idioma. Pero también es cierto que puede desesperar, sobre todo cuando viene mezclado con temas culturales y de difícil comprensión para el extranjero. Por suerte acá hay mucha gente con quién hablar la lengua de Cervantes. Por un lado, gracias a Emilio, me uní al grupo de Facebook "Argentinos en Gothenburgo". Resultó ser una gran ayuda en temas gastronómicos y otros relacionados con la cultura local. Por otro lado, en la universidad hay varios hispanohablantes que también facilitan mucho la entrada a mundo sueco, entre ellos Alejandro y Ana.

Las fotos

Resolví subir la fotos "diarias" a Picasa, el servicio de álbumes de Google. Se las puede encontrar aquí. La razón principal por la que lo hice de esta forma es bastante tonta y tiene que ver con que mi mamá puede bajarlas en buena calidad para imprimirlas (sí, ella imprime las fotos). Vieja, eso se hace desde el botón Download. Subir fotos en buena calidad (y a solo 5 dolares anuales los 20G) está bueno. Lo malo es que quien quiera comentarlas tendrá que tener una cuenta Google (las de Gmail, vamos). Sorber y soplar.
Pueden subscribirse al álbum para que se les notifique cuando hay nuevas fotos vía mail (que creo que también requiere tener cuenta) o por RSS. Las fotos de viajes y eventos específicos seguirán en http://www.lucianobello.com.ar/fotos/.

Nos volveremos a ver

Antes de irme, Pato me hizo un emotivo video de despedida. Muchas gracias a todos los que participaron en él. El mismo gira alrededor de la frase "nos volveremos a ver" en alusión a la canción calamarera. Pues.. así será. Mañana sacaré el pasaje para ir a Buenos Aires a pasar las fiestas y Guadalupe ya tiene los suyos para venir (y traerme las cosas que me olvidé :P) en Noviembre. Sin duda nos volveremos a ver y habrá muchas aventuras que contar!

Ciudad K explicado

Primero lo primero, visita:

www.ciudadkexplicado.com.ar

A continuación la explicación de qué es eso.

Cada vez que voy al viejo continente redescubro la tele española. Está llena de programas de humor, muchos de ellos increíblemente graciosos, incluso cuando varias gracias se pierden por no ser local. La última vez que estuve ahí no fue la excepción. Santiago me habló de un programa llamado Ciudad K (sin relación con los K de acá).

Ciudad K es un ya finalizado show de 14 capítulos, dirigido por el genial José Antonio Pérez, que fusiona el humor y el geekismo de forma épica. En esta hipotética ciudad, los habitantes tiene un nivel cultural e intelectual sobresaliente y las situaciones son de lo más bizarras. Todos los capítulos se encuentran en línea y son altamente recomendables.

Les hablé de esta serie a muchos conocidos freaks/nerds/geeks, y con ellos solemos comentar algunos gags que allí aparecen. Así fue como hemos notamos que ninguno de nosotros entendía todos los chistes, dado que abarcan un amplio espectro entre física, tecnología, economía, cine, artes plásticas, psicología y otras ramas de la cultura y la ciencia. De hecho, rápidamente descubrimos que conversar sobre Ciudad K era una muy divertida forma de aprender nuevas cosas, especialmente en las áreas en las que uno es un completo ignorante.

Así fue como levanté www.ciudadkexplicado.com.ar, un espacio en donde espero que se pueda conversar sobre los temas que se tocaron en la serie mientras se aprenden cosas nuevas y posiblemente inútiles.

Este viejo procrastination project lo tenía pendiente desde hacía meses y lo que se ve (así de feo) es el resultado de un arrebato de aburrimiento y de las ganas de saber que tan lejos se puede llegar con Google Sites. Pasé por varios vericuetos técnicos que, supongo, explicaré en otro post.

PD: Lo lamento José, soy un tío :P

Avancez

This post is available in English too.

Si me seguís por Twitter/Facebook o te lo comenté en persona, sabrás que durante el último viaje que hice al viejo continente pasé unos días en Gotemburgo, Suecia. Lo que muy posiblemente no sepas es qué fui a hacer a tan remota ciudad.

Hace unos meses apliqué para una posición en Chalmers, como estudiante de doctorado. Tuve la suerte de quedar en la short-list, lo que implicaba que tenía que ir a hacer algunas entrevista in-situ. Y eso fue lo que hice durante esos 3 días. ¡Y me aceptaron! :-)

Así que a mediados del próximo Agosto me estaré reubicando en la linda ciudad de Gotemburgo. Quedan excitantes días en los próximos meses en Buenos Aires, con muchas cosas para hacer y mucha gente a la que me gustaría ver. Así que si estas leyendo esto y me conoces mínimamente, escribime un correo y vamos a por unas cervezas :)

Chalmers es una universidad muy prestigiosa. La gran mayoría de los papers que estudié durante los últimos meses, fueron escritos por estudiantes de ahí y estoy muy contento con la posibilidad de trabajar en semejante ambiente académico.

Avancez

Este post también está escrito en español.

If you follow me on Twitter/Facebook, you probably know that I went to Gothenburg, Sweden, during my last trip to Europe. But you probably don't know what I did in such remote city.

Few months ago, I applied to a PhD student position at Chalmers. I was lucky enough to be shortlisted, so I went to some in-situ interviews. And, incredibly, I have been accepted! :-)

Chalmers is a TOP 100 university. Most of the papers I read during the last months has been written by Chalmers researchers and for me is a great honor to be part of an academic institution with such prestige.

I'm going to move to the nice Gothenburg city in August. And I'm happy :)

parser para fórmulas de lógica proposicional (o una somera introducción a pyparsing)

La semana pasada empecé a cursar, de oyente, dos materias en Exactas: Lógica y Computabilidad y Teoría de Lenguajes. En la primera, empezamos a estudiar algunos conceptos de cálculo proposicional. Al final de la clase, el profesor sugirió escribir un pequeño parser que reconozca fórmulas de lógica proposicional. Dado que venía con ganas de entender mejor pyparsing, me pareció que podía ser una buena forma de empezar.

Primero, la teoría. Dado el alfabeto $latex A$, $latex A^*$ es el conjunto de palabras que pueden formarse combinando sus elementos.
$latex A=\{ \to , \wedge , \vee , \neg , ( , ) , p , \prime \}$
Existe un tipo particular de palabras, a las que llamamos variables.
$latex Var=\{p , p\prime, p\prime\prime , \ldots \}$
Es un conjunto infinito y, dado que puede ser tedioso contar la cantidad de primas, las variables pueden ser referenciadas como $latex p_n$, donde n es la cantidad de primas. Así, parece razonable pensar que no todas las palabras son válidas a la hora de escribir una fórmula (que es como llamaremos a las palabras válidas).

Ejemplos de fórmulas:

  • $latex p_2$
  • $latex ( ( p_3 \wedge p_5 ) \to ( \neg p_2 \vee p_5 ) )$
  • $latex \neg \neg ( p\prime \vee p_{1232} )$

Ejemplos de no-fórmulas (palabras que no forman una fórmula):

  • $latex \neg\prime$
  • $latex ( p_2 )$
  • $latex p_3 \vee \wedge $

Si bien es más o menos intuitivo qué es una fórmula y qué no, es necesario definirlo en un sentido formal. Así $latex Form \subset A^* $ y es el conjunto de las palabras que cumplen:

  1. si $latex \alpha \in A^*$ y $latex \alpha \in Var$, entonces $latex \alpha \in Form$
  2. si $latex \alpha \in Form$, entonces $latex \neg \alpha \in Form$
  3. si $latex \alpha,\beta \in Form$, entonces $latex ( \alpha \circledast \beta)\in Form$. Donde $latex \circledast=\vee,\wedge,\to $

Nada más es una fórmula.

Ahora, a la práctica. Queremos escribir un parser que, dada una palabra, reconozca si es una fórmula. Y para esto vamos a jugar con el módulo pyparsing, para python.

Lo primero es definir el conjunto de variables.

>>> from pyparsing import Word
>>> variable=Word('Pp',"0123456789'")
>>> variable.parseString('p1')
(['p1'], {})
>>> variable.parseString("P'")
(["P'"], {})

Así, variable reconoce los posibles nombres de variables. Toda expresión que sea parseable por variable, es una formula. Para el punto ii. hay que definir una estructura recursiva. Utilizaremos el bang (!) para la negación.
from pyparsing import Forward
formula=Forward()
ii='!' + formula

Caso similar en el punto iii.. Para esto hay que definir los operadores, que son and (&), or (|) y then (<).

operador=Word('&|>',max=1)
iii='('+formula+operador+formula+')'

Por último, definimos una fórmula cómo una variable (i.) o una negación de una fórmula (ii.) o una operación entre fórmulas (iii.).

formula << ( variable | ii | iii )

Y esto es, básicamente, nuestro parser:

>>> formula.parseString("(p1 | p4)")
(['(', 'p1', '|', 'p4', ')'], {})

Lo dicho, con un poco más de contexto y en un único archivo, a continuación:

¡Nos vemos en España!

Gracias los grandes esfuerzos de Diego el gallego y Chema josemaricariño visitaré España en algo menos de un mes. Las excusas son las jornadas de seguridad organizadas por GSIC y los labs de la RootedCon. Así que vamos por partes.

Qué: Daré un taller sobre seguridad en sistemas Linux
Dónde: En el Campus de Elviña de la Facultad de Informática de A Coruña.
Cuándo: Las jornadas son entre el 24 y el 26 de Febrero.
Qué hay que hacer para asistir: La asistencia es gratuita con previa inscripción, la cual aún no está abierta pero lo estará pronto (posiblemente sea anunciado en @ficsecurity). Hay unas 25 plazas disponibles.
El taller será netamente práctico y será de unas 5 horas, por lo que tengo entendido. Trataremos temas de seguridad básica, como el acceso discrecional, la administración de recursos y PAM. Está orientado a iniciados en la administración de sistemas Linux-like.



Qué: Haré una introducción a la criptografía en uno de los Labs, previos a RootedCon
Dónde: En las Instalaciones Madrid On Rails, en Madrid.
Cuándo: Los Labs son entre 28 de Febrero y el 2 de Marzo. El mío en particular será durante el 1º.
Qué hay que hacer para asistir: La asistencia requiere inscripción previa y tienen un coste de 200 € + IVA. Hay 12 plazas disponibles.
Se puede acceder al temario aquí, aunque puede que dé una incorrecta impresión. En el momento que lo escribí hice demasiado foco en la parte matemática (aburrido!!). Si bien aún lo estoy preparando, el cursillo tendrá un foco mucho más programático. El objetivo es la mejora de decisiones tecnológicas cuando impliquen criptografía. Haremos prácticas en OpenSSL, SSH y PGP.

¿Nos vemos allí?

secure information flow analysis: my first steps

During the last months and have been reading a lot about information flow analysis, with the remarkable Eduardo Bonelli's guidance.

Some months ago, as an exercise, I wrote two analyzers for a really short command set of Python (while, if and assign). Before remove that directory, it occurred to me that may exists a remote possibility that someone might find it interesting. So here it is, with a quick and dirty introduction to secure information flow.

The goal, in short words, is to avoid that variables tagged as secret (high confidential level) doesn't leak to public variables (low confidential level). This may happen in two ways:

  • Explicit: A high variable is assigned to a low variable
  • public:=secret

  • Implicit: A low variable content depends on the content of a high variable
  • if secret == true
    then public:=true
    else public:=false

If there is no leak, we said that the code satisfies non-interference (wikipedia link). You can learn more about secure information flow analysis in the web. In my humble opinion, this is a good introduction.

A typical way (certainly not the only one) to detect these leaks is with type systems. This was the approach in both analyzers. The first one is a sort of an implementation of a fundation paper, by Volpano et.al.. I made an algorithm version (probably wrong) of the typing rules exposed in the paper. The code is here. This type of analyzers are called Denning-style, because Denning and Denning introduced those concepts in a 1977 paper.

The second analyzer (the code is here) is based on the formalism presented by Hunt and Sands in this paper. It's a dynamic analyzer (Denning-style analyzers are static), which means that the non-interference can be broken in subprograms and still be good as a whole. This may be a little tricky. For example, this code is secure (the leak was overwritten with a 0) even when a subprogram (without the last line) is insecure:
public:=secret
public:=0

Anyway, that's all for now. The analyzers are written in Python, using the Abstract Syntax Trees module and python-lattice (yes, this is what that stupid library is for). If you want to play more, here is a tarball with the code, the papers and few examples to analyze.

log log binning

Una de las materias que hice el año pasado (estrictamente hablando, aún la estoy haciendo) fue Topología de Internet, con Nacho Alvarez-Hamelin. En ella estudié a Internet como sistema complejo, donde routers y/o ASs se interconectan y forman un grafo.

Una de las propiedades más características de los grafos es su distribución de grados. El grado es la cantidad de vértices que tiene un nodo. En el ejemplo de la izquierda, el nodo 4 tiene grado 3. La distribución de grados es una característica del grafo en su conjunto y no es otra cosa que contar cuántos nodos hay con grado 0, cuántos con grado 1, y así siguiendo. En el caso de la topología de Internet, no hay nodos con grado 0, ya que es una red totalmente conexa (triste sería estar conectado a ese router que no está conectado a nada más).

La topología de Internet (es decir, cómo se interconectan sus componentes) no se conoce a ciencia cierta (tema que quedará para otro post) pero hay algunos acercamientos académicamente aceptados. Uno de ellos es el de CAIDA que provee información sobre como están conectados los distintos sistemas autónomos. Esta data, después de modificar un poco su formato, puede ser analizada con el módulo Complex Systems Toolbox, para Scilab, un clon libre de Matlab.
Resulta ser que, al analizar la distribución de grados de la topología de Internet, uno se encuentra con una distribución de ley potencial (chocolate por la noticias, dirían los hermanos Faloutsos, que ya sabían esto desde 1999).

Esta ley de potencia (en inglés, power law) es una relación en que la frecuencia de un hecho cae de forma exponencial con respecto a la magnitud. Este tipo de distribuciones tiene una forma de panza hacia el eje de coordenadas y abunda en la naturaleza™, desde el crecimiento de los ríos hasta la popularidad de las personas en las redes sociales. Por su forma tan particular, se suele dibujar en ejes logarítmicos, quedando como una recta que se caracteriza por su pendiente (en el dibujo, b), que es el exponente de la curva en ejes lineales.

En estos dibujos, la curva es continua y elegante. Pero cuando uno va al mundo discreto de la modelización de fenómenos, la cosa cambia. Y mucho. Por ejemplo, este es el gráfico de la distribución de grados de la topología de AS, según CAIDA:

Los puntos rojos son las muestras discretas, las uní solo para que se aprecie mejor cuál va delante de cada cuál. Como se ve, la cosa no queda tan prolijita y agradable. Es que hay veces que la naturaleza™ se resiste a ser modelada con una fórmula y la estimación de al pendiente cuando se trata de datos experimentales puede ser complicada, sobre todo en la cola. Así es como llegamos al concepto de binning.

La idea es sencilla. Consiste en dividir el eje x es zócalos (bins) de tamaño fijo. Después tomar todas las muestras que caigan en un bin y promediarlas. Así, se grafica solo este promedio como un único punto que representa a todo el bin. Como estamos trabajando con ejes logarítmicos, el calculo del ancho de los bins requiere cierta aritmética, dado que estos se van ampliando exponencialmente (de forma tal que queden todos del mismo tamaño, o casi, al plotearlos). A esto lo llamamos log log binning.

Por suerte, el Complex Systems Toolbox tiene una función para hacer esta magia. Y aquí está el resultado:

Las muestras son las cruces rojas, mientras que los puntos verdes son los representantes de binning. Puede verse que están casi equidistantes, sobre todo después de 10. Por otro lado ¿no notan nada raro acá? Vamos por partes. En la parte inicial de la curva, ésta aparece por debajo de la línea de las cruces rojas. Esto empieza a tener poco sentido. Se supone que el promedio de un único punto es ese mismo punto.

Más grave aún es lo que ocurre en la cola. Ahí, esporádicos puntos (hay muchos ceros) generan una recta paralela al eje. Cuando uno promedia varios valores el resultado debería ser cada vez menor si la cantidad de ceros aumenta. Sin embargo, aquí la curva se suaviza hasta perder toda su inclinación.

Fue así como decidí mejorar esta funcion de log log binning (si, toda esta introducción para contarles esto... es que evidentemente soy muy pedante). A continuación, el mismo gráfico, resultado de mi propia implementación:

Algunas reimplementaciones por acá, fixeo de bugs por allá y ahora la pendiente se puede ver mucho más clara. Obvio que también podías leerte el paper de los hermanos Faloutsos, donde se explica que b está entre 2.1 y 2.4, pero no hubiese sido igual de divertido. Tuve que leer bastante y entender aritmética que había olvidado. Putié mucho contra scilab/matlab pero terminé descubriéndole cosas interesantes. En general, fue algo bastante entretenido.

La nueva implementación de log log binning ya está en el trunk de Complex Systems Toolbox y seguramente estará disponible en la próxima versión. También incluí novedades para graficar distribución de grados cuando los grafos son dirigidos y algunas otras pequeñeses de formato.

La UTN tiene dueño (wtf)

Hernán me pasó un excelente link de Linkedin (redundancia necesaria), la red social orientada a negocios y el mundo profesional, cuya captura reproduzco a continuación:


Mucho se me ha escuchado putear sobre el corporativismo en la universidad en este blog y otros entornos. Pero este fallido es como demasiado :P
El tiempo de estudio es un bonus wtf (y yo que siempre pensé que mis 8 años de carrera habían sido demasiados)...

El borroneo sobre el nombre tiene como fin no darte el dato directamente, una situación parecida a la ocurrida acá. Ya sé que lo podés conseguir, bien por ti.

not yours

If I say "I got the third place in a scholarship application", it doesn't look bad.

But there is money only for the first two persons. Sometimes, close is not enough. So, without money, I won't be able to study in Europe... damn...

Maybe next year... maybe not.

Note: The application was, as you can see, for a doctoral scholarship in Spain... my broken English has no effect here...

semana definida

Para quienes no se van de vacaciones en enero/febrero, lo dilatado y pesado que se vuelve la vida en estos días es algo molesto. Uno pretende seguir a paso firme y se sorprende a sí mismo tirando de las cosas. Pero esos días ya terminaron y marzo llegó (de hecho, ya está terminando).

Alguien dijo por ahí que marzo es al año lo que el lunes es a la semana. Como consecuencia de esto estoy en vías de definir mi actividades semanales, al menos durante los próximos meses. Empecé a estudiar dos materias: Fundamentos de Concurrencia y Movilidad y Metaheurísticas. Estoy tratando de retomar formalmente el Inglés, y empezaré con Alemán.

Ahora que lo veo escrito, parece haber demasiado hemisferio izquierdo involucrado en mi semana tipo. Posiblemente le agregue algo para balancearla en los próximos días...

the root of all mistake: the overgeneralization

Yes, it's me again with this DSA-1571 exploitation issue. The discovery, explanation and exploitation of the bug is now part of my final coursework for my postgraduate degree career. So, yes... sorry.

Some weeks ago I started suspecting about the attack to PFS in SSL with EDH. The key point is: the key space is dependent of the PRNG state. The bug affects the initialization of the PRNG, but the random string has not a pattern by it self. If you ask for many random numbers to the PRNG, you gonna get numbers that differ among them, since they are the output of a hash function of them self. So each random number depends on, besides the PID, the state of the PRNG pool in the moment (in other words, amount of bytes that you already pull from the PRNG pool before)

The explained attack was based in a fixed list of private exponents (which are selected randomly during the DHE handshake), presupposing that all the application call RAND_bytes() the same number of times before get it. To make the list of exponent I ran the openssl s_client with all the possible PIDs, hoping that all the applications behaves the same way.

After more tests I notice that that was an overgeneralization. The proof is in the pudding: wget and cURL, two simple CLI file retrievers, gets different exponent between them, even running with the same PID.

I was working on this when I accidentally found a really nice Eric Rescorla's post which is deeply related with this. The post goes further and analyzes the interaction between how Apache forks off and how it generates SSL handshakes.

So, I made lists of secret exponents for wget, curl, openssl s_client and openssl s_server with a modification version of libssl (appling this messy patch) and running scripts like this:

for i in $(seq $((2**15)));
do
  export MAGICPID=$i;
  LD_LIBRARY_PATH="openssl.broken/" LD_PRELOAD="./getpid.so" \
     wget --no-check-certificate https://localhost/ -q  -O /dev/null ;
  echo $i ;
done

As you can see, I used the HD Moore's GetPID faker shared library and a normal local Apache with mod_ssl. The broken libssl (which is in .openssl.broken/) store up in /tmp/data.key a csv with command name, PID and all the DH components (g, x, y and p).

But this way is farly unconfortable for others SSL deamon servers. Have you got any better idea?

estoy a esto -><- de ser ingeniero

Estas últimas semanas fueron a puro estudio. Así que finalmente terminé. Si si si, terminé la carrera. Hoy rendí mi último final y el sábado solo me resta firmar proyecto.

Si tuviste un mal año y querés venir a desquitar toda la ira en forma de huevo con un inocente muchacho... Sábado 22 (mañana), a las 3:30 pm en Medrano 951. Os estaré esperando.

fin del semestre academico

Finalmente terminé el semestre académico. Todo hubiera salido de maravillas sino fuese por un tropezón en el final de Inteligencia Artificial, que tendré que volver a dar en septiembre.

Primero, lo prometido (ni que fuera gran cosa). Los dos informes que presenté este semestre y que disfruté mucho de hacerlos. Ambos fueron comentados en este blog durante su confección y vienen acompañados de un poco de código para que pueda verse su parte “práctica”:

  • Algoritmos Genéticos para la Resolución de Sudokus - (Inteligencia Artificial): Como lo había comentado, no esperen nada interesante desde el punto de vista de la resolución. Es, más bien, una ridiculez hecha informe. Planeo hacerle algunas mejoras al programa propuestas por amigos con demasiado tiempo libre.
  • Análisis y Detección de Esteganografía en Audio - (Procesamiento de Señales): Tampoco esperen nada revelador. Aunque creo que también voy a mejorarle la parte algorítmica en algún momento. Si bien es algo más serio que el anterior, su enfoque está muy basado en los lenguajes y funciones utilizadas. Creo que se puede orientar más a lo analítico, por lo que sugerencias son bienvenidas.

El semestre que voy a iniciar es el último antes de convertirme en ingeniero. Quedan 6 materias y el objetivo principal es terminar con un promedio superior a 7.

Otro tema. Gracias a todos lo que me saludaron y felicitaron por mi nombramiento en Debian :-). Sus elogios y empujones de entusiasmo hacen mucho bien.

Esteganografía en Audio

¿Qué tienen en común estos libros?

Son todos referencias del informe de Procesamiento de Señales en el que estoy trabajando este fin de semana: Análisis y Detección de Esteganografía en Audio. Incluye un pequeño programita (mitad en R, mitad en C) para analizar como se deforma el audio cuando es manipulado esteganográficamente. Tengo pensado colgarlo acá en un par de semanas, cuando tenga mejor forma, pero ya afloran algunas conclusiones:

  • Las grandes amplitudes favorecen el ocultamiento
  • Las altas frecuencias también
  • No hay ganancia real en modificar solo un porcentaje de las muestras

¿Interesado en el tema? Estoy a la escucha de sugerencias e ideas, sientete libre de pedir más información.

UPDATE August 6th: El informe y los archivos relacionados ya está publicados.

sudoku, algorítmos genéticos, la estrategia backtracking, programación lineal y R

/* Habiendo leído El curioso incidente del perro a medianoche le tomé cierto buen gusto a los títulos largos :-) */

Hace unas semanas, Mahoo me regaló un pequeño libro con un montón de sudokus para resolver. Si bien conocía el juego, nunca me atrajo particularmente. En esos días, yo estaba buscando algún tema original para uno de los trabajos prácticos de Inteligencia Artificial. La consigna se refería al uso de algoritmos genéticos para la resolución de algún problema. Lo importante no era el programa, sino el análisis de su comportamiento: estudiando, por ejemplo, qué método de cruzamiento se aplica mejor o qué función de aptitud es más representativa.

Viendo como Mahoo se entretenía con alguno de ellos (práctica en la que también se iniciaba) se me ocurrió que un resolver de sudokus podría ser una linda propuesta para mi TP.

Los algoritmos genéticos intentan emular a la naturaleza, a base de prueba y error, favoreciendo a las soluciones más aptas y castigando a las que no lo son tanto. Suponiendo que el cruzamiento de las buenas-soluciones generan aún-mejores-soluciones. Se trata de la búsqueda probabilística, muy parecida a meter muchas soluciones en un cubilete gigante y agitarlas hasta encontrar algo útil.

Al tratarse de un problema determinístico, la solución dista muchísimo de ser óptima. De hecho, ni siquiera se asegura que vaya a haber una solución. Pero me pareció algo simpático de intentar.

El resultado, escrito en mi rústico Python, puede ser bajado de aquí (incluye instrucciones para correrlo en Windows). No, no esperen que funcione bien, advertidos están. Es uno de los peores métodos posibles para este tipo de problemas. Sólo llega a una solución cuando la cantidad de incógnitas es (muy) limitada. Se plantean soluciones a base de llenar de random cada uno de los casilleros vacíos y chequeando cuantos valores se repiten en cada fila, columna y región. Cuando este chequeo da 0, se llega a una solución. Bastante cavernícola como notarán.

Es natural pensar en cuál sería la forma correcta de llegar a una solución. Recordé las clases de Investigación Operativa y la utilización del método simplex para la solución a problemas con restricciones. De hecho, es una solución que muchos proponen. No se si alguno de ustedes lo ha intentado. Yo sí, durante las clases aburridas me senté a pensar como sería el conjunto de ecuaciones y me encontré con una demencial y frustrante cantidad de ecuaciones. Acá hay una linda explicación, la que resumo, haciendo énfasis en las complicaciones:
Se necesitan variables binarias de la forma xijk donde 1 significa que el símbolo k (de 1 a 9) va en la celda (i,j) de la solución. 0 significa que no está. Esto genera un total de 729 variables (93) lo que, como mínimo, asusta. Veamos las ecuaciones:

(1) Para que cada celda (i,j) tenga un símbolo y éste sea único. Se necesitan 81 ecuaciones como éstas (una por cada celda).
(2) Para que en la fila i cada símbolo esté una vez y que en todas las columnas sea distinto. Se necesitan 81 ecuaciones como éstas(una por cada columna y cada símbolo posible).
(3) Para que en la columna j cada símbolo esté una vez y que en todas las filas sea distinto. Se necesitan 81 ecuaciones como éstas(una por cada fila y cada símbolo posible).
(4) Para que en cada región cada símbolo esté una y solo una vez. Se necesitan 81 ecuaciones como éstas (una por cada región y cada símbolo posible).
(5) Representa el enunciado, es decir, el problema a resolver. Por ejemplo, x115=1 significa que en la celda (1,1) hay un 5. Dependiendo cuantos casilleros vengan asignados es la cantidad de igualdades como estas que se necesitan; típicamente, ~30.
(6) Restringe las variables al conjunto binario.

¡En total son más de 350 ecuaciones! Hay propuestas con menos ecuaciones, pero siempre serán muchísimas. Evidentemente, ésta tampoco es la solución óptima (aunque es mucho mejor que los algoritmos genéticos). Y su problema radica en que, desde algún punto de vista, el método simplex no se ajusta al problema. Gráficamente, las ecuaciones representan semiplanos en un hiperespacio multidimencional (de 9 dimensiones?) cuya intersección es, en caso que haya una única solución, un único punto. /* Puede que le esté pifiando en esta conclusión final y cualquier ratificación o rectificación es bienvenida */

Simplex está pensado para restricciones de máximos y mínimos donde el objetivo es maximizar o minimizar y las variables binarias intentan ampliar el método para restricciones de este tipo. Da soluciones múltiples en forma de un polígono, donde a una o más se las llama óptima, porque maximiza o minimiza la función objetivo. Es claro que el problema del sudoku no usa sus ventajas y abusa de sus debilidades.

Curiosamente, cuando comenté este problema a un reciente conocido, surgió que también él tuvo que hacer un trabajo práctico que resolvía sudokus. En este caso, el TP giraba entorno a la gestión de la pila para recorrer árboles. Particularmente, árboles empleados en la estrategia de backtracking. Así pues, éste es su programita, sencillo, simpático y rápido. Gracias Nacho :).

Los métodos basados en búsqueda combinatoria sobre árboles parecen ser particularmente buenas para el problema del sudoku. En la wikipedia figuran dos interesantes formas: backtracking y ramificación y poda.

Para terminar, una última casualidad: Por razones que no vienen al caso ahora y que seguramente provocarán un nuevo post en el futuro estoy aprendiendo un lenguaje para el procesamiento de señales llamado R. Estoy trabajando mucho con una biblioteca llamada sound. Buscándola en el repositorio de bibliotecas, me encuentro con una llamada sudoku. No resistí la tentación de probarla :). Un ejemplo de su uso:

> install.packages("sudoku")
> # es necesario instalar tcltk si se quiere la parte gráfica
> install.packages("tcltk")
> library(sudoku)
> library(tcltk)
> library(tkrplot)
> miSudoku <- generateSudoku(Nblank=50, print.it=TRUE)
  +-------+-------+-------+
  |   6   |   7   |   8 2 |
  | 4 8   |     1 | 7     |
  |       | 8 2   | 5     |
  +-------+-------+-------+
  |       | 1     | 9 7   |
  |       |     2 |   5 1 |
  | 5 1 6 |   9 7 |       |
  +-------+-------+-------+
  |       |   4 8 |       |
  | 6 5   | 7   9 | 8     |
  |       |       |   9 7 |
  +-------+-------+-------+
> # la variable miSudoku es una matriz
> miSudoku
       [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9]
 [1,]    0    6    0    0    7    0    0    8    2
 [2,]    4    8    0    0    0    1    7    0    0
 [3,]    0    0    0    8    2    0    5    0    0
 [4,]    0    0    0    1    0    0    9    7    0
 [5,]    0    0    0    0    0    2    0    5    1
 [6,]    5    1    6    0    9    7    0    0    0
 [7,]    0    0    0    0    4    8    0    0    0
 [8,]    6    5    0    7    0    9    8    0    0
 [9,]    0    0    0    0    0    0    0    9    7
> #La biblioteca incluye una función para para solucionarlo
> solveSudoku(miSudoku)
       [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9]
 [1,]    1    6    5    9    7    3    4    8    2
 [2,]    4    8    2    5    6    1    7    3    9
 [3,]    3    7    9    8    2    4    5    1    6
 [4,]    2    4    8    1    5    6    9    7    3
 [5,]    7    9    3    4    8    2    6    5    1
 [6,]    5    1    6    3    9    7    2    4    8
 [7,]    9    3    7    2    4    8    1    6    5
 [8,]    6    5    1    7    3    9    8    2    4
 [9,]    8    2    4    6    1    5    3    9    7
> # Incluso trae soporte gráfico para resolverlo en una ventanita :)
> playSudoku()

Así fue como, un simple regalo, un TP universitario y un montón de simpáticas casualidades tuvieron su punto de conexión. Y que divertido que resultó ser :). Ahora tengo que escribir el informe sobre los algoritmos genéticos en el sudoku. La semana que viene espero publicarlo aquí.

UPDATE August 6th: El informe y los archivos relacionados ya está publicados.

Seminario complementario sobre seguridad informática

En el marco de los seminarios complementarios Athena, voy a dar un seminario sobre Seguridad informática. Como olfateo algunos problemas en la difusión, este post tiene como fin invitar gente.

El qué: Seguridad Informatica: criptografia desde su aplicación domestica

El de qué se habla:

  • Teoría: Criptografía fácil y útil. Critografía simétrica y asimétrica. Funciones de hash

  • Uso seguro del correo. Ejemplos de mails firmados y cifrados. PGP y Web of trust.
  • Ataques a usuarios domésticos. Malware y Botnets. Análisis de los antivirus. Precauciones en el gestor de correo. Phishing.
  • Qué es SSL. De qué nos protege. Cómo funciona PKI. Qué chequear cuando ingresamos a un sitio seguro. Precauciones a tener en cuenta. (Keyloggers/teclado virtual)

El dónde:
Sede Medrano de la Universidad Tecnologica Nacional
Medrano 951 - Aula Magna
Capital Federal, Buenos Aires. Argentina

El cuándo: Lunes 16 de abril de 2007, 19:00 hs (próximo lunes)

El cómo: Ir no más, no requiere inscripción previa ni aviso

El para quién: Para cualquiera, alumnos, docentes y profesionales de sistemas, de la UTN o externos en general.

Invitados están todos a venir y a correr la bola.

UPDATE 15-05: Los slides de la charla en varios formatos y con ejemplos, acá.