The domain name systems (DNS) are nowadays frequently misused by a certain type of malware. For example, malware programs installed by attackers on a host computer try to use the DNS as a mean to establish connection with the Command and Control server in order to become a part of a botnet. The Command and Control server first registers a list of algorithmically generated domain names. The malware on an infected computer then queries the domain names generated by the same algorithm. The large number of generated domains prevents their manual detection. Examples of legitimate domain names and those generated by malware:

LEGITIMATE GENERATED
---------------- ------------------
google.com atqgkfauhuaufm.com
facebook.com vopydum.com
youtube.com jgiugobavtyfsck.biz
yahoo.com dhjopxgdetn.com
baidu.com hhjjqjghfir.com
wikipedia.org ldivjfkfamhnzjvbabqylvsij.info
qq.com towngwvyjaebrtp.com
amazon.com yyryxlgbgxsy.biz
live.com mpwnnvqmxtnkv.ru
... ...

Our goal will be to design a classifier able to distinguish the generated domain names from the legitimate ones automatically. We will learn such classifier from a training set of examples by the Support Vector Machine algorithm. The training setT ={(x^1 ,y^1 ),...,(xm,ym)} ∈ (X × {+1,− 1 })mis composed of pairs of domain names and their labels. The input space X= Σ∗contains all strings that can be generated from a finite alphabet Σ. The labely= + will denote a generated malicious domain name whiley=−1 will stand for a legitimate domain. We will represent the input strings by the String Sub-sequence Kernel (SSK) [3]. The SSK kq: Σ∗×Σ∗→Rcomputes a dot product,kq(x,x′) =〈φ(x),φ(x′)〉, between two input strings embedded to a feature space via the mapφ: Σ∗→R|Σ| q

. The SSK compares two strings by means of the substrings of lengthqthat may not be contiguous. The more substrings the input strings have in common, the more similar they are. The kernel is constructed such that less contiguous substrings contribute with less weight to the overall string similarity. The formal definition of the SSK is described in more details below. This computer lab has been motivated by the paper [2].

[1] Chang Chih-Chung and Lin Chih-Jen. Libsvm: http://www.csie.ntu.edu.tw/~cjlin/ libsvm/.

[2] Haddadi F. and Zincir-Heywood A.N. Analyzing string format-based classifiers for botnet detection: GP and SVM. InIEEE Congress on evolutionary Computation, 2013.

[3] Lodhi H., Saunders C., Shawe-Taylor J., Cristianini N., and Watkins C. Text classification using string kernels.Journal of Machine Learning Research, 2002.