As content providers adopt peer-to-peer approaches for content sharing and distribution, they face new challenges in guaranteeing privacy to their clients. Participating peers can glean information from their communication with other peers, such as their identities or the shared data and use this information for malicious purposes. We present Nemor, a protocol that allows a requesting peer and a corresponding serving peer to communicate anonymously with each other and from other participating peers, while protecting the identity of the content being exchanged. Nemor relies on a trusted intermediary, such as a provider-managed tracker, to identify a potential serving peer. A peer in Nemor joins one or more trees. Using a combination of a random walk, a probabilistic jump from one tree to another and constrained flooding, the requesting and serving peer dynamically construct an overlay path between them. A key differentiator of Nemor is the integrated design of a congestion avoidance mechanism that yields significant performance benefits without compromising on anonymity. Using experimental results from PlanetLab and simulations with traces from an operational VoD system, we demonstrate that Nemor outperforms state of the art approaches like TOR and OneSwarm. Our results confirm that Nemor, while being resilient to attacks on anonymity, achieves high performance and scalability and is suitable for a range of applications, including distribution of large volume content, such as streaming video.

Network protocol fingerprinting refers to the process of identifying a protocol implementation by their input and output behaviors. It has been regarded as both a potential threat to network security and also as a useful mechanism for network management. Existing protocol fingerprinting tools share common disadvantages such as being protocol-specific and difficult to automate. This paper proposes a formal methodology for fingerprinting experiments using which we can model a broad spectrum of fingerprinting problems and design-efficient algorithms. We present a formal behavioral model that specifies a protocol principal by its states and transitions, then identify a complete taxonomy of fingerprint matching and discovery problems is identified based on 1) whether the fingerprinting experiment is active or passive and 2) the information available about the specifications and implementations. Algorithms to solve the problems are discussed. In particular, for fingerprint matching algorithm, we propose an efficient PEFSM online separation algorithm for active experiment and concurrent passive testing for passive experiments. For fingerprint discovery problem, there are two cases: if the protocol specification is available as a nondeterministic PEFSM, we apply across verification and back-tracing technique for active and passive discovery, respectively; if no specification is available, we take the machine learning approach and discover the fingerprint by active testing.

A lot of efforts have been devoted to the analysis of network protocol specification for reliability and security properties using formal techniques. However, faults can also be introduced during system implementation; it is indispensable to detect protocol implementation flaws, yet due to the black-box nature of protocol implementation and the unavailability of protocol specification most of the approaches resort to random or manual testing. In this paper we propose a model-based approach for security flaw detection of protocol implementation with a high fault coverage, measurability, and automation. Our approach first synthesizes an abstract behavioral model from a protocol implementation and then uses it to guide the testing process for detecting security and reliability flaws. For protocol specification synthesis we reduce the problem a trace minimization with a finite state machine model and an efficient algorithm is presented for state space reduction. Our method is implemented and applied to real network protocols. Guided by the synthesized model our testing tool reveals a number of unknown reliability and security issues by automatically crashing the implementations of the Microsoft MSN instant messaging (MSNIM) protocol. Analytical comparison between our model-based and prevalent syntax-based flaw detection schemes is also provided with the support of experimental results.

Security and reliability of network protocol implementations are essential for communication services. Most of the approaches for verifying security and reliability, such as formal validation and black-box testing, are limited to checking the specification or conformance of implementation. However, in practice, a protocol implementation may contain engineering details, which are not included in the system specification but may result in security flaws. We propose a new learning-based approach to systematically and automatically test protocol implementation security properties. Protocols are specified using symbolic parameterized extended finite state machine (SP-EFSM) model, and an important security property - message confidentiality under the general Dolev-Yao attacker model - is investigated. The new testing approach applies black-box checking theory and a supervised learning algorithm to explore the structure of an implementation under test while simulating the teacher with a conformance test generation scheme. We present the testing procedure, analyze its complexity, and report experimental results.

