Top

Software Quality Journal

Published in:

01-06-2015

Using constraints to diagnose faulty spreadsheets

Authors: Rui Abreu, Birgit Hofer, Alexandre Perez, Franz Wotawa

Published in: Software Quality Journal | Issue 2/2015

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Spreadsheets can be viewed as a highly flexible programming environment for end users. Spreadsheets are widely adopted for decision making and may have a serious economical impact for the business. However, spreadsheets are staggeringly prone to errors. Hence, approaches for aiding the process of pinpointing the faulty cells in a spreadsheet are of great value. We present a constraint-based approach, ConBug, for debugging spreadsheets. The approach takes as input a (faulty) spreadsheet and a test case that reveals the fault and computes a set of diagnosis candidates for the debugging problem. Therefore, we convert the spreadsheet and a test case to a constraint satisfaction problem. We perform an empirical evaluation with 78 spreadsheets from different sources, where we demonstrate that our approach is light-weight and efficient. From our experimental results, we conclude that ConBug helps end users to pinpoint faulty cells.

previous article Reducing software defects removal cost via design of experiments using Taguchi approach

next article Prioritizing code-smells correction tasks using chemical reaction optimization

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

http://office.microsoft.com/en-gb/excel/.

http://www.apple.com/iwork/numbers/.

http://www.openoffice.org/product/calc.html.

We are aware that there exist different types of spreadsheet usage scenarios: quickly written calculations and spreadsheets carefully written for long-term use. The first type often contains careless mistakes that can be easily detected with the help of pattern identification mechanisms that are already implemented in most of the available spreadsheet tools. The second spreadsheet type often contains faults that are difficult to detect and localize. In this paper, we therefore focus on the localization of the latter one.

http://www.wiscnews.com/baraboonewsrepublic/news/local/article_7672b6c6-22d5-11e1-8398-001871e3ce6c.html.

In principle, other domains like real numbers are possible. For the sake of clarity, we restrict the domains to Integer and Boolean in this paper. This is not a general limitation of the approach.

Boolean values are interpreted as 1 if set to true. Otherwise they are interpreted as 0.

Known as iterative calculations; see http://office.microsoft.com/en-us/excel-help/remove-or-allow-a-circular-reference-HP010066243.aspx.

https://dl.dropbox.com/u/38372651/Spreadsheets/Integer_Spreadsheets.zip.

Abraham, R., & Erwig, M. (2004). Header and unit inference for spreadsheets through spatial analyses. In Proceedings of the 2004 IEEE symposium on visual languages—human centric computing, VLHCC ’04, (pp. 165–172). IEEE Computer Society, Washington, DC, USA. doi:10.1109/VLHCC.2004.29.

Abraham, R., & Erwig, M. (2007). Goaldebug: A spreadsheet debugger for end users. In Proceedings of the 29th international conference on software engineering, ICSE ’07, (pp. 251–260). IEEE Computer Society, Washington, DC, USA (2007). doi:10.1109/ICSE.2007.39.

Abraham, R., & Erwig, M. (2007). Ucheck: A spreadsheet type checker for end users. Journal of Visual Languages and Computing, 18, 71–95. doi:10.1016/j.jvlc.2006.06.001.CrossRef

Abraham, R., & Erwig, M. (2009). Mutation operators for spreadsheets. IEEE Transactions on Software Engineering, 35(1), 94–108. doi:10.1109/TSE.2008.73

Abraham, R., & Erwig, M. (2013). Personal, communication.

Abreu, R., Mayer, W., Stumptner, M., & van Gemund, A. J. C. (2009). Refining spectrum-based fault localization rankings. In Proceedings of the 2009 ACM symposium on applied computing, SAC ’09, (pp. 409–414). ACM, New York, NY, USA. doi:10.1145/1529282.1529374.

Abreu, R., Riboira, A., & Wotawa, F. (2012a). Constraint-based debugging of spreadsheets. In Ibero-American conference on software engineering (CibSE’12), (pp. 1–14).

Abreu, R., Riboira, A., & Wotawa, F. (2012b). Debugging of spreadsheets: A CSP-based approach. In Third IEEE international workshop on program debugging.

Abreu, R., Zoeteweij, P., & van Gemund, A. J. C.: On the accuracy of spectrum-based fault localization. In Proceedings of the testing: Academic and industrial conference practice and research techniques—MUTATION, TAICPART-MUTATION ’07, (pp. 89–98). IEEE Computer Society, Washington, DC, USA. http://dl.acm.org/citation.cfm?id=1308173.1308264

Abreu, R., Zoeteweij, P., & Gemund, A. J. C. V. (2009) Spectrum-based multiple fault localization. In Proceedings of the 2009 IEEE/ACM international conference on automated software engineering, ASE ’09, (pp. 88–99). IEEE Computer Society, Washington, DC, USA. DOI:10.1109/ASE.2009.25.

