A method to mine sequence dependent rules and detect violations for kernel extension interfaces

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 violations 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.