一种面向内核接口的顺序依赖规则挖掘与违例检测方法  

A Method to Mine Sequence Dependent Rules and Detect Violations for Kernel Extension Interfaces

作　　者：刘虎球[1] 白家驹[1] 王瑀屏[1] 

机构地区：[1]清华大学计算机科学与技术系,北京100084

出　　处：《计算机学报》2015年第5期1007-1019,共13页Chinese Journal of Computers

基　　金：国家"八六三"高技术研究发展计划重大课题项目以支撑公众与企业服务为主的网络操作系统研制(2011AA01A203)资助~~

摘　　要：内核扩展函数以接口的形式提供给驱动,用于管理设备和申请相关的资源.这些接口中存在大量的顺序依赖规则,如自旋锁必须经过初始化才能加锁,然后才能解锁;驱动在加载时申请的内存,卸载时必须予以释放等.然而,驱动开发者常常不熟悉或疏忽内核接口的使用规则,导致驱动中存在大量的接口使用违例,影响驱动及系统的可靠运行.文中提出了一种面向内核接口的顺序依赖规则挖掘与违例检测方法(SD-Miner).该方法结合驱动源码的结构特征,对驱动代码使用的内核接口进行统计分析,挖掘并提取内核接口的顺序依赖规则,并利用提取的规则检测现有的驱动源码中的使用违例.SD-Miner对Linux 3.10.10和2.6.38的驱动源码分别进行了规则挖掘和违例检测.对比检测结果发现,在2.6.38中检测出的错误中,有64处在3.10.10中得到了修正.SD-Miner检测和分析Linux 3.10.10的3781款驱动的过程仅耗费5min,共计提取出了220个顺序依赖相关的接口使用规则,并检测到了756个使用违例,作者将其中50个提交给了开发者,累计有25个回复者对20个使用违例进行了确认.实验结果表明,SD-Miner能够有效地挖掘出内核接口的顺序依赖规则,并检测出使用违例,进而辅助开发人员对驱动进行修正来提高驱动可靠性.此外,规则的挖掘是基于驱动的结构信息和统计信息,不需要开发者在源码中提供额外的注释及标注.Kernel extension functions are provided to drivers in the form of interfaces, to manage devices and resources. There are many sequence dependent rules in these interfaces, like the spin lock must be initialized before being locked, and then unlocked; the memory allocated for probing the device should be released when removing the device. However, due to driver developers＇ ignorance or unawareness of using these rules of the interfaces, a lot of violations may occur, which harms the reliability of drivers. This paper presents a method to mine the sequence dependent rules and detect violations for the kernel extension interfaces （SD-Miner）. SD-Miner associates the structure of drivers, and exploits the statistic method to mine and extract sequence dependent rules, and it detects violations on the source code of drivers with extracted rules. SD-Miner has checked two versions of Linux 2.6.38 and 3.10. 10, and 64 bugs detected in 2.6.38 have been fixed in 3.10. 10. 220 sequence dependent rules have been extracted from 3.10. 10, and 756 viola- tions have been detected as well. It only costs about 5 minutes to mine rules and detect violations for Linux 3.10.10. The selected 50 bugs have been reported to the developers, and 20 bugs （among 25 replies） have been confirmed. All the experimental evaluation results show that SD- Miner can mine sequence dependent rules for kernel extension interfaces effectively, and it also can detect real violations from the source code of drivers. Besides, with the help of SD-Miner, programmers can improve the reliability of drivers, without adding special notations to drivers.

关 键 词：内核扩展函数 规则挖掘 违例检测 顺序依赖规则 

分 类 号：TP312[自动化与计算机技术—计算机软件与理论]