正文

学点算法搞安全之hmm(上篇)

author  author  2022-08-31  722

关键词：

前言

　　隐式马尔可夫（HMM），也称韩梅梅，广泛应用于语音识别、文本处理以及网络安全等领域，2009年I Corona，D Ariu，G Giacinto三位大神关于HMM应用于web安全领域的研究论文，让HMM逐渐被各大安全厂商重视。本篇重点介绍HMM最常见同时也比较基础的基于url参数异常检测的应用，后继文章将介绍HMM结合NLP技术在XSS、SQL、RCE方面的应用。"多一个公式少一半读者"，所以霍金的《时间简史》和《明朝那些事》一样畅销，我的机器学习系列文章都是尽量少讲概念，多讲例子，希望可以让机器学习被更多人了解和使用。

HMM基础原理

　　现实世界中有一类问题具有明显的时序性，比如路口红绿灯、连续几天的天气变化，我们说话的上下文，HMM的基础假设就是，一个连续的时间序列事件，它的状态受且仅受它前面的N个事件决定，对应的时间序列可以成为N阶马尔可夫链。

　　假设今天是否有雾霾只由前天和昨天决定，于是就构成了一个2阶马尔可夫链，若昨天和前天都是晴天，那么今天是晴天概率就是90%。

　　稍微再复杂点，假设你想知道2000公里外一个城市的雾霾情况，但是你没法直接去当地看到空气情况，手头只有当地风力情况，也就是说空气状态是隐藏的，风力情况是可观察的，需要观察序列推测隐藏序列，由于风力确实对雾霾情况有较大影响，甚至可以假设风力大的情况下90%概率是晴天，所以通过样本学习，确实可以达到从观察序列推测隐藏序列的效果，这就是隐式马尔可夫。

URL参数建模

　　常见的基于GET请求的XSS、SQL注入、RCE，攻击载荷主要集中在请求参数中，以XSS为例：

/0_1/include/dialog/select_media.php?userid=%3Cscript%3Ealert(1)%3C/script%3E

正常的http请求中参数的取值范围都是确定的，这里说的确定是指可以用字母数字特殊字符来表示，并非说都可以用1-200这种数值范围来确定。

以下面的几条日志为例：

/0_1/include/dialog/select_media.php?userid=admin123
/0_1/include/dialog/select_media.php?userid=root
/0_1/include/dialog/select_media.php?userid=maidou0806
/0_1/include/dialog/select_media.php?userid=52maidou
/0_1/include/dialog/select_media.php?userid=wjq_2014
/0_1/include/dialog/select_media.php?userid=mzc-cxy

肉眼观察可以归纳出userid字段的由字母数字和特殊字符‘-_‘组成,如果你足够强大可以看完上万的正常样本，甚至都可以总结取值范围为[0-9a-zA-Z-_]{4,}。如果有上亿的日志上百万的参数，人工如何完成？这时候机器学习可以发挥作用了。

以uid字段为例，uid的取值作为观察序列，简化期间可以对uid的取值进行泛化，整个模型为3阶HMM，隐藏序列的状态只有三个S1、S2、S3:

[a-zA-Z]泛化为A
[0-9]泛化为N
[\-_]泛化为C
其他字符泛化为T

比如：

admin123泛化为AAAAANNN
root泛化为AAAA
wjq_2014泛化为AAAACNNN

技术分享

　　隐藏序列就是S1-S4三个状态间循环转化，这个概率称为转移概率矩阵，同时四个状态都以确定的概率，以观察序列中的A、C、N、T四个状态展现，这个转换的概率称为发射概率矩阵。HMM建模过程就是通过学习样本，生成这两个矩阵的过程。生产环境中泛化需谨慎，至少域名、中文等特殊字符需要再单独泛化。

数据处理与特征提取

　　由于每个域名的每个url的每个参数的范围都可能不一样，有的userid可能是[0-9]{4，}，有的可能是[0-9a-zA-Z-_]{3,}，所以需要按照不同域名的不同url不同参数分别学习。泛化过程如下：

 1 def etl(str):
 2    vers=[]
 3    for i, c in enumerate(str):
 4        c=c.lower()
 5        if   ord(c) >= ord(‘a‘) and  ord(c) <= ord(‘z‘):
 6            vers.append([ord(‘A‘)])
 7        elif ord(c) >= ord(‘0‘) and  ord(c) <= ord(‘9‘):
 8            vers.append([ord(‘N‘)])
 9        else:
10            vers.append([ord(‘C‘)])
11    return np.array(vers)

