Hardening reliability-critical gates in a circuit is an important step to improve the circuit reliability at a low cost. However, accurately locating the reliability-critical gates is a key prerequisite for the efficient implementation of the hardening operation. In this paper, a probabilistic-based calculation method developed for locating the reliability-critical gates in a circuit is described. The proposed method is based on the generation of input vectors and the sampling of reliability-critical gates using uniform non-Bernoulli sequences, and the criticality of the gate reliability is measured by combining the structure information of the circuit itself. Both the accuracy and the efficiency of the proposed method have been illustrated by various simulations on benchmark circuits. The results show that the proposed method has an efficient performance in locating accuracy and algorithm runtime.