Negative bias temperature instability along with the presence of process variations has resulted in time-varying path criticalities. To ensure reliable circuit operation, aging sensors are used at the end of potential critical paths (PCPs) for delay monitoring. Optimization of the number of delay sensors requires accurate computational models for prediction of criticality and selection of PCPs. We identify a path as a PCP if its maximum global criticality over the lifetime exceeds a certain threshold. However, the global criticality of a path could vary nonmonotonically over the lifetime of the device. In this paper, we propose a framework for time-varying statistical static timing analysis (TV-SSTA), wherein the circuit delay is obtained as a collection of time-varying canonicals with breakpoints in time which define the end of validity of one and the start of the next canonical. We show that the global criticality of any path will be maximum either at t = 0 or at these breakpoints. Hence, criticality computation and PCP selection need to be done only at these time points, which typically is less than four. The TV-SSTA is integrated with a previously proposed criticality computation technique to identify the PCPs and the results are validated against Monte Carlo simulations. © 1993-2012 IEEE.