Model formalny dla problemu lokalizacji błędów w kodzie programu

Abstract

There are several criteria for testing program correctness. In this paper we deal with the problem of automatic software testing under the assumption that the set of tests (assertions) is given for selected blocks of code. We simplify the analysis by assuming that the program being tested contains exactly one bug, but this does not lead to loss of generality. We consider some practical aspects of the above problem and a graph-theoretical model in general as well as some chromatic aspects of a graph searching model in particular. Istnieje szereg sposobów badania poprawności programów komputerowych. W artykule podejmujemy problem automatycznego testowania oprogramowania przy założeniu, że dany jest zbiór testów (asercji) dla poszczególnych fragmentów kodu. Dla uproszczenia analizy zakładamy, że badany fragment kodu zawiera dokładnie jeden błąd, co nie zmniejsza ogólności rozważań. W artykule analizujemy praktyczne aspekty powyższego problemu oraz rozważamy model teoretyczny oparty na teorii grafów, w szczególności jej chromatyczne aspekty oraz pewien model przeszukiwania grafu opisującego strukturę programu.