開篇

從這一篇開始，我們正式進(jìn)入對靜態(tài)代碼檢測開源項(xiàng)目Pixy的深度剖析，以期望能夠發(fā)掘出靜態(tài)代碼分析可以應(yīng)用在webshell檢測上的更多實(shí)用能力。

成都創(chuàng)新互聯(lián)公司長期為上千余家客戶提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊(duì)從業(yè)經(jīng)驗(yàn)10年，關(guān)注不同地域、不同群體，并針對不同對象提供差異化的產(chǎn)品和服務(wù)；打造開放共贏平臺(tái)，與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為冷水江企業(yè)提供專業(yè)的做網(wǎng)站、成都網(wǎng)站設(shè)計(jì)，冷水江網(wǎng)站改版等技術(shù)服務(wù)。擁有十載豐富建站經(jīng)驗(yàn)和眾多成功案例,為您定制開發(fā)。

Pixy是用java語言實(shí)現(xiàn)的用于檢測php中SQL注入和XSS漏洞的開源檢測工具，它曾在三個(gè)知名web應(yīng)用中發(fā)現(xiàn)了15個(gè)未知的漏洞，并且誤報(bào)漏能控制在50%左右。Pixy項(xiàng)目最初在2006年倍創(chuàng)建，而且只能檢測php5的語法，雖然距今已經(jīng)過去超過15年了，但其中使用的靜態(tài)檢測理論模型依然未過時(shí)，且在惡意腳本檢測領(lǐng)域依然發(fā)揮著重要作用。

Pixy涉及到的理論基礎(chǔ)非常多，為了避免剛開始就進(jìn)入諸多的細(xì)節(jié)，我們先來做一波理論鋪墊，對涉及到的理論有個(gè)初步了解，然后再高屋建瓴地俯瞰整個(gè)Pixy的檢測流程，最后我們再深入到核心處，看看它的核心位置的具體實(shí)現(xiàn)。

好了，作為Pixy系列的第一篇，我們先來了解一下數(shù)據(jù)流分析的底層基石 — 格（lattice）理論。

格理論

格理論是離散數(shù)學(xué)中的內(nèi)容，對這部分內(nèi)容的講解我們力求深入淺出，在較短的篇幅內(nèi)對其中幾個(gè)重要的概念有個(gè)直觀的理解。不過不用擔(dān)心，這些內(nèi)容并不需要多少數(shù)學(xué)知識(shí)，只要對集合稍有了解即可。

二元關(guān)系

二元關(guān)系（Binary Relations）作用在集合上，我們用符號(hào)R來代表二元關(guān)系，其含義是：從集合中拿出兩個(gè)元素作為二元關(guān)系R的輸入，注意不必是任意兩個(gè)元素，R運(yùn)算之后的輸出必定為true或者false。

舉個(gè)例子，考慮關(guān)系“≤”（小于等于）和集合{1,2,3}，從集合中選取兩個(gè)元素（1,2），那么經(jīng)“≤”運(yùn)算后的結(jié)果為true（1<=2）。再選取元素（3,2），“≤”運(yùn)算后的結(jié)果為fasle。所以我們可以稱“≤”是集合{1,2,3}的二元關(guān)系。

偏序關(guān)系

偏序關(guān)系（Partial Order Relations）屬于二元關(guān)系，但需額外滿足如下三個(gè)特性：

設(shè)R是集合A上的一個(gè)二元關(guān)系，若R滿足：

Ⅰ 自反性：對任意x∈A，那么對于（x，x），R的運(yùn)算結(jié)果必定為true，簡寫為xRx；
Ⅱ 反對稱性（即反對稱關(guān)系）：對任意x,y∈A，若xRy，且yRx，則x = y；
Ⅲ 傳遞性：對任意x,y,z∈A，若xRy，且yRz，則xRz。

則稱R為A上的偏序關(guān)系。

比如我們之前舉的例子，集合{1,2,3}上的二元關(guān)系“≤”滿足這三條特性，因此二元關(guān)系“≤”是集合{1,2,3}上的偏序關(guān)系。

偏序集

集合和作用在其上的偏序關(guān)系合稱為偏序集（Partially Ordered Sets），偏序集中的"偏"的含義是指偏序關(guān)系不必對集合中的任意兩個(gè)元素運(yùn)算結(jié)果都為true。如果某個(gè)偏序關(guān)系對集合中任意兩個(gè)元素都成立（無需考慮這兩個(gè)元素的順序），那我們稱之為全序集（totally ordered set），作為偏序集的特例。事實(shí)上我們之前舉的例子，集合{1,2,3}和偏序關(guān)系“≤”即是全序集。

接下來我們舉一個(gè)偏序集不是全序集的例子，考慮集合{1,2,3}的冪集（powerset）：{ {1,2,3}, {1,2}, {1,3}, {2,3}, {1}, {2}, {3}, {} }，然后我們定義偏序關(guān)系?（子集關(guān)系），對于集合中的如下元素對來說，偏序關(guān)系?的結(jié)果是true：

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

