[BPF] BPF 관련 여러가지 정리

필터 모델

  BPF의 필터 모델에는 CFG 모델과 Tree 모델이라는 2가지 형식이 있다. 2개의 모델은 계산상으로는 동일한 성능을 가지긴 하지만, 구현 방식이 전혀 다르다. 하지만 최근에는 현대의 기기들이 레지스터 기반이기 때문에 CFG 모델이 구현에 더 적합하다고 하고 있다.

• Tree 모델 : Stack 기반, 각 노드 자체가 boolean으로 표현되어 or 연산에 의해 결론지어짐
• CFG 모델 : Register 기반, 각 노드에 의해 분기되어 흐름을 가지고 있어 분기로 결론지어짐 

 개인적인 생각으로 Tree 모델이 실제로 구현했을 때, 코드는 더 깔끔하다고 생각한다. CFG 모델은 대신 알고리즘 상으로는 더 효율적일 수 있다. 코드가 길면 길수록 중첩 분기가 많아져 코드가 복잡해질 수 있는 반면, Tree 모델은 정돈되는 형태이기 때문에 코드를 정렬시킬 수 있다.

Tree 모델

  Tree 모델은 필터 엔진이 Stack을 기반으로 하고 있다는 특징이 있다. Tree 모델의 명령어는 최상위 2개의 요소를 가져와 이진 부울 또는 비트 연산을 수행하거나,  스택에 상수나 데이터를 push하는 동작을 수행한다. 이 때, 필터 프로그램은 순차적으로 실행할 명령어 리스트이다. 프로그램이 동작을 마친 후, 스택의 최상위에 0이 아닌 값이 있거나 스택이 비어 있다면 데이터가 허가되고, 아닌 경우는 데이터가 거부된다.

문제점

• 시뮬레이션을 위해 스택을 사용하기 때문에 메모리를 많이 사용하게 되어 병목 현상이 발생하기 쉬워짐
• 불필요한 연산이 존재하는 경우, 이것도 함께 수행한 이후에 결론을 낸다는 문제점이 존재
• 특정 부분을 파싱해서 연산을 수행해야 하는 경우, 매우 번거로워짐

CFG 모델(BPF 모델)

  CFG 모델은 필터 엔진이 Register를 기반으로 한다. CFG 모델의 각 노드 결과에 따라 분기되어 특정 흐름을 가진다. 중첩 분기문이라고 생각하면 이해하기 쉬워진다. Tree 모델의 문제점 3가지를 해결할 수 있다. 

BPF Pseudo-Code

• Load : accumulator나 index 레지스터에 값을 복사하는 명령어, Source에는 다양한 값들이 올 수 있음
• Store : accumulator나 index 레지스터의 값을 메모리에 복사하는 명령어
• ALU : operand도 index 레지스터나 상수를 사용하여 accumulator에서 사칙 연산이나 논리 연산 수행
• Branch : accumulator와 상수 또는 x 레지스터로 비교 연산을 테스트하여 제어 흐름 변경
• Return : 필터를 제거하고 저장할 패킷의 위치를 지정하는 명령어, 필터가 0을 반환한 경우에는 패킷을 제거
• Miscellaneous : 기타 등등....

BPF 아키텍쳐 기본 요소

• A : 32bit accumulator
• X : 32bit X 레지스터
• M[] = 16 x 32bit misc 레지스터(통칭 'scratch memory sotre'), 0부터 15까지 주소지정 가능

Instruction 구조

Opcode(16 bits)	jt(8 bits)	jf(8 bits)
k(32 bits)

• Opcode : 명령어의 타입과 주소 모드를 가리킴
• jt, jf : 조건 분기 명령어를 통해 다음 명령어로부터 True 또는 False로 분기하는 대상까지의 Offset으로 사용됨
• k : 다양한 목적을 위해 사용되는 일반적인 필드

Instruction 종류(Addressing Mode에 대해서는 참고의 2번째를 참고)

