"Радиомир. Ваш компьютер", #5, 2002

  В данной статье под случайными числами понимается возможность получения псевдослучайной последовательности символов в заданном диапазоне значений. И только. Математические теории их получения и прочие вопросы не рассматриваются. Я попытался с помощью случайных чисел упростить алгоритм поиска файлов в OS DOS (Windows) и провести небольшое исследование поведения программы, обладающей таким алгоритмом.

• Исходные тексты

Суть исследований

  Сначала коротко о поиске файлов и каталогов в DOS (Windows). Как известно, для поиска файлов и каталогов используются два сервиса прерывания int 21h - FindFirst и FindNext (функции 4eh и 4fh). Для указания цели поиска следует передать атрибут файлов в регистре cx, указатель на путь до каталога поиска и маску в файла в виде строки (в регистрах ds:[dx]). Например: MyPath db 'c:\tmp\*.bat',0.

  В этом случае поиск выполнится в каталоге c:\tmp, будут (или не будут) найдены все файлы с расширением "*.bat". Сначала для инициализации поиска следует вызвать сервис FindFirst, а последующие найденные файлы будут возвращатся после вызова FindNext. Папки (директории) ищутся аналогично - например, по маске "*.*" и атрибуту 16 (директория).

  Результаты поиска DOS помещает в так называемую DTA (Data Transfer Area). К примеру, при запуске программы она по умолчанию находится в PSP программы (для com-файла по смещению 80h). Но, при желании, DTA можно переопределить, чтобы не портить содержимое PSP. В этой области, помимо имени найденного файла, находятся такие атрибуты файла как дата и время.

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

  Данная задача - не из легких. В простой реализации ее решением может быть использование очередей (динамические связанные элементы, реализуемые, например, в Паскале через указатели). Более сложной реализацией (но и более красивой!) является рекурсия (к примеру, процедуре передается в стеке стартовый каталог).

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

• сложность и большой размер кода (даже на asm!);
• низкое быстродействие;
• самое главное - если нам нужно найти любой подходящий объект во множестве каталогов (не все, а первый попавшийся!), то удручает применение столь мощной "артиллерии" (выше) для решения достаточно простой задачи.

  Где же и зачем может быть поставлена задача поиска любого первого объекта? Я для примера рассмотрел обычный файловый нерезидентный вирус, способный заражать exe-файлы.

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

  Время незначительное, потому что он не хочет быть похожим на операционную систему с ее сообщением "Install: Please Wait:". Можно схалявить, и посмотреть "под ноги" - в текущий каталог, откуда запустилась программа. Для этого просто нужно выполнить поиск файлов прямо здесь с маской "*.exe". Но так мы далеко не уйдем - максимум, что можно, это заразить все файлы в одной директории, и точка. Не говоря уж о всем диске и других драйвах: Конечно, если пользователи не будут постоянно копировать друг у друга файлы и вдобавок раскидывать их по всем своим папкам. Правда, в этом случае сектор поражения тоже будет невелик - пациенты психушки имеют ограниченное число контактов с внешним миром.

  Таким образом, приходим к вирусу, который должен искать мишени в других местах (каталогах, дисках). Например, можно получить текущий диск, перейти в его корень, и заражать файлы, лежащие в корне. Или пойти дальше - поискать во всех каталогах корня exe-файлы одним из вышеперечисленных алгоритмов.

Первичная реализация другого подхода

  Однако можно посмотреть на проблему не так прямолинейно. Ведь нам на самом деле нужен всего лишь любой случайный объект. Заразив его, наш код удваивается, а, следовательно, в следующий раз уже будет выбрано два случайных объекта, потом - четыре, и так по нарастающей.

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

• случайным образом сменить диск (логический);
• случайным образом перейти в верхний каталог (команда "cd :");
• случайным образом найти подкаталог со случайным номером и перейти в него.

  После выполнения одного или нескольких действий из этого списка, текущим каталогом для поиска становиться в общем случае произвольный, но другой! каталог, возможно, на другом логическом диске.

Более подробное описание и первые результаты

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

  Для начала необходимо задать случайное число (числа), чтобы разыграть вероятность каждого действия. Для этих целей был взят сервис того же int 21h - функция получения системного времени 2ch, которая возвращает в регистре dl достаточно случайное число сотых долей секунды.

  Далее необходимо определиться со стратегией - с какой вероятностью будем выполнять каждое из действий. Почему не выполнять их с максимальным приоритетом (всегда пытаться сменить диск, выйти наверх и найти что-нибудь "под ногами")? Так мы сузим себе круг поиска и, самое главное - будем негибки к различным конфигурациям пользователя (скажем, у одного много подкаталогов, а другой все скинул в корень). С этой целью в программе задается три параметра вероятностей активизации:

• VarOfDrive(0...99) - вероятность перехода на другой диск;
• VarOfUpDr(0:99) - вероятность перехода в верхний каталог;
• VarOfDnDr(0:99) - вероятность поиска подкаталога с произвольным номером.

  Итак, с вероятностью VarOfDrive начинаем искать другой диск в пределах поддерживаемых DOS (0:31). Далее, независимо от результата предыдущего действия, с вероятностью VarOfUpDr выполняем команду "cd ...", и с вероятностью VarOfDnDr, опять-таки независимо от предыдущих событий, ищем каталог с произвольным в разумных пределах номером (скажем, не более 24) "под ногами" и, если он найден, переходим в него. При этом в момент поиска подкаталога происходит сверка с DOS-временем файла в DTA, и если время и текущий номер поиска кратны 4, то каталог с таким номером досрочно признается годным.

  Надо признать, что в первичной реализации я действовал скорее по наитию - параметры выбрал достаточно наобум: VarOfDrive = 33%, VarOfUpDr = 50% и VarOfDnDr = 50%. Причем последние оказались зависимыми друг от друга. Для розыгрыша во всех событиях бралось одно и то же число - всегда число сотых долей секунды, полученное при старте.

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

Стратегия с умом

  Однако можно задаться вопросом - а насколько эффективно был сделан выбор вероятностей VarOfDrive = 33%, VarOfUpDr = 50% и VarOfDnDr = 50%, и что же будет со всеми-всеми программами на всех-всех дисках в общем случае? Заразит ли вирус(ы) их все или забьется в какой-нибудь каталог и по тем или иным причинам не сможет вырваться из него в силу неправильно выбранной стратегии? Если в случае вируса, который умеет заражать только в текущем каталоге, проверка тривиальна, то в нашем случае вот так все не проверишь: Не будешь же, в самом деле, последовательно обходить десятки а то и сотни каталогов в непонятно какой последовательности!

  С целью получения хоть какого-то ответа на эти вопросы мною была написана специальная программа, моделирующая распространение вируса по заранее выбранной конфигурации дисков и каталогов.

Моделирование процесса размножения вируса

  Для начала зададим параметры идеальной модели конфигурации дисков и каталогов в них:

• DriveNumber - число логических дисков;
• DirsPerDrive - число корневых каталогов на каждом диске;
• DirsLevel - уровень вложенности каталогов. Это означает, к примеру, что если задан уровень вложенности 2, то у корневого каталога может быть не более двух вложенных директорий. Например: C:\TEMP - корневой каталог, в нем есть две папки - DIR1 и DIR2 (C:\TEMP\DIR1 и C:\TEMP\DIR2), у папок DIR1 и DIR2 могут быть подкаталоги, но в этих подкаталогах не может быть других подкаталогов;
• LocDirs - сколько папок в любой директории, включая корневые;
• ExecutableProgs - число исполняемых модулей в любой папке (в корне у меня их нет!), которые можно заразить.

  Будем задавать также различные параметры стратегии распространения вируса - все те же VarOfDrive, VarOfUpDr и VarOfDnDr.

  Для моделирования поведения вируса и получения результатов общего заражения воспользуемся методом Монте-Карло, проще говоря - методом случайного розыгрыша событий. В данном случае можно было, конечно, попытаться вывести аналитическую зависимость количества заражаемых модулей от количества запуска произвольных программ, но данный способ представляется мне гораздо более сложным, чем тот, который описан ниже.

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

  В нашем случае будем делать вот что. Доопределим несколько параметров уже самого моделирования:

• MaxDays - число дней испытаний;
• ProgPerDay - число запусков произвольных программ в день;
• AverCounter - число проходов по всем дням (т.е. прогоняем весь процесс заражения AverCounter раз - прямо как с монетой).

  Испытания будут заключаться в следующем. Пусть вначале все программы на всех DriveNumber дисках будут незараженными. Заразим произвольную программу. Потом будем выбирать случайную программу (имитируя ее запуск) ProgPerDay раз в день, и так MaxDays дней. Фактически, в одном проходе мы выполняем запуски программ ProgPerDay*MaxDays раз - так сделано просто для наглядности. Если случайно запущенная программа окажется зараженной, то мы можем имитировать активизацию вируса из конкретного каталога и диска. Модельный вирус, в свою очередь, получит случайное число (как бы досовские сотые секунды) в качестве параметра и с ним запустит собственный генератор случайных чисел (в первичной реализации я не понимал необходимости такого генератора). Далее он случайным образом выполнит действия по смене диска и каталога и, если найдет незараженную программу, выполнит ее заражение. Таким образом, число зараженных программ будет увеличиваться.

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

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

