9-1. 소프트웨어 퍼징의 개념과 기술

경희대학교 장대희 교수님의 소프트웨어보안 수업을 기반으로 정리한 글입니다.

 

1. 기본 개념

Bug

소프트웨어 개발자의 실수

• Software "Bug" e.g., 버퍼오버플로우

 

퍼징은 기본적으로 버그를 자동으로 찾고 싶은 것을 말한다.

 

이때 말하는 버그는 런타임 버그이다.

• 버그는 컴파일 버그와 런타임 버그가 있는데, 컴파일 버그는 소스 코드 작성 시 문법같은 거 틀렸을 때 발생하는 버그로, 애당초 이 버그로 인해 프로그램이 만들어지지도 않기에 문제가 되지 않음
• 런타임 버그: 소프트웨어 사용하는 시점에서 문제가 되는 버그

 

또한, 버그는 메모리 버그, 로직 버그 등 종류가 다양한데, 퍼저가 타겟하여 찾고자 하는 버그는 메모리 버그이다. (e.g. ,BOF)

• 물론, 고도화된 연구를 통해 로직 버그도 퍼징하는 게 존재하긴 함

 

버그의 발견이 흥미로운 이유 -> 해커들이 사고 팜

 

단순히 소프트웨어의 오작동을 유발하는 버그도 있지만, 해킹을 유발할 수 있는 구멍을 열어주는 버그도 있다.

때문에, 이런 파급력이 높은 버그를 막기 위해 퍼징이라는 기술을 통해 자동으로 버그를 찾고자 하는 것이다.

 

Fuzzing Basics

Input

퍼징 대상 프로그램에게 주는 입력 (Data) -> 해커가 조작할 수 있는 입력인 것이 중요

• 해커가 줄 법한 입력을 메모리에 넣고 복잡한 일을 하는 소프트웨어가 가장 퍼징을 하기 좋은 소프트웨어임

 

Corpus

Fuzzing에 사용되는 Input의 집합을 칭함

 

퍼징의 기본단계

프로그램이 crash 날 때까지 반복

 

1. Input 생성

어떻게 하면 "좋은 Input"을 생성할 수 있을까?

• Dumb Fuzzing: 순수하게 Random Data 생성
• Smart/Hybrid fuzzing: Random + @ 를 이용해서 버그 발견 확률을 증대

 

2. 프로그램 실행

어떻게 하면 "빠르게" 실행할까?

 

3. 결과 관찰

어떻게 하면 "Bug"를 놓치지 않을까?"

 

Fuzzing 분류

1. Black Box Fuzzing

프로그램 내부를 전혀 모른 채 입력값만 무작위로 계속 넣어보는 방식 (그래서 블랙박스 -> 아무것도 모른다!)

 

2. White Box Fuzzing

소스 코드와 내부 로직을 모두 알고 이를 기반으로 입력을 생성하는 방식

 

3. Gray Box Fuzzing

Black, White의 중간 방식으로 가장 많이 사용하는 방식이다.

: Instrumentation 기반 -> Coverage 측정

• 인스트루멘테이션: 실행 중 어떤 코드가 지나갔는지 기록하려고 프로그램에 계측(로그/표식) 코드를 심는 것
• 커버리지: 특정 입력을 넣었을 때 프로그램의 코드가 얼마나/어디까지 실행됐는지를 나타내는 지표

 

Input 생성에 기반한 분류

Generative vs Mutational

 

1. Generative Fuzzing

• Input을 바닥부터 생성
  • 프로그램의 input specification을 알아야 함
  • Fuzzer가 empty set에서부터 input들을 생성함
• 장점
  • Initial Corpus가 필요하지 않음 (샘플 필요 없다는 의미)
  • 모든 경우를 균일하게 테스트 해갈 수 있음
• 단점
  • mutation보다 input의 효율이 떨어짐: 놓치는 경우들이 많음

 

2. Mutational Fuzzing

• Input을 정상적인 Sample로부터 Mutation(조금씩 변형 -> 돌연변이 input) 
• 장점
  • 일반적으로 Bug Trigger 효과가 뛰어남
  • Input Specification에 대한 완전한 정보가 없어도 되므로 Generative 보다 구현이 쉬움
• 단점
  • Initial Corpus의 수집 과정이 필요함
  • Initial Corpus의 범주를 크게 벗어난 테스팅이 어려움

 

Address Sanitizer

구글에서 퍼징을 위해 만든 도구이다.

 

C언어에서 배열의 인덱스는 0번부터 시작하기에 100개의 element를 선언한 배열의 마지막 인덱스는 99이다.

하지만 100번을 참조했으니  건드리면 안 되는 남의 메모리 위치, 즉 버퍼를 넘어서 참조했기에 버그이다.

 

이때 문제인 것이, 명백한 버그임에도 이 버그를 가지고 있는 소프트웨어를 한 두 번 실행해가지고는 아무 일도 일어나지 않는다.

왜냐하면 페이징 때문이다.

 

