Browsing by Author "Lin, Ying-Dar"

Now showing 1 - 20 of 172

A Fast Scalable Automaton-Matching Accelerator for Embedded Content Processors
(2009-04-01)
Tseng, Kuo-Kun
;
Lai, Yuan-Cheng
;
Lin, Ying-Dar
;
Lee, Tsern-Huei
;
資訊工程學系
Home and office network gateways often employ a cost-effective embedded network processor to handle their network services. Such network gateways have received strong demand for applications dealing with intrusion detection, keyword blocking, antivirus and antispam. Accordingly, we were motivated to propose an appropriate fast scalable automaton-matching (FSAM) hardware to accelerate the embedded network processors. Although automaton matching algorithms are robust with deterministic matching time, there is still plenty of room for improving their average-case performance. FSAM employs novel prehash and root-index techniques to accelerate the matching for the nonroot states and the root state, respectively, in automation based hardware. The prehash approach uses some hashing functions to pretest the input sub-string for the nonroot states while the root-index approach handles multiple bytes in one single matching for the root state. Also, FSAM is applied in a prevalent automaton algorithm, Aho-Corasick (AC), which is often used in many content-filtering applications. When implemented in FPGA, FSAM can perform at the rate of 11.1Gbps with the pattern set of 32,634 bytes, demonstrating that our proposed approach can use a small logic circuit to achieve a competitive performance, although a larger memory is used. Furthermore, the amount of patterns in FSAM is not limited by the amount of internal circuits and memories. If the high-speed external memories are employed, FSAM can support up to 21,302 patterns while maintaining similar high performance.
A Fast-Converging TCP-Equivalent Window-Averaging Rate Control Scheme
(2012)
Tsao, Shih-Chiang
;
Lai, Yuan-Cheng
;
Lin, Ying-Dar
;
資訊工程學系
;
Department of Computer Science
Smooth rate control schemes are necessary for Internet streaming flows to use available bandwidth. To equally share the Internet bandwidth with existing Transmission Control Protocol (TCP) flows, these new schemes should meet TCP-equivalent criterion, i.e., achieve the same transmission rates as TCP under the same network conditions. However, when the available bandwidth oscillates, many of these schemes fail to meet this criterion due to their slow increasing rate. This study proposes a window-averaging rate control (WARC) scheme to send packets at the same average rate as a TCP flow over a fixed time interval. Considering the TCP rate only over a fixed interval allows WARC to forget the historical loss condition more rapidly than other schemes, thus achieving a faster increasing rate when additional bandwidth becomes available. When the available bandwidth drops dramatically, WARC uses a history-reset procedure to converge its rate to the new steady rate immediately after a specified number of losses. The simulations in this study show that WARC not only achieves the same bandwidth as TCP, but exhibits faster convergent behaviors and has a smoother rate than existing schemes.
A fuzzy pattern-based filtering algorithm for botnet detection
(2011-10-27)
Wang, Kuochen
;
Huang, Chun-Ying
;
Lin, Shang-Jyh
;
Lin, Ying-Dar
;
資訊工程學系
Botnet has become a popular technique for deploying Internet crimes. Although signature-based bot detection techniques are accurate, they could be useless when bot variants are encountered. Therefore, behavior-based detection techniques become attractive due to their ability to detect bot variants and even unknown bots. In this paper, we propose a behavior-based botnet detection system based on fuzzy pattern recognition techniques. We intend to identify hot-relevant domain names and IP addresses by inspecting network traces. If domain names and IP addresses used by botnets can be identified, the information can be further used to prevent protected hosts from becoming one member of a botnet. To work with fuzzy pattern recognition techniques, we design several membership functions based on frequently observed bots' behavior including: (1) generate failed DNS queries; (2) have similar DNS query intervals; (3) generate failed network connections; and (4) have similar payload sizes for network connections. Membership functions can be easily altered, removed, or added to enhance the capability of the proposed system. In addition, to improve the overall system performance, we develop a traffic reduction algorithm to reduce the amount of network traffic required to be inspected by the proposed system. Performance evaluation results based on real traces show that the proposed system can reduce more than 70% input raw packet traces and achieve a high detection rate (about 95%) and a low false positive rates (0-3.08%). Furthermore, the proposed FPRF algorithm is resource-efficient and can identify inactive botnets to indicate potential vulnerable hosts. (C) 2011 Elsevier B.V. All rights reserved.
A Hybrid Algorithm of Backward Hashing and Automaton Tracking for Virus Scanning
(2011-04-01)
Lin, Po-Ching
;
Lin, Ying-Dar
;
Lai, Yuan-Cheng
;
資訊工程學系
;
Department of Computer Science
Virus scanning involves computationally intensive string matching against a large number of signatures of different characteristics. Matching a variety of signatures challenges the selection of matching algorithms, as each approach has better performance than others for different signature characteristics. We propose a hybrid approach that partitions the signatures into long and short ones in the open-source ClamAV for virus scanning. An algorithm enhanced from the Wu-Manber algorithm, namely the Backward Hashing algorithm, is responsible for only long patterns to lengthen the average skip distance, while the Aho-Corasick algorithm scans for only short patterns to reduce the automaton sizes. The former utilizes the bad-block heuristic to exploit long shift distance and reduce the verification frequency, so it is much faster than the original WM implementation in ClamAV. The latter increases the AC performance by around 50 percent due to better cache locality. We also rank the factors to indicate their importance for the string matching performance.
A Joint Network and Server Load Balancing Algorithm for Chaining Virtualized Network Functions
(2016)
Minh-Tuan Thai
;
Lin, Ying-Dar
;
Lai, Yuan-Cheng
;
交大名義發表
;
National Chiao Tung University
Chaining virtualized network functions (VNF) is an effective practice to deploy network services in network operator\'s data centers. Two common concerns arise in such a deployment arc network load balancing and server load balancing. In this study, motivated by the argument that such two concerns should be jointly addressed for efficiently chaining VNFs in a data center environment, we propose a 2-phase algorithm, Nearest First and Local-Global Transformation (NF-LGT), which concurrently supports network and service load balancing. The algorithm firstly constructs service chains by a greedy strategy which both considers network latency and server latency. Then a searching technique is applied to improve the solutions. We have implemented the algorithm using Software-defined networking (SDN)/OpenFlow concept. The experimental results indicate that, compared with a sequential approach, NF-LGT improves the system bandwidth utilization up to 45%.
A latency and modulation aware bandwidth allocation algorithm for WiMAX base stations
(2008)
Lin, Yi-Neng
;
Wu, Che-Wen
;
Lin, Ying-Dar
;
Lai, Yuan-Cheng
;
交大名義發表
The mobile WiMAX systems based on IEEE 802.16e-2005 provide high data rate for the mobile wireless network. However, the link quality is frequently unstable owing to the long-distance and air interference and therefore impacts real-time applications. Thus, a bandwidth allocation algorithm. IS required to be modulation-aware, while further satisfying the latency guarantee, service differentiation and fairness. This work proposes the Highest Urgency First (HUF) algorithm to conquer the above challenges by taking into consideration the adaptive modulation and coding scheme (MCS) and the urgency of requests. Downlink and uplink sub-frames are determined by reserving the bandwidth for the most urgent requests am: proportionating the remaining bandwidth for others. Then independently in the downlink and uplink, the HUF allocates bandwidth to every mobile station according to a pre-calculated U-factor which considers urgency, priority and fairness. Simulation results prove the HUF is modulation-aware and achieves the above three objectives, notably the zero violation rate within system capacity as well as the throughput paralleling to the best of the existing approaches.
A platform-based SoC design and implementation of scalable automaton matching for deep packet inspection
(2007-12-01)
Lin, Ying-Dar
;
Tseng, Kuo-Kun
;
Lee, Tsern-Huei
;
Lin, Yi-Neng
;
Hung, Chen-Chou
String matching plays a central role in packet inspection applications such as intrusion detection, anti-virus, anti-sparn and Web filtering. Since they are computation and memory intensive, software matching algorithms are insufficient to meet the high-speed performance. Thus, offloading packet inspection to a dedicated hardware seems inevitable. This paper presents a scalable automaton matching (SAM) coprocessor that uses Aho-Corasick (AC) algorithm with two parallel acceleration techniques, root-indexing and pre-hashing. The root-indexing can match multiple bytes in one single matching, and the pre-hashing can be used to avoid bitmap, AC matching which is a cycle-consuming operation. In the platform-based SoC implementation of the Xilinx ML310 FPGA, the proposed hardware architecture can achieve almost 10.7 Gbps and support over 10,000 patterns for virus, which is the largest pattern set from among the existing works. On the average, the performance of SAM is 7.65 times faster than the original bitmap AC. Furthermore, SAM is feasible for either internal or external memory architecture. The internal memory architecture provides high performance, while the external memory architecture provides high scalability in term of the number of patterns. (C) 2007 Elsevier B.V. All rights reserved.
A scalable and accurate distributed traffic generator with Fourier transformed distribution over multiple commodity platforms
(2019-10-15)
Chang, Ching-Hao
;
Lin, Ying-Dar
;
Lai, Yu-Kuen
;
Lai, Yuan-Cheng
;
資訊工程學系
The rapid growth of high-speed computer networks poses a challenge in the design of testing and verification equipment. The hardware-based packet generators that are often used in the verification process are accurate but costly. Software-based packet generators, on the other hand, are relatively low-cost but have a limited performance with low accuracy. This paper proposes a Fourier-based profile decomposition and formulation methodology for a distributed packet generating system, featuring good horizontal scalability and high accuracy. Different from traditional software-based packet generators, this proposed system extracts the traffic components from a specific traffic distribution applying Fourier transformation to generate traffic components. These traffic components are distributed to one or more worker nodes for packet generation, and thus achieving higher aggregated traffic rate in any given distribution. The system design is based on the Data Plane Development Kits (DPDK) framework to maximize the traffic generation performance. The accuracy and performance of the proposed system scale according to the number of worker nodes used. Currently, with multiple CPU cores and five workers, the proposed system can generate aggregated traffic of more than 40 Gbps in a Poisson distribution.
Accelerating web content filtering by the early decision algorithm
(2008-02-01)
Lin, Po-Ching
;
Liu, Ming-Dao
;
Lin, Ying-Dar
;
Lai, Yuan-Cheng
;
資訊工程學系
Real-time content analysis is typically a bottleneck in Web filtering. To accelerate the filtering process, this work presents a simple, but effective early decision algorithm that analyzes only part of the Web content. This algorithm can make the filtering decision, either to block or to pass the Web content, as soon as it is confident with a high probability that the content really belongs to a banned or an allowed category. Experiments show the algorithm needs to examine only around one-fourth of the Web content on average, while the accuracy remains fairly good: 89% for the banned content and 93% for the allowed content. This algorithm can complement other Web filtering approaches, such as URL blocking, to filter the Web content with high accuracy and efficiency. Text classification algorithms in other applications can also follow the principle of early decision to accelerate their applications.
Active versus Passive Malware Collection
(2014-04-01)
Lin, Ying-Dar
;
Lee, Chia-Yin
;
Wu, Yu-Sung
;
Ho, Pei-Hsiu
;
Wang, Fu-Yu
An exploration of active and passive malware honeypots reveals that the two systems yield vastly different malware collections and that peer-to-peer file sharing is an important, but often overlooked, malware source.
An early decision algorithm to accelerate web content filtering
(2006)
Lin, Po-Ching
;
Liu, Ming-Dao
;
Lin, Ying-Dar
;
Lai, Yuan-Cheng
;
資訊工程學系
Real-time content analysis can be a bottleneck in Web filtering. This work presents a simple, but effective early decision algorithm to accelerate the filtering process by examining only part of the Web content. The algorithm can make the filtering decision, either to block or to pass the Web content, as soon as it is confident with a high probability that the content should belong to a banned or an allowable category. The experiments show the algorithms can examine only around one-fourth of the Web content on average, while the accuracy remains fairly good: 89% in the banned content and 93% in the allowable content. This algorithm can complement other Web filtering approaches to filter the Web content with high efficiency.
An Extended SDN Architecture for Network Function Virtualization with a Case Study on Intrusion Prevention
(2015-05-01)
Lin, Ying-Dar
;
Lin, Po-Ching
;
Yeh, Chih-Hung
;
Wang, Yao-Chun
;
Lai, Yuan-Cheng
In conventional software-defined networking (SDN), a controller classifies the traffic redirected from a switch to determine the path to network function virtualization (NFV) modules. The redirection generates a large volume of control-plane traffic. We propose an extended SDN architecture to reduce the traffic overhead to the controller for providing NFV. The extension includes two-layer traffic classification in the data plane, extended OpenFlow protocol messages and service chaining mechanisms. Network events are analyzed in the data plane instead of the control plane. The efficiency is evaluated with a case study of intrusion prevention. The evaluation shows that only 0.12 percent of the input traffic is handled by the controller, while 77.23 percent is handled on the controller in conventional SDN.
Analytical Model For Power Savings in LTE Networks using DRX Mechanism
(2015)
Varma, Syama R.
;
Sivalingam, Krishna M.
;
Tung, Li-Ping
;
Lin, Ying-Dar
;
資訊工程學系
This paper presents an analytical model, based on a semi-Markov process, for determining the power savings achieved in a User Equipment (UE) device of a Long Term Evolution (LTE) network using the Discontinuous Reception (DRX) mechanism. Systems with and without packet buffers and the UE and enodeB are presented in this paper. Using the models, it is possible to determine the savings in power attainable by the UE when different DRX sleep cycles and timers are used. The analytical models has been validated using a discrete-event simulation model. The numerical results show that it is possible to obtain UE power savings of up to 63%.
Analytical Modelling of Software and Hardware Switches with Internal Buffer in Software-Defined Networks
(2019-06-15)
Singh, Deepak
;
Ng, Bryan
;
Lai, Yuan-Cheng
;
Lin, Ying-Dar
;
Seah, Winston K. G.
Open Flow supports internal buffering of data packets in Software-Defined Networking (SDN) switch whereby a fraction of data packet header is sent to the controller instead of an entire data packet. This internal buffering increases the robustness and the utilization of the link between SDN switches and the controller by absorbing temporary burst of packets which may overwhelm the controller. Existing queuing models for an SDN have focused on the switches that immediately sends packets to the controller for decisioning, with no existing models investigating the impact of the internal buffer in SDN software and hardware switches. In this paper, we propose a unified queueing model to characterise the performance of SDN software and hardware switches with the internal buffer. This unified queueing model is an analytical tool for network engineers to predict a delay and loss during SDN deployments in delay and loss sensitive environments. Our results show that a hardware switch achieves up to 80% lower average packet transfer delay and 99% lower packet loss rate at the cost of requiring up to 50% more queue capacity than a software switch. The proposed models are validated with a discrete event simulation, where the error between 0.6% and 2.8% was observed for both average packet transfer delay and average packet loss rate. Moreover, a hardware switch outperforms a software switch with increasing number of hosts per switch suggesting that a hardware switch has better scalability. We use the insights from the model to develop guidelines that help network engineers decide between a software and hardware switch in their SDN deployments.
Apparatus, system and method for stream-based data filtering
(2008-01-03)
Lin, Po-Ching
;
Lin, Ying-Dar
;
Chen, Szu-Hao
;
Lai, Yuan-Cheng
An apparatus, a system and a method for stream-based data filtering are disclosed. The apparatus is for filtering data transmitted from a sending end. The data is transmitted one by one by using a plurality of data segments. The data filtering apparatus includes a receiving module, a processing module and a transmission module. The receiving module is for receiving the data segments transmitted from the sending end. The processing module implements virus scanning for the data segments one by one. The transmission module then transmits the data segments which have passed through the virus scanning to a receiving end.
Application classification using packet size distribution and port association
(2009-09-01)
Lin, Ying-Dar
;
Lu, Chun-Nan
;
Lai, Yuan-Cheng
;
Peng, Wei-Hao
;
Lin, Po-Ching
Traffic classification is an essential part in common network management applications such as intrusion detection and network monitoring. Identifying traffic by looking at port numbers is only suitable to well-known applications, while signature-based classification is not applicable to encrypted messages. Our preliminary observation shows that each application has distinct packet size distribution (PSD) of the connections. Therefore, it is feasible to classify traffic by analyzing the variances of packet sizes of the connections without analyzing packet payload. Ill this work, each connection is first transformed into a point in a multi-dimensional space according to its PSD. Then it is compared with the representative points of pre-defined applications and recognized as the application having a minimum distance. Once a connection is identified as a specific application, Port association is used to accelerate the classification by combining it with the other connections of the same session because applications usually use consecutive ports during a session. Using the proposed techniques, packet size distribution and port association, a high accuracy rate, 96% oil average, and low false positive and false negative rates, 4-5%, are achieved. Our proposed method not only works well for encrypted traffic but also can be easily incorporated with a signature-based method to provide better accuracy. (C) 2009 Elsevier Ltd. All rights reserved.
Application Performance Profiling in Android Dalvik Virtual Machines
(2016-05-01)
Chang, Hung-Cheng
;
Chang, Kuei-Chung
;
Lin, Ying-Dar
;
Lai, Yuan-Cheng
;
資訊工程學系
Most Android applications are written in JAVA and run on a Dalvik virtual machine. For smartphone vendors and users who wish to know the performance of an application on a particular smartphone but cannot obtain the source code, we propose a new technique, Dalvik Profiler for Applications (DPA), to profile an Android application on a Dalvik virtual machine without the support of source code. Within a Dalvik virtual machine, we determine the entry and exit locations of a method, log its execution time, and analyze the log to determine the performance of the application. Our experimental results show an error ratio of less than 5% from the baseline tool Traceview which instruments source code. The results also show some interesting behaviors of applications and smartphones: the performance of some smartphones with higher hardware specifications is 1.5 times less than the phones with lower specifications. DPA is now publicly available as an open source tool.
Balanced Service Chaining in Software-Defined Networks with Network Function Virtualization
(2016-11)
Lin, Po-Ching
;
Lin, Ying-Dar
;
Wu, Cheng-Ying
;
Lai, Yuan-Cheng
;
Kao, Yi-Chih
Balanced Hash Tree (BHT) is a mechanism for service function (SF) chaining, service routing, and traffic steering that enables switches to select SF instances for load balancing without involving the controller. In an experimental evaluation, BHT decreased packet-in message-processing time by 92.5 percent and achieved near-perfect load-balancing performance.
Behavior-based botnet detection in parallel
(2014-11-01)
Wang, Kuochen
;
Huang, Chun-Ying
;
Tsai, Li-Yang
;
Lin, Ying-Dar
;
資訊工程學系
Botnet has become one major Internet security issue in recent years. Although signature-based solutions are accurate, it is not possible to detect bot variants in real-time. In this paper, we propose behavior-based botnet detection in parallel (BBDP). BBDP adopts a fuzzy pattern recognition approach to detect bots. It detects a bot based on anomaly behavior in domain name service (DNS) queries and transmission control protocol (TCP) requests. With the design objectives of being efficient and accurate, a bot is detected using the proposed five-stage process, including: (i) traffic reduction, which shrinks an input trace by deleting unnecessary packets; (ii) feature extraction, which extracts features from a shrunk trace; (iii) data partitioning, which divides features into smaller pieces; (iv) DNS detection phase, which detects bots based on DNS features; and (v) TCP detection phase, which detects bots based on TCP features. The detection phases, which consume approximately 90% of the total detection time, can be dispatched to multiple servers in parallel and make detection in real-time. The large scale experiments with the Windows Azure cloud service show that BBDP achieves a high true positive rate (95%+) and a low false positive rate (approximate to 3%). Meanwhile, experiments also show that the performance of BBDP can scale up linearly with the number of servers used to detect bots. Copyright (c) 2013 John Wiley & Sons, Ltd.
Benchmarking handheld graphical user interface: Smoothness quality of experience
(2018-05-01)
Lin, Ying-Dar
;
Chu, Edward T. -H.
;
Wen, Chien-Ling
;
Lai, Yuan-Cheng
;
Chen, I-Ching
With the rapid growth of smartphones in the market, the smoothness of smartphones, how quickly and well smartphones react to a user's input, becomes a crucial factor consumers consider when making buying decisions. However, there is no benchmark for comparing the smoothness of one phone against another. In this paper, a handheld smoothness evaluation over regression (HSER) model was developed to make a fair evaluation. A video was first made and the several key indexes were extracted to represent behavior-based smoothness quality of services (BQoS). We built up a relationship between BQoS and behavior-based smoothness quality of experience (BQoE), and converted BQoE to handheld smoothness quality of experience. Our experiment results show that maximal frame interval and number of frame intervals are the two most critical indexes that indicate smoothness. The proposed HSER model is able to fairly evaluate the smoothness of smartphones because the error rate of the HSER model is less than 9% for a single behavior.