더 나은 베이즈 필터링

2003년 1월

(이 글은 2003년 스팸 컨퍼런스에서 발표된 내용입니다. 스팸 대책에서 설명된 알고리즘의 성능을 개선하기 위해 제가 수행한 작업과 향후 계획을 설명합니다.)

제가 여기서 소개하고 싶은 첫 번째 발견은 연구 논문의 게으른 평가(lazy evaluation)를 위한 알고리즘입니다. 그냥 쓰고 싶은 대로 쓰고 이전 연구를 인용하지 않으면, 분개한 독자들이 인용했어야 할 모든 논문들의 참고 문헌을 보내줄 것입니다. 저는 이 알고리즘을 '스팸 대책' [1]이 Slashdot에 올라온 후에 발견했습니다.

스팸 필터링은 텍스트 분류의 한 부분이며, 이는 잘 정립된 분야입니다. 하지만 베이즈 스팸 필터링 자체에 대한 첫 논문들은 1998년 같은 컨퍼런스에서 발표된 두 편으로 보입니다. 하나는 Pantel과 Lin의 논문 [2]이고, 다른 하나는 Microsoft Research 그룹의 논문 [3]입니다.

이 연구에 대해 들었을 때 저는 약간 놀랐습니다. 4년 전부터 사람들이 베이즈 필터링을 사용하고 있었다면, 왜 모두가 그것을 사용하지 않았을까요? 논문들을 읽어보니 이유를 알 수 있었습니다. Pantel과 Lin의 필터가 둘 중 더 효과적이었지만, 스팸의 92%만을 걸러냈고, 오탐(false positives)률은 1.16%였습니다.

제가 베이즈 스팸 필터를 직접 작성해 보았을 때, 스팸의 99.5%를 걸러냈고 오탐률은 0.03% 미만이었습니다 [4]. 같은 실험을 시도한 두 사람이 크게 다른 결과를 얻는 것은 항상 놀라운 일입니다. 특히 이 경우, 두 수치 세트가 정반대의 결론을 낼 수 있기 때문에 더욱 그렇습니다. 사용자마다 요구 사항이 다르지만, 많은 사람들에게 1.16%의 오탐률로 92%의 필터링률은 필터링이 허용 가능한 해결책이 아님을 의미하는 반면, 0.03% 미만의 오탐률로 99.5%는 허용 가능하다는 것을 의미한다고 생각합니다.

그렇다면 왜 이렇게 다른 수치를 얻었을까요? 저는 Pantel과 Lin의 결과를 재현하려고 시도하지는 않았지만, 논문을 읽어보니 차이를 설명할 수 있는 다섯 가지 요인이 있는 것 같습니다.

첫째, 그들은 매우 적은 데이터로 필터를 훈련시켰습니다. 스팸 메일 160개와 비스팸 메일 466개였습니다. 그렇게 작은 데이터 세트에서는 필터 성능이 여전히 향상될 여지가 있습니다. 따라서 그들의 수치는 베이즈 스팸 필터링 전반은 물론, 그들의 알고리즘 성능에 대한 정확한 측정치조차 아닐 수 있습니다.

하지만 가장 중요한 차이점은 아마도 그들이 메시지 헤더를 무시했다는 점일 것입니다. 스팸 필터 작업을 해본 사람이라면 이것이 이상한 결정이라고 생각할 것입니다. 하지만 제가 처음 작성해 본 필터에서도 저 역시 헤더를 무시했습니다. 왜 그랬을까요? 문제를 깔끔하게 유지하고 싶었기 때문입니다. 당시 저는 메일 헤더에 대해 잘 몰랐고, 무작위적인 내용으로 가득 차 있다고 생각했습니다. 필터 개발자들에게는 여기서 얻을 교훈이 있습니다: 데이터를 무시하지 마십시오. 이 교훈은 너무나 당연해서 언급할 필요조차 없다고 생각할 수 있지만, 저는 여러 번 이 교훈을 배워야 했습니다.

셋째, Pantel과 Lin은 토큰을 어간 추출(stemming)했습니다. 예를 들어, 'mailing'과 'mailed'를 모두 어근인 'mail'로 줄였습니다. 그들은 코퍼스(corpus)의 크기가 작아서 이렇게 할 수밖에 없다고 느꼈을 수도 있지만, 그렇다면 이것은 일종의 성급한 최적화입니다.

