一种基于模板重构与语义实例化的SQL语句生成方法

本公开涉及计算机领域，更具体地讲，涉及一种面向不同数据库管理系统的基于变异的通用模糊测试方法。

背景技术：

1、数据库管理系统（dbms）是现代软件系统中的基础组件。随着数据库功能不断扩展，dbms实现日趋复杂，容易出现崩溃、内存错误、逻辑错误、性能异常等缺陷。dbms模糊测试通过自动生成大量sql测试用例并执行目标数据库，能够有效发现隐藏缺陷和安全漏洞。现有dbms模糊测试技术主要包括基于变异或基于语法规则的生成两种方法。这些方法在主流的dbms上能够有效挖掘漏洞，但在跨dbms、跨sql方言场景下仍存在以下不足：

2、不同dbms的sql方言差异明显，分页、函数、类型、ddl/dml语法、表达式和约束等存在大量实现差异，导致测试器通常需要针对每一种dbms编写大量语法适配代码。而方言适配代码维护成本高，且往往只覆盖目标dbms的一部分语法特征，使得生成的sql结构多样性不足，覆盖率和漏洞发现能力受限。已有通用模糊测试方法虽然可以减少部分方言适配工作，但在语法结构多样性和语义有效性之间仍存在不足。部分语义实例化方法依赖前置sql语句的静态上下文，如果前置语句未能成功执行，后续表、列、类型、外键、嵌套查询结果等语义关系会出现错误和冲突，导致大量无效输入。

3、因此，亟需一种面向多种sql方言的通用dbms模糊测试方法，其能够在减少人工语法适配的同时，生成结构多样且语义有效的sql测试输入，从而提高dbms测试覆盖率和漏洞发现效率。

技术实现思路

1、本公开的实施例的目的在于提供一种基于模板重构与语义实例化的sql语句生成方法，旨在解决在减少人工语法适配的同时，提高dbms测试覆盖率和漏洞发现效率的问题。

2、在一个总的方面，提供一种基于模板重构与语义实例化的sql语句生成方法，面向不同结构的数据库管理系统，首先输入sql种子，通过sql结构模板语料库构建模块生成去语义化的结构模板语料库；然后利用所述结构模板语料库，通过通用变异模块对输入sql进行结构级重构变异得到sql骨架；最后将sql骨架输入语义实例化模块，结合目标数据库管理系统的运行时模式信息对sql骨架进行语义实例化，生成可由目标数据库管理系统执行的sql测试输入，并由所述目标数据库管理系统执行；在检测到目标数据库管理系统出现崩溃、内存访问异常或断言失败时，记录触发相应异常的sql测试输入，提取异常类型和调用栈信息，并生成数据库缺陷检测结果。

3、所述sql结构模板语料库构建模块的具体实现方式为：

4、步骤①：收集有效sql种子，并对sql种子进行预处理，过滤无法解析或不适合作为结构模板来源的sql语句；

5、步骤②：利用通用sql解析器解析sql种子，将不同sql方言中的语句形式转换为统一抽象语法树表示，使具有相同逻辑结构但语法形式不同的sql语句能够被统一表达；

6、对于sql种子及其所属sql方言，利用支持方言的通用sql解析器执行解析，得到解析树；由所述通用sql解析器将不同方言中表达相同语法功能的节点规范化为统一节点类型，并将规范化运算记为，得到统一抽象语法树。遍历中的各节点，将表名、列名、常量值和别名分别替换为表占位节点、列占位节点、常量占位节点和别名占位节点，形成去语义化运算e，并得到去语义化统一抽象语法树。

7、对于节点，以表示其统一结构，其中为统一节点类型，为该节点在父节点中的语法角色，为子节点数量，至为按照原有语法顺序排列的子节点；转换过程中保留节点之间的父子关系、语法角色及顺序约束。对于不同sql方言中书写形式不同但语法功能相同的结构，由通用sql解析器映射为相同的统一节点结构；对于方言特有但能够被解析的节点，保留解析器输出的节点类型及其子树结构，使其仍可作为模板提取和同类型节点变异的对象

