Recent studies have shown that hidden failures in the protective devices ha
ve a great impact on the power system reliability. In this paper, we provid
e the definitions of vulnerability and reliability of protection system to
numerically characterize this impact. A random search algorithm based on po
wer system heuristics is given for fast rare-event simulation of consecutiv
e relaying malfunctions in bulk power systems. We also propose an economica
l system upgrading strategy that can best enhance the protection system rel
iability under limited budget. Finally, we present the result of a case stu
dy on New York Power Pool (NYPP) 3000-bus system.