Preview

Моделирование и анализ информационных систем

Расширенный поиск
Том 26, № 3 (2019)
Скачать выпуск PDF

Software

317-331 177
Аннотация

Разрабатывается способ оценки практической стойкости обфусцирующих преобразований программ, основанный на вычислении показателя похожести для исходной, обфусцированной и деобфусцированной программ. Предлагаются кандидаты для показателей похожести, в основе вычисления которых лежат такие характеристики программ, как граф потока управления, время символьного выполнения и степень покрытия при символьном выполнении. Граф потока управления рассматривается как основа для построения других кандидатов для показателей похожести программ. На его основе предлагается новый кандидат для показателя похожести, при вычислении которого находится расстояние Хэмминга между матрицами смежности графов потока управления сравниваемых программ. Строится схема оценки (анализа) стойкости обфусцирующих преобразований, в соответствии с которой для исходной, обфусцированной и деобфусцированной программ вычисляются или находятся характеристики этих программ, которые сравниваются в соответствии с выбранной моделью сравнения. Разработанная схема, в частности, подходит для сравнения программ на основе показателей похожести. В работе разрабатывается и реализуется один из ключевых блоков построенной схемы – блок получения характеристик программ, скомпилированных для архитектуры x86/x86_64. Разработанный блок позволяет находить граф потока управления, время символьного выполнения и степень покрытия при символьном выполнении. Приводятся некоторые результаты работы построенного блока.

 

332-350 206
Аннотация

В работе исследуется задача формальной верификации (математически строгой проверки правильности) диаграмм цифровых сигналов, используемых на практике на ранних стадиях разработки микроэлектронных цифровых устройств (цифровых схем). Отправной точкой разработки схемы, согласно современным методам проектирования, является её описание на каком-либо высокоабстрактном языке описания аппаратуры (hardware description language, HDL). Обязательным этапом разработки HDL-кода схемы является отладка этого кода, схожая по устройству и важности с отладкой программ. Один из популярных способов отладки HDL-кода основан на получении и проверке правильности диаграммы сигналов, то есть совокупности графиков сигналов: функций, описывающих изменение значений в выделенных местах схемы в реальном времени. В работе предлагаются математические средства автоматизации проверки правильности таких диаграмм, основанные на понятиях и методах верификации систем относительно формул темпоральных логик и учитывающие такие характерные особенности сигналов в HDL и соответствующих свойств правильности диаграмм в неформальном смысле, как реальное время, троичность и наличие точек фронтов. Троичность сигнала означает, что наряду с основными логическими значениями 0 и 1 сигнал может принимать и неопределённое значение: одно из значений 0 и 1, но неизвестно или неважно, какое именно. Точкой фронта называется момент изменения значения сигнала. В работе предлагаются понятия, утверждения и алгоритмы, предназначенные для формализации и решения задачи верификации диаграмм сигналов: определения сигналов и диаграмм, учитывающие упомянутые характерные особенности сигналов; темпоральная логика, предназначенная для описания свойств диаграмм сигналов, и соответствующая постановка задачи верификации диаграмм; метод решения предлагаемой задачи верификации, основанный на сведении к задачам преобразования и анализа сигналов; соответствующий алгоритм верификации диаграмм с обоснованием корректности и “приемлемой” оценкой сложности.

Computer System Organization

351-359 149
Аннотация

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

360-364 202
Аннотация

На основе анализа современных средств создания ИС GRID-типа, входящих в ставший европейским EGI-“стандартом” репозиторий UMD (включая новые версии Globus Toolkit, ARC, dCache и др.), кратко рассмотрено применение GRID-систем для задач вычислительной химии. Созданная авторами GRID-система объединяет два кластера с Linux CentOS 7 и базируется на программном обеспечении из UMD-4. Актуальность и эффективность применения систем пакетной обработки (у нас используется Torque 4.2.10) в квантовохимических расчетах повышается для массовых расчетов докинг-комплексов (в т.ч. для задач моделирования лекарств), для чего был предложен усовершенствованный полуэмпирический метод с более эффективными аппроксимациями, реализованный в программном комплексе LSSDOCK на Fortran-95. Для таких расчетов разработаны новые методы аппроксимаций, в т.ч. для функционалов DFT, и осуществляется их программная реализация. Разработаны конверторы результатов расчетов по LSSDOCK в естественный для GRID, основанный на XML, формат CML версии 3. С использованием CMLформата на базе программных средств dCache реализовано единое дерево виртуальной файловой GRID-системы, распределённой между гетерогенными узлами, которое используется для хранения результатов расчетов по LSSDOCK.

365-404 193
Аннотация

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

Algorithms

405-419 259
Аннотация

В данной статье рассматривается задача о двухшаговой раскраске произвольного неориентированного связного графа. Она состоит в нахождении такой раскраски в заданное число цветов, при которой ни одна пара вершин на расстоянии 1 или 2 друг от друга не будет окрашена в одинаковый цвет. Также в работе ставится соответствующая задача распознавания. Данная задача тесно связана с классической задачей о раскраске графа. В статье рассматривается и обосновывается полиномиальное сведение задач друг к другу. В частности, это позволяет доказать NP-полноту задачи о двухшаговой раскраске. Кроме того, определяются некоторые ее свойства. Отдельно исследуется задача о двухшаговой раскраске в приложении к прямоугольным графам решетки. Максимальная степень вершины таких графов может принимать значение от 0 до 4, и для каждого возможного случая была определена и обоснована функция двухшаговой раскраски в минимальное число цветов. Полученные функции строятся таким образом, что каждая вершина графа может быть раскрашена независимо от остальных, а время раскраски прямоугольного графа решетки полиномиально при последовательном переборе вершин.