넷째, 그들은 확률을 다르게 계산했습니다. 그들은 모든 토큰을 사용했지만, 저는 가장 중요한 15개만 사용합니다. 모든 토큰을 사용하면 긴 스팸, 즉 누군가가 다단계 마케팅으로 부자가 된 시점까지의 인생 이야기를 들려주는 유형의 스팸을 놓치는 경향이 있습니다. 그리고 그러한 알고리즘은 스패머가 쉽게 속일 수 있습니다. 스팸 용어를 상쇄하기 위해 무작위 텍스트 덩어리를 추가하기만 하면 됩니다.

마지막으로, 그들은 오탐에 대한 편향(bias)을 두지 않았습니다. 저는 어떤 스팸 필터링 알고리즘이든 필터링률을 희생하여 오탐률을 줄일 수 있는 편리한 조절 장치가 있어야 한다고 생각합니다. 저는 비스팸 코퍼스에서 토큰의 출현 횟수를 두 배로 계산하여 이를 수행합니다.

저는 스팸 필터링을 단순한 텍스트 분류 문제로 취급하는 것이 좋은 생각이라고 보지 않습니다. 텍스트 분류 기술을 사용할 수는 있지만, 해결책은 텍스트가 이메일, 특히 스팸이라는 사실을 반영할 수 있고 또 반영해야 합니다. 이메일은 단순한 텍스트가 아닙니다. 구조를 가지고 있습니다. 스팸 필터링은 단순한 분류가 아닙니다. 오탐이 미탐(false negatives)보다 훨씬 더 나쁘기 때문에 다른 종류의 오류로 취급해야 합니다. 그리고 오류의 원인은 단순히 무작위적인 변동이 아니라, 필터를 무력화하기 위해 적극적으로 노력하는 살아있는 인간 스패머입니다.

토큰

Slashdot 기사 이후에 제가 들었던 또 다른 프로젝트는 Bill Yerazunis의 CRM114 [5]였습니다. 이것은 제가 방금 언급한 설계 원칙의 반례입니다. 이는 단순한 텍스트 분류기이지만, 자신이 무엇을 하는지조차 모른 채 스팸을 거의 완벽하게 필터링할 정도로 놀랍도록 효과적입니다.

CRM114가 어떻게 작동하는지 이해하고 나니, 언젠가는 단어 기반 필터링에서 이와 같은 접근 방식으로 넘어가야 할 것이 필연적으로 보였습니다. 하지만 먼저, 저는 단어만으로 얼마나 멀리 갈 수 있을지 시험해 보기로 했습니다. 그리고 그 답은 놀랍게도 '매우 멀리'였습니다.

주로 저는 더 똑똑한 토큰화(tokenization)에 집중해 왔습니다. 현재 스팸에 대해 CRM114에 근접하는 필터링률을 달성할 수 있었습니다. 이러한 기술들은 Bill의 기술과 대부분 직교합니다. 최적의 해결책은 둘 다 통합하는 것일 수 있습니다.

'스팸 대책'은 토큰에 대한 매우 간단한 정의를 사용합니다. 문자, 숫자, 대시, 아포스트로피, 달러 기호는 구성 문자이며, 그 외의 모든 것은 토큰 구분자입니다. 저는 또한 대소문자를 무시했습니다.

이제 저는 토큰에 대한 더 복잡한 정의를 가지고 있습니다:

1. 대소문자를 보존합니다.

2. 느낌표는 구성 문자입니다.

3. 마침표와 쉼표는 두 숫자 사이에 있을 경우 구성 문자입니다. 이를 통해 IP 주소와 가격을 온전히 얻을 수 있습니다.

4. $20-25와 같은 가격 범위는 $20과 $25 두 개의 토큰을 생성합니다.

5. To, From, Subject, Return-Path 줄 또는 URL 내에 나타나는 토큰은 그에 따라 표시됩니다. 예를 들어, 'foo'는 Subject 줄에서 'Subject*foo'가 됩니다. (별표는 구성 문자로 허용하지 않는 모든 문자일 수 있습니다.)

이러한 조치들은 필터의 어휘를 증가시켜 더 높은 변별력을 갖게 합니다. 예를 들어, 현재 필터에서 Subject 줄의 '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

'스팸 대책' 필터에서는 이 모든 토큰이 0.7602라는 동일한 확률을 가졌을 것입니다. 그 필터는 약 23,000개의 토큰을 인식했습니다. 현재 필터는 약 187,000개를 인식합니다.

