Constructing the Formal Grammar of System Calls

October 21, 10:30
Room III

The mathematical model of userspace-based process tree reconstruction via syscall sequences is constructed on the basis of the type-0 formal grammar and prototyped as two-staged grammar analyser with 3 heuristics for grammar shortening. The prototype has been developed to compare with profile-based techniques of syscall collection. The results of experimental comparison with two profile-based tools indicate the possibility of grammatical analysis competitive application for metadata reconstruction in checkpoint-restore tools.

The report is aimed at specialists working at the intersection of discrete mathematics, operating systems, virtualization technologies. It will be interesting both for developers and architects who use checkpoint-restore for processes, VMs and containers in their projects, and applied mathematicians working with mathematical models in computer science.

The audience will learn how to restore the process-tree state relatively quickly, without direct tree generation, profiling and a lot of heuristics and find out design and computing shortcomings of existing solutions; Learn a lot of problem-specific info: how to compactly store the process-tree in a string and how the stack-frame helps to parse such strings efficiently to restore the chains of syscalls, what cases of tree configuration are the most trivial and laborious, where is the limit when ptrace-based solutions are not looks such slow.

Knowing the approaches to recovering and analyzing the syscall sequences is an important step towards effectively addressing the various tasks of virtualization, checkpoint-restore, live migration and software vulnerabilities detection.

Nikolay Efanov

Postgraduate/Teaching-assistant, MIPT

2016-2017 Worked on a grant from the Infotecs-Academy, winner of the research support program.

2015-2016 Worked as a Junior Software Developer in Virtuozzo(former Parallels).

2014-2015 Worked as a Junior Software Developer in Parallels.

2010-2016 Studying at the Moscow Institute of Physics and Technology. Graduated from the Faculty of Management and Applied Mathematics in 2016. Postgraduate student of the Department of Informatics.

2007-2010 Studied at the Taurida NU at the Faculty of Applied Mathematics

Born in Simferopol in 1990.

Sponsors & Partners



JetBrainsFirst Line Software


Dell EMCDINSVeeam Software




I.T. GroupT-SystemsUnited Frontal System Program


Andrey Terekhov


Main partners


In cooperation

Association for Computing MachineryACM Special Interest Group on Software Engineering

Technical partners

CUSTISSoftInvent7pap StudioHosting-CenterGroup MPrezentPrint SalonDPI.Solutions

With support of



Software Russiai-Help