一种改进的多模式匹配算法在Snort中的应用

模式匹配算法是入侵检测系统的重要组成部分。为进一步提高入侵检测系统的性能和效率,提出一种新的多模式匹配算法——完全自动机匹配算法(CA-AC算法),并将其应用于入侵检测系统Snort中。该算法是对Aho-Corasick算法的改进,根据新算法进行状态转换使得自动机状态减少,相应节约了存储空间。分析了算法的复杂度。实验表明,完全自动机算法在Snort中的应用改进了算法的性能,提高了Snort系统的规则检测效率。     

基于语法解析树的函数漏洞发现方法

大多数行业定制软件的漏洞检测较困难,而传统的静态漏洞检测方法会产生很多错误的和虚假的信息。针对函数调用前后存在的漏洞问题,提出了基于上下文无关的自顶向下与自底向上相结合的语法解析树的方法,它能够在对函数内部定义不了解或者部分了解的情况下,解析函数调用前后安全契约规则:前置规则和后置规则。同时通过扩展规则表示的XML文法来表示面向对象下,规则中的属性存在继承关系下的契约规则。实验表明,与同类型安全分析工具比较,该方法具有避免函数重复分析、规则可扩展性良好、尤其在自定义对象类和特定环境下自定义参数准确率高等优点。     

入侵检测系统中模式匹配自动机的构造研究

本文提出了一种新的用于构造入侵检测模式匹配自动机的方法。该方法从构造判定单个模式的NFA自动机入手,通过集成单个的NFA而得到全集的NFA,并将全集NFA转换为与之等价的DFA并化简,从而可得到全集的确定型模式匹配有限自动机。由于该方法可以完全自动完成,从而可以方便地为入侵检测系统构造模式匹配自动机。     

基于程序合法作用域的入侵检测系统的研究

通过分析应用程序在执行时的系统调用序列,提出了一种新的基于程序合法作用域的入侵检测方法.合法作用域的建立以程序的系统调用信息为依据,并采用了有限状态自动机对其进行建模,每一个合法作用域由一个状态来表示,它包含程序运行时的有效用户标示和有效组标示,然后据此检测系统的异常行为.实验结果表明,该方法可以检测到利用应用程序代码漏洞而发起的攻击,并且有较低的错误警报率.     

面向RFID数据处理的复杂事件模式匹配方法

RFID数据具有不确定性,复杂事件处理技术将RFID数据看作不同类型的事件,从事件流中检测符合特定匹配模式的复杂事件。概率事件流分为多项概率事件流和单项概率事件流;针对多项概率事件流,提出NFA-MMG模式匹配方法,亦即使用多个有向无环图结合自动机实现模式匹配。针对单项概率事件流,提出NFA-Tree模式匹配方法,亦即使用匹配树结合自动机实现模式匹配;并提出改进的NFA-Tree方法,即基于概率阈值进行过滤,提高结果过滤效率。实验结果验证了上述模式匹配方法的性能优势。     

基于有限状态自动机的漏洞检测模型

漏洞是软件安全的一个严重威胁,如何检测软件中存在的漏洞对提高其安全性具有重要的意义.经过分析缓冲区溢出漏洞产生的原因,得出了其形成的3个必要条件,并根据产生原因的不同,针对函数调用出错和循环拷贝出错而导致的两类缓冲区溢出漏洞,分别提出了相应的基于有限状态自动机的漏洞检测模型.     

软件漏洞静态检测模型及检测框架

软件漏洞静态分析是信息安全领域的重点研究方向,如何描述漏洞及判别漏洞是漏洞静态分析的核心问题。提出了一种用于描述和判别漏洞的漏洞静态检测模型。首先对软件漏洞的属性特征进行形式化定义,并对多种软件漏洞和其判定规则进行形式化描述;其次,针对传统的路径分析存在的状态空间爆炸问题,提出了一个新的程序中间表示——漏洞可执行路径集,以压缩程序状态空间。在该模型的基础上,设计了一个基于漏洞可执行路径集的软件漏洞静态检测框架,利用定义的漏洞语法规则求解漏洞可执行路径集上的漏洞相关节点集,利用漏洞判定规则对漏洞相关节点集进行判别得出漏洞报告。实验分析验证了该漏洞检测模型的正确性和可行性。     

基于改进正则表达式规则分组的内网行为审计方案

针对网络安全审计中对应用层协议审计能力不足的问题,提出一种基于改进正则表达式（RE）规则分组的内网行为审计方案。首先,通过正则表达式对需审计的协议进行描述,并设置相关参数,使内网中出现频率高和审计中相对重要的协议状态在正则表达式描述集中取得高优先级;然后,在正则表达式交互值小的前提下,尽可能地将高优先级协议状态表达式构建到相同自动机分组中以生成审计引擎;最后,根据审计需求,改变相关参数,实现对内网行为的安全审计。实验结果显示,所提出的自动机构建算法在转化时的状态数缩减为经典非确定有限状态自动机（NFA）转化算法Thompson的10%~20%,检测时的吞吐量约为传统自动机分组引擎的8到12倍;所提审计方案能够满足对应用层协议进行安全审计的需求,具有较高的准确性和效率。     

