SW취약점분석

Fuzzing에서의 Code Coverage 논쟁

Fuzz testing 수행함에 있어서 자주 발생하는 질문이 있다. '언제 퍼징을 그만해도 될까?' 혹은 '지금까지 한 퍼징이 이 정도면 충분한가?'이다.

하지만 사실 이 질문은 애초에 답을 할 수 없는 질문이다. 예를 들어 아래와 같은 답변을 생각해보자.

"주어진 프로그램에 대해서, 실행할 수 있는 모든 입력을 다 넣어보자"

하지만 가능한 입력은 사실상 무한대에 가깝기 때문에 이런 종류의 '완벽한 퍼징'은 불가능하다. 결국 영영 끝나지 않는 퍼징을 무한히 반복해야 한다는 뜻이 된다.

또 다른 답변으로 "모든 결함을 다 잡았을 때 테스팅을 종료하자"라고 해보자.

이 문장은 그 자체로 모순인데, 임의의 프로그램에 대해 결함이 존재하는지 안 하는지, 몇 개가 존재하는지를 미리 알 수 있는 방법이 없다. 정답을 알고 있는 테스트용 바이너리의 경우 확인할 수 있는 좋은 목표가 될 수 있겠지만 사실 real world 프로그램으로는 도달할 수 없는 목표이기 때문에 실질적으로 쓸모가 없는 기준이다.


그렇다면, 퍼징을 언제 멈춰도 좋은지에 대해서 약간 관점을 다르게 생각해보자. 언제 멈춰야 할지를 정확하게 알 수 없다면 적어도 지금 Fuzzing iteration을 한 번 더 수행했을 때 과연 얼마만큼의 이득을 볼 수 있는가를 고찰해보자. 질문을 이렇게 바꿀 경우에, 테스트 입력을 하나 더 실행하기 위해서 필요한 비용과, 그것을 수행했을 때 얻을 수 있는 이익을 비교해볼 수 있다. 비용보다 이익이 더 크다면 테스트를 계속 수행해도 되고, 어느 순간 비용이 이익보다 작아진다면 테스트를 그만해도 좋을 것이다. 하지만 이 경우에도 문제가 있는데, 과연 그 '이득'과 '비용'을 정확하게 측정해서 비교할 수 있는지에 대한 것이다. 궁극적으로 하나의 Fuzz test case를 실행했을 때 기대하는 이득은 결함을 잡을 수 있는지, 없는지에 대한 것인데 마찬가지로 결함이 존재하는지 자체를 아직 알 수 없기 때문이다.

결국 '결함이 존재하는지'라는 정답 대신, 정답과 유사한 결론을 얻게 해 주는 대체적인 특징을 뽑아야 한다. 이때 보통 커버리지(coverage)라는 개념이 사용된다. 테스트가 실행되는 도중에 프로그램 내부 구조 중 어느 정도 비율을 달성하는지를 측정하는 것을 커버리지라고 한다. 


그간 Fuzz test 논문들은 통상적으로 Coverage를 높였다는 점을 입증하기 위해 애를 써왔다. 하지만 어떤 논문에서 "Coverage가 정말로 Bug find와 관련이 있는 거 맞음?"이라는 주장이 제기되었고, 이후 Bug find와 관련성이 있는 coverage가 무엇인지에 대한 관심이 대두되었다. 해당 논문들을 간단히 리뷰해보고 나의 생각을 정리해보고자 한다.


1. Code Coverage가 관련성이 적다는 주장

2018년에 발표된 Evaluating Fuzz Testing이라는 논문이 있다[1]. 해당 논문에서는 Fuzzing Paper 32개를 분석하여 각 저자들의 개별 실험 결과가 아닌, 통일된 조건에서 각각을 다시 평가(Evaluating)하고 비교 분석하였다. 다양한 도구들이 대부분 실패했던 부분에 대해 지적하면서 향후 도구들이 다루어야 할 포인트들을 제안하기도 하였다. 

이 논문의 7.4절에 보면, 많은 Fuzzer 도구들이 Code Coverage를 높이려고 애쓰는 경향이 있다고 지적한다. 하지만 Code Coverage에 향상이 있다고 해서 과연 버그를 더 많이 찾을 수 있는 것인가? 에 대해 의문을 제기한다. 실제로 AFLGo와 같은 경우 coverage를 높이는데 신경 쓰지 않는 대신 오류가 발생하기 쉬운 특정 부분을 더 집중적으로 공략함으로써 버그를 더 찾았다는 반례도 제시한다. 그리고 만약 coverage와 bug finding 사이에 상관관계(co-related)가 있다 하더라도, 그것은 굉장히 약할 것으로 추측한다. 그 주장의 근거는 Software Testing분야에서 출간된 다른 논문인 Coverage is Not Strongly Correlated with Test Suite Effectiveness [2]을 인용한 것이다.

그들은 "code coverage를 최대화하는 것이 버그를 찾는 것과 직접적으로 관련이 있다는 구체적인 이유에 대해서 아직 밝혀진 바 없다"는 주장을 펼친 것이다.


2. 다양한 Coverage Metrics이 Greybox Fuzzing에 미치는 영향 분석

한편 2019년 USENIX의 RAID(Research in Attacks, Intrusions and Defenses)에 발표된 Be Sensitive and Collaborative: Analyzing Impact of Coverage Metrics in Greybox Fuzzing 라는 논문[3]을 살펴보자.

