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

Использование информационных технологий для современного человека является повседневной задачей. Благодаря программным решениям и WEB технологиям люди общаются, совершают покупки через интернет, проводят исследовательские работы. Соответственно, огромное количество данных обрабатывается в каждый момент времени и если используемый сервис будет делать это некорректно, конечный пользователь останется недоволен. Рассмотрение вопроса правильной обработки и валидации принятой программой информации на соответствие необходимым требованиям важно не только с целью удобства использования того или иного приложения, но так же и с целью устранить возможные проблемы в безопасности продукта. Множество мошенников, имеющих специализированные навыки используют ошибки в разработанных интернет сайтах и нативных программах для получения несанкционированного доступа к персональным данным и дополнительным возможностям, таким, как превышение полномочий до уровня администратора. Поэтому правильная фильтрация получаемых данных необходима для создания устойчивого и безопасного сервиса.

В программных технологиях повсеместно применяется практическая реализация модели конечного автомата (Finite-state machine). Конечный автомат используется для представления и управления потоком выполнения каких-либо команд. На основе данного решения работают компиляторы машинного кода существующих компьютеров. Также, конечный автомат используется для написания сложных искусственных интеллектов и создания программного обеспечения для транспортной логистики.

Детерминированным конечным автоматом (ДКА) называется устройство, имеющее следующие параметры [3, стр. 293]:

• Q – конечное множество состояний.
• Σ – конечное множество входных символов.
• δ – функция перехода. Аргументы – состояние и входной символ, результат – состояние.
• s0 – начальное состояние, принадлежит Q.
• F – множество допускающих состояний, является подмножеством Q.

Работа ДКА осуществляется таким образом:

• При начале работы автомат переходит в состояние s0.
• Если автомат находится в состоянии si, а на вход поступает очередной символ a, то автомат переходит в состояние δ(qi, a).

Рисунок 1. Пример детерминированного конечного автомата

Существенным отличием детерминированного конечного автомата является то, что при заданной любой последовательности входных символов из текущего состояния существует лишь одно, в которое автомат может перейти. Благодаря этому его применение в программировании, а в частности при обработке пользовательских данных, может быть очень полезным.

Возвращаясь к валидации пользовательских данных, рассмотрим реализацию проверки поля для ввода E-mail адреса в WEB приложении. Предположим, есть простая задача – создать форму, при заполнении которой пользователь сможет подписаться на рассылку почтовых сообщений. Задача программиста состоит в необходимости проверки полученных данных из поля ввода на предмет соответствия некоторому шаблону. Правильный шаблон должен отфильтровать полученные данные от лишних символов, которые могут использоваться злоумышленниками для эксплуатирования уязвимостей, но при этом не должны возникать ситуации, когда валидный адрес вдруг был бы заблокирован приложением. При этом возможна необходимость проверки состояния полученного адреса (активен, заблокирован).

Для создания подобных шаблонов с последующей проверкой данных на соответствие этому шаблону большинство разработчиков используют регулярные выражения - формальный язык поиска и осуществления манипуляций с подстроками  в тексте, основанный на использовании метасимволов. Для поиска используется строка-образец, которую часто называют шаблоном и которая задает правило поиска. Большинство символов в регулярном выражении представляют сами себя за исключением специальных символов [ ] \ / ^ $ . | ? * + ( ) { }. Они называются метасимволами, каждый из которых устанавливает определенное правило. Например, знак плюс означает возможность одного или более повторений при сравнении строки с шаблоном, знак вопроса означает число повторений ноль, либо одно и т.д.

Для создания правильного шаблона для поля ввода E-mail адреса нужно иметь представление, как почтовый адрес может выглядеть. Интуитивно можно предположить следующее:

Рисунок 2. Общий вид E-mail адреса

Основываясь на данном общем виде, можно создать регулярное выражение, которое будет пропускать только правильные адреса:

[a-zA-Z0-9]+@[a-zA-Z0-9]+\.[a-zA-Z0-9]+

На самом же деле такой метод будет работать лишь в малом количестве случаев, так как существуют определенные требования, описанные в спецификации RFC 2822 (документ  из серии пронумерованных информационных документов Интернета, содержащих технические спецификации и стандарты, широко применяемые во всемирной сети), которые позволяют создавать адреса следующих видов:

• test-one (адреса без доменного имени являются локальными для сервера)
• test-two@com (соответствует спецификации, но вряд ли существует)
• test-three@example.c (соответствует спецификации, но доменов из одной буквы не существует)
• 
  

  (домен, являющийся частью домена более высокого уровня, такой как .co.uk)

• 
  

  (IP адрес сервера вместо домена допускается)