Ahmad, Y., Antoniu, T., Goldwater, S., & Krishnamurthi, S. (2003). A type system for statically detecting spreadsheet errors. In 18th IEEE international conference on automated software engineering (ASE 2003), 6–10 October 2003, Montreal, Canada, pp. 174–183. IEEE Computer Society. http://csdl.computer.org/comp/proceedings/ase/2003/2035/00/20350174abs.htm

Ayalew, Y., & Mittermeir, R. (2003) Spreadsheet debugging. Building better business spreadsheets—from the ad-hoc to the quality-engineered. In Proceedings of EuSpRIG 2003, Dublin, Ireland, July 24th–25th 2003. pp. 67–79 (2003).

Ceballos, R., Gasca, R.M., & Borrego, D. (2005). Constraint satisfaction techniques for diagnosing errors in design by contract software. SIGSOFT Software Engineering Notes 31(2). doi:10.1145/1108768.1123070.

Chadwick, D., Knight, B., & Rajalingham, K. (2001). Quality control in spreadsheets: A visual approach using color codings to reduce errors in formulae. Software Quality Control, 9(2), 133–143. doi:10.1023/A:1016631003750.CrossRef

Collavizza, H., & Rueher, M.: Exploring different constraint-based modelings for program verification. In Proceedings of the 13th international conference on Principles and practice of constraint programming, CP’07, (pp. 49–63). Springer, Berlin, Heidelberg. http://dl.acm.org/citation.cfm?id=1771668.1771676

Cunha, J., Erwig, M., & Saraiva, J.: Automatically inferring classsheet models from spreadsheets. In Proceedings of the 2010 IEEE symposium on visual languages and human-centric Computing, VLHCC ’10, pp. 93–100. IEEE Computer Society, Washington, DC, USA. doi:10.1109/VLHCC.2010.22.

Fisher, M., Cao, M., Rothermel, G., Cook, C.R., & Burnett, M. M. (2002). Automated test case generation for spreadsheets. In Software engineering, 2002. ICSE 2002. Proceedings of the 24th international conference on, (pp. 141–151). IEEE (2002).

Fisher, M., & Rothermel, G. (2005). The EUSES spreadsheet corpus: A shared resource for supporting experimentation with spreadsheet dependability mechanisms. SIGSOFT Software Engineering Notes, 30(4), 1–5.CrossRef

Gent, I. P., Jefferson, C., & Miguel, I.: Minion: A fast, scalable, constraint solver. In Proceedings of the 2006 conference on ECAI 2006: 17th European conference on artificial intelligence August 29–September 1, 2006, Riva del Garda, Italy, pp. 98–102. IOS Press, Amsterdam, The Netherlands. http://dl.acm.org/citation.cfm?id=1567016.1567043.

Gotlieb, A., Botella, B., & Rueher, M.: Automatic test data generation using constraint solving techniques. In Proceedings of the 1998 ACM SIGSOFT international symposium on Software testing and analysis, ISSTA ’98, (pp. 53–62). ACM, New York, NY, USA. doi:10.1145/271771.271790.

Gotlieb, A., Botella, B., & Rueher, M. (2000) A clp framework for computing structural test data. In Proceedings of the First international conference on computational logic, CL ’00, pp. 399–413. Springer, London, UK (2000). http://dl.acm.org/citation.cfm?id=647482.728291

Hermans, F., Pinzger, M., & van Deursen, A. (2011). Supporting professional spreadsheet users by generating leveled dataflow diagrams. In Proceeding of the 33rd international conference on Software engineering, pp. 451–460. ACM.

Hermans, F., Sedee, B., Pinzger, M., van Deursen, A., Cheng, B., & Pohl, K. (2013). Data clone detection and visualization in spreadsheets. In Proceedings of the international conference on software engineering (ICSE). ACM, IEEE Computer Society (2013).

Hofer, B., Perez, A., Abreu, R., & Wotawa, F. (2014). On the empirical evaluation of similarity coefficients for spreadsheets fault localization. Automated Software Engineering, 1–28.

Hofer, B., Riboira, A., Wotawa, F., Abreu, R., & Getzner, E.: On the empirical evaluation of fault localization techniques for spreadsheets. In V. Cortellessa, D. Varró (eds.) Fundamental approaches to software engineering—16th international conference, FASE 2013, Held as part of the European joint conferences on theory and practice of software, ETAPS 2013, Lecture Notes in Computer Science, Vol. 7793, pp. 68–82. Springer (2013).

Jannach, D., & Engler, U. (2010). Toward model-based debugging of spreadsheet programs. In Proceedings of the 9th joint conference on knowledge-based software engineering, (pp. 252–264). JCKBSE’10 Lithuania: Kaunas.

