基于离散马尔科夫链的数据库用户异常行为检测<span class="superscript">*</span>

摘要：针对数据库系统内部攻击的问题，将基于用户行为的异常检测方法引入到数据库系统内部攻击检测中.将离散时间马尔科夫链(DTMC)应用到数据库系统异常检测中，构建了一种基于DTMC的用户行为异常检测系统.将用户提交的SQL语句作为用户行为特征进行分析，并利用DTMC分别提取了正常用户和待检测行为的行为特征，并将两者进行比较，如果两者的偏离程度超过了阈值，则判定行为异常.通过实验对所提出系统的可行性和有效性进行测试，结果表明，该系统可以较好地描述用户行为，并有效地检测出数据库系统内部攻击.

关键词：网络安全；数据库安全；用户行为；内部攻击；异常检测；入侵检测；SQL语句；离散马尔科夫链

随着计算机以及网络技术的飞速发展，计算机网络对社会发展起到了巨大的推动作用.但是，这也带来了诸多的网络安全问题，例如数据窃取、敏感信息泄露以及网络欺诈等.尽管研究人员已经开发了多种网络安全保护技术和产品，例如防火墙、入侵检测、入侵防御、隔离网闸以及主机审计等，但是，无论在发达国家还是在发展中国家，网络安全问题仍然日益严重，信息安全风险[1]正在加大，已经成为信息时代人类必须面临的共同挑战[2].

目前，学术界和企业界在网络安全方面投入了大量的精力，并取得了丰硕的研究成果，但是，对于数据库安全方面的研究则相对薄弱.然而，在信息系统的整体安全中，数据库往往是最吸引攻击者的目标，许多网络攻击的根本目的就是获取存放在数据库中的重要信息.传统的数据库安全保障方法[3]在一定程度上提高了数据库系统的安全性，但是它们大多是被动的安全技术，以预防为主，无法有效地制止入侵行为，特别是对于数据库用户(如数据库管理员等)的权限滥用等内部攻击常常是无能为力的.据统计，对数据库的攻击80%来自内部，内部攻击是数据库系统的主要威胁.因此，针对数据库系统中用户异常行为检测研究就显得尤为重要.

基于异常的入侵检测是入侵检测研究领域中的一个重要课题，并取得了一定的研究成果[4-6].但是，这些研究成果主要针对操作系统和计算机网络，针对数据库系统的研究成果则相对较少.Chung等人将数据库系统的语义和异常检测系统研究紧密结合起来，提出使用用户轮廓检测数据库用户的行为，并研发出了数据库误用入侵检测系统原型[7].之后，相关企业也推出了一系列数据库入侵检测产品，如Application Security Inc公司的数据库入侵检测产品AppRadar，它可针对不同的数据库设计不同的入侵检测系统.李银钊等人构建了一种基于自适应模型数据库入侵检测方法[8]，该方法是基于矩阵和最小支持度函数的Apriori Z 关联算法，在训练和自适应入侵检测阶段产生数据库的操作特征，用户根据实际需求动态调整最小支持度函数的值，更高效地挖掘操作特征.陈大鹏提出了基于网络用户行为分析与识别的数据库入侵检测系统[9]，并给出了神经网络算法在数据库用户行为入侵检测上的应用实例.陈炜利用基于聚类分析与关联规则挖掘的数据库异常检测技术，对数据库操作行为和数据操作进行审计分析，建立用户正常的行为模式，并通过编写异常检测算法来检测用户的异常行为[10].

本文提出了一种基于DTMC的数据库用户异常行为检测方法，该方法将用户提交的SQL语句作为用户行为特征，并利用DTMC进行提取和分析，之后通过计算出的阈值进行判断，最后利用相关实验数据集进行测试，结果表明，本文系统可以有效地检测出数据库系统内部的攻击行为.

1 离散马尔科夫链

定义1一个随机过程{Xn，n≥1}称作具有状态空间S={1，2，…，∞}的(一阶)离散时间马尔科夫链(discrete-time Markov Chain，DTMC)，如果对所有的n≥1，j∈S和sm∈S(1≤m≤n)，则有

