• Contribute
• What's New
• Submit News

“Tricksy spammers, they’ll stop at nothing to get my precious”

Introduction

Can Laws Defeat Spam? No. This has to be one of the greatest misconceptions of users. The internet is just that, an “INTERnational NETwork” that cannot be governed by one country’s laws. Spammers can exist anywhere on the internet, meaning they can sling their wares from anywhere in the world, making the laws of one country completely irrelevant. Also, the decentralized, self-organizing design of the internet makes it nearly impossible to regulate by external means. It would be easier to regulate the weather than to regulate the internet.

Spam as a Living Organism

1. Spam evolves and adapts based off the rules of natural selection

   Through the fight against spam, spam has demonstrated an uncanny ability to adapt to the conditions of its environment, namely the internet. When one barrier against a strain of spam is put up, another, resistant strain appears. This is similar to how bacteria builds immunity against antibiotics, the strains that are not immune will die, while the ones that are immune take over and become the dominant, drug resistant strain. This leads to the belief that spam will not die until the barriers of its environment evolve faster than it does.

2. Spam lives within an eco-system, and we’re its food

   The internet is a complex chain of systems that all rely on each for the other’s survival. Without an internet protocol, a web browser couldn’t exist. Without web servers, the web wouldn’t exist. Without … (you get the picture). This chain of systems can be likened to an eco-system, with spam existing at a parasitic level of species within this system. It consumes resources (bandwidth, servers, time) in its attempt to reach its primary host: us. Once spam reaches its target, its sole purpose is to solicit its “food” from us, primarily money. If it is effective, that strain of spam lives and continues to propagate, otherwise it will die. Can the internet eco-system be modified so spam can’t feed?

3. Spam has genetic traits and markers

   Just like any organism, spam contains certain traits that uniquely identify it. This can be a combination of words, information inside the header of the e-mail, the format of the message (HTML, plain text, rtf), the message encoding (base64), does it contain image links, the number of links, does it contain hidden text, so on and so forth. Up until recently, spam filters have primarily focused on just one of these traits, the wording of the e-mail. Spam, being an organism, evolved so this marker was hidden within its code, making it difficult at best to filter. It did this by including random, non-spam words in hidden areas of the e-mail, by modifying words like Viagra with V1@gr@, sending spam as image links, and by encoding the message in a format that filters could not read. The good news is this “gene” is still present, and can be unlocked by identifying the defensive genes within the spam message.

   The goal of this article is to present a highly adaptive spam filtering technology that treats spam as an artificial organism. To achieve this goal, the technique described will employ an Artificial Neural Network (ANN) that will learn what features within a set of gene markers qualify an e-mail as spam or “ham” (good e-mail). Prior knowledge of ANNs and the methods required to train them is highly recommended before continuing with this article.

   NOTE: This article will present just the filter engine. How to implement the engine on specific clients and servers is left entirely to the reader.

The Plan of Attack

1. Process and parse an e-mail into string tokens.
2. Look at the defined genetic markers within the e-mail, and generate numerical statistics on each marker between {0, 1}.
3. Take the collection of statistics generated, and feed them as input vectors into our Artificial Neural Network, a Multi-Layer Perceptron (MLP).
4. The MLP will have one output, which will be a probability between {0, 1} on whether the e-mail is spam, ham (good e-mail), or mystery meat (unknown status).
5. Based off the output of the MLP, the e-mail will be moved to an appropriate mail corpus.

1. Process and parse both corpuses of e-mail into string tokens.
2. Look at the defined genetic markers within each e-mail, and generate two collections of statistics on each marker between {0, 1} for each message within each corpus. One collection will be for the spam corpus, and the other for the ham corpus.
3. Take each collection of statistics generated, and using gradient descent/back-propagation, train the MLP on each collection of statistics, with the desired output of the spam input vectors being 1, and the desired output of the ham input vectors being 0. Continue training until an acceptable mean-squared error (MSE) is reached.

Other features that should be considered in any implementation of this filter should be:

