Depending on the structured peer-to-peer networks, the P2P botnets are the main threats of the Internet in the future. In this paper, a formal mathematical P2P botnet propagation model is built based on a deep analysis of two typical structured P2P protocols, Chord and Kademlia. This model, it integrates different factors, such as structured P2P protocols, two-factor immunizations, and host online rates to describe the structured P2P botnet propagation mechanisms comprehensively. Meanwhile, in order to evaluate the model effectiveness, simulate the P2P botnets propagation, the difference between the theoretical model and the simulation is used to verify the model efficiency. The experiments prove the correctness of the theoretical model also verify the different influences of structured P2P protocols, immunization mechanisms, and the host online rates on P2P botnet propagation. Moreover, through simulating P2P network with millions of nodes, it can be shown that the propagation model is correct and valid in large scale network, which provides a theoretical basis for botnet detection and prevention.