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.      

基于博弈论的隐私保护分布式数据挖掘

隐私保护的分布式数据挖掘问题是数据挖掘领域的一个研究热点,而基于经济视角,利用博弈论的方法对隐私保护分布式数据挖掘进行研究只是处于初始阶段。基于收益最大化,研究了完全信息静态博弈下分布式数据挖掘中参与者(两方或多方)的策略决策问题,得出了如下结论:数据挖掘在满足一定的条件下,参与者(两方或多方)的准诚信攻击策略是一个帕累托最优的纳什均衡策略;在准诚信攻击的假设下,参与者(多方)的非共谋策略并不是一个纳什均衡策略。同时给出了该博弈的混合战略纳什均衡,它对隐私保护分布式数据挖掘中参与者的决策具有一定的理论和指导意义。     

Adversarial classification using signaling games with an application to phishing detection

In adversarial classification, the interaction between classifiers and adversaries can be modeled as a game between two players. It is natural to model this interaction as a dynamic game of incomplete information, since the classifier does not know the exact intentions of the different types of adversaries (senders). For these games, equilibrium strategies can be approximated and used as input for classification models. In this paper we show how to model such interactions between players, as well as give directions on how to approximate their mixed strategies. We propose perceptron-like machine learning approximations as well as novel Adversary-Aware Online Support Vector Machines. Results in a real-world adversarial environment show that our approach is competitive with benchmark online learning algorithms, and provides important insights into the complex relations among players.     

一种大数据环境中分布式辅助关联分类算法

在很多现实的分类应用中,新数据的类标需要由领域专家最终确定,而分类器的分类结果仅起辅助作用.另外,随着大数据所隐含价值越发被人们重视,分类器的训练会从面向单一数据集逐渐过渡到面向分布式空间数据集,大数据环境下辅助分类也将成为未来分类应用的重要分支.然而,现有的分类研究缺乏对此类应用的关注.大数据环境中的辅助分类面临以下3个问题:1) 训练集是分布式大数据集;2) 在空间上,训练集所包含的各局部数据源的类别分布不尽相同;3) 在时间上,训练集是动态变化的,会发生类别迁移现象.在考虑以上问题的基础上,提出一种大数据环境中分布式辅助关联分类方法.该方法首先给出一种大数据环境中分布式关联分类器构建算法,在该算法中,通过横向加权考虑分类数据集在空间上的类别分布差异,并给出"前件空间支持度-相关系数"的度量框架,改进关联分类算法面对不平衡数据的性能缺陷;然后,给出一种基于适应因子的辅助关联分类器动态调整方法,能够在分类器应用过程中充分利用领域专家实时反馈的结果对分类器进行动态调整,以提升其面向动态数据集的分类性能,减缓分类器的退化和重新训练的频率.实验结果表明,该方法能够面向分布式数据集较快地训练出有较高分类准确率的关联分类器,并在数据集不断扩充变化时提升分类性能,是一种有效的大数据环境中辅助分类应用方法.     

Training a reciprocal-sigmoid classifier by feature scaling-space

This paper presents a reciprocal-sigmoid model for pattern classification. This proposed classifier can be considered as a Φ-machine since it preserves the theoretical advantage of linear machines where the weight parameters can be estimated in a single step. The model can also be considered as an approximation to logistic regression under the framework of Generalized Linear Models. While inheriting the necessary classification capability from logistic regression, the problems of local minima and tedious recursive search no longer exist in the proposed formulation. To handle possible over-fitting when using high order models, the classifier is trained using multiple samples of uniformly scaled pattern features. Empirically, the classifier is evaluated using a benchmark synthetic data from random sampling runs for initial statistical evidence regarding its classification accuracy and computational efficiency. Additional experiments based on ten runs of 10-fold cross validations on 40 data sets further support the effectiveness of the reciprocal-sigmoid model, where its classification accuracy is seen to be comparable to several top classifiers in the literature. Main reasons for the good performance are attributed to effective use of reciprocal sigmoid for embedding nonlinearities and effective use of bundled feature sets for smoothing the training error hyper-surface. Editor: Risto Miikkulainen     

一种不平衡噪声数据流集成分类模型

针对不平衡噪声数据流的分类问题,本文利用基于平均概率的集成分类器AP与抽样技术,提出了一种处理不平衡噪声数据流的集成分类器(IMDAP)模型。实验结果表明,该集成分类器更能适应存在概念漂移与噪声的不平衡数据流挖掘分类,其整体分类性能优于AP集成分类器模型,能明显提升少数类的分类精度,并且具有与AP相近的时间复杂度。     

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.     

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.     

Large margin classification for combating disguise attacks on spam filters

This paper addresses the challenge of large margin classification for spam filtering in the presence of an adversary who disguises the spam mails to avoid being detected. In practice, the adversary may strategically add good words indicative of a legitimate message or remove bad words indicative of spam. We assume that the adversary could afiord to modify a spam message only to a certain extent, without damaging its utility for the spammer. Under this assumption, we present a large margin approach for classification of spam messages that may be disguised. The proposed classifier is formulated as a second-order cone programming optimization. We performed a group of experiments using the TREC 2006 Spam Corpus. Results showed that the performance of the standard support vector machine (SVM) degrades rapidly when more words are injected or removed by the adversary, while the proposed approach is more stable under the disguise attack.     

Reliable agnostic learning

It is well known that in many applications erroneous predictions of one type or another must be avoided. In some applications, like spam detection, false positive errors are serious problems. In other applications, like medical diagnosis, abstaining from making a prediction may be more desirable than making an incorrect prediction. In this paper we consider different types of reliable classifiers suited for such situations. We formalize the notion and study properties of reliable classifiers in the spirit of agnostic learning (Haussler, 1992; Kearns, Schapire, and Sellie, 1994), a PAC-like model where no assumption is made on the function being learned. We then give two algorithms for reliable agnostic learning under natural distributions. The first reliably learns DNFs with no false positives using membership queries. The second reliably learns halfspaces from random examples with no false positives or false negatives, but the classifier sometimes abstains from making predictions.     

A novel intrusion detection framework for wireless sensor networks

Vehicle cloud is a new idea that uses the benefits of wireless sensor networks (WSNs) and the concept of cloud computing to provide better services to the community. It is important to secure a sensor network to achieve better performance of the vehicle cloud. Wireless sensor networks are a soft target for intruders or adversaries to launch lethal attacks in its present configuration. In this paper, a novel intrusion detection framework is proposed for securing wireless sensor networks from routing attacks. The proposed system works in a distributed environment to detect intrusions by collaborating with the neighboring nodes. It works in two modes: online prevention allows safeguarding from those abnormal nodes that are already declared as malicious while offline detection finds those nodes that are being compromised by an adversary during the next epoch of time. Simulation results show that the proposed specification-based detection scheme performs extremely well and achieves high intrusion detection rate and low false positive rate.     

Similarity assessment for removal of noisy end user license agreements

In previous work, we have shown the possibility to automatically discriminate between legitimate software and spyware-associated software by performing supervised learning of end user license agreements (EULAs). However, the amount of false positives (spyware classified as legitimate software) was too large for practical use. In this study, the false positives problem is addressed by removing noisy EULAs, which are identified by performing similarity analysis of the previously studied EULAs. Two candidate similarity analysis methods for this purpose are experimentally compared: cosine similarity assessment in conjunction with latent semantic analysis (LSA) and normalized compression distance (NCD). The results show that the number of false positives can be reduced significantly by removing noise identified by either method. However, the experimental results also indicate subtle performance differences between LSA and NCD. To improve the performance even further and to decrease the large number of attributes, the categorical proportional difference (CPD) feature selection algorithm was applied. CPD managed to greatly reduce the number of attributes while at the same time increase classification performance on the original data set, as well as on the LSA- and NCD-based data sets.     

