A method for verifying the performance of a real-time system modeled as a timed automaton. An abstract model of the system is checked against an initial Linear Temporal Logic specification. If a path to an undesirable state is found, the counterexample is validated or invalidated using negative cycle detection. If a negative cycle is detected, optimization is undertaken to identify a minimal infeasible fragment in the negative cycle. The specification is then refined to eliminate usage of the minimal infeasible fragment, and the abstract model is then checked against the refined specification.