顯示具有 algorithm 標籤的文章。 顯示所有文章
顯示具有 algorithm 標籤的文章。 顯示所有文章

2024/7/15

CBOR

RFC 8949 CBOR: Concise Binary Object Representation,這是一種輕量的二進位資料格式,可簡單理解為一種二進位的 JSON,設計目的是最小化處理程式碼,最小化訊息位元組大小。另外在 RFC 9052, 9053 CBOR Object Signing and Encryption (COSE) 制定了要如何對 CBOR 資料進行資料簽章與加密的方法。

online test

cbor.me

CBOR/web (plain)

可到這兩個網頁進行線上測試

測試時可以發現,不管是整數,字串,都有對應的編碼。甚至是 JSON 字串,也有對應的 Map (key-value pair) 的編碼方式

CBOR

header 有兩個資訊,前 3 bits 是 Major Type,後 5 個 bits 是 Additional Information

字節(byte)數 1 byte (CBOR Data Item Header) 動態長度 動態長度
結構 Major Type Additional Information Payload Length(可選) Data Payload(可選)
bit 3 Bits 5 Bits 動態長度 動態長度

CBOR 有八種 Major Type

首位元組的 lower 5 bits 在不同的主類型表示長度(除主類型 0 和主類型 1),如果長度指示不足,則依次使用後續位元組。

Major Type Name content
0 unsigned integer -
1 negative integer -
2 byte string N bytes
3 text string N bytes (UTF-8 text)
4 array of data items N data items
5 map of pairs of data items 2N data items (key/value pairs)
6 tag of number N 1 data item
7 simple/float -

比較特別的是 Major Type 6 裡面定義了 date time

0xC0 定義了 text-based date/time,0xC1 定義了 epoch-based date/time

還有 Major Type 7 裡面的

  • False 編碼後 0xF4
  • True 編碼後 0xF5
  • Null 編碼後 0b1110_0000 + 0b0001_01110 (22) = 0xF6

implementation

CBOR — Concise Binary Object Representation | Implementations

這邊列出了不同程式語言的 CBOR 實作 library

這邊用 js 測試

<html>
<script src="https://cdn.jsdelivr.net/npm/cbor-js@0.1.0/cbor.min.js"></script>
<script>

function hex(buffer) {
    var s = '', h = '0123456789ABCDEF';
    (new Uint8Array(buffer)).forEach((v) => { s += h[v >> 4] + h[v & 15]; });
    return s;
}

function test0() {
    console.log("");
    console.log("test0 unsigned integer");
    var initial = 1000;
    var encoded = CBOR.encode(initial);
    var decoded = CBOR.decode(encoded);
    console.log("initial =" + initial);
    console.log("encoded hex=", hex(encoded));
    console.log("decoded =" + decoded);
}

function test1() {
    console.log("");
    console.log("test1 negative integer");
    var initial = -1000;
    var encoded = CBOR.encode(initial);
    var decoded = CBOR.decode(encoded);
    console.log("initial =" + initial);
    console.log("encoded hex=", hex(encoded));
    console.log("decoded =" + decoded);
}

function test2() {
    console.log("");
    console.log("test2 byte string");
    var initial = new Uint8Array([0, 1, 2, 3]);
    var encoded = CBOR.encode(initial);
    var decoded = CBOR.decode(encoded);
    console.log("initial =", initial);
    console.log("encoded hex=", hex(encoded));
    console.log("decoded =", decoded);
}

function test3() {
    console.log("");
    console.log("test3 text string");
    var initial = "text string";
    var encoded = CBOR.encode(initial);
    var decoded = CBOR.decode(encoded);
    console.log("initial =", initial);
    console.log("encoded hex=", hex(encoded));
    console.log("decoded =", decoded);
}

function test4() {
    console.log("");
    console.log("test4 array");
    var initial = [1, "2"];
    var encoded = CBOR.encode(initial);
    var decoded = CBOR.decode(encoded);
    console.log("initial =", initial);
    console.log("encoded hex=", hex(encoded));
    console.log("decoded =", decoded);
}

