With the rapid advancement of CMOS and non-CMOS nanotechnologies, circuit reliability is becoming an important design parameter. In recent years, a number of reliability evaluation methodologies based on probabilistic model checking, probabilistic transition matrices, etc., have been proposed. Scalability has been a concern in the wide applicability of these methodologies to the reliability analysis of large circuits. In this paper, we discuss the similarities between these reliability evaluation methodologies and focus mainly on the scalability issue. In particular, we develop a scalable technique for the model checking-based methodology, and show how this technique can be applied to the other methodologies. We also develop a tool called SETRA that can be used to integrate the scalable forms of these methodologies in the conventional circuit design flow.