Modern effective distributed information systems (DIS) [1,2] are based on the joint use of many promising computer, communication, computing, information subject technologies, and some of which are rapidly developing service-oriented architectures, as Web services [3,4], cluster, cloud, multi-agent [5,6]and GRID systems [7,8], super-large data and knowledge systems [9,10] intelligent systems [11][12][13], the avalanche-growing world of the Internet of things [14,15]. One of the most important reasons for this growth is the significant successes of fundamental mathematical computer sciences, in particular, in the field of complex, decomposition, functional, fuzzy, intellectual, concurrent methods of analysis and synthesis of DIS.
At the same time, the quality of their functioning, which is determined not only by the general completeness, accuracy and efficiency of the results, but also their reliability, and the performance of the DIS as a whole [2]. One of the most important ways to ensure the operability of computer systems is the technology of technical verification of projects, testing and diagnosing of DIS implementations, which allows developing and applying various tools, as part of automated technical diagnostic systems (ASTD) [16]. Among these tools, as a rule, there is an online and offline testing. Currently, there are developed tools of structural, functional-behavioral, deterministic, pseudo-random, evolutionarygenetic, logical, symbolic, fuzzy, intelligent, abstract, decomposition analysis and synthesis to provide the necessary level of DIS reliability of projects and the operability of functioning of its implementations, in particular, the tools of online and offline testing of DIS.
Most often, to achieve greater efficiency, these tools are used in a comprehensive manner, tuning their aggregates to the features of specific tested systems and the tasks they solve. The properties of the DIS, that adopted from the applied technologies, are reflected also in the properties of ASTD tools. Moreover, the complexity of constructing technical tools ASTD often exceeds the complexity of the DIS [15][16][17][18][19] itself. It is often and naturally, for example, for systems of critical applications [20][21][22].
At the same time, there is transfer of the basic methods of DIS analysis and synthesis to a systemic, abstract-symbolic, structural-behavioral level, which has mappings to many possible technologies of physical implementation.
Additionally, the degree of dimensionality, uncertainty and intelligence of DIS behavior, of scalability, autonomy, mobility and situational dynamic the goal formation and the cooperation of DIS components for solving objective problems in a multi-level, multi-platform global network is increasing. This increasing degree requires appropriate improvement of verification and test tools, in particular, in the abstract, behavioral, decomposition, intelligent directions.
Thus, we can conclude, that the development of effective tools for ASTD new DIS is non-trivial and relevant.
Formal behavioral analysis and synthesis of computer systems (CS), usually characterized by NPcomplexity [15][16][17][18][19], is becoming increasingly important in systemic, structural and functional verification of projects of CS and check of its implementation.
The ongoing development of the mathematical theory of experiments with automata class models [23,24], which define a formal methodology of behavioral checking and recognition, gradually raises the upper limits of applicability of check automata models.
Generally, these limits are determined by exponential (NP-complex) dependences of the complexity of such an analysis from the dimension of input models [15][16][17][18][19].
To reduce the complexity, in particular, the time of preparation and execution of the behavioral testing in the class of errors of functional automata mappings with preserved values of the completeness of the testing itself, a common (mathematical) and special (taking into account architectural solutions) network and hierarchical decomposition are used [25][26][27][28][29] for checked systems most often.
They allow to reduce (usually polynomially) the exponential dependence of the dimension of complexity (computational resources) and time of constructing and performing of testing at a formal model level. Special probabilistic-statistical [30][31][32], fuzzy [33][34][35][36], intelligent [37,38], in particular, evolutionary-genetic [25,28,29,38] models and methods give experimental values for the complexity of behavioral testing for most real systems, that polynomially smaller, than the upper theoretical boundaries of deterministic methods, with a slight decrease in the completeness of this testing.
As a result, depending on the involved computing tools, behavioral check of acceptable completeness of checking for DIS of medium complexity becomes achievable, nevertheless, as noted, such a decrease does not remove this problem from the class of NP-complex ones.
The above circumstances determine the expediency of further development of verification and testing of CS, in particular, complex, formal, decomposition, intelligent, parallel check models and methods with the total effect of reducing the complexity of the computational costs of its preparation and implementation.
The growing tendency to classify a significant part of modern DIS to real-time and critical application systems, significantly strengthens the requirements for completeness, accuracy and relevance of operational checking of their performance, for resources, that necessary for its implementation.
This trend also encourages the use of complex ASTD, which include tools of online and offline testing, acting from the upper systemic, structural and functional level. In this case, the work of ASTD is inevitably based on formal models and methods of behavioral testing [24,28,29,[39][40][41], whether their analytical or intuitive expert implementations.
Behavioral testing of the CS makes it possible both for the online testing [29], that is backgrounding to the main functioning and performing the accumulation of check presentability of passive recognition experiments, as well as the special offline testing, that is interrupting the main functioning of the CS and performing active check experiments [28]. Typically, both modes involve a previous (preprocessor) check analysis of the reference behavior of the CS with external or internal (own) procurement of elements of behavioral check.
The foregoing does not remove the advisability of continuing research on decomposition, compatible, dynamically integrated online and offline behavioral testing, especially for distributed, critical, intellectual CS, in particular, DIS, with dynamically reconfigurable of model representation, structure, composition and migration of components, general and component behavior.
These features, in particular, become characteristic of DIS and cause the expanding use of multiagent technologies. For such systems, a distributed, fuzzy, dynamic definition of the class of checked properties, completeness, accuracy and relevance of the checking are also characteristic. The consequence of this condition, in particular, can be considered the emergence of the class of ASTD DIS, essentially relying on models and methods of multi-agent technologies [42].
Taking into account the aforementioned, the tasks of system-functional, network and multi-level, integrated online and offline behavioral testing of DIS can be considered relevant and carried out. This testing executes on the basis of the dynamic cooperation of intelligent agents in the conditions of variable resources, that provided by the environment of the DIS itself. Also, this behavioral testing has variable check controllability, observability and heritability of own results, bases on agent, decomposition, deterministic and evolutionary models and methods.
A multilevel network modela extended hierarchical Petri net, adopted as the basic input model of checking agent for DIS,is characterized by a two-dimensional structure, alphabets and mappings of components, data and knowledge structures, that can change in the life cycle of a checked DIS, that hosts checking agents from MAS.
Online and offline testing of DIS is carried out by cooperations of agents from a set of Ag, that located into DIS environment. Atomic element, MAS agent agiAg, is the MAS model of the first level.
The goal of this work is the construction an agent check model agi, as a formalization of the representation of agent online and offline behavioral testing, performed on the basis of the Petri net S(f)ian automata class model for some DIS component.
These representations are selected in accordance with the contexts for MAC testing, namely: autonomous; mobile; purposeful or intellectual; cooperative.
To achieve this goal, the tasks of behavioral testing for PN S(f)i are formalized. These tasks are solved by the agent agiAg of a certain components of DIS and include: behavioral testing for an component Petri net S(f)i; controllability and observability of testing for the component Petri net S(f)i into the network model nS(f)i of DIS; inheritance of the elements of behavioral testing of a single-level Petri net S(f)i into the hierarchical model iS(f)i of DIS.
The model of behavioral agent-based testing is built on the basis of an extended Petri netan input automata class model [26,28,29] for some i-th component of DIS of the form:
where P, Tpositions and transitions, respectively; Ev, Acevents for positions and actions for transitions; X@Co, Y@Fuexternal controlled events and observed actions, supplemented by @an unknown event or action; Epthe set of variables for the energy costs, represented as triples epnep= ( F:((B(P),S(B(P)))T×Ac×Et)B(P)))the incidence relation for subsets of positions from the Boolean {p1,…,pip}B(P) and transitions from T, that is depended from current events, actions and energy costs; S:(PEv×EpTAc×Et)the correspondence of own, internal variables of events, as well as actions, expanded by the metric of energy costs in positions and transitions, included in F; M0:PEm-the initial marking of positions, taking into account the initial energy costs of initialization, M:P×EmEmfunction of the current marking of positions and transitions, taking into account the current energy costs, accumulated during the movement of chips.
The model agi of the behavioral agent-based testing, which contains two components for simulated Petri nets (1), the deterministic reactive agRi and the evolutionary deliberative agDi [42] has the form:
where agRi, agDiits reactive and deliberative components, that interact with each other in space and in time, they are functioning in the Petri net S(f)ithe behavioral model of some i-th component of DIS in its space-network nS(f)i [28] and temporal hierarchical iS(f)i [29] models; Evi, Acithe events and actions of the components; i:iIAcRiEvDi)(AcDiEvRi)))the relation of the interaction for reactive agRi and deliberative agDi components, both parallel (in space) and serial (in time).
The type, complexity and state of the Petri net S(f)i of the DIS and the multi-agent system (MAS) of testing, these states, as well as own targeting and tasks of agent agi affect to the form, complexity, priority, activation of agRi and agDi components.
The difference between reactive agRi and deliberative agDi of the check agent agi consists in the features of check tasks, models and methods, which are used into definition, constructing, and recognizing of the check objects.
In general, the agent model agi has information about the objects of check for reference checked properties Pri, identifiers Cii, check Cpi and link Lpi primitives, realized S(f)i(R Ac ) and transported
and transported S(f)i(Tr Y T(S(f)i)) nodal Petri nets necessary, inherited properties iPri , identifiers iCii, check iCpi and iLpi primitives, check fragments Cfi, realized Cfi R and transported Cfi Tr check fragments, inherited check fragments iCfi.
The intelligence of the check agent agi for its deliberative component agDi can be based on evolutionary approaches to check a type of check evolution [28]:
where: Cfi, Cpi, Lpithe sets of check fragments, check and linking primitives, Сf0iinitial set of check fragments, Сf0i=СpiСfi, Сffifinal set of check fragments; SgtagDi={tagDi, tagDi, tagDi, tagDi, tagDi}the signature of operations and functions of check evolution, that contain special operations of mutation, crossover, immunity, fitness function, selection function, respectively. In the case of the presentation of DIS not only as checked, but also as a resource environment for hosting the checking MAS, the second extended model of the check agent agi (also agRi and agDi) [42] is also presented as a system: agi=(cSi, cMi, Qi, Sti, {i, i, i}, {cs0i, cm0i, q0i, st0i}), (4) where: -cSiagent check models for the i-th component of the placement in the DIS, which determine the check conditions; -cMiagent check methods for the i-th component of the placement in the DIS, which determine the implementation of check procedures; -Qiagent goals, for some qiQi, defined as:
qi:
where ki, ki, ki, ki, ki, ki, i, i, i, i=(i , i , i ), i=(i , i , i ), i=(i , i , i )the weighted priority coefficients and determination functions, respectively, of completeness of verification, length (complexity), multiplicity , network realizability and transportability , inter-level inheritance of check (moreover, the functions of realizability, transportability, inheritance combine each of three own functions of preservation of completeness, lengths, multiples of check), csi and csi', cmi and cmi' -the initial and assumed next agent models and check methods for the placement component, respectively; Sti -strategies for the agent's functioning -the agent's application of deterministic, pseudorandom, expert, evolutionary check methods in its life cycle, for some sti defined as:
sti:(jJ(csicmijjJcsicmi)j), (csi',cmi')=sti(csi,cmi);
{i, i, i}accent-agent operations directly displayed in the composition of check models from cMi, their signatures of operations and relations (5), in composition of check methods from cMi, their signatures of operations and relations (6), accordance with the models: a) abstract SgS(f)i={,,} -the signature of the check operations of identification, congruence, determination [24]; b) network realizing and transporting compositions SgnS(f)i={@,,@',#} -the signature of the check compositionssequential, parallel, with feedback, DeMorgan half-convolution [28,29]; c) hierarchical inheriting compositions SgiS(f)i={ p , t } -signature of check substitutions of macropositions and macro-transitions [29]. Own agent operations include: 1. observation i:(jJ(csicmijVi(jJ(csicmij,
with the definition of the current agent check model and method, if necessary, the construction of identifiers Cii and check primitives Cpi in their composition, here Vi=(eni, agRi, Conni) is the complete environment of agent agi, for which: 1) eni=(S(f)i, nS(f)i, iS(f)i, Pli)abstract, twodimensional, network-hierarchical space of the agent world for the agent agi, provided by the ith component of DIS;
and output transportable S(f)(Tr Ac T(S(f)i)) nodal (for input and output topological subnets) partial Petri nets [26,28]; 6) inherited, adjacent up or down for hierarchy, iS(f)i hierarchies of properties and transactions іPri, identifiers іCii, check iCpi and linking iLpi primitives, check fragments iCfi, respectively [29]; {cs0i, cm0i, q0i, st0i}initial agent check model, method, goal, strategy.
Then the combined agent check model csicSi from the above set models cSi for components of abstract S(f)i, network nS(f)i and hierarchical iS(f)i models is defined as:
(
The representation of the abstract component agent meta-method of behavioral check cmicMi as a special, asynchronous-event parallel behavioral procedure with many realizations, that is satisfying the conditions of the corresponding component agent check model csicSi, can be formally determined by using the special Petri net -a special kind of the Rabin-Scott automata, the components of which individually and the relationships for them were mostly determined earlier:
{i,i,i},{i,i,i},{i,i,i},{i,i0},(Wi0 ^=Cfi0,Pri0=, {i0=0,i0=0,i0=0}),(WiF ^,CfiF,PriF,{iF,iF,iF})), (11) where: a) {Evi,Aci
The meta-method can be implemented in deterministic, pseudo-random, evolutionary, and also combined methods based on the search in depth and/or in width.
So, model evolutionary concretization and modification of the component agent method of behavioral testing cemiceMi has specialized view for evolutionary operations -i,-i and functions -i,-i,-i,-i,-i,-i: cemi=({W ^,Evi,Aci},jJ(Wij ^,Cfij,Prij,{ij,ij,ij}),{Pri,Cii,Cpi,Cfi},Mmi, {i,i,i},{i-i,-i,-i,i},{-i,-i,-i,-i,-i,-i},{i,i0}, (Wi0 ^=Cfi0,Pri0=,{i0=0,i0=0,i0=0}),(WiF ^,CfiF,PriF,{iF,iF,iF})), (12) here modified objectsoperations and functions [24,28,29] The procedure of the component agent evolutionary method cemi of behavioral testing is an event model and does not determine the serial-parallel organization of check, in particular, the combined organization of search in width and depth. Such an organization can be determined by using relations for subjects and objects in their structures and locations, as well as for their operations/functions.
Relationships include special (dependencies, generalizations, implementations, associations, aggregations, inheritance), basic (precedence, order, equivalence, compatibility, incompatibility, uncertainty, indifference), properties (reflexivity, symmetry, transitivity connectivity), both forming and limiting the possible structures of the actions of the method. At the internal level, these relations are determined by abstract resources shared in a certain way, first of all, by basic computer-processors, information objects, and communication tools.
Computing processors and communication tools directly depend on the environment of the agent's location, therefore, their influence on the relationship between objects and operations/functions of the agent is indirect to the environment of placement and can be considered instrumental.
Information objects are abstracted from the placement environment, their influence on the relationship between objects and agent operations/functions is direct and can be considered methodological. In this regard, it is necessary to consider the current, previous and subsequent influences -temporary relationships for objects (including information) and operations/functions, as well as their instances in the agent's lifetime. In such relations, the input and output weight characteristics of the action object (usually an information object) performed by the subject of the action (usually an operation/function) are significant. These weight characteristics are essential precisely for the subjects of action and their instances, when organizing the system of priorities and parallelism, and also the corresponding system of method relations.
Own relations for operations/functions, as subjects of the current moment of time and the current shared object of action in the evolutionary method of cemi behavioral check, are general relations: firstly, of direct preceding (see table 1), which defines adjacent sequential subjects of actionoperations/functions with the transfer of a action object between them; secondly, compatibility (see table 2), which defines parallel subjects of the action -operations/functions with conflict-free separation of the objects of action. It is obvious, that in the evolutionary method of behavioral check cemi for operations/functions, as subjects of the current moment of time, the relation of indifference acts for different current individual objects of action not separated by subjects. That is, parallelism for such operations/functions and individual objects is methodologically not limited.
The Relationship of the immediate preceding (quasiorder)
The ratio of compatibility (tolerance): The specificity of the check functioning of the deterministic reactive component agRi of the agent agithe execution of its operations {i, i, i}can be based on the methods of depth and breadth search with local search optimization for behavioral testing, which bases on experiments with automata model, and is characterized by computational NP-complexity. This circumstance implies the limitation of the analysis spacea subset of the DIS components by objects of medium complexity (up to 1000 positions/ /transitions) to obtain the solution of check tasks of the required characteristics. These characteristics include high completeness i, acceptable properties of length i and multiplicity i, realizability i, transportation i, inheritance i for spent of time i and memory i, limited by the upper bounds of the allocated computing resources RagRi=(MaxagRi, MaxagRi) of the reactive component agRi.
The specificity of the functioning of the deliberative component of the agent for performance of its operations {i, i, i} can be based on a pseudo-random goal-oriented check evolutionary search. As result, this functioning retains the upper exponential analytical estimates of deterministic methods for experiments with automata and Petri nets, but it has experimental complexity, significantly less computational NP-complexity of the latter.
This leads to the possibility of solution of check tasks of acceptable completeness and length with time and memory costs lower, than average. This range is limited by the lower and upper boundaries of the resources RagDi=(MaxagDi, MaxagDi) of the deliberative component in the analysis space of the objects above an average degree of complexity (more, than 1000 positions/transitions) -a subset of the DIS components and DIS in as a whole. The results of analytical modeling made it possible to verify the models and assess the domain of their applicability, in particular, the possibility of moving the NPcomplexity of the behavioral check into the reachable area.
Petri nets S(f) are represented in the memory of the controllers for monitoring systems by using of the list structures. Let the following dimensions of the sets be adopted for the Petri net: |P|=np, |T|=nt, n= np+nt, |X|=m, |Y|=l. The structures require for the upper limit of the number of conditional fields:
The complexity of the check analysis of Petri net S(f) includes the preprocessor and main stages for each of evolutions and is determined by upper bound: cciS max =nt(4np+3L+4)+np(3m+2)+2ntnp(nt-1)+2(2Lmnpnt) nt -3)+(nt-1)(npnt)!+ +(iI nt(4npi +3Li +4)+npi (3mi +2)+2ntinpi(nti -1)+2(2Liminpinti) niti -3)+(nti-1)(npinti)!)+ +(jJ ntjntj(4npj+3Lj+4)+npj(3mj+2)++2ntjnpj(ntj-1)+2(2Ljmjnpjntj) njt j -3)+(ntj-1)(npjntj)!). (14) These formulas contain the three parts for Petri net and Petri subnets. The comparison of the online testing programs, based on automata-deterministic and Petri-evolutionary models and methods for onboard automated control systems and terminal video surveillance confirmed a decrease for the computational complexity of online testing and reducing the its time. Upper computational complexity and length of the online testing for the Determination (solid) and Evolutional (dashed) models and methods in cases of simple Petri net () and hierarchical Petri net () are presents in Fig. 1. The comparison of the results of basic programs for automata-deterministic and Petri-evolutionary models and methods of online testing for onboard automated control systems (BSAC) and terminal video surveillance (TVS) confirmed: a) decrease in computational complexity of online testing; b) reducing timer time of the check with preservation of: c) the length of the check and their d) completeness.
The proposed agent-based model of behavioral checking by taking into account the resource conditions of the deployment environment, when checking the DIS components allows to balance and perform distributed behavioral online and offline testing, based on its combined deterministic and evolutionary models and methods, as well as models of the agent deployment environment in the DIS itself.
The proposed combined models, due to the decomposition of the check processes of the distributed MAS, coordinated with the resources of the DIS, make it possible to reduce the time of the DIS check by up to 90% in comparison with the non-decomposition approach.
These models and methods increase the completeness, accuracy and efficiency of the checking of the structure and functioning of real DIS with acceptable computational costs of the MAS level built into DIS. Its exponential complexity, limiting the use of behavioral check, is polynomially reduced due to component (DIS) and agent-based (MAS) decomposition. This, in turn, allows to check more complex DIS.