Authentication and Account Takeover

Any website or app that only serves content does not need to make any distinction between users. However, when your site needs to differentiate the experience for different users—for example, by allowing users to create content or make payments—you need to be able to determine which user is making each request, which requires some form of user authentication.

Authentication on the internet today overwhelmingly takes the form of passwords. Passwords have many useful properties, the foremost of which is that due to their prevalence, nearly everyone knows how to use them. In the ideal situation, passwords serve to identify a user by verifying a snippet of information that is known only to that user. In practice, however, passwords suffer from many flaws:

• Users choose passwords that are easy to remember but also easy to guess. (The most common password seen in most data breaches is “password.”)

• Because it is nearly impossible to remember a unique, secure password for each site, people reuse passwords across multiple sites; research has shown that nearly half of all internet users reuse credentials.¹ This means that when a site is breached, up to half of its users are vulnerable to compromise on other unrelated sites.

• Users are vulnerable to “phishing” campaigns, in which a malicious email or website takes on the appearance of a legitimate login form, and tricks users into revealing their credentials.

• Users might write down passwords where they can be easily read or share them with friends, family, or colleagues.

What are websites to do in the face of these weaknesses? How can you ever be sure that the person logging in is the actual account owner?

One line of research has focused on developing alternative authentication mechanisms that can replace passwords entirely. Biometric identifiers such as fingerprint or iris scans have been shown to be uniquely identifying, and behavioral patterns such as typing dynamics have also shown success in small studies. However, biometrics lack revocability and are inherently unchangeable. Because current sensors are susceptible to being tricked, this brittleness makes for an unacceptable system from a security standpoint, even leaving aside the difficult task of getting users to switch away from the well-known password paradigm.

A more common pattern is to require a second factor for login. This second factor can be deployed all the time (e.g., on a high-value site such as a bank), on an opt-in basis (e.g., for email or social sites), or when the site itself detects that the login looks suspicious. Second factors typically rely on either additional information that the user knows or an additional account or physical item that the user possesses. Common second-factor authentication patterns include:

• Confirming ownership of an email account (via code or link)

• Entering a code sent via SMS to a mobile phone

• Entering a code generated by a hardware token (such as those provided by RSA or Symantec)

• Entering a code generated by a software app (such as Google Authenticator or Microsoft Authenticator)

• Answering security questions (e.g., “What month is your best friend’s birthday?”)

• Verifying social information (e.g., Facebook’s “photo CAPTCHA”)

Of course, all of these second factors themselves have drawbacks:

• Email accounts are themselves protected by passwords, so using email as a second factor just pushes the problem to the email provider (especially if email can be used to reset the password on the account).

• SMS codes are vulnerable to man-in-the-middle or phone-porting attacks.

• Hardware and software tokens are secure but the user must have the token or app with them to log in, and the token must be physically protected.

• Answers to security questions can be easily guessed.

• Social details can often be guessed or found on the internet; or the questions might be unanswerable even by the person owning the account, depending on the information requested.

In the most extreme case, the website might simply lock an account believed to be compromised, which requires the owner to contact customer support and prove their ownership of the account via an offline mechanism such as verifying a photo ID.

Regardless of the recovery mechanism used, a website that wants to protect its users from account takeover must implement some mechanism to distinguish legitimate logins from illegitimate ones. This is where machine learning and statistical analysis come in.

Account Creation

Even though getting into a legitimate user’s account might be necessary to steal assets belonging to that user, attacks such as sending spam or fake content can be carried out from accounts created and owned by the attacker. If attackers can create a large number of accounts, your site could potentially be overwhelmed by illegitimate users. Thus, protecting the account creation process is essential to creating a secure system.

There are two general approaches to detecting and weeding out fake accounts: scoring the account creation request to prevent fake accounts from being created at all, and scoring existing accounts in order to delete, lock, or otherwise restrict the fake ones. Blocking during the creation process prevents attackers from doing any damage at all, and also keeps the size of your account database under control; however, scoring after the fact allows greater precision and recall, due to the fact that more information is available about the accounts.

The following (simplistic) example illustrates this trade-off. Suppose that you have concluded from your data that if more than 20 new accounts are created from the same IP address in the same hour, these accounts are certain to be fake. If you score at account creation time, you can count creation attempts per IP address in the past hour and block (or perhaps show a CAPTCHA or other challenge) whenever this counter is greater than 20. (See the following subsection for details on rolling counters.) However, for any particular attack, there will still be 20 fake accounts that got through and are free to send spam. On the other hand, if you score newly created accounts once per hour and take down any group of more than 20 from the same IP address, you will block all the spammers but still give them each one hour to wreak havoc.

