webshell检测方式深度剖析---Pixy系列一(格理论)-创新互联

开篇

从这一篇开始,我们正式进入对静态代码检测开源项目Pixy的深度剖析,以期望能够发掘出静态代码分析可以应用在webshell检测上的更多实用能力。

成都创新互联公司长期为上千余家客户提供的网站建设服务,团队从业经验10年,关注不同地域、不同群体,并针对不同对象提供差异化的产品和服务;打造开放共赢平台,与合作伙伴共同营造健康的互联网生态环境。为冷水江企业提供专业的做网站、成都网站设计,冷水江网站改版等技术服务。拥有十载丰富建站经验和众多成功案例,为您定制开发。

Pixy是用java语言实现的用于检测php中SQL注入和XSS漏洞的开源检测工具,它曾在三个知名web应用中发现了15个未知的漏洞,并且误报漏能控制在50%左右。Pixy项目最初在2006年倍创建,而且只能检测php5的语法,虽然距今已经过去超过15年了,但其中使用的静态检测理论模型依然未过时,且在恶意脚本检测领域依然发挥着重要作用。

Pixy涉及到的理论基础非常多,为了避免刚开始就进入诸多的细节,我们先来做一波理论铺垫,对涉及到的理论有个初步了解,然后再高屋建瓴地俯瞰整个Pixy的检测流程,最后我们再深入到核心处,看看它的核心位置的具体实现。

好了,作为Pixy系列的第一篇,我们先来了解一下数据流分析的底层基石 — 格(lattice)理论。

格理论

格理论是离散数学中的内容,对这部分内容的讲解我们力求深入浅出,在较短的篇幅内对其中几个重要的概念有个直观的理解。不过不用担心,这些内容并不需要多少数学知识,只要对集合稍有了解即可。

二元关系

二元关系(Binary Relations)作用在集合上,我们用符号R来代表二元关系,其含义是:从集合中拿出两个元素作为二元关系R的输入,注意不必是任意两个元素,R运算之后的输出必定为true或者false。

举个例子,考虑关系“≤”(小于等于)和集合{1,2,3},从集合中选取两个元素(1,2),那么经“≤”运算后的结果为true(1<=2)。再选取元素(3,2),“≤”运算后的结果为fasle。所以我们可以称“≤”是集合{1,2,3}的二元关系。

偏序关系

偏序关系(Partial Order Relations)属于二元关系,但需额外满足如下三个特性:

设R是集合A上的一个二元关系,若R满足:

Ⅰ 自反性:对任意x∈A,那么对于(x,x),R的运算结果必定为true,简写为xRx;
Ⅱ 反对称性(即反对称关系):对任意x,y∈A,若xRy,且yRx,则x = y;
Ⅲ 传递性:对任意x,y,z∈A,若xRy,且yRz,则xRz。

则称R为A上的偏序关系。

比如我们之前举的例子,集合{1,2,3}上的二元关系“≤”满足这三条特性,因此二元关系“≤”是集合{1,2,3}上的偏序关系。

偏序集

集合和作用在其上的偏序关系合称为偏序集(Partially Ordered Sets),偏序集中的"偏"的含义是指偏序关系不必对集合中的任意两个元素运算结果都为true。如果某个偏序关系对集合中任意两个元素都成立(无需考虑这两个元素的顺序),那我们称之为全序集(totally ordered set),作为偏序集的特例。事实上我们之前举的例子,集合{1,2,3}和偏序关系“≤”即是全序集。

接下来我们举一个偏序集不是全序集的例子,考虑集合{1,2,3}的幂集(powerset):{ {1,2,3}, {1,2}, {1,3}, {2,3}, {1}, {2}, {3}, {} },然后我们定义偏序关系⊆(子集关系),对于集合中的如下元素对来说,偏序关系⊆的结果是true:

  • ({1}, {1,2})
  • ({2}, {1,2,3})
  • ({2,3}, {1,2,3})
  • ({}, {1})

该幂集和偏序关系⊆是偏序集而不是全序集,因为对于元素对({1}, {2})和({1,2}, {2,3}),对偏序关系⊆的结果是false。
现在我们已经见到了两种偏序关系:“≤"和"⊆”,现在我们用符号"⊑"来代表任意的偏序关系。

偏序集可以用图形化的形式来描述,我们可以把偏序集中的元素作为节点,把两个元素之间的偏序关系作为有向边。不过这种描述方式也有不方便和冗余的地方,比如边的数量会随着节点数量的增长而快速增长。一种更简洁的方式是使用哈斯图来描述,它会把一些显式的信息隐式化,因此图本身会变得更简洁。准确来说,哈斯图做了如下的简化措施:

  • 自反边(起始节点和目的节点相同的边)被省略,因为对于哈斯图上的每个节点,都存在一条被省略的自反边;
  • 可传递的边被省略。举个例子,有一条边由{1}指向{1,2},同时也有一条边由{1,2}指向{1,2,3},那么这时候就没有必要再单独画一条由{1}指向{1,2,3}的边了;
  • 按照惯例,所有的边都是向上绘制的,所以代表边的方向的箭头也就可以被省略了。

