面向數(shù)據(jù)庫性能的SQL語句解析與翻譯

崔娜

（內(nèi)蒙古電子信息職業(yè)技術(shù)學院，內(nèi)蒙古 呼和浩特　010070）

面向數(shù)據(jù)庫性能的SQL語句解析與翻譯

崔娜

（內(nèi)蒙古電子信息職業(yè)技術(shù)學院，內(nèi)蒙古 呼和浩特010070）

信息泄漏事件不斷發(fā)生使得數(shù)據(jù)庫安全的重要性不斷提高?；赟QL解析能夠?qū)崿F(xiàn)SQL到自然語言的翻譯，幫助非專業(yè)人員分析數(shù)據(jù)庫的訪問活動和識別風險。通過SQL詞法和語法的EBNF描述構(gòu)造了可以用于LL的規(guī)則輸入，使用ANTLR工具生成了SQL詞法和語法解析器。進一步，SQL詞法和語法解析器實現(xiàn)了SQL語句到抽象語法樹的轉(zhuǎn)換。并通過解析抽象語法樹，將SQL語句翻譯成自然語言。最后，將SQL解析和翻譯功能應(yīng)用在數(shù)據(jù)庫防火墻和安全審計系統(tǒng)中。

SQL解析；LL解析器；ANTLR；抽象語法樹；SQL翻譯；數(shù)據(jù)庫安全

0　引　言

近幾年，信息泄漏事件頻繁發(fā)生，用戶對數(shù)據(jù)庫的安全性越來越關(guān)注。由于數(shù)據(jù)庫本身的復雜性，數(shù)據(jù)庫的管理運行、日常維護和數(shù)據(jù)安全保護只能由專業(yè)的數(shù)據(jù)庫管理員進行。但是，很多使用數(shù)據(jù)庫的人并不熟悉數(shù)據(jù)庫，甚至完全不了解數(shù)據(jù)庫。SQL分析技術(shù)能夠幫助用戶快速抽取SQL語句中的字段、表、視圖及對它們的操作，快速識別SQL語句的風險。同時基于SQL分析技術(shù)能夠?qū)QL語句翻譯成自然語言，使之更容易被理解，有助于實現(xiàn)安全控制。

早期的SQL解析使用Lex，Yacc的比較多。雖然Oracle已經(jīng)將ANTLR應(yīng)用在SQL Developer的IDE中，但是SQL Developer并非開源使用。因此使用ANTLR進行SQL解析的研究目前還很少，進行SQL翻譯的工作還未見報道。在使用ANTLR解析SQL并且將結(jié)果進行進一步分析是一個新的嘗試。本文針對數(shù)據(jù)庫安全，基于LL文法，采用ANTLR工具，實現(xiàn)了SQL的詞法和語法解析器，并進一步實現(xiàn)了SQL語句到自然語言的翻譯。最后，將SQL解析和翻譯功能應(yīng)用在數(shù)據(jù)庫防火墻和安全審計系統(tǒng)中，對于提高數(shù)據(jù)庫的安全防護能力具有很大的實際意義。

1　SQL解析器

1.1SQL詞法解析器實現(xiàn)

SQL語言的詞法主要分為標識符、數(shù)字、注釋與提示、字符串、時間、區(qū)間和變量?；贏NTLR實現(xiàn)SQL詞法解析首先要定義詞法的fragment。所謂的fragment是詞的一部分，而不會出現(xiàn)在詞法解析的結(jié)果中。以數(shù)字和時間為例分析。

（1）數(shù)字Number。在SQL語言中表示數(shù)值類型。數(shù)值類型包含整數(shù)部分、小數(shù)部分、符號部分、指數(shù)部分和類型部分，其中指數(shù)部分是一個大寫字母“E”或者一個小寫字母“e”加一個帶有符號的整數(shù)，如果不帶符號默認為“+”。數(shù)值類型中，整數(shù)部分和小數(shù)部分必須包含其中之一，其他部分都是可選的，只包含小數(shù)部分時允許“.”出現(xiàn)在數(shù)值的最前面，例如“.5”表示“0.5”。數(shù)字的DFA表示如圖1所示。

圖1　Number詞法分析圖

（2）時間Datetime。時間格式比較固定，必須由關(guān)鍵字DATE開頭，后面是一個表示時間的字符串，如果不是表示時間的字符串，SQL語句認為是錯誤的語句。另外，時間戳也被認為是一種時間格式，必須是由關(guān)鍵字TIMESTAMP開頭，時間戳格式包含AT TIME ZONE可選結(jié)構(gòu)，表示時區(qū)。時間的DFA表示如圖2所示。

