LocFaults
Authors:
Open Access
- 13 April 2015
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1773-1780
Abstract
We introduce in this paper LocFaults, a new flow-driven and constraint-based approach for error localization. The input is a faulty program for which a counter-example and a postcondition are provided. To identify helpful information for error location, we generate a constraint system for the paths of the control flow graph for which at most k conditional statements may be erroneous. Then, we calculate Minimal Correction Sets (MCS) of bounded size for each of these paths. The removal of one of these sets of constraints yields a maximal satisfiable subset, in other words, a maximal subset of constraints satisfying the post condition. To compute the MCS, we extend the algorithm proposed by Liffiton and Sakallah [21] in order to handle programs with numerical statements more efficiently. The main advantage of this flow-driven approach is that the computed sets of suspicious instructions are small, each of them being associated with an identified path. Moreover, the constraint-programming based framework of LocFaults allows mixing Boolean and numerical constraints in an efficient and straightforward way. Preliminary experiments are quite encouraging.Keywords
Funding Information
- Agence Nationale de la Recherche (11-INSE-0004)
This publication has 25 references indexed in Scilit:
- Enumerating Infeasibility: Finding Multiple MUSes Quickly2013
- Automated debugging based on a constraint model of the program and a test caseThe Journal of Logic and Algebraic Programming, 2012
- An efficient diagnosis algorithm for inconsistent constraint setsArtificial Intelligence for Engineering Design, Analysis and Manufacturing, 2011
- CPBPV: a constraint-programming framework for bounded program verificationConstraints, 2010
- Algorithms for Computing Minimal Unsatisfiable Subsets of ConstraintsJournal of Automated Reasoning, 2007
- Automated Fault Localization for C ProgramsElectronic Notes in Theoretical Computer Science, 2007
- Error explanation with distance metricsInternational Journal on Software Tools for Technology Transfer, 2005
- Understanding Counterexamples with explain2004
- Consistent subsets of inconsistent systems: structure and behaviourJournal of Experimental & Theoretical Artificial Intelligence, 2003
- Detecting iis in infeasible linear programmes using techniques from goal programmingComputers & Operations Research, 1996