Probabilistic Diagnosis Methods For Multi-Fault Programs

Automation software fault diagnosis technique plays an important role in ensuring the quality of software. However, most of the existing techniques assume that there is only one fault in the program, which is not realistic in the practical program. Unlike single-fault program, the inherent uncertainty of multiple-fault program is more complex, and makes that the existing single-fault techniques cannot deal with multiple-fault program.This thesis mainly analyzes the software fault diagnosis techniques of program slicing, model-based software debugging, statistical-based fault localization, and probabilistic graph model diagnosis. In order to treat for the problems, such as test case dependency, fault propagation, and fault masking generated by the inherent uncertainty of multi-fault program, this thesis formalizes the multi-fault program diagnosis problem, concentrates on the extended models and algorithms of probabilistic graph model diagnosis, and has achieved the following research work:(1) Infection graph and its probabilistic diagnosis technique (IGADER), which takes BARIENL a step further, is proposed to deal with the test case dependency, fault propagation and fault masking of the multi-fault programs. Infection graph employs infection connections to describe the interaction among statements from the perspective of dependences. Then IGADER identifies conflict, generates and distinguishes candidate diagnosis. To verify the effectiveness of IGADER, it compares its diagnostic accuracy with Tarantula, Ochiai, and BARINEL by using different scales of single-fault and multi-fault real-world programs. The experimental results show that IGADER is better than others.(2) Based on the control dependences and data dependences among statements, a two layer Bayesian Network (PCEG) of causal effect model is established by introducing Markov Cover. PCEG combines the noisy-or model-based "top-down" reasoning with the Bayesian theory-based "bottom-up" reasoning to capture (cyclic) the fault propagation in control flow and data flow. With the same experimental data and the different size of test case, the experimental results show that PCEG depicts the deeper causality among statements than Tarantula, Ochiai, and B ARINEL. Thus, PCEG has lower sensitivity of the size of test case, and can control the negative impact of the diagnostic accuracy caused by the execution information similarity that generated with loop statements.(3) To focus on the problem of "false dependence" in software development, an extended hidden markov model and its probabilistic diagnosis technique EHMM is proposed. By taking program feature (such as basic block) as "hidden" variable, EHMM sets up a hidden markov model with each failed test case, and employs probabilistic reasoning to divided "hidden" variables into faulty or healthy. Then for faulty variables, EHMM ranks their suspiciousness as diagnostic result. To verify the performance of EHMM, some real "false dependency" programs, which contain one fault, two faults, or three faults, respectively, are designed and used to do experiments. The experimental results show that EHMM is more accuracy than PCEG, IGADER, Tarantula, and Ochiai for dealing with "false dependency" problem.(4) In order to apply IGADER, PCEG and EHMM into practice, a probabilistic diagnosis system PGDS is designed and implemented. PGDS can be used to handle the multi-fault software diagnosis and cognitive ability of student diagnosis, and has obtained remarkable results.