17131

Стиснення програм. Комп’ютерні віруси

Лекция

Информатика, кибернетика и программирование

Лекція №7 Тема: Стиснення програм. Комп’ютерні віруси. План Алгоритми оборотних методів. Алгоритм RLE. Алгоритм KWE. Алгоритм Хафмана. Вірус. Класифікація вірусів. Алгоритми оборотних методів При дослідженні методів стиснення даних слід

Украинкский

2013-06-29

252.5 KB

0 чел.

Лекція №7

Тема: Стиснення програм. Комп’ютерні віруси.

План

  1.  Алгоритми оборотних методів.
  2.  Алгоритм RLE.
  3.  Алгоритм KWE.
  4.  Алгоритм Хафмана.
  5.  Вірус.
  6.  Класифікація вірусів.

Алгоритми оборотних методів

При дослідженні методів стиснення даних слід мати на увазі існування наступних доведених теорем.

1. Для будь-якої послідовності даних існує теоретична межа стиснення, яка не може бути перевищений без втрати частини інформації.

2. Для будь-якого алгоритму стиснення можна вказати таку послідовність даних, для якої він забезпечить кращий ступінь стиснення, ніж інші методи.

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

Таким чином, обговорюючи різні методи стиснення, слід мати на увазі, що щонайвищу ефективність вони демонструють для даних різних типів і різних об'ємів.

Існує достатньо багато оборотних методів стиснення даних, проте в їх основі лежить порівняно невелика кількість теоретичних алгоритмів, представлених в таблиці 1.

Таблиця 1. Властивості алгоритмів стиснення

Алгоритм

Вихідна структура

Сфера

застосування

Примітка

