Static Disassembly
정적 디스어셈블(static disassembly)이란 바이너리를 실행하지 않고 바이너리를 디스어셈블 하는 방법이다.
모든 정적 디스어셈블 도구는 다음 순서로 진행된다.
- 대상 바이너리를 로드 한다.
- 대상 바이너리 내부의 모든 assembly instruction을 찾아내야 한다.
- 찾아낸 instruction들을 사람이나 컴퓨터가 이해하고 처리할 수 있도록 번역한다.
2번 항목은 매우 어렵고 많은 오류가 발생할 수 있다. 이런 오류를 회피하기 위해 선형 디스어셈블(linear disassembly)이나 재귀적 디스어셈블(recursive disassembly)과 같은 전략을 사용한다.
다음 그림은 선형/재귀적 디스어셈블의 기본 개념을 그림으로 나타낸 것이다.
화살표는 디스어셈블 작업의 진행 흐름이고, 회색 부분은 손상되거나 놓치게 되는 코드를 나타낸다.
Linear Disassembly
선형 디스어셈블(linear disassembly)은 바이너리의 모든 코드 영역의 모든 바이트들을 순차적으로 디코딩하고, 내용을 분석해 명령어로 번역하는 방법이다. objdump와 같은 단순한 도구들이 사용한다.
하지만 바이너리의 모든 바이트들이 명령어로 대응되지는 않는다.
예를 들어 Visual Studio 같은 컴파일러는 점프 테이블 등의 데이터를 코드와 섞는데, 해당 데이터가 무엇인지 구분할 단서를 남기지 않는다. 이런 경우 인라인 데이터를 코드와 혼동해 invalid opcode로 잘못 해석한다. x86과 같은 복잡한 ISA는 대부분의 바이트가 임의의 명령어로 해석될 소지가 높아서 자주 발생한다.
게다가 x86 등의 ISA처럼 명령어 길이가 가변적인 경우 인라인 데이터를 잘못 해석해 실제의 정확한 명령어의 길이와의 상호 정렬을 깨뜨릴 수도 있다.
인라인 데이터 바이트들 뒤의 값들을 올바르게 해석했다면 왼쪽의 동기화(Synchronized)처럼 나타나야 한다. 하지만 데이터를 코드로 해석하는 4바이트씩 밀림(-4 bytes off)과 같은 실수를 범할 수도 있다.
Recursive Disassembly
재귀적 디스어셈블(recursive disassembly)은 프로그램의 실행 흐름(control flow)을 고려한다. 메인 엔트리 포인트나 특정 함수 심벌과 같은 특정 엔트리 포인트를 시작점으로 하고, 조건 분기나 함수 호출과 같은 실행 흐름을 재귀적으로 따라가면서 코드를 찾는다.
이 경우 소수의 corner case를 제외하고 대부분의 바이트를 처리할 수 있다.
코드 커버리지를 최대화하기 위해 (ret이 수행되는 부분이 최종 목표가 되기 때문에) 일반적으로 call 명령어 바로 뒤의 바이트를 무조건 디스어셈블한다. 또한 선택적 점프가 이루어지는 분기 모두를 유요한 명령어로 가정한다.
재귀적 디스어셈블은 IDA와 같이 악성 코드 분석 등에서 사용되는 다양한 리버싱 도구들이 채택한 기법이다.
하지만 재귀적 디스어셈블도 단점이 존재한다.
- 데이터와 코드 구분 문제
먼저 프로그램의 모든 제어 흐름을 따라가는 것이 쉽지 않다. 예를 들어 간접 점프나 함수 호출의 목적지를 정적으로 파악하는 것이 어려울 수 있고, 간접 점프나 함수 호출로 이동하는 일부 코드를 놓칠 수도 있다. (위 그림의 )
- 간접 제어 흐름(indirect control flow) 문제
switch 문을 통해 분기하는 코드를 고려해보자. x64의 switch 구문 구현은 점프 테이블(jump table)을 기반으로 동작한다. 이는 swtich의 입력 값을 확인하고 해당 인덱스를 계산해 테이블 내에 저장된 코드 구문으로 점프하는 방법이다.
이는 jmp rax와 같이 하나의 간접 점프 명령어로 점프 테이블의 어떤 주소로도 이동할 수 있다. 하지만 간접 점프에는 명시적인 주소를 사용하지 않는다. 따라서 이 경우 컴파일러에 의존적인 휴리스틱 기법을 사용해야 한다.
일반적으로 swtich 구문을 탐지하는 휴리스틱 기법은 고정된 베이스 메모리 주소와 입력값에 종속적인 오프셋 값을 더해 명령어들이 위치한 주소를 계산하고, 그곳으로 점프하는 명령어를 찾는 방식이다. 그런 다음 점프 테이블 내에서 바이너리 내부의 데이터 섹션이나 코드 섹션에 위치한 유요한 목적 주소를 찾는다.
그럼에도 switch 구문 안에 ret 명령어가 많이 포함돼 있어서 문제가 더 어려워진다.
Dynamic Disassembly
동적 디스어셈블(dynamic disassembly)은 레지스터와 메모리 값 등의 정보를 활용할 수도 있고, 도달한 주소에 명령어가 있다고 확신할 수도 있다.
이 때문에 실행 추적(execution tracer) 또는 명령어 추적(instruction tracer)이라고도 부른다.
Code Coverage Strategies
동적 분석은 모든 명령어를 검사하는 것이 아닌 실행되는 것들만 살펴보기 때문에 코드 커버리지(code coverage) 문제가 존재한다.
예를 들어 버그를 탐지하기 위해 동적 분석을 했다면 테스트에서 실행된 코드 이외에 다른 코드에는 버그가 존재하지 않는지 확신할 수 없다.
프로그램이 도달할 수 있는 모든 경로를 조사하는 입력값을 찾는 것은 어렵다.
대신 적용 범위(coverage)를 높이는 몇 가지 방법을 사용해야 한다. 다만 정확성(completeness)은 정적 분석에 비해 떨어진다.
코드 커버리지를 위한 전략들을 살펴보자.
Test Suites
사전에 협의된 바이너리의 입력값인 테스트 케이스(test case)를 이용해 테스트하는 방법이다.
단점으로는 각 상황에 적합한 테스트 케이스들을 모두 준비하는 것이 어렵다는 것이다.
테스트 케이스를 사용할 수 있는 상황은 바이너리마다 다르며 테스트 값에 따라 결과도 달라진다.
일반적으로 Makefile 내부에 test라는 키워드로 대상 프로그램을 지정하는 방법을 사용하며, make test 명령어로 테스트 케이스를 사용해 작동하도록 한다.
Fuzzing
퍼저(Fuzzer)를 이용하는 방법인데, 퍼저는 주어진 바이너리에 대해 새로운 코드 경로를 찾아내기 위한 입력값을 자동으로 생성하는 도구다. AFL, MS의 Springfield 프로젝트, 구글의 OSS-Fuzz 등이 있다.
퍼저는 입력값 생성 방법에 따라 크게 두 종류로 구분할 수 있다.
- 생성 기반 퍼저(Generation-based fuzzers): 예상되는 입력 형식에 대한 지식 없이 입력값을 처음부터 만들어낸다.
- 변이 기반 퍼저(Mutation-based fuzzers): 알려진 특정 유효 입력값을 기반으로 변이(mutation)를 가해 새로운 값을 생성한다. (예를 들어 기존 테스트 케이스를 모방)
퍼징의 성공 여부와 효율성은 퍼저에게 제공되는 정보와 관련이 있다.
퍼저는 보통 버그를 찾기 위해 crash가 발생할 대까지 입력값을 반복해서 생성하는 방식으로 동작한다.
Symbolic Execution
기호 실행(symbolic execution)은 코드 커버리지 문제뿐만 아니라 더 다양한 목적을 위해 사용할 수 있다.
기호 실행은 프로그램 실행 시 구체적인 값(concrete value) 대신 일종의 수학적인 기호인 기호화된 값(symbolic value)을 사용한다. 즉 레지스터나 메모리 상태와 같은 변수를 모두 기호화된 값을 사용한 수식으로 표현하는 에뮬레이션이다.
다음 pseudocode를 살펴보자.
- Pseudocode example to illustrate symbolic execution
x = int(argv[0]) // ➊
y = int(argv[1])
z = x + y // ➋
if(x < 5) // ➌
foo(x, y, z)
else // ➍
bar(x, y, z)먼저 값을 입력받아 저장한다➊.
기호 실행이 시작되는 시점에서 변수 는 기호 로, 는 로 초기화한다. 과 는 모두 기호이며, 수치적으로 나타낼 수 있는 모든 값을 대표한다.
그러면 에뮬레이션 수행 단계에서 해당 프로그램은 이 기호들을 포함한 공식을 바꾸어 계산한다. 예를 들어 는 이다➋.
그리고 동시에 경로 제약 조건(path constraint)를 계산한다. 이는 실행 경로의 branch에서 해당 기호에 대입할 수 있는 concrete value의 제한 범위를 계산하는 것이다.
예를 들어 if(x < 5)라는 조건절에서 해당 경로를 따를 경우 라는 제약 조건을 부여하는 것이다➌. 이처럼 실행 가능한 모든 경로들에 대해 적절한 제약 조건들의 목록이 부여된다.
따라서 코드 커버리지를 위해 '주어진 제약 조건의 목록이 있을 때 그 모든 조건을 만족시킬 수 있는 구체적인 입력값(concrete input)이 존재하는지를 점검'해야 한다.
이는 조건 풀이기(constraint solver)라는 프로그램이 수행한다. 예를 들어 현재 제약 조건은 뿐이므로 solver는 ^ 과 같은 답을 내놓을 것이다.
이제 코드 커버리지를 증가시키기 위해 경로 제약 조건을 수정하고 다시 솔버에게 해가 있는지 질의한다➍. 이렇게 실행할 수 있는 구체적인 경우의 수들을 확인하면서 코드 커버리지를 증가시킬 수 있다.
하지만 기호 실행은 코드 커버리지 전략만 다루더라고 이론적으로 복잡하고, 다수의 경로 제약 조건을 푸는 것은 계산상 어렵다.
Structuring Disassembled Code and Data
정적/동적 디스어셈블로 코드와 데이터를 찾아도 이를 구조화하지 않으면 분석하기 매우 어렵다.
Structuring Code
디스어셈블된 코드를 구조화하는 기법은 크게 두 가지다.
- 구획화(compartmentalizing): 코드들을 논리적으로 연결된 조각(chunk)로 구분해 쪼개는 방법이다. 이를 통해 각 조각들의 행위와 상호 연관 관계를 쉽게 파악할 수 있다.
- 제어 흐름 파악(Revealing control flow): 일부 코드들은 명시적인 코드 그 자체일 뿐만 아니라 control transfers를 내포하기도 한다. 이런 과정들을 시각화하여 코드의 제어 흐름을 파악하고, 해당 코드들이 어떤 행위를 하는지 손쉽게 알 수 있다.
다음으로 자동화/수동 분석 모두에서 유용하게 사용되는 코드 구조화 사례를 살펴보자.
Function Detection
디스어셈블 도구는 프로그램의 원래 함수 구조를 파악하기 위해 명령어들을 함수 단위로 묶는 함수 탐지(function detection)를 수행한다.
함수 탐지는 리버싱뿐 아니라 자동화된 바이너리 분석에서도 큰 이점이 있다.
심벌 정보가 있다면 심벌 테이블에서 함수명, 주소, 크기 등의 정보를 알 수 있기 때문에 함수 탐지는 아주 쉬워진다. 하지만 실무에서 다루는 바이너리는 스트립 되어 심벌 정보가 없다.
심지어 하나의 함수에 속한 코드가 바이너리 내에서는 불연속적으로 존재할 수도 있다. 함수 내의 코드가 코드 섹션의 여기저기에 흩어질 수도 있고, 일부 코드는 여러 함수들이 공유하기도 한다(overlapping code block).
디스어셈블 도구들은 함수 탐지를 위해 함수 시그니처(function signature)를 이용한다. 시그니처는 함수 시작 부분이나 끝부분에서 자주 나타나는 특정 패턴이다. 이는 재귀적 디스어셈블러가 주로 사용한다.
시그니처 기반의 함수 탐지 알고리즘은 call 명령어에 의해 직접 호출되는 것을 함수로 가정한다. 반면 간접 호출이나 꼬리 호출(함수를 호출하면서 return)로 실행되는 함수들은 난이도가 높다. 따라서 시그니처 기반 함수 탐지는 잘 알려진 함수들의 시그니처를 DB 화하여 관리한다.
시그니처 패턴에는 잘 알려진 함수 프롤로그와 함수 에필로그가 포함된다.
함수 탐지를 이용한 구조화는 유용하지만 오류에 주의해야 한다.
함수 패턴은 환경이나 컴파일러, 최적화 정도에 따라 다른데, 특히 최적화는 함수의 프롤로그와 에필로그를 완전히 없애기도 한다.
최근에는 시그니처를 기반으로 하지 않은 함수 탐지 방법이 연구되고 있다. 이 방법론은 Binary Ninja에서 채택돼 있으며 IDA에서도 연동할 수 있는 실험 단계 도구도 발표되었다.
ELF 바이너리는 .eh_frame 섹션을 이용한 탐지 방법이 있다. 해당 섹션은 DWARF 기반의 디버깅 정보들을 포함하는데, 이 섹션은 스트립 된 바이너리라도 제공된다.
Control Flow Graphs
제어 흐름 그래프(CFG: Control-Flow Graph)는 함수 내부의 코드 블록들의 조합을 그림으로 나타내는 방법으로, 자동/수동 분석에서 모두 유용하다.
- CFG as seen in IDA Pro.
CFG는 화살표로 표시되는 분기 간선(branch edge)으로 연결된 기본 블록(basic block) 단위로 나타난다.
기본 블록은 명령어들로 구성되어 있으며, 바이너리 내에서 점프되는 유일한 명령어인 유일한 entry point에서 시작해서 또 다른 기본으로 점프할 수 있는 명령어인 exit point로 끝난다.
즉 entry point 또는 exit point 이외의 명령으로 화살표가 연결되는 기본 블록은 존재할 수 없다.
CFG에서 기본 블록 에서 다른 기본 블록 로 연결되는 edge가 있다면, 이는 의 exit point에서 의 entry point로 점프하는 것을 의미한다.
의 edge가 하나라면 제어 흐름은 해당 방향으로만 흐른다(간접 점프나 다른 함수 호출을 의미). 만약 여러 조건에 의해 분기한다면 2개 이상의 edge가 존재할 것이다.
함수 외부로의 이동은 표현할 수 없기 때문에 다른 함수 호출을 나타내는 간선은 CFG에서 표현되지 않는다. 대신 함수 호출이 끝나면 빠져나간다는(fallthrough) edge만 기록한다.
간접 간선은 정적으로 해결하기 어렵기 때문에 CFG에서 생략하기도 한다.
디스어셈블 도구는 함수별 CFG 대신 전체 CFG를 그리기도 하는데, 이런 그래프는 CFG를 합친 형태이므로 프로시저간 CFG(ICFG: Interprocedural CFG)라고 한다.
ICFG는 오류가 적지만 CFG에 비해 구획화(compartmentalization) 측면에서 이점이 없다.
Call Graphs
호출 그래프(call graph)는 기본 블록이 아닌 호출 명령과 함수 사이의 관계를 나타내기 위한 구조화 방법이다.
호출 그래프도 CFG처럼 간접 호출 간선은 무시한다.
- CFGs and connections between functions (left) and the corresponding call graph (right).
위 그림의 왼쪽은 함수들(~)의 상관관계를 나타내고 있다. 각 함수들은 기본 블록(회색 원)들로 이루어져 있고, 분기 간선(화살표)로 연결되어 있다.
오른쪽 그림은 이를 호출 그래프로 나타낸 것이다.
함수의 주소를 메모리에 적재하는 명령어가 있는 경우 이 함수를 주소 획득 함수(address-taken functions)라고 한다. 함수의 주소 획득은 간접적으로 호출될 가능성이 있다는 것을 의미하므로 중요하다.
만약 어떤 함수가 주소 획득도 안되고 데이터 섹션 내에서 보이지 않으며 간접 호출이 일어나지 않는다고 간주하면 된다.
Object-Oriented Code
객체 지향 언어의 코드에서는 클래스(class)를 사용해 함수와 데이터들을 논리적으로 묶는다.
C++ 프로그램은 가상 함수(virtual function)로 인해 함수 포인터를 많이 포함한다. 가상 함수는 파생 클래스에서 재정의될 수 있는 클래스 메서드다.
각 함수 포인터들을 관리하기 위해 특정 클래스에 속하는 모든 가상 함수를 목록화해 vtable에 저장한다. vtable은 보통 메모리상에서 읽기 전용이며, 각각의 다형성 객체들은 vtable 안에 각 객체의 형식에 알맞은 포인터 vptr를 저장한다.
컴파일러는 가상 함수를 처리하기 위해 객체의 vptr을 따르는 코드를 표기하고, 실행 시점에 vtable에서 올바른 항목을 간접적으로 호출할 수 있도록 한다.
이런 간접 호출은 제어 흐름을 파악하기 어렵게 만든다.
Structuring Data
지금까지 코드를 식별하고 구조화하는 방법과 자동화에 대해 다루었는데, 데이터를 구조화하는 것은 매우 어렵다.
자동 데이터 구조 탐지는 일반적으로 동적 분석으로 코드에서 접근하는 방식을 살펴보고 메모리에 있는 객체의 데이터 유형을 유추한다. (Howard: a Dynamic Excavator for Reverse Engineering Data Structures 논문 참고)
물론 방법이 전혀 없는 것은 아니다. 예를 들어 특정 데이터 객체가 잘 알려진 함수에 전달되는 상황을 고려해보자. 함수에서 사용되는 매개 변수는 레지스터나 메모리 객체로 사용될 때의 데이터 타입으로 추론할 수 있다.
하지만 더 복잡한 구조체나 배열에서는 힘들다. 중요한 데이터 타입을 식별하는 것은 매우 복잡해서 자동화를 거의 시도하지 않는다.
Decompile
디컴파일러(decompiler)는 컴파일 과정의 역변환을 수행하는 굉장히 유용한 도구다.
하지만 오류가 발생할 확률이 높아서 결과가 부정확하기도 하고 실패율도 높다. 따라서 중요한 분석을 수행할 때는 디컴파일을 고려하지 않는 것이 좋다.
Intermediate Representations
동적 오염 분석이나 기호 실행 기법에서는 분석하려는 명령어가 데이터 흐름 관점에서 어떤 의미인지 파악하고 처리할 수 있어야 한다. 이런 부담을 줄이고자 중간 언어 표현식(Intermediate Representation) 또는 중간 언어(Intermediate Language) 개념이 등장했다.
IR은 기계어 코드를 추상화할 수 있는 단순한 언어다. REIL(Reverse Engineering Intermediate Language), 바이너리 계측 프레임워크인 valgrind가 채택한 VEX IR 등이 있고, LLVM 용 바이너리 기계어 LLVM IR 변환을 위한 McSema라는 도구도 있다.
IR 언어는 기계어 코드를 의미적으로 포괄하면서 더 쉽게 분석 가능한 언어로 번역하는 역할을 해준다. 예를 들어 REIL은 x86의 수백 가지 명령어 중 17개를 제외하고 모두 지원한다.
장점은 특정 명령어 위주의 처리 방법을 구현하지 않고 IR을 이용해 한 번만 변환하면 되고, 통일된 IR을 이용해 다양한 ISA를 처리할 수도 있다 점이다.
단점은 IR의 표현식이 더 복잡할 수 있다는 것이다. 이는 제한된 수의 명령어로 모든 명령어를 표현하려 했기 때문인데, 사람이 읽을 때 문제가 되지만 자동화에서는 문제가 아니다.
다음은 x86-64 명령어인 add rax, rdx를 VEX IR로 변환한 예시다.
IRSB { // ➊
t0:Ity_I64 t1:Ity_I64 t2:Ity_I64 t3:Ity_I64 // ➋
00 | ------ IMark(0x40339f, 3, 0) ------ // ➌
01 | t2 = GET:I64(rax) // ➍
02 | t1 = GET:I64(rdx)
03 | t0 = Add64(t2, t1) // ➎
04 | PUT(cc_op) = 0x0000000000000004 // ➏
05 | PUT(cc_dep1) = t2
06 | PUT(cc_dep2) = t1
07 | PUT(rax) = t0 // ➐
08 | PUT(pc) = 0x00000000004033a2
09 | t3 = GET:I64(pc) // ➑
NEXT: PUT(rip) = t3; Ijk_Boring // ➒
}한 줄의 add instruction이 10줄로 변환되었으며, metadata들도 추가되었다.
먼저 하나의 machine instruction에 대응하는 메타데이터인 IRSB(IR Super Block)를 선언한다➊.
해당 IRSB는 t0부터 t3까지 4개의 임시 변수를 사용하며 모두 Ity_I64(64-bit integer)임을 알 수 있다➋.
이후 해당 기계어의 주소와 길이 등의 정보를 포함하는 메타데이터인 IMark가 등장한다➌.
이후 GET 명령어로 rax와 rdx 레지스터에서 64-bit int 값을 각각 t2, t1 변수에 할당한다➍. 이때의 rax, rdx는 레지스터를 VEX에서 처리하기 위한 심벌 이름이다. 실제 레지스터에 접근하지 않고 레지스터의 복사본을 VEX 내부에 저장하는 방식을 사용한다.
이제 VEX의 Add64 명령어를 사용해 t2와 t1을 더해 t0에 저장한다➎.
덧셈 연산 이후 add instruction의 후속 작용에 대응하는 몇 개의 PUT 명령어가 수행돼 x86의 상태 플래그를 변경한다➏.
그러고는 연산의 결과를 rax에 저장하고➐ 마지막으로 PC(program counter)를 갱신한다.
Ijk_Boring(Jump Kind Boring)은 add 명령어가 제어 흐름에 영향을 끼치지 않음을 나타낸다➒. (만약 조건 분기 명령어라면 Ijk_Call 또는 Ijk_Ret과 같은 정보가 표기된다.)
Effects of Compiler Settings on Disassembly
컴파일러의 최적화는 디스어셈블 작업의 정확성을 저해한다. 예를 들어 mul과 div 명령어를 bitwise shift 연산으로 변경할 수 있다.
또한 함수 호출의 오버헤드를 줄이기 위해 작은 함수들을 큰 함수 안으로 병합하는 인라인(inline) 작업을 수행할 수도 있다. 이 때문에 코드 상의 함수가 바이너리에서 똑같이 존재하리란 보장을 할 수 없게 된다.
또한 함수를 호출하면서 반환하는 꼬리 호출(tail call)이나 최적화된 호출 규약으로 함수 탐지가 어려워진다.
더 높은 최적화 단계에서는 함수와 기본 블록 사이에 패딩 바이트를 생성해 메모리 주소를 정렬하기도 하는데, 이 패딩 바이트를 코드의 일부로 잘못 해석하면 디스어셈블 과정에서 오류가 발생할 것이다.
최적화는 데이터 구조 파악에도 방해가 된다. 예를 들어 최적화된 코드에서는 여러 배열을 순회할 때 하나의 베이스 레지스터를 사용하는 것처럼 보인다.
앞서 다룬 최적화 기법들 외에도 ASLR(Address-Space Layout Randomization)을 위해 위치 독립 코드(PIC: Position-Independent Code)와 같은 기법도 적용되는데, 그로 인해 코드와 데이터의 위치가 변경되는 형태도 볼 수 있다.
PIC를 적용한 바이너리를 위치 독립 실행 파일(PIE: Position Independent Executable)이라고 한다. 이런 바이너리는 코드와 데이터를 참조할 때 절대 주소(absolute address)를 사용하지 않기 때문에 PLT 등의 기본 구조가 굉장히 다르게 보인다.
참고 및 인용
[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