开篇

从这一篇开始，我们正式进入对静态代码检测开源项目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系列一（格理论）-创新互联
链接URL：http://kswjz.com/article/dcohep.html