Search engines and advertisers continuously suffer substantial financial losses from click fraud, which poses challenges to existing detection algorithms. Even more concerning, despite ongoing advancements, our understanding of click fraud remains limited, leaving room for sophisticated fraudulent techniques to bypass existing detection measures. In this study, we pivot from examining individual search requests to analyzing search sessions, defined as sequences of consecutive search queries made by the same user. We found that benign users exhibit coherent behavior patterns within these sessions, which contrast clearly with those of fraudulent actors. Specifically, legitimate users tend to conduct searches focused on a single topic at a time. In contrast, fraudsters or automated bots often exhibit diverse, illogical, and incoherent search behaviors within a session. To address this behavioral distinction, we propose CoSeC, a system designed to quantify the “incoherence index” of search sessions. CoSeC integrates literal semantic, temporal, and ad-click behavioral features to evaluate sessions' coherence quantitatively. Our evaluation of CoSeC demonstrates high efficacy, achieving a precision of 95.79% and a recall of 92.40% in identifying incoherent sessions, highlighting CoSeC's substantial potential to enhance real-world click fraud detection.

We know surprisingly little about the prevalence and severity of cybercrime in the U.S. Yet, in order to prioritize the development and distribution of advice and technology to protect end users, we require empirical evidence regarding cybercrime. Measuring crime, including cybercrime, is a challenging problem that relies on a combination of direct crime reports to the government – which have known issues of under-reporting – and assessment via carefully-designed self-report surveys. We report on the first large-scale, nationally representative academic survey (n=11,953) of consumer cybercrime experiences in the U.S. Our analysis answers four research questions: (1) What is the prevalence and (2) the monetary impact of these cybercrimes we measure in the U.S.?, (3) Do inequities exist in victimization?, and (4) Can we improve cybercrime measurement by leveraging social-reporting techniques used to measure physical crime? Our analysis also offers insight toward improving future measurement of cybercrime and protecting users.

Practitioners who seek to defend password-protected resources from online guessing attacks will find a shortage of tooling and techniques to help them. Little research suggests anything beyond blocking or throttling traffic from IP addresses sending suspicious traffic; counting failed authentication requests, or some variant, is often the sole feature used to determine suspicion. In this paper we show that several other features can greatly help distinguishing benign and attack traffic. First, we increase the penalties for clients responsible for fail events involving passwords frequently-guessed by attackers. Second, we reduce the threshold (and thus protect better) for accounts with weak passwords. Third, we detect, and are more forgiving of, login failures caused by users mistyping their passwords. Most importantly, we achieve all of these goals without needing any marker that indicates weak accounts, changing the format in which passwords are stored (i.e. we do not store passwords plaintext or in any recoverable form), or storing any information that might be harmful if leaked. We present an open-source implementation of this system and demonstrate its improvement over simpler blocking strategies in various simulated scenarios.

The past ten years has seen increasing calls to make security research more “scientific”. On the surface, most agree that this is desirable, given universal recognition of “science” as a positive force. However, we find that there is little clarity on what “scientific” means in the context of computer security research, or consensus on what a “Science of Security” should look like. We selectively review work in the history and philosophy of science and more recent work under the label “Science of Security”. We explore what has been done under the theme of relating science and security, put this in context with historical science, and offer observations and insights we hope may motivate further exploration and guidance. Among our findings are that practices on which the rest of science has reached consensus appear little used or recognized in security, and a pattern of methodological errors continues unaddressed.

Traffic exchange services enable members to bring traffic to their websites from a diverse pool of IP addresses, in return for visiting sites of other members. We examine the world of traffic exchanges to characterize their makeup, usage, and monetization. We find that the ecosystem includes a range of services, from manual exchanges where participants must solve CAPTCHAs between successive page views, to exchanges that provide tools that automatically surf without requiring any user action. By "milking" a sample of these exchanges, we analyze month-long datasets to examine the nature of URLs that members submit to them. We find a wide prevalence of URLs for services that pay users in return for views to their content, and at least 30% of the requested impressions are for pages that clearly participate in a class of impression fraud called referrer spoofing. We also analyze the size and composition of a sample of these exchange networks by making purchases, finding that the exchanges delivered visits from roughly 200K unique IP~addresses, and that in some exchange networks, the majority of visits came from cloud hosting services.

