저자	Junho Ahn et al.
연도	2024
게재처	USENIX security
유형	one-time allocator
URL	https://usenix.org/conference/usenixsecurity24/presentation/ahn

Introduction

메모리 버그 중 하나인 UAF(Use-After-Free)는 CWE에서 가장 만연하고 영향력 있는 취약점 25개 중 8번째(2024 ver.)에 위치할 정도로 심각한 버그에 해당한다.

최근까지 이러한 UAF 버그를 예방 및 탐지하기 위해 많은 연구가 진행되어 왔다.

Category	Description	Limitation	Paper
explicit labeling	메모리에 할당/해제 여부를 태그	성능 오버헤드 ↑	– CETS (ISMM 10’) – AddressSanitizer (USENIX ATC 12’)
reference counting	메모리에 대한 참조 수를 저장(증가 및 감소)	C/C++환경에 적용 힘듦, 오버헤드 ↑	– pSweeper (CCS 18’) -CRCount (NDSS 19’)
garbage collection	메모리를 가리키는 포인터 유무 지속적 체크	Multi-thread 환경에서 오버헤드 ↑	– MarkUs (IEEE S&P 20’) – MineSweeper (ASPLOS 22’)
one-time allocator	한번 할당했던 가상 주소를 재할당 X	semantic gap, 호환성 ↓, 오버헤드 ↑	– Oscar (USENIX Security 17’) – FFmalloc (USENIX Security 21’) – DangZero (CCS 22’)

이 중에서 one-time allocator(OTA) 기법이 최근 주목 받고 있다. 이는 UAF 버그 자체를 제거하진 않지만, UAF 버그를 통한 공격을 불가능하게 만든다. system call을 기반으로 하거나, 가상 환경을 기반으로 하는 등의 이전 연구가 존재했지만, 이들은 모두 오버헤드가 너무 높거나 기존 커널과의 호환성이 떨어진다는 문제점이 존재했다.

BUDAlloc에서는 이러한 OTA 기법에 대한 새로운 방법을 제안한다. 주된 아이디어로는 커널이 관리하는 주소와 유저가 관리하는 주소를 분리하여, 기존에 커널에서 수행하던 가상 주소 관리를 유저 레벨에서 수행하도록 하는 것이다. 이를 위해 커널에서 직접 사용자가 정의한 코드를 실행할 수 있는 기능인 eBPF(extended Berkeley Packet Filter)를 사용했다.

BUDAlloc은 위의 방법을 통해 성능 오버헤드, 메모리 오버헤드, 안전성 사이에서 적절한 균형을 맞췄다. 또한, 확장성과 호환성 측면에서도 이전 연구들의 한계점을 해결해냈다.

Background

What is eBPF?

eBPF는 커널이나 다른 애플리케이션 상에서 사용자가 작성한 코드를 실행할 수 있도록 한 기능이다. eBPF의 작동 방식은 다음과 같다.

1. 사용자가 C(혹은 다른 언어)로 eBPF 프로그램 작성

2. 프로그램을 eBPF 바이트코드로 컴파일

3. 커널(혹은 애플리케이션)에 로드 및 검증

4. 특정 이벤트 발생 시 해당 프로그램 실행

eBPF를 사용하는 이유는 다음과 같은 장점을 가지기 때문이라고 볼 수 있다.

커널 레벨에서 직접 실행되기에 높은 성능 제공
커널 소스 코드 수정 없이 사용자가 정의한 코드 사용 가능
CAP_BPF 권한만 있으면 사용 가능 (sudo 권한 필요 X)

eBPF는 보통 네트워킹(패킷 처리, 로드 밸런싱), 보안(실시간 위협 탐지), 성능 모니터링 등에 사용된다.

One-Time Allocator

one-time allocator의 기본 아이디어는 말 그대로 ‘한 번만 할당’, 즉 한번 할당했다가 해제한 주소를 재사용하지 않는 것이다. 이를 위해서 virtual aliasing이라는 기법을 사용한다.

virtual aliasing은 가상 주소를 두 가지 종류로 나눈다. Canonical address와 Alias address이다.

