This paper presents a new approach to solve Fault Detection Problem with Lazy Spread (FDPL) that arises in many fault tolerant real world systems with little opportunities of maintenance during their operations and significant failure interactions between the sub-systems/components. As opposed to cascading faults that spread to most of the system almost instantaneously, FDLP considers fault resistant systems where the spread of failures is rather slow (lazy), i.e., only a small fraction of the components are faulty at the time of inspection (maintenance), and accurate detection of the faulty components is of critical importance to restore system performance and stop further demage. Despite the practical importance, there are not enough studies in the literature to address FDLP, mostly due to the difficulties to overcome computational intractability for solving large size problem instances. To address this urgent yet challenging problem we use graph theory concepts to model the diagnosis problem with a novel integer programming formulation and devise an efficient branch-and-cut algorithm to solve it. Extensive numerical experiments on realistic problem instances attests to the superior performance of our approach, in terms of both computational efficiency and prediction accuracy, compared to the state-of-the-art in the literature.