바이너리 분석 방법론(Binary Analysis Fundamentals)

Binary Analysis Properties

Interprocedural and Intraprocedural Analysis

Flow-Sensitivity

Context-Sensitivity

Control-Flow Analysis

Loop Detection

Cycle Detection

Data-Flow Analysis

Reaching Definitions Analysis

use-def Chains

Program Slicing

참고 및 인용

---

Binary Analysis Properties

Interprocedural and Intraprocedural Analysis

함수 단위 분석의 또 다른 이점은 규모 가변성(scalability)이다.

일부 분석 방법은 실제로 적용할 때 제대로 동작하지 않는 경우가 많다. 발생 가능한 조건 분기의 수가 늘어나면 실행 경로가 2의 제곱에 비례해 증가한다. 일반적인 프로그램은 많은 조건 분기를 가지고 있으므로 모든 경로를 분석하는 것은 불가능한다.

따라서 계산량을 줄이기 위해 주어진 함수 하나만을 분석하는 프로시저 내부 분석(intraprocedural) 방법을 사용한다. 보통은 CFG에 나타난 함수들을 하나씩 분석한다. 함수 단위로 수행한다면 현실적인 범위 안에서 계산할 수 있다.

이와 반대인 프로시저 간 분석(interprocedural) 방법은 CFG의 모든 함수들의 연결 관계를 호출 그래프로 파악하는 방법이다.

프로시저 내부 분석은 결과가 완벽하지 못하다는 단점이 있다. 예를 들어 어떤 프로그램에 특정한 일련의 함수들이 호출되어야 트리거되는 버그가 있다면 이 버그를 찾을 수 없다.

반대로 프로시저 간 분석은 이런 버그를 발견할 가능성은 있지만 시간이 오래 걸리기 때문에 결과를 도출하지 못할 수도 있다.

Flow-Sensitivity

바이너리 분석은 보통 흐름 위주(flow-sensitive) 또는 흐름 무관(flow-insensitive) 방법을 따른다.

흐름 위주 분석은 명령어가 처리되는 순서를 누적한다는 의미다. 다음 의사 코드를 살펴보자.

x = unsigned_int(argv[0])  # x ∈ [0, ∞]
x = x + 5                  # x ∈ [5, ∞]
x = x + 10                 # x ∈ [15, ∞]

각 변수가 가질 수 있는 잠재적인 결과값을 결정하려는 변수 범위 분석(value set analysis) 상황을 가정해보자.

흐름을 무시한다면 x의 값은 사용자의 입력이므로 어떤 값이든 가질 수 있다고 가정할 것이다. 이는 매우 부정확하지만 계산 복잡도 관점에서는 아주 쉬운 전략이다.

프로그램의 흐름을 고려해 이전 명령어들의 계산을 누적하면 변수 x의 가능한 값의 범위가 $[15, \infin]$라는 더 정확한 결과를 얻을 수 있다.

실제 바이너리는 복잡하기 때문에 흐름 위주 분석 방법이 더 복잡하고 계산 강도가 높은 경향이 있다.

Context-Sensitivity

문맥 위주(context-sensitivity) 분석 방법은 함수들의 호출 순서를 누적해 고려한다.

만약 context-insensitive 방법으로 프로시저 간 분석을 한다면 전역적인 결과 하나만 계산하게 된다. 반면 문맥 위주의 분석을 한다면 호출 그래프상 경로에 대한 call stack 함수의 순서를 각각 얻게 된다.

문맥 위주 분석 방법의 정확도는 호출 그래프의 정확도에 따라 결정된다. 여기서 문맥(context)이란 호출 그래프를 탐색하는 동안의 상태를 뜻하며, $<f_1, f_2, \dots , f_n>$로 표기한다.

문맥의 크기에 따라 계산량이 증가하므로 실무에서 문맥을 파악하는 것은 제한적이다. 예를 들어 길이가 무한한 재귀 함수의 경우에는 임의의 유한 길이만큼의 문맥만 다룬다.

• Context-sensitive versus context-insensitive indirect call analysis in opensshd

channel_handler 함수에서의 간접 호출 가능성을 파악하고 있다. ftab은 간접 호출 시 참조하는 함수 포인터 테이블이다.

channel_handler 함수의 간접 호출이 channel_pre 테이블(from channel_prepare_select) 또는 channel_post 테이블(from channel_after_select)의 모든 함수 포인터를 대상으로 할 수 있다.

문맥을 고려하지 않고 분석한다면 channel_handler가 가능한 모든 경로의 합집합에서 호출 가능하다고 판단한다➊.

문맥을 고려한다면 가능한 경로만을 분석한 집합을 제시한다. channel_handler 함수가 channel_prepare_select에서 호출되었다면 channel_pre 테이블만을 제시한다➋.