定义2一个DTMC{Xn，n≥1}称作时间齐次的，如果它满足不动性假设，即对所有的j∈S和i∈S，条件概率Pr(Xn+1=j|Xn=i)与n无关.

当DTMC{Xn，n≥1}是时间齐次时，pij=Pr(Xn+1=j|Xn=i)称作(一步)转移概率，由(一步)转移概率pij构成的矩阵P=[pij]称作(一步)转移概率矩阵.ai=Pr(X1=i)称作状态i的初始出现概率，由状态的初始出现概率构成的行向量A=(ai)i∈S称作初始概率分布.

定理1时间齐次的DTMC{Xn，n≥1}由初始概率分布A和转移概率矩阵P完全刻画，即

定义3一个DTMC{Xn，n≥1}称作平稳的，则其初始概率分布A和转移概率矩阵P满足

2 系统分析与设计

2.1 检测流程设计

在本文系统中，用户行为异常检测是建立一个合法用户的正常行为模式，通过比较该合法用户的当前行为和正常行为特征来识别异常行为，即如果该合法用户的当前行为较大幅度地偏离了其历史上的正常行为特征，则认为发生了异常.这种异常可能是该合法用户本身进行了非授权操作，也可能是系统中其他合法用户或外部入侵者(非法用户)冒充该合法用户进行了非法操作.

在数据库系统中，用户主要通过SQL语句与数据库管理系统进行交互，完成信息的查询、修改以及删除等操作.通过分析SQL语句的执行序列，就可以较为全面地描述用户的行为特征.分析SQL语句的优点在于：当查询通过异常检测系统的处理时，系统负载较轻.一个新的SQL语句被分析并通过一些统计模型检查，仅当查询被异常检测系统所接受时才在数据库管理系统中运行.

在本文系统中，基于用户行为的异常检测主要包括两个过程，即训练过程和检测过程.

1) 在训练过程中，使系统在正常情况下运行一段时间，收集正常运行时的数据，提取用户行为特征，建立正常的用户行为模式(应该使建立的行为特征模式包括尽可能多的正常的系统行为).

2) 在检测中，使系统运行于实际的环境中，收集当前用户的行为数据并提取行为特征，比较检测用户的行为特征与正常行为特征，通过对比观察正常与当前行为特征的偏离程度判断是否发生了异常.

1) 数据预处理阶段.在该阶段对用户提交给数据库系统的SQL语句，即数据库用户行为，进行采集和预处理.

2) 训练阶段.在该阶段分析用户行为特征，获取用户正常行为模式.训练阶段和检测阶段的流程图如图1所示.在训练阶段，采集的是用户一段时间内正常操作的数据，如日志文件中的SQL语句等，从中提取用户正常状态下的行为规律，作为历史行为模式.提取训练序列的行为特征，建立正常序列库，运用DTMC得到训练序列的马尔科夫链状态集，并计算该马尔科夫链状态的转移概率矩阵，以此来描述用户的正常行为.

3) 检测阶段.在该阶段采集被检测用户的操作数据.提取检测数据中的行为特征作为当前被检测用户的行为特征.将被检测用户的行为特征与历史行为特征进行对比，判断当前行为是否为异常行为.如果两者的偏离超过一定阈值，则认为是异常的；如果两者的偏离在正常范围内，则认为行为是正常的.

图1训练阶段和检测阶段流程
Fig.1Flowchartoftraininganddetectingstages

2.2 系统功能设计

本文系统主要包括三个功能模块：数据预处理模块、数据训练模块和异常检测模块.

1) 数据采集子模块.在本文系统中，采用SQL语句作为异常检测的数据源，因此，需要收集数据库日志文件中的用户SQL操作请求.

2) 预处理子模块.在该模块中主要是对收集到的数据进行处理和加工，使之符合下一个模块的输入.根据正常序列库(library of general sequence，LGS)的要求，需要将收集到的所有数据处理成一个序列.因此，需要将SQL请求中的关键字提取出来，组合成为一个训练序列.在实现过程中，由于SQL语句的关键字通常为多个字母的英文单词，在训练和检测过程中操作较为复杂，为了优化算法的执行效率，将关键字进行统计分类，由单个英文字母代替.

