Detecting Social Spam Campaigns on Twitter

Report
Detecting Social Spam
Campaigns on Twitter
Zi Chu & Haining Wang
The College of William & Mary
Indra Widjaja
Bell Laboratories, Alcatel-Lucent, USA
Presented by Yingjiu Li
Singapore Management University, Singapore
Outline
LOGO
1
Background
2
Measurement
3
Classification
4
Evaluation
5
Conclusion
2
Outline
LOGO
1
Background
2
Measurement
3
Classification
4
Evaluation
5
Conclusion
3
Background
LOGO
Twitter: micro-blogging & social networking
Tweet
Bob
Follower
Alice
Friend
4
Background
LOGO
 Popularity brings spam
- Spam definition: malicious / phishing / scam content or
URL
- Social spamming is more successful using social
relationship
Spam tweet <text, URL>
5
Background
LOGO
 Spam campaign
- Spammer runs multiple accounts to spread spam
tweets for a specific purpose (i.e. propagating a spam
site, selling goods)
Real case of adult pill campaign
with multiple accounts
6
Background
LOGO
 Detecting spam, 1st step in fighting spam
- Tweet level: spam words, spam URLs
- Account level: spam tweets, aggressive automation
- Campaign level: cluster related tweets/accounts into
campaigns, observe collective features (similar content,
posting behavior …)
 Efficiency
- Capture multiple spam accounts at one time
 Robustness
- Some spamming methods can’t be detected at
individual level
7
Related Work
LOGO
 Existing work relies on solo URL feature
- Group tweets into a campaign based on the shared URL.
If the URL is blacklisted, the campaign is classified as
spam.
 Disadvantages
- Blacklists have the lag effect (90% of clicks before
blacklisted)
- Blacklists can only cover part of spam URLs
- False positive (whole domain bit.ly is blacklisted, benign
webpage http://bit.ly/fg7Uy)
- False negative: the URL/website is benign, but the
campaign’s collective behavior is spamming
8
Background
LOGO
 A real spam campaign example of aggressive
duplication
 Twitter Spamming Rule: “posts duplicate content
over multiple accounts”
Account EldoYPISILONE
Nutz this music video, SO COOL ;)
http://on.fb.me/ht2wXJ?=mti0
Account MatthewVankomen
Amazing this music footage, you'll like ^^
http://on.fb.me/ht2wXJ?=nzky
Account KristaBauske2r
Amazing this music vid, Maybe u'll like it :^
http://on.fb.me/ht2wXJ?=mtcz
9
Contribution
LOGO
 Improve the existing work based on solo URL
detection
 Introduce new features
 Design an automatic detection system using
machine learning
10
Outline
LOGO
1
Background
2
Measurement
3
Classification
4
Evaluation
5
Conclusion
11
Data Collection
LOGO
 Twitter Streaming API - Spritzer
- Uniform sampling, 1% of real-time global tweets
 Dataset, 50 million tweets
- Feb. – Apr. 2011
- Only check tweets with URLs, 8 million
(assume tweets without URLs are non-spam)
12
Clustering Algorithm
LOGO
 URL redirection, tweet = <content, URL>
- original URL => final landing URL
http://ow.ly/5UbUS ==> ... ==>
http://www.people.com/people/.../020515101,00.html
 Cluster tweets with the same final URL into a
campaign
Campaign = <shared URL, tweet set, account set>

Campaign_1 <shared_URL_1, {tweet_1, tweet_2, tweet_3}, {account_1,
account_2}>

Campaign_2 <shared_URL_2, {tweet_4, tweet_5}, {account_1, account_3}>

Campaign_3 <shared_URL_3, {tweet_1, tweet_6}, {account_1, account_4}>
13
Ground Truth
LOGO
 Creation
- Blacklists: Google’s SafeBrowsing, PhishTank, URIBL,
SURBL, Spamhaus
(If URL is blacklisted, the campaign is labeled as spam)
- Manual check: content of tweets, accounts (i.e. tweets
posted by them outside the campaign)…
Violate Official Twitter Rules of Spam and Abuse?
 Ground truth set
- 580 legitimate campaigns
- 744 spam campaigns
14
Twitter Rules
LOGO
15
Data Analysis
LOGO
Master URL, http://biy.ly/5As4k3
Affiliate URL <==> spam account
Account_1, http://biy.ly/5As4k3?=xd56
Account_2, http://biy.ly/5As4k3?=f2kk
Master URL Diversity Ratio = unique_Master_URL_# / tweet_no
High ratio ==> account independence
Low ratio ==> account dependence
16
Data Analysis
LOGO
17
Data Analysis
LOGO
Burstiness - overall workload distribution of a campaign
18
Outline
LOGO
1
Background
2
Measurement
3
Classification
4
Evaluation
5
Conclusion
19
Classification
LOGO
 Automatic classification framework
 Binary-class classification