이 예제에서는 문맥 길이가 1이라고 가정했지만, 임의의 길이에 대해서도 적용 가능하다➌.

문맥 위주 분석은 정확도가 높지만 계산 복잡도도 높아지기 때문에 적절한 조치가 필요하다. 예를 들어 재귀 함수는 가능한 문맥의 경우의 수가 무한대이므로 대책을 강구해야 한다.

Control-Flow Analysis

바이너리 분석의 목적은 제어 흐름(control flow)와 데이터 흐름(data flow)의 속성을 찾는 것이므로 제어 흐름 분석(control-flow analysis)과 데이터 흐름 분석(data-flow analysis)으로 나누어서 생각할 수 있다.

Loop Detection

먼저 제어 흐름 분석 기법 중 하나인 반복문 탐지(loop detection)다. 바이너리 수준에서는 반복문이 if/else/switch 구문 등의 조건 분기를 이용한 점프 명령어로 나타나므로 까다롭다.

컴파일러 이론에서의 반복문 탐지 알고리즘은 일반적인 반복문과는 조금 다르다. 여기서의 반복문은 자연 반복문(natural loop)으로 분석 및 최적화가 더 쉬운 형태의 속성을 갖는 반복문을 의미한다.

다음 그림은 CFG 내에 존재하는 자연 반복문과 자연 반복문이 아닌 사이클을 나타내는 예시다.

• A CFG and the corresponding dominance tree

먼저 자연 반복문을 탐지하는 전형적인 알고리즘을 다룰 것이다. 그러려면 지배 트리(dominance tree)에 대해 알아야 한다.

CFG의 entry point에서 $A$를 먼저 통과해야만 $B$로 갈 수 있는 경우 기본 블록 $A$가 기본 블록 $B$를 지배한다고 말한다. 예를 들어 위 그림에서 $BB_3$는 $BB_5$를 지배하지만 $BB_6$는 지배하지 않는다.

오른쪽 그림처럼 CFG 상의 모든 지배 관계를 트리 형태로 표현한 것을 지배 트리라고 한다.

$A$가 $B$를 지배할 때 $B$에서 $A$로의 역행 간선(back edge)을 유도하면 자연 반복문을 찾을 수 있다. 해당 자연 반복문에는 $A$가 지배면서 $B$로 가는 경로가 있는 모든 기본 블록이 포함하며, $B$는 이 집합에서 제외한다.

직관적으로 자연 반복문이란 중간에 삽입될 수 없고, 잘 정의된 헤더 노드(header node)에만 삽입될 수 있음을 의미한다.

예를 들어 위 그림에서 기본 블록 $BB_3$와 $BB_5$를 감싸는 자연 반복문이 존재한다. 이때 $BB_3$은 자연 반복문의 헤더 노드가 되고, $BB_5$는 루프백(loopback) 노드가 된다. 그리고 헤더와 루프백 사이인 loop body에는 아무런 노드도 없다.

컴파일러는 반복문을 최적화하기 위해 반복문에서 역행(unroll)할 수도 있는데, 이로 인해 루프 탐지 알고리즘이 오판할 수도 있다.

Cycle Detection

위 그림에서 $BB_7$에서 $BB_4$로의 역행 간선이 존재하는데, $BB_4$이 $BB_7$을 지배하지는 못한다. 따라서 이는 자연 반복문은 아니지만 일종의 사이클(cycle) 형태다.

만약 단순한 사이클만을 탐지하고자 한다면 CFG만 확인하면 된다.

CFG의 시작 노드에서 깊이 우선 탐색(DFS: Depth-First Search)으로 만나는 기본 블록은 스택에 push하고, DFS를 역행(backtrack) 할 때 pop하면 된다. 만약 DFS 도중 스택에 있는 블록을 만나면 사이클로 간주한다.

위 그림의 CFG에서 사이클을 찾는 과정은 다음과 같다.

• Cycle detection using DFS

0:  [BB1]
1:  [BB1, BB2]
2:  [BB1]
3:  [BB1, BB3]
4:  [BB1, BB3, BB5]
5:  [BB1, BB3, BB5, BB3] // cycle
6:  [BB1, BB3, BB5]
7:  [BB1, BB3, BB5, BB7]
8:  [BB1, BB3, BB5, BB7, BB4]
9:  [BB1, BB3, BB5, BB7, BB4, BB6]
10: [BB1, BB3, BB5, BB7, BB4, BB6, BB7] // cycle

.. skip..

Data-Flow Analysis

Reaching Definitions Analysis

도달 정의 분석(reaching definition analysis)이란 정의된 데이터가 특정 지점에 도달할 수 있는지를 보는 것이다.

여기서 도달(reach)의 의미는 특정 변수(레지스터나 메모리 주소)에 할당된 값이 다른 값으로 덮어쓰이지 않고 특정 위치까지 유지되는 것을 의미한다.

