Complejidad algorítmica y ataques

Leía hace unos días el artículo algorithmic complexity attacks and libc qsort() donde se hace un análisis del Quick Sort, lo que pueden costar algunas de sus implementaciones y fantasea con la posiblidad de utilizarlo para algún tipo de ataque de denegación de servicio (o al menos ralentización).

Son de esas cosas que nos trae el software libre e internet.

Una introducción al cálculo del coste de algoritmos

Una de las diferencias entre alguien que resuelve problemas y un buen desarrollador está en si es capaz de analizar cómo de buena es la solución que propone o no. A veces nos mareamos (y mareamos a otros) haciendo micro-optimizaciones sin habernos parado a pensar dónde ni cómo es la forma más adecuada de hacerlo.

En A Gentle Introduction to Algorithm Complexity Analysis podemos leer las ideas básicas sobre el tema, que nos abrirían la puerta a empezar a pensar en un algoritmo como un todo y no como un conjunto de instrucciones más o menos afortunadas.

¿Seguro que es el mejor algoritmo?

Cambiamos un poco de tema. En Think you’ve mastered the art of server performance? Think again. el análisis del coste de una solución cuando empiezan a entrar diversos factores que afectan a cómo la teoría interpreta los resultados.

Por ejemplo, algunas suposiciones puede ser importante:

A quick browse of the mental catalog flipped up the binary-heap card, which not only sports an O(log2(n)) transaction performance, but also has a meta-data overhead of only a pointer to each object—which is important if you have 10 million+ objects.

La memoria virtual:

It took quite some time before virtual memory took hold, but today all general-purpose, most embedded, and many specialist operating systems use VM to present a standardized virtual machine model (i.e., POSIX) to the processes they herd.

Y como seguimos ignorándola a la hora de medir teóricamente algunas cosas:

The fact is, however, 46 years later most CS-educated professionals still ignore VM as a matter of routine. This is an embarrassment for CS as a discipline and profession, not to mention wasting enormous amounts of hardware and electricity.

Por eso,

What good is an O(log2(n)) algorithm if those operations cause page faults and slow disk operations? For most relevant datasets an O(n) or even an O(n^2) algorithm, which avoids page faults, will run circles around it.

Por eso, nosotros siempre recomendamos medir teóricamente para tener una idea de por donde van los tiros. Pero luego probar con nuestros sistemas reales y con los datos de verdad, para estar seguros de que los resultados teóricos se mantienen.
Y, por supuesto, esto nos da pistas de por qué es importante saber de hardware, del sistema y tratar de estar al día en muchos de estos temas.

Divertido, ¿no?

¿Por qué GNU grep es rápido?

La respuesta en why GNU grep is fast y lo explica haciendo referencia a los aspectos técnicos pero sin meterse mucho en los detalles.

Esencialmente:
Se utiliza el algoritmo de Boyer-Moore, que tiene como ventaja que evita mirar los bytes uno a uno, porque es capaz de evitar algunos basándose en información sobre lo que se busca (letra final, tamaño y aprovechándolo para dar saltos más grandes).
Pocas operaciones sobre cada byte de los que realmente se miran.

Además, el bucle interno está ‘desenrollado‘, lo que le evita algunas operaciones extra (las de control del propio bucle, claro). También evita pensar en líneas (salvo cuando ‘cree’ que ha podido encontrar lo que buscaba y trata de gestionar mejor la memoria para que la lectura sea más eficiente.
¿Alguien se anima a echarle un ojo al código?

Algoritmos galácticos

En Galactic Algorithms nos hablan de una forma de llamar a esos algoritmos que tienen un buen coste asintótico pero que no los usarísmoa para calcular nada: Dick Lipton comenta como es un gran avance el ser capaces de predecir el comportamiento de un algoritmo sin ejecutarlo. También que hay algoritmos que son un gran descubrimiento aunque luego no se utilicen en el ‘mundo real’, por motivos como: descubrir nuevas técnicas, ser utilizables en el futuro si algunos paradigmas de computación cambian, abrir la puerta a otros algoritmos que sí son utilizables, o descubrirnos que algunos cotas temporales de algunos son excesivas (un programa costoso, pero con una cota polinómica cambiaría las ideas previas sobre determinados problemas, por ejemplo).

Uno que entra en esta categoría podría ser el de divide y vencerás para multiplicar matrices grandes, el algoritmo de Strassen.