AlphaDev: La IA que optimiza la implementación de los algoritmos mejor que los humanos

Ayer sábado cayó en mis manos el artículo académico publicado en la revista Nature sobre AlphaDev, la I.A. que se ha utilizado para optimizar los algoritmos básicos de programación, que ha logrado hacer mejores implementaciones que las que hemos logrado hacer los seres humanos, en problemas tan de base como los algoritmos de ordenación. Y no me he resistido a hablaros de él.

Figura 1: AlphaDev: La IA que optimiza la implementación

de los algoritmos mejor que los humanos

Y es que, para mí, la programación de algoritmos de ordenación ha sido casi un juego toda mi vida. Comienzas haciendo algoritmos de ordenación basados en la burbuja, y sigues implementando soluciones hasta que llegas a soluciones O(nLog(n)) como QuickSort. Y cuando llegas a algorítmica óptima, tienes que pasar a la siguiente fase, a la implementación en lenguaje de alto nivel más optima posible, para que esta codificación se estandarice, y sea compilado en código ensamblandor, código intermedio, o código máquina más optimizado posible. 

Figura 2: Artículo de "Faster sorting algorithms discovered using Deep Reinforcement Learning

En esta optimización, se busca la mejora de uno o de todos los parámetros de medición que sean relevantes para nosotros, como puede ser el número de instrucciones, la latencia o los ciclos de reloj que consume el programa completo en el modelo teórico, en la media de los casos o en caso más probable. La optimización es un arte de buscar el mejor resultado posible para la ejecución completa del problema.

Figura 3: AlpahDev ha descubierto mejores algoritmos Sort

Y por eso, leer en el artículo que AlphaDev ha conseguido superar en las implementaciones de los algoritmos Sort estáticos, y dinámicos para diferentes tamaños de datos de entrada, tanto en número de instrucciones como en latencia de ejecución al estado del arte de los algoritmos que hemos creado los humanos, me capturó al instante la atención.

Porque una mejora en un algoritmo como Sort para tres elementos, se utiliza tantas y tantas, y tantas veces en los programas que utilizamos constantemente, que el impacto que puede tener es brutal en temas como la eficiencia, el consumo energético o la velocidad de resolución de problemas complejos en equipos de menor capacidad de computo. 

Al final, que es el debate que tenía con uno de mis amigos, durante décadas llevamos alejándonos de la máquina para programar. Nos hemos abstraído, pasando de pensar y codificar algoritmos de forma eficiente, a utilizar objetos, luego componentes, después APIs, y por último I.A, a la que le decimos qué queremos que haga pero no nos importa mucho cómo lo haga con las estrategias de NoCode o LowCode. Lo que es casi anatema con la eficiencia algorítmica.

Figura 4: Mejoras obtenidas en algoritmos de Sort obtenidas con AlphaDev

Hemos fiado a la implementación de las capas inferiores la optimización de los pequeños detalles de lo que queríamos construir con software, y ahora usamos esa I.A. para hacer ese trabajo también. Y es como subir hacia arriba en la escala de distanciamiento del lenguaje más básico hasta crear la I.A. necesaria que permita bajar otra vez a lo más bajo nivel para hacer ese trabajo.

El problema, tal y como lo han plateado el equipo de AlphaDev ha sido similar al que hemos visto para cualquier otro juego como el Ajedrez o el Go. Un algoritmo de Deep Reinforcement Learning para que una I.A. busque el algoritmo más eficiente. Solo que en lugar de enseñarle a mover el caballo, la reina o el rey, se le enseña para qué sirve cada una de las instrucciones básicas de un microprocesador, y se le pide que gane la partida de la mejor forma.

Figura 5: La algorítmica como resolución de un juego

