Wyniki wyszukiwania - BazTech

1

Sprzętowa implementacja filtru Blooma bazująca na pojedynczej funkcji skrótu

Augustynowicz Paweł, Augustynowicz Aneta

Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne

|

2019

|

nr 7

557--560, CD

PL

Filtrem Blooma nazywamy probabilistyczną strukturę danych o niewielkiej zajętości pamięciowej umożliwiającą szybkie sprawdzenie obecności danego elementu w zbiorze. W ramach artykułu przedstawiono problem sprzętowej implementacji filtru Blooma w oparciu o wyłącznie jedną funkcję skrótu oraz metodologię „one-hashing”. W szczególności przeanalizowano wpływ zwiększania rozmiaru pamięci na zmniejszenie prawdopodobieństwa wystąpienia błędnej odpowiedzi pozytywnej.

EN

This article deals with the problem of hardware implementation of Bloom Filter based on one-hashing approach. Particularly, the dependency between the memory size and false positive ratio is examined.

2

Realizacja sprzętowego generatora indeksów z wykorzystaniem filtru Blooma

Mazurkiewicz Tomasz

Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne

|

2019

|

nr 3

61--66

PL

Funkcje generowania indeksów są wykorzystywane przede wszystkim do wyszukiwania wzorców w dużych zbiorach danych. Spowodowało to znaczny wzrost zainteresowania efektywną realizacją tych funkcji w czasach dynamicznego rozwoju technologii, takich jak np. Big Data. W literaturze przedstawiono wiele algorytmów skutecznie minimalizujących tego typu funkcje. Równocześnie zaproponowano metody ich sprzętowej realizacji. W ramach niniejszej pracy przedstawiono możliwość implementacji funkcji generowania indeksów z wykorzystaniem struktury probabilistycznej - filtru Blooma. Pokazano, że kosztem wprowadzenia niewielkiego prawdopodobieństwa otrzymania wyniku fałszywie pozytywnego, możliwa jest efektywna implementacja proponowanego rozwiązania. W tym celu przedstawiono ideę filtru Blooma z pojedynczą funkcją skrótu. Uzyskane wyniki dowodzą, że opisana struktura zapewnia mniejsze wykorzystanie pamięci od rozwiązania opisywanego w literaturze. Mimo że konieczne jest zrealizowanie dodatkowych obliczeń, w pracy pokazano, że mogą być one efektywnie zrealizowane w układach FPG A.

EN

Index generation functions are primarily used for pattern matching in large data sets. Efficient implementation of these functions is attracting significant interest due to the dynamic development of technologies such as Big Data. In the literature many algorithms were presented that efficiently minimize these functions. At the same time, methods of efficient hardware implementation have been proposed. In this paper, the possibility of implementing index generation functions using the probabilistic structure, i.e. a B loom filter, was analyzed. We show that at the cost of a small probability of a false positive result, it is possible to efficiently implement the proposed method. Furthermore, the idea of an One-Hashing Bloom filter is presented. The obtained results prove that the described structure provides lower memory usage than the structure described in the literature. Even though it requires additional computations, we prove that these operations can be efficiently implemented using FPG A devices.

3

Dobór funkcji skrótu spełniających wymagania sprzętowej implementacji filtru Blooma

Augustynowicz P.

Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne

|

2018

|

nr 8-9

605--608, CD

PL

Filtr Blooma to probabilistyczna struktura danych pozwalająca na szybkie sprawdzenie, czy dany element jest obecny we wcześniej zadanym zbiorze. W artykule przedstawiono problem wyboru funkcji skrótu dla sprzętowej implementacji filtru Blooma w układach FPGA, biorąc pod uwagę takie czynniki jak efektywność i zajętość. Podczas badań zaimplementowano i zrewidowano aplikacyjność w rozwiązaniach sprzętowych kilku popularnych algorytmów.

EN

This article deals with the problem of optimal choice of hash functions with application to hardware Bloom Filter implementation. Particularly, the efficiency of Bloom Filter implementation and its area occupancy for several common algorithms were investigated.

4

Calculating distributed denial of service attack probability in bloom-filter based information-centric networks

Vassilakis V. G., Wang L., Moscholios I. D., Logothetis M. D.

Image Processing & Communications

|

2016

|

Vol. 21, no. 1

7--22

EN

Information-Centric Networking (ICN) is an emerging networking technology that has been designed to directly operate on named content/information objects, rather than relying on the knowledge of the content location. According to the ICN principles, a user requests the information object by its name or some other form of object identiﬁer. After that, the ICN system is responsible for ﬁnding the particular object and send In git back to theuser. Despite a large number of works on ICN in recent years, ICN systems still face security challenges. This is especially true when considering different types of alternative networks, such as the wireless community networks (WCNs). In this work, we explore the applicability of ICN principles in the challenging and unpredictable environments of WCNs. We consider stateless contentdisseminationusingBloomﬁlters(BFs) and analyze two BF based approaches: the traditional single-stage BF and its generalization, the multi-stageBF. We fokus on the security aspects of BF based approaches and in particular on distributed denial of service (DDoS) attacks. Finally, we investigate the attaca probabilisty for various system and net work parameters, such as the number of hash functions, the BFmaximum ﬁll factor, and the number of hops toward the victim node.

5

Hardened Bloom filters, with an application to unobservability

Bernard M., Leprévost F.

Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica

|

2012

|

Vol. 12, no. 4

11--22

EN

Classical Bloom filters may be used to elegantly check if an element e belongs to a set S, and, if not, to add e to S. They do not store any data and only provide boolean answers regarding the membership of a given element in the set, with some probability of false positive answers. Bloom filters are often used in caching system to check that some requested data actually exist before doing a costly lookup to retrieve them. However, security issues may arise for some other applications where an active attacker is able to inject data crafted to degrade the filters’ algorithmic properties, resulting for instance in a Denial of Service (DoS) situation. This leads us to the concept of hardened Bloom filters, combining classical Bloom filters with cryptographic hash functions and secret nonces. We show how this approach is successfully used in the TrueNyms unobservability system and protects it against replay attacks.

6

Realizacja szybkiego wyszukiwania wzorców w układach FPGA

Machaczek K., Russek P., Jamro E., Wiatr K.

Pomiary Automatyka Kontrola

|

2008

|

R. 54, nr 8

540-542

PL

Niniejszy artykuł prezentuje sprzętową realizację filtracji Bloom'a w układach FPGA. Implementacja ta służy do szybkiego wyszukiwania wielu wzorców binarnych bądź znakowych w dużym zbiorze danych. Podczas filtracji Bloom'a sekwencyjnie podawane dane wejściowe są haszowane, a następnie obliczony hash jest porównywany w pamięci z podanymi wzorcami. Proces haszowania ciągu wejściowego jak i porównywanie z wzorcami odbywa się potokowo. Zaproponowana implementacja równoległa w jednym takcie zegara porównuje 16-bajtowy fragment ciągu wejściowego ze wszystkimi wzorcami. Przy uzyskanej szybkości zegara 100 MHz, szybkość przeszukiwania danych wejściowych wynosi 1.6 GB/s.

EN

This paper presents FPGAs implementation of Bloom filters. Consequently a great number of both binary and text patters can be quickly searched for in a large database. For Bloom filters, sequencially fed input data are hashed, then addresses a special memory which output data indicates whether the input string is or is not one of paterns. The whole implementation is strongly pipelined and parallel. Consequently, 16-byte of input data are processed in a single clock cycle at clock frequency 100 MHz, therefore the search throughput is 1.6 GB/s.