数据训练模块包括序列库建立子模块和基于DTMC的行为特征提取子模块.

1) 序列库建立模块.对于经过预处理的序列，定义W种不同长度的短序列，并设置相应的出现频率权重.

定义4x=(x1，x2，…，xn)是一个序列，

被称作x的一个流，其中

是由x截取的长度为k的短序列.另外，由于流

的长度由k决定，

也称为由x生成k长度的流.

l(i)代表第i种短序列的长度，e(i)代表第i种短序列的出现频率权重，其中，i=1，2，…，W，l(1)<l(2)<…<l(W).

获得经过预处理的数据，并生成W种不同长度短序列.经过采集、预处理的数据最终会形成一个序列，由s=(s1，s2，…，sr)表示，其中，r表示序列中SQL查询字段的个数，sj′(1≤j′≤r)表示序列s中的第j′个字段.生成序列s=(s1，s2，…，sr)的W种不同长度的流

是长度l(i)的流，并且有

提取每个流中不同的短序列，并计算其出现频率.在数据流

中，不同的短序列种类可以表示为

是数据流

中不同的短序列种类个数，按照定义5计算每一种短序列的出现频率.

定义

是长度为l(i)的短序列，

表示

在数据流

中出现的次数，则

在

中出现的频率为

将所有数据流中全部的不同短序列合并到正常序列库中，并计算其在正常序列库中的加权出现频率.

将所有的不同短序列合并到正常序列库中，则正常序列库LGS可以表示为

中各种短序列的加权出现频率计算方法如定义6所示.

按照每种短序列的加权出现频率的大小进行排序，并将其分成N-1组.按照加权出现频率对所有不同种类的短序列进行降序排序后，得到的结果可以表示为

其中H=m(1)+m(2)+…+m(W).N表示状态数，u表示不大于H/(N-1)的最大整数，且v=u+1，h=H-(N-1)u.T中前hv个序列分成h组，每组v个序列.余下的(N-h-1)u个序列分成N-h-1组，每组u个序列.由此所有种类的短序列按照加权出现频率被分成了N-1组，分别表示为Λ1=

2) 基于DTMC的行为特征提取模块.在检测异常行为之前，系统需要建立用户正常行为的行为特征.本文利用不同长度短序列的状态构建离散时间马尔科夫链，以此作为用户的行为特征.在本文方法里，状态数N需要提前设置.首先需要得到训练数据s=(s1，s2，…，sr)中每一个命令的行为模式；然后根据LGS中的N-1个分组，生成每一个行为模式的马尔科夫链状态，由此得到一个马尔科夫链状态集；最后建立马尔科夫链的转移概率矩阵P.

一旦用户行为特征形成，异常检测系统的基本操作就是比较检测序列与历史数据，并且判断两者是否属于同一个用户.被检测用户的行为特征与历史数据的偏离是入侵的重要标识，因此，假设历史数据都属于同一个用户.在本文系统的异常检测阶段，由转移概率矩阵决定的分类值是判定异常行为的唯一衡量标准，这将大大减轻系统的计算负担，系统的主要检测步骤如下：

1) 获取并预处理审计数据.在异常检测阶段，需要采集待检测用户产生的原始SQL命令行(即需要被审计的数据)，将采集到的数据经过预处理形成一个序列.c=(c1，c2，…，ct)表示经过预处理后的检测序列，其中，cj是检测序列中第j个命令，t代表检测序列中的命令个数.

2) 定义检测序列状态，生成状态序列.根据行为模式提取算法和Markov链状态生成算法，将正常序列库T和检测序列c=(c1，c2，…，ct)作为输入，可以得到与检测序列相对应的状态序列q=(q1，q2，…，qM′).由c=(c1，c2，…，ct)截取的短序列可能不包含在LGS中，因此在状态序列q=(q1，q2，…，qM′)中，状态值可能为N.

