Genetic Algorithms for Protocol Validation

摘要

We present a first attempt in applying a genetic algorithm for checking the correctness of communication protocols (expressed as a pair of communicating FSMs). The GA measures the fitness of a given string by making use of a protocol simulator. Every string in the population is a trace of the execution of the protocol. The simulator evaluates the trace by running it, provoking changes and messages exchanges in the states of every FSM. The fitness of a string (trace) is high if the string detects a deadlock or if useless states or transitions are encountered. We are interested in testing the suitness of the GA search in such a domain. We have tested this genetic validation on a hand-made protocol and on the Transmission Control Protocol (TCP).