더 큰 토큰 집합을 갖는 것의 단점은 놓칠 가능성이 더 많다는 것입니다. 코퍼스를 더 많은 토큰에 분산시키는 것은 코퍼스를 더 작게 만드는 것과 같은 효과를 가집니다. 예를 들어, 느낌표를 구성 문자로 간주하면, 느낌표 두 개만 있는 'free'의 확률이 99.99%라는 것을 알고 있음에도 불구하고, 느낌표 일곱 개가 있는 'free'에 대한 스팸 확률을 갖지 못하게 될 수 있습니다.

이에 대한 한 가지 해결책은 제가 퇴화(degeneration)라고 부르는 것입니다. 토큰에 대한 정확한 일치를 찾을 수 없다면, 덜 구체적인 버전인 것처럼 취급합니다. 저는 마지막 느낌표, 대문자, 그리고 다섯 가지 표시된 컨텍스트 중 하나에 나타나는 것을 토큰을 더 구체적으로 만드는 것으로 간주합니다. 예를 들어, 'Subjectfree!'에 대한 확률을 찾을 수 없다면, 'Subjectfree', 'free!', 'free'에 대한 확률을 찾아 0.5에서 가장 멀리 떨어진 것을 선택합니다.

다음은 필터가 Subject 줄에서 'FREE!!!'를 보고 이에 대한 확률이 없을 때 고려되는 대안들입니다 [7].

SubjectFree!!! Subjectfree!!! SubjectFREE! SubjectFree! Subjectfree! SubjectFREE SubjectFree Subjectfree FREE!!! Free!!! free!!! FREE! Free! free! FREE Free free

이렇게 할 경우, 첫 글자가 대문자인 버전뿐만 아니라 모두 대문자 및 모두 소문자인 버전도 반드시 고려해야 합니다. 스팸은 명령형 문장이 더 많은 경향이 있으며, 그러한 문장에서는 첫 단어가 동사입니다. 따라서 첫 글자가 대문자인 동사는 모두 소문자인 경우보다 더 높은 스팸 확률을 가집니다. 제 필터에서 'Act'의 스팸 확률은 98%이고 'act'는 62%에 불과합니다.

필터의 어휘를 늘리면, 예전의 '동일함' 정의에 따라 같은 단어를 여러 번 세게 될 수 있습니다. 논리적으로는 더 이상 같은 토큰이 아닙니다. 하지만 이것이 여전히 신경 쓰인다면, 경험상 여러 번 세는 것처럼 보이는 단어들이 정확히 여러분이 그렇게 하고 싶어 하는 단어들인 경향이 있다는 점을 덧붙이고 싶습니다.

더 큰 어휘의 또 다른 효과는 들어오는 메일을 볼 때 더 흥미로운 토큰, 즉 0.5에서 멀리 떨어진 확률을 가진 토큰을 더 많이 발견한다는 것입니다. 저는 메일이 스팸인지 여부를 결정하기 위해 가장 흥미로운 15개를 사용합니다. 하지만 이렇게 고정된 숫자를 사용할 때 문제가 발생할 수 있습니다. 가장 흥미로운 토큰을 많이 발견하면, 결과가 동일하게 흥미로운 토큰들의 순서를 결정하는 무작위 요인에 의해 결정될 수 있습니다. 이를 처리하는 한 가지 방법은 일부를 다른 것보다 더 흥미롭게 취급하는 것입니다.

예를 들어, 토큰 'dalco'는 제 스팸 코퍼스에는 3번 나타나고 합법적인 코퍼스에는 전혀 나타나지 않습니다. 토큰 'Url*optmails'(URL 내의 'optmails'를 의미)는 1223번 나타납니다. 하지만 제가 토큰에 대한 확률을 계산하던 방식으로는 둘 다 동일한 스팸 확률인 0.99의 임계값을 가졌을 것입니다.

그것은 옳지 않다고 느껴집니다. 이 두 토큰에 실질적으로 다른 확률을 부여해야 한다는 이론적 주장이 있지만(Pantel과 Lin은 그렇게 합니다), 저는 아직 시도해 보지 않았습니다. 적어도 한 코퍼스에만 나타나는 토큰이 15개 이상 발견되면, 많이 나타나는 토큰에 우선순위를 부여해야 할 것 같습니다. 그래서 이제 두 개의 임계값이 있습니다. 스팸 코퍼스에만 나타나는 토큰의 경우, 10회 이상 나타나면 확률은 0.9999이고, 그렇지 않으면 0.9998입니다. 합법적인 코퍼스에서만 발견되는 토큰의 경우에도 마찬가지입니다.