function test5() {
    console.log("");
    console.log("test5 map");
    var initial = { Hello: "World" };
    var encoded = CBOR.encode(initial);
    var decoded = CBOR.decode(encoded);
    console.log("initial =", initial);
    console.log("encoded hex=", hex(encoded));
    console.log("decoded =", decoded);
}

function test6() {
    console.log("");
    console.log("test6 float");
    var initial = 3.1415;
    var encoded = CBOR.encode(initial);
    var decoded = CBOR.decode(encoded);
    console.log("initial =", initial);
    console.log("encoded hex=", hex(encoded));
    console.log("decoded =", decoded);
}

function test7() {
    console.log("");
    console.log("test7 true");
    var initial = true;
    var encoded = CBOR.encode(initial);
    var decoded = CBOR.decode(encoded);
    console.log("initial =", initial);
    console.log("encoded hex=", hex(encoded));
    console.log("decoded =", decoded);
}

function test8() {
    console.log("");
    console.log("test8 null");
    var initial = null;
    var encoded = CBOR.encode(initial);
    var decoded = CBOR.decode(encoded);
    console.log("initial =", initial);
    console.log("encoded hex=", hex(encoded));
    console.log("decoded =", decoded);
}

test0();
test1();
test2();
test3();
test4();
test5();
test6();
test7();
test8();

</script>
</html>

結果

test0 unsigned integer
initial =1000
encoded hex= 1903E8
decoded =1000

test1 negative integer
initial =-1000
encoded hex= 3903E7
decoded =-1000

test2 byte string
initial = Uint8Array(4) [0, 1, 2, 3, buffer: ArrayBuffer(4), byteLength: 4, byteOffset: 0, length: 4, Symbol(Symbol.toStringTag): 'Uint8Array']
encoded hex= 4400010203
decoded = Uint8Array(4) [0, 1, 2, 3, buffer: ArrayBuffer(5), byteLength: 4, byteOffset: 1, length: 4, Symbol(Symbol.toStringTag): 'Uint8Array']

test3 text string
initial = text string
encoded hex= 6B7465787420737472696E67
decoded = text string

test4 array
initial = (2) [1, '2']
encoded hex= 82016132
decoded = (2) [1, '2']

test5 map
initial = {Hello: 'World'}
encoded hex= A16548656C6C6F65576F726C64
decoded = {Hello: 'World'}

test6 float
initial = 3.1415
encoded hex= FB400921CAC083126F
decoded = 3.1415

test7 true
initial = true
encoded hex= F5
decoded = true

test8 null
initial = null
encoded hex= F6
decoded = null

references

# 物聯網專用資料交換格式 CBOR

cobr.io

CBOR_百度百科

2023/3/6

Rate-Limit Algorithm

rate-limit 是在某個時間區間內,能夠被執行的次數限制。在大型分散式系統,必須要內建這個限制,避免系統因為短時間內收到大量的 requests 造成問題。

系統有可能會遇到的攻擊

  1. brute force attacks

    攻擊者可能針對 login 及忘記密碼,用亂數帳號進行暴力的攻擊,試圖取得可以登入系統的帳號

  2. Dos, DDos

    攻擊者利用大量的 requests 癱瘓系統運作,導致系統無法接受並處理正常的使用者的 requests

  3. Web Scraping

    這是網頁抓取的方法,攻擊者可透過工具,分析網頁的內容,並抓取整個網站的所有可能的連結資料。

  • Rate Limit

    限制 requests 在某段時間區間內,允許執行的數量

  • Throttling

    控制 request 可被服務的頻率,ex: 控制 requests 每 100ms 可處理 10 個 requests,如果超過這個頻率的 request,可以允許另一個 threshold 的數量被處理,ex: 15/100ms,直到超過這個 threshold,就會被拒絕服務

Token Bucket

想像有一個水桶,裡面放 n 個 token,當使用者發出 request,必須要先到水桶取得一個 token,取得 token 後,就能繼續執行,如果無法取得 token,就會被拒絕。