Due to the real time nature and buddy list presence information of instant messaging (IM) systems worms can spread over IM networks rapidly, causing severe damages, however, it is a challenge to detect and control their propagation; it has become an urgent task to develop and deploy efficient procedures to proactively defend against worms before they plague IM networks. Based on modeling and analysis of worm propagation and traffic pattern, we present efficient methods for real time worm detection and control, including content insensitive tracing, signature-based detection, and relay restriction. Experiments on real IM network topologies, such as AIM, have shown promising results of our approaches.

Abstract — Network protocol system fingerprinting has been recognized as an important issue and a major threat to network security. Prevalent works rely largely on human experiences and insight of the protocol system specifications and implementations. Such ad-hoc approaches are inadequate in dealing with large complex protocol systems. In this paper we propose a formal approach for automated protocol system fingerprinting analysis and experiment. Parameterized Extended Finite State Machine is used to model protocol systems, and four categories of fingerprinting problems are formally defined. We propose and analyze algorithms for both active and passive fingerprinting and present our experimental results on Internet protocols. Furthermore, we investigate protection techniques against malicious fingerprinting and discuss the feasibility of two defense schemes, based on the protocol and application scenarios.

Emergency alerting capability is crucial for the prompt response to natural disasters and terrorist attacks. The emerging network infrastructure and secure broadcast techniques enable prompt and secure delivery of emergency notification messages. With the ubiquitous deployment of alert systems, scalability and heterogeneity pose new challenges for the design of secure broadcast schemes. In this paper, we discuss the key generation problem with the goal of minimizing the total number of keys which need to be generated by the alert center and distributed to the users. Two encryption schemes, zero message scheme and extended header scheme, are modeled formally. For both schemes we show the equivalence of the general optimal key generation (OKG) problem and the bipartite clique cover (BCC) problem, and show that OKG problem is NP-hard. The result is then generalized to the case with resource constraints, and we provide a heuristic algorithm for solving the restricted BCC (and OKG) problem.

For network fault management, we present a new technique that is based on on-line monitoring of networks with link state routing protocols, such as OSPF (open shortest path first) and integrated IS-IS. Our approach employs an agent that monitors the on-line information of the network link state database, analyzes the events generated by network faults for event correlation, and detects and localizes the faults. We apply our method to a real network topology with various types of network faults. Experimental results show that our approach can detect and localize the faults in a timely manner, yet without disrupting normal network operations.

This work has been motivated by the need to test interoperability of systems carrying voice calls over the IP network. The voice over IP (VoIP) systems must be integrated and interoperate with the existing public switched telephone network (PSTN) before they are widely adopted. Standards have been developed to address this problem, but unfortunately different standards bodies and commercial consortiums have defined different standards. Furthermore, the prevailing VoIP standard such as H.323 is incomplete, complex, and presents the implementers with "vendors latitudes". As a result, there is no guarantee that the integrated VoIP systems would interoperate properly even if the implementations are all H.323-compliant. Thus interoperability testing has become indispensable. We want to test all the system interoperations by exercising all the required patterns of "interoperating behaviors". On the other hand, test execution in real environment is expensive, and we want to minimize the number of tests while maintaining the coverage. We present a general method for automatic generation of test cases, which cover all the required system interoperations and contain a minimal number of tests. We study data structures and efficient test generation algorithms, which take time proportional to the total test case size. Finally, we report experimental results on VoIP systems.

Finite-state machines are widely used to model systems in diverse areas. Often, the modeling machines can be decomposed into smaller component machines and this decomposition can facilitate the system design, implementation and analysis. J. Hartmanis and R.E. Stearns (1966) developed an elegant algebraic theory for machine decomposition that is based on the closed-partition lattice of a machine. In this paper, we study the computation of the closed-partition lattice of finite-state machines for the application to their decomposition. We present efficient algorithms for constructing the closed-partition lattice and for machine decomposition.

