• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
Of all publications in the section: 124
Sort:
by name
by year
Article
Tatarnikov A. Proceedings of the Institute for System Programming of the RAS. 2016. Vol. 28. No. 4. P. 77-98.

Test program generation and simulation is the most widely used approach to functional verification of microprocessors. High complexity of modern hardware designs creates a demand for automated tools that are able to generate test programs covering non-trivial situations in microprocessor functioning. The majority of such tools use test program templates that describe scenarios to be covered in an abstract way. This provides verification engineers with a flexible way to describe a wide range of test generation tasks with minimum effort. Test program templates are developed in special domain-specific languages. These languages must fulfill the following requirements: (1) be simple enough to be used by verification engineers with no sufficient programming skills; (2) be applicable to various microprocessor architectures and (3) be easy to extend with facilities for describing new types of test generation tasks. The present work discusses the test program template description language used in the reconfigurable and extensible test program generation framework MicroTESK being developed at ISP RAS. It is a flexible Ruby-based domain-specific language that allows describing a wide range of test generation tasks in terms of hardware abstractions. The tool and the language have been applied in industrial projects dedicated to verification of MIPS and ARM microprocessors.

Added: Nov 26, 2017
Article
Davydova K. V., Shershakov S. A. Proceedings of the Institute for System Programming of the RAS. 2016. Vol. 28. No. 3. P. 85-102.

In this paper, we consider an approach to reverse engineering of UML sequence  diagrams from event logs of information systems with a service-oriented architecture (SOA).  UML sequence diagrams are graphical models quite suitable for representing interactions in  heterogeneous component systems; in particular, the latter include increasingly popular SOA- based  information  systems.  The  approach  deals  with  execution  traces  of  SOA  systems,  represented  in  the  form  of  event  logs.  Event  logs  are  created  by  almost  all  modern  information  systems  primarily  for  debug  purposes.  In  contrast  with  conventional  reverse  engineering techniques that require source code for analysis, our approach for inferring UML  sequence diagrams deals only with available logs and some heuristic knowledge. Our method  consists  of  several  stages  of  building  UML  sequence  diagrams  according  to  different  perspectives  set by  the analyst.  They include mapping  log attributes  to diagram  elements,  thereby determining a level of abstraction, grouping several components of a diagram and  building hierarchical diagrams. We propose to group some of diagram components (messages  and  lifelines)  based  on  regular  expressions  and  build  hierarchical  diagrams  using  nested  fragments. The approach is evaluated in a software prototype implemented as a Microsoft  Visio add-in. The add-in builds a UML sequence diagram from a given event log according  to a set of customizable settings.

Added: Nov 18, 2016
Article
K. Davydova, S. Shershakov. Proceedings of the Institute for System Programming of the RAS. 2017. Vol. 29. No. 4. P. 155-174.

In the paper we consider a method for mining so-called “hybrid” UML models, that refers to software process mining. Models are built from execution traces of information systems with service-oriented architecture (SOA), given in the form of event logs. While common reverse engineering techniques usually require the source code, which is often unavailable, our approach deals with event logs which are produced by a lot of information systems, and some heuristic parameters. Since an individual type of UML diagrams shows only one perspective of a system’s model, we propose to mine a combination of various types of UML diagrams (namely, sequence and activity), which are considered together with communication diagrams. This allows us to increase the expressive power of the individual diagram. Each type of diagram correlates with one of three levels of abstraction (workflow, interaction and operation), which are commonly used while considering web-service interaction. The proposed algorithm consists of four tasks. They include splitting an event log into several parts and building UML sequence, activity and communication diagrams. We also propose to encapsulate some insignificant or low-level implementation details (such as internal service operations) into activity diagrams and connect them with a more general sequence diagram by using interaction use semantics. To cope with a problem of immense size of synthesized UML sequence diagrams, we propose an abstraction technique based on regular expressions. The approach is evaluated by using a developed software tool as a Windows-application in C#. It produces UML models in the form of XML-files. The latter are compatible with well-known Sparx Enterprise Architect and can be further visualized and utilized by that tool.

Added: Oct 18, 2017
Article
Salibekyan S. M., Oleynik P. P. Proceedings of the Institute for System Programming of the RAS. 2016. Vol. 28. No. 3. P. 35-50.

