检索结果-内蒙古大学图书馆

30th International Conference on the Theory and Application of Cryptology and Information Security

作者： Filic, Mia Kocher, Keran Kummer, Ella Unnikrishnan, Anupama Swiss Fed Inst Technol Zurich Switzerland

ISBN: (纸本)9789819608935;9789819608942

probabilistic data structures (PDS) are compact representations of high-volume data that provide approximate answers to queries about the data. They are commonplace in today's computing systems, finding use in databases, networking and more. While PDS are designed to perform well under benign inputs, they are frequently used in applications where inputs may be adversarially chosen. This may lead to a violation of their expected behaviour, for example an increase in false positive rate. In this work, we focus on PDS that handle approximate membership queries (AMQ). We consider adversarial users with the capability of making adaptive insertions, deletions and membership queries to AMQ-PDS, and analyse the performance of AMQ-PDS under such adversarial inputs. We argue that deletions significantly empower adversaries, presenting a challenge to enforcing honest behaviour when compared to insertion-only AMQ-PDS. To address this, we introduce a new concept of an honest setting for AMQ-PDS with deletions. By leveraging simulation-based security definitions, we then quantify how much harm can be caused by adversarial users to the functionality of AMQ-PDS. Our resulting bounds only require calculating the maximal false positive probability and insertion failure probability achievable in our novel honest setting. We apply our results to Cuckoo filters and Counting filters. We show how to protect these AMQ-PDS at low cost, by replacing or composing the hash functions with keyed pseudorandom functions in their construction. This strategy involves establishing practical bounds for the probabilities mentioned above. Using our new techniques, we demonstrate that achieving security against adversarial users making both insertions and deletions remains practical.

关键词： probabilistic data structures Counting filters Cuckoo filters security simulation-based proofs

来源：评论

学校读者我要写书评

暂无评论

Automated Expected Amortised Cost Analysis of probabilistic data structures 34th

Automated Expected Amortised Cost Analysis of Probabilistic ...

引用

34th International Conference on Computer-Aided Verification (CAV) held as part of the Federated Logic Conference (FLoC)

作者： Leutgeb, Lorenz Moser, Georg Zuleger, Florian Max Planck Inst Informat Saarland Informat Campus Saarbrucken Germany Grad Sch Comp Sci Saarland Informat Campus Saarbrucken Germany Univ Innsbruck Dept Comp Sci Innsbruck Austria Tech Univ Wien Inst Log & Computat 192 4 Vienna Austria

ISBN: (纸本)9783031131882;9783031131875

In this paper, we present the first fully-automated expected amortised cost analysis of self-adjusting data structures, that is, of randomised splay trees, randomised splay heaps and randomised meldable heaps, which so far have only (semi-)manually been analysed in the literature. Our analysis is stated as a type-and-effect system for a first-order functional programming language with support for sampling over discrete distributions, non-deterministic choice and a ticking operator. The latter allows for the specification of fine-grained cost models. We state two soundness theorems based on two different-but strongly related-typing rules of ticking, which account differently for the cost of non-terminating computations. Finally we provide a prototype implementation able to fully automatically analyse the aforementioned case studies.

关键词： amortised cost analysis functional programming probabilistic data structures automation constraint solving

来源：评论

学校读者我要写书评

暂无评论

A probabilistic data structures-Based Anomaly Detection Scheme for Software-Defined Internet of Vehicles

引用

IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS 2021年第6期22卷 3557-3566页

作者： Garg, Sahil Singh, Amritpal Aujla, Gagangeet Singh Kaur, Sukhdeep Batra, Shalini Kumar, Neeraj Univ Quebec Elect Engn Dept Ecole Technol Super Montreal PQ H3C 1K3 Canada Natl Inst Technol Comp Sci & Engn Dept Jalandhar 144805 Punjab India Newcastle Univ Sch Comp Newcastle Upon Tyne NE4 5TG Tyne & Wear England Chandigarh Univ Comp Sci & Engn Dept Mohali 140413 India Thapar Inst Engn & Technol Patiala 147001 Punjab India Asia Univ Dept Comp Sci & Informat Engn Taichung 41354 Taiwan King Abdulaziz Univ Jeddah 21589 Saudi Arabia

