Critical Path Analysis is always an important task in timing verification. For today’s nanometer IC technologies, process variations have a significant impact on circuit performance. The variability can change the criticality of long paths [1]. Therefore, statistical approaches should be incorporated in Critical Path Analysis. In this paper, we present two novel techniques that can efficiently evaluate path criticality under statistical non-linear delay models. They are integrated into a block-based Statistical Timing tool with the capability of handling arbitrary correlations from manufacturing process dependence and also path sharing. Experiments on ISCAS85 benchmarks prove both accuracy and efficiency of these techniques.