Enabling automatic adaptation in systems with under-specified elements

ABSTRACT

Software that people use for everyday purposes is usually not mission critical---some failures can be tolerated. However, this software should be dependable enough for its intended use, even when users change expectations. Software systems that could adapt to accommodate both failures and changing user expectations could significantly improve the dependability of such everyday software. Many adaptation techniques require specifications of proper behavior (for detecting improper behavior) and problem severity, alternatives and their selection (for mitigation and for repair).However, the specifications of everyday software are usually incomplete and imprecise. This makes it difficult to determine the dependability of the software and even more difficult to adapt.We address the problem of detecting anomalies---deviations from expected behavior---when specifications of expected behavior are missing. Setting up anomaly detection depends on human participation, yielding predicates that can serve as proxies for missing specifications.We propose a template mechanism to lower the demands on human attention when setting up detection. We show how this mechanism may be used in our framework for enhancing dynamic data feeds with automatic adaptation. We discuss how the same mechanism may be used in repair. Our emphasis is on detecting semantic anomalies: cases in which the data feed is responsive and delivers well-formed results, but these results are unreasonable.

REFERENCES

• 1: IBM. Autonomic Computing. URL: http://www.research.ibm.com/autonomic/overview/. Accessed November 2001.
• 2: IBM. eLiza: self-manging servers. URL: http://www-1.ibm.com/servers/eserver/introducing/eliza/. Accessed November 2001.
• 3: W3C. The Semantic Web, Activity. URL: http://www.w3.org/2001/sw/. Accessed November 2001.
• 4: Alexa browser enhancement. URL: http://www.alexa.com. Accessed April 2001.
• 5: Glenn Ammons , Rastislav Bodík , James R. Larus, Mining specifications, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.4-16, January 16-18, 2002, Portland, Oregon
• 6: Mathias Bauer , Dietmar Dengler, TrIAs: trainable information assistants for cooperative problem solving, Proceedings of the third annual conference on Autonomous Agents, p.260-267, April 1999, Seattle, Washington, United States [doi>10.1145/301136.301207]
• 7: William Dickinson , David Leon , Andy Podgurski, Finding failures by cluster analysis of execution profiles, Proceedings of the 23rd International Conference on Software Engineering, p.339-348, May 12-19, 2001, Toronto, Ontario, Canada
• 8: Stock quotes data source. URL: http://quote.pathfinder.com. Accessed September-November 2000.
• 9: Dawson Engler , David Yu Chen , Seth Hallem , Andy Chou , Benjamin Chelf, Bugs as deviant behavior: a general approach to inferring errors in systems code, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 10: Michael D. Ernst , Jake Cockrell , William G. Griswold , David Notkin, Dynamically Discovering Likely Program Invariants to Support Program Evolution, IEEE Transactions on Software Engineering, v.27 n.2, p.99-123, February 2001 [doi>10.1109/32.908957]
• 11: Google search engine (caching service). URL: http://www.google.com. Accessed April 2001.
• 12: Go!Zilla download manager. URL: http://www.gozilla.com. Accessed April 2001.
• 13: Rulequest. GritBot, autonomous data quality auditor. URL: http://www.rulequest.com/gritbot-info.html. Accessed January 2002.
• 14: Steven A. Hofmeyr , Stephanie A. Forrest, Architecture for an Artificial Immune System, Evolutionary Computation, v.8 n.4, p.443-473, December 2000 [doi>10.1162/106365600568257]
• 15: C. Knoblock, K. Lerman, S. Minton, and I. Muslea. Accurately and reliably extracting data from the web. In Data Engineering Bulletin, 1999.
• 16: Nicholas Kushmerick, Regression testing for wrapper maintenance, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.74-79, July 18-22, 1999, Orlando, Florida, United States
• 17: T. Lane and C. E. Brodley. Approaches to online learning and concept drift for user identifi cation in computer security. In KDD, 1998.
• 18: Pat Langley, The computational support of scientific discovery, International Journal of Human-Computer Studies, v.53 n.3, p.393-410, Sept. 2000 [doi>10.1006/ijhc.2000.0396]
• 19: Kristina Lerman , Steven Minton, Learning the Common Structure of Data, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.609-614, July 30-August 03, 2000
• 20: R. Mackey, M. James, H. Park, and M. Zak. BEAM: Technology for autonomous self-analysis. In Aerospace Conference, 2001.
• 21: Robert C. Miller , Brad A. Myers, Outlier finding: focusing user attention on possible errors, Proceedings of the 14th annual ACM symposium on User interface software and technology, November 11-14, 2001, Orlando, Florida [doi>10.1145/502348.502361]
• 22: Vijayshankar Raman , Joseph M. Hellerstein, Potter's Wheel: An Interactive Data Cleaning System, Proceedings of the 27th International Conference on Very Large Data Bases, p.381-390, September 11-14, 2001
• 23: Orna Raz , Philip Koopman , Mary Shaw, Semantic anomaly detection in online data sources, Proceedings of the 24th International Conference on Software Engineering, May 19-25, 2002, Orlando, Florida [doi>10.1145/581339.581378]
• 24: Orna Raz , Mary Shaw, An Approach to Preserving Sufficient Correctness in Open Resource Coalitions, Proceedings of the 10th International Workshop on Software Specification and Design, p.159, November 05-07, 2000
• 25: M. Shaw. Sufficient correctness and homeostasis in open resource coalitions. In ISAW, 2000.