File Allocation Methods & Cybersecurity

Section 01

The Story That Explains File Allocation

📖 Real World Analogy

The Airport Baggage Handling System

Imagine an international airport with 100 000 lockers to store passengers' luggage. Three different luggage handlers propose three storage systems.

Handler A insists every passenger's bags must sit in consecutive lockers: bag one in 47, bag two in 48, bag three in 49. Fast to retrieve — just walk down the row. But finding six adjacent empty lockers gets harder every day.

Handler B stores bags wherever there's a gap, and glues a little note inside each locker saying "your next bag is in locker 8034". Great — lockers are always used. But to find a passenger's fifth bag, you must walk through the first four. And if one note gets torn off, everything after it is lost forever.

Handler C gives every passenger a single index card listing all her locker numbers in order: {47, 291, 8034, 12, 99, …}. Fast random access. Compact. But if that one card is destroyed, the whole set of bags is orphaned.

Three trade-offs. In an OS, the "bags" are disk blocks of a file, and the "locker plan" is called a file allocation method. From a cybersecurity standpoint, the choice also determines how easy it is to recover (forensics), destroy (ransomware wipers), or hide (steganography) files.

🛡️

Why Cyber Professionals Study This

When ransomware encrypts a drive, when a forensic analyst tries to reconstruct a deleted file, when an incident responder recovers evidence from a corrupted system — they all need to understand how the file system laid the data out physically. The three classic allocation methods drive three completely different attack surfaces and recovery techniques.

Section 02

Overview — The Three Classical Methods

A file system must solve one central problem: given a stream of file blocks, which physical disk sectors do they live in, and how does the OS find them all at read time? Galvin's textbook groups the answer into three families.

📕

Contiguous

block N, N+1, N+2, ...

Each file occupies a consecutive run of blocks starting at some address. Directory entry stores just start block and length. Very fast, but suffers external fragmentation and rigid growth.

🔗

Linked

chain of pointers

Each block contains a pointer to the next block. Directory entry stores first block. Grows freely, no external fragmentation. But random access is slow, and losing one pointer breaks the rest of the chain.

📋

Indexed

separate index block

Each file has its own index block holding the addresses of all its data blocks. Directory entry points to the index block. Fast random access, no fragmentation — but the index block itself becomes a critical single point of failure.

Section 03

Contiguous Allocation

The simplest scheme. When a file is created, the OS reserves N consecutive blocks for it. The directory entry stores only two fields: the address of the first block, and the total length. To read block k of the file, the OS just seeks to start + k.

Contiguous Allocation — files sit as unbroken runs on disk

Strengths and Weaknesses

✅ Strengths

Fast sequential and random access — only one seek per read

Directory entry is tiny (start + length)

Excellent locality — the disk head barely moves

Used by CD-ROMs, DVDs, and read-only archives

❌ Weaknesses

External fragmentation — free space split into unusable slivers

File growth is a nightmare — no room to extend; must relocate

Requires knowing final file size at creation time

Compaction is expensive (see below)

🛡️

Cybersecurity Angle — The Forensic Investigator's Best Friend

Contiguous allocation is a digital-forensics goldmine. When a file is deleted, its blocks remain intact and adjacent on disk — only the directory entry gets erased. Tools like PhotoRec and Autopsy can carve deleted photos, PDFs, and documents by scanning for well-known file signatures (JPEG "FF D8 FF", PDF "%PDF-", etc.) and reading contiguously until they see an end-of-file marker. This is exactly how many high-profile deleted-evidence recoveries succeed in criminal investigations.

Section 04

Linked Allocation

Instead of forcing every file to be contiguous, why not let it be a linked list of blocks? The directory entry stores only the address of the first block. Each block holds a pointer to the next block. The last block's pointer is null (or −1).

Linked Allocation — file "jeep" scattered across blocks 9 → 16 → 1 → 10 → 25

The FAT Variant — File Allocation Table

The pointer overhead of pure linked allocation is unpopular: each 512-byte block gives up 4 bytes to the next-pointer, leaving 508 for data. Microsoft's FAT (File Allocation Table) family — FAT12, FAT16, FAT32 — moves all the pointers into a single centralised table at the start of the disk. The block itself is 100% data.

🔑

Why FAT Ruled Consumer Computing for Decades

MS-DOS (1981), Windows 95/98/ME, and every USB flash drive shipped before 2010 used FAT. Even today, most SD cards, digital cameras, and boot partitions still use FAT32 or its successor exFAT — because it's simple, patent-free, and readable on every OS on Earth.

