Determining that a resource is spam based upon a uniform resource locator of the webpage

Described herein are technologies relating to predicting whether a resource is spam based solely upon a Uniform Resource Locator (URL) for the resource. The URL is tokenized in connection with generating a sequence of numerical identifiers for the resource. A score for the URL is computed based upon the sequence of numerical identifiers, where the score is indicative of a probability that the resource pointed to by the URL is spam. generating a score for the URL based upon the sequence of numbers, wherein the score is indicative of a probability that the resource pointed to by the URL is spam. When the score is above a predefined threshold, a label is assigned to the URL that indicates that the resource pointed to by the URL is spam, and an entry for the resource is not included in a search engine index based upon the label assigned to the URL.

BACKGROUND

A computer-implemented search engine is configured to receive a query from a client computing device and return search results that represent documents (e.g., webpages, images, videos, etc.) to the client computing device, where the documents corresponding to the search results have been identified by the search engine as being relevant to the query. With more specificity, when the search engine receives the query, the search engine searches over a computer-readable search engine index based upon the query, where the search engine index includes entries corresponding to webpages that have been previously crawled by a web crawler of the search engine. The search engine identifies webpages indexed in the search engine index based upon the query, and the search engine then ranks the identified webpages based upon several features of the webpages and/or the query, such as static scores assigned to the webpages, numbers of inbound and outbound links in the webpages, whether words in the query match words in the titles of the webpages, amongst numerous other features. The search engine then returns a search engine results page (SERP) to the client computing device, where, for example, the SERP includes ten search results that represent the ten webpages most highly ranked by the search engine.

A search engine index for a general-purpose search engine includes hundreds of millions to billions of entries that represent hundreds of millions to billions of webpages that are available on the World Wide Web. There are, however, several billion (or even several trillion) webpages that exist; therefore, it can be ascertained that a huge number of webpages are not represented in the search engine index, where a webpage is not represented in the search engine index either because: 1) the search engine is unaware of the existence of the webpage; or 2) the search engine has deemed the webpage as being unworthy of representation in the search engine index (e.g., the webpage includes content that is not relevant to users of the search engine, the webpage includes malicious content, etc.).

Conventionally, to determine that a webpage is spam (and thus should not be represented in a search engine index), a computer-executable module searches a URL that points to the webpage for a specific (known) pattern that corresponds to spam webpages and/or a sequence of characters that are included in a blacklist. When the URL includes the patterns or when the URL includes the sequence of characters that are in the blacklist, the URL is assigned a label that indicates that the webpage pointed to by the URL is spam. Otherwise, the webpage is retrieved and content is extracted from the webpage to ascertain whether the webpage is spam.

The above-described approach is suboptimal, as the creators of spam webpages often change tactics in an attempt to cause a search engine to index spam webpages and return them to users who issue queries. In an example, a spammer may ascertain that URLs with the word “spam” in the path of the URL are not indexed by search engines; accordingly, the spammer may make a minor change to the text in the path of the URL, so that the blacklisted word no longer appears. The webpage is then retrieved and examined, which consumes finite resources of the search engine. Thus, there is currently no robust approach detecting spam webpages without retrieving and analyzing content of the webpages.

SUMMARY

Described herein are various technologies pertaining to determining that a resource that is available by way of the World Wide Web is spam without retrieving the resource and extracting content from the resource. With more particularity, the resource is determined to be spam based upon a Uniform Resource Locator (URL) for the resource, where a binary classifier receives a sequence of numerical identifiers (which represents at least a portion of the URL) and outputs a computed probability that the webpage is spam based upon the sequence of numerical identifiers. Therefore, unlike conventional approaches, the technologies described herein do not rely upon blacklists in connection with determining that a resource is spam, and further do not rely upon recognition of rigid patterns in URLs when determining that a resource is spam. Moreover, the technologies described herein can be used in combination with existing approaches for detecting spam resources; for instance, with respect to a resource, when a probability score output by the classifier indicates that the resource is not spam, the resource is retrieved and content from the resource is extracted and analyzed through use of natural language technologies (NLP). Therefore, computational resources are reserved while nevertheless resources that are spam are identified.

The classifier referenced above is trained based upon positive and negative training examples. The positive training examples are URLs that have been identified as pointing to resources that are spam, while the negative training examples are URLs that have been identified as pointing to resources that are not spam. The positive training examples are obtained based upon human labelers labeling resources as spam, computer-implemented tools labeling resources as spam based upon content extracted from the resources and analyzed by the computer-implemented tools, etc. The negative examples can be obtained from a search engine index of a search engine, where resources indexed in the search engine index are presumed to not be spam. The URLs are subjected to tokenization, such that each URL is represented by a series of identifiers (IDs), with each ID being a token in a vocabulary or representing an n-gram of predefined length. The number of tokens and length of n-grams are hyperparameters selected by a developer. Due to spammers often changing tactics, the computer-implemented classifier can be retrained periodically (e.g., every day, every other day) as new spam resources are identified and/or as new resources that are not spam are identified. Further, as will be described in greater detail herein, to avoid overfitting certain portions of some URLs can be masked (e.g., to prevent the classifier from providing an inordinate amount of weight to certain portions of URLs, such as hosts in URLs).

