RTVD: A Real-Time Volumetric Detection Scheme for DDoS in the Internet of Things

Distributed Denial of Service (DDoS) attacks are increasingly harmful to the cyberspace nowadays. The attackers can now easily launch a bigger and more challenging DDoS attack both towards and with Internet-of-Things (IoT) devices, due to the fast popularization of them. Because of the characteristic of fast overwhelming, it is important to make fast as well as accurate response to DDoS attacks, and the real-time performance can be even more important to prevent and legitimate the attacks. Among the methods proposed by researchers, the entropy-based detection method provides a sensitive and reliable performance. However, the balance between computational complexity and recognition accuracy remains a challenge. In this paper, we propose a detection method that consists of 3 main parts in different aspects: a sliding time window to fasten the entropy calculation, a single-directional filter to realize early detection during the DDoS progress but not after the crash, and a quintile deviation check algorithm to optimize the detection result. These will eventually lead to a real-time and high-efficient performance to recognize IoT DDoS attacks as soon as possible.

I. INTRODUCTION
It has been decades since the Distributed Denial-of-Service (DDoS) attack pattern first appeared [1], yet the DDoS attacks are still huge challenges. Traditionally, a Denial-of-Service (DoS) attack is characterized by an explicit attempt by attackers to prevent the legitimate use of a service, and a DDoS attack deploys multiple devices, usually millions of devices, to attain this goal [2]. In September 2016, the website of computer security consultant Brian Krebs was hit with 620 Gbps of traffic. The DDoS attacks can do much faster and more severe harm to the Internet, yet the attacks can be even stealthier than DoS attacks are. Due to the differences The associate editor coordinating the review of this manuscript and approving it for publication was Zhenyu Zhou . between DoS and DDoS, the defense strategies can be totally different.
Unfortunately, the security situation is even more severe especially in the era of Internet-of-Things (IoT) today. With the up growing number of IoT devices, attackers can easily take control of far more infected bots than ever before. What's more disturbing is that, the concepts of IoT, such as the modern Internet of Vehicles [3], [4], edge computing [7] and Information-Centric Networking (ICN) [5], [6] etc., are having increasingly stronger computing power [8]. In late 2016, Mirai [9], the ever largest IoT botnet, outbroke in 2016 and launched a DDoS attack on 20th Sept., with the maximum speed of 1.5 Tbps on OVH, the French web host and cloud service provider, and launched another DDoS attack on a DNS management service provider in America, which caused a large-area network paralysis in eastern United States. Many VOLUME 8, 2020 This work is licensed under a Creative Commons Attribution 4.0 License. For more information, see http://creativecommons.org/licenses/by/4.0/ American websites, including Twitter and Facebook, failed to be accessed by their domain names. In the offline event in Germany, attackers launched a flood scan on 7,547 port with Mirai, about 900,000 Deutsche Telekom routers crashed during the campaign, resulting in a large scale of limited network access. In late November 2017, a Mirai variant was found launching attacks on IoT devices in Argentina through port 23 and 2323 [10]. Besides Mirai, there already exist many IoT botnets such as QBOT, Luabot, Bashlight, Zollard, Remaiten, KTN-RM, etc., and most of them provide the DDoS service. In fact, few IoT viruses exclude the function of DDoS because IoT is perfect to launch a DDoS attack, making the DDoS more threatening.
In an original DDoS attack, the attacker controls a huge number of devices and threads to directly consume the resources of the victim servers. A Direct DDoS Attack itself is simple to understand and realize, but the attacker must prepare an attacking network to manage and control all the devices by adopting a botnet or a Trojan virus, which enriches the cost of an attack. To avoid this problem, or to make the attack more dangerous, the strategy of (Amplified) Reflective Attack is proposed. In a reflective DDoS attack, the attacker takes advantage of the vulnerabilities of those protocols which make more responding resources than requesting ones, such as DNS, NTP, SSDP, etc. The attacker designs and sends some fake request packets, which are claimed to be sent from the victims to the servers running those reflective protocols. Usually, the servers won't check whether the source IP addresses are valid or real and will send the query results to the victim IP addresses.
In another classification of flow quantity, DDoS attacks are divided into Volumetric attacks and Low and Slow attacks. Volumetric attacks are the traditional type of DDoS, and they overwhelm the targets by consuming network, storage or computing resources. Huge Volume DDoS attacks send a high amount of traffic or request packets to a targeted network or device to overwhelm its bandwidth capabilities, connection limit or other network resources. In contrast, Low and Slow attacks, also known as low-rate DDoS attacks (LDDoS) or Slow DDoS attacks, are mainly based on the vulnerabilities of layer-7 protocols and involve ''what appears to be legitimate traffic at a very slow rate'' [11] to occupy and consume the connections. The earliest Slow DDoS is SlowLoris [12], and it is first released by Robert ''RSnake'' Hansen in June 2009, which allows a single machine to take down another machine's web server with minimal bandwidth and side effects on unrelated services and ports.
Generally, Slow DDoS attacks can go through Volume DDoS detectors, because their packets are usually valid and real, and cause few volume or number of requests, so some researchers claim that Slow DDoS attacks are more technically superior, more dangerous and stealthier than volume attacks. We used to believe that as well, but the reports and data show the result. As is shown in the DDoS Threat Report 2018 Q3 [13], ''The maximum attack size increased 139.84% Year-over-Year to 118Gbps'', and in the Nexusguard Threat Report (DDoS) 2019 Q3 [14], the top attacking vectors are DNS Amplification, HTTP(S) Flood and TCP SYN Flood, as shown in Fig. 1. Since the Huge Volume DDoS attack is still one of the biggest threats in cyberspace and is turning its attacking mode into a brand-new faster one, it is necessary to make the detection more efficient and flexible.
Volume DDoS attacks flood the target in the hopes of slowing or stopping their services. There are 3 main statistical characteristics of the DDoS traffic: 1) Huge traffic size. As in the big data era today, the in-out traffic of a personal web server can easily come to 1000's of Mbps, and when a DDoS attack occurred, typically, the request sizes are in the 100's of Gbps, and reports show that recent attacks have scaled to over 1Tbps.
2) Various source info. Not only does the source Port vary, but the source IP address also varies in a wide range. Usually, the attackers will use the fast-flux technology [15] and an IP/MAC pool for IP spoofing, or will simply generate fake packet heads for those non-source-IP-check protocols. Considering the huge size of network traffic, the range of values can be shocking.
3) Take the effect quickly. The DDoS attack will arouse a huge number of traffic or requests and crash the target victim in a short duration, which means there will be little interaction time for the detection and following defense against the attack.
In this paper, we focus on fastening the detection of volume type DDoS and designed a real-time alarming system. The contribution of this paper is described as follows: 1) We optimize the method of sliding time window to fasten the entropy calculation algorithm; 2) We design a Quintile Deviation Check algorithm to identify the attacks; 3) We redefine a temporal indicator to evaluate the time performance of DDoS detection.
With the 3 contributions, we realize a real-time volumetric detection scheme for DDoS in the Internet of Things.
The rest of this paper is organized as follows. In Section II, we describe the related works on the usage of the sliding time window and DDoS detection methods. In Section III, we list the nomenclature of all the terms, abbreviations and mathematical symbols used in the following paragraphs. In Section IV, we discuss the detection architecture as well as the mathematical theories that our detection is based on. And we set 3 subsections to explain the concepts of Traffic Processor, Entropy Calculator, and Detection & Alarm Module in detail. In Section V, we make simulations on 3 public datasets and a generated dataset to prove and evaluate the detection scheme we propose. In Section VI, we conclude the whole paper and point out the direction of future research.

II. RELATED WORKS
Research works have been done with various strategies to detect DDoS attacks with sliding time window or information entropy methods in recent years.
Early in 2006, the sliding window was used in DDoS detection in [16]. The authors use two adjacent non-overlapping windows: the referenced sliding window and the test sliding window, and use an autoregressive model to recognize anomalous traffic. Reference [18] mentioned a real-time DDoS detection technique, using a sliding window and source IP clusters, and using Spark to meet the distributed demands. In years before the DDoS attacks had the characteristics of a relatively fixed number of packets per second, packet bytes, gap periods, etc. However, the situation has changed and the technique of source IP cluster technique won't work as well as before, but other parts of the research provide many inspirations.
In [19], the authors propose a new two-step method for DDoS attack detection, which combines the approaches of network traffic entropy and the TSK Fuzzy System (TSK-FS), and shows that the TSK-FS DDoS detector reaches enhanced sensitivity and robustness in the detection process. Reference [20] shows a method to identify DDoS attacks by computing entropy and frequency-sorted distributions of selected packet attributes. The authors also use the sliding window to simplify the computation of the entropy, which fastens the calculation, but they didn't discuss the aspect of accuracy in detail. In [21] the authors study information-theoretic methods to detect intrusions in the network. They consider the usage of entropy, conditional entropy and information gain to help partition and setting parameters for existing detection models. On this basis, Virmani et al. proposed an entropy deviation method for network intrusion analysis [22]. They used the variation value of source IP entropy packet-by-packet to classify the benign (trusted) and malicious IP addresses. Reference [17] presented a DDoS attack detection and mitigation system with Software Defined Network (SDN). They collected the network traffic information using the SDN controller and sFlow agents in advance and then identified abnormal network traffic with an entropy-based method and a Support Vector Machine (SVM) classifier. Other researches also mentioned detection or mitigation methods such as Threat Intelligence (TI) information sharing [23] and command lines analysis [24].
Based on all the researches above, entropy works well in the DDoS detection scenario, but the balance between efficiency and accuracy is a big challenge. The mentioned reference [20] uses a sliding window to optimize the time performance, and base on that, our research in this paper does further progress.

