Browsing by Author "Lai, Yuan-Cheng"

Now showing 1 - 20 of 95

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 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.
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 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.
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.
Booting, browsing and streaming time profiling, and bottleneck analysis on android-based systems
(2013-07-01)
Lin, Ying-Dar
;
Ho, Cheng-Yuan
;
Lai, Yuan-Cheng
;
Du, Tzu-Hsiung
;
Chang, Shun-Lee
Android-based systems perform slowly in three scenarios: booting, browsing, and streaming. Time profiling on Android devices involves three unique constraints: (1) the execution flow of a scenario invokes multiple software layers, (2) these software layers are implemented in different programming languages, and (3) log space is limited. To compensate for the first and second constraints, we assumed a staged approach using different profiling tools applied to different layers and programming languages. As for the last constraint and to avoid generating enormous quantities of irrelevant log data, we began profiling scenarios from an individual module, and then iteratively profiled an increased number of modules and layers, and finally consolidated the logs from different layers to identify bottlenecks. Because of this iteration, we called this approach a staged iterative instrumentation approach. To analyze the time required to boot the devices, we conducted experiments using off-the-shelf Android products. We determined that 72% of the booting time was spent initializing the user-space environment, with 44.4% and 39.2% required to start Android services and managers, and preload Java classes and resources, respectively. Results from analyzing browsing performance indicate that networking is the most significant factor, accounting for at least 90% of the delay in browsing. With regard to online streaming, networking and decoding technologies are two most important factors occupying 77% of the time required to prepare a 22 MB video file over a Wi-Fi connection. Furthermore, the overhead of this approach is low. For example, the overhead of CPU loading is about 5% in the browsing scenario. We believe that this proposed approach to time profiling represents a major step in the optimization and future development of Android-based devices. (c) 2013 Elsevier Ltd. All rights reserved.
Browser Fuzzing by Scheduled Mutation and Generation of Document Object Models
(2015-01-01)
Lin, Ying-Dar
;
Liao, Feng-Ze
;
Huang, Shih-Kun
;
Lai, Yuan-Cheng
;
資訊工程學系
Internet applications have made our daily life fruitful. However, they also cause many security problems if these applications are leveraged by intruders. Thus, it is important to find and fix vulnerabilities timely to prevent application vulnerabilities from being exploited. Fuzz testing is a popular methodology that effectively finds vulnerabilities in application programs with seed input mutation. However, it is not a satisfied solution for the web browsers. In this work, we propose a solution, called scheduled DOM fuzzing (SDF), which integrates several related browser fuzzing tools and the fuzzing framework called BFF. To explore more crash possibilities, we revise the browser fuzzing architecture and schedule seed input selection and mutation dynamically. We also propose two probability computing methods in scheduling mechanism which tries to improve the performance by determining which combinations of seed and mutation would produce more crashes. Our experiments show that SDF is 2.27 time more efficient in terms of the number of crashes and vulnerabilities found at most. SDF also has the capacity for finding 23 exploitable crashes in Windows 7 within five days. The experimental results reveals that a good scheduling method for seed and mutations in browser fuzzing is able to find more exploitable crashes than fuzzers with the fixed seed input.
Bug Traces: Identifying and Downsizing Packet Traces with Failures Triggered in Networking Devices
(2014-04-01)
Lin, Ying-Dar
;
Lu, Chun-Nan
;
Lai, Yuan-Cheng
;
Eliezer, Zongo Pawendtaore
;
交大名義發表
Testing networking devices before releasing them onto the market is a way of ensuring quality and robustness. Replaying artificial or real-world traffic is a method to test networking devices. Using real-world traffic is desirable as it uncovers more realistic properties. The challenges of testing with real-world traffic are mainly the high volume of the captured traces and the prolonged time required for replay testing. In order to efficiently reproduce the failures of networking devices and reduce the replay time, it is necessary to reduce the size of the traces that have triggered the failures. In this work, two algorithms used to downsize the traces but still retain the failures they triggered, Binary Downsizing (BD) and Linear Downsizing (LD), are proposed. Meanwhile, a metric called downsizing ratio (DR), the ratio between the size of the downsized traces and that of the original traces, is defined in order to evaluate the efficiency of the trace downsizing. Three kinds of probes following the basic RFC benchmarking requirements, ARP, ICMP, and HTTP requests, are regularly sent to diagnose the devices during the testing. ARP and ICMP probes test the reachability of a networking device hosted on the local network, and HTTP probes check if the device still responds to users\' requests. The evaluation of failure distribution shows that 70 percent of failures happened because they failed to respond to one of the three probes, 23 percent failed to respond to two probes, and 7 percent failed to respond to all probes. From the downsizing experiments, LD was inferred to have a slightly higher DR than that of BD, but BD generally would require fewer iterations than LD.
Calibrating parameters and formulas for process-level energy consumption profiling in smartphones
(2014-09-01)
Lin, Ying-Dar
;
Rattagan, Ekarat
;
Lai, Yuan-Cheng
;
Chang, Li-Pin
;
Yo, Yun-Chien
Battery-powered mobile devices substantially constrain energy resources. Process-level energy profiling tools can identify the most energy-consuming process and detail the energy usage of hardware components. With the help of energy profiling tools, programmers can fine-tune the energy consumption of processes to extend battery lifetime. However, profiling tools are highly dependent on hardware and must be calibrated for each hardware platform. Furthermore, for any new hardware components, new energy estimation formulas must be created. To solve these two problems regarding off-the-shelf products, this work proposes a two-phase calibrating approach. The first phase reconstructs the power table with a power meter, while the second creates new energy estimation formulas using linear regression analysis. The accuracy of the calibrated tool was evaluated in five scenarios and its error ratio is proven to be below 10%, occasionally less than 5%. Hence, this proposed approach to energy consumption profiling represents a major step in off-the-shelf devices. (C) 2014 Elsevier Ltd. All rights reserved.