8、步骤③：遍历统一抽象语法树，去除其中的具体语义信息，保留sql语句的语法结构关系，所述具体语义信息为与特定数据库实例相关的信息；

9、步骤④：将抽象语法树中的完整树和各级子树作为候选结构模板，并根据节点类型、父子关系、子节点顺序和结构特征对候选结构模板进行等价判断和去重；

10、所述等价判断包括：遍历去语义化统一抽象语法树，将完整树以及以每一节点为根节点的全部子树提取为候选结构模板集合。对于任一候选结构模板，以其根节点为起点递归生成规范化结构编码：当为叶节点时，；当r依次具有子树至时，，其中子树编码按照各子节点在父节点中的语法角色和原有顺序排列。两个模板和的结构等价判定函数为，其中为条件成立时取1、否则取0的指示函数；当时，判定两个模板具有相同的去语义化语法结构。为提高去重效率，对计算结构哈希值，先按照根节点类型和结构哈希值分组，再对哈希值相同的模板执行递归结构比较以排除哈希冲突；每一等价类保留一个代表模板，并记录该结构的出现次数及来源方言。最后建立节点类型索引，使变异模块能够按照待变异节点的统一节点类型检索相同类型的模板。

11、步骤⑤：为去重后的结构模板建立节点类型索引，使后续变异模块能够根据待变异节点的类型快速检索相同或兼容类型的模板；

12、步骤⑥：输出sql结构模板语料库，所述语料库包括多个去语义化sql结构模板以及对应的节点类型索引信息。

13、所述具体语义信息包括表名、列名、常量值、别名。

14、所述通用变异模块的具体实现方式为：

15、步骤①：将待变异sql语句解析为统一抽象语法树，并确定其中可参与变异的候选节点；

16、确定候选节点包括：将待变异sql语句解析并去语义化，得到统一抽象语法树；对中的节点集合进行遍历，并根据节点的统一节点类型查询节点类型索引，将候选节点集合确定为。对于被选中的候选节点，从中选择根节点类型相同的模板子树，并以为根取得原始子树。以从子树根节点出发的子节点角色路径作为节点地址，对和进行结构对齐：

17、步骤②：遍历候选节点，根据当前节点的节点类型，从sql结构模板语料库中检索相同或兼容节点类型的结构模板；

18、步骤③：将原始sql抽象语法树中待变异节点 对应的子树记为 ，将检索得到的结构模板记为 。对 与 进行结构对齐，并将对齐后的节点位置集合记为 。针对任一对齐位置 ，分别以 和 表示原始子树和结构模板在该位置对应的节点；当相应位置不存在节点时，以符号 表示；以 表示节点类型。共有节点集合、原始独有节点集合和模板独有节点集合分别表示为：

19、

20、

21、步骤④：对于，利用随机变量选择保留或采用；对于，利用随机变量选择保留或删除；对于，利用随机变量选择插入或舍弃。按照父节点先于子节点的顺序重建子树，并满足子节点被保留或插入时其父节点必须存在的结构一致性条件；将重建子树替换得到新的抽象语法树。；

22、步骤⑤：根据上述节点保留、删除和插入结果重构抽象语法树，生成新的sql结构；

23、步骤⑥：对重构后的sql结构进行合法性检查，若结构无法被解析或不满足基本语法约束，则重新选择结构模板或回退至上一有效结构；若检查通过，则输出去语义化sql骨架。

24、所述基于动态模式信息的语义实例化模块的具体实现方式为：

25、步骤①：连接目标数据库管理系统，在每轮sql骨架实例化前，通过目标数据库管理系统提供的系统目录、元数据查询接口或数据库连接接口，动态读取当前数据库实例中的数据库名、模式名、表名、视图名、列名、列类型、主键、外键、唯一性约束、索引信息以及可调用函数的参数类型和返回类型，并将读取到的元数据信息组织为当前模式信息集合；当目标数据库实例中的表、列或约束发生变化时，重新读取并更新所述当前模式信息集合，使语义实例化过程使用与目标数据库实际运行状态一致的模式信息；

