Introduction

KernelToolchain

PaX - kernel self-protection
PaX Team

H2HC 2012.10.09

PaX - kernel self-protection

FutureIntroduction

Introduction
Design concepts
KernelToolchain
Future

PaX - kernel self-protection

KernelToolchain

FutureIntroduction

KernelToolchain

Design concepts

Overview
I Host Intrusion Prevention System
I Focus: exploit techniques against memory corruption bugs
I Threat model: arbitrary read-write memory access
I Bugs vs. Exploits vs. Exploit techniques
I Performance vs. Usability
I 2000-2012, linux 2.2-3.6

PaX - kernel self-protection

FutureIntroduction

KernelToolchain

Design concepts

Bugs
I Buffer overflows (stack/heap/static data)
I Heap object mismanagement (double free, use-after-free, etc)
I Integer overflows (underallocation, buffer overflow, reference

counts, etc)
I see http://cwe.mitre.org/
I Known/unknown (0-day)
I None of this matters :)PaX - kernel self-protection

FutureIntroduction

KernelToolchain

Design concepts

Exploit Techniques

I Execute new (injected) code (shellcode)
I Execute existing code out-of-(intended)-order (return-to-libc,

ROP/JOP)
I Execute existing code in-(intended)-order (data-only attacks)
I Increasing order of difficulty
I Decreasing amount of control

PaX - kernel self-protection

FutureIntroduction

KernelToolchain

Introduction
KernelNon-executable pages (KERNEXEC)
Userland/kernel separation (UDEREF)
Userland/kernel copying(USERCOPY/STACKLEAK/SANITIZE)
Reference counter overflows (REFCOUNT)
Toolchain
Future
PaX - kernel self-protection

FutureIntroduction

KernelToolchainNon-executable pages (KERNEXEC)

Overview
I Implements non-executable page behaviour (where there is no

direct hardware support)
I Makes data pages non-executable (anything but kernel andmodule code)
I Makes read-only data actually read-only in the page tables
I Makes some important kernel data read-only (IDT, GDT,

some page tables, CONSTIFY, __read_only, etc)
I i386: segmentation
I amd64: NX bit (except very early Intel P4 Xeon CPUs)

PaX - kernel self-protection

FutureIntroduction

KernelToolchainNon-executable pages (KERNEXEC)KERNEXEC/i386 Overview
I Idea: have __KERNEL_CS cover only kernel code
I base: __PAGE_OFFSET+__LOAD_PHYSICAL_ADDR
I limit: 4GB during init, _etext after free_initmem
I Excludes userland for free (unlike on amd64, but there is

SMEP to the rescue :)I Special problems: logical/linear translations, relocations,modules and .init code

PaX - kernel self-protection

FutureIntroduction

KernelToolchainNon-executable pages (KERNEXEC)KERNEXEC/i386 Problems
I Problem: kernel assumes logical address == linear address,

no longer true for code (function pointers)
I Needs translation (ktla_ktva and ktva_ktla) for:I runtime patching and probing (alternatives, backtrace, ftrace,

kprobes, lockdep, perf, etc)
I module loading (relocation)
I Relocatable kernel does no longer need relocations for code

PaX - kernel self-protection

FutureIntroduction

KernelToolchainNon-executable pages (KERNEXEC)KERNEXEC/i386 Module handling
I Module code must be allocated within __KERNEL_CS
I Module data is a separate allocation
I Module read-only data is allocated with the code
I Preallocated area in vmlinux at compile/link time, size isconfigurable
I Fragmentation can be a problem
I Consumes (reserves) physical memory in the direct mapping

even when no modules are loaded
I Module loader allocates code and data separately, special

allocator for code under KERNEXEC/i386
PaX - kernel self-protection

FutureIntroduction

KernelToolchainNon-executable pages (KERNEXEC)KERNEXEC/i386 Initialization code handling

I Kernel initialization code is discarded at runtime
I Still must be within __KERNEL_CS during init
I Placed along with the other init code/data
I Its memory is freed/reused

PaX - kernel self-protection

FutureIntroduction

KernelToolchainNon-executable pages (KERNEXEC)KERNEXEC/amd64 Overview
I Idea: remove rwx mappings from the kernel virtual addressrange
I Establishes more control over kernel page tables (per-cpu pgd)
I kmaps: tool for auditing a page table hierarchy
I More details than CONFIG_X86_PTDUMPI Special problems: modules, vsyscall, BIOS/ACPI (ioremap)
I Does not prevent userland code execution per se
I KERNEXEC gcc plugin
I CR4.SMEP

