面向数据库性能的SQL语句解析与翻译

崔娜

（内蒙古电子信息职业技术学院，内蒙古 呼和浩特　010070）

面向数据库性能的SQL语句解析与翻译

崔娜

（内蒙古电子信息职业技术学院，内蒙古 呼和浩特010070）

信息泄漏事件不断发生使得数据库安全的重要性不断提高。基于SQL解析能够实现SQL到自然语言的翻译，帮助非专业人员分析数据库的访问活动和识别风险。通过SQL词法和语法的EBNF描述构造了可以用于LL的规则输入，使用ANTLR工具生成了SQL词法和语法解析器。进一步，SQL词法和语法解析器实现了SQL语句到抽象语法树的转换。并通过解析抽象语法树，将SQL语句翻译成自然语言。最后，将SQL解析和翻译功能应用在数据库防火墙和安全审计系统中。

SQL解析；LL解析器；ANTLR；抽象语法树；SQL翻译；数据库安全

0　引　言

近几年，信息泄漏事件频繁发生，用户对数据库的安全性越来越关注。由于数据库本身的复杂性，数据库的管理运行、日常维护和数据安全保护只能由专业的数据库管理员进行。但是，很多使用数据库的人并不熟悉数据库，甚至完全不了解数据库。SQL分析技术能够帮助用户快速抽取SQL语句中的字段、表、视图及对它们的操作，快速识别SQL语句的风险。同时基于SQL分析技术能够将SQL语句翻译成自然语言，使之更容易被理解，有助于实现安全控制。

早期的SQL解析使用Lex，Yacc的比较多。虽然Oracle已经将ANTLR应用在SQL Developer的IDE中，但是SQL Developer并非开源使用。因此使用ANTLR进行SQL解析的研究目前还很少，进行SQL翻译的工作还未见报道。在使用ANTLR解析SQL并且将结果进行进一步分析是一个新的尝试。本文针对数据库安全，基于LL文法，采用ANTLR工具，实现了SQL的词法和语法解析器，并进一步实现了SQL语句到自然语言的翻译。最后，将SQL解析和翻译功能应用在数据库防火墙和安全审计系统中，对于提高数据库的安全防护能力具有很大的实际意义。

1　SQL解析器

1.1SQL词法解析器实现

SQL语言的词法主要分为标识符、数字、注释与提示、字符串、时间、区间和变量。基于ANTLR实现SQL词法解析首先要定义词法的fragment。所谓的fragment是词的一部分，而不会出现在词法解析的结果中。以数字和时间为例分析。

（1）数字Number。在SQL语言中表示数值类型。数值类型包含整数部分、小数部分、符号部分、指数部分和类型部分，其中指数部分是一个大写字母“E”或者一个小写字母“e”加一个带有符号的整数，如果不带符号默认为“+”。数值类型中，整数部分和小数部分必须包含其中之一，其他部分都是可选的，只包含小数部分时允许“.”出现在数值的最前面，例如“.5”表示“0.5”。数字的DFA表示如图1所示。

图1　Number词法分析图

（2）时间Datetime。时间格式比较固定，必须由关键字DATE开头，后面是一个表示时间的字符串，如果不是表示时间的字符串，SQL语句认为是错误的语句。另外，时间戳也被认为是一种时间格式，必须是由关键字TIMESTAMP开头，时间戳格式包含AT TIME ZONE可选结构，表示时区。时间的DFA表示如图2所示。

图2　Datetime词法分析图

根据这七种类型的自动机表示将其转换成对应的EBNF表示。使用“*”、“+”替换DFA中的循环结构，“*”表示可以跳过的循环结构，“+”表示不可跳过的循环结构。使用“|”表示DFA中的选择结构，在每个分支之间使用“|”表示选择。使用“？”表示DFA中可跳过的结构，将“？”放在可选结构的后面。在每个单元上使用“（）”将不可拆分的部分包含在内，就可以使用简单的EBNF语句描述复杂的DFA。另外，对于SQL的保留字要做单独的识别。例如：select要定义成SELECT：SE L E C T；这样select无论是“Select”还是“seLECT”都能识别出来。针对不同的SQL语句它的保留字也是不一样的，需要单独定义语法文件。SQL语言中是不区分大写字母和小写字母的，在ANTLR中单独的字母应该被当作碎片来定义，不能出现在最终的解析结果中，使用“fragment”修饰。字母包含键盘上所有能够输入的符号以及键盘上不能直接输入的UNICODE字符。SQL语言中使用的数字是阿拉伯数字0～9，单独的数字也要使用“fragment”修饰。

1.2SQL语法解析器实现

语法解析器实现过程中需要将所有的语言模式转化为EBNF描述的规则语句。SQL语言的范式使用的是EBNF描述，要将其转换成EBNF描述的规则。EBNF范式的好坏虽然不会影响到解析的效率，解析效率只与被解析的字符串的长度有关系，但是会影响到解析器生成的效率。坏的EBNF规则会导致生成的过程中出现大量的递归调用和栈操作，生成的时间和内存会成指数级增长。所以EBNF的规则还是有很多细节需要注意。规则的深度不能太深，并且需要或关系的规则尽量将K值控制到最低，因为规则生成的复杂度是（K*N）M。其中，K是向后查看的token数；N是或关系连接的多个规则；M是规则嵌套的层数。由于一个子规则经常被多个规则引用，所以子规则会影响所有引用它的规则的生成效率。降低子规则的层数和减小K值是有效的提高生成效率的方法。N值一般难以降低，除非规则本身就有冗余，但是这种情况比较少见。