III. NOMENCLATURE
To make a clearer expression, in this section, we list all the terms, abbreviations and mathematical symbols that are used in the following paragraphs, as well as their descriptions and definitions. VOLUME 8, 2020

IV. DETECTION ARCHITECTURE AND MATHEMATICAL THEORIES
The detection system consists of 3 parts: a traffic processor, an entropy calculator, and a detection module, and the architecture is shown in Fig. 2. The traffic processor monitors the traffic in the whole network, preprocesses the traffic data and then forwards the data to the entropy calculator. The entropy calculator calculates the real-time entropy values and sends the values to the detection module. The detection module matches the entropy values with the given risk models and decides whether to send out an alarm. In the following sections, we will introduce the mechanism and theories of the 3 parts in detail.

A. TRAFFIC PROCESSOR 1) MONITORING AND THE TIMESTAMP ATTACHED 5-TUPLES
Due to the existence of security vulnerabilities in traditional network architectures, DDoS attacks are becoming increasingly dangerous. To contain the consequence and also to trace the attacks, the industry and academia proposed the concept of software-defined network (SDN), whose centralized control network provides support for the defense against DDoS attacks [25]. Within an SDN environment, we can trace and filter the DDoS traffic, can get the traffic packet in real-time and can make real-time detection and defense.
Since we can get real-time traffic packets, the next thing that matters most is to extract the concerned segments from the input data. The traditional Request-For-Comments (RFC)-defined traffic identifier is the 5-Tuple [26], [27]: [Source IP, Source Port, Destination IP, Destination Port, Protocol]. Analysts use 5-tuples to distinguish between different network flows. Using 5-tuple only will lose time-domain characteristics. To solve this problem, we also append the timestamp of each packet to the tuple as the expiring threshold variable.

2) SINGLE DIRECTIONAL PACKET FILTER
A complete DDoS attack can be divided into 3 stages of preparing, attack accumulating, and saturation. The attackers collect the necessary information and intelligence of the target victims and deploy botnets of Trojans during the preparation stage. After the preparation, the attackers send out a command to launch the attack. As the connection numbers, network resources or computing resources are being gradually occupied, the service capacity keeps declining, and the victims will finally be unable to respond. Most detection methods are based on this characteristic, but this means the attackers have already fulfilled their goals. If we want to prevent the attack before the victims paralyzed, we must further shorten the responding time and latency. However, another problem is that, during the accumulating stage. the victim server can still make responses to the packets, including the malicious ones. We will not only see the victims' IP addresses in the destination IP segment but also see as many attackers' and legal users' IP addresses as well. This will lead to a failure in applying entropy detection until the attack enters the saturation stage.
To eliminate the influences from the victims' response packets, a popular approach is to use flow information instead of packet information, because the network traffic flow will keep only the first packet in the flow. However, this will also lead to false statistical characteristics. Popular flow extractors (e.g., bro and tshark) usually work on a captured pcap file and loses real-time capability. In this paper, we propose a single directional packet filter and tried to advance the detection to the attack accumulation stage. Fig. 3 describes the flow chart of the filter.
The filter takes every sent-in 5-tuple as an input, and only allows the tuples whose direction is the same with the first tuple of a flow to pass. The filter maintains a list to record the identifier of every flow. We reform each 5-tuple into a 3-part array  In the example, we can easily notice that the distribution of source information and destination information becomes unexpectedly the same, and we are unable to locate the attacking event until we remove the response packets.

B. ENTROPY CALCULATOR
Entropy theory is effective in DDoS detection because when an attack occurs, the IP addresses and port numbers of the malicious traffic are provided by thousands of millions of different hosts that are fake, virtual or illegally controlled, while under legal usage. However, they would be confined to a relatively small range, and that will show a sharp contrast from the entropy perspective.

1) OPTIMIZED SLIDING TIME WINDOW
The entropy value can directly represent the distribution of information, but according to Shannon's original entropy formula (1) where w is a constant value and is less than n. Because the series of entropy value describes the trend of the value distribution, the input values that have arrived too long before should have few influences on the current input. Therefore, we can set a proper constant width of a sliding window, i.e. 10 4 packets, and apply the sliding window to the input values to calculate the entropy. Comparing with (1), the upper bound of i is limited to be less than or equal to the width w. The method makes it possible to apply entropy to DDoS detection, but the response time can be further reduced. Taking the result as a basis, we propose 2 methods to further reduce the time complexity.

a: VARIATION UPDATING METHOD
The calculation of the entropy is accumulative. If we apply a sliding time window, we can only recalculate the information content of both the slide-out and slide-in elements, and keep most other unaffected elements the same, thus simplifying the calculation. Supposing that there is an input sequence , and the width of the sliding window is w = 5. Then it is easy to calculate the entropy of the first sliding window: When the window slides forward by a step, the entropy becomes: Giving a subscript of [0 : 4] to the information contents in (2) and [1 : 5] to those in (3), we can get the relation between (2) and (3) [5]) (5) Using this method, the only thing to do is just to count how many times do the slide-in-and-out elements appear within the sliding time window, and the worst time complexity is O(2 * w). Then we calculate the variation of their information contents to update the entropy value, thus getting the generalized (5) with the following hypothesis.
Given an n-length sequence S and a preset sliding window width w (w < n), let H (x) be the entropy value of the x th wlength subsequence of S (marked as S x ), and h x (e) be the information content of an element e in S x . The recurrence formula of entropy writes:

: VALUE COUNTER DICTIONARY AND COUNTER MATRIX
Another realization is to build a dictionary to record the count numbers of every distinct element at every sliding since the very beginning. Taking the previous example, we now record all the count numbers: 3 x 1 s, 1 x 2 and 1 x 3 and record the result as a dictionary d = {x 1 : 3, x 2 : 1, x 3 : 1} to make the result formatted. Now we slide the time window, recount the elements and append the new dictionary to the former one: Because we preset the window width to be 5, it's simple to count the number of all elements. But the situation could be worse as the w goes larger. So we set another variable X to record the to-be-slide-out element. In the example, we set X = x 1 , and after we slide we update the counting number of x 1 from 3 down to 2, and then check whether the newly slide-in element x 4 already exists.
The dictionaries of the whole sliding window can be described in an array: is the value vector of d i . In the example above, the matrix is C = 3 1 1 0 2 1 1 1 . The entropy calculation formula can now be written in a matrix format: Or: 2) JOINT ENTROPY When a DDoS attack occurs, we usually see a sharp climbingup of the entropy of source IP and Ports because of the huge amount of distributed attacking devices. But the situation may be opposite if the target devices are so weak that they can be easily taken down by a few attacking nodes, or the attack is launched by some old-but-still-effective DDoS tools such as ddosim [28]. On the other point of view, we will see a sharp decline of the entropy of destination IP until the number of attack packets reaches the width of the entropy sliding window, and this is a traditional and the most popular detection basis. But actually, the result will be interfered with by some indicators such as the target numbers, policies that motivate traffic to burst up, which is called ''a benign flash crowd'' in Zhao's research [19], etc.
To solve these problems, we combine both source and destination segments and apply joint entropy to the timestamp attached 5-tuples. We use the joint couple of (s_IP, s_Port) instead of the source IP and source port, and then make it joint with destination segments as our final detection basis. We mark (s_IP, s_Port) as s and (d_IP, d_Port) as d, and the final detection basis can be written as (s, d), so that the fake going-down of source IP can be eliminated.

C. DETECTION AND ALARM MODULE 1) BACKGROUND TRAFFIC FILTER
We can now easily find the beginning of attacks even by our eyes, but in practice, the terrible jitters can confuse the computers. It is necessary to eliminate the influences of background noise. Because the entropy values are continuous time series, we can use a Long Short-Term Memory (LSTM) model to predict the following entropy values. The LSTM [29], [30] is an artificial Recurrent Neural Network (RNN) architecture. Unlike standard Feedforward Neural Networks, LSTM has feedback connections and can take past inputs into the calculation, which makes it capable to deal with sequence prediction missions. Bloomberg Business Week wrote: ''These powers make LSTM arguably the most commercial AI achievement, used for everything from predicting diseases to composing music'' [31]. We preset lb as the number of the previous values that LSTM model looks back, send the first lb values as the input sequence, and get a predicted output value p. Then we repeat the process, pump p into the bottom of lb sequence and pop out the top value, send it to LSTM and get the second p value, and so on.

2) QUINTILE DEVIATION CHECK ALGORITHM
As we've got the pre-processed and real-time entropy values, the next thing to do is to make an immediate check and alarm for the suspicious packets. There are many deviation check algorithms: Quartile Deviation [32], [33], Generalized Extreme Studentized Deviate (GESD) [34], Linear Regression, Confidence Interval, etc. In this paper, we concern more about the sensitivity, and the values are nearly continuous, so we decide to redesign the Quartile Deviation algorithm. Quartile Deviation departs ascending sequence values into 4 equal-length subintervals and marks the 3 quartile points as Q1(25%), Q2(50%) and Q3(75%). The deviation value is Q3-Q1, which means 50% of the values are in [Q1, Q3], and the maximum deviation is Q3-Q1.
We made a great modification to the original Quartile Deviation algorithm, and name it as Quintile Deviation Check (abbr. QuinDC). Since we have to consider both directions of the curve trend, we extended the number of subintervals to 5 unequal-length subintervals and named them as Divergent Interval (Upward), Shock Interval (Upward), Convergent Interval, Shock Interval (Downward) and Divergent Interval (Downward) as shown below. The core parameters of QuinDC is the previous average value e and the previous radius value r (half of the value of which in traditional Quartile Deviation algorithm). We set e as the central basis of every test data, and determine the division points with e, e ± r and e ± 2r. If a value falls in the interval of [e − r, e + r], we mark it as 'convergent'; if it falls in the interval of [e − 2r, e − r] or [e + r, e + 2r], we mark it as 'shock'; and if it is larger than e + 2r or less than e − 2r, then we mark it as 'divergent'. Those divergent values are what we concern about, and we can then turn to research what kind of data shows abnormal behavior. We introduce 3 new parameters, N , k and φ to solve this problem.
As is shown in Fig. 5, we apply an N -length sliding window here and divide the N-length sequence into k-length groups in the pattern shown in Fig. 6. Generally, N cannot be divided by k, so we just get rid of the beginning N %k values. Because the sequence or array is checked with a sliding window, this operation won't cause a bad affect on the result.
Finally, we set φ as the threshold of the alarm trigger, and summarize the following two alarm principles: 1) Monotonicity: The average value of all groups must be monotonic.
2) Divergency: φ of the values in the sliding window should be in the divergent intervals determined by the first φ of the sliding window in the previous step. The system will send out an alarm as soon as the 2 principles are both met.

V. SIMULATION AND EVALUATION A. DATASETS SELECTION
In this paper, we use 3 public datasets and a generated dataset for testing. The public datasets are the 1999 DARPA Intrusion Detection Evaluation Data Set [35]- [37], 2009 DARPA DDOS Dataset [38], and the UNB CIC DDoS 2019 Evaluation Dataset [39]. The generated dataset is an emulation SDN-environment DDoS attack traffic generated by IXIA traffic simulator [40]. The 1999 & 2009 DARPA datasets are classical in DDoS evaluation. The CIC DDoS 2019 dataset is the newest dataset that including more modern attacking methods than the previous two datasets. The IXIA dataset is used as a supplement for testing the real-time performance in the SDN environment.
The The IXIA BreakingPoint network tester simulates different DDoS attack scenarios and sends out the traffic packets. In the dataset, the types of DDoS attacks consist of generated simple attacks (such as SYN Flood, UDP Flood, and HTTP Flood) and simulated toolkit attacks (such as TCP and UDP attacks with different frequencies, background traffics or traffic-peak values).

B. SIMULATION OF RTVD DETECTION
Traditionally, we will see the entropy curves of source IP and destination IP in a volumetric DDoS like the black and VOLUME 8, 2020 red curves shown in Fig. 7a, which describe the entropy changes from the occurrence of the attack to its saturation status. But if there are some indicators of specific attacking methods or legal flash crowd etc., like the black and red curves shown in Fig. 7b, it can be difficult to tell when to use the source IP or the destination IP for detection. But after we apply the joint entropy, as the blue curves shown in Fig. 7a and Fig. 7b, the situations become unified. So far, the data preparation has been completed. Now we realize the IoT background packet filter. Fig. 8 shows the real entropy data and its LSTM-predicted data. We can see irregular but legal (for these entropy comes from benign background traffic without any attack) serrations in the real blue entropy line and the highly-coincident predicted red line. We let the LSTM prediction model continuously predict the future entropy with a benign input. Then, we still use a sliding time window, pump the predicted value into the input sequence, then pop out the oldest value. Therefore, the prediction keeps going on. Since we've got the prediction entropy values of the background traffic, we can make a subtraction to eliminate the background noise, thus cutting down the false alarm rate.

C. EVALUATION
We've already been able to receive the traffic from an IoT network and calculate the real-time entropy values of that traffic. The only thing to do is to use QuinDC to find when the attacks occur. Before the final detection, we first made several tests to decide the optimal parameters N , k, φ in QuinDC. We select the traditional Receiver Operating Characteristic (RoC) indices of False Positive Rate (FPR) and False Positive Rate (FPR) to evaluate the QuinDC performance under different parameters.
Generally, the TPR will raise together with the FPR from both 0% to near both 100%, and we hope to find the point where the TPR is as high as possible, and the FPR is as low as possible in the meanwhile. That is to say, what we want is the certain combination of (N , k, φ) that makes the point of (TPR, FPR) closest to the top-left point in the coordinates. In Fig. 9, there are three RoC curves represent IXIA SYN Flood, CIC 2019 DDoS Dataset and DARPA 1999 DDoS Dataset. Since We succeeded in detecting all the DDoS attacks listed in the dataset providers' attackingtimeline files, so we turn to evaluate the TPR and FPR with how many 'attacking packets' will QuinDC identify or omit. According to the result shown in Fig. 9, the best parameter combination is: N = 500, k = 100, φ = 0.4, which means the width of a QuinDC sliding window is 500 packets, the group size is 100 packets, and at least 40% of the values in a sliding window should fall in the I DU which is determined by the first 40% values in the previous sliding window.  The TPR of modern DDoS detection is 100%, and the TPR of attacking packets detection is over 90%, with a low FPR of less than 3%. Furthermore, we redesigned another indicator of Temporal False Omission Rate (TFOR) (10) to evaluate the time performance of response. Traditionally, researchers will use a False Omission Rate (FOR) to evaluate the rate of omitted positive samples.
However, in this paper, we do not care about the other positive samples but want to know how fast can we find the first true attack packet. So we modified (12) and added the temporal variables, and get the TFOR formula as (10).

TFOR =
Alarm Delay Alarm Delay + Elapsed Benign Duration (13) With this revision, we can evaluate a detection scheme to be sensitive and fast with a lower TFOR value. If the system recognizes an attack at its first attacking packet, then the value of Alarm Delay is 0, and the TFOR will be 0%. Otherwise, with the sliding window running, if the system fails to recognize any of the attacking packets, then the TFOR value will raise up and finally reach 100% because there are no packets before the attack and the value of Elapsed Benign Duration is 0. We simulate different types of DDoS attacks from the 4 datasets, and the TFOR results are shown in Fig.10 and listed in detail in Table 2. Most TFOR are less than 0.5% and have an average TFOR of 0.344765%. Also, the scheme can recognize all the volumetric DDoS attacks in an average delay of 0.015172 second.

VI. CONCLUSION
In this paper, we optimized the joint entropy calculation process and designed the algorithm of Quintile Deviation Check (QuinDC) to realize RTVD: a real-time volumetric detection scheme for DDoS in the Internet of Things. The techniques of sliding window, timestamp attached 5-tuple, and single directional packet filter make it possible to do entropy calculation in real-time. Furthermore, the QuinDC provides a lowlatency and accurate performance, so that it can be applied in systems with the real-time requirement, such as intrusion defense systems in IoT environments. In future research, we will try to use LSTM or GRU for directly IoT DDoS detection, and focus on the Slow DDoS, as well as real-time volumetric DDoS taxonomy.
MING LIU is currently a Lecturer with the School of Electronic Information and Electrical Engineering, Shanghai Jiao Tong University, China. His research interests include cyber threat intelligence, intrusion detection systems, and scalable data analytics.
ZHI XUE is currently a Professor with the School of Electronic Information and Electrical Engineering, Shanghai Jiao Tong University, China. His research interests include wireless network security, cloud security, cryptography, and cyber threat intelligence.
XIAOCHEN FAN (Student Member, IEEE) received the B.S. degree in computer science from the Beijing Institute of Technology, China, in 2013. He is currently pursuing the Ph.D. degree with the School of Electrical and Data Engineering, University of Technology Sydney (UTS), Australia. His research interests include mobile and pervasive computing, deep learning, and the IoT.
XIANGJIAN HE is currently a Professor and also the Director of the Computer Vision and Pattern Recognition Laboratory, Global Big Data Technologies Centre (GBDTC), and also a Co-Leader of the Network Security Research Team, Center for Real-time Information Networks (CRIN), University of Technology Sydney. VOLUME 8, 2020


extfieldsofstudy:
Mathematics
Computer Science

text:
Towards a Parallel-in-Time Calculation of Time-Periodic Solutions with Unknown Period

This paper presents a novel parallel-in-time algorithm able to compute time-periodic solutions of problems where the period is not given. Exploiting the idea of the multiple shooting method, the proposed approach calculates the initial values at each subinterval as well as the corresponding period iteratively. As in the Parareal method, parallelization in the time domain is performed using discretization on a two-level grid. A special linearization of the time-periodic system on the coarse grid is introduced to speed up the computations. The iterative algorithm is verified via its application to the Colpitt oscillator model.

Introduction
Steady-state analysis is a common task in electrical engineering, for example, during the initial design stages of, e.g., electric circuits or motors. Classical sequential time stepping may lead to lengthy transient computation particularly when the underlying dynamical system possesses a large time constant. Various approaches for efficient steady-state calculation are known from the literature. For instance, clever methods to choose the starting value [1] or an explicit error correction [14] could accelerate the time-domain calculation considerably.
A powerful tool for speeding up the classical time stepping is the class of parallelin-time methods, such as the multigrid reduction in time [5] or Parareal [11]. Originating from the multiple shooting method [12], they are based on the splitting of the considered time interval into several windows and updating the solution at synchronization points iteratively. The use of coarse and fine discretizations propagates quickly low-frequency information of the solution using a cheap sequential solver followed by a very accurate result with a precise fine solver applied in parallel. Another direction of obtaining the steady state is based on the solution of the joint space-and time-discrete time-periodic system formulated on the whole period [8]. There the initial and final values are coupled through the prescribed periodicity condition. An obstacle within the solution of the periodic problem in the time domain becomes the large size of the system matrix as well as its special block structure due to the interdependence of the solution vectors over the period. To deal with this difficulty a frequency domain approach was proposed in [2]. In case of linear problems, the method takes advantage of the block-cyclic matrix structure by applying the discrete Fourier transform. It fully decouples the variables, thereby allowing for the separate solution of each harmonic coefficient. This approach was further extended and incorporated into the Parareal framework by the authors in [10]. There, a simplified Newton-based iterative algorithm was presented together with its convergence analysis for the efficient treatment of nonlinear problems.
Solutions of time-periodic problems become much more challenging when the period is not given. Such situation occurs, e.g., when dealing with an atonomous system [4]. In contrast to a non-atonomous problem, the periodicity cannot be determined from the applied excitation. This paper proposes a numerical algorithm capable of determining an appropriate period automatically using parallelization in the time domain. Extending the idea of the multiple shooting method we include the unknown period together with multiple initial values as the sought parameters into the iterative procedure. Verification of the presented approach is illustrated through its application to the Colpitt oscillator model [9].
The paper is organized as follows. Section 2 describes the basis of the multiple shooting approach including the unknown period as an additional variable. This is further expanded to the family of the Parareal-based methods in Section 3. Section 4 applies the proposed parallel-in-time approach to the Colpitt oscillator model using a particular linerization on the coarse level. The paper is finally summarized in Section 5.

Multiple shooting with unknown period
We consider the following time-periodic problem for a system of ordinary differential equations (ODEs) where the period T > 0 and the vectorũ : M is a given (regular) mass matrix, f is a bounded and Lipschitz continous right-hand-side (RHS) function. Following [3] we incorporate the period T as an unknown parameter by performing the change of variables Fig. 1 Example of the interval splitting within the multiple shooting for N = 5. The mismatches at the synchronization points τ n , n = 1, . . ., N − 1 together with the periodicity jump between the solution at τ 0 and τ N are eliminated (up to a prescribed tolerance) by solving the root-finding problem.
A sketch of the piecewise-defined solution due to the interval splitting is shown in Fig. 1. In order to eliminate the jumps at the synchronization points τ n , n = 1, . . . , N − 1 as well as the difference between the initial value at τ 0 and the final one at τ N the matching conditions: (5) represents the rootfinding problem for the mapping Φ : R Nd+1 → R Nd . The Jacobian of Φ is given by where n = 1, . . . , N and I is the identity matrix. The root z of (5) can then be calculated using the Newton method, i.e., for a given z (0) and k = 0, 1, . . . solution z (k+1) at the iteration k + 1 is updated through Note that due to the introduction of the additional variable T the system of equations (8) is underdetermined and can be solved, e.g., by calculating the Moore-Penrose pseudoinverse. Besides, in case when the size of (8) is large it can be condensed to a d-dimensional system with d + 1 unknowns by block Gaussian elimination [3,4].

Periodic time-parallelization with coarse grid correction
Inheriting the idea of the Parareal algorithm [7,11] we approximate the derivative in G n (7) in a finite difference way using a coarse propagator G , i.e., for the iteration k and n = 1, . . . , N Similar to the fine propagator F , the operator G solves the IVP (4) on each time window. However, in contrast to the fine solver the coarse propagator has a considerably lower precision, e.g., it uses a lower-order time integrator or bigger time steps. Substituting (10) into (8) we obtain the periodic Parareal with periodic coarse problem [6] with unknown period (PP-PC-UP): n−1 and following [3] for n = 1, . . . , N. In the general case, the system of equation (11) is nonlinear and implicit, which requires an additional linearization. Building upon the ideas presented in [10], which dealt with the time-periodic problem for a known given period T , we encorporate an additive splitting of the system matrix in (11). For this let us introduce a modified coarse propagatorḠ , which instead of (4) solves an approximate model with a linearized functionf(u) = Au + c on the RHS, i.e., with a given Jacobi-matrix A n and a vector c. Having the linear coarse model we construct a fixed point iteration: for s = 0, 1, . . . for n = 1, . . . , N. Assuming thatḠ solves (13) with the implicit Euler method using a single step on (τ n−1 , τ n ] and that all the windows have the same length ∆ τ, we have an explicit representation for the coarse solution for n = 1, . . . , N. Denoting by C := 1/∆ τ · M and Q (k) := C − T (k) A and plugging this into the system (13) we obtain Remark 1 We note that when the period T is given within the problem setting (1), the corresponding block-cyclic matrix (system matrix of (3) without the last column) can be transformed into a block-diagonal using the frequency domain transformation [2]. A detailed description of the approach as well as a Newton-like linearization of the periodic system within the parallel-in-time setting is presented in [10].

Numerical example
We now consider the Colpitt oscillator model presented in [9]. It is described by the circuit illustrated in Fig. 2, which consists of an inductance, a bipolar transistor, as well as of four capacitances and four resistances. The Colpitt oscillator model was exploited in the multi-rate context in [13]. The mathematical model of the circuit is given by an implicit system of ODEs [9], namely, we search for the four node voltages U = [U 1 ,U 2 ,U 3 ,U 4 ] ⊤ s.t. To find the periodic steady-state solution and the corresponding period T we apply the iteration (14). Linearization of the nonlinear periodic system on the coarse level is performed using a surrogate linear model, i.e.,Ḡ solves the problem (13) withf(U) = AU + c given by withŪ T = 0.2585V. The unit interval [0, 1] is split into N = 10 windows. The coarse time step ∆ τ = 0.1 and the fine step δ τ = 10 −4 were chosen within the time integration. The calculated period with the fixed point iteration (3) is T = 0.1125ms. The right-hand part of the Fig. 3 shows convergence of the PP-PC iteration with the linearization from [10] for a given period T as well as for an unknown period (PP-PC-UP). Both results are obtained up to the relative tolerance of 10 −3 . One can see that in case when T is known the method required less iterations, as one would expect. When comparing the computational cost of the computations in terms of the number of linear systems solves, PP-PC and PP-PC-UP delivered the periodic solution effectively 4 and 3 times faster than the sequential time stepping, respectively.

Conclusions
An iterative parallel-in-time method for solving time-periodic problems where the period is not initially given is proposed in this paper. It complements the system of equations originating from the Parareal-like algorithm with an additional variable T and gives an underdetermined system of nonlinear equations. A linearization using the fixed point iteration is applied on the coarse grid. The algorithm is verified through its application to a Colpitt oscillator model.


TinyTL: Reduce Activations, Not Trainable Parameters for Efficient On-Device Learning

On-device learning enables edge devices to continually adapt the AI models to new data, which requires a small memory footprint to fit the tight memory constraint of edge devices. Existing work solves this problem by reducing the number of trainable parameters. However, this doesn't directly translate to memory saving since the major bottleneck is the activations, not parameters. In this work, we present Tiny-Transfer-Learning (TinyTL) for memory-efficient on-device learning. TinyTL freezes the weights while only learns the bias modules, thus no need to store the intermediate activations. To maintain the adaptation capacity, we introduce a new memory-efficient bias module, the lite residual module, to refine the feature extractor by learning small residual feature maps adding only 3.8% memory overhead. Extensive experiments show that TinyTL significantly saves the memory (up to 6.5x) with little accuracy loss compared to fine-tuning the full network. Compared to fine-tuning the last layer, TinyTL provides significant accuracy improvements (up to 34.1%) with little memory overhead. Furthermore, combined with feature extractor adaptation, TinyTL provides 7.3-12.9x memory saving without sacrificing accuracy compared to fine-tuning the full Inception-V3.

Introduction
Intelligent edge devices with rich sensors (e.g., billions of mobile phones and IoT devices) 1 have been ubiquitous in our daily lives. These devices keep collecting new and sensitive data through the sensor every day while being expected to provide high-quality and customized services without sacrificing privacy 2 . These pose new challenges to efficient AI systems that could not only run inference but also continually fine-tune the pre-trained models on newly collected data (i.e., on-device learning).
Though on-device learning can enable many appealing applications, it is an extremely challenging problem. First, edge devices are memory-constrained. For example, a Raspberry Pi 1 Model A only has 256MB of memory, which is sufficient for inference, but by far insufficient for training (Figure 1 left), even using a lightweight neural network architecture (MobileNetV2 [1]). Furthermore, the memory is shared by various on-device applications (e.g., other deep learning models) and the operating system. A single application may only be allocated a small fraction of the total memory, which makes this challenge more critical. Second, edge devices are energy-constrained. DRAM access consumes two orders of magnitude more energy than on-chip SRAM access. The large memory footprint of activations cannot fit into the limited on-chip SRAM, thus has to access DRAM. For instance, the training memory of MobileNetV2, under batch size 16, is close to 1GB, which is by far larger than the SRAM size of an AMD EPYC CPU 3 (Figure 1 left), not to mention lower-end   There is plenty of efficient inference techniques that reduce the number of trainable parameters and the computation FLOPs [1,2,3,4,5,6,7,8,9,10], however, parameter-efficient or FLOPs-efficient techniques do not directly save the training memory. It is the activation that bottlenecks the training memory, not the parameters. For example, Figure 1 (right) compares ResNet-50 and MobileNetV2-1. 4. In terms of parameter size, MobileNetV2-1.4 is 4.3× smaller than ResNet-50. However, for training activation size, MobileNetV2-1.4 is almost the same as ResNet-50 (only 1.1× smaller), leading to little memory reduction. It is essential to reduce the size of intermediate activations required by back-propagation, which is the key memory bottleneck for efficient on-device training.
In this paper, we propose Tiny-Transfer-Learning (TinyTL) to address these challenges. By analyzing the memory footprint during the backward pass, we notice that the intermediate activations (the main bottleneck) are only needed when updating the weights, not the biases (Eq. 2). Inspired by this finding, we propose to freeze the weights of the pre-trained feature extractor and only update the biases to reduce the memory footprint ( Figure 2b). To compensate for the capacity loss, we introduce a memory-efficient bias module, called lite residual module, which improves the model capacity by refining the intermediate feature maps of the feature extractor ( Figure 2c). Meanwhile, we aggressively shrink the resolution and width of the lite residual module to have a small memory overhead (only 3.8%). Extensive experiments on 9 image classification datasets with the same pre-trained model (ProxylessNAS-Mobile [11]) demonstrate the effectiveness of TinyTL compared to previous transfer learning methods. Further, combined with a pre-trained once-for-all network [10], TinyTL can select a specialized sub-network as the feature extractor for each transfer dataset (i.e., feature extractor adaptation): given a more difficult dataset, a larger sub-network is selected, and vice versa. TinyTL achieves the same level of (or even higher) accuracy compared to fine-tuning the full Inception-V3 while reducing the training memory footprint by up to 12.9×. Our contributions can be summarized as follows: • We propose TinyTL, a novel transfer learning method to reduce the training memory footprint by an order of magnitude for efficient on-device learning. We systematically analyze the memory of training and find the bottleneck comes from updating the weights, not biases (assume ReLU activation). • We also introduce the lite residual module, a memory-efficient bias module to improve the model capacity with little memory overhead. • Extensive experiments on transfer learning tasks show that our method is highly memory-efficient and effective. It reduces the training memory footprint by up to 12.9× without sacrificing accuracy.

Related Work
Efficient Inference Techniques. Improving the inference efficiency of deep neural networks on resource-constrained edge devices has recently drawn extensive attention. Starting from [4,5,12,13,14], one line of research focuses on compressing pre-trained neural networks, including i) network pruning that removes less-important units [4,15] or channels [16,17]; ii) network quantization that reduces the bitwidth of parameters [5,18] or activations [19,20]. However, these techniques cannot handle the training phase, as they rely on a well-trained model on the target task as the starting point.
Another line of research focuses on lightweight neural architectures by either manual design [1,2,3,21,22] or neural architecture search [6,8,11,23]. These lightweight neural networks provide highly competitive accuracy [10,24] while significantly improving inference efficiency. However, concerning the training memory efficiency, key bottlenecks are not solved: the training memory is dominated by activations, not parameters ( Figure 1).
There are also some non-deep learning methods [25,26,27] that are designed for efficient inference on edge devices. These methods are suitable for handling simple tasks like MNIST. However, for more complicated tasks, we still need the representation capacity of deep neural networks.
Memory Footprint Reduction. Researchers have been seeking ways to reduce the training memory footprint. One typical approach is to re-compute discarded activations during backward [28,29]. This approach reduces memory usage at the cost of a large computation overhead. Thus it is not preferred for edge devices. Layer-wise training [30] can also reduce the memory footprint compared to end-to-end training. However, it cannot achieve the same level of accuracy as end-to-end training. Another representative approach is through activation pruning [31], which builds a dynamic sparse computation graph to prune activations during training. Similarly, [32] proposes to reduce the bitwidth of training activations by introducing new reduced-precision floating-point formats. Besides reducing the training memory cost, there are some techniques that focus on reducing the peak inference memory cost, such as RNNPool [33] and MemNet [34]. Our method is orthogonal to these techniques and can be combined to further reduce the memory footprint.
Transfer Learning. Neural networks pre-trained on large-scale datasets (e.g., ImageNet [35]) are widely used as a fixed feature extractor for transfer learning, then only the last layer needs to be fine-tuned [36,37,38,39]. This approach does not require to store the intermediate activations of the feature extractor, and thus is memory-efficient. However, the capacity of this approach is limited, resulting in poor accuracy, especially on datasets [40,41] whose distribution is far from ImageNet (e.g., only 45.9% Aircraft top1 accuracy achieved by Inception-V3 [42]). Alternatively, fine-tuning the full network can achieve better accuracy [43,44]. But it requires a vast memory footprint and hence is not friendly for training on edge devices. Recently, [45,46] propose to only update parameters of the batch normalization (BN) [47] layers, which greatly reduces the number of trainable parameters. Unfortunately, parameter-efficiency doesn't translate to memory-efficiency. It still requires a large amount of memory (e.g., 326MB under batch size 8) to store the input activations of the BN layers (Table 3). Additionally, the accuracy of this approach is still much worse than fine-tuning the full network (70.7% v.s. 85.5%; Table 3). People can also partially fine-tune some layers, but how many layers to select is still ad hoc. This paper provides a systematic approach to save memory without losing accuracy.

Understanding the Memory Footprint of Back-propagation
Without loss of generality, we consider a neural network M that consists of a sequence of layers: where w i denotes the parameters of the i th layer. Let a i and a i+1 be the input and output activations of the i th layer, respectively, and L be the loss. In the backward pass, given ∂L ∂ai+1 , there are two goals for the i th layer: computing ∂L ∂ai and ∂L ∂wi . Assuming the i th layer is a linear layer whose forward process is given as: a i+1 = a i W + b, then its backward process under batch size 1 is  Figure 2: TinyTL overview ("C" denotes the width and "R" denote the resolution). Conventional transfer learning relies on fine-tuning the weights to adapt the model (Fig.a), which requires a large amount of activation memory (in blue) for back-propagation. TinyTL reduces the memory usage by fixing the weights (Fig.b) while only fine-tuning the bias. (Fig.c) exploit lite residual learning to compensate for the capacity loss, using group convolution and avoiding inverted bottleneck to achieve high arithmetic intensity and small memory footprint. The skip connection remains unchanged (omitted for simplicity).
According to Eq. (2), the intermediate activations (i.e., {a i }) that dominate the memory footprint are only required to compute the gradient of the weights (i.e., ∂L ∂W ), not the bias. If we only update the bias, training memory can be greatly saved. This property is also applicable to convolution layers and normalization layers (e.g., batch normalization [47], group normalization [48], etc) since they can be considered as special types of linear layers.
Regarding non-linear activation layers (e.g., ReLU, sigmoid, h-swish), sigmoid and h-swish require to store a i to compute ∂L ∂ai (Table 1), hence they are not memory-efficient. Activation layers that build upon them are also not memory-efficient consequently, such as tanh, swish [49], etc. In contrast, ReLU and other ReLU-styled activation layers (e.g., LeakyReLU [50]) only requires to store a binary mask representing whether the value is smaller than 0, which is 32× smaller than storing a i . Table 1: Detailed forward and backward processes of non-linear activation layers. |a i | denotes the number of elements of a i . "•" denotes the element-wise product.

Lite Residual Learning
Based on the memory footprint analysis, one possible solution of reducing the memory cost is to freeze the weights of the pre-trained feature extractor while only update the biases ( Figure 2b). However, only updating biases has limited adaptation capacity. Therefore, we introduce lite residual learning that exploits a new class of generalized memory-efficient bias modules to refine the intermediate feature maps (Figure 2c).
Formally, a layer with frozen weights and learnable biases can be represented as: To improve the model capacity while keeping a small memory footprint, we propose to add a lite residual module that generates a residual feature map to refine the output: where a i = reduce(a i ) is the reduced activation. According to Eq. (2), learning these lite residual modules only requires to store the reduced activations {a i } rather than the full activations {a i }.
Implementation ( Figure 2c). We apply Eq. (4) to mobile inverted bottleneck blocks (MB-block) [1]. The key principle is to keep the activation small. Following this principle, we explore two design dimensions to reduce the activation size: • Width. The widely-used inverted bottleneck requires a huge number of channels (6×) to compensate for the small capacity of a depthwise convolution, which is parameter-efficient but highly activation-inefficient. Even worse, converting 1× channels to 6× channels back and forth requires two 1 × 1 projection layers, which doubles the total activation to 12×. Depthwise convolution also has a very low arithmetic intensity (its OPs/Byte is less than 4% of 1 × 1 convolution's OPs/Byte if with 256 channels), thus highly memory in-efficient with little reuse. To solve these limitations, our lite residual module employs the group convolution that has much higher arithmetic intensity than depthwise convolution, providing a good trade-off between FLOPs and memory. That also removes the 1×1 projection layer, reducing the total channel number by 6×2+1 1+1 = 6.5×. • Resolution. The activation size grows quadratically with the resolution. Therefore, we shrink the resolution in the lite residual module by employing a 2 × 2 average pooling to downsample the input feature map. The output of the lite residual module is then upsampled to match the size of the main branch's output feature map via bilinear upsampling. Combining resolution and width optimizations, the activation of our lite residual module is roughly 2 2 × 6.5 = 26× smaller than the inverted bottleneck.

Discussions
Normalization Layers. As discussed in Section 3.1, TinyTL flexibly supports different normalization layers, including batch normalization (BN), group normalization (GN), layer normalization (LN), and so on. In particular, BN is the most widely used one in vision tasks. However, BN requires a large batch size to have accurate running statistics estimation during training, which is not suitable for on-device learning where we want a small training batch size to reduce the memory footprint. Moreover, the data may come in a streaming fashion in on-device learning, which requires a training batch size of 1. In contrast to BN, GN can handle a small training batch size as the running statistics in GN are computed independently for different inputs. In our experiments, GN with a small training batch size (e.g., 8) performs slightly worse than BN with a large training batch size (e.g., 256). However, as we target at on-device learning, we choose GN in our models.
Feature Extractor Adaptation. TinyTL can be applied to different backbone neural networks, such as MobileNetV2 [1], ProxylessNASNets [11], EfficientNets [24], etc. However, since the weights of the feature extractor are frozen in TinyTL, we find using the same backbone neural network for all transfer tasks is sub-optimal. Therefore, we choose the backbone of TinyTL using a pre-trained once-for-all network [10] to adaptively select the specialized feature extractor that best fits the target transfer dataset. Specifically, a once-for-all network is a special kind of neural network that is sparsely activated, from which many different sub-networks can be derived without retraining by sparsely activating parts of the model according to the architecture configuration (i.e., depth, width, kernel size, resolution), while the weights are shared. This allows us to efficiently evaluate the effectiveness of a backbone neural network on the target transfer dataset without the expensive pre-training process. Further details of the feature extractor adaptation process are provided in Appendix A. For object classification datasets, we report the top1 accuracy (%) while for CelebA we report the average top1 accuracy (%) over 40 facial attribute classification tasks. 'B' represents Bias while 'L' represents LiteResidual. FT-Last represents only the last layer is fine-tuned. FT-Norm+Last represents normalization layers and the last layer are fine-tuned. FT-Full represents the full network is fine-tuned. The backbone neural network is ProxylessNAS-Mobile, and the resolution is 224 except for 'TinyTL-L+B@320' whose resolution is 320. TinyTL consistently outperforms FT-Last and FT-Norm+Last by a large margin with a similar or lower training memory footprint. By increasing the resolution to 320, TinyTL can reach the same level of accuracy as FT-Full while being 6× memory efficient. Datasets. Following the common practice [43,44,45], we use ImageNet [35] as the pre-training dataset, and then transfer the models to 8 downstream object classification tasks, including Cars [41], Flowers [51], Aircraft [40], CUB [52], Pets [53], Food [54], CIFAR10 [55], and CIFAR100 [55].

Method
Besides object classification, we also evaluate our TinyTL on human facial attribute classification tasks, where CelebA [56] is the transfer dataset and VGGFace2 [57] is the pre-training dataset.
Model Architecture. To justify the effectiveness of TinyTL, we first apply TinyTL and previous transfer learning methods to the same backbone neural network, ProxylessNAS-Mobile [11]. For each MB-block in ProxylessNAS-Mobile, we insert a lite residual module as described in Section 3.2 and Figure 2 (c). The group number is 2, and the kernel size is 5. We use the ReLU activation since it is more memory-efficient according to Section 3.1. We replace all BN layers with GN layers to better support small training batch sizes. We set the number of channels per group to 8 for all GN layers. Following [58], we apply weight standardization [59] to convolution layers that are followed by GN.
For feature extractor adaptation, we build the once-for-all network using the MobileNetV2 design space [10,11] that contains five stages with a gradually decreased resolution, and each stage consists of a sequence of MB-blocks. In the stage-level, it supports elastic depth (i.e., 2, 3, 4). In the block-level, it supports elastic kernel size (i.e., 3, 5, 7) and elastic width expansion ratio (i.e., 3,4,6). Similarly, for each MB-block in the once-for-all network, we insert a lite residual module that supports elastic group number (i.e., 2, 4) and elastic kernel size (i.e., 3, 5).
Training Details. We freeze the memory-heavy modules (weights of the feature extractor) and only update memory-efficient modules (bias, lite residual, classifier head) during transfer learning. The models are fine-tuned for 50 epochs using the Adam optimizer [60] with batch size 8 on a single GPU. The initial learning rate is tuned for each dataset while cosine schedule [61] is adopted for learning rate decay. We apply 8bits weight quantization [5] on the frozen weights to reduce the parameter size, which causes a negligible accuracy drop in our experiments. For all compared methods, we also assume the 8bits weight quantization is applied if eligible when calculating their training memory footprint. Additionally, as PyTorch does not support explicit fine-grained memory management, we use the theoretically calculated training memory footprint for comparison in our experiments. For simplicity, we assume the batch size is 8 for all compared methods throughout the experiment section.  Figure 3: Top1 accuracy results of different transfer learning methods under varied resolutions using the same pre-trained neural network (ProxylessNAS-Mobile). With the same level of accuracy, TinyTL achieves 3.9-6.5× memory saving compared to fine-tuning the full network.

Main Results
Effectiveness of TinyTL. Table 2 reports the comparison between TinyTL and previous transfer learning methods including: i) fine-tuning the last linear layer [36,37,39] (referred to as FT-Last); ii) fine-tuning the normalization layers (e.g., BN, GN) and the last linear layer [42] (referred to as FT-Norm+Last) ; iii) fine-tuning the full network [43,44] (referred to as FT-Full). We also study several variants of TinyTL including: i) TinyTL-B that fine-tunes biases and the last linear layer; ii) TinyTL-L that fine-tunes lite residual modules and the last linear layer; iii) TinyTL-L+B that fine-tunes lite residual modules, biases, and the last linear layer. All compared methods use the same pre-trained model but fine-tune different parts of the model as discussed above. We report the average accuracy across five runs.
Compared to FT-Last, TinyTL maintains a similar training memory footprint while improving the top1 accuracy by a significant margin. In particular, TinyTL-L+B improves the top1 accuracy by 34.1% on Cars, by 30.5% on Aircraft, by 12.6% on CIFAR100, by 11.0% on Food, etc. It shows the improved adaptation capacity of our method over FT-Last. Compared to FT-Norm+Last, TinyTL-L+B improves the training memory efficiency by 5.2× while providing up to 7.3% higher top1 accuracy, which shows that our method is not only more memory-efficient but also more effective than FT-Norm+Last. Compared to FT-Full, TinyTL-L+B@320 can achieve the same level of accuracy while providing 6.0× training memory saving.
Regarding the comparison between different variants of TinyTL, both TinyTL-L and TinyTL-L+B have clearly better accuracy than TinyTL-B while incurring little memory overhead. It shows that the lite residual modules are essential in TinyTL. Besides, we find that TinyTL-L+B is slightly better than TinyTL-L on most of the datasets while maintaining the same memory footprint. Therefore, we choose TinyTL-L+B as the default. Figure 3 demonstrates the results under different input resolutions. We can observe that simply reducing the input resolution will result in significant accuracy drops for FT-Full. In contrast, TinyTL can reduce the memory footprint by 3.9-6.5× while having the same or even higher accuracy compared to fine-tuning the full network.
Combining TinyTL and Feature Extractor Adaptation. Table 3 summarizes the results of TinyTL and previously reported transfer learning results, where different backbone neural networks are used as the feature extractor. Combined with feature extractor adaptation, TinyTL achieves 7.5-12.9× memory saving compared to fine-tuning the full Inception-V3, reducing from 850MB to 66-114MB while providing the same level of accuracy. Additionally, we try updating the last two layers besides biases and lite residual modules (indicated by † ), which results in 2MB of extra  Figure 4: Compared with the dynamic activation pruning [31], TinyTL saves the memory more effectively.
training memory footprint. This slightly improves the accuracy performances, from 90.7% to 91.5% on Cars, from 85.0% to 86.0% on Food, and from 84.8% to 85.4% on Aircraft.

Ablation Studies and Discussions
Comparison with Dynamic Activation Pruning. The comparison between TinyTL and dynamic activation pruning [31] is summarized in Figure 4. TinyTL is more effective because it re-designed the transfer learning framework (lite residual module, feature extractor adaptation) rather than prune an existing architecture. The transfer accuracy drops quickly when the pruning ratio increases beyond 50% (only 2× memory saving). In contrast, TinyTL can achieve much higher memory reduction without loss of accuracy.
Initialization for Lite Residual Modules. By default, we use the pre-trained weights on the pretraining dataset to initialize the lite residual modules. It requires to have lite residual modules during both the pre-training phase and transfer learning phase. When applying TinyTL to existing pre-trained neural networks that do not have lite residual modules during the pre-training phase, we need to use another initialization strategy for the lite residual modules during transfer learning. To verify the effectiveness of TinyTL under this setting, we also evaluate the performances of TinyTL when using random weights [62] to initialize the lite residual modules except for the scaling parameter of the final normalization layer in each lite residual module. These scaling parameters are initialized with zeros. Table 4 reports the summarized results. We find using the pre-trained weights to initialize the lite residual modules consistently outperforms using random weights. Besides, we also find that using  TinyTL-RandomL+B still provides highly competitive results on Cars, Food, Aircraft, CIFAR10, CIFAR100, and CelebA. Therefore, if having the budget, it is better to use pre-trained weights to initialize the lite residual modules. If not, TinyTL can still be applied and provides competitive results on datasets whose distribution is far from the pre-training dataset.
Results of TinyTL under Batch Size 1. Figure 5 demonstrates the results of TinyTL when using a training batch size of 1. We tune the initial learning rate for each dataset while keeping the other training settings unchanged. As our model employs group normalization rather than batch normalization (Section 3.3), we observe little/no loss of accuracy than training with batch size 8. Meanwhile, the training memory footprint is further reduced to around 16MB, a typical L3 cache size. This makes it much easier to train on the cache (SRAM), which can greatly reduce energy consumption than DRAM training.

Conclusion
We proposed Tiny-Transfer-Learning (TinyTL) for memory-efficient on-device learning that aims to adapt pre-trained models to newly collected data on edge devices. Unlike previous methods that focus on reducing the number of parameters or FLOPs, TinyTL directly optimizes the training memory footprint by fixing the memory-heavy modules (i.e., weights) while learning memory-efficient bias modules. We further introduce lite residual modules that significantly improve the adaptation capacity of the model with little memory overhead. Extensive experiments on benchmark datasets consistently show the effectiveness and memory-efficiency of TinyTL, paving the way for efficient on-device machine learning.

Broader Impact
The proposed efficient on-device learning technique greatly reduces the training memory footprint of deep neural networks, enabling adapting pre-trained models to new data locally on edge devices without leaking them to the cloud. It can democratize AI to people in the rural areas where the Internet is unavailable or the network condition is poor. They can not only inference but also fine-tune AI models on their local devices without connections to the cloud servers. This can also benefit privacy-sensitive AI applications, such as health care, smart home, and so on.

MobileNetV2
ResNet  1 Figure 6: Transfer learning performances of various ImageNet pre-trained models with the last linear layer trained. The relative accuracy order between different pre-trained models changes significantly among ImageNet and the transfer learning datasets. Figure 6 shows the top1 accuracy of various widely used ImageNet pre-trained models on three transfer datasets by only learning the last layer, which reflects the transferability of their pre-trained weights. The relative order between different pre-trained models is not consistent with their ImageNet accuracy on all three datasets. This result indicates that the ImageNet accuracy is not a good proxy for transferability. Besides, we also find that the same pre-trained model can have very different rankings on different tasks. For instance, Inception-V3 gives poor accuracy on Flowers but provides top results on the other two datasets.
Therefore, we need to specialize the feature extractor to best match the target dataset. In this work, we achieve this by using a pre-trained once-for-all network [10] that comprises many different sub-networks. Specifically, given a pre-trained once-for-all network on ImageNet, we fine-tune it on the target transfer dataset with the weights of the main branches (i.e., MB-blocks) frozen and the other parameters (i.e., biases, lite residual modules, classifier head) updated via gradient descent. In this phase, we randomly sample one sub-network in each training step. The peak memory cost of this phase is 61MB under resolution 224, which is reached when the largest sub-network is sampled. Regarding the computation cost, the average MAC (forward & backward) 4 of sampled sub-nets is (776M + 2510M) / 2 = 1643M per sample, where 776M is the training MAC of the smallest sub-network and 2510M is the training MAC of the largest sub-network. Therefore, the total MAC of this phase is 1643M × 2040 × 0.8 × 50 = 134T on Flowers, where 2040 is the number of total training samples, 0.8 means the once-for-all network is fine-tuned on 80% of the training samples (the remaining 20% is reserved for search), and 50 is the number of training epochs.
Based on the fine-tuned once-for-all network, we collect 500 [sub-net, accuracy] pairs on the validation set (20% randomly sampled training data) and train an accuracy predictor 5 using the collected data [10]. We employ evolutionary search [63] based on the accuracy predictor to find the sub-network that best matches the target transfer dataset. No back-propagation on the once-for-all  Figure 7: On-device training cost on Pets. TinyTL requires 9.9× smaller memory cost (assuming using the same batch size) and 27× smaller computation cost compared to fine-tuning the full MobileNetV2-1.4 [43] while having a better accuracy.
network is required in this step, thus incurs no additional memory overhead. The primary computation cost of this phase comes from collecting 500 [sub-net, accuracy] pairs required to train the accuracy predictor. It only involves the forward processes of sampled sub-nets, and no back-propagation is required. The average MAC (only forward) of sampled sub-nets is (355M + 1182M) / 2 = 768.5M per sample, where 355M is the inference MAC of the smallest sub-network and 1182M is the inference MAC of the largest sub-network. Therefore, the total MAC of this phase is 768.5M × 2040 × 0.2 × 500 = 157T on Flowers, where 2040 is the number of total training samples, 0.2 means the validation set consists of 20% of the training samples, and 500 is the number of measured sub-nets.
Finally, we fine-tune the searched sub-network with the weights of the main branches frozen and the other parameters updated, using the full training set to get the final results. The memory cost of this phase is 66MB under resolution 256 on Flowers. The total MAC is 2190M × 2040 × 1.0 × 50 = 223T, on Flowers, where 2190M is the training MAC, 2040 is the number of total training samples, 1.0 means the full training set is used, and 50 is the number of training epochs.

B Details of the Accuracy Predictor
The accuracy predictor is a three-layer feed-forward neural network with a hidden dimension of 400 and ReLU as the activation function for each layer. It takes the one-hot encoding of the sub-network's architecture as the input and outputs the predicted accuracy of the given sub-network. The inference MAC of this accuracy predictor is only 0.37M, which is 3-4 orders of magnitude smaller than the inference MAC of the CNN classification models. The memory footprint of this accuracy predictor is only 5KB. Therefore, both the computation overhead and the memory overhead of the accuracy predictor are negligible.

C Cost Details
The on-device training cost of TinyTL and FT-Full on Pets is summarized in Figure 7 (left side), while the memory cost breakdown of TinyTL is provided in Figure 7 (right side). Compared to fine-tuning the full MobileNetV2-1.4, TinyTL not only greatly reduces the activation size but also reduces the parameter size (by applying weight quantization on the frozen parameters) and the training cost (by not updating weights of the feature extractor and using fewer training steps). Specifically, TinyTL reduces the memory footprint by 9.9×, and reduces the training computation by 27× without loss of accuracy. Therefore, TinyTL is not only more memory-efficient but also more computation-efficient.


extfieldsofstudy:
Computer Science
Engineering

text:
A Multi-stream Convolutional Neural Network for Micro-expression Recognition Using Optical Flow and EVM

Micro-expression (ME) recognition plays a crucial role in a wide range of applications, particularly in public security and psychotherapy. Recently, traditional methods rely excessively on machine learning design and the recognition rate is not high enough for its practical application because of its short duration and low intensity. On the other hand, some methods based on deep learning also cannot get high accuracy due to problems such as the imbalance of databases. To address these problems, we design a multi-stream convolutional neural network (MSCNN) for ME recognition in this paper. Specifically, we employ EVM and optical flow to magnify and visualize subtle movement changes in MEs and extract the masks from the optical flow images. And then, we add the masks, optical flow images, and grayscale images into the MSCNN. After that, in order to overcome the imbalance of databases, we added a random over-sampler after the Dense Layer of the neural network. Finally, extensive experiments are conducted on two public ME databases: CASME II and SAMM. Compared with many recent state-of-the-art approaches, our method achieves more promising recognition results.

