Spamszűrő rendszerek. BODÓ Zalán. Spamszűrő rendszerek. BODÓ Zalán () A spam. Osztályozás. A spam eredete. A spam szó eredete

Spamszűrő rendszerek BODÓ Zalán A spam Osztályozás A spam eredete A „spam” szó eredete Az első spam(ek) Spamszűrők

Spamszűrő rendszerek

Miért nehéz a feladat? A kezdet Primitív nyelvi analízis Feketelisták, fehérlisták

BODÓ Zalán

Heurisztikus szűrés Challenge/response (C/R) Fojtogatás (throttling) Kollaboratív szűrés

Gépi tanulás alapú spamszűrés Naiv Bayes

BODÓ Zalán ()


1 / 23

A spam Spamszűrő rendszerek BODÓ Zalán A spam Osztályozás

Definíció UBE = Unsolicited Bulk Email (kéretlen és tömeges levél)

A spam eredete

legtöbbször: kéretlen levél (’unwanted email’)

A „spam” szó eredete Az első spam(ek)

Változatai:

Spamszűrők

Chat spam és SPIM

Miért nehéz a feladat?

Email spam – klasszikus; általában ezt értjük alatta

A kezdet

Fórum spam

Primitív nyelvi analízis Feketelisták, fehérlisták

Hírcsoport spam

Heurisztikus szűrés Challenge/response (C/R)

On-line játék spam

Fojtogatás (throttling)

Spamdexing

Kollaboratív szűrés

Gépi tanulás alapú spamszűrés

stb.

Naiv Bayes

BODÓ Zalán ()


2 / 23

Néhány statisztika Spamszűrő rendszerek BODÓ Zalán A spam Osztályozás A spam eredete A „spam” szó eredete Az első spam(ek)

Spam/ham arányok

Spamszűrők

Spamtípusok

Miért nehéz a feladat? A kezdet Primitív nyelvi analízis Feketelisták, fehérlisták Heurisztikus szűrés Challenge/response (C/R) Fojtogatás (throttling) Kollaboratív szűrés


Legnagyobb spamküldő országok

Naiv Bayes

BODÓ Zalán ()


3 / 23

A spamszűrők osztályozása Spamszűrő rendszerek BODÓ Zalán A spam Osztályozás

Szűrés típusa szerint származás alapú szűrés

A spam eredete A „spam” szó eredete

hálózati forgalom alapú szűrés

Az első spam(ek)

tartalom alapú szűrés

Spamszűrők Miért nehéz a feladat?

Szűrés helye szerint routerek szintjén történő szűrés

A kezdet Primitív nyelvi analízis

levelezőszerver szintjén történő szűrés

Feketelisták, fehérlisták Heurisztikus szűrés

felhasználói oldalon történő szűrés

Challenge/response (C/R) Fojtogatás (throttling) Kollaboratív szűrés


BODÓ Zalán ()


4 / 23

A spam eredete Spamszűrő rendszerek MontySpam-780577 (519x308x16M jpeg)

BODÓ Zalán A spam Osztályozás A spam eredete A „spam” szó eredete Az első spam(ek) Spamszűrők Miért nehéz a feladat?

Monty Python Flying Circus: Spam (1970) – Spam sketch; Spam song – kb. 132-szer fordul elő benne a „spam” kifejezés

A kezdet Primitív nyelvi analízis

MUD (MultiUser Dungeon) típusú játékokból (szöveges akciójáték; szerepjáték + hack and slash + chat szobák) – a MUD szerver vagy játékosok gépének túlterhelése sok szöveg elküldése által

Feketelisták, fehérlisták Heurisztikus szűrés Challenge/response (C/R) Fojtogatás (throttling) Kollaboratív szűrés

löncshúsnak (konzervhús) a ventillátorba dobása által erdményezett „felfordulás” (kellemetlen érzés/szag/stb.) – eléggé elborult. . . :)


BODÓ Zalán ()


5 / 23

A „spam” szó eredete Spamszűrő rendszerek BODÓ Zalán A spam Osztályozás A spam eredete A „spam” szó eredete Az első spam(ek)