圖2　Datetime詞法分析圖

根據(jù)這七種類型的自動機表示將其轉(zhuǎn)換成對應(yīng)的EBNF表示。使用“*”、“+”替換DFA中的循環(huán)結(jié)構(gòu)，“*”表示可以跳過的循環(huán)結(jié)構(gòu)，“+”表示不可跳過的循環(huán)結(jié)構(gòu)。使用“|”表示DFA中的選擇結(jié)構(gòu)，在每個分支之間使用“|”表示選擇。使用“？”表示DFA中可跳過的結(jié)構(gòu)，將“？”放在可選結(jié)構(gòu)的后面。在每個單元上使用“（）”將不可拆分的部分包含在內(nèi)，就可以使用簡單的EBNF語句描述復雜的DFA。另外，對于SQL的保留字要做單獨的識別。例如：select要定義成SELECT：SE L E C T；這樣select無論是“Select”還是“seLECT”都能識別出來。針對不同的SQL語句它的保留字也是不一樣的，需要單獨定義語法文件。SQL語言中是不區(qū)分大寫字母和小寫字母的，在ANTLR中單獨的字母應(yīng)該被當作碎片來定義，不能出現(xiàn)在最終的解析結(jié)果中，使用“fragment”修飾。字母包含鍵盤上所有能夠輸入的符號以及鍵盤上不能直接輸入的UNICODE字符。SQL語言中使用的數(shù)字是阿拉伯數(shù)字0～9，單獨的數(shù)字也要使用“fragment”修飾。

1.2SQL語法解析器實現(xiàn)

語法解析器實現(xiàn)過程中需要將所有的語言模式轉(zhuǎn)化為EBNF描述的規(guī)則語句。SQL語言的范式使用的是EBNF描述，要將其轉(zhuǎn)換成EBNF描述的規(guī)則。EBNF范式的好壞雖然不會影響到解析的效率，解析效率只與被解析的字符串的長度有關(guān)系，但是會影響到解析器生成的效率。壞的EBNF規(guī)則會導致生成的過程中出現(xiàn)大量的遞歸調(diào)用和棧操作，生成的時間和內(nèi)存會成指數(shù)級增長。所以EBNF的規(guī)則還是有很多細節(jié)需要注意。規(guī)則的深度不能太深，并且需要或關(guān)系的規(guī)則盡量將K值控制到最低，因為規(guī)則生成的復雜度是（K*N）M。其中，K是向后查看的token數(shù)；N是或關(guān)系連接的多個規(guī)則；M是規(guī)則嵌套的層數(shù)。由于一個子規(guī)則經(jīng)常被多個規(guī)則引用，所以子規(guī)則會影響所有引用它的規(guī)則的生成效率。降低子規(guī)則的層數(shù)和減小K值是有效的提高生成效率的方法。N值一般難以降低，除非規(guī)則本身就有冗余，但是這種情況比較少見。

使用ANTLR將語法文件編譯成解析器，實現(xiàn)過程類似于詞法分析。輸入由String變成tokens，ANTLR自身的語法不變。使用全部的語法生成語法解析器，在生成過程中系統(tǒng)采用LL（K）分析方法。ANTLR支持預測功能，可以在特定的地方使用預測。設(shè)置回溯位置，對輸入的tokens進行預測，降低解析時間和消耗的資源。 解析的結(jié)果可以得到每一個token的屬性、內(nèi)容和值。再對生成的一維AST樹做遞歸下降，將AST樹的二維層次結(jié)構(gòu)補全，得到具有層次和附屬關(guān)系的二維語法樹。AST樹上的節(jié)點對于解析來說并不都是必須的，在生成過程中將不需要的節(jié)點刪除，留下必須的結(jié)果，精簡AST樹對于快速提取重要信息有很大的幫助。在AST樹生成的過程中直接嵌入SQL語句檢查代碼，同時可以在解析過程中直接根據(jù)token的類型判斷輸入詞的意義，從而將SQL中最重要的表、視圖、字段直接提取出來，同時判斷出SQL的類型和操作對象的類型。更進一步，將SQL中存在的安全隱患的類似緩沖區(qū)溢出和SQL注入攻擊的風險直接檢測出來。

2　SQL翻譯

2.1SQL語句AST的構(gòu)建

