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

тров, аналогичных маскам морфологических помет, но их логи-

ческие функции определены на объединенном множестве морфо-

логических помет, окончаний сокращённой парадигмы, словоформ

сокращённой парадигмы, словоформ полной парадигмы и лексем.

Например, для лексемы ЛЮБИТЬ морфологический описатель

@Прич.Страд.Наст.> будет присвоен словоформам полной пара-

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

ется на ∗Y , т.е. ЛЮБИМЫЙ, ЛЮБИМАЯ, ЛЮБИМОЕ, . . . Для

лексемы

ПРИЛЕЧЬ

морфологический

описатель

@Прош.Ед.Муж. получит словоформа ПРИЛЕГ-, но не слово-

форма ПРИЛЯГ- ещё и потому, что морфологическая помета дан-

ной лексемы – г8сН’1.

Метод представления флексий может также применяться при

морфологическом анализе других синтетических языков (флективно-

фузионных и агглютинативных), таких как финский, эстонский, ту-

рецкий, венгерский, украинский и т.д.

1.2. Обратная задача. Обратная задача применяется на

практике гораздо чаще, чем прямая. Её результаты используются

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

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

при семантическом анализе [2] и т.д. Для решения обратной задачи

применяется словарь всех основ. БНФ статьи этого словаря имеет

вид:

<статья основы> :: = <основа> { [<окончания>]

<модификатор лексемы>

<морфологическая помета> }*

<окончания> ::= {<окончание>}*

Например, для основы ЛЮБ статья выглядит так:

ЛЮБ 0 п1&- а о ы 0А ж1о – ам ами ах е ой ою у ы

0ИТЬ г4н ишь ит им ите ят и ите я ящJ имY

0ОЙ МП#

Лексемы ЛЮБ, ЛЮБА, ЛЮБИТЬ, ЛЮБОЙ строятся с по-

мощью основы и соответствующих модификаторов лексем с приме-

нением описанного выше алгоритма для построения основ. В каче-

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

вого словаря для соответствующих основ. Общий алгоритм анализа

следующий:

406

1. Если в словаре содержится основа, равная искомому слову,

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

перейти ко второму этапу прямой задачи. Выход;

2. n = 1;

3. Оторвать от исходного слова n последних букв;

4. Если в словаре содержится основа, равная слову, и среди окон-

чаний этой основы содержится окончание, равное n оторван-

ным буквам, взять основу плюс окончание в качестве слово-

формы сокращённой парадигмы и перейти ко второму этапу

прямой задачи;

5. n = n + 1;

6. Если n равно длине слова, то выход. Иначе перейти к п. 3.

2. Представление и анализ составных слов. Составны-

ми словами называются такие словоформы, в состав которых вхо-

дят неалфавитные символы. В русском языке это дефис. Под дан-

ную категорию попадают неопределённые местоимения и наре-

чия: куда-нибудь, где-то, кто-либо, кое-кто и т.д. Составные суще-

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

-максимум, Тянь-Шань и т.д. Составные прилагательные: сине-

-голубой, красно-зелёно-фиолетовый, кирпично-деревянный и т.д.

Все составные слова можно условно разделить на четыре типа:

1. В первом типе ни одно из составляющих слов, входящих в со-

ставное слово, не изменяется по формам;

2. Во втором типе по формам изменяется только последнее слово;

3. В третьем – по формам изменяется одно из входящих слов, но

не последнее;

4. В четвёртом типе по формам изменяются все слова, входящие

в состав составного слова.

Составные слова первого и второго типов вносятся в морфологи-

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

КУДА-НИБУДЬ НР

ГУЛЯЙ-ГОРОД м1|1- а у ом е

ГАЗО-ДВИГАТЕЛЬНЫЙ п1 ая ое ого ой ому ую ом

ою ые ых ым ыми ее ей 2ЕН - 2ЬН а о ы

Составные слова третьего типа представляются в словаре в виде

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

407

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

вид:

ПРОГРАММА*-МАКСИМУМ ж1 ы е у ой ою - ам ами ах

Основа, строящаяся по данной статье, совпадает с основой для

слова программа. При реализации обратной задачи для поиска ос-

нований составных слов третьего типа нужно наложить условие на

совпадение неизменяемых частей слова с соответствующими частя-

ми лексемы.

К четвёртому типу принадлежит самая многочисленная группа

составных слов, и в словарь вносятся только их лексемы с морфоло-

гической пометой, например:

АВТОМОБИЛЬ-ФУРГОН м2

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

в состав слова (например, для словоформы автомобиля-фургона

сначала анализируются слова автомобиля и фургона), а затем они

согласовываются по падежу и числу. Морфологический описатель

таких слов ищется по морфологической помете лексемы составного

слова.

Заключение. В статье были рассмотрены прямая и обратная

задачи морфологического анализа для русского языка; метод пред-

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

нии морфологических анализаторов для языков со структурой сло-

воизменения, схожей с русской; представление составных слов рус-

ского языка в морфологическом словаре и их анализ.

Литература

1. Зализняк А.А. Грамматический словарь русского языка: Слово-

изменение. 3-е изд. М., 1987. 880 с.

2. Тузов В.А. Компьютерная семантика русского языка. СПб.: Изд-

во СПбГУ, 2004. 400 с.

408

Подласов А.С., Фрянти П.

Университет Йоэнсуу, Финляндия

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

сжатия палитровых изображений

Алгоритм сжатия палитровых изображений, предложенный Че-

ном [1], помимо эффективной компрессии предоставляет возмож-

ность прогрессивной передачи сжатых данных. Изображение деко-

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

щих вплоть до полной реконструкции. В данной работе предложены

два улучшения алгоритма Чена. Производительность улучшенного

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

Представлены сравнения с оригинальным алгоритмом и со стандарт-

ным алгоритмом сжатия без потерь PNG.

1. Исходный алгоритм. Алгоритм Чена состоит из двух эта-

пов. На первом этапе цветовая палитра изображения представляется

в виде бинарного дерева. На втором этапе исходное изображение ко-

дируется в соответствии с построенным деревом.

1.1. Построение бинарного дерева. Обозначим цветовую

палитру

изображения

как

множество

RGB

триплетов

C = {c

1

, . . . , c

M

}, где M – число цветов. Пусть S

0

= {1, . . . , M } –

множество индексов, идентифицирующих цвета в палитре, индекс i

соответствует цвету c

i

. Число пикселей цвета c

i

обозначим p

i

. Пред-

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

каждому узлу j сопоставлено множество цветов C

j

и множество ин-

дексов s

j

. Множеству C

j

сопоставлен репрезентативный цвет q

j

,

заданный как взвешенная сумма всех цветов множества s

j

.

Корень дерева соответствует всей цветовой палитре C. Дерево

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

цветов которого C

j

содержит более одного элемента, разбивается на

два потомка l и r таким образом, что множества C

l

и C

r

лежат

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

правлению данных множества C

j

