Detecting Insider Threats: Solutions and Trends

ABSTRACT

Insider threats pose significant challenges to any organization. Many solutions have been proposed in the past to detect insider threats. Unfortunately, given the complexity of the problem and the human factors involved, many solutions which have been proposed face strict constraints and limitations when it comes to the working environment. As a result, many past insider threat solutions have in practice failed in their implementations. In this work, we review some of the recent insider threat detection solutions and explore their benefits and limitations. We also discuss insider threat issues for emerging areas such as cloud computing, virtualization, and social networking.     

Detecting Holes and Antiholes in Graphs

In this paper we study the problems of detecting holes and antiholes in general undirected graphs, and we present algorithms for these problems. For an input graph G on n vertices and m edges, our algorithms run in O(n + m²) time and require O(n m) space; we thus provide a solution to the open problem posed by Hayward et al. asking for an O(n⁴)-time algorithm for finding holes in arbitrary graphs. The key element of the algorithms is the use of the depth-first-search traversal on appropriate auxiliary graphs in which moving between any two adjacent vertices is equivalent to walking along a P₄ (i.e., a chordless path on four vertices) of the input graph or on its complement, respectively. The approach can be generalized so that for a fixed constant k ≥ 5 we obtain an O(n^k-1)-time algorithm for the detection of a hole (antihole resp.) on at least k vertices. Additionally, we describe a different approach which allows us to detect antiholes in graphs that do not contain chordless cycles on five vertices in O(n + m²) time requiring O(n + m) space. Again, for a fixed constant k ≥ 6, the approach can be extended to yield O(n^k-2)-time and O(n²)-space algorithms for detecting holes (antiholes resp.) on at least k vertices in graphs which do not contain holes (antiholes resp.) on k - 1 vertices. Our algorithms are simple and can be easily used in practice. Finally, we also show how our detection algorithms can be augmented so that they return a hole or an antihole whenever such a structure is detected in the input graph; the augmentation takes O(n + m) time and space.     

Embedding Complete Binary Trees into Star and Pancake Graphs

Let G and H be two simple undirected graphs. An embedding of the graph G into the graph H is an injective mapping f from the vertices of G to the vertices of H . The dilation of the embedding is the maximum distance between f(u),f(v) taken over all edges (u,v) of G . We give a construction of embeddings of dilation 1 of complete binary trees into star graphs. The height of the trees embedded with dilation 1 into the n -dimensional star graph is Ω (n log n) , which is asymptotically optimal. Constructions of embeddings of complete binary trees of dilation 2δ and 2δ +1 , δ≥ 1, into star graphs are given. The use of larger dilation allows embeddings of trees of greater height into star graphs. It is shown that all these constructions can be modified to yield embeddings of dilation 1 and 2δ , δ≥ 1 , of complete binary trees into pancake graphs. Received February 1996, and in final form October 1997.     

Embeddings of Star Graphs into Optical Meshes without Bends

We show an embedding of the star graph into a rectangular optical multichannel mesh ofddimensions such that the embedding has no bends; that is, neighbors in the star graph always differ in exactly one coordinate in the mesh, to facilitate one-hop optical communication. To embed ann-star, the mesh can have any number of dimensionsdbetween 1 andn− 1. The embedding has load 1 and an expansion of at mostn^{d − 1}/d!. The size of the mesh will be at most We optimize the size of the host mesh using clique-partitioning to produce embeddings with expansions as low as unity. In two dimensions, for evenn, the mesh will be no larger thann×n(n− 2)!, and have an expansion of no more than 1 1/(n− 1). Further, we show how we can use a contraction method to efficiently embed the star graph into an optical mesh with near-unity aspect ratios. Contraction on a two-dimensional embedding will yield a mesh of size no larger thann×nfor evennwith a load of (n− 2)!.     

Detecting Fixed Patterns in Chordal Graphs in Polynomial Time