When a URL for a resource is received for analysis, the URL is tokenized and a sequence of identifiers for the URL is created, where the sequence of identifiers is representative of the URL. The sequence of identifiers is provided to the classifier, and based upon the sequence of identifiers the classifier outputs a score that is indicative of a probability that the resource pointed to by the URL is spam. The score can be compared to a threshold; when the score is above the threshold, a label is assigned to the URL, where the label indicates that the resource pointed to by the URL is spam. Accordingly, the resource is not retrieved, and an entry for the resource is not included in a search engine index. Contrarily, when the score is below the threshold, the resource is retrieved and content of the resource is analyzed to ascertain whether or not the resource is spam.

DETAILED DESCRIPTION

Various technologies pertaining to inferring that a resource available by way of the World Wide Web is spam based upon a Uniform Resource Locator (URL) of the resource are now described with reference to the drawings, where like reference numerals are used to refer to like elements throughout. In the following description, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of one or more aspects. It may be evident, however, that such aspect(s) may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form in order to facilitate describing one or more aspects. Further, it is to be understood that functionality that is described as being carried out by certain system components may be performed by multiple components. Similarly, for instance, a component may be configured to perform functionality that is described as being carried out by multiple components.

Described herein are various technologies pertaining to inferring that a resource that is available by way of the World Wide Web (including but not limited to a webpage) is spam based solely upon a URL of the resource. As will be described in detail below, a computer-implemented binary classifier is configured to receive a sequence of identifiers that represents a URL and is trained to compute a score for the URL based upon the sequence of identifiers, where the score is indicative of a probability that the resource pointed to by the URL is spam. When the score is sufficiently high (e.g., above a threshold), a label is assigned to the URL indicating that the resource is spam; thus, an entry for the URL is not created in a search engine index. When the score is below the threshold, the resource is retrieved and subjected to automated analysis to ensure that the resource is not spam. There are numerous types of spam resources, including those that sell fake goods and services, those that include backlinks to spam webpages, those that include encrypted links, etc.

There are numerous advantages associated with the technologies described herein. These advantages include saving of compute resources compared to conventional technologies, as the search engine can save compute resources by determining not to crawl and/or index webpages based upon the webpages identified as being spam. The technologies also are associated with an improved search engine index, as a determination as to whether to include an entry for a webpage in the search engine index is made based upon the webpage identified as not being spam. Moreover, as the search engine index fails to include an entry for a spam webpage in a search engine index, computer-readable storage required to store the index is reduced, and search results may be returned more quickly as the search engine need not contemplate entries for spam webpages. Other advantages will be appreciated.

With reference now toFIG.1, a functional block diagram of a system100is presented, where the system100is configured to update a search engine index to include an entry for a resource that is available by way of the World Wide Web based upon a determination that the resource is not spam, and further where the resource is inferred to not be spam based upon the URL for the resource. The resource may be a webpage, an image, a document, a video, etc. The example system100includes several web servers102-104and a computing system106that is in communication with the web servers102-104by way of a network107. The web servers102-104host respective websites, where each of the websites hosted by the web servers102-104includes at least one resource. As illustrated inFIG.1, the first web server102hosts a first website108, where the first website108includes N resources110-112. The Qth web server104hosts a Qth website114, where the Qth website114includes M resources116-118. While each of the web servers102-104is illustrated as hosting a single website, it is to be understood that one or more of the web servers102-104may host multiple websites. Additionally, while the websites108and114are illustrated as including several resources, one or more of the websites108and114may include a single resource. The resources110-112and116-118have URLs assigned thereto that point to locations where the resources110-112and116-118can be retrieved.

The computing system106is included in computing systems that implement a search engine. To that end, the computing system106includes a computer-readable data store120that retains a list of URLs122, where each URL in the list of URLs122points to a resource that is retrievable by way of the Internet. The data store further includes a search engine index124, where the search engine index124includes entries for respective resources that have been crawled by a crawler of the search engine. In an example, the URLs in the list of URLs122correspond to resources that the search engine is aware of but for which there are no entries in the search engine index124, and further where the resources corresponding to the URLs in the list of URLs122have not been analyzed to determine whether such resources are spam. The websites108and114may be relatively new websites, where sitemaps for the websites108and114have been submitted to the computing system106but the search engine has yet to crawl the resources110-112and116-118of the websites108and114, respectively. The sitemaps include URLs of the resources110-112and116-118, and therefore the listing of URLs122includes the URLs of the resources110-112and116-118.

