Восстановление повреждённых файлов

Повреждённый файл – это последовательность байтов, нарушившая свой контракт: часть данных утрачена/искажена, метаданные (размер, смещения, контрольные суммы) неконсистентны, логическая структура (заголовки, индексы, таблицы, карты блоков) не согласована. Причины: сбой питания, «незавершённая» запись, деградация носителя, ошибки ПО/драйвера, логические ошибки пользователя.

Почему восстановление возможно:

1. Избыточность (контрольные суммы, копии метаданных, резервирование в ФС и RAID).
2. Самоописываемость формата (заголовки/magic, длины секций, индексы).
3. Локальность ошибок (часто повреждён фрагмент при сохранении целостности остального).
4. Коды исправления ошибок (ECC-страйпы на носителях, Hamming/Reed–Solomon в контейнерах).

Связь с ЕГЭ: тема развивает навыки кодирования информации, работы с двоичными структурами, оценок надёжности, доказательства корректности алгоритмов и чтения формальных спецификаций.

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

1. Типы повреждений (уровни)
   

   • Физический уровень: отдельные биты/байты меняются (bit rot), «дыры» нулей/мусора, bad-blocks.

   • Логический уровень ФС: потеря ссылок, рассинхронизация таблиц размещения (FAT), журнала (NTFS/EXT), деревьев (B-tree).

   • Прикладной уровень формата: нарушены поля заголовка, длины, индексы; потеря «хвоста» файла.

2. Формализация
   

   Пусть идеальный файл – массив байтов X = (x0, x1, …, x_{L-1}). Повреждение – применение помехового оператора E:

   Y = E(X),  где E изменяет/удаляет/вставляет подпоследовательности.

   Цель восстановления – найти оценку X̂, минимизирующую невязку:

   minimize  D(X, X̂)  при выполнении структурных ограничений формата.

   Часто D – число изменённых байтов, а структурные ограничения задают корректные заголовки, индексы и согласованность размеров.

Обнаружение и локализация ошибок: контрольные суммы и хеш-функции

1. Контрольные суммы и вероятности недетектирования
   

   • Сумма по модулю 2^k: быстро, слабо.

   • CRC (циклические избыточные коды): хорошо ловят burst-ошибки.

   • Криптохеши (SHA-2/3): для целостности/подлинности; тяжелее, но устойчивы к коллизиям на практике.

   Вероятность недетектирования (упрощённая оценка):

   P_undetected ≈ 1 / 2^r

   где r – длина контрольного кода (бит).

2. Полезные формулы
   

   Скалярная контрольная сумма:

   S = ( Σ_{i=0..L-1} x_i ) mod 2^32

   Фрагментная валидация (скользящая):

   S_j = ( Σ_{i=j..j+m-1} x_i ) mod 2^32

   Позволяет локализовать повреждение по «окнам».

3.  Практическое правило C-VALID
   

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

   C2  Если есть фрагментные/страничные CRC – используйте их для бинарного поиска повреждённых отрезков.

   C3  При отсутствии контрольных сумм – переходите к структурной валидации формата (magic, длины, индексы).

Исправление ошибок: от простых паритетов к Hamming и Reed–Solomon

1. Паритет и Hamming (одно-битовые исправления)
   

   • Паритет (чётный/нечётный): только обнаружение.

   • Код Хэмминга (7,4) исправляет 1 бит, обнаруживает 2:

   d_min = 3  ⇒ исправляет t = ⌊(d_min−1)/2⌋ = 1

   Общее правило:

   t = ⌊(d_min − 1) / 2⌋

   где d_min – минимальное кодовое расстояние.

2. Reed–Solomon (RS) – исправление блоковых «бурстов»
   

   Параметры RS(n, k) над GF(2^8):

   n – длина кодового слова (байт), k – полезные байты, n−k = 2t  (исправляет t байт-ошибок)

   В контейнерах (оптические носители, архивы) RS позволяет восстановить «выпавшие» последовательные байты.

   Правило ECC-USE

   E1  Если формат/контейнер содержит ECC – начинайте с штатного декодера (RS/BCH).

   E2  При отсутствии ECC – используйте внешние паритетные архивы (PAR2) или избыточное резервирование.

Форматы и структурная реконструкция: «понять и собрать»

1. Самоописываемые форматы
   

   • Медиа-контейнеры (PNG, JPEG, MP4, MKV): сигнатуры (magic), TLV-структуры, длины секций, локальные CRC.

   • Архивы (ZIP): локальные и центральные директории, дублирование заголовков.

   Правило S-STRUCT

   S1  Сначала восстановите «скелет»: заголовок(и), таблицу индексов, смещения.

   S2  Проверяйте монотонность смещений и суммарные длины.

   S3  При потере индекса – карвинг по сигнатурам с верификацией локальных CRC/длин.

