파서 호환성 문제와 기존 해결책의 한계
Ruby 파서 구현체 간의 호환성 문제는 특정 파서에서는 올바르게 동작하는 코드가 다른 파서에서는 오류를 발생시키거나 다르게 파싱되는 상황을 야기합니다. 기존에는 유닛 테스트, 공개 Gem 파싱, 퍼징(fuzzing)과 같은 물량 공세 방식이 사용되었으나, Ruby 문법의 복잡성과 마이너하거나 새로운 구문의 미활용성으로 인해 모든 경우를 포괄적으로 검증하기 어렵다는 한계가 있었습니다.
오토마톤 이론의 적용
발표자는 이 문제를 해결하기 위해 오토마톤 이론을 도입합니다. * 오토마톤과 정규 표현식: 오토마톤은 상태, 알파벳, 전이 함수 등을 통해 문자열의 수락 여부를 결정하며, 정규 표현식과 상호 변환이 가능합니다. 이는 오토마톤이 문자열 집합을 다루는 효과적인 도구임을 의미합니다. * 집합 연산과 대칭 차집합: 오토마톤은 문자열 집합에 대한 교집합, 합집합, 차집합 등 다양한 집합 연산을 효율적으로 수행할 수 있습니다. 특히, 두 파서의 차이를 발견하는 데 핵심적인 ‘대칭 차집합(Symmetric Difference, XOR)’ 연산은 한 오토마톤에는 포함되지만 다른 오토마톤에는 포함되지 않는 문자열 집합을 찾아냅니다. * 파서와 오토마톤 연결: 파서가 특정 문자열을 성공적으로 파싱할 때만 수락하는 ‘파서에 대응하는 오토마톤’ 개념을 정의하여 파서의 동작을 오토마톤으로 모델링합니다.
오토마톤 학습(Automata Learning)을 통한 오토마톤 획득
블랙박스 시스템인 파서로부터 해당 오토마톤을 직접 구축하는 것은 어렵습니다. 이를 위해 ‘오토마톤 학습’ 알고리즘, 특히 Angluin의 L* 알고리즘이 활용됩니다. * L* 알고리즘: L는 ‘멤버십 쿼리(Membership Query)’ (주어진 문자열이 시스템에 의해 수락되는가?)와 ‘동등성 쿼리(Equivalence Query)’ (학습된 오토마톤이 실제 시스템과 일치하는가? 불일치 시 반례 제공)를 통해 시스템의 동작을 학습합니다. * Ruby 문법의 복잡성 극복: L는 정규 언어에 특화되어 있어 Ruby와 같은 복잡한 문맥 자유 언어(Context-Free Language)를 직접 학습하기 어렵습니다. 이를 해결하기 위해 괄호의 중첩과 같은 문맥 자유 언어의 일부 특성을 처리할 수 있는 ‘Visible Pushdown Automata(VPA)’를 사용합니다. VPA는 Ruby 문법 전체는 아니지만, 특정 부분 문법의 호환성 검증에 유용합니다.
‘Lernnen’ 라이브러리와 실제 버그 발견
발표자는 자신이 개발한 Ruby 기반 오토마톤 학습 라이브러리 ‘Lernnen’을 소개합니다. ‘Lernnen’은 다양한 오토마톤 학습 알고리즘을 지원하며, 사용자 친화적인 API를 제공하여 쉽게 오토마톤을 학습하고 분석할 수 있도록 합니다.
* 실험 설정: Lernnen을 사용하여 문자열 리터럴, 콜론, 괄호 등 제한된 알파벳에 대한 parse.y와 Prism의 오토마톤을 학습했습니다.
* 버그 발견: 학습된 두 오토마톤의 대칭 차집합을 계산한 결과, (:A)와 같은 구문이 parse.y에서는 올바르게 파싱되지만 Prism에서는 심볼 리터럴로 잘못 파싱되는 버그를 발견했습니다. 이 버그는 Prism에 보고되어 이미 수정되었습니다.