# Decrypting Live SSH Traffic in Virtual Environments

Peter McLaren, Gordon Russell, William J Buchanan and Zhiyuan Tan  School of
Computing, Edinburgh Napier University, Edinburgh.

###### Abstract

Decrypting and inspecting encrypted malicious communications may assist crime
detection and prevention. Access to client or server memory enables the
discovery of artefacts required for decrypting secure communications. This
paper develops the MemDecrypt framework to investigate they discovery of
encrypted artefacts in memory and applies the methodology to decrypting the
secure communications of virtual machines. For Secure Shell, used for secure
remote server management, file transfer, and tunnelling inter alia, MemDecrypt
experiments rapidly yield AES-encrypted details for a live secure file
transfer including remote user credentials, transmitted file name and file
contents. Thus, MemDecrypt discovers cryptographic artefacts and quickly
decrypts live SSH malicious communications including detection and
interception of data exfiltration of confidential data.

###### keywords:

network traffic; decryption; memory analysis; IoT; Android; VMI; Secure Shell;
SSH; AES; Secure File Transfer; data exfiltration; insider attacks;

††journal: Digital Investigation

##  1 Introduction

Decrypting malicious communications offers opportunities to discover useful
information. This could include botnet command and control traffic identifying
compromised machines, confidential information that has been extracted and
sent or uploaded to an external location, ransomware keys, or details of
criminal activity [1]. This paper focuses on decrypting Secure Shell (SSH)
traffic, a potential medium for data exfiltration [2]. Realistically useful
decryption methods require a knowledge of both the algorithm and the
cryptographic artefacts used. Encryption techniques based only on algorithmic
secrecy may be unreliable, as mechanisms such as reverse-engineering enable
the algorithm’s functionality to be discovered and furthermore, without
extensive independent verification, the robustness of an encryption algorithm
may be weak [3]. As a result, publicly known encryption algorithms are
commonly used, and key secrecy thus becomes paramount. Generating sufficiently
long random blocks as keys makes decryption unlikely using brute force
methods.

To decrypt, a framework must discover keys and other cryptographic artefacts.
When software applications perform encryption and decryption, the artefacts
reside in program memory at that moment, whether on the program stack, in the
heap, or in shared memory. As memory access is important to forensic
investigations [4] software tools and libraries already exist to support such
capability for technologies such as desktops, servers, the Internet of Things
(IoT), Android smartphones, and virtualized environments. Mechanisms to
discover cryptographic artefacts in memory in a manner that allows the target
device to continue to operate normally during an investigation while remaining
undetectable is of particular interest. This paper presents the MemDecrypt
framework that stealthily decrypts secure communications traffic. Although
earlier researchers have discovered encryption keys in device memory, other
cryptographic artefacts, commonly required to decrypt secure traffic, are not
considered. MemDecrypt implements a novel approach to decrypting SSH traffic
by analyzing target memory extracts to identify these candidate cryptographic
artefacts (initialization vectors) that, in turn, enable rapid location of
candidate keys and the deciphering of payloads in live sessions with high
probability. This enables malicious SSH activity in live secure communications
sessions to be addressed. The techniques proposed are applicable to a range of
device platforms, though the MemDecrypt framework is particularly focused on
decrypting communications from within virtual machines.

Although plaintext could be obtained by adding an audit function to the
binary, this is arguably a different application and has some similarity with
a key logger, which may only be acceptable in specific environments. Also,
unless all plaintext is captured rather than client input, file contents are
not obtained.

Plaintext could possibly be obtained by extracting on buffer memory writes.
However, researchers have found that monitoring virtual machine read/write
buffers is inefficient. As memory extraction is invasive minimizing the number
of extracts is preferable so with buffer memory write triggers, the larger the
exfiltrated file, the more extracts. To discover the plaintext of a full
session, buffer breaks would need to be in place before the session. In
MemDecrypt, memory can be extracted at any stage after the handshake completes
to decrypt a captured network session. Buffer memory write triggers may be
effective with interactive sessions as with exfiltrated data, missing an
extract makes decryption problematic. Furthermore, exfiltrating non-ASCII data
may be more challenging without certainty of buffer memory locations.

The rest of the paper is structured as follows. To provide framework context,
the background to secure communications is provided in Section II. Earlier
research in discovering cryptographic artefacts is reviewed in Section III.
Section IV presents the MemDecrypt design and Section V the implementation
details. Test results are evaluated and discussed in Section VI and
conclusions drawn in Section VII.

##  2 Related Work

This section provides a summary of symmetric encryption including block and
stream algorithms commonly used in secure communications protocols. Approaches
for accessing memory to support cryptographic artefact discovery are also
discussed.

Although there is no published research into finding cryptographic artefacts
in Android smartphone and IOT device memory, desktop and server memory has
been studied. Entropy measures have frequently been used as a filtering
mechanism to discover keys. This approach assisted in searches for AES key
schedules after cold-boot attacks [5] as well in finding Skipjack and Twofish
algorithm artefacts [6]. These studies focus on encryption key discovery in
dormant devices and therefore do not decrypt the secure network sessions of
live virtual machines.

Although malware analysis and detection has been a research focus for
monitoring from outside the virtual machine, it has also been applied to
analyze secure communications. For example, SSH session details were obtained
from an SSH honeypot server customized to extract data when the specific
system calls executed [7]. In TLSkex [8], AES-CBC cryptographic keys were
discovered in Linux client virtual machine memory when Change Cipher Spec
messages were detected in TLS network sessions by searching for bit strings
where the counts of 0’s and 1’s suggested randomness. TLSkex investigates TLS
traffic only so, for example, the uploading of confidential data using SSH is
not considered. Furthermore, TLSkex analysis is restricted to Linux virtual
machine so Windows virtual machine activity is excluded. The MemDecrypt
framework decrypts entire sessions for both SSH and TLS protocols where
different encryption algorithms have been applied for Windows clients and
Linux servers using a standard entropy measure. Moreover, MemDecrypt memory
extractions are independent of message type and discovery of candidate
initialization vectors drives the decryption process.

Encryption keys can be discovered by intercepting encryption function calls to
extract parameters. For example, the Linux ptrace command can attach to the
encrypting process enabling identification of keys and other artefacts [9].
This approach may have been used to discover SSH plaintext, ciphertext, and
keys, although implementation details are unclear [10]. These approaches are
Linux-specific and are easily detectable by virtual machine software.
Consequently, they may not be effective against malicious insiders, especially
when the target device runs Windows. Ptrace or the related strace can also
monitor server system calls to extract SSH plaintext although this presumes
control of the server and rapidity of tracing both of which may be problems in
live scenarios. MemDecrypt decrypts SSH network sessions in a stealthy manner
by triggering memory extracts only when an unusual event is detected.

###  2.1 Encryption algorithms

Encryption algorithms for secure communications are asymmetric or symmetric.
For encryption and decryption, asymmetric algorithms use different keys
whereas symmetric algorithms use the same keys. Asymmetric algorithms attain
security through computational complexity, which takes processor time, making
them considerably less CPU efficient than symmetric algorithms [11].
Consequently, asymmetric algorithms are frequently only used for agreement on
symmetric keys, which are then used to encrypt the channel. Symmetric
encryption algorithms are either stream algorithms, where plaintext is
encrypted with either bit-by-bit or block algorithms (where blocks of a
specific size are encrypted). Although the Advanced Encryption Standard (AES)
block algorithm may be the _gold standard_ , vulnerability and performance
concerns have led to the adoption of ChaCha20 stream algorithm with Poly-1305
authentication [12] in secure protocols such as OpenSSH and OpenSSL, as well
as being used for Google Chrome related communications on Android smartphones
[13].

Block and stream algorithms commonly require initialization vectors (IVs) for
secure communications. For AES, IVs incorporated in the encryption process
provide defenses against replay attacks [14]. For example, in AES counter mode
(AES-CTR), an IV is encrypted and XORed with the plaintext to produce
ciphertext. AES-CTR is the quickest AES mode, and is recommended by security
experts [3] [15]. For ChaCha20, the key, IV, and a counter are parameters to
keystream creation [12]. The keystream is XORed with the plaintext to produce
ciphertext. Both AES-CTR and ChaCha20 are approved for SSH [16] and TLS
protocols. Consequently, encryption keys and IVs must be discovered to decrypt
AES-CTR and ChaCha20 encrypted SSH and TLS channels.

This paper focuses on SSH communications. For SSH in AES-CTR mode, the IV
increments by 1 for each outgoing plaintext block [17] so that the difference
between the IV for the first plaintext block in packets n+1 and n is the
number of plaintext blocks in packet n. Although AES-CTR is the only
recommended SSH AES mode [16], AES-CBC is also used. For AES-CBC, each IV
after the initial value is the ciphertext of the previous block [17].
Consequently, the IV for each encrypted AES-CBC block is known. ChaCha20 uses
the IV to generate key streams. It performs 20 rounds of mathematical
operations starting from a base structure consisting of a constant string of
16 bytes, a generated 32-byte key, a 4-byte counter, and a 12-byte IV, where
the counter is typically 0 or 1 for each 64-byte plaintext block [12].

SSH enables secure management of remote servers across potentially insecure
networks, offering functionality such as client-server file transfer. The
protocol is specified in 4 key IETF RFCs: SSH Protocol Architecture (SSH-ARCH)
[18], SSH Transport Layer Protocol (SSH-TRANS)[19], SSH Authentication
Protocol (SSH-AUTH) [20], and the SSH Connection Protocol (SSH-CONNECT) [21].
SSH-TRANS defines the initial connection, packet protocol, server
authentication, and the basic encryption and integrity service [22]. Following
the TCP handshake, the parties transmit supported SSH protocol versions, and
optionally application, which enables the probable operating systems and
library to be inferred. For instance, ’SSH-2.0-PuTTY_Release_0.70’ probably
signifies that a Windows client is executing the PuTTY application [23].
Exchanged ’Key Exchange Initialization; and ’Key Exchange’ messages determine
the session encryption and authentication algorithm and the material for the
generation of the cryptographic artefacts. Client _New Keys_ messages advises
that all subsequent traffic in the session is encrypted. An example of the
handshake process as well as the first encrypted packet is illustrated in
Figure 1. SSH-AUTH defines authentication methods such as _public key_ ,
_password_ , _host based_ and _none_. After successful authentication, a file
transfer requires the establishment of a secure channel to support the secure
file transfer protocol as defined by. Secure file transfer (SFTP) [24] is an
SSH sub-system particularly worthy for investigation as significant potential
exists for it to transfer confidential files out of a system.

Figure 1:  SSH Handshake Example

###  2.2 Memory Access

Memory acquisition tools assist forensic analysis. So, for workstation and
server technologies hardware and software acquisition methods exist [25].
Hardware acquisition typically involves connecting devices, such as PCMCIA
cards or USB sticks, to a target [26] while software acquisition commonly
involves executing extraction programs such as FTK Imager [27], Memoryze [28],
or WinPmem [29] on the target [30]. These solutions may not always be
practical in live network session decryption scenarios.

Android smartphone volatile memory is accessible. As Androids run Linux,
memory acquisition tools such as the Linux Memory Extractor (’LiME’)
application [31] may suffice. However, LiME depends on compiled kernel modules
for the target’s Linux version, support by the smartphone and kernel level
execution. The quantity of Linux variations for Android smartphones as well as
the installation and execution requirements may be challenging. AMExtractor
[32] requires kernel execution privilege but no compilation is required and so
is potentially less restrictive. TrustDump [33] may be appropriate but minimal
testing has been carried out. Commercial tools such as Cellebrite also claim
to extract memory from Android devices without target modification although
usage is restricted [34].

Internet of Things (IoT) devices also commonly run Linux [35]. However, device
type and Linux variations pose potentially greater challenges than
smartphones. Nevertheless, solutions that support live acquisition from
Android smartwatches, as well as smartphones, have been proposed [36]. IoT
device memory may also be acquired by flashing memory, running Linux dump
commands, or accessing device circuitry [37]. Furthermore, memory access with
commercial tools, such as Cellebrite UFED Physical Analyzer, has also been
demonstrated [38]. As IoT devices frequently communicate with cloud-based
servers, memory acquisition of virtualized machines may present an easier
alternative [35]. Virtualization enables memory access. Virtualization
technologies enable virtual machines to share host computer resources thereby
providing an opportunity to discover cryptographic artefacts in virtual
machine memory from the physical host. This ensures investigations have
reduced the impact on virtual machine operations. Furthermore, software
programs executing on the virtual machine, such as malware, may not detect the
investigations. Examples of tools and libraries that support outsidethe-
machine monitoring include LibVMI [39] together with PyVMI [40] and Volatility
[41], and Rekall [42].

##  3 MemDecrypt Design

MemDecrypt consists of network and data collection, memory analysis, and
decrypt analysis components. Figure 2 illustrates the MemDecrypt activity flow
diagram. Each component is described in the following paragraphs.

Figure 2:  MemDecrypt Activity Flow Diagram

Network and Memory Extract. In MemDecrypt unusual events trigger memory
extracts. This approach is less intrusive than continuous memory monitoring
where the monitoring and analysis activities of the host may impact target
device performance. Furthermore, malware writers script programs to be aware
of monitoring activity, which would probably be more obvious with continuous
monitoring. The triggers approach is also more precise than obtaining memory
snapshots on a polled basis. Polling snapshots may miss malicious activity if
the polling interval is too large, especially when malware uses counter
analysis techniques. The quantity and timing of memory extraction events
depend on the target device, the secure protocol, and the encryption
algorithm. Where memory is classifiable, the read/write memory of the
encryption program is extracted for size minimization, with consequent reduced
impact on target performance and faster subsequent analysis.

Memory analysis. Candidate encryption keys and IVs are identified in the
memory extracts. Although largely protocol specific, there are common
features. In particular, candidate IV locations are discovered first with
approaches that encompass an analysis of memory extracts, network packets or
both network packets and memory extracts. As keys and IVs are cryptographic
artefacts, the distance between their respective memory locations may be small
If program memory extracts are taken when the same activity is being
performed, such as the transmission of outgoing messages, memory blocks
containing IVs change, while other blocks remain static.

Key randomness makes it different from many other types of memory regions. Key
randomness means that the sequence of bits cannot be easily predicted. The
randomness of keys can be evaluated using entropy, a measure of the amount of
information in a key. This paper uses Shannon’s entropy measure for discrete
variables [43] in preference to cryptographically useful alternatives such as
guessing entropy and min-entropy [44] because smaller candidate key sets are
produced:

$H=-\sum_{i=1}^{n}p(i)\log_{2}p(i)$ (1)

where $p(i)$ is the normalized frequency of the $i$th byte in the message i.e.
$p(i)=f(i)/n$. So, segments of high entropy user memory are more likely to
contain the key. In contrast with IVs, keys do not generally change during a
session. So, static, high-entropy contents are candidate encryption keys. This
observation assists in improving memory analysis performance.

Decrypt analysis. Candidate keys and IVs identified in memory analysis are
used in decrypting network packets until a valid key and IV combination has
been found. Decrypt validation uses information derived from specific
encrypted fields. SSH encrypted data blocks are of the following format:

Packet Length (4 bytes) Padding Length (1 byte) Payload (variable bytes)
Padding (variable bytes) MAC

The packet length is the sum of the padding length size, the payload, and
padding fields. So, equation (2) is a good decrypt test for many SSH messages
as $2^{(8*4-21)}$ valid packet length decrypts are possible. The minimum SSH
block size is 21 bytes comprising a packet length of 4 bytes, a padding length
of 1 byte, and the payload and padding which is at least one block. So, the
probability of an incorrect decrypt producing the correct header data is
1-in-4,294,967,275. Reassembly is undertaken when the SSH packet size exceeds
the network packet size. Equation (2) is sound during the authentication,
channel, and sub-service setup stages when SSH packet sizes are generally
small and a modified version is used for reassembled SSH packets. An
additional test evaluates whether the decrypted padding length meets Equation
(3) as required by SSH-TRANS. Correct decrypts are parsed to obtain SSH and
SFTP fields.

$\begin{split}packet\ data\ length\ =\\\ &decrypted\ packet\ length\ +\\\
&size(packet\ length\ field)\ +\\\ &size(MACfield)\end{split}$ (2)
$4<=padding\ length<=255$ (3)

##  4 MemDecrypt Implementation

This paper focuses on SSH decryption using AES-CTR and AES-CBC in virtualized
environments using MemDecrypt. The following paragraphs present implementation
and evaluation details. The framework is implemented on the Xen hypervisor
[45]. Xen’s small trusted computing base makes it potentially less prone to
vulnerabilities than hypervisors with larger footprints. Furthermore, the
LibVMI library (“LibVMI,” n.d.) for Xen enables efficient memory access to
live memory of Windows or Linux virtual machines. As the Xen hypervisor has
minimal functionality a privileged virtual machine (Dom0) manages the
hypervisor and provides network and virtual disk device access to other
virtual machines. Network access for the virtual machines is through a Dom0
virtual software bridge. The MemDecrypt components either all run on, or are
initiated, from Dom0.

The MemDecrypt implementation architecture for virtualized environments is
illustrated in Figure 3. An isolated hypervisor supports two unprivileged
virtual machines, shown in the centre and right of the figure, and one
privileged virtual machine shown on the left. Test client applications execute
on the virtual machine on the right, targeting server applications executing
on the virtual machine, shown in the centre.

Figure 3:  MemDecrypt Virtualization Architecture

###  4.1 Data Collection

For virtualized environments, virtual machine network traffic is inspected by
redirecting each packet to a local queue using an iptables rule and
NetFilterQueue 0.8.1 [46], and analyzing protocol fields using Scapy 2.3 [47].
When unusual activity is detected, the component stores the network packet and
deconstructs the message. Memory is extracted for any 2 outgoing SSH messages
after a _New Keys_ message. Linux memory extraction uses PyVMI and LibVMI
libraries, whereas Windows extraction applies Volatility framework user
plugins.

MemDecrypt obtains useful data from the SSH initialization stage. Client and
server versions, and application if available are obtained from the protocol
version exchange. The encryption algorithm is determined from the “Key
Exchange” messages. Also, if initialization has completed, i.e. the “New Keys”
has been transmitted, user-level read/write program memory extraction is
triggered for two outgoing packets in the network session. Memory extracts are
not required for consecutive packets or to be immediately after the “New Keys”
message.

###  4.2 Memory Analysis

Analysis approaches vary according to encryption mode and operating system.
For AES-CTR, two steps are required to discover candidate IVs and keys in
memory, whereas AES-CBC requires only key discovery. For Windows, discovery is
performed by iteratively analyzing multiple memory files extracted at
different times, whereas, for Linux, a single heap file is analyzed.

For AES-CTR, candidate IVs are discovered first. As IVs increase but are
likely to be located at the same memory address over different extracts,
memory blocks that change is subject to further analysis. If the 16-byte value
at a memory address increments by the number of encrypted blocks in the
previous packet, then the address contents are a candidate IV. Supposing that
value at location $p$ in capture $y$ at the time $a$ is compared with the
value at location $p$ in capture $y$ at time $b$. Then, if the values are IVs
and represented by $IV_{pya}$ and $IV_{pyb}$ respectively, then
$IV_{pyb}=IV_{pya}+n$, where $n$ is the number of AES encrypted network blocks
that have been sent between the time $a$ and $b$ in that session. For example,
if the value of a 16-byte memory block is 123456 and two network packets with,
say, 10 and 5 encrypted blocks are sent and captured, then a value of 123471
at the same position in the later extract identifies a candidate AES-CTR IV.
Algorithm 1 shows the process.

Data: extract folders $fldr_{a}$, $fldr_{b}$ and packets $pkt_{a}$, $pkt_{b}$

Result: Z = candidate IVs

delta := blocks[$pkt_{a}$:$pkt_{b}$];

for  _file $f_{1}$ in $fldr_{a}$_ do

$f_{2}$ = match ($f_{1}$, $fldr_{b}$);

if  _$f_{1}$ <> $f_{2}$_ then

for  _i = 0 to size( $f_{1}$) inc 4_ do

if  _val( $f_{2}$[i:i+16]) - val($f_{1}$[i:i+16]) = delta_ then

Z += $f_{1}$[i:i+16];

end if

end for

end if

end for

Algorithm 1 AES-CTR IV Memory Analysis

To discover AES candidate keys for AES-CTR and AES-CBC, the memory extract
files are analysed. Key segment entropies are calculated for key length
segment sizes. If an entropy exceeds a threshold, the segment is compared with
the equivalent segment in a later extract, and if the segments are identical,
the segment is a candidate encryption key. For example, a 256-bit key length,
a 32-byte memory segment entropy of 4.9, and a 32-byte AES threshold of 4.65
determines the segment to be of interest. An identical match to the segment at
the same location in a later memory extract identifies a candidate key. The
identified candidate IVs and keys provide input to the decrypt analysis stage.
Heuristic testing determined that AES entropy thresholds of 4.65 for 256-bit
keys, 4.0 for 192-bit keys, and 3.4 for 128-bit keys ensured the inclusion of
all keys in candidate sets while minimizing set size.

###  4.3 Decrypt Analysis

The component iterates through each candidate key for each candidate IV until
decrypts are validated. The first ciphertext block is decrypted for each
combination with pycrypto 2.6.1 [48]. For a correct decrypt the first four
plaintext bytes are the packet length and Equation (2) holds. For additional
validation, the decrypted padding length is checked with Equation (3). With a
valid key and IVs, MemDecrypt decrypts each block and deconstructs the SSH
plaintext stream. For SSH authorization requests, the ’password’ type
plaintext yields the remote user credentials and for SSH connection requests,
the channel type, and channel request decrypts. For SFTP, all plaintext is
produced including _initialization_ , _file attribute_ , _file open_ , _write_
and _close_ message types fields. All plaintext is written to file for
evaluation.

###  4.4 Testbed

The physical environment is a Core 2 Duo Dell personal computer with 40 GB of
disk storage and 3 GB of RAM. It hosts the hypervisor, a Dom0 privileged
virtual machine, an untrusted Windows virtual machine, and an untrusted Ubuntu
virtual machine. The hypervisor is Xen Project 4.4.1 and the Dom0 hypervisor
console is Debian release 3.16.0-4-amd64 version 1.

Tests run on Windows client and Linux server virtual machines. One client runs
a standard Windows 7 SP1 operating system with 512 MB of allocated memory and
30 GB of disk space. Another client runs a Windows 10 (10.0.16299) operating
system with 2 GB of memory and 40 GB of disk. Windows operating systems
support a number of SSH clients [49]. The selected PuTTY suite [23] is widely
used [49] so may be used by suspect actors. However, other SSH client
applications should produce similar results. The untrusted Linux server
virtual machine runs an Ubuntu 14.04 build (“Trusty”) with 512 MB of allocated
memory and 4 GB of disk storage. SSH server functionality is provided by
openssh-server. To remove unnecessary communications with external agents, the
_dnsmasq_ package is installed and configured to respond to DNS requests with
the server virtual machine IP address.

##  5 Evaluation

MemDecrypt is evaluated by running a sequence of experiments. The experimental
set-up is described followed by the presentation and review of results.
Possible countermeasures to MemDecrypt results are discussed.

###  5.1 Experimental Set-up

Experiments are performed with variable file sizes, key lengths, modes of
operation, operating systems, and operating system versions. In each instance,
the ’pscp’ program is executed from the Windows command line using requests of
the form:

pscp -P nnnn filename name@ipaddress:/home/name

where nnnn is the target port, filename is the file being transmitted, name is
a user account on the target Ubuntu server, ipaddress is the target server IP
address and /home/name is the Ubuntu server target folder for the transmitted
file. An Ubuntu service is started from the bash command line to listen to
client SSH messages with requests of the form:

/usr/sbin/sshd -f /root/sshd_config -d -p nnnn

where nnnn is the service receiving port number and sshd_config contains
configuration details such as encryption algorithms supported by the server.

Sets of experiments investigate decrypting SSH traffic encrypted with AES
under different conditions. One set evaluates decrypt effectiveness for
Windows 7 and Windows 10 clients. A second set evaluates the effectiveness of
128-bit, 192-bit and 256-bit keys on Windows 10 clients in AES-CTR mode. A
third set evaluates MemDecrypt effectiveness with 256-bit keys in AES-CBC and
AES-CTR modes on Windows 10 clients. To evaluate file invariability, a fourth
set uploads 30 files in text, pdf, Excel, and executable formats between 1 KB
and 500 KB for Windows clients in AES-CTR mode using 256-bit keys. Experiments
also assess decrypt effectiveness with Ubuntu server for AES-CBC and AES-CTR
with 256-bit keys.

###  5.2 Test Results

In each experiment, encryption keys, and for AES-CTR initialization vectors,
were discovered and valid plaintext produced for all SSH and SFTP fields. For
example, with a client command of ’pscp -P 2222 plaintext.txt
peter@192.168.137.85:/home/peter’ and plaintext.txt of ’An outcropping of
limestone beside the path that had a silhouette…’, the interesting decrypted
fields are depicted in Figure 4. MemDecrypt also produces other SSH fields
such as request identifiers, and file offsets. As observed earlier, the
probability of an incorrect combination generating a packet length meeting
Equation (2) is 0.00000002% (1 in 4,294,967,275). MemDecrypt decrypts SSH
traffic with a high degree of certainty.

Figure 4: SSH Decrypt Output

Analysis durations for producing correct plaintext determines MemDecrypt’s
usefulness. For example, if plaintext is produced during the network session
MemDecrypt can assist in the prevention of further malicious activity, perhaps
by dropping packets or hijacking the session.

The first experiment compares the relative performance of Windows 7 and
Windows 10 client virtual machines. For AES-CTR, two memory extracts are
required for the analysis whereas, for CBC, one extract suffices. Memory
analysis typically executes for approximately nine seconds for Windows 7
clients and 16 seconds for Windows 10 clients with a maximum of 25.1 seconds.
Decrypt analysis durations varied between 0.2 and 34.1 seconds averaging at
4.5 seconds. The variance is linked to the candidate IV set size and the
ordinality of the correct IV within the file set.

The second experiment compares analysis time durations for different CTR key
sizes on Windows 10 clients. Shorter key lengths require lower entropy
thresholds, so more candidate encryption keys are discovered in-memory
analysis. Figure 5 illustrates a typical distribution of 32-byte entropy
segments in read/write memory. This maps the count of memory segments
exceeding an entropy with an entropy levels so that for example whereas out of
264,813 segments exceeding 0.0 entropy, 188,602 (i.e. 72.1%) exceed 2.0, 2,628
(i.e. 0.99%) exceed 4.5. So, for example, in one test sequence memory analysis
yielded candidate key set sizes of 272 for 256-bit key lengths, 1123 for
192-bit key lengths, and 5658 for 128-bit key lengths. With these set sizes,
decrypt analysis durations are longer for shorter key lengths as illustrated
in Figure 6.

Figure 5: Typical Memory Segment Entropy Distribution

The third experiment compares analysis time durations on Windows 10 clients
for 256-bit key sizes in AES-CTR and AES-CBC. The CBC memory analysis takes
approximately 16 seconds which is similar to CTR. However, the CBC decrypt
analysis duration is faster with a minimum of 0.07 seconds as iterating
through potential IVs is not required.

Figure 6:  Key Length Analysis Durations

For experiments accessing Ubuntu server memory with the default encryption
algorithm, i.e. AES with 256-bit key length and CTR mode, all client and
server packets are correctly decrypted. The data collection component obtains
process lists and extracts process heap from the Ubuntu virtual machine in 0.3
seconds. Memory analysis finds approximately 320 keys and 3 initialization
vectors in 6 seconds, and decrypt analysis decrypts the session successfully
in 37 seconds.

MemDecrypt performance may suffice when extracts are obtained for Windows
clients or Ubuntu servers. Nevertheless, strategies to enhance performance
include improving memory extraction for Windows clients, pre-testing with
known SSH client and server applications, pipelining, multi-threading, and
implementing in a low-level language instead of Python. A custom extract
engine using PyVMI and LibVMI libraries to replace Volatility plugins improves
Windows memory extraction performance. Pre-testing SSH client and server
applications may determine the distance between key and IV memory locations.

Cryptographic libraries generally request memory to hold crypto data
structures (’malloc’) when algorithms are agreed which occurs after the
handshake so data is usually on the heap. The data structures can include
fields such as encryption/decryption flag, key size, keys etc so for an
algorithm, AES-CTR with 256 bit keys, the data structures may be invariant.
For example, with PuTTY ’pscp’, distances are 968 bytes for 256-bit and
192-bit keys and 728 bytes for 128-bit-keys and are invariant with operating
system version or transmitted file size. Where the distance is known, and the
program identified from the SSH version message, memory analysis and decrypt
analysis components take one second. Multi-threading supports simultaneous
analysis of multiple files and decrypts while pipelining between components
enables analysis to terminate when the correct plaintext is obtained.

So, MemDecrypt decrypts SSH sessions with high probability independent of file
size, operating system type or version, key length, or mode. Furthermore, with
SSH application pre-testing, analysis and decrypt decryption completes in 1
second. With unknown SSH applications, the plaintext is produced in under 60
seconds for 192-bit and 256-bit keys. Although in experiments, MemDecrypt
decrypts sessions with exfiltrated files of 100 bytes, the risk exists that
extracts are not acquired in terse SSH sessions. The risk might be mitigated
by pausing the virtual machine. Decrypting sessions with SSH key rotation [50]
is not currently implemented but the planned MemDecrypt approach is
considering each rotation as a separate session with its own candidate keys
and IVs.

###  5.3 Countermeasures

Countermeasures may prevent or delay MemDecrypt discovery of cryptographic
artefacts. Invalid assumptions can invalidate the methodology. Candidate
encryption keys are assumed to be high entropy, static for a network session,
and in the same memory location. For entropy, less randomness, i.e. lower
entropy, makes key regions less evident but key unpredictability is an
essential requirement. For key staticity, MemDecrypt requires two extractions
for AES-CTR, key changes would be required between each outgoing packet which
could cause excessive transmission delays. Key location changes could delay
decryption. However, tests on a Linux heap extract produced delays of less
than 0.5 seconds. MemDecrypt assumes candidate AES-CTR IVs are located at the
same memory locations in each extract and values to increment by the sum of
payload blocks in the previous packets. As with keys, tests where IV memory
addresses changed induced delay of 0.5 seconds. As a result, the measure may
not suffice. AES-CTR IVs increments make them detectable when stored _in the
clear_ in memory. Another delaying measure is encrypting artefacts with an
additional key. However, this key may be discoverable, and furthermore, the
additional encryption and decryption for each packet, or block, may have an
unacceptable performance impact. Obfuscation the artefacts may be more
effective. For example, splitting key and IV strings and interpolating
variable data between splits will limit MemDecrypt performance, and possibly
effectiveness. This technique is faster and less detectable than an additional
encryption layer. A more effective counter-measure is preventing memory access
to artefacts. For example, Intel [51] and AMD [52] may develop virtual machine
encryption where encryption keys are absent from virtual machine memory.
Although this can offer privacy, malicious behaviour is then hidden so
administrators may seek to disable the feature.

##  6 Conclusions and Future Work

The MemDecrypt framework rapidly discovers cryptographic artefacts and
decrypts SSH communications in virtualized environments. This can assist in
detecting, and preventing insider attackers from extracting and encrypting
confidential information to external locations. MemDecrypt can be extended to
technologies where memory acquisition of live secure sessions is enabled.
Decrypting SSH sessions may be illegal without approval so cryptographic
artefact sets could be retained with the associated network traffic for
decryption once approval is obtained. High performance makes the framework
applicable so future work should apply multithreading and pipelining
techniques before being extended to other non-virtualized use cases, secure
protocols, encryption algorithms, and malware that use encrypted
communications channels.

## References

  * [1] S. Khandelwal, ““How Dutch Police Decrypted BlackBerry PGP Messages For Criminal Investigation,” The Hacker News,” https://thehackernews.com/2017/03/decrypt-pgp-encryption.html, 2017, [Online; accessed 29-Jan-2019].
  * [2] A. Duncan, S. Creese, and M. Goldsmith, “An overview of insider attacks in cloud computing,” _Concurrency and Computation: Practice and Experience_ , vol. 27, no. 12, pp. 2964–2981, 2015.
  * [3] N. Ferguson, B. Schneier, and T. Kohno, _Cryptography engineering: design principles and practical applications_. John Wiley & Sons, 2011.
  * [4] N. Zhang, R. Zhang, K. Sun, W. Lou, Y. T. Hou, and S. Jajodia, “Memory forensic challenges under misused architectural features,” _IEEE Transactions on Information Forensics and Security_ , vol. 13, no. 9, pp. 2345–2358, 2018.
  * [5] J. A. Halderman, S. D. Schoen, N. Heninger, W. Clarkson, W. Paul, J. A. Calandrino, A. J. Feldman, J. Appelbaum, and E. W. Felten, “Lest we remember: cold-boot attacks on encryption keys,” _Communications of the ACM_ , vol. 52, no. 5, pp. 91–98, 2009.
  * [6] C. Maartmann-Moe, S. E. Thorkildsen, and A. Årnes, “The persistence of memory: Forensic identification and extraction of cryptographic keys,” _digital investigation_ , vol. 6, pp. S132–S140, 2009.
  * [7] S. Sentanoe, B. Taubmann, and H. P. Reiser, “Virtual machine introspection based ssh honeypot,” in _Proceedings of the 4th Workshop on Security in Highly Connected IT Systems_. ACM, 2017, pp. 13–18.
  * [8] B. Taubmann, C. Frädrich, D. Dusold, and H. P. Reiser, “Tlskex: Harnessing virtual machine introspection for decrypting tls communication,” _Digital Investigation_ , vol. 16, pp. S114–S123, 2016.
  * [9] Y. Nakano, A. Basu, S. Kiyomoto, and Y. Miyake, “Key extraction attack using statistical analysis of memory dump data,” in _International Conference on Risks and Security of Internet and Systems_. Springer, 2014, pp. 239–246.
  * [10] B. Hay and K. Nance, “Circumventing cryptography in virtualized environments,” in _Malicious and Unwanted Software (MALWARE), 2012 7th International Conference on_. IEEE, 2012, pp. 32–38.
  * [11] D. Puthal, S. Nepal, R. Ranjan, and J. Chen, “A dynamic prime number based efficient security mechanism for big sensing data streams,” _Journal of Computer and System Sciences_ , vol. 83, no. 1, pp. 22–42, 2017.
  * [12] Y. Nir and A. Langley, “Chacha20 and poly1305 for ietf protocols,” Tech. Rep., 2018.
  * [13] Ianix, ““ChaCha Usage & Deployment,” Ianix,” https://ianix.com, 2019, [Online; accessed 29-Jan-2019].
  * [14] T. Aura, “Strategies against replay attacks,” in _Computer Security Foundations Workshop, 1997. Proceedings., 10th_. IEEE, 1997, pp. 59–68.
  * [15] P. Rogaway, “Evaluation of some blockcipher modes of operation,” _Cryptography Research and Evaluation Committees (CRYPTREC) for the Government of Japan_ , 2011.
  * [16] M. Bellare, T. Kohno, and C. Namprempre, “The secure shell (ssh) transport layer encryption modes,” Tech. Rep., 2005.
  * [17] M. Dworkin, “Recommendation for block cipher modes of operation. methods and techniques,” NATIONAL INST OF STANDARDS AND TECHNOLOGY GAITHERSBURG MD COMPUTER SECURITY DIV, Tech. Rep., 2001.
  * [18] T. Ylonen and C. Lonvick, “The secure shell (ssh) protocol architecture,” Tech. Rep., 2005.
  * [19] ——, “The secure shell (ssh) transport layer protocol,” Tech. Rep., 2005.
  * [20] ——, “The secure shell (ssh) authentication protocol,” Tech. Rep., 2005.
  * [21] ——, “The secure shell (ssh) connection protocol,” Tech. Rep., 2005.
  * [22] D. J. Barrett, D. J. Barrett, R. E. Silverman, and R. Silverman, _SSH, the Secure Shell: the definitive guide_. " O’Reilly Media, Inc.", 2001.
  * [23] S. Tatham, ““PuTTY”,” https://www.chiark.greenend.org.uk/~sgtatham/putty/latest.html, 2019, [Online; accessed 29-Jan-2019].
  * [24] J. Galbraith and O. Saarenmaa, “Ssh file transfer protocol,” _Work in Progress_ , 2006.
  * [25] S. Vömel and J. Stüttgen, “An evaluation platform for forensic memory acquisition software,” _Digital Investigation_ , vol. 10, pp. S30–S40, 2013\.
  * [26] S. Vömel and F. C. Freiling, “A survey of main memory acquisition and analysis techniques for the windows operating system,” _Digital Investigation_ , vol. 8, no. 1, pp. 3–22, 2011.
  * [27] AccessData, “"FTK Imager",” http://marketing.accessdata.com/ftkimager4.2.0, 2018, [Online; accessed 29-Jan-2019].
  * [28] "FireEye", ““Memoryze”,” https://www.fireeye.com/services/freeware.html, 2018, [Online; accessed 29-Jan-2019].
  * [29] M. Cohen", ““WinPMEM”,” https://github.com/google/rekall/tree/master/tools/windows/winpmem, 2018, [Online; accessed 29-Jan-2019].
  * [30] F. Freiling, T. Groß, T. Latzo, T. Müller, and R. Palutke, “Advances in forensic data acquisition,” _IEEE Design & Test_, vol. 35, no. 5, pp. 63–74, 2018.
  * [31] J. Sylve", ““LiME Linux Memory Extractor”,” https://github.com/504ensicslabs/lime, 2019, [Online; accessed 29-Jan-2019].
  * [32] H. Yang, J. Zhuge, H. Liu, and W. Liu, “A tool for volatile memory acquisition from android devices,” in _IFIP International Conference on Digital Forensics_. Springer, 2016, pp. 365–378.
  * [33] H. Sun, K. Sun, Y. Wang, and J. Jing, “Reliable and trustworthy memory acquisition on smartphones,” _IEEE Transactions on Information Forensics and Security_ , vol. 10, no. 12, pp. 2547–2561, 2015.
  * [34] "Cellebrite", ““Advanced Extraction Service”,” https://www.cellebrite.com/en/services/advanced-extraction-services, 2018, [Online; accessed 29-Jan-2019].
  * [35] A. Case and G. G. Richard III, “Memory forensics: The path forward,” _Digital Investigation_ , vol. 20, pp. 23–33, 2017.
  * [36] S. J. Yang, J. H. Choi, K. B. Kim, R. Bhatia, B. Saltaformaggio, and D. Xu, “Live acquisition of main memory data from android smartphones and smartwatches,” _Digital Investigation_ , vol. 23, pp. 50–62, 2017.
  * [37] B. P. Kondapally", ““What is IoT Forensics and How is it Different from Digital Forensics?”,” https://securitycommunity.tcs.com/infosecsoapbox/articles/2018/02/27/what-iot-forensics-and-how-it-different-digital-forensic, 2018, [Online; accessed 29-Jan-2019].
  * [38] S. Alabdulsalam, K. Schaefer, T. Kechadi, and N.-A. Le-Khac, “Internet of things forensics: Challenges and case study,” _arXiv preprint arXiv:1801.10391_ , 2018.
  * [39] "LibVMI Project", ““LibVMI”,” http://libvmi.com/, 2013, [Online; accessed 29-Jan-2019].
  * [40] B. D. Payne", ““pyvmi – A Python adapter for LibVMI”,” https://github.com/libvmi/libvmi/tree/master/tools/pyvmi, 2013, [Online; accessed 29-Jan-2019].
  * [41] "The Volatility Foundation", ““The Volatility Foundation - Open Source Memory Forensics”,” http://www.volatilityfoundation.org/, 2017, [Online; accessed 29-Jan-2019].
  * [42] M. Cohen", “Rekall Memory Forensic Framework”,” http://www.rekall-forensic.com/, 2017, [Online; accessed 29-Jan-2019].
  * [43] C. E. Shannon, “A mathematical theory of communication,” _Bell system technical journal_ , vol. 27, no. 3, pp. 379–423, 1948.
  * [44] C. Cachin, “Entropy measures and unconditional security in cryptography,” Ph.D. dissertation, ETH Zurich, 1997.
  * [45] "Xen Project", “Xen Project Software Overview”,” https://wiki.xenproject.org, 2018, [Online; accessed 27-Nov-2018].
  * [46] Kerkhoff Technologies, “NetFilterQueue,” https://pypi.org/project/NetfilterQueue, 2017, [Online; accessed 29-Jan-2019].
  * [47] P. Biondi", “Scapy”,” https://scapy.readthedocs.io/en/latest/, 2017, [Online; accessed 29-Aug-2018].
  * [48] D. C. Litzenberger", “Python Cryptography Toolkit (pycrypto)”,” http://www.rekall-forensic.com/, 2013, [Online; accessed 29-Jan-2018].
  * [49] "SSH Communications", “SSH Client for Windows - Comparison”,” https://www.ssh.com/ssh/client, 2018, [Online; accessed 29-Jan-2018].
  * [50] T. Ylonen, P. Turner, K. Scarfone, and M. Souppaya, “Security of interactive and automated access management using secure shell (ssh),” Tech. Rep., 2015.
  * [51] B. Patel", “Intel Releases New Technology Specification for Memory Encryption”,” https://software.intel.com/en-us/blogs/2017/12/22/intel-releases-new-technology-specification-for-memory-encryptio, 2017, [Online; accessed 15-Oct-2018].
  * [52] S. Nichols", “Epyc fail? We can defeat AMD’s virtual machine encryption, say boffins,”,” https://www.theregister.co.uk, 2017, [Online; accessed 15-Oct-2018].


11institutetext: PSL, Université Paris-Dauphine, LAMSADE, CNRS, UMR 7243,
Paris, France 22institutetext: Wavestone, Paris, France

# Training compact deep learning models for video classification using
circulant matrices

Alexandre Araujo 11 2 2 Benjamin Negrevergne 11 Yann Chevaleyre 11 Jamal Atif
11

###### Abstract

In real world scenarios, model accuracy is hardly the only factor to consider.
Large models consume more memory and are computationally more intensive, which
makes them difficult to train and to deploy, especially on mobile devices. In
this paper, we build on recent results at the crossroads of Linear Algebra and
Deep Learning which demonstrate how imposing a structure on large weight
matrices can be used to reduce the size of the model. We propose very compact
models for video classification based on state-of-the-art network
architectures such as Deep Bag-of-Frames, NetVLAD and NetFisherVectors. We
then conduct thorough experiments using the large YouTube-8M video
classification dataset. As we will show, the circulant DBoF embedding achieves
an excellent trade-off between size and accuracy.

###### Keywords:

Deep Learning Computer Vision Structured Matrices Circulant Matrices

##  1 Introduction

The top-3 most accurate approaches proposed during the first YouTube-8M
111https://www.kaggle.com/c/youtube8m video classification challenge were all
ensembles models. The ensembles typically combined models based on a variety
of deep learning architectures such as NetVLAD, Deep Bag-of-Frames (DBoF),
NetFisherVectors (NetFV) and Long-Short Term Memory (LSTM), leading to a large
aggregation of models (25 distinct models have been used by the first
contestant [24], 74 by the second [33] and 57 by the third [20]). Ensembles
are accurate, but they are not ideal: their size makes them difficult to
maintain and deploy, especially on mobile devices.

A common approach to compress large models into smaller ones is to use model
distillation [13]. Model distillation is a two steps training procedure:
first, a large model (or an ensemble model) is trained to be as accurate as
possible. Then, a second compact model is trained to approximate the first
one, while satisfying the given size constraints. The success of model
distillation and other model compression techniques begs an important
question: is it possible to devise models that are compact by nature while
exhibiting the same generalization properties as large ones?

In linear algebra, it is common to exploit structural properties of matrices
to reduce the memory footprint of an algorithm. Cheng et al. [6] have used
this principle in the context of deep neural networks to design compact
network architectures by imposing a structure on weight matrices of fully
connected layers. They were able to replace large, unstructured weight
matrices with structured circulant matrices without significantly impacting
the accuracy. And because a n-by-n circulant matrix is fully determined by a
vector of dimension $n$, they were able to train a neural network using only a
fraction of the memory required to train the original network.

Inspired by this result, we designed several compact neural network
architectures for video classification based on standard video architectures
such as NetVLAD, DBoF, NetFV and we evaluated them on the large YouTube-8M
dataset. However, instead of adopting the structure used by [6] (initially
proposed by [32]), we decomposed weight matrices into products of diagonal and
circulant matrices (as in [29]). In contrast with [32] which has been proved
to approximate distance preserving projections, this structure can approximate
any transformation (at the cost of a larger number of weights). As we will
show, this approach exhibits good results on the video classification task at
hand.

In this paper, we bring the following contributions:

  * •

We define a compact architecture for video classification based on circulant
matrices. As a side contribution, we also propose a new pooling technique
which improves the Deep Bag-of-Frames embedding.

  * •

We conduct thorough experimentations to identify the layers that are less
impacted by the use of circulant matrices and we fine-tune our architectures
to achieve the best trade-off between size and accuracy.

  * •

We combine several architectures into a single model to achieve a new model
trained-end-to-end that can benefit from architectural diversity (as in
ensembles).

  * •

We train all our models on the Youtube-8M dataset with the 1GB model size
constraint imposed by the 2nd YouTube-8M Video Understanding
Challenge222https://www.kaggle.com/c/youtube8m-2018, and compare the different
models in terms of size vs. accuracy ratio. Our experiments demonstrate that
the best trade-off between size and accuracy is obtained using circulant DBoF
embedding layer.

##  2 Related Works

Classification of unlabeled videos streams is one of the challenging tasks for
machine learning algorithms. Research in this field has been stimulated by the
recent release of several large annotated video datasets such as Sports-1M
[19], FCVID [17] or the YouTube-8M [2] dataset.

The naive approach to achieve video classification is to perform frame-by-
frame image recognition, and to average the results before the classification
step. However, it has been shown in [2, 24] that better results can be
obtained by building features across different frames and several deep
learning architectures have been designed to learn embeddings for sets of
frames (and not single frames). For example Deep Bag-of-Frames (DBoF) [2],
NetVLAD [3] or architectures based on Fisher Vectors [27].

The DBoF embedding layer, proposed in [2] processes videos in two steps.
First, a learned transformation projects all the frames together into a high
dimensional space. Then, a max (or average) pooling operation aggregates all
the embedded frames into a single discriminative vector representation of the
video. The NetVLAD [3] embedding layer is built on VLAD [16], a technique that
aggregates a large number of local frame descriptors into a compact
representation using a codebook of visual words. In NetVlad, the codebook is
directly learned end-to-end during training. Finally, NetFisherVector (NetFV)
is inspired by [27] and uses first and second-order statistics as video
descriptors also gathered in a codebook. The technique can benefit from deep
learning by using a deep neural network to learn the codebook [24].

All the architectures mentioned above can be used to build video features in
the sense of features that span across several frames, but they are not
designed to exploit the sequential nature of videos and capture motion. In
order to learn truly spatio-temporal features and account for motion in
videos, several researchers have looked into recurrent neural networks (e.g.
LSTM [36, 20]) and 3D convolutions [19] (in space and time). However, these
approaches do not outperform non-sequential models, and the single best model
proposed in [24] (winner of the first YouTube-8M competition) is based on
NetVLAD [3].

####

The 2nd YouTube-8M Video Understanding Challenge includes a constraint on the
model size and many competitors have been looking into building efficient
memory models with high accuracy. There are two kinds of techniques to reduce
the memory required for training and/or inference in neural networks. The
first kind aims at compressing an existing neural network into a smaller one,
(thus it only impacts the size of the model at inference time). The second one
aims at constructing models that are compact by design.

To compress an existing network several researchers have investigated
techniques to prune parameters that are redundant (e.g. [9, 12, 21]).
Redundant parameters can be omitted from the model without significantly
changing the accuracy. It is also possible to use sparsity regularizers during
training, to be able to compress the model after the training using efficient
sparse matrix representations (e.g. [7, 9, 22]). Building on the observation
that weight matrices are often redundant, another line of research has
proposed to use matrix factorization [10, 15, 35] in order to decompose large
weight matrices into factors of smaller matrices before inference.

An important idea in model compression, proposed by Buciluǎ et al. ([4]), is
based on the observation that the model used for training is not required to
be the same as the one used for inference. First, a large complex model is
trained using all the available data and resources to be as accurate as
possible, then a smaller and more compact model is trained to approximate the
first model. The technique which was later specialized for deep learning
models by [13] (a.k.a. model distillation) is often used to compress large
ensemble models into compact single deep learning models.

Instead of compressing the model after the training step, one can try to
design models that are compact by nature (without compromising the
generalization properties of the network). The benefit of this approach is
that it reduces memory usage required during both training and inference. As a
consequence, users can train models that are virtually larger using less time
and less computing resources. They also save the trouble of training two
models instead of one as it is done with distillation. These techniques
generally work by constraining the weight representation, either at the level
of individual weights (e.g. using floating variable with limited precision
[11], quantization [8, 23, 28]) or at the level of the whole matrix, (e.g.
using weight hashing techniques [5]) which can achieve better compression
ratio. However in practice, hashing techniques are difficult to use because of
their irregular memory access patterns which makes them inadequate for GPU-
execution.

Another way of constraining the weight representation is to impose a structure
on weight matrices (e.g. using circulant matrices [6, 30], Vandermonde [30] or
Fastfood transforms [34]). In this domain, Cheng et al. [6] have proposed to
replace two fully connected layers of AlexNet by circulant and diagonal
matrices where the circulant matrix is learned by a gradient based
optimization algorithm and the diagonal matrix entries are sampled at random
in {-1, 1}. The size of the model is reduced by a factor of 10 without loss in
accuracy333In network such as AlexNet, the last 3 fully connected layers use
58M out of the 62M total trainable parameters ($>90\%$ of the total number of
parameters).. Most of the time the resulting algorithms are easy to execute on
GPU-devices.

##  3 Preliminaries on circulant matrices

In this paper, we use circulant matrices to build compact deep neural
networks. A n-by-n circulant matrix $C$ is a matrix where each row is a cyclic
right shift of the previous one as illustrated below.

$C=circ(c)=\left[\begin{array}[]{ccccc}c_{0}&c_{n-1}&c_{n-2}&\dots&c_{1}\\\
c_{1}&c_{0}&c_{n-1}&&c_{2}\\\ c_{2}&c_{1}&c_{0}&&c_{3}\\\
\vdots&&&\ddots&\vdots\\\
c_{n-1}&c_{n-2}&c_{n-3}&&\phantom{0}c_{0}\phantom{0}\end{array}\right]$

Because the circulant matrix $C\in\mathbb{R}^{n\times n}$ is fully determined
by the vector $c\in\mathbb{R}^{n}$, the matrix $C$ can be compactly
represented in memory using only $n$ real values instead of $n^{2}$.

An additional benefit of circulant matrices, is that they are computationally
efficient, especially on GPU devices. Multiplying a circulant matrix $C$ by a
vector $x$ is equivalent to a circular convolution between $c$ and $x$
(denoted $c\star x$). Furthermore, the circular convolution can be computed in
the Fourier domain as follows.

$Cx\quad=\quad c\star
x\quad=\quad{\mathcal{F}}^{-1}\left({\mathcal{F}}(c)\times{\mathcal{F}}(x)\right)$

where ${\mathcal{F}}$ is the Fourier transform. Because this operation can be
simplified to a simple element wise vector multiplication, the matrix
multiplication $Cx$ can be computed in $O(n\log n)$ instead of $O(n^{2})$.

Among the many applications of circulant matrices, matrix decomposition is one
of the interest. In particular, Schmid et al. have shown in [26, 29], that any
complex matrix $A\in\mathbb{C}^{n\times n}$ can be decomposed into the product
of diagonal and circulant matrices, as follows:

$A=D^{(1)}C^{(1)}D^{(2)}C^{(2)}\dots
D^{(m)}C^{(m)}=\prod_{i=1}^{m}D^{(i)}C^{(i)}$ (1)

Later in [14], Huhtanen and Perämäki have demonstrated that choosing $m=n$ is
sufficient to decompose any complex matrix $A\in\mathbb{C}^{n\times n}$. By
[29], the result in Equation 1 also holds for a real matrix
$A\in\mathbb{R}^{n\times n}$, but the proof yields a much bigger value of $m$.
However, the construction of [29] is far from optimal and it is likely that
most real matrices can be decomposed into a reasonable number of factors. The
authors of [25] made this conjecture, and they have leveraged the
decomposition described in Equation 1 in order to implement compact fully
connected layers.

##  4 Compact video classification architecture using circulant matrices

Building on the decomposition presented in the previous section and the
previous results obtained in [25], we now introduce a compact neural network
architecture for video classification where dense matrices have been replaced
by products of circulant and diagonal matrices.

###  4.1 Base Model

We demonstrate the benefit of circulant matrices using a base model which has
been proposed by [24]. This architecture can be decomposed into three blocks
of layers, as illustrated in Figure 1.

EmbeddingDim ReductionClassificationVideoAudioFCFCconcatMoE Context Gating
Figure 1: This figure shows the architecture used for the experiences. The
network samples at random video and audio frames from the input. The sample
goes through an embedding layer and is reduced with a Fully Connected layer.
The results are then concatenated and classified with a Mixture-of-Experts and
Context Gating layer.

The first block of layers, composed of the Deep Bag-of-Frames embedding, is
meant to process audio and video frames independently. The DBoF layer computes
two embeddings: one for the audio and one for the video. In the next
paragraph, we will only focus on describing the video embedding (The audio
embedding is computed in a very similar way).

We represent a video $V$ as a set of $m$ frames $\\{v_{1},\ldots,v_{m}\\}$
where each frame $v_{i}\in\mathbb{R}^{k}$ is a vector of visual features
extracted from the frame image. In the context of the YouTube-8M competition,
each $v_{i}$ is a vector of 1024 visual features extracted using the last
fully connected layer of an Inception network trained on ImageNet. The DBoF
layer then embeds a video $V$ into a vector $v^{\prime}$ drawn from a $p$
dimensional vector space as follows:

$v^{\prime}=\max\left\\{Wv_{i}\mid v_{i}\in V\right\\}$

where $W$ is a matrix in $\mathbb{R}^{p\times k}$ (learned) and max is the
element-wise maximum operator. We typically choose $p>k$, (e.g. $p=8192$).
Note that because this formulation is framed in term of sets, it can process
videos of different lengths (i.e., a different value of $m$).

A second block of layers reduces the dimensionality of each embedding layer
(audio and video), and merges the result into a single vector by using a
simple concatenation operation. We chose to reduce the dimensionality of each
embedding layer separately before the concatenation operation to avoid the
concatenation of two high dimensional vectors.

Finally, the classification block uses a combination of Mixtures-of-Experts
(MoE) and Context Gating to calculate the final probabilities. The Mixtures-
of-Experts layer introduced in [18] and proposed for video classification in
[2] is used to predict each label independently. It consists of a gating and
experts networks which are concurrently learned. The gating network learns
which experts to use for each label and the experts layers learn how to
classify each label. The context gating operation was introduced in [24] and
captures dependencies among features and re-weight probabilities based on the
correlation of the labels. For example, it can capture the correlation of the
labels ski and snow and re-adjust the probabilities accordingly.

Table 1 shows the shapes of the layers as well as the shapes of the weight
matrices.

Layer |  Layer Size |  Activation shape |  Weight matrix shape |  #Weights
---|---|---|---|---
Video DBoF |  8192 |  (-1, 150, 1024) |  (1024, 8192) |  8 388 608
Audio DBoF |  4096 |  (-1, 150, 128) |  (128, 4096) |  524 288
Video FC |  512 |  (-1, 8192) |  (8192, 512) |  4 194 304
Audio FC |  512 |  (-1, 4096) |  (4096, 512) |  2 097 152
Concat |  - |  (-1, 1024) |  - |  -
MoE Gating |  3 |  (-1, 1024) |  (1024, 19310) |  19 773 440
MoE Experts |  2 |  (-1, 1024) |  (1024, 15448) |  15 818 752
Context Gating |  - |  (-1, 3862) |  (3862, 3862) |  14 915 044

Table 1: This table shows the architecture of our base model with a DBoF
Embedding and 150 frames sampled from the input. For more clarity, weights
from batch normalization layers have been ignored. The $-1$ in the activation
shapes corresponds to the batch size. The size of the MoE layers corresponds
to the number of mixtures used.

###  4.2 Robust Deep Bag-of-Frames pooling method

We propose a technique to extract more performance from the base model with
DBoF embedding. The maximum pooling is sensitive to outliers and noise whereas
the average pooling is more robust. We propose a method which consists in
taking several samples of frames, applying the upsampling followed by the
maximum pooling to these samples, and then averaging over all samples. More
formally, assume a video contains $m$ frames
$v_{1},\ldots,v_{m}\in\mathbb{R}^{1024}$. We first draw $n$ random samples
$S_{1}\ldots S_{n}$ of size $k$ from the set
$\left\\{v_{1},\ldots,v_{m}\right\\}$. The output of the robust-DBoF layer is:

$\frac{1}{n}\sum_{i=1}^{n}\max\left\\{v\times W:v\in S_{i}\right\\}$

Depending on $n$ and $k$, this pooling method is a tradeoff between the max
pooling and the average pooling. Thus, it is more robust to noise, as will be
shown in the experiments section.

###  4.3 Compact representation of the base model

In order to train this model in a compact form we build upon the work of [6]
and use a more general framework presented by Equation 1. The fully connected
layers are then represented as follows:

$h(x)=\phi\left(\left[\prod_{i=1}^{m}D^{(i)}C^{(i)}\right]x+b\right)$

where the parameters of each matrix $D^{(i)}$ and $C^{(i)}$ are trained using
a gradient based optimization algorithm, and $m$ defines the number of
factors. Increasing the value of $m$ increases the number of trainable
parameters and therefore the modeling capabilities of the layer. In our
experiments, we chose the number of factors $m$ empirically to achieve the
best trade-off between model size and accuracy.

To measure the impact of the size of the model and its accuracy, we represent
layers in their compact form independently. Given that circulant and diagonal
matrices are square, we use concatenation and slicing to achieve the desired
dimension. As such, with $m=1$, the weight matrix (1024, 8192) of the video
embedding is represented by a concatenation of 8 DC matrices and the weight
matrix of size (8192, 512) is represented by a single DC matrix with shape
(8192, 8192) and the resulting output is sliced at the 512 dimension. We
denote layers in their classic form as “Dense” and layers represented with
circulant and diagonal factors as “Compact”.

###  4.4 Leveraging architectural diversity

In order to benefit from architectural diversity, we also devise a single
model architecture that combines different types of embedding layers. As we
can see in Figure 2, video and audio frames are processed by several embedding
layers before being reduced by a series of compact fully connected layers. The
output of the compact fully connected layers are then averaged, concatenated
and fed into the final classification block. Figure 7 shows the result of
different models given the number of parameters. The use of circulant matrices
allow us to fit this model in GPU memory. For example, the diversity model
with a NetVLAD embedding (cluster size of 256) and NetFV embedding (cluster
size of 128) has 160 millions parameters (600 Mo) in the compact version and
728M (2.7 Go) in the dense version.

VideoDBoFNetVLADNetFVFCFCFCAudioDBoFNetVLADNetFVFCFCFCaverageaverageconcatMoE
Context Gating EmbeddingDim ReductionClassification

Figure 2: This figure shows an evolution of the first architecture from figure
1 with several embeddings. This architecture is made to leverage the diversity
of an Ensemble in a single model.

##  5 Experiments

In this section, we first evaluate the pooling technique proposed in Section
4.2. Then, we conduct experiments to evaluate the accuracy of our compact
models. In particular, we investigate which layer benefits the most from a
circulant representation and show that the decomposition presented in Section
3 performs better than the approach from [6] for the video classification
problem. Finally, we compare all our models on a two dimensional size vs.
accuracy scale in order to evaluate the trade-off between size and accuracy of
each one of our models.

###  5.1 Experimental Setup

#### Dataset

All the experiments of this paper have been done in the context of the 2nd
YouTube-8M Video Understanding Challenge with the YouTube-8M dataset. We
trained our models with the full training set and 70% of the validation set
which corresponds to a total of 4 822 555 examples. We used the data
augmentation technique proposed by [31] to virtually double the number of
inputs. The method consists in splitting the videos into two equal parts. This
approach is motivated by the observation that a human could easily label the
video by watching either the beginning or the ending of the video.

All the code used in this experimental section is available
online.444https://github.com/araujoalexandre/youtube8m-circulant

#### Hyper-parameters

All our experiments are developed with TensorFlow Framework [1]. We trained
our models with the CrossEntropy loss and used Adam optimizer with a 0.0002
learning rate and a 0.8 exponential decay every 4 million examples. All fully
connected layers are composed of 512 units. DBoF, NetVLAD and NetFV are
respectively 8192, 64 and 64 of cluster size for video frames and 4096, 32, 32
for audio frames. We used 4 mixtures for the MoE Layer. We used all the
available 150 frames and robust max pooling introduced in 4.2 for the DBoF
embedding. In order to stabilize and accelerate the training, we used batch
normalization before each non linear activation and gradient clipping.

#### Evaluation Metric

We used the GAP (Global Average Precision), as used in the 2nd YouTube-8M
Video Understanding Challenge, to compare our experiments. The GAP metric is
defined as follows:

$GAP=\sum_{i=1}^{P}p(i)\Delta r(i)$

where $P$ is the number of final predictions, $p(i)$ the precision, and $r(i)$
the recall. We limit our evaluation to 20 predictions for each video.

#### Hardware

All experiments have been realized on a cluster of 12 nodes. Each node has 160
POWER8 processor, 128 Go of RAM and 4 Nividia Titan P100.

###  5.2 Robust Deep Bag-of-Frames pooling method

We evaluate the performance of our Robust DBoF embedding. In accordance with
the work from [2], we find that average pooling performs better than maximum
pooling. Figure 3 shows that the proposed robust maximum pooling method
outperforms both maximum and average pooling.

$0$$1$$2$$3$$4$$5$$6$$0.82$$0.83$$0.84$$0.85$$0.86$$0.87$$0.88$EpochsValidation
GAPComparison of polling methods used with DBoF embeddingRobust DBoFDBoF w/max
poolingDboF w/average pooling
Figure 3: This graphic shows the impact of robust DBoF (i.e. red line) with
$n=10$ and $k=15$ on the Deep Bag-of-Frames embedding compared to max and
average pooling.

###  5.3 Impact of circulant matrices on different layers

This series of experiments aims at understanding the effect of compactness
over different layers. Table 2 shows the result in terms of number of weights,
size of the model (MB) and GAP. We also compute the compression ratio with
respect to the dense model. The compact fully connected layer achieves a
compression rate of 9.5 while having a very similar performance, whereas the
compact DBoF and MoE achieve a higher compression rate at the expense of
accuracy. Figure 4 shows that the model with a compact FC converges faster
than the dense model. The model with a compact DBoF shows a big variance over
the validation GAP which can be associated with a difficulty to train. The
model with a compact MoE is more stable but at the expense of its performance.
Another series of experiments investigates the effect of adding factors of the
compact matrix DC (i.e. the parameters $m$ specified in section 4.3). Table 3
shows that there is no gain in accuracy even if the number of weights
increases. It also shows that adding factors has an important effect on the
speed of training. On the basis of this result, i.e. given the performance and
compression ratio, we can consider that representing the fully connected layer
of the base model in a compact fashion can be a good trade-off.

Baseline Model |  #Weights |  Size (MB) |  Compress. Rate (%) |  GAP@20 |  Diff.
---|---|---|---|---|---
Dense Model |  45 359 764 |  173 |  - |  0.846 |  -
Compact DBoF |  36 987 540 |  141 |  18.4 |  0.838 |  -0.008
Compact FC |  41 181 844 |  157 |  9.2 |  0.845 |  -0.001
Compact MoE |  12 668 504 |  48 |  72.0 |  0.805 |  -0.041

Table 2: This table shows the effect of the compactness of different layers. In these experiments, for speeding-up the training phase, we did not use the audio features and exploited only the video information. $0$$1$$2$$3$$4$$5$$6$$7$$0.77$$0.78$$0.79$$0.8$$0.81$$0.82$$0.83$$0.84$$0.85$$0.86$$0.87$EpochsValidation GAP Comparison of the effect of compactness over different layers with the base model Dense ModelModel with compact DBoFModel with compact FCModel with compact MoE Figure 4: Validation GAP according to the number of epochs for different compact models. #factors |  #Examples/sec |  #parameters in FC Layer |  Compress. Rate of FC layer (%) |  GAP@20
---|---|---|---|---
1 |  1 052 |  12 288 |  99.8 |  0.861
3 |  858 |  73 728 |  98.8 |  0.861
6 |  568 |  147 456 |  97.6 |  0.859
Dense FC |  1 007 |  6 291 456 |  - |  0.861

Table 3: This table shows the evolution of the number of parameters and the
accuracy according to the number of factors. Despite the addition of degrees
of freedom for the weight matrix of the fully connected layer, the model does
not improve in performance. The column #Examples/sec shows the evolution of
images per sec processed during the training of the model with a compact FC
according to the number of factors.

###  5.4 Comparison with related works

Circulant matrices have been used in neural networks in [6]. They proposed to
replace fully connected layers by a circulant and diagonal matrices where the
circulant matrix is learned by a gradient based optimization algorithm and the
diagonal matrix is random with values in {-1, 1}. We compare our more general
framework with their approach. Figure 5 shows the validation GAP according to
the number of epochs of the base model with a compact fully connected layer
implemented with both approaches.

$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$0.79$$0.8$$0.81$$0.82$$0.83$$0.84$$0.85$$0.86$$0.87$$0.88$EpochsValidation
GAPGAP given the pooling method used with DBoF embeddingCompact FC w/general
approachCompact FC w/CD and $D\in\\{-1,1\\}$ Figure 5: This figure shows the
GAP difference between the $CD$ approach proposed in [6] and the more
generalized $DC$ approach from section 4.3. Instead of having
$D\in\\{-1,+1\\}$ fixed, the generalized approach allows $D$ to be learned.

###  5.5 Compact Baseline model with different embeddings

To compare the performance and the compression ratio we can expect, we
consider different settings where the compact fully connected layer is used
together with different embeddings. Figure 6 and Table 4 show the performance
of the base model with DBoF, NetVLAD and NetFV embeddings with a Dense and
Compact fully connected layer. Notice that we can get a bigger compression
rate with NetVLAD and NetFV due to the fact that the output of the embedding
is in a higher dimensional space which implies a larger weight matrix for the
fully connected layer. Although the compression rate is higher, it is at the
expense of accuracy.

$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$0.81$$0.82$$0.83$$0.84$$0.85$$0.86$$0.87$$0.88$EpochsValidation
GAPDBoFCompactDense

$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$0.81$$0.82$$0.83$$0.84$$0.85$$0.86$$0.87$$0.88$EpochsValidation
GAPNetVLADCompactDense

$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$0.81$$0.82$$0.83$$0.84$$0.85$$0.86$$0.87$$0.88$EpochsValidation
GAPNetFVCompactDense

Figure 6: The figures above show the validation GAP of compact and Dense fully connected layer with different embeddings according to the number of epochs. Method |  #Parameters |  Size (MB) |  Compress. Rate (%) |  GAP@20
---|---|---|---|---
DBoF |
FC Dense | 65 795 732 | 251 | - |  0.861
FC Circulant | 59 528 852 | 227 | 9.56 |  0.861
NetVLAD |  |  |  |
FC Dense | 86 333 460 | 330 | - |  0.864
FC Circulant | 50 821 140 | 194 | 41.1 |  0.851
NetFisher |  |  |  |
FC Dense | 122 054 676 | 466 | - |  0.860
FC Circulant | 51 030 036 | 195 | 58.1 |  0.848

Table 4: This table shows the impact of the compression of the fully connected
layer of the model architecture shown in Figure 1 with Audio and Video
features vector and different types of embeddings. The variable compression
rate is due to the different width of the output of the embedding.

###  5.6 Model size vs. accuracy

To conclude our experimental evaluation, we compare all our models in terms of
size and accuracy. The results are presented in Figure 7.

$0$$20$$40$$60$$80$$100$$120$$140$$160$$180$$200$$0.81$$0.82$$0.83$$0.84$$0.85$$0.86$$0.87$$0.88$Number
of weights (Millions)Validation GAPBenchmark of compact modelsNetVLAD 32,
Compact FC 256, MoE 2NetVLAD 64, Compact FC 512, MoE 4NetFV 64, Compact FC
512, MoE 4DBoF 8192, Compact FC 512, MoE 4NetVLAD 256, Compact FC 1024, MoE
4NetVLAD 128, NetFV 64, Compact FC 1024, MoE 4NetVLAD 256, NetFV 128, Compact
FC 1024, MoE 4DBoF 8192, NetVLAD 128, Compact FC 1024, MoE 4DBoF 16384,
NetVLAD 256, Compact FC 1024, MoE 4 Figure 7: Comparison between different
models with compact fully connected layers.

As we can see in this figure, the most compact models are obtained with the
circulant NetVLAD and NetFV. We can also see that the complex architectures
described in Section 4.4 (DBoF + NetVLAD) achieve top performance but at the
cost of a large number of weights. Finally, the best trade-off between size
and accuracy is obtained using the DBoF embedding layer and achieves a GAP of
0.861 for only 60 millions weights.

##  6 Conclusion

In this paper, we demonstrated that circulant matrices can be a great tool to
design compact neural network architectures for video classification tasks. We
proposed a more general framework which improves the state of the art and
conducted a series of experiments aiming at understanding the effect of
compactness on different layers. Our experiments demonstrate that the best
trade-off between size and accuracy is obtained using circulant DBoF embedding
layers. We investigated a model with multiple embeddings to leverage the
performance of an Ensemble but found it ineffective. The good performance of
Ensemble models, i.e. why aggregating different distinct models performs
better that incorporating all the diversity in a single architecture is still
an open problem. Our future work will be devoted to address this challenging
question and to pursue our effort to devise compact models achieving the same
accuracy as larger one, and to study their theoretical properties.

##  7 Acknowledgement

This work was granted access to the OpenPOWER prototype from GENCI-IDRIS under
the Preparatory Access AP010610510 made by GENCI. We would like to thank the
staff of IDRIS who was really available for the duration of this work,
Abdelmalek Lamine and Tahar Nguira, interns at Wavestone for their work on
circulant matrices. Finally, we would also like to thank Wavestone to support
this research.

## References

  * [1] Abadi, M., Agarwal, A., Barham, P., Brevdo, E., Chen, Z., Citro, C., Corrado, G.S., Davis, A., Dean, J., Devin, M., Ghemawat, S., Goodfellow, I., Harp, A., Irving, G., Isard, M., Jia, Y., Jozefowicz, R., Kaiser, L., Kudlur, M., Levenberg, J., Mané, D., Monga, R., Moore, S., Murray, D., Olah, C., Schuster, M., Shlens, J., Steiner, B., Sutskever, I., Talwar, K., Tucker, P., Vanhoucke, V., Vasudevan, V., Viégas, F., Vinyals, O., Warden, P., Wattenberg, M., Wicke, M., Yu, Y., Zheng, X.: TensorFlow: Large-scale machine learning on heterogeneous systems (2015), https://www.tensorflow.org/, software available from tensorflow.org
  * [2] Abu-El-Haija, S., Kothari, N., Lee, J., Natsev, A.P., Toderici, G., Varadarajan, B., Vijayanarasimhan, S.: Youtube-8m: A large-scale video classification benchmark. In: arXiv:1609.08675 (2016), https://arxiv.org/pdf/1609.08675v1.pdf
  * [3] Arandjelović, R., Gronat, P., Torii, A., Pajdla, T., Sivic, J.: NetVLAD: CNN architecture for weakly supervised place recognition. In: IEEE Conference on Computer Vision and Pattern Recognition (2016)
  * [4] Buciluǎ, C., Caruana, R., Niculescu-Mizil, A.: Model compression. In: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 535–541. ACM (2006)
  * [5] Chen, W., Wilson, J.T., Tyree, S., Weinberger, K.Q., Chen, Y.: Compressing neural networks with the hashing trick. In: Proceedings of the 32Nd International Conference on International Conference on Machine Learning - Volume 37. pp. 2285–2294. ICML’15, JMLR.org (2015), http://dl.acm.org/citation.cfm?id=3045118.3045361
  * [6] Cheng, Y., Yu, F.X., Feris, R.S., Kumar, S., Choudhary, A., Chang, S.F.: An exploration of parameter redundancy in deep networks with circulant projections. In: 2015 IEEE International Conference on Computer Vision (ICCV). pp. 2857–2865 (Dec 2015)
  * [7] Collins, M.D., Kohli, P.: Memory bounded deep convolutional networks. CoRR abs/1412.1442 (2014)
  * [8] Courbariaux, M., Bengio, Y., David, J.P.: Binaryconnect: Training deep neural networks with binary weights during propagations. In: Proceedings of the 28th International Conference on Neural Information Processing Systems - Volume 2. pp. 3123–3131. NIPS’15, MIT Press, Cambridge, MA, USA (2015), http://dl.acm.org/citation.cfm?id=2969442.2969588
  * [9] Dai, B., Zhu, C., Guo, B., Wipf, D.: Compressing neural networks using the variational information bottleneck. In: Dy, J., Krause, A. (eds.) Proceedings of the 35th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 80, pp. 1143–1152. PMLR, Stockholmsmässan, Stockholm Sweden (10–15 Jul 2018), http://proceedings.mlr.press/v80/dai18d.html
  * [10] Denil, M., Shakibi, B., Dinh, L., Ranzato, M.A., de Freitas, N.: Predicting parameters in deep learning. In: Burges, C.J.C., Bottou, L., Welling, M., Ghahramani, Z., Weinberger, K.Q. (eds.) Advances in Neural Information Processing Systems 26, pp. 2148–2156. Curran Associates, Inc. (2013), http://papers.nips.cc/paper/5025-predicting-parameters-in-deep-learning.pdf
  * [11] Gupta, S., Agrawal, A., Gopalakrishnan, K., Narayanan, P.: Deep learning with limited numerical precision. In: Proceedings of the 32Nd International Conference on International Conference on Machine Learning - Volume 37. pp. 1737–1746. ICML’15, JMLR.org (2015), http://dl.acm.org/citation.cfm?id=3045118.3045303
  * [12] Han, S., Mao, H., Dally, W.J.: Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. International Conference on Learning Representations (ICLR) (2016)
  * [13] Hinton, G., Vinyals, O., Dean, J.: Distilling the knowledge in a neural network. In: NIPS Deep Learning and Representation Learning Workshop (2015), http://arxiv.org/abs/1503.02531
  * [14] Huhtanen, M., Perämäki, A.: Factoring matrices into the product of circulant and diagonal matrices. Journal of Fourier Analysis and Applications 21(5), 1018–1033 (Oct 2015). https://doi.org/10.1007/s00041-015-9395-0, https://doi.org/10.1007/s00041-015-9395-0
  * [15] Jaderberg, M., Vedaldi, A., Zisserman, A.: Speeding up convolutional neural networks with low rank expansions. CoRR abs/1405.3866 (2014)
  * [16] Jégou, H., Douze, M., Schmid, C., Pérez, P.: Aggregating local descriptors into a compact image representation. In: CVPR 2010 - 23rd IEEE Conference on Computer Vision & Pattern Recognition. pp. 3304–3311. IEEE Computer Society, San Francisco, United States (Jun 2010). https://doi.org/10.1109/CVPR.2010.5540039, https://hal.inria.fr/inria-00548637
  * [17] Jiang, Y.G., Wu, Z., Wang, J., Xue, X., Chang, S.F.: Exploiting feature and class relationships in video categorization with regularized deep neural networks. IEEE Transactions on Pattern Analysis and Machine Intelligence 40(2), 352–364 (2018). https://doi.org/10.1109/TPAMI.2017.2670560, https://doi.org/10.1109/TPAMI.2017.2670560
  * [18] Jordan, M.I., Jacobs, R.A.: Hierarchical mixtures of experts and the em algorithm. In: Proceedings of 1993 International Conference on Neural Networks (IJCNN-93-Nagoya, Japan). vol. 2, pp. 1339–1344 vol.2 (Oct 1993). https://doi.org/10.1109/IJCNN.1993.716791
  * [19] Karpathy, A., Toderici, G., Shetty, S., Leung, T., Sukthankar, R., Fei-Fei, L.: Large-scale video classification with convolutional neural networks. In: Proceedings of the IEEE conference on Computer Vision and Pattern Recognition. pp. 1725–1732 (2014)
  * [20] Li, F., Gan, C., Liu, X., Bian, Y., Long, X., Li, Y., Li, Z., Zhou, J., Wen, S.: Temporal modeling approaches for large-scale youtube-8m video understanding. CoRR abs/1707.04555 (2017)
  * [21] Lin, J., Rao, Y., Lu, J., Zhou, J.: Runtime neural pruning. In: Guyon, I., Luxburg, U.V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., Garnett, R. (eds.) Advances in Neural Information Processing Systems 30, pp. 2181–2191. Curran Associates, Inc. (2017), http://papers.nips.cc/paper/6813-runtime-neural-pruning.pdf
  * [22] Liu, B., Wang, M., Foroosh, H., Tappen, M., Penksy, M.: Sparse convolutional neural networks. In: 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). pp. 806–814 (June 2015). https://doi.org/10.1109/CVPR.2015.7298681
  * [23] Mellempudi, N., Kundu, A., Mudigere, D., Das, D., Kaul, B., Dubey, P.: Ternary neural networks with fine-grained quantization. CoRR abs/1705.01462 (2017)
  * [24] Miech, A., Laptev, I., Sivic, J.: Learnable pooling with context gating for video classification. CoRR abs/1706.06905 (2017)
  * [25] Moczulski, M., Denil, M., Appleyard, J., de Freitas, N.: Acdc: A structured efficient linear layer. arXiv preprint arXiv:1511.05946 (2015)
  * [26] Müller-Quade, J., Aagedal, H., Beth, T., Schmid, M.: Algorithmic design of diffractive optical systems for information processing. Physica D: Nonlinear Phenomena 120(1-2), 196–205 (1998)
  * [27] Perronnin, F., Dance, C.: Fisher kernels on visual vocabularies for image categorization. In: 2007 IEEE Conference on Computer Vision and Pattern Recognition. pp. 1–8 (June 2007). https://doi.org/10.1109/CVPR.2007.383266
  * [28] Rastegari, M., Ordonez, V., Redmon, J., Farhadi, A.: Xnor-net: Imagenet classification using binary convolutional neural networks. In: ECCV (2016)
  * [29] Schmid, M., Steinwandt, R., Müller-Quade, J., Rötteler, M., Beth, T.: Decomposing a matrix into circulant and diagonal factors. Linear Algebra and its Applications 306(1-3), 131–143 (2000)
  * [30] Sindhwani, V., Sainath, T., Kumar, S.: Structured transforms for small-footprint deep learning. In: Cortes, C., Lawrence, N.D., Lee, D.D., Sugiyama, M., Garnett, R. (eds.) Advances in Neural Information Processing Systems 28, pp. 3088–3096. Curran Associates, Inc. (2015), http://papers.nips.cc/paper/5869-structured-transforms-for-small-footprint-deep-learning.pdf
  * [31] Skalic, M., Pekalski, M., Pan, X.E.: Deep learning methods for efficient large scale video labeling. arXiv preprint arXiv:1706.04572 (2017)
  * [32] Vybíral, J.: A variant of the johnson–lindenstrauss lemma for circulant matrices. Journal of Functional Analysis 260(4), 1096 – 1105 (2011). https://doi.org/https://doi.org/10.1016/j.jfa.2010.11.014, http://www.sciencedirect.com/science/article/pii/S0022123610004507
  * [33] Wang, H., Zhang, T., Wu, J.: The monkeytyping solution to the youtube-8m video understanding challenge. CoRR abs/1706.05150 (2017)
  * [34] Yang, Z., Moczulski, M., Denil, M., d. Freitas, N., Smola, A., Song, L., Wang, Z.: Deep fried convnets. In: 2015 IEEE International Conference on Computer Vision (ICCV). pp. 1476–1483 (Dec 2015). https://doi.org/10.1109/ICCV.2015.173
  * [35] Yu, X., Liu, T., Wang, X., Tao, D.: On compressing deep models by low rank and sparse decomposition. In: 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). pp. 67–76 (July 2017). https://doi.org/10.1109/CVPR.2017.15
  * [36] Yue-Hei Ng, J., Hausknecht, M., Vijayanarasimhan, S., Vinyals, O., Monga, R., Toderici, G.: Beyond short snippets: Deep networks for video classification. In: Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 4694–4702 (2015)