On recognition of the shift register output function with a random input for a Markov model of an input sequence

Abstract

The problem of recognizing the output function of a binary non-autonomous shift register is considered, the input of which receives a sequence of random variables connected in a simple homogeneous stationary Markov chain. The statistics of symbol frequencies in the output register sequence is used. The recognition problem is reduced to the form of integer minimization of the linear form module under linear constraints. The results are compared with the case when the input sequence is Bernoulli.

Keywords

• shift register
• random input machine
• recognition of output functions

1. Introduction and background

In [ 1 ], the problem of recognizing the output function of a Moore automaton by the output sequence symbol statistics when the input is a sequence of independent identically distributed random variables was considered. Such a problem is a special case of the general problem of recognition of machines with random input and arises in a number of theoretical and applied problems. We list some of them. The problem of choosing the minimum set of multigrams in the output sequence, the probabilities of which characterize the automaton, leads to the problem of analyzing the algebraic properties of the probability distributions family of such multigrams as functions of the probability distribution at the input [ 2, 3 ].

In [ 4 ], a review of papers on a similar problem is given: the probabilities of multigrams of some stationary discrete random process are known, and it is required to determine whether this process is a function on a Markov chain. In [ 5 ], for a non-autonomous shift register with a random input, an estimate was obtained of the output n-grams size, the set of probabilities of which determines the equivalence class of such an automaton, and estimates of the number of equivalence classes.

We can represent any probabilistic automaton [ 6, 7 ] in the form of a sequential connection of a “source of probability” that randomly and independently generates the symbols of an Workshop on information technology and scientific computing in the framework of the X International Conference

CEUR

CEUR Workshop Proceedings (CEUR-WS.org) alphabet with given probabilities and a deterministic finite automaton. In a number of works (see the review [ 8 ]), the problem of synthesizing such a “source of probability” was considered, in particular, developing criteria to determine whether the desired value is generated by a combination of Bernoulli random variables with probabilities from a given set.

The search for new calculation methods leads to the problem of analyzing a class of functions that describe the probabilities of multigrams in the output sequence as functions of real variables [ 9 ].

A large number of works are devoted to the problem of discrete devices testing by applying random sequences (tests) to them and analyzing the statistics at the outputs [ 10, 11 ], etc.). The problem of determining the malfunction of a device in such a formulation is the task of recognizing automata [ 12 ]. This direction is called random or pseudorandom testing. As noted in [ 13 ], the relevance of this direction is associated with the high volume of computations necessary to construct deterministic tests for complex discrete devices. A special place is taken by probabilistic compact testing methods, in which malfunctions are detected by comparing some statistical characteristics of the tested and reference device. Such a characteristic may be the frequency of occurrence in the output sequence of a fixed segment of the output symbols. The ability to change the analyzed segment and the parameters of the random sequence generator at the input of the device is a powerful tool in the hands of the researcher. In [Hamlet, 2006], situations are described where the use of deterministic tests is impractical and random tests should be used. The questions of estimating the length of random tests and the probability of detection of malfunctions are considered in [ 14 ] and [ 15 ]. We note the possibility of using probabilistic testing to detect covert channels in the analyzed equipment [ 16, 17 ].

In [ 18 ] and [ 19 ], the problem of diagnosing a discrete device with random input under conditions when the output sequence of the device is known with distortions is considered.

In [ 20 ], a binary shift register with a random Bernoulli input is considered, the output function of which is known up to a certain transformation. The output sequence of the register is specified, and the input sequence is known in the variants. A statistical criterion is built to verify that the output sequence could be obtained by this input variant. The criterion is based on counting the frequencies of certain bigrams in the output sequence.

The problem considered in [ 1 ] can be formulated as follows. What information about the output function of the automaton whose input is a sequence of independent random variables can we obtain if the parameters of the “input” distribution and the relative frequency of occurrence of the symbol in the output sequence are known? How will this information change if the parameters of the “input” distribution are changed? What output functions are indistinguishable?

