• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Найдены 134 публикации
Сортировка:
по названию
по году
Статья
Твардовский A., Евтушенко Н. В., Громов М. Труды Института системного программирования РАН. 2017. Т. 29. № 4. С. 139-154.

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

Добавлено: 9 ноября 2017
Статья
Захаров В. А. Труды Института системного программирования РАН. 2015. Т. 27. № 2. С. 221-250.

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

Добавлено: 30 сентября 2015
Статья
Зеленов С. В., Зеленова С. Труды Института системного программирования РАН. 2017. Т. 29. № 5. С. 257-282.

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

Добавлено: 12 февраля 2018
Статья
Гетьман А. И., Маркин Ю. В., Иванников В. П. и др. Труды Института системного программирования РАН. 2015. Т. 27. № 4. С. 5-22.

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

Добавлено: 5 сентября 2019
Статья
Гетьман А. И., Маркин Ю. В., Обыденков Д. О. и др. Труды Института системного программирования РАН. 2017. Т. 29. № 3. С. 117-150.

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

Добавлено: 5 сентября 2019
Статья
Татарников А. Д. Труды Института системного программирования РАН. 2017. Т. 29. № 1. С. 167-194.

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

Добавлено: 8 ноября 2017
Статья
Мендкович Н. А., Кузнецов С. Д. Труды Института системного программирования РАН. 2012. Т. 23. С. 195-214.

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

Добавлено: 1 ноября 2017
Статья
Казаков К., Семенов В. А. Труды Института системного программирования РАН. 2016. Т. 28. № 4. С. 241-294.

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

Добавлено: 12 декабря 2018
Статья
Петренко А. К., Кулямин В. В., Хорошилов А. В. Труды Института системного программирования РАН. 2015. Т. 27. № 5. С. 175-190.

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

Добавлено: 28 августа 2017
Статья
Казаков К., Семенов В. А. Труды Института системного программирования РАН. 2017. Т. 29. № 5. С. 185-238.

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

Добавлено: 12 декабря 2018
Статья
Аничкин А., Семенов В. А. Труды Института системного программирования РАН. 2017. Т. 29. № 3. С. 247-296.

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

Добавлено: 12 декабря 2018
Статья
С.Д. Кузнецов Труды Института системного программирования РАН. 2015. Т. 27. № 1. С. 173-192.

В 2005 г. я написал статью, в которой приводил наиболее существенные черты стандартов ODMG 3.0 (объектная модель ODMG) и SQL:2003 (модель данных SQL) и убедительно (как мне тогда казалось) доказывал, что сходство между объектной моделью и объектными расширениями SQL является чисто внешним, что за близкими на вид синтаксическими конструкциями скрываются глубинные различия модельного уровня. Примерами таких различий являются фоннеймановское разыменование объектных идентификаторов в модели ODMG по сравнению с ассоциативным разыменованием ссылочных значений в модели SQL, раздельное и независимое хранение объектов одного объектного типа в модели ODMG по сравнению с хранением всех строк типизированной таблицы в одной этой таблице в модели SQL, хранение объектных идентификаторов в экстенте в модели ODMG и хранение в аналоге экстента самих объектов в модели SQL и т.д. С тех пор прошло много лет, за которые я понял многие вещи, неправильно или недостаточно правильно понимавшиеся мной тогда, и постепенно пришел к выводам, что: 1.    различия, которые мне казались глубинными, таковыми не являются, да и вообще не являются различиями уровня модели; 2.    объектные расширения SQL обеспечивают не меньшие (а скорее большие) возможности, чем объектная модель ODMG; 3.    при разумном (с позиций сообщества баз данных) использовании СУБД, основанной на модели ODMG, будут создаваться базы данных и средства манипулирования ими, близкие к тем, которые предписывает модель данных SQL.

Добавлено: 23 января 2018
Статья
Захаров В. А., Абрамова И. В., Варновский Н. П. и др. Труды Института системного программирования РАН. 2019. Т. 31. № 6. С. 145-162.

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

Добавлено: 19 февраля 2020
Статья
Дворянский Л. В. Труды Института системного программирования РАН. 2011. № 20. С. 71-94.

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

Добавлено: 20 сентября 2012
Статья
Кудряшов Е. А., Мельник Д. М., Монаков А. В. Труды Института системного программирования РАН. 2016. Т. 28. № 1. С. 63-80.

