Power system protection plays a very significant role in the reliable operation of the power grid, by safeguarding the personnel, equipment, and property against any undesirable events. These protection systems are traditionally analyzed using computer simulation and physical testing. However, the sampling-based nature of these analysis techniques does not allow us to cover all the possible scenarios and thus the resulting protection systems may not guarantee complete protection. This fact can lead to partial or complete power loss/blackouts, which can have devastating consequences. Formal verification methods have been successfully used to overcome the incomplete analysis issues in many domains of engineering. We believe that their introduction in the analysis of protection systems can lead to more reliable power grid operations. With this motivation, we propose to formally verify the correctness and reliability of the conventional and dual setting directional overcurrent relays. In this regard, we propose the development of the generic Markovian models of the conventional and dual setting directional overcurrent relays. To illustrate the effectiveness of the developed models a simple three bus distribution system network is analyzed to formally verify the efficiency and reliability of these models using PRISM, which is a probabilistic model checking tool. Furthermore, the failure and success probabilities of isolation of the faulty section are also determined.