La evaluación de políticas de seguridad basadas en rutas de ficheros a nivel de kernel introduce una sobrecarga computacional significativa debido a la reconstrucción repetitiva del árbol de directorios (dentries) para cada acceso a fichero. Este problema se agrava en cargas de trabajo que acceden frecuentemente a los mismos ficheros o a ficheros dentro de la misma jerarquía de directorios, como las bases de datos. La tesis central es que la memoización, específicamente el caching de resultados de evaluación de políticas, puede mitigar drásticamente esta sobrecarga, transformando una operación costosa de O(profundidad_ruta) en una operación de O(1) en caso de acierto de caché.

El contexto histórico de este problema se remonta a los sistemas operativos Unix y su modelo de ficheros, donde la resolución de rutas es una operación fundamental. Con la emergencia de tecnologías como eBPF, que permiten la instrumentación y el control de bajo nivel en el kernel, la optimización de estas operaciones se vuelve crítica para evitar la degradación del rendimiento del sistema. La necesidad de aplicar políticas de seguridad detalladas a nivel de fichero, combinada con la naturaleza de alto rendimiento de eBPF, impulsa la búsqueda de soluciones eficientes para la evaluación de políticas.

Arquitectura del Sistema

El sistema se basa en un agente de seguridad eBPF que utiliza un hook LSM (Linux Security Module) para interceptar eventos de apertura de ficheros. Antes de la optimización, cada evento de apertura de fichero desencadenaba un proceso de 'slow path' que implicaba:
1. Obtener la ruta completa del fichero.
2. Recorrer el árbol de dentries hacia arriba desde el fichero hasta la raíz.
3. En cada nivel del árbol, verificar si existe una política de seguridad aplicable.
4. Combinar los resultados para determinar la política final (permitir/denegar).

La optimización introduce una caché de políticas basada en inodos, implementada como un mapa eBPF de tipo BPF_MAP_TYPE_LRU_HASH. La clave de la caché es una estructura inode_cache_key compuesta por mntns_id (ID del namespace de montaje), mount_id (ID del montaje específico) e inode (número de inodo). Esta combinación asegura la unicidad de la clave a través de diferentes namespaces y montajes, resolviendo la ambigüedad de los números de inodo que solo son únicos dentro de un montaje. El valor de la caché, inode_policy_cache_value, almacena un access_index (posición de bit para la política de ruta, optimizado para eficiencia espacial) y un state (estado de la caché).

El flujo con la caché es el siguiente:
1. Construir la clave de la caché (inode_cache_key).
2. Buscar la clave en el mapa LRU_HASH.
3. Si hay un acierto, aplicar la política almacenada en caché.
4. Si hay un fallo, ejecutar el 'slow path' original y almacenar el resultado en la caché para futuras consultas. Se manejan los hardlinks (múltiples rutas a un mismo inodo) verificando el i_nlink del inodo; si es mayor que 1, se ignora la caché y se recurre al 'slow path' para garantizar la precisión, priorizando la corrección sobre la cobertura de la caché.

Flujo de Evaluación de Política sin Caché (Slow Path)

  1. 1 Hook LSM (file open) El agente eBPF intercepta el evento de apertura de fichero.
  2. 2 Get File Path Se obtiene la ruta completa del fichero.
  3. 3 Walk Dentry Tree Se recorre el árbol de dentries hacia arriba desde el fichero.
  4. 4 Check Policy at Each Level En cada nivel, se verifica la existencia de una política aplicable.
  5. 5 Combine Results Se combinan las políticas encontradas para determinar la final.
  6. 6 Enforce Policy Se aplica la política (permitir/denegar).

Flujo de Evaluación de Política con Caché

  1. 1 Hook LSM (file open) El agente eBPF intercepta el evento de apertura de fichero.
  2. 2 Build Cache Key Se construye la clave de caché (mntns_id, mount_id, inode).
  3. 3 Lookup in LRU_HASH Map Se busca la clave en el mapa eBPF de tipo LRU_HASH.
  4. 4 Cache Hit? Si hay un acierto, se recupera la política.
  5. 5 Enforce Policy (Cache Hit) Se aplica la política desde la caché.
  6. 6 Cache Miss? Si hay un fallo, se ejecuta el 'slow path'.
  7. 7 Store in Cache El resultado del 'slow path' se almacena en la caché.
  8. 8 Enforce Policy (Cache Miss) Se aplica la política obtenida del 'slow path'.