Internet of Vehicles (IoV) has escalated the movement of big data across moving vehicles which create a huge burden on the network infrastructure. In IoV environment, effective handling of streaming data has to face various challenges like;traffic monitoring, flow management, re-configuration and security. Software-defined networks (SDN) provides improved flexibility, and centralized control of the network to overcome (almost) the above-mentioned challenges. However, it can lead to an easy target (node or controller) for malicious agents. So, to detect the anomalous behaviour of the nodes in the IoV environment, a hybrid approach using probabilistic data structures is proposed which works in the following phases. In phase I, a traffic monitoring scheme using Count-Min-Sketch is designed to identify the suspicious nodes. In phase II, to detect an anomaly, a Bloom filter-based control scheme is used for signature verification of suspicious nodes. In phase III, a Quotient filter is used for fast and efficient storage of malicious nodes. In phase IV, to detect the super points (malicious hosts that are connected to a large number of destinations), a Hyperloglog counter is used to measure the cardinality of each flow passing through the switches. The proposed scheme has been evaluated in a simulated environment. The results obtained depict that the proposed scheme is faster, accurate, and efficient concerning detection ratio and false-positive ratio.

关键词： Monitoring probabilistic logic Internet Control systems Denial-of-service attack Anomaly detection Anomaly detection probabilistic data structures Software-defined networks Internet of Vehicles

来源：评论

学校读者我要写书评

暂无评论

probabilistic data structures for big data analytics: A comprehensive review

引用

KNOWLEDGE-BASED SYSTEMS 2020年 188卷 104987-104987页

作者： Singh, Amritpal Garg, Sahil Kaur, Ravneet Batra, Shalini Kumar, Neeraj Zomaya, Albert Y. Deemed Univ Thapar Inst Engn & Technol Comp Sci & Engn Dept Patiala Punjab India Univ Sydney Ctr Distributed & High Performance Comp Sydney NSW Australia

An exponential increase in the data generation resources is widely observed in last decade, because of evolution in technologies such as-cloud computing, IoT, social networking, etc. This enormous and unlimited growth of data has led to a paradigm shift in storage and retrieval patterns from traditional data structures to probabilistic data structures (PDS). PDS are a group of data structures that are extremely useful for Big data and streaming applications in order to avoid high-latency analytical processes. These data structures use hash functions to compactly represent a set of items in stream-based computing while providing approximations with error bounds so that well-formed approximations get built into data collections directly. Compared to traditional data structures, PDS use much less memory and constant time in processing complex queries. This paper provides a detailed discussion of various issues which are normally encountered in massive data sets such as-storage, retrieval, query,etc. Further, role of PDS in solving these issues is also discussed where these data structures are used as temporary accumulators in query processing. Several variants of existing PDS along with their application areas have also been explored which give a holistic view of domains where these data structures can be applied for efficient storage and retrieval of massive data sets. Mathematical proofs of various parameters considered in the PDS have also been discussed in the paper. Moreover, the relative comparison of various PDS with respect to various parameters is also explored. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Big data Internet of things (IoT) probabilistic data structures Bloom filter Quotient filter Count min sketch HyperLogLog counter MM-hash Locality sensitive hashing

来源：评论

学校读者我要写书评

暂无评论

ProIDS: probabilistic data structures based Intrusion Detection System for Network Traffic Monitoring

<i>ProIDS</i>: Probabilistic Data Structures based Intrusion...

引用

IEEE Global Telecommunications Conference (GLOBECOM)

作者： Gupta, Divya Garg, Sahil Singh, Amritpal Batra, Shalini Kumar, Neeraj Obaidat, M. S. Thapar Univ Comp Sci & Engn Dept Patiala Punjab India Univ Jordan King Abdullah Sch Informat Technol Amman Jordan

ISBN: (纸本)9781509050192

