{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T10:41:34Z","timestamp":1740134494845,"version":"3.37.3"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2015,6,24]],"date-time":"2015-06-24T00:00:00Z","timestamp":1435104000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science and Technology Major Project of China","award":["2012ZX01039-004"]},{"name":"National Science Foundation","award":["CCF-1149454, CCF-1500365, and CCF-1500024"]},{"DOI":"10.13039\/501100001809","name":"National Science Foundation of China","doi-asserted-by":"crossref","award":["61472318"],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2015,6,24]]},"abstract":"\n During software debugging, a significant amount of effort is required for programmers to identify the root cause of a manifested failure. In this article, we propose a cascade fault localization method to help speed up this labor-intensive process via a combination of weakest precondition computation and constraint solving. Our approach produces a cause tree, where each node is a potential cause of the failure and each edge represents a casual relationship between two causes. There are two main contributions of this article that differentiate our approach from existing methods. First, our method systematically computes all potential causes of a failure and augments each cause with a proper context for ease of comprehension by the user. Second, our method organizes the potential causes in a tree structure to enable\n on-the-fly<\/jats:italic>\n pruning based on domain knowledge and feedback from the user. We have implemented our new method in a software tool called CaFL, which builds upon the LLVM compiler and KLEE symbolic virtual machine. We have conducted experiments on a large set of public benchmarks, including real applications from GNU Coreutils and Busybox. Our results show that in most cases the user has to examine only a small fraction of the execution trace before identifying the root cause of the failure.\n <\/jats:p>","DOI":"10.1145\/2738038","type":"journal-article","created":{"date-parts":[[2015,6,25]],"date-time":"2015-06-25T14:36:19Z","timestamp":1435242979000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Explaining Software Failures by Cascade Fault Localization"],"prefix":"10.1145","volume":"20","author":[{"given":"Qiuping","family":"Yi","sequence":"first","affiliation":[{"name":"Chinese Academy of Sciences, Beijing, China"}]},{"given":"Zijiang","family":"Yang","sequence":"additional","affiliation":[{"name":"Western Michigan University, Kalamazoo, MI"}]},{"given":"Jian","family":"Liu","sequence":"additional","affiliation":[{"name":"Chinese Academy of Sciences, Beijing, China"}]},{"given":"Chen","family":"Zhao","sequence":"additional","affiliation":[{"name":"Chinese Academy of Sciences, Beijing, China"}]},{"given":"Chao","family":"Wang","sequence":"additional","affiliation":[{"name":"Virginia Polytechnic Institute and State University, Blacksburg, VA"}]}],"member":"320","published-online":{"date-parts":[[2015,6,24]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1145\/93542.93576"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1109\/SEFM.2008.35"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1145\/604131.604140"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1145\/1882291.1882319"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1007\/978-3-319-11164-3_14"},{"volume-title":"Software Testing Techniques","author":"Beizer Boris","unstructured":"Boris Beizer . 1990. Software Testing Techniques . Van Nostrand Reinhold Co. , New York . Boris Beizer. 1990. Software Testing Techniques. Van Nostrand Reinhold Co., New York.","key":"e_1_2_1_6_1"},{"unstructured":"Busybox. http:\/\/busybox.net\/. Busybox. http:\/\/busybox.net\/.","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the USENIX Symposium on Operating Systems Design and Implementation. 209--224","author":"Cadar Cristian","year":"2008","unstructured":"Cristian Cadar , Daniel Dunbar , and Dawson Engler . 2008 . KLEE: Unassisted and automatic generation of high-coverage tests for complex systems programs . In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation. 209--224 . Cristian Cadar, Daniel Dunbar, and Dawson Engler. 2008. KLEE: Unassisted and automatic generation of high-coverage tests for complex systems programs. In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation. 209--224."},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1007\/978-3-642-35873-9_13"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1145\/1062455.1062522"},{"unstructured":"Coreutils. http:\/\/www.gnu.org\/software\/coreutils\/. Coreutils. http:\/\/www.gnu.org\/software\/coreutils\/.","key":"e_1_2_1_11_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.2307\/2963594"},{"volume-title":"A Discipline of Programming","author":"Dijkstra Edsger Wybe","unstructured":"Edsger Wybe Dijkstra . 1976. A Discipline of Programming . Prentice-Hall , Englewood Cliffs, NJ . Edsger Wybe Dijkstra. 1976. A Discipline of Programming. Prentice-Hall, Englewood Cliffs, NJ.","key":"e_1_2_1_13_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1007\/s10664-005-3861-2"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1007\/978-3-642-32759-9_17"},{"volume-title":"Proceedings of the International Conference on Computer Aided Verification. 519--531","author":"Ganesh Vijay","unstructured":"Vijay Ganesh and David L. Dill . 2007. A decision procedure for bit-vectors and arrays . In Proceedings of the International Conference on Computer Aided Verification. 519--531 . Vijay Ganesh and David L. Dill. 2007. A decision procedure for bit-vectors and arrays. In Proceedings of the International Conference on Computer Aided Verification. 519--531.","key":"e_1_2_1_16_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1007\/11817963_33"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1016\/j.entcs.2006.12.032"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.1007\/s10009-005-0202-0"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1007\/978-3-540-27813-9_35"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.5555\/1767111.1767119"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.5555\/318773.319248"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.5555\/2032305.2032345"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.1145\/1993498.1993550"},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.1016\/0020-0190(88)90054-3"},{"key":"e_1_2_1_26_1","volume-title":"LLVM: An infrastructure for multi-stage optimization. Master's Thesis.","author":"Lattner Chris","year":"2002","unstructured":"Chris Lattner . 2002 . LLVM: An infrastructure for multi-stage optimization. Master's Thesis. Chris Lattner. 2002. LLVM: An infrastructure for multi-stage optimization. Master's Thesis."},{"doi-asserted-by":"publisher","key":"e_1_2_1_27_1","DOI":"10.5555\/2014698.2014872"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.1145\/1669112.1669182"},{"doi-asserted-by":"publisher","key":"e_1_2_1_29_1","DOI":"10.1007\/s10817-007-9084-z"},{"volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence. 327--332","author":"Yongmei","unstructured":"Yongmei Y. Liu and Bing Li. 2010. Automated program debugging via multiple predicate switching . In Proceedings of the AAAI Conference on Artificial Intelligence. 327--332 . Yongmei Y. Liu and Bing Li. 2010. Automated program debugging via multiple predicate switching. In Proceedings of the AAAI Conference on Artificial Intelligence. 327--332.","key":"e_1_2_1_30_1"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the International Conference on Theory and Applications of Satisfiability Testing (SAT'04)","author":"Lynce In\u00eas","year":"2004","unstructured":"In\u00eas Lynce and Joao Marques-Silva . 2004 . On computing minimum unsatisfiable cores . In Proceedings of the International Conference on Theory and Applications of Satisfiability Testing (SAT'04) . In\u00eas Lynce and Joao Marques-Silva. 2004. On computing minimum unsatisfiable cores. In Proceedings of the International Conference on Theory and Applications of Satisfiability Testing (SAT'04)."},{"doi-asserted-by":"publisher","key":"e_1_2_1_32_1","DOI":"10.1007\/978-3-319-12154-3_17"},{"key":"e_1_2_1_33_1","volume-title":"Reiss","author":"Pytlik Brock","year":"2003","unstructured":"Brock Pytlik , Manos Renieris , Shriram Krishnamurthi , and Steven P . Reiss . 2003 . Automated fault localization using potential invariants. CoRR cs.SE\/0310040 (2003). Brock Pytlik, Manos Renieris, Shriram Krishnamurthi, and Steven P. Reiss. 2003. Automated fault localization using potential invariants. CoRR cs.SE\/0310040 (2003)."},{"doi-asserted-by":"publisher","key":"e_1_2_1_34_1","DOI":"10.1145\/1595696.1595704"},{"volume-title":"Proceedings of the IEEE\/ACM International Conference On Automated Software Engineering. 30--39","author":"Renieris Manos","unstructured":"Manos Renieris and Steven P. Reiss . 2003. Fault localization with nearest neighbor queries . In Proceedings of the IEEE\/ACM International Conference On Automated Software Engineering. 30--39 . Manos Renieris and Steven P. Reiss. 2003. Fault localization with nearest neighbor queries. In Proceedings of the IEEE\/ACM International Conference On Automated Software Engineering. 30--39.","key":"e_1_2_1_35_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_36_1","DOI":"10.1145\/2338965.2336790"},{"doi-asserted-by":"publisher","key":"e_1_2_1_37_1","DOI":"10.1145\/2451116.2451131"},{"doi-asserted-by":"publisher","key":"e_1_2_1_38_1","DOI":"10.1007\/11901914_9"},{"doi-asserted-by":"publisher","key":"e_1_2_1_39_1","DOI":"10.1109\/TSE.1984.5010248"},{"doi-asserted-by":"publisher","key":"e_1_2_1_40_1","DOI":"10.1109\/ICSE.2015.46"},{"unstructured":"Yices: An SMT Solver. In http:\/\/yices.csl.com\/. Yices: An SMT Solver. In http:\/\/yices.csl.com\/.","key":"e_1_2_1_41_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_42_1","DOI":"10.1145\/587051.587053"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the Conference on Design, Automation and Test in Europe (DATE'03)","author":"Zhang Lintao","year":"2003","unstructured":"Lintao Zhang and Sharad Malik . 2003 . Validating SAT solvers using an independent resolution-based checker: Practical implementations and other applications . In Proceedings of the Conference on Design, Automation and Test in Europe (DATE'03) . 880--885. Lintao Zhang and Sharad Malik. 2003. Validating SAT solvers using an independent resolution-based checker: Practical implementations and other applications. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE'03). 880--885."},{"doi-asserted-by":"publisher","key":"e_1_2_1_44_1","DOI":"10.1145\/1134285.1134324"},{"doi-asserted-by":"publisher","key":"e_1_2_1_45_1","DOI":"10.1145\/1250734.1250782"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2738038","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,30]],"date-time":"2022-12-30T20:09:53Z","timestamp":1672430993000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2738038"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,24]]},"references-count":45,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,6,24]]}},"alternative-id":["10.1145\/2738038"],"URL":"https:\/\/doi.org\/10.1145\/2738038","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2015,6,24]]},"assertion":[{"value":"2014-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-06-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}