Sanitizer

개요

Sanitizer는 Compiler Instrumentation을 활용하여서 Runtime에 버그를 잡는 Programming tool을 의미한다. 대표적인 예로 Shadow memory를 활용하셔어 Memory corruption을 추적하는 AddressSanitizer과 같은 툴이 있다.

종류

Sanitizer는 Memory Safety를 검사하기 위해 필요한 Metadata를 어떤 방식으로 찾는지에 따라 크게 두 가지로 나눌 수 있다. 이때 Metadata를 찾는 데 사용하는 기준을 Identity Unit이라고 한다. 효율적인 Identity Unit은 Metadata Lookup이 빠르고, 메모리가 해제되거나 재사용되더라도 Identity가 안정적으로 유지되어야 하며, Object의 Bounds와 Liveness 정보를 식별할 수 있어야 한다. 빠른 Metadata Lookup은 Runtime Overhead를 줄이고, 안정적인 Identity는 Quarantine 없이도 Temporal Bug를 검출할 수 있도록 하며, 정확한 Bounds Metadata는 큰 Redzone 없이도 Spatial Bug를 검출할 수 있도록 한다. 기존 Sanitizer들은 Identity Unit을 정의하는 방식에 따라 Location-based Sanitizer와 Identity-based Sanitizer로 구분할 수 있다.

Location-based Sanitizer

Location-based Sanitizer는 Memory Location을 기준으로 Metadata를 관리한다. 대표적인 예시인 AddressSanitizer(ASan)는 Application Memory를 Shadow Memory에 Mapping하고, Heap, Stack, Global Object 주변의 Redzone을 Poisoned 상태로 표시한다. ASan은 8바이트의 Application Memory를 1바이트의 Shadow Memory로 표현하는 1:8 Mapping을 사용한다. 실제 Memory Access가 발생하면 접근하려는 Address를 이용하여 Shadow Memory의 위치를 직접 계산하고, 해당 위치가 현재 접근 가능한 상태인지 확인한다. 따라서 접근하려는 Address가 Poisoned Redzone에 해당하면 Spatial Bug를 검출할 수 있으며, 해제된 메모리의 Shadow Metadata가 Poisoned 상태로 유지되는 동안에는 Temporal Bug도 검출할 수 있다. 이 방식은 Metadata Lookup이 매우 빠르다는 장점이 있다. 그러나 Shadow Memory, Redzone, Delayed Reuse로 인해 추가적인 Memory Overhead가 발생한다. Spatial Bug의 검출 범위를 늘리기 위해서는 더 큰 Redzone이 필요하며, Temporal Bug의 검출 범위를 늘리기 위해서는 메모리의 재사용을 더 오래 지연시켜야 한다. 두 방식 모두 Memory Overhead를 증가시킨다. 또한 Location-based Sanitizer는 하나의 Memory Range 전체를 단일 Object Bounds Check로 검사할 수 없다. 대신 해당 Range에 대응하는 Shadow Metadata를 확인해야 하므로, 검사 범위가 커질수록 Runtime Overhead가 증가할 수 있다.

Identity-based Sanitizer

Identity-based Sanitizer는 Memory Location이 아니라 Memory Object 또는 해당 Object를 가리키는 Pointer의 Identity를 기준으로 Metadata를 관리한다. 이러한 Metadata에는 Object의 Bounds와 Liveness 정보가 포함될 수 있다. 따라서 단순히 접근하는 Memory Location이 유효한지를 확인하는 대신, 해당 접근이 특정 Object의 Bounds와 Lifetime을 만족하는지 직접 검사할 수 있다. 또한 Bounds 정보를 활용하여 Compiler가 여러 Memory Check를 병합하거나(Check Merging), Loop 밖으로 이동시키거나(Check Hoisting), 불필요한 Check를 제거하는(Check Elimination) 최적화를 수행할 수 있다. Identity-based Sanitizer는 Metadata를 Object 단위로 관리하는지, Pointer 단위로 관리하는지에 따라 다시 두 가지로 나뉜다.

Object-based Sanitizer