With N routers in a network running the open shortest path first (OSPF) routing protocol a network topology update can generate on the order of N/sup 2/ LSA packets. This phenomenon, known as the LSA N-squared problem, severely degrades network performance and scalability. Hierarchical OSPF network architectures have been proposed to reduce the number of link state advertisements (LSA) that are generated by a network topology update. We show that equal-size areas minimize the number of LSAs. Then we derive the optimal number of areas and the size of areas to create the network producing the minimal number of LSAs. Finally we show that the optimal network architecture reduces the number of LSAs from O(N/sup 2/) to O(/sup 3//spl radic/(N/spl middot/N)).

Voice over IP (VoIP) systems have to be integrated and interoperate with the existing telephone network before they become widely adopted. However, different standards have been proposed and the prevailing standard (H.323) is incomplete, complex, and provides the implementers with "vendors latitudes". As a result, there is no guarantee that even H.323-compliant systems would interoperate properly. Interoperability testing has become indispensable. We present techniques for automatic generation of a minimal set of test cases, covering all the required system interoperations. Our algorithms have been implemented and incorporated in a software tool-ITIS. We report experimental results on VoIP systems interoperability testing, using ITIS.

SOCRATES is a software system for testing correctness of implementations of IP routing protocols such as RIP, OSPF and BGP. It uses a probabilistic algorithm to automatically construct random network topologies. For each generated network topology, it checks the correctness of routing table calculation and the IP packet forwarding behavior. For OSPF, it also checks the consistency between network topologies and the link-state databases of router under test. For BGP, it further checks the BGP update redistribution. Being different than commercial testing tools, which select their test cases in an ad-hoc manner, SOCRATES chooses test cases with a guaranteed fault coverage.

In this paper an automatic and optimized technique for test generation for communication protocol control and data portion is described, the goal is to minimize the number of tests with a guaranteed coverage. The test generation algorithm is applied to the client layer part of the TCP/IP protocol. The protocol used for the experiment is TCP-Reno, which is specified in the SDL language and is one of the commonly referenced implementations. For such a sophisticated protocol, the algorithm efficiently constructs 22 tests that cover all the required portions of the protocol.

An important aspect of network management is fault management-determining, locating, isolating and correcting faults in the network. The paper deals with the algorithms for detecting faults, i.e., behavior of the network different from specifications. It is important for communication networks to detect faults "in-process" i.e., while the network is in its normal operation. Thus, we detect faults by examining the input-output behavior without forcing the system to specialized inputs explicitly for testing. Such testing is commonly called passive testing. We model the network as a finite state machine and develop procedures for passive testing including the required data structure, efficient implementations and the complexity of our procedures. We start with fully observable and deterministic machines and then study more realistic models: partially observable and nondeterministic machines. We also discuss extensions to communicating finite state machines and machines extended with parameters and variables. We apply our techniques to management of a signaling network operating under the Signaling System 7 (SS7) and report experimental results, which show the feasibility of applying passive testing to practical systems.

We study both the correctness and performance of the source/destination protocol of the available bit rate (ABR) service in asynchronous transfer mode (ATM) networks. Although the basic source/destination protocol for congestion management is relatively simple, the protocol specification has to cope with several "real-world" cases such as failures and delayed/lost feedback which may introduce complexity. Rigorous proofs of the correct functioning of the protocol based on a formal specification is necessary. We use a formal extended finite state machine (EFSM) model to show that the ABR source/destination protocol is free of live-locks, so that under all conditions both resource management (RM) and data cells will be transmitted. We also show that the network options of explicit forward congestion indication (EFCI) and explicit rate (ER) interoperate correctly. We use the understanding of the informal English description of the source/destination behavior and of our EFSM model to derive conditions that ensure that the source transmission rate is stable in the presence of delayed or lost feedback RM cells, especially under the operation of a source rule that requires the reduction of the source rate under these conditions. We arrive at bounds on the number of consecutive RM cell losses tolerated while the rate remains stable. We also provide a worst-case analysis of the delay in turning around RM cells at the destination station and the worst-case inter-departure time of forward RM cells from the source.

Formal specifications are indispensible for computer-aided verification and testing of communication protocols. However, a large number of the practical protocols, including ATM, have only informal specifications mostly in English. There an no general procedures to derive formal specifications from such informal specifications. As a case study, we consider an important protocol specification-ATM's available bit rate (ABR) service specification. The ABR source/destination policies have been specified using an English description in the main body of the ATM Forum's draft traffic management specification from which it is hard to conduct a formal analysis. Furthermore, while considerable energy has been spent in providing a reasonably precise specification, while allowing for appropriate implementation latitude, an English description still has the potential for different interpretations. We model the protocol by parametrized communicating extended finite state machines with timers, which is often called a transitions system, and present a formal specification by transitions of the system. We also provide insights gained in the derivation of the formal specification. Furthermore, we introduce a scheduler involved in transmitting queued cells at the allowed cell rate to meet the minimal requirements from the source and destination protocols. We present the transitions for the source/destination/scheduler machines, primarily for transmitting cells in-rate.

In feature testing of communication protocols, we want to construct a minimal number of tests with a desirable fault coverage. We model the protocols by extended finite state machines and reduce the test generation process to optimization problems on graphs. We study efficient algorithms and their complexity. We report experimental results on real systems, including Personal HandyPhone System, a 5ESS based ISDN wireless system, and 5ESS Intelligent Network Application Protocol.

With advanced computer technology, systems are getting larger to fulfill more complicated tasks: however, they are also becoming less reliable. Consequently, testing is an indispensable part of system design and implementation; yet it has proved to be a formidable task for complex systems. This motivates the study of testing finite stare machines to ensure the correct functioning of systems and to discover aspects of their behavior. A finite state machine contains a finite number of states and produces outputs on state transitions after receiving inputs. Finite state machines are widely used to model systems in diverse areas, including sequential circuits, certain types of programs, and, more recently, communication protocols. In a testing problem we have a machine about which we lack some information; we would like to deduce this information by providing a sequence of inputs to the machine and observing the outputs produced. Because of its practical importance and theoretical interest, the problem of testing finite state machines has been studied in different areas and at various times. The earliest published literature on this topic dates back to the 1950's. Activities in the 1960's mid early 1970's were motivated mainly by automata theory and sequential circuit testing. The area seemed to have mostly died down until a few years ago when the testing problem was resurrected and is now being studied anew due to its applications to conformance testing of communication protocols. While some old problems which had been open for decades were resolved recently, new concepts and more intriguing problems from new applications emerge. We review the fundamental problems in testing finite state machines and techniques for solving these problems, tracing progress in the area from its inception to the present and the stare of the art. In addition, we discuss extensions of finite state machines and some other topics related to testing.

We present a new approach for conformance testing of protocols specified as a collection of communicating finite state machines (FSMs). Our approach uses a guided random walk procedure. This procedure attempts to cover all transitions in the component FSMs. We also introduce the concept of observers that check some aspect of protocol behavior. We present the result of applying our method to two example protocols: full-duplex alternating bit protocol and the ATM-adaptation-layer-convergence protocol. Applying our procedure to the ATM adaptation layer, 99% of component FSMs edges can be covered in a test with 11692 input steps. Previous approaches cannot do conformance test generation for standard protocols (such as asynchronous transfer mode (ATM) adaptation layer) specified as a collection of communicating FSMs.

A communication system uses a precise set of rules called a protocol, to define interactions among its entities. With advancing computer transmission and switching technology, communication systems are providing sophisticated services demanded by users over a wide area. Protocol standards include a very, large number of options to take care of different service possibilities and to please all the people involved in the Standards Committees. Consequently, protocols have become large and complex, and, therefore their design and analysis have become a formidable task. To cope with this problem, a variety of approaches to simplify the protocols have been proposed in the published literature, such as protocol projection, homomorphism, selective resolution, and many others. We have recently developed a new technique called protocol pruning. It reduces the complexity of the protocols by pruning them to keep only that part which is required for a specified subset of services. More importantly, it takes polynomial (rather than exponential) time and space in the size of the protocol specification. This makes the algorithm feasible for engineers to use for practical problems involving large and complex protocols. We describe the technique and discuss applications to synthesis of protocol converters/gateways, protocol conformance testing, and thinning for lightweight and high performance protocols. The technique could also be useful for protocol implementation, synthesis, validation, and verification.>

To provide reliable connection management, a transport protocol uses 3-way handshakes in which user incarnations are identified by bounded incarnation numbers from some modulo-N space, Cacheing schemes have been proposed to reduce the 3-way handshake to a 2-way handshake, providing the minimum latency desired for transaction-oriented applications. The authors define a class of cacheing protocols and determine the minimum N and optimal cache residency time as a function of real-time constraints (e.g., message lifetime, incarnation creation rate, inactivity duration, etc.). The protocols use the client-server architecture and handle failures and recoveries, Both clients and servers generate incarnation numbers from a local counter (e.g., clock). These protocols assume a maximum duration for each incarnation; without this assumption, there is a very small probability (/spl ap/1/N/sup 2/) of misinterpretation of incarnation numbers. This restriction can be overcome with some additional cacheing.>

We study the complexity of two fundamental problems in the testing of finite-state machines. 1) Distinguishing sequences (state identification). We show that it is PSPACE-complete to determine whether a finite-state machine has a preset distinguishing sequence. There are machines that have distinguishing sequences, but only of exponential length. We give a polynomial time algorithm that determines whether a finite-state machine has an adaptive distinguishing sequence. (The previous classical algorithms take exponential time.) Furthermore, if there is an adaptive distinguishing sequence, then we give an efficient algorithm that constructs such a sequence of length at most n(n/spl minus/1)/2 (which is the best possible), where n is the number of states. 2) Unique input output sequences (state verification). It is PSPACE-complete to determine whether a state of a machine has a unique input output sequence. There are machines whose states have unique input output sequences but only of exponential length.>

