基于H-tree的多维序列模式挖掘算法

提出了一种基于H-tree的多维序列模式挖掘算法,首先在序列信息中挖掘序列模式,然后针对每个序列模式,根据包含此模式的所有元组中的多维信息构造H-tree树,挖掘出相应的多维模式,从而得到了多维序列模式。该算法将多维分析方法与序列模式挖掘算法有效地结合在一起,当维度较高时具有较高的性能。     

基于特征相似的软件缺陷排除方法

开发人员思维定式和代码复制与克隆会导致代码中存在相同类型的软件缺陷。基于这一思想,提出一种基于特征相似的软件缺陷排除方法。该方法对已定位缺陷代码进行特征分析,基于该缺陷代码特征,查找项目代码中具有相似特征的代码片段。结合缺陷类型和代码特征对缺陷代码进行分析,建立特征相似关联规则,检测项目代码,排查与缺陷代码相似度超过预定阈值的代码片段,相似度超过预定阈值的代码片段称为疑似代码。通过对科研管理系统和物业系统人工导入错误并进行缺陷排除实验分析和人工检测,证实了该方法能够有效地发现项目中隐含的相似缺陷代码。     

面向SQLite3数据库API调用序列的并行运行时验证方法

作为轻量级的高可靠嵌入式数据库, SQLite3已被广泛应用于航空航天和操作系统等多个安全攸关领域, 其提供了丰富灵活API函数以支持用户快速实现项目构建.然而, 不正确的API函数调用序列会导致严重后果, 包括运行错误、内存泄露和程序崩溃等.为了高效准确地监控SQLite3数据库API函数的正确调用情况, 本文提出了基于多核系统的并行运行时验证方法.该方法首先分析API函数文档, 自动挖掘相关API调用序列规约描述, 辅助人工将其形式化表达为具有完全正则表达能力的命题投影时序逻辑公式; 然后在程序运行时, 采用多任务调度策略, 将程序执行产生的状态序列分割并对不同片段并行验证.实验结果表明, 该方法能够发现调用SQLite3数据库API函数的30个被验证C程序中, 违背API函数调用序列规约的达16个.另外, 与传统串行运行时验证方法的对比实验表明, 本文提出的并行运行时验证方法能够有效提高多核系统的验证效率.     

统计策略序列模式挖掘及其在软件缺陷预测中的应用

人类的生活越来越依赖于高可靠性和可用性的软件系统,软件缺陷一直是软件工程领域中研究最活跃的内容之一。在研究序列模式挖掘技术的基础上,介绍了软件缺陷预测的相关技术,设计了一种基于统计策略的序列模式挖掘算法的软件缺陷预测方案,实现了InfoMiner和STAMP两种模式挖掘算法、卡方检验特征选择和SVM等分类算法;构造了一个软件缺陷预测模型,实现了预测和发现软件系统中的未知缺陷的功能。实验结果表明,所提软件预测模型可以获得良好的预测结果,具有一定的使用价值和应用前景。     

网络告警序列中的频繁情景规则挖掘算法

网络告警序列中隐含着丰富的关于网络自身行为特征的模式知识，对其进行有效挖掘和利用将显著提高网络故障管理智能化程度．本文研究网络告警序列中的知识发现问题，提出并实现了一种基于滑动窗口的情景规则挖掘算法。     

基于指针神经网络的细粒度缺陷定位

软件缺陷定位是指找出与软件失效相关的程序元素. 当前的缺陷定位技术仅能产生函数级或语句级的定位结果. 这种粗粒度的定位结果会影响人工调试程序和软件缺陷自动修复的效率和效果. 专注于细粒度地识别导致软件缺陷的具体代码令牌, 为代码令牌建立抽象语法树路径, 提出基于指针神经网络的细粒度缺陷定位模型来预测出具体的缺陷代码令牌和修复该令牌的具体操作行为. 开源项目中的大量缺陷补丁数据集包含大量可供训练的数据, 且基于抽象语法树构建的路径可以有效捕获程序结构信息. 实验结果表明所训练出的模型能够准确预测缺陷代码令牌并显著优于基于统计的与基于机器学习的基线方法. 另外, 为了验证细粒度的缺陷定位结果可以贡献于缺陷自动修复, 基于细粒度的缺陷定位结果设计两种程序修复流程, 即代码补全工具去预测正确令牌的方法和启发式规则寻找合适代码修复元素的方法, 结果表明两种方法都能有效解决软件缺陷自动修复中的过拟合问题.     

