Entregable Reto 3

Tema

• Nociones de conteo
• Permutaciones y combinaciones
• Concepto de algoritmo
• Introducción al análisis de algoritmos

Instrucciones

Contexto:

En un sistema de monitoreo de seguridad digital, cada acción de los usuarios queda registrada como un evento estructurado. A partir de estos registros, es posible diseñar algoritmos que detecten patrones de comportamiento sospechoso. Sin embargo, la eficiencia de estos algoritmos es clave: mientras más grande sea el conjunto de eventos, más costoso puede ser el análisis. En este reto, aplicarás lógica condicional, estructuras de datos y análisis algorítmico para detectar riesgos.

Pregunta esencial:

¿Cómo diseñar y evaluar algoritmos que detecten comportamientos sospechosos de forma eficiente en sistemas digitales de gran escala?

Objetivo:

Implementar en Python una función que recorra el registro de eventos utilizando bucles anidados, aplique tres reglas de detección de patrones sospechosos y devuelva una lista de alertas que identifique al usuario, la regla violada y los índices de los eventos relevantes. Evaluar su complejidad formalmente y contrastarla con resultados experimentales.

Indicaciones:

1. Generación de datos simulados:
   • Genera una lista llamada events que simule un registro de eventos ordenado por tiempo. Cada elemento debe ser un diccionario con la siguiente estructura:
   • "timestamp": marca temporal del evento (entero que represente segundos desde el inicio).
   • "user_id": identificador del usuario. Define al menos 10 usuarios distintos (por ejemplo, "u01" a "u10").
   • "action": tipo de acción registrada. Usa como posibles valores: "login_fail", "login_success", "access", "chmod".
   • "resource": componente afectado por la acción. Usa una lista de al menos 5 recursos, incluyendo "db" y "root_fs" como críticos.
   • Genera cinco conjuntos de datos simulados con tamaños de:
     • 100 eventos
     • 1.000 eventos
     • 10.000 eventos
     • 100.000 eventos
     • 1.000.000 eventos
   • Asegúrate de que algunos eventos cumplan las condiciones de las reglas descritas más abajo y que otros no cumplan ninguna regla, para evitar falsos positivos.
2. Implementación del algoritmo de detección:
   • Implementa una única función llamada detect_suspicious(events) que reciba la lista de eventos como parámetro y retorne una lista de alertas.
   • Cada alerta debe ser una tupla de la forma:
     • (user_id, rule_id, [i, j, ...])
   • user_id: identificador del usuario.
   • rule_id: entero 1, 2 o 3 según la regla violada.
   • [i, j, ...]: índices dentro del arreglo events que activaron la alerta.
   • El algoritmo debe recorrer el arreglo de eventos usando dos bucles anidados.
   • Solo deben compararse eventos del mismo user_id.
   • Evaluar las siguientes reglas:
     • Regla 1: Tres o más eventos "login_fail" del mismo usuario en un intervalo de 60 segundos.
     • Regla 2: Al menos dos accesos ("access") del mismo usuario a recursos distintos dentro de CRITICAL = {"db", "root_fs"} en un intervalo de 60 segundos.
     • Regla 3: Un evento "login_success" seguido de un "chmod" del mismo usuario dentro de un intervalo de 5 minutos.
3. Análisis experimental del tiempo de ejecución:
   • Utiliza herramientas como time o timeit para medir el tiempo de ejecución de detect_suspicious(events).
   • Repite cada medición al menos 5 veces y calcula el promedio.
   • Representa gráficamente los resultados usando matplotlib.
4. Análisis formal:
   • Justifica teóricamente la complejidad del algoritmo.
   • Reflexiona:
     • ¿Cuál regla es más costosa de evaluar?
     • ¿Cómo podría optimizarse el algoritmo sin cambiar su lógica?
     • ¿Qué tiempo se tardaría en revisar 100.000.000 eventos?
5. Producto por entregar:
   • Un único archivo IPYNB (Jupyter Notebook) que contenga:
     • Introducción (objetivos, contexto, lista de eventos).
     • Generación de datos simulados.
     • Implementación de la función.
     • Medición experimental del tiempo (gráfico tamaño del input vs. tiempo de ejecución).
     • Análisis formal.
     • Conclusiones.
   • El notebook debe estar correctamente estructurado, comentado y ejecutarse sin errores.
   • Video explicativo de máximo 5 minutos que presente cada sección del archivo IPYNB, junto con explicaciones.