On game theoretic DSA-driven MAC for cognitive radio networks

The game theoretic dynamic spectrum allocation (DSA) technique is an efficient approach to coordinate cognitive radios sharing the spectrum. However, existing game based DSA algorithms lack a platform to support the game process. On the other hand, existing medium access control (MAC) protocols for cognitive radio networks do not fully utilize the adaptability and intelligence of the cognitive radio (CR) to achieve efficient spectrum utilization, let alone fairness and QoS support. Therefore it is necessary to develop DSA-driven MAC protocols with the game theoretic DSA embedded into the MAC layer. In this paper, based on the analysis of challenges for the game theoretic DSA in realistic applications, we conclude that a unified game theoretic DSA-driven MAC framework should constitute of four integral components: (1) DSA algorithm, deriving the spectrum access strategy for data communication; (2) negotiation mechanism, coordinating players to follow the right game policy; (3) clustering algorithm, limiting the negotiation within one cluster for scalability; (4) collision avoidance mechanism, eliminating collisions among clusters. With our MAC framework, DSA-driven MAC protocols can be conveniently developed, as illustrated in the design process of a concrete QoSe-DSA-driven MAC protocol. The game theoretic DSA-driven MAC framework can fulfill merits of game theoretic DSA algorithms including high spectrum utilization, collision-free channel access for data communication, QoS and fairness support. Through simulations, the merits of the DSA-driven MAC framework are demonstrated.     

An efficient cascaded method for network intrusion detection based on extreme learning machines

Machine learning techniques are widely used for network intrusion detection (NID). However, it has to face the unbalance of training samples between classes as it is hard to collect samples of some intrusion classes. This would produce false positives for these intrusion classes. Meanwhile, since there are various types of intrusions, classification boundaries between different classes are seriously nonlinear. Due to the huge amount of training data, computational efficiency is also required. This paper therefore proposes an efficient cascaded classifier for NID. This classifier consists of a collection of binary base classifiers which are serially connected. Each base classifier corresponds to a type of intrusion. The order of these base classifiers is automatically determined based on the number of false positives to cope with the unbalance of training samples. Extreme learning machine algorithm, which has low computational cost, is used to train these base classifiers to delineate the nonlinear boundaries between classes. This proposed NID method is evaluated on the KDD99 data set. Experimental results have shown that this proposed method outperforms other state-of-the-art methods including decision tree, back-propagation neural network and support vector machines.     

A Predator-prey Particle Swarm Optimization Approach to Multiple UCAV Air Combat Modeled by Dynamic Game Theory

Dynamic game theory has received considerable attention as a promising technique for formulating control actions for agents in an extended complex enterprise that involves an adversary. At each decision making step, each side seeks the best scheme with the purpose of maximizing its own objective function. In this paper, a game theoretic approach based on predatorprey particle swarm optimization (PP-PSO) is presented, and the dynamic task assignment problem for multiple unmanned combat aerial vehicles (UCAVs) in military operation is decomposed and modeled as a two-player game at each decision stage. The optimal assignment scheme of each stage is regarded as a mixed Nash equilibrium, which can be solved by using the PP-PSO. The effectiveness of our proposed methodology is verified by a typical example of an air military operation that involves two opposing forces: the attacking force Red and the defense force Blue.      

Distributed denial of service attack detection using an ensemble of neural classifier

The vulnerabilities in the Communication (TCP/IP) protocol stack and the availability of more sophisticated attack tools breed in more and more network hackers to attack the network intentionally or unintentionally, leading to Distributed Denial of Service (DDoS) attack. The DDoS attacks could be detected using the existing machine learning techniques such as neural classifiers. These classifiers lack generalization capabilities which result in less performance leading to high false positives. This paper evaluates the performance of a comprehensive set of machine learning algorithms for selecting the base classifier using the publicly available KDD Cup dataset. Based on the outcome of the experiments, Resilient Back Propagation (RBP) was chosen as base classifier for our research. The improvement in performance of the RBP classifier is the focus of this paper. Our proposed classification algorithm, RBPBoost, is achieved by combining ensemble of classifier outputs and Neyman Pearson cost minimization strategy, for final classification decision. Publicly available datasets such as KDD Cup, DARPA 1999, DARPA 2000, and CONFICKER were used for the simulation experiments. RBPBoost was trained and tested with DARPA, CONFICKER, and our own lab datasets. Detection accuracy and Cost per sample were the two metrics evaluated to analyze the performance of the RBPBoost classification algorithm. From the simulation results, it is evident that RBPBoost algorithm achieves high detection accuracy (99.4%) with fewer false alarms and outperforms the existing ensemble algorithms. RBPBoost algorithm outperforms the existing algorithms with maximum gain of 6.6% and minimum gain of 0.8%.     

Data dimensionality reduction with application to simplifying RBF network structure and improving classification performance

For high dimensional data, if no preprocessing is carried out before inputting patterns to classifiers, the computation required may be too heavy. For example, the number of hidden units of a radial basis function (RBF) neural network can be too large. This is not suitable for some practical applications due to speed and memory constraints. In many cases, some attributes are not relevant to concepts in the data at all. In this paper, we propose a novel separability-correlation measure (SCM) to rank the importance of attributes. According to the attribute ranking results, different attribute subsets are used as inputs to a classifier, such as an RBF neural network. Those attributes that increase the validation error are deemed irrelevant and are deleted. The complexity of the classifier can thus be reduced and its classification performance improved. Computer simulations show that our method for attribute importance ranking leads to smaller attribute subsets with higher accuracies compared with the existing SUD and Relief-F methods. We also propose a modified method for efficient construction of an RBF classifier. In this method we allow for large overlaps between clusters corresponding to the same class label. Our approach significantly reduces the structural complexity of the RBF network and improves the classification performance.     

Artificial immune‐based supervised classifier for land‐cover classification

This paper explores the potential of an artificial immune‐based supervised classification algorithm for land‐cover classification. This classifier is inspired by the human immune system and possesses properties similar to nonlinear classification, self/non‐self identification, and negative selection. Landsat ETM+ data of an area lying in Eastern England near the town of Littleport are used to study the performance of the artificial immune‐based classifier. A univariate decision tree and maximum likelihood classifier were used to compare its performance in terms of classification accuracy and computational cost. Results suggest that the artificial immune‐based classifier works well in comparison with the maximum likelihood and the decision‐tree classifiers in terms of classification accuracy. The computational cost using artificial immune based classifier is more than the decision tree but less than the maximum likelihood classifier. Another data set from an area in Spain is also used to compare the performance of immune based supervised classifier with maximum likelihood and decision‐tree classification algorithms. Results suggest an improved performance with the immune‐based classifier in terms of classification accuracy with this data set, too. The design of an artificial immune‐based supervised classifier requires several user‐defined parameters to be set, so this work is extended to study the effect of varying the values of six parameters on classification accuracy. Finally, a comparison with a backpropagation neural network suggests that the neural network classifier provides higher classification accuracies with both data sets, but the results are not statistically significant.     

Path Clearance

In military scenarios, agents (i.e., troops of soldiers, convoys, and unmanned vehicles) may often have to traverse environments with only a limited intelligence about the locations of adversaries. We study a particular instance of this problem that we refer to as path clearance problem. In path clearance, an agent has to navigate to its goal as quickly as possible without being detected by an adversary. When picking a path to follow, the agent does not know the precise locations of adversaries. Instead, it has a list of their possible locations, each associated with the probability of containing an adversary. Any of these locations can be sensed by either the agent itself at a distance close enough (provided the agent has a capability of long-range sensing) or by one of the scouts (if they are available). If no adversary is present at a sensed location, the agent can then safely traverse through it. Otherwise, the agent has to take a detour.