나중에 토큰 확률을 실질적으로 조정할 수도 있겠지만, 이 작은 양의 조정만으로도 토큰이 올바른 방식으로 정렬되도록 보장합니다.

또 다른 가능성은 15개의 토큰뿐만 아니라 특정 흥미도 임계값을 넘는 모든 토큰을 고려하는 것입니다. Steven Hauser는 그의 통계적 스팸 필터 [8]에서 이를 수행합니다. 임계값을 사용한다면, 매우 높게 설정해야 합니다. 그렇지 않으면 스패머가 더 많은 무해한 단어로 메시지를 채워 필터를 속일 수 있습니다.

마지막으로, HTML에 대해서는 어떻게 해야 할까요? 저는 HTML을 무시하는 것부터 모두 파싱하는 것까지 모든 옵션을 시도해 보았습니다. HTML을 무시하는 것은 좋지 않은 생각입니다. 유용한 스팸 신호로 가득 차 있기 때문입니다. 하지만 모두 파싱하면 필터가 단순한 HTML 인식기로 퇴화할 수 있습니다. 가장 효과적인 접근 방식은 중간 경로를 택하는 것으로 보입니다. 일부 토큰은 인식하지만 다른 토큰은 무시하는 것입니다. 저는 a, img, font 태그를 보고 나머지는 무시합니다. 링크와 이미지는 URL을 포함하고 있기 때문에 반드시 확인해야 합니다.

HTML 처리 방식에 대해 더 똑똑해질 수 있겠지만, 여기에 많은 시간을 투자할 가치는 없다고 생각합니다. HTML로 가득 찬 스팸은 필터링하기 쉽습니다. 더 똑똑한 스패머들은 이미 HTML을 피하고 있습니다. 따라서 미래의 성능은 HTML 처리 방식에 크게 의존하지 않을 것입니다.

성능

2002년 12월 10일부터 2003년 1월 10일 사이에 저는 약 1750개의 스팸을 받았습니다. 이 중 4개가 통과되었습니다. 이는 약 99.75%의 필터링률입니다.

제가 놓친 스팸 4개 중 2개는 제 합법적인 이메일에서 자주 나타나는 단어를 사용했기 때문에 통과되었습니다.

세 번째는 안전하지 않은 CGI 스크립트를 악용하여 제3자에게 메일을 보내는 유형이었습니다. 헤더는 무해하고 사용하는 단어에 주의를 기울이기 때문에 내용만으로는 필터링하기 어렵습니다. 그럼에도 불구하고 저는 보통 이런 스팸을 잡아낼 수 있습니다. 이 스팸은 0.88의 확률로 간신히 통과했는데, 이는 임계값인 0.9 바로 아래였습니다.

물론, 여러 토큰 시퀀스를 살펴보면 쉽게 잡아낼 수 있었을 것입니다. '아래는 귀하의 피드백 양식 결과입니다'는 즉각적인 단서입니다.

네 번째 스팸은 제가 '미래의 스팸'이라고 부르는 것이었습니다. 스팸이 진화할 것이라고 예상하는 형태이기 때문입니다. 완전히 중립적인 텍스트 뒤에 URL이 붙는 형태입니다. 이 경우, 누군가가 마침내 자신의 홈페이지를 완성했고 제가 가서 봐줄 수 있는지 묻는 내용이었습니다. (물론 그 페이지는 포르노 사이트 광고였습니다.)

스패머가 헤더에 주의를 기울이고 새로운 URL을 사용한다면, 미래의 스팸에는 필터가 알아챌 만한 것이 아무것도 없습니다. 물론 우리는 크롤러를 보내 페이지를 살펴보는 것으로 대응할 수 있습니다. 하지만 그럴 필요가 없을 수도 있습니다. 미래의 스팸에 대한 응답률은 낮아야 합니다. 그렇지 않으면 모두가 그렇게 할 것입니다. 충분히 낮다면 스패머가 그것을 보내는 것이 수익성이 없을 것이고, 우리는 그것을 필터링하는 데 너무 많은 노력을 기울일 필요가 없을 것입니다.

이제 정말 충격적인 소식입니다. 같은 한 달 동안 저는 세 개의 오탐을 경험했습니다.

