On some combinatorial properties of LINUX process trees

N. N. Efanov

Čebyševskij sbornik, Tome 19 (2018) no. 2, pp. 151-162.

Résumé

The paper examines the Linux process tree data structure, which arises from the hierarchical scheme of processes generation in Unix-like operating systems. The purpose of study is to highlight the properties of the Linux process trees, which allow to conclude the applicable methods for analyzing such trees, in aim to solve the checkpoint-restore problem of executable environments in Unix-like operating systems.The inverse discrete problem of restoring chains of system calls that generate a certain tree of processes is formulated, as well as a number of restrictions on the form of the system call and an assertion about the existence of a solution that concludes the correctness of the input.Combinatorial estimation of total trees number, which are provided by fork system call, is presented, and correction is noted for the discernibility of identifiers. The feasibility of indexing by nodes is substantiated, due to the formation of non-root identifiers of the symmetric group. Thus, the functional equivalence of automorphic trees with permutations of non-root identifiers is proved. A combinatorial explosion of the functionally different trees number is shown by the procedure of adding a new system call. In view of the above estimations, a conclusion about the ineffectiveness of process trees restoring by bruteforce or direct search is drawn. The idea of constructing restoring mathematical formalisms that take into account the structure of the problem is proposed.Next, the inheritance property of attributes in the process trees is examined, which allows to localize a required attribute when checking the applicability of a system call rule, thus reducing the number of checks. The segmentation property of the Linux process trees is provided. On the basis of the above properties, the conclusion is formulated on the goal of constructing a solution of restoring the syscall chains, which constructing a certain process tree, on the basis of the theory of formal languages and grammars, using formalisms of the class of mildly-context-sensitive. The alternative methods of solution are reviewed too.

Détail

Keywords: mathematical modeling, enumeration combinatorics, groups, trees, Unix-like operating systems, system calls, process tree, checkpoint restore, formal grammars.

Bibliographie

[1] A. Mirkin, A. Kuznetsov, K. Kolyshkin, “Containers checkpointing and live migration”, Proceedings of the In Ottawa Linux Symposium (Ottawa, Ontario, Canada), v. 2, 2008, 85–90

[2] N. N. Efanov, P. V. Emelyanov, “Postroenie formal'noj grammatiki sistemnyh vyzovov”, Informacionnoe obespechenie matematicheskih modelej (Moscow, Russia), 2017, 83–91

[3] N. N. Efanov, P. V. Emelyanov, “Constructing the formal grammar of system calls”, Proceedings of the 13th Central Eastern European Software Engineering Conference in Russia, CEE-SECR'17, ACM, New York, NY, USA, 2017, 12, 5 pp. | DOI

[4] M. Bozyigit, M. Wasiq, “User-level process checkpoint and restore for migration”, ACM SIGOPS Operating Systems Review, 35:2 (2017), 86–96 | DOI

[5] A. Cayley, “A theorem on trees”, Collected Mathematical Papers, 13 (1897), 26–28 | MR

[6] C. Izurieta, J. Bieman, “The evolution of FreeBSD and linux”, Proceedings of the 2006 ACM/IEEE international symposium on Empirical software engineering, ISESE'06, ACM, New York, NY, USA, 2006, 204–211 | DOI

[7] L. Passos, J. Guo, L. Teixeira, K. Czarnecki, A. Wa̧sowski, P. Borba, “Coevolution of variability models and related artifacts: a case study from the Linux kernel”, Proceedings of the 17th International Software Product Line Conference, SPLC'13, ACM, New York, NY, USA, 2013, 91–100 | DOI

[8] Belousov A. I., Discretnaya matematika, 4th edition, Bauman University (BMSTU), M., 2006, 744 pp.

[9] Th. H. Cormen, Ch. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 2nd Edition, MIT Press and McGraw-Hill, 2001 | MR | Zbl

[10] D. E. Knuth, The Art of Computer Programming, v. 1, 3rd edition, Addison-Wesley, Boston, 1997 | MR

[11] K. Krippendorff, “Combinatorial Explosion”, Web Dictionary of Cybernetics and Systems. PRINCIPIA CYBERNETICA WEB, Retrieved 29 November 2010 (Data obrascheniya: 31.05.2018) http://pespmc1.vub.ac.be/ASC/Combin_explo.html

[12] A. V. Aho, J. D. Ullman, The theory of parsing, translation, and compiling, Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1972 (Data obrascheniya: 31.05.2018) https://dl.acm.org/doi/book/10.5555/578789

[13] Okhotin A., Formal'nye grammatiki i vychislitelnaya slojnost' sintaksicheskogo analiza, “Matematika” educational program, SPbSU, 2017

[14] D. J. Weir, Characterizing Mildly Context-Sensitive Grammar Formalisms, Ph.D. thesis, University of Pennsylvania, Philadelphia, USA, 1988 | DOI

[15] M. A. Alonso, V. J. Díaz, “Variants of mixed parsing of TAG and TIG”, Traitement Automatique des Langues (TAL), 44:3 (2003), 41–65

[16] M. Barash, Defining Contexts in Context-Free Grammars, TCCS Dissertation No 204, Turku Center for Computer Science, 2015 (Data obrascheniya: 31.05.2018) https://www.doria.fi/bitstream/handle/10024/113793/TUCSDissertationD204.pdf

[17] P. Boullier, “On Multicomponent TAG parsing”, 6th conference annuelle sur le Traitement Automatique des Langues Naturelles (TALN 1999) (Cargse, Corse, France, 1999), 321–326

[18] P. Boullier, B. Sagot, “Multi-Component Tree Insertion Grammars”, Formal Grammar, FG 2009, Lecture Notes in Computer Science, 5591, eds. de Groote P., Egg M., Kallmeyer L., Springer, Berlin–Heidelberg, 2011 | Zbl

[19] C. Gardent, L. Kallmeyer, “Semantic construction in feature-based TAG”, Proceedings of the tenth conference on European chapter of the Association for Computational Linguistics, EACL'03, v. 1, Association for Computational Linguistics, Stroudsburg, PA, USA, 2003, 123–130 | DOI

[20] M. Kudinova, P. Emelyanov, “Building Mathematical Model for Restoring Processes Tree during Container Live Migration”, IVth International Conference on Engineering and Telecommunication (EnT) (November 2017, Dolgoprudniy) | DOI

[21] M. Zengin, V. Vafeiadis, “A programming language approach to fault tolerance for fork-join parallelism”, Proceedings of the 7th International Symposium on Theoretical Aspects of Software Engineering, TASE 2013, Max Planck Institute for Software Systems (MPI-SWS), Saarsbruchen, Germany, 2013 http://plv.mpi-sws.org/ftpar/tase2013-ftpar.pdf

[22] A. Cherif, M. Suzuki, T. Katayama, “A Replication Technique Based on a Functional and Attribute Grammar Computation Model”, Proceedings of the The Seventh International Symposium on Software Reliability Engineering, ISSRE'96, IEEE Computer Society, Washington, DC, USA, 1996, 266