noriwiki - 최근 바뀜 [ko]

Data Flow Analysis

Ahn9807 — Wed, 25 Mar 2026 08:20:51 GMT

새 문서: 분류:프로그램 분석 == 개요 == '''Data Flow Analysis'''는 프로그램의 각 지점(program point)에서 변수나 메모리 상태에 대한 정보를 계산하는 정적 분석 기법이다. 이 분석은 프로그램을 실행하지 않고도, 가능한 모든 실행 경로를 고려하여 변수의 값, 상태, 혹은 속성(property)을 추론하는 것을 목표로 한다. 특히, Data Flow Analysis는 프로그램을 '''Control Flow Graph (CFG)'''로 변...

새 문서

[[분류:프로그램 분석]]

== 개요 ==
'''Data Flow Analysis'''는 프로그램의 각 지점(program point)에서 변수나 메모리 상태에 대한 정보를 계산하는 정적 분석 기법이다. 이 분석은 프로그램을 실행하지 않고도, 가능한 모든 실행 경로를 고려하여 변수의 값, 상태, 혹은 속성(property)을 추론하는 것을 목표로 한다.

특히, Data Flow Analysis는 프로그램을 '''Control Flow Graph (CFG)'''로 변환한 뒤, 각 노드에서의 상태를 정의하고, 이 상태가 CFG를 따라 어떻게 전달(propagate)되는지를 반복적으로 계산하는 방식으로 동작한다. 이 과정에서 각 지점의 상태는 단순한 값이 아니라 '''추상화된 정보(abstract value)'''로 표현되며, 이는 실제 실행 시 발생할 수 있는 여러 경우를 하나로 요약한 것이다. DFA는 실제 값 대신 추상 도메인 위에서 계산을 수행함으로써, 현실적인 비용 내에서 프로그램의 전반적인 특성을 파악할 수 있도록 한다.

== Motivation & Importance ==
Data Flow Analysis는 다음과 같은 이유로 매우 중요한 기술이다.

* '''컴파일러 최적화'''
** Constant propagation: 변수의 값이 상수로 확정되는 경우 이를 전파하여 연산 제거
** Dead code elimination: 사용되지 않는 코드 제거
** Redundant computation 제거

* '''버그 탐지 및 검증'''
** 초기화되지 않은 변수 사용
** Null pointer dereference
** Use-after-free와 같은 메모리 오류

* '''보안 분석'''
** 데이터가 신뢰되지 않은 입력으로부터 왔는지 추적 (taint analysis)
** 권한 상승이나 정보 유출 가능성 분석

기존의 동적 분석은 특정 실행 경로에 대해서만 정보를 얻을 수 있지만, Data Flow Analysis는 '''모든 가능한 실행 경로를 동시에 고려'''하기 때문에, 보다 안전하고 보수적인 결과를 제공한다. 이에, Data Flow Analysis는 다양한 정적 분석 및 검증 시스템의 기반이 된다.

== Challenge ==
Data Flow Analysis를 설계하고 구현하는 데에는 여러 가지 어려움이 존재한다.

#'''경로의 폭발(Path Explosion)''': 프로그램에는 조건문과 반복문이 존재하기 때문에, 가능한 실행 경로의 수가 기하급수적으로 증가한다. 이를 그대로 추적하는 것은 현실적으로 불가능하다.
#'''정보 병합(Merge) 문제''':여러 경로에서 동일한 프로그램 지점으로 도달할 경우, 각 경로의 상태를 하나로 합쳐야 한다. 이때 정보를 어떻게 보존하면서도 간결하게 표현할지가 중요하다.
#'''정밀도 vs 성능''':더 정밀한 분석을 위해서는 더 많은 상태를 유지해야 하지만, 이는 계산 비용 증가로 이어진다. 반대로 단순화하면 빠르지만 부정확해진다.
# '''루프와 고정점''': 루프가 존재하면 상태가 반복적으로 변화하게 되므로, 언제 계산을 멈출지 결정해야 한다. 이를 위해 '''고정점(Fixed Point)''' 개념이 사용된다.

이를 해결하기 위해서 '''lattice 구조와 monotonic transfer function'''을 사용하여 반드시 수렴하도록 DFA를 설계하는 것이 기본이다.

== Background ==

=== [[Control Flow Graph]] (CFG) ===
프로그램의 실행 흐름을 그래프로 나타낸 구조이다.

* 노드: basic block (연속된 명령어의 집합)
* 간선: 제어 흐름 (branch, jump, function call 등)

CFG는 Data Flow Analysis의 기반이 되며, 모든 상태 전파는 이 그래프 위에서 이루어진다.