The article describes two approaches for control access rights based on role approach (RBAC) and the use of tables (lists) access rights (ACL). At first, an overview of modern approaches to information security and control user access rights of applications with different architectures is provided. After that, two author's methods of data protection is described. The first approach was developed for the protection of object-oriented applications, the second approach was developed for object-attribute applications used to operating network (graph) databases and knowledge bases. The focus of attention is the first author's approach based on the description of access rights for classes, attributes of classes and objects that has a certain criterion. The approach is implemented by the use of a class hierarchy, composition and structure describing in detail in the article. The article gives examples of specific information systems developed by the first author: information system for scientific conferences that was repeatedly used at the conference "Object systems" (objectsystems.ru) and information system of the beauty salon. Further focus is on the second approach required development of new technique to the information security of network (graph) information structures. The approach developed by second author fully duplicates the functionality of the first approach. In particular, it provides permissions copy when copying of the network data structure, just as in the object-oriented paradigm is a transfer of the properties of parent to child class; the article gives a detailed description of such mechanism. For access control, the method involves the use of a special virtual device. Information about access rights is linked to the node network (graph) if restrict access is needed.

Added: Sep 16, 2016
Article
Горшков И. А., Долгалева И. И. Труды Института системного программирования РАН. 2018. Т. 29. № 4. С. 325-336.

Nowadays, news portals are forced to seek new methods of engaging the audience due to the increasing competition in today’s mass media. The growth in the loyalty of news service consumers may further a rise of popularity and, as a result, additional advertising revenue. Therefore, we propose the tool that is intended for stylish presenting of facts from a news feed. Its outputs are little poems that contain key facts from different news sources, based on the texts of Russian classics. The main idea of our algorithm is to use a collection of classical literature or poetry as a dictionary of style. The facts are extracted from news texts through Tomita Parser and then presented in the form similar to a sample from the collection. During our work, we tested several approaches for text generating, such as machine learning (including neural networks) and template-base method. The last method gave us the best performance, while the texts generated by the neural network are still needed to be improved. In this article, we present the current state of Narrabat, a prototype system rephrasing news we are currently working on, give examples of generated poems, and discuss some ideas for future performance improvement.

Added: Oct 31, 2018
Article
Zelenova S. A., Zelenov S. V. Proceedings of the Institute for System Programming of the RAS. 2017. Vol. 29. No. 6. P. 183-202.

In the paper, we address mission critical systems, such as automobile, avionic, mobile robotic, telecommunication, etc. Such systems must meet hard real-time constraints in order to avoid catastrophic consequences. To meet the real-time constraints, strict periodicity is used (i.e. for any periodic task, time between release points is constant). Sensors, actuators and feedback control functions are typical examples of strict periodic tasks. We study a monoprocessor preemptive scheduling problem for arbitrary number of strict periodic tasks. In this context, we focus on the following problem: how to find non-conflict set of task release points (i.e. sequences of instance release points for different tasks must not intersect). First, as a preliminaries, we introduce some fundamental definitions and prove several elementary schedulability conditions. Next, we investigate the correlation between the scheduling problem and a graph coloring problem for graphs of some special kinds. The graphs under consideration are built on the basis of the tasks' period values. We introduce a notion of divisibility graph for tasks' periods, and study compatibility of graphs' coloring with respect to the schedulability problem. At last, we prove a theorem that provides necessary and sufficient graph coloring conditions for schedulability of given strict periodic tasks. This theorem allows either to find non-conflict set of task release points directly, or to determine quickly that scheduling is impossible.  

Added: Aug 11, 2018
Article
Gnatenko A. R., Zakharov V. Proceedings of the Institute for System Programming of the RAS. 2018. Vol. 30. No. 3. P. 303-324.

The syntax and semantics of the new temporal logic LP-CTL * designed for the formal specification of the behavior of sequential responsive programs, modeled by automata-transducers (transducers) over semigroups, are developed. An algorithm is developed for verifying the feasibility of the formulas of the proposed temporal logic on models represented by finite transducers working on free semigroups. The correctness of the developed algorithm is proved and an upper bound of its complexity is obtained.

Added: Jun 14, 2018
Article
Carrasquel Gamez J. C., Morales A., Villapol M. E. Proceedings of the Institute for System Programming of the RAS. 2018. Vol. 30. No. 4. P. 107-128.

This paper presents Prosega/CPN (Protocol Sequence Generator and Analyzer), an extension of CPN Tools for supporting automata-based analysis and verification. The tool implements several operations such as the  generation of a minimized deterministic finite-state automaton (FSA) from a CPN’s occurrence graph, language generation, and FSA comparison. The solution is supported by the Simulator Extensions feature whose development has been driven by the need of integrating CPN with other formal methods.

Added: Nov 19, 2018
Article
Nosovskiy M.M., Degtiarev K.Y. Proceedings of the Institute for System Programming of the RAS. 2019. Vol. 31. No. 3. P. 99-122.