The authors study the problem of locating the differences between a protocol specification and its implementation. They give an exact procedure for solving this problem. If there is only one difference between the implementation and the specification, then the algorithm will locate the difference and therefore identify the implementation machine. Otherwise, it will detect that the implementation machine has more than one change. The run time of the algorithm is a low-degree polynomial in the number of states and inputs of the machine. Both a brute-force version of the algorithm with a cost O(pn/sup 5/), where n is the number of states of the specification machine and p is the number of inputs, and a fast algorithm with a cost O(pn/sup 3/ log n) are described. An improvement for which the cost on the average is O(pn/sup 2/ log n) is also given. A heuristic procedure that uses a test of comparable length to a conformance test sequence which has been used successfully in practice is described.>

To provide reliable connection management, a transport protocol uses 3-way handshakes in which user incarnations are identified by bounded incarnation numbers from some modulo-N space. Recently, several caching schemes have been proposed to reduce the 3-way handshake to a 2-way handshake. The authors define a class of caching protocols and determine the minimum value of N needed as a function of real-time constraints (e.g., message lifetime, incarnation creation rate, inactivity duration, cache residency times, etc.). The protocols use the client-server architecture and handle failures and recoveries. Both clients and servers generate incarnation numbers from a local counter (e.g., a clock). These protocols assume a maximum duration for each incarnation; without this assumption, there is a very small probability of misinterpretation of incarnation numbers. This restriction can be overcome with some additional caching.>