jelentése löncshús/konzervhús Hormel Foods Corporation, Austin, Minnesota, USA (= Spam Town) a név megjelenése: 1937. július 5; előtte „Hormel Spiced Ham”-nek hívták ugyanazt a konzervet – ezt 1930-ban vezették be (a II. világháborúban terjedt el igazán) egy másik lehetséges eredet: Shoulder of Pork and Ham, Spiced Pork And Ham vicces eredetek (backronyms): Something Posing As Meat, Special Purpose Army Meat

Spamszűrők Miért nehéz a feladat? A kezdet Primitív nyelvi analízis Feketelisták, fehérlisták Heurisztikus szűrés Challenge/response (C/R) Fojtogatás (throttling) Kollaboratív szűrés


BODÓ Zalán ()


6 / 23

Az első spam(ek) Spamszűrő rendszerek BODÓ Zalán

szerző: Gary Thuerk, DEC (Digital Equipment Corporation)

A spam

téma: a DEC-20 mainframe (nagygép) megjelenése, meghívó a termékbemutatóra

Osztályozás A spam eredete A „spam” szó eredete

kb. 320 személy kapta meg (Arpanet hálózat) eredmény: nagy felháborodás ← ez is jócskán leterhelte a hálózatot (max. sávszélesség 56 Kbps)

Az első spam(ek) Spamszűrők Miért nehéz a feladat? A kezdet Primitív nyelvi analízis Feketelisták, fehérlisták Heurisztikus szűrés Challenge/response (C/R) Fojtogatás (throttling) Kollaboratív szűrés


BODÓ Zalán ()


7 / 23

Spamszűrő rendszerek BODÓ Zalán A spam Osztályozás A spam eredete A „spam” szó eredete Az első spam(ek) Spamszűrők Miért nehéz a feladat? A kezdet Primitív nyelvi analízis Feketelisták, fehérlisták Heurisztikus szűrés Challenge/response (C/R) Fojtogatás (throttling) Kollaboratív szűrés


Mail-from: DEC-MARLBORO rcvd at 3-May-78 0955-PDT Date: 1 May 1978 1233-EDT From: THUERK at DEC-MARLBORO Subject: ADRIAN@SRI-KL DIGITAL WILL BE GIVING A PRODUCT PRESENTATION OF THE NEWEST MEMBERS OF THE DECSYSTEM-20 FAMILY; THE DECSYSTEM-2020, 2020T, 2060, AND 2060T. THE DECSYSTEM-20 FAMILY OF COMPUTERS HAS EVOLVED FROM THE TENEX OPERATING SYSTEM AND THE DECSYSTEM-10 COMPUTER ARCHITECTURE. BOTH THE DECSYSTEM-2060T AND 2020T OFFER FULL ARPANET SUPPORT UNDER THE TOPS-20 OPERATING SYSTEM. THE DECSYSTEM-2060 IS AN UPWARD EXTENSION OF THE CURRENT DECSYSTEM 2040 AND 2050 FAMILY. THE DECSYSTEM-2020 IS A NEW LOW END MEMBER OF THE DECSYSTEM- 20 FAMILY AND FULLY SOFTWARE COMPATIBLE WITH ALL OF THE OTHER DECSYSTEM-20 MODELS. WE INVITE YOU TO COME SEE THE 2020 AND HEAR ABOUT THE DECSYSTEM-20 FAMILY AT THE TWO PRODUCT PRESENTATIONS WE WILL BE GIVING IN CALIFORNIA THIS MONTH. THE LOCATIONS WILL BE: TUESDAY, MAY 9, 1978 - 2 PM HYATT HOUSE (NEAR THE L.A. AIRPORT) LOS ANGELES, CA THURSDAY, MAY 11, 1978 - 2 PM DUNFEY'S ROYAL COACH BODÓ Zalán ()


7 / 23

SAN MATEO, CA (4 MILES SOUTH OF S.F. AIRPORT AT BAYSHORE, RT 101 AND RT 92)

Spamszűrő rendszerek BODÓ Zalán A spam Osztályozás A spam eredete

