This paper considers the problem of certifying the performance of a class of model-based fault detection schemes. The underlying plant is assumed to be a linear time-varying (LTV) system subject to a Markov-switching fault input. The fault detection scheme consists of two parts: an LTV component that produces a scalar residual and a static nonlinear function that infers the presence of a fault based on this residual. Probabilistic performance metrics are presented and the complexity of computing these metrics is analyzed. It is shown that under a set of realistic assumptions, this complexity is reduced to polynomial time. An aerospace example, involving a pitot-static probe subject to random bias faults, is used to demonstrate the usefulness of this analysis.