BSD Packet Filter

Le BPF, initialement conçu en 1992, est un code binaire minimaliste injecté dans le kernel depuis l’espace utilisateur. Il permet à l’utilisateur de filtrer les paquets circulant dans le kernel tout en évitant de devoir les transférer vers l’espace utilisateur[1] - [2] - [3]. Toutefois, de par son côté minimaliste il possède peu d’instruction, de plus, sa difficulté de programmation fait qu’il est utilisé par un petit nombre d’applications tel que tcpdump[2] - [3]. En 2013, Alexei Starovoitov (ingénieur logiciel spécialisé dans le kernel chez Facebook) refaçonne complètement BPF en y ajoutant de nouvelles fonctionnalités et en améliorant ses performances. Cette nouvelle version est appelée eBPF, opposé à cBPF (classic BPF) désignant la version antérieure. Ce nouveau langage permet de concevoir une plus grande variété de cas d’utilisation, qui se décompose en deux domaines d’applications. Le premier domaine est le traçage du kernel et la supervision, tandis que le deuxième est la programmation réseaux[1].

Il existe de multiples cas d'utilisation tel que du tracing, du filtrage pare-feu ou de la mise en réseau de conteneurs [2], du filtrage de socket, du filtrage de paquet et du contrôle de trafic[4]. 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 très tôt; par exemple XDP(Express Data Path) est un projet utilisant les eBPF qui est utilisable pour la prévention d’attaque par déni de service[4]. 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[3].

Voici une liste non exhaustive de projet utilisant les BPFs[5] :

Traçage / Monitoring:

Bpftrace

est un langage de traçage de haut niveau pour améliorer les Berkeley Packet Filter (eBPF) de Linux, il est disponible dans les versions récentes du noyau linux (soit depuis la version 4.x). De plus bpftrace utilise LLVM pour compiler les scripts, et utilise BCC pour intéragir avec le système BPF de linux[6].

Perf

est un outil d'analyse de performance système développé par la communauté de développement kernel Linux[7].

Ply

est un outil de traçage dynamique léger n'ayant aucune dépendance autre que la libc. Il supporte les architectures x86_64 arch64, arm et powerpc. Il compile des scripts ply en programme BPF et utilise une syntaxe proche du C[8].

Systemtap

est un outil de traçage / sondage, sous licence GPL, qui permet d'outrepasser la routine de recompilation, installation et redémarrage afin de collecter des données. Il possède une interface en ligne de commande ainsi qu'un langage de script[9].

PCP

signifie "Performance Co-Pilot". C'est un ensemble d'outils mature, extensible, multiplateforme qui permet une analyse en direct et rétrospective d'un système[10].

Weave Scope

est un outil de monitoring et de contrôle d'un conteneur Docker en temps réel. Il offre une vue sur des métriques, des tags et des métadonnées de conteneurs; ainsi que de gérer les conteneurs[11].

Networking :

Cilium

est un logiciel open source qui fournit et sécurise les connexions réseau et d'équilibrage de charge entre des conteneurs d'application ou des processus. Il est intégré dans les frameworks d'orchestration Kubernetes et Mesos[12].

Suricata

est un système de détection d'intrusion réseau, un système de prévention d'intrusion et un dispositif de contrôle de sécurité réseau[13].

Systemd

est un ensemble de programmes destiné à la gestion système dans le noyau linux[14].

Iproute2

est un logiciel open source mettant à disposition des utilitaires pour contrôler et surveiller le réseautage dans le kernel linux[15].

P4c-xdp

est un compilateur backend de code P4 pour XDP [16].

Autres :

LLVM

est un compilateur de code C en programme eBPF [17].

BCC

signifiant BPF Compiler Collection, est un toolkit permettant d'écrire des programmes efficaces pour faire du traçage et manipuler le noyau. De plus BCC facilite l'écriture des programmes BPF, avec l'instrumentation du noyau en C et ses front-ends en Python et lua[18].

Libbpf

est une librairie BPF permettant de charger des programmes BPF, sous le format ELF produit par LLVM, dans le kernel[19].

Bpftool

est un outil pour l'inspection et la manipulation de programmes eBPF[20].