E-commerce is a runaway activity growing at an unprecedented rate all over the world and drawing millions of people from different spots on the globe. At the same time, e-commerce affords ground for malicious behavior that becomes a subject of principal concern. One way to minimize this threat is to use reputation systems for trust management across users of the network. Most of existing reputation systems are feedback-based, and they work with feedback expressed in the form of numbers (i.e. from 0 to 5 as per integer scale). In general, notions of trust and reputation exemplify uncertain (imprecise) pieces of information (data) that are typical for the field of e-commerce. We suggest using fuzzy logic approach to take into account the inherent vagueness of user’s feedback expressing the degree of satisfaction after completion of a regular transaction. Brief comparative analysis of well-known reputation systems, such as EigenTrust, HonestPeer, Absolute Trust, PowerTrust and PeerTrust systems is presented. Based on marked out criteria like convergence speed, robustness, the presence of hyper parameters, the most robust and scalable algorithm is chosen on the basis of carried out sets of computer experiments. The examples of chosen algorithm’s (PeerTrust) fuzzy versions (both Type-1 and Interval Type-2 cases) are implemented and analysed.

Added: Sep 13, 2019
Article
Nesterov R.A., Mitsyuk A.A., Lomazova I.A. Proceedings of the Institute for System Programming of the RAS. 2018. Vol. 30. No. 3. P. 285-302.

In this paper, we present an approach to model and simulate models of multi-agent systems (MAS) using Petri nets. A MAS is modeled as a set of workflow nets. The agent-toagent interactions are described by means of an interface. It is a logical formula over atomic interaction constraints specifying the order of inner agent actions. Our study considers positive and negative interaction rules. In this work, we study interfaces describing acyclic agent interactions. We propose an algorithm for simulating the MAS with respect to a given interface. The algorithm is implemented as a ProM 6 plug-in that allows one to generate a set of event logs. We suggest our approach to be used for evaluating process discovery techniques against the quality of obtained models since this research area is on the rise. The proposed approach can be used for process discovery algorithms concerning internal agent interactions of the MAS.

Added: Jul 10, 2018
Article
Pavel Pertsukhov, Mitsyuk A. A. Proceedings of the Institute for System Programming of the RAS. 2019.

Event logs of software systems are used to analyse their behaviour and inter-component interaction. Artificial event logs with desirable specifics are needed to test algorithms supporting this type of analysis. Recent methods allow to generate artificial event logs by simulating ordinary Petri nets. In this paper we present the algorithm generating event logs for Petri nets with inhibitor and reset arcs. Nets with inhibitor arcs are more expressive than ordinary Petri nets, and allow to conveniently model conditions in real-life software. Resets are common in real-life systems as well. This paper describes the net simulation algorithm, and shows how it can be applied for event log generation.

Added: Oct 14, 2019
Article
A.M. Rigin, S.A. Shershakov. Proceedings of the Institute for System Programming of the RAS. 2019. Vol. 31. No. 3. P. 203-216.

Multiway trees are one of the most popular solutions for the big data indexing. The most commonly used kind of the multiway trees is the B-tree. There exist different modifications of the B-trees, including B+-trees, B*-trees and B*+-trees considered in this work. However, these modifications are not supported by the popular open-source relational DBMS SQLite. This work is based on the previous research on the performance of multiway trees in the problem of structured data indexing, with the previously developed multiway trees C++ library usage. In this research the B*+-tree was developed as the data structure which combines the main B+-tree and B*-tree features together. Also, in the research the empirical computational complexities of different operations on the B-tree and its modifications were measured as well as the memory usage. The purpose of the current work is the development of the SQLite RDBMS extension which allows to use B-tree modifications (B+-tree, B*-tree and B*+-tree) as index structures in the SQLite RDBMS. The modifications of the base data structure were developed as a C++ library. The library is connected to the SQLite using the C-C++ cross-language API which is developed in the current work. The SQLite extension implements the novel algorithm for selecting the index structure (one of B-tree’s modifications) for some table of a database. The provided SQLite extension is adopted by the SQLiteEventLog component of the LDOPA process mining library. In addition, the experiment on the counting the empirical computational complexities of operations on the trees of different types is conducted using the developed in this work SQLite extension.

Added: Sep 15, 2019
Article
Гудошникова А. А., Литвинов Ю. В. Proceedings of the Institute for System Programming of the RAS. 2016. Vol. 28. No. 2. P. 97-110.