Clearly a robust approach combines instances of both techniques. In this section, we consider a scoring model that runs at account creation time. The features that go into such a model fall into two categories: velocity features and reputation scores.

Reputation scores

Velocity features are good at catching high-volume attacks, but what if the attacker slows down and/or diversifies their keys to the point where the requests are coming in below the threshold for any given key? How can we make a decision on a single request?

The foundation here is the concept of reputation. Reputation quantifies the knowledge we have about a given key (e.g., IP address) either from our own data or from third parties, and gives us a starting point (or more formally, a prior) for assessing whether a request from this key is legitimate.

Let’s look at the example of IP address. The simplest reputation signal for a registration defense model is the fraction of accounts on that IP that have been previously labeled as bad. A more sophisticated system might capture other measures of “badness”: how many account takeover attempts have been seen from the IP, or how much spam has been sent from it. If these labels are not readily available, you can use proxies for reputation:

• How long ago was the IP first seen? (Older is better.)

• How many legitimate accounts are on the IP?

• How much revenue comes in from the IP?

• How consistent is traffic on the IP? (Spikes are suspicious.)

• What’s the ratio of reads to writes on the IP? (More writes = more spam.)

• How popular is the IP (as a fraction of all requests)?

In addition to data you collect, there is a great deal of external data that can go into your reputation system, especially with regard to IP addresses and user agents. You can subscribe to a database that will inform you as to whether any given IP address belongs to a hosting provider, is a VPN or anonymous proxy, is a Tor exit node, and so on. Furthermore, there are a number of vendors who monitor large swaths of internet traffic and compile and sell IP blacklist feeds; these vendors typically will provide a free data sample so that you can evaluate whether their labels overlap with the abuse you see on your site.

With regard to user agents, there are published lists of known bot user agents and web scripting packages. For example, requests from curl, wget, or python-requests should be treated with extra suspicion. Similarly, if a request advertises itself as Googlebot, it is either the real Googlebot or someone pretending to be Googlebot in the hopes that your thirst for search engine optimization will result in you letting them through—but the real Googlebot is not likely to be creating any accounts!

Now let’s consider how to combine all of these features into a reputation score, again using IP address as an example. One question we could answer with such a score is, “What is the probability that this IP address will be used for abuse in the future?” To cast this question as a supervised learning problem we need labels. Your choice of labels will depend on exactly what you want to defend against, but let’s say for simplicity that an IP address is bad if a fake account is created on it in a period of n days. Our supervised learning problem is now as follows: given the past m days of data for an IP, predict whether there will be a fake account created on it in the next n days.

To train our supervised classifier, we compute features (starting with those described previously) for each IP for a period of m days and labels for the n days immediately following. Certain features are properties of the IP, such as “is hosting provider.” Others are time based, such as “number of legitimate accounts on the IP.” That is to say, we could compute the number of accounts over the entire n days, or for each of the n days, or something in between. If there is enough data, we could compute n features, one for each day, in order to capture trends; this aspect will require some experimentation.

If you are planning on retraining regularly (e.g., daily), validation on a held-out test set (i.e., a random subset of your data excluded from training) is probably sufficient. If retraining is sporadic (e.g., less often than every n days), you will want to be sure that your model is sufficiently predictive, so you should validate your model on the next n days of your training samples, as demonstrated in Figure 6-1.

Figure 6-1. Out-of-time training and validation

A final word on reputation: we have for the most part used IP address in this section as our example. However, everything we wrote applies to any of the keys listed in the section “Velocity features” earlier in the chapter. The only limits to you creating reputation systems for countries, browsers, domains, or anything else are the amount of data you have and your creativity.

Financial Fraud

If attackers can obtain your product at no cost, they can resell it for less than your price and make money. This problem applies not only to physical goods that have a large secondhand market (e.g., electronics), but also to services that can be arbitraged in a competitive market (e.g., ride hailing). If your audience is large enough, there will be some people who try to steal your product regardless of what it is. To stop these people, you need to determine whether each purchase on your site is legitimate.

The vast majority of financial fraud is conducted using stolen credit cards. Credit card fraud is older than the internet, and an enormous amount of work has been done to understand and prevent it. A single credit card transaction passes through many different entities as it is processed:

1. The merchant (you)

2. A payment processor

3. The merchant’s bank

4. The card network (Visa/Mastercard/American Express/Discover), which routes inter-bank transactions

5. The card issuer’s bank

Each of these entities has fraud detection mechanisms in place, and can charge upstream entities for fraudulent transactions that make it to them. Thus, the cost of fraud to you is not just the loss of your product or service, but also fees assessed at different levels of the ecosystem. In extreme cases, the damage to your business’s credit and reputation may cause some banks or networks to levy heavy fines or even refuse to do business with you.

Of course, credit cards are not the only payment method you might accept on your site. Direct debit is a popular method in Europe, where credit cards are more difficult to get than in the United States. Many sites accept online payment services such as PayPal, Apple Pay, or Android Pay; in these cases, you will have account data rather than credit card and bank data. However, the principles of fraud detection are essentially the same across all payment types.

Although many companies offer fraud detection as a service, you might decide that you want to do your own fraud detection. Perhaps you can’t send sensitive data to a third party. Perhaps your product has an unusual payment pattern. Or perhaps you have calculated that it’s more cost effective to build fraud detection yourself. In any case, after you have made this decision, you will need to collect features that are indicative of fraud. Some of these include:

• Spending profiles of customers:

  • How many standard deviations from the customer’s average purchase a given transaction is

  • Velocity of credit card purchases

  • Prevalence of the current product or product category in the customer’s history

  • Whether this is a first purchase (e.g., a free user suddenly begins making lots of purchases)

  • Whether this payment method/card type is typical for the customer

  • How recently this payment method was added to the account

• Geographical/time-dependency correlation:

  • All the correlation signals for authentication (e.g., geographic displacement, IP/browser history)

  • Geographic velocity (e.g., if a physical credit card transaction was made in London at 8:45 PM and in New York at 9:00 PM on the same day, the user’s velocity is abnormally high)

• Data mismatch:

  • Whether the credit card billing address matches the user’s profile information at the city/state/country level

  • Mismatch between billing and shipping addresses

  • Whether the credit card’s bank is in the same country as the user

• Account profile:

  • Age of the user’s account

  • Reputation from account creation scoring (as just discussed)

• Customer interaction statistics:

  • Number of times the customer goes through the payment flow

  • Number of credit cards tried

  • How many times a given card is tried

  • Number of orders per billing or shipping address

If you want to train a supervised fraud detection algorithm, or, even more basically, if you want to be able to know how well you’re doing at catching fraud, you will need labeled data. The “gold standard” for labeled data is chargebacks—purchases declared by the card owner to be fraudulent and rescinded by the bank. However, it usually takes at least one month for a chargeback to complete, and it can even take up to six months in many cases. As a result, chargebacks cannot be used for short-term metrics or to understand how an adversary is adapting to recent changes. Thus, if you want to measure and iterate quickly on your fraud models, you will need a supplementary metric. This could include any of the following:

• Customer reports of fraud

• Customer refunds

• Purchases made by fake or compromised accounts

Finally, when building your system, it is important to think carefully about where in the payment flow you want to integrate. As with other abuse problems, if you wait longer you can collect more data to make a more informed decision but risk more damage. Here are some possible integration points:

Preauthorization

You might want to run at least a minimal scoring before sending any data to the credit card company; if too many cards are declined, you might accrue fines. Furthermore, preauthorization checks prevent attackers from using your site as a test bed to determine which of their stolen cards work.

Post-authorization, prepurchase

This is a typical place to run fraud scoring because it allows you to ignore cards that are declined by the bank and to avoid chargebacks, given that you won’t take funds for fraudulent purchases. If your site is set up with auth/capture functionality, you can let the customer proceed as if the purchase were going through, and collect more data to do further scoring before actually receiving the funds.

Post-purchase

If you have a physical good that takes some time to prepare for shipping, or if you have a virtual service that cannot effect much damage in a short time, you can let the purchase go through and collect more behavioral signals before making a decision on the purchase and cancelling/refunding transactions deemed to be fraudulent. By scoring post-purchase, however, you are exposing yourself to chargebacks in the case that the real owner quickly discovers the fraud.

Bot Activity