CapaTecnologíaJustificación
security eBPF Permite la instrumentación a nivel de kernel para interceptar eventos de sistema y aplicar políticas de seguridad sin modificar el código fuente del kernel.
storage Linux Kernel LSM hooks Proporciona los puntos de extensión en el kernel para que el agente eBPF pueda interceptar operaciones de sistema de ficheros, como la apertura de ficheros.
cache BPF_MAP_TYPE_LRU_HASH Implementa la caché de políticas dentro del kernel, utilizando una estrategia LRU para la gestión de entradas y un hash map para búsquedas eficientes. vs dentry-based cache (descartado por complejidad y peso de la clave) __uint(max_entries, 10000)
storage Inodes Sirve como base para la clave de la caché, identificando de forma única los ficheros dentro de un sistema de ficheros montado. vs dentries (descartado por ser punteros y no poder almacenarse directamente en mapas eBPF)

Trade-offs

Ganancias
  • ▲▲ Reducción del consumo de CPU del kernel
  • ▲ Mejora de latencia en la evaluación de políticas
Costes
  • △ Cobertura de caché para hardlinks
  • △ Complejidad de implementación de la lógica de caché en eBPF 
#define INODE_POLICY_CACHE_NO_POLICY 0
#define INODE_POLICY_CACHE_ACCESS_INDEX 1
#define INODE_POLICY_CACHE_GLOBAL_READ_ONLY 2
#define INODE_POLICY_CACHE_ACCESS_INDEX_AND_GLOBAL_RO 3

struct inode_cache_key {
    u64 mntns_id;
    u64 mount_id;
    u64 inode;
};

struct inode_policy_cache_value {
    u32 access_index;
    u8 state;
};

struct {
    __uint(type, BPF_MAP_TYPE_LRU_HASH);
    __uint(max_entries, 10000);
    __type(key, struct inode_cache_key);
    __type(value, struct inode_policy_cache_value);
} bomfather_inode_policy_cache SEC(".maps");
Definición de un mapa eBPF de tipo LRU_HASH para la caché de políticas de inodos, especificando la clave, el valor y el número máximo de entradas.
if (BPF_CORE_READ_INTO(&nlink, inode, i_nlink)) {
    return false;
}
if (nlink != 1) {
    inode_cache_stats_inc(INODE_CACHE_STATS_SKIPS_NLINK);
    return false;
}
Fragmento de código eBPF que verifica el número de enlaces (`i_nlink`) de un inodo para detectar hardlinks y, en ese caso, deshabilitar el uso de la caché para garantizar la precisión.

Fundamentos Teóricos

El concepto de memoización es un principio fundamental en la optimización de algoritmos y sistemas, ampliamente estudiado en la ciencia de la computación. Se relaciona directamente con la programación dinámica, donde los resultados de subproblemas se almacenan para evitar recálculos. En el contexto de sistemas operativos, la gestión de caché para estructuras de datos como inodos y dentries ha sido un área de investigación constante para mejorar el rendimiento del sistema de ficheros. Por ejemplo, el diseño de cachés de bloques y cachés de metadatos en sistemas de ficheros como ext4 o ZFS se basa en principios similares de localidad temporal y espacial.

La elección de un mapa LRU_HASH para la caché de eBPF refleja la aplicación práctica de algoritmos de reemplazo de caché, donde LRU (Least Recently Used) es una estrategia clásica que busca mantener los elementos más relevantes en memoria. Este enfoque se alinea con los trabajos pioneros en gestión de memoria virtual y cachés de CPU, como los descritos por Maurice Wilkes en la década de 1960, que sentaron las bases para entender cómo la jerarquía de memoria y el caching pueden impactar significativamente el rendimiento del sistema. La optimización presentada es una aplicación directa de estos principios clásicos a un problema moderno de seguridad y rendimiento en el kernel de Linux.