A steganographer network corresponds to a graphic structure that the involved vertices (or called nodes) denote social entities such as the data encoders and data decoders, and the associated edges represent any real communicable channels or other social links that could be utilized for steganography. Unlike traditional steganographic algorithms, a steganographer network models steganographic communication by an abstract way such that the concerned underlying characteristics of steganography are quantized as analyzable parameters in the network. In this paper, we will analyze two problems in a steganographer network. The first problem is a passive attack to a steganographer network where a network monitor has collected a list of suspicious vertices corresponding to the data encoders or decoders. The network monitor expects to break (disconnect) the steganographic communication down between the suspicious vertices while keeping the cost as low as possible. The second one relates to determining a set of vertices corresponding to the data encoders (senders) such that all vertices can share a message by neighbors. We point that, the two problems are equivalent to the minimum cut problem and the minimum-weight dominating set problem.
The authors in @cite_6 have pointed that Eq. (2) is equivalent to solving the Steiner Tree Problem (STP) problem @cite_16 , which is NP-hard. The STP is seen as a generalization of two other combinatorial optimization problems, i.e., the shortest path problem and the minimum spanning tree (MST) problem. If the STP deals with only two terminals, it reduces to finding a shortest path. If all vertices are terminals, it is equivalent to the MST problem. Therefore, one may employ the existing approximation algorithms designed for the STP to find the suitable strategy for steganographic communication.
@cite_16 @cite_6
2027515293 2773381262
The Steiner tree problem on weighted graphs seeks a minimum weight subtree containing a given subset of the vertices (terminals). We show that it is NP-hard to approximate the Steiner tree problem within a factor 96 95. Our inapproximability results are stated in a parametric way, and explicit hardness factors would be improved automatically by providing gadgets and or expanders with better parameters. Steganography aims to conceal the very fact that the communication takes place, by embedding a message into a digit object such as image without introducing noticeable artifacts. A number of steganographic systems have been developed in past years, most of which, however, are confined to the laboratory conditions where the real-world use of steganography are rarely concerned. In this paper, we introduce an alternative perspective to steganography. A graph-theoretic model to steganography on social networks is presented to analyze real-world steganographic scenarios. In the graph, steganographic participants are corresponding to the vertices with meaningless unique identifiers. Each edge allows the two vertices to communicate with each other by any steganographic algorithm. Meanwhile, the edges are associated with weights to quantize the corresponding communication risk (or say cost). The optimization task is to minimize the overall risk, which is modeled as additive over the social network. We analyze different scenarios on a social network, and provide the suited solutions to the corresponding optimization tasks. We prove that a multiplicative probabilistic graph is equivalent to an additive weighted graph. From the viewpoint of an attacker, he may hope to detect suspicious communication channels, the data encoder(s) and the data decoder(s). We present limited detection analysis to steganographic communication on a network.