오늘 리뷰할 논문은 NDSS 2016에 발표된 Driller: Augmenting Fuzzing Through Selective Symbolic Execution입니다.
N. Stephens et al., "Driller: Augmenting Fuzzing Through Selective Symbolic Execution," in NDSS, 2016.
논문은 아래 링크클릭하시면 PDF로 확인할 수 있습니다.
약 15페이지 정도의 논문이고 원문을 프린트해서 해석하면서 공부했습니다.
이전 포스팅까지 6개의 angr 포스팅과 2개의 퍼징 관련 포스팅을 작성했었습니다.
angr은 Symbolic execution으로 해당 논문에서는 Concolic execution으로 표현합니다. Concolic은 concrete와 symbolic의 합성어로 실제 SMT 솔버와 같은 심볼릭기반 시스템이 동작하는 걸 concolic execution으로 이해하면 될 듯싶습니다.
fuzzing은 이전 포스팅들에 설명했던 것과 같이 genetic과 mutation을 통해 랜덤한 입력값을 생성해서 넣어 프로그램의 크래쉬나 버퍼 오버플로우 등의 보안 버그를 유발합니다.
사전 지식
조금 더 깊게 살펴보기 전에 논문에서 정의하는 개념을 짚고 넘어가보겠습니다. 총 3가지 개념이 있습니다.
- specific input : 프로그램 내에서 "특정한" 입력을 의미합니다. 이를테면 if문으로 갇혀있는 비밀번호 입력 함수와 같은 조건을 만족하는 input입니다.
- general input: 프로그램의 특정 구획 내부에서 처리되는 데이터들로, 한가지 값이 아닌 다양한 값들이 허용 되는 입력입니다.
- Compartment : 논문에서는 프로세스 안에서의 동작을 compartment라는 구획으로 구분해뒀습니다. 이 구획들은 나중에 그래프에서 블록으로도 표현되는데,
조금 더 쉽게 설명을 해보자면 ida에서 제공하는 블럭들과 같은 공간들이라고 생각하셔도 편할 것 같습니다. 해당 compartment들은 옵션 선택(리눅스 명령어처럼 여러가지 입력)과 같은 방식으로도 넘어갈 수 있지만 특정한 password를 입력해야 넘어갈 수 있는 구획들도 있습니다. 여기서 특정한 specific을 입력해야 넘어갈 수 있는 compartment를 Boundaries라고 정의합니다.
이제 본격적으로 살펴보도록 하겠습니다.
Fuzzing과 Concolic execution은 각각의 장단점을 가지고 있습니다.
먼저 Fuzzing입니다.
- High-Speed : 프로그램을 Native로 돌리기 때문에 압도적인 속도를 가지고 있고, 초당 수천번~수만번의 테스트가 가능합니다.
- Low overhead : 복잡한 분석 없이 실행 결과만 모니터링하므로, 시스템 자원을 적게 먹습니다.
- General Input 탐색에 강점을 가짐 : Compartment 내부의 일반적인 로직을 빠르게 훑어 코드 커버리지를 높일 수 있습니다.
- Magic Value : if ( input == PASSWORD)와 같이 구체적인 값을 요구하는 조건문을 만나면, 이를 맞출 가능성이 매우매우 낮습니다(brute force와 비슷)
- Shallow Depth : 복잡한 로직 뒤에 있는 깊은 버그를 찾기 어렵습니다.
다음은 Concolic execution입니다.
- Precision : 복잡한 조건문(Magic Value, Checksum)을 만나도 제약조건을 풀어내서 specific input을 생성할 수 있습니다.
- Deep reach : 퍼저가 절대 도달하지 못하는 깊은 코드 경로까지 도달 가능합니다.
- 이론적 보장 : 해(soulution)이 존재하는 모든 조건문에 대한 탐색을 보장합니다.
- Path Explotion : angr ctf에도 나왔던 개념인 경로 폭발로, 프로그램 분기가 늘어날수록 분석할 경로의 수가 2^n으로 비약적으로 증가하여, 경로 폭발 현상이 발생합니다.
- High overhead : SMT Solver와 같은 symbolic execution 툴들은 일반 실행보다 몇십~몇천배 느리고 메모리를 많이 차지합니다. angr와 같은 경우 분석 코드를 VER IR이라는 언어로 한번 번역을 하고 처리하는데 이 과정에서 오버헤드가 발생합니다.
이제 기본 개념들은 어느정도 이해가 되셨을 거라 생각합니다.
Fuzzing과 concolic execution의 장점을 유지하면서 단점을 해결하기 위해 나온 도구가 Driller라는 툴입니다. driller는 fuzzing과 concolic execution 방식을 둘 다 채용합니다.
Driller Process
Driller의 작동 방식을 4단계 프로세스로 나눠서 정리해보겠습니다.
(*아래 포스팅에서 사용된 그림은 논문 본문 5페이지(Driller overview)에 삽입된 그림입니다.)
- Fuzzing 먼저 Fuzzer가 작동하여 입력값을 변이(Mutation)시키면서 프로그램을 실행합니다. 위의 사진에서 보시면 check magic함수에 대해서는 올바른 입력값을 찾지 못해 bad magic의 상태로만 전이가 되고 있습니다.
2. Saturation Detection
Fuzzer가 한동안 돌았는데도 더 이상 새로운 상태 전이(State Transition), 즉 새로운 코드 경로를 찾지 못하게 되면, Driller는 Fuzzer가 특정 조건문에 막혀있다고 판단을 합니다(사진에서는 check magic). 따라서 symbolic execution engine을 부릅니다.
3. Concolic execution
Fig2와 같이 Fuzzer가 넘겨준 입력값을 받아 Concolic Execution을 시작합니다. 그 길을 그대로 따라가면서 (Pre-constrained Tracing), Fuzzer가 뚫지 못한 분기점을 찾아 symbolic execution을 통해 해결책을 찾아 specific input을 생성합니다.
4. Feedback
3단계 프로세스에서 찾아낸 새로운 입력값을 다시 Fuzzer의 큐에 집어넣습니다. Fuzzer는 막혀있던 구간을 통과 한 뒤 다시 Mutation을 통해 구획 내부를 다시 탐색합니다(1단계 프로세스로 복귀)
Concolic execution in Driller
Driller에서의 선택적 concolic execution 방식입니다. 흥미로운 4가지 방식을 가지고 있습니다.
1. Pre-constrained Tracing : 사전 제약 추적
Fuzzer가 멈춘 그 상태에서 멈춰서 Symbolic engine을 부를 순 없습니다. symbolic engine을 부르고 나면 Angr과 처음부터 모든 길을 다시 입력값을 입력하면서 fuzzer가 멈춘 곳에서 분석을 해야하는데, 이 때 사전 제약을 걸지 않으면 경로 폭발 문제가 발생할 수 있습니다.
따라서 Fuzzer가 실행한 기존 블록들의 주소 순서들을 기록하고, angr가 fuzzer가 입력한 입력 그대로 입력하여 마지막에 fuzzer가 막힌 블럭으로 최단 시간안에 도달할 수 있도록 하고 효율성을 높입니다.
2. Input Preconstraining : 입력 사전 제약
Symbolic Execution engine이 수식을 계산하다보면, 의도치 않게 입력값을 너무 많이 바꿔 엉뚱한 경로로 빠지는 현상이 생깁니다. 따라서 Solver가 방정식을 풀다가 앞부분의 중요한 헤더값까지 바꾸는 일이 없도록, 입력값의 바이트들을 Symbolic varition으로 두면서도 "이 값은 원래 Fuzzer가 찾은 값과 같아야 한다"는 제약 조건을 미리 걸어둡니다.
3. Limited Symbolic Exploration : 제한된 심볼릭 탐색
가장 신기했던 부분으로, 심볼릭 탐색으로 어려운 조건문을하나 뚫고 바로 Fuzzer를 불러오는게 아니라 주변코드를 조금 더 탐색을 하다가 Fuzzer를 호출하는 최적화 방식입니다.
다음과 같은 코드가 있다고 생각해보겠습니다.
// 4바이트씩 두 번 입력받음
read(0, &magic1, 4);
read(0, &magic2, 4);
// 첫 번째 specific input
if (magic1 == 0xDEADBEEF) {
// 두 번째 specific input
if (magic2 == 0xCAFEBABE) {
bug();
}
}
위의 코드에서 보면 첫번째 if문 magic value check 이후에 바로 두번째 magic value를 체크합니다.
만약 Limited Symbolic Exploration이 없다고 생각했을 때, driller가 풀기에 불가능한 문제는 아니지만, 첫번째 if문 뒤에 퍼저를 부른 뒤- 또 한참 시간이 지난 뒤 symbolic engine을 불러야 하고, 다시 symbolic engine은 프로그램 초입부터 해당 지점까지 뚫고 와야합니다. 이러한 방식은 시스템 자원 관리 차원에서 비효율 적입니다.
이러한 코드에서 driller는 첫번째 if문을 푼 뒤 몇가지 블록을 더 탐색하다 두번째 if문을 확인한 뒤 fuzzer에게 바통을 넘기게 되고 fuzzer가 블록을 추가 탐색하면서 버그를 발생시키게 될 것입니다.
4.Re-randomization : 재무작위화
재무작위화는 프로그램이 실행할 때 마다 바뀌는 랜덤 값(Challenge - Response)에 대응하는 것입니다. 예를 들어 다음과 같은 코드가 있다고 생각해보겠습니다.
int main(void){
int challenge;
int response;
challenge = random();
write(1,challenge, sizeof(challenge));
read(0, &response, sizeof(response));
if (challenge == response)
abort();
}(*위의 예제 코드는 논문 본문 8페이지에서 발췌했습니다)
위의 코드는 랜덤값으로 생성한 challenge에 대해 일치 여부를 검사합니다.
만약에 angr를 통해 한번 문제를 풀었다 하더라도 다음 실행에서 challenge값이 달라지면 response값을 채우는데 다시 비용을 써야할 것입니다.
여기서 driller는 단순히 response = 특정 숫자 와 같은 저장 대신에, response = challenge와 같은 규칙을 찾습니다.
이러한 방식도 비용을 줄이는 최적화 방식입니다.
Evaluation : 평가
논문의 평가 부분입니다. DARPA Cyber Grand Challenge 예선에 출제된 문제(126개의 바이너리)를 대상으로 실험을 진행하였고, 세부 평가 사항은 작성하지 않겠습니다만, 내용중에서 조금 흥미로웠던 부분을 가져오겠습니다.
위의 그래프는 Driller(D), Fuzzer(F), Symbolic(S)가 찾은 취약점에 대한 양적 그래프입니다.
Driller와 Fuzzing에 대한 원의 크기가 드라마틱하게 커지진 않았지만, Fuzzing만으로 푼 문제에 대한 100%를 Driller로 풀 수 있었고, 마찬가지로 Symbolic으로 풀 수 있던 문제도 100% Driller로 풀 수 있습니다.
여기서 중요한 점은 Driller만 풀 수 있었던 9문제의 난이도를 생각해봐야 합니다.
저희가 CTF나가면 쉬운문제 / 어려운 문제가 나눠져 있는데, Driller가 푼 9문제는 대회 전체에서 우승팀을 제외하고는 푼 팀이 거의 없는 난이도가 매우 높은 문제라고 합니다.
그림 8은 각 바이너리 문제에 대한 fuzzing과 concolic의 누적그래프입니다. 이게 좀 인상깊었는데 concolic이 짙은 회색으로 표현되어 있는데, 짙은 색이 아주 적은 부분도 있고, 매우 길게 쌓여있는 그래프도 있습니다.
왼쪽에서 두번째 막대 보시면, 짙은회색이 아주 길게 쌓여있는데, 이건 해당 문제를 풀 때 concolic engine이 자원을 매우 많이 썼단 뜻이고, 다시 생각해보면 fuzzer로는 해당 문제를 절대 풀수 없다는 뜻이기도 합니다. 또한 왼쪽에서 3번째 그래프도 마찬가디로 처음에 concolic engine을 잠깐 불렀다가 다시 퍼징을 진행하는데, 이것도 마찬가지로 concolic의 도움이 없었으면 진척도가 매우 떨어졌을 것입니다.
Driller와 같은 hybrid tool의 효율성에 대해 입증을 해주는 그래프인듯 하여 가져왔습니다.
Limitation : 한계
한계점으로 두가지 방식이 있습니다.
- AFL의 단순한 상태 표현 방식 : Driller는 효율성을 위해 AFL의 상태 관리 방식(State-Transition tuples + Hit counts)을 그대로 차용했습니다. 이는 속도를 올려주지만 너무 단순합니다.
위와 같은 코드가 있을때 Driller는 static_strcmp를 다르게 사용하더라도 인식을 잘 못합니다. 이건 아까 말했던 fuzzer의 단점인 shallow depth문제인데, Driller와 AFL은 함수의 호출자인 Caller는 확인하지 않고, 지금 실행하는 코드의 주소만 확인합니다.
따라서 위와 같은 코드에서 first_cmd를 분석하고나면 second_cnd나 crash_cmd에 대해서는 static_strcmp에 대해 이미 분석했다고 생각하여 깊게 분석하지 않아 핵심 버그인 abort()를 찾을 수 없게 됩니다.
2. 특정 조건에 있어서 fuzzer가 아예 힘을 못쓰고 단순 symbolic executiion engine으로 전락하는 경우가 있습니다.
코드를 간단하게만 확인하고 user command의 조건 정의해보면 다음과 같습니다.
1. user_command는 genetic input이지만 user_hash와 일치해야합니다.
2. user_command는 "CRASH"여야 합니다.
이런 경우 fuzzer는 2단계를 맞추기 위해 CRASH값을 맞추는 과정에서 다시 1단계의 hash체크에 막혀서 stub상태에 빠지게 되고 결국 위와 같은 코드가 많을경우 driller는 fuzzer의 도움을 받지 못하고 느린 Symbolic engine에 비해 장점이 모두 사라지게 됩니다.
이렇게 해서 Driller : Augmenting Fuzzing Through Selective Symbolic Execution에 대한 리뷰를 마치겠습니다.
처음 읽었을 때는 9년이나 된 논문인 줄 몰랐는데, 읽으면서 보니까 9년이나 지난 논문이더라고요, 근데 9년이 지났어도 지금 쓰는 퍼징 툴이나 그때 쓰던 툴이나 그렇게 큰 차이는 없는 것 같습니다.. 그만큼 세련된 논문인 것 같다는 생각도 드는 것 같습니다.
AFL이랑 BooFuzz로 퍼징은 해봤는데 아직 Driller를 써보진 않아서 한번 저도 직접 angr, fuzzing, driller 3가지를 이용해서 드림핵 워게임 문제를 풀어보고 비교해볼까 싶은 생각이 듭니다. 공부할 컨텐츠가 정말 넘쳐나네요. 아니면 최근 driller이후로 개발된 퍼징 툴도 있다고 해서 그것도 아마 포스팅을 해보지 않을까 싶습니다.
아마 조금 쉬다가 공부를 더 할 것 같은데 오늘 내로 포스팅을 한두개 더 써보도록 하겠습니다.
읽어주셔서 감사합니다~
'논문리뷰' 카테고리의 다른 글
| [논문리뷰]Comparing Traditional Hacking Tools and AI-Driven Alternatves (0) | 2025.12.29 |
|---|---|
| [논문리뷰] Scaling Responsible Generative AI: Automating Red Teaming of LLM applications (0) | 2025.12.22 |