nach oben

Automated Software Engineering

Erschienen in:

01.03.2016

Model-based diagnosis of spreadsheet programs: a constraint-based debugging approach

verfasst von: Dietmar Jannach, Thomas Schmitz

Erschienen in: Automated Software Engineering | Ausgabe 1/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Spreadsheet programs are probably the most successful example of end-user software development tools and are used for a variety of purposes. Like any type of software, they are prone to error, in particular as they are usually developed by non-programmers. While various techniques exist to support the developer in finding errors in procedural programs, the tool support for spreadsheet debugging is still limited. In this paper, we show how techniques from model-based diagnosis can be applied and extended for spreadsheet debugging by translating the relevant parts of a spreadsheet to a constraint satisfaction problem. We additionally propose both problem-specific and generalizable extensions to the classical diagnosis algorithms which help to detect potential problems in a spreadsheet based on user-provided test cases more efficiently. The proposed techniques were integrated into a modular framework for spreadsheet debugging and evaluated with respect to scalability based on a number of real-world and artificially created spreadsheets. An additional error detection exercise involving 24 subjects was performed to assess the general applicability of such advanced spreadsheet debugging techniques for end users.

Vorheriger Artikel Differential precondition checking: a language-independent, reusable analysis for refactoring engines

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Nur mit Berechtigung zugänglich

In the following, we will use the terms “spreadsheet”, “spreadsheet program” and “spreadsheet application” interchangeably as done in the literature.

http://www.eusprig.org/horror-stories.htm, last accessed November 2013.

The second option has its limitations because the non-existence of formal processes is probably one of the reasons for the success of spreadsheets in the first place.

When a component is considered to be faulty, we assume that it can produce an arbitrary output within the range of generally possible values.

In this paper we use the terms “diagnosis candidates” and “diagnoses” interchangeably.

An algorithm for the treatment of multiple test cases during diagnosis is given in Felfernig et al. (2004).

Alternatively, the user could have restricted the domain size of variable C1.

The correct formulas in the figures are only used to better illustrate the problem setting.

In the formalization of MBD and CSP concepts, we will rely on the notations and terms used, e.g., in Reiter (1987) or Felfernig et al. (2004), to illustrate the correspondence of our approach with previous works.

The detection of faults which are caused by semantic errors or wrong domain definitions are beyond the scope of this work.

See later sections for a further discussion of the problem of domain definitions.

In the literature, a number of formalizations for spreadsheets are proposed, e.g., in Abraham and Erwig (2006a) or Abraham and Erwig (2007), and some of them provide their own grammar for expressions or detailed mapping rules to a different representation (Abreu et al. 2012; Hofer et al. 2013). Since the specific mapping of the spreadsheet formulas to the CSP representation is not relevant for the subsequently described pruning approach, we will introduce a simple notation that focuses only on the relevant cell dependencies.

There also might be a wrong formula in D1 but this one will be independent of the other error and can only be identified through another test case.

The set of input cells that should be considered by the debugging to be potentially faulty could be determined interactively by the spreadsheet developer.

A discussion of the computational complexity of QuickXplain can be found in Junker (2004).

Usual depth limitations could be applied here.

We omitted these calls in Algorithm 1 for better readability.

Some redundant calculations of conflicts can however in theory occur depending on how the threads are scheduled.

We also made experiments in which we limited the thread-pool size to 1, thereby imitating a non-parallelized approach, leading to similar results. The additional overheads related to the creation of threads appear to be neglectable.

http://www.emn.fr/z-info/choco-solver/

Intel Core i7-3770K, 3.5 GHz, 16GB RAM, 8 hardware threads.

This is about twice the time needed for the single fault problem reported in Fig. 9.

We conducted the experiment in German and all material used in the study was prepared in German. Here the English translation is shown.

The value 1 corresponds to “never”; 5 means “very often”.

We made additional measurements regarding the time needed by the subjects to study the description of the intended semantics or go through the Exquisite tutorial. A detailed analysis of possible correlations of these measurements with the error-detection performance is however beyond the scope of this paper.

We encouraged the participants to comment on their strategies during the experiment in the sense of a think-aloud protocol.

Other types of errors could be semantic or structural errors.

Available at http://www.cril.univ-artois.fr/CPAI08/

