{'fraction_non_alphanumeric': 0.03922826830937714, 'fraction_numerical': 0.012020876112251883, 'mean_word_length': 4.847173586793397, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Block Permutational Steganographic Algorithm for Scanned Documents and other Images

: Steganography studies the embedding of messages into cover mediums, while obscuring the fact that any message exists. A supplement to encryption, steganographic methods help to avoid attention from adversaries, who may take additional measures if made aware of such messages. Common forms of image steganography, such as Least Significant Bit steganography, alter the first-order statistics of a cover image, allowing for easier detection by methods such as the Wavelet Motion Analyzer. We study steganographic methods based on permutation of pixels in grayscale images, which do not share this disadvantage. A generalization of pixel-swapping methods, our algorithm identifies invariant sets of pixels and intensities, called Permissible Sets, within an image block, and allow their full permutation in the encoding or decoding of messages. This increase in the number of permissible permutations serves to reduce the detectability of our method, while increasing the bit-per-pixel embedding rate. Through direct implementation and comparison, we find our method to be an improvement over previous swap-based steganography for the Microsoft Research Cambridge dataset of general images, and a large improvement for the higher-resolution NoisyOffice dataset of scanned images.


Introduction
Digital communications, and the security of the information transmitted through those communications, have become a cornerstone of the modern web [1]. Encryption of data has been, by and large, the main defense to ensure the authenticity of transmitted or received data, and that secret data is not readable by adversaries. Despite this, increasingly sophisticated and oblique attack vectors have been developed to bypass cryptographic solutions. In addition, data breaches are a matter of concern, making it preferable that even stored data is not recognized as such [2,3]. As such, it has become increasingly worthwhile to combine encryption with data hiding, further enhancing security via data confidentiality [3].
Data hiding techniques may be divided into watermarking and steganography. The former field aims to keep the watermark resistant to attacks, but does not necessarily aim to keep the embedded information hidden [4]: the primary concern of steganography. Steganography is the embedding of messages in some medium, in some way that makes it nonobvious that the message exists. A supplement to encryption, steganography prevents an adversary from determining that there is any message to decode at all: a fact that, if known, could itself have security implications. Data known to be encrypted can be stored en masse for later decryption, in the event some weakness to the protocol is later discovered. More immediately, the sender or receiver may be targeted via indirect methods such as malware, deception, various social attacks, or through breaching the security of a data storage endpoint (particularly if the data is stored unencrypted). While these indirect methods do not break the encryption itself, they may nonetheless obtain its contents through some other weakness in the user's system or data storage. It is advantageous, therefore, to obfuscate the fact that any message exists at all to be targeted.
Though classical forms of steganography related to physical messages, steganography in the era of electronic communications relates to information hidden within multimedia files such as text, audio, images, or video [5]. Multiple Copyright © 2021 MECS I.J. Modern Education and Computer Science, 2021, 5, 42-57 means of steganography are possible, including small variations in font [6][7][8][9] or spacing [7,10,11] within a textual document. Also studied is the hiding of messages within a cover text [12,13] or audio [14][15][16]. The effectiveness of any such steganographic method is measured though both detectability (through steganalysis tools), as well as the embedding payload size allowed through the method [17]. There is generally a trade-off between these two factors: as detectability decreases, so does payload size, and vice versa [18]. Other concerns include transparency and robustness. Transparency refers to the lack of noticeable changes between cover and stego-file, while robustness is the resistance of the message against compression, scaling, and noise addition [1]. Image steganography, in particular, begins with a cover image and encodes a hidden message to produce a stego-image; the receiver of the image then decodes the message from the stego-image [1]. This type of steganography sees frequent use; the large number of transmitted bits, and difficulty in distinguishing a subtly-modified image, makes this medium advantageous for the task [19][20][21][22]. Common forms of image steganography, such as Least Significant Bit (LSB) steganography, involve the hiding of data within the least significant bits of pixels. While such methods have significant advantages-such as their usability in most images while being indistinguishable to the naked eye-they are known to alter the statistics of the cover image, allowing for easier detection [23][24][25][26][27]. Approaches relating to modified LSB, along with Multi-Level Steganography (MLS), have been explored. Ref. [17] modifies MLS based on dynamic encryption keys with an unlimited number of levels. Ref. [28] explores the use of a secret key to determine encoding/decoding positions in LSB steganography, while [29] studies an improvement of LSB via the use of a byte replacement table based on a secret key. We, however, take a different approach.
Swap-based methods have been previously studied, and have shown some promise in resisting the analyses that detect LSB steganography [30]. They-and, more generally, permutational methods-have the advantage of, unlike LSB, not modifying an image's first-order statistics, as pixels are only permuted, not modified. This obviates the entire class of detection methods that rely on said statistics.
Ref. [31] examines the characteristics of scanner noise with the aim of embedding hidden information within said noise. Their methodology involved the embedding of a noise signal into partially de-noised scans and, according to their analysis, could be detected with an accuracy of 0.862. One of their findings was that, at least for some models of scanner, the pixel values adhere to a normal distribution. Our permutational algorithm avoids, by construction, one of the stated limitations of theirs': that the color histogram is changed, and risks detection. Another approach of a similar paradigm, in which the cover source was modified based on knowledge of camera noise, was taken in [32].
A slight variation of the pixel-swapping algorithm is described in [33]. Their algorithm resists the Sample Pair Analysis [25], which estimates the embedding rate of a hypothetical message in any given image, but is detected by the Wavelet Motion Analyzer [34]. The approach of [33] is largely superseded by [35], which describes a variant block-based pixel-swapping algorithm based partially on comparisons with the block's mean value. Said algorithm was implemented, and evaluated based on detection by the Wavelet Motion Analyzer, for the purpose of comparison. In addition to the Wavelet Motion Analyzer, we also use additional methods to compare the algorithms: the Sample Pair Analysis [25] and Peak Signal Noise Ratio (PSNR) [3]. For both the NoisyOffice dataset [36][37][38] of scanned documents, and the MSRCv2 dataset [39] of more general images, Wavelet Motion Analyzer results indicate that the algorithm of [35] is outperformed by our own, while the other measures are either roughly comparable or improved. This paper is organized as follows. Section 2 details our methodology: Section 2.1 describes the algorithm, with the exception of the permutation-to-bitstring (or vice versa) subprocedures, which are described in Section 2.2. Section 2.3 examines the time complexity of the algorithm and its major subprocedures, while Section 2.4 details the actual computation time under testing. Section 2.5 describes the training and testing methodology. Section 3 describes the results of the testing, comparing our algorithm with that of previous work. Finally, we detail our conclusions in Section 4.

Methodology
This section describes first our encoding/decoding algorithm, followed by the experimental method for testing its detectability. We study the embedding of messages within 8-bit, grayscale images. We do so both for general images and a type of grayscale image of interest: scanned documents. Noise in scanned backgrounds is already expected, and provides a certain degree of plausible deniability.
We study steganographic methods based on permutation of pixels in grayscale images. The original studied methods were based on pixel-swapping, but said methods were generalized to allow for permutations within 2×2, regions. Eventual generalizations to n×n regions are forthcoming.

Algorithm
Both encoder and decoder may be conceptualized as having in common a deterministic image reader subroutine. Said subroutine divides an image into a grid of n×n blocks (some rows/columns may be left over if n does not divide the image Copyright © 2021 MECS I.J. Modern Education and Computer Science, 2021, 5, 42-57 size), then loops through the blocks using the order given by a base 2 van der Corput sequence [40]. (For example, denote by B the total number of blocks in the image. The fifth member of the van der Corput sequence is 5 8 , so the fifth block traversed would be the block whose index, in lexicographic order, is ⌊ 5 8 B⌋. Any repeating indices would be skipped in this traversal.) Within each block, the permissible sets of intensities are determined, for use within the encoder/decoder. Because the permissible sets are, by design, an invariant, both encoder and decoder read the same ones. After the permissible sets have been read, the encoder permutes said sets based on the encoded data. The decoder, on the other hand, deduces which permutation was used in order to decode the encoded message. A permissible set is understood to include the number of occurrences of each intensity (in short, the permissible set of intensities is a multiset), along with the set of pixels corresponding to those intensities. A permutation of a permissible set is a permutation of intensities over the same underlying pixels. An intensity value may be shared by more than one pixel, allowing for different permutations to yield the same intensities over the permissible set pixels. Such permutations are called indistinguishable.
Permissible sets may have repeated intensities; this allows for a greater number of allowed permutations than a pure swap-based method, increasing the bit-per-pixel rate of the encoding. The restriction is that the intensities of any two permissible sets must be disjoint; that is, all instances of an intensity value must belong to a single permissible set, to avoid ambiguity.
Other restrictions are also possible: the one we use is to designate an intensity limit L and require that any two intensities within the permissible set may be swapped by a sequence of transpositions, each of intensity difference at most L. More precisely, we require that: Definition 1 (Sequence-Level Intensity Limit). For each two intensities x,y in a permissible set, there must exist a sequence x 1 ,...,x j of intensities, also in the permissible set, such that The permissible sets within a single pixel block are found via a greedy algorithm: at each step, find a maximum-sized multiset of intensities satisfying the above constraints; the set of pixels of any such intensity forms a permissible set. (The Greedy subprocedure is described as Algorithm 1, and the overall procedure summarized in Fig. 1.) When there is more than one maximum-sized permissible set candidate, ties are broken by taking the one containing the minimum intensity. Finally, a canonical ordering of permissible sets is required, in order to sort them: that ordering is by comparing minimum pixel coordinate contained within the set (the coordinates themselves are ordered lexicographically). In general, for any multiset { 1 1 , … , } , the number of distinct permutations is given by [41,42]: Denote by 1 , … , the permissible sets in sorted order, and denote the number of distinct permutations for each as | | = φ(S ). Because intensities are (by construction) disjoint between sets, the total number of possible permutations is their product, = | 1 | • … • | |. Denote by the index of the block the reader is currently looping through, and define = ⌊log 2 ⌋ to be the number of digits that may be encoded in this block. The encoder receives, as input, a b-digit bitstring, which it interprets as an unsigned integer . We offset by the block index to obtain: I.J. Modern Education and Computer Science, 2021, 5, 42-57 is then represented as a multi-radix number, with radixes | 1 |, … , | |: The encoding then proceeds by permuting each , according to Section 2.2: the | | th indexed permutation is chosen for , relative to a known base map. Conversely, the decoder reverses these steps. The permutation of each is read, its index determined (see, again, Section 2.2), and set as the digit | | . From there, construct the multi-radix number Finally, remove the offset: and interpret as a b-digit bitstring, to yield the bitstring stored in this block. See Fig. 3 for an overview and example of this encoding process, and Fig. 4, similarly, for the decoding process. The only remaining detail is that the encoder must pre-encode the message length, as a fixed-length integer, prior to the actual message (at the beginning of the image block loop). Conversely, the decoder reads said length, prior to decoding the message. In this manner, the stopping point of the message is known by both.

Permutation Subprocedures
In the sequel, we consider the pixels of an image to be lexicographically ordered by coordinate: (x 1 ,y 1 ) ≤ (x 2 ,y 2 ) ⇐⇒ (x 1 < x 2 )∨(x 1 = x 2 ∧y 1 ≤ y 2 ). A bitstring can be encoded into a permissible set using the following high-level algorithm: begin with a known base map of pixel to intensity; the simplest such map is the one that arises from sorting the intensities of a permissible set from lowest to highest among the [lexicographically-ordered] pixels. From there, various possible permutations are possible. One can describe a permutation-lexicographic ordering over all such permutations: ≤ if, on the minimum pixel p where ( ) ≠ ( ), one has ( ) ≤ ( ).
Given any permissible set S, one may thereby create a permutation-lexicographically sorted list R of all such permutations-or, more accurately, of all distinct permutation results; as permissible sets may contain multiple instances of the same intensity, different permutations may result in indistinguishable mappings of pixel-to-intensity.
The list R can then be used to encode a number i (where 0 ≤ i < |S|): starting from the known base map, enact the permutation result corresponding to index i. Conversely, the decoder determines the index of the permutation result used, thereby extracting the number i.
In practice, the list R of sorted permutation results is purely conceptual: it is far more efficient for an encoder or decoder to compute the index matching a permutation result indirectly.
Let φ, the formula for the number of unique permutations of a generic multiset, be as in Equation (1 = ∑ number of permutations with prefix 1 … such that τ k+1 < +1 In pseudocode, is written as Algorithm 2. In reverse, an encoder uses as its main subprocedure the index-to-permutation assignment function ∶ {0, … , | | − 1} → which, given a target index integer, computes the permutation in the list R corresponding to said index. It avoids a full linear search by treating the possible permutation results as a multi-level tree, the level i nodes corresponding to the possible intensities of the ith pixel of a permutation result (with previous pixels fixed via the ancestor nodes). φ, from Equation (1), computes the total number of permutations down any particular ith-level node, without requiring actual traversal. Thus, by looping through the ith level nodes in order of increasing intensity, and stopping before the cumulative number of permutations has exceeded the target index, the tree traversal corresponding to said index is recursively computed. The pseudocode description of this subprocedure is Algorithm 3.

Time Complexity
We estimate the time complexity of the various algorithms. Let B denote the block size in pixels (for example, B = 4 for a 2×2 block).
The formula ϕ, given by Equation (1), plays a part in several algorithms. If we define n = k 1 +...+ k j , the time complexity is O(n), which in practice is O(B). In the numerator, the number of terms being added is at most n, attained when k 1 = ... = k j = 1. Since k 1 +...k j = n, the number of terms multiplied to attain the factorial is at most n as well. For the denominator, since again, k 1 +...k j = n the number of terms being multiplied in all the k i ! terms is at most n, as is the product itself.
For  Table 1 lists the average computation times, both of our algorithm and of [35], for the MSRCv2 [39] and NoisyOffice [36][37][38] datasets. Tests were run on an Intel 7th Generation Core i7 notebook computer. The proposed algorithm is approximately 2-3 times slower for the measured datasets, which is a trade-off for its reduced detectability. Both algorithms, however, have an acceptable runtime for typical usage, particularly if only a few images need to be processed.

Training and Testing
The steganography methods are trained and tested on two datasets: the NoisyOffice [36][37][38] dataset of scanned documents, and the MSRCv2 [39] dataset of more general images. The two datasets are evaluated separately. The NoisyOffice dataset contains "RealNoisyOffice" and "SimulatedNoisyOffice" subsets; the former is further partitioned into "single resolution" and "double resolution" images. All tests in this paper are run on the "single resolution" images of the "RealNoisyOffice" subset.
For each tested bit-per-pixel rate, the two datasets are augmented with a duplicated copy of the images. A message of random bits, simulating encrypted data, is embedded in each duplicate image using the steganography method being tested.
For each image-with or without an encoded message-the Wavelet Motion Analyzer [34] is used to create a feature. As in [35], a Fischer linear classifier is used to discriminate between features resulting from images containing, or not containing, a message. 10-fold cross-validation is used to train and evaluate said classifier. The Area Under the Receiver Operating Curve (AROC) is used to evaluate the detectability of the steganography method-the average AROC across the ten folds is taken.
In addition to the Wavelet Motion Analyzer, the algorithms are also compared using Sample Pair Analysis [25] and Peak Signal Noise Ratio (PSNR) [3].

Results and Discussion
We measure the detection rates for our algorithm. Results are shown in Table 2 and Table 3, for the NoisyOffice dataset of scanned images [36][37][38] and the MSRCv2 dataset of more generic images [39], respectively. The main measurement of detectability is the Area under the Receiver Operating Curve (AROC). The lower the area, the less detectable the corresponding steganographic method. Our method has shown low detectability, for given bit-per-pixel encoding rates, as well as allowing for higher encoding rates at the cost of detectability.
We compare our own algorithm with a prior permutational algorithm, of which the best performing is the pixel swapbased algorithm of [35]. We implement the algorithm of [35] in order to directly compare performance using the same sample images. Certain parameters of [35] were open to specification. To ensure that their algorithm effectiveness was being favorably estimated, we tested using a range of open parameters for each bit-per-pixel rate, taking the best-performing result for each such rate. This comprehensive approach provides an ideal-performance measure, one perhaps even better than would ordinarily be realistic (as parameters would ordinarily be fixed, rather than the best-performing ones chosen). This approach is not used for our own algorithm, which is left with no unfixed parameters. Fig. 5 and Fig. 6 show graphs of AROC results against bit-per-pixel rates, for the respective datasets. Tested in each graph is the algorithm of [35] (under the aforementioned optimized parameters) along with our own method, under a 2 ×2 block size and varying choices of the Max Intensity Difference parameter. (The number of data points varies per steganographic method, as some do not support higher bit-per-pixel rates.) The results corresponding to [35] are shown in Table 4 and Table 5, for the NoisyOffice and MSRCv2 datasets, respectively. These may be compared to our own results in Table 2 and Table 3 be less detectable for each tested bit-per-pixel rate, under the tested Max Intensity Difference parameters. For the NoisyOffice dataset in particular, our proposed algorithm has proved to be far less detectable, by as much as 49%, as measured by AROC. For the MSRCv2 dataset, our algorithm is still less detectable, but the improvement is not to as great a degree. Both algorithms, we found, are uniformly more detectable under the NoisyOffice dataset. The reasons for this-and, in particular, for the high detectability of [35] with this dataset-are unclear, and to be followed up upon. Possibilities range from NoisyOffice's higher resolution, to unexpected sources of noise within the MSRCv2 dataset. An answer to this question may help to characterize the images best suited for comparable steganographic methods.
In addition to the Wavelet Motion Analyzer method, two additional steganalysis systems were tested: Peak Signal Noise Ratio (PSNR) and Sample Pair Analysis. PSNR measures the change made to a stego-image [3] and ranges between 0 and 100; higher values are preferred. Sample Pair Analysis outputs a value estimating the length of a hidden message, as a proportion of the image; values closer to zero are preferred. As with the Wavelet Motion Analyzer test, we took the best result of [35] for a range of unspecified parameters, in order to favorably estimate their algorithm effectiveness. The proposed algorithm has a better PSNR for the same bit-per-pixel embedding rates (the precise difference depending on the Max Pixel Intensity Difference parameter). The Sample Pair Analysis results were roughly comparable, both algorithms' estimated hidden message lengths being close to zero. See Table 4 and Table 5, for results corresponding to [35]; our own results are found in Table 2 and Table 3.
As our algorithm improves upon [35], it appears to provide the best detectability results within the class of permutation-based steganographic methods. The trade-off is a longer operation time per message length, which may make the algorithm less usable for some applications. This is not a concern for a reasonable number of images. (Additionally, overly long messages, requiring a large number of cover images, may draw an adversary's attention regardless).