In some cases, attackers can glean a great deal of value from a single victim. A bank account is an obvious example, but any account that can hold tradable assets is a target; these include ride- or house-sharing accounts, rewards accounts, or ad publishing accounts. For these high-value accounts it makes sense for attackers to work manually to avoid detection. On the other hand, in many cases the expected value of a single victim is very small, and is in fact less than the cost of the human effort required to access or use the account; examples include spamming, credential stuffing, and data scraping. In these cases, attackers must use automation if they hope to make a profit. Even in the higher-value cases, human effort can scale only so far, and automation is likely to provide higher return on investment for attackers.

It follows that finding abuse in many cases is equivalent to finding automated activity (aka bots) on your site or app.⁵ Bots might try to take any of a number of actions, including the following:

Account creation

This was discussed in depth earlier. These bots can be stopped before or after account creation.

Credential stuffing

Running leaked lists of username/password pairs against your login infrastructure to try to compromise accounts. These bots should be stopped before they gain access to the account, ideally without leaking information about whether the credentials are valid.

Scraping

Downloading your site’s data for arbitrage or other illicit use. Scraping bots must be stopped before they are served any data, so detection must be synchronous and very fast in order to avoid a big latency hit for legitimate users.

Click fraud

Inflating click counts to bring extra revenue to a site that hosts advertisements, or using artificial clicks to deplete a competitor’s ad budget. The minimal requirement here is that advertisers not be billed for fraudulent clicks; this computation could be in real time or as slow as a monthly or quarterly billing cycle. However, if recent click data is used to determine current ad ranking, fraudulent clicks must be handled in near real time (though asynchronously).

Ranking fraud

Artificially increasing views, likes, or shares in order to make content reach a wider audience. These fraudulent actions must be discounted soon after they occur.

Online gaming

Bots can simulate activity that would be tedious or expensive for humans to take, such as moving large distances geographically (via spoofed GPS signals) or earning points or other gaming currency via repetitive actions (e.g., battling the same enemy over and over to gain a huge number of experience points).

As with financial fraud, there are entire companies devoted to detecting and stopping bot activity; we give some pointers here for detecting and stopping basic bot attacks.

Bots come in a wide variety of levels of sophistication and with a wide variety of intents. Many bots are even legitimate: think of search engine crawlers such as Googlebot or Bingbot. These bots will typically advertise themselves as such and will also honor a robots.txt file you place on your site indicating paths that are off-limits to bots.

The dumbest bots are those that advertise themselves as such in their user agent string. These include tools such as curl and wget, frameworks such as python-requests, or scripts pretending to be legitimate crawlers such as Googlebot. (The last can be distinguished by the fact that they don’t come from a legitimate crawling IP address.)

After you have eliminated the dumb bots, the key to detecting further automated activity is aggregation—can you group together requests that come from the same entity? If you require users to be logged in to engage in whatever activity the bots are trying to automate, you will already have a user ID upon which you can aggregate. If a user ID is not available, or if you want to aggregate across multiple users, you can look at one or more of IP addresses, referrers, user agents, mobile app IDs, or other dimensions.

Now let’s assume that you have aggregated requests that you believe to be from a single entity. How do you determine whether the activity is automated? The key idea here is that the pattern of requests from bots will be different from the patterns demonstrated by humans. Specific quantitative signals include the following:

Velocity of requests

Bots will make requests at a faster rate than humans.

Regularity of requests, as measured by variance in time between requests

Bots will make requests at more regular intervals than humans. Even if the bot operator injects randomness into the request time, the distribution of interarrival times will still be distinguishable from that of humans.

Entropy of paths/pages requested

Bots will focus on their targets instead of browsing different parts of the site. Scraping bots will request each page exactly once, whereas real users will revisit popular pages.

Repetitive patterns in requests

A bot might repeatedly request page A, then B, then C, in order to automate a flow.

Unusual transitions

For example, a bot might post to a content generation endpoint without loading the page containing the submission form.

Diversity of headers

Bots might rotate IP addresses, user agents, referrers, and other client-site headers in order to seem like humans, but the distribution generated by the bot is unlikely to reflect the typical distribution across your site. For example, a bot user might make exactly the same number of requests from each of several user agents.

Diversity of cookies

A typical website sets a session cookie and can set other cookies depending on the flow. Bots might ignore some or all of these set-cookie requests, leading to unusual diversity of cookies.

Distribution of response codes

A high number of errors, especially 403 or 404, could indicate bot requests whose scripts are based on an older version of the site.

Several bot detection systems in the literature make use of some or all of these signals. For example, the PubCrawl system⁶ incorporates clustering and time series analysis of requests to detect distributed crawlers, whereas the algorithm of Wang et al.⁷ clusters sequences of requests based on a similarity metric.