3) 对应状态序列获取分类值.在状态序列q=(q1，q2，…，qM′)中，对于每一个状态qi(1≤i≤M′-1)，由qi到qi+1的转移概率为Pr(qi+1|qi)=aqi，qi+1.从qi转移到qi+1的分类值定义为

式中：ψ(i)为从qi转移到qi+1的分类值；δ为概率临界值，需要提前设置.当ψ(i)=1时，代表一个正常的转移；否则，表示发生了一个异常的转移.计算所有状态的分类值之后，得到一个分类值的序列(ψ(1)，ψ(2)，…，ψ(M′-1)).

4) 计算判定值.虽然个别转移可能会偏离历史先例，但是有效用户大量的行为集合应该在主体上符合历史行为，而入侵者的行为与历史行为对比会有明显的偏离.因此，本文系统对分类值序列应用滑动窗口以获取大量的行为，然后计算其判定值.本文采用一种均值滑动窗口，在分类值序列(ψ(1)，ψ(2)，…，ψ(M′-1))中的ψ(n)处，其判定值定义为

式中：D(n)为分类值ψ(n)相对应的判定值，n逐次加1(w≤n≤M′-1)；w为窗口大小.

5) 判别用户行为是否异常.判定用户行为是否异常的阈值λ，需要根据系统需求提前设置，当前被检测用户的行为是否异常则由D(n)和λ决定.如果D(n)≥λ，认为被检测用户的当前行为是正常的，反之如果D(n)<λ，则认为被检测用户的当前行为是异常的.本文中，当前行为对应着w个分类值ψ(n-w+1)，ψ(n-w+2)，…，ψ(n)，与w+1个状态(qn-w+1，qn-w+2，…，qn，qn+1)相关.阈值λ是灵敏度很高的参数，阈值越高，异常检测成功率越高，同时误报率也越高；阈值越低，异常检测成功率越低，误报率也降低.

3 实验分析

3.1 测试指标

异常检测系统对异常行为的检测效果通常由检测率、误报率和漏报率三个参数来衡量.

定义8误报率.误报率是指正常的数据被误检为异常数据的比率，即

定义9漏报率.漏报率是指没有被检测出来的异常数据的比率，即

ROC(receiveroperatingcharacteristic)曲线，即接受者操作特征曲线，在信号检测理论中被用来表示检测率和误报率的折中.本文也将利用ROC曲线来分析系统的性能.ROC曲线左上角的点代表着100%的检测率和0%的误报率.因此，ROC曲线越靠近左上角，异常检测系统性能越好.

3.2 实验数据

实验使用的测试数据集是一个诊所的数据库集合[12]，包括39 322条select、insert、update、delete等SQL命令.从数据库日志文件中采集到的原始数据是SQL命令行.SQL命令里包含操作类型、操作对象、表名等大量命令字段.为了提高检测效率，需要对SQL语句进行预处理.

定义10语句模板是一个三元组〈OP，F，T〉，其中，OP是SQL语句的语句类型，F是SQL语句涉及的属性集，T是SQL语句中的表集合.

每条语句都可以归类到某个语句模板，实际使用过程中认为只要语句模板相同，则两条语句为同一类语句.

SQL语句1：“SELECT学号，姓名，年龄FROM学生表WHERE年龄<20”；语句2：“SELECT学号，姓名，年龄FROM学生表WHERE性别=男”；语句3：“SELECT学号，数学+语文AS总分FROM学生表，成绩表WHERE年龄<20”，3条语句的语句模板如表1所示.

表1SQL语句模板示例
Tab.1ExamplesofSQLstatementtemplate

由表1可知，将每一条SQL语句处理成语句模板，并按照时间先后排序生成语句模板的序列(OP1，F1，T1，OP2，F2，T2，…)，所有的训练数据和检测数据都需按照上述过程处理.

3.3 实验结果