The technologies described herein relate to determining whether or not the resources110-112and116-118can be characterized as being spam based upon their respective URLs, without requiring retrieval of the resources110-112and116-118from the web servers102-104to analyze content of the resources110-112and116-118. As will be described in greater detail below, a determination as to whether or not a resource is spam can be made based upon tokenization of a URL that points to the resource.

The computing system106includes a processor126and memory128that includes data that is retrieved by the processor126and instructions that are executed by the processor126. The memory128has a Pth URL130loaded therein, where the Pth URL130was retrieved from the list of URLs122in the data store120. In an example, the Pth URL130is the URL of the first resource110of the first website108hosted by the first web server102. The memory128further includes a tokenizer module132that is configured to tokenize URLs, such that the tokenizer module132breaks a received URL into a sequence of tokens. The tokenizer module132is additionally configured to generate a sequence of identifiers based upon the sequence of tokens, where an identifier in the sequence of identifiers represents an n-gram in the received URL. The received URL is thus represented by a sequence of tokens and a sequence of (non-overlapping) identifiers, collectively referred to herein as a sequence of IDs.

The memory128also includes a classifier module134that is configured to receive sequences of IDs output by the tokenizer module132and compute scores based upon the sequences of IDs, where a score computed by the classifier module134is indicative of a likelihood that a resource pointed to by a URL represented by the sequence of IDs is spam. The memory128also includes a labeler module136that is configured to assign a label to a URL based upon a score computed for the URL by the classifier module134. The label indicates one of: a) that the resource pointed to by the URL is spam; or b) the resource should be retrieved for potential representation in the search engine index124. Finally, the memory128includes a crawler module138that is configured to crawl a webpage when a score output by the classifier module134for a URL of the resource is below a threshold.

Operation of the tokenizer module132, the classifier module134, the labeler module136, and the crawler module138is now described with respect to the Pth URL130. The tokenizer module132receives the Pth URL130, parses the Pth URL130, and breaks the Pth URL130into a sequence of tokens. In an example, the tokenizer module132is trained to identify some predefined number of different tokens (e.g., 250,000 potential tokens), and parses the Pth URL130in search of such tokens. Upon tokenizing the Pth URL, the tokenizer module132maps the tokens to predefined (numerical) token identifiers. Thus, the tokenizer module132transforms the sequence of tokens extracted from the Pth URL130into a sequence of token identifiers. Optionally, the tokenizer module132forms a sequence of n-grams (e.g., bigrams, trigrams, four-grams, etc.) and maps each n-gram into one of a predefined number of n-gram identifiers. In a specific example, the tokenizer module132forms a sequence of bigrams from the sequence of tokens and hashes each bigram into one of several million (e.g., 10 million to 200 million) bigram identifiers. In another example, the tokenizer module132forms a sequence of trigrams from the sequences of tokens and hashes each trigram into one of several million trigram identifiers (e.g., 10 million to 200 million). Therefore, the tokenizer module132transforms the Pth URL130into a sequence of IDs, where the IDs include a sequence of token identifiers and a sequence of n-gram identifiers.

The classifier module134receives the sequence of IDs for the Pth URL output by the tokenizer module132and computes a score based upon the sequence of IDs, where the score is indicative of a likelihood that the resource pointed to by the URL is spam. Put differently, the classifier module134, upon receipt of the output of the tokenizer module132, ascertains whether the sequence of IDs of the Pth URL130are closer to: 1) sequences of IDs that represent URLs whose resources have previously been identified as being spam; or 2) sequences of IDs that represents URLs whose resources have previously been identified as not being spam.

As will be described in greater detail below, the classifier module134is trained based upon several positive and negative training items, where positive training items include URLs of resources that have been previously identified as being spam (e.g., by human labelers and/or a computer-implemented tool that labels resources as being spam based upon content of the resources extracted therefrom by the computer-implemented tool) and negative training items include URLs of resources that have entries in the search engine index124(and presumably therefore are not spam). When the classifier module134is trained, the tokenizer module132receives URLs in the positive and negative training items and outputs sequences of IDs that represent the URLs. The classifier module134is trained based upon such sequences of IDs.

The classifier module134outputs the score, and the labeler module136assigns a label to the Pth URL130based upon the score output by the classifier module134. For example, the labeler module compares the score output by the classifier module134with a predefined threshold; when the score is above the threshold (and thus the classifier module134has indicated that there is a high probability that the Pth resource pointed to by the Pth URL130is spam), the labeler module136assigns a label to the Pth URL130that indicates that the Pth resource is spam. Due to such label, the crawler module138does not retrieve the Pth resource, thereby conserving computing resources of the computing system106. When the score is below the threshold (and thus the classifier module134has indicated that there is at least some likelihood that the Pth resource is not spam), the labeler module136assigns a label to the Pth URL130indicating that the Pth resource should be crawled by the crawler module138. The Pth URL130can thus be added to a list of URLs, where the crawler module138is to crawl resources pointed to by URLs in such list.

