DOC PREVIEW
Purdue CS 59000 - Statistical Debugging

This preview shows page 1-2-14-15-29-30 out of 30 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS590Z Statistical DebuggingA Very Important PrincipleTarantula (ASE 2005, ISSTA 2007)Scalable Remote Bug Isolation (PLDI 2004, 2005)Bug IsolationSlide 6An ExampleSlide 8Program PredicatesEvaluation Bias of Predicate PUnderlying PopulationsMajor ChallengesOur ApproachAlgorithm OutputsOutlineExperiment ResultsBug BenchmarkLocalization Quality Metric [RR03]1st Example2nd ExampleRelated WorksLocalized bugs w.r.t. Examined CodeCumulative Effects w.r.t. Code ExaminationTop-k SelectionSlide 25Case Study: bc 1.06Slide 27Future WorkConclusionsDiscussionCS590Z Statistical DebuggingXiangyu Zhang (part of the slides are from Chao Liu)A Very Important PrincipleTraditional debugging techniques deal with single (or very few) executions.With the acquisition of a large set of executions, including passing and failing executions, statistical debugging is often highly effective.Failure reportingIn house testingTarantula (ASE 2005, ISSTA 2007)Scalable Remote Bug Isolation (PLDI 2004, 2005)Look at predicatesBranchesFunction returns (<0, <=0, >0, >=0, ==0, !=0)Scalar pairsFor each assignment x=…, find all variables y_i and constants c_j, each pair of x (=,<,<=…) y_i/c_jSample the predicate evaluations (Bernoulli sampling)Investigate the relation of the probability of a predicate being true with the bug manifestion.Bug IsolationBug Isolation How much does P being true increase the probability of failure over simply reaching the line P is sampled.An ExampleSymptoms563 lines of C code130 out of 5542 test cases fail to give correct outputsNo crashesThe predicate are evaluated to both true and false in one executionvoid subline(char *lin, char *pat, char *sub){ int i, lastm, m; lastm = -1; i = 0; while((lin[i] != ENDSTR)) {m = amatch(lin, i, pat, 0);if (m >= 0){ putsub(lin, i, m, sub); lastm = m; }if ((m == -1) || (m == i)){ fputc(lin[i], stdout); i = i + 1;} else i = m; }}void subline(char *lin, char *pat, char *sub){ int i, lastm, m; lastm = -1; i = 0; while((lin[i] != ENDSTR)) {m = amatch(lin, i, pat, 0);if ((m >= 0) && (lastm != m) ){ putsub(lin, i, m, sub); lastm = m; }if ((m == -1) || (m == i)){ fputc(lin[i], stdout); i = i + 1;} else i = m; }}not enoughvoid subline(char *lin, char *pat, char *sub){ int i, lastm, m; lastm = -1; i = 0; while((lin[i] != ENDSTR)) {m = amatch(lin, i, pat, 0);if ((m >= 0) && (lastm != m) ){ putsub(lin, i, m, sub); lastm = m; }if ((m == -1) || (m == i)){ fputc(lin[i], stdout); i = i + 1;} else i = m; }}P_f (A) = tilde P (A | A & !B)P_t (A) = tilde P (A | !(A&!B))Program PredicatesA predicate is a proposition about any program propertiese.g., idx < BUFSIZE, a + b == c, foo() > 0 … Each can be evaluated multiple times during one executionEvery evaluation gives either true or falseTherefore, a predicate is simply a boolean random variable, which encodes program executions from a particular aspect.Evaluation Bias of Predicate PEvaluation biasDef’n: the probability of being evaluated as true within one executionMaximum likelihood estimation: Number of true evaluations over the total number of evaluations in one runEach run gives one observation of evaluation bias for predicate PSuppose we have n correct and m incorrect executions, for any predicate P, we end up withAn observation sequence for correct runsS_p = (X’_1, X’_2, …, X’_n)An observation sequence for incorrect runsS_f = (X_1, X_2, …, X_m)Can we infer whether P is suspicious based on S_p and S_f?Underlying PopulationsImagine the underlying distribution of evaluation bias for correct and incorrect executions are and S_p and S_f can be viewed as a random sample from the underlying populations respectivelyOne major heuristic is The larger the divergence between and , the more relevant the predicate P is to the bug0 1ProbEvaluation bias0 1ProbEvaluation biasMajor ChallengesNo knowledge of the closed forms of both distributionsUsually, we do not have sufficient incorrect executions to estimate reliably. 0 1ProbEvaluation bias0 1ProbEvaluation biasOur ApproachAlgorithm OutputsA ranked list of program predicates w.r.t. the bug relevance score s(P)Higher-ranked predicates are regarded more relevant to the bugWhat’s the use?Top-ranked predicates suggest the possible buggy regionsSeveral predicates may point to the same region… …OutlineProgram PredicatesPredicate RankingsExperimental ResultsCase Study: bc-1.06Future WorkConclusionsExperiment ResultsLocalization quality metricSoftware bug benchmarkQuantitative metricRelated worksCause Transition (CT), [CZ05] Statistical Debugging, [LN+05] Performance comparisonsBug BenchmarkBug benchmarkDreaming benchmarkLarge number of known bugs on large-scale programs with adequate test suiteSiemens Program Suite130 variants of 7 subject programs, each of 100-600 LOC130 known bugs in totalmainly logic (or semantic) bugsAdvantagesKnown bugs, thus judgments are objectiveLarge number of bugs, thus comparative study is statistically significant.DisadvantagesSmall-scaled subject programsState-of-the-art performance, so far claimed in literature, Cause-transition approach, [CZ05]Localization Quality Metric [RR03]1st Example12354961087T-score = 70%2nd Example1237496105T-score = 20%8Related WorksCause Transition (CT) approach [CZ05]A variant of delta debugging [Z02]Previous state-of-the-art performance holder on Siemens suitePublished in ICSE’05, May 15, 2005Cons: it relies on memory abnormality, hence its performance is restricted.Statistical Debugging (Liblit05) [LN+05]Predicate ranking based on discriminant analysisPublished in PLDI’05, June 12, 2005Cons: Ignores evaluation patterns of predicates within each executionLocalized bugs w.r.t. Examined CodeCumulative Effects w.r.t. Code ExaminationTop-k SelectionRegardless of specific selection of k, both Liblit05 and SOBER are better than CT, the current state-of-the-art holderFrom k=2 to 10, SOBER is better than Liblit05 consistentlyOutlineEvaluation Bias of PredicatesPredicate RankingsExperimental ResultsCase Study: bc-1.06Future WorkConclusionsCase Study: bc 1.06bc 1.0614288 LOCAn arbitrary-precision


View Full Document

Purdue CS 59000 - Statistical Debugging

Documents in this Course
Lecture 4

Lecture 4

42 pages

Lecture 6

Lecture 6

38 pages

Load more
Download Statistical Debugging
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Statistical Debugging and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Statistical Debugging 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?