本文选取了4个用户的数据用于实验，如果从4个用户中选择一个用户作为正常用户，其他3个用户相对于选定的用户来说就是异常用户.用户的变化会导致系统检测到的行为模式特征发生变化，如果变化值超出了正常范围内的波动，系统将会认定其为异常行为.

经过预处理后，用户1的前9 999个SQL命令字段用于训练阶段构建LGS和Markov链，剩余的4 998个SQL命令字段在检测阶段用作测试数据，作为正常行为来检测系统的误报率.用户2、用户3、用户4各有6 000条SQL命令字段用作异常行为来测试系统的检测率.系统各个参数设置为：N=5，W=3，l(1)=1，l(2)=2，l(3)=3，e(1)=1，e(2)=2，e(3)=3，w=81，δ=0.28.

表2给出了每个用户检测序列对应的Markov链状态数.由于LGS是由用户1的训练数据生成，那么由用户1的训练数据截取的短序列总是会出现在LGS中，因此，用户1检测序列状态为N的概率极低，也就是对应行为模式的长度为1的可能性较低.状态总数与行为模式的长度相关，行为模式的长度越大，状态总数越少，所以用户1检测序列的状态总数最少.

表2不同用户检测序列状态数
Tab.2Statusnumberofdifferentuserdetectingsequences

图2给出了4个用户的判定值曲线，从图2中可以看出，用户2、用户3和用户4的曲线可以很明显地与用户1的曲线区分开来，即不同用户的行为特征不同.一旦数据库出现内部攻击，攻击者的行为模式与正常用户的行为模式一定存在较大差异，被检测用户的判定值曲线会出现较大幅度的波动，当系统检测到波动已超过设定的阈值时，则可以认为该用户出现了异常.

实验表明，系统检测性能和所选定的阈值λ有很大关系，λ越大，系统的检测率和误报率会越高，漏报率越低.因此，要通过测试选定比较合适的λ值.另外，状态数N对系统的性能也会产生一定影响.图3为N等于4、5、6，阈值λ不同时，系统的ROC曲线.从图3中可以看出，N=5时，系统性能较N=6、N=4时更好，且λ=0.84时，系统性能达到最优.

图2各用户的ROC曲线
Fig.2ROCcurvesofvarioususers

图3状态数不同时系统ROC曲线
Fig.3ROCcurvesofsystemwithdifferentstatusnumber

4 结论

针对数据库系统中的用户异常行为检测问题，利用SQL语句来提取用户的行为特征，并应用离散Markov链的状态来描述用户的行为轮廓，设计并实现了基于DTMC的数据库用户异常行为检测系统，该系统包括数据预处理模块、数据训练模块和异常检测模块.为了验证系统的有效性，采用数据库日志数据进行实验测试.实验结果表明，离散Markov链的状态可以用于刻画数据库用户的行为轮廓，正常行为的判定值曲线和异常行为的判定值曲线可以很明显地区分开，从而证明了系统的有效性.因此，本文系统在数据库用户异常行为检测领域具有一定的实际应用价值.

[1] 赵刚，宫义山，王大力.考虑成本与要素关系的信息安全风险分析模型 [J].沈阳工业大学学报，2015，37(1)：69-74.

(ZHAO Gang，GONG Yi-shan，WANG Da-li.Information security risk analysis model considering costs and factors relevance [J].Journal of Shenyang University of Technology，2015，37(1)：69-74.)

[2] 沈昌祥，张焕国，冯登国，等.信息安全综述 [J].中国科学(E辑：信息科学)，2007，37(2)：129-150.

(SHEN Chang-xiang，ZHANG Huan-guo，FENG Deng-guo，et al.An overview of information security [J].Science in China (Series E：Information Sciences)，2007，37(2)：129-150.)

[3] 吴溥峰，张玉清.数据库安全综述 [J].计算机工程，2006，32(12)：85-88.

(WU Pu-feng，ZHANG Yu-qing.An overview of database security [J].Computer Engineering，2006，32(12)：85-88.)

[4] Joldzic O，Djuric Z，Vuletic P.A transparent and sca-lable anomaly-based DoS detection method [J].Computer Networks，2016，104：27-42.

