1Class 20• Fault localization (cont’d)• Test-data generation• Exam review: Nov 3, after class to 7:30• Responsible for all material up through Nov 3 (through test-data generation)• Send questions beforehand so all can prepare• Exam: Nov 10• Final project presentations: Dec 1, 3; 4:35-6:45• Assign (see Schedule for links) • Problem Set 9 discuss• ReadingsFault Localization Using Tarantula• What information does Tarantula use to compute suspicious (and ranking) of statements in the program?• How is this information used?• Are there other ways to compute the suspiciousness using this information?• What information other than statement coverage could be used for fault localization?• Do you think statement coverage would have worked for tritype?• How could we use fault localization to identify which changes are most suspicious after a build?Improving Fault-localization EfficiencyPExecuteDebugfailed testsP’all testspassExecuteDebugfailedtestsP’’Piisfailure-freeExecute…• Are all failing tests caused by the same fault?• Are all failing tests caused by the same fault?• Can we associate groups of tests with differentfaults?• Are all failing tests caused by the same fault?• Can we associate groups of tests with differentfaults?• Can we reduce debugging effort by considering these groups individually?• Are all failing tests caused by the same fault?• Can we associate groups of tests with differentfaults?• Can we reduce debugging effort by considering these groups individually?• Can we reduce debugging effort by consideringthese groups simultaneously?mid() {int x,y,z,m;1:read(“Enter 3 integers:”,x,y,z);2:m = z;3:if (y<z)4: if (x<y)5: m = y;6: else if (x<z)7: m = y;8:else9: if (x>y)10: m = z;11: else if (x>z)12: m = x;13:print(“Middle number is:”, m);}3,3,51,2,33,2,25,5,51,1,45,3,4PPPP FhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhPass/fail Status3,2,12,1,35,4,25,2,6hhhhhhhhhhhhhhhhhhhhhhhhhhhhPPFFFt1 t2 t3 t4 t5 t6 t7 t8 t9 t10Improving Fault-localization Efficiency3,3,51,2,33,2,25,5,51,1,45,3,4PPPP FhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhPass/fail Status3,2,12,1,35,4,25,2,6hhhhhhhhhhhhhhhhhhhhhPPFFFmid() {int x,y,z,m;1:read(“Enter 3 integers:”,x,y,z);2:m = z;3:if (y<z)4: if (x<y)5: m = y;6: else if (x<z)7: m = y;8:else9: if (x>y)10: m = z;11: else if (x>z)12: m = x;13:print(“Middle number is:”, m);}t1 t2 t3 t4 t5 t6 t7 t8 t9 t10Improving Fault-localization EfficiencyhhhhhhhDebugging ProcessPExecuteDebugfailed testsP’all testspassExecuteDebugfailed testsP’’Piisfailure-freePjisfailure-freeExecute…PExecuteDebugsomefailedtestsP’all testspassExecutesomefailedtests…Debugging ProcessPExecuteDebugfailed testsP’all testspassExecuteDebugfailed testsP’’Piisfailure-freePjisfailure-freeExecute…PExecuteDebugsomefailedtestsP’all testspassExecutesomefailedtests…ExecutePDebugDebugP’all testspass…Pkisfailure-freesomefailedtestssomefailedtestsHierarchy of Bugsy Faults often dominate each othery Failing test cases are first caused by a set of initial faultsy Once initial faults are fixed, other faults manifest themselvesTimeFault 1Fault 2Fault 3Fault 4Fault 5Fault 6Fault 7Fault 8Pkisfailure-freeDebugging ProcessPExecuteDebugfailed testsP’all testspassExecuteDebugfailed testsP’’Piisfailure-freePjisfailure-freeExecute…PExecuteDebugsomefailedtestsP’all testspassExecutesomefailedtests…ExecutePDebugDebugP’all testspass…somefailedtestssomefailedtestsPotential benefits:• Reduced time to failure-free program• Less “noise” in locating each fault• Better utilization of developer effortPotential costs• Overhead to partition testcases • Multiple debuggers(developers)Debugging ProcessPExecuteDebugfailed testsP’all testspassExecuteDebugfailed testsP’’Piisfailure-freePjisfailure-freeExecute…PExecuteDebugsomefailedtestsP’all testspassExecutesomefailedtests…ExecutePDebugDebugP’all testspass…Pkisfailure-freesomefailedtestssomefailedtestsCrucial problem: • Partitioning failed tests into groups of similar behavior—focus on different faults• fault-focusing clustersCrucial problem: • Partitioning failed tests into groups of similar behavior—focus on different faults• fault-focusing clusters of failed test casesFault-focusing Clusters—Overviewt06t07t09t08t10t08t07t04t09t02t05t01 t03t10Fault-focusing clusters: • Clusters of failing test cases• Clusters failing in similar way• Each cluster targeting a different faultTest CasesFault-focusing Clusterst07t09t08t10t06t04t02t05t01 t03Test Casest06t04t02t05t01 t03Specialized Test SuitesSpecialized test suites: Fault-focusing clusters combined with passing test casesFault-focusing Clusterst07t09t08t10Specialized Test SuitesDeveloper Developert06t04t02t05t01 t03t06t04t02t05t01 t03Specialized test suites: Fault-focusing clusters combined with passing test casesSpecialized test suites: Fault-focusing clusters combined with passing test cases• Find faults one at a using specialized testsuitesFault-focusing Clusterst07t09t08t10t06t04t02t05t01 t03Test Casest06t04t02t05t01 t03Specialized Test SuitesDeveloper 1 Developer 2t06t04t02t05t01 t03t06t04t02t05t01 t03Specialized test suites: Fault-focusing clusters combined with passing test cases• Find faults one at a using specialized testsuites• Find faults at the sametime (in parallel) usingspecialized test suitesFault-focusing ClustersExecutionClusteringFaultLocalizationfailed test casesexecutioninformationspecializedtest suitessuspiciousnessand ranksFault-focusing ClustersClustering by behavior modelsDynamic information• profiles (branch, method-method, …)• only failed testsStatistical analysis, machine learning• generate models for each execution• cluster modelsFault-localization for stopping pointExecutionClusteringFaultLocalizationfailed test casesexecutioninformationspecializedtest suitessuspiciousnessand rankst07-09t07-09-08-10t08-010Clustering Behavior Models• Models: discrete-time Markov chains (DTMCs) from profiles(branch, method,…)• Clustering: iterative with two most similar according to Sim1Sim1: sum of absolute difference between matching transitions in DTMCs being comparedMost difficult problem of clustering is determining a good stopping criterion?t07t08t09t10Most difficult problem of clustering is determining a good stopping criterion?What is a good stopping point for the clusteringfor fault-focused