Browsing by Author "Lin, Po-Ching"

Now showing 1 - 20 of 24

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.
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.
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.
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.
Deep Packet Inspection: Algorithms, Hardware, and Applications
(2014-10-01)
Lin, Ying-Dar
;
Lin, Po-Ching
;
Prasanna, Viktor K.
;
Chao, H. Jonathan
;
Lockwood, John W.
Designing an integrated architecture for network content security gateways
(2006-11-01)
Lin, Ying-Dar
;
Jan, Chih-Wei
;
Lin, Po-Ching
;
Lai, Yuan-Cheng
;
資訊工程學系
Increasing computer processing power has made it economically feasible to integrate multiple functions into a single gateway, but the industry remains divided over whether that is preferable to an all- in- one solution. Researchers in this area have primarily focused on enhancing performance. Little research, however, has examined integrated content security architectures. To address this issue, the authors integrated five popular open source content security packages. Using a set of external and internal benchmarks, they compared packet-flow performance during content inspection by combining a loosely integrated arrangement with a tightly integrated content security gateway. Their research indicated that this new architecture substantially reduces overhead in interprocess communications and kernel/ user space interactions. The study also revealed that the main bottlenecks of content processing are string matching in Web filtering and RAM disk access in mail processing.
Evasion Techniques: Sneaking through Your Intrusion Detection/Prevention Systems
(2012)
Cheng, Tsung-Huan
;
Lin, Ying-Dar
;
Lai, Yuan-Cheng
;
Lin, Po-Ching
;
資訊工程學系
Detecting attacks disguised by evasion techniques is a challenge for signature-based Intrusion Detection Systems (IDSs) and Intrusion Prevention Systems (IPSs). This study examines five common evasion techniques to determine their ability to evade recent systems. The denial-of-service (DoS) attack attempts to disable a system by exhausting its resources. Packet splitting tries to chop data into small packets, so that a system may not completely reassemble the packets for signature matching. Duplicate insertion can mislead a system if the system and the target host discard different TCP/IP packets with a duplicate offset or sequence. Payload mutation fools a system with a mutative payload. Shellcode mutation transforms an attacker's shellcode to escape signature detection. This study assesses the effectiveness of these techniques on three recent signature-based systems, and among them, explains why Snort can be evaded. The results indicate that duplicate insertion becomes less effective on recent systems, but packet splitting, payload mutation and shellcode mutation can be still effective against them.
Extracting Attack Sessions from Real Traffic with Intrusion Prevention Systems
(2009)
Chen, I-Wei
;
Lin, Po-Ching
;
Luo, Chi-Chung
;
Cheng, Tsung-Huan
;
Lin, Ying-Dar
False Positive (FP) and False Negative (FN) happen to every Intrusion Prevention System (IPS). No one could do better judgment than others all the time. This work proposes a system of Attack Session Extraction (ASE) to create a pool of suspicious traffic traces which cause potential FNs (abbreviated as P-FNs) and potential FPs (abbreviated as P-FPs) to IPSes. Developers of IPSes can use these suspicious traffic traces to improve the accuracy of their products. Traffic traces are called suspicious since what they cause are P-FNs and P-FPs which need to be confirmed by the developers of IPSes whether P-FNs are FNs and P-FPs are FPs. First, the ASE captures real traffic and replays captured traffic traces to multiple IPSes. By comparing the logs of IPSes, we can find that some attack logs are logged or not logged only at certain IPS. The former is P-FPs, while the latter is P-FNs to that IPS. The ASE then starts to extract this suspicious traffic from replayed traffic traces. The extracted traffic traces can then be used for further analysis by IPS developers. Some of the traces may prove to be guilty, i.e. confirmed to be FNs and FPs. To completely extract a suspicious session, the ASE uses an association mechanism based on anchor packets, five-tuple and time, and similarity for the first packet, first connection, and whole session, respectively. It calculates the degree of similarity among packets to extract a suspicious session containing multiple connections. We define variation and completeness/purity as the performance indexes to evaluate ASE. The experiments demonstrate that 95% of extracted sessions have low variation, and the average completeness/purity is around 80%.
HARDWARE-SOFTWARE CODESIGN FOR HIGH-SPEED SIGNATURE-BASED VIRUS SCANNING
(2009-09-01)
Lin, Ying-Dar
;
Lin, Po-Ching
;
Lai, Yuan-Cheng
;
Liu, Tai-Ying
;
資訊工程學系
HIGH-SPEED NETWORK CONTENT SECURITY APPLICATIONS OFTEN OFFLOAD SIGNATURE MATCHING TO HARDWARE. IN SUCH SYSTEMS, THE THROUGHPUT OF THE OVERALL SYSTEM, RATHER THAN THE HARDWARE ENGINE ALONE, IS SIGNIFICANT. THE AUTHORS OFFLOAD VIRUS SCANNING IN THE CLAMAV ANTIVIRUS PACKAGE TO THE BFAST* HARDWARE ENGINE. THEY FIND THAT THE DATA-PASSING PROCESSES SIGNIFICANTLY DEGRADE SYSTEM THROUGHPUT.
kP2PADM: An In-Kernel Architecture of P2P Management Gateway
(2008-10-01)
Lin, Ying-Dar
;
Lin, Po-Ching
;
Tsai, Meng-Fu
;
Chang, Tsao-Jiang
;
Lai, Yuan-Cheng
Managing increasing traffic from Instant Messengers and P2P applications is becoming more important nowadays. We present an in-kernel architecture of management gateway, namely kP2PADM, built upon open-source packages with several modifications and design techniques. First, the in-kernel design streamlines the data path through the gateway. Second, the dual-queue buffer eliminates head-of-line blocking for multiple connections. Third, a connection cache reduces useless reconnection attempts from the peers. Fourth, a fast-pass mechanism avoids slowing down the TCP transmission. The in-kernel design approximately doubles the throughput of the design in the user space. The internal benchmarks also analyze the impact of each function on performance.
Low-Storage Capture and Loss Recovery Selective Replay of Real Flows
(2012-04-01)
Lin, Ying-Dar
;
Lin, Po-Ching
;
Cheng, Tsung-Huan
;
Chen, I-Wei
;
Lai, Yuan-Cheng
Capturing and replaying real flows are important for testing network security products. However, capturing real flows demands a high storage cost and runs a risk of capture loss, which makes the replay inaccurate. Replaying real flows should be accurate and stateful to adapt to the reaction of the device under test. It should also efficiently reproduce a defect and help developers identify the flows triggering defects. Therefore, this work first presents the (N, M, P) capture scheme which begins with, for each connection, capturing at most N bytes of application payload and then at most M bytes of application payload for at most each of the subsequent P packets in the same connection. This scheme reduces 87 percent of storage cost while retaining 99.74 percent of original events. This work develops a tool named SocketReplay with the mechanisms of loss recovery, stateful replay, and selective replay. Loss recovery tracks TCP sequence numbers to identify capture loss and recovers incomplete flows with dummy data. Stateful replay maintains the states in the TCP/IP stack to replay real flows. Selective replay incrementally selects flows to replay. The results show that SocketReplay can accurately and efficiently reproduce product events and significantly decrease the volume of replayed packet traces.
Method for web content filtering
(2005-06-16)
Lin, Po-Ching
;
Lin, Ying-Dar
;
Liu, Ming-Dao
The present invention provides a method of web content filtering, which can be applied to gateway devices at client ends. When an access request for a web page from a browser is sent, by analyzing the web page content returned from the web site, we can decide whether the page is allowed or not, by early blocking and early bypassing algorithms. It allows making the decision as early as we have enough confidence that the web content should belong to some forbidden category or a normal one. Therefore, the web content determination speed can be improved and users' waiting time can be reduced. Moreover, by the present method, the network gateway devices will be allowed to analyze more web content.
On Campus Beta Site: Architecture Designs, Operational Experience, and Top Product Defects
(2010-12-01)
Lin, Ying-Dar
;
Chen, I-Wei
;
Lin, Po-Ching
;
Chen, Chang-Sheng
;
Hsu, Chun-Hung
Testing network products in a beta site to reduce the possibility of customer found defects is a critical phase before marketing. We design and deploy an innovative beta site on the campus of National Chiao Tung University, Hsinchu, Taiwan. It can be used for developers to test and debug products, while maintaining network quality for network users. To satisfy the needs of developers, we set up environments and mechanisms, such as a variety of test zones for multiple types of products or systems under test (SUTs), remote control, degrees of traffic volume, and traffic profiling. For network users, we set up mechanisms of failure detection, notification, and recovery. The beta site network users are all volunteers. Test results show that beta site testing is good for finding stability and compatibility defects. The period starting from the beginning of a test until the next defect is found is called the time to fail (TTF). We call it converged if the TTF exceeds four weeks, and the convergence ratio is the percentage of SUTs that reach convergence. We find that the TTF increases with longer test duration, meaning that product quality improves through beta site testing. However, the convergence ratios are only 7 and 20 percent for test durations of one month and one year, respectively, meaning that few products operate faultlessly for a long duration. The convergence ratios also indicate that it takes much more time to enhance product quality to be converged. Therefore, if considering both marketing timing and product quality, one month is our suggested minimum TD for low-end and short-life-cycle products. However, we recommend one year as the minimum TD for high-end and long-life-cycle products.
On-the-Fly Capture and Replay Mechanisms for Multi-Port Network Devices in Operational Networks
(2014-06)
Lin, Ying-Dar
;
Lin, Po-Ching
;
Lin, Yu-An
;
Lai, Yuan-Cheng
;
資訊工程學系
Testing network devices in a live environment is desirable due to its reality. However, the defects are not reproducible, and the network connectivity will be broken if the device is down. For effective defect reproduction from real traffic, we design a new mechanism, which allows the device under test (DUT) to be automatically online/offline, and supports multiport replay for multi-port network devices with an OpenFlow switch. The defect traces are captured when the DUT is online. When a DUT failure is detected, the DUT will be offline, and the defect-triggering traces will be replayed to identify the defect. For efficient replay, we keep only partial payloads in a reduced number of packets in the defect traces that are sufficient to trigger the defects. For defect identification, reduction based on a binary search algorithm is presented to deal with the defects caused by payload anomalies and by overloading. The downsizing ratios in the cases of payload anomalies and overloading are up to 98.8% and 96%, respectively. The minimum outage time of the failover during the DUT failure is obtained when the check interval is 1 second and the number of tolerable consecutive failures is 2.
PCAPLib: A System of Extracting, Classifying, and Anonymizing Real Packet Traces
(2016-06)
Lin, Ying-Dar
;
Lin, Po-Ching
;
Wang, Sheng-Hao
;
Chen, I-Wei
;
Lai, Yuan-Cheng
This paper presents the PCAPLib system for providing extracted, well-classified, and anonymized packet traces from real network traffic with two mechanisms. First, active trace collection actively extracts and classifies packet traces into sessions by leveraging multiple detection devices. Second, deep packet anonymization protects the privacy in the packet payloads for hundreds of application protocols while preserving the utility of the traces. We evaluate 318 anonymized packet traces collected over a period of four months and show that the efficiency of anonymization is up to 96%. The usefulness of this system for assessing false positives/false negatives in intrusion detection has been also demonstrated.
PROFILING AND ACCELERATING STRING MATCHING ALGORITHMS IN THREE NETWORK CONTENT SECURITY APPLICATIONS
(2006)
Lin, Po-Ching
;
Li, Zhi-Xiang
;
Lin, Ying-Dar
;
Lai, Yuan-Cheng
;
Lin, Frank C.
The efficiency of string matching algorithms is essential for network content security applications, such as intrusion detection systems, anti-virus systems, and Web content filters. This work reviews typical algorithms and profiles their performance under various situations to study the influence of the number, the length, and the character distribution of the signatures on performance. This profiling can reveal the most efficient algorithm in each situation. A fast verification method for some string matching algorithms is also proposed. This work then analyzes the signature characteristics of three content security applications and replaces their original algorithms with the most efficient ones in the profiling. The improvement for both real and synthetic sample data is observed. For example, an open source anti-virus package, ClamAV, is five times faster after the revision. This work features comprehensive profiling results of typical string matching algorithms and observations of their application on network content security. The results can enlighten the choice of a proper algorithm in practical design.
Realizing a Sub-Linear Time String-Matching Algorithm With a Hardware Accelerator Using Bloom Filters
(2009-08-01)
Lin, Po-Ching
;
Lin, Yin-Dar
;
Lai, Yuan-Cheng
;
Zheng, Yi-Jun
;
Lee, Tsern-Huei
Many network security applications rely on string matching to detect intrusions, viruses, spam, and so on. Since software implementation may not keep pace with the high-speed demand, turning to hardware-based solutions becomes promising. This work presents an innovative architecture to realize string matching in sub-linear time based on algorithmic heuristics, which come from parallel queries to a set of space-efficient Bloom filters. The algorithm allows skipping characters not in a match in the text, and in turn simultaneously inspect multiple characters in effect. The techniques to reduce the impact of certain bad situations on performance are also proposed: the bad-block heuristic, a linear worst-case time method and a non-blocking interface to hand over the verification job to a verification module. This architecture is simulated with both behavior simulation in C and timing simulation in HDL for antivirus applications. The simulation shows that the throughput of scanning Windows executable files for more than 10 000 virus signatures can achieve 5.64 Gb/s, while the worst-case performance is 1.2 Gb/s if the signatures are properly specified.