AddressSanitizer Optimization

개요

이 문서는 AddressSanitizer(ASan)의 실행 오버헤드를 줄이기 위한 다양한 최적화 기법들을 정리한 문서이다.

ASan은 heap, stack, global object에 대한 out-of-bounds access와 heap use-after-free를 효과적으로 검출하지만, 각 memory access마다 shadow memory를 확인하는 check를 삽입하므로 실행 시간 오버헤드가 크다.

Removing Unsatisfiable Checks

이 범주는 프로그램 의미론 상 절대로 실패할 수 없는 ASan check를 제거하는 방식이다.

ASan check는 기본적으로 어떤 주소 [math]\displaystyle{ addr }[/math]에 접근하기 전에 그 주소에 대응되는 shadow byte를 확인한다. 그런데 접근 대상 object의 크기와 offset, access size가 모두 정적으로 계산 가능하고, 모든 경로에서 범위 내 접근임이 보장되면 shadow를 확인할 이유가 없다. 이런 check는 남겨 두어도 항상 통과하기만 하므로 순수 오버헤드가 된다.

일반적으로 다음 조건이 모든 실행 경로에서 성립하면 제거 가능하다.

[math]\displaystyle{ offset \ge 0 }[/math]
[math]\displaystyle{ offset + access\_size \le object\_size }[/math]

예를 들어 다음 코드는 접근 위치가 완전히 정적으로 결정된다.

int foo() {
    char buf[20];
    buf[10] = 0;
}

이 최적화는 특히 다음과 같은 경우에 잘 적용된다.

stack object에 대한 상수 인덱스 접근
global array에 대한 정적 인덱스 접근
구조체 필드 접근처럼 layout이 compile time에 확정되는 경우
inlining과 constant propagation 이후 값이 상수로 환원되는 경우

반대로 다음과 같은 경우는 조심해야 한다.

pointer arithmetic 결과가 외부 입력에 의존하는 경우
heap object 크기가 정적으로 불명확한 경우
alias를 통해 실제 object 경계가 바뀔 수 있는 경우
signed/unsigned cast 때문에 정적 범위 추론이 깨지는 경우

LLVM Backward tracing

실제 코드에서는 인덱스가 항상 상수로 직접 나타나지 않는다. 따라서 단순히 배열 첨자에 상수가 들어갔는가만 보면 많은 기회를 놓친다. 이를 보완하는 방식이 backward tracing이다.

int foo() {
    char buf[20];
    unsigned int i = 10;
    i++;
    buf[i] = 0;
}

표면적으로는 i가 변수이므로 동적 접근처럼 보인다. 하지만 SSA 기반 IR에서 보면 최종 값은 [math]\displaystyle{ 11 }[/math]로 환원 가능하다. 즉, 컴파일러가 정의-사용 사슬을 거슬러 올라가며 값을 역추적하면 이 접근 역시 항상 안전하다고 판단할 수 있다.

이 과정에서 주로 필요한 분석은 다음과 같다.

SSA 기반 value propagation
constant folding
backward slicing
simple range analysis
dead path pruning

예를 들어 다음과 같은 패턴도 같은 부류이다.

int foo() {
    int idx = 4;
    int j = idx * 2;
    char buf[16];
    buf[j] = 1;
    return 0;
}

여기서 j = 8로 환원되므로 check를 제거할 수 있다.

Removing Recurring Checks

이 범주는 서로 다른 위치에 삽입된 ASan check들이 논리적으로 같은 안전성 조건을 중복해서 확인하는 경우, 뒤의 check를 제거하는 방식이다.

핵심 질문은 다음과 같다.

이 check가 검사하는 주소는 이전에 검사한 주소와 같은가
이전 check가 더 넓은 범위를 이미 검사했는가
control-flow 상 이전 check 이후에 대상 pointer나 object 상태가 바뀌지 않는가

가장 단순한 예시는 같은 pointer를 짧은 구간 안에서 반복 접근하는 경우이다.

int *p;
ASan(p);

if (*p == 0) {
    ASan(p);
    *p = 1;
}

두 번째 check는 첫 번째 check와 완전히 같은 대상에 대해 같은 조건을 다시 확인한다. 첫 번째 check 이후에 p가 바뀌지 않고, free가 발생하지 않고, 더 좁아진 memory object로 바뀌지도 않았다면 두 번째 check는 redundant하다.

보다 일반적으로는 다음 조건이 필요하다.

두 접근이 must-alias 관계
앞선 check가 동일하거나 더 넓은 범위를 검사
앞선 check가 뒤 check를 dominance 또는 post-dominance 관계로 덮음
두 check 사이에 pointer/object 상태를 깨뜨릴 수 있는 연산이 없음