어떤 면에서는 오탐이 발생한 것이 안심이 됩니다. '스팸 대책'을 작성했을 때는 오탐이 전혀 없었고, 어떤 모습일지 알 수 없었습니다. 이제 몇 번 경험하고 나니, 제가 두려워했던 것만큼 나쁘지 않다는 것을 알게 되어 안심됩니다. 통계 필터가 생성하는 오탐은 스팸과 매우 유사하게 들리는 메일로 판명되며, 이러한 메일은 놓쳐도 가장 신경 쓰이지 않을 만한 것들인 경향이 있습니다 [9].

오탐 중 두 개는 제가 물건을 구매했던 회사들의 뉴스레터였습니다. 저는 그것들을 받겠다고 요청한 적이 없었으므로, 논쟁의 여지는 있지만 스팸이라고 볼 수도 있습니다. 하지만 저는 이전에 그것들을 스팸으로 삭제하지 않았기 때문에 오탐으로 간주합니다. 필터가 그것들을 잡아낸 이유는 1월에 두 회사 모두 자체 서버에서 메일을 보내는 대신 상업용 이메일 발송 서비스로 전환했고, 그 결과 헤더와 본문 모두 훨씬 더 스팸스러워졌기 때문입니다.

하지만 세 번째 오탐은 좋지 않은 것이었습니다. 이집트에서 온 메일이었고, 모두 대문자로 작성되어 있었습니다. 이는 토큰을 대소문자 구분하도록 만든 직접적인 결과였습니다. '스팸 대책' 필터는 그것을 잡아내지 못했을 것입니다.

전반적인 오탐률이 얼마인지 말하기는 어렵습니다. 통계적으로 노이즈 수준에 있기 때문입니다. 필터(적어도 효과적인 필터) 작업을 해본 사람이라면 이 문제를 알고 있을 것입니다. 일부 이메일은 스팸인지 아닌지 판단하기 어렵고, 필터를 정말 엄격하게 설정했을 때 결국 살펴보게 되는 것이 바로 이런 이메일입니다. 예를 들어, 지금까지 필터는 오타 때문에 제 주소로 보내진 이메일 두 개와 제가 다른 사람이라고 착각하여 보내진 이메일 한 개를 잡아냈습니다. 논쟁의 여지는 있지만, 이것들은 제 스팸도 아니고 제 비스팸 메일도 아닙니다.

또 다른 오탐은 Virtumundo의 부사장으로부터 온 것이었습니다. 저는 고객인 척 그들에게 글을 썼고, 답장이 Virtumundo의 메일 서버를 통해 돌아왔기 때문에 상상할 수 있는 가장 유죄를 입증하는 헤더를 가지고 있었습니다. 이것 역시 진정한 오탐은 아니지만, 일종의 하이젠베르크 불확정성 원리(Heisenberg uncertainty effect)와 같습니다. 제가 스팸 필터링에 대해 쓰고 있었기 때문에 받은 것입니다.

이것들을 제외하고, 저는 지금까지 약 7740개의 합법적인 이메일 중 총 5개의 오탐을 경험했으며, 이는 0.06%의 비율입니다. 나머지 두 개는 제가 구매한 물건이 백오더되었다는 알림과 Evite에서 온 파티 알림이었습니다.

이 수치는 신뢰할 수 없다고 생각합니다. 표본 크기가 너무 작고, 이 중 일부를 필터가 잡아내지 않도록 수정할 수 있다고 생각하기 때문입니다.

오탐은 미탐과는 다른 종류의 오류라고 생각합니다. 필터링률은 성능 측정치입니다. 오탐은 버그에 가깝다고 생각합니다. 필터링률 향상은 최적화로, 오탐 감소는 디버깅으로 접근합니다.

따라서 이 다섯 가지 오탐은 제 버그 목록입니다. 예를 들어, 이집트에서 온 메일은 대문자 텍스트 때문에 필터에게 나이지리아 스팸처럼 보였기 때문에 걸렸습니다. 이것은 정말 일종의 버그입니다. HTML과 마찬가지로, 이메일이 모두 대문자인 것은 개념적으로 각 단어에 대한 하나의 특징이 아니라 하나의 특징입니다. 대소문자를 더 정교하게 처리해야 합니다.