PaX - kernel self-protection

FutureIntroduction

KernelToolchainNon-executable pages (KERNEXEC)KERNEXEC/amd64 Problems
I Module problem: one contiguous rwx allocation (before thedays of CONFIG_DEBUG_SET_MODULE_RONX)
I Reuses KERNEXEC/i386 module loader logic (was already ingeneric kernel code anyway)
I Module code/rodata vs. data
I vsyscall problem: page mapped twice (rw-, r-x), abused by

an exploit for CVE-2009-0065
I ioremap problem: too easy access to physical memory
I No access allowed above 1MB
I No more sensitive data in the first 1MB

PaX - kernel self-protection

FutureIntroduction

KernelToolchain

Userland/kernel separation (UDEREF)

Overview
I Prevents unintended userland accesses from the kernel
I Intended accesses via explicit accessors only: *copy*user*,*{get,put}_user
I NULL pointer dereferences
I ’magic’ poison value dereferences
I AMD catalyst bug
I i386: segmentation
I amd64: paging
I Haswell and CR4.SMAP, see our blog

PaX - kernel self-protection

FutureIntroduction

KernelToolchain

Userland/kernel separation (UDEREF)

UDEREF/i386
I Expand down kernel data segment (__KERNEL_DS) preventsuserland access
I Intended accesses use segment override prefix (gs) with__USER_DS
I Segment prefix collides with stack smashing protector (SSP)
I Default userland code/data segments prevent kernel access
I TLS/LDT still have to be allowed, kernel doesn’t use them
I kernel-to-kernel copying (set_fs)
I Used to patch __USER_DS to change its limit
I Nowadays switches gs between 0, __USER_DS or __KERNEL_DS

PaX - kernel self-protection

FutureIntroduction

KernelToolchain

Userland/kernel separation (UDEREF)

UDEREF/amd64
I Idea: unmap userland while executing in the kernel
I Remaps it elsewhere (shadow) as non-executable(KERNEXEC)I Obvious performance impact, thanks to AMD for killingsegmentation
I Requires per-cpu top-level page directory (pgd) for

SMP/multi-threaded apps
I Performance optimizations
I Context switch copies a few pgd entries only, one cacheline’s

worth
I No TLB flush on kernel->userland transitions
PaX - kernel self-protection

FutureIntroduction

KernelToolchain

Userland/kernel separation (UDEREF)

per-cpu pgd concept
I Idea: instead of a single per-process pgd have one per-cpu
I Allows local (per-cpu) changes to the process memory map
I swapper_pg_dir (init_level4_pgt on amd64) is kept as

master pgd for the kernel
I cpu_pgd[NR_CPUS][PTRS_PER_PGD] array
I Invariant:

cr3 on cpuN must always point to cpu_pgd[N]I Reduces number of userland pgd entries (256 vs. 8 on

amd64), reduces ASLR (5 bits less)I 8 entries occupy one cache line
I Future optimization: per-process pgd can be reduced to theuserland pgd entries only
PaX - kernel self-protection

FutureIntroduction

KernelToolchain

Userland/kernel separation (UDEREF)

per-cpu pgd management
I When allocating the per-process pgd:
I pud tables (8 of them on amd64) are allocated as well
I They are never freed while the process is alive
I The per-process pgd does not have the kernel pgd entries
I Prevents its accidental use in cr3
I switch_mm: calls __clone_user_pgds and__shadow_user_pgds
I clone: sets up the normal userland pgd entries in cpu_pgd[N]I shadow: sets up the shadow userland mapping in cpu_pgd[N]PaX - kernel self-protection

FutureIntroduction

KernelToolchain

Userland/kernel copying (USERCOPY/STACKLEAK/SANITIZE)

Overview
I Bounds checking for copying from kernel memory to userland(info leak) or vice versa (buffer overflow)
I spender’s idea: ksize can determine the object’s size fromthe object’s address
I Originally heap (slab) buffers only
I Limited stack buffer support (see Future section)
I Disables SLUB merging
I Data lifetime reduction: STACKLEAK and SANITIZE
I Process kernel stack clearing (STACKLEAK)
I Enhanced with a gcc plugin
I Freed page clearing in the low level page allocator (SANITIZE)
PaX - kernel self-protection

FutureIntroduction

KernelToolchain