基于位置信息的显露序列模式挖掘研究

显露序列因为具有强区分能力,常被用来构建有效的分类器。当前算法大多关注序列模式的支持度或出现次数,而忽略序列模式在序列中的出现位置,这将导致一些重要的信息丢失。为此,提出一种带有局部位置信息的显露序列模式,并给出位置显露序列模式挖掘算法。该算法基于出现次数框架,结合后缀树,省略了候选模式的生成与选择步骤,能够快速有效地挖掘出位置显露序列模式。实验结果表明,采用位置显露序列模式构建的分类器在平均分类准确度上高于传统的显露序列模式挖掘算法。     

基于XML的软件安全静态检测方法研究

安全关键软件设计使用的C/C++语言含有大量未定义行为,使用不当可能产生重大安全隐患。软件静态检测是从软件代码和结构中找出安全缺陷的重要手段。从安全规则的角度,提出了基于XML（eXtensible Markup Language）中间模型的静态检测方法。该方法将C/C++源代码解释为XML中间模型,将安全规则转化为缺陷模式,利用Xquery查询表达式对软件安全缺陷进行定位。基于该方法的原型系统检验结果表明：该方法能够有效地检测出违反安全规则的软件缺陷,并具有安全规则可定制的特点。     

基于Sequitur的时间序列异步周期模式挖掘

现有的时间序列异步周期模式挖掘方法是在获取1-pattern有效段及周期的基础上再以枚举法得到i-patterns,时间复杂度较高。为解决该问题,提出一种改进的异步周期模式挖掘方法。在时间序列符号化后,使用基于Sequitur的候选模式算法获取候选i-patterns及其事件位置序列,通过基于OEOP的i-patterns有效段生成算法得到1-pattern和i-patterns的有效段及周期,从而生成有效子序列。实验结果表明,该方法具有较高的挖掘效率。     

考虑价格的跨种类模糊序列模式挖掘算法*

消费者对不同种类的产品具有不同的价格偏好,而传统的序列模式挖掘算法仅考虑序列中不同项目的出现顺序,使得挖掘到的序列模式没有包含产品价格以及种类等重要信息。为了克服传统算法的这一缺陷,在序列模式中体现更多的用户行为信息,本文基于模糊集理论,提出了一种在产品种类维度上进行的跨种类模糊价格序列模式挖掘算法。实验结果表明,与传统序列模式挖掘算法相比,该算法可以有效解决序列数据的稀疏性问题,能够挖掘得到更多个性化的序列模式。     

Alattin: mining alternative patterns for defect detection

To improve software quality, static or dynamic defect-detection tools accept programming rules as input and detect their violations in software as defects. As these programming rules are often not well documented in practice, previous work developed various approaches that mine programming rules as frequent patterns from program source code. Then these approaches use static or dynamic defect-detection techniques to detect pattern violations in source code under analysis. However, these existing approaches often produce many false positives due to various factors. To reduce false positives produced by these mining approaches, we develop a novel approach, called Alattin, that includes new mining algorithms and a technique for detecting neglected conditions based on our mining algorithm. Our new mining algorithms mine patterns in four pattern formats: conjunctive, disjunctive, exclusive-disjunctive, and combinations of these patterns. We show the benefits and limitations of these four pattern formats with respect to false positives and false negatives among detected violations by applying those patterns to the problem of detecting neglected conditions.     

Model-checking software library API usage rules

