A model-based approximate λ-policy iteration approach to online evasive path planning and the video game Ms. Pac-Man

This paper presents a model-based approximate λ-policy iteration approach using temporal differences for optimizing paths online for a pursuit-evasion problem, where an agent must visit several target positions within a region of interest while simultaneously avoiding one or more actively pursuing adversaries. This method is relevant to applications, such as robotic path planning, mobile-sensor applications, and path exposure. The methodology described utilizes cell decomposition to construct a decision tree and implements a temporal difference-based approximate λ-policy iteration to combine online learning with prior knowledge through modeling to achieve the objectives of minimizing the risk of being caught by an adversary and maximizing a reward associated with visiting target locations. Online learning and frequent decision tree updates allow the algorithm to quickly adapt to unexpected movements by the adversaries or dynamic environments. The approach is illustrated through a modified version of the video game Ms. Pac-Man, which is shown to be a benchmark example of the pursuit-evasion problem. The results show that the approach presented in this paper outperforms several other methods as well as most human players.     

An underwater sensor allocation scheme for a range dependent environment

A series of assumptions is typically made when designing a field of passive underwater sensors. One of the more glaring is range independence throughout an operational area. It is unlikely that a large water space will have uniform acoustic characteristics throughout, i.e., the performance of a sensor will vary based upon its physical location. In an area clearance scenario, where there is no apparent target for an adversary to gravitate towards, such as a ship or a port, it is difficult to determine where the field designer should allocate sensors so that their deployment locations can be planned efficiently. To intelligently allocate sensors, a field designer could first divide an area into sectors of relatively uniform acoustics, based upon variations in acoustic characteristics throughout the area. A prediction of how often a threat submarine will visit each sector can then be made in order to increase the field’s detection capabilities. In this work, an area of interest is divided into sectors of varying geographic size and acoustic characteristics and the probability of visitation to each sector by a threat submarine is determined by solving a minimax matrix game. The Game Theory Field Design (GTFD) model is proposed, which allocates sensors to sectors of relatively uniform acoustics according to the visitation probabilities of an adversary, against adversaries of varying intelligence. In a comparison with two models that do not consider these visitation probabilities and only examine either acoustic characteristics or the size of the sectors, GTFD is shown to offer a significant improvement in terms of overall field detection capability against intelligent adversaries.     

The Lazy Adversary Conjecture Fails

In the context of competitive analysis of online algorithms for the k-server problem, it has been conjectured that every randomized, memoryless online algorithm exhibits the highest competitive ratio against an offline adversary that is lazy, i.e., that will issue requests forcing it to move one of its own servers only when this is strictly necessary to force a move on the part of the online algorithm. We prove that, in general, this lazy adversary conjecture fails. Moreover, it fails in a very strong sense: there are adversaries which perform arbitrarily better than any other adversary which is even slightly "lazier."     

A new provably secure certificateless short signature scheme

Certificateless public key cryptography simplifies the complex certificate management in the traditional public key cryptography and resolves the key escrow problem in identity-based cryptography. In 2007, Huang et al. revisited the security models of certificateless signature scheme. They classified adversaries according to their attack power into normal, strong, and super adversaries (ordered by their attack power). Recently, Du and Wen proposed a short certificateless signature scheme and presented that their scheme is secure against the strong adversary in the random oracle model. In this paper, we show that their short signature scheme is insecure against the strong adversary. We then propose a new short certificateless signature scheme which is secure against the super adversary. Our scheme is the first certificateless signature scheme which satisfies both the strongest security level and the shortest signature length.     

Motion planning for multitarget surveillance with mobile sensor agents

In the surveillance of multiple targets by mobile sensor agents (MSAs), system performance relies greatly on the motion-control strategy of the MSAs. This paper investigates the motion-planning problem for a limited resource of M MSAs in an environment of N targets (M相似文献   

Adversary Aware Surveillance Systems

We consider surveillance problems to be a set of system-adversary interaction problems in which an adversary can be modeled as a rational (selfish) agent trying to maximize his utility. We feel that appropriate adversary modeling can provide deep insights into the system performance and also clues for optimizing the system's performance against the adversary. Further, we propose that system designers should exploit the fact that they can impose certain restrictions on the intruders and the way they interact with the system. The system designers can analyze the scenario to determine conditions under which system outperforms the adversaries, and then suitably reengineer the environment under a “scenario engineering” approach to help the system outperform the adversary. We study the proposed enhancements using a game theoretic framework and present results of their adaptation to two significantly different surveillance scenarios. While the precise enforcements for the studied zero-sum ATM lobby monitoring scenario and the nonzero-sum traffic monitoring scenario were different, they lead to some useful generic guidelines for surveillance system designers.      

Modeling and analysis of air campaign resource allocation: a spatio-temporal decomposition approach

In this paper, we address the modeling and analysis issues associated with a generic theater level campaign where two adversaries pit their military resources against each other over a sequence of multiple engagements. In particular, we consider the scenario of an air raid campaign where one adversary uses suppression of enemy air defense (SEAD) aircraft and bombers (BMBs) against the other adversary's invading ground troops (GTs) that are defended by their mobile air defense (AD) units. The original problem is decomposed into a temporal and a spatial resource allocation problem. The temporal resource allocation problem is formulated and solved in a game-theoretical framework as a multiple resource interaction problem with linear attrition functions. The spatial resource allocation problem is posed as a risk minimization problem in which the optimal corridor of ingress and optimal movement of the GTs and AD units are decided by the adversaries. These two solutions are integrated using an aggregation/deaggregation approach to evaluate resource strengths and distribute losses. Several simulation experiments were carried out to demonstrate the main ideas.     

一种IND-CCA2完全匿名的短群签名

基于线性假设下的Cramer-Shoup加密方案和SDH假设,提出一种新的SDH问题的零知识证明协议,并基于此协议构造了一种在Bellare-Micciancio-Warinshi模型下可证明安全的短群签名方案.该方案具有IND-CCA2完全匿名性,允许攻击者在攻击完全匿名性时提问打开预言机.签名的长度仅为1704bits.     

Weakening the perfect encryption assumption in Dolev–Yao adversaries

We consider secrecy and authentication in a simple process calculus with cryptographic primitives. The standard Dolev–Yao adversary is enhanced so that it can guess the key required to decrypt an intercepted message. We borrow from the computational complexity approach the assumptions that guessing succeeds with a given negligible probability and that the resources available to adversaries are polynomially bounded. Under these hypotheses we prove that the standard Dolev–Yao adversary is as powerful as the enhanced one.     

The disagreement power of an adversary

At the heart of distributed computing lies the fundamental result that the level of agreement that can be obtained in an asynchronous shared memory model where t processes can crash is exactly t?+?1. In other words, an adversary that can crash any subset of size at most t can prevent the processes from agreeing on t values. But what about all the other ${2^{2^n - 1} - (n+1)}$ adversaries that are not uniform in this sense and might crash certain combination of processes and not others? This paper presents a precise way to classify all adversaries. We introduce the notion of disagreement power: the biggest integer k for which the adversary can prevent processes from agreeing on k values. We show how to compute the disagreement power of an adversary and derive n equivalence classes of adversaries.     

Online linear optimization and adaptive routing

This paper studies an online linear optimization problem generalizing the multi-armed bandit problem. Motivated primarily by the task of designing adaptive routing algorithms for overlay networks, we present two randomized online algorithms for selecting a sequence of routing paths in a network with unknown edge delays varying adversarially over time. In contrast with earlier work on this problem, we assume that the only feedback after choosing such a path is the total end-to-end delay of the selected path. We present two algorithms whose regret is sublinear in the number of trials and polynomial in the size of the network. The first of these algorithms generalizes to solve any online linear optimization problem, given an oracle for optimizing linear functions over the set of strategies; our work may thus be interpreted as a general-purpose reduction from offline to online linear optimization. A key element of this algorithm is the notion of a barycentric spanner, a special type of basis for the vector space of strategies which allows any feasible strategy to be expressed as a linear combination of basis vectors using bounded coefficients.We also present a second algorithm for the online shortest path problem, which solves the problem using a chain of online decision oracles, one at each node of the graph. This has several advantages over the online linear optimization approach. First, it is effective against an adaptive adversary, whereas our linear optimization algorithm assumes an oblivious adversary. Second, even in the case of an oblivious adversary, the second algorithm performs slightly better than the first, as measured by their additive regret.     

Classifier evaluation and attribute selection against active adversaries

Many data mining applications, such as spam filtering and intrusion detection, are faced with active adversaries. In all these applications, the future data sets and the training data set are no longer from the same population, due to the transformations employed by the adversaries. Hence a main assumption for the existing classification techniques no longer holds and initially successful classifiers degrade easily. This becomes a game between the adversary and the data miner: The adversary modifies its strategy to avoid being detected by the current classifier; the data miner then updates its classifier based on the new threats. In this paper, we investigate the possibility of an equilibrium in this seemingly never ending game, where neither party has an incentive to change. Modifying the classifier causes too many false positives with too little increase in true positives; changes by the adversary decrease the utility of the false negative items that are not detected. We develop a game theoretic framework where equilibrium behavior of adversarial classification applications can be analyzed, and provide solutions for finding an equilibrium point. A classifier??s equilibrium performance indicates its eventual success or failure. The data miner could then select attributes based on their equilibrium performance, and construct an effective classifier. A case study on online lending data demonstrates how to apply the proposed game theoretic framework to a real application.     

An efficient and practical threshold gateway-oriented password-authenticated key exchange protocol in the standard model

With the assistance of an authentication server, a gateway-oriented password-authenticated key exchange (GPAKE) protocol can establish a common session key shared between a client and a gateway. Unfortunately, a GPAKE protocol becomes totally insecure if an adversary can compromise the authentication server and steal the passwords of the clients. In order to provide resilience against adversaries who can hack into the authentication server, we propose a threshold GPAKE protocol and then present its security proof in the standard model based on the hardness of the decisional Diffie-Hellman (DDH) problem. In our proposal, the password is shared among n authentication servers and is secure unless the adversary corrupts more than t+1 servers. Our protocol requires n > 3t servers to work. Compared with existing threshold PAKE protocols, our protocol maintains both stronger security and greater efficiency.     

对一种无证书代理签名方案的分析与改进

分析了一种无证书代理签名方案,指出其针对于无证书密码系统中的两类敌手都不安全。类型I敌手可替换用户的公钥来伪造代理授权和代理签名;类型II敌手(KGC)可针对预先选择好的用户生成特殊的系统参数,然后伪造代理授权。为了克服这些安全问题,提出了一种改进的方案,分析表明,新方案具有更好的安全性。     

无证书代理盲签名方案的安全性分析?

分析证明某无证书代理盲签名方案对于无证书密码体制的2类敌手都不安全。类型I敌手利用公钥替换攻击,可以伪造任意原始签名者对代理签名者的代理授权,或伪造任意合法代理签名者的代理盲签名。类型II敌手利用预选的目标用户生成含有陷门信息的系统参数后,可以伪造该目标用户对任意其他用户的代理授权,从而使非法代理签名者生成未经授权的代理盲签名。     

Broadcasting in dynamic radio networks

It is reasonable to claim that almost all major questions related to radio broadcasting can be considered closed as far as static networks are considered: the network never changes during the entire protocol's execution. On the other hand, theoretical results on communication protocols in any scenario where the network topology may change during protocol's execution (i.e. a dynamic radio network) are very few.In this paper, we present a theoretical study of broadcasting in radio networks having dynamic unknown topology. The dynamic network is modeled by means of adversaries: we consider two of them. We first analyze an oblivious, memoryless random adversary that can be seen as the dynamic version of the average-case study presented by Elsässer and Gasieniec in JCSS, 2006. We then consider the deterministic worst-case adversary that, at each time slot, can make any network change (thus the strongest adversary). This is the dynamic version of the worst-case study provided by Bar-Yehuda, Goldreich and Itai in JCSS, 1992.In both cases we provide tight bounds on the completion time of randomized broadcast protocols.     

On Delivery Times in Packet Networks under Adversarial Traffic

We consider packet networks and make use of the "adversarial queuing theory" model [10]. We are interested in the question of guaranteeing that all packets are actually delivered to destination, and of having an upper bound on the delivery times of all packets. Whether this is possible against all adversarial queuing theory rate-1 adversaries was previously posed as an open question [13],[10]. Among other things, we give a queuing policy that guarantees bounded delivery time whenever the rate-1 adversary injects a sequence of packets for which there exists a schedule with a finite upper bound on the delivery times of all packets, and adheres to certain additional conditions. On the negative side we show that there exist rate-1 sequences of packets for which there is no schedule with a finite upper bound on the delivery times of all packets. We thus answer an open question posed by Gamarnik [13]. We further show that delivering all packets while maintaining stability (we coin the term "reliability" for this property) can be done by an offline scheduler whenever the injection of packets is done at rate of at most 1. However, on the other hand, we also show that there is no online protocol (even centralized) that can achieve that property against all rate-1 adversaries. We thus answer an open question of Borodin et al. [10].     

Dynamic path privacy protection framework for continuous query service over road networks

Many applications of location based services (LBSs), it is useful or even necessary to ensure that LBSs services determine their location. For continuous queries where users report their locations periodically, attackers can infer more about users’ privacy by analyzing the correlations of their query samples. The causes of path privacy problems, which emerge because the communication by different users in road network using location based services so, attacker can track continuous query information. LBSs, albeit useful and convenient, pose a serious threat to users’ path privacy as they are enticed to reveal their locations to LBS providers via their queries for location-based information. Traditional path privacy solutions designed in Euclidean space can be hardly applied to road network environment because of their ignorance of network topological properties. In this paper, we proposed a novel dynamic path privacy protection scheme for continuous query service in road networks. Our scheme also conceals DPP (Dynamic Path Privacy) users’ identities from adversaries; this is provided in initiator untraceability property of the scheme. We choose the different attack as our defending target because it is a particularly challenging attack that can be successfully launched without compromising any user or having access to any cryptographic keys. The security analysis shows that the model can effectively protect the user identity anonymous, location information and service content in LBSs. All simulation results confirm that our Dynamic Path Privacy scheme is not only more accurate than the related schemes, but also provide better locatable ratio where the highest it can be around 95 % of unknown nodes those can estimate their position. Furthermore, the scheme has good computation cost as well as communication and storage costs.Simulation results show that Dynamic Path Privacy has better performances compared to some related region based algorithms such as IAPIT scheme, half symmetric lens based localization algorithm (HSL) and sequential approximate maximum a posteriori (AMAP) estimator scheme.     

无线传感器网络中的位置隐私保护

随着无线传感器网络的广泛应用,隐私成为无线传感器网络成功使用的主要障碍。当无线传感器网络用于监控敏感对象,被监控对象的位置隐私成为一个重要问题。在传感节点发送一系列分组,通过多跳,向基站报告监控对象时,敌手能够反向追踪分组到信息源位置。基于洪泛的幻影具有消息发送时间长且能量消耗过大的缺陷。为了保护能量受限的无线传感器网络中的位置隐私,提出了定向随机步。定向随机步使敌手难于跳到跳地反向追踪信息源。在定向随机步中,信源节点发出一个分组,此分组被单播给信源节点的父节点。当中介节点收到一个分组,它以等概率的方式转发给它的一个父节点。与基于洪泛的幻影相比,定向随机步具有较小的信息发送时间和较低的能量消耗。特别在中介节点具有多个父节点的情形下,定向随机步具有较大的安全期。     

Iterative path-accurate trajectory generation for fast sensor-based motion of robot arms

Sensor-based trajectory generation of industrial robots can be seen as the task of, first, adaptation of a given robot program according to the actually sensed world, and second, its modification that complies with robot constraints regarding its velocity, acceleration, and jerk. The second task is investigated in this paper. Whenever the sensed trajectory violates a constraint, a transient trajectory is computed that, both, keeps the sensed path, and reaches the sensed trajectory as fast as possible while satisfying the constraints. This is done by an iteration of forward scaling and backtracking. In contrast to previous papers, a new backtracking algorithm and an adaptation of the prediction length are presented that are favorable for high-speed trajectories. Arc Length Interpolation is used in order to improve the path accuracy. This is completed by provisions against cutting short corners or omitting of loops in the given path. The refined trajectory is computed within a single sampling step of 4 ms using a standard KUKA industrial robot.