英文文献阅读-使用遗传算法的异常入侵检测

基于遗传算法进行入侵检测

0x01 算法基础

阅读的文献是CCSIT 2012的一篇论文

Srinivasa K G. Application of Genetic Algorithms for Detecting Anomaly in Network Intrusion Detection Systems

论文的核心部分是在GA算法本身的描述上，遗传算法主要是为了解决优化问题，正如它的名字，它模仿了自然界的生物遗传特性，首先提取个体的特征，也就是基因，进行杂交获取不同于父辈的基因，然后使用某种标度去计算子代是否是最优解，如果不是就再一次杂交迭代。

0x02 算法实现

在入侵检测方面，文章利用GA算法来产生特征组，GA算法的伪代码如下：

Input:
    x[i],代表i时刻的payload
Output:
    fittest,适当的基因
begin:
    for i in [0,G]:
        min_dist = INFINITY
        fittest = 0
        for c in Chromosome:
            dist = manhattan_dis(c,x[i])
            if dist <= min_dist:
                fittest = i
                min_dist = dist
        crossover(fittest,x[i])
        for c in Chromosome:
            mutation(c)

其中G是子代迭代次数，Chromosome是测试后适合加入种群的基因c的基因组，测量的标度是c和x的曼哈顿距离。

另外还有两个函数，杂交函数crossover和变异函数mutation。

如伪代码所表示的，在一次次的子代繁殖中，确定出当前的测量值dist，然后将子代与这一代的基因进行杂交，杂交后会产生新的基因组种群，为了快速探索到整个特征空间，引入变异函数来加快这一探索过程。

杂交函数伪代码如下：

Input:
    x[i]
    fittest 合适的基因
Output：
    子代及子代基因，如果满足条件，加入基因组
begin：
    Children[6] = Cross(fittest,x[i])
    杂交后产生的除去2个与父代相同的子代后剩下的6个子代（很拗口的一句话，总之就是2个父代——8个子代——减去2个子代=6个子代）
    for c in Children:
        if fitness(c) > threshold:大于临界值
            add_to_population(c)将该基因加入种群
    remove(fittest)移除父代

变异函数如下：

Input：
    c 基因组内基因
Output：
    c' 变异基因
begin：
    r = random()
    if r > pm(变异可能性):
        mutate(c)

生成一个随机数，如果它大于变异率，即变异发生。

当然，这里还有两个问题，杂交和变异到底如何表示，遗传学里的孟德尔的豌豆实验对于两组特征AaBb的豌豆杂交，产生多种基因组合的子代就是杂交，而变异就是一个子代本来是aabb，但是当变异发生，可能会成为Aabb。

上面是生物学的描述方法，那么在计算机中我们就可以用编码来描述基因，比如一个特征1的编码可以是0001,2编码为0010.那么每两个二进制的数位代表一个基因，1和2杂交可以产生出0000,0001，0010三种子代，当然如果等概率假设的话实际数目应该是4个子代，三种基因。那么，这时，如果产生变异，0010就有可能成为0011，以此类推。

而在这里，最后的基因组就是异常行为的特征值组。

0x03 疑惑

整个论文的核心其实就是上述的一整套算法，接着论文利用这套算法与另一篇论文中的PAYL进行对比，并最终得到结论，论文的算法拥有更高的检出率和更低的误报率，并且训练速度较快。

这里还有几点疑惑，首先，遗传算法重要的一个研究点就是如何定义基因，或者说是编码，而论文中并没有提出这种编码机制。其次，如果没理解错的话，文中的payload仅使用目标地址和目标端口，这种选取是否合适。另外，就是文中的伪代码描述也不是很清晰。

当然，这篇文章有可能是建立在其他GA-IDS文章的基础上所以省略了上述说明。

句式：

In our system we use a two point crossover scheme where the two parents crossover at two different points producing a total of eight off springs out of which two are replicas of the parents itself which are discarded.

好长的一段话，大意就是说这个两点杂交会产生8个子代，而和父代完全一样的两个子代会被丢弃。主句是we use a two point crossover scheme。where修饰前句，the two parents crossover producing a total of……，然后out of which two指代前面的offsprings，再下一个which修饰two。