Ultralightweight mutual authentication protocols (UMAP) of Radio frequency identification (RFID) systems have attracted much attention from researchers. Many studies reveal that most of UMAP suffer malicious attack. To improve security of UMAP, formal analysis is performed with Simple promela interpreter (SPIN). Two typical UMAPs, which are RCIA and RAPP, are selected as our case study. A protocol abstract modeling method is presented to make UMAP can be formalized simply. Using SPIN, verification results show that RCIA and RAPP are both vulnerable against desynchronization attack. A Generalized model of UMAP (G-UMAP) and a general patching scheme are presented for resisting the attack. To validate the patching scheme, formal verification is then performed for the improved protocol. SPIN verification shows that the improved RCIA and RAPP both gain higher security. The above proposed modeling method has great significance for similar UMAP analyzing, and the proposed patching scheme is proved to be practical and reliable.