Malicious bots make up about a quarter of all trafic on the web and degrade the performance of personalization and recommendation algorithms that operate on e-commerce websites. Positive-Unlabeled learning (PU learning) provides the ability to train a binary classifier using only positive (P) and unlabeled (U) instances. The unlabeled data comprises both positive and negative classes. It is possible to find labels for strict subsets of non-malicious actors, e.g., the assumption that only humans purchase during web sessions, or clear CAPTCHAs. However, finding signals of malicious behavior is almost impossible due to the ever-evolving and adversarial nature of bots. Such a set-up naturally lends itself to PU learning. Unfortunately, standard PU learning approaches assume that the labeled set of positives are a random sample of all positives, this is unlikely to hold in practice. In this work, we propose two modifications to PU learning that make it more robust to violations of thseelected-completely-at-random assumption, leading to a system that can filter out malicious bots. In one public and one proprietary dataset, we show that proposed approaches are better at identifying humans in web data than standard PU learning methods.
Non-Human Trafic or trafic generated by robots (or bots) is estimated to constitute close
to half of all web trafic [
Malicious Bots
The major challenge in building machine learning (ML) models to detect bad bots is getting
labeled data. In this context, ML methods that aim to learn from positive and unlabeled data (PU
learning) provide promise [
Current PU learning frameworks assume that the labeled subset of the positive class is Selected Completely at Random (SCAR) from the positive class, where the labeling mechanism does not depend on the attributes of the instance 3[]. That is, the labeled subset of humans is not influenced by the features of the observations. Unfortunately, such an assumption is hard to justify in practice. For example, it is reasonable to expect that not all human visitors to an e-commerce website are equally likely to make a purchase. This requires us to revisit the PU framework to handle problems where the random sampling assumption is violated. Figur1e describes the problem we are addressing.
In this work, we address the question of classifying a web session as originating from a human
surfer or a robot, using PU learning. Our contribution includes two novel models to handle
biased sampling within the positive class, one of which is a scalable version of the proposals
in [
Malicious non-human activity on the web has been observed in the context of fake reviews,
information theft, the spread of misinformation, spam on social networks, and click fraud in
advertising [
While there has been some work to build recommendation systems that are robust to
adversarial attacks2[
PU Learning requires only a subset of one of the two classes to be labeled. Hence, PU learning
is appealing in the bot detection problem where we can assume that a subset of humans is
labeled. Early work in1[0] and [
Empirical success in a variety of scenarios has led to a recent focus on the class of PU learning
algorithms [
We first describe the notations and then briefly review PU learning work in [
To distinguish humans from bots we need to learn a classifier that generates the probabilities (| ). Here ∈ {0, 1} denotes if the observation was generated by a human =( 1 ) or bot and is the corresponding feature vector. The dataset for PU learning are instanc(e s, , ) from a space × × , where and
denote the feature and label space respectively. The binary variable represents if the instance is labeled. Since only positive instances (humans) are labeled, ( = 1| = 1) = 1
. Marginalizing( = 1| ) over , we get: ( = 1| ) = ( = 1| = 1, ) × ( = 1| ) + ( = 1| = 0, ) × ( = 0| ) Now, ( = 1| = 0, ) = 0 since only the positive instances are labeled. This leads to
The work by Elkan and Noto is based on the SCAR assumption. The approach assumes that
the labeled positive instances were chosen uniformly at random from the universe of positive
instances [
, i.e., the sampling process
The SCAR assumption above enables the building of PU Learning models for a range of scenarios. However, we believe that this is an unrealistic assumption and argue that explicitly accounting for selection bias for the known positives allows us to build models that are more aligned to the data.
We propose Modified Assumption Model (MAM), geared towards practical cases where labeling is performed via a stratified procedure. Instead of using the SCAR assumption, we make a more lenient assumption that known positives come from two sub-groups, where for one the sampling depends on and the other is independent of . (1) (2)
We introduce a new binary variable∈ {0, 1} that indicates which of the two sub-groups a given labeled instance =( 1 ) comes from. So, = 0 indicates that value of is independent of , whereas = 1 implies that value of is dependent on . Marginalizing over b, we get: ) )
Since is independent of when = 0 , so ( = 1| = 1, = 0, 1 − ( = 1| = 1, ), we can re-write above equation as ) = and given that( = 0| = 1, ) =
Similar to EAM the numerator can be obtained by training a classifier that separates the
labeled (= 1 ) points from the unlabeled (= 0 ). The denominator model can be trained using
= 1 and = 0 sets (note that points in these sets are labeled and positive, i.e=., 1 and = 1 ).
The constant can be estimated by averaging the scores predicted by the numerator model
for instances with = 0 in the validation set. If( = 1| = 1, ) = 0 for all data points, i.e.,
sampling is independent of , we recover EAM from MAM. Our MAM proposal closely relates
to the proposals made in [
The most general model, referred asRelaxed Assumption Model (RAM), does not make any assumption about being independent of . Instead, we attempt to model this process explicitly, i.e., we build a model fo r( = 1| = 1, ) - the denominator in equation (1). We first acquire a set of positive unlabeled instances o f= 1 with = 0 and then utilize standard binary classification methods to distinguish = 0 from = 1 amongst the positive instances.
We propose the use of a nearest-neighbor based method that finds points in the dataset that are close to the known positives but are not in the sampled set (= 1 ). Since any point outside the sampled set is = 0 , the nearest neighbor to a( = 1, = 1) point not in this set is implicitly taken to be ( = 1, = 0) . Note that this assumption may not always be true. As in the other models, we aim to find techniques that are robust even when the modeling assumption may be wrong. It is important to note that we do not alter the numerator in equation1() and hence training classifier for numerator remains identical to EAM.
In our first set of experiments, we artificially create PU learning datasets by hiding the ground truth labels of a labeled dataset during training. We then evaluate the trained model on a labeled test set. The simulations primarily involve controlling the subset of positive data points that are labeled for training, and all the other instances are unlabeled. The simulated datasets having varying degrees of “randomness”, one of the extremes is a completely random subset of positive samples (satisfying SCAR perfectly). The other is extreme is a carefully crafted subset of positive samples where SCAR assumption is violated.
Public Dataset: We use the KDDCUP’99 dataset (NSL-KDD Dataset), a widely adopted
labeled dataset for network intrusion detection. The train and test datasets have a total of
148, 517 records with 43 features each. To get around known problems with the dataset1[
Data Simulations: The process of creating artificial datasets involves hiding the labels for all negative points and a proportion of the positive points. We sample a labeled subset of positive data points to create a known subset of positives. We first build a supervised classifier to score each data point. The classification task here is to distinguish intrusive vs legitimate sessions and the score is the predicted class probability. We use this score to introduce sampling bias in creating the known subset of positives. Using a Random Forest classifier, we achieve an AUC (area under ROC curve) value o0f.9921 on the training data and0.9911 on the test data. We then curate diferent PU learning datasets by performing sampling over the scored data points by controlling two parameters as described below.
1. Topper : This parameter is used to introduce sampling bias by selecting only those positive points whose prediction score (using the supervised model) is higher than theth quantile of all positive labeled points. This selection of the top fraction of positives introduces a sampling bias since we are only selecting points with a high score. The idea is to capture spread within the positive class, and one meaningful scale is to use the estimated probability that a point is positive, given its features. Note that sampling is only done for positive class, the labels for all negative points are hidden.
2. Mixing: This parameter controls ‘randomness’ for the known subset of positives. After creating a sample of known positives based on the topper parameter, at valuewe swap % of the selected points with points from the positive set, the swapping is done with replacement. As we move from = 0 to = 100 we decrease the sampling bias in the set and correspondingly increase the randomness. A mixing of 100% means SCAR is completely satisfied.
The subset obtained at a particular value oafnd is the known labeled subset of positives, and the remaining points (all negatives and the unsampled positives) are treated as unlabeled. With distinct values o f and we obtain diferent simulated datasets. At a particular value of the topper parameter (), with = 100 , we get a completely random sample of positive class (satisfying SCAR), on the other end with = 0 we get an extremely biased sample, containing only high scoring points. When < 100 the sampling is not completely random and depends on the score of the supervised model that uses all the featur es. Consequently, the sampling variable is not independent of and the dataset does not align with the assumption of Elkan and Noto. We show that in cases of biased sampling, the proposed methods outperform the baseline approaches that rely on SCAR assumption.
Results on simulated datasets: We train MAM and RAM and compare against the baselines
- EAM [
The performance metrics are AUC (area under ROC curve) and Precision@Recall99, precision when 99% of known positives in the validation set are classified correctly. Unlike the standard ‘0.5’ threshold for classification, we set the classification threshold such that 99% of the legitimate sessions (positives) are correctly classified as legitimate. This is particularly important since in real systems we do not wish to interrupt legitimate users with any scrutiny. And so, Precision@Recall99 is an important metric to consider.
The results for the simulated experiments are shown in Tabl1e. When sampling is extreme, towards the left with smaller mixing parameter , RAM and MAM perform significantly better than the EAM along the two evaluation metrics. With more randomness (increasing mixing), EAM beats other methods but our proposed RAM still has competitive performance. Biased SVM performs poorly throughout. This shows that in extremely biased situations the proposed models MAM and RAM provide significant improvements by explicitly accounting for the sampling bias. On the other hand, EAM provides slight improvement at high mixing (random sample) since it is tailored specifically for scenarios when the SCAR assumption holds.
This section describes the application of RAM to a proprietary dataset from the trafic logs of an e-commerce website.
Data Description: The data contains a record for every page request, here referred to as a ‘hit’. We consider one week and collapse these records into ‘sessions’ for each user. A session combines a series of hits made by a user. The session ends with 30 minutes of inactivity. Overall we identify 3.6 million unique visitors from6 million sessions, and more than 100 million hits. The task is to label a session as arising from a human or a bot. The sessions from legitimate bots are filtered out using user-agent strings. The feature representation of all sessions utilizes a standard set of technology (e.g. browser and device types), behavioral (e.g. time between hits) and session related (e.g. timezone and time-of-day). Since this is an e-commerce website, we also have information as to whether a particular session resulted in a purchase. This information is leveraged to build our partial set of positives. The details are presented next.
Known subset of positives: Out of the 6 million sessions,36 (0.6%) sessions arepurchase sessions and360 (6%) sessions belong to an identified purchaser. We label this6% of sessions as positive (Human class). The dataset is then split into the train, test, and validation sets in an 80:10:10 ratio for modeling purposes.
Partially labeled test dataset: To validate our approach, we split the test data in3togroups
of points and observe the distribution of prediction scores across these classes. This split is
based on heuristics which we describe next.Positive data points: The subset of sessions that had
a user corresponding to a purchase session in the training dataseNt.egative data points: The
subset of sessions which have been originated from AWS/Azure servers are tagged as negative.
The assumption being that browsing sessions originating from these cloud environments are
unlikely to be initiated by humans. The set of AWS/Azure IPs are publicly availab1l4e,1[
It is important to note that all points during model training had the label of ‘Positive’ or ‘Unlabeled’. The ‘Negative’ label is only used for validation. Also notice that the set of known positives is neither complete (not all Humans purchase), nor is it an unbiased sample (diferent users have varying propensities for purchases).
Using the validation set, we identify a threshold that captur9e9s% of positive labels. The output score of the RAM model is converted into a booleanis-human label by using this threshold. Table2 shows the break-up of the trafic in the dataset and how RAM classifies points from each of these classes. As seen in the table, we misclassify only a few negatively labeled sessions (<3%) and in total, we have close to 82% human trafic as reported by this model. We expect high human trafic since the website has strict login requirements for accessing their content. Additionally, we observe a stark separation in the prediction scores for positive and negative classes. Most positive samples had a score close to 1, while negatives were scored close to 0.
In this paper, we have addressed the problem of detecting non-human trafic using positive and unlabeled data. Providing recommendation and personalization systems unbiased data to learn from, leads to a better experience for the end-customer. We specifically accounted for the selected completely at random assumption in standard PU Learning methods and conducted simulation studies for validation. We also evaluated our most general model, RAM, on a large real word e-commerce dataset. Given the scale of fraud due to bots, such bot detection systems have a clear utility. The methods described in this paper show promising results in addressing the endemic bot problem.