Cybersecurity Implications

✅ Advantages

No external fragmentation — any free block works

Files grow trivially — just append a new block to the chain

Small directory entries

❌ Weaknesses & Attack Surface

Slow random access — must traverse chain to reach block k

Fragility — a single bad pointer orphans everything after it

FAT table corruption = entire disk unreadable → target of ransomware

Overhead — pointer per block reduces usable capacity

Section 05

Indexed Allocation

Take all the pointers of a file's chain and put them in one dedicated index block. The directory entry points to the index block, and the index block contains the addresses of every data block. This restores fast random access (jump to entry k of the index → seek to data block k) while keeping the no-fragmentation win of linked allocation.

Indexed Allocation — index block acts as a compact map

Multilevel & Combined Indexing — The UNIX i-node

What if a file is larger than the index block can address? A single 4 KB index block holding 4-byte pointers can only reference 1024 data blocks = 4 MB — hopeless for modern files.

UNIX i-nodes solve this with a combined scheme: some pointers in the i-node point directly to data blocks, others point to intermediate index blocks that hold more pointers. This allows small files to be accessed with one indirection, while huge files use more.

UNIX i-node — Combined Direct + Single/Double/Triple Indirect

📈

Why This Design Won

Real workloads follow a heavy tail: most files are tiny (config files, shell scripts, cookies), a few are enormous (video, VMs). The i-node scheme optimises for both: small files reach data in one seek; giant files still work through multiple levels of indirection. This is why UNIX, Linux (ext2/3/4), and BSD variants all use i-node style indexed allocation.

Section 06

Practical Example — Reading a File Byte by Byte

A concrete walkthrough. Suppose block size = 4 KB, and we want to read byte offset 10 240 from a file. How does each method find it?

📋 Block Arithmetic First

Compute

Logical block number k = 10 240 / 4096 = 2. Offset within block = 10 240 mod 4096 = 2048.

Task

We need to read block 2 of this file. Where is it physically?

Contiguous

// directory entry: start = 100, length = 8
physical_block = start + k = 100 + 2 = 102
// One seek. Done.

Linked

// directory entry: first_block = 47
block = 47                              // start with first
block = read_ptr_field(47)              // walk to block 1 → returns 291
block = read_ptr_field(291)             // walk to block 2 → returns 8034
// Three seeks to reach block 2. For block k, we do k seeks. Slow.

Indexed

// directory entry: index_block = 42
index = read_block(42)                 // seek 1: fetch the whole index
physical_block = index[2]                 // look up entry 2 in memory
data = read_block(physical_block)          // seek 2: fetch the data
// Exactly 2 seeks regardless of k. Fast and predictable.

🏆

Summary

Contiguous: 1 seek. Indexed: 2 seeks. Linked: k+1 seeks. This is why databases, virtual memory backing stores, and video editing scratch files never use linked allocation — they need predictable random access to random offsets.

Section 07

Comparison — Which Method for Which Job?

Property	Contiguous	Linked	Indexed
Sequential access	Excellent	Good	Good
Random access	Excellent	Poor	Good
External fragmentation	Yes — major problem	None	None
Internal fragmentation	Minimal	Minimal	Small (last block)
File growth	Painful — may relocate	Easy	Easy
Directory-entry size	Tiny (start + length)	Tiny (first block)	Small (index-block ptr)
Overhead per file	None	1 ptr per data block	1 index block per file
Fault tolerance	Medium	Very low — chain breaks	Low — index corruption fatal
Used by	CD-ROMs, DVDs, archive tapes	MS-DOS FAT, Windows FAT32/exFAT	UNIX ext2/3/4, Solaris UFS

Section 08

Real-World Case Studies — Newspaper Headlines

File allocation isn't just an academic curiosity. Every major cyber incident of the last decade has had a file-system dimension. Here are four widely-reported cases.

💥

NotPetya, June 2017

Called by Wired's Andy Greenberg "the most devastating cyberattack in history" — damages exceeded $10 billion. NotPetya masqueraded as ransomware but was a state-attributed wiper that overwrote the NTFS Master File Table and MBR. Because NTFS uses indexed allocation, destroying the MFT effectively wiped every file's metadata — the data blocks were physically intact but unreachable. Covered extensively by Reuters, The Guardian, and BBC News.

NTFS · MFT wipe · Indexed allocation

📁

Panama Papers, April 2016

The International Consortium of Investigative Journalists (ICIJ), Süddeutsche Zeitung, and The Guardian published 11.5 million documents leaked from Panamanian law firm Mossack Fonseca. Recovery of deleted email attachments used classical file-carving techniques — scanning contiguous disk regions for JPEG/PDF/DOCX magic bytes. This is exactly the recovery technique contiguous allocation makes possible even after directory entries are gone.

Forensic carving · Contiguous recovery

🎥

Sony Pictures Attack, November 2014

The New York Times, Reuters, and The Washington Post documented how the "Guardians of Peace" attackers deployed the Shamoon-family wiper. It targeted disk-partition tables and file-allocation structures directly — analogous to the NotPetya technique three years later. Recovery required rebuilding from tape backups.

Disk-level destruction · Wiper malware

🔥

WannaCry Ransomware, May 2017

Reported by BBC News, Reuters, and The Times: 200 000 Windows machines across 150 countries had their files encrypted, most notably shutting down the UK NHS for days. WannaCry didn't destroy allocation structures — it encrypted individual files in-place, blocking read access even though the file system's index still resolved them. The distinction matters for recovery: allocation-metadata attacks require rebuilding indexes; encryption attacks require the key.

In-place encryption · Directory intact

📡

Colonial Pipeline, May 2021

Covered by The Wall Street Journal, Bloomberg, and The New York Times: DarkSide ransomware forced the shutdown of the largest US fuel pipeline for six days. Post-incident forensics reconstructed the file system's exfiltrated regions by analysing recovered i-nodes and NTFS MFT records — showing how modern indexed allocation can be an ally to defenders as well as an attack surface.

Post-incident forensics · MFT analysis

🔑

Vault 7 CIA Leak, March 2017

WikiLeaks published — as reported by The Guardian, The New York Times, and Reuters — a trove of CIA hacking tool documentation. Several tools targeted file-system-level implants, exploiting the fact that i-node metadata (timestamps, permissions, block pointers) can be spoofed to hide files or make malicious binaries look like legitimate system files. Detection required cross-checking i-node block-pointer chains against on-disk reality.

Anti-forensics · Timestomping

Section 09

Cybersecurity Considerations for Each Method

Contiguous Allocation — the Forensic Analyst's Ally

🛡️ Security Profile of Contiguous

Recovery

Deleted files are trivially recoverable via file carving. This is good for forensics, bad for privacy. A stolen disk containing deleted secrets is a treasure trove.

Wiping

Secure erasure requires overwriting the full contiguous run. Standards like DoD 5220.22-M and NIST SP 800-88 specify multi-pass overwrites.

Steganography

Unused blocks (gap regions from fragmentation) can be used to hide data. Tools like slacker exploit this. Investigators must scan gaps too.

Attack surface

Small — only the directory entry's start/length pair needs corrupting to lose a file. Compact metadata is a double-edged sword.

Linked Allocation — Fragile but Anonymous

🛡️ Security Profile of Linked

Recovery

Harder than contiguous — must reconstruct the pointer chain. Tools like testdisk can rebuild FAT chains by scanning for continuation patterns.

FAT corruption

Single point of failure. Ransomware historically targeted FAT tables directly. FAT32 keeps two copies of the table as a mitigation.

Chain-break attack

Zero out one pointer in the middle of a chain → OS reports file as "shorter than actual size" while leaked bytes sit unmapped on disk. Classic anti-forensics technique.

Scattering

Data can be scattered across the disk in ways that resist sequential-scan carving. Slight forensic obscurity — files aren't in one place.

Indexed Allocation — Powerful, Concentrated Attack Surface

🛡️ Security Profile of Indexed

MFT / i-node table

The critical structure. Destroying it — as NotPetya did to NTFS — makes every file's data blocks inaccessible even though the data survives physically. High-value target for wipers.

Timestomping

Attackers modify i-node timestamps to hide when a malicious file was created. Standard anti-forensic technique. Detection: compare against $LogFile or NTFS $UsnJrnl.

Alternate Data Streams (NTFS)

NTFS lets a file have multiple "streams" — one file, many hidden payloads. Malware families hide code in ADS attached to legitimate files. dir /R and streams.exe reveal them.

Journaling saves

Modern indexed file systems (NTFS, ext4, XFS) use journals that let forensic tools reconstruct recent changes even after directory corruption. Read $LogFile on NTFS or the ext4 journal to see what was modified before the incident.

Section 10

Digital Forensics — What the Investigator Actually Does

When law enforcement or an incident-response team receives a compromised drive, they apply the following method-aware playbook:

Image the disk read-only

Use a hardware write-blocker + tools like dd, dc3dd, or FTK Imager. Never mount the original for writing; work off the image. Preserves chain-of-custody.

Identify allocation method

Read the boot sector. FAT/exFAT → linked-style. NTFS → indexed with MFT. ext2/3/4 → indexed with i-nodes. HFS+/APFS → indexed with B-trees. Different methods, different next steps.

Parse metadata

Tools like Autopsy, X-Ways, and The Sleuth Kit walk the MFT / i-node table to enumerate every known file (present and deleted). Timestamps, sizes, and permission changes get logged.

File carving

For files whose metadata is destroyed, scan the raw disk for signatures (JPEG headers, PDF markers, ZIP EOCDs). This is where contiguous allocation shines — deleted files often come back cleanly.

Timeline reconstruction

Cross-reference file timestamps with journal entries (NTFS $LogFile, ext4 journal), event logs, and registry hives to reconstruct attacker actions. Timestomping is caught here.

Section 11

Cybersecurity Best Practices for System Administrators

🔐 Practices to Harden the File System

Never trust a single allocation table. Modern file systems keep redundant copies (NTFS's mirrored MFT, ext4's backup superblocks, FAT's dual tables). Verify redundancy is enabled during formatting.

Enable journaling. NTFS, ext4, XFS, ZFS all provide journals. A journal is the difference between "we know what changed" and "the disk is a mystery" after a crash or attack.

Use full-disk encryption. BitLocker, LUKS, FileVault all encrypt the raw disk blocks, so an attacker who steals the physical drive sees only ciphertext — allocation metadata and all. Defeats offline carving of deleted files.

Monitor MFT / i-node table integrity. Tools like Tripwire, AIDE, and commercial EDRs baseline critical structures and alert on unauthorised modification. Wipers hitting the MFT trip this alarm before user-visible damage.

Follow NIST SP 800-88 for erasure. When disposing of drives, a simple "delete" leaves data trivially recoverable. Cryptographic erase (destroying the encryption key) or multi-pass overwrite is required.

Scan for Alternate Data Streams. Windows environments should periodically enumerate ADS with dir /R or the Sysinternals streams tool. Many malware families hide payloads there.

Keep offline backups. The one thing that beats every allocation-level attack — including NotPetya-style MFT destruction — is a backup on media the attacker cannot reach. Air-gapped tapes, immutable object storage (S3 Object Lock), or hardware write-once media.

Understand your storage stack. When responding to incidents, knowing whether the system uses NTFS, ext4, or ZFS changes the tools, the timeline, and the chances of recovery. Cybersecurity teams should include a file-system specialist.

Section 12

Golden Rules — File Allocation Methods

🔑 Galvin's Non-Negotiable Rules

File allocation methods answer one question: given a file, where do its blocks live on disk? Three families: Contiguous, Linked, Indexed.

Contiguous allocation is fastest and simplest but causes external fragmentation and forbids easy file growth. Used by read-only media like CD-ROMs and DVDs.

Linked allocation eliminates fragmentation and supports free growth, but random access is O(k) — must walk the chain. FAT (Microsoft's variant) centralises the pointers into a table to speed up traversal.

Indexed allocation puts all pointers in a dedicated index block per file. Fast random access, no fragmentation — the modern default (UNIX i-node, NTFS MFT).

UNIX i-nodes use a combined scheme: 12 direct pointers plus single/double/triple indirect blocks. Small files → one seek; huge files → up to four seeks.

Every allocation method has a concentrated attack surface. Contiguous: directory entry corruption. Linked: chain breaks / FAT wipes. Indexed: MFT / i-node table destruction.

Modern wiper malware (NotPetya, Shamoon) targets allocation-metadata directly because it wipes 100 TB of data by destroying a few MB of indexes. Wired's coverage of NotPetya is the go-to case study.

Digital forensics uses knowledge of allocation methods to recover deleted files. Contiguous allocation is the easiest to carve; indexed is the richest source of metadata (timestamps, permissions).

Enable journaling and redundancy for production systems, use full-disk encryption for confidentiality, and follow NIST SP 800-88 for secure erasure. These practices defeat most allocation-level attacks.

The best defence against any file-system attack is a fresh offline backup. Colonial Pipeline (2021), NotPetya (2017), and WannaCry (2017) all had one thing in common: victims with clean offline backups recovered faster and paid no ransom.