2. Карвинг (carving) и сборка фрагментов
   

   Карвинг – поиск по сигнатурам/структурным маркерам и извлечение полезных сегментов даже без ФС-метаданных. Стыковка фрагментов – по:

   • совпадению продолжений (контекстные байты),

   • согласованности длин/CRC,

   • временным меткам/монотонности кадров.

Роль файловых систем и журналов: от FAT до COW

1. FAT/ExFAT
   

   Главные таблицы размещения (FAT) и дубли; корневой каталог с 8.3/длинными именами. Восстановление: анализ дубликатов FAT, связностей цепочек кластеров.

2.  NTFS
   

   MFT (Master File Table), журнал ($LogFile), альтернативные потоки, атрибутная модель. Восстановление: поиск «живых» записей MFT, журналирование транзакций.

3. Ext3/4
   

   Журнал (JBD/JBD2), группы блоков, таблицы инодов, bitmaps. Восстановление: реплеи журнала, реконструкция каталогов по деревьям хешей.

4.  Копирование-при-записи (ZFS/Btrfs)
   

   COW-пойнты, чек-суммы на каждом блоке, снапшоты. Восстановление: откат к снапшоту, репликация, scrub (прочистка по чекам).

   Правило FS-SAFE

   F1  Никогда не работайте по месту: создайте образ носителя «бит-в-бит».

   F2  Сначала восстановите метаданные ФС (таблицы/журналы), затем пользоват. данные.

   F3  При COW-ФС используйте снапшоты, не нарушая ссылочную целостность.

Процедурная методика восстановления: от теории к практике

1. Подготовка и имиджирование
   

   1. «Только чтение»: задействуйте интерфейсы/режимы без записи.

   2. Снимите образ (RAW) всего носителя:

   IMG := READ(device, 0 .. size−1)

   1. Зафиксируйте криптохеши образа:

   H = SHA256(IMG)

   Правило I-HASH: все операции далее – над копией; целостность подтверждается совпадением H.

2. Диагностика и локализация
   

   • Прогон скользящих контрольных сумм по образу;

   • Сканирование ФС-метаданных;

   • Поиск сигнатур форматов (карвинг);

   • Сбор карты «хороших/плохих» областей.

3. Ремонт и реконструкция
   

   • Структурный ремонт: правка заголовков/индексов (с резервными копиями);

   • Фрагментная реконструкция: склейка по длинам/CRC и контексту;

   • Использование ECC/избыточности: RS/PAR2, RAID-паритет.

4.  Валидация результата
   

   • Пере-расчёт контрольных сумм и сравнение с «эталонными» (если есть);

   • Проверка воспроизводимости (например, раскадривание видео/аудио);

   • Дифференциальная проверка: H(new) == H(reference) для известной части.

RAID и внешняя избыточность: восстановление по паритетам

1. RAID-1/10
   

   Зеркалирование: возьмите целые блоки с «живой» копии.

2. RAID-5 (один паритет)
   

   Для блока на позиции j:

   P = B0 ⊕ B1 ⊕ ... ⊕ B_{n-2}   (без самого P)

   Если «выпал» один блок Bk:

   Bk = P ⊕ ( ⊕_{i≠k} B_i )

3.  RAID-6 (два паритета)
   

   Добавляется независимый второй код (обычно RS над GF(2^8)) ⇒ корректируется до двух утерь.

   Правило RAID-REC

   R1  Зафиксируйте порядок дисков и размер страйпа.

   R2  Проверьте согласованность супермэт и метаданных массива.

   R3  Восстановление – на образах дисков, а не на «живых» носителях.

Оценка надёжности и вероятностные модели

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

P(без ошибок) ≈ (1 − p_b)^L  ≈  exp( − p_b * L )

Вероятность недетектирования при CRC-r:

P_undetected ≈ 1 / 2^r

При наличии страйповой ECC (RS):

исправляем до t байт-ошибок в каждом кодовом слове длиной n; вероятность невосстановимости падает экспоненциально при разумном t.

Чек-лист правил корректности и безопасности

R/O  Работайте только с копией (образом); исходный носитель не трогайте.

HASH Фиксируйте и сверяйте хеши образа и результатов.

MAP  Стройте карту плохих блоков; читайте с повторами, увеличивая таймауты.

FS   Сначала метаданные ФС (журнал, таблицы), потом содержимое.

SIG  Используйте сигнатуры и структурную валидацию (magic, длины, CRC).

ECC  При наличии ECC/RAID – применяйте штатные декодеры/паритеты.