и проходящей через q

j

. Главное

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

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

ковариации

A

j

=

i∈s

j

(c

i

c

t

i

− q

i

q

t

i

).

409

В итоге каждый лист дерева ассоциируется с одним цветом из

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

нарная последовательность переменной длины, представляющая со-

бой путь в дереве. Первые биты последовательности соответствуют

наиболее значимой цветовой информации. Близкие цвета получают

близкие индексы – таким образом корреляция цветов преобразуется

в корреляцию индексов палитры.

1.2. Прогрессивное кодирование. Кодирование изображе-

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

тативный цвет q

0

. Затем применяется следующий алгоритм:

1. Выбрать узел m дерева с максимальным по модулю собствен-

ным значением матрицы C

m

;

2. Передать декодеру индекс узла и репрезентативные цвета двух

его потомков q

l

m

и q

r

m

;

3. Закодировать местоположение пикселей, цвета которых при-

надлежат множествам s

l

m

и s

r

m

, s

m

= s

l

m

∪ s

r

m

.

Местоположение пикселей кодируется контекстным арифметиче-

ским кодером (context-based arithmetic coder) [2]. Для построения

контекстов алгоритм Чена использует фиксированный 8-пиксельный

шаблон (см. рис. 1, левый шаблон). Местоположение пикселей, чьи

?

1

5

4

2

3

7

6

8

?

1

4

2

3

7

6

10

8

9

11

5

Рис. 1. Контекстные шаблоны: используемый в алгоритме Чена (слева) и

пример оптимизированного шаблона, построенного свободным деревом (справа)

цвета принадлежат множеству s

m

, уже известно декодеру (передано

на предыдущем шаге). Следовательно, для каждого из этих пикселей

необходимо закодировать принадлежность к одному из множеств s

l

m

или s

r

m

. Поэтому для каждого пиксела, чей цвет q ∈ s

m

, кодируется

бит b

0

, заданный как

b

0

=

0, q ∈ s

l

m

,

1, q ∈ s

r

m

.

410

Пиксели b

i

, формирующие контекст кодирования, задаются как

b

i

=

0,

q

i

− q

l

m

≤ q

i

− q

r

m

,

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

где q

i

– цвет пиксела декодированного изображения на позиции i

контекстного шаблона. В результате изображение кодируется после-

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

дом шаге алгоритма, начиная с наиболее значимых составляющих –

так называемое прогрессивное кодирование (см. рис. 2).

Рис. 2. Пример цветовой прогрессии, полученной построением дерева снизу

вверх. Три первых шага алгоритма.

2. Предложенные улучшения. Алгоритм Чена предполага-

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

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

ной работе предложено построение дерева снизу вверх, основанное

на простом и эффективном алгоритме поиска ближайших соседей.

Предложенный метод демонстрирует более точное приближение цве-

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

сии. Кроме этого, применен метод свободного дерева (free tree) [3] для

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

достичь более эффективного сжатия.

2.1. Построение дерева снизу вверх. Предложенный нами

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

применения операции слияния. Изначально каждый цвет c

i

ассоции-

руется с отдельным листом дерева. На каждом шаге алгоритма объ-

единяются два узла дерева – им сопоставляется узел-родитель, чье

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

ются таким образом, чтобы их объединение вызывало минимальное

411

искажение полученной (уменьшенной) цветовой палитры. Искаже-

ние d

ij

, вызванное слиянием узлов i и j, вычисляется как

d

ij

=

n

i

n

j

n

i

+ n

j

q

i

− q

j

2

,

где q

i

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

i

и n

i

– число пиксе-

лей, чьи цвета принадлежат s

i

. Величины q

j

, n

j

заданы аналогично.

Процесс слияния продолжается до тех пор, пока не остается один

узел – корень дерева, цветовому множеству которого принадлежат

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

2.2. Контекстное моделирование методом „свободного

дерева“. Контекстное дерево (context tree) – это вид контекстного

моделирования, в котором хранение информации о контекстах орга-

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

позволяет выделять память только для контекстов, действительно

присутствующих в кодируемом изображении, и делает возможным

использование контекстов большего размера. Моделирование „сво-

бодным деревом“ является вариантом контекстного дерева, позво-

ляющим оптимизировать не только размер, но и форму используе-

мых контекстов (см. рис. 1, правый шаблон). На каждом шаге по-

строения шаблона алгоритм анализирует все возможные позиции те-

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

эффективность сжатия. Построение завершается, когда дальнейшее

увеличение его размера не приводит к повышению эффективности.

Недостатком алгоритма является необходимость передать по-

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

ли. Помимо этого, построение методом „свободного дерева“ является

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

3. Исследование эффективности. Эффективность предло-

женного алгоритма (PF) исследована на 12 тестовых палитровых

изображениях. Результаты сравнения с оригинальным алгоритмом

и со стандартным алгоритмом сжатия без потерь PNG представле-

ны в таблице 1. Предложенный алгоритм превосходит оригинальный

алгоритм Чена на 17,5% и PNG на 68,2%.

412

Таблица 1. Результаты сжатия тестовых изображений алгоритмами PNG,

алгоритмом Чена (Chen) и предложенным алгоритмом (PF), байт.

Изображение

PNG

Chen

PF

pc

360291

135051

91220

books

20754

8102

7950

music

2800

830

814

winaw

33182

13046

11366

party8

10140

3341

2933

netscape

40546

11176

11146

sea_dusk

2712

1497

1128

benjerry

6239

2847

2921

gate

47446

15329

15057

descent

39738

17911

17157

sunset

136966

59806

58335

yahoo

11912

5764

6442

Всего

712726

274700

226469

4. Заключение. Предложены две модификации алгоритма сжа-

тия Чена: построение бинарного представления палитры „снизу

вверх“ и контекстное моделирование методом „свободного дерева“.

Эти модификации позволяют улучшить эффективность алгоритма

на 17,5% по сравнению с исходным алгоритмом. Предложеный алго-

ритм превосходит стандартный алгоритм PNG на 68,2%.

Литература

1. Chen X., Kwong S., Feng J.-F. A new compression scheme for color-

quantized images // IEEE Trans. on Circuits and Systems for Video

Technology, 2002. V. 12, № 10. Р. 904–908.

2. Witten I., Near R. Cleary J., Arithmetic coding for data compression

// Communications ACM, 1987. V. 30. P. 520–539.

3. Martins B., Forchhammer S. Bi-level image compression with tree

coding // IEEE Trans. on Image Processing. 1998. V. 7, № 4.

P. 517–528.

413

Русаков В.Е.

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

Современные методы перехвата

API-функций в ОС Windows

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

1. Введение. В современном обществе активно используются

компьютерные технологии. В связи с постоянным расширением об-

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

является вопрос защищенности и неприкосновенности информации.

Существует множество программных продуктов, которые обеспечи-

вают безопасность данных. Это антивирусные продукты, брэндмау-

