계층화된 문맥 자유 문법을 사용한 입력 데이터 기술

김태환, 이담호, 서현지, 표창우

http://doi.org/10.5626/JOK.2019.46.4.321

본 논문에서는 복수의 입력 장치로부터 들어오는 입력의 형태적 특성을 문맥 자유 문법 기반으로 표현하는 데이터 기술 언어(DDL)를 정의하고 있다. 각 입력 파일 또는 장치는 자체의 입력 데이터 기술을 가지며, 상위 계층 입력 기술과 연결되어 계층 구조를 형성한다. 또한 본 논문에서는 DDL을 사용하여 입력 데이터를 생성하는 방법을 개발하였다. DDL의 유용성을 확인하기 위하여 기본 블록 실행 범위와 입력 생성 시간에 대하여 2 개의 다른 입력 생성 체계와 비교 평가하였다. Coreutils의 37 개 프로그램에 대하여 DDL 방식은 KLEE보다 O(10³) 배 더 빠르게 입력을 생성하였으며, 기본 블록 실행 범위는 25.44%가 더 넓었다. DDL 방식은 단일 계층 CFG 방식보다 평균 1.52 배의 생성 시간이 더 필요하지만 기본 블록 실행 범위를 6.59%만큼 더 감당하였다. 현재 DDL은 동적 제어흐름 분석을 위한 정상적인 입력 생성에 사용하고 있다.