Object-based Sanitizer는 각 Pointer에 Metadata를 연결하는 대신, Allocation Object마다 Metadata를 한 번씩 저장한다. Runtime은 Object가 할당되거나 해제될 때 Metadata를 갱신하며, Pointer가 생성되거나 복사되는 과정에서는 별도의 Metadata Propagation이 필요하지 않다. 따라서 Pointer-based Sanitizer에서 발생하는 Metadata Propagation Overhead를 피할 수 있다. 하지만 Object-based Sanitizer는 개별 Pointer가 아닌 Allocation Object를 기준으로 Metadata를 관리하기 때문에, 하나의 Object 내부에서 발생하는 Intra-object Overflow를 검출할 수 없다는 한계가 있다. 또한 Memory Access가 발생했을 때 해당 Pointer가 어떤 Object를 가리키는지 식별해야 한다. 단순한 Metadata Table Lookup은 높은 Runtime Overhead를 발생시킬 수 있기 때문에, 실제 Sanitizer들은 Metadata Lookup 비용을 줄이기 위한 다양한 기법을 사용한다. 대표적으로 제한된 Address Layout, Rounded Object Size, Shadow Metadata, Low-fat Pointer 등을 활용한다. 그러나 Allocation Size를 특정 단위로 반올림하면 Memory Overhead가 증가할 수 있다. 또한 Metadata가 실제 Object의 정확한 Bounds가 아니라 반올림된 Bounds를 기록하는 경우, 일부 OOB를 검출하지 못할 수 있다.

Pointer-based Sanitizer

Pointer-based Sanitizer는 각 Pointer Value에 Metadata를 연결하는 방식이다. 각 Pointer는 자신이 가리키는 Object의 Bounds 정보를 유지하므로, 해당 Pointer를 통한 Memory Access가 원래 Object의 경계를 벗어나는지 정확하게 검사할 수 있다. 따라서 Pointer-based Sanitizer는 정확한 Spatial Memory Safety Checking을 제공할 수 있으며, 별도의 Liveness Metadata를 추가하면 Temporal Safety Checking으로 확장할 수도 있다. 또한 Pointer의 Bounds를 해당 Subobject의 범위로 제한하면 Intra-object Overflow도 검출할 수 있다. 그러나 이러한 방식은 Pointer가 생성되거나, 복사되거나, Memory에 저장되거나, 다시 Load되거나, Pointer Arithmetic이 수행될 때마다 해당 Pointer의 Metadata도 함께 전달해야 한다. Location-based Sanitizer가 간단한 Address 계산과 Shadow Memory Lookup만 수행하는 것과 달리, Pointer-based Sanitizer는 Pointer Operation 전반에 걸쳐 Metadata Propagation을 수행해야 한다. 이로 인해 Compiler Optimization을 적용하더라도 상당한 Runtime Overhead가 발생할 수 있다. 또한 Instrumentation되지 않은 코드와의 호환성 문제도 존재한다. Instrumentation되지 않은 코드에서 Pointer를 복사하면서 해당 Metadata를 함께 전달하지 않는 경우, Pointer와 Metadata의 연결이 끊어질 수 있기 때문이다.

Sanitizer 관련 프로젝트 정리

Sanitizer 프로젝트 정리 (* 수치는 직접 측정, 혹은 다른 논문에 측정된 수치를 참고함)

Name	Target	Target Vulnerability	Memory overhead	Performance overhead	Scalability
ASAN	Application	Memory corruption	73%	240%	Low
KASAN	OS	Memory corruption
LSan	Application	Memory Leak
TSan	Application	Data races & Deda locks
MSan	Application	Uninitialized memory
UBSan	Application	Undefined behaviors

Sanitizer 관련 논문 정리

Sanitizer 관련 논문 정리 (* 수치는 직접 측정, 혹은 다른 논문에 측정된 수치를 참고함)

Name	Target	Target Vulnerability	Memory overhead	Performance overhead	Scalability
ASAN	Application	Memory corruption	73%	240%	Low
KASAN	OS	Memory corruption
LSan	Application	Memory Leak
TSan	Application	Data races & Deda locks
MSan	Application	Uninitialized memory
UBSan	Application	Undefined behaviors