Similar problems can be considered in a more general form, assuming a simple or complex [ 21 ] Markov dependence in the input sequence. The main ideas of the developed approach, in principle, can be transferred from the “independent” to the “Markov” case. In fact, a sequence of random variables connected into a finite Markov chain can be considered as a sequence of states of a suitable finite automaton (the transition graph of which is the transition graph of the Markov chain under consideration) that processes a sequence of independent random variables with a properly selected distribution [ 22 ]. Let the output function of such an automaton be identical (output = state). Then the machine that processes the Markov chain can be represented as a serial connection of two machines, the input of the first of which receives a sequence of independent random variables. Thus, the problem reduces to the one considered above, only for a more complex automaton (Figure 1).

The same can be done if the input sequence is a more general random process — a function on a finite Markov chain. In this case, the output function of the first automaton may not be identical. Certain dificulties in this direction are associated both with an increase in the number of states of a new combined automaton, and therefore with an increase in the dimension of computational problems, and with the requirement of strong connectivity of the serial connection of two automata, the first of which should provide all possible models of randomness in the input sequence.

For the case of a binary shift register, we will use the direct representation of probability functions as functions of the Markov chain parameters. A Markov chain with two states is determined by the transition probability matrix and the initial probability distribution, which we assume to be stationary. The transition probability matrix has a size of 2 × 2 , and due tostochasticity it is determined by two real parameters and , 0 < , < 1 . These parameters can be interpreted as the probabilities of transitions “from state 0 to state 1” and “from state 1 tostate 0”, respectively. In [ 23 ], for the case when the symbols of the input sequence are connected into a simple homogeneous stationary Markov chain, an expression is obtained for the probability of the symbol “1” in the output sequence of the register. The same work describes the equivalence relation on a set of Boolean functions that occurs when registers with these output functions have the same probability functions. Here we consider the problem of determining the equivalence class of the output function from symbol statistics, reduce it to the form of the discrete optimization problem, and compare the Bernoulli and Markov cases in terms of obtaining information for recognizing the output function and dimensions of discrete optimization problems.

2. Statement of the problem

Let be the space of -dimensional binary vectors, be the set of Boolean functions of arguments, = 1, 2, … . For ( 1, 2, … , ) ∈ by = ( = {0, 1}, , = {0, 1}, ℎ, ) we denote the Moore automaton with set of states , the transition function ℎ, determined by the rule ℎ (( 1, … , ), ) = ( 2, … , , ), where , ∈ {0, 1}, = 1, 2, … , , and output function ( 1, 2, … , ). The automaton is a shift register with a size of .

Suppose that the automaton , ∈ , = 1, 2, … receives a sequence of binary random variables () , = 1, 2, … , connected in a simple homogeneous stationary Markov chain with the transition probability matrix ( 1 −

1 −

) , 0 < , < 1.

Our task is to determine the accuracy with which the output function ( 1, 2, … , ) can be recognized by the relative frequency of the symbol “1” in the output sequence of automaton and propose a recognition method. 3. Recognition of the equivalence class by the value of the probability function (1) (2) (3)

Thus, is the set of integer points of a () -dimensional parallelepiped. Let be a family of real functions defined on a square 0 < , < 1 of the form (, ) ( − ) , where , ∈ , ≠ , the vector (, )

is defined in [ 23 ], the coordinates of this vector are fractional rational functions of and . Let Ω be the set of all those points of the square at which at least one In [ 23 ], the definition of the Markov weight structure of a Boolean function ∈ was introduced as an integer vector ( )

consisting of sums of values ( 1, 2, … , ) on special subsets formed by vectors with the same bigram markings.

The vector ( )

of the Markov weight structure defines the class of statistical equivalence of the function . It is easy to see that the dimension () of the vector ( ) grows quadratically with . Direct calculation of the number of diferent bigram markings of vectors from leads to the following result.