RLE (Run-Length Encoding

Список (вектор даних)

Графічні дані

Ефективність алгоритму не залежить від об'єму даних

KWE (Keyword Encoding)

Таблиця даних (словник)

Текстові дані

Ефективний для масивів великого об'єму

Алгоритм Хафмана

Ієрархічна структура (дерево кодування)

Будь-які дані

Ефективний для масивів великого об'єму

Алгоритм RLE

У основу алгоритмів RLE встановлений принцип виявлення послідовностей даних і заміни їх простою структурою, що повторюються, в якій указується код даних і коефіцієнт повтору.

Наприклад, для послідовності: 0; 0; 0; 127; 127; 0; 255; 255; 255; 255 (всього 10 байтів) утворюється наступний вектор:

Значення

Коефіцієнт повтору

0

3

127

2

0

1

255

4

При записі в рядок він має вигляд:

0; 3; 127; 2; 0; 1; 255; 4 (всього 8 байтів).

У даному прикладі коефіцієнт стиснення рівний 8/10 (80 %).

Програмні реалізації алгоритмів RLE відрізняються простотою, високою швидкістю роботи, але в середньому забезпечують недостатнє стиснення. Якнайкращими об'єктами для даного алгоритму є графічні файли, в яких великі одноколірні ділянки зображення кодуються довгими послідовностями однакових байтів. Цей метод також може давати помітний виграш на деяких типах файлів баз даних, що мають таблиці з фіксованою довжиною полів. Для текстових даних методи RLE, як правило, неефективні.

Алгоритм KWE

У основу алгоритмів кодування за ключовими словами (Keyword Encoding) встановлено кодування лексичних одиниць початкового документа групами байтів фіксованої довжини. Прикладом лексичної одиниці може служити слово (послідовність символів, справа і зліва обмежена пропусками або символами кінця абзацу). Результат кодування зводиться в таблицю, яка прикладається до результуючого коду і є словником. Звичайно для англомовних текстів прийнято використовувати двобайтове кодування слів. Пари байтів, що утворюються при цьому, називають токенамі.

Ефективність даного методу істотно залежить від довжини документа, оскільки через необхідність прикладати до архіву словник довжина коротких документів не тільки не зменшується, але навіть зростає.

Даний алгоритм найбільш ефективний для англомовних текстових документів і файлів баз даних. Для російськомовних документів, відмінних збільшеною довжиною слів і великою кількістю приставок, суфіксів і закінчень, не завжди вдається обмежитися двобайтовими токенамі, і ефективність методу помітно знижується.

Алгоритм Хафмана

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

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

• Чим частіше зустрічається той або інший символ, тим меншою кількістю бітів він кодується (відповідно, чим рідше зустрічається символ, тим довше його кодова бітова послідовність).

• Ієрархічна структура, що утворюється в результаті кодування, прикладається до стислого документа як таблиця відповідності.

Використовуючи 16 біт, можна закодувати до 256 різних символів. Проте ніщо не заважає використовувати і послідовності завдовжки до 20 біт — тоді можна закодувати до 1024 лексичних одиниць (це можуть бути не символи, а групи символів, склади і навіть слова).

У зв'язку з тим, що до стислого архіву необхідно прикладати таблицю відповідності, на файлах малих розмірів алгоритм Хафмана малоефективний. Практика також показує, що його ефективність залежить і від заданої граничної довжини коду (розміру словника). В середньому, найефективнішими виявляються архіви з розміром словника від 512 до1024 одиниць (довжина коду до 18-20 біт).

Синтетичні алгоритми

Розглянуті вище алгоритми в «чистому вигляді» на практиці не застосовують через те, що ефективність кожного з них сильно залежить від початкових умов. У зв'язку з цим, сучасні засоби архівації даних використовують складніші алгоритми, засновані на комбінації декількох теоретичних методів. Загальним принципом в роботі таких «синтетичних» алгоритмів є попередній перегляд і аналіз початкових даних для індивідуальної настройки алгоритму на особливості оброблюваного матеріалу.

Вірус (вірусна програма)це, як правило, невелика за об'ємом послідовність програмних кодів, володіюча наступними властивостями:

1.   Можливість створювати свої копії і упроваджувати їх в інші програмні об'єкти.

2.   Забезпечення прихованої (латентність) до певного моменту її існування і розповсюдження.

3.   Несанкціонована (з боку користувача) вироблюваних нею дій.

4.   Наявність негативних наслідків від її функціонування.

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

Реально існує цілий комплекс причин існування і розвитку «індустрії» вірусів. Серед основних з них слід виділити:

•    причини технічного характеру (пропуски в захисті ранніх версій операційних систем, призначених для персональних комп'ютерів з обмеженими можливостями);

•    причини економічного характеру (припустимо, боротьба з конкурентами);

•    причини соціального і психологічного характеру (наявність «фахівців», що володіють професійною кваліфікацією для написання вірусів і з тієї або іншої причини шляхів, що не знаходять, для конструктивної реалізації своїх здібностей).

Класифікація вірусів

В даний час описана велика кількість вірусів, обчислюваних десятками тисяч. Але серед них можна налічити не більш 40-50 активних, які мають розповсюдження. Віруси можна класифікувати таким чином:

•    завантажувальні віруси;

•    файлові віруси;

•    макровіруси;

•    мережеві віруси.

Завантажувальні віруси

Завантажувальні віруси упроваджуються в так звані завантажувальні області носіїв (початкові сектори (boot - сектори) накопичувачів, призначені для зберігання завантажувача ОС). Якщо зараженим виявиться системний диск, з якого відбувається завантаження системи, то управління одержує не звична програма завантаження, а заміщаючий його код вірусу. При зараженні вірус прочитує необхідну інформацію з первинного завантажувача і зберігає її в своєму коді.

Як правило, завантажувальні віруси є резидентними, тобто при завантаженні системи вірус встановлюється в пам'ять комп'ютера і знаходиться там постійно, перехоплює необхідні переривання і виробляє всі дії, на які він запрограмований.

При включенні більшості комп'ютерів BIOS прочитує головний завантажувальний запис з початку завантажувального диска в оперативну пам'ять і виконує її. Ця програма знаходить активний розділ диска, прочитує його перший (завантажувальний) сектор і виконує його. Потім ця програма завантажує або операційну систему, або завантажувач операційної системи. На жаль, вже багато років тому комусь прийшла в голову ідея створити вірус, що перезаписує головний завантажувальний запис або завантажувальний сектор, наслідки реалізації якої виявилися руйнівними. Такі віруси дуже широко поширені.

Як правило, вірус, що вражає завантажувальний сектор (або головний завантажувальний запис), спочатку копіює початковий вміст завантажувального сектора в яке-небудь безпечне місце на диску, що дозволяє йому завантажувати операційну систему після того, як він закінчить свої справи. Програма форматування диска фірми Microsoft fdisk пропускає першу доріжку диска, тому ця доріжка на машинах з операційною системою Windows є хорошим укриттям. Ще один варіант полягає в тому, щоб помітити вільний сектор диска як дефектний. Якщо кореневий каталог достатньо великий і розташовується у фіксованому місці, як в системі Windows 98, вірус може використовувати кінець кореневого каталогу. По-справжньому агресивний вірус може навіть виділити собі нормальний вільний дисковий простір і відновити стан списку вільних блоків відповідним чином.

При завантаженні комп'ютера вірус копіює себе в оперативну пам'ять, або на старші адреси, або в невживану область векторів переривань. У цей момент машина знаходиться в режимі ядра, її блок управління пам'яттю вимкнений, операційної системи немає, також немає і антивірусної програми. Найзручніший момент для вірусів. Коли все готово, вірус завантажує операційну систему, як правило, залишаючись резидентним в пам'яті.

Проте проблема таких вірусів пов'язана з тим, як потім знову одержати управління. Звичний спосіб полягає у використовуванні специфічних відомостей про те, як операційна система управляє вектором переривань. Наприклад, система Windows не перезаписує весь вектор за одну операцію. Натомість вона завантажує драйвери пристроїв один за іншим, і кожний з них забирає при необхідності вектор переривання. Цей процес може займати близько хвилини.

Така схема дає вірусу можливість зберегти за собою управління. Він починає з того, що перехоплює відразу всі вектори переривань (рис.1,а). У міру завантаження драйверів деякі вектори перезаписуються. Але якщо тільки драйвер годинника не завантажиться першим, у вірусу буде багато можливостей одержати управління по перериванню від таймера. Втрата вірусом переривання від принтера показана на мал. 1,б. Як тільки вірус помічає, що один з векторів переривань у нього відніме, він може захопити його знову, знаючи, що тепер це безпечно. (Насправді деякі вектори переривань перезаписуються під час завантаження операційної системи по декілька разів, але послідовність цих дій є детермінованою, і автор вірусу знає її напам'ять.) Повторне перехоплення переривання принтера показане на рис.1,в. Коли все завантажено, вірус відновлює всі вектори переривань, а собі залишає тільки вектор емулюючого переривання, яким користуються системні виклики. Врешті-решт, управління системними викликами значно цікавіше, ніж контроль над кожною операцією гнучкого диска, але під час завантаження вірус не може ризикувати втратити управління назавжди. Отже, коли операційна система завантажилася, ми маємо резидентний вірус, контролюючий системні виклики. Більшість резидентних вірусів саме так і завантажуються.

Мал. 1. На початку вірус перехоплює всі вектори переривань (а); операційна система забрала собі вектор переривання принтера (б); вірус помітив втрату вектора переривання принтера і знову

захопив його (в)

Файлові віруси

Файлові віруси використовують особливості файлової організації системи. Такі віруси упроваджуються у виконувані файли, в бібліотечні і об'єктні модулі, завантажувані драйвери, файли початкових текстів програм.

Файлові віруси заражають файли, упроваджуючись в початок, в кінець або в середину файлу. Такі файли залишаються працездатними, оскільки код вірусу дописується до початкового коду.

Деякі віруси замість початкового вмісту файлу записують свій код. Такі файли вже не можуть бути використаними по своєму прямому призначенню.

Файлові віруси можуть і не змінювати вміст файлів, що заражаються. Іноді для своєї активізації вони використовують властивості операційної системи, визначаючі порядок запуску програм. Так, якщо в одному каталозі є файли з однаковими іменами, то спочатку запускається файл з розширенням імені *.ВАТ, потім *.СОМ і *.ЕХЕ. Відповідно, якщо файл, що заражається, має розширення *.ЕХЕ, то вірусний файл з тим же ім'ям, але розширенням *.СОМ запускатиметься першим. У інших випадках файл з вірусом для перехоплення управління розташовує себе в такому каталозі, який, згідно змінного середовища PATH, знаходиться «вище» за каталог однойменного програмного файлу. Деякі віруси «привласнюють» ім'я файлу, що заражається, а тому дають нове (змінене) ім'я. Це, знову-таки, призводить до того, що при запуску «зараженого» файлу спочатку відпрацює вірус.

Як правило, потім управління передається на оригінальний файл. Останнє робиться для того, щоб приховати від користувача факт роботи вірусу.

Серед файлових вірусів зустрічаються віруси, які не пов'язані ні з одним з файлів. Запуск таких вірусів здійснюється «помилково». Файли таких вірусів мають «цікаві» з погляду користувача імена: Install.exe, Start.com і т.д. Такі віруси називають черв'яками (англ, варіант — worm).

Макровіруси

Макровіруси — це файлові віруси, що використовують особливості файлів документів популярних редакторів і електронних таблиць. У цих файлах розміщуються програми на макромовах, можливості яких дозволяють створювати програми-віруси.

Мережеві віруси

Мережеві віруси використовують для свого розповсюдження можливості комп'ютерних мереж. Найбільше поширення мережеві віруси набули в кінці 80-х років. Ці віруси використовували помилки в мережевих протоколах і програмному забезпеченні глобальних мереж. Зараз ці помилки виправлені і ці віруси не мають розповсюдження.

В даний час мережеві віруси розповсюджуються, використовуючи можливості електронної пошти. В основному це макровіруси.

Особливості алгоритму роботи вірусів

Віруси, які можуть залишати свої копії в оперативній пам'яті, називаються резидентними. Такі віруси залишаються активними, і після завершення роботи програми (і навіть після видалення файлу вірусу) аж до перезавантаження системи.

З метою приховати до певного моменту своє існування деякі віруси використовують різні методи. Стелс-віруси перехоплюють команду читання зараженої ділянки і підставляють незаражений код. Полиморфик-віруси шифрують свій код, щоб утруднити своє виявлення.

Апаратні пристрої — джерела вірусів

Зараження комп'ютера відбувається через пристрої, що дозволяють вводити інформацію в комп'ютер:

•   модем.

Інтернет — основне джерело розповсюдження вірусів. Зараження відбувається через копіювання заражених файлів з серверів глобальної мережі, при обміні через електронну пошту листами, в яких містяться документи формату Word, які можуть бути заражені макровірусами.

•    мережева карта.

При реєстрації в локальній мережі зараженої робочої станції відбувається зараження системних файлів серверу. Інфікування незараженої робочої станції відбувається при реєстрації на зараженому сервері.

•    пристрої зберігання інформації із змінними носіями.

При використовуванні дискет на зараженому комп'ютері відбувається зараження дискет, з яких можна заразити будь-який комп'ютер. Зустрічаються заражені диски -CD-ROM, які, як правило, містять піратське програмне забезпечення.

Виняток становлять пристрої «ручного» введення: клавіатура, миша і т.д.

Сканери вірусів

Обговоримо способи роботи антивірусних програм. У компаній, що займаються розробкою антивірусних програм, є лабораторії, в яких учені проводять довгий годинник, висліджуючи і досліджуючи нові віруси. Перший крок полягає в тому, щоб заразити вірусом програму, що не виконує ніяких функцій, часто звану козлом відпущення, і одержати вірус в його чистісінькій формі. Наступний крок полягає в тому, щоб одержати точний лістинг коду вірусу і помістити його в базу даних відомих вірусів. Компанії змагаються один з одним, намагаючись перевершити конкурента розмірами бази даних. Винахід нових вірусів просто з метою збільшення розмірів бази даних вважається неспортивним.

Після установки на комп'ютері замовника антивірусна програма сканує всі виконувані файли на диску, порівнюючи їх вміст з штамами відомих вірусів, що зберігаються в її базі даних. У більшості компаній, що займаються розробкою антивірусних програм, є свої web-сайти, з яких клієнти даних компаній можуть викачати описи недавно знайдених вірусів в свої бази даних. Якщо у користувача 10 000 файлів, а в базі даних зберігаються дані про 10 000 віруси, то щоб така програма працювала швидко, потрібне дуже розумне програмування.

Оскільки незначні мутації вже відомих вірусів з'являються постійно, антивірусна програма повинна уміти розпізнавати вірус, не дивлячись на зміну в трьох байтах. Проте такий спосіб пошуку не тільки повільніший за точний пошук, але він може привести до помилкових тривог, тобто антивірусна програма видаватиме попередження про незаражені файли, які містять шматок коду, що смутно нагадує вірус, знайдений в Пакистані 7 років тому. Користувач при цьому одержує повідомлення типу

УВАГА! Файл xyz.exe, можливо, заражений вірусом lahore-9x. Видалити?

Чим більше за віруси в базі даних і чим ширші критерії пошуку, тим більше буде помилкових тривог. Якщо їх буде дуже багато, користувач просто перестане запускати антивірусну програму. Але якщо скануюча програма шукатиме дуже точну відповідність, вона може пропустити деякі модифіковані віруси. Знайти золоту середину непросто. У ідеальному випадку лабораторія повинна знайти у вірусі якесь незмінне ядро і використати його для ідентифікації вірусу.

Якщо антивірусна програма не знайшла на диску вірусів минулого тижня, то це не означає, що їх на ньому немає зараз, тому сканувати диск антивірусною програмою слід регулярно. Оскільки процес сканування займає багато часу, істотно ефективніше перевіряти тільки ті файли, які були змінені з моменту останнього сканування. Недолік такого підходу у тому, що розумний вірус обов'язково збереже дату файлу, що заражається їм, щоб уникнути виявлення. Антивірусна програма може перевірити дату останньої зміни каталога, в якому зберігається файл. Вірус може відповісти на це збереженням також дати каталога. Гра в кішки-мишки продовжується.

Антивірусна програма для виявлення зміни файлів може зберігати в своєму файлі на диску довжини всіх файлів. Якщо розмір файлу збільшився з моменту останньої перевірки, це може означати, що він заражений, як показано на рис.2, а і рис.2,б. Проте розумний вірус може перехитрити антивірусну програму, стиснувши інфікований файл і додавши до стислого файлу самого себе і доповнивши довжину файлу до оригінального значення. Щоб ця схема могла працювати, вірус повинен містити процедури стиснення і декомпресії, як показано на рис.2, в.

Мал. 2. Програма (а); інфікована програма (б); стисла інфікована програма (е); зашифрований

вірус (г); стислий вірус із зашифрованою програмою компресії (д)

Інший метод уникнення виявлення полягає в спробі зробити так, щоб зовнішній вигляд вірусу відрізнявся від його уявлення в базі даних. Один із способів досягнення цієї мети полягає у тому, що вірус, заражаючи файл, зашифровує сам себе в цьому файлі, причому кожного разу використовується новий ключ. Перш ніж створити нову копію, вірус формує випадковий 32-розрядний ключ шифрування, наприклад, складаючи по модулю 2 поточний час з вмістом деяких слів пам'яті, скажімо, 72 008 і 319 992. Потім з цим ключем також по модулю 2 складається, слово за словом, весь код вірусу. (Зашифроване тіло вірусу показане темно-сірим кольором на рис.2, р.) Ключ шифрациі зберігається в самому файлі. З погляду секретності приміщення ключа в той же файл не є ідеальним рішенням, але мета тут полягає в тому, щоб обдурити антивірусну програму, а не приховати від дослідників-вірусологів деталі реалізації.

Література:

Симонович С.В. Информатика. Базовый курс, Харьков, 2001 – 640 с. [4], 84-119

Контрольні запитання:

  1.  Як працює алгоритм Хафмана?
  2.  Дайте коротку характеристику файловим вірусам.