DRReduce: 의존성 재구성을 통한 구문 가이드 프로그램 축소 성능 향상

프로그램 축소 (Program reduction)는 오류를 유발하는 대규모 프로그램을 최소한의 재현 가능한 테스트 케이스로 단순화하는 기술입니다. CReduce와 같은 언어 특화 도구들은 C/C++의 깊은 의미론적 지식 (semantic knowledge)을 활용하여 강력한 성능을 달성하지만, 단일 언어 계열에 밀접하게 결합되어 있습니다. Perses와 같은 언어 불가지론적 (Language-agnostic) 축소기들은 모든 문법에 대해 구문 가이드 탐색 (syntax-guided search)을 적용함으로써 이 문제를 해결하지만, 근본적인 한계를 공유합니다. 즉, 노드나 서브트리를 단독으로 삭제하면 의미론적 일관성 (semantic coherence)이 깨지는 경우가 많아, 속성 검사기 (property checker)가 삭제를 거부하게 만들고 축소기가 백트래킹 (backtrack)을 강제하게 하여, 전반적인 축소 효과와 효율성을 제한한다는 점입니다.

본 논문에서는 언어 불가지론적 구문 축소에 가벼운 의미론적 계층인 의존성 재구성 (dependency reconstruction)을 추가하여 이러한 격차를 해소하는 프레임워크인 DRReduce를 제안합니다. 의존성 재구성은 삭제로 인해 깨진 프로그램 의존성을 복구하여 중간 프로그램의 의미론적 유효성 (semantic validity)을 보존하고 속성 검사기의 수락률을 높입니다. DRReduce는 입력 프로그램으로부터 의미론적 의존성 그래프 (semantic dependency graph)를 구축하고, 의존성 재구성을 통해 의미론적으로 일관된 삭제를 수행하며, 추가적인 최소화 작업은 구문 가이드 축소기 (syntax-guided reducer)에 위임합니다.

우리는 C와 Java를 위해 DRReduce를 구현하였으며, 실제 버그를 유발하는 프로그램들을 대상으로 평가를 진행했습니다. 최신 기술 (SOTA) 구문 가이드 축소기들과 비교했을 때, DRReduce는 Perses, WDD, CDD 대비 각각 평균 51.9%, 14.9%, 19.8%의 크기 축소 효과를 달성하였으며, 대부분의 프로그램에서 더 빠르게 축소를 완료했습니다. 언어 특화 도구들과 비교했을 때, DRReduce는 어떠한 언어 특화 변환 규칙 없이도 CReduce 및 Latra와 대등한 결과를 얻었으며, 평균적으로 CReduce보다 3.3배, Latra보다 1.2배 높은 효율성을 보였습니다. 절제 연구 (Ablation study)를 통해 의존성 재구성이 쿼리 호출을 80.2%, 축소 시간을 58.7%, 최종 토큰 수를 55.1% 이상 감소시킨다는 것을 확인했습니다.