云安全审计中基于日志的用户行为分析
赵春晔+涂山山+陈昊宇+黄永峰
摘 要： 云存储将网络中大量不同类型的存储设备集合起来协同工作，共同对外提供数据存储服务。由于其特征上存在着用户和服务商之间的信任博弈，因此构建一个健康、公平、安全的云数据服务环境，对云数据的状态及操作过程执行客观、公正的安全审计尤为重要。为此，提出一种基于用户行为日志分析的云安全审计解决方案，通过制定数据“用户行为”描述，从功能上实现基于用户行为的系统日志信息分析，同时改进现有关联规则挖掘算法，提出一种针对长序列的关联规则挖掘算法。最后通过实验表明该方案可有效地实现云安全审计中隐私数据泄露的追踪与取证。
关键词： 云安全审计； 日志分析； 关联规则； 追踪与取证
中图分类号： TN911?34； TP309.2 文献标识码： A 文章编号： 1004?373X（2017）02?0001?05
Abstract： Cloud Storage provides data storage service for external by combing and coordinating different types of storage devices in the network， so that they can collectively work together. However it always exists a trust game relationship between users and service providers， therefore it is important to build a healthy， fair and secure cloud data service environment for the security auditing on the state of cloud data and operation processes. A cloud security?auditing scheme based on analysis of user behavior （UB） log data from cloud servers is proposed in this paper. The system log information analysis based on UB is realized functionally by description rules of UB. And the existing association rule mining algorithm is improved simultaneously， which is proposed for dealing with the Long Sequence Frequent Pattern （LSFP） to extract UB. The experiment result indicates that the solution can implement the tracking and evidence taking of data leakage efficiently for the cloud security auditing.
Keywords： cloud security auditing； log analysis； association rule； data tracking and evidence taking
0 引 言
云計算已然成为当今最热门的应用及研究领域，但云计算所需的对于数据和资源的共享所带来的云数据安全问题，一直是限制云计算技术发展的重要因素[1]。惠普在2000年提出了“可信云”的概念，并提出了云数据安全的理论模型[2]——CALC（Cloud Accountability Life Cycle）。在CALC模型中，将云数据安全的整体解决方案描述为一个环形结构，将整个数据安全过程分为：策略、追踪、日志、存储、报告、审计、整理7个环节，每个环节都对其下的环节提供支持，而整个过程的结果也反过来支持最初的策略环节，整个安全过程是递进优化的。
在此基础上，Ryan等人针对日志采集[3]（Logging）环节，提出了Flogger[4]，S2Logger[5]等一系列的解决方案。其基本思想是对整个云数据环境下主机的操作系统日志进行采集，通过分析日志，得到云环境下数据使用的具体情况。这种区别于以往对数据出、入口进行检测的方法[6?7]，可以得到在整个云环境内数据被使用的真实情况。解决了以往数据安全方案中“整个云环境安全可信”这个不可自立[7]的前提，并使“可信云”可被证实。但随着数据规模的不断增大，将日志分析仅仅停留在日志采集阶段已经无法满足云计算“受信”的基本要求。迫切地需要一种对日志数据进行归纳分析的方法，即在R&R（Reporting and Replaying）阶段进一步对日志进行处理。
基于这种思路的数据安全方案，将在多个环节对现有方案有所改进：在“存储”阶段，因为日志分析的引入，将原本的描述系统操作行为的日志，转化成为描述“用户行为” [8]的信息，使得日志数据的数量大幅精简；而在“报告”和“审计”阶段，本方案提供可读性更高、更符合实际的描述信息，使数据安全审计变得更加面向用户，为云环境的“可信性”提供更好、更直接的证实和支持；在“整理”和“策略”阶段，由于本方案提供的记录信息更能够准确描述现实情况，也使得“策略”的制定从原本的技术层面升级到对现实行为的约束，使责任追究变得更加简单、准确。
为此引入一种近年来主要用于知识发现（KDD），并在数据挖掘（Data Mining）和数据分析（Data Analyze）领域取得较好成果的方式——关联规则挖掘（Association Rule Mining）。算法本身是为了解决经典的“购物篮”问题而提出的，通过分析顾客购买商品的情况，得到不同商品之间的联系（基于统计学的联系，而不是逻辑上的因果联系）。
本文对频繁模式发现算法FP?Growth进行了研究，并针对云安全审计中数据日志分析的实际需求，提出一种实际可行的改进算法，旨在将关联规则挖掘引入特定模式数据集的分析过程。
1 相关理论知识
1.1 关联规则算法分析
Agrawal于1993年首次提出关联规则算法，以解决挖掘顾客交易数据中项集的关联性问题。其基本思路是找到数据中频繁性满足要求的多项集，再以此为基础分析项之间隐含的关联性。在此基础上，研究人员进行了大量的研究工作，主要在算法性能和面向对象上对算法进行了改进和扩展。
在性能改进方面比较突出的有Apriori算法和FP?Growth算法[9]。Apriori算法基于一种迭代的思想，逐步产生关联性分析所需要的多项集，以此尽可能得到包含更多项的集合，以达到良好的分析结果。而FP?Growth算法是由韩家炜在2000年提出的，针对Apriori算法需要迭代产生多项集而带来的算法时空复杂度问题，通过引入“树”的概念，将迭代过程改进为通过一次扫描数据集以生成“频繁模式树（FP?tree）”，通过这种树形结构表示数据集的频繁性，再通过树的搜索算法得到频繁多项集。因其性能较优，已成为当今主流的关联规则挖掘算法。
而在面向对象方面，AprioriAll[10]算法在Apriori算法的基础上，对事务集加入了时间约束，以分析短序列集合中项之间的关联性。
AprioriAll算法，在每一次扫描数据库时，利用上一次扫描时产生的序列生成候选序列，并在扫描的同时计算它们的支持度，满足支持度的候选序列作为下次扫描的序列。
GSP算法[11]是AprioriAll算法的扩展算法。在GSP算法中，引入了时间约束、滑动时间窗和分类层次技术，增加了扫描的约束条件，有效地减少了需要扫描的候选序列的数量，同时还克服了基本序列模型的局限性，更切合实际，减少多余无用模式的产生。另外，GSP利用哈希树来存储候选序列，减少了需要扫描的序列数量，同时对数据序列的表示方法进行了转换，这样就可以有效地发现一个候选项是否是数据序列的子序列。
Apriori及其改进算法，在数据集较大的情况下，会产生大量的中间集（候选集），使算法的时空复杂度变大，对大数据模型的效率不能令人满意。
FP?Growth算法通过引入图形结构，使得其算法结构更加适应于新型的计算框架和数据库结构。而基于FP?Growth的改进算法，将工作重心更多地投入当今流行的分布式计算[12?13]、投影数据库[14]方向，并取得了大量的成果。但FP?Growth及其改进算法，由于算法过程依赖“树”型结构，因此不能解决序列等包含其他约束条件数据集的挖掘。
1.2 约束规则
通过分析，对关联规则算法的改进，其本质都是一种约束条件的引入。Apriori算法基于一种简单的逻辑约束，即“任何一个频繁集的子集一定是频繁的”。而FP?Growth算法则是通过“树”的引入，将这种约束更加显性的表述，以提升算法效率。而AprioriAll和GSP算法，则是通过对数据集引入时间约束，有效地过滤了“无用”的多项集。
从挖掘所使用约束的类型看，可以把用于关联规则挖掘的约束分为：
（1） 单调性约束（Monotone Constraint）。所谓一个约束是单调性的约束，是指满足的任何项集的超集也能满足。
（2） 反单调性约束（Anti?monotone Constraint）。约束是“反单调的”，是指对于任意给定的不满足的项集， 不存在的超集能够满足。
（3） 可转变的约束（Convertible Constraint）。可转变的约束是指约束条件可以在项集和它的子集间传递。如果一个约束无法用单调或反单调形式给出，那么就给使用上带来困难，于是可通过对数据的特殊组织等方式使问题得到转换。
（4） 简洁性约束（Succinct Constraint）。简洁性约束是指对一个项目子集可以用选择性谓词来表示成选择操作。很显然，如果一个约束是简洁的，那么就可以直接使用SQL查询来得到满足条件的集合。在挖掘的不同阶段可以尽量尝试简洁性的约束，这样可以避免不必要的测试。
按照挖掘所使用约束条件的来源，又可将约束进行如下分类：
（1） 知识类型约束。利用知识背景可以过滤无关信息。
（2） 数据约束。利用数据的某些属性，可以隔离与当前问题无关的信息。
（3） 维、层、度约束。利用数据或数据库的结构和规模，将数据挖掘限定在某个区间，以滤除“额外”信息。
2 长序列关联规则算法
随着当今网络技术的发展，对于流数据等具有强时间约束的数据集的关联规则挖掘方法越来越值得重视。而通过对以往研究成果的分析，发现关联规则挖掘的对象依然停留在离散的数据上。即便如GSP算法将时间约束引入事务，其面向的数据集（事务集）依然是离散的。在针对长序列结构的数据集时，依然不能满足功能需求。
基于对已有研究成果的分析，本方案在FP?Growth算法基础上，引入合理的约束条件，即强时间约束。并与之匹配的引用“有向图”这一图形结构，以直观的表述约束条件。通过对算法结构的改造和新模型的引入，设计一种面向长序列的关联规则挖掘算法Long Sequence Frequent Pattern（LSFP）。
2.1 LSFP算法描述
針对数据集强时间约束的特点，传统FP?Growth算法构造的频繁模式树结构，并不能有效地描述数据集的有序性，在针对序列类型的数据集时，数据本身的性质可能使得频繁模式树规模过大而不可用。其根本是因为树型结构更易于表述节点之间的联系，而数据的有序性使得节点之间的“边”具有描述更多数据含义的能力，针对有序数据，需要一种能够直观表述“边”之间关系的图形结构。为此，本方案引入一种新的图形结构，即有向图。对于序列，这种结构的优势主要体现在两个方面：
（1） 有向图不同于树型结构，有向图中的“边”描述了“从节点到节点”的转移关系，这种转移关系，可以有效地描述强时间约束的数据集中“有序性”的信息。
（2） 有向图的结构保证在图里没有重复出现的节点，相比于树形结构，有向图为算法提供了空间复杂度上的改进。
基于这种思想，提出算法结构和流程设计。
算法分为2步：一是算法训练阶段，通过训练集得到整个数据集的频繁性；二是分析挖掘阶段，通过之前得到的数据频繁性，得到数据集中满足频繁性的“UB（短序列）”。算法相关参数定义如表1所示。
在项集中，节点包含属性和，用以描述节点是否可作为一个UB（User Behavior）的起始节点和终止节点。
2.2 算法步骤
算法第一阶段：
Step1：扫描训练集，生成项集；
Step2：生成有向图，并以关联矩阵描述；
Step3：选择恰当的阈值，对有向图进行剪枝；
Step4：引入先验规则，优化关联矩阵，得到数据完整频繁特征；
Step5：通过有向图搜索，得到可能的“用户行为”短序列（即事务）格式。
算法第二阶段：
Step1：根据关联矩阵描述的数据频繁性，将长序列拆分成若干较短序列，形成待挖掘的序列集；
Step2：在序列集中挖掘出“行为”，生成“行为集”。
3 算法实现及性能分析
3.1 实验环境
针对算法设计思路和实际问题，本方案选择通过采集得到的Linux操作系统日志作为算法实现的数据集，因为其具有良好的时间属性，并具有很好的代表性。并根据算法的复杂度选择适合的软、硬件环境。
3.1.1 算法环境
算法环境如表2所示。
3.1.2 算法参数
算法参数对性能的影响主要包含两个方面：训练集规模和最小支持度。训练集规模：算法选择使用数据集的一部分作为获取频繁性的训练集，主要是因为来源相同的数据集和训练集拥有相似的数据频繁特性，使得通过分析训练集得到的频繁性对于数据集同样是适用的。当使用整个数据集作为训练集的时候，数据集和训练集必定拥有相同的频繁性。但过大的训练集会使算法的整体效率降低，于是选择规模恰当的训练集，对算法性能有巨大的影响。最小支持度：最小支持度决定了算法认为哪些操作组合可以被认为是一种“用户行为”。当选择较小的支持度，必然会得到更多的“操作组合”，但这些组合是否足够频繁使其可以被看作一种“行为”却无法保证；当选择较大的支持度，可以保证“操作组合”即是“用户行为”的准确性，但必然会使算法得到的操作组合变少。
3.2 算法分析
在进行算法性能分析之前，需要对算法结果有一个直观的认识。在此将几个常见的用户行为所对应的操作系统日志序列（规则）展示如下：
（1） 文件创建
Create，wzq，3103，2406，2406，2387，nautilus，/home/wzq/De
sktop/test/new file，/home/wzq/，193，438，30
Close，wzq，3103，2406，2406，2387，30
（2） 文件复制
Open，wzq，3354，3054，3054，2752，test，log，/home/wzq/Desk
top/test/，577，438，4
Close，wzq，3355，3354，3054，2752，3Duplicate2，wzq，3355，
3354，3054，2752，4，1Close，wzq，3355，3354，3054，2752，4
（3） 文件编辑
Move，wzq，2956，2928，2928，2856，vim，aaa.txt，aaa.txt～，
/home/wzq/Desktop/test/
Create，wzq，2956，2928，2928，2856，vim，aaa.txt，/home/wzq/
Desktop/test/，577，436，3
Write，wzq，2956，2928，2928，2856，3，0，6F6E650A0A
Read，wzq，2856，1，2424，2405，21，0，
0D1B5B3F32356C226161612E747B7422
Close，wzq，2956，2928，2928，2856，3
Chmod，wzq，2956，2928，vim，aaa.txt，33204
前文中，从理论上分析了算法性能的影响因素。这里通过实验数据对算法性能进行直观的反映。
3.2.1 针对训练集的算法性能分析
数据集和训练集大小，是指在日志采集后经过“预处理”的数据大小。因为日志采集过程中会产生大量的与数据操作无关的系统日志信息，占原始日志数据的80%。为分析训练集规模对算法性能的影响，选择相同的数据集和最小支持度，评价算法性能的主要指标有得到的“规则”数、得到的“行为”数、运行时间。
实验结果分析如下：
（1） 规则数与行为数。在实验过程中，随着训练集规模从1 MB逐渐增大到10 MB，通过算法训练阶段可以得到更“完整”的规则信息，针对相同的数据集，得到的行为数从400余条增长到900余条。两者与训练集规模基本呈非線性对数关系。如图1所示。
（2） 算法运行时间。训练集规模直接相关，随着训练集规模增大，算法训练阶段所需时间也相应提高，两者间的关系基本呈线性。而随着训练集的增大，得到的“规则数”也增大，但两者基本保持对数关系。而“规则数”的增大，也导致了算法挖掘“行为”阶段需要对比更多“规则”。在实验过程中，随着训练集规模从1 MB逐渐增大到10 MB，算法运行时间从400 ms增长到900 ms。算法运行时间与训练集规模基本呈线性关系。如图2所示。
3.2.2 针对最小支持度的算法性能分析
关联规则算法的最小支持度可以通过多重方式获得，这也是相关改进算法研究的一个重要方面，在这里，只分析选用不同的支持度对算法性能的影响，对于计算最小支持度的算法不做讨论。为分析最小支持度对算法性能的影响，选择相同的數据集和训练集，评价算法性能的主要指标有：得到的“规则”数、得到的“行为”数、运行时间。实验结果分析如下：
（1） 规则数与行为数。随着最小支持度的减小，必将使得到的规则数变大，也导致算法挖掘阶段得到更多的行为数。在实验过程中，随着最小支持数从20逐渐增大到100，行为数从1 200余条减小到400余条，行为数、规则数与最小支持度基本呈非线性指数关系。但最小支持度的减小，也会把原本“不频繁”的操作组合认定为一种频繁的规则，这使得最终得到的行为在准确性方面有所不足，如图3所示。
（2） 算法运行时间。由于训练集大小不变，所以算法训练阶段所需时间保持不变。但由于最小支持度变小，使得得到的规则数增大，导致算法挖掘阶段的时间消耗变大。在实验过程中，随着最小支持度从20逐渐增大到100，运行时间从1 200 ms减小到400 ms。运行时间与最小支持度基本呈非线性指数关系，如图4所示。
4 结 语
本文从解决云数据安全性这个实际问题出发，分析了已有解决方案优劣，并研究、分析了现今在数据挖掘领域较主流的关联规则挖掘算法。借鉴关联规则的思想，设计并实现了一种针对主机操作系统日志的模式挖掘算法，将描述系统操作的进程级日志数据转化为描述用户行为的日志，为云数据安全审计提供更合适的信息。在以后的工作中，算法依然有需要改进的方面：
最小支持度的获得。通过实验可知，最小支持度对算法结果和过程的效率都有直接的影响。在本文的实验范围内，通过人为的设定一个阈值的方式获得最小支持度，并尝试改变阈值，分析最小支持度对算法结果和算法效率的影响。在现今的研究中，通过数据集的特征计算最小支持度的方式越来越主流，相应的计算方法也各有优劣。在今后的工作中，将基于系统操作日志这个特定的数据集，设计并实现适合的最小支持度计算方法，改进算法性能。
算法在不同环境下的性能分析。在本文的实验范围中，将实验环境设定在单用户主机情景下。在这种情景下，用户对文件进行的操作比较简单，操作过程也相对容易理解、分析。在联机环境或服务器环境下，通过日志分析表现出的行为模式必定与本文的实验环境不同。在今后的工作中，将在不同的环境下进行实验，并分析不同环境下的行为模式。以期达到日志分析的最终目的：为数据安全策略的制定提供现实依据。
参考文献
[1] TU Shanshan， HUANG Yongfeng. Towards efficient and secure access control system for mobile cloud computing [J]. China communications， 2015， 12（12）： 43?52.
[2] KO R K L， JAGADPRAMANA Peter， MOWBRAY Miranda， et al. TrustCloud： A framework for accountability and trust in cloud computing [C]// Proceedings of the 2011 IEEE World Congress on Services. [S.l.]： IEEE， 2011： 584?588.
[3] KO R K L， KIRCHBERG M.， LEE B S. From system?centric to data?centric logging? accountability， trust and security in cloud computing [C] // Proceedings of Defense Science Research Conference and Expo. [S.l.： s.n.]， 2011： 1?4.
[4] KO R K L， JAGADPRAMANA P， LEE B S. Flogger： a file?centric logger for monitoring file access and transfers with cloud computing environments [C]// Proceedings of 3rd IEEE International Workshop on Security in e?Science and e?Research （ISSR 11）. [S.l.]： IEEE， 2011： 11?16.
[5] SUEN C H， KO R K L， TAN Y S， et al. S2Logger： end?to?end data tracking mechanism for cloud data provenance [C]// Proceedings of 12th IEEE International Conference on Trust， Security and Privacy in Computing and Communications. [s.l.]： IEEE， 2013： 123?130.
[6] MUNISWAMY?REDDY K K， HOLAND D A， BRAUN U， et al. Provenance?aware storage systems [C]// Proceedings of 06 Annual Technical Conference on USENIX. [S.l.： s.n.]， 2006： 6?11.
[7] MUNISWAMY?REDDY K K， BRAUN U， HOLAND D A， et al. Layering in provenance systems [C]// Proceedings of the Annual Technical Conference of USENIX. [S.l.： s.n.]， 2009： 11?16.
[8] 肖传奇，陈明志.云环境下基于IFAHP的用户行为信任模型研究[J].信息网络安全，2015（12）：14?20.
[9] HAN J W， PEI J， YIN Y W， et al. Mining frequent patterns without candidate generation [J]. Data mining and knowledge discovery， 2004， 8（1） ： 53?87.
[10] AGRAWAL R， SRIKANT R. Mining sequential patterns [C]// Proceedings of 1995 Int Conf Data Engineering （ICDE 95）. Taipei， China： IEEE Computer Society， 1995： 3?14.
[11] AGRAWAL R， SRIKANT R. Mining sequential patterns： generalizations and performance improvements[C]// Proceedings of 5th Int Conf Extending Database Technology （EDBT）. Avignon： Lecture Notes in Computer Science， 1996： 3?17.
[12] MOHAMMAD El?Hajj， OSMAR R， ZA Iane. Parallel leap： large?scale maximal pattern mining in a distributed environment [C]// Proceedings of the 12th International Conference on Parallel and Distributed Systems. Washington D.C， USA： IEEE， 2006： 135?142.
[13] 郑亚军，胡学钢.基于PFP的关联规则增量更新算法[J].合肥工业大学学报（自然科学版），2015（4）：500?503.
[14] PEI J， HAN Jiawei， MORTAZAVI?ASL B， et al. PrefixSpan： mining sequential patterns efficiently by prefix?projected pattern growth [C]// Proceedings of 2001 Internationaol Conf on Data Engineering. Heidelberg， Germany： [s.n.]， 2001： 215?224.
[15] KO R K L. Data accountability in cloud systems [J]. Security， privacy and trust in cloud systems， 2013， 35： 211?238.
摘 要： 云存储将网络中大量不同类型的存储设备集合起来协同工作，共同对外提供数据存储服务。由于其特征上存在着用户和服务商之间的信任博弈，因此构建一个健康、公平、安全的云数据服务环境，对云数据的状态及操作过程执行客观、公正的安全审计尤为重要。为此，提出一种基于用户行为日志分析的云安全审计解决方案，通过制定数据“用户行为”描述，从功能上实现基于用户行为的系统日志信息分析，同时改进现有关联规则挖掘算法，提出一种针对长序列的关联规则挖掘算法。最后通过实验表明该方案可有效地实现云安全审计中隐私数据泄露的追踪与取证。
关键词： 云安全审计； 日志分析； 关联规则； 追踪与取证
中图分类号： TN911?34； TP309.2 文献标识码： A 文章编号： 1004?373X（2017）02?0001?05
Abstract： Cloud Storage provides data storage service for external by combing and coordinating different types of storage devices in the network， so that they can collectively work together. However it always exists a trust game relationship between users and service providers， therefore it is important to build a healthy， fair and secure cloud data service environment for the security auditing on the state of cloud data and operation processes. A cloud security?auditing scheme based on analysis of user behavior （UB） log data from cloud servers is proposed in this paper. The system log information analysis based on UB is realized functionally by description rules of UB. And the existing association rule mining algorithm is improved simultaneously， which is proposed for dealing with the Long Sequence Frequent Pattern （LSFP） to extract UB. The experiment result indicates that the solution can implement the tracking and evidence taking of data leakage efficiently for the cloud security auditing.
Keywords： cloud security auditing； log analysis； association rule； data tracking and evidence taking
0 引 言
云計算已然成为当今最热门的应用及研究领域，但云计算所需的对于数据和资源的共享所带来的云数据安全问题，一直是限制云计算技术发展的重要因素[1]。惠普在2000年提出了“可信云”的概念，并提出了云数据安全的理论模型[2]——CALC（Cloud Accountability Life Cycle）。在CALC模型中，将云数据安全的整体解决方案描述为一个环形结构，将整个数据安全过程分为：策略、追踪、日志、存储、报告、审计、整理7个环节，每个环节都对其下的环节提供支持，而整个过程的结果也反过来支持最初的策略环节，整个安全过程是递进优化的。
在此基础上，Ryan等人针对日志采集[3]（Logging）环节，提出了Flogger[4]，S2Logger[5]等一系列的解决方案。其基本思想是对整个云数据环境下主机的操作系统日志进行采集，通过分析日志，得到云环境下数据使用的具体情况。这种区别于以往对数据出、入口进行检测的方法[6?7]，可以得到在整个云环境内数据被使用的真实情况。解决了以往数据安全方案中“整个云环境安全可信”这个不可自立[7]的前提，并使“可信云”可被证实。但随着数据规模的不断增大，将日志分析仅仅停留在日志采集阶段已经无法满足云计算“受信”的基本要求。迫切地需要一种对日志数据进行归纳分析的方法，即在R&R（Reporting and Replaying）阶段进一步对日志进行处理。
基于这种思路的数据安全方案，将在多个环节对现有方案有所改进：在“存储”阶段，因为日志分析的引入，将原本的描述系统操作行为的日志，转化成为描述“用户行为” [8]的信息，使得日志数据的数量大幅精简；而在“报告”和“审计”阶段，本方案提供可读性更高、更符合实际的描述信息，使数据安全审计变得更加面向用户，为云环境的“可信性”提供更好、更直接的证实和支持；在“整理”和“策略”阶段，由于本方案提供的记录信息更能够准确描述现实情况，也使得“策略”的制定从原本的技术层面升级到对现实行为的约束，使责任追究变得更加简单、准确。
为此引入一种近年来主要用于知识发现（KDD），并在数据挖掘（Data Mining）和数据分析（Data Analyze）领域取得较好成果的方式——关联规则挖掘（Association Rule Mining）。算法本身是为了解决经典的“购物篮”问题而提出的，通过分析顾客购买商品的情况，得到不同商品之间的联系（基于统计学的联系，而不是逻辑上的因果联系）。
本文对频繁模式发现算法FP?Growth进行了研究，并针对云安全审计中数据日志分析的实际需求，提出一种实际可行的改进算法，旨在将关联规则挖掘引入特定模式数据集的分析过程。
1 相关理论知识
1.1 关联规则算法分析
Agrawal于1993年首次提出关联规则算法，以解决挖掘顾客交易数据中项集的关联性问题。其基本思路是找到数据中频繁性满足要求的多项集，再以此为基础分析项之间隐含的关联性。在此基础上，研究人员进行了大量的研究工作，主要在算法性能和面向对象上对算法进行了改进和扩展。
在性能改进方面比较突出的有Apriori算法和FP?Growth算法[9]。Apriori算法基于一种迭代的思想，逐步产生关联性分析所需要的多项集，以此尽可能得到包含更多项的集合，以达到良好的分析结果。而FP?Growth算法是由韩家炜在2000年提出的，针对Apriori算法需要迭代产生多项集而带来的算法时空复杂度问题，通过引入“树”的概念，将迭代过程改进为通过一次扫描数据集以生成“频繁模式树（FP?tree）”，通过这种树形结构表示数据集的频繁性，再通过树的搜索算法得到频繁多项集。因其性能较优，已成为当今主流的关联规则挖掘算法。
而在面向对象方面，AprioriAll[10]算法在Apriori算法的基础上，对事务集加入了时间约束，以分析短序列集合中项之间的关联性。
AprioriAll算法，在每一次扫描数据库时，利用上一次扫描时产生的序列生成候选序列，并在扫描的同时计算它们的支持度，满足支持度的候选序列作为下次扫描的序列。
GSP算法[11]是AprioriAll算法的扩展算法。在GSP算法中，引入了时间约束、滑动时间窗和分类层次技术，增加了扫描的约束条件，有效地减少了需要扫描的候选序列的数量，同时还克服了基本序列模型的局限性，更切合实际，减少多余无用模式的产生。另外，GSP利用哈希树来存储候选序列，减少了需要扫描的序列数量，同时对数据序列的表示方法进行了转换，这样就可以有效地发现一个候选项是否是数据序列的子序列。
Apriori及其改进算法，在数据集较大的情况下，会产生大量的中间集（候选集），使算法的时空复杂度变大，对大数据模型的效率不能令人满意。
FP?Growth算法通过引入图形结构，使得其算法结构更加适应于新型的计算框架和数据库结构。而基于FP?Growth的改进算法，将工作重心更多地投入当今流行的分布式计算[12?13]、投影数据库[14]方向，并取得了大量的成果。但FP?Growth及其改进算法，由于算法过程依赖“树”型结构，因此不能解决序列等包含其他约束条件数据集的挖掘。
1.2 约束规则
通过分析，对关联规则算法的改进，其本质都是一种约束条件的引入。Apriori算法基于一种简单的逻辑约束，即“任何一个频繁集的子集一定是频繁的”。而FP?Growth算法则是通过“树”的引入，将这种约束更加显性的表述，以提升算法效率。而AprioriAll和GSP算法，则是通过对数据集引入时间约束，有效地过滤了“无用”的多项集。
从挖掘所使用约束的类型看，可以把用于关联规则挖掘的约束分为：
（1） 单调性约束（Monotone Constraint）。所谓一个约束是单调性的约束，是指满足的任何项集的超集也能满足。
（2） 反单调性约束（Anti?monotone Constraint）。约束是“反单调的”，是指对于任意给定的不满足的项集， 不存在的超集能够满足。
（3） 可转变的约束（Convertible Constraint）。可转变的约束是指约束条件可以在项集和它的子集间传递。如果一个约束无法用单调或反单调形式给出，那么就给使用上带来困难，于是可通过对数据的特殊组织等方式使问题得到转换。
（4） 简洁性约束（Succinct Constraint）。简洁性约束是指对一个项目子集可以用选择性谓词来表示成选择操作。很显然，如果一个约束是简洁的，那么就可以直接使用SQL查询来得到满足条件的集合。在挖掘的不同阶段可以尽量尝试简洁性的约束，这样可以避免不必要的测试。
按照挖掘所使用约束条件的来源，又可将约束进行如下分类：
（1） 知识类型约束。利用知识背景可以过滤无关信息。
（2） 数据约束。利用数据的某些属性，可以隔离与当前问题无关的信息。
（3） 维、层、度约束。利用数据或数据库的结构和规模，将数据挖掘限定在某个区间，以滤除“额外”信息。
2 长序列关联规则算法
随着当今网络技术的发展，对于流数据等具有强时间约束的数据集的关联规则挖掘方法越来越值得重视。而通过对以往研究成果的分析，发现关联规则挖掘的对象依然停留在离散的数据上。即便如GSP算法将时间约束引入事务，其面向的数据集（事务集）依然是离散的。在针对长序列结构的数据集时，依然不能满足功能需求。
基于对已有研究成果的分析，本方案在FP?Growth算法基础上，引入合理的约束条件，即强时间约束。并与之匹配的引用“有向图”这一图形结构，以直观的表述约束条件。通过对算法结构的改造和新模型的引入，设计一种面向长序列的关联规则挖掘算法Long Sequence Frequent Pattern（LSFP）。
2.1 LSFP算法描述
針对数据集强时间约束的特点，传统FP?Growth算法构造的频繁模式树结构，并不能有效地描述数据集的有序性，在针对序列类型的数据集时，数据本身的性质可能使得频繁模式树规模过大而不可用。其根本是因为树型结构更易于表述节点之间的联系，而数据的有序性使得节点之间的“边”具有描述更多数据含义的能力，针对有序数据，需要一种能够直观表述“边”之间关系的图形结构。为此，本方案引入一种新的图形结构，即有向图。对于序列，这种结构的优势主要体现在两个方面：
（1） 有向图不同于树型结构，有向图中的“边”描述了“从节点到节点”的转移关系，这种转移关系，可以有效地描述强时间约束的数据集中“有序性”的信息。
（2） 有向图的结构保证在图里没有重复出现的节点，相比于树形结构，有向图为算法提供了空间复杂度上的改进。
基于这种思想，提出算法结构和流程设计。
算法分为2步：一是算法训练阶段，通过训练集得到整个数据集的频繁性；二是分析挖掘阶段，通过之前得到的数据频繁性，得到数据集中满足频繁性的“UB（短序列）”。算法相关参数定义如表1所示。
在项集中，节点包含属性和，用以描述节点是否可作为一个UB（User Behavior）的起始节点和终止节点。
2.2 算法步骤
算法第一阶段：
Step1：扫描训练集，生成项集；
Step2：生成有向图，并以关联矩阵描述；
Step3：选择恰当的阈值，对有向图进行剪枝；
Step4：引入先验规则，优化关联矩阵，得到数据完整频繁特征；
Step5：通过有向图搜索，得到可能的“用户行为”短序列（即事务）格式。
算法第二阶段：
Step1：根据关联矩阵描述的数据频繁性，将长序列拆分成若干较短序列，形成待挖掘的序列集；
Step2：在序列集中挖掘出“行为”，生成“行为集”。
3 算法实现及性能分析
3.1 实验环境
针对算法设计思路和实际问题，本方案选择通过采集得到的Linux操作系统日志作为算法实现的数据集，因为其具有良好的时间属性，并具有很好的代表性。并根据算法的复杂度选择适合的软、硬件环境。
3.1.1 算法环境
算法环境如表2所示。
3.1.2 算法参数
算法参数对性能的影响主要包含两个方面：训练集规模和最小支持度。训练集规模：算法选择使用数据集的一部分作为获取频繁性的训练集，主要是因为来源相同的数据集和训练集拥有相似的数据频繁特性，使得通过分析训练集得到的频繁性对于数据集同样是适用的。当使用整个数据集作为训练集的时候，数据集和训练集必定拥有相同的频繁性。但过大的训练集会使算法的整体效率降低，于是选择规模恰当的训练集，对算法性能有巨大的影响。最小支持度：最小支持度决定了算法认为哪些操作组合可以被认为是一种“用户行为”。当选择较小的支持度，必然会得到更多的“操作组合”，但这些组合是否足够频繁使其可以被看作一种“行为”却无法保证；当选择较大的支持度，可以保证“操作组合”即是“用户行为”的准确性，但必然会使算法得到的操作组合变少。
3.2 算法分析
在进行算法性能分析之前，需要对算法结果有一个直观的认识。在此将几个常见的用户行为所对应的操作系统日志序列（规则）展示如下：
（1） 文件创建
Create，wzq，3103，2406，2406，2387，nautilus，/home/wzq/De
sktop/test/new file，/home/wzq/，193，438，30
Close，wzq，3103，2406，2406，2387，30
（2） 文件复制
Open，wzq，3354，3054，3054，2752，test，log，/home/wzq/Desk
top/test/，577，438，4
Close，wzq，3355，3354，3054，2752，3Duplicate2，wzq，3355，
3354，3054，2752，4，1Close，wzq，3355，3354，3054，2752，4
（3） 文件编辑
Move，wzq，2956，2928，2928，2856，vim，aaa.txt，aaa.txt～，
/home/wzq/Desktop/test/
Create，wzq，2956，2928，2928，2856，vim，aaa.txt，/home/wzq/
Desktop/test/，577，436，3
Write，wzq，2956，2928，2928，2856，3，0，6F6E650A0A
Read，wzq，2856，1，2424，2405，21，0，
0D1B5B3F32356C226161612E747B7422
Close，wzq，2956，2928，2928，2856，3
Chmod，wzq，2956，2928，vim，aaa.txt，33204
前文中，从理论上分析了算法性能的影响因素。这里通过实验数据对算法性能进行直观的反映。
3.2.1 针对训练集的算法性能分析
数据集和训练集大小，是指在日志采集后经过“预处理”的数据大小。因为日志采集过程中会产生大量的与数据操作无关的系统日志信息，占原始日志数据的80%。为分析训练集规模对算法性能的影响，选择相同的数据集和最小支持度，评价算法性能的主要指标有得到的“规则”数、得到的“行为”数、运行时间。
实验结果分析如下：
（1） 规则数与行为数。在实验过程中，随着训练集规模从1 MB逐渐增大到10 MB，通过算法训练阶段可以得到更“完整”的规则信息，针对相同的数据集，得到的行为数从400余条增长到900余条。两者与训练集规模基本呈非線性对数关系。如图1所示。
（2） 算法运行时间。训练集规模直接相关，随着训练集规模增大，算法训练阶段所需时间也相应提高，两者间的关系基本呈线性。而随着训练集的增大，得到的“规则数”也增大，但两者基本保持对数关系。而“规则数”的增大，也导致了算法挖掘“行为”阶段需要对比更多“规则”。在实验过程中，随着训练集规模从1 MB逐渐增大到10 MB，算法运行时间从400 ms增长到900 ms。算法运行时间与训练集规模基本呈线性关系。如图2所示。
3.2.2 针对最小支持度的算法性能分析
关联规则算法的最小支持度可以通过多重方式获得，这也是相关改进算法研究的一个重要方面，在这里，只分析选用不同的支持度对算法性能的影响，对于计算最小支持度的算法不做讨论。为分析最小支持度对算法性能的影响，选择相同的數据集和训练集，评价算法性能的主要指标有：得到的“规则”数、得到的“行为”数、运行时间。实验结果分析如下：
（1） 规则数与行为数。随着最小支持度的减小，必将使得到的规则数变大，也导致算法挖掘阶段得到更多的行为数。在实验过程中，随着最小支持数从20逐渐增大到100，行为数从1 200余条减小到400余条，行为数、规则数与最小支持度基本呈非线性指数关系。但最小支持度的减小，也会把原本“不频繁”的操作组合认定为一种频繁的规则，这使得最终得到的行为在准确性方面有所不足，如图3所示。
（2） 算法运行时间。由于训练集大小不变，所以算法训练阶段所需时间保持不变。但由于最小支持度变小，使得得到的规则数增大，导致算法挖掘阶段的时间消耗变大。在实验过程中，随着最小支持度从20逐渐增大到100，运行时间从1 200 ms减小到400 ms。运行时间与最小支持度基本呈非线性指数关系，如图4所示。
4 结 语
本文从解决云数据安全性这个实际问题出发，分析了已有解决方案优劣，并研究、分析了现今在数据挖掘领域较主流的关联规则挖掘算法。借鉴关联规则的思想，设计并实现了一种针对主机操作系统日志的模式挖掘算法，将描述系统操作的进程级日志数据转化为描述用户行为的日志，为云数据安全审计提供更合适的信息。在以后的工作中，算法依然有需要改进的方面：
最小支持度的获得。通过实验可知，最小支持度对算法结果和过程的效率都有直接的影响。在本文的实验范围内，通过人为的设定一个阈值的方式获得最小支持度，并尝试改变阈值，分析最小支持度对算法结果和算法效率的影响。在现今的研究中，通过数据集的特征计算最小支持度的方式越来越主流，相应的计算方法也各有优劣。在今后的工作中，将基于系统操作日志这个特定的数据集，设计并实现适合的最小支持度计算方法，改进算法性能。
算法在不同环境下的性能分析。在本文的实验范围中，将实验环境设定在单用户主机情景下。在这种情景下，用户对文件进行的操作比较简单，操作过程也相对容易理解、分析。在联机环境或服务器环境下，通过日志分析表现出的行为模式必定与本文的实验环境不同。在今后的工作中，将在不同的环境下进行实验，并分析不同环境下的行为模式。以期达到日志分析的最终目的：为数据安全策略的制定提供现实依据。
参考文献
[1] TU Shanshan， HUANG Yongfeng. Towards efficient and secure access control system for mobile cloud computing [J]. China communications， 2015， 12（12）： 43?52.
[2] KO R K L， JAGADPRAMANA Peter， MOWBRAY Miranda， et al. TrustCloud： A framework for accountability and trust in cloud computing [C]// Proceedings of the 2011 IEEE World Congress on Services. [S.l.]： IEEE， 2011： 584?588.
[3] KO R K L， KIRCHBERG M.， LEE B S. From system?centric to data?centric logging? accountability， trust and security in cloud computing [C] // Proceedings of Defense Science Research Conference and Expo. [S.l.： s.n.]， 2011： 1?4.
[4] KO R K L， JAGADPRAMANA P， LEE B S. Flogger： a file?centric logger for monitoring file access and transfers with cloud computing environments [C]// Proceedings of 3rd IEEE International Workshop on Security in e?Science and e?Research （ISSR 11）. [S.l.]： IEEE， 2011： 11?16.
[5] SUEN C H， KO R K L， TAN Y S， et al. S2Logger： end?to?end data tracking mechanism for cloud data provenance [C]// Proceedings of 12th IEEE International Conference on Trust， Security and Privacy in Computing and Communications. [s.l.]： IEEE， 2013： 123?130.
[6] MUNISWAMY?REDDY K K， HOLAND D A， BRAUN U， et al. Provenance?aware storage systems [C]// Proceedings of 06 Annual Technical Conference on USENIX. [S.l.： s.n.]， 2006： 6?11.
[7] MUNISWAMY?REDDY K K， BRAUN U， HOLAND D A， et al. Layering in provenance systems [C]// Proceedings of the Annual Technical Conference of USENIX. [S.l.： s.n.]， 2009： 11?16.
[8] 肖传奇，陈明志.云环境下基于IFAHP的用户行为信任模型研究[J].信息网络安全，2015（12）：14?20.
[9] HAN J W， PEI J， YIN Y W， et al. Mining frequent patterns without candidate generation [J]. Data mining and knowledge discovery， 2004， 8（1） ： 53?87.
[10] AGRAWAL R， SRIKANT R. Mining sequential patterns [C]// Proceedings of 1995 Int Conf Data Engineering （ICDE 95）. Taipei， China： IEEE Computer Society， 1995： 3?14.
[11] AGRAWAL R， SRIKANT R. Mining sequential patterns： generalizations and performance improvements[C]// Proceedings of 5th Int Conf Extending Database Technology （EDBT）. Avignon： Lecture Notes in Computer Science， 1996： 3?17.
[12] MOHAMMAD El?Hajj， OSMAR R， ZA Iane. Parallel leap： large?scale maximal pattern mining in a distributed environment [C]// Proceedings of the 12th International Conference on Parallel and Distributed Systems. Washington D.C， USA： IEEE， 2006： 135?142.
[13] 郑亚军，胡学钢.基于PFP的关联规则增量更新算法[J].合肥工业大学学报（自然科学版），2015（4）：500?503.
[14] PEI J， HAN Jiawei， MORTAZAVI?ASL B， et al. PrefixSpan： mining sequential patterns efficiently by prefix?projected pattern growth [C]// Proceedings of 2001 Internationaol Conf on Data Engineering. Heidelberg， Germany： [s.n.]， 2001： 215?224.
[15] KO R K L. Data accountability in cloud systems [J]. Security， privacy and trust in cloud systems， 2013， 35： 211?238.