The theme of code reuse in software development is still important. Sometimes it is hard to find out what exactly we need to reuse in isolation of context. However, there is an opportunity to narrow the context problem, if applications in one given domain are considered. Same features in different applications in one domain have the same context respectively so the common part must be reused. Hence, the problem of domain analysis arises. On the other hand, there is metaCASE-techonology that allows to generate code of an application using diagrams, which describe this application. The main objective of this article is to present the technology for application family creation which connects the metaCASE-techonology and results of domain analysis activity. We propose to use some ideas of FODA (feature-oriented domain analysis) approach for domain analysis and use feature diagrams for describing of variability in a domain. Then we suggest to generate metamodel of the domain-specific visual language, based on feature diagram. After that based on generated metamodel domain-specific visual language editor is generated with the aid of metaCASE-tool. With this language user can connect and configure existing feature implementations thus producing an application. This technology supposed to be especially useful for software product lines.

Added: Oct 30, 2018
Article
Денис Турдаков, Астраханцев Н. А., Недумов Я. Р. и др. Труды Института системного программирования РАН. 2014. Т. 26. С. 421-438.

he paper presents a framework for fast text analytics developed during the Texterra project. Texterra is a technology for multilingual text mining based on novel text processing methods that exploit knowledge extracted from user-generated content. It delivers a fast scalable solution for text mining without the expensive customization. Depending on use-cases Texterra could be utilized as a library, extendable framework or scalable cloudbased service. This paper describes details of the project, use-cases and results of evaluation for all developed tools. Texterra utilizes Wikipedia as a primary knowledge source to facilitate text mining in arbitrary documents (news, blogs, etc). We mine the graph of Wikipedia’s links to compute semantic relatedness between all concepts described in Wikipedia. As a result, we build a semantic graph with more than 5 million concepts. This graph is exploited to interpret meanings and relationships of terms in text documents. In spite of large size, Wikipedia doesn’t contain information about many domain-specific concepts. In order to increase applicability of the technology we developed several automatic knowledge extraction tools. These tools include systems for knowledge extraction from MediaWiki resources and Linked Data resources, as well as system for knowledge base extension with concepts described in arbitrary text documents using original information extraction techniques. In addition, utilization of information from Wikipedia allows easily extend Texterra for support of new Natural languages. The paper presents evaluation of Texterra applied for different text processing tasks (part-of-speech tagging, word sense disambiguation, keyword extraction and sentiment analysis) for English and Russian.

Added: Nov 6, 2017
Article
Денис Турдаков, Недумов Я., Астраханцев Н. и др. Труды Института системного программирования РАН. 2014. Т. 26. № 1. С. 421-438.
Added: Sep 13, 2016
Article
Yenigün H., N.Yevtushenko, Kushik N. et al. Proceedings of the Institute for System Programming of the RAS. 2018. Vol. 30. No. 1. P. 7-24.

 State identification is a long standing problem in the area of Finite State Machine (FSM) based modeling and testing of discrete event systems. For the identification of the current state of the system, so-called homing and synchronizing experiments with FSMs are used whereas for the initial state identification one can perform a distinguishing experiment. The homing, synchronizing, and distinguishing experiments are known as “gedanken” experiments, and the sequences for these experiments can be derived for deterministic and nondeterministic, partial and complete specification FSMs that are used to formally represent the required behavior of systems under investigation. The problems of checking the existence and derivation of homing, synchronizing, and distinguishing sequences are known to become harder as a specification FSM turns to be nondeterministic and partial. It is also known that in some cases the complexity can be reduced through a ‘switch’ from preset to adaptive experiment derivation. In this paper, we study how the partiality and adaptivity affect the complexity of checking the existence of homing/synchronizing/distinguishing sequences for deterministic and nondeterministic FSMs and visualize the complexity issues via appropriate figures. We also mention that the existing solutions to state identification problems are widely used for verification and testing of finite state transition systems.

Added: Oct 9, 2019
Article
Glukhoded E., Smetanin S. Proceedings of the Institute for System Programming of the RAS. 2016. Vol. 28. No. 3. P. 7-20.