1. A sender white list and black list. If an e-mail is from someone or from some domain on the white list, it is automatically accepted as ham. If it is from someone on the black list, the inverse occurs and it is automatically rejected as spam. If the sender is on neither list, than the e-mail is processed through the above system.
2. A way that the user can augment sensitivities to the input vector of our MLP. For instance, say we parse an e-mail to see if it has HTML image links (this would be one of the genes we track). If it does contain an image link, we know that 99.9% of messages that contain this trait are spam. But, certain people may not want these e-mails categorized as spam, because they deal with good e-mail that contains image links. Giving the user the ability to inhibit this marker with a setting like “How often do you receive valid e-mail that contains images?” would serve well.
3. Because of the adaptive nature of spam, a central server that could deploy new filters on a day-to-day basis would be a must have. The filter described here will adapt on its own to the gene markers its familiar with, but not to new defensive gene markers that spammers will likely include down the road. It would make this system extremely efficient, and with wider use, make it cost prohibitive for spammers to continue their ways. In essence, we want this system to evolve as fast as spam.

Spam Gene Markers

1. Is the format of the e-mail HTML?
2. Is the e-mail formatted in valid HTML?
3. Is the e-mail encoding base64?
4. Does the e-mail contain image links?
5. Does the e-mail contain “hidden” text that the user cannot see?
6. Does this e-mail have a large number of recipients?
7. What’s the ratio of links to words in this e-mail?
8. What’s the ratio of misspelled words to words in this e-mail?
9. What’s the Bayesian spam probability of this e-mail?

Here’s an analysis of why I would consider these some of the top markers.

Is the format of the e-mail HTML?

Is the e-mail formatted in valid HTML?

Is the e-mail encoding base64?

Does the e-mail contain image links?

Does the e-mail contain “hidden” text that the user cannot see?

NOTE: Our filter will completely ignore these areas of hidden text, and look just at the message the user sees.

Does this e-mail have a large number of recipients?

What’s the ratio of links to words in this e-mail?

What’s the ratio of misspelled words to words in this e-mail?

What’s the Bayesian spam probability of this e-mail?

Now that we have defined what the overall process is going to look like, let’s delve into the code.

Putting it Together

NOTE: The sample code for this application is in C#. C# was chosen over C++ so beginners could better see the structures of the process, and C# was chosen over Java because of the inherent performance advantages of .NET. If anyone would like to re-factor the code into C++ or Java, please do and I will include it with the distribution of this article.

The namespace defined for our engine is SpamAwareLib. Its structure is as follows:

• SpamAwareLib
  • DataObjects
    • AddressList.cs - Represents collection of addresses and domains
    • Chromosome.cs - Collection of “genetic” traits regarding an e-mail
    • ChromosomeHistory.cs - Collection of chromosomes represents a history of chromosome data over time
    • Corpus.cs - Collection of mail tokens, the number of times each token has been encountered, and the number of messages that this corpus is based off of
    • Dictionary.cs - StringCollection of words that represent a dictionary; used for spell checking
    • Message.cs - Collection of data that represents a mail message
  • MsgProcessors
    • BayesianAnalyzer.cs - Computes a Bayesian probability if a message is spam from the body of the message, a ham corpus, and a spam corpus.
    • HTMLParser.cs - Simple HTML parser that scans a message for genetic traits specific to HTML messages
    • TokenParser.cs - Parsers a message in to string tokens, and posts the resulting tokens into a corpus and collection
  • NeuralNet
    • Neuron.cs - Neuron model for a Multi-Layer Perceptron
    • NNMLP.cs - Model for a simple Multi-Layer Perceptron
    • NNSpamAware.cs - ANN implementation of the MLP used for the spam engine
  • Utility
    • ChromosomeGen.cs - Factory that generates a Chromosome and/or executes it against the MLP
    • ANNTrainer.cs - Factory that generates our neural networks

To see a code representation of how the engine works, let’s take a look at the chromosome generator method GenerateChromosomeAndCheck.

