Back to search

University of South Florida

Approximate Sub-Graph Isomorphism For Watermarking Finite State Machine Hardware

Abstract

dc:description

We present a method of mitigating theft of sequential circuit Intellectual Property hardware designs through means of watermarking. Hardware watermarking can be performed by selectively embedding a watermark in the state encoding of the Finite State Machine. This form of watermarking can be achieved by matching a directed graph representation of the watermark with a sub-graph in state transition graph representation of the FSM. We experiment with three approaches: a brute force method that provides a proof of concept, a greedy algorithm that provides excellent runtime with a drawback of sub-optimal results, and finally a simulated annealing method that provides near optimal solutions with runtimes that meet our performance goals. The simulated annealing approach when applied on a ten benchmarks chosen from IWLS 93 benchmark suite, provides watermarking results with edge overhead of less than 6% on average with runtimes not exceeding five minutes.

Degree

thesis:*
Level thesis:degree_level
Thesis
Discipline thesis:degree_discipline
Engineering Computer Science
Grantor
University of South Florida
Year dc:date
2013

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Meana, Richard William Piper
Contributors dc:contributor
  • Srinivas Katkoori

Subjects

dc:subject × 6

Rights

Language dc:language
EN-US

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.usf.edu/etd/4728

Chain of custody

source
Harvested from
University of South Florida
Base URL
digitalcommons.usf.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Meana, Richard William Piper. Approximate Sub-Graph Isomorphism For Watermarking Finite State Machine Hardware. Thesis thesis, University of South Florida, 2013. https://digitalcommons.usf.edu/etd/4728