使用ANTLR将语法文件编译成解析器，实现过程类似于词法分析。输入由String变成tokens，ANTLR自身的语法不变。使用全部的语法生成语法解析器，在生成过程中系统采用LL（K）分析方法。ANTLR支持预测功能，可以在特定的地方使用预测。设置回溯位置，对输入的tokens进行预测，降低解析时间和消耗的资源。 解析的结果可以得到每一个token的属性、内容和值。再对生成的一维AST树做递归下降，将AST树的二维层次结构补全，得到具有层次和附属关系的二维语法树。AST树上的节点对于解析来说并不都是必须的，在生成过程中将不需要的节点删除，留下必须的结果，精简AST树对于快速提取重要信息有很大的帮助。在AST树生成的过程中直接嵌入SQL语句检查代码，同时可以在解析过程中直接根据token的类型判断输入词的意义，从而将SQL中最重要的表、视图、字段直接提取出来，同时判断出SQL的类型和操作对象的类型。更进一步，将SQL中存在的安全隐患的类似缓冲区溢出和SQL注入攻击的风险直接检测出来。

2　SQL翻译

2.1SQL语句AST的构建

ANTLR语法解析的输出结果就是抽象语法树。将语法解析的结果设置为AST，ANTLR每一个规则解析之后就能生成AST结构。默认情况下生成一维语法树，所有的结果在同一个层次上。如果需要自定义抽象语法树的返回结果，需要在语法解析过程中加入AST构建规则。ANTLR的抽象语法树构建语法非常简单，标准语法只有三种：

（1）“^”，前面的符号作为父节点；

（2）“！”，前面的节点不出现在语法树上；

（3）“->^（……）”，“->”左侧是语法解析语句，右侧是抽象语法树生成语句，括号内是一棵子树，第一个符号是树的根，其他元素是第一个元素的子节点。例如：（A+B）->^（+A B）。

由于SQL语言是结构化的查询语句，在构建抽象语法树上有先天的优势。构建语法树时只需要考虑SQL中查询的主体，忽略不需要的部分，其中最重要的就是表、字段、视图和在表、字段、视图上的操作。查询语句是SQL语句中最复杂的语句，可以使用嵌套和递归的方式，语法结构十分灵活。由于其他语言相比于查询语言简单很多。本节用查询语句举例说明SQL语句抽象语法树生成过程。

查询语句可以包含for update语句，但不是必须包含，for update和查询是平行关系，一个查询只能在最后包含一个for update语句，这里只需要将最后的“；”裁剪掉：

selectStatment：subquery（for_update_clause）？（′；′！）？；

子查询可以有嵌套，也可以和其他子查询做交、并、异或操作，最终结果做一次排序：

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

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

（order_by_clause）？；

查询块是最终的查询，包含查询的各个功能模块，模块在结构上是平行的：

query_block：（subquery_factoring_clause）？

select_clause from_clause

（where_clause）？

（hierarchical_query_clause）？

（group_by_clause）？

（model_clause）？

（having_clause）？

2.2AST转换成自然语言

SQL语句的语言结构更接近英文的语言结构，与中文的语言结构差别较大，简单的对关键字替换不考虑语义是不能达到翻译效果的，只会让结果更加匪夷所思，举例说明：

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‘admin’in（SELECT name FROM user）；

直接替换翻译结果为：

查询concat（查询user（），′--′，database（）），name从逻辑表（查询date，user，action，name从logs条件满足id等于if（ascii （substr（（查询user（）），1，1））等于1，1，0）条件满足‘admin’在（查询name从user）。

使用树解析器将抽象语法树转换成自然语言。由于抽象语法树采用递归的方式表示语法结构，在解析的过程中也使用递归的方式，并将语法习惯调整为汉语语言的语法习惯。在转换的过程中补充虚词和连接词，增加语言的连贯性。最后对翻译结果进行格式化，增加缩进便于阅读。考虑汉语的阅读习惯，可以将较长的句子翻译成子句的形式，最后，根据数据库建模表和数据库方法表，可以将翻译结果中的方法名、字段名、表名等翻译成中文，翻译时只要判断出被翻译内容的类型，然后查找相应的数据表，就能将剩下的英文部分翻译成中文，生成最终结果为：

模块1：

查询获取用户方法（user）的执行结果的返回数据

模块2：

从用户表（user）中查询姓名字段（name）的返回数据

条件1：

标识字段（id）等于条件判断方法（if）［转换成ascii编码方法（ascii）［子串方法（substr）［｛模块1｝，1，1］的返回结果］］的返回结果等于1，1，0］的返回结果

条件2：

字串‘admin’在［｛模块2｝］里

模块3：

