Radio frequency identification (RFID) is a noncontact automatic identification technology in the Internet of things. It is widely used in the construction of RFID system for the interconnection of things. RCIA is an ultralightweight RFID mutual authentication protocol (UMAP), which provides high security and claims to be resistant to desynchronization attack. Formal method is a powerful tool to analyze the security of cryptographic protocols. We analyze the RFID tag authentication protocol RCIA based on formal method. Model checker SPIN is used to verify the authenticity and consistency of the RCIA protocol. The results show that the RCIA protocol is vulnerable to synchronization attack, for which we propose a patching scheme based on the key synchronization mechanism to improve the protocol. Formal analysis and verification results of the improved protocol show that the improved RCIA protocol has higher security. An abstract protocol modeling method we proposed in this paper is used to build an abstract protocol model of RCIA protocol formally, which has important reference for the formal analysis of such ultralightweight RFID mutual authentication protocol. The proposed vulnerability patching scheme based on key synchronization is proved to be effective against desynchronization attack, and it can be applied to the design and analysis of such ultralightweight RFID mutual authentication protocol.