420-440 217
Аннотация

Анализ функциональной эквивалентности перевода, основанный на достижении ритмической эквивалентности, представляет собой чрезвычайно важную задачу современной лингвистики. При этом ритмическая составляющая является неотъемлемой частью функциональной эквивалентности, которая не может быть достигнута без передачи ритмических характеристик текста. Для анализа ритмических средств в оригинальном тексте и переводе художественного произведения авторами был разработан программный инструмент ProseRhythmDetector, позволяющий находить и визуализировать лексические и синтаксические средства в англоязычных и русскоязычных прозаических текстах: анафору, эпифору, симплоку, анадиплозис, эпаналепсис, редупликацию, эпистрофу, многосоюзие и апозиопезу. Целью данной работы является представление результатов апробации ProseRhythmDetector на двух произведениях английских авторов и их переводах на русский язык: Ш. Бронте «Городок» (Ch. Bronte “Villette”) и А. Мердок «Черный принц» (I. Murdoch “The Black Prince”). На основе результатов работы инструмента авторы сопоставили ритмические характеристики в оригинале текста и его переводе и сравнили как аспекты ритма, так и их контексты. Данный эксперимент позволил выявить особенности передачи стиля автора художественного произведения переводчиком, обнаружить и объяснить случаи несовпадения ритмических средств оригинала и перевода. Применение программного инструмента ProseRhythmDetector позволило существенно сократить объем работы экспертов-лингвистов за счет автоматизированного выявления лексических и синтаксических средств с достаточно высокой точностью (от 62 % до 93 %) для различных ритмических средств.

Discrete mathematics in relation to computer science

441-449 197
Аннотация
Пусть \(n\in {\mathbb N}\), \(B_n\) - евклидов единичный шар в \({\mathbb R}^n\), задаваемый неравенством \(\|x\|\leq 1\), \(\|x\|:=\left(\sum\limits_{i=1}^n x_i^2\right)^{\frac{1}{2}}\). Под \(C(B_n)\) мы понимаем пространство непрерывных функций \(f:B_n\to{\mathbb R}\) с нормой \(\|f\|_{C(B_n)}:=\max\limits_{x\in B_n}|f(x)|\), под \(\Pi_1\left({\mathbb R}^n\right)\) - совокупность многочленов от \(n\) переменных степени \(\leq 1\), т.е. линейных функций на \({\mathbb R}^n\). Пусть \(x^{(1)}, \ldots, x^{(n+1)}\) - вершины \(n\)-мерного невырожденного симплекса \(S\subset B_n\). Интерполяционный проектор \(P:C(B_n)\to \Pi_1({\mathbb R}^n)\), соответствующий симплексу \(S\), определяется равенствами \(Pf\left(x^{(j)}\right)=f\left(x^{(j)}\right).\) Через \(\|P\|_{B_n}\) обозначим норму \(P\) как оператора из \(C(B_n)\) в \(C(B_n)\). Определим \(\theta_n(B_n)\) как минимальную величину \(\|P\|_{B_n}\) при условии \(x^{(j)}\in B_n\). Описывается подход, при котором норму проектора удаётся оценить снизу через объём симплекса. Пусть \(\chi_n(t):=\frac{1}{2^nn!}\left[ (t^2-1)^n \right] ^{(n)}\) - стандартизованный многочлен Лежандра степени \(n\). В статье доказывается неравенство \(\|P\|_{B_n}\geq\chi_n^{-1}\left(\frac{vol(B_n)}{vol(S)}\right).\) Из этой оценки выводится эквивалентность \(\theta_n(B_n)\) \(\asymp\) \(\sqrt{n}\). Даются оценки констант из неравенств отмеченного вида, а также сравнение с аналогичными соотношениями для линейной интерполяции на единичном \(n\)-мерном кубе \([0,1]^n\). Полученные результаты могут иметь приложения в полиномиальной интерполяции и вычислительной геометрии.
450-468 184
Аннотация

Анализ формы объекта – проблема, которая связана такими областями, как геометрия, топология, обработка изображений, машинное обучение или вычислительная анатомия. При анализе формы оценивается деформация между исходной и терминальной формой объекта. Наиболее используемой моделью анализа формы является модель диффеоморфного метрического отображения больших деформаций (Large Deformation Diffeomorphic Metric Mapping – LDDMM). Модель LDDMM может быть дополнена функциональной негеометрической информацией объектов (объем, цвет, момент времени формирования). В работе рассмотрены алгоритмы построения множеств баркодов для сравнения диффеоморфных изображений, которые являются вещественными значениями, принимаемыми персистентными гомологиями. Отличительной особенностью использования персистентных гомологий по отношению к методам алгебраической топологии является получение большего количества информации о форме объекта. Важным направлением применения персистентных гомологий является изучение инвариантов больших объемов данных. Предлагается метод, основанный на персистентных когомологиях, который объединяет технологии персистентных гомологий с внедренной негеометрической информацией, представленной в виде функций от симплициальных комплексов. Предлагаемая структура расширенных баркодов с использованием когомологий повышает эффективность методов персистентных гомологий. Предложена модификация метода Вассерштейна для нахождения расстояния между изображениями введением негеометрической информации. Рассмотрена возможность формирования баркодов изображений инвариантных к преобразованиям вращения, сдвига и подобия.



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


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)