스팸 필터링의 효과적인 방법으로 베이즈 통계적 접근을 제안하며, 그 작동 원리와 실제 적용, 그리고 스팸 정의 등에 대해 상세히 설명한 글입니다.
2002년 8월
(이 글은 우리가 Arc를 시험하기 위해 만든 스팸 방지 웹 기반 메일 리더에서 사용한 스팸 필터링 기법을 설명합니다. 보다 개선된 알고리즘은 Better Bayesian Filtering에서 다룹니다.)
저는 스팸을 막을 수 있으며, 콘텐츠 기반 필터가 그 방법이라고 생각합니다. 스팸 발송자의 아킬레스건은 바로 그들의 메시지입니다. 그들은 여러분이 설치하는 어떤 장벽이든 우회할 수 있습니다. 실제로 지금까지 그렇게 해왔죠. 하지만 그들은 어떠한 형태로든 메시지를 전달해야만 합니다. 우리가 그 메시지를 인식할 수 있는 소프트웨어를 만든다면, 그들은 결코 이를 우회할 수 없습니다.
받는 사람 입장에서 스팸은 금방 알아차릴 수 있습니다. 누군가 당신의 메일을 읽고 스팸을 걸러내는 일을 시킨다면 별다른 어려움 없이 할 수 있을 것입니다. AI까지는 아니더라도, 어느 정도까지 이 과정을 자동화할 수 있을까요?
저는 꽤 간단한 알고리즘으로 이 문제를 해결할 수 있다고 생각합니다. 실제로, 현재의 스팸을 개별 단어의 스팸 확률의 베이즈 결합만으로도 꽤 잘 걸러낼 수 있습니다. 약간 조정된(아래에 설명된) 베이즈 필터를 사용하면, 현재는 스팸 1,000개당 5개 미만을 놓치고, 오탐(false positive)은 0개입니다.
통계적 접근은 보통 스팸 필터를 만들 때 사람들이 처음 시도하는 방법이 아닙니다. 대부분의 해커들은 먼저 스팸의 개별 특성을 인식하는 소프트웨어를 만들려고 합니다. 스팸 메일을 보고 "친애하는 친구님"으로 시작하거나, 제목이 모두 대문자이고 느낌표가 8개 붙은 메일을 보고 기막혀하면서 이런 것쯤은 한 줄 코드로 거를 수 있다고 생각하죠.
그리고 실제로 그렇게 하면 처음엔 잘 됩니다. 간단한 규칙 몇 가지로도 스팸의 상당 부분을 걸러낼 수 있죠. 예를 들어 "click"이라는 단어만 찾아도 제 스팸 집합에서 79.7%의 메일을 걸러내고, 오탐은 1.2%밖에 안 됩니다.
저도 통계적 방법을 쓰기 전에 반년 정도 개별 스팸 특징을 찾는 소프트웨어를 개발했습니다. 그런데 마지막 몇 퍼센트를 인식하는 것이 점점 어려워졌고, 필터를 엄격하게 만들수록 오탐도 늘었습니다.
오탐이란 무고한 이메일이 실수로 스팸으로 분류되는 경우를 말합니다. 대부분의 사용자에게는 정상 메일을 놓치는 것이 차라리 스팸을 받는 것보다 훨씬 큰 문제입니다. 즉, 오탐이 있는 필터는 마치 부작용에 치명적 위험이 있는 여드름 치료제와 같습니다.
사용자가 스팸을 많이 받을수록 스팸폴더에 정상 메일이 하나 들어가도 눈치채지 못할 가능성이 커집니다. 그리고 필터가 좋아질수록 사용자는 걸러진 메일을 더욱 신뢰하게 되어, 오탐의 위험도 커집니다.
왜 통계적 방법을 그토록 오래 시도하지 않았는지 모르겠습니다. 아마도 스팸 특징을 직접 식별하는 데 중독됐기 때문일 겁니다. 이는 일종의 스팸 발송자와의 경쟁 게임 같은 기분이 들기도 합니다(비해커들은 잘 모르지만, 해커들은 굉장히 경쟁적입니다). 통계적 분석을 시도해 보니, 즉시 저보다 훨씬 똑똑하다는 것을 알았습니다. "virtumundo"나 "teens" 같은 단어가 스팸에 좋은 지표라는 것도 당연히 발견하지만, "per"나 "FL", "ff0000"(밝은 빨간색 html 코드) 같은 단어도 좋은 지표라고 알려줍니다. 실제로 "ff0000"은 그 어떤 음란어 못지않게 강력한 스팸 지표입니다.
통계적 필터링 방법을 간단히 소개하겠습니다. 스팸 메일 집합과 정상 메일 집합을 만듭니다. 현재 각 집합엔 약 4,000개의 메일이 들어 있습니다. 각 메일의 전체 텍스트(헤더, 포함된 html, 자바스크립트 포함)를 스캔합니다. 현재는 영숫자, 대시, 작은따옴표, 달러 기호까지 토큰(token)으로 취급하며, 나머지는 토큰 구분자로 보고 있습니다(개선 여지가 있습니다). 모두 숫자로만 된 토큰은 무시하며, html 주석도 무시합니다.
각 집합마다 토큰이 나타난 횟수를 셉니다(대소문자 무시). 그 결과, 각각의 집합에 대해 토큰 → 등장 횟수의 큰 해시테이블 두 개가 생깁니다.
다음으로 각 토큰이 있는 메일이 스팸일 확률을 세 번째 해시테이블에 저장합니다. 그 계산은 다음과 같습니다.[1]
lisp(let ((g (* 2 (or (gethash word good) 0))) (b (or (gethash word bad) 0))) (unless (< (+ g b) 5) (max .01 (min .99 (float (/ (min 1 (/ b nbad)) (+ (min 1 (/ g ngood)) (min 1 (/ b nbad)))))))))
여기서 word는 계산 중인 토큰, good과 bad는 앞서 만든 해시테이블, ngood과 nbad는 정상 및 스팸 메일 개수입니다.
코드로 설명한 이유는 중요한 부분을 강조하기 위해서입니다. 오탐을 방지하려고 스팸이 아닌 쪽의 수치를 두 배로 잡습니다. 이런 방법이 정상 메일에 가끔 나오는 단어와 거의 나오지 않는 단어를 구분하는 데 좋습니다. 다섯 번 이상 등장한 단어만 사용(스팸이 아닌 쪽에서 세 번 등장해도 됨)하며, 한 쪽 집합에만 있는 단어의 확률은 .01 또는 .99로 둡니다. 튜닝 여지는 있지만 데이터가 쌓이면 자동으로 보정됩니다.
집합 전체를 단일 텍스트 스트림으로 보지만, 확률 계산 분모에는 메일 건수를 씁니다. 이 또한 오탐 방지에 약간의 편향 효과를 줍니다.
새로운 메일이 오면 토큰화한 후, 스팸성 확률이 .5에서 가장 먼 단어 15개를 골라 그 확률을 합산해 메일의 스팸 확률을 계산합니다(베이즈 결합 방식 설명). 만약 테이블에 없는 단어라면 .4 정도로 둡니다. 처음 보는 단어라면 대체로 무탈한 경우가 많고, 스팸 단어는 대부분 익숙하니까요.
실제 이메일에 이 알고리즘을 적용한 예시는 맨 뒤 부록에 있습니다.
이렇게 계산해 확률이 0.9가 넘으면 스팸으로 간주합니다. 하지만 실제로는 대부분의 확률이 0.9 또는 0.1 근처에 몰리므로 임계값 위치가 큰 영향을 주진 않습니다.
통계적 접근의 큰 장점 중 하나는 스팸을 그리 많이 읽지 않아도 된다는 점입니다. 지난 6개월 동안 수천 개의 스팸을 읽었는데, 정말 우울해집니다. 노버트 위너가 말하길, 노예와 경쟁하면 자신도 노예가 된다고 했죠. 스팸 발송자와 경쟁하려면 그들의 머릿속에 들어가 봐야 하는데, 저는 가능한 스팸 발송자 머릿속에 있고 싶지 않습니다.
베이즈식 접근의 진짜 장점은 측정치가 명확하다는 것입니다. 스팸어새신 같은 필터는 스팸 "점수"를 매기지만, 베이즈 방식은 실제 확률을 할당합니다. "점수"는 무엇을 의미하는지 사용자도, 개발자도 모릅니다. 그러나 확률은 명확하게 해석됩니다. 예를 들어, "sex"는 약 .97, "sexy"는 .99, 둘 다 나오면 .9997의 확률로 스팸이 됩니다.
베이즈 방식은 메일 전체의 모든 단서를 반영합니다. 스팸에 거의 등장하지 않는 단어(예: "though", "tonight", "apparently" 등)는 스팸성 확률을 낮추는 데 기여합니다. 그래서 "sex"가 들어간 정상 메일이 스팸으로 분류될 일은 거의 없습니다.
이상이지만, 확률은 각 사용자 개별적으로 계산되는 것이 이상적입니다. 예를 들어 저는 "Lisp"가 들어간 메일을 자주 받지만 스팸에는 없습니다. 이런 단어는 제게 메일을 보내는 일종의 패스워드처럼 작동합니다. 이전에는 이런 단어를 목록으로 관리했지만, 베이즈 필터는 알아서 이 기능을 수행하고, 제가 놓친 단어까지 찾아냅니다.
앞서 스팸 1,000개당 5개 미만을 놓친다고 했는데, 이는 제 메일에 대해 훈련한 결과입니다. 그러나 이것이 곧 사용자별 스팸/정상 메일 기반으로 각 메일을 필터링하자는 주장과 일치합니다. 즉, 각 사용자에게 두 개의 삭제버튼(일반 삭제, 스팸으로 삭제)이 있고, "스팸으로 삭제"된 것은 스팸 집합, 나머지는 정상 집합에 담깁니다.
초기에는 씨앗 필터를 제공할 수 있지만, 결국 각 사용자가 받은 메일 기반으로 단어별 확률을 가져야 합니다. 그래야 (a) 필터가 더 정확해지고, (b) 스팸의 정확한 기준이 각 사용자에 따라 달라지며, (c) 스팸 발송자가 모든 사용자 필터를 뚫기 어렵게 됩니다.
콘텐츠 기반 필터는 종종 화이트리스트와 결합됩니다. 화이트리스트 중 하나는 사용자가 메일을 보낸 적이 있는 주소 목록입니다. 메일 리더가 "스팸 삭제" 버튼이 있다면 보통 삭제한 메일의 보낸 주소도 자동으로 화이트리스트에 추가할 수 있습니다.
저는 화이트리스트를 필터링 향상보다는 연산 절감용 보조책으로 옹호합니다. 처음에는 화이트리스트가 필터링을 더 쉽게 해줄 줄 알았지만, 실제로는 사용자도 여러 이메일 주소를 쓸 수 있으므로, 새로운 보낸이 주소라고 해서 첫 메일이 아닐 수 있습니다. 갑자기 친구가 새로운 이메일로 연락할 수도 있고, 모르는 주소라고 지나치게 엄격하게 거르면 오탐 위험이 높아집니다.
어떤 의미에선, 제 필터는 메일 전체(헤더 포함)를 기반으로 하므로 화이트/블랙리스트 역할도 부분적으로 수행합니다. 저는 신뢰하는 발신인의 주소, 메일 경로까지 알고 있으며, 이는 스팸 발송자 및 서버명, 메일러 버전, 프로토콜 등에도 적용됩니다.
현재 수준의 필터링 성능을 유지할 수 있다면 저는 이 문제가 해결됐다고 할 겁니다. 하지만 스팸은 진화하므로, 현재 대부분의 스팸을 막는 것만으론 부족합니다. 지금까지의 스팸 방지 기법 대부분은 해충 방제제에 불과해서 더 강한 내성 스팸만 만들어냈습니다.
베이즈 필터는 스팸에 맞춰 진화하므로 더 희망적입니다. 스팸 발송자가 단어 일부를 바꿔도 베이즈 필터는 즉시 그 변화까지 학습합니다. 예를 들어 "cock" 대신 "c0ck"를 써도, 베이즈 필터는 둘의 차이까지 정량적으로 반영합니다.
그럼에도, 필터 설계자는 항상 스팸 발송자가 알고리즘을 정확히 알아도 통과가 가능한지 답할 수 있어야 합니다. 예컨대 체크섬 기반 필터가 장벽이 되면 스팸 발송자는 메드립(mad-lib)식 본문변환 등으로 우회할 겁니다.
베이즈 필터를 뚫으려면 스팸 발송자는 메일을 평범한 정상 메일과 구별 못 하게 만들어야 합니다. 하지만 대부분의 스팸은 판촉 메일이므로, 사용자의 일반 메일과는 성격이 달라지고, 필연적으로 드러나게 됩니다. 또한 헤더(경로, 서버, 발송 방식 등) 역시 정상 메일과 다르므로 더욱 어렵습니다.
만약 헤더 문제까지도 해결했다고 해도, 미래의 스팸은 대략 이런 식이 될 겁니다:
Hey there. Thought you should check out the following: http://www.27meg.com/foo
콘텐츠 필터링에 걸리지 않으려면, 실제로 이 정도가 한계일 겁니다. 실상 URL만으로도 충분히 의심할만합니다.
스팸 발송자는 단순히 불법적인 자들뿐 아니라, 자기 신원을 숨기지 않는 기업형도 있습니다. 만약 필터로 이런 스팸 유형을 극단적으로 제한할 수 있다면, 다양한 관련 법적 요구(구독 취소 안내 등)로 인해 그들은 훨씬 더 쉽게 필터에 걸릴 것입니다.
(저는 옛날엔 법률로 스팸이 줄어들 것이라고 믿지 않았지만, 지금은 더 강한 법률이 스팸의 발송량은 크게 못 줄여도 수신자가 보는 양은 줄이고, 필터링에는 도움될 것으로 봅니다.)
어떤 종류의 스팸이든, 판촉 메시지 자체를 제한하면 스팸 비즈니스는 줄어듭니다. 중요한 건 스팸도 결국 "비즈니스"라는 점입니다. 스팸 발송자들은(극히 낮은 반응률에도 불구하고) 비용이 거의 안 들기 때문에 스팸을 계속 보냅니다. 수신자 전체를 통틀면 지는 피해는 엄청나지만, 스팸 발송자는 그것을 부담하지 않습니다.
물론 스팸 발송자도 약간의 비용을 치릅니다.[2] 하지만 우리가 필터링으로 반응률을 계속 낮춘다면, 스팸을 보낼 유인은 점점 줄어듭니다.
스팸 발송자들이 선정적이고 현혹적인 광고문구를 쓰는 이유는 반응률을 높이기 위해서입니다. 스팸에 응답하는 사람들은 대체로 속기 쉽거나 현실을 부정하는 경향이 있으므로, 현혹적인 메시지가 효과적입니다. "Thought you should check out the following" 같은 평범한 문구로는 지금 스팸처럼 반응을 이끌기 어렵습니다. 결국 판촉이 불가능해지면 스팸의 효용이 떨어지고, 스팸 사업자는 줄어듭니다.
이게 궁극적인 대승입니다. 저도 처음엔 "스팸을 이제 더 못 보겠다"는 생각으로 스팸 필터링 소프트웨어를 만들기 시작했지만, 만약 우리가 정말 효과적으로 스팸을 차단한다면, 결국 스팸 자체가 사라질 수 있습니다.
스팸 방지(법률 포함) 중에서 베이즈 필터가 단일 방식으론 가장 효과적이라고 믿습니다. 그러나 다양한 방식이 병행될수록 좋고, 콘텐츠 기반 필터 내부적으로도 여러 종류의 소프트웨어가 함께 쓰이면 좋습니다. 그래야 스팸 발송자가 모두를 뚫는 스팸을 설계하기 어렵습니다.
부록: 필터링 예시
여기는 이 글을 쓰는 도중 도착한 실제 스팸입니다. 가장 "흥미로운" 15개 단어는 다음과 같습니다:
qvp0045 indira mx-05 intimail $7500 freeyankeedom cdo bluefoxmedia jpg unsecured platinum 3d0 qves 7c5 7c266675
헤더와 본문 단어가 뒤섞여 있는데, 이게 전형적 스팸입니다. 이 단어들은 모두 제 데이터베이스에서 스팸 확률이 .99입니다. 실제론 .99인 단어가 더 많지만 여기선 15개만 뽑았습니다.
흥미로운 확률 다양성은 이 예시를 보면 알 수 있습니다:
madam 0.99 promotion 0.99 republic 0.99 shortest 0.047 mandatory 0.047 standardization 0.073 sorry 0.082 supported 0.090 people's 0.090 enter 0.908 quality 0.892 organization 0.124 investment 0.857 very 0.148 valuable 0.823
여기는 "좋은" 단어와 "나쁜" 단어가 섞였습니다. 이런 조합이 있더라도, 베이즈 규칙으로 확률을 합산하면 결과적으로 .9027이 나옵니다.
"madam"은 전통적인 스팸 인사말에서, "republic"은 흔히 나이지리아 사기와 연관된 스팸에서 옵니다. "enter"는 주로 스팸 해제 안내에서 등장하지만, 여기선 무고하게 나왔습니다. 다행히 통계적 방식은 이런 정도의 미스는 충분히 감내할 수 있습니다.
필터를 통과한 드문 사례는 여기에서 볼 수 있습니다. 왜 통과했을까요? 우연히 제 실제 메일에서 자주 쓰는 단어가 대거 들어있었기 때문입니다:
perl 0.01 python 0.01 tcl 0.01 scripting 0.01 morris 0.01 graham 0.015 guarantee 0.976 cgi 0.973 paul 0.027 quite 0.031 pop3 0.042 various 0.061 prices 0.936 managed 0.065 difficult 0.072
다행히, 이런 메일은 평범한 사용자(프로그래밍 언어, 지인 Morris가 없는 경우)에겐 전부 중립 단어로 처리되어 스팸 확률에 큰 영향을 주지 않습니다. 또, 단어 쌍 기반으로 필터링하면 "cost effective", "setup fee", "money back" 등으로 추가로 잡을 수도 있습니다. 반복적으로 스팸이 오면 그 단어도 학습하게 됩니다.
마지막으로, 이곳은 정상 메일 예시입니다:
continuation 0.01 describe 0.01 continuations 0.01 example 0.034 programming 0.052 i'm 0.055 examples 0.080 color 0.919 localhost 0.099 hi 0.117 california 0.844 same 0.160 spot 0.165 us-ascii 0.168 what 0.192
거의 모든 단어가 무고함을 나타냅니다. "color"(스팸은 색깔 있는 폰트를 좋아함), "California"(후기, 폼 메뉴 등에서 등장)가 그나마 스팸 느낌이지만, 다른 정상 단어들이 충분히 압도합니다. "describe"가 한 번도 스팸에서 안 쓰였다는 점도 흥미롭습니다. 스팸 분석을 하다보면 스팸이 사용하는 언어가 매우 제한되어 있음을 알 수 있는데, 그런 점이 베이즈 필터의 강점입니다.
부록: 추가 아이디어
아직 시도하지 않았지만, 단어 쌍(혹은 세 단어 조합) 기반으로 필터링하면 더 정밀한 확률 추정을 할 수 있습니다. 현재 제 데이터베이스에서 "offers"의 확률이 .96이라면, 단어쌍 "special offers"는 .99, "approach offers"은 .1에 불과할 수 있습니다.
개별 단어만으로도 이미 필터 성능이 충분히 좋아 시도하지 않았지만, 스팸이 점점 교묘해지면 단어쌍 분석도 필요할 수 있습니다(이 경우 본질적으로 역방향 마르코프 체인 기반 텍스트 생성기와 유사함).
특정한 스팸 특징(예: 받는사람 주소 없음)도 중요한데, 이들도 가상 단어로서 알고리즘에 포함시킬 수 있습니다. 아마 차후 버전에선 주요 스팸 신호 몇 개를 별도 변수로 처리할 예정입니다. 개별 특징 인식 기반 필터에도 일리 있지만, 결정 근거 병합 방식이 부족할 뿐입니다.
스팸 특징 인식보다 정상 메일 특징 인식이 더 중요할 수 있습니다. 오탐 방지가 매우 중요하므로, 나중엔 오탐 방지만을 위한 2차 필터도 고려할 예정입니다. 이런 2차 필터는 통계적이기보다는 경험 기반이 될 것 같습니다.
또 한 가지는 메일의 특정부위(예: URL)에 초점을 맞추는 방법입니다. 스팸 중 95%가 방문을 유도하는 url을 포함합니다. url만으로도 스팸 여부를 파악할 수 있는 경우도 많습니다.
도메인명은 평범한 텍스트와 달리 여러 단어가 합쳐져 있으므로, 분해해서 확률 합산하면 더욱 정밀한 판별이 가능합니다. 특히 점점 스팸이 본문 단어를 우회할수록, 이런 처리가 중요해집니다.
스팸 url 목록을 협력적으로 관리하는 것도 좋은 아이디어입니다. 신뢰성 평가(trust metric)가 필요하겠지만, 실현된다면 여러 필터 소프트웨어에 유용하게 쓰일 수 있습니다.
또 다른 아이디어로는 수상한 url에 대해, 사용자가 메일을 보기 전 크롤러로 사이트 내용을 자동 분석해, 그 결과를 이메일 스팸 확률에 포함시키는 방법도 있습니다.
공동으로 방대한 스팸 집합(코퍼스)을 만드는 것 역시 훌륭한 계획입니다. 대규모, 깨끗한 코퍼스가 있어야 베이즈 필터가 잘 작동합니다. 안티스팸 연구 전반에서도 좋은 테스트셋이 됩니다. 물론 개인정보(주소, cc, 구독 해지 url의 인자 등) 삭제 등 기술적 문제와 신뢰 기준이 필요합니다. 누군가 이 프로젝트를 추진한다면 세상에 큰 도움일 것입니다.
부록: 스팸의 정의
스팸이 뭔지 대충 합의는 있지만, 명확한 정의가 있으면 여러모로 좋을 것입니다. 예를 들어, 스팸 코퍼스를 만들거나 필터링 성능 비교시에도 필요합니다.
우선, 스팸은 "비요청 상업 메일"이 아닙니다. 예를 들어, 내가 오래된 Raleigh 3단 자전거를 찾는다는 소문을 들은 이웃이 이를 판다고 메일을 준다면 아주 반가울 겁니다. 이 메일은 상업적이고 비요청이지만, 스팸은 아닙니다. 스팸의 핵심은 일괄 자동화입니다.
상업적이든 아니든, 자동화 대량 메일이면 스팸입니다. 대량 정치운동 홍보 메일도 마찬가지입니다.
저는 스팸을 비요청 자동화 메일로 정의합니다. 이 정의는 많은 법적 스팸 정의보다 포함 범위가 넓습니다. 기업에서 "관계 있음"을 이유로 보내는 대량 메일도, 명시적으로 구독에 동의하지 않았다면 여전히 스팸입니다.
기업들이 고객에게 "수신 거부(unsubscribe)"나 "계정 설정 변경"을 요청해도, 미수신 선택을 하지 않았다는 것이 곧 수신 동의(opt-in)가 아닙니다. 명시적으로 체크박스를 선택하지 않았다면 스팸입니다.
물론, 어떤 비즈니스 관계에서는 특정 메일을 암묵적으로 허락합니다. 온라인 주문시 영수증이나 발송 안내 등은 괜찮습니다. 하지만 무료 가이드 같은 광고성 메일은 스팸입니다.
주석:
감사의 말: Sarah Harlin(초안 검토), Daniel Giffin(스팸 인프라 구축과 필터아이디어), Robert Morris, Trevor Blackwell, Erann Gat(수많은 스팸 논의), Raph Levien(신뢰성 평가 조언), Chip Coldwell, Sam Steingold(통계 조언)에게 감사드립니다.
추가 정보: