Proofs of randomized algorithms in Coq

Randomized algorithms are widely used for finding efficiently approximated solutions to complex problems, for instance primality testing and for obtaining good average behavior. Proving properties of such algorithms requires subtle reasoning both on algorithmic and probabilistic aspects of programs. Thus, providing tools for the mechanization of reasoning is an important issue. This paper presents a new method for proving properties of randomized algorithms in a proof assistant based on higher-order logic. It is based on the monadic interpretation of randomized programs as probabilistic distributions (Giry, Ramsey and Pfeffer). It does not require the definition of an operational semantics for the language nor the development of a complex formalization of measure theory. Instead it uses functional and algebraic properties of unit interval. Using this model, we show the validity of general rules for estimating the probability for a randomized algorithm to satisfy specified properties. This approach addresses only discrete distributions and gives rules for analyzing general recursive functions.We apply this theory to the formal proof of a program implementing a Bernoulli distribution from a coin flip and to the (partial) termination of several programs. All the theories and results presented in this paper have been fully formalized and proved in the Coq proof assistant.     

A Visualization Based Approach for Digital Signature Authentication

We propose a visualization based approach for digital signature authentication. Using our method, the speed and pressure aspects of a digital signature process can be clearly and intuitively conveyed to the user for digital signature authentication. Our design takes into account both the expressiveness and aesthetics of the derived visual patterns. With the visual aid provided by our method, digital signatures can be authenticated with better accuracy than using existing methods—even novices can examine the authenticity of a digital signature in most situations using our method. To validate the effectiveness of our method, we conducted a comprehensive user study which confirms positively the advantages of our approach. Our method can be employed as a new security enhancement measure for a range of business and legal applications in reality which involve digital signature authorization and authentication.     

Efficient migration access control for mobile agents