ANTLR語法解析的輸出結(jié)果就是抽象語法樹。將語法解析的結(jié)果設(shè)置為AST，ANTLR每一個規(guī)則解析之后就能生成AST結(jié)構(gòu)。默認情況下生成一維語法樹，所有的結(jié)果在同一個層次上。如果需要自定義抽象語法樹的返回結(jié)果，需要在語法解析過程中加入AST構(gòu)建規(guī)則。ANTLR的抽象語法樹構(gòu)建語法非常簡單，標準語法只有三種：

（1）“^”，前面的符號作為父節(jié)點；

（2）“！”，前面的節(jié)點不出現(xiàn)在語法樹上；

（3）“->^（……）”，“->”左側(cè)是語法解析語句，右側(cè)是抽象語法樹生成語句，括號內(nèi)是一棵子樹，第一個符號是樹的根，其他元素是第一個元素的子節(jié)點。例如：（A+B）->^（+A B）。

由于SQL語言是結(jié)構(gòu)化的查詢語句，在構(gòu)建抽象語法樹上有先天的優(yōu)勢。構(gòu)建語法樹時只需要考慮SQL中查詢的主體，忽略不需要的部分，其中最重要的就是表、字段、視圖和在表、字段、視圖上的操作。查詢語句是SQL語句中最復雜的語句，可以使用嵌套和遞歸的方式，語法結(jié)構(gòu)十分靈活。由于其他語言相比于查詢語言簡單很多。本節(jié)用查詢語句舉例說明SQL語句抽象語法樹生成過程。

查詢語句可以包含for update語句，但不是必須包含，for update和查詢是平行關(guān)系，一個查詢只能在最后包含一個for update語句，這里只需要將最后的“；”裁剪掉：

selectStatment：subquery（for_update_clause）？（′；′?。?？；

子查詢可以有嵌套，也可以和其他子查詢做交、并、異或操作，最終結(jié)果做一次排序：

subquery：（query_block|′（′！subquery′）′！）

（（UNION（ALL）？|INTERSECT|MINUS）subquery）*

（order_by_clause）？；

查詢塊是最終的查詢，包含查詢的各個功能模塊，模塊在結(jié)構(gòu)上是平行的：

query_block：（subquery_factoring_clause）？

select_clause from_clause

（where_clause）？

（hierarchical_query_clause）？

（group_by_clause）？

（model_clause）？

（having_clause）？

2.2AST轉(zhuǎn)換成自然語言

SQL語句的語言結(jié)構(gòu)更接近英文的語言結(jié)構(gòu)，與中文的語言結(jié)構(gòu)差別較大，簡單的對關(guān)鍵字替換不考慮語義是不能達到翻譯效果的，只會讓結(jié)果更加匪夷所思，舉例說明：

SELECT concat（select user（），′--′，database（）），name FROM TABLE（SELECT date，user，action，name FROM logs WHERE id=if（ascii（substr（（SELECT user（））），1，1）=1），1，0））WHERE‘a(chǎn)dmin’in（SELECT name FROM user）；

直接替換翻譯結(jié)果為：

查詢concat（查詢user（），′--′，database（）），name從邏輯表（查詢date，user，action，name從logs條件滿足id等于if（ascii （substr（（查詢user（）），1，1））等于1，1，0）條件滿足‘a(chǎn)dmin’在（查詢name從user）。

使用樹解析器將抽象語法樹轉(zhuǎn)換成自然語言。由于抽象語法樹采用遞歸的方式表示語法結(jié)構(gòu)，在解析的過程中也使用遞歸的方式，并將語法習慣調(diào)整為漢語語言的語法習慣。在轉(zhuǎn)換的過程中補充虛詞和連接詞，增加語言的連貫性。最后對翻譯結(jié)果進行格式化，增加縮進便于閱讀?？紤]漢語的閱讀習慣，可以將較長的句子翻譯成子句的形式，最后，根據(jù)數(shù)據(jù)庫建模表和數(shù)據(jù)庫方法表，可以將翻譯結(jié)果中的方法名、字段名、表名等翻譯成中文，翻譯時只要判斷出被翻譯內(nèi)容的類型，然后查找相應(yīng)的數(shù)據(jù)表，就能將剩下的英文部分翻譯成中文，生成最終結(jié)果為：

模塊1：

查詢獲取用戶方法（user）的執(zhí)行結(jié)果的返回數(shù)據(jù)

模塊2：

從用戶表（user）中查詢姓名字段（name）的返回數(shù)據(jù)

條件1：

