This paper presents an efficient on-line fault diagnosis methodology based on the extended symptom-fault association(ESFA) model. The proposed methodology offers both automatic construction of ESFAs from the digraph and on-line fault diagnosis by a parallel scheme. An ESFA is an association between a symptom and all the possible faults which may cause the symptom. Each fault candidate in an ESFA has ordinal information of fault propagation path and constraints such as current process states. These constraints attached to each fault candidate are tested during on-line diagnosis process to find a common set of candidates for the symptoms which may come from the plant. The advantages of the proposed methodology over previous methodologies are described using several signed digraphs available from the literature.