AutoDiDact를 이용한 구조적 입력 축소 기법
델타 디버깅(Delta debugging)은 실패하는 입력에서 청크를 삭제하여 줄이고, 오라클이 실패가 지속됨을 확인해 줄 때만 해당 삭제를 유지합니다. 이는 입력의 길이에 의해서만 청크를 나누기 때문에, 식별자(identifiers)나 구분된 그룹(delimited groups)과 같은 단위들을 가로지르는 삭제가 발생하여 호출을 낭비하고 출력을 크게 남깁니다. 현재 최첨단 구조적 리듀서(structural reducers)들은 문법(grammars)이나 내장된 형식 지식(built-in format knowledge)을 제공함으로써 이러한 문제를 피합니다.
우리는 구조적 축소에 이 둘이 필요하지 않음을 보여줍니다. 중립어(neutral word)와 구분자 쌍(delimiter pairs)만으로 충분하며, 이 두 가지 모두 델타 디버깅이 오라클에게 이미 묻는 것("실패가 지속됩니까?")을 물어봄으로써 실패하는 입력으로부터 추론될 수 있습니다. 공백과 같은 중립어는 그러한 단위들 사이에 삽입될 때는 실패를 보존하지만 그 내부에서는 그렇지 않으므로, 입력을 토큰(tokens)으로 분할합니다. 구분자 쌍은 함께 추가되거나 제거될 때만 실패를 보존하는 두 개의 토큰이며, 따라서 이들이 둘러싸는 범위(span)는 하나의 단위로 축소될 수 있습니다.
우리는 이 두 가지 모두를 형식화하고, 오라클이 언제 이를 드러낼 수 있는지 명시하며, 유한한 횟수의 호출로 각각을 학습합니다. AutoDiDact는 계층적 델타 디버깅(hierarchical delta debugging, HDD)을 통해 결과적인 범위(spans)의 트리를 줄이고 각 토큰이 나타나는 모든 곳에서 크기를 축소합니다.
AutoDiDact는 18개 형식군(format families) 중 125개의 입력에 대해 75개에서 중립어를 찾습니다. 이들 입력에서는 바이트 레벨 델타 디버깅보다 출력이 83% 작고, 추론을 포함하여 기하 평균(geometric mean) 기준으로 호출은 37% 적습니다. 절감액은 입력 크기에 따라 증가하여, 최소 10 KiB의 입력에서는 각각 98%와 87%에 달합니다. 문법 없이도 AutoDiDact는 출력 크기 면에서 문법 기반 HDD와 동등하며, 호출 횟수는 3.85배 적고, C-Reduce의 언어 불가지론적 모드(language-agnostic mode)보다 54% 적은 호출을 사용합니다. 오라클만 필요하기 때문에, AutoDiDact는 퍼저(fuzzer)가 찾는 모든 것, 심지어 잘못된 형식의 입력까지도 최소화할 수 있습니다.