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.