該冪集和偏序關(guān)系?是偏序集而不是全序集，因?yàn)閷τ谠貙?{1}, {2})和({1,2}, {2,3})，對偏序關(guān)系?的結(jié)果是false。
現(xiàn)在我們已經(jīng)見到了兩種偏序關(guān)系：“≤"和"?”，現(xiàn)在我們用符號(hào)"?"來代表任意的偏序關(guān)系。

偏序集可以用圖形化的形式來描述，我們可以把偏序集中的元素作為節(jié)點(diǎn)，把兩個(gè)元素之間的偏序關(guān)系作為有向邊。不過這種描述方式也有不方便和冗余的地方，比如邊的數(shù)量會(huì)隨著節(jié)點(diǎn)數(shù)量的增長而快速增長。一種更簡潔的方式是使用哈斯圖來描述，它會(huì)把一些顯式的信息隱式化，因此圖本身會(huì)變得更簡潔。準(zhǔn)確來說，哈斯圖做了如下的簡化措施：

• 自反邊（起始節(jié)點(diǎn)和目的節(jié)點(diǎn)相同的邊）被省略，因?yàn)閷τ诠箞D上的每個(gè)節(jié)點(diǎn)，都存在一條被省略的自反邊；
• 可傳遞的邊被省略。舉個(gè)例子，有一條邊由{1}指向{1,2}，同時(shí)也有一條邊由{1,2}指向{1,2,3}，那么這時(shí)候就沒有必要再單獨(dú)畫一條由{1}指向{1,2,3}的邊了；
• 按照慣例，所有的邊都是向上繪制的，所以代表邊的方向的箭頭也就可以被省略了。

下圖就是用哈斯圖來表示的集合{1,2,3}的冪集上的?偏序集：

界

對于偏序集中的元素a和b，如果對于偏序集中的元素u，存在a?u，且b?u，那么我們就稱u為元素a和b的一個(gè)上界。以集合{1,2,3}的冪集舉例，元素{1,2}和元素{2,3}存在上界{1,2,3}，而元素{1}和元素{1,2}存在上界{1,2}和{1,2,3}。所以說，對一個(gè)元素對來說可能存在多個(gè)上界，而且上界不是必須要和元素對內(nèi)的元素不同。

一旦我們理解了上界的含義，那么最小上界（寫作?）也就不難理解了，它指的是在一個(gè)元素對所有的上界中，那個(gè)?于其它所有上界的那個(gè)上界。舉個(gè)例子，元素{1}和元素{1,2}的最小上界是{1,2}，寫作{1}?{1,2} = {1,2}，簡寫為?({1}，{1,2}）={1,2}，而不是{1,2,3}。最小上界總是唯一的，而且不是必須和元素對內(nèi)的元素不同。

同理，下界和大下界（寫作?）的概念也不言而喻了。而且，上界和下界的概念也適用于多個(gè)元素的情況，而不是僅僅針對于兩個(gè)元素的元素對，比如元素{1}、{2}和{3}的最小上界是{1,2,3}。

偏序集的大元素（即最頂部的元素，寫作?）是這樣一個(gè)概念，該元素屬于該偏序集，并且該偏序集中的其它元素必須全部是該元素的下界，那么我們就稱該元素是該偏序集的大元素。同理，偏序集的最小元素（即最底部的元素，寫作?）的定義即是大元素的反向定義。

格

首先，格是一個(gè)偏序集，同時(shí)，對于該偏序集的任意非空子集，對這個(gè)子集中的所有元素作為一個(gè)整體，它都存在最小上界和大下界。比如之前一直用來舉例的冪集，無論你從該集合中拿出哪個(gè)或者哪幾個(gè)元素，總能計(jì)算出這幾個(gè)元素的最小上界和大下界。

為了更好地理解格的概念，我們再來看一個(gè)偏序集不是格的例子，比如偏序集{{a}，，{a,b}}，哈斯圖如下：

對于子集{{a}，}，是沒有大下界存在的，甚至沒有下界，因?yàn)楣箞D中不存在一個(gè)點(diǎn)既是{a}的下界，同時(shí)也是的下界，所以該偏序集不是格。

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

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

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

順便說一下，以上關(guān)于完全格的定義可能會(huì)被簡化為"完全格的所有子集，包括空集都必須存在最小上界或大下界"，因?yàn)閺臄?shù)學(xué)上可以證明，對完全格的所有子集來說，存在最小上界必然存在大下界。

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

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

半格

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

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

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

總結(jié)

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

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

當(dāng)前標(biāo)題：webshell檢測方式深度剖析---Pixy系列一（格理論）-創(chuàng)新互聯(lián)
文章位置：http://www.rwnh.cn/article48/dcohep.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供全網(wǎng)營銷推廣、移動(dòng)網(wǎng)站建設(shè)、響應(yīng)式網(wǎng)站、網(wǎng)站內(nèi)鏈、虛擬主機(jī)、營銷型網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)