Perception is a critical component of high-integrity applications of robotics and autonomous systems, such as self-driving cars. 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 mon- itor safe operation. Despite the paramount importance of perception, currently there is no formal approach for system-level perception monitoring. This paper investigates runtime monitoring of perception systems. We formalize the problem of runtime fault detection and identification in perception systems and present a framework to model diagnostic information using a diagnostic graph. We then provide a set of deterministic, probabilistic, and learning-based algorithms that use diagnostic graphs to perform fault detection and identification. Moreover, we investigate fundamental limits and provide deterministic and probabilistic guar- antees on the fault detection and identification results. We conclude the paper with an extensive experimental evaluation, which recreates several realistic fail- ure modes in the LGSVL open-source autonomous driving simulator, and applies the proposed system monitors to a state-of-the-art autonomous driving software stack (Baidu’s Apollo Auto). The results show that the proposed system moni- tors outperform baselines, have the potential of preventing accidents in realistic autonomous driving scenarios, and incur a negligible computational overhead.