一天自动发现四大数据库 100+ 漏洞,浙大研究获 SIGMOD 2023 最佳论文
2023-05-17 13:23:54来源:ZAKER科技
机器之心专栏
机器之心编辑部
本文中,浙大的研究者提出了一种名为 Transformed Query Synthesis(TQS)的方法。在运行了 24 小时后,TQS 成功找到了 115 个漏洞,包括 MySQL 中 31 个、MariaDB 中 30 个、TiDB 中 31 个、PolarDB 中 23 个。
(资料图片)
2023 年度的 ACM SIGMOD/PODS 国际数据管理大会(SIGMOD 2023)将于当地时间 6 月 18-23 日在美国西雅图举办。近日,该会议公布了最佳论文名单,微软研究院的《Predicate Pushdown for Data Science Pipelines》和浙江大学的《Detecting Logic Bugs of Join Optimizations in DBMS》获奖。自 1975 年该会议始办以来,这是中国大陆研究团队首次获得该会议的最佳论文奖。其中浙大的研究提出了一种新颖的方法,可以自动发现 MySQL、MariaDB、TiDB 和 PolarDB 等数据库管理系统的逻辑漏洞。
过去几十年,现代数据库管理系统(DBMS)不断演进,可以支持多种不同的新架构,比如云平台和 HTAP,这需要对查询评估进行越来越复杂精细的优化。查询优化器(query optimizer)被认为是 DBMS 中最复杂和最重要的组件之一,其功能是解析输入的 SQL 查询,然后在内置成本模型的协助下生成高效的执行方案。查询优化器实现中的错误可能会导致出现漏洞(bug ) ,包括崩溃漏洞和逻辑漏洞。崩溃漏洞很容易检测,因为崩溃会导致系统立即停止。然而逻辑漏洞却容易被忽视,因为逻辑漏洞会导致 DBMS 返回难以检测的错误结果集。这篇论文关注的重心是检测这些无声的漏洞。在检测 DBMS 中的逻辑漏洞方面有一种新兴方法,即 Pivoted Query Synthesis(PQS)。该方法的核心思路是从表格中随机选定一个枢轴数据行(pivot row),然后生成以该行作为结果的查询。如果合成的任何查询都不能返回该数据行,那么就检测到了一个逻辑漏洞。PQS 主要用来支持单表中的选项查询,其报告的漏洞中 90% 都是仅涉及单表查询。对于使用不同连接算法和连接结构的多表查询(比单表查询更易出错),还存在很大研究空白。
下图展示了 MySQL 中连接查询两个的逻辑漏洞的。这两个漏洞通过使用本文新提出的工具都能被检测到。
图 1:DBMS 中连接优化的逻辑漏洞示例图 1 ( a ) 展示了 MySQL 8.0.18 中的哈希连接(hash join)的一个逻辑漏洞。在这个示例中,第一个查询返回了正确的结果集,因为其执行过程中使用了块嵌套循环连接(block nested loop join)。但是,第二个查询使用内部哈希连接(inner hash join)却出了问题,返回的是一个不正确的空结果集。这是因为其底层的哈希连接算法错误地认定 0 不等于 0。
图 1 ( b ) 中的逻辑漏洞源自 MySQL 8.0.28 中的半连接(semi-join)处理过程。在第一个查询中,嵌套循环内部连接会将数据类型 varchar 转换成 bigint,进而得到正确的结果集。而当使用哈希半连接执行第二个查询时,数据类型 varchar 会被转换成 double,从而导致数据准确度出现损失以及等值比较出错。
为多表连接查询的逻辑漏洞检测问题采用查询合成方法的难度远远超过单表查询的情况,这涉及到的挑战有两个:
结果验证:为了验证查询结果的正确性,之前的方法采用的是差分测试策略。其思路是使用不同的物理执行计划(physical plan,即数据库系统实际执行查询语句的方式)来处理查询。如果这些规划返回的结果集不一致,那么就可能是检测到了逻辑漏洞。但是,差分测试方法有两个缺点。其一,某些逻辑漏洞可影响多个物理执行计划并让它们全部生成同样的错误结果。其二,当观察到不一致的结果集时,需要人工检查生成正确结果的是哪一个执行计划,从而导致成本开销变得高昂。这个问题有一个可能的解决方案,即为任意测试查询构建真值(ground-truth)结果,但现有的工具并不支持这种操作;
搜索空间:对于给定的数据库模式,可生成的连接查询的数量随表格和列的数量呈指数级变化。由于我们不可能为了验证而枚举出所有可能的查询,因此就需要一种有效的查询空间探索机制,以便让我们尽可能高效地检测出逻辑漏洞。
针对以上难题,浙大的研究者提出了一种名为 Transformed Query Synthesis(TQS)的方法。在检测 DBMS 中连接优化的逻辑漏洞任务上,TQS 是一种普适且成本高效的全新工具。
针对上述第一个挑战,研究者提出的应对方法是 DSG,即数据驱动的模式和查询生成(Data-guided Schema and query Generation)。给定表示为一个宽表数据集,DSG 可基于检测到的范式将该数据集拆分为多个表格。为了加快发现漏洞的速度,DSG 还会向生成的数据库中注入一些人工噪声数据。首先,将该数据库模式转换成一个图(graph),其中节点是表 / 列,边是节点之间的关系。DSG 会在模式图上使用随机游走来为查询选择表格,然后再使用这些表格来生成连接(join)。对于涉及多表的特定连接查询,我们可以轻松从宽表格中找到其真值结果。这样一来,DSG 就能有效地为数据库验证生成 ( 查询,结果 ) 集合 了。
针对上述第二个挑战,研究者设计的方法是 KQE,即知识引导的查询空间探索(Knowledge-guided Query space Exploration)。该方法首先是将模式图扩展成一个规划迭代图(plan-iterative graph),其表示整个查询生成空间。然后将每个连接查询表示为一个子图。为了给生成的查询图评分,KQE 采用了一种基于嵌入的图索引,其可以在已经探索过的空间中搜索是否有结构相似的查询图。根据覆盖度分数引导随机游走查询生成器,以尽可能多地探索未知的查询空间。
为了展现该方法的通用性和有效性,研究者在四个常用 DBMS 上对 TQS 进行了评估:MySQL、MariaDB、TiDB 和 PolarDB。运行了 24 小时后,TQS 成功找到了 115 个漏洞,包括 MySQL 中 31 个、MariaDB 中 30 个、TiDB 中 31 个、PolarDB 中 23 个。通过分析根本原因,可归纳出这些漏洞的类型,其中 MySQL 中的漏洞有 7 种、MariaDB 有 5 种、TiDB 有 5 种、PolarDB 有 3 种。研究者已经将发现的漏洞提交给相应的社区并且收到了积极的反馈。
下面将通过数学形式描述所要解决的问题以及浙大提出的解决方案。
问题定义
数据库的漏洞有两种:崩溃和逻辑漏洞。崩溃漏洞来自于操作系统和 DBMS 的执行过程。它们会导致 DBMS 被强行终止,原因包括内存等资源不足或访问了无效内存地址等。因此,崩溃漏洞很容易被发现。相较而言,逻辑漏洞则更难以发现,因为数据库依然会正常运行,处理查询后也会返回看似正确的结果(并且大多数情况下它们确实会返回正确结果,但在少数情况下却可能读取错误的结果集)。这些无声漏洞就像是隐形炸弹,要更加危险一些,因为它们难以检测到,还可能影响到应用的正确性。
这篇论文为多表连接查询问题引入了查询优化器来检测逻辑漏洞。研究者将这些漏洞称为连接优化漏洞(join optimization bugs)。使用表 1 给出的标记法,连接优化漏洞检测问题可以形式化地定义为:
定义:对于查询工作负载中的每个查询,令查询优化器通过多个实际规划执行 的连接,并使用基本真值 验证其结果集。如果,则发现了一个连接优化漏洞。
表 1:符号说明表方案概述
图 2 给出了 TQS 的架构概况。给定一个基准数据集和目标 DBMS,TQS 通过基于数据集生成查询来搜索 DBMS 可能存在的逻辑漏洞。TQS 有两大关键组件:数据引导的模式和查询生成(DSG)和知识引导的查询空间探索(KQE)
图 2:TQS 概况DSG 将输入数据集视为一个宽表,并且除了原始元组外,DSG 还会刻意合成一些有易错值(比如空值或非常长的字符串)的元组。针对连接查询,DSG 会为该宽表创建一个新模式,其方法是将该宽表分成多个表,确保这些表符合基于功能依赖性的范式。DSG 会将该数据库模式建模成一个图,然后在该模式图上通过随机游走来生成逻辑 / 概念查询。DSG 会将逻辑查询具体化为物理执行计划,并通过不同的提示对该查询进行变换,使 DBMS 能够执行多个不同的物理执行计划,以搜索漏洞。对于一个连接查询,其基本真值结果是通过将连接图映射回宽表而得到。
在完成模式设置和数据拆分之后,KQE 将该模式图扩展为一个规划迭代图。每个查询都表示为一个子图。KQE 为历史中的查询图(即在已探索过的查询空间中)的嵌入构建一个基于嵌入的图索引。直观地说,KQE 的作用是确保新生成的查询图尽可能地远离其在历史中的最近邻,即这是为了探索新的查询图,而不是重复已有的查询图。为此,KQE 通过基于结构相似性(与历史中的查询图)为生成的查询图评分,同时使用自适应随机游走方法来生成查询。。
算法 1 总结了 TQS 的核心思想,其中第 2、10、12 行是 DSG,第 4、8、9 行是 KQE。
给定一个数据集和从 采样得到的宽表,DSG 将单个宽表 拆分成多表,这些表格组成符合 3NF 的数据库模式(第 2 行)。模式可以被视为一个图,其中表格和列是顶点,边代表的是顶点之间的关系。DSG 在 上使用随机游走来生成查询的连接表达(第 10 行)。事实上,连接查询可以被投射为 的子图。通过将子图映射回宽表格,DSG 可轻松地检索到该查询的基本真值结果(第 12 行)。KQE 将模式图扩展为一个规划迭代图(第 4 行)。为避免测试相似的路径,KQE 会构建一个基于嵌入的图索引来索引已有查询图的嵌入(第 9 行)。KQE 根据当前查询图与已有查询图的结构相似性来更新规划迭代图 G 的边权重 π (第 8 行)。KQE 为下一条可能路径评分,其引导着随机游走生成器,从而更倾向于探索未知的查询空间。
对于一个查询 ,TQS 通过提示集对该查询进行变换,以执行多个不同的实际查询规划(第 11 行)。最后,将查询 的结果集与基本真值 进行比较(第 14 行)。如果它们不一致,那么就检测到了连接优化漏洞(第 15 行)。
有关 DSG 和 KQE 的更多详细描述请阅读原论文。
实验结果
TQS 成功找到了 MySQL、MariaDB、TiDB 和 PolarDB 等数据库管理系统的一些逻辑漏洞,它们分为 20 种类型,其中 MySQL 的漏洞有 7 种、MariaDB 的有 5 种、TiDB 的有 5 种、PolarDB 的有 3 种,如下表所示。
相比于其它方法,浙大提出的 TQS 的整体表现也相当亮眼,在多项指标上都取得了显著更优的成绩,而各组件的有效性也通过控制变量实验得到了检验。但研究者也表示,TQS 目前关注的是等值连接查询。尽管如此,DSG 和 KQE 思想也可扩展到非等值连接的情况。唯一的难题是如何生成和管理查询真值结果 —— 在非等值连接的情况下,这些结果的规模将指数级增长。这方面还有待未来进一步研究。THE END
转载请联系本公众号获得授权
投稿或寻求报道:content@jiqizhixin.com
责任编辑:hnmd003
相关阅读
-
一天自动发现四大数据库 100+ 漏洞,浙大研究获 SIGMOD 2023 最佳论文
机器之心专栏机器之心编辑部本文中,浙大的研究者提出了一种名为TransformedQuerySynthesis(TQS)的方法。
2023-05-17 -
分析师称 iPhone 15 所需面板将在 6 月份开始生产 与正常年份相当_世界今日报
【TechWeb】5月17日消息,据外媒报道,有分析师在当地时间周日的一份报告中称,由于4800万像素后置主摄像头
2023-05-17 -
OPPO Reno10 系列官宣!将于 5 月 24 日发布,潜望长焦稳了|世界看点
OPPOReno系列的十代里程碑之作——全新Reno10系列终于官宣,将于5月24日14:30举行新品发布会。每一代Reno新
2023-05-17 -
三星或在开发用于 Windows on Arm 笔电的 Exynos 芯片,整合 AMD 的 GPU|速看
三星过往有推出WindowsonArm的Galaxy系列笔记本电脑,搭载的是高通的芯片,不过这些设备并不算很成功,这也
2023-05-17
相关阅读
-
一天自动发现四大数据库 100+ 漏洞,浙大研究获 SIGMOD 2023 最佳论文
机器之心专栏机器之心编辑部本文中,浙大的研究者提出了一种名为TransformedQuerySynthesis(TQS)的方法。
-
空调显示e6是什么意思?空调显示e6还能继续开着吗?
空调显示e6是什么意思?1、导致空调出现E6故障代码的原因有很多,比如说空调的主板或显示板坏了,主控板...
-
抖音ip地址可以改吗?抖音闪退是什么原因?
抖音ip地址可以改吗?抖音ip地址不可以改。 抖音IP属地是不支持用户手动修改的,是根据手机运营商提供的...
-
我爱我家谢勇:房产经纪大模型时代来临,以数字化穿越周期_实时
随着人工智能技术快速发展,AI大模型正加速进入各行各业。从2018年提出数字化战略以来,我爱我家已经在数字
-
空调外机需要防雨罩吗?空调外机不工作是怎么回事?
空调外机需要防雨罩吗?不需要的。使用空调的时候,外机不要遮盖空调防护罩,它会严重影响外机的出风散热...
-
新生儿医疗保险有什么用?多少钱?-新资讯
做大的作用就是给新生儿提供医疗保障。新生儿医疗保险主要作用是保障新生儿的医疗费用。由于新生儿的身体较
-
意外伤害保险有哪些保障?要多少钱?
意外身故保险金:在被保险人因意外身故时,保险公司会按照保单约定的金额给付一定比例的身故保险金,帮助家
-
新生儿有必要买保险吗?新生儿可以买哪些保险?
看自身的实际情况和需求选择。新生儿由于年龄小,身体较为脆弱,因此存在许多健康风险。对于一些重大疾病或
-
天天热推荐:意外伤害保险费由谁支付?要多少?
最常见的方式是由个人自主购买,即由投保人自行缴纳保险费用并承担相应的保障责任。一些企事业单位会集体为
-
全球热资讯!保险公司拒保怎么办?如何才能避免保险公司拒赔?
保险公司会对申请人的健康状况进行评估,如果被评估为高风险群体或患有某些疾病,就有可能被拒保。一些职业
-
福特CEO:在中国电动汽车市场,无法确保西方车企会赢
福特CEO:在中国电动汽车市场,无法确保西方车企会赢盖世汽车讯据《金融时报》报道,福特汽车首席执行官Jim
-
美股道指跌1.01% 谷歌涨2.7%百度涨4%蔚来跌4.1%
美股道指跌1 01%谷歌涨2 7%百度涨4%蔚来跌4 1%---中国经济网北京5月17日讯美股周二收跌,截至收盘,道指跌3
-
华为云与国联股份等伙伴成立工业数字化创新联合体 天天最资讯
品玩5月17日讯,据IBI国联股份官微,在2023华为云城市峰会现场,由华为云与亿邦智库、国联股份、中航供应链
-
焦点快播:精微视达复合型共聚焦胆道显微内镜亮相CMEF
作为中国(共聚焦)细胞级内窥镜领先企业,精微视达携BIOPSEE®倍晰®、INSIGHT视达TM系列产品以及重磅新品
-
分析师称 iPhone 15 所需面板将在 6 月份开始生产 与正常年份相当_世界今日报
【TechWeb】5月17日消息,据外媒报道,有分析师在当地时间周日的一份报告中称,由于4800万像素后置主摄像头
-
OPPO Reno10 系列官宣!将于 5 月 24 日发布,潜望长焦稳了|世界看点
OPPOReno系列的十代里程碑之作——全新Reno10系列终于官宣,将于5月24日14:30举行新品发布会。每一代Reno新
-
联想杨元庆:PC 最早可能在 2023 年下半年恢复增长 全球即时看
鞭牛士5月17日消息,据上证报报道,联想集团董事长兼CEO杨元庆今日在天津举行的联想集团全球供应商大会上称
-
三星或在开发用于 Windows on Arm 笔电的 Exynos 芯片,整合 AMD 的 GPU|速看
三星过往有推出WindowsonArm的Galaxy系列笔记本电脑,搭载的是高通的芯片,不过这些设备并不算很成功,这也
-
焦点播报:“特斯拉依赖症”
图片来源@视觉中国文|锦缎全球电动化转型的机遇期,自主车企的崛起已经势在必行,汽车产业链迎来全面重塑
-
灵境ai绘画永久会员版(灵境什么)|热门
灵境ai绘画好用吗好用。根据查询相关公开信息显示,灵境ai绘画会员有丰富的色彩库,各种风格的色彩安排,会
-
珠江人寿保险可靠吗?值得参保吗?|焦点快看
珠江人寿保险作为中国大陆领先的保险公司之一,其经营稳健,产品丰富,并得到了多个国际机构的认可,具有较
-
百万众安医疗保险是真的吗?好不好?
百万众安医疗保险是一款非常真实可靠的医疗保险产品,具有全方位、高效快捷的优点。在选择该保险产品时,客
-
当前要闻:保险公司拖车多少公里免费?怎么向保险公司报销拖车费?
不同的保险公司和套餐提供的免费拖车公里数可能会有所不同。 一般而言,标准的免费拖车公里数为50公里左右
-
失地保险多少岁开始领?赔偿金标准是什么?|今亮点
根据国家有关规定,失地农民在年满60周岁后可以开始领取失地保险金。也就是说,在失地保险合同约定的保障期
-
纪翔:让工业机器人更“聪明”|环球速看料
博锲思每一个工业机器人应用方案的背后,都有公司机器人工程技术人员前期的调研设计和后期的方案实现所付出
-
【焦点热闻】财富人生e款年金保险(分红)怎么样?值得购买吗?
财富人生e款年金保险(分红)是一种长期储蓄型保险产品,旨在为投保人提供养老金、保障收益以及遗产规划等全
-
马斯克称特斯拉电动皮卡将在今年开始交付 不打算卸任CEO
【TechWeb】5月17日消息,据外媒报道,特斯拉2019年11月份推出的造型科幻而霸气的电动皮卡Cybertruck,虽然
-
应急管理部:推进人工智能等技术在应对大火巨灾中的运用
证券时报e公司讯,应急管理部火灾防治管理司司长杨旭东在发布会上表示,国家森防指办公室、应急管理部围绕
-
爱奇艺会员数近1.3亿 中国视频会员规模天花板再拉高
5月16日,爱奇艺发布2023年一季度财报。此次财报显示出了开年的三个月里,爱奇艺的整体财务表现和会员规模
-
全球热头条丨中国式ESG|新能源车:电池回收重中之重
一众传统燃油车企比拼全周期减排的同时,作为降碳主力军,ESG对新能源汽车的价值也日益凸显。相比燃油车企
精彩推荐
阅读排行
精彩推送
- 传特斯拉申请扩建上海工厂,将年...
- 世界热文:解决低电量加速缓慢问...
- 天玑9000属于什么档次?天玑9000...
- 中国籍远洋渔船印度洋倾覆39人失...
- 海口金龙大观房价未来怎样?金龙...
- MES系统是什么?mes系统都有哪些...
- 国家支持新能源汽车下乡
- 全球快资讯丨92号汽油下调0.3元/升
- 基石药业获执行董事杨建新增持合...
- 当前快看:一键预约!天水市智慧...
- 云顶新耀宣布完成Etrasimod亚洲3...
- 锐骏 RUH4040M2 开关管,为倍...
- 华为云肖苡:华为云赋能工业数字...
- 天天看热讯:联通世界,致敬时代...
- 理想汽车 CEO:高性能模式会在...
- 至臻网络,创新致远,上海移动联...
- 拜登将缩短亚洲之行应对债务上限...
- 4 月 70 城房价出炉!银川环...
- 华丽家族:二股东临时提案程序存...
- 当前短讯!格力电器开除孟羽童?...
- 兴齐眼药开盘大涨 “近视神药”...
- 60寸液晶屏尺寸是多少厘米?60寸...
- 3Gp是什么格式?3gp格式的视频在...
- 瑞安一职在哪?瑞安一职学校有什...
- 工商银行u盾丢了怎么办?工商银...
- 台湾银行有哪些?台湾银行的信贷...
- 移动平均线是什么意思?移动平均...
- 斗罗大陆魂师对决唐门小舞阵容搭...
- 富时罗素概念股是什么意思?富时...
- 净资产增长率计算公式是什么?净...