=== [[Abstract Domain]] ===
실제 값을 그대로 사용하는 대신, 이를 추상화한 값으로 표현한다.

예:
* 정수 값 → {constant c, non-constant, unknown}
* 변수 상태 → {initialized, uninitialized}
* 포인터 상태 → {null, non-null, unknown}

이러한 추상화는 여러 실행 경로를 하나의 상태로 요약하기 위해 필요하다.

=== Lattice ===
[[파일:Data Flow Analysis Lattice.png|섬네일|오른쪽]]
Abstract Domain은 일반적으로 '''lattice 구조'''를 가진다.

* 각 상태는 부분 순서(partial order)로 비교 가능
* join 연산을 통해 여러 상태를 결합 가능
* bottom: 정보 없음 (초기 상태)
* top: 모든 가능성을 포함 (가장 보수적 상태)

여기서 [[Partial Order]]는 다음과 같은 Order체계를 의미한다.
join(a, b) ⩾ a and join(a, b) ⩾ b and join(x, x) = x

이 구조 덕분에 반복 계산이 항상 수렴하게 된다.

=== Transfer Function ===
각 프로그램 문장이 상태를 어떻게 변화시키는지를 정의한다.

예:
<syntaxhighlight lang=c>
x = y + 1;
</syntaxhighlight>

* y가 constant이면 → x도 constant
* y가 unknown이면 → x도 unknown

Transfer function은 '''monotonic'''해야 하며, 이는 분석이 안정적으로 수렴하기 위한 조건이다.

=== Join Operation ===
여러 경로에서 온 상태를 하나로 합치는 연산이다.

예:
<syntaxhighlight lang=c>
if (cond) x = 1;
else x = 2;
</syntaxhighlight>

→ x ∈ {1, 2}

Join은 정보 손실을 동반할 수 있으며, 이는 분석의 보수성을 증가시킨다.

== Main Idea ==
Data Flow Analysis의 핵심 아이디어는 다음과 같다.

* 프로그램의 각 지점에 대해 상태를 정의하고
* 이 상태를 CFG를 따라 반복적으로 전파하며
* 더 이상 상태가 변하지 않을 때까지 계산한다

이 과정을 '''고정점 계산(Fixed Point Computation)'''이라고 한다.

초기에는 모든 상태를 bottom으로 시작하고, transfer function과 join을 반복 적용하면서 점점 더 많은 정보를 포함하게 된다. 이 과정은 lattice의 구조 덕분에 반드시 수렴한다.

LLVM 문서에서는 이러한 반복 계산을 통해, 각 프로그램 지점에서의 '''sound한(over-approximate) 결과'''를 얻을 수 있다고 설명한다.

== Design ==

=== Worklist Algorithm ===
실제 구현에서는 '''worklist 알고리즘'''이 사용된다.

* 초기 상태 설정
* 변경이 발생한 노드를 worklist에 추가
* 하나씩 꺼내어 transfer function 적용
* 결과가 변하면 후속 노드를 다시 worklist에 추가

이 방식은 불필요한 계산을 줄이면서 효율적으로 고정점에 도달하도록 한다.

=== Forward vs Backward Analysis ===
* Forward analysis
** 프로그램 시작 → 끝 방향
** 예: constant propagation

* Backward analysis
** 프로그램 끝 → 시작 방향
** 예: liveness analysis

분석 목적에 따라 방향이 결정된다.

=== May vs Must Analysis ===
* May analysis
** 어떤 경로에서라도 가능하면 포함
** 보수적 (over-approximation)

* Must analysis
** 모든 경로에서 반드시 성립해야 포함
** 더 엄격하지만 정보가 줄어들 수 있음

=== Flow-sensitive vs Flow-insensitive ===
* Flow-sensitive: 프로그램 순서를 고려
* Flow-insensitive: 순서를 무시하고 전체를 하나로 분석

LLVM 문서에서는 주로 flow-sensitive 분석을 기반으로 설명한다.

== Result ==
Data Flow Analysis를 통해 다음과 같은 정보를 얻을 수 있다.

* 각 프로그램 지점에서 변수의 가능한 값 또는 상태
* 안전한 최적화 수행 가능
* 프로그램의 잠재적 오류 탐지

특히, 이 분석은 실제 실행 없이도 '''모든 가능한 실행 경로를 고려한 결과'''를 제공하며, 이는 정적 분석의 핵심적인 장점이다.

또한 결과는 '''over-approximation'''이므로, 실제로는 발생하지 않는 경우도 포함될 수 있지만, 반대로 중요한 오류를 놓치지 않는다는 장점이 있다.