While not illustrated, the computing system106can optionally include a computer-implemented tool that analyzes content extracted from resources and ascertains whether the resources are spam based upon the content extracted therefrom. For instance, such a tool uses natural language processing (NLP) technologies to ascertain whether or not a resource is spam—therefore, even when the classifier module134outputs a score that indicates that there is a reasonably high likelihood that the Pth resource is not spam based upon the Pth URL130, the computer-implemented tool analyzes content extracted from the Pth resource by the crawler module138and may determine that, in fact, the Pth resource is spam. The computer-implemented tool can then add the Pth URL to a list of URLs that point to spam resources. When the Pth resource is identified as not being spam by the computer-implemented tool, the search engine index124can be updated to include an entry for the Pth resource.

Subsequent to the search engine index124being updated to include the entry for the Pth resource, the search engine can receive a query from a client computing device operated by a user, and the search engine can return search results based upon the updated index124(e.g., the search engine returns a search result that represents the Pth resource).

While the classifier module134has been described as being configured to compute a score that is indicative of a likelihood that the Pth resource (pointed to by the Pth URL130) is spam, it is to be understood that the classifier module134can be adapted to output scores for the Pth resource that are indicative of other likelihoods. In another embodiment, based upon the sequence of identifiers for the Pth URL130output by the tokenizer module132, the classifier module134is configured to output a score that is indicative of a likelihood that the Pth resource will cause a client computing device that loads the Pth resource to install malware thereon. In such an embodiment, the classifier module134is trained based upon positive and negative training items, where the positive training items include URLs of resources that have previously been identified as causing malware to be installed on client computing devices and negative training items include URLs of resources that have previously been identified as not causing client computing devices to install malware thereon. In yet another embodiment, based upon the sequence of identifiers for the Pth URL130output by the tokenizer module132, the classifier module134is configured to output a score that is indicative of a likelihood that the Pth resource includes pornographic material. In such an embodiment, the classifier module134is trained based upon training items that include URLs of webpages and indications as to whether or not the webpages include pornographic material.

In still yet another embodiment, based upon the sequence of identifiers for the Pth URL130output by the tokenizer module132, the classifier module134is configured to output a score that is indicative of a likelihood that the Pth resource includes material that is generally not suitable for viewing by children under a particular age (e.g., a likelihood that the Pth resource is not family friendly). In such an embodiment, the classifier module134is trained based upon training items that include URLs of resources that have been identified as being family friendly and URLs of resources that have been identified as not being family friendly. In each of these embodiments, training items are readily available in a search log of a search engine, where a relatively large number of training items (e.g., on the order of millions or billions of training items) can be used to train the classifier module134.

The technologies described above exhibit various advantages over conventional approaches for determining whether or not a resource is spam. Due to the relatively large amount of training data, the computing system106is able to fairly accurately predict whether or not a resource pointed to by a URL is spam based solely upon the URL; that is, the classifier module134is able to discern patterns in URLs that are not readily discernable by humans, and employ those patterns to predict whether or not URLs are spam. In addition, the classifier module134can be readily updated as new URLs are identified (as spammers are constantly creating new spam resources). Moreover, computing resources are saved, as the crawler module138need not crawl resources that are identified by the classifier module134as having a high probability of being spam.

With reference now toFIG.2, a diagram that depicts operation of the tokenizer module132is presented. In an example, the Pth URL130is http://www.example.com/prdcttype/newitm/product.html. Continuing with this example, the tokenizer module132breaks the URL into a sequence of 11 separate tokens: “http://www.”, “example”, “.com/”, “prdct”, “type”, “/”, “new”, “itm”, “/”, “product”, and “.html”. As indicated previously, each of these 11 tokens may be one of a predefined number (e.g., 150,000, 250,000, 500,000, etc.) of tokens that the tokenizer module132is configured to identify. The tokenizer module132maps the tokens extracted from the Pth URL130to respective token identifiers for the tokens. In the example depicted inFIG.2, the tokenizer module132maps the eleven tokens into the sequence of token identifiers “5”, “25”, “676”, “2567”, “10876”, “356”, “12567”, “165789”, “356”, “25674”, and “213584”.

In addition, in the example depicted inFIG.2, the tokenizer module132forms bigrams from the tokens (or from the token identifiers), where the bigrams are “http://www.example”, “example.com/”, “.com/prdct”, “prdcttype”, “type/”, “/new”, “newitm”, “itm/”, “/product”, “product.html”, and “.html-null”. The tokenizer module132then transforms the bigrams into respective bigram identifiers. In an example, the tokenizer module132hashes each bigram into one of a predefined number (e.g., 180 million) of bins, where each bin corresponds to a bigram identifier. InFIG.2, the bigram “http://www.example” is transformed into the bigram identifier250623, the bigram “example.com” is transformed into the bigram identifier1345832, and so forth. The output of the tokenizer module132is thus a sequence of LDs that includes the sequence of token identifiers and the sequence of bigram identifiers. The Pth URL130is therefore represented by the sequence of IDs.

