Passive testing has proved to be a powerful technique for protocol system fault detection by observing its input/output behaviors yet without interrupting its normal operations. Various techniques for passive testing on Extended Finite State Machine (EFSM) exist such as by invariants and by interval determination, which are not very costy in terms of complexity but that also don?t detect every errors. To improve the fault detection capabilities a backward checking method was proposed. It analyzes in a backward fashion the input/output trace from passive testing and its past. It effectively checks both the control and data portion of a protocol system and is able to detect every errors, but with a higher complexity. The purpose of the present paper is then to propose possible parallel algorithms and architectures to improve the backward passive testing approach by narrowing down its maximal time complexity and transforming it into the first real-time exhaustive passive testing approach. We present the backward algorithm and its parallel versions, study their complexity, and report results on various communication and routing protocols.