LogiCase: 경쟁 프로그래밍 입력 명세로부터의 효과적인 테스트 케이스 생성 프레임워크

1. 문제 제기

**자동 테스트 케이스 생성(Automated Test Case Generation, ATCG)**은 알고리즘의 정확성과 견고함을 평가하는 데 필수적인 기술로, 특히 경쟁 프로그래밍 환경에서 그 중요성이 부각되고 있습니다. 그러나 기존 ATCG 기법들은 복잡한 입력 명세를 정확히 반영하지 못하거나, 코너 케이스를 제대로 생성하지 못하는 한계를 지닙니다.

또한, 문법 기반(fuzzing) 접근 방식은 테스트 입력의 구조를 잘 포착할 수 있음에도 불구하고, 입력 명세마다 수작업으로 문법을 정의해야 하는 부담이 존재합니다. 이에 따라, 자연어로 주어진 문제 설명을 구조적 문법으로 자동 변환하고, 이를 기반으로 고품질 테스트 케이스를 생성할 수 있는 새로운 접근이 요구되고 있습니다.

2. 제안 방법론: LogiCase 프레임워크

LogiCase 프레임워크 구조도.

LogiCase는 자연어로 주어진 문제 명세를 **카운터 기반 문맥 자유 문법(Context-Free Grammar with Counters, CCFG)**으로 변환한 후, 해당 문법을 활용해 정형화되고 유효한 테스트 케이스를 자동 생성하는 프레임워크입니다. LogiCase는 다음과 같은 세 가지 주요 구성 요소를 포함합니다:

CCFG: 카운터 기반 문법
- 반복 구조나 라인 수와 같은 의미적 제약을 반영할 수 있도록 확장된 문법 체계.
- 전통적인 CFG로는 포착하기 어려운 구조적 제약을 표현 가능.
CCFGT5: 문법 변환 모델
- 문제 입력 명세를 CCFG로 변환하기 위한 CodeT5 기반 이중 모듈 구성.
- 하나는 문법 구조 학습, 다른 하나는 정수 제약 조건 학습에 특화되어 있음.
샘플링 기반 테스트 케이스 생성
- 생성된 CCFG를 기반으로 짧은/중간/긴 길이의 다양한 테스트 케이스를 샘플링.
- 코너 케이스까지 포함하여 다양한 오류 탐지 가능성 확보.

3. 실험 결과

테스트 케이스 유효성 및 효과성 비교 표.

우리는 CodeContests 데이터셋을 활용해 LogiCase의 성능을 정량적으로 평가했습니다.

비교 대상으로는 변이(mutation)기반 접근, LLM(ChatGPT, Gemini)을 이용한 직접 생성 방식, 그리고 Ground-truth 수작업 문법이 포함되었습니다. 실험 결과, **LogiCase의 핵심 구성인 CCFGT5-10은 set-based 유효성 81.18%, element-based 효과성 42.26%, set-based 효과성 67.73%**를 기록하며 다른 방법 대비 우수한 성능을 보였습니다.

✅ 주요 실험 결과 요약:

CCFG기반 생성은 복잡한 입력 명세를 가진 문제에서 더욱 효과적임.
다양한 길이의 테스트 케이스를 조합하는 것이 가장 효과적임.
CCFGT5 기반 테스트 케이스는 LLM기반 직접 생성 방식보다 높은 유효성과 일반성을 가짐.