友情提示，为了避免中文等字符的干扰，ASCII大于127或者小于32的可以不处理直接跳过。

从weblog中提取url参数，需要解决url编码、参数抽取等恶心问题，还好python有现成的接口：

1 with open(filename) as f:
2    for line in f:
3        #切割参数
4        result = urlparse.urlparse(line)
5        # url解码
6        query=urllib.unquote(result.query)
7        params = urlparse.parse_qsl(query, True)
8        for k, v in params:

　　#k为参数名，v为参数值

　　友情提示，urlparse.parse_qsl解析url请求切割参数时，遇到‘;‘会截断，导致获取的参数值缺失‘;‘后面的内容，

　　这是个大坑，生产环境中一定要注意这个问题。

训练模型

安装hmmlearn

hmmlearn是python下的一个HMM实现，是从scikit-learn独立出来的一个项目，依赖环境如下：

Python >= 2.6
NumPy (tested to work with >=1.9.3)
SciPy (tested to work with >=0.16.0)
scikit-learn >= 0.16

安装命令如下：

pip install -U --user hmmlearn

训练模型

将泛化后的向量X以及对应的长度矩阵X_lens输入即可，需要X_lens的原因是参数样本的长度可能不一致，所以需要单独输入。

model = hmm.GaussianHMM(n_components=3, covariance_type="full", n_iter=100)
remodel.fit(X,X_lens)

训练样本得分为：

score:16 query param:admin123

score:9 query param:root

score:21 query param:maidou0806

score:16 query param:52maidou

score:15 query param:wjq_2014

score:12 query param:mzc-cxy

模型验证

　　HMM模型完成训练后通常可以解决三大类问题，一类就是输入观察序列获取概率最大的隐藏序列，最典型的应用就是语音解码以及词性标注；一类是输入部分观察序列预测概率最大的下一个值，比如搜索词猜想补齐等；另外一类就是输入观察序列获取概率，从而判断观察序列的合法性。参数异常检测就输入第三种。

我们定义T为阈值，概率小于T的参数识别为异常，通常会把T定义比训练集最小值略大，在此例中可以取10。

 1 with open(filename) as f:
 2    for line in f:
 3        # 切割参数
 4        result = urlparse.urlparse(line)
 5        # url解码
 6        query = urllib.unquote(result.query)
 7        params = urlparse.parse_qsl(query, True)
 8        for k, v in params：
 9            if ischeck(v) and len(v) >=N :
10                vers = etl(v)
11                pro = remodel.score(vers)
12                if pro <= T:
13                    print  "PRO:%d V:%s LINE:%s " % (pro,v,line)

　　以userid=%3Cscript%3Ealert(1)%3C/script%3E为例子，经过解码后为<script>alert(1)</script>，

　　泛化后为TAAAAAATAAAAATNTTTAAAAAAT，score为-13945，识别为异常。

总结

　　本文介绍了HMM在web安全的基础应用，由于仅依赖参数的文本特征进行异常检测，虽然理论上只要白样本足够多确实可以识别几乎所有基于GET请求参数的未知攻击，但是由于缺乏语义层面异常检测，误报率比较高。另外扫描器等对结果的影响很大，如何进一步提升检测能力，请看下篇。

学点算法搞安全之apriori

前言　　在企业安全建设专题中偶尔有次提到算法的应用，不少同学想深入了解这块，所以我专门开了一个子专题用于介绍安全领域经常用到的机器学习模型，从入门级别的SVM、贝叶斯等到HMM、神经网络和深度学习（其实深度学... 查看详情

学点算法搞安全之apriori

hmm的维特比算法简单示例

