AFL Fuzzer 관점에서 바라본 Instrumentation-guided genetic algorithm(계측 기반 유전 알고리즘)

 

 

AFL 퍼저는 Instrumentation-guided genetic 알고리즘을 사용하여 테스트 케이스를 생성하고, 변이하는 방식으로 동작.

Instrumentation-guided genetic algorithm - 계측 기반 유전 알고리즘

 

Instrumentation-Guided

AFL은 타겟 프로그램을 실행할 때 Instrumentation 기법을 사용하여 코드 커버리지를 추적함. 컴파일 시점에 삽입된 게측 코드 (QEMU(리눅스 커널 구동하는 가상머신)와 같은 동적 바이너리 Instrumentation 기법)을 활용하여 실행 흐름을 모니터링.

이를 통해 어떤 입력이 새로운 코드 경로를 트리거 했는지 알 수 있으며, 효과적인 변이가 가능함

Genetic Algorithm

AFL 특성상 기존의 퍼징 방식보다 진화적인 방식으로 입력을 선택하고 변이함. 이에 사용된 알고리즘이 유전 알고리즘.

- 초기 시드 설정
사용자가 제공한 시드 입력이나 AFL 자체가 생성한 기본 입력을 사용
- 변이 연산
AFL은 기본적인 변이 기법(Bit Flip, Byte Swap, Random Number Input)뿐만 아니라, 유전 알고리즘에서 사용하는 교차(Crossover) 기법도 사용. -> 좋은 특성을 가진 테스트 케이스 끼리 일부 데이터를 교환하여 새로운 입력을 생성.
- 적합도 평가
AFL은 새로운 입력이 실행 경로를 다양하게 탐색하는지 (새로운 코드 커버리지를 발견하는지)를 확인하여 적합도 평가. 더 많고, 새로운 경로를 찾은 입력을 좋은 입력으로 간주하여 변이 과정에서 더 많이 활용
- 선택 & 반복
높은 적합도를 가진 입력을 더욱 자주 선택하여, 변이와 교차를 반복하면서 점점 더 유용한 입력을 생성

정리

AFL 퍼저는 Instrumentation을 통해 실행 흐름을 분석하면서, 유전 알고리즘을 활용하여 효과적으로 테스트 입력을 최적화 함. 이렇게 함으로써 무작위 퍼징 방식보다 훨씬 효율적으로 시스템의 취약점을 찾아낼 수 있다.

실행 경로를 더 깊이 탐색하면서 크래시를 유발한 가능성이 높은 입력을 빠르게 찾음.