The concept of Z-numbers introduced by Zade in 2011 is discussed topically nowadays due to it aptitude to deal with nonlinearities and uncertainties whose are common in real life. It was a large step of representing fuzzy logic, however that numbers created much larger problems of how to calculate them or aggregate multiple numbers of that type. Z-numbers have a significant potential in the describing of the uncertainty of the human knowledge because both the expert assessment and the Z-number consists of restraint and reliability of the measured value. In this paper, a method of converting an expert opinion to Z-number is proposed according to set of specific questions. In addition, the approach to Z-numbers aggregation is introduced. Finally, submitted methods are demonstrated on a real example. The topicality of the research is developing a new algorithm and software (based on that development) which could help people make decision in a messy uncertainty with many parameters and factors that are also defined imprecisely. In this work, we present the research that is aimed to find the most efficient methods to operate them (aggregate, add, divide). Firstly, it is important to identify all existing methods of aggregating Z-numbers. Secondly, it is needed to invent new methods of how work with them. The most interesting techniques should be detailed and summarized. There is also a program that is developed to model the real-word task of decision-making.

Added: Nov 23, 2018
Article
S.M. Avdoshin, E.N. Beresneva. Proceedings of the Institute for System Programming of the RAS. 2017. Vol. 29. No. 4. P. 123-138.

The Metric Travelling Salesman Problem is a subcase of the Travelling Salesman Problem (TSP), where the triangle inequality holds. It is a key problem in combinatorial optimization. Solutions of the Metric TSP are generally used for costs minimization tasks in logistics, manufacturing, genetics and other fields. Since this problem is NP-hard, heuristic algorithms providing near optimal solutions in polynomial time will be considered instead of the exact ones. The aim of this article is to experimentally find Pareto optimal heuristics for Metric TSP under criteria of error rate and run time efficiency. Two real-life kinds of inputs are intercompared - VLSI Data Sets based on very large scale integration schemes and National TSPs that use geographic coordinates of cities. This paper provides an overview and prior estimates of seventeen heuristic algorithms implemented in C++ and tested on both data sets. The details of the research methodology are provided, the computational scenario is presented. In the course of computational experiments, the comparative figures are obtained and on their basis multi-objective optimization is provided. Overall, the group of Pareto-optimal algorithms for different  consists of some of the MC, SC, NN, DENN, CI, GRD, CI + 2-Opt,  GRD + 2-Opt, CHR and LKH heuristics.

Added: Sep 27, 2017
Article
M.K. Gordenko, S.M. Avdoshin. Proceedings of the Institute for System Programming of the RAS. 2017. Vol. 29. No. 4. P. 107-122.

The routing problems are important for logistic and transport sphere. Basically, the routing problems related to determining the optimal set of routes in the multigraph. The Chinese postman problem (CPP) is a special case of the routing problem, which has many potential applications. We propose to solve the MCPP (special NP-hard case of CPP, which defined on mixed multigraph) using the reduction of the original problem into General Travelling Salesman Problem (GTSP). The variants of CPP are pointed out. The mathematical formulations of some problems are presented. The algorithm for reduction the MCPP in multigraph into GTSP is shown. The experimental results of solving MCPP in multigraph through the reduction into GTSP are presented. 

Added: Sep 27, 2017
Article
Pozin B. Proceedings of the Institute for System Programming of the RAS. 2018. Vol. 30. No. 1. P. 103-114.

The set of outline and guidelines as well as tools for automation to ensure continuity of business-continuity in the lifecycle of mission critical systems are considered. This complex is called the Life Cycle Supporting System (LCSS). The aim of the system is to reduce the risk level of the realization of critical errors in the system and application software throughout the life cycle of mission critical system, reducing operational risks and total cost of ownership of mission critical system. LCSS in the ISO / IEC / IEEE 15288 terms is enabling system. LCSS is created for life cycle of mission critical system support in the organization-owner.

Added: Oct 31, 2018
Article
Smetanin S. Proceedings of the Institute for System Programming of the RAS. 2017. Vol. 29. No. 4. P. 315-324.

With the popularization of social media, a vast amount of textual content with additional geo-located and time-stamped information is directly generated by human every day. Both tweet meaning and extended message information can be analyzed in a purpose of exploration of public mood variations within a certain time periods.  This paper aims at describing the development of the program for public mood monitoring based on sentiment analysis of Twitter content in Russian. Machine learning (naive Bayes classifier) and natural language processing techniques were used for the program implementation. As a result, the client-server program was implemented, where the server-side application collects tweets via Twitter API and analyses tweets using naive Bayes classifier, and the client-side web application visualizes the public mood using Google Charts libraries.  The mood visualization consists of the Russian mood geo chart, the mood changes plot through the day, and the mood changes plot through the week. Cloud computing services were used in this program in two cases. Firstly, the program was deployed on Google App Engine, which allows completely abstracts away infrastructure, so the server administration is not required.  Secondly, the data is stored in Google Cloud Datastore, that is, the highly-scalable NoSQL document database, which is fully integrated with Google App Engine.

Added: Nov 23, 2018