Modern software increasingly relies on using third-party libraries which are accessed via application programming interfaces (APIs). Libraries usually impose constraints on how API functions can be used (API usage rules) and programmers have to obey these API usage rules. However, API usage rules often are not well documented or documented informally. In this work, we show how to use the SCTPL and SLTPL logics to precisely and formally specify API usage rules in libraries, where SCTPL/SLTPL can be seen as an extension of the branching/linear temporal logic CTL/LTL with variables, quantifiers and predicates over the stack. This allows library providers to formally describe API usage rules without knowing how their libraries will be used by programmers. We propose an automated approach to check whether programs using libraries violate API usage rules or not. Our approach consists in modeling programs as pushdown systems (PDSs) and checking API usage rules by SCTPL/SLTPL model-checking for PDSs. To make the model-checking procedure more efficient and precise, we propose an abstraction that reduces drastically the size of the program model and integrate may-alias analysis into our approach to reduce false alarms. Moreover, we characterize two sublogics rSCTPL and rSLTPL of SCTPL and SLTPL that are preserved by the abstraction. We implement our techniques in a tool and apply the tool to check several open-source programs. Our tool finds several previously unknown bugs in several programs. The may-alias analysis avoids most of the false alarms that occur using SCTPL or SLTPL model-checking techniques without may-alias analysis.     

A decision support system for constructing an alert classification model

As the rapid growth of network attacking tools, patterns of network intrusion events change gradually. Although many researches had been proposed to analyze network intrusion behaviors in accordance with low-level network data, they still suffer a large mount of false alerts and result in difficulties for network administrators to discover useful information from these alerts. To reduce the load of administrators, by collecting and analyzing unknown attack sequences systematically, administrators can do the duty of fixing the root causes. Due to the different characteristics of each intrusion, none of analysis methods can correlate IDS alerts precisely and discover all kinds of real intrusion patterns. Therefore, an alert-based decision support system is proposed in this paper to construct an alert classification model for on-line network behavior monitoring. The architecture of decision support system consists of three phases: Alert Preprocessing Phase, Model Constructing Phase and Rule Refining Phase. The Alert Processing Phase is used to transform IDS alerts into alert transactions with specific data format as alert subsequences, where an alert sequence is a kind of well-aggregated alert transaction format to discover intrusion behaviors. Besides, the Model Constructing Phase is used to construct three kinds of rule classes: normal rule classes, intrusion rule classes and suspicious rule classes, to filter false alert patterns and analyze each existing or unknown alert patterns; each rule class represents a set of classification rules. Normal rule class, a set of false alert classification rules, can be trained by using sequential pattern mining approach in an attack-free environment. Intrusion rule classes, a set of known intrusion classification rules, and suspicious rule classes, a set of novel intrusion classification rules, can be trained in a simulated attacking environment using several well-known rootkits and labeling by experts. Finally, the Rule Refining Phase is used to change the classification flags of alert sequence across different time intervals. According to the urgent situations of different levels, Network administrators can do event protecting or vulnerability repairing, even or cause tracing of attacks. Therefore, the decision support system can prevent attacks effectively, find novel attack patterns exactly and reduce the load of administrators efficiently.     

Associative Classification With Artificial Immune System

Associative classification (AC), which is based on association rules, has shown great promise over many other classification techniques. To implement AC effectively, we need to tackle the problems on the very large search space of candidate rules during the rule discovery process and incorporate the discovered association rules into the classification process. This paper proposes a new approach that we call artificial immune system-associative classification (AIS-AC), which is based on AIS, for mining association rules effectively for classification. Instead of massively searching for all possible association rules, AIS-AC will only find a subset of association rules that are suitable for effective AC in an evolutionary manner. In this paper, we also evaluate the performance of the proposed AIS-AC approach for AC based on large datasets. The performance results have shown that the proposed approach is efficient in dealing with the problem on the complexity of the rule search space, and at the same time, good classification accuracy has been achieved. This is especially important for mining association rules from large datasets in which the search space of rules is huge.     

特殊网络通信行为的数据挖掘与分析

为了挖掘可疑通信的行为模式,定位发生了可疑通信行为的上网账户,本文首先分析了可疑通信行为特点。然后针对已有关联规则挖掘算法不能同时满足多层次数据挖掘和加权关联规则挖掘的问题,分析对比两种典型的基本关联规则算法,以FP-tree为基础,提出了ML-WFP多层次加权关联规则挖掘算法。针对算法中数据项权重的确定问题,由用户设置数据项间的重要性比较关系,借鉴模糊一致矩阵的概念,利用模糊层次分析法计算数据项的权重。最后将该算法应用于可疑通信行为的挖掘。实验测试结果表明可疑通信行为挖掘方案合理有效。     

