系统软件安全学习贴

Pivot Query Synthesis

论文的目的为了检测数据库中的逻辑漏洞，其技术为数据透视查询合成

• 逻辑漏洞：代码正常运行给出结果，但是结果是错的


• 数据库查询特点与潜在漏洞举例：
  
  
  
  • 查询缓存->优化器（选择最优执行计划）->索引->数据表，数据库尽量不会碰数据表，能在缓存拿到就不解析，能用索引定位就不全表扫描，当数据表改变了，但是统计数据或者索引没有改变就会出现问题
  
  
  • 优化器在获取了统计数据后，数据表改变，导致统计数据不在真实
  
  
  • 子表继承父表，主键一致，两个表独立但是查询父表的时候会查询子表，当子表与父表出现主键一致的时候，出现数据丢失
  
  
  • SQL语句中的双重否定失效： NOT(NOT 123) 不是123，MySQL在翻译的时候由于123非零，即1，则NOT 123是0，再否定是1，即NOT(NOT 123) 为1，当建立语句NOT(NOT 123) != 123时本来是非，但变成了是
  
  
  
  

比如：当前语句创建一个表，并建立非空索引，在将表中进行赋值，最后选择值中非1的所有元素，而在选择过程中，由于建立了一个index的索引，而这个索引中没有NULL，数据库在执行最后一句时使用的index进行访问，把NULL省略掉了

• 传统方法：差分测试：同一个语句放在多个不同数据库进行执行，查看返回的异同，由于不同系统的执行语句在细节上有所差异，SQL dialects vary significantly，很难将其放在同一基准下进行判断


• 技术的基本逻辑：首先随机挑选数据作为目标，在随机生成一个搜索条件，将此条件进行修改使其所搜索的目标中必然包含第一步确定的目标数据；之后再交给数据库去搜索，如果结果没有目标数据，说明有bug

• 
  

  结果：为许多主流的数据库找到了大量的漏洞，如SQLite（个人本地）、MySQL（学生、科研、互联网开发），PostgreSQL（复杂业务）

  
  


• 
  

  细节实现：

  
  

1、生成随机的数据表与元组，并随机设置一行pivot row，其中的每列都是从多个随机生产的数据表中挑选的某列的某个元素

2、随机生成一个查询语句并评估：利用递归函数随机构建语法树，随机生成一个查询表达式，代入pivot row值计算出最终的布尔值，并进行值的修改保证最后的布尔值一定为TRUE，利用表达式结合不同的数据库管理系统生成各自的查询语句

3、将查询语句在数据库管理系统中执行，查看返回结果，如果没有pivot row，说明有bug

• 进一步细节：
  
  
  
  • 语法树的构建：使用一个递归函数，在提前确定好最深深度后进行递归查询语句的构建，当当前深度小于最大深度时，可以选择在常量、表属性和运算符中随机选择，如果选择运算符，则继续递归；如果当前深度为最大深度，则只能在常量与属性中选择
  
  
  
  

• 
  
  
  
  • 表达式的评估：调用递归函数：execute（），利用抽象语法树评估，需要手动实现，常量叶子节点赋值常量，属性叶子节点赋值pivot row的值，分支节点依据底层节点与自身给出output，最终的输出有三种：TRUE、FALSE、NULL
  
  
  • 表达式修改：调用函数rectifyCondition，根据最后的输出进行表达式的修改：如果本身为true，则不变，如果为false，则取NOT，如果为NULL，则取IS NOT NULL
  
  
  • 生成查询语句：结合不同数据库内部的不同细节，生成各自的语句
  
  
  
  


• 
  

  执行细节：

  
  
  
  
  • 错误处理：一些语义的错误为了提高效率，作者定义了一个可能遇到的错误清单，提前定义好可能出现的错误，这些错误都是具体关键词缺失或者存在造成的
  
  
  • 性能：SQLancer优化硬件，实现了并行提高性能，降低SQL执行的CPU占比
  
  
  • 代码量：10-30行（较少），过多的代码量会导致超时
  
  
  • 需要动态获取数据库的状态，不提前预设表结构
  
  
  • 在函数操作执行时无需必须考虑所有可能，当在执行中出现异常，可以随时被抛出，并生成一个新的表达式；这种方法也会丢弃一些已知的错误
  
  
  • 通过SQLancer获取的值会暂时缓存，同时这些值可能引发一些边界条件
  
  
  • 对于每个数据库管理系统，作者涉及到的范围很广泛但是不全面，都支持整数和字符串类型
  
  
  
  

