With the advancement of large-scale coordinated attacks, the adversary is shifting away from traditional distributed denial of service (DDoS) attacks against servers to sophisticated DDoS attacks against Internet infrastructures. Link flooding attacks (LFAs) are such powerful attacks against Internet links. Employing network measurement techniques, the defender could detect the link under attack. However, given the large number of Internet links, the defender can only monitor a subset of the links simultaneously, whereas any link might be attacked. Therefore, it remains challenging to practically deploy detection methods. This paper addresses this challenge from a game-theoretic perspective, and proposes a randomized approach (like security patrolling) to optimize LFA detection strategies. Specifically, we formulate the LFA detection problem as a Stackelberg security game, and design randomized detection strategies in consideration of the adversary's behavior, where best and quantal response models are leveraged to characterize the adversary's behavior. We employ a series of techniques to solve the nonlinear and nonconvex NP-hard optimization problems for finding the equilibrium. The experimental results demonstrate the necessity of handling LFAs from a game-theoretic perspective and the effectiveness of our solutions. We believe our study is a significant step forward in formally understanding LFA detection strategies.