Abstract
Advanced visual tools are useful to provide additional information for modern information warfare. 2D spatial distributions of random sequences play an important role to understand properties of complex sequences. This chapter proposes time sequences from a given logical function of 1D cellular automata in both Poincare map and conjugate map. Multiple measure sequences of Markov chains can be used to display spatial distributions using conjugate maps. Measure sequences are recursively produced by different logical functions generating maps. Possible complementary feature exists between pair functions. Conjugate symmetry relationships between a pair of logical functions in conjugate maps can be observed.
This work was supported by Yunnan Advanced Overseas Scholar Project.
You have full access to this open access chapter, Download chapter PDF
Similar content being viewed by others
Keywords
1 Introduction
Random sequences are widely used in many security-based applications such as security communication, cryptology coding, and information security systems [1]. To make proper analysis, Markov chain methodologies and technologies provide a series of important methods and tools to help analyzers decoding process [2,3,4]. In modern information warfare, it is essential for analyzers to detect and decrypt the opponent’s communications using information acquisition toolkits from real coding sequences [5].
Information Warfare describes terms of “actions” executed to achieve a sought outcome—denial, exploitation, corruption and destruction of an opponent’s “information” and related functions, and prevention of such “actions” executed by an opponent [6].
The battle between the obscurers and those who sought to break the codes has been a continual one, but it reached a new level of stature and importance during World War II with its decryption of Germany’s Enigma messages. Historic events are approved that statistical and probability tools are extremely important in Information Warfare applications. This battle of wits fought by British mathematicians and statisticians shortened World War II and ushered in the age of information warfare [7].
Prerequisite of executing these attack actions is thoroughly understood by the mechanism of information encryption that opponent uses [8]. In information warfare, secured communications among opposite parts may use public networks. It is feasible to capture relevant information for further analysis. Different quantitative tools and methods are useful to provide additional information in decoding process. Variant features play an important role for measurement and analysis of random sequences [9].
Because of the implicated expression of functions that generate random sequences, it is hard to get the characteristic of random sequences from the function and coding sequences themselves [10]. Traditionally, time sequence map and Poincare map are the two most popular methods to take the measure features of a random sequence in two dimensions [11]. From a visual viewpoint, current Markov chain schemes do not provide efficient visual mechanism to display multiple measurement sequences from the spatial characteristic of complex random sequences.
To extract further information from random sequences, this chapter establishes a visual system to illustrate multiparameter measurement sequences of Markov chains as conjugate maps. For a given set of measurement sequences, the conjugate map proposed in this chapter can provide refined information of distributed structure than present map technologies [12].
In the second section, respective characteristics of traditional methods and conjugate method are discussed. The measurement mechanism of logical function’s spatial characteristics, disposal model, measuring model, and visualizing model, is described in the third section. The results of maps and analysis of the results are discussed in the fourth and fifth sections, and then, concluding remarks are provided in the last section.
2 Traditional Methods and Conjugate Method
In this section, two typically traditional methods, time sequence map and Poincare map, are discussed for comparison.
Time sequence map generates a 2D coordinate; X-axis is determined by the time scale t, and Y-axis is determined by the value of measured parameter \( f(t) \), as shown in Fig. 1a.
The measure sequence \( \{ f(t)\}_{t = 0}^{T - 1} \) with length of T can form Poincare map according to the matching pattern considering data correlation. Poincare method maps one group of measures of time sequence to a 2D map. It detects spatial distribution of sequence through the distribution of point cluster. In Poincare map, X-axis is determined by the value of \( f(t) \) while Y is \( f(t + l) \). It is vicinity-related patterns map when \( l = 1 \), as shown in Fig. 1b.
Different from Poincare method based on one group of measures, new map proposed in this chapter chooses two groups of measures from relevant parallel measures sequences. As two different groups of measures are acted simultaneously, the value of each axis is determined by these two groups of measurements. It is convenient to name new map as conjugate map to present this kind of multiple parameter measurement map.
3 Generate and Measure Mechanism of Time Sequence
In this section, the Cellular Automata (CA) method is applied to generate time sequence and then to make concomitant measurement sequence. First, the initial sequence inputted, and the output sequence is generated by a given logical function using 1D cellular automata. Using this data sequence, measurements are formed by probability measurement according to pairs of input and output sequences. Finally, the generated measure sequences can be used to construct a 2D conjugate map showing 2D spatial distribution of the time sequence. The processing flow of the mechanism is shown in Fig. 2.
3.1 Disposal Model
Consider a logical function \( f \) as a function of CA. The function generates equal-length output sequence \( \{ Y_{i} \}_{i = 0}^{N - 1} \) for any initial input sequence \( \{ X_{i} \}_{i = 0}^{N - 1} \) with N-length bits. The I/O pattern is shown in Table 1.
A total of \( 2^{N} \) states of N-length initial input sequence are exhaustively generated, and the corresponding sequence under the logical function \( f:X \to Y \) can be generated. The input and the output sequences are in the same group corresponded to each other; there are \( 2^{N} \) groups of corresponding relationship [13]. Exhaustion of all the initial input sequences is shown in Table 2.
3.2 Measure Model
The basic model of measurement can be confirmed to establish the transformation relation between the input sequence \( \{ X_{i}^{{}} \}_{i = 0}^{N - 1} \) and the output sequence \( \{ Y_{i}^{{}} \}_{i = 0}^{N - 1} \) for each group.
In the transformation of \( f:X_{i} \to Y_{i} ,0 \le i < N \), there are a total of four types of transformations, each type determines a number, and corresponding relationships are shown in Table 3. This type of measurement structure has a directly corresponding relationship to the Markov chain mechanism [4].
Consider \( j \in \{ 0,1,2, \ldots ,2^{N} - 1\} \) as the serial number of different initial input sequences. There are four measurements that can be identified by the measurement parameters above shown in Table 4 with Markov chain properties, respectively.
For different initial input sequences, there can be generated four groups of measurements on the corresponding I/O sequences: \( \{ P_{00} (j)\}_{j = 0}^{{2^{N} - 1}} \), \( \{ P_{01} (j)\}_{j = 0}^{{2^{N} - 1}} \), \( \{ P_{10} (j)\}_{j = 0}^{{2^{N} - 1}} \), and \( \{ P_{11} (j)\}_{j = 0}^{{2^{N} - 1}} \).
3.3 Visualization Model
Based on the probability measurements presented above, two measurements are chosen to construct 2D map, as two different groups of measurements are used simultaneously, to name this kind of map conjugate map, of which the value of each axis is determined by these two groups of measurements.
According to the construction pattern introduced above, there are \( C_{4}^{2} = 6 \) kinds of different combinations as below: \( \{ P_{00} (j),P_{01} (j)\} \), \( \{ P_{00} (j),P_{10} (j)\} \), \( \{ P_{00} (j),P_{11} (j)\} \), \( \{ P_{10} (j),P_{11} (j)\} \), \( \{ P_{01} (j),P_{11} (j)\} \), and \( \{ P_{01} (j),P_{10} (j)\} \).
On the same group of sequences, construct 2D conjugate maps, respectively, by using the combinations above as shown in Fig. 3.
This chapter chooses the typical combination \( \{ P_{01} (j),P_{10} (j)\} \) constructing 2D conjugate map to detect the special distribution of time sequences for N = 13 condition.
4 Visualization Result
Because of the restriction of the structural complexity of the logical function, 16 functions of 2 variables are used to describe them in the way of exhaustion [14]. Output sequences are generated by different initial input sequences under the given logical function and then obtaining various measure data from the corresponding I/O sequence based on probability method. Then, the map is constructed using these measurement data.
This chapter chooses No. 1, 5, 6, and 13 functions which are typical functions as an example, observing the characteristic of three kinds of maps which are given in Fig. 4.
-
In (a) group of time sequence maps, only one measurement sequence transforms with time.
-
In (b) group of Poincare maps, different functions form different point clusters.
-
In (c) group of conjugate maps, the distribution of the points cluster has clear polarized properties.
According to the variable-value logic theory, three kinds of encoding model can be distinguished: W, F, and C [15].
The visualization information that can be acquired from a single function’s map is rather limited. In order to compare the spatial property of different logical functions, a 4 × 4 array is constructed using the maps that are generated from 16 logical functions in different encoding patterns as shown in Fig. 5.
By assemble maps of total 16 logical functions under the models, the entire structure information among logical functions themselves can be observed.
To compare conveniently, combinations of 16 recursive images which generated from 16 functions are given in this chapter under different codes. Recursive images in W-code, F-code, and C-code from a given initial sequence are shown in Figs. 6, 7, and 8, respectively.
The combination of time sequence map is shown in Fig. 9. The figure shows that different functions have different distribution properties, and also reveals the trend of single measurement’s transforming with time.
The combination of Poincare map in W-code is shown in Fig. 10. Different distribution properties of functions can be observed from the figure. It is clear that there are four groups of configurations appeared in the figure: \( \left\{ {0,8,2,10} \right\}, \, \left\{ {1,3,9,11} \right\}, \, \left\{ {4,6,12,14} \right\}, \, \left\{ {5,7,13,15} \right\} \).
For W-code, Poincare maps are shown in Fig. 10 and corresponding 2D conjugate maps are shown in Fig. 11. Conjugate maps have polarized properties, and their function pairs of 0:15, 1:7, 2:11, 4:13 and 8:14 have conjugate symmetry. In general, 16 conjugate maps are different from relevant maps generated by Poincare maps.
To arrange 16 Poincare maps and conjugate maps by F-code structure, F-code maps are shown in Figs. 12 and 13, respectively.
Under C-code structure, Poincare maps and conjugate maps are shown in Figs. 14 and 15.
In the above maps, 2D conjugate maps not only show spatial distributions of different logical functions but also have special holistic symmetries under the F- and C-code conditions.
5 Analyze
Through three types of different maps, three different coding schemes can be observed.
Time sequence map can show the simple trend of single measurement series with time variations, but it was difficult for the scheme to describe spatial distributions of time sequence.
Poincare map can apply a single measurement sequence; although the map can be generated under different lengths in a correlation, information of distribution is naturally limited by the selected measurement sequence.
A 2D conjugate map uses two groups of independent measurements simultaneously; this scheme can show differences and connections between spatial distributions of logical functions; furthermore, through different coding models, it can illustrate holistic relationships among different functions, i.e., function pairs of 0:15, 1:7, 2:11, 4:13, and 8:14 have clear conjugated symmetry in conjugate maps. In addition, for C-code condition, the points of four functions on each edge of maps are located on the same side of edge. For example, points clusters of (0, 4, 1, 5), (0, 2, 8, 10), (10, 14, 11, 15), and (5, 7, 13, 15) functions are separately located on four sides of the 2D map space.
6 Conclusion
Refined property of various time sequences can be identified from 2D conjugate maps to illustrate multiple measurement sequences under Markov chain mechanism. Spatial property of time sequence plays an important role in the study of dynamic sequence’s behavior. The stable distribution under visualization method can help people understand relevant issues.
In comparison with Poincare maps and conjugate maps, there are additional properties in the complex dynamic sequences. Conjugate map method uses multiple parameters of Markov chains to make independent measurements simultaneously.
Proposed technology can provide further structural information among multiple measurements, and refined relationship via spatial distributions can be established. It is possible for the scheme to use statistical and probability methodologies to enhance visual tools of Markov chain mechanisms to resolve real problems and requirements for modern information warfare and information security applications in near future.
References
E.L. Key, An analysis of the structure and complexity of nonlinear binary sequence generators. IEEE Trans. Inf. Theory IT-22(6), 732–736 (1976)
D. Haccoun, A Markov chain analysis of the sequential decoding metric. IEEE Trans. Inf. Theory 26(1), 109–113 (1980)
J.L. Massey, M.K. Sain, Certain infinite Markov chains and sequential decoding. Discrete Math. 3(1–3), 163–175 (1972)
O.B. Sheynin, Markov’s work on probability. Artch. History Exact Sci. 39(3), 337–377 (1989)
S.E. Widnall, R.R. Fogelman, Cornerstones of Information Warfare (Doctrine/Policy Document, United States Air Force, 1997)
A. Borden, What is Information Warfare? Aerospace Power Chronicles, United States, Air Force, Air University, Maxwell AFB, Contributor’s Corner (1999). http://www.airpower.maxwell.af.mil/airchronicles/cc/borden.html
S. Budiansky, Battle of Wits: The Complete Story of Codebreaking in World War II (Free Press, New York, 2000)
C. Kopp, B. Mills, Information warfare and evolution, in Proceedings of the 3 rd Australian Information Warfare & Security Conference, ECU (2002)
D.E. Denning, Information Warfare and Security (Addison Wesley, Reading, MA, 1999)
S. Li, X. Tian, Nonlinear Study and Complexity Study (Harbin Institute of Technology Press, Harbin, 2006)
G. Pye, M. Warren, Appraising critical infrastructure systems with visualisation, in 10th Australian Information Warfare and Security Conference, pp. 5–12 (2009)
Q. Li, J.Z.J. Zheng, Spacial distributions for measures of random sequences using 2D conjugate maps, Proceedings of Asia-Pacific Youth Conference on Communication, pp. 64–68 (2010)
S. Wolfram, Theory and Applications of Cellular Automata (World Scientific Press, Singapore, 1986)
J. Wan, J.Z.J. Zheng, Showing exhaustive number sequences of two logic variables for variant logic functional space, in Proceedings of Asia-Pacific Youth Conference on Communication, pp. 69–73 (2010)
J.Z.J. Zheng, C. Zheng, A framework to express variant and invariant functional spaces for binary logic. Front. Electr. Election. Eng. China 5(2), 163–172 (2010). (Higher Education Press & Springer Press)
Acknowledgements
Thanks goes to Mr. Jie Wan for helping him to generate data for this study and the special fund of Information Security (No. 2010KS06), Software School of Yunnan University to fund the project.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
Copyright information
© 2019 The Author(s)
About this chapter
Cite this chapter
Li, Q., Zheng, J. (2019). 2D Spatial Distributions for Measures of Random Sequences Using Conjugate Maps. In: Zheng, J. (eds) Variant Construction from Theoretical Foundation to Applications. Springer, Singapore. https://doi.org/10.1007/978-981-13-2282-2_13
Download citation
DOI: https://doi.org/10.1007/978-981-13-2282-2_13
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-13-2281-5
Online ISBN: 978-981-13-2282-2
eBook Packages: EngineeringEngineering (R0)