基于确定有限状态自动机的改进多模式匹配算法研究

针对网络入侵检测系统的一般问题,在详细分析现存单模式与多模式匹配算法的基础上,将AC算法里的DFSA方法与单模式匹配算法BMH的思想相融合,以求取优化检测效率为目标,提出一种基于确定有限状态自动机的改进多模式匹配算法。该算法特别适合在大字符集文本串中查找小字符集模式串。将该改进多模式匹配算法应用到Snort入侵检测过程中,针对处理结果进行科学评价。通过实例的应用,验证了该改进算法的可行性和高效性。     

使用事件自动机规约的C语言有界模型检测

提出使用事件自动机对 C 程序的安全属性进行规约,并给出了基于有界模型检测的形式化验证方法。事件自动机可以规约程序中基于事件的安全属性,且可以描述无限状态的安全属性。事件自动机将属性规约与C程序本身隔离,不会改变程序的结构。在事件自动机的基础上,提出了自动机可达树的概念。结合自动机可达树和有界模型检测技术,给出将事件自动机和C程序转化为可满足性模理论SMT(satisfiability modulo theory)模型的算法。最后,使用SMT求解器对生成的SMT模型求解,并根据求解结果给出反例路径分析算法。实例分析和实验结果表明,该方法可以有效验证软件系统中针对事件的属性规约。     

一种改进数据流图的子字并行程序表示方法

论文致力于对图像处理算法的串行C程序进行子字并行分析,并重定向到带有多媒体扩展的通用处理器和多媒体专用嵌入式微处理器。图像处理算法的特点决定其是内在可并行的,这种并行粒度介于数据并行(DLP)和指令级并行(ILP)之间,称之为子字并行。但是,当前的编译技术很难充分挖掘和定位程序基本块内的子字并行,对此设计了一种基于流图程序表示的编译方法,能够从串行程序中显式地定位子字并行。扩展了编译器的功能,增加了特定的模式库,基于模式识别的控制流和数据流分析后,产生特定的子字并行流图(SWFG,Sub-WordFlowGraph),并将该图作为中间表示,提供给子字并行指令选择,进而实现有效的子字并行代码产生。     

Theory and practice of unparsed patterns for metacompilation

Several software development tools support the matching of concrete syntax user-supplied patterns against the application source code, allowing the detection of invalid, risky, inefficient or forbidden constructs. When applied to compilers, this approach is called metacompilation. These patterns are traditionally parsed into tree patterns, i.e., fragments of abstract-syntax trees with metavariables, which are then matched against the abstract-syntax tree corresponding to the parsing of the source code. Parsing the patterns requires extending the grammar of the application programming language with metavariables, which can be difficult, especially in the case of legacy tools. Instead, we propose a novel matching algorithm which is independent of the programming language because the patterns are not parsed and, as such, are called unparsed patterns. It is as efficient as the classic pattern matching while being easier to implement. By giving up the possibility of static checks that parsed patterns usually enable, it can be integrated within any existing utility based on abstract-syntax trees at a low cost. We present an in-depth coverage of the practical and theoretical aspects of this new technique by describing a working minimal patch for the GNU C compiler, together with a small standalone prototype punned Matchbox, and by lying out a complete formalisation, including mathematical proofs of key algorithmic properties, like correctness and equivalence to the classic matching.     

基于抽象语法树的智能化漏洞检测系统

源代码漏洞的自动检测是一个重要的研究课题。目前现有的解决方案大多是基于线性模型,依赖于源代码的文本信息而忽略了语法结构信息,从而造成了源代码语法和语义信息的丢失,同时也遗漏了许多漏洞特征。提出了一种基于结构表征的智能化漏洞检测系统Astor,致力于使用源代码的结构信息进行智能化漏洞检测,所考虑的结构信息是抽象语法树（Abstract Syntax Tree,AST）。首先,构建了一个从源代码转化而来且包含源码语法结构信息的数据集,提出使用深度优先遍历的机制获取AST的语法表征。最后,使用神经网络模型学习AST的语法表征。为了评估Astor的性能,对多个基于结构化数据和基于线性数据的漏洞检测系统进行比较,实验结果表明Astor能有效提升漏洞检测能力,降低漏报率和误报率。此外,还进一步总结出结构化模型更适用于长度大,信息量丰富的数据。     

一种有效的字符串有序跳跃模式近似匹配算法

字符串的模式匹配问题是计算机科学的基本问题之一,而近似模式匹配更是近期的研究热点。本文分析了文本分析领域中出现的一种特殊的近似模式匹配问题,即字符串有序跳跃模式近似匹配问题,提出了一种基于有限自动机的组件组合分析算法。算法的特点在于将组件匹配过程与组配过程进行分离,这样既降低了问题的复杂度,又可以实现按策略组配的灵活性。组件匹配过程中利用有限自动机对跳跃模式的组件进行匹配查找;组件的组配过程中先对查找到的组件进行组合分析,然后再对各种组合进行初步筛选和基于策略的优选。初步筛选工作是依据顺序性、唯一性和最大数三条原则进行;而优选工作是根据四个设计的评价参数选择其中最佳组合。实验结果表明,该算法的确能解决字符串有序跳跃模式匹配问题,完全可以适用于句型匹配与主题词跳词匹配。     

