Browsing by Author "Yang, Ming-Chuan"

Now showing 1 - 5 of 5

Detecting Amplification Attacks with Software Defined Networking
(2017-01-01)
Chen, Chih-Chieh
;
Chen, Yi-Ren
;
Lu, Wei-Chih
;
Tsai, Shi-Chun
;
Yang, Ming-Chuan
Distributed denial of service (DDoS) is an attack that attempts to disrupt network service for various malicious purposes. It makes use of public services as reflectors to amplify the traffic, and thus called distributed reflection denial of service attacks. This type of attack forges source IP address, and makes it hard to filter the problematic packets. With Software Defined Networking (SDN) and machine learning techniques, we implement a system to detect DRDoS packets and block the amplification attacks automatically. DNS and NTP amplifications are two typical attacks of DDoS. By analyzing the traffic features, although our classifier is trained only for the DNS amplification attack, our system can identify and then block both DNS and NTP amplification attacks with great accuracy.
Forwarding Path Discovery with Software Defined Networking
(2017-01-01)
Chen, Chih-Chieh
;
Chen, Yi-Ren
;
Tsai, Shi-Chun
;
Yang, Ming-Chuan
;
資訊工程學系
Without STP and LLDP, we propose a new approach to find faster paths between the source and the destination and fully utilize the links between switches under the Software Defined Network paradigm. To find round-trip path with lighter load, we design a mechanism to compose special ARP packets for exploring the routing path and avoid broadcast storm by dropping late or duplicate packets. Meanwhile, the controller can carefully regulate other packets without affecting the behavior of the special packets. The evaluation results with the Clos-like network topology show that our approach can be used to improve the performance of transmission throughput. We believe our method is very suitable, especially, for a dynamic network environment, where links are up and down frequently. Our implementation can be seen as an instance showing the flexibility of SDN.
On the inapproximability of maximum intersection problems
(2012-10-15)
Shieh, Min-Zheng
;
Tsai, Shi-Chun
;
Yang, Ming-Chuan
;
資訊工程學系
;
Department of Computer Science
Given a sets, we want to choose exactly k sets such that the cardinality of their intersection is maximized. This is the so-called MAX-k-INTERSECT problem. We prove that MAX-k-INTERSECT cannot be approximated within an absolute error of 1/2n(1-2 epsilon) + O(n(1-3 epsilon)) unless P = NP. This answers an open question about its hardness. We also give a correct proof of an inapproximable result by Clifford and Papa (2011) [3] by proving that MAX-INTERSECT problem is equivalent to the MAX-CLIQUE problem. (C) 2012 Elsevier B.V. All rights reserved.
Online Prediction Problems with Variation
(2014-01-01)
Lee, Chia-Jung
;
Tsai, Shi-Chun
;
Yang, Ming-Chuan
;
資訊工程學系
;
Department of Computer Science
We study the prediction with expert advice problem, where in each round, the player selects one of N actions and incurs the corresponding loss according to an N-dimensional linear loss vector, and aim to minimize the regret. In this paper, we consider a new measure of the loss functions, which we call L-infinity-variation. Consider the loss functions with small L-infinity-variation, if the player is allowed to have some information related to the variation in each round, we can obtain an online bandit algorithm for the problem without using the self-concordance methodology, which conditionally answers an open problem in [8]. Another related problem is the combinatorial prediction game, in which the set of actions is a subset of {0, 1}(d), and the loss function is in [-1, 1](d). We provide an online algorithm in the semi-bandit setting when the loss functions have small L-infinity-variation.
Restrictions of Nondegenerate Boolean Functions and Degree Lower Bounds over Different Rings
(2015)
Lee, Chia-Jung
;
Lokam, Satyanarayana V.
;
Tsai, Shi-Chun
;
Yang, Ming-Chuan
;
資訊工程學系
A Boolean function f : {0; 1}(n) -> {0, 1} is called nondegenerate if f depends on all its n variables. We show that, for any nondegenerate function f, there exists a variable x(i) such that at least one of the restrictions f vertical bar(xi) = 0 or f vertical bar(xi) = 1 must depend on all the remaining n - 1 variables. We also consider lower bounds on the degrees of polynomials representing a Boolean function over different rings. Let d (q)(f) be the degree of the unique) polynomial over the ring Z(q) exactly representing f. For distinct primes p(i) let m = Pi(r)(i=1) p(i)(ei). Then, we show that any nondegenerate symmetric Boolean function f must have m . d(p1)(e1) (f)...d(pr)(er)(f) > n. We use the existence of nondegenerate subfunctions to prove degree lower bounds on random functions. Specifically, we show that m .d(p)(e1) (f)...d(pr)(er) (f) > l g n - 1 holds for almost all f when f is chosen uniformly at random from all n - variate Boolean functions. Our proof uses the second moment method to show that a random f must almost always contain a nondegenerate symmetric subfunction on at least l g n - 1 variables. It follows that an n-variate nondegenerate symmetric Boolean function can have degree o(root n) over at most one finite field and that almost all f can have degree o(root lg n) over at most one finite field.