RTDMiner:基于数据挖掘的引用计数更新缺陷检测方法.pdf
《RTDMiner:基于数据挖掘的引用计数更新缺陷检测方法.pdf》由会员分享,可在线阅读,更多相关《RTDMiner:基于数据挖掘的引用计数更新缺陷检测方法.pdf(19页珍藏版)》请在咨信网上搜索。
1、RTDMiner:基于数据挖掘的引用计数更新缺陷检测方法*边攀1,2,梁彬1,黄建军1,游伟1,石文昌1,张健31(中国人民大学信息学院,北京100872)2(华为技术有限公司,北京100085)3(计算机科学国家重点实验室(中国科学院软件研究所),北京100190)通信作者:梁彬,E-mail:摘要:在 Linux 内核等大型底层系统中广泛采用引用计数来管理共享资源.引用计数需要与引用资源的对象个数保持一致,否则可能导致不恰当引用计数更新缺陷,使得资源永远无法释放或者被提前释放.为检测不恰当引用计数更新缺陷,现有静态检测方法通常需要知道哪些函数增加引用计数,哪些函数减少引用计数.而手动获取这
2、些关于引用计数的先验知识过于费时且可能有遗漏.基于挖掘的缺陷检测方法虽然可以减少对先验知识的依赖,但难以有效检测像不恰当引用计数更新缺陷这类路径敏感的缺陷.为此,提出一个将数据挖掘技术和静态分析技术深度融合的不恰当引用计数更新缺陷检测方法 RTDMiner.首先,根据引用计数的通用规律,利用数据挖掘技术从大规模代码中自动识别增加或减少引用计数的函数.然后,采用路径敏感的静态分析方法检测增加了引用计数但没有减少引用计数的缺陷路径.为了降低误报,在检测阶段再次利用数据挖掘技术来识别例外模式.在 Linux 内核上的实验结果表明,所提方法能够以将近 90%的准确率自动识别增加或减少引用计数的函数.而
3、且 RTDMiner 检测到的排行靠前的 50 个疑似缺陷中已经有 24 个被内核维护人员确认为真实缺陷.关键词:引用计数;缺陷检测;数据挖掘;静态分析中图法分类号:TP311中文引用格式:边攀,梁彬,黄建军,游伟,石文昌,张健.RTDMiner:基于数据挖掘的引用计数更新缺陷检测方法.软件学报,2023,34(10):47244742.http:/ Reference Count Update Bugs Based on Data MiningBIANPan1,2,LIANGBin1,HUANGJian-Jun1,YOUWei1,SHIWen-Chang1,ZHANGJian31(Schoo
4、lofInformation,RenminUniversityofChina,Beijing100872,China)2(HuaweiTechnologiesCo.Ltd.,Beijing100085,China)3(StateKeyLaboratoryofComputerScience(InstituteofSoftware,ChineseAcademyofSciences),Beijing100190,China)Abstract:Referencecountsarewidelyemployedinlarge-scalelow-levelsystemsincludingLinuxkerne
5、ltomanagesharedresources,andshould be consistent with the number of objects referring to resources.Otherwise,bugs of improper update of reference counts may becaused,and resources can never be released or will be released earlier.To detect improper updates of reference counts,available staticdetecti
6、onmethodshavetoknowthefunctionswhichincreasereferencecountsordecreasethecounts.However,manuallycollectingpriorknowledgeofreferencecountsistootime-consumingandmaybeincomplete.Thoughmining-basedmethodscanreducethedependencyon prior knowledge,it is difficult to effectively detect path-sensitive bugs co
7、ntaining improper updates of reference counts.To this end,*基金项目:国家自然科学基金(U1836209,62132020,61802413,62002361)收稿时间:2021-06-11;修改时间:2021-12-18;采用时间:2022-03-14;jos 在线出版时间:2023-04-04CNKI 网络首发时间:2023-04-06软件学报ISSN1000-9825,CODENRUXUEWE-mail:Journal of Software,2023,34(10):47244742doi:10.13328/ki.jos.0066
8、76http:/中国科学院软件研究所版权所有.Tel:+86-10-62562563this study proposes a method RTDMiner that deeply integrates data mining into static analysis to detect improper updates of referencecounts.First,accordingtothegeneralprinciplesofreferencecounts,thedataminingtechniqueisleveragedtoidentifyfunctionsthatraiseor
9、 reduce reference counts.Then,a path-sensitive static analysis method is employed to detect defective paths that increase referencecounts instead of decreasing the counts.To reduce false positives,the study adopts the data mining technique to identify exceptionalpatterns during detection.The experim
10、ent results on the Linux kernel demonstrate that the proposed method can automatically identifyfunctions increasing or decreasing reference counts with the precision of nearly 90%.Moreover,24 out of the top 50 suspicious bugsdetectedbyRTDMinerhavebeenconfirmedtoberealbugsbykernelmaintainers.Key word
11、s:referencecount;bugdetection;datamining;staticanalysis引用计数法(referencecount)是一种自动管理共享资源的技术1,在操作系统、数据库、浏览器、虚拟机等各类软件系统中有着广泛的应用25.在引用计数法中,会设置一个引用计数来跟踪资源的引用数.当需要使用资源时,如果资源还不存在,就申请内存创建该资源,并将引用计数初始化为 1;否则如果资源已经存在,就直接引用该资源,并将资源的引用计数加 1.当释放资源时,引用计数减 1.当资源的引用计数变为 0 时,表明该对象将不再使用,相应的内存将被释放或者重新分配给其他资源使用.当资源的引用计
12、数与实际引用它的对象个数不一致时,将导致不恰当引用计数更新缺陷(CWE-911:Improperupdateofreferencecount.https:/cwe.mitre.org/data/definitions/911.html).在本文中,为方便叙述,我们将不恰当引用计数更新缺陷简称为引用计数缺陷.如果引用计数大于实际引用数时,资源将永远无法释放,造成资源耗尽,导致拒绝服务漏洞,如 CVE-2008-2136、CVE-2010-4593;而如果引用计数小于实际引用数时,资源可能被提前释放,导致释放后使用漏洞,如 CVE-2009-3624、CVE-2012-4787.为避免缺陷,增加引
13、用计数之后通常会相应地减少引用计数.为了保证原子性,对引用计数的更新通常封装在函数中.我们将初始化引用计数或增加引用计数的函数称为引用获取(referencetaking)函数,将减少资源引用计数的函数称为引用释放(referencedropping)函数.用户代码通常通过调用引用获取函数和引用释放函数来管理引用计数,而非直接修改引用计数的值6.造成引用计数缺陷的原因通常是没有在有需要的地方调用引用获取函数或引用释放函数7.引用计数缺陷导致的后果可能并不会在当时就表现出来,有可能在很长时间之后才会影响到其他组件甚至其他线程,如资源耗尽或者系统崩溃.因此,纯动态分析技术(如模糊测试8)难以有效检
14、测此类缺陷.更自然的方法是利用静态分析方法来检测不恰当的引用计数更新缺陷.例如,Mao 等人提出一个名为 RID 的静态分析方法,通过检测函数中不同路径上对引用计数更新的不一致来发现不恰当引用计数更新缺陷6.然而,传统静态分析方法面临的最大挑战是需要大量的先验知识9.为检测引用计数缺陷,静态分析方法通常需要知道哪些是引用获取函数、哪些是引用释放函数.而引用获取/释放函数通常是特定于应用的,不同的目标系统的引用获取/释放函数也往往不相同.在大型系统中,可能存在成百上千的引用获取/释放函数,难以通过手动的方式来收集并配置到检查工具中.此外,在某些例外场景下,并不需要获取引用或者释放引用.例如,在
15、Linux 内核中,当 inode 节点通过 d_instantiate()附加到目录项 dentry 后,不应该再调用引用释放函数 iput()来减少引用计数.在实践中,手动列举例外场景更是不现实.为了缓解传统静态分析方法对先验知识的依赖问题,人们提出代码挖掘方法10,利用数据挖掘技术从大规模代码中自动提取检查规则.其基本原理是从大规模代码中提取数量占优的编码模式.代码挖掘方法已经取得了较为显著的成果,能够从实际大型系统中自动提取隐式编码规则并据此检测到数十个真实缺陷.考虑到路径爆炸问题,大部分代码挖掘方法都是路径不敏感的1012,难以有效检测诸如引用计数缺陷这样与路径密切相关的缺陷.本文提
16、出一种新型引用计数缺陷检测方法 RTDMiner,有机结合数据挖掘和静态分析技术来解决各自面临的挑战.具体而言,首先根据引用计数的一般使用规则,利用数据挖掘技术自动识别引用获取函数和引用释放函数;其次,分析引用获取函数和引用释放函数未配对出现的路径,进一步利用数据挖掘技术,提取例外模式;最后,检测调用引用获取函数但既没有调用引用释放函数又不包含例外模式的路径来发现潜在引用计数缺陷.此外,我们还根据是真实缺陷的可能性对疑似缺陷进行排序,以尽可能凸显真实缺陷.为了评估本方法的有效性,我们实现了一个原型系统,并将其应用于 Linux 内核(v5.11)的缺陷检测中.实验结果显示,在只知道一些基本增减
17、操作的情况下,RTDMiner 从 Linux 内核中自动识别出 1250 对候选引用获取函边攀等:RTDMiner:基于数据挖掘的引用计数更新缺陷检测方法4725数和引用释放函数,经人工确认,其中 1118 对都是真实的引用获取函数和引用释放函数,准确率高达 89.4%.利用这些引用获取函数和引用释放函数,RTDMiner 从 Linux 内核中检测到 3140 个可能存在引用计数泄漏缺陷的函数,即调用引用获取函数之后未调用相应的引用释放函数.通过人工审计,我们在排名前 50 个函数中发现 35 条疑似缺陷.我们将这些疑似缺陷提交给 Linux 内核社区,其中 24 条已经被 Linux 内
18、核开发人员确认为真实缺陷,其他 11 条疑似缺陷正在确认中.目前为止,我们提交的这些疑似缺陷还没有被证实是误报的.实验结果表明,RTDMiner 可以在无需手动指定引用获取函数和引用释放函数的情况下检查出相当数量的不恰当的引用计数更新缺陷.本文主要贡献如下.(1)根据引用计数的一般使用规律,提出一种利用数据挖掘技术来自动识别引用获取函数和引用释放函数的方法.(2)提出一种利用数据挖掘技术来自动提取例外模式的方法.在检测引用计数泄露缺陷时可以根据例外模式减少误报和凸显最可能的缺陷.(3)实现了一个不恰当引用计数更新缺陷检测原型系统.利用该原型系统从大型软件系统中检测到数十个真实缺陷.本文首先在第
19、 1 节介绍相关工作.然后,在第 2 节以 Linux 内核中的一个实际缺陷为例来说明 RTDMiner 的研究动机和基本思想.第 3 节介绍自动识别引用获取/释放函数的方法.而第 4 节则说明如何根据挖掘到的引用获取/释放函数来检测引用计数更新缺陷.第 5 节进行实验评估本方法的有效性.第 6 节探讨未来可能的研究方向.第 7 节对本文进行总结.1 相关工作 1.1 引用计数缺陷检测与本工作相关性比较大的工作是 Mao 等人提出的方法 RID6,通过检测路径之间的不一致性来发现潜在引用计数相关的缺陷.RID 将不一致的路径配对(inconsistentpathpair)作为潜在缺陷.对于同一
20、个函数中无法从外部通过检查参数或返回值加以区分的路径,如果它们对引用计数的更新不一致,例如其中一条路径减少了引用计数,但另外一条路径没有减少引用计数,那么其中一条路径可能存在缺陷.利用该方法,RID 从 Linux 内核等系统中检测到数十个不恰当引用计数更新缺陷.Lal 等人提出一个利用静态分析技术检测闭包程序中的引用计数缺陷的方法13.在程序入口(如函数 main(),所有的引用计数都被初始化为 0.而在程序退出时,如果引用计数不为 0,说明程序存在引用计数泄漏缺陷.MalCom 提出的 CPyChecker14和 Li 等人提出的 Pungi15主要通过检查函数中引用计数的增加与逃逸个数不
21、一致来发现潜在缺陷.引用计数可以通过返回值、特定 API 等逃逸到函数之外.上述引用计数缺陷检测方法都依赖大量的先验知识,需要用户指定增加/减少引用计数的函数6,14,15,或者表示引用计数的结构成员13.而在实际系统中,特别是那些大型软件系统,通过手动方式从成千上万的函数或结构成员中辨别这些先验知识费时费力且容易遗漏.与上述方法相比,RTDMiner 可以根据更容易获取的递增/递减操作来自动识别引用计数更新函数,并在此基础上检测可能的引用计数泄漏缺陷.当然,RTDMiner 识别出的引用计数更新函数还可以作为上述方法的输入来检测其他形式的引用计数缺陷.1.2 敏感函数识别人们也提出来一些方法
22、来识别具有特定语义的函数.其中一些方法利用安全编程实践统计特征来启发式推导函数的语义.例如,为避免释放后使用缺陷,指针传递给内存释放函数之后通常不会再引用.基于这一经验性观察,Engler 等人统计在调用函数之后,其参数的使用频率,如果某个参数极少再被使用,则该函数可能是内存释放函数9.Kremenek 等人进一步提出了利用因子图来整合更多信息的方法,能够更准确地识别资源分配和释放函数16.还有一些方法根据特定领域的专业知识来识别相关的敏感函数.Ganapathy 等人使用概念分析(concept4726软件学报2023 年第 34 卷第 10 期analysis)根据给定领域的知识(如一个或
23、多个关键数据结构)来推导安全敏感操作的指纹17.Tan等人提出了一个名为 AutoISES的方法来推断应该受某些安全检查函数保护的操作18.启发式方法在查找某些类型的安全敏感函数方面很有效,但同时也存在可伸缩性问题,因为不同类型的安全敏感函数通常具有不同的关键特征,需要具有一定的洞察力.启发式方法通常根据一些容易获取的线索来推断想要的敏感函数.RTDMiner 也采用了类似的思路,从相对比较容易获取(甚至通用)的递增/递减操作出发,综合采用数据挖掘和程序分析技术来识别引用计数获取/释放函数.Rasthofer等人提出名为 SuSi 的方法,利用分类技术来识别 Android框架中的污点源(ta
24、intsource)和污点汇(taintsink)19.SuSi使用数百个已标记的 API来训练 SVM分类器,然后使用 SVM 分类器来预测其他 API的标签.SuSi已成功识别上千个 Android 框架中的污点源和污点汇,用于 Android应用程序上污点分析20.但 SuSi 需要一定数量的训练样本才能训练出有效的分类器,而在实际应用中往往难以获取足够多的样本.为此,Bian 等人提出一个两阶段方法 SinkFinder21,首先利用词嵌入技术的类比分析能力,可以仅根据一对种子函数,找到与之具有类似语义的函数对,获取足够多的样本.然后,利用这些样本训练一个分类器.SinkFinder
25、可以在已知样本数量有限的情况下也可以进行工作.SuSi 和 SinkFinder 是通用方法,聚焦于识别与已知训练样本在行为模式上相似的函数.而在引用计数缺陷检测中,需要准确知道引用获取/释放函数.而 SuSi 和 SinkFinder 难以精确到这些信息.例如,对于 SinkFinder 而言,引用获取/释放函数对(如 ext4_fc_start_update()/ext4_fc_stop_update()在使用模式上可能与加锁/解锁函数(如 spin_lock()/spin_unlock()类似.虽然难以直接识别引用计数更新函数,SinkFinder 可以与 RTDMiner相结合,Sin
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- RTDMiner 基于 数据 挖掘 引用 计数 更新 缺陷 检测 方法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。