君は春の中にいる、かけがえのない春の中にいる.

你驻足于春色中,于那独一无二的春色之中.

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

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

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。