全球关注:让“无声的漏洞”无可遁形:详解2023 数据库顶会SIGMOD最佳论文
【编者按】2023数据库顶会SIGMOD在美国西雅图颁出最佳论文。阿里云与浙江大学合作的《Detecting Logic Bugs of Join Optimizations in DBMS》获得最佳论文,成为自1975年该会议至今49年以来,中国大陆研究团队首次斩获该奖项。
(相关资料图)
这项工作聚焦数据库逻辑测试,始于阿里云PolarDB云原生数据库的内核测试,通过开发创新的自动化数据库逻辑测试方案TQS,检出不易察觉的逻辑漏洞予以修复。实验发现,TQS运行仅24小时就检测出4大商用数据库管理系统的逻辑漏洞115个,予以修复后,大幅提升数据库稳定性。
该论文一作唐秀系浙江大学博士,这一工作是她在阿里云数据库进行研究型实习时的成果;阿里云数据库负责人李飞飞也是作者之一,此前他曾以一作身份凭借《Wander Join: Online Aggregation via Random Walks》拿下2016年SIGMOD最佳论文。本次论文获奖,完成了中国大陆研究团队在数据库顶会的历史性突破,也成为了中国校企合作攻克科研难题的典范之一。
我们特别邀请到唐秀博士,为我们深入浅出地解读这篇论文的关键成果。
作者 | 唐秀,浙江大学博士,2022 年阿里巴巴优秀研究型实习生
背景与动机
我国数据库正处于高速发展期,并且随着应用复杂程度的增加,企业和用户对于更强大、更安全的数据库的需求也越来越迫切。因此,如何检查数据库漏洞和错误,成为保障数据库安全、提升数据库稳定性的关键之一。
在数据库查询执行期间,主要有两类错误(bug):一种常见的错误是数据库突然崩溃停止,这种错误对于开发人员来说相对容易检测,因为数据库连接会突然中断。然而,还存在一类隐藏的错误,即逻辑漏洞。在这种情况下,数据库正常运行并返回结果,但实际上并非正确的结果。
图说:逻辑漏洞举例
以上图中的两个逻辑漏洞为例,图a展现了MySQL的一个哈希连接错误,这种错误发生在错误地将零和负零视为不同值的情况下,导致最终返回一组空集合;b图涉及数据类型转换和数据精度损失导致的错误半连接:在MySQL中,当比较两个值是否相等时,数据类型转换和精度损失可能导致意外的结果,从而影响查询结果集的构建。
逻辑漏洞很难检测,但其导致的后果确很严重,重则会导致“上万航班延误瘫痪”级别的大规模宕机,因此也被视为“无声的漏洞”。本论文便主要聚焦于此。
针对逻辑漏洞,目前已经有一些检测方法,例如部分查询语义(PQS),但这些方法通常只支持针对单表选择查询的检测,在涉及多表查询以及不同的连接算法和连接结构的情况下,仍存在大量的研究空白。
而最常用的差分测试,通过在不同数据库中执行相同操作,以验证其一致性,这种测试仍存在问题:假如两个数据库返回相同的结果,也有可能是基于同样错误的逻辑生成了一样的结果, 也即如何验证查询结果正确性的关键问题。
同时,测试数据库现在面临的搜索空间是非常庞大的, 如何引导测试以尽可能消耗最小的资源穷尽全部测试,也是一个需要解决的问题。
研究思路与核心内容
围绕这两个关键问题,我们引入了一个名为TQS(转换查询合成)的全新解决方案,以解决MySQL数据库中可能出现的逻辑错误。
图说:TQS架构图
TQS包括DSG和KQE两部分,分别为数据驱动的模式和查询生成,与知识引导的查询空间探索。
为解决真值生成问题,我们采用了以下方法:首先,根据给定的宽表,使用函数依赖(FD)将该表拆分为多个表。
图说:DSG是如何拆分宽表的
同时,为了进行边缘测试,我们还插入了一些噪声数据作为边缘情况的样本(图中彩色数据),并基于数据库的模式图模型,随机游走生成一系列查询。
图说:DSG构建针对表连接的Bitmap 索引
在此基础上,构建RowID映射表,用于记录在表拆分过程中,宽表中的行和拆分后表的行的对应关系。根据表连接是表拆分的逆向过程的直觉,构建基于构建RowID映射的Bitmap索引,以便从宽表中检索到连接查询的理论真值。 这些真值生成后,便是检测潜在逻辑错误的参照样本。
然而,对于给定的数据库模式,可生成的连接查询的数量会随着表格和列的数量呈指数级增长,显然无法使用枚举法一一验证。那么,要如何更高效地探索查询未知空间呢?我们提出了TQS的第二部分设计——KQE。
图说:KQE原理图
KQE首先将模式图进一步拓展为一个规划迭代图,来表示整个查询生成空间。同时,在大量的历史查询图中,KQE构建了一个基于嵌入的图索引,以确保新生成的查询图尽可能地远离其在历史查询中的近邻,探索更多的未知空间。
总体来看,KQE可基于结构相似性为生成的查询图评分,同时也通过自适应随机游走多样化查询生成, 从而极大降低了对于重复查询的概率,节省了计算资源开支。
实验结果分析
我们的研究在MySQL、MariaDB、TiDB 和 PolarDB 等4大常用DBMS上进行了实验。
运行了 24 小时后,TQS 成功找到了 115 个漏洞:MySQL 中 31 个、MariaDB 中 30 个、TiDB 中 31 个、PolarDB 中 23 个。通过最小化测试样例,我们进一步将它们分为20种类型。
图说:实验检出漏洞分类详表
我们已经将检测到的漏洞提交给相应数据库社区,并得到了他们积极的反馈。这些漏洞的危机程度被数据库社区判定为首要危急或严重级别,一些漏洞已经修复在了其数据库最新版本中。
具体来说,MySQL 8.0.28的错误主要集中在Semi-join和Sub-query的执行过程中,其中,几个错误被评定为首要危急,即最紧急的错误,这些错误已经在MySQL 8.0.30版本中得到修复,并提供了相应的修复说明。而对于已使用SQLancer进行全面测试的TiDB,TQS也测出了一些首要危急错误,TiDB对其进行了修复。另外,针对PolarDB,我们则直接提交错误报告,相关错误已经被修复。
图说:TQS与原有方法的有效性对比
总的来说,相比于其它方法,TQS在多项指标上取得了更优的效果,较原有方法实现高达100倍的性能提升,各组件的有效性也通过控制变量实验得到了检验。
6月21日晚上8点整,本文一作唐秀将直播解读论文,欢迎广大读者预约收看。
返回搜狐,查看更多
责任编辑:
关键词:
您可能也感兴趣:
今日热点
为您推荐
环球快看点丨全国夏播粮食超七成 “先进农机+配套技术”助农增产增收
世界热资讯!6月21日锦纶DTY为17860.00
系统停息挂账怎么操作?停息挂账卡还能用吗?
排行
最近更新
- 全球关注:让“无声的漏洞”无可遁形:详解2023 数据库顶会S...
- 兴义市向阳路小学民航校区开展教职工消防安全知识培训活动
- 全球今日报丨腊肠树花开 挂满“黄金雨”
- 储能电扇出口火爆 中国电风扇在欧洲火了
- 卓胜微实控人之一唐壮离婚女方分走34亿 股价跌6.93%|天天新要闻
- 动态:男演员离世,年仅34岁!网友痛惜:这病越来越年轻化
- 世界今热点:端午出行如何避堵?哪些时段车流较高?请收好这...
- 2023年印刷行业概念利好什么股票?(6月21日)-焦点快报
- 科创板涉及医疗上市企业名单(6/21)
- 新中港06月21日涨停分析
- 金恩圣有孩子吗(金恩圣的姐姐)
- 2023年美容概念上市公司有哪些?(6月21日)
- iQOO TWS 1 主动降噪耳机参数曝光,将与 iQOO11S 手机一同发布_热资讯
- 当前快播:1-溴丁烷商品报价动态(2023-06-22)
- 极目锐评|川大污蔑大叔偷拍的女生被留校留党察看,所有网民都...
- 公益微视频|珍惜粮食,你我有责
- 甲基丙烯酸缩水甘油酯商品报价动态(2023-06-22) 全球微速讯
- 供销社上市龙头企业有哪些?(2023/6/21)-当前速讯
- 科创板涉及锂电池的个股一览(6/21)
- 交易员3月以来首次全面定价欧洲央行利率峰值为4%_环球热门
- 湖南工大科技学院党委班子赴杨得志故居开展体验式学习 实时
- 速递!AMD(AMD.US)将投资1.35亿美元扩大爱尔兰业务
- 中发展控股(00475.HK)年度营收同比增28.37%至2.48亿港元 ...
- 新百利融资(08439)发布年度业绩,股东应占亏损682.1万港元,...
- 后备厢空间有大幅提升 全新奔驰E级旅行版官图发布
- 淘宝货源怎么找厂家(淘宝货源怎么找)|观天下
- 华科资本(01140.HK)年度纯利跌33.85%至1.46亿港元
- 借船过河心理测试答案mfsle_借船过河-全球最资讯
- 李想,在微博“造车” 天天快播
- 世界观速讯丨报告:北上深广为中国房地产开发投资吸引力四强城市