예를 들어 폭이 다른 access에도 같은 논리가 적용될 수 있다.

char *p;
ASan_8B(p);
x = *(long long *)p;
ASan_1B(p);
y = *p;

앞의 8-byte check가 성공했다면 그 범위 안에 포함되는 1-byte access를 다시 검사할 필요가 없는 경우가 있다. 물론 이는 두 access가 같은 object 내에 있고 중간에 상태 변화가 없을 때만 성립한다.

이 최적화는 특히 다음 상황에서 효과적이다.

같은 필드를 여러 번 load/store하는 코드
optimizer가 값을 레지스터로 들고 있지 못해 메모리 재접근이 반복되는 경우
C++ method chain이나 inline expansion으로 같은 base pointer 검사 코드가 복제되는 경우
sanitizer slow path를 피하기 위해 원래부터 보수적으로 많은 check가 들어간 경우

하지만 제거가 위험한 경우도 많다.

함수 호출이 사이에 있으면 callee가 free를 수행할 수 있다
unknown store가 object metadata를 바꿀 수 있다
pointer recast나 integer-to-pointer 변환이 있으면 alias 보장이 약해진다
signal, longjmp, exceptional control flow 등 비정상 흐름이 있으면 보수적으로 남겨야 한다

따라서 필요한 분석은 다음과 같다.

alias analysis
dominance/post-dominance analysis
escape analysis
interprocedural mod/ref analysis
call effect summary

이 계열의 최적화는 check 수를 줄이는 효과가 직접적이며, 특히 대형 C/C++ 프로그램에서 같은 base pointer에 대한 repeated field access가 많기 때문에 체감 효과가 크다.^[1]^[2]

Optimizing Neighbor Checks

이 범주는 인접한 memory access들이 shadow memory 수준에서는 거의 같은 검사를 수행한다는 점을 이용해, 여러 check를 병합하거나 일부를 제거하는 방식이다.

ASan은 보통 주소를 8:1 shadow mapping으로 변환해 shadow byte를 읽는다. 따라서 주소가 서로 가깝다면 결국 같은 shadow byte 또는 인접한 몇 개의 shadow byte만 확인하게 된다. 이때 source-level access는 여러 개여도 shadow-level 정보는 거의 중복일 수 있다.

Mergeable Neighbor Checks

서로 인접한 access가 같은 shadow 영역에 속하면, 여러 개의 ASan check를 하나의 묶음 검사로 합칠 수 있다.

예를 들어 다음과 같은 구조체 field access를 생각할 수 있다.

struct S {
    int a;
    int b;
};

void foo(struct S *ptr) {
    ptr->a = 1;
    ptr->b = 2;
}

일반적인 instrumentation은 다음처럼 각 access마다 독립 check를 넣는다.

ASan(ptr->a)
ASan(ptr->b)

하지만 a와 b가 메모리상 연속해 있고 같은 shadow block 또는 매우 가까운 shadow block을 사용한다면, 두 access를 위해 shadow를 두 번 읽는 것은 낭비다. 이때 다음과 같은 병합이 가능하다.

먼저 더 큰 범위의 shadow 상태를 한 번 확인
fast path에서는 두 access를 모두 safe로 간주
slow path에서만 원래의 세밀한 개별 check로 분기

즉, 논리는 넓게 한 번 보고, 이상이 있을 때만 자세히 본다이다.

이 방식은 다음 이점을 준다.

shadow load 수 감소
conditional branch 수 감소
instruction cache pressure 감소
같은 base address 계산의 중복 감소

다만 병합 가능한지는 다음에 좌우된다.

두 access의 상대 위치가 정적으로 알려져 있는가
병합한 범위가 false negative 없이 원래 두 check를 커버하는가
alignment와 access width 차이 때문에 coarse check가 지나치게 커지지 않는가

Removable Neighbor Checks

인접 access 중 일부는 주변 access만으로도 오류가 검출되므로 완전히 제거할 수 있다.

ptr->a = ...;
ptr->b = ...;
ptr->c = ...;

여기서 ptr->b가 가리키는 위치에서 위반이 발생한다면, 그 위반이 구조상 반드시 ptr->a 또는 ptr->c의 check에서도 드러나는 경우가 있다. 이 경우 ptr->b check는 새로운 오류 검출 능력을 추가하지 않는다.

이 최적화는 직관적으로는 애매해 보이지만, 핵심은 이 access가 독립적인 정보량을 제공하는가이다. 만약 가운데 access가 주변 access들의 union으로 커버되는 memory safety boundary 안에 있다면 중간 check는 제거 가능하다.

