*
본 게시글은 Fuzzing: A Survey for Roadmap Survey 논문을 토대로
동향을 분류, 재구성, 보충하였으니 자세한 내용이 궁금하다면 해당 논문을 살펴보길 바란다.
* Fuzzing과 AI에 대한 동향 조사를 수행한 발표자료를 게재함.
본 게시글은 Fuzzing : A Survey for Roadmap 을 토대로 재구성하였음
필자 또한 배우고 있는 입장에서 이해한 바를 작성하였기 때문에 자료를 100% 믿지는 말 것.
Q2. 퍼징 프로세스 최적화 기법, Fuzzing Theories
첫 번째로 살펴볼 것은 퍼징 프로세스 최적화 기법(Fuzzing Theories)이다.
해당 기법은 입력 공간과 결함 공간 사이의 간격을 줄이고자 하는 기법으로, 풀어 말하자면 무작위가 아닌 Fuzzer가 취약한 코드가 있을만한 공간만 탐색하자는 것이다.
하지만 취약한 코드가 어디있을지 알 방법이 없어 확정적으로는 공간사이의 간격을 줄일 방법이 없다.
그렇다고 사람이 일일이 알려줄 수는 없지 않는가.
퍼징 프로세스 최적화는 취약한 코드가 있을 곳을 fuzzer가 경험적으로 습득하도록 최적화 문제 솔루션을 접목한 것이다.
본 글에서는 최적화 문제를 기계학습을 통해 풀어낸 기법만을 다루었으며 상단 표의 연구들은 이러한 문제를 해결하기 위해 딥러닝, 강화학습, 그외의 기계학습을 사용하여 해결하였다.
퍼징 최적화 기법들은 퍼징이 취약점을 보다 쉽게 찾아내도록 Seed Set, Seed Schedule, Byte Schedule, Mutation Schedule에 다양한 최적화 문제 솔루션을 적용하여 성능을 개선하고자 하는데 그중에서 머신러닝이 사용된 것은 seed schedule과 byte schedule이니 이를 중심으로 살펴보겠다.
Q2-0. 퍼징 프로세스 최적화 - 왜 퍼징 프로세스 자체는 최적화할 수 없을까?
퍼징 프로세스 최적화 기법을 소개하기에 앞서 드는 의문을 먼저 해소하고자 한다.
위에서 퍼징 최적화 기법들은 Seed Set, Seed Schedule, Byte Schedule, Mutation Schedule 에 대해 최적화하고자 퍼징의 성능을 개선하고자 한다고 언급하였다. 하지만 굳이 이렇게 퍼징을 나누어서 최적화를 수행해야 할까? 퍼징 프로세스 자체를 최적화하면 간단한 일 일텐데 말이다.
답은 퍼징 프로세스 최적화라는 것 자체가 불가능하기 때문이다.
최적화를 하기 위해서는 대상에 대한 확률 분포를 얻을 수 있어야 하는데 발견되지 않은 코드의 범위나 버그는 어디에 있는지 알 수가 없어 최적화 문제를 공식화할 수 없다. 버그를 찾으려면 최적화 문제를 공식화해야 하는데, 최적화 문제는 버그를 찾아야만 공식화할 수 있다니.. 아이러니한 상황이 되어버렸다.
각 코드 라인을 수행하여 해당 입력의 버그 트리거 여부를 알기 전까지는 퍼징 프로세스 자체를 최적화하는 방법을 수학적으로 구할 수가 없어 퍼징 프로세스 최적화 기법은 버그 트리거 여부가 기준이 되지 않도록 대략적, 부분적으로 퍼징 프로세스를 공식화하는 연구가 수행되었다.
Q2-1. 퍼징 프로세스 최적화 - Seed Schedule의 최적화
seed schedule 최적화 기법은
1. 다음 라운드에서 어떤 시드를 선택할 것인지
2. 선택된 시드의 시간 자원(선택한 시드 변경 횟수)를 어떻게 할애할지에 대한 문제를 해결하고자 한다.
seed schedule의 문제 자체는 명확하나 PUT와 bug의 복잡성으로 인해 쉽게 해결할 수 없어 최적화를 위한 솔루션이 필요하다.
seed schedule 최적화는 Markov Chain을 사용하는 state transition 최적화와 MAB 알고리즘을 사용하는 state transition으로 구분할 수 있다.
먼저 Markov Chain 최적화 알고리즘을 state transition 최적화를 살펴보자. 해당 기법은 코드 커버리지와 같은 실행 상태(execution state)를 기반으로 확률 분포를 구성하며, 확률 분포를 Markov Chain기법을 통해 state transition을 공식화하고 최적화한다. 공식화한 state transition은 fuzzing이 발견되지 않은 state를 효율적으로 탐색하도록 안내하게 된다.
Markov Chain을 사용한 state Transiton은 state를 CFG의 블록단위로 보느냐, path 단위로 보느냐에 따라 Block Transition과 Path Transition으로 나눌 수 있다.
Block Transition 최적화 기법은 CFG 기본 블럭을 상태(state)로 정의하며 block에서 block으로 상태 전이(state transition)를 수행한다.
그렇다면 이 state와 state transition에 따라 기법이 나뉘는 이유는 무엇일까? Marcov Chain은 상태(state)와 상태 전이(state transition)를 토대로 상태 전이 확률(state transition probability)을 계산하고 다음의 상태를 예측하는데 사용하기 때문이다.
이때, 상태와 상태 전이는 해당 CFG 기본 블록이 탐색된 비율로 측정을 하므로 프로그램을 실행해야만 전이 확률를 얻을 수 있다. 퍼징을 시작할 때, transition probability는 무작위로 탐색하다가 점차 markov chain기법을 토대로 전이 확률이 낮은 방향(도달하기 어려운 코드 영역이 있는 곳)으로 최적화를 수행하게 된다.
Path Transition 최적화 기법은 상태(state)를 execution path, 상태 전이(state transition)을 기존의 입력을 토대로 새로운 입력을 생성하는 mutation으로 정하여 최적화를 수행한다.
하지만 Markov Chain을 사용한 상태 전이 방법에는 한계가 있으니.. 상태 전이를 위해서는 모든 상태 간의 상태 전이 확률을 구해야한다는 것이다. 하지만 fuzzing에서 모든 코드영역에 대한 상태를 탐색하는 것은 불가능한 일. 결국 각 block transition과 path transition 기법을 이론 그대로 사용할 수 없다.
때문에 markov chain based block transition 기법들은 탐색되지 않은 블록으로 전환할 때 통계적인 수치를 측정하는 것으로 개선하며, path transition은 모든 상태 전이 확률을 구하기 위해 라운드로빈 스케쥴링으로 동일하게 시드 변경 횟수(time budget)을 할당하여 탐색하도록 하여 어떻게든 state transition 기법을 구현하였다.
하지만 해당 방식들은 효율적인 것과는 거리가 멀다. 통계적인 수치 측정은 정확한 수치가 될 수 없으며, 동일한 time budget 할당은 더더욱 효율적이지 않다.
결국 seed schedule 기법은 최적화 기법에서 더 나아가 모든 시드를 탐색해야할지 특정 시드에 집중할지에 대해 (Exploration vs. Exploitation)에 대한 해결이 필요하다.
근래에 나온 퍼징 프로세스 최적화는 바로 이 exploration vs. Exploitation 문제를 해결하고자 한다.
MAB를 사용한 state Transition 기법들은 그러한 exploration vs. Exploitation 문제를 MAB(Multi-Armed Bandit) 강화학습 알고리즘을 통해 MAB 알고리즘을 사용한 Fuzzing 기법들은 모두 path transition을 기반으로 공식화 최적화한다.
여기서 seed는 fuzzing을 시도하는 exploration이며 해당 시드를 토대로 발견되는 새로운 경로를 보상으로 취급한다. MAB는 보상의 기대치를 확인하였을 때, 가장 높은 보상 기대를 갖는 seed만을 선택(exploitation)하도록 경험적으로 학습하는 것으로 시드 탐색에 대한 문제를 해결하였다.
Q2-2. 퍼징 프로세스 최적화 - Byte Schedule의 최적화
Fuzzer 내에서 byte schedule은 변이될 시드의 바이트를 선택하는 빈도를 결정하는데 사용된다. 기본적으로 fuzzer는 무작위하게 결정하거나 코드 커버리지와 같은 실행정보를 토대로 휴리스틱하게 결정하게 되는데 아무래도 byte schedule이 seed schedule보다 path constraint라던가 data low와 같은 프로그램 동작에 대해 정교한 동작을 요구하다보니 무작위에 가까운 schedule로는 제대로된 결정을 내리지 못한다.
이를 해결하기 위해 byte schedule을 최적화하기 위한 연구들은 importance of bytes, fuzzer 내에서 byte의 변화가 퍼징 프로세스에 어떤 영향을 미치는지 확인하는 것으로 문제를 해결하고자 한다.
Byte Schedule 최적화 기법은 importance of byte에서 어떤 영향을 미치는 대상을 정하는지에 따라서 branch behavior에 대한 영향과 seed 적합성 판단에 대한 영향으로 나뉜다.
전자 방식은 선택한 바이트에 따른 분기점에 대한 행동변화를 살펴보는 것으로 최적화하는 기법이다. 보통 해당 방식은 NEUZZ[5]와 MTFuzz[6]와 같이 딥러닝 기법으로 모델링한다. 해당 기법을 딥러닝 모델로 모델링하는 이유는 Byte의 그래디언트가 클수록 작은 perturbation은 분기점에 대한 행동에 상당한 차이를 초래하게 되는데 이 DL 모델의 그래디언트를 토대로 importance of byte를 정량화할 수 있다,
후자 방식은 바이트가 선택한 시드가 적합한지에 대한 적합성 판단에 어떤 영향을 미치는지 여부를 확인하는 것으로 최적화하는 기법이다.
해당 방식에서 AFLChurn은 ACO(Anto Colony Optimization) 알고리즘을 통해 byte의 변화가 시드의 적합성 정도를 향상하였을 때, 바이트 점수를 높이도록 하며 개미의 호르몬처럼 시간에 지남에 따라 바이트를 감소시키는 것으로 byte가 치중되어 local optimum에 빠지지 않도록 하는 기법이다.
이것으로 본 장에서는 퍼징 프로세스 최적화 기법을 사용한 퍼징 기법에 대해서 다루었다.
위에서 언급한 논문들은 reference에 링크로 연결해두었으니 관심이 있다면 확인해보시길.
[Reference]
[1] 2016 CCS, Coverage-based Greybox Fuzzing as Markov Chain (AFLFast)
[2] 2017 NDSS, Vuzzer: Applicaton-aware evolutionary fuzzing
[3] 2018 S&P, Angora: Efficient Fuzzing by Principled Search
[5] 2019 S&P NEUZZ: Efficient Fuzzing with Neural Program Smoothing.
[7] 2021 USENIX, SyzVegas: Beating Kernel Fuzzing Odds with Reinforcement Learning
[8] 2021 NDSS, Reinforcement Learning-based Hierarchical Seed Scheduling for Greybox Fuzzing (AFL_HIER)
[9] 2020 FSE, MTFuzz: Fuzzing with a multi-task neural network.
[10] 2021 CCS, Regression Greybox Fuzzing. (AFLChurn)
'동향 및 조사' 카테고리의 다른 글
| Fuzzing + AI 동향 조사 (3) Input space 탐색 기법 (0) | 2022.03.28 |
|---|---|
| Fuzzing + AI 동향 조사 (1) 개요 (0) | 2022.02.17 |