Putting detectors in their place [program monitoring]

In this paper, we address the problem of locating detectors in a given program under resource constraints. A detector is a program component that asserts the validity of a predicate in a program. The detector location problem is to identify which program actions need to be monitored by detectors such that certain given dependability properties are met. In this paper, we focus on the following dependability properties: (i) high detection coverage, (ii) low detection latency, and (iii) low false alarms rate. Our main contributions are: (i) we first provide a formal definition of the detector location problem under resource constraints, and (ii) we subsequently show that the problem is NP-complete, (iii) we investigate a special case of the detector location problem that can be solved in polynomial time, and present a sound and complete algorithm that solves the problem. We present an example to show the applicability of our approach, which is intended in the area of dependable embedded systems.