Greybox fuzzing has achieved success in revealing bugs and vulnerabilities in programs. However, bit-level randomized mutation strategies have limited the fuzzer’s performance on structured data. Specialized fuzzers can handle specific structured data, but require additional efforts in grammar and suffer from low throughput. In this paper, we explore the potential of utilizing Large Language Models (LLMs) to enhance greybox fuzzing for structured data. We utilize the pre-trained knowledge of LLM about data conversion and format to generate new valid inputs. We further enhance the LLM on structured formats and mutation strategies by fine-tuning with paired mutation seeds. Our LLM-enhanced fuzzer, LLAMAFUZZ, integrates the power of LLM to understand and mutate structured data to fuzzing. Our experiments show that LLAMAFUZZ outperformed the state-of-the-art methods on all benchmarks, demonstrating its effectiveness in various scenarios.

The transferability of adversarial examples allows for the attack on unknown deep neural networks (DNNs), posing a serious threat to many applications and attracting great attention. In this paper, we improve the transferability of adversarial examples by incorporating the Bayesian formulation into both the model parameters and model input, enabling their joint diversification. We demonstrate that combination of Bayesian formulations for both the model input and model parameters yields significant improvements in transferability. By introducing advanced approximations of the posterior distribution over the model input, adversarial transferability achieves further enhancement, surpassing all state-of-the-arts when attacking without model fine-tuning. Additionally, we propose a principled approach to fine-tune model parameters within this Bayesian framework. Extensive experiments demonstrate that our method achieves a new state-of-the-art in transfer-based attacks, significantly improving the average success rate on ImageNet and CIFAR-10. We will make our code publicly available.

Recent decoding methods improve the factuality of large language models (LLMs) by refining how the next token is selected during generation.These methods typically operate at the token level, leveraging internal representations to suppress superficial patterns.Nevertheless, LLMs remain prone to hallucinations, especially over longer contexts.In this paper, we propose Active Layer-Contrastive Decoding (ActLCD), a novel decoding strategy that actively decides when to apply contrasting layers during generation.By casting decoding as a sequential decision-making problem, ActLCD employs a reinforcement learning policy guided by a reward-aware classifier to optimize factuality beyond the token level.Our experiments demonstrate that ActLCD surpasses state-of-the-art methods across five benchmarks, showcasing its effectiveness in mitigating hallucinations in diverse generation scenarios.

Modern compilers, such as LLVM, are complex. Due to their complexity, manual testing is unlikely to suffice, yet formal verification is difficult to scale. End-to-end fuzzing can be used, but it has difficulties in discovering LLVM backend problems for two reasons. First, frontend preprocessing and middle optimization shield the backend from seeing diverse inputs. Second, branch coverage cannot provide effective feedback as LLVM backend contains much reusable code. In this paper, we implement IRFuzzer to investigate the need of specialized fuzzing of the LLVM compiler backend. We focus on two approaches to improve the fuzzer: guaranteed input validity using constrained mutations to improve input diversity and new metrics to improve feedback quality. The mutator in IRFuzzer can generate a wide range of LLVM IR inputs, including structured control flow, vector types, and function definitions. The system instruments coding patterns in the compiler to monitor the execution status of instruction selection. The instrumentation not only provides new coverage feedback on the matcher table but also guides the mutator on architecture-specific intrinsics. We ran IRFuzzer on 29 mature LLVM backend targets. IRFuzzer discovered 78 new, confirmed bugs in LLVM upstream, none of which existing fuzzers could discover. This demonstrates that IRFuzzer is far more effective than existing fuzzers. Upon receiving our bug report, the developers have fixed 57 bugs and back-ported five fixes to LLVM 15, which shows that specialized fuzzing provides actionable insights to LLVM developers.

Crafting high-quality fuzz drivers not only is time-consuming but also requires a deep understanding of the library. However, the state-of-the-art automatic fuzz driver generation techniques fall short of expectations. While fuzz drivers derived from consumer code can reach deep states, they have limited coverage. Conversely, interpretative fuzzing can explore most API calls but requires numerous attempts within a large search space. We propose PromptFuzz, a coverage-guided fuzzer for prompt fuzzing that iteratively generates fuzz drivers to explore undiscovered library code. To explore API usage in fuzz drivers during prompt fuzzing, we propose several key techniques: instructive program generation, erroneous program validation, coverage-guided prompt mutation, and constrained fuzzer scheduling. We implemented PromptFuzz and evaluated it on 14 real-world libraries. Compared with OSS-Fuzz and Hopper (the state-of-the-art fuzz driver generation tool), fuzz drivers generated by PromptFuzz achieved 1.61 and 1.63 times higher branch coverage than those by OSS-Fuzz and Hopper, respectively. Moreover, the fuzz drivers generated by PromptFuzz detected 33 genuine, new bugs out of a total of 49 crashes, out of which 30 bugs have been confirmed by their respective communities.

The remarkable capability of large language models (LLMs) in generating high-quality code has drawn increasing attention in the software testing community. However, existing code LLMs often demonstrate unsatisfactory capabilities in generating accurate, complete tests since they were trained on code snippets collected without differentiating between code for testing and for other purposes. In this paper, we present a large-scale dataset, UniTSyn, which can enhance LLMs for Unit Test Synthesis. Associating tests with the tested functions is crucial for LLMs to infer the expected behavior and the logic paths to be verified. By leveraging Language Server Protocol, UniTSyn achieves the challenging goal of collecting focal-test pairs without per-project execution setups or per-language heuristics, which tend to be fragile and difficult to scale. Containing 2.7 million focal-test pairs across five mainstream programming languages, it can enhance the test generation ability of LLMs. Our experiments demonstrate that, by building an autoregressive LLM based on UniTSyn, we can achieve significant benefits in learning and understanding unit test representations, resulting in improved generation accuracy and code coverage across all the evaluated programming languages.

Adversarial prompts (or say, adversarial examples) generated using gradient-based methods exhibit outstanding performance in performing automatic jailbreak attacks against safety-aligned LLMs. Nevertheless, due to the discrete nature of texts, the input gradient of LLMs struggles to precisely reflect the magnitude of loss change that results from token replacements in the prompt, leading to limited attack success rates against safety-aligned LLMs, even in the *white-box* setting. In this paper, we explore a new perspective on this problem, suggesting that it can be alleviated by leveraging innovations inspired in transfer-based attacks that were originally proposed for attacking *black-box* image classification models. For the first time, we appropriate the ideologies of effective methods among these transfer-based attacks, *i.e.*, Skip Gradient Method and Intermediate Level Attack, into gradient-based adversarial prompt generation and achieve significant performance gains without introducing obvious computational cost. Meanwhile, by discussing mechanisms behind the gains, new insights are drawn, and proper combinations of these methods are also developed. Our empirical results show that 87% of the query-specific adversarial suffixes generated by the developed combination can induce Llama-2-7B-Chat to produce the output that exactly matches the target string on AdvBench. This match rate is 33% higher than that of a very strong baseline known as GCG, demonstrating advanced discrete optimization for adversarial prompt generation against LLMs. In addition, without introducing obvious cost, the combination achieves >30% absolute increase in attack success rates compared with GCG when generating both query-specific (38% ->68%) and universal adversarial prompts (26.68% -> 60.32%) for attacking the Llama-2-7B-Chat model on AdvBench. Code at: https://github.com/qizhangli/Gradient-based-Jailbreak-Attacks.