The speed and convenience of the Internet has facilitated dynamic development in electronic commerce in recent years. E-commerce technologies and applications are widely studied by expert researchers. Mobile agent is considered to have high potential in e-commerce; it has been attracting wide attention in recent years. Mobile agent has high autonomy and mobility; it can move unbridled in different runtime environments carrying out assigned tasks while automatically detecting its current environment and responding accordingly. The above qualities make mobile agent very suitable for use in e-commerce. The Internet is an open environment, but transfer of confidential data should be conducted only over a secure environment. So, to transfer information over the Internet, a secure Internet environment is absolutely essential. Therefore, the security of present Internet environment must be improved. During its execution, a mobile agent needs to roam around on the Internet between different servers, and it may come in contact with other mobile agents or hosts; it may also need to interact with them. So, a mobile agent might come to harm when it meets a malicious host, and the confidentiality of data could also be compromised. To tackle the above problems, this paper proposes a security scheme for mobile agents. It is designed to ensure the safety of mobile agents on the Internet, and it also has access control and key management to ensure security and data confidentiality. Volker and Mehrdad [R. Volker, J.S. Mehrdad, Access Control and Key Management for Mobile Agents, “Computer Graphics”, Vol. 22, No. 4, August 1998, pp. 457–461] have already proposed an access control and key management scheme for mobile agents, but it needs large amount of space. So, this paper proposes a new scheme that uses the concepts of Chinese Remainder Theorem [F.H. Kuo, V.R.L. Shen, T.S. Chen, F. Lai, A Cryptographic Key Assignment Scheme for Dynamic Access Control in a User Hierarchy, “IEE Proceeding on Computers & Digital Techniques”, Vol. 146, No. 5, Sept. 1999, pp. 235–240., T.S. Chen, Y.F. Chung, Hierarchical Access Control Based on Chinese Remainder Theorem and Symmetric Algorithm, ”Computers & Security”, Vol. 21, No. 6, 2002, pp. 565–570., U.P. Lei, S.C. Wang, A Study of the Security of Mambo et al.'s Proxy Signature Scheme Based on the Discrete Logarithm Problem, June 2004], hierarchical structure and Superkey [S.G. Akl, P.D. Taylor, Cryptographic Solution to a Problem of Access Control in a Hierarchy, “ACM Transactions on Computer Systems”, Vol. 1, No. 3, August 1983, pp. 239–248]. A security and performance analysis of the proposed scheme shows that the scheme effectively protects mobile agents.     

A Fast Approximation of the Bilateral Filter Using a Signal Processing Approach

The bilateral filter is a nonlinear filter that smoothes a signal while preserving strong edges. It has demonstrated great effectiveness for a variety of problems in computer vision and computer graphics, and fast versions have been proposed. Unfortunately, little is known about the accuracy of such accelerations. In this paper, we propose a new signal-processing analysis of the bilateral filter which complements the recent studies that analyzed it as a PDE or as a robust statistical estimator. The key to our analysis is to express the filter in a higher-dimensional space where the signal intensity is added to the original domain dimensions. Importantly, this signal-processing perspective allows us to develop a novel bilateral filtering acceleration using downsampling in space and intensity. This affords a principled expression of accuracy in terms of bandwidth and sampling. The bilateral filter can be expressed as linear convolutions in this augmented space followed by two simple nonlinearities. This allows us to derive criteria for downsampling the key operations and achieving important acceleration of the bilateral filter. We show that, for the same running time, our method is more accurate than previous acceleration techniques. Typically, we are able to process a 2 megapixel image using our acceleration technique in less than a second, and have the result be visually similar to the exact computation that takes several tens of minutes. The acceleration is most effective with large spatial kernels. Furthermore, this approach extends naturally to color images and cross bilateral filtering.     

Robot learning language — Integrating programming and learning for cognitive systems

One central property of cognitive systems is the ability to learn and to improve continually. We present a robot control language that combines programming and learning in order to make learning executable in the normal robot program. The language constructs of our learning language RoLL rely on the concept of hierarchical hybrid automata to enable a declarative, explicit specification of learning problems. Using the example of an autonomous household robot, we point out some instances where learning–and especially continued learning–makes the robot control program more cognitive.     

Multiphase Image Segmentation and Modulation Recovery Based on Shape and Topological Sensitivity

Topological sensitivity analysis is performed for the piecewise constant Mumford-Shah functional. Topological and shape derivatives are combined in order to derive an algorithm for image segmentation with fully automatized initialization. Segmentation of 2D and 3D data is presented. Further, a generalized Mumford-Shah functional is proposed and numerically investigated for the segmentation of images modulated due to, e.g., coil sensitivities.

A formally specified ontology management API as a registry for ubiquitous computing systems

Recently, several standards have emerged for ontology markup languages that can be used to formalize all kinds of knowledge. However, there are no widely accepted standards yet that define APIs to manage ontological data. Processing ontological information still suffers from the heterogeneity imposed by the plethora of available ontology management systems. Moreover, ubiquitous computing environments usually comprise software components written in a variety of different programming languages, which makes it particularly difficult to establish a common ontology management API with programming language agnostic semantics. We implemented an ontological Knowledge Base Server, which can expose the functionality of arbitrary off-the-shelf ontology management systems via a formally specified and well defined API. A case study was carried out in order to demonstrate the feasibility of our approach to use a formally specified ontology management API to implement a registry for ubiquitous computing systems.     

Fixed-point DSP implementation of nonlinear controller for large gap electromagnetic suspension system

Electromagnetic suspension systems are inherently nonlinear and often face hardware limitation when digitally controlled. The main contributions of this paper are: the design of a nonlinear H_∞ controller, including dynamic weighting functions, applied to a large gap electromagnetic suspension system and the presentation of a procedure to implement this controller on a fixed-point DSP, through a methodology able to translate a floating-point algorithm into a fixed-point algorithm by using l_∞ norm minimization due to conversion error. Experimental results are also presented, in which the performance of the nonlinear controller is evaluated specifically in the initial suspension phase.     

对等数据管理系统中模式映射的备份机制

针对对等数据管理系统中节点因自治性而动态离开和返回网络造成模式映射路径频繁断裂的问题,提出一种基于模式映射备份机制的离开节点绕过方法,向下游节点提供以树状结构组织的上游映射信息。当映射路径中有节点离开时,其下游节点的查询以此映射信息和备份的上游映射,绕过离开节点。仿真和分析的结果表明,映射备份机制的引入提高了查询的可达性,从而可以从更多的局部数据库中获得返回结果。