Discrete control for safe execution of IT automation workflows

ABSTRACT

As information technology (IT) administration becomes increasingly complex, workflow technologies are gaining popularity for IT automation. Writing correct workflow programs is notoriously difficult. Although static analysis tools are available, fixing defects remains manual and error-prone. This paper applies discrete control theory to IT automation workflows. Discrete control detects flaws in workflows just as static analysis does, and more importantly it also allows safe execution of flawed workflows by dynamically avoiding run-time failures. Our approach can guarantee compliance with certain requirements and can partially decouple requirements from software, reducing the need to modify the latter if the former change. We have implemented a discrete control module for a real IT automation system. Experiments with workflows from a real production system and with randomly generated workflows show that our approach scales to workflows of practical size.

REFERENCES

• 1: Jeannie Albrecht , Christopher Tuttle , Alex C. Snoeren , Amin Vahdat, PlanetLab application management using plush, ACM SIGOPS Operating Systems Review, v.40 n.1, January 2006 [doi>10.1145/1113361.1113370]
• 2: Thomas Ball , Ella Bounimova , Byron Cook , Vladimir Levin , Jakob Lichtenberg , Con McGarvey , Bohus Ondrusek , Sriram K. Rajamani , Abdullah Ustuner, Thorough static analysis of device drivers, Proceedings of the ACM SIGOPS/EuroSys European Conference on Computer Systems 2006, April 18-21, 2006, Leuven, Belgium
• 3: Y. Bar-David and G. Taubenfeld. Automatic discovery of mutual exclusion algorithms. In Proc. 17th Int'l Sympos. Dist. Comput (LNCS 2648), pages 136--150, Oct. 2003.
• 4: N. Ben Hadj-Alouane, S. Lafortune, and F. Lin. Variable lookahead supervisory control with state information. IEEE Trans. on Automatic Control, 39(12):2398--2410, Dec. 1994.
• 5: B. A. Brandin. The real-time supervisory control of an experimental manufacturing cell. IEEE Trans. on Robotics & Automation, 12(1):1--14, Feb. 1996.
• 6: Aaron B. Brown , Joseph L. Hellerstein, Reducing the cost of IT operations: is automation always the answer?, Proceedings of the 10th conference on Hot Topics in Operating Systems, p.12-12, June 12-15, 2005, Santa Fe, NM
• 7: Y.-L. Chen, S. Lafortune, and F. Lin. Resolving feature interactions using modular supervisory control with priorities. In Feature Interactions in Telecom, Networks IV, pages 108--122. IOS Press, 1997.
• 8: R. Cieslak, C. Desclaux, A. Fawaz, and P. Varaiya. Supervisory control of discrete-event processes with partial observations. IEEE Trans. on Automatic Control, 33(3):249--260, Mar. 1988.
• 9: E. W. Dijstra. Selected Writings on Computing, chapter The Mathematics Behind the Banker's Algorithm, pages 308--312. Springer-Verlag, 1982.
• 10: Eric Eide , Leigh Stoller , Tim Stack , Juliana Freire , Jay Lepreau, Integrated scientific workflow management for the Emulab network testbed, Proceedings of the Annual Technical Conference on USENIX'06 Annual Technical Conference, p.33-33, May 30-June 03, 2006, Boston, MA
• 11: K. Farkas, S. Iyer, V. Machiraju, J. Pruyne, and A. Sahai. Automated provisioning of shared services. In Proceedings of the 10th IFIP/IEEE Symposium on Integrated Management, May 2007.
• 12: Joseph L. Hellerstein , Yixin Diao , Sujay Parekh , Dawn M. Tilbury, Feedback Control of Computing Systems, John Wiley & Sons, 2004
• 13: jBPM. http://www.jboss.com/products/jbpm.
• 14: K. Keeton. Personal communication.
• 15: Kimberly Keeton , Dirk Beyer , Ernesto Brau , Arif Merchant , Cipriano Santos , Alex Zhang, On the road to recovery: restoring data after disasters, Proceedings of the ACM SIGOPS/EuroSys European Conference on Computer Systems 2006, April 18-21, 2006, Leuven, Belgium
• 16: E. Kiciman and L. Subramanian. A root cause localization model for large scale systems. In HotDep, June 2005.
• 17: B. Kiepuszewski, A. ter Hofstede, and W. van der Aalst. Fundamentals of control flow in workflows. Acta Informatica, 39(3):143--209, 2003.
• 18: C. Killian, J. Anderson, R. Jhala, and A. Vahdat. Life, death, and the critical transition: Finding liveness bugs in systems code. Technical report, UC San Diego, 2006. http://mace.ucsd.edu/papers/MaceMC_TR.pdf.
• 19: F. Lin , W. M. Wonham, On observability of discrete-event systems, Information Sciences: an International Journal, v.44 n.3, p.173-198, April, 1988 [doi>10.1016/0020-0255(88)90001-1]
• 20: H. Marchand and S. Pinchinat. Supervisory control problem using symbolic bisimulation techniques. In American Control Conference, pages 4067--4071, June 2000.
• 21: J. Mendling, M. Moser, G. Neumann, H. Verbeek, B. van Dongen, and W. van der Aalst. A quantitative analysis of faulty EPCs in the SAP reference model. Technical Report BPM-06-08, Business Process Management Center, 2006. http://is.tm.tue.nl/staff/wvdaalst/BPMcenter/reports/2006/BPM-06-08.pdf%.
• 22: T. Murata. Petri nets: Properties, analysis and applications. Proceedings of the IEEE, 77(4):541--580, Apr. 1989.
• 23: Kiran Nagaraja , Fábio Oliveira , Ricardo Bianchini , Richard P. Martin , Thu D. Nguyen, Understanding and dealing with operator mistakes in internet services, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.5-5, December 06-08, 2004, San Francisco, CA
• 24: David Oppenheimer , Archana Ganapathi , David A. Patterson, Why do internet services fail, and what can be done about it?, Proceedings of the 4th conference on USENIX Symposium on Internet Technologies and Systems, p.1-1, March 26-28, 2003, Seattle, WA
• 25: Oracle BPEL workflows. http://www.oracle.com/technology/products/ias/bpel/.
• 26: C. Ouyang, E. Verbeek, W. M. P. van der Aalst, S. Breutel, M. Dumas, and A. H. M. ter Hofstede. Wofbpel: A tool for automated analysis of BPL processes. In ICSOC, pages 484--489, Dec. 2005.
• 27: Feng Qin , Joseph Tucek , Jagadeesan Sundaresan , Yuanyuan Zhou, Rx: treating bugs as allergies---a safe method to survive software failures, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom
• 28: P. J. Ramadge , W. M. Wonham, Supervisory control of a class of discrete event processes, SIAM Journal on Control and Optimization, v.25 n.1, p.206-230, Jan. 1987 [doi>10.1137/0325013]
• 29: Martin Rinard , Cristian Cadar , Daniel Dumitran , Daniel M. Roy , Tudor Leu , William S. Beebee, Jr., Enhancing server availability and security through failure-oblivious computing, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.21-21, December 06-08, 2004, San Francisco, CA
• 30: M. Sampath. A hybrid approach to failure diagnosis of industrial systems. In American Control Conference, pages 2077--2082, June 2001.
• 31: M. Sampath, R. Sengupta, K. S. S. Lafortune, and D. Teneketzis. Diagnosability of discrete event systems. IEEE Trans. on Automatic Control, 40(9):1555--1575, Sept. 1995.
• 32: Secure programming lint. http://wwww.splint.org/.
• 33: Sun. WorkShop: Command-Line Utilities, chapter 24: Using Lock Lint. Sun Press, 2006. http://docs.sun.com/app/docs/doc/802-5763/.
• 34: Wil M.P. Van Der Aalst , Arthur H. M. Ter Hofstede, Verification of workflow task structures: A petri-net-based approach, Information Systems, v.25 n.1, p.43-69, Mar.1.2000 [doi>10.1016/S0306-4379(00)00008-9]
• 35: Yin Wang , Tae-Sic Yoo , Stéphane Lafortune, Diagnosis of Discrete Event Systems Using Decentralized Architectures, Discrete Event Dynamic Systems, v.17 n.2, p.233-263, June 2007 [doi>10.1007/s10626-006-0006-8]
• 36: W. M. Wonham and P. J. Ramadge. Modular supervisory control of discrete event systems. Mathematics of Control of Discrete Event Systems, 1(1):13--30, 1988.
• 37: Junfeng Yang , Paul Twohey , Dawson Engler , Madanlal Musuvathi, Using model checking to find serious file system errors, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.19-19, December 06-08, 2004, San Francisco, CA

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES

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

  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.1 Office Automation
          Subjects: Workflow management

General Terms:
Management, Reliability

Keywords:
deadlock avoidance, discrete control, workflow