標識字段（id）等于條件判斷方法（if）［轉(zhuǎn)換成ascii編碼方法（ascii）［子串方法（substr）［｛模塊1｝，1，1］的返回結(jié)果］］的返回結(jié)果等于1，1，0］的返回結(jié)果

條件2：

字串‘a(chǎn)dmin’在［｛模塊2｝］里

模塊3：

從日志表（logs）中查詢滿足｛條件1｝條件的日期字段（date）和用戶字段（user）和動作字段（action）和姓名字段（name）的返回數(shù)據(jù)

模塊4：

邏輯表［｛模塊3｝］

模塊5：

查詢方法用戶方法（user）執(zhí)行結(jié)果的返回數(shù)據(jù)

模塊6：

連接字符串方法（concat）［｛模塊5｝，′--′，方法數(shù)據(jù)（database）的執(zhí)行結(jié)果］的執(zhí)行結(jié)果

主查詢：

從｛模塊4｝中查詢滿足｛條件2｝條件的｛模塊6｝和姓名字段（name）的返回數(shù)據(jù)。

翻譯過程中需要調(diào)整語序，語序的調(diào)整主要使用棧實現(xiàn)，將需要調(diào)整語序的句子放入棧中，返回時再從棧中取出。樹解析器翻譯的過程如下：

（1）當前指針在根節(jié)點，獲取節(jié)點，判斷節(jié)點類型，類型不一樣，Tree Walker進入不同的解析模塊，這里以SELECT語句為例；

（2）獲取一個子節(jié)點，判斷節(jié)點的類型；

（3）如果是 SELECT語句，那么就調(diào)用 select_tree_walker，然后調(diào)整語序，執(zhí)行stack.push操作，將結(jié)果先緩存。如果是FROM語句，調(diào)用from_tree_walker的結(jié)果放入output流中。如果是WHERE語句，調(diào)用where_tree_walker，調(diào)用stack.pop將SELECT語句出棧，和WHERE語句合并格式，結(jié)果放入到output流中；

（4）tree_waker是一個遞歸的過程，在解析過程中，將查詢的條件和子模塊生成獨立的翻譯模塊；

（5）tree_waker在執(zhí)行的過程中遇到需要查詢建模表和函數(shù)表的情況，將查詢的結(jié)果輸出；

（6）重復步驟（2）～步驟（5）過程，直到input流為空。

Tree Walker對部分葉節(jié)點的翻譯規(guī)則如表1所示。

3　系統(tǒng)實現(xiàn)與效果分析

本系統(tǒng)目前已在數(shù)據(jù)庫審計和防火墻產(chǎn)品有所應(yīng)用，數(shù)據(jù)庫審計與防火墻引擎設(shè)置界面如圖3所示。要對數(shù)據(jù)庫進行審計或者建立防火墻，先要添加數(shù)據(jù)庫引擎。審計數(shù)據(jù)獲取方式有很多種，在設(shè)置界面進行設(shè)置。

表1　Tree W alker部分規(guī)則表

圖3　DAF審計防火墻設(shè)置窗口

規(guī)則設(shè)置界面部分截圖如圖4所示。規(guī)則可以設(shè)置表、字段、SQL類型等，SQL解析中能夠獲取的所有信息都可以在規(guī)則界面上設(shè)置。通過對SQL語句進行解析獲取語句的類型，然后對不同類型的SQL語句設(shè)置不同的規(guī)則。

圖4　DAF規(guī)則設(shè)置窗口

告警設(shè)置界面如圖5所示。規(guī)則匹配上之后設(shè)置相應(yīng)的告警級別，就會產(chǎn)生相應(yīng)的告警信息。

圖5　DAF告警設(shè)置窗口

檢索界面如圖6所示?？梢詫徲嬋罩具M行檢索，獲取數(shù)據(jù)庫用戶的操作行為。

告警界面如圖7所示。SQL語句觸發(fā)告警規(guī)則就會產(chǎn)生告警，在告警界面上可以查看告警細節(jié)。

圖6　DAF檢索界面

圖7　DAF告警查看窗口

圖7中select 1 from db_queue_tables where 1=2，其中條件1=2是常量比較，判定SQL語句可能是SQL注入語句，產(chǎn)生高風險告警。然后通過SQL翻譯將SQL語句翻譯成對應(yīng)的中文，select 1 from db_queue_tables where 1=2的翻譯結(jié)果為“從表dba_queue_tabkes中查詢滿足條件1=2的值1的返回結(jié)果”。

