Aussie researchers use game theory to crack spam

A group of Australian researchers has developed a new anti-spam model using repetitive game theory, which delivered a 30 percent improvement in classifying spam when compared with traditional spam filters over a period of 12 months.

The model, developed with the support of the Capital Markets Cooperative Research Centre (CMCRC), also has the potential to be applied to network security situations and in the detection of insurance fraud.

The research, published in the journal Machine Learning, was undertaken by University of Sydney pattern and data mining Professor Sanjay Chawla, CMCRC PhD candidate Fei Wang, and Wei Liu, also from the University of Sydney.

Chawla, whose research is focused on anomaly detection, said he wanted to bring in elements of game theory, with the notion of an adversary and strategic interaction, to traditional machine learning approaches to spam classification.

Game theory is a study of strategic decision making across a wide field of behavioural relations.

“We came up with a few models and we tested it on real spam data sets and it showed that the model that we built was more robust to changes,” Chawla said.

“Now we are trying to see if there is a way we can add some extra conditions, for example can we assume there is a finite budget that either the spammer or classifier has and they have to operate in that budget, so adding constraints into the model.”

Modelling the interaction between a spam classifier and an adversary as a repeated game theory setting is a far more realistic way of getting training data for the classifier because it allows for cause and effect behaviour to be captured, the CMCRC's Fei Wang said.

"We look for a compromise solution, or equilibrium, where no party wants to deviate from the situation they are in. The classifier is then trained using this equilibrium position. This approach is both more robust and economical than previous methods."

Chawla said the model could also be applied to other settings, such as network security, with network anomaly detection.

“We’re trying to figure out if there’s a way we can pinpoint different types of attack, like a denial of service. So we’re trying to come up with a unified approach.”

The theory, according to the CMCRC, is that the technique can be applied to many situations wherever there is some motivation for one party to get an advantage over another, taking game theory out of its traditional domain of economics and politics and applying it to computer science and data mining.