canonical address는 기존의 virtaul-physical 매핑에서의 virtual address와 같은 존재로, OTA에서 내부적으로 사용하는 가상 주소이다. 반면 alias address는 OTA를 위해 도입된 주소로, 실제 사용자에게 반환되는 주소이며, 사용자 입장에서는 이 alias address를 virtual-physical 매핑에서의 virtual address로 인식하게 된다.

alias address 여러개가 하나의 canonical address와 매핑되며, 각각의 alias address는 canonical address에서 서로 다른 offset을 가지게 된다. 그리고 canonical address는 physical address와 일대일로 매칭되며, 따라서 해당 canonical address와 매핑된 여러 alias address들이 하나의 physical address와 매핑되는 것이다.

만약 사용자가 메모리 할당 요청 후 이를 해제했다면, 해당 alias address는 해제되고 이후에 다시 사용되지 않기 때문에, 만약 해당 주소로 접근을 시도한다면 이를 UAF로 판단할 수 있는 것이다.

Challenge : Semantic Gap

Semantic Gap

alias-canonical mapping 정보를 바탕으로, 커널은 page fault 시에 alias와 physical memory를 매핑 그런데 커널은 alias-canonical mapping 정보를 모르고 있음 → Semantic Gap

Solution 1 : 매 할당, 해제마다 시스템 콜(mremap, munmap) 호출 → Performance overhead ↑

Solution 2 : munmap을 모았다가 여러개를 한 번에 처리(FFmalloc) → Memory overhead ↑, Bug detection ↓

Threat Model

프로그램은 하나 이상의 UAF 버그들을 가지며, 공격자는 최소 하나의 UAF 버그를 발생시킬 수 있음
Allocator 자체는 공격할 수 없음. 즉, Allocator는 reliability를 가짐
UAF 이외의 메모리 버그(OOB, side-channel attack 등)은 방어 대상으로 고려하지 않음
두 가지 modes → prevention < detection
- prevention mode : UAF 발생 시 crash를 일으키거나, 이전의 데이터에 접근하게 됨
- detection mode : UAF 발생 시 crash 일으킴. (이전 데이터에 접근조차 방지)

Design

Overview

User-level Components

user-level OTA와 virtual address manager(LibMM)으로 구성됨

# user-level OTA

LD_PRELOAD로 기존 메모리 할당자의 API를 intercpet, 작업 처리 후에 다시 relay

Allocating an object

internal allocator에서 새로운 canonical address를 할당(일반적인 가상주소 할당)
user-level OTA에서 새로운 virtual alias page를 할당 → user-level에서 가상 주소 공간을 직접 관리하므로 system call(mremap) 필요 X
alias-to-canonical 매핑 정보를 trie metadata에 저장
application에 alias 주소를 return

Access to the object by alias address(page falut)
alias page fault 발생 시, BUDAlloc custom page fault handler가 trie metadata에서 해당 alias address와 매핑된 canonical address를 찾음. 만약 canonical entry가 존재한다면, alias page를 canonical address가 매핑된 physical address와 매핑시켜줌.
Freeing an obejct
1. trie metadata를 스캔해서 해제하려는 alias object에 해당하는 canonical address를 찾음. → internal allocator에게 해당 canonical을 재사용하라고 notify → internal fragmentation 방지
2. 두 가지 mode에 따라 처리가 달라짐.
  1. prevention mode
    1. per-thread ring buffer에 해제된 alias address 삽입
    2. 새로 할당된 alias address에 대한 접근 발생 시(page fault), ring buffer에 저장된 모든 alias addresses를 unmap시킴
    → canonical address의 해제된 slot을 재사용하기 위해서는 반드시 해제된 alias address의 canonical page에 대한 매핑이 삭제된 상태, 즉 page table로부터 alias pages에 대한 정보가 사라진 상태여야함
  2. detection mode
    1. alias address 해제 요청 발생 시 바로 unmap
3. trie metadata에서 해제하는 alias address에 대한 canonical address 매핑 정보를 삭제(정확히는 canonical entry를 삭제) → 만약 다음 page fault 발생 시, trie metadata에서 alias address에 해당하는 canonical entry를 찾지 못할 시, 이를 UAF로 판단, user에게 report

# virtual address manager(LibMM)

