Fuzzing 이란? - Grey-box fuzzing, Code coverage, Mutation, Seed Scheduling

퍼징을 처음 공부할 때, 지루하지만 꼭 알아야 하는 개념들을 가져와 봤습니다. 

현대의 복잡한 소프트웨어에서 버그를 찾는 것은 점점 어려워지고 있습니다. 복잡해지니까 요구하는 입력 유형이 다양해지면서 수동 분석만으로는 한계가 있는거죠. 이러한 배경에서 자동화된 프로그램 분석 기법이 생겼습니다. 

 

프로그램을 분석하는 방법은 크게 정적 분석과 동적 분석으로 나눌 수 있습니다.

정적 분석은 프로그램을 실행하지 않고 코드 자체를 분석하는 방법입니다. 주요 기법들은 아래와 같습니다. 

• Control-flow analysis: 실행 경로와 흐름을 분석합니다. 어떤 코드가 언제 실행되고.. 분기는 어떻게 이루어지는지를 트리 구조로 파악합니다. (트리 구조로 그림이 만들어지는 경우)
• Data-flow analysis: 데이터의 흐름을 분석합니다. 예를 들어 printf 함수의 매개변수가 코드상에서 어디서 왔는지 추적하여 데이터 간의 의존관계를 파악합니다. (먼저 control flow 분석이 되어있어야 합니다)
• Symbolic execution: 위의 두 분석이 완료된 후 가능한 기법입니다.
• Abstract interpretation과 Static taint analysis 등도 있습니다. 뭐 이런게 있다~ 정도만 알고 넘어가도 됩니다. 

동적 분석은 프로그램을 실제로 실행시켜서 관찰하는 방법입니다:

• 디버깅
• Fuzzing
• Dynamic taint analysis
• Sanitizer

정적 분석과 동적 분석은 서로 장단점이 상보적이기 때문에, 두 방법을 함께 사용하는 Hybrid Analysis이 효과적입니다.

---

그럼 퍼징(Fuzzing)이란 무엇일까요??

퍼징은 못생긴 입력값을 무작위로 생성해서 프로그램에 입력으로 던지는 기법입니다.

프로그램이 이런 입력을 처리하면서 어떻게 동작하는지 관찰하여 버그를 찾는 것이 목표입니다.

• 구현이 쉽고
• 실행 속도가 빠르고
• 병렬화가 용이하다

정보의 가용 여부에 따라 퍼징을 분류할 수 있습니다:

• White-box fuzzing: 소스코드까지 모든 정보를 알 수 있는 경우
• Black-box fuzzing: documentation조차 빈약하여 손에 있는 정보가 거의 없는 경우
• Grey-box fuzzing: 컴파일된 프로그램의 명령어 정도는 알 수 있어 코드 커버리지를 측정할 수 있는 경우

---

Grey-box Fuzzing

저희가 주의깊게 볼 방법은 그레이박스 퍼징인데요, 여기서 가장 중요한 개념은 코드 커버리지입니다.

코드 커버리지는 특정 입력값을 던졌을 때 실제로 프로그램 내부에서 어떤 코드들이 실행되는지를 측정한 것입니다.

 

Coverage-guided fuzzing은 코드 커버리지를 극대화하는 방향으로 진행됩니다.

입력값을 변형했더니 더 많은 코드가 실행되었다면, 이 방향으로 계속 변형을 시도하여(이번엔 여기까지 변형해볼까..) 점점 커버리지를 넓혀가는 전략입니다. 커버리지를 100%로 = 프로그램의 코드를 모두 다 실행하는 것이 목표이지만? 실제로는 불가능하겠죠..

 

커버리지 = 테스트가 소스코드의 얼마나 많은 부분을 실제로 실행했는가??

• Line coverage: 소스코드 한 줄 한 줄을 각각 다른 커버리지로 측정
• Function coverage: 명령어 수준까지는 알 필요없고, 어떤 함수들이 실행되었는지만 측정
• Branch coverage: 조건문에서 각 분기가 실행되었는지 측정
• Edge coverage: 베이직 블록(순서대로 실행되는 명령어) 사이의 transition을 측정 (가장 많이 사용됨)
• Path coverage: 전체 실행 경로 하나하나를 구분

