一种基于免疫的计算机病毒检测方法

一种基于免疫的计算机病毒检测 陈 桓 , 刘晓洁 , 宋 程 , 梁可心 () 四川大学 计算机系 , 四川 成都 610065 摘 要 : 提出了一种基于人工免疫的病毒检测方法 ,给出了计算机软件系统中自体 、非自体 、抗原 、免疫细胞等 的表示方法 ,实现了否定选择和克隆选择等免疫机制 。通过实验测试了该方法的识别能力 、错误否定率和错误 肯定率 ,结果表明该方法具有自适应 、自学习和多样性等特点 ,能够有效地检测未知计算机病毒 。 关键词 : 计算机病毒检测 ; 人工免疫系统 ; 否定选择 ; 克隆选择 ( ) 中图法分类号 : TP30912 文章编号 : 100123695 200509 20111 202 文献标识码 : A A n Imm une2ba sed M e thod fo r V iru s D e tec tion CH EN H uan, L IU X iao2jie, SON G Cheng, L IAN G Ke2xin ()D ept. of Com pu ter S cience, S ichuan U n iversity, C hengdu S ichuan 610065, Ch ina A b stra c t: A n imm une2ba sed m e thod fo r viru s de tec tion is p ropo sed in th is p ap e r. The fo rm a l defin ition s of se lf, non se lf, an2 tigen, an tibody, imm unocyte in comp u te r softwa re system a re p re sen ted. Som e imm une m echan ism , such a s nega tive se lec tion and c lone se lec tion, a re imp lem en ted. Exp e rim en ts a re done to te st the de tec tion ab ility, fa lse2nega tive ra te and fa lse2po sitive ra te of the m e thod. R e su lt show s tha t th is m e thod ha s the fea tu re s of se lf2adap ta tion, se lf2lea rn ing, d ive rsity, can de tec t know and unknow comp u te r viru s effec tive ly. Key word s: Comp u te r V iru s D e tec tion; A rtific ia l Imm une System; N ega tive Se lec tion; C lone Se lec tion 计算机病毒检测研究一直是计算机安全技术领域的一个义自体集 S 为正常程序代码集合 , S Α U; 非自体 T 为病毒程序 [ 1 ] 研究热点 。传统的 计 算 机 病 毒 检 测 技 术 都 存 在 各 自 的 缺 代码集合 , T Α U , 满足 S ?T = <, S ?T = U。定义抗原 A g< U。[ 2 ] 24 陷 :特征码扫描法不能检测未知计算机病毒 ; 校验和法与行 i 定义免疫细胞集合 B = { b | b? Y G } ,即免疫细胞用长度i = 16 为监控法有很高的误别率 ,并且很难区分病毒的类型 。同时这 在 16位到 24位之间的十六进制的病毒特征码定义 。免疫细 些传统的病毒防御技术很难对病毒进行实时的防御 。随着计胞集合又可以分成未成熟免疫细胞 、成熟免疫细胞和记忆免疫 算机病毒产生速度的不断加快 ,传播速度更加便捷和迅速 ,传 细胞 。未成 熟 免 疫 细 胞 是 刚 生 成 还 没 有 通 过 否 定 选 择 过 程 统的计算机检测技术已经无法有效防御计算机病毒 。对未知 (( ) ) 如式 3 的免疫细胞 ,某个未成熟免疫细胞成功通过否定选计算机病毒的实时防御 ,在保持检测能力的同时降低错误率是 择过程就成为一个成熟免疫细胞 ,而成熟免疫细胞被激活后就 目前需要迫切解决的问题 。进化成记忆免疫细胞 。 ( ) 计算机病毒防御问题与生 物免疫系统 B IS所遇 到的问 ( ) ( ) 定义匹配函数 fx, y x, y?U : m a tch 题非常相似 ,都需要在不断变化的环境中保持系统的稳定性和 ( ) ( ) β1, fx, y/m in l, l? h_d is x y ( )( ) 1 fx, y= 高效性 。B IS具 有 多 样 性 、耐 受 性 、免 疫 记 忆 、分 布 式 并 行 处m a tch 0 , o the rw ise 理 、自组织 、自学习 、自适应和鲁棒性等良好的特点 。基于人工 ( ) ( ) 其中 l, l是 x与 y长度 , fx, y x, y ?U 是 x 与 y 之间的 x y h_d is 免疫的计算机安全技术能够弥补现有技术的一些缺陷 ,是非常 β 广义海明距离 ,是门限比例 :[ 3,5 ] 有意义的研究方向 。( )( ) ()2 fx, y= m ax m , m , , m h_1 2 | l- l is | + 1 x y d ( )m in l, l xy1 计算机病毒免疫系统 δ其中 m = 6, it i t = 1 在计算机软件系统中所有的信息最终都可以还原为一个 1, x= y? l< l i i + t - 1 x yδ 二进制串 ,所以实际上计算机病毒检测问题就是一个根据一定 1, y= x? l? l, 1 ? i? | l- l| + 1 i i + t - 1 x y x y =it 的规则和先验知识来分类二进制串的问题 。 0 , o the rw ise 1. 1 免疫组件定义 1. 2 免疫机制的实现 + ? i 系统主要采用的免疫机 制有否定选择机制 、克 隆 选 择 机 定义计算机病毒检测问题的状态空间 U = Y G, 其中 G =i = 1 制 。否定选择过程就是免疫细胞的自体耐受过程 :保证参与检 ) ({ 0, 1 , , 9 , A , , F} 二进制串与十六进制串是等价的 。定 测的免疫细胞在病毒检测中不把正常的程序识别成病毒 。免 ( )疫细胞集合的自体耐受过程用式 3 定义 :消除免疫细胞集合 收稿日期 : 2004208228; 修返日期 : 2004210213 中所有识别自体的检测细胞 。 ( ) 基金项目 : 国家自然科学基金资助项目 60373110 ; 教育部博 ( )() ( ) 3 ( f B = B - { d | d ?B ?ϖ y?S fd, y= 1 } ( )士点基金资助项目 200306100003 tolerance t t t m a tch ) β:算法如下 试验中已知病毒和未知病毒的比例是 1 ?1 , 虽然 的增大会 使错误否定率上升 , 但是不会超过 50% 。在实际情况中 , 一台 p rocedu re clone_ se lec tion { 固定主机的某个时刻的未知病毒与已知病毒的比例是非常小 置初始检测细胞集合 B; / 3 置为 Bm 3 / (wh ile B 中的所有检测细胞都不能识别病毒且克隆选择的轮数小 β的一个数值 , 在这种情况下 , 对系统的错误肯定率的影响会 ) 于 r{ β大大降低 。所以 对系统的识别能力和错误否定率影响较强 , 计算所有免疫细胞与病毒的亲和力 ; β在实际情况下错误否定率是优先考虑的性能 , 所以 的取 λ选择亲和力高于 一个子集 ; s 根据亲和力克隆这个免疫细胞子集形成 B; 1 值大于 0. 8是较为合理的选择 。根据亲和力变异 B中的免疫细胞 ; 1 ( )随机产生 | B | 个新的免疫细胞加入到 B中 ; 1 对 B进行自体耐受处理 ; / 3 耐受 3 / 1 置 B 为新的免疫细胞集合 B; 1 (} / 3 end of wh ile3 / if 识别) 病毒 保存识别病毒的免疫细胞 D; else 无法通过自体耐受 ,没有病毒 ,结束病毒检测 ; } / 3 end of p rocedu re3 / 3 θ ( ) 其中某个免疫细胞 b的克隆数目 n= [fb, v/ l], 其中 b h_d is b ( ) β 2/B /的大小对系统的影 响 。另外两 个 参 数 固 定 = m θv为正在被检测的病毒 ,是克隆数目的上限值 , l为 b串长 , b 018 , / S / = 100如图 2 所示 。从图 2 中 可 以 看 出 , 当 /B/的 值 m ( ) fb, v为 b和 v之间的广义海明距离 。对免疫细胞 b的变 h_d is 为 0时模型的错误否定率几乎达到了 100 % ,而识别能力几乎 ( ( ) ) 异就是把 b中随机选取的 l- fb, v位字符用随机选取 b h_d is 为 0。但是随着记忆免疫细胞集合的增大系统的总体识别能 的十六进制字符代替 。 力以及对未知病毒的识别能力都显著增加 ,并且几乎可以识别 该系统通过记忆免疫细胞集合检测已知病毒 ,通过克隆选所有的变种病毒 。当 /B/的大小达到 90 时 ,系统就可以识别 m 择过程学习识别未知病毒 ,在克隆选择过程中通过否定选择算 ( ) 所有的 200个病毒 100个原病毒 , 100个变种 ,即能够识别几法来保证系统不会识别自体 ,通过变异记忆免疫细胞和随机生 (乎所有变种病毒和占总病毒 10 %左右的新病毒 不包括变种 成来产生新的免疫细胞 。病毒识别算法如下 : ) 病毒 ,说明 /B/的大小对系统的识别能力和错误否定率具有 m p rocedu re de tect_algo rithm 极强的影响 ,记忆免疫细胞集合的大小几乎决定了系统的识别{ 初始参数设定 ; 读取自体集合 S; 能力 。这是因为在系统中对已知病毒的识别能力由记忆免疫 初始化记忆免疫细胞集合 B; m 细胞集合直接决定 ,而对未知病毒的识别能力由记忆免疫细胞 读可疑样本文件 F用于识别 ; / 3 取样本 3 / ()if B中的某个免疫细胞 D 识别 F中的病毒 变异以及免疫细胞随机生成来完成 ,记忆免疫细胞的多少之间m 已知病毒 ,检测完成 ; (决定了变异出来的免疫细胞的好坏 记忆免疫细胞越多 ,越能 else { / 3 未知病毒 ,调用克隆选择过程识别 3 / ) 够生成有效的新免疫细胞 。这表明该系 统具有很强的自学 调用 c lone_ se lec tion算法学习识别 ; 把识别病毒的新免疫细胞 D 存入记忆检测细胞集合 B中 ; / 3 免 m 习 、自适应能力 ,并具有动态调节和多样性等特点 。实际使用 疫记忆 3 / 中初始的记忆免疫细胞集合可以用现有的病毒特征码进行初/ 3 end of e lse3 / } 始化 ,那么系统在开始就具有非常好的识别未知病毒的能力 。/ 3 end of p rocedu re3 / } (λβ) λ其中 是克隆选择门限值 <。 s s 2 实验结果 实验主要测试初始记忆免疫细胞集 合的大小 /B/ , 自体 m β集合的大小 / S /以及匹配的门限比例 的取值对系统 的识别 能力 、错误否定率和错误肯定率的影响 。通过测试这些参数调 节对系统识别能力的影响来论证系统的一些优良特点 。 实验中使用的自体是 从 200 个 重 要 的 系 统 文 件 , 使 用 了 ( ) β 3/S /的大 小 对 系 统 的 影 响 。另 外 两 个 参 数 = 0. 8, ( 100个计算 机 病 毒 , 其 中 包 括 一 些 经 典 的 DO S 病 毒 P IN G2 /B/ = 50如图 3 所 示 。自 体 集 合 的 大 小 对 系 统 的 识 别 能 力m )() PON G病毒 以及一些比较新的病毒 如 C IH 病毒 ,使用的抗 () 能够略微提高 和错误否定率影响不大 ,但是对错误肯定率 ()原集合 检测的对象 是 200 个自体文件与 200 个感染了实验 有极大的影响 ,自体集合越大错误肯定率越低 。同时从图 3 还 (中使用的病毒的样本文件 其中每个使用的病毒有对 应的两 可以看出 ,要对 200个自体耐受并不需要完全的 200 个完备的 个样本 ,一个是原病毒感染后形成的样本 ,一个是该病毒的变 自体 ,这说明在实际可行的中仅仅需要维持一部分较典型 ) λβ θ 种感染产生的样本 。实验中取 = 10,=×0. 5。s 的自体集合就能达到对绝大多数自体耐受的效果 ,同时说明即 ( )β 1 对系统的影响 。另外两个参数固定 /B/ = 50, / S / =m 使自体集合发生一些错误 ,系统还是能够较好的工作 ,具有一 )β 100如图 1所示 。这两个图说明 的值越小系统的识别能力定的容错能力 。() 下转第 114 页 ev a ( 当用户支付商家电子现金时 ,商家验证 v和 t?H g‖ 1 参考文献 : a ) ) gmod n, 如果正确 , 接着通过第 2节提到的零知识交互 2 1B lind Signa tu re fo r U n traceab le Paym en ts[ C ]. A dvance s in D Chaum[ 1 ] a a C ryp to logy2C ryp to’82 , 19831199 2203.g, g的正确性 , 从而验证用户是否为货币的真正所有者 。若 1 2 [ 2 ] D Chaum , A F ia t, M N ao r. U n traceab le E lec tron ic Ca sh [ C ]. A d2 验证通过 , 商家向银行求证 , 有关 v的电子现金的余额或是否 () vances in C ryp to logy2C ryp to’88 LNCS 403 , 1990. 319 23271二次花费以及是否过期以及使用次数 。银行通过验证 , 在商家 [ 3 ] J K L iu, V K W ei, S H W ong. R ecove rab le and U n traceab le E2ca sh 的账户中注入相当的钱数 , 并且银行在自己保存的数据库中记 [ C ]. EUROCON ’2001 , Trend s in Comm un ica tion s, In te rna tional 录这次交易完成 。Confe rence on, vo lum e 1 , 2001. [ 4 ] Jen s Bo F riis. D igica sh Imp lem en ta tion [ EB /OL ]. h ttp: / / bofriis. 4 新的电子现金性质 dk / secu rity / d igica sh_ imp lem en ta tion. p df, 2003 206. [ 5 ] P L Yu, C L L e i. A n U ser Effic ien t Fair E2ca sh Schem e w ith A nony2 ( )1 强安全保护 mou s Ce rtifica tes [ C ]. E lec trica l and E lec tron ic Techno logy, 2001 , 新协议保证了只有真正的现金私有者才能使用电子现金 ,TENCON , P roceed ings of IEEE R egion 10 In te rna tiona l Confe rence 任何人包括商家和银行都不能使用该电子现金 ,因为由零知识 on, vo l. 1 , 2001. 证明是一个挑战应答机制 ,只有现金的真正所有人即现金的取 [ 6 ] T O kamo to, K O h ta. U n ive rsa l E lec tron ic Ca sh [ C ]. A dvance s in α() 款人才知道 ,完成零知识证明 。商家和银行也不可能二次花 C ryp to logy 2 C ryp to’91 LNCS 576 , 1992. 324 2337. [ 7 ] M A be, E Fu jisak i. How to D a te B lind Signa tu res [ C ]. A dvances in 费电子现金 。这 样电子现金即使被盗 、丢失等也不会 带来 损 () C ryp to logy 2A S IACR YPT’96 LNCS 1163 , 1996. 244 2251. 失 ,而且即使银行内部人员犯错 ,也不能花费该电子现金 。[ 8 ] Ronggong Song, L a rry Ko rba. How to M ake E2ca sh w ith Non2R ep ud i2 ( ) 2 强私有保护a tion and A nonym ity[ C ] 1P roceed ings of the In ternationa l Confe rence 由于该现金基于部分盲签名和零知识证明 ,商家和银行都 ( ) on Info rm a tion Techno logy: Cod ing and Comp u ting ITCC ’04 ,不能知道用户的真正身份 ,保证了用户的私有性 。 20041 ( ) 3 非否认性[ 9 ] D Chaum , T P Pede rsen. W alle t D a taba se s w ith O b serve rs [ C ]. A d2 如果交易过程中出现了问题 ,或者非法交易等 ,用户不能 vances in C ryp to logy2C ryp to’92 , L ectu re No te s in Comp u te r Sc ience, vo l. 740 , Sp ringe r2V e rlag, 1993. 89 2105. 否认它使用了该电子现金 ,因为只有用户的所有者才能完成零 作者简介 : 知识证明 。该现金具有不可否认性 ,能避免洗钱等非法交易 。( ) 蔡满春 1972 2,男 ,河北保定人 , 博士生 , 主要研究方向为密码学 、网 ( ) 络安全 、电子商务 ;杨成 1974 2,男 ,山东潍坊人 , 博士生 ,主要研究方 5 结论和进一步研究的问题 ( ) 向为密码学 、信息隐藏 、数字水印 ; 赵海洋 1978 2,男 , 山东潍坊人 ,博 ( ) 士生 ,主要研究方向为网络通信 、密码学与信息安全 ; 杨义先 1961 2, 本文在基于部分盲签名和零知识证明基础上 ,设计了一个 男 ,四川盐亭人 ,教授 ,博士生导师 , 主要研究方向为密码学 、信息隐藏 同时具有匿名性和非否认的电子现金 。该使用零知识证 与水印 、电子商务 、网络通信等 。 明起到了双重的作用 ,既达到了对用户的强私有保护 ,同时非 ( ) ()ca l Pe rsp ec tive [ J ]. Comp u te r F raud & Secu rity, 2000 , 12 : 13 2161 上接第 112 页 Dm itry Gryaznov1Scanne rs of the Year 2000: H eu ristic s [ C ]. P ro2 [ 2 ] ceed ings of the 15 th In ternationa l V iru s B u lle tin Confe rence, 1999. 225 22341 [ 3 ] O N a sa rou i, F Gonza lez, et a l. A Sca lab le A rtific ial Imm une System Mode l fo r D ynam ic U n sup e rvised L ea rn ing [ C ]. P roceed ings of the ( ) Gene tic and Evo lu tionary Comp u tation Confe rence GECCO , 2003112 216. D e Ca stro L N , Timm is J .I A rtific ia l Imm une System s a s a Nove l Soft [ 4 ] ( ) Comp u ting Parad igm [ J ]. Soft Comp u ting Jou rna l, 2003 , 7 8 : 526 2 5441 3 结论 Pau l K H a rm e r, Pau l D W illiam s, et a l. A n A rtific ia l Imm une System [ 5 ] A rch itec tu re fo r Comp u te r Secu rity App lica tion s [ J ]. IEEE Tran sac2 从实验结果可以看出 ,该方法具有很强的自学习能力 ,能 ( ) tion on Evo lu tionary Comp u tation, 2002 , 6 3 : 252 2280. 够较有效地识别已知病毒和未知病毒 ,特别是变种病毒 。并且 作者简介 : 该方法有一定的容错能力 ,体现了多样性 、自学习 、动态调节等 ( ) 陈桓 1980 2,男 ,浙江东阳人 ,硕士研究生 ,研究方向为网络安全技术 多种优秀特性 ,能够不断地完善和提高识别能力 ,在合理参数 ( ) 及应用 ;刘晓洁 1965 2,女 ,江苏南京人 ,副教授 , 硕士生导师 ,研究方 ( ) 的选择下能够获得很低的错误否定率和错误肯定率 。 向为网络安全 、人工智能 ; 宋程 1980 2,男 ,四川达州人 ,硕士研究生 , ( ) 研究方向为网络安全技术及应用 ; 梁可心 1980 2,男 , 四川成都人 ,硕 参考文献 : 士研究生 ,研究方向为网络安全技术及应用 。 [ 1 ] Dwan, B ern i. The Comp u te r V iru s: F rom The re to H e re: A n H isto ri2