The Contractibility problem takes as input two graphs G and H, and the task is to decide whether H can be obtained from G by a sequence of edge contractions. The Induced Minor and Induced Topological Minor problems are similar, but the first allows both edge contractions and vertex deletions, whereas the latter allows only vertex deletions and vertex dissolutions. All three problems are NP-complete, even for certain fixed graphs H. We show that these problems can be solved in polynomial time for every fixed H when the input graph G is chordal. Our results can be considered tight, since these problems are known to be W[1]-hard on chordal graphs when parameterized by the size of H. To solve Contractibility and Induced Minor, we define and use a generalization of the classic Disjoint Paths problem, where we require the vertices of each of the k paths to be chosen from a specified set. We prove that this variant is NP-complete even when k=2, but that it is polynomial-time solvable on chordal graphs for every fixed k. Our algorithm for Induced Topological Minor is based on another generalization of Disjoint Paths called Induced Disjoint Paths, where the vertices from different paths may no longer be adjacent. We show that this problem, which is known to be NP-complete when k=2, can be solved in polynomial time on chordal graphs even when k is part of the input. Our results fit into the general framework of graph containment problems, where the aim is to decide whether a graph can be modified into another graph by a sequence of specified graph operations. Allowing combinations of the four well-known operations edge deletion, edge contraction, vertex deletion, and vertex dissolution results in the following ten containment relations: (induced) minor, (induced) topological minor, (induced) subgraph, (induced) spanning subgraph, dissolution, and contraction. Our results, combined with existing results, settle the complexity of each of the ten corresponding containment problems on chordal graphs.     

Packet Routing and PRAM Emulation on Star Graphs and Leveled Networks

We consider the problem of permutation routing on a star graph, an interconnection network which has better properties than the hypercube. In particular, its degree and diameter are sublogarithmic in the network size. We present optimal randomized routing algorithms that run in O(D) steps (where D is the network diameter) for the worst-case input with high probability. We also show that for the n-way shuffle network with N = nⁿ nodes, there exists a randomized routing algorithm which runs in O(n) time with high probability. Another contribution of this paper is a universal randomized routing algorithm that could do optimal routing for a large class of networks (called leveled networks) which includes the star graph. The associative analysis is also network-independent. In addition, we present a deterministic routing algorithm, for the star graph, which is near optimal. All the algorithms we give are oblivious. As an application of our routing algorithms, we also show how to emulate a PRAM optimally on this class of networks.     

一种面向加权双向图的聚类发掘方法

加权双向图是一种表达具有连接关系的科学和工程问题中的信息的比较准确的方式,加权双向图上聚类发掘的研究具有重要意义.本文提出一种面向加权双向图的聚类发掘方法,它通过定义双向边的调整权和节点的调整度,充分利用加权双向图上边的权值信息和方向信息,比较准确地描述了节点对之间的结构相似性,从而比较好地实现了加权双向图上的聚类发掘.对比实验表明本文方法的聚类发掘结果在聚类质量评价指标上具有更好的表现.     

A Formal Methodology for Detecting Managerial Vulnerabilities and Threats in an Enterprise Information System

From information security point of view, an enterprise is considered as a collection of assets and their interrelationships. These interrelationships may be built into the enterprise information infrastructure, as in the case of connection of hardware elements in network architecture, or in the installation of software or in the information assets. As a result, access to one element may enable access to another if they are connected. An enterprise may specify conditions on the access of certain assets in certain mode (read, write etc.) as policies. The interconnection of assets, along with specified policies, may lead to managerial vulnerabilities in the enterprise information system. These vulnerabilities, if exploited by threats, may cause disruption to the normal functioning of information systems. This paper presents a formal methodology for detection of managerial vulnerabilities of, and threats to, enterprise information systems in linear time.     

E-Passport Threats

The International Civil Aviation Organization (ICAO) standardized e-passports by specifying how to implement and protect machine-readable travel documents. E-passports have embedded contactless chips that can be read by radio from tip to a few centimeters away. The ICAO chose this technology over magnetic strips and 2D barcodes because it provides reliable connection, large memory capacity, random access, and rewritable memory. As with many other RFID devices, the chip in e-passports uses a 32-bit number for collision avoidance. Every country maintains its own public-key infrastructure (PKI) and exchanges root certificates with other countries via diplomatic means. Agencies issuing e-passports have their own public keys and certificates from the PKI. In this way, a passive authentication mechanism verifies every data group's digest. With today's e-passports, private information is limited to the MRZ and a digital picture, but the goal is to eventually add more biometrics at some point, along with a digitized handwritten signature.     

静态威胁下的无人机航迹规划

无人机（Uninhabited Air Vehicle,UAV）由于其自身优点,已经在军事以及民用领域取得广泛使用。无人机的航迹规划本质可归结为一个多目标多约束条件的最优化问题。简单介绍无人机航迹规划的基本理论。运用神经网络算法针对静态环境下的火力威胁和非火力分别建模。运用遗传算法对无人机进行航迹规划。通过建立不同环境的模型仿真验证算法的优越性。     

