# Reliable Detection of Compressed and Encrypted Data

Fabio De Gaspari, Dorjan Hitaj, Giulio Pagnotta, Lorenzo De Carli, Luigi V.
Mancini F. De Gaspari, D. Hitaj, G. Pagnotta and L.V. Mancini are with
Dipartimento di Informatica, Sapienza Università di Roma, 00198 Rome, Italy
(Email: {degaspari, hitaj.d, pagnotta, mancini}@di.uniroma1.it).L. De Carli is
with the Department of Computer Science, Worcester Polytechnic Institute,
Worcester, MA 01609, USA (email: ldecarli@wpi.edu).

###### Abstract

Several cybersecurity domains, such as ransomware detection, forensics and
data analysis, require methods to reliably identify encrypted data fragments.
Typically, current approaches employ statistics derived from byte-level
distribution, such as entropy estimation, to identify encrypted fragments.
However, modern content types use compression techniques which alter data
distribution pushing it closer to the uniform distribution. The result is that
current approaches exhibit unreliable encryption detection performance when
compressed data appears in the dataset. Furthermore, proposed approaches are
typically evaluated over few data types and fragment sizes, making it hard to
assess their practical applicability.

This paper compares existing statistical tests on a large, standardized
dataset and shows that current approaches consistently fail to distinguish
encrypted and compressed data on both small and large fragment sizes. We
address these shortcomings and design EnCoD, a learning-based classifier which
can reliably distinguish compressed and encrypted data. We evaluate EnCoD on a
dataset of 16 different file types and fragment sizes ranging from 512B to
8KB. Our results highlight that EnCoD outperforms current approaches by a wide
margin, with accuracy ranging from $\sim 82\%$ for 512B fragments up to $\sim
92\%$ for 8KB data fragments. Moreover, EnCoD can pinpoint the exact format of
a given data fragment, rather than performing only binary classification like
previous approaches.

##  I Introduction

Reliable detection of encrypted data fragments is an important primitive with
many applications to security and digital forensics. For instance, ransomware
detection algorithms use estimates of write-operations’ data randomness to
quickly identify evidence of malicious encryption processes [26, 34, 17, 27].
When performing digital forensic analysis of hard drives and phones, it is
oftentimes important to identify encrypted archives [16]. Finally, encryption
detection is widely used in network protocol analysis [18, 21].

A popular approach to address this problem is to estimate the Shannon entropy
of the sequence of interest using the Maximum Likelihood Estimator (MLE):
$\hat{H}_{MLE}$. This approach leverages the observation that the distribution
of byte values in an encrypted stream closely follows a uniform distribution;
therefore, high entropy is used as a proxy for randomness. This estimator has
the advantage of being simple and computationally efficient. As non-encrypted
digital data is assumed to have low byte-level entropy, the estimator is
expected to easily differentiate non-encrypted and encrypted content.

While this approach remains widely used (e.g., [26, 34, 17, 27]), a number of
works have highlighted its limitations. Modern applications tend to compress
data prior to both storage and transmission. Popular examples include the zip
compressed file format, and HTTP compression [22] (both using the DEFLATE
algorithm). As compression removes recurring patterns in data, compressed
streams tend to exhibit high Shannon entropy. As a result, compressed data
exhibit values of $\hat{H}_{MLE}$ that are close and oftentimes overlapping
with those obtained by encryption. In principle, compressed content can be
identified by using appropriate parsers. However, many security-related
applications, such as ransomware detection, traffic analysis and digital
forensics, generally do not have access to whole-file information, but rather
work at the level of fragments of data. In these settings, the metadata that
is required by parsers is not present or is incomplete [36]. Given this issue,
a number of works have been looking at alternative tests to distinguish
between encrypted and compressed content [31, 44, 33, 35, 24, 12, 14]. While
these works have the potential to be useful, there has been limited evaluation
of their performance on a standardized dataset. Consequently, there is no
clear understanding of how these approaches: (i) fare on a variety of
compressed file formats and sizes, and (ii) compare to each other. The
potential negative implications are significant: the use of ineffective
techniques for identifying encrypted content can hinder the effectiveness of
ransomware detectors [20], and significantly limit the capability of forensic
tools.

Our work compares state-of-the-art approaches on a large dataset of different
data types and fragment sizes. We find that, while more useful than entropy
estimates, current approaches fail to achieve consistently high accuracy. To
address this, we propose EnCoD (Encryption/Compression Distinguisher), a novel
neural network-based approach. Our evaluation shows that EnCoD outperforms
existing approaches for most considered file types, over all considered
fragment sizes.

EnCoD can distinguish between compressed and encrypted data fragments as small
as 512B with $86\%$accuracy. The accuracy increases to up to $94\%$ when
distinguishing between encrypted and purely compressed data (i.e.,zip, gzip),
and up to $100\%$ in the case of compressed application data fragments (e.g.,
pdf, jpeg, mp3) when the fragment size is 8KB. Furthermore, we investigate the
applicability of robust feature extraction techniques such as autoencoders to
our architecture, in an effort to understand whether feature vector pre-
processing can lead to increased performance compared to a plain neural
network (NN) architecture in this domain.

This paper revises and extends our previous conference paper [19], by
considering a larger and more diverse dataset of file fragments and evaluating
the effectiveness of data pre-processing on accuracy. Overall, we make the
following contributions:

  * •

We review and categorize existing literature on the topic of distinguishing
compressed and encrypted data fragments.

  * •

We build and make available to the community a large, standardized dataset of
data fragments of different sizes from 16 different data formats.111The full
dataset is available at
https://drive.google.com/file/d/1IDNv3U1hRILXblwT9fI3G-D8hJquiequ

  * •

We systematically evaluate and compare state-of-the-art approaches on our
dataset for different fragment formats and sizes.

  * •

We propose a new neural-network based approach and show that it outperforms
current state-of-the-art tests in distinguishing encrypted from compressed
content for most considered formats, over all considered fragment sizes.

  * •

We propose a new multi-class classifier that can label a fragment with high
accuracy as encrypted data, general-purpose compressed data
(zip/gzip/rar/bz2), or one of multiple application-specific compressed data
(png, jpeg, pdf, mp3, office, video).

  * •

We investigate the effectiveness of data pre-processing techniques such as
autoencoders for our architecture, and show that plain neural network models
outperform these approaches in the considered domain.

  * •

We thoroughly discuss the implications of our findings and effectiveness of
the evaluated approaches in distinguishing compressed and encrypted data.

The rest of this paper is structured as follows: Section II provides
background on entropy estimation and its applications. Section III reviews
existing approaches to the problem. Section IV presents and evaluates a novel
approach to the problem, based on deep learning. Section V evaluates the
performance of the considered approaches, discussing their strengths and
limitations. Section VI discusses the implications of our findings. Section
VII discusses related work and Section VIII concludes the paper.

##  II Background

Determining the format of a particular data object (e.g. a file in permanent
storage, or an HTTP object) is an extremely common operation. Under normal
circumstances, it can be accomplished by looking at content metadata or by
parsing the object. Things get more complicated, however, when no metadata is
available and the data object is corrupted or partly missing. In this paper,
we focus on detection of encrypted content and, in particular, on
distinguishing between encrypted and compressed data fragments. We begin by
examining relevant applications of encryption detection primitives.

###  II-A Ransomware Detection

Ransomware encrypts user files with the aim of making them unusable for the
user. It then presents a prompt asking the user to pay a ransom in order to
receive the decryption key. Ransomware attacks can cause significant financial
damage to organizations [3, 4, 10].

Mitigating a ransomware infection requires rapid detection and termination of
all ransomware processes. A number of approaches based on behavioral process
analysis have been proposed for this purpose [26, 34, 17, 27]. These
approaches typically rely on a classifier trained on various process-related
features to distinguish benign and ransomware processes. Virtually all
proposed behavioral detectors use entropy of file write operations as one of
the key features, based on the insight that frequently writing encrypted
content is a characteristic behavioral fingerprint of ransomware. Entropy is
typically estimated using $\hat{H}_{MLE}$. In several approaches entropy is
estimated on the content of individual file writes [26, 27, 17], therefore the
estimation procedure has only access to partial file fragments.

###  II-B Forensics

Digital forensics oftentimes involves analysis of phone [42] or PC [36]
storage that has been corrupted, or uses an unknown format. Therefore,
forensic techniques attempt to recover data of interest (contacts, pictures,
etc.) by searching for blocks with recognizable structure. These techniques
typically only have access to data fragments, rather than whole files.

Encrypted and compressed data represent a corner case, as they exhibit a
complete lack of structure. Still, detecting such content may be important in
data recovery operations (e.g., if sensitive data is known to have been
encrypted). Distinguishing between compressed and encrypted blocks is
notoriously difficult, and some forensic approaches label data as “compressed
or encrypted”, without attempting to pinpoint which one of the two it is [16].

###  II-C Network Traffic Analysis

Network traffic analysis examines flows in/out of a network to identify
security issues. Regulations (e.g. HIPAA in the U.S.) and best practices
expect sensitive data to be encrypted in transit; therefore, entropy-based
analyzers have been proposed to ensure that all traffic leaving a monitored
network is encrypted [21]. Another application is reverse-engineering of
network protocols used by malware. It has been observed [18] that malware
protocols may mix encrypted and non-encrypted content within the same message.
Encryption detection primitives can be applied to break messages into
encrypted and non-encrypted fields.

In both cases above, encryption detectors have partial visibility on the data
stream and can only access fragments of data (e.g., an encrypted stream broken
into individual packets), rather than whole data objects.

Figure 1: Entropy ranges for common formats (2048B blocks)

###  II-D Challenges

In the three domains above, the use of Shannon entropy has been proposed in
order to identify encrypted content. Entropy is used to measure the
information content of a byte sequence; highly structured data exhibit low
entropy, while unstructured data—such as a randomly distributed sequence—have
high entropy. Therefore, an entropy estimate can be used as a proxy for how
close a sequence of bytes is to being randomly distributed. Most encryption
algorithms output ciphertexts whose byte-value distributions tend to follow a
uniform distribution. As a result, an encrypted bytestream will almost
invariably exhibit high entropy.

One of the most common approaches to entropy estimation is the Maximum
Likelihood Estimator $\hat{H}_{MLE}=-\sum_{i=0}^{255}{f_{i}log_{2}(f_{i})}$,
where $f_{i}$ is the frequency of byte value $i$ in the sequence. The entropy
range is $[0-8]$. The frequency $f_{i}$ of byte value $i$, which is
measurable, is used in place of the probability $P(i)$ of that value
occurring, which is unknown. This approach is commonly used in some of the
applications above (e.g., [26, 21]), due to its simplicity and efficiency.

This reasoning assumes that, while encrypted data has high entropy, non-
encrypted data does not. This appears reasonable, as most relevant data types
(e.g., text, images, audio) are information-rich and highly structured.
However, this assumption does not hold true in modern computing. Modern CPUs
can efficiently decompress data for processing, and compress it back for
storage or transmission; this is oftentimes performed in real time and
transparent to the user. As a result, most formats tend to apply compression
[2, 41]. Informally, a good compression algorithm works by identifying and
removing recognizable structures from the data stream; as a result, compressed
data tend to exhibit high entropy. In practice, this fact compromises the
ability of entropy-based detectors to distinguish encrypted and non-encrypted,
compressed content.

Entropy estimates for common data formats. In order to substantiate the claim
above, we computed entropy estimates using a dataset consisting of 10,000 file
fragments. The dataset covers various popular file formats and
AES-256-encrypted data. We considered multiple fragment sizes, from 512B to
8KB (details in Section IV). Figure 1 summarizes the distribution of estimated
entropy values for eight different formats with block size 2048 (some ranges
truncated for clarity). Results for other block sizes were qualitatively
similar. As illustrated in Figure 1, both general-purpose (e.g., zip, rar) and
domain-specific (e.g., jpeg, mp3) compression algorithms result in data which
exhibits entropy whose ranges are overlapping with that of encrypted content
(enc). The only format that can be unambiguously distinguished is png. Even
so, png still overlaps with various other formats. Interestingly, utilities
that create and modify data in zip, gzip, office and png format internally all
use the DEFLATE algorithm for compression: the differences in entropy are
likely due to differences in file structure and algorithm implementation.

Due to the limits of entropy estimation, the attention of the community has
been increasingly focusing on alternative measures that can more precisely
estimate whether data follow a random distribution. However, no comprehensive
review of such approaches exists. In the next section, we review state-of-art
approaches, while we evaluate and compare them in Section V.

##  III Review of Existing Techniques

This section reviews three state-of-the-art approaches to distinguishing
encrypted and compressed content: the NIST suite, $\chi^{2}$ and HEDGE [12].
Strictly speaking, these approaches test the randomness of a string of bytes,
and make no attempt to determine its type. However, due to their high
precision they can be used to distinguish true pseudorandom (encrypted)
sequences and compressed ones which, while approximating a randomly generated
stream, maintain structure.

The NIST suite and $\chi^{2}$ are standard statistical tests for identifying
randomly-distributed data. HEDGE is a recently proposed statistical approach
which shows promising results. HEDGE is a combination of a subset of the NIST
tests and two forms of $\chi^{2}$ tests. Note that, despite the inclusion of
HEDGE, we decided to also report separate results for NIST and $\chi^{2}$ due
to the fact that those are designed to be, and oftentimes are, used as
standalone tests.

###  III-A NIST SP800-22

The NIST SP800-22 specification [39] describes a suite of tests whose intended
use is to evaluate the quality of random number generators. The suite consists
of 15 distinct tests, which analyze various structural aspects of a byte
sequence. These tests are commonly employed as a benchmark for distinguishing
compressed and encrypted content (e.g., [12, 14]). Each test analyzes a
particular property of the sequence, and subsequently applies a test-specific
decision rule to determine whether the result of the analysis suggests
randomness or not. When using the NIST suite for discriminating random and
non-random sequences, an important question concerns aggregation of the
results of individual tests. Analysis of the tests [39] suggests that they are
largely independent. Given this observation, and the intrinsic complexity of a
priori defining a ranking between the tests, we use a majority voting
approach. In other words, we consider a fragment to be random (and therefore
encrypted) when the majority of tests considers it so. Since some of the tests
require a block length much bigger than the ones we use for our smaller
fragment sizes, we did not consider in the voting the tests that cannot be
executed.

###  III-B $\chi^{2}$ Test

The $\chi^{2}$ test is a simple statistical test to measure goodness of fit.
It has been widely applied to distinguish compressed and encrypted content
[31, 35, 12]. Given a set of samples, it measures how well the distribution of
such samples follows a given distribution. Mathematically, the test is defined
as:

$\chi^{2}=\sum\limits_{i=0}^{255}\frac{(N_{i}-E_{i})^{2}}{E_{i}}$

where $N_{i}$ is the actual number of samples assuming value $i$, and $E_{i}$
is the expected number of samples assuming value $i$ according to the known
distribution of interest. Since the distribution being evaluated for goodness
of fit is the discrete uniform distribution, $\forall iE_{i}=L/256$, where $L$
is the particular fragment length being considered. The results of the test
can be interpreted using either a fixed threshold, or a confidence interval
[12].

###  III-C HEDGE

HEDGE [12] simultaneously incorporates three methods to distinguish between
compressed and encrypted fragments: $\chi^{2}$ test with absolute value,
$\chi^{2}$ with confidence interval and a subset of NIST SP800-22 test suite.
Out of the NIST SP800-22 test suite HEDGE incorporates 3 tests: frequency
within block test, cumulative sums test, and approximate entropy test. These
tests were selected due to (i) their ability to operate on short byte
sequences, and (ii) their reliable performance on a large and representative
dataset. In the HEDGE detector the threshold of the number of the above-
mentioned NIST SP800-22 tests failed is set to 0. For the $\chi^{2}$ with
absolute value test, the thresholds are pre-computed for each of the
considered packet sizes, by considering the average and its standard
deviation. For $\chi^{2}$ with confidence interval, the $\chi\%$ interval is
$(\chi\%>99\%||\chi\%<1\%)$. For classifying the content of a packet, HEDGE
applies the three randomness tests to the input data. Data is considered
random only if it passes all tests.

##  IV EnCoD: A Learning-based Approach

Past work and our own evaluation suggest that tests based on byte-value
distribution, such as $\chi^{2}$, can distinguish some encrypted and
compressed content, but have accuracy issues (ref. Section V). Such tests, in
a sense, “collapse” the entire distribution to a single scalar value, losing
information concerning the shape of the distribution. It is therefore natural
to ask if Deep Neural Networks (DNNs) can improve such results. DNNs can
consider the entire discrete distribution (modeled as a feature vector), and
can learn to recognize complex distributions [30].

In order to evaluate the potential of DNNs we designed EnCoD, a set of two
distinct neural network-based approaches for distinguishing encryption and
compression.

###  IV-A Model Architecture #1: Binary Classifiers

Our first model is a binary classifier trained to distinguish a single
specific compressed format from encrypted content. It may be used in cases
where only one compressed format is known to exist in the dataset (e.g.,
detecting writes of encrypted data performed by a potential ransomware on
image files vs legitimate writes of JPEG-compressed data). We explored several
alternative architectures for this application, and we found that the
structure depicted in Figure 2a provides the best performance. The binary-
classifier architecture consists of 4 fully-connected layers with dimensions
as shown in the figure. We initialize the model weights using Glorot uniform
[23]. The activation function is ReLU for the first 3 layers, followed by a
softmax on the output layer. We used a batch size of $64$ for training our
model. Each hyperparameter has been chosen using grid search. We used the same
procedure also for the model described in Section IV-B.

###  IV-B Model Architecture #2: Content-Type Detector

In many applications, a classifier may encounter more than one type of
compressed data. Furthermore, it may be important to determine the specific
type being encountered. To support these use cases, we design a content-type
detector: a multi-class classifier that can determine whether a given fragment
is encrypted, or belongs to one of multiple known compressed formats. We
explored several designs for the neural network, converging to the model
depicted in Figure 2b. Its architecture consists of 5 fully-connected layers
with dimensions as shown in the figure. We initialize model weights using
LeCun normal [29]. Differently from the binary models, this multi-class
classifier seemed prone to the dying neuron problem associated with the ReLU
activation function [40]. We therefore opted for the SelU activation function
[28] for the first 4 layers, followed by a softmax on the output layer. We
used a batch size of $64$ instances for training.

(a) Binary Classifier Architecture (b) Multi-Class Classifier Architecture

Figure 2: Neural Network Architectures

###  IV-C Model Architecture Extension: Autoencoders

In addition to the architectures described in Section IV-A and Section IV-B,
we design a third model architecture that makes use of autoencoders.
Autoencoders (AE) are NN models that are trained to compress an N-dimensional
feature vector into an M-dimensional latent representation, with $M<N$, and
then reconstruct the original input from the latent representation. AE are
composed of two parts: the encoder, which compresses the original feature
vector into the latent representation, and the decoder, which takes the output
of the encoder and reconstructs the input. AE are generally used to extract
robust features from a feature vector and aid classification [37, 38].

In our third architecture, we use the encoder portion of a trained autoencoder
to pre-process samples into a compressed latent representation, which is then
used as input by a fully-connected NN. We design two different set of NN with
two different encoders:

  * •

AE architercure #1: The encoder is composed of 3 fully-connected layers of
size $256-200-128$ respectively, followed by a 3-layer fully-connected NN of
size $128-64-2$.

  * •

AE architecture #2: The encoder is composed of 4 fully-connected layers of
size $256-156-128-64$ respectively, followed by a 3-layer fully-connected NN
of size $64-64-2$.

Both AE are trained for 25 epochs using the Adam optimizer and Mean Squared
error as loss function. We initialize the weights using Glorot uniform for the
NN model and uniform distribution for the AE. The activation function used is
ReLU for all layers except for the output ones, which use softmax in the NN
and sigmoid in the AE. We used a batch size of $64$ for training the NN and
128 for the AE. The hyperparameters were chosen using grid search.

###  IV-D Fragment Dataset

We built a dataset of 400 million encrypted and compressed fragments from 16
different data formats. For the compressed data, we selected a set of formats
covering common, popular content types. To generate the encrypted data
fragments, we used the AES cipher in CBC mode implemented by the PyCryptodome
library [1]. We chose AES because it is the most widely used and well known
symmetric cipher, representative of modern ciphers which result in byte
streams consistently close to random.

In constructing the dataset, we focused on ensuring a diversity of compressed
formats, rather than compression algorithms. While algorithms such as DEFLATE
are used in multiple compression formats, they are generally used with
different parameters and/or embed compressed data in different ways within the
compressed archive. Consequently, compressed archives created with different
formats tend to differ considerably from each other even when using the same
underlying compression algorithm. This observation is empirically confirmed by
our evaluation in Section V. Finally, our dataset does not include data which
is both compressed and encrypted, and we ensured such data is not present in
the dataset. The dataset is comprised of the following data types:

  1. 1.

AES encrypted data (enc). We used the AES implementation provided by the
Cryptodome Python library. AES was configured to use CBC mode with 256-bit
keys, with a random IV generated before encrypting each file.

  2. 2.

zip, gzip, rar, bz2, xz: DEFLATE, rar, Burrows–Wheeler and Lempel–Ziv–Markov
compressed data. These algorithms are among the most used for generic file
compression, with DEFLATE and rar being akin to de-facto standards. DEFLATE is
also widely used for documents (such as in the Microsoft office file formats),
and network applications (e.g., HTTP header compression).

  3. 3.

png and jpeg images: png is used for lossless image compression; it internally
uses DEFLATE, but png files present a structure that is different from that of
zip files. jpeg uses DCT-based lossy compression.

  4. 4.

mp3 audio files: MP3 compressors use a psychoacoustic model to remove
inaudible frequencies from audio data, and compress the resulting data using a
lossy algorithm based on the modified-DCT transform.

  5. 5.

pdf documents: PDF is an office format used for document exchange and form
filling. Internally, PDF files consist of a tree of objects that can be
compressed using a variety of techniques. In practice, most PDF documents
contain a large amount of compressed content, such as embedded images.

  6. 6.

Microsoft office files: Ms office is one of the most used tool suites for
office productivity. Internally, office files use the deflate algorithm for
compression.

  7. 7.

h264, h265, mpeg2, mpeg4 and vp8 video formats: h264 is one of the most widely
used video codecs today, being the recommended codec for Youtube videos. H265
is the successor of h264 and substantially improves compression rate while
maintaining the same video quality. Mpeg4 (Xvid codec) is a format that was
widely used before h264. Vp8 and mpeg-2 are fairly dated video codecs that are
not often used anymore, but there still exists old contents using them.

####  IV-D1 Fragment generation process.

We generate fragments from a dataset of files:

  * •

zip/gzip/rar/bz2/xz/enc: we used various textual documents obtained from a
2020 English Wikipedia dump [8]. We created four copies of each file, each of
which was either compressed using one of zip, gzip, rar, bz2, xz utilities
(with default parameters), or encrypted using AES-256.

  * •

png: we crawled $\sim 116,000$ png images from the web and various
repositories [5].

  * •

jpeg:  we downloaded $\sim 68,000$ images from the Open Images Dataset v5 [7]
and various online sources.

  * •

mp3: we used the FMA medium dataset [6], which contains 25,000 mp3 files.

  * •

pdf: we crawled $\sim 3,000$ randomly-selected papers from arXiv [9].

  * •

office: we sampled 4500 Word, 1700 PowerPoint and 1800 Excel files from a
private hard drive. For privacy reasons, these files are not included in the
provided dataset.

  * •

video files: we downloaded a large, h264-encoded video from Youtube and re-
encoded it to the remaining formats.

We split each file into fragments of 512B, 1KB, 2KB, 4KB, and 8KB. In an
effort to ensure that the dataset remains balanced, we randomly sampled 1M
fragments for each fragment size/data type combination.

###  IV-E Dataset Analysis Methodology

##### Statistical tests (NIST, $\chi^{2}$, HEDGE)

For each fragment size, we randomly selected 10,000 compressed fragments
(evenly distributed across the different compressed data types) and 10,000
encrypted fragments. We then executed the tests directly on these fragments.

#####  EnCoD/Binary Classifiers

We separately trained and evaluated classifiers for each fragment size. The
features that are fed to our models for training/classification are derived
from the histograms of the byte values for the observed fragment size. Each
feature is the value of the probability density function at a given bin,
normalized such that the integral over the range is 1.

We trained the binary classifiers by randomly selecting 3M vectors from the
encrypted class and 3M vectors from the data type that we aim to distinguish.
We partitioned this dataset into 85% training, 5% development and 10% test.
Before fitting the data to the model for training, we applied a MinMax scaler
to scale the dataset from the range $[0,1]$ to the range $[0,2]$ (range
selected via grid search). Scaling helps the ML model to more easily capture
minute differences in the inputs, allowing to better distinguish among the
classes and converge faster.

#####  EnCoD/Content-Type Detector

To train the content-type detectors, for each fragment size we randomly
sampled 6M feature vectors consisting of a mix of the considered file types.
This dataset was partitioned into training, development and test sets in the
same ratios used for the binary classifiers. We also scaled the dataset using
the MinMax scaler with the same parameters used above.

#####  EnCoD/Binary Classifiers with Encoder

We trained one autoencoder per fragment size for all file types. The
autoencoder was trained by randomly sampling 8M feature vectors in total
(500,000 per each of the 16 file types). The feature vectors are created
following the procedure used to train the plain binary classifiers. The
dataset was partitioned into training, development and test sets following the
same ratios used for the binary classifiers. The binary models are trained as
previously described. The only variation is that the latent representation
generated by the trained encoder is used as input by the NN, rather then the
original feature vector derived from a given sample.

##  V Evaluation

This section comprehensively evaluate existing approaches (see Section III)
and our own neural network-based approach, EnCoD. We frame the evaluation in
terms of the following comparisons:

  1. 1.

Binary classification: all formats. In Section V-B, we consider the ability of
different detectors to discriminate encrypted and compressed data, regardless
of the specific compressed format. Results show that our classifier
outperforms NIST, $\chi^{2}$-test and HEDGE for all fragment sizes, with NIST
performance approaching that of EnCoD only for large fragment size.

  2. 2.

Binary classification by format. In Section V-C, we break down the performance
of $\chi^{2}$, NIST and HEDGE by compressed format. We also report the
performance of our per-format binary classifiers (see Section IV-A). The
latter perform comparably or better than other tests on all formats but one.

  3. 3.

Format fingerprinting. In Section V-D, we evaluate the accuracy of our multi-
class classifier in labeling unknown fragments as the correct compressed
format (or as encrypted). Results show that our classifier is able to
distinguish the file type with an overall accuracy of 83% for the 2048 byte
fragment size. It also achieves high precision, especially on png, jpeg, mp3.

  4. 4.

Autoencoder approach. In Section V-E we analyze the performance of the
encoder-based feature extraction approach in the binary classification task.
Our evaluation shows that the plain NN approach outperforms the encoder-based
consistently for all considered formats, with the exception of the pdf file
type.

Figure 3: Performance comparison between our binary-classifier approach, NIST,
$\chi^{2}$ with Threshold and HEDGE. All results are for 2048 Bytes data
fragments.

###  V-A Implementation