대표적으로 다음 상황에서 기회가 생긴다.

packed struct field access
compiler가 분해한 memcpy/memset의 이웃 store들
vectorized access가 scalar access로 다시 쪼개진 경우
small-width field들이 연달아 접근되는 경우

이 범주의 최적화는 correctness 조건이 섬세하므로 보통 보수적으로 적용한다. 잘못 적용하면 false negative가 생기기 때문이다.

Optimizing Checks in Loops

loop 내부 check는 ASan overhead의 핵심 원인 중 하나다. 루프는 본질적으로 같은 패턴의 access를 대량 반복하므로, per-iteration instrumentation은 비용이 눈덩이처럼 커진다.

이 범주의 핵심은 다음 두 가지다.

loop를 도는 동안 변하지 않는 것은 밖으로 빼기
반복되는 접근을 chunk 단위로 묶기

Loop-invariant Checks

루프 안에서 같은 주소를 계속 접근한다면 매 iteration마다 ASan check를 할 필요가 없다.

for (int i = 0; i < N; i++) {
    ASan(ptr);
    *ptr = i;
}

이 코드는 실제로는 같은 위치 ptr를 반복해서 쓴다. 따라서 다음처럼 바꿀 수 있다.

ASan(ptr);
for (int i = 0; i < N; i++) {
    *ptr = i;
}

이 최적화는 일반 loop-invariant code motion과 유사하지만, 중요한 차이가 있다. 원래 store 자체는 side effect 때문에 루프 밖으로 뺄 수 없더라도, check는 뺄 수 있다는 점이다.

적용 조건은 다음과 같다.

루프 반복 동안 대상 주소가 변하지 않음
루프 안에서 free/unmap/reallocation 같은 상태 변화가 없음
signal-like 비정상 흐름으로 memory validity가 바뀌지 않음
hoisted check가 루프 내 모든 access를 sound하게 대표함

이 최적화는 특히 작은 loop body에서 효과가 크다. 원래 check가 차지하던 비중이 커서, hoisting만으로도 branch와 shadow access 수가 크게 줄어든다.

Grouped Checks in Loops

loop가 연속된 주소를 차례로 접근한다면, 각 iteration마다 check하는 대신 몇 개 iteration을 묶어서 검사할 수 있다.

for (int i = 0; i < N; i++) {
    ASan(ptr + i);
    ptr[i] = i;
}

이 경우 ptr + i는 연속 증가 주소다. ASan shadow mapping의 granularity를 생각하면, 여러 iteration이 같은 shadow chunk를 공유할 수 있다. 따라서 매번 check하는 대신 다음처럼 바꿀 수 있다.

현재 iteration이 속한 shadow chunk를 확인
그 chunk 범위 안에서는 추가 check 생략
chunk 경계를 넘을 때만 다시 검사

즉, per-access check를 per-chunk check로 바꾸는 것이다.

이 방식이 성립하려면 보통 다음이 필요하다.

contiguous access 또는 고정 stride access
induction variable이 명확함
access width가 일정하거나 상한이 추론 가능함
redzone boundary를 정확히 고려할 수 있음

예를 들어 [math]\displaystyle{ 8:1 }[/math] shadow mapping에서 1-byte store가 연속해서 8번 일어나면, 이 8개의 access는 같은 shadow byte 상태와 연관될 수 있다. 이때 매번 shadow를 읽지 않고 한 번만 읽어도 충분한 경우가 많다.

실제 구현 시 고려해야 할 문제는 다음과 같다.

마지막 iteration에서 chunk를 부분적으로만 쓰는 경우
loop peeling/unrolling 후 원래 induction 관계가 바뀌는 경우
vectorized loop와 scalar remainder loop를 별도로 처리해야 하는 경우
stride가 1이 아니라 2, 4, 8인 경우 coverage 계산이 달라지는 경우

이 범주의 최적화는 대규모 array processing, codec, parser, numeric kernel처럼 loop가 긴 코드에서 특히 효과적이다.^[3]

Redesigning ASAN Checks

References

↑ SANRAZOR: Reducing Redundant Sanitizer Checks in C/C++ Programs. OSDI 2021.
↑ Debloating Address Sanitizer. USENIX Security 2022.
↑ Debloating Address Sanitizer. USENIX Security 2022.

[1] SANRAZOR: Reducing Redundant Sanitizer Checks in C/C++ Programs. OSDI 2021.

[2] Debloating Address Sanitizer. USENIX Security 2022.

[3] Debloating Address Sanitizer. USENIX Security 2022.

[1]

[2]

[3]