※ 이 글은 chatGPT를 기반으로 작성한 글입니다.
Search-Based Fuzzing - The Fuzzing Book
Sometimes we are not only interested in fuzzing as many as possible diverse program inputs, but in deriving specific test inputs that achieve some objective, such as reaching specific statements in a program. When we have an idea of what we are looking for
www.fuzzingbook.org
Intro
① 다양한 프로그램 입력으로 퍼징(Fuzzing)을 수행하는 것뿐만 아니라 프로그램에서 특정 문(statement)에 도달하는 특정 테스트 입력에 대한 글이다.
② 프로그램 입력들을 효율적으로 테스트 및 파생시키기 위해서는 문제를 최적화할 수 있어야 하는데, 현실의 모든 문제에 대해서 최적화 알고리즘을 찾기란 불가능에 가깝다.
㉠ 예를 들어 x = 2(y+1)을 만족하는 x와 y값이 존재하는 지를 찾는다고 가정해보자.
ⓐ test_me 함수는 2개의 입력 인자를 갖고, 반환값으로 참 또는 거짓을 내보내는 함수이다.
ⓑ 해당 문제를 2차원 격자에서 해를 찾는 문제로 치환해보면 현재 위치에서 해를 찾기 위해 택할 수 있는 방향은 8가지이다.
| (x-1, y-1) | (x, y-1) | (x+1, y-1) |
| (x-1, y) | x, y | (x+1, y) |
| (x-1, y+1) | (x, y+1) | (x+1, y+1) |
㉡ 주어진 입력값들에 대해서 휴리스틱(heuristic) 함수의 적합도가 얼마인지에 따라 생성된 입력값이 최적인지를 판단할 수 있다.
ⓐ 격자 탐색 문제에서는 휴리스틱 함수의 가능한 각 입력에 대해 거리를 계산하여 적합도를 평가할 수 있다.
ⓑ 적합도가 0이 되었을 때 입력값이 최적임을 확인할 수 있다. 그래프를 통해서도 z값이 0일 떄 확인할 수 있다.
계측(Instrumentation)
① 일반적으로 분기 조건 바로 앞이나 뒤에 print 함수를 이용해 실행 중인 프로그램의 값을 관찰할 수 있다.
② 나중에 계측값을 이용하기 위해 변수나 자료구조에 저장하는 방법도 존재한다.
검색 문제로의 프로그램 입력 변환 (Representing Program Inputs as a Search Problem)
① 검색(또는 탐색)의 자동화를 위해 입력의 가능한 경우의 수를 특정 형태로 바꿔줘야 한다.
② 현재의 검색 공간(search space)는 격자이기 때문에 좌표값으로 표현할 수 있다.
③ 현재 위치에 대한 이웃한 좌표를 구하는 함수는 다음과 같다.
Hillclimbing the Example
①힐 클라이밍(Hill climbing)은 최적화 및 검색 알고리즘의 한 종류로 등산과 유사한 전략을 사용해 핼르 찾는 휴리스틱 검색 방법이다.
㉠ 이 알고리즘은 지역 최적해(local optimum, local optima)에 도달할 때까지 현재 해의 이웃한 해 중에서 더 나은 해를 반복적으로 선택한다.
② 힐 클라이밍의 작동 원리는 다음과 같다,
㉠ 초기 상태 선택: 문제 공간에서 임의의 시작점 선택
㉡ 이웃 솔루션 평가: 현재 상태의 이웃 상태들 중 하나를 선택 및 평가
㉢ 해 및 이웃 갱신: 선택한 이웃이 현재 해보다 적합도가 좋다면 현재 해를 해당 이웃으로 갱신한다.
㉣ 종료 조건 확인: 지역 최적해에 도달하면 알고리즘을 종료하고, 그렇지 않으면 2 단계로 돌아간다.
③ 무작위 값을 사용하기 위해 random 라이브러리를 불러오고, 출력될 로그 메세지의 숫자를 20으로 제한했다.
㉠ -1000~ 1000 범위의 랜덤한 x, y에서 휴리스틱 함수 get_fitness를 이용해 적합도를 구한 후, 보다 나은 적합도가 존재할 경우 갱신하는 방법을 취했다.
㉡ 로그 메시지를 출력하는 대신 자료구조에 저장해 그래프를 그려보았다.
㉢ 반복할 수록 더 좋은 최적값을 찾는 것을 볼 수 있다.
③ 힐 클라이밍 기법을 사용하기 좋지 않은 예시는 다음과 같다.