эры, системы шифрования и т.д. Цель данной статьи – показать воз-

можные методы, которые сильно облегчат труд анализа сложных

вирусов.

Существуют методы, которые позволяют перехватывать фукн-

ции операционной системы (ОС) [1]. Этими методами пользуются не

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

тив некоторые функции ОС, можно оставаться в системе практиче-

ски незаметным. Однако, эту технологию можно использовать и во

благо.

2. Перехват функций на пользовательском уровне.

Windows NT полностью построена на системе DLL (динамически

загружаемых библиотек) [2–4]. ОС предоставляет приложениям до-

ступ к системным API-функциям. С их помощью приложения взаи-

модействуют с системой. API-функции представляют собой переход-

ники к функциям ядра (Native API). Для того, чтобы приложение

могло использовать API-функции, оно должно их импортировать.

Когда приложение вызывает некоторую функцию, оно обращается

в свою таблицу импорта (Import Address Table). В данной табли-

це хранятся адреса всех функций, используемых приложением. До-

пустим, что приложение использует функцию CreateFile, экспорти-

руемую динамической библиотекой Kernel32.dll. Во время загрузки

приложения в память настраиваются его импорты и в таблицу поме-

щается адрес CreateFile в Kernel32.dll, которая находится в памяти.

При обращении к этой функции происходит перенаправление вызова

414

в динамическую библиотеку. Далее вызов функции перенаправляет-

ся в ядро ОС.

2.1. Подмена таблиц импорта. Простейшим методом пере-

хвата функций в пользовательском пространстве является перехват

таблиц импорта. Необходимо разобрать формат исполняемого PE-

файла и найти в нем IAT. Далее, необходимо найти точку входа

перехватываемой функции и заменить ее адрес в IAT на наш обра-

ботчик. Данный метод обладает рядом недостатков, а именно, его

очень просто обнаружить. Также можно получить адрес вызывае-

мой функции в обход IAT вызовом GetProcAddress из Kernel32.dll.

2.2. Сплайсинг функции. Данный метод состоит в следу-

ющем: необходимо определить адрес перехватываемой функции и

первые 5 байт функции заменить на длинный прыжок в наш об-

работчик. Если после того, как отработал наш обработчик нужно

вызвать оригинальную функцию, то необходимо восстановить за-

мененные байты и передать управление оригинальной функции. У

данного метода тоже есть недостатки. Один из них состоит в том,

что если после восстановления функции произошло переключение

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

звать функцию, минуя наш перехватчик. Данная проблема, однако,

разрешима. Можно, например, останавливать все побочные потоки

приложения перед вызовом и запускать после вызова. Кроме это-

го, есть еще недостатки этого метода, один из которых состоит в

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

образ DLL в памяти с образом DLL на диске, или же реализовать

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

инструкций функции.

2.3. Внедрение кода в исполняемый процесс. Существует

несколько методов внедрения динамической библиотеки в процесс.

Первый состоит в том, чтобы использовать параметр реестра ОС:

HKLM\Software\Microsoft\Windows NT\CurrentVersion\Windows\

AppInit_DLLs.

В данном ключе нужно указать имя и путь к DLL. Когда старту-

ет приложение, использующее User32.dll, динамическая библиотека,

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

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

ку, используя функцию SetWindowsHookEx. Эти два метода здесь

рассматриваться не будут, так как они устарели и мало где находят

415

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

ленные потоки. Для данной техники необходимо описание функции

CreateRemoteThread. Ее прототип выглядит следующим образом:

HANDLE CreateRemoteThread(HANDLE hProcess,

LPSECURITY_ATTRIBUTES lpThreadAttributes,

SIZE_T dwStackSize,

LPTHREAD_START_ROUTINE lpStartAddress,

LPVOID lpParameter,

DWORD dwCreationFlags,

LPDWORD lpThreadId);

Первый параметр – это дескриптор процесса, в который необходи-

мо внедрить библиотеку. Чтобы его получить, необходимо использо-

вать функцию OpenProcess. Ей надо указать PID (Process Identifier)

процесса. Эта функция как раз и вернет дескриптор процесса. Вто-

рой и седьмой параметры необходимо установить в NULL, а тре-

тий и шестой – в 0. Остались лишь два параметра, на которые и

надо обратить внимание – это четвертый (lpStartAddress) и пятый

(lpParameter). Четвертый параметр должен быть равен адресу функ-

ции LoadLibrary в текущем процессе. Чтобы получить адрес, нужно

воспользоваться функцией GetProcAddress. Последний пятый пара-

метр – это адрес в памяти аргумента, который будет передан функ-

ции LoadLibrary. В нем необходимо передать строку, которая указы-

вает на нашу библиотеку, внедряемую в процесс. В целевом процессе

необходимо выделить память с помощью функции VirtualAllocEx и

записать имя нашей библиотеки в это пространство, используя функ-

цию WriteProcessMemory. После того как в процесс будет загружена

DLL, можно начинать перехватывать функции методом сплайсинга

или методом подмены таблицы импорта.

3. Перехват функций на уровне ядра. Как видно из преды-

дущего раздела, перехват в пользовательском пространстве доста-

точно легко обнаружить и обезвредить. Более элегантным решением

является установка перехвата на уровне ядра. Из пользовательского

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

Исключением является процесс, имеющий привилегии отладчика,

использующий некоторые специальные функции. Для наших целей

вполне подходит реализация в виде системного драйвера. Ядро как

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

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

416

3.1. Перехват функций в SSDT. Исполнительная часть

Windows, работающая в режиме ядра, предоставляет системные

функции. Адреса этих функций содержатся в системной таблице

System Service Dispatch Table (SSDT). Другая таблица System Service

Parameter Table (SSPT) – таблица, содержащая количество байт, ко-

торые

занимают

параметры

каждой

функции.

KeServiceDescriptorTable экспортируется ядром ОС. Чтобы вызвать

определенную функцию ядра, системный диспетчер KiSystemService

берет номер нужной функции, умножает его на 4 и получает смеще-

ние в SSDT. В системе также существует еще одна системная таб-

лица KeServiceDescriptorTableShadow, содержащая адреса сервисов

USER и GDI, реализованных в драйвере Win32k.sys. Системный дис-

петчер срабатывает при вызове инструкций INT 2E или SYSENTER.

Подменой адреса в SSDT можно перехватить любую экспортируе-

мую ядром функцию. Достоинствами данного метода являются ско-

рость и простота исполнения. Однако, у метода есть и недостатки,

так как этот метод перехвата можно достаточно легко обнаружить

существующими стредствами. Кроме того, не все функции пользо-

вательского уровня реализованы на уровне ядра.

3.2. Перехват с использованием таблицы дескрипторов

прерываний. Interrupt Descriptor Table (IDT) служит для обслу-

живания прерываний. Прерывания могут происходить как от про-

граммного обеспечения, так и от аппаратного. Как показано выше,

доступ к SSDT запрашивается прерыванием INT 2E. Поэтому, если

