On the theory of patching

We study the problem of patching, i.e., modifying the behavior of an existing system. We consider systems modelled as finite state machines (FSMs), and define edit operators for them based on a traditional fault model. We argue that sequences of edit operations can be considered as models of patches defining modifications to an FSM system. We utilize recent results in graph matching theory as mathematical foundations. We introduce a new type of problem which we call the optimal patch or optimal update problem: given an FSM M modeling the behavior of an existing system and an other machine M´ modeling a new design, find an optimal patch, i.e., the edit operations changing M to M´ that are minimal according to a given cost function associated with the edit operations. We analyze the complexity of the problem, and conclude that it is unlikely to have a polynomial time solution for it. We also show that the problem can be easily transformed to a state-space search problem, for which many heuristic approximation algorithms have been developed.