（计算机应用技术专业论文）分布式网络安全漏洞扫描系统中扫描任务调度的研究.pdf

1 一 声明尸明 i i i ii iif l lll fi i iir illf 17 8 6 0 8 7 本人郑重声明：此处所提交的硕士学位论文 o ( 2 3 ) v = l v = l 其中，i 【1 ，k 】，【1 ，丹】；t o ( 日) 表示在扫描服务器i 上对目标主机执行扫描 策略所需的时间。 m 同一扫描任务集中的子任务执行的扫描策略都是相同的，即，都是相同的， v = l 因此可用一个常整数z 代替，则子任务的执行时间可简化为： 岛( 开) = 以玎，五 0 且i 1 ，k 】， 1 ，z ( 2 - 4 ) 在确定扫描任务集的调度方案时可用矩阵哌。描述，它的每一个元素 w , a = j ( i 1 ，尼】，- ，【1 ，珂】) ，j 代表一个子任务的编号，表示第j 个子任务将在第f 个结 l o 叱如 的扫描子任 描任务集在 全部子任务 ( 2 5 ) 的时间。而 服务器上。 s _ ，之前已分 ( 2 - 6 ) ( 2 - 7 ) ( 2 - 8 ) 本章简述了分布式漏洞扫描系统的特点，对漏洞的概念、分类、命名标准以及 漏洞数据库做了简要介绍。同时介绍了漏洞扫描技术的分类、方法以及未来的发展 趋势。研究了任务调度的技术，对任务调度的几种经典的算法做了理论分析，其中 有m i n - m i n 算法、m a x - m i n 算法、先进先出调度算法、s u f f e r a g e 算法以及模拟退火 算法。给出了任务调度问题的一般模型，并建立了分布式漏洞扫描任务调度的调度 模型。、 华北电力大学硕士学位论文 第三章基于遗传算法的分布式漏洞扫描任务调度方法研究 随着模拟退火、遗传算法等现代优化算法研究的逐渐兴起，用遗传算法解决任 务调度问题的研究也在进行，并且显示了强大的优越性。本文针对分布式漏洞扫描 任务调度的特点，对遗传算法参数进行相应的设计，设计了基于遗传算法的分布式 漏洞扫描任务调度算法g a t s 。 3 1 遗传算法的基本原理 遗传算法的基本思想是基于d a r w i n 的进化论和m e n d e l 的遗传学说。该算法由密 执安( m i c h i g a n ) 大学教授j o h nh o l l a n d 及其同事、学生们于1 9 7 5 年创建【3 6 1 。此后，遗 传算法的研究引起了国内外学者的关注。自1 9 8 5 年以来，国际上已召开了多次遗传 算法的学术会议和研讨会，为研究和应用遗传算法提供了国际交流的机会。目前， 遗传算法已被成功应用在机器学习、过程控制、经济预测、工程优化等领域。作为 一种通用的问题求解方法，遗传算法采用简单的编码技术来表示各种复杂的结构， 并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和 确定搜索的方向。 作为一种通用的问题求解方法，遗传算法采用简单的编码技术来表示各种复杂 的结构，并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导 学习和确定搜索的方向。 遗传算法是一个以适应度函数为依据，通过对群体个体施加遗传操作，实现群 体内个体结构重组的迭代处理过程【3 7 1 。主要包括五个基本要素：染色体编码、初始 化种群、适应度函数、遗传操作、相关运行参数与进化停止准则。下面针对这五个 基本要素介绍遗传算法的基本原理。 ( 1 ) 染色体编码 使用遗传算法时，需要把优化问题的每一个解的参数形式转换成基因位串的表 现形式，这一转换操作称作编码。其中码串中的每一位代表一个基因，一个基因位 串就代表问题的一个解，每个基因位串称为一个个体，或称为染色体。最常见的编 码方法是以h o l l a n d 为代表的二进制编码。 二进制编码使用的编码符号集是由o 和l 组成，将原问题的解映射为0 、1 组 成的位串，然后在位串空间上进行遗传操作，这种编码方法的优点是编码、解码操 作简单，交叉、变异等遗传操作易于实现，而且便于利用模式定理给予理论分析。 同时，二进制编码也存在一些缺点：首先，二进制编码的精度不高；其次，若为提 高精度而使个体编码串长度增加，也会加大算法的搜索空间，使得算法效率低下【3 引。 华北电力大学硕士学位论文 ( 2 ) 初始化种群 遗传算法是基于种群寻优的方法，算法运行时是以一个种群在搜索空间中进行 搜索，一般采用随机方法生成一个初始种群，也可以使用其它方法构造一个初始种 群。 ( 3 ) 适应度函数 遗传算法中的适应度函数表示种群中每个个体对生存环境的适应能力，每个个 体都具有一个适应值，适应值是个体生存机会的唯一确定性指标。适应度函数基本 上依据优化的目标函数来确定。为了能够直接将适应度函数与群体中的个体优劣相 联系，适应值规定为非负，并且在任何情况下总是希望越大越好。适应度函数的选 取至关重要，直接影响到遗传算法的收敛速度以及能否找到最优解。一般而言，适 应度函数是由目标函数变换而成的【3 9 1 。 在设计遗传算法时，如果群体中出现了超级个体，即该个体的适应值远远超过 群体的平均适应值，则按照适应值比例进行选择时，该个体很快就会在群体中占有 绝对的比例。从而导致算法较早地收敛到一个局部最优点，这种现象称为过早收敛 ( p r e m a t u r ec o n v e r g e n c e ) 。又如在搜索过程的后期，虽然群体中存在足够的多样性， 但群体的平均适应值可能会接近群体的最优适应值。在这种情况下，群体中实际上 已不存在竞争，从而搜索目标也难以得到改善，这种现象我们称之为停滞现象 ( s t a g n a t i o n ) 。基于上述原因，改变算法性能的方法之一是对适应值要进行调节。 ( 4 ) 遗传操作 遗传操作主要包括选择、交叉和变异，它们构成了遗传算法的主体。 1 ) 选择操作 从群体中选择优胜个体，淘汰劣质个体的操作叫选择。选择的目的是为了从当 前群体中选出优良的个体，使他们有机会作为父代繁殖下一代子孙。判断个体优良 与否的标准是他们的适应值。如基本遗传算法采用的是轮盘赌选择法，它的基本思 想是根据各染色体适应值大小与全体染色体适应值之和的比值，确定各染色体被选 择进入下一代的概率【4 0 1 。 从遗传算法( g a ) 的整个选择策略来讲，精英选择是群体收敛到优化问题最优解 的一种基本保障。如果下一代群体的最佳个体适应值小于当前群体最佳个体的适应 值，则将当前群体最佳个体或适应值大于下一代最佳个体适应值的多个个体直接复 制到下一代，随机替代或替代最差的下一代群体中相应数量的个体。本文采用精英 选择策略。 2 ) 交叉操作 交叉运算是最重要的遗传操作，种群通过交叉产生新的染色体，从而不断扩展 华北电力大学硕士学位论文 搜索空间，最终达到全局搜索的目的。遗传算法通过选择和交叉操作产生平均适应 值更高、更好的子代种群，使进化过程朝更优解的方向进行。 基本遗传算法中的交叉操作采用单点交叉，它是由h o l l a n d 提出的最基本的一 种交叉方式。具体的操作为：在双亲的染色体串上随机确定一个交叉点，交换两个 个体在所设定的两个交叉点之间的部分染色体。 3 ) 变异操作 变异是一种重要的遗传机制。变异操作具有补偿群体多样性损失的重要作用， 变异本身是一种局部随机搜索，它与选择、交叉操作结合在一起，保证了遗传算法 的有效性，使遗传算法具有很好的全局搜索能力，保证了种群的多样性，防止早熟。 变异操作对于种群产生新个体来说是起辅助作用的。 基本遗传算法中的变异操作采用的是基本位变异，它以很小的变异概率p 。随机 地改变染色体中某一位或某几位的基因值，对于二进制编码的染色体来说，就是将 某基因位的0 变为1 或是将1 变为0 。 ( 5 ) 相关运行参数与进化停止准则 遗传算法需要设定的运行参数包括群体规模m 、交叉概率见、变异概率p 。、 进化停止准则等。这几个参数对遗传算法的运行性能有很大的影响，必须谨慎设定。 1 ) 群体规模m ：表示群体中所含个体的数量。当m 取值较小时，可以提高遗 传算法的运算速度，但降低了群体的多样性，有可能会引起遗传算法的“早熟； 当肘取值较大时，会使遗传算法的运行效率降低。 2 ) 交叉概率以：交叉操作是遗传算法中产生新个体的主要方法，所以交叉概 率一般应取较大的值。但若取值过大，它又会破坏群体中的优良模式，使算法过早 收敛；若取值过小，产生新个体的速度又较慢。 3 ) 变异概率a ：若取值太小，则变异操作产生新个体的能力和抑制早熟的 能力会较差；若p 。取值较大，能够产生较多的新个体，但有可能破坏很多较好的模 式，使得遗传算法蜕变成随机搜索算法。 4 ) 进化停止准则一般使用终止代数r 作为参数，终止代数丁表示遗传算法到指 定的进化代数之后停止运行，并将当前群体中的最佳个体作为所求问题的最优解输 出。遗传算法的终止条件还可以利用其它判定准则。 遗传算法的流程图如图3 1 所示。 华北电力大学硕士学位论文 3 2g a - t s 算法的设计 图3 1 遗传算法流程图 针对分布式漏洞扫描任务调度问题，对遗传算法在染色体编码、初始种群生成、交 叉操作及变异操作四个方面进行相应的设计。 3 2 1 染色体编码方式的设计 标准遗传算法采用二进制0 、1 编码方式，将问题的一个解表示成一个长度为l 的二进制串，作为一个个体。采用二进制编码的优点在于编码、解码操作简单，交 叉、变异等遗传操作便于实现。但缺点在于： ( 1 ) 二进制编码时，一般要先给出求解精度以确定串长，而精度确定后，就很 难在算法执行过程中进行调整，从而使算法缺乏微调的功能。若在算法一开始就选 取较高的精度，那么串长就很大，这样也将降低算法的效率。 ( 2 ) 在求解高维化问题时，二进制编码串将非常长，从而使得算法的搜索效率 降低。 本文根据任务调度的特点，使用的是一维十进制分离编码方式( o n e d i m e n s i o n d e c i m a ls e p a r a t i o nc o d i n g ，o d s c ) ，这种编码方式可以唯一地表示所有搜索空间中 华北电力大学硕士学位论文 的结点。 具体的编码步骤为： ( 1 ) 让一个染色体由一个分配子串和一个调度子串组成，两个子串按照不同的 方法进行编码、交叉和变异。 ( 2 ) 解的编码形式用一个一维的字符串表示，其中，前半部分( 即左子串) 称为分 配子串，表示任务分配情况，其任一位l i = a 表示任务正分配到资源只上：后半部 分( 即右子串) 称为调度子串，表示任务调度约束，r = b 说明瓦的前趋任务必定排在 第f 位置。 算例2 - l 】： 在图2 2 中，任务分布方案a 假设为： 一露：五一瓦一五 昱：夏一互一互 则解a 对应的一维编码形式可以是： 1 2 2 1 2 11 4 2 3 5 6 因为石，瓦，瓦分配在资源曰上，所以左子串的第1 ，4 ，6 位取值为1 ；五，互， 不分配在资源b 上，所以左子串的第2 ，3 ，5 位取值为2 。因为子任务的执行顺序 要求互在互之前，正在瓦之前，正在乃之前，乃在乃之前，所以1 4 2 3 5 6 就是一个可 行的染色体形式。 十进制编码的优点在于： ( 1 ) 十进制有很大的值域，而且具有相当高的精度； ( 2 ) 改善了遗传算法的计算复杂性，提高了运算效率； ( 3 ) 便于遗传算法与经典优化方法的混合使用。 3 2 2 初始种群生成方法的设计 标准遗传算法中的初始种群是随机产生的。也可以通过设定某种具体的方法来 产生初始种群，本文依据分布式漏洞扫描任务调度的特点，设计了初始种群的生成 方法。 首先，定义d a g 图中结点的高度值，一方面是为调度合法性提供一种判别依 据；另一方面就是为了初始群体的生成服务。 初始种群的生成方法描述如下：将d a g 图中的所有结点集合按高度值划分成 v a l u e h + 1 个子集d a g ( i ) ，0 f v a l u eh 。其中，v a l u eh 是d a g 图中最大的 高度值。对于染色体的左子串，由于其任一位厶= a 表示霉分配到只上，所以生成 华北电力大学硕士学位论文 初始种群左子串的方法是：在l 到n 的每一位随机产生一个 1 ，m 】的随机数。其含义 是将任务随机地分配给一个资源。对于染色体的右子串，由于必须满足任务的前趋 后继约束关系，所以要保证生成的染色体代表能够合法调度。 设种群规模为m ，子任务集为s ，s 集合的个数为n ，瓯表示高度值为h 的子 任务集，扫描器集合为p ，扫描服务器的数量为m 。则生成初始种群的算法( i n i t i a l p o p u l a t i o na l g o r i t h m ，i p - a ) 如下： 输入：初始种群规模，子任务集，扫描任务集 输出：生成的初始种群 步骤： ( 1 ) c o u n t = 0 ；h = 0 ； ( 2 ) 随机产生n 个i 1 ，册】之间的整数，将这n 个数连接起来组成分配子串； ( 3 ) 若h = v a l u e h + i ，则表明调度子串已经生成，转( 6 ) ； ( 4 ) 从最中随机抽取一个任务号，直至该集合为空。将这些子任务号按 抽取的先后顺序排列起来； ( 5 ) h + + ；转( 3 ) ； ( 6 ) 将这些子任务排列所组成的串置于( 2 ) 形成的分配子串之后，形成一个 染色体； ( 7 ) c o u n t + + ；若c o u n t m ，则转到( 2 ) ； ( 8 ) e n d 算例2 - 2 】： 以图2 - 2 为例。假设有两个资源，下面五和五是用该算法可能产生的两个解： 五2 1 2 2 1 2 1 1 4 2 3 5 6 五2 1 1 2 1 2 2 2 1 3 4 5 6 则它们对应的分配方案4 和4 分别是： 44 一 日f 。五年五一瓦日：疋一墨一互 昱：互一互一霉最：互一巧一瓦 由【算例2 2 】可知，按此方法生成的染色体串满足d a g 图中任务的前趋后继约束 关系。 华北电力大学硕士学位论文 3 2 3 交叉方法的设计 在对遗传算法的设计中为了保证交叉后生成的新个体仍然是可行解，设计了如 下交叉操作方法：将分配子串和调度子串采用不同的交叉方法进行交叉。 ( 1 ) 分配子串采用经典的单点交叉方法。即等概率地随机确定一个基因位置作 为交叉点，实行交换时，该交叉点后的两个个体的部分结构互换，形成两个新个体。 ( 2 ) 调度子串交叉方法( s c h e d u l es u b s t r i n gc r o s s o v e rm e t h o d ，s s c m ) 是：随机选 一个交叉点，。令交叉点前的基因不变，后面的基因按它们在交配对方的排列顺序重 新进行排列。 算例2 - 3 】： 染色体x 与x ：交叉，交叉点选在第三位和第九位。 五4 0 7 l3 0 6 3 5 4 i8 9 7 x 2 1 2 4 l 8 1 3 7 8 9 l 2 0 1 则交叉的结果为： ， 五4 0 7 l8 13 3 5 4 l7 8 9 ， x 2 1 2 4 l 3 0 62 0 1l8 9 7 五是这样产生的：对于五的分配子串，交叉点前的基因是五对应位的基因， 交叉后的基因是x ：对应位的基因；对于x ，的调度子串，杂交点前的基因是彳，对应 位的基因，交叉后的基因是将x 。的交叉点后的基因8 ，9 ，7 按照它们在x ：中的先 后顺序( 7 ，8 ，9 ) 重新排列。 可以看出，在分配子串，交叉母体中的一方采纳了另一方的新基因；在调度子 串，一方的基因值不变，只采纳了另一方的排列顺序。这样做可使调度子串不违反 前趋后继的约束，按此方法交叉后形成的新染色体仍然保持前趋后继关系，因而是 可行解。 3 2 4 变异方法( m u r a tio nm e t h o d m m ) 的设计 在进化过程中，一般需要在初期提高模式的重组能力，加大编码空间探索的广 度，以便找到最优解所在的子空间，跳出局部极值点。在后期，希望提高模式的生 存能力，以便在最优解子空间上逐步求精。从理论上来讲，采用随着群体进化而变 的变异概率，从某种程度上也可以取得类似效果，但是实际操作控制要复杂的多。 在本论文中，以变异概率己将所选个体位取反，这里变异算子实质上就是将某 个子任务迁移到另一个资源上执行。为了防止某个子任务在迁移后，执行的时间增 大而造成种群退化，规定迁移后子任务占用的资源不是随机产生，而是在除了该子 华北电力大学硕士学位论文 任务目前占用的资源外的资源集合中，选择使该子任务执行时间最短的资源，将其 迁移到该资源上执行。 分配子串与调度子串的变异操作也有所不同。描述如下： ( 1 ) 分配子串：随机选择一个变异位i ( i 【1 ，研】) ，将该位上的资源随机换为另一 资源； ( 2 ) 调度子串：对于随机选择的一个变异位，让该基因位代表的任务在其前驱 结点和后继结点间迁移，以确保迁移后得到的解仍然是可行解。 【算例2 - 4 - 以图2 2 为例。染色体x = 1 2 2 1 2 11 4 2 3 6 5 ，假设分配子串与调度子串的变异 位分别为i = 5 和i = 1 0 ，则变异后的染色体x 。= 1 2 2 11 1 1 4 2 6 3 5 。 x 是这样产生的：对于分配子串，变异位在第五位，将第五位的l 变异位2 ； 对于调度子串，变异位在第l o 位，而第l o 位对应的任务正的前驱结