Counterfactuals (or what-if scenarios) are often employed as security arguments, but the dos and don'ts of their use are poorly understood. They are useful to discuss vulnerability of systems under threats that haven't yet materialized, but they can also be used to justify investment in obscure controls. In this paper, we shed light on the role of counterfactuals in security, and present conditions under which counterfactuals are legitimate arguments, linked to the exclusion or inclusion of the threat environment in security metrics. We provide a new paradigm for security reasoning by deriving essential questions to ask in order to decide on the acceptability of specific counterfactuals as security arguments, which can serve as a basis for further study in this field. We conclude that counterfactuals are a necessary evil in security, which should be carefully controlled.

Password meters tell users whether their passwords are "weak" or "strong." We performed a laboratory experiment to examine whether these meters influenced users' password selections when they were forced to change their real passwords, and when they were not told that their passwords were the subject of a study. We observed that the presence of meters yielded significantly stronger passwords. We performed a followup field experiment to test a different scenario: creating a password for an unimportant account. In this scenario, we found that the meters made no observable difference: participants simply reused weak passwords that they used to protect similar low-risk accounts. We conclude that meters result in stronger passwords when users are forced to change existing passwords on "important" accounts and that individual meter design decisions likely have a marginal impact.

Drive-by download attacks attempt to compromise a victim's computer through browser vulnerabilities. Often they are launched from Malware Distribution Networks (MDNs) consisting of landing pages to attract traffic, intermediate redirection servers, and exploit servers which attempt the compromise. In this paper, we present a novel approach to discovering the landing pages that lead to drive-by downloads. Starting from partial knowledge of a given collection of MDNs we identify the malicious content on their landing pages using multiclass feature selection. We then query the webpage cache of a commercial search engine to identify landing pages containing the same or similar content. In this way we are able to identify previously unknown landing pages belonging to already identified MDNs, which allows us to expand our understanding of the MDN. We explore using both a rule-based and classifier approach to identifying potentially malicious landing pages. We build both systems and independently verify using a high-interaction honeypot that the newly identified landing pages indeed attempt drive-by downloads. For the rule-based system 57% of the landing pages predicted as malicious are confirmed, and this success rate remains constant in two large trials spaced five months apart. This extends the known footprint of the MDNs studied by 17%. The classifier-based system is less successful, and we explore possible reasons.

A New Security Paradigms Workshop (2013) panel discussed the topic of ethical issues and implications related to markets for zero-day exploits, i.e., markets facilitating the sale of previously unknown details on how to exploit software vulnerabilities in target applications or systems. The related topic of vulnerability rewards programs ("bug bounties" offered by software vendors) was also discussed. This note provides selected background material submitted prior to the panel presentation, and summarizes discussion resulting from the input of both the panelists and NSPW participants.

We evaluate two decades of proposals to replace text passwords for general-purpose user authentication on the web using a broad set of twenty-five usability, deployability and security benefits that an ideal scheme might provide. The scope of proposals we survey is also extensive, including password management software, federated login protocols, graphical password schemes, cognitive authentication schemes, one-time passwords, hardware tokens, phone-aided schemes and biometrics. Our comprehensive approach leads to key insights about the difficulty of replacing passwords. Not only does no known scheme come close to providing all desired benefits: none even retains the full set of benefits that legacy passwords already provide. In particular, there is a wide range from schemes offering minor security benefits beyond legacy passwords, to those offering significant security benefits in return for being more costly to deploy or more difficult to use. We conclude that many academic proposals have failed to gain traction because researchers rarely consider a sufficiently wide range of real-world constraints. Beyond our analysis of current schemes, our framework provides an evaluation methodology and benchmark for future web authentication proposals.

We examine the password policies of 75 different websites. Our goal is understand the enormous diversity of requirements: some will accept simple six-character passwords, while others impose rules of great complexity on their users. We compare different features of the sites to find which characteristics are correlated with stronger policies. Our results are surprising: greater security demands do not appear to be a factor. The size of the site, the number of users, the value of the assets protected and the frequency of attacks show no correlation with strength. In fact we find the reverse: some of the largest, most attacked sites with greatest assets allow relatively weak passwords. Instead, we find that those sites that accept advertising, purchase sponsored links and where the user has a choice show strong inverse correlation with strength.

It is often suggested that users are hopelessly lazy and unmotivated on security questions. They chose weak passwords, ignore security warnings, and are oblivious to certificates errors. We argue that users' rejection of the security advice they receive is entirely rational from an economic perspective. The advice offers to shield them from the direct costs of attacks, but burdens them with far greater indirect costs in the form of effort. Looking at various examples of security advice we find that the advice is complex and growing, but the benefit is largely speculative or moot. For example, much of the advice concerning passwords is outdated and does little to address actual treats, and fully 100% of certificate error warnings appear to be false positives. Further, if users spent even a minute a day reading URLs to avoid phishing, the cost (in terms of user time) would be two orders of magnitude greater than all phishing losses. Thus we find that most security advice simply offers a poor cost-benefit tradeoff to users and is rejected. Security advice is a daily burden, applied to the whole population, while an upper bound on the benefit is the harm suffered by the fraction that become victims annually. When that fraction is small, designing security advice that is beneficial is very hard. For example, it makes little sense to burden all users with a daily task to spare 0.01% of them a modest annual pain.

Conventional wisdom is that phishing represents easy money. In this paper we examine the economics that underly the phenomenon, and find a very different picture. Phishing is a classic example of tragedy of the commons, where there is open access to a resource that has limited ability to regenerate. Since each phisher independently seeks to maximize his return, the resource is over-grazed and yields far less than it is capable of. The situation stabilizes only when the average phisher is making only as much as he gives up in opportunity cost.

We report the results of a large scale study of password use andpassword re-use habits. The study involved half a million users over athree month period. A client component on users' machines recorded a variety of password strength, usage and frequency metrics. This allows us to measure or estimate such quantities as the average number of passwords and average number of accounts each user has, how many passwords she types per day, how often passwords are shared among sites, and how often they are forgotten. We get extremely detailed data on password strength, the types and lengths of passwords chosen, and how they vary by site. The data is the first large scale study of its kind, and yields numerous other insights into the role the passwords play in users' online experience.

In this paper we examine the problem of entering sensitive data, such as passwords, from an untrusted machine. By untrusted we mean that it is suspected to be infected with spyware which snoops on the user's activity. Using such a machine is obviously undesirable, and yet roaming users often have no choice. They are in no position to judge the security status of Internet cafe, airport lounge or business center machines. Either malice or negligence on the part of an administrator means that any such machine can easily be running a keylogger. The roaming user has no reliable way of determining whether it is safe, and has no alternative to typing the password. We consider whether it is possible to enter data to confound spyware assumed to be running on the machine in question. The difficulty of mounting a collusion attack on a single user's password makes the problem more tractable than it might appear. We explore several approaches. In the first, we show how the user can embed a password in random keystrokes to confuse spyware, while leaving the actual login unaffected. In the second we employ a proxy server to strip random keys. In the third we again employ a proxy that inverts a key mapping performed by the user. We examine also several potential attacks

Abstract — In recent years, BitTorrent has emerged as a very scalable peer-to-peer file distribution mechanism. While early measurement and analytical studies have verified BitTorrent’s performance, they have also raised questions about various metrics (upload utilization, fairness, etc.), particularly in settings other than those measured. In this paper, we present a simulationbased study of BitTorrent. Our goal is to deconstruct the system and evaluate the impact of its core mechanisms, both individually and in combination, on overall system performance under a variety of workloads. Our evaluation focuses on several important metrics, including peer link utilization, file download time, and fairness amongst peers in terms of volume of content served. Our results confirm that BitTorrent performs near-optimally in terms of uplink bandwidth utilization, and download time except under certain extreme conditions. We also show that low bandwidth peers can download more than they upload to the network when high bandwidth peers are present. We find that the rate-based tit-for-tat policy is not effective in preventing unfairness. We show how simple changes to the tracker and a stricter, block-based tit-for-tat policy, greatly improves fairness. I.