Gobpf

est une librairie GO afin de permettre au toolkit BCC de produire des programmes eBPF à partir de code GO[21].

Ebpf_asm

est un assembleur pour programmes eBPF écrit dans une syntaxe se rapprochant de celle d'Intel[22].

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[23] - [24]. De plus 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[24] - [25]. 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[26]. 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[24].

eBPF est une extension de BPF qui en diffère de plusieurs manières : 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[27]. La dernière extension apportée par eBPF est la possibilité d'accéder à des structures de données partagées [27]. En effet pour partager ces données, eBPF utilise trois mécanismes distincts:

• Le tampon PERF: eBPF peut capturer des événements puis les enregistrer dans une structure C, qui sera alors envoyée dans le tampon PERF[28]. Ainsi le tampon PERF est un tampon ayant pour but de contenir des événements et des structures C.
• Les structures maps : ce sont des structures de données ayant la particularité d’être plus évoluées que celle du langage C, puisqu’elles permettent la persistance des données au fur et à mesure de l’exécution d’un programme BPF[28].
• 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[28].

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[29]. 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[25]. 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 par exemple Java, 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[30].

Des risques de sécurité et de stabilité sont présents lorsqu'un code est exécuté dans le kernel. Pour pallier ces risques, BPF compte sur un interpréteur pour exécuter sûrement un programme. Tandis que pour réduire ces risques, eBPF introduit un vérificateur Linux qui s’assure que chaque programme respecte certaines conditions avant d’être chargé dans le kernel évitant ainsi un fort coût en temps en vérification. 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. Et dans un autre temps, il vérifie chaque instruction et la simule 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 kernel hors de sa zone allouée[30] - [31]. L'implémentation d'eBPF fait en sorte d'être sûr et sécurisé pour le kernel mais aussi dans le but d'offrir la possibilité de mettre en place diffère travail dans le kernel tel que le traçage du kernel et faire du réseau [32].

Les appels système permettent le chargement d'un code binaire. Pour que le chargement soit un succès, il faut que le programme soit vérifié par le vérificateur eBPF[32]. Les programmes eBPF peuvent être instanciés en même temps, même sur différent hook. Ainsi ils peuvent opérer individuellement ou bien être chainés[32].

En 2019 différents problèmes se posent encore au développeur tel que:

• le vérificateur fait état de nombreux faux positifs[30].
• le vérificateur n’est pas scalable pour les programmes avec beaucoup de chemin[30].
• le vérificateur ne supporte pas les programmes avec des boucles[30].
• la limitation en taille des programmes (maximum 4096 instructions pour assurer que le programme se termine dans un délai limité car exécuté dans le kernel) [3] - [32].

Il existe des restrictions dans l’utilisation des services kernel, peu de fonctions d’aide et aucun espace utilisateur ou service tiers ne peut être utilisé dans les programmes eBPF[36]. Certaines contraintes rendent les vérifications des programmes flexibles et permettent l’intégrité du système, tel que l’impossibilité de faire des allocations dynamiques, d’accéder aux structures de données kernel, d’appeler les APIs kernel ou de faire des sauts d’instructions indirect. Ainsi que le fait qu’elle s'exécute sur un seul thread et donc ont un temps d'exécution lié aux nombres d’instructions[30] - [32].

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 ) de SUN s'exécutant sur le même matériel [23]. Le temps d'exécution d’un appel à BPF est d’environ 6 microseconde par paquet pour un filtre qui rejette tous les paquets[23]. 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[31]. Il existe un facteur 10 d’amélioration de performance des eBPF comparé aux IPTABLES et NFTABLES[4].

