Intelligent false data injection on load measurements can trigger false relay operation (FRO) of frequency-based protection relays, affecting the power system frequency and thus threatening the security of power systems. In this paper, we propose an optimization-based formal model to find the optimal false data injection attack (OFDIA) with the minimum required time leading to an FRO. The proposed model considers the dynamic behavior of the power system in an optimization framework to find the optimal size of attacks over multiple generators’ dispatching cycles to minimize the attack launch time. Using the proposed formal modeling, we study the impact of power system parameters, including inertia, governor’s droop and time constant, and the attacker’s accessibility to loads on the attack success and launch time. The results demonstrate that systems with low inertia are more vulnerable to FDIAs while systems with higher inertia are more secure as fewer generator protection relays are impacted by FRO. In addition, we show that securing more load meters can increase the time for launching an attack in the system. Moreover, our studies show that a combination of large values of the governor’s time constants and small values of the governor’s droops can raise the time of successful attacks, making the system more secure against FDIAs.