그렇다면 이 0.06%를 어떻게 해석해야 할까요? 별 의미 없다고 생각합니다. 작은 표본 크기를 염두에 두고 상한선으로 취급할 수 있습니다. 하지만 이 단계에서는 베이즈 필터링의 본질적인 오탐률이라기보다는 제 구현의 버그를 측정하는 것에 가깝습니다.

미래

다음은 무엇일까요? 필터링은 최적화 문제입니다. 그리고 최적화의 핵심은 프로파일링입니다. 코드의 속도가 어디에서 느려지는지 추측하려고 하지 마십시오. 틀릴 것입니다. 코드의 속도가 어디에서 느려지는지 확인하고 그것을 고치십시오. 필터링에서는 이것이 다음과 같이 해석됩니다: 놓친 스팸을 살펴보고, 그것들을 잡기 위해 무엇을 할 수 있었는지 파악하십시오.

예를 들어, 스패머들은 이제 필터를 회피하기 위해 적극적으로 노력하고 있으며, 그들이 하는 일 중 하나는 필터가 단어를 인식하지 못하도록 단어를 쪼개거나 오타를 내는 것입니다. 하지만 이것에 집중하는 것은 제 최우선 순위가 아닙니다. 저는 여전히 이러한 스팸을 잡는 데 어려움이 없기 때문입니다 [10].

현재 제가 어려움을 겪고 있는 스팸은 두 가지 종류입니다. 하나는 여성으로부터 온 이메일인 척하며 채팅을 하거나 데이팅 사이트에서 프로필을 보라고 초대하는 유형입니다. 이런 스팸은 판매용 문구를 사용하지 않고도 판매를 유도할 수 있는 유일한 유형이기 때문에 통과됩니다. 일반적인 이메일과 같은 어휘를 사용합니다.

제가 필터링하기 어려운 또 다른 종류의 스팸은 불가리아 등지에서 계약 프로그래밍 서비스를 제공하는 회사들로부터 오는 것입니다. 이런 스팸은 저 역시 프로그래머이기 때문에 제 실제 메일과 같은 단어로 가득 차 있어서 통과됩니다.

아마도 개인 광고 유형에 먼저 집중할 것입니다. 더 자세히 살펴보면 이러한 스팸과 제 실제 메일 사이에 통계적 차이를 발견할 수 있을 것이라고 생각합니다. 글쓰기 스타일은 분명히 다르지만, 이를 잡아내려면 다중 단어 필터링이 필요할 수 있습니다. 또한, 그들은 URL을 반복하는 경향이 있는데, 합법적인 메일에 URL을 포함하는 사람은 그렇게 하지 않을 것입니다 [11].

아웃소싱 유형은 잡기 어려울 것입니다. 사이트에 크롤러를 보낸다 해도 결정적인 통계적 증거를 찾지 못할 것입니다. 아마도 유일한 해결책은 스팸에 광고된 도메인들의 중앙 목록일 것입니다 [12]. 하지만 이런 유형의 메일이 그렇게 많지는 않을 것입니다. 만약 남은 스팸이 불가리아에서 온 계약 프로그래밍 서비스에 대한 원치 않는 제안뿐이라면, 우리 모두는 아마 다른 일을 하러 넘어갈 수 있을 것입니다.

통계적 필터링이 실제로 우리를 그 지점까지 데려갈 수 있을까요? 모르겠습니다. 지금 당장 저 개인적으로는 스팸이 문제가 아닙니다. 하지만 스패머들은 아직 통계 필터를 속이기 위한 심각한 노력을 기울이지 않았습니다. 그들이 그렇게 한다면 어떻게 될까요?

저는 네트워크 수준에서 작동하는 필터에 대해 낙관적이지 않습니다 [13]. 극복할 가치가 있는 정적인 장애물이 있다면, 스패머들은 그것을 극복하는 데 매우 효율적입니다. 이미 Assurance Systems라는 회사가 여러분의 메일을 Spamassassin을 통해 실행하고 필터링될지 여부를 알려줄 것입니다.

네트워크 수준 필터가 완전히 쓸모없지는 않을 것입니다. Virtumundo나 Equalamail과 같이 자신들이 실제로 옵트인(opt-in) 목록을 운영한다고 주장하는 회사들의 '옵트인' 스팸을 모두 제거하는 데는 충분할 수 있습니다. 본문에 무엇이 쓰여 있든 헤더만으로도 그런 스팸을 필터링할 수 있습니다. 하지만 헤더를 위조하거나 오픈 릴레이를 사용할 의향이 있는 사람이라면, 아마도 대부분의 포르노 스패머를 포함하여, 원한다면 네트워크 수준 필터를 통과하는 메시지를 보낼 수 있을 것입니다. (그들이 보내고 싶어 하는 메시지는 결코 아닐지라도, 무언가는 보낼 수 있습니다.)

