懒人在思考？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/）

推荐阅读：

相关文章