In this letter, we analyze the security of a long term evolution/system architecture evolution-based network in the presence of de-synchronization attack. For a random mobile user, with the mobility management entity residence time distributed as a Hyper-Erlang random variable, we derive closed form expressions for the distribution of key exposure time, expected volume of exposed packets, and expected additional signaling overhead rate. Furthermore, we present a novel framework for a cellular operator to select the trade-off between security and computational complexity for various practical scenarios. Finally, we verify the proposed results through extensive simulations. © 1997-2012 IEEE.