internal allocator → mimalloc (https://github.com/microsoft/mimalloc)

internal allocator는 system call(mmap, munmap, madvise)를 통해 virtual address(canonical address)를 할당 받고 해제시킴.

BUDAlloc이 이러한 system call을 가로채서 LibMM에게 포워딩

LibMM에서는 Linux Kernel과 같이 canonical address를 linked list로 관리함

page fault 발생 시,

만약 canonical page라면, 해당 page에 physical address를 매핑시켜 줌.
만약 alias page라면, shared metadata로부터 해당하는 canonical page를 찾음

Kernel Components

# Decoupling address space

user-level에서 가상 주소 공간을 관리하므로(기존엔 Kernel이 관리), physical address layout을 그대로 user-level에 보여주는 것은 보안 취약점이 될 수 있음 → Solution : pseudo-physical address

pseudo-phsyical address
user-level OTA가 제공하는 physical address로, kernel이 이를 받아서 real physical address로 변환 후에 virtual-physical 매핑을 만들게 된다.

pseudo-physical address를 physical address로 변환하기 위해서 해당 프로세스 자체의 page table을 사용하기 때문에 추가적인 메모리 오버헤드는 발생하지 않는다.

pseudo-physical address를 사용함으로써 BUDAlloc은 user-level에서 해당 프로세스의 가상 주소만을 사용할 수 있게 한다. 즉, user-level OTA가 사용하는 주소 공간과 kernel이 사용하는 주소 공간을 분리하는 것이다. 따라서 만약 owner process가 오염되더라도, 해당 문제가 다른 프로세스의 메모리(ex. 페이지 테이블) 혹은 커널 메모리를 수정하는 것으로까지 이어지는 것을 막는다.

BPF helper function에서 인자 pindx로 pseudo-physical address를 전달해준다. 이때 pindx가 unused 상태라면, 새로운 zeroed physical page에 이를 매핑시키고, 이후에 virtual address와 pseudo-physical address를 연결시킨다.

# Custom page fault handler

이전에 말했듯이, user-level OTA는 alias-to-canonical 매핑 metadata를 kernel과 공유한다. customized page fault handler는 이 metadata 정보를 바탕으로 page table을 수정한다. (bridging the semantic gap)

BUDAlloc은 기존 Linux kernel page fault handler를 eBPF를 사용하여 확장시킴으로써 customized page fault handler를 만들어냈다.

customized page fault handler에는 몇가지의 helper function이 추가되었다.

Page Table
- bpf_set_page_table(void *vaddr, size_t len, void *pindx, u64 vm_flags, u64 prot)
- bpf_unset_page_table(void *vaddr, size_t len)
Shared Memory
- bpf_uaddr_to_kaddr(void *uaddr, size_t len)

+ 추가로 POSIX mmap 시스템 콜을 확장시켜서 LibMM과 OTA가 사용하기 위한 가상 주소 공간을 추가로 등록시키도록 했다.

user-level OTA는 alias page를 매핑하기 위해 bpf_set_page_table()를 사용한다. 여기서 vaddr이 alias address에 해당하고, pindx는 pseudo-physical address에 해당한다.

custom page fault handler를 호출하면, 이는 shared metadata를 참조하여 faulted address를 physical address와 위치시키게 된다. page fault handling이 마무리될 때, 성공이라면 0, 실패라면 1을 반환한다.

custom page fault handler와 user-level OTA는 alias-to-canonical metadata를 공유하게 된다. 이때 user와 kernel 사이의 shared memory를 통해 bpf_uaddr_to_kaddr()이 사용된다.

shared memory는 하나의 physical address를 가지지만, user와 kernel 각각에게 다른 가상 주소로 매핑된다. 따라서 위의 helper function을 통해 kernel에서도 user-level OTA가 설정한 메타데이터에 안전하게 접근할 수 있는 것이다.

+ 추가로, eBPF에서 page table을 수정하려고 할 때마다 TLB를 flush 시켜줌으로써 page table 수정으로 인한 오류를 방지한다. 이는 보수적인 접근일 수 있지만, page table 업데이트의 정확성과 안전성을 우선시한 선택이다.

Scalability

BUDAlloc user-level allocator는 fine-grained locking과 lock-free data 구조를 통해 multi-threading 확장성에 최적화되어 있다.

OTA는 메타데이터 update가 빈번하게 일어나기 때문에, coarse-grained kernel lock을 사용하는 건 상당한 오버헤드를 발생시킬 수 있다.

BUDAlloc은 address space를 decoupling시켰기에, user-level에서의 가상 주소 관리(빈 가상 주소 찾기, 빈 가상 주소 범위 반환)에서 lock 경쟁을 줄일 수 있다.

Shared trie metadata
trie metadta는 four level로 구성되어 있으며, 각각은 48 bits의 가상 주소로 되어 있다. 마지막 레벨 entry는 canonical address를 가리키지만, 상위 entry들은 다음 레벨의 entry를 가리킨다. 따라서 상위 레벨 노드(L1-L3)와 최하위 노드(L4)에 각기 다른 lock 체계를 적용시킨다.
- upper-level nodes(L1-L3) : reference counting → 상위 레벨 노드의 값은 잘 수정되지 않기에, 접근 시 증가하고 완료시 감소하는 reference count 기법을 적용한다. 만약 0이 되면 node를 해제한다. (thread는 dangling node에 접근하지 않음)
- leaf nodes(L4) : spinlock → 최하위 노드의 경우 canonical address를 저장하기에 동작 중에 자주 수정될 수 있다. 따라서 해당 노드에는 spinlock을 적용하여 leaf node에 대한 접근을 serialize 한다. 이 spinlock은 user threads와 eBPF code 사이에서 공유된다.

Deferred free list
위에서 prevention mode는 per-thread ring buffer에 alias address를 모아놓고 다음 page fault 발생 시 한번에 unmap 시킨다고 했다. 이때 만약 thread가 재사용된 canonical address를 통해 새로운 alias object에 접근하려고 한다면, 해당 canonical address와 관련된 freed alias page들은 반드시 그 전에 unmap 되어야 한다. → 참고)

