ExplainFuzz: 확률적 회로 (Probabilistic Circuits) 를 활용한 설명 가능하고 제약 조건 기반의 테스트 생성

이 문서는 소프트웨어 테스트 및 디버깅에서 생성된 테스트 입력의 구조를 이해하고 설명하는 것이 중요하다는 점에 착안하여, ExplainFuzz라는 새로운 테스트 생성 프레임워크를 제안한 논문입니다. 기존 방법론의 한계를 극복하고, 문법 (Grammar) 을 인지하면서도 맥락에 민감한 확률적 의존성을 학습할 수 있는 모델을 제시합니다.

1. 문제 정의 (Problem)

소프트웨어 테스트, 특히 컴파일러나 데이터베이스와 같은 복잡한 구조화된 데이터를 요구하는 시스템의 테스트를 위해서는 고품질의 테스트 입력 생성이 필수적입니다. 그러나 기존 방법론들은 다음과 같은 근본적인 한계를 가지고 있습니다:

• 기존 문법 기반 Fuzzer (예: Grammarinator): 문법적으로 유효한 입력을 빠르게 생성할 수 있지만, 입력 분포에 대한 체계적인 제어가 부족합니다. 무작위 확률적 확장이나 국소적인 시드 (seed) 변형에 의존하기 때문에, 자연스럽지 않거나 형식이 잘못된 (ill-formed) 입력을 생성하며, 문맥에 민감한 확률적 의존성 (예: SQL 에서 GROUP BY 가 있으면 HAVING 이 나올 확률이 높아지는 것) 을 포착하지 못합니다.
• 확률적 문맥 자유 문법 (pCFG): 규칙에 확률을 부여하여 생성을 편향시킬 수 있으나, 생성 규칙 간의 독립성을 가정하므로 문맥 의존성을 모델링하지 못합니다.
• 확률적 회로 (PC) 중 문법 무지 모델 (PC-HMM 등): 표현력은 높지만 문법적 유효성을 보장할 수 없어 컴파일러 테스트에 부적합합니다.
• 대규모 언어 모델 (LLM): 잘 형성된 입력을 생성할 수 있으나, 블랙박스 특성을 가지며 해석 가능성 (explainability) 이 부족하고, 고밀도/고다양성 테스트 생성에 필요한 계산 효율성이 떨어집니다.

결론적으로, 해석 가능하고 (explainable), 제어 가능하며 (controllable), 문법적 유효성을 유지하면서 맥락 의존성을 학습하는 테스트 생성 방법이 부재했습니다.

2. 방법론 (Methodology)

저자들은 **확률적 회로 (Probabilistic Circuits, PCs)**를 활용하여 위 문제를 해결하는 ExplainFuzz를 제안합니다. PCs 는 복잡한 확률 분포를 계산 그래프로 표현하여 효율적인 추론과 해석 가능성을 제공합니다.

주요 프로세스

1. 전처리 (Preprocessing):

   • ANTLR 문법을 입력받아 문법-aware PC 로 변환할 수 있도록 경량 리팩토링을 수행합니다.
   • 리터럴 (literal) 을 토큰으로 대체하고, 시드 입력을 Grammarinator 등을 통해 증폭 (amplification) 한 후, 구체적인 값 (lexemes) 을 토큰 (tokens) 으로 익명화 (anonymization) 하여 학습 데이터를 준비합니다.

2. 문법 인지 확률적 회로 컴파일 (PC Compilation):

   • 컨텍스트 자유 문법 (CFG) 을 기반으로 문법-aware PC 를 하향식 (bottom-up) 방식으로 컴파일합니다.
   • CYK 알고리즘과 유사하게, 시퀀스의 시작과 끝 위치, 그리고 비단말 기호 (non-terminal) 를 기반으로 합 (sum) 노드와 곱 (product) 노드를 구성하여 모든 가능한 입력 시퀀스를 모델링합니다.

3. 학습 (Training):

   • 준비된 익명화된 시드 입력 데이터셋으로 PC 를 학습시켜, 문법 토큰 간의 확률적 분포와 맥락 의존성을 학습합니다.

4. 추론 및 생성 (Inference & Generation):

   • 해석 가능한 쿼리 (Explainable Inference): 학습된 분포를 분석하여 특정 토큰의 등장 확률, 조건부 확률 (예: GROUP BY 가 있을 때 HAVING 의 확률) 등을 계산할 수 있습니다.
   • 제약 조건 기반 샘플링 (Constraint-Conditioned Sampling): 사용자가 특정 제약 (예: "JOIN 절이 반드시 포함되어야 함") 을 지정하면, PC 는 해당 조건을 만족하는 입력을 생성합니다. 이는 단순한 시드 변형이 아닌, 학습된 분포 내에서 체계적으로 탐색하는 방식입니다.
   • 구체화 (Concretization): 생성된 토큰 시퀀스를 실제 실행 가능한 입력 (SQL 쿼리, XML 문서 등) 으로 변환하기 위해 도메인별 구체화 (concretizer) 를 적용합니다 (예: SQL 은 스키마 기반의 실제 컬럼명 매핑).

