# Berkeley Packet Filter

Le BPF (Berkeley Packet Filter ou BSD packet filter), désigne un programme injecté depuis l'espace utilisateur, généralement dans un noyau de système d'exploitation de type Unix, permettant notamment d'effectuer du filtrage réseau.
On distingue l'implémentation initiale, parfois nommée cBPF pour classical BPF, qui désigne un programme minimaliste limité au filtrage de paquets réseau dans le noyau, et sa ré-implémentation moderne nommée eBPF pour extended BPF, autorisant des programmes plus complexes et dont les cas d'usages ne se limitent pas à l'interception de paquets réseau. eBPF est intégré depuis 2013 au noyau Linux. Il existe un portage pour Microsoft Windows, et un autre en cours d'implémentation pour FreeBSD. Le terme BPF peut désigner cBPF comme eBPF, selon le contexte.
Différents problèmes existent encore à ce jour, principalement au niveau du vérificateur.

## Historique

BPF signifie à l'origine BSD packet filter, développé pour UNIX en 1992 par Steven McCanne et Van Jacobson au Laboratoire national Lawrence-Berkeley, afin de capturer des paquets réseau depuis l’espace utilisateur via l'injection de filtres dans le noyau de système d'exploitation, conçus comme des programmes minimalistes$^,$$^,$. Ils permettent alors une amélioration de performances dans les applications d'analyse réseau tel que tcpdump, en évitant la copie de l'intégralité des paquets depuis l'espace noyau vers l'espace utilisateur$^,$$^,$$^,$$^,$.
À l’origine les BPF n’ont pas pour fonction de jeter des paquets reçus, mais décrits comme filtres ils peuvent associer des paquets, copier des paquets, et envoyer des paquets. Initialement les BPF sont implémentés dans le noyau Linux 2.x, disposant de 2 registres 32 bits$^,$$^,$$^,$. Toutefois, de par leur côté minimaliste ils possèdent peu d’instructions, et leur difficulté de programmation fait qu’ils ne sont utilisés que par un petit nombre d’applications telles que tcpdump$^,$.
En 2013, Alexei Starovoitov, alors ingénieur logiciel chez PLUMgrid, refaçonne complètement BPF en y ajoutant de nouvelles fonctionnalités et en améliorant ses performances. Avec Daniel Borkmann, alors ingénieur chez Red Hat, ils intègrent cette implémentation dans le noyau Linux, remplaçant la précédente. Cette nouvelle version est appelée eBPF (extended BPF), et la version antérieure sera rétrospectivement appelée cBPF (classical BPF). eBPF permet de concevoir une plus grande variété de cas d’utilisation, notamment dans le traçage d'événements du noyau, la supervision du trafic réseau, la programmation réseau, la sécurité, etc$^,$. Parmi les changements les plus notables figure le passage à 10 registres de 64 bits$^,$$^,$$^,$, l’appel de fonction dans le kernel grâce à une nouvelle instruction$^,$$^,$, ou encore l'ajout de structures de données telles qu'un ringbuffer et des maps, lesquelles autorisent une persistance d'état qui était impossible précédemment.
eBPF fait son apparition dans la version 3.18 du noyau Linux$^,$$^,$, avec des améliorations continues telles qu’un compilateur JIT (Just In Time)$^,$, de nouvelles fonctionnalités telles que les maps et les tail calls. Les programmes eBPF peuvent s'injecter de différentes manières : via des points d'attache pré-définis (tracepoints), les kprobes du noyau Linux (ou leur version améliorée en 2019, fentry/fexit) ou des uprobes de l'espace utilisateur. Ces dernières permettent par exemple l'accès "en clair" aux paquets chiffrés via une attache dans la bibliothèque OpenSSL. En 2015 et 2016, les possiblités d'attache se sont étoffées, d'abord avec le traffic controller en entrée comme en sortie, puis avec XDP$^,$$^,$.
Les programmes eBPF sont vérifiés et volontairement restreints de différentes manières, notamment en terme de nombre d'instructions autorisées. En 2019, certaines restrictions sont levées : la limite du nombre d'instructions totales disparait, et la limite du nombre d'instructions vérifiées (complexité) passe de 32768 à 1 million.
Un documentaire sur YouTube retrace, avec les auteurs des premiers commits, la genèse de eBPF entre 2013 et 2023.

