기존 문제
- 경로 다양성 부족
  - 현재 [[fuzzing|퍼징]] 기법은 목표 지점에 도달하는 것을 중점으로 함
  - 따라서 다양한 경로를 충분히 확보하지 못하기 때문에 특정 경로를 발견하지 못할 가능성 높음
- 에너지 할당 편향
  - 기존의 거리 기반 에너지 할당은 특정 목표에 편향되어 다양한 목표에 에너지를 충분히 할당 못함
제안
- 경로 다양성 메트릭 도입
  - 목표 지점 별 [[virgin_bits|virgin map]]을 유지/관리
  - 시드 실행 시, 여러 virgin map을 비교하여 각 virgin map 별로 새로운 [[커버리지|커버리지]] 유무 확인
  - 단, 목표 별 virgin map은 오버헤드가 너무 커서, 유사한 목표 지점은 클러스터링 (A 목표 virgin map이 업데이트될 때, B 목표 virgin map이 업데이트 되면 이 둘은 하나로 묶기) ㅅㅇ. 묶는다는 게 정확히 뭔가? virgin map update는 수시로 이뤄지는데 그러면 그룹도 수시로 풀렸다 묶였다 변하나?
- Critical blocks
  - 가장 가까이 다가간 블록들을 명시, 지나는 시드에 에너지
AFLRun
- 경로 다양성
- 공평 에너지 할당
AFLRun-
- 공평 에너지 할당
AFLRun–
- 공평 에너지 할당 (중요 블록 X)

Note

[[favored|favored]]를 사용. favored일 시 에너지 score대로, 아닐 시 1/20을 곱함. Besides a target virgin map for each cluster introduced in §5.2, AFLRUN also maintains a top-rated array for each cluster, similar to the original top-rated array discussed in §2.1.

When a new seed is added to the corpus, a set of top-rated arrays are selected using Algorithm 5, and we update these top-rated arrays using the same method as [[AFL++|AFL++]].

Using these top-rated arrays, we can select a set of favored seeds. We can apply the queue culling algorithm, similar to AFL++, on top-rated arrays of all clusters to select the favored seeds.

For each top-rated array, we use the queue culling algorithm from AFL++ to select a set of favored seeds, and we then take the union of each set of favored seeds from each top-rated array to obtain the total set of favored seeds.

내 생각 (7월)

[[AFLRun과 Topuzz 비교|AFLRun과 Topuzz 비교]] 논문 “Toward Unbiased Multiple-Target Fuzzing with Path Diversity"를 각 챕터별로 정리한다.

Abstract

AFLRUN이라는 새로운 퍼징 솔루션을 제안한다. 이는

target path-diversity metric
and unbiased energy assignment 즉 목표 경로 다양성(metric)과 공정한 에너지 할당을 특징으로 한다.

각 목표에 대해 추가 [[virgin_bits|버진 맵]]을 유지하여 경로 다양성을 높이고, 공정한 에너지 할당 전략을 통해 각 목표에 대한 공평성을 보장한다. 실험 결과, AFLRUN은 기존 퍼저보다 더 많은 취약점을 더 빠르게 발견하고, 29개의 새로운 취약점을 찾아냈다.

1. Introduction

퍼징은 프로그램의 행동을 다양한 입력으로 테스트하여 이상 현상을 찾아내는 기법이다. 최근에는 특정 코드 위치를 목표로 하는 Directed Fuzzing이 주목받고 있다. 하지만, Directed Fuzzing은 종종 목표 위치를 자주 테스트하더라도 복잡한 취약점을 발견하지 못하는 한계를 가지고 있다. 또한, 여러 목표를 퍼징할 때 에너지 할당의 공정성이 보장되지 않아 일부 목표에 충분한 퍼징이 이루어지지 않는다.

preconditioned flaw activation, or PFA

post-target activation, or PTA

2. Background

2.1 Coverage-guided Fuzzing

커버리지 기반 퍼징은 초기 시드 입력을 변형하여 테스트 케이스를 생성하고, 새로운 동작을 유발하는 테스트 케이스를 시드로 저장하여 [[커버리지|커버리지]]를 확장하는 방식으로 작동한다. [[AFL++|AFL++]]은 실행 경로를 기록하고, 새로운 비트를 덮는 테스트 케이스를 시드로 추가하여 커버리지를 향상시킨다.

2.2 Directed Fuzzing

Directed Fuzzing은 특정 목표 위치를 테스트하는데 중점을 두고, 시드의 목표 위치 근접도를 평가하여 에너지를 할당한다. 이 접근법은 목표 위치에 더 가까운 시드에 더 많은 에너지를 할당하여 목표 위치의 취약점을 빠르게 발견하는 것을 목표로 한다.

3. Motivation

복잡한 취약점을 발견하기 위해서는 목표 경로 다양성을 높이는 것이 중요하다. 또한, 여러 목표를 퍼징할 때 공정한 에너지 할당이 필요하다. 기존의 Directed Fuzzing은 이러한 요구를 충분히 충족하지 못한다.

4. Design Overview

AFLRUN의 설계는 목표 경로 다양성과 공정한 에너지 할당을 중심으로 이루어져 있다. 각 목표에 대한 [[virgin_bits|버진 맵]]을 유지하고, 각 시드에 에너지를 공정하게 할당하여 목표 경로 다양성을 향상시키고 목표 간의 공정성을 보장한다.

5. Target Path-Diversity Metric

목표 경로 다양성을 높이기 위해 여러 [[virgin_bits|버진 맵]]을 유지한다. 이를 통해 목표를 다루는 경로의 다양성을 높이고, 복잡한 취약점을 발견할 확률을 높인다.

6. Unbiased Energy Assignment

공정한 에너지 할당을 통해 각 목표에 대한 탐색과 활용을 공평하게 만든다. 이를 위해 각 목표 블록에 가중치를 할당하고, 시드의 에너지를 이 가중치에 따라 분배한다.

7. Evaluation

AFLRUN의 성능을 평가하기 위해 표준 벤치마크와 실제 프로그램을 사용하였다. 평가 결과, AFLRUN은 기존 퍼저보다 더 많은 취약점을 더 빠르게 발견하였다. 또한, 29개의 새로운 취약점을 발견하였으며, 그 중 8개는 CVE로 등록되었다.

8. Discussion

AFLRUN의 범위와 한계를 논의하고, 향후 개선 방안을 제안한다. 경로 다양성 메트릭과 공정한 에너지 할당의 유효성을 강조하면서, 시드 폭발 문제와 로컬 최적화 문제를 해결하기 위한 잠재적 솔루션을 제시한다.

커버리지 메트릭을 개선하거나 Directed Fuzzing을 향상시키기 위한 기존 연구를 검토한다. AFLRUN은 이러한 연구들을 기반으로 하여 새로운 커버리지 메트릭과 에너지 할당 전략을 제안한다.

10. Conclusion

AFLRUN은 목표 경로 다양성과 공정한 에너지 할당을 통해 Directed Fuzzing의 한계를 극복하고, 더 효과적으로 취약점을 발견하는 새로운 퍼징 기법이다. 실험 결과, AFLRUN의 우수성이 입증되었으며, 이는 향후 퍼징 연구에 중요한 기여를 할 것이다.

Park, Geon/AFLRun 논문