Referring now toFIG.3, operation of the classifier module134is illustrated. The classifier module134receives the sequence of LDs output by the tokenizer module132, where the sequence of IDs includes the token identifiers and the bigram identifiers. The sequence of IDs for the Pth URL130is provided as input to the classifier module134, and the classifier module134outputs a score for the Pth URL130(and thus for the first Pth resource), where the score is indicative of a likelihood that the Pth resource is spam.

Other embodiments pertaining to the tokenizer module132and the classifier module134are now set forth. A URL may include several elements that are consistent across URLs. For instance, a URL may include the following portions: 1) a scheme; 2) a host name; 3) a path; and 4) a query string. The scheme identifies the protocol to be used to access the resource on the Internet (e.g., HTTP or HTTPS). The host name identifies the host that holds the resource; for example, www.example.com. A host name can sometimes be followed by a port number. The path identifies the specific resource in the host that a web client wants to access—for example: /software/hto/cics/index.html. The query string, when included in a URL, follows the path and provides a string of information that the resource can use for some purpose (for example, as parameters for a search or as data to be processed). The query string is typically a string of name and value pairs; for example, term=bluebird. Name and value pairs are separated from each other by an ampersand (&); for example, term=bluebird&source=browser-search.

In an example embodiment, the tokenizer module132can parse a URL and identify one or more of these components of the URL, so that certain components of the URL can be masked, certain components can be extracted from the URL and tokenized separately, etc. This can be undertaken to avoid overfitting of the classifier module134. In an example, the classifier module134can include several separate classifier modules, with each classifier module being a binary classifier that is configured to compute a probability that a resource pointed to by a URL is spam based upon a portion of the URL or a combination of portions of the URL. For instance, the classifier module134can include a first classifier module that is configured to receive a sequence of IDs that represents an entirety of a URL, a second classifier module that is configured to receive a sequence of IDs that represents a host of the URL, a third classifier module that is configured to receive a sequence of IDs that represent a query string of the URL, etc. Each classifier module in the classifier modules is configured to compute a score that is indicative of a probability that the resource pointed to by the URL is spam based upon the sequence of IDs respectively received by the classifier module. Continuing with the example set forth above, the first classifier module receives a first sequence of IDs that represents the entirety of the URL; the second classifier module receives a second sequence of IDs that represents the host name in the URL (but not other portions of the URL), and the third classifier module receives a third sequence of IDs that represents the query string of the URL.

The first classifier module outputs a first score based upon the first sequence of IDs, the second classifier module outputs a second score based upon the second sequence of IDs, and the third classifier module outputs a third score based upon the third sequence of IDs, wherein the first, second, and third scores are computed probabilities that the resource pointed to by the URL is spam. The classifier module134can act as a voting system, taking into account the three different scores when outputting a probability that the resource pointed to by the URL is spam. Thus, a score output by the classifier module134is based upon multiple scores output by multiple classifiers.

Further, constraints can be learned based upon scores output by the multiple classifiers. Pursuant to an example, a spammer may create a URL for a spam resource and may create a particular query string in the URL for the purpose of preventing the classifier module134(or other computer-implemented tool for detecting spam resources) from labeling the resource as spam. The first classifier (based upon a sequence of IDs that represents the entirety of the URL) may output a score that indicates that the resource is more likely than not to be spam, but with a value that indicates a reasonably high probability that the resource is not spam (e.g., a 60% likelihood that the resource is spam). The second classifier (based upon a sequence of IDs that represents the host name in the URL) may output a second score that indicates that there is a very high probability that the resource is spam (e.g., over a 95% likelihood that the resource is spam). A constraint can be learned over time based upon scores output by the classifiers, such that when the first score is above a first threshold and the second score is above a second threshold, the URL is to be assigned a label that indicates that the resource is spam.

In such an embodiment, the classifiers are trained using appropriate positive and negative examples; for instance, the first classifier is trained with positive and negative examples with the entireties of the URL represented; the second classifier is trained with positive and negative examples with only the host names of the URLs represented, etc.

In another embodiment, the classifier module134can be trained with positive and negative examples for different portions of URLs. For instance, there may be positive training examples in the training data where the host name is masked; there may be positive training examples in the training data where the query string is masked; there may be negative training examples in the training data where the host name is masked, etc. This approach can prevent the classifier module134from being overfitted with respect to certain portions of URLs. When a prediction about a resource is desired, the classifier module134can be provided with multiple different sequences of IDs that correspond to the URL: 1) a first sequence of IDs that represent the entirety of the URL; 2) a second sequence of IDs that represents only the host name in the URL (with the query path, sub-domains, etc. masked); 3) a third sequence of IDs that represents only the query path, etc. The classifier module134can compute a score for each different sequence of IDs, and the classifier module134can output a final score for the resource based upon the multiple scores computed for the multiple different sequences of IDs.