BPF signifie à l’origine “Berkeley packet filter", développés pour UNIX en 1992 afin de faire du filtrage de paquets réseau [4] - [37] , ils permettent alors une amélioration de performances dans les applications de monitoring réseau tel que “tcpdump” [37] - [38] - [1] - [2] - [3]. À l’origine les BPF n’ont pas pour fonction de jeter des paquets reçus, mais décrits comme filtre ils peuvent associer des paquets, copier des paquets, et envoyer des paquets[24]. Initialement les BPF sont implémentés dans le kernel linux 2.x, disposant de 2 registres 32 bits[25] - [39] - [31] - [38]. Puis en 2013, Alexei Starovoitov, propose une amélioration des BPF différenciant maintenant les cBPF (classic BPF) et les eBPF (extended BPF), un des changements les plus notables est le passage à 10 registres de 64 bits[25] - [39] - [31] - [38], ainsi que l’appel de fonction dans le kernel grâce à une nouvelle instruction [31] - [39] - [38] Une autre différence est l'absence de persistance d’état dans les cBPF[40] alors que dans eBPF les états peuvent être maintenus grâce au maps[5]. Les eBPF font leur apparition à la version 3.x du kernel linux [31] - [25], avec des améliorations continues telles qu’un compilateur JIT (Just In Time) [4] - [1], de nouvelles fonctionnalités telles que les “maps” et les “tail calls” [1].

• (en) Justin Pettit, Joe Stringer et Cheng-Chun Tu, « Building an Extensible Open vSwitch Datapath », ACM SIGOPS Operating Systems Review,‎ septembre 2017 (DOI 10.1145/3139645.3139657)

• (en) Sebastiano Miano, Matteo Bertrone, Fulvio Risso, Massimo Tumolo et Mauricio Vásquez B, « Creating Complex Network Services with eBPF: Experience and Lessons Learned », 2018 IEEE 19th International Conference on High Performance Switching and Routing (HPSR),‎ 2018 (ISBN 978-1-5386-7802-2, ISSN 2325-5595, DOI 10.1109/HPSR.2018.8850758)

• (en) Cynthia Sturton, Rohit Sinha et Thurston H. Y. Dang, « Symbolic software model validation », 2013 Eleventh ACM/IEEE International Conference on Formal Methods and Models for Codesign (MEMOCODE 2013),‎ 2013 (ISBN 978-1-4799-0903-2)

• (en) Steven McCanne et Van Jacobson, « The BSD Packet Filter: A New Architecture for User-level Packet Capture », USENIX'93 Proceedings of the USENIX Winter 1993 Conference Proceedings on USENIX Winter 1993 Conference Proceedings,‎ janvier 1993

• (en) S. Ioannidis, K.G. Anagnostakis, J. Ioannidis et A.D. Keromytis, « xPF: packet filtering for low-cost network monitoring », IEEE Xplore,‎ novembre 2002 (ISBN 4-88552-184-X, DOI 10.1109/HPSR.2002.1024219)

• (en) Dominik Scholz, Daniel Raumer, Paul Emmerich, Alexander Kurtz, Krzysztof Lesiak et Georg Carle, « Performance Implications of Packet Filtering with Linux eBPF », IEEE Xplore,‎ septembre 2018 (ISBN 978-0-9883045-5-0, DOI 10.1109/ITC30.2018.00039)

• (en) Suo Kun, Zhao Yong, Chen Wei et Rao Jia, « Demo/poster abstract: Efficient and flexible packet tracing for virtualized networks using eBPF », IEEE INFOCOM 2018 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS),‎ avril 2018 (ISBN 978-1-5386-5979-3, DOI 10.1109/INFCOMW.2018.8406849)

• (en) Dominik Scholz, Daniel Raumer, Paul Emmerich, Alexander Kurtz, Krzysztof Lesiak et Georg Carle, « Performance Implications of Packet Filtering with Linux eBPF », 2018 30th International Teletraffic Congress (ITC 30),‎ 2018, p. 209-217 (ISBN 978-0-9883045-5-0, DOI 10.1109/ITC30.2018.00039)

• (en) Abdulqawi Saif, Lucas Nussbaum et Ye-Qiong Song, « IOscope: A Flexible I/O Tracer for Workloads’ I/O Pattern Characterization », ISC High Performance,‎ juillet 2018, p. 14 (DOI 10.1007/978-3-030-02465-9_7)

• (en) Kun Suo, Yong Zhao, Wei Chen et Jia Rao, « vNetTracer: Efficient and Programmable Packet Tracing in Virtualized Networks », IEEE 38th International Conference on Distributed Computing Systems (ICDCS),‎ juillet 2018 (DOI 10.1109/ICDCS.2018.00026)