Userland/kernel copying (USERCOPY/STACKLEAK/SANITIZE)USERCOPY
I Instruments copy*user functions to callcheck_object_size when size is not a compile-time constantI check_object_size is implemented for SLAB/SLUB/SLOB
I Only slabs marked with the SLAB_USERCOPY flag are letthrough
I cifs_request, cifs_small_rq, jfs_ip, kvm_vcpu,

names_cache, task_xstate
I All kmalloc-* slabs (for now)I Some kernel code is patched to reduce flag proliferation
I Limited stack buffer checking (object_is_on_stack)I Current function frame under CONFIG_FRAME_POINTERI Current kernel stack without CONFIG_FRAME_POINTER
PaX - kernel self-protection

FutureIntroduction

KernelToolchain

Userland/kernel copying (USERCOPY/STACKLEAK/SANITIZE)

STACKLEAK
I Idea: reduce lifetime of data on process kernel stacks byclearing the stack on kernel->user transitions
I Per-arch hooks in the low-level kernel entry/exit code
I Moved thread_info off the stack
I Initially blind memset on the entire kernel stack (8 kbytes)
I Too slow (unused part of the stack is cache cold)
I Refinement: detect/clear only the used part of the stack
I Looks for memset pattern from stack bottom to top
I Optimization: check only a certain length (cache line)
I Needs to record stack depth in functions with a big stackframe
I Manual inspection and patching
I Instrumentation by a gcc plugin
PaX - kernel self-protection

FutureIntroduction

KernelToolchain

Userland/kernel copying (USERCOPY/STACKLEAK/SANITIZE)

STACKLEAK
I Special paths for ptrace/auditing
I Low-level kernel entry/exit paths can diverge forptrace/auditing and leave interesting information on the stack
for the actual syscall code
I Problems: still considerable overhead, races, leaks from asingle syscall still possible
I Solution: dual process kernel stack, one used only for copying

to/from userland
I Needs static analysis to find all local variables whose address issunk into copy*user
I New gcc plugin, LTO
PaX - kernel self-protection

FutureIntroduction

KernelToolchain

Userland/kernel copying (USERCOPY/STACKLEAK/SANITIZE)SANITIZEI Reduces potential info leaks from kernel memory to userland
I Freed memory is cleared immediately infree_pages_prepare
I Optimization: prep_new_page does not need to handle__GFP_ZERO
I Low-level page allocator, not slab layer
I Works on whole pages, not individual heap objects
I Kernel stacks on task death
I Anonymous userland mappings on munmap
I Anti-forensics vs. privacy
PaX - kernel self-protection

FutureIntroduction

KernelToolchain

Reference counter overflows (REFCOUNT)

Overview
I Detects reference counter overflows
I Idea: detect signed overflow (in the middle of the counter

space, INT_MAX+1)
I Linux refcounts are based on atomic_t and atomic64_t
I Per-arch assembly accessors, access to CPU flags
I False positives: not all variables of these types are refcounts(statistics, unique ids, bitflags)
I Manual auditing, should be automated (gcc plugin)I armv6+/sparc64/x86, soon powerpc

PaX - kernel self-protection

FutureIntroduction

KernelToolchain

Introduction
KernelToolchain
GCC plugins
Kernel stack information leak reduction (STACKLEAK)
Read-only function pointers (CONSTIFY)
KERNEXEC/amd64 helper plugin
Integer (size) overflows (SIZE_OVERFLOW)
Latent Entropy Extraction (LATENT_ENTROPY)
Future
PaX - kernel self-protection

FutureIntroduction

KernelToolchain

GCC plugins

Overview
I Idea: add special instrumentation during compilation to

detect/prevent entire bug classes at runtime
I Loadable module system introduced in gcc 4.5
I Loaded early right after command line parsing
I No well defined API, all public symbols available for plugin use
I Typical (intended :) use: new IPA/GIMPLE/RTL passes
I Plugins can sign up for events, insert/remove/replace passes
I No (easy) access to language frontends

PaX - kernel self-protection

FutureIntroduction

KernelToolchain

GCC plugins

Introduction to gcc
I Compilation process is a pipeline, driven by the compiler driver
I Language frontend parses the source code and produces

GENERIC/GIMPLE
I Plugins can implement new attributes and pragmas, inspect

structure declarations and variable definitions (gcc 4.6+)
I Static Single Assignment (SSA) based representation
I First set of optimization/transformation passes runs on

GIMPLE (-fdump-ipa-all, -fdump-tree-all)
I Data structures: gimple, tree
I GIMPLE is lowered to RTL (pre-SSA gcc had only this)
I Second set of optimization passes runs on RTL(-fdump-rtl-all)
I Data structures: rtx, tree
PaX - kernel self-protection

