SONIC: streaming overlapping community detection

A community within a graph can be broadly defined as a set of vertices that exhibit high cohesiveness (relatively high number of edges within the set) and low conductance (relatively low number of edges leaving the set). Community detection is a fundamental graph processing analytic that can be applied to several application domains, including social networks. In this context, communities are often overlapping, as a person can be involved in more than one community (e.g., friends, and family); and evolving, since the structure of the network changes. We address the problem of streaming overlapping community detection, where the goal is to maintain communities in the presence of streaming updates. This way, the communities can be updated more efficiently. To this end, we introduce SONIC—a find-and-merge type of community detection algorithm that can efficiently handle streaming updates. SONIC first detects when graph updates yield significant community changes. Upon the detection, it updates the communities via an incremental merge procedure. The SONIC algorithm incorporates two additional techniques to speed-up the incremental merge; min-hashing and inverted indexes. Results show that SONIC can provide high quality overlapping communities, while handling streaming updates several orders of magnitude faster than the alternatives performing from-scratch computation.     

Evading stepping-stone detection under the cloak of streaming media with SNEAK

Network-based intrusions have become a serious threat to the users of the Internet. To help cover their tracks, attackers launch attacks from a series of previously compromised systems called stepping stones. Timing correlations on incoming and outgoing packets can lead to detection of the stepping stone and can be used to trace the attacker through each link. Prior work has sought to counter the possibility of the attacker employing chaff packets and randomized delays. To date, however, researchers have not accounted for the full range of techniques that a sophisticated attacker could apply. In this work, we show that such an attacker could avoid detection by the best known stepping-stone detection methods. We propose a simple buffering technique that could be used by an attacker on a stepping stone to evade detection. This technique makes the timing of packets in the output flow of the stepping stone entirely independent of the timing of packets from the input flow, thereby eliminating the timing link that makes existing stepping-stone detection methods possible. To accomplish this, we only require buffering at the stepping stone and enough chaff packets to generate a constant-rate flow. This traffic has the characteristics of a multimedia stream, such as Voice over IP (VoIP), which is quite common on the Internet today. To test the effectiveness of our technique, we implemented it in a prototype stepping-stone application and tested its performance on the DETER testbed and the PlanetLab testbed. Our prototype successfully evades watermark-based detection and provides reasonable performance for shell commands over at least three stepping stones.     

基于Linux的RTP流检测识别算法研究

针对流媒体在网络转发环节识别准确率不高、转发速度慢的问题,通过对RTP协议包头的分析,提出了基于RTP协议“流特征”的分析、阈值判定和缓存回收相结合的优化算法,并在Linux系统内核的Netfilter框架下实现了RTP流的自动检测识别和快速转发.实验结果表明,与传统的RTP流识别算法相比,该算法提高了RTP流识别的准确率和容错性能,显著减少了RTP协议转发延迟,使RTP流的检测识别效率明显提高.     

Interactive collision detection for deformable models using streaming AABBs

We present an interactive and accurate collision detection algorithm for deformable, polygonal objects based on the streaming computational model. Our algorithm can detect all possible pairwise primitive-level intersections between two severely deforming models at highly interactive rates. In our streaming computational model, we consider a set of axis aligned bounding boxes (AABBs) that bound each of the given deformable objects as an input stream and perform massively-parallel pairwise, overlapping tests onto the incoming streams. As a result, we are able to prevent performance stalls in the streaming pipeline that can be caused by expensive indexing mechanism required by bounding volume hierarchy-based streaming algorithms. At runtime, as the underlying models deform over time, we employ a novel, streaming algorithm to update the geometric changes in the AABB streams. Moreover, in order to get only the computed result (i.e., collision results between AABBs) without reading back the entire output streams, we propose a streaming en/decoding strategy that can be performed in a hierarchical fashion. After determining overlapped AABBs, we perform a primitive-level (e.g., triangle) intersection checking on a serial computational model such as CPUs. We implemented the entire pipeline of our algorithm using off-the-shelf graphics processors (GPUs), such as nVIDIA GeForce 7800 GTX, for streaming computations, and Intel Dual Core 3.4G processors for serial computations. We benchmarked our algorithm with different models of varying complexities, ranging from 15K up to 50K triangles, under various deformation motions, and the timings were obtained as 30 approximately 100 FPS depending on the complexity of models and their relative configurations. Finally, we made comparisons with a well-known GPU-based collision detection algorithm, CULLIDE [4] and observed about three times performance improvement over the earlier approach. We also made comparisons with a SW-based AABB culling algorithm [2] and observed about two times improvement.     

Human-machine interactive streaming anomaly detection by online self-adaptive forest

Anomaly detectors are used to distinguish differences between normal and abnormal data, which are usually implemented by evaluating and ranking the anomaly scores of each instance. A static unsupervised streaming anomaly detector is difficult to dynamically adjust anomaly score calculation. In real scenarios, anomaly detection often needs to be regulated by human feedback, which benefits adjusting anomaly detectors. In this paper, we propose a human-machine interactive streaming anomaly detection method, named ISPForest, which can be adaptively updated online under the guidance of human feedback. In particular, the feedback will be used to adjust the anomaly score calculation and structure of the detector, ideally attaining more accurate anomaly scores in the future. Our main contribution is to improve the tree-based streaming anomaly detection model that can be updated online from perspectives of anomaly score calculation and model structure. Our approach is instantiated for the powerful class of tree-based streaming anomaly detectors, and we conduct experiments on a range of benchmark datasets. The results demonstrate that the utility of incorporating feedback can improve the performance of anomaly detectors with a few human efforts.     

Identification with stochastic sampling time jitter

This work investigates how stochastic sampling jitter noise affects the result of system identification, and proposes a modification of known approaches to mitigate the effects of sampling jitter, when the jitter is unknown and not directly measurable. By just assuming conventional additive measurement noise, the analysis shows that the identified model will get a bias in the transfer function amplitude that increases for higher frequencies. A frequency domain approach with a continuous-time model allows an analysis framework for sampling jitter noise. The bias and covariance in the frequency domain model are derived. These are used in bias compensated (weighted) least squares algorithms, and by asymptotic arguments this leads to a maximum likelihood algorithm. Continuous-time output error models are used for numerical illustrations.     

Multimedia event detection with multimodal feature fusion and temporal concept localization

We present a system for multimedia event detection. The developed system characterizes complex multimedia events based on a large array of multimodal features, and classifies unseen videos by effectively fusing diverse responses. We present three major technical innovations. First, we explore novel visual and audio features across multiple semantic granularities, including building, often in an unsupervised manner, mid-level and high-level features upon low-level features to enable semantic understanding. Second, we show a novel Latent SVM model which learns and localizes discriminative high-level concepts in cluttered video sequences. In addition to improving detection accuracy beyond existing approaches, it enables a unique summary for every retrieval by its use of high-level concepts and temporal evidence localization. The resulting summary provides some transparency into why the system classified the video as it did. Finally, we present novel fusion learning algorithms and our methodology to improve fusion learning under limited training data condition. Thorough evaluation on a large TRECVID MED 2011 dataset showcases the benefits of the presented system.     

一种基于android轻型网关敏感数据泄露检测模型

针对智慧家居控制系统中基于android系统轻型网关的敏感数据泄露问题,提出了一种基于android本地库层污点传播和应用层控制的分层互连检测模型。通过在IPC Binder通信时标记污点,在待测应用进程调用本地网络套接字函数时检测污点,分析污点传播路径并计算泄露指数,实现对敏感数据泄露的跟踪检测。实验表明该模型能够检测出各个敏感数据源以明文或密文方式的数据泄露,准确率达到93%以上,同时性能开销不超过1%,从而实现对Android轻型网关敏感数据泄露的有效检测,实用性强,并为之后相关研究提供了新方向。     

Sampling streaming data with replacement

Simple random sampling is a widely accepted basis for estimation from a population. When data come as a stream, the total population size continuously grows and only one pass through the data is possible. Reservoir sampling is a method of maintaining a fixed size random sample from streaming data. Reservoir sampling without replacement has been extensively studied and several algorithms with sub-linear time complexity exist. Although reservoir sampling with replacement is previously mentioned by some authors, it has been studied very little and only linear algorithms exist. A with-replacement reservoir sampling algorithm of sub-linear time complexity is introduced. A thorough complexity analysis of several approaches to the with-replacement reservoir sampling problem is also provided.     

基于前—后向光流点匹配运动熵的视频抖动检测算法

