Browsing by Author "Tsai, Shi-Chun"

Now showing 1 - 20 of 47

A Monte Carlo Method for Estimating the Extended All-terminal Reliability
(2008)
Huang, Shiang-Ming
;
Wu, Quincy
;
Tsai, Shi-Chun
;
資訊工程學系
;
Department of Computer Science
Designing a network with optimal deployment cost and maximum reliability considerations is a hard problem, especially when the all-terminal reliability is required. For efficiently finding out an acceptable solution, Genetic Algorithms (GAs) have been widely applied to solve this problem. In these GAs, the reliability values could be calculated in their objective functions. In year 2002, an extended network reliability model was proposed which considers the connection important level between each pair of nodes. This paper proposes an approximation algorithm based on Monte Carlo simulation for the new network reliability model. This approximation algorithm can be integrated into GAs to solve the optimal cost reliable network design problem under the extended model.
Algebraic methods for pseudo-randomness and boolean complexity
(The university of chicago, 1996)
Tsai, Shi-Chun
Alternating Runs of Geometrically Distributed Random Variables
(2011-05-01)
Lee, Chia-Jung
;
Tsai, Shi-Chun
;
資訊工程學系
;
Department of Computer Science
Run statistics about a sequence of independent geometrically distributed random variables has attracted some attention recently in many areas such as applied probability, reliability, statistical process control, and computer science. In this paper, we first study the mean and variance of the number of alternating runs in a sequence of independent geometrically distributed random variables. Then, using the relation between the model of geometrically distributed random variables and the model of random permutation, we can obtain the variance in a random permutation, which is difficult to derive directly. Moreover, using the central limit theorem for dependent random variables, we can obtain the distribution of the number of alternating runs in a random permutation.
An Autoblocking Mechanism for Firewall Service
(2017-01-01)
Fu, Shan-Jung
;
Hsu, Huai-Wen
;
Kao, Yi-Chih
;
Tsai, Shi-Chun
;
Tseng, Chien-Chao
A distributed denial-of-service (DDoS) attack could cause the incoming connections per second exceeding the capacity of the firewall device and the network system might be paralyzed. By analyzing the syslog of firewall, we design an effective mechanism to block malicious source IPs automatically from the router. We have undergone a field trial on campus for two years. The collected data shows that our approach significantly reduces suspicious traffic and improve the stability of overall network service.
An Optimal Data Hiding Scheme With Tree-Based Parity Check
(2011-03-01)
Hou, Chung-Li
;
Lu, ChangChun
;
Tsai, Shi-Chun
;
Tzeng, Wen-Guey
;
資訊工程學系
Reducing distortion between the cover object and the stego object is an important issue for steganography. The tree-based parity check method is very efficient for hiding a message on image data due to its simplicity. Based on this approach, we propose a majority vote strategy that results in least distortion for finding a stego object. The lower embedding efficiency of our method is better than that of previous works when the hidden message length is relatively large.
Arranging numbers on circles to reach maximum total variations
(2007-06-28)
Liao, Ying-Jie
;
Shieh, Min-Zheng
;
Tsai, Shi-Chun
;
資訊工程學系
;
Department of Computer Science
The dartboard problem is to arrange n numbers on a circle to obtain maximum risk, which is the sum of the q-th power of the absolute differences of adjacent numbers, for q >= 1. Curtis showed that the dartboard problem admits a greedy algorithm. We generalize the dartboard problem by considering more circles and the goal is to arrange kn number on k circles to obtain the maximum risk. In this paper, we characterize an optimal arrangement for k = 2 and show that the generalized dartboard problem also admits a greedy algorithm.
Complexity of Hard-Core Set Proofs
(2011-03-01)
Lu, Chi-Jen
;
Tsai, Shi-Chun
;
Wu, Hsin-Lung
;
資訊工程學系
;
Department of Computer Science
We study a fundamental result of Impagliazzo (FOCS'95) known as the hard-core set lemma. Consider any function f : {0,1}(n) -> {0,1} which is "mildly hard", in the sense that any circuit of size s must disagree with f on at least a delta fraction of inputs. Then, the hard-core set lemma says that f must have a hard-core set H of density delta on which it is "extremely hard", in the sense that any circuit of size s' = O(s/1/epsilon(2) log 1/epsilon(delta)))) must disagree wiht f on at least (1 - epsilon)/2 fraction of inputs from H. There are three issues of the lemma which we would like to address: the loss of circuit size, the need of non-uniformity, and its inapplicability to a low-level complexity class. We introduce two models of hard-core set proofs, a strongly black-box one and a weakly black-box one, and show that those issues are unavoidable in such models. First, we show that using any strongly black-box proof, one can only prove the hardness of a hard-core set for smaller circuits of size at most s' = O(s/1/epsilon(2) log 1/delta)). Next, we show that any weakly black-box proof must be inherently non-uniform-to have a hard-core set for a class G of functions, we need to start from the assumption that f is hard against a non-uniform complexity class with Omega(1/epsilon log vertical bar G vertical bar) bits of advice. Finally, we show that weakly black-box proofs in general cannot be realized in a low-level complexity class such as AC (0)[p]-the assumption that f is hard for AC (0)[p] is not sufficient to guarantee the existence of a hard-core set.
Computing the Ball Size of Frequency Permutations under Chebyshev Distance
(2011)
Shieh, Min-Zheng
;
Tsai, Shi-Chun
;
資訊工程學系
;
Department of Computer Science
Let S-n(lambda) be the set of all permutations over the multiset [GRAPHICS] where n = m lambda. A frequency permutation array (FPA) of minimum distance d is a subset of S-n(lambda) in which every two elements have distance at least d. FPAs have many applications related to error correcting codes. In coding theory, the Gilbert- Varshamov bound and the spherepacking bound are derived from the size of balls of certain radii. We propose two efficient algorithms that compute the ball size of frequency permutations under Chebyshev distance. Both methods extend previous known results. The first one runs in O((()(2d lambda)2.376)(d lambda) log n) time and O((()(2d lambda)2)(d lambda)) space. The second one runs in O ((()(2d lambda)()(d lambda) (d lambda+lambda))(lambda)n/lambda) time and O((2d lambda)(d lambda)) space. For small constants lambda and d, both are efficient in time and use constant storage space.
Computing the ball size of frequency permutations under Chebyshev distance
(2012-07-01)
Shieh, Min-Zheng
;
Tsai, Shi-Chun
;
資訊工程學系
;
Department of Computer Science
Let S-n(lambda) be the set of all permutations over the multiset { [GRAPHICS] , .... , [GRAPHICS] } where n = m lambda. A frequency permutation array (FPA) of minimum distance d is a subset of S-n(lambda) which every two elements have distance at least d. FPAs have many applications related to error correcting codes. In coding theory, the Gilbert-Varshamov bound and the sphere-packing bound are derived from the size of balls of certain radii. We propose two efficient algorithms that compute the ball size of frequency permutations under Chebyshev distance. Here it is equivalent to computing the permanent of a special type of matrix, which generalizes the Toepliz matrix in some sense. Both methods extend previous known results. The first one runs in O (((2d lambda)(d lambda))(2.376) log n) time and O(((2d lambda)(d lambda))(2)) space. The second one runs in O (((2d lambda)(d lambda)) ((d lambda+lambda)(lambda))n/lambda) time and O (((2d lambda)(d lambda))) space. For small constants lambda and d, both are efficient in time and use constant storage space. (C) 2012 Elsevier Inc. All rights reserved.
Decoding Frequency Permutation Arrays Under Chebyshev Distance
(2010-11-01)
Shieh, Min-Zheng
;
Tsai, Shi-Chun
;
資訊工程學系
;
Department of Computer Science
A frequency permutation array (FPA) of length n = m lambda and distance d is a set of permutations on a multiset over m symbols, where each symbol appears exactly lambda times and the distance between any two elements in the array is at least d. FPA generalizes the notion of permutation array. In this paper, under the Chebyshev distance, we first prove lower and upper bounds on the size of FPA. Then we give several constructions of FPAs, and some of them come with efficient encoding and decoding capabilities. Moreover, we show one of our designs is locally decodable, i.e., we can decode a message bit by reading at most lambda + 1 symbols, which has an interesting application to private information retrieval.
Decoding Frequency Permutation Arrays Under Chebyshev Distance
(2010-11-01)
Shieh, Min-Zheng
;
Tsai, Shi-Chun
;
資訊工程學系
;
Department of Computer Science
A frequency permutation array (FPA) of length n = m lambda and distance d is a set of permutations on a multiset over m symbols, where each symbol appears exactly lambda times and the distance between any two elements in the array is at least d. FPA generalizes the notion of permutation array. In this paper, under the Chebyshev distance, we first prove lower and upper bounds on the size of FPA. Then we give several constructions of FPAs, and some of them come with efficient encoding and decoding capabilities. Moreover, we show one of our designs is locally decodable, i.e., we can decode a message bit by reading at most lambda + 1 symbols, which has an interesting application to private information retrieval.
Decoding Frequency Permutation Arrays under Infinite norm
(2009)
Shieh, Min-Zheng
;
Tsai, Shi-Chun
;
資訊工程學系
;
Department of Computer Science
A frequency permutation array (FPA) of length n = rn lambda), and distance d is a set of permutations on a multiset over m symbols, where each symbol appears exactly lambda times and the distance between any two elements in the array is at least d. FPA generalizes the notion of permutation array. In this paper, under the distance metric l(infinity)-norm, we first prove lower and upper bounds on the size of FPA. Then we give a construction of FPA with efficient encoding and decoding capabilities. Moreover, we show our design is locally decodable, i.e., we can decode a message bit by reading at most lambda + 1 symbols, which has an interesting application for private information retrieval.
Decoding permutation arrays with ternary vectors
(2011-10-01)
Lee, Chia-Jung
;
Lin, Te-Tsung
;
Shieh, Min-Zheng
;
Tsai, Shi-Chun
;
Wu, Hsin-Lung
We give an explicit decoding scheme for the permutation arrays under Hamming distance metric, where the encoding is constructed via a distance-preserving mapping from ternary vectors to permutations (3-DPM).
Deploying WLAN service with OpenFlow technology
(2017-05-01)
Hsu, Huai-Wen
;
Huang, Kuei-Li
;
Kao, Yi-Chih
;
Tsai, Shi-Chun
;
Lin, Yi-Bing
In this paper, we proposed a feasible software-defined networking (SDN) wireless local area network (WLAN) solution that leverages OpenFlow technique and provides affordable centralized WLAN service without the proprietary restrictions of centralized thin access point WLAN architecture. On the basis of an SDN-enabled WLAN architecture with fat access points, we implement and deploy a wireless network test bed, where network administrators can exploit the extensibility and flexibility of OpenFlow-based SDN switches and controller. Service providers can develop customized application modules and required features. We build our system with open sources and commercial off-the-shelf hardware and develop a mechanism to control wireless bandwidth. Field experimental results show that our SDN wireless bandwidth control application can effectively manage bandwidth in a dynamic and flexible way via the SDN WLAN.
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.
Detecting P2P Botnet in Software Defined Networks
(2018-01-01)
Su, Shang-Chiuan
;
Chen, Yi-Ren
;
Tsai, Shi-Chun
;
Lin, Yi-Bing
;
資訊工程學系
Software Defined Network separates the control plane from network equipment and has great advantage in network management as compared with traditional approaches. With this paradigm, the security issues persist to exist and could become even worse because of the flexibility on handling the packets. In this paper we propose an effective framework by integrating SDN and machine learning to detect and categorize P2P network traffics. This work provides experimental evidence showing that our approach can automatically analyze network traffic and flexibly change flow entries in OpenFlow switches through the SDN controller. This can effectively help the network administrators manage related security problems.
Deterministic extractors for independent-symbol sources
(2006)
Lee, Chia-Jung
;
Lu, Chi-Jen
;
Tsai, Shi-Chun
;
資訊工程學系
;
Department of Computer Science
In this paper, we consider the task of deterministically extracting randomness from sources consisting of a sequence of n independent symbols from {0, 1}(d). The only randomness guarantee on such a source is that the whole source has min-entropy k. We give an explicit deterministic extractor which can extract Omega(log k-log d-log log(1/epsilon)) bits with error epsilon, for any n, d, k is an element of N and epsilon G (0, 1). For sources with a larger min-entropy, we can extract even more randomness. When k >= n(1/2+gamma) for any constant gamma is an element of (0, 1/2), we can extract m = k - O(d log(1/epsilon)) bits with any error epsilon >= 2(-Omega)(n(gamma)). When k >= log(c)n, for some constant c > 0, we can extract m = k - d(1/epsilon)(O(1)) bits with any error epsilon >= k(-Omega(1)). Our results generalize those of Kamp & Zuckerman and Gabizon et al. which only work for bit-fixing sources (with d = I and each bit of the source being either fixed or perfectly random). Moreover, we show the existence of a non-explicit deterministic extractor which can extract m = k-O(log(1/epsilon)) bits whenever k = w(d+log(n/epsilon)). Finally, we show that even to extract from bit-fixing sources, any extractor, seeded or not, must suffer an entropy loss k-m = Q (log (1/epsilon)). This generalizes a lower bound of Radhakrishnan & Ta-Shma with respect to general sources.
Deterministic Extractors for Independent-Symbol Sources
(2010-12-01)
Lee, Chia-Jung
;
Lu, Chi-Jen
;
Tsai, Shi-Chun
;
資訊工程學系
;
Department of Computer Science
In this paper, we consider the task of deterministically extracting randomness from sources consisting of a sequence of n independent symbols from {0, 1}(d). The only randomness guarantee on such a source is that the whole source has min-entropy k. We give an explicit deterministic extractor which extract Omega(log k - log log(1/epsilon)) bits with error epsilon, for any, n, d, k is an element of N and epsilon is an element of (0, 1). For sources with a larger min-entropy, we can extract even more randomness. When k >= n(1/2+gamma), for any constant gamma is an element of (1, 1/2), we can extract m = k - O(d log(1/epsilon)) bits with any error epsilon >= 2(-Omega(n gamma)). When k >= log(c) n, for some constant c > 0 , we can extract m = k - (1/epsilon)(O(1)) bits with any error epsilon >= k(-Omega(1)). Our results generalize those of Kamp and Zuckerman and Gabizon et al. which only work for bit-fixing sources (with d = 1 and each bit of the source being either fixed or perfectly random). Moreover, we show the existence of a nonexplicit deterministic extractor which can extract m = k - O(log(1/epsilon)) bits whenever k = omega(d + log(n/epsilon)). Finally, we show that even to extract from bit-fixing sources, any extractor, seeded or not, must suffer an entropy loss k - m = Omega(log(1/epsilon)). This generalizes a lower bound of Radhakrishnan and Ta-Shma on extracting from general sources.
Dual-Stack Network Management Through One-Time Authentication Mechanism
(2020-01-01)
Kao, Yi-Chih
;
Liu, Jui-Chun
;
Ke, Yi-Quan
;
Tsai, Shi-Chun
;
Lin, Yi-Bing
The exhaustion of IPv4 addresses has led to the rapid implementation of IPv6. However, the design of IPv6 is incompatible with that of its predecessor IPv4 and slows down the development of the IPv4-to-IPv6 migration. Several transitioning mechanisms have been proposed to attain the compatibility of IPv4 and IPv6 to bridge the gap between these two heterogeneous protocols. The two protocols would need to coexist continually before IPv6 completely takes over IPv4. However, the existing captive portal authentication systems generally do not support IPv4/IPv6 dual-stack authentication and lack one-time dual-stack authentication solutions. Upgrading the authentication system has become an urgent problem to be addressed. This study presents dual-stack network management strategies using a novel one-time authentication mechanism for large and complex dual-stack network environments. The proposed authentication system resolves the inconvenience of separate IPv4 and IPv6 authentication and effectively improves the compatibility of the two protocols. Furthermore, authenticating both IPv4 and IPv6 increases the traceability of traffic logs when security attacks occur. The proposed solution is deployed in a campus dormitory environment, and the feasibility and stability are successfully verified.
Efficient Encoding and Decoding with Permutation Arrays
(2008)
Lin, Te-Tsung
;
Tsai, Shi-Chun
;
Tzeng, Wen-Guey
;
資訊工程學系
;
Department of Computer Science
An (n, d) permutation array (PA) is a subset of S(n) with the property that the distance (under any distance metric, such as Hamming) between any two permutations in the array is at least d, which becomes popular recently for communication over power line. We use l(infinity)-norm to measure the distance between permutations, and give a construction of permutation arrays under l(infinity)-norm together with efficient encoding and decoding algorithms. This construction is the first of its kind.