установить перехват на это прерывание, то оно будет срабатывать

еще до входа в таблицу. Однако, необходимо помнить, что каждый

процессор имеет свою IDT. Перехват одной таблицы прерываний на

мультипроцессорной системе совершенно бесполезен. С помощью ин-

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

процессора. Сохраняя настоящий обработчик прерывания INT 2E и

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

пример, собрать информацию со стека и вернуть управление ориги-

нальному обработчику.

4. "Гибридные" методы перехвата функций. Как видно

из предыдущих разделов, каждый из методов перехвата функций

обладает своими достоинствами и недостатками. Однако, можно по-

пробовать устранить недостатки и оставить достоинства. Чем долж-

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

417

няемые файлы быстро и эффективно? Во-первых, система должна

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

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

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

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

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

вательском уровне. Выход – перехват методом подмены IAT. Одна-

ко, этот метод, как было замечено выше, имеет ряд недостатков, а

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

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

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

Рис. 1. Вызов функции

CreateFile

4.1. Перехват методом подме-

ны таблиц экспорта. Для того, что-

бы перехватить API-функции физиче-

ски, необходимо найти каждую экспор-

тируемую функцию и ее адрес в табли-

це экспорта заменить на адрес нашего

обработчика. Допустим, что надо пере-

хватить функцию CreateFile и ее пара-

метры, а также возвращаемое значение.

Находим в библиотеке Kernel32.dll ад-

рес экспортируемой функции. Добавля-

ем новую секцию в DLL. В этой секции

будут находиться все обработчики всех

перехватываемых функций в виде:

MOV EAX, n

MOV EDX, m

INT FF

где n – номер динамической библиотеки в специальной таблице, а

m – номер функции. Подменяем адрес в таблице экспорта на адрес

нашего обработчика функции. Для каждой библиотеки существует

своя таблица в памяти, в которой содержится информация о каждой

перехватываемой функции. А именно: количество параметров, кото-

рые необходимо собрать со стека; тип параметра (HANDLE, строка,

DWORD, указатель на буфер и т.д.); параметр, указывающий, нуж-

но ли возвращаемое значение и т.д. Низкоуровневый драйвер реги-

стрирует себя на прерывании INT FF. Как только оно срабатывает,

418

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

функции. На основе прототипа он собирает всю необходимую ин-

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

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

разбирает пакет и регистрирует информацию в LOG-файле. Кроме

всего прочего, драйвер выполняет еще ряд дополнительных функ-

ций: следит только за указанными процессами, фильтруя их по име-

ни; отслеживает создание процесса-ребенка процессом-родителем и

начинает следить и за ним. Данный метод позволяет практически

полностью забыть о том, какой упаковщик использует приложение,

какой метод защиты себя от отладчика реализован в приложении.

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

ся иметь дело с зашифрованными строками, которые передаются

в качестве аргументов API-функциям, так как перед выполнением

функции строки должны быть расшифрованы. Тем самым реали-

зованы все критерии, которые ставились в самом начале. Анализ

исполняемых файлов превратился в изучение LOG-файла. С такой

системой намного проще изучать подозрительные процессы и делать

соответствующие выводы.

Литература

1. Перехват API функций в Windows NT. http://www.wasm.ru/

2. Соломон Д., Руссинович М. Внутреннее устройство Microsoft

Windows 2000. Структура и алгоритмы работы компонентов

Windows 2000 и NTFS 5. М.: Microsoft Press, 2001.

3. Hoglund G., Butler J. Rootkits: subverting the Windows kernel.

Addison Wesley Professional, 2005.

4. Schrieber S.B. Undocumented Windows 2000 secrets. A programmers

cookbook. Addison Wesley Professional, 2001.

419

Савицкая Д.В.

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

Генерирование неотрицательных матриц

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

Кодирование и декодирование (0,1)-матриц

Рекомендовано к публикации доцентом Хитровым Г.М.

1. Генерирование матриц. Различные задачи теории эксперт-

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

ложений используют матрицы с неотрицательными элементами и

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

реализации. Отладка программ требует либо иметь в качестве баз

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

ным образом выбираются матрицы, либо случайным образом гене-

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

ко 5-вершинные графы весьма трудная задача, поскольку их общее

количество равно числу различных (0,1)-матриц 5-го порядка, т.е.

2

5

= 33554432. А в MATLAB имеется стандартная программа, гене-

рирующая случайным образом неотрицательные матрицы с элемен-

тами из промежутка [0,1] [1, стр. 296]. Таким образом, для отлад-

ки программ, можно строить (генерировать) матрицы с заданными

свойствами на основе упомянутой стандартной программы. Этому и

посвящена первая часть статьи.

Начнем с генерирования весовых векторов, т.е. с построения век-

тора (столбца) с неотрицательными элементами, сумма которых рав-

на единице, встречающихся в различных задачах усреднения. Поль-

зуясь стандартной программой MATLAB, необходимо сгенерировать

столбец желаемой размерности (т.е. (n×1)-матрицу), и нормировать

его, предварительно посчитав сумму его элементов.

2. Генерирование матриц для аддитивного метода пар-

ных экспертных сравнений. Этому методу соответствует неот-

рицательная матрица со следующими свойствами: a

ij

+ a

ji

= 1 и

a

ii

=

n

j=i,j=1

a

ij

, где n – размерность матрицы A.

В данном случае после генерирования матрицы желаемой раз-

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

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

ных элементов уже необходимо знать все остальные элементы мат-

420

рицы. Желательно также сделать округление до заданного числа

цифр после запятой, поэтому после генерирования матрицы умножа-

ем каждый элемент, например, на 1000, округляем до ближайшего

целого числа и затем делим элементы на 1000.

function Gexp

n=input(’размерность матрицы A - ’);

A=rand(n,n);

A=A.*1000;A=round(A);A=A./1000;

for i=1:n

for j=1:n j>i;

A(j,i)=1-A(i,j); end

end

for i=1:n;

for j=1:n

if j==i; A(i,j)=sum(A(:,j))-A(i,j); end

end

end

disp(A)

Перейдем к генерированию квадратных (0,1)-матриц со специальны-

ми свойствами. Нужно отметить, что (0,1)-матрицами являются, в

частности, матрицы бинарных отношений [2] и матрицы смежностей

графов. Поскольку зачастую задачи в теории графов рассматрива-

ются для графов различных свойств: без петель, ацикличных (без

ориентированных циклов [3, стр.168]), неориентированных и т.д., то

будем генерировать (0,1)-матрицы с соответствующими свойствами.

3. Генерирование матриц графов, различной степени на-

сыщенности связями между вершинами. Другими словами,

нас интересует генерирование (0,1)-матриц различной степени раз-

реженности ((0,1)-матрица тем более разрежена, чем больше у нее

нулей).

Программа генерирования таких матриц, приведенная ниже, сна-

чала генерирует матрицы с элементами, принадлежащими отрезку