从日志表（logs）中查询满足｛条件1｝条件的日期字段（date）和用户字段（user）和动作字段（action）和姓名字段（name）的返回数据

模块4：

逻辑表［｛模块3｝］

模块5：

查询方法用户方法（user）执行结果的返回数据

模块6：

连接字符串方法（concat）［｛模块5｝，′--′，方法数据（database）的执行结果］的执行结果

主查询：

从｛模块4｝中查询满足｛条件2｝条件的｛模块6｝和姓名字段（name）的返回数据。

翻译过程中需要调整语序，语序的调整主要使用栈实现，将需要调整语序的句子放入栈中，返回时再从栈中取出。树解析器翻译的过程如下：

（1）当前指针在根节点，获取节点，判断节点类型，类型不一样，Tree Walker进入不同的解析模块，这里以SELECT语句为例；

（2）获取一个子节点，判断节点的类型；

（3）如果是 SELECT语句，那么就调用 select_tree_walker，然后调整语序，执行stack.push操作，将结果先缓存。如果是FROM语句，调用from_tree_walker的结果放入output流中。如果是WHERE语句，调用where_tree_walker，调用stack.pop将SELECT语句出栈，和WHERE语句合并格式，结果放入到output流中；

（4）tree_waker是一个递归的过程，在解析过程中，将查询的条件和子模块生成独立的翻译模块；

（5）tree_waker在执行的过程中遇到需要查询建模表和函数表的情况，将查询的结果输出；

（6）重复步骤（2）～步骤（5）过程，直到input流为空。

Tree Walker对部分叶节点的翻译规则如表1所示。

3　系统实现与效果分析

本系统目前已在数据库审计和防火墙产品有所应用，数据库审计与防火墙引擎设置界面如图3所示。要对数据库进行审计或者建立防火墙，先要添加数据库引擎。审计数据获取方式有很多种，在设置界面进行设置。

表1　Tree W alker部分规则表

图3　DAF审计防火墙设置窗口

规则设置界面部分截图如图4所示。规则可以设置表、字段、SQL类型等，SQL解析中能够获取的所有信息都可以在规则界面上设置。通过对SQL语句进行解析获取语句的类型，然后对不同类型的SQL语句设置不同的规则。

图4　DAF规则设置窗口

告警设置界面如图5所示。规则匹配上之后设置相应的告警级别，就会产生相应的告警信息。

图5　DAF告警设置窗口

检索界面如图6所示。可以对审计日志进行检索，获取数据库用户的操作行为。

告警界面如图7所示。SQL语句触发告警规则就会产生告警，在告警界面上可以查看告警细节。

图6　DAF检索界面

图7　DAF告警查看窗口

图7中select 1 from db_queue_tables where 1=2，其中条件1=2是常量比较，判定SQL语句可能是SQL注入语句，产生高风险告警。然后通过SQL翻译将SQL语句翻译成对应的中文，select 1 from db_queue_tables where 1=2的翻译结果为“从表dba_queue_tabkes中查询满足条件1=2的值1的返回结果”。

最新流量界面如图8所示。在最新流量界面可以实时显示最新的SQL操作，随时监控SQL操作动态。基于SQL解析和翻译的数据库审计和防火墙产品可以在审计模式对操作进行溯源，起到对不法分子进行震慑的作用。防火墙模式可以通过阻断方式对风险进行控制，从而提升数据库系统的安全性。

图8　DAF最新流量界面

4　结　论

本文通过分析标准SQL语言的词法规则和语法规则，并基于ANTLR设计并实现了SQL词法解析器和语法解析器；使用SQL词法解析器和语法解析器实现了SQL语句辅助分析功能，实现了SQL语句的词法分析和语法树生成；通过解析语法树提取SQL信息并将SQL语句翻译成自然语言；并将SQL解析和翻译的功能应用在

数据库综合审计系统中。SQL解析和翻译模块已经被应用在商业数据库防火墙和安全审计系统中，并且被部署到多个数据中心。系统可以监控数据库的所有活动，阻断危险操作和攻击，从而达到增强数据库安全的目的，为保障数据库及信息系统的安全逐步发挥作用。

本文设计了一种基于反激式直流变换器的动力电池均衡电路，给出了系统建模方法，并在PSIM环境下完了系统仿真电路，针对8种典型非均衡状态进行了全面的仿真实验，最后通过实验证明了系统建模的有效性。由于建模过程忽略了变换器磁阻、磁滞、磁饱和现象，同时简化了电路寄生参数，需要进一步完善。

［1］张博，类艳春，廉小伟.数据库安全漏洞浅析［J］.保密科学技术，2012（3）：23-25.

［2］刘三献.基于ANTLR的Gaussian词法分析器和语法分析器的分析与设计［D］.兰州：兰州大学，2009.

［3］闫红岩.SQL语句分析及数据库安全研究［J］.贵阳：贵州大学，2006.

［4］侯智斌，孙彦飞，吕曹芳.基于入侵容忍技术的数据库安全策略研究［J］.现代电子技术，2011，34（7）：78-80.

［5］PARR T，FISHER 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—），女，内蒙古呼和浩特人，硕士，讲师，高级工程师。主要研究方向为计算机技术。