Abraham, R., Erwig, M.: AutoTest: a tool for automatic test case generation in spreadsheets. In: Proceedings of the IEEE Symposium on Visual Languages and Human-Centric Computing (VL/HCC 2006), Brighton, United Kingdom, pp. 43–50 (2006)

Abraham, R., Erwig, M.: Inferring templates from spreadsheets. In: Proceedings of the 28th International Conference on Software Engineering (ICSE 2006), Shanghai, China, pp. 182–191 (2006)

Abraham, R., Erwig, M.: GoalDebug: a spreadsheet debugger for end users. In: Proceedings of the 29th International Conference on Software Engineering (ICSE 2007), Minneapolis, MN, USA, pp. 251–260 (2007)

Abraham, R., Erwig, M.: Mutation operators for spreadsheets. IEEE Trans. Softw. Eng. 35(1), 94–108 (2009)CrossRef

Abreu, R., Zoeteweij, P., van Gemund, A.J.C.: An observation-based model for fault localization. In: Proceedings of the 6th International Workshop on Dynamic Analysis (WODA 2008), New York, NY, USA, pp. 64–70 (2008)

Abreu, R., Riboira, A., Wotawa, F.: Constraint-based debugging of spreadsheets. In: Proceedings of the 15th Ibero-American Conference on Software Engineering (CIbSE 2012), Buenos Aires, Argentina, pp. 1–14 (2012)

Asavametha, A.: Detecting bad smells in spreadsheets. Master’s thesis, School of Electrical Engineering and Computer Science, Oregon State University, USA (2012)

Brown, P.S., Gould, J.D.: An experimental study of people creating spreadsheets. ACM Trans. Inf. Syst. 5(3), 258–272 (1987)CrossRef

Burnett, M., Sheretov, A., Ren, B., Rothermel, G.: Testing homogeneous spreadsheet grids with the “what you see Is what you test” methodology. IEEE Trans. Softw. Eng. 28(6), 576–594 (2002)CrossRef

Burnett, M., Cook, C., Pendse, O., Rothermel, G., Summet, J., Wallace, C.: End-user software engineering with assertions in the spreadsheet paradigm. In: Proceedings of the 25th International Conference on Software Engineering (ICSE 2003), Portland, Oregon, pp. 93–103 (2003)

Campos, J., Riboira, A., Perez, A., Abreu, R.: Gzoltar: an eclipse plug-in for testing and debugging. In: Proceedings of the 27th IEEE/ACM International Conference on Automated Software Engineering (ASE 2012), Essen, Germany, pp. 378–381 (2012)

Chadwick, D., Knight, B., Rajalingham, K.: Quality control in spreadsheets: a visual approach using color codings to reduce errors in formulae. Softw. Qual. Control 9(2), 133–143 (2001)CrossRef

Chittaro, L., Ranon, R.: Hierarchical model-based diagnosis based on structural abstraction. Artif. Intell. 155(1–2), 147–182 (2004)MATHMathSciNetCrossRef

Console, L., Friedrich, G., Dupré, D.T.: Model-based diagnosis meets error diagnosis in logic programs. In: Proceedings of the 13th International Joiunt Conference on Artificial Intelligence (IJCAI 1993), Chambéry, France, pp. 1494–1499 (1993)

Creeth, R.: Micro-computer spreadsheets: their uses and abuses. J. Account. 159(6), 90–93 (1985)

Cunha, J., Fernandes, JaP., Ribeiro, H., Saraiva, Ja.: Towards a catalog of spreadsheet smells. In: Proceedings of the 12th International Conference on Computational Science and Its Applications (ICCSA 2012), Salvador de Bahia, Brazil, pp. 202–216 (2012)

de Kleer, J.: Using crude probability estimates to guide diagnosis. Artif. Intell. 45(3), 381–391 (1990)CrossRef

de Kleer, J., Williams, B.C.: Diagnosing multiple faults. Artif. Intell. 32(1), 97–130 (1987)MATHCrossRef

Ditlea, S.: Spreadsheets can be hazardous to your health. Pers. Comput. 11(1), 60–69 (1987)

Felfernig, A., Schubert, M.: FastDiag: a diagnosis algorithm for inconsistent constraint sets. In: Proceedings of the 21st International Workshop on the Principles of Diagnosis (DX 2010), Portland, OR, USA, pp. 31–38 (2010)

