Abstract

체크섬은 데이터의 동일성을 확인하는 효율적인 방법으로, 퍼징 도구 AFL에서는 커버리지 비교와 입력 최적화 작업에 체크섬을 활용해 메모리 접근을 최소화한다. 입력 최적화 작업은 퍼징의 성능을 크게 좌우하기 때문에, 다중 지향성 퍼징의 개발에 있어서 AFL의 체크섬 알고리즘이 방해를 받지 않게 주의해야 한다. 퍼징 개발에 있어 이처럼 주의할 요소를 파악하기 위해서는 실험 중 생성되는 데이터를 효과적으로 시각화하는 자세가 필요하다.

본문

체크섬은 데이터의 동일성을 효율적으로 확인하는 방법이다. 데이터를 해시 함수에 통과시켜 생성된 작은 값을 저장하고, 이후 비교 대상 데이터의 해시 값과 비교하여 두 데이터가 같은지를 판단하게 되며, 보통 데이터의 변경 여부를 감지하는 데 쓰인다.

퍼징 도구인 AFL에서 체크섬은 변형 전후의 두 입력이 같은 커버리지를 가지는지 확인할 때 쓰인다. 커버리지는 프로그램 실행 중 소스 코드에서 실제로 실행된 부분을 의미한다. AFL은 초기 입력값을 변형시켜 새로운 커버리지를 생성할 입력값을 만들어내 저장하고, 이를 반복해 다양한 실행 경로로 프로그램을 검사한다. 입력값의 일부분을 변형했을 때 새로운 커버리지를 만들 확률을 높이기 위해서는, 반대로 잘라내도 커버리지에 영향이 없는 부분을 찾아 제거하는 ‘트리밍 (trimming)’ 작업이 선행되는 게 중요하다. AFL은 매 입력값의 커버리지를 64KB 메모리에 저장하는데, 두 커버리지를 비교할 때는 메모리 모두를 비교하는 대신, 각각의 32비트 체크섬을 비교한다.

체크섬의 장점은 데이터를 자주 비교해야 하는 상황에서 메모리 접근을 최소화할 수 있다는 점이다. AFL을 직접 실행해본 결과 저장되는 입력값 수는 프로그램 실행 횟수의 1만 분의 1에 불과하다. 따라서 저장되는 입력값의 커버리지는 수만 번 다른 커버리지와 비교된다는 것인데, 체크섬을 활용하면 비교 때마다 해당 데이터를 메모리에서 읽어올 필요 없이, 해시 값만 가져오면 되므로 효율성이 크게 향상된다. 이런 장점으로 체크섬은 트리밍 이외에도, 같은 입력에서 일관성 있게 같은 커버리지가 나오는지 검사하는 안정성 확인 (calibration) 작업 등 많은 곳에 사용된다. 반면, 메모리의 직접 비교는, 두 커버리지가 같은지를 비교하는 게 아닌 문제, 예를 들어 여태까지 실행된 적 없는 코드가 이번 커버리지에 들어 있는지 확인하는 문제 등에서 사용된다.

AFL 위에 새로운 전략을 구현할 때는 AFL의 체크섬 알고리즘이 방해받지 않도록 주의해야 한다. 현재 개발 중인 다중 지향성 퍼징은 시간에 따라 커버리지의 일정 부분을 무시하도록 작동 중이다. 만약 원래 AFL처럼 시드 생성 시의 체크섬을 그대로 불러와 현재 커버리지의 체크섬과 비교한다면, 시드 생성 시점에서는 무시하지 않았지만 지금은 무시하도록 설정한 커버리지 부분이 체크섬에 반영된 상태로 비교가 이루어져 원하지 않는 동작이 벌어질 수 있다. 따라서 커버리지에서 무시할 부분이 바뀌는 시간대마다 모든 시드의 체크섬을 다시 계산하도록 해야 한다. 이러한 유연한 체크섬 설계는 우리의 기법이 AFL의 다른 부분, 예를 들어 트리밍과 안정성 확인 등에 나쁜 영향을 주지 않고, 원하는 효율성만 끌어올리는 데 핵심적인 역할을 한다.

새로운 기술을 도입할 때 AFL의 체크섬 알고리즘처럼 생길 수 있는 문제를 빠르게 감지하는 방법은 무엇일까? 핵심은 퍼징 중 생성되는 데이터를 한눈에 볼 수 있도록 시각화하는 것이다. 개발 도중 체크섬 알고리즘의 문제를 발견한 계기는 시드의 최신 수정 시간 기록을 분석하면서였다. 수정 시간 기록은, 실험이 끝나며 원래 휘발될 정보를 따로 기록하도록 한 텍스트 문서였는데, 단순히 시드의 번호와 수정 시간의 나열이라, 보는 것만으로 문제를 직관적으로 파악하기 어려웠다는 점이 아쉬웠다. 만약 시드 저장 시간의 이질적인 패턴을 강조하는 그래프를 실험마다 출력했다면, 문제를 훨씬 빠르게 인식할 수 있었을 것이다. 따라서, 실험 중 최대한 많은 정보를 기록하는 것뿐만 아니라, 이를 효과적으로 시각화하는 프로세스가 필수적이라고 느꼈다. 이를 통해 앞으로 퍼징 도구를 건드릴 때 체크섬 말고 또 뭘 주의해야 할지, 이상 요소를 빠르게 감지할 수 있을 것이다.