Телефон: 8-800-350-22-65
WhatsApp: 8-800-350-22-65
Telegram: sibac
Прием заявок круглосуточно
График работы офиса: с 9.00 до 18.00 Нск (5.00 - 14.00 Мск)

Статья опубликована в рамках: XXI Международной научно-практической конференции «Научное сообщество студентов: МЕЖДИСЦИПЛИНАРНЫЕ ИССЛЕДОВАНИЯ» (Россия, г. Новосибирск, 18 мая 2017 г.)

Наука: Математика

Скачать книгу(-и): Сборник статей конференции

Библиографическое описание:
Агеев Н.О., Булавко А.И. ИСПОЛЬЗОВАНИЕ ДЕТЕРМИНИРОВАННОГО КОНЕЧНОГО АВТОМАТА ДЛЯ ВАЛИДАЦИИ ПОЛЬЗОВАТЕЛЬСКИХ ДАННЫХ // Научное сообщество студентов: МЕЖДИСЦИПЛИНАРНЫЕ ИССЛЕДОВАНИЯ: сб. ст. по мат. XXI междунар. студ. науч.-практ. конф. № 10(21). URL: https://sibac.info/archive/meghdis/10(21).pdf (дата обращения: 29.03.2024)
Проголосовать за статью
Конференция завершена
Эта статья набрала 557 голосов
Дипломы участников
Диплом лауреата
отправлен участнику

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

Агеев Николай Олегович

студент института информатики, математики и электроники Самарского университета,

РФ, г.Самара

Булавко Ангелина Игоревна

студент института информатики, математики и электроники Самарского университета,

РФ, г.Самара

Тишин Владимир Викторович

научный руководитель,

доц. кафедры прикладной математики Самарского университета,

РФ, г.Самара

Использование информационных технологий для современного человека является повседневной задачей. Благодаря программным решениям и 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)
Проголосовать за статью
Конференция завершена
Эта статья набрала 557 голосов
Дипломы участников
Диплом лауреата
отправлен участнику

Комментарии (5)

# Владислав 23.05.2017 22:27
Это не научная работа, а просто заметка о том, как мы решили выпендриться. Почему распишу по пунктам: 1) if в switch в while, тройная вложенность, и после этого вы заявляете о более высоком быстродействие, подумайте и проведите сравнительно тестирование 2) Вы приводите как аргументы против использование регулярных выражений следующие пункты "С помощью регулярных выражений возможна проверка только на соответствие. Выполнить дополнительные действия по аудиту входящего набора символов становится недоступным (например, проверка на состояние адреса в черном списке)." Да, при помощи регулярных выражений можно сделать только проверку на соответствие, но и при помощи вашего метода проверяется только это, никаких проверок на состояние адреса в черном списке вы не проверите по-символьно. В зависимости от выбранного языка программирования написание регулярных выражений отличается, и такая задача, как проверка правильности ввода почтового адреса может быть растянута на более чем 6000 символов (интерпретируемый язык Perl). Реализация вашего алгоритма так же может быть затруднительна на других языках программирования. К тому же вы не указали какой язык использовали и о том, что вы использовали можно догадаться только посмотрев список использованной литературы.
# Александр 25.05.2017 01:35
Отличная статья
# Москаленко Александр 25.05.2017 01:42
отличная статья
# Василий 29.05.2017 19:58
Язык программирования не указан!
# Николай 29.05.2017 23:01
Уважаемый Владислав, спасибо за ваш комментарий. В любом случае приятно, когда твоя работа вызывает какие-либо эмоции. Отвечая на ваши замечания хотелось бы немножко прояснить ситуацию: 1) Язык программирования, используемый в научной работе был явно указан в самой статье, а именно: (Цитата) "Для демонстрации работоспособности нашего алгоритма используем язык javascript, который является одним из основных при разработке WEB приложений." Так что не нужно догадываться и заглядывать в список литературы. 2) Относительно проверки на содержание адреса в черном списке. Было сказано, что "можно" делать такие проверки или проверять другие дополнительные условия в данном алгоритме, в сравнении с которым в регулярных выражениях этого не получится, а только совершить проверку на соответствие. 3)Относительно вложенности циклов и медленности алгоритмов. Если речь идет о простом варианте почтового адреса, например указанном в начале статьи, то здесь вы можете быть правы. Тесты проводились и при таком раскладе выполнение реализации детерминированного конечного автомата займет столько же, а может и больше времени. Но при значительно большей необходимости в количестве условий ля проверки, иными словами для адреса, соответствующего RFC, регулярные выражения сильно проигрывают во времени.

Оставить комментарий

Форма обратной связи о взаимодействии с сайтом
CAPTCHA
Этот вопрос задается для того, чтобы выяснить, являетесь ли Вы человеком или представляете из себя автоматическую спам-рассылку.