blekinge, Author at Open Preservation Foundation

February 23 2012

Identification tools, an evaluation

blekinge Corpora, Fido, Identification, SCAPE, Web archiving 4

The Scape Characterisation Tool Testing Suite

This information have also been published in the Scape Deliverable D9.1.

We have created a testing framework based on the Govdocs1 digital Corpora (http://digitalcorpora.org/corpora/files), and are using the characterisation results from Forensic Innovations, Inc. ((http://www.forensicinnovations.com/), as ground truths.

The framework we used for this evaluation can be found on

https://github.com/openplanetsfoundation/Scape-Tool-Tester

All the tested tools use a different identification scheme for formats of files. As a common denominator, we have decided to use Mime Types. Mimetypes are not detailed enough to contain all the relevant information about a file format, but all the tested tools are capable of reducing their more complete results to mimetypes. This thus ensures a level playing field.

The ground truths and the corpus

The govdocs1 corpus is a set of about 1 million files, freely available (http://digitalcorpora.org/corpora/files). Forensic Innovations, Inc. (http://www.forensicinnovations.com/) have kindly provided the ground truths for this testing framework, in the form of http://digitalcorpora.org/corp/files/govdocs1/groundtruth-fitools.zip. Unfortunately, they do not list mimetypes for each file, but rather a numeric ID, which seems to be vendor specific. They do provide this mapping, however, http://www.forensicinnovations.com/formats-mime.html, which allows us to match IDs to mimetypes. The list is not complete, as they have not provided mimetypes for certain formats (which they claim do not have mimetypes). For the testing suite, we have chosen to disregard files that Forensic Innovations, Inc. do not provide mimetypes for, as they make up a very small part of the collection. The remaining files number 977885.

The reduced govdocs1 corpus contains files of 87 different formats. These are not evenly distributed, however. Some formats are only represented by a single file, while others make up close to 25% of the corpus.

To display the results, we have chosen to focus on the 20 most common file formats in the corpus, and to list the remainding 67 as the long tail, as these only make up 0.56% of the total number of files in the corpus.

Format Distribution in Govdocs

One interesting characteristic of the ID-to-mime table from Forensic Innovations, Inc. is that each format only have one mimetype. Now, in the real world, this is patently untrue. Many formats have several mimetypes, the best known example probably being text/xml and application/xml. To solve this problem, we have introduced the mimetype-equivalent list, which ammends the ground truths with additional mimetypes for certain formats. It should be noted that this list have been constructed by hand, simply by looking at the result of the characterisation tools. Any result that do not match the ground truth is recorded as an error, but inspection of the logs later have allowed us to pick up the results that should not have been errors, but rather alias results.

The test iterator

We have endeavoured to use the tools in a production-like way for benchmarking purposes. This means that we have attempted to use the tools’ own built-in recursion features, to avoid redundant program startups (most relevant for the java based tools). Likewise, we have, if possible, disabled those parts of the tools, that are not needed for format identification (most relevant for Tika). We have hidden the filenames from the tools (by simple renaming the data files), in order to test their format identification capabilities, without recursion to file extension.

Versions

Tika: 1.0 release

Droid: 6.0 release, Signature version 45

Fido: 0.9.6 release

Tika – a special note

For this test, Tika have been used as a java library, and have been wrapped in a specialised Java program (https://github.com/blekinge/Tika-identification-Wrapper). This way, we can ensure that only the relevant parts of Tika is being invoked (ie. identification) and not the considerably slower metadata extraction parts. By letting java, rather than the test framework handle the iteration over the files in the archve, we have also been able to measure the performance in a real massprocessing situation, rather than the large overhead in starting the JVM for each file.

Results

We have tested how precisely the tools have been able to produce results to match the ground truths. As stated, we have focused on the 20 most common formats in the corpus, and bundled the remainder into a bar called the Long Tail.

Precision

As can be seen from this graph, Tika generally performs best for all the 20 most common formats. Especially for text files (text/plain), it is the only tested tool that correctly identifies the files. For office files, especially excel and powerpoint, droid seems to be more precise. Tika is almost as precise, but Fido loses greatly here. Given that Fido is based on the Droid signatures, it might be surprising why it seems to outperform Droid for certain formats, but this is clear for pdf, postscript and rich text format. The authors will not speculate on why this is so.

Comma/tab separated files are fairly common in the corpus. Tika cannot detect this feature of the files, and recognize them as text/plain files. Fido and Droid fails to identify the files, just as they do for text/plain files.

The dBase files, a somewhat important feature of the corpus is not detected by any of the tools.

Only Tika identifies any files as rfc2822, and even then it misses a lot. All three tools are equally bad at identifing sgml files.

Interestingly, Droid and Fido seems to work much better than Fido on the long tail of formats.

The Long tail

We feel that the long tail of formats is worth looking more closely at.

The long tail

In this table, we have removed any format where none of the tools managed to identify any files. So, this table is to show the different coverage of the tools. We see that it is not just different levels of precision that matter, but which formats are supported by which tools.

Droid and fido support the Fits image format. Tika does not. Tika however, supports the openxml document format, which Fido and Droid does not.

Application pdf and application xml are some rather odd files (otherwise the ground truths would have marked them as normal pdfs or xmls). Here Tika is worse than the other tools. Tika, however, is able to recognize RDF, as shown by the application/rdf+xml format.

It is clear that while the overall precision in the long tail is almost equivalent for the three tools, the coverage differs greatly. If Tika, for example, gained support for the fits image format, it would outperform Droid and Fido on the long tail. Droid and Fido, however, would score much higher, if they gained Tikas support for Microsoft openxml documents.

The speed of the tools

For production use of these tools, not just the precision, but also the performance of the tools are critical. For each tool, we timed the execution, to show us the absolute time, in which the tool is able to parse the archive. Of course, getting precise numbers here is difficult, as keeping an execution totally free of delays is almost impossible on modern computer systems.

We ran each of the tools on a dell poweredge m160 blade server, with two Intel(R) Xeon(R) CPU X5670 @ 2.93GHz. The server had 70 GB RAM, in the form of 1333MHz Dual Ranked LV RDIMMs.

The corpus was mounted on file server accessed through a mounted Network File System via Gigabit network interface.

Each of the tools were allowed to run as the only significant process on the given machine, but we could not ensure that no delayes were caused by the network, as this was shared with other processes in the organisation.

Speed test

To establish baselines, we have added two additional ”tools”, the unix File tool and the md5 tool.

The Unix File tool check the file headers against a database of signatures. Being significantly faster than the File tool indicates that the tool was able to identify the file without reading the contents. To do so, it would probably have to rely on filenames. Tika seems to be faster, but such small differences are covered by the uncertainties in the system.

Md5 is not a characterisation tool. Rather, it is a checksumming tool. To checksum a file, the tool needs to read the entire file. For the system in question the actual checksum calculation in neglible, so Md5 gives a baseline for reading the entire archive.

As can be seen, Tika is the fastests of the tools, and Fido is the slowest. That the showdown was to be between Tika and Droid was expected. Python does not have a Just In Time compiler, and will not be able to compete with java for such long running processes. That Fido was even slower than Md5 came as a surprise, but again, Md5 is written in very optimised C, and Fido is still python.

February 17 2011

A new direction in file characterisation

blekinge 1

While thinking about the Dev8D challenge (which I cannot compete in 🙁 I got to thinking about the way we do file characterisation.

I am not old enough to know the history of this field, but it seems that the grand old tool is the file(8) tool from unix. When “file” was developed, all files should contain/contained a few magic bytes in the header, to help identification tools. We still see this pattern.

Pdf files start with %PDF-1.
Shell scripts start with #!/bin/sh
Xml files start with <?xml

So, for quick identification, this is sufficient. Combined with filename suffix, you can get a good idea about the kind of file your dealing with. But his design came from a time where binary files were the norm. This is no longer the case. Increasingly, we use xml files, and semi binary formats like pdf. I use xml files for configfiles for everything, and as data files for most things. Having my characteriser tell me that the file is xml is anti-informative. I am being given no information about what kind of file it is. It is comparable to being told that your data file is binary.

Alternatively, we use zip files. It is easy to identify a zip file. But these are, from memory the kind of files that will be identified as zip files

docx
zip
jar
war

Now, for characterisation purposes, we do not want just to be told that the file is a zip. We want to be told more.

If we move towards more advanced signatures, we can get more information, mainly because zip files have an uncompressed file list. More heavily compressed formats, or gzip/tar will prove a lot harder to characterise.

So, in this day and age, binary file signatures are not sufficient. Instead, we need to understand the serialization formats more. For that is what files are, serialization formats. The content of the file is serialized into the bytes of the file. For many advanced uses, there are multiple ways to serialize the very same file. But if we understand the serialization, we can read the file contents, and perform our characterisation on the contents.

To prove this concept, I wrote a little tool, currently called DocumentIdentifier. It will be released soonly, but really, it’s so simple. Given a file, it loads it as xml, if able. Then it outputs the namespace of the root element. It runs through the file, and outputs the namespaces used in the file.

So, working on a Mets xml file, I would get something like this

Root element namespace: "http://www.loc.gov/METS/"
Other namespaces used
"http://www.loc.gov/mix/"
"http://www.loc.gov/ndnp"
"http://www.loc.gov/standards/premis"
"http://www.loc.gov/mods/v3"
"http://www.w3.org/2001/XMLSchema-instance"
"http://www.w3.org/1999/xlink"
"http://www.w3.org/2000/09/xmldsig#"

So, where traditional tools would tell me the file is a xml file, I would now be informed that it was a Mets file, with content from the mix, ndnp, premis and mods schemas.

The next step for me will be, thanks to David Tarrant, to have it validate xml blobs, if there are from a namespace the tool recognize.

February 17 2011

Percipio; computer generated file signatures

blekinge 0

Percipio is a small tool I have developed. You can find the tool here https://github.com/blekinge/percipio

I will make a proper release soon, especially if anybody shows any interest. It has been heavily inspired by the now not-developed closed sourcec tool TrID http://mark0.net/soft-trid-e.html

File signatures have traditionally been created by hand. This comes from the traditional belief that humans are much better than computers in reading binary data. This belief is obviously wrong, or at least not complete. Whereas humans can understand binary data on a higher level, any simple matching task is much easier done by computers.

The primary task of Percipio is to generate file format recognizition signatures. Given a set of data files, Percipio will scan for header and footer bytes in common between the files. These common bytes are the signature of the file. The signature is written in an xml format, that attempts to be compatible with the one used by TRiD. I hope someone will write an xslt to transform these to Fido signatures, which should be very easy.

Percipio cannot presently generate regular expression signatures. So, if the same structure exist in all files, but at different offsets, Percipio will not find it. I am presently thinking about algorithms for matching identical blocks this way, but presently percipio does not have this capability.

Percipio also contain code to match files against signatures. Here again I use an Idea from TrID. Rather than going for a unique identification, I score the file against all the known signatures, and present a scoreboard. With computer generated signatures, there will be false positives, and I hope the scoreboard will provide a way for users to work with this.

The score is generated as (number of bytes matched – number of bytes not matched) * the number of files used to generate the signature

I multiply the score with the number of files used to generate the signature, as this is a an easy number that should somewhat correspond to the quality of the signature. A signature generated from many files will be less likely to have “local” artifacts, than one generated from few files. Of course, if the files are all related, this number will not work, but I do not know any other way to specify the quality of a signature in a computer generated way.

Tests have shown that as few as three distinct files are sufficient to generate signatures of a useful quality. If possible, get files created by different programs or computers, to prevent license and author identifiers embedded in the file headers to be identified as file signatures.

blekinge

About blekinge

Posts by :