Sometimes, you will not be able to aggregate requests on user ID or any other key—that is, you have no reliable way to determine whether any two requests come from the same actor. This could happen, for example, if the endpoint you want to protect is available to the public without a login, or if many different accounts act in loose coordination during an attack. In these cases, you will need to use request-based bot detection; that is, determine whether a request is automated using only data from the request itself, without any counters or time series data.

Useful data you can collect from the request includes the following:

• The client’s ability to run JavaScript. There are various techniques to assess JavaScript ability, from simple redirects to complex challenge–response flows; these differ in latency introduced as well as complexity of bots they can detect.

• An HTML5 canvas fingerprint, which can be used to determine whether the user agent is being spoofed.⁸

• Order, casing, and spelling of request headers, which can be compared with legitimate requests from the claimed user agent.

• The TLS fingerprint, which can be used to identify particular clients.

• Spelling and casing of values in HTTP request fields with a finite number of possibilities (e.g., Accept-Encoding, Content-Type)—scripts might contain a typo or use unusual values.

• Mobile hardware data (e.g., microphone, accelerometer), which can be used to confirm that a claimed mobile request is coming from an actual mobile device.

• IP address and browser/device info, which you can use to look up precomputed reputation scores.

When implementing request-based detection, we encounter the typical trade-off between preventing abuse and increasing friction for good users. If you give each request an interactive CAPTCHA, you will stop the vast majority of bots but will also annoy many of your good users into leaving. As a less extreme example, running JavaScript to collect browser or other information can introduce unacceptable latency in page load times. Ultimately, only you can determine your users’ tolerance for your data-collection processes.

Labeling Data

In the ideal case, you will have a large set of data that was sampled for this particular project and manually labeled. If this is the case for your site or app, great! In real life, however, hand-labeled data usually isn’t presented to you on a platter. Even if you can get some, it might not be enough to train a robust classifier.

At the other extreme, suppose that you are unable to sample and label any data at all. Is supervised learning useless? Probably not—you must have some accounts that you have already banned from the site for fraud or spam; if this is not the case, your problem probably isn’t big enough to justify engineering a large-scale machine learning classifier. The already banned accounts might have been categorized that way through a rules-based system, other machine learning models, or manual intervention due to user complaints. In any case, you can use these accounts as your positive (i.e., bad) examples,¹⁰ and you can use all accounts not (yet) banned as your negative examples.

What risks does this approach entail? One risk is blindness: your model learns only what you already know about the accounts on your system. Without manual labeling, retraining won’t help the model identify new types of abuse, and you will need to build yet another model or add rules to take care of new attacks.

Another risk is feedback loops—your model learning from itself and amplifying errors. For example, suppose that you erroneously banned some accounts from Liechtenstein. Your model will then learn that accounts from Liechtenstein are predisposed to be abusive and block them proportionately often. If the model retrains regularly and the false positives are not remediated, this feedback loop could eventually lead to all accounts from Liechtenstein being banned.

There are some steps that you can take to mitigate risk when using imperfectly labeled data:

• Oversample manually labeled examples in your training data.

• Oversample false positives from this model when retraining (as in boosting).

• Undersample positive examples from previous iterations of this model (or closely related models/rules).

• If you have resources to sample and manually label some accounts, use them to adjudicate cases near the decision boundary of your model (as in active learning¹¹).

One final warning when you are training on imperfect data: don’t take too literally the precision and recall numbers that come out of your validation step. If your model does a reasonable job of generalizing from the data you have, it will find errors in your labeled set. These will be “false positives” and “false negatives” according to your labels, but in real life they are instances your classifier got correct. Thus, you should expect the precision when your model is deployed to be higher than that which you obtain in offline experiments. Quantifying this effect can be done only through online experimentation.

Cold Start Versus Warm Start

If you have no scoring at account creation (“cold start”), model training is straightforward: use whatever labels you have to build the model. On the other hand, if there is already a model running at account creation time and blocking some requests (“warm start”), the only bad accounts that are created are the ones that get through the existing model (i.e., the false negatives). If you train v2 of your model on only this data, v2 might “forget” the characteristics of v1.

To illustrate this conundrum with an example, suppose v1 blocks all requests with IP velocity greater than five per day. Then, the IP velocity of bad accounts used to train the v2 model will be very low, and this feature will probably not be significant in the v2 model. As a result, if you deploy v2, you run the risk of allowing high-velocity requests per IP.