浅谈WLAN的安全威胁及对策

随着计算机无线网络的不断发展和普及,无线网络满足了人们实现移动办公的梦想,为用户创造了一个丰富多彩的自由天空,让人能够真正体会到网络无处不在的奇妙感觉。但随之而来的网络安全问题也越来越突出,文章重点介绍了无线局域网WLAN安全现状与防御对策。     

Star Walk

虽然这年头看到满天繁星的几率比中彩票还低,但这并不妨碍我们对浪漫星空的热烈向往,试想—下,你和心爱的妹子在夜晚的海滩上,或者草地上,或者山峦上,或者……好吧,在什么地方不重要,重点是和妹子在一起,而且头上有数不清的星星。这个时候,你想不想云淡风轻地告诉妹子：呐,这里是你的星座,这是我的,我们可以让它们在一起……     

Information Security Threats and Practices in Small Businesses

This article focuses on how small businesses (fewer than 500 employees) are managing information security and the associated risks. Our findings indicate that the businesses interviewed for this study are taking many of the typical steps that are indicative of best security practices. However, there are also several areas of concern that could potentially leave their systems open to threats.     

从一国的综合角度看,信息时代存在哪些威胁?

信息技术这一人类历史上的又一次重大革命使世界发生了彻底的改变,大家顿感“忽如一夜春风来”。我们欣喜于万象更新的同时,却也看到了多种驱动力撞击而使IT界产生的某种无序。更深感在信息安全领域,很多人还怀有一些片面或错误的认识(比如笔者曾见到过某单位采购人员去购买防火墙时只问哪一种最便宜)。因此加强信息安全的教育普及也是信息安全工作者面临的一项迫切任务。在此,我们介绍美国政府的国家信息系统保护计划中对信息安全威胁的阐述,使公众对于信息安全面临的各类威胁有系统的认识,明确地理解这些威胁对我们的不同危害程度。我们希望,读者在阅读完文章后不再谈黑客色变,更不要再把黑客同信息安全问     

基于主星对的星图识别算法

星图识别是星敏感器确定卫星姿态的关键技术。在传统三角形识别算法的基础上,将星图中最亮的两颗星作为主星对,其它星作为辅助导航星,引入星对相对星等差信息,通过对主星对的识别提高识别速度,采用以主星对为公共边的多三角形模式匹配提高识别精度。并提出了一种将星对表拟合成曲线函数实现快速角距匹配的方法。微机模拟实验结果表明该算法的识别率和识别速度均优于传统的三角形法。     

Recognizing d-Interval Graphs and d-Track Interval Graphs

A d-interval is the union of d disjoint intervals on the real line. A d-track interval is the union of d disjoint intervals on d disjoint parallel lines called tracks, one interval on each track. As generalizations of the ubiquitous interval graphs, d-interval graphs and d-track interval graphs have wide applications, traditionally to scheduling and resource allocation, and more recently to bioinformatics. In this paper, we prove that recognizing d-track interval graphs is NP-complete for any constant d≥2. This confirms a conjecture of Gyárfás and West in 1995. Previously only the complexity of the case d=2 was known. Our proof in fact implies that several restricted variants of this graph recognition problem, i.e., recognizing balanced d-track interval graphs, unit d-track interval graphs, and (2,…,2) d-track interval graphs, are all NP-complete. This partially answers another question recently raised by Gambette and Vialette. We also prove that recognizing depth-two 2-track interval graphs is NP-complete, even for the unit case. In sharp contrast, we present a simple linear-time algorithm for recognizing depth-two unit d-interval graphs. These and other results of ours give partial answers to a question of West and Shmoys in 1984 and a similar question of Gyárfás and West in 1995. Finally, we give the first bounds on the track number and the unit track number of a graph in terms of the number of vertices, the number of edges, and the maximum degree, and link the two numbers to the classical concepts of arboricity.     

无线局域网安全威胁及解决方法

随着无线通信技术的不断发展,无线网络已经得以广泛使用,同时无限局域网的安全缺陷也快速地体现出来,这对无线网络的应用产生了一定的阻碍。由此对无限局域网的安全性提出了更高的要求。本文针对无线局域网络使用中出现的主要安全威胁提出相应的解决方案。