Many media streams consist of distinct objects that repeat. For example, broadcast television and radio signals contain advertisements, call sign jingles, songs, and even whole programs that repeat. The problem we address is to explicitly identify the underlying structure in repetitive streams and de-construct them into their component objects. Our algorithm exploits dimension reduction techniques on the audio portion of a multimedia stream to make search and buffering feasible. Our architecture assumes no a priori knowledge of the streams, and does not require that the repeating objects (ROs) be known. Everything the system needs, including the position and duration of the ROs, is learned on the fly. We demonstrate that it is perfectly feasible to identify in realtime ROs that occur days or even weeks apart in audio or video streams. Both the compute and buffering requirements are comfortably within reach for a basic desktop computer. We outline the algorithms, enumerate several applications and present results from real broadcast streams.

We examine the problem of combining several images to remove occlusions that occur in one or more of a sequence of images. A sequence of digital camera images of a photo-worthy landmark may be occluded by passers-by walking between the photographer and the scene. As they move they occludes different regions in each image of the sequence. It is obvious that if two or more images coincide at each location an unoccluded image can be formed. We show that this is not necessary: in fact so long as at least one image is unoccluded at each location an unoccluded image can be formed automatically. This greatly eases the conditions under which an unoccluded image can be formed. We detail the algorithm and show results of occlusion removal.

This paper introduces a novel and very accurate segmentation algorithm. It is very efficient and consumes less than 10% of CPU on a simple desktop PC to segment a stream in real-time. It operates on an audio stream, or on the audio portion of a audio-visual stream. It is very accurate: it accurately detects the positions and durations of objects on an over-the-air broadcast television signal, and songs on both FM and internet radio stations (as checked against labeled ground truth streams). The algorithm does not require any prior information or training. We detail the system design and present results of segmenting broadcast streams.

In this paper, we present a simulation-based study of BitTorrent. Our results confirm that BitTorrent performs near-optimally in terms of uplink bandwidth utilization and download time, except under certain extreme conditions. On fairness, however, our work shows that low bandwidth peers systematically download more than they upload to the network when high bandwidth peers are present. We find that the rate-based tit-for-tat policy is not effective in preventing unfairness. We show how simple changes to the tracker and a stricter, block-based tit-for-tat policy, greatly improves fairness, while maintaining high utilization.

Many media streams consist of distinct objects that repeat. For example, broadcast television and radio signals contain advertisements, call sign jingles, songs and even whole programs that repeat. The problem we address is to identify explicitly the underlying structure in repetitive streams and deconstruct them into their component objects. Our architecture assumes no a priori knowledge of the streams, and does not require a pre-trained database. Everything the system needs is learned on the fly. We demonstrate that using a modestly capable computer it is perfectly feasible to identify, in realtime, repeating objects that occur days or even weeks apart in audio or video streams. We outline the algorithms, enumerate several applications and present results from real streams.

Objects identification in images is generally hard unless the objects are simple geometric shapes such as circles, rectangles, have very particular properties. Even simple geometric shapes can be hard to identify if they deviate even a little from the ideal. We examine the question of identifying and segmenting noisy rectangles, where edges may be ragged, corners may be missing and so on. We test the robustness of our scheme on receipts and small documents obtained from real scans.

Counterfeiting of valuable documents is an increasingly serious problem. Banknotes, drivers licenses, passports, diplomas and stock certificates are all the subjects of increasingly frequent and accurate counterfeiting efforts. This is in part due to the performance improvements of consumer inkjet printers. Design features which required great labor and skill to reproduce on an engraved-plate printing process pose essentially no difficulty to a counterfeiter armed with an accurate scanner and high-resolution color printer. We show how simple changes in banknote design coupled with possible changes in rendering engines can make the task of counterfeiting enormously more difficult.

In scanning photographs, receipts or other small objects users will often scan many at a time. It would be convenient to automatically detect that the scanned image consists of many small objects rather than a single large one, and segment appropriately. We present a simple, efficient and robust way of doing this.