이를 안전하게 보장하기 위해, BUDAlloc custom page fault handler는 per-thread spinlock을 통해 보호 받는다. 또한, 새로운 alias에 대한 trie entry를 해당 thread index로 mark 해놓는다.
- 만약 trie entry가 mark되어 있는데 custom page fault handler가 lock을 얻지 못했다면, 이는 다시 page fault를 시도하여 이전 매핑이 제대로 해제된 것을 확인한다.
- 만약 trie entry가 mark되어 있지 않다면, 이는 새로운 alias address를 사용하는 것이 아니기에 deferred free를 건너뛰고 page fault를 그대로 진행한다.
Supporting fork
fork를 실행하기 전, user-level OTA는 모든 spinlock을 release하고 read-write lock을 사용하여 fork가 끝나기를 기다림. → fork 시작과 끝 사이의 다른 thread들의 상호작용으로 lock 상태가 inconsistent한 것을 방지

Compatibility

On-demand paging
user-level OTA에서 alias & canonical의 매핑을 pseudo-physical address와 관리하기에, 실제 kernel에서의 physical memory 관리에는 아무런 영향을 주지 않는다. 따라서 BUDAlloc은 기존의 allocator와 마찬가지로 page fault 시에 page table entry를 위치시킬 수 있다.
Copy-on-Write
이전의 다른 OTA(syscall-based, LibOS-based)는 copy-on-write를 위해서 전체 address space를 복사해야 하는 문제점이 있었다. (혹은 아예 CoW를 지원하지 않기도 함) 그러나 BUDAlloc의 경우, On-demand paging과 마찬가지로 kernel의 physical memory 관리에는 아무런 영향을 주지 않으며, eBPF를 사용해 fork도 정상적으로 지원하기에 기존의 copy-on-write를 그대로 사용할 수 있다.
proc file system

Two challenges

VA-Chain reverse map
기존 OS는 physical address 관리 작업(swapping, migration, compaction, copy-on-write 등)을 위해 reverse mapping(physical page에 대한 virtual address를 나열)을 지원한다.

Linux에서는 object 기반으로, virtual address 관리를 위한 메타 데이터로 vm_area_struct와 함께 reverse map을 사용한다.