== Contribution (Conclusion) ==
Data Flow Analysis는 다음과 같은 기여를 한다.

* 프로그램 분석을 위한 일반적인 프레임워크 제공 (CFG + lattice + fixed point)
* 다양한 최적화 및 정적 분석 기법의 기반
* 추상 해석을 통해 현실적인 비용으로 전체 프로그램 분석 가능

LLVM 문서에서 설명하듯이, 이 프레임워크는 다양한 분석 문제에 재사용 가능하며, 새로운 분석을 설계할 때도 동일한 구조를 활용할 수 있다.

== Criticize (Conclusion) ==
다음과 같은 한계가 존재한다.

* '''False positive'''
보수적 분석으로 인해 실제로는 발생하지 않는 오류도 탐지됨

* '''정밀도 한계'''
추상화 과정에서 정보 손실 발생

* '''성능 문제'''
복잡한 프로그램에서는 분석 비용 증가

* '''모델링 한계'''
실제 실행 환경(예: 시스템 호출, 외부 입력)을 완전히 반영하기 어려움

그럼에도 불구하고, Data Flow Analysis는 현대 컴파일러와 보안 분석에서 필수적인 핵심 기술이며, LLVM과 같은 시스템에서도 핵심 기반으로 활용되고 있다.

== References ==
# https://clang.llvm.org/docs/DataFlowAnalysisIntro.html

파일:Data Flow Analysis Lattice.png

Ahn9807 — Wed, 25 Mar 2026 05:59:43 GMT

Ahn9807님이 파일:Data Flow Analysis Lattice.png 파일을 올렸습니다

새 문서

https://clang.llvm.org/docs/DataFlowAnalysisIntro.html

AddressSanitizer Optimization

Ahn9807 — Mon, 23 Mar 2026 07:11:34 GMT

새 문서: 분류:AddressSanitizer 분류:Program Analysis 분류:Optimization == 개요 == 이 문서는 AddressSanitizer(ASan)의 실행 오버헤드를 줄이기 위한 다양한 최적화 기법들을 정리한 문서이다. ASan은 heap, stack, global object에 대한 out-of-bounds access와 heap use-after-free를 효과적으로 검출하지만, 각 memory access마다 shadow memory를 확인하는 check를 삽입하므로 실행 시간 오버헤드가 크다. == Remo...

새 문서

[[분류:AddressSanitizer]]
[[분류:Program Analysis]]
[[분류: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>addr</math>에 접근하기 전에 그 주소에 대응되는 shadow byte를 확인한다. 그런데 접근 대상 object의 크기와 offset, access size가 모두 정적으로 계산 가능하고, 모든 경로에서 범위 내 접근임이 보장되면 shadow를 확인할 이유가 없다. 이런 check는 남겨 두어도 항상 통과하기만 하므로 순수 오버헤드가 된다.

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

* <math>offset \ge 0</math>
* <math>offset + access\_size \le object\_size</math>

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

<syntaxhighlight lang=c>
int foo() {
char buf[20];
buf[10] = 0;
}
</syntaxhighlight>

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

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

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

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

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

<syntaxhighlight lang=c>
int foo() {
char buf[20];
unsigned int i = 10;
i++;
buf[i] = 0;
}
</syntaxhighlight>

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

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

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

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

<syntaxhighlight lang=c>
int foo() {
int idx = 4;
int j = idx * 2;
char buf[16];
buf[j] = 1;
return 0;
}
</syntaxhighlight>

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

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

핵심 질문은 다음과 같다.

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

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

<syntaxhighlight lang=c>
int *p;
ASan(p);

if (*p == 0) {
ASan(p);
*p = 1;
}
</syntaxhighlight>

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

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

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

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

<syntaxhighlight lang=c>
char *p;
ASan_8B(p);
x = *(long long *)p;
ASan_1B(p);
y = *p;
</syntaxhighlight>

앞의 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가 많기 때문에 체감 효과가 크다.<ref>SANRAZOR: Reducing Redundant Sanitizer Checks in C/C++ Programs. OSDI 2021.</ref><ref>Debloating Address Sanitizer. USENIX Security 2022.</ref>

== 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를 생각할 수 있다.

<syntaxhighlight lang=c>
struct S {
int a;
int b;
};

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

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

* <code>ASan(ptr->a)</code>
* <code>ASan(ptr->b)</code>

하지만 <code>a</code>와 <code>b</code>가 메모리상 연속해 있고 같은 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만으로도 오류가 검출되므로 완전히 제거할 수 있다.

<syntaxhighlight lang=c>
ptr->a = ...;
ptr->b = ...;
ptr->c = ...;
</syntaxhighlight>

여기서 <code>ptr->b</code>가 가리키는 위치에서 위반이 발생한다면, 그 위반이 구조상 반드시 <code>ptr->a</code> 또는 <code>ptr->c</code>의 check에서도 드러나는 경우가 있다. 이 경우 <code>ptr->b</code> 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를 할 필요가 없다.

<syntaxhighlight lang=c>
for (int i = 0; i < N; i++) {
ASan(ptr);
*ptr = i;
}
</syntaxhighlight>

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

<syntaxhighlight lang=c>
ASan(ptr);
for (int i = 0; i < N; i++) {
*ptr = i;
}
</syntaxhighlight>

이 최적화는 일반 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을 묶어서 검사할 수 있다.

<syntaxhighlight lang=c>
for (int i = 0; i < N; i++) {
ASan(ptr + i);
ptr[i] = i;
}
</syntaxhighlight>

이 경우 <code>ptr + i</code>는 연속 증가 주소다. 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>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가 긴 코드에서 특히 효과적이다.<ref>Debloating Address Sanitizer. USENIX Security 2022.</ref>

== Redesigning ASAN Checks ==

== References ==

Principles and Methodologies for Serial Performance Optimization

Ahn9807 — Thu, 19 Mar 2026 02:23:09 GMT

← 이전 판		2026년 3월 19일 (목) 02:23 판
46번째 줄:		46번째 줄:

	== [[Conclusion]] ==		== [[Conclusion]] ==
	이 논문은 Memory allocator optimization을 많이 해 왔던 나의 경험에 비추어서, 평소 생각하고 있었던 Implementation의 Optimization step-by-step solution의 가려운 부분을 긁어준 매우 재미있는 논문이었다. 나중에도 만약 Optimization할일이 있다면, 이 논문에서 제공하는 여러 원리와 방법론들을 참고 하면서 (혹은 GPT에 이 논문을 넣고 해줘 하면서...), checklist를 참고할 수 있을 것 같다는 생각이든다. 논문의 흐름도 매우 매끄럽고, 이해하는데 어려움이 없었지만, 몇몇 설명들은 설명의 Completness를 위해서인지 조금 쉬운 내용을 어렵게 설명하는 느낌이 (E.g., Section 2.1 Principles for performance optimization)있었다. 그리고 원리의 3가지 요소들은 서로 중복되는 면이 없지 않는가 하는 생각이 ~~들어쓴ㄴ데~~		이 논문은 Memory allocator optimization을 많이 해 왔던 나의 경험에 비추어서, 평소 생각하고 있었던 Implementation의 Optimization step-by-step solution의 가려운 부분을 긁어준 매우 재미있는 논문이었다. 나중에도 만약 Optimization할일이 있다면, 이 논문에서 제공하는 여러 원리와 방법론들을 참고 하면서 (혹은 GPT에 이 논문을 넣고 해줘 하면서...), checklist를 참고할 수 있을 것 같다는 생각이든다. 논문의 흐름도 매우 매끄럽고, 이해하는데 어려움이 없었지만, 몇몇 설명들은 설명의 Completness를 위해서인지 조금 쉬운 내용을 어렵게 설명하는 느낌이 (E.g., Section 2.1 Principles for performance optimization)있었다. 그리고 원리의 3가지 요소들은 서로 중복되는 면이 없지 않는가 하는 생각이 들었다.

Principles and Methodologies for Serial Performance Optimization

Ahn9807 — Thu, 19 Mar 2026 02:22:23 GMT

새 문서: 분류:USENIX OSDI {{Paper|title=Principles and Methodologies for Serial Performance Optimization|author=Sujin Park, Mingyu Guan, Xiang Cheng, Taesoo Kim Georgia Institute of Technology|year=2025|conference=USENIX OSDI 19}} == 개요 == 이 논문은 시스템 성능 최적화에 초점을 맞추고, 이를 체계적으로 최적화하기 위한 framework를 제안한다. 기존에는 성능 최적화가 경험과 직관에 의존했으나, 본 논문은 이를 구조화된...

새 문서

[[분류:USENIX OSDI]]
{{Paper|title=Principles and Methodologies for Serial Performance Optimization|author=Sujin Park, Mingyu Guan, Xiang Cheng, Taesoo Kim
Georgia Institute of Technology|year=2025|conference=USENIX OSDI 19}}

== 개요 ==
이 논문은 시스템 성능 최적화에 초점을 맞추고, 이를 체계적으로 최적화하기 위한 framework를 제안한다. 기존에는 성능 최적화가 경험과 직관에 의존했으나, 본 논문은 이를 구조화된 문제로 정의한다.

핵심적으로, sequential task sequence를 최적화하는 세 가지 원리 (removal, replacement, reordering)를 정의하고, 이를 기반으로 8가지 방법론 (batching, caching, precomputing, deferring, relaxation, contextualization, hardware specialization, layering)을 제시한다.

또한, 지난 10년간 OSDI/SOSP 논문 477편을 분석하여, 해당 8가지 방법론이 실제 성능 최적화 기법을 거의 모두 설명할 수 있음을 보인다. 추가적으로 SysGPT라는 fine-tuned LLM을 통해 자동화된 최적화 제안 가능성을 실험적으로 보여준다.

== Motivation & Importance ==
=== 문제 정의 ===
시스템 성능 향상의 핵심은 latency 감소와 throughput 증가이다. 이는 유저 경험에 큰 영향을 미치고, '''사실 논문 작성을 위한 Implementation'''에서도 대부분의 시간을 차지하는 중요한 작업이다. 여기서 Optimization의 중요한 좀은, Sequential portion이 전체 성능의 bottleneck이 된다는 점이다. 이는 [[암달의 법칙]](Amdahl’s law)으로도 잘 알려져 있다.

기존 연구들은 체계적인 방법론이 아니라 optimization이 경험 기반(heuristic)이기 떄문에, 이러한 경험을 확장시키지 못하였다. 본 논문은 Optimization을 하나의 체계화된 구조로 정리하여서, 쉽게 프로그램의 Serial part를 최적화 할 수 있도록 하였다.

== Main Idea ==
문헌 조사를 통해서 기존에는 모호하거나 구전되던 여러 방법들을 3개의 원리와 8개의 방법론으로 분류 하였다.

== Design ==
[[파일:USENIX OSDI 2025 Sujin, Park Table 1.png|프레임|가운데]]
=== 3가지의 원리 ===
* Removal (<math>P_{rm}</math>): 수행해야 하는 Instruction의 개수를 줄여서 optimization하는 방법이다.
* Replacement (<math>P_{rep}</math>): 기존에 수행되던 Instruction을 더 빠른 방식 또는 더 효율적인 알고리즘으로 대체하여 전체 실행 비용을 줄이는 방법이다.
* Reordering (<math>P_{ord}</math>): Instruction 또는 Task의 실행 순서를 변경하여 dependency를 유지하면서도 latency를 줄이거나 병목 구간을 완화하는 방법이다.

=== 8가지 Methodologies ===
# Batching [Rm, Rep, Ord]: 여러 태스크들을 묶어서 처리하여 각 태스크에 존재하는 중복 비용을 제거하고 ('''Rm'''), 묶음 단위로 더 효율적인 처리 방식으로 대체하며 ('''Rep'''), 실행 순서를 조정하여 locality를 향상시키는 ('''Ord''') 기법이다.
# Caching [Rep]: 이전에 수행된 연산 결과를 저장해두고 재사용함으로써, 동일한 연산을 반복 수행하는 알고리즘을 대체하는 ('''Rep''') 기법이다.
# Precomputing [Rm, Ord]: 실행 경로 상에서 수행될 연산을 미리 계산하여 runtime의 critical path에서 해당 작업을 제거하고 ('''Rm'''), 실행 시점을 앞당겨 순서를 변경하는 ('''Ord''') 기법이다.
# Deferring [Ord -> Rm,Ord]: 즉시 수행할 필요가 없는 작업을 나중으로 미루어 실행 순서를 변경하고 ('''Ord'''), batching이나 추가적인 최적화 기회를 확보하는 기법이다.
# Relaxation [Rep, Rm]: 정확성이나 일관성의 일부를 희생하는 대신, 더 단순하고 빠른 연산으로 대체하여 실행 비용을 줄이거나 ('''Rep''') 아니면 생략 하는 ('''Rm''') 기법이다.
# Contextualization [Rep, Ord]: runtime 상황이나 workload 특성에 맞게 실행 방식을 더 적합한 방식으로 대체하는 ('''Rep''') 방식이다.
# Hardware Specialization [Rep]: 특정 하드웨어의 특성을 활용하여 기존 연산을 더 빠른 하드웨어 기반 처리로 대체하는 ('''Rep''') 기법이다.
# Layering [Rm, Rep]: 시스템 계층을 제거하거나 우회하여 불필요한 작업을 제거하고 ('''Rm'''), 하나의 레이어를 여러개의 레이어로 나누어서 상호의존성을 줄이는 ('''Rep''') 기법이다.

=== Methodology 특징 ===
* 여러 방법이 동시에 사용됨 (평균 2.01개)
* 서로 결합되어 효과 증폭

== Result ==
=== Empirical Study ===
* OSDI/SOSP 477개 논문 분석
* 206개 performance 논문 모두 8가지 방법론으로 설명 가능 (특히 논문에서 제일 재밌는 파트였는데, 기존의 내가 알고 있던 논문들의 Design들이 제시한 Optimization기법으로 설명된다는 것을 보며, 논문을 읽으면서 들었던 생각인, 어쩌면 중복되는 아이디어가 많다는 생각이 여기서 나온 것은 아닌 가 하는 생각이 들었다. 따라서 Implementation이든 Design이든 새로운 시스템 아이디어를 구현한다는 것은 어떻게 기존 시스템을 보다 최적화 할 수 있다는 것에 있음을 보며, 적절한 Optimization기법을 효과적으로 사용하는 방법을 배우는 과정이라는 생각이 들었다.)

== [[Conclusion]] ==
이 논문은 Memory allocator optimization을 많이 해 왔던 나의 경험에 비추어서, 평소 생각하고 있었던 Implementation의 Optimization step-by-step solution의 가려운 부분을 긁어준 매우 재미있는 논문이었다. 나중에도 만약 Optimization할일이 있다면, 이 논문에서 제공하는 여러 원리와 방법론들을 참고 하면서 (혹은 GPT에 이 논문을 넣고 해줘 하면서...), checklist를 참고할 수 있을 것 같다는 생각이든다. 논문의 흐름도 매우 매끄럽고, 이해하는데 어려움이 없었지만, 몇몇 설명들은 설명의 Completness를 위해서인지 조금 쉬운 내용을 어렵게 설명하는 느낌이 (E.g., Section 2.1 Principles for performance optimization)있었다. 그리고 원리의 3가지 요소들은 서로 중복되는 면이 없지 않는가 하는 생각이 들어쓴ㄴ데

파일:USENIX OSDI 2025 Sujin, Park Table 1.png

Ahn9807 — Wed, 18 Mar 2026 12:03:04 GMT

Ahn9807님이 파일:USENIX OSDI 2025 Sujin, Park Table 1.png 파일을 올렸습니다

새 문서

Table 1: Summary of the eight methodologies, detailing their underlying principles, visual representations, necessary conditions, and strategic applications.

Fast Pointer Nullification for Use-After-Free Prevention

Ahn9807 — Wed, 18 Mar 2026 08:03:10 GMT

← 이전 판		2026년 3월 18일 (수) 08:03 판
1번째 줄:		1번째 줄:
	[[~~index.php?title=~~분류:NDSS]]		[[분류:NDSS]]

	{{Paper\|title=Fast Pointer Nullification for Use-After-Free Prevention\|author=Yubo Du University of Pittsburgh yubo.du@pitt.edu Youtao Zhang University of Pittsburgh youtao@pitt.edu Jun Yang University of Pittsburgh juy9@pitt.edu\|conference=NDSS 2026\|year=2026}}		{{Paper\|title=Fast Pointer Nullification for Use-After-Free Prevention\|author=Yubo Du University of Pittsburgh yubo.du@pitt.edu Youtao Zhang University of Pittsburgh youtao@pitt.edu Jun Yang University of Pittsburgh juy9@pitt.edu\|conference=NDSS 2026\|year=2026}}

Fast Pointer Nullification for Use-After-Free Prevention

Ahn9807 — Wed, 18 Mar 2026 08:02:53 GMT

새 문서: index.php?title=분류:NDSS {{Paper|title=Fast Pointer Nullification for Use-After-Free Prevention|author=Yubo Du University of Pittsburgh yubo.du@pitt.edu Youtao Zhang University of Pittsburgh youtao@pitt.edu Jun Yang University of Pittsburgh juy9@pitt.edu|conference=NDSS 2026|year=2026}} == 개요 == Pointer nullification기법은 Use-after-free버그를 효과적으로 막을 수 있지만, 기존의 PN (Pointer nullification)기법들은 메타데이터 Looku...

새 문서

[[index.php?title=분류:NDSS]]

{{Paper|title=Fast Pointer Nullification for Use-After-Free Prevention|author=Yubo Du University of Pittsburgh yubo.du@pitt.edu Youtao Zhang University of Pittsburgh youtao@pitt.edu Jun Yang University of Pittsburgh juy9@pitt.edu|conference=NDSS 2026|year=2026}}

== 개요 ==
[[Pointer nullification]]기법은 [[Use-after-free]]버그를 효과적으로 막을 수 있지만, 기존의 PN (Pointer nullification)기법들은 메타데이터 Lookup에 많은 시간이 사용되기 때문에 효율적으로 사용하기는 어려웠다.

이 논문은 '''Fast Pointer Nullification (FPN)'''이라는 기법을 제안하여, 최적화된 PN을 통해 UAF 탐지 및 방지의 성능을 향상시키는 것을 목표로 한다.

기존 PN의 핵심 병목이었던 metadata lookup을 단순화하고, 공간적 지역성을 활용한 새로운 저장 구조를 통해 성능과 메모리 오버헤드를 동시에 줄인다.

== Motivation & Importance ==
UAF 버그는 dangling pointer가 해제된 메모리를 참조하면서 발생하는 취약점으로, arbitrary code execution 등 심각한 보안 문제로 이어질 수 있다.

이를 방지하기 위한 다양한 기법이 존재하지만, 성능(Performance), 메모리 사용량(Memory consumption), 보안(Security), 호환성(Compatibility) 측면에서 trade-off가 존재한다.

그중 Pointer Nullification (PN)기법은 이러한 trade-off를 비교적 균형 있게 만족하는 방식으로 평가된다.

== Background ==
[[파일:NDSS 2026 FPN Figure 2.png|섬네일|오른쪽]]
Pointer Nullification은 다음과 같은 방식으로 동작한다:

# heap object가 생성될 때 metadata를 생성한다.
# pointer가 특정 object를 가리킬 때, 해당 pointer의 저장 위치를 metadata에 기록한다.
# object가 free될 때, 해당 object를 가리키는 모든 pointer를 찾아 null로 설정한다.

즉, dangling pointer가 생성되는 것을 사전에 제거하여 UAF를 방지하는 방식이다.

하지만 PN 기법에는 다음과 같은 문제가 존재한다:

* pointer → object 관계를 추적하기 위한 metadata lookup 비용이 매우 큼
* CAMP 기준으로 약 62.5%의 성능 오버헤드가 lookup에서 발생
* metadata를 tree/hash 구조로 저장 → cache locality가 매우 나쁨

또한 pointer 저장 위치들은 실제로는 공간적으로 밀집되어 있는 경우가 많음에도 불구하고, 이를 활용하지 못하는 비효율이 존재한다.

== Main Idea ==
이 논문은 Fast Pointer Nullification이라는 기법을 도입하였다.

FPN은 두 가지 핵심 최적화 디자인을 포함한다:

* Constant-time and lightweight metadata address computation: pointer가 속한 metadata 위치를 bit-shift 연산으로 계산하여 O(1) 접근
* Spatial locality 활용: individual pointer storage location 대신 <math>2^M</math> byte-aligned memory block 단위로 관리

즉,
* 기존 PN: pointer 단위 tracking
* FPN: block 단위 tracking

을 통해 metadata lookup과 registration 비용을 동시에 줄인다.

== Challenge ==
* PN 방식은 pointer가 어떤 연결관계를 맺는지를 기억해야 한다. 이 metadata lookup 비용이 매우 크다.
** DangNULL: Red-black tree 사용 → O(log n)
** CAMP: 최적화했지만 여전히 높은 비용
** 전체 성능 오버헤드 중 약 62.50%가 lookup에서 발생
* metadata가 spatial locality를 전혀 반영하지 못한다.
** hash / tree 기반 구조 → 메모리 상에 무작위 배치
** pointer 저장 위치는 실제로 인접한 경우가 많음에도 불구하고 이를 활용하지 못함
** cache miss 증가 및 성능 저하 발생

== Design ==
[[파일:NDSS 2026 FPN Figure 4.png|프레임|가운데]]

FPN은 기존 PN의 동작 구조를 유지하면서 내부 메커니즘을 최적화한다.

여기서 Buffer는 Allocation된 Heap메모리를, Pointer는 그 Buffer를 가르키는 포인터를 의미한다. 예를 들어서 Pointer A = Buffer; 이 있을때, Pointer B = A;면 Pointer A와 Pointer B는 동시에 같은 Buffer B를 가르키고, 과연 어떻게 이러한 종속관계를 빠르게 추적할 수 있는 자료구조를 만들 수 있을지가 이 논문의 핵심이다.

=== Region-based Metadata ===
메모리를 2^N byte 단위 region으로 분할하고 pointer가 속한 region을 다음과 같이 계산한다:

region_id = ptr >> N

각 region은 다음 정보를 포함한다:
* buffer list: 이 리전에 포함된 버퍼들의 리스트를 가지고 있다. 이 리스트는 Buffer info로 관리되며 각 Buffer info는 할당된 메모리들의 Start address와 End address가 있다.
* block list: 이 리전을 가르키는 포인터들이 어떤 Block에 속하는 지에 대한 리스트를 가지고 있다.

이를 통해 metadata lookup을 constant-time으로 수행할 수 있다.

=== Block-based Pointer Registration ===
기존 PN는 pointer 저장 위치를 개별적으로 기록하지만 FPN과 같은 경우는 pointer가 속한 block 단위로 등록한다.

block_addr = store_loc & ~(2^M - 1)

동작:
# pointer → region 계산
# region의 block list 접근
# 최근 block들과 비교하여 중복 제거
# 새로운 block만 등록 (이 Region에는 Block 1과 Block 2에 해당하는 포인터들이 있다. 즉 Possible한 Pointer의 Range를 가지고 있는 것)

효과:
# registration 횟수 감소
# metadata 크기 감소
# cache locality 향상

=== Nullification 과정 ===
object free 시:
# 해당 object가 속한 region 확인
# region의 block list 순회
# 각 block 내 pointer 후보 탐색
# 해당 object를 가리키는 pointer를 null로 설정
# Region에서 Buffer info제거

특징:
* pointer를 정확히 저장하지 않고 block 단위로 탐색
* '''deallocation frequency가 낮기 때문에 overhead는 제한적'''

=== Status Bit (False Positive 방지) ===
문제: block 단위 탐색 시 pointer가 아닌 값까지 nullify될 위험 존재한다.

해결: shadow memory 기반 status bit 사용

status_table[address >> 3]
* pointer 저장 시 bit 설정
* free 시 bit 제거

효과:
* false positive 제거
* 안전한 nullification

== Evaluation ==
=== 성능 및 메모리 오버헤드 ===
: SPEC CPU 2017 기준으로 분석하였을 경우
* 성능 오버헤드: 약 17.78%
* 메모리 오버헤드: 약 8.34%

; 기존 PN 대비 크게 개선된 사항
* CAMP: ~56% performance / ~173% memory
* FreeSentry: 높은 메모리 오버헤드

== [[Conclusion]] ==
FPN은 기존 Pointer Nullification의 핵심 병목이었던 metadata lookup 비용과 pointer registration를 Corased-grained block-based region search로 변경하여 문제를 해결하였다. 그결과, 낮은 성능 및 메모리 오버헤드를 가져올 수 있었다. 논문의 몇몇 가정은 동의하기 힘든 부분도 있었지만, "E.g., Page 5, "ALthough scanning entire blocks during nullification may introduce additional performance overhead, deallocations occur infrequently in most applications", [[BUDAlloc: Defeating Use-After-Free Bugs by Decoupling Virtual Address Management from Kernel|BUDAlloc]]과 [[SwiftSweeper]]를 평가에 반영하였기 때문에 매우 높은 점수를 주고 싶다.

Minor comments:

# Buffer information이 설명없이 그림에만 나와서, 알고리즘을 이해하는데 조금 어려웠다.

Major comments:

# Deallocation frequency가 낮기 때문에 Free성능이 병목이 되지 않는 다고 주장하고 있지만, 이 부분에 대한 명시적인 증거가 필요해 보인다. 추측해 보건데, Deallocation frequency가 낮은 것이 아니라, 단순히 Pointer tracking이 Deallocation시의 Overhead를 감수할만큼 더 많이 Overhead를 줄인 것으로 추측된다.
# Performance overhead관점에서 보았을 경우, FPN은 Pointer nullification의 단점인 Overhead를 확실히 많이 끌어 올린 것은 맞지만, 기존의 FFmalloc과 같은 논문과 비교하여 아직 부족한 부분이 있다. Pointer nullification을 좀더 빠르게 만들 수 있는 방법으로, Block tracking 내부적으로 Hash를 이용하는 방법이나, 아니면 LLVM컴파일러의 도움을 받는 부분도 탐색하면 좋을 것 같다는 생각이 든다.

파일:NDSS 2026 FPN Figure 4.png

Ahn9807 — Wed, 18 Mar 2026 04:56:12 GMT

Ahn9807님이 파일:NDSS 2026 FPN Figure 4.png 파일을 올렸습니다

새 문서

Diagram of FPN and comparisons of pointer registrations between previous PN methods and FPN. To illustrate the points-to relationships more clearly, (a) presents two conceptual views of memory (overlapping with each other): a zoomed-in view highlighting the heap region that heap pointers reference, and a full-memory view showing where these pointers may be stored.

파일:NDSS 2026 FPN Figure 2.png

Ahn9807 — Wed, 18 Mar 2026 03:54:09 GMT

Ahn9807님이 파일:NDSS 2026 FPN Figure 2.png 파일을 올렸습니다

새 문서

NDSS 2026 FPN Figure 2