下图就是用哈斯图来表示的集合{1,2,3}的幂集上的⊆偏序集:
在这里插入图片描述

对于偏序集中的元素a和b,如果对于偏序集中的元素u,存在a⊑u,且b⊑u,那么我们就称u为元素a和b的一个上界。以集合{1,2,3}的幂集举例,元素{1,2}和元素{2,3}存在上界{1,2,3},而元素{1}和元素{1,2}存在上界{1,2}和{1,2,3}。所以说,对一个元素对来说可能存在多个上界,而且上界不是必须要和元素对内的元素不同。

一旦我们理解了上界的含义,那么最小上界(写作⨆)也就不难理解了,它指的是在一个元素对所有的上界中,那个⊑于其它所有上界的那个上界。举个例子,元素{1}和元素{1,2}的最小上界是{1,2},写作{1}⨆{1,2} = {1,2},简写为⨆({1},{1,2})={1,2},而不是{1,2,3}。最小上界总是唯一的,而且不是必须和元素对内的元素不同。

同理,下界和大下界(写作⨅)的概念也不言而喻了。而且,上界和下界的概念也适用于多个元素的情况,而不是仅仅针对于两个元素的元素对,比如元素{1}、{2}和{3}的最小上界是{1,2,3}。

偏序集的大元素(即最顶部的元素,写作⊺)是这样一个概念,该元素属于该偏序集,并且该偏序集中的其它元素必须全部是该元素的下界,那么我们就称该元素是该偏序集的大元素。同理,偏序集的最小元素(即最底部的元素,写作⟂)的定义即是大元素的反向定义。

首先,格是一个偏序集,同时,对于该偏序集的任意非空子集,对这个子集中的所有元素作为一个整体,它都存在最小上界和大下界。比如之前一直用来举例的幂集,无论你从该集合中拿出哪个或者哪几个元素,总能计算出这几个元素的最小上界和大下界。

为了更好地理解格的概念,我们再来看一个偏序集不是格的例子,比如偏序集{{a},{b},{a,b}},哈斯图如下:
在这里插入图片描述

对于子集{{a},{b}},是没有大下界存在的,甚至没有下界,因为哈斯图中不存在一个点既是{a}的下界,同时也是{b}的下界,所以该偏序集不是格。

完全格是一种特殊的格,对完全格来说,它的所有子集,包括空集都必须存在最小上界和大下界,而普通格只需要它的所有非空子集存在最小上界和大下界。

事实上,所有的有有限个数量元素的普通格都是完全格,为了展示完全格和普通格的不同,我们需要一个有无限个元素的格。
考虑这样一个偏序集,它的元素是所有的整数(Z = {…,-3,-2,-1,0,1,2,3,…}),并且偏序关系是"≤"小于等于。哈斯图如下:
在这里插入图片描述

很明显,该偏序集是无限集,且满足普通格的条件。但是对于该集合本身所构成的它的一个子集,既不存在最小上界,也不存在大下界。因此,该格并不满足完全格的条件,它不是完全格。我们也可以在该偏序集中加入元素-∞和+∞来使该偏序集得以满足完全格的条件,这意味着一个完全格必须存在大元素和最小元素。
在这里插入图片描述
顺便说一下,以上关于完全格的定义可能会被简化为"完全格的所有子集,包括空集都必须存在最小上界或大下界",因为从数学上可以证明,对完全格的所有子集来说,存在最小上界必然存在大下界。

接下来我们来说一个完全格中令人疑惑的点,即完全格的空子集(写作∅),不过我们仅作了解即可。注意不要把完全格的∅和完全格中的空集元素搞混,比如对于幂集{{},{1},{2},{1,2}}组成的格,该集合中的空集{}是它的一个元素,不是该集合的∅。下面的两个等式可能会看起来有些怪,但它们是成立的:

  • ⨆∅ =⟂: 完全格的空子集的最小上界是完全格的最小元素;
  • ⨅∅ = ⊺:完全格的空子集的大下界是完全格的大元素;
半格

如名字所示,半格类似于格,但是与格有一点不同。首先,半格也必须是偏序集,但是对于下面的两个条件,半格只需满足其一即可,而格必须全部满足:

  • 它的所有非空子集都有最小上界;
  • 它的所有非空子集都有大上界;

其中,满足第一个条件的半格叫做并半格(Join Semilattice),满足第二个条件的半格叫作交半格(Meet Semilattice)。

总结

这篇文章我们了解了格理论的一些基本概念,从数学上讲只要对集合论有些了解就能轻松理解,相比微积分这些大山要简单的多。不过虽然看懂了理论,但是相信你现在一定一头雾水,想不通webshell检测和这些抽象的点和边有什么关系。不用担心,在下一篇文章中我会详细讲解一下数据流分析,并展示格理论是如何在数据流分析中发挥作用的,请拭目以待吧。

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


文章名称:webshell检测方式深度剖析---Pixy系列一(格理论)-创新互联
文章来源:http://scjbc.cn/article/dcohep.html

其他资讯