基于图神经网络的代码漏洞检测方法

使用神经网络进行漏洞检测的方案大多基于传统自然语言处理的思路，将源代码当作序列样本处理，忽视了代码中所具有的结构性特征，从而遗漏了可能存在的漏洞。提出了一种基于图神经网络的代码漏洞检测方法，通过中间语言的控制流图特征，实现了函数级别的智能化代码漏洞检测。首先，将源代码编译为中间表示，进而提取其包含结构信息的控制流图，同时使用词向量嵌入算法初始化基本块向量提取代码语义信息；然后，完成拼接生成图结构样本数据，使用多层图神经网络对图结构数据特征进行模型训练和测试。采用开源漏洞样本数据集生成测试数据对所提方法进行了评估，结果显示该方法有效提高了漏洞检测能力。     

基于关系图卷积网络的源代码漏洞检测

软件安全的根源在于软件开发人员开发的源代码,但随着软件规模和复杂性不断提高,仅靠人工检测漏洞代价高昂且难以扩展,而现有的代码分析工具有较高的误报率与漏报率。为此,提出一种基于关系图卷积网络（RGCN）的自动化漏洞检测方法以进一步提高漏洞检测的精度。首先将程序源代码转换为包含语法、语义特征信息的CPG;然后使用RGCN对图结构进行表示学习;最后训练神经网络模型预测程序源代码中的漏洞。为验证所提方法的有效性,在真实的软件漏洞样本上开展了实验验证,结果表明所提方法的漏洞检测结果的召回率和F1值分别达到了80.27%和63.78%。与Flawfinder、VulDeepecker和基于图卷积网络（GCN）的同类方法相比,所提方法的F1值分别提高了182%、12%和55%,可见所提方法能有效提高漏洞检测能力。     

一种用于反编译代码与源代码的比较算法

现有反编译器产生的代码与对应的源代码之间存在差异,找到并理解差异有助于改进并完善反编译器的设计。该文给出一种适用于C语言反编译代码与源代码的比较算法。该算法以语法树匹配方法为基础,定义新的C语言中间代码表示形式并对表达式进行动态匹配,提高了语法树匹配的准确性。实验结果表明,该算法能有效计算出反编译代码与源代码之间的多数差异。     

基于AC自动机的多模式匹配算法FACA

Aho-Corasick自动机算法在模式匹配失配时,需要多次回溯才转移到有效的后继状态。为此,提出一种快速多模式匹配算法。该算法为每个状态建立失配时的后继指针,在模式匹配失配时,可以通过失配后继指针快速找到有效后继状态,从而避免Aho-Corasick自动机失配时的过多回溯,提高匹配效率。算法在自动机建立时采用动态规划的方法,为每个状态建立匹配长度和匹配量等信息,在模式匹配过程中,基于这些信息统计模式串在主串中的重复次数、最早出现模式串位置等信息。实验结果表明,该算法匹配精确、效率高,且支持在线操作。     

基于代码属性图及注意力双向LSTM的漏洞挖掘方法

随着信息安全愈发严峻的趋势,软件漏洞已成为计算机安全的主要威胁之一.如何准确地挖掘程序中存在的漏洞,是信息安全领域的关键问题.然而,现有的静态漏洞挖掘方法在挖掘漏洞特征不明显的漏洞时准确率明显下降.一方面,基于规则的方法通过在目标源程序中匹配专家预先定义的漏洞模式挖掘漏洞,其预定义的漏洞模式较为刻板单一,无法覆盖到细节特征,导致其存在准确率低、误报率高等问题;另一方面,基于学习的方法无法充分地对程序源代码的特征信息进行建模,并且无法有效地捕捉关键特征信息,导致其在面对漏洞特征不明显的漏洞时,无法准确地进行挖掘.针对上述问题,提出了一种基于代码属性图及注意力双向LSTM的源码级漏洞挖掘方法.该方法首先将程序源代码转换为包含语义特征信息的代码属性图,并对其进行切片以剔除与敏感操作无关的冗余信息;其次,使用编码算法将代码属性图编码为特征张量;然后,利用大规模特征数据集训练基于双向LSTM和注意力机制的神经网络;最后,使用训练完毕的神经网络实现对目标程序中的漏洞进行挖掘.实验结果显示,在SARD缓冲区错误数据集、SARD资源管理错误数据集及它们两个C语言程序构成的子集上,该方法的F1分数分别达到了82.8%,77.4%,82.5%和78.0%,与基于规则的静态挖掘工具Flawfinder和RATS以及基于学习的程序分析模型TBCNN相比,有显著的提高.