Despite the fact that the state-of-the-art fuzzers can generate inputs efficiently, existing fuzz drivers still cannot adequately cover entries in libraries. Most of these fuzz drivers are crafted manually by developers, and their quality depends on the developers' understanding of the code. Existing works have attempted to automate the generation of fuzz drivers by learning API usage from code and execution traces. However, the generated fuzz drivers are limited to a few specific call sequences by the code being learned. To address these challenges, we present HOPPER, which can fuzz libraries without requiring any domain knowledge to craft fuzz drivers. It transforms the problem of library fuzzing into the problem of interpreter fuzzing. The interpreters linked against libraries under test can interpret the inputs that describe arbitrary API usage. To generate semantically correct inputs for the interpreter, HOPPER learns the intra-and inter-API constraints in the libraries and mutates the program with grammar awareness. We implemented HOPPER and evaluated its effectiveness on 11 real-world libraries against manually crafted fuzzers and other automatic solutions. Our results show that HOPPER greatly outperformed the other fuzzers in both code coverage and bug finding, having uncovered 25 previously unknown bugs that other fuzzers couldn't. Moreover, we have demonstrated that the proposed intra- and inter-API constraint learning methods can correctly learn constraints implied by the library and, therefore, significantly improve the fuzzing efficiency. The experiment results indicate that HOPPER is able to explore a vast range of API usages for library fuzzing out of the box.

Multi-view hierarchical clustering (MCHC) plays a pivotal role in comprehending the structures within multi-view data, which hinges on the skillful interaction between hierarchical feature learning and comprehensive representation learning across multiple views. However, existing methods often overlook this interplay due to the simple heuristic agglomerative strategies or the decoupling of multi-view representation learning and hierarchical modeling, thus leading to insufficient representation learning. To address these issues, this paper proposes a novel Multi-view Hierarchical Clustering Network (MHCN) model by performing simultaneous multi-view learning and hierarchy modeling. Specifically, to uncover efficient tree-like structures among all views, we derive multiple hyperbolic autoencoders with latent space mapped onto the Poincaré ball. Then, the corresponding hyperbolic embeddings are further regularized to achieve the multi-view representation learning principles for both view-common and view-private information, and to ensure hyperbolic uniformity with a well-balanced hierarchy for better interpretability. Extensive experiments on real-world and synthetic multi-view datasets have demonstrated that our method can achieve state-of-the-art hierarchical clustering performance, and empower the clustering results with good interpretability.

Intermediate-level attacks that attempt to perturb feature representations following an adversarial direction drastically have shown favorable performance in crafting transferable adversarial examples. Existing methods in this category are normally formulated with two separate stages, where a directional guide is required to be determined at first and the scalar projection of the intermediate-level perturbation onto the directional guide is enlarged thereafter. The obtained perturbation deviates from the guide inevitably in the feature space, and it is revealed in this paper that such a deviation may lead to sub-optimal attack. To address this issue, we develop a novel intermediate-level method that crafts adversarial examples within a single stage of optimization. In particular, the proposed method, named intermediate-level perturbation decay (ILPD), encourages the intermediate-level perturbation to be in an effective adversarial direction and to possess a great magnitude simultaneously. In-depth discussion verifies the effectiveness of our method. Experimental results show that it outperforms state-of-the-arts by large margins in attacking various victim models on ImageNet (+10.07% on average) and CIFAR-10 (+3.88% on average). Our code is at https://github.com/qizhangli/ILPD-attack.

The adversarial vulnerability of deep neural networks (DNNs) has drawn great attention due to the security risk of applying these models in real-world applications. Based on transferability of adversarial examples, an increasing number of transfer-based methods have been developed to fool black-box DNN models whose architecture and parameters are inaccessible. Although tremendous effort has been exerted, there still lacks a standardized benchmark that could be taken advantage of to compare these methods systematically, fairly, and practically. Our investigation shows that the evaluation of some methods needs to be more reasonable and more thorough to verify their effectiveness, to avoid, for example, unfair comparison and insufficient consideration of possible substitute/victim models. Therefore, we establish a transfer-based attack benchmark (TA-Bench) which implements 30+ methods. In this paper, we evaluate and compare them comprehensively on 10 popular substitute/victim models on ImageNet. New insights about the effectiveness of these methods are gained and guidelines for future evaluations are provided.

This paper substantially extends our work published at ECCV [1], in which an intermediate-level attack was proposed to improve the transferability of some baseline adversarial examples. Specifically, we advocate a framework in which a direct linear mapping from the intermediate-level discrepancies (between adversarial features and benign features) to prediction loss of the adversarial example is established. By delving deep into the core components of such a framework, we show that 1) a variety of linear regression models can all be considered in order to establish the mapping, 2) the magnitude of the finally obtained intermediate-level adversarial discrepancy is correlated with the transferability, 3) further boost of the performance can be achieved by performing multiple runs of the baseline attack with random initialization. In addition, by leveraging these findings, we achieve new state-of-the-arts on transfer-based$\ell _\infty$and$\ell _{2}$attacks. Our code is publicly available athttps://github.com/qizhangli/ila-plus-plus-lr https://github.com/qizhangli/ila-plus-plus-lr .

This paper reports our recent practice of recommending articles to cold-start users at Tencent. Transferring knowledge from information-rich domains to help user modeling is an effective way to address the user-side cold-start problem. Our previous work demonstrated that general-purpose user embeddings based on mobile app usage helped article recommendations. However, high-dimensional embeddings are cumbersome for online usage, thus limiting the adoption. On the other hand, user clustering, which partitions users into several groups, can provide a lightweight, online-friendly, and explainable way to help recommendations. Effective user clustering for article recommendations based on mobile app usage faces unique challenges, including (1) the gap between an active user's behavior of mobile app usage and article reading, and (2) the gap between mobile app usage patterns of active and cold-start users. To address the challenges, we propose a tailored Dual Alignment User Clustering (DAUC) model, which applies a sample-wise contrastive alignment to eliminate the gap between active users' mobile app usage and article reading behavior, and a distribution-wise adversarial alignment to eliminate the gap between active users' and cold-start users' app usage behavior. With DAUC, cold-start recommendation-optimized user clustering based on mobile app usage can be achieved. On top of the user clusters, we further build candidate generation strategies, real-time features, and corresponding ranking models without much engineering difficulty. Both online and offline experiments demonstrate the effectiveness of our work.

