RTDMiner：基于数据挖掘的引用计数更新缺陷检测方法.pdf

RTDMiner:基于数据挖掘的引用计数更新缺陷检测方法*边攀1,2,梁彬1,黄建军1,游伟1,石文昌1,张健31(中国人民大学信息学院,北京100872)2(华为技术有限公司,北京100085)3(计算机科学国家重点实验室(中国科学院软件研究所),北京100190)通信作者:梁彬,E-mail:摘要:在 Linux 内核等大型底层系统中广泛采用引用计数来管理共享资源.引用计数需要与引用资源的对象个数保持一致,否则可能导致不恰当引用计数更新缺陷,使得资源永远无法释放或者被提前释放.为检测不恰当引用计数更新缺陷,现有静态检测方法通常需要知道哪些函数增加引用计数,哪些函数减少引用计数.而手动获取这些关于引用计数的先验知识过于费时且可能有遗漏.基于挖掘的缺陷检测方法虽然可以减少对先验知识的依赖,但难以有效检测像不恰当引用计数更新缺陷这类路径敏感的缺陷.为此,提出一个将数据挖掘技术和静态分析技术深度融合的不恰当引用计数更新缺陷检测方法 RTDMiner.首先,根据引用计数的通用规律,利用数据挖掘技术从大规模代码中自动识别增加或减少引用计数的函数.然后,采用路径敏感的静态分析方法检测增加了引用计数但没有减少引用计数的缺陷路径.为了降低误报,在检测阶段再次利用数据挖掘技术来识别例外模式.在 Linux 内核上的实验结果表明,所提方法能够以将近 90%的准确率自动识别增加或减少引用计数的函数.而且 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(SchoolofInformation,RenminUniversityofChina,Beijing100872,China)2(HuaweiTechnologiesCo.Ltd.,Beijing100085,China)3(StateKeyLaboratoryofComputerScience(InstituteofSoftware,ChineseAcademyofSciences),Beijing100190,China)Abstract:Referencecountsarewidelyemployedinlarge-scalelow-levelsystemsincludingLinuxkerneltomanagesharedresources,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 staticdetectionmethodshavetoknowthefunctionswhichincreasereferencecountsordecreasethecounts.However,manuallycollectingpriorknowledgeofreferencecountsistootime-consumingandmaybeincomplete.Thoughmining-basedmethodscanreducethedependencyon prior knowledge,it is difficult to effectively detect path-sensitive bugs containing 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.006676http:/中国科学院软件研究所版权所有.Tel:[phone]this study proposes a method RTDMiner that deeply integrates data mining into static analysis to detect improper updates of referencecounts.First,accordingtothegeneralprinciplesofreferencecounts,thedataminingtechniqueisleveragedtoidentifyfunctionsthatraiseor 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 experiment 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 words:referencecount;bugdetection;datamining;staticanalysis引用计数法(referencecount)是一种自动管理共享资源的技术1,在操作系统、数据库、浏览器、虚拟机等各类软件系统中有着广泛的应用25.在引用计数法中,会设置一个引用计数来跟踪资源的引用数.当需要使用资源时,如果资源还不存在,就申请内存创建该资源,并将引用计数初始化为 1;否则如果资源已经存在,就直接引用该资源,并将资源的引用计数加 1.当释放资源时,引用计数减 1.当资源的引用计数变为 0 时,表明该对象将不再使用,相应的内存将被释放或者重新分配给其他资源使用.当资源的引用计数与实际引用它的对象个数不一致时,将导致不恰当引用计数更新缺陷(CWE-911:Improperupdateofreferencecount.https:/cwe.mitre.org/data/definitions/911.html).在本文中,为方便叙述,我们将不恰当引用计数更新缺陷简称为引用计数缺陷.如果引用计数大于实际引用数时,资源将永远无法释放,造成资源耗尽,导致拒绝服务漏洞,如 CVE-2008-2136、CVE-2010-4593;而如果引用计数小于实际引用数时,资源可能被提前释放,导致释放后使用漏洞,如 CVE-2009-3624、CVE-2012-4787.为避免缺陷,增加引用计数之后通常会相应地减少引用计数.为了保证原子性,对引用计数的更新通常封装在函数中.我们将初始化引用计数或增加引用计数的函数称为引用获取(referencetaking)函数,将减少资源引用计数的函数称为引用释放(referencedropping)函数.用户代码通常通过调用引用获取函数和引用释放函数来管理引用计数,而非直接修改引用计数的值6.造成引用计数缺陷的原因通常是没有在有需要的地方调用引用获取函数或引用释放函数7.引用计数缺陷导致的后果可能并不会在当时就表现出来,有可能在很长时间之后才会影响到其他组件甚至其他线程,如资源耗尽或者系统崩溃.因此,纯动态分析技术(如模糊测试8)难以有效检测此类缺陷.更自然的方法是利用静态分析方法来检测不恰当的引用计数更新缺陷.例如,Mao 等人提出一个名为 RID 的静态分析方法,通过检测函数中不同路径上对引用计数更新的不一致来发现不恰当引用计数更新缺陷6.然而,传统静态分析方法面临的最大挑战是需要大量的先验知识9.为检测引用计数缺陷,静态分析方法通常需要知道哪些是引用获取函数、哪些是引用释放函数.而引用获取/释放函数通常是特定于应用的,不同的目标系统的引用获取/释放函数也往往不相同.在大型系统中,可能存在成百上千的引用获取/释放函数,难以通过手动的方式来收集并配置到检查工具中.此外,在某些例外场景下,并不需要获取引用或者释放引用.例如,在 Linux 内核中,当 inode 节点通过 d_instantiate()附加到目录项 dentry 后,不应该再调用引用释放函数 iput()来减少引用计数.在实践中,手动列举例外场景更是不现实.为了缓解传统静态分析方法对先验知识的依赖问题,人们提出代码挖掘方法10,利用数据挖掘技术从大规模代码中自动提取检查规则.其基本原理是从大规模代码中提取数量占优的编码模式.代码挖掘方法已经取得了较为显著的成果,能够从实际大型系统中自动提取隐式编码规则并据此检测到数十个真实缺陷.考虑到路径爆炸问题,大部分代码挖掘方法都是路径不敏感的1012,难以有效检测诸如引用计数缺陷这样与路径密切相关的缺陷.本文提出一种新型引用计数缺陷检测方法 RTDMiner,有机结合数据挖掘和静态分析技术来解决各自面临的挑战.具体而言,首先根据引用计数的一般使用规则,利用数据挖掘技术自动识别引用获取函数和引用释放函数;其次,分析引用获取函数和引用释放函数未配对出现的路径,进一步利用数据挖掘技术,提取例外模式;最后,检测调用引用获取函数但既没有调用引用释放函数又不包含例外模式的路径来发现潜在引用计数缺陷.此外,我们还根据是真实缺陷的可能性对疑似缺陷进行排序,以尽可能凸显真实缺陷.为了评估本方法的有效性,我们实现了一个原型系统,并将其应用于 Linux 内核(v5.11)的缺陷检测中.实验结果显示,在只知道一些基本增减操作的情况下,RTDMiner 从 Linux 内核中自动识别出 1250 对候选引用获取函边攀等:RTDMiner:基于数据挖掘的引用计数更新缺陷检测方法4725数和引用释放函数,经人工确认,其中 1118 对都是真实的引用获取函数和引用释放函数,准确率高达 89.4%.利用这些引用获取函数和引用释放函数,RTDMiner 从 Linux 内核中检测到 3140 个可能存在引用计数泄漏缺陷的函数,即调用引用获取函数之后未调用相应的引用释放函数.通过人工审计,我们在排名前 50 个函数中发现 35 条疑似缺陷.我们将这些疑似缺陷提交给 Linux 内核社区,其中 24 条已经被 Linux 内核开发人员确认为真实缺陷,其他 11 条疑似缺陷正在确认中.目前为止,我们提交的这些疑似缺陷还没有被证实是误报的.实验结果表明,RTDMiner 可以在无需手动指定引用获取函数和引用释放函数的情况下检查出相当数量的不恰当的引用计数更新缺陷.本文主要贡献如下.(1)根据引用计数的一般使用规律,提出一种利用数据挖掘技术来自动识别引用获取函数和引用释放函数的方法.(2)提出一种利用数据挖掘技术来自动提取例外模式的方法.在检测引用计数泄露缺陷时可以根据例外模式减少误报和凸显最可能的缺陷.(3)实现了一个不恰当引用计数更新缺陷检测原型系统.利用该原型系统从大型软件系统中检测到数十个真实缺陷.本文首先在第 1 节介绍相关工作.然后,在第 2 节以 Linux 内核中的一个实际缺陷为例来说明 RTDMiner 的研究动机和基本思想.第 3 节介绍自动识别引用获取/释放函数的方法.而第 4 节则说明如何根据挖掘到的引用获取/释放函数来检测引用计数更新缺陷.第 5 节进行实验评估本方法的有效性.第 6 节探讨未来可能的研究方向.第 7 节对本文进行总结.1 相关工作 1.1 引用计数缺陷检测与本工作相关性比较大的工作是 Mao 等人提出的方法 RID6,通过检测路径之间的不一致性来发现潜在引用计数相关的缺陷.RID 将不一致的路径配对(inconsistentpathpair)作为潜在缺陷.对于同一个函数中无法从外部通过检查参数或返回值加以区分的路径,如果它们对引用计数的更新不一致,例如其中一条路径减少了引用计数,但另外一条路径没有减少引用计数,那么其中一条路径可能存在缺陷.利用该方法,RID 从 Linux 内核等系统中检测到数十个不恰当引用计数更新缺陷.Lal 等人提出一个利用静态分析技术检测闭包程序中的引用计数缺陷的方法13.在程序入口(如函数 main(),所有的引用计数都被初始化为 0.而在程序退出时,如果引用计数不为 0,说明程序存在引用计数泄漏缺陷.MalCom 提出的 CPyChecker14和 Li 等人提出的 Pungi15主要通过检查函数中引用计数的增加与逃逸个数不一致来发现潜在缺陷.引用计数可以通过返回值、特定 API 等逃逸到函数之外.上述引用计数缺陷检测方法都依赖大量的先验知识,需要用户指定增加/减少引用计数的函数6,14,15,或者表示引用计数的结构成员13.而在实际系统中,特别是那些大型软件系统,通过手动方式从成千上万的函数或结构成员中辨别这些先验知识费时费力且容易遗漏.与上述方法相比,RTDMiner 可以根据更容易获取的递增/递减操作来自动识别引用计数更新函数,并在此基础上检测可能的引用计数泄漏缺陷.当然,RTDMiner 识别出的引用计数更新函数还可以作为上述方法的输入来检测其他形式的引用计数缺陷.1.2 敏感函数识别人们也提出来一些方法来识别具有特定语义的函数.其中一些方法利用安全编程实践统计特征来启发式推导函数的语义.例如,为避免释放后使用缺陷,指针传递给内存释放函数之后通常不会再引用.基于这一经验性观察,Engler 等人统计在调用函数之后,其参数的使用频率,如果某个参数极少再被使用,则该函数可能是内存释放函数9.Kremenek 等人进一步提出了利用因子图来整合更多信息的方法,能够更准确地识别资源分配和释放函数16.还有一些方法根据特定领域的专业知识来识别相关的敏感函数.Ganapathy 等人使用概念分析(concept4726软件学报2023 年第 34 卷第 10 期analysis)根据给定领域的知识(如一个或多个关键数据结构)来推导安全敏感操作的指纹17.Tan等人提出了一个名为 AutoISES的方法来推断应该受某些安全检查函数保护的操作18.启发式方法在查找某些类型的安全敏感函数方面很有效,但同时也存在可伸缩性问题,因为不同类型的安全敏感函数通常具有不同的关键特征,需要具有一定的洞察力.启发式方法通常根据一些容易获取的线索来推断想要的敏感函数.RTDMiner 也采用了类似的思路,从相对比较容易获取(甚至通用)的递增/递减操作出发,综合采用数据挖掘和程序分析技术来识别引用计数获取/释放函数.Rasthofer等人提出名为 SuSi 的方法,利用分类技术来识别 Android框架中的污点源(taintsource)和污点汇(taintsink)19.SuSi使用数百个已标记的 API来训练 SVM分类器,然后使用 SVM 分类器来预测其他 API的标签.SuSi已成功识别上千个 Android 框架中的污点源和污点汇,用于 Android应用程序上污点分析20.但 SuSi 需要一定数量的训练样本才能训练出有效的分类器,而在实际应用中往往难以获取足够多的样本.为此,Bian 等人提出一个两阶段方法 SinkFinder21,首先利用词嵌入技术的类比分析能力,可以仅根据一对种子函数,找到与之具有类似语义的函数对,获取足够多的样本.然后,利用这些样本训练一个分类器.SinkFinder 可以在已知样本数量有限的情况下也可以进行工作.SuSi 和 SinkFinder 是通用方法,聚焦于识别与已知训练样本在行为模式上相似的函数.而在引用计数缺陷检测中,需要准确知道引用获取/释放函数.而 SuSi 和 SinkFinder 难以精确到这些信息.例如,对于 SinkFinder 而言,引用获取/释放函数对(如 ext4_fc_start_update()/ext4_fc_stop_update()在使用模式上可能与加锁/解锁函数(如 spin_lock()/spin_unlock()类似.虽然难以直接识别引用计数更新函数,SinkFinder 可以与 RTDMiner相结合,SinkFinder 可以根据通用递增/递减操作(即“+”和“”)来发现更多的递增/递减函数,为 RTDMiner 提供更多线索来发现尽可能多的引用计数相关的函数.1.3 编码模式挖掘传统静态分析技术根据已知编码规则来检查缺陷.而某些特定于应用的隐式编码规则往往难以获取.为了缓解传统静态分析技术对先验知识的依赖,人们提出利用数据挖掘技术从大规模代码中自动提取频繁出现的编码模式作为隐式编码规则,并据此检测可能的缺陷912,16,18,2227.RTDMiner 也利用了数据挖掘的思想来识别频繁函数对,以限定引用计数更新函数的搜索范围.引用计数获取/释放函数对是频繁函数对的子集.我们自然想知道 RTDMiner 检测到的缺陷是否也是基于挖掘的检测方法(如文献 27)的子集?考虑到性能和准确性,绝大部分纯挖掘的缺陷检测方法都是路径不敏感的.实际上,频繁出现在同样上下文的函数在某些路径下可能并不会同时出现.例如,kmalloc()和 kfree()是频繁函数对,经常出现在同样的上下文.但在 kmalloc()分配内存失败,或者将内存加入到全局链表的路径上,往往并不会调用 kfree().因此,如果规则挖掘阶段采用路径敏感的算法可能导致无法有效获取编码规则,而如果在检测阶段进行路径敏感的检测又可能导致大量的误报.为了解决这一问题,研究人员通常针对特定类型的缺陷(如返回值未验证)提出有针对性的挖掘和检测方法.为检测引用计数缺陷,我们设计了 RTDMiner.首先,根据引用计数更新函数的一般规律,利用数据挖掘算法识别引用获取/释放函数;然后,利用路径敏感的程序分析方法,检测在需要释放引用计数的路径上未正确调用引用释放函数的路径,从而发现纯挖掘的检测方法难以发现的问题.实际上,之前的一些工作也探索过将挖掘和传统分析工具相结合的方法.Pradel 等人从动态执行路径中挖掘JavaAPI 的使用规范,然后利用静态分析技术来检查规范的违反28.而 Sun 等人则先利用挖掘技术从代码中提取前置规则、后置规则及调用序列规则,然后将这些规则传递给 Klocwork,利用静态分析工具的强大检测能力来检测潜在缺陷29.与上述方法只在规则提取阶段使用数据挖掘技术相比,RTDMiner 在检测阶段也需要用到挖掘技术来排除例外场景.2 问题分析及解决思路我们以 RTDMiner 从 Linux 内核中发现的一个真实缺陷来说明本文的研究动机.如图 1 所示,Linux-v5.11 中函数 ext4_setattr()中存在引用计数泄漏缺陷.具体而言,在其中一条路径上,索引节点 inode 的引用计数递增之后却没有递减(第 13 行).对象 inode 的引用计数 i_fc_updates 用来记录正在执行的快速提交(fastcommit)30的个数,边攀等:RTDMiner:基于数据挖掘的引用计数更新缺陷检测方法4727在更新 inode 的内容和状态之前需要增加引用计数 i_fc_updates 的值,而完成更新之后则应当减少引用计数.如图 2所示,函数 ext4_fc_start_update()会增加该引用计数,而函数 ext4_fc_stop_update()则减少引用计数,并在引用计数的值降为 0 时唤醒其他被阻塞的快速提交.造成图 1 所示缺陷的根本原因是函数 ext4_setattr()在执行更新操作之前调用了函数 ext4_fc_start_update()来增加引用计数,但当函数 ext4_mark_inode_dirty()将 inode 标记为脏时出现错误却没有调用函数 ext4_fc_stop_update()来结束更新操作.此时将导致 inode 的引用计数 i_fc_updates 泄漏,造成 inode 上的其他操作可能一直被阻塞,永远得不到执行.1234567891011121314151617181920212223/linux-v5.11/fs/ext4/inode.cint ext4_setattr(struct dentry*dentry,struct iattr*attr)int error,rc=0;.ext4_journal_stop(handle);if(unlikely(error)return error;.err_out:if(error)if(!error)error=rc;return error;Patchif(ia_valid&ATTR_UID&!uid_eq(attr-ia_uid,inode-i_uid)|(ia_valid&ATTR_GID&!gid_eq(attr-ia_gid,inode-i_gid)error=ext4_mark_inode_dirty(handle,inode);/缺少调用函数 ext4_fc_stop_update(inode),导致引用计数泄露!ext4_fc_stop_update(inode);struct inode*inode=d_inode(dentry);ext4_fc_stop_update(inode);ext4_fc_start_update(inode);ext4_std_error(inode-i_sb,error);图1Linux-v5.11 中一条不恰当引用计数更新缺陷为检测引用计数缺陷,传统静态分析方法需要知道哪些函数会增加引用计数,哪些函数会减少引用计数.例如,只有知道函数 ext4_fc_start_update()和函数 ext4_fc_stop_update()是一对引用获取函数和引用释放函数,RID6才能检测图 1 所示缺陷.然而,在实际大型系统中,可能存在成百上千更新引用计数的函数.手动收集的方式费力耗时,且容易出错和遗漏.Mao 等人6根据命名习惯来搜索可能的引用计数函数,如“get-put”“inc-dec”等.但在实际编码中,命名方式可能多种多样.根据函数名来获取引用计数函数可能会遗漏 ext4_fc_start_update()和 ext4_fc_stop_update().因此,在实践中,可能需要对特定目标系统非常了解的专家配合进行反复试验,才能构建出有针对性的检查工具.A BA B为检测缺陷,代码挖掘方法1012首先提取形如的隐式编码规则,其中 A 和 B 是编码元素(如函数调用、条件检查等)的集合.规则表示包含 A 的上下文同时也应当包含 B.违反隐式编码规则的代码则可能存在缺陷.例如,在 Linux 内核中,在调用 ext4_fc_start_update()的 7 个函数中都随后调用了 ext4_fc_stop_update(),挖掘算法可以提取出隐式编码规则 R:ext4_fc_start_update()ext4_fc_stop_update().但由于图 1 中的函数 ext4_setattr()既调用了 ext4_fc_start_update()也调用了 ext4_fc_stop_update(),挖掘算法将认为函数 ext4_setattr()遵守编码规则 R.因此,基于挖掘的方法难以有效检测图 1 所示缺陷.为解决上述问题,本文提出了一种将代码挖掘技术与传统静态分析技术有机相结合的方法 RTDMiner,来检测引用计数缺陷.RTDMiner 的框架如图 3 所示,其基本思想是通过两次挖掘来提取缺陷模式.首先,根据引用计数的一般使用规律,利用数据挖掘技术从源代码中自动识别引用获取函数和引用释放函数.一般地,增加引用和减少引用要成对出现,并且减少引用之后,当前上下文通常不应该再使用该对象.然后,再次利用数据挖掘技术来提取调用引用获取函数但不需要调用相应的引用释放函数的例外模式.最后,根据引用获取/释放函数和例外模式来检测潜在缺陷,并对检测到的疑似缺陷进行评分和排序,以凸显真实缺陷.4728软件学报2023 年第 34 卷第 10 期12345678910111213141516171819202122232425/linux-v5.11/fs/ext4/inode.c/*This function is called by the high level call VFS callbacks before*/void ext4_fc_start_update(/*Stop inode update and wake up waiting fast commits if any.*/wake_up_all(&ei-i_fc_wait);if(atomic_dec_and_test(&ei-i_fc_updates)*Inform Ext4s fast about start of an inode update*performing any inode update.This function blocks if theres an ongoing*fast commit on the inode in question.struct ext4_inode_info*ei=EXT4_I(inode);struct ext4_inode_info*ei=EXT4_I(inode);void ext4_fc_stop_update(struct inode*inode)spin_unlock(&EXT4_SB(inode-i_sb)-s_fc_lock);/增加引用计数i_fc_updates的值atomic_inc(&ei-i_fc_updates);struct inode*inode)/减少引用计数i_fc_updates的值,并检查结果是否为 0图2Linux-v5.11 中的引用获取和引用释放函数源代码缺陷挖掘例外模式识别敏感函数检测缺陷&排序例外模式引用获取/释放函数引用获取/释放函数图3RTDMiner 框架图例如,配对出现的函数 ext4_fc_start_update()和 ext4_fc_stop_update()分别增加和减少了对象 inode 的成员变量 i_fc_updates.而在 ext4_fc_stop_update()之后通常不再使用 inode.因此,函数 ext4_fc_start_update()和 ext4_fc_stop_update()被当作一对引用获取/释放函数.通过模式挖掘发现,调用 ext4_fc_start_update()之后的所有路径都应该调用 ext4_fc_stop_update().而函数 ext4_setattr()中有一条路径违反了上述规则,因此存在潜在缺陷.可见,将代码挖掘和静态分析相结合可以有效检测图 1 所示引用计数缺陷.3 识别引用获取函数和引用释放函数 3.1 方法概述如图 4 所示,根据引用计数的一般使用规律,利用静态分析技术和数据挖掘技术自动识别引用获取函数和引用释放函数.我们发现引用计数在实际使用中一般遵守如下规律.源代码代码挖掘静态分析函数及结构成员摘要信息频繁函数对和终止函数推理候选引用获取函数和引用释放函数控制流图程序依赖图图4RTDMiner 识别引用获取函数和引用释放函数的框架图边攀等:RTDMiner:基于数据挖掘的引用计数更新缺陷检测方法4729(1)资源的引用计数通常用表示资源的结构体的一个成员变量来表示,对引用计数的值的更新也往往封装在引用获取函数和引用释放函数中.(2)在引用获取函数中,如果新创建一个对象,则将资源的引用计数初始化为 1;否则,如果是已经存在的对象,则将资源的引用计数加 1.(3)在引用释放函数中,资源的引用计数将被减 1.有些引用释放函数还会检查引用计数的值,并在取值降为0 时释放资源.(4)当引用被释放后,相应的资源在当前上下文通常处于不可用状态,可能随时被修改甚至释放.因此,为了避免非预期错误,在引用释放函数被调用之后通常不再使用资源.(5)为了保证引用计数的一致性,引用获取函数和引用释放函数通常成对调用.基于上述规律,识别引用获取函数和引用释放函数的流程如下.首先,利用自底向上的程序归纳技术计算函数及数据结构的摘要信息(见第 3.2 节).摘要信息记录了对成员变量的修改情况,如初始化、递增、递减或其他修改情况.其次,利用数据挖掘技术从源代码中挖掘频繁函数对,并识别参数很少再次引用的终止函数(见第 3.3 节).最后,根据规律(1)(3),只有那些对参数的某个成员变量进行递增或递减的函数才可能是引用获取或释放函数;而根据规律(4)和(5),可以进一步筛选引用获取函数和引用释放函数(见第 3.4 节).3.2 计算函数和数据结构摘要我们计算在整个系统和特定函数中对结构成员的变更情况.根据结构成员的变更摘要信息,可以识别那些可能用来表示引用计数的结构成员,并进一步筛选出可能的引用获取函数及引用释放函数.根据引用计数的使用规律,通常在分配资源时将引用计数的值初始化为 1,增加对资源的引用时将引用计数的值递增,而释放对资源的引用时则将引用计数的值递减.初始化为 1 可以视为特殊的递增,即将变量值隐式地从 0 变成 1.因此,在本文中,我们主要关注 3 种变量变更类型,即递增(increment,I)、递减(decrement,D)和其他(other,O),分别 I、D 和 O 来表示.除了像“v+”“v”“v+=1”“v=1”等通用递增递减操作,目标系统可能还有一些系统特定的递增递减操作,例如 Linux 内核中的递增函数 atomic_inc(v)和递减函数 atomic_dec(v).相对于引用获取和引用释放函数,这些递增递减操作较为容易获取且通常在很长时间保持不变.因此,在本文中我们将递增和递减操作作为线索来发现引用获取/释放函数.TT(s,m)T(f,i,m)我们用集合来记录所有结构成员的变更情况.其中记录了程序中对结构体 s 的成员 m 的所有可能的更新情况,而记录了函数 f 的第 i 个参数的成员 m 的更新情况.在本文中,为便于说明,我们将函数返回值也当成函数的一个参数.当 i=0 时,表示函数 f 的返回值,当 i 大于 0 时则表示函数 f 的第 i 个参数.G如算法 1 所示,我们采用自底向上(bottom-up)的路径敏感的过程间分析方法来计算结构成员的更新情况.算法 1 的输入是函数调用图.算法 1 首先根据函数间的调用关系对函数进行排序,使得被调用函数先于调用函数被分析(第 34 行).算法 1.计算数据结构及函数摘要.G1procedurecalculate_summary()T2=;FG3=topological_sort();4for(eachfunctionfinF)5/计算当前函数内成员变量的更新类型6for(eachstatementstmtinf)7if(stmtupdatesmembermofvariablevwithtypet)8s=structure_of(v);/变量 v 的类型4730软件学报2023 年第 34 卷第 10 期T(s,m)=T(s,m)t9;/更新结构体摘要10end if11end for12/计算每条路径上对参数的成员变量的更新类型13for(eachpathpoff)14for(eachparameteri andmemberm)T,p,i,m15t=calculate_update_type();16if(t!=O)T(f,i,m)=T(f,i,m)t17;/更新函数摘要18end if19end for20end for21end forT22return;/返回摘要信息23end procedure24T,p,i,m25procedurecalculate_update_type()26numInc=0;/递增计数,记录对结构成员 m 进行递增的次数27numDec=0;/递减计数,记录对结构成员 m 进行递减的次数28for(eachstatementstmtonpathp)29t=O;30 if(stmtcallsfunctiong)T=T(g,j,m)31;/函数 f 的参数 i 对应函数 g 的参数 jT=I OR T=D32if()T33 t=.value(0);/获取在调用函数中的更新类型34end if35else if(stmtupdatesmembermofparameteriwithtypet1)36t=t1;37end if38numInc+=(t=I);/如果进行了类型为 I 的更新,则增加递增计数39numDec+=(t=D);/如果进行了类型为 D 的更新,则增加递减计数40end for41if(numInc=numDec+1)42returnI;/在该路径上,结构成员 m 的值递增了43else if(numInc+1=numDec)44returnD;/在该路径上,结构成员 m 的值递减了45end if46returnO;/在该路径上,结构成员 m 的值的变更不是递增也不是递减47 end procedureT(s,m)对于每个函数 f,首先遍历函数中所有语句,如果某条语句更新了结构体 s 的成员变量 m 的值,假设更新类型为 t,则将 t 加入 m 的变更集合中(第 611 行).然后,遍历函数 f 的路径(第 13 行),计算在该路径上对参数边攀等:RTDMiner:基于数据挖掘的引用计数更新缺陷检测方法4731T(f,i,m)Ti 的成员变量 m 的更新类型 t(第 1415 行).如果是递增或递减操作,则将 t 加入到集合中,而其他更新类型则不进行处理(第 1618 行).最后,算法返回数据结构及函数的摘要集(第 22 行).我们用子程序 caculate_update_type()来计算成员变量在某条路径上的更新类型(第 2547 行).递增计数和递减计数分别记录了路径上对成员变量进行递增和递减的语句数.特别是对于函数调用语句,并没有进入被调用函数进行分析,而是根据它的摘要信息来确定结构成员的更新情况(第 3034 行),这也是我们将该计算方法称为自底向上的过程间