## Écosystème

Un écosystème d'outils et de bibliothèques s'est constitué autour de la technologie. libbpf est une bibliothèque C permettant de vérifier et charger dans le noyau des objets BPF compilés, en les attachant aux hooks désirés. Elle offre des helpers facilitant la programmation de code eBPF, ainsi que la fonctionnalité CO-RE (Compile Once – Run Everywhere) permettant une portabilité des programmes BPF indépendamment de la version du noyau Linux sur lequel ils s'exécutent. bcc (BPF Compiler Collection) permet d'écrire des programmes eBPF avec un backend en C et un frontend en Python ou Lua. D'autres bibliothèques offrent un support d'eBPF dans d'autres langages, telles que gobpf et ebpf-go en Go, ou Aya en Rust.
Parmi les outils les plus répandus, bpftrace permet d'écrire des scripts traduits en BPF parfois via de simples one-liners, et bpftool permet d'inspecter et manipuler les programmes BPF chargés dans le système.

## Cas d'utilisation

Il existe de multiples cas d'utilisation tel que du traçage (exemple : ply), de l'observabilité (exemples : Hubble, kepler), du filtrage pare-feu, de la mise en réseau de conteneurs (exemple : Cilium (en)), du filtrage de socket, du filtrage de paquet et du contrôle de trafic, de la détection d'intrusion (exemples : suricata, falco), etc.
Il est également possible de faire du filtrage au plus bas niveau de la pile réseau, c’est-à-dire directement par le pilote de la carte d’interface réseau. Ainsi des paquets peuvent être jetés ou redirigés très tôt; par exemple XDP (Express Data Path) est un type de point d'attache eBPF utilisable entre autres pour la prévention d’attaque par déni de service.
De plus, les BPF permettent de faire de la surveillance efficace et flexible des performances d’un réseau pour des applications dans des machines virtuelles, un exemple est le framework vNetTracer.
La variété de cas d'utilisation rapproche eBPF des modules noyau qui peuvent être utilisés à des fins similaires, mais en comparaison, eBPF offre des avantages en terme de sécurité et de maintenance, un programme BPF ne pouvant en théorie pas provoquer d'erreur fatale dans le noyau, et ne nécessitant pas de recompilation pour toute nouvelle version du noyau.

## Fonctionnement technique

