開篇

從這一篇開始，我們正式進入對靜態代碼檢測開源項目Pixy的深度剖析，以期望能夠發掘出靜態代碼分析可以應用在webshell檢測上的更多實用能力。

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}，，{a,b}}，哈斯圖如下：

對于子集{{a}，}，是沒有最大下界存在的，甚至沒有下界，因為哈斯圖中不存在一個點既是{a}的下界，同時也是的下界，所以該偏序集不是格。

完全格是一種特殊的格，對完全格來說，它的所有子集，包括空集都必須存在最小上界和最大下界，而普通格只需要它的所有非空子集存在最小上界和最大下界。

事實上，所有的有有限個數量元素的普通格都是完全格，為了展示完全格和普通格的不同，我們需要一個有無限個元素的格。
考慮這樣一個偏序集，它的元素是所有的整數（Z = {…，-3，-2，-1,0,1,2,3，…}），并且偏序關系是"≤"小于等于。哈斯圖如下：

很明顯，該偏序集是無限集，且滿足普通格的條件。但是對于該集合本身所構成的它的一個子集，既不存在最小上界，也不存在最大下界。因此，該格并不滿足完全格的條件，它不是完全格。我們也可以在該偏序集中加入元素-∞和+∞來使該偏序集得以滿足完全格的條件，這意味著一個完全格必須存在最大元素和最小元素。

順便說一下，以上關于完全格的定義可能會被簡化為"完全格的所有子集，包括空集都必須存在最小上界或最大下界"，因為從數學上可以證明，對完全格的所有子集來說，存在最小上界必然存在最大下界。

接下來我們來說一個完全格中令人疑惑的點，即完全格的空子集（寫作?），不過我們僅作了解即可。注意不要把完全格的?和完全格中的空集元素搞混，比如對于冪集{{}，{1}，{2}，{1,2}}組成的格，該集合中的空集{}是它的一個元素，不是該集合的?。下面的兩個等式可能會看起來有些怪，但它們是成立的：

• ?? =?： 完全格的空子集的最小上界是完全格的最小元素；
• ?? = ?：完全格的空子集的最大下界是完全格的最大元素；

半格

如名字所示，半格類似于格，但是與格有一點不同。首先，半格也必須是偏序集，但是對于下面的兩個條件，半格只需滿足其一即可，而格必須全部滿足：

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

其中，滿足第一個條件的半格叫做并半格（Join Semilattice），滿足第二個條件的半格叫作交半格（Meet Semilattice）。

總結

這篇文章我們了解了格理論的一些基本概念，從數學上講只要對集合論有些了解就能輕松理解，相比微積分這些大山要簡單的多。不過雖然看懂了理論，但是相信你現在一定一頭霧水，想不通webshell檢測和這些抽象的點和邊有什么關系。不用擔心，在下一篇文章中我會詳細講解一下數據流分析，并展示格理論是如何在數據流分析中發揮作用的，請拭目以待吧。

總結

以上是生活随笔為你收集整理的webshell检测方式深度剖析 --- Pixy系列一（格理论）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。