目前大部分视频监控系统面临着高效实时性智能分析与低效滞后的人工故障排查的矛盾。视频质量智能诊断系统可以为此提供有效的解决方案。针对视频质量诊断系统中的画面抖动异常检测问题,提出一种简单有效的实用算法。该算法通过有效融合图像的稀疏光流与特征点匹配算法,根据前向-后向误差标准估计图像帧的全局运动参数,引入连续帧的运动熵用于衡量视频画面片段运动的混乱程度,判断是否存在视频抖动现象。算法在不同分辨率的实际监控录像数据集上进行了测试和比较。实验证明,该算法在一定程度上克服了大位移抖动的影响,具备良好的实时特性以及较高的检测精度,能够满足实际工作的需求。     

On the reliable detection of concept drift from streaming unlabeled data

Classifiers deployed in the real world operate in a dynamic environment, where the data distribution can change over time. These changes, referred to as concept drift, can cause the predictive performance of the classifier to drop over time, thereby making it obsolete. To be of any real use, these classifiers need to detect drifts and be able to adapt to them, over time. Detecting drifts has traditionally been approached as a supervised task, with labeled data constantly being used for validating the learned model. Although effective in detecting drifts, these techniques are impractical, as labeling is a difficult, costly and time consuming activity. On the other hand, unsupervised change detection techniques are unreliable, as they produce a large number of false alarms. The inefficacy of the unsupervised techniques stems from the exclusion of the characteristics of the learned classifier, from the detection process. In this paper, we propose the Margin Density Drift Detection (MD3) algorithm, which tracks the number of samples in the uncertainty region of a classifier, as a metric to detect drift. The MD3 algorithm is a distribution independent, application independent, model independent, unsupervised and incremental algorithm for reliably detecting drifts from data streams. Experimental evaluation on 6 drift induced datasets and 4 additional datasets from the cybersecurity domain demonstrates that the MD3 approach can reliably detect drifts, with significantly fewer false alarms compared to unsupervised feature based drift detectors. At the same time, it produces performance comparable to that of a fully labeled drift detector. The reduced false alarms enables the signaling of drifts only when they are most likely to affect classification performance. As such, the MD3 approach leads to a detection scheme which is credible, label efficient and general in its applicability.     

The effects of aperture jitter and clock jitter in wideband ADCs

Designing leading-edge systems (e.g., communication systems) requires knowledge about the technological limits. Jitter is the limiting effect in wideband ADCs with a digitization bandwidth between 1 MHz and 1 GHz. The effects of aperture jitter and clock jitter have been investigated previously. However, some very important aspects are still missing, in particular investigations on the spectral distribution of the jitter induced error. This gap is filled by this article.     

Anomaly detection in streaming environmental sensor data: A data-driven modeling approach

The deployment of environmental sensors has generated an interest in real-time applications of the data they collect. This research develops a real-time anomaly detection method for environmental data streams that can be used to identify data that deviate from historical patterns. The method is based on an autoregressive data-driven model of the data stream and its corresponding prediction interval. It performs fast, incremental evaluation of data as it becomes available, scales to large quantities of data, and requires no pre-classification of anomalies. Furthermore, this method can be easily deployed on a large heterogeneous sensor network. Sixteen instantiations of this method are compared based on their ability to identify measurement errors in a windspeed data stream from Corpus Christi, Texas. The results indicate that a multilayer perceptron model of the data stream, coupled with replacement of anomalous data points, performs well at identifying erroneous data in this data stream.     

SDH设备抖动测试

传输设备经历了几代更新,已逐步完成了模拟设备到PDH设备和SDH设备的过渡。SDH有许多PDH设备所不能比拟的优点,但也存在一些缺陷,比如指针调整引起的抖动。由于传输设备的抖动对通信质量至关重要,文中通过理论分析,结合实际测试,对传输设备工程验收中抖动指标的测量进行了详细的论述。     

Approximate models for continuous-time linear systems with sampling jitter

The behaviour of single input, single output, continuous time systems sampled with various types of jitter in both measurement and control action is investigated. It is shown that the effects of jitter can be modelled by approximations for the plant dynamics, and additive noise constructed by the modulation of plant signals with the jitter. These approximations give useful insights for digital controller design.     

具有网关功能的矿用本安传输分站设计

针对传统矿用传输分站存在执行协议单一、通信接口单一的问题,设计了一种具有网关功能的矿用本安传输分站,详细介绍了该分站的硬件和软件设计。该传输分站采用分布式结构,具有多种通信接口,通信端口可以自由定义协议类型、自由编辑数据地址、自由共享网关中数据,具有数据采集、数据融合和数据传输等功能。试验结果表明,该分站兼具网关和分站的作用,实现了监控现场多设备的无缝兼容和松耦合,具有很高的工程实用价值。