There are a few different approaches to avoid this problem:

Never throw away training data

Collect your data for the v2 model after v1 is deployed, and train on the union of v1 and v2 training data. (If you are facing fast-changing adversaries, consider applying an exponential decay model to weight more recent attacks higher.)

Run simultaneous models

Train and deploy the v2 model, but also run the v1 model at the same time. Most likely the reason you were building v2 in the first place is that the performance of v1 is degrading; in this case you should tune the threshold of v1 to make it more accurate. This approach can lead to an explosion in complexity as you deploy more and more models.

Sample positives from the deployed v1 model to augment the v2 training data

The advantage of this approach is that all the training data is recent; the disadvantage is that it’s difficult to know what the v1 false positives are (see the following section).

False Positives and False Negatives

In theory, false negatives are easy to identify—these are accounts that your model said were good that you allowed to register but ended up being bad. But in practice, you can identify false negatives in your model only if they trigger some other model or rule, or prompt user complaints. There will always be bad accounts that get through undetected and are therefore mislabeled. If you have the resources to sample and label examples, you will get the most leverage by sampling accounts with scores near your classification threshold; these are the examples about which your model is most uncertain.

False positives are also tricky. You blocked them by using the best information you had at the time, and that’s it—you get no more information with which to refine your decision. Even worse, a false positive at account creation means you blocked a new user that didn’t already have an established relationship with your site. Such a user will most likely give up rather than complain to your support team.

One way to deal with the false positive problem is to let a small fraction of requests scored as bad create accounts anyway, and monitor them for further bad activity. This approach is imperfect because an attacker who gets only five percent of their registrations through might just give up on spamming because it doesn’t scale—your testing approach led the adversary to change their behavior, and thus your test results might be inconclusive. (This problem exists when A/B testing adversarial models in general.) You should also monitor such accounts for good activity to find “true false positives.”

Identified false positives and false negatives can be oversampled in your training data when you retrain the model using one of the techniques of the previous section.

Multiple Responses

Typically, an account creation model will have multiple thresholds: block if the score is super bad, let the request through if the score is reasonably good, and present a challenge (e.g., CAPTCHA or phone verification) to the “gray area” scores. This approach can complicate performance measurement and labeling for retraining: is a bad account that solved a challenge a true positive or a false negative? What about a good account that received a challenge? Ideally each case can receive a certain cost in your global cost function; if you’re not using a cost function, you will need to decide what your positives and negatives are.

Large Attacks

In either the cold-start scenario or the “sample positives” approach to the warm-start problem, the following can occur: there was a single unsophisticated attacker who made so many requests from a single IP that this one attacker was responsible for half the bad requests in the training data. If you simply train on the distribution as is, your model will learn that half of all attacks look like this one—the model will be overfit to this single event, simply because it was so large (and in the warm-start case, it was even defended).

One approach to solving this problem is to downsample large attacks; for example, from an attack with x requests you might sample log(x) requests for the training data. Then, this attack appears large but not overwhelming.

This approach begs the question: how do you identify attacks from a single actor? We’re glad you asked—this topic is the focus of our next section.

Example: Clustering Spam Domains

To demonstrate both the cluster generation and cluster scoring steps, we will work with a labeled dataset of internet domain names. The good names are the top 500,000 Alexa sites from May 2014, and the bad names are 13,788 “toxic domains” from stopforumspam.org. The fraction of positive (i.e., spam) examples in the dataset is 2.7%, which is reasonable in terms of order of magnitude for the abuse problems with which you will typically contend.

The domain data is not account or activity data, but it does have the property that we can find clusters of reasonable size. For example, a quick scan of the bad domains in alphabetical order reveals the following clusters of a size of at least 10:

(Apparently selling knockoff shoes is a favorite pastime of spammers.)

Good domains also can appear in clusters, typically around international variants:

Because many domains, both good and bad, do not appear in clusters, the goal of the experiments that follow will be to maximize recall on the bad domains while maintaining high precision. In particular, we will make the following choices:

• Clusters must be of size at least 10 in order to be considered.

• Clusters must be at least 75% spam in order to be labeled as bad.

These choices will minimize the chances of good domains getting caught up in clusters of mostly bad domains.

Generating Clusters

Let’s tackle the first step: separating your set of accounts or actions into groups that are similar to one another. We will consider several different techniques and apply them to the spam dataset.