IDX  Никогда не «чините на глазок»: сохраняйте версии каждый шаг (copy-on-write).

WIN  Карвинг с «скользящими окнами» и повторной валидацией сегментов.

DOC  Документируйте все операции: офсет, размер, до/после хеши.

VAL  Подтверждайте результат функционально (открывается? декодируется? проверяется CRC?).

Типичные ошибки и анти-паттерны

1. «Лечить на месте» → усугубление потерь.
2. Игнорировать контрольные суммы и размеры → неконсистентные сборки.
3. Неправильный порядок дисков RAID → «корректный мусор».
4. Попытки «исправить» криптохешуемый контейнер без ремапа метаданных → неизбежная невалидность.
5. Отсутствие журналирования действий → неоткатные ошибки.

Мини-шпаргалка (копируемые формулы/шаблоны)

Сумма (mod 2^32):   S = ( Σ x_i ) mod 2^32

CRC недетект.:      P ≈ 2^(−r)

RS(n,k):            t = (n − k)/2  (байт-ошибок на кодовое слово)

RAID-5 блок:        Bk = P ⊕ ( ⊕_{i≠k} B_i )

Вероятность безош.: P ≈ exp( − p_b * L )

Дист. Хэмминга:     t = ⌊(d_min − 1)/2⌋

Связь с ЕГЭ по информатике

• Кодирование информации: понимание Хэмминга, CRC, контрольных сумм.
• Алгоритмы и структуры: работа со смещениями, таблицами, индексами, графами ссылок.
• Оценка надёжности: вероятностные расчёты, экспоненциальные приближения.
• Практикум: строгое следование спецификациям, проверка инвариантов, доказательство корректности шагов восстановления.

Пять упражнений 

Упражнение 1. Локализация повреждения по скользящей сумме

Дан файл длиной L = 10^6 байтов. Известно, что в нём один короткий «бурст» повреждения длиной не более m = 4096.
a) Предложите алгоритм бинарного поиска повреждённого окна по скользящей сумме:

S_j = ( Σ_{i=j..j+m−1} x_i ) mod 2^32

b) Оцените трудоёмкость в худшем случае.
c) Обоснуйте, почему при независимых ошибках вероятность ложноположительного совпадения мала.

Упражнение 2. RS-контейнер

Контейнер кодируется RS(n=255, k=223) над GF(2^8).
a) Сколько байт-ошибок исправляется в каждом кодовом слове?
b) Как изменится избыточность при переходе на RS(255, 191)?
c) Объясните компромисс «избыточность ↔ надёжность».

Ответ-намёк: t = (n−k)/2: для (255,223) ⇒ t=16; для (255,191) ⇒ t=32, но избыточность выше.

Упражнение 3. Восстановление RAID-5 блока

Даны блоки страйпа: B0, B1, B2, P, где

P = B0 ⊕ B1 ⊕ B2

Утерян B1.
a) Запишите формулу для восстановления B1.
b) Если длина блока 64 КБ, оцените время восстановления при скорости чтения 200 МБ/с.
c) Почему важно знать точный порядок дисков?

Упражнение 4. Карвинг PNG

В образе диска отсутствуют записи ФС. Требуется извлечь PNG-изображения.
a) Укажите сигнатуру PNG и структуру первого чанка.
b) Предложите алгоритм карвинга с верификацией CRC каждого чанка.
c) Как корректно разруливать фрагментацию (несмежные части файла)?

Напоминание: магия PNG: 89 50 4E 47 0D 0A 1A 0A; чанк: [Length(4)][Type(4)][Data][CRC(4)].

Упражнение 5. Ремонт заголовка ZIP

ZIP-архив частично повреждён: центральная директория утеряна, локальные заголовки присутствуют.
a) Опишите процедуру восстановления центральной директории из локальных заголовков.
b) Какие поля критичны для согласования (смещения, размеры, CRC32)?
c) Как убедиться, что восстановленный архив корректен?

Заключение

Восстановление повреждённых файлов – это строго формализуемая задача: мы используем коды контроля/исправления, структурную валидацию форматов, метаданные ФС и внешнюю избыточность (RAID/архивы), чтобы из последовательности байтов, претерпевшей возмущение, собрать юридически корректный и практически работоспособный объект. Ключевые идеи – неразрушающая работа с образами, локализация ошибки, поэтапный ремонт и многоуровневая верификация.

Для подготовки к ЕГЭ по информатике эта тема укрепляет инструментарий работы с двоичным представлением, контрольными суммами, вероятностными оценками и алгоритмической строгостью: умением читать спецификации, проектировать алгоритмы и подтверждать их корректность проверками и инвариантами.