BPF utilise des graphes de flot de contrôle (CFG) afin de représenter les critères utilisés dans l'analyse de paquets, et aussi pour sa performance sur les expressions de modèle d’arbre$^,$. Ces graphes sont utilisés par BPF pour mettre en place des règles de filtrage permettant de réduire efficacement les chemins CFG inutiles à l'analyse d'un paquet ainsi que les comparaisons redondantes$^,$.
Le transfert de donnée fait par les appels systèmes se fait de manière bidirectionnelle entre le noyau et l'espace utilisateur. Ceux-ci permettant le bon déroulement de l'injection du code binaire d’eBPF dans le noyau ainsi que la communication des données du noyau cible vers un processus de l'espace utilisateur.
Dans l'implémentation cBPF, les paquets associés par le programme BPF sont en partie copiés dans un buffer avant d’être transférés dans l’espace utilisateur. BPF permet au programme de définir le nombre d’octets du paquet devant être copiés dans le buffer. Cela permet de faire des économies en temps en évitant de copier des données non nécessaires. Par exemple, pour les paquets TCP/IP/Ethernet, 134 octets suffisent. Un programme voulant faire des statistiques sur les trames TCP sera en mesure de copier seulement une partie des trames économisant ainsi du temps d’exécution.
Avec eBPF, le chargement des programmes est réalisé par l'utilisateur, et une vérification est faite sur la terminaison d'un programme afin de s'assurer que celui-ci est sûr à exécuter. Plusieurs structures de données permettent de partager les informations non seulement entre l'espace noyau et l'espace utilisateur, mais également entres les invocations de programmes BPF (par exemple via différents points d'attache):
* Le perf buffer est un tampon circulaire par cœur CPU. Un programme eBPF peut capturer des événements puis les enregistrer dans une structure C, qui sera alors envoyée dans ce tampon. Le tampon peut être lu depuis l'espace utilisateur.
* Le ring buffer est également un tampon circulaire, mais il est global pour l'ensemble des cœurs CPU. Son fonctionnement est similaire au perf buffer.
* Les maps : ce sont des structures de données permettant la persistance des données au cours de l’exécution d’un programme BPF, utilisées notamment pour l’agrégation de statistiques. Plusieurs variantes existent : globales ou par cœur CPU, indexées par valeur numérique ou par hachage, queues, piles, LRU, etc. Les maps peuvent être écrites depuis l'espace noyau et lues depuis l'espace noyau ou utilisateur. Des verrous peuvent être placés pour gérer les accès concurrents.
* Le fichier /sys/kernel/debug/tracing/trace_pipe : Ce fichier peut être lu depuis l’espace utilisateur et écrit par un programme, mais son utilisation est fortement déconseillé car plusieurs traceurs écrivent dessus rendant la lecture incohérente.
Depuis la version 3.15 du noyau Linux les fonctions de la machine virtuelle de eBPF fournissent un accès à la couche liaison grâce à des instructions basiques et à l'introduction de nouvelles fonctionnalités d’eBPF, ceci permet de créer un moyen de filtrer et d’analyser les paquets du réseau. Cependant les programmes eBPF peuvent être invoqués dans différentes couches de la pile réseaux ce qui permet de traiter les paquets capturés avant de progresser vers la couche suivante.
eBPF s’appuie sur un code binaire compilé en instructions natives du CPU au chargement de l'extension dans le noyau. Contrairement au bytecode classique comme Java par exemple, le compilateur et le temps d’exécution d’eBPF n’imposent pas de type ni de sécurité mémoire. Au lieu de cela, la sécurité est renforcée par un vérificateur statique qui vérifie que le programme ne peut pas accéder à des structures de données du noyau ou provoquer des erreurs de page.
Des risques de sécurité et de stabilité sont présents lorsqu'un code est exécuté dans le noyau. Pour pallier ces risques, cBPF compte sur un interpréteur pour exécuter sûrement un programme. Avec eBPF, un vérificateur est introduit pour s’assurer du respect de certaines conditions avant d’être chargé dans le noyau, évitant ainsi un fort coût en temps en vérification à l'exécution. Il s’assure que le programme est en mesure de se terminer, qu'il ne contient pas de boucle pouvant engendrer un blocage du kernel ou que certaines instructions soient inaccessibles. Il vérifie et simule chaque instruction afin d’être sûr que l’état des registres et des piles soient valides, empêchant ainsi l'accès à la mémoire ou à l’état du noyau hors de sa zone allouée$^,$.
Plusieurs programmes eBPF peuvent être instanciés en parallèle, y compris sur les mêmes hooks. Ainsi ils peuvent opérer individuellement ou être chainés. Cela peut nécessiter une forme de coopération et de priorisation pour le chaînage de programmes. bpfman est un projet CNCF "sandbox" visant à faciliter cette coopération.

### Réseaux

Un programme cBPF peut être en écoute sur une interface. Le pilote de l’interface fait alors appel à ce programme en premier. BPF distribue les paquets à chaque filtre qui participe au traitement. Les filtres définis par l'utilisateur s’appliquent aux paquets et décident si chaque paquet est accepté ou non, et combien d'octets de chaque paquet doivent être sauvegardés. Pour chaque filtre acceptant le paquet, BPF copie la quantité de données demandée que le buffer a associé à ce filtre.
Lorsque des modifications de topologies surviennent ou un changement dans les applications, il devient nécessaire de modifier les règles servant de pare-feu afin de pouvoir ajouter, supprimer ou modifier les ports et les adresses impactés par les filtres. Pour cela, grâce à la stratégie de bitmap, qui permet de garder le programme C simple, il suffit de créer un nouveau programme avec de nouvelles maps et de charger la map avec de nouvelles clés-valeur et de l'échanger avec l’ancien programme, imitant ainsi le comportement de iptables-restore.