Es decir, imaginad el problema del Sort de tres elementos A,B,C. Las salidas posibles pueden ser ABC, ACB, BAC, BCA, CAB, CBA dependiendo si el mayor, el medio o el menor entran en un orden u otro como forma de solucionarlo. Dado esto, AlpaDev tenía que resolver ese "juego" consiguiendo que la combinación de instrucciones resolviera el problema en todos los casos, y que se optimizara primero el número de instrucciones y luego la latencia de ejecución - que es algo aún mucho más a bajo nivel donde se toman en cuenta los ciclos de ejecución -. Y por supuesto, lo hace.

Figura 6: La diferencia entre las estrategias implementadas

Los resultados han sido que para diferentes algoritmos de ordenación fija y variable ha conseguido superar, en todos los casos, al estado del arte de los algoritmos implementados por los humanos, utilizando diferentes implementaciones. Y es espectacular. En el caso del algoritmo Sort de tres elementos, consigue resolver el problema con un movimiento curioso.

Al final, pasa de resolver el problema de una forma en la que el primer elemento es el mínimo de los tres, y el último el valor máximo de los tres para que el que quede sea el del medio, a hacer una ordenación de un subconjunto de dos elementos y hacer una inserción del tercero en la lista ordenada de los dos primeros. Como hace el QuickSort a alto nivel. Y eso, implementado en código de instrucciones es una línea menos.

Figura 7: Una línea menos en la implementación de AlphaDev

Pero lo importante es que, estos códigos, una vez visto que AlphaDev es capaz de encontrar estas soluciones primando el objetivo en líneas de código o latencia, y siendo entrenado para el conjunto concreto de las instrucciones de cada uno de los microprocesadores donde vaya a ejecutarse, la eficiencia en tiempo, en recursos de computación y energía, puede ser brutal.

Figura 8: Libro de Machine Learning aplicado a Ciberseguridad de
Carmen Torrano, Fran Ramírez, Paloma Recuero, José Torres y Santiago Hernández.

Y algoritmos muy complejos, podrían ser ejecutados mucho mejor, haciendo que aquellos que son más complejos se vean beneficiados. Como los complejos algoritmos de Machine Learning e Inteligencia Artificial. Y cuando podamos utilizar estas estrategias no con solo 130 instrucciones de un microprocesador, sino con las mismas herramientas que usamos hoy en día nosotros para programar a alto nivel, se podrán optimizar soluciones de hacking y de seguridad informática de forma diferente. ¿No es maravilloso?

¡Saludos Malignos!

Autor: Chema Alonso (Contactar con Chema Alonso)  

LeHack: Una noche de hacking en París con Open AI, Python e iBombshell [Parte 1 de 2]

 El fin de semana ha sido de lo más ajetreado. Siempre hablamos de la importancia de optimizar el tiempo y el valor de éste. Recientemente nos aceptaron un workshop a mi compañero Fran Ramírez y a mí para ir a LeHack una conferencia que se celebra en París. Antiguamente, y por lo que hemos podido conocer allá, la Hacking París tenía una Nuit du Hack. Ahora, y tras 16 años de evento, se han separado en dos, dando lugar a LeHack.

Figura 1: LeHack: Una noche de hacking en París. Open AI, Python e iBombshell

En el evento pudimos ver cómo la importancia y el crecimiento de la ciberseguridad en Francia tiene un ritmo similar al nuestro. La gente muestra mucho interés en todo lo que rodea a nuestro sector y, en un porcentaje alto, también muestran mucho interés por sectores como el de la Inteligencia Artificial. Un evento con cerca de 2.000 personas en la capital de Francia. Allá estábamos dispuestos a mostrarles cómo de locas son nuestras ideas.

Nuestro workshop, inicialmente programado de 1 de la madrugada a 4 de la madrugada, fue cambiado una semana antes a un horario menos nocturno, de 21.00 a 00.00. Hackira, uno de los organizadores responsables del evento, nos comentó que podíamos estar más tiempo sin problema, ya que de 00.00 a 01.00 no habría nadie. Digamos que Fran le cogió el gusto y estuvimos hasta las 00.40 con el workshop.

Figura 2: Badge de LeHack 19

