c © 2011 Shankar Sadasivam GRAPH-BASED DECODERS AND DIVERGENCE-RATE ESTIMATORS FOR DATA-HIDING PROBLEMS BY SHANKAR SADASIVAM DISSERTATION Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Electrical and Comput er Engineering in the Graduate College of the University of Illinois at Urbana-Champaign, 2011 Urbana, Illinois Doctoral Committee: Professor Pierre Moulin, Chair Professor Richard E. Blahut Professor Thomas S. Huang Assistant Professor Todd P. Coleman Assistant Professor Paris Smaragdis Abstract In this thesis, we look closely at two fundamental problems tha t arise within the context of multimedia blind watermark decoding and t iming channels steganalysis. The central problem considered, loo sely speak- ing, is that of implementing optimal (or near-optimal) strategies at the receiver, which is typically tasked to perform reliable deco ding or de- tection, depending on the application at hand, in the presen ce of nu- merous unavoidable statistical uncertainties that are rathe r unique to the problem setup. A typical question we will be asking is, “Ca n we perform reliable decoding of hidden data in spite of the pres ence of unknown channel parameters?” or “How best can we detect prese nce of hidden data with unknown, and rather arbitrary, host and o bser- vation statistics?” While such questions are naturally rele vant from a practical viewpoint, we draw additional inspiration for our study from profound theoretical insights arising from our recent resea rch. As our solution to the first problem, we propose a new paradigm for blind watermark decoding in the presence of various signal dis tortion operations. Employing Forney-style factor graphs to model the water- marking system, we cast the blind watermark decoding problem as a probabilistic inference problem on a graph, and solve it via mess age- passing. We study a wide range of moderate to strong distortion s in- cluding scaling, amplitude modulation, fractional shift, arb itrary linear and shift invariant (LSI) filtering, and blockwise filtering, and sh ow that the graph-based iterative decoders perform almost as wel l as if they had exact knowledge of the distortion channel parameters . Other ii desirable features of the graph-based decoders include the fl exibility to adapt to other types of distortions and the ability to cope with the “curse of dimensionality” problem that seemingly results when the dis- tortion channel parameters’ space has high dimensionality. Th ese prop- erties are unlike most blind watermark decoders proposed to da te, and close an important computational gap in favor of deploying jo int estimation-decoding strategies (shown to be theoretically o ptimal in our earlier work) to cope with common signal distortions. For the second problem, we propose new tools for steganalysis o f queue- based stegocodes over covert timing channels. We propose a unive r- sal estimator for the Kullback-Leibler (KL) divergence-rate b etween the covertext process and the stegotext process. We empiricall y illus- trate the performance of our estimator on some simple queue-base d stegocodes and study its convergence properties. iii To Amma and Appa iv