A 2020 WILL BE THERE FOR YOU TO VIEW. ALSO TERMINALS ON-LINE TO OTHER DECSYSTEM-20 SYSTEMS THROUGH THE ARPANET. IF YOU ARE UNABLE TO ATTEND, PLEASE FEEL FREE TO CONTACT THE NEAREST DEC OFFICE FOR MORE INFORMATION ABOUT THE EXCITING DECSYSTEM-20 FAMILY

A „spam” szó eredete Az első spam(ek) Spamszűrők Miért nehéz a feladat? A kezdet Primitív nyelvi analízis Feketelisták, fehérlisták Heurisztikus szűrés Challenge/response (C/R) Fojtogatás (throttling) Kollaboratív szűrés


BODÓ Zalán ()


8 / 23


Lánclevelek – első: 1982. február „küldd tovább és nagy szerencse ér[, ha nem küldöd, akkor szerencsétlenség]” típusú levelek Jay-Jay’s College Fund – 1988

A „spam” szó eredete

„kunyeráló levél”; 1 dollár adakozás a tanulmányok befejezéséhez egy megadott számlaszámra/alapba

Az első spam(ek) Spamszűrők Miért nehéz a feladat? A kezdet Primitív nyelvi analízis

Jézus-spam – 1994 „Jesus is coming” típusú vallásos „világvége”-levél Canter & Siegel – 1994

Feketelisták, fehérlisták

első kereskedelmi célú spam

Heurisztikus szűrés Challenge/response (C/R)

zöldkártya sorsjáték (Green Card Lottery) nem volt kifejezetten kereskedelmi célú, csak annak beharangozója

Fojtogatás (throttling) Kollaboratív szűrés


...

Naiv Bayes

BODÓ Zalán ()


8 / 23

Spamszűrő rendszerek Spamszűrő rendszerek

dokumentumok (levelek): D = {d1 , . . . , dN }

BODÓ Zalán

osztályok (címkék): C = {spam, ham}

A spam Osztályozás A spam eredete A „spam” szó eredete Az első spam(ek) Spamszűrők Miért nehéz a feladat?

Feladat Osztályozási feladat: b f : D × C → {T , F }, ami legjobban megközelíti az (ismeretlen) f függvényt; f tanulási példák által adott: D = {(di , ci )|di ∈ D , ci ∈ C, i = 1, 2, . . . , N } spamham (1200x287x16M jpeg)

A kezdet Primitív nyelvi analízis Feketelisták, fehérlisták Heurisztikus szűrés Challenge/response (C/R) Fojtogatás (throttling) Kollaboratív szűrés


BODÓ Zalán ()


9 / 23

Spamszűrő rendszerek BODÓ Zalán

Kiértékelés Kontingencia-táblázat

i.

A spam Osztályozás A spam eredete A „spam” szó eredete

osztály

Megjósolt hozzátartozás

Valódi hozzátartozás IGAZ HAMIS

IPi HNi

IGAZ HAMIS

Az első spam(ek)

HPi INi

HP +HN Erri = IP +HP +HN +IN IP +IN pontosság (accuracy): Acci = IP +HP +HN +IN precision: Pi = IP IP +HP IP recall: Ri = IP + HN P/R kiegyenlítési pont (breakeven point): P ≈ R F -mérték

Spamszűrők

hiba (error):


i

i

i

i

i

i

i

A kezdet

i

Primitív nyelvi analízis

i

i

i

i

i

Feketelisták, fehérlisták

i

Heurisztikus szűrés

i

i

Challenge/response (C/R)

i



i

ROC-görbe, ROC-AUC stb.

Naiv Bayes

BODÓ Zalán ()


10 / 23

Miért nehéz a feladat? Spamszűrő rendszerek

csak szövegek (képek – más kategória: OCR, stb.)

BODÓ Zalán

meg kellene értenünk a szöveget (?)

A spam Osztályozás

(szintaktika és szemantika nem szétválasztható) példák:


PL1: „John saw the man in the park with the telescope.” PL2: „I saw the Statue of Liberty flying over New York.” PL3: „Visiting aunts can be a nuisance.” PL4: „James while John had had had had had had had had had had had a better effect on the teacher.” (James, while John had had "had", had had "had had"; "had had" had had a better effect on the teacher.) PL5: „Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo.” ([Those] Buffalo buffalo [whom] Buffalo buffalo buffalo, buffalo Buffalo buffalo.) PL6: „We saw her duck.”



