21. září bude sraz! Od 18.00 v restauraci Tradice v Praze u Anděla
Autor Zpráva
lucasso
Profil *
Ahoj přátelé.
Dostal se ke mně zajímavý dotaz a zajímalo by mě, jak byste se k tomu postavili vy a co byste navrhovali?

Máte běžný HDD na kterém někdo vytvořil náhodně kopie již existujících souborů. Vznikly
tak duplicity, které byste chtěli detekovat. Protože dotyčný útočník při kopírování
neponechával stejné názvy, není možné k detekci využít názvů souborů. Popište způsob jak
byste postupovali tak, abyste na disku našli všechny duplicitní soubory (zajímá nás jaký soubor
a kolikrát se na disku vyskytuje). Zkuste vymyslet takové řešení, které poběží co nejrychleji.

Moderátor Petr ZZZ: Titulek „zajímavý dotaz“ nevystihoval podstatu dotazu. Příště zkus prosím vymyslet lepší. — Přesouvám z PHP.
Moderátor Chamurappi: Odtučněno.
mimochodec
Profil
To nesouvisí s tvorbou webu, natož s php. Navíc to vypadá jako nějaká školní úloha, byť ne úplně triviální.
Ale ok. V reálu bych našel jednu tu kopii ručně a pak vyhledal všechny soubory, které vznikly přibližně ve stejném čase. Kdyby tu udělal skript, dala by se k detekci možná použít i nějaká jeho logika. Třeba kdyby se ty kopie jmenovaly puvodninazev_tohlesemprilepilutocnik.jpg
Kdybych měl nějakou množinu podezřelých souborů a chtěl mít jistotu, asi bych pohledal přesně stejně velké soubory a případně si z nich vytáhl pro ověření namátkově pár znaků.
weroro
Profil
Neviem ako je to s rýchlosťou, ale aj pri kontrole veľkosti súboru sa môže stať, že budú mať dva rozdielne súbory veľkosť rovnakú. Asi by som to skúsil porovnávaním hashu súborov.
Keeehi
Profil
lucasso:
Zvolil bych kombinaci 3 postupů. Porovnání velikosti, porovnání hashů souborů a porovnání souborů bajt po bajtu. Nejprve porovnáme velikosti všech souborů a rozdělíme je do skupin dle stejné velikosti. V těchto skupinách se pokusíme najít shodné soubory. Když je skupina malá nebo soubory budou malé, bude výhodnější je porovnávat bajt po bajtu. Od určité meze je však výhodnější počítat hashe všech souborů a porovnávat ty. Stejné soubory mají stejný hash a rozdílné soubory mají s vysokou pravděpodobností rozdílný hash. Kde je ta mez by se samozřejmě muselo určit podle konkrétního systému. *

Ještě chci upozornit na to, že zadání je neúplné. Chybí tam totiž informace, co za souborový systém na disku je protože různé systémy mají různé parmetry. Postup výše bude fungovat pro velkou část souborových systém, ale existují i takové, u kterých by se to dalo udělat jednodušeji, nebo naopak by tento působ nebyl vůbec použitelný vzhledem k parametrům souborového systému. Pro představu: Souborový systém ZFS má hashe uložené pro každý soubor. Můžeme porovnávat tedy rovnou hashe, protože nám to nepřináší žádnou výkonovou ztrátu. Naopak existuje třeba souborový systém, kde nejdříve je nutné přečíst celý disk abychom vůbec zjistili, co za soubory tam vůbec je a jaké mají parametry. Dokážu si taky představit (možná i existuje) souborový systém, ve ktrém při kopírování souboru vlastně ke kopiím nedochází, ale systém si pouze pamatuje, že nějaká dvě různá pojmenování ukazují na ten samý soubor. Takovýto systém dokáže kopie vyhledat velmi rychle.


* Není to 100% metoda. Protože se dají vytvořit rozdílné soubory které budou mylně považovány za shodné. Ovšem takovéto soubory vytvořené přesně pro to, aby postup selhal nebudou v reálném použití prakticky existovat. Takže tato metoda je dostatečně dobrá pro reálné použití.
Bubák
Profil
Vyhledání shodných souborů umí Třebas TotalCommander, při hledání souborů stačí na kartě "Rozšířené" mít nezatržené políčko "Stejný název" a zaškrtnout políčko "Stejný obsah". Mám za to, že další nastavení nebude zapotřebí a pokud ano, tak jsou dostatečně intuitivní.
juriad
Profil
Keeehi:
Dokážu si taky představit (možná i existuje) souborový systém, ve ktrém při kopírování souboru vlastně ke kopiím nedochází, ale systém si pouze pamatuje, že nějaká dvě různá pojmenování ukazují na ten samý soubor.
Existují, treba Btrfs nebo to zmíněné ZFS. Tam kopie souboru jen poznamená nový pointer na data, dokud uživatel na jednom z míst soubor nezmění. Toto však funguje jen při kopírování v rámci filesystému. Existuje však řešení i kopírování zvenku.
Tyto dva filesystémy podporují deduplikaci - proces, který běží a hledá shodné bloky* a upravuje pointery na data těch duplicitních souborů.

* Funguje to raději na úrovni bloků než celých souborů, protože pro malé soubory je to to samé, pro velké prostě najde duplicity více bloků. Ale v případě velkých podobných souborů, třeba virtuální disky, které můžou mít desítky gigabytů, ale liší se jen nepatrně (všechny třeba vznikly kopií jednoho originálu), to může uspořit ohromné množství dat.

Tyto nízkoúrovňové věci možná dokáží na zadané otázky odpovídat (snad stačí online při deduplikaci). Asi by byl problém se zjišťováním názvů těch duplicitních souborů, získat informaci o počtu kopií by však bylo snadné. Ale v případě použití těchto filesystémů nejspíš nezáleží na duplicitě souborů, protože eventuálně nezabírají žádné místo.

lucasso:
Jaké prostředky máš k dispozici? Řešíš úlohu na úrovni souborů nebo máš povoleno jít níže?
Chceš to řešit online (za konání útočníka) nebo offline (již máš disk obsahující duplicity)?
O jakých objemech dat se bavíme? Megabyty, gigabyty, terabyty? Ještě víc?

Vaše odpověď


Prosím používejte diakritiku a interpunkci.

Ochrana proti spamu. Napište prosím číslo dvě-sta čtyřicet-sedm:

0