### Outils
#### Jit compiler

Les filtres sont interprétés sous forme de bytecode dans un kernel avec interpréteur. Dans le cas de l'absence de celui-ci, eBPF peut utiliser le compilateur à la volée du kernel (JIT compiler) afin de traduire les bytecodes produit par eBPF en code natif et de réaliser des optimisations optionnelles dépendant de la machine.

#### LLVM

Clang (LLVM natif) permet à l’utilisateur de compiler son code C en instruction eBPF dans un fichier ELF.

#### BCC

La programmation en instruction eBPF peut être compliquée. C’est pour cela qu’un toolkit appelé BPF Compiler Collection (BCC) existe permettant à l’utilisateur de créer facilement des programmes eBPF. BCC englobe LLVM et l’améliore afin de fournir à l’utilisateur la possibilité de définir des eBPF maps dans un code C et de compiler ce code C en programme eBPF$^,$$^,$$^,$.

### Instructions

La machine virtuelle de BPF+ possède 5 classes d’opération :
* load : copie une valeur dans un registre.
* store : copie un registre à une position fixe dans la mémoire.
* alu : opération arithmétique et logique.
* branch : alter le flux de contrôle, basé sur une comparaison teste entre un registre et une valeur immédiate ou un autre registre.
* return : termine le filtre et retourne le résultat de l'évaluation.

## Limitations

Les programmes eBPF sont volontairement restreints afin de maintenir l'intégrité et la sécurité du système, via des contraintes imposées par le vérificateur, dont voici une liste non exhaustive :
* le nombre d'instructions vérifiées ne peut dépasser 1 million.
* les boucles infinies, ou la récursion infinie sont interdites$^,$.
* la lecture de zone mémoire arbitraire est interdite.
* aucun espace utilisateur ou service tiers ne peut être utilisé dans les programmes eBPF.
* impossibilité de faire des allocations dynamiques.
* les programmes s'exécutent sur un seul thread et donc ont un temps d'exécution lié aux nombres d’instructions.
En 2019, il était fait état de nombreux faux positifs générés par le vérificateur.

## Performance BPF

Les cBPF utilise une stratégie de mise en mémoire tampon qui rend sa performance totale jusqu’à 100 fois plus rapide que le NIT (Network Interface Tap (en)) de SUN s'exécutant sur le même matériel.
Le temps d'exécution d’un appel à BPF est d’environ 6 microseconde par paquet pour un filtre qui rejette tous les paquets.
Les eBPF sont jusqu'à 4 fois plus rapides sur les architecture x86_64 que l’implémentation des cBPF pour certain microbenchmark de filtrage réseaux, et la plupart sont 1.5 fois plus rapides.
Il existe un facteur 10 d’amélioration de performance des eBPF comparé aux IPTABLES et NFTABLES.

### Express Data Path (XDP)

Un programme eBPF XDP est attaché au plus bas niveau de la pile réseau, avant tout traitement par le noyau. Il est adéquat pour le filtrage grossier de paquets tel que la prévention d'attaques par déni de service. Il peut produire quatre fois les performances en comparaison à une tâche similaire dans le kernel.
De plus, XDP offre des améliorations sur la latence médiane en utilisant le code compiler en JIT (Just In Time), jusqu'à 45% d’amélioration de performance avec comme coût une plus haute valeur de latence aberrantes.
XDP offre un compromis, il n’offre pas des performances aussi bonnes que les frameworks dédiés hautes performances qui outrepassent le noyau (DPDK (en), hardware offloading (en)). Cependant il offre une intégration au noyau, c’est-à-dire que les paquets peuvent passer par la pile réseau avec tous ses avantages. Bien qu’il traite seulement 50% du débit d’une ligne 10 GbE, cela représente les performances d’un seul cœur, c’est-à-dire qu’il évolue avec le nombre de cœurs CPU.