Greybox fuzzing has received much attention from developers and researchers due to its success in discovering bugs within many programs. However, randomized algorithms have limited fuzzers’ effectiveness. First, branch coverage feedback that is based on random edge ID can lead to branch collision. Besides, state-of-the-art fuzzers heavily rely on randomized methods to reach new coverage. Even fuzzers with a solver rely on incorrect assumptions, limiting their ability to solve branches and forcing them to turn to randomness as a last resort.We believe deterministic techniques deliver consistent, predictable, reproducible results. We propose Valkyrie, a greybox fuzzer whose performance is boosted primarily by deterministic techniques. Valkyrie combines collision-free branch coverage with context sensitivity to maintain accuracy while introducing an instrumentation removal algorithm to reduce overhead. It also pioneers a new mutation method, compensated step, allowing fuzzers that use solvers to adapt to real-world fuzzing scenarios without using randomness. We implement and evaluate Valkyrie’s effectiveness on the standard benchmark Magma, and a wide variety of real-world programs. Valkyrie triggered 21 unique integer and memory errors, 10.5% and 50% more than AFL++ and Angora, respectively. Valkyrie shows little to no variance across ten trials and is the fastest to trigger half of the bugs. Valkyrie reached 8.2% and 12.4% more branches in real-world programs, compared with AFL++ and Angora, respectively. We also verify that our branch counting and mutation method is better than the state-of-the-art, which shows that deterministic techniques trump random techniques in consistency, predictability, reproducibility, and performance.

Concurrent programs with multiple threads executing in parallel are widely used to unleash the power of multicore computing systems. Owing to their complexity, a lot of research focuses on testing and debugging concurrent programs. Besides correctness, we find that security can also be compromised by concurrency. In this article, we present concurrent program spectre (ConcSpectre), a new security threat that hides malware in nondeterministic thread interleavings. To demonstrate such threat, we have developed a stealth malware technique called concurrent logic bomb by partitioning a piece of malicious code and injecting its components separately into a concurrent program. The malicious behavior can be triggered by certain thread interleavings that rarely happen (e.g.,$< $1%) under a normal execution environment. However, with a new technique called controllable probabilistic activation, we can activate such ConcSpectre malware with a very high probability (e.g.,$>$90%) by remotely disturbing thread scheduling. In the evaluation, more than 1000 ConcSpectre samples are generated, which bypassed most of the antivirus engines in VirusTotal and four well-known online dynamic malware analysis systems. We also demonstrate how to remotely trigger a ConcSpectre sample on a web server and control its activation probability. Our work shows an urgent need for new malware analysis methods for concurrent programs.

Go is a statically typed programming language designed for efficient and reliable concurrent programming. For this purpose, Go provides lightweight goroutines and recommends passing messages using channels as a less error-prone means of thread communication. Go has become increasingly popular in recent years and has been adopted to build many important infrastructure software systems. However, a recent empirical study shows that concurrency bugs, especially those due to misuse of channels, exist widely in Go. These bugs severely hurt the reliability of Go concurrent systems. To fight Go concurrency bugs caused by misuse of channels, this paper proposes a static concurrency bug detection system, GCatch, and an automated concurrency bug fixing system, GFix. After disentangling an input Go program, GCatch models the complex channel operations in Go using a novel constraint system and applies a constraint solver to identify blocking bugs. GFix automatically patches blocking bugs detected by GCatch using Go’s channel-related language features. We apply GCatch and GFix to 21 popular Go applications, including Docker, Kubernetes, and gRPC. In total, GCatch finds 149 previously unknown blocking bugs due to misuse of channels and GFix successfully fixes 124 of them. We have reported all detected bugs and generated patches to developers. So far, developers have fixed 125 blocking misuse-of-channel bugs based on our reporting. Among them, 87 bugs are fixed by applying GFix’s patches directly.

Abstract Research showed that deep learning models are vulnerable to membership inference attacks, which aim to determine if an example is in the training set of the model. We propose a new framework to defend against this sort of attack. Our key insight is that if we retrain the original classifier with a new dataset that is independent of the original training set while their elements are sampled from the same distribution, the retrained classifier will leak no information that cannot be inferred from the distribution about the original training set. Our framework consists of three phases. First, we transferred the original classifier to a Joint Energy-based Model (JEM) to exploit the model’s implicit generative power. Then, we sampled from the JEM to create a new dataset. Finally, we used the new dataset to retrain or fine-tune the original classifier. We empirically studied different transfer learning schemes for the JEM and fine-tuning/retraining strategies for the classifier against shadow-model attacks. Our evaluation shows that our framework can suppress the attacker’s membership advantage to a negligible level while keeping the classifier’s accuracy acceptable. We compared it with other state-of-the-art defenses considering adaptive attackers and showed our defense is effective even under the worst-case scenario. Besides, we also found that combining other defenses with our framework often achieves better robustness. Our code will be made available at https://github.com/ChenJiyu/meminf-defense.git .

Deep learning models are vulnerable to adversarial examples. Most of current adversarial attacks add pixel-wise perturbations restricted to some \(L^p\)-norm, and defense models are evaluated also on adversarial examples restricted inside \(L^p\)-norm balls. However, we wish to explore adversarial examples exist beyond \(L^p\)-norm balls and their implications for attacks and defenses. In this paper, we focus on adversarial images generated by transformations. We start with color transformation and propose two gradient-based attacks. Since \(L^p\)-norm is inappropriate for measuring image quality in the transformation space, we use the similarity between transformations and the Structural Similarity Index. Next, we explore a larger transformation space consisting of combinations of color and affine transformations. We evaluate our transformation attacks on three data sets --- CIFAR10, SVHN, and ImageNet --- and their corresponding models. Finally, we perform retraining defenses to evaluate the strength of our attacks. The results show that transformation attacks are powerful. They find high-quality adversarial images that have higher transferability and misclassification rates than C&W's \(L^p \) attacks, especially at high confidence levels. They are also significantly harder to defend against by retraining than C&W's \(L^p \) attacks. More importantly, exploring different attack spaces makes it more challenging to train a universally robust model.

The vulnerability of deep neural networks (DNNs) to adversarial examples has drawn great attention from the community. In this paper, we study the transferability of such examples, which lays the foundation of many black-box attacks on DNNs. We revisit a not so new but definitely noteworthy hypothesis of Goodfellow et al.'s and disclose that the transferability can be enhanced by improving the linearity of DNNs in an appropriate manner. We introduce linear backpropagation (LinBP), a method that performs backpropagation in a more linear fashion using off-the-shelf attacks that exploit gradients. More specifically, it calculates forward as normal but backpropagates loss as if some nonlinear activations are not encountered in the forward pass. Experimental results demonstrate that this simple yet effective method obviously outperforms current state-of-the-arts in crafting transferable adversarial examples on CIFAR-10 and ImageNet, leading to more effective attacks on a variety of DNNs. Code at: https://github.com/qizhangli/linbp-attack.

The study of adversarial vulnerabilities of deep neural networks (DNNs) has progressed rapidly. Existing attacks require either internal access (to the architecture, parameters, or training set of the victim model) or external access (to query the model). However, both the access may be infeasible or expensive in many scenarios. We investigate no-box adversarial examples, where the attacker can neither access the model information or the training set nor query the model. Instead, the attacker can only gather a small number of examples from the same problem domain as that of the victim model. Such a stronger threat model greatly expands the applicability of adversarial attacks. We propose three mechanisms for training with a very small dataset (on the order of tens of examples) and find that prototypical reconstruction is the most effective. Our experiments show that adversarial examples crafted on prototypical auto-encoding models transfer well to a variety of image classification and face verification models. On a commercial celebrity recognition system held by clarifai.com, our approach significantly diminishes the average prediction accuracy of the system to only 15.40%, which is on par with the attack that transfers adversarial examples from a pre-trained Arcface model. Our code is publicly available at: https://github.com/qizhangli/nobox-attacks.

Sensors are widely used in modern mobile devices (e.g., smartphones, watches) and may gather abundant information from environments as well as about users, e.g., photos, sounds and locations. The rich set of sensor data enables various applications (e.g., health monitoring) and personalized apps as well. However, the powerful sensing abilities provide opportunities for attackers to steal both personal sensitive data and commercial secrets like never before. Unfortunately, the current design of smart devices only provides a coarse access control on sensors and does not have the capability to audit sensing. We argue that knowing how often the sensors are accessed and how much sensor data are collected is the first-line defense against sensor data breach. Such an ability is yet to be designed. In this paper, we propose a framework that allows users to acquire sensor data usages. In particular, we leverage a hook-based track method to track sensor accesses. Thus, with no need to change the source codes of the Android system and applications, we can intercept sensing operations to graphic sensors, audio sensors, location sensors, and standard sensors, and audit them from four aspects: flow audit, frequency audit, duration audit and invoker audit. Then, we implement a prototype, referred to as senDroid, which visually shows the quantitative usages of these sensors in real time at a performance overhead of [0.04-8.05] percent. senDroid allows Android users to audit the applications even when they bypass the Android framework via JNI invocations or when the malicious codes are dynamically loaded from the server side. Our empirical study on 1,489 popular apps in three well-known Android app markets shows that 26.32 percent apps access sensors when the apps are launched, and 11.01 percent apps access sensors while the apps run in the background. Furthermore, we analyze the relevance between sensor usage patterns and third-party libraries, and reverse-engineering on suspicious third-party libraries shows that 77.27 percent apps access sensors via third-party libraries. Our results call attentions to address the users' privacy concerns caused by sensor access.

Greybox fuzzing has made impressive progress in recent years, evolving from heuristics-based random mutation to approaches for solving individual branch constraints. However, they have difficulty solving path constraints that involve deeply nested conditional statements, which are common in image and video decoders, network packet analyzers, and checksum tools. We propose an approach for addressing this problem. First, we identify all the control flow-dependent conditional statements of the target conditional statement. Next, we select the taint flow-dependent conditional statements. Finally, we use three strategies to find an input that satisfies all conditional statements simultaneously. We implemented this approach in a tool called Matryoshka and compared its effectiveness on 13 open source programs against other state-of-the-art fuzzers. Matryoshka has significantly higher cumulative line and branch coverage than AFL, QSYM, and Angora. We manually classified the crashes found by Matryoshka into 41 unique new bugs and obtained 12 CVEs. Our evaluation also uncovered the key technique contributing to Matryoshka's impressive performance: it collects only the nesting constraints that may cause the target conditional statement unreachable, which greatly simplifies the path constraints that it has to solve.

Fuzzing is a popular technique for finding software bugs. However, the performance of the state-of-the-art fuzzers leaves a lot to be desired. Fuzzers based on symbolic execution produce quality inputs but run slow, while fuzzers based on random mutation run fast but have difficulty producing quality inputs. We propose Angora, a new mutation-based fuzzer that outperforms the state-of-the-art fuzzers by a wide margin. The main goal of Angora is to increase branch coverage by solving path constraints without symbolic execution. To solve path constraints efficiently, we introduce several key techniques: scalable byte-level taint tracking, context-sensitive branch count, search based on gradient descent, and input length exploration. On the LAVA-M data set, Angora found almost all the injected bugs, found more bugs than any other fuzzer that we compared with, and found eight times as many bugs as the second-best fuzzer in the program who. Angora also found 103 bugs that the LAVA authors injected but could not trigger. We also tested Angora on eight popular, mature open source programs. Angora found 6, 52, 29, 40 and 48 new bugs infile,jhead,nm,objdumpandsize, respectively. We measured the coverage of Angora and evaluated how its key techniques contribute to its impressive performance.

Third-party libraries are widely used in Android applications to ease development and enhance functionalities. However, the incorporated libraries also bring new security & privacy issues to the host application, and blur the accounting between application code and library code. Under this situation, a precise and reliable library detector is highly desirable. In fact, library code may be customized by developers during integration and dead library code may be eliminated by code obfuscators during application build process. However, existing research on library detection has not gracefully handled these problems, thus facing severe limitations in practice. In this paper, we propose LibPecker, an obfuscation-resilient, highly precise and reliable library detector for Android applications. LibPecker adopts signature matching to give a similarity score between a given library and an application. By fully utilizing the internal class dependencies inside a library, LibPecker generates a strict signature for each class. To tolerate library code customization and elimination as much as possible, LibPecker introduces adaptive class similarity threshold and weighted class similarity score when calculating library similarity. To quantitatively evaluate the precision and the recall of LibPecker, we perform the first such experiment (to the best of our knowledge) with a large number of libraries and applications. Results show that LibPecker significantly outperforms the state-of-the-art tools in both recall and precision (91% and 98.1% respectively).

Deep learning has shown impressive performance on hard perceptual problems. However, researchers found deep learning systems to be vulnerable to small, specially crafted perturbations that are imperceptible to humans. Such perturbations cause deep learning systems to mis-classify adversarial examples, with potentially disastrous consequences where safety or security is crucial. Prior defenses against adversarial examples either targeted specific attacks or were shown to be ineffective.

HIGHT is a lightweight block cipher which has been adopted as a standard block cipher. In this paper, we present a bit-level algebraic fault analysis (AFA) of HIGHT, where the faults are perturbed by a stealthy HT. The fault model in our attack assumes that the adversary is able to insert a HT that flips a specific bit of a certain intermediate word of the cipher once the HT is activated. The HT is realized by merely 4 registers and with an extremely low activation rate of about 0.000025. We show that the optimal location for inserting the designed HT can be efficiently determined by AFA in advance. Finally, a method is proposed to represent the cipher and the injected faults with a merged set of algebraic equations and the master key can be recovered by solving the merged equation system with an SAT solver. Our attack, which fully recovers the secret master key of the cipher in 12572.26 seconds, requires three times of activation on the designed HT. To the best of our knowledge, this is the first Trojan attack on HIGHT.

Dynamic revocation of permissions of installed Android applications has been gaining popularity, because of the increasing concern of security and privacy in the Android platform. However, applications often crash or misbehave when their permissions are revoked, rendering applications completely unusable. Even though Google has officially introduced the new permission mechanism in Android 6.0 to explicitly support dynamic permission revocation, the issue still exists. In this paper, we conduct an empirical study to understand the latest application practice post Android 6.0. Specifically, we design a practical tool, referred to as revDroid, to help us to empirically analyze how often the undesirable side effects, especially application crash, can occur in off-the-shelf Android applications. From the analysis of 248 popular applications from Google Play Store, revDroid finds out that 70% applications and 46% permission-relevant calls do not appropriately catch exceptions caused by permission revocation, while third-party libraries pay much more attention to permission revocation. We also use revDroid to analyze 132 recent malware samples. The result shows that only 27% malwares and 36% permission-relevant API calls of malwares fail to consider the permission revocation. In fact, many of them perform specialized handling of permission revocation to keep the core malicious logic running. Finally, revDroid can be used to help developers uncover the unhandled permission revocations during development time and greatly improve the application quality.

Many mobile services consist of two components: a server providing an API, and an application running on smartphones and communicating with the API. An unresolved problem in this design is that it is difficult for the server to authenticate which app is accessing the API. This causes many security problems. For example, the provider of a private network API has to embed secrets in its official app to ensure that only this app can access the API; however, attackers can uncover the secret by reverse-engineering. As another example, malicious apps may send automatic requests to ad servers to commit ad fraud.

Modern mobile devices, especially smartphones, are widely equipped with cameras, which enable their owners to capture every memorable moment or scenery, such as parties with friends. However, significant privacy concerns are posed by the potential possibility of revealing a large amount of privacy contained by photos, e.g., portrait of a person. World Driven Access Control (WDAC) [1], which triggered by environment signs rather than user operations, provides a privacy access control mechanism for photographed objects (including people and other objects containing sensitive information). WDAC supports several policy label forms which either have impact on the normal appearance of objects or rely on sensors other than camera to sense policy labels. This paper proposes an approach of labelling with a Near Infrared (NIR) label which relies only on camera and has no influence on normal appearance of objects. When an object wears a NIR label, surrounding people are unaware of the existence of the labels. Meanwhile, we design and implement a policy label recognition and policy enforcement system based on Android. The system is able to recognize NIR labels binding to objects, and then enforce privacy policies, such as Gaussian Blur, on these objects to protect their privacy.

To protect sensitive resources from unauthorized use, modern mobile systems, such as Android and iOS, design a permission-based access control model. However, current model could not enforce fine-grained control over the dynamic permission use contexts, causing two severe security problems. First, any code package in an application could use the granted permissions, inducing attackers to embed malicious payloads into benign apps. Second, the permissions granted to a benign application may be utilized by an attacker through vulnerable application interactions. Although ad hoc solutions have been proposed, none could systematically solve these two issues within a unified framework. This paper presents the first such framework to provide context-sensitive permission enforcement that regulates permission use policies according to system-wide application contexts, which cover both intra-application context and inter-application context. We build a prototype system on Android, named FineDroid, to track such context during the application execution. To flexibly regulate the context-sensitive permission rules, FineDroid features a policy framework that could express generic application contexts. We demonstrate the benefits of FineDroid by instantiating several security extensions based on the policy framework, for three potential users: end users, administrators, and developers. Furthermore, FineDroid is showed to introduce a minor overhead.

Transport Layer Security (TLS) is the most commonly used security protocol to encrypt web traffic. TLS connections are computationally expensive to set up, so the TLS protocol supports session resumption, where previously negotiated connection parameters can be used to short- circuit the TLS handshake. The server assigns new sessions a session identifier (ID) and caches each session by its ID so it can be retrieved later. As clients come and go, sessions in the server's cache will have to be evicted according to the server's eviction policy. We find that first-in-first-out (FIFO) and least-recently- used (LRU) are the most common session cache eviction policies among popular TLS libraries, however, for applications whose clients connect at regular intervals, such as mobile advertising, the performance of these policies may be far worse than randomly evicting policies from the cache. To handle this, we propose a novel eviction policy for TLS session caches, predictive eviction, that relies on the server knowing the next time each client will connect again. Using a real-world application of such a policy, Android in-application advertising, we build a client that is able to simulate the behavior of a large number of devices requesting mobile advertisements over TLS. We use this simulated client to benchmark the hit rate of the predictive policy compared with eviction policies found in popular TLS library implementations. In addition, we demonstrate that our policy can be implemented efficiently by benchmarking its performance in transactions per second compared with OpenSSL's session cache implementation, and compared with TLS session tickets (an alternative to session caching for resuming TLS sessions). We find that our policy has better hit rate performance than other eviction policies, and can achieve comparable performance to session tickets. To the best of our knowledge, this is the first study of the performance of TLS session resumption strategies.

Smartphones rely on their vibrant application markets; however, plagiarism threatens the long-term health of these markets. We present a scalable approach to detecting similar Android apps based on their semantic information. We implement our approach in a tool called AnDarwin and evaluate it on 265,359 apps collected from 17 markets including Google Play and numerous third-party markets. In contrast to earlier approaches, AnDarwin has four advantages: it avoids comparing apps pairwise, thus greatly improving its scalability; it analyzes only the app code and does not rely on other information-such as the app's market, signature, or description-thus greatly increasing its reliability; it can detect both full and partial app similarity; and it can automatically detect library code and remove it from the similarity analysis. We present two use cases for AnDarwin: finding similar apps by different developers (“clones”) and similar apps from the same developer (“rebranded”). In 10 hours, AnDarwin detected at least 4,295 apps that are the victims of cloning and 36,106 rebranded apps. Additionally, AnDarwin detects similar code that is injected into many apps, which may indicate the spread of malware. Our evaluation demonstrates AnDarwin's ability to accurately detect similar apps on a large scale.

Many Android applications are distributed for free but are supported by advertisements. Ad libraries embedded in the app fetch content from the ad provider and display it on the app's user interface. The ad provider pays the developer for the ads displayed to the user and ads clicked by the user. A major threat to this ecosystem is ad fraud, where a miscreant's code fetches ads without displaying them to the user or "clicks" on ads automatically. Ad fraud has been extensively studied in the context of web advertising but has gone largely unstudied in the context of mobile advertising.

An obvious asset of the Android platform is the tremendous number and variety of available apps. There is a less obvious, but potentially even more important, benefit to the fact that nearly all apps are developed using a common platform. We can leverage the relatively uniform nature of Android apps to allow users to tweak applications for improved security, usability, and functionality with relative ease (compared to desktop applications). We design and implement an Android app rewriting framework for customizing behavior of existing applications without requiring source code or app-specific guidance. Following app-agnostic transformation policies, our system rewrites applications to insert, remove, or modify behavior. The rewritten application can run on any unmodified Android device, without requiring rooting or other custom software. This paper describes RetroSkeleton, our app rewriting framework, including static and dynamic interception of method invocations, and creating policies that integrate with each target app. We show that our system is capable of supporting a variety of useful policies, including providing flexible fine-grained network access control, building HTTPS-Everywhere functionality into apps, implementing automatic app localization, informing users of hidden behavior in apps, and updating apps depending on outdated APIs. We evaluate these policies by rewriting and testing more than one thousand real-world apps from Google Play.

Malicious activities involving Android applications are rising rapidly. As prior work on cyber-crimes suggests, we need to understand the economic incentives of the criminals to design the most effective defenses. In this paper, we investigate application plagiarism on Android markets at a large scale. We take the first step to characterize plagiarized applications and estimate their impact on the original application developers. We first crawled 265,359 free applications from 17 Android markets around the world and ran a tool to identify similar applications ("clones"). Based on the data, we examined properties of the cloned applications, including their distribution across different markets, application categories, and ad libraries. Next, we examined how cloned applications affect the original developers. We captured HTTP advertising traffic generated by mobile applications at a tier-1 US cellular carrier for 12 days. To associate each Android application with its advertising traffic, we extracted a unique advertising identifier (called the client ID) from both the applications and the network traces. We estimate a lower bound on the advertising revenue that cloned applications siphon from the original developers, and the user base that cloned applications divert from the original applications. To the best of our knowledge, this is the first large scale study on the characteristics of cloned mobile applications and their impact on the original developers.

Malicious activities involving Android applications are rising rapidly. As prior work on cyber-crimes suggests, we need to understand the economic incentives of the criminals to design the most effective defenses. In this paper, we investigate application plagiarism on Android markets at a large scale. We take the first step to characterize plagiarized applications and estimate their impact on the original application developers. We first crawled 265,359 free applications from 17 Android markets around the world and ran a tool to identify similar applications ("clones"). Based on the data, we examined properties of the cloned applications, including their distribution across different markets, application categories, and ad libraries. Next, we examined how cloned applications affect the original developers. We captured HTTP advertising traffic generated by mobile applications at a tier-1 US cellular carrier for 12 days. To associate each Android application with its advertising traffic, we extracted a unique advertising identifier (called the client ID) from both the applications and the network traces. We estimate a lower bound on the advertising revenue that cloned applications siphon from the original developers, and the user base that cloned applications divert from the original applications. To the best of our knowledge, this is the first large scale study on the characteristics of cloned mobile applications and their impact on the original developers.

This video demonstrates one potential application of RetroSkeleton, which is a system for specifying and applying transformations to Android apps via bytecode rewriting. These transformation policies are app-agnostic and can be applied to Android apps without any manual guidance. In this video, we show how RetroSkeleton can be used to automatically add custom fine-grained network access controls into an existing app, giving users more control over their apps. We also show the use of the RetroSkeleton web interface, available at http://retroskeleton.com.

Security policies, which specify what applications are allowed to do, are notoriously difficult to specify correctly. Many applications were found to request over-liberal permissions. On mobile platforms, this might prevent a cautious user from installing an otherwise harmless application or, even worse, increase the attack surface in vulnerable applications. As a result of such difficulties, programmers frequently ask about them in on-line fora. Our goal is to gain some insight into both the misuse of permissions and the discussions of permissions in on-line fora. We analyze about 10,000 free apps from popular Android markets and found a significant sub-linear relationship between the popularity of a permission and the number of times when it is misused. We also study the relationship of permission use and the number of questions about the permission on StackOverflow. Finally, we study the effect of the influence of a permission (the functionality that it controls) and the interference of a permission (the number of other permissions that influence the same classes) on the occurrence of both permission misuse and permission discussions in StackOverflow.

An alibi provides evidence of a person's past location and can be critical in proving ones innocence. An alibi involves two parties: the owner, who benefits from the alibi, and the corroborator, who testifies for the owner. As mobile devices become ubiquitous, they can determine where we are and what we are doing, and help us to establish evidence of our location as they accompany us on our daily activities. Existing location-based services like Google Latitude can already track and record our every move, but these systems require us to reveal our identity when recording our location. This leaves our privacy at risk, and requires a trusted third party to maintain our location information.

Trust and anonymity are both desirable properties on the Internet. However, online services and users often have to make the trade off between trust and anonymity due to the lack of usable frameworks for achieving them both. We propose Opaak, a practical anonymous authentication framework. Opaak enables its users to establish identities with different online services while ensuring that these identities cannot be linked with each other or their real identity. In addition, Opaak allows online service providers to control the rate at which users utilize their services while preserving their anonymity. Hence, allowing the service providers to prevent abuse in the form of spam or Sybil attacks, which are prevalent in such online services that offer anonymity. Opaak leverages the mobile phone as a scarce resource combined with anonymous credentials in order to provide these features. We target two kinds of applications for Opaak and identify their requirements in order to achieve both trust and anonymity. We develop efficient protocols for these applications based on anonymous credentials. In addition, we design an architecture that facilitates integration with existing mobile and web applications and allows application developers to transparently utilize our protocols. We implement a prototype on Android and evaluate its performance to demonstrate the practicality of our approach.

Web authentication that is both secure and usable remains a challenge. Passwords are vulnerable to phishing attacks, while physical tokens face deployment obstacles. We propose to leverage the authentication infrastructure of cellular networks to enhance Web authentication. We design WebCallerID, a Web authentication scheme that uses cell phones as physical tokens and uses cellular networks as trusted identity providers. Since WebCallerID requires no user participation during authentication, it prevents security mistakes by users. WebCallerID also prevents rogue websites from replaying authentication assertions or stealing users' identities. We have implemented a prototype of WebCallerID using the OpenID framework. The prototype shows that WebCallerID seamlessly integrates into OpenID-capable Web authentication while avoiding phishing problems in OpenID and simplifying user participation.

Existing handover schemes in wireless LANs, 3G/4G networks, and femtocells rely upon protocols involving centralized authentication servers and one or more access points. These protocols are invariably complex and use extensive signaling on the wireless backhaul since they aim to be be efficient (minimal handover latency) without sacrificing robustness. However, the mobile user has little involvement especially with the so-calledcontext transferstage; this stage involves the transfer of necessary state to the new access point as well as the enforcement of security goals such as user authentication and single point of access. We propose the incorporation of usercapabilities, network-asserted proofs of user identity and access control, as a general mechanism to simplify the context transfer stage. To this end, we have designedCapAuth, a capability-based scheme that has reduced complexity, low overhead, high level of fault tolerance and is general enough to implement a range of security policies.

Third Generation (3G) cellular networks take advantage of time-varying and location-dependent channel conditions of mobile users to provide broadband services. Under fairness and QoS constraints, they use opportunistic scheduling to efficiently utilize the available spectrum. Opportunistic scheduling algorithms rely on the collaboration among all mobile users to achieve their design objectives. However, we demonstrate that rogue cellular devices can exploit vulnerabilities in popular opportunistic scheduling algorithms, such as Proportional Fair (PF) and Temporal Fair (TF), to usurp the majority of time slots in 3G networks. Our simulations show that under realistic conditions, only five rogue device per 50-user cell can capture up to 95 percent of the time slots, and can cause 2-second end-to-end interpacket transmission delay on VoIP applications for every user in the same cell, rendering VoIP applications useless. To defend against this attack, we propose strengthening the PF and TF schedulers and a robust handoff scheme.

Most cryptographic algorithms provide a means for secret and authentic communication. However, under many circumstances, the ability to repudiate messages or deny a conversation is no less important than secrecy and authenticity. For whistleblowers, informants, political dissidents and journalists --- to name a few --- it is most important to have means for deniable conversation, where electronic communication must mimic face-to-face private meetings. Off-the-Record Messaging, proposed in 2004 by Borisov, Goldberg and Brewer, and its subsequent improvements, simulate private two-party meetings. Despite some attempts, the multi-party scenario remains unresolved.

The current security model used by web browsers, the Same Origin Policy (SOP), does not support secure cross-domain communication desired by web mashup developers. The developers have to choose between no trust, where no communication is allowed, and full trust, where third-party content runs with the full privilege of the integrator. Furthermore, the SOP has its own set of security vulnerabilities and pitfalls, including Cross-Site Request Forgery, DNS rebinding and dynamic pharming. To overcome the unfortunate tradeoff between security and functionality forced upon today's mashup developers, we propose OMash, a simple abstraction that treats web pages as objects and allows objects to communicate only via their declared public interfaces. Since OMash does not rely on the SOP for controlling DOM access or cross-domain data exchange, it does not suffer from the SOP's vulnerabilities. We show that OMash satisfies the trust relationships desired by mashup authors and may be configured to be backward compatible with the SOP. We implemented a prototype of OMash using Mozilla Firefox 2.0 and demonstrated several proof-of-concept applications.

Firewalls are among the most pervasive network security mechanisms, deployed extensively from the borders of networks to end systems. The complexity of modern firewall policies has raised the computational requirements for firewall implementations, potentially limiting the throughput of networks. Administrators currently rely on ad hoc solutions to firewall optimization. To address this problem, a few automatic firewall optimization techniques have been proposed, but there has been no general approach to evaluate the optimality of these techniques. In this paper we present a general framework for rule-based firewall optimization. We give a precise formulation of firewall optimization as an integer programming problem and show that our framework produces optimal reordered rule sets that are semantically equivalent to the original rule set. Our framework considers the complex interactions among the rules in firewall configurations and relies on a novel partitioning of the packet space defined by the rules themselves. For validation, we employ this framework on real firewall rule sets for a quantitative evaluation of existing heuristic approaches. Our results indicate that the framework is general and faithfully captures performance benefits of firewall optimization heuristics.

To combat the rapid infection rate of today's Internet worms, signatures for novel worms must be generated soon after an outbreak. This is especially critical in the case of polymorphic worms, whose binary representation changes frequently during the infection process. In this paper, we examine the assumptions underlying two leading network-based signature generation systems for polymorphic worms: polygraph [14] and Hamsa [12]. By identifying an assumption of both systems not met by all vulnerabilities, we discover a class of vulnerabilities (feature omission vulnerabilities) that neither system can accurately characterize. We demonstrate the limitations of polygraph and Hamsa by testing the signatures that they generate for exploits targeting a feature omission vulnerability. We discuss why feature omission vulnerabilities are difficult to characterize and how increased semantic awareness can help the signature generation process.

Spammers use questionable search engine optimization (SEO) techniques to promote their spam links into top search results. In this paper, we focus on one prevalent type of spam - redirection spam - where one can identify spam pages by the third-party domains that these pages redirect traffic to. We propose a five-layer, double-funnel model for describing end-to-end redirection spam, present a methodology for analyzing the layers, and identify prominent domains on each layer using two sets of commercial keywords. one targeting spammers and the other targeting advertisers. The methodology and findings are useful for search engines to strengthen their ranking algorithms against spam, for legitimate website owners to locate and remove spam doorway pages, and for legitimate advertisers to identify unscrupulous syndicators who serve ads on spam pages.

Malware, software with malicious intent, has emerged as a widely-spread threat to system security. It is difficult to detect malware reliably because new and polymorphic malware programs appear frequently. It is also difficult to remove malware and repair its damage to the system because it can extensively modify a system. We propose a novel framework for automatically removing malware from and repairing its damage to a system. The primary goal of our framework is to preserve system integrity. Our framework monitors and logs untrusted programs' operations. Using the logs, it can completely remove malware programs and their effects on the system. Our framework does not require signatures or other prior knowledge of malware behavior. We implemented this framework on Windows and evaluated it with seven spyware, trojan horses, and email worms. Comparing our tool with two popular commercial anti-malware tools, we found that our tool detected all the malware's modifications to the system detected by the commercial tools, but the commercial tools overlooked up to 97% of the modifications detected by our tool. The runtime and space overhead of our prototype tool is acceptable. Our experience suggests that this framework offers an effective new defense against malware.

Security concerns are becoming increasingly critical in networked systems. Firewalls provide important defense for network security. However, misconfigurations in firewalls are very common and significantly weaken the desired security. This paper introduces FIREMAN, a static analysis toolkit for firewall modeling and analysis. By treating firewall configurations as specialized programs, FIREMAN applies static analysis techniques to check misconfigurations, such as policy violations, inconsistencies, and inefficiencies, in individual firewalls as well as among distributed firewalls. FIREMAN performs symbolic model checking of the firewall configurations for all possible IP packets and along all possible data paths. It is both sound and complete because of the finite state nature of firewall configurations. FIREMAN is implemented by modeling firewall rules using binary decision diagrams (BDDs), which have been used successfully in hardware verification and model checking. We have experimented with FIREMAN and used it to uncover several real misconfigurations in enterprise networks, some of which have been subsequently confirmed and corrected by the administrators of these networks.

Software model checking has become a popular tool for verifying programs' behavior. Recent results suggest that it is viable for finding and eradicating security bugs quickly. However, even state-of-the-art model checkers are limited in use when they report an overwhelming number of false positives, or when their lengthy running time dwarfs other software development processes. In this paper we report our experiences with software model checking for security properties on an extremely large scale - an entire Linux distribution consisting of 839 packages and 60 million lines of code. To date, we have discovered 108 exploitable bugs. Our results indicate that model checking can be both a feasible and integral part of the software development process

A key missing link in the creation of secure and robust systems is finding a ost effective way to demonstrate and preserve correspondence between a software design and its implementation. This paper explores the use of software model checking techniques to validate selected design invariants in the EROS operating system kernel. Several global consistency policies in the EROS kernel can be expressed as finite state automata. Using the MOPS static hecker, we have been able to validate the EROS kernel implementation against these automata. In the process, we have confirmed the practical utility of the basic verification technique, identified a number of desirable enhancements in MOPS, and located bugs in the EROS implementation.A key contribution of this paper is establishing that it is practical to integrate software model checking into normal development lifestyle. Model hecking is efficient enough that it does not add noticeably to our build times. This allows us to view it as a tool for error prevention rather than detection. Our work with EROS and MOPS suggests that domain specific application of software model hecking is a practical and powerful technique for software assurance and maintenance.

We describe a formal approach for finding bugs in security-relevant software and verifying their absence. The idea is as follows: we identify rules of safe programming practice, encode them as safety properties, and verify whether these properties are obeyed. Because manual verification is too expensive, we have built a program analysis tool to automate this process. Our program analysis models the program to be verified as a pushdown automaton, represents the security property as a finite state automaton, and uses model checking techniques to identify whether any state violating the desired security goal is reachable in the program. The major advantages of this approach are that it is sound in verifying the absence of certain classes of vulnerabilities, that it is fully interprocedural, and that it is efficient and scalable. Experience suggests that this approach will be useful in finding a wide range of security vulnerabilities in large programs efficiently.

We developed and evaluated seven interfaces for integrating semantic category information with Web search results. List interfaces were based on the familiar ranked-listing of search results, sometimes augmented with a category name for each result. Category interfaces also showed page titles and/or category names, but re-organized the search results so that items in the same category were grouped together visually. Our user studies show that all Category interfaces were more effective than List interfaces even when lists were augmented with category names for each result. The best category performance was obtained when both category names and individual page titles were presented. Either alone is better than a list presentation, but both together provide the most effective means for allowing users to quickly examining search results. These results provide a better understanding of the perceptual and cognitive factors underlying the advantage of category groupings and provide some practical guidance to Web search interface designers. Keywords User Interface, World Wide Web, Search, User Study, Usability, Text Categorization, Focus-In-Context

We developed a user interface that organizes Web search results into hierarchical categories. Text classification algorithms were used to automatically classify arbitrary search results into an existing category structure on-the-fly. A user study compared our new category interface with the typical ranked list interface of search results. The study showed that the category interface is superior both in objective and subjective measures. Subjects liked the category interface much better than the list interface, and they were 50% faster at finding information that was organized into categories. Organizing search results allows users to focus on items in categories of interest rather than having to browse through all the results sequentially.

This paper explores the use of hierarchical structure for classifying a large, heterogeneous collection of web content. The hierarchical structure is initially used to train different second-level classifiers. In the hierarchical case, a model is learned to distinguish a second-level category from other categories within the same top level. In the flat non-hierarchical case, a model distinguishes a second-level category from all other second-level categories. Scoring rules can further take advantage of the hierarchy by considering only second-level categories that exceed a threshold at the top level.

The signature block is a common structured component found in email messages. Accurate identification and analysis of signature blocks is important in many multimedia messaging and information retrieval applications such as email text-to-speech rendering, automatic construction of personal address databases, and interactive message retrieval. It is also a very challenging task, because signature blocks often appear in complex two-dimensional layouts which are guided only by loose conventions. Traditional text analysis methods designed to deal with sequential text cannot handle two-dimensional structures, while the highly unconstrained nature of signature blocks makes the application of two-dimensional grammars very difficult. In this article, we describe an algorithm for signature block analysis which combines two-dimensional structural segmentation with one-dimensional grammatical constraints. The information obtained from both layout and linguistic analysis is integrated in the form of weighted finite-state transducers. The algorithm is currently implemented as a component in a preprocessing system for email text-to-speech rendering.

The signature block is a common structured component found in e-mail messages. Accurate identification and analysis of signature blocks are important in many multimedia messaging and information retrieval applications such as e-mail text-to-speech rendering. Traditional text analysis methods designed to deal with sequential text cannot handle 2D structures, while the highly unconstrained nature of signature blocks makes the application of 2D grammars very difficult. In this paper we describe an algorithm for signature block analysis which combines 2D structural segmentation with 1D grammatical constraints. The information obtained from both geometrical and linguistic analysis are integrated in a form of weighted finite state transducers, and the final solution is the optimal interpretation under both constraints.

E-mail reading is one of the most important commercial applications of text-to-speech synthesis (TTS). Yet e-mail is one of the most difficult types of text to deal with, since it is both highly structured -frequently containing elements such as tables, signatures, "artwork" and quotations from previous messages; and at the same time often lacks any reliable unambiguous indicators for such structure. This paper describes Emu, an e-mail mark-up and rendering program that preprocesses e-mail for TTS. We discuss algorithms for detecting regions of interest in the input text; for "normalizing" the input; and for actually rendering the input through the Bell Labs TTS system.

A new piecewise linear modulation model of handwriting is proposed. In this model, the velocity of handwriting trajectory is modeled as the impulse response of a time varying second order system. For mathematical tractability, the entire trajectory is segmented into several non-overlapping frames, while the natural frequency and the damping factor of the system are assumed to vary linearly with time in each frame and are continuous along the entire trajectory. In other words, handwriting is regarded as an oscillation modulated by a continuous and piecewise linear signal. The parameters of this model are estimated by Powell's optimization algorithm which does not require the computation of the first order derivative. The number and lengths of the frames are decided by a modified binary search algorithm along with the estimation of parameters. This model has achieved very high data compression rate as well as accurate reproduction of real handwriting.