A Darwinian Genetic Algorithm for State Encoding Based Finite State Machine Watermarking

Matthew Lewandowski and Srinivas Katkoori
University of South Florida


This work presents a novel Darwinian Genetic Algorithm that builds upon the traditional genetic algorithm in the efforts to more accurately depict the process of natural selection through significant alterations inspired by Darwin’s ’On the Origin of Species’ and considerations to regularly observable practices in nature. We demonstrate the capabilities of this algorithm by employing it with an existing state encoding based watermarking system for sequential circuits that was previously hindered by attempting to na¨ıvely solve the subgraph isomorphism problem involved during the watermark embedding process. Wherein we are able to demonstrate maximal savings of 30%, 29%, and 20% over the current state-of-the-art in terms of literals, area, and delay required for synthesizing the watermarked finite state machines, respectively.