posted @
2023-10-24 15:25 春秋十二月 閱讀(209) |
評論 (0) |
編輯 收藏1. 區(qū)間圖：用于局部寄存器分配，基本塊內(nèi)的每個活躍范圍看作一個區(qū)間（最早定義位置+最新使用位置），所有活躍范圍構(gòu)成區(qū)間圖。區(qū)間圖是一種不精確的沖突圖（因為高估了活躍范圍的范圍而導致偽沖突，比如認為一個復制操作連接的或兩個源相同目標不同的復制操作產(chǎn)生重疊的兩個活躍范圍沖突，但實際沒有沖突），優(yōu)勢在于著色是P（復雜度O(|V|)或O(|E|)）而非NP問題。llvm早期的線性掃描分配器是基于區(qū)間圖在全局的擴展，比較適用于JIT編譯（減少編譯時間）
2. 一般圖：用于全局寄存器分配，是一種精確的沖突圖（由一組定義與一組使用構(gòu)成的網(wǎng)絡）。優(yōu)勢在于努力最小化溢出活躍范圍而生成高效執(zhí)行的代碼，但會犧牲編譯時間。llvm的greedy寄存器分配是基于一般圖的代表。編譯器使用的沖突圖可能會將機器約束條件比如多寄存器值/調(diào)用約定編碼進去而存在重復邊，導致不滿足圖論中的簡單圖定義，故這里采用一般圖
3. 弦圖：定義詳見
https://oi-wiki.org/graph/chord?；陟o態(tài)單賦值形式名建立的沖突圖是弦圖。優(yōu)勢在于可以做到最佳著色（復雜度O(|V|+|E|)）而非啟發(fā)式（基于一般圖的全局寄存器分配使用啟發(fā)式），利于減少寄存器壓力。劣勢在于必須將指派寄存器后的仍然為靜態(tài)單賦值代碼轉(zhuǎn)換為機器碼，而這種轉(zhuǎn)換可能增加寄存器壓力，以及插入一些可能非必要的復制操作，若復制操作實現(xiàn)的數(shù)據(jù)流與ssa phi函數(shù)對應，則分配器無法合并這種復制，這將破壞弦圖的性質(zhì)
4. 沖突圖拆分：查找其中的團分割即連通子圖，移除它劃分得到不相交的一些子圖，這樣一來，各子圖可獨立著色（有點類似活躍范圍拆分）而利于減少寄存器壓力，另外實現(xiàn)上還能節(jié)省下三角布爾矩陣（用于快速判斷兩結(jié)點是否沖突）的規(guī)模
#############################
寄存器分配與圖論的染色理論相關。其它的比如常量傳播與格代數(shù)及不動點相關，循環(huán)優(yōu)化與多面體、矩陣相關。這三方面是我目前看到的編譯器所用數(shù)學理論
posted @
2023-10-04 13:08 春秋十二月 閱讀(3891) |
評論 (0) |
編輯 收藏posted @
2023-09-30 08:47 春秋十二月 閱讀(108) |
評論 (0) |
編輯 收藏
有單向、雙向、三向3種認證方式，前兩者必須檢查時間戳以防重放攻擊，單向因為只有一個消息傳遞，如果僅靠一次性隨機數(shù)是無法判斷消息是否重放。雙向有兩個消息傳遞，一來一回，僅靠一次性隨機數(shù)只能檢測到發(fā)響應那方的重放。最后者則不必，可僅通過一次性隨機數(shù)檢測自己是否遭遇重放攻擊，因為接收第二個消息的那方，通過判斷第二個消息中隨機數(shù)是否等于自己先前已發(fā)送第一個消息中的那個，若不等于則為重放，若等于則發(fā)第三個確認消息給對方，對方收到并判斷確認消息中的隨機數(shù)是否等于先前它已發(fā)送第二個消息中的隨機數(shù)，若等于則說明第它收到的第一個消息的確是另一方發(fā)送的即非重放，否則為重放。因此三向認證可不必同步雙方時鐘。但正因為不強制檢查時間戳而可能導致
中間人攻擊：假設通信雙方為A、B，中間人為C，攻擊步驟如下
1. C與B認證時，發(fā)送先前已截獲的A到B請求消息給B
2. 截獲并存儲B到A的響應消息x，但不轉(zhuǎn)發(fā)，開始與A認證
3. 收到A的請求消息后，解密x取出其中的隨機數(shù)Rb作為響應給A消息中的隨機數(shù)，用自己私鑰簽署整個消息后發(fā)給A
4. 收到并轉(zhuǎn)發(fā)A的確認消息給B
以上完成后，C就能冒充A與B通信了。一種簡單的改進方法是先用對方的公鑰加密消息中的隨機數(shù)，再用自己的私鑰簽署整個消息。關于網(wǎng)絡協(xié)議的安全性分析，主流方法是形式化分析，可以借助相關工具來驗證找出漏洞
posted @
2023-09-30 08:00 春秋十二月 閱讀(457) |
評論 (0) |
編輯 收藏
1.
對于RSA，給定大整數(shù)n分解的一對素因子p和q，p或q是否素數(shù)決定不了安全性，但決定算法的正確性，也就是說p或q不能為合數(shù)，而安全性取決于n的位數(shù)及p、q的距離，n越大則難于素因子分解（因為素數(shù)測試是一個P問題，而因子分解是一個NP問題，其耗時是關于n的指數(shù)），|p - q|要大是為抵抗一種
特殊因子分解攻擊，論證如下：由(p+q)
2/4 - n = (p+q)
2/4 - pq = (p-q)
2/4，若|p - q|小，則(p-q)
2/4也小，因此(p+q)
2/4稍大于n，(p+q)/2稍大于n
1/2即根號n?？傻胣的如下分解法：a) 先順序檢查大于n
1/2的每一整數(shù)x，直至找到一個x使得x
2 - n是某一整數(shù)y的平方；b) 再由x
2 - n = y
2 得 n = (x+y)(x-y)。另外，p - 1和q - 1都應有大素因子（所有因子皆是大素數(shù)），以抵抗可能的
重復加密攻擊（重復加密較少步后可恢復出明文）
2.
對于DH密鑰交換，通常選擇階為素數(shù)的有限循環(huán)(子)群，這時素數(shù)決定了安全性。因素數(shù)不能再因子分解，故避免了針對階為合數(shù)的質(zhì)因子分解且利用中國剩余定理求離散對數(shù)的(已知最好)攻擊。具體講就是為了防
index-calculus方法求解離散對數(shù)，底層循環(huán)群G的素數(shù)模p要足夠大，長度1024位可實現(xiàn)80位安全等級，長度3072位可實現(xiàn)128位安全等級；另為了防
Pohlig-Hellman攻擊，G的階p-1必須不能因式分解為全部都是小整數(shù)的素數(shù)因子，且為了p-1的每個因子構(gòu)成的子群防
baby-step giant-step或
Pollards's rho攻擊，要求對80位安全等級而言，p-1的最小素因子必須至少為160位，而對128位安全等級，其至少為256位
3.
對于Hash函數(shù)，安全性要求有三點：第一是單向性，由于壓縮函數(shù)理論上存在碰撞，因此單向性是指計算不可行，為什么要單向性？因為若不單向，則可從結(jié)果比如簽名逆出原文消息；第二是抗弱沖突性即
第1類生日攻擊，計算不可行；第三是抗強沖突性即
第2類生日攻擊，計算不可行。這三點要求，取決于壓縮函數(shù)是否能抗差分、線性等密碼分析
4. 周知
Shamir門限方案基于多項式的拉格朗日插值公式，普遍的設計采用GF(q)域上的多項式，秘密s為f(0)，q是一個大于n的大素數(shù)（n是s被分成的部分數(shù)）。正常來講，參與者個數(shù)必須至少是設計時的k，才能恢復出正確的s。如果個數(shù)少于k比如k-1，則只能猜測s0=f(0)以構(gòu)建第k個方程，那么恢復得到的多項式g(x)等同設計時的多項式f(x)的概率是1/q。因為g(x)的項系數(shù)可以看作關于s0的同余式即h(s0)=(a+b*s0)mod q的形式，因q為素數(shù)，故依模剩余系遍歷定理，當s0取GF(q)一值時，則h(s0)唯一對應另一值。所以h(s0)等于f(0)的概率為1/q。由此可見，當q取80位以上，敵手攻擊概率不大于1/2
80，這已經(jīng)很低了。這種門限方案如同RSA加密，再次佐證了素數(shù)越大安全性越高
5.
PGP是密碼學經(jīng)典應用，體現(xiàn)在首先支持保密與認證業(yè)務的正交，即獨立或組合，且組合時按認證、壓縮、加密的順序，這個順序是經(jīng)考究有優(yōu)勢的；其次會話密鑰是一次性的，由安全偽隨機數(shù)生成器生成，且按公鑰加密；最后使用自研的密鑰環(huán)與信任網(wǎng)解決公鑰管理問題。理論本質(zhì)上，PGP提供的是一種保密認證業(yè)務的通用框架，因為具體的對稱加密算法、隨機數(shù)生成、公鑰算法，都可依需要靈活選配擴展。PGP有兩個問題跟組合與概率相關，一個是算密鑰環(huán)N個公鑰中，密鑰ID(64位)至少有兩個重復的概率？設所求概率為p，先算任意兩個不重復的概率q，令m=2
64，則q=m!/((m-N)!*m
N)，則p=1-q，不難看出，N越小則q越大則p越小，因?qū)嶋H應用N<<m，故p非常小可忽略，即PGP取公鑰中最低64有效位作密鑰ID，是可行的。另一個是簽名摘要暴露了前16位明文，對哈希函數(shù)安全的影響有多大？這問題意思應該是敵手拿到消息后但沒發(fā)送方的私鑰作簽名，只能窮舉變換原消息并求哈希值，使之與消息摘要剩余位組相等。這本質(zhì)是求
兩類生日攻擊碰撞概率大于0.5時所需的輸入量。在僅認證模式中，抗弱碰撞計算量降低為原來的1/2
16，抗強碰撞計算量至少降低為原來的1/2
8。另外，考慮到這16位明文可能的特殊性，有沒更快的代數(shù)攻擊，需進一步研究
posted @
2023-09-28 08:04 春秋十二月 閱讀(3041) |
評論 (0) |
編輯 收藏posted @
2023-09-26 16:47 春秋十二月 閱讀(2161) |
評論 (0) |
編輯 收藏
周知編譯原理龍書闡述的基本塊指令調(diào)度算法，它所使用的空的資源預約表RTD與每個指令的資源預約表RT，可以看作二維矩陣，行表示時鐘周期、列表示cpu資源，其定位的元素值1表示占用/預約，0表示空閑/非預約。前者是隨周期遞增而動態(tài)擴大的矩陣，后者是固定尺寸(維數(shù))的矩陣（指令花費周期與每周期預約資源皆已知）。在調(diào)度時，按帶優(yōu)先級比如關鍵路徑的拓撲排序基本塊內(nèi)的指令，順序選取一條指令Inst，計算每前驅(qū)發(fā)射周期加延遲的結(jié)果tmp，取所有tmp的最大值tmax作為Inst的發(fā)射周期，再判斷處理器資源是否可用，即RTD和RT作
與運算，得到一個新矩陣RTN，若RTN為
全零矩陣則tmax為Inst的最終發(fā)射周期，否則遞增tmax再做矩陣與運算，直至得到全零矩陣。最后更新RTD，即RTD與RT作
或運算結(jié)果存于RTD。重復上述過程直到基本塊末尾。
綜上不難看出，如果一個基本塊很大比如有1000條指令，平均每指令花2個周期，則RTD需要2000個條目，若一條目即矩陣每行占用32字節(jié)（256種資源數(shù)），則總量約64k。當然這對于現(xiàn)代內(nèi)存體量來說不算什么，但可以有更好的節(jié)省內(nèi)存的做法：RTD尺寸其實可以相對固定，其上限為基本塊中耗費周期最多指令的周期的一個大于1常數(shù)因子倍（為兼顧指令并行性），這樣一來就要增加當指令完成時（當前指令發(fā)射周期大于前一條的終止周期時復位前一條指令的RTD）從發(fā)射周期處復位RTD即作一個矩陣反運算的操作，其它步驟對應的矩陣與、矩陣或運算的操作保留不變。另由于RTD固定了尺寸，因此發(fā)射周期遞增后要取模
【備注】以上是我針對簡單機器模型（每種資源數(shù)量僅一個，比如整數(shù)運算單元1個，內(nèi)存訪問單元1個，浮點運算單元1個）用布爾矩陣作的優(yōu)化。如果是復雜的超標量機器即每種資源數(shù)有多個，那么只需修改如下：布爾矩陣換成整數(shù)矩陣；新增一個機器資源可用總數(shù)整數(shù)矩陣RDA（單列資源數(shù)同值），布爾矩陣與運算換成加法并與RDA比較，若大于RDA則遞增tmax；布爾矩陣或運算換成加法；布爾矩陣反運算換成減法，RTD減RT存于RTD
posted @
2023-09-23 12:14 春秋十二月 閱讀(373) |
評論 (0) |
編輯 收藏曾因朋友問到監(jiān)控，致使我探究了kretprobe的實現(xiàn)，想到編譯中的尾調(diào)用優(yōu)化，作個小結(jié)
?1. kretprobe_trampoline_holder該跳轉(zhuǎn)函數(shù)無參是必須的或說最好的通用設計，因為替換返回地址是非正常程序流程，即被探測函數(shù)的調(diào)用者無感知，不存在為跳轉(zhuǎn)函數(shù)準備入?yún)ⅰＨ粢O計傳參且只讀，則不會破壞被探測函數(shù)調(diào)用者的上下文，但跳轉(zhuǎn)函數(shù)內(nèi)部流程怎么用參數(shù)是個問題，這需要一種約定
?2. 跳轉(zhuǎn)函數(shù)為調(diào)用trampoline_handler準備入?yún)ⅲ丛跅Ｉ蠘?gòu)造一個（不完整的）pt_regs，再把它地址即棧頂賦給rdi，rdi是x86_64上傳入第一參數(shù)使用的寄存器，同時預留一個棧單元存放原返回地址（為什么要預留？因為被探測函數(shù)返回時，其調(diào)用者存放返回地址的?？臻g被釋放了，所以得在跳轉(zhuǎn)函數(shù)內(nèi)造一個）。由于trampoline_handler內(nèi)調(diào)到用戶自定義handler而傳入pt_regs，因此自定義handler內(nèi)要注意最好別改動pt_regs，否則會破壞被探測函數(shù)調(diào)用者的上下文
posted @
2023-09-13 02:26 春秋十二月 閱讀(362) |
評論 (0) |
編輯 收藏有理數(shù)域的本原多項式與有限域的本原多項式定義不同，前者不要求不可約（由高斯引理知兩個本原多項式的乘積還是本原），后者則必須不可約（確保生成的有限域其每個元素有逆元）。aes基于有限域F{0,1}設計，故使用的模8次多項式不可約
P(x)=x^8+x^4+x^3+x+1，但不是本原多項式，因為它的階是51而非255。有限域次數(shù)為8的本原多項式有16個、不可約多項式有30個（由莫比烏斯反演推出），具體多項式影響s盒與列混合操作的實現(xiàn)。不可約加之0的逆元規(guī)定為0，保證正確加解密。若0的逆元規(guī)定為非0比如x，則導致x有兩個逆元，便違反了逆元唯一性，除非s盒不用有限域設計。逆元等于其自身的非0元素只有1，原因可類比模素數(shù)二次剩余的求解
posted @
2023-09-13 02:00 春秋十二月 閱讀(408) |
評論 (0) |
編輯 收藏1. 若DFA D是用子集構(gòu)造法從NFA N構(gòu)造出來的，則L(D)=L(N)
2. 一個語言L被某個DFA接受，當且僅當被某個NFA接受
3. 一個語言L被某個£-NFA接受，當且僅當被某個DFA接受
4. 若對于某個DFA A，L=L(A)，則存在一個正則表達式R使得L=L(R)
5. 每一個用正則表達式定義的語言也可用有窮自動機定義
6. 若通過填表算法不能區(qū)分兩個狀態(tài)，則它們是等價的
7. DFA的狀態(tài)等價性是傳遞的
8. 若對于DFA每個狀態(tài)q及與q等價的所有狀態(tài)組成塊，則不同的狀態(tài)塊形成狀態(tài)集合的劃分。也就是說，每個狀態(tài)恰好屬于一個塊，同一塊中的所有成員都是等價的，從不同塊中選擇的狀態(tài)對都不是等價的
9. 根據(jù)等價狀態(tài)劃分算法最小化DFA D得到的DFA M是唯一的。也就是說，不存在其它等價于D的DFA N，其狀態(tài)數(shù)比M少
----------------------------------------------------------------------------------------
10. 對于正則表達式，空集是并運算的單位元、連接運算的零元，空串是連接運算的單位元
11. 若L和M都是正則語言，則L和M的并、交、差也是
12. 若L是字母表T上的正則語言，則~L=T*—L也是
13. 若L是正則語言，則L的反轉(zhuǎn)也是
14. 若L是字母表T上的正則語言，h是T上的一個同態(tài)，則h(L)也是正則的
15. 若h是字母表A到字母表T的同態(tài)，且L是T上的正則語言，則逆同態(tài)h^-1(L)也是正則的
posted @
2023-09-09 08:11 春秋十二月 閱讀(1146) |
評論 (0) |
編輯 收藏