Preview

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

Расширенный поиск
Том 27, № 3 (2015)
Скачать выпуск PDF
5-8 59
Аннотация
Этот выпуск «Трудов ИСП РАН» содержит избранные статьи, представленные на 9-ом коллоквиуме молодых ученых в области программной инженерии SYRCoSE 2015 (Spring/Summer Young Researchers’ Colloquium on Software Engineering). Мероприятие прошло 28-30 мая 2015 года в Самаре на базе Поволожского государственного университета телекоммуникаций и информатики (ПГУТИ). Организаторами выступили ИСП РАН, Санкт-Петербургский государственный университет и ПГУТИ.
9-28 101
Аннотация
В данной статье рассматриваются вопросы построения языкового сервиса для расширенной поддержки языка программирования Fortran в интегрированной среде разработки Microsoft Visual Studio. Предлагается модель и общий подход к построению языковых сервисов. Подробно рассматриваются вопросы организации данной модели, и доказательство её работоспособности на примере разработанного автором языкового сервиса FRIS. Изложенный материал может быть в равной мере использован для построения языковых сервисов, как для других языков программирования, так и для других средств разработки.
29-46 106
Аннотация
По сравнению с классами типов Haskell и концептами C++ такие объектно-ориентированные языки как C# и Java предоставляют значительно менее выразительные механизмы обобщённого программирования на основе F-ограниченного полиморфизма. В этой статье рассматриваются основные подводные камни обобщений C#. Для решения проблем обобщений предлагается расширение языка C# концептами, которые можно использовать одновременно с интерфейсами; очерчены дизайн и основные принципы трансляции концептов.
47-56 65
Аннотация
В работе представлен визуальный подход к параллельному программированию, реализованный в технологии графо-символического программирования. Рассмотрены основы этой технологии, а также преимущества и недостатки визуального параллельного программирования. Описано текущее состояние работ по реализации технологии графо-символического программирования в виде облачного PaaS-сервиса, предоставляющего средства для создания, анализа и выполнения параллельных программ для кластерных систем.
57-72 102
Аннотация
В рамках традиционной программной инженерии требования и код развиваются в двух параллельных мирах. Возможно ли объединить эти миры? Такое объединение упростило бы изменение и повторное использование программного обеспечения. Целесообразность применения нового подхода нуждается в изучении. В представленном исследовании рассмотрен классический пример из литературы в области проектирования требований. Для спецификации предметной области, равно как и конечного программного решения, использована одна и та же нотация - язык программирования. Данная работа содержит описание подхода, а также оценку его преимуществ, возможных ограничений и масштабируемости.
73-86 58
Аннотация
Рассматривается формальный метод, обеспечивающий поддержку критически важного шага в объектно-ориентированном анализе и проектировании программного обеспечения. Предложено формировать модель, описывающую структуру классов объектов, на основе онтологического анализа эмпирических данных о целевой предметной области проектирования. Эта технология является развитием известного метода анализа формальных понятий и способна работать с неполной (противоречивой, неточной, нечеткой и т.п.) эмпирической информацией о предметной области, органично поддерживает построение произвольных отношений между классами объектов и принимает во внимание имеющиеся у исследователя сведения о взаимосвязи актуальных для проектировщика свойств объектов предметной области. Для учета реалий накопления эмпирических данных используются модели и аппарат многозначной векторной логики. При этом для задачи вывода понятийной структуры предметной области формируется нестрогий формальный контекст. Его преобразование в бинарный формальный контекст, для которого известны эффективные алгоритмы вывода формальных понятий, производится с использованием интеллектуального алгоритма альфа-аппроксимации, учитывающего типичные зависимости между свойствами объектов и, прежде всего, концептуальную сопряженность свойств объектов, возникающую в результате фундаментальной познавательной процедуры проектировщика - концептуального шкалирования регистрируемых свойств объектов. Между выведенными из формального контекста понятиями фиксируется частичный порядок по вложению свойств, известный в объектно-ориентированном анализе как наследование свойств. Определяемая этим отношением замкнутая решетка формальных понятий трансформируется в модель, описывающую структуру классов объектов, в соответствии с рядом прагматических принципов проектирования этого ключевого компонента программного обеспечения.
87-100 60
Аннотация
Оптимизирующие компиляторы вносят существенный вклад в повышение производительности современных вычислительных систем. Наиболее чувствительными к качеству компиляции являются процессоры с VLIW архитектурой, поскольку в этом случае производительность обеспечивается за счет одновременного исполнения в одном такте нескольких статически спланированных команд, это приводит к усложнению VLIW компиляторов. Так, компилятор для семейства процессоров Эльбрус в режиме -O3 выполняет последовательно более 300 оптимизирующих фаз. Такое количество этапов необходимо для достижения требуемой производительности итогового кода, но является затратным по времени компиляции. Значительное увеличение времени компиляции при высокоуровневой оптимизации в первую очередь вызвано применением ряда агрессивных необратимых преобразований, приводящих к также нежелательному росту итогового кода. Кроме того, остается проблема использования некоторых полезных только для отдельных контекстов оптимизаций. Для одновременного учета требований повышения производительности, уменьшения времени компиляции и размера итогового кода имеет смысл выбрать подходящую оптимизирующую последовательность на раннем этапе компиляции в зависимости от специфических характеристик процедуры. В представленной статье обсуждается проблема классификации процедур для осуществления такого выбора и предлагается ряд способов ее решения.
101-114 83
Аннотация
В данной статье представлена унифицированная модель тестирования инструментов разработки объектно-ориентированных приложений. На основе имеющихся литературных источников были выделены недостатки имеющихся работ и определены следующие критерии оптимальности, которым должна соответствовать полученная модель: 1. Необходимо наличие глубоких иерархий наследования 2. Присутствие нескольких иерархий наследования 3. Наличие абстрактных классов в иерархии 4. Присутствие множественных n-арных ассоциаций 5. Наличие ассоциаций с атрибутами 6. Присутствие композиции между классами 7. Наличие рекурсивных ассоциаций 8. Наличие ассоциаций между классами, входящими в одну иерархию наследования 9. Присутствие класса-ассоциации 10. Наличие ассоциаций между классом-ассоциацией и другим классом 11. Присутствие в модели перечислений С помощью графического унифицированного языка UML была представлена диаграмма классов унифицированной модели тестирования. В работе проверено соответствие полученной реализации выделенным критериям. В настоящее время для реализации приложений используют объектно-ориентированные языки программирования и реляционные базы данных. Для преодоления объектно-реляционного несоответствия необходимо реализовать методы (паттерны) отображения. В статье описаны три метода, используемых для представления иерархии классов, выделены достоинства и недостатки каждого метода. Для проверки реализуемости унифицированной модели выбрана среда разработки SharpArchitect RAD Studio, в которой спроектировано объектное приложение на языке C# и реализована структура реляционной БД. В статье представлена разработанная объектная модель в виде диаграммы классов, на которой показано наследование интерфейсов и диаграмма отношений, содержащая все таблицы и столбцы полученной БД. В заключении даны рекомендации по направлениям дальнейшего развития работы, и определена необходимость реализовать унифицированную модель с помощью других подходов, предложенных авторами.
115-124 79
Аннотация
В данной работе описывается подход к конкретизации символических тестовых сценариев в рамках технологии верификации и тестирования программного обеспечения. Представлены инструменты автоматизации процесса конкретизации на основании пользовательских настроек.
125-138 66
Аннотация
В данной работе предложен метод генерации тестовых программ для функциональной верификации блока управления памятью микропроцессора. В основе метода лежат формальные спецификации инструкций доступа к памяти, а именно инструкций чтения и записи, и устройств памяти, таких как блоки кэш-памяти и буферы трансляции адресов. Использование формальных спецификаций помогает автоматизировать разработку генераторов тестовых программ и обеспечивает систематичность верификации благодаря четкому определению целей тестирования. В предложенном подходе тестовые программы составляются при помощи комбинаторных методов. Т.е. тестовые воздействия (последовательности инструкций чтения и записи) создаются путем перечисления всех возможных комбинаций инструкций, ситуаций (путей выполнения инструкций) и зависимостей (множеств конфликтов между инструкциями). Важно отметить, что тестовые ситуации и зависимости автоматически извлекаются из спецификаций. Данный подход применялся в нескольких промышленных проектах и позволил выявить критические ошибки в механизмах управления памятью.
139-148 73
Аннотация
В статье описан метод верификации подсистемы прямого доступа к памяти, примененный к семейству микропроцессоров «Эльбрус». Для сокращения накладных расходов на верификацию подсистемы разработан имитатор периферийных контроллеров. Модель имитатора контроллеров была включена в функциональный симулятор вычислительного комплекса. На основе функциональной модели был разработан генератор псевдослучайных тестов, предназначенных для верификации подсистемы прямого доступа к памяти.
149-160 58
Аннотация
В работе представлен метод построения тестовых оракулов для подсистем памяти многоядерных микропроцессоров. В методе используется недетерминированная эталонная модель тестируемой системы. Идея подхода состоит в динамическом уточнении поведения модели на основе реакций, полученных от системы. При возникновении недетерминированного выбора в эталонной модели создаются и запускаются дополнительные экземпляры модели, каждый из которых моделирует возможный вариант поведения. При получении реакции от тестируемой системы завершаются экземпляры модели, для которых данная реакция является некорректной. Признаком ошибки является отсутствие активных экземпляров эталонной модели. Предложенный метод использовался для верификации кэш-памяти третьего уровня микропроцессора «Эльбрус-8C»; с его помощью было найдено три ошибки.
161-182 106
Аннотация
Генерация тестов по моделям широко используется для функциональной верификации аппаратуры. Расширенные конечные автоматы (extended finite state machines, EFSM) - удобный формализм для моделирования цифровых устройств. В отличие от обычных конечных автоматов, в EFSM-моделях управляющие сигналы и данные разделены, что позволяет описывать системы в более компактной форме, уменьшая в некотором смысле риск комбинаторного взрыва при верификации. В данной статье представлен метод генерации тестов по EFSM-моделям и проведено его сравнение с другими подходами. Предлагаемый метод сочетает случайный обход графа состояний автомата и направленный поиск реализуемых путей. Первая из указанных фаз направлена на покрытие «простых» переходов, вторая - «сложных». При направленном поиске используется информация о зависимостях по данным и управлению между переходами автомата и задействуется символическое исполнение. Проведенные эксперименты показывают, что в сравнении с другими подходами метод обеспечивает лучшие показатели тестового покрытия более короткими тестами.
183-196 53
Аннотация
В работе приведен анализ существующих методов верификации протоколов когерентности кэш-памяти масштабируемых систем. На основании литературы изложен формальный метод параметризованной проверки свойств безопасности протоколов когерентности. Предложена архитектура системы верификации протоколов когерентности. Описано применение метода к верификации протокола German, построение и анализ соответствующей Promela-модели. Сформулированы направления по улучшению и автоматизации метода, необходимые для верификации микропроцессоров «Эльбрус».
197-218 68
Аннотация
Язык диаграмм последовательностей сообщений (MSC-диаграмм) является популярным сценарно-ориентированным языком спецификаций, который используется для описания взаимодействия компонент в распределенных системах. Однако методы и средства проверки корректности MSC-диаграмм недостаточно развиты. Эта статья описывает метод трансляции MSC-диаграмм в раскрашенные сети Петри (CPN). Метод используется для верификации свойств таких диаграмм. Рассматриваемое множество элементов диаграмм расширено элементами диаграмм взаимодействий стандарта UML и конструкциями композиционных MSC-диаграмм. Свойства результирующих CPN анализируются и верифицируются при помощи известной системы CPN Tools и верификатора CPN на основе системы SPIN. Применение данного метода продемонстрировано на примере.
219-236 92
Аннотация
Модели процессов и графы широко используются для моделирования и визуализации процессов в информационных системах. Модели используются для представления связей между объектами или событиями в рамках процесса. Следовательно, необходимы программы для создания и редактирования моделей. Данная работа описывает редактор моделей, который позволяет работать с классическими графами, сетями Петри, конечными автоматами и системами взаимодействующих конечных автоматов. Кроме этого программа позволяет выполнять симуляцию сетей Петри, импорт и экспорт моделей в различных форматах хранения. Модульная архитектура Carassius позволяет расширять его различными способами, например, добавляя новые формализмы и нотации. Предложены два алгоритма размещения сетей Петри и графов на плоскости, реализованные в Carassius. Представленное программное обеспечение предназначено для использования в образовательных и исследовательских целях. Поэтому, при проектировании и разработке особое внимание уделялось простоте использования и расширяемости.
237-254 92
Аннотация
В данной работе представлено приложение для проведения экспериментов в области Process mining и тестирования алгоритмов починки моделей. Подходы и методы Process mining предназначены для извлечения моделей бизнес процессов из логов событий, их анализа и усовершенствования. Починка модели процесса необходима в случаях недостаточного соответствия существующей модели логам событий реального процесса. В статье рассматривается реализация модульного подхода починки моделей. Несмотря на то, что статья нацелена на описание особенностей реализации инструмента, теоретические основы модульной починки моделей рассмотрены на уровне, достаточном для понимания подхода. Более того, рассмотрены сценарии использования инструмента и описаны способы его расширения. Приведен обзор других существующих решений для починки моделей, обсуждены их сильные и слабые стороны.
255-266 208
Аннотация
На сегодняшний день различным организациям приходится все чаще сталкиваться с моделированием своих бизнес-процессов для сокращения издержек и для обеспечения четкого понимания процессов, которые используются в организации. Но из-за изменения законодательства, внедрения инноваций и других факторов бизнес-процессы компании постоянно изменяются. В свою очередь системным и бизнес аналитикам, которые занимаются моделированием бизнес-процессов, нужен инструмент для сравнения моделей бизнес-процессов и определения их различий. Сложность решения данной проблемы объясняется недостатком инструментов, которые могут быть использованы для сравнения моделей бизнес-процессов. Также нет общепризнанного стандарта для моделирования. EPC, YAWL, BPEL, XPDL и BPMN только небольшая часть широко используемых нотаций, которые нашли признание среди разработчиков. Каждая нотация имеет свои преимущества и недостатки, но почти все из них описаны с помощью XML-схемы, которая определяет правила сериализации. В этой статье предложен общий подход к сравнению моделей бизнес-процессов, который опирается на XML представления моделей. Предложенный подход реализован в виде плагина для фреймворка ProM, который активно используется аналитиками и исследователями в рамках новой научной дисциплины process mining.
267-278 64
Аннотация
В данной работе описывается дальнейшая разработка системы защиты Sevigator, использующей аппаратную виртуализацию. Изначальное устройство Sevigator состоит в исполнении пользовательских приложений в отдельной виртуальной машине, у которой отсутствует сетевой интерфейс. Для доверенных приложений Sevigator перехватает системные вызовы, связанные с операциями с сетью, и перенаправляет их на обслуживание в выделенную виртуальную машину. Такое устройство позволяет системе Sevigator защищать сетевое взаимодействие от вредоносных приложений, включая злонамеренный код на самом высоком уровне привилегий в ядре ОС. Использование современных гипервизоров, построенных по микроядерной архитектуре, позволяет изменить архитектуру системы Sevigator. Такие гипервизоры по своей природе являются маленькой операционной системой, в которой большинство аппаратных операций и управление виртуальными машинами изолированно в процессы с низким уровнем приоритета. Компрометация таких процессов не приведет к компрометации всего гипервизора. В данной работе мы предоставляем экспериментальную архитектуру Sevigator-а, основанную на гипервизоре NOVA, в рамках которой системные вызовы доверенных приложений обрабатываются в отдельном процессе в гипервизоре, а не в отдельной виртуальной машине. Этот эксперимент показал 25% прирост производительности при уменьшении количества переключений контекстов
279-290 75
Аннотация
Работа содержит описание приватного сервиса с шифрованием и расшифрованием данных на стороне клиента. В статье описано прямое соединение - клиент к клиенту. Приведен алгоритм работы программы, описаны способы защиты от некоторых сетевых атак и эксперимент работы прототипа. Рассмотрены потенциальные опасности внешнего характера, которые могут повлиять на конфиденциальность передачи данных.
291-302 59
Аннотация
В работе рассмотрен новый подход к фильтрации сообщений на сайтах с использованием совмещенного классификатора. Уровень защиты пользовательских данных определен стандартами информационной безопасности для интернет-ресурсов, кроме того постоянно растет число спам-сообщений в интерактивных разделах сайтов. Предлагаемый подход, в отличие от распространенных решений для электронной почты, основан на совместном использовании методов Байеса и Фишера, что позволило разработать эффективное программное решение фильтрации спама. В работе рассмотрен подход к построению совмещенного классификатора, удовлетворяющего критериям оптимальности и обеспечивающего принятие решений при классификации сообщений на основе статистических методов.
303-314 94
Аннотация
Аннотация В работе представлена программа-дополнение к анализатору трафика Wireshark для расчета моментов случайной величины - интервала между пакетами входящего трафика. Приведено аналитическое решение для среднего времени ожидания для СМО типа Н2/М/1. Здесь Н2 - гиперэкспоненциальный закон распределения 2-го порядка интервалов времени входного потока. Конечный результат получен путем решения интегрального уравнения Линдли методом спектрального разложения. Показано, что в этом случае законы распределения интервалов между требованиями входного потока можно аппроксимировать на уровне их трех первых моментов. Совместное использование этих результатов позволяет полностью анализировать входящий трафик методами массового обслуживания.
315-328 86
Аннотация
Проводимое исследование направлено на повышение эффективности использования высоконагруженных информационных систем, развернутых в облачной системе. Для этого планируется разработать модели, описывающие основные особенности обслуживания потоков с учетом топологий системы, сетевых сервисов и существующих систем планирования задач, а также методы управления потоками данных между процессами вычислительных задач. В рамках данной статьи решается задача исследования облачной системы и оценка эффективности схем управления с учетом различных алгоритмов планирования. С этой целью разработаны: модель облачной системы, метрики эффективности и методика экспериментального исследования алгоритмов планирования и методов управления потоками данных. Модели определяют функционалы вычислительных узлов и связанных потоков между сервисами всей системы в целом. Методика экспериментального исследования предполагает оценку эффективности совместной работы виртуальных машин с учетом алгоритмов планирования и методов управления потоками данных по описанным метрикам. Предложенные в рамках данной статьи решения являются основой разработанного симулятора облачной системы.
329-342 81
Аннотация
При передаче данных от одного учреждения к другому возникает проблема персональной идентификации физических лиц, у которых частично или полностью не совпадают реквизиты. В работе представлены метод и реализующий его алгоритм нечеткого поиска, использующие модифицированную метрику Левенштейна. Разработанный алгоритм, спроектированный в виде процесса Data Mining, позволяет быстро определять людей, используя данные ранее проведенного поиска. Встроенная система приоритета реквизитов позволяет идентифицировать человека в таких случаях, как смена фамилии, имени, переезд, ошибки при ручном вводе данных, а также при частично отсутствующих реквизитах. Алгоритм реализован на языке PL-SQL в СУБД Oracle 11g.
343-350 54
Аннотация
В статье приводится обзор средств, используемых в объектной СУБД нового типа для повышения эффективности доступа к данным. Описываются особенности объектной СУБД DIM, основанные на использовании отношений классов объектов (как множеств объектов): наследования, включения, взаимодействия и истории и отношений объектов: наследования, внутреннего наследования, включения, внутреннего включения, взаимодействия и истории. Вводится описание предметной области при помощи объектно-динамической модели данных (OD-модели) и обосновывается полнота СУБД DIM для произвольной OD-модели. Описывается объектный язык запросов ODQL, позволяющий совместить сложность точного описания с простотой использования за счет введения двух уровней запросов. В целях выяснения наиболее эффективного способа обращения к СУБД DIM проводится исследование различных запросных технологий для этой среды, а также разрабатываются и реализуются механизмы для работы пользователей с ней. Для этого разрабатывается комплекс программных средств, необходимых для работы с СУБД DIM. Рассматривается разработка ПО «Генератор ODQL-запросов», который нужен для упрощения построения запросов к СУБД DIM без необходимости для пользователя в обязательном порядке знать синтаксис нового языка запросов. Рассматриваются пути решения проблемы конвертации данных из существующих СУБД в СУБД DIM.
351-364 139
Аннотация
Краудсорсинг успешно нашёл применение при создании и анализе данных в случаях, когда такие задачи могут быть представлены в виде человеко-машинных вычислительных систем. Данная работа посвящена разработке инструментария краудсорсинга, позволяющего запустить гибкую платформу, управляющую всем процессом краудсорсинга, включая такие его элементы, как назначение заданий, оценка труда участников, агрегация ответов. Предложенный подход реализован, проведённый эксперимент показывает положительные результаты.
365-378 89
Аннотация
В статье рассматривается архитектура и структурная схема дистанционной обучающей системы «3Ducation», а также назначение и возможности всех входящих в него программных компонентов, описываются ее основные возможности. Система «3Ducation» построена на двух принципах: игровом подходе и технологиях виртуальных миров. Технологии виртуальной реальности позволяют перенести процесс обучения внутрь трехмерного пространства и сделать обучающее пространство более интересным, а процесс обучения более увлекательным. Игровой подход, с помощью которого реализуются активные методы педагогической деятельности, позволяет вовлечь обучаемых в сам процесс обучения, постоянно поддерживать и даже увеличивать интерес к самостоятельному обучению.
379-390 54
Аннотация
В работе рассматривается метод оптимизации вычисления метрики схожести изображений с помощью вычислений общего назначения на графическом процессоре (GPGPU). Использование потоковых процессоров графических ускорителей и платформы CUDA позволяет добиться значительного прироста производительности по сравнению с расчетами на процессорах общего назначения при решении задач в области компьютерного зрения, в частности для определения схожести изображений. Приведены результаты исследования производительности GPGPU реализации расчетов значений метрики.
391-406 58
Аннотация
В данной статье рассмотрена проблема создания компьютерной музыки, происходящего без непосредственного влияния пользователя в процесс генерации. Приведен обзор существующих решений, описание их ключевых особенностей и моделирование функции композитора на современном персональном компьютере. Моделирование опусов на базе объединения музыкального ритма и мелодической линии позволяет создать компьютерную музыку с заданными композиционными параметрами. Использование нового подхода приводит к результатам, отличающимся от предшественников и предполагающим новую область для исследования и разработки в сфере искусства, творимого компьютером.


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


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