3. 주요 기여 (Key Contributions)

1. 해석 가능하고 제어 가능한 테스트 생성: PC 를 활용하여 입력 분포를 투명하게 분석하고, 제약 조건을 통해 생성 방향을 체계적으로 제어할 수 있는 프레임워크를 제시했습니다.
2. 향상된 일관성과 현실성: pCFG, 문법 무지 PC, LLM 보다 낮은 퍼플렉시티 (perplexity) 를 달성하여, 맥락에 민감한 확률적 의존성을 더 잘 포착하고 현실적인 테스트 입력을 생성함을 증명했습니다.
3. 목표 지향적 생성 (Targeted Generation): PC 의 조건부 샘플링 기능을 통해 특정 구조 (예: 특정 SQL 절 포함) 를 가진 입력을 생성하여, 버그 발견률과 입력 다양성을 크게 향상시켰습니다.
4. 버그 발견 효과성 증대: 기존 문법 기반 변형 Fuzzer (Grammarinator) 대비 버그 유발률이 크게 증가했습니다.

4. 실험 결과 (Results)

저자들은 SQL 과 XML 도메인에서 ExplainFuzz 를 평가했습니다.

• RQ1 (일관성 및 현실성): 7 개 도메인 (SQL, JSON, XML 등) 에서 퍼플렉시티를 측정했습니다. ExplainFuzz 는 7 개 중 5 개 도메인에서 가장 낮은 퍼플렉시티를 기록하여, pCFG, PC-HMM, LLM 보다 학습된 입력 분포를 더 정확하게 모델링함을 보였습니다.
• RQ2 (목표 지향적 샘플링의 영향):
  • SQL: 조건부 샘플링을 적용한 결과, 버그 커버리지가 39.7% 에서 63.3% 로 23.6%p 증가했습니다.
  • XML: 버그 커버리지가 82.5% 에서 100% 로 17.5%p 증가했습니다.
  • 또한, 각 버그를 유발하는 고유한 입력의 다양성 (Distinct triggers) 이 크게 향상되었습니다 (SQL: +21 개, XML: +121 개 증가).
• RQ3 (버그 유발 입력 다양성):
  • SQL: Grammarinator 대비 버그 커버리지는 **35.3% → 39.7%**로, 버그 유발 입력 수는 평균 +417 개 증가했습니다.
  • XML: 버그 커버리지는 **10% → 82.5%**로 급증했으며, 버그 유발 입력 수는 평균 +1587 개 증가했습니다.
  • Grammarinator 는 시드 입력의 국소적 변형에 머무르는 반면, ExplainFuzz 는 학습된 분포를 통해 더 넓은 의미적 영역 (semantic neighborhood) 을 탐색하여 복잡한 버그를 더 많이 발견했습니다.

5. 의의 및 결론 (Significance)

ExplainFuzz 는 소프트웨어 테스트 분야에서 다음과 같은 중요한 의의를 가집니다:

• 블랙박스 모델의 대안: LLM 의 블랙박스 특성을 극복하고, 내부 확률 분포를 투명하게 분석하고 제어할 수 있는 해석 가능한 테스트 생성 모델을 제시했습니다.
• 맥락 의존성 학습: 단순한 문법 규칙을 넘어, 실제 데이터에서 나타나는 복잡한 맥락적 상관관계 (예: 특정 SQL 절의 공존 확률) 를 학습하여 더 현실적인 테스트 케이스를 생성합니다.
• 지능형 테스트 생성: 사용자가 원하는 특정 조건 (제약) 을 명시하면, 해당 조건을 만족하면서도 문법적으로 유효하고 다양한 입력을 자동으로 생성할 수 있어, 특정 취약점이나 버그를 타겟팅한 테스트에 매우 효과적입니다.

결론적으로, ExplainFuzz 는 확률적 회로를 기반으로 한 문법 인지형, 제어 가능형, 해석 가능한 테스트 생성의 새로운 패러다임을 제시하며, 기존 변형 (mutation) 기반 Fuzzing 의 한계를 극복하고 소프트웨어 품질 보증을 크게 향상시킬 수 있음을 입증했습니다.