There have been a number of steganography embedding techniques proposed over the past few years. In turn, there has been great interest in steganalysis techniques as the embedding techniques improve. Specifically, universal steganalysis techniques have become more attractive since they work independently of the embedding technique. In this work, we examine the effectiveness of a basic universal technique that relies on some knowledge about the cover media, but not the embedding technique. We consider images as a cover media, and examine how a single technique that we call steganographic sanitization performs on 26 different steganography programs that are publicly available on the Internet. Our experiments are completed using a number of secret messages and a variety of different levels of sanitization. However, since our intent is to remove covert communication, and not authentication information, we examine how well the sanitization process preserves authentication information such as watermarks and digital fingerprints.
We prove that for all 0 ≤ t ≤ k and d ≥ 2k, every graph G with treewidth at most k has a 'large' induced subgraph H, where H has treewidth at most t and every vertex in H has degree at most d in G, The order of H depends on t, k, d, and the order of G. With t = k, we obtain large sets of bounded degree vertices. With t = 0, we obtain large independent sets of bounded degree. In both these cases, our bounds on the order of H are tight. For bounded degree independent sets in trees, we characterise the extremal graphs. Finally, we prove that an interval graph with maximum clique size k has a maximum independent set in which every vertex has degree at most 2k.