<!DOCTYPE html>
<html lang="en" data-content_root="../">
<head>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" /><meta name="viewport" content="width=device-width, initial-scale=1" />
<title>eBPF verifier — The Linux Kernel documentation</title>
<link rel="stylesheet" type="text/css" href="../_static/pygments.css?v=fa44fd50" />
<link rel="stylesheet" type="text/css" href="../_static/alabaster.css?v=3918102e" />
<script src="../_static/documentation_options.js?v=5929fcd5"></script>
<script src="../_static/doctools.js?v=9bcbadda"></script>
<script src="../_static/sphinx_highlight.js?v=dc90522c"></script>
<link rel="index" title="Index" href="../genindex.html" />
<link rel="search" title="Search" href="../search.html" />
<link rel="next" title="libbpf" href="libbpf/index.html" />
<link rel="prev" title="BPF Documentation" href="index.html" />
<link rel="stylesheet" href="../_static/custom.css" type="text/css" />
</head><body>
<div class="document">
<div class="sphinxsidebar" role="navigation" aria-label="Main">
<div class="sphinxsidebarwrapper">
<p class="logo"><a href="../index.html">
<img class="logo" src="../_static/logo.svg" alt="Logo of The Linux Kernel"/>
</a></p>
<h1 class="logo"><a href="../index.html">The Linux Kernel</a></h1>
<p class="blurb">6.18.50</p>
<search id="searchbox" style="display: none" role="search">
<h3 id="searchlabel">Quick search</h3>
<div class="searchformwrapper">
<form class="search" action="../search.html" method="get">
<input type="text" name="q" aria-labelledby="searchlabel" autocomplete="off" autocorrect="off" autocapitalize="off" spellcheck="false"/>
<input type="submit" value="Go" />
</form>
</div>
</search>
<script>document.getElementById('searchbox').style.display = "block"</script>
<p>
<h3 class="kernel-toc-contents">Contents</h3>
<input type="checkbox" class="kernel-toc-toggle" id = "kernel-toc-toggle" checked>
<label class="kernel-toc-title" for="kernel-toc-toggle"></label>
<div class="kerneltoc" id="kerneltoc">
<ul>
<li class="toctree-l1"><a class="reference internal" href="../process/development-process.html">Development process</a></li>
<li class="toctree-l1"><a class="reference internal" href="../process/submitting-patches.html">Submitting patches</a></li>
<li class="toctree-l1"><a class="reference internal" href="../process/code-of-conduct.html">Code of conduct</a></li>
<li class="toctree-l1"><a class="reference internal" href="../maintainer/index.html">Maintainer handbook</a></li>
<li class="toctree-l1"><a class="reference internal" href="../process/index.html">All development-process docs</a></li>
</ul>
<ul class="current">
<li class="toctree-l1"><a class="reference internal" href="../core-api/index.html">Core API</a></li>
<li class="toctree-l1"><a class="reference internal" href="../driver-api/index.html">Driver APIs</a></li>
<li class="toctree-l1 current"><a class="reference internal" href="../subsystem-apis.html">Subsystems</a><ul class="current">
<li class="toctree-l2"><a class="reference internal" href="../subsystem-apis.html#core-subsystems">Core subsystems</a></li>
<li class="toctree-l2"><a class="reference internal" href="../subsystem-apis.html#human-interfaces">Human interfaces</a></li>
<li class="toctree-l2"><a class="reference internal" href="../subsystem-apis.html#networking-interfaces">Networking interfaces</a></li>
<li class="toctree-l2"><a class="reference internal" href="../subsystem-apis.html#storage-interfaces">Storage interfaces</a></li>
<li class="toctree-l2 current"><a class="reference internal" href="../subsystem-apis.html#other-subsystems">Other subsystems</a><ul class="current">
<li class="toctree-l3"><a class="reference internal" href="../accounting/index.html">Accounting</a></li>
<li class="toctree-l3"><a class="reference internal" href="../cpu-freq/index.html">CPUFreq - CPU frequency and voltage scaling code in the Linux(TM) kernel</a></li>
<li class="toctree-l3"><a class="reference internal" href="../edac/index.html">EDAC Subsystem</a></li>
<li class="toctree-l3"><a class="reference internal" href="../fpga/index.html">FPGA</a></li>
<li class="toctree-l3"><a class="reference internal" href="../i2c/index.html">I2C/SMBus Subsystem</a></li>
<li class="toctree-l3"><a class="reference internal" href="../iio/index.html">Industrial I/O</a></li>
<li class="toctree-l3"><a class="reference internal" href="../pcmcia/index.html">PCMCIA</a></li>
<li class="toctree-l3"><a class="reference internal" href="../spi/index.html">Serial Peripheral Interface (SPI)</a></li>
<li class="toctree-l3"><a class="reference internal" href="../w1/index.html">1-Wire Subsystem</a></li>
<li class="toctree-l3"><a class="reference internal" href="../watchdog/index.html">Watchdog Support</a></li>
<li class="toctree-l3"><a class="reference internal" href="../virt/index.html">Virtualization Support</a></li>
<li class="toctree-l3"><a class="reference internal" href="../hwmon/index.html">Hardware Monitoring</a></li>
<li class="toctree-l3"><a class="reference internal" href="../accel/index.html">Compute Accelerators</a></li>
<li class="toctree-l3"><a class="reference internal" href="../security/index.html">Security Documentation</a></li>
<li class="toctree-l3"><a class="reference internal" href="../crypto/index.html">Crypto API</a></li>
<li class="toctree-l3 current"><a class="reference internal" href="index.html">BPF Documentation</a></li>
<li class="toctree-l3"><a class="reference internal" href="../usb/index.html">USB support</a></li>
<li class="toctree-l3"><a class="reference internal" href="../PCI/index.html">PCI Bus Subsystem</a></li>
<li class="toctree-l3"><a class="reference internal" href="../misc-devices/index.html">Assorted Miscellaneous Devices Documentation</a></li>
<li class="toctree-l3"><a class="reference internal" href="../peci/index.html">PECI Subsystem</a></li>
<li class="toctree-l3"><a class="reference internal" href="../wmi/index.html">WMI Subsystem</a></li>
<li class="toctree-l3"><a class="reference internal" href="../tee/index.html">TEE Subsystem</a></li>
</ul>
</li>
</ul>
</li>
<li class="toctree-l1"><a class="reference internal" href="../locking/index.html">Locking</a></li>
</ul>
<ul>
<li class="toctree-l1"><a class="reference internal" href="../process/license-rules.html">Licensing rules</a></li>
<li class="toctree-l1"><a class="reference internal" href="../doc-guide/index.html">Writing documentation</a></li>
<li class="toctree-l1"><a class="reference internal" href="../dev-tools/index.html">Development tools</a></li>
<li class="toctree-l1"><a class="reference internal" href="../dev-tools/testing-overview.html">Testing guide</a></li>
<li class="toctree-l1"><a class="reference internal" href="../kernel-hacking/index.html">Hacking guide</a></li>
<li class="toctree-l1"><a class="reference internal" href="../trace/index.html">Tracing</a></li>
<li class="toctree-l1"><a class="reference internal" href="../fault-injection/index.html">Fault injection</a></li>
<li class="toctree-l1"><a class="reference internal" href="../livepatch/index.html">Livepatching</a></li>
<li class="toctree-l1"><a class="reference internal" href="../rust/index.html">Rust</a></li>
</ul>
<ul>
<li class="toctree-l1"><a class="reference internal" href="../admin-guide/index.html">Administration</a></li>
<li class="toctree-l1"><a class="reference internal" href="../kbuild/index.html">Build system</a></li>
<li class="toctree-l1"><a class="reference internal" href="../admin-guide/reporting-issues.html">Reporting issues</a></li>
<li class="toctree-l1"><a class="reference internal" href="../tools/index.html">Userspace tools</a></li>
<li class="toctree-l1"><a class="reference internal" href="../userspace-api/index.html">Userspace API</a></li>
</ul>
<ul>
<li class="toctree-l1"><a class="reference internal" href="../firmware-guide/index.html">Firmware</a></li>
<li class="toctree-l1"><a class="reference internal" href="../devicetree/index.html">Firmware and Devicetree</a></li>
</ul>
<ul>
<li class="toctree-l1"><a class="reference internal" href="../arch/index.html">CPU architectures</a></li>
</ul>
<ul>
<li class="toctree-l1"><a class="reference internal" href="../staging/index.html">Unsorted documentation</a></li>
</ul>
<ul>
<li class="toctree-l1"><a class="reference internal" href="../translations/index.html">Translations</a></li>
</ul>
</div>
<script type="text/javascript"> <!--
var sbar = document.getElementsByClassName("sphinxsidebar")[0];
let currents = document.getElementsByClassName("current")
if (currents.length) {
sbar.scrollTop = currents[currents.length - 1].offsetTop;
}
--> </script>
<div role="note" aria-label="source link">
<h3>This Page</h3>
<ul class="this-page-menu">
<li><a href="../_sources/bpf/verifier.rst.txt"
rel="nofollow">Show Source</a></li>
</ul>
</div>
</div>
</div>
<div class="documentwrapper">
<div class="bodywrapper">
<div class="body" role="main">
<section id="ebpf-verifier">
<h1>eBPF verifier<a class="headerlink" href="#ebpf-verifier" title="Link to this heading">¶</a></h1>
<p>The safety of the eBPF program is determined in two steps.</p>
<p>First step does DAG check to disallow loops and other CFG validation.
In particular it will detect programs that have unreachable instructions.
(though classic BPF checker allows them)</p>
<p>Second step starts from the first insn and descends all possible paths.
It simulates execution of every insn and observes the state change of
registers and stack.</p>
<p>At the start of the program the register R1 contains a pointer to context
and has type PTR_TO_CTX.
If verifier sees an insn that does R2=R1, then R2 has now type
PTR_TO_CTX as well and can be used on the right hand side of expression.
If R1=PTR_TO_CTX and insn is R2=R1+R1, then R2=SCALAR_VALUE,
since addition of two valid pointers makes invalid pointer.
(In ‘secure’ mode verifier will reject any type of pointer arithmetic to make
sure that kernel addresses don’t leak to unprivileged users)</p>
<p>If register was never written to, it’s not readable:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>bpf_mov R0 = R2
bpf_exit
</pre></div>
</div>
<p>will be rejected, since R2 is unreadable at the start of the program.</p>
<p>After kernel function call, R1-R5 are reset to unreadable and
R0 has a return type of the function.</p>
<p>Since R6-R9 are callee saved, their state is preserved across the call.</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>bpf_mov R6 = 1
bpf_call foo
bpf_mov R0 = R6
bpf_exit
</pre></div>
</div>
<p>is a correct program. If there was R1 instead of R6, it would have
been rejected.</p>
<p>load/store instructions are allowed only with registers of valid types, which
are PTR_TO_CTX, PTR_TO_MAP, PTR_TO_STACK. They are bounds and alignment checked.
For example:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>bpf_mov R1 = 1
bpf_mov R2 = 2
bpf_xadd *(u32 *)(R1 + 3) += R2
bpf_exit
</pre></div>
</div>
<p>will be rejected, since R1 doesn’t have a valid pointer type at the time of
execution of instruction bpf_xadd.</p>
<p>At the start R1 type is PTR_TO_CTX (a pointer to generic <code class="docutils literal notranslate"><span class="pre">struct</span> <span class="pre">bpf_context</span></code>)
A callback is used to customize verifier to restrict eBPF program access to only
certain fields within ctx structure with specified size and alignment.</p>
<p>For example, the following insn:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>bpf_ld R0 = *(u32 *)(R6 + 8)
</pre></div>
</div>
<p>intends to load a word from address R6 + 8 and store it into R0
If R6=PTR_TO_CTX, via <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">is_valid_access()</span></code> callback the verifier will know
that offset 8 of size 4 bytes can be accessed for reading, otherwise
the verifier will reject the program.
If R6=PTR_TO_STACK, then access should be aligned and be within
stack bounds, which are [-MAX_BPF_STACK, 0). In this example offset is 8,
so it will fail verification, since it’s out of bounds.</p>
<p>The verifier will allow eBPF program to read data from stack only after
it wrote into it.</p>
<p>Classic BPF verifier does similar check with M[0-15] memory slots.
For example:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>bpf_ld R0 = *(u32 *)(R10 - 4)
bpf_exit
</pre></div>
</div>
<p>is invalid program.
Though R10 is correct read-only register and has type PTR_TO_STACK
and R10 - 4 is within stack bounds, there were no stores into that location.</p>
<p>Pointer register spill/fill is tracked as well, since four (R6-R9)
callee saved registers may not be enough for some programs.</p>
<p>Allowed function calls are customized with bpf_verifier_ops-><code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">get_func_proto()</span></code>
The eBPF verifier will check that registers match argument constraints.
After the call register R0 will be set to return type of the function.</p>
<p>Function calls is a main mechanism to extend functionality of eBPF programs.
Socket filters may let programs to call one set of functions, whereas tracing
filters may allow completely different set.</p>
<p>If a function made accessible to eBPF program, it needs to be thought through
from safety point of view. The verifier will guarantee that the function is
called with valid arguments.</p>
<p>seccomp vs socket filters have different security restrictions for classic BPF.
Seccomp solves this by two stage verifier: classic BPF verifier is followed
by seccomp verifier. In case of eBPF one configurable verifier is shared for
all use cases.</p>
<p>See details of eBPF verifier in kernel/bpf/verifier.c</p>
<section id="register-value-tracking">
<h2>Register value tracking<a class="headerlink" href="#register-value-tracking" title="Link to this heading">¶</a></h2>
<p>In order to determine the safety of an eBPF program, the verifier must track
the range of possible values in each register and also in each stack slot.
This is done with <code class="docutils literal notranslate"><span class="pre">struct</span> <span class="pre">bpf_reg_state</span></code>, defined in include/linux/
bpf_verifier.h, which unifies tracking of scalar and pointer values. Each
register state has a type, which is either NOT_INIT (the register has not been
written to), SCALAR_VALUE (some value which is not usable as a pointer), or a
pointer type. The types of pointers describe their base, as follows:</p>
<blockquote>
<div><dl class="simple">
<dt>PTR_TO_CTX</dt><dd><p>Pointer to bpf_context.</p>
</dd>
<dt>CONST_PTR_TO_MAP</dt><dd><p>Pointer to <code class="xref c c-struct broken_xref docutils literal notranslate"><span class="pre">struct</span> <span class="pre">bpf_map</span></code>. “Const” because arithmetic
on these pointers is forbidden.</p>
</dd>
<dt>PTR_TO_MAP_VALUE</dt><dd><p>Pointer to the value stored in a map element.</p>
</dd>
<dt>PTR_TO_MAP_VALUE_OR_NULL</dt><dd><p>Either a pointer to a map value, or NULL; map accesses
(see <a class="reference internal" href="maps.html"><span class="doc">BPF maps</span></a>) return this type, which becomes a
PTR_TO_MAP_VALUE when checked != NULL. Arithmetic on
these pointers is forbidden.</p>
</dd>
<dt>PTR_TO_STACK</dt><dd><p>Frame pointer.</p>
</dd>
<dt>PTR_TO_PACKET</dt><dd><p>skb->data.</p>
</dd>
<dt>PTR_TO_PACKET_END</dt><dd><p>skb->data + headlen; arithmetic forbidden.</p>
</dd>
<dt>PTR_TO_SOCKET</dt><dd><p>Pointer to <code class="xref c c-struct broken_xref docutils literal notranslate"><span class="pre">struct</span> <span class="pre">bpf_sock_ops</span></code>, implicitly refcounted.</p>
</dd>
<dt>PTR_TO_SOCKET_OR_NULL</dt><dd><p>Either a pointer to a socket, or NULL; socket lookup
returns this type, which becomes a PTR_TO_SOCKET when
checked != NULL. PTR_TO_SOCKET is reference-counted,
so programs must release the reference through the
socket release function before the end of the program.
Arithmetic on these pointers is forbidden.</p>
</dd>
</dl>
</div></blockquote>
<p>However, a pointer may be offset from this base (as a result of pointer
arithmetic), and this is tracked in two parts: the ‘fixed offset’ and ‘variable
offset’. The former is used when an exactly-known value (e.g. an immediate
operand) is added to a pointer, while the latter is used for values which are
not exactly known. The variable offset is also used in SCALAR_VALUEs, to track
the range of possible values in the register.</p>
<p>The verifier’s knowledge about the variable offset consists of:</p>
<ul class="simple">
<li><p>minimum and maximum values as unsigned</p></li>
<li><p>minimum and maximum values as signed</p></li>
<li><p>knowledge of the values of individual bits, in the form of a ‘tnum’: a u64
‘mask’ and a u64 ‘value’. 1s in the mask represent bits whose value is unknown;
1s in the value represent bits known to be 1. Bits known to be 0 have 0 in both
mask and value; no bit should ever be 1 in both. For example, if a byte is read
into a register from memory, the register’s top 56 bits are known zero, while
the low 8 are unknown - which is represented as the tnum (0x0; 0xff). If we
then OR this with 0x40, we get (0x40; 0xbf), then if we add 1 we get (0x0;
0x1ff), because of potential carries.</p></li>
</ul>
<p>Besides arithmetic, the register state can also be updated by conditional
branches. For instance, if a SCALAR_VALUE is compared > 8, in the ‘true’ branch
it will have a umin_value (unsigned minimum value) of 9, whereas in the ‘false’
branch it will have a umax_value of 8. A signed compare (with BPF_JSGT or
BPF_JSGE) would instead update the signed minimum/maximum values. Information
from the signed and unsigned bounds can be combined; for instance if a value is
first tested < 8 and then tested s> 4, the verifier will conclude that the value
is also > 4 and s< 8, since the bounds prevent crossing the sign boundary.</p>
<p>PTR_TO_PACKETs with a variable offset part have an ‘id’, which is common to all
pointers sharing that same variable offset. This is important for packet range
checks: after adding a variable to a packet pointer register A, if you then copy
it to another register B and then add a constant 4 to A, both registers will
share the same ‘id’ but the A will have a fixed offset of +4. Then if A is
bounds-checked and found to be less than a PTR_TO_PACKET_END, the register B is
now known to have a safe range of at least 4 bytes. See ‘Direct packet access’,
below, for more on PTR_TO_PACKET ranges.</p>
<p>The ‘id’ field is also used on PTR_TO_MAP_VALUE_OR_NULL, common to all copies of
the pointer returned from a map lookup. This means that when one copy is
checked and found to be non-NULL, all copies can become PTR_TO_MAP_VALUEs.
As well as range-checking, the tracked information is also used for enforcing
alignment of pointer accesses. For instance, on most systems the packet pointer
is 2 bytes after a 4-byte alignment. If a program adds 14 bytes to that to jump
over the Ethernet header, then reads IHL and adds (IHL * 4), the resulting
pointer will have a variable offset known to be 4n+2 for some n, so adding the 2
bytes (NET_IP_ALIGN) gives a 4-byte alignment and so word-sized accesses through
that pointer are safe.
The ‘id’ field is also used on PTR_TO_SOCKET and PTR_TO_SOCKET_OR_NULL, common
to all copies of the pointer returned from a socket lookup. This has similar
behaviour to the handling for PTR_TO_MAP_VALUE_OR_NULL->PTR_TO_MAP_VALUE, but
it also handles reference tracking for the pointer. PTR_TO_SOCKET implicitly
represents a reference to the corresponding <code class="docutils literal notranslate"><span class="pre">struct</span> <span class="pre">sock</span></code>. To ensure that the
reference is not leaked, it is imperative to NULL-check the reference and in
the non-NULL case, and pass the valid reference to the socket release function.</p>
</section>
<section id="direct-packet-access">
<h2>Direct packet access<a class="headerlink" href="#direct-packet-access" title="Link to this heading">¶</a></h2>
<p>In cls_bpf and act_bpf programs the verifier allows direct access to the packet
data via skb->data and skb->data_end pointers.
Ex:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>1: r4 = *(u32 *)(r1 +80) /* load skb->data_end */
2: r3 = *(u32 *)(r1 +76) /* load skb->data */
3: r5 = r3
4: r5 += 14
5: if r5 > r4 goto pc+16
R1=ctx R3=pkt(id=0,off=0,r=14) R4=pkt_end R5=pkt(id=0,off=14,r=14) R10=fp
6: r0 = *(u16 *)(r3 +12) /* access 12 and 13 bytes of the packet */
</pre></div>
</div>
<p>this 2byte load from the packet is safe to do, since the program author
did check <code class="docutils literal notranslate"><span class="pre">if</span> <span class="pre">(skb->data</span> <span class="pre">+</span> <span class="pre">14</span> <span class="pre">></span> <span class="pre">skb->data_end)</span> <span class="pre">goto</span> <span class="pre">err</span></code> at insn #5 which
means that in the fall-through case the register R3 (which points to skb->data)
has at least 14 directly accessible bytes. The verifier marks it
as R3=pkt(id=0,off=0,r=14).
id=0 means that no additional variables were added to the register.
off=0 means that no additional constants were added.
r=14 is the range of safe access which means that bytes [R3, R3 + 14) are ok.
Note that R5 is marked as R5=pkt(id=0,off=14,r=14). It also points
to the packet data, but constant 14 was added to the register, so
it now points to <code class="docutils literal notranslate"><span class="pre">skb->data</span> <span class="pre">+</span> <span class="pre">14</span></code> and accessible range is [R5, R5 + 14 - 14)
which is zero bytes.</p>
<p>More complex packet access may look like:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>R0=inv1 R1=ctx R3=pkt(id=0,off=0,r=14) R4=pkt_end R5=pkt(id=0,off=14,r=14) R10=fp
6: r0 = *(u8 *)(r3 +7) /* load 7th byte from the packet */
7: r4 = *(u8 *)(r3 +12)
8: r4 *= 14
9: r3 = *(u32 *)(r1 +76) /* load skb->data */
10: r3 += r4
11: r2 = r1
12: r2 <<= 48
13: r2 >>= 48
14: r3 += r2
15: r2 = r3
16: r2 += 8
17: r1 = *(u32 *)(r1 +80) /* load skb->data_end */
18: if r2 > r1 goto pc+2
R0=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R1=pkt_end R2=pkt(id=2,off=8,r=8) R3=pkt(id=2,off=0,r=8) R4=inv(id=0,umax_value=3570,var_off=(0x0; 0xfffe)) R5=pkt(id=0,off=14,r=14) R10=fp
19: r1 = *(u8 *)(r3 +4)
</pre></div>
</div>
<p>The state of the register R3 is R3=pkt(id=2,off=0,r=8)
id=2 means that two <code class="docutils literal notranslate"><span class="pre">r3</span> <span class="pre">+=</span> <span class="pre">rX</span></code> instructions were seen, so r3 points to some
offset within a packet and since the program author did
<code class="docutils literal notranslate"><span class="pre">if</span> <span class="pre">(r3</span> <span class="pre">+</span> <span class="pre">8</span> <span class="pre">></span> <span class="pre">r1)</span> <span class="pre">goto</span> <span class="pre">err</span></code> at insn #18, the safe range is [R3, R3 + 8).
The verifier only allows ‘add’/’sub’ operations on packet registers. Any other
operation will set the register state to ‘SCALAR_VALUE’ and it won’t be
available for direct packet access.</p>
<p>Operation <code class="docutils literal notranslate"><span class="pre">r3</span> <span class="pre">+=</span> <span class="pre">rX</span></code> may overflow and become less than original skb->data,
therefore the verifier has to prevent that. So when it sees <code class="docutils literal notranslate"><span class="pre">r3</span> <span class="pre">+=</span> <span class="pre">rX</span></code>
instruction and rX is more than 16-bit value, any subsequent bounds-check of r3
against skb->data_end will not give us ‘range’ information, so attempts to read
through the pointer will give “invalid access to packet” error.</p>
<p>Ex. after insn <code class="docutils literal notranslate"><span class="pre">r4</span> <span class="pre">=</span> <span class="pre">*(u8</span> <span class="pre">*)(r3</span> <span class="pre">+12)</span></code> (insn #7 above) the state of r4 is
R4=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) which means that upper 56 bits
of the register are guaranteed to be zero, and nothing is known about the lower
8 bits. After insn <code class="docutils literal notranslate"><span class="pre">r4</span> <span class="pre">*=</span> <span class="pre">14</span></code> the state becomes
R4=inv(id=0,umax_value=3570,var_off=(0x0; 0xfffe)), since multiplying an 8-bit
value by constant 14 will keep upper 52 bits as zero, also the least significant
bit will be zero as 14 is even. Similarly <code class="docutils literal notranslate"><span class="pre">r2</span> <span class="pre">>>=</span> <span class="pre">48</span></code> will make
R2=inv(id=0,umax_value=65535,var_off=(0x0; 0xffff)), since the shift is not sign
extending. This logic is implemented in <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">adjust_reg_min_max_vals()</span></code> function,
which calls <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">adjust_ptr_min_max_vals()</span></code> for adding pointer to scalar (or vice
versa) and <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">adjust_scalar_min_max_vals()</span></code> for operations on two scalars.</p>
<p>The end result is that bpf program author can access packet directly
using normal C code as:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>void *data = (void *)(long)skb->data;
void *data_end = (void *)(long)skb->data_end;
struct eth_hdr *eth = data;
struct iphdr *iph = data + sizeof(*eth);
struct udphdr *udp = data + sizeof(*eth) + sizeof(*iph);
if (data + sizeof(*eth) + sizeof(*iph) + sizeof(*udp) > data_end)
return 0;
if (eth->h_proto != htons(ETH_P_IP))
return 0;
if (iph->protocol != IPPROTO_UDP || iph->ihl != 5)
return 0;
if (udp->dest == 53 || udp->source == 9)
...;
</pre></div>
</div>
<p>which makes such programs easier to write comparing to LD_ABS insn
and significantly faster.</p>
</section>
<section id="pruning">
<h2>Pruning<a class="headerlink" href="#pruning" title="Link to this heading">¶</a></h2>
<p>The verifier does not actually walk all possible paths through the program. For
each new branch to analyse, the verifier looks at all the states it’s previously
been in when at this instruction. If any of them contain the current state as a
subset, the branch is ‘pruned’ - that is, the fact that the previous state was
accepted implies the current state would be as well. For instance, if in the
previous state, r1 held a packet-pointer, and in the current state, r1 holds a
packet-pointer with a range as long or longer and at least as strict an
alignment, then r1 is safe. Similarly, if r2 was NOT_INIT before then it can’t
have been used by any path from that point, so any value in r2 (including
another NOT_INIT) is safe. The implementation is in the function <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">regsafe()</span></code>.
Pruning considers not only the registers but also the stack (and any spilled
registers it may hold). They must all be safe for the branch to be pruned.
This is implemented in <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">states_equal()</span></code>.</p>
<p>Some technical details about state pruning implementation could be found below.</p>
<section id="register-liveness-tracking">
<h3>Register liveness tracking<a class="headerlink" href="#register-liveness-tracking" title="Link to this heading">¶</a></h3>
<p>In order to make state pruning effective, liveness state is tracked for each
register and stack slot. The basic idea is to track which registers and stack
slots are actually used during subseqeuent execution of the program, until
program exit is reached. Registers and stack slots that were never used could be
removed from the cached state thus making more states equivalent to a cached
state. This could be illustrated by the following program:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>0: call bpf_get_prandom_u32()
1: r1 = 0
2: if r0 == 0 goto +1
3: r0 = 1
--- checkpoint ---
4: r0 = r1
5: exit
</pre></div>
</div>
<p>Suppose that a state cache entry is created at instruction #4 (such entries are
also called “checkpoints” in the text below). The verifier could reach the
instruction with one of two possible register states:</p>
<ul class="simple">
<li><p>r0 = 1, r1 = 0</p></li>
<li><p>r0 = 0, r1 = 0</p></li>
</ul>
<p>However, only the value of register <code class="docutils literal notranslate"><span class="pre">r1</span></code> is important to successfully finish
verification. The goal of the liveness tracking algorithm is to spot this fact
and figure out that both states are actually equivalent.</p>
</section>
</section>
<section id="understanding-ebpf-verifier-messages">
<h2>Understanding eBPF verifier messages<a class="headerlink" href="#understanding-ebpf-verifier-messages" title="Link to this heading">¶</a></h2>
<p>The following are few examples of invalid eBPF programs and verifier error
messages as seen in the log:</p>
<p>Program with unreachable instructions:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>static struct bpf_insn prog[] = {
BPF_EXIT_INSN(),
BPF_EXIT_INSN(),
};
</pre></div>
</div>
<p>Error:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>unreachable insn 1
</pre></div>
</div>
<p>Program that reads uninitialized register:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>BPF_MOV64_REG(BPF_REG_0, BPF_REG_2),
BPF_EXIT_INSN(),
</pre></div>
</div>
<p>Error:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>0: (bf) r0 = r2
R2 !read_ok
</pre></div>
</div>
<p>Program that doesn’t initialize R0 before exiting:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>BPF_MOV64_REG(BPF_REG_2, BPF_REG_1),
BPF_EXIT_INSN(),
</pre></div>
</div>
<p>Error:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>0: (bf) r2 = r1
1: (95) exit
R0 !read_ok
</pre></div>
</div>
<p>Program that accesses stack out of bounds:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>BPF_ST_MEM(BPF_DW, BPF_REG_10, 8, 0),
BPF_EXIT_INSN(),
</pre></div>
</div>
<p>Error:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>0: (7a) *(u64 *)(r10 +8) = 0
invalid stack off=8 size=8
</pre></div>
</div>
<p>Program that doesn’t initialize stack before passing its address into function:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
BPF_LD_MAP_FD(BPF_REG_1, 0),
BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
BPF_EXIT_INSN(),
</pre></div>
</div>
<p>Error:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>0: (bf) r2 = r10
1: (07) r2 += -8
2: (b7) r1 = 0x0
3: (85) call 1
invalid indirect read from stack off -8+0 size 8
</pre></div>
</div>
<p>Program that uses invalid map_fd=0 while calling to <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">map_lookup_elem()</span></code> function:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
BPF_LD_MAP_FD(BPF_REG_1, 0),
BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
BPF_EXIT_INSN(),
</pre></div>
</div>
<p>Error:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>0: (7a) *(u64 *)(r10 -8) = 0
1: (bf) r2 = r10
2: (07) r2 += -8
3: (b7) r1 = 0x0
4: (85) call 1
fd 0 is not pointing to valid bpf_map
</pre></div>
</div>
<p>Program that doesn’t check return value of <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">map_lookup_elem()</span></code> before accessing
map element:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
BPF_LD_MAP_FD(BPF_REG_1, 0),
BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 0),
BPF_EXIT_INSN(),
</pre></div>
</div>
<p>Error:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>0: (7a) *(u64 *)(r10 -8) = 0
1: (bf) r2 = r10
2: (07) r2 += -8
3: (b7) r1 = 0x0
4: (85) call 1
5: (7a) *(u64 *)(r0 +0) = 0
R0 invalid mem access 'map_value_or_null'
</pre></div>
</div>
<p>Program that correctly checks <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">map_lookup_elem()</span></code> returned value for NULL, but
accesses the memory with incorrect alignment:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
BPF_LD_MAP_FD(BPF_REG_1, 0),
BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 1),
BPF_ST_MEM(BPF_DW, BPF_REG_0, 4, 0),
BPF_EXIT_INSN(),
</pre></div>
</div>
<p>Error:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>0: (7a) *(u64 *)(r10 -8) = 0
1: (bf) r2 = r10
2: (07) r2 += -8
3: (b7) r1 = 1
4: (85) call 1
5: (15) if r0 == 0x0 goto pc+1
R0=map_ptr R10=fp
6: (7a) *(u64 *)(r0 +4) = 0
misaligned access off 4 size 8
</pre></div>
</div>
<p>Program that correctly checks <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">map_lookup_elem()</span></code> returned value for NULL and
accesses memory with correct alignment in one side of ‘if’ branch, but fails
to do so in the other side of ‘if’ branch:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
BPF_LD_MAP_FD(BPF_REG_1, 0),
BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 2),
BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 0),
BPF_EXIT_INSN(),
BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 1),
BPF_EXIT_INSN(),
</pre></div>
</div>
<p>Error:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>0: (7a) *(u64 *)(r10 -8) = 0
1: (bf) r2 = r10
2: (07) r2 += -8
3: (b7) r1 = 1
4: (85) call 1
5: (15) if r0 == 0x0 goto pc+2
R0=map_ptr R10=fp
6: (7a) *(u64 *)(r0 +0) = 0
7: (95) exit
from 5 to 8: R0=imm0 R10=fp
8: (7a) *(u64 *)(r0 +0) = 1
R0 invalid mem access 'imm'
</pre></div>
</div>
<p>Program that performs a socket lookup then sets the pointer to NULL without
checking it:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>BPF_MOV64_IMM(BPF_REG_2, 0),
BPF_STX_MEM(BPF_W, BPF_REG_10, BPF_REG_2, -8),
BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
BPF_MOV64_IMM(BPF_REG_3, 4),
BPF_MOV64_IMM(BPF_REG_4, 0),
BPF_MOV64_IMM(BPF_REG_5, 0),
BPF_EMIT_CALL(BPF_FUNC_sk_lookup_tcp),
BPF_MOV64_IMM(BPF_REG_0, 0),
BPF_EXIT_INSN(),
</pre></div>
</div>
<p>Error:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>0: (b7) r2 = 0
1: (63) *(u32 *)(r10 -8) = r2
2: (bf) r2 = r10
3: (07) r2 += -8
4: (b7) r3 = 4
5: (b7) r4 = 0
6: (b7) r5 = 0
7: (85) call bpf_sk_lookup_tcp#65
8: (b7) r0 = 0
9: (95) exit
Unreleased reference id=1, alloc_insn=7
</pre></div>
</div>
<p>Program that performs a socket lookup but does not NULL-check the returned
value:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>BPF_MOV64_IMM(BPF_REG_2, 0),
BPF_STX_MEM(BPF_W, BPF_REG_10, BPF_REG_2, -8),
BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
BPF_MOV64_IMM(BPF_REG_3, 4),
BPF_MOV64_IMM(BPF_REG_4, 0),
BPF_MOV64_IMM(BPF_REG_5, 0),
BPF_EMIT_CALL(BPF_FUNC_sk_lookup_tcp),
BPF_EXIT_INSN(),
</pre></div>
</div>
<p>Error:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>0: (b7) r2 = 0
1: (63) *(u32 *)(r10 -8) = r2
2: (bf) r2 = r10
3: (07) r2 += -8
4: (b7) r3 = 4
5: (b7) r4 = 0
6: (b7) r5 = 0
7: (85) call bpf_sk_lookup_tcp#65
8: (95) exit
Unreleased reference id=1, alloc_insn=7
</pre></div>
</div>
</section>
</section>
</div>
</div>
</div>
<div class="clearer"></div>
</div>
<div class="footer">
©The kernel development community.
|
Powered by <a href="https://www.sphinx-doc.org/">Sphinx 8.1.3</a>
& <a href="https://alabaster.readthedocs.io">Alabaster 0.7.16</a>
|
<a href="../_sources/bpf/verifier.rst.txt"
rel="nofollow">Page source</a>
</div>
</body>
</html>