Конечный автомат для поиска строковых значений в исходном коде Perl-программ

УДК 004.423.2

КОНЕЧНЫЙ АВТОМАТ ДЛЯ ПОИСКА СТРОКОВЫХ ЗНАЧЕНИЙ В ИСХОДНОМ КОДЕ PERL-ПРОГРАММ

А. А. Мышенков

FINITE-STATE MACHINE FOR SEARCHING STRING VALUES IN

PERL SOURCE CODE

А. A. Myshenkov

Аннотация. Актуальность и цели. При оптимизации или обфускации кода одним из главных требований является сохранение функциональных возможностей программы. Это зависит от точности результатов лексического анализа. В данной работе рассматривается решение проблемы поиска строковых значений в исходном тексте на языке программирования Perl. Основной сложностью проведения такого поиска является особенность языка Perl, позволяющая записывать один и тот же алгоритм разными способами, в том числе и объявление строковых значений. Материалы и методы. Лексический анализ строковых значений осуществляется с помощью конечного автомата, на вход которого подаются символы строк кода. Результаты. Разработан алгоритм конечного автомата, который может быть использован в методах обфускации. Выводы. В результате исследования разработан алгоритм, позволяющий получить точные результаты лексического анализа, связанные с нахождением строковых значений. Благодаря этому соблюдаются условия сохранения функциональности программы и уменьшается вероятность возникновения ошибок при проведении обфускации.

Ключевые слова: лексический анализ, Perl, конечный автомат.

Abstract. Background. During the optimization or obfuscation of source code one of the major requirement is saving of program functionality. It depends on the accuracy of the result of lexical analysis. In this paper decision of string values search problem in Perl source code is researched. The main complexity of such searching is a feature of Perl, which allows to code one algorithm by different ways including string values. Materials and methods. Lexical analysis for searching string values is carried with finite-state machine. Characters of code line are input to finite-state machine. Results. Finite-state machine algorithm was designed. It can be used in obfuscation methods. Conclusions. Because of research, developed algorithm, which allows get accurate results of lexical analysis for search string values. Thereby a condition is observed to save program functionality and decrease probability of errors.

Key words: lexical analysis, Perl, finite-state machine.

Введение

Лексический анализ текстов на языках программирования наряду с синтаксическим и семантическим анализом имеет очень обширную область применения. Кроме использования в компиляторах и интерпретаторах методы лексического анализа применяются также для построения сред разработки, оптимизации и обфускации кода. При применении методов оптимизации или обфускации кода одним из главных требований является функциональность, т.е. полное сохранение функциональных возможностей программы [1].

Главным образом функциональность зависит от точности результатов лексического анализа. В данной статье рассмотрим решение проблемы поиска строковых значений на примере анализа текста на языке программирования Perl. Естественно, лексический анализ проводится в самом интерпретаторе Perl, а также существуют стандартные модули форматирования, такие как Deparse, но данных средств недостаточно для получения точных данных о местоположении строковых значений в коде. Однако эти средства могут использоваться в качестве вспомогательных.

Постановка задачи

Одной из особенностей языка Perl является принцип «There's More Than One Way To Do It» («Есть больше одного способа сделать это») [3]. Это подразумевает возможность записи одного и того же алгоритма множеством способов. Данный принцип применим и к записи строковых значений.