Internet is an integrated platform where the data is growing at an exponential rate. Since it incorporates numerous business and personal services, we need to protect the data from illegal access or modifications. In literature, a large number of techniques have been proposed to protect the data against the malicious intent of the intruders. However, one of the most important way for monitoring and analyzing network traffic against various attacks is by the deployment of Intrusion detection systems (IDS). This paper presents a novel IDS based on probabilistic data structures named as ProIDS. In the proposed ProIDS, a popular probabilistic data structure (PDS), Bloom filter has been used to store the information about the suspicious nodes. Using Bloom filter, the number of hits on suspicious nodes per unit time has been computed using the modified version of Count min sketch, i.e., MCMS, a PDS. The work also presents a detailed theoretical analysis backed by relevant technical description. Simulation results clearly depict that the proposed system is more reliable and scalable in comparison to the existing Count-min sketch method. The results obtained show that proposed system requires comparatively less computational time and storage in comparison to the existing Count-min sketch method.

关键词： probabilistic data structures Bloom filter Count-min sketch Intrusion detection Network security

来源：评论

学校读者我要写书评

暂无评论

LSM tree read-deletion operations optimization through the implementation of cuckoo filters

引用

JOURNAL OF BIG data 2025年第1期12卷 1-20页

作者： Valverde, Humberto Cesar Villalta Kim, Kwangsik Kim, Kisu Kwon, Jinman Lim, Jaechoon Jun, Yongjoo Dtonic Seongnam 13591 Gyeonggido South Korea

This study aims to develop an LSM tree that uses two different kinds of probabilistic data structures (PDS). These two data structures are the Bloom Filters and the state-of-the-art Cuckoo Filter released in 2014 by Fan. Cuckoo filters are a perfect choice for saving space and also for deleting keys that are not needed in the algorithm so the filters are synchronized with the keys of all the SSTables. The implementation in this study of Cuckoo filters showed three main advantages (1) Keys that are deleted in the SSTables are immediately reflected in the Cuckoo Filters (2) When SSTables are merged, Cuckoo Filters are also merged by measuring its load factor for availability (3) The performance of Cuckoo Filters compared to Bloom filters after deleting and query shows better performance despite that cuckoo filters are also being updated. This approach is expected to reduce storage space and the amount of time for queries and deletions on the overall data structure. This new optimized LSM tree is expected to be implemented in HBase as future work to check its performance with a real-world database for more empirical results.

关键词： probabilistic data structures Indexing algorithms Query optimization Cuckoo filters Bloom filters

来源：评论

学校读者我要写书评

暂无评论

A Case for Partitioned Bloom Filters

引用

IEEE TRANSACTIONS ON COMPUTERS 2023年第6期72卷 1681-1691页

作者： Almeida, Paulo Sergio INESC TEC P-4200465 Porto Portugal Univ Minho P-4710057 Braga Portugal

In a partitioned Bloom Filter (PBF) the bit vector is split into disjoint parts, one per hash function. Contrary to hardware designs, where they prevail, software implementations mostly ignore PBFs, considering them worse than standard Bloom filters (SBF), due to the slightly larger false positive rate (FPR). In this paper, by performing an in-depth analysis, first we show that the FPR advantage of SBFs is smaller than thought;more importantly, by deriving the per-element FPR, we show that SBFs have weak spots in the domain: elements that test as false positives much more frequently than expected. This is relevant in scenarios where an element is tested against many filters. Moreover, SBFs are prone to exhibit extremely weak spots if naive double hashing is used, something occurring in mainstream libraries. PBFs exhibit a uniform distribution of the FPR over the domain, with no weak spots, even using naive double hashing. Finally, we survey scenarios beyond set membership testing, identifying many advantages of having disjoint parts, in designs using SIMD techniques, for filter size reduction, test of set disjointness, and duplicate detection in streams. PBFs are better, and should replace SBFs, in general purpose libraries and as the base for novel designs.

关键词： Standards Hash functions Proposals Indexes Hardware Testing Libraries Information filtering partitioned bloom filters probabilistic data structures

来源：评论

学校读者我要写书评

暂无评论

EPMDroid: Efficient and privacy-preserving malware detection based on SGX through data fusion

引用

INFORMATION FUSION 2022年 82卷 43-57页

作者： Wei, Wentao Wang, Jie Yan, Zheng Ding, Wenxiu Xidian Univ Sch Cyber Engn State Key Lab Integrated Serv Networks Xian Peoples R China Aalto Univ Dept Commun & Networking Espoo Finland

