Provenance-enhanced Algorithmic Debugging
Resumo
Localizing defects in a faulty software is a notoriously difficult activity. Researchers proposed several techniques to help developers to locate defects. One of these techniques is Algorithmic Debugging, which consists on executing the defective program, building an execution tree with the subcomputations, asking questions to the developer about the correctness of some specific subcomputations, and pruning the search space according to the answers to those questions. However, depending on the complexity of the program, the number of questions can be high, increasing the duration of the debug session. In this work we propose DebugProv, an algorithmic debugging approach for Python programs that enhances the execution tree with provenance to reduce the number of necessary questions to locate the defect, and, consequently, reduce the duration of debug sessions. We evaluated our technique over different programs and found that it was able to reduce the number of questions in 25.26%, on average.
Referências
Hiralal Agrawal and Joseph R Horgan. 1990. Dynamic program slicing. ACM SIGPlan Notices 25, 6 (1990), 246--256.
Evyatar Av-Ron. 1984. Top-down diagnosis of Prolog programs. Master's thesis. Weizmann Institute of Science, Rehovot, Israel.
Rafael Caballero, Christian Hermanns, and Herbert Kuchen. 2007. Algorithmic debugging of Java programs. ENTCS 177 (2007), 75--89.
Rafael Caballero, Enrique Martin-Martin, Adrian Riesco, and Salvador Tamarit. 2014. EDD: A declarative debugger for sequential erlang programs. In TACAS. Springer Berlin Heidelberg, Berlin, Heidelberg, 581--586.
Rafael Caballero, Adrián Riesco, and Josep Silva. 2017. A survey of algorithmic debugging. CSUR 50, 4 (2017), 60.
Adriane Chapman and HV Jagadish. 2009. Why not?. In SIGMOD. ACM, Providence, RI, 523--534.
Zhifei Chen, Lin Chen, Yuming Zhou, Zhaogui Xu, William C Chu, and Baowen Xu. 2014. Dynamic slicing of Python programs. In COMPSAC. IEEE, Vasteras, Sweden, 219--228.
Richard A DeMillo, Richard J Lipton, and Frederick G Sayward. 1978. Hints on test data selection: Help for the practicing programmer. Computer 11, 4 (1978), 34--41.
Peter Fritzson, Nahid Shahmehri, Mariam Kamkar, and Tibor Gyimothy. 1992. Generalized algorithmic debugging and testing. LOPLAS 1, 4 (1992), 303--322.
Hani Z Girgis and Bharat Jayaraman. 2006. JavaDD: a declarative debugger for java. Technical Report. University at Buffalo, Department of Computer Science and Engineering.
Juan González, David Insa, and Josep Silva. 2013. A new hybrid debugging architecture for eclipse. In LOPSTR. Springer, Madrid, Spain, 183--201.
Alex Groce, Josie Holmes, Darko Marinov, August Shi, and Lingming Zhang. 2018. An extensible, regular-expression-based tool for multi-language mutant generation. In ICSE-Companion. IEEE, Gothenburg, Sweden, 25--28.
Christian Hermanns and Herbert Kuchen. 2011. Hybrid debugging of java programs. In ICSOFT. Springer, Seville, Spain, 91--107.
Matthew M Huntbach. 1987. Algorithmic PARLOG debugging. In Symposium on Logic Programming. IEEE, San Francisco, CA, 288--297.
David Insa and Josep Silva. 2010. An algorithmic debugger for Java. In ICSME. IEEE, Timisoara, Romania, 1--6.
Hoon-Joon Kouh and Weon-Hee Yoo. 2003. The efficient debugging system for locating logical errors in java programs. In ICCSA. Springer, Montreal, Canada, 684--693.
Arun Lakhotia and Leon Sterling. 1990. ProMiX: A Prolog partial evaluation system. In The Practice of Prolog. MIT Press, Cambridge, MA, 137--179.
Joseph Lawrance, Christopher Bogart, Margaret Burnett, Rachel Bellamy, Kyle Rector, and Scott D Fleming. 2013. How programmers debug, revisited: An information foraging theory perspective. IEEE Transactions on Software Engineering 39, 2 (2013), 197--215.
Paolo Missier, Khalid Belhajjame, and James Cheney. 2013. The W3C PROV family of specifications for modelling provenance metadata. In EDBT/ICDT. ACM, Genoa, Italy, 773--776.
Leonardo Murta, Vanessa Braganholo, Fernando Chirigati, David Koop, and Juliana Freire. 2015. no Workflow: Capturing and Analyzing Provenance of Scripts. In IPAW. Springer International Publishing, Cham, 71--83.
Lee Naish. 1992. Declarative diagnosis of missing answers. New Generation Computing 10, 3 (1992), 255--285.
Lee Naish, Philip W Dart, and Justin Zobel. 1989. The NU-Prolog Debugging Environment. In ICLP. MIT Press, Lisbon, Portugal, 521--536.
Henrik Nilsson and Peter Fritzson. 1994. Algorithmic debugging for lazy functional languages. Journal of functional programming 4, 3 (1994), 337--369.
João Felipe Pimentel, Juliana Freire, Leonardo Murta, and Vanessa Braganholo. 2016. Fine-Grained Provenance Collection over Scripts Through Program Slicing. In IPAW. Springer International Publishing, Cham, 199--203.
Joao Felipe Pimentel, Leonardo Murta, Vanessa Braganholo, and Juliana Freire. 2017. no Workflow: a tool for collecting, analyzing, and managing provenance from python scripts. PVLDB 10, 12 (2017), 4.
Bernard Pope. 2004. Declarative debugging with Buddha. In AFP. Springer, Tartu, Estonia, 273--308.
Python Software Foundation. 2019. difflib Helpers for computing deltas. https: //docs.python.org/3/library/difflib.html Accessed: 2019-05-19.
Jeanine Romano, Jeffrey D Kromrey, Jesse Coraggio, and Jeff Skowronek. 2006. Appropriate statistics for ordinal level data: Should we really be using t-test and Cohen's d for evaluating group differences on the NSSE and other surveys. In Annual meeting of the Florida Association of Institutional Research. FAIR, Cocoa Beach, FL, 1--33.
Nahid Shahmehri and Peter Fritzson. 1990. Algorithmic debugging for imperative languages with side-effects. In CC. Springer, Schwerin, Germany, 226--227.
Ehud Yehuda Shapiro. 1982. Algorithmic Program Debugging. Ph.D. Dissertation. Yale University, New Haven, CT. AAI8221751.
Samuel Sanford Shapiro and Martin B Wilk. 1965. An analysis of variance test for normality (complete samples). Biometrika 52, 3/4 (1965), 591--611.
Josep Silva. 2011. A survey on algorithmic debugging strategies. Advances in engineering software 42, 11 (2011), 976--991.
Mark Weiser. 1982. Programmers use slices when debugging. CACM 25, 7 (1982), 446--452.
Frank Wilcoxon. 1945. Individual Comparisons by Ranking Methods. Biometrics Bulletin 1, 6 (1945), 80--83. http://www.jstor.org/stable/3001968
Andreas Zeller. 2009. Why programs fail: a guide to systematic debugging. Morgan Kaufmann, San Francisco, CA.
Evyatar Av-Ron. 1984. Top-down diagnosis of Prolog programs. Master's thesis. Weizmann Institute of Science, Rehovot, Israel.
Rafael Caballero, Christian Hermanns, and Herbert Kuchen. 2007. Algorithmic debugging of Java programs. ENTCS 177 (2007), 75--89.
Rafael Caballero, Enrique Martin-Martin, Adrian Riesco, and Salvador Tamarit. 2014. EDD: A declarative debugger for sequential erlang programs. In TACAS. Springer Berlin Heidelberg, Berlin, Heidelberg, 581--586.
Rafael Caballero, Adrián Riesco, and Josep Silva. 2017. A survey of algorithmic debugging. CSUR 50, 4 (2017), 60.
Adriane Chapman and HV Jagadish. 2009. Why not?. In SIGMOD. ACM, Providence, RI, 523--534.
Zhifei Chen, Lin Chen, Yuming Zhou, Zhaogui Xu, William C Chu, and Baowen Xu. 2014. Dynamic slicing of Python programs. In COMPSAC. IEEE, Vasteras, Sweden, 219--228.
Richard A DeMillo, Richard J Lipton, and Frederick G Sayward. 1978. Hints on test data selection: Help for the practicing programmer. Computer 11, 4 (1978), 34--41.
Peter Fritzson, Nahid Shahmehri, Mariam Kamkar, and Tibor Gyimothy. 1992. Generalized algorithmic debugging and testing. LOPLAS 1, 4 (1992), 303--322.
Hani Z Girgis and Bharat Jayaraman. 2006. JavaDD: a declarative debugger for java. Technical Report. University at Buffalo, Department of Computer Science and Engineering.
Juan González, David Insa, and Josep Silva. 2013. A new hybrid debugging architecture for eclipse. In LOPSTR. Springer, Madrid, Spain, 183--201.
Alex Groce, Josie Holmes, Darko Marinov, August Shi, and Lingming Zhang. 2018. An extensible, regular-expression-based tool for multi-language mutant generation. In ICSE-Companion. IEEE, Gothenburg, Sweden, 25--28.
Christian Hermanns and Herbert Kuchen. 2011. Hybrid debugging of java programs. In ICSOFT. Springer, Seville, Spain, 91--107.
Matthew M Huntbach. 1987. Algorithmic PARLOG debugging. In Symposium on Logic Programming. IEEE, San Francisco, CA, 288--297.
David Insa and Josep Silva. 2010. An algorithmic debugger for Java. In ICSME. IEEE, Timisoara, Romania, 1--6.
Hoon-Joon Kouh and Weon-Hee Yoo. 2003. The efficient debugging system for locating logical errors in java programs. In ICCSA. Springer, Montreal, Canada, 684--693.
Arun Lakhotia and Leon Sterling. 1990. ProMiX: A Prolog partial evaluation system. In The Practice of Prolog. MIT Press, Cambridge, MA, 137--179.
Joseph Lawrance, Christopher Bogart, Margaret Burnett, Rachel Bellamy, Kyle Rector, and Scott D Fleming. 2013. How programmers debug, revisited: An information foraging theory perspective. IEEE Transactions on Software Engineering 39, 2 (2013), 197--215.
Paolo Missier, Khalid Belhajjame, and James Cheney. 2013. The W3C PROV family of specifications for modelling provenance metadata. In EDBT/ICDT. ACM, Genoa, Italy, 773--776.
Leonardo Murta, Vanessa Braganholo, Fernando Chirigati, David Koop, and Juliana Freire. 2015. no Workflow: Capturing and Analyzing Provenance of Scripts. In IPAW. Springer International Publishing, Cham, 71--83.
Lee Naish. 1992. Declarative diagnosis of missing answers. New Generation Computing 10, 3 (1992), 255--285.
Lee Naish, Philip W Dart, and Justin Zobel. 1989. The NU-Prolog Debugging Environment. In ICLP. MIT Press, Lisbon, Portugal, 521--536.
Henrik Nilsson and Peter Fritzson. 1994. Algorithmic debugging for lazy functional languages. Journal of functional programming 4, 3 (1994), 337--369.
João Felipe Pimentel, Juliana Freire, Leonardo Murta, and Vanessa Braganholo. 2016. Fine-Grained Provenance Collection over Scripts Through Program Slicing. In IPAW. Springer International Publishing, Cham, 199--203.
Joao Felipe Pimentel, Leonardo Murta, Vanessa Braganholo, and Juliana Freire. 2017. no Workflow: a tool for collecting, analyzing, and managing provenance from python scripts. PVLDB 10, 12 (2017), 4.
Bernard Pope. 2004. Declarative debugging with Buddha. In AFP. Springer, Tartu, Estonia, 273--308.
Python Software Foundation. 2019. difflib Helpers for computing deltas. https: //docs.python.org/3/library/difflib.html Accessed: 2019-05-19.
Jeanine Romano, Jeffrey D Kromrey, Jesse Coraggio, and Jeff Skowronek. 2006. Appropriate statistics for ordinal level data: Should we really be using t-test and Cohen's d for evaluating group differences on the NSSE and other surveys. In Annual meeting of the Florida Association of Institutional Research. FAIR, Cocoa Beach, FL, 1--33.
Nahid Shahmehri and Peter Fritzson. 1990. Algorithmic debugging for imperative languages with side-effects. In CC. Springer, Schwerin, Germany, 226--227.
Ehud Yehuda Shapiro. 1982. Algorithmic Program Debugging. Ph.D. Dissertation. Yale University, New Haven, CT. AAI8221751.
Samuel Sanford Shapiro and Martin B Wilk. 1965. An analysis of variance test for normality (complete samples). Biometrika 52, 3/4 (1965), 591--611.
Josep Silva. 2011. A survey on algorithmic debugging strategies. Advances in engineering software 42, 11 (2011), 976--991.
Mark Weiser. 1982. Programmers use slices when debugging. CACM 25, 7 (1982), 446--452.
Frank Wilcoxon. 1945. Individual Comparisons by Ranking Methods. Biometrics Bulletin 1, 6 (1945), 80--83. http://www.jstor.org/stable/3001968
Andreas Zeller. 2009. Why programs fail: a guide to systematic debugging. Morgan Kaufmann, San Francisco, CA.
Publicado
23/09/2019
Como Citar
LINHARES, Henrique; PIMENTEL, João Felipe; KOHWALTER, Troy; MURTA, Leonardo Gresta Paulino.
Provenance-enhanced Algorithmic Debugging. In: SIMPÓSIO BRASILEIRO DE ENGENHARIA DE SOFTWARE (SBES), 33. , 2019, Salvador.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