FutureIntroduction

KernelToolchain

Kernel stack information leak reduction (STACKLEAK)

Overview
I First plugin :)I Idea: insert function call to pax_track_stack if local frame

size is over a specific limit
I pax_track_stack records deepest used kernel stack pointer
I Problem: frame size info is available at the last RTL pass

only, too late to insert complex code like a function call
I New strategy: instrument every function first and remove

unneeded instrumentation later
I Also finds all (potentially exploitable :) alloca calls

PaX - kernel self-protection

FutureIntroduction

KernelToolchain

Kernel stack information leak reduction (STACKLEAK)

STACKLEAK
I GIMPLE pass: inserts call to pax_track_stack into every

function prologue
I unless alloca is in the first basic block
I alloca is bracketed with a call to pax_check_alloca and

pax_track_stack
I RTL pass: removes unneeded pax_track_stack calls
I if the local frame size is below the limit
I if alloca is not used

PaX - kernel self-protection

FutureIntroduction

KernelToolchain

Read-only function pointers (CONSTIFY)

Overview
I Automatic constification of ops structures (200+ types inlinux)I Structures with function pointer members only
I Structures explicitly marked with a do_const attribute
I no_const attribute for special cases
I Unfortunately many ops structures want to be written atruntime
I Local variables not allowed (compiler error generated)

PaX - kernel self-protection

FutureIntroduction

KernelToolchain

Read-only function pointers (CONSTIFY)CONSTIFYI PLUGIN_ATTRIBUTES callback: registers do_const andno_const attributes
I Linux code patched by hand
I Could be automated (static analysis, LTO)I PLUGIN_FINISH_TYPE callback: sets TYPE_READONLY and

C_TYPE_FIELDS_READONLY on eligible structure types
I Only function pointer members, recursively
I do_const is set, no_const is not set
I End result is that the frontend will do the dirty job ofenforcing C variable constness
I GIMPLE pass: constified types cannot be used for local

variables (stack is writable :)PaX - kernel self-protection

FutureIntroduction

KernelToolchain

KERNEXEC/amd64 helper plugin

Overview
I Goal: prevent executing userland code on amd64
I Idea: set most significant bit in all function pointers
I Userland addresses become non-canonical ones, GPF on any

dereference
I GIMPLE pass: handles C function pointers(execute_kernexec_fptr)
I RTL pass: handles function return values(execute_kernexec_retaddr)

PaX - kernel self-protection

FutureIntroduction

KernelToolchain

KERNEXEC/amd64 helper plugin

KERNEXEC/amd64 helper plugin

I Two methods: bts vs. or (reserves %r10 for bitmask)
I Compatibility vs. performance
I Special cases: vsyscall, assembly source, asm()
I kernexec_cmodel_check to exclude code in vsyscall sections
I Manual verification/patching
I GIMPLE pass to reload r10 when clobbered by asm()

PaX - kernel self-protection

FutureIntroduction

KernelToolchain

Integer (size) overflows (SIZE_OVERFLOW)

Overview
I Detects integer overflows in expressions used as a size

parameter: kmalloc(count * sizeof...)
I Written by Emese Révfy, extends spender’s old idea

(preprocessor trick)
I Initial set of functions/parameters marked by thesize_overflow function attribute
I Walks use-def chains and duplicates statements using adouble-wide integer type
I SImode/DImode vs. DImode/TImodeI Special cases: asm(), function return values, constants(intentional overflows), memory references, type casts, etc
I More in our blog
PaX - kernel self-protection

FutureIntroduction

KernelToolchain

Integer (size) overflows (SIZE_OVERFLOW)SIZE_OVERFLOWI PLUGIN_ATTRIBUTES callback: size_overflow attribute,takes arbitrary arguments (size parameter index)
I Only a handful of functions are marked by hand
I Hash table lookup for the rest (could be automated with LTO)
I GIMPLE pass: handle_function enumerates all function

calls looking for the size_overflow attribute (or hash table)
I handle_function_arg starts the real work
I Manually walks the use-def chain of the given function

argument
I Walk forks on binary/ternary operations and phi nodes
I Walk stops at asm/call stmts, function parameters, globals,

memory references, constants, etc
PaX - kernel self-protection

FutureIntroduction

KernelToolchain