• Load
• ld : A에 word만큼 로드
• ldh : A에 half-word만큼 로드
• ldb : A에 byte만큼 로드
• ldx : X에 word만큼 로드
• Store
• st : M[]에 A의 내용을 저장
• stx : M[]에 X의 내용을 저장
• ALU
• add : A + <x>
• sub : A - <x>
• mul : A * <x>
• div : A / <x>
• and : A & <x>
• or : A | <x>
• lsh : A << <x>
• rsh : A >> <x>
• Branch
• jmp : 라벨의 위치로 점프
• jeq, jgt, jge : 조건과 일치할 경우, 라벨의 위치로 점프
• jset : A & k인 경우, 라벨의 위치로 점프
• Return
• ret: Return
• Miscellaneous
• tax : X에 A의 내용을 복사
• txa : A에 X의 내용을 복사

JIT 컴파일러

  아래와 같은 bash 커맨드로 bpf_jit을 enable시킬 수 있다.

$ echo 1 > proc/sys/net/core/bpf_jit_enable

• CONFIG_BPF_JIT_ALWAYS_ON이 활성화된 경우, 1로 영구적으로 설정됨
• 2로 설정할 경우, 커널 로그(dmesg)로 이를 덤프할 수 있긴 하지만 추천하지 않음

eBPF

  eBPF는 BPF의 ISA를 확장한 버전이며, BPF extensions이랑은 다르다. eBPF는 일대일 매핑으로 JIT를 수행할 수 있도록 설계되어 빠르고, 백앤드를 통해 최적화된 코드를 생성할 수 있다. 고전 BPF는 32비트 환경에서 JIT 컴파일을 수행하지만, eBPF는 64비트 환경도 지원한다.

새로운 변경 사항

• 레지스터의 갯수가 2개에서 10개로 증가
• 기존은 A와 X만 존재
• eBPF는 R0 - R10까지 존재, Calling Convention도 추가되었음(ARM이랑 비슷)
• 레지스트의 크기가 32비트에서 64비트로 증가
• 조건부 jt/jf의 대상을 jt/fall-through로 변경
• 예)    if(cond) jump_true; else jump_false
• 변경) if(cond) jump_true; else fall-through
• bpf_call 명령어를 통해 커널의 시스템 콜을 오버헤드 없이 호출 가능 
• Calling Convention이 생기면서 매핑시킬 수 있게 되어서

eBPF Instruction 구조

Opcode(8 bits)	dst_reg(4 bits)	src_reg(4 bits)	offset(16 bits)
imm(32 bits)

  BPF에서는 Opcode의 크기가 16 bits지만, eBPF는 Opcode의 크기가 8 bits로 더 작아졌다. 그래서 8 bits로 Opcode의 정보를 표현하기 위해 각 부분(예) instruction의 클래스, 실제 동작 코드, Source)을 나눠 이를 통해 정확한 Opcode Instruction을 구분한다. 더 자세한건 2번째 참고의 843번째 줄을 보면 된다. 

  990번째 줄에는 Instruction 구조에 따른 예제가 잘 나와 있다.

eBPF Verifier

  ...

eBPF Encode 정리

  bpf_insn.h의 전처리문 내용을 한 번 정리하였다.

