In the current landscape of network technology, it is indisputable that the Domain Name System (DNS) plays a vital role but also encounters significant security challenges. Despite the potential of recent advancements in deep learning and machine learning, concept drift is often not addressed. In this work, we designed a DNS anomaly detection system leveraging client-domain associations. We propose the Modified Deterministic Sampling Classifier with weighted Bagging (MDSCB) method, a chunk-based ensemble learning approach addressing concept drift and data imbalance. It integrates weighted bagging, resampling, random feature selection, and a retention strategy for classifier updates, enhancing adaptability and efficiency. We conducted experiments using multiple real-world and synthetic datasets for evaluation. Empirical studies show that our detection system can help identify malicious domains that are difficult for firewalls to detect timely. Moreover, MDSCB outperforms other methods in terms of performance and efficiency.

With the growth of web applications, REST APIs have become the primary communication method between services. In order to ensure system reliability and security, software quality can be assured by effective testing methods. Black box fuzz testing is one of the effective methods to perform tests on a large scale. However, conventional black box fuzz testing generates random data without judging the quality of the input. We implement a black box fuzz testing method for REST APIs. It resolves the issues of blind mutations without knowing the effectiveness by Test Coverage Level feedback. We also enhance the mutation strategies by reducing the testing complexity for REST APIs, generating more appropriate test cases to cover possible paths. We evaluate our method by testing two large open-source projects and 89 bugs are reported and confirmed. In addition, we find 351 bugs from 64 remote API services in APIs.guru. The work is in https://github.com/iasthc/hsuan-fuzz.

To avoid distributed denial-of-service (DDoS) attacks or real-time transmission control protocol (TCP) incast in the software-defined networking (SDN) environment, the HashPipe algorithm was developed following the space-saving approach. Unfortunately, HashPipe implemented in the behavioral model (bmv2) cannot be directly executed at a real programming protocol-independent packet processor (P4) switch due to P4 pipeline limitation. Based on the Banzai machine model, this paper shows how to smartly utilize the Banzai atoms to develop HashPipe as a soft computing application in a real P4 switch. Then we propose an enhanced HashPipe algorithm that significantly improves the accuracy of the original HashPipe. The proposed heavy hitter detection is executed at the line-rate of the Tofino P4 switch with the highest process rate in the world.

When a link failure occurs in Software Defined Networking, a typical response is from controller's intervention once the Link Failure Event is triggered. Then the controller usually recalculates the possible alternative route and sets new flow rules on the affected SDN switches. However, the latency could lead to packet drop, if the route is not restored in time. Here, we propose a new method that utilizes the fast failover mechanism of group table to simulate distributed depth-first-search (DFS) with SDN switches without the intervention of controller after the related rules are installed. Based on Menger's Theorem, we can find a set of disjoint backup routes, if the topology possesses enough connectivity. With the backup routes, the controller can set up fast failover group tables with buckets watching the links appearing in the backup routes. We can properly arrange the order of the buckets in each switch, such that the switches together can simulate depth-first search for a backup route. According to our experiments, our method significantly reduces the communication between the SDN switch and the controller.

Traversing game is a two-person game played on a connected undirected simple graph with a source node and a destination node. A pebble is placed on the source node initially and then moves autonomously according to some rules. Alice is the player who wants to set up rules for each node to determine where to forward the pebble while the pebble reaches the node, so that the pebble can reach the destination node. Bob is the second player who tries to deter Alice's effort by removing edges. Given access to Alice's rules, Bob can remove as many edges as he likes, while retaining the source and destination nodes connected. Under the guide of Alice's rules, if the pebble arrives at the destination node, then we say Alice wins the traversing game; otherwise the pebble enters an endless loop without passing through the destination node, then Bob wins. We assume that Alice and Bob both play optimally. We study the problem: When will Alice have a winning strategy? This actually models a routing recovery problem in Software Defined Networking in which some links may be broken. In this paper, we prove a dichotomy result for certain traversing games, called cyclic-order traversing games. We also give a linear-time algorithm to find the corresponding winning strategy, if one exists.

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.

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.

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 xisuch that at least one of the restrictions fIxi=0or fIxi=1must 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 dq(f) be the degree of the (unique) polynomial over the ring ℤqexactly representing f. For distinct primes pilet m = Πri=1peii. Then, we show that any nondegenerate symmetric Boolean function f must have m · dp1e1(f)...dprer(f) > n. We use the existence of nondegenerate subfunctions to prove degree lower bounds on random functions. Specifically, we show that m · dp1e1(f)...dprer(f) > lg 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 lg n - 1 variables. It follows that an n-variate nondegenerate symmetric Boolean function can have degree o(√(n)) over at most one finite field and that almost all f can have degree o(√(lg n)) over at most one finite field.

A subgroup permutation code is a set of permutations onnsymbols with the property that its elements are closed under the operation of composition. In this paper, we give inapproximability results for the minimum and maximum weight problems of subgroup permutation codes under several well-known metrics. Based on previous works, we prove that under Hamming, Lee, Cayley, Kendall's tau, Ulam's, andlpdistance metrics, 1) there is no polynomial-time 2log1-εn-approximation algorithm for the minimum weight problem for any constant ε >; 0 unless NP ⊆ DTIME(2polylog(n)) (quasi-polynomial time), and 2) there is no polynomial-timer-approximation algorithm for the minimum weight problem for any constantr>; 1 unless P = NP. Underl∞-metric, we prove that it is NP-hard to approximate the minimum weight problem within factor 2-ε for any constant ε >; 0. We also prove that for any constant ε >; 0, it is NP-hard to approximate the maximum weight withinp√{[ 3/ 2]}-ε under ℓpdistance metric, and within [ 3/ 2]-ε under Hamming, Lee, Cayley, Kendall's tau, and Ulam's distance metrics.

Let Sλnbe the set of all permutations over the multiset {1,...,1,...,m,...,m} where n = mλ. A frequency permutation array (FPA) of minimum distance d is a subset of Sλnin 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. Both methods extend previous known results. The first one runs in O((2dλdλ)2.376log n) time and O ((2dλdλ)2)space. The second one runs in O ((2dλdλ)((dλ+λ)/λ)n/λ) time and O ((2dλdλ)) space. For small constants λ and d, both are efficient in time and use constant storage space.

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.

We study the task of deterministically extracting randomness from sources containing computational entropy. The sources we consider have the form of a conditional distribution (f(X)|X), for some functionfand some distributionX, and we say that such a source has computational min-entropykif any circuit of size 2kcan only predictf(x) correctly with probability at most 2-kgiven inputxsampled fromX. We first show that it is impossible to have a seedless extractor to extract from one single source of this kind. Then we show that it becomes possible if we are allowed a seed which is weakly random (instead of perfectly random) but contains some statistical min-entropy, or even a seed which is not random at all but contains some computational min-entropy. This can be seen as a step toward extending the study of multisource extractors from the traditional, statistical setting to a computational setting. We reduce the task of constructing such extractors to a problem in computational learning theory: learning linear functions under arbitrary distribution with adversarial noise, and we provide a learning algorithm for this problem. In fact, this problem is a well-recognized one in computational learning theory and variants of this problem have been studied intensively before. Thus, in addition to its application to extractors, our learning algorithm also has independent interest of its own, and it can be considered as the main technical contribution of this paper.

Permutation codes of length n and distance d is a set of permutations on n symbols, where the distance between any two elements in the set is at least d. Subgroup permutation codes are permutation codes with the property that the elements are closed under the operation of composition. In this paper, under the distance metric ℓ∞-norm, we prove that finding the minimum weight codeword for subgroup permutation code is NP-complete. Moreover, we show that it is NP-hard to approximate the minimum weight within the factor 7 over 6 - ∈ for any ∈ > 0.

An(n,d) permutation array (PA) is a subset ofSnwith the property that the distance (under some metric) between any two permutations in the array is at leastd. They became popular recently for communication over power lines. Motivated by an application to flash memories, in this paper, the metric used is the Chebyshev metric. A number of different constructions are given, as well as bounds on the size of such PA.

In this paper, we consider the task of deterministically extracting randomness from sources consisting of a sequence ofnindependent symbols from {0,1}d. The only randomness guarantee on such a source is that the whole source has min-entropyk. We give an explicit deterministic extractor which extract Ω(logk-loglog(1/ ε)) bits with error ε , for anyn,d,k∈ \BBN and ε ∈ (0,1). For sources with a larger min-entropy, we can extract even more randomness. Whenk≥n1/2+γ, for any constant γ ∈ (0,1/2), we can extractm=k-O(dlog(1/ ε)) bits with any error ε ≥ 2-Ω(nγ). Whenk≥ logcn, for some constantc> 0, we can extractm=k-(1/ ε)O(1) bits with any error ε ≥k-Ω(1). Our results generalize those of Kamp and Zuckerman and Gabizon which only work for bit-fixing sources (withd=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 extractm=k-O(log(1/ ε)) bits wheneverk=ω(d+log(n/ ε)) . Finally, we show that even to extract from bit-fixing sources, any extractor, seeded or not, must suffer an entropy lossk-m=Ω(log(1/ ε)). This generalizes a lower bound of Radhakrishnan and Ta-Shma on extracting from general sources.

A frequency permutation array (FPA) of lengthn=mλ and distancedis a set of permutations on a multiset overmsymbols, where each symbol appears exactly λ times and the distance between any two elements in the array is at leastd. 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 λ+1 symbols, which has an interesting application to private information retrieval.

A frequency permutation array (FPA) of length n = m¿ and distance d is a set of permutations on a multiset over m symbols, where each symbol appears exactly ¿ 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 ¿¿-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 ¿ + 1 symbols, which has an interesting application for private information retrieval.

In this paper we re-examine the attacking scenario about wireless sensor networks. It is generally assumed that the adversary picks up all radio communications of sensor nodes without any loss and stores the eavesdropped messages for later use. We suggest that in some situations the adversary may not be able to pick up all radio communications of sensor nodes. Therefore, we propose the storage-bounded adversary model for wireless sensor networks, in which the adversary's storage is bounded. We propose two key establishment schemes for establishing shared keys for neighboring sensor nodes in the storage-bounded adversary model. The first scheme needs special beacon nodes for broadcasting random bits. In the second scheme, some sensor nodes play the role of beacon nodes. Our results are theoretical in some sense. Nevertheless, we can adjust them for realistic consideration.

An (n, d) permutation array (PA) is a subset of Snwith 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∞-norm to measure the distance between permutations, and give a construction of permutation arrays under l∞-norm together with efficient encoding and decoding algorithms. This construction is the first of its kind.

We give a simple construction of distance-preserving mappings from ternary vectors to permutations (3-DPM). Our result gives a lower bound for permutation arrays, i.e., P(n, d) ges A3(n, d) , which significantly improves previous lower bounds for d les 3n / 5.

For$\delta \in (0,1)$and$k,n\in \BBN $, we study the task of transforming a hard function$f: \{0,1\}^{n}\to \{0,1\} $, with which any small circuit disagrees on$(1-\delta )/2$fraction of the input, into a harder function$f^{\prime}$, with which any small circuit disagrees on$(1-\delta ^{k})/2$fraction of the input. First, we show that such hardness amplification, when carried out in some black-box way, must require a high complexity. In particular, it cannot be realized by a circuit of depth$d$and size$2^{o(k^{1/d})}$or by a nondeterministic circuit of size$o(k/\log k)$(and arbitrary depth) for any$\delta \in (0,1)$. This extends the result of Viola, which only works when$(1-\delta )/2$is small enough. Furthermore, we show that even without any restriction on the complexity of the amplification procedure, such a black-box hardness amplification must be inherently nonuniform in the following sense. To guarantee the hardness of the resulting function$f^{\prime}$, even against uniform machines, one has to start with a function$f$, which is hard against nonuniform algorithms with$\Omega (k\log (1/\delta ))$bits of advice. This extends the result of Trevisan and Vadhan, which only addresses the case with$(1-\delta )/2=2^{-n}$. Finally, we derive similar lower bounds for any black-box construction of a pseudorandom generator (PRG) from a hard function. To prove our results, we link the task of hardness amplifications and PRG constructions, respectively, to some type of error-reduction codes, and then we establish lower bounds for such codes, which we hope could find interest in both coding theory and complexity theory.

We study the task of transforming a hard function f, with which any small circuit disagrees on (1 - /spl delta/)/2 fraction of the input, into a harder function f', with which any small circuit disagrees on (1 - /spl delta//sup k/)/2 fraction of the input, for /spl delta/ /spl isin/ (0,1) and k /spl isin/ /spl Nopf/. We show that this process cannot be carried out in a black-box way by a circuit of depth d and size 2/sup o(k2/d)/ or by a nondeterministic circuit of size o(k/log k) (and arbitrary depth). In particular, for k = 2/sup /spl Omega/(n)/, such hardness amplification cannot be done in ATIME(O(1), 2/sup o(n)/. Therefore, hardness amplification in general requires a high complexity. Furthermore, we show that even without any restriction on the complexity of the amplification procedure, such a black-box hardness amplification must be inherently non-uniform in the following sense. Given as an oracle any algorithm which agrees with f' on (1 - /spl delta//sup k/)/2 fraction of the input, we still need an additional advice of length /spl Omega/(k log(1//spl delta/)) in order to compute f correctly on (1 - /spl delta/)/2 fraction of the input. Therefore, to guarantee the hardness, even against uniform machines, of the function f', one has to start with a function f which is hard against non-uniform circuits. Finally, we derive similar lower bounds for any black-box construction of pseudorandom generators from hard functions.

We study the problem of deterministically extracting almost perfect random bits from multiple weakly random sources that are mutually independent. With two independent sources, we have an explicit extractor which can extract a number of random bits that matches the best construction currently known, via the generalized leftover hash lemma. We also extend our construction to extract randomness from more independent sources. One nice feature is that the extractor still works even with all but one source exposed. Finally, we apply our extractor for a cryptographic task in which a group of parties wants to agree on a secret key for group communication over an insecure channel, without using ideal local randomness.

We study the distance measures between two probability distributions via two different distance metrics, a new metric induced from Jensen-Shannon divergence, and the well known L/sub 1/ metric. We show that several important results and constructions in computational complexity under the L/sub 1/ metric carry over to the new metric, such as Yao's next-bit predictor, the existence of extractors, the leftover hash lemma, and the construction of expander graph based extractor. Finally, we show that the useful parity lemma in studying pseudorandomness does not hold in the new metric.

Mappings of the set of binary vectors of a fixed length to the set of permutations of the same length are useful for the construction of permutation codes. In this article, several explicit constructions of such mappings preserving or increasing the Hamming distance are given. Some applications are given to illustrate the usefulness of the construction. In particular, a new lower bound on the maximal size of permutation arrays (PAs) is given.

In this article, we investigate compiler transformation techniques regarding the problem of scheduling VLIW instructions aimed at reducing power consumption of VLIW architectures in the instruction bus. The problem can be categorized into two types: horizontal scheduling and vertical scheduling. For the case of horizontal scheduling, we propose a bipartite-matching scheme for instruction scheduling. We prove that our greedy bipartite-matching scheme always gives the optimal switching activities of the instruction bus for given VLIW instruction scheduling policies. For the case of vertical scheduling, we prove that the problem is NP-hard, and we further propose a heuristic algorithm to solve the problem. Our experiment is performed on Alpha-based VLIW architectures and an ATOM simulator, and the compiler incorporated in our proposed schemes is implemented based on SUIF and MachSUIF. Experimental results of horizontal scheduling optimization show an average 13.30% reduction with four-way issue architecture and an average 20.15% reduction with eight-way issue architecture for transitional activities of the instruction bus as compared with conventional list scheduling for an extensive set of benchmarks. The additional reduction for transitional activities of the instruction bus from horizontal to vertical scheduling with window size four is around 4.57 to 10.42%, and the average is 7.66%. Similarly, the additional reduction with window size eight is from 6.99 to 15.25%, and the average is 10.55%.

In this note we consider the number of distinct $\alpha$-ary codes produced by repeatedly applying the Gray code mapping of Sharma and Khanna [ Inform. Sci., 15 (1978), pp. 31--43]. This number was derived before by Lichtner [SIAM J. Discrete Math., 11 (1998), pp. 381--386], and we give an alternative proof here. Our key observation is a simple connection between this number and the period of binomial coefficients modulo $\alpha$. Then the result follows immediately from a known periodic property of binomial coefficients modulo $\alpha$ [ Fibonacci Quart., 27 (1989), pp. 64--79; SIAM J. Discrete Math., 9 (1996), pp. 55--62; Ann. Univ. Mariae Curie-Sklodowska Sect. A, 10 (1956), pp. 37--47].

Abstract We describe JGAP, a web‐based platform for designing and implementing Java‐coded graph algorithms. The platform contains a library of common data structures for implementing graph algorithms, features a ‘plug‐and‐play’ modular design for adding new algorithm modules, and includes a performance meter to measure the execution time of implemented algorithms. JGAP is also equipped with a graph editor to generate and modify graphs to have specific properties. JGAP's graphic user interface further allows users to compose, in a functional way, computation sequences from existing algorithm modules so that output from an algorithm is used as input for another algorithm. Hence, JGAP can be viewed as a visual graph calculator for helping experiment with and teach graph algorithm design. Copyright © 2001 John Wiley & Sons, Ltd.

Both the bottleneck counting argument and Razborov's approximation method have been used to prove exponential lower bounds for monotone circuits. We show that under the monotone circuit model for every proof by the approximation method, there is a bottleneck counting proof and vice versa. We also illustrate the elegance of the bottleneck counting technique with a simple self-explained example: the proof of a (previously known) lower bound for the 3-CLIQUE/sub n/ problem by the bottleneck counting argument.

Define the $MOD_m $-degree of a boolean function F to be the smallest degree of any polynomial P, over the ring of integers modulo m, such that for all 0-1 assignments $\vec x$, $F(\vec x) = 0$ iff $P(\vec x) = 0$. By exploring the periodic property of the binomial coefficients modulo m, two new lower bounds on the $MOD_m $-degree of the $MOD_l $ and $- MOD_m $ functions are proved, where m is any composite integer and l has a prime factor not dividing m. Both bounds improve from sublinear to $\Omega (n)$. With the periodic property, a simple proof of a lower bound on the $MOD_m $-degree with symmetric multilinear polynomial of the OR function is given. It is also proved that the majority function has a lower bound $\frac{n}{2}$ and the MidBit function has a lower bound $\sqrt n $.