Un recuerdo que me traigo es el ‘badge’ del evento. Una tarjeta de un circuito impreso con un NFC incluido. El reto era leer la tarjeta NFC y ver qué imagen se encontraba oculta. No tuvimos tiempo de ponernos con ello, pero es algo que pude seguir vía Twitter.

Workshop: Learning how to code doing some hacking and creating AI programs to beat video games

El workshop tenía tres partes. Una de ellas donde Fran hablaba de la IA y la creación de agentes con Open AI para enseñarles a jugar a juegos clásicos. Otra donde yo hablaba de cómo aprender hacking a través de la implementación de pequeños códigos en Python, hubiera preferido Ruby, pero era lo que tocada (guiño, guiño). En esta segunda parte se llegaba a ver módulos de ibombshell escritos en Python. Y una tercera parte donde Fran volvía a tomar el timón y hablar del punto de unión entre la ciberseguridad y la inteligencia artificial, mediante ejemplos que en el equipo de Ideas Locas del área CDO de Telefónica hemos llevado a cabo.

LeHACK. Parte Workshop IA OpenAI

La parte del seminario dedicada a Inteligencia Artificial y Videojuegos, estaba centrada principalmente en OpenAI Gym, un framework para ejecutar diferentes entornos (pero sobre centrado en videojuegos) sobre el cual ya hemos hablado en profundidad en el blog de LUCA en estos artículos entre otros:

• Cómo entrenar a tu Inteligencia Artificial jugando a videojuegos. Parte 1 Rejilla
• Cómo entrenar a tu Inteligencia Artificial jugando a videojuegos. Parte 2 Entorno
• Cómo entrenar a tu Inteligencia Artificial jugando a videojuegos. Parte 3 CartPole
• Cómo entrenar a tu Inteligencia Artificial jugando a videojuegos. Parte 4 Taxi (1/2)
• Cómo entrenar a tu Inteligencia Artificial jugando a videojuegos. Parte 5 Taxi (2/2)

El objetivo principal era demostrar, utilizando pocas líneas de código (en nuestro caso utilizamos el lenguaje de programación Python), cómo resolver problemas y entornos sencillos de juegos utilizando Machine Learning, y sobre todo, Aprendizaje Reforzado (Reinforcement Learning). Antes de entrar de lleno en la materia, realizamos una pequeña introducción a la IA y más en concreto al Machine Learning, repasando conceptos como aprendizaje supervisado, no supervisado, reforzado, redes neuronales, etcétera. De esto, ya sabéis que hablamos en el libro de Machine Learning aplicado a la Ciberseguridad.

Figura 3: Machine Learning aplicado a Ciberseguridad

No sabíamos en principio del nivel de conocimiento de la materia de los asistentes, así que este paso introductorio era necesario. Para la ejecución de todos los ejemplos utilizamos una sencilla máquina virtual GNU/Linux con Ubuntu y el entorno OpenAI Gym instalado.

Figura 4: Parte de la introducción a Machine Learning donde explicamos el Aprendizaje Reforzado
y sus fases en un entorno de videojuego, en este caso BreakOut de Atari 2600.

El siguiente bloque se centró en explicar OpenAI Gym, su funcionamiento y cómo poder ejecutar entornos. Para ello mostramos varios juegos de Atari 2600. En esto punto hicimos especial énfasis en un aspecto realmente importante y necesario para comprender todo el proceso de aprendizaje reforzado: el agente (el programa de IA) no sabe al principio nada sobre el entorno, ni las reglas ni qué acciones puede realizar. Es decir, es el mismo agente el que a base de experiencia y recompensas “deduce” las reglas y las acciones que puede realizar para optimizarlas y resolver el entorno.

Ejemplos de la primera parte

El primer problema propuesto para resolver durante el taller fue CartPole. Un entorno sencillo en el cual tienes que mantener una varilla en equilibrio encima de un carro el cual se puede mover de izquierda a derecha. Para resolverlo utilizamos un algoritmo básico pero necesario para comprender conceptos más avanzados que vendrían después. Este algoritmo es Random Search o búsqueda aleatoria.

Figura 5: Resolviendo CartPole