В Языке Perl строковые значения определяются операторами кавычек (" и '), операторами q, qq, в которых ограничителями могут выступать как парные символы ((), {}, <>, []), так и повторяющиеся одиночные символы из множества букв и спецсимволов [2]. Операторы кавычек и символы ограничителей строковых значений сами могут находиться внутри строкового значения при использовании оператора экранирования. Таким образом, строковые значения являются частным случаем контекстно-свободной грамматики вложенных скобок. Это означает, что лексический анализ с применением шаблонов регулярных выражений ко всей строке невозможен, так как необходимо учитывать операторы экранирования и вложенность скобок. В связи с этим лексический анализ строковых значений осуществляется с помощью конечного автомата, на вход которого подаются символы строк кода. Состояния конечного автомата меняются при обнаружении операторов кавычек, ограничителей строковых значений, операторов скобок со счетчиком вложенности скобок, операторов экранирования.

Для избегания ошибок при интерполяции переменных необходимо провести форматирование текста с помощью стандартного модуля Perl Deparse [3]. В процессе форматирования интерполяция переменных заменяется конкатенацией. Это позволяет точно определить, что внутри строковых значений не будет интерполированных имен переменных. Все переменные в этом случае соединяются со строковыми значениями оператором конкатенации (.).

Для избегания путаницы будем называть искомые строки PERL-строками.

Алгоритм работы

Рассмотрим подробнее алгоритм конечного автомата M для поиска PERL-строк

M = (S, I*, Q, Fq, Ft),

где S - входная строка, множество входных символов длиной l, подаваемая на вход автомата; i - индекс элемента множества входных символов; I -множество индексов:

S = {¿1,...,si}, iе I = {!,...,l}, l = | Si.

Состояния Q автомата определяются несколькими триггерами T, счетчиком C :

Q = ^ Чъ Чп J, j = {1, q} = {TS, T', T", Tq , TQQ, TB, TD, TE, CB J,

T e {0,1J, C e Z .

I - множество индексов, которые соответствуют найденным символам PERL-строк:

т* Г* -*1 т* т О* О О* * т*

I ={/1,-,/k J, I СI, S с S, v* e S , 1 e I .

Таким образом, S * - подстрока с найденными PERL-строками, а I * -массив индексов для нахождения подстроки PERL-строк в основной строке.

Триггер пробела TS определяет состояние автомата, при котором возможно появление операторов начала строкового значения. Например, после форматирования кода операторы кавычек могут располагаться после пробела или скобок:

$x = 'string';

$y = $hash{"key"};

@a = ('a', 'b', 'c');

$string = 'concatenated' . 'string' . "\n";

В данном случае PERL-строками будут являться значения: string, key, a, b, c, concatenated, string, \n. Символы, располагающиеся перед операторами кавычек в данном примере, - это символ пробела, символы открывающихся скобок { и (.

Триггер одинарной кавычки T определяет состояние автомата после открытия одинарной кавычки.

Триггер двойной кавычки T'' определяет состояние автомата после открытия двойной кавычки.

Триггеры операторов q и qq - TQ и TQQ соответственно.

Триггер скобок в качестве ограничителей строковых значений - TB , BO и BC - символы открывающей и закрывающей скобки соответственно: BO e { (,{,[,< } и BC e { ),},],> }.

Для проверки сбалансированности скобок используем счетчик CBeZ . При CB = 0 скобки считаются сбалансированными, т.е. количество открывающих и закрывающих скобок равно. При появлении открывающей скобки значение счетчика увеличивается на 1, соответственно, при появлении закрывающей скобки значение счетчика уменьшается на 1. Счетчик сбалансированности скобок работает для символов BO и BC , которые были определены оператором q или qq. Символы других скобок игнорируются. Экранированные символы скобок также игнорируются.

Триггер одиночного символа в качестве ограничителя строковых значений - Т°, Б е {а ..г, А ..2, 0..9, !, @, #, $, %, а, &, *,+, =,_,,, .,;,

$81г1п§ =

$81ппв = д('!@#$ %Л&*"[{(<]})>/;.,д\\]);

$81г1пе = д<'!@#$ %А&*"[{(<]})>/;.^\\])>;

= я{"!@#\\$ %А&*'[{(<]})>/;.,\\д\\]>)};

В указанных примерах в качестве разделителей РБКЬ-строк выступают парные символы скобок: [],(),{},<>. Таким образом, найденные РБКЬ-строки будут соответствовать следующим наборам символов:

I

'!@#$ %А&*"[{(<]})>/;.,д\\],

'!@#$ %А&*"[{(<]})>/;.,Я\\]),

{"!@#\\$ %А&*'[{(<]})>/;.,\\д\\]>).

Так как в данном случае в качестве ограничителя могут выступать только сбалансированные скобки, другие символы скобок внутри сбалансированных ограничителей не учитываются.

В следующем примере показаны одиночные символы в качестве ограничителя РБКЬ-строк.

$string = qq'$string';

$string = q qabc4q;

$string = qq qabc5q;

В данном случае ограничителями выступают символ одинарной кавычки ' и сам символ буквы q. РБКЬ-строки соответственно равны: $string, аЬс4, аЬс5.

Триггер экранирования - ТЕ, Ее { \ }. При появлении символа экранирования следующий за ним символ игнорируется, в том числе и сам символ обратной косой черты.

В начале алгоритма все триггеры устанавливаются в значение по умолчанию, равное 0. Таким образом, начальное состояние:

д0 = |т5,Т',Т'',ТЯ,Твв,Тв,Т°,ТЕ,Св}, Т = 0, С = 0,

N = 0.

Все значения переменных символов ограничителей и скобок устанавливаются в значение пустой строки.

На вход поступает строка кода, которая разбивается на последовательность символов. Далее происходит пошаговая обработка каждого символа. В зависимости от входного символа и текущего состояния выполняются следующие функции:

^ : 0х5 ^ 0, ^ : 0х5 ^ I*.

- функция, определяющая переход из одного состояния в другое.

^ - функция, определяющая соответствие входного символа литералу, в зависимости от текущего состояния д и текущего символа 5 .

Блок-схема алгоритма работы конечного автомата изображена на рис. 1.

Рис. 1. Блок-схема алгоритма поиска строковых значений

В основном цикле выполняется пять подпрограмм, отмеченных на рисунке цифрами от 1 до 5. Блоки 1-4 реализуют функцию , т.е. непосредственно поиск символов, соответствующих строковому значению. Блок 5 реализует функцию и переключает триггеры, таким образом обеспечивая

переход состояний.

На рис. 2 изображен алгоритм подпрограммы 1. В данном примере показан поиск строковых значений внутри одинарных кавычек. Состояния определяются триггерами одинарной кавычки и экранирования:

0 е{д,,д}}, д, = {т',ТЕ}, где ^ е {',\}, д} = {т'}, где * Ф '.

Начала

Него

Установить = О

Конеа

Рис. 2. Блок-схема подпрограммы поиска значений внутри одинарных кавычек

Пример работы алгоритма

Рассмотрим пример работы автомата на следующей строке кода: $x = 'abc';

i si TS t' t' tq tqq Tв TD TE CB BO BC I*

0 0 0 0 0 0 0 0 0 0 0 0 0

i i

Перейти без изменений

1 "x" 0 0 0 0 0 0 0 0 0 0 0 0

i i

Перейти без изменений

2 " " 0 0 0 0 0 0 0 0 0 0 0 0

i i i

Обнаружен символ пробела. Установить TS = 1 и перейти.

3 " = " 1 0 0 0 0 0 0 0 0 0 0 0

i i i

Установить TS = 0 и перейти.

4 " " 0 0 0 0 0 0 0 0 0 0 0 0

i i i

Обнаружен символ пробела. Установить TS = 1 и перейти.

5 1 0 0 0 0 0 0 0 0 0 0 0

i i i

Обнаружен символ одинарной кавычки и TS = 1 .

Установить T 1 , установить T S = 0 и перейти.

6 "a" 0 1 0 0 0 0 0 0 0 0 0 0

i i i

T = , добавить индекс в I* , перейти.

7 "b" 0 1 0 0 0 0 0 0 0 0 0 {6}

i i i

T = , добавить индекс в I* , перейти.

8 "c" 0 1 0 0 0 0 0 0 0 0 0 {6,7}

i i i

T = , добавить индекс в I* , перейти.

9 0 1 0 0 0 0 0 0 0 0 0 {6,7,8}

i i i

Обнаружен символ одинарной кавычки и T =1

Установить T = 0 , перейти.

10 0 0 0 0 0 0 0 0 0 0 0 {6,7,8}

i i i

Конец строки.

Таким образом, в результате выполнения получаем множество найденных индексов I* = {6,7,8} . Отсюда следует, что найденная PERL-строка равна S* = {s6,s7,s8} = abc .

Заключение

В результате проведенного исследования получен алгоритм конечного автомата для поиска строковых значений в тексте исходного кода программ на языке Perl. В результате работы конечного автомата можно получить точное местоположение найденных символов в строке, что невозможно при использовании стандартных средств интерпретатора Perl. Полученные данные могут быть использованы для применения методов обфускации, например, метода шифрования строковых данных с соблюдением условия сохранения

функциональности программы и уменьшением вероятности возникновения ошибок, связанных с неточным определением строковых значений.

Список литературы

1. Варновский, Н. П. Математические проблемы обфускации / Н. П. Варновский, В. А. Захаров, Н. Н. Кузюрин // Математика и безопасность информационных технологий : материалы конф. в МГУ (28-29 октября 2004 г.). - М. : МЦНМО, 2005. - С. 65-91.

2. Шохирев, М. В. Язык программирования Perl 5 / М. В. Шохирев. - М. : Интернет-университет информационных технологий, 2007. - 192 с.

3. B::Deparse. - URL: http://perld0c.perl.0rg/B/Deparse.html (дата обращения: 14.02.2016).

Мышенков Артем Алексеевич аспирант,

Самарский государственный технич университет

E-mail: artem.myshenkov@gmail.com

Myshenkov Artem Alekseevich

postgraduate student,

Samara State Technical University

УДК 004.423.2 Мышенков, А. А.

Конечный автомат для поиска строковых значений в исходном коде РЕКЬ-программ / А. А. Мышенков // Модели, системы, сети в экономике, технике, природе и обществе. - 2016. - № 2 (18). - С. 223-230.