This paper covers a method for capturing documents using a digital camera. A typical cheap VGA digital camera (resolution 640 by 480 pixels) does not have adequate resolution to capture text over a page. By displacing the sensor spatially and taking multiple acquisitions we seek to enhance the resolution. There are many approaches in the literature to multi-frame reconstruction. Our approach differs from most previous work in that we make an additional restriction that we wish to enhance the resolution of documents which consist primarily of regions that are spatially piecewise constant (e.g. monochrome text on a monochrome background). We show that this enables us to achieve resolution enhancement that is superior to previously reported schemes. A simulation involving 16 frames of a VGA camera gives excellent rendition of an A4 or legal sized page with 9 pt text.

The paper covers a method of allowing a client to browse an image to examine it in detail, while making it difficult to steal. It differs from invisible watermarking methods in that it attempts to prevent theft, rather than detect or verify theft after it has happened. The image is served to the client in parts. The parts are imperceptibly altered. No effort is made to protect individual parts; however, the alterations ensure that putting the parts together is extremely difficult without clearly visible distortion. Thus, the client can view any part of the image in detail, but is unable to obtain a usable copy of the whole.

We examine the question of reconstruction of signals from periodic nonuniform samples. This involves discarding samples from a uniformly sampled signal in some periodic fashion. We give a characterization of the signals that can be reconstructed at exactly the minimum rate once a nonuniform sampling pattern has been fixed. We give an implicit characterization of the reconstruction system, and a design method by which the ideal reconstruction filters may be approximated. We demonstrate that for certain spectral supports the minimum rate can be approached or achieved using reconstruction schemes of much lower complexity than those arrived at by using spectral slicing, as in earlier work. Previous work on multiband signals have typically been those for which restrictive assumptions on the sizes and positions of the bands have been made, or where the minimum rate was approached asymptotically. We show that the class of multiband signals which can be reconstructed exactly is shown to be far larger than previously considered. When approaching the minimum rate, this freedom allows us, in certain cases to have a far less complex reconstruction system.

Digital cameras generally produce color images by placing color filters on monochrome sensors. The sensor produces one color at each location, and the other two color values for that location are interpolated. A lossy compression stage, using a coder such as JPEG, often follows. For a fixed interpolation algorithm, the color interpolation stage enforces a spatial dependence among pixels. We show how we may exploit this dependence to reduce the compression noise. This is achieved using the algorithm of projection on convex sets. For a fixed compression scheme we can also attempt to find the interpolation method that minimises the compression noise in the original data, and we show an approach to solving this problem.

A color correction matrix is usually used to transform the raw color image obtained from color image sensors to adjust for factors such as variations in illumination and deviations of the actual filter characteristics from the ideal. Color correction matrices that have high condition numbers can greatly amplify noise, while it can be difficult to achieve good color saturation with low condition number matrices. Noise can be a significant problem for digital camera images which have limited bit-depth. We explore the trade-off between noise reduction and color saturation analytically, and using digital camera images. We present an orthonormality criterion to define optimality with respect to noise sensitivity and color saturation in the case of signal-independent, orthogonal sensor measurement noise in each color channel.

We examine the problem of reconstructing a signal from periodic non-uniform samples, i.e. a uniform train from which samples are deleted in some periodic fashion. We develop a condition previously derived by Herley and Wong (see Proc. IEEE Int. Conf. Image Proc., 1996) and examine its implications. We show that this method has a number of advantages over alternative approaches. In particular it gives a condition for achieving the minimum rate rather than approaching it asymptotically. We show that it generally leads to a reconstruction scheme that is simpler than those derived by other strategies. We examine a few special cases in which the minimum rate is precisely achieveable, and cases where design of the reconstruction system is possible without explicitly knowing the signal spectrum.

We describe a method for scaling images which have been acquired with a charge coupled device (CCD) sensor. This method produces enlarged images which are sharper than those produced by bilinear interpolation, for comparable complexity. It is based on the observation that the sampling process of a CCD is not a point sampling process, but instead can be modelled as an averaging filter followed by sampling.

