졸업프로젝트의 Ghidra 스크립트를 구현하기 위해 Taint Analysis 방식을 사용한다고 들었다. 이에 따라 선행 개념을 복습하고 Taint Analysis에 대한 개념을 정리해 보려고 한다.
1. Basic Block(BB)
컴파일러가 프로그램을 분석할 때, 가장 먼저 하는 일은 코드를 베이직 블록 단위로 쪼개는 것이다. 베이직 블록은 오직 첫 번째 명령어(Entry)를 통해서만 진입할 수 있고, 마지막 명령어(Exit)를 통해서만 빠져나갈 수 있는 연속된 명령어의 묶음을 뜻한다. 즉 블록의 첫 번째 명령어가 실행되면 마지막 명령어까지 무조건 실행된다는 보장이 있는 안전한 구역이다.
2. Control Flow Analysis와 Data Flow Analysis
컴파일러는 베이직 블록들을 도구 삼아 두 가지 분석을 수행할 수 있다.
2.1. Control Flow Analysis
개별 명령어의 세부 내용은 무시하고, 베이직 블록 자체를 하나의 블랙박스로 취급한다. 오직 블록의 마지막에 있는 분기문(if, jump 등)에만 집중하여, 어떤 블록에서 어떤 블록으로 프로그램의 실행 흐름이 이동하는지를 파악한다. 이를 통해 프로그램의 전체적인 지도를 그리게 되는데, 이것을 제어 흐름 그래프인 Control Flow Graph(CFG)라고 부른다.
2.2 Data Flow Analysis
제어 흐름으로 지도를 그렸다면, 이제는 그 지도 위를 돌아다니는 데이터(변수)들의 생애 주기를 추적할 차례다. 프로그램 내의 데이터가 어디서 생성(정의)되고, 어디서 사용되며, 어디서 소멸(변경)되는지에 대한 정보를 모으는 과정이다. 이때는 베이직 블록이라는 블랙박스를 열고, 그 내부의 명령어들을 자세히 들여다보며 블록 간의 데이터 전달 상태를 파악한다.
3. Reaching Definitions(Data Flow Analysis 예시)
Reaching Definitions란 변수에 값을 할당하는 특정 지점이 프로그램의 다른 지점까지 그 값을 유지한 채 살아서 도달할 수 있는지 파악하는 분석이다.
3.1. Definition과 Reach
어떤 변수에 값을 넣는 행위를 Definition, 즉 정의라고 한다. 특정 정의 d가 프로그램 내의 어떤 위치 p에 도달(Reach)한다는 것은, d가 실행된 직후부터 p에 이르기까지 그 변수의 값이 다른 값으로 덮어씌워지지 않는 경로가 최소 하나 이상 존재한다는 뜻이다.
3.2. kill
만약 두 지점 사이를 잇는 경로에서 동일한 변수에 새로운 값이 할당된다면, 이전의 정의는 효력을 잃고 kill 되었다고 표현한다. 예를 들여 r1 = r2 + r3라는 명령어가 실행되면, 이전에 r1이라는 변수에 어떤 값을 넣었든 그 과거의 정의들은 모두 이 지점에서 kill 된다.
3.3. Reaching Definition 분석
Reaching Definition 분석을 위해 컴파일러는 각 베이직 블록마다 4가지 정보 집합을 계산한다.
- GEN: 해당 베이직 블록 내부에서 새롭게 만들어져서 밖으로 살아나갈 수 있는 정의들의 모음이다.
- KILL: 프로그램 전체의 정의들 중에서, 해당 베이직 블록을 통과하면서 덮어씌워져 죽어버린 정의들의 모음이다.
- IN: 해당 베이직 블록이 시작될 때, 다른 블록들로부터 살아서 넘어온 정의들의 모음이다.
- OUT: 해당 베이직 블록이 끝날 때, 밖으로 살아서 나가는 정의들의 모음이다. OUT은 블록 내부에서 새롭게 생성된 GEN과 밖에서 들어온 IN 중 KILL 되지 않고 살아남은 것들을 합친 결과다.
4. Use-Def Chain
Reaching Definitions 분석을 마치면, 컴파일러는 각 변수가 어디서 정의(Def)되어 어디서 사용(Use)되는 지를 연결할 수 있게 된다. 이 연결 고리를 Use-Def Chain이라고 한다.
어떤 명령어에서 변수 x를 사용할 때(Use), 이 x가 어디서 온 값인지 추적하려면 이전에 x를 정의한 지점(Def)들을 모두 찾아야 한다. 만약 프로그램의 흐름이 여러 갈래로 나뉘었다가 합쳐지는 구조라면, 하나의 Use 지점에 도달할 수 있는 Def 지점이 여러 개일 수도 있다. Use-Def Chain은 이렇게 복잡한 다대다 관계를 그래프 형태로 엮어내어 최적화를 수행하는 뼈대가 된다.
5. SSA(Static Single Assignment)
일반적인 코드에서는 하나의 변수 이름이 여러 번 재정의 될 수 있기 때문에 Use-Def Chain이 매우 복잡하게 얽히게 된다. 이를 해결하는 방법이 바로 SSA다. SSA는 변수마다 유일하게 단 한 번씩만 값을 할당받도록 고유한 1회용 이름을 부여하는 코드 형태다. 예를 들면 x=1; x =2를 x1 = 1; x2 = 2; 로 변경하는 식이다.
5.1. 장점
- Use-Def Chain의 단순화
SSA를 적용하여 모든 변수의 이름이 유일해지면, 어떤 변수를 사용할 때, 그 변수가 정의된 위치는 프로그램 전체에서 오직 한 곳뿐이다. 즉 복잡했던 Use-Def Chain이 완벽한 1대1 관계로 단순화된다. 변수의 정의와 사용 간의 연결고리가 직관적이고 명확해져서, 상수 폴딩이나 데드 코드 제거 같은 최적화 알고리즘이 훨씬 빠르고 강력하게 동작할 수 있다.
- 파이 함수를 통한 분기문에서의 충돌 해결
SSA를 만들 때 가장 큰 난관은 분기문이다. 예를 들어 if 경로에서는 x1 = 1이 할당되고, else 경로에서는 x2= 2가 할당되었다고 할 때, 두 경로가 합쳐지는 지점에서 x의 값을 읽으려고 하면 x1과 x2중 무엇을 읽어야 할지 모호해진다. 이를 해결하기 위해 SSA는 두 경로가 병합되는 지점에 파이함수(Phi Funtion)라는 가상의 명령어를 삽입한다. 파이 함수는 프로그램의 실행 흐름이 어느 경로를 타고 왔는지에 따라, 여러 개의 변수 이름 중 알맞은 것을 하나 선택하여 새로운 변수에 할당해 주는 역할을 한다. 예를 들어 x3 = Phi(x1, x2)라는 코드가 삽입되었을 때, 흐름이 if를 타고 왔다면 x3에 x1 값을, else를 타고 왔다면 x3에 x2 값을 넣어 흐름의 충돌을 완벽하게 해결한다.
6. Taint Analysis
테인트 분석은 프로그램 외부에서 들어오는 신뢰할 수 없는 데이터, 즉 오염된 데이터가 프로그램 내부를 돌아다니다가, 보안적 문제를 일으킬 수 있는 중요한 지점까지 도달하는지 추적하는 정보 흐름 분석 기법이다. ( taint는 "오염시키다"라는 뜻임)
6.1. 필수 요소
테인트 분석을 컴파일러의 논리적인 데이터 흐름 문제로 모델링하기 위해서는 3가지 필수 요소를 먼저 정의해야 한다.
- Source(오염원): 신뢰할 수 없는 외부 데이터가 프로그램 내부로 처음 들어오는 지점이다. 사용자 입력 폼, 웹 요청 API, 파일 읽기 함수 등이 여기에 해당한다. 이곳을 통해 생성된 변수나 데이터는 모두 오염되었다는 꼬리표가 붙는다.
- Sink(위험 지점): 오염된 데이터가 적절한 검증 없이 도달해서는 절대 안 되는 민감한 함수나 실행영역이다. 데이터베이스 쿼리를 실행하는 함수, 시스템 명령어를 호출하는 함수, 중요한 메모리 할당 함수 등이 Sink가 된다.
- Sanitizer: 오염된 데이터를 안전하게 만들어주는 검증 및 필터링 로직이다. 입력값에서 악의적인 특수문자를 제거하거나, 안전한 타입으로 변환하는 함수를 통과하면 그 데이터는 오염 꼬리표가 떨어지고 다시 안전한 상태가 된다.
6.2. Propagation
테인트 분석의 기본 원칙은 오염된 데이터와 연산을 통해 엮이면 그 결과물도 같이 오염된다는 전파 규칙이다. 예를 들어 x가 Source에서 온 오염된 변수라고 가정해 보자. 만약 y = x+10이라는 명령어가 실행된다면 원래 안전했던 변수 y 역시 오염된 x의 영향받아 값이 결정되었으므로 그 즉시 오염된 변수로 취급된다. 분석기는 이러한 방식으로 변수에서 다른 변수로 오염 속성이 전염되는 과정을 끝까지 따라간다.
6.3. Reaching Definiton과 Use-Def Chain
컴파일러는 수만 줄의 코드 속에서 오염이 어떻게 전파되어 Sink까지 가는지를 증명하기 위해 Reaching Definiton과 Use-Def Chain를 사용한다.
- Reaching Definitions와 데이터 의존성 추적
오염된 데이터가 Source를 통해 프로그램에 진입하는 것을 하나의 정의라고 보자. Reaching Definition 분석은 이 특정 할당 값이 덮어씌워지지 않고 어디까지 살아남는지를 계산한다. 하지만 이것만으로는 취약점을 찾을 수 없다. Reaching Definition은 오직 단일 변수의 생존 여부만 추적하기 때문이다. 예를 들어 y = x + 10이라는 연산을 만나면, x의 흐름은 여기서 목적을 다하고 끝난다. 그 결과로 새로운 변수 y가 정의되었기 때문이다. 하지만 테인트 분석은 여기서 한 걸음 더 나아가 연산을 매개체로 오염 속성을 다음 변수로 전이 시킨다. x가 오염되었다면 그 연산 결과인 y에도 오염 꼬리표를 붙여 새로운 추적을 시작하는 식이다.
즉 Reaching Definition이 개별 변수의 생존 구간을 짧은 점선들로 보여준다면, 테인트 분석은 이 끊어진 점선들을 Use-Def Chain으로 엮어 Source부터 Sink까지 이어지는 하나의 굵은 실선(데이터 의존성 흐름)으로 완성해 내는 과정이다.
- Use-Def Chain을 통한 Data Dependency Graph 탐색
오염은 단일 변수에 머물지 않고 A->B->C->Sink처럼 수많은 변수들의 연산을 거쳐 복잡하게 전파된다. 컴파일러는 각 변수의 Use-Def Chain을 엮어 거대한 데이터 의존성 그래프(Data Dependency Graph)를 구성한다. 테인트 분석기는 Sink 지점에서 사용되는 변수를 시작점으로 잡고, 이 그래프를 역방향으로 추적해 올라간다. 그 연결 고리의 끝이 오염된 Source와 맞닿아 있다면, 도달 가능한 취약 경로가 존재한다고 최종 결론을 내리게 된다.
6.4. Implicit Flow (암시적 흐름)
앞서 설명한 오염 전파는 변수 간의 직접적인 연산(y = x + 10)을 통한 명시적 흐름(Explicit Flow)이다. 하지만 실제 프로그램에서는 제어 흐름에 의한 암시적 흐름도 존재한다. 예를 들어 if (tainted_a == 1) { b = 1; } 처럼 오염된 변수가 조건문에 사용되어 다른 변수 b의 값을 결정하는 경우, b는 tainted_a와 직접 연산되지 않았지만 제어 의존성(Control Dependency)에 의해 간접적으로 영향을 받는다.
문제는 이러한 암시적 흐름을 테인트 분석에 어떻게 반영할 것인가 하는 점이다 만약 조건문에 사용된 변수가 오염되었다는 이유만으로 그 조건문 내부에서 실행되는 모든 변수(b 등)를 오염되었다고 판단하면, 프로그램의 수많은 분기문을 거치면서 오염이 눈덩이처럼 불어나, 결국 프로그램 내의 거의 모든 변수가 오염된 것으로 잘못 판단하는 과탐문제가 발생하기 쉽다. 반대로 이런 과탐을 막기 위해 암시적 흐름을 완전히 무시해버리면, 해커가 조건문을 이용해 교묘하게 오염 검증을 우회하는 실제 취약점을 놓치는 미탐이 발생한다. 따라서 정적 분석기를 구현할 때 이 암시적 흐름을 어디까지 추적하고 허용할 것인지는 매우 까다롭고 중요한 설계 요소이다.
정리하면 테인트 분석은 외부의 오염된 데이터가 위험 지점까지 도달하는지 추적하는 방법이며, 오염이 덮어씌워지지 않고 살아남는지를 확인하는 Reaching Definition 분석과 오염이 어떤 변수들을 거쳐 전파되었는지 그 연결 고리를 따라가는 Use-Def Chain이 사용된다.
'CS > Graduation project' 카테고리의 다른 글
| [UEFI] DEPEX Cycle Vulnerability 가능성 판단하기 (1) | 2026.03.25 |
|---|---|
| [UEFI] SMI 발생 원리 및 처리 방법 (0) | 2026.03.10 |
| [UEFI] Ghidra에서 edk2 함수 P-code로 확인해 보기 (0) | 2026.02.26 |
| [UEFI] gRT(Runtime Services)란? (0) | 2026.02.24 |
| [UEFI] gBS(Boot Services)란? (0) | 2026.02.24 |