Процессы управления и устойчивость

0

50

100

150

200

250

−4

−2

0

2

4

6

8

10

12

roll

0

50

100

150

200

250

−40

−30

−20

−10

0

10

20

rudder

Рис. 3. Два варианта управления с прогнозом T

p

= 50 сек

2. Алгоритмы с применением нелинейной прогнозирующей моде-

ли позволяют достичь цели управления с выполнением всех требо-

ваний по качеству динамики, но, являясь более сложными в реали-

зации, предъявляют повышенные требования к возможностям бор-

товой компьютерной техники.

3. Допустимое снижение уровня этих требований для реализации

алгоритмов управления с прогнозом обеспечивается уменьшением

размерности задачи нелинейного программирования, которая долж-

на решаться в режиме реального времени на каждом такте форми-

рования управления.

4. Одним из наиболее эффективных способов уменьшения раз-

мерности служит оптимальный выбор соотношения между величи-

нами шага прогноза и шага пересчета программного управления, ко-

торый использован в рассмотренном примере.

Литература

1. Веремей Е.И., Корчанов В.М., Коровкин М.В., Погожев С.В. Ком-

пьютерное моделирование систем управления движением морских

подвижных объектов. СПб.: НИИ Химии СПбГУ, 2002. 370 с.

2. Morari, M., Garcia, C.E., Lee, J.H. and Prett, D.M. Model Predictive

Control. Prentice Hall, New York, 1994.

3. Camacho E.F. and Bordons C. Model Predictive Control. Springer,

London, 1999.

439

Сущих Д.М.

Санкт-Петербургский государственный университет

Модель системы описания и анализа

вредоносного кода ресурсов Web

Рекомендовано к публикации ассистентом Севрюковым С.Ю.

1. Введение. Под вредоносным кодом в этой статье понима-

ется любой код, который, при выполнении в браузере, совершает

какие-либо действия, не предусмотренные пользователем. Напри-

мер: всплывающие окна с рекламой, несанкционированная отсылка

или приём данных с сервера, кроме тех, что запросил пользователь.

Задача: построение модели системы, позволяющей описать струк-

туру кода Web-ресурса с точки зрения его опасности. Цель рабо-

ты системы: анализ вероятности опасности для пользователя того

или иного ресурса. Требования: 1) адекватные результаты, понят-

ные пользователю; 2) скорость работы; 3) актуальность.

2. Деревья атак. Для решения задачи предлагается использо-

вать понятие деревьев атак (attack trees или risk trees) [1]. Деревья

атак представляют собой описание вариантов проведения атаки для

достижения некоторой цели, которая ставится во главу дерева атаки

(является его вершиной). Для каждого ресурса может быть опреде-

лено достаточно большое количество угроз. Каждый узел в дереве

представляет собой некоторую подцель, достижение которой, в слу-

чае выполнения ряда условий, позволяет считать, что этот участок

кода расценен как опасный, и нужно двигаться по дереву на более

высокий уровень, и так до тех пор, пока не достигнем вершины дере-

ва (конечной цели). В последнем случае считается, что код действи-

тельно опасен. Причём величина вероятности его опасности зависит

от ”веса” каждой из пройденных подцелей.

Узел дерева считается достигнутым, если:

1. Достигнуты все подцели этого узла (”и”-декомпозиция);

2. Достигнута хотя бы одна подцель этого узла (”или”-декомпози-

ция).

3. Построение модели. Так как любой скрипт, отображающий-

ся в браузере, лежит на прослойке HTML, то можно поставить его

на вершину дерева модели. Анализируя перечень возможных атак,

440

отметим в коде страницы те элементы, которые могут допускать с

той или иной степенью вероятности возможность атаки. Например:

JS, URL с параметрами, cookies, SQL-запросы, элементы форм и т.д.

В рамках модели системы предлагается рассмотреть лишь несколько

путей развития атак, которые наиболее полно отразили бы концеп-

цию модели.

Рассмотрим элемент JS. Сам по себе элемент JavaScript безвре-

ден, однако его методы и функции могут инициировать различные

процессы, угрожающие безопасности системы пользователя. С одной

стороны, это может быть метод open(); объекта Window, который от-

крывает новое окно (например, с рекламой), а с другой стороны, это

может быть сочетание PHP и XMLHttpRequest, который указыва-

ет на возможность атаки по технологии AJAX. На уровне метода

open(); и AJAX имеет место ”или”-декомпозиция, так как выполне-

ние любого из условий означает успешность прохождения данного

узла, а на уровне PHP и XMLHttpRequest – ”и”-декомпозиция, так

как необходимо выполнение обоих условий. С другой стороны, са-

