Randomized LU decomposition: An Algorithm for Dictionaries Construction
Aviv Rotbart${^1
In recent years, distinctive-dictionary construction has gained importance due to his usefulness in data processing. Usually, one or more dictionaries are constructed from a training data and then they are used to classify signals that did not participate in the training process. A new dictionary construction algorithm is introduced. It is based on a low-rank matrix factorization being achieved by the application of the randomized LU decomposition to a training data. This method is fast, scalable, parallelizable, consumes low memory, outperforms SVD in these categories and works also extremely well on large sparse matrices. In contrast to existing methods, the randomized LU decomposition constructs an under-complete dictionary, which simplifies both the construction and the classification processes of newly arrived signals. The dictionary construction is generic and general that fits different applications. We demonstrate the capabilities of this algorithm for file type identification, which is a fundamental task in digital security arena, performed nowadays for example by sandboxing mechanism, deep packet inspection, firewalls and anti-virus systems. We propose a content-based method that detects file types that neither depend on file extension nor on metadata. Such approach is harder to deceive and we show that only a few file fragments from a whole file are needed for a successful classification. Based on the constructed dictionaries, we show that the proposed method can effectively identify execution code fragments in PDF files.\\ \noindent Keywords. Dictionary construction, classification, LU decomposition, randomized LU decomposition, content-based file detection, computer security.
LaTeX-headers.tex
%\usepackage[title]{appendix}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{bbm}
\usepackage{verbatim}
\usepackage{graphicx}
\usepackage{subfigure}
\usepackage{afterpage}
\usepackage{etoolbox}
\usepackage{footbib}
\usepackage{float}
\usepackage{algorithmic}
\usepackage[algosection,algoruled,vlined]{algorithm2e}
\usepackage{cite}
\usepackage{url}

\numberwithin{equation}{section}
\numberwithin{figure}{section}
\numberwithin{table}{section}

\makeatletter
\renewcommand{\p@subfigure}{\thefigure}
\makeatother

\newtheorem{definition}{Definition}[section]
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{rem}[theorem]{Remark}

\newcommand{\repeatable}[2]{\makeatletter \global\expandafter\def\csname repText@#1\endcsname {#2} \makeatother #2}
\newcommand{\repeatxt}[1]{\makeatletter \expandafter\csname repText@#1\endcsname \makeatother}
\newcommand{\repeathm}[3]{{\renewcommand{\thetheorem}{\ref{#2}}\begin{#1}\repeatxt{#3}\end{#1}}}

\newtoggle{citeInAbstract}
\toggletrue{citeInAbstract}
\newcommand{\abstractcite}[1]{\iftoggle{citeInAbstract}{\footcite{#1}}{}}

\newcommand{\usecrop}[2]
{
	\newlength{\cropwidth}
	\setlength{\cropwidth}{\the\textwidth}
	\addtolength{\cropwidth}{#1}
	\newlength{\cropheight}
	\setlength{\cropheight}{\the\textheight}
	\addtolength{\cropheight}{#2}
	\usepackage[width=\the\cropwidth,height=\the\cropheight,center]{crop}
}
\DeclareMathOperator{\colspan}{column-span}
\DeclareMathOperator{\mean}{mean}

\DeclareMathAlphabet{\mathpzc}{OT1}{pzc}{m}{it}

\DeclareMathOperator{\len}{len}
\DeclareMathOperator{\source}{s}
\DeclareMathOperator{\target}{t}
\DeclareMathOperator{\vol}{vol}
\DeclareMathOperator{\lpr}{lpr}
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\proj}{proj}
\newcommand{\transpose}[1]{#1^T}
\newcommand{\abs}[1]{\left | #1 \right |}
\newcommand{\absinline}[1]{| #1 |}
\newcommand{\norm}[1]{\left \| #1 \right \|}
\newcommand{\norminline}[1]{\| #1 \|}

RandLuApps_paper.tex
% The manuscript version.
%\documentclass{article}
% The double-column version.
\documentclass[10pt,twocolumn,twoside]{IEEEtran}

%\documentclass[journal]{IEEEtran}
% The single-column version.
%\documentclass[12pt,onecolumn,twoside]{IEEEtran}


%\usepackage[T1]{fontenc}
\input{LaTeX-headers}
\usepackage[utf8]{inputenc}
\usepackage{authblk}
\usepackage{epstopdf}
\usepackage{multirow}
\usepackage{xcolor,colortbl}

\newtheorem{conjecture}[theorem]{Conjecture}
%\usecrop{1.69in}{1.5in}
\newcommand{\newdef}{\stackrel{\Delta}{=}}

\makeatletter
\newcommand*{\rom}[1]{\expandafter\@slowromancap\romannumeral #1@}
\makeatother

\makeatletter
\newcommand{\thickhline}{%
    \noalign {\ifnum 0=`}\fi \hrule height 1pt
    \futurelet \reserved@a \@xhline
}
\newcolumntype{"}{@{\hskip\tabcolsep\vrule width 1pt\hskip\tabcolsep}}
\makeatother


\begin{document}
\title{Randomized LU decomposition: An Algorithm for Dictionaries Construction}


\author
{Aviv Rotbart${^1}$\thanks{Corresponding author: aviv.rotbart@cs.tau.ac.il}~~Gil Shabat${^2}$~~Yaniv Shmueli${^1}$~~Amir Averbuch${^1}$\\
${^1}$School of Computer Science, Tel Aviv University, Israel\\
${^2}$School of Electrical Engineering, Tel Aviv University, Israel
}

\maketitle

\begin{abstract}
In recent years, distinctive-dictionary construction has gained importance due to his usefulness in data processing.
Usually, one or more dictionaries are constructed from a training
data and then they are used to classify signals that did not
participate in the training process. A new dictionary construction
algorithm is introduced. It is based on a low-rank matrix
factorization being achieved by the application of the randomized LU
decomposition to a training data. This method is fast, scalable, parallelizable,
consumes low memory, outperforms  SVD in these categories and works
also extremely well on large sparse matrices. In contrast to
existing methods, the randomized LU decomposition constructs an
under-complete dictionary, which simplifies both the construction
and the classification processes of newly arrived signals. The
dictionary construction is generic and general  that fits
different applications. We demonstrate the capabilities of this
algorithm for file type identification, which is a fundamental task
in digital security arena, performed nowadays for example by sandboxing mechanism, 
deep packet inspection,  firewalls and anti-virus systems. 
We propose a content-based method that detects file types
that neither depend on file extension nor on metadata. Such
approach is harder to deceive and we show that only a few file
fragments from a whole file are needed for a successful
classification. Based on the constructed dictionaries, we show that
the proposed method can effectively identify execution code
fragments in PDF files.\\

\noindent \textbf{Keywords.} Dictionary construction,
classification, LU decomposition, randomized LU decomposition,
content-based file detection, computer security.
\end{abstract}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
\label{fileRec:sec:introduction}

Recent years have shown a growing interest in dictionary learning.
Dictionaries were found to be useful for applications such as signal
reconstruction, denoising, image impainting, compression, sparse
representation, classification and more.
Given a data matrix $A$, a dictionary learning algorithm produces
two matrices $D$ and $X$ such that $||A-DX||$ is small where $D$ is
called dictionary and $X$ is a coefficients matrix also called
representation matrix. Sparsity of $X$, means that each signal from $A$
is described with only a few signals (also called atoms) from the
dictionary $D$. It is a major property being pursued by many dictionary
learning algorithms. 
The algorithms, which learn dictionaries for sparse representations,
optimize a goal function $\min_{D,X} ||A-DX|| + \lambda||X||_{0}$, which considers both the accuracy and the
sparsity of the solution, by optimizing alternately these two
properties ($\lambda$ is a regularization term). This
construction is computationally expensive and does not scale well to
big data. It becomes even worse when dictionary learning is used for
classification since another distinctive term in addition to the two
aforementioned is being introduced in the objective function. This
term provides the learned dictionary a discriminative ability. This
can be seen for example in the optimization problem $\min_{D,X,W}
||A-DX|| + \lambda||X||_{0} + \xi||H-WX||$ where $W$ is a classifier
and $H$ is a vector of labels. $||H-WX||$ is the penalty term for achieving a
wrong classification.  In order to achieve the described properties,
dictionaries are usually over-complete, namely, they contain more
atoms than the signal dimension. As a consequence, dictionaries are
redundant such that there are linear dependencies between atoms.
Therefore, a given signal can be represented in more than one way
using dictionary atoms. This enables us on one hand to get sparse
representations, but on the other hand it complicates the
representation process because it is
NP-hard to find the sparsest representation for a signal by an
over-complete dictionary~\cite{natarajan1995sparse}.

In this work, we provide a generic way to construct an
under-complete dictionary. Its capabilities will be demonstrated for
signal classification task. Since we do not look for sparse signal
representation, we remove the alternating optimization process
from the construction of over-complete dictionaries.
Our dictionary construction is based on matrix factorization. We use
the randomized LU matrix factorization
algorithm~\cite{shabat2013randomized} for a dictionary construction. This algorithm, which is applied to a given data matrix $A\in\mathbb{R}^{m\times n}$ of $m$ features and $n$ data-points, decomposes $A$ into two matrices $L$ and $U$, where $L$ is the dictionary and $U$ is the coefficient matrix. The size of $L$ is determined by the decaying spectrum of the singular values of the matrix $A$, and bounded by $\min\{n,m\}$. Both $L$ and $U$ are linearly independent. The proposed dictionary construction has couple of advantages: it is fast, scalable, parallelizable and thus can run on GPU and multicore-based systems, consumes low memory, outperforms  SVD in these categories and works extremely well on large sparse matrices. Under this construction, the classification of a newly arrived signal is done by a fast projection method that represents this signal by the columns of the matrix $L$. The computational cost of this method is linear in the input size, while in the under-complete case finding the optimal solution is NP-hard~\cite{natarajan1995sparse}. Approximation algorithms for sparse signal reconstruction, like Orthogonal Matching
Pursuit~\cite{tropp:GIG} or Basis Pursuit~\cite{chen:BasisPursuit}, have no guarantees for general dictionaries.

In order to evaluate the performance of the dictionaries, which are
constructed by the application of the randomized LU algorithm to a training set, we use them to classify
file types. The experiments were conducted on a dataset that
contains files of various types. The goal is to classify each file
or portion of a file to the class describing its type. To the best
of our knowledge, this work is the first to use dictionary learning
method for file type classification. This work considers three
different scenarios that represent real security tasks: examining
the full content of the tested files, classifying a file type using a
small number of fragments from the file and detecting malicious code
hidden inside innocent looking files. While the first two scenarios
were examined by other works, none of the papers described in this work dealt
with the latter scenario. It is difficult to compare our results to other
algorithms since the used datasets are not publicly available. For similar testing conditions, we improve the state-of-the-art
results. The datasets we used will be made publicly available.

The paper has the following structure: Section~\ref{fileRec:sec:related_work} 
reviews related work on dictionary construction and on file content recognition algorithms. 
Section~\ref{fileRec:sec:random_lu} presents the dictionary construction algorithm. 
Section~\ref{fileRec:sec:randLU_dict_classify} shows how to utilize it to develop our 
classification algorithms for file content detection.
Section~\ref{fileRec:subsec:dictionary_size} addresses the problem of computing 
the correct dictionaries sizes needed by the classifiers.
Experimental results are presented in Section~\ref{fileRec:sec:experimental_results} and compared with 
other content classification methods. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Related Work}
\label{fileRec:sec:related_work} Dictionary-based classification models have
been the focus of much recent research leading to results in face recognition~\cite{zhang2010discriminative,
wright2009robust,yang2007feature,yang2011fisher,pham2008joint,jiang2011learning},
digit recognition~\cite{yang2011fisher},  object
categorization~\cite{pham2008joint,jiang2011learning} and more. Many
of these works~\cite{jiang2011learning,zhang2010discriminative,pham2008joint}
utilize the K-SVD~\cite{aharon:ksvd} for their training, or in other
words, for their dictionary learning step. Others define different
objective functions such as the Fisher Discriminative Dictionary
Learning~\cite{yang2011fisher}. Majority of these methods use an
alternating optimization process in order to construct their
dictionary. This optimization procedure seeks a dictionary which is
re-constructive, enables sparse representation and sometimes also has a
discriminative property. In some works (see for
example~\cite{zhang2010discriminative,jiang2011learning}) the
dictionary learning algorithm requires meta parameters to regulate
these properties of the learned dictionary. Finding the optimal
values for these parameters is a challenging task that adds
complexity to the proposed solutions. A dictionary construction,
which uses a multivariate optimization process, is computationally
expensive task (as described in~\cite{pham2008joint}, for example).
The proposed approach in this paper suggests to avoid these complexities by using the
randomized LU Algorithm~\cite{shabat2013randomized}. 
The dictionary it creates is under-complete
where the number of atoms is smaller than the signal dimension.
The outcome is that the dictionary construction is fast that does not compromise its abilities to achieve high classification accuracy.
We improve upon the state-of-the-art results in file type
classification~\cite{amirani2013feature} as demonstrated by the experimental results.

The testing phase in many dictionary learning schemes is simple.
Usually, linear classifier is used to assign test signals to one of
the learned classes~\cite{zhang2010discriminative,jiang2011learning}. However, 
classifier learning combined with dictionary learning adds additional overhead
to the process~\cite{zhang2010discriminative,jiang2011learning}. The proposed
method in this paper does not require to allocate special attention to a
classifier learning. We utilize the output from the randomized LU
algorithm to create a projection matrix. This matrix is used to
measure the distance between a test signal and the dictionary. The
signal is then classified as belonging to the class that
approximates it best. The classification process is fast and simple.
The results described in Section~\ref{fileRec:sec:experimental_results} show
high accuracy in the content-based file type classification task.

We used this classification task to test the randomized LU
dictionary construction and to measure its discriminative power.
This task is useful in computer security applications like
anti-virus systems and firewalls that need to detect files transmitted
through network and response quickly to threats.
Previous works in this field use mainly deep packet inspection (DPI) 
and byte distribution frequency features (1-gram statistics) in order to 
analyze a file~\cite{calhoun2008predicting,ahmed2009improving,amirani2013feature,
ahmed2010fast,veenman2007statistical,karresand2006file,erbacher2007identification,li2005fileprints,mcdaniel2003content}.
In some works, other features were tested like consecutive byte
differences~\cite{amirani2013feature,calhoun2008predicting} and
statistical properties of the content~\cite{calhoun2008predicting}.
The randomized LU decomposition~\cite{shabat2013randomized}
construction is capable of dealing with a large number of features.
This enables us to test our method on high dimensional feature sets
like double-byte frequency distributions (2-grams statistics) where
each measurement has 65536 Markov-walk based features. We refer the
reader to~\cite{amirani2013feature} and references within for an
exhaustive comparison of the existing methods for content-based file
type classification.

Throughout this work, when $A$ is a matrix, the norm $\Vert A
\Vert$ indicates the spectral norm (the largest singular value of
$A$) and when $A$ is a vector it indicates the standard $l_2$ norm
(Euclidean norm).



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{algorithm}[H]
%\caption{LU Decomposition with Partial Pivoting}
%\label{fileRec:alg:randomized_lu}
%\textbf{Input:} $A$ matrix of size $m \times n$ to decompose; $k$  desired rank; $l$ number of columns to use.\\
%\textbf{Output:} Matrices $P,L,U$ such that $PA=LU$ where $L$ and
%$U$ are the lower and upper triangular, respectively, $P$ is an
%orthogonal permutation =matrix given by $P=\Pi_{n-1} \cdots \Pi_{1}$
%where $\Pi_{k}$ is an interchange permutation obtained by swapping
%rows $k$ and $piv(k)$ of $I_{n}$.
%\begin{algorithmic}[1]
%\STATE Initialize $L$ to identity and $U$ to zero matrices \STATE
%\For{$j=1$ to $n$}{
%         \hspace{1cm} if $j=1$     \\
%         \hspace{1.5cm} $v=A(:,1)$    \\
%         \hspace{1cm} else     \\
%         \hspace{1.5cm} $\tilde{a}=\Pi_{j-1} \cdots \Pi_{1}A(:,j)$  \\
%         \hspace{1.5cm} Solve $L(1:j-1,1:j-1)z=\tilde{a}(1:j-1)$ for
%         $z\in R^{j-1}$\\
%         \hspace{1.5cm} $U(1:j-1,j)=z,~~v(j:n)=\tilde{a}(j:n)-L(j:n,1:j-1)z$\\
%         }
%\end{algorithmic}
%\end{algorithm}


\section{Randomized LU}
\label{fileRec:sec:random_lu}
In this section, we present the randomized LU decomposition algorithm for computing the rank $k$ LU approximation
of a full matrix (Algorithm \ref{fileRec:alg:randomized_lu}). 
The main building blocks of the algorithm are random projections and Rank Revealing LU (RRLU)
\cite{pan2000existence} to obtain a stable low-rank approximation
for an input matrix $A$.

The RRLU algorithm, used in the randomized LU algorithm, reveals the 
connection between LU decomposition of a matrix and its singular values.
This property is very important since it connects between the size of the decomposition 
to the actual numerical rank of the data. Similar algorithms exist for 
rank revealing QR decompositions (see, for example \cite{gu1996efficient}).

\begin{theorem}[\cite{pan2000existence}]
\label{fileRec:trm:rrlu-pan}
Let $A$ be an $m\times n$ matrix ($m \ge n$). 
Given an integer $1 \le k < n$, then the following factorization 
\begin{equation}
\label{fileRec:eq:rrlu_def}
PAQ = \begin{pmatrix} L_{11} & 0 \\ L_{21} & I_{n-k} \end{pmatrix}
\begin{pmatrix} U_{11} & U_{12} \\ 0 & U_{22} \end{pmatrix},
\end{equation}
holds where $L_{11}$ is a lower triangular with ones on the diagonal, $U_{11}$ is an upper triangular, $P$ and $Q$ are orthogonal permutation matrices. 
Let $\sigma_1 \ge \sigma_2 \ge ... \ge \sigma_n \ge 0$ be the singular values of $A$, then:
\begin{equation*}
\label{fileRec:eq:rrlu_def1}
\sigma_k \ge \sigma_{min}(L_{11}U_{11}) \ge \frac{\sigma_k}{k(n-k)+1},
\end{equation*}
and 
\begin{equation*}
\label{fileRec:eq:rrlu_def2}
\sigma_{k+1} \le \Vert U_{22} \Vert \le (k(n-k)+1)\sigma_{k+1}.
\end{equation*}
\end{theorem}

Based on Theorem \ref{fileRec:trm:rrlu-pan}, we have the following definition: 
\begin{definition}[RRLU Rank $k$ Approximation denoted RRLU$_k$] 
Given a RRLU decomposition (Theorem \ref{fileRec:trm:rrlu-pan}) of a matrix $A$ with an integer $k$ (as in Eq. \ref{fileRec:eq:rrlu_def})
such that $PAQ=LU$, then the RRLU rank $k$ approximation is defined by taking $k$ columns 
from $L$ and $k$ rows from $U$ such that
\begin{equation*}
\label{fileRec:eq:rrlu_rank_k_approx}
\text{RRLU}_k(PAQ)=\begin{pmatrix} L_{11} \\ L_{21} \end{pmatrix}
\begin{pmatrix} U_{11} U_{12} \end{pmatrix},
\end{equation*}
where $L_{11}, L_{21}, U_{11}, U_{12}, P$ and $Q$ are defined in Theorem \ref{fileRec:trm:rrlu-pan}.
\end{definition}

\begin{lemma}[~\cite{shabat2013randomized} RRLU Approximation Error] 
The error of the RRLU$_k$ approximation of $A$ is
\label{fileRec:lem:rrlu_approx_err}
\begin{equation*}
\Vert PAQ-\text{RRLU}_k(PAQ) \Vert \le (k(n-k)+1)\sigma_{k+1}.
\end{equation*}
\end{lemma}

Algorithm~\ref{fileRec:alg:randomized_lu} describes the flow of the RLU decomposition algorithm.

\begin{algorithm}[h]
\caption{Randomized LU Decomposition}
\label{fileRec:alg:randomized_lu}
\textbf{Input:} $A$ matrix of size $m \times n$ to decompose; $k$  rank of $A$; $l$ number of columns to use (for example, $l=k+5$).\\
\textbf{Output:} Matrices $P,Q,L,U$ such that $\Vert PAQ-LU \Vert \le \mathcal{O}(\sigma_{k+1}(A))$ where $P$ and $Q$ are orthogonal permutation matrices, 
$L$ and $U$ are the lower and upper triangular matrices, respectively, and $\sigma_{k+1}(A)$ is the ${(k+1)}$th singular value of $A$.
\begin{algorithmic}[1]
\STATE Create a matrix $G$ of size $n \times l$ whose entries are \\
i.i.d. Gaussian random variables with zero mean \\ and unit standard deviation. 
\STATE $Y \gets AG$. 
\STATE Apply RRLU decomposition (See \cite{pan2000existence}) to $Y$ \\ such that $PYQ_y=L_yU_y$.
\STATE Truncate $L_y$ and $U_y$ by choosing the first $k$ columns\\ and $k$ rows, respectively: $L_y \leftarrow L_y(:,1:k)$ and $U_y \leftarrow U_y(1:k,:)$.
 \STATE $B \gets L_y^{\dagger}PA$. ($L_y^{\dagger}$ is the pseudo inverse of $L_y$). 
\STATE Apply LU decomposition to $B$ with column pivoting $BQ=L_bU_b$. 
\STATE $L \gets L_y L_b$. 
\STATE $U \gets U_b$.
\end{algorithmic}
\end{algorithm}

\begin{rem}
In most cases, it is sufficient to compute the regular LU
decomposition in Step 3 instead of computing the RRLU decomposition.
\end{rem}
The running time complexity of Algorithm~\ref{fileRec:alg:randomized_lu} is
$\mathcal{O}(mn(l+k)+l^2m+k^3+k^2n)$ (see Section 4.1 and
\cite{shabat2013randomized} for a detailed analysis). It is shown in
Section 4.2 in \cite{shabat2013randomized} that the error bound of
Algorithm \ref{fileRec:alg:randomized_lu} is given by the following theorem:
\begin{theorem}[\cite{shabat2013randomized}]
\label{fileRec:trm:rand_lu_err} Given a matrix $A$ of size $m\times n$.
Then, its randomized LU decomposition produced by Algorithm
\ref{fileRec:alg:randomized_lu} with integers $k$ and $l$  ($l\ge k$)
satisfies

\begin{equation*}
\begin{split}
&\Vert LU-PAQ \Vert \le \\
&\left(2\sqrt{2nl\beta^2\gamma^2+1}+2\sqrt{2nl}\beta\gamma \left( k(n-k)+1 \right)\right)\sigma_{k+1}(A) ,
\end{split}
\end{equation*}
with probability not less than
\begin{equation*}
\begin{split}
\label{fileRec:eq:rand_lu_err_prob}
1 &-\frac{1}{\sqrt{2\pi(l-k+1)}}\left(\frac{e}{(l-k+1)\beta}\right)^{l-k+1} \\
&-\frac{1}{4(\gamma^2-1)\sqrt{\pi n \gamma^2}}\left(\frac{2\gamma^2}{e^{\gamma^2-1}}\right)^n,
\end{split}
\end{equation*}
for all $\beta>0$ and $\gamma>1$.
\end{theorem}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Randomized LU Based Classification Algorithm}
\label{fileRec:sec:randLU_dict_classify}

This section describes the application of the randomized LU Algorithm
\ref{fileRec:alg:randomized_lu} to a classification task. The training phase
includes dictionary construction for each learned class from a given
dataset. The classification phase assigns a newly arrived signal to
one of the classes based on its similarity to the learned
dictionaries. Let $X\in\mathbb{R}^{m\times n}$ be the matrix whose
$n$ columns are the training signals (samples). Each column is defined by $m$ features. 
Based on Section~\ref{fileRec:sec:random_lu}, we apply the randomized LU decomposition (Algorithm~\ref{fileRec:alg:randomized_lu}) to $X$, yielding
$P X Q \approx L U$.
 The outputs $P$ and $Q$ are orthogonal permutation matrices.
Theorem~\ref{fileRec:trm:dictionaryerr} shows that $P^T L$ forms (up to a
certain accuracy) a basis to $A$. This is the key property of the
classification algorithm.
\begin{theorem}
\label{fileRec:trm:dictionaryerr} Given a matrix $A$. Its randomized LU
decomposition is $PAQ \approx LU$. Then, the error of representing
$A$ by $P^T L$ satisfies:
\begin{equation*}
\begin{split}
&\Vert (P^T L)(P^T L)^\dagger A- A \Vert \le \\ 
&\left(2\sqrt{2nl\beta^2\gamma^2+1}+2\sqrt{2nl}\beta\gamma \left( k(n-k)+1 \right)\right)\sigma_{k+1}(A)\\
\end{split}
\end{equation*}
with the same probability as in Theorem~\ref{fileRec:trm:rand_lu_err}.
\end{theorem}
\begin{proof}
By combining Theorem \ref{fileRec:trm:rand_lu_err} with the fact that $BQ=L_b U_b=L_y^{\dagger}PAQ$  we get
\begin{equation*}
\Vert LU-PAQ \Vert=\Vert L_yL_bU_b-PAQ \Vert=\Vert L_y L_y^\dagger
PAQ-PAQ \Vert .
\end{equation*}
Then, by using the fact that $L_b$ is square and invertible we get
\begin{equation*}
\begin{split}
\Vert L_y L_y^\dagger PAQ-PAQ \Vert &= \Vert L_yL_b L_b^{-1}
L_y^\dagger PAQ-PAQ \Vert \\ 
&= \Vert L L^\dagger PAQ-PAQ \Vert .
\end{split}
\end{equation*}
By using the fact that the spectral norm is invariant to orthogonal
projections, we get
\begin{equation*}
\begin{split}
 &\Vert L L^\dagger PAQ-PAQ \Vert = \Vert L L^\dagger PA-PA \Vert \\
 &= \Vert P^T L L^\dagger PA-A \Vert =\Vert (P^T L)(P^T  L)^\dagger A-A \Vert \\ 
 &\le \left(2\sqrt{2nl\beta^2\gamma^2+1}+2\sqrt{2nl}\beta\gamma \left( k(n-k)+1 \right)\right)\sigma_{k+1}(A),
\end{split}
\end{equation*}
with the same probability as in Theorm~\ref{fileRec:trm:rand_lu_err}.
\end{proof}


Assume that our dataset is composed of the sets 
$X_1,X_2,\ldots,X_l$. We denote by $D_i=P_i^T L_i$ the dictionary
learned from the set $X_i$ by Algorithm~\ref{fileRec:alg:randomized_lu}.
$U_i Q_i^T$ is the corresponding coefficient matrix. It is used to
reconstruct signals from $X_i$ as a linear combination of atoms from
$D_i$. The training phase of the algorithm is done by the
application of Algorithm~\ref{fileRec:alg:randomized_lu} to different
training datasets that correspond to different classes. For each
class, a different dictionary is learned. The size of $D_i$, namely
its number of atoms, is determined by the parameter $k_i$ that is
related to the decaying spectrum of the matrix $X_i$. The dictionaries do not have to be of equal sizes.
A discussion about the dictionary sizes appears later in this
section and in Section~\ref{fileRec:subsec:dictionary_size}. The third parameter, which
Algorithm~\ref{fileRec:alg:randomized_lu} needs, is the number of
projections $l$ on the random matrix columns. $l$ is related to the
error bound in Theorem~\ref{fileRec:trm:rand_lu_err} and it is used to
ensure high success probability for
Algorithm~\ref{fileRec:alg:randomized_lu}. Taking $l$ to be a little bigger
than $k$ is sufficient. The training process of our algorithm is
described in Algorithm~\ref{fileRec:alg:lu_learning}.

\begin{algorithm}[h]
\caption{Dictionaries Training using Randomized LU}
\label{fileRec:alg:lu_learning}	
%\SetAlgoLined
\textbf{Input:} $X = \{X_{1},X_{2},\ldots,X_{r}\}$ training datasets for $r$ sets;
$K = \{k_{1},k_{2},\ldots,k_{r}\}$ dictionary size of each set.\\
\textbf{Output:} $D = \{D_{1},D_{2},\ldots,D_{r}\}$ set of dictionaries.

\begin{algorithmic}[1]
 \STATE \For {$t\in\{1,2,\ldots,r\}$ }{
        $P_t,Q_t,L_t,U_t \leftarrow Randomized~LU~Decomposition(X_t,k_t,l)$,
        $(l\stackrel{\Delta}{=}k_t+5)$; (Algorithm~\ref{fileRec:alg:randomized_lu})\\
          $D_t \leftarrow P^T_t L_t$
    }
\STATE $D \leftarrow \{D_{1},D_{2},\ldots,D_{r}\}$
\end{algorithmic}
\end{algorithm}

For the test phase of the algorithm, we need a similarity measure
that provides a distance between a given test signal and a dictionary.
\begin{definition}
\label{fileRec:def:dist} Let $x$ be a signal and $D$ be a dictionary. The
distance between $x$ and the dictionary $D$ is defined by

\begin{equation*}
dist(x,D) \triangleq || DD^{\dag}x - x||,
\end{equation*}
where $D^{\dag}$ is the pseudo-inverse of the matrix $D$.
\end{definition}

The geometric meaning of $dist(x,D_i)$ is related to the projection
of $x$ onto the column space of $D_i$, where $D_i$ is the dictionary
learned for class $i$ of the problem. $dist(x,D_i)$ denotes the
distance between $x$ and $D_i D_i^{\dag}x$ which is the vector $x$ built with the dictionary $D_{i}$. If $x\in
\colspan\{D_i\}$ then Theorem~\ref{fileRec:trm:dictionaryerr} guarantees
that $dist(x,D_i) < \epsilon$.
 %$x\in \colspan\{X_i\}$
%for a constant $\epsilon$ that depends on $X_i$ between $D_i$ and
%signals from $X_i$ is bounded and small.
For $x\notin \colspan\{D_i\}$, $dist(x,D_i)$ is large.
%is a measure of
%similarity, or distance, between a signal and a dictionary. The
%value of $dist(x,D_i)$ will be small if the signal can be accurately
%approximated by the atoms in $D_i$, and large otherwise.
Thus, $dist$ is used for classification as described in
Algorithm~\ref{fileRec:alg:lu_classify}.


\begin{algorithm}[h]
%\SetAlgoLined
\caption{Dictionary based Classification}
\label{fileRec:alg:lu_classify} 
\textbf{Input:} $x$ input test signal; $D = \{D_1,D_2,\ldots,D_r\}$ set of dictionaries.\\
\textbf{Output:} $t_X$ the classified class label for $x$.

\begin{algorithmic}[1] 
\STATE \For {$t\in\{1,2,\ldots,r\}$}{
        $ERR_t \leftarrow dist(x,D_t)$
    }
\STATE $t_X \leftarrow \arg\min_{t}{\{ERR_t\}}$

\end{algorithmic}
\end{algorithm}

The core of Algorithm~\ref{fileRec:alg:lu_classify} is the $dist$ function
from Definition~\ref{fileRec:def:dist}.
%This function determines the
%distance between a given dictionary and a signal.
 This is done by
examining portion of the signal that is spanned by the dictionary
atoms. If the signal can be expressed with high accuracy as a linear
combination of the dictionary atoms then their $dist$ will be small.
The best accuracy is achieved when the examined signal belongs to the span
of $D_i$. In this case, $dist$ is small and bounded by
Theorem~\ref{fileRec:trm:rand_lu_err}. On the other hand, if the dictionary
atoms cannot express well a signal then their $dist$ will be large.
The largest distance is achieved when a signal is orthogonal to the
dictionary atoms. In this case, $dist$ will be equal to the norm of
the signal. Signal classification is accomplished by finding a
dictionary with a minimal distance to it. This is where the
dictionary size comes into play. The more atoms a dictionary has,
the larger is the space of signals that have low $dist$ to it and
vice versa.
 %The
%parameter $k$ of Algorithm~\ref{fileRec:alg:lu_learning} allows the user
%control over the signal space that is approximated with low $dist$
%by each of the dictionaries.
By adding or removing atoms from a
dictionary, the distances between this dictionary and the test
signals are changed. This affects the classification results of
Algorithm~\ref{fileRec:alg:lu_classify}. The practical meaning of this
observation is that dictionary sizes need to be chosen carefully.
Ideally, we wish that each dictionary will be of $dist$ zero to test
signals of its type, and of large $dist$ values for signals of other
types. However, in reality, some test signals are represented more
accurately by a dictionary of the wrong type than by a dictionary of
their class type. For example, we encountered several cases where
GIF files were represented more accurately by a PDF dictionary
than by a GIF dictionary. An incorrect selection of the dictionary size, $k$, 
will result in either a dictionary that cannot represent well signals of its own class
(causes misdetections), or in a dictionary that represents too
accurately signals from other classes (causes false alarms). 
The first problem occurs when the dictionary is too small whereas the
second occurs when the dictionary is too large. 
In Section~\ref{fileRec:subsec:dictionary_size}, we discuss the problem of finding the 
optimal dictionaries sizes and how they relate it to the spectrum of the training data matrices.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Determining the Dictionaries Sizes}
\label{fileRec:subsec:dictionary_size}
One possible way to find the dictionaries sizes is to observe 
the spectrum decay of the training data matrix. 
In this approach, the number of atoms in each dictionary is selected as the number of singular values 
that capture most of the energy of the training matrix. 
This method is based on estimating the numerical rank of the matrix, namely on the dimension of its column space.
Such a dictionary approximates well the column space of the data and represents accurately signals of its own class.
Nevertheless, it is possible in this construction that dictionary of
a certain class will have high rate of false alarms. 
In other words, this dictionary might approximate signals from other classes with a low error rate.

Two different actions can be taken to prevent this situation. 
The first option is to reduce the size of this dictionary so that it approximates mainly
signals of its class and not from other classes. 
This should be done carefully so that this dictionary still identifies well signals of
its class better than other dictionaries. 
The second option is to increase the sizes of other
dictionaries in order to overcome their misdetections.
This should also be done with caution since we might represent well signals 
from other classes using these enlarged dictionaries. 
Therefore, relying only on the spectrum analysis of the training data is insufficient, 
because this method finds the size of each dictionary independently from the other dictionaries. 
It ignores the interrelations between dictionaries, while the classification algorithm is based on those relations. 
Finding the optimal $k$ values can be described by the following optimization problem: 
\begin{equation}
\label{fileRec:eq:optimize_k}
\arg \min_{k_1,k_2,\ldots,k_r}{\sum_{\substack{1\leq i \leq r \\ 1\leq j \leq r \\ i \ne j}}{C_{i,j,X}(k_i,k_j)}},
\end{equation}
where $C_{i,j,X}(k_i,k_j)$ is the number of signals from class $i$ in the dataset $X$ classified 
as belonging to class $j$ for the respective dictionary sizes $k_i$ and $k_j$. 
The term, which we wish to minimize in Eq.~\ref{fileRec:eq:optimize_k}, is therefore the total number of 
wrong classifications in our dataset $X$ when using a set of dictionaries $D_1,D_2,\ldots,D_r$ 
with sizes $k_1,k_2,\ldots,k_r$, respectively.

We propose an algorithm for finding the dictionary sizes by examining 
each specific pair of dictionaries separately, and thus identifying the optimized dictionary sizes for this pair. 
Then, the global $k$ values for all dictionaries will be determined by finding an agreement between all the local results. 
This process is described in Algorithm~\ref{fileRec:alg:finding_k}.

\begin{algorithm}[h]
%\SetAlgoLined
\caption{Dictionary Sizes Detection}
\label{fileRec:alg:finding_k}

\textbf{Input:} $X = \{X_{1},X_{2},\ldots,X_{r}\}$ training datasets for the $r$ classes; 
$K_{range}$ set of possible values of $k$ to search in.\\
\textbf{Output:} $K = \{k_{1},k_{2},\ldots,k_{r}$\} dictionaries sizes.
 
 \begin{algorithmic}[1]
\STATE	\For {$i,j\in\{1,2,\ldots,r\},\, i<j$}{
        \For {$k_i,k_j\in K_{range}$}{
	        $ERROR_{i,j}(k_i,k_j) \leftarrow C_{i,j,X}(k_i,k_j) + C_{j,i,X}(k_j,k_i)$
    }}
\STATE	$K \leftarrow {\bf find\_optimal\_agreement}(\{ERROR_{i,j}\}_{1\leq i<j\leq r})$
\end{algorithmic}
\end{algorithm}

Algorithm~\ref{fileRec:alg:finding_k} examines each pair of classes $i$ and $j$ for different $k$ values 
and produces the matrix $ERROR_{i,j}$, such that the element $ERROR_{i,j}(s,t)$ is the number of 
classification errors for those two classes, when the dictionary size of class $i$ is $s$ and the dictionary size of class $j$ is $t$. 
This number is the sum of signals from each class that were classified as belonging to the other class. 
The matrix $ERROR_{i,j}$ reveals the ranges of $k$ values for which the number of classification errors is minimal. 
These are the ranges that fit when dealing with a problem that contains only two classes of signals. 
However, many classification problems need to deal with a large number of classes. 
For this case, we create the $ERROR$ matrix for all possible pairs, find the $k$ ranges 
for each pair and then find the optimal agreement between all pairs. 
The step {\bf find\_optimal\_agreement} describes this idea in Algorithm~\ref{fileRec:alg:finding_k}. 
Finding this agreement can be done by making a list of constraints for each pair and then finding $k$ values that satisfy all the constraint 
and bring the minimal solution to the problem described in Eq.~\ref{fileRec:eq:optimize_k}. 
The constraints can bound from below or above the size of a specific dictionary, 
or the relation between sizes of two dictionaries (for example, the dictionary of the first class should have 10 more elements than the dictionary of the second class). 
The step {\bf find\_optimal\_agreement} is not described here formally but demonstrated in details as part of Algorithm~\ref{fileRec:alg:finding_k} in Section~\ref{fileRec:subsec:second_scen}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Experimental Results}
\label{fileRec:sec:experimental_results}

In order to evaluate the performance of the dictionary construction
and classification algorithms in Section~\ref{fileRec:sec:randLU_dict_classify},
Algorithm~\ref{fileRec:alg:lu_classify} was applied to a dataset that
contains six different file types. 
The goal is to classify each file or portion of a file to the class that describes its type. 
This dataset consists of 1200 files that were collected in the wild using automated Web crawlers. 
The files were equally divided into six types: PDF, EXE, JPG, GIF, HTM and DOC.
100 files of each type were chosen randomly as training datasets
and the other 100 files served for algorithms testing. 
In order to get results that reflect the true nature of the problem, no
restrictions were imposed on the file collection process. 
Thus, some files contain only a few kilobytes while others are of  several megabytes in size. 
In addition, some of the PDF files contain pictures, which make
it hard for a content-based algorithm to classify the correct file type. 
Similarly, DOC files may contain pictures and the executables may contain text and pictures. 
Clearly, these phenomena have negative effect on the accuracy of the results in this section. 
However, we chose to leave the dataset in its original form.

Throughout this work, we came across several similar
works~\cite{calhoun2008predicting,ahmed2009improving,amirani2013feature,ahmed2010fast,
veenman2007statistical,karresand2006file,erbacher2007identification,li2005fileprints,mcdaniel2003content}
that classify unknown files to their type based on their content. 
None of these works made their datasets publicly available 
for analysis and comparison with other methods. 
We decided to publicize the dataset of files that we collected to enable future comparisons. 
The details about downloading and using the dataset can be obtained by contacting one of the authors.

Three different scenarios were tested with the common goal of
classifying files or portions of files to their class type, namely,
assigning them to one of the six file types described above. 
In each scenario, six dictionaries were learned that correspond to the six file types. 
Then, the classification algorithm (Algorithm~\ref{fileRec:alg:lu_learning})  was applied to classify
the type of a test fragment or a file. The learning phase, which is
common to all scenarios, was done by applying Algorithm~\ref{fileRec:alg:finding_k} to find 
the dictionary sizes and Algorithm~\ref{fileRec:alg:lu_learning} to construct the dictionaries. 
The testing phase varies according to the specific goal of each scenario. 
Sections \ref{fileRec:subsec:first_scen}, \ref{fileRec:subsec:second_scen} and \ref{fileRec:subsec:execution_code_in_pdf}
provide a detailed description for each scenario and its classification results.

%\begin{algorithm}[H]
%\SetAlgoLined
% \KwData{$X = \{X_{PDF},X_{DOC},X_{EXE},X_{GIF},X_{JPG},X_{HTM}\}$ -  training data \;
%$K = \{K_{PDF},K_{DOC},K_{EXE},K_{GIF},K_{JPG},K_{HTM}\}$ -  dictionary sizes;}
% \KwOut{ $D = \{D_{PDF},D_{DOC},D_{EXE},D_{GIF},D_{JPG},D_{HTM}\}$ - set of dictionaries;}
%
%    \For {$t\in\{PDF,DOC,EXE,GIF,JPG,HTM\}$ }{
%        $L_t,U_t,P_t,Q_t = Randomized~LU~Decomposition(X_t,k_t,k_t+5)$;
%          $D_t = P^T_t L_t$;
%    }
%     $D = \{D_{PDF},D_{DOC},D_{EXE},D_{GIF},D_{JPG},D_{HTM}\}$;\\
%    Output $D$;
%
%\caption{File Content Dictionary Learning}
%\label{fileRec:alg:dict_learning}
%\end{algorithm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Scenario A: Entire File is Analyzed}
\label{fileRec:subsec:first_scen}
In this scenario, we process a whole file and the extracted
features are taken from its entire content. The features are byte frequency
distribution (BFD) that contains 256 features followed by consecutive
differences distribution (CDD) that adds another 256 features. Total of 512 features are measured
for each training and testing files. CDD is used in addition to BFD
because the latter fails to capture any information about bytes
ordering in the file. CDD turned out to be very discriminative and
improved the classification results. The features extracted from
each file were normalized by its size since there are files of various sizes in the dataset. Example for BFD construction is described in
Fig. \ref{fileRec:fig:example_bfd} and example for CDD construction is given
in Fig. \ref{fileRec:fig:example_cdd}.

\begin{figure}[h]
\center 
\framebox[1.1\width]{\Large AABCCCDR} $\Longrightarrow$
\scriptsize
\begin{tabular}{c c}
\hline
Byte &  Probability (BFD) \\
\hline
A & 0.25 \\
B & 0.125 \\
C & 0.375 \\
D & 0.125 \\
R & 0.125 \\
\vdots  & 0 \\
\hline
\end{tabular}
\caption{Byte Frequency Distribution (BFD) features extracted from
the file fragment ``AABCCCDR''.} 
\label{fileRec:fig:example_bfd}
\end{figure}

\begin{figure}[h]
\center 
\framebox[1.1\width]{\Large AABCCCDFG} $\Longrightarrow$
\scriptsize
\begin{tabular}{c c}
\hline
Difference &  Probability (CDD) \\
\hline
0 & 0.375 \\
1 & 0.5 \\
2 & 0.125 \\
\vdots  & 0 \\
\hline
\end{tabular}
\caption{Consecutive Differences Distribution (CDD) features
extracted from the file fragment ``AABCCCDFG''. There are three
consecutive-pairs of bytes with difference 0, four with difference 1
and one with difference 2. These distributions are normalized to
produce the shown probabilities. The normalization factor is the length of the string minus one (8 in this example).} \label{fileRec:fig:example_cdd}
\end{figure}


%\begin{figure}[h]
%	\centering
%	\subfigure[Byte Frequency Distribution (BFD) features extracted from
%	the file fragment ``AABCCCDR''.] {\centering \framebox[1.1\width]{\Large AABCCCDR} $\Longrightarrow$
%		\scriptsize
%		\begin{tabular}{c c}
%			\hline
%			Byte &  Probability (BFD) \\
%			\hline
%			A & 0.25 \\
%			B & 0.125 \\
%			C & 0.375 \\
%			D & 0.125 \\
%			R & 0.125 \\
%			\vdots  & 0 \\
%			\hline \\
%		\end{tabular}
%		\label{fileRec:fig:example_bfd}}
%\par\bigskip\bigskip
%	\subfigure[Consecutive Differences Distribution (CDD) features
%	extracted from the file fragment ``AABCCCDFG''. There are three
%	consecutive-pairs of bytes with difference 0, four with difference 1
%	and one with difference 2. These distributions are normalized to
%	produce the shown probabilities. The normalization factor is the length of the string minus one (8 in this example).]{\centering \framebox[1.1\width]{\Large AABCCCDFG} $\Longrightarrow$
%		\scriptsize
%		\begin{tabular}{c c}
%			\hline
%			Difference &  Probability (CDD) \\
%			\hline
%			0 & 0.375 \\
%			1 & 0.5 \\
%			2 & 0.125 \\
%			\vdots  & 0 \\
%			\hline \\
%		\end{tabular}
%		\label{fileRec:fig:example_cdd}
%		}	
%\end{figure}

This scenario can be useful when the entire tested file is available for inspection.
% Typical example is when a
%dump of memory is analyzed or hard drive is scanned with anti virus.
The training was done by the application of
Algorithms~\ref{fileRec:alg:finding_k} and~\ref{fileRec:alg:lu_learning}  to the training data. The $K_{range}$ parameter to Algorithm~\ref{fileRec:alg:finding_k} was determined by the numerical rank of the training matrix. The possible dictionary sizes need to be close to this rank in order to represent well their datasets.
The dictionary sizes were 60 atoms per dictionary. 
The set of dictionaries $D = \{D_{PDF},D_{DOC},D_{EXE},D_{GIF},D_{JPG},D_{HTM}\}$
is the output of Algorithm~\ref{fileRec:alg:lu_learning}, which is later used for classification of test files. 
Each test file was analyzed using Algorithm~\ref{fileRec:alg:lu_classify_entire} and
classified to one of the six classes. 
The classification results are presented as a confusion matrix in
Table~\ref{fileRec:tbl:conf_train_entire_test_entire_deriv}. Each column
corresponds to an actual file type and the rows correspond to the
classified file type by Algorithm~\ref{fileRec:alg:lu_classify_entire}. A
perfect classification produces a table with score 100 on the diagonal
and zero elsewhere. Our results are similar to those achieved
in~\cite{amirani2013feature} (Table~\rom{2}) that use different
methods. However, we did not have the dataset that
\cite{amirani2013feature} used and there is no way to perform a fair
comparison.

\begin{algorithm}[t]
%\SetAlgoLined
\caption{File Content Dictionary Classification}
\label{fileRec:alg:lu_classify_entire}
\textbf{Input:} $x$ input file; $D = \{D_{PDF},D_{DOC},D_{EXE},D_{GIF},D_{JPG},D_{HTM}\}$ set of dictionaries.\\
\textbf{Output:} $t_x$ file type predicted for $x$.

\begin{algorithmic}[1]
\STATE    \For {$t\in\{PDF,DOC,EXE,GIF,JPG,HTM\}$ }{
        $ERR_t \leftarrow dist(x,D_t)$
    }
\STATE $t_x \leftarrow \arg\min_{t}{\{ERR_t\}}$


\end{algorithmic}
\end{algorithm}



\begin{table}[H]
\centering
\caption{Confusion matrix for Scenario A. 100 files of each
type were classified by Algorithm~\ref{fileRec:alg:lu_classify_entire}.}
\begin{tabular}{l|l|c|c|c|c|c|c|c|c}
\multicolumn{3}{c}{}&\multicolumn{3}{c}{Correct File Type}\\
\cline{2-8}
&&PDF&DOC&EXE&GIF&JPG&HTM\\
%\cline{2-8} \multirow{5}{*}{Classified File Type} \
\cline{2-8} \multirow{5}{*}{\parbox{1.1cm}{\raggedleft Classified\\ File Type}} \
& PDF & {\bf 98} & 0 & 1 & 1 & 0 & 0\\
\cline{2-8}
& DOC & 0 & {\bf 97} & 1 & 0 & 0 & 0\\
\cline{2-8}
& EXE & 0 & 3 & {\bf 98} & 2 & 1 & 0\\
\cline{2-8}
& GIF & 0 & 0 & 0 & {\bf 97} & 1 & 0\\
\cline{2-8}
& JPG & 2 & 0 & 0 & 0 & {\bf 98} & 0\\
\cline{2-8}
& HTM & 0 & 0 & 0 & 0 & 0 & {\bf 100}\\
\cline{2-8}
\end{tabular}
\label{fileRec:tbl:conf_train_entire_test_entire_deriv}
\end{table}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Scenario B: Fragments of a File}
\label{fileRec:subsec:second_scen}
In this scenario we describe a situation in which the entire file
is unavailable for the analysis but only some fragments that were taken from
random locations are available. The goal is to classify the file
type based on this partial information. This serves a real
application such as a firewall that examines  packets transmitted
through a network or a file being downloaded from a network server.
This scenario contains three experiments where different features were used in each. 
The training phase, which is common to all three
experiments, includes extracted features from a 10 kilobytes fragments that belong to the training data. 
These features serve as an input to Algorithm~\ref{fileRec:alg:lu_learning}, 
which produces the dictionaries for the classification phase. 
The second parameter in Algorithm~\ref{fileRec:alg:lu_learning} is a set of dictionary sizes, 
which were determined by Algorithm~\ref{fileRec:alg:finding_k}. 
We use the first set of features in this scenario (described hereafter) to demonstrate more deeply how Algorithm~\ref{fileRec:alg:finding_k} works. 
The sizes of six dictionaries need to be determined based on the agreement between the pairwise error matrices. 
Fig.~\ref{fileRec:fig:classification_errors} shows the matrices $ERROR_{PDF\text{-}JPG}$ and $ERROR_{PDF\text{-}EXE}$. 

%It can be seen in Fig.~\ref{fileRec:fig:errors_pdf_jpg} that the PDF and JPG types are very close to each other because for many dictionary sizes $k$ they have overlapped signals. 

Fig.~\ref{fileRec:fig:errors_pdf_jpg} describes the number of classification-errors for the PDF and JPG types, as a function of the respective dictionary sizes. 
It can be observed that there is a large number of errors for many size pairs, suggesting that the PDF and JPG dictionaries exhibit a high measure of similarity. 
This property makes the distinction between these two types a hard task. A closer look on Fig.~\ref{fileRec:fig:errors_pdf_jpg} 
enables us to find the optimal sizes for those dictionaries, by making the following observations.
Only a few values in the cells above the main diagonal provide good results for this pair. 
Additionally, JPG dictionary should have 10 atoms more than the PDF dictionary. 
It cab be also learned that both dictionaries sizes should be greater than 50 atoms.

 
The PDF and EXE error values in Fig.~\ref{fileRec:fig:errors_pdf_exe} indicate that these dictionaries are well separated.
There is a large set of dictionary sizes near the diagonal for which the classification error is low. 
The following intuition helps to understand why a large range of low errors will achieve better classification results.
The error matrices are built based on training data $X$ and represent the 
classification error $C_{PDF,JPG,X}+C_{JPG,PDF,X}$ of the algorithm when it applies to this data (See  Eq.~\ref{fileRec:eq:optimize_k} when using 2 sets).
The best $k$ values from the $ERROR$ matrix fit the training data, in the sense that a PDF training signal will be represented more accurately by a 
PDF dictionary of size $k_{pdf}$ than by a JPG dictionary of size $k_{jpg}$. 
However, this is not necessarily the case for a PDF {\it test} signal, which may need a larger PDF dictionary or smaller JPG dictionary in order to be classified correctly. 
This might happen because many PDF-dictionary atoms are irrelevant for reconstructing this signal while too many JPG-dictionary atoms are relevant for it. 
This means that from this signal's perspective, the PDF dictionary size is smaller than $k_{pdf}$ and the JPG dictionary is larger than $k_{jpg}$. 
In terms of Fig.~\ref{fileRec:fig:classification_errors}, which shows the classification errors for the two discussed pairs, 
this means moving away from  the diagonal (which has the best dictionary sizes for the training set). In the JPG-PDF case, 
this shift will increase the classification error because all the off-diagonal entries in Fig.~\ref{fileRec:fig:errors_pdf_jpg} have higher errors numbers.
On the other hand, there is a low probability to get a classification error in Fig.~\ref{fileRec:fig:errors_pdf_exe},
because there are many off-diagonal options for dictionary sizes that will generate a low error.
The pair JPG-PDF is more sensitive to noise than the pair EXE-PDF. 
This observation is supported by the confusion matrix of the first experiment, 
as shown in Table~\ref{fileRec:tbl:train_10K_test_sample_10_1500B_deriv}.


\begin{figure}
\centering
\subfigure[Error matrix for the pair PDF-JPG]{
\includegraphics[width=0.55\textwidth,keepaspectratio]{Figures/conf_jpg_pdf_bfd_cdd.eps}
\label{fileRec:fig:errors_pdf_jpg} } \subfigure[Error matrix for the pair PDF-EXE]{
\includegraphics[width=0.55\textwidth,keepaspectratio]{Figures/conf_exe_pdf_bfd_cdd.eps}
\label{fileRec:fig:errors_pdf_exe} } 
\caption{Error matrices produced by Algorithm~\ref{fileRec:alg:finding_k}. 
The matrix is presented in cold to hot colormap to show ranges of low (blue) and high (red) errors.}
\label{fileRec:fig:classification_errors}
\end{figure}


In the first experiment, the dictionary sizes, which were determined by Algorithm~\ref{fileRec:alg:finding_k}, are 
150 atoms per PDF, DOC, EXE, GIF, and HTM dictionaries and 160 atoms per JPG dictionary. 
10 fragments of 1500 bytes each were
sampled randomly from each examined file. BFD and CDD based features were
extracted from each fragment and then normalized by the fragment
size (similarly to the normalization by file size conducted in Scenario A  in Section~\ref{fileRec:subsec:first_scen}). Then, the distance between each fragment and each
of the six dictionaries was calculated. The
mean value of the distances was computed for each dictionary. Eventually, the examined file was
classified to the class that has the minimal mean value. This
procedure is described in Algorithm~\ref{fileRec:alg:lu_classify_by_sample}.
The classification results are presented in
Table~\ref{fileRec:tbl:train_10K_test_sample_10_1500B_deriv}.

\begin{algorithm}[h]
%\SetAlgoLined
 \caption{File fragment classification using dictionary learning}
 \label{fileRec:alg:lu_classify_by_sample}
\textbf{Input:} $X = \{x_1,x_2,\cdots,x_r\}$ input fragments; $D = \{D_{PDF},D_{DOC},D_{EXE},D_{GIF},D_{JPG},D_{HTM}\}$ set of dictionaries.\\
\textbf{Output:} $t_X$ file type predicted to $X$.

\begin{algorithmic}[1]
\STATE    \For {$i\leftarrow 1,\ldots,r$}{
        \For {$t\in\{PDF,DOC,EXE,GIF,JPG,HTM\}$}{
         $ERR_{i,t} \leftarrow dist(x_i,D_t)$
        }
    }

\STATE  \For {$t\in\{PDF,DOC,EXE,GIF,JPG,HTM\}$}{
        $MEAN_t \leftarrow \mean\{ERR_{i,t}\}_{i=1}^{r}$
}
\STATE    $t_X \leftarrow \arg\min_{t}{\{MEAN_t\}}$
\end{algorithmic}
\end{algorithm}

\begin{table}[H]
\centering
\caption{Confusion matrix for Scenario B where BFD+CDD
based features were chosen. 100 files of each type were classified
by Algorithm~\ref{fileRec:alg:lu_classify_by_sample}.}
\begin{tabular}{l|l|c|c|c|c|c|c|c|c}
\multicolumn{3}{c}{}&\multicolumn{3}{c}{\bf Correct File Type}\\
\cline{2-8}
&&PDF&DOC&EXE&GIF&JPG&HTM\\
\cline{2-8} \multirow{5}{*}{\parbox{1.2cm}{\raggedleft {\bf Classified\\ File Type}}} \
& PDF & {\bf 93} & 0 & 2 & 0 & 14 & 0\\
\cline{2-8}
& DOC & 0 & {\bf 96} & 2 & 0 & 0 & 0\\
\cline{2-8}
& EXE & 0 & 4 & {\bf 95} & 0 & 0 & 0\\
\cline{2-8}
& GIF & 0 & 0 & 0 & {\bf 100} & 2 & 0\\
\cline{2-8}
& JPG & 6 & 0 & 0 & 0 & {\bf 82} & 0\\
\cline{2-8}
& HTM & 1 & 0 & 1 & 0 & 2 & {\bf 100}\\
\cline{2-8}
\end{tabular}
\label{fileRec:tbl:train_10K_test_sample_10_1500B_deriv}
\end{table}

The second experiment used a double-byte frequency distribution
(DBFD), which contains 65536 features. 
Figure~\ref{fileRec:fig:example_dbfd} demonstrates the DBFD
feature extraction from a small file fragment.

\begin{figure}[H]
\centering \framebox[1.1\width]{\Large AABCCC} $\Longrightarrow$
\scriptsize
\begin{tabular}{c c}
\hline
Double-Byte &  Probability (DBFD) \\
\hline
AA & 0.2 \\
AB & 0.2 \\
BC & 0.2 \\
CC & 0.4 \\
\vdots  & 0 \\
\hline
\end{tabular}
\caption{Features extracted from the file fragment ``AABCCC'' using Double Byte Frequency Distribution (DBFD). 
The normalization factor is the length of the string minus one.}
\label{fileRec:fig:example_dbfd}
\end{figure}
Similarly to the first experiment, 10 fragments were sampled from
random locations at each examined file. However, this time we used 2000
bytes per fragment since smaller fragment sizes do not capture
sufficient information when DBFD features are used.
%This is due to
%the large number of features and due to the high sparsity of the
%extracted data.
 The feature vectors were normalized by the
fragment's size as before. Algorithm~\ref{fileRec:alg:lu_classify_by_sample}
was applied to classify the type of each examined file. 
The dictionaries sizes in this experiment are 80 atoms per PDF, DOC and JPG and 60 atoms per EXE, GIF and HTM.  
The classification results of this experiment are presented in
Table~\ref{fileRec:tbl:train_10K_test_sample_10_2000B_2gram}. We see that
DBFD based features reveal patterns in the data that were not
revealed by using BFD and CDD based features. In particular, it
captures very well GIF files that BFD and CDD based features fail to capture.

\begin{table}[H]
\centering
\caption{Confusion matrix for Scenario B that is based on
DBFD based features. 100 files of each type were classified by
Algorithm~\ref{fileRec:alg:lu_classify_by_sample}.}
\begin{tabular}{l|l|c|c|c|c|c|c|c|c}
\multicolumn{3}{c}{}&\multicolumn{3}{c}{\bf Correct File Type}\\
\cline{2-8}
&&PDF&DOC&EXE&GIF&JPG&HTM\\
%\cline{2-8} \multirow{5}{*}{Classified File Type} \
\cline{2-8} \multirow{5}{*}{\parbox{1.2cm}{\raggedleft {\bf Classified\\ File Type}}} \
& PDF & {\bf 92} & 0 & 2 & 0 & 5 & 1\\
\cline{2-8}
& DOC & 2 & {\bf 97} & 2 & 0 & 5 & 0\\
\cline{2-8}
& EXE & 3 & 1 & {\bf 88} & 2 & 0 & 0\\
\cline{2-8}
& GIF & 1 & 1 & 5 & {\bf 98} & 0 & 0\\
\cline{2-8}
& JPG & 1 & 1 & 2 & 0 & {\bf 90} & 0\\
\cline{2-8}
& HTM & 1 & 0 & 1 & 0 & 0 & {\bf 99}\\
\cline{2-8}
\end{tabular}
\label{fileRec:tbl:train_10K_test_sample_10_2000B_2gram}
\end{table}

The third experiment defines a Markov-walk (MW) like set of 65536
features extracted from the dataset for each signal. The transition
probability between each pair of bytes is calculated.
Figure~\ref{fileRec:fig:example_mw} demonstrates how to extract MW type
features from a file fragment.
\begin{figure}[H]
\centering \framebox[1.1\width]{\Large AABCCCF} $\Longrightarrow$
\scriptsize
\begin{tabular}{c c}
\hline
Transition &  Probability (MW) \\
\hline
A $\rightarrow$ A & 0.5 \\
A $\rightarrow$ B & 0.5 \\
B $\rightarrow$ C & 1 \\
C $\rightarrow$ C & 0.66 \\
C $\rightarrow$ F & 0.33 \\
\vdots  & 0 \\
\hline
\end{tabular}
\caption{Markov Walk (MW) based features extracted from the file
fragment ``AABCCCF''.} \label{fileRec:fig:example_mw}
\end{figure}
Both MW based features  and DBFD based features are calculated using the double byte frequencies, 
but they capture different information from the data. 
DBFD based features are focused on finding pairs of bytes that are most
prevalent and those who have low chances of appearing in a file. On
the other hand, MW based features represent the probability that a
specific byte will appear in the file given the appearance of a
previous byte. This is well suited to file types such as EXE where
similar addresses and opcodes are used repeatedly. Each memory
address or opcode is comprised of two or more bytes, therefore, it
can be described by the transition probability between these bytes.
Text files also constitute a good example for the applicability of
MW based features because it is well known that natural language can
be described by patterns of transition probabilities between words
or letters. Our study shows that MW based features capture also the
structure of media files like GIF and HTM files. The relatively
unsatisfactory performance on JPG files is because our PDF dictionary
was trained on PDF files that contain pictures. Therefore, it
detected some of the JPG files.
%MW features are a novel contribution
%of this paper to the file type prediction research area, and have
%the potential to be extracted and used on other datasets.
The prediction accuracy is described in
Table~\ref{fileRec:tbl:train_10K_test_sample_10_2000B_mw}. Those results
(97\% avg. accuracy) outperform the results obtained by
the BFD+CDD and DBFD features. It also improve over
all the surveyed methods in~\cite{amirani2013feature}
(Table~\rom{6}), including the algorithm proposed
in~\cite{amirani2013feature}, that has 85.5\% average accuracy. However,
it should be noted that we used 10 fragments for the classification
of each file whereas in~\cite{amirani2013feature} a single fragment is used. 
In Scenario B, the dictionary sizes are 500 atoms per PDF, DOC and EXE files, 600 per GIF files, 800 per JPG files and 220 per HTM files. 
The HTM dictionary is smaller than the other dictionaries due to the fact that the HTM training set contains only 230 samples, 
and the LU dictionary size is bounded by the dimensions of the training matrix (see Algorithm~\ref{fileRec:alg:randomized_lu}).


\begin{table}[H]
\centering
\caption{Confusion matrix for Scenario B using MW based
features. 100 files of each type were classified by
Algorithm~\ref{fileRec:alg:lu_classify_by_sample}.}
\begin{tabular}{l|l|c|c|c|c|c|c|c|c}
\multicolumn{3}{c}{}&\multicolumn{3}{c}{\bf Correct File Type}\\
\cline{3-8}
\multicolumn{2}{c|}{}&PDF&DOC&EXE&GIF&JPG&HTM\\
%\cline{2-8} \multirow{5}{*}{Classified File Type} \
\cline{2-8} \multirow{5}{*}{\parbox{1.2cm}{\raggedleft {\bf Classified\\ File Type}}} \
& PDF & {\bf 93} & 1 & 0 & 0 & 9 & 0\\
\cline{2-8}
& DOC & 0 & {\bf 98} & 0 & 0 & 0 & 0\\
\cline{2-8}
& EXE & 2 & 0 & {\bf 98} & 1 & 0 & 0\\
\cline{2-8}
& GIF & 3 & 1 & 1 & {\bf 99} & 0 & 0\\
\cline{2-8}
& JPG & 1 & 0 & 0 & 0 & {\bf 91} & 0\\
\cline{2-8}
& HTM & 1 & 0 & 1 & 0 & 0 & {\bf 100}\\
\cline{2-8}
\end{tabular}
\label{fileRec:tbl:train_10K_test_sample_10_2000B_mw}
\end{table}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Scenario C: Detecting Execution Code in PDF Files}
\label{fileRec:subsec:execution_code_in_pdf}

PDF is a common file format that can
contain different media elements such as text, fonts, images,
vector graphics and more. This format is widely used in the Web due
to the fact that it is self contained and platform independent.
While PDF format is considered to be safe, it can contain any file
format including executables such as EXE files and various script files.
Detecting malicious PDF files can be challenging as it requires a
deep inspection into every file fragment that can potentially hide
executable code segments. The embedded code is not automatically
executed when the PDF is being viewed using a PDF reader since it
first requires to exploit a vulnerability in the viewer code or in
the PDF format. Still, detecting such a potential threat can lead to
a preventive action by the inspecting system. 
%Still, detecting the presence of executable code
%segments in a PDF file can lead to taking preventive action by the
%firewall or by the anti-virus software by blocking for example the
%file or alerting the user.

To evaluate how effective our method can be in detecting executable
code embedded in PDF files, we generated several PDF files which
contain text, images and executable code. We used four datasets of
PDF files as our training data: \\
%\begin{description}
%\item[$X_{PDF}$:]     \hspace{0.95cm} 100 regular PDF files containing mostly text.
%\item[$X_{GIFinPDF}$:] \hspace{0.12cm} 100 PDF files containing GIF images.
%\item[$X_{JPGinPDF}$:] \hspace{0.08cm} 100 PDF files containing JPG images.
%\item[$X_{EXEinPDF}$:] \hspace{0.00cm} 100 PDF files containing EXE files.
%\end{description}

\begin{tabular}{p{1.75cm}l}
	$X_{PDF}$: &100 PDF files containing mostly text. \\
	$X_{GIFinPDF}$: &100 PDF files containing GIF images. \\
	$X_{JPGinPDF}$: &100 PDF files containing JPG images. \\
	$X_{EXEinPDF}$: &100 PDF files containing EXE files.
\end{tabular} \\

All the GIF, JPG and EXE files were taken from previous
experiments and were embedded into the PDF files. We generated 4
dictionaries for each dataset using Algorithm~\ref{fileRec:alg:lu_learning}.
The input for the algorithm was
$$X = \{X_{PDF}, X_{GIFinPDF}, X_{JPGinPDF} ,X_{EXEinPDF}\}.$$
We then created a test dataset which consisted of: 100 regular PDF
files and 10 PDF files that contain executable code.
Algorithm~\ref{fileRec:alg:lu_classify_by_sample} classified the 110 files.
The input fragments $X$ were the PDF file fragments. The input set
of dictionaries 
$$D = \{D_{PDF}, D_{GIFinPDF}, D_{JPGinPDF}, D_{EXEinPDF}\}$$
were the output from Algorithm~\ref{fileRec:alg:lu_learning}.
A file is classified as malicious (contains an executable code) if
we find more than $T_{EXE}$ fragments of type EXE  inside, otherwise it is
classified as a safe PDF file. We used $T_{EXE}=10$ as our threshold
since it minimized the total number of miss-classifications. The
training step was applied to 10 kilobytes fragments and the
classification step was applied to five kilobytes  fragments. We used the
MW based features (65,536 extracted features).
By using Algorithm~\ref{fileRec:alg:lu_classify_by_sample}, we managed to
detect all the 10 malicious PDF files with $8\%$ of false alarm
rate (8 PDF files that were classified as malicious PDF files).
The results are summarized in Table~\ref{fileRec:tbl:malicious_pdf}.

\begin{table}[H]
\centering
\caption{Confusion matrix for malicious PDF detection experiment.
110 files were classified by
Algorithm~\ref{fileRec:alg:lu_classify_by_sample}.}
\begin{tabular}{l|l|c|c|c|c}
\multicolumn{1}{c}{}&\multicolumn{3}{c}{{\bf Correct File Type}}\\
%\multicolumn{1}{c}{}\\
\cline{2-4}
&&PDF&Malicious PDF\\
%\cline{2-4} \multirow{2}{*}{Classified File Type} \
\cline{2-4} \multirow{2}{*}{\parbox{1.2cm}{\raggedleft {\bf Classified\\ File Type}}} \
& Safe PDF & {\bf 92} & 0 \\
\cline{2-4}
& Malicious PDF & 8 & {\bf 10} \\
\cline{2-4}
\end{tabular}
\label{fileRec:tbl:malicious_pdf}
\end{table}

Other file formats, which contain embedded data (DOC files for
example), can be classified in the same way.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Time Measurements}
\label{fileRec:subsec:timing} 
Computer security software face frequent situations that were described in
sections~\ref{fileRec:subsec:first_scen}--\ref{fileRec:subsec:execution_code_in_pdf}. 
Therefore, any solution to a file type classification must provide a
quick response to queries. We measured the time required for both
the training phase and the classification phase of our method that
classifies a file or a fragment of a file. Since the training phase
operates offline it does not need to be fast. On the other hand,
classification query should be fast for real-time considerations and
for high-volume applications. Tables~\ref{fileRec:tbl:timing_file} and~\ref{fileRec:tbl:timing_fragment} describe the
execution time in Scenarios A (Section~\ref{fileRec:subsec:first_scen}) and B (Section~\ref{fileRec:subsec:second_scen}), respectively. 
The times are divided into a preprocessing
step and into the actual analysis step. The preprocessing includes
feature extraction from files (data preparation) and loading this
data into Matlab. The feature extraction was done in Python and the
output files were loaded to Matlab. Obviously, this is not an
optimal configuration as it involves intensive slow disk I/O. We did
not optimize these steps. We note that the computation time of the dictionary size is not included in the table, 
because this is a meta-parameter to Algorithm~\ref{fileRec:alg:lu_learning} which can be computed in different ways, based on the application. 
The analysis time refers to the time needed by Algorithm~\ref{fileRec:alg:lu_learning} to build six dictionaries (left column in each table) and to classify a single file to one of the six classes (right column). The classification was performed by Algorithm~\ref{fileRec:alg:lu_classify_entire} in Scenario A (Table~\ref{fileRec:tbl:timing_file}), and by Algorithm~\ref{fileRec:alg:lu_classify_by_sample} in Scenario B (Table~\ref{fileRec:tbl:timing_fragment}). All training and classification times are normalized by the data size, which allows evaluation of the algorithm performance regardless of actual file sizes (which vary largely). Classification time of Scenario B is not normalized because Algorithm~\ref{fileRec:alg:lu_classify_by_sample} is not dependent on the input file size (it samples the same amount of data from each file, ignoring its size). Our classification process is fast. The preprocessing step can be
further optimized for real-time applications. All the experiments were
conducted on Windows 64-bit, Intel i7, 2.93 GHz CPU machine with 8
GB of RAM.

%The training is done offline and it does
%not affect significantly the algorithm performance. The
%classification , on the other hand, has to be fast for applications
%that deal with millions of files and high-volume network traffic.


%The running times of the training and
%classification steps of each scenario are presented in
%Tables~\ref{fileRec:tbl:timing_file} and~\ref{fileRec:tbl:timing_fragment}.

\begin{table}[h]
\caption{Running times for Scenario A.} 
\begin{center}
\begin{tabular}{ c"l  c  c }
    \thickhline
        Features    &  & Training time (sec)   & Classification time (sec) \\
            &          & per 1 MB of data      & per 1 MB of data \\
    \thickhline
         \multirow{3}{*}{BFD+CDD} &&& \\

   &  Preprocessing       & 1.8               & 1.88        \\
   &  Analysis            & {\bf 0.004}       & {\bf 0.0005}    \\
    & Total               & 1.804             & 1.8805        \\
    \thickhline
    \end{tabular}
\label{fileRec:tbl:timing_file}
\end{center}
\end{table}

%	The bold number in
%	the left column refers to the running time of
%	Algorithm~\ref{fileRec:alg:lu_learning}. The corresponding number in the right column refers to the running time of
%	Algorithm~\ref{fileRec:alg:lu_classify_entire}. 
%	The times are normalized by the training data size (left column) and the testing data size (right column). 
%	This normalization allows to analyze the times regardless of the sizes of the files in our experiments, 
%	which are random and vary largely.


\begin{table}[h]
\caption{Running times for Scenario B.} 
\begin{center}
    \begin{tabular}{ c"l  c  l }
    \thickhline
        Features    &  & Training time (sec)   & Classification time \\
            &          & per 1 MB of data      & (sec) \\
    \thickhline
         \multirow{3}{*}{BFD+CDD} &&& \\

    &  Preprocessing              & 1.93              & 0.1 (per 1 MB)  \\
    &  Analysis                   & {\bf 0.008}       & {\bf 0.01} (per file)          \\
    &  Total                      & 1.938             &         \\
    \thickhline
    \multirow{3}{*}{DBFD} &&&\\
    &  Preprocessing              & 13.78              & 1.6 (per 1 MB)   \\
    &  Analysis                   & {\bf 0.54}         & {\bf 0.26} (per file)         \\
    &  Total                      & 14.32              &          \\
    \thickhline
\multirow{3}{*}{MW} &&& \\
    &  Preprocessing              & 18.42              & 2.41 (per 1 MB)    \\
    &  Analysis                   & {\bf 0.65}         & {\bf 0.27} (per file)         \\
    &  Total                      & 19.07              &        \\
    \thickhline
    \end{tabular}
\label{fileRec:tbl:timing_fragment}
\end{center}
\end{table}

%The bold numbers in
%the left column refer to the running time of
%Algorithm~\ref{fileRec:alg:lu_learning} for different feature sets.
%The corresponding numbers in the right column refer to the running time
%of Algorithm~\ref{fileRec:alg:lu_classify_by_sample}. 
%The times in the table are normalized by the training and testing data sizes, as done in Table~\ref{fileRec:tbl:timing_file}. 
%The analysis time of the test files however is per file because Algorithm~\ref{fileRec:alg:lu_classify_by_sample} samples 
%a fixed amount of content from each file regardless of its actual size.}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Conclusion}
\label{fileRec:sec:conclusion}
In this work, we presented a novel algorithm for dictionary construction, which is based on a randomized LU decomposition.
By using the constructed dictionary, the algorithm classifies the content of a file and can deduct its type by examining a few file fragments. 
The algorithm can also detect anomalies in PDF files (or any other rich content formats) which can be malicious.
This approach can be applied to detect suspicious files that can potentially contain malicious payload. Anti-virus systems and
firewalls can therefore analyze and classify PDF files using the described method and block suspicious files.
The usage of dictionary construction and classification in our algorithm is different from other classical methods for file content detection, 
which use statistical methods and pattern matching in the file header for classification via deep packet inspection.
The fast dictionary construction allows to rebuild the dictionary from scratch when it is out-of-date which is important 
when building evolving systems that classify continuously changing data.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Acknowledgment}
\noindent This research was partially supported by the Israel Science
Foundation (Grant No. 1041/10), by the
Israeli Ministry of Science \& Technology (Grants No. 3-9096, 3-10898), by
US - Israel Binational Science Foundation (BSF 2012282)
and by a Fellowship from Jyv\"{a}skyl\"{a} University.

%\bibliographystyle{plain}
%\bibliographystyle{unsrt}
\bibliographystyle{siam}
\bibliography{RandLuApps_paper}
\end{document}

RandLuApps_paper.bbl
\begin{thebibliography}{10}

\bibitem{aharon:ksvd}
{\sc M.~Aharon, M.~Elad, and A.~Bruckstein}, {\em {K-SVD}: An algorithm for
  designing overcomplete dictionaries for sparse representation}, IEEE Trans.
  on Signal Processing, 54 (2006), pp.~4311--4322.

\bibitem{ahmed2009improving}
{\sc I.~Ahmed, K.-s. Lhee, H.~Shin, and M.~Hong}, {\em On improving the
  accuracy and performance of content-based file type identification}, in
  Information Security and Privacy, Springer, 2009, pp.~44--59.

\bibitem{ahmed2010fast}
\leavevmode\vrule height 2pt depth -1.6pt width 23pt, {\em Fast file-type
  identification}, in Proceedings of the 2010 ACM Symposium on Applied
  Computing, ACM, 2010, pp.~1601--1602.

\bibitem{amirani2013feature}
{\sc M.~C. Amirani, M.~Toorani, and S.~Mihandoost}, {\em Feature-based type
  identification of file fragments}, Security and Communication Networks, 6
  (2013), pp.~115--128.

\bibitem{calhoun2008predicting}
{\sc W.~C. Calhoun and D.~Coles}, {\em Predicting the types of file fragments},
  Digital Investigation, 5 (2008), pp.~S14--S20.

\bibitem{chen:BasisPursuit}
{\sc S.~S. Chen, D.~L. Donoho, and M.~A. Saunders}, {\em Atomic decomposition
  by basis pursuit}, SIAM journal on scientific computing, 20 (1998),
  pp.~33--61.

\bibitem{erbacher2007identification}
{\sc R.~F. Erbacher and J.~Mulholland}, {\em Identification and localization of
  data types within large-scale file systems}, in Systematic Approaches to
  Digital Forensic Engineering, 2007. SADFE 2007. Second International Workshop
  on, IEEE, 2007, pp.~55--70.

\bibitem{gu1996efficient}
{\sc M.~Gu and S.~C. Eisenstat}, {\em Efficient algorithms for computing a
  strong rank-revealing {QR} factorization}, SIAM Journal on Scientific
  Computing, 17 (1996), pp.~848--869.

\bibitem{jiang2011learning}
{\sc Z.~Jiang, Z.~Lin, and L.~S. Davis}, {\em Learning a discriminative
  dictionary for sparse coding via label consistent k-svd}, in Computer Vision
  and Pattern Recognition (CVPR), 2011 IEEE Conference on, IEEE, 2011,
  pp.~1697--1704.

\bibitem{karresand2006file}
{\sc M.~Karresand and N.~Shahmehri}, {\em File type identification of data
  fragments by their binary structure}, in Information Assurance Workshop, 2006
  IEEE, IEEE, 2006, pp.~140--147.

\bibitem{li2005fileprints}
{\sc W.-J. Li, K.~Wang, S.~J. Stolfo, and B.~Herzog}, {\em Fileprints:
  Identifying file types by n-gram analysis}, in Information Assurance
  Workshop, 2005. IAW'05. Proceedings from the Sixth Annual IEEE SMC, IEEE,
  2005, pp.~64--71.

\bibitem{mcdaniel2003content}
{\sc M.~McDaniel and M.~H. Heydari}, {\em Content based file type detection
  algorithms}, in System Sciences, 2003. Proceedings of the 36th Annual Hawaii
  International Conference on, IEEE, 2003, pp.~10--pp.

\bibitem{natarajan1995sparse}
{\sc B.~K. Natarajan}, {\em Sparse approximate solutions to linear systems},
  SIAM journal on computing, 24 (1995), pp.~227--234.

\bibitem{pan2000existence}
{\sc C.-T. Pan}, {\em On the existence and computation of rank-revealing {LU}
  factorizations}, Linear Algebra and its Applications, 316 (2000),
  pp.~199--222.

\bibitem{pham2008joint}
{\sc D.-S. Pham and S.~Venkatesh}, {\em Joint learning and dictionary
  construction for pattern recognition}, in Computer Vision and Pattern
  Recognition, 2008. CVPR 2008. IEEE Conference on, IEEE, 2008, pp.~1--8.

\bibitem{shabat2013randomized}
{\sc G.~Shabat, Y.~Shmueli, and A.~Averbuch}, {\em Randomized {LU}
  decomposition}, arXiv preprint arXiv:1310.7202,  (2013).

\bibitem{tropp:GIG}
{\sc J.~Tropp}, {\em Greed is good: algorithmic results for sparse
  approximation}, Information Theory, IEEE Transactions on, 50 (2004),
  pp.~2231--2242.

\bibitem{veenman2007statistical}
{\sc C.~J. Veenman}, {\em Statistical disk cluster classification for file
  carving}, in Information Assurance and Security, 2007. IAS 2007. Third
  International Symposium on, IEEE, 2007, pp.~393--398.

\bibitem{wright2009robust}
{\sc J.~Wright, A.~Y. Yang, A.~Ganesh, S.~S. Sastry, and Y.~Ma}, {\em Robust
  face recognition via sparse representation}, Pattern Analysis and Machine
  Intelligence, IEEE Transactions on, 31 (2009), pp.~210--227.

\bibitem{yang2007feature}
{\sc A.~Y. Yang, J.~Wright, Y.~Ma, and S.~S. Sastry}, {\em Feature selection in
  face recognition: A sparse representation perspective}, submitted to IEEE
  Transactions Pattern Analysis and Machine Intelligence,  (2007).

\bibitem{yang2011fisher}
{\sc M.~Yang, D.~Zhang, and X.~Feng}, {\em Fisher discrimination dictionary
  learning for sparse representation}, in Computer Vision (ICCV), 2011 IEEE
  International Conference on, IEEE, 2011, pp.~543--550.

\bibitem{zhang2010discriminative}
{\sc Q.~Zhang and B.~Li}, {\em Discriminative k-svd for dictionary learning in
  face recognition}, in Computer Vision and Pattern Recognition (CVPR), 2010
  IEEE Conference on, IEEE, 2010, pp.~2691--2698.

\end{thebibliography}