• (en) Zhenyu Wu, Mengjun Xie et Haining Wang, « Design and Implementation of a Fast Dynamic Packet Filter », IEEE/ACM Transactions on Networking, vol. 19,‎ octobre 2011, p. 1405 - 1419 (ISSN 1063-6692, DOI 10.1109/TNET.2011.2111381)

• (en) Haina Tang, Lian Duan et Jun Li, « A performance monitoring architecture for IP videoconferencing », 2004 IEEE International Workshop on IP Operations and Management,‎ 2004 (ISBN 0-7803-8836-4, DOI 10.1109/IPOM.2004.1547591)

• (en) Paul Chaignon, Kahina Lazro, Jerome Francois, Thibault Delmas et Olivier Festor, « Oko: Extending Open vSwitch with Stateful Filters », ACM Symposium,‎ novembre 2018, p. 1-13 (DOI 10.1145/3185467.3185496)

• (en) Ludwig Thomeczek, Andreas Attenberger et Johannes Kolb, « Measuring Safety Critical Latency Sources using Linux Kernel eBPF Tracing », ARCS Workshop 2019; 32nd International Conference on Architecture of Computing Systems,‎ mai 2019 (ISBN 978-3-8007-4957-7)

• (en) Xuan-Thuy Dang, Manzoor Ahmed Khan, Sebastian Peters et Tobias Dorsch, « Realization of handover management in SDNized 3GPP architecture with protocol independent forwarding », Innovation in Clouds Internet and Networks and Workshops (ICIN) 2019 22nd Conference,‎ avril 2018, p. 277 - 284 (DOI 10.1109/WD.2018.8361695)

• (en) Jose Fernando Zazo, Sergio Lopez-Buedo, Gustavo Sutter et Javier Aracil, « Automated synthesis of FPGA-based packet filters for 100 Gbps network monitoring applications », 2016 International Conference on ReConFigurable Computing and FPGAs (ReConFig),‎ 2016 (ISBN 978-1-5090-3707-0, DOI 10.1109/ReConFig.2016.7857156)

• (en) Scott Raynel, Anthony McGregor et Murray Jorgensen, « Using the IEEE 802.11 Frame Check Sequence as a pseudo random number for packet sampling in wireless networks », 2009 7th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks,‎ juin 2009, p. 850-855 (ISBN 978-1-4244-4919-4, DOI 10.1109/WIOPT.2009.5291575)

• (en) Mathieu Xhonneux et Olivier Bonaventure, « Flexible failure detection and fast reroute using eBPF and SRv6 », 2018 14th International Conference on Network and Service Management (CNSM),‎ décembre 2018 (ISBN 978-3-9031-7614-0)

• (en) Kurt J. Lidl, Deborah G. Lidl et Paul R. Borman, « Flexible packet filtering: providing a rich toolbox », Proceedings of the BSDCon 2002 Conference,‎ février 2002

• (en) Taekho Nam et JongWon Kim, « Open-source IO visor eBPF-based packet tracing on multiple network interfaces of Linux boxes », 2017 International Conference on Information and Communication Technology Convergence (ICTC),‎ décembre 2017 (ISBN 978-1-5090-4032-2, DOI 10.1109/ICTC.2017.8190996)

• (en) Elazar Gershuni, Nadav Amit, Arie Gurfinkel, Nina Narodytska, Jorge A. Navas, Noam Rinetzky, Leonid Ryzhyk et Mooly Sagiv, « Simple and Precise Static Analysis of Untrusted Linux Kernel Extensions », PLDI 2019: Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation,‎ juin 2019, p. 1069–1084 (DOI 10.1145/3314221.3314590)

• (en) Simon Jouet, Richard Cziva et Dimitrios P. Pezaros, « Arbitrary packet matching in OpenFlow », 2015 IEEE 16th International Conference on High Performance Switching and Routing (HPSR),‎ juillet 2015 (ISBN 978-1-4799-9871-5, DOI 10.1109/HPSR.2015.7483106)

