{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,29]],"date-time":"2024-04-29T15:10:02Z","timestamp":1714403402952},"reference-count":45,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2012,9,19]],"date-time":"2012-09-19T00:00:00Z","timestamp":1348012800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Concurrency and Computation"],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:title>SUMMARY<\/jats:title><jats:p>Multicore computers are ubiquitous. Expert developers as well as developers with little experience in parallelism are now asked to create multithreaded software to exploit parallelism in mainstream shared\u2010memory hardware. However, finding and fixing parallel programming errors is a complex and arduous task. Programmers thus rely on tools such as race detectors that typically focus on reporting errors due to incorrect usage of synchronization constructs or due to missing synchronization. This arsenal of debugging techniques, however, is incomplete. This article presents a new perspective and addresses a largely unexplored direction of defect localization where a wrong usage of<jats:italic>nonparallel<\/jats:italic>programming constructs might cause wrong<jats:italic>parallel<\/jats:italic>application behavior. In particular, we make a contribution by showing how to use data\u2010mining techniques to locate defects in multithreaded shared\u2010memory programs. Our technique analyzes execution anomalies in a condensed representation of the dynamic call graphs of a multithreaded object\u2010oriented application and identifies methods that contain a defect. Compared with race detectors that concentrate on finding incorrect synchronization, our method is able to reveal a wider range of defects that affect the control flow of a parallel program. Results from controlled experiments show that our data\u2010mining approach finds not only race conditions in different types of multicore applications but also other errors that cause incorrect parallel program behavior. Data\u2010mining techniques offer a fruitful new ground for parallel program debugging, and we also discuss long\u2010term directions for this interesting field. Copyright \u00a9 2012 John Wiley &amp; Sons, Ltd.<\/jats:p>","DOI":"10.1002\/cpe.2918","type":"journal-article","created":{"date-parts":[[2012,9,19]],"date-time":"2012-09-19T04:35:07Z","timestamp":1348029307000},"page":"1-20","source":"Crossref","is-referenced-by-count":1,"title":["Data mining for defects in multicore applications: an entropy\u2010based call\u2010graph technique"],"prefix":"10.1002","volume":"26","author":[{"given":"Frank","family":"Eichinger","sequence":"first","affiliation":[{"name":"SAP Research Karlsruhe Germany"}]},{"given":"Victor","family":"Pankratius","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory Cambridge MA USA"}]},{"given":"Klemens","family":"B\u00f6hm","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology (KIT) Germany"}]}],"member":"311","published-online":{"date-parts":[[2012,9,19]]},"reference":[{"key":"e_1_2_11_2_1","first-page":"45","volume-title":"Emerging Research Directions in Computer Science \u2013 Contributions from the Young Informatics Faculty in Karlsruhe","author":"Pankratius V","year":"2010"},{"key":"e_1_2_11_3_1","doi-asserted-by":"crossref","unstructured":"FarchiE NirY UrS.Concurrent bug patterns and how to test them.Proceedings of the 1st Workshop on Parallel and Distributed Systems: Testing and Debugging (PADTAD) Nice France 2003 DOI:10.1109\/IPDPS.2003.1213511.","DOI":"10.1109\/IPDPS.2003.1213511"},{"key":"e_1_2_11_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353534.1346323"},{"key":"e_1_2_11_5_1","doi-asserted-by":"crossref","unstructured":"EnglerD AshcraftK.Racer X: effective static detection of race conditions and deadlocks.Proceedings of the 19th ACM Symposium on Operating Systems Principles (SOSP) Bolton Landing New York USA 2003 DOI:10.1145\/945445.945468.","DOI":"10.1145\/945445.945468"},{"key":"e_1_2_11_6_1","doi-asserted-by":"crossref","unstructured":"FlanaganC LeinoKRM LillibridgeM NelsonG SaxeJB StataR.Extended static checking for Java.Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) Berlin Germany 2002 DOI:10.1145\/512529.512558.","DOI":"10.1145\/512529.512558"},{"key":"e_1_2_11_7_1","unstructured":"MusuvathiM QadeerS BallT.CHESS: a systematic testing tool for concurrent software.Technical Report MSR\u2010TR\u20102007\u2010149 Microsoft Research 2007."},{"key":"e_1_2_11_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/966049.781528"},{"key":"e_1_2_11_9_1","doi-asserted-by":"crossref","unstructured":"QiY DasR LuoZD TrotterM.MulticoreSDK: a practical and efficient data race detector for real\u2010world applications.Proceedings of the 7th Workshop on Parallel and Distributed Systems (PADTAD) Chicago IL USA 2009 DOI: 2410.1145\/1639622.1639627.","DOI":"10.1145\/1639622.1639627"},{"key":"e_1_2_11_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/265924.265927"},{"key":"e_1_2_11_11_1","doi-asserted-by":"crossref","unstructured":"TzorefR UrS Yom\u2010TovE.Instrumenting where it hurts \u2013 an automatic concurrent debugging technique.Proceedings of the 16th International Symposium on Software Testing and Analysis (ISSTA) London UK 2007 DOI: 2410.1145\/1273463.1273469.","DOI":"10.1145\/1273463.1273469"},{"key":"e_1_2_11_12_1","volume-title":"Why Programs Fail: A Guide to Systematic Debugging","author":"Zeller A","year":"2009"},{"key":"e_1_2_11_13_1","unstructured":"EichingerF.Data\u2010mining techniques for call\u2010graph\u2010based software\u2010defect localisation.PhD Thesis Department of Informatics Karlsruhe Institute of Technology (KIT) Karlsruhe Germany May2011."},{"key":"e_1_2_11_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2006.105"},{"key":"e_1_2_11_15_1","doi-asserted-by":"crossref","unstructured":"JonesJA HarroldMJ.Empirical evaluation of the tarantula automatic fault\u2010localization technique.Proceedings of the 20th IEEE\/ACM International Conference on Automated Software Engineering (ASE) Long Beach CA USA 2005 DOI:10.1145\/1101908.1101949.","DOI":"10.1145\/1101908.1101949"},{"key":"e_1_2_11_16_1","doi-asserted-by":"crossref","unstructured":"JonesJA HarroldMJ StaskoJ.Visualization of test information to assist fault localization.Proceedings of the 24th International Conference on Software Engineering (ICSE) Orlando FL USA 2002 DOI: 2410.1145\/581339.581397.","DOI":"10.1145\/581396.581397"},{"key":"e_1_2_11_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jss.2009.06.035"},{"key":"e_1_2_11_18_1","unstructured":"EichingerF B\u00f6hmK HuberM.Mining edge\u2010weighted call graphs to localise software bugs.Proceedings of the 8th European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD) Antwerp Belgium 2008 DOI:10.1007\/978\u20103\u2010540\u201087479\u20109_40."},{"key":"e_1_2_11_19_1","unstructured":"EichingerF PankratiusV Gro\u00dfePWL B\u00f6hmK.Localizing defects in multithreaded programs by mining dynamic call graphs.Proceedings of the 5th Testing: Academic and Industrial Conference \u2013 Practice and Research Techniques (TAIC PART) Windsor UK 2010 DOI:10.1007\/978\u20103\u2010642\u201015585\u20107_7."},{"key":"e_1_2_11_20_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380160304"},{"key":"e_1_2_11_21_1","unstructured":"ZellerA.Yesterday my program worked. Today it does not. Why?Proceedings of the 7th European Software Engineering Conference and the 7th ACM SIGSOFT International Symposium on the Foundations of Software Engineering (ESEC\/FSE) Rome Italy 1999 DOI:10.1007\/3\u2010540\u201048166\u20104_16."},{"key":"e_1_2_11_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/MS.2008.130"},{"key":"e_1_2_11_23_1","doi-asserted-by":"crossref","unstructured":"AyewahN PughW.The google findbugs fixit.Proceedings of the 19th International Symposium on Software Testing and Analysis (ISSTA) Trento Italy 2010 DOI:10.1145\/1831708.1831738.","DOI":"10.1145\/1831708.1831738"},{"key":"e_1_2_11_24_1","doi-asserted-by":"crossref","unstructured":"RutarN AlmazanCB FosterJS.A comparison of bug finding tools for Java.Proceedings of the 15th International Symposium on Software Reliability Engineering (ISSRE) Rennes France 2004 DOI:10.1109\/ISSRE.2004.1.","DOI":"10.1109\/ISSRE.2004.1"},{"key":"e_1_2_11_25_1","doi-asserted-by":"crossref","unstructured":"DallmeierV LindigC ZellerA.Lightweight defect localization for Java.Proceedings of the 19th European Conference on Object\u2010Oriented Programming (ECOOP) Glasgow UK 2005 DOI:10.1007\/11531142_23.","DOI":"10.1007\/11531142_23"},{"key":"e_1_2_11_26_1","doi-asserted-by":"crossref","unstructured":"LiuC YanX YuH HanJ YuPS.Mining behavior graphs for \u2018backtrace\u2019 of noncrashing bugs.Proceedings of the 5th SIAM International Conference on Data Mining (SDM) Newport Beach CA USA 2005.","DOI":"10.1137\/1.9781611972757.26"},{"key":"e_1_2_11_27_1","doi-asserted-by":"crossref","unstructured":"Di\u2009FattaG LeueS StegantovaE.Discriminative pattern mining in software fault detection.Proceedings of the 3rd International Workshop on Software Quality Assurance (SOQUA) Portland OR USA 2006 DOI:10.1145\/1188895.1188910.","DOI":"10.1145\/1188895.1188910"},{"key":"e_1_2_11_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978\u20101\u20104419\u20106045\u20100_17"},{"key":"e_1_2_11_29_1","doi-asserted-by":"crossref","unstructured":"ChengH LoD ZhouY WangX YanX.Identifying bug signatures using discriminative graph mining.Proceedings of the 18th International Symposium on Software Testing and Analysis (ISSTA) Chicago IL USA 2009 DOI:10.1145\/1572272.1572290.","DOI":"10.1145\/1572272.1572290"},{"key":"e_1_2_11_30_1","unstructured":"KiczalesG HilsdaleE HuguninJ KerstenM PalmJ GriswoldWG.An overview of AspectJ.Proceedings of the 15th European Conference on Object\u2010Oriented Programming (ECOOP) Budapest Hungary 2001 DOI:10.1007\/3\u2010540\u201045337\u20107_18."},{"key":"e_1_2_11_31_1","doi-asserted-by":"crossref","unstructured":"CoptyS UrS.Multi\u2010threaded testing with AOP is easy and it finds bugs!Proceedings of the 11th International Euro\u2010Par Conference Lisboa Portugal 2005 DOI:10.1007\/11549468_81.","DOI":"10.1007\/11549468_81"},{"key":"e_1_2_11_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1656274.1656278"},{"key":"e_1_2_11_33_1","volume-title":"C4.5: Programs for Machine Learning","author":"Quinlan JR","year":"1993"},{"key":"e_1_2_11_34_1","unstructured":"ElomaaT RousuJ.Efficient multisplitting on numerical data.Proceedings of the 1st European Symposium on Principles of Data Mining and Knowledge Discovery (PKDD) Trondheim Norway 1997 DOI:10.1007\/3\u2010540\u201063223\u20109_117."},{"key":"e_1_2_11_35_1","doi-asserted-by":"crossref","unstructured":"EytaniY UrS.Compiling a benchmark of documented multi\u2010threaded bugs.Proceedings of the 18th International Parallel and Distributed Processing Symposium (IPDPS) Santa Fe NM 2004 DOI:10.1109\/IPDPS.2004.1303339.","DOI":"10.1109\/IPDPS.2004.1303339"},{"key":"e_1_2_11_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/356989.357000"},{"key":"e_1_2_11_37_1","unstructured":"Tornado HTTP Server software. (Available athttp:\/\/tornado.sourceforge.net\/) [Accessed on August 2 2012]."},{"key":"e_1_2_11_38_1","unstructured":"WebLech URL Spider software. (Available athttp:\/\/weblech.sourceforge.net\/) [Accessed on August 2 2012]."},{"key":"e_1_2_11_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1976.233837"},{"key":"e_1_2_11_40_1","doi-asserted-by":"crossref","unstructured":"NagappanN BallT ZellerA.Mining metrics to predict component failures.Proceedings of the 28th International Conference on Software Engineering (ICSE) Shanghai China 2006 DOI:10.1145\/1134285.1134349.","DOI":"10.1145\/1134285.1134349"},{"key":"e_1_2_11_41_1","doi-asserted-by":"crossref","unstructured":"RenieresM ReissSP.Fault localization with nearest neighbor queries.Proceedings of the 18th IEEE\/ACM International Conference on Automated Software Engineering (ASE) Montreal Canada 2003 DOI:10.1109\/ASE.2003.1240292.","DOI":"10.1109\/ASE.2003.1240292"},{"key":"e_1_2_11_42_1","doi-asserted-by":"crossref","unstructured":"CleveH ZellerA.Locating causes of program failures.Proceedings of the 27th International Conference on Software Engineering (ICSE) St. Louis MO USA 2005 DOI:10.1145\/1062455.1062522.","DOI":"10.1145\/1062455.1062522"},{"key":"e_1_2_11_43_1","unstructured":"EichingerF KrogmannK KlugR B\u00f6hmK.Software\u2010defect localisation by mining dataflow\u2010enabled call graphs.Proceedings of the 10th European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD) Barcelona Spain 2010 DOI:10.1007\/978\u20103\u2010642\u201015880\u20103_33."},{"key":"e_1_2_11_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-05094-1"},{"key":"e_1_2_11_45_1","doi-asserted-by":"crossref","unstructured":"ChoiJD ZellerA.Isolating failure inducing thread schedules.Proceedings of the 11th International Symposium on Software Testing and Analysis (ISSTA) Rome Italy 2002 DOI: 2410.1145\/566172.566211.","DOI":"10.1145\/566210.566211"},{"key":"e_1_2_11_46_1","doi-asserted-by":"publisher","DOI":"10.1002\/9780470073049.ch5"}],"container-title":["Concurrency and Computation: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fcpe.2918","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fcpe.2918","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/cpe.2918","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,29]],"date-time":"2024-04-29T14:51:30Z","timestamp":1714402290000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/cpe.2918"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,9,19]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1002\/cpe.2918"],"URL":"https:\/\/doi.org\/10.1002\/cpe.2918","archive":["Portico"],"relation":{},"ISSN":["1532-0626","1532-0634"],"issn-type":[{"value":"1532-0626","type":"print"},{"value":"1532-0634","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,9,19]]}}}