• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
Of all publications in the section: 135
Sort:
by name
by year
Article
D.S. Kildishev, A.V. Khoroshilov. Proceedings of the Institute for System Programming of the RAS. 2019. Vol. 30. No. 5. P. 163-176.

Requirements play an important role in the process of safety critical software development. To achieve reasonable quality and cost ratio a tool support for requirements management is required. The paper presents a formal definition of a metamodel that is used as a basis of Requality requirements management tool. An experience of implementation of the meta model is discussed.

Added: Oct 17, 2019
Article
LYADOVA L.N., SUVOROV N.M. Proceedings of the Institute for System Programming of the RAS. 2020. Vol. 32. No. 2. P. 149-160.

The language-oriented approach is becoming more and more popular in the development of information systems, but the existing DSM platforms that implement this paradigm have significant limitations, including insufficient expressive capabilities of the models used to implement visual model editors for complex subject areas and limited abilities to transform visual models. Visual languages are usually based on graph models, but the types of graphs used have certain limitations, such as insufficient expressiveness, the complexity of representing large-dimensional models and operation executions. For creating a tool that does not have the described constraints, development of a new formal model is needed. HP-graphs can become a solution for this problem. It is not only possible to create new visual languages for diverse domains based on them, but also to develop efficient algorithms to perform different operations on models constructed using these languages. The HP-graph definition is given and the justification of the expressive power of the proposed model is presented, the main operations for HP-graphs are described. The chosen graph formalism combines the capabilities of different types of graphs to represent visual models and allows creating a flexible model editor for the DSM platform, to implement effective algorithms of performing operations, in particular, model transformations.

Added: Jun 27, 2020
Article
Turdakov D., Aleksiyants A., Borisenko O. et al. Proceedings of the Institute for System Programming of the RAS. 2015. Vol. 27. No. 5. P. 35-48.

In this paper the problem of creating virtual clusters in clouds for big data analysis with Apache Hadoop and Apache Spark is discussed. Both clouds and MapReduce models are popular nowadays for a bunch of reasons: cheapness and efficient big data analysis respectively. For these thoughts, having an open source solution for building clusters is important. The article gives an overview on existing methods for Apache Spark cluster creation in clouds. We consider two open source cloud engines OpenStack and Eucalyptus and the most popular proprietary cloud service Amazon Web Services and examine cloud related features presented by these systems. Afterwards, we regard possible ways of creating virtual clusters for big data processing in OpenStack and describe their pros and cons. In the second part we describe in details one of these solutions that uses service Sahara. Sahara represents a cluster management system for OpenStack and it is used for setting up virtual clusters and executing MapReduce jobs. Sahara did not support contemporary versions of Apache Spark. The article introduces the results of our work that led to a Sahara modification, describes its idea and implementation details. By virtue of our modification, Sahara is able to create and use virtual clusters with contemporary versions of Apache Spark in OpenStack clouds.

Added: Sep 13, 2016
Article
I. Shugurov, A. Mitsyuk. Proceedings of the Institute for System Programming of the RAS. 2015. Vol. 27. No. 3. P. 237-254.

This paper is dedicated to a tool whose aim is to facilitate process mining experiments and evaluation of the repair algorithms. Process mining is a set of approaches which provides solutions and algorithms for discovery and analysis of business process models based on event logs. Process mining has three main areas of interest: model discovery, conformance checking and enhancement. The paper focuses on the latter. The goal of enhancement process is to refine an existing process model in order to make it adhere event logs. The particular approach of enhancement considered in the paper is called decomposed model repair. Although the paper is devoted to the implementation part of the approach, theoretical preliminaries essential for domain understanding are provided. Moreover, a typical use case of the tool is shown as well as guides to extending the tool and enriching it with extra algorithms and functionality. Finally, other solutions which can be used for implementation of repair schemes are considered, pros and cons of using them are mentioned.

Added: Aug 18, 2015
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
Avdoshin S. M., Beresneva E. Proceedings of the Institute for System Programming of the RAS. 2019. Vol. 31. No. 4. P. 121-138.

This study is concerned with local search metaheuristics for solving Capacitated Vehicle Routing Problem (CVRP). In this problem the optimal design of routes for a fleet of vehicles with a limited capacity to serve a set of customers must be found. The problem is NP-hard, therefore heuristic algorithms which provide near-optimal polynomial-time solutions are still actual. This experimental analysis is a continue of previous research on construction heuristics for CVRP. It was investigated before that Clarke and Wright Savings (CWS) heuristic is the best among constructive algorithms except for a few instances with geometric type of clients’ distribution where Nearest Neighbor (NN) heuristic is better. The aim of this work is to make a comparison of best-known local search metaheuristics by criteria of error rate and running time with CWS or NN as initial algorithms because there were not found any such state-of-the-art comparative study. An experimental comparison is made using 8 datasets from well-known library because it is interesting to analyze “effectiveness” of algorithms depending on type of input data. Overall, five different groups of Pareto optimal algorithms are defined and described.

Added: Oct 24, 2019
Article
AvdoshinS.M., Lazarenko A.V., Chichileva N.I. et al. Proceedings of the Institute for System Programming of the RAS. 2019. Vol. 31. No. 5. P. 191-202.

The problem regarding the use of machine learning in cybersecurity is difficult to solve because the advances in the field offer many opportunities that it is challenging to find exceptional and beneficial use cases for implementation and decision making. Moreover, such technologies can be used by intruders to attack computer systems. The goal of this paper to explore machine learning usage in cybersecurity and cyberattack and provide a model of machine learning-powered attack.

Added: Dec 31, 2019
Article
N. S. Zubkova, S. A. Shershakov. Proceedings of the Institute for System Programming of the RAS. 2019. Vol. 31. No. 4. P. 139-150.

UML Activity Diagrams are widely used models for representing software processes. Models built from event logs, recorded by information systems, can provide valuable insights into real flows in processes and suggest ways of improving those systems. This paper proposes a novel method for mining UML Activity Diagrams from event logs. The method is based on a framework that consists of three nested stages involving a set of model transformations. The initial model is inferred from an event log using one of the existing mining algorithms. Then the model, if necessary, is transformed into an intermediate form and, finally, converted into the target UML Activity Diagram by the newly proposed algorithm. The transforming algorithms, except one used at the last stage, are parameters of the framework and can be adjusted based on needed or available models. The paper provides examples of the approach application on real life event logs.

Added: Oct 28, 2019
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. Vol. 31. No. 4. P. 151-162.

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