• Alexei Starovoitov's avatar
    bpf: verifier (add verifier core) · 17a52670
    Alexei Starovoitov authored
    This patch adds verifier core which simulates execution of every insn and
    records the state of registers and program stack. Every branch instruction seen
    during simulation is pushed into state stack. When verifier reaches BPF_EXIT,
    it pops the state from the stack and continues until it reaches BPF_EXIT again.
    For program:
    1: bpf_mov r1, xxx
    2: if (r1 == 0) goto 5
    3: bpf_mov r0, 1
    4: goto 6
    5: bpf_mov r0, 2
    6: bpf_exit
    The verifier will walk insns: 1, 2, 3, 4, 6
    then it will pop the state recorded at insn#2 and will continue: 5, 6
    
    This way it walks all possible paths through the program and checks all
    possible values of registers. While doing so, it checks for:
    - invalid instructions
    - uninitialized register access
    - uninitialized stack access
    - misaligned stack access
    - out of range stack access
    - invalid calling convention
    - instruction encoding is not using reserved fields
    
    Kernel subsystem configures the verifier with two callbacks:
    
    - bool (*is_valid_access)(int off, int size, enum bpf_access_type type);
      that provides information to the verifer which fields of 'ctx'
      are accessible (remember 'ctx' is the first argument to eBPF program)
    
    - const struct bpf_func_proto *(*get_func_proto)(enum bpf_func_id func_id);
      returns argument constraints of kernel helper functions that eBPF program
      may call, so that verifier can checks that R1-R5 types match the prototype
    
    More details in Documentation/networking/filter.txt and in kernel/bpf/verifier.c
    Signed-off-by: default avatarAlexei Starovoitov <ast@plumgrid.com>
    Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
    17a52670
verifier.c 48.4 KB