Reasearch On Rfid Protocal Reverse Analysis Based On State Machine Inference

Radio Frequency Identification(RFID)technology is widely used in the Internet of Things(Iot),and the RFID communication protocol is also one of the most common communication protocols used in the Internet of Things.Nowadays in Io T,a variety of wireless communication protocols emerges,thus effective security analysis tools are needed to ensure the safety and reliability of the protocols,and minimize the attacks from malware attacks targeting Io T system.Therefore,this thesis analyzes and studies the reverse analysis process and technology for RFID communication protocol,and proposes an improved sequence alignment algorithm combining n-gram algorithm with NW(Needleman-Wunshc)algorithm.This thesis mainly works on the following three aspects:(1)This thesis proposes an improved sequence alignment algorithm(Needleman-Wunsch ngram,NWN)that combines n-gram with NW algorithms.The existing NW algorithm is mainly aims at the biological information sequence with small character range and long sequence length,so its performance on the RFID message with short length is not as expected.Therefore,this thesis improves the classification process of the NW algorithm by adopting the idea that the occurring probability of the current character is influenced by the context,and provides data to the NW algorithm based on more accurate classification results,and improvises the NW algorithm to make its performance on RFID message data more accurate,and also reduces its time overhead when the amount of data is large.(2)Based on the RFID message and the protocol format extracted from it,in order to solve the problem of incomplete simplification in the state machine construction process,this thesis adopts a method based on Extended Finite State Machines(EFSM)to construct the state machine,which can generate an abstract description of the protocol behavior specification.In view of the problem that the generated state machine is not in the simplest form,this thesis adopts the K-Tail algorithm and field constraints to simplify the final output result,in order to output the simplest form of the state transfer process of the RFID protocol,which provides support for further data analysis.(3)Based on NWN algorithm and finite state machine algorithm,this thesis designs and implements a prototype system for reverse analysis of RFID protocol.The system can automatically analyze the collected RFID message data,and through pre-processing,message format extraction and state machine construction,finally the message format contained in the message data and the state transition process corresponding to the message data are obtained.The experiment results verify the feasibility and practicability of the method from the engineering perspective.