Felfernig, A., Friedrich, G., Jannach, D., Stumptner, M., Zanker, M.: Hierarchical diagnosis of large configurator knowledge bases. In: Proceedings of the Joint German/Austrian Conference on Artificial Intelligence (KI 2001), Vienna, Austria, pp. 185–197 (2001)

Felfernig, A., Friedrich, G., Jannach, D., Stumptner, M.: Consistency-based diagnosis of configuration knowledge bases. Artif. Intell. 152(2), 213–234 (2004)MATHMathSciNetCrossRef

Filby, G. (ed.): Spreadsheets in Science and Engineering. Springer, Berlin (1998)

Freuder, E.C., Wallace, R.J., Heffernan, R.: Partial constraint satisfaction. Artif. Intell. 58(1–3), 278–283 (1992)

Friedrich, G., Nejdl, W.: Choosing observations and actions in model-based diagnosis/repair systems. In: Proceedings of the 3rd International Conference on Principles of Knowledge Representation and Reasoning (KR 1992), Cambridge, MA, USA, pp. 489–498 (1992)

Friedrich, G., Stumptner, M., Wotawa, F.: Model-based diagnosis of hardware designs. Artif. Intell. 111(1–2), 3–39 (1999)MATHMathSciNetCrossRef

Galletta, D.F., Abraham, D., Louadi, M.E., Lekse, W., Pollalis, Y.A., Sampler, J.L.: An empirical study of spreadsheet error-finding performance. Account. Manag. Inf. Technol. 3(2), 79–95 (1993)CrossRef

Greiner, R., Smith, B.A., Wilkerson, R.W.: A correction to the algorithm in Reiter’s theory of diagnosis. Artif. Intell. 41(1), 79–88 (1989)MATHMathSciNetCrossRef

Hermans, F.: Improving spreadsheet test practices. In: Proceedings of the 23rd Annual International Conference on Computer Science and Software Engineering (CASCON 2013), Markham, Ontario, Canada, pp. 56–69 (2013)

Hermans, F., Pinzger, M., van Deursen, A.: Detecting and visualizing inter-worksheet smells in spreadsheets. In: Proceedings of the 34th International Conference on Software Engineering (ICSE 2012), Zurich, Switzerland, pp. 441–451 (2012)

Hermans, F., Pinzger, M., van Deursen, A.: Detecting code smells in spreadsheet formulas. In: Proceedings of the 28th IEEE International Conference on Software Maintenance (ICSM 2012), pp. 409–418. Trento, Riva del Garda (2012)

Herndon, T., Ash, M., Pollin, R.: Does high public debt consistently stifle economic growth? A critique of Reinhart and Rogoff. Working paper 322, Political Economy Research Institute, University of Massachusetts, Amherst (2013)

Hofer, B., Riboira, A., Wotawa, F., Abreu, R., Getzner, E.: On the empirical evaluation of fault localization techniques for spreadsheets. In: Proceedings of the 16th International Conference on Fundamental Approaches to Software Engineering (FASE 2013), Rome, Italy, pp. 68–82 (2013)

Jannach, D., Engler, U.: Toward model-based debugging of spreadsheet programs. In: Proceedings of the 9th Joint Conference on Knowledge-Based Software Engineering (JCKBSE 2010), Kaunas, Lithuania, pp. 252–264 (2010)

Jannach, D., Baharloo, A., Williamson, D.: Toward an integrated framework for declarative and interactive spreadsheet debugging. In: Procedings of the 8th International Conference on Evaluation of Novel Approaches to Software Engineering (ENASE 2013), Angers, France, pp. 117–124 (2013)

Jones, J.A., Harrold, M.J., Stasko, J.: Visualization of test information to assist fault localization. In: Proceedings of the 24th International Conference on Software Engineering (ICSE 2002), Orlando, FL, USA, pp. 467–477 (2002)

Junker, U.: QUICKXPLAIN: preferred explanations and relaxations for over-constrained problems. In: Proceedings of the 19th National Conference on Artificial Intelligence (AAAI 2004), San Jose, CA, USA, pp. 167–172 (2004)

Larrosa, J., Meseguer, P., Schiex, T.: Maintaining reversible DAC for Max-CSP. Artif. Intell. 107(1), 149–163 (1999)

Mateis, C., Stumptner, M., Wieland, D., Wotawa, F.: Model-based debugging of Java Programs. In: Proceedings of the Fourth International Workshop on Automated Debugging (AADEBUG 2000), Munich, Germany (2000)