보통 CFG에서 이뤄지며, 프로세스 간 분석에서도 수행할 수 있다.

• Example of gen and kill sets for a basic block

각 기본 블록을 생성(generate)하는 것과 소멸(kill)하는 것을 기반으로 한다.

$\text{gen}[BB_3]=\{6, 8\}$인 이유는 x, z가 6번, 8번 구문에서 계속 유지되었기 때문이고, 반면 7번 구문에서 z는 8번 구문에서 덮어썼기 때문이다. $\text{kill}[BB_3]=\{1, 3, 4\}$인 이유는 1, 3, 4번의 구문에서 정의된 변수들이 $BB_3$에서 덮어쓰기 때문이다.

이렇게 각 기본 블록에 대한 gen/kill 집합을 계산하면 각 기본 블록이 생성하거나 소멸시키는 데이터 정의에 대한 local solution을 얻게 된다. 이를 이용해 global solution을 계산할 수 있다.

이렇게 global set을 구한 후 $B$에 도달할 수 있는 정의 집합을 $\text{in}[B]$라고 한다.

$$\text{in}[B] = \bigcup_{p\in \text{pred}[B]}\text{out}[p]$$

$\text{out}[B]$는 $B$에서 출발하는 정의 집합이다.

$$\text{out}[B] = \text{gen}[B] \cup (\text{in}[B] - \text{kill}[B])$$

in 집합과 out 집합은 상호 의존적이므로 도달 정의를 수행할 때 in/out 집합을 반복해서 계산해야 한다. 반복을 통해 모든 in, out 집합이 안정적인 상태가 되면 분석이 끝난 것이다.

use-def Chains

use-def 체인 기법은 어떤 변수를 사용한다면 그 변수는 이미 정의가 되어있었을 것이라는 사실을 기반으로 한다.

• Example of use-def chains

위 그림의 $B_2$에서 변수 y의 use-def 체인이 2, 7인 이유는 y가 2번째 구문 또는 반복문을 통해 7번째 구문에서 왔을 것이라고 추측한 것이다.

이 기법은 디컴파일러 분야에서 유용하게 쓰인다. 디컴파일러는 user-def 체인을 통해 조건부 점프에서 사용된 변수 값의 변화를 추적할 수 있다. 또한 특정 지점에서 변수의 값이 하나로만 결정되는 경우 그냥 상수로 처리하는 상수 전파(constant propagation)와 같은 컴파일러 최적화에도 사용된다.

만약 CFG에 대한 도달 정의 분석을 통해 각 변수의 in 집합만 찾는다면 그리 어렵지 않은 기법이다.

반대로 데이터가 어느 위치에서 쓰일지 파악하기 위해 def-use 체인을 계산하는 경우도 있다.

Program Slicing

슬라이싱(slicing)이란 슬라이싱 기준점(slicing criterion)에서 선택된 변수 집합의 값에 영향을 미치는 모든 명령어(소스 코드 기반인 경우 코드 라인)를 추출하는 것이 목표다.

슬라이스는 control flow 및 data flow를 추적해 관계없는 영역을 찾아 제거한다. 관련 있는 코드만 남은 것을 최종 슬라이스(final slice)라고 한다.

• Using slicing to find the lines contributing to y on line 14: print(y)

x = int(argv[0])  // here
y = int(argv[1])  // here


z = x + y
while(x < 5) {   // here
	x = x + 1      // here
	y = y + 2      // here
	z = z + 2
	z = z + y
	z = z * 5
}

print(x)
print(y)
print(z)

print 함수로 y를 출력하기 전까지 y에 기여하는 구문을 찾아보면 here 주석이 있는 구문들이 슬라이스임을 알 수 있다. 이런 슬라이스만으로 프로그램을 컴파일해 y의 값을 출력하면 결과는 같을 것이다.

위 예시처럼 아래에서부터 올라가는 것을 역방향 슬라이싱(backward slicing)이라고 한다. 반대로 선택한 지점에서 코드를 변경할 경우 어느 지점에 영향을 미칠지 예측하기 위해 정방향 슬라이싱(forward slicing)도 가능하다.

이 기법은 리버싱뿐만 아니라 버그가 있는 코드를 찾기 위한 디버깅에서도 쓰인다.

슬라이싱은 정적 분석 분야에서 제안되었는데, 최근에는 동적 실행 추적에서도 종종 적용된다. 동적 슬라이싱은 상대적으로 더 작아서 해석하기 쉬운 슬라이스를 생성한다.

슬라이스는 매우 복잡해서 제품보다는 연구 주제로 다뤄지고 있다(angr 참고).

---

참고 및 인용

[1] https://practicalbinaryanalysis.com/

[2] http://www.acornpub.co.kr/book/binary-analysis

[3] https://hexterisk.github.io/blog/posts/

---

Uploaded by Notion2Tistory v1.1.0