[0,1]. Затем эти элементы «округляются» до нуля или единицы. Но

так как нас интересуют (0,1)-матрицы различной степени разрежен-

ности, вводим коэффициент p ∈ [0, 1] , относительно которого будет

определяться степень разреженности (0,1)-матрицы, а именно, если

a

ij

< p, то a

ij

= 0. Понятно, что при p < 0, 5 в генерируемой (0,1)-

421

матрице будет больше единиц, при p > 0, 5 — нулей, при p = 0 —

единичная матрица, а при p = 1 – нулевая матрица.

Рассмотрим далее (0,1)-матрицы с нулевой диагональю. Такие

матрицы являются матрицами смежности графов без петель. Гене-

рировать такие (0,1)-матрицы легко, достаточно в сгенерированной

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

нулить главную диагональ. В имеющейся программе это отразится

добавлением двух строчек.

Для ацикличных графов матрица смежности всегда может быть

приведена к треугольному виду с нулевой диагональю [2]. Для полу-

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

ной выше матрице, стоящие над (под) главной диагональю. Дополне-

нием в программу генерирования (0,1)-матриц двух строчек можно

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

графов.

Симметричные (0,1)-матрицы есть матрицы смежности неориен-

тированных графов, которые часто рассматриваются в теории гра-

фов отдельным классом. Для генерирования таких матриц достаточ-

но рассматривать элементы, стоящие над (под) главной диагональю,

и через них определять элементы, стоящие под (над) диагональю.

function Gen

n=input(’размерность матрицы A - ’);

