Kevin Boos
Emilio Del Vecchio
ABSTRACT
Understanding and managing the propagation of states in operating systems has become an intractable problem due to their sheer size and complexity. Despite modularization efforts, it remains a significant barrier to many contemporary computing goals: process migration, fault isolation and tolerance, live update, software virtualization, and more. Though many previous OS research endeavors have achieved these goals through ad-hoc, tedious methods, we argue that they have missed the underlying reason why these goals are so challenging: state spill.
State spill occurs when a software entity's state undergoes lasting changes as a result of a transaction from another entity. In order to increase awareness of state spill and its harmful effects, we conduct a thorough study of modern OSes and contribute a classification of design patterns that cause state spill. We present StateSpy, an automated tool that leverages cooperative static and runtime analysis to detect state spill in real software entities. Guided by StateSpy, we demonstrate the presence of state spill in 94% of Android system services. Finally, we analyze the harmful impacts of state spill and suggest alternative designs and strategies to mitigate them.
- Design of the Genode OS Architecture: Interfaces and Mechanisms. http://genode.org/documentation/architecture/interfaces. Accessed: 2016-02-22.Google Scholar
- Invoking user-space applications from the kernel. https://www.ibm.com/developerworks/library/l-user-space-apps/. Accessed: 2016-10-13.Google Scholar
- UI/Application Exerciser Monkey. https://developer.android.com/studio/test/monkey.html. Accessed: 2016-10-10.Google Scholar
- X.Org Security Advisory: Dec. 9, 2014. https://www.x.org/wiki/Development/Security/Advisory-2014-12-09/. Accessed: 2016-10-11.Google Scholar
- G. Altekar, I. Bagrak, P. Burstein, and A. Schultz. Opus: Online patches and updates for security. In Proc. USENIX Security, 2005.Google ScholarDigital Library
- J. Andrus, C. Dall, A. V. Hof, O. Laadan, and J. Nieh. Cells: A virtual mobile smartphone architecture. In Proc. ACM SOSP, 2011. Google ScholarDigital Library
- J. Arnold and M. F. Kaashoek. Ksplice: Automatic rebootless kernel updates. In Proc. ACM EuroSys, 2009. Google ScholarDigital Library
- S. Arzt, S. Rasthofer, C. Fritz, E. Bodden, A. Bartel, J. Klein, Y. Le Traon, D. Octeau, and P. McDaniel. FlowDroid: Precise context, flow, field, object-sensitive and lifecycle-aware taint analysis for Android apps. In Proc. ACM PLDI, 2014. Google ScholarDigital Library
- P. Barton-Davis. Linux kernel mailing list: upcalls. http://lkml.iu.edu/hypermail/linux/kernel/9809.3/0922.html. Accessed: 2016-10-13.Google Scholar
- K.Boos. StateSpy: State Spill Characterization Project Website. http://download.recg.org.Google Scholar
- K. Boos, A. Amiri Sani, and L. Zhong. Eliminating state entanglement with checkpoint-based virtualization of mobile OS services. In Proc. ACM APSys, 2015. Google ScholarDigital Library
- G. Candea, S. Kawamoto, Y. Fujiki, G. Friedman, and A. Fox. Microreboot - a technique for cheap recovery. In Proc. USENIX OSDI, 2004.Google ScholarDigital Library
- E. Chin, A. P. Felt, K. Greenwood, and D. Wagner. Analyzing inter-application communication in Android. In Proc. ACM MobiSys, 2011. Google ScholarDigital Library
- D. D. Clark. The structuring of systems using upcalls. In Proc. ACM SOSP, 1985. Google ScholarDigital Library
- G. Coulson, G. Blair, P. Grace, F. Taiani, A. Joolia, K. Lee, J. Ueyama, and T. Sivaharan. A generic component model for building systems software. ACM Transactions on Computer Systems, 2008. Google ScholarDigital Library
- F. M. David, E. M. Chan, J. C. Carlyle, and R. H. Campbell. CuriOS: Improving reliability through operating system structure. In Proc. USENIX OSDI, 2008.Google ScholarDigital Library
- P. Dong. Reducing fate-sharing in software systems via fine-grained checkpoint and restore. Master's thesis, Rice University, 2016.Google Scholar
- W. Enck, P. Gilbert, S. Han, V. Tendulkar, B.-G. Chun, L. P. Cox, J. Jung, P. McDaniel, and A. N. Sheth. TaintDroid: an information-flow tracking system for realtime privacy monitoring on smartphones. In Proc. USENIX OSDI, 2010.Google ScholarDigital Library
- D. R. Engler, M. F. Kaashoek, and J. O'Toole, Jr. Exokernel: An operating system architecture for application-level resource management. In Proc. ACM SOSP, 1995. Google ScholarDigital Library
- J.-P. Fassino, J.-B. Stefani, J. L. Lawall, and G. Muller. THINK: A software framework for component-based operating system kernels. In Proc. USENIX ATC, 2002.Google Scholar
- N. Feske and C. Helmuth. A Nitpicker's guide to a minimal-complexity secure GUI. Technical report, Technische Universität Dresden, 2005.Google Scholar
- R. Fielding. Representational state transfer. Architectural Styles and the Design of Network-based Software Architecture, 2000.Google Scholar
- R. T. Fielding and R. N. Taylor. Principled design of the modern Web architecture. ACM Transactions on Internet Technology (TOIT), 2002.Google Scholar
- B. Ford, G. Back, G. Benson, J. Lepreau, A. Lin, and O. Shivers. The Flux OSKit: A substrate for kernel and language research. In Proc. ACM SOSP, 1997. Google ScholarDigital Library
- C. Giuffrida, A. Kuijsten, and A. S. Tanenbaum. Safe and automatic live update for operating systems. In Proc. ACM ASPLOS, 2013. Google ScholarDigital Library
- J. N. Herder, H. Bos, B. Gras, P. Homburg, and A. S. Tanenbaum. Minix 3: A highly reliable, self-repairing operating system. ACM SIGOPS Operating Systems Review, 2006. Google ScholarDigital Library
- K. Hui, J. Appavoo, R. Wisniewski, M. Auslander, D. Edelsohn, B. Gamsa, O. Krieger, B. Rosenburg, and M. Stumm. Supporting hot-swappable components for system software. In Proc. ACM HotOS, 2001. Google ScholarCross Ref
- A. Kadav, M. J. Renzelmann, and M. M. Swift. Fine-grained fault tolerance using device checkpoints. In Proc. ACM ASPLOS, 2013. Google ScholarDigital Library
- M. Krohn, A. Yip, M. Brodsky, N. Cliffer, M. F. Kaashoek, E. Kohler, and R. Morris. Information flow control for standard OS abstractions. In Proc. ACM SOSP, 2007. Google ScholarDigital Library
- L. Lamport. A new solution of Dijkstra's concurrent programming problem. Communications of the ACM, 1974. Google ScholarDigital Library
- A. Madhavapeddy, R. Mortier, C. Rotsos, D. Scott, B. Singh, T. Gazagnaire, S. Smith, S. Hand, and J. Crowcroft. Unikernels: Library operating systems for the cloud. In Proc. ACM ASPLOS, 2013. Google ScholarDigital Library
- K. Makris and K. D. Ryu. Dynamic and adaptive updates of non-quiescent subsystems in commodity operating system kernels. In Proc. ACM EuroSys, 2007. Google ScholarDigital Library
- N. R. Mehta, N. Medvidovic, and S. Phadke. Towards a taxonomy of software connectors. In Proc. ACM/IEEE ICSE, 2000. Google ScholarDigital Library
- D. S. Milojičić, F. Douglis, Y. Paindaveine, R. Wheeler, and S. Zhou. Process migration. ACM Comput. Surv., 2000. Google ScholarDigital Library
- D. Octeau, P. McDaniel, S. Jha, A. Bartel, E. Bodden, J. Klein, and Y. Le Traon. Effective inter-component communication mapping in android with EPICC: An essential step towards holistic security analysis. In Proc. USENIX Security, 2013.Google ScholarDigital Library
- A. J. Offutt, M. J. Harrold, and P. Kolte. A software metric system for module coupling. Journal of Systems and Software, 1993. Google ScholarDigital Library
- R. Olsson. Applying REST principles on local client-side APIs. Master Thesis, KTH Royal Institute of Technology, 2014.Google Scholar
- S. Osman, D. Subhraveti, G. Su, and J. Nieh. The design and implementation of Zap: A system for migrating computing environments. In Proc. USENIX OSDI, 2002. Google ScholarDigital Library
- C. Pautasso and E. Wilde. Why is the web loosely coupled?: a multi-faceted metric for service design. In Proc. WWW, 2009. Google ScholarDigital Library
- C. Pautasso, O. Zimmermann, and F. Leymann. RESTful web services vs. 'big' web services: making the right architectural decision. In Proc. WWW, 2008. Google ScholarDigital Library
- D. E. Porter, S. Boyd-Wickizer, J. Howell, R. Olinsky, and G. C. Hunt. Rethinking the library os from the top down. In Proc. ACM ASPLOS, 2011. Google ScholarDigital Library
- A. Reid, M. Flatt, L. Stoller, J. Lepreau, and E. Eide. Knit: Component composition for systems software. In Proc. USENIX OSDI, 2000.Google Scholar
- N. Sangal, E. Jordan, V. Sinha, and D. Jackson. Using dependency models to manage complex software architecture. In Proc. ACM OOPLSA, 2005. Google ScholarDigital Library
- S. R. Schach, B. Jin, D. R. Wright, G. Z. Heller, and A. J. Offutt. Maintainability of the linux kernel. IEE Proceedings-Software, 2002. Google ScholarCross Ref
- R. W. Scheifler and J. Gettys. The x window system. ACM Transactions on Graphics (TOG), 1986.Google Scholar
- K. Sen. Concolic testing. In Proc. IEEE/ACM ASE, 2007. Google ScholarDigital Library
- R. Sethi. Programming languages: concepts and constructs. 1996.Google Scholar
- M. Siniavine and A. Goel. Seamless kernel updates. In Proc. IEEE/IFIP DSN, 2013. Google ScholarDigital Library
- C. A. Soules, J. Appavoo, K. Hui, R. W. Wisniewski, D. Da Silva, G. R. Ganger, O. Krieger, M. Stumm, M. A. Auslander, M. Ostrowski, B. Rosenburg, and J. Xenidis. System support for online reconfiguration. In Proc. USENIX ATC, 2003.Google Scholar
- B. P. Swift. User mode scheduling in MINIX 3. Technical report, Vrije University Amsterdam, 2010.Google Scholar
- M. M. Swift, M. Annamalai, B. N. Bershad, and H. M. Levy. Recovering device drivers. In Proc. USENIX OSDI, 2004.Google ScholarDigital Library
- M. M. Swift, B. N. Bershad, and H. M. Levy. Improving the reliability of commodity operating systems. In Proc. ACM SOSP, 2003. Google ScholarDigital Library
- P. Tullmann, J. Lepreau, B. Ford, and M. Hibler. User-level checkpointing through exportable kernel state. In Proc. IEEE Wrkshp. Object-Orientation in Operating Systems, 1996. Google ScholarCross Ref
- R. Vallée-Rai, P. Co, E. Gagnon, L. Hendren, P. Lam, and V. Sundaresan. Soot - a java bytecode optimization framework. In Proc. CASCON, 1999.Google ScholarDigital Library
- A. Van't Hof, H. Jamjoom, J. Nieh, and D. Williams. Flux: Multi-surface computing in Android. In Proc. ACM EuroSys, 2015. Google ScholarDigital Library
- F. Wei, S. Roy, X. Ou, and Robby. Amandroid: A precise and general inter-component data flow analysis framework for security vetting of Android apps. In Proc. ACM CCS, 2014.Google Scholar
- M.Weiser. Program slicing. In Proc. ACM/IEEE ICSE, 1981.Google Scholar
- L. Yu, S. R. Schach, K. Chen, G. Z. Heller, and J. Offutt. Maintainability of the kernels of open-source operating systems: A comparison of Linux with FreeBSD, NetBSD, and OpenBSD. Journal of Systems and Software, 2006. Google ScholarDigital Library
- N. Zeldovich, S. Boyd-Wickizer, E. Kohler, and D. Mazières. Making information flow explicit in HiStar. In Proc. USENIX OSDI, 2006.Google Scholar
- N. Zeldovich, S. Boyd-Wickizer, and D. Mazieres. Securing distributed systems with information flow control. In Proc. USENIX NSDI, 2008.Google Scholar
- G. Zellweger, S. Gerber, K. Kourtis, and T. Roscoe. Decoupling cores, kernels, and operating systems. In Proc. USENIX OSDI, 2014.Google ScholarDigital Library
Recommendations
Spill hazard evaluation for chemicals shipped in bulk using modeling
A wide variety of chemicals are shipped in bulk world-wide, raising concerns regarding the ecological and human health risks of spills of hazardous materials. A screening analysis was performed, using the chemical spill model CHEMMAP to estimate the ...
Orimulsion® spill modelling in marine environments
Orimulsion, a fuel product developed in Venezuela and transported to markets by ocean going tankers, is an emulsion composed of about 70% bitumen (a heavy hydrocarbon) and 30% water to which a surfactant has been added. It has the potential to serve as ...
Comments