이 논문에서는 퍼징에서 다양한 커버리지 요소들이 미치는 영향에 대한 (최초의) 체계적인 연구를 수행했다고 한다. 통칭 Coverage-guided greybox fuzzing 상황에서 이론적으로 다양한 커버리지 메트릭을 비교하는 데 사용할 수 있는 민감도(Sensitivity)의 개념을 공식적으로 제안하였다. 결국 A라는 요소가 B라는 요소보다 나은가? 라는 질문에 답할 수 있으려면, 특정 커버리지가 다음 테스트 케이스를 mutation 하는 상황에 어떤 영향을 미치는지를 알 수 있어야 하고 이를 민감도라고 정의한 것이다.


그런 민감도에 따른 몇 가지 커버리지 요소 조합을 제시하였다.

  • Branch Coverage
  • N-Gram Branch Coverage
  • Context-Sensitive Branch Coverage
  • Memory-Access-Aware Branch Coverage 

각 요소들의 Lattice 관계를 아래와 같이 표현할 수 있다.


이를 DARPA CGC 데이터 세트, LAVA-M 데이터 세트 및 실제 애플리케이션 세트 (총 221 개의 바이너리)를 사용하여 이러한 측정 항목에 대한 비교 분석을 수행하였다.

실험에서 살펴보고자 한 요소는 아래와 같다.

  • Unique crashes (얼마나 많이)
  • crash를 찾는데 걸린 시간 (얼마나 빨리)
  • seed count (sensitivity의 정량화)


그들은 시간 및 컴퓨팅 자원이 제한적인 조건 하에 퍼징을 수행하였으며 이때 내린 결론은 아래와 같다.

  1. 각각의 커버리지 유형들은 특정 유형의 조건 분기를 선택하는 데 있어 특수한 장점으로 작용할 수는 있다.
  2. 그러나 다른 모든 커버리지를 뛰어넘는 강력한 커버리지 요소를 찾을 수는 없었다. (결국 상황에 따라 다르단 뜻)

결론적으로 이 연구는 다양한 측정 항목의 조합을 통해 더 많은 Crash를 더 빠르게 찾을 수 있음을 보여주었으나, 구체적으로 어떤 조합이 가장 좋은지는 찾지 못했으며 그러므로 앞으로 그레이 박스 퍼징에 대한 더 많은 커버리지 요소의 조합을 발견하는 연구를 자극하기를 바란다고 읍소하고 있다.


3. 나의 결론

(이것은 나의 주관적인 결론이므로 어떤 확신적인 실험 결과가 아님을 참고)

나는 결론적으로 버그 탐색에 있어서 Coverage 달성은 필요조건(Necessary)은 맞지만, 충분조건(not sufficient)은 아니라고 생각한다. 결국 어떤 목표를 달성하기 위해서 꼭 필요한 조건이지만, 이 목표를 달성했다고 해서 주어진 결과를 항상 얻을 수는 없다는 것이다. 커버리지를 달성함으로써 해당 프로그램 구조에 존재하던 결함을 더 밝힐 수는 있지만, 어떤 프로그램에 대해서 특정한 수준의 커버리지를 달성했고 거기에 결함을 발견하지 못했다고 해서 결함이 없다는 것이 증명되는 것은 아닌 것이다. 

따라서 커버리지는 절대로 어떤 것도 보증하지 않는다. 커버리지를 특정 수준에 달성했기 때문에 결함이 있다, 없다는 결론을 내리는 것은 위험하다.

그럼에도 퍼징을 수행할 때 높은 커버리지를 달성할 것을 기대할 수는 있다. 커버리지를 달성하는 것이 그 자체로서 테스팅에 도움이 될 수는 있다. 하지만 종종 어떤 기준으로써 테스트 커버리지를 제시하게 되는 때가 있는데 이것은 그다지 좋은 선택이 아닐 것이다. 커버리지를 달성했다는 것은 테스팅을 잘했다는 사후 증거는 될 수 있지만, 처음부터 커버리지만을 달성하기 위해 테스팅을 하는 것은 실제로 그 프로그램의 품질을 높이는 데에 별 관계가 없을 수도 있는 것이다. 따라서 어떤 소프트웨어 프로세스 상에 특정한 숫자의 커버리지를 달성하기 위해서 테스팅을 더 하자, 혹은 덜하자 라고 말하는 판단은 잘못된 것일 수 있다. 실제로 커버리지를 100% 달성한다고 하더라도 해당 프로그램에 결함이 없다는 것을 증명할 수는 전혀 없다. 

결국 퍼징은 결함의 존재를 밝힐 수는 있지만, 결함이 없다는 것을 밝히기 위한 목적으로 사용될 수는 없다.


[1] Klees, George, et al. "Evaluating fuzz testing." Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. 2018. 

[2] Inozemtseva, Laura, and Reid Holmes. "Coverage is not strongly correlated with test suite effectiveness." Proceedings of the 36th international conference on software engineering. 2014. 

[3] Wang, Jinghan, et al. "Be sensitive and collaborative: Analyzing impact of coverage metrics in greybox fuzzing." 22nd International Symposium on Research in Attacks, Intrusions and Defenses ({RAID} 2019). 2019. 

[4] Paul Ammann and Jeff Offutt. Introduction to Software Testing (2nd Ed.)

Software Security Engineer

CPUU 님의 창작활동을 응원하고 싶으세요?

CPUU의 Daydreamin'
CPUU의 Daydreamin'
구독자 220

1개의 댓글

SNS 계정으로 간편하게 로그인하고 댓글을 남겨주세요.
새로운 알림이 없습니다.