Selecting the invariant classification characteristics of the program behavior of some secured infrastructure (in this task, into two classes: correct and incorrect execution) is identical to the isomorphism problem of the two systems under some mapping. I order to clarify the necessary and sufficient conditions for the system isomorphism, as well as to determine the isomorphism mapping qualitative and quantitative parameters, a similarity theory of the mathematical apparatus was developed. However, in the late 1980s, the results were applied in the field of modeling, applying the universal digital computers and then transferred to solve a much wider spectrum of problems, including cybersecurity and ensuring the required cyber resilience of the critical information infrastructure.
The most detailed provisions of the similarity theory were developed concerning the processes, described by the homogeneous power polynomial systems [1, 3]. There are three main theorems in the similarity theory: the direct, inverse, and π-theorem. The similarity theorem, known as "π-theorem", allows identifying the functional relationship between variable processes in relative form. The deductions form the direct theorem and the “π-theorem” of similarity allowed formulating invariant informative fea*
Copyright 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). tures for the correct behavior of some critical information infrastructure software [2, 4, 5]. 2
Introducing a passport system for programs Let us consider two processes of p1 and p2, which complete equations have the following form: q i1 ui 0
, u = 1, 2, …, r; q i1Фui 0 , u = 1, 2, …, r; u n xu1 j1 j
n Фu X u1
j1 j Where and ‒ homogeneous functions of their parameters. The direct similarity theorem states that if the processes are homogeneously similar, then the following system takes place:
Expressions u = 1,2, …, r; s = 1,2, …, (q-1).
ui Фui uq
Фuq , us ui
uq , u = 1,2, …, r; s = 1,2, …, (q-1) are called criteria or similarity invariants and, as a theorem deduction, are numerically equal to all processes belonging to the same subclass of mutually similar processes.
Thus, the direct theorem formulates the necessary conditions for the correlation of the analyzed process with one of the subclasses. Sufficient conditions for the homogeneous similarity of two processes are given in the inverse similarity theorem: if it is possible to reduce the complete processes equations to an isostructural relative form with the numerically equal similarity invariants, then such processes are homogeneously similar [6, 7].
The similarity theorem, known as "π-theorem", allows identifying the functional
relationship between variable processes in relative form. The deductions form the
direct theorem and the “π-theorem” of similarity allowed formulating invariant
informative features for the correct behavior of some critical information infrastructure
software [9, 11].
(
Imagine the computational process (СP) in the following form ((
The set of times t at which a computational process is observed Sets of input and output parameters of the computational process
Set of states of the computing process. Every state of the computational process is characterized at each moment of time by the sequence of arithmetic operations at the selected control point k.
The set of transition operators fi, reflecting the mechanism of changing the states of the computing process during its execution, including arithmetic operations
The set of output operators фi, describing the mechanism of the
formation of the result during the calculation
ψ: Z’→П’
μ: П’→П
ξ: П→Z
(
In order to form the passport program the following actions are required: 1. Solving the observative problem (the computational process simulation by an oriented program control graph). 2. Solving the problem of presenting calculations by similarity equations on linear graph parts, i.e. to transform the arithmetic operations of the form:
p zi ( x1, x2 ,...,xm ) zij ( x1, x2 ,...,xm )
j1
[zij (x1, x2 ,..., xm )] [zil (x1, x2 ,..., xm )], j ,l 1, p 1. Solving the problem of managing the computational process by comparing the semantic invariants with the program passport that means that it is necessary to find the maps:
1. Considered set of arithmetic operations {+,‒,*,/,=} 2. ti<tmax, where ti – computation time recovery, tmax – maximum allowable time to recover the correctness of the calculations. Solving these problems allowed developing a new method to control the computational program semantic correctness, which complemented the known method capabilities to ensure the required cyber resilience of the secured critical information infrastructure [9, 12].
In order to control the software correctness, it was necessary to construct a program control graph.
Let us imagine some computational process in the form of a program control graph: G(B.D).
Where B = {Bi}is set of vertices (linear program part and D = {BxB} set of arcs (control connections) between them.
Here, each linear graph part Bi B has its own arithmetic operator sequence, i.e.
Bi (bi1, bi2 ,..., bil ).
Bk (B1k , B2k ,..., Btk ), An ordered vertex sequence corresponds to each elementary (without cycles) route of the graph input vertex to output vertex:
where Bk B and Bi k (bik1 , bik2 ,..., bikl ), i 1, p form a sequence of the executed arithmetic operators called a program implementation or a computational process. The arithmetic expression sequence data is the potentially dangerous program fragments.
The computational process algorithm was reduced to the graph representation form to derive the arithmetic expression operators from the control operators (conditional transitions, branching, cycles). As a result, in the control graph, all arithmetic expression operators were grouped on a set of linear program parts — the graph vertices, into which checkpoints (CP) were entered. Here, checkpoints were needed to determine the routing context within which the calculations take place. Moreover, the special systems of defining relations were constructed in the form of similarity equations at each checkpoint for arithmetic operators. The equation system solution allowed to form the matrices of similarity invariants to control the computational process semantics. 4
A similarity equations system development
The studies have shown that the most effective way to control the computation
semantics is to test relations, based on theoretically based relations and computation
features. Here the key relationships in the approach for detecting the parameters of the
incorrect computational process functioning are some invariant, which is understood
as the auto modeling (constant) presentation of program execution in the actual
operating secured infrastructure conditions. The invariant generation problem, from the
different program representations, is non-trivial and poorly formalized. In the
program execution dynamics, only semantic invariants remain fully computable
(repro(
Let us imagine the implementation of Bk of the program control graph as an ordered primary relation sequence, corresponding to arithmetic operators: y1 f1k ( x1 ,x2 ,..., xN ), y2 f2k ( x1 ,x2 ,..., xN , y1 ), ... yM f Mk ( x1 , x2 ,..., xN , y1 , y2 ,..., yM 1 ) Having performed the superposition {yi} on X on the right relation sides, we obtain a relation invariant system according to the displacement: The relation yi zik ( x1 ,x2 ,..., xN ) can be presented as: y1 z1k ( x1 ,x2 ,..., xN ), y2 z2k ( x1 ,x2 ,..., xN ), ... ym z mk ( x1 ,x2 ,..., xN ).
p yi ii1zij ( x1 ,x2 ,..., xN ), where zij ( x1 ,x2 ,..., xN ) ‒ a power monomial.
In accordance with the Fourier rule, the summands (
[yi] = [ zij ( x1 ,x2 ,..., xN ) ] = [ zil ( x1 ,x2 ,..., xN ) ], j,l 1, pi or [ zij ( x1 ,x2 ,..., xN ) ] = [ zil ( x1 ,x2 ,..., xN ) ], j ,l 1, pi System (16) is a defining relations system or a similarity equation system.
Using the function ρ = X→[X], we associate each x j X
with some abstract
dimension x j X . Then the summand dimensions (
N jn
zij ( x1 ,x2 ,..., xn n1xn , j 1, pi
(
N x n1 n jn
N ln x , j ,l 1, pi
n1 n N x n1 n jnln
1, j ,l 1, pi Using the logarithm method, as it is usually done, when analyzing the similarity relations we obtain a homogeneous system of linear equations from the system (17) n1 j n l n ln[xn ] 0 , j ,l 1, pi
N Expression (16) is a criterion for semantic correctness.
Having performed a similar development for Bik B , we obtain a system of k homogeneous linear equations for k-implementation: Акω = 0 (19) the Bk implementation is represented by a matrix Generally, we can assume that the function ρ = X→[X] is surjective and, therefore, Ak a ij of size mk × nk, which a number of columns are not less than the number of rows, i.e. nk mk .
We say that the implementation of Bk is representative if it corresponds to the matrix Аk with mk 1 , i.e. the implementation allows developing at least one similarity criterion.
Usually, a program corresponds to a separate functional module or consists of an interconnected group of those and describes the general solution of a certain task. Each of the implementations Bk B describes a particular solution of the same problem, corresponding to the certain X components values. Since Bk Bl Bk ,Bl B then the mathematical dependencies structure should be preserved during the transition from one implementation to another, i.e. similarity criteria should be common. Then the matrices {Ak}, corresponding to the implementations {Bk}, can be combined into one system.
Let the program have q implementations. Denote by A the union of the matrices {Ak} corresponding to the implementations {Bk}, i.e.
A1 A ... Aq (16) (17) (18) (20) The A Development can be carried out using selective vertices covering the implementations.
Thus, the matrices A union is part of the program passport and is a database of semantic standards {Ak} for the linear program {Bk} sections.
The similarity equation example.
Let us consider an assignment operator: p = a*b + c/(d‒e) (21)
Here, the correct expression must be generated by some selected grammar, which depends on both the possible terms meanings and the chosen operations set. For a context-free grammar, each expression can be matched to an output tree in a unique way. Thus, an output tree can be used as an alternative expression representation.
When constructing a tree by the expression, the order of the calculations plays its role. Obviously, the vertex descendant values are calculated earlier than the ancestor vertex value. Therefore, the operation last performed will take place at the treetop. In order to construct a tree unambiguously, it is necessary to determine the operation calculation order in the expression, taking into account their priorities and the operation order with the same priority, including the case when calculating the same operation (associativity property). Usually, such expressions are calculated from left to right.
The constructed tree will definitely correspond to the specified expression taking into account the calculation order.
We formalize the arithmetic expressions: Let Op {+,‒,*,/} be an arithmetic operations set under consideration.
Terms is a set of terms, consisting of possible objects that can be operation arguments.
Expr is a set of all possible expressions, and Terms Expr . elem(o,e) Expr - many other elements, and oOp, e Expr .
Thus, an arithmetic expression is either a term or an operation connecting several expressions.
The expression (20) with the set of terms Terms = {p,a,b,c,d,e} and the binary operations set Op {,-,*,/} will be represented as: elem: (=,p,(,(*,a,b),(/,c,(-,d,e)))).
The arithmetic operator execution correctness can be assessed using the appropriate semantic function. When applied to expressions, the semantic function T : a a assigns to each argument some abstract entity or dimension [a]. Thus, the arithmetic operations, performed on program variables during the program execution are in fact operations on physical dimensions, and the semantics reflections, performed at runtime, are linear mappings. The axiomatic of extended semantic algebra, which defines operations on the variable dimensions, is presented in Table 2.
Operator Denotation cCoonrdrietciotnness Linear equations cSrimiteilraiorinty Addition R = L + P [L] = [P] [R]0[L]1[P]-1 = 1 0 1 -1 Subtraction R = L – P [L] = [P] [R]0[L]1[P]-1 = 1 0 1 -1 Multiplication R = L * P [R] = [L][P] [R]1[L]-1[P]-1 = 1 1 -1 -1 Division R = L / P [R] = [L][P]-1 [R]1[L]-1[P]1 = 1 1 -1 1 Exponentiation R = Ls [R] = [L]s [R]1[L]-s[P]0 = 1 1 -s 0 Assignment L = P [L] = [P] [R]0[L]1[P]-1 = 1 0 1 -1 where R – the operation result; L, R – left and right operands; [ ] – dimension.
For a correctly running program in the context of this operator, the following relations between the physical dimensions of the terms {p, a,b,c,d,e} should be fulfilled: [p] = [a ∗ b] = [a][b],
[d] = [e], [p] = [c / (d‒ e)] = [c][d]−1 = [c][e]−1, (22)
G , N , R, S ,
A computation model in memory can be represented using the context-free grammars. It allows describing the calculation process structure as a whole. Context-free grammar has the following form: where identifier,constant ,address ... register – a set of assembler terminal symbols/ N Addition, Subtraction, Multiplication, Division, Appropriate – a non-terminal character set;
R AddCommand, SubCommand MulCommand, ..., DivCommand – an output rule set;
S
– a starting symbol.
The terminal symbols include arithmetic coprocessor command lexical tokens, including addition, subtraction, multiplication, division, assignment (data transfer) commands. A non-terminal symbol set is a set of lexical tokens, united by a generalizing feature, as well as their combinations, using products. An example of nonterminal symbols is given in the Table 3. The output rule represented by expression (21) determines the use of the “fadd” command. Thus, we will present all possible inference rules in assembly language.
AddCommand Addition_ Re gister, Address | Addition_ Re gister,Re gister | Addition_ Re gister,Re gister faddp st1, st
Addition ‒ a non-terminal set of coprocessor addition commands; Register ‒ a non-terminal set of coprocessor stack registers; Address ‒ a memory identifier set or actual memory addresses. (23) (24)
Each output in a context-free grammar, starting with a non-terminal symbol, is uniquely associated with a directed graph, which is a tree and is called an output (parse) tree. An output tree example related to the disassembled expression code, as well as its representation as to the similarity equations in terms of the dimension theory, is shown in figure 3.
By taking a logarithm we obtain a homogeneous linear equation system with a coefficients matrix: In order to organize the similarity relations development, it is necessary to construct a translation grammar for assignment operators of the arithmetic type. The translational (attribute) grammar in addition to the syntax allows describing the action characters, which are implemented as functions, procedures, and algorithms. According to dimensions, these functions should implement algorithmic calculations and the similarity relation development, power monomials, equations and solutions.
Thus, the observation problem solution (control graph) and the computations representation (similarity equation) made it possible to form the image of a system for monitoring destructive software actions on the secured infrastructure, and restoring computation processes based on similarity invariants.
The plan of destructive software impacts control and the computational processes recovery includes preparatory and main stages (Figure 4). The preparatory stage includes the program passport formation in similarity invariants, the main ones are the stages of: ─ Similarity invariants formation underexposure, ─ Similarity invariants database formation at the checkpoints of the program control graph, ─ Validation of the semantic correctness criteria of computational processes, ─ Signal generation of the computation semantics violation, ─ Partial calculations recovery according to the program passport.
A general representation of the information infrastructure that implements correct calculations under the hidden intruder program actions is reflected in Figure 5. We will reveal the stages of the destructive software impacts control and the computation processes recovery in more detail. Stage 1. The program passport formation in similarity invariants.
In order to implement a dynamic control, it is necessary to use the static verification results in the form of a program passport.
At the stage of a static verification using the disassembled correct calculation code, the program control graph is constructed.
At each checkpoint for each arithmetic operator, a production tree of an arithmetic expression is generated to develop a linear homogeneous equation system in the dimension terms. The result of solving the equation systems for each linear program part is a similarity invariant matrix. The semantic standard database is made up of reference matrices of similarity invariants for each checkpoint (Figure 6). Stage 2. The similarity invariants formation underexposure
The similarity invariants formation of the computational process, which is subjected to the hidden arithmetic operations impacts, runs according to the same algorithm as the computational process reference invariant formation.
For a given program, a set of checkpoints (CT) is formed, which are embedded in the studied program. The initial program model is the control graph of the computation process in terms of linear program sections. The similarity equations are analyzed and a coefficient matrix is developed in embedded CT for each linear program section, where the calculations take place (Figure 7).
Incorrect calculations will differ in the state set of the computational process Z, i.e. in arithmetic operator sequence. The incorrect calculations scheme is presented in Figure 8.
Stage 3. The similarity invariants database formation at the checkpoints of the program control graph.
At this stage, the similarity invariant matrices constructed for each checkpoint form a similarity invariants database. The scheme of adding matrices to the database is presented in Figure 9.
Stage 4. The validation of the semantic correctness criteria of the computational processes.
In order to control the semantic correctness of the performed calculations, it is necessary to check the semantic correctness criterion by the formula (18) applying the reference and standard invariants matrix (Figure 9).
If the validation of this checkpoint has been completed, then proceed to check the criteria in the next CT until the program ends.
Stage 5. The signal generation of the computation semantics violation and the partial calculations recovery according to the program passport.
If the semantic correctness violation of the program execution is detected, that is, if for a given checkpoint jn in 0 , then a signal is formed and an attempt is made to recover the calculations from the inverse transformation of the reference matrix invariants (Figure 10).
This approach allows to determine not only the fact of the calculation semantics violation but also to indicate the specific impact location on the program, using the mechanism for introducing checkpoints Thus, the dimensions and similarity theory application allowed synthesizing new informative features - the so-called similarity invariants for controlling the computational processes correctness. The similarity invariants use made it possible to bring the monitoring system of destructive program actions and the computation processes recovery closer to the controlled computational process semantics.
The obtained results allowed presenting a controlled computational process as a corresponding equations system of dimensions and similarity invariants, and its solution was to analyze the computations semantics under the destructive program impacts on the secured critical information infrastructure.