To cluster, we must generate features for our domains. These features can be categorical, numerical, or text-based (e.g., bag-of-words). For our example, we use the following features:

• Top-level domain (e.g., “.com”)

• Percentage of letters, digits, and vowels in the domain name

• Age of the domain in days, according to the whois registration date

• The bag of words consisting of n-grams of letters in the domain (e.g., “foo.com” breaks into the 4-grams [“foo.”,“oo.c”,“o.co”,“.com”]) for n between 3 and 8

  Note

  This technique is often called shingling. The following Python code computes n-grams for a string:

  def ngram_split(text, n):
    ngrams = [text] if len(text) < n else []
    for i in range(len(text)-n+1):
         ngrams.append(text[i:i+n])
    return(ngrams)

• The first n letters of the domain, for n in (3,5,8)¹³

A good clustering method will produce relatively pure clusters (i.e., predominantly good or bad rather than mixed). In addition, if your data is heavily skewed, as in our example, the clustering algorithm should rebalance the classes to some extent. The main intuition behind clustering is that bad things disproportionately happen in bunches, so if you apply a clustering algorithm and get proportionately more good clusters than bad clusters, clustering hasn’t helped you much.

With these principles in mind, when searching for the best clustering strategy, we need to consider the proportion of clusters that are labeled bad, the proportion of domains within the bad clusters that are labeled bad, and the recall of the bad clusters.

import lsh

def compute_hashes(domains, n, num_perms=32, max_items=100,
hash_function=lsh.md5hash):
    # domains is a dictionary of domain objects, keyed by domain name

    # Create LSH index
    hashes = lsh.lsh(num_perms, hash_function)

    # Compute minHashes
    for dom in domains:
        dg = hashes.digest(domains[dom].ngrams[n])
        domains[dom].digest = dg
        hashes.insert(dom, dg)
    return(hashes)


def compute_lsh_clusters(domains, hashes, min_size=10, threshold=0.5):
    # domains is a dictionary of domain objects, keyed by domain name
    # hashes is an lsh object created by compute_hashes

    clusters = []
    for dom in domains:
        # Get all domains matching the given digest
        # result is a dictionary of {domain : score}
        result = hashes.query(domains[dom].digest).
        result_domains = {domains[d] : result[d] for d in result
                if result[d] >= threshold}
        if len(result_domains) >= min_size:
            # Create a cluster object with the result data
            clusters.append(cluster(dom, result_domains))
    return(clusters)

hashes = compute_hashes(data, n, 32, 100)
clusters = compute_lsh_clusters(data, hashes, 10, threshold)

Scoring Clusters

In the previous section, we applied several techniques to find clusters of similar domains in our dataset. However, the act of clustering doesn’t immediately achieve our goal of finding abuse; it simply reorganizes the data in a way that makes abusive entities more likely to “pop out.” The next step is to look at the clusters and determine which ones are abusive and which ones are legitimate.

In general, when clustering abusive entities, your first instinct might be to say that any cluster of a certain size is automatically bad. Rules like this are a good initial step, but when you have a popular website with a large amount of data, there are sure to be legitimate outliers, such as these:

• Lots of activity on a single IP address? It could be a mobile gateway.

• Lots of accounts sharing a tracking cookie? It could be a public computer.

• Lots of registrations in quick succession with email addresses in a certain format? It could be a training session at a school or company where everyone is asked to create an account.

How can we distinguish the legitimate clusters from abusive ones? The answer, as usual, is in the data. Specifically, we want to extract cluster-level features that will allow us to distinguish the two types of clusters. Our intuition here is that if a single actor is responsible for creating a cluster, the data within that cluster will probably have an unusual distribution in some dimension. As a simple example, if we find a batch of accounts that all have the same name, this batch is suspicious; if the distribution of names in the cluster roughly follows the distribution of names across the entire site, this batch is less suspicious (at least along the name dimension).

Ideally, we would like to treat the cluster scoring stage as a supervised learning problem. This means that we must acquire cluster-level labels and compute cluster-level features that we can input to a standard classification algorithm such as logistic regression or random forest. We now briefly summarize this process.

Feature extraction

As we did with labels, we need to aggregate account-level features into cluster-level features so that each cluster is represented by a single numerical vector that can be fed into a classifier. Because our intuition is that abusive clusters will show less diversity along certain dimensions, we want to compute features that measure this diversity. For numerical account-level features, we select nine cluster-level features to compute:

• Min, max, median, quartiles

• Mean and standard deviation

• Percentage of null or zero values

For categorical account-level features, we compute four features:

• Number of distinct values

• Percentage of values belonging to the mode

• Percentage of null values

• Entropy

Let’s consider some concrete examples of this process, using n-gram clusters that correspond to examples of good and bad clusters we found earlier. Per our previous analysis, we will focus on 7-grams. Figure 6-2 shows per-domain features for domains containing the 7-gram “jordano,” whereas Figure 6-3 shows the same for domains containing the 7-gram “gabyte.”

Figure 6-2. Domains with the 7-gram “jordano”

Figure 6-3. Domains with the 7-gram “gabyte”

Expanding the 5 numerical and 4 categorical features as just described gives a total of 65 features. For example, the “whois” domain-level feature (which gives the age of the domain in days) produces the cluster-level features shown in Figure 6-4.

Figure 6-4. Examples of cluster-level features for “whois”

Whereas the “top-level domain” feature produces the features in Figure 6-5.

Figure 6-5. Examples of cluster-level features for “top-level domain”

From these two examples, we expect the fact that most whois results return null for the bad domains and return a wide range of results for the good domains to be a distinguishing feature. We also expect that high diversity of top-level domains indicates a good cluster.

Classification

Now let’s attempt to put this intuition into practice by training a classifier. We will use a random forest classifier, which is a nonlinear classifier that tends to be effective “out of the box” with little tuning. We downsample the good clusters in the training set in order not to overwhelm the classifier; however, we leave the test set unbiased so that we get an accurate calculation of precision and recall:

from sklearn.metrics import roc_auc_score, roc_curve, precision_recall_curve
from sklearn.model_selection import train_test_split
from sklearn.ensemble import RandomForestClassifier
from random import random
import matplotlib.pyplot as plt

# Add a random entry to each row, to be used for sampling
R = [random() for i in range(len(ngram_cluster_features))]
ngram_cluster_features['rand'] = R

# Split into 2/3 train, 1/3 test, and downsample good clusters
train, test = train_test_split(ngram_cluster_features.fillna(value=0),
                               test_size=0.33)
sample_factor = 0.2
sampled_train = train[(train.label == 1) | (train.label == 0) &
                      (train.rand < sample_factor)]

# Fit and predict
features = sampled_train[sampled_train.columns.difference(
    ['label','rand','score'])]
labels = sampled_train.label
clf = RandomForestClassifier(n_estimators=20)
clf.fit(features, labels)
probs = clf.predict_proba(test[train.columns.difference(
    ['label','rand','score'])])

# Compute and plot P-R curve
precision, recall, thresholds = precision_recall_curve(
    test.label, probs[:,1])
plt.step(recall, precision, color='b', alpha=0.2, where='post')
plt.fill_between(recall, precision, step='post', alpha=0.2, color='b')
plt.xlabel('Recall')
plt.ylabel('Precision')
plt.ylim([0.0, 1.05])
plt.xlim([0.0, 1.0])
plt.title('Precision-Recall curve for 7-gram groupings')
plt.show()

# Find threshold for 95% precision
m = min([i for i in range(len(precision)) if precision[i] > 0.95])
p,r,t = precision[m], recall[m], thresholds[m]
print(p,r,t)

From this calculation and the precision-recall curve for this classifier in Figure 6-6, we see that we can achieve 61% recall and 95% precision on clusters at a threshold of 0.75 (i.e., 15 of the 20 trees in our forest classify the cluster as bad).

Figure 6-6. Precision-recall curve for 7-gram groupings for spam domain classification

But this calculation is at the cluster level—what is our precision and recall on the individual domain level? For example, if false positives tended to be larger clusters on average than true positives, our precision on individual domains would be less than on clusters.

We can work out the item-level precision and recall as follows:

# Compute item-level precision/recall
pos = (test.score * test['count'])
neg = (1-test.score) * (test['count'])
tp = sum(pos[test.label >= t])
fp = sum(neg[test.label >= t])
tn = sum(neg[test.label < t])
fn = sum(pos[test.label < t])
item_precision = 1.0*tp/(tp+fp)
item_recall = 1.0*tp/(tp+fn)

In this example, we find that precision drops slightly to 92%, but recall goes all the way down to 21%. This result makes sense intuitively, given that many bad domains in our dataset are not part of clusters and must thus be detected via some other means.