Preview

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

Расширенный поиск

Труды Института системного программирования РАН (Труды ИСП РАН) издаются Институтом в традиционной бумажной форме с 2000 г. (с ISBN). До 2010 г. у издания отсутствовал строгий график выхода очередных выпусков, но обычно каждый год публиковались 1-2 новых "регулярных" тома, а иногда и специальные тематические тома.

С 2010 г. Труды ИСП РАН также публикуются на данном сайте в виде периодического электронного издания с одновременной публикацией небольшим тиражом в бумажной форме (ISSN 2220-6426 (Online), ISSN 2079-8156 (Print)). До начала 2014 г. ежегодно издавались два регулярных тома; по решению редакционной коллегии допускалось издание дополнительных тематических томов. С 2014 г. Труды ИСП РАН издаются в более традиционной форме: один том в год, по шесть выпусков (номеров) в каждом томе.

Это издание зарегистрировано в Федеральном агентстве по печати и массовым коммуникациям как средство массовой информации – научное электронное периодическое издание (регистрационное свидетельство Эл № ФС77-42228), а также в НТЦ "ИНФОРМРЕГИСТР" Федерального агентства по информационным технологиям как электронное научное издание (номер государственной регистрации 0421100143). Издание включено в Перечень ВАК российских рецензируемых научных журналов, в которых должны быть опубликованы основные научные результаты диссертаций на соискание ученых степеней доктора и кандидата наук (позиция в списке 1952).

Текущий выпуск

Том 32, № 2 (2020)
7-14 55
Аннотация
В работе представляются модификации модели векторов fastText, основанные исключительно на н-граммах, для морфологического анализа текстов. fastText - библиотека для классификации текстов и обучения векторных представлений. Представление каждого слова вычисляется как сумма его отдельного вектора и векторов его символьных н-грамм. fastText хранит и использует отдельный вектор для целого слова, но во внесловарных случаях такой вектор отсутствует, что приводит к ухудшению качества получаемого вектора слова. Кроме того, в результате хранения векторов для целых слов, модели fastText обычно требуют много памяти для хранения и обработки Это становится особенно проблематично для морфологически богатых языков, учитывая многочисленность словоформ. В отличие от исходной модели fastText, предлагаемые варианты используют только информацию об н-граммах слова, избавляя от зависимости от векторов на уровне слов и в то же время помогая значительно сократить количество параметров в модели. Предлагается два способа извлечения информации из слова: внутренние символьные н-граммы и суффиксы. Модели тестируются на корпусе СинТагРус в задаче морфологической разметки и лемматизации русского языка, и показывают результаты, сравнимые с исходной моделью fastText.
15-28 28
Аннотация

Требования к программному обеспечению достаточно трудно объективно измерить по критериям качества без вовлечения в процесс оценки непосредственно самих заинтересованных сторон. Оценка качества документов спецификации требований в автоматическом режиме может существенно сократить расходы бюджета проекта и также предотвращает появление скрытых дефектов в программном обеспечении на более поздних этапах разработки. Качество требований может быть оценено, основываясь на широком разнообразии атрибутов качества, но значение каждого такого атрибута достаточно расплывчато и не имеет строгой привязки к какой-либо измеримой метрике. Использование метода GQM (Goal-Question-Metric) в процессе построения модели оценки может помочь выявить наиболее важные критерии качества и установить связь между атрибутами и конкретными метриками, которые могут быть собраны и вычислены автоматически. Текст требований к программному обеспечению, написанный на естественном языке, может быть проанализирован при помощи инструментов NLP (Natural Language Processing) с целью выявления наиболее слабых слов и фраз, которые делают предложения неоднозначными и двусмысленными. Метрики для таких критериев качества как неоднозначность, единственность, субъективность, полнота и удобочитаемость предложены в данной работе. Описанная модель оценки качества была реализована при помощи сторонних инструментов с открытым исходным кодом для требований, написанных на русском языке. 

29-36 26
Аннотация

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

37-51 28
Аннотация

Повсеместное использование облачных технологий позволяет оптимизировать экономические издержки на содержание ИТ-инфраструктуры предприятий, но при этом увеличивает вероятность кражи конфиденциальных данных. Одним из механизмов для защиты данных от кражи является криптография. Использование классических примитивов симметричного и ассиметричного шифрования не позволяет обрабатывать данные в зашифрованном виде. Для обработки конфиденциальных данных используют гомоморфное шифрование. Гомоморфное шифрование позволяет производить арифметические действия с зашифрованным текстом и получать зашифрованный результат, который соответствует результату операций, выполненных с открытым текстом. Одним из перспективных направлений для построения гомоморфных шифров является гомоморфные шифры, основанные на обучении с ошибками. В статье мы исследуем криптографические свойства существующих гомоморфных шифров (CKKS, BFV) на основе обучения с ошибками, сравниваем их технические характеристики: криптостойкость и избыточность данных, скорость кодирования и декодирования данных, скорость выполнения арифметических операций сложения и умножения данных, скорость выполнения операции KeySwitching.

53-60 18
Аннотация

Система прерываний является важной частью микропроцессоров. Прерывания широко используются для взаимодействия с оборудованием и реагирования на сигналы. Современные микропроцессорные системы прерываний включают аппаратную поддержку виртуализации. Аппаратная поддержка помогает повысить производительность виртуальных машин. Однако добавление дополнительной функциональности может привести к появлению потенциальных ошибок. В статье представлен обзор подходов, используемых для систем прерывания в многоядерных микропроцессорах с аппаратной поддержкой виртуализации. Описаны некоторые определения и характеристики систем прерываний, которые необходимо учитывать в процессе проверки. Представлена общая схема автономной среды верификации. Universal Verification Methodology была применена для построения тестовой системы. Для упрощения разработки модуля проверки использовалась эталонная модель с учетом временных характеристик. Последовательности первичных запросов и автоматически генерируемые вторичные запросы в специальных модулях авто генерации использовались для рандомизации поведения тестовой системы. Были описаны некоторые трудности, обнаруженные в процессе верификации, а также соответствующие методы их решения. Представлены обобщенные этапы алгоритма тестирования. Были рассмотрены некоторые другие методы проверки корректности работы системы прерываний. В заключение приведены примеры применения предложенных подходов для верификации системы прерываний микропроцессоров с архитектурой Эльбрус и «SPARC-V9», разработанной АО МЦСТ. Представлены результаты и дальнейший план развития тестовой системы.

61-80 20
Аннотация

Производительность современных микропроцессоров существенно зависит от устройства их подсистемы памяти. Таким образом, программная модель подсистемы памяти является ключевым компонентом потактово-точных симуляторов, и качество этой модели в значительной степени определяет итоговую точность моделирования всего микропроцессора. Данная статья посвящена потактово-точному симулятору уровня приложений, специализированного на моделировании микропроцессоров архитектуры «Эльбрус». В статье дано описание общей структуры рассматриваемого потактово-точного симулятора. Вслед за этим описаны программная модель подсистемы памяти и особенности ее интеграции как части потактово-точного симулятора. Далее изложены результаты оценки точности разработанного потактово-точного симулятора на наборе тестов SPEC CPU2006 и проведен анализ ошибок моделирования. Завершает статью сравнение производительности симуляторов микропроцессоров «Эльбрус» различных типов.

81-98 22
Аннотация

Система команд – это стержень, вокруг которого строится весь остальной процессор. Ошибки или негибкость в решениях, однажды заложенные в систему команд, остаются с этим поколением процессоров навсегда. Поэтому одна из ключевых причин, по которой рост производительности современных CPU замедлился, заключается в том, что исходный код процессоров «испортился» в прямом и переносном смысле этого слова: процессоры внутри становятся сложными, из-за чего их дальнейшее развитие затрудняется. Разработка современных ЭВМ (CPU, GPU или специализированных систем) – это крайне дорогостоящий процесс, состоящий из большого количества затратных статей. Поэтому вопрос цены, или, скорее, целесообразности разработки процессора является ключевым. В данной работе мы провели исследование существующих популярных систем команд процессора и сделали выводы о перспективности в настоящее время направления RISC-V и других открытых систем команд CPU. Мы постарались ответить на следующие вопросы: почему система команд процессора – это действительно важно? Почему именно RISC-V, чем он лучше остальных? Какие возможности RISC-V открывает для российских разработчиков и какие у него есть аналоги?

99-106 21
Аннотация

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

107-124 30
Аннотация

При дедуктивной верификации Си-программ как с помощью различных платформ верификации (Why3, Frama-C/WP, F*), так и с помощью систем интерактивного доказательства теорем (Isabelle, HOL4, Coq) достаточно широко используются SMT-решатели. Их разрешающие алгоритмы полны для некоторых комбинаций логических теорий (логик), в частности для логики QF_UFLIA. В то же время при верификации Си-программ часто необходимо оперировать формулами в других разрешимых логиках, поддерживаемых не всеми SMT-решателями. Типичными примерами таких логик могут служить комбинации QF_UFLIA c теориями ограниченных целых как с переполнением (для беззнаковых целых в Си), так и без переполнения (для знаковых целых), а также теорией конечных интерпретируемых множеств (для поддержки рамочных условий) и др. Одним из возможных способов поддержки таких логик является их непосредственная реализация в SMT-решателях, однако этот способ часто является трудоемким, а также недостаточно гибким и универсальным. Другим способом является реализация пользовательских стратегий инстанцирования кванторов для сведения формул в неподдерживаемых логиках к формулам в широко распространенных разрешимых логиках, таких как QF_UFLIA. В данной статье представлена процедура инстанцирования лемм для трансляции формул в теории ограниченных целых без переполнения в логику QF_UFLIA. Для процедуры трансляции даны доказательства корректности и полноты, а также описана формализация этих доказательств в системе Isabelle/HOL. Аналогичный подход можно использовать для формулирования и доказательства полноты процедур трансляции формул в других теориях, таких как теория ограниченных целых с переполнением и теория ограниченной адресной арифметики.

125-134 19
Аннотация

Модели с конечным числом состояний широко используются при решении задач анализа и синтеза дискретных систем, и минимизация конечных автоматов является известной проблемой оптимизации, которая позволяет уменьшить количество состояний конечного автомата, описывающего поведение дискретной системы, на основе использования его приведенной формы. Такая форма единственна с точностью до изоморфизма для классических конечных автоматов, что, в частности, является основой для соответствующих методов синтеза тестов с гарантированной полнотой относительно «черного ящика», таких как W-метод и его модификации. Поскольку поведение современного программного и аппаратного обеспечения зачастую зависит от временных аспектов, в настоящее время классические автоматы расширяются временной переменной и связанными с ней входными и выходными таймаутами. Существующие подходы к минимизации временных автоматов охватывают оптимизацию как состояний, так и временных аспектов, и позволяют получить единственную минимальную форму для неинициальных детерминированных временных автоматов. В то же время для инициальных временных автоматов, т.е. автоматов с выделенным начальным состоянием, могут существовать различные попарно неизоморфные минимальные формы. В настоящей работе мы определяем классы инициальных временных автоматов, для которых минимальная форма единственна с точностью до изоморфизма.

135-148 32
Аннотация

Теория формальных языков активно изучается и находит широкое применение во многих областях. Например, в биоинформатике в задачах распознавания и классификации иногда требуется найти подпоследовательности генетических цепочек, обладающие некоторыми характерными чертами, которые могут быть описаны с помощью грамматики. Задача поиска этих подпоследовательностей сводится к проверке их принадлежности некоторому формальному языку, заданному грамматикой.  При этом часто требуется эффективная обработка больших объёмов данных, что приводит к необходимости усовершенствования существующих методов синтаксического анализа. На данный момент среди алгоритмов синтаксического анализа, работающих с произвольной КС-грамматикой, одним из самых быстрых является алгоритм Валианта, основанный на использовании матричных операций. В данной работе предложен алгоритм, который является модификацией алгоритма Валианта. Его основным достоинством является возможность разбиения матрицы разбора на подслои непересекающихся подматриц, которые могут быть обработаны независимо. Доказана корректность и приведена оценка сложности предложенного алгоритма. Проведенные эксперименты показывают, что он сохранил основные преимущества исходного алгоритма, главное из которых – высокая производительность, полученная за счет использования эффективных методов перемножения матриц. Также предложенный алгоритм позволил заметно уменьшить время, затрачиваемое на поиск подстрок, сократив большое количество избыточных вычислений.

149-160 46
Аннотация

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

161-173 38
Аннотация

Рандомизированное тестирование приложений (фаззинг, фаззинг-тестирование) является одним из широко используемых методов поиска ошибок. Цель фаззинг-тестирования – определить стабильность приложений при обработке псевдослучайно сгенерированных входных данных. В ходе тестирования приложение запускается на множестве произвольных входных данных, которые могут быть недействительными/неожиданными. Современное программное обеспечение часто предоставляет программный интерфейс (Application programming interface) для расширения возможностей программы. Это еще больше усложняет тестирование программного обеспечения, поскольку становится необходимым учитывать все возможные сценарии использования предоставленных интерфейсных функций. Применение фаззинга для генерации разных сценариев использования программного интерфейса приложения и соответствующих входных данных позволяет эффективным образом выявить ошибки в реализации функций программного интерфейса. В данной статье описывается новый метод фаззинг-тестирования для Android приложений и библиотек, написанных на языке Java. Разработанный инструмент фаззинг-тестирования выявил 15 уникальных дефектов, приводящих к аварийному завершению приложения SmartThings, разработанного компанией Samsung.

175-190 24
Аннотация

Авиационная отрасль в Российской Федерации сталкивается с трудностями организации инструментальной поддержки процессов разработки. Активный курс государства в сторону цифровизации экономики не способствует решению данной проблемы. Выбор инструмента является важным критерием успешной разработки сложного сертифицируемого ПО - бортовых авиационных систем. Подобная ситуация наблюдается и в других отраслях промышленности. В настоящее время на российском ИТ-рынке представлено достаточное количество программного обеспечения, способного в различной степени покрыть те или иные процессы жизненного цикла разработки сложного сертифицируемого программного обеспечения в сфере авионики. В рамках данной статьи анализируется текущая ситуация на российском рынке программного обеспечения и влияние политики импортозамещения Российской Федерации на разработчиков программного обеспечения и его потребителей - промышленных предприятий. Детали нормативного документа КТ-178С для разработки бортового программного обеспечения показывают важность выбора инструментальной среды проекта. Авторы определили основные группы функциональных возможностей инструментов, которые обеспечивают поддержку жизненного цикла разработки бортового программного обеспечения. Российские и зарубежные PLM (Product Lifecycle Management) и PDM (Product Data Management) системы, а также другое программное обеспечение были проверены на соответствие необходимой функциональности. Для сравнительного анализа был предложен метод, основанный на аддитивной верификации программного обеспечения по заданным критериям. Результаты исследований позволили авторам сделать вывод о современном уровне российского программного обеспечения в сравнении с зарубежными аналогами. На основании результатов анализа получили обоснование перспективы дальнейшей эволюции российского программного обеспечения. Также результаты анализа позволили сформулировать  рекомендации по направлениям разработки и доработки программного обеспечения и систем. Анализ, представленный в статье, может быть полезен для предприятий авионики и других отраслей, перед которыми стоят задачи выбора программного обеспечения для поддержки процессов жизненного цикла разработки в новых и текущих проектах разработки сложных систем. Также данные о продуктах и выводы могут быть полезны специалистам, интересующимся текущим состоянием российской ИТ-индустрии.



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