26、步骤②：解析sql骨架中的语句结构和作用域关系，识别主查询、子查询、嵌套子句、表达式、连接条件、分组条件和排序条件等语义片段，并根据各语义片段之间的包含关系构建作用域树：

27、

28、其中， 表示语义片段节点集合， 表示语义片段之间的直接嵌套关系集合；对于任一语义片段 ，以 表示该语义片段在作用域树中的嵌套深度，并按照嵌套深度由大到小生成实例化序列：

29、

30、所述实例化序列满足：

31、

32、从而优先实例化最内层语义片段，再逐层实例化对应的外层语义片段；

33、步骤③：对于实例化序列中的当前待实例化语义片段 ，确定该语义片段在作用域树中的直接内层语义片段集合：

34、

35、从当前模式信息集合 中提取在语义片段 的作用域内可访问的表、列、视图、类型、函数及约束信息，形成模式候选集合 ；同时获取各直接内层语义片段已完成实例化后形成的输出模式 ，并构建当前语义片段的候选语义对象集合：

36、

37、其中， 包括对应内层语义片段可由外层语义片段引用的输出列名称、输出别名及数据类型；当语义片段 不包含直接内层语义片段时，其候选语义对象集合由构成；

38、步骤④：

39、针对当前语义片段 中的表、列、常量、表达式及函数参数等占位对象 ，从候选语义对象集合 中选择满足可见性约束、类型兼容约束、引用关系约束和语法位置约束的候选语义对象进行填充；对于任一候选语义对象 ，分别建立下列判定函数：

40、

41、

42、其中， 为可见性判定函数，用于判断候选语义对象 是否属于占位对象所在作用域可访问的数据库对象或内层语义片段输出； 为类型兼容判定函数，用于判断候选语义对象的数据类型是否与占位对象所在表达式所要求的数据类型相同，或者是否属于目标数据库管理系统允许的隐式兼容类型； 为引用关系判定函数，用于判断候选列与已选表、连接列、分组列、函数参数及内外层引用对象之间的依赖关系是否成立； 为语法位置判定函数，用于判断候选语义对象的对象类别、参数数量及语法角色是否允许出现在当前占位位置。

43、根据上述判定函数构建综合约束函数：

44、

45、并形成占位对象 的可用候选集合：

46、

47、当 时，从所述可用候选集合中选择候选语义对象填充占位对象 ；当时，确定未满足的约束类型，并重新选择与占位对象 存在引用关系或类型依赖关系的已填充对象，或者将当前语义片段标记为待回退修正片段；

48、步骤⑤：完成当前语义片段 中各占位对象的实例化后，获取该语义片段的投影表达式集合 ，并分别确定各投影表达式 的输出名称 和输出数据类型 ，构建当前语义片段的输出模式：

49、

50、当投影表达式设置有别名时，将相应别名作为输出名称；当投影表达式未设置别名时，根据其对应的列名、函数名或表达式类型确定输出名称；将所述输出模式与当前语义片段的作用域标识关联存储，并在实例化当前语义片段的直接外层语义片段时，将该输出模式并入外层语义片段的候选语义对象集合，使外层语义片段能够引用内层语义片段实际输出的列及对应数据类型；

51、步骤⑥：按照自底向上的顺序逐步完成各片段实例化，生成完整sql测试输入，并将其提交目标数据库管理系统进行解析或执行验证；若出现语义错误，则重新选择候选语义对象或回退修正相应片段，直至生成可执行sql测试输入。

52、所述模式信息包括数据库名、表名、列名、列类型、键约束、索引信息。

53、所述语义片段包括主查询、子查询、嵌套子句、表达式、连接条件、排序条件、分组条件。

54、所述占位对象包括表、列、常量、表达式、函数参数。

55、本发明实施例的所要实现的技术效果在于：

56、本发明将sql语法结构的生成与具体数据库实例中的语义对象选择相分离：前者由结构模板语料库和通用变异模块负责，以提高跨方言结构适配能力和sql结构多样性；后者由动态语义实例化模块负责，以提高生成sql在目标数据库中的语义正确性和实际执行概率。