[5] Bhuyan M H，Bhattacharyya D K，Kalita J K.A multi-step outlier-based anomaly detection approach to network-wide traffic [J].Information Sciences，2016，348(6)：243-271.

[6] 徐明，陈纯，应晶.一个两层马尔科夫链异常入侵检测模型 [J].软件学报，2006，16(2)：276-285.

(XU Ming，CHEN Chun，YING Jing.A two-layer Markov chain anomaly detection model [J].Journal of Software，2006，16(2)：276-285.)

[7] Chung C Y，Gertz M，Levitt K.DEMIDS：a misuse detection system for database system [C]//Proceedings of 3rd International Working Conference on Integrity and Internal Control in Information Systems.Amsterdam，Netherlands，1999：159-178.

[8] 李银钊，闫怀志，张佳，等.基于自适应模型的数据库入侵检测方法 [J].北京理工大学学报，2012，32(3)：258-262.

(LI Yin-zhao，YAN Huai-zhi，ZHANG Jia，et al.A method of database instruction detection based on adaptive model [J].Transactions of Beijing Institute of Technology，2012，32(3)：258-262.)

[9] 陈大鹏.基于用户行为分析与识别的数据库入侵检测系统的研究 [D].成都：电子科技大学，2015.

(CHEN Da-peng.Intrusion detection system of database based on user behavior of analysis and identification [D].Chengdu：University of Electronic Science and Technology of China，2015.)

[10]陈炜.基于网络的数据库审计和风险控制研究 [D].武汉：武汉理工大学，2013.

(CHEN Wei.The research about database audit and risk management based on network [D].Wuhan：Wuhan University of Technology，2013.)

[11]Karlin S，Taylor H M.A first course in stochastic processed [M].Beijing：Post & Telecom Press，2007：30-60.

[12]Yao Q S，An A J，Huang X J.Finding and analyzing database user sessions[C]//10th International Conference on Database Systems for Advanced Applications.Beijing，China，2005：851-862.

Anomalybehaviordetectionofdatabaseuserbasedondiscrete-timeMarkovchain

(1.Software College, Northeastern University, Shenyang 110169, China; 2.School of Management, Shenyang University of Technology, Shenyang 110870, China; 3.State Key Laboratory of Information Security, Institute of Information Engineering of Chinese Academy of Sciences, Beijing 100093, China)

Abstract：Aiming at the problem of internal attack in the database system, an anomaly detection method based on the user behaviour was introduced into the internal attack detection in the database system.The discrete-time Markov chain (DTMC) was applied to the anomaly detection of database system, and an anomaly detection system for user behaviour based on DTMC was established.The SQL statements submitted by the users were taken as the user behavior features and were analyzed.In addition, the behavior features of normal users and behavior to be detected were extracted with DTMC, and the corresponding comparison between them was performed.If the deviation degree of two behavior features was beyond the threshold, the detected behavior would be judged as an anomaly behavior.The feasibility and effectiveness of the proposed system were actually tested.The results show that the proposed system can better describe the user behavior, and can effectively detect the internal attack of database system.

Key words：network security; database security; user behavior; internal attack; anomaly detection; intrusion detection; SQL statement; discrete-time Markov chain(DTMC)

基金项目：国家自然科学基金资助项目(61602102，61402095)；辽宁省科技攻关计划项目(2013217004)；中央高校基本科研业务费专项基金资助项目(N151704002)；沈阳市科技计划资助项目(F14-231-1-08).

作者简介：毕猛(1982-)，男，辽宁沈阳人，工程师，博士生，主要从事网络与信息安全等方面的研究.

* 本文已于2017-10-25 21∶12在中国知网优先数字出版.网络出版地址：http：//kns.cnki.net/kcms/detail/21.1189.T.20171025.2112.028.html

(1.东北大学软件学院，沈阳 110169；2.沈阳工业大学管理学院，沈阳 110870；3.中国科学院信息工程研究所信息安全国家重点实验室，北京 100093)

基于离散马尔科夫链的数据库用户异常行为检测*