• test@-five.com (соответствует спецификации, но такой домен невозможно зарегистрировать)
• 
  

  (допускаются точки внутри имени пользователя)

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

(?:[a-z0-9!#$%&'*+/=?^_`{|}~-]+(?:\.[a-z0-9!#$%&'*+/=?^_`{|}~-]+)*|"(?:[\x01-\x08\x0b\x0c\x0e-\x1f\x21\x23-\x5b\x5d-\x7f]|\\[\x01-\x09\x0b\x0c\x0e-\x7f])*")@(?:(?:[a-z0-9](?:[a-z0-9-]*[a-z0-9])?\.)+[a-z0-9](?:[a-z0-9-]*[a-z0-9])?|\[(?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)\.){3}(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?|[a-z0-9-]*[a-z0-9]:(?:[\x01-\x08\x0b\x0c\x0e-\x1f\x21-\x5a\x53-\x7f]|\\[\x01-\x09\x0b\x0c\x0e-\x7f])+)\])

Отсюда вытекает несколько проблем:

• Сложность полной проверки правильности данного выражения. Функциональность таких решения дополняется постепенно до тех пор, пока работа с выражением становится невозможной.
• Чем длиннее выражение, тем дольше оно будет компилироваться, так как сравнение всегда происходит за O(n). Как следствие, теряется его эффективность и целесообразность применения.
• С помощью регулярных выражений возможна проверка только на соответствие. Выполнить дополнительные действия по аудиту входящего набора символов становится недоступным (например, проверка на состояние адреса в черном списке).
• В зависимости от выбранного языка программирования написание регулярных выражений отличается, и такая задача, как проверка правильности ввода почтового адреса может быть растянута на более чем 6000 символов (интерпретируемый язык Perl).

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

Для демонстрации работоспособности нашего алгоритма используем язык javascript, который является одним из основных при разработке WEB приложений. Пусть:

• Σ – множество символов полученного адреса
• δ – наша функция обработки символов is_valid()
• Q – множество из 6 состояний:
  
  • s0 – начальное состояние, проверка первого символ текстовой части локального имени
  • s1 – проверка остальных символы текстовой части локального имени
  • s2 – переход к текстовой части локального имени при наличии в нем точки
  • s3 – переход к доменной части, проверка первого символа
  • s4 – проверка остальных символов доменной части
  • s5 – переход к текстовой части доменной части при наличии в ней точки
  • s6 – конечное состояние, означающее, что адрес валиден

Изобразим диаграмму переходов для первой части нашего алгоритма.

Рисунок 3. Диаграмма переходов первой части алгоритма

Вершина графа - состояние проверки. Ребро графа - прочитанный символ. Если в результате считывания символа невозможно перейти ни по одному ребру, значит, адрес не валиден. Реализация первойчасти этого алгоритма:

                case 0: {

// Первый символ текстовой части локального имени

                    if ((symbol >= 'a' && symbol <= 'z') || (symbol >= 'A' && symbol <= 'Z') || (symbol >= '0' && symbol <= '9') || symbol == '_' || symbol == '-' || symbol == '+') {

                        state = 1;

                        break;

                    }

// Переход в состояние ошибки, если встретился недопустимый символ

                    state = -1;

                    break;

                }

После прохождения этой диаграммы необходимо сделать дополнительные проверки:

• Домен должен быть по меньшей мере второго уровня
• Спецификация RFC 5321 ограничивает длину имени ящика до 64 символов
• Спецификация RFC 5321 ограничивает длину адреса до 254 символов
• Доменная зона должна состоять только из букв и быть по меньше мере два символа длинной

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

Рисунок 4. Диаграмма переходов полного алгоритма

Приведенный ниже код выполняет проверку полученного почтового адреса на валидность с помощью реализации детерминированного конечного автомата по представленной диаграмме:

class EmailTester {

    is_valid(address) {

        if (address == null)return false;

        var state = 0;

        var symbol;

        var index = 0;

        var mark = 0;

        var local = null;

        var domain = [];

        while (index <= address.length && state != -1) {

            if (index == address.length) {

                symbol = '\0';

// Обозначается конец работы

            }

            else {

                symbol = address[index];

                if (symbol == '\0') {

// Cимвол обозначения конца работы не может быть частью введенного адреса

                    return false;

                }

            }

            switch (state) {

                case 0: {

// Первый символ текстовой части локального имени

                    if ((symbol >= 'a' && symbol <= 'z') || (symbol >= 'A' && symbol <= 'Z') || (symbol >= '0' && symbol <= '9') || symbol == '_' || symbol == '-' || symbol == '+') {

                        state = 1;

                        break;

                    }

// Переход в состояние ошибки, если встретился недопустимый символ

                    state = -1;

                    break;

                }

                case 1: {

// Оставшиеся символы текстовой части локального имени

                    if ((symbol >= 'a' && symbol <= 'z') || (symbol >= 'A' && symbol <= 'Z') || (symbol >= '0' && symbol <= '9') || symbol == '_' || symbol == '-' || symbol == '+') {

                        break;

                    }

                    if (symbol == '.') {

                        state = 2;

                        break;

                    }

                    if (symbol == '@') {

// Переход к концу работы с локальной частью

                        local = address.substring(0,index-mark);

                        mark = index + 1;

                        state = 3;

                        break;

                    }

// Переход в состояние ошибки, если встретился недопустимый символ

                    state = -1;

                    break;

                }

                case 2: {

// Переход к работе с текстовой частью после точки

                    if ((symbol >= 'a' && symbol <= 'z') || (symbol >= 'A' && symbol <= 'Z') || (symbol >= '0' && symbol <= '9') || symbol == '_' || symbol == '-' || symbol == '+') {

                        state = 1;

                        break;

                    }

// Переход в состояние ошибки, если встретился недопустимый символ

                    state = -1;

                    break;

                }

                case 3: {

// Переходим к проверке первого символа доменной части

                    if ((symbol >= 'a' && symbol <= 'z') || (symbol >= '0' && symbol <= '9') || (symbol >= 'A' && symbol <= 'Z')) {

                        state = 4;

                        break;

                    }

// Переход в состояние ошибки, если встретился недопустимый символ

                    state = -1;

                    break;

                }

                case 4: {

// Оставшиеся символы текстовой части доменного имени

                    if ((symbol >= 'a' && symbol <= 'z') || (symbol >= '0' && symbol <= '9') || (symbol >= 'A' && symbol <= 'Z')) {

                        break;

                    }

                    if (symbol == '-') {

                        state = 5;

                        break;

                    }

                    if (symbol == '.') {

                        domain.push(address.substring(mark, index - mark));

                        mark = index + 1;

                        state = 5;

                        break;

                    }

// Проверка на конец строки

                    if (symbol == '\0') {

                        domain.push(address.substring(mark, index - mark));

                        state = 6;

                        break;

// Переход к заключительному состоянию при достижении конца строки

                    }

// Переход в состояние ошибки, если встретился недопустимый символ

                    state = -1;

                    break;

                }

                case 5: {

                    if ((symbol >= 'a' && symbol <= 'z') || (symbol >= '0' && symbol <= '9') || (symbol >= 'A' && symbol <= 'Z')) {

                        state = 4;

                        break;

                    }

                    if (symbol == '-') {

                        break;

                    }

// Переход в состояние ошибки, если встретился недопустимый символ

                    state = -1;

                    break;

                }

                case 6: {

// Достижение заключительного состояния

                    break;

                }

            }

            index++;

        }

// Дополнительные проверки

// Возвращаем ошибку, если не ранее не совершен переход в заключительное состояние

        if (state != 6)return false;

// Домен должен быть как минимум второго уровня

        if (domain.length < 2)return false;

// Ограничения длины локальной части по спецификации RFC 5321

        if (local.length > 64)return false;

// Ограничения длины всего адреса по спецификации RFC 5321

        if (address.length > 254)return false;

// Домен верхнего уровня должен состоять только из букв и быть не короче двух символов

        index = address.length - 1;

        while (index > 0) {

            symbol = address[index];

            if (symbol == '.' && address.length - index > 2)return true;

            if (!((symbol >= 'a' && symbol <= 'z') || (symbol >= 'A' && symbol <= 'Z'))) {

                return false;

            }

            index--;

        }

        return true;

    }

}

Созданный класс обеспечивает работу алгоритма с помощью функции переходов is_valid(), которая принимает на вход полученный от пользователя почтовый адрес. Данный метод является эффективным аналогом использования регулярных выражений, обеспечивая более высоко быстродействие, а так же дает возможность поддержки приложения при необходимых дополнениях и правках. Разработчик получает простой инструмент для проверки E-mail адреса на соответствие спецификации и фильтрации вводимых данных от вновь появляющихся уязвимостей.

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

1. Брюс Шнайер. Секреты и ложь. Безопасность данных в цифровом мире. Издательский дом: Питер, 2003.
2. Дэвид Флэнаган. JavaScript. Подробное руководство. Издательство: Символ-Плюс, 2013 – 165 c.
3. Тишин В.В. Дискретная математика в примерах и задачах: Самара, 2007 - 293 с. [электронный ресурс] - URL: http://repo.ssau.ru/handle/Uchebnye-posobiya/Diskretnaya-matematika-v-primerah-i-zadachah-Elektronnyi-resurs-elektron-ucheb-posobie-54961 (дата обращения 18.05.2017)