BODÓ Zalán ()


11 / 23

Kezdetleges spamszűrő rendszerek Spamszűrő rendszerek BODÓ Zalán A spam Osztályozás A spam eredete A „spam” szó eredete Az első spam(ek) Spamszűrők Miért nehéz a feladat? A kezdet Primitív nyelvi analízis

Primitív nyelvi analízis (Primitive Language Analysis, PLA) működése: (a) ismert spamküldők ellenőrzése; (b) adott szavak/kifejezések ellenőrzése a subject-ben és a szövegtestben, pl. „Call now!”, „Free trial!”, stb. előny: egyszerű implementálni; hátrány: túl sok hamis pozitív Feketelisták, fehérlisták . . . Heurisztikus szűrés kézzel alkotott szabályok szerinti szűrés Pl.

Feketelisták, fehérlisták Heurisztikus szűrés

[(try ∈ subj) ∨ (new ∈ subj)] ∧ [(free ∈ body) ∨ (viagra ∈ body)]

Challenge/response (C/R) Fojtogatás (throttling)

→ spam



(try ∈ body)∧(now ∈ body)∧(|pos (try)−pos (now)| ≤ 5) → spam

Naiv Bayes

BODÓ Zalán ()


12 / 23



A spam

A spam eredete

ha egy ismeretlentől kapunk levelet, megkérjük, hogy „azonosítsa” magát


Pl.

Osztályozás

Subject: Re: Hi There! Greetings, You just sent an email to my spam-free email service. Because this is the first time you have sent to this email account, please confirm yourself so you’ll be recognized when you send to me in the future. It’s easy. To prove your message comes from a human and not a computer, click on the link below: http://[Some Web Link] Attached is your original message that is in my pending folder, waiting for your quick authentication.



BODÓ Zalán ()


13 / 23

Spamszűrő rendszerek BODÓ Zalán A spam

Fojtogatás (throttling) hálózati védelem

Osztályozás A spam eredete

korlátozza az ugyanazon hálózatról érkező adatok (levelek) mennyiségét


le tudja terhelni a spam küldőjét, mivel mindig visszaküldi neki, hogy küldje újra

Az első spam(ek) Spamszűrők Miért nehéz a feladat?


A kezdet

azonos spamszűrőt használó felhasználók közötti automatikus együttműködés

Primitív nyelvi analízis Feketelisták, fehérlisták Heurisztikus szűrés

ha valaki „új” spamet kap, megosztja a többivel az abból nyert információt



BODÓ Zalán ()


14 / 23

Gépi tanulás alapú spamszűrés Spamszűrő rendszerek BODÓ Zalán A spam Osztályozás A spam eredete A „spam” szó eredete

tartalom alapú, a felhasználói oldalon szövegkategorizáláson (Text Categorization, TC) alapuló szűrés egyszerűsített feladat: csak 2 osztály van (spam, ham) szükséges egy reprezentáció + egy tanuló algoritmus 2 lépés: feature-ök kiválasztása + tanulás A bag-of-words reprezentációs modell

Az első spam(ek)



vektortér-modell; dimenziók = szavak (termek, feature-ök) száma Pl.: szavak = {music, sport, science} d = (3, 0, 1)

sport

Spamszűrők

science

music

Naiv Bayes

BODÓ Zalán ()


15 / 23


normalizálás: kd k = 1


→

d = d /kd k

dokumentumok összehasonlítása lineáris modellekben: sim(d 1 , d 2 ) = cos(d 1 , d 2 ) = d 10 d 2


[szótövesítés (stemming) – bizonyos esetekben hasznosnak bizonyul]



BODÓ Zalán ()


16 / 23


Feature-kiválasztás A spam

sokféle lehetőség, megközelítés

Osztályozás

legöbbet használt módszerek: szűrők; pl. DFT, DIA, IG, MI, χ 2 , . . . legegyszerűbb módszer: DFT (Document Frequency Thresholding)


termek növekvő sorrendbe való rendezése a dokumentumokban való megjelenési szám szerint vágjuk a lista két végét