水桶中的 token 會依照 1/n second 的速度,補充 token 到水桶中,直到補滿 n 個 token。

當水桶裡面有 n 個 token,可允許瞬間發生 n 個 requests,也就是同時被取走 n 個 tokens,也就是允許系統突然暴增的 requests。

Leaky Bucket

跟 Token Bucket 很相近,一樣想像有個水桶,預先設定了該水桶可流出 token 的速度,如果收到 requests 的速度超過允許流出的速度,就會累積在水桶裡面 (queue),如果水桶裡面超過了 n 個 tokens,後續的 requests 會被丟棄。

系統不允許發生突然暴增的 requests。

Fixed Window Counter

預先定義每個時間區間下允許執行的 request 數量 n,時間區間是固定的 (ex: 00:00:01 ~ 00:00:02, 00:00:02 ~ 00:00:03),每個時間區間都有一個 counter,當發生了新的 requests,就會計算這個時間區間的 counter,如果新增的 request 讓 counter 超過 n,就必須丟棄這個 request。

這個方法可能會遇到的問題是,如果時間區間 (00:00:01.500 ~ 00:00:02.000) 及 (00:00:02.000 ~ 00:00:02.500) 都產生了 n 個 requests,就等於在時間區間 (00:00:01.500 ~ 00:00:02.500) 發生了 2n 個 requests。

Sliding Window Logs

類似 Fixed Window Counter,記錄每一個 reuqest 發生的時間店,當有新的 request 發生時,會去比較目前的時間點到先前某一個時間點,這個時間區間的 requests 數量,用這個數量來衡量是否允許執行這個 request,如果超過了預先定義的數量,就會丟棄這個 request。

Sliding Window Counter

這個方法整合了 Fixed Window Counter 及 Sliding Window Log 的方法,概念上也是用 Fixed Window Counter,但將每個時間區間,又再切割了多個子區間。再比對某個 requst 是否允許執行時,就是比對目前這個時間點到先前多個子時間區間的 counter 總和,如果超過預先定義的值,就會丟棄該 request。

有了 Fixed Window Counter 及 Sliding Window Log 的優點,且實作並不困難。

References

實作 API Rate limiter George's blog

System Design Concept: Rate limiting

Rate limiting - Wikipedia

2021/11/15

Boyer-Moore字串匹配演算法

Boyer-Moore 演算法又稱BM演算法,是1977 年 Robert S. Boyer and J Strother Moore 提出的高效率字串搜尋演算法。

在開始搜尋字串之前,會先對搜尋目標 pattern 進行預處理 preprocessing 的動作,前處理可得到後續要使用的「好後綴位移」(good-suffix shift)和「壞字元位移」(bad-character shift) 兩種資料。

接下來在使用這個 pattern 到原文搜尋字串時,就能利用「好後綴位移」(good-suffix shift)和「壞字元位移」(bad-character shift),來想辦法讓目前無法與樣本相匹配的文字索引位置,能夠位移最多個字元的索引距離,減少原文字元與樣本字元的判斷是否相同的次數,來加速字串搜尋。

「好後綴」為目前位置之樣本和原文相符的字串後綴;「壞字元」為目前位置之樣本和原文從後面判斷第一個出現的不相符字元,就是好後綴開頭的前一個字元。

定義

bad-character

目前無法與 pattern 匹配的字元,匹配順序是由 pattern 最後面往前找

good-suffix

在匹配遇到 bad-character 之前,跟 pattern 匹配成功的字串

bad-character shift rule

往右移動的字元數 = "bad-character" 在 pattern 中出現的位置 - "bad-character" 在 pattern 中出現最右邊的位置

「把 pattern 往右移動最少幾個索引值後,pattern 本身所含有的『壞字元』能和剛剛在原文中發現的『壞字元』對齊」

如果 pattern 中不存在 bad-character,則最右邊的位置是在 pattern 的前面一個字元。也就是要把 pattern 往右移動最少幾個索引值後,pattern 的第1個字元會在原文的「壞字元」的下一個索引位置。

good-suffix shift rule

