문제 개요

제1회 구데기컵의 IDN Homograph Attack(15635번) 문제를 풀어보았습니다. 이 문제는 동형이의자를 찾는 문제입니다. 동형이의자는 糖(U+FA03)과 糖(U+7CD6) 처럼 동일한 형태를 가졌지만 코드포인트가 서로 다른 문자를 말합니다.

여러 접근법

유니코드 영역과 코드 포인트 (안 돼)

완성형 한글 문자의 유니코드 코드 포인트만으로도 음절의 초성, 중성, 종성을 계산해낼 수 있다는 사실에 착안해서, 혹시 동형이의자 여부를 유니코드 영역 정보나 코드 포인트 자체로부터 알아낼 수 있지 않을까 싶었습니다만…

그런 건 없었습니다.

공개된 동형이의자 데이터베이스 (안 될 것 같아)

위키피디아의 IDN Homograph Attack (en) 항목을 보니 동형이의자 공격을 막기 위해 머신 러닝 기반의 문자 인식으로 동형이의자 데이터베이스를 만들어 놓고 사용하기도 한다는 내용이 있었습니다. 그래서 처음에는 공개된, 잘 알려진 동형이의자 목록을 구하려 했습니다.

하지만 문제에 Noto Sans CJK KR 폰트를 기준으로 한다고 명시되어 있었기 때문에, 공개된 데이터베이스가 다른 폰트를 기반으로 만들어졌다면 동형이의자 목록이 완전히 일치하지는 않을 것 같아 직접 동형이의자를 구해보기로 했습니다.

(나중에 알고보니 구데기컵 에디토리얼 레포지토리에 동형이의자 목록이 있긴 했습니다.)

머신 러닝 (난 못해)

Noto Sans CJK KR 폰트 기반으로 머신 러닝 기반의 문자 인식으로 동형이의자를 구할 수도 있겠습니다만은… 익숙하지 않기도 하고 패스했습니다.

폰트 뜯어보기 (성공)

폰트 제작은 큰 비용이 드는 작업인데 동형이의자를 고려하지 않고 똑같은 글리프를 중복해서 제작하지는 않았을 거라는 생각이 들었습니다. 그렇다면 Noto Sans CJK KR 파일을 뜯어서 글리프를 조사해 보면 완전히 동일한 글리프 데이터를 가진 문자들이 있지 않을까라는 가정을 기반으로 진행해 보았습니다.

풀이

폰트 파일 파싱

문자별 글리프 데이터를 얻어내기 위해 NotoSansKR-Regular.otf을 파싱해야 합니다. 폰트 파일 포맷을 조사하거나 파서를 만들 필요는 없었습니다. 저는 Node.js가 익숙하므로 Node.js에서 폰트를 파싱할 수 있는 라이브러리 fontkit을 찾아 사용했습니다.

글리프가 동일한 문자 찾기

처음에는 글리프(Glyph, 자형) 데이터를 직접 비교해서 완전히 동일한 문자를 찾으려 했는데, 코드포인트마다 글리프 데이터 자체가 직접 할당된 것이 아니라 글리프는 인덱싱되어 있고 코드포인트에 글리프 인덱스가 할당되어 있었습니다. 따라서 동일한 글리프 인덱스가 할당된 코드포인트만 찾으면 됩니다.

그래서 모든 문자를 순회하며 중복으로 나타나는 글리프를 찾아 텍스트 파일로 기록하는 코드를 작성해 동형이의자 목록을 구했습니다.

제출용 동형이의자 판별 코드 작성

위에서 구한 동형이의자 목록을 코드 안에 하드코딩하고 입력으로 들어온 문자 중 하나가 그 배열에 존재하는지 검사하는 코드를 작성했습니다. 이왕이면 숏코딩이 재미있으니 숏코딩 1위를 목표로 코드를 개조했습니다. 연속된 문자열로 하드코딩된 동형이의자를 런타임에 한 글자씩 잘라 배열에 넣어 쓰는 방식으로 배열 리터럴이 차지하는 크기를 줄였습니다.

문제 해결!