341 lines · plain
1.. SPDX-License-Identifier: GPL-2.02.. Copyright (C) 2020, Google LLC.3 4Kernel Electric-Fence (KFENCE)5==============================6 7Kernel Electric-Fence (KFENCE) is a low-overhead sampling-based memory safety8error detector. KFENCE detects heap out-of-bounds access, use-after-free, and9invalid-free errors.10 11KFENCE is designed to be enabled in production kernels, and has near zero12performance overhead. Compared to KASAN, KFENCE trades performance for13precision. The main motivation behind KFENCE's design, is that with enough14total uptime KFENCE will detect bugs in code paths not typically exercised by15non-production test workloads. One way to quickly achieve a large enough total16uptime is when the tool is deployed across a large fleet of machines.17 18Usage19-----20 21To enable KFENCE, configure the kernel with::22 23 CONFIG_KFENCE=y24 25To build a kernel with KFENCE support, but disabled by default (to enable, set26``kfence.sample_interval`` to non-zero value), configure the kernel with::27 28 CONFIG_KFENCE=y29 CONFIG_KFENCE_SAMPLE_INTERVAL=030 31KFENCE provides several other configuration options to customize behaviour (see32the respective help text in ``lib/Kconfig.kfence`` for more info).33 34Tuning performance35~~~~~~~~~~~~~~~~~~36 37The most important parameter is KFENCE's sample interval, which can be set via38the kernel boot parameter ``kfence.sample_interval`` in milliseconds. The39sample interval determines the frequency with which heap allocations will be40guarded by KFENCE. The default is configurable via the Kconfig option41``CONFIG_KFENCE_SAMPLE_INTERVAL``. Setting ``kfence.sample_interval=0``42disables KFENCE.43 44The sample interval controls a timer that sets up KFENCE allocations. By45default, to keep the real sample interval predictable, the normal timer also46causes CPU wake-ups when the system is completely idle. This may be undesirable47on power-constrained systems. The boot parameter ``kfence.deferrable=1``48instead switches to a "deferrable" timer which does not force CPU wake-ups on49idle systems, at the risk of unpredictable sample intervals. The default is50configurable via the Kconfig option ``CONFIG_KFENCE_DEFERRABLE``.51 52.. warning::53 The KUnit test suite is very likely to fail when using a deferrable timer54 since it currently causes very unpredictable sample intervals.55 56By default KFENCE will only sample 1 heap allocation within each sample57interval. *Burst mode* allows to sample successive heap allocations, where the58kernel boot parameter ``kfence.burst`` can be set to a non-zero value which59denotes the *additional* successive allocations within a sample interval;60setting ``kfence.burst=N`` means that ``1 + N`` successive allocations are61attempted through KFENCE for each sample interval.62 63The KFENCE memory pool is of fixed size, and if the pool is exhausted, no64further KFENCE allocations occur. With ``CONFIG_KFENCE_NUM_OBJECTS`` (default65255), the number of available guarded objects can be controlled. Each object66requires 2 pages, one for the object itself and the other one used as a guard67page; object pages are interleaved with guard pages, and every object page is68therefore surrounded by two guard pages.69 70The total memory dedicated to the KFENCE memory pool can be computed as::71 72 ( #objects + 1 ) * 2 * PAGE_SIZE73 74Using the default config, and assuming a page size of 4 KiB, results in75dedicating 2 MiB to the KFENCE memory pool.76 77Note: On architectures that support huge pages, KFENCE will ensure that the78pool is using pages of size ``PAGE_SIZE``. This will result in additional page79tables being allocated.80 81Error reports82~~~~~~~~~~~~~83 84A typical out-of-bounds access looks like this::85 86 ==================================================================87 BUG: KFENCE: out-of-bounds read in test_out_of_bounds_read+0xa6/0x23488 89 Out-of-bounds read at 0xffff8c3f2e291fff (1B left of kfence-#72):90 test_out_of_bounds_read+0xa6/0x23491 kunit_try_run_case+0x61/0xa092 kunit_generic_run_threadfn_adapter+0x16/0x3093 kthread+0x176/0x1b094 ret_from_fork+0x22/0x3095 96 kfence-#72: 0xffff8c3f2e292000-0xffff8c3f2e29201f, size=32, cache=kmalloc-3297 98 allocated by task 484 on cpu 0 at 32.919330s:99 test_alloc+0xfe/0x738100 test_out_of_bounds_read+0x9b/0x234101 kunit_try_run_case+0x61/0xa0102 kunit_generic_run_threadfn_adapter+0x16/0x30103 kthread+0x176/0x1b0104 ret_from_fork+0x22/0x30105 106 CPU: 0 PID: 484 Comm: kunit_try_catch Not tainted 5.13.0-rc3+ #7107 Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.14.0-2 04/01/2014108 ==================================================================109 110The header of the report provides a short summary of the function involved in111the access. It is followed by more detailed information about the access and112its origin. Note that, real kernel addresses are only shown when using the113kernel command line option ``no_hash_pointers``.114 115Use-after-free accesses are reported as::116 117 ==================================================================118 BUG: KFENCE: use-after-free read in test_use_after_free_read+0xb3/0x143119 120 Use-after-free read at 0xffff8c3f2e2a0000 (in kfence-#79):121 test_use_after_free_read+0xb3/0x143122 kunit_try_run_case+0x61/0xa0123 kunit_generic_run_threadfn_adapter+0x16/0x30124 kthread+0x176/0x1b0125 ret_from_fork+0x22/0x30126 127 kfence-#79: 0xffff8c3f2e2a0000-0xffff8c3f2e2a001f, size=32, cache=kmalloc-32128 129 allocated by task 488 on cpu 2 at 33.871326s:130 test_alloc+0xfe/0x738131 test_use_after_free_read+0x76/0x143132 kunit_try_run_case+0x61/0xa0133 kunit_generic_run_threadfn_adapter+0x16/0x30134 kthread+0x176/0x1b0135 ret_from_fork+0x22/0x30136 137 freed by task 488 on cpu 2 at 33.871358s:138 test_use_after_free_read+0xa8/0x143139 kunit_try_run_case+0x61/0xa0140 kunit_generic_run_threadfn_adapter+0x16/0x30141 kthread+0x176/0x1b0142 ret_from_fork+0x22/0x30143 144 CPU: 2 PID: 488 Comm: kunit_try_catch Tainted: G B 5.13.0-rc3+ #7145 Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.14.0-2 04/01/2014146 ==================================================================147 148KFENCE also reports on invalid frees, such as double-frees::149 150 ==================================================================151 BUG: KFENCE: invalid free in test_double_free+0xdc/0x171152 153 Invalid free of 0xffff8c3f2e2a4000 (in kfence-#81):154 test_double_free+0xdc/0x171155 kunit_try_run_case+0x61/0xa0156 kunit_generic_run_threadfn_adapter+0x16/0x30157 kthread+0x176/0x1b0158 ret_from_fork+0x22/0x30159 160 kfence-#81: 0xffff8c3f2e2a4000-0xffff8c3f2e2a401f, size=32, cache=kmalloc-32161 162 allocated by task 490 on cpu 1 at 34.175321s:163 test_alloc+0xfe/0x738164 test_double_free+0x76/0x171165 kunit_try_run_case+0x61/0xa0166 kunit_generic_run_threadfn_adapter+0x16/0x30167 kthread+0x176/0x1b0168 ret_from_fork+0x22/0x30169 170 freed by task 490 on cpu 1 at 34.175348s:171 test_double_free+0xa8/0x171172 kunit_try_run_case+0x61/0xa0173 kunit_generic_run_threadfn_adapter+0x16/0x30174 kthread+0x176/0x1b0175 ret_from_fork+0x22/0x30176 177 CPU: 1 PID: 490 Comm: kunit_try_catch Tainted: G B 5.13.0-rc3+ #7178 Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.14.0-2 04/01/2014179 ==================================================================180 181KFENCE also uses pattern-based redzones on the other side of an object's guard182page, to detect out-of-bounds writes on the unprotected side of the object.183These are reported on frees::184 185 ==================================================================186 BUG: KFENCE: memory corruption in test_kmalloc_aligned_oob_write+0xef/0x184187 188 Corrupted memory at 0xffff8c3f2e33aff9 [ 0xac . . . . . . ] (in kfence-#156):189 test_kmalloc_aligned_oob_write+0xef/0x184190 kunit_try_run_case+0x61/0xa0191 kunit_generic_run_threadfn_adapter+0x16/0x30192 kthread+0x176/0x1b0193 ret_from_fork+0x22/0x30194 195 kfence-#156: 0xffff8c3f2e33afb0-0xffff8c3f2e33aff8, size=73, cache=kmalloc-96196 197 allocated by task 502 on cpu 7 at 42.159302s:198 test_alloc+0xfe/0x738199 test_kmalloc_aligned_oob_write+0x57/0x184200 kunit_try_run_case+0x61/0xa0201 kunit_generic_run_threadfn_adapter+0x16/0x30202 kthread+0x176/0x1b0203 ret_from_fork+0x22/0x30204 205 CPU: 7 PID: 502 Comm: kunit_try_catch Tainted: G B 5.13.0-rc3+ #7206 Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.14.0-2 04/01/2014207 ==================================================================208 209For such errors, the address where the corruption occurred as well as the210invalidly written bytes (offset from the address) are shown; in this211representation, '.' denote untouched bytes. In the example above ``0xac`` is212the value written to the invalid address at offset 0, and the remaining '.'213denote that no following bytes have been touched. Note that, real values are214only shown if the kernel was booted with ``no_hash_pointers``; to avoid215information disclosure otherwise, '!' is used instead to denote invalidly216written bytes.217 218And finally, KFENCE may also report on invalid accesses to any protected page219where it was not possible to determine an associated object, e.g. if adjacent220object pages had not yet been allocated::221 222 ==================================================================223 BUG: KFENCE: invalid read in test_invalid_access+0x26/0xe0224 225 Invalid read at 0xffffffffb670b00a:226 test_invalid_access+0x26/0xe0227 kunit_try_run_case+0x51/0x85228 kunit_generic_run_threadfn_adapter+0x16/0x30229 kthread+0x137/0x160230 ret_from_fork+0x22/0x30231 232 CPU: 4 PID: 124 Comm: kunit_try_catch Tainted: G W 5.8.0-rc6+ #7233 Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.13.0-1 04/01/2014234 ==================================================================235 236DebugFS interface237~~~~~~~~~~~~~~~~~238 239Some debugging information is exposed via debugfs:240 241* The file ``/sys/kernel/debug/kfence/stats`` provides runtime statistics.242 243* The file ``/sys/kernel/debug/kfence/objects`` provides a list of objects244 allocated via KFENCE, including those already freed but protected.245 246Implementation Details247----------------------248 249Guarded allocations are set up based on the sample interval. After expiration250of the sample interval, the next allocation through the main allocator (SLAB or251SLUB) returns a guarded allocation from the KFENCE object pool (allocation252sizes up to PAGE_SIZE are supported). At this point, the timer is reset, and253the next allocation is set up after the expiration of the interval.254 255When using ``CONFIG_KFENCE_STATIC_KEYS=y``, KFENCE allocations are "gated"256through the main allocator's fast-path by relying on static branches via the257static keys infrastructure. The static branch is toggled to redirect the258allocation to KFENCE. Depending on sample interval, target workloads, and259system architecture, this may perform better than the simple dynamic branch.260Careful benchmarking is recommended.261 262KFENCE objects each reside on a dedicated page, at either the left or right263page boundaries selected at random. The pages to the left and right of the264object page are "guard pages", whose attributes are changed to a protected265state, and cause page faults on any attempted access. Such page faults are then266intercepted by KFENCE, which handles the fault gracefully by reporting an267out-of-bounds access, and marking the page as accessible so that the faulting268code can (wrongly) continue executing (set ``panic_on_warn`` to panic instead).269 270To detect out-of-bounds writes to memory within the object's page itself,271KFENCE also uses pattern-based redzones. For each object page, a redzone is set272up for all non-object memory. For typical alignments, the redzone is only273required on the unguarded side of an object. Because KFENCE must honor the274cache's requested alignment, special alignments may result in unprotected gaps275on either side of an object, all of which are redzoned.276 277The following figure illustrates the page layout::278 279 ---+-----------+-----------+-----------+-----------+-----------+---280 | xxxxxxxxx | O : | xxxxxxxxx | : O | xxxxxxxxx |281 | xxxxxxxxx | B : | xxxxxxxxx | : B | xxxxxxxxx |282 | x GUARD x | J : RED- | x GUARD x | RED- : J | x GUARD x |283 | xxxxxxxxx | E : ZONE | xxxxxxxxx | ZONE : E | xxxxxxxxx |284 | xxxxxxxxx | C : | xxxxxxxxx | : C | xxxxxxxxx |285 | xxxxxxxxx | T : | xxxxxxxxx | : T | xxxxxxxxx |286 ---+-----------+-----------+-----------+-----------+-----------+---287 288Upon deallocation of a KFENCE object, the object's page is again protected and289the object is marked as freed. Any further access to the object causes a fault290and KFENCE reports a use-after-free access. Freed objects are inserted at the291tail of KFENCE's freelist, so that the least recently freed objects are reused292first, and the chances of detecting use-after-frees of recently freed objects293is increased.294 295If pool utilization reaches 75% (default) or above, to reduce the risk of the296pool eventually being fully occupied by allocated objects yet ensure diverse297coverage of allocations, KFENCE limits currently covered allocations of the298same source from further filling up the pool. The "source" of an allocation is299based on its partial allocation stack trace. A side-effect is that this also300limits frequent long-lived allocations (e.g. pagecache) of the same source301filling up the pool permanently, which is the most common risk for the pool302becoming full and the sampled allocation rate dropping to zero. The threshold303at which to start limiting currently covered allocations can be configured via304the boot parameter ``kfence.skip_covered_thresh`` (pool usage%).305 306Interface307---------308 309The following describes the functions which are used by allocators as well as310page handling code to set up and deal with KFENCE allocations.311 312.. kernel-doc:: include/linux/kfence.h313 :functions: is_kfence_address314 kfence_shutdown_cache315 kfence_alloc kfence_free __kfence_free316 kfence_ksize kfence_object_start317 kfence_handle_page_fault318 319Related Tools320-------------321 322In userspace, a similar approach is taken by `GWP-ASan323<http://llvm.org/docs/GwpAsan.html>`_. GWP-ASan also relies on guard pages and324a sampling strategy to detect memory unsafety bugs at scale. KFENCE's design is325directly influenced by GWP-ASan, and can be seen as its kernel sibling. Another326similar but non-sampling approach, that also inspired the name "KFENCE", can be327found in the userspace `Electric Fence Malloc Debugger328<https://linux.die.net/man/3/efence>`_.329 330In the kernel, several tools exist to debug memory access errors, and in331particular KASAN can detect all bug classes that KFENCE can detect. While KASAN332is more precise, relying on compiler instrumentation, this comes at a333performance cost.334 335It is worth highlighting that KASAN and KFENCE are complementary, with336different target environments. For instance, KASAN is the better debugging-aid,337where test cases or reproducers exists: due to the lower chance to detect the338error, it would require more effort using KFENCE to debug. Deployments at scale339that cannot afford to enable KASAN, however, would benefit from using KFENCE to340discover bugs due to code paths not exercised by test cases or fuzzers.341