往右移動的字元數 = "good-suffix" 在 pattern 中出現的位置 - "good-suffix" 在 pattern 中最右邊出現且 prefix 字元不同的位置

要把 pattern 往右移動最少幾個索引值後,pattern 本身所含有的 good-suffix 或是延伸的good-suffix能和剛剛在原文中發現的 good-suffix 或是延伸的 good-suffix 對齊。

實例

搜尋 pattern:

EXAMPLE

原文:

HERE IS A SIMPLE EXAMPLE

Step 1

HERE IS A SIMPLE EXAMPLE
EXAMPLE
  • S 跟 E 不同,這時候的 S 為 bad-character
  • 因為沒有一個字元一樣,所以沒有 good-suffix
  • 因為 EXAMPLE 裡面不存在 S,無法完成「把EXAMPLE這個 pattern 往右移動最少幾個索引值後,pattern 本身所含有的『壞字元』能和剛剛在原文中發現的『壞字元』對齊」這個條件
  • 現在的 bad-character shift,變成是要把EXAMPLE這個樣本往右移動最少幾個索引值後,樣本的第1個字元會在原文的「壞字元」的下一個索引位置

Step 2

HERE IS A SIMPLE EXAMPLE
       EXAMPLE
  • 因為 P 跟 E 不同,P 為 bad-character
  • 沒有字元匹配成功,故沒有 good-suffix
  • 接下來判斷「把EXAMPLE這個 pattern 往右移動最少幾個索引值後,pattern 本身所含有的『壞字元』能和剛剛在原文中發現的『壞字元』對齊」這個條件,故往右移動 2 個字元

Step 3

HERE IS A SIMPLE EXAMPLE
         EXAMPLE
  • MPLE 一樣,稱為 good-suffix
  • I 跟 A 不同,稱為 bad-character
  • 因為 EXA 裡面不存在 I,無法完成「把EXAMPLE這個 pattern 往右移動最少幾個索引值後,pattern 本身所含有的『壞字元』能和剛剛在原文中發現的『壞字元』對齊」這個條件
  • 現在的 bad-character shift,變成是要把EXAMPLE這個樣本往右移動最少幾個索引值後,樣本的第1個字元會在原文的「壞字元」的下一個索引位置,所以是 3
  • 同時利用 good-suffix MPLE 以及 PLE, LE, E,計算 good-suffix shift。
  • 目標是要把EXAMPLE這個 pattern 往右移動最少幾個索引值後,pattern 本身所含有的 good-suffix 或是延伸的good-suffix能和剛剛在原文中發現的 good-suffix 或是延伸的 good-suffix 對齊。
  • 先看 MPLE,無法在 pattern 右移後,還能跟 MPLE 對齊
  • 無法在 pattern 右移後,跟 PLE 對齊
  • 無法在 pattern 右移後,跟 LE 對齊
  • 可以在 pattern 右移後,跟 E 對齊,pattern 必須右移 6 個字元
  • 因為 bad-character shift 為 3,good-suffix shift 為 6,選擇使用 good-suffix shift 為 6

Step 4

HERE IS A SIMPLE EXAMPLE
               EXAMPLE
  • P 與 E 不同,稱為 bad-character
  • 接下來判斷「把EXAMPLE這個 pattern 往右移動最少幾個索引值後,pattern 本身所含有的『壞字元』能和剛剛在原文中發現的『壞字元』對齊」這個條件,故往右移動 2 個字元

Step 5

HERE IS A SIMPLE EXAMPLE
                 EXAMPLE
  • EXAMPLE 完全一樣,搜尋完成

References

Boyer-Moore-MagicLen(BM-MagicLen)字串搜尋演算法,超快速的全文搜尋演算法

演算法: Boyer-Moore字串匹配演算法

演算法――字串匹配之BM演算法

字串匹配Boyer-Moore演算法:文字編輯器中的查詢功能是如何實現的?

字串搜尋演算法Boyer-Moore的Java實現

字符串匹配的Boyer-Moore算法

图解字符串匹配的KMP算法