...牛的关于HMM的技术博客，读完之后，写了一个关于维特比算法的简单示例，用scala和java语言混合编写的。现在上传之。packagecom.txq.hmmimportjava.utilimportscala.collection._/***HMM维特比算法，根据显示状态链条估计隐式链条*@paramstates隐式s... 查看详情

大道至简机器学习算法之隐马尔科夫模型(hiddenmarkovmodel,hmm)详解---预测问题：维特比算法（viterbialgorithm）详解

...本概念和几个要素（2）HMM计算问题：前后向算法（3）HMM学习问题：Baum-Welch算法❤️本文隶属专栏：大道至简之机器学习系列❤️更多精彩文章持续发布，敬请关注本人主页~目录写在前面一、从青... 查看详情

大道至简机器学习算法之隐马尔科夫模型(hiddenmarkovmodel,hmm)详解---学习问题：baum-welch算法推导

☕️本文往期系列文章：【大道至简】机器学习算法之隐马尔科夫模型(HiddenMarkovModel,HMM)详解（1）---开篇：基本概念和几个要素_尚拙谨言的博客-CSDN博客【大道至简】机器学习算法之隐马尔科夫模型(HiddenMarkovModel,... 查看详情

一文搞懂hmm（隐马尔可夫模型）

本文转自于：http://www.cnblogs.com/skyme/p/4651331.html隐马尔可夫模型（HiddenMarkovModel，HMM）是统计模型，它用来描述一个含有隐含未知参数的马尔可夫过程。其难点是从可观察的参数中确定该过程的隐含参数。然后利用这些参数来作进... 查看详情

一文搞懂对称加密：加密算法工作模式填充方式代码实现(代码片段)

...emos上篇介绍了《单向散列加密》，它是一种消息摘要算法。该算法在信息安全领域，有很多重要的应用场景，比如：用户密码查看详情

一文彻底搞懂bp算法：原理推导+数据演示+项目实战（上篇）

参考技术A反向传播算法（BackpropagationAlgorithm，简称BP算法）是深度学习的重要思想基础，对于初学者来说也是必须要掌握的基础知识！本文希望以一个清晰的脉络和详细的说明，来让读者彻底明白BP算法的原理和计算过程。全文... 查看详情

每天学点python之collections(代码片段)

每天学点Python之collections内容摘抄自：<python大法好>的每天学点Python之collectionscollections模块在内置数据类型（dict、list、set、tuple）的基础上，提供了几个额外的数据类型：ChainMap、Counter、deque、defaultdict、namedtuple和OrderedDict... 查看详情

隐马尔科夫模型hmm鲍姆-韦尔奇算法求解hmm参数

...（一）HMM模型　　　　隐马尔科夫模型HMM（二）前向后向算法评估观察序列概率　　　　隐马尔科夫模型HMM（三）鲍姆-韦尔奇算法求解HMM参数（TODO）　　　　隐马尔科夫模型HMM（四）维特比算法解码隐藏状态序列（TODO）　　　... 查看详情

隐马尔科夫模型hmm前向后向算法评估观察序列概率

hmm和veterbi算法

...未深入，做个记录。参考：隐马尔可夫(HMM)、前/后向算法、Viterbi算法再次总结　　　谁能通俗的讲解下viterbi算法？　　　数学之美第二版的第26章本文结构：　　1.hmm三要素　　2.维特比算法　　3.简明例子hmm三要素：1.初始... 查看详情

hmm算法-解码问题

...解码问题，也是挺贴切的~求解这个问题，有一个经典的算法，叫做Viterbi算法。Viterbi是个了不起的人物，数学之美第26就是讲Viterbi和他的Viterbi算法。Viterbi算法针对篱笆网络有查看详情

机器学习hmm模型算法实例(代码片段)

目录1前向算法求HMM观测序列的概率1.1流程梳理1.2算法总结1.3HMM前向算法求解实例1.4用后向算法求HMM观测序列的概率1.4.1流程梳理1.4.2后向算法流程1.5小结2维特比算法解码隐藏状态序列2.1HMM最可能隐藏状态序列求解概述2.2维特比算... 查看详情

标注-隐马尔可夫模型hmm的探究

...念1.1定义1.2观测序列生成过程1.3HMM的三个问题2概率计算算法2.1直接计算算法2.2前向算法forwardalgorithm2.3后向算法2.4一些概率与期望值的计算3学习算法3.1监督学习3.2非监督学习——Baum-Welch算法3.3Baum-Welch模型参数估计公式4预测算法... 查看详情

机器学习-命名实体识别之hiddenmarkovmodelling(代码片段)

...ion的领域。NamedEntityRecognition(NER)的应用中，最常用的一种算法模型是隐式马可夫模型（HiddenMarkovModelling）-HMM。本节内容主要是通过介绍HMM的原理，以及应用HMM来做一个NER的实例演示。 HMM原理解析在解释HMM的原理之前，先引... 查看详情

概率图模型之em算法

一、EM算法概述EM算法（ExpectationMaximizationAlgorithm，期望极大算法）是一种迭代算法，用于求解含有隐变量的概率模型参数的极大似然估计（MLE）或极大后验概率估计（MAP）。EM算法是一种比较通用的参数估计算法，被广泛用于朴... 查看详情

每天学点python之布尔类型(代码片段)

每天学点Python之布尔类型Python中的布尔类型有两个常量True和False表示。布尔值转化Python中的布尔值是可以转化为数值的，True表示1，而False表示0，可以对其进行数值运算，但不建议这么做，会引起代码的混乱。... 查看详情