베이지안 필터링을 개선하는 방법, 기존 연구들과의 차이점, 효과적인 토큰화 전략 및 미래의 스팸 필터링 방향에 대해 설명합니다.
2003년 1월
(이 글은 2003년 스팸 컨퍼런스에서 발표한 내용입니다. A Plan for Spam에서 소개한 알고리즘의 성능을 개선한 작업과 앞으로의 계획을 설명합니다.)
제가 처음 소개하고 싶은 발견은 연구 논문을 게으르게 평가하기 위한 알고리즘입니다. 원하는 대로 글을 쓰고 기존 연구는 전혀 인용하지 않으면, 분개한 독자들이 인용해야 할 모든 논문을 보내줍니다. Slashdot에 "A Plan for Spam"[1]이 올라온 뒤 이 알고리즘을 발견했습니다.
스팸 필터링은 텍스트 분류의 하위집합으로 잘 확립된 분야지만, 베이지안 스팸 필터링에 관한 최초의 논문은 1998년 같은 컨퍼런스에서 두 편 발표되었습니다. 하나는 Pantel과 Lin[2], 다른 하나는 Microsoft Research 그룹[3]입니다.
이 연구들을 들었을 때 약간 놀랐습니다. 사람들이 이미 4년 전에 베이지안 필터링을 연구했다면 왜 모두 사용하지 않을까? 논문을 직접 읽고 나서 이유를 알았습니다. Pantel과 Lin의 필터가 두 논문 중 더 효과적이었지만, 스팸 탐지율은 92%에 불과했고 오탐율(정상 메일이 스팸으로 분류될 확률)이 1.16%나 됐습니다.
제가 베이지안 스팸 필터를 만들었을 때는, 99.5%의 스팸을 잡으면서 오탐율은 0.03% 미만이었습니다[4]. 같은 실험을 한 두 사람이 결과가 크게 다르면 항상 불안합니다. 여기서는 이 두 수치에 따라 완전히 반대의 결론이 나올 수도 있습니다. 사용자마다 요구 수준이 다르지만, 많은 사람에게 92% 탐지/1.16% 오탐은 필터가 해법이 아니라는 뜻이고, 99.5% 탐지/0.03% 미만의 오탐은 충분히 해법이 될 수 있습니다.
그렇다면 왜 이렇게 다른 결과가 나왔을까요? Pantel과 Lin의 실험을 그대로 재현해보진 않았지만 논문을 읽고 다섯 가지 다른 점을 발견했습니다.
첫째, 그들은 아주 적은 데이터(스팸 160개, 정상 메일 466개)로 필터를 훈련시켰습니다. 데이터셋 크기가 너무 작아 필터 성능이 덜 나왔을 수 있습니다. 그러니 그들의 수치는 해당 알고리즘의 성능뿐 아니라 베이지안 필터 전체를 평가하기에도 적절하지 않을 수 있습니다.
둘째, 가장 중요한 차이는 그들이 메시지 '헤더'를 무시했다는 점입니다. 스팸 필터를 만들어 본 사람이라면 이 결정이 이상하다고 느낄 것입니다. 저도 처음에는 헤더를 무시했는데, 이는 문제를 단순하게 유지하고 싶어서였습니다. 헤더가 복잡해 보여 데이터를 빼 버린 것이죠. 필터 개발자라면 '데이터를 무시하지 말 것'이 중요한 교훈입니다. 당연해 보여도 직접 여러 번 경험하며 익힌 사실입니다.
셋째, 그들은 토큰을 스테밍(stemming)하여 'mailing', 'mailed' 모두 'mail'로 변환했습니다. 아마도 작은 코퍼스 때문에 그런 선택을 했겠지만, 이는 일종의 성급한 최적화입니다.
넷째, 확률 계산 방법도 다릅니다. 그들은 모든 토큰을 사용했지만, 저는 가장 중요한 15개만 사용했습니다. 모든 토큰을 사용하면 긴 스팸 메일을 놓치기 쉽고, 스팸 발송자가 무작위 텍스트를 추가해서 필터를 속이기 쉬워집니다.
마지막으로, 그들은 오탐을 줄이는 편향을 두지 않았습니다. 저는 정상 메일 코퍼스에서 나오는 토큰 발생 횟수를 두 배로 세어 오탐을 줄입니다.
스팸 필터링을 단순한 텍스트 분류 문제로 다루는 것은 좋은 접근이 아닙니다. 문자 분류 기술은 쓸 수 있지만, 이메일이라는 구조적 특성과 오탐의 심각성을 반드시 고려해야 하고, 스팸 발송자가 실시간으로 방어하는 특성도 생각해야 합니다.
Slashdot 이후 알게된 또 다른 프로젝트는 Bill Yerazunis의 CRM114입니다[5]. 이 필터는 위에서 언급한 원칙과 달리, 순수 텍스트 분류기임에도 불구하고 거의 완벽히 스팸을 걸러냅니다.
CRM114를 이해한 후 언젠가는 나도 단어 단위가 아닌 더 복잡한 방식을 써야겠다고 생각했으나, 일단 단어 단위(Filter based on single words)로 어디까지 갈 수 있는지 실험했는데 생각보다 성능이 잘 나왔습니다.
저는 주로 토큰화를 더 영리하게 개발하는 데 중점을 두고 있습니다. 현재의 스팸이라도 CRM114에 가까운 탐지율을 구현할 수 있었고, 두 방법이 독립적이므로 최적화된 해법은 두 방식을 결합할 수도 있습니다.
"A Plan for Spam"에서는 토큰을 아주 단순하게 정의했습니다. 알파벳, 숫자, 대시, 작은따옴표, 달러 기호만 토큰의 일부로 보고 그 외는 토큰 구분자로 간주했습니다. 대소문자도 무시했습니다.
현재는 더 복잡한 토큰 정의를 사용합니다.
이런 방식은 필터의 어휘수를 늘려 더 정교하게 구분할 수 있게 해 줍니다. 예를 들어 "free"란 단어가 제목에 나왔을 때와 본문에 나왔을 때 스팸 확률이 다릅니다(제목: 98%, 본문: 65%).
현재 일부 토큰의 확률 예시는 아래와 같습니다[6]:
SubjectFREE 0.9999 free!! 0.9999 Tofree 0.9998 Subjectfree 0.9782 free! 0.9199 Free 0.9198 Urlfree 0.9091 FREE 0.8747 From*free 0.7636 free 0.6546
"A Plan for Spam" 필터에서는 위 모두가 .7602의 확률로 같게 취급됐습니다. 옛 필터는 약 23,000개의 토큰을, 지금은 187,000개 가량을 인식합니다.
토큰 수가 많아지면 필터가 놓치는 경우도 늘어날 수 있습니다(토큰 분산 효과). 즉, "free" 뒤에 느낌표가 여럿 붙으면(예: free!!!!!!) 기존 필터로는 스팸임을 인식하지 못했을 수 있습니다.
이 문제의 한 해결책은 "퇴화(degeneration)"입니다. 정확히 일치하는 토큰이 없을 땐, 덜 구체적인 버전으로 처리합니다. 저는 다음 특징이 토큰을 더 구체적으로 만든다고 봅니다: 마지막에 느낌표, 대문자, 그리고 특정 헤더 위치(Subject, To, From 등) 등장. 예를 들어 "Subjectfree!" 확률이 없으면, "Subjectfree", "free!", "free" 중 .5에서 가장 먼 값을 사용합니다.
즉, "FREE!!!"이 제목에 나오면 다음과 같은 순서로 대체값을 고려합니다[7]:
SubjectFree!!! Subjectfree!!! SubjectFREE! SubjectFree! Subjectfree! SubjectFREE SubjectFree Subjectfree FREE!!! Free!!! free!!! FREE! Free! free! FREE Free free
이때 대문자, 첫글자 대문자, 전체 소문자 버전 등도 모두 포함하여 비교해야 합니다. 실제로 동사류에서 첫 글자가 대문자인 경우 스팸 확률이 더 높을 수 있습니다(Act: 98%, act: 62%).
어휘수 증가로, 같은 단어가 여러 번 집계될 수 있습니다. 논리적으로는 서로 다른 토큰이지만, 경험상 그런 중복 집계가 오히려 필터 성능에 도움이 됩니다.
어휘가 커지면 흥미로운(=확률이 .5에서 먼) 토큰도 더 많이 검출됩니다. 하지만 기준 토큰 수(예: 15개)를 정하면, 혹시 아주 강력한 토큰이 많은 경우 순위 결정이 임의로 흐를 수 있습니다. 이럴 땐 더 많이 등장하는 토큰에 더 큰 가중치를 부여하는 것이 한 방법입니다.
예를 들어 "dalco"(스팸에 3회, 정상메일에 0회)와 "Url*optmails"(스팸에 1223회, 정상메일에 0회)가 같은 0.99 확률을 가진다면, 실제로는 후자에 훨씬 더 강한 신호를 줘야 합니다. 그래서 현재는 스팸 코퍼스에서만 10회 이상 나오면 .9999, 그 미만은 .9998을 부여합니다. 정상 메일 쪽도 반대로 적용합니다.
더 나아가, Hauser[8]처럼 "가장 흥미로운 토큰 15개"가 아니라 일정 임계치 이상의 토큰을 모두 사용하는 방법도 생각할 수 있습니다. 이때 임계치는 아주 높게 잡아야, 스팸 발송자가 무해한 단어로 메시지를 채워 넣어 필터를 속이는 것을 막을 수 있습니다.
마지막으로 html을 어떻게 처리해야 할까요? html을 무시하는 것은 나쁜 아이디어입니다. 하지만 태그 전체를 분석하면 필터가 단순히 html 탐지기가 될 수 있습니다. 적당히 골라서 필수적인 링크(a, img, font 태그만)만 분석하는 게 가장 효과적이었습니다. 매우 똑똑한 스팸 발송자는 이미 html을 잘 쓰지 않기에, 미래의 스팸 필터 성능도 html 처리 방식에 크게 좌우되진 않습니다.
2002년 12월 10일부터 2003년 1월 10일까지 스팸 1750통을 받았고, 그중 4통이 필터를 뚫었습니다. 탐지율 약 99.75%입니다.
이 중 2개는 필터가 정상 메일에서 자주 등장하는 단어를 포함했기 때문에 놓쳤고, 하나는 불안전한 cgi 스크립트를 악용해 삼자에게 보낸 메일로, 내용만 봐서는 탐지 어렵지만 흔히 쓰이는 안내 문구(예: "Below is the result of your feedback form")의 등장으로 대부분은 잡힙니다. 마지막 하나는 "스팸의 미래형"이라 부르는 케이스인데, 평범한 문장 뒤에 URL만 남깁니다. 이런 경우 필터가 잡기 어렵지만, 반응률이 낮아 해커들이 대량 발송할 동기를 잃을 가능성이 높습니다.
더 놀라운 점은 같은 기간 동안 오탐이 3건 나왔다는 점입니다.
실제로 오탐을 겪고 나서 보니 생각보다 나쁘지 않았습니다. 통계적 필터에서 발생한 오탐은 정말 스팸과 매우 유사한 메일이었고, 이런 메일을 놓치는 건 크게 아쉽지 않습니다.
2건은 구매한 회사에서 온 뉴스레터로 원래 받지 않았던 물건이어서 논란이 있음에도, 일단 오탐으로 집계합니다. 두 회사가 상업용 메일 발송 서비스로 넘어오면서 헤더나 내용이 스팸 같아졌기 때문입니다.
마지막 실질적 오탐은 이집트에서 온 올대문자 메일입니다. 대소문자 구분 기준이 추가되면서 기존 필터에서는 걸리지 않던 경우죠.
전체 오탐율은 샘플 수가 적어 정확히 계산하기 어렵지만, 약 7740개의 정상 메일 중 5건(0.06%)이 오탐으로 분류됐습니다. 이 수치도 몇몇은 필터를 개선해 막을 수 있다고 생각합니다.
저는 오탐과 누락(스팸인데 거르지 못한 경우)은 서로 다른 에러라 봅니다. 탐지율 향상은 최적화이고, 오탐 감소는 디버깅입니다. 오탐 사례는 바로 제 버그리스트입니다. 예를 들어, 올대문자 메일은 나이지리아 스팸과 혼동된 것인데, 대소문자를 좀 더 영리하게 다루는 방법을 도입해야 할 것입니다.
따라서 .06%는 의미를 부여하자면 오탐의 상한선으로 볼 수 있지만, 실제로는 현재 구현의 버그율일 뿐 베이지안 필터 본연의 한계는 아닙니다.
이제는 최적화의 단계입니다. 최적화를 잘 하려면, 어디가 느린지 직접 살펴서 개선해야 하듯, 스팸 필터링도 못 잡은 스팸을 분석하여 방안을 찾아야 합니다.
현재 스팸 발송자는 필터를 회피하려고 단어나 철자법을 교묘하게 변형합니다. 하지만 저는 아직 그런 스팸도 충분히 잡고 있어, 더 시급한 문제는 아닙니다[10].
현재 가장 힘든 유형은 두 가지입니다. 하나는 '채팅'이나 '소개팅' 사이트 접속을 유도하는, 평범한 이메일을 가장한 스팸입니다. 영업 멘트 없이 일상어만 써 필터가 판단하기 어려운 경우입니다.
다른 하나는 예를 들어 불가리아 등에서 온 외주 프로그래밍 서비스 홍보 메일로, 프로그래머인 저의 정상 메일과 비슷한 단어를 써서 필터 통과가 쉽습니다. 아마도 첫 타입(소개팅류)에 통계를 더 적용하거나, URL 반복 여부 등 패턴을 찾아내는 것이 한 방법일 것입니다[11].
외주형 메일은 사이트에 크롤러를 돌려도 통계적 신호가 뚜렷하지 않아, 메시지에 언급된 도메인을 중앙에서 관리하는 블랙리스트 방식 등이 최선일 수 있습니다[12]. 그나마 이런 메일이 많지 않으니, 이 문제만 남는다면 스팸 해결은 한 단계 접을 수 있겠습니다.
통계적 필터만으로 정말 스팸 문제가 해결될 수 있을까요? 지금은 저에겐 큰 문제가 아니지만, 언젠가 스팸 발송자가 본격적으로 통계 필터를 속이려 들면 어떤 일이 일어날지는 장담하기 어렵습니다.
네트워크 레벨에서 필터링하는 방식에는 낙관적이지 않습니다[13]. 스팸 발송자는 정적인 장애가 있으면 그걸 극복하는 데 뛰어난 편입니다. 이미 스팸어세신(Spamassassin)을 통과하는지 사전 검사해주는 회사가 존재합니다.
네트워크 레벨 필터는 "옵트인"을 주장하는 스팸만 차단하기엔 충분할 수 있습니다. 그러나 헤더 조작이나 오픈 릴레이를 쓰는 적극적인 발송자는 얼마든지 메시지를 뚫을 수 있습니다.
저는 각 사용자의 메일을 기준으로 확률을 산출하는 개별 필터 방식에 더 낙관적입니다. 오탐이 줄고, 필터 성능도 높아집니다(예: 수신자의 이메일 주소가 base64로 암호화되어 등장하면 스팸 신호 등).
무엇보다 개별 필터는 모두 다르다는 점이 중요합니다. 모든 사용자가 각자 다른 확률 데이터를 갖게 되면, 스팸 발송자의 최적화 작업(즉, 시도-수정-테스트 사이클)이 매우 어려워집니다. 단일 표준 필터라면 메시지 한두 번 수정하며 쉽게 우회할 수 있지만, 각각 다르면 그만큼 많은 샘플을 실제로 보내봐야 통과 여부를 알 수 있으니, 스팸 발송자는 작업 효율성이 매우 떨어집니다.
주석(Notes)
[1] Paul Graham. "A Plan for Spam." 2002년 8월. http://paulgraham.com/spam.html
이 알고리즘의 확률 계산은 베이즈 규칙의 단순한 경우로, 두 가지 가정이 있습니다: 단어(특징)의 발생이 독립적이며, 스팸 여부의 사전확률(prior probability)을 모른다고 가정합니다. 첫 번째는 통계적 텍스트 분류에서 널리 쓰이고, 두 번째는 메일의 스팸/비스팸 비율이 시시각각 다르기 때문에 채택했습니다.
만약 스팸/비스팸 비율이 항상 높거나(낮거나) 일정하다면 사전 확률을 사용해 필터를 더 개선할 수 있습니다. 다만 시간대별로 비율이 달라지니 시간에 따라 따로 기록해야 합니다.
[2] Patrick Pantel and Dekang Lin. "SpamCop-- A Spam Classification & Organization Program." Proceedings of AAAI-98 Workshop on Learning for Text Categorization.
[3] Mehran Sahami, Susan Dumais, David Heckerman and Eric Horvitz. "A Bayesian Approach to Filtering Junk E-Mail." Proceedings of AAAI-98 Workshop on Learning for Text Categorization.
[4] 당시 정상 메일 약 4,000통 중 오탐 0건이었습니다. 만약 바로 다음 메일이 오탐이었다면, 오탐율은 0.03%가 되겠지요. 이런 수치는 신뢰하기 어렵지만, 1.16%보다는 훨씬 낮다는 점을 강조하기 위해 예로 들었습니다.
[5] Bill Yerazunis. "Sparse Binary Polynomial Hash Message Filtering and The CRM114 Discriminator." 2003년 스팸 컨퍼런스 발표.
[6] "A Plan for Spam"에서는 임계값을 .99, .01로 잡았습니다. 현재는 코퍼스 규모가 1만 개쯤 되기에 .9999, .0001로 올렸습니다.
[7] 여기 개선이 필요할 수 있습니다. 현 구조에선 "Subjectfoo"가 "foo"로 퇴화(degeneration)하면, 바디나 기타 헤더에서의 "foo" 확률을 사용합니다. 더 정확히 하려면 각 버전별 통계도 별도 집계해 "Anywherefoo"로 퇴화해야 합니다. 대문자는 임의 대소문자 버전으로 퇴화해야 합니다. 가격 역시 "$129.99"를 "$--9.99", "$--.99", "$--" 등으로 점진적으로 퇴화할 수 있겠지요. 어근(stem)으로의 퇴화는 코퍼스가 작을 때만 쓸만할 수 있습니다.
[8] Steven Hauser. "Statistical Spam Filter Works for Me." http://www.sofbot.com.
[9] 오탐은 모두 동일한 심각도가 아닙니다. 블랙리스트를 쓴다면, 오탐 메일이 단순히 특정 ISP를 쓴다는 이유로 거부될 수 있지만, 필터 기반 오탐은 텍스트가 스팸과 매우 유사한 메일일 가능성이 높습니다.
[10] 만약 스팸 발송자가 토큰 변형을 능숙히 한다면, 텍스트에서 공백, 마침표, 쉼표 등을 제거하고 사전에 등을 활용해 단어를 찾는 방식을 쓸 수 있습니다. 인간이 읽어낼 수 있으면 기계도 가능합니다.
[11] 일반적으로 스팸은 정규 메일보다 반복이 많습니다. 필터에서 상위 15개 토큰에 중복을 허용하지 않지만, 중복 여부 자체도 통계적으로 참고할 수 있습니다. (예: "dick"은 스팸확률이 0.9999이지만 이름일 수도 있음) 최대 2회까지 허용하는 것도 방법일 수 있습니다.
[12] 이런 방식이야말로 브라이트메일(Brightmail/PMS)처럼 스팸이 모든 요소를 임의로 변환하게 되면 자연스럽게 퇴화하게 될 것입니다.
[13] 네트워크 수준에서 필터링을 강조하는 것은 흔히 현 상태를 유지하고 싶거나, 근본적인 재설계를 피하고 싶어서 나오는 주장입니다. 하지만 실제로 소프트웨어 설계 논쟁 역사에서 희소 자원 절약 논리는 대부분 패배해왔습니다.
감사의 말: Sarah Harlin, Trevor Blackwell, Dan Giffin에게 초안 검토와 조언, Dan에게 이 필터가 동작하는 기반 시스템 구축에 감사드립니다.