그레이박스 퍼저는 다음과 같은 구조로 설계됩니다

1. Initial corpus: 최초 테스트할 입력값들
   • ex) 퍼징 캠페인을 실행하며 무작위로 생성할 파일의 소스
2. Seed queue: 코퍼스를 읽어서 저장하는 큐
3. Seed selector: 큐에서 시드 하나를 선택하는 싱글 스케줄링 알고리즘
4. Mutator: 선택된 시드를 변형하여 새로운 테스트 케이스 생성 
   • 시드 한 개에서 얼마나 많은 새로운 입력값을 만들어 낼거야? = power 스케줄링
   • 이 시드에서 새로운 입력값을 파생시킬 건데, 그땐 어떻게 할건지?
5. Test cases: 시드에서 파생된 새로운 입력값들
6. Code coverage 측정: Instrument가 커버리지를 측정
7. 가치 있는 테스트 케이스(코드 커버리지)는 다시 시드 큐에 추가하고 다음 퍼징에 활용 (interesting)

---

시드 스케줄링 전략

시드 큐에서 어떤 기준으로 시드를 선택할지 결정하는 것이 중요합니다.

• 라운드 로빈 스케줄링

모든 시드를 공평하게 돌아가면서 사용하는 방법입니다. 어느 한쪽에 치우치지 않고 돌아가면서 츠츠..

돌아간다는 뜻의 round, 서명하는 robin = 원탁에 앉은 사람들이 차례대로 서명을 했다라는 관용어 입니다

하지만 어떤 건 커버리지를 많이 확보한 시드, 어떤 건 조금만 확보한 시드들이 섞여 있습니다. 시드끼리는 중요도가 다른데..

이렇게 시드들의 중요도 차이를 고려하지 않는다는 단점이 있습니다.

• 랜덤 스케줄링

큐에서 무작위로 시드를 선택하는 방법입니다. 일반적으로 라운드 로빈보다는 조금 나은 성능을 보입니다.

시드의 중요도를 고려하지 않고 랜덤으로 뽑다 보니, 사이클이 여러 번 돌게 되면 선택이 된 횟수가 비슷해집니다. 

• Coverage Guided 스케줄링

위 스케줄링 방법들의 공통적인 한계점인 시드 가치 간과를 해결한 방법입니다.

시드들의 가치를 고려하여 가장 높은 커버리지를 가진 시드를 우선적으로 선택합니다. (seed3)

더 많은 코드를 실행하는 시드의 포텐셜(기대감)을 보고 사용하는 전략입니다.

• 휴리스틱 스케줄링

경험적으로 얻은 지식을 바탕으로 한 스케줄링입니다. (내가 해보니까 이렇게 하는게 좋더라~)

휴리스틱이란 어떤 알고리즘을 지칭하는 고유명사가 아니라 그냥 '내 의견'이 들어가면 다 이 단어를 사용합니다. 

많이 실행된 경로보다는 적게 실행된 경로를 트리거한 시드에 우선순위를 두는 전략입니다.

많이 실행된 경로는 흥미로운 게 나올 것 같지는 않고, 많이 실행이 안 된것은 테스트가 덜 된거니까 이걸 지지고 볶으면 더 재밌는게 나오지 않을까? 싶은거죠.

• Power 스케줄링

주어진 시드에서 생성할 테스트 케이스의 수를 결정하는 것입니다.

에너지를 왜 측정하냐면, 시드로부터 얼마만큼의 테스트 케이스를 파생시킬지 결정하기 위해서 입니다. 한 개의 시드로부터 몇 개의 테스트 케이스를 만들어야 하냐? 인거죠. 

알고리즘의 종류는 exploit, explore 이 있습니다. 

• Exploit: 시드의 가치(α)를 그대로 에너지 값으로 사용합니다. 
  • 시드 스케줄러가 꺼내온 시드인 i 를 가지고 와서 알파를 계산한다 (알파는 퍼저가 내부적으로 계산하는 시드의 가치)
  • ex)  p(i) = α(i) >> α(i)=64000이 그대로 에너지 값이 된다 >> 에너지 값만큼 테스트 케이스를 생성한다.
    = 하나의 시드로부터 서로 다른 테스트 케이스를 64000개 만드는 것