• (en) Nguyen Van Tu, Kyungchan Ko et James Won-Ki Hong, « Architecture for building hybrid kernel-user space virtual network functions », 2017 13th International Conference on Network and Service Management (CNSM),‎ novembre 2017 (ISBN 978-3-901882-98-2, DOI 10.23919/CNSM.2017.8256051)

• (en) Sabur Baidya, Yan Chen et Marco Levorato, « eBPF-based content and computation-aware communication for real-time edge computing », IEEE INFOCOM 2018 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS),‎ avril 2018 (ISBN 978-1-5386-5979-3, DOI 10.1109/INFCOMW.2018.8407006)

• (en) Andrew Begel, Steven McCanne et Susan L. Graham, « BPF+: exploiting global data-flow optimization in a generalized packet filter architecture », ACM SIGCOMM Computer Communication Review, vol. 29, n^o 4,‎ août 1999, p. 123-134 (DOI 10.1145/316194.316214)

• (en) Simon Jouet et Dimitrios P. Pezaros, « BPFabric: Data Plane Programmability for Software Defined Networks », 2017 ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS),‎ mai 2017 (ISBN 978-1-5090-6386-4, DOI 10.1109/ANCS.2017.14)

• (en) Jibum Hong, Seyeon Jeong, Jae-Hyoung Yoo et James Won-Ki Hong, « Design and Implementation of eBPF-based Virtual TAP for Inter-VM Traffic Monitoring », 2018 14th International Conference on Network and Service Management (CNSM),‎ novembre 2018 (ISBN 978-3-9031-7614-0)

• (en) Using eBPF as an Abstraction for Switching, 2018
  Coécrit avec Nicolaas Viljoen.

• (en) TCP-BPF: Programmatically tuning TCP behavior through BPF, 2018
  Coécrit avec Lawrence Brakmo.

• (en) eBPF / XDP based firewall and packet filtering, 2018
  Coécrit avec Anant Deepak, Shankaran Gnanashanmugam, Richard Huang, Puneet Mehra.

• (en) FFPF: Fairly Fast Packet Filters, 2004
  Coécrit avec Herbert Bos , Willem de Bruijn , Mihai Cristea, Trung Nguyen, Georgios Portokalidis.

• (en) Combining kTLS and BPF for Introspection and Policy Enforcement, 2018
  Coécrit avec Daniel Borkmann, John Fastabend.

• (en) Bringing the Power of eBPF to Open vSwitch, 2018
  Coécrit avec William Tu Joe Stringer Yifeng Sun Yi-Hung Wei.
• (en) Xenofontas Dimitropoulos, Michail Vlachos et Luca Deri, « pcapIndex: an index for network packet traces with legacy compatibility », ACM SIGCOMM Computer Communication Review, vol. 42,‎ janvier 2012, p. 47-53 (DOI 10.1145/2096149.2096156)

• (en) Jibum Hong, Seyeon Jeong, Jae-Hyoun Yoo et James Won-Ki Hong, « Design and Implementation of eBPF-based Virtual TAP for Inter-VM Traffic Monitoring », 2018 14th International Conference on Network and Service Management (CNSM),‎ 2018 (ISBN 978-1-5386-9193-9, ISSN 2165-9605)

• Jugurtha Belkalem, « Les secrets du traceur eBPF », sur www.linuxembedded.fr, 14 mars 2019

• (en) « eBPF, part 1: Past, Present, and Future », sur https://ferrisellis.com/, 28 avril 2017

• (en) Cilium Authors, « BPF and XDP Reference Guide », sur https://cilium.readthedocs.io/en/v1.6/, 30 septembre 2019.

• (en) Jonathan Corbet, « BPF: the universal in-kernel virtual machine », sur https://lwn.net/, 21 mai 2014.

• (en) Quentin Monnet, « Dive into BPF: a list of reading material », sur https://qmonnet.github.io/, 1^er septembre 2016.

• (en) Ferris Ellis, « eBPF, part 2: Syscall and Map Types », sur https://ferrisellis.com/, 11 mai 2017.

• (en) Matt Fleming, « A thorough introduction to eBPF », sur https://lwn.net/, 2 décembre 2017.

• Berkeley software distribution