Preview

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

Расширенный поиск
Том 27, № 1 (2015)
Скачать выпуск PDF
https://doi.org/10.15514/ISPRAS-2015-27(1)

5-24
Аннотация

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

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

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

В статье приведены результаты практических экспериментов по применению разработанной программной системы, реализующей предлагаемый метод. На примере задачи подсчёта базовых блоков разработанная система показала более высокую производительность по сравнению с распространённым средством инструментации Valgrind.
25-38
Аннотация

В статье рассматривается задача проведения динамического анализа программ на языке Java при условии, что исходный код программы отсутствует, а запуск программы может происходить на виртуальных машинах, которые интерпретируют байт-код формата, отличного от формата Java Virtual Machine. Приводится обзор методов инструментации и особенностей инструментации байт-кода языка Java для проведения итеративного динамического анализа с целью покрытия наибольшего числа путей выполнения программы. Для такого рода анализа используется построение входных данных для покрытия ранее не пройденных базовых блоков при помощи отслеживания потока помеченных данных, построения ограничений пути и проверки их выполнимости. В качестве метода решения поставленной задачи рассматривается применение статической инструментации байт-кода. Основными достоинствами подобного подхода являются увеличение скорости анализа (за счёт того, что инструментация проводится один раз, до начала работы итеративного механизма) и возможность конвертировать инструментированный байт-код в другие форматы для запуска на нестандартных виртуальных машинах (например, DEX для виртуальной машины Dalvik). В статье также рассматривается реализация предложенных методов в инструменте Coffee Machine. Инструментация осуществляется с помощью BCEL (библиотеки для манипулирования байт-кодом) и разделяется на три этапа: определение классов и методов для инструментации, инструментация на уровне классов и методов, инструментация на уровне отдельных инструкций. На основе Coffee Machine показано, как статическая инструментация может быть применена для печати информации о выполнившихся инструкциях, отслеживания помеченных данных, построения ограничений пути выполнения, а также для построения трассы синхронизационных событий. В качестве одного из ограничений предложенного подхода рассматривается невозможность доступа к динамическим данным в ходе выполнения программы и некоторым методам системных классов. Эти ограничения могут быть сняты за счёт увеличения накладных расходов на повторную инструментацию анализируемой программы и написание методов, симулирующих работу требуемых системных методов. Для использования методов-симуляторов используется специальный механизм, который сопоставляет их имена и имена реальных методов в процессе работы программы и производит дублирование вершины стека для передачи фактических параметров методу-симулятору.

39-50
Аннотация
В статье обсуждаются существующие методы поиска семантически сходных участков кода (клонов). Анализируются недостатки каждого метода, на основе чего предлагается новый метод поиска клонов кода и описывается архитектура инструмента для языков C/C++ на основе компиляторной инфраструктуры LLVM, в которой реализован предложенный метод. Работу инструмента можно разделить на два основных этапа. На первом этапе программа компилируется в промежуточное представление LLVM  компилятором Clang. По этому представлению строится граф зависимостей программы (Program Dependence Graph – PDG) для каждой единицы компиляции. На втором этапе производится анализ  поиска клонов кода в построенных графах. В инструменте существует отдельный этап тестирования алгоритмов, который будет подключен при запуске инструмента в режиме тестирования. Это дает возможность автоматической генерации тестов и проверки точности реализованных алгоритмов.
51-68
Аннотация
Исследование графов автоматами является корневой задачей во многих приложениях. К таким приложениям относятся верификация и тестирование программных и аппаратных систем, а также исследование сетей, в том числе сети интернета и GRID на основе формальных моделей. Модель системы или сети, в конечном счёте, сводится к ориентированному графу переходов, свойства которого нужно исследовать. За последние годы размер реально используемых систем и сетей и, следовательно, размер их графовых моделей непрерывно растёт. Проблемы возникают тогда, когда исследование графа одним автоматом (компьютером) либо требует недопустимо большого времени, либо граф не помещается в памяти одного компьютера, либо и то и другое. Поэтому возникает задача параллельного и распределённого исследования графов. Эта задача формализуется как задача исследования графа коллективом автоматов. В основе такого исследования лежит обход графа (проход по всем его дугам, достижимым из начальной вершины). Автоматы могут генерироваться в начальной вершине графа, перемещаться по дугам графа в направлении их ориентации и обмениваться между собой сообщениями через независимую (от графа) сеть связи. Суммарная память автоматов используется для хранения описания пройденной части графа. Для перемещения из вершины по выходящей из неё дуге графа автомат каким-то образом должен идентифицировать эту дугу: указать её номер. В нашей статье «Обход неизвестного графа коллективом автоматов» предложен алгоритм такого обхода для случая детерминированных графов. Задача усложняется, если граф недетерминирован. В таком графе одному номеру дуги соответствует, вообще говоря, несколько дуг, из которых для перехода выбирается одна дуга недетерминированным образом. Для того, чтобы обход графа был возможен, должна быть гарантия, что при неограниченном числе экспериментов каждая выходящая из вершины дуга с данным номером может быть пройдена. Такой недетерминизм мы называем справедливым. Решению задачи обхода справедливо недетерминированных графов посвящена данная работа.
69-96
Аннотация
Исследование ориентированных графов является корневой задачей во многих приложениях. Такое исследование имеет особую специфику тогда, когда граф моделирует сеть связи, в том числе сеть интернета и GRID. Узел сети имеет локальную информацию о сети: он «знает» только о дугах, выходящих из этой вершины, но «не знает», куда  (в какие вершины) эти дуги ведут. Узлы сети обмениваются сообщениями, передаваемыми по сетевым связям, которые в графе изображаются как дуги и играют роль каналов передачи сообщений. Исследование графа базируется на его обходе, когда сообщение проходит по каждой дуге графа. Пока не пройдена какая-то дуга, нет уверенности, что она не ведёт в ещё не исследованную часть графа. Обычно рассматривается обход графа с помощью одного сообщения, циркулирующего в сети. Обход выполняется быстрее, если выполнять его параллельно: по сети одновременно циркулирует не одно, а множество сообщений. В данной работе рассматривается параллельное исследование сильно связного графа, целью которого является не просто обход графа, а сбор полной информации о графе в каждой его вершине. Вторая особенность работы – исследование динамически меняющегося графа: его дуги могут исчезать, появляться или менять свои конечные вершины. Предлагается алгоритм работы автоматов, который обеспечивает сбор полной информации о графе в каждой вершине графа.
97-124
Аннотация
В статье дается обзор существующих методов извлечения моделей из описаний цифровой аппаратуры, разработанных на языках семейства HDL (Hardware Description Language). Методы извлечения моделей используются для решения многих задач, связанных с процессом проектирования и обеспечения качества программных и аппаратных систем. В данной работе затрагиваются методы решения следующих актуальных задач – оптимизация кода, оптимизация логического синтеза, абстракция, функциональная верификация. В статье рассматриваются методы извлечения таких семейств моделей, как графы потока и зависимостей, а также автоматные модели. Подробно рассматриваются методы построения программных срезов, конечных автоматов и расширенных конечных автоматов.
125-150
Аннотация
Описываются различные виды сервисов и служб, используемых в современных программных и распределенных системах. Дается характеристика широко распространенных и внедренных в практику систем со спектром системных и функциональных сервисов. Рассмотрены модели сервисной, сервисно-компонентной архитектур и системы сервисной поддержки WCF для представления прикладных систем из готовых сервисов с целью решения бизнес-задач. Приведен пример решения бизнес задачи обработки данных в калькуляторе, реализованном с помощью сервисной службы WCF комплекса ИТК.
151-172
Аннотация
В статье представлен новый подход идентификации пользователя на основе анализа его поведения при работе с текстовой информацией. Для описания поведения пользователя предлагается использовать содержимое текстовых документов, к которым он обращался. Структурированное представление рассматриваемой поведенческой информации осуществляется на основе отображения содержимого электронных документов в тематическое пространство пользователя, формируемое с использованием неотрицательной матричной факторизации. Веса выделенных тематик в документе характеризуют тематическую направленность пользователя во время работы с данным документом. Изменение значений весов тематик во времени формирует многомерный временной ряд, описывающий историю поведения пользователя при работе с текстовыми данными. Построение прогноза такого временного ряда позволит осуществлять идентификацию данного пользователя на основе оценки отклонений наблюдаемой тематической направленности пользователя от спрогнозированных значений. В рамках предложенного подхода был разработан собственный оригинальный метод прогнозирования временных рядов, основанный на ортонормированной неотрицательной матричной факторизации (ОНМФ). Важно отметить, что ранее методы неотрицательной матричной факторизации не использовался для решения задачи прогнозирования временных рядов. Проведённое экспериментальное исследование на примере реальной корпоративной переписки пользователей, сформированной из набора данных Enron, показало применимость предложенного подхода идентификации пользователя. Кроме того, эксперименты с применением других популярных на сегодняшний день методами прогнозирования показали превосходство разработанного метода на основе ОНМФ по качеству классификации тематических характеристик пользователя. Также в работе исследовались два различных подхода оценки отклонений: абсолютная оценка и оценка p-значения. Эксперименты показали, что оба рассмотренные подхода расчёта оценки отклонения временной точки от прогноза применимы в предложенном подходе идентификации пользователя.
173-192
Аннотация

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

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


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


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