Software debugging and testing using the abstract diagnosis theory
Bibliographic record
Abstract
In this paper, we present a notion of observability and controllability in the context of software testing and debugging. Our view of observability is based on the ability of developers, testers, and debuggers to trace back a data dependency chain and observe the value of a variable by starting from a set of variables that are naturally observable (e.g., input/output variables). Likewise, our view of controllability enables one to modify and control the value of a variable through a data dependency chain by starting from a set of variables that can be modified (e.g., input variables). Consequently, the problem that we study in this paper is to identify the minimum number of variables that have to be made observable/controllable in order for a tester or debugger to observe/control the value of another set of variables of interest, given the source code. We show that our problem is an instance of the well-known abstract diagnosis problem, where the objective is to find the minimum number of faulty components in a digital circuit, given the system description and value of input/output variables. We show that our problem is NP-complete even if the length of data dependencies is at most 2. In order to cope with the inevitable exponential complexity, we propose a mapping from the general problem, where the length of data dependency chains is unknown a priori, to integer linear programming. Our method is fully implemented in a tool chain for MISRA-C compliant source codes. Our experiments with several real-world applications show that in average, a significant number of debugging points can be reduced using our methods. This result is our motivation to apply our approach in debugging and instrumentation of embedded software, where changes must be minimal as they can perturb the timing constraints and resource consumption. Another interesting application of our results is in data logging of non-terminating embedded systems, where axillary data storage devices are slow and have limited size.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
How this classification was reachedexpand
Full frame machine prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. The Gemma side is a direct model label for every work in the frame, read from the title-only record. The Codex side is a classifier learned from the 10,348 direct Codex labels and calibrated to design-weighted sample rates; fields without enough sample support carry no Codex call. Candidate is the union of the two sides; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels.
Distilled classifier scores by category (both heads)
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.003 | 0.011 |
| Meta-epidemiology (narrow) | 0.002 | 0.001 |
| Meta-epidemiology (broad) | 0.002 | 0.003 |
| Bibliometrics | 0.003 | 0.002 |
| Science and technology studies | 0.001 | 0.004 |
| Scholarly communication | 0.003 | 0.006 |
| Open science | 0.002 | 0.003 |
| Research integrity | 0.002 | 0.004 |
| Insufficient payload (model declined to judge) | 0.003 | 0.001 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from itClassification
machine, unvalidatedMachine predicted; a candidate call from one source (direct Gemma or distilled Codex), not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".