Semantic anomaly detection in online data sources

ABSTRACT

Much of the software we use for everyday purposes incorporates elements developed and maintained by someone other than the developer. These elements include not only code and databases but also dynamic data feeds from online data sources. Although everyday software is not mission critical, it must be dependable enough for practical use. This is limited by the dependability of the incorporated elements.It is particularly difficult to evaluate the dependability of dynamic data feeds, because they may be changed by their proprietors as they are used. Further, the specifications of these data feeds are often even sketchier than the specifications of software components.We demonstrate a method of inferring invariants about the normal behavior of dynamic data feeds. We use these invariants as proxies for specifications to perform on-going detection of anomalies in the data feed. We show the feasibility of our approach and demonstrate its usefulness for semantic anomaly detection: identifying occasions when a dynamic data feed is delivering unreasonable values, even though its behavior may be superficially acceptable (i.e., it is delivering parsable results in a timely fashion).

REFERENCES

• 1: Alexa browser enhancement. www.alexa.com. Accessed April 2001.
• 2: 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]
• 3: Christopher M. Bishop, Neural networks for pattern recognition, Oxford University Press, Oxford, 1996
• 4: Stock quotes data source. finance.northernlight.com. Accessed September-November 2000.
• 5: Stock quotes data source. qs2.cnnfn.com. Accessed September-November 2000.
• 6: Stock quotes data source. quote.pathfinder.com. Accessed September-November 2000.
• 7: Michael Dean Ernst , David Notkin, Dynamically discovering likely program invariants, 2000
• 8: 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]
• 9: Google search engine. www.google.com. Accessed April 2001.
• 10: Go!Zilla download manager. www.gozilla.com. Accessed April 2001.
• 11: GritBot. http://www.rulequest.com/gritbot-info.html. Accessed January 2002.
• 12: Geoff Hulten , Laurie Spencer , Pedro Domingos, Mining time-changing data streams, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.97-106, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502529]
• 13: Kangaroo. www.kangaroonet.com. Accessed August 2001.
• 14: C. Knoblock, K. Lerman, S. Minton, and I. Muslea. Accurately and reliably extracting data from the web: A machine learning approach. In Data Engineering Bulletin, 1999.
• 15: 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
• 16: Terran Lane , Carla E. Brodley, Temporal sequence learning and data reduction for anomaly detection, ACM Transactions on Information and System Security (TISSEC), v.2 n.3, p.295-331, Aug. 1999 [doi>10.1145/322510.322526]
• 17: J.C. C. Laprie , A. Avizienis , H. Kopetz, Dependability: Basic Concepts and Terminology, Springer-Verlag New York, Inc., Secaucus, NJ, 1992
• 18: 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
• 19: Marti A. Hearst, Information Integration, IEEE Intelligent Systems, v.13 n.5, p.12-24, September 1998 [doi>10.1109/5254.722342]
• 20: Alon Y. Levy , Anand Rajaraman , Joann J. Ordille, Querying Heterogeneous Information Sources Using Source Descriptions, Proceedings of the 22th International Conference on Very Large Data Bases, p.251-262, September 03-06, 1996
• 21: Michael R. Lyu, Handbook of software reliability and system reliability, McGraw-Hill, Inc., Hightstown, NJ, 1996
• 22: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 23: 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
• 24: O. Raz and M. Shaw. Software risk management and insurance. Position paper. In 3rd Workshop on Economics-Driven Software Engineering Research, 2001.
• 25: Dow Jones average collapses to 0.20. TheRegister, March 19 2001. www.theregister.co.uk/content/28/17700.html.
• 26: Per Runeson , Magnus C. Ohlsson , Claes Wohlin, A Classification Scheme for Studies on Fault-Prone Components, Proceedings of the Third International Conference on Product Focused Software Process Improvement, p.341-355, September 10-13, 2001
• 27: Torres Wilfredo, Software Fault Tolerance: A Tutorial, NASA Langley Technical Report Server, 2000
• 28: XML 1.0, W3C recommendation. w3c.org, http://www.w3.org/TR/2000/REC-xml-20001006. Accessed Nov. 2001.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Internet (e.g., TCP/IP)

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Web-based services

General Terms:
Algorithms, Design, Performance