懶人在思考？WAF研究中...

• 什麼是漢語？是漢字+語法嗎？
• 什麼是英語？是單詞+語法嗎？

我們能夠看懂這篇文章，是因為我們認識裡面每一個漢字，理解這門語言的語法。那麼我們能不能定義一門攻擊語言？

• 比如XSS攻擊語言：JS token + JS語法？
• 比如PHP攻擊語言：PHP token + PHP語法？

當我們看到一個字元串，它是XSS攻擊語言，那麼我們就稱這個字元串是XSS攻擊串！那麼如何判斷一個字元串是XSS攻擊語言呢？這就是我們要做的XSS語義引擎！為瞭解決這個問題，我們引入一個類似的問題：如何判斷一個字元串，它符合C語言語法？答案呼之欲出：編譯原理！我們要解決的問題是判斷XSS攻擊！我們踏入的第一個坑是上下文無關語法！非安全研究人員可以停止閱讀了，天書預警！

上下文無關語法

上下文無關語法G：終結符集合T + 非終結符集合N + 產生式集合P + 起始符號S

由語法G推倒出來的所有句子的集合稱為G語言！由XSS攻擊語法推倒出來的所有句子的集合稱為XSS攻擊語言。

S -> AB
A -> aA | ε
B -> b | bB


• 產生式(Production)：形如S -> AB，右側可以替換左側
• 非終結符(Nonterminal)：產生式左側符號，SAB
• 終結符(Terminal)：產生式右側符號，token (a,b,ε...)
• 起始符(Start symbol)：所有句子都以它為起點產生，S
• 展開(expand)：將P(A->u )應用到符號串vAw中，得到新串vu w
• 摺疊(reduce)：將P(A->uu )應用到符號串vuu w中，得到新串vAw
• 推導(derivate)：符號串u 應用一些列產生式，變成符號串v ，則u =>v
• 上下文無關語法G：4元組：（P,N,T,S）
• 解析(parse)：由T 推導得到句子s的全過程

A:{ε ,a ,aa ,aaa , ...}
B:{b ,bb ,bbb , ...}
S:{b ,bb ,ab ,abb ,aab ,aabb ,...}


看看S是不是可以替代正則表達式：a*b+，拯救正則性能有救了！

再來看看上下文無關語法更強大的表達能力：

E -> E OP E | (E) | N
OP -> = + - * /
N -> [0-9]+


整數算術表達式！哇哦，簡直了 ~

E:{1 ,123 ,1-1 ,(1+1)*(1+2) ,...}


很明顯，我們知道1+1符合語法E，1+-1不符合語法E，那麼機器是怎麼知道的呢？

參考文獻：自己動手寫編譯器（pandolia.net/tinyc/）

推薦閱讀：

相關文章