Fault Diagnosis of Embedded Software using Program Spectra∗

In this paper we present a technique to automatically diagnose errors detected during software testing. With diagnosis we mean localization of the fault that causes these errors. Strictly speaking, this belongs to the debugging phase, rather than to the testing phase of the software development cycle, but the technique is well suited for integration with (automated) testing, and enhances the information that can be extracted from this phase. We assume that testing involves a number of different runs (or transac-tions, usage scenario’s, etc.) of the same software. Per run, we record a so-called program spectrum (see, e.g., [2]). The particular form of program spectrum that we are interested in is an array of Boolean flags that tells us which parts of the software were active during a run. This can be measured at different levels of granularity, for example, at component, class, or func-tion level, but also at the level of individual statements, or blocks of code. Together, the program spectra for a series of test runs form a binary matrix, whose row vectors correspond to the runs, and whose column vectors tell us in which runs a particular part of the software was active (see Figure 1). During testing, errors are detected in some of the runs. This information constitutes another column vector, the error vector, which can be seen as to correspond to a hypothetical part of the software that is responsible for the detected errors. The assumption is that the actual parts of the software whose column vectors resemble the error vector most, have a high probability of containing the fault. Basic data clustering techniques can be applied to ∗This work has been carried out as part of the TRADER project under the responsi-bility of the Embedded Systems Institute, and is partially supported by the Netherlands Ministry of Economic Affairs under the BSIK03021 program. N parts errors M runs x11 x12... x1N x21 x22... x2