We examine the question of how to choose a space varying filterbank tree representation that minimizes some additive cost function for an image. The idea is that for a particular cost function, e.g., energy compaction or quantization distortion, some tree structures perform better than others. While the wavelet tree represents a good choice for many signals, it is generally outperformed by the best tree from the library of wavelet packet frequency-selective trees. The double-tree library of bases performs better still, by allowing different wavelet packet trees over all binary spatial segments of the image. We build on this foundation and present efficient new pruning algorithms for both one- and two-dimensional (1-D and 2-D) trees that will find the best basis from a library that is many times larger than the library of the single-tree or double-tree algorithms. The augmentation of the library of bases overcomes the constrained nature of the spatial variation in the double-tree bases, and is a significant enhancement in practice. Use of these algorithms to select the least-cost expansion for images with a rate-distortion cost function gives a very effective signal adaptive compression scheme. This scheme is universal in the sense that, without assuming a model for the signal or making use of training data, it performs very well over a large class of signal types. In experiments it achieves compression rates that are competitive with the best training-based schemes.

An N-level scalar quantization system for continuous alphabet i.i.d. sources with a pre- and post-filter as suggested by Popat and Zeger (see IEEE Trans. Commun., vol.40, no.11, p.1670, 1992) is considered. The idea is that the pre-filter changes the distribution of the source to approximately Gaussian, which is then quantized by a Lloyd-Max (1960, 1982) quantizer for Gaussian random variables. For many sources, the overall system outperforms one that directly quantizes the sources. We propose an iterative algorithm for designing the optimum filters, to minimize the overall mean squared error between the input and output of the quantization system. It is found experimentally that the design algorithm always converges very rapidly to a solution where the optimum pre- and post-filters are all pass filters. We prove the convergence of the design algorithm for the N=2 case, and conjecture that convergence to the same solution always holds for any N.

We examine the problem of reconstructing a signal from periodic non-uniform samples, i.e. a uniform train from which samples are deleted in some periodic fashion. We develop the necessary and sufficient conditions for reconstruction, both for one and multiple dimensions. We prove that one-dimensional multiband signals which have arbitrary frequency support can be sampled without loss arbitrarily close to the theoretically minimum rate. An important advantage of our approach is the existence of an efficient design procedure for the reconstruction system. We show that the algorithm of projection on convex sets can be used to design the reconstruction filters efficiently. Once the filters are designed, the reconstruction algorithm is non-iterative. We give illustrative examples.

An Occam filter employs lossy data compression to separate signal from noise. Previously it was shown that Occam filters are useful for filtering random noise from discrete samples of a deterministic and continuous signal. In this paper, we show that Occam filters can also be used to separate two stochastic sources, with the effectiveness of the separation depending on their relative compressibility. We then construct an Occam filter based on singular value decomposition (SVD) and apply it to digital images corrupted with Gaussian noise. We observe that the SVD-based Occam filter outperforms the wavelet-based denoising method of Donoho and Johnstone (1994) and DeVore and Lucier (1992).

The emergence of wavelets has led to a convergence of linear expansion methods used in signal processing and applied mathematics. In particular, subband coding methods and their associated filters are closely related to wavelet constructions. We first review such constructions with a signal processing perspective. We then discuss the idea behind signal adapted bases and associated algorithms before showing how wavelets and subband coding methods are used in signal compression applications.

We examine the problem of reconstructing a discrete-time signal given only n of its M-phase components. Borrowing analysis from the field of perfect reconstruction filter banks enables us to derive necessary and sufficient conditions under which reconstruction is possible. Essentially, in a perfect reconstruction system, the conditions required to reconstruct from partial information are equivalent to the conditions needed to ensure that the rest of the information does not contribute to the reconstructed signal. This allows us to reconstruct multiband signals which have an overall bandwidth of no more than B, yet cannot be reconstructed from uniformly spaced samples at the minimum rate of B/2/spl pi/.

We examine the question of how to choose a time-varying filter bank representation for a signal which is optimal with respect to an additive cost function. We present in detail an efficient algorithm for the Haar filter set which finds the optimal basis, given the constraint that the time and frequency segmentations are binary. Extension to multiple dimensions is simple, and the use of arbitrary filter sets is also possible. We verify that the algorithm indeed produces a lower cost representation than any of the wavelet packet representations for compression of images using a simple rate-distortion cost.

We introduce a new image coding algorithm which exploits the idea of space-varying wavelet packets, where the best filter bank representation is chosen from a large library. The filter bank tree representations in the library are free to vary in structure over different segments of the image, and a fast search algorithm is given. In addition we employ the idea of space-frequency quantization, which is a rate-distortion optimized extension of the zero-tree wavelet coder of Shapiro to wavelet packets. The coder thus adaptively chooses the representation to suit the image and adaptively chooses the quantization to suit the representation. We present coding results that confirm the excellent performance of the scheme.

In this paper we explore how to implement realizable orthogonal projection operators for real signals. Using some of the ideas developed in the area of multirate filter banks we find it possible to implement orthogonal projections onto spaces that are approximately bandlimited, using very efficient operators. These represent a considerable improvement over linear shift-invariant approximations, which are neither bandlimited nor exact projections. A main application is for use with the algorithm of projection on convex sets, which is used, for example in image deblurring, bandlimited extrapolation and in reconstruction in oversampled A/D conversion.>

In this paper we examine the circumstances under which a discrete-time signal can be exactly interpolated given only every M-th sample. After pointing out the connection between designing an M-fold interpolator and the construction of an M-channel perfect reconstruction filter bank, we derive necessary and sufficient conditions on the signal under which exact interpolation is possible. Bandlimited signals are one obvious example, but numerous others exist. We examine these and show how the interpolators may be constructed. A main application is to iterative interpolation schemes, used for the efficient generation of smooth curves. Conventional bandlimited interpolators are not suitable in this context. We illustrate that a better criterion is to use interpolators that are exact for polynomial functions. We show how these may be designed for any polynomial degree N and any interpolation factor M.>

We examine the question of how to construct time-varying filter banks in the most general M-channel non-orthogonal case. We show that by associating with both analysis and synthesis operators a set of boundary filters, it is possible to make the analysis structure vary arbitrarily in time, and yet reconstruct the input with a similarly time-varying synthesis section. There is no redundancy or distortion introduced. This gives a solution to the problem of applying filter banks to finite length signals; it suffices to apply the boundary filters at the beginning and end of the signal segment. This also allows the construction of orthogonal and non-orthogonal bases with essentially any prescribed time and frequency localization, but which, nonetheless, are based on structures with efficient filter bank implementations.>

The relation between orthogonal finite impulse response filter banks and orthonormal bases of compactly supported wavelets has been established by Daubechies (1988). Building on this result, the authors use infinite impulse response (IIR) filter banks to construct more general orthonormal wavelet bases, which have infinite support, but rapid decay. They give a complete constructive method which gives all rational orthogonal two-channel filters banks. A family of wavelets is developed which have similar smoothness and moment properties to those of Daubechies. Wavelet bases are derived for the space of piecewise polynomial functions, which are alternatives to the Battle-Lemarie bases (Battle, 1987; Lemarie, 1988) and have the desirable property of being realizable. Relevant design exchanges are presented.>

The authors present new theoretical results on FIR (finite impulse response) filter banks based on Diophantine equations and continued fraction expansions and use them to show how general wavelets may be designed. They further show that by considering a noncausal IIR (infinite impulse response) structure it is possible to have a linear phase paraunitary solution. A number of design examples illustrating the advantages of the new results are presented.>

The discrete version of the wavelet transform, which has recently emerged as a powerful tool for nonstationary signal analysis is closely related to filter banks, which have been studied in digital signal processing. Also, multiresolution signal analysis has been used in image processing. The relationship between these techniques is indicated. It is shown how to construct biorthogonal systems with linear-phase finite impulse response (FIR) filters and with regular analysis and synthesis. Some examples of practical interest are given. The complexity of the discrete wavelet transform is also discussed.>