Статьи журнала - Труды Института системного программирования РАН
Все статьи: 115
Комплекс алгоритмов функционирования системы безопасного исполнения программного кода
Статья научная
В настоящей статье представлен комплекс алгоритмов, составляющих основу функционирования системы безопасного исполнения программного кода. Функциональным предназначением данной системы является проведение исследования произвольных исполняемых файлов операционной системы в условиях отсутствия исходных кодов с целью обеспечения возможности контроля исполнения программного кода в рамках заданных функциональных требований. Представленный в работе комплекс алгоритмов включает в себя: алгоритм функционирования системы безопасного исполнения программного кода и алгоритм построения модели программы, пригодной для проведения верификации и сохраняющей свойства исходной программы.
Бесплатно
Статья научная
В статье представлена композиционная модель функционально-ориентированных информационных ресурсов информационно-управляющих систем, а также способ построения этой модели. Предлагаемая модель и способ построения функционально-ориентированных информационных ресурсов обеспечивают расширенные возможности по созданию перспективных средств защиты информационно-управляющих систем, ориентированных на комплексную защиту выполнения задач с учетом уровней управления сложных организационно-технических систем. Композиционная модель соответствует модели данных в не первой нормальной форме, образована функциональным комплексом данных и представляется в виде многоосновной алгебраической структуры, который отображает структуру, взаимосвязи, а также специфику операций манипулирования и обработки над сложно структурированными данными на различных уровнях управления информационно-управляющих систем. Способ построения функционально-ориентированных информационных ресурсов информационно-управляющих систем основан на дедуктивном методе построения аксиоматических теорий. Представлено формализованное описание функционально-ориентированных информационных ресурсов информационно-управляющих систем для решения задач различных уровней управления; функционального комплекса данных многоосновной алгебраической структуры композиционной модели; функциональных зависимостей и отношения, образующих систему аксиом композиционной модели. Показаны графические элементы, на которых отображено распределение компонентов подсистем информационно-управляющей системы на смежных уровнях управления; структурно-функциональная диаграмма взаимодействия компонентов информационно-управляющих систем, распределенных по уровням управления; структура композиционной модели функционально-ориентированных информационных ресурсов информационно-управляющей системы, представленная таблицей сложно структурированных данных в не первой нормальной форме; структурно-логическая схема способа построения композиционной модели функционально-ориентированных информационных ресурсов информационно-управляющих систем.
Бесплатно
Логика первого порядка для задания требований к безопасному программному коду
Статья научная
В настоящее время вопросу защиты информации при проектировании и эксплуатации объектов критической информационной инфраструктуры уделяется особое внимание. Одним из распространенных подходов к обеспечению безопасности информации, обрабатываемой на объектах, при этом является создание изолированной программной среды. Безопасность среды обуславливается ее неизменностью. Однако эволюционное развитие систем обработки информации порождает необходимость запуска в данной среде новых компонентов и программного обеспечения при условии выполнения требований по безопасности. Наиболее важным при этом является вопрос доверия к новому программному коду. Данная работа посвящена разработке формального логического языка описания функциональных требований к программному коду, который позволит в дальнейшем предъявлять требования на этапе статического анализа и контролировать их выполнение в динамике.
Бесплатно
Статья научная
Работа посвящена поиску приближенного решения системы уравнений газовой динамики методом RKDG (Runge - Kutta Discontinuous Galerkin), который характеризуется высоким порядком точности по сравнению с классическим методом конечных объёмов (МКО). Вычислительный алгоритм реализован на языке C++ и верифицирован на тестовых задачах. Результаты моделирования акустического импульса на достаточно грубой сетке с кусочно-линейной аппроксимацией хорошо согласуются с аналитическим решением, в отличие от численного приближения с помощью МКО. Для задачи Сода приводится сравнение зависимости схемы от выбора численных потоков, индикатора проблемных ячеек и лимитера.
Бесплатно
Метод оценки эксплуатируемости программных дефектов
Статья научная
В статье рассматривается метод оценки эксплуатируемости программных дефектов. Применение данного подхода позволяет осуществить приоритезацию найденных ошибок в программах. Это даёт возможность разработчику программного обеспечения исправлять ошибки, которые представляют наибольшую угрозу безопасности в первую очередь. Метод представляет собой совместное применение предварительной классификации аварийных завершений и автоматическую генерацию эксплойтов. Предварительная классификация используется для фильтрации неэксплуатируемых ошибок. Если аварийное завершение считается потенциально эксплуатируемым, то выбирается соответствующий алгоритм генерации эксплойта. В случае успешной генерации эксплойта происходит проверка работоспособности посредством эксплуатации анализируемой программы в эмуляторе. Для поиска программных дефектов можно использовать различные методы. В качестве таких методов можно выделить фаззинг и активно развивающийся в настоящее время подход к поиску ошибок на основе динамического символьного выполнения. Главным требованием для использования предлагаемого метода является возможность получения входных данных, на которых проявляется найденный дефект. Разработанный подход применяется к бинарным файлам программ и не требует дополнительной отладочной информации. Реализация метода представляет собой совокупность программных средств, которые связаны между собой управляющими скриптами. Метод предварительной классификации и метод автоматической генерации эксплойтов реализованы в виде отдельных программных средств, которые могут работать независимо друг от друга. Метод был апробирован на анализе 274 аварийных завершений, полученных в результате фаззинга. В результате анализа удалось обнаружить 13 эксплуатируемых дефектов, для которых в последствии успешно сгенерированы работоспособные эксплойты.
Бесплатно
Методы оптимизации программ на языке JavaScript, основанные на статистике выполнения программы
Статья научная
Язык JavaScript является одним из самых популярных языков для разработки веб-приложений. В связи с ростом производительности персональных компьютеров, мобильных и встраиваемых систем использование JavaScript стало возможным также и в масштабных приложениях. Более того, в настоящее время язык JavaScript активно используется в операционных системах в качестве одного из основных языков для создания пользовательских приложений. Примерами таких систем являются Tizen OS и Firefox OS. С ростом популярности языка многие крупные компании выпустили свои реализации JavaScript, в которых для генерации машинного кода в основном используется многоуровневая динамическая компиляция. В данной работе описываются разработанные методы оптимизации динамических многоуровневых компиляторов с учетом информации о профиле выполнения программы. Метод был реализован в динамическом компиляторе языка JavaScript V8, разработанном компанией Google. Использование профиля выполнения программы позволяет оптимизировать программу для конкретных входных данных. Это особенно актуально в связи с использованием JavaScript в операционных системах. Сценарий использования оптимизации на основе профиля программы в операционных системах следующий: на этапе тестирования программного обеспечения можно организовать сбор информации о профиле программы и использовать его для оптимизации приложений под конкретные случаи выполнения. Одним из новых применений использования информации о профиле программы может быть обеспечение немедленного переключения выполнения часто исполняющихся участков кода на уровень оптимизирующего компилятора. Другое применение - удаление обратных переходов на неоптимизирующие уровни выполнения.
Бесплатно
Статья научная
Получены необходимые соотношения для реализации алгоритма моделирования осесимметричных течений вязкой несжимаемой жидкости в методе конечных элементов с частицами PFEM-2. Осесимметричная модель реализована в программном комплексе c открытым исходным кодом Kratos на основе существующего модуля для решения плоских задач. Была проведена валидация осесимметричной модели на тестовых задачах. В качестве модельных рассмотрены задачи о течении в трубе (задача Пуазейля) и задача о моделировании падения капли в глубокий слой жидкости. Численное решение, полученное методом конечных элементов с частицами, для задачи Пуазейля показало удовлетворительное согласие с аналитическим; решение задачи о падении капли в слой глубокий жидкости в комплексе Kratos сравнивалось с результатом моделирования в программном пакете Gerris с открытым исходным кодом. Результаты расчетов также удовлетворительно согласуются.
Бесплатно
Моделирование программно-аппаратных систем и анализ их безопасности
Статья научная
В данной статье демонстрируется целесообразность применения языка моделирования программно-аппаратных систем AADL и его расширения Error Model Annex для описания требований безопасности проектируемой системы. Наиболее важным аспектом здесь является возможность описания требований безопасности в терминах, используемых в теории безопасности, таких, как марковские цепи или логико-вероятностные функции, т.к. за годы развития теории было накоплено большое количество весьма полезных результатов. Различные подходы к оценке безопасности систем не конкурируют, но дополняют друг друга, так что наличие некоторой универсальности в описании требований безопасности является весьма ценным качеством.
Бесплатно
Модель поведения объектов, подверженных спонтанному изменению, в прецедентном подходе к управлению
Статья научная
В рамках прецедентного подхода к управлению сложными объектами, не поддающимися формализации в виде математической модели, предложена модель поведения объектов, вовлеченных в вялотекущие процессы и подверженных, казалось бы, внезапному спонтанному переходу в лавинообразный процесс. Для описания таких изменений вводится понятие сопутствующего класса, влияние которого можно трактовать как дополнительное управляющее воздействие по отношению к исходному классу, к которому принадлежал объект. Модель ориентирована прежде всего на медицину, где можно найти множество аналогов такого поведения.
Бесплатно
Статья научная
Предложен способ построения модифицированных кодов с суммированием взвешенных переходов между разрядами в информационных векторах, занимающими соседние позиции в информационных векторах. Новые коды с суммированием имеют такое же количество контрольных разрядов, как и классические коды Бергера, однако обнаруживают большее количество ошибок в информационных векторах. Модифицированные коды с суммированием взвешенных переходов по сравнению с кодами Бергера также имеют улучшенные характеристики обнаружения ошибок в области малой кратности. Кроме того, для некоторых значений длин информационных векторов могут быть построены коды с обнаружением любых двукратных и любых трехкратных ошибок. Авторами разработан способ синтеза систем функционального контроля комбинационных схем, основанный на анализе топологии объекта диагностирования с выделением групп контролепригодных выходов с учетом свойств обнаружения ошибок модифицированными кодами с суммированием взвешенных переходов. Сформирован алгоритм синтеза системы функционального контроля.
Бесплатно
Некоторые задачи на графовых базах данных
Статья научная
Одним из наиболее популярных и актуальных подвидов нереляционных баз данных являются графовые базы данных. В данной работе рассмотрены задачи на таких базах данных, которые наиболее часто встречаются в современной литературе. Изучены задачи максимизации влияния, motif mining (MM), задача оценки схожести узлов графа, сопоставление образца в графе. Рассмотрены первичные алгоритмы каждого направления и некоторые промежуточные работы. Проанализированы алгоритмы, соответствующие текущему положению дел.
Бесплатно
О задаче приближенного нахождения максимальной двудольной клики
Статья научная
Задача о нахождении большой "спрятанной" клики в случайном графе и ее аналог для двудольных графов являются объектами рассмотрения в данной заметке.
Бесплатно
О представлении результатов обратной инженерии бинарного кода
Статья научная
В статье рассматривается вопрос представления кода алгоритмов, извлекаемых из бинарного кода в рамках задачи обратной инженерии: как промежуточные представления для автоматического анализа, так и конечные представления, передаваемые пользователю. Разбираются две ключевых подзадачи в области обратной инженерии: автоматический поиск эксплуатируемых дефектов и выявление НДВ. Описана общая схема системы, реализующей автоматический поиск эксплуатируемых дефектов, указаны ключевые свойства промежуточного представления, позволяющего решать такую задачу с точки зрения эффективной генерации системы уравнений для SMT-решателя. Представлен тракт работы системы по выявлению НДВ, состоящий из трех этапов: локализация алгоритма, его представление в удобной для анализа форме и исследование его свойств. Для автоматизации первого этапа применяется построение статико-динамического представления, выделяются события уровня ОС и вызовы библиотечных функций, являющиеся «якорями», от которых отталкивается аналитик при локализации алгоритма. Дальнейшая поддержка локализации осуществляется за счет построения срезов и средств навигации. После того, как локализация алгоритма выполнена, дальнейшая работа разделяется на два направления: диалоговое построение компактного аннотированного представления алгоритма в виде блок-схемы и автоматизированное изучение свойств алгоритма в части определения декларированных и недекларированных потоков данных. Представление алгоритма в виде блок-схемы базируется на построении упрощенных моделей функций, учитывающих входные и выходные буферы, и автоматически выявляемыми связями по данным между буферами различных вызовов функций. Описан общий сценарий работы аналитика с подобной блок-схемой в контексте задачи выявления НДВ, основанный на аннотировании декларированных потоков данных и автоматическом выявлении недекларированных потоков. В завершение статьи приводится пример получаемого представления и перечисляются направления дальнейшей работы.
Бесплатно
О проблеме представления формальной модели политики безопасности операционных систем
Статья научная
В связи с начавшимся процессом внедрения ФСТЭК России «Требований безопасности информации к операционным системам» в работе анализируются пути выполнения требований функциональной компоненты ADV_SPM.1 «Формальная модель политики безопасности», в том числе по определению языка, глубины и детализации представления модели политики безопасности управления доступом и информационными потоками. При этом приводятся предложения по составу основных элементов модели, использованию для ее верификации инструментальных средств. Практическая возможность применения предлагаемых подходов рассматривается на примере представления описания и верификации МРОСЛ ДП-модели, как основы механизма управления доступом в ОССН Astra Linux Special Edition.
Бесплатно
Об оценках вычислительной сложности и погрешности быстрого алгоритма в методе вихревых элементов
Статья научная
Основная вычислительная сложность при использовании вихревых методов сосредоточена в вычислении конвективных и диффузионных скоростей всех вихревых элементов. Рассматривается один из эффективных способов ускорения вычислений в методе вихревых элементов - алгоритм типа Барнса - Хата. Метод основан на построении иерархической структуры областей (дерева). При вычислении конвективных скоростей вихревых элементов данный метод позволяет учитывать взаимное влияние вихревых элементов, находящихся далеко друг от друга, приближенно по формуле, полученной с помощью разложения выражения для конвективной скорости в ряд Тейлора. Влияние вихревых элементов, находящихся в ближней зоне, рассчитывается напрямую по закону Био - Савара. При реализации данного алгоритма возникают параметры, влияющие на вычислительную трудоемкость и точность решения задачи: - количество уровней дерева и - параметр дальности ячеек. Влияние вихревых элементов на диффузионные скорости друг друга экспоненциально затухает с увеличением расстояния между ними. Поэтому для вычисления диффузионных скоростей также построен алгоритм, позволяющий с помощью использования структуры дерева находить вихревые элементы, находящиеся в ближней зоне и вычислять влияние только от них. На основе решения модельных задач получены оценки вычислительной сложности алгоритмов вычисления конвективных и диффузионных скоростей, которые зависят от параметров алгоритма и количества вихревых элементов. Также получены оценки погрешности вычисления конвективных и диффузионных скоростей в зависимости от параметров алгоритма. На практике эти оценки позволяют выбирать оптимальные значения параметров алгоритма и добиваться максимального ускорения вычислений при заданном уровне допустимой погрешности расчета.
Бесплатно
Обещающая компиляция в ARMv8.3
Статья научная
Поведение многопоточных программ не может быть промоделировано попеременным последовательным исполнением различных потоков на одном вычислительном узле. На данный момент полное и корректное описание поведения многопоточных программ является открытой теоретической проблемой. Одним из перспективных решений этой проблемы является „обещающая“ модель памяти. Для того, чтобы некоторая модель могла быть использована в стандарте некоторого промышленного языка программирования, должна быть доказана корректность компиляции из этой модели в модель памяти целевой процессорной архитектуры. Данная статья представляет доказательство корректности компиляции из подмножества обещающей модели в модели памяти процессора ARMv8.3. Главной идеей доказательства является введение промежуточного операционного варианта модели ARMv8.3, поведение которого может быть симулировано обещающей моделью.
Бесплатно
Обзор задач и методов их решения в области классификации сетевого трафика
Статья научная
В статье рассматривается задача классификации сетевого трафика: характеристики, используемые для её решения, существующие подходы и области их применимости. Перечисляются прикладные задачи, требующие привлечения компонента классификации и дополнительные требования, проистекающие из особенности основной задачи. Анализируются свойства сетевого трафика, обусловленные особенностями среды передачи,а также применяемых технологий, так или иначе влияющие на процесс классификации. Рассматриваются актуальные направления в современных подходах к анализу и причины их развития.
Бесплатно
Обзор методов динамической компиляции запросов
Статья научная
Эффективное использование процессора является решающим фактором производительности аналитических систем, особенно с увеличением размеров обрабатываемых данных. В то же время возрастающие объёмы доступной основной памяти позволяют значительно сократить количество обращений к медленным дисковым хранилищам и тем самым отводят традиционные для большинства систем обработки данных оптимизации подсистемы ввода-вывода на второй план. Одним из наиболее эффективных способов повышения эффективности использования процессора и сокращения накладных расходов, прежде всего проявляющихся в затратах на интерпретацию планов запросов, является компиляция запросов в исполняемый код во время выполнения (динамическая компиляция). В последнее время наблюдается рост интереса к методам динамической компиляции запросов как в академических, так и в прикладных разработках. Данная статья является обзором литературы в области динамической компиляции запросов, в основном для реляционных СУБД. Представлены работы последних лет, описаны архитектурные особенности методов, сделана классификация работ, приведены основные результаты.
Бесплатно
Обзор подходов к улучшению качества результатов статического анализа программ
Статья научная
В настоящий момент индустрия создания программ для всевозможного рода вычислительных устройств находится в состоянии бурного развития. Постоянно увеличивающаяся мощность вычислительных систем предоставляет всё новые возможности для создания высокопроизводительных, в том числе - параллельных, программ и программных комплексов. В связи с этим постоянно возрастает сложность программного обеспечения, управляющего вычислительными системами. Из-за высокой сложности программных систем процесс обеспечения качества разрабатываемого программного обеспечения требует новых подходов к процессу проверки корректности программ как на соответствие требованиям пользователей, так и на наличие критических дефектов и уязвимостей безопасности. Одним из методов контроля качества программного обеспечения является применение инструментальных средств программиста, предназначенных для анализа программ. Отрасль создания инструментальных средств статического и динамического анализа программ активно развивается с начала 2000-х годов. Разрабатывается большое количество академических и промышленных сред и инструментов анализа программ. В связи с фундаментальными ограничениями и инженерными компромиссами в угоду производительности и масштабируемости инструменты статического анализа не всегда могут обеспечить отсутствие ошибок первого рода в результатах своей работы. При этом анализ предупреждений инструмента может отнимать значительное время высококвалифицированного эксперта в области разработки и обеспечения качества программного обеспечения. В связи с этим возникает задача улучшения качества результатов работы статических анализаторов программ. Данная статья посвящена обзору методов анализа программ и подходов к улучшению качества работы статических анализаторов. Особое внимание в статье уделяется методам совмещения подходов статического и динамического анализа программ.
Бесплатно
Обзор расширяемого протокола аутентификации и его методов
Статья научная
Данная статья представляет собой обзор расширяемого протокола аутентификации (Extensible Authentication Protocol, EAP), специфицированного комитетом Internet Engineering Task Force, IETF, и предоставляющего эффективный механизм встраивания в него различных методов аутентификации, а также обзор собственно методов аутентификации EAP, часть из которых была стандартизована в спецификациях IETF. Показано разнообразие механизмов, используемых для реализации сервиса аутентификации. Работа выполнялась при поддержке РФФИ, проект № 16-07-00603 «Верификация функций безопасности и оценка устойчивости к атакам реализаций протокола аутентификации EAP».
Бесплатно