• ALU
• BPF_ALU64_REG : src 레지스터와 dst 레지스터가 64bit arithmetic 연산 수행, 모든 arithmetic 연산을 다 포함하기 때문에 OP code를 인자로 주어야 함
• 필요 : opcode, src 레지스터, dst 레지스터
• ex) dst_reg += src_reg
• BPF_ALU32_REG : src 레지스터와 dst 레지스터가 32bit arithmetic 연산 수행
• 필요 : opcode, src 레지스터, dst 레지스터
• ex) dst_reg += src_reg
• BPF_ALU64_IMM : dst 레지스터와 상수 값을 64bit arithmetic 연산 수행
• 필요 : opcode, dst 레지스터, 상수 값
• ex) dst_reg += imm32
• BPF_ALU32_IMM : dst 레지스터와 상수 값을 32bit arithmetic 연산 수행
• 필요 : opcode, dst 레지스터, 상수 값
• ex) dst_reg += imm32
• Move
• BPF_MOV64_REG : dst 레지스터에 src 레지스터 값 저장
• 필요 : dst 레지스터, src 레지스터
• ex) dst_reg = src_reg
• BPF_MOV32_REG : dst 레지스터에 src 레지스터 값 저장
• 필요 : dst 레지스터, src 레지스터
• ex) dst_reg = src_reg
• BPF_MOV64_IMM : dst 레지스터에 상수 값 저장
• 필요 : dst 레지스터, 상수 값
• ex) dst_reg = imm32
• BPF_MOV32_IMM : dst 레지스터에 상수 값 저장
• 필요 : dst 레지스터, 상수 값
• ex) dst_reg = imm32
• Load
• BPF_LD_IMM64 : dst 레지스터에 64bit 상수 값 저장
• 필요 : dst 레지스터, 상수 값
• ex) dst_reg = imm64
• BPF_LD_IMM64_RAW : dst 레지스터에 64bit 상수 값 저장, src 레지스터는 어디에 사용되는지 모르겠다.
• 필요 : dst 레지스터, src 레지스터??, 상수 값
• ex) dst_reg = imm64
• BPF_LD_MAP_FD : dst 레지스터에 프로세스의 로컬 map_fd 값을 참조하여 저장
• 필요 : dst 레지스터, MAP_FD 값
• BPF_LD_ABS : 직접 패킷 데이터에 상수 값으로 접근하여 R0 레지스터로 size 만큼의 데이터를 저장
• 필요 : size, 상수 값
• ex) R0 = *(uint *) (skb->data + imm32)
• BPF_LDX_MEM : src 레지스터 + 오프셋 값에 있는 데이터를 size 만큼 dst 레지스터에 저장
• 필요 : size, dst, src, off
• ex) dst_reg = *(uint *) (src_reg + off16)
• Store
• BPF_STX_MEM : src 레지스터 값을 dst 레지스터 + 오프셋 값의 주소에 size 만큼 저장
• 필요 : size, dst, src, off
• ex) *(uint *) (dst_reg + off16) = src_reg
• BPF_STX_XADD : dst 레지스터 + 오프셋 값의 주소에 있는 데이터를 src 레지스터 값만큼 더해서 그대로 size 만큼 저장
• 필요 : size, dst, src, off
• ex) *(uint *)(dst_reg + off16) += src_reg
• BPF_ST_MEM : dst 레지스터 + 오프셋 값의 주소에 상수 값을 size만큼 저장
• 필요 : size, dst, src, off
• ex) *(uint *) (dst_reg + off16) = imm32
• Jump
• BPF_JMP_REG : dst과 src의 연산 결과가 참인 경우, 오프셋 값만큼 점프
• 필요 : op, dst, src, off
• ex) if (dst_reg 'op' src_reg) goto pc + off16
• BPF_JMP_IMM : dst와 상수 값의 연산 결과가 참인 경우, 오프셋 값만큼 점프
• 필요 : op, dst, imm, off
• ex) if (dst_reg 'op' imm32) goto pc + off16
• Etc
• BPF_RAW_INSN : 모든 값을 직접 지정하여 사용
• BPF_EXIT_INSN : BPF 프로그램 종료

참고

• http://www.vodun.org/papers/net-papers/van_jacobson_the_bpf_packet_filter.pdf
• https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/Documentation/networking/filter.txt
• http://www.brendangregg.com/ebpf.html
• https://github.com/torvalds/linux/blob/master/samples/bpf/bpf_insn.h
• seccomp 메뉴얼 번역 : https://github.com/wariua/manpages-ko/wiki/seccomp(2)