Взаимодействие в открытых сетях несёт определённые риски. Для обеспечения информационной безопасности участников сетевого взаимодействия используют криптографические протоколы. Высокие гарантии безопасности могут быть достигнуты в результате их формальной верификации. Распространённым формальным методом верификации криптографических протоколов является метод проверки модели. В работе для проверки модели криптографических протоколов предлагается использовать инструментальное средство TLA+/TLC, широко применяемое на практике в различных прикладных областях. На языке спецификации TLA+ задаётся модель протокола, а также требуемые свойства безопасности в форме инвариантов. Модель протокола описывает его поведение в виде системы переходов, содержащей все возможные состояния модели протокола и переходы между ними. Для проведения автоматической проверки соответствия модели требуемым свойствам задействуется верификатор TLC. Задача верификации криптографических протоколов имеет свою специфику. Настоящее исследование предлагает три приёма моделирования, учитывающих особенности данной задачи и используемого инструментария TLA+/TLC. Первый приём моделирования состоит в замене системы, состоящей из произвольного количества агентов, на трёхагентную систему. Это позволяет упростить модель и уменьшить её пространство состояний. Второй приём связан с представлением передаваемых сообщений в виде иерархической структуры — это даёт возможность вкладывать одни зашифрованные сообщения в другие. Третий приём состоит в оптимизации модели с целью повышения производительности верификатора TLC. Это выполняется путем задания функции, порождающей множество только тех элементов, которые приводят к переходам между состояниями в модели. В итоге предложенные приёмы позволяют упростить модель и снизить время её верификации. Применение результатов демонстрируется на примере простого протокола — протокола Нидхема-Шредера для аутентификации с открытым ключом. После обнаружения верификатором TLC известной уязвимости этого протокола выполняется моделирование и верификация его доработанной версии. Результаты верификации показывают, что новая версия протокола не имеет данной уязвимости.
В работе рассматривается класс расширенных регулярных выражений с обратными ссылками, которые представляются как элементы полукольца, частично удовлетворяющего теоремам алгебры Клини. Используя эти теоремы в качестве правил переписывания, возможно построить алгоритм устранения неоднозначности в ячейках памяти выражений. В дальнейшем этот алгоритм может быть применён для построения обращений расширенных регулярных выражений в заданных ограничениях. Предложенные алгоритмы были апробированы на тестовой выборке регулярных выражений, построенных на базе выражений из RegexLib и StackOverflow. Результаты экспериментов показали, что в ряде случае время сопоставления с преобразованным регулярным выражением было значительно меньше, чем с исходным.
Процесс-ориентированное программирование — это подход к разработке управляющего программного обеспечения, в котором программа определяется как набор взаимодействующих процессов. PoST — это процесс-ориентированный язык, который является расширением языка ST из стандарта IEC 61131-3. В области разработки управляющего программного обеспечения формальная верификация играет важную роль вследствие необходимости обеспечения высокой надежности такого программного обеспечения. Дедуктивная верификация — это метод формальной верификации, в котором программа и требования к ней представляются в виде логических формул, а для доказательства того, что программа удовлетворяет требованиям, используется логический вывод. К управляющему программному обеспечению часто предъявляются темпоральные требования. Мы формализуем такие требования для процесс-ориентированных программ в виде инвариантов цикла управления. Но инварианты цикла управления, представляющие требования, недостаточны для доказательства корректности программы. Поэтому мы добавляем дополнительные инварианты, которые содержат вспомогательную информацию. В данной статье рассматривается проблема автоматизации дедуктивной верификации процесс-ориентированных программ. Предложен подход, в котором темпоральные требования задаются с использованием шаблонов требований, которые строятся из базовых шаблонов. Для каждого шаблона требований определяются соответствующий шаблон дополнительных инвариантов и леммы. В статье описан предлагаемый подход и схемы базовых и производных шаблонов требований. Рассмотрены схемы базовых шаблонов дополнительных инвариантов, схемы лемм, определяемых для базовых шаблонов, а также набор базовых шаблонов и леммы для них. Определены схема производных шаблонов дополнительных инвариантов и схемы лемм, определяемых для производных шаблонов. Представлены алгоритмы построения производных шаблонов дополнительных инвариантов и лемм для них, а также метод доказательства этих лемм. Рассмотрены схемы доказательства условий корректности. Предложенный подход демонстрируется на примере. Также проведен анализ связанных работ.
Статья посвящена задаче определения тональности по отношению к аспектам социально-экономического развития в предложениях на русском языке. Аспект, отношение к которому определяется, может как упоминаться явно, так и подразумеваться. Авторами были исследованы возможности применения нейросетевых классификаторов, а также предложен алгоритм определения тональности по отношению к аспекту, основанный на семантических правилах, реализованных с использованием деревьев синтаксических единиц. Тональность по отношению к аспекту определяется в два этапа. На первом этапе в предложении отыскиваются аспектные термины — явно упоминаемые события или явления, связанные с аспектом. На втором этапе тональность по отношению к аспекту определяется как тональность по отношению к аспектному термину, который теснее всего связан с аспектом. В работе предлагается несколько методов поиска аспектных терминов. Качество оценивалось на корпусе из 468 предложений, извлечённых из материалов предвыборной агитации. Лучший результат для нейросетевых классификаторов был получен с использованием нейронной сети BERT-SPC, предобученной на задаче определения тональности по отношению к явно упоминаемому аспекту, макро-F-мера составила 0.74. Лучший результат для алгоритма, основанного на семантических правилах, был получен при использовании метода поиска аспектных терминов на основе семантической схожести, макро-F-мера составила 0.63. При объединении BERT-SPC и алгоритма, основанного на правилах, в ансамбль была получена макро-F-мера, равная 0.79, что является лучшим результатом, полученным в рамках работы.
В статье рассматриваются неориентированные кратные графы произвольной натуральной кратности k>1. Кратный граф содержит ребра трех типов: обычные, кратные и мультиребра. Ребра последних двух типов представляют собой объединение k связанных ребер, которые соединяют 2 или (k+1) вершину соответственно. Связанные ребра могут использоваться только согласованно. Если вершина инцидентна кратному ребру, то она может быть инцидентна другим кратным ребрам, а также она может быть общим концом k связанных ребер мультиребра. Если вершина является общим концом мультиребра, то она не может быть общим концом никакого другого мультиребра. Рассматривается задача об эйлеровом маршруте (цикле или цепи) в кратном графе, которая обобщает классическую задачу для обычного графа. Задача о кратном эйлеровом маршруте является NP-трудной. Обоснована полиномиальность двух подклассов задачи о кратном эйлеровом маршруте, разработаны полиномиальные алгоритмы. В первом подклассе задано ограничение на множества достижимости по обычным ребрам, которые представляют собой подмножества вершин, соединенных только обычными ребрами. Во втором подклассе задано ограничение на степень квазивершин в графе с квазивершинами. Структура этого обычного графа отражает структуру кратного графа, а каждая квазивершина определяется k индексами множеств достижимости по обычным ребрам, которые инцидентны какому-то мультиребру.
Приводятся оценки для минимальной нормы проектора при линейной интерполяции на компакте в Rn. Пусть Π1(Rn) - пространство многочленов от n переменных степени не выше 1, Ω - компакт в Rn, K=conv(E). Будем предполагать, что vol(K)>0. Пусть точки x(j)∈Ω, 1≤j≤n+1, являются вершинами n-мерного невырожденного симплекса. Интерполяционный проектор P:C(Ω)→Π1(Rn) с узлами x(j) определяется равенствами Pf(x(j))=f(x(j)). Под ∥P∥Ω будем понимать норму P как оператора из C(Ω) в C(Ω. Через θn(Ω) обозначим минимальную норму ∥P∥Ω из всех операторов P с узлами, принадлежащими Ω. Через simp(Ω) обозначим максимальный объём симплекса с вершинами в Ω. Устанавливаются неравенства χ−1n(vol(K)simp(Ω))≤θn(Ω)≤n+1. Здесь χn - стандартизованный многочлен Лежандра степени n. Нижняя оценка доказывается с применением полученной характеризации многочленов Лежандра через объёмы выпуклых многогранников. Именно, мы показываем, что при γ≥1 объём многогранника \left{x=(x_1,...,x_n)\in{\mathbb R}^n : \sum |x_j| +\left|1- \sum x_j\right|\le\gamma\right} равен χn(γ)/n!. В случае, когда Ω - n-мерный куб или n-мерный шар, нижняя оценка даёт возможность получить неравенства вида θn(Ω)⩾cn√. Формулируются некоторые открытые вопросы.Приводятся оценки для минимальной нормы проектора при линейной интерполяции на компакте в Rn. Пусть Π1(Rn) - пространство многочленов от n переменных степени не выше 1, Ω - компакт в Rn, K=conv(E). Будем предполагать, что vol(K)>0. Пусть точки x(j)∈Ω, 1≤j≤n+1, являются вершинами n-мерного невырожденного симплекса. Интерполяционный проектор P:C(Ω)→Π1(Rn) с узлами x(j) определяется равенствами Pf(x(j))=f(x(j)). Под ∥P∥Ω будем понимать норму P как оператора из C(Ω) в C(Ω. Через θn(Ω) обозначим минимальную норму ∥P∥Ω из всех операторов P с узлами, принадлежащими Ω. Через simp(Ω) обозначим максимальный объём симплекса с вершинами в Ω. Устанавливаются неравенства χ−1n(vol(K)simp(Ω))≤θn(Ω)≤n+1. Здесь χn - стандартизованный многочлен Лежандра степени n. Нижняя оценка доказывается с применением полученной характеризации многочленов Лежандра через объёмы выпуклых многогранников. Именно, мы показываем, что при γ≥1 объём многогранника \left{x=(x_1,...,x_n)\in{\mathbb R}^n : \sum |x_j| +\left|1- \sum x_j\right|\le\gamma\right} равен χn(γ)/n!. В случае, когда Ω - n-мерный куб или n-мерный шар, нижняя оценка даёт возможность получить неравенства вида θn(Ω)⩾cn√. Формулируются некоторые открытые вопросы.
В статье представлен метод семантического анализа данных посредством комплекснозначного матричного разложения. Метод основан на квантовой модели контекстно-чувствительных решений, согласно которой наблюдаемые вероятности порождаются кубитными состояниями, представляющими субъективный смысл контекстов для базисного решения. В простейшем трёхконтекстом случае один из кубитов раскладывается в суперпозицию оставшихся двух, математически представляющую смысловые отношения между контекстами. Для использования в задаче анализа данных эта модель представлена в матричной форме так, что строки и столбцы соответствуют контекстам и постановкам эксперимента. При этом наблюдаемые действительные данные порождаются матрицей комплекснозначных амплитуд, раскладываемой на произведение действительной матрицы базисных векторов и комплекснозначной матрицы коэффициентов суперпозиции. Это разложение выявляет устойчивые процессно-смысловые соотношения контекстов, не обнаруживаемые другими методами. В результате данные воспроизводятся более точно и с меньшим числом параметров, чем при использовании сингулярного и неотрицательного матричных разложений той же размерности. Модель успешно испытана в описательном и предсказательном режимах. Результат открывает возможности для разработки природоподобных вычислительных архитектур на новых логических принципах.
Статья продолжает цикл публикаций по разработке и верификации управляющих программ на основе LTL-спецификаций специального вида. Ранее для описания строго детерминированного поведения программ была предложена декларативная LTL-спецификация, проработаны способы её верификации и трансляции: для верификации используется инструмент проверки модели nuXmv, трансляция осуществляется в императивный язык программирования ST для программируемых логических контроллеров. При верификации декларативной LTL-спецификации поведения программ может возникнуть необходимость в моделировании поведения её окружения. В общем случае требуется обеспечить возможность построения замкнутых систем «программа-окружение». В настоящей работе для описания поведения окружения программ логического управления предложена LTL-спецификация ограниченно недетерминированного поведения булевой переменной. Данная спецификация позволяет задавать поведение булевых сигналов обратной связи, а также условия справедливости для исключения нереалистичных сценариев поведения. В статье предлагается подход к разработке и верификации программ логического управления, в рамках которого модель поведения окружения программы описывается в виде ограничений на поведение её входных сигналов, что позволяет избежать отдельного детального представления процессов функционирования окружения. В результате полученная модель поведения замкнутой системы «программа-окружение» даёт ряд преимуществ: упрощение процесса моделирования, сокращение пространства состояний проверяемой модели, снижение времени верификации. При невозможности сведения поведения окружения к поведению имеющихся входных сигналов данный подход предполагает применение «мнимых» датчиков - дополнительных булевых переменных, использующихся как вспомогательное средство для описания поведения входных сигналов. Цель введения мнимых датчиков состоит в компенсации недостающих датчиков для отслеживания специфического поведения отдельных элементов окружения, которое необходимо учесть при задании реалистичного поведения входов программы логического управления. Предложенный подход к разработке и верификации программ с учётом поведения окружения (объекта управления) демонстрируется на примере промышленной установки для литья пластмасс.
В работе сравнивается качество работы различных методов определения неявно упоминаемых аспектов социально-экономической жизни в публицистических предложениях на русском языке. Задача определения неявно упоминаемых аспектов является вспомогательной для задач аспектно-ориентированного анализа тональности. Эксперименты проводились на корпусе предложений, извлечённых из политической агитации. Лучшие результаты, с F1-мерой, достигающей 0.84, были получены с использованием эмбеддингов Navec и классификаторов, основанных на методе опорных векторов. Достаточно высокие результаты, с F1-мерой до 0.77, были получены при использовании модели «мешок слов» и наивного байесовского классификатора. Остальные методы показали более низкие результаты. Также в ходе экспериментов было выявлено, что качество определения различных аспектов может достаточно сильно отличаться. Лучше всего определяются аспекты, с которыми в речи связаны характерные слова-маркеры, например, «здравоохранение» и «проведение выборов» Хуже всего определяются упоминания достаточно общих аспектов, таких как «качество управления».
В работе представлены результаты исследования современных моделей текста с целью выявления на их основе семантической близости текстов на английском языке. Задача определения семантического сходства текстов является важной составляющей многих областей обработки естественного языка: машинного перевода, поиска информации, систем вопросов и ответов, искусственного интеллекта в образовании. Авторы решали задачу классификации близости ответов учащихся к эталонному ответу учителя. Для исследования были выбраны нейросетевые языковые модели BERT и GPT, ранее применявшиеся к определению семантического сходства текстов, новая нейросетевая модель Mamba, а так же стилометрические характеристики текста. Эксперименты проводились с двумя корпусами текстов: корпус Text Similarity из открытых источников и собственный корпус, собранный с помощью филологов. Качество решения задачи оценивалось точностью, полнотой и F-мерой. Все нейросетевые языковые модели показали близкое качество F-меры около 86% для большего по размеру корпуса Text Similarity и 50-56% для собственного корпуса авторов. Совсем новым результатом оказалось успешное применение модели mamba. Однако, самым интересным достижением стало применение векторов стилометрических характеристик текста, показавшее 80% F-меры для авторского корпуса и одинаковое с нейросетевыми моделями качество решения задачи для другого корпуса.
Безопасность движения на железнодорожном транспорте требует регулярной проверки состояния рельсов для отслеживания и своевременного устранения возникающих на них дефектов. Вихретоковая дефектоскопия - один из популярных методов проведения неразрушающего контроля рельсов. Данные (дефектограммы), поступающие от вихретоковых дефектоскопов при тестировании рельсов, характеризуются большим объёмом и нуждаются в эффективном автоматическом анализе. Под анализом понимается процесс определения по дефектограммам наличия дефектных участков наряду с выявлением конструктивных элементов рельсового пути с учётом шума и возможных помех разной природы. Для выделения полезных сигналов (от дефектов и конструктивных элементов) находится пороговый уровень шума, значение которого может быть искажено накладывающимися на сигналы электромагнитными помехами, обладающими выраженной низкочастотностью и периодичностью. Указанные помехи завышают пороговый уровень шума, осложняя выявление полезных сигналов. В связи с этим возникает необходимость в подавлении помех описанного типа. В данной работе в качестве метода устранения помех на вихретоковых дефектограммах используется спектральное вычитание. Функция помех определяется как сумма низкочастотных гармоник дискретного преобразования Фурье исходных сигналов. Очищенные от помех сигналы получаются вычитанием гармоник низкочастотного диапазона. Правая граница этого диапазона названа частотой пороговой гармоники. Она находится с помощью минимизации расстояния между автокорреляционной функцией сигналов и ожидаемой автокорреляцией. Предложены два вида ожидаемой автокорреляции: автокорреляция гауссовского шума и эталонная автокорреляция. Оба подхода позволяют определить частоту пороговой гармоники, при которой периодические помехи будут подавляться наилучшим образом. Метод, основанный на автокорреляции гауссовского шума, является в некотором роде универсальным для вихретоковых дефектограмм. Эталонная автокорреляция привязана к конкретным данным и пишущему оборудованию. Для рассматриваемых данных вихретоковых дефектограмм найдена наиболее подходящая частота пороговой гармоники. Описанные подходы к подавлению периодических низкочастотных помех помимо вихретоковой дефектоскопии могут успешно применяться и в других областях.
Разработка более точных и адаптивных методов обнаружения вредоносного кода является критической задачей в контексте постоянно эволюционирующих угроз кибербезопасности. Это требует постоянного внимания к новым уязвимостям и методам атак, а также поиска инновационных подходов к обнаружению и предотвращению киберугроз. В работе исследуется алгоритм обнаружения исполнения вредоносного кода в процессе защищаемой программы. Этот алгоритм основан на ранее предложенном подходе, когда легитимное исполнение защищаемой программы описывается профилем разностей адресов возврата вызываемых функций, называемым также профилем расстояний. Введено такое понятие, как позиционное расстояние, которое определяется разницей между номерами вызовов в трассе программы. Основным изменением стала возможность добавления в профиль расстояний между адресами возврата не только соседних функций, а также нескольких предыдущих с заданным позиционным расстоянием. Кроме модификации алгоритма обнаружения, в работе разработано средство автоматизации построения профиля расстояний и экспериментально исследуется зависимость вероятности ложного обнаружения нетипичного расстояния от длительности обучения для четырех известных браузеров. Эксперименты подтверждают, что при незначительном увеличении времени проверки число нетипичных расстояний, обнаруживаемых предложенным алгоритмом, может быть существенно меньше числа нетипичных расстояний, выявляемых базовым алгоритмом. Однако следует отметить, что при этом эффект перехода от базового алгоритма к предложенному, как показали результаты, зависит от характеристик конкретной защищаемой программы. Исследование подчеркивает важность постоянного совершенствования методов обнаружения вредоносного кода, чтобы адаптировать их к изменяющимся угрозам и условиям эксплуатации программного обеспечения. В итоге это позволит обеспечить более надежную защиту информации и систем от кибератак и других киберугроз.