DOI: 10.17587/prin.14.285-291
Anomaly Detection Using the DAG Process Models
I. Yu. Teryokhina, Assistant, iteryokhina@cs.msu.ru, Lomonosov Moscow State University, Moscow, 119991, Russian Federation
Corresponding author: Irina Yu. Teryokhina, Assistant, Lomonosov Moscow State University, Moscow, 119991, Russian Federation, E-mail: iteryokhina@cs.msu.ru
Received on April 17, 2023
Accepted on April 26, 2023
The problem of anomaly detection when several information technologies (processes) are functioning simultaneously is considered. It is assumed that the normal or typical functioning of the process can be described by some formal model. In this paper a directed acyclic graph (DAG) is considered as such formal model. It is considered that all necessary information about the processes possible executions can be received from an event log, which is considered given.
In this paper the event log traces containing the data from one and several processes were examined. The complexity estimates for solving anomaly detection problem with the use of the constructed earlier formal models are determined.
It has been shown that the solution of the anomaly detection problem has linear complexity with respect to the length of the trace, for which it is required to give an answer whether such trace contains an anomaly. Also, it has been proven that the solution of the anomaly detection problem has quadratic complexity with respect to the maximum possible number of actions and dependencies in one simulated process. Moreover, it has been demonstrated how the system of different representatives may help to effectively identify the trajectories of many different processes.
Keywords: anomaly detection, directed acyclic graph, process mining, process model construction
pp. 285–291
For citation:
Teryokhina I. Yu. Anomaly Detection Using the DAG Process Models, Programmnaya Ingeneria, 2023, vol. 14, no. 6, pp. 285—291. DOI: 10.17587/prin.14.285-291. (in Russian).
References:
- Agrawal R., Gunopulos D., Leymann F. Mining process models from workflow logs, Advances in Database Technology—EDBT'98: 6th International Conference on Extending Database Technology Valencia, Spain, March 23—27, 1998 Proceedings 6, Springer Berlin Heidelberg, 1998, pp. 467—483. DOI: 10.1007/bfb0101003.
- Kunze M., Weske M. Behavioural models: From modelling finite automata to analysing business processes, Springer International Publishing, 2016, pp. 163—185. DOI: 10.1007/978-3-319-44960-9.
- Sommers D., Menkovski V., Fahland D. Supervised learning of process discovery techniques using graph neural networks, Information Systems, 2023, p. 102209. DOI: 10.1016/j.is.2023.102209.
- Liu C., Cheng, L., Zeng Q., Wen L. Formal Modeling and Discovery of Hierarchical Business Processes: A Petri Net-Based Approach, IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2022. DOI: 10.1109/TSMC.2022.3195869.
- Httbscher G., Geist V., Auer D. et al. Graph-based managing and mining of processes and data in the domain of intellectual property, Information Systems, 2022, no. 106, p. 101844. DOI: 10.1016/j.is.2021.101844.
- Huang Y., Fan J., Yan Z. et al. Research on early warning for gas risks at a working face based on association rule mining, Energies, 2021, vol. 14, no. 21, p. 6889. DOI: 10.3390/en14216889.
- Teryokhina I. Yu., GrushoA. A., Timonina Е. Е., Shorgin S. Ya. Building process models with simple Petri nets, Systems and Means of Informatics, 2020, vol. 30, no. 4, pp. 61—75. DOI: 10.14357/08696527200406 (in Russian).
- Teryokhina I. Anomaly detection in several running processes, International Journal of Open Information Technologies, 2021, vol. 10, no. 1, pp. 21—27.
- Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to algorithms, MIT press, 2022, 1312 p.
- Grusho A. A., TimoninaC. Е., Grusho N. A., Teryokhina I. Yu. Anomaly detection with metadata, Informatics and Applications, 2020, vol. 14, no. 3, pp. 76—80. DOI: 10.14357/19922264200311 (in Russian).
