Automatic Template Pattern Recognition

Spam se typicky nevyskytuje ve formě samostatných zpráv, ale často bývá sdružován do takzvaných kampaní. Ty bývají automaticky generovány pomocí šablon. Díky tomu jsou jednotlivé zprávy sémanticky, ale ne syntakticky, ekvivalentní. Cílem práce je navrhnout algoritmus schopný z množiny zpráv jedné kampaně zpětně extrahovat šablonu, ze které tyto zprávy byly generovány. Práce se zaměřuje na spam v SMS komunikaci, ale navržené postupy jsou dostatečně obecné pro širší použití. Algoritmus je postaven na metodě zarovnávání dvou sekvencí, používané v bioinformatice pro nalezení podobných oblastí proteinových řetězců. Výstupem je regulární výraz popisující šablonu dané kampaně. Součástí řešení je také nástroj pro vizualizaci šablony pomocí HTML.Řešení bylo ověřeno na přibližně třech stovkách skutečných kampaní z celého světa. V naprosté většině případů je poskytnutý výsledek postačující pro identifikaci kampaně.Spam does not occur as separate messages, but it is sent in so-called campaigns. They are usually generated by a certain template which allows producing large amount of semantically, but not syntactically, equivalent messages. The goal of this work is to design an algorithm able to reversely extract a template of a campaign from a set of concrete messages. The main focus is on spam in SMS communication. However, proposed method is general enough for wider use. The proposed algorithm is based on a method of aligning to sequences, which is used in bioinformatics to detect similar regions of protein strings. Resulting templates are represented as regular expressions. The tool is able to visualize extracted templates using HTML.Results of the tool were validated on more than three hundred real-world campaigns. In most cases extracted regular expressions were able to identify their source campaign.