В статье рассматривается подход к оптимизации вызовов внешних функций в позиционно-независимом коде, основанный на выдаче вызовов непосредственно через глобальную таблицу смещений (GOT), минуя таблицу компоновки процедур (PLT). Стандартные механизмы кодогенерации на операционной системе Linux предполагают создание PLT не только для основного модуля (который является позиционно-зависимым и полагается на механизм PLT для вызовов внешних процедур), но и для динамических библиотек, где PLT используется также для организации ленивого связывания; однако, использование PLT требует дополнительной инструкции перехода, может иметь низкую локальность по кешу и на некоторых архитектурах накладывает дополнительные ограничения на работу компилятора в месте вызова. Реализация вызовов внешних функций в виде косвенных переходов на адреса, загруженные непосредственно из GOT в месте вызова, позволяет избежать недостатков вызовов через PLT, ценой отказа от возможности ленивого связывания и, возможно, увеличением размера кода. Была исследована реализация этой оптимизации для архитектур x86 и ARM в компиляторе GCC. Было обнаружено, что на архитектуре ARM отсутствуют типы релокаций, которые позволили бы генерировать оптимальный код для загрузок из GOT. Для решения этой проблемы в GCC и Binutils (в ассемблере и компоновщике) были реализованы недостающие типы релокаций, позволяющие построить адрес позиции в GOT относительно счетчика команд, используя инструкции movt, movw. Проведенное тестирование свидетельствует, что предложенная оптимизация позволяет получить увеличение производительности, несмотря на увеличение размеров динамических библиотек.

Добавлено: 5 ноября 2018
Статья
Аветисян А. И., Мельник Д., Курмангалеев Ш. Ф. и др. Труды Института системного программирования РАН. 2014. Т. 26. № 1. С. 343-356.

В статье рассматривается рабочий цикл оптимизации производительности приложений для заданной процессорной архитектуры на примере открытых компиляторов GCC и LLVM. Приводятся примеры выполненных оптимизаций и их результаты тестирования на известных наборах тестов. Также описывается инструмент TACT автоматической настройки компилятора на заданное приложение и его примерное использование как прикладным разработчиком, так и компиляторным инженером, приводятся результаты работы инструмента.

Добавлено: 22 марта 2017
Статья
Емеленко А., Маллачиев К., Пакулин Н. В. Труды Института системного программирования РАН. 2017. Т. 29. № 4. С. 295-302.

В этой статье мы расскажем о проекте по разработке отладчика для мультиплатформенной операционной системы реального времени JetOS, созданной для гражданских авиационных систем. Она предназначена для работы в рамках архитектуры Интегрированной Модульной Авионики (ИМА) и реализует ARINC 653 спецификацию API. Эта операционная система разрабатывается в институте системного программирования РАН, и важным шагом в ее создании является разработка инструмента для отладки пользовательских приложений. В этой статье будут рассмотрены проблемы особенностей отладчика для операционной системы реального времени и показаны методы, которыми достигается его мультиплатформенность, а также легкая переносимость на новую платформу. Более того, были рассмотрены другие отладчики для встраиваемых операционных систем, такие как CodeWarrior, отладчики для WxWorks и L4Ka::Pistachio, а также был изучен их функционал.  В заключение мы представим наш отладчик, который может работать как в эмуляторе QEMU, используемом для эмуляции окружения для  JetOS, так и на целевой машине на всех поддерживаемых платформах. Представленный отладчик является удаленным и построен с использованием структуры GDB, но содержит ряд расширений, специфичных для отладки встроенных приложений. Сама структура отладчика была разделена на архитектурно зависимые и независимые части, что помогает облегчить перенос отладчика на новую платформу. В то же время наш отладчик удовлетворяет большинству требований, налагаемых к отладчику операционной системы реального времени, а также уже используется разработчиками приложений для Jet OS.

Добавлено: 12 февраля 2018
Статья
С.Д, Кузнецов, Мендкович Н. А. Труды Института системного программирования РАН. 2013. Т. 25. С. 113-130.

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

Добавлено: 30 января 2018
Статья
С.Д. Кузнецов, Мендкович Н. А. Труды Института системного программирования РАН. 2013. Т. 25. С. 113-130.

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

Добавлено: 6 ноября 2017
Статья
Дробышевский М., Коршунов А., Turdakov D. Y. Proceedings of the Institute for System Programming of the RAS. 2016. Vol. 28. No. 6. P. 153-170.

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

Добавлено: 28 августа 2017
Статья
Трофимович Ю., Козлов И., Турдаков Д. Ю. Труды Института системного программирования РАН. 2016. Т. 28. № 6. С. 185-196.

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

Добавлено: 28 августа 2017