제가 낙관적으로 생각하는 필터는 각 개별 사용자의 메일을 기반으로 확률을 계산하는 필터입니다. 이러한 필터는 오탐을 피하는 데뿐만 아니라 필터링에서도 훨씬 더 효과적일 수 있습니다. 예를 들어, 메시지 내 어디에서든 Base64로 인코딩된 수신자의 이메일 주소를 찾는 것은 매우 좋은 스팸 지표입니다.

하지만 개별 필터의 진정한 장점은 모두 다를 것이라는 점입니다. 모든 사람의 필터가 다른 확률을 가진다면, 스패머의 최적화 루프, 즉 프로그래머들이 편집-컴파일-테스트 주기라고 부를 만한 것이 끔찍하게 느려질 것입니다. 그들은 데스크톱에 있는 어떤 필터의 복사본을 통과할 때까지 스팸을 조정하는 대신, 각 조정마다 테스트 메일을 보내야 할 것입니다. 이는 대화형 최상위 레벨이 없는 언어로 프로그래밍하는 것과 같을 것이며, 저는 누구에게도 그런 일을 바라지 않습니다.

주석

[1] Paul Graham. '스팸 대책.' 2002년 8월. http://paulgraham.com/spam.html.

이 알고리즘의 확률은 베이즈 정리(Bayes' Rule)의 퇴화된 경우를 사용하여 계산됩니다. 두 가지 단순화 가정이 있습니다: 특징(즉, 단어)의 확률이 독립적이라는 것, 그리고 이메일이 스팸일 사전 확률에 대해 아무것도 모른다는 것입니다.

첫 번째 가정은 텍스트 분류에서 널리 퍼져 있습니다. 이를 사용하는 알고리즘은 '나이브 베이즈(naive Bayesian)'라고 불립니다.

두 번째 가정은 제 수신 메일에서 스팸의 비율이 매일(실제로 매시간) 너무 많이 변동하여 전체 사전 비율이 예측 변수로서 가치가 없다고 판단했기 때문에 제가 세운 것입니다. P(스팸)과 P(비 스팸)이 모두 0.5라고 가정하면, 이들은 상쇄되어 공식에서 제거할 수 있습니다.

스팸 대 비 스팸의 비율이 일관되게 매우 높거나(특히) 매우 낮은 상황에서 베이즈 필터링을 수행한다면, 사전 확률을 통합하여 필터 성능을 향상시킬 수 있을 것입니다. 이를 올바르게 수행하려면 스팸과 합법적인 메일 볼륨 모두 뚜렷한 일일 패턴을 가지고 있기 때문에 시간대별 비율을 추적해야 할 것입니다.

[2] Patrick Pantel과 Dekang Lin. 'SpamCop-- 스팸 분류 및 조직 프로그램.' AAAI-98 텍스트 분류를 위한 학습 워크숍 회의록.

[3] Mehran Sahami, Susan Dumais, David Heckerman, Eric Horvitz. '정크 이메일 필터링을 위한 베이즈 접근법.' AAAI-98 텍스트 분류를 위한 학습 워크숍 회의록.

[4] 당시 저는 약 4,000개의 합법적인 이메일 중 오탐이 전혀 없었습니다. 만약 다음 합법적인 이메일이 오탐이었다면, 이는 0.03%를 의미했을 것입니다. 이러한 오탐률은 제가 나중에 설명하듯이 신뢰할 수 없습니다. 제가 여기서 숫자를 인용하는 것은 오탐률이 얼마든 간에 1.16% 미만이라는 점을 강조하기 위함입니다.

[5] Bill Yerazunis. '희소 이진 다항 해시 메시지 필터링 및 CRM114 판별기.' 2003년 스팸 컨퍼런스 회의록.

[6] '스팸 대책'에서는 0.99와 0.01의 임계값을 사용했습니다. 코퍼스 크기에 비례하는 임계값을 사용하는 것이 정당해 보입니다. 이제 각 유형의 메일이 약 10,000개 정도 있으므로, 0.9999와 0.0001을 사용합니다.

[7] 여기에는 제가 고쳐야 할 결함이 있습니다. 현재 'Subjectfoo'가 단순히 'foo'로 퇴화할 때, 이는 제가 표시한 헤더 줄 외의 본문이나 헤더 줄에서 'foo'의 출현 통계를 얻는다는 의미입니다. 제가 해야 할 일은 'foo'의 전체 통계뿐만 아니라 특정 버전의 통계도 추적하고, 'Subjectfoo'를 'foo'가 아닌 'Anywhere*foo'로 퇴화시키는 것입니다. 대소문자도 마찬가지입니다. 대문자에서 소문자가 아닌 모든 대소문자로 퇴화시켜야 합니다.

가격에도 이렇게 하는 것이 아마도 이득일 것입니다. 예를 들어, '$129.99'를 '$--9.99', '$--.99', '$--'로 퇴화시키는 것입니다.

단어를 어간으로 퇴화시킬 수도 있지만, 이는 코퍼스가 작을 때 초기 필터링률만 향상시킬 것입니다.

[8] Steven Hauser. '통계적 스팸 필터가 나에게 효과가 있다.' http://www.sofbot.com.

[9] 오탐은 모두 동일하지 않으며, 스팸을 막는 기술을 비교할 때 이 점을 기억해야 합니다. 필터로 인해 발생하는 많은 오탐은 놓쳐도 괜찮을 만한 '거의 스팸'인 반면, 블랙리스트로 인해 발생하는 오탐은 예를 들어 잘못된 ISP를 선택한 사람들의 메일일 뿐입니다. 두 경우 모두 스팸에 가까운 메일을 잡아내지만, 블랙리스트의 경우 근접성은 물리적이고, 필터의 경우 텍스트적입니다.

[10] 스패머가 토큰을 모호하게 만드는 데 충분히 능숙해져서 이것이 문제가 된다면, 우리는 단순히 공백, 마침표, 쉼표 등을 제거하고 사전을 사용하여 결과 시퀀스에서 단어를 추출하는 것으로 대응할 수 있습니다. 그리고 물론 이런 방식으로 원본 텍스트에 보이지 않던 단어를 찾는 것 자체가 스팸의 증거가 될 것입니다.

단어를 추출하는 것이 사소한 일은 아닐 것입니다. 단순히 단어 경계를 재구성하는 것 이상이 필요할 것입니다. 스패머는 글자를 추가(예: 'xHot nPorn cSite')하고 생략(예: 'P#rn')하기도 합니다. 인간의 시각이 그러한 속임수가 접근할 수 있는 한계이므로, 시각 연구가 여기서 유용할 수 있습니다.

[11] 일반적으로 스팸은 일반 이메일보다 반복적입니다. 그들은 메시지를 각인시키고 싶어 합니다. 저는 현재 상위 15개 토큰에 중복을 허용하지 않습니다. 발신자가 우연히 나쁜 단어를 여러 번 사용하면 오탐이 발생할 수 있기 때문입니다. (제 현재 필터에서 'dick'는 스팸 확률이 0.9999이지만, 이름이기도 합니다.) 하지만 적어도 중복을 인지해야 할 것 같으므로, Brian Burton이 SpamProbe에서 하는 것처럼 각 토큰을 최대 두 개까지 허용하는 것을 시도해 볼 수 있습니다.

[12] 스패머가 메시지의 다른 모든 것을 생성하기 위해 매드-립(mad-lib) 기술을 사용하도록 강요받으면 Brightmail과 같은 접근 방식이 퇴화할 것입니다.

[13] 때때로 네트워크 수준에서 필터링 작업을 해야 한다고 주장되는데, 이는 더 효율적이기 때문입니다. 사람들이 이렇게 말할 때 보통 의미하는 것은 '우리는 현재 네트워크 수준에서 필터링하고 있으며, 처음부터 다시 시작하고 싶지 않다'는 것입니다. 하지만 해결책에 맞춰 문제를 지시할 수는 없습니다.

역사적으로 희소 자원 주장은 소프트웨어 설계 논쟁에서 패배하는 측이었습니다. 사람들은 다른 이유로 내린 선택(특히 무대응)을 정당화하기 위해서만 이런 주장을 사용하는 경향이 있습니다.

감사합니다

이 논문의 초안을 읽어준 Sarah Harlin, Trevor Blackwell, Dan Giffin에게 감사드립니다. 그리고 이 필터가 실행되는 대부분의 인프라를 제공해준 Dan에게 다시 한번 감사드립니다.

관련 글: