This demo introduces Doenba Edit, a user-friendly, AI-powered platform developed by Librum Technologies, Inc., designed for seamless editing and typesetting of academic writing within a word processor-like interface. It supports the entire academic writing workflow, from outlining and idea development to drafting, revising, typesetting, and cross-referencing, assisted by integrated AI tools at every stage. This offers a comprehensive solution for enhancing both the quality and efficiency of producing scholarly work.

Existing tools to detect text generated by a large language model (LLM) have met with certain success, but their performance can drop when dealing with texts in new domains. To tackle this issue, we train a ranking classifier called RoBERTa-Ranker, a modified version of RoBERTa, as a baseline model using a dataset we constructed that includes a wider variety of texts written by humans and generated by various LLMs. We then present a method to fine-tune RoBERTa-Ranker that requires only a small amount of labeled data in a new domain. Experiments show that this fine-tuned domain-aware model outperforms the popular DetectGPT and GPTZero on both in-domain and cross-domain texts, where AI-generated texts may either be in a different domain or generated by a different LLM not used to generate the training datasets. This approach makes it feasible and economical to build a single system to detect AI-generated texts across various domains.

Generative text steganography has received considerable attention in the covert communication community for the benefit of sending secret messages without the need to modify carriers. Existing methods typically choose the next word when generating a stego-text based on conditional probability encoding of candidates, which may lead to generating inadequate words for the underlying secret message. How to generate a semantically controllable stego-text with a high capacity on secure embedding of a secret message is a main challenge. We address this challenge by proposing a new paradigm to generative text steganography that takes advantage of certain social media through apparently normal behaviors from the sender. In particular, we make use of the live commenting feature provided by public video sharing platforms (PVSPs), which allow viewers to make comments on video scenes that will fly on screens when the scenes are shown. We show that this feature can be used to construct a generative steganographic system. The sender generates at random a number of distracting words and a certain invertible matrix called W-dmatrix based on the total number of message words and distracting words. The sender then transforms a sequence of indexes of these words to a sequence, selects one or more videos with a sufficiently large number of total frames, and generates a comment on each frame in the sequence. The receiver extracts commented frame indexes, uses the shared stego-key to generate the same W-dmatrix as the sender, and obtains the secret message using the inverse of the matrix. The stego-key consists of a vocabulary generator and a W-dmatrix generator (WMG) based on pseudorandomly generated numbers. To generate comments on frames that conform to comments made by viewers, we devise a neural ResNet-LSTM model to generate a comment for an input image based on its content. Theoretical analysis shows that commented video frames (CVF) is covert, secure, efficient, and feasible to conceal any message of arbitrary length. We implement CVF and present evaluation results from multiple aspects that our work outperforms the existing stego-methods.

We present a generative method called CQG for constructing cloze questions from a given article using neural networks and WordNet, with an emphasis on generating multigram distractors. Built on sense disambiguation, text-to-text transformation, WordNet's synset taxonomies and lexical labels, CQG selects an answer key for a given sentence, segments it into a sequence of instances, generates instance-level distractor candidates (IDCs) using a transformer and sibling synsets. It then removes inappropriate IDCs, ranks the remaining IDCs based on contextual embedding similarities, as well as synset and lexical relatedness, forms distractor candidates by combinatorially replacing instances with the corresponding top-ranked IDCs, and checks if they are legitimate phrases. Finally, it selects top-ranked distractor candidates based on contextual semantic similarities to the answer key. Experiments show that this method significantly outperforms SOTA results. Human judges also confirm the high qualities of the generated distractors.

We present a method to perform a downstream task of transformers on generating question-answer pairs (QAPs) from a given article. We first finetune pretrained transformers on QAP datasets. We then use a preprocessing pipeline to select appropriate answers from the article, and feed each answer and the relevant context to the finetuned transformer to generate a candidate QAP. Finally we use a postprocessing pipeline to filter inadequate QAPs. In particular, using pretrained T5 models as transformers and the SQuAD dataset as the finetruning dataset, we obtain a finetuned T5 model that outperforms previous models on standard performance measures over the SQuAD dataset. We then show that our method based on this finetuned model generates a satisfactory number of QAPs with high qualities on the Gaokao-EN dataset assessed by human judges.

We construct a contextual network to represent a document with syntactic and semantic relations between word-sentence pairs, based on which we devise an unsupervised algorithm called CNATAR to score sentences, and rank them through a bi-objective 0-1 knapsack maximization problem over topic analysis and sentence scores. We show that CNATAR outperforms the combined ranking of the three human judges provided on the SummBank dataset under both ROUGE and BLEU metrics, which in term significantly outperforms each individual judge’s ranking. Moreover, CNATAR produces so far the highest ROUGE scores over DUC-02, and outperforms previous supervised algorithms on the CNN/DailyMail and NYT datasets. We also compare the performance of CNATAR and the latest supervised neural-network summarization models and compute oracle results.

We present a hierarchical neural network model called SemText to detect HTML boilerplate based on a novel semantic representation of text blocks. We train SemText on three published datasets of news webpages and fine-tune it using a small number of development data in CleanEval and GoogleTrends-2017. We show that SemText achieves the state-of-the-art accuracy on these datasets. We then demonstrate the robustness of SemText by showing that it also detects boilerplate effectively on out-of-domain community-based Q&A webpages.

How to efficiently generate an accurate, well-structured overview report (ORPT) over thousands of documents is challenging. A well-structured ORPT is divided into sections of multiple levels (e.g., a two-level structure consists of sections and subsections). None of the existing multi-document summarization (MDS) algorithms is suitable for accomplishing this task. To overcome this obstacle, we devise NDORGS (Numerous Documents' Overview Report Generation Scheme) that integrates text filtering, keyword scoring, single-document summarization (SDS), topic modeling, MDS, and title generation to generate a coherent, well-structured ORPT. We then present a multi-criteria evaluation method using techniques of text mining and multi-attribute decision making on a combination of human judgments, running time, information coverage, and topic diversity. We evaluate ORPTs generated by NDORGS on two large corpora of documents, where one is classified and the other unclassified. We show that, using Saaty's pairwise comparison 9-point scale and TOPSIS, the ORPTs generated on SDS's with the length of 20% of the original documents are the best overall on both datasets.

Abstract In recent years searchable symmetric encryption has seen a rapid increase in query expressiveness including keyword, phrase, Boolean, and fuzzy queries. With this expressiveness came increasingly complex constructions. Having these facts in mind, we present an efficient and generic searchable symmetric encryption construction for phrase queries. Our construction is straightforward to implement, and is proven secure under adaptively chosen query attacks (CQA2) in the random oracle model with an honest-but-curious adversary. To our knowledge, this is the first encrypted phrase search system that achieves CQA2 security. Moreover, we demonstrate that our document collection preprocessing algorithm allows us to extend a dynamic SSE construction so that it supports phrase queries. We also provide a compiler theorem which transforms any CQA2-secure SSE construction for keyword queries into a CQA2-secure SSE construction that supports phrase queries.

Large-scale information gathering becomes more and more common with the increasing popularity of smartphones, GPS, social networks, and sensor networks. Services based on this real-time data are the logical next step. Service Oriented Stream Systems (SOSS) have a focus on one-time ad hoc queries as op-posed to continuous queries. High availability is crucial in these services. However, data replication has inherent costs, which are particularly burdensome for high rate, often overloaded, SOSS. To provide high availability and to cope with the problem of over-loading the system, we propose a mechanism called soft quorums. Soft quorums incorporate a tuning knob that provides a trade off between query result accuracy and performance. Thus, in essence, soft quorums simultaneously offer high availability and per-query load shedding as needed. This is done in a system-wise optimal way. The parameter choices of soft quorums automatically adapt to dynamic data stream rates and query rates, and minimize the overall system load, given an accuracy requirement. We devise a recovery algorithm and study data quality after recovery. Finally, we conduct a comprehensive experimental study using two real-world and some synthetic datasets.

Abstract Big data presents critical requirements for security in data collection and transmission of selected data through a communication network. This paper presents a new secure transmission for big data based on nested sparse sampling and coprime sampling. With nested sampling and coprime sampling, besides the advantage of higher spectrum efficiency, big data could also achieve higher power spectral density for binary frequency shift keying (BFSK) signal. When the sampling spacing pairs are big enough, the spectrum of BFSK signal performs like frequency hopping. This property has great advantage in the security of big data collection and transmission using FH/BFSK, as it could achieve low error probability. With the same multitone interfering signal added to FH/BFSK, the error probability becomes much lower using nested sampling and coprime sampling compared with the original FH/BFSK signal. This proves that both nested sampling and coprime sampling could be used in big data transmission to resist interference, while guaranteeing the transmission performance. Copyright © 2013 John Wiley & Sons, Ltd.

We describe a security flaw in the construction of the privacy-preserving trie presented in an ICC'12 paper. The flaw allows a semi-honest-but-curious cloud to forge a verifiable dictionary entry with a set of documents that do not contain the keyword in the query. We then proceed to offer a fix.

Time-critical Location Based Service (LBS) applications in mobile ad hoc networks require fast localization. The conventional localization techniques are, unfortunately, unsuitable for such applications, for they neglect the time needed for localization. As a result, time-critical information may become obsolete, and the mobile users such as vehicles may have moved to new locations before the localization procedure is completed. To address this issue, we formulate a notion of On-Demand Fast Localization (ODFL) and devise a framework to implement this concept over existing routing protocols in MANETs. We present analytical and simulation results to demonstrate that ODFL can significantly reduce the time solely needed for localization before starting time-critical applications. Moreover, we show that ODFL can also improve location privacy and reduce energy consumptions.

A graph is a fundamental and general data structure underlying all data applications. Many applications today call for the management and query capabilities directly on graphs. Real time graph streams, as seen in road networks, social and communication networks, and web requests, are such applications. Event pattern matching requires the awareness of graph structures, which is different from traditional complex event processing. It also requires a focus on the dynamicity of the graph, time order constraints in patterns, and online query processing, which deviates significantly from previous work on subgraph matching as well. We study the semantics and efficient online algorithms for this important and intriguing problem, and evaluate our approaches with extensive experiments over real world datasets in four different domains.

Answering real-time queries, especially over probabilistic data, is becoming increasingly important for service providers. We study anytime query processing algorithms, and extend the traditional query execution plan with a timing component. Our focus is how to determine this timing component, given the queries' deadline constraints. We consider the common multicore processors. Specifically, we propose two query optimization modes: offline periodic optimization and online optimization. We devise efficient algorithms for both offline and online cases followed by a competitive analysis to show the power of our online optimization. Finally, we perform a systematic experimental evaluation using real-world datasets to verify our approaches.

In this paper we present a middleware named SmartPrint to provide cloud print service in office, where many heterogeneous networks exist. The goal of the system is to shield the communication heterogeneity of the devices in the office and make authorized users freely connect to all the printers with no modification on their terminals. SmartPrint can manages all the printers in an office building, and it provides friendly service for the users who know nothing about the printers. SmartPrint can also automatically choose printers for the office staffs. We propose and implement two printer allocation methods, one aims to improve the experience of the user with short print job, and the other is a multiple attributes decision algorithm which considers all factors including spatial information that impact the user experiences. Through experiments we validate the methods, and prove that SmartPrint achieves high user satisfaction from collected real data.

How to achieve energy efficiency to run a cloud data center is a major challenge in the era of rising electricity cost and environmental protection. Various techniques have been devised to help reduce energy consumption for cloud data centers that consist of a large number of identical servers, including dynamic allocation of active servers, consolidating diverse applications to run on them, and adjusting the CPU speed of an active server. Leveraging these techniques, we use an Online Coloring Bin Packing problem to model the consolidation problem and devise an effective application-aware approximation algorithm to find a near-optimal solution. We show a 1.7 asymptotic approximation ratio. We then apply a Predictive Bayesian Network model to identify daily workload patterns and adjust resource provisioning accordingly. We evaluate our approaches using traces collected from a real data center and demonstrate that (1) our prediction algorithm is effective in estimating future demands, (2) our coordinated approaches can provide significant savings of energy and operational costs close to the near-optimal offline solution, and (3) our approaches incur little reliability costs in term of wear-and-tear of server components.

A mobile underwater wireless sensor network is a system of mobile underwater sensors which are acoustically networked. Existing ocean studies using independent mobile sensors have led to many interesting discoveries. Therefore, the networking capability will extend the capability of existing approaches and enable novel applications because it provides more control and coordination of the sensors. However, network mobility and environment uncertainty create numerous challenging issues which need to be addressed before such a paradigm becomes reality. Network deployment is among the most important problems because it has a significant impact on other research areas. In this paper, we consider the reuse-based deployment scheme in which a mobile underwater sensor network operates in a bounded area and a sensor, when reaching beyond the area, is deployed back into it. We propose a deployment framework to study the connectivity and coverage of such networks and show its effectiveness through two case studies. Our framework is based on the idea that the reuse of network nodes stabilizes these network metrics. By modeling them, we can estimate the number of nodes needed to achieve a requirement on network coverage or network connectivity only by solving algebraic equations rather than running more simulations.

Admission control (AC) is an effective mechanism for providing bandwidth assurance in wireless mesh networks. Early AC schemes over multirate WMNs typically use a pre-chosen rate or a MAC-layer adapted rate for each link, denying data sessions that could have been admitted should a better multirate AC be available. Taking full advantage of multirate WMNs, we present a rate-adaptive admission control protocol (RaAC) for IEEE 802.11-based WMNs. RaAC consists of three major components: (1) a rate adaption algorithm to meet the bandwidth requirement of the data session and satisfy the channel condition of the PHY layer; (2) a new path-selection metric to balance between hop counts, bandwidth, rates, and other network parameters; and (3) a routing-coupled, distributed, rate-adaptive admission control algorithm to admit data sessions with bandwidth assurance. Through simulations, we show that RaAC is efficient and effective in meeting bandwidth requirements.

Opportunistic routing (OR) is a viable approach for improving performance of wireless communications. Previous studies on OR have focused on cost minimization, performance of multiple rates, congestion control, and other issues. Bandwidth assurance over OR, however, has not been adequately investigated. To bridge this gap, we present a bandwidth-aware opportunistic routing (BOR) with admission control (AC) protocol named BOR/AC. In particular, by analyzing the expected available bandwidth (EAB) and the expected transmission cost (ETC) in OR, we first devise a new metric called BCR (bandwidth-cost ratio) to determine the priority of relays in the forwarding candidates set. Admission control is then applied to admit or reject traffic flows based on estimated expected available bandwidth. Extensive simulation results show that BOR/AC consistently achieves much better performance than existing opportunistic routing protocols.

"The Marauder's Map,” a magical map in J.K. Rowling's fantasy series Harry Potter and the Prisoner of Azkaban [CHECK END OF SENTENCE], can be used as a surveillance tool to show all moving objects within the boundary of "Hogwarts School of Witchcraft and Wizardry” at a spell. In this paper, we introduce a similar forensic surveillance tool for wireless networks. Our system, the digital Marauder's map, can reveal the locations of WiFi-enabled mobile devices within the coverage area of a high-gain antenna. The digital Marauder's map is built solely with off-the-shelf wireless equipments, and features a mobile design that can be quickly deployed to a new location for instant usage without training. We present a comprehensive set of theoretical analysis and experimental results which demonstrate the coverage and localization accuracy of the digital Marauder's map.

The skyline query can help identify the “best” objects in a multi-attribute dataset. During the past decade, this query has received considerable attention in the database research community. Most research focused on computing the “skyline” of a dataset, or the set of “skyline objects” that are not dominated by any other object. Such algorithms are not appropriate in an online system, which should respond in real time to skyline query requests with arbitrary subsets of the attributes (also called subspaces). To guarantee real-time response, an online system should precompute the skylines for all subspaces, and look up a skyline upon query. Unfortunately, because the number of subspaces is exponential to the number of attributes, such pre computation has very expensive storage cost and update cost. We propose the Compressed SkyCube (CSC) that is much more compact, yet can still return the skyline of any subspace without consulting the base table. The CSC therefore combines the advantage of precomputation in that it can respond to queries in real time, and the advantage of no-precomputation in that it has efficient space cost and update cost. This article presents the CSC data structures, the CSC query algorithm, the CSC update algorithm, and the CSC initial computation scheme. A solution to extend to high-dimensional data is also proposed.

Intersection collision warning system has been widely studied with the progress in wireless communication technology and positioning devices, which are now increasingly available on smart phones. In this paper, we present an Intersection Collision Warning (ICW) system using Wi-Fi smart phones with built-in GPS receivers for vehicular ad-hoc networks. In the system, smart phones first retrieve safety-related information, i.e., location, moving direction and velocity, via onboard GPS receivers and then periodically exchange the information using standard wireless communication between vehicles to compute the probability of potential collision and issue warnings when necessary. Simulation results show that our ICW system can significantly reduce the probability of collisions.

Cyber crimes often involve complicated scenes. In this paper, we investigate unidentified crimes committed through anonymous communication networks. We developed a long Pseudo-Noise (PN) code based Direct Sequence Spread Spectrum (DSSS) flow marking technique for invisibly tracing suspect anonymous flows. By interfering with a sender's traffic and marginally varying its rate, an investigator can embed a secret spread spectrum signal into the sender's traffic. Each signal bit is modulated with a small segment of a long PN code. By tracing where the embedded signal goes, the investigator can trace the sender and receiver of the suspect flow despite the use of anonymous networks. Benefits of the Long PN code include its resistance to previous discovered detection approaches. We may also use the vast number of long PN code at different phases to conduct parallel tracback without worrying about the interference between codes. Using a combination of analytical modeling and experiments on Anonymizer, we demonstrate the effectiveness of the long PN code based DSSS watermarking technique.

Constructing sensing barriers using wireless sensor networks has important applications in military operations and homeland security. The goal of forming a sensing barrier is to detect intruders attempting to cross the network. Early studies often assume that sensors remain static once deployed. We note that barrier gaps may occur at deployment if sensors are deployed at random. Barrier gaps may also occur in an existing barrier if some sensors used to form the barrier start malfunctioning or run out of power. We present an efficient solution to solve this problem. In particular, we devise an efficient algorithm to find sensing gaps and relocate mobile sensors to form a new barrier while balancing the energy consumption among mobile sensors. We also investigate the related design issues and performance tradeoffs. Simulation results show that our algorithms can effectively improve the barrier coverage of a wireless sensor network under a wide range of deployment parameters. These results provide insights and guidelines to the deployment, design, and performance of mobile wireless sensor networks for barrier coverage.

In this paper, we present 3DLoc: an integrated system of hardware and software toolkits for locating an 802.11-compliant mobile device in a three dimensional (3D) space. 3DLoc features two specialized antennas: an azimuth antenna and an elevation antenna, for detecting the azimuth and elevation angles of a mobile device respectively in real time. To improve positioning accuracy in real-world urban settings, we propose various signal processing techniques such as clustering and wavelet-transform based denoising, and present theoretical analysis of the accuracy of these techniques. With different antenna configurations, 3DLoc is able to track single or multiple targets in one round of azimuth scanning and elevation scanning. We conduct extensive experiments to demonstrate the efficiency and accuracy of 3DLoc. 3DLoc can be used in various applications, including wireless network forensics for locating anonymous criminal mobile devices.

Barrier coverage is a critical issue in wireless sensor networks for various battlefield and homeland security applications. The goal is to effectively detect intruders that attempt to penetrate the region of interest. A sensor barrier is formed by a connected sensor cluster across the entire deployed region, acting as a "trip wire" to detect any crossing intruders. In this paper we study how to efficiently improve barrier coverage using mobile sensors with limited mobility. After the initial deployment, mobile sensors can move to desired locations and connect with other sensors in order to create new barriers. However, simply moving sensors to form a large local cluster does not necessarily yield a global barrier. This global nature of barrier coverage makes it a challenging task to devise effective sensor mobility schemes. Moreover, a good sensor mobility scheme should efficiently improve barrier coverage under the constraints of available mobile sensors and their moving range. We first explore the fundamental limits of sensor mobility on barrier coverage and present a sensor mobility scheme that constructs the maximum number of barriers with minimum sensor moving distance. We then present an efficient algorithm to compute the existence of barrier coverage with sensors of limited mobility, and examine the effects of the number of mobile sensors and their moving ranges on the barrier coverage improvement. Both the analytical results and performance of the algorithms are evaluated via extensive simulations.

With current technologies submarines can thwart active or passive sonar detection. A viable alternative to detect submissible vessels is to use magnetic or acoustic sensors in close proximity to possible underwater pathways of them. This approach may require deploying large-scale underwater sensor networks to form barriers. We show new results for construction barriers in 3D sensor networks. First, we prove that barriers are unlikely to exist in a large 3D fixed emplacement sensor field where sensor locations follow a Poisson point process. We then derive the notion of 3D stealth distance to measure how far a submarine can travel in a sensor network without detection. Finally, we describe energy conserving approaches for constructing a 3D barrier using mobile nodes to detect intruders. We focus on developing an energy efficient matching of mobile sensors that move to cover gridpoints using auction algorithms. We compare our results of the auction approach to an optimal approach using simulations and show that the auction algorithm produces similar results to the optimal approach at a reduced computational expense. This provides a fruitful new approach to constructing barriers in 3D sensor networks.

"The Marauder's Map" is a magical map in J. K. Rowling's fantasy series, "Harry Potter and the Prisoner of Azkaban". It shows all moving objects within the boundary of the "Hogwarts School of Witchcraft and Wizardry". In this paper, we introduce a similar attack to location privacy in wireless networks. Our system, namely the digital Marauder's map, can reveal the locations of WiFi-enabled mobile devices within the coverage area of a single high-gain antenna. The digital Marauder's map is built solely with off-the-shelf wireless equipments, and features a mobile design that can be quickly deployed to a new location and instantly used without training. We present a comprehensive set of theoretical analysis and experimental results which demonstrate the coverage and localization accuracy of the digital Marauder's map.

Barrier coverage of wireless sensor networks has been studied intensively in recent years under the assumption that sensors are deployed uniformly at random in a large area (Poisson point process model). However, when sensors are deployed along a line (e.g., sensors are dropped from an aircraft along a given path), they would be distributed along the line with random offsets due to wind and other environmental factors. It is important to study the barrier coverage of such line- based deployment strategy as it represents a more realistic sensor placement model than the Poisson point process model. This paper presents the first set of results in this direction. In particular, we establish a tight lower-bound for the existence of barrier coverage under line-based deployments. Our results show that the barrier coverage of the line-based deployments significantly outperforms that of the Poisson model when the random offsets are relatively small compared to the sensor's sensing range. We then study sensor deployments along multiple lines and show how barrier coverage is affected by the distance between adjacent lines and the random offsets of sensors. These results demonstrate that sensor deployment strategies have direct impact on the barrier coverage of wireless sensor networks. Different deployment strategies may result in significantly different barrier coverage. Therefore, in the planning and deployment of wireless sensor networks, the coverage goal and possible sensor deployment strategies must be carefully and jointly considered. The results obtained in this paper will provide important guidelines to the deployment and performance of wireless sensor networks for barrier coverage.

Constructing sensor barriers to detect intruders crossing a randomly-deployed sensor network is an important problem. Early results have shown how to construct sensor barriers to detect intruders moving along restricted crossing paths in rectangular areas. We present a complete solution to this problem for sensors that are distributed according to a Poisson point process. In particular, we present an efficient distributed algorithm to construct sensor barriers on long strip areas of irregular shape without any constraint on crossing paths. Our approach is as follows: We first show that in a rectangular area of width w and length l with w = Ω(log l), if the sensor density reaches a certain value, then there exist, with high probability, multiple disjoint sensor barriers across the entire length of the area such that intruders cannot cross the area undetected. On the other hand, if w = o(log l), then with high probability there is a crossing path not covered by any sensor regardless of the sensor density. We then devise, based on this result, an efficient distributed algorithm to construct multiple disjoint barriers in a large sensor network to cover a long boundary area of an irregular shape. Our algorithm approximates the area by dividing it into horizontal rectangular segments interleaved by vertical thin strips. Each segment and vertical strip independently computes the barriers in its own area. Constructing "horizontal" barriers in each segment connected by "vertical" barriers in neighboring vertical strips, we achieve continuous barrier coverage for the whole region. Our approach significantly reduces delay, communication overhead, and computation costs compared to centralized approaches. Finally, we implement our algorithm and carry out a number of experiments to demonstrate the effectiveness of constructing barrier coverage.

Unauthorized rogue access points (APs), such as those brought into a corporate campus by employees, pose a security threat as they may be poorly managed or insufficiently secured. Any attacker in the vicinity can easily get onto the internal network through a rogue AP, bypassing all perimeter security measures. Existing detection solutions work well for detecting layer-2 rogue APs. It is a challenge, however, to accurately detect a layer-3 rogue AP that is protected by WEP or other security measures. In this paper, we describe a new rogue AP detection method to address this problem. Our solution uses a verifier on the internal wired network to send test traffic towards wireless edge, and uses wireless sniffers to identify rouge APs that relay the test packets. To quickly sweep all possible rogue APs, the verifier uses a greedy algorithm to schedule the channels for the sniffers to listen to. To work with the encrypted AP traffic, the sniffers use a probabilistic algorithm that only relies on observed packet size. Using extensive experiments, we show that the proposed approach can robustly detect rogue APs with moderate network overhead.

Network processors (NP) are designed to provide both performance and flexibility through parallel and programmable architecture, making them superior to general-purpose processors on performance and to hardware-based solutions on flexibility. But NPs also introduce new challenges. It is important to study the limitations of NP architectures so that one can take full advantage of NP resources to achieve the required performance for a given application. It is therefore desirable to develop a general framework for analyzing performance of NP-based applications. This paper presents an analytical method for solving this problem. In particular, we devise a queuing network to model NP resources and application work flows. We then use queuing theory and operational analysis to obtain performance metrics on throughput and response time, among other things, at the component level as well as at the system level. We apply our performance model to SpliceNP, a TCP splicing implementation of content-aware switches on network processors presented in [10], and show that the analytical results using our models match the experimental results from actual implementation.

Given a multiset X={x 1 ,. . .,x n } of real numbers, the floating-point set summation problem asks for S n =x 1 + . . . + x n . Let $E^*_n$ denote the minimum worst-case error over all possible orderings of evaluating S n . We prove that if X has both positive and negative numbers, it is NP-hard to compute S n with the worst-case error equal to $E^*_n$. We then give the first known polynomial-time approximation algorithm that has a provably small error for arbitrary X. Our algorithm incurs a worst-case error at most $2(\lceil\log(n-1)\rceil+1)E^*_n$. (All logarithms log in this paper are base 2.) After X is sorted, it runs in O(n) time. For the case where X is either all positive or all negative, we give another approximation algorithm with a worst-case error at most $\lceil\log\log n\rceil E^*_n$. Even for unsorted X, this algorithm runs in O(n) time. Previously, the best linear-time approximation algorithm had a worst-case error at most $\lceil\log n\rceil E^*_n$, while $E^*_n$ was known to be attainable in O(n log n) time using Huffman coding.

We propose a practical and secure electronic voting protocol for large-scale online elections. Our protocol satisfies a large set of important criteria that has never been put together in a single protocol before. Among all electronic voting schemes in the literature, Sensus, a security-conscious electronic voting protocol proposed by Cranor and Cytron (1997), satisfies most of our criteria. Sensus has been implemented and used in mock elections. However, Sensus suffers from several major drawbacks. For instance, we show that even if all voters follow the Sensus protocol honestly, some voters' votes may still be replaced with different votes without being detected. Our protocol overcomes these drawbacks.

This paper studies the word problem for finitely presented groups under the restriction that words can only be rewritten for a bounded number of times. We obtain a similar result to the Novikov--Boone theorem in the setting of average-case NP-completeness. The word problem we consider here is to decide, when given a finite presentation of a group G, words x, y, z, and an integer k, whether (x -1 yx )z can be derived from z(x -1 yx )z in the presentation of G in k steps. We show that when each component of the instance is chosen uniformly at random, the problem cannot be solved fast on average unless every NP problem under every reasonable distribution on instances can be solved fast on average.

This paper first investigates and analyzes security holes concerning the use of server-side includes (SSI) in some of the most used Web server software packages. We show that, by exploiting features of SSI, one could seriously compromise Web server security. For example, we demonstrate how users can gain access to information they are not supposed to see, and how attackers can crash a Web server computer by having an HTML file execute a simple program. Such attacks can be made with no trace left behind. We have successfully carried out all the attacks described in this paper on dummy servers we set up for this investigation. We then suggest several practical security measures to prevent a Web server from such attacks.

This paper investigates the performance of media access protocols based on on-line scheduling for an optically connected star-coupled system with wavelength division multiple access channels. Hybrid access protocols combining reservation and pre-allocation of receiver channels have been previously proposed. Transmission consisted of a reservation phase followed by a data phase. Each node was allowed to place a reservation for one WDM channel. This protocol is extended in this paper by allowing reservations on multiple channels and using simple on-line scheduling algorithms. Existing scheduling algorithms (all are off-line) for similar reservation problems tend to have high implementation and computational complexity. We require that scheduling algorithms be real-time and amenable to hardware implementation. The performance of the extended protocol incorporating two simple on-line scheduling algorithms is presented in this paper. We show that the slight increased computational overhead with scheduling is justified by reduced packet latency and higher utilization, especially for client-server traffic.

Article Free Access Share on Average-case completeness of a word problem for groups Author: Jie Wang Department of Mathematical Sciences, University of North Carolina at Greensboro, Greensboro, NC Department of Mathematical Sciences, University of North Carolina at Greensboro, Greensboro, NCView Profile Authors Info & Claims STOC '95: Proceedings of the twenty-seventh annual ACM symposium on Theory of computingMay 1995 Pages 325–334https://doi.org/10.1145/225058.225153Published:29 May 1995Publication History 10citation343DownloadsMetricsTotal Citations10Total Downloads343Last 12 Months6Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Two necessary and sufficient conditions for all E-complete sets to contain dense P subsets are shown. We then prove that every ≤pm-hard for E set and its complement contain dense E∩UP subsets. As a corollary, every NE-complete set and its complement contain dense E∩UP subsets.

This paper studies polynomial-time approximations to intractable sets using the concept of p-productivity. It is shown that every (deterministic and nondeterministic) superpolynomial-time computable p-productive set is p-levelable. All $ \leq _m^p $-complete sets for any deterministic superpolynomial time class are shown to be p-productive. It is then shown that the complement of any honest k-creative set in NP is p-levelable. This settles an open problem in Homer [Theoret. Comput. Sci., 47 (1986), pp. 169–180].

We study p-creative sets and p-completely creative sets. We first prove that for recursively enumerable sets, p-creativeness is equivalent to p-complete creativeness and Myhill's theorem still holds in the polynomial setting. We then consider p-creativity and p-complete creativity for time complexity classes. We prove that for P, p-creativeness is equivalent to p-complete creativeness. Moreover, we prove that a set A is p-m-complete for DEXT iff A is p-creative for P in DEXT. Since every p-m-complete set for DEXT is p-1-complete (Berman, 1977), we know that Myhill's theorem still holds for P in DEXT. These results can also be proved for NP in NEXT. k-creative sets and k-completely creative sets in NP are next studied. (k,l)-creative sets and (k,l)-completely creative sets in a more general setting are defined and shown to exist. It is known that k-completely creative sets are NP-complete (Joseph and Young, 1985), but it is not known whether the converse is true. We approach this problem based on our “double diagonalization” technique of showing that every p-m-complete set for DEXT is p-creative for P. A new class of k-completely creative sets is constructed as well.