The DOI matches its Crossref record.
Cause clue clauses: error localization using maximum satisfiability
Abstract
Much effort is spent by programmers everyday in trying to reduce long, failing execution traces to the cause of the error. We present an algorithm for error cause localization based on a reduction to the maximal satisfiability problem (MAX-SAT), which asks what is the maximum number of clauses of a Boolean formula that can be simultaneously satisfied by an assignment. At an intuitive level, our algorithm takes as input a program and a failing test, and comprises the following three steps. First, using bounded model checking, and a bound obtained from the execution of the test, we encode the semantics of a bounded unrolling of the program as a Boolean trace formula . Second, for a failing program execution (e.g., one that violates an assertion or a post-condition), we construct an unsatisfiable formula by taking the formula and additionally asserting that the input is the failing test and that the assertion condition does hold at the end. Third, using MAX-SAT, we find a maximal set of clauses in this formula that can be satisfied together, and output the complement set as a potential cause of the error. We have implemented our algorithm in a tool called BugAssist that performs error localization for C programs. We demonstrate the effectiveness of BugAssist on a set of benchmark examples with injected faults, and show that in most cases, BugAssist can quickly and precisely isolate a few lines of code whose change eliminates the error. We also demonstrate how our algorithm can be modified to automatically suggest fixes for common classes of errors such as off-by-one.We have implemented our algorithm in a tool called BugAssist that performs error localization for C programs. We demonstrate the effectiveness of BugAssist on a set of benchmark examples with injected faults, and show that in most cases, BugAssist can quickly and precisely isolate a few lines of code whose change eliminates the error. We also demonstrate how our algorithm can be modified to automatically suggest fixes for common classes of errors such as off-by-one.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cited by
A Survey on Software Fault Localization
Wong, W. E., Gao, R., Li, Y., Abreu, R., & Wotawa, F. (2016) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2016.2521368 · Cited by 1,110
Automatic patch generation by learning correct code
Long, F., & Rinard, M. (2016) · Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages · doi:10.1145/2837614.2837617 · Cited by 481
Automated feedback generation for introductory programming assignments
Singh, R., Gulwani, S., & Solar-Lezama, A. (2013) · Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/2491956.2462195 · Cited by 383
Staged program repair with condition synthesis
Long, F., & Rinard, M. (2015) · Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering · doi:10.1145/2786805.2786811 · Cited by 348
SQLizer: query synthesis from natural language
Yaghmazadeh, N., Wang, Y., Dillig, I., & Dillig, T. (2017) · Proceedings of the ACM on Programming Languages · doi:10.1145/3133887 · Cited by 279
Metadata
- Authors
- Jose, M., & Majumdar, R.
- Venue
- ACM SIGPLAN Notices
- Published
- 2011-06-04
- Volume
- 46
- Issue
- 6
- Pages
- 437-446
- ISSN
- 0362-1340 (ISSN-L)
- 1558-1160
- OpenAlex
- W2040900440
- Cited by
- 185
- References
- 0
- FWCI
- 56.97
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Cause clue clauses: error localization using maximum satisfiability. https://app.cochat.ai/papers/10.1145/1993316.1993550
- The paper
- Jose, M., & Majumdar, R. (2011). Cause clue clauses: error localization using maximum satisfiability. ACM SIGPLAN Notices. https://doi.org/10.1145/1993316.1993550
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.