[sokszor használjuk: stop-szavak kiszűrése]

A kezdet Primitív nyelvi analízis Feketelisták, fehérlisták

Tanulás


egy gyors és „jó” tanuló algoritmus


legtöbbet használt: naiv Bayes, kNN, SVM, LLSF,. . .



BODÓ Zalán ()


17 / 23


Spamszűrő felépítése

A spam Osztályozás

Korpusz (tanulási adatok)

A spam eredete

Tokenizáló

A „spam” szó eredete Az első spam(ek)

Új email

Spamszűrők

Preprocesszor

Feature‐ök kiválasztása

Teszt (döntés / szűrés)

Tanulás



BODÓ Zalán ()


18 / 23

Naiv Bayes Spamszűrő rendszerek

poszterior valószínűségek kiszámítása Bayes-képlet: p(d |ci ) · p(ci ) p(ci |d ) = p (d ) vagy p(d |c ) · p(ci ) p(ci |d ) = PK i i =1 p (d |ci ) · p (ci ) „naivitás”: feltételezzük, hogy a szavak függetlenek egymástól (a kategóriákra nézve):

BODÓ Zalán A spam Osztályozás A spam eredete A „spam” szó eredete Az első spam(ek) Spamszűrők Miért nehéz a feladat? A kezdet

p(d |ci ) =

Primitív nyelvi analízis Feketelisták, fehérlisták Heurisztikus szűrés Challenge/response (C/R)

W Y

j

j =1

Fojtogatás (throttling)

p(ci |d ) ∝ p(ci ) ·



p(tj |ci )freq(d ,t ) W Y

p(tj |ci )freq(d ,t ) j

j =1

ahonnan BODÓ Zalán ()


19 / 23


c (d ) =

BODÓ Zalán A spam

argmax log p (ci ) +

i ∈{1,2,...,K }

Osztályozás

W X

log p (tj |ci )freq(d ,t ) j

j =1


becslések:


|c | p(ci ) = i ; N

freq (ci , tj ) p(tj |ci ) = Pn j =1 freq (ci , tj ) sok esetben, az adatok ritkasága miatt p (tj |ci ) = 0

probléma: megoldás: „simítás”

A kezdet Primitív nyelvi analízis Feketelisták, fehérlisták

W X freq (ci , tj ) + aj , a =a freq (ci , t1,2,...,n ) + a j =1 j freq (ci , tj ) + 1 pL (tj |ci ) = freq (ci , t1,2,...,n ) + W


p(tj |ci ) =



BODÓ Zalán ()


20 / 23

Példa Spamszűrő rendszerek

P (spam|d ) madam 0.99 promotion 0.99 republic 0.99 shortest 0.047225013 mandatory 0.047225013 standardization 0.07347802 sorry 0.08221981 supported 0.09019077 people’s 0.09019077 enter 0.9075001 quality 0.8921298 organization 0.12454646 investment 0.8568143 very 0.14758544 valuable 0.82347786

BODÓ Zalán A spam Osztályozás A spam eredete A „spam” szó eredete Az első spam(ek) Spamszűrők Miért nehéz a feladat? A kezdet Primitív nyelvi analízis Feketelisták, fehérlisták Heurisztikus szűrés Challenge/response (C/R) Fojtogatás (throttling) Kollaboratív szűrés


BODÓ Zalán ()


21 / 23

Támadások Spamszűrő rendszerek BODÓ Zalán A spam Osztályozás A spam eredete A „spam” szó eredete

tokenizálási támadás (tokenization attack)

Az első spam(ek)

összezavarás (obfuscation)

Spamszűrők

gyenge statisztikai támadás (weak statistical attack)


erős statisztikai támadás (strong statistical attack)



BODÓ Zalán ()


22 / 23

Spamszűrő rendszerek BODÓ Zalán A spam Osztályozás A spam eredete A „spam” szó eredete

Köszönöm a figyelmet!



BODÓ Zalán ()


23 / 23

Spamszűrő rendszerek. BODÓ Zalán. Spamszűrő rendszerek. BODÓ Zalán () A spam. Osztályozás. A spam eredete. A spam szó eredete

Recommend Documents