public static Chromosome GenerateChromosomeAndCheck(Message msg, 
			Dictionary dict, 
			Corpus ham,
			Corpus spam,
			NNSpamAware net)
{
  string body = msg.Body;

  Chromosome stats = new Chromosome();
  
  body = body.ToLower();
  stats.IsHTML = 
    Chromosome.ConvertBoolToDouble(HTMLParser.IsHTML(body));
  stats.ContainsImgLinks = 
    Chromosome.ConvertBoolToDouble(HTMLParser.ContainsImgLinks(body));
  stats.IsValidHTMLBody = 
    Chromosome.ConvertBoolToDouble(HTMLParser.IsHTMLBodyValid(body));
  stats.ContainsHiddenText = 
    Chromosome.ConvertBoolToDouble(
      HTMLParser.ContainsInvisibleHTMLText(body));
  stats.LinkDegree = 
    Chromosome.CalcLinkDegree(HTMLParser.GetLinkCount(body));
  stats.RecipientDegree = 
    Chromosome.CalcRecipientDegree(msg.GetRecipients());

  // Run parts of chromosone against a pre-net
  // (This is an optimization)
  stats.SpamProbability = net.RunPreNet(stats);
			
  // This can be adjusted...  Calculating the misspelled word ratio and
  // any Bayesian probability is time consuming
  if (stats.SpamProbability < .66)
  {
    string parsedBody = "";

    if (stats.IsHTML > .5)
    {
      parsedBody = HTMLParser.CleanHTML(body);
    }
    else
    {
      parsedBody = body;
    }

    stats.MisspelledWordRatio = 
      TokenParser.GetMisspelledWordRatio(parsedBody, dict);
    stats.BayesianSpamProbability =	
      BayesianAnalyzer.CalcSpamProbabiliy( msg.Subject + 
                             " " + parsedBody, ham, spam );

    // Run full choromosone against a net (This is an optimization)
    stats.SpamProbability = net.RunFullNet(stats);
  }

  return stats;
}

NOTE: For further details on the implementation of the message processors (gene finders), please see the code attached to the project.

Training the Networks

public static NNSpamAware GenerateNetwork(Message [] hamMsgs, 
                                          Message [] spamMsgs,
			      Corpus hamCorpus, Corpus spamCorpus,
			ChromosomeHistory hist, Dictionary dict)
{			
// First, add the tokens of our messages to our corpuses
  for (int i = 0; i < hamMsgs.Length; i++)
  {
    TokenParser.AddMsgTokensToCorpus(hamMsgs[i].Subject, 
                                     hamMsgs[i].Body, hamCorpus);
  }

  for (int i = 0; i < spamMsgs.Length; i++)
  {
    TokenParser.AddMsgTokensToCorpus(spamMsgs[i].Subject, 
                                     spamMsgs[i].Body, spamCorpus);
  }

  // Generate the chromosomes for all the mail items
  for (int i = 0; i < hamMsgs.Length; i++)
  {
    Chromosome chromosome = 
          ChromosomeGen.GenerateChromosome(hamMsgs[i], 
                                           dict, hamCorpus,
                                           spamCorpus, 0);
   hist.AddChromosome(hamMsgs[i].Id.ToString(), chromosome);
  }

  for (int i = 0; i < spamMsgs.Length; i++)
  {
    Chromosome chromosome = 
          ChromosomeGen.GenerateChromosome(spamMsgs[i], 
                                           dict, hamCorpus, 
                                           spamCorpus, 1);
    hist.AddChromosome(spamMsgs[i].Id.ToString(), chromosome);
  }

  // Perform Network Training
  NNSpamAware ann = new NNSpamAware();

  // Train for 1,000 epochs.  A better method would be to look for an
  // acceptable MSE, but for simplicities sake, we train for a set 
  // number of epochs
  for (int epoch = 0; epoch < 1000; epoch ++)
  {
    for (int i = 0; i < hist.Count; i++)
    {
      ann.TrainPreNet(hist[i]);     // Train the pre Net
      ann.TrainFullNet(hist[i]);	// Train the full Net
    }
  }

  return ann;
}

Results

Conclusions

With that said, a sucker is born everyday, and certain individuals will purchase items from spammers no matter how shady or underhanded the promotion is. As long as these people continue to buy from spammers, and the cost of spamming does not escalate, spamming will continue.

To combat this problem, the “see-no-evil, buy-no-evil” approach can be taken. With this, vendors need to include EFFECTIVE anti-spam tools within their e-mail applications. And not just in new versions, but also through the development and deployment of service packs and free add-ons to existing and previous product lines. The more spam messages the user is oblivious to, the least likely he or she will partake in a spam promotion. This in turn makes spam less effective, significantly decreasing the return on investment of the practice, which will in turn greatly reduce it and/or kill it.

Last but not least, no single, elementary solution can be used to effectively filter and kill spam. It will take a solution that recognizes spam as an organism, and that can evolve as quickly as it can.

Contact Information

• SpamAwareLib.zip (1.3Mb)