  Perception is a critical component of high-integrity applications of robotics
and autonomous systems, such as self-driving vehicles. In these applications,
failure of perception systems may put human life at risk, and a broad adoption
of these technologies requires the development of methodologies to guarantee
and monitor safe operation. Despite the paramount importance of perception
systems, currently there is no formal approach for system-level monitoring. In
this work, we propose a mathematical model for runtime monitoring and fault
detection and identification in perception systems. Towards this goal, we draw
connections with the literature on diagnosability in multiprocessor systems,
and generalize it to account for modules with heterogeneous outputs that
interact over time. The resulting temporal diagnostic graphs (i) provide a
framework to reason over the consistency of perception outputs -- across
modules and over time -- thus enabling fault detection, (ii) allow us to
establish formal guarantees on the maximum number of faults that can be
uniquely identified in a given perception system, and (iii) enable the design
of efficient algorithms for fault identification. We demonstrate our monitoring
system, dubbed PerSyS, in realistic simulations using the LGSVL self-driving
simulator and the Apollo Auto autonomy software stack, and show that PerSyS is
able to detect failures in challenging scenarios (including scenarios that have
caused self-driving car accidents in recent years), and is able to correctly
identify faults while entailing a minimal computation overhead (< 5 ms on a
single-core CPU).
