NIST SP 800-168 日本語訳
英語タイトル : Approximate Matching: Definition and Terminology日本語タイトル : 近似マッチング：定義と用語
公開日 : 2014-07-02
原文URL : https://csrc.nist.gov/pubs/sp/800/168/final
翻訳編集 : 自動生成（有志による非公式の日本語訳）, 原文取得日 : 2026-09-30, 訳文 : 161 / 161 ブロック
[要約] SP 800-168 は、2つのデジタル成果物間の類似性を識別する近似マッチングについて、定義と用語を示す文書です。ユースケース、用語、基本要件、結果の信頼性を整理したうえで、バイト単位の近似マッチングアルゴリズムを試験する際の動機、試験データ、注目する性質を扱います。議論、研究、ツール開発、ツール調達を促進するための基盤で、対象読者は類似性を特定する技術を選定・構築・使用するセキュリティやフォレンジックの技術者です。
NIST Special Publication 800-168
NIST特別刊行物 800-168
Approximate Matching: Definition and Terminology
近似マッチング：定義と用語
Frank Breitinger Barbara Guttman Michael McCarrin Vassil Roussev Douglas White
Frank Breitinger、Barbara Guttman、Michael McCarrin、Vassil Roussev、Douglas White
http://dx.doi.org/10.6028/NIST.SP.800-168
http://dx.doi.org/10.6028/NIST.SP.800-168
［NIST のロゴ。公的な標章のため、この非公式サイトには掲載していません。原本 PDF を参照してください。］
NIST Special Publication 800-168
NIST特別刊行物 800-168
Approximate Matching: Definition and Terminology
近似マッチング：定義と用語
Frank Breitinger University of New Haven West Haven, CT
Frank Breitinger University of New Haven West Haven, CT
Douglas White Barbara Guttman
Douglas White Barbara Guttman
Software and Systems Division Information Technology Laboratory
ソフトウェア・システム部門 情報技術研究所
Michael McCarrin Naval Postgraduate School Monterey, CA
Michael McCarrin Naval Postgraduate School Monterey, CA
Vassil Roussev University of New Orleans New Orleans, LA
Vassil Roussev University of New Orleans New Orleans, LA
http://dx.doi.org/10.6028/NIST.SP.800-168
http://dx.doi.org/10.6028/NIST.SP.800-168
May 2014
2014年5月
U.S. Department of Commerce Penny Pritzker, Secretary
米国商務省 長官 Penny Pritzker
National Institute of Standards and Technology
国立標準技術研究所
Patrick D. Gallagher, Under Secretary of Commerce for Standards and Technology and Director
Patrick D. Gallagher、標準技術担当商務次官兼所長
Authority
法的根拠
This publication has been developed by National Institute of Standards and Technology (NIST) to further its statutory responsibilities under the Federal Information Security Management Act (FISMA), Public Law (P.L.) 107-347. NIST is responsible for developing information security standards and guidelines, including minimum requirements for Federal information systems, but such standards and guidelines shall not apply to national security systems without the express approval of appropriate Federal officials exercising policy authority over such systems. This guideline is consistent with the requirements of the Office of Management and Budget (OMB) Circular A-130, Section 8b(3), Securing Agency Information Systems, as analyzed in Circular A 130, Appendix IV: Analysis of Key Sections. Supplemental information is provided in Circular A-130, Appendix III, Security of Federal Automated Information Resources.
本刊行物は、連邦情報セキュリティマネジメント法（FISMA）、公法（P.L.）107-347に基づく法定責務を推進するために、国立標準技術研究所（NIST）が策定したものです。NISTは、連邦情報システムの最低要件を含む情報セキュリティ標準およびガイドラインを策定する責任を負います。ただし、これらの標準およびガイドラインは、国家安全保障システムに対する政策権限を行使する適切な連邦当局者の明示的な承認がない限り、国家安全保障システムには適用されません。本ガイドラインは、行政管理予算局（OMB）通達A-130第8b(3)節「政府機関情報システムの保護」の要件と整合しています。この要件は、通達A-130の付録IV「主要条項の分析」で分析されています。補足情報は、通達A-130の付録III「連邦自動化情報資源のセキュリティ」に記載されています。
Nothing in this publication should be taken to contradict the standards and guidelines made mandatory and binding on Federal agencies by the Secretary of Commerce under statutory authority. Nor should these guidelines be interpreted as altering or superseding the existing authorities of the Secretary of Commerce, Director of the OMB, or any other Federal official. This publication may be used by nongovernmental organizations on a voluntary basis and is not subject to copyright in the United States. Attribution would, however, be appreciated by NIST.
本刊行物のいかなる記述も、商務長官が法的権限に基づいて連邦機関に対して義務的かつ拘束力のあるものとした標準およびガイドラインに矛盾するものと解釈すべきではありません。また、本ガイドラインは、商務長官、OMB長官、その他の連邦当局者が有する既存の権限を変更する、またはそれに取って代わるものと解釈すべきではありません。本刊行物は、非政府組織が任意に使用でき、米国内では著作権の対象ではありません。ただし、出典を明記してもらえればNISTとしては幸いです。
National Institute of Standards and Technology Special Publication 800-168 Natl. Inst. Stand. Technol. Spec. Publ. 800-168, 21 pages (May 2014) http://dx.doi.org/10.6028/NIST.SP.800-168 CODEN: NSPUE2
国立標準技術研究所 特別刊行物 800-168 Natl. Inst. Stand. Technol. Spec. Publ. 800-168、全21ページ（2014年5月） http://dx.doi.org/10.6028/NIST.SP.800-168 CODEN: NSPUE2
Certain commercial entities, equipment, or materials may be identified in this document in order to describe an experimental procedure or concept adequately. Such identification is not intended to imply recommendation or endorsement by NIST, nor is it intended to imply that the entities, materials, or equipment are necessarily the best available for the purpose. There may be references in this publication to other publications currently under development by NIST in accordance with its assigned statutory responsibilities. The information in this publication, including concepts and methodologies, may be used by Federal agencies even before the completion of such companion publications. Thus, until each publication is completed, current requirements, guidelines, and procedures, where they exist, remain operative. For planning and transition purposes, Federal agencies may wish to closely follow the development of these new publications by NIST. Organizations are encouraged to review all draft publications during public comment periods and provide feedback to NIST. All NIST Computer Security Division publications, other than the ones noted above, are available at http://csrc.nist.gov/publications.
本文書では、実験手順や概念を適切に説明するために、特定の商業的な事業体、機器、または材料を挙げる場合があります。このように挙げることは、NISTによる推奨または支持を意味するものではなく、それらの事業体、材料、または機器がその目的に対して必ずしも入手可能な最良のものであることを意味するものでもありません。本刊行物には、NISTが付与された法定責務に従って現在策定中の他の刊行物への言及が含まれる場合があります。本刊行物に記載された情報（概念および方法論を含む）は、そのような関連刊行物が完成する前であっても、連邦機関が利用してもよいです。したがって、各刊行物が完成するまでは、現行の要件、ガイドライン、および手順が存在する場合、それらが引き続き有効です。計画策定および移行のために、連邦機関は、NISTによるこれらの新しい刊行物の策定状況を注視するとよいです。組織には、パブリックコメント期間中にすべての草案刊行物をレビューし、NISTにフィードバックを提供することを推奨します。上記のものを除き、NISTコンピュータセキュリティ部門のすべての刊行物は http://csrc.nist.gov/publications で入手できます。
Comments on this publication may be submitted to: National Institute of Standards and Technology Attn: Software and Systems, Information Technology Laboratory 100 Bureau Drive (Mail Stop 8970) Gaithersburg, MD 20899-8970 Email: barbara.guttman@nist.gov
本刊行物に関する意見の送付先： National Institute of Standards and Technology 宛先：Software and Systems, Information Technology Laboratory 100 Bureau Drive (Mail Stop 8970), Gaithersburg, MD 20899-8970 Email: barbara.guttman@nist.gov
Reports on Computer Systems Technology
コンピュータシステム技術に関する報告書
The Information Technology Laboratory (ITL) at the National Institute of Standards and Technology (NIST) promotes the U.S. economy and public welfare by providing technical leadership for the Nation’s measurement and standards infrastructure. ITL develops tests, test methods, reference data, proof of concept implementations, and technical analyses to advance the development and productive use of information technology. ITL’s responsibilities include the development of management, administrative, technical, and physical standards and guidelines for the cost-effective security and privacy of other than national security-related information in Federal information systems. The Special Publication 800-series reports on ITL’s research, guidelines, and outreach efforts in information system security, and its collaborative activities with industry, government, and academic organizations.
国立標準技術研究所（NIST）の情報技術研究所（ITL）は、米国の計測および標準の基盤に対して技術的リーダーシップを提供することにより、米国の経済と公共の福祉を促進しています。ITLは、情報技術の発展と生産的な利用を推進するために、試験、試験方法、参照データ、概念実証の実装、および技術分析を開発しています。ITLの責務には、連邦情報システムにおける国家安全保障関連以外の情報の、費用対効果の高いセキュリティおよびプライバシーのための、管理面、事務面、技術面、および物理面の標準およびガイドラインの策定が含まれます。特別刊行物800シリーズは、情報システムセキュリティにおけるITLの研究、ガイドライン、および普及活動、ならびに産業界、政府機関、および学術機関との協働活動について報告するものです。
Abstract
概要
This document provides a definition of and terminology for approximate matching. Approximate matching is a promising technology designed to identify similarities between two digital artifacts. It is used to find objects that resemble each other or to find objects that are contained in another object. This can be very useful for filtering data for security monitoring, digital forensics, or other applications. The purpose of this document is to provide a definition and terminology to describe approximate matching in order to promote discussion, research, tool development and tool acquisition.
本文書は、近似マッチングの定義と用語を示します。近似マッチングは、2つのデジタル成果物間の類似性を識別するために設計された有望な技術です。これは、互いに似ているオブジェクトを見つけるため、または別のオブジェクトに含まれているオブジェクトを見つけるために用いられます。これは、セキュリティ監視、デジタルフォレンジック、またはその他の用途のためにデータをフィルタリングするうえで非常に有用となり得ます。本文書の目的は、議論、研究、ツール開発、およびツール調達を促進するために、近似マッチングを記述するための定義と用語を示すことです。
Keywords
キーワード
approximate matching; bytewise matching; syntactic matching; semantic matching; fuzzy hashing
近似マッチング、バイト単位マッチング、構文マッチング、意味マッチング、ファジーハッシュ
Acknowledgements
謝辞
This document is based on the work of the NIST Approximate Matching Working Group, which consists of Frank Breitinger, John Delaroderie, Simson Garfinkel, Barbara Guttman, John Kelsey, Jesse Kornblum, Mary Laamanen, Michael McCarrin, Vassil Roussev, Clay Shields, John Tebbutt, Douglas White, and Joel Young.
本文書は、NIST近似マッチング作業部会の作業に基づいています。同作業部会は、Frank Breitinger、John Delaroderie、Simson Garfinkel、Barbara Guttman、John Kelsey、Jesse Kornblum、Mary Laamanen、Michael McCarrin、Vassil Roussev、Clay Shields、John Tebbutt、Douglas White、およびJoel Youngで構成されます。
Table of Contents
目次
TABLE OF CONTENTS
目次
序論
1.1 Purpose and Scope
1.1 目的と適用範囲
Approximate matching is a promising technology designed to identify similarities between two digital artifacts. It is used to find objects that resemble each other or to find objects that are contained in another object. This can be very useful for filtering data for security monitoring, digital forensics, or other applications. The purpose of this document is to provide a definition and terminology to describe approximate matching in order to promote discussion, research, tool development and tool acquisition. Approximate matching has the potential to provide valuable filtering in a world inundated with information, but the technique is not widely used. The goal of the document is to provide infrastructure to support advances in approximate matching and its use in forensics and security.
近似マッチングは、2つのデジタル成果物間の類似性を特定するために設計された有望な技術です。互いに似たオブジェクトや、別のオブジェクトに含まれるオブジェクトを見つけるために使われます。これは、セキュリティ監視、デジタル・フォレンジック、その他の用途でデータを絞り込むうえで非常に有用となり得ます。本書の目的は、議論、研究、ツール開発およびツール調達を促進するために、近似マッチングを記述するための定義と用語を提供することです。情報があふれる世界において、近似マッチングは価値ある絞り込み手段を提供する可能性を持ちますが、この技術は広くは使われていません。本書の目標は、近似マッチングの進歩と、フォレンジックおよびセキュリティにおけるその利用を支える基盤を提供することです。
1.2 Audience
1.2 対象読者
The intended audience of this document is security digital forensics programmers and other technical professionals with a need to determine, build, or use technology to identify similarity.
本書の対象読者は、類似性を特定する技術を選定、構築、または使用する必要がある、セキュリティおよびデジタル・フォレンジックのプログラマー、ならびにその他の技術専門家です。
2. 定義と用語
Approximate matching is a generic term describing any technique designed to identify similarities between two digital artifacts. In this context, an artifact (or an object) is defined as an arbitrary byte sequence, such as a file, which has some meaningful interpretation.
近似マッチングとは、2つのデジタル成果物間の類似性を特定するために設計されたあらゆる手法を指す一般用語です。この文脈で成果物（またはオブジェクト）とは、ファイルのように、何らかの意味のある解釈が可能な任意のバイト列と定義されます。
Different approximate matching methods may operate at different levels of abstraction. At the lowest level, generic techniques may detect the presence of common byte sequences (substrings) without any attempt to interpret the artifacts. At higher levels, approximate matching can incorporate more abstract analysis. In general lower level methods are expected to be faster and more generic in their applicability, whereas higher level methods are typically more targeted and require more processing.
近似マッチングの手法は、手法によって異なる抽象度で動作することがあります。最も低いレベルでは、汎用的な手法が、成果物を解釈しようとすることなく、共通のバイト列（部分文字列）の存在を検出することがあります。より高いレベルでは、近似マッチングに、より抽象的な分析を取り入れることができます。一般に、低レベルの手法はより高速で適用範囲もより汎用的であると期待され、一方、高レベルの手法は通常、より対象を絞ったものであり、より多くの処理を必要とします。
One common approach in security and forensic analysis is to find identical objects using cryptographic hashing. Approximate matching can be viewed as a generalization of that idea in that, instead of providing a yes/no {0, 1} answer to a comparison, it provides a range of outcomes, [0, 1], with the result interpreted as a measure of similarity.
セキュリティ分析やフォレンジック分析では、暗号学的ハッシュを使って同一のオブジェクトを見つける方法が一般的です。近似マッチングはこの考え方を一般化したものとみなせます。比較結果を yes/no の {0, 1} で示す代わりに、[0, 1] の範囲で示し、その値を類似性の尺度として解釈します。
2.1 Use cases
2.1 ユースケース
Broadly, there are two types of similarity queries that are of interest – resemblance and containment [1]. In the case of resemblance, we compare two similarly sized objects and interpret the result as a measure of the commonality between them; for example, two successive versions of a piece of code are likely to resemble each other substantially. When the compared objects differ in size significantly, such as a file and a whole-disk image, the test for commonality is interpreted as a containment query because it addresses the question of whether the large object contains the smaller one.
大別すると、関心の対象となる類似性クエリには、類似（resemblance）と包含（containment）の2種類があります[1]。類似クエリでは、サイズがほぼ同じ2つのオブジェクトを比較し、共通性の尺度として結果を解釈します。たとえば、あるコードの連続する2つのバージョンは、互いによく似ていると考えられます。ファイルとディスク全体のイメージのように、比較するオブジェクトのサイズが大きく異なる場合、共通性の検査は包含クエリとして解釈されます。これは、大きなオブジェクトに小さなオブジェクトが含まれているかを問うものです。
An approximate matching algorithm should address at least one of the following problems (divided according to whether the query type is (R)esemblance or (C)ontainment) [2, 3]: Object similarity detection (R): identify related artifacts, e.g., different versions of a document. Cross correlation (R): identify artifacts that share a common object, e.g., a Microsoft Word document and a PDF document containing the same image, or other embedded object. Embedded object detection (C): identify a given object inside an artifact, e.g., an image within a compound document or an executable inside a memory capture. Fragment detection (C): identify the presence of traces/fragments of a known artifact, e.g., identify the presence of a file in a network stream based on individual packets. In most analytical scenarios, approximate matching is used to filter data in, or out, based on a known reference set. In security monitoring applications, approximate matching could potentially be used to blacklist known bad artifacts, and (by extension) anything closely resembling them. However, approximate matching is not nearly as useful when it comes to whitelisting artifacts as malicious content can often be quite similar to benign content; e.g., a backdoored ssh server would approximately match regular one.
近似マッチングアルゴリズムは、次の問題（クエリの種類が類似（R）か包含（C）かによって分類している）のうち少なくとも1つに対応すべきです[2, 3]。オブジェクト類似性の検出（R）：文書の異なるバージョンなど、関連する成果物を特定します。相互相関（R）：共通のオブジェクトを共有する成果物を特定します。たとえば、同じ画像またはその他の埋め込みオブジェクトを含むMicrosoft Word文書とPDF文書。埋め込みオブジェクトの検出（C）：複合文書内の画像やメモリキャプチャ内の実行可能ファイルなど、成果物の内部にある所与のオブジェクトを特定します。断片の検出（C）：既知の成果物の痕跡または断片の存在を特定します。たとえば、個々のパケットに基づいてネットワークストリーム内のファイルの存在を特定します。ほとんどの分析シナリオでは、近似マッチングは、既知の参照セットに基づいてデータを選び入れる、または除外するフィルタリングに使われます。セキュリティ監視の用途では、近似マッチングを使って、既知の悪意ある成果物、および（その延長として）それによく似たあらゆるものをブラックリストに登録できる可能性があります。しかし、悪意あるコンテンツは無害なコンテンツとかなり似ていることが多いため、成果物のホワイトリスト化に関しては、近似マッチングはそれほど有用ではありません。たとえば、バックドアを仕込まれたsshサーバーは、通常のsshサーバーと近似マッチするでしょう。
2.2 Terminology
2.2 用語
Although the common language definition of ‘similarity’ is sufficient to give an intuitive sense of the term, the multitude of ways in which two artifacts can be said to be similar poses a challenge when attempting to describe the purpose and behavior of approximate matching algorithms. For example, two strings ‘ababa’ and ‘cdcdc’ might be considered similar in that they both have five characters ranging over two alternating values, or they might be treated as dissimilar because they have no common characters. To resolve this ambiguity, approximate matching algorithms define similarity in terms of features that represent characteristics of the artifacts pertinent to the algorithm’s method of comparison.
「類似性」という語の一般的な意味は直感的な理解には十分ですが、2つの成果物がどのような点で似ていると言えるかは多岐にわたるため、近似マッチングアルゴリズムの目的や動作を説明する際に課題となります。たとえば、文字列「ababa」と「cdcdc」は、どちらも2種類の値が交互に現れる5文字の列である点で似ているとも、共通の文字がない点で似ていないとも考えられます。この曖昧さを解消するため、近似マッチングアルゴリズムは、比較方法に関係する成果物の特性を表す特徴に基づいて類似性を定義します。
Features. The basic elements through which artifacts are compared. Comparison of two features always yields a binary {0, 1} outcome indicating a match or non-match; because features are defined as the most basic comparison unit that the algorithm considers, partial matches are not permitted. Generally, a feature can be any value derived from an artifact. Each approximate matching algorithm must define the structure of its features and the method by which they are derived. For example, an algorithm might define a feature as a (byte, offset) pair produced by reading the value of a byte and storing it along with the offset at which it was read. Feature set. The set of all features associated with a single artifact is its feature set. Each algorithm must include a criteria by which candidate features are selected for inclusion in this set. For example, an algorithm might select all the (byte, offset) pairs produced by reading every 16th byte in the artifact. Similarity. The similarity of two artifacts, as measured by a particular approximate matching algorithm, is defined as an increasing monotonic function of the number of matching features contained in their respective feature sets.
特徴（Features）。成果物を比較するための基本要素。2つの特徴を比較すると、常に、一致または不一致を示す二値の結果 {0, 1} が得られます。特徴はアルゴリズムが考慮する最も基本的な比較単位として定義されるため、部分一致は認められません。一般に、特徴は成果物から導出される任意の値であり得ます。各近似マッチングアルゴリズムは、特徴の構造とその導出方法を定義しなければなりません。たとえば、バイトの値を読み取り、その値を読み取った位置のオフセットとともに保存することで得られる（バイト、オフセット）の組を、特徴として定義するアルゴリズムが考えられます。特徴集合（Feature set）。1つの成果物に関連付けられたすべての特徴の集合が、その成果物の特徴集合です。各アルゴリズムは、この集合に含める候補特徴を選ぶ基準を含まなければなりません。たとえば、成果物の16バイトごとに1バイトを読み取って得られるすべての（バイト、オフセット）の組を選ぶアルゴリズムが考えられます。類似性（Similarity）。特定の近似マッチングアルゴリズムで測定した2つの成果物の類似性は、それぞれの特徴集合に含まれる一致特徴の数の単調増加関数として定義されます。
Based on the level of abstraction of the similarity analysis performed, approximate matching methods can be placed in one of three main categories [4]:
類似性分析の抽象度に基づき、近似マッチング手法は主に次の3種類に分類できます[4]。
Bytewise matching relies only on the sequences of bytes that make up a digital object, without reference to any structures within the data stream, or to any meaning the byte stream may have when appropriately interpreted. Such methods have the widest applicability as they can be applied to any piece of data; however, they also carry the implicit assumption that artifacts that humans perceive as similar have similar byte-level encodings. This assumption is not universally valid. Analyst expertise is necessary to evaluate the significance of a byte-level match. Syntactic matching uses internal structures present in digital objects. For ex ample, the structure of a TCP network packet is defined by an international standard and matching tools can make use of this structure during network packet analysis to match the source, destination or content of the packet. Syntax-sensitive similarity measurements are specific to a particular class of objects that share an encoding but require no interpretation of the content to produce meaningful results. Semantic matching uses contextual attributes of the digital object to interpret the artifact in a manner that more closely corresponds with human perceptual categories. For example, perceptual hashes allow the matching of visually similar images and are unconcerned with the low-level details of how the images are persistently stored. Semantic methods tend to provide the most specific results but also tend to be the most computationally expensive ones.
バイト単位のマッチングは、デジタルオブジェクトを構成するバイト列だけに依拠し、データストリーム内部のいかなる構造も、適切に解釈した場合にバイトストリームが持ち得るいかなる意味も参照しません。この種の手法はあらゆるデータに適用できるため、適用範囲が最も広範です。ただし、人間が似ていると認識する成果物はバイトレベルの符号化も似ている、という暗黙の前提も伴います。この前提は常に成り立つわけではありません。バイトレベルの一致の重要性を評価するには、分析者の専門知識が必要です。構文マッチングは、デジタルオブジェクトに存在する内部構造を利用します。たとえば、TCPネットワークパケットの構造は国際規格で定義されており、マッチングツールは、ネットワークパケット分析の際にこの構造を利用して、パケットの送信元、宛先、または内容を照合できます。構文に依存する類似性測定は、符号化を共有する特定の種類のオブジェクトに固有のものですが、有意な結果を出すために内容の解釈を必要としません。意味マッチングは、デジタルオブジェクトの文脈的属性を使い、人間の知覚上の分類により近い形で成果物を解釈します。たとえば、知覚ハッシュは視覚的に似た画像の照合を可能にし、画像が永続的にどのように保存されているかという低レベルの詳細には関知しません。意味的手法は最も特定性の高い結果を出す傾向がありますが、計算コストも最も高くなる傾向があります。
In current literature, researchers use a number of terms to refer to various approximate matching methods: fuzzy hashing and similarity hashing denote bytewise approximate matching; perceptual hashing and robust hashing denote semantic approximate matching. There is no widely-used pre-existing terminology for syntactic approximate matching as it is mostly viewed as pre-processing (to separate the features) before hashing, or applying a bytewise approximate matching algorithms. For example, network flows are usually reconstructed before any processing is done on them.
現在の文献では、研究者はさまざまな近似マッチング手法を表すために複数の用語を使っています。ファジーハッシュおよび類似性ハッシュはバイト単位の近似マッチングを指し、知覚ハッシュおよびロバストハッシュは意味的な近似マッチングを指します。構文的な近似マッチングについては、広く使われている既存の用語がありません。これは、ハッシュ処理またはバイト単位の近似マッチングの前に特徴を分離する前処理とみなされることが多いためです。たとえば、ネットワークフローは通常、処理を始める前に再構成されます。
Bytewise approximate matching algorithms work in two phases. In the first, a similarity digest representation (also referred to as a signature or fingerprint) is generated from the original data. In the second phase, digests are compared to produce a similarity score. More precisely:
バイト単位の近似マッチングアルゴリズムは2段階で動作します。第1段階では、元データから類似性ダイジェスト表現（シグネチャまたはフィンガープリントとも呼ばれる）を生成します。第2段階では、ダイジェストを比較して類似性スコアを算出します。より正確には、次のとおりです。
Similarity digest. A similarity digest is a (compressed) representation of the original data object’s feature set that is suitable for comparison with other similarity digests created by the same algorithm. In most cases, the digest is much smaller than the original artifact and the original object is not recoverable from the digest.
類似性ダイジェスト（Similarity digest）。類似性ダイジェストとは、同じアルゴリズムで作成された他の類似性ダイジェストと比較できるようにした、元のデータオブジェクトの特徴集合の（圧縮された）表現です。ほとんどの場合、ダイジェストは元の成果物より大幅に小さく、ダイジェストから元のオブジェクトを復元することはできません。
Every bytewise approximate matching technique requires at least two core functions:
バイト単位の近似マッチング手法には、少なくとも次の2つの中核機能が必要です。
Feature extraction function: identifies and extracts features/attributes from each digital artifact. The mechanism by which features are picked and interpreted depends on the approximate matching algorithm. The representation of this collection is the similarity digest of the object. Similarity function: compares two similarity digests and outputs a score. The recommended approach is to assign a score \(s\) in the \(0 \le s \le 1\) range, where 0 indicates no similarity and 1 indicates high similarity. This score represents a normalized estimate of the number of matching features in the feature sets corresponding to the artifacts from which the similarity digests were created. Normalization strategy: The similarity function can follow one of two normalization strategies, depending on whether the algorithm describes resemblance or containment. For resemblance queries, the number of matching features will be weighed against the total number of features in both objects. In the case of containment queries, the algorithm may disregard unmatched features in the larger of the objects’ two-feature sets.
特徴抽出関数：各デジタル成果物から特徴または属性を特定して抽出します。特徴の選択・解釈方法は近似マッチングアルゴリズムによって異なります。この特徴群の表現が、オブジェクトの類似性ダイジェストとなります。類似性関数：2つの類似性ダイジェストを比較し、スコアを出力します。推奨される方法は、スコア \(s\) を \(0 \le s \le 1\) の範囲で割り当てることであり、0は類似性なし、1は高い類似性を示します。このスコアは、類似性ダイジェストの生成元である成果物に対応する特徴集合のうち、一致する特徴数の正規化推定値です。正規化方法：類似性関数は、アルゴリズムが類似クエリと包含クエリのどちらを扱うかに応じて、次の2つの正規化方法のいずれかを使います。類似クエリでは、一致する特徴数を両方のオブジェクトの特徴総数と比較します。包含クエリでは、2つの特徴集合のうち大きい方に含まれる不一致特徴を無視してもよいです。
Because features and feature sets can be arbitrarily complex and, furthermore, deal with byte-level structures to which meaning is not clearly assigned, the interpretation of the similarity score can prove challenging. To address this problem, some approximate matching algorithms make use of an empirically determined threshold value to attempt to correlate bytewise similarity scores with higher-level properties of interest. In such cases, the similarity score can be treated as a confidence score, where results above the threshold value are considered likely to exhibit common human-recognizable traits.
特徴や特徴集合は任意に複雑になり得るうえ、意味が明確に割り当てられていないバイトレベルの構造を扱うこともあるため、類似性スコアの解釈は難しい場合があります。この問題に対処するため、経験的に決定したしきい値を使い、バイト単位の類似性スコアを、より高レベルの関心対象の特性と対応付けようとする近似マッチングアルゴリズムもあります。この場合、類似性スコアを信頼度スコアとして扱い、しきい値を上回る結果は、人が認識できる共通の特徴を示す可能性が高いとみなせます。
2.3 Essential requirements
2.3 必須要件
Like traditional hash functions, there are several defining characteristics that approximate matching functions should exhibit. Each algorithm should define how it incorporates each of these properties and how it satisfies the reporting requirements for those properties, where appropriate.
従来のハッシュ関数と同様に、近似マッチング関数が示すべき、いくつかの定義上の特性があります。各アルゴリズムは、これらの特性のそれぞれをどのように取り入れるか、また該当する場合はそれらの特性に関する報告要件をどのように満たすかを定めるべきです。
Similarity preservation: Similarity digests must be constructed such that the outcome of a comparison between any two digests is uniquely determined by the similarity of the artifacts from which they were produced. That is, if \(A'\) is a similarity digest created from artifact \(A\) and \(B'\) is a similarity digest created from artifact \(B\), the results of comparing \(A'\) and \(B'\) should be uniquely determined by the similarity of \(A\) and \(\mathrm{B}\). Self-evaluation: The similarity measure should be accompanied by a measure of the accuracy of the matching technique under the circumstances in which it is used, e.g., a margin of error or confidence level. The description of the output score should also state whether a score of 1 indicates an exact match. Compression: A compact similarity digest is desired as it normally allows a faster comparison and requires less storage space. In the best case, it will have a fixed length like the output of traditional hash functions. If the efficiency and reliability of the results remains unchanged, then a shorter similarity digest is preferable. Ease of computation: First, the algorithm description should include the results of testing the runtime efficiency of the feature extraction function and of the similarity function. The former might be expressed relative to a standard hashing algorithm, such as SHA-1. Second, the algorithm description should state the theoretical complexity for a similarity digest comparison in big O notation. For instance, common lookup complexities for comparing a single digest against a database with \(n\) entries, are: \(O(1)\) for fixed-length digests stored in hash tables (e.g. dictionaries) \(O(\log_2 n)\) for fixed-length digests stored in binary trees or a sorted list
類似性の保持：類似性ダイジェストは、任意の2つのダイジェストを比較した結果が、それらの生成元である成果物の類似性によって一意に決まるように構成しなければなりません。つまり、\(A'\) が成果物 \(A\) から作成した類似性ダイジェストであり、\(B'\) が成果物 \(B\) から作成した類似性ダイジェストである場合、\(A'\) と \(B'\) の比較結果は、\(A\) と \(\mathrm{B}\) の類似性によって一意に決まるべきです。自己評価：類似性尺度には、それが使用される状況における照合手法の精度を示す尺度（誤差範囲や信頼水準など）を併記すべきです。出力スコアの説明では、スコア1が完全一致を表すかどうかも明記すべきです。圧縮：コンパクトな類似性ダイジェストが望ましい。通常、比較を高速化でき、必要な記憶領域も少なくて済むためです。最良の場合、従来のハッシュ関数の出力のように固定長となります。結果の効率性と信頼性が変わらないなら、類似性ダイジェストは短い方が望ましい。計算の容易さ：第一に、アルゴリズムの説明には、特徴抽出関数および類似性関数の実行時効率を試験した結果を含めるべきです。前者は、SHA-1などの標準的なハッシュアルゴリズムとの相対値で表してもよいです。第二に、アルゴリズムの説明では、類似性ダイジェストの比較に関する理論計算量をビッグO記法で示すべきです。たとえば、\(n\) 件のエントリを持つデータベースに対して単一のダイジェストを比較する場合の一般的な検索計算量は、次のとおりです。\(O(1)\)：ハッシュテーブル（辞書など）に格納した固定長ダイジェスト。\(O(\log_2 n)\)：二分木またはソート済みリストに格納した固定長ダイジェスト。
\(O(n)\) for fixed-length digests stored in an unsorted list, or other scenarios in which no indexing or sorting is possible
\(O(n)\)：ソートされていないリストに格納した固定長ダイジェスト、またはインデックスやソートを利用できないその他の場合。
2.4 Reliability of results
2.4 結果の信頼性
The reliability of the results for a given approximate matching technique depends on three factors. Each algorithm should define how it incorporates these factors and how it satisfies their reporting requirements.
特定の近似マッチング手法による結果の信頼性は、3つの要因に左右されます。各アルゴリズムは、これらの要因をどのように取り入れるか、また各要因に関する報告要件をどのように満たすかを定めるべきです。
Sensitivity & robustness: The algorithm should provide some measure of its robustness. A technique’s robustness will define the operating conditions in which it can function effectively, also called its performance envelope. For example, robustness addresses the minimum and maximum sizes of objects that an algorithm can reliably distinguish between. Precision & recall: The algorithm should include a description of the methods used to determine its reliability and to select the test data. Specifically, it should indicate whether test data is culled from existing collections or developed solely to support testing. Test results may include precision, recall, F-score, and other relevant measures of effectiveness.
感度&堅牢性：アルゴリズムは、その堅牢性について何らかの尺度を示すべきです。手法の堅牢性は、その手法が効果的に機能できる動作条件を定めます。この動作条件は性能範囲とも呼ばれます。たとえば、堅牢性は、アルゴリズムが確実に区別できるオブジェクトの最小サイズと最大サイズに関係します。適合率&再現率：アルゴリズムには、その信頼性を判定するために用いた方法とテストデータを選択するために用いた方法の説明を含めるべきです。具体的には、テストデータを既存のコレクションから選別したのか、テストを支援する目的のみで作成したのかを示すべきです。テスト結果には、適合率、再現率、Fスコア、およびその他の関連する有効性指標を含めてもよいです。
Security of results: The algorithm should indicate whether it includes security properties designed to prevent attacks. Such attacks include manipulation of the matching technique or input data such that a data object appears dissimilar to another object to which it is similar or similar to another object with which it has little in common.
結果のセキュリティ：アルゴリズムは、攻撃を防ぐためのセキュリティ特性を備えているかどうかを示すべきです。攻撃には、照合手法または入力データを操作して、データオブジェクトが、本来は似ている別のオブジェクトと似ていないように見せることや、ほとんど共通点のない別のオブジェクトと似ているように見せることが含まれます。
3. バイト単位の近似マッチングアルゴリズムのテスト
The section gives a general overview of the motives and methods behind testing approximate matching algorithms. Defining a universal testing criteria is difficult; the effectiveness of a given approximate matching algorithm depends largely on the particular task against which it is evaluated. As such, rather than attempt to enumerate a comprehensive evaluation strategy, we focus on key considerations that arise during test design and evaluation. We also describe several properties of approximate matching algorithms that may be useful for characterizing their behavior.
この節では、近似マッチングアルゴリズムのテストを行う動機と方法を概説します。普遍的なテスト基準を定めるのは困難です。近似マッチングアルゴリズムの有効性は、評価対象となる個別のタスクに大きく依存するためです。そのため、網羅的な評価戦略を列挙しようとするのではなく、テストの設計と評価の際に生じる主要な考慮事項に焦点を当てます。また、近似マッチングアルゴリズムの動作を特徴付けるのに役立ち得る、近似マッチングアルゴリズムのいくつかの性質についても説明します。
3.1 Motivation
3.1 動機
There are at least three major motivations for testing bytewise approximate matching algorithms. The first and most basic is to understand the classes of objects that the algorithm identifies as similar. For example, an algorithm may define its feature set such that it measures similarity as a function of the number of certain common byte sequences shared between two digital artifacts. Because this comparison occurs at a very low level, its semantic interpretation is not obvious. Testing across various tasks and types of data is necessary to determine whether such an algorithm is useful for identifying, say, html documents that contain similar content, or pdfs with the same embedded font.
バイト単位の近似マッチングアルゴリズムをテストする主な動機は、少なくとも3つあります。第一の、最も基本的な動機は、アルゴリズムがどの種類のオブジェクトを似ていると判定するかを理解することです。たとえば、2つのデジタル成果物の間で共有される特定の共通バイト列の数の関数として類似性を測定するよう、特徴集合を定義するアルゴリズムがあり得ます。この比較は非常に低いレベルで行われるため、その意味的な解釈は明らかでありません。そのようなアルゴリズムが、たとえば、内容の似たHTML文書や、同じ埋め込みフォントを持つPDFを特定するのに有用かどうかを判断するには、さまざまなタスクやデータ種別にわたるテストが必要です。
Second, as an algorithm is developed, a standard suite of tests, such as those proposed by Breitinger, Stivaktakis, and Baier [3], allows new versions to be compared against previous versions. Testing against a fixed set of tasks helps to highlight any changes in the algorithm’s similarity score as a function of its input. Improvements in speed or space efficiency can also be measured.
第二に、アルゴリズムの開発中、Breitinger、Stivaktakis、Baierが提案したもの[3]などの標準テスト一式を用いれば、新しいバージョンを以前のバージョンと比較できます。固定された一連のタスクでテストすると、入力に応じたアルゴリズムの類似性スコアの変化を明らかにできます。速度や記憶領域の効率向上も測定できます。
Finally, testing allows approximate matching algorithms to be compared to each other. The use of a standard suite of tasks can be beneficial in this testing scenario also. Additional measures must be taken, however, to ensure that tests produce comparable results. Because the algorithms define their similarity score independently, direct comparison of scores is rarely meaningful. One solution for this problem is to use a threshold or some other criteria to translate scores from their [0,1] range back to a binary {0,1} output which can be evaluated against known ground truth to produce confusion matrices (Roussev’s comparison of sdhash and ssdeep offers an example of this approach [2]). Alternately, the tester might define other high-level criteria for the expected behavior of an algorithm in a specific use case of interest, and evaluate the algorithms against this expectation.
最後に、テストによって近似マッチングアルゴリズム同士を比較できます。このテストシナリオでも、標準的なタスク一式の使用が有益となり得ます。ただし、テストが比較可能な結果を生むようにするには、追加の対策を講じなければなりません。各アルゴリズムは類似性スコアを独自に定義しているため、スコアを直接比較しても意味をなすことはほとんどありません。この問題の解決策の一つは、しきい値またはその他の基準を使って、[0,1] の範囲のスコアを二値の {0,1} の出力に変換し直すことです。この出力は、既知の正解データと照らして評価し、混同行列を作成できます（Roussevによるsdhashとssdeepの比較は、この方法の例です[2]）。別の方法として、テスト実施者が、関心のある特定のユースケースにおいてアルゴリズムに期待される動作について別の高レベルの基準を定め、その期待に照らして各アルゴリズムを評価してもよいです。
3.2 Test Data
3.2 テストデータ
Approximate matching algorithms can be tested against either controlled (synthetic) data [7] or real data (i.e., data originally created for purposes other than testing). The former typically consists of randomly generated blocks or files; its main advantage is that ground truth is constructed and, therefore, precisely known. This allows tests to be run automatically and the results to be interpreted with standard statistical measures.
近似マッチングアルゴリズムは、制御された（合成）データ[7]または実データ（つまり、もともとテスト以外の目的で作成されたデータ）のいずれかを使ってテストできます。前者は通常、ランダムに生成したブロックまたはファイルで構成されます。その主な利点は、正解データが構築されたものであり、したがって正確に分かっていることです。このため、テストを自動実行し、標準的な統計指標を使って結果を解釈できます。
The drawback to using randomly generated data is that it is not necessarily representative. For example, random data tends to be unique, high-entropy and internally varied. These properties may be appropriate for use cases involving compressed or encrypted data, but could prove misleading for other file types (such as text documents). A potential workaround is to develop more sophisticated randomization that preserves the characteristic properties of the target file type.
ランダム生成データを使う欠点は、必ずしも代表性がないことです。たとえば、ランダムデータは一意性が高く、エントロピーが高く、内部の変化に富む傾向があります。これらの特性は、圧縮データや暗号化データを扱うユースケースには適している可能性がありますが、テキスト文書など、他の種類のファイルでは誤解を招くおそれがあります。対象ファイル形式の特徴的な性質を保つ、より洗練されたランダム化を開発することが解決策となり得ます。
The obvious advantage of using real data is that the results can be directly be related to practical applications. However, the challenges of defining a representative sample, establishing the ground truth, and running experiments at scale (without a human in the loop) are non-trivial. See Appendix A1 Example test methodologies for both controlled and real data.
実データを使用する明らかな利点は、結果を実際の応用に直接関連付けられることです。ただし、代表的なサンプルの定義、グラウンドトゥルースの確立、人を介さずに大規模な実験を実行することには、容易には解決できない課題があります。管理されたデータと実データの両方に関するテスト方法の例は、付録A1を参照されました。
3.3 Properties of Special Interest
3.3 特に注目する性質
The following properties may be especially useful for testing and comparing approximate matching algorithms. This list is not meant to be exhaustive. Note that the properties enumerated here are adapted from those proposed by Breitinger, Stivaktakis, and Baier [3]. See their work on the FRASH testing framework for an example of a complete description (including full implementation details and suggested test values) of a testing framework that incorporates these properties.
次の性質は、近似照合アルゴリズムのテストと比較に特に有用な場合があります。この一覧は網羅的なものではありません。ここに挙げる性質は、Breitinger、Stivaktakis、Baierが提案したもの[3]をもとにしています。これらの性質を取り入れたテストフレームワークの完全な記述の例として、FRASHテストフレームワークに関する同著者らの研究を参照されました。そこには、実装の詳細と推奨テスト値も含まれます。
3.3.1 Efficiency
3.3.1 効率
The efficiency of an algorithm is measured in terms of the space and time it requires; the latter property is further subdivided according to time needed for generating similarity digests and time need for comparing them.
アルゴリズムの効率は、必要とする空間と時間によって測定します。後者はさらに、類似性ダイジェストの生成に必要な時間と、その比較に必要な時間に分けられます。
Space efficiency.
空間効率。
Traditional hash functions return a fixed length fingerprint; in contrast, the length of similarity digests is sometimes variable and proportional to the input length. If the digest is of variable length, space efficiency measures the ratio between input and the digest and returns a percentage value. That is,
従来のハッシュ関数は固定長のフィンガープリントを返します。一方、類似性ダイジェストの長さは可変で、入力長に比例する場合があります。ダイジェストが可変長の場合、空間効率では両者の長さの比を測定し、百分率の値を返します。すなわち、次のとおりです。
Generation efficiency.
生成効率。
Generation efficiency measures the throughput of an algorithm when producing a similarity digest from raw input. To enable useful comparisons across different architectures, it is recommended that the throughput of a standard algorithm implementation, such as SHA-1 in openssh, be included as a reference point.
生成効率は、生の入力から類似性ダイジェストを生成する際のアルゴリズムのスループットを測定します。異なるアーキテクチャ間で有用な比較ができるよう、opensshにおけるSHA-1など、標準的なアルゴリズム実装のスループットを基準点として含めることが推奨されます。
Comparison efficiency.
比較効率。
The comparison efficiency measures the rate at which similarity digests can be compared. It is useful to have both a formal analysis, which provides the theoretical complexity of the comparison (in O- notation) and an empirical evaluation based on a reference data set.
比較効率は、類似性ダイジェストを比較できる速度を測定します。比較の理論的計算量をO記法で示す形式的な分析と、基準データセットに基づく実測評価の両方を行うことが有用です。
A related property of note is the ability of the algorithm to leverage parallel computational resources; these may include conventional multi-core CPU architectures, as well as massively parallel ones, such as GPUs. To that end, tests should include scalability analysis, which shows speedup as a function of available hardware concurrency.
関連する性質として、並列計算資源を活用できることも挙げられます。これには、従来のマルチコアCPUアーキテクチャや、GPUなどの大規模な並列アーキテクチャが含まれます。このため、テストには、利用可能なハードウェアの並列性に応じてどの程度高速化するかを示すスケーラビリティ分析を含めるべきです。
3.3.2 Sensitivity
3.3.2 感度
Sensitivity is a measure of the ability of an approximate matching algorithm to find correlations among objects based on fine-grained commonality—the smaller the features being correlated, the more sensitive the algorithm is. Clearly, there is a threshold below which the sensitivity will be too high and all objects will appear similar; it is up to the algorithm designer to identify that threshold and incorporate it into the implementation.
Two examples of tests for measuring an algorithm’s sensitivity are fragment detection and single-common-block correlation.
感度は、細かな共通性に基づいてオブジェクト間の相関を見つける、近似照合アルゴリズムの能力の尺度です。相関の対象となる特徴が小さいほど、アルゴリズムの感度は高いです。ただし、対象とする特徴があるしきい値より小さくなると感度が高すぎて、すべてのオブジェクトが類似しているように見えます。アルゴリズムの設計者がそのしきい値を特定し、実装に組み込む必要があります。
アルゴリズムの感度を測定するテストの例として、断片検出と単一共通ブロックの相関の2つがあります。
•Fragment detection. Fragment detection quantifies the length of the shortest sample from a data object, for which the similarity tool reliably correlates the sample and the whole object. Common uses include correlating a disk block, or network packet to file.
•断片検出。断片検出では、類似性ツールがサンプルとオブジェクト全体を確実に相関付けられる、データオブジェクトからの最短サンプルの長さを定量化します。一般的な用途には、ディスクブロックまたはネットワークパケットをファイルに相関付けることが含まれます。
•Single-common-block correlation. The single-common-block correlation test is designed to characterize the behavior of an algorithm in the case where two files share a single common object. That is, given two files f₁ and f₂ that share a common object O (but are otherwise dissimilar), what is the smallest O for which the similarity tool reliably correlates the two targets?
•単一共通ブロック相関。このテストは、2つのファイルが1つの共通オブジェクトを共有している場合のアルゴリズムの動作を特徴付けます。つまり、オブジェクト O を1つ共有する（それ以外は互いに異なる）2つのファイル f₁ と f₂ があるとき、類似性ツールが2つの対象を確実に相関付けるために必要な O の最小サイズはどれくらいか、という問いです。
3.3.3 Robustness
3.3.3 堅牢性
Robustness is a measure of the ability of an approximate matching algorithm to find correlation among related objects in the presence of noise and routine transformations. Common transformations include internal fragmentation (e.g., during network transmission) and misalignment (adding content during artifact editing).
堅牢性とは、ノイズや日常的な変換が加わった状態でも、近似マッチングアルゴリズムが関連オブジェクト間の相関を見つけられる能力を測る指標です。一般的な変換には、内部断片化（例：ネットワーク伝送時）や位置ずれ（成果物の編集時に内容が追加されること）が含まれます。
Alignment robustness and white noise resistance are examples of tests that measure an algorithm’s robustness.
位置合わせに対する堅牢性とホワイトノイズ耐性は、アルゴリズムの堅牢性を測定するテストの例です。
•Alignment robustness. Alignment robustness is an attempt to quantify the sensitivity of an algorithm to alignment shifts. Specifically, the test analyzes the impact of inserting sequences of bytes at the beginning of one of the compared artifacts.
•位置合わせに対する堅牢性。位置合わせに対する堅牢性は、アルゴリズムが位置ずれにどの程度敏感かを定量化する試みです。具体的には、比較対象の成果物の一方の先頭にバイト列を挿入した場合の影響を分析します。
•White noise resistance. This test measures the amount of (uniformly) random noise that can be added to an object before the approximate matching algorithm becomes unable to correlate the original and the modified version. For example, for ssdeep [5] it was shown that a few changes distributed over the input are sufficient to prevent a match [6].
•ホワイトノイズ耐性。このテストでは、近似マッチングアルゴリズムが元のオブジェクトと変更後のオブジェクトを相関付けられなくなるまでに、オブジェクトへ追加できる（一様な）ランダムノイズの量を測定します。たとえばssdeep [5]では、入力全体に分散したわずかな変更だけでマッチを妨げるのに十分であることが示されています[6]。
参考文献
1.A. Z. Broder. “On the resemblance and containment of documents,” in In Compression and Complexity of Sequences (SEQUENCES’97). IEEE Computer Society, 1997, pp. 21–29.
1.A. Z. Broder「文書の類似性と包含について」、Compression and Complexity of Sequences（SEQUENCES’97）所収、IEEE Computer Society、1997年、21–29頁。
2.V. Roussev. “An evaluation of forensic similarity hashes,” Digital Forensic Research Workshop, vol. 8, pp. 34–41, 2011.
2.V. Roussev「フォレンジック類似ハッシュの評価」、Digital Forensic Research Workshop、第8巻、34–41頁、2011年。
3.F. Breitinger, G. Stivaktakis, and H. Baier. “FRASH: A framework to test algorithms of similarity hashing,” in 13th Digital Forensics Research Conference (DFRWS’13), Monterey, August 2013.
3.F. Breitinger、G. Stivaktakis、H. Baier「FRASH：類似ハッシュアルゴリズムをテストするフレームワーク」、第13回デジタルフォレンジック研究会議（DFRWS’13）、モントレー、2013年8月。
4.F. Breitinger, H. Liu, C. Winter, H. Baier, A. Rybalchenko, and M. Steinebach. “Towards a process model for hash functions in digital forensics,” 5th International Conference on Digital Forensics & Cyber Crime, September 2013.
4.F. Breitinger、H. Liu、C. Winter、H. Baier、A. Rybalchenko、M. Steinebach「デジタルフォレンジックにおけるハッシュ関数のプロセスモデルに向けて」、第5回デジタルフォレンジック・サイバー犯罪国際会議、2013年9月。
5.J. Kornblum. “Identifying almost identical files using context triggered piecewise hashing,” Digital Forensic Research Workshop (DFRWS), vol. 3S, pp. 91–97, 2006.
5.J. Kornblum「コンテキスト起動型分割ハッシュを用いたほぼ同一のファイルの識別」、Digital Forensic Research Workshop（DFRWS）、第3S巻、91–97頁、2006年。
6.H. Baier and F. Breitinger. “Security aspects of piecewise hashing in computer forensics,” IT Security Incident Management & IT Forensics (IMF), pp. 21–36, May 2011.
6.H. Baier、F. Breitinger「コンピュータフォレンジックにおける分割ハッシュのセキュリティ側面」、IT Security Incident Management & IT Forensics（IMF）、21–36頁、2011年5月。
7.F. Breitinger, G. Stivaktakis, and V. Roussev. “Evaluating Detection Error Trade-offs for Bitwise Approximate Matching Algorithms,” 5th ICST Conference on Digital Forensics & Cyber Crime (ICDF2C), September 2013.
7.F. Breitinger、G. Stivaktakis、V. Roussev「ビット単位近似マッチングアルゴリズムにおける検出誤差のトレードオフ評価」、第5回ICSTデジタルフォレンジック・サイバー犯罪会議（ICDF2C）、2013年9月。
8.L. C. Noll. (2001) Fowler / Noll / Vo (FNV) Hash. [Online]. Available: http://www.isthe.com/chongo/tech/comp/fnv/index.html
8.L. C. Noll（2001年）Fowler / Noll / Vo（FNV）ハッシュ。[オンライン] 入手先：http://www.isthe.com/chongo/tech/comp/fnv/index.html
付録1：バイト単位の近似マッチングのための参照テスト方法
This appendix presents detailed example methodologies for testing bytewise approximate matching algorithms with controlled and real data.
本付録では、制御データおよび実データを用いてバイト単位の近似マッチングアルゴリズムをテストするための詳細な方法の例を示します。
Testing with controlled data. The main purpose of controlled data experiments is to know exactly the ground truth by carefully constructing the test cases. In this case, the goal is to build artifacts—files—that have known common substrings. The most practical way to accomplish this is to use (pseudo-)random data.
制御データによるテスト。制御データ実験の主な目的は、テストケースを注意深く構築することで、正解データを正確に把握することです。この場合の目標は、既知の共通部分文字列を持つ成果物（ファイル）を作成することです。これを実現する最も実用的な方法は、（疑似）ランダムデータを使うことです。
The first step is to determine appropriate sizes for the constructed files. This will vary depending on the intended application, but if the size distribution of the almost 1,000,000 files in the govdoc-corpus can be treated as representative, it may be sufficient to evaluate algorithms against six reference file sizes—1, 4, 16, 64, 256 and 1024 KiB. As shown in Table 1, nearly 91% of all files in this set are smaller than 1 MiB.
最初の手順は、作成するファイルに適したサイズを決めることです。これは想定用途によって異なりますが、govdoc-corpus内の約1,000,000ファイルのサイズ分布を代表的なものと見なせるなら、1、4、16、64、256、1024 KiBの6種類の参照ファイルサイズでアルゴリズムを評価すれば十分な場合があります。表1に示すように、この集合のファイルの約91%は1 MiB未満です。
Table 1. Cumulative empirical file size distribution in the govdoc-corpus.
表1．govdoc-corpusにおけるファイルサイズの累積実測分布。
| File size range (KiB) | \(\le 4\) | \(\le 16\) | \(\le 64\) | \(\le 256\) | \(\le 1024\) |
| Cumulative probability (%) | 5.4 | 20.71 | 52.54 | 75.82 | 90.60 |
| ファイルサイズ範囲（KiB） | \(\le 4\) | \(\le 16\) | \(\le 64\) | \(\le 256\) | \(\le 1024\) |
| 累積確率（%） | 5.4 | 20.71 | 52.54 | 75.82 | 90.60 |
Test methodology. The proposed approach consists of four basic steps: build a set of unique files, create mutations of them, run approximate matching comparisons between the original and modified versions (for all algorithms), and summarize the results with appropriate statistics. In regards to producing the file modifications, we provide four example modification methods, below. Each corresponds to one of the four test examples listed in sections 3.3.2 and 3.3.3. In each, f₁ refers to the original randomly generated file, f₂ refers to a copy of that file that is transformed according to the method, and X refers to a set of object sizes to be tested with that method.
試験方法。提案する手法は基本的に4段階で構成されます。固有ファイルの集合を作成し、その変異版を作り、元版と変更版を（すべてのアルゴリズムで）近似照合して、適切な統計量で結果を要約します。ファイルを変更する方法の例を以下に4つ示します。それぞれ、3.3.2節および3.3.3節に記載した4つの試験例に対応します。各方法において、f₁は元のランダム生成ファイル、f₂はそのファイルを各方法に従って変換したコピー、Xは各方法で試験するオブジェクトサイズの集合を表します。
•Fragment detection: f₂ is a fragment of f₁, selected randomly for each run of the test, where the size of f₂ ranges the values X, which are selected such that each element of X is less than the size of f₁. For reference, the default settings of FRASH [3] recommend X = {0.01s₁, 0.02s₁, 0.03s₁, 0.04s₁, 0.05s₁, 0.1s₁, 0.15s₁, 0.2s₁, 0.3s₁, 0.5s₁}, where s₁ is the size of f₁.
•断片検出：f₂はf₁の断片であり、試験の実行ごとにランダムに選択します。f₂のサイズはXの各値を取り、Xの各要素はf₁のサイズより小さくなるよう選びます。参考として、FRASH [3]の既定設定ではX = {0.01s₁, 0.02s₁, 0.03s₁, 0.04s₁, 0.05s₁, 0.1s₁, 0.15s₁, 0.2s₁, 0.3s₁, 0.5s₁}を推奨します。ここでs₁はf₁のサイズです。
•Single-common-block correlation: f₁ and f₂ have equal size and share a common byte string (block), the size of which ranges across the values in X. The position of the common block and its content are chosen randomly for each file/run combination. For reference, the default settings of FRASH [3] recommend X = {0.01s₁, 0.02s₁, 0.03s₁, 0.04s₁, 0.05s₁, 0.1s₁, 0.15s₁, 0.2s₁, 0.3s₁, 0.5s₁}, where s₁ is the size of f₁.
•単一共通ブロック相関：f₁とf₂は同じサイズで、共通のバイト文字列（ブロック）を共有します。そのブロックのサイズはXの各値をとります。共通ブロックの位置と内容は、ファイルと実行の組み合わせごとにランダムに選びます。参考として、FRASH [3]の既定設定ではX = {0.01s₁, 0.02s₁, 0.03s₁, 0.04s₁, 0.05s₁, 0.1s₁, 0.15s₁, 0.2s₁, 0.3s₁, 0.5s₁}を推奨します。ここでs₁はf₁のサイズです。
•Alignment robustness: f₂ is prefixed with a random byte string of size s where s ranges across the values in X. The content of the prefix is randomized across runs. For reference, the default settings of FRASH [3] recommend X = {0.01s₁, 0.02s₁, 0.03s₁, 0.04s₁, 0.05s₁, 0.1s₁, 0.15s₁, 0.2s₁}, where s₁ is the size of f₁.
•位置合わせに対する堅牢性：f₂の先頭に、サイズsのランダムなバイト列を付加します。sはXの各値をとります。接頭辞の内容は実行ごとにランダム化します。参考として、FRASH [3]の既定設定ではX = {0.01s₁, 0.02s₁, 0.03s₁, 0.04s₁, 0.05s₁, 0.1s₁, 0.15s₁, 0.2s₁}を推奨します。ここでs₁はf₁のサイズです。
•Random-noise resistance: f₂ is edited with some number, n, of single-byte edit operations (either additions, deletions or replacements) applied to it at random, where n ranges across the values in X. For reference, the default settings of FRASH [3] recommend X = {0.005s₁, 0.01s₁, 0.015s₁, 0.02s₁, 0.025s₁}, where s₁ is the size of f₁ in bytes and the values of X are rounded to the nearest whole number.
•ランダムノイズ耐性：f₂に対し、単一バイトの編集操作（追加、削除、置換のいずれか）をn回ランダムに適用します。nはXの各値をとります。参考として、FRASH [3]の既定設定ではX = {0.005s₁, 0.01s₁, 0.015s₁, 0.02s₁, 0.025s₁}を推奨します。ここでs₁はバイト単位のf₁のサイズであり、Xの値は最も近い整数に丸めます。
For every choice of file size and modification method, each test has two additional parameters: file count and number of runs. The former specifies the number of files in the test set; the latter specifies the number of independent test runs to be executed (where each run creates its own new test set).
ファイルサイズと変更方法の各選択について、テストにはさらに、ファイル数と実行回数という2つのパラメータがあります。前者はテストセット内のファイル数を指定します。後者は、実行する独立したテストの回数を指定します。各実行では、新しいテストセットをそれぞれ作成します。
Testing with real data.
実データを使用するテスト。
As already mentioned, two of the main challenges in testing with real data are the choice of representative samples, and the establishment of ground truth. In respect to the former the choice depends, to some degree, on the expected characteristics of the target data. For example, for general evaluation of artifacts found on the Internet, the govdocs-corpus is a good starting point.
既に述べたように、実データを用いるテストの主な課題の2つは、代表的なサンプルの選択とグラウンドトゥルースの確立です。前者の選択は、対象データに想定される特性にある程度依存します。例えば、インターネット上で見つかる成果物を一般的に評価する場合、govdocs-corpusを出発点にできます。
The focus of this section is to provide an approach for establishing ground truth using automated means. The proposed approach is to use the longest common substring (LCS) as the reference metric and to characterize the behavior of bytewise approximate matching algorithms with respect to this metric.
本節の目的は、自動化された方法でグラウンドトゥルースを確立するためのアプローチを示すことです。提案するアプローチは、最長共通部分文字列（LCS）を基準の指標として使用し、この指標に対するバイト単位の近似照合アルゴリズムの挙動を明らかにするものです。
Using a string comparison algorithm as a reference is a natural choice given that the algorithms treat the data objects as plain strings with no attempt to parse or interpret them. LCS should be considered a first-order approximation; two objects may have a lot more in common than what the LCS result suggests, so further refinements are to be expected at a later stage.
これらのアルゴリズムは、データオブジェクトを構文解析や解釈を行わない単純な文字列として扱うため、文字列比較アルゴリズムを基準にすることは自然です。LCSは一次近似と考えるべきです。2つのオブジェクトはLCSの結果が示す以上の共通性を持つ場合があるため、後の段階でさらに精緻化することが見込まれます。
Given an unordered pair of files \((f_1, f_2)\), define the absolute \((L_a)\) and relative \((L_r)\) results as follows:
順序を問わないファイルの対\((f_1, f_2)\)について、絶対的な結果\((L_a)\)と相対的な結果\((L_r)\)を次のように定義します。
where \(|f|\) denotes the file size in bytes.
ここで、\(|f|\)はファイルサイズをバイト単位で表します。
Broadly, any two strings sharing a substring are related; however, we suggest a more practical lower bound on the minimum amount of commonality to declare two files related. Specifically, we require that the absolute size \(L_a\) is at least 100 (bytes) and that the relative result \(L_r\) exceeds 0.5% of the size of the smaller file. More formally, the true positive function \(\mathit{TP}_{\mathit{lcs}}(f_1, f_2)\) is defined as
大まかに言えば、部分文字列を共有する任意の2つの文字列には関連があります。しかし、2つのファイルを関連ありと判定するための共通性の最小量について、より実用的な下限を提案します。具体的には、絶対サイズ \(L_a\) が100バイト以上であり、相対値 \(L_r\) が小さい方のファイルサイズの0.5%を超えることを求めます。より形式的には、真陽性関数 \(\mathit{TP}_{\mathit{lcs}}(f_1, f_2)\) を次のように定義します。
(Note: result of \(L_r\) is rounded and thus 0.5 is equal to 1.)
（注：\(L_r\)の結果は丸められるため、0.5は1となります。）
Clearly, the true negative function \(\mathit{TN}_{\mathit{lcs}}(f_1, f_2) = \neg \mathit{TP}_{\mathit{lcs}}(f_1, f_2)\).
明らかに、真陰性関数は \(\mathit{TN}_{\mathit{lcs}}(f_1, f_2) = \neg \mathit{TP}_{\mathit{lcs}}(f_1, f_2)\) です。
Approximate ground truth LCS is a well-studied problem and has known solutions of quadratic time complexity–\(O(mn)\), where \(m\) and \(n\) are the string lengths. Given that files can be large, the exact solution quickly becomes too burdensome to be practical. Therefore, we suggest an approximation of the longest common substring which, by design, provides a lower bound on LCS; details are given in Appendix 2.
近似グラウンドトゥルース LCSは十分に研究された問題であり、文字列長を\(m\)と\(n\)とすると、2次の時間計算量\(O(mn)\)となる解法が知られています。ファイルは大きい場合があるため、厳密解を求める負担はすぐに実用的でないほど大きくなります。そこで、最長共通部分文字列の近似を提案します。この近似は、その設計によりLCSの下界を与えます。詳細は付録2に示します。
Appendix 2: Approximate longest common substring
付録2：近似最長共通部分文字列
The basic idea of the approximate longest common substring metric (aLCS) is not to compare files byte-by-byte but rather block-by-block. To identify the blocks, we apply the rolling hash from ssdeep. Our settings aim at having blocks of ≈ 80 bytes. Instead of comparing blocks bytewise, each one is hashed and compared using the 64-bit FNV-1a hash [8]. Besides the hash value, we also store the entropy and length for each block in a final linear list called alcs-digest; a reference implementation is publicly available.1
近似最長共通部分文字列（aLCS）指標の基本的な考え方は、ファイルをバイトごとに比較するのではなく、ブロックごとに比較することです。ブロックの特定にはssdeepのローリングハッシュを適用します。設定では、ブロックの大きさを約80バイトとします。ブロックをバイト単位で比較する代わりに、それぞれをハッシュ化し、64ビットFNV-1aハッシュ[8]で比較します。ハッシュ値に加えて各ブロックのエントロピーと長さを保存し、alcs-digestと呼ぶ最終的な線形リストを作成します。参照実装は公開されています。1
Let La denote the absolute longest common substring of two alcs-digests. Comparing two alcs-digests is equal to comparing two linear lists. If the hash of an item on list A has the same value as the hash of an item on list B, we are convinced that La is greater than or equal to the length of the blocks corresponding to the hashes. If two consecutive items on list A have the same hash values as two consecutive items on list B, we sum up the length of both blocks to receive La. Of course, the usage of hash functions implies the possibility of false positives. Nevertheless, this is an easy and fast method to get a good estimation of the longest common substring.
Laを2つのalcs-digest間の絶対最長共通部分文字列とします。2つのalcs-digestの比較は、2つの線形リストの比較と同等です。リストA上の項目のハッシュ値がリストB上の項目のハッシュ値と一致すれば、該当するブロックの長さ以上のLaがあると判断できます。リストA上の連続する2項目のハッシュ値がリストB上の連続する2項目と一致する場合、両ブロックの長さを合計してLaを得ます。もちろん、ハッシュ関数の使用には偽陽性の可能性が伴います。それでも、最長共通部分文字列を適切に推定するための簡便で高速な方法です。
Implementation details. The tool is implemented in C and proceeds in three steps: reading, hashing and comparing, which are declared in the main function. Because it is a command line tool, it can be executed by ./aLCS <dir>.
実装の詳細。本ツールはC言語で実装され、メイン関数で宣言された読み込み、ハッシュ化、比較の3段階で処理します。コマンドラインツールであり、./aLCS <dir> として実行できます。
First, all files in dir are read. Out of the file names, we create “hash-tasks” which are added to a thread pool. A hash-task contains the path to a file and denotes “hash file”. Depending on the number of threads, these tasks are processed. Once all alcs-digests are created, we perform an all against-all comparison. Therefore, we create compare-tasks (compare file₁ against file₂) which are again added to the thread pool. The output is printed to the standard output.
最初にdir内のすべてのファイルを読み込みます。ファイル名から「ハッシュタスク」を作成し、スレッドプールに追加します。ハッシュタスクはファイルへのパスを含み、「ファイルをハッシュ化する」ことを表します。スレッド数に応じてタスクを処理します。すべてのalcs-digestを作成したら、全ファイル間の総当たり比較を行います。そのため、比較タスク（file₁とfile₂を比較）を作成し、再びスレッドプールに追加します。出力は標準出力に表示します。
The reference implementation has three main settings configurable in header/config.h. MIN_LCS is the minimum \(L_a\) length which is printed to stdio and is by default 0 (all comparisons are printed). The THREAD_POOL_QUEUE_SIZE is the length of the queue and should be \(\frac{\mathrm{fileamount} \times (\mathrm{fileamount} - 1)}{2}\). NUMTHREADS is the number of threads which should be equal to the number of cores.
参照実装には、header/config.h で設定できる主な設定が3つあります。MIN_LCS は stdio に表示する最小の \(L_a\) 長で、既定値は0（すべての比較を表示）です。THREAD_POOL_QUEUE_SIZE はキュー長で、\(\frac{\mathrm{fileamount} \times (\mathrm{fileamount} - 1)}{2}\) とすべきです。NUMTHREADS はスレッド数で、コア数と同じにすべきです。
Verification of ground truth. To verify the correctness of our approximate longest common substring, we compared the results against LCS for a subset of t5. In order to do this, we implemented a parallelized LCS tool written in C++.2 The output is a summary file structured similarly to our aLCS output: file₁ | file₂ | LCS. A small, ruby script is used to compare the LCS- summary and aLCS-summary.
正解データの検証。近似最長共通部分文字列の正確性を検証するため、t5の一部について結果をLCSと比較しました。このため、C++で並列化したLCSツールを実装しました。2 出力はaLCSの出力と同様の形式を持つ要約ファイルであり、file₁ | file₂ | LCSとなります。小さなRubyスクリプトを用いてLCS要約とaLCS要約を比較します。
Our subset consists of 201 randomly selected files. We compare these files using aLCS as well as LCS and finally compare both summaries. All \(\frac{(200) \times (201)}{2} = 20{,}100\) comparisons yield alcs scores in the correct range, i.e., \(0 \le \mathit{alcs} \le \mathit{lcs}\).
対象サブセットはランダムに選んだ201ファイルから成ります。これらのファイルをaLCSとLCSの両方で比較し、最後に2つの要約を比較します。全ての \(\frac{(200) \times (201)}{2} = 20{,}100\) 件の比較で、alcsスコアは正しい範囲、すなわち、\(0 \le \mathit{alcs} \le \mathit{lcs}\) となりました。
We also consider the distribution of the differences between the LCS and aLCS scores. Specifically, we define dr for files f1 and f2 as follows:
LCSスコアとaLCSスコアの差の分布も検討します。具体的には、ファイルf1およびf2について、drを次のように定義します。
In other words, we consider the score difference relative to the size of the smaller of the two files, and build the empirical distribution in Table 2. As we can see, upwards of 95% of the observed differences do not exceed 3% of the size of the smaller files – we consider this a reasonable starting point for our purposes (further research may refine this). If anything, this should give tools a slight boost as the available commonality would be underestimated.
言い換えると、2つのファイルのうち小さい方のサイズに対するスコア差を考慮し、表2の実測分布を作成します。見てのとおり、観測された差の95%超は、小さい方のファイルサイズの3%を超えません。この値は本目的に対する妥当な出発点と考えます（今後の研究で改良される可能性があります）。むしろ、利用可能な共通性が過小評価されることになるため、これはツールにわずかに有利に働くはずです。
Table 2. Empirical probability distribution function (pdf) and cumulative distribution function (cdf) for dr.
表2．drの実測確率分布関数（pdf）および累積分布関数（cdf）。
| \(X\) | 0 | 1 | 2 | 3 | 4 | 5 | 10 | 15 | 20 |
| \(P_r\{d_r = X\}\) | 0.8869 | 0.0449 | 0.0155 | 0.0040 | 0.0047 | 0.0116 | 0.0062 | 0.0001 | 0.0000 |
| \(P_r\{d_r \le X\}\) | 0.8869 | 0.9318 | 0.9473 | 0.9513 | 0.9561 | 0.9677 | 0.9834 | 0.9992 | 0.9999 |
| \(X\) | 0 | 1 | 2 | 3 | 4 | 5 | 10 | 15 | 20 |
| \(P_r\{d_r = X\}\) | 0.8869 | 0.0449 | 0.0155 | 0.0040 | 0.0047 | 0.0116 | 0.0062 | 0.0001 | 0.0000 |
| \(P_r\{d_r \le X\}\) | 0.8869 | 0.9318 | 0.9473 | 0.9513 | 0.9561 | 0.9677 | 0.9834 | 0.9992 | 0.9999 |