Topes: reusable abstractions for validating data

ABSTRACT

Programmers often omit input validation when inputs can appear in many different formats or when validation criteria cannot be precisely specified. To enable validation in these situations, we present a new technique that puts valid inputs into a consistent format and that identifies "questionable" inputs which might be valid or invalid, so that these values can be double-checked by a person or a program. Our technique relies on the concept of a "tope", which is an application-independent abstraction describing how to recognize and transform values in a category of data. We present our definition of topes and describe a development environment that supports the implementation and use of topes. Experiments with web application and spreadsheet data indicate that using our technique improves the accuracy and reusability of validation code and also improves the effectiveness of subsequent data cleaning such as duplicate identification.

REFERENCES

• 1: Robert J. Adler , Raisa E. Feldman , Murad S. Taqqu, A practical guide to heavy tails: statistical techniques and applications, Birkhauser Boston Inc., Cambridge, MA, 1998
• 2: Allen, E. et. al. The Fortress Language Specification, Sun Microsystems, 2006.
• 3: Aslam, T., Krsul, I., and Spafford, E. Use of a Taxonomy of Security Faults. Tech. Rpt. TR-96-051, Purdue University, 1996.
• 4: Hersh Bhasin, Microsoft Asp.Net Professional Projects, Premier Press, 2002
• 5: Claus Brabrand , Anders Møller , Mikkel Ricky , Michael I. Schwartzbach, PowerForms: Declarative client-side form field validation, World Wide Web, v.3 n.4, p.205-214, December 2000 [doi>10.1023/A:1018772405468]
• 6: Margaret Burnett , Curtis Cook , Omkar Pendse , Gregg Rothermel , Jay Summet , Chris Wallace, End-user software engineering with assertions in the spreadsheet paradigm, Proceedings of the 25th International Conference on Software Engineering, May 03-10, 2003, Portland, Oregon
• 7: Soumen Chakrabarti, Mining the Web: Discovering Knowledge from HyperText Data, Science & Technology Books, 2002
• 8: Michael J. Coblenz , Andrew J. Ko , Brad A. Myers, Using Objects of Measurement to Detect Spreadsheet Errors, Proceedings of the 2005 IEEE Symposium on Visual Languages and Human-Centric Computing, p.314-316, September 20-24, 2005 [doi>10.1109/VLHCC.2005.67]
• 9: Martin Erwig , Margaret M. Burnett, Adding Apples and Oranges, Proceedings of the 4th International Symposium on Practical Aspects of Declarative Languages, p.173-191, January 19-20, 2002
• 10: Fisher II, M., and Rothermel, G. The EUSES Spreadsheet Corpus: A Shared Resource for Supporting Experimentation with Spreadsheet Dependability Mechanisms. Tech. Rpt. 04-12-03, University of Nebraska?Lincoln, 2004.
• 11: David Flanagan, JavaScript: The Definitive Guide, O'Reilly Media, Inc., 2006
• 12: Maria Jean Johnstone Hall, A Risk and Control Oriented Study of the Practices of Spreadsheet Application Developers, Proceedings of the 29th Hawaii International Conference on System Sciences (HICSS) Volume 2: Decision Support and Knowledge-Based Systems, p.364, January 03-06, 1996
• 13: Michael Hanus, Type-oriented construction of web user interfaces, Proceedings of the 8th ACM SIGPLAN international conference on Principles and practice of declarative programming, July 10-12, 2006, Venice, Italy [doi>10.1145/1140335.1140341]
• 14: Michael Howard , David LeBlanc , John Viega, 19 Deadly Sins of Software Security, McGraw-Hill Osborne Media, 2005
• 15: Kennedy, A. Programming Languages and Dimensions. PhD thesis, Tech. Rpt. 391, University of Cambridge, 1996.
• 16: Marsh, E., and Perzanowski, D. MUC-7 Evaluation of IE Technology: Overview of Results. 7th Message Understanding Conf., 2001.
• 17: Robert C. Miller , Brad A. Myers, Lightweight structured text processing, Proceedings of the annual conference on USENIX Annual Technical Conference, p.10-10, June 06-11, 1999, Monterey, California
• 18: Bonnie A. Nardi , James R. Miller , David J. Wright, Collaborative, programmable intelligent agents, Communications of the ACM, v.41 n.3, p.96-104, March 1998 [doi>10.1145/272287.272331]
• 19: Raymond R. Panko, What we know about spreadsheet errors, Journal of End User Computing, v.10 n.2, p.15-21, Spring 1998
• 20: Benjamin C. Pierce, Types and programming languages, MIT Press, Cambridge, MA, 2002
• 21: Plasmeijer, R., and Achten, P. The Implementation of iData?A Case Study in Generic Programming. Tech Rpt. TCD-CS-2005-60, Dublin University, 2005.
• 22: Porter, M. An Algorithm for Suffix Stripping. Program, 14, 3 (July 1980), 130--137.
• 23: Rahm, E., and Do, H. Data Cleaning: Problems and Current Approaches. IEEE Data Eng. Bulletin, 23, 4 (Dec. 2000), 3--13.
• 24: 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
• 25: 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]
• 26: Jochen Rode , Mary Beth Rosson , Manuel A. Perez-Quinones, Web application development by nonprogrammers: user-centered design of an end-user web development tool, Virginia Polytechnic Institute & State University, Blacksburg, VA, 2005
• 27: Karen J. Rothermel , Curtis R. Cook , Margaret M. Burnett , Justin Schonfeld , T. R. G. Green , Gregg Rothermel, WYSIWYT testing in the spreadsheet paradigm: an empirical evaluation, Proceedings of the 22nd international conference on Software engineering, p.230-239, June 04-11, 2000, Limerick, Ireland [doi>10.1145/337180.337206]
• 28: Scaffidi, C. Unsupervised Inference of Data Formats in Human-Readable Notation. Proc. 9th Intl. Conf. Enterprise Integration Systems ? HCI Volume, 2007, 236--241.
• 29: Scaffidi, C., Shaw, M. Accommodating Data Heterogeneity in ULS Systems. 2nd Intl. Workshop on Ultra-Large-Scale Software-Intensive Systems, at the 30th Intl. Conf. Software Engineering, to appear.
• 30: Scaffidi, C., Myers, B., and Shaw, M. Challenges, Motivations, and Success Factors in the Creation of Hurricane Katrina "Person Locator" Web Sites. Psychology of Programming Interest Group Workshop, 2006.
• 31: Scaffidi, C., Myers, B., and Shaw, M. The Topes Format Editor and Parser. Tech Rpt. CMU-ISRI-07-104, Carnegie Mellon University, 2007.
• 32: Christopher Scaffidi , Brad Myers , Mary Shaw, Toped: enabling end-user programmers to validate data, CHI '08 extended abstracts on Human factors in computing systems, April 05-10, 2008, Florence, Italy [doi>10.1145/1358628.1358884]
• 33: Christopher Scaffidi , Mary Shaw , Brad Myers, Estimating the Numbers of End Users and End User Programmers, Proceedings of the 2005 IEEE Symposium on Visual Languages and Human-Centric Computing, p.207-214, September 20-24, 2005 [doi>10.1109/VLHCC.2005.34]
• 34: Scaffidi, C., Shaw, M., and Myers, B. Games Programs Play: Obstacles to Data Reuse, 2nd Workshop on End User Soft. Eng, 2006.
• 35: M. Shaw, Larger scale systems require higher-level abstractions, Proceedings of the 5th international workshop on Software specification and design, p.143-146, April 1989, Pittsburgh, Pennsylvania, United States
• 36: Zadeh, L. Fuzzy Logic. Tech Rpt. CSLI-88-116, Stanford University, 1988.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Input/output

General Terms:
Languages, Reliability

Keywords:
abstraction, data, validation