The healthy development of the Internet largely depends on the online advertisement which provides the financial support to the Internet. Click fraud, however, poses serious threat to the Internet ecosystem. It not only brings harm to the advertisers, but also damages the mutual trust between advertiser and ad agency. Click fraud prediction is a typical big data application in that we normally need to identify the malicious clicks from massive click logs, therefore ecient detection methods in big data framework are much desired to combat this fraudulent behavior. In this paper, we propose a three-stage filtering system to attack click fraud. The serialized filters e↵ectively detect the malicious clicks with decreasing confidence that can satisfy both advertisers and content providers.
The fast development of the Internet depends not only on
the increase of rich content, but also on online
advertisement which provides the financial support to the Internet
ecosystem. Online advertising tends to benefit all involved
parties including content provider, advertiser, ad agency and
ad network. It requires the mutual trust among all parties.
This trust was at risk, however, by fraudulent clicks. Click
fraud (also called click spam, malicious click) is an action of
intentional clicking with the purpose of making undue profit,
or doing harm to competitors. Click fraud is becoming a
serious problem to the World Wide Web [
Ad agencies or networks often deploy die↵rent filters to
identify malicious clicks [
We use the precision as the measure of confidence in this paper. The reason to use precision, instead of other metrics such as recall or F-measure is because 1) precision focuses on singling out bad clicks while trying to minimize the possibility of predicting valid clicks as fraudulent ones; 2) it is well-known that the judgement of whether or not a click is a fraudulent one is very subjective in many cases. Too large recall can potentially classify large number of valid clicks as bad ones unless we have high quality classifiers which is hard to obtain, especially when human judgement is dicult.
In this paper, we propose a click fraud detecting architecture which organizes filters sequentially by decreasing confidence order. This architecture was applied to large scale advertising log obtained from an ad agency. Specifically, • we address the malicious click problem on the ad agency side. In addition to rule-based and supervised methods, we propose a clustering-based method to analyse the trac quality; • we design a click detecting mechanism in big data computation framework, i.e., Hadoop, to detect malicious clicks eciently by sequentially organizing three types of filters of di↵erent confidence level; • we carefully design and analyse important features, and verify our approach by evaluating the dissimilarity between predicted fraudulent clicks vs. valid clicks.
The rest of the paper is organized as follows. In Section 2, we introduce previous work related to click fraud detection. We present our detection architecture in Section 3. In Section 4, we comprehensively analyze the results of our approach by applying it to over one month real click log data from an ad agency, and conclude our paper in Section 5.
There are many participants play in online advertising ecosystem. Ad agency usually plays an match maker role between publishers and advertisers. Publishers own the website pages containing ad slots. Advertisers purpose their ad creativity to attract users to buy their products or to make other kinds of profit. Ad agency buys inventory from publishers and sells advertising trac to advertisers. Thus, for a reputed ad agency, it is responsible to filter these malicious clicks before charging.
Undoubtedly there are great e↵orts in the area of fraud
detection, including the click fraud problem, but most
solutions are not easily available. The report by Tuzhilin [
Another type of malicious click detection methods was
based on click stream analysis techniques which identified
patterns of fraudulent trac. Metwally et al. proposed
fraud detection solutions for data stream by combining
association rules and duplicate detection methods [
Supervised learning approach detects the malicious clicks
by training a classifier. Data collection is one of the most
important steps in this approach. Haddadi [
Bot-generated click trac is a big part of malicious clicks.
The state-of-the-art bot detection work mostly aimed at
clicks in search engine logs [
clicks trust users
Result Validation
Result Analysis & Ensemble
Stage 4: Validation and
Analysis
Blacklist Heavy Hitter Frequent
Click Feature
Extraction Malicious User
Prediction
Model Malicious Publishers Detection
Stage 1: Rulebased Filtering
Stage 2: Classificationbased Filtering Stage 3: Clusteringbased Filtering
Previous approaches to identify and understand malicious
clicks focused on one specific method, or one specific
problem. Researchers adopted click-through rate related
methods for web spam in search engine [
In order to accommodate di↵erent filtering methods with di↵erent confidence in predicting the fraudulent clicks, we argue that it is advantageous to take the approach of stagewise filtering architecture. The filters are sequentially connected such that the filter generating results with higher predicting confidence is put in the chain before the one with lower confidence. The intuition is that we need to identify most confident malicious clicks, and reduce the data size which need further processing, hence reduce the complexity of the problem. Furthermore, stage-wise structure o↵ers prediction results of di↵erent confidence, which enables the users to utilize the result with more flexibility.
The stage-wise filtering system architecture is illustrated in Figure 1. The major components are following 3 stages. 1) Rule-based filters at stage 1 to detect obvious invalid clicks with high confidence. They can identify two types of malicious clicks: heavy hitter and frequent clicker. 2) Classification-based filters at stage 2 to determine more complicated clicks with human judged training set. 3) The clustering-based filter at stage 3 to identify cheating groups from similar publisher websites. We use intra-cluster distance and query diversity to separate malicious groups. 0 0 0 rse 100 s U fro 00 be 500 m u N
To fight click fraud, generating blacklist in the filtering
system is the most reliable method. It is easy to compile
the blacklist for violating entities such as user agent(UA)
or IP address, but the coverage of a blacklist is limited.
Setting certain rules is ecient to exclude more malicious
clicks from entering accounting system. In this paper we
focus on setting rules for the heavy hitter and frequent click
problems [
Heavy hitter in click logs means, at a specific time interval, the click rate of a user is relatively higher than a threshold 1, while frequent click problem refers to the situation that user’s click appears in relatively more periods1 than a predefined threshold 2.
To obtain a reasonable filtering threshold, we note from Figure 2 that the number of clicks and periods follows the Zipfian distribution. We set the maximum number for normal user behavior as the lower value of the two: number of clicks in one interval and number of periods the user clicks. For better accuracy, we can also determine the threshold based on the p-quantile value on the entire log dataset. 3.3
Classification-based methods are widely used in fraud
detection or spam detection field [
It is obvious that results of supervised methods highly depend on the accuracy, coverage and labeling scheme of the labeled corpus. The classified malicious clicks are limited by the fraudulent types in training set. Hence, we develop our clustering-based method, which is based on our observation 1We use period to represent the window for counting in frequent clicks problem, in order to distinguish the interval of heavy hitter. Clicks of each user occur within the same period will be ignored. s r e s U frebo 00040 m u N that, for agency’s customers(advertisers), some of the suspicious ad trac from the same website shows high similarity. We try to group similar trac and analyze them as a group in order to detect abusive clicks from the publisher-side. This approach can also be applied to search engine trac, since the query diversity can be used to separate the suspicious groups from the search ad log. Considering the result confidence and filtering cost, this stage can be an optional choice for each advertiser. For valuable customers, this is an attractive feature, which di↵ers from previous work.
For clustering, We define the dissimilarity between two log entries x, y as:
X
f2 F ields
D(x, y) =
wf df (x, y)
(1)
where each log entry is represented by a vector of click
attributes as < user, IP, ref errer, U A, area, query >. F ields
is the feature set used in click attributes and df (x, y) is the
distance measure defined on each attribute f , normalized
between [
For attributes like refer URL and user agent, we care about the longest matching prefix, and the distance measure is defined as: durl(x, y) = 1
LCP (x, y) max(|x|, |y|) where LCP means the longest common prefix of two strings.
Even though network address translation (NAT) might allow many users behind a single IP address, the cheating groups always show strong similarity in IP address. To amplify the importance of the tail part in IP address, we take 32 bits IPv4 address as an example to define the distance. If LCB(longest common bits) 16, then dIP (x, y) = 1
LCB(x, y) total bits otherwise, the distance between two IP addresses is 1.
For other attributes such as area, we simply treat their dissimilarity as binary value (0 or 1). Furthermore, we can easily prove that D(x, y) is a metric, since it follows the properties: (1) D(x, y) = 0if f x = y, (2) D(x, y) 0, (3) D(x, y) = D(y, x), and (4) D(x, y) D(x, z) + D(z, y)(triangle inequality). Due to space limit, we skip the proof here.
After obtaining the dissimilarity matrix of a log set, we use k-medoids algorithm to produce the clustering in this stage. K-medoids is an adaptation of k-means algorithm. Rather than calculating the mean of the items for each cluster, which is not applicable in our situation, a representative item, or medoid, is chosen for each cluster. Medoids for each cluster are calculated to finding object i by minimizing (2) (3) (4) J˜ = X D(i, j)
j2 Ci where Ci is the cluster containing object i and D(i, j) is the dissimilarity function defined in equation 1. Since the algorithm simply looks up the dissimilarity matrix, it only needs to be calculated once in the beginning.
The next step is how to distinguish cheating groups from all clusters. Obviously, if one group agrees on most fields, it indicates this group of clicks come from a botnet using similar terminals and browsers or a real interested user with high probability. From the click statistics we can figure that, if the group size is reasonable, it is less possible to be an interested user. In other words, if the intra-cluster similarity of a group is lower, then the probability of the tracs in the group being malicious is higher. Moreover, the high similarity of the referrer in a suspicious group means the low trac quality of the publisher except search engine. In particular, we add the query diversity factor for search engine trac. We define the Scatter(SC) score of each group as: SC = intra distance ⇥ query diversity (5) where query diversity is defined as the ratio of distinct search phrases to total search phrases. The query diversity is set to 1 for non-search engine trac. By adding query diversity, we want to give more importance to the website trac groups, since it is more dicult to locate the root cause of problem in search engine groups. Thus, we use the intracluster distance times query diversity to measure the ads click Scatter-ness of groups. Finally, the groups with low SC score will be regarded as suspicious groups. Figure 3 shows the distribution of Scatter score across our test groups. A brief description is shown in Algorithm 1.
input : clicks on each advertiser output: groups of malicious clicks initialize dissimilarity matrix; while not at end of advertisers’ trac set do step 1: apply K-medoids using D(x, y) distance to get trac groups with similar features step 2: select suspicious groups with lower SC score end Algorithm 1: Major steps of getting cheating groups 3.5
The features extracted from data that work in web page spam domains may not work in ad log analysis. We inspect the click data and introduce several features specifically designed for classifiers to predict malicious clicks. Features are created by studying the labeled users’ activity patterns.
In order to define useful features, we need to analyze the di↵erence between normal and malicious click behaviors. Below, we discuss some of the features we identified to represent the user.
Number of clicked advertisers. This feature counts the number of distinct advertisers each user clicked. Malicious users show extreme patterns, for instance most have empty cookie and others have dense clicks on one advertiser. Click ratio on advertisers. This feature takes into account both the total clicks and the distinct clicked advertisers, defined as total clicks/total clicked advertisers. For each user, it represents the average clicks per advertiser. We observe that the trusted users show higher diversity by comparing their histograms.
We also define features that can be used to characterize the attribute of a user. For instance, a fraudulent user might carry out the malicious click behaviors from one device, but with many dynamically allocated IP addresses. Thus, we derive features from user agent, IP and cookie. Short cookies are more suspicious than normal cookies, same goes for user agent. Some details about these features are shown below. Click/IP ratio. This feature is defined as the total clicks for a user/total unique IP addresses the clicks come from. Variance of IP clicks. After counting the number of clicks from each IP address, we can calculate the variance of these clicks. It will be suspicious if one user launches clicks with consistent frequency from some IP addresses. Besides, we also use features such as the number of user agents, number of referrers, length of agent, length of cookie.
There are some other features derived from geographic or temporal attributes. For click timestamp, we divide a day into four six-hour periods: night(0:00 to 5:59), morning(6:00 to 11:59), afternoon(12:00 to 17:59) and evening(18:00-23:59). With the information available, the features below are also extracted: most frequent area, most frequent period, number of clicks in each period, mean/std deviation of clicks in periods and so on. We are not going to list out all the 17 features used in classification considering the space limit.
In this section we present the experimental results of the stage-wise filtering framework. 4.1
The data set used in the experiments is over one month click log we get from an ad agency company. It contains about 35 million records of ad clicks. The advertising log data normally contains attributes as user ID, click timestamp, user’s IP, cookie, query phrase (if the ad trac is from a search engine), user agent and referrer (url of the page where user clicked the ad link ).
To protect privacy, users who click the ads are assumed to be only temporarily identified by cookie. We assume that some user actions such as buying stu↵ or registering are benign. In this way, we extract non-fraudulent clicks from benign users for training. On the other hand, some malicious clicks were addressed using domain knowledge. Examples of malicious clicks are shown in Table 1. We notice that attack may come from similar IP addresses with fake user agent, fake referrer, or meaningless query phrase. Besides, the training data includes complete clicks of three advertisers that can be used to evaluate clustering performance. A brief description of dataset for training is shown in Table 2. 4.2
We run our stage-wise method on an 8-node Hadoop
cluster using Pig Latin [
In the first stage of our framework, the bound rules for click density and click frequency are determined using pquantile of the entire distribution. From our training data, we find there contains over 0.5% heavy hitters. There exists a certain percentage of noisy clicks in the log, 0.995 or similar (consider the distributions in Figure 1) can be chosen as value of p in our experiment for rule setting. The large click logs are filtered by passing through click counting, period counting, quantile calculating and filtering phases.
Next, the reduced dataset is passed to feature extraction modules as well as classifiers in the second stage. In our experiment, 17 features which have been discussed above are created. Then, we use training set in Table 2 to train classification models and compare the performance of the following classifiers: Na¨ıve Bayes, Decision Table, Bayes Net, REP Tree and Random Forest(10 trees, 5 random features each). The comparison results of 5-fold cross validation over training set are presented in Table 3. Since the labelled malicious are just partial of real malicious clicks, the relatively recall performance is less important than precision. The performance could be very good result of the simple labeling scheme, thus we need unsupervised methods.
Finally, three advertisers with die↵rent click size(100K, 10K, 1K) are chosen as the evaluation dataset in the clustering stage. We set equal weight for die↵rent features in experiment. According to Figure 3, we use 2.0 as the lower bound for the SC score of groups, which means the group is quite dense. The number of K in applying K-medoids are determined experimentally. 4.3
Figure 4 illustrates the result of our implementation of stage-wise approach applied on click log of one month.
From the daily result, we find that a high percentage of clicks follows the format http://search-engine.com/s?word with the same short UA. Further study suggests that these clicks are coming from bot-net which directly inject noise into our logs using fake referer, user agent and IP address. We also find four suspicious publisher groups, which generate high density clicks with similar IP addresses and user agents from their website. Moreover, part of the suspicious clicks were generated by download manager showing in UA.
Figure 4 shows that the percentage of malicious in first stage distributed evenly. We could reasonably assume that all the heavy hitters and frequent clicks are malicious, since the upper bounds were setting based on the propriety of distribution. Thus, the rule-based filter can be chosen as the basic filter with absolute high confidence to meet basic requirement of ad agency. For classification stage, we choose Random Forest as our model. This stage can discover stealthy clicks with suspicious patterns derived from domain knowledge-based labeling. However, for the limitation of supervised method, false positive is inevitable. Our aim is to get the classifier with maximum precision. As to the clustering stage, we evaluate the precision on three different advertisers’ click log. If the number of final result groups is n, precision metric in this case is: n P recision = 1 X |Ci \ L| n
|Ci| i where L is the cheating click set in result, and Ci is the total click set from each of the advertisers. Figure 5 shows our test results of clustering. Three advertisers’ dataset achieve different precision performance, which indicates that the confidence partially depends on the distribution of real click data. Therefore, we set the clustering-based filters in the last stage. Indeed, even this filter has a lower confidence, it Rule-based Classification-based
Clustering-based 3N0umber of Clusters 40 50 60 is important for ad agency to assess the trac quality from publishers by evaluating the malicious group.
It is worth pointing out that our framework built on the top of Hadoop platform achieved high eciency for processing click log. Due to the as-many-as computation in one-pass design, each stage could be finished in minutes for both daily and monthly filtering.
To further validate the stage-wise precision, we pick 4-day predicated malicious clicks for human judgement. We invite domain expert to inspect these clicks and the comparison results were shown in Figure 6. We see that the rule-based methods achieve high precision, which verifies our assumption. However, false positives are inevitable in any unsupervised learning algorithms. It is interesting that most of the false classified results are from mobile applications, especially on the 10th day. The missing of referrer field in these clicks is the root cause, which makes the patterns of these clicks similar to those of malicious clicks.
As a comparison, we check the diversity ratio on three features: hash of cookie, hash of user agent, hash of referrer, by sampling clicks from positive and negative results respectively. The diversity is defined as the ratio of distinct items to total samples. Figure 7 shows the result: diversities of normal clicks are relatively higher than these of malicious groups. For example, a group of intentional clicks with similar UA may come from one commander. The obvious die↵rence between the malicious groups and normal groups suggests that the identified ones are indeed very suspicious.
Fraudulent click is a malicious behavior which threatens the healthy development of Internet ecosystem. In this work, we propose a stage-wise click fraud filtering architecture which e↵ectively identifies the fraud clicks for ad agency with di↵erent prediction confidence. The stages in this work can be further divided into a set of modules, which consist of one or several rounds of Map/Reduce using parallel computing. We performed an in-depth analysis on one month click log using the proposed framework and evaluated our results by die↵rent metrics.
ACKNOWLEDGMENTS 1.0 0.8 n io0.6 s i c re0.4 P 0.2 0.0 20 100 cookie Fields referrer
Normal Malicious in stage 2 Malicious in stage 3
This work is partially supported by the Key Program of National Natural Science Foundation of China grant No. 61232002, National Science Foundation of China under grant No.60925008, No.61103039, No.61021004 and the Key lab Project of Wuhan University. 7.