Ko, A. J., Abraham, R., Beckwith, L., Blackwell, A., Burnett, M., Erwig, M., Scaffidi, C., Lawrance, J., Lieberman, H., Myers, B., Rosson, M. B., Rothermel, G., Shaw, M., Wiedenbeck, S. (2011). The state of the art in end-user software engineering. ACM Comput. Surv. 43(3), 21:1–21:44. doi:10.1145/1922649.1922658.

Mayer, W. (2007). Static and hybrid analysis in model-based debugging. Ph.D. thesis, School of Computer and Information Science, University of South Australia.

Nica, I., Pill, I., Quaritsch, T., & Wotawa, F. (2013). The route to success: A performance comparison of diagnosis algorithms. In: F. Rossi (ed.) IJCAI. IJCAI/AAAI (2013).

Nica, M., Nica, S., & Wotawa, F. (2012). On the use of mutations and testing for debugging. Software: Practice & Experience.CrossRef

Panko, R. R. (1999). Applying code inspection to spreadsheet testing. Journal of Management Information Systems, 16, 159–176.

Peischl, B., & Wotawa, F. (2006). Automated source-level error localization in hardware designs. IEEE Design Test of Computers, 23, 8–19. doi:10.1109/MDT.2006.5.CrossRef

Reichwein, J., Rothermel, G., & Burnett, M.: Slicing spreadsheets: An integrated methodology for spreadsheet testing and debugging. In Proceedings of the 2nd conference on domain-specific languages (DSL 1999), pp. 25–38. Austin, Texas.

Reiter, R. (1987). A theory of diagnosis from first principles. Artificial Intelligence, 32(1), 57–95.CrossRefMATHMathSciNet

Rothermel, K. J., Cook, C. R., Burnett, M. M., Schonfeld, J., Green, T. R. G., & Rothermel, G. (2000). WYSIWYT testing in the spreadsheet paradigm: An empirical evaluation. In Proceedings of the 22nd international conference on Software engineering, ICSE ’00, (pp. 230–239). ACM, New York, NY, USA. doi:10.1145/337180.337206.

Ruthruff, J., Creswick, E., Burnett, M., Cook, C., Prabhakararao, S., Fisher II, M., & Main, M. (2003). End-user software visualizations for fault localization. In Proceedings of the 2003 ACM symposium on software visualization, SoftVis ’03, (pp. 123–132). ACM, New York, NY, USA. doi:10.1145/774833.774851.

Ruthruff, J. R., Prabhakararao, S., Reichwein, J., Cook, C., Creswick, E., & Burnett, M. (2005). Interactive, visual fault localization support for end-user programmers. Journal of Visual Languages & Computing, 16(1–2), 3–40.CrossRef

Tukiainen, M.: Uncovering effects of programming paradigms: Errors in two spreadsheet systems. In: Proceedings of the PPIG’00, pp. 247–266 (2000).

Weimer, W., Nguyen, T., Le Goues, C., & Forrest, S. (2009). Automatically finding patches using genetic programming. In Proceedings of the 31st international conference on software engineering, ICSE ’09, (pp. 364–374). IEEE Computer Society, Washington, DC, USA. doi:10.1109/ICSE.2009.5070536.

Woods, S., & Yang, Q. (1998). Program understanding as constraint satisfaction: Representation and reasoning techniques. Automated Software Engineering, 5(2), 147–181. doi:10.1023/A:1008655230736.CrossRef

Wotawa, F., & Nica, M. (2008). On the compilation of programs into their equivalent constraint representation. Informatica Journal, 32, 359–371.MATH

Wotawa, F., Nica, M., & Moraru, I. D. (2012). Automated debugging based on a constraint model of the program and a test case. The journal of logic and algebraic programming, 81(4).

Wotawa, F., Weber, J., Nica, M., & Ceballos, R. (2010). On the complexity of program debugging using constraints for modeling the program’s syntax and semantics. In Proceedings of the current topics in artificial intelligence, and 13th conference on Spanish association for artificial intelligence, CAEPIA’09, pp. 22–31. Springer, Berlin, Heidelberg. http://dl.acm.org/citation.cfm?id=1893496.1893500

Title: Using constraints to diagnose faulty spreadsheets
Authors: Rui Abreu
Birgit Hofer
Alexandre Perez
Franz Wotawa
Publication date: 01-06-2015
Publisher: Springer US
Published in: Software Quality Journal / Issue 2/2015
Print ISSN: 0963-9314
Electronic ISSN: 1573-1367
DOI: https://doi.org/10.1007/s11219-014-9236-4

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Other articles of this Issue 2/2015

Reducing software defects removal cost via design of experiments using Taguchi approach

Prioritizing code-smells correction tasks using chemical reaction optimization

In this issue

A quality cost reduction model for large-scale software development

Predicting defective modules in different test phases

Exploring fault types, detection activities, and failure severity in an evolving safety-critical software system

Premium Partner