With reference now toFIG.4, a functional block diagram of a computing system400that is configured to learn the tokenizer module132is illustrated. The computing system400has a computer-readable data store402that includes a list of URLs404. The list of URLs404can include URLs for webpages of which the search engine is aware. Thus, the URLs in the list of URLs404can include URLs that have a corresponding entry in the search engine index124as well as URLs for webpages of which the search engine is aware but have been identified as spam and thus do not have a corresponding entry in the search engine index124. The computing system400also includes a processor406and memory408that stores data that is accessed by the processor406and instructions that are executed by the processor406. The memory408has a sampler module410loaded therein that selects several URLs from the listing of URLs404in the computer-readable data store402. For instance, the sampler module410randomly samples URLs from the list of URLs404, and therefore the URLs selected by the sampler module410may include URLs that have corresponding entries in the search engine index124, URLs of webpages that have been labeled as being spam, URLs for popular webpages, URLs for unpopular webpages, etc. In another example, the sampler module410uses a weighted approach when sampling from the list of URLs404, such that the sampler module410is more likely to select URLs of webpages that have been identified as spam than URLs of webpages that have been determined to not be spam.

The memory406also includes a learner module412that learns identities of tokens in the URLs sampled from the list of URLs404by the sampler module410, and thus learns the tokenizer module132. The learner module412can learn the tokenizer module132based upon a statistical analysis of alphanumerical sequences in the sampled URLs, such that alphanumerical sequences that occur frequently in the sampled URLs are identified as tokens. The learner module412is configured to identify a predefined number of tokens in the URLs. As noted previously, in an example, the learner module412is configured to identify 250,000 tokens, such that the vocabulary of the tokenizer module132is 250,000.

Now referring toFIG.5, a functional block diagram of a computing system500that is configured to train the classifier module134is illustrated. While the system500is illustrated as being separate from the system400, it is to be understood that the system400can be configured to train the classifier module134. The computing system500includes a computer-readable data store502, where the data store502stores a database506of positive examples (URLs of resources that have been identified a spam) and a database507of negative examples (URLs of resources that are not spam). Further, in the databases506and507, there may be some time constraint on the examples (e.g., in the database506, the URLs may point to resources that have existed for a relatively small amount of time, such as two months).

The computing system500includes a processor508and memory510that includes data that is accessed by the processor508and instructions that are executed by the processor508. The memory510includes the sampler module410that samples URLs from the databases506and507. In an embodiment, the sampler module410samples from the databases506and507such that a ratio between positive and negative training examples is at some desired amount (e.g., 20% positive training examples and 80% negative training examples). Pursuant to an example, the sampler module410samples hundreds of millions to billions of training items (e.g., URLs and indications as to whether resources corresponding to the URLs are spam.

The memory510further includes a trainer module512that trains the classifier module134based upon the training items sampled from the databases506and507by the sampler module410. With more specificity, each of the URLs sampled from the databases506and507by the sampler module410is tokenized by the tokenizer module132, such that the tokenizer module132outputs a sequence of IDs for each URL. The trainer module512receives, for each sampled URL, the sequence of IDs that represents the URL and a label indicating whether or not a resource pointed to by the URL is spam.

The trainer module512uses any suitable supervised learning approach in connection with training the classifier module134, which in this example acts as a computer-implemented binary classifier. For instance, the trainer module512employs backpropagation when training the classifier module134.

Pursuant to an example, the classifier module134is trained periodically (e.g., every three days), and is trained based upon data in the databases506and507that is fairly recent (e.g., within the last two months). This allows the classifier module134to adapt to changes in behavior of spammers. As noted above, spammers tend to change tactics in order to cause a search engine to index a spam resource, so that the search engine returns the spam resource to a querier. By retraining the classifier module134periodically and based upon recent data, the scores output by the classifier module134are reflective of recent behavior of spammers.

Now referring solely toFIG.6, a flow diagram illustrating a methodology for training the classifier module134is illustrated. The methodology600starts at602, and at604, based upon URLs sampled from a search log of a search engine, a tokenizer designed to tokenize URLs is learned. At606, URLs are sampled to create two sets of training items: 1) a first set of training items that includes URLs of spam resources; and 2) a second set of training items that includes URLs of resources that are not spam.

At608, the tokenizer learned at604is employed to tokenize URLs in the first set of training items and URLs in the second set of training items in connection with forming a first set of identifiers and a second set of identifiers that represent the URLs in the first set of training items and the URLs in the second set of training items, respectively.

At610, the classifier module134is trained based upon the first set of identifiers and the second set of identifiers. The methodology600completes at612.