An approach for conformance testing of protocols specified as a collection of communicating finite state machines (FSMs) with two parts, pruning and a guided random walk procedure, is presented. First the protocol is pruned to various sets of machines; each set provides only one service. This significantly reduces the test sequence length. Then a guided random walk procedure that attempts to cover all transitions in the component FSMs is used. The results of applying the procedure to the full-duplex alternating bit protocol and the asynchronous transfer mode (ATM) adaptation layer convergence protocol are presented. For the ATM adaptation layer, 99% of component FSMs' edges can be covered in a test with 11692 input steps. Previous approaches cannot generate conformance tests for standard protocols (such as ATM adaptation layer) specified as a collection of communicating FSMs.>

General zero-crossing-based discontinuity detectors in two dimensions, which include Marr-Hildreth (1980), residual, difference of Gaussians, and other detectors as special cases, are discussed. Mathematical justification for this class of detectors is presented. An optimal detector that maximizes the signal-to-noise ratio is derived. Preliminary experimental results for real images are reported.

A systematic procedure that takes exponential time to synthesize protocol converters from formal specifications is presented. The algorithm proceeds in two steps: compute the largest common subset of services provided by the two mismatched protocols, and reduce the converter, retaining common services, without traversing the entire machine that represents the composition of the two mismatched protocols. In a number of cases, the converter can be constructed by a memoryless translation of messages from one protocol to another. Conditions under which such stateless conversion is possible are given. Two examples are presented to illustrate the techniques. In the first example, a converter that interconnects a half-duplex protocol with a full-duplex protocol from their formal specifications is computed. In the second example, the polynomial procedure is applied to computation of a converter for interconnecting the SNR and TCP protocols.>

