浅谈PAP与CHAP认证

分析PPP中PAP与CHAP两种认证方法的原理及认证工作过程.利用实际例子实现PAP与CHAP两种认证方法的单向认证、双向认证,并给出具体操作方法.给出验证PAP与CHAP认证是否成功的方法.     

Murg term rewrite systems

The union of a monadic and a right-ground term rewrite system is called a murg term rewrite system. We show that for murg TRSs the ground common ancestor problem is undecidable. We show that for a murg term rewrite system it is undecidable whether the set of descendants of a ground tree is a recognizable tree language. We show that it is undecidable whether a murg term rewrite system over Σ preserves Σ-recognizability.     

Well rewrite orderings and well quasi-orderings

This paper studies well (quasi) orderings described as rewrite orderings and proposes a new family of well (quasi) orderings that extends the embedding or divisibility order of G. Higman. For instance, the well (quasi) orderings proposed in this paper may contain pairs of the form f(f(χ)) >f(g(f(χ))). Conditions called basicity and projectivity under which the transitive closure of a well-founded rewrite relation is a well-quasi-ordering are given. A tool based on narrowing is proposed for proving projectivity.     

Semantic foundations for generalized rewrite theories

Rewriting logic (RL) is a logic of actions whose models are concurrent systems. Rewrite theories involve the specification of equational theories of data and state structures together with a set of rewrite rules that model the dynamics of concurrent systems. Since its introduction, more than one decade ago, RL has attracted the interest of both theorists and practitioners, who have contributed in showing its generality as a semantic and logical framework and also as a programming paradigm. The experimentation conducted in these years has suggested that some significant extensions to the original definition of the logic would be very useful in practice. These extensions may develop along several dimensions, like the choice of the underlying equational logic, the kind of side conditions allowed in rewrite rules and operational concerns for the execution of certain rewrites. In particular, the Maude system now supports subsorting and conditional sentences in the equational logic for data, and also frozen arguments to block undesired nested rewrites; moreover, it allows equality and membership assertions in rule conditions. In this paper, we give a detailed presentation of the inference rules, model theory, and completeness of such generalized rewrite theories. Our results provide a mathematical semantics for Maude, and a foundation for formal reasoning about Maude specifications.     

一种改进的 CHAP 方案

电子计算机的普及和互联网技术日新月异的发展使得计算机网络已经渗透到社会生活的各个方面。但网络的全球化、开放化的特点使得网络环境充满着复杂性和不确定性,各种网络攻击与假冒手段等不安全因素充斥着整个网络。因此,如何保证网上业务开展的安全性是当前面临的主要问题,计算机网络安全已经成为当今世界各国共同关注的焦点。身份认证技术是构筑现代网络信息系统安全基石的不可或缺的组成部分,是信息安全的基础。目前,常用的身份认证方法有：基于证书的数字签名认证方式和口令方式。基于证书的数字签名认证的安全性较高,但需要一个完善的证书系统作为基础。而基于口令的身份认证技术作为最早出现的身份认证技术之一,以其简洁性和实用性得到了广泛的应用和发展,成为了网络安全中重要的分支。但是传统的静态口令身份认证技术存在着明显的安全漏洞,动态口令身份认证技术就是针对静态口令身份认证技术的安全隐患而提出的。动态口令是随机变化的一种口令,在口令中加入不确定因子作为动态因子,以提高登录过程中的安全性。文章在深入分析了传统的 CHAP 动态口令身份认证方案及其一系列衍生方案的优点与不足的基础上,结合安全的散列函数和异或运算,同时引入了保护认证信息的干扰因子,设计并实现了一种改进的 CHAP 一次性口令双向身份认证协议。本方案分为用户注册、登录认证和密码修改三个阶段。只需要通信双方的三次信息握手就实现了客户端与服务器端的双向身份认证。与其它几种典型的 CHAP 改进方案相比,本方案不但实现了通信双方的双向身份认证,而且具有通信量小、灵活性高、安全性强、成本低等特点。通过对整个方案的安全性测试和性能测试可以看出,本方案能够?     

Decidability of the confluence of finite ground term rewrite systems and of other related term rewrite systems

The aim of this paper is to propose an algorithm to decide the confluence of finite ground term rewrite systems. Actually a more general class of possibly infinite ground term rewrite systems is studied. It is well known that the confluence is not decidable for general term rewrite systems, but this paper proves it is for ground term rewrite systems following a conjecture made by Huet and Oppen in their survey. The result is also applied to the confluence of left-linear and right-ground term rewrite systems. We also sketch an algorithm for checking this property. This algorithm is based on tree automata and tree transducers. Here, we regard them as rewrite systems and specialists in automata theory would translate that easily in their language.     

Proving geometry theorems with rewrite rules

We investigate the application of rewrite rules to proving theorems from elementary geometry. We have proven 80 theorems, some of them quite difficult. There is a discussion of the formulation of the problem and degenerate conditions. The authors thank the National Science Foundation for its support of the work described in this article.     

Cooperating rewrite processes for natural-language analysis

General methods for understanding a natural language based on the intensive use of rewrite rules and on the existence of several cooperating processes are put forward. The choice of Horn-clause logic as the underlying formalism for semantic representations, together with the employment of unification as pattern-matching procedure and depth-first search with backtracking were derived from logic-programming ideas, in particular from the use of PROLOG. Several examples are presented to illustrate how these methods work.     