Now referring toFIG.7, a flow diagram illustrating a methodology700for determining whether or not a resource is spam is depicted. The methodology700starts at702, and at704a URL is received for a resource. In an example, there is no entry for the resource in a search engine index of a search engine. At706, the URL is tokenized to generate a sequence of tokens. At708, a sequence of IDs is generated based upon the sequence of tokens, wherein the sequence of IDs includes a sequence of token identifiers and a sequence of n-gram identifiers. At710, a score for the URL is computed based upon the sequence of IDs generated at708. At712, a determination is made as to whether the score is greater than a threshold. When the score is greater than the threshold, at714a label is assigned to the URL, where the label indicates that the resource pointed to by the URL is spam. If the score is less than the threshold, then the resource can be retrieved and further analyzed to ascertain whether or not the resource is spam. When it is determined that the resource is not spam, a search engine index is updated to include an entry for the resource. For instance, a crawler retrieves the resource, extracts information from the resource, and updates the search engine index based upon the information extracted from the resource. The methodology700ends at714when it is determined at712that the score is not greater than the threshold or subsequent to the label being assigned to the resource.

The features described herein relate to whether or not a resource (e.g., a webpage) is spam according to at least the examples provided below.

(A1) In one aspect, some embodiments include a method for identifying that a resource pointed to by a URL is spam, the method performed by a computer processor, the method including obtaining the URL that points to the resource, wherein the URL includes a sequence of characters. The method additionally includes generating a sequence of numbers based upon the sequence of characters, wherein the sequence of numbers represents at least a portion of the URL. The method also includes generating a score for the URL based upon the sequence of numbers, wherein the score is indicative of a probability that the resource pointed to by the URL is spam. The method additionally includes comparing the score with a predefined threshold. The method also includes when the score is above the predefined threshold, assigning a label to the URL that indicates that the resource pointed to by the URL is spam, wherein an entry for the resource is not included in a search engine index based upon the label assigned to the URL.

(A2) In some embodiments of the method of A1, the method also includes: a) when the score is below the predefined threshold, retrieving the resource pointed to by the URL; b) upon retrieving the resource, extracting content from the resource; and c) updating the search engine index to include the entry for the resource based upon the content extracted from the resource.

(A3) In some embodiments of any of the methods of A1-A2, the resource is a webpage.

(A4) In some embodiments of any of the methods of A1-A3, generating the score for the URL includes providing the sequence of numbers to a binary classifier, wherein the binary classifier has been trained based upon training pairs. In addition, each training pair includes: a) a respective sequence of numbers that represents a respective URL; and b) a respective label assigned to the respective sequence of numbers, wherein the respective label identifies whether or not the respective URL points to a respective spam resource.

(A5) In some embodiments of any of the methods of A1-A4, the sequence of numbers represents a first portion of the URL, and the URL includes a second sequence of characters. The method also includes generating a second sequence of numbers based upon the second sequence of characters, wherein the second sequence of numbers represents a second portion of the URL. The method additionally includes providing the sequence of numbers to a first binary classifier, wherein the first binary classifier outputs a first score based upon the sequence of numbers, wherein the first score is a first computed probability that the resource pointed to by the URL is spam. The method also includes providing the second sequence of numbers to a second binary classifier, wherein the second binary classifier outputs a second score based upon the second sequence of numbers, wherein the second score is a second computed probability that the resource pointed to by the URL is spam, wherein the score is based upon the first score and the second score.

(A6) In some embodiments of any of the methods of A1, A2, A4, or A5, the resource is an image or video.

(A7) In some embodiments of any of the methods of A1-A6, generating the sequence of numbers based upon the sequence of characters includes tokenizing the URL to generate a sequence of numerical identifiers, wherein the sequence of numbers is based upon the sequence of numerical identifiers.

(A8) In some embodiments of any of the methods of A1-A4, A6, or A7, the sequence of numbers represents a first portion of the URL, and the URL includes a second sequence of characters. The method also includes generating a second sequence of numbers based upon the second sequence of characters, wherein the second sequence of numbers represents a second portion of the URL. The method further includes providing the sequence of numbers to a binary classifier, wherein the binary classifier outputs a first score based upon the sequence of numbers, wherein the first score is a first computed probability that the resource pointed to by the URL is spam. The method additionally includes providing the second sequence of numbers to the binary classifier, wherein the binary classifier outputs a second score based upon the second sequence of numbers, wherein the second score is a second computed probability that the resource pointed to by the URL is spam, and further wherein the score for the URL is based upon the first score and the second score.

(A9) In some embodiments of the method of A8, the first portion of the URL is a domain, and the second portion of the URL is a path.

(B1) In another aspect, some embodiments include a method performed by at least one processor of a computing system. The method includes obtaining a uniform resource locator (URL) that points to a resource that is available by way of the World Wide Web. The method also includes tokenizing the URL to generate a vector of numbers, wherein the vector of numbers represents at least a portion of the URL. The method additionally includes providing the vector of numbers to a binary classifier, wherein the binary classifier, based upon the vector of numbers, outputs a computed probability that the resource is spam. The method further includes comparing the computed probability with a threshold and based upon the computed probability being above the threshold, assigning a label to the URL that indicates that the resource is spam, wherein the label is assigned without retrieving the resource.