20
Feature Extractor
LOGO
 Tweet-level Features
- Tweet = <textual content, URL>
- Text contains spam words?
- URL is redirected?
- URL is blacklisted?
21
Feature Extractor
LOGO
 Account-level Features
Account = <tweets, friends/followers, account properties>
- Lifetime tweet count
- Account registration date
- Account protected? Verified?
- Friend_count, follower_count, ratio
- Account reputation = follower_count / (follower_count +
friend_count)
- Account taste = avg(account reputation of each of his
friend)
22
Feature Extractor
LOGO
 Campaign-level Features
- Campaign = ({tweets}, {accounts}, shared_URL)
- Account Diversity Ratio = account_no / tweet_no
- Entropy of inter-arrival timing
Lower: regular behavior ==> coordination
Higher: irregular behavior ==> independent participation
Corrected Conditional Entropy (CCE)
23
Feature Extractor
LOGO
- Content self-similarity
{Tweets} => sense clusters
Cluster_1)
this music video so cool,
amazing this music footage you'll like,
this music video hope u like
Cluster_2)
How to Consolidate Credit Card Debt
Consolidate Credit Cards Now to Become Debt Free Later
Three Effective Ways to Consolidate Credit Card Debt Without
Using Intermediaries
24
Feature Extractor
LOGO
- SenseClusters - cluster messages based on contextual
similarity
- Vector space model: text ==>vector
Msg_1, He visited Russia in 1996.
Msg_2, In 1996 he went to Russia.
…
Vocabulary = {in, he, Russia, to, visited, went, 1996, …}
Occurrence Matrix
word_1
word_2
word_3
…
word_N
Msg_1
weight
0
weight
0
0
Msg_2
0
weight
0
0
0
…
0
0
0
0
Weight, TF-IDF (Term Frequency – Inverse Document Frequency)
25
Feature Extractor
LOGO
- Latent Semantic Analysis, rank lowering
- 2nd-order similarity (1st-order similarity)
“Score” => a number that expresses the accomplishment of a
team in a game
“Goal” => a successful attempt at scoring
- Cosine similarity measure
-
cos0 = 1, same
-
cos90 = 0, orthogonal
-
cos_sim > threshold, the same sense cluster
26
Feature Extractor
LOGO
- {Tweets} => K sense clusters (on the fly)
Cluster
Size %
Similarity
1
10%
1
2
30%
0.9
3
60%
0.1
K
self _ sim ila rity _ sco re 

i 1
clu steri _ size
w1
* clu steri _ sim ila rity
K
w2
W 3
27
Decision Maker
LOGO
 Random Forest
- Ensemble classifier that consists of many decision trees
- Construction of each tree: calculate the best split based
on m (<< M) features in the training set
- Prediction of a new sample is pushed down the tree. It is
assigned with the label of the leaf node it ends up in
- Final decision – majority voting of all trees
28
Outline
LOGO
1
Background
2
Measurement
3
Classification
4
Evaluation
5
Conclusion
29
Evaluation
LOGO
Classifier
Accuracy %
FPR %
FNR %
Random Forest
94.5
4.1
6.6
DecisionTable
92.1
6.7
8.8
RandomTree
91.4
9.1
8.2
KStar
90.2
7.9
11.3
Bayes Net
88.8
9.6
12.4
SMO
85.2
11.2
17.6
SimpleLogistic
84.0
10.4
20.4
J48
82.8
15.2
18.8
 Weka
 Try each classifier with the ground truth set, 10-fold
cross-validation
 High Accuracy, Low FPR (legitimate => spam), Medium
FNR (spam => legitimate)
30
Evaluation
LOGO
- Evaluate importance for every feature with Decision
Tree
Only use one feature for classification each time
Feature
Accuracy %
FPR %
FNR %
Account Diversity Ratio
85.6
16.2
13.0
Timing Entropy
83.0
9.5
22.8
URL Blacklist
(Our Result)
82.3
(94.5)
3.2
(4.1)
29.0
(6.6)
Avg Account Reputation
78.5
25.6
18.3
Active Time
77.0
16.2
28.3
Affiliate URL No
76.7
9.6
34.0
Manual Device %
74.8
10.3
36.8
Tweet Total No
74.32
32.4
20.4
Content Self Similarity
72.3
33.7
23.0
Spam Word Ratio
70.5
25.8
32.4
31
Outline
LOGO
1
Background
2
Measurement
3
Classification
4
Evaluation
5
Conclusion
32
Conclusion
LOGO
 Large measurement on Twitter
 Formulation of new features
 Automatic classification system
 Overall accuracy 94.5%
33
Questions
LOGO
34
Click
to
edit
company
slogan
.

similar documents