In reliability design, often, there is scarce data for constructing probabilistic models. Probabilistic models whose parameters vary in known intervals could be more suitable than Bayesian models because the former models do not require making assumptions that are not supported by the available evidence. If we use models whose parameters vary in intervals we need to calculate upper and lower bounds of the failure probability (or reliability) of a system in order to make design decisions. Monte Carlo simulation can be used for this purpose, but it is too expensive for all but very simple systems. This paper proposes an efficient Monte-Carlo simulation approach for estimation of upper and lower probabilities. This approach is based on two ideas: a) use an efficient approach for reliability reanalysis of a system, which is introduced in this paper, and b) approximate the probability distribution of the minimum and maximum failure probabilities using extreme value statistics. The proposed approach is demonstrated on calculation of the maximum and the minimum of probabilities of failure of a dynamic system.