Metodi, A., Stern, R., Kalech, M., Codish, M.: Compiling model-based diagnosis to Boolean satisfaction. In: Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI 2012), Toronto, Canada (2012)

Panko, R.R.: What we know about spreadsheet errors. J. End User Comput. 10(2), 15–21 (1998)CrossRef

Panko, R.R., Halverson, R.P.: Spreadsheets on trial: a survey of research on spreadsheet risks. In: Proceedings of the 29th Hawaii International Conference on System Sciences (HICSS 1996), Wailea, HI, USA, pp. 326–335 (1996)

Panko, R.R., Port, D.N.: End user computing: the dark matter (and dark energy) of corporate IT. In: Proceedings of the 45th Hawaii International Conference on System Sciences (HICSS 2012), Wailea, HI, USA, pp. 4603–4612 (2012)

Parnin, C., Orso, A.: Are automated debugging techniques actually helping programmers?. In: Proceedings of the 2011 International Symposium on Software Testing and Analysis (ISSTA 2011), Toronto, Canada, pp. 199–209 (2011)

Pemberton, J., Robson, A.: Spreadsheets in business. Ind. Manag. Data Syst. 100(8), 379–388 (2000)CrossRef

Powell, S.G., Baker, K.R., Lawson, B.: A critical review of the literature on spreadsheet errors. Decis. Support Syst. 46(1), 128–138 (2008)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), Austin, Texas, pp. 25–38 (1999)

Reinhart, C.M., Rogoff, K.S.: Growth in a time of debt. Am. Econ. Rev. 100(2), 573–578 (2010)CrossRef

Reiter, R.: A theory of diagnosis from first principles. Artif. Intell. 32(1), 57–95 (1987)MATHMathSciNetCrossRef

Rothermel, G., Li, L., Dupuis, C., Burnett, M.: What you see is what you test: a methodology for testing form-based visual programs. In: Proceedings of the 20th International Conference on Software Engineering (ICSE 1998), Kyoto, Japan, pp. 198–207 (1998)

Shchekotykhin, K., Friedrich, G., Fleiss, P., Rodler, P.: Interactive ontology debugging: two query strategies for efficient fault localization. J. Web Semant. 12–13, 88–103 (2012)CrossRef

Smith, B.M.: Locating the phase transition in binary constraint satisfaction problems. Artif. Intell. 81, 155–181 (1994)CrossRef

Stumptner, M., Wotawa, F.: Model-based program debugging and repair. In: Proceedings of the 9th International Industrial and Engineering Applications of Artificial Intelligence and Expert Systems (IEA/AIE 1996), Fukuoka, Japan, pp. 155–160 (1996)

Stumptner, M., Wotawa, F.: Debugging functional programs. In: Proceedings of the 16th International Joint Conference on Artificial Intelligence (IJCAI 1999), Stockholm, Sweden, pp. 1074–1079 (1999)

Stumptner, M., Wotawa, F.: Diagnosing tree-structured systems. Artif. Intell. 127(1), 1–29 (2001)MATHMathSciNetCrossRef

Tsang, E.: Foundations of Constraint Satisfaction. Academic Press, London (1993)

Wotawa, F., Pill, I.: On classification and modeling issues in distributed model-based diagnosis. AI Commun. 26(1), 133–143 (2013)MathSciNet

Wotawa, F., Weber, J.: Challenges of distributed model-based diagnosis. In: Trends in Applied Intelligent Systems, Springer, Lecture Notes in Computer Science, pp. 711–720 (2010)

Titel: Model-based diagnosis of spreadsheet programs: a constraint-based debugging approach
verfasst von: Dietmar Jannach
Thomas Schmitz
Publikationsdatum: 01.03.2016
Verlag: Springer US
Erschienen in: Automated Software Engineering / Ausgabe 1/2016
Print ISSN: 0928-8910
Elektronische ISSN: 1573-7535
DOI: https://doi.org/10.1007/s10515-014-0141-7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2016

Diversity maximization speedup for localizing faults in single-fault and multi-fault programs

Ahead of time static analysis for automatic generation of debugging interfaces to the Linux kernel

Editorial introduction

Differential precondition checking: a language-independent, reusable analysis for refactoring engines

Premium Partner