An empirical study of operating systems errors

ABSTRACT

We present a study of operating system errors found by automatic, static, compiler analysis applied to the Linux and OpenBSD kernels. Our approach differs from previous studies that consider errors found by manual inspection of logs, testing, and surveys because static analysis is applied uniformly to the entire kernel source, though our approach necessarily considers a less comprehensive variety of errors than previous studies. In addition, automation allows us to track errors over multiple versions of the kernel source to estimate how long errors remain in the system before they are fixed.We found that device drivers have error rates up to three to seven times higher than the rest of the kernel. We found that the largest quartile of functions have error rates two to six times higher than the smallest quartile. We found that the newest quartile of files have error rates up to twice that of the oldest quartile, which provides evidence that code "hardens" over time. Finally, we found that bugs remain in the Linux kernel an average of 1.8 years before being fixed.

REFERENCES

• 1: Alexander Aiken , Manuel Fähndrich , Zhendong Su, Detecting Races in Relay Ladder Logic Programs, Proceedings of the 4th International Conference on Tools and Algorithms for Construction and Analysis of Systems, p.184-200, March 28-April 04, 1998
• 2: Jean Arlat , Martine Aguera , Louis Amat , Yves Crouzet , Jean-Charles Fabre , Jean-Claude Laprie , Eliane Martins , David Powell, Fault Injection for Dependability Validation: A Methodology and Some Applications, IEEE Transactions on Software Engineering, v.16 n.2, p.166-182, February 1990 [doi>10.1109/32.44380]
• 3: Victor R. Basili , Barry T. Perricone, Software errors and complexity: an empirical investigation0, Communications of the ACM, v.27 n.1, p.42-52, Jan. 1984 [doi>10.1145/69605.2085]
• 4: M. Bishop and M. Dilger. Checking for Race Conditions in File Accesses. Computing systems, pages 131-152, Spring 1996.
• 5: J. Bradley Chen , Yasuhiro Endo , Kee Chan , David Mazières , Antonio Dias , Margo Seltzer , Michael D. Smith, The measured performance of personal computer operating systems, ACM Transactions on Computer Systems (TOCS), v.14 n.1, p.3-40, Feb. 1996 [doi>10.1145/225535.225536]
• 6: R. Chillarege and N. Bowen. Understanding Large System Failures - A Fault Injection Experiment. In The lgth International Symposium on Fault Tolerant Computing, June 1989.
• 7: D.R. Cox and D. Oakes. Analysis of Survival Data. Chapman and Hall, London, UK, 1984.
• 8: D.R. Engler, B. Chelf, A. Chou, and S. Hallem. Checking System Rules Using System-Specific, Programmer-Written Compiler Extensions. In Proceedings of Operating Systems Design and Implementation (OSDI), September 2000.
• 9: Norman E. Fenton , Niclas Ohlsson, Quantitative Analysis of Faults and Failures in a Complex Software System, IEEE Transactions on Software Engineering, v.26 n.8, p.797-814, August 2000 [doi>10.1109/32.879815]
• 10: J. Gray. A Census of Tandem System Availability Between 1985 and 1990. IEEE Transactions on Software Engineering, 39(4), October 1990.
• 11: Intrinsa. A Technical Introduction to PREfix/Enterprise. Technical report, Intrinsa Corporation, 1998.
• 12: N.L. Johnson and S. Kotz. Discrete Distributions. John Wiley & Sons, New York, NY, 1969.
• 13: Philip Koopman , John Sung , Christopher Dingman , Daniel Siewiorek , Ted Marz, Comparing Operating Systems Using Robustness Benchmarks, Proceedings of the 16th Symposium on Reliable Distributed Systems (SRDS '97), p.72, October 22-24, 1997
• 14: Ghani A. Kanawati , Nasser A. Kanawati , Jacob A. Abraham, FERRARI: A Flexible Software-Based Fault and Error Injection System, IEEE Transactions on Computers, v.44 n.2, p.248-260, February 1995 [doi>10.1109/12.364536]
• 15: I. Lee, R. Iyer, and F. Symptoms. Faults, Symptoms, and Software Fault Tolerance in the Tandem GUARDIAN Operating System. In International Symposium on Fault- Tolerant Computing (FTCS), 1993.
• 16: Will E. Leland , Murad S. Taqqu , Walter Willinger , Daniel V. Wilson, On the self-similar nature of Ethernet traffic, Conference proceedings on Communications architectures, protocols and applications, p.183-193, September 13-17, 1993, San Francisco, California, United States
• 17: Barton P. Miller , Louis Fredriksen , Bryan So, An empirical study of the reliability of UNIX utilities, Communications of the ACM, v.33 n.12, p.32-44, Dec. 1990 [doi>10.1145/96267.96279]
• 18: B.P. Miller, D. Koski, C.P. Lee, V. Maganty, R. Murthy, A. Natarajan, and J. Steidl. Fuzz Revisited: A Reexamination of the Reliability of UNIX Utilities and Services. Technical Report CS-TR-1995-1268, University of Wisconsin, 1995.
• 19: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 20: Sharon E. Perl , Richard L. Sites, Studies of Windows NT performance using dynamic execution traces, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.169-183, October 29-November 01, 1996, Seattle, Washington, United States
• 21: M. Rosenblum , E. Bugnion , S. A. Herrod , E. Witchel , A. Gupta, The impact of architectural trends on operating system performance, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.285-298, December 03-06, 1995, Copper Mountain, Colorado, United States
• 22: S.D. Silvey. Statistical Inference. Chapman and Hall, London, UK, 1975.
• 23: M. Sullivan and R. Chillarege. Software Defects and Their Impact on System 118 Availability - A Study of Field Failures in Operating Systems. In Plst International Symposium on Fault Tolerant Computing, June 1991.
• 24: M. Sullivan and R. Chillarege. A Comparison of Software Defects in Database Management Systems and Operating Systems. In 22nd International Symposium on Fault- Tolerant Computing, July 1992.
• 25: D. Wagner, J. Foster, E. Brewer, and A. Aiken. A First Step Towards Automated Detection of Buffer Overrun Vulnerabilities. In The 2000 Network and Distributed Systems Security Conference. San Diego, CA, February 2000.
• 26: Jun Xu , Zbigniew Kalbarczyk , Ravishankar K. Iyer, Networked Windows NT System Field Failure Data Analysis, Proceedings of the 1999 Pacific Rim International Symposium on Dependable Computing, p.178, December 16-17, 1999

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.0 General

          Nouns: Linux

General Terms:
Performance, Reliability