Theorem 1. If ⩾ 2 : () = { 4 3 2 − + 2, 4 3 ( − 1) 2 − + 2, if is even, if is odd.

Consider the set = {( ), ∈

} of vectors formed by the vectors of all possible Markov weight structures as the set of integer points in the () -dimensional Euclidean space () .

Using the result of the Lemma of [ 23 ], it is easy to see that = 1 × 2 × 3, where (1) (2) (3) 1 = {(

, (, ) ∈ 1) |0 ≤ 2 = {(

, (, ) ∈ 2) |0 ≤ 3 = {( , (, ) ∈ 3) |0 ≤ (1) ≤ ( (2) ≤ 2 ( (3) ≤ ( − − 1 ) ( − 1 − 1 − − 1 − 1 ) ( − 1 − 1 − − 1 − 1 ) ( − 1 ) , (1) – integer} , ) , (2) – integer} , ) , (3) – integer} . function in the family is equal to zero. It is easy to see that Ω is the union of a finite number of smooth curves in a unit square. In particular, it can be shown that both diagonals of the square, {(, )| + = 1 Lebesgue measure zero.

Theorem 2. For (, ) ∈

{(0, 1) × (0, 1})\Ω , by the value of (, ) , we can unambiguously indicate the class of statistical equivalence of the function . This equivalence class corresponds to the vector of the Markov weight structure 0, which is the only solution of the equation } and {(, )| =

} belong to the set Ω , if ⩾ 3 . The set Ω has (, ) = (, )

( 0) under restriction 0 ∈ .

If (, ) ∈ Ω , then this equation has more than one solution, and the vector of the Markov weight structure of is contained among these solutions. 4. Recognition of the equivalence class using the symbols statistics Let () = ( () , (+1) , … , (+−1) ), = 1, 2, … be the output sequence of the automaton in the scheme described above, = 1 =1 ∑ () ,

= 1, 2, … . {| ∈ − (, ) | → min (4) (5) (6) (7) The binary sequence () is stationary, therefore, the law of large numbers is valid [ 24 ]: → (, )

(probability convergence).

Theorem 3. Let (, ) ∈ {(0, 1) × (0, 1})\Ω . The probability that the minimization problem has a unique solution, tends to 1 with → ∞ .

This unique solution corresponds the class of statistical equivalence of output function . For the case (, ) ∈ Ω

, we can only say that the vector of the weighted Markov structure of the true output function is contained among the solutions of problem (7).

5. Conclusion

Comparing the results obtained for the case when the input sequence is a Markov chain with the results obtained for the case of a Bernoulli sequence, the following can be noted. 1. Probabilistic functions in both cases are determined by the weights (sums of values) of the Boolean function of the outputs on special subsets of space . These subsets consist of vectors that have the same probability in a particular model (in the independent case, vectors of the same weight, in Markov, vectors with the same frequency of occurrence of bigrams). In the first case, the probability function is a polynomial in the parameter of the Bernoulli scheme; in the second, it is a fractional rational function in the parameters and , that determine the Markov chain. 2. The relations of statistical equivalence on are introduced on the basis of the identity of probability functions; from the statistical equivalence of two Boolean functions with a Markov input dependence follows their statistical equivalence with a Bernoulli input. The equivalence of two functions is equivalent to the equality of their weights on the mentioned subsets . In the independent case the number of such subsets is + 1 , in the Markov case the number of such subsets is 3 2() . The number of equivalence classes 4 for the Bernoulli case is equal to exp ( 2

2 + ( ln ) ), for the Markov case is equal to exp (543 ln + ( 3)). 3. In the set of all kinds of distributions (the parameter of the Bernoulli distribution belongs to the interval (0, 1), the parameters (, ) of the transition matrix of the Markov chain belong to the square (0, 1) × (0, 1)), a subset Ω of the “special” distributions is distinguished. For all distributions not from the set Ω, the value of the probability function allows us to uniquely indicate the equivalence class of the output function. If the distribution belongs Ω, then there are at least two nonequivalent output functions for which the probability values of “1” in the output sequence coincide. The Lebesgue measure of the set Ω of “special distributions” in the distribution space is zero: in the first case it turns out to be a ifnite set of points of the segment, in the second – the set of points of a finite number of smooth curves inside a square. 4. The problem of determining the equivalence class of a function from the value of a probability function reduces to the problem of solving the equation in integers under linear constraints; the problem of determining the equivalence class of a function from the statistic value of a sample average output sequence is reduced to the problem of minimizing a linear form module under linear constraints. The number of unknowns in the Bernoulli case is equal + 1 , in the case of Markov dependence it is approximately equal 34 2 − .

Thus, analyzing the problem of recognizing an unknown function of outputs by symbol statistics, we can say that the proposed approach, while complicating the probabilistic nature of the input sequence (switching from the Bernoulli scheme to the Markov chain), leads, on the one hand, to the possibility of obtaining more detailed information about the recognizable function; on the other hand, the dimension of discrete optimization problems increases.

Acknowledgments

The publication has been prepared with the support of the “RUDN University Program 5100”. The reported study was funded by RFBR, project numbers 18-00-01555 (18-00-01685), 19-07-00933.

References

[1] S. Y. Melnikov , K. E. Samouylov, The recognition of the output function of a finite automaton with random input , in: V. M. Vishnevskiy , D. V. Kozyrev (Eds.), Distributed Computer and Communication Networks , volume 919 , Springer International Publishing, Cham, 2018 , pp. 525 - 531 . doi:1 0 . 1 0 0 7 / 9 7 8 - 3 - 3 1 9 - 9 9 4 4 7 - 5 _ 4 5 .

[2] A. S. Barashko , O range i statisticheskom otobrazhenii sil'nosvyaznogo avtomata , Kibernetika ( 1987 ) 56 - 60 .

[3] H. Ito , S. Amari , K. Kobayashi , Identifiability of hidden markov information sources and their minimum degrees of freedom , IEEE Transactions on Information Theory 38 ( 1992 ) 324 - 333 . doi:1 0 . 1 1 0 9 / 1 8 . 1 1 9 6 9 0 .

[4] M. Vidyasagar , The complete realization problem for hidden markov models: a survey and some new results , Math. Control Signals Syst . ( 2011 ) 1 - 65 . doi:1 0 . 1 0 0 7 / s 0 0 4 9 8 - 0 1 1 - 0 0 6 6 - 7 .

[5] M. I. Rozhkov , Algoritmicheskie voprosy identifikacii konechnyh avtomatov po raspredeleniyu vyhodnyh m-gramm, dis . … d.t.n., 05 . 13 .19 - metody i sistemy zashchity informacii . informacionnaya bezopasnost , Moskva, MGIEM , 2012 .

[6] R. G. Buharaev , Osnovy teorii veroyatnostnyh avtomatov , Nauka, Moskva, 1985 .

[7] A. Paz , Introduction to probabilistic automata, Academic Press, London, 1971 .

[8] R. M. Kolpakov , Diskretnye preobrazovaniya veroyatnostnyh raspredelenij, in: Sovremennye problemy matematiki i mekhaniki, volume III. Matematika, Izd-vo Moskovskogo universiteta , Moskva, 2009 , pp. 35 - 50 .

[9] A. V. Ryabinin , Stohasticheskie funkcii konechnyh avtomatov, in: Algebra, logika i teoriya chisel, 7 temat . konf. mekh. -mat. fak. MGU , Moskva, 1986 , pp. 77 - 80 .

[10] D. Y. Golembiovskij , Diagnostika cifrovyh ustrojstv. Mikroprogrammnoe i veroyatnostnoe testirovanie, Politekhn . in-t, Saratov , 1993 .

[11] C. N. Hadjicostis , Probabilistic detection of fsm single state-transition faults based on state occupancy measurements , IEEE Transactions on Automatic Control 50 ( 2005 ) 2078 - 2083 . doi:1 0 . 1 1 0 9 / T A C . 2 0 0 5 . 8 6 0 2 7 0 .

[12] N. G. Kushik , Metody sinteza ustanovochnyh i razlichayushchih eksperimentov s nedeterminirovannymi avtomatami, dis . … k.f.-m.n., 05 . 13 .01 - sistemnyj analiz, upravlenie, obrabotka informacii, Tomsk , 2013 .

[13] A. S. Barashko , Y. A. Skobcov , D. V. Speranskij , Modelirovanie i testirovanie diskretnyh ustrojstv, Naukova dumka , Kiev, 1992 .

[14] A. S. Barashko , N. V. Cherevko , Nekotorye sposoby ocenki dliny sluchajnogo testa, in: Teoriya i modelirovanie upravlyayushchih sistem, Naukova dumka , Kiev, 1989 , pp. 10 - 15 .

[15] G. V. Petruhnova , Ocenka dliny sluchajnoj posledovatel'nosti dlya operacii vosproizvedeniya informacii v kontrol'nom ispytanii , in: O. Y. Kravca (Ed.), Sovremennye problemy informatizacii v sistemah modelirovaniya, programmirovaniya i telekommunikaciyah , volume 9 , Izd . ”Nauchnaya kniga”, Voronezh , 2004 , pp. 303 - 305 .

[16] E. E. Timonina , Analiz ugroz skrytyh kanalov i metody postroeniya garantirovanno zashchishchennyh raspredelennyh avtomatizirovannyh sistem, dis . … d. t.n. 05.13 .17 - teoreticheskie osnovy informatiki, Moskva, RGGU , 2004 .

[17] A. A. Grusho , N. A. Grusho , E. E. Timonina , Vklyuchenie novyh zapretov v sluchajnye posledovatel'nosti , Inform. i ee primen. 8 ( 2014 ) 46 - 52 .

[18] E. Athanasopoulou , C. N. Hadjicostis , Probabilistic approaches to fault detection in networked discrete event systems , IEEE Transactions on Neural Networks 16 ( 2005 ) 1042 - 1052 . doi:1 0 . 1 1 0 9 / T N N . 2 0 0 5 . 8 5 3 4 3 0 .

[19] E. Athanasopoulou , L. Li , C. N. Hadjicostis , Probabilistic failure diagnosis in finite state machines under unreliable observations , in: in Proceedings of the 8th International Workshop on Discrete Event Systems - WODES'06 , Ann Arbor , MI., 2006 , pp. 301 - 306 . doi:1 0 . 1 1 0 9 / W O D E S . 2 0 0 6 . 1 6 7 8 4 4 6 .

[20] B. A. Sevastyanov , The conditional distribution of the output of an automaton without memory for given characteristics of the input , Discrete Mathematics and Applications 4 ( 1994 ) 1 - 6 . doi:1 0 . 1 5 1 5 / d m a . 1 9 9 4 . 4 . 1 . 1 .

[21] A. S. Barashko , O raspoznavanii avtomatov s ispol'zovaniem generatorov zavisimyh sluchajnyh signalov, in: Naukovi praci Donec'kogo nacional'nogo tekhnichnogo universitetu, Problemi modelyuvannya ta avtomatizacii proettuvannya (MAP- 2002 ), DonNTU, Donec'k, 2002 , pp. 61 - 71 .

[22] A. S. Davis , Markov chains as random input automata , The American Mathematical Monthly 68 ( 1961 ) 264 - 267 .

[23] S. Y. Mel'nikov , K. E. Samujlov, Veroyatnostnye funkcii i statisticheskaya ekvivalentnost' dvoichnyh registrov sdviga so sluchajnym markovskim vhodom, in: Informacionnotelekommunikacionnye tekhnologii i matematicheskoe modelirovanie vysokotekhnologichnyh sistem : materialy Vserossijskoj konferencii s mezhdunarodnym uchastiem . Moskva, RUDN, 13 - 17 aprelya 2020 g., 2020 , pp. 49 - 54 .

[24] V. S. Korolyuk , N. I. Portenko , A. V. Skorohod , A. F. Turbin , Spravochnik po teorii veroyatnostej i matematicheskoj statistike , Nauka, Moskva, 1985 .