BUDAlloc은 virtual address 관리를 kernel에서 수행하지 않고 user-level에서 수행한다. 따라서 특정 physical page에 대한 virtual address들은 VA-chain 형태로 저장하고, 이때 Linux의 struct page의 사용하지 않는 field를 활용하여 reverse map을 구성한다.

각 mapping마다 16bytes가 소모되며, 만약 virtual address가 연속적이라면 해당 주소들에 대해서는 16bytes 한번만 소모되기에 실제 평가 시에 acceptable한 메모리 오버헤드를 보였다.
PTE reference count
기존 Linux에서는 페이지 테이블의 최하위 레벨 entries가 해제되면, 그에 해당하는 상위 레벨의 페이지 테이블 entry도 해제하여 unused page table을 낭비하지 않게 한다. 이때, vm_area_struct의 가상 주소 할당 정보를 바탕으로 최하위 레벨 entries를 선택적으로 해제한다.

BUDAlloc에서는 vm_area_struct에 대한 정보를 알 수 없기에(user-level에서 가상 주소를 관리), struct page의 사용하지 않는 field를 통해 각 PTE entries의 reference count를 저장함. 이를 통해 page table을 효과적으로 관리할 수 있었다.

Evaluation

Environment

OS : Linux 6.4.0

CPU : Intel(R) Xeon(R) Gold 5220R at 2.2GHz with 24 cores

Memory : 172GB DRAM – 2666 MHZ

SSD : 512GB

Security

BUDAlloc의 두가지 mode(prevention, detection)와 이전 연구인 FFmalloc, DangZero 대상으로 실험을 진행했다. detection mode에서는 전부, prevention mode에서는 30개 취약점 중 1개를 제외하곤 모두 탐지 가능했다. FFmalloc은 연속된 페이지가 해제될 때까지 unmap을 미뤘기 때문에 대부분의 실험에서 UAF를 막을 순 있었지만 탐지에는 실패했다.

Performance

Single-threaded Benchmarks

SPEC CPU 2006 & 2017

Multi-threaded Benchmarks

PARSEC 3.0

Real-world Applications

Apache and Nginx

Limitation

TLB pressure

TLB pressure는 이전 one-time allocator 연구에서도 계속 지적됐던 한계점이다. OTA가 Use-After-Free를 막는 방법이 alias 페이지를 재사용하지 않는 방법이므로, TLB에 올라간 alias 주소들은 한번 해제된 이후에는 더 이상 재사용되지 않는다. 이는 TLB miss 비율의 증가로 이어진다.

또한, BUDAlloc에서는 보안을 고려하여 alias page를 해제할 때마다 TLB를 flush해준다. 이는 이미 해제되어 다시 사용되지 않을 alias page의 주소가 TLB에 남아서 악용되는 것을 막는 것이다. 이로 인해서 마찬가지로 TLB miss의 비율이 증가하게 된다.

TCB size ↑

BUDAlloc에서는 가상 주소 관리를 커널에서 유저 레벨로 분리하기 위해서 eBPF를 도입하였다. 그런데 위협 모델에서 eBPF 자체는 안전하다고 가정한다. 이는 eBPF 자체에 대한 공격, 혹은 eBPF를 이용한 공격을 가능하게 만들게 된다.

Related Works

one-time allocator

DangZero: Efficient Use-After-Free Detection via Direct Page Table Access (CCS 22’)
→ 리눅스 가상화를 이용하여 유저가 page table을 직접 수정하는 방식으로 OTA를 구현했다.
Oscar: A Practical Page-Permissions-Based Scheme for Thwarting Dangling Pointers (USENIX Security 17’) → 시스템 콜을 이용하여 semantic gap을 해결하였다.
Preventing Use-After-Free Attacks with Fast Forward Allocation (USENIX security 17’) → virtual aliasing을 사용하지 않는다. 때문에 벤치마크 실험 결과에서 메모리 오버헤드가 높게 측정되었다.

Other methods

추후 추가 예정

[Paper Review] BUDAlloc: Defeating Use-After-Free Bugs by Decoupling Virtual Address Management from Kernel

Introduction

Background

What is eBPF?

One-Time Allocator