Результаты моделирования

  Как только я провел серию первых испытаний со стратегией, соответствующей первоначальной реализации вируса, то сразу стало ясно, насколько она оказалась неэффективна! Оказалось, что такой вирус практически ничего не заражает - менее 5% программ! Пришлось дополнить алгоритм стратегии следующими усовершенствованиями:

• в вирус был добавлен генератор псевдослучайных чисел;
• параметры VarOfDrive,VarOfUpDr и VarOfDnDr стали по-настоящему независимыми друг от друга - оказалось, что их взаимная зависимость серьезно сужает эффективность алгоритма случайного поиска!

  Рис. 1

  На рис.1 изображена зависимость числа зараженных программ от числа дней существования вируса в системе для следующих параметров:

• MaxDays = 200 - число дней испытаний;
• ProgPerDay = 50 - число запусков произвольных программ в день;
• DriveNumber = 8 - число логических дисков;
• DirsPerDrive = 12 - число корневых каталогов на каждом диске;
• DirsLevel = 2 - уровень вложенности каталогов;
• LocDirs = 2 - количество папок в любой директории, включая корневые;
• ExecutableProgs = 2 - число исполняемых модулей в любой папке.

  Т.е. всего было выполнено 10000 запусков для 1344 программ. Каждая программа запускалась примерно 9 раз. Число каталогов в корневом каталоге рассчитывается по формуле: (LocDirs^(DirsLevel + 1) - 1)/(LocDirs-1) - фактически, сумма геометрической прогрессии).

  Параметры стратегии были следующими:

  VarOfDrive = 50%, VarOfUpDr = 50% и VarOfDnDr = 50%.

  Далее я сразу обнаружил очень интересный эффект - если в системе запускать программы неограниченно долго (число запусков >> числа программ), то вирус никогда не сможет заразить все программы! По крайней мере, это проявлялось для вышеприведенных параметров, с той лишь разницей, что число дней запуска было увеличено до 2000 (рис.2). Насыщение наступает примерно на уровне всего 40% от всего числа программ. Причем повторюсь, первая зараженная программа выбиралась произвольно - а это означает, что режим насыщения наступает независимо от того, какая программа будет заражена первой!

  Рис. 2

  Далее я поэкспериментировал с параметрами стратегии. В одном случае (конфигурация системы прежняя) параметры стратегии были: VarOfDrive = 10%, VarOfUpDr = 50% и VarOfDnDr = 50% (неактивно меняем диски, но достаточно активно лезем в верхние и нижние каталоги), в другом - VarOfDrive = 50%, VarOfUpDr = 50% и VarOfDnDr = 50% (средне-активно меняем диски, каталоги), а в третьем - VarOfDrive = 90%, VarOfUpDr = 50% и VarOfDnDr = 50% (очень активно меняем диски). Результат представлен на рис.3. Вероятности смены диска: "-" - 10%; "---" - 50%; "- - -" - 90%.

  Рис. 3

  В следующем случае я исследовал на тех же параметрах системы что выгоднее: активно менять каталоги (VarOfDrive = 5%, VarOfUpDr = 90% и VarOfDnDr = 30%) или активно менять диски (VarOfDrive = 90%, VarOfUpDr = 10% и VarOfDnDr = 90%), т.е. активно менять текущий драйв и "расползаться" по подкаталогам. Результат на рис.4 (вероятности смены диска, перехода в верхний каталог и вероятность перехода в нижний каталог: "-" - 5%,90% и 30%; "----" - 90%,10% и 90%.

  Рис. 4

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

• DriveNumber = 2 - число логических дисков;
• DirsPerDrive = 10 - число корневых каталогов на каждом диске;
• DirsLevel = 2 - уровень вложенности каталогов;
• LocDirs = 4 - количество папок в любой директории, включая корневые;
• ExecutableProgs = 2 - число исполняемых модулей в любой папке.

  Рис. 5

  На рис.5 - то, что получилось для четырех различных стратегий размножения. Уровень вложенности равен 4, в каждом каталоге - по две директории. Вероятности смены диска, перехода в верхний каталог и вероятность перехода в нижний каталог: "===" - 5%,20% и 90%; "---" - 5%,30% и 60%; "-" - 5%,90% и 90%; "- -" - 5%,60% и 30%.

Немного о генераторе случайных чисел

  Для моделирования мною был выбран генератор псевдослучайных чисел из книги С.В.Зубкова "Assembler - язык неограниченных возможностей". Это так называемый сдвиговый генератор в простейшей реализации для получения псевдослучайных чисел в размере одного байта.