ball-blog
  • Welcome, I'm ball
  • Machine Learning - Basic
    • Entropy
    • Cross Entropy
    • KL-Divergence
    • Monte-Carlo Method
    • Variational Auto Encoder
    • SVM
    • Adam Optimizer
    • Batch Normalization
    • Tokenizer
    • Rotary Positional Encoding
    • Vector Quantized VAE(VQ-VAE)
    • DALL-E
    • Diffusion Model
    • Memory Layers at Scale
    • Chain-of-Thought
  • Einsum
  • Linear Algebra
    • Linear Transformation
    • Determinant
    • Eigen-Value Decomposition(EVD)
    • Singular-Value Decomposition(SVD)
  • AI Accelerator
    • CachedAttention
    • SGLang
    • CacheBlend
  • Reinforcement Learning
    • Markov
  • Policy-Improvement Algorithm
  • Machine Learning - Transformer
    • Attention is All you need
    • Why do we need a mask in Transformer
    • Linear Transformer
    • kr2en Translator using Tranformer
    • Segment Anything
    • MNIST, CIFAR10 Classifier using ViT
    • Finetuning PaliGemma using LoRA
    • LoRA: Low-Rank Adaptation
  • EGTR: Extracting Graph from Transformer for SGG
  • Machine Learning - Mamba
    • Function Space(Hilbert Space)
    • HIPPO Framework
    • Linear State Space Layer
    • S4(Structures Space for Sequence Model)
    • Parallel Scan Algorithm
    • Mamba Model
  • Computer System
    • Memory Ordering: Release/Acquire 1
    • Memory Ordering: Release/Acquire 2
    • BUDAlloc
    • Lock-free Hash Table
    • Address Sanitizer
  • App development
    • Bluetooth connection in linux
    • I use Bun!
    • Using Tanstack-query in Frontend
    • Deploying AI Service using EC2
  • Problem Solving
    • Bipartite Graph
    • Shortest Path Problem in Graph
    • Diameter of a Tree
  • Scribbles
Powered by GitBook
On this page
  • BUDAlloc: Defeating Use-After-Free Bugs by Decoupling Virtual Address Management from Kernel
  • My Contributions
  • Summary
  • Solving Internal Fragmentation
  • Solving Frequent Syscalls
  • Optimization for PARSEC.swaptions benchmark

Was this helpful?

Edit on GitHub
  1. Computer System

BUDAlloc

Last updated 3 months ago

Was this helpful?

BUDAlloc: Defeating Use-After-Free Bugs by Decoupling Virtual Address Management from Kernel

My Contributions

  1. Built Benchmark script that shows the performance/memory overhead of BUDAlloc compared to other UAF protection systems such as FFMalloc, DangZero etc.

  2. Built an automation script using gdb, which shows if the system(BUDAlloc, FFMalloc, DangZero etc) detected/prevented/vulnerable to various CVEs.

  3. Proposed an optimization to the system, tested with several benchmarks if it is applicable.

Summary

BUDAlloc use OTA(One-Time-Allocator) concept to prevent Use-After-Free bugs.

OTA(One-Time-Allocator)

OTA is a concept of never reusing Memory chunk.

However, these basic OTA has two problems: Internal fragmentation and frequent syscalls

BUDAlloc effectively solved two problems as follows:

Solving Internal Fragmentation

BUDAlloc solved internal fragmentation using virtual aliasing. Virtual aliasing is a concept that makes another layer for virtual memory system. It makes the object allocated in seperate virtual page, but actually in same physical page.

Solving Frequent Syscalls

BUDAlloc solved frequent syscall problem using eBPF. Frequent syscall for mremap, munmap was the main bottleneck for OTA.

The root cause of the syscall is the semantic gap between User-level and Kernel-level. Since Kernel-level doesn't have any information about the virtual alias, canonical pages, it requires syscall to get information about it.

However, BUDAlloc resolved semantic gap problem using eBPF.

Optimization for PARSEC.swaptions benchmark

I observed a performance overhead at PARSEC.swaptions benchmark.

This was due to bottleneck in Canonical2Alias trie lookup. I tried to reduce entry numbers in the trie. So I partially adopted non-demand-paging to large pages(larger than 4KB). This idea was brought from FFMalloc. However, this caused a huge memory-overhead, and small performance improvement.

As a result, we didn't take this optimization.

LogoBUDAlloc: Defeating Use-After-Free Bugs by Decoupling Virtual Address Management from Kernel | USENIX
Allocation scheme of OTA
Deallocation of 1KB object in OTA
Figure of virtual aliasing
Figure2 of virtual aliasing
Solving Frequenst Syscall problem using eBPF
PARSEC.swaptions benchmark results
Performance benchmark result
Memory footprint benchmark result
https://github.com/casys-kaist/BUDAlloc