Android has stood at a predominant position in mobile operating systems for many years. However, its popularity and openness make it a desirable target of malicious attackers. There is an increasing need for mobile malware detection. Existing analysis methods fall into two categories, i.e., static analysis and dynamic analysis. The dynamic analysis is more effective and timely than the static one, but it incurs a high computational overhead, thus cannot be deployed in resource-constrained mobile devices. Existing studies solve this issue by outsourcing malware detection to the cloud. However, the privacy of mobile app runtime data uploaded to the cloud is not well preserved during both detection model training and malware detection. Numerous efforts have been made to preserve privacy with cryptography, which suffers from high computational overhead and low flexibility. To address these issues, in this paper, we propose an Intel SGXempowered mobile malware detection scheme called EPMDroid. We also design a probabilistic data structure based on cuckoo filters, named CuckooTable, to effectively fuse features for detection and achieve high space efficiency. We conduct both theoretical analysis and real-world data based tests on EPMDroid performance. Experimental results show that EPMDroid can speed up malware detection by up to 43.8 times and save memory space by up to 3.7 times with the same accuracy, as compared to a baseline method.

关键词： Malware detection Intel SGX Privacy preservation probabilistic data structures data fusion

来源：评论

学校读者我要写书评

暂无评论

ProbMinHash - A Class of Locality-Sensitive Hash Algorithms for the (Probability) Jaccard Similarity

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND data ENGINEERING 2022年第7期34卷 3491-3506页

作者： Ertl, Otmar Dynatrace Res A-4020 Linz Austria

The probability Jaccard similarity was recently proposed as a natural generalization of the Jaccard similarity to measure the proximity of sets whose elements are associated with relative frequencies or probabilities. In combination with a hash algorithm that maps those weighted sets to compact signatures which allow fast estimation of pairwise similarities, it constitutes a valuable method for big data applications such as near-duplicate detection, nearest neighbor search, or clustering. This paper introduces a class of one-pass locality-sensitive hash algorithms that are orders of magnitude faster than the original approach. The performance gain is achieved by calculating signature components not independently, but collectively. Four different algorithms are proposed based on this idea. Two of them are statistically equivalent to the original approach and can be used as drop-in replacements. The other two may even improve the estimation error by introducing statistical dependence between signature components. Moreover, the presented techniques can be specialized for the conventional Jaccard similarity, resulting in highly efficient algorithms that outperform traditional minwise hashing and that are able to compete with the state of the art.

关键词： Clustering algorithms Device-to-device communication Estimation error Indexes Measurement Time complexity Minwise hashing Jaccard similarity locality-sensitive hashing streaming algorithms probabilistic data structures

来源：评论

学校读者我要写书评

暂无评论

Staggered HLL: Near-continuous-time cardinality estimation with no overhead

引用

COMPUTER COMMUNICATIONS 2022年 193卷 168-175页

作者： Cornacchia, Alessandro Bianchi, Giuseppe Bianco, Andrea Giaccone, Paolo Politecn Torino Corso Duca Abruzzi 24 I-10129 Turin Italy Univ Roma Tor Vergata CNIT Via Politecn 1 I-00133 Rome Italy

Most of existing cardinality estimation algorithms do not support natively interval queries under a sliding window model and are thereby insensitive to data recency. We present Staggered-HyperLogLog (ST-HLL), a probabilistic data structure that takes inspiration from HyperLogLog (HLL) and provides nearly continuous-time estimation of cardinality rates, rather than absolute counts. Our solution has zero-bit overhead with respect to vanilla HLL and negligible additional computational complexity. It is based on a periodic staggered reset of HLL registers and a register equalization operation at query times to compensate for staggered counting. We tested ST-HLL over both synthetic and real Internet traffic traces, showing its ability to track variations of the flow cardinality, quickly adapting to variations under non-stationary flow arrival processes. We show that for the same amount of memory footprint, our algorithm improves the accuracy up to a factor 2x with respect to the state-of-the-art solution, Sliding HLL.

关键词： Network monitoring probabilistic data structures HyperLogLog counters Cardinality estimation

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：