We are given a transition system implicitly through a compact representation and wish to perform simultaneously reachability analysis and minimization without constructing first the whole system graph. We present an algorithm for this problem that applies to general systems, provided we have appropriate primitive operations for manipulating blocks of states and we can determine termination; the number of operations needed to construct the minimal reachable graph is quadratic in the size of this graph. We specialize the method to obtain efficient algorithms for extended finite state machines that apply separable affine transformations on the variables.

Detection and thresholding using a stochastic approach is discussed. A general form of detectors which includes a number of well-known detectors as special cases is discussed. Thresholding is indispensable to eliminate spurious responses from the detection process. The authors propose a weighted thresholding, which is designed to cope with a variety of anomalies. The analysis and experimental results on real images show that intelligent thresholding methods can make a significant difference for discontinuity detection.>

Article Testing finite state machines Share on Author: Mihalis Yannakakis AT&T Bell Labs., Murray Hill, NJ AT&T Bell Labs., Murray Hill, NJView Profile , Editor: David Lee AT&T Bell Labs., Murray Hill, NJ AT&T Bell Labs., Murray Hill, NJView Profile Authors Info & Claims STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of ComputingJanuary 1991 Pages 476–485https://doi.org/10.1145/103418.103468Online:03 January 1991Publication History 37citation1,310DownloadsMetricsTotal Citations37Total Downloads1,310Last 12 Months13Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

A method for generating test sequences for checking the conformance of a protocol implementation to its specification is described. A rural Chinese postman tour problem algorithm is used to determine a minimum-cost tour of the transition graph of a finite-state machine. It is shown that, when the unique input/output sequence (UIO) is used in place of the more cumbersome distinguishing sequence, both the controllability and observability problems of the protocol testing problem are addressed, providing an efficient method for computing a test sequence for protocol conformance testing.>

The general principles of detection, classification, and measurement of discontinuities are studied. The following issues are discussed: detecting the location of discontinuities; classifying discontinuities by their degrees; measuring the size of discontinuities; and coping with the random noise and designing optimal discontinuity detectors. An algorithm is proposed for discontinuity detection from an input signal S. For degree k discontinuity detection and measurement, a detector (P, Phi ) is used, where P is the pattern and Phi is the corresponding filter. If there is a degree k discontinuity at location t/sub 0/, then in the filter response there is a scaled pattern alpha P at t/sub 0/, where alpha is the size of the discontinuity. This reduces the problem to searching for the scaled pattern in the filter response. A statistical method is proposed for the approximate pattern matching. To cope with the random noise, a study is made of optimal detectors, which minimize the effects of noise.>

An edge detector is proposed which consists of a pair of a pattern and a linear filter. It is shown that for an edge in the input signal, there is a scaled pattern in the filter response. The location of the pattern is the location of the edge, and the scaling factor of the pattern is the size of the edge. Therefore the problem of edge detection and measurement is reduced to searching for the (scaled) pattern in the filter response. In the presence of noise, the pattern matching is approximate. A statistical approach for the pattern search is proposed. Optimal detectors which minimize the effects of noise are studied; for white noise, the optimal detectors are natural splines. Testing results on real images are reported.>

