Analysis of typical faults in Linux operating system drivers
Abstract
Fast evolution of the Linux operating system kernel and drivers, developed by a big programmers community distributed all over the world, led to nowadays there is not a common base of rules that completely describe a correct interaction between drivers and the kernel. This is an obstacle both for programmers that do not have expert knowledge in all peculiarities of the given interaction, and for development and application of tools that could find corresponding typical faults in the automatic way. The given paper presents a method to detect and to classify typical faults and corresponding rules. This method is based on analysis of changes, made to Linux operating system drivers.
The paper gives results of the method application to stable versions of the Linux kernel from 2.6.35 till 3.0 starting from October 26, 2010 till October 26, 2011. We analyzed in total 1503 unique commits to drivers, marked 396 (about 27%) of them as fixes of typical faults and provided a classification and a distribution by classes for these typical faults. We distinguished 3 classes of typical faults: generic (faults all C programs are subjected to), specific (faults related to misuses of the Linux kernel API) and synchronization (faults related to parallel execution). We found that specific faults constitute about 50% of all typical faults. Then each typical fault was ascribed to one of 21 first-level subclasses: 12, 7 and 2 for specific, generic and synchronization classes correspondingly. We found that more than 50% of typical faults correspond to 5 first-level subclasses. More than 80% of typical faults correspond to 14 first-level subclasses. The most frequent faults were race conditions during parallel execution – they account for about 17% of all typical faults. Second and third places with about 9% were occupied by leaks of specific resources and null pointer deference.About the Authors
V. S. Mutilin
ISP RAS
Russian Federation
Russian Federation
E. M. Novikov
ISP RAS
Russian Federation
Russian Federation
A. V. Khoroshilov
ISP RAS
Russian Federation
Russian Federation
References
1. Corbet J., Kroah-Hartman G., McPherson A. Linux kernel development. How Fast it is Going, Who is Doing It, What They are Doing, and Who is Sponsoring It. http://go.linuxfoundation.org/who-writes-linux-2012, 2012.
2. Leemhuis T. What's new in Linux 3.3. http://www.h-online.com/open/features/What-s-new-in-Linux-3-3-1466872.html, 2012.
3. Vanilla Linux kernel. http://www.kernel.org.
4. Corbet J. How to Participate in the Linux Community. A Guide To The Kernel Development Process. http://www.linuxfoundation.org/sites/main/files/How-Participate-Linux-Community_0.pdf, 2008.
5. Kerner S.M. The Red Hat Enterprise Linux 6 Kernel: What Is It? http://www.serverwatch.com/news/article.php/3880131/The-Red-Hat-Enterprise-Linux-6-Kernel-What-Is-It.htm, 2010.
6. openSUSE kernel. http://en.opensuse.org/Kernel.
7. Debian kernel. http://wiki.debian.org/DebianKernel.
8. Real-Time Linux. https://www.osadl.org/Realtime-Linux.projects-realtime-linux.0.html.
9. Android operating system. http://developer.android.com/guide/basics/what-is-android.html.
10. Chou A., Yang J., Chelf B., Hallem S., Engler D. An Empirical Study of Operating System Errors. In Proc. 18th ACM Symposium on Operating Systems Principles (SOSP), pp. 73-88, 2001. doi: 10.1145/502034.502042
11. Swift M., Bershad B., Levy H. Improving the reliability of commodity operating systems. In Proc. 19th ACM Symposium on Operating Systems Principles (SOSP), pp. 73-88, 2003. doi: 10.1145/502034.502042
12. Ganapathi A., Ganapathi V., Patterson D. Windows XP kernel crash analysis. In Proc. 20th Conference on Large Installation System Administration (LISA), pp. 149-159, 2006.
13. Palix N., Thomas G., Saha S., Calves C., Lawall J., Muller G. Faults in linux: ten years later. In Proc. 16th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pp. 305-318, 2011. doi: 10.1145/1950365.1950401
14. Butt S., Ganapathy V., Swift M.M., Chang C.-C. Protecting Commodity Operating System Kernels from Vulnerable Device Drivers. In Proc. Computer Security Applications Conference (ACSAC), pp. 301-310, 2009. doi: 10.1109/ACSAC.2009.35
15. Tian D., Xiong X., Hu C., Liu P. Policy-centric protection of OS kernel from vulnerable loadable kernel modules. In Proc. Information Security Practice and Experience, LNCS, vol. 6672, pp. 317-332, 2011. doi: 10.1007/978-3-642-21031-0_24
16. Raymond E.S. The Cathedral and the Bazaar: Musings on Linux and Open Source by an Accidental Revolutionary. O'Reilly Media, 1999.
17. Glass R.L. Facts and Fallacies of Software Engineering. Addison Wesley, 2002.
18. ISO/IEC TR 24772. Information Technology — Programming Languages — Guidance to Avoiding Vulnerabilities in Programming Languages through Language Selection and Use, 2010.
19. Kroah-Hartman G.. The Linux kernel driver interface. http://www.kernel.org/doc/Documentation/stable_api_nonsense.txt.
20. Linux kernel documentation. http://kernel.org/doc/Documentation.
21. Rubini A. Linux Device Drivers (Nutshell Handbooks). O'Reilly Media, 1998.
22. Beck M., Bohme H., Dziadzka M., Kunitz U., Magnus R., Verworner D. Linux Kernel Internals. Addison-Wesley, 1996.
23. Linux kernel mailing list. https://lkml.org.
24. Indexed source code of various versions of the Linux kernel. http://lxr.linux.no.
25. Russell R. Unreliable Guide To Hacking The Linux Kernel. http://www.kernel.org/doc/htmldocs/kernel-hacking.html, 2005.
26. Repository of stable versions of the Linux kernel. http://git.kernel.org/?p=linux/kernel/git/stable/linux-stable.git;a=summary.
27. Saad M.K. Browsing Linux Kernel. Linux Day, 2007.
28. Kroah-Hartman G. Kernel development statistics for 2.6.35. http://lwn.net/Articles/395961, 2010.
29. Results of analysis of commits to Linux drivers. http://linuxtesting.org/downloads/ldv-commits-analysis-2012.zip.
30. Engler D., Chen D.Y., Hallem S., Chou A., Chelf B. Bugs as deviant behavior: a general approach to inferring errors in systems code. In Proc. 18th ACM Symposium on Operating Systems Principles (SOSP), vol. 35, issue 5, pp. 57-72, 2001. doi: 10.1145/502034.502041
31. Li Z., Zhou Y. PR-Miner: automatically extracting implicit programming rules and detecting violations in large software code. In Proc. 10th European Software Engineering Conference held jointly with 13th ACM SIGSOFT International Symposium on Foundations of Software Engineering (ESEC/FSE), vol. 30, issue 5, pp. 306-315, 2005. doi:10.1145/1081706.1081755
Review
For citations:
Mutilin V.S., Novikov E.M., Khoroshilov A.V. Analysis of typical faults in Linux operating system drivers. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2012;22. (In Russ.)
Email this article 