Integer (size) overflows (SIZE_OVERFLOW)SIZE_OVERFLOW
I When a walk stops, stmt duplication begins
I New variable is created with signed_size_overflow_type
I DImode or TImode (signed)
I When stmt duplication reaches the original function call, theduplicated result is bounds checked
I Against TYPE_MAX_VALUE/TYPE_MIN_VALUE
I Optimization: check omitted if the walk did not find any stmt

that could cause an overflow

PaX - kernel self-protection

FutureIntroduction

KernelToolchain

Latent Entropy Extraction (LATENT_ENTROPY)

Overview

I Goal: extract entropy from kernel state during bootI Inspired by https://factorable.net/
I USENIX Security Symposium, August 2012
I Problem: much less entropy after boot than needed
I Result: vulnerable RSA and DSA keys used for SSH/TLS
I Some fixes in Linux but can we do better?

PaX - kernel self-protection

FutureIntroduction

KernelToolchain

Latent Entropy Extraction (LATENT_ENTROPY)LATENT_ENTROPY
I Idea: compute a hash-like function embedded in the control

flow graph of kernel boot code
I Similar and also simpler approach already in Phrack 66
I Insert a random combination of ADD/XOR/ROL insns into

every basic block
I Mix end state into a global variable in the function epilogues
I Feed global variable (entropy) into the kernel entropy pools

after each initcall
I Entropy is not actually accounted for until someone

cryptanalyzes this whole thing :)I More info on our mailing list
PaX - kernel self-protection

FutureIntroduction

KernelFuture
LLVM/Clang
Link-Time Optimization (LTO)
Control flow enforcement (CFE)
Data flow enforcement (KERNSEAL)
Miscellaneous

PaX - kernel self-protection

Toolchain

FutureIntroduction

KernelToolchain

LLVM/Clang

Overview
I http://llvm.org and http://clang.llvm.org
I Mostly works with linux-side patches only
I clang 3.1 and -integrated-as, .code16gcc/.code16
I -fcatch-undefined-behavior (ext4 triggers it on mount)
I LTO
I Port the gcc plugins to llvm
I New plugins for clang (not really feasible with gcc)

PaX - kernel self-protection

FutureIntroduction

KernelToolchain

Link-Time Optimization (LTO)

Overview
I Idea: run optimization passes on one big translation unit

combined from all source files
I Allows whole program analysis
I Mostly works with gcc 4.7
I Takes 5 minutes and 4GB RAM on a quad-core Sandy Bridge
I Problems: KALLSYMS, tracing, initcalls, section attributes
I Better support for other plugins (CONSTIFY, REFCOUNT,SIZE_OVERFLOW, STACKLEAK, USERCOPY)I New plugins: static stack overflow checking, sparse attributes,

etc
PaX - kernel self-protection

FutureIntroduction

KernelToolchain

Link-Time Optimization (LTO)

LTO plans
I CONSTIFY: find all non-constifiable types/variables
I REFCOUNT: find all non-refcount atomic_t/atomic64_t

uses
I SIZE_OVERFLOW: walk use-def chains across function calls,

eliminate the hash table
I STACKLEAK: find all local variables whose address sinks into

copy*user
I USERCOPY: find all kmalloc-* slab allocations that sink

into copy*user

PaX - kernel self-protection

FutureIntroduction

KernelToolchainControl flow enforcement (CFE)

Overview
I Against the “execute existing code out-of-(intended)-order”

exploit technique
I Compiler plugin to instrument all function pointer dereferences
I (No) support for binary-only modules
I Assembly source: manual instrumentation
I Runtime code generation (JIT compiler engines) support
I Performance impact is critical (<5% desired), very hard

problem

PaX - kernel self-protection

FutureIntroduction

KernelToolchain

Data flow enforcement (KERNSEAL)

Overview
I Against the “execute existing code in-(intended)-order”

technique
I Ensures that certain kernel data cannot be modified

unintentionally (arbitrary write bug)
I Credential structures, memory management data, filesystem

metadata/data (page cache), etc
I Needs lots of infrastructure:
I Read-only slab and kernel stacks (except for the current one :)I Efficient hardware support is missing (SMAP v2?)

PaX - kernel self-protection

FutureIntroduction

KernelToolchain

Miscellaneous

Overview
I Android port
I Better virtualization support
I virtualbox, vmware, xen
I More architecture support (especially kernel self-protection)
I Heap (slab) hardening
I CPU cores dedicated to security
I Your ideas :)PaX - kernel self-protection

Futurehttp://pax.grsecurity.net
http://grsecurity.net
irc.oftc.net #pax #grsecurity