The problem of shape from shading and occluding boundaries can be reduced to solving a system of nonlinear equations for a smoothing spline, using regularization. The author discusses some theoretical issues corrected with this problem. He studies the existence and uniqueness of the smoothing spline. For solving the system of equations, he presents an iterative algorithm and proves that it converges to the unique solution for arbitrary regions. He also discusses efficient implementations of the iterative method, and analyzes their computational complexity.>

The authors provide theoretical justification for the use of zero crossings of residuals (between a filtered image and the original) for edge detection. The smoothed version is obtained by bilinear interpolation as a result of two-dimensional discrete regularization of subsampled images. The method is also applicable to smoothed images obtained by convolution with a Gaussian. Examples of applications of the method are shown for three kinds of pictures: aerial photographs, low-quality pictures of tools, and a high-quality picture of a face. The same parameters are used in all the examples. In addition they show examples of the results of one of the Canny edge detectors on the same pictures.>

The general principles of detection, classification, and measurement of discontinuities are studied. The following issues are discussed: detecting the location of discontinuities; classifying discontinuities by their degrees; measuring the size of discontinuities; and coping with the random noise and designing optimal discontinuity detectors. An algorithm is proposed for discontinuity detection from an input signal S. For degree k discontinuity detection and measurement, a detector (P, Phi ) is used, where P is the pattern and Phi is the corresponding filter. If there is a degree k discontinuity at location t/sub 0/, then in the filter response there is a scaled pattern alpha P at t/sub 0/, where alpha is the size of the discontinuity. This reduces the problem to searching for the scaled pattern in the filter response. A statistical method is proposed for the approximate pattern matching. To cope with the random noise, a study is made of optimal detectors, which minimize the effects of noise. >

We study some computational aspects of determining optical flow. Necessary and sufficient con- ditions are investigated for the existence and uniqueness of the smoothing-spline from regularization. We discuss different boundary conditions: free, Neuman, and Dirich- let boundary conditions. We show that both free and Neuman boundary problems are ill-conditioned, and are not appropriate for optical flow computation. We discuss Dirichlet boundary problem in more details. As a com- mon practice in low-level vision, a continuous problem is formulated, and a discrete version of the problem is solved instead. We estimate the discretization errors, and com- pute the resulting discrete smoothing-splines. We study efficient iterative methods for solving the system of linear equations for the discrete smoothing-splines. We propose the Chebyshev method for the computation. The Cheby- shev method converges faster than the Gauss-Seidel and Jacobi methods, and is parallelizable.

Regularization is equivalent to fitting smoothing splines to the data so that efficient and reliable numerical algorithms exist for finding solutions. however, the results exhibit poor performance along edges and boundaries. To cope with such anomalies, a more general class of smoothing splines that preserve corners and discontinuities is studied. Cubic splines are investigated in detail, since they are easy to implement and produce smooth curves near all data points except those marked as discontinuities or creases. A discrete regularization method is introduced to locate corners and discontinuities in the data points before the continuous regularization is applied.>

We present a family of data structures that can process a sequence of insert, delete, and lookup instructions such that each lookup and deletion is done in constant worst-case time and each insertion is done in constant expected time. The amount of space used by each data structure is proportional to the maximal number of elements that need to be stored at any moment in time.

We study approximation of linear functionals on separable Banach spaces equipped with a Gaussian measure. We study optimal information and optimal algorithms in average case, probabilistic, and asymptotic settings, for a general error criterion. We prove that adaptive information is not more powerful than nonadaptive information and that μ-spline algorithms, which are linear, are optimal in all three settings. Some of these results hold for approximation of linear operators. We specialize our results to the space of functions with continuous rth derivatives, equipped with a Wiener measure. In particular, we show that the natural splines of degree 2r + I yield the optimal algorithms. We apply the general results to the problem of integration.