We implemented the classifier described in Section IV using the Keras Library
[13] for machine learning. For the NIST tests, we used the official
implementation [15]. In order to aggregate the NIST tests results, we use the
majority voting approach described in Section III-A. In order to label
fragments as compressed or encrypted based on $\chi^{2}$ results, we used the
thresholds suggested in the HEDGE paper [12], as the analysis in HEDGE is
specifically aimed at producing a dataset-independent threshold for general
use. We implemented HEDGE according to the published description [12].
Finally, all experiments were conducted using the dataset described in Section
IV.

Figure 4: Performance comparison (binary classification: all formats)

###  V-B Binary Classification: All Formats

The first part of our evaluation considers the binary classification problem
of determining whether a given high-entropy data fragment is compressed or
encrypted. Given a fragment, the $\chi^{2}$ test, HEDGE, and the NIST test
suite return whether the fragment’s content appears random or not. Therefore,
a binary classifier can be constructed from the above-mentioned three tests by
simply labeling the random content as encrypted. Our binary classifier used
for this evaluation is based on our multi-class classifier. The multi-class
classifier labels each fragment either as encrypted, or as one of the fourteen
supported compressed formats. Since in this experiment we are only interested
in distinguishing encryption and compression, regardless of the type, we
combine all compressed type labels into one. Effectively, we consider
classification in two labels: (1) a macro-label “compressed”, which is
comprised of the labels $\\{$_zip, rar, gzip, bz2, png, jpeg, mp3, pdf, h264,
h265, mpeg2, mpeg4, vp8, office_ $\\}$ and (2) the label “encrypted”. We
analyze file type fingerprinting accuracy separately in Section V-D. It is
worth noting that in experiment shown in Figure 4 we do not consider the xz
file type. This is due to the fact that none of the considered approaches is
able to reliably distinguish xz files from encryption for small fragment
sizes, as we will see in Section V-C.

The results of this evaluation are depicted in Figure 4. As we can see, the
performance of all classifiers tends to improve as fragment size increases.
This behavior is expected, as it is hard to approximate distribution
information from short fragment sizes. However, as the fragment size
increases, differences in distribution become more apparent and the models can
exploit additional information for classification. We further discuss this
phenomenon in Section VI. In the binary classification task, EnCoD outperforms
all the other approaches on all block sizes, with the NIST approach reaching
similar performance for $8K$ fragment size only. The $\chi^{2}$ accuracy
remains consistently low across the range of block sizes, while performance
for HEDGE increases for larger sizes but remains approximately $\sim 10$
percentage points lower than EnCoD’s. These results suggest that the
$\chi^{2}$ test has an intrinsic difficulty in discriminating non-random
content which closely approaches a uniform random distribution.

(a) Performance of our binary classifiers for compressed formats (b)
Performance of our binary classifiers for video formats  (c) Performance of
our binary classifiers for miscellaneous formats

Figure 5: Performance of our binary classification models on different formats
and block size ranging from 512 bytes to 8192 bytes.

###  V-C Binary classification by format

Our second experiment considers the question of whether some compressed
formats are harder than others to distinguish from encrypted content. Such
phenomenon may arise due to (i) differences in effectiveness between
compression algorithms in removing redundancy (and thus structure) from the
uncompressed data; and (ii) presence (or absence) of metadata, or other
structured information interleaved with compressed data.

In order to answer this question, we break down results for the
$\chi^{2}$-test, NIST suite, HEDGE test and EnCoD by format. In this
experiment, for EnCoD we evaluate multiple binary NN classifiers, one per file
type (see Section IV-A). Each type-specific classifier is trained to
distinguish content of a given type from encrypted content (e.g., zip vs
encrypted). Note that, while each of these classifiers is trained specifically
on one format, the other tests ($\chi^{2}$, NIST and HEDGE) work the same
regardless of the format. Despite this limitation, we believe this experiment
to provide an informative analysis, as there are scenarios in which file type
is known a priori, and we are interested only in differentiating between that
type and encryption. For instance, if we consider a storage dedicated only to
pictures backups, we can use a binary classifier (e.g., png/enc) to detect
potential ransomware activity encrypting the pictures.

Figure 3 shows the comparison between the four approaches on 2048-byte blocks.
Overall, neural network-based classifiers tend to fare better than the other
tests, particularly on challenging formats such as zip/gzip, rar and bz2. PDF
is the only format on which the NIST and HEDGE tests outperform the neural
network classifier, while for the office format EnCoD performs slightly worse
but comparably. Interestingly, the $\chi^{2}$ fares slightly better than NIST
on most formats, but its accuracy is significantly worse on formats that are
typically easy to distinguish, such as PNG and MP3. We believe this to be due
to the fact that the NIST tests look at a richer set of properties beyond byte
value distribution, such as a presence of runs and repeated sequences. HEDGE
test outperform $\chi^{2}$ on all file types, while outperforming NIST on most
formats, beside PDF, and have similar performance on PNG, MP3, office and all
video formats but vp8. Intersingly, all approaches fail to consistently
distinguish the xz compressed type (Lempel–Ziv–Markov chain algorithm), with
accuracy at $\sim 50\%$. This behavior is indicative of the great compression
performance of this algorithm, which pushes compressed data extremely close to
a uniform distribution. Due to the inability of any of the considered
approaches to consistently detect xz files, this type is not included in any
of the aggregated results presented in this evaluation.

Finally, Figure 5 presents the performance of all our binary classifiers
across all considered fragment sizes. The results are split in three images
for clarity, all images have the same scale. These results highlight once
again how accuracy increases significantly as block size increases. Indeed,
for larger fragment sizes EnCoD can successfully classify xz compressed files
from encryption reliably, with approximately $70\%$ accuracy on 8k fragment
size, compared to $50\%$ for fragment sizes in the range $[512-2k]$.

###  V-D Format Fingerprinting

Figure 6: Confusion matrix for the content-type classifier

Our multiclass classifier has the ability to (1) distinguish encrypted and
compressed data, and (2) pinpoint the specific format compressed data belong
to. This is a significant improvement over the functionality of existing
tests, that can only distinguish encryption and compression, but cannot tell
the specific format or even generic type of the compressed data. In this
section, we analyze the effectiveness of our multi-class classifier in
fingerprinting the correct type of compressed content. Since for some type
families we have many subtypes (e.g., for video we have 5 types, for cmp we
have 4), while for others only one or two, in this experiment we group some of
the classes in macro labels. Specifically, the office macro label includes all
office file types, the compressed (cmp) macro labels includes zip, gzip, rar,
bz2 and the video macro label includes h264, h265, mpeg2, mpeg4 and vp8.

Figure 7: Performance comparison between plain EnCoD binary classifiers, EnCoD
binary classifier with Encoder64 and EnCoD binary classifier with Encoder128.
Encoder64 uses 64 dimensions for the latent space representation and
Encoder128 uses 128 dimensions. All results are for 2048 Bytes data fragments.
Figure 8: Performance comparison for all formats binary classification between
plain EnCoD, EnCoD with Encoder64 and EnCoD with Encoder128. Encoder64 uses 64
dimensions for the latent space representation and Encoder128 uses 128
dimensions.

Figure 6 shows the confusion matrix for the multi-class classifier. Results
indicate that our classifier is able to pinpoint the type of a given sample
with consistently high precision for most formats, especially png, mp3, jpeg
and encryption. It performs fairly well on the other considered compressed
formats such as cmp (which contains a mixture of zip, rar, gzip and bz2
feature vectors) but with a slightly higher rate of misclassified instances
between enc and cmp. This can be explained by the fact that their
distributions are very close, and intrinsically hard to distinguish. The
worse-performing class is the video macro label, for which a sizable portion
of the samples is classified as encrypted content. However, given the results
of the binary classification presented in Figure 3, this behavior is expected.
The binary classifiers were already struggling in distinguishing the h264 and
h265 types from encryption. Therefore, it is expected that the multiclass
classifier would struggle as well with these formats.

###  V-E Autoencoder Approach

We analyze the effectiveness of the autoencoder approach presented in Section
IV-C compared to the base EnCoD binary approach. As previously discussed, we
have two separate encoder architectures, encoder64 and encoder128, compressing
the feature vector in a 64-dimensional and 128-dimensional latent
representation respectively. This compressed representation is then fed to a
binary NN classifier to distinguish between encrypted data and compressed data
of a specific type.

Figure 7 compares the performance of base EnCoD binary classifiers to the
binary classifiers extended with encoder64 and with encoder128. As we can see,
the base EnCoD models outperform the encoder models in all binary
classification tasks, with the only exception being the pdf type where the
encoders slightly outperform the base model. The difference in accuracy is
especially apparent for the four general purpose compression formats bz2, zip,
rar and gzip, where the best autoencoder (encoder128) results in accuracies 5
to 10 percentage points lower than the base model. Similar results can be
observed in Figure 8, which compares the average accuracy of all binary models
for different data fragment sizes. The performance of the encoder-based
approaches trails that of the base EnCoD models for all fragment sizes, with
accuracy differences in the range of 4 to 10 percentage points.

These results indicate that, while the encoder is able capture meaningful
features for classification in the latent representation, it also loses
critical information that the plain NN can use to achieve better performance.

###  V-F Overhead

In the final part of our evaluation, we analyze the practical applicability of
the three approaches, comparing their runtime in order to understand if they
can be deployed in time-critical applications. For this test, we used a small
dataset comprised of 1000 randomly-selected compressed or encrypted samples.
We ran three approaches (NIST, HEDGE and our binary ML model) on each sample,
taking individual runtime and repeating the experiment 1000 times. We did not
include the autoencoder approach in this evaluation, given its poor
performance when compared to the plain NN models. Table I presents the results
of our evaluation. As we can see, while both mean and median runtime for NIST
tests are faster then HEDGE, our proposed binary classifier is considerably
faster than both. Both mean and median runtime for the ML model are three
orders of magnitude faster than both NIST and HEDGE, making it easily
applicable to scenarios that require fast classification results such as
ransomware detection. It is worth noting that the evaluation of our ML model
was carried out by measuring the time required to predict a single sample,
rather than a batch of samples. However, our model can easily classify
multiple samples in parallel by exploiting the heavy parallelism of GPUs,
further decreasing the runtime required per individual sample.

Approach | Mean | Median | Std.dev
---|---|---|---
NIST | 0.1 | 0.1 | 0.004
HEDGE | 0.44 | 0.43 | 0.008
Binary Classifier | 0.00046 | 0.00044 | 0.00012
TABLE I: Time required by each approach to classify one sample, in seconds.

##  VI Discussion of Findings

Results shown in Section V highlight the difficulty of discriminating
compressed and encrypted fragments. State-of-the-art statistical tests tend to
fare better than entropy measures (ref. Section II), but their performance
varies significantly depending on the specifics of the compressed format and
fragment size. Moreover, such approaches can only determine whether a given
fragment is encrypted with a certain confidence, but cannot distinguish
between different compressed formats. EnCoD, the learning-based approach
introduced in Section IV, tackles both these limitations. Both per-format and
multi-class classifiers outperform existing tests on all considered file
types/block sizes. Moreover, our multi-class classifier can be used to
determine the format of a given unknown fragment, even in the complete absence
of any context or information on its type.

Results show that accuracy improves consistently with increasing fragment
size. This is in a sense to be expected; all approaches considered in this
paper leverage differences between the byte value distribution of random data
(which is uniform) and that of compressed data. Perfectly estimating the byte
value distribution of a short data stream is generally not possible. As
sequences get shorter, the probability that the estimated distribution may not
reflect the typical distribution for their content type increases. However, as
the size of the sample increases, the estimated empirical distribution
approaches the underlying data distribution, allowing us to capture any
deviation from the uniform distribution. For modern compression algorithms,
these deviations are quite minor, and a 512-byte block gives even accurate
tests very little data to work with. However, when enough data is available,
it is possible to identify the class of data with high accuracy; our learning-
based classifier exceeds 90% accuracy already for 2048-byte blocks. In
general, we recommend against using any one approach as the sole guidance for
automated security decisions (e.g. dropping/allowing flows, terminating
processes, etc.). However, when integrated as part of a more complete set of
features in a larger system, our proposed classifiers can provide an
additional robust feature to use in the decision-making process.

Given the discussion above, we suspect an intrinsic bound on the accuracy
reachable by any classifier which looks purely at byte value distributions.
However, approaches attempting to parse fragments or identify recognizable
structures are likely to incur an impractical computational cost. Moreover, it
is not apparent that any such structure is preserved for very short fragment
sizes.

##  VII Related Work

###  VII-A Entropy-based encryption detection

Use of entropy estimation to detect encrypted content is common in ransomware
detection. Proposals such as RWGuard [34], UNVEIL [27], Redemption [26] and
ShieldFS [17] use entropy of written content either directly as a feature, or
as part of feature calculation. It should be noted that none of these
detectors use entropy as the sole feature for detection. However, evidence
from Section II suggests that they may be better ignoring entropy altogether.
In the realm of digital forensics, entropy estimation has been used to
determine the type of unknown disk data fragments. One of the most complete
approaches is that of Conti et al. [16]. However, the same authors found that
such estimates have limited discerning power in distinguishing encrypted and
compressed content, and aggregated the two types under a single label.

Entropy estimation has also been applied to the real-time analysis of network
traffic. Dorfinger’s Master thesis [21] proposes a system for discriminating
encrypted and non-encrypted traffic, to ensure that all communications from a
target network are encrypted. Similar approaches were also proposed by Mamun
et al. [32] and Malhotra [31]. Zhang et al. proposed an entropy-based
classifier for the identification of botnet traffic [45]. All these approaches
also suffer from the limitations of using high entropy as a fingerprint of
encryption. Wang et al. [44] report positive results in using an SVM
classifier to discriminate between various data types using entropy estimates.
Their application scenario is different from ours, as they consider both low-
entropy (non-compressed) and high-entropy (compressed or encrypted) formats.
We only consider high-entropy formats, which are difficult to distinguish
using entropy alone.

Finally, MovieStealer [43] aims at identifying encrypted and decrypted-but-
compressed media buffers in order to break DRM. It uses an entropy test to
single out encrypted and compressed buffers from other data, and the
$\chi^{2}$-test to distinguish them. It requires 800KB of data to reliably
identify random data, which is far beyond the fragment size in the scenarios
that we consider.

###  VII-B Non-entropy-based approaches

HEDGE, by Casino et al. [12], evaluates a combination of $\chi^{2}$-test and a
subset of NIST SP800-22 [39] to discriminate encrypted and compressed traffic.
They use a dataset which is significantly smaller than ours, and do not
discuss learning-based approaches. A limitation of this class of approaches is
the fairly low accuracy, especially for small block sizes (ref. Section V).
Also, this and other similar approaches based on statistical randomness tests
(e.g., [35, 14]) cannot distinguish between different types of compressed
archives. Mbol et al. [33] investigate the use of the Kullback-Leibler
divergence (relative entropy) to differentiate encrypted files from JPEG
images. Their analysis does not investigate other formats, and assumes the
availability of blocks of significant size (128 to 512KB) from the beginning
of each file. Especially in forensic and networking applications,
uninterrupted blocks of such size are difficult to obtain.

While the application of neural networks to the problem at hand is fairly new,
there exist some preliminary work. Ameeno et al. [11] show promising
preliminary results, however the analysis is limited in scope: it only
attempts to distinguish zip archives from rc4-encrypted data, and considers
whole files (not fragments). Hahn et al. [25] perform an exploratory analysis
of machine learning models. Their dataset is order of magnitudes smaller than
ours, and they lack a comparative analysis of statistical approaches.

##  VIII Conclusions

Discriminating encrypted from non-encrypted content is important for a variety
of security applications, and oftentimes tackled via entropy estimation. We
comprehensively highlighted the limits of this technique and reviewed the
effectiveness of the leading alternative approaches: $\chi^{2}$-test, NIST
SP800-22 test suite, and HEDGE. In addition, we proposed EnCoD, a novel neural
network classifier of our own design. In order to ensure generality of
results, we created a dataset of 400M fragments covering 5 different sizes and
16 data formats.

Results show that previous state-of-the-art methods have blind spots which
result in low accuracy for certain fragment sizes/data types. However, our
neural network-based approach appears promising. While statistical tests only
discriminate between compressed and encrypted data fragments, our multiclass
classifier is able to classify between specific compressed formats with $\sim
83\%$ accuracy already on 2KB fragments, and our binary classifier reaches
$\sim 90\%$ accuracy on the same fragment size. This suggests that systems
incorporating encrypted content detection (e.g., ransomware detectors) would
be better served by learning-based, rather than hand-crafted statistical
approaches. This finding also suggests that learning may have useful
applications to other problems in content type inference. Overall, we believe
this work is an important step forward towards reliable encryption detection.

##  IX Acknowledgments

We would like to thank Daniele Venturi and Guinevere Gilman for their useful
insights and comments. This work was supported by Gen4olive, a project that
has received funding from the European Union’s Horizon 2020 research and
innovation programme under grant agreement No. 101000427, and in part by the
Italian MIUR through the Dipartimento di Informatica, Sapienza University of
Rome, under Grant Dipartimenti di eccellenza 2018–2022.

## References

  * [1] “Pycriptodome library.” [Online]. Available: https://pycryptodome.readthedocs.io/en/latest/src/introduction.html
  * [2] “DOCX Transitional (Office Open XML),” Jan. 2017. [Online]. Available: https://www.loc.gov/preservation/digital/formats/fdd/fdd000397.shtml
  * [3] “Atlanta spent $2.6m to recover from a $52,000 ransomware scare,” https://www.wired.com/story/atlanta-spent-26m-recover-from-ransomware-scare/, 2018\.
  * [4] “Wannacry cyber attack cost the nhs £92m as 19,000 appointments cancelled,” https://www.telegraph.co.uk/technology/2018/10/11/wannacry-cyber-attack-cost-nhs-92m-19000-appointments-cancelled/, 2018\.
  * [5] “Evolvingai: Deep neural networks are easily fooled: High confidence predictions for unrecognizable images,” Dec. 2019. [Online]. Available: http://www.evolvingai.org/fooling
  * [6] “Fma: A dataset for music analysis,” Dec. 2019. [Online]. Available: https://github.com/mdeff/fma
  * [7] “Open images dataset v5,” Dec. 2019. [Online]. Available: https://www.figure-eight.com/dataset/open-images-annotated-with-bounding-boxes/
  * [8] “Wikipedia:database download,” Dec. 2019. [Online]. Available: https://dumps.wikimedia.org/enwiki/
  * [9] “arXiv.org e-Print archive,” Feb. 2020. [Online]. Available: https://arxiv.org/
  * [10] “Ransomware attacks grow, crippling cities and businesses,” https://www.nytimes.com/2020/02/09/technology/ransomware-attacks.html, 2020\.
  * [11] N. Ameeno, K. Sherry, and K. Gagneja, “Using Machine Learning to Detect the File Compression or Encryption,” _Amity Journal of Computational Sciences_ , vol. 3, no. 1, p. 6, 2019.
  * [12] F. Casino, K.-K. R. Choo, and C. Patsakis, “HEDGE: Efficient Traffic Classification of Encrypted and Compressed Packets,” _IEEE Transactions on Information Forensics and Security_ , vol. 14, no. 11, pp. 2916–2926, Nov. 2019.
  * [13] F. Chollet _et al._ , “Keras,” https://keras.io, 2015.
  * [14] P. Choudhury, K. R. P. Kumar, S. Nandi, and G. Athithan, “An empirical approach towards characterization of encrypted and unencrypted VoIP traffic,” _Multimedia Tools and Applications_ , vol. 79, no. 1-2, pp. 603–631, Jan. 2020.
  * [15] I. T. L. Computer Security Division, “NIST SP 800-22: Documentation and Software,” May 2016. [Online]. Available: https://csrc.nist.gov/projects/random-bit-generation/documentation-and-software
  * [16] G. Conti, S. Bratus, A. Shubina, B. Sangster, R. Ragsdale, M. Supan, A. Lichtenberg, and R. Perez-Alemany, “Automated mapping of large binary objects using primitive fragment type classification,” _Digital Investigation_ , vol. 7, pp. S3–S12, Aug. 2010.
  * [17] A. Continella, A. Guagnelli, G. Zingaro, G. De Pasquale, A. Barenghi, S. Zanero, and F. Maggi, “Shieldfs: A self-healing, ransomware-aware filesystem,” in _ACSAC_ , 2016.
  * [18] L. De Carli, R. Torres, G. Modelo-Howard, A. Tongaonkar, and S. Jha, “Botnet Protocol Inference in the Presence of Encrypted Traffic,” in _INFOCOM_ , 2017.
  * [19] F. De Gaspari, D. Hitaj, G. Pagnotta, L. De Carli, and L. V. Mancini, “Encod: Distinguishing compressed and encrypted file fragments,” in _International Conference on Network and System Security_. Springer, 2020, pp. 42–62.
  * [20] F. De Gaspari, D. Hitaj, G. Pagnotta, L. De Carli, and L. V. Mancini, “The naked sun: Malicious cooperation between benign-looking processes,” in _18th International Conference on Applied Cryptography and Network Security_ , ser. ACNS, 2020.
  * [21] P. Dorfinger, G. Panholzer, and W. John, “Entropy estimation for real-time encrypted traffic identification,” in _Traffic Monitoring and Analysis_ , 2011.
  * [22] R. Fielding, J. Gettys, J. Mogul, H. Frystyk, L. Masinter, P. Leach, and T. Berners-Lee, “Rfc 2616, hypertext transfer protocol – http/1.1,” 1999. [Online]. Available: http://www.rfc.net/rfc2616.html
  * [23] X. Glorot and Y. Bengio, “Understanding the difficulty of training deep feedforward neural networks,” in _AISTATS_ , 2010.
  * [24] D. Hahn, N. Apthorpe, and N. Feamster, “Detecting compressed cleartext traffic from consumer internet of things devices,” 2018.
  * [25] ——, “Detecting Compressed Cleartext Traffic from Consumer Internet of Things Devices,” _arXiv:1805.02722 [cs]_ , May 2018. [Online]. Available: http://arxiv.org/abs/1805.02722
  * [26] A. Kharraz and E. Kirda, “Redemption: Real-time protection against ransomware at end-hosts,” in _RAID_ , 2017.
  * [27] E. Kirda, “Unveil: A large-scale, automated approach to detecting ransomware (keynote),” in _SANER_ , 2017.
  * [28] G. Klambauer, T. Unterthiner, A. Mayr, and S. Hochreiter, “Self-normalizing neural networks,” _CoRR_ , vol. abs/1706.02515, 2017. [Online]. Available: http://arxiv.org/abs/1706.02515
  * [29] Y. LeCun, L. Bottou, G. B. Orr, and K.-R. Müller, “Efficient backprop,” in _Neural Networks: Tricks of the Trade_ , 1998.
  * [30] H. Lee, R. Ge, T. Ma, A. Risteski, and S. Arora, “On the ability of neural nets to express distributions,” in _Proceedings of the 30th Conference on Learning Theory, COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017_ , ser. Proceedings of Machine Learning Research, S. Kale and O. Shamir, Eds., vol. 65. PMLR, 2017, pp. 1271–1296. [Online]. Available: http://proceedings.mlr.press/v65/lee17a.html
  * [31] P. Malhotra, “Detection of encrypted streams for egress monitoring,” Master of Science, Iowa State University, Ames, 2007. [Online]. Available: https://lib.dr.iastate.edu/rtd/14632/
  * [32] M. S. I. Mamun, A. A. Ghorbani, and N. Stakhanova, “An Entropy Based Encrypted Traffic Classifier,” in _Information and Communications Security_ , ser. Lecture Notes in Computer Science, S. Qing, E. Okamoto, K. Kim, and D. Liu, Eds. Cham: Springer International Publishing, 2016, pp. 282–294.
  * [33] F. Mbol, J.-M. Robert, and A. Sadighian, “An Efficient Approach to Detect TorrentLocker Ransomware in Computer Systems,” in _Cryptology and Network Security_ , S. Foresti and G. Persiano, Eds. Cham: Springer International Publishing, 2016, vol. 10052, pp. 532–541.
  * [34] S. Mehnaz, A. Mudgerikar, and E. Bertino, “Rwguard: A real-time detection system against cryptographic ransomware,” in _Research in Attacks, Intrusions, and Defenses_ , ser. RAID ’18, 2018.
  * [35] A. Palisse, A. Durand, H. Le Bouder, C. Le Guernic, and J.-L. Lanet, “Data Aware Defense (DaD): Towards a Generic and Practical Ransomware Countermeasure,” in _Secure IT Systems_ , H. Lipmaa, A. Mitrokotsa, and R. Matulevičius, Eds. Cham: Springer International Publishing, 2017, vol. 10674, pp. 192–208.
  * [36] B. Park, A. Savoldi, P. Gubian, J. Park, S. H. Lee, and S. Lee, “Data Extraction from Damage Compressed File for Computer Forensic Purposes,” _International Journal of Hybrid Information Technology_ , vol. 1, no. 4, p. 14, Oct. 2008.
  * [37] M. Piskozub, F. De Gaspari, F. Barr-Smith, L. Mancini, and I. Martinovic, “Malphase: Fine-grained malware detection using network flow data,” in _Proceedings of the 2021 ACM on Asia Conference on Computer and Communications Security_ , ser. ASIACCS’21, 2021.
  * [38] Y. Qi, Y. Wang, X. Zheng, and Z. Wu, “Robust feature learning by stacked autoencoder with maximum correntropy criterion,” in _2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2014.
  * [39] A. Rukhin, J. Soto, J. Nechvatal, E. Barker, S. Leigh, M. Levenson, D. Banks, A. Heckert, and J. Dray, “A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications,” NIST, Special Publication 800-22r1a, Apr. 2010.
  * [40] L. Trottier, P. Giguere, and B. Chaib-draa, “Parametric exponential linear unit for deep convolutional neural networks,” in _2017 16th IEEE International Conference on Machine Learning and Applications (ICMLA)_ , 2017.
  * [41] G. K. Wallace, “The jpeg still picture compression standard,” _IEEE transactions on consumer electronics_ , vol. 38, no. 1, pp. xviii–xxxiv, 1992\.
  * [42] R. J. Walls, E. Learned-Miller, and B. N. Levine, “Forensic Triage for Mobile Phones with DEC0DE,” in _USENIX Security Symposium_ , 2011\.
  * [43] R. Wang, Y. Shoshitaishvili, C. Kruegel, and G. Vigna, “Steal This Movie - Automatically Bypassing DRM Protection in Streaming Media Services,” in _USENIX_ , 2013.
  * [44] Y. Wang, Z. Zhang, L. Guo, and S. Li, “Using Entropy to Classify Traffic More Deeply,” in _2011 IEEE Sixth International Conference on Networking, Architecture, and Storage_ , Jul. 2011, pp. 45–52.
  * [45] H. Zhang, C. Papadopoulos, and D. Massey, “Detecting encrypted botnet traffic,” in _2013 Proceedings IEEE INFOCOM_ , Apr. 2013, pp. 3453–1358.

|  Fabio De Gaspari is a PostDoc researcher at the Computer Science Department
of Sapienza University of Rome, Italy. He received the PhD in Computer Science
from Sapienza University in 2019. His research areas are machine learning and
security, new network architectures and security and active defence
techniques. Fabio obtained his MSc in Computer Science with honors in 2015
from the University of Padova, Italy.
---|---
|  Dorjan Hitaj is a PhD student in Computer Science with Sapienza University
of Rome. His research focus is on machine learning and security. He obtained
his MSc. degree in Computer Science with high honors from Sapienza University
of Rome in 2018.
---|---
|  Giulio Pagnotta is a Ph.D. student in Computer Science with Sapienza
University of Rome. His research focus is on machine learning and security. He
obtained his MSc. degree in Cybersecurity with high honors from Sapienza
University of Rome in 2019.
---|---
|  Lorenzo De Carli ’s research interests focus on the security of the web and
internet-of-things devices, and usable security. His contributions include
hardware accelerators for packet inspection and forwarding, parallelization
strategies for intrusion detection, and analysis of malware communications.
Lorenzo received a B.Sc. (2004) and a M.Sc. (2007) in Computer Engineering
from Politecnico di Torino, Italy, and a M.Sc. (2010) and Ph.D. (2016) in
Computer Science from the University of Wisconsin-Madison.
---|---
|  Luigi V. Mancini received the PhD degree in Computer Science from the
University of Newcastle, U.K., in 1989. He is currently a Full Professor with
Sapienza University of Rome, where he is the chair of the Master degree in
Cybersecurity. He has authored over 130 scientific papers in international
conferences and journals.
---|---


# PyHard: a novel tool for generating hardness embeddings to support data-
centric analysis

Pedro Yuri Arbs Paiva
Instituto Tecnológico de Aeronáutica (ITA)
Praça Marechal Eduardo Gomes, 50
São José dos Campos, SP, Brazil
<EMAIL_ADDRESS>
Kate Smith-Miles
School of Mathematics and Statistics
The University of Melbourne
Parkville VIC 3010, Australia
<EMAIL_ADDRESS>Maria G. Valeriano
Instituto Tecnológico de Aeronáutica (ITA)
Praça Marechal Eduardo Gomes, 50
São José dos Campos, SP, Brazil
<EMAIL_ADDRESS>Ana Carolina Lorena
Instituto Tecnológico de Aeronáutica (ITA)
Praça Marechal Eduardo Gomes, 50
São José dos Campos, SP, Brazil
<EMAIL_ADDRESS>

###### Abstract

For building successful Machine Learning (ML) systems, it is imperative to
have high quality data and well tuned learning models. But how can one assess
the quality of a given dataset? And how can the strengths and weaknesses of a
model on a dataset be revealed? Our new tool PyHard employs a methodology
known as Instance Space Analysis (ISA) to produce a hardness embedding of a
dataset relating the predictive performance of multiple ML models to estimated
instance hardness meta-features. This space is built so that observations are
distributed linearly regarding how hard they are to classify. The user can
visually interact with this embedding in multiple ways and obtain useful
insights about data and algorithmic performance along the individual
observations of the dataset. We show in a COVID prognosis dataset how this
analysis supported the identification of pockets of hard observations that
challenge ML models and are therefore worth closer inspection, and the
delineation of regions of strengths and weaknesses of ML models.

##  1 Introduction

A recent Meta-Learning (MtL) (Vilalta and Drissi, , 2002; Vanschoren, , 2019)
methodology known as Instance Space Analysis (ISA) has demonstrated success in
gaining insights through the visual analysis of the relationships between the
performance of ML classification techniques and data meta-features across
multiple datasets (Muñoz et al., , 2018). Using ISA, the performance of
multiple ML classification techniques can be predicted and understood in terms
of a set of meta-features describing popular classification datasets from
public repositories. A 2-D projection relating meta-features values and
algorithmic performance is then created, presenting linear trends that reveal
pockets of hard and easy datasets, that is, datasets that are harder or easier
for the algorithms to classify, revealing the strengths and weaknesses of each
classifer.

We adapt here such a framework for a fine-grained analysis of a single
classification dataset, rather than a collection of datasets, so that we can
ontain similar insights about the difficulties of individual observations
within a dataset. Given a dataset of interest, multiple measures of the
hardness level of its observations are extracted and related to the
algorithmic performance of popular ML models. As a result, a 2-D hardness
embedding of the original dataset is obtained, which can be scrutinized to
inspect data quality and understand classifier behaviors. We present herein
PyHard, an analytical tool designed to assist the understanding of the
difficulty level of the individual observations in a dataset, and also to
trace regions where each algorithm is expected to perform well. We show in a
case study with a dataset for COVID-19 prognosis how this tool supported the
identification of problematic observations and the understanding of the
behavior of different classifiers across the dataset.

##  2 Instance Space Analysis for a single dataset

As originally proposed, the Instance Space Analysis (ISA) builds upon the
Algorithm Selection Problem (ASP) (Rice, , 1976; Smith-Miles, , 2009), whose
objective is to automate the process of selecting good candidate algorithms
and their hyperparameters for solving new problems, based on knowledge
gathered from similar problems they solved in the past. The ISA framework goes
further and extends the ASP analysis to give insights into why some instances
are harder to solve than others, combining the information of meta-features
and algorithm performance in a new embedding that can be visually inspected.
To this end, an optimization problem is solved to find the mapping from the
high dimensional meta-features space into a 2-D space, such that the
distribution of algorithm performance metrics and meta-feature values across
instances in the 2-D space displays as much of a linear trend as possible to
assist the interpretation of hardness directions. Footprints of algorithm
performance representing regions where each algorithm performs well can also
be delineated, allowing to characterize their domains of competence. Objective
measures of algorithmic performance along the IS can be extracted from the
footprints too, such as area, density and purity. Details on the construction
of the instance space and calculation of algorithm footprints can be found at
(Muñoz et al., , 2018, 2021).

Original dataset
$D$$f(\mathbf{x}_{i})\in\mathcal{F}$Hardnessmeasures$\alpha\in\mathcal{A}$Algorithmspace$y\in\mathcal{Y}$Performancespace$fs(f(\mathbf{x}_{i}),y)$Featureselection$\mathbf{\mu}\in\mathcal{M}$Metadata$(z_{1},z_{2})\in\mathbb{R}^{2}$Instance
space$f(\cdot)$$y(\alpha,\bm{x}_{i})$$ISA$

Figure 1: ISA framework for a single dataset.

Here we recast the framework for the analysis of a single classification
dataset, as outlined in Figure 1. Given a dataset $\mathcal{D}$ with $n$
labeled observations $\mathbf{x}_{i}$, a set of hardness measures (HM)
$\mathcal{F}$ assessing their difficulty (aka hardness level) is extracted. A
pool of ML classifiers of distinct biases are applied to the dataset and
compose the algorithm space $\mathcal{A}$, namely: Bagging, Gradient Boosting,
Support Vector Machine (both linear and RBF kernels), Logistic Regression,
Multilayer Perceptron and Random Forest (but alternative algorithms can be
added). The performance space $\mathcal{Y}$ records the performance obtained
by each algorithm in $\mathcal{A}$ for each instance $\mathbf{x}_{i}\in D$. A
meta-dataset $\mathcal{M}$ is built by joining a subset of $\mathcal{F}$ and
the set $\mathcal{Y}$. The former subset contains meta-features which relates
more to the performance space $\mathcal{Y}$, which are screened in a feature
selection step. ISA is then applied for obtaining the 2-D hardness embedding
(instance space). Some of the most specific components of our framework are
described next.

### Hardness measures.

One important aspect when performing ISA is using a set of informative meta-
features able to reveal the capabilities of the algorithms and the level of
difficulty each individual instance poses. Here we revisit the definition of
Instance Hardness (IH) proposed by Smith et al.,  (2014) as a property that
indicates the likelihood that an instance will be misclassified. IH is
measured by Equation 1, where $p\big{(}c_{i}|\mathbf{x}_{i},\alpha_{j}\big{)}$
gives the probability a learning model $\alpha_{j}$ induced from $D$ assigns
$\mathbf{x}_{i}$ to its expected class $c_{i}$. According to this formulation,
observations that are frequently misclassified by a pool $\mathcal{A}$ of
diverse learning algorithms are considered hard, whilst easy instances are
likely to be correctly classified by any of the considered algorithms.

$IH_{\mathcal{A}}\big{(}\mathbf{x}_{i},c_{i}\big{)}=1-\frac{1}{|\mathcal{A}|}\sum_{j=1}^{|\mathcal{A}|}p\big{(}c_{i}|\mathbf{x}_{i},\alpha_{j}\big{)}$
(1)

Table 1: Hardness measures employed as meta-features in this work.

Measure | Acron. | Min | Max | Reference
---|---|---|---|---
k-Disagreeing Neighbors | $kDN$ | 0 | 1 | (Smith et al., , 2014)
Disjunct Class Percentage | $DCP$ | 0 | 1 | (Smith et al., , 2014)
Tree Depth (pruned) | $TD_{P}$ | 0 | 1 | (Smith et al., , 2014)
Tree Depth (unpruned) | $TD_{U}$ | 0 | 1 | (Smith et al., , 2014)
Class Likelihood | $CL$ | 0 | 1 | (Smith et al., , 2014)
Class Likelihood Difference | $CLD$ | 0 | 1 | (Smith et al., , 2014)
Frac. features in overlapping areas | $F1$ | 0 | 1 | (Arruda et al., , 2020)
Frac. nearby instances of different class | $N1$ | 0 | 1 | (Arruda et al., , 2020)
Ratio of intra-extra class distances | $N2$ | 0 | $\approx 1$ | (Arruda et al., , 2020)
Local set cardinality | $LSC$ | 0 | 1 | (Arruda et al., , 2020)
Local set radius | $LSR$ | 0 | 1 | (Arruda et al., , 2020)
Usefulness | $U$ | $\approx 0$ | $1$ | (Arruda et al., , 2020)
Harmfulness | $H$ | 0 | $\approx 1$ | (Arruda et al., , 2020)

Smith et al.,  (2014) also define a set of hardness measures (HM) intended to
explain why some instances are often misclassified. These are the measures
employed as meta-features in $\mathcal{F}$. Table 1 summarizes the HM employed
in this work, with their names, acronyms, minimum and maximum values
achievable and references from where they are extracted. We introduced
modifications into some of the measures in order to limit and standardize
their values. Consequently, for all measures higher values are registered for
instances that are harder to classify.

### Algorithm performance assessment.

Given a dataset $D$, we first split it into five folds according to the cross-
validation (CV) strategy, such that each instance belongs to one of the test
sets. For each instance, we measure the log-loss error rate achieved in the
predictions, which takes into account the probabilities associated to each
class. Furthermore, a hyper-parameter optimization step was added, acting as
an inner loop for each of the training sets of the outer CV. Within this inner
loop, a candidate set of parameters is evaluated through cross-validation upon
the training data from the outer loop.

### Feature selection.

According to Muñoz et al.,  (2018), it is advisable to maintain just the most
informative meta-features in the meta-dataset $\mathcal{M}$ before the IS
projection is generated. We performed a supervised meta-feature selection in
$\mathcal{M}$, based on the continuous response value
$y(\alpha_{k},\mathbf{x}_{i})$, that is, the log-loss performance of the
classifiers for the instances in $\mathcal{D}$. Since there are seven
classification algorithms in the pool, a ranking of meta-features for each one
of them is obtained. Next, a rank aggregation method is employed to merge
these subsets, as suggested in (Prati, , 2012).

### IS representation and footprints.

PyHard embeds a Python package named PyISpace implementing the main ISA
functionalities, including obtaining the projections and the algorithms’
footprints. In order to assist the visual interpretation of the 2-D
projections, we introduce a rotation step in order to ensure that hard
instances are always placed towards the upper left corner of the IS, whilst
the easier instances are placed towards the bottom right corner of the space.
We also introduce an instance easiness footprint, which are regions of the IS
which encompass observations with IH values below a threshold of 0.4. These
are the easiest instances of the dataset for most of the algorithms.

##  3 Case study: inspecting a COVID prognosis dataset

Here we present an analysis of a dataset containing anonymized data from
citizens positively diagnosed for COVID-19, collected from March 1st, 2020 to
April 15th, 2021111The data comes from a partnership with the health
department of the city of São José dos Campos - SP, Brazil. Part of such data
was formatted for some predictive analysis to support public health decision
making.. The dataset involves predicting whether an individual will require
future hospitalization or not taking as input the following attributes
routinely supplied during COVID scanning: age, sex, initial symptoms (fever,
cough, sore throat, dyspnea, respiratory distress, low saturation, diarrhea,
vomit and other symptoms) and comorbidities (chronic cardiovascular disease,
immunodeficiency-immunodepression, chronic kidney disease, diabetes mellitus,
obesity, chronic respiratory diseases and other risks). The dataset has data
from 5,156 citizens, half of which were hospitalized.

(a) Colored by $IH$ values.

(b) Colored by MLP log-loss.

(c) Colored by age input feature value.

Figure 2: ISA for the hospitalization dataset.

Our objective is to analyze the hardness profile of this dataset and to
extract some insights from the visualization and interaction with its IS222The
complete experiment with anonymizations can be found at:
https://gitlab.com/ita-ml/pyhard/-/tree/master/experiments/hospitalization.
Instructions can be found in ‘experiments’ folder.. Figure 2 presents the ISA
of the hereafter called hospitalization dataset. Each point corresponds to an
observation of the dataset, that is, a confirmed COVID case. In Figure 2a, the
observations are colored according to their IH values, with harder
observations colored in red and easier observations colored in blue,
hospitalized individuals plotted as triangles and non-hospitalized
observations represented by circles. Most of the observations in this dataset
are easy to classify correctly by the algorithm portfolio and the instance
easiness footprint has a large area.

There is a large group of hospitalized citizens with an easier profile placed
in the bottom of the IS. Non-hospitalized observations had mostly an
intermediate hardness level, with low to medium IH. But some particular
clusters of observations hard to classify, highlighted in circles numbered as
I, II and III have caught our attention. Group I contains observations from
the non-hospitalized class, whilst groups II and III have mostly instances
from the hospitalized class. The observations from these groups have: a low
likelihood of belonging to their classes (measured by $CL$ meta-feature); are
placed in disjuncts with elements which do not share their labels (measured by
$DCP$); are close to elements from the opposite class (measured by $N1$); and
have a high proportion of nearest neighbors with labels which differ from
their own (measured by $kDN$). Overall, this indicates these groups probably
contain noisy or outlier instances with input characteristics similar to that
of other class. Plotting the values of the raw input attributes along the IS
allowed us to observe some interesting features. Figure 2c shows one of them:
age (red colors are attributed to elderly and youngsters are colored in blue),
a well known feature with influences on COVID severity, impacting
hospitalization. Indeed, the easiest cases of non-hospitalized citizens tend
to be younger. But some observations from groups I and II have conflicting age
patterns to what is commonly expected. Contradicting patterns are also
observed for other input features along the observations from groups I, II and
III. Inspecting the original records from these groups of citizens, we were
able to confirm that group I has either individuals wrongly labeled as non-
hospitalized and some atypical cases, such as people seeking for
hospitalization too late. Group III has individuals with few and mild symptoms
who were hospitalized and it is possible that their forms have missing
information on some of the symptoms. Group I has also atypical cases which may
contain missing information.

Concerning algorithmic performance, Figure 2b presents the ISA, colored
according to the log-loss performance of the MLP classifier which attained the
largest footprint area (shown within a green polygon). The MLP showed a good
predictive performance for most of the instances except from those of the
groups I and II. The PyHard tool allows to save and to inspect the
characteristics of the instances from a selected footprint for gain further
insights into an algorithm’s strengths and weaknesses, and the explanations
for such based on the characteristics of these instances.

##  4 Conclusion

In this paper we have presented PyHard, a new analytical tool intended to
address a gap in meta-learning studies about instance hardness for a single
dataset, distributed publicly at PyPI333https://pypi.org/project/pyhard/. The
tool allows for the construction, visualization and interaction with a
hardness embedding of a dataset, allowing to obtain useful insights to support
data-centric analysis. Our case study demonstrates the utility of the tool for
identifying anomalous and noisy observations within a dataset and to highlight
observations for which a given classifier shows a consistently good predictive
performance and where it may be biased.

## Acknowledgements

To the São José dos Campos municipal health secretariat and to the research
agencies CAPES - Finance Code 001 (main grant 88887.507037/2020-00), CNPq
(grant 307892/2020-4) and the Australian Research Council (grant FL140100012).

## References

  * Arruda et al., (2020) Arruda, J. L., Prudêncio, R. B., and Lorena, A. C. (2020).  Measuring instance hardness using data complexity measures.  In Brazilian Conference on Intelligent Systems, pages 483–497. Springer.
  * Muñoz et al., (2018) Muñoz, M. A., Villanova, L., Baatar, D., and Smith-Miles, K. (2018).  Instance spaces for machine learning classification.  Machine Learning, 107(1):109–147.
  * Muñoz et al., (2021) Muñoz, M. A., Yan, T., Leal, M. R., Smith-Miles, K., Lorena, A. C., Pappa, G. L., and Rodrigues, R. M. (2021).  An instance space analysis of regression problems.  ACM Transactions on Knowledge Discovery from Data (TKDD), 15(2):1–25.
  * Prati, (2012) Prati, R. C. (2012).  Combining feature ranking algorithms through rank aggregation.  In The 2012 International Joint Conference on Neural Networks (IJCNN), pages 1–8. IEEE.
  * Rice, (1976) Rice, J. R. (1976).  The algorithm selection problem.  In Advances in Computers, volume 15, pages 65 – 118. Elsevier.
  * Smith et al., (2014) Smith, M. R., Martinez, T., and Giraud-Carrier, C. (2014).  An instance level analysis of data complexity.  Machine Learning, 95(2):225–256.
  * Smith-Miles, (2009) Smith-Miles, K. A. (2009).  Cross-Disciplinary Perspectives on Meta-Learning for Algorithm Selection.  ACM Computing Surveys, 41(1).
  * Vanschoren, (2019) Vanschoren, J. (2019).  Meta-learning.  In Automated Machine Learning, pages 35–61. Springer.
  * Vilalta and Drissi, (2002) Vilalta, R. and Drissi, Y. (2002).  A perspective view and survey of meta-learning.  Artificial Intelligence Review, 18(2):77–95.