• Explore: α 값을 상수로 나누어 스케일링하여 더 빠른 시드 순환 효과를 냅니다. 
  • 위와 똑같은데, α을 거의 그대로 사용하는데? 𝜓 로 나누는 것만 차이
  • i번째 시드에 대한 점수 α를 거의 에너지 점수로 사용하나, 약간 1보다 큰 상수로 점수를 나눠줌으로써 작게 만드는 스케일링 방법입니다. 
  • 어떤 시드로부터 8000개만 만들자 → 시드의 순환을 더 빠르게 하는 효과 → 더 적은 시간에 더 많은 시드를 테스트 해볼수 있음

• exploit은 성능이 우수한 씨앗에 초점, explore은 많은 씨앗을 빠르게!

---

• Cut-off exponential schedule: 아직 많이 실행되지 않은 시드를 우선적으로 사용합니다. 
  • 베어내는 지수함수 같은 그래프

cut-off 지수 스케줄링의 식 (저도 아직 이해가 안 가서 첨부만 했습니다..ㅎㅎ)

• FAST 알고리즘: 시드 선택 시마다 에너지가 지수적으로 증가하되 f라는 것으로 스케일링해주며 조절합니다. 
  • 극단적으로 어떤 경로가 아주 자주 실행이 되면 f값이 매우 커질 것입니다. 
  • 너무 자주 실행되는 경로에 대해서도 에너지를 0으로 만들지 말고 조금은 테스트를 해보자는 것!
• Linear schedule: 시드가 선택되는 횟수에 따라 에너지가 선형적으로 증가합니다. (컨셉은 다 같은데 에너지가 증가하는 속도를 완만하게 하는 것)
• QUAD: 시드 선택 횟수의 제곱으로 증가

---

마지막으로 뮤테이션(Mutation) 기법에 대해 더 알아보겠습니다. 

뮤테이션은 주어진 시드로부터 새로운 테스트 케이스를 만들어내는 방식입니다. 유전 알고리즘에서 영감을 받아 개발되었습니다.

어떤 주어진 시드로부터 새로운 테스트 케이스를 만들어 내는 방식이 이것만 있는게 아닙니다. 

근데 특별히 테스트 케이스를 만들 때 뮤테이션을 사용한다면? '뮤테이션 기반의 퍼저' 라고 합니다. 

유전 알고리즘에서 영감을 받아 시작된 알고리즘 >> 크로스 오버 + 뮤테이션 연산을 가지고 처음 퍼저가 설계되었습니다. 

자주 사용되는 뮤테이션 전략은 아래와 같습니다. 

• 비트플립: 1→0, 0→1로 비트를 뒤집는 방법입니다. 비트 연산이기 때문에 연산 속도가 빠르고 작은 변화로도 큰 값 변화가 가능합니다.
• 바이트플립: 다른 바이트값을 삽입
• Arithmetic mutation: 바이트나 워드에서 작은 정수를 더하거나 빼기
• 흥미로운 값 삽입: 보통 경계값(boundary value) 등을 삽입 (경계 검증이 잘 이루어져야 합니다)
• Random value: 무작위 값 삽입
• Block mutation: n바이트를 한 번에 변경 (블록 단위로)
• Crossover: 서로 다른 두 시드의 일부를 결합하여 새로운 시드로
• 딕셔너리 기반: 사전 지식으로 효과적인 값들을 활용 (이런 값을 넣어두면 결과가 괜찮았던 것 같아~ 싶은 값들을 넣어놓은 것)
• Havoc mutation: 여러 기법을 조합

 

여기까지 퍼징에 관한 기본적인 개념이었습니다. 성능 향상 기법인 계측, 포크 서버등은 따로 찾아보시는 걸 추천합니다. 

sanitizer은 기회가 된다면 기본적인 내용만 정리해서 한 번 포스팅 해보겠습니다. 

이건 그저 배경지식일뿐 본격적으로 입문하려면 실습을 해야겠죠.. 저는 Fuzzing 101부터 해보려고 합니다. 

항상 언급하지만 저는 이 블로그를 배우는 과정에서 작성하기 때문에 오개념이 있을 수 있습니다.