Analizamos el código y explicamos línea por línea el método de resolución, así como el resultado final. Este algoritmo suele resolver este entorno sólo en unos 15 episodios (es decir, 15 ejecuciones) así que no habría problema en ejecutarlo durante el taller.

El resto de los entornos que usamos a partir de aquí, fueron un poco más avanzados con la intención de explicar el concepto de Q-Learning y Q-Tables, necesarios para comprender otros algoritmos y técnicas más complejas como por ejemplo, Deep Q-Learning. Para ello utilizamos el entorno Taxi de OpenAI y otro creado por nosotros que hemos llamado Dungeon (Mazmorra).  Taxi es un entorno en el cual hay que llevar un pasajero de una ubicación a otra maximizando y utilizando el mejor recorrido utilizando Q-Tables y Q-Learning.

Figura 6: Resolución de Dungeon que utilizamos para explicar paso a paso, cómo optimizar
una Q-Table para conseguir la puntuación máxima del Entorno. En la imagen
se muestra el resultado final de la optimización mostrando el camino óptimo

Para explicar mejor la Ecuación de Bellman, básica para entender los conceptos de optimización matemática que utilizamos durante todo el taller, mostramos la resolución de una sencilla Mazmorra (Dungeon) desde la cual un caballero medieval debía encontrar la salida maximizando la puntuación, recogiendo una gema y un tesoro pero evitando en todo momento a un Dragón.

Figura 7: Explicación paso a paso de la optimización de valores utilizando la Ecuación de Bellman
para llegar al resultado final. En este caso se muestra la puntuación al obtener el tesoro.

Una vez explicada la teoría, mostramos la ejecución de Dungeon pero de un entorno más avanzado, donde el laberinto es mayor (y generado de forma aleatoria) pero además, aparecen más obstáculos e incluso una llave. Hablaremos en breve más a fondo sobre este nuevo entorno en el cual estamos aún trabajando junto a nuestro compañero en Ideas Locas, Enrique Blanco.

Finalmente, también resolvimos en la máquina virtual entorno Taxi, mostrando los diferentes pasos y el contenido de la Q-Table. De esta forma quedaba muy claro el objetivo principal de maximización de valores dentro de una matriz.

Figura 8: Resolución de Taxi, explicado paso a paso mostrando la Q-Table y sus
valores optimizados durante el proceso además de las gráficas del proceso.

En este punto ya estábamos listos para explicar cómo resolver entornos más complejos como por ejemplo videojuegos, donde el análisis y pre-procesado de las imágenes es realmente importante. Estos conceptos son mucho más avanzados, pero intentamos dar una visión general de cómo funciona una red neuronal, en este caso, Convolucional y sobre todo de la importancia del pre-proceso de dichas imágenes para optimizar y utilizar los fotogramas con el menor número de bytes posibles.

Figura 9: Explicación de las diferentes técnicas de optimización de fotogramas de las imágenes
obtenidas para conseguir la mayor información posible al menor coste en bytes.

Mostramos los resultados que hemos obtenido entrenando un agente dentro del entorno Breakout y SpaceInvaders. Debido al alto coste de entrenamiento de este tipo de entornos, es imposible hacerlo durante el taller, pero sí mostramos vídeos con dichos resultados.

[Continúa en la segunda parte]

Autores: Pablo González Pérez (@pablogonzalezpe), escritor de los libros "Metasploit para Pentesters", "Hacking con Metasploit: Advanced Pentesting" "Hacking Windows", "Ethical Hacking", "Got Root" y “Pentesting con Powershell”, Microsoft MVP en Seguridad y Security Researcher en el equipo de "Ideas Locas" de la unidad CDO de Telefónica.

Fran Ramírez, (@cyberhadesblog) es investigador de seguridad y miembro del equipo de Ideas Locas en CDO en Telefónica, co-autor del libro "Microhistorias: Anécdotas y Curiosidades de la historia de la informática (y los hackers)", del libro "Docker: SecDevOps" y del blog Cyberhades.