Preview

Труды Института системного программирования РАН

Расширенный поиск
Том 33, № 4 (2021)
Скачать выпуск PDF
7-18 58
Аннотация

Унифицированный язык моделирования (UML) является широко используемым стандартом для визуализации моделей в отрасли программного обеспечения. Следовательно, подготовка ИТ-специалистов включает в себя обучение моделированию. Исследования восприятия студентами UML-моделирования показывают, что обучение проходит довольно непросто. В данной статье представлено программное обеспечение для проверки диаграмм активности, классов и прецедентов по их представлению в формате XMI. Для достижения этой цели мы исследовали существующие методы и системы. Кроме того, мы проанализировали каталоги ошибок и модели студентов Пермского государственного университета, чтобы предложить классификацию ошибок и контрольный список, который представляет список необходимых проверок. В данной статье основное внимание уделяется проверке каждого типа диаграмм независимо друг от друга, без сохранения согласованности между различными моделями UML. Однако все эти модули проверки объединены в одну систему, которая позволяет проверить любой из исследованных типов диаграмм.

19-30 64
Аннотация

Среды разработки с низким кодом привлекают внимание из-за их потенциала в качестве парадигмы разработки для очень крупномасштабного внедрения в ИТ будущего. В этой статье мы предлагаем метод расширения (приложений) предметно-ориентированных языков, поддерживаемых двумя средами разработки с низким уровнем кода, основанными на формальных моделях, а именно DIME (родная Java) и Pyro (родной Python), для включения функций, размещенных на гетерогенных технологиях и платформы. Для этого мы следуем аналогии с микросервисами. После этой интеграции обе среды могут использовать связь с уже существующими удаленными службами RESTful и корпоративных систем, в нашем случае Amazon Web Services (AWS) (но это можно легко распространить на другие облачные платформы). Таким образом, разработчики могут использовать в DIME и Pyro потенциал сложных сервисов, потенциально всей экосистемы Python и AWS, в виде библиотек перетаскиваемых компонентов в управляемом ими стиле с низким кодом. Новые DSL доступны в DIME и Pyro как коллекции реализованных SIB и блоков. Из-за особых возможностей и проверок, лежащих в основе платформ DIME и Pyro, отдельные функции DSL автоматически проверяются на семантические и синтаксические ошибки в обеих средах.

31-48 112
Аннотация

В статье рассматривается задача классификации сетевого трафика на три типа, в зависимости от представления данных в нём: прозрачный, сжатый и шифрованный. Описываются существующие методы классификации, служащие для разделения трафика на прозрачный и непрозрачный, сжатый и шифрованный применительно к сетевым данным и документам. На основе них выбираются методы, показавшие лучшие результаты, и производится отбор лучшей их комбинации и вывод единого результата с применением методов машинного обучения (случайный лес). Также исследуется вопрос классификации потоков как единого целого и предлагается новый, отличный от существующих способ. Завершается статья анализом направлений для дальнейших исследований.

49-68 81
Аннотация

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

69-76 45
Аннотация

В данной работе рассматривается архитектура программируемого сетевого процессорного устройства (СПУ), основанного на специализированных вычислительных ядрах. В настоящее время в программно конфигурируемых сетях развиваются алгоритмы обработки пакетов с хранением состояния. Особенностью алгоритмов данного типа является перенос части управляющих функций из плоскости управления в плоскость передачи данных. Но для работы алгоритмов обработки пакетов с хранением состояния требуется поддержка со стороны СПУ. В работе предложены модификации архитектуры СПУ, позволяющие использовать алгоритмы обработки пакетов с хранением состояния и синхронизировать состояние алгоритма обработки пакетов между портами СПУ. Проведено экспериментальное исследование модифицированной архитектуры СПУ.

77-86 43
Аннотация

Данная статья посвящена проблемам классификации пакетов в архитектуре сетевого процессорного устройства (СПУ) без выделенного ассоциативного устройства. Под классификацией мы понимаем процесс идентификации пакета по его заголовку. На этапе классификации требуется реализация структур данных для хранения таблиц потоков. В данной работе рассматривается СПУ без адресуемой памяти, а таблицы потоков представляются в виде программы на языке ассемблера СПУ. Для перевода таблиц потоков в программу на языке ассемблера используется транслятор таблиц потоков. Необходимость реализации алгоритмов сжатия данных в трансляторе таблиц потоков обуславливается тем, что современные таблицы потоков могут занимать память объёмом до десятков мегабайт. В настоящей статье рассматриваются следующие алгоритмы сжатия данных: алгоритм оптимального кэширования, рекурсивного отсечения и общие алгоритмы сжатия данных. Оценка реализованных алгоритмов сжатия данных проводилась на имитационной модели СПУ.

87-98 72
Аннотация