I. INTRODUCTION
Micro-expression refers to a rapid, unconscious, spontaneous facial movement that occurs when experiencing a strong emotion. It usually has a short maintenance time, between 0.2s to 0.04s. Unlike ordinary expressions, spontaneous expressions cannot be faked or suppressed but can reflect people's real emotions so that the reliability of micro-expression in emotion recognition task is very high. Therefore there are many applications of micro-expressions, such as lie detection, negotiating, marketing, distance learning, and so on. However, its duration is short, and change is subtle, usually appearing only either the upper or lower half of the face, but not the whole face [1]. Because of these problems, it is difficult to observe microexpressions correctly.
In the past, methods based on Local Binary Pattern (LBP), optical flow, and machine learning were the main means of micro-expression recognition. They usually use LBP-based or optical flow methods to extract features and then classify them by Support Vector Machine (SVM). Most existing databases [2] [3] use LBP with Three Orthogonal Planes (LBP-TOP) [4] as their primary baseline feature extractor. Wang et al. [5] proposed LBP-SIP that provided a lightweight representation based on three intersecting lines crossing over the center point of LBP-TOP. In addition to the LBP-TOP based approach, there are other approaches, such as, Xu et al. [6] took the optical flow field as the basic feature to describe the motion pattern of micro-expressions and further extracted more simplified expression forms to propose facial dynamic map (FDM).
Additionally, not just traditional machine learning, but deep learning can also be used for micro-expressions. In recent years, CNN has made great achievements in the fields of computer vision. Of course it could also be used for microexpression recognition. Patel et al. [7] proposed a method based on temporal interpolation and CNN. Khor et al. [8] proposed a three-stream neural network and an enrichment method to fuse various features. However, compared with traditional machine learning, deep learning is less used to recognize micro-expression. And there are some problems to be solved in these CNN models, such as the imbalance of databases, and the inputs need to be more effective features rather than just video sequences or optical flows (dynamic features) or grayscale images (static features).
To solve these problems, in this paper, we propose a method based on deep learning for micro-expression recognition. Firstly, we use EVM to magnify micro-expression. And then we use the optical flow calculation method [9] proposed by Bob et al. to get the optical flow that contain information about the movements of facial muscles. After that, the optical flow images obtained are binarized with 50 as the threshold to obtain masks. After this step, we add the masks to the grayscale images to get the local areas of the face that have motion changes. At last, we input optical flow images (dynamic features), original gray images (static features) and the gray images which are covered by the masks (local features) into the multi-stream convolutional neural network proposed by ourselves. Different from the previous multi-stream neural network [8], we add an over-sampler after the network's final Dense Layer to deal with the problem of imbalanced databases.
Our main contributions are summarized as follows: • We combine EVM and optical flow method to process micro-expression. Comparing to using only one of the  two, our method has higher accuracy. • We propose a method to extract local features of motion and reduce data redundancy. • We attempt to deal with the imbalance problem by adding an over-sampler inside the neural network The rest of this paper is organized as follows. Section II presents our proposed method, and it is divided into two subsections to describe two modules: preprocessing and CNN. The preprocessing module includes steps such as extracting features and extending databases, while the other module determines some parameters of the deep network. Then we discuss two related databases and the experimental results for algorithm evaluation in Section III. Finally, Section IV concludes this work.

II. PROPOSED METHOD
In this section, we will introduce our proposed method of recognizing micro-expressions. Figure 1 summarizes the proposed framework with the preprocessing module and learning module.

A. Pre-processing
The micro-expression videos are first preprocessed using Eulerian Video Magnification (EVM), which could magnify the expression, makes it easier to recognize. However, the linear EVM method will amplify the noise while amplifying the changes in the movement so that we need a reasonable amplification factor α, and we will discuss this parameter in Section III.
After using EVM to magnify expressions, we used the optical flow calculation method proposed by Liu et al. [9] to calculate optical flow. They calculate dense optical flow, which computes the motion of each pixel, and the objective function shows in (1). The image lattice is represented as p = (x, y, t) and flow is w(p) = (u(p), v(p), 1), ψ(·) and φ(·) are robust functions.
Then we will get the optical flow of Figure 2(b) and Figure  2(a), the visual image is shown in Figure 2(c). In our proposed method, we use the onset frame, apex frame, and apex frame to generate optical flow.
Xia et al. [10] proposed a method to extract mask based on the heatmap. The mask produced by this method included both the upper and lower parts of the face, whereas ME usually appeared on only half the face [1]. So we binarized the optical flow image with a threshold value of 50 to get a mask, this method will only extract the moving part, as the Figure 2(d) shows. This mask is used to be added to the apex frame of a video sequence, and it can extract the effective areas of motion in the image and remove some redundancy. The result is shown in Figure 2(e).
Due to the small number of ME database samples will lead to bad robustness, to improve the robustness of the model and the reliability of the results, in the last step of preprocessing, we expand the training samples, using horizontal inversion and clockwise/counterclockwise rotation of 5°/10°to expand the number of samples by 10 times.

B. Convolutional Neural Network (CNN)
In this paper, we use Resnet-18 [11] to learn training data. It takes images size of 224 × 224 and batch normalization is carried out before each convolutional layer for faster training convergence. All convolutional and fully connected layers adopt Rectified Linear Unit (ReLU) as the activation function. Micro-expressions often overfit because of its small databases, so here we use Early Stopping to mitigate these overfitting  problems. The classifier we used is Softmax, then we used a mini-batch size of 64, and the maximum epoch is 200. The learning rate is 10 −3 , and momentum is 0.9. The weight decay is 5 × 10 −4 , and optimizer is SGD. The network's three inputs are optical flow images (O ∈ R 3 ), gray-scale raw images (G ∈ R 2 ) and gray-scale images that are covered by masks (M ∈ R 2 ).

A. Databases and experiment setting
At present, the commonly used databases of ME are CASME-II [2] from Chinese academy of sciences and SAMM database [3]. CASME-II is a comprehensive spontaneous ME database containing 247 video samples, elicited from 26 Asian participants, and it is obtained using a high-speed camera of 200 frames per second. In order to ensure the reliability of the data set, CASME-II induced the subjects' emotions by watching videos, and if the subjects successfully suppressed their emotions without being noticed by the record, they could receive a cash reward.
The SAMM database has 159 micro-expressions from 29 subjects. It has the same frame rate as CASME-II, and its induction mechanism is also similar to that of CASME-II. CASME-II and SAMM have coded both emotions and FACS for each expression. CASME-II is divided into five emotion classes while SAMM is divided into eight emotion classes, but in order to be consistent with CASME-II, we only select the five classes with the largest number of samples for the experiment. Information about these two databases can be seen in TableI.
In order to avoid too much distortion, we need to set a reasonable amplification factor α. To find the best α for EVM, we tried several different sets of values and calculated the optical flow of the CASME-II database under this value. The final results are shown in Figure 3(a). As we can see, the best result is obtained when the parameter is 8.

B. Comparison Results on CASME-II and SAMM
We evaluated our approach on two spontaneous facial ME databases: CASME-II and SAMM using the Leave-One-Subject-Out (LOSO) cross validation as this protocol prevents subject bias during learning. Table II, III compares the performance of our proposed approach with the baseline LBP-TOP approach and some recent and related works. The confusion matrix is shown in Figure 4. It can be seen that our method has the highest accuracy and F1-Score among these methods, which is not only superior to some of the previously mentioned deep learning methods but also higher than some traditional machine learning methods. And for the SAMM database, we got a result that is lower than CASME-II, and the result of the multi-stream neural network is not as good as that of single-stream optical flow, and this may be because the SAMM database is relatively small, resulting in poor results of the other two streams, which will also lower the performance of optical flow after feature fusion. However, since this oversampler is a random over-sampler, it may cause overfitting, so it does not perform well in the SAMM database.
To overcome the imbalance of databases, we added the oversampler, to verify the validity of this step, we compared the results obtained by no sampler with those obtained by a threeflow neural network adding a sampler based on CASME-II, as is shown in the Figure 3(b). However, since this over-sampler is a random over-sampler, it may cause overfitting, so it does not perform well in the SAMM database.
For further analysis, we also analyzed the different singlestream and double-stream inputs. These are carried out using both the CASME-II database and SAMM database, and are shown in Figure 3(c), 3(d), 3(e), 3(f).

IV. CONCLUSION
In this paper, we propose a MSCNN for ME recognition using optical flow and EVM. Firstly, the architecture of MSCNN is suitable for dealing with MEs recognition problem, because it can fuse different features, get more effective information. Secondly, it is clear that we use EVM, optical flow and a mask to extract feature, when α is 8, which benefit distinguishing MEs as well. Finally, we add an oversampler to reduce the effect of imbalanced database. Through experiments, we find that MSCNN has better performance than other methods mentioned. In the future, we will try to use some other oversamplers, such as SMOTE, ADASYN over-sampler and so on. In addition, we will focus on a network structure more suitable for ME recognition than the residual network.