论文名称：Testing Database Engines via Pivoted Query Synthesis Manuel Rigger and Zhendong Su, ETH Zurich https://www.usenix.org/conference/osdi20/presentation/rigger

• 
  

  核心问题：解决优化器的过度优化问题

  
  


• 
  

  解决方法：对于同一个查询语句进行改编，在逻辑一致的基础上去掉可能进行优化的部分，将优化前与优化后的语句分别放入其中进行执行，来查看结果的行数与非优化的True的数量是否相同

  
  


• 
  

  相比于POS： POS在生成一个查询表达试之后需要首先进行模拟实验，保证目标行结果为TRUE，而且不同的平台的语句也不一样，需要进行不同的处理,因此需要为每个数据库写一套查询生成器和逻辑模拟器保证生成的随机条件对于目标数据是TRUE,NoREC则拜托了这项工作，将其丢给数据库自己做；此外POS是单行目标，很难处理重复错误

  
  


• 
  

  方案细节：优化器优化的核心关键词是where，那么将where进行改编，比如：
  
  

  
  


• 
  

  如图，我们将where子句的内容放在select后面，那么所有的元组都会进行比较，而非通过where优化掉。

  
  

此种方法并不能完全的摆脱优化器的影响

----Detecting Optimization Bugs in Database Engines via Non-Optimizing Reference Engine Construction

“Finding Bugs in Database Systems via Query Partitioning”

核心思想：随机生成一个查询语句并获取查询结果，然后将原查询语句进行拆分，可以基于布尔进行查询，从而进行分区查询，获得的三个分区进行合并，然后与初始的查询结果进行比较，查看数据是否有丢失，根据丢失的数据来判断是否有逻辑错误（有个问题是如果这个初始的查询语句本身就是有问题的查询，而分区查又照着错误的重新查一遍，或浮点数舍入问题可能会由于不同的执行语句出现精度的丢失）

usenix现在不办osdi了吧，好老的会了，现在只有四大security了，差分sqlengine的思路也比较旧了，语法树和特性不一样的话还得手动写好多模板。之前nus的coopauthor做了一篇基于llm对sql-like的差分测试，不用自己手动对每个新的engine迁移特性和语法树了。

现在单纯差分sql-like这类系统已经很难投了 ^-^

嗯呢，因为才接触这一块，从头了解，所以再看一些比较老的文章

可以的佬，testing这个方向其实更需要简单有效的思路直接力大转飞，可以看看php fusion那一篇，也是我coopauthor之前在nus的同门发的，非常有意思，我第三篇工作也准备做一个思路像一点但是用模型微调。

“Testing Database Systems via Differential Query Execution” (pdf)

• 基本思想是：具有相同谓词（WHERE子句）的不同类型的SQL查询（SELECT、UPDATE、DELETE）在逻辑上应该访问数据库中相同的行。如果一个数据库管理系统（DBMS）对这三种查询的处理结果不一致，就说明存在逻辑漏洞

• 细节：设置了两个属性，分别是rowId和updated，第一个的含义是唯一标识某一行（即便是多个表也不会重复），第二个来表示是否update修改，我们在进行select与update和delete时，会通过这两个数进行判断：在选择的时候会记录选择出来的rowId，在update时会根据update的标记位来获取对应的rowId，delete会根据删除前后哪些rowId确实来记录。获取这三个操作的rowId后进行比较

“CERT: Finding Performance Issues in Database Systems Through the Lens of Cardinality Estimation” (pdf)

• 
  

  背景：用户在通过SQL进行查询的时候，DBMS会进行解析出每一步，优化器会进行每一步的基数估计，根据基数估计生成一个执行计划（数结构），当基数估算错误的时候（比如很少的行却估计成了很多的行）优化器会选择基于当前基数的最合适的行为，真实情况下数据很少可以用一个高效的做法，但是由于估算出错，于是选择了一个适合大量数据，但是对于少量数据更加低效的做法，造成了性能上的缺失。这篇论文就是为了找基数估算的bug

  
  


• 
  

  基本原理：如果一个查询 Q 被修改得更加“严苛”（通过添加限制条件）得到查询 Q ′ ，那么 Q ′ 实际返回的行数必然小于或等于 Q 的行数 ，如果预估 Q ′ 的行数反而更多，就说明优化器存在逻辑缺陷，可能导致选择错误的执行计划，进而引发严重的性能下降。

  
  

严格限制的条件：

• 进一步细节：当对原查询语句进行进一步限制的时候需要检查这两条查询语句是否结构相似，防止由于限制前后导致的计划的不同造成的bug的误报：

“Keep It Simple: Testing Databases via Differential Query Plans” (pdf)

• 核心点：对于同一个查询，通过修改查询语句的语法结构，使其采用不同的执行计划，比较在不同的执行计划下的查询结果是否一致，如不一致说明有漏洞

• 
  

  数据库与查询语句都是随机生成的

  
  


• 
  

  对于查询语句，在逻辑上不改变查询结果的基础上，添加SQL的关键字（查询提示与系统变量）

  
  
  
  
  • 
    

    查询提示：a comment-like clause（注释）in a query and can affect the behaviors of the query optimizer.

    
    
  
  
  • 
    

    系统变量：使用SET语句来配置系统变量

    
    
  
  
  • 
    

    通过这两种变量进行查询控制是可以实现的，因为在SQL中这两种是有限的（“We examined DBMS documents and extracted 32 query hints and 26 options for the system variable optimizer_switch in MySQL, 37 options for the system variable optimizer_switch in MariaDB, and 22 query hints in TiDB for enforcing different query plans.” (pdf) ）

    
    
  
  
  
  


• 
  

  防止误报：对于一些查询本身的结果就是不固定的，而非是查询计划出现的bug，比如由于当有多个同值是，随机选出一个来，虽然查询计划一样，但由于通过结果来判断，会造成误判

  
  
  
  
  • 处理逻辑：把测试用例最小化之后在不改变数据的前提下打乱表中数据行的顺序，重新进行查询，如果结果变了说明存在误报，直接跳过
  
  
  
  

Permutation函数的作用是打乱数据库顺序

“Constant Optimization Driven Database System Testing”

• 
  

  核心思想： 将查询中的复杂表达式替换为其运行时的常量结果，查询结果不应改变 。

  
  
  
  
  • 
    

    原始查询 (O)： SELECT COUNT() FROM t0 WHERE (SELECT COUNT() FROM v0 …); —— 包含一个复杂的子查询 。 执行结果： 1 。

    
    
  
  
  • 
    

    辅助查询 (A)： 单独运行那个子查询，得到结果为 0 。

    
    
  
  
  • 
    

    折叠后查询 (F)： 将原始查询中的子查询直接替换为常量 0：SELECT COUNT(*) FROM t0 WHERE 0; 。 执行结果： 0 。

    
    
  
  
  • 
    

    结论： 逻辑上 O 和 F 应当等价 。这种结果不一致（1 vs 0）暴露了 SQLite 在处理含有聚合子查询的复杂计划时存在优化漏洞

    
    
  
  
  
  

[image]### “Constant Optimization Driven Database System Testing”

• 
  

  核心思想： 将查询中的复杂表达式替换为其运行时的常量结果，查询结果不应改变 。

  
  
  
  
  • 
    

    原始查询 (O)： SELECT COUNT() FROM t0 WHERE (SELECT COUNT() FROM v0 …); —— 包含一个复杂的子查询 。 执行结果： 1 。

    
    
  
  
  • 
    

    辅助查询 (A)： 单独运行那个子查询，得到结果为 0 。

    
    
  
  
  • 
    

    折叠后查询 (F)： 将原始查询中的子查询直接替换为常量 0：SELECT COUNT(*) FROM t0 WHERE 0; 。 执行结果： 0 。

    
    
  
  
  • 
    

    结论： 逻辑上 O 和 F 应当等价 。这种结果不一致（1 vs 0）暴露了 SQLite 在处理含有聚合子查询的复杂计划时存在优化漏洞