基于加权信息增益的恶意代码检测方法
- 格式:pdf
- 大小:83.07 KB
- 文档页数:3
网络安全中的恶意代码检测与防范方法恶意代码(Malware)是指用于攻击计算机系统、窃取用户信息、传播病毒等恶意行为的计算机程序。
随着网络的普及和应用的广泛,恶意代码的威胁日益严重,对网络安全造成了巨大的风险。
为了保护用户信息和计算机系统的安全,网络安全专家们积极研发并应用恶意代码检测与防范方法。
恶意代码的检测方法主要包括特征检测、行为检测和机器学习检测。
特征检测是一种常见而有效的方法,它利用已知的恶意代码特征来识别和分类恶意代码。
这些特征可以是恶意代码的特定字符串、文件结构或者函数调用等。
特征检测不依赖于恶意代码的行为,而是依赖于恶意代码的特定特征。
然而,特征检测的局限在于对已知特征的依赖,新型的恶意代码可能会使用新的特征,从而逃避检测。
行为检测是通过观察恶意代码的行为来判断其是否为恶意代码。
这种方法不依赖于恶意代码的特定特征,而是关注其对计算机系统的影响和操作。
行为检测可以监控恶意代码执行的系统调用、网络通信等行为,从而及时发现和阻止恶意代码的活动。
然而,行为检测也有其局限性,因为某些新型的恶意代码可以通过伪装、加密等手段来隐藏其行为特征,使得其难以被检测。
机器学习是一种基于样本数据的自动学习方法,其在恶意代码检测中也得到了广泛应用。
机器学习方法通过分析已有的恶意代码数据和非恶意代码数据,学习生成一个分类模型。
这个模型可以对新的恶意代码进行预测和分类。
机器学习方法能够自动学习具有较强泛化能力的特征,对于新型的恶意代码也能较好地进行检测。
但是,机器学习方法也存在着过拟合、样本不平衡等问题,需要针对这些问题进行优化。
除了恶意代码的检测方法,防范恶意代码也是非常重要的。
下面我来介绍几种常用的防范恶意代码的方法。
首先是使用杀毒软件。
杀毒软件是一种能够检测和消除计算机病毒的软件。
它通过对病毒特征的识别和监听计算机的活动,及时发现和清除恶意代码。
用户可以定期更新杀毒软件的病毒库,确保其具备最新的恶意代码识别能力。
基于机器学习的恶意代码检测技术一、引言随着互联网的快速发展,恶意代码越来越普遍。
恶意代码能够侵害用户的隐私、盗取个人信息、破坏计算机系统甚至引起经济损失。
因此,开发恶意代码检测技术变得至关重要。
在过去的几十年里,恶意代码检测技术不断发展,从基于特征的检测技术到基于机器学习的检测技术。
本文将从机器学习角度探讨恶意代码检测技术。
二、基于特征的恶意代码检测技术基于特征的恶意代码检测技术是早期被开发的技术。
该技术从代码的特征入手,分析代码的功能、结构、行为等信息来判断代码是否是恶意代码。
常用的特征包括文件大小、使用的API函数、代码段和数据段的长度等。
但是,随着技术不断发展,恶意代码变得越来越复杂,很难从特征中准确地识别恶意代码。
另外,攻击者会不断地对恶意代码进行变异,使得基于特征的检测技术无法及时地适应变异后的恶意代码。
因此,基于特征的检测方法已经被机器学习的方法所替代。
三、基于机器学习的恶意代码检测技术基于机器学习的恶意代码检测技术是目前最为流行的检测技术之一。
该技术利用机器学习算法从大量的数据中学习,可以自动地提取恶意代码的特征,并可以适应恶意代码的变异。
1. 数据收集和准备在基于机器学习的恶意代码检测技术中,数据的收集和准备是非常重要的一个环节。
恶意代码数据的来源可以是公共数据库、恶意代码样本库、黑客论坛以及其他来源。
在准备数据时,需要对数据进行清洗、去重和标注。
数据清洗是为了剔除无效数据,去重是为了避免训练数据重复,标注是为了对恶意代码和正常代码进行区分。
2. 特征提取特征提取是机器学习检测技术的关键步骤之一。
提取恶意代码的特征需要考虑到特征的全面性和重要性。
通常,特征可以包括二进制特征、API调用特征、图像特征和文本特征等。
在恶意代码检测中,二进制特征是最基础的特征,用于描述代码的结构和实现。
API调用特征是用于描述代码调用的API函数,可以反映代码的行为和功能。
图像特征和文本特征则用于描述代码的可视化和语言特性。
如何使用机器学习技术进行恶意代码检测近年来,随着网络威胁不断增加,恶意代码成为了对计算机和网络安全最大的威胁之一。
为了应对这一问题,学术界和工业界一直在努力研发有效的恶意代码检测技术。
其中,机器学习技术因其在大数据处理和模式识别方面的优势而备受关注。
本文将介绍如何使用机器学习技术进行恶意代码检测。
恶意代码通常是指那些具有恶意目的、能够对计算机系统造成破坏的代码。
为了防止这些恶意代码威胁计算机安全,研究人员常常通过对代码的特征进行分析并训练机器学习模型来检测此类威胁。
首先,恶意代码检测的第一步是构建一个可靠的数据集。
这个数据集应包含恶意代码样本和良性代码样本。
恶意代码样本可以从已知的恶意软件样本集合中获取,而良性代码样本可以从各种来源收集,如开源软件、可信网站等。
对于每个样本,需要提取并选择适当的特征来描述代码。
特征提取是恶意代码检测中的关键步骤。
常用的特征包括静态特征和动态特征。
静态特征是通过分析代码的静态特性来提取的,包括文件大小、代码结构、函数调用等。
动态特征则是通过在虚拟环境中执行代码并记录其行为来提取的,包括系统调用、网络流量等。
在提取特征时,需要注意特征的可区分性和代表性,以便机器学习模型能够准确地区分恶意代码和良性代码。
接下来,需要选择适当的机器学习算法来训练模型。
常用的算法包括支持向量机(Support Vector Machine,SVM)、决策树(Decision Tree)、随机森林(Random Forest)等。
这些算法可以利用已经提取的特征来学习并建立模型,以实现对未知代码的分类。
在训练模型之前,需要对数据集进行预处理。
预处理的目的是清洗数据并提高训练模型的效果。
常见的预处理方法包括特征选择、特征缩放、数据平衡等。
特征选择可以通过选择最具信息量的特征来减少特征的维度,并提高模型的训练速度和精度。
特征缩放可以将特征值缩放到相同的范围内,以避免某些特征对模型的影响过大。
数据平衡则是指处理不均衡的数据集,以避免模型对少数类别的过度偏差。
网络安全中的恶意代码检测方法恶意代码是指那些带有恶意意图的计算机程序,它们可能对用户的计算机系统、数据以及网络安全带来巨大风险。
随着网络攻击的不断增加和恶意代码的复杂化,恶意代码检测成为了网络安全中至关重要的一环。
本文将探讨网络安全中的恶意代码检测方法。
1. 病毒特征检测法病毒特征检测法是一种基于病毒数据库的常用检测方法。
它通过比对文件或代码的特征与已知病毒特征进行匹配,以确定是否存在恶意代码。
该方法的优势在于可以检测出已知的病毒,但缺点是无法检测出未知的病毒,因为对于未知的病毒,病毒特征数据库中并没有相应的特征。
2. 行为监测法行为监测法是一种动态分析方法,它通过监测程序运行时的行为来判断是否存在恶意代码。
该方法可以检测出未知的恶意代码,因为它不依赖于特定的特征库。
行为监测法主要是通过监控程序的系统调用、文件读写、网络连接等行为来推断程序是否具有恶意行为。
然而,由于恶意代码具有多样性和变异性,行为监测法也存在漏报和误报的风险。
3. 静态分析法静态分析法是一种通过分析恶意代码的源代码或二进制码来检测恶意代码的方法。
它可以在不运行程序的情况下检测出恶意代码的存在,并可以提供恶意代码的详细信息。
静态分析法主要依靠对代码结构、指令流等进行分析,以推断代码是否具有恶意行为。
然而,静态分析法也存在一些局限性,例如无法检测出加密或混淆的恶意代码。
4. 机器学习方法近年来,机器学习方法在恶意代码检测中得到了广泛应用。
机器学习方法利用大量的已知恶意代码样本进行训练,从而建立分类模型,并通过对新样本进行分类来判断是否存在恶意代码。
机器学习方法可以有效地检测出未知的恶意代码,并且可以通过不断更新训练样本来提高检测效果。
然而,机器学习方法也存在一些挑战,例如需要大量的训练样本和处理不平衡数据的问题。
5. 混合检测方法为了提高恶意代码检测的准确性和效率,研究者们提出了一种将多种检测方法结合起来的混合检测方法。
混合检测方法可以综合利用特征检测、行为监测、静态分析、机器学习等方法的优势,从而提高恶意代码检测的综合能力。
网络安全中的恶意代码检测与分析技术随着互联网的快速发展,网络安全问题变得日益复杂和严峻。
恶意代码(Malware)作为网络安全的主要威胁之一,对用户的信息和隐私产生了巨大的威胁。
为了保护用户的网络安全,研究人员和安全公司致力于开发恶意代码的检测和分析技术,以及相应的防护措施。
本文将介绍恶意代码的检测与分析技术的发展现状以及一些常用的技术方法。
首先,恶意代码的检测是网络安全的重要环节。
通过及时对恶意代码进行检测,可以防止其对用户设备或系统造成损害。
最常见的恶意代码检测方法之一是基于特征的检测。
这种方法通过分析即将运行的代码是否与已知的恶意代码特征相匹配来判断代码是否为恶意。
然而,由于恶意代码的不断变异,特征匹配方法的准确性受到了一定的限制。
因此,研究人员还开发了一些基于行为的检测方法。
这些方法通过分析程序的行为,例如文件的读写、网络通信等,来判断其是否为恶意代码。
基于行为的检测方法具有一定的优势,可以检测出一些之前未知的恶意代码。
另外,机器学习方法也被广泛应用于恶意代码检测。
通过训练模型识别已知的恶意代码样本,进一步应用于未知样本的检测。
这种方法可以有效地提高恶意代码检测的准确性。
其次,恶意代码的分析是深入理解恶意代码的行为和特征的重要手段。
恶意代码的行为分析可以帮助研究人员了解其具体的攻击目标和方式。
一般来说,恶意代码的行为包括文件操作、系统调用、网络通信等。
通过对这些行为进行分析,可以了解恶意代码对受感染设备的影响以及后续可能引发的攻击行为。
除了行为分析,研究人员还将重点放在恶意代码的变体分析上。
由于恶意代码不断变异,变体分析可以帮助分析人员快速识别出恶意代码的新型变种,以便及时做出相应的反应和防范。
同时,恶意代码的代码分析也是一项重要的工作。
通过对代码的细致分析,可以揭示其内部的攻击机制和漏洞利用方式,为相关安全防护工作提供有力的依据。
在实际应用中,恶意代码的检测和分析技术需要与现有的网络安全产品结合使用,形成综合的安全解决方案。
恶意代码技术和检测方法恶意代码及其检测技术1.恶意代码概述1.1定义恶意代码也可以称为Malware,目前已经有许多定义。
例如Ed Skoudis将Malware定义为运行在计算机上,使系统按照攻击者的意愿执行任务的一组指令。
微软“计算机病毒防护指南”中奖术语“恶意软件”用作一个集合名词,指代故意在计算机系统上执行恶意任务的病毒、蠕虫和特洛伊木马。
随着网络和计算机技术的快速发展,恶意代码的传播速度也已超出人们想象,特别是人们可以直接从获得恶意代码源码或通过网络交流代码。
很多编程爱好者把自己编写的恶意代码放在网上公开讨论,发布自己的研究成果,直接推动了恶意代码编写技术发展。
所以目前网络上流行的恶意代码及其变种层出不穷,攻击特点多样化。
1.2类型按照恶意代码的运行特点,可以将其分为两类:需要宿主的程序和独立运行的程序。
前者实际上是程序片段,他们不能脱离某些特定的应用程序或系统环境而独立存在;而独立程序是完整的程序,操作系统能够调度和运行他们;按照恶意代码的传播特点,还可以把恶意程序分成不能自我复制和能够自我复制的两类。
不能自我复制的是程序片段,当调用主程序完成特定功能时,就会激活它们;能够自我复制的可能是程序片段(如病毒),也可能是一个独立的程序(如蠕虫)。
2.分析与检测的方法恶意代码与其检测是一个猫捉老鼠的游戏,单从检测的角度来说。
反恶意代码的脚步总是落后于恶意代码的发展,是被动的.目前基于主机的恶意代码检测方法主要有反恶意代码软件、完整性校验法以及手动检测,基于网络的检测方法主要有基于神经网络”、基于模糊识别“等方法,本文主要讨论基于主机的检测。
2.1 恶意代码分析方法2.1.1 静态分析方法是指在不执行二进制程序的条件下进行分析,如反汇编分析,源代码分析,二进制统计分析,反编译等,属于逆向工程分析方法。
(1)静态反汇编分析,是指分析人员借助调试器来对而已代码样本进行反汇编出来的程序清单上根据汇编指令码和提示信息着手分析。
恶意代码及其检测技术1.恶意代码概述1.1定义恶意代码也可以称为Malware,目前已经有许多定义。
例如Ed Skoudis将Malware定义为运行在计算机上,使系统按照攻击者的意愿执行任务的一组指令。
微软“计算机病毒防护指南”中奖术语“恶意软件”用作一个集合名词,指代故意在计算机系统上执行恶意任务的病毒、蠕虫和特洛伊木马。
随着网络和计算机技术的快速发展,恶意代码的传播速度也已超出人们想象,特别是人们可以直接从网站获得恶意代码源码或通过网络交流代码。
很多编程爱好者把自己编写的恶意代码放在网上公开讨论,发布自己的研究成果,直接推动了恶意代码编写技术发展。
所以目前网络上流行的恶意代码及其变种层出不穷,攻击特点多样化。
1.2类型按照恶意代码的运行特点,可以将其分为两类:需要宿主的程序和独立运行的程序。
前者实际上是程序片段,他们不能脱离某些特定的应用程序或系统环境而独立存在;而独立程序是完整的程序,操作系统能够调度和运行他们;按照恶意代码的传播特点,还可以把恶意程序分成不能自我复制和能够自我复制的两类。
不能自我复制的是程序片段,当调用主程序完成特定功能时,就会激活它们;能够自我复制的可能是程序片段(如病毒),也可能是一个独立的程序(如蠕虫)。
2.分析与检测的方法恶意代码与其检测是一个猫捉老鼠的游戏,单从检测的角度来说。
反恶意代码的脚步总是落后于恶意代码的发展,是被动的.目前基于主机的恶意代码检测方法主要有反恶意代码软件、完整性校验法以及手动检测,基于网络的检测方法主要有基于神经网络”、基于模糊识别“等方法,本文主要讨论基于主机的检测。
2.1 恶意代码分析方法2.1.1 静态分析方法是指在不执行二进制程序的条件下进行分析,如反汇编分析,源代码分析,二进制统计分析,反编译等,属于逆向工程分析方法。
(1)静态反汇编分析,是指分析人员借助调试器来对而已代码样本进行反汇编出来的程序清单上根据汇编指令码和提示信息着手分析。
恶意代码行为分析技术和检测方法研究近年来,随着互联网的普及和信息技术的发展,恶意代码带来的威胁不断增加。
恶意代码是指一种具有恶意目的的计算机程序,在未被允许的情况下,采取窃取、篡改、破坏等行为,侵害计算机及其用户的安全。
因此,研究恶意代码行为分析技术和检测方法具有重要的现实意义。
一、恶意代码行为分析技术恶意代码行为分析是指对恶意软件进行静态或动态行为分析过程,主要是为了找出其隐藏的恶意行为,以达到对其的有效防范和处理。
主要有以下几种技术。
1. 静态签名分析技术:该方法主要是利用恶意代码的特征构建基于模式匹配的规则或算法,以便能够迅速地检测出已知的恶意代码。
该方法优点是快速、准确,适用于网络安全防御领域。
但其缺点是易被攻击者绕过,因此静态签名分析技术只能被视为恶意代码检测的辅助方法,而非主要方法。
2. 动态行为分析技术:该方法应用广泛,主要有分析系统调用堆栈、进程间通信、文件系统、网络等行为的行为监测技术。
该方法能够有效拦截未知的恶意代码,具有较好的可靠性,但因为该方法需要直接执行恶意代码,因此可能会造成损失。
其缺点是耗时长,不利于对大规模的恶意代码进行样本检测。
3. 模型学习技术:该方法基于机器学习技术,将一些已知和未知的恶意代码作为训练数据构建模型,再通过学习算法进行分类。
该方法的优点是准确、便捷,适用于已知样本训练和分类,但我们也必须意识到,模型学习技术对于未知样本的判断存在一定缺陷,因此需要不断完善。
二、恶意代码检测方法除了以上的恶意代码行为分析技术之外,还有一些常见的恶意代码检测方法,如下所示。
1. 杀毒软件:杀毒软件属于静态签名分析技术,在保证实时更新病毒库的前提下,能够及时发现并清除已知的病毒。
但病毒库的繁琐管理和完善,使得部分杀毒软件功能和覆盖率并不完善。
2. 行为监测软件:行为监测软件属于动态行为分析技术,其优点是能够拦截未知的恶意代码,其缺点是对计算机的资源占用长;对于已存在于计算机系统的恶意代码,行为监测软件往往无法完成清除等工作,所以仅能作为一种较好的预防手段。
—149—基于加权信息增益的恶意代码检测方法张小康,帅建梅,史 林(中国科学技术大学自动化系,合肥 230027)摘 要:采用数据挖掘技术检测恶意代码,提出一种基于加权信息增益的特征选择方法。
该方法综合考虑特征频率和信息增益的作用,能够更加准确地选取有效特征,从而提高检测性能。
实现一个恶意代码检测系统,采用二进制代码的N-gram 和变长N-gram 作为特征提取方法,加权信息增益作为特征选择方法,使用多种分类器进行恶意代码检测。
实验结果证明,该方法能有效提高恶意代码的检测率和准确率。
关键词:数据挖掘;变长N-gram ;特征选择;信息增益Malicious Code Detection Method Based on Weighted Information GainZHANG Xiao-kang, SHUAI Jian-mei, SHI Lin(Department of Automation, University of Science & Technology of China, Hefei 230027)【Abstract 】Using data mining technology to detect malicious code, this paper proposes a feature selection method based on weighted information gain. This method can select effective features more correctly by combining the advantage of information gain with classwise frequency. A malicious code detection system is implemented which adopts binary N-gram and variable-length N-gram as the feature extraction method, weighted information gain as the feature selection method. Several classifiers are used to detect malicious code in the system. Experimental results prove that this method can effectively improve the detection and accuracy rate.【Key words 】data mining; variable-length N-gram; feature selection; information gain计 算 机 工 程 Computer Engineering 第36卷 第6期Vol.36 No.6 2010年3月March 2010·安全技术·文章编号:1000—3428(2010)06—0149—03文献标识码:A中图分类号:TP3911 概述传统恶意代码检测技术主要基于签名和启发式方法,基于签名的检测方法是提取已知病毒样本的特征,通过搜索病毒库查找相匹配的恶意代码特征。
这种方法有较高的检测率,但无法检测新出现的病毒。
启发式算法利用专家定义一组行为来检测未知恶意代码,准确率高,但效率低。
数据挖掘方法可以通过学习恶意代码与正常代码的区别,有效检测未知恶意代码。
Kephart 最早提出了一种特征提取和选择方法,使用人工神经网络的方法来检测引导区病毒。
Arnold 采用了同样的方法来检测Win32病毒。
文献[1]提出数据挖掘技术检测未知恶意代码,分别提取Win32 dll 文件调用、ASC Ⅱ字符串、字节序列等代码特征,使用多种分类算法,包括RIPPER 、朴素贝叶斯和多重朴素贝叶斯算法,其中检测未知恶意代码准确率最高的是用字节序列作为特征的多重朴素贝叶斯算法。
文献[2]提出基于二进制代码的N-gram 特征提取方法,使用K-NN 算法来检测恶意代码。
文献[3]用N-gram 提取二进制代码的特征,利用信息增益进行特征选择,使用朴素贝叶斯、SVM 、boosted J48等算法实现分类,其中,boosted J48的检测率最高。
随着变长N-gram 应用于入侵检测和文本分类,文献[4]提出用N-gram 提取二进制代码的特征,利用类域频率进行特征选择,采用J48分类算法进行分类。
已有文献主要专注于特征提取的方法,然而按已有方法提取出的特征包含大量冗余特征。
如何选取有效特征,对于提高检测性能是非常重要的,但这个方面却鲜有研究。
本文提取二进制代码的N-gram 和变长N-gram 作为特征,提出一种基于加权信息增益的特征选择方法,选择有效特征供分类器学习。
加权信息增益特征选择方法利用特征是否出现以及出现的频率这2个因素来综合评价一个特征所含有的信息量,弥补了信息增益只考虑特征出现与否的不足。
结果表明,采用此方法能够更加准确地选取有效特征,检测性能优于基于信息增益特征选择方法的性能。
2 恶意代码检测模型结构本文实现了一个基于数据挖掘方法的恶意代码检测系统,采用代码二进制序列的N-gram 和变长N-gram 作为特征,加权信息增益作为特征选择方法,采用多种分类算法实现恶意代码检测的系统。
其模型如图1所示。
图1 恶意代码检测模型基金项目:国家“863”计划基金资助项目(2006AA01Z449)作者简介:张小康(1983-),女,硕士,主研方向:信息安全; 帅建梅,副教授;史 林,硕士收稿日期:2009-11-05 E-mail :zxkang@训练部分首先选取一定数量的恶意代码和正常代码作为训练集合,提取代码二进制序列的N-gram和变长N-gram作为特征;然后进行特征选择,计算出每个特征对应的加权信息增益()IW j,并按照()IW j降序排序,选取前面若干个作为有效特征,根据每个训练样本是否包含这些特征,构成一个布尔向量空间,供分类器学习。
检测部分提取待测代码二进制序列的N-gram和变长N-gram作为特征,根据每个待测代码是否包含训练部分选择的有效特征,构成一个布尔向量空间,分类器用几种分类算法对该向量空间进行分析,判断该待测代码是否为恶意代码。
假设待测代码样本数量为N,则N TP TN FP FN=+++。
其中,TP是恶意代码被正确分类的数目;FP是正常代码被错误标记为恶意代码的数量;TN是正常代码被正确分类的数目;FN是恶意代码被错误标记为正常代码的数量。
一个恶意代码检测工具有如下2个评价指标:(1)准确率TP TNN+,即所有被正确分类的代码数量在待测集合中所占的比例。
(2)检测率TPTP FN+,即被正确分类的恶意代码数目在待测集合的所有恶意代码中所占的比例。
3 特征提取方法本文选择代码二进制序列作为表示形式,在此基础上使用N-gram和变长N-gram滑动窗口提取特征。
下面分别介绍这2种算法。
3.1 N-gram特征N-gram是由一个长度为N的滑动窗口收集的一系列重叠的子字符串,这个窗口每次滑动一个单位长度。
比如,08 00 74 ff 13 b2,其对应的3-gram为(08 00 74), (00 74 ff), (74 ff 13), (ff 13 b2)。
N-gram可以捕获到一些潜在的其他方法很难准确提取的特征,在恶意代码检测领域,N-gram是广泛应用的特征提取方法。
N-gram提取特征有2个缺点:(1)N-gram很难同时捕获不同长度的字节序列,当一个有意义的字节序列不是N的倍数时,会产生边缘误匹配,从而无法提取这个特征。
(2)由N-gram产生的特征集合非常庞大,需要相当大的存储容量。
本文在实现N-gram算法时采用Trie数据结构,节省存储空间,保证了特征生成和查找的快速准确性。
3.2 变长N-gram特征变长N-gram也称段落,是一串有意义的连续字节序列,与N-gram不同,它的长度是不固定的,避免一个有意义的序列被拆开的可能性。
提取有意义的段落,首先需要在一系列字节序列中寻找断点,相邻断点之间的连续序列就是一个段落。
本文的段落分割算法采用了专家投票算法[5]。
专家投票算法假设有2个专家。
一个是频率专家,负责测量每个子序列出现的频率,频率越高,那么这个子序列是一个段落的可能性越大,其中包含断点的可能性越小;另一个是熵专家,负责测量每个点的熵,如果一个元素后面连接的元素每次都各不相同,熵越大,那么与一个后面连接的元素总是固定的元素相比,是一个段落结尾的可能性更大。
每个位置都有一个分数,在一个固定长度的滑动窗口中,频率最大以及熵最大的2个位置的分数加1。
最后,综合2个专家的结果,根据每个位置所得到的累加分数来判断可能的断点。
将2个断点之间的连续序列作为一个特征提取出来。
本文选择d=4的Trie数据结构实现专家投票算法。
假设字符串string=(01 E8 B8 01 E8 B8 B8 01),其Trie 结构如图2所示。
其中,左边叶节点E8在Trie中表示字节序列(01 E8 B8),这个节点的数字2表示这个序列出现的次数。
当长度为3的窗口从左至右划过string时,先遇到(01|E8|B8|)。
第1个位置的频率是由此隔开的前后2个序列的频率之和,即=(01)+(E8B8)f f f。
(01)=(01)+(E8 B8)f f f表示在Trie第1层的(01)的频率,(E8 B8)f表示在Trie第2层并且父节点是(E8)的(B8)的频率。
第1个位置的熵表示在Tire 第1层的(01)的熵,第2个位置的熵表示在Trie第2层并且父节点是(01)的(E8)的熵,以此类推。
这个窗口中频率和熵最大的位置分别被标记出来,对应的分数加1。
然后窗口向右滑动,直至结束。
图2 string的Trie结构(d=4)Trie中节点的频率为()()(())f xP xf parent x=(1) 节点的熵为(())()lb()mi iiE parent x P x P x==−∑ (2)其中,m为x的父节点拥有的子树个数。
当滑动窗口遍历整个string之后,可以根据分数找出一些局部极大值,对应的位置就为断点。
string的段落分割结果为((01 E8 B8) (01 E8 B8) (B8 01))。
4 加权信息增益通过以上方法提取特征包含很多冗余特征,从中选取有利于区分代码类型的特征是必要的。
本文提出加权信息增益的特征选择方法选择有效的一组特征。
信息增益也被称作平均互信息量。