p=input(’введите коэффициент p (если Aij

A=rand(n,n);

for i=1:n

for j=1:n %для симметричных матриц добавить "j>=i;"

if i==j A(i,j)=0; %для обнуления главной диагонали

end %для обнуления главной диагонали

if j<=i A(i,j)=0; %для треугольной матрицы

else %для треугольной матрицы

if A(i,j)

A(i,j)=0;

else A(i,j)=1;

end

A(j,i)=A(i,j); %для симметричных матриц

end

end

disp(A)

422

4. Кодирование и декодирование (0,1)-матриц.

Определение 1. Назовем вектором-кодом (0,1)-матрицы стол-

бец, определяемый по следующему правилу: Acod = A ∗ H, где

H = (2

n−1

, 2

n−2

, . . . , 1) и n – размерность матрицы A.

Иначе говоря, если представить, что строки (0,1)-матрицы — это

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

систему, получим вектор-код (0,1)-матрицы. Перевод из двоичной в

десятичную форму записи процедура однозначная, следовательно,

(0,1)-матрица определяется однозначно по ее вектору-коду. А зна-

чит, вместо хранения (0,1)-матриц целиком, что в памяти занимает

n

2

ячеек, можно хранить их как векторы-коды, которые занимают

всего n ячеек памяти. Также с применением вектора-кода на листе

печатного текста можно разместить больше информации.

Таким образом, использование вектор-кода (0,1)-матриц ведет к

некоторой экономии электронных и бумажных носителей.

Нужно отметить, что кодирование (0,1)-матриц не только ведет к

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

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

дочение произвольных (0,1)-матриц. По виду вектора-кода матрицы

смежности неориентированного графа можно также сказать о неко-

торых свойствах самого графа. Если в векторе-коде присутствует

хотя бы один нуль, то соответствующая ему (0,1)-матрица — разло-

жимая, а неориентированный граф – несвязный. Однако отсутствие

нулей не гарантирует связность неориентированного графа.

Замечание 1. Понятие вектора-кода можно применять и для

прямоугольных (0,1)-матриц. В этом случае помимо самого вектора-

кода

необходимо

хранить

информацию

и

о

размерности

(0,1)-матрицы.

Программа построения вектора-кода матрицы заключается в по-

строении столбца H и умножении на кодируемую матрицу справа.

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

Программа декодирования (0,1)-матриц изначально проверяет

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

ца не превышал числа 2

n

− 1, где n – размерность вектор-кода и,

соответственно, (0,1)-матрицы.

Программа декодирования матриц:

function decod

Acod=input(’введите вектор-код (0,1)-матрицы - ’);

423

n=numel(Acod);

i=1:n;

if Acod(i)>2^n-1

’проверьте правильность ввода вектор-кода’

Acod(i)

return

end

A=zeros(n,n);

for i=1:n

k=str2num(int2str(dec2bin(Acod(i))))-’0’;

p=numel(k); A(i,n-p+1:n)=k;

end

disp(A)

Определение 2. Граф будем называть упорядоченным, если

его нумерация вершин упорядочена по степеням захода (число дуг,

сходящихся в вершине [4, стр.13; 3, стр.171]).

Определение 3. (0,1)-матрица называется упорядоченной, если

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

Понятно, что упорядоченному графу соответствует упорядочен-

ная матрица смежности.

Любую (0,1)-матрицу можно упорядочить с помощью переста-

новки рядов (одновременной перестановки строк и столбцов), т.е.

упорядочивание (0,1)-матрицы можно определить как переход от ис-

ходной матрицы к P -подобной матрице, у которой упорядочена по

убыванию строка столбцовых сумм. Иными словами, упорядочение

есть переход от матрицы A к матрице A = P AP , где P — матрица

перестановок, а A – упорядоченная матрица.

Определение 4. Сумму элементов вектора-кода назовем кодом

матрицы или кодом графа.

Если же рассматривать строчки матрицы смежности графа как

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

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

чим код (0,1)-матрицы. При более глубоком рассмотрении можно

увидеть, что код (0,1)-матрицы есть ничто иное, как произведение

строки столбцовых сумм на H (из определения вектора-кода).

В отличие от вектора-кода, по коду нельзя однозначно восстано-

вить (0,1)-матрицу. Код не является инвариантом P -подобных мат-

риц, т.е. коды P -подобных матриц могут быть различны, они зави-

424

сят от упорядочивания (0,1)-матрицы. Поэтому будем рассматривать

код в основном для упорядоченной матрицы.

Утверждение 1. Код (0,1)-матрицы инвариантен относи-

тельно преобразований Р-подобия, сохраняющих упорядочивание

матриц.

Доказательство. При преобразованиях P -подобия, сохраняю-

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

неизменной, а так как код можно представить как произведение

строки столбцовых сумм на H, значит, и код (0,1)-матрицы не из-

менится.

Утверждение 2. Все матрицы перестановок имеют код 2

n

−1,

где n — размерность матрицы перестановки.

Доказательство. Возьмем тривиальную матрицу перестановок

– единичную. Вектор-код единичной матрицы равен самому столбцу

H. Сумма элементов вектора-кода (код матрицы) равна 2

n

− 1.

Так как строка столбцовых сумм матриц перестановок состоит из

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

матриц, то по утверждению 1 все матрицы перестановок имеют тот

же код, что и единичная матрица.

Замечание 2. Среди P -подобных матриц наибольший код у упо-

рядоченной (0,1)-матрицы. Его и будем подразумевать под словами

«код матрицы».

Процесс упорядочивания (0,1)-матрицы, важный для различных

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

рестановки P , с помощью которой осуществляется переход от исход-

ной матрицы к упорядоченной матрице.

Обсудим программу нахождения таких матриц перестановок.

Прежде всего необходимо вычислить строку столбцовых сумм и

провести ее упорядочивание. В программе MATLAB имеется стан-

дартная функция упорядочивания элементов строки по возраста-

нию, одновременно указывающая перестановку номеров элементов

строки. Поскольку нас интересует упорядочивание по убыванию, то

необходимо ввести матрицу, состоящую из нулей с единичной диа-

гональю, идущей из правого верхнего угла в левый нижний (эта

матрица строится с использованием декодирования вектора-кода). С

помощью этой матрицы можно перейти от возрастания к убыванию.

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

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

матрицу перестановки P . Останется лишь сделать преобразования

425

P -подобия над исходной матрицей A.

Qcod=[1];

for t=1:n-1; Qcod=[Qcod; 2^t]; end

Q=decod(Qcod)

e=ones(n,1); S=e’*A

[a, i]=sort(S); j=i*Q;

for k=1:n; b(k)=2^(n-j(k)); end

P=decod(b)

A=P*A*P’

5. Заключение. В статье введены определения вектора-кода и

кода (0,1)-матрицы (графа) и рассмотрены некоторые их свойства.

Показано, что кодирование и декодирование дает не только различ-

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

процессе «упорядочивания матрицы».

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

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

ствами, откуда случайным образом их можно выбирать, а лучше

воспользоваться одной из описанных выше программ генерирова-

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

MATLAB. В статье рассмотрено генерирование лишь нескольких

основных классов неотрицательных матриц, оперируя с которыми

можно без труда перейти к генерированию матриц с более сложны-

ми свойствами.

Литература

1. Дьяконов В. MATLAB: учебный курс. СПб: Питер, 2001. 560 с.

2. Беспалов А.А. О матрицах бинарных отношений // Процессы

управления и устойчивость: Труды 33-й научной конференции

студентов и аспирантов факультета ПМ–ПУ / Под ред. В.Н. Стар-

кова. – СПб.: НИИ Химии СПбГУ, 2002. С. 456–460.

3. Оре О. Графы и их применение. М.: Мир, 1965. 176 с.

4. Цветкович Д., Дуб М., Захс Х. Спектры графов. Киев: Наукова

Думка, 1984. 384 с.

426

Семенец С. В.

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

Использование технологий WWW и ODBC

для организации удаленного администрирования

БД различных типов

Рекомендовано к публикации ассистентом Стученковым А.Б.

1. Введение. Существует множество реляционных СУБД раз-

личных производителей, таких как MSSQL, Oracle, DB2 и др. Лю-

бая серьезная СУБД располагает встроенными средствами админи-

стрирования и управления данными, например, Enterprise Manager у

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

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

ет необходимость в удаленном администрировании сразу несколь-

ких СУБД различных типов, установленных на одном или несколь-

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

СУБД, установленных, допустим, в большой корпоративной сети, с

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

ям по установке соответствующего программного обеспечения? Эта

проблема решается с помощью встроенных средств, но такое реше-

ние будет не совсем удобным и довольно трудоемким, так как ко-

нечному пользователю или администратору нужно, как минимум,

иметь на своем рабочем месте соответствующее ПО.

В рамках данной работы была сделана попытка разработки и ре-

ализации универсального, единого Web-приложения для доступа к

СУБД различных производителей. При этом, для того, чтобы конеч-

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

или иной СУБД, достаточно лишь иметь компьютер с доступом в

Internet или подключенный к корпоративной (локальной) сети.

2. Выбор средств реализации. Почти все современные СУБД

поддерживают язык запросов SQL (Structured Query Language), ко-

торый в настоящее время можно назвать стандартным языком ре-

ляционных баз данных (нынешние стандарты SQL известны под на-

званием SQL/92 и SQL/99). Отличия СУБД различных производи-

телей заключается в их реализации языка SQL. Под реализацией

языка понимается добавление к стандартному языку SQL различ-

ных расширений, увеличивающих его функциональность. Из наибо-

427

лее известных реализаций можно назвать такие, как Transact-SQL у

MSSQL Server и PL/SQL у Oracle. Но, несмотря на эти конфигурации

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

дарты SQL остаются выдержанными, и поэтому запрос, написанный

на языке SQL, будет корректно работать во всех СУБД (поддержи-

вающих, конечно, стандарт SQL/92) [1, 2].

2.1. Технология ODBC. Для доступа к различным СУБД

в работе используется технология ODBC. ODBC расшифровывается

как Open DataBase Connectivity (открытая система связи с базами

данных). Подавляющее большинство БД различных производителей

поддерживает эту технологию – ставший индустриальным стандар-

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

[3].

Вообще говоря, эта технология предназначена для упрощенного

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

ставляет собой стандартный интерфейс прикладного программиро-

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

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

расположена сама база данных.

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

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

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

ПО, поскольку на каждом клиентском месте для доступа к источни-

ку данных необходимо иметь соответствующий драйвер.

Эту проблему "размножения" клиентских драйверов ODBC мо-

жет решить применение так называемых "серверов ODBC". Наи-

более распространены сервера ODBC OpenLink фирмы OpenLink

Software и OpenChannel фирмы Visigenic Software. При их примене-

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

вера используемых БД, а лишь один, который связывает клиента с

"сервером ODBC", а тот уже передает клиенту нужный ему драйвер.

Естественно, что на сервере ODBC для каждого источника данных

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

В этом случае задача администрирования намного легче, чем внесе-

ние изменений в ПО на каждой клиентской машине [4].

В данной работе предпринята попытка решить подобную про-

блему "размножения драйверов" при помощи серверного Web–при-

ложения. Таким образом, вся обработка и обращение к различным

СУБД будет происходить на Web-сервере, а значит нужно устанав-

428

ливать соответствующее ПО (драйвера) только на один компьютер

— Web-сервер, а на клиентах достаточно иметь только Web-браузер,

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

Архитектура ODBC состоит из четырех основных компонентов

[3].

• Программный интерфейс (API). С его помощью приложе-

ние вызывает ODBC-функции для подключения к источнику

данных, посылки, приема данных, отключения от источника.

• Менеджер ODBC-драйверов. Обеспечивает приложение

списком доступных источников данных, динамически загружа-

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

редаваемых аргументов.

• Драйвер. Обрабатывает вызовы ODBC-функций и управля-

ет обменом между приложением и определенной реляционной

базой данных. При необходимости драйвер может преобразо-

вывать стандартные SQL-запросы в запросы для конкретного

источника данных.

• Источник данных – собственно данные и соответствующее

ядро базы данных и связанное с ними DSN (Data Source Name).

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

эта технология, в том, что пользовательское приложение общается

с физической базой данных через менеджер драйверов, фактически

ничего не зная о ее типе. Таким образом, возможна гибкая замена

типа физической базы данных при сохранении корректности рабо-

тающего с ней приложения (конечно, существуют исключения из-за

особенностей поддержки языка SQL различными типами БД, но они

несущественны, так как большинство БД все же поддерживают стан-

дарт SQL-92).

2.2. Технология PHP. Для реализации поставленной зада-

чи был выбран язык программирования PHP 4.х.х и Web-сервер

Apache, так как PHP – это широко распространенный высокофунк-

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

самые популярные парадигмы программирования — объектная и

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

ляющим фактором оказалось то, что этот язык довольно хорошо

интегрирован с технологией ODBC. Начиная с версии 4.х.х, в PHP

429

появилась возможность напрямую работать c ODBC данными, при-

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

ет подключения дополнительных библиотек. Эта возможность полу-

чила название унифицированных функций ODBC в PHP. Эти

функции заимствуют семантику ODBC API для реализации своего

собственного API [5-7].

3. Архитектура приложения. Архитектуру приложения мож-

но условно разбить на 2 части.

Рис. 1. Архитектура Web-приложения, использующего технологию ODBC

• Клиентская часть. Так как основой взаимодействия пользо-

вателя и WEB-приложения являются по большей части такие

сущности, как формы, а в нашем случае – большое количе-

ство форм, то на клиентскую часть обрушивается весомая до-

ля функциональности приложения. В основном, это обработ-

ка ошибок при заполнении форм пользователем, навигация по

430

сайту (в нашем случае сайт представляет собой визуализацию

структуры БД), предоставление пользователю графического

интерфейса для работы с БД и т.д. Для реализации этой функ-

циональности был использован скриптовый язык программи-

рования java script.

• Серверная часть (логика приложения). Здесь реализует-

ся ODBC API и происходит непосредственное взаимодействие

приложения и источника данных. Например, открытие соеди-

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

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

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

тие соединения.

Преимущества предложенной архитектуры:

• отсутствие необходимости в установке дополнительного ПО

для работы с базами данных;

• универсальность; возможность работы с СУБД различных ти-

пов (производителей);

• ориентация на Internet; возможность удаленного администри-

рования и/или управления различными серверами БД;

• масштабируемость; возможность расширять функциональность

приложения;

4. Результаты и выводы. Основные функции, доступные в раз-

работанном приложении:

• работа с двумя (пока) типами БД различных производителей

(MSSQL и ORACLE);

• просмотр содержимого СУБД (просмотр списка таблиц, содер-

жимого таблиц);

• интерактивное добавление новых БД, таблиц в БД, записей в

таблице;

• интерактивное удаление БД, таблиц в БД, записей в таблице;

• интерактивное изменение БД, таблиц в БД, записей в

таблице;

• навигация по выбранной СУБД;

• возможность ввода и выполнения текстовых "ручных"

SQL–запросов непосредственно из интерфейса.

431

Функции, которые планируется реализовать в ближайшее время:

• создание и подключение источника данных (DSN – удаленной

БД) непосредственно через интерфейс программы;

• просмотр служебной информации (статистики) по базе данных,

таблице (таблицах);

• работа в режиме транзакций;

• работа с индексами;

• работа с представлениями;

• интерактивная фильтрация вывода записей по полям таблицы

и по значениям полей;

• добавление и изменение новых ролей, пользователей, прав;

• поиск по значению в таблице.

В результате работы указанные технологии показали себя с наилуч-

шей стороны и оказались незаменимы в решении данной задачи.

Литература

1. Тихомиров Ю. MS SQL Server 2000: разработка приложений.

СПб.: BHV-СПб, 2001.

2. Дворжецкий А. SQL: Structured Query Language. Руководство

пользователя. М.: Познавательная книга плюс, 2002.

3. http://www.microsoft.com

4. http://www.ccc.ru/magazine/depot/

5. Сколло К., Аргерих Л. и др. Профессиональное PHP программи-

рование (2-е издание). М.: Символ-Плюс, 2003.

6. http://www.intuit.ru

7. http://phplens.com/phpeverywhere/node/view/9

432

Сотникова М.В.

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

Компьютерное моделирование

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

Рекомендовано к публикации профессором Веремеем Е.И.

1. Введение. Работа посвящена вопросам, связанным с анали-

зом возможностей реализации алгоритмов управления в режиме ре-

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

динамических объектов в связи с существенной ограниченностью ре-

сурсов бортовой вычислительной техники. Исследование проводит-

ся на примере конкретной системы управления морским судном [1],

движущимся в режиме циркуляции по курсу. Алгоритмы формиру-

ются с применением прогнозирующих моделей в контуре управле-

ния. Приводятся различные варианты их реализации с учетом огра-

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

цессов по курсу и крену. Осуществляется выбор параметров алго-

ритмов, уменьшающих длительность такта вычислений.

2. Математическая постановка задачи. Пусть динамика объ-

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

˙x = f (t, x, δ),

(1)

где x – вектор состояния, δ – отклонение исполнительных органов.

Динамика привода рулей описывается уравнениями

˙˜δ = f

1

(u) , δ = f

2

(˜

δ),

(2)

где u – управляющее воздействие, функции f

1

и f

2

определяют огра-

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

нение соответственно.

Наряду с уравнением состояния (1) будем рассматривать уравне-

ние измерения

y = Cx, dimy < dimx.

Управляющее воздействие будем формировать в виде

u = L (t, y, ϕ

∗

) ,

433

где L – оператор из некоторого класса, ϕ

∗

– постоянный командный

сигнал.

Введём также уравнение для контролируемых переменных

z = Mx.

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

менной будем считать угол крена θ, а измеряемыми величинами –

отклонение рулей δ и угол курса ϕ.

Целью управления является выполнение циркуляции с ограни-

ченным временем T разворота по курсу на угол 360

◦

. При этом вели-

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

допустимой величины: ρ ≤ ρ

0

.

Задача состоит в таком выборе оператора L, чтобы достигалась

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

переменные

|θ (t)| ≤ θ

0

, ∀t ∈ [0, T ] .

3. Оптимизационный подход к достижению цели управ-

ления. Для достижения поставленной цели можно использовать ал-

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

тичным функционалом

J = J (u) =

∞

0

λ

2

1

(ϕ − ϕ

∗

)

2

+ λ

2

2

u

2

dt.

(3)

Осуществим синтез линейного LQR-регулятора u = K (x − x

∗

) на

базе уравнений линейного приближения для модели (1), (2). При

этом выбором коэффициентов функционала (3) можно добиться же-

лаемого качества переходного процесса по курсу, но при этом не га-

рантируются ограничения по крену. Одним из традиционных спо-

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

симально допустимых отклонений рулей. Но это ведёт к неполному

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

го процесса и радиус циркуляции.

4. Алгоритмы управления с прогнозирующей моделью.

Для построения управления, которое обеспечивает достижение цели

434

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

вано в режиме реального времени, воспользуемся MPC-подходом [2],

[3] с текущим прогнозированием динамики. Этот подход позволяет

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

чений.

Существо MPC-подхода составляет следующая схема управления

динамическими объектами по принципу обратной связи.

1. Рассматривается некоторая (относительно простая) математи-

ческая модель объекта (прогнозирующая модель), начальные

условия для которой определяются его текущим состоянием

x (t). При заданном программном управлении u = u (τ ) выпол-

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

гноз движения на некотором конечном отрезке времени (гори-

зонте прогноза T

p

).

2. Выполняется оптимизация программного управления, целью

которой служит приближение регулируемых переменных мо-

дели к соответствующим командным сигналам r (t) на гори-

зонте прогноза. Оптимизация осуществляется с учётом всего

комплекса ограничений, наложенных на управляющие и регу-

лируемые переменные.

3. Найденное оптимальное управление u

∗

(τ, x (t) , T

p

, T

c

) реализу-

ется в

качестве

программного

управления

на

отрезке

τ ∈ [t, t + δ].

4. Горизонт прогноза сдвигается на шаг вперед, и повторяются

пункты 1—3 данной схемы.

В целом реализация MPC-подхода приводит к нелинейной неста-

ционарной обратной связи по состоянию объекта управления.

5. Схема реализации управления в режиме реального

времени. При реализации в режиме реального времени программ-

ное управление задается в виде кусочно-постоянной функции со зна-

чениями u

k

, u

k+1

, . . . , u

k+P −1

, где P – число шагов на горизонте про-

гноза. Шаг прогноза обозначим символом ∆t, тогда горизонт прогно-

за определит величина T

p

= P ∆t (сек).

Приведенная выше схема управления с прогнозом может быть

реализована в режиме реального времени следующим образом.

1. Осуществляем измерение вектора y и восстанавливаем текущее

состояние x

k

объекта с помощью наблюдателя.

435

2. Решаем оптимизационную задачу для прогнозирующей модели

с начальным условием x|

τ =t

= x

k

. Это задача о поиске экстре-

мума нелинейной функции J (u

k

, u

k+1

, . . . , u

k+P −1

, x

k

) на допу-

стимом множестве Ω ⊂ R

P

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

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

J (u

k

, u

k+1

, . . . , u

k+P −1

, x

k

) −→

min

(u

k

,u

k+1

,...,u

k+P −1

)∈ Ω

(4)

Функция J формируется путём подстановки в функционал (3)

программного управления на горизонте прогноза.

3. Из найденной в результате решения задачи (4) оптимальной

числовой последовательности u

∗

k

, u

∗

k+1

, . . . , u

∗

k+P −1

используем

только первую компоненту u

∗

k

в качестве программного управ-

ления на отрезке τ ∈ [t

k

, t

k

+ ∆t].

4. Заменяем момент времени t

k

моментом t

k

+ ∆t и повторяем

операции, указанные в пунктах 1—3.

Приведенная схема реализации MPC-управления определяет необ-

ходимость решения задачи оптимизации на каждом шаге ∆t процес-

са. При этом, чем больше горизонт прогноза T

p

и чем меньше шаг

прогноза ∆t, тем больше размерность задачи оптимизации. Заметим,

что уменьшение горизонта и увеличение его шага с целью упроще-

ния оптимизации, может привести к ухудшению качества процесса,

вплоть до потери устойчивости.

Рассмотрим два возможных варианта реализации управления с

прогнозом для выполнения циркуляции судна.

6. Управление с линейной прогнозирующей моделью. В

этом случае в качестве прогнозирующей модели будем использовать

систему линейных разностных уравнений. Данная прогнозирующая

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

уравнений (1), (2) и её последующей дискретизацией с шагом дис-

кретности ∆t. Задача оптимизации (4) в рамках данного варианта

MPC-подхода сводится к задаче квадратичного программирования

J (u

k

, u

k+1

, . . . , u

k+P −1

, x

k

) = u

T

Hu + 2f

T

u + g →

min

u∈Ω⊂R

P

,

(5)

где u = (u

k

, u

k+1

, . . . , u

k+P −1

).

436

Для проведения вычислительных экспериментов примем в каче-

стве объекта управления сухогруз водоизмещением 4000 тонн. Ис-

следования показывают, что для этого объекта управления нелиней-

ность исходных уравнений динамики (1), (2) играет весьма суще-

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

ной модели приводит к значительным ошибкам в прогнозировании.

В частности, по угловой скорости крена ω

x

и по крену θ прогноз

не соответствует движению, определяемому исходными уравнения-

ми. На рис. 1 приведен пример прогноза по крену на период 20 сек.

0

5

10

15

20

−5

0

5

10

15

20

25

Prediction

Real motion

Рис. 1. Прогноз по крену

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

мые значения крена гораздо меньшие

по модулю, чем реализуемые в дей-

ствительности. Это не дает возмож-

ности MPC-регулятору заранее про-

гнозировать возможность выхода на

нежелательные уровни. Поэтому вве-

дение дополнительных ограничений

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

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

няет оптимизационную задачу (5), которая при неправильном про-

гнозе может вообще не иметь решения.

7. Управление с прогнозом по нелинейным уравнениям.

Естественный путь повышение качества MPC-управления заключа-

ется в прогнозе движения по нелинейным уравнениям. С вычисли-

тельной точки зрения это значительно сложнее, чем линейный вари-

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

ного программирования со сложной целевой функцией и нелинейны-

ми ограничениями. Это обстоятельство определяет необходимость в

проведении компьютерного моделирования для подтверждения воз-

можности реализации предлагаемого алгоритма управления на бор-

ту и для выбора наилучших параметров алгоритма управления.

Осуществим по методу Эйлера дискретизацию нелинейных урав-

нений (1), (2). В результате получим следующую систему разностных

уравнений для выполнения прогноза:

x

k+1

= x

k

+ τ f t

k

, x

k

, ˜

δ

k

,

˜

δ

k+1

= ˜

δ

k

+τ f

1

(u) .

(6)

437

Здесь τ – шаг интегрирования, составляющий фиксированную, до-

статочно малую часть от шага прогноза.

При построении нелинейного MPC-управления, учитывающего

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

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

пуклом допустимом множестве.

Для рассматриваемого объекта зададим максимальное значение

по крену θ

max

= 10

◦

, по рулям – δ

max

= 35

◦

, по скорости перекладки

– ˙δ

max

= 3

◦

/c. На рис. 2 представлен переходный процесс по крену θ

и отклонениям рулей δ для нелинейного MPC-управления (NMPC)

с учетом введенных ограничений. Для сравнения на рисунке также

показаны аналогичные процессы для регулятора, полученного LQR-

оптимизацией с функционалом (3).

0

50

100

150

200

250

−5

0

5

10

15

20

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

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