개요
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
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
각 프로그램 문장이 상태를 어떻게 변화시키는지를 정의한다.
예:
x = y + 1;
- y가 constant이면 → x도 constant
- y가 unknown이면 → x도 unknown
Transfer function은 monotonic해야 하며, 이는 분석이 안정적으로 수렴하기 위한 조건이다.
Join Operation
여러 경로에서 온 상태를 하나로 합치는 연산이다.
예:
if (cond) x = 1;
else x = 2;
→ 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과 같은 시스템에서도 핵심 기반으로 활용되고 있다.