Synthesis of rewrite programs by higher-order and semantic unification

This paper presents a framework for synthesizing rewrite programs using higher-order and semantic unification. Many problems in computer science and artificial intelligence can be formalized as problems of higher-order unification. Among such problems is first-order anti-unification. In this paper, we show that first-order anti-unification can be regarded as a second-order matching problem and solved by the algorithm for higher-order unification.     

Termination of rewrite systems by elementary interpretations

We focus on termination proofs of rewrite systems, especially of rewrite systems containing associative and commutative operators. We prove their termination by elementary interpretations, more specifically, by functions defined by addition, multiplication and exponentiation. We discuss a method based on polynomial interpretations and propose an implementation of a mechanisation of the comparison of expressions built with polynomials and exponentials.     

Proving termination of (conditional) rewrite systems

In this paper an important problem in the domain of term rewriting, the termination of (conditional) rewrite systems, is dealt with. We show that in many applications, well-founded orderings on terms which only make use of syntactic information of a rewrite systemR, do not suffice for proving termination ofR. Indeed sometimes semantic information is needed to orient a rewrite rule. Therefore we integrate a semantic interpretation of rewrite systems and terms into a well-founded ordering on terms: the notion ofsemantic ordering is the first main contribution of this paper. The use and usefulness of the semantic ordering in proving termination is illustrated by means of some realistic examples.Furthermore the concept of semantic information induces a novel approach for proving termination inconditional rewrite systems. The idea is to employ not only semantic information contained in the terms that are to be compared, but also extra (semantic) information contained in the premiss of the conditional equation in which the terms appear. This leads to our second contribution in the termination problem area: the notion ofcontextual ordering andcontextual semantic ordering. Thecontextual approach allows to prove termination of conditional rewrite systems where all classical partial orderings would fail.     

Generating priority rewrite systems for OSOS process languages

We propose an algorithm for generating a Priority Rewrite System (PRS) for an arbitrary process language in the OSOS format such that rewriting of process terms is sound for bisimulation and head normalising. The algorithm is inspired by a procedure which was developed by Aceto, Bloom and Vaandrager and presented in Turning SOS rules into equations [L. Aceto, B. Bloom, F.W. Vaandrager, Turning SOS rules into equations, Information and Computation 111 (1994) 1–52].For a subclass of OSOS process languages representing finite behaviours the PRSs that are generated by our algorithm are strongly normalising (terminating) and confluent, where termination is proved using the dependency pair and dependency graph techniques. Additionally, such PRSs are complete for bisimulation on closed process terms modulo associativity and commutativity of the choice operator of CCS. We illustrate the usefulness of our results, and the benefits of rewriting with priorities in general, with several examples.     

Invariants and closures in the theory of rewrite systems

The article investigates some useful concepts of rewrite systems, especially invariants and closures. The concepts are formalised with so-called string expressions, for which an axiomatisation is given. The central operator in the theory of rewrite systems, the rewrite operator, is introduced with formulas that permit a calculational approach. The connections with distributed programming are also explained.     

On intuitionistic proof nets with additional rewrite rules and their approximations

First we present a proof nets system with eight additional rewrite rules, which concerns ordering of introductions of exponential-links and are only applied to normal forms of proof nets in the usual sense. We show that the reduction relation generated by these eight rewrite rules is strong normalizing and confluent. Second we propose an simply judged equality on intuitionistic proof nets based on the notion of the main path of an intuitionistic proof net. The notion is an analogue of Böhm-trees in λ-calculus.     

Model checking for process rewrite systems and a class of action-based regular properties

We consider the model checking problem for Process Rewrite Systems (PRS), an infinite-state formalism (non Turing-powerful) which subsumes many common models such as Pushdown Processes and Petri Nets. PRS can be adopted as a formal model for programs with dynamic creation and synchronization of concurrent processes, and with recursive procedures. The model-checking problem of PRS against action-based linear temporal logic (ALTL) is undecidable. However, decidability for some interesting fragment of ALTL remains an open question. In this paper, we state decidability results concerning generalized acceptance properties about infinite derivations (infinite term rewriting) in PRS. As a consequence, we obtain decidability of the model-checking problem (restricted to infinite runs) of PRS against a meaningful fragment of ALTL.     

Orienting rewrite rules with the Knuth–Bendix order

We consider two decision problems related to the Knuth–Bendix order (KBO). The first problem is orientability: given a system of rewrite rules R, does there exist an instance of KBO which orients every ground instance of every rewrite rule in R. The second problem is whether a given instance of KBO orients every ground instance of a given rewrite rule. This problem can also be reformulated as the problem of solving a single ordering constraint for the KBO. We prove that both problems can be solved in the time polynomial in the size of the input. The polynomial-time algorithm for orientability builds upon an algorithm for solving systems of homogeneous linear inequalities over integers. We show that the orientability problem is P-complete. The polynomial-time algorithm for solving a single ordering constraint does not need to solve systems of linear inequalities and can be run in time O(n²). Also we show that if a system is orientable using a real-valued instance of KBO, then it is also orientable using an integer-valued instance of KBO. Therefore, all our results hold both for the integer-valued and the real-valued KBO.