最新流量界面如圖8所示。在最新流量界面可以實時顯示最新的SQL操作，隨時監(jiān)控SQL操作動態(tài)?；赟QL解析和翻譯的數(shù)據(jù)庫審計和防火墻產(chǎn)品可以在審計模式對操作進行溯源，起到對不法分子進行震懾的作用。防火墻模式可以通過阻斷方式對風險進行控制，從而提升數(shù)據(jù)庫系統(tǒng)的安全性。

圖8　DAF最新流量界面

4　結(jié)　論

本文通過分析標準SQL語言的詞法規(guī)則和語法規(guī)則，并基于ANTLR設(shè)計并實現(xiàn)了SQL詞法解析器和語法解析器；使用SQL詞法解析器和語法解析器實現(xiàn)了SQL語句輔助分析功能，實現(xiàn)了SQL語句的詞法分析和語法樹生成；通過解析語法樹提取SQL信息并將SQL語句翻譯成自然語言；并將SQL解析和翻譯的功能應(yīng)用在

數(shù)據(jù)庫綜合審計系統(tǒng)中。SQL解析和翻譯模塊已經(jīng)被應(yīng)用在商業(yè)數(shù)據(jù)庫防火墻和安全審計系統(tǒng)中，并且被部署到多個數(shù)據(jù)中心。系統(tǒng)可以監(jiān)控數(shù)據(jù)庫的所有活動，阻斷危險操作和攻擊，從而達到增強數(shù)據(jù)庫安全的目的，為保障數(shù)據(jù)庫及信息系統(tǒng)的安全逐步發(fā)揮作用。

本文設(shè)計了一種基于反激式直流變換器的動力電池均衡電路，給出了系統(tǒng)建模方法，并在PSIM環(huán)境下完了系統(tǒng)仿真電路，針對8種典型非均衡狀態(tài)進行了全面的仿真實驗，最后通過實驗證明了系統(tǒng)建模的有效性。由于建模過程忽略了變換器磁阻、磁滯、磁飽和現(xiàn)象，同時簡化了電路寄生參數(shù)，需要進一步完善。

［1］張博，類艷春，廉小偉.數(shù)據(jù)庫安全漏洞淺析［J］.保密科學技術(shù)，2012（3）：23-25.

［2］劉三獻.基于ANTLR的Gaussian詞法分析器和語法分析器的分析與設(shè)計［D］.蘭州：蘭州大學，2009.

［3］閆紅巖.SQL語句分析及數(shù)據(jù)庫安全研究［J］.貴陽：貴州大學，2006.

［4］侯智斌，孫彥飛，呂曹芳.基于入侵容忍技術(shù)的數(shù)據(jù)庫安全策略研究［J］.現(xiàn)代電子技術(shù)，2011，34（7）：78-80.

［5］PARR T，F(xiàn)ISHER K.LL（*）：the foundation of the ANTLR parser generator［C］//Proceedings of 32nd ACM SIGPLAN Conference on Programm ing Language Design and Implementation. ［S.l.］：ACM，2011：425-436.

［6］SALOMAA K，YU S.NFA to DFA transformation for finite languages over arbitrary alphabets［C］//Proceedings of 1996 First International Workshop on Implementing Automata.London：Springer，1996：149-158.

［7］LOUDEN K C.Compiler construction：principlesand practice［M］. New York：Cengage Learning，2000：21-148.

［8］DATE C J，DARWEN H.A guide to the SQL standard［M］. New York：Addison-Wesley，1987.

SQL parse and translation oriented to database per form ance

CUINa
（Inner Mongolia Electronic Information Vocational Technical College，Hohhot 010070，China）

The continuous occurrence of information leakage incidents makes the importance of database security improve constantly.The SQL parse can realize the translation from SQL to natural language，and help the non-specialized people to analyze the database access activities and identify the risks.The rule input applied to LL was constructed by means of EBNF description of SQL morphology and syntax.The SQL morphology and parser are generated with ANTLR tool，which can realize the conversion from SQL statement to abstract syntax tree.The SQL statement can be translated into natural language by parsing the abstract syntax tree.Finally，SQL parse and translation function are applied to the database firewall and safety audit system.

SQL parse；LL parser；ANTLR；abstract syntax tree；SQL translation；database security

TN918.91-34；TM417

A

1004-373X（2016）11-0099-04

10.16652/j.issn.1004-373x.2016.11.024

2015-12-08

崔娜（1981—），女，內(nèi)蒙古呼和浩特人，碩士，講師，高級工程師。主要研究方向為計算機技術(shù)。