On some combinatorial properties of LINUX process trees

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.

1. Mirkin A., Kuznetsov A., Kolyshkin K, 2008, “Containers checkpointing and live migration”, Proceedings of the In Ottawa Linux Symposium. Ottawa, Ontario, Canada, vol.2, pp. 85-90.

2. Efanov N.N., Emelyanov P.V. 2017, “Postroenie formal’noj grammatiki sistemnyh vyzovov” , Informacionnoe obespechenie matematicheskih modelej, Moscow, Russia, pp. 83-91.

3. Efanov N. N., Emelyanov P. V. “Constructing the formal grammar of system calls”, In Proceedings of the 13th Central \& Eastern European Software Engineering Conference in Russia (CEE-SECR '17), ACM, New York, NY, USA, Article 12, 5 pages. doi: 10.1145/ 3166094.3166106

4. Bozyigit M., Wasiq M., 2001, “User-level process checkpoint and restore for migration”, ACM SIGOPS Operating Systems Review, vol. 35, no. 2, p.86-96. doi: 10.1145/377069.377091

5. Cayley A. 1897, “A theorem on trees”, Collected Mathematical Papers, Cambridge University Press, vol. 13, pp. 26-28.

6. Clemente Izurieta and James Bieman. 2006, “The evolution of FreeBSD and linux”, In Pro\-cee\-dings of the 2006 ACM/IEEE international symposium on Empirical software engi\-nee\-ring (ISESE '06), ACM, New York, NY, USA, 204-211. doi: 10.1145/1159733.1159765

7. Leonardo Passos, Jianmei Guo, Leopoldo Teixeira, Krzysztof Czarnecki, Andrzej Wąsowski, and Paulo Borba 2013, “Coevolution of variability models and related artifacts: a case study from the Linux kernel”, In Proceedings of the 17th International Software Product Line Conference (SPLC '13), ACM, New York, NY, USA, 91-100. doi: 10.1145/2491627.2491628

8. Belousov, A.I. 2006, Discretnaya matematika, 4th edition, Bauman University (BMSTU), Moscow, p. 349.

9. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2001, Introduction to Algorithms, 2nd Edition, MIT Press and McGraw-Hill. ISBN 0-262-03293-7.

10. Knuth, Donald E. 1997, The Art of Computer Programming, Vol 1., 3rd edition, Boston: Addison-Wesley, ISBN 0-201-89683-4

11. Krippendorff, Klaus, 2010, "Combinatorial Explosion", Web Dictionary of Cybernetics and Systems, PRINCIPIA CYBERNETICA WEB, Retrieved 29 November 2010. Available at: \url{http://pespmc1.vub.ac.be/ASC/Combin_explo.html}

12. Alfred V. Aho , Jeffrey D. Ullman 1972, The theory of parsing, translation, and compiling, Prentice-Hall, Inc., Upper Saddle River, NJ, USA. Available at: \url{dl.acm.org/citation.cfm?id=578789}

13. Okhotin A, 2017, “Formal’nye grammatiki i vychislitelnaya slojnost’ sintaksicheskogo analiza”, “Matematika” educational program, SPbSU. Available at: \url{https://compsciclub.ru/media/slides/formal_grammars_2017_autumn/2017_11_12_formal_grammars_2017_autumn.pdf}

14. David J. Weir. 1988, Characterizing Mildly Context-Sensitive Grammar Formalisms, Ph.D. thesis, University of Pennsylvania, Philadelphia, USA. doi: 10.1145/3166094.3166106

15. Alonso M. A. and D\'iaz V. J. 2003, “Variants of mixed parsing of TAG and TIG”, Traitement Automatique des Langues (T.A.L.), no. 44(3), pp. 41–65.

16. Barash Mihail, 2015, Defining Contexts in Context-Free Grammars, Turku Center for Computer Science, TCCS Dissertation No 204. Available at: \url{https://www.doria.fi/bitstream/handle/10024/113793/TUCSDissertationD204.pdf}

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

18. Boullier P., Sagot B. 2011. “Multi-Component Tree Insertion Grammars”, In: de Groote P., Egg M., Kallmeyer L. (eds) Formal Grammar, Lecture Notes in Computer Science, vol. 5591, Springer, Berlin-Heidelberg.

19. Claire Gardent and Laura Kallmeyer. 2003, “Semantic construction in feature-based TAG”, In Proceedings of the tenth conference on European chapter of the Association for Computational Linguistics - Volume 1 (EACL '03), Vol. 1, Association for Computational Linguistics, Stroudsburg, PA, USA, pp. 123-130. doi: 10.3115/1067807.1067825

20. Marina Kudinova and Pavel Emelyanov. 2017, “Building Mathematical Model for Restoring Processes Tree during Container Live Migration”, IVth International Conference on Engineering and Telecommunication (EnT), November 2017, Dolgoprudniy. doi: 10.1109/ICEnT.2017.41

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

22. Adel Cherif, Masato Suzuki, and Takuya Katayama. 1996, “A Replication Technique Based on a Functional and Attribute Grammar Computation Model”, In Proceedings of the The Seventh International Symposium on Software Reliability Engineering (ISSRE '96), IEEE Computer Society, Washington, DC, USA, p. 266.