Mobile menu icon
Skip to navigation | Skip to main content | Skip to footer
Mobile menu icon Search iconSearch
Search type

Department of Computer Science


Formally Verifying eBPF

Primary supervisor

Additional supervisors

  • Lucas Cordeiro

Additional information

Contact admissions office

Other projects with the same supervisor

Funding

  • Competition Funded Project (Students Worldwide)

This research project is one of a number of projects at this institution. It is in competition for funding with one or more of these projects. Usually the project which receives the best applicant will be awarded the funding. Applications for this project are welcome from suitably qualified candidates worldwide. Funding may only be available to a limited set of nationalities and you should read the full department and project details for further information.

Project description

Help me make operating systems safer and more secure using formal methods to verify Berkeley Packet Filtering!

The Berkeley Packet Filtering (BPF) was originally designed to analyze network traffic.
Nowadays, extended BPF has become an important part of Linux server platforms.
For example, there are at least 40 BPF programs active on every server at Facebook, and at least 14 at the servers powering Netflix [1].

Internally, BPF works by executing a user-provided program directly in kernel space.
This allows for very efficient programs, but thorough checks are required to not compromise security.
Bugs in the BPF implementation can and do lead to catastrophic security errors, e.g. CVE-2020-8835, CVE-2019-7308, CVE-2017-16995.

BPF can also be used for non-network related tasks like performance analysis [2],
and further extensions of eBPF are discussed, which will make its implementation even more complex,
and thus more susceptible to bugs.

The goal of this project is to formally verify an eBPF implementation, that is, to rigorously prove that it has no bugs.
In a next step, advanced features and eBPF checking techniques are to be explored, with formal verification ensuring that
their complex implementations they have no bugs.

The formal verification is done with an interactive theorem prover (ITP).
ITPs are tools for the development of computer-checked mathematical proofs.
State-of-the art ITPs that have successfully been used for software verification are Isabelle/HOL [3] and Coq [4].


If you are interested in applying state-of-the-art theorem proving to make Linux a bit safer, contact peter.lammich@manchester.ac.uk!
Training on using Isabelle/HOL will be provided if necessary!


Related work:
Xi Wang, et al.: Jitk: A Trustworthy In-Kernel Interpreter Infrastructure. OSDI 2014
-- verification of the old "classic BPF" system of Linux 3.15 in Coq.

Klein et al., seL4: Formal Verification of an OS Kernel, SOSP 2009
-- verification of a microkernel for embedded systems in Isabelle/HOL


Info about eBPF in Linux:
[1] http://www.brendangregg.com/blog/2019-12-02/bpf-a-new-type-of-software.html
[2] Book: Brendan Gregg, BPF Performance Tools

Theorem Provers:
[3] Isabelle/HOL: https://isabelle.in.tum.de/
[4] Coq: https://coq.inria.fr/

Person specification

For information

Essential

Applicants will be required to evidence the following skills and qualifications.

  • This project requires mathematical engagement and ability substantially greater than for a typical Computer Science PhD. Give evidence for appropriate competence, as relevant to the project description.
  • You must be capable of performing at a very high level.
  • You must have a self-driven interest in uncovering and solving unknown problems and be able to work hard and creatively without constant supervision.

Desirable

Applicants will be required to evidence the following skills and qualifications.

  • You will have good time management.
  • You will possess determination (which is often more important than qualifications) although you'll need a good amount of both.

General

Applicants will be required to address the following.

  • Comment on your transcript/predicted degree marks, outlining both strong and weak points.
  • Discuss your final year Undergraduate project work - and if appropriate your MSc project work.
  • How well does your previous study prepare you for undertaking Postgraduate Research?
  • Why do you believe you are suitable for doing Postgraduate Research?