MACSPMD:基于恶意API调用序列模式挖掘的恶意代码检测

基于动态分析的恶意代码检测方法由于能有效对抗恶意代码的多态和代码混淆技术,而且可以检测新的未知恶意代码等,因此得到了研究者的青睐。在这种情况下,恶意代码的编写者通过在恶意代码中嵌入大量反检测功能来逃避现有恶意代码动态检测方法的检测。针对该问题,提出了基于恶意API调用序列模式挖掘的恶意代码检测方法MACSPMD。首先,使用真机模拟恶意代码的实际运行环境来获取文件的动态API调用序列;其次,引入面向目标关联挖掘的概念,以挖掘出能够代表潜在恶意行为模式的恶意API调用序列模式;最后,将挖掘到的恶意API调用序列模式作为异常行为特征进行恶意代码的检测。基于真实数据集的实验结果表明,MACSPMD对未知和逃避型恶意代码进行检测的准确率分别达到了94.55%和97.73%,比其他基于API调用数据的恶意代码检测方法 的准确率分别提高了2.47%和2.66%,且挖掘过程消耗的时间更少。因此,MACSPMD能有效检测包括逃避型在内的已知和未知恶意代码。     

一种改进的基于活动轨迹的Aspect挖掘方法

面向方面程序设计是近年来提出的一种程序设计技术,通过将横切关注点封装成Aspect,实现软件系统复杂性的降低,系统可维护性和可扩展性的提高。Aspect挖掘的目标是识别遗产系统中的横切关注点,为遗产系统的面向方面改造提供支持。文章提出了一种改进的基于活动轨迹的Aspect挖掘方法,基于横切关注点具有不同的调用上下文等约束寻找方法调用轨迹中相同的方法调用模式。通过实例说明该方法提高了候选Aspect的查全率。     

Forecasting association rules using existing data sets

An important issue that needs to be addressed when using data mining tools is the validity of the rules outside of the data set from which they are generated. Rules are typically derived from the patterns in a particular data set. When a new situation occurs, the change in the set of rules obtained from the new data set could be significant. In this paper, we provide a novel model for understanding how the differences between two situations affect the changes of the rules, based on the concept of fine partitioned groups that we call caucuses. Using this model, we provide a simple technique called combination data set, to get a good estimate of the set of rules for a new situation. Our approach works independently of the core mining process and it can be easily implemented with all variations of rule mining techniques. Through experiments with real-life and synthetic data sets, we show the effectiveness of our technique in finding the correct set of rules under different situations.     

基于差分隐私的轨迹模式挖掘算法

针对现有基于差分隐私的频繁轨迹模式挖掘算法全局敏感度过高、挖掘结果可用性较低的问题,提出一种基于前缀序列格和轨迹截断的差分隐私下频繁轨迹模式挖掘算法--LTPM。该算法首先利用自适应的方法获得最优截断长度,然后采用一种动态规划的策略对原始数据库进行截断处理,在此基础上,利用等价关系构建前缀序列格,并挖掘频繁轨迹模式。理论分析表明LTPM算法满足ε-差分隐私;实验结果表明,LTPM算法的准确率（TPR）和平均相对误差（ARE）明显优于N-gram和Prefix算法,能有效提高挖掘结果的可用性。     

A flexible sequence alignment approach on pattern mining and matching for human activity recognition

This paper proposes a flexible sequence alignment approach for pattern mining and matching in the recognition of human activities. During pattern mining, the proposed sequence alignment algorithm is invoked to extract out the representative patterns which denote specific activities of a person from the training patterns. It features high performance and robustness on pattern diversity. Besides, the algorithm evaluates the appearance probability of each pattern as weight and allows adapting pattern length to various human activities. Both of them are able to improve the accuracy of activity recognition. In pattern matching, the proposed algorithm adopts a dynamic programming based strategy to evaluate the correlation degree between each representative activity pattern and the observed activity sequence. It can avoid the trouble on segmenting the observed sequence. Moreover, we are able to obtain recognition results continuously. Besides, the proposed matching algorithm favors recognition of concurrent human activities with parallel matching. The experimental result confirms the high accuracy of human activity recognition by the proposed approach.