(B2) In some embodiments of the method of B1, the resource is a webpage.

(B3) In some embodiments of any of the methods of B1-B2, the binary classifier is trained based upon a first set of training items and a second set of training items, the first set of training items including first URLs that have been identified as pointing to spam resources, the second set of training items including second URLs that have identified as pointing to resources that are not spam.

(B4) In some embodiments of the method of B3, the second set of training items are retrieved from a search engine index.

(B5) In some embodiments of any of the methods of B1-B4, the method further includes obtaining a second URL that points to a second resource that is available by way of the World Wide Web. The method also includes tokenizing the second URL to generate a second vector of numbers, wherein the second vector of numbers represents at least a portion of the second URL. The method additionally includes providing the second vector of numbers to the binary classifier, wherein the binary classifier, based upon the second vector of numbers, outputs a second computed probability that the second resource is spam. The method further includes comparing the second computed probability with the threshold. The method also includes based upon the second computed probability being below the threshold, retrieving the second resource. The method additionally includes extracting content from the second resource.

(B6) In some embodiments of the method of B5, the method also includes updating a search engine index to include an entry for the second resource based upon the content extracted from the second resource. The method additionally includes subsequent to updating the search engine index, receiving a query from a client computing device. The method further includes identifying the entry in the search engine index based upon the query. The method also includes returning a search result that represents the second resource to the client computing device.

(B7) In some embodiments of the method of B5, the method also includes assigning a second label to the second URL based upon the content extracted from the second resource, wherein the second label indicates that the second resource is spam.

(C1) In another aspect, some embodiments include a method performed by a computer processor, the method includes obtaining a URL that points to a resource that is available by way of the Internet, wherein the URL includes a sequence of characters. The method also includes generating a sequence of numerical identifiers based upon the sequence of characters, wherein the sequence of numerical identifiers represents at least a portion of the URL. The method additionally includes computing a score for the URL based upon the sequence of numerical identifiers, wherein the score is indicative of a probability that the resource pointed to by the URL is spam. The method further includes comparing the score with a predefined threshold. The method also includes when the score is above the predefined threshold, assigning a label to the URL that indicates that the resource pointed to by the URL is spam, wherein an entry for the resource is not included in a search engine index based upon the label assigned to the URL.

(C2) In some embodiments of the method of C1, the method further includes: a) when the score is below the predefined threshold, retrieving the resource pointed to by the URL; b) upon retrieving the resource, extracting content from the resource; and updating the search engine index to include the entry for the resource based upon the content extracted from the resource.

(C3) In some embodiments of any of the methods of C1-C2, the resource is a webpage.

(C4) In some embodiments of any of the methods of C1-C3, generating the score for the URL includes providing the sequence of numerical identifiers to a binary classifier, wherein the binary classifier has been trained based upon training pairs. Further, each training pair comprises: a) a respective sequence of numerical identifiers that represents a respective URL; and b) a respective label assigned to the respective sequence of numerical identifiers, wherein the respective label identifies whether or not the respective URL points to a respective spam resource.

(D1) In still yet another aspect, a computing system is described herein, where the computing system includes a processor and memory that stores instructions that, when executed by the processor, cause the processor to perform any of the methods described herein (e.g., any of A1-A9, B1-B7, or C1-C4).

(E1) In yet another aspect, a computer-readable storage medium is described herein, where the computer-readable storage medium includes instructions that, when executed by a processor, cause the processor to perform any of the methods described herein (e.g., any of A1-A9, B1-B7, or C1-C4).

Referring now toFIG.8, a high-level illustration of an example computing device800that can be used in accordance with the systems and methodologies disclosed herein is illustrated. For instance, the computing device800may be used in a system that determines that a resource is spam based upon a URL of the resource. By way of another example, the computing device800can be used in a system that trains a classifier module to output scores that are indicative of whether or not a resource is spam. The computing device800includes at least one processor802that executes instructions that are stored in a memory804. The instructions may be, for instance, instructions for implementing functionality described as being carried out by one or more components discussed above or instructions for implementing one or more of the methods described above. The processor802may access the memory804by way of a system bus806. In addition to storing executable instructions, the memory804may also store URLs, tokens of URLs, etc.

The computing device800additionally includes a data store808that is accessible by the processor802by way of the system bus806. The data store808may include executable instructions, a search engine log, tokens, etc. The computing device800also includes an input interface810that allows external devices to communicate with the computing device800. For instance, the input interface810may be used to receive instructions from an external computer device, from a user, etc. The computing device800also includes an output interface812that interfaces the computing device800with one or more external devices. For example, the computing device800may display text, images, etc. by way of the output interface812.

Additionally, while illustrated as a single system, it is to be understood that the computing device800may be a distributed system. Thus, for instance, several devices may be in communication by way of a network connection and may collectively perform tasks described as being performed by the computing device800.