Запись и расшифровка электрокардиограммы в 12 отведениях является наиболее распространенной процедурой для определения сердечных заболеваний. В последнее время предлагаются различные методы машинного обучения для автоматической постановки диагноза по электрокардиограмме. Их задача – предоставить второе мнение для врача и помочь обнаружить патологию на ранней стадии. В статье рассматриваются методы улучшения качества автоматического определения патологий по ЭКГ: добавление метаданных пациента, уменьшение шума электрокардиограммы и самоадаптивное обучение. Также представлены результаты экспериментального исследования влияние различных ЭКГ отведений, значимости длины электрокардиограммы и объема обучающей выборки на результаты работы алгоритмов. Проведенные эксперименты показывают релевантность описываемых подходов, а также предлагают оптимальную оценку параметров входных данных.

99-116 59
Аннотация

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

117-130 67
Аннотация

Морфологический анализ текстов на естественном языке является одним из важнейших этапов автоматической обработки текстов (АОТ). Традиционные и хорошо исследованные задачи морфологического анализа включают приведение словоформы к нормальной форме (лемме), определение ее морфологических характеристик, а также разрешение (снятие) морфологической омонимии (неоднозначности характеристик).  К морфологическому анализу относится также задача морфемного разбора слов (т.е. сегментация слов на составляющие морфы и их классификация), которая востребована в некоторых приложениях АОТ. В последние годы разработан ряд программных моделей на основе машинного обучения, повышающих точность традиционного морфологического анализа и морфемного разбора, однако производительность таких моделей недостаточна для многих практических задач, а для задачи морфемного разбора высокоточные модели построены только для лемм. В данной работе описаны две новые высокоточные нейросетевые модели, реализующие морфемный разбор словоформ русского языка при достаточно высокой производительности. Первая модель основана на сверточной нейронной сети и показывает достойное качество морфемного разбора словоформ. Вторая модель, кроме морфемного разбора словоформы, позволяет предварительно уточнить её морфологические характеристики, решая задачу снятия омонимии. Производительность этой объединенной морфологической модели оказалась наилучшей среди рассмотренных моделей морфемного разбора, при сравнимой точности разбора.   

131-146 62
Аннотация

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

 

147-162 80
Аннотация

Утечка значительной части электронных документов происходит путем фотографирования экрана. Для расследования таких случаев применяются технологии data leakage prevention (DLP), в частности, внедрение цифровых водяных знаков (ЦВЗ) в изображение на экране. В статье представлен краткий обзор существующих методов внедрения ЦВЗ. Предложен подход к маркированию изображений текстовых документов, выведенных на экран. Цифровая метка внедряется в межстрочные интервалы текста путем незначительного изменения яркости. ЦВЗ неразличим для восприятия человеком, но может быть запечатлен на цифровую камеру. Разработан алгоритм извлечения цифровой метки из фотографии экрана. Алгоритм не требует изображение исходного документа для успешного извлечения ЦВЗ. Результаты тестирования показали, что цифровая метка устойчива к преобразованиям (атакам), возникающим в ходе фотографирования экрана. Предложен метод, позволяющий оценить корректность извлечения цифровой метки при отсутствии информации о встроенной цифровой метке.

163-176 87
Аннотация

Визуальное моделирование на данный момент широко распространено, однако существующие платформы, предназначенные для моделирования, не могут удовлетворить все требования пользователей. Визуальные языки, как правило, основаны на графовых моделях, однако графовые формализмы, используемые для представления моделей, обладают существенными ограничениями. Для решения проблемы недостаточной выразительности существующих графовых моделей ранее была представлена новая графовая модель (HP-граф), основным элементом которой является множество полюсов, подмножества которых объединены в вершины и гиперребра. Многие операции над визуальными моделями, включая трансформацию моделей, сталкиваются с проблемой поиска изоморфного подграфа, что оказывает значительное влияние на скорость их выполнения. Многослойная структура HP-графа позволяет снизить временную сложность алгоритмов поиска. Количество операций может быть снижено благодаря тому, что поиск изначально осуществляется на слое вершин и гиперребер, и только в случае нахождения подграфа с желаемыми характеристиками алгоритм переходит на более детальный уровень, где сравниваются наборы соответствующих полюсов и обыкновенных связей отобранных подграфов. Представлено описание идеи многослойного подхода. Предложен алгоритм поиска с возвратом, основанный на этом подходе. Алгоритмы Ульмана и VF2 адаптированы к данному подходу, выполнена оценка их временной сложности. Предложенный подход постепенно сокращает область поиска алгоритмов и помогает уменьшить их общую сложность. В статье доказывается, что существующие алгоритмы сопоставления подграфов, за исключением тех, которые изменяют шаблон графа, могут быть успешно адаптированы к предлагаемому подходу.

177-194 43
Аннотация

Процесс разработки кода на Си довольно часто сопровождается появлением ошибок, связанных с использованием указателей и адресов памяти. В связи с этим возникает потребность создания инструментов автоматизированной проверки программ. Одним из методов, применяемых такими инструментами проверки, является использование решающих процедур на основе SMT-решателей. Но в то же время разрешимые логики (комбинации логических теорий), требуемые для адекватного моделирования указателей в языке Си, непосредственно не присутствуют в стандарте SMT-LIB и не реализованы в большинстве существующих SMT-решателей. Одним из возможных способов поддержки таких логик является непосредственная их реализация в каком-либо SMT-решателе, однако такой подход часто оказывается трудоемким (требуется изменение исходного кода решателя), негибким (трудно модифицировать сигнатуру и семантику новых теорий) и ограниченным (требуется отдельная реализация поддержки теории в каждом используемом решателе). Другим способом является реализация пользовательских стратегий конечного инстанцирования кванторов для сведения формул в неподдерживаемых логиках к формулам в широко распространенных разрешимых логиках, таких как QF_UFLIA. В данной статье представлена процедура инстанцирования лемм для трансляции формул в теории типизированной адресной арифметики в логику QF_UFLIA. Для процедуры трансляции даны доказательства корректности и полноты, а также описана формализация этих доказательств в системе Isabelle/HOL. Сама теория адресной арифметики сформулирована на основе известных ошибок использования адресной арифметики в языке Си, а также спецификаций семантики этих операций из стандарта языка. Аналогичные доказательства и процедура также могут быть сформулированы для фрагмента теории бит-векторов (монотонные формулы над равенствами между выражениями с побитовыми операциями, такими как исключающее “или”, сдвиг, конкатенация, экстракция, отрицание). Представленная в статье процедура трансляции, в частности, позволяет легко реализовать полный метод доказательства утверждений в теории адресной арифметики в системе Isabelle/HOL на основе существующей в этой системе поддержки SMT-решателей (Z3 или VeriT).

195-210 68
Аннотация

С развитием оптимизирующих компиляторов стали возникать случаи появления уязвимостей в программах во время оптимизации. Это связано с тем, что зачастую программисты используют конструкции с неопределенным поведением, опираясь на свое представление о том, в какой код такие конструкции транслировались знакомым им компилятором для определенной архитектуры. В то же время компилятор, руководствующийся стандартом языка, вправе проводить оптимизации так, как будто бы таких конструкций в коде не может существовать. В этой статье описываются подходы к обнаружению и устранению уязвимостей в программах, рассматривается применимость этих подходов для случая уязвимостей, появляющихся вследствие оптимизации, в условиях, когда возможность изменения исходного кода ограничена или отсутствует. В статье предлагается концепция безопасного компилятора, т.е. компилятора, обеспечивающего отсутствие внесения уязвимостей в программу во время оптимизации, и описывается реализация такого компилятора на базе компилятора GCC. Для безопасного компилятора приводится разделение реализованного функционала на три уровня защиты и описание применимости этих уровней, показывается применимость безопасного компилятора на практике, а также оценивается изменение производительности получаемой программы.

211-226 52
Аннотация

Цифровизация общества приводит к созданию большого количества распределенных автоматизированных информационных систем в различных областях современной жизни. Необходимость отвечать требованиям безопасности и надежности подталкивает к созданию инструментов их автоматизированного тестирования. Фаззинг-тестирование в рамках цикла безопасной разработки является необходимым инструментом решения указанной задачи, но не менее востребованы средства фаззинга бинарного кода, обеспечивающие поиск критических дефектов в уже функционирующих системах. Особенно остро этот вопрос стоит при исследовании безопасности проприетарных систем, функционирующих с использованием закрытых протоколов. В ходе проводимых исследований было выявлено, что для тестирования сетевых приложений в условиях отсутствия исходных текстов применение универсальных фаззеров затруднительно. Эти обстоятельства подталкивают к созданию простого в эксплуатации инструмента фаззинг-тестирования сетевых программ. В работе рассматриваются особенности фаззинг-тестирования такого рода программ и предлагаются возможные пути решения выявленных проблем.

227-240 34
Аннотация

В работе проводится калибровка k − ε модели турбулентности для потоков со свободной поверхностью в русле и на склоне. Для калибровки модели проводится эксперимент в наклонном лотке постоянного уклона прямоугольного сечения. В эксперименте с помощью трубки Пито измеряются значения давления в потоке на различном расстоянии от дна, с помощью которых так же получается профиль скорости потока. На основании данных эксперимента с использованием алгоритма оптимизации Нелдера-Мида производится калибровка k − ε модели турбулентности. Откалиброванная модель турбулентности далее применяется для расчёта прорыва ледникового озера, вблизи ледника Малый Азау.



Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)