스팸 대책
만들기를 좋아하시나요? Hacker News를 방문해 보세요.
2002년 8월
(이 글은 Arc를 시험하기 위해 구축한 스팸 방지 웹 기반 메일 리더에 사용된 스팸 필터링 기술을 설명합니다. 개선된 알고리즘은 더 나은 베이즈 필터링에 설명되어 있습니다.)
저는 스팸을 막을 수 있으며, 내용 기반 필터가 그 방법이라고 생각합니다. 스패머의 아킬레스건은 그들의 메시지입니다. 그들은 당신이 설정하는 다른 어떤 장벽도 우회할 수 있습니다. 적어도 지금까지는 그랬습니다. 하지만 그들은 어떤 메시지든 전달해야 합니다. 만약 우리가 그들의 메시지를 인식하는 소프트웨어를 작성할 수 있다면, 그들이 그것을 피할 방법은 없습니다.
수신자에게 스팸은 쉽게 인식됩니다. 만약 당신이 메일을 읽고 스팸을 버릴 사람을 고용한다면, 그들은 거의 어려움 없이 그 일을 할 것입니다. AI를 제외하고, 이 과정을 자동화하기 위해 얼마나 많은 일을 해야 할까요?
저는 우리가 상당히 간단한 알고리즘으로 문제를 해결할 수 있을 것이라고 생각합니다. 사실, 저는 개별 단어의 스팸 확률을 베이즈 결합하는 것만으로도 현재의 스팸을 충분히 잘 필터링할 수 있다는 것을 발견했습니다. 약간 수정된(아래 설명 참조) 베이즈 필터를 사용하여, 현재 1000개의 스팸 중 5개 미만을 놓치고 있으며, 오탐은 0입니다.
통계적 접근 방식은 사람들이 스팸 필터를 작성할 때 보통 처음 시도하는 방법이 아닙니다. 대부분의 해커들은 스팸의 개별 속성을 인식하는 소프트웨어를 작성하려고 시도하는 것이 첫 번째 본능입니다. 당신은 스팸을 보고 생각합니다. 'Dear Friend'로 시작하거나 제목이 모두 대문자이고 여덟 개의 느낌표로 끝나는 메일을 보내려는 이 사람들의 뻔뻔함이라니. 나는 한 줄의 코드로 그런 것들을 필터링할 수 있어.
그래서 당신은 그렇게 하고, 처음에는 작동합니다. 몇 가지 간단한 규칙으로 수신되는 스팸의 상당 부분을 제거할 수 있습니다. 단순히 'click'이라는 단어를 찾는 것만으로도 제 스팸 코퍼스에 있는 이메일의 79.7%를 잡아내고, 오탐은 1.2%에 불과합니다.
저는 통계적 접근 방식을 시도하기 전에 약 6개월 동안 개별 스팸 특징을 찾는 소프트웨어를 작성했습니다. 제가 발견한 것은 마지막 몇 퍼센트의 스팸을 인식하는 것이 매우 어려워졌고, 필터를 엄격하게 만들수록 오탐이 더 많아졌다는 것입니다.
오탐은 스팸으로 잘못 식별되는 무고한 이메일입니다. 대부분의 사용자에게는 합법적인 이메일을 놓치는 것이 스팸을 받는 것보다 훨씬 더 나쁩니다. 따라서 오탐을 유발하는 필터는 환자에게 사망 위험을 수반하는 여드름 치료제와 같습니다.
사용자가 스팸을 더 많이 받을수록, 스팸 폴더에 있는 무고한 메일 하나를 알아차릴 가능성은 줄어듭니다. 그리고 이상하게도, 스팸 필터가 더 좋아질수록 오탐은 더 위험해집니다. 왜냐하면 필터가 정말 좋으면 사용자는 필터가 걸러낸 모든 것을 무시할 가능성이 더 높기 때문입니다.
왜 그렇게 오랫동안 통계적 접근 방식을 피했는지 모르겠습니다. 스패머들과 일종의 경쟁 게임을 하는 것처럼, 스팸 특징을 직접 식별하려는 시도에 중독되었기 때문인 것 같습니다. (비해커들은 종종 이것을 깨닫지 못하지만, 대부분의 해커들은 매우 경쟁적입니다.) 통계 분석을 시도했을 때, 저는 즉시 그것이 저보다 훨씬 더 영리하다는 것을 발견했습니다. 물론 'virtumundo'나 'teens'와 같은 용어가 스팸의 좋은 지표라는 것을 발견했습니다. 하지만 'per'와 'FL' 그리고 'ff0000'도 스팸의 좋은 지표라는 것을 발견했습니다. 사실, 'ff0000'(밝은 빨간색을 나타내는 HTML 코드)은 어떤 포르노 용어만큼이나 좋은 스팸 지표로 밝혀졌습니다.
제가 통계적 필터링을 하는 방법에 대한 개요입니다. 저는 하나의 스팸 코퍼스와 하나의 비스팸 메일 코퍼스로 시작합니다. 현재 각각 약 4000개의 메시지가 들어 있습니다. 저는 각 코퍼스의 각 메시지에 있는 헤더와 포함된 HTML, 자바스크립트를 포함한 전체 텍스트를 스캔합니다. 현재 저는 영숫자 문자, 대시, 아포스트로피, 달러 기호를 토큰의 일부로 간주하고, 나머지는 모두 토큰 구분자로 간주합니다. (여기에는 개선의 여지가 있을 것입니다.) 저는 모든 숫자로만 이루어진 토큰은 무시하고, HTML 주석도 토큰 구분자로 간주하지 않고 무시합니다.
저는 각 코퍼스에서 각 토큰(현재는 대소문자 무시)이 나타나는 횟수를 셉니다. 이 단계에서 저는 두 개의 큰 해시 테이블을 얻게 되는데, 각 코퍼스에 하나씩, 토큰을 출현 횟수에 매핑합니다.
다음으로 세 번째 해시 테이블을 만듭니다. 이번에는 각 토큰을 해당 토큰을 포함하는 이메일이 스팸일 확률에 매핑합니다. 이 확률은 다음과 같이 계산합니다 [1]: (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는 각각 비스팸 메시지와 스팸 메시지의 수입니다.
제가 이것을 코드로 설명한 것은 몇 가지 중요한 세부 사항을 보여주기 위함입니다. 저는 오탐을 피하기 위해 확률에 약간의 편향을 주고 싶었고, 시행착오를 통해 good에 있는 모든 숫자를 두 배로 늘리는 것이 좋은 방법이라는 것을 발견했습니다. 이것은 합법적인 이메일에서 가끔 나타나는 단어와 거의 나타나지 않는 단어를 구별하는 데 도움이 됩니다. 저는 총 5회 이상 나타나는 단어만 고려합니다(실제로는 두 배로 늘리기 때문에 비스팸 메일에서 3회 나타나는 것으로도 충분합니다). 그리고 한 코퍼스에는 나타나지만 다른 코퍼스에는 나타나지 않는 단어에 어떤 확률을 할당할 것인가 하는 문제가 있습니다. 다시 시행착오를 통해 저는 .01과 .99를 선택했습니다. 여기에도 조정의 여지가 있을 수 있지만, 코퍼스가 커짐에 따라 그러한 조정은 어쨌든 자동으로 이루어질 것입니다.
특히 예리한 관찰자들은 제가 출현 횟수를 세기 위해 각 코퍼스를 하나의 긴 텍스트 스트림으로 간주하지만, 스팸 확률을 계산할 때 합쳐진 길이가 아닌 각 코퍼스의 이메일 수를 제수로 사용한다는 것을 알아차릴 것입니다. 이것은 오탐을 방지하기 위한 또 다른 약간의 편향을 추가합니다.
새 메일이 도착하면 토큰으로 스캔되고, 스팸 확률이 중립적인 .5에서 얼마나 떨어져 있는지로 흥미로움을 측정하는 가장 흥미로운 15개의 토큰이 메일이 스팸일 확률을 계산하는 데 사용됩니다. 만약 probs가 15개의 개별 확률 목록이라면, 결합된 확률은 다음과 같이 계산합니다: (let ((prod (apply #'* probs))) (/ prod (+ prod (apply #'* (mapcar #'(lambda (x) (- 1 x)) probs))))) 실제로 발생하는 한 가지 질문은 한 번도 본 적이 없는 단어, 즉 단어 확률 해시 테이블에 없는 단어에 어떤 확률을 할당할 것인가 하는 것입니다. 다시 시행착오를 통해 저는 .4가 좋은 숫자라는 것을 발견했습니다. 이전에 한 번도 본 적이 없는 단어라면 아마도 상당히 무고할 것입니다. 스팸 단어는 너무나 익숙한 경향이 있습니다.
이 알고리즘이 실제 이메일에 적용된 예시는 마지막 부록에 있습니다.
저는 위 알고리즘이 스팸일 확률이 .9를 초과하면 해당 메일을 스팸으로 처리합니다. 하지만 실제로는 이 임계값을 어디에 두든 크게 중요하지 않을 것입니다. 왜냐하면 중간 범위에 해당하는 확률은 거의 없기 때문입니다.
통계적 접근 방식의 큰 장점 중 하나는 그렇게 많은 스팸을 읽을 필요가 없다는 것입니다. 지난 6개월 동안 저는 말 그대로 수천 개의 스팸을 읽었는데, 정말 사기를 저하시키는 일이었습니다. 노버트 위너는 노예와 경쟁하면 노예가 된다고 말했는데, 스패머와 경쟁하는 것도 비슷하게 품위를 떨어뜨리는 일입니다. 개별 스팸 특징을 인식하려면 스패머의 마음속으로 들어가려고 노력해야 하는데, 솔직히 저는 스패머의 마음속에서 가능한 한 적은 시간을 보내고 싶습니다.
하지만 베이즈 접근 방식의 진정한 장점은 물론, 당신이 무엇을 측정하고 있는지 안다는 것입니다. 스팸어새신(SpamAssassin)과 같은 특징 인식 필터는 이메일에 스팸