Fast byte-granularity software fault isolation

ABSTRACT

Bugs in kernel extensions remain one of the main causes of poor operating system reliability despite proposed techniques that isolate extensions in separate protection domains to contain faults. We believe that previous fault isolation techniques are not widely used because they cannot isolate existing kernel extensions with low overhead on standard hardware. This is a hard problem because these extensions communicate with the kernel using a complex interface and they communicate frequently. We present BGI (Byte-Granularity Isolation), a new software fault isolation technique that addresses this problem. BGI uses efficient byte-granularity memory protection to isolate kernel extensions in separate protection domains that share the same address space. BGI ensures type safety for kernel objects and it can detect common types of errors inside domains. Our results show that BGI is practical: it can isolate Windows drivers without requiring changes to the source code and it introduces a CPU overhead between 0 and 16%. BGI can also find bugs during driver testing. We found 28 new bugs in widely used Windows drivers.

REFERENCES

• 1: M. Abadi, M. Budiu, U. Erlingsson, and J. Ligatti. Control-Flow Integrity: Principles, Implementations, and Applications. In ACM CCS, 2005.
• 2: P. Akritidis, C. Cadar, C. Raiciu, M. Costa, and M. Castro. Preventing memory error exploits with WIT. In IEEE Symposium on Security and Privacy, 2008.
• 3: Z. Anderson, D. Gay, and M. Naik. Lightweight annotations for controlling sharing in concurrent data structures. In PLDI, 2009.
• 4: P. Barham, B. Dragovic, K. Fraser, S. Hand, T. Harris, A. Ho, R. Neugebauer, I. Pratt, and A. Warfield. Xen and the art of virtualization. In SOSP, 2003.
• 5: B.N. Bershad, S. Savage, P. Pardyak, E.G. Sirer, M. Fiuczynski, D. Becker, S. Eggers, and C. Chambers. Extensibility, safety and performance in the SPIN operating system. In SOSP, 1995.
• 6: H. Bos and B. Samwel. Safe kernel programming in the OKE. In OPENARCH, 2002.
• 7: A. Chou, J. Yang, B. Chelf, S. Hallem, and D. Engler. An empirical study of operating system errors. In SOSP, 2001.
• 8: J. Christmansson and R. Chillarege. Generation of an error set that emulates software faults -- based on field data. In FTCS, 1996.
• 9: P. Chubb. Get more device drivers out of the kernel! In Linux Symposium, 2004.
• 10: J. Criswell, A. Lenharth, D. Dhurjati, and V. Adve. Secure virtual architecture: a safe execution environment for commodity operating systems. In SOSP, 2007.
• 11: U. Erlingsson, M. Abadi, M. Vrable, M. Budiu, and G.C. Necula. XFI: software guards for system address spaces. In OSDI, 2006.
• 12: A. Forin, D. Golub, and B. Bershad. An I/O system for Mach 3.0. In Proc. USENIX Mach Symposium, 1991.
• 13: V. Ganapathy, M. Renzelmann, A. Balakrishnan, M. Swift, and S. Jha. The Design and Implementation of Microdrivers. 2008.
• 14: D. Gay, R. Ennals, and E. Brewer. Safe manual memory management. In ISMM, 2007.
• 15: K. Glerum, K. Kinshumann, S. Greenberg, G. Aul, V. Orgovan, G. Nichols, D. Grant, G. Loihle, and G. Hunt. Debugging in the (Very) Large: Ten Years of Implementation and Experience. In SOSP, 2009.
• 16: L.H. Linux Kernel Heap Tampering Detection. Phrack, 13(66), 2009.
• 17: B. Hackett, M. Das, D. Wang, and Z. Yang. Modular checking for buffer overflows in the large. In ICSE, 2006.
• 18: H. Härtig, M. Hohmuth, J. Liedtke, S. Schönberg, and J. Wolter. The performance of μ-kernel-based systems. In SOSP, 1997.
• 19: J.N. Herder, H. Bos, B. Gras, P. Homburg, and A.S. Tanenbaum. Minix 3: a highly reliable, self-repairing operating system. SIGOPS OSR, 40(3):80--89, 2006.
• 20: G.C. Hunt and J.R. Larus. Singularity: rethinking the software stack. SIGOPS OSR, 41(2):37--49, 2007.
• 21: A. Ionescu. Pointers and Handles: A Story of Unchecked Assumptions in the Windows Kernel. In Black Hat, 2008.
• 22: T. Jim, J.G. Morrisett, D. Grossman, M.W. Hicks, J. Cheney, and Y. Wang. Cyclone: A Safe Dialect of C. In USENIX Annual Technical Conference, 2002.
• 23: J. Katcher. Postmark: A new file system benchmark. Technical Report TR3022, Network Appliance, 1997.
• 24: V. Kiriansky, D. Bruening, and S.P. Amarasinghe. Secure Execution via Program Shepherding. In USENIX Security Symposium, 2002.
• 25: K. Kortchinsky. Real World Kernel Pool Exploitation. In SyScan'08 Hong Kong, 2008.
• 26: B. Leslie, P. Chubb, N. Fitzroy-Dale, S. Gotz, C. Gray, L. Macpherson, D. Potts, Y. Shen, K. Elphinstone, and G. Heiser. User-level device drivers: Achieved performance. Journal of Computer Science and Technology, 20(5), 2005.
• 27: J. LeVasseur, V. Uhlig, J. Stoess, and S. Gotz. Unmodified Device Driver Reuse and Improved System Dependability via Virtual Machines. In OSDI, 2004.
• 28: S. McCamant and G. Morrisett. Evaluating SFI for a CISC architecture. In USENIX Security Symposium, 2006.
• 29: Microsoft. Phoenix SDK. http://connect.microsoft.com/Phoenix.
• 30: Microsoft. User-Mode Driver Framework. http://www.microsoft.com/whdc/driver/wdf/UMDF.mspx.
• 31: Microsoft. Windows Driver Kit. http://www.microsoft.com/wdk.
• 32: G.C. Necula and P. Lee. Safe kernel extensions without run-time checking. In OSDI, 1996.
• 33: G.C. Necula, S. McPeak, and W. Weimer. CCured: type-safe retrofitting of legacy code. SIGPLAN Not., 37(1):128--139, 2002.
• 34: L. Seawright and R. MacKinnon. VM/370--A Study of Multiplicity and Usefulness. IBM Systems Journal, 18(1):4--17, 1979.
• 35: M.I. Seltzer, Y. Endo, C. Small, and K.A. Smith. Dealing with disaster: surviving misbehaved kernel extensions. In OSDI, 1996.
• 36: C. Small and M. Seltzer. MiSFIT: A tool for constructing safe extensible C++ systems. IEEE Concurrency, 6(3):34--41, 1998.
• 37: A. Srivastava, A. Edwards, and H. Vo. Vulcan: Binary transformation in a distributed environment. Technical Report MSR-TR-2001-50, Microsoft Research, 2001.
• 38: R.E. Strom and S. Yemini. Typestate: A programming language concept for enhancing software reliability. IEEE Transactions on Software Engineering, 12(1), 1986.
• 39: J. Sugerman, G. Venkitachalam, and B.-H. Lim. Virtualizing I/O devices on VMware Workstation's hosted virtual machine monitor. In USENIX Annual Technical Conference, 2001.
• 40: M. Sullivan and R. Chillarege. Software defects and their impact on system availability -- a study of field failures in operating systems. In FTCS, 1991.
• 41: M.M. Swift, M. Annamalai, B.N. Bershad, and H.M. Levy. Recovering device drivers. ACM TOCS, 24(4):333--360, 2006.
• 42: M.M. Swift, B.N. Bershad, and H.M. Levy. Improving the reliability of commodity operating systems. ACM TOCS, 23(1):77--110, 2005.
• 43: R. Wahbe, S. Lucco, T.E. Anderson, and S.L. Graham. Efficient software-based fault isolation. In SOSP, 1993.
• 44: D. Williams, P. Reynolds, K. Walsh, E.G. Sirer, and F.B. Schneider. Device driver safety through a reference validation mechanism. In OSDI, 2008.
• 45: E. Witchel, J. Rhee, and K. Asanović. Mondrix: memory isolation for Linux using mondriaan memory protection. In SOSP, 2005.
• 46: F. Zhou, J. Condit, Z. Anderson, I. Bagrak, R. Ennals, M. Harren, G. Necula, and E. Brewer. SafeDrive: safe and recoverable extensions using language-based techniques. In OSDI, 2006.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance

General Terms:
Measurement, Performance, Reliability, Security

Keywords:
device drivers, isolation