CPU가 메모리에 접근할 때, 접근 순간마다 즉시 오류를 발생시키는 것이 아니라 페이지(Page)라는 단위를 기준으로 접근 권한을 검사한다. 메모리는 보통 4KB의 페이지로 나뉘어 있으며, 각 페이지마다 “읽기 가능”, “쓰기 가능”, “실행 가능”과 같은 권한이 설정된다.

 

따라서 배열의 99번째 요소에 정상적으로 읽기 또는 쓰기가 가능했다면, 그 바로 옆인 100번째 요소도 같은 페이지에 속해 있을 가능성이 높아 CPU는 이를 즉시 잘못된 접근으로 판단하지 않는다.

 

-> 때문에, 아무리 퍼징을 해도 버그가 안 잡히는데, 이를 해결하기 위한 도구가 address sanitizer[쎄니타이절]이다. 

 

address sanitizer의 원리는 프로그램의 소스 코드가 바이너리로 컴파일 될 때 약간의 변형을 가하여 소프트웨어의 로직을 건들지는 않지만 메모리 접근시마다 무슨 검사를 하는 추가 로직을 집어 넣는다. (instrument)

 

버퍼 영역 벗어난 접근이다라는 판단이 서면 그 즉시 프로그램 중단

 

어드레스 새니타이저(AddressSanitizer)가 적용된 프로그램을 만들기 위해서는 소스 코드부터 다시 빌드해야 한다.

즉, 기존 실행 파일에 붙이는 것이 아니라 퍼징 전용으로 새롭게 컴파일하는 것이다.

 

이렇게 빌드된 프로그램은 실행 중 허용되지 않은 메모리 접근이 발생하면 지연 없이 즉시 오류를 감지한다.

 

오류가 발생하면 AddressSanitizer 관련 메시지가 출력되며, 어떤 종류의 메모리 오류인지, 어디에서 왜 문제가 발생했는지에 대한 상세한 로그와 스택 트레이스를 함께 제공한다.

 

-> 훨씬 효율적이고, 많은 버거들을 놓치지 않고 잘 잡아낼 수 있음

 

Corpus Pruning?

saturation: 포화

 

code coverage를 크게 하는 인풋이 좋은 인풋 -> bug trigger 할 확률 높은 인풋 -> 빨간색 제거!

 

이때, 어떤 걸 지우는 게 좋을지 판단하는 것을 coverage라는 개념을 통해 하게 된다.

• coverage가 작은 녀석들을 지우는 게 기본 원리 or 중복 커버리지 갖는 인풋 지움

 

2. Coverage 기반 퍼징

퍼징에 유전 알고리즘을 적용

 

Coverage?

basic block, edge: 어셈블리의 레벨

 

즉, 커버리지는 프로그램이 실행된 정도를 표현하는 기준이다.

 

4개 중 주황색으로 표시된 3개의 블럭은 최소 한 번 이사 실행 흐름이 온 블럭이고, 하얀 블럭은 한 번도 실행된 적이 없음을 뜻함 -> block coverage는 75%

edge: 블록 간에 이동할 수 있는 라인 (자료구조에서 노드를 연결하는 엣지)

 

block보다 edge가 더 세밀하게 측량 가능하다.

-> 실제 현업에서 엣지 커버리지를 거의 기본으로 활용

 

그리고 block와 edge는 어셈블리만 가지고 표현이 되는 정보이기에 분석하는 소프트웨어의 소스 코드가 없이, 바이너리만 가지고도 다 얻을 수 있지만, line 같은 경우는 소스 코드가 몇 번째 줄까지 실행 됐느냐를 나타내기에 소스 코드가 없으면 알 수 없다.

-> line coverage로 퍼징을 하는 일은 거의 X, 대부분이 block, edge O

 

유전 알고리즘

퍼저 도구에서의 c의 main과 같은 함수

 

퍼저는 실행 경로(커버리지)를 보고 조건을 하나씩 통과하는 입력만 살아남게 하면서,

결국 크래시를 일으키는 입력(HI!)을 찾아낸다.

 

-> 1/(26*3) 경우로 찾을 수 있음 (선형, 지수에 비해 훨씬 빠른 시간 안에 해결)

 

만약, 커버리지 측정 안 하고 걍 랜덤으로 돌리면 1/26^3 경우로 찾을 수 있음 (지수)

 

AFL (American Fuzzy Lop)

초기 AFL 퍼저의 경우, 타겟 소프트웨어와 퍼저 소프트웨어가 독립적이었음

 

libFuzzer

초기부터, 퍼징 당하는 소프트웨어와 퍼징하는 소프트웨어가 독립적이지 않은 1개의 소프트웨어였음(In-Process), 산업계에서 실제로 많이 사용

 

3. Structured Input Fuzzing

연구 방향: 소스 코드를 트리 자료 구조로 변환하고, 이 자료 구조를 mutation 하는 식으로 퍼징함

 

4. Hybrid Fuzzing

퍼징에 분석 추가!

Data Flow Sanitizer: DFSan

데이터 -> 변수 영향 예측

 

 

특정 조건 만족되는 분기문 타려면 어떤 인풋? (방정식 푸는 기법)

 

 

5. Anti-Fuzzing

내 실수를 찾지 마라! -> 버그 못 찾게 함

 

6. Distributed Fuzzing

자동화 잘 되어 있다!