мо появление PHP-кода означает присутствие некоторого серверно-

го сценария, который, с большой долей вероятности, получает дан-

ные от пользователя, отправляет их на сервер и присылает какую-то

информацию обратно. Очевидно, что на этом пути информация мо-

жет подвергнуться множеству атак. Если же используются запросы

к базе данных MySQL, то существует возможность несанкциониро-

ванного изменения данных в ней.

Таким образом, получается, что по сути один и тот же элемент

PHP встречается в разных ветках дерева. Поэтому необходимо вве-

сти некоторую индексацию узлов дерева.

Стоит обратить внимание на тот факт, что различные узлы-

угрозы имеют разный ”вес”, т.е. величина вероятности опасности

узлов различна. Это касается и узлов, расположенных на одном

уровне. Предлагается учитывать следующие факторы для оценки

веса того или иного элемента:

• частота. Узел-элемент form встречается почти на всех ресурсах

и в больших количествах, так как обеспечивает пользователю

минимальные возможности работы с сервером. Следовательно,

вес этого элемента с выбранной точки зрения мал;

• опасность. С другой стороны, узел form выполняет весьма важ-

ную функцию по отправке данных, введённых пользователем

441

на сервер. Эта операция может подвергаться множеству видов

атак. С этой точки зрения узел form имеет большой вес.

Для каждого узла нужно находить свой компромисс между часто-

той/опасностью. Очевидно, что нет нужды расставлять вес для всех

элементов (HTML, JS сами по себе не имеют веса, так как встре-

чаются практически везде), однако, учитывая существование ”и”-

декомпозиций, вариант с расставлением веса только конечным ли-

стьям неприемлим.

4. Работа системы. Дерево атак подразумевает следующий ана-

лиз кода страницы. Если парсер будет сравнивать каждое слово

на странице со списком всех возможных рискованных выражений,

то быстродействие будет неудовлетворительным. Поэтому стоит ис-

пользовать анализ по уровням, опускаясь к корню дерева. Система

начинает работать с вершины дерева и двигается до концов ветвей.

Программа анализатора ищет в тексте элемент и сохраняет в таб-

лице базы данных информацию о том, найден элемент или нет. Если

элемент не найден, то отсекается вся его подветвь. При этом для

каждого элемента проверяется его участие в ”и/или”-декомпозиции.

Проверка идет по всему уровню. После того, как проверен последний

элемент на уровне, на основании данных из таблицы составляется

дерево (или деревья), в вершинах которых стоят элементы, находя-

щиеся на уровень ниже совпавших. Вес тех ветвей исходного дерева,

которые пройдены до конца, суммируется и, вместе с информацией

о них, выдается пользователю.

5. Заключение. Реальная система должна быть огромна по мас-

штабу, так как существует множество путей для атак. Как следствие,

она требует постоянного пополнения данных о комбинациях кода,

делающих его вредоносным. Однако, при четкой формализации и

грамотном написании всех модулей системы, основанной на описан-

ной модели, можно добиться выполнения требований перечисленных

в начала статьи.

Литература

1. Полаженко С. Деревья атак и их применение при ана-

лизе проблемы безопасности и защищенности программных

продуктов. http://www.software-testing.ru/lib/polazhenko/attack-

trees-security-testing.htm

442

Татауров В.А.

Санкт-Петербургский государственный университет

О распараллеливании

быстрых преобразований Фурье

1

Рекомендовано к публикации профессором Демьяновичем Ю.К.

1. Введение. Дискретное преобразование Фурье (ДПФ) широ-

ко применяется при анализе дискретных сигналов для выделения

из них информативной части. Подобная обработка необходима при

передаче аудио- и видео-сигналов, а также при анализе топографи-

ческой информации и т.п. Ввиду больших объёмов подобной инфор-

мации были разработаны быстрые методы ее обработки.

Преобразование Фурье вектора v имеет вид

V

k

=

n−1

i=0

w

ik

v

i

,

где v

i

– компоненты исходного вектора, n – его размерность, w –

примитивный корень n-й степени из единицы, требует n

2

умножений

и n(n−1) сложений. Однако известны последовательные алгоритмы,

требующие для своего выполнения порядка nlog

2

n арифметических

операций.

В данной статье рассматривается задача разработки параллель-

ной формы алгоритма быстрого дискретного преобразования Фурье,

который должен удовлетворять следующим требованиям:

• число последовательных арифметических операций при выпол-

нении на q-процессорной системе по сравнению с последова-

тельным алгоритмом должно быть меньше в q раз;

• межпроцессорное взаимодействие, замедляющее работу систем

с распределённой памятью, должно быть минимальным.

В данной работе предлагается алгоритм для 2

p

-процессорной си-

стемы, производительность которого близка к оптимальной; также

рассматриваются различные сложности, которые могут возникнуть

1

Работа выполнена при финансовой поддержке РФФИ (гранты № 04-01-00692

и 04-01-00026)

443

при реализации алгоритма на конкретной многопроцессорной систе-

ме.

2. Алгоритм быстрого преобразования Фурье. В дальней-

шем будем считать, что n = 2

k

, в противном случае дополним ис-

ходный вектор нулями. В работе используется алгоритм быстрого

преобразования Фурье (БПФ), описанный Кули и Тьюки. Этот ал-

горитм подробно описан, например, в [1].

Указанный алгоритм основан на том, что вычисление преобразо-

вания Фурье эквивалентно вычислению остатков от деления много-

члена P (x) =

n−1

i=0

a

i

x

i

на биномы (x − w

j

), j = 0, . . . , n − 1. Данные

биномы перемножают попарно, после чего получаются одночлены

вида x

j

− c, и вычисление БПФ сводится к вычислению последова-

тельности остатков от деления полинома P (x) на одночлены вида

x

j

− c.

Определение. Пусть j – целое число, 0 ≤ j < 2

k

, а [d

k−1

, . . . , d

0

]

– его двоичное представление. Инверсией числа j будем называть

целое число rev

k

(j) с двоичным представлением [d

0

, . . . , d

k−1

].

Последовательный алгоритм БПФ, требующий порядка nlog

2

n

арифметических операций, можно описать следующим образом.

Вход. Вектор a = (a

0

, . . . , a

n−1

), n = 2

k

, k – целое.

Выход. Вектор F (a) = (b

0

, . . . , b

n−1

), b

i

=

n−1

j=0

a

j

w

ij

, 0 ≤ i < n.

begin

(1)

r

0,k

=

n−1

j=0

a

j

x

j

{данные на входе, никаких вычислений не производится }

(2)

for m:=k-1 step -1 until 0 do

(3)

for l:=0 step 2

m+1

until n-1 do

begin

(4)

r

l,m+1

(x) :=

2

m+1

−1

j=0

a

j

x

j

;

{данные для цикла, вычислений не производится;

a

j

- изменяемые переменные;}

(5)

s := rev

k

(l/2

m

);

(6)

r

l,m

(x) :=

2

m

−1

j=0

(a

j

+ w

s

a

j+2

m

)x

j

;

(7)

r

l+2

m

,m

(x) :=

2

m

−1

j=0

(a

j

+ w

s+n/2

a

j+2

m

)x

j

;

end;

(8)

for l:= 0 step 1 until n - 1 do

b

rev

k

(l)

:= r

l,0

;

end;

444

Замечание 1. Строки 5 и 8 алгоритма требуют порядка n∗log

2

n

арифметических операций деления на 2.

Замечание 2. Строки 5 и 8 алгоритма можно освободить от

арифметических операций.

Доказательство. Таблицу rev

k

(j) следует получить заранее. В

этом случае можно считать, что строки 5 и 8 алгоритма БПФ не

содержат арифметических операций.

Заранее получим также таблицу степеней корней из единицы

w

0

, . . . , w

n−1

, обозначим эту таблицу W [j]. Составим эту таблицу та-

ким образом, что в ней на j-м месте располагается w

rev

k

(j)

.

Для составления таблицы потребуется число умножений M , ко-

торое, очевидно, оценивается сверху числом n: M ≤ n.

Замечание 3. Для составления таблиц из w

j

и rev

k

(j) на систе-

ме с 2

p

процессорами понадобится не больше (n/2

p

+ k) операций

умножения и n ∗ log

2

n/2

p

операций деления на 2.

Таким образом, время, затраченное на составление указанных

таблиц на многопроцессорной системе, мало по сравнению с време-

нем работы самого алгоритма.

Теорема 1. Все арифметические операции в алгоритме заклю-

чены в строках (6) и (7) и сводятся к вычислению остатков r

l,m

.

Замечание 4. Для вычисления сумм, указанных в строках (6)

и (7) алгоритма, на каждом шаге требуется 2

m

умножений и вдвое

больше сложений, так как w

s

= −w

s+n/2

.

Замечание 5. Если не учитывать операции, требуемые для со-

ставления таблиц из w

j

и rev

k

(j), для вычисления БПФ потребуется

n ∗ log

2

n сложений и n ∗ log

2

n/2 умножений.

3. Возможности распараллеливания алгоритма БПФ. Ис-

следуем структуру предлагаемого последовательного алгоритма и

выявим места потенциального параллелизма.

3.1. Параллельное выполнение внешнего цикла (2). Для

начала рассмотрим алгоритм, развёрнутый по итерациям внешнего

цикла (2):

(2) for m:=k - 1 step -1 until 0 do

{вычисляются остатки r

l,m

по коэффициентам остатков r

l,m+1

и таблице W }

В соответствии с алгоритмом можно нарисовать бинарное дерево

вычисляемых остатков (рис. 1), на котором показано, коэффициенты

каких остатков предыдущего уровня используются для вычисления

445

коэффициентов остатков следующего уровня. Здесь каждый уровень

соответствует итерации цикла (2).

Рис. 1. Вычисление r

l,m

для k = 3

Рис. 1 хорошо от-

ражает порядок ис-

пользования корней из

единицы в вычислени-

ях. Каждый блок на

рисунке – это оста-

ток r

l,m

. Порядковый

номер этого блока в

строке – номер перво-

образного корня в таб-

лице W [j], который используется для вычисления остатков следую-

щего уровня.

Представленная схема вычислений хорошо подходит для распа-

раллеливания. На первом шаге можно использовать один процессор,

на 2-м шаге – два независимо работающих процессора, на 3-м – че-

тыре и т.д.

Теорема 2. Существует алгоритм, работающий на 2

p

-процессор-

ной системе, для выполнения которого потребуется количество

умножений, равное 2

k

+ (k − p − 2) ∗ 2

(

k − p − 1) = n + (log

2

n −

p − 2) ∗ (n/2

p+1

), и вдвое больше сложений.

Оценим полноту использования вычислительных возможностей

дополнительных процессоров. В оптимальном случае, при полной за-

груженности всех 2

p

процессоров, получим ускорение по операциям

в 2

p

раз по сравнению с однопроцессорной системой. Таким образом,

понадобится k ∗ 2

k−p−1

последовательных операций умножения.

Зафиксируем размерность входного вектора, пусть k = 100,

n = 2

100

. Тогда эффективность использования дополнительных про-

цессоров при данной организации вычислений указана в таблице 1.

Таблица 1. Эффективность использования процессоров

p=1

0,99

p=3

0,97

p=6

0,45

p=10

0,05

В данной схеме распараллеливания также велико число межпро-

цессорных коммуникаций: на каждом из p первых шагов алгоритма

446

нужно передавать количество информации, равное n/2, что суще-

ственно скажется на производительности многопроцессорных систем

с распределённой памятью.

3.2. Параллельное вычисление остатков. Вторая возмож-

ность потенциального параллелизма кроется в вычислении остатков

r

l,m

, которое производится в строках (6) и (7) исходного алгоритма:

(6)

r

l,m

(x) :=

2

m

−1

j=0

(a

j

+ w

s

a

j+2

m

)x

j

;

(7)

r

l+2

m

,m

(x) :=

2

m

−1

j=0

(a

j

+ w

s+n/2

a

j+2

m

)x

j

;

Рис. 2. Вычисление остатков r

0,2

и r

4,2

по

коэффициентам остатка r

0,3

Как видно из рис. 2,

для вычисления пары

коэффициентов a

j

и

a

j+2

m

требуются толь-

ко коэффициенты с

такими же номерами

из остатка предыду-

щего уровня. Таким

образом, можно эф-

фективно распаралле-

лить вычисление ос-

татков.

Теорема 3. На 2

p

-процессорной системе можно распараллелить

вычисление остатков r

l,m

и r

l+2

m

,m

так, что алгоритм будет де-

лать 2

m−p

последовательных умножения и 2

m−p+1

последователь-

ных сложения.

Теорема имеет смысл при предположении, что p ≤ 2

m

.

4. Параллельная форма алгоритма. Объединим предложен-

ные выше подходы для получения параллельной формы алгоритма

БПФ, максимально использующей вычислительные мощности выде-

ленных процессоров при минимальном межпроцессорном взаимодей-

ствии.

Массив коэффициентов a

j

можно распределить на несколько

групп так, что до определённого момента будет соблюдаться локаль-

ность вычислений, поскольку нет обмена данными между группами.

Теорема 4. Для любого p ≤ k можно распределить коэффици-

енты a

j

на 2

p

групп таким образом, что в течении первых (k − p)

итераций цикла (2) будет соблюдаться локальность вычислений

внутри каждой группы.

447

Доказательство. Данное разбиение следующее: в группе с но-

мером T содержатся коэффициенты a[T +q ∗2

p

], q = 0, 1, . . . , 2

k−p

−1.

Замечание 6. При таком распределении коэффициентов по про-

цессорам, на каждом из 2

p

процессоров будет вычисляться преобра-

жүктеу/скачать 30,48 Mb.

Достарыңызбен бөлісу: