기계 학습 기법을 이용한 스팸 메일 걸러내기

기계학습기법으로스팸메일걸러내기 소프트웨어무결점연구 (ROSAEC) 센터제 5 회워크샵 튜토리얼 2011 년 1 월 8 일 곽남주 1

차례 스팸의어원 왜스팸메일을보내는가? 스팸메일에당한사례 스팸방지를위한노력 기계학습을활용한스팸걸러내기 베이지안스팸거름법 (Bayesian Spam Filtering) 복수단어인식단위로의확장 (Multiple-Word Feature) 마르코비안거름법 (Markovian Filtering) 은닉마르코프모형과난독화문제해법 (Deobfuscation with Hidden Markov Model) 정리 질의응답 참고자료및참고문헌 2

스팸의어원 1970 년대, 영국의코미디프로그램 스팸 이라는말을불필요하게반복적으로함으로써웃음을유발 초기인터넷사용자들사이, 온라인게시판이나토론장을스팸이라는말로도배하는장난이유행 1980 년대 머드 (multi-user-dungeon) 게임에서도성행 Usenet 과개인이메일사용자, 지나친광고글을게시하는일을 스패밍 한다고부르기시작 영국코미디 Monty Python Sketches World of Warcraft 대화창스패밍 3

왜스팸메일을보내는가? 통계수치에따르면 12,500,000 통의상품판매목적스팸메일을보내면, 한건정도는매출로이어진다고함 (2010 년 3 월자료 ). McAfee 에의하면, 미국인의절반이매일이메일을사용하고, 그중절반이귀가얇아잘속는경향이있고, 그중 1% 가구매를시도하다신용사기의희생양이되어, $20 씩을지불해야한다면, 잠재적시장규모가미국내에서만일간 1500 만달러, 주간 1 억 500 만달러, 연간 55 조달러에이름. 4

스팸메일에당한사례 Shtyle.fm 뭔가페이스북같은곳일까? 5

스팸메일에당한사례 Shtyle.fm 아주간단한비밀번호도통과되고세부정보는제공하지않아도가입이가능단, 아이디는이메일주소 가입기념으로친구에게선물을줄수있다고하면서, 가입시사용했던이메일주소의비밀번호를요구함 6

스팸메일에당한사례 Shtyle.fm 친구에게선물을줘야지! Shtyle.fm 데이터베이스 PW: ABC ID: somebody@somewhere.some PW: 123 PW: ABC Shtyle.fm 사이트 송신 : 나수신 : 내주소록친구들 가입자의이메일계정주소록을조회해서, 발신자는가입자의이메일주소, 수신자는주소록에서얻어진이메일주소들로하여자사홍보메일을보낸다. 7

스팸방지를위한노력 사용자입장 이메일주소는지인들에게만공개 주소일그러뜨리기 (personnos@pamdomain.com) 스팸에반응보이지않기 더이상스팸보내지마세요! 라고반응하는것은 당신이스팸보낸주소는실제로존재하는주소입니다. 감사합니다. 라고하는것과같다. 외부용주소를사용하고, 실제사용은전달 (forward) 받아서하기 응징및복수 ( 발신자추적해스팸더보내기, 발신자컴퓨터찾아서괴롭히기, 스팸광고하는사이트가서악성게시물올리기 ) 8

스팸방지를위한노력 이메일관리자입장 스팸발신자가없다고검증된이메일서버만취급 발신때마다스팸발신이아닌지검사 (Captcha 등 ) 스팸메일의검사합계 (checksum) 를수집하여, 걸러내기 RFC 표준준수여부확인 ( 스팸메일은보통표준을염두에두지않음 ) 스팸메일덫설치후걸린발신자차단 기계학습및통계적방법으로걸러내기 9

기계학습을활용한스팸걸러내기 베이지안스팸거름법 복수단어인식단위로의확장 마르코비안거름법 10

베이지안스팸거름법 (Bayesian Spam Filtering) 11

베이지안스팸거름법 (Bayesian Spam Filtering) 12

베이지안스팸거름법 (Bayesian Spam Filtering) 13

베이지안스팸거름법 (Bayesian Spam Filtering) 14

베이지안스팸거름법 (Bayesian Spam Filtering) 15

베이지안스팸거름법 (Bayesian Spam Filtering) 16

복수단어인식단위로의확장 (Multiple-Word Feature) 베이지안스팸거름법은단어들의이웃함을고려하지않는다. 대출한도 와 대출 한도 의차이 최대 k 개의단어순서열을인식의단위로간주하면어떨까? 크기 k 인창을움직이면서, 창의첫단어를반드시포함하되, 다른단어들은생략가능하며, 단, 그단어들의순서가유지되어야한다. k=3 이라고할때의생성되는일부인식단위들의예 빠르게알아보는나의대출한도조회기록 빠르게 알아보는 나의 사용 사용 사용 빠르게알아보는나의 사용 사용 빠르게알아보는 사용 사용 빠르게나의 알아보는 나의 대출한도 사용 사용 사용 알아보는나의대출한도 사용 사용 알아보는나의 사용 사용 알아보는대출한도 사용 빠르게 사용 알아보는 17

복수단어인식단위로의확장 (Multiple-Word Feature) 빠르게알아보는나의 알아보는나의대출한도 나의대출한도조회 대출한도조회기록 빠르게알아보는 알아보는나의 나의대출한도 대출한도조회 빠르게나의 알아보는대출한도 나의조회 대출한도기록 빠르게 알아보는 나의 대출한도 18

마르코비안거름법 (Markovian Filtering) 스팸메일에포함된 k 개의단어들을순서와이웃함을유지한채포함하고있는경우가많을수록스팸일가능성이높지않을까? 당일바로대출 5000 과 당일바로 의차이 인식단위의길이에지수적으로증가하는가중치를부여 k=5 이라고할때의, 각인식단위에주어지는가중치의예 당일바로대출최대 5000 당일바로대출최대 5000 256 당일바로 5000 16 당일대출최대 5000 64 당일바로최대 16 당일바로최대 5000 64 당일바로대출 16 당일바로대출 5000 64 당일 5000 4 당일바로대출최대 64 당일최대 4 당일최대 5000 16 당일대출 4 당일대출 5000 16 당일바로 4 당일대출최대 16 당일 1 19

마르코비안거름법 (Markovian Filtering) 20

Honglak Lee and Adrew Y. Ng, Spam deobfuscation using a hidden Markov model, Conf. on Email and Anti-Spam, 2005. 은닉마르코프모형과난독화문제해법 (Deobfuscation with Hidden Markov Model) 난독화문제 (obfuscation) 기존단어 refinance mortgage viagra unsubscribe 난독화단어 r.efina.nce, r-efin-ance, re xe finance mort gage, mo>rtglage, mor;tg2age v*1agra, v-i-a-g-r-a, v1@gra, vjaggra u.n sabcjbe, un susc ribe 은닉마르코프모형 (Hidden Markov Model, HMM) 21

Honglak Lee and Adrew Y. Ng, Spam deobfuscation using a hidden Markov model, Conf. on Email and Anti-Spam, 2005. 은닉마르코프모형과난독화문제해법 (Deobfuscation with Hidden Markov Model) 22

Honglak Lee and Adrew Y. Ng, Spam deobfuscation using a hidden Markov model, Conf. on Email and Anti-Spam, 2005. 은닉마르코프모형과난독화문제해법 (Deobfuscation with Hidden Markov Model) 초기상태확률벡터, 상태이전확률행렬, 관찰발생확률벡터의정의 자가이전제어인자 (S 0 X) 를접두어로갖는단어의총빈도수 단어 (S 0 X) 의총빈도수 Q 는이전하면서공백문자를생성할확률, P 는이전하면서비공백문자를생성할확률 모형자체의또다른인자 공백문자이전제어인자 훈련데이터 (training data) 의로그가능성 (likelihood) 를최대화하도록 η, ε, τ 를학습한다. 난독화를위해삽입되는무의미한문자의확률분포 상태가나타내는문자를나타내기위한관찰된문자의확률분포 23

Honglak Lee and Adrew Y. Ng, Spam deobfuscation using a hidden Markov model, Conf. on Email and Anti-Spam, 2005. 은닉마르코프모형과난독화문제해법 (Deobfuscation with Hidden Markov Model) 학습된모형에난독화된단어를입력으로넣고비터비알고리즘을수행하면, 가장가능성이높은상태의순서열이얻어지고, 이것이바로비난독화가적용된단어이다. v1@gra viagra v i a g r a 상태전이확률행렬의희소 (sparse) 표현을적용하고, Jelinek 의 1999 년저서에서소개된방법 (beam search) 을사용하면, 알고리즘을더욱빠르게할수있다. F. Jelinek, Statistical Methods for Speech Recognition. MIT Press, 1999. 24

정리 베이지안거름법 : 단어의이웃관계를무시하고단어의출현이독립적인사건이라는가정하에, 메일에등장하는각단어의스팸성을구해종합함으로써스팸메일일확률을추정한다. 복수단어인식단위로의확장 : 단어의이웃관계를제한적으로감안하고단어의출현의종속성을다소반영한인식단위를이용하여, 스팸메일일확률을추정한다. 마르코비안거름법 : 단어의이웃관계및출현의종속성이잘반영된인식단위일수록높은가중치를제공하여, 스팸메일일확률을추정한다. 은닉마르코프모형과난독화문제 : 은닉마르코프모형을이용하여난독화된단어를원래단어로해독하고, 이를바탕으로거름법을수행하면더좋은결과를기대할수있을것이다. 25

질의응답 26

참고자료및참고문헌 참고자료및참고문헌 Wikipedia - Spam (Monty Python) (http://en.wikipedia.org/wiki/spam_(monty_python)) Spam Experts (http://www.spamexperts.com/spam-experts/news-archive/article/motivation-forspammers.html) Consumer Fraud Reporting (http://www.consumerfraudreporting.org/spam_costs.php) Wikipedia - Bayesian spam filtering (http://en.wikipedia.org/wiki/bayesian_spam_filtering) Ben O connor, Markovian Spam Filtering, 2007. Gary Robinson's Rants (http://radio-weblogs.com/0101454/stories/2002/09/16/spamdetection.html) Jonathan A. Zdziarski, Ending Spam: Bayesian Content Filtering and the Art of Statistical Language Classification, No Starch Press, 2005. Raju Shrestha and Yaping Lin, Improved Bayesian Spam Filtering Based on Co-weighted Multi-area Information, Advances in Knowledge Discovery and Data Mining, 2005. William S. Yerazunis, Sparse Binary Polynomial Hashing and the CRM114 Discriminator (slides) Shalendra Chhabra, William S. Yerazunis, and Christian Siefkes, Spam Filtering using a Markov Random Field Model with Variable Weighting Schemas, ICDM 04, 2004. William S. Yerazunis, The Spam-Filtering Accuracy Plateau at 99.9 percent Accuracy and How to Get Past It, MIT Spam Conference, 2004 William S. Yerazunis, et al., A Unified Model of Spam Filtration, MIT Spam Conference, 2005. Honglak Lee and Adrew Y. Ng, Spam deobfuscation using a hidden Markov model, Conference on Email and Anti-Spam, 2005. Seunghak Lee, Iryoung Jeong, and Seungjin Choi, Dynamically Weighted Hidden Markov Model for Spam Deobfuscation, Proceedings of the 20th International Joint Conference on Artificial Intelligence, 2007. 27