Preview

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

Расширенный поиск
Том 28, № 6 (2016)
Скачать выпуск PDF
9-10 38
Аннотация
В заключительном выпуске 28-го тома публикуются статьи, посвященные технологии анализа, моделирования и трансформации программ, технологии распределенных систем, анализу текстов на естественных языках и анализу социальных сетей.
11-26 62
Аннотация
Анализ помеченных данных неоднократно пытались применять для исследования безопасности бинарного кода, но все попытки наталкивались на ряд нерешенных вопросов. В данной работе рассматриваются ограничения анализа помеченных данных на уровне бинарного кода, когда он проводится в рамках всей системы. Предлагается подход, способный преодолеть такие ограничения, как высокие накладные расходы на анализ, разрыв в уровне абстракций бинарного и исходного кода и сложности переноса на другие процессорные архитектуры и ОС. Подход позволяет смягчить негативное влияние недостаточной и избыточной помеченности. В подходе используется полносистемный эмулятор, использующий бинарную трансляцию. Возможности анализа помеченных данных обеспечиваются тремя встроенными в эмулятор механизмами: детерминированным воспроизведением, плагинами инстроспекции ВМ и инструментированием промежуточного представления. Приводятся экспериментальные результаты, показывающие лучшую скорость работы в сравнении с аналогичными программными инструментами.
27-36 117
Аннотация
В данной работе предложен метод классификации ROP гаджетов, который позволяет аналитику сделать вывод о применимости техники ROP для эксплуатации уязвимостей в том или ином случае. Метод, реализованный в виде программного инструмента, применим к бинарным файлам программ. Работа инструмента продемонстрирована на 32-х и 64-х битных приложениях из дистрибутива Ubuntu 14.04, а возможность применения ROP на основе результатов классификации подтверждена на нескольких примерах.
37-48 101
Аннотация
В последние годы по мере увеличения производительности и роста объема оперативной и внешней памяти производительность СУБД для некоторых классов запросов определяется непосредственно скоростью обработки запросов процессором. Для исполнения SQL-запросов в большинстве современных реляционных СУБД используется модель итераторов (Volcano-модель), которая удобна в реализации в рамках интерпретатора запросов, но сопряжена с существенными накладными расходами при выполнении плана, например, связанными с большим количеством ветвлений, неявными вызовами функций-обработчиков и выполнением лишних проверок, избежать которых довольно сложно при использовании механизма интерпретации. Одно из решений - динамическая компиляция запросов. В рамках данной работы рассматривается метод динамической компиляции запросов с применением альтернативной модели выполнения запроса в СУБД, что подразумевает отказ от используемой в PostgreSQL итеративной Volcano-модели, и его реализация для СУБД PostgreSQL с помощью компиляторной инфраструктуры LLVM. Динамический компилятор запросов реализован в виде расширения к СУБД PostgreSQL и не требует изменения исходного кода СУБД. Результаты проведенного тестирования показывают, что динамическая компиляция запросов с помощью JIT-компилятора LLVM позволяет получить ускорение в несколько раз на тестовом наборе TPC-H.
49-64 62
Аннотация
Большие программные системы всегда создаются достаточно долго, в несколько этапов, это приводит к необходимости появления версий (релизов) систем. Кроме того, у большой системы всегда есть несколько, а иногда много, конфигураций установки, что обуславливается либо разным набором программно-аппаратного окружения, либо требованиями пользователя системы. Тем самым результатом разработки можно рассматривать не отдельную систему, а цепочку и семейство программных систем или программных продуктов (Product Lines/Product Families). Появление этого понятия можно рассматривать как развитие методов повышения доли повторно-используемого программного обеспечения (re-use). Однако, в отличие от ранних работ по повторно-используемому ПО исследования по семействам программ рассматривают весь спектр работ и задач создания ПО, то есть не только собственно проектирование и программирование, но и документирование, верификацию, поддержку эксплуатации, в частности, инсталляцию и так далее. Одной из работ, выполняемых в ходе создания семейства программ, является моделирование. Статья рассматривает современные подходы к моделированию семейств программных систем, а также, подробнее, одно из направлений этого исследования - моделирование семейств операционных систем (описывая задачи исследования, поддержанного грантом РФФИ).
65-86 53
Аннотация
В статье представлен конфигурируемый метод для поиска состояний гонок. Метод позволяет настраивать требуемую точность анализа, выбирая баланс между затрачиваемыми ресурсами и количеством ложных предупреждений подключением двух расширений: уточнением путей на основе предикатных абстракций и анализом потоков. Метод основан на алгоритме Lockset и использует упрощенную модель памяти для уменьшения количества ложных предупреждений. Предлагаемый подход был реализован в инструменте CPALockator, который был апробирован на модулях ядра операционной системы Linux, что позволило обнаружить несколько состояний гонок, которые были признаны и исправлены разработчиками.
87-102 90
Аннотация
ARM - это семейство микропроцессорных архитектур, разработанных в одноименной компании. Новейшая архитектура этого семейства, ARMv8, содержит большое число команд разных типов и отличается сложной организацией виртуальной памяти (включающей аппаратную поддержку многоуровневой трансляции адресов и виртуализации); все это делает функциональную верификацию микропроцессоров этой архитектуры крайне трудной технической задачей. Неотъемлемой частью верификации микропроцессора является генерация тестовых программ - программ на языке ассемблера, создающих разнообразные ситуации (исключения, блокировки конвейера, неверные предсказания переходов, вытеснения данных из кэш-памяти и т.п.). В статье описываются требования, предъявляемые к промышленным генераторам тестовых программ, и представляется генератор для микропроцессоров архитектуры ARMv8, разработанный с использованием инструмента MicroTESK (Microprocessor TEsting and Specification Kit). Генератор поддерживает подмножество команд, характерное для мобильных приложений (около 400 команд) и состоит из двух основных частей: (1) архитектурно независимого ядра и (2) формальной спецификации ARMv8 (точнее, модели, автоматически построенной по формальным спецификациям). При такой организации процесс разработки генератора тестовых программ состоит преимущественно в создании формальных спецификаций, что экономит усилия за счет повторного использования архитектурно независимых компонентов. Архитектура описывается на языках nML и mmuSL: первый язык позволяет описывать регистры микропроцессора, синтаксис и семантику команд; второй - устройство подсистемы памяти (адресные пространства, разного рода буферы и таблицы, алгоритмы трансляции адресов и т.п.). В статье приводятся характеристики разработанного генератора и делается сравнение с существующими аналогами.
103-110 71
Аннотация
В статье предложены различные способы представления результатов анализа сетевого трафика, необходимость в которых возникает прежде всего в задачах обеспечения сетевой информационной безопасности. Рассмотрена возможность построения полного графа сетевых взаимодействий, а также создания временной диаграммы передачи пакетов. Эти компоненты используются при расследовании инцидентов нарушения ИБ. Временная диаграмма также применяется при анализе туннельных протоколов, поскольку позволяет аналитику определить, какие именно заголовки протоколов необходимо визуализировать. Для задач, связанных с обратной инженерией, а также отладкой сетевых протоколов, предлагается использовать журнал, в котором фиксируются ошибки разбора заголовков протоколов. Представленные графические компоненты либо не имеют аналогов среди opensource-инструментов, либо улучшают уже существующие opensource-решения.
111-120 102
Аннотация
Apache Spark является одним из наиболее производительных распределенных фреймворков для обработки больших данных в парадигме Map-Reduce. С распространением облачных технологий и предоставления ресурсов по запросу все более актуальной становится задача построения виртуальных вычислительных кластеров для конкретной задачи. В работе представлен краткий обзор разработанного решения для создания виртуальных кластеров Apache Spark в облачной среде Openstack и подведение итогов исследования о способах создания виртуальных кластеров Apache Spark в открытых облачных средах. Решение построено с использованием системы оркестрации Ansible. В работе будет проведено качественное сравнение разработанных в ИСП РАН подходов к решению задачи.
121-140 128
Аннотация
В этой статье рассматривается вопрос применения анализа данных большого объема с использованием облачных вычислений для решения задач анализа дорожного траффика в контексте «умных» городов. Предложенное решение базируется на модели параллельных вычислений MapReduce, реализованной на платформе Hadoop. Анализируются два экспериментальных случая: оценка качества общественного транспорта на основе анализа истории местоположения автобусов, и оценка мобильности пассажиров при помощи анализа истории покупок билетов с транспортных карт. Оба эксперимента используют реальную базу данных системы общественного транспорта Монтевидео в Уругвае. Результаты эксперимента показали, что рассмотренная модель действительно позволяет эффективно обрабатывать большие объемы данных.
141-152 1115
Аннотация
Жизнь современного мира во многом зависит от функционирования больших однородных сетей, таких как проводные и безпроводные коммуникационные системы, сети дорог и трубопроводов. Поддержание их эффективной работы требует автоматического контроля, постоянной оптимизации, включающей обработку больших объемов данных с использованием высокопроизводительных распределенных систем. Предложен новый мета-алгоритм для анализа больших однородных сетей, их альтернативного разбиения на слабосвязанные подсети и параллельной оптимизации наиболее независимых элементов подсетей. Данный подход основан на специфической для сети корреляционной функции, алгоритме имитации отжига и адаптирован для работы в вычислительном кластере. На примере безпроводной коммуникационной сети показано, что предложенный алгоритм существенно увеличивает скорость многопоточной оптимизации. Разработанный общий подход может быть использован для анализа и оптимизации широкого спектра сетей, включая такие специфические типы как искусственные нейронные сети или организованные в виде сетей физиологические системы живых организмов.
153-170 126
Аннотация
В статье представлены новые алгоритмы расчета модулярности для направленных взвешенных графов с пересекающимися сообществами. Рассматриваются несколько подходов для вычисления модулярности и их расширения. Учитывая вычислительную сложность известных подходов, предлагаются два параллельных расширения, масштабируемых на графы с более 104 вершин.
171-184 86
Аннотация
Работа посвящена методам определения возраста пользователей социальных сетей. Социальные сети предоставляют пользователям возможность заполнять свои профили, которые могут включать в себя возраст. В связи с тем, что профили заполняются не полностью, возникает задача предсказания неуказанных значений атрибутов пользователей. Явно указанные и предсказанные значения возраста используются в рекомендательных и маркетинговых системах, они позволяют фильтровать целевую аудиторию рекомендуемых товаров и услуг. Кроме того, предсказанные значения могут использоваться для более точного определения демографического профиля интернет-сообществ, целевую аудиторию рекламных кампаний в Интернете. В данной работе предлагается метод, предсказывающий незаполненное значение возраста пользователя. Метод использует следующую доступную информацию из социальной сети: явно указанные пользователями значения возраста и социальные связи. Метод основан на распространении меток по графу друзей и подписок пользователей на сообщества.
185-196 44
Аннотация
В статье рассматриваются подходы к определению основного места проживания пользователей социальных сетей по графу образуемому в результате установления двунаправленной связи - “дружбы”. Предложен подход, базирующийся на векторном представлении вершин графа и последующем применении алгоритма классификации на основе обучения с учителем. Приведены результаты экспериментов и сравнение с референсными подходами. Показано, что предложенный подход сопоставим по качеству с другими подходами.
197-206 62
Аннотация
В статье представлен подход к автоматическому построению лексической онтологии путём извлечения и связывания структурированных данных, направленный на повторное использование материалов существующих лексических ресурсов неизвестного качества. Подход состоит из двух этапов. На первом этапе производится построение и кластеризация графа синонимов с целью вывода отдельных значений слов и их объединения в синонимические ряды, именуемые синсетами или понятиями. На втором этапе производится формирование родо-видовых отношений между понятиями путём сопоставления родо-видовых пар слов. С целью расширения множества доступных родо-видовых пар слов выполняется преобразование векторных представлений гипонимов в векторные представления гиперонимов при помощи проекционной матрицы. Проведены предварительные эксперименты с использованием тезауруса русского языка в качестве золотого стандарта. Проанализированы преимущества и недостатки предложенного подхода.
207-222 79
Аннотация
Одним из главных вопросов при решении задачи классификации временных рядов является выбор меры сходства рядов. В данной статье представлен сравнительный анализ меры сходства временных рядов, основанной на преобразовании скользящих аппроксимаций (САП трансформ), с двумя другими наиболее известными мерами: Алгоритмом Динамической Трансформации и Евклидовым расстоянием для задачи классификации. Кроме того, предложен алгоритм, улучшающий точность меры САП трансформ для временных рядов, имеющих схожие значения, но сдвинутых относительно друг друга по оси X, где координата на оси X представляет собой единицу времени.
223-240 85
Аннотация
В интернете существует множество площадок, которые предоставляют пользователям возможность обмениваться своими мнениями и оставлять отзывы о всевозможных товарах и услугах. Эти мнения могут быть полезны не только для других пользователей, но и для компаний, которые хотят отслеживать собственную репутацию и получать своевременные отзывы о своих продуктах и услугах. Наиболее детальная постановка задачи в данной области ставится при аспектно-ориентированном анализе тональности, в котором определяется отношение пользователя не только к объекту в целом, но и к отдельным его аспектам. В настоящей работе рассмотрено решение подзадачи извлечения аспектных терминов при аспектно-ориентированном анализе тональности. Представлен обзор исследований в данной области. Подзадача извлечения аспектных терминов рассматривается как проблема разметки последовательности; для её решения применяется модель условных случайных полей (CRF). Для составления признакового описания последовательности используются векторные представления слов, полученные на основе нейросетевых моделей для русского языка, а также части речи анализируемых слов. Представлены этапы работы программной системы извлечения аспектных терминов. Эксперименты с разработанной программной системой проводились на размеченном корпусе отзывов о ресторанах, созданном в рамках международного тестирования SemEval-2016 Task 5. Исследованы зависимости качества решения подзадачи извлечения аспектных терминов от различных нейросетевых моделей и вариаций признаковых описаний. Наилучшие результаты (F1-мера = 69%) демонстрирует вариант